beblocksched.c 20 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Christian Würdig's avatar
Christian Würdig committed
20
21
22
23
24
/**
 * @file
 * @brief       Block-scheduling strategies.
 * @author      Matthias Braun, Christoph Mallon
 * @date        27.09.2006
25
26
27
28
29
30
31
32
33
34
 *
 * The goals of the greedy (and ILP) algorithm here works by assuming that
 * we want to change as many jumps to fallthroughs as possible (executed jumps
 * actually, we have to look at the execution frequencies). The algorithms
 * do this by collecting execution frequencies of all branches (which is easily
 * possible when all critical edges are split) then removes critical edges where
 * possible as we don't need and want them anymore now. The algorithms then try
 * to change as many edges to fallthroughs as possible, this is done by setting
 * a next and prev pointers on blocks. The greedy algorithm sorts the edges by
 * execution frequencies and tries to transform them to fallthroughs in this order
35
 */
36
#include "config.h"
37
38
39
40
41
42
43
44
45
46

#include "beblocksched.h"

#include <stdlib.h>

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

#include "iredges.h"
#include "irgwalk.h"
Michael Beck's avatar
Michael Beck committed
47
#include "irnode_t.h"
48
49
50
#include "irgraph_t.h"
#include "irloop.h"
#include "irprintf.h"
Michael Beck's avatar
Michael Beck committed
51
#include "execfreq.h"
52
#include "irdump_t.h"
53
#include "irtools.h"
54
#include "util.h"
55
#include "debug.h"
56
#include "beirgmod.h"
57
58
#include "bemodule.h"
#include "be.h"
59
#include "error.h"
60

Matthias Braun's avatar
Matthias Braun committed
61
62
#include "lc_opts.h"
#include "lc_opts_enum.h"
63

64
65
#include "lpp.h"
#include "lpp_net.h"
66

Matthias Braun's avatar
Matthias Braun committed
67
68
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

69
typedef enum blocksched_algos_t {
70
	BLOCKSCHED_NAIV, BLOCKSCHED_GREEDY, BLOCKSCHED_ILP
71
72
73
74
75
} blocksched_algos_t;

static int algo = BLOCKSCHED_GREEDY;

static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
76
	{ "naiv",   BLOCKSCHED_NAIV },
77
78
79
80
81
82
83
84
85
86
	{ "greedy", BLOCKSCHED_GREEDY },
	{ "ilp",    BLOCKSCHED_ILP },
	{ NULL,     0 }
};

static lc_opt_enum_int_var_t algo_var = {
	&algo, blockschedalgo_items
};

static const lc_opt_table_entry_t be_blocksched_options[] = {
87
	LC_OPT_ENT_ENUM_INT ("blockscheduler", "the block scheduling algorithm", &algo_var),
88
	LC_OPT_LAST
89
90
91
92
93
94
95
96
97
98
99
};

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

100
101
102
103
104
105
typedef struct blocksched_entry_t blocksched_entry_t;
struct blocksched_entry_t {
	ir_node            *block;
	blocksched_entry_t *next;
	blocksched_entry_t *prev;
};
106

107
108
typedef struct edge_t edge_t;
struct edge_t {
109
110
111
	ir_node *block;             /**< source block */
	int     pos;                /**< number of cfg predecessor (target) */
	double  execfreq;           /**< the frequency */
112
113
114
115
116
117
118
	double  outedge_penalty_freq; /**< for edges leaving the loop this is the
	                                   penality when we make them a
	                                   fallthrough. */
	int     highest_execfreq;   /**< flag that indicates whether this edge is
	                                 the edge with the highest execfreq pointing
	                                 away from this block */
};
119

120
121
typedef struct blocksched_env_t blocksched_env_t;
struct blocksched_env_t {
122
	ir_graph       *irg;
123
	struct obstack *obst;
124
125
126
127
	ir_exec_freq   *execfreqs;
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
128
};
129

130
131
132
133
/**
 * Collect cfg frequencies of all edges between blocks.
 * Also determines edge with highest frequency.
 */
