beblocksched.c 22.5 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Christian Würdig's avatar
Christian Würdig committed
6
7
8
9
10
/**
 * @file
 * @brief       Block-scheduling strategies.
 * @author      Matthias Braun, Christoph Mallon
 * @date        27.09.2006
11
12
13
14
15
16
17
18
19
20
 *
 * 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
21
22
23
24
25
 */
#include "beblocksched.h"

#include <stdlib.h>

Matthias Braun's avatar
Matthias Braun committed
26
#include "util.h"
27
28
#include "array.h"
#include "pdeq.h"
29
#include "beirg.h"
30
31
#include "iredges.h"
#include "irgwalk.h"
Michael Beck's avatar
Michael Beck committed
32
#include "irnode_t.h"
33
#include "irgraph_t.h"
34
#include "irgmod.h"
35
#include "irloop.h"
Michael Beck's avatar
Michael Beck committed
36
#include "execfreq.h"
37
#include "irdump_t.h"
38
39
#include "irtools.h"
#include "debug.h"
40
#include "bearch.h"
41
#include "bemodule.h"
42
#include "besched.h"
43
#include "beutil.h"
44
#include "be.h"
Matthias Braun's avatar
Matthias Braun committed
45
#include "panic.h"
46

Matthias Braun's avatar
Matthias Braun committed
47
48
#include "lc_opts.h"
#include "lc_opts_enum.h"
49

50
51
#include "lpp.h"
#include "lpp_net.h"
52

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

55
typedef enum blocksched_algos_t {
56
	BLOCKSCHED_NAIV, BLOCKSCHED_GREEDY, BLOCKSCHED_ILP
57
58
59
60
61
} blocksched_algos_t;

static int algo = BLOCKSCHED_GREEDY;

static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
62
	{ "naiv",   BLOCKSCHED_NAIV },
63
64
65
66
67
68
69
70
71
72
	{ "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[] = {
73
	LC_OPT_ENT_ENUM_INT ("blockscheduler", "the block scheduling algorithm", &algo_var),
74
	LC_OPT_LAST
75
76
};

77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
static bool blocks_removed;

/**
 * Post-block-walker: Find blocks containing only one jump and
 * remove them.
 */
static void remove_empty_block(ir_node *block)
{
	if (irn_visited_else_mark(block))
		return;

	if (get_Block_n_cfgpreds(block) != 1)
		goto check_preds;

	ir_node *jump = NULL;
	sched_foreach(block, node) {
		if (!is_Jmp(node)
		    && !(arch_get_irn_flags(node) & arch_irn_flag_simple_jump))
			goto check_preds;
		if (jump != NULL) {
			/* we should never have 2 jumps in a block */
			panic("found 2 jumps in a block");
		}
		jump = node;
	}
	if (jump == NULL)
		goto check_preds;

	ir_entity *entity     = get_Block_entity(block);
	ir_node   *pred       = get_Block_cfgpred(block, 0);
	ir_node   *succ_block = NULL;
	foreach_out_edge_safe(jump, edge) {
		int pos = get_edge_src_pos(edge);

		assert(succ_block == NULL);
		succ_block = get_edge_src_irn(edge);
		if (get_Block_entity(succ_block) != NULL && entity != NULL) {
			/* Currently we can add only one label for a block. Therefore we
			 * cannot combine them if both block already have one. :-( */
			goto check_preds;
		}

		set_irn_n(succ_block, pos, pred);
	}

	/* move the label to the successor block */
	set_Block_entity(succ_block, entity);

	/* there can be some non-scheduled Pin nodes left in the block, move them
	 * to the succ block (Pin) or pred block (Sync) */
	foreach_out_edge_safe(block, edge) {
		ir_node *const node = get_edge_src_irn(edge);

		if (node == jump)
			continue;
		/* we simply kill Pins, because there are some strange interactions
		 * between jump threading, which produce PhiMs with Pins, we simply
		 * kill the pins here, everything is scheduled anyway */
		if (is_Pin(node)) {
			exchange(node, get_Pin_op(node));
			continue;
		}
		if (is_Sync(node)) {
			set_nodes_block(node, get_nodes_block(pred));
			continue;
		}
		if (is_End(node)) { /* End-keep, reroute it to the successor */
			int pos = get_edge_src_pos(edge);
			set_irn_n(node, pos, succ_block);
			continue;
		}
		panic("Unexpected node %+F in block %+F with empty schedule", node, block);
	}

151
	ir_graph *irg = get_irn_irg(block);
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
	set_Block_cfgpred(block, 0, new_r_Bad(irg, mode_X));
	kill_node(jump);
	blocks_removed = true;

	/* check predecessor */
	remove_empty_block(get_nodes_block(pred));
	return;

check_preds:
	for (int i = 0, arity = get_Block_n_cfgpreds(block); i < arity; ++i) {
		ir_node *pred = get_Block_cfgpred_block(block, i);
		remove_empty_block(pred);
	}
}

