beblocksched.c 20.4 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
	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
523
	blocksched_env_t   env;
	struct obstack     obst;
524
	blocksched_entry_t *start_entry;
525
	ir_node            **block_list;
526
527
528

	obstack_init(&obst);

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

535
	assure_loopinfo(irg);
536

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

540
	(void)be_remove_empty_blocks(irg);
541

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

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

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

	return block_list;
}

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

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

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

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

	int out_cst;
} blocksched_ilp_entry_t;

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

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

592
593
	edge.block  = block;
	edge.pos    = pos;
594
595
596
597
598
599
600
601
	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)
{
602
	blocksched_ilp_env_t *env        = (blocksched_ilp_env_t*)data;
603
604
605
606
607
	ir_graph             *irg        = env->env.irg;
	ir_node              *startblock = get_irg_start_block(irg);
	int                  arity;
	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
		double execfreq = get_block_execfreq(block);
626
		add_ilp_edge(block, 0, execfreq, env);
627
628
	}
	else {
629
		int i;
630
		int cst_idx;
631
632

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

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

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

649
650
651
652
static blocksched_ilp_entry_t *get_blocksched_ilp_entry(const ir_node *block)
{
	return (blocksched_ilp_entry_t*)get_irn_link(block);
}
653
654
655

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

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

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

670
		pred  = get_Block_cfgpred_block(block, edge->pos);
671
		entry = get_blocksched_ilp_entry(pred);
672

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

678
	lpp_solve_net(env->lpp, be_options.ilp_server, be_options.ilp_solver);
679
680
681
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
682
683
684
685
686
	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;
687
688
689
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

690
691
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
692
693
			continue;

694
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
695
		if (is_jump)
696
697
			continue;

698
		pred       = get_Block_cfgpred_block(block, edge->pos);
699
700
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred);
701
702

		assert(entry->prev == NULL && pred_entry->next == NULL);
703
		entry->prev      = pred_entry;
704
705
706
707
		pred_entry->next = entry;
	}
}

708
static ir_node **create_block_schedule_ilp(ir_graph *irg)
709
710
{
	blocksched_ilp_env_t env;
711
712
713
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
714
715
716

	obstack_init(&obst);

717
718
719
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.worklist   = NULL;
720
	env.env.blockcount = 0;
721
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
722

723
	env.lpp = lpp_new("blockschedule", lpp_minimize);
724
725
726
727
728
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

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

729
	(void)be_remove_empty_blocks(irg);
730
731
732
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
733
734
	block_list  = create_blocksched_array(&env.env, start_entry,
	                                      env.env.blockcount,
735
	                                      be_get_be_obst(irg));
736
737

	DEL_ARR_F(env.ilpedges);
738
	lpp_free(env.lpp);
739
740
741
742
743
744
745
746
747
748
749
750
751
	obstack_free(&obst, NULL);

	return block_list;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
Matthias Braun's avatar
Matthias Braun committed
752
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
753
void be_init_blocksched(void)
754
{
755
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
756

757
	lc_opt_add_table(be_grp, be_blocksched_options);
758

Matthias Braun's avatar
Matthias Braun committed
759
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
760
}
761

762
ir_node **be_create_block_schedule(ir_graph *irg)
763
{
764
	switch (algo) {
765
766
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
767
		return create_block_schedule_greedy(irg);
768
	case BLOCKSCHED_ILP:
769
		return create_block_schedule_ilp(irg);
770
771
	}

772
	panic("unknown blocksched algo");
773
}