beblocksched.c 20.2 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
25
/**
 * @file
 * @brief       Block-scheduling strategies.
 * @author      Matthias Braun, Christoph Mallon
 * @date        27.09.2006
 * @version     $Id$
26
27
28
29
30
31
32
33
34
35
 *
 * 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
36
 */
37
#include "config.h"
38
39
40
41
42
43
44
45
46
47

#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
48
#include "irnode_t.h"
49
50
51
#include "irgraph_t.h"
#include "irloop.h"
#include "irprintf.h"
Michael Beck's avatar
Michael Beck committed
52
#include "execfreq.h"
53
#include "irdump_t.h"
54
55
#include "irtools.h"
#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
66
#ifdef WITH_ILP
#include <lpp/lpp.h>
#include <lpp/lpp_net.h>
Christian Würdig's avatar
Christian Würdig committed
67
#endif /* WITH_ILP */
68

Matthias Braun's avatar
Matthias Braun committed
69
70
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

71
typedef enum _blocksched_algos_t {
72
	BLOCKSCHED_NAIV, BLOCKSCHED_GREEDY, BLOCKSCHED_ILP
73
74
75
76
77
78
79
80
81
} blocksched_algos_t;

static int algo = BLOCKSCHED_GREEDY;

static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
	{ "naiv",	BLOCKSCHED_NAIV },
	{ "greedy", BLOCKSCHED_GREEDY },
#ifdef WITH_ILP
	{ "ilp",    BLOCKSCHED_ILP },
Christian Würdig's avatar
Christian Würdig committed
82
#endif /* WITH_ILP */
83
84
85
86
87
88
89
90
	{ NULL,     0 }
};

static lc_opt_enum_int_var_t algo_var = {
	&algo, blockschedalgo_items
};

static const lc_opt_table_entry_t be_blocksched_options[] = {
Christian Würdig's avatar
Christian Würdig committed
91
	LC_OPT_ENT_ENUM_INT ("algo", "the block scheduling algorithm", &algo_var),
92
	LC_OPT_LAST
93
94
95
96
97
98
99
100
101
102
103
};

/*
 *   ____                   _
 *  / ___|_ __ ___  ___  __| |_   _
 * | |  _| '__/ _ \/ _ \/ _` | | | |
 * | |_| | | |  __/  __/ (_| | |_| |
 *  \____|_|  \___|\___|\__,_|\__, |
 *                            |___/
 */

104
105
106
107
108
109
typedef struct blocksched_entry_t blocksched_entry_t;
struct blocksched_entry_t {
	ir_node            *block;
	blocksched_entry_t *next;
	blocksched_entry_t *prev;
};
110

111
112
typedef struct edge_t edge_t;
struct edge_t {
113
114
115
	ir_node *block;             /**< source block */
	int     pos;                /**< number of cfg predecessor (target) */
	double  execfreq;           /**< the frequency */
116
117
118
119
120
121
122
	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 */
};
123

124
125
typedef struct blocksched_env_t blocksched_env_t;
struct blocksched_env_t {
126
	ir_graph       *irg;
127
	struct obstack *obst;
128
129
130
131
	ir_exec_freq   *execfreqs;
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
132
};
133

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 = data;
141
142
	int                arity;
	edge_t             edge;
143
	blocksched_entry_t *entry;
144
	ir_loop            *loop;
145

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

	entry = obstack_alloc(env->obst, sizeof(entry[0]));
	memset(entry, 0, sizeof(*entry));
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
167
168
169
170
171
172
173
174
		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
		ir_loop *pred_loop  = get_irn_loop(pred_block);
		float    freq       = get_block_execfreq(env->execfreqs, block);

		/* is it an edge leaving a loop */
		if (get_loop_depth(pred_loop) > get_loop_depth(loop)) {
			float pred_freq = get_block_execfreq(env->execfreqs, pred_block);
			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
204
		if(highest_edge_num >= 0)
			env->edges[highest_edge_num].highest_execfreq = 1;
205
206
207
208
209
210
211
	}
}