/* removes basic blocks that just contain a jump instruction */
static void remove_empty_blocks(ir_graph *irg)
{
	blocks_removed = false;

	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
	inc_irg_visited(irg);
	remove_empty_block(get_irg_end_block(irg));
	foreach_irn_in(get_irg_end(irg), i, pred) {
		if (!is_Block(pred))
			continue;
		remove_empty_block(pred);
	}
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);

	if (blocks_removed) {
		/* invalidate analysis info */
		clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
	}
}

188
189
190
191
192
193
194
195
196
/*
 *   ____                   _
 *  / ___|_ __ ___  ___  __| |_   _
 * | |  _| '__/ _ \/ _ \/ _` | | | |
 * | |_| | | |  __/  __/ (_| | |_| |
 *  \____|_|  \___|\___|\__,_|\__, |
 *                            |___/
 */

197
198
199
200
201
202
typedef struct blocksched_entry_t blocksched_entry_t;
struct blocksched_entry_t {
	ir_node            *block;
	blocksched_entry_t *next;
	blocksched_entry_t *prev;
};
203

204
205
typedef struct edge_t edge_t;
struct edge_t {
206
207
208
	ir_node *block;             /**< source block */
	int     pos;                /**< number of cfg predecessor (target) */
	double  execfreq;           /**< the frequency */
209
210
211
212
213
214
215
	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 */
};
216

217
218
typedef struct blocksched_env_t blocksched_env_t;
struct blocksched_env_t {
219
	ir_graph       *irg;
220
	struct obstack  obst;
221
222
223
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
224
};
225

226
227
228
229
230
static blocksched_entry_t* get_blocksched_entry(const ir_node *block)
{
	return (blocksched_entry_t*)get_irn_link(block);
}

231
232
233
234
/**
 * Collect cfg frequencies of all edges between blocks.
 * Also determines edge with highest frequency.
 */
235
236
static void collect_egde_frequency(ir_node *block, void *data)
{
237
	blocksched_env_t   *env = (blocksched_env_t*)data;
238
239
	int                arity;
	edge_t             edge;
240
	blocksched_entry_t *entry;
241
	ir_loop            *loop;
242

243
244
	memset(&edge, 0, sizeof(edge));

245
	entry = OALLOCZ(&env->obst, blocksched_entry_t);
246
247
248
	entry->block = block;
	set_irn_link(block, entry);

249
250
	loop = get_irn_loop(block);

251
	arity = get_Block_n_cfgpreds(block);
252

253
	if (arity == 0) {
254
255
		/* must be the start block (or end-block for endless loops),
		 * everything else is dead code and should be removed by now */
256
257
		assert(block == get_irg_start_block(env->irg)
				|| block == get_irg_end_block(env->irg));
258
		/* nothing to do here */
259
260
		return;
	} else if (arity == 1) {
261
262
		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
		ir_loop *pred_loop  = get_irn_loop(pred_block);
263
		float    freq       = (float)get_block_execfreq(block);
264
265
266

		/* is it an edge leaving a loop */
		if (get_loop_depth(pred_loop) > get_loop_depth(loop)) {
267
			float pred_freq = (float)get_block_execfreq(pred_block);
268
269
270
			edge.outedge_penalty_freq = -(pred_freq - freq);
		}

271
272
		edge.block            = block;
		edge.pos              = 0;
273
		edge.execfreq         = freq;
274
275
276
		edge.highest_execfreq = 1;
		ARR_APP1(edge_t, env->edges, edge);
	} else {
277
		int    i;
278
		double highest_execfreq = -1.0;
279
		int    highest_edge_num = -1;
280
281

		edge.block = block;
282
283
		for (i = 0; i < arity; ++i) {
			double  execfreq;
284
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
285

286
			execfreq = get_block_execfreq(pred_block);
287

288
289
			edge.pos              = i;
			edge.execfreq         = execfreq;
290
291
			edge.highest_execfreq = 0;
			ARR_APP1(edge_t, env->edges, edge);
292
293

			if (execfreq > highest_execfreq) {
294
295
296
297
298
				highest_execfreq = execfreq;
				highest_edge_num = ARR_LEN(env->edges) - 1;
			}
		}

299
		if (highest_edge_num >= 0)
300
			env->edges[highest_edge_num].highest_execfreq = 1;
301
302
303
	}
}