134
135
static void collect_egde_frequency(ir_node *block, void *data)
{
136
	blocksched_env_t   *env = (blocksched_env_t*)data;
137
138
	int                arity;
	edge_t             edge;
139
	blocksched_entry_t *entry;
140
	ir_loop            *loop;
141

142
143
	memset(&edge, 0, sizeof(edge));

144
	entry = OALLOCZ(env->obst, blocksched_entry_t);
145
146
147
	entry->block = block;
	set_irn_link(block, entry);

148
149
	loop = get_irn_loop(block);

150
	arity = get_Block_n_cfgpreds(block);
151

152
	if (arity == 0) {
153
154
		/* must be the start block (or end-block for endless loops),
		 * everything else is dead code and should be removed by now */
155
156
		assert(block == get_irg_start_block(env->irg)
				|| block == get_irg_end_block(env->irg));
157
		/* nothing to do here */
158
159
		return;
	} else if (arity == 1) {
160
161
		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
		ir_loop *pred_loop  = get_irn_loop(pred_block);
162
		float    freq       = (float)get_block_execfreq(env->execfreqs, block);
163
164
165

		/* is it an edge leaving a loop */
		if (get_loop_depth(pred_loop) > get_loop_depth(loop)) {
166
			float pred_freq = (float)get_block_execfreq(env->execfreqs, pred_block);
167
168
169
			edge.outedge_penalty_freq = -(pred_freq - freq);
		}

170
171
		edge.block            = block;
		edge.pos              = 0;
172
		edge.execfreq         = freq;
173
174
175
		edge.highest_execfreq = 1;
		ARR_APP1(edge_t, env->edges, edge);
	} else {
176
		int    i;
177
		double highest_execfreq = -1.0;
178
		int    highest_edge_num = -1;
179
180

		edge.block = block;
181
182
		for (i = 0; i < arity; ++i) {
			double  execfreq;
183
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
184

185
186
			execfreq = get_block_execfreq(env->execfreqs, pred_block);

187
188
			edge.pos              = i;
			edge.execfreq         = execfreq;
189
190
			edge.highest_execfreq = 0;
			ARR_APP1(edge_t, env->edges, edge);
191
192

			if (execfreq > highest_execfreq) {
193
194
195
196
197
				highest_execfreq = execfreq;
				highest_edge_num = ARR_LEN(env->edges) - 1;
			}
		}

198
		if (highest_edge_num >= 0)
199
			env->edges[highest_edge_num].highest_execfreq = 1;
200
201
202
203
204
	}
}

static int cmp_edges(const void *d1, const void *d2)
{
205
206
	const edge_t *e1 = (const edge_t*)d1;
	const edge_t *e2 = (const edge_t*)d2;
207
208

	return QSORT_CMP(e2->execfreq, e1->execfreq);
209
210
}

211
212
static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
{
213
214
	const edge_t *e1 = (const edge_t*)d1;
	const edge_t *e2 = (const edge_t*)d2;
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
	/* reverse sorting as penalties are negative */
	return QSORT_CMP(e1->outedge_penalty_freq, e2->outedge_penalty_freq);
}

static void clear_loop_links(ir_loop *loop)
{
	int i, n;

	set_loop_link(loop, NULL);
	n = get_loop_n_elements(loop);
	for (i = 0; i < n; ++i) {
		loop_element elem = get_loop_element(loop, i);
		if (*elem.kind == k_ir_loop) {
			clear_loop_links(elem.son);
		}
	}
}

233
234
235
236
static void coalesce_blocks(blocksched_env_t *env)
{
	int i;
	int edge_count = ARR_LEN(env->edges);
237
238
239
240
	edge_t *edges = env->edges;

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

242
243
	/* run1: only look at jumps */
	for (i = 0; i < edge_count; ++i) {
244
		const edge_t *edge  = &edges[i];
245
		ir_node      *block = edge->block;
246
		int           pos   = edge->pos;
247
		ir_node      *pred_block;
248
249
		blocksched_entry_t *entry, *pred_entry;

250
251
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
252
253
			continue;

254
255
256
257
258
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
259
260
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
261

262
		if (pred_entry->next != NULL || entry->prev != NULL)
263
			continue;
264
265
266

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

269
		/* schedule the 2 blocks behind each other */
270
		DB((dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n",
271
		           pred_entry->block, entry->block, edge->execfreq));
272
		pred_entry->next = entry;
273
		entry->prev      = pred_entry;
274
275
	}

276
277
278
279
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

	qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_edges_outedge_penalty);
280
	for (i = 0; i < edge_count; ++i) {
281
		const edge_t *edge  = &edges[i];
282
		ir_node      *block = edge->block;
283
		int           pos   = edge->pos;
284
		ir_node      *pred_block;
285
		blocksched_entry_t *entry, *pred_entry;
286
287
288
289
290
291
		ir_loop      *loop;
		ir_loop      *outer_loop;

		/* already seen all loop outedges? */
		if (edge->outedge_penalty_freq == 0)
			break;
292

293
		/* the block might have been removed already... */
294
		if (is_Bad(get_Block_cfgpred(block, pos)))
295
296
			continue;

297
		pred_block = get_Block_cfgpred_block(block, pos);
298
299
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336

		if (pred_entry->next != NULL || entry->prev != NULL)
			continue;

		/* we want at most 1 outedge fallthrough per loop */
		loop = get_irn_loop(pred_block);
		if (get_loop_link(loop) != NULL)
			continue;

		/* schedule the 2 blocks behind each other */
		DB((dbg, LEVEL_1, "Coalesce (Loop Outedge) %+F -> %+F (%.3g)\n",
		           pred_entry->block, entry->block, edge->execfreq));
		pred_entry->next = entry;
		entry->prev      = pred_entry;

		/* all loops left have an outedge now */
		outer_loop = get_irn_loop(block);
		do {
			/* we set loop link to loop to mark it */
			set_loop_link(loop, loop);
			loop = get_loop_outer_loop(loop);
		} while (loop != outer_loop);
	}

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

	/* run3: remaining edges */
	for (i = 0; i < edge_count; ++i) {
		const edge_t *edge  = &edges[i];
		ir_node      *block = edge->block;
		int           pos   = edge->pos;
		ir_node      *pred_block;
		blocksched_entry_t *entry, *pred_entry;

		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, pos)))
