beblocksched.c 18.2 KB
Newer Older
1
2
3
4
5
/*
 * Author:      Matthias Braun, Christoph Mallon
 * Date:		27.09.2006
 * Copyright:   (c) Universitaet Karlsruhe
 * License:     This file is protected by GPL -  GNU GENERAL PUBLIC LICENSE.
Christian Würdig's avatar
Christian Würdig committed
6
 * CVS-Id:      $Id$
7
8
9
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
Christian Würdig's avatar
Christian Würdig committed
10
#endif /* HAVE_CONFIG_H */
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include "beblocksched.h"

#include <stdlib.h>

#include "array.h"
#include "pdeq.h"

#include "iredges.h"
#include "irgwalk.h"
#include "irgraph_t.h"
#include "irloop.h"
#include "irprintf.h"
#include "irdump_t.h"
25
26
#include "irtools.h"
#include "debug.h"
27
#include "beirgmod.h"
28
29
#include "bemodule.h"
#include "be.h"
30
31
32
33
34

#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#include <libcore/lc_timing.h>
Christian Würdig's avatar
Christian Würdig committed
35
#endif /* WITH_LIBCORE */
36
37
38
39

#ifdef WITH_ILP
#include <lpp/lpp.h>
#include <lpp/lpp_net.h>
Christian Würdig's avatar
Christian Würdig committed
40
#endif /* WITH_ILP */
41
42
43
44
45
46
47

typedef enum _blocksched_algos_t {
	BLOCKSCHED_NAIV, BLOCKSCHED_EXTBB, BLOCKSCHED_GREEDY, BLOCKSCHED_ILP
} blocksched_algos_t;

static int algo = BLOCKSCHED_GREEDY;

Matthias Braun's avatar
Matthias Braun committed
48
#ifdef WITH_LIBCORE
49
50
51
52
53
54
static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
	{ "naiv",	BLOCKSCHED_NAIV },
	{ "extbb",	BLOCKSCHED_EXTBB },
	{ "greedy", BLOCKSCHED_GREEDY },
#ifdef WITH_ILP
	{ "ilp",    BLOCKSCHED_ILP },
Christian Würdig's avatar
Christian Würdig committed
55
#endif /* WITH_ILP */
56
57
58
59
60
61
62
63
	{ NULL,     0 }
};

static lc_opt_enum_int_var_t algo_var = {
	&algo, blockschedalgo_items
};

static const lc_opt_table_entry_t be_blocksched_options[] = {
Christian Würdig's avatar
Christian Würdig committed
64
	LC_OPT_ENT_ENUM_INT ("algo", "the block scheduling algorithm", &algo_var),
65
66
	{ NULL }
};
Matthias Braun's avatar
Matthias Braun committed
67
#endif
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

/*
 *   ____                   _
 *  / ___|_ __ ___  ___  __| |_   _
 * | |  _| '__/ _ \/ _ \/ _` | | | |
 * | |_| | | |  __/  __/ (_| | |_| |
 *  \____|_|  \___|\___|\__,_|\__, |
 *                            |___/
 */

typedef struct _blocksched_entry_t {
	ir_node *block;
	struct _blocksched_entry_t *next;
	struct _blocksched_entry_t *prev;
} blocksched_entry_t;

typedef struct _edge_t {
85
86
87
88
	ir_node *block;             /**< source block */
	int     pos;                /**< number of cfg predecessor (target) */
	double  execfreq;           /**< the frequency */
	int     highest_execfreq;   /**< flag that indicates wether this edge is the edge with the highest
89
90
91
92
							   	     execfreq pointing away from this block */
} edge_t;

typedef struct _blocksched_env_t {
93
	ir_graph       *irg;
94
	struct obstack *obst;
95
96
97
98
99
	ir_exec_freq   *execfreqs;
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
100
101
} blocksched_env_t;

102
103
104
105
/**
 * Collect cfg frequencies of all edges between blocks.
 * Also determines edge with highest frequency.
 */
