beblocksched.c 19.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Christian Würdig's avatar
Christian Würdig committed
6
7
8
9
10
/**
 * @file
 * @brief       Block-scheduling strategies.
 * @author      Matthias Braun, Christoph Mallon
 * @date        27.09.2006
11
12
13
14
15
16
17
18
19
20
 *
 * 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
21
22
23
24
25
26
27
 */
#include "beblocksched.h"

#include <stdlib.h>

#include "array.h"
#include "pdeq.h"
28
#include "beirg.h"
29
30
#include "iredges.h"
#include "irgwalk.h"
Michael Beck's avatar
Michael Beck committed
31
#include "irnode_t.h"
32
33
#include "irgraph_t.h"
#include "irloop.h"
Michael Beck's avatar
Michael Beck committed
34
#include "execfreq.h"
35
#include "irdump_t.h"
36
37
#include "irtools.h"
#include "debug.h"
38
#include "beirgmod.h"
39
40
#include "bemodule.h"
#include "be.h"
41
#include "error.h"
42

Matthias Braun's avatar
Matthias Braun committed
43
44
#include "lc_opts.h"
#include "lc_opts_enum.h"
45

46
47
#include "lpp.h"
#include "lpp_net.h"
48

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

51
typedef enum blocksched_algos_t {
52
	BLOCKSCHED_NAIV, BLOCKSCHED_GREEDY, BLOCKSCHED_ILP
53
54
55
56
57
} blocksched_algos_t;

static int algo = BLOCKSCHED_GREEDY;

static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
58
	{ "naiv",   BLOCKSCHED_NAIV },
59
60
61
62
63
64
65
66
67
68
	{ "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[] = {
69
	LC_OPT_ENT_ENUM_INT ("blockscheduler", "the block scheduling algorithm", &algo_var),
70
	LC_OPT_LAST
71
72
73
74
75
76
77
78
79
80
81
};

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

82
83
84
85
86
87
typedef struct blocksched_entry_t blocksched_entry_t;
struct blocksched_entry_t {
	ir_node            *block;
	blocksched_entry_t *next;
	blocksched_entry_t *prev;
};
88

89
90
typedef struct edge_t edge_t;
struct edge_t {
91
92
93
	ir_node *block;             /**< source block */
	int     pos;                /**< number of cfg predecessor (target) */
	double  execfreq;           /**< the frequency */
94
95
96
97
98
99
100
	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 */
};
101

102
103
typedef struct blocksched_env_t blocksched_env_t;
struct blocksched_env_t {
104
	ir_graph       *irg;
105
	struct obstack  obst;
106
107
108
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
109
};
110

111
112
113
114
115
static blocksched_entry_t* get_blocksched_entry(const ir_node *block)
{
	return (blocksched_entry_t*)get_irn_link(block);
}

116
117
118
119
/**
 * Collect cfg frequencies of all edges between blocks.
 * Also determines edge with highest frequency.
 */
120
121
static void collect_egde_frequency(ir_node *block, void *data)
{
122
	blocksched_env_t   *env = (blocksched_env_t*)data;
123
124
	int                arity;
	edge_t             edge;
125
	blocksched_entry_t *entry;
126
	ir_loop            *loop;
127

128
129
	memset(&edge, 0, sizeof(edge));

130
	entry = OALLOCZ(&env->obst, blocksched_entry_t);
131
132
133
	entry->block = block;
	set_irn_link(block, entry);

134
135
	loop = get_irn_loop(block);

136
	arity = get_Block_n_cfgpreds(block);
137

138
	if (arity == 0) {
139
140
		/* must be the start block (or end-block for endless loops),
		 * everything else is dead code and should be removed by now */
141
142
		assert(block == get_irg_start_block(env->irg)
				|| block == get_irg_end_block(env->irg));
143
		/* nothing to do here */
144
145
		return;
	} else if (arity == 1) {
146
147
		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
		ir_loop *pred_loop  = get_irn_loop(pred_block);
148
		float    freq       = (float)get_block_execfreq(block);
149
150
151

		/* is it an edge leaving a loop */
		if (get_loop_depth(pred_loop) > get_loop_depth(loop)) {
152
			float pred_freq = (float)get_block_execfreq(pred_block);
153
154
155
			edge.outedge_penalty_freq = -(pred_freq - freq);
		}

156
157
		edge.block            = block;
		edge.pos              = 0;
158
		edge.execfreq         = freq;
159
160
161
		edge.highest_execfreq = 1;
		ARR_APP1(edge_t, env->edges, edge);
	} else {
162
		int    i;
163
		double highest_execfreq = -1.0;
164
		int    highest_edge_num = -1;
165
166

		edge.block = block;
167
168
		for (i = 0; i < arity; ++i) {
			double  execfreq;
169
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
170

171
			execfreq = get_block_execfreq(pred_block);
172

173
174
			edge.pos              = i;
			edge.execfreq         = execfreq;
175
176
			edge.highest_execfreq = 0;
			ARR_APP1(edge_t, env->edges, edge);
177
178

			if (execfreq > highest_execfreq) {
179
180
181
182
183
				highest_execfreq = execfreq;
				highest_edge_num = ARR_LEN(env->edges) - 1;
			}
		}

184
		if (highest_edge_num >= 0)
185
			env->edges[highest_edge_num].highest_execfreq = 1;
186
187
188
	}
}