337
338
339
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
340
341
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
342

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

347
		/* schedule the 2 blocks behind each other */
348
		DB((dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n",
349
		           pred_entry->block, entry->block, edge->execfreq));
350
		pred_entry->next = entry;
351
		entry->prev      = pred_entry;
352
353
354
355
356
	}
}

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
357
358
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
359
	blocksched_entry_t *succ_entry;
360
361
	const ir_edge_t    *edge;
	double             best_succ_execfreq;
362

363
	if (irn_visited_else_mark(block))
364
		return;
365

366
367
	env->blockcount++;

368
	DB((dbg, LEVEL_1, "Pick succ of %+F\n", block));
369

370
	/* put all successors into the worklist */
371
372
373
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

374
		if (irn_visited(succ_block))
375
376
			continue;

377
378
		/* we only need to put the first of a series of already connected
		 * blocks into the worklist */
379
		succ_entry = (blocksched_entry_t*)get_irn_link(succ_block);
380
381
382
		while (succ_entry->prev != NULL) {
			/* break cycles... */
			if (succ_entry->prev->block == succ_block) {
383
				succ_entry->prev->next = NULL;
384
				succ_entry->prev       = NULL;
385
386
387
				break;
			}
			succ_entry = succ_entry->prev;
388
		}
389

390
		if (irn_visited(succ_entry->block))
391
392
			continue;

393
		DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
394
395
396
		pdeq_putr(env->worklist, succ_entry->block);
	}

397
	if (entry->next != NULL) {
398
399
400
401
		pick_block_successor(entry->next, env);
		return;
	}

402
	DB((dbg, LEVEL_1, "deciding...\n"));
403
	best_succ_execfreq = -1;
404

405
	/* no successor yet: pick the successor block with the highest execution
406
407
	 * frequency which has no predecessor yet */

408
409
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);
410
		double  execfreq;
411

412
		if (irn_visited(succ_block))
413
414
			continue;

415
		succ_entry = (blocksched_entry_t*)get_irn_link(succ_block);
416
		if (succ_entry->prev != NULL)
417
418
			continue;

Michael Beck's avatar
Michael Beck committed
419
		execfreq = get_block_execfreq(env->execfreqs, succ_block);
420
		if (execfreq > best_succ_execfreq) {
421
422
423
424
425
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

426
	if (succ == NULL) {
427
		DB((dbg, LEVEL_1, "pick from worklist\n"));
428
429

		do {
430
			if (pdeq_empty(env->worklist)) {
431
				DB((dbg, LEVEL_1, "worklist empty\n"));
432
433
				return;
			}
434
			succ = (ir_node*)pdeq_getl(env->worklist);
435
		} while (irn_visited(succ));
436
437
	}

438
	succ_entry       = (blocksched_entry_t*)get_irn_link(succ);
439
	entry->next      = succ_entry;
440
441
442
443
444
445
446
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
447
448
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
449
	blocksched_entry_t *entry      = (blocksched_entry_t*)get_irn_link(startblock);
450

451
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
452
453
454
455
456
457
458
	inc_irg_visited(irg);

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

459
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
460

461
462
463
	return entry;
}

464
465
466
467
468
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;
469
	blocksched_entry_t *entry;
470
	(void) env;
471
472

	block_list = NEW_ARR_D(ir_node *, obst, count);
473
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
474
475

	for (entry = first; entry != NULL; entry = entry->next) {
476
477
		assert(i < count);
		block_list[i++] = entry->block;
478
		DB((dbg, LEVEL_1, "\t%+F\n", entry->block));
479
480
481
482
483
484
485
486
	}
	assert(i == count);

	return block_list;
}

