beblocksched.c 20.6 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
/**
 * 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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
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;
		}
	}
}

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

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

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

266
267
268
269
static void coalesce_blocks(blocksched_env_t *env)
{
	int i;
	int edge_count = ARR_LEN(env->edges);
270
271
272
273
	edge_t *edges = env->edges;

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

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

283
284
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
285
286
			continue;

287
288
289
290
291
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
292
293
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
294

295
		if (pred_entry->next != NULL || entry->prev != NULL)
296
			continue;
297
298
299

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

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

309
310
311
312
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

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

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

326
		/* the block might have been removed already... */
327
		if (is_Bad(get_Block_cfgpred(block, pos)))
328
329
			continue;

330
		pred_block = get_Block_cfgpred_block(block, pos);
331
332
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
333
334
335
336
337
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

		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)))
370
371
372
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
373
374
		entry      = (blocksched_entry_t*)get_irn_link(block);
		pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
375

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

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

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
390
391
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
392
	blocksched_entry_t *succ_entry;
393
394
	const ir_edge_t    *edge;
	double             best_succ_execfreq;
395

396
	if (irn_visited_else_mark(block))
397
		return;
398

399
400
	env->blockcount++;

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

403
	/* put all successors into the worklist */
404
405
406
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

407
		if (irn_visited(succ_block))
408
409
			continue;

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

423
		if (irn_visited(succ_entry->block))
424
425
			continue;

426
		DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
427
428
429
		pdeq_putr(env->worklist, succ_entry->block);
	}

430
	if (entry->next != NULL) {
431
432
433
434
		pick_block_successor(entry->next, env);
		return;
	}

435
	DB((dbg, LEVEL_1, "deciding...\n"));
436
	best_succ_execfreq = -1;
437

438
	/* no successor yet: pick the successor block with the highest execution
439
440
	 * frequency which has no predecessor yet */

441
442
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);
443
		double  execfreq;
444

445
		if (irn_visited(succ_block))
446
447
			continue;

448
		succ_entry = (blocksched_entry_t*)get_irn_link(succ_block);
449
		if (succ_entry->prev != NULL)
450
451
			continue;

Michael Beck's avatar
Michael Beck committed
452
		execfreq = get_block_execfreq(env->execfreqs, succ_block);
453
		if (execfreq > best_succ_execfreq) {
454
455
456
457
458
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

459
	if (succ == NULL) {
460
		DB((dbg, LEVEL_1, "pick from worklist\n"));
461
462

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

471
	succ_entry       = (blocksched_entry_t*)get_irn_link(succ);
472
	entry->next      = succ_entry;
473
474
475
476
477
478
479
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
480
481
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
482
	blocksched_entry_t *entry      = (blocksched_entry_t*)get_irn_link(startblock);
483

484
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
485
486
487
488
489
490
491
	inc_irg_visited(irg);

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

492
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
493

494
495
496
	return entry;
}

497
498
499
500
501
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;
502
	blocksched_entry_t *entry;
503
	(void) env;
504
505

	block_list = NEW_ARR_D(ir_node *, obst, count);
506
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
507
508

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

	return block_list;
}

static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execfreqs)
{
520
521
	blocksched_env_t   env;
	struct obstack     obst;
522
	blocksched_entry_t *start_entry;
523
	ir_node            **block_list;
524
525
526

	obstack_init(&obst);

527
528
529
530
531
	env.irg        = irg;
	env.obst       = &obst;
	env.execfreqs  = execfreqs;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
532
533
	env.blockcount = 0;

534
	assure_loopinfo(irg);
535

536
537
538
	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

539
	(void)be_remove_empty_blocks(irg);
540

541
	if (algo != BLOCKSCHED_NAIV)
542
543
544
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
545
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount,
546
	                                      be_get_be_obst(irg));
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562

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

	return block_list;
}

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

563
typedef struct ilp_edge_t {
564
565
566
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
567
568
} ilp_edge_t;

