beblocksched.c 20.1 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
25
/**
 * @file
 * @brief       Block-scheduling strategies.
 * @author      Matthias Braun, Christoph Mallon
 * @date        27.09.2006
 * @version     $Id$
26
27
28
29
30
31
32
33
34
35
 *
 * 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
36
 */
37
#include "config.h"
38
39
40
41
42
43
44
45
46
47

#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
48
#include "irnode_t.h"
49
50
51
#include "irgraph_t.h"
#include "irloop.h"
#include "irprintf.h"
Michael Beck's avatar
Michael Beck committed
52
#include "execfreq.h"
53
#include "irdump_t.h"
54
55
#include "irtools.h"
#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
66
#ifdef WITH_ILP
#include <lpp/lpp.h>
#include <lpp/lpp_net.h>
Christian Würdig's avatar
Christian Würdig committed
67
#endif /* WITH_ILP */
68

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

71
typedef enum blocksched_algos_t {
72
	BLOCKSCHED_NAIV, BLOCKSCHED_GREEDY, BLOCKSCHED_ILP
73
74
75
76
77
} blocksched_algos_t;

static int algo = BLOCKSCHED_GREEDY;

static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
78
	{ "naiv",   BLOCKSCHED_NAIV },
79
80
81
	{ "greedy", BLOCKSCHED_GREEDY },
#ifdef WITH_ILP
	{ "ilp",    BLOCKSCHED_ILP },
Christian Würdig's avatar
Christian Würdig committed
82
#endif /* WITH_ILP */
83
84
85
86
87
88
89
90
	{ 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
91
	LC_OPT_ENT_ENUM_INT ("algo", "the block scheduling algorithm", &algo_var),
92
	LC_OPT_LAST
93
94
95
96
97
98
99
100
101
102
103
};

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

104
105
106
107
108
109
typedef struct blocksched_entry_t blocksched_entry_t;
struct blocksched_entry_t {
	ir_node            *block;
	blocksched_entry_t *next;
	blocksched_entry_t *prev;
};
110

111
112
typedef struct edge_t edge_t;
struct edge_t {
113
114
115
	ir_node *block;             /**< source block */
	int     pos;                /**< number of cfg predecessor (target) */
	double  execfreq;           /**< the frequency */
116
117
118
119
120
121
122
	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 */
};
123

124
125
typedef struct blocksched_env_t blocksched_env_t;
struct blocksched_env_t {
126
	ir_graph       *irg;
127
	struct obstack *obst;
128
129
130
131
	ir_exec_freq   *execfreqs;
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
132
};
133

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

146
147
	memset(&edge, 0, sizeof(edge));

148
	entry = OALLOCZ(env->obst, blocksched_entry_t);
149
150
151
	entry->block = block;
	set_irn_link(block, entry);

152
153
	loop = get_irn_loop(block);

154
	arity = get_Block_n_cfgpreds(block);
155

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

		/* is it an edge leaving a loop */
		if (get_loop_depth(pred_loop) > get_loop_depth(loop)) {
170
			float pred_freq = (float)get_block_execfreq(env->execfreqs, pred_block);
171
172
173
			edge.outedge_penalty_freq = -(pred_freq - freq);
		}

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

		edge.block = block;
185
186
		for (i = 0; i < arity; ++i) {
			double  execfreq;
187
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
188

189
190
			execfreq = get_block_execfreq(env->execfreqs, pred_block);

191
192
			edge.pos              = i;
			edge.execfreq         = execfreq;
193
194
			edge.highest_execfreq = 0;
			ARR_APP1(edge_t, env->edges, edge);
195
196

			if (execfreq > highest_execfreq) {
197
198
199
200
201
				highest_execfreq = execfreq;
				highest_edge_num = ARR_LEN(env->edges) - 1;
			}
		}

202
		if (highest_edge_num >= 0)
203
			env->edges[highest_edge_num].highest_execfreq = 1;
204
205
206
207
208
209
210
	}
}

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

	return QSORT_CMP(e2->execfreq, e1->execfreq);
213
214
}

