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
28
29
30
31
32
#include "beirgmod.h"

#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
33
#endif /* WITH_LIBCORE */
34
35
36
37

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

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

static int algo = BLOCKSCHED_GREEDY;

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
52
#endif /* WITH_ILP */
53
54
55
56
57
58
59
60
	{ 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
61
	LC_OPT_ENT_ENUM_INT ("algo", "the block scheduling algorithm", &algo_var),
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
	{ NULL }
};

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

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 {
81
82
83
84
	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
85
86
87
88
							   	     execfreq pointing away from this block */
} edge_t;

typedef struct _blocksched_env_t {
89
	ir_graph       *irg;
90
	struct obstack *obst;
91
92
93
94
95
	ir_exec_freq   *execfreqs;
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
96
97
} blocksched_env_t;

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

111
	entry        = obstack_alloc(env->obst, sizeof(entry[0]));
112
	entry->block = block;
113
114
	entry->next  = NULL;
	entry->prev  = NULL;
115
116
	set_irn_link(block, entry);

117
	if (block == startblock)
118
119
120
		return;

	arity = get_irn_arity(block);
121
122
123
124
125

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

		edge.block = block;
134
135
		for (i = 0; i < arity; ++i) {
			double  execfreq;
136
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
137

138
139
			execfreq = get_block_execfreq(env->execfreqs, pred_block);

140
141
			edge.pos              = i;
			edge.execfreq         = execfreq;
142
143
			edge.highest_execfreq = 0;
			ARR_APP1(edge_t, env->edges, edge);
144
145

			if (execfreq > highest_execfreq) {
146
147
148
149
150
				highest_execfreq = execfreq;
				highest_edge_num = ARR_LEN(env->edges) - 1;
			}
		}

151
152
		if(highest_edge_num >= 0)
			env->edges[highest_edge_num].highest_execfreq = 1;
153
154
155
156
157
158
159
	}
}

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

	return QSORT_CMP(e2->execfreq, e1->execfreq);
162
163
164
165
166
167
168
}

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

169
170
171
172
173
	/* 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;
174
175
		blocksched_entry_t *entry, *pred_entry;

176
177
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
178
179
			continue;

180
181
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
182
183
184
			continue;

		pred_block = get_Block_cfgpred_block(block, edge->pos);
185
		entry      = get_irn_link(block);
186
187
		pred_entry = get_irn_link(pred_block);

188
		if (pred_entry->next != NULL || entry->prev != NULL)
189
			continue;
190
191
192

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

195
196
197
		/* 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));
198
		pred_entry->next = entry;
199
		entry->prev      = pred_entry;
200
201
	}

202
203
204
205
206
	/* 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;
207
208
		blocksched_entry_t *entry, *pred_entry;

209
210
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
211
212
213
			continue;

		pred_block = get_Block_cfgpred_block(block, edge->pos);
214
		entry      = get_irn_link(block);
215
216
		pred_entry = get_irn_link(pred_block);

217
218
		/* TODO: what's this check for? */
		if (pred_entry->next != NULL || entry->prev != NULL)
219
220
			continue;

221
222
223
		/* 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));
224
		pred_entry->next = entry;
225
		entry->prev      = pred_entry;
226
227
228
229
230
	}
}

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
231
232
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
233
	blocksched_entry_t *succ_entry;
234
235
	const ir_edge_t    *edge;
	double             best_succ_execfreq;
236

237
	if (irn_visited(block))
238
		return;
239

240
241
242
	env->blockcount++;
	mark_irn_visited(block);

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

245
	/* put all successors into the worklist */
246
247
248
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

249
		if (irn_visited(succ_block))
250
251
			continue;

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

265
		if (irn_visited(succ_entry->block))
266
267
			continue;

268
		DBG((env->dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
269
270
271
		pdeq_putr(env->worklist, succ_entry->block);
	}

272
	if (entry->next != NULL) {
273
274
275
276
		pick_block_successor(entry->next, env);
		return;
	}

277
	DBG((env->dbg, LEVEL_1, "deciding...\n"));
278
	best_succ_execfreq = -1;
279

280
	/* no successor yet: pick the successor block with the highest execution
281
282
	 * frequency which has no predecessor yet */

283
284
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);
285
		double  execfreq;
286

287
		if (irn_visited(succ_block))
288
289
290
			continue;

		succ_entry = get_irn_link(succ_block);
291
		if (succ_entry->prev != NULL)
292
293
			continue;

Michael Beck's avatar
Michael Beck committed
294
		execfreq = get_block_execfreq(env->execfreqs, succ_block);
295
		if (execfreq > best_succ_execfreq) {
296
297
298
299
300
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

301
302
	if (succ == NULL) {
		DBG((env->dbg, LEVEL_1, "pick from worklist\n"));
303
304

		do {
305
306
			if (pdeq_empty(env->worklist)) {
				DBG((env->dbg, LEVEL_1, "worklist empty\n"));
307
308
309
				return;
			}
			succ = pdeq_getl(env->worklist);
310
		} while (irn_visited(succ));
311
312
	}

313
314
	succ_entry       = get_irn_link(succ);
	entry->next      = succ_entry;
315
316
317
318
319
320
321
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
322
323
324
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
	blocksched_entry_t *entry      = get_irn_link(startblock);
325
326
327
328
329
330
331
332
333
334
335

	inc_irg_visited(irg);

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

	return entry;
}

336
337
338
339
340
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;
341
342
343
	blocksched_entry_t *entry;

	block_list = NEW_ARR_D(ir_node *, obst, count);