189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
static int cmp_edges_base(const edge_t *e1, const edge_t *e2)
{
	long nr1 = get_irn_node_nr(e1->block);
	long nr2 = get_irn_node_nr(e2->block);
	if (nr1 < nr2) {
		return 1;
	} else if (nr1 > nr2) {
		return -1;
	} else {
		if (e1->pos < e2->pos) {
			return 1;
		} else if (e1->pos > e2->pos) {
			return -1;
		} else {
			return 0;
		}
	}
}

208
209
static int cmp_edges(const void *d1, const void *d2)
{
210
211
	const edge_t *e1 = (const edge_t*)d1;
	const edge_t *e2 = (const edge_t*)d2;
212
213
214
215
216
217
218
219
220
	double        freq1 = e1->execfreq;
	double        freq2 = e2->execfreq;
	if (freq1 < freq2) {
		return 1;
	} else if (freq1 > freq2) {
		return -1;
	} else {
		return cmp_edges_base(e1, e2);
	}
221
222
}

223
224
static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
{
225
226
227
228
229
230
231
232
233
234
235
	const edge_t *e1   = (const edge_t*)d1;
	const edge_t *e2   = (const edge_t*)d2;
	double        pen1 = e1->outedge_penalty_freq;
	double        pen2 = e2->outedge_penalty_freq;
	if (pen1 > pen2) {
		return 1;
	} else if (pen1 < pen2) {
		return -1;
	} else {
		return cmp_edges_base(e1, e2);
	}
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
}

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

252
253
254
255
static void coalesce_blocks(blocksched_env_t *env)
{
	int i;
	int edge_count = ARR_LEN(env->edges);
256
257
258
259
	edge_t *edges = env->edges;

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

261
262
	/* run1: only look at jumps */
	for (i = 0; i < edge_count; ++i) {
263
		const edge_t *edge  = &edges[i];
264
		ir_node      *block = edge->block;
265
		int           pos   = edge->pos;
266
		ir_node      *pred_block;
267
268
		blocksched_entry_t *entry, *pred_entry;

269
270
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
271
272
			continue;

273
274
275
276
277
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
Christoph Mallon's avatar
Christoph Mallon committed
278
279
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
280

281
		if (pred_entry->next != NULL || entry->prev != NULL)
282
			continue;
283
284
285

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

288
		/* schedule the 2 blocks behind each other */
289
		DB((dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n",
290
		           pred_entry->block, entry->block, edge->execfreq));
291
		pred_entry->next = entry;
292
		entry->prev      = pred_entry;
293
294
	}

295
296
297
298
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

	qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_edges_outedge_penalty);
299
	for (i = 0; i < edge_count; ++i) {
300
		const edge_t *edge  = &edges[i];
301
		ir_node      *block = edge->block;
302
		int           pos   = edge->pos;
303
		ir_node      *pred_block;
304
		blocksched_entry_t *entry, *pred_entry;
305
306
307
308
309
310
		ir_loop      *loop;
		ir_loop      *outer_loop;

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

312
		/* the block might have been removed already... */
313
		if (is_Bad(get_Block_cfgpred(block, pos)))
314
315
			continue;

316
		pred_block = get_Block_cfgpred_block(block, pos);
Christoph Mallon's avatar
Christoph Mallon committed
317
318
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355

		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)))
356
357
358
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
Christoph Mallon's avatar
Christoph Mallon committed
359
360
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
361

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

366
		/* schedule the 2 blocks behind each other */
367
		DB((dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n",
368
		           pred_entry->block, entry->block, edge->execfreq));
369
		pred_entry->next = entry;
370
		entry->prev      = pred_entry;