304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
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;
		}
	}
}

323
324
static int cmp_edges(const void *d1, const void *d2)
{
325
326
	const edge_t *e1 = (const edge_t*)d1;
	const edge_t *e2 = (const edge_t*)d2;
327
328
329
330
331
332
333
334
335
	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);
	}
336
337
}

338
339
static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
{
340
341
342
343
344
345
346
347
348
349
350
	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);
	}
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
}

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

367
368
369
370
static void coalesce_blocks(blocksched_env_t *env)
{
	int i;
	int edge_count = ARR_LEN(env->edges);
371
372
373
	edge_t *edges = env->edges;

	/* sort interblock edges by execution frequency */
374
	QSORT_ARR(edges, cmp_edges);
375

376
377
	/* run1: only look at jumps */
	for (i = 0; i < edge_count; ++i) {
378
		const edge_t *edge  = &edges[i];
379
		ir_node      *block = edge->block;
380
		int           pos   = edge->pos;
381
		ir_node      *pred_block;
382
383
		blocksched_entry_t *entry, *pred_entry;

384
385
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
386
387
			continue;

388
389
390
391
392
		/* 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
393
394
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
395

396
		if (pred_entry->next != NULL || entry->prev != NULL)
397
			continue;
398
399
400

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

403
		/* schedule the 2 blocks behind each other */
404
		DB((dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n",
405
		           pred_entry->block, entry->block, edge->execfreq));
406
		pred_entry->next = entry;
407
		entry->prev      = pred_entry;
408
409
	}

410
411
412
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

413
	QSORT_ARR(edges, cmp_edges_outedge_penalty);
414
	for (i = 0; i < edge_count; ++i) {
415
		const edge_t *edge  = &edges[i];
416
		ir_node      *block = edge->block;
417
		int           pos   = edge->pos;
418
		ir_node      *pred_block;
419
		blocksched_entry_t *entry, *pred_entry;
420
421
422
423
424
425
		ir_loop      *loop;
		ir_loop      *outer_loop;

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

427
		/* the block might have been removed already... */
428
		if (is_Bad(get_Block_cfgpred(block, pos)))
429
430
			continue;

431
		pred_block = get_Block_cfgpred_block(block, pos);
Christoph Mallon's avatar
Christoph Mallon committed
432
433
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458

		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 */
459
	QSORT_ARR(edges, cmp_edges);
460
461
462
463
464
465
466
467
468
469
470

	/* 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)))
471
472
473
			continue;

		pred_block = get_Block_cfgpred_block(block, pos);
Christoph Mallon's avatar
Christoph Mallon committed
474
475
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred_block);
476

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

481
		/* schedule the 2 blocks behind each other */
482
		DB((dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n",
483
		           pred_entry->block, entry->block, edge->execfreq));
484
		pred_entry->next = entry;
485
		entry->prev      = pred_entry;
486
487
488
489
490
	}
}

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
491
492
	ir_node            *block = entry->block;
	ir_node            *succ  = NULL;
493
	blocksched_entry_t *succ_entry;
494
	double              best_succ_execfreq;
495

496
	if (irn_visited_else_mark(block))
497
		return;
498

499
500
	env->blockcount++;

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

503
	/* put all successors into the worklist */
504
505
506
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

507
		if (irn_visited(succ_block))
508
509
			continue;

510
511
		/* we only need to put the first of a series of already connected
		 * blocks into the worklist */
Christoph Mallon's avatar
Christoph Mallon committed
512
		succ_entry = get_blocksched_entry(succ_block);
513
514
515
		while (succ_entry->prev != NULL) {
			/* break cycles... */
			if (succ_entry->prev->block == succ_block) {
516
				succ_entry->prev->next = NULL;
517
				succ_entry->prev       = NULL;
518
519
520
				break;
			}
			succ_entry = succ_entry->prev;
521
		}
522

523
		if (irn_visited(succ_entry->block))
524
525
			continue;

526
		DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
527
528
529
		pdeq_putr(env->worklist, succ_entry->block);
	}

530
	if (entry->next != NULL) {
531
532
533
534
		pick_block_successor(entry->next, env);
		return;
	}

535
	DB((dbg, LEVEL_1, "deciding...\n"));
536
	best_succ_execfreq = -1;
537

