beblocksched.c 20.2 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
#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
502
503
504
505
	/* make sure loopinfo is up-to-date */
	if (! (get_irg_loopinfo_state(irg) & loopinfo_cf_consistent)) {
		construct_cf_backedges(irg);
	}

506
507
508
	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

509
	(void)be_remove_empty_blocks(irg);
510

511
	if (algo != BLOCKSCHED_NAIV)
512
513
514
		coalesce_blocks(&env);

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

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

	return block_list;
}

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

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

539
typedef struct blocksched_ilp_env_t {
540
	blocksched_env_t env;
541
542
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
543
544
} blocksched_ilp_env_t;

545
typedef struct blocksched_ilp_entry_t {
546
	ir_node *block;
547
548
	struct blocksched_entry_t *next;
	struct blocksched_entry_t *prev;
549
550
551
552
553
554

	int out_cst;
} blocksched_ilp_entry_t;

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

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

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

583
	entry          = OALLOC(env->env.obst, blocksched_ilp_entry_t);
584
585
586
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
587
588
589
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, out_count - 1);
	set_irn_link(block, entry);

590
	if (block == startblock)
591
592
593
		return;

	arity = get_irn_arity(block);
594
	if (arity == 1) {
595
596
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
597
598
	}
	else {
599
600
601
602
603
		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);

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

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

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

632
633
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
634
635
			continue;

636
		pred  = get_Block_cfgpred_block(block, edge->pos);
637
638
		entry = get_irn_link(pred);

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

Matthias Braun's avatar
Matthias Braun committed
644
	lpp_solve_net(env->lpp, options->ilp_server, options->ilp_solver);
645
646
647
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
648
649
650
651
652
	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;
653
654
655
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

656
657
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
658
659
			continue;

660
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
661
		if (is_jump)
662
663
			continue;

664
665
		pred       = get_Block_cfgpred_block(block, edge->pos);
		entry      = get_irn_link(block);
666
667
668
		pred_entry = get_irn_link(pred);

		assert(entry->prev == NULL && pred_entry->next == NULL);
669
		entry->prev      = pred_entry;
670
671
672
673
674
675
676
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
677
678
679
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
680
681
682

	obstack_init(&obst);

683
684
685
686
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.execfreqs  = execfreqs;
	env.env.worklist   = NULL;
687
	env.env.blockcount = 0;
688
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
689

690
	env.lpp = lpp_new("blockschedule", lpp_minimize);
691
692
693
694
695
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

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

696
	(void)be_remove_empty_blocks(irg);
697
698
699
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
700
701
	block_list  = create_blocksched_array(&env.env, start_entry,
	                                      env.env.blockcount,
702
	                                      be_get_be_obst(irg));
703
704

	DEL_ARR_F(env.ilpedges);
705
	lpp_free(env.lpp);
706
707
708
709
710
711
712
713
714
715
716
717
718
	obstack_free(&obst, NULL);

	return block_list;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
Matthias Braun's avatar
Matthias Braun committed
719
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
720
void be_init_blocksched(void)
721
{
722
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
723

724
	lc_opt_add_table(be_grp, be_blocksched_options);
725

Matthias Braun's avatar
Matthias Braun committed
726
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
727
}
728

729
ir_node **be_create_block_schedule(ir_graph *irg)
730
{
731
	ir_exec_freq *execfreqs = be_get_irg_exec_freq(irg);
732

733
	switch (algo) {
734
735
736
737
738
739
740
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
		return create_block_schedule_greedy(irg, execfreqs);
	case BLOCKSCHED_ILP:
		return create_block_schedule_ilp(irg, execfreqs);
	}

741
	panic("unknown blocksched algo");
742
}