371
372
373
374
375
	}
}

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
376
377
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
378
	blocksched_entry_t *succ_entry;
379
	double              best_succ_execfreq;
380

381
	if (irn_visited_else_mark(block))
382
		return;
383

384
385
	env->blockcount++;

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

388
	/* put all successors into the worklist */
389
390
391
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

392
		if (irn_visited(succ_block))
393
394
			continue;

395
396
		/* we only need to put the first of a series of already connected
		 * blocks into the worklist */
Christoph Mallon's avatar
Christoph Mallon committed
397
		succ_entry = get_blocksched_entry(succ_block);
398
399
400
		while (succ_entry->prev != NULL) {
			/* break cycles... */
			if (succ_entry->prev->block == succ_block) {
401
				succ_entry->prev->next = NULL;
402
				succ_entry->prev       = NULL;
403
404
405
				break;
			}
			succ_entry = succ_entry->prev;
406
		}
407

408
		if (irn_visited(succ_entry->block))
409
410
			continue;

411
		DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
412
413
414
		pdeq_putr(env->worklist, succ_entry->block);
	}

415
	if (entry->next != NULL) {
416
417
418
419
		pick_block_successor(entry->next, env);
		return;
	}

420
	DB((dbg, LEVEL_1, "deciding...\n"));
421
	best_succ_execfreq = -1;
422

423
	/* no successor yet: pick the successor block with the highest execution
424
425
	 * frequency which has no predecessor yet */

426
427
428
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

429
		if (irn_visited(succ_block))
430
431
			continue;

Christoph Mallon's avatar
Christoph Mallon committed
432
		succ_entry = get_blocksched_entry(succ_block);
433
		if (succ_entry->prev != NULL)
434
435
			continue;

436
		double execfreq = get_block_execfreq(succ_block);
437
		if (execfreq > best_succ_execfreq) {
438
439
440
441
442
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

443
	if (succ == NULL) {
444
		DB((dbg, LEVEL_1, "pick from worklist\n"));
445
446

		do {
447
			if (pdeq_empty(env->worklist)) {
448
				DB((dbg, LEVEL_1, "worklist empty\n"));
449
450
				return;
			}
451
			succ = (ir_node*)pdeq_getl(env->worklist);
452
		} while (irn_visited(succ));
453
454
	}

Christoph Mallon's avatar
Christoph Mallon committed
455
	succ_entry       = get_blocksched_entry(succ);
456
	entry->next      = succ_entry;
457
458
459
460
461
462
463
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
464
465
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
Christoph Mallon's avatar
Christoph Mallon committed
466
	blocksched_entry_t *entry      = get_blocksched_entry(startblock);
467

468
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
469
470
471
472
473
474
475
	inc_irg_visited(irg);

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

476
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
477

478
479
480
	return entry;
}

481
482
483
484
485
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;
486
	blocksched_entry_t *entry;
487
	(void) env;
488
489

	block_list = NEW_ARR_D(ir_node *, obst, count);
490
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
491
492

	for (entry = first; entry != NULL; entry = entry->next) {
493
494
		assert(i < count);
		block_list[i++] = entry->block;
495
		DB((dbg, LEVEL_1, "\t%+F\n", entry->block));
496
497
498
499
500
501
	}
	assert(i == count);

	return block_list;
}

502
static ir_node **create_block_schedule_greedy(ir_graph *irg)
503
{
504
	blocksched_env_t   env;
505
	blocksched_entry_t *start_entry;
506
	ir_node            **block_list;
507

508
509
510
	env.irg        = irg;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
511
	env.blockcount = 0;
512
	obstack_init(&env.obst);
513

514
	assure_loopinfo(irg);
515

516
517
518
	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

519
	(void)be_remove_empty_blocks(irg);
520

521
	if (algo != BLOCKSCHED_NAIV)
522
523
524
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
525
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount,
526
	                                      be_get_be_obst(irg));
527
528

	DEL_ARR_F(env.edges);
529
	obstack_free(&env.obst, NULL);
530
531
532
533
534
535
536
537
538
539
540
541
542

	return block_list;
}

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

543
typedef struct ilp_edge_t {
544
545
546
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
547
548
} ilp_edge_t;

549
typedef struct blocksched_ilp_env_t {
550
	blocksched_env_t env;
551
552
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
553
554
} blocksched_ilp_env_t;

555
typedef struct blocksched_ilp_entry_t {
556
	ir_node *block;
557
558
	struct blocksched_entry_t *next;
	struct blocksched_entry_t *prev;
559
560
561
562
563
564

	int out_cst;
} blocksched_ilp_entry_t;