538
	/* no successor yet: pick the successor block with the highest execution
539
540
	 * frequency which has no predecessor yet */

541
542
543
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

544
		if (irn_visited(succ_block))
545
546
			continue;

Christoph Mallon's avatar
Christoph Mallon committed
547
		succ_entry = get_blocksched_entry(succ_block);
548
		if (succ_entry->prev != NULL)
549
550
			continue;

551
		double execfreq = get_block_execfreq(succ_block);
552
		if (execfreq > best_succ_execfreq) {
553
554
555
556
557
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

558
	if (succ == NULL) {
559
		DB((dbg, LEVEL_1, "pick from worklist\n"));
560
561

		do {
562
			if (pdeq_empty(env->worklist)) {
563
				DB((dbg, LEVEL_1, "worklist empty\n"));
564
565
				return;
			}
566
			succ = (ir_node*)pdeq_getl(env->worklist);
567
		} while (irn_visited(succ));
568
569
	}

Christoph Mallon's avatar
Christoph Mallon committed
570
	succ_entry       = get_blocksched_entry(succ);
571
	entry->next      = succ_entry;
572
573
574
575
576
577
578
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
579
580
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
Christoph Mallon's avatar
Christoph Mallon committed
581
	blocksched_entry_t *entry      = get_blocksched_entry(startblock);
582

583
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
584
585
586
587
588
589
590
	inc_irg_visited(irg);

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

591
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
592

593
594
595
	return entry;
}

596
597
598
599
600
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;
601
	blocksched_entry_t *entry;
602
	(void) env;
603
604

	block_list = NEW_ARR_D(ir_node *, obst, count);
605
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
606
607

	for (entry = first; entry != NULL; entry = entry->next) {
608
609
		assert(i < count);
		block_list[i++] = entry->block;
610
		DB((dbg, LEVEL_1, "\t%+F\n", entry->block));
611
612
613
614
615
616
	}
	assert(i == count);

	return block_list;
}

617
static ir_node **create_block_schedule_greedy(ir_graph *irg)
618
{
619
	blocksched_env_t   env;
620
	blocksched_entry_t *start_entry;
621
	ir_node            **block_list;
622

623
624
625
	env.irg        = irg;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
626
	env.blockcount = 0;
627
	obstack_init(&env.obst);
628

629
	assure_loopinfo(irg);
630

631
632
633
	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

634
	remove_empty_blocks(irg);
635

636
	if (algo != BLOCKSCHED_NAIV)
637
638
639
		coalesce_blocks(&env);

	start_entry = finish_block_schedule(&env);
640
	block_list  = create_blocksched_array(&env, start_entry, env.blockcount,
641
	                                      be_get_be_obst(irg));
642
643

	DEL_ARR_F(env.edges);
644
	obstack_free(&env.obst, NULL);
645
646
647
648
649
650
651
652
653
654
655
656
657

	return block_list;
}

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

658
typedef struct ilp_edge_t {
659
660
661
	ir_node *block;   /**< source block */
	int     pos;      /**< number of cfg predecessor (target) */
	int     ilpvar;
662
663
} ilp_edge_t;

664
typedef struct blocksched_ilp_env_t {
665
	blocksched_env_t env;
666
667
	ilp_edge_t       *ilpedges;
	lpp_t            *lpp;
668
669
} blocksched_ilp_env_t;

670
typedef struct blocksched_ilp_entry_t {
671
	ir_node *block;
672
	int      out_cst;
673
674
675
676
} blocksched_ilp_entry_t;

static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
{
677
	char       name[64];
678
	ilp_edge_t edge;
679
	int        edgeidx = ARR_LEN(env->ilpedges);
680
681
682

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

683
684
	edge.block  = block;
	edge.pos    = pos;
685
686
687
688
689
690
691
692
	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)
{
693
	blocksched_ilp_env_t *env        = (blocksched_ilp_env_t*)data;
694
695
696
697
698
	ir_graph             *irg        = env->env.irg;
	ir_node              *startblock = get_irg_start_block(irg);
	int                  arity;
	char                 name[64];
	int                  out_count;
699
700
701
702
703
	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);

704
	entry          = OALLOC(&env->env.obst, blocksched_ilp_entry_t);
705
	entry->block   = block;
706
	entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, out_count - 1);
707
708
	set_irn_link(block, entry);

709
	if (block == startblock)
710
711
712
		return;

	arity = get_irn_arity(block);