static int cmp_edges(const void *d1, const void *d2)
{
	const edge_t *e1 = d1;
	const edge_t *e2 = d2;
212
213

	return QSORT_CMP(e2->execfreq, e1->execfreq);
214
215
}

216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
{
	const edge_t *e1 = d1;
	const edge_t *e2 = d2;
	/* reverse sorting as penalties are negative */
	return QSORT_CMP(e1->outedge_penalty_freq, e2->outedge_penalty_freq);
}

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

238
239
240
241
static void coalesce_blocks(blocksched_env_t *env)
{
	int i;
	int edge_count = ARR_LEN(env->edges);
242
243
244
245
	edge_t *edges = env->edges;

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

247
248
	/* run1: only look at jumps */
	for (i = 0; i < edge_count; ++i) {
249
		const edge_t *edge  = &edges[i];
250
		ir_node      *block = edge->block;
251
		int           pos   = edge->pos;
252
		ir_node      *pred_block;
253
254
		blocksched_entry_t *entry, *pred_entry;

255
256
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
257
258
			continue;

259
260
261
262
263
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
264
		entry      = get_irn_link(block);
265
266
		pred_entry = get_irn_link(pred_block);

267
		if (pred_entry->next != NULL || entry->prev != NULL)
268
			continue;
269
270
271

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

274
		/* schedule the 2 blocks behind each other */
275
		DB((dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n",
276
		           pred_entry->block, entry->block, edge->execfreq));
277
		pred_entry->next = entry;
278
		entry->prev      = pred_entry;
279
280
	}

281
282
283
284
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

	qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_edges_outedge_penalty);
285
	for (i = 0; i < edge_count; ++i) {
286
		const edge_t *edge  = &edges[i];
287
		ir_node      *block = edge->block;
288
		int           pos   = edge->pos;
289
		ir_node      *pred_block;
290
		blocksched_entry_t *entry, *pred_entry;
291
292
293
294
295
296
		ir_loop      *loop;
		ir_loop      *outer_loop;

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

298
		/* the block might have been removed already... */
299
		if (is_Bad(get_Block_cfgpred(block, pos)))
300
301
			continue;

302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
		pred_block = get_Block_cfgpred_block(block, pos);
		entry      = get_irn_link(block);
		pred_entry = get_irn_link(pred_block);

		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)))
342
343
344
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
345
		entry      = get_irn_link(block);
346
347
		pred_entry = get_irn_link(pred_block);

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

352
		/* schedule the 2 blocks behind each other */
353
		DB((dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n",
354
		           pred_entry->block, entry->block, edge->execfreq));
355
		pred_entry->next = entry;
356
		entry->prev      = pred_entry;
357
358
359
360
361
	}
}

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
362
363
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
364
	blocksched_entry_t *succ_entry;
365
366
	const ir_edge_t    *edge;
	double             best_succ_execfreq;
367

368
	if (irn_visited_else_mark(block))
369
		return;
370

371
372
	env->blockcount++;

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

375
	/* put all successors into the worklist */
376
377
378
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

379
		if (irn_visited(succ_block))
380
381
			continue;

382
383
		/* we only need to put the first of a series of already connected
		 * blocks into the worklist */
384
		succ_entry = get_irn_link(succ_block);
385
386
387
		while (succ_entry->prev != NULL) {
			/* break cycles... */
			if (succ_entry->prev->block == succ_block) {
388
				succ_entry->prev->next = NULL;
389
				succ_entry->prev       = NULL;
390
391
392
393
394
				break;
			}
			succ_entry = succ_entry->prev;
		};

395
		if (irn_visited(succ_entry->block))
396
397
			continue;

398
		DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
399
400
401
		pdeq_putr(env->worklist, succ_entry->block);
	}

402
	if (entry->next != NULL) {
403
404
405
406
		pick_block_successor(entry->next, env);
		return;
	}

407
	DB((dbg, LEVEL_1, "deciding...\n"));
408
	best_succ_execfreq = -1;
409