static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
{
565
	char       name[64];
566
	ilp_edge_t edge;
567
	int        edgeidx = ARR_LEN(env->ilpedges);
568
569
570

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

571
572
	edge.block  = block;
	edge.pos    = pos;
573
574
575
576
577
578
579
580
	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)
{
581
	blocksched_ilp_env_t *env        = (blocksched_ilp_env_t*)data;
582
583
584
585
586
	ir_graph             *irg        = env->env.irg;
	ir_node              *startblock = get_irg_start_block(irg);
	int                  arity;
	char                 name[64];
	int                  out_count;
587
588
589
590
591
	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);

592
	entry          = OALLOC(&env->env.obst, blocksched_ilp_entry_t);
593
594
595
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
596
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, out_count - 1);
597
598
	set_irn_link(block, entry);

599
	if (block == startblock)
600
601
602
		return;

	arity = get_irn_arity(block);
603
	if (arity == 1) {
604
		double execfreq = get_block_execfreq(block);
605
		add_ilp_edge(block, 0, execfreq, env);
606
	} else {
607
		int i;
608
		int cst_idx;
609
610

		snprintf(name, sizeof(name), "block_in_constr_%ld", get_irn_node_nr(block));
611
		cst_idx = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, arity - 1);
612

613
614
615
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
616
			ilp_edge_t *edge;
617
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
618

619
			execfreq = get_block_execfreq(pred_block);
620
621
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
622
			lpp_set_factor_fast(env->lpp, cst_idx, edge->ilpvar, 1.0);
623
624
625
626
		}
	}
}

627
628
629
630
static blocksched_ilp_entry_t *get_blocksched_ilp_entry(const ir_node *block)
{
	return (blocksched_ilp_entry_t*)get_irn_link(block);
}
631
632
633

static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
Matthias Braun's avatar
Matthias Braun committed
634
635
	int           edge_count = ARR_LEN(env->ilpedges);
	int           i;
636
637

	/* complete out constraints */
638
	for (i = 0; i < edge_count; ++i) {
639
640
641
		const ilp_edge_t *edge  = &env->ilpedges[i];
		ir_node          *block = edge->block;
		ir_node          *pred;
642
643
		blocksched_ilp_entry_t *entry;

644
645
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
646
647
			continue;

648
		pred  = get_Block_cfgpred_block(block, edge->pos);
649
		entry = get_blocksched_ilp_entry(pred);
650

651
		DB((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
652
				  pred, block, edge->pos));
653
654
655
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

656
	lpp_solve_net(env->lpp, be_options.ilp_server, be_options.ilp_solver);
657
658
659
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
660
661
662
663
664
	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;
665
666
667
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

668
669
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
670
671
			continue;

672
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
673
		if (is_jump)
674
675
			continue;

676
		pred       = get_Block_cfgpred_block(block, edge->pos);
677
678
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred);
679
680

		assert(entry->prev == NULL && pred_entry->next == NULL);
681
		entry->prev      = pred_entry;
682
683
684
685
		pred_entry->next = entry;
	}
}

686
static ir_node **create_block_schedule_ilp(ir_graph *irg)
687
688
{
	blocksched_ilp_env_t env;
689
690
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
691

692
693
	env.env.irg        = irg;
	env.env.worklist   = NULL;
694
	env.env.blockcount = 0;
695
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
696
	obstack_init(&env.env.obst);
697

698
	env.lpp = lpp_new("blockschedule", lpp_minimize);
699
700
701
702
703
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

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

704
	(void)be_remove_empty_blocks(irg);
705
706
707
	coalesce_blocks_ilp(&env);

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

	DEL_ARR_F(env.ilpedges);
713
	lpp_free(env.lpp);
714
	obstack_free(&env.env.obst, NULL);
715
716
717
718
719
720
721
722
723
724
725
726

	return block_list;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
Matthias Braun's avatar
Matthias Braun committed
727
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
728
void be_init_blocksched(void)
729
{
730
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
731

732
	lc_opt_add_table(be_grp, be_blocksched_options);
733

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

737
ir_node **be_create_block_schedule(ir_graph *irg)
738
{
739
	switch (algo) {
740
741
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
742
		return create_block_schedule_greedy(irg);
743
	case BLOCKSCHED_ILP:
744
		return create_block_schedule_ilp(irg);
745
746
	}

747
	panic("unknown blocksched algo");
748
}