beblocksched.c 20.3 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

#include "beblocksched.h"

#include <stdlib.h>

#include "array.h"
#include "pdeq.h"
44
#include "beirg.h"
45
46
#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
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
127
};
128

129
130
131
132
133
static blocksched_entry_t* get_blocksched_entry(const ir_node *block)
{
	return (blocksched_entry_t*)get_irn_link(block);
}

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

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

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

152
153
	loop = get_irn_loop(block);

154
	arity = get_Block_n_cfgpreds(block);
155

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

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

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

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

189
			execfreq = get_block_execfreq(pred_block);
190

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

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

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

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

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

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

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

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

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

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

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

291
292
293
294
295
		/* 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
296
297
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
298

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

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

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

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

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

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

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

334
		pred_block = get_Block_cfgpred_block(block, pos);
Christoph Mallon's avatar
Christoph Mallon committed
335
336
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
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
370
371
372
373

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

		pred_block = get_Block_cfgpred_block(block, pos);
Christoph Mallon's avatar
Christoph Mallon committed
377
378
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
379

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

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

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

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

402
403
	env->blockcount++;

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

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

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

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

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

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

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

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

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

444
445
446
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

447
		if (irn_visited(succ_block))
448
449
			continue;

Christoph Mallon's avatar
Christoph Mallon committed
450
		succ_entry = get_blocksched_entry(succ_block);
451
		if (succ_entry->prev != NULL)
452
453
			continue;

454
		double execfreq = get_block_execfreq(succ_block);
455
		if (execfreq > best_succ_execfreq) {
456
457
458
459
460
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

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

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

Christoph Mallon's avatar
Christoph Mallon committed
473
	succ_entry       = get_blocksched_entry(succ);
474
	entry->next      = succ_entry;
475
476
477
478
479
480
481
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
482
483
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
Christoph Mallon's avatar
Christoph Mallon committed
484
	blocksched_entry_t *entry      = get_blocksched_entry(startblock);
485

486
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
487
488
489
490
491
492
493
	inc_irg_visited(irg);

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

494
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
495

496
497
498
	return entry;
}

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

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

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

	return block_list;
}

520
static ir_node **create_block_schedule_greedy(ir_graph *irg)
521
{
522
	blocksched_env_t   env;
523
	blocksched_entry_t *start_entry;
524
	ir_node            **block_list;
525

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

532
	assure_loopinfo(irg);
533

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

537
	(void)be_remove_empty_blocks(irg);
538

539
	if (algo != BLOCKSCHED_NAIV)
540
541
542
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
543
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount,
544
	                                      be_get_be_obst(irg));
545
546

	DEL_ARR_F(env.edges);
547
	obstack_free(&env.obst, NULL);
548
549
550
551
552
553
554
555
556
557
558
559
560

	return block_list;
}

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

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

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

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

	int out_cst;
} blocksched_ilp_entry_t;

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

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

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

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

617
	if (block == startblock)
618
619
620
		return;

	arity = get_irn_arity(block);
621
	if (arity == 1) {
622
		double execfreq = get_block_execfreq(block);
623
		add_ilp_edge(block, 0, execfreq, env);
624
625
	}
	else {
626
		int i;
627
		int cst_idx;
628
629

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

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

638
			execfreq = get_block_execfreq(pred_block);
639
640
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
641
			lpp_set_factor_fast(env->lpp, cst_idx, edge->ilpvar, 1.0);
642
643
644
645
		}
	}
}

646
647
648
649
static blocksched_ilp_entry_t *get_blocksched_ilp_entry(const ir_node *block)
{
	return (blocksched_ilp_entry_t*)get_irn_link(block);
}
650
651
652

static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
Matthias Braun's avatar
Matthias Braun committed
653
654
	int           edge_count = ARR_LEN(env->ilpedges);
	int           i;
655
656

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

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

667
		pred  = get_Block_cfgpred_block(block, edge->pos);
668
		entry = get_blocksched_ilp_entry(pred);
669

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

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

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

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

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

695
		pred       = get_Block_cfgpred_block(block, edge->pos);
696
697
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred);
698
699

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

705
static ir_node **create_block_schedule_ilp(ir_graph *irg)
706
707
{
	blocksched_ilp_env_t env;
708
709
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
710

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

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

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

723
	(void)be_remove_empty_blocks(irg);
724
725
726
	coalesce_blocks_ilp(&env);

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

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

	return block_list;
}

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

751
	lc_opt_add_table(be_grp, be_blocksched_options);
752

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

756
ir_node **be_create_block_schedule(ir_graph *irg)
757
{
758
	switch (algo) {
759
760
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
761
		return create_block_schedule_greedy(irg);
762
	case BLOCKSCHED_ILP:
763
		return create_block_schedule_ilp(irg);
764
765
	}

766
	panic("unknown blocksched algo");
767
}