beblocksched.c 20.8 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
134
static blocksched_entry_t* get_blocksched_entry(const ir_node *block)
{
	return (blocksched_entry_t*)get_irn_link(block);
}

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

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

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

153
154
	loop = get_irn_loop(block);

155
	arity = get_Block_n_cfgpreds(block);
156

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

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

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

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

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

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

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

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

208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
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;
		}
	}
}

227
228
static int cmp_edges(const void *d1, const void *d2)
{
229
230
	const edge_t *e1 = (const edge_t*)d1;
	const edge_t *e2 = (const edge_t*)d2;
231
232
233
234
235
236
237
238
239
	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);
	}
240
241
}

242
243
static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
{
244
245
246
247
248
249
250
251
252
253
254
	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);
	}
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
}

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

271
272
273
274
static void coalesce_blocks(blocksched_env_t *env)
{
	int i;
	int edge_count = ARR_LEN(env->edges);
275
276
277
278
	edge_t *edges = env->edges;

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

280
281
	/* run1: only look at jumps */
	for (i = 0; i < edge_count; ++i) {
282
		const edge_t *edge  = &edges[i];
283
		ir_node      *block = edge->block;
284
		int           pos   = edge->pos;
285
		ir_node      *pred_block;
286
287
		blocksched_entry_t *entry, *pred_entry;

288
289
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
290
291
			continue;

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

		pred_block = get_Block_cfgpred_block(block, pos);
297
298
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
299

300
		if (pred_entry->next != NULL || entry->prev != NULL)
301
			continue;
302
303
304

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

307
		/* schedule the 2 blocks behind each other */
308
		DB((dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n",
309
		           pred_entry->block, entry->block, edge->execfreq));
310
		pred_entry->next = entry;
311
		entry->prev      = pred_entry;
312
313
	}

314
315
316
317
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

	qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_edges_outedge_penalty);
318
	for (i = 0; i < edge_count; ++i) {
319
		const edge_t *edge  = &edges[i];
320
		ir_node      *block = edge->block;
321
		int           pos   = edge->pos;
322
		ir_node      *pred_block;
323
		blocksched_entry_t *entry, *pred_entry;
324
325
326
327
328
329
		ir_loop      *loop;
		ir_loop      *outer_loop;

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

331
		/* the block might have been removed already... */
332
		if (is_Bad(get_Block_cfgpred(block, pos)))
333
334
			continue;

335
		pred_block = get_Block_cfgpred_block(block, pos);
336
337
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374

		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)))
375
376
377
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
378
379
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
380

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

385
		/* schedule the 2 blocks behind each other */
386
		DB((dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n",
387
		           pred_entry->block, entry->block, edge->execfreq));
388
		pred_entry->next = entry;
389
		entry->prev      = pred_entry;
390
391
392
393
394
	}
}

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
395
396
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
397
	blocksched_entry_t *succ_entry;
398
	double              best_succ_execfreq;
399

400
	if (irn_visited_else_mark(block))
401
		return;
402

403
404
	env->blockcount++;

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

407
	/* put all successors into the worklist */
408
409
410
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

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

414
415
		/* we only need to put the first of a series of already connected
		 * blocks into the worklist */
416
		succ_entry = (blocksched_entry_t*)get_irn_link(succ_block);
417
418
419
		while (succ_entry->prev != NULL) {
			/* break cycles... */
			if (succ_entry->prev->block == succ_block) {
420
				succ_entry->prev->next = NULL;
421
				succ_entry->prev       = NULL;
422
423
424
				break;
			}
			succ_entry = succ_entry->prev;
425
		}
426

427
		if (irn_visited(succ_entry->block))
428
429
			continue;

430
		DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
431
432
433
		pdeq_putr(env->worklist, succ_entry->block);
	}

434
	if (entry->next != NULL) {
435
436
437
438
		pick_block_successor(entry->next, env);
		return;
	}

439
	DB((dbg, LEVEL_1, "deciding...\n"));
440
	best_succ_execfreq = -1;
441

442
	/* no successor yet: pick the successor block with the highest execution
443
444
	 * frequency which has no predecessor yet */

445
446
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);
447
		double  execfreq;
448

449
		if (irn_visited(succ_block))
450
451
			continue;

452
		succ_entry = (blocksched_entry_t*)get_irn_link(succ_block);
453
		if (succ_entry->prev != NULL)
454
455
			continue;

Michael Beck's avatar
Michael Beck committed
456
		execfreq = get_block_execfreq(env->execfreqs, succ_block);
457
		if (execfreq > best_succ_execfreq) {
458
459
460
461
462
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

463
	if (succ == NULL) {
464
		DB((dbg, LEVEL_1, "pick from worklist\n"));
465
466

		do {
467
			if (pdeq_empty(env->worklist)) {
468
				DB((dbg, LEVEL_1, "worklist empty\n"));
469
470
				return;
			}
471
			succ = (ir_node*)pdeq_getl(env->worklist);
472
		} while (irn_visited(succ));
473
474
	}

475
	succ_entry       = (blocksched_entry_t*)get_irn_link(succ);
476
	entry->next      = succ_entry;
477
478
479
480
481
482
483
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
484
485
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
486
	blocksched_entry_t *entry      = (blocksched_entry_t*)get_irn_link(startblock);
487

488
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
489
490
491
492
493
494
495
	inc_irg_visited(irg);

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

496
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
497

498
499
500
	return entry;
}

501
502
503
504
505
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;
506
	blocksched_entry_t *entry;
507
	(void) env;
508
509

	block_list = NEW_ARR_D(ir_node *, obst, count);