569
typedef struct blocksched_ilp_env_t {
570
	blocksched_env_t env;
571
572
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
573
574
} blocksched_ilp_env_t;

575
typedef struct blocksched_ilp_entry_t {
576
	ir_node *block;
577
578
	struct blocksched_entry_t *next;
	struct blocksched_entry_t *prev;
579
580
581
582
583
584

	int out_cst;
} blocksched_ilp_entry_t;

static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
{
585
	char       name[64];
586
	ilp_edge_t edge;
587
	int        edgeidx = ARR_LEN(env->ilpedges);
588
589
590

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

591
592
	edge.block  = block;
	edge.pos    = pos;
593
594
595
596
597
598
599
600
	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)
{
601
602
603
604
605
606
607
	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;
608
609
610
611
612
	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);

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

620
	if (block == startblock)
621
622
623
		return;

	arity = get_irn_arity(block);
624
	if (arity == 1) {
625
626
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
627
628
	}
	else {
629
630
631
		int i;

		snprintf(name, sizeof(name), "block_in_constr_%ld", get_irn_node_nr(block));
632
		cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, arity - 1);
633

634
635
636
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
637
			ilp_edge_t *edge;
638
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
639
640

			execfreq = get_block_execfreq(env->env.execfreqs, pred_block);
641
642
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
643
644
645
646
647
648
649
650
			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
651
652
	int           edge_count = ARR_LEN(env->ilpedges);
	int           i;
653
654

	/* complete out constraints */
655
	for (i = 0; i < edge_count; ++i) {
656
657
658
		const ilp_edge_t *edge  = &env->ilpedges[i];
		ir_node          *block = edge->block;
		ir_node          *pred;
659
660
		blocksched_ilp_entry_t *entry;

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

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

668
		DB((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
669
				  pred, block, edge->pos));
670
671
672
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

673
	lpp_solve_net(env->lpp, be_options.ilp_server, be_options.ilp_solver);
674
675
676
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
677
678
679
680
681
	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;
682
683
684
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

685
686
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
687
688
			continue;

689
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
690
		if (is_jump)
691
692
			continue;

693
694
		pred       = get_Block_cfgpred_block(block, edge->pos);
		entry      = get_irn_link(block);
695
696
697
		pred_entry = get_irn_link(pred);

		assert(entry->prev == NULL && pred_entry->next == NULL);
698
		entry->prev      = pred_entry;
699
700
701
702
703
704
705
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
706
707
708
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
709
710
711

	obstack_init(&obst);

712
713
714
715
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.execfreqs  = execfreqs;
	env.env.worklist   = NULL;
716
	env.env.blockcount = 0;
717
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
718

719
	env.lpp = lpp_new("blockschedule", lpp_minimize);
720
721
722
723
724
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

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

725
	(void)be_remove_empty_blocks(irg);
726
727
728
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
729
730
	block_list  = create_blocksched_array(&env.env, start_entry,
	                                      env.env.blockcount,
731
	                                      be_get_be_obst(irg));
732
733

	DEL_ARR_F(env.ilpedges);
734
	lpp_free(env.lpp);
735
736
737
738
739
740
741
742
743
744
745
746
747
	obstack_free(&obst, NULL);

	return block_list;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
Matthias Braun's avatar
Matthias Braun committed
748
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
749
void be_init_blocksched(void)
750
{
751
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
752

753
	lc_opt_add_table(be_grp, be_blocksched_options);
754

Matthias Braun's avatar
Matthias Braun committed
755
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
756
}
757

758
ir_node **be_create_block_schedule(ir_graph *irg)
759
{
760
	ir_exec_freq *execfreqs = be_get_irg_exec_freq(irg);
761

762
	switch (algo) {
763
764
765
766
767
768
769
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
		return create_block_schedule_greedy(irg, execfreqs);
	case BLOCKSCHED_ILP:
		return create_block_schedule_ilp(irg, execfreqs);
	}

770
	panic("unknown blocksched algo");
771
}