215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
{
	const edge_t *e1 = d1;
	const edge_t *e2 = d2;
	/* 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);
		}
	}
}

237
238
239
240
static void coalesce_blocks(blocksched_env_t *env)
{
	int i;
	int edge_count = ARR_LEN(env->edges);
241
242
243
244
	edge_t *edges = env->edges;

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

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

254
255
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
256
257
			continue;

258
259
260
261
262
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
263
		entry      = get_irn_link(block);
264
265
		pred_entry = get_irn_link(pred_block);

266
		if (pred_entry->next != NULL || entry->prev != NULL)
267
			continue;
268
269
270

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

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

280
281
282
283
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

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

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

297
		/* the block might have been removed already... */
298
		if (is_Bad(get_Block_cfgpred(block, pos)))
299
300
			continue;

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
337
338
339
340
		pred_block = get_Block_cfgpred_block(block, pos);
		entry      = get_irn_link(block);
		pred_entry = get_irn_link(pred_block);

		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)))
341
342
343
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
344
		entry      = get_irn_link(block);
345
346
		pred_entry = get_irn_link(pred_block);

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

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

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
361
362
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
363
	blocksched_entry_t *succ_entry;
364
365
	const ir_edge_t    *edge;
	double             best_succ_execfreq;
366

367
	if (irn_visited_else_mark(block))
368
		return;
369

370
371
	env->blockcount++;

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

374
	/* put all successors into the worklist */
375
376
377
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

378
		if (irn_visited(succ_block))
379
380
			continue;

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

394
		if (irn_visited(succ_entry->block))
395
396
			continue;

397
		DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
398
399
400
		pdeq_putr(env->worklist, succ_entry->block);
	}

401
	if (entry->next != NULL) {
402
403
404
405
		pick_block_successor(entry->next, env);
		return;
	}

406
	DB((dbg, LEVEL_1, "deciding...\n"));
407
	best_succ_execfreq = -1;
408

409
	/* no successor yet: pick the successor block with the highest execution
410
411
	 * frequency which has no predecessor yet */

412
413
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);
414
		double  execfreq;
415

416
		if (irn_visited(succ_block))
417
418
419
			continue;

		succ_entry = get_irn_link(succ_block);
420
		if (succ_entry->prev != NULL)
421
422
			continue;

Michael Beck's avatar
Michael Beck committed
423
		execfreq = get_block_execfreq(env->execfreqs, succ_block);
424
		if (execfreq > best_succ_execfreq) {
425
426
427
428
429
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

430
	if (succ == NULL) {
431
		DB((dbg, LEVEL_1, "pick from worklist\n"));
432
433

		do {
434
			if (pdeq_empty(env->worklist)) {
435
				DB((dbg, LEVEL_1, "worklist empty\n"));
436
437
438
				return;
			}
			succ = pdeq_getl(env->worklist);
439
		} while (irn_visited(succ));
440
441
	}

442
443
	succ_entry       = get_irn_link(succ);
	entry->next      = succ_entry;
444
445
446
447
448
449
450
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
451
452
453
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
	blocksched_entry_t *entry      = get_irn_link(startblock);
454

455
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
456
457
458
459
460
461
462
	inc_irg_visited(irg);

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

463
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
464

465
466
467
	return entry;
}

468
469
470
471
472
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;
473
	blocksched_entry_t *entry;
474
	(void) env;
475
476

	block_list = NEW_ARR_D(ir_node *, obst, count);
477
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
478
479

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

	return block_list;
}

static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execfreqs)
{
491
492
	blocksched_env_t   env;
	struct obstack     obst;
493
	blocksched_entry_t *start_entry;
494
	ir_node            **block_list;
495
496
497

	obstack_init(&obst);

498
499
500
501
502
	env.irg        = irg;
	env.obst       = &obst;
	env.execfreqs  = execfreqs;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
503
504
	env.blockcount = 0;

505
506
507
508
509
	/* make sure loopinfo is up-to-date */
	if (! (get_irg_loopinfo_state(irg) & loopinfo_cf_consistent)) {
		construct_cf_backedges(irg);
	}

510
511
512
	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

513
	(void)be_remove_empty_blocks(irg);
514

515
	if (algo != BLOCKSCHED_NAIV)
516
517
518
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
519
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount,
520
	                                      be_get_be_obst(irg));
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537

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

	return block_list;
}

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

#ifdef WITH_ILP
538
typedef struct ilp_edge_t {
539
540
541
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
542
543
} ilp_edge_t;