510
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
511
512

	for (entry = first; entry != NULL; entry = entry->next) {
513
514
		assert(i < count);
		block_list[i++] = entry->block;
515
		DB((dbg, LEVEL_1, "\t%+F\n", entry->block));
516
517
518
519
520
521
522
523
	}
	assert(i == count);

	return block_list;
}

static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execfreqs)
{
524
525
	blocksched_env_t   env;
	struct obstack     obst;
526
	blocksched_entry_t *start_entry;
527
	ir_node            **block_list;
528
529
530

	obstack_init(&obst);

531
532
533
534
535
	env.irg        = irg;
	env.obst       = &obst;
	env.execfreqs  = execfreqs;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
536
537
	env.blockcount = 0;

538
	assure_loopinfo(irg);
539

540
541
542
	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

543
	(void)be_remove_empty_blocks(irg);
544

545
	if (algo != BLOCKSCHED_NAIV)
546
547
548
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
549
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount,
550
	                                      be_get_be_obst(irg));
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566

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

	return block_list;
}

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

567
typedef struct ilp_edge_t {
568
569
570
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
571
572
} ilp_edge_t;

573
typedef struct blocksched_ilp_env_t {
574
	blocksched_env_t env;
575
576
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
577
578
} blocksched_ilp_env_t;

579
typedef struct blocksched_ilp_entry_t {
580
	ir_node *block;
581
582
	struct blocksched_entry_t *next;
	struct blocksched_entry_t *prev;
583
584
585
586
587
588

	int out_cst;
} blocksched_ilp_entry_t;

static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
{
589
	char       name[64];
590
	ilp_edge_t edge;
591
	int        edgeidx = ARR_LEN(env->ilpedges);
592
593
594

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

595
596
	edge.block  = block;
	edge.pos    = pos;
597
598
599
600
601
602
603
604
	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)
{
605
	blocksched_ilp_env_t *env        = (blocksched_ilp_env_t*)data;
606
607
608
609
610
	ir_graph             *irg        = env->env.irg;
	ir_node              *startblock = get_irg_start_block(irg);
	int                  arity;
	char                 name[64];
	int                  out_count;
611
612
613
614
615
	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);

616
	entry          = OALLOC(env->env.obst, blocksched_ilp_entry_t);
617
618
619
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
620
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, out_count - 1);
621
622
	set_irn_link(block, entry);

623
	if (block == startblock)
624
625
626
		return;

	arity = get_irn_arity(block);
627
	if (arity == 1) {
628
629
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
630
631
	}
	else {
632
		int i;
633
		int cst_idx;
634
635

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

638
639
640
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
641
			ilp_edge_t *edge;
642
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
643
644

			execfreq = get_block_execfreq(env->env.execfreqs, pred_block);
645
646
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
647
			lpp_set_factor_fast(env->lpp, cst_idx, edge->ilpvar, 1.0);
648
649
650
651
		}
	}
}

652
653
654
655
static blocksched_ilp_entry_t *get_blocksched_ilp_entry(const ir_node *block)
{
	return (blocksched_ilp_entry_t*)get_irn_link(block);
}
656
657
658

static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
Matthias Braun's avatar
Matthias Braun committed
659
660
	int           edge_count = ARR_LEN(env->ilpedges);
	int           i;
661
662

	/* complete out constraints */
663
	for (i = 0; i < edge_count; ++i) {
664
665
666
		const ilp_edge_t *edge  = &env->ilpedges[i];
		ir_node          *block = edge->block;
		ir_node          *pred;
667
668
		blocksched_ilp_entry_t *entry;

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

673
		pred  = get_Block_cfgpred_block(block, edge->pos);
674
		entry = get_blocksched_ilp_entry(pred);
675

676
		DB((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
677
				  pred, block, edge->pos));
678
679
680
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

681
	lpp_solve_net(env->lpp, be_options.ilp_server, be_options.ilp_solver);
682
683
684
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
685
686
687
688
689
	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;
690
691
692
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

693
694
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
695
696
			continue;

697
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
698
		if (is_jump)
699
700
			continue;

701
		pred       = get_Block_cfgpred_block(block, edge->pos);
702
703
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred);
704
705

		assert(entry->prev == NULL && pred_entry->next == NULL);
706
		entry->prev      = pred_entry;
707
708
709
710
711
712
713
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
714
715
716
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
717
718
719

	obstack_init(&obst);

720
721
722
723
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.execfreqs  = execfreqs;
	env.env.worklist   = NULL;
724
	env.env.blockcount = 0;
725
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
726

727
	env.lpp = lpp_new("blockschedule", lpp_minimize);
728
729
730
731
732
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

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

733
	(void)be_remove_empty_blocks(irg);
734
735
736
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
737
738
	block_list  = create_blocksched_array(&env.env, start_entry,
	                                      env.env.blockcount,
739
	                                      be_get_be_obst(irg));
740
741

	DEL_ARR_F(env.ilpedges);
742
	lpp_free(env.lpp);
743
744
745
746
747
748
749
750
751
752
753
754
755
	obstack_free(&obst, NULL);

	return block_list;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
Matthias Braun's avatar
Matthias Braun committed
756
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
757
void be_init_blocksched(void)
758
{
759
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
760

761
	lc_opt_add_table(be_grp, be_blocksched_options);
762

Matthias Braun's avatar
Matthias Braun committed
763
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
764
}
765

766
ir_node **be_create_block_schedule(ir_graph *irg)
767
{
768
	ir_exec_freq *execfreqs = be_get_irg_exec_freq(irg);
769

770
	switch (algo) {
771
772
773
774
775
776
777
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
		return create_block_schedule_greedy(irg, execfreqs);
	case BLOCKSCHED_ILP:
		return create_block_schedule_ilp(irg, execfreqs);
	}

778
	panic("unknown blocksched algo");
779
}