713
	if (arity == 1) {
714
		double execfreq = get_block_execfreq(block);
715
		add_ilp_edge(block, 0, execfreq, env);
716
	} else {
717
		int i;
718
		int cst_idx;
719
720

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

723
724
725
		for (i = 0; i < arity; ++i) {
			double     execfreq;
			int        edgenum;
726
			ilp_edge_t *edge;
727
			ir_node    *pred_block = get_Block_cfgpred_block(block, i);
728

729
			execfreq = get_block_execfreq(pred_block);
730
731
			edgenum  = add_ilp_edge(block, i, execfreq, env);
			edge     = &env->ilpedges[edgenum];
732
			lpp_set_factor_fast(env->lpp, cst_idx, edge->ilpvar, 1.0);
733
734
735
736
		}
	}
}

737
738
739
740
static blocksched_ilp_entry_t *get_blocksched_ilp_entry(const ir_node *block)
{
	return (blocksched_ilp_entry_t*)get_irn_link(block);
}
741
742
743

static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
Matthias Braun's avatar
Matthias Braun committed
744
745
	int           edge_count = ARR_LEN(env->ilpedges);
	int           i;
746
747

	/* complete out constraints */
748
	for (i = 0; i < edge_count; ++i) {
749
750
751
		const ilp_edge_t *edge  = &env->ilpedges[i];
		ir_node          *block = edge->block;
		ir_node          *pred;
752
753
		blocksched_ilp_entry_t *entry;

754
755
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
756
757
			continue;

758
		pred  = get_Block_cfgpred_block(block, edge->pos);
759
		entry = get_blocksched_ilp_entry(pred);
760

761
		DB((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
762
				  pred, block, edge->pos));
763
764
765
		lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
	}

766
	lpp_solve_net(env->lpp, be_options.ilp_server, be_options.ilp_solver);
767
768
769
	assert(lpp_is_sol_valid(env->lpp));

	/* Apply results to edges */
770
771
772
773
774
	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;
775
776
777
		blocksched_entry_t *entry;
		blocksched_entry_t *pred_entry;

778
779
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
780
781
			continue;

782
		is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
783
		if (is_jump)
784
785
			continue;

786
		pred       = get_Block_cfgpred_block(block, edge->pos);
787
788
		entry      = get_blocksched_entry(block);
		pred_entry = get_blocksched_entry(pred);
789
790

		assert(entry->prev == NULL && pred_entry->next == NULL);
791
		entry->prev      = pred_entry;
792
793
794
795
		pred_entry->next = entry;
	}
}

796
static ir_node **create_block_schedule_ilp(ir_graph *irg)
797
798
{
	blocksched_ilp_env_t env;
799
800
	blocksched_entry_t   *start_entry;
	ir_node              **block_list;
801

802
803
	env.env.irg        = irg;
	env.env.worklist   = NULL;
804
	env.env.blockcount = 0;
805
	env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
806
	obstack_init(&env.env.obst);
807

808
	env.lpp = lpp_new("blockschedule", lpp_minimize);
809
810
811
812
813
	lpp_set_time_limit(env.lpp, 20);
	lpp_set_log(env.lpp, stdout);

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

814
	remove_empty_blocks(irg);
815
816
817
	coalesce_blocks_ilp(&env);

	start_entry = finish_block_schedule(&env.env);
818
819
	block_list  = create_blocksched_array(&env.env, start_entry,
	                                      env.env.blockcount,
820
	                                      be_get_be_obst(irg));
821
822

	DEL_ARR_F(env.ilpedges);
823
	lpp_free(env.lpp);
824
	obstack_free(&env.env.obst, NULL);
825
826
827
828
829
830
831
832
833
834
835
836

	return block_list;
}

/*
 *  __  __       _
 * |  \/  | __ _(_)_ __
 * | |\/| |/ _` | | '_ \
 * | |  | | (_| | | | | |
 * |_|  |_|\__,_|_|_| |_|
 *
 */
Matthias Braun's avatar
Matthias Braun committed
837
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
838
void be_init_blocksched(void)
839
{
840
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
841

842
	lc_opt_add_table(be_grp, be_blocksched_options);
843

Matthias Braun's avatar
Matthias Braun committed
844
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
845
}
846

847
ir_node **be_create_block_schedule(ir_graph *irg)
848
{
849
	switch (algo) {
850
851
	case BLOCKSCHED_GREEDY:
	case BLOCKSCHED_NAIV:
852
		return create_block_schedule_greedy(irg);
853
	case BLOCKSCHED_ILP:
854
		return create_block_schedule_ilp(irg);
855
856
	}

857
	panic("unknown blocksched algo");
858
}