static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execfreqs)
{
487
488
	blocksched_env_t   env;
	struct obstack     obst;
489
	blocksched_entry_t *start_entry;
490
	ir_node            **block_list;
491
492
493

	obstack_init(&obst);

494
495
496
497
498
	env.irg        = irg;
	env.obst       = &obst;
	env.execfreqs  = execfreqs;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
499
500
	env.blockcount = 0;

501
	assure_loopinfo(irg);
502

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

506
	(void)be_remove_empty_blocks(irg);
507

508
	if (algo != BLOCKSCHED_NAIV)
509
510
511
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
512
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount,
513
	                                      be_get_be_obst(irg));
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529

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

	return block_list;
}

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

530
typedef struct ilp_edge_t {
531
532
533
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
534
535
} ilp_edge_t;

536
typedef struct blocksched_ilp_env_t {
537
	blocksched_env_t env;
538
539
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
540
541
} blocksched_ilp_env_t;

542
typedef struct blocksched_ilp_entry_t {
543
	ir_node *block;
544
545
	struct blocksched_entry_t *next;
	struct blocksched_entry_t *prev;
546
547
548
549
550
551

	int out_cst;
} blocksched_ilp_entry_t;

static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
{
552
	char       name[64];
553
	ilp_edge_t edge;
554
	int        edgeidx = ARR_LEN(env->ilpedges);
555
556
557

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

558
559
	edge.block  = block;
	edge.pos    = pos;
560
561
562
563
564
565
566
567
	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)
{
568
569
570
571
572
573
574
	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;
575
576
577
578
579
	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);

580
	entry          = OALLOC(env->env.obst, blocksched_ilp_entry_t);
581
582
583
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
584
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, out_count - 1);
585
586
	set_irn_link(block, entry);

587
	if (block == startblock)
588
589
590
		return;

	arity = get_irn_arity(block);
591
	if (arity == 1) {
592
593
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
594
595
	}
	else {
596
597
598
		int i;

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

601
602
603
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
604
			ilp_edge_t *edge;
605
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
606
607

			execfreq = get_block_execfreq(env->env.execfreqs, pred_block);
608
609
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
610
611
612
613
614
615
616
617
			lpp_set_factor_fast(env->lpp, cst, edge->ilpvar, 1.0);
		}
	}
}


static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
Matthias Braun's avatar
Matthias Braun committed
618
619
	int           edge_count = ARR_LEN(env->ilpedges);
	int           i;
620
621

	/* complete out constraints */
622
	for (i = 0; i < edge_count; ++i) {
623
624
625
		const ilp_edge_t *edge  = &env->ilpedges[i];
		ir_node          *block = edge->block;
		ir_node          *pred;
626
627
		blocksched_ilp_entry_t *entry;

628
629
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
630
631
			continue;

632
		pred  = get_Block_cfgpred_block(block, edge->pos);
633
634
		entry = get_irn_link(pred);

635
		DB((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
636
				  pred, block, edge->pos));
637
638
639
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

640
	lpp_solve_net(env->lpp, be_options.ilp_server, be_options.ilp_solver);
641
642
643
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
644
645
646
647
648
	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;
649
650
651
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

652
653
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
654
655
			continue;

656
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
657
		if (is_jump)
658
659
			continue;

660
661
		pred       = get_Block_cfgpred_block(block, edge->pos);
		entry      = get_irn_link(block);
662
663
664
		pred_entry = get_irn_link(pred);

		assert(entry->prev == NULL && pred_entry->next == NULL);
665
		entry->prev      = pred_entry;
666
667
668
669
670
671
672
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
673
674
675
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
676
677
678

	obstack_init(&obst);

679
680
681
682
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.execfreqs  = execfreqs;
	env.env.worklist   = NULL;
683
	env.env.blockcount = 0;
684
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
685

686
	env.lpp = lpp_new("blockschedule", lpp_minimize);
687
688
689
690
691
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

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

692
	(void)be_remove_empty_blocks(irg);
693
694
695
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
696
697
	block_list  = create_blocksched_array(&env.env, start_entry,
	                                      env.env.blockcount,
698
	                                      be_get_be_obst(irg));
699
700

	DEL_ARR_F(env.ilpedges);
701
	lpp_free(env.lpp);
702
703
704
705
706
707
708
709
710
711
712
713
714
	obstack_free(&obst, NULL);

	return block_list;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
Matthias Braun's avatar
Matthias Braun committed
715
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
716
void be_init_blocksched(void)
717
{
718
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
719

720
	lc_opt_add_table(be_grp, be_blocksched_options);
721

Matthias Braun's avatar
Matthias Braun committed
722
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
723
}
724

725
ir_node **be_create_block_schedule(ir_graph *irg)
726
{
727
	ir_exec_freq *execfreqs = be_get_irg_exec_freq(irg);
728

729
	switch (algo) {
730
731
732
733
734
735
736
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
		return create_block_schedule_greedy(irg, execfreqs);
	case BLOCKSCHED_ILP:
		return create_block_schedule_ilp(irg, execfreqs);
	}

737
	panic("unknown blocksched algo");
738
}