544
typedef struct blocksched_ilp_env_t {
545
	blocksched_env_t env;
546
547
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
548
549
} blocksched_ilp_env_t;

550
typedef struct blocksched_ilp_entry_t {
551
	ir_node *block;
552
553
	struct blocksched_entry_t *next;
	struct blocksched_entry_t *prev;
554
555
556
557
558
559

	int out_cst;
} blocksched_ilp_entry_t;

static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
{
560
	char       name[64];
561
	ilp_edge_t edge;
562
	int        edgeidx = ARR_LEN(env->ilpedges);
563
564
565

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

566
567
	edge.block  = block;
	edge.pos    = pos;
568
569
570
571
572
573
574
575
	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)
{
576
577
578
579
580
581
582
	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;
583
584
585
586
587
	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);

588
	entry          = OALLOC(env->env.obst, blocksched_ilp_entry_t);
589
590
591
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
592
593
594
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, out_count - 1);
	set_irn_link(block, entry);

595
	if (block == startblock)
596
597
598
		return;

	arity = get_irn_arity(block);
599
	if (arity == 1) {
600
601
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
602
603
	}
	else {
604
605
606
607
608
		int i;

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

609
610
611
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
612
			ilp_edge_t *edge;
613
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
614
615

			execfreq = get_block_execfreq(env->env.execfreqs, pred_block);
616
617
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
618
619
620
621
622
623
624
625
			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
626
627
628
	int           edge_count = ARR_LEN(env->ilpedges);
	be_options_t *options    = be_get_irg_options(env->env.irg);
	int           i;
629
630

	/* complete out constraints */
631
	for (i = 0; i < edge_count; ++i) {
632
633
634
		const ilp_edge_t *edge  = &env->ilpedges[i];
		ir_node          *block = edge->block;
		ir_node          *pred;
635
636
		blocksched_ilp_entry_t *entry;

637
638
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
639
640
			continue;

641
		pred  = get_Block_cfgpred_block(block, edge->pos);
642
643
		entry = get_irn_link(pred);

644
		DB((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
645
				  pred, block, edge->pos));
646
647
648
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

Matthias Braun's avatar
Matthias Braun committed
649
	lpp_solve_net(env->lpp, options->ilp_server, options->ilp_solver);
650
651
652
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
653
654
655
656
657
	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;
658
659
660
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

661
662
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
663
664
			continue;

665
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
666
		if (is_jump)
667
668
			continue;

669
670
		pred       = get_Block_cfgpred_block(block, edge->pos);
		entry      = get_irn_link(block);
671
672
673
		pred_entry = get_irn_link(pred);

		assert(entry->prev == NULL && pred_entry->next == NULL);
674
		entry->prev      = pred_entry;
675
676
677
678
679
680
681
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
682
683
684
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
685
686
687

	obstack_init(&obst);

688
689
690
691
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.execfreqs  = execfreqs;
	env.env.worklist   = NULL;
692
	env.env.blockcount = 0;
693
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
694
695
696
697
698
699
700

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

701
	(void)be_remove_empty_blocks(irg);
702
703
704
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
705
706
	block_list  = create_blocksched_array(&env.env, start_entry,
	                                      env.env.blockcount,
707
	                                      be_get_be_obst(irg));
708
709
710
711
712
713
714

	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
715
#endif /* WITH_ILP */
716
717
718
719
720
721
722
723
724

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
725
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched);
726
void be_init_blocksched(void)
727
{
728
729
	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");
730
731

	lc_opt_add_table(blocksched_grp, be_blocksched_options);
732

Matthias Braun's avatar
Matthias Braun committed
733
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
734
}
735

736
ir_node **be_create_block_schedule(ir_graph *irg)
737
{
738
	ir_exec_freq *execfreqs = be_get_irg_exec_freq(irg);
739

740
	switch (algo) {
741
742
743
744
745
746
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
		return create_block_schedule_greedy(irg, execfreqs);
#ifdef WITH_ILP
	case BLOCKSCHED_ILP:
		return create_block_schedule_ilp(irg, execfreqs);
Christian Würdig's avatar
Christian Würdig committed
747
#endif /* WITH_ILP */
748
749
	}

750
	panic("unknown blocksched algo");
751
}