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

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

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

506
		pred  = get_Block_cfgpred_block(block, edge->pos);
507
508
		entry = get_irn_link(pred);

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

514
515
516
517
518
519
520
521
522
523
524
525
#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

526
527
528
529
530
	//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 */
531
532
533
534
535
	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;
536
537
538
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

539
540
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
541
542
543
			continue;

		is_jump = lpp_get_var_sol(env->lpp, edge->ilpvar);
544
		if (is_jump)
545
546
			continue;

547
548
		pred       = get_Block_cfgpred_block(block, edge->pos);
		entry      = get_irn_link(block);
549
550
551
		pred_entry = get_irn_link(pred);

		assert(entry->prev == NULL && pred_entry->next == NULL);
552
		entry->prev      = pred_entry;
553
554
555
556
557
558
559
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
560
561
562
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
563
564
565

	obstack_init(&obst);

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

	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);
584
	block_list  = create_blocksched_array(&env.env, start_entry, env.env.blockcount, get_irg_obstack(irg));
585
586
587
588
589
590
591

	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
592
#endif /* WITH_ILP */
593
594
595
596
597
598
599
600
601
602
603
604

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

/** A simple forward single linked list. */
typedef struct {
605
606
	ir_node  *start;   /**< start of the list */
	ir_node  *end;     /**< last block in the list */
607
608
609
610
	unsigned n_blks;  /**< number of blocks in the list */
} anchor;

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

	list->n_blks++;
}

static void create_block_list(ir_node *leader_block, anchor *list) {
624
	int             i;
625
	const ir_edge_t *edge;
626
627
	ir_node         *block = NULL;
	ir_extblk       *extbb = get_Block_extbb(leader_block);
628

629
	if (extbb_visited(extbb))
630
631
632
		return;
	mark_extbb_visited(extbb);

633
	for (i = 0; i < get_extbb_n_blocks(extbb); ++i) {
634
635
636
637
638
639
		block = get_extbb_block(extbb, i);
		add_block(list, block);
	}

	assert(block != NULL);

640
	/* pick successor extbbs */
641
642
643
644
645
	foreach_block_succ(block, edge) {
		ir_node *succ = get_edge_src_irn(edge);
		create_block_list(succ, list);
	}

646
	for (i = 0; i < get_extbb_n_blocks(extbb) - 1; ++i) {
647
		block = get_extbb_block(extbb, i);
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
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;
}

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

#ifdef WITH_LIBCORE
void be_block_schedule_register_options(lc_opt_entry_t *grp)
{
701
	static int     run_once = 0;
702
703
	lc_opt_entry_t *blocksched_grp;

704
	if (run_once)
705
		return;
706
707

	run_once       = 1;
708
709
710
711
	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
712
#endif /* WITH_LIBCORE */
713
714
715
716
717
718
719
720
721
722
723
724

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
725
#endif /* WITH_ILP */
726
727
728
729
730
	}

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