410
	/* no successor yet: pick the successor block with the highest execution
411
412
	 * frequency which has no predecessor yet */

413
414
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);
415
		double  execfreq;
416

417
		if (irn_visited(succ_block))
418
419
420
			continue;

		succ_entry = get_irn_link(succ_block);
421
		if (succ_entry->prev != NULL)
422
423
			continue;

Michael Beck's avatar
Michael Beck committed
424
		execfreq = get_block_execfreq(env->execfreqs, succ_block);
425
		if (execfreq > best_succ_execfreq) {
426
427
428
429
430
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

431
	if (succ == NULL) {
432
		DB((dbg, LEVEL_1, "pick from worklist\n"));
433
434

		do {
435
			if (pdeq_empty(env->worklist)) {
436
				DB((dbg, LEVEL_1, "worklist empty\n"));
437
438
439
				return;
			}
			succ = pdeq_getl(env->worklist);
440
		} while (irn_visited(succ));
441
442
	}

443
444
	succ_entry       = get_irn_link(succ);
	entry->next      = succ_entry;
445
446
447
448
449
450
451
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
452
453
454
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
	blocksched_entry_t *entry      = get_irn_link(startblock);
455

456
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
457
458
459
460
461
462
463
	inc_irg_visited(irg);

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

464
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
465

466
467
468
	return entry;
}

469
470
471
472
473
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;
474
	blocksched_entry_t *entry;
475
	(void) env;
476
477

	block_list = NEW_ARR_D(ir_node *, obst, count);
478
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
479
480

	for (entry = first; entry != NULL; entry = entry->next) {
481
482
		assert(i < count);
		block_list[i++] = entry->block;
483
		DB((dbg, LEVEL_1, "\t%+F\n", entry->block));
484
485
486
487
488
489
490
491
	}
	assert(i == count);

	return block_list;
}

static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execfreqs)
{
492
493
	blocksched_env_t   env;
	struct obstack     obst;
494
	blocksched_entry_t *start_entry;
495
	ir_node            **block_list;
496
497
498

	obstack_init(&obst);

499
500
501
502
503
	env.irg        = irg;
	env.obst       = &obst;
	env.execfreqs  = execfreqs;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
504
505
	env.blockcount = 0;

506
507
508
509
510
	/* make sure loopinfo is up-to-date */
	if (! (get_irg_loopinfo_state(irg) & loopinfo_cf_consistent)) {
		construct_cf_backedges(irg);
	}

511
512
513
	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

514
	(void)be_remove_empty_blocks(irg);
515

516
	if (algo != BLOCKSCHED_NAIV)
517
518
519
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
520
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount, get_irg_obstack(irg));
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538

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

	return block_list;
}

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

#ifdef WITH_ILP
typedef struct _ilp_edge_t {
539
540
541
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
542
543
544
545
} ilp_edge_t;

typedef struct _blocksched_ilp_env_t {
	blocksched_env_t env;
546
547
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
548
549
550
551
552
553
554
555
556
557
558
559
} blocksched_ilp_env_t;

typedef struct _blocksched_ilp_entry_t {
	ir_node *block;
	struct _blocksched_entry_t *next;
	struct _blocksched_entry_t *prev;

	int out_cst;
} blocksched_ilp_entry_t;

static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
{
560
	char       name[64];
561
	ilp_edge_t edge;
562
	int        edgeidx = ARR_LEN(env->ilpedges);
563
564
565

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

566
567
	edge.block  = block;
	edge.pos    = pos;
568
569
570
571
572
573
574
575
	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)
{
576
577
578
579
580
581
582
	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;
583
584
585
586
587
	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);

588
589
590
591
	entry          = obstack_alloc(env->env.obst, sizeof(entry[0]));
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
592
593
594
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, out_count - 1);
	set_irn_link(block, entry);

595
	if (block == startblock)
596
597
598
		return;

	arity = get_irn_arity(block);