106
107
static void collect_egde_frequency(ir_node *block, void *data)
{
108
109
110
111
112
	blocksched_env_t   *env        = data;
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
	int                arity;
	edge_t             edge;
113
114
	blocksched_entry_t *entry;

115
	entry        = obstack_alloc(env->obst, sizeof(entry[0]));
116
	entry->block = block;
117
118
	entry->next  = NULL;
	entry->prev  = NULL;
119
120
	set_irn_link(block, entry);

121
	if (block == startblock)
122
123
124
		return;

	arity = get_irn_arity(block);
125
126
127
128
129

	if (arity == 1) {
		edge.block            = block;
		edge.pos              = 0;
		edge.execfreq         = get_block_execfreq(env->execfreqs, block);
130
131
132
		edge.highest_execfreq = 1;
		ARR_APP1(edge_t, env->edges, edge);
	} else {
133
		int    i;
134
		double highest_execfreq = -1;
135
		int    highest_edge_num = -1;
136
137

		edge.block = block;
138
139
		for (i = 0; i < arity; ++i) {
			double  execfreq;
140
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
141

142
143
			execfreq = get_block_execfreq(env->execfreqs, pred_block);

144
145
			edge.pos              = i;
			edge.execfreq         = execfreq;
146
147
			edge.highest_execfreq = 0;
			ARR_APP1(edge_t, env->edges, edge);
148
149

			if (execfreq > highest_execfreq) {
150
151
152
153
154
				highest_execfreq = execfreq;
				highest_edge_num = ARR_LEN(env->edges) - 1;
			}
		}

155
156
		if(highest_edge_num >= 0)
			env->edges[highest_edge_num].highest_execfreq = 1;
157
158
159
160
161
162
163
	}
}

static int cmp_edges(const void *d1, const void *d2)
{
	const edge_t *e1 = d1;
	const edge_t *e2 = d2;
164
165

	return QSORT_CMP(e2->execfreq, e1->execfreq);
166
167
168
169
170
171
172
}

static void coalesce_blocks(blocksched_env_t *env)
{
	int i;
	int edge_count = ARR_LEN(env->edges);

173
174
175
176
177
	/* run1: only look at jumps */
	for (i = 0; i < edge_count; ++i) {
		const edge_t *edge  = &env->edges[i];
		ir_node      *block = edge->block;
		ir_node      *pred_block;
178
179
		blocksched_entry_t *entry, *pred_entry;

180
181
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
182
183
			continue;

184
185
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
186
187
188
			continue;

		pred_block = get_Block_cfgpred_block(block, edge->pos);
189
		entry      = get_irn_link(block);
190
191
		pred_entry = get_irn_link(pred_block);

192
		if (pred_entry->next != NULL || entry->prev != NULL)
193
			continue;
194
195
196

		/* only coalesce jumps */
		if (get_block_succ_next(pred_block, get_block_succ_first(pred_block)) != NULL)
197
198
			continue;

199
200
201
		/* schedule the 2 blocks behind each other */
		DBG((env->dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n",
		           pred_entry->block, entry->block, edge->execfreq));
202
		pred_entry->next = entry;
203
		entry->prev      = pred_entry;
204
205
	}

206
207
208
209
210
	/* run2: remaining edges */
	for (i = 0; i < edge_count; ++i) {
		const edge_t *edge  = &env->edges[i];
		ir_node      *block = edge->block;
		ir_node      *pred_block;
211
212
		blocksched_entry_t *entry, *pred_entry;

213
214
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
215
216
217
			continue;

		pred_block = get_Block_cfgpred_block(block, edge->pos);
218
		entry      = get_irn_link(block);
219
220
		pred_entry = get_irn_link(pred_block);

Matthias Braun's avatar
Matthias Braun committed
221
		/* is 1 of the blocks already attached to another block? */
222
		if (pred_entry->next != NULL || entry->prev != NULL)
223
224
			continue;

225
226
227
		/* schedule the 2 blocks behind each other */
		DBG((env->dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n",
		           pred_entry->block, entry->block, edge->execfreq));
228
		pred_entry->next = entry;
229
		entry->prev      = pred_entry;
230
231
232
233
234
	}
}

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
235
236
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
237
	blocksched_entry_t *succ_entry;
238
239
	const ir_edge_t    *edge;
	double             best_succ_execfreq;
240

241
	if (irn_visited(block))
242
		return;
243

244
245
246
	env->blockcount++;
	mark_irn_visited(block);

247
	DBG((env->dbg, LEVEL_1, "Pick succ of %+F\n", block));
248

249
	/* put all successors into the worklist */
250
251
252
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

253
		if (irn_visited(succ_block))
254
255
			continue;

256
257
		/* we only need to put the first of a series of already connected
		 * blocks into the worklist */
258
		succ_entry = get_irn_link(succ_block);
259
260
261
		while (succ_entry->prev != NULL) {
			/* break cycles... */
			if (succ_entry->prev->block == succ_block) {
262
				succ_entry->prev->next = NULL;
263
				succ_entry->prev       = NULL;
264
265
266
267
268
				break;
			}
			succ_entry = succ_entry->prev;
		};

