beblocksched.c 20.9 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
399
	const ir_edge_t    *edge;
	double             best_succ_execfreq;
400

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

404
405
	env->blockcount++;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	pick_block_successor(succ_entry, env);
}

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

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

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

497
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
498

499
500
501
	return entry;
}

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

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

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

	return block_list;
}

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

	obstack_init(&obst);

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

539
	assure_loopinfo(irg);
540

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

544
	(void)be_remove_empty_blocks(irg);
545

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

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

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

	return block_list;
}

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

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

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

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

	int out_cst;
} blocksched_ilp_entry_t;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	obstack_init(&obst);

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

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

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

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

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

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

	return block_list;
}

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

762
	lc_opt_add_table(be_grp, be_blocksched_options);
763

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

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

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

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