344
345
346
	DBG((env->dbg, LEVEL_1, "Blockschedule:\n"));

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

	return block_list;
}

static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execfreqs)
{
358
359
	blocksched_env_t   env;
	struct obstack     obst;
360
	blocksched_entry_t *start_entry;
361
	ir_node            **block_list;
362
363
364

	obstack_init(&obst);

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

	// 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);

381
	if (algo != BLOCKSCHED_NAIV)
382
383
384
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
385
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount, get_irg_obstack(irg));
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403

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

	return block_list;
}

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

#ifdef WITH_ILP
typedef struct _ilp_edge_t {
404
405
406
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
407
408
409
410
} ilp_edge_t;

typedef struct _blocksched_ilp_env_t {
	blocksched_env_t env;
411
412
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
413
414
415
416
417
418
419
420
421
422
423
424
} 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)
{
425
	char       name[64];
426
	ilp_edge_t edge;
427
	int        edgeidx = ARR_LEN(env->ilpedges);
428
429
430

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

431
432
	edge.block  = block;
	edge.pos    = pos;
433
434
435
436
437
438
439
440
	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)
{
441
442
443
444
445
446
447
	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;
448
449
450
451
452
	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);

453
454
455
456
	entry          = obstack_alloc(env->env.obst, sizeof(entry[0]));
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
457
458
459
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, out_count - 1);
	set_irn_link(block, entry);

460
	if (block == startblock)
461
462
463
		return;

	arity = get_irn_arity(block);
464
	if (arity == 1) {
465
466
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
467
468
	}
	else {
469
470
471
472
473
474
		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);

475
476
477
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
478
			ilp_edge_t *edge;
479
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
480
481

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


static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
492
493
	int  i;
	int  edge_count = ARR_LEN(env->ilpedges);
494
495
496
497
498
	FILE *f;
	char fname[256];

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

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

508
		pred  = get_Block_cfgpred_block(block, edge->pos);
509
510
		entry = get_irn_link(pred);

511
512
		DBG((env->env.dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
				  pred, block, edge->pos));
513
514
515
516
517
518
519
520
521
522
523
524
525
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

	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);
	//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 */
526
527
528
529
530
	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;
531
532
533
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

534
535
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
536
537
538
			continue;

		is_jump = lpp_get_var_sol(env->lpp, edge->ilpvar);
539
		if (is_jump)
540
541
			continue;

542
543
		pred       = get_Block_cfgpred_block(block, edge->pos);
		entry      = get_irn_link(block);
544
545
546
		pred_entry = get_irn_link(pred);

		assert(entry->prev == NULL && pred_entry->next == NULL);
547
		entry->prev      = pred_entry;
548
549
550
551
552
553
554
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
555
556
557
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
558
559
560

	obstack_init(&obst);

561
562
563
564
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.execfreqs  = execfreqs;
	env.env.worklist   = NULL;
565
	env.env.blockcount = 0;
566
567
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
	FIRM_DBG_REGISTER(env.env.dbg, "firm.be.blocksched");
568
569
570
571
572
573
574
575
576
577
578

	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);
579
	block_list  = create_blocksched_array(&env.env, start_entry, env.env.blockcount, get_irg_obstack(irg));
580
581
582
583
584
585
586

	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
587
#endif /* WITH_ILP */
588
589
590
591
592
593
594
595
596
597
598
599

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

/** A simple forward single linked list. */
typedef struct {
600
601
	ir_node  *start;   /**< start of the list */
	ir_node  *end;     /**< last block in the list */
602
603
604
605
	unsigned n_blks;  /**< number of blocks in the list */
} anchor;

static void add_block(anchor *list, ir_node *block) {
606
	if (list->start == NULL) {
607
		list->start = block;
608
609
610
		list->end   = block;
	}
	else {
611
612
613
614
615
616
617
618
		set_irn_link(list->end, block);
		list->end = block;
	}

	list->n_blks++;
}

static void create_block_list(ir_node *leader_block, anchor *list) {
619
	int             i;
620
	const ir_edge_t *edge;
621
622
	ir_node         *block = NULL;
	ir_extblk       *extbb = get_Block_extbb(leader_block);
623

624
	if (extbb_visited(extbb))
625
626
627
		return;
	mark_extbb_visited(extbb);

628
	for (i = 0; i < get_extbb_n_blocks(extbb); ++i) {
629
630
631
632
633
634
		block = get_extbb_block(extbb, i);
		add_block(list, block);
	}

	assert(block != NULL);

635
	/* pick successor extbbs */
636
637
638
639
640
	foreach_block_succ(block, edge) {
		ir_node *succ = get_edge_src_irn(edge);
		create_block_list(succ, list);
	}

641
	for (i = 0; i < get_extbb_n_blocks(extbb) - 1; ++i) {
642
		block = get_extbb_block(extbb, i);
643

644
645
646
647
648
649
650
651
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
		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;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */

#ifdef WITH_LIBCORE
void be_block_schedule_register_options(lc_opt_entry_t *grp)
{
696
	static int     run_once = 0;
697
698
	lc_opt_entry_t *blocksched_grp;

699
	if (run_once)
700
		return;
701
702

	run_once       = 1;
703
704
705
706
	blocksched_grp = lc_opt_get_grp(grp, "blocksched");

	lc_opt_add_table(blocksched_grp, be_blocksched_options);
}
Christian Würdig's avatar
Christian Würdig committed
707
#endif /* WITH_LIBCORE */
708
709
710
711
712
713
714
715
716
717
718
719

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
720
#endif /* WITH_ILP */
721
722
723
724
725
	}

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