269
		if (irn_visited(succ_entry->block))
270
271
			continue;

272
		DBG((env->dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
273
274
275
		pdeq_putr(env->worklist, succ_entry->block);
	}

276
	if (entry->next != NULL) {
277
278
279
280
		pick_block_successor(entry->next, env);
		return;
	}

281
	DBG((env->dbg, LEVEL_1, "deciding...\n"));
282
	best_succ_execfreq = -1;
283

284
	/* no successor yet: pick the successor block with the highest execution
285
286
	 * frequency which has no predecessor yet */

287
288
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);
289
		double  execfreq;
290

291
		if (irn_visited(succ_block))
292
293
294
			continue;

		succ_entry = get_irn_link(succ_block);
295
		if (succ_entry->prev != NULL)
296
297
			continue;

Michael Beck's avatar
Michael Beck committed
298
		execfreq = get_block_execfreq(env->execfreqs, succ_block);
299
		if (execfreq > best_succ_execfreq) {
300
301
302
303
304
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

305
306
	if (succ == NULL) {
		DBG((env->dbg, LEVEL_1, "pick from worklist\n"));
307
308

		do {
309
310
			if (pdeq_empty(env->worklist)) {
				DBG((env->dbg, LEVEL_1, "worklist empty\n"));
311
312
313
				return;
			}
			succ = pdeq_getl(env->worklist);
314
		} while (irn_visited(succ));
315
316
	}

317
318
	succ_entry       = get_irn_link(succ);
	entry->next      = succ_entry;
319
320
321
322
323
324
325
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
326
327
328
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
	blocksched_entry_t *entry      = get_irn_link(startblock);
329
330
331
332
333
334
335
336
337
338
339

	inc_irg_visited(irg);

	env->worklist = new_pdeq();
	pick_block_successor(entry, env);
	assert(pdeq_empty(env->worklist));
	del_pdeq(env->worklist);

	return entry;
}

340
341
342
343
344
static ir_node **create_blocksched_array(blocksched_env_t *env, blocksched_entry_t *first,
										int count, struct obstack* obst)
{
	int                i = 0;
	ir_node            **block_list;
345
346
347
	blocksched_entry_t *entry;

	block_list = NEW_ARR_D(ir_node *, obst, count);
348
349
350
	DBG((env->dbg, LEVEL_1, "Blockschedule:\n"));

	for (entry = first; entry != NULL; entry = entry->next) {
351
352
		assert(i < count);
		block_list[i++] = entry->block;
353
		DBG((env->dbg, LEVEL_1, "\t%+F\n", entry->block));
354
355
356
357
358
359
360
361
	}
	assert(i == count);

	return block_list;
}

static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execfreqs)
{
362
363
	blocksched_env_t   env;
	struct obstack     obst;
364
	blocksched_entry_t *start_entry;
365
	ir_node            **block_list;
366
367
368

	obstack_init(&obst);

369
370
371
372
373
	env.irg        = irg;
	env.obst       = &obst;
	env.execfreqs  = execfreqs;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
374
	env.blockcount = 0;
375
	FIRM_DBG_REGISTER(env.dbg, "firm.be.blocksched");
376
377
378
379
380
381
382
383
384

	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

	// sort interblock edges by execution frequency
	qsort(env.edges, ARR_LEN(env.edges), sizeof(env.edges[0]), cmp_edges);

	be_remove_empty_blocks(irg);

385
	if (algo != BLOCKSCHED_NAIV)
386
387
388
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
389
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount, get_irg_obstack(irg));
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407

	DEL_ARR_F(env.edges);
	obstack_free(&obst, NULL);

	return block_list;
}

/*
 *  ___ _     ____
 * |_ _| |   |  _ \
 *  | || |   | |_) |
 *  | || |___|  __/
 * |___|_____|_|
 *
 */

#ifdef WITH_ILP
typedef struct _ilp_edge_t {
408
409
410
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
411
412
413
414
} ilp_edge_t;

typedef struct _blocksched_ilp_env_t {
	blocksched_env_t env;
415
416
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
417
418
419
420
421
422
423
424
425
426
427
428
} blocksched_ilp_env_t;

typedef struct _blocksched_ilp_entry_t {
	ir_node *block;
	struct _blocksched_entry_t *next;
	struct _blocksched_entry_t *prev;

	int out_cst;
} blocksched_ilp_entry_t;