599
	if (arity == 1) {
600
601
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
602
603
	}
	else {
604
605
606
607
608
		int i;

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

609
610
611
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
612
			ilp_edge_t *edge;
613
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
614
615

			execfreq = get_block_execfreq(env->env.execfreqs, pred_block);
616
617
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
618
619
620
621
622
623
624
625
			lpp_set_factor_fast(env->lpp, cst, edge->ilpvar, 1.0);
		}
	}
}


static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
626
627
	int  i;
	int  edge_count = ARR_LEN(env->ilpedges);
628
629
630

	/* complete out constraints */
	for(i = 0; i < edge_count; ++i) {
631
632
633
		const ilp_edge_t *edge  = &env->ilpedges[i];
		ir_node          *block = edge->block;
		ir_node          *pred;
634
635
		blocksched_ilp_entry_t *entry;

636
637
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
638
639
			continue;

640
		pred  = get_Block_cfgpred_block(block, edge->pos);
641
642
		entry = get_irn_link(pred);

643
		DB((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
644
				  pred, block, edge->pos));
645
646
647
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

648
649
650
651
652
653
654
655
656
657
658
659
#if 0
	{
		FILE *f;
		char fname[256];
		lpp_dump(env->lpp, "lpp.out");
		snprintf(fname, sizeof(fname), "lpp_%s.plain", get_irg_dump_name(env->env.irg));
		f = fopen(fname, "w");
		lpp_dump_plain(env->lpp, f);
		fclose(f);
	}
#endif

660
661
662
663
664
	//lpp_solve_net(env->lpp, main_env->options->ilp_server, main_env->options->ilp_solver);
	lpp_solve_net(env->lpp, "i44pc52", "cplex");
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
665
666
667
668
669
	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;
670
671
672
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

673
674
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
675
676
			continue;

677
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
678
		if (is_jump)
679
680
			continue;

681
682
		pred       = get_Block_cfgpred_block(block, edge->pos);
		entry      = get_irn_link(block);
683
684
685
		pred_entry = get_irn_link(pred);

		assert(entry->prev == NULL && pred_entry->next == NULL);
686
		entry->prev      = pred_entry;
687
688
689
690
691
692
693
		pred_entry->next = entry;
	}
}

static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
{
	blocksched_ilp_env_t env;
694
695
696
	struct obstack       obst;
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
697
698
699

	obstack_init(&obst);

700
701
702
703
	env.env.irg        = irg;
	env.env.obst       = &obst;
	env.env.execfreqs  = execfreqs;
	env.env.worklist   = NULL;
704
	env.env.blockcount = 0;
705
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
706
707
708
709
710
711
712

	env.lpp = new_lpp("blockschedule", lpp_minimize);
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

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

713
	(void)be_remove_empty_blocks(irg);
714
715
716
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
717
	block_list  = create_blocksched_array(&env.env, start_entry, env.env.blockcount, get_irg_obstack(irg));
718
719
720
721
722
723
724

	DEL_ARR_F(env.ilpedges);
	free_lpp(env.lpp);
	obstack_free(&obst, NULL);

	return block_list;
}
Christian Würdig's avatar
Christian Würdig committed
725
#endif /* WITH_ILP */
726
727
728
729
730
731
732
733
734

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
735
void be_init_blocksched(void)
736
{
737
738
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_entry_t *blocksched_grp = lc_opt_get_grp(be_grp, "blocksched");
739
740

	lc_opt_add_table(blocksched_grp, be_blocksched_options);
741

Matthias Braun's avatar
Matthias Braun committed
742
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
743
}
744
745

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched);
746
747
748
749
750
751
752
753
754
755

ir_node **be_create_block_schedule(ir_graph *irg, ir_exec_freq *execfreqs)
{
	switch(algo) {
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
		return create_block_schedule_greedy(irg, execfreqs);
#ifdef WITH_ILP
	case BLOCKSCHED_ILP:
		return create_block_schedule_ilp(irg, execfreqs);
Christian Würdig's avatar
Christian Würdig committed
756
#endif /* WITH_ILP */
757
758
	}

759
	panic("unknown blocksched algo");
760
761
	return NULL;
}