beblocksched.c 18.1 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
35
36
37

#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#include <libcore/lc_timing.h>

#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
	blocksched_env_t   *env = data;
105
106
	int                arity;
	edge_t             edge;
107
108
	blocksched_entry_t *entry;

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

115
	if (block == get_irg_start_block(env->irg))
116
117
118
		return;

	arity = get_irn_arity(block);
119
120
121
122
123

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

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

136
137
			execfreq = get_block_execfreq(env->execfreqs, pred_block);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

235
	if (irn_visited(block))
236
		return;
237

238
239
240
	env->blockcount++;
	mark_irn_visited(block);

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

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

247
		if (irn_visited(succ_block))
248
249
			continue;

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

263
		if (irn_visited(succ_entry->block))
264
265
			continue;

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

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

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

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

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

285
		if (irn_visited(succ_block))
286
287
288
			continue;

		succ_entry = get_irn_link(succ_block);
289
		if (succ_entry->prev != NULL)
290
291
			continue;

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

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

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

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

	pick_block_successor(succ_entry, env);
}

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

	inc_irg_visited(irg);

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

	return entry;
}

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

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

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

	return block_list;
}

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

	obstack_init(&obst);

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

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

377
	(void)be_remove_empty_blocks(irg);
378

379
	if (algo != BLOCKSCHED_NAIV)
380
381
382
		coalesce_blocks(&env);

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

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

	return block_list;
}

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

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

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

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

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

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

458
	if (block == startblock)
459
460
461
		return;

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

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

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


static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
490
491
	int  i;
	int  edge_count = ARR_LEN(env->ilpedges);
492
493
494

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

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

504
		pred  = get_Block_cfgpred_block(block, edge->pos);
505
506
		entry = get_irn_link(pred);

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

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

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

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

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

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

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

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

	obstack_init(&obst);

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

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

578
	(void)be_remove_empty_blocks(irg);
579
580
581
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
582
	block_list  = create_blocksched_array(&env.env, start_entry, env.env.blockcount, get_irg_obstack(irg));
583
584
585
586
587
588
589

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

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

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

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

	list->n_blks++;
}

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

627
	if (extbb_visited(extbb))
628
629
630
		return;
	mark_extbb_visited(extbb);

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

	assert(block != NULL);

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

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

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
695
void be_init_blocksched(void)
696
{
697
698
	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");
699
700
701

	lc_opt_add_table(blocksched_grp, be_blocksched_options);
}
702
703

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched);
704
705
706
707
708
709
710
711
712
713
714
715

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
716
#endif /* WITH_ILP */
717
718
719
720
721
	}

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