static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
{
429
	char       name[64];
430
	ilp_edge_t edge;
431
	int        edgeidx = ARR_LEN(env->ilpedges);
432
433
434

	snprintf(name, sizeof(name), "edge%d", edgeidx);

435
436
	edge.block  = block;
	edge.pos    = pos;
437
438
439
440
441
442
443
444
	edge.ilpvar = lpp_add_var_default(env->lpp, name, lpp_binary, execfreq, 1.0);

	ARR_APP1(ilp_edge_t, env->ilpedges, edge);
	return edgeidx;
}

static void collect_egde_frequency_ilp(ir_node *block, void *data)
{
445
446
447
448
449
450
451
	blocksched_ilp_env_t *env        = data;
	ir_graph             *irg        = env->env.irg;
	ir_node              *startblock = get_irg_start_block(irg);
	int                  arity;
	lpp_cst_t            cst;
	char                 name[64];
	int                  out_count;
452
453
454
455
456
	blocksched_ilp_entry_t *entry;

	snprintf(name, sizeof(name), "block_out_constr_%ld", get_irn_node_nr(block));
	out_count = get_irn_n_edges_kind(block, EDGE_KIND_BLOCK);

457
458
459
460
	entry          = obstack_alloc(env->env.obst, sizeof(entry[0]));
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
461
462
463
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, out_count - 1);
	set_irn_link(block, entry);

464
	if (block == startblock)
465
466
467
		return;

	arity = get_irn_arity(block);
468
	if (arity == 1) {
469
470
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
471
472
	}
	else {
473
474
475
476
477
478
		int i;
		int *edgenums = alloca(sizeof(edgenums[0]) * arity);

		snprintf(name, sizeof(name), "block_in_constr_%ld", get_irn_node_nr(block));
		cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, arity - 1);

479
480
481
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
482
			ilp_edge_t *edge;
483
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
484
485

			execfreq = get_block_execfreq(env->env.execfreqs, pred_block);
486
487
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
488
489
490
491
492
493
494
495
			lpp_set_factor_fast(env->lpp, cst, edge->ilpvar, 1.0);
		}
	}
}


static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
496
497
	int  i;
	int  edge_count = ARR_LEN(env->ilpedges);
