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

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
46
#ifdef WITH_LIBCORE
47
48
49
50
51
52
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
53
#endif /* WITH_ILP */
54
55
56
57
58
59
60
61
	{ 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
62
	LC_OPT_ENT_ENUM_INT ("algo", "the block scheduling algorithm", &algo_var),
63
64
	{ NULL }
};
Matthias Braun's avatar
Matthias Braun committed
65
#endif
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

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

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

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

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

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

119
	if (block == startblock)
120
121
122
		return;

	arity = get_irn_arity(block);
123
124
125
126
127

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

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

140
141
			execfreq = get_block_execfreq(env->execfreqs, pred_block);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

239
	if (irn_visited(block))
240
		return;
241

242
243
244
	env->blockcount++;
	mark_irn_visited(block);

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

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

251
		if (irn_visited(succ_block))
252
253
			continue;

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

267
		if (irn_visited(succ_entry->block))
268
269
			continue;

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

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

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

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

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

289
		if (irn_visited(succ_block))
290
291
292
			continue;

		succ_entry = get_irn_link(succ_block);
293
		if (succ_entry->prev != NULL)
294
295
			continue;

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

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

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

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

	pick_block_successor(succ_entry, env);
}

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

	inc_irg_visited(irg);

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

	return entry;
}

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

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

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

	return block_list;
}

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

	obstack_init(&obst);

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

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

383
	if (algo != BLOCKSCHED_NAIV)
384
385
386
		coalesce_blocks(&env);

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

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

	return block_list;
}

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

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

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

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

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

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

462
	if (block == startblock)
463
464
465
		return;

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

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

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


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

	/* 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
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

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

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

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

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

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

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

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

	obstack_init(&obst);

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

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

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

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

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

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

	list->n_blks++;
}

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

631
	if (extbb_visited(extbb))
632
633
634
		return;
	mark_extbb_visited(extbb);

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

	assert(block != NULL);

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

648
	for (i = 0; i < get_extbb_n_blocks(extbb) - 1; ++i) {
649
		block = get_extbb_block(extbb, i);
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
701
702
		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)
{
703
	static int     run_once = 0;
704
705
	lc_opt_entry_t *blocksched_grp;

706
	if (run_once)
707
		return;
708
709

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

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

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