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
	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
166
167
168
169
170
171
172
173
		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);
		}

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
190
			execfreq = get_block_execfreq(env->execfreqs, pred_block);

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
203
		if(highest_edge_num >= 0)
			env->edges[highest_edge_num].highest_execfreq = 1;
204
205
206
207
208
209
210
	}
}

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

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

215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
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);
		}
	}
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

370
371
	env->blockcount++;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	pick_block_successor(succ_entry, env);
}

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

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

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

463
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
464

465
466
467
	return entry;
}

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

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

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

	return block_list;
}

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

	obstack_init(&obst);

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

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

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

513
	(void)be_remove_empty_blocks(irg);
514

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

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

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

	return block_list;
}

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

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

typedef struct _blocksched_ilp_env_t {
	blocksched_env_t env;
545
546
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
547
548
549
550
551
552
553
554
555
556
557
558
} 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)
{
559
	char       name[64];
560
	ilp_edge_t edge;
561
	int        edgeidx = ARR_LEN(env->ilpedges);
562
563
564

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

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

587
	entry          = OALLOC(env->env.obst, blocksched_ilp_entry_t);
588
589
590
	entry->block   = block;
	entry->next    = NULL;
	entry->prev    = NULL;
591
592
593
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, out_count - 1);
	set_irn_link(block, entry);

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

	arity = get_irn_arity(block);
598
	if (arity == 1) {
599
600
		double execfreq = get_block_execfreq(env->env.execfreqs, block);
		add_ilp_edge(block, 0, execfreq, env);
601
602
	}
	else {
603
604
605
606
607
		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);

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

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


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

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

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

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

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

647
648
649
650
651
652
653
654
655
656
657
658
#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

659
660
661
662
663
	//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 */
664
665
666
667
668
	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;
669
670
671
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

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

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

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

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

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

	obstack_init(&obst);

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

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

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

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

	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
724
#endif /* WITH_ILP */
725
726
727
728
729
730
731
732
733

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
734
void be_init_blocksched(void)
735
{
736
737
	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");
738
739

	lc_opt_add_table(blocksched_grp, be_blocksched_options);
740

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

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

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
755
#endif /* WITH_ILP */
756
757
	}

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