498
499
500

	/* complete out constraints */
	for(i = 0; i < edge_count; ++i) {
501
502
503
		const ilp_edge_t *edge  = &env->ilpedges[i];
		ir_node          *block = edge->block;
		ir_node          *pred;
504
505
		blocksched_ilp_entry_t *entry;

506
507
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
508
509
			continue;

510
		pred  = get_Block_cfgpred_block(block, edge->pos);
511
512
		entry = get_irn_link(pred);

513
514
		DBG((env->env.dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
				  pred, block, edge->pos));
515
516
517
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

518
519
520
521
522
523
524
525
526
527
528
529
#if 0
	{
		FILE *f;
		char fname[256];
		lpp_dump(env->lpp, "lpp.out");
		snprintf(fname, sizeof(fname), "lpp_%s.plain", get_irg_dump_name(env->env.irg));
		f = fopen(fname, "w");
		lpp_dump_plain(env->lpp, f);
		fclose(f);
	}
#endif

530
531
532
533
534
	//lpp_solve_net(env->lpp, main_env->options->ilp_server, main_env->options->ilp_solver);
	lpp_solve_net(env->lpp, "i44pc52", "cplex");
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
535
536
537
538
539
	for (i = 0; i < edge_count; ++i) {
		const ilp_edge_t   *edge  = &env->ilpedges[i];
		ir_node            *block = edge->block;
		ir_node            *pred;
		int                is_jump;
540
541
542
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

543
544
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
545
546
547
			continue;

		is_jump = lpp_get_var_sol(env->lpp, edge->ilpvar);
548
		if (is_jump)
549
550
			continue;

551
552
		pred       = get_Block_cfgpred_block(block, edge->pos);
		entry      = get_irn_link(block);
553
554
555
		pred_entry = get_irn_link(pred);

		assert(entry->prev == NULL && pred_entry->next == NULL);
556
		entry->prev      = pred_entry;
557
558
559
560
561
562
563
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
564
565
566
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
567
568
569

	obstack_init(&obst);

570
571
572
573
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.execfreqs  = execfreqs;
	env.env.worklist   = NULL;
574
	env.env.blockcount = 0;
575
576
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
	FIRM_DBG_REGISTER(env.env.dbg, "firm.be.blocksched");
577
578
579
580
581
582
583
584
585
586
587

	env.lpp = new_lpp("blockschedule", lpp_minimize);
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

	irg_block_walk_graph(irg, collect_egde_frequency_ilp, NULL, &env);

	be_remove_empty_blocks(irg);
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
588
	block_list  = create_blocksched_array(&env.env, start_entry, env.env.blockcount, get_irg_obstack(irg));
589
590
591
592
593
594
595

	DEL_ARR_F(env.ilpedges);
	free_lpp(env.lpp);
	obstack_free(&obst, NULL);

	return block_list;
}
Christian Würdig's avatar
Christian Würdig committed
596
#endif /* WITH_ILP */
597
598
599
600
601
602
603
604
605
606
607
608

/*
 *  _____      _   ____  ____
 * | ____|_  _| |_| __ )| __ )
 * |  _| \ \/ / __|  _ \|  _ \
 * | |___ >  <| |_| |_) | |_) |
 * |_____/_/\_\\__|____/|____/
 *
 */

/** A simple forward single linked list. */
typedef struct {
609
610
	ir_node  *start;   /**< start of the list */
	ir_node  *end;     /**< last block in the list */
611
612
613
614
	unsigned n_blks;  /**< number of blocks in the list */
} anchor;

static void add_block(anchor *list, ir_node *block) {
615
	if (list->start == NULL) {
616
		list->start = block;
617
618
619
		list->end   = block;
	}
	else {
620
621
622
623
624
625
626
627
		set_irn_link(list->end, block);
		list->end = block;
	}

	list->n_blks++;
}

static void create_block_list(ir_node *leader_block, anchor *list) {
628
	int             i;
629
	const ir_edge_t *edge;
630
631
	ir_node         *block = NULL;
	ir_extblk       *extbb = get_Block_extbb(leader_block);
632

633
	if (extbb_visited(extbb))
634
635
636
		return;
	mark_extbb_visited(extbb);

637
	for (i = 0; i < get_extbb_n_blocks(extbb); ++i) {
638
639
640
641
642
643
		block = get_extbb_block(extbb, i);
		add_block(list, block);
	}

	assert(block != NULL);

644
	/* pick successor extbbs */
645
646
647
648
649
	foreach_block_succ(block, edge) {
		ir_node *succ = get_edge_src_irn(edge);
		create_block_list(succ, list);
	}

650
	for (i = 0; i < get_extbb_n_blocks(extbb) - 1; ++i) {
651
		block = get_extbb_block(extbb, i);
652

653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
		foreach_block_succ(block, edge) {
			ir_node *succ = get_edge_src_irn(edge);
			create_block_list(succ, list);
		}
	}
}

void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs);

/*
 * Calculates a block schedule. The schedule is stored as a linked
 * list starting at the start_block of the irg.
 */
static ir_node **create_extbb_block_schedule(ir_graph *irg, ir_exec_freq *execfreqs)
{
	anchor list;
	ir_node **blk_list, *b, *n;
	unsigned i;

	/* schedule extended basic blocks */
	compute_extbb_execfreqs(irg, execfreqs);
	//compute_extbb(irg);

	list.start  = NULL;
	list.end    = NULL;
	list.n_blks = 0;
	inc_irg_block_visited(irg);
	create_block_list(get_irg_start_block(irg), &list);

	/** create an array, so we can go forward and backward */
	blk_list = NEW_ARR_D(ir_node *, irg->obst,list.n_blks);

	for (i = 0, b = list.start; b; b = n, ++i) {
		n = get_irn_link(b);
		blk_list[i] = b;
	}

	return blk_list;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
701
void be_init_blocksched(void)
702
{
703
704
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_entry_t *blocksched_grp = lc_opt_get_grp(be_grp, "blocksched");
705
706
707

	lc_opt_add_table(blocksched_grp, be_blocksched_options);
}
708
709

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched);
710
711
712
713
714
715
716
717
718
719
720
721

ir_node **be_create_block_schedule(ir_graph *irg, ir_exec_freq *execfreqs)
{
	switch(algo) {
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
		return create_block_schedule_greedy(irg, execfreqs);
	case BLOCKSCHED_EXTBB:
		return create_extbb_block_schedule(irg, execfreqs);
#ifdef WITH_ILP
	case BLOCKSCHED_ILP:
		return create_block_schedule_ilp(irg, execfreqs);
Christian Würdig's avatar
Christian Würdig committed
722
#endif /* WITH_ILP */
723
724
725
726
727
	}

	assert(0 && "unknown blocksched algo");
	return NULL;
}