beblocksched.c 16 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 "be.h"
Matthias Braun's avatar
Matthias Braun committed
44
#include "panic.h"
45

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

48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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) {
64
		if (!(arch_get_irn_flags(node) & arch_irn_flag_simple_jump))
65
66
67
68
69
70
71
72
73
74
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
			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;
		}
118
		panic("unexpected node %+F in block %+F with empty schedule", node, block);
119
120
	}

121
	ir_graph *irg = get_irn_irg(block);
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
151
152
153
154
155
156
157
	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);
	}
}

158
159
160
161
162
163
typedef struct blocksched_entry_t blocksched_entry_t;
struct blocksched_entry_t {
	ir_node            *block;
	blocksched_entry_t *next;
	blocksched_entry_t *prev;
};
164

165
166
typedef struct edge_t edge_t;
struct edge_t {
167
168
169
	ir_node *block;             /**< source block */
	int     pos;                /**< number of cfg predecessor (target) */
	double  execfreq;           /**< the frequency */
170
171
172
173
174
175
176
	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 */
};
177

178
179
typedef struct blocksched_env_t blocksched_env_t;
struct blocksched_env_t {
180
	ir_graph       *irg;
181
	struct obstack  obst;
182
183
184
	edge_t         *edges;
	pdeq           *worklist;
	int            blockcount;
185
};
186

187
188
189
190
191
static blocksched_entry_t* get_blocksched_entry(const ir_node *block)
{
	return (blocksched_entry_t*)get_irn_link(block);
}

192
193
194
195
/**
 * Collect cfg frequencies of all edges between blocks.
 * Also determines edge with highest frequency.
 */
196
197
static void collect_egde_frequency(ir_node *block, void *data)
{
Matthias Braun's avatar
Matthias Braun committed
198
	blocksched_env_t *env = (blocksched_env_t*)data;
199

Matthias Braun's avatar
Matthias Braun committed
200
	edge_t edge;
201
202
	memset(&edge, 0, sizeof(edge));

Matthias Braun's avatar
Matthias Braun committed
203
	blocksched_entry_t *entry = OALLOCZ(&env->obst, blocksched_entry_t);
204
205
206
	entry->block = block;
	set_irn_link(block, entry);

Matthias Braun's avatar
Matthias Braun committed
207
208
	ir_loop *loop  = get_irn_loop(block);
	int      arity = get_Block_n_cfgpreds(block);
209
	if (arity == 0) {
210
211
		/* must be the start block (or end-block for endless loops),
		 * everything else is dead code and should be removed by now */
212
213
		assert(block == get_irg_start_block(env->irg)
				|| block == get_irg_end_block(env->irg));
214
		/* nothing to do here */
215
216
		return;
	} else if (arity == 1) {
217
218
		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
		ir_loop *pred_loop  = get_irn_loop(pred_block);
219
		float    freq       = (float)get_block_execfreq(block);
220
221
222

		/* is it an edge leaving a loop */
		if (get_loop_depth(pred_loop) > get_loop_depth(loop)) {
223
			float pred_freq = (float)get_block_execfreq(pred_block);
224
225
226
			edge.outedge_penalty_freq = -(pred_freq - freq);
		}

227
228
		edge.block            = block;
		edge.pos              = 0;
229
		edge.execfreq         = freq;
230
231
232
		edge.highest_execfreq = 1;
		ARR_APP1(edge_t, env->edges, edge);
	} else {
233
		double highest_execfreq = -1.0;
234
		int    highest_edge_num = -1;
235
236

		edge.block = block;
Matthias Braun's avatar
Matthias Braun committed
237
		for (int i = 0; i < arity; ++i) {
238
			double  execfreq;
239
			ir_node *pred_block = get_Block_cfgpred_block(block, i);
240

241
			execfreq = get_block_execfreq(pred_block);
242

243
244
			edge.pos              = i;
			edge.execfreq         = execfreq;
245
246
			edge.highest_execfreq = 0;
			ARR_APP1(edge_t, env->edges, edge);
247
248

			if (execfreq > highest_execfreq) {
249
250
251
252
253
				highest_execfreq = execfreq;
				highest_edge_num = ARR_LEN(env->edges) - 1;
			}
		}

254
		if (highest_edge_num >= 0)
255
			env->edges[highest_edge_num].highest_execfreq = 1;
256
257
258
	}
}

259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
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;
		}
	}
}

278
279
static int cmp_edges(const void *d1, const void *d2)
{
280
281
	const edge_t *e1 = (const edge_t*)d1;
	const edge_t *e2 = (const edge_t*)d2;
282
283
284
285
286
287
288
289
290
	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);
	}
291
292
}

293
294
static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
{
295
296
297
298
299
300
301
302
303
304
305
	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);
	}
306
307
308
309
310
}

static void clear_loop_links(ir_loop *loop)
{
	set_loop_link(loop, NULL);
Matthias Braun's avatar
Matthias Braun committed
311
	for (int i = 0, n = get_loop_n_elements(loop); i < n; ++i) {
312
313
314
315
316
317
318
		loop_element elem = get_loop_element(loop, i);
		if (*elem.kind == k_ir_loop) {
			clear_loop_links(elem.son);
		}
	}
}

319
320
static void coalesce_blocks(blocksched_env_t *env)
{
321
	/* sort interblock edges by execution frequency */
Matthias Braun's avatar
Matthias Braun committed
322
	edge_t *edges = env->edges;
323
	QSORT_ARR(edges, cmp_edges);
324

325
	/* run1: only look at jumps */
Matthias Braun's avatar
Matthias Braun committed
326
327
	size_t edge_count = ARR_LEN(edges);
	for (size_t i = 0; i < edge_count; ++i) {
328
		const edge_t *edge  = &edges[i];
329
		ir_node      *block = edge->block;
330
		int           pos   = edge->pos;
331

332
333
		/* only check edge with highest frequency */
		if (! edge->highest_execfreq)
334
335
			continue;

336
337
338
339
		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, 0)))
			continue;

Matthias Braun's avatar
Matthias Braun committed
340
341
342
		ir_node *pred_block = get_Block_cfgpred_block(block, pos);
		blocksched_entry_t *entry      = get_blocksched_entry(block);
		blocksched_entry_t *pred_entry = get_blocksched_entry(pred_block);
343

344
		if (pred_entry->next != NULL || entry->prev != NULL)
345
			continue;
346
347
348

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

351
		/* schedule the 2 blocks behind each other */
352
		DB((dbg, LEVEL_1, "Coalesce (Jump) %+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
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

361
	QSORT_ARR(edges, cmp_edges_outedge_penalty);
Matthias Braun's avatar
Matthias Braun committed
362
	for (size_t i = 0; i < edge_count; ++i) {
363
		const edge_t *edge  = &edges[i];
364
		ir_node      *block = edge->block;
365
		int           pos   = edge->pos;
366
367
368
369

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

371
		/* the block might have been removed already... */
372
		if (is_Bad(get_Block_cfgpred(block, pos)))
373
374
			continue;

Matthias Braun's avatar
Matthias Braun committed
375
376
377
		ir_node *pred_block = get_Block_cfgpred_block(block, pos);
		blocksched_entry_t *entry      = get_blocksched_entry(block);
		blocksched_entry_t *pred_entry = get_blocksched_entry(pred_block);
378
379
380
381
382

		if (pred_entry->next != NULL || entry->prev != NULL)
			continue;

		/* we want at most 1 outedge fallthrough per loop */
Matthias Braun's avatar
Matthias Braun committed
383
		ir_loop *loop = get_irn_loop(pred_block);
384
385
386
387
388
389
390
391
392
393
		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 */
Matthias Braun's avatar
Matthias Braun committed
394
		ir_loop *outer_loop = get_irn_loop(block);
395
396
397
398
399
400
401
402
		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 */
403
	QSORT_ARR(edges, cmp_edges);
404
405

	/* run3: remaining edges */
Matthias Braun's avatar
Matthias Braun committed
406
	for (size_t i = 0; i < edge_count; ++i) {
407
408
409
410
411
412
		const edge_t *edge  = &edges[i];
		ir_node      *block = edge->block;
		int           pos   = edge->pos;

		/* the block might have been removed already... */
		if (is_Bad(get_Block_cfgpred(block, pos)))
413
414
			continue;

Matthias Braun's avatar
Matthias Braun committed
415
416
417
		ir_node *pred_block = get_Block_cfgpred_block(block, pos);
		blocksched_entry_t *entry      = get_blocksched_entry(block);
		blocksched_entry_t *pred_entry = get_blocksched_entry(pred_block);
418

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

423
		/* schedule the 2 blocks behind each other */
424
		DB((dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n",
425
		           pred_entry->block, entry->block, edge->execfreq));
426
		pred_entry->next = entry;
427
		entry->prev      = pred_entry;
428
429
430
431
432
	}
}

static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
{
Matthias Braun's avatar
Matthias Braun committed
433
	ir_node *block = entry->block;
434
	if (irn_visited_else_mark(block))
435
		return;
436

437
438
	env->blockcount++;

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

441
	/* put all successors into the worklist */
442
443
444
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

445
		if (irn_visited(succ_block))
446
447
			continue;

448
449
		/* we only need to put the first of a series of already connected
		 * blocks into the worklist */
Matthias Braun's avatar
Matthias Braun committed
450
		blocksched_entry_t *succ_entry = get_blocksched_entry(succ_block);
451
452
453
		while (succ_entry->prev != NULL) {
			/* break cycles... */
			if (succ_entry->prev->block == succ_block) {
454
				succ_entry->prev->next = NULL;
455
				succ_entry->prev       = NULL;
456
457
458
				break;
			}
			succ_entry = succ_entry->prev;
459
		}
460

461
		if (irn_visited(succ_entry->block))
462
463
			continue;

464
		DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
465
466
467
		pdeq_putr(env->worklist, succ_entry->block);
	}

468
	if (entry->next != NULL) {
469
470
471
472
		pick_block_successor(entry->next, env);
		return;
	}

473
	DB((dbg, LEVEL_1, "deciding...\n"));
Matthias Braun's avatar
Matthias Braun committed
474
	double best_succ_execfreq = -1;
475

476
	/* no successor yet: pick the successor block with the highest execution
477
478
	 * frequency which has no predecessor yet */

Matthias Braun's avatar
Matthias Braun committed
479
	ir_node *succ  = NULL;
480
481
482
	foreach_block_succ(block, edge) {
		ir_node *succ_block = get_edge_src_irn(edge);

483
		if (irn_visited(succ_block))
484
485
			continue;

Matthias Braun's avatar
Matthias Braun committed
486
		blocksched_entry_t *succ_entry = get_blocksched_entry(succ_block);
487
		if (succ_entry->prev != NULL)
488
489
			continue;

490
		double execfreq = get_block_execfreq(succ_block);
491
		if (execfreq > best_succ_execfreq) {
492
493
494
495
496
			best_succ_execfreq = execfreq;
			succ = succ_block;
		}
	}

497
	if (succ == NULL) {
498
		DB((dbg, LEVEL_1, "pick from worklist\n"));
499
500

		do {
501
			if (pdeq_empty(env->worklist)) {
502
				DB((dbg, LEVEL_1, "worklist empty\n"));
503
504
				return;
			}
505
			succ = (ir_node*)pdeq_getl(env->worklist);
506
		} while (irn_visited(succ));
507
508
	}

Matthias Braun's avatar
Matthias Braun committed
509
	blocksched_entry_t *succ_entry       = get_blocksched_entry(succ);
510
	entry->next      = succ_entry;
511
512
513
514
515
516
517
	succ_entry->prev = entry;

	pick_block_successor(succ_entry, env);
}

static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
{
518
519
	ir_graph           *irg        = env->irg;
	ir_node            *startblock = get_irg_start_block(irg);
Christoph Mallon's avatar
Christoph Mallon committed
520
	blocksched_entry_t *entry      = get_blocksched_entry(startblock);
521

522
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
523
524
525
526
527
528
529
	inc_irg_visited(irg);

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

530
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
531

532
533
534
	return entry;
}

Christoph Mallon's avatar
Christoph Mallon committed
535
static ir_node **create_blocksched_array(blocksched_env_t *const env)
536
{
537
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
538

Christoph Mallon's avatar
Christoph Mallon committed
539
540
541
542
543
544
	unsigned                  i          = 0;
	blocksched_entry_t *const first      = finish_block_schedule(env);
	unsigned            const count      = env->blockcount;
	struct obstack     *const obst       = be_get_be_obst(env->irg);
	ir_node           **const block_list = NEW_ARR_D(ir_node*, obst, count);
	for (blocksched_entry_t const *entry = first; entry; entry = entry->next) {
545
546
		assert(i < count);
		block_list[i++] = entry->block;
547
		DB((dbg, LEVEL_1, "\t%+F\n", entry->block));
548
549
550
551
552
553
	}
	assert(i == count);

	return block_list;
}

554
ir_node **be_create_block_schedule(ir_graph *irg)
555
{
Matthias Braun's avatar
Matthias Braun committed
556
	blocksched_env_t env;
557
558
559
	env.irg        = irg;
	env.edges      = NEW_ARR_F(edge_t, 0);
	env.worklist   = NULL;
560
	env.blockcount = 0;
561
	obstack_init(&env.obst);
562

563
	assure_loopinfo(irg);
564

565
	// collect edge execution frequencies
566
	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
567
568
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

569
	remove_empty_blocks(irg);
570

571
	coalesce_blocks(&env);
572

Christoph Mallon's avatar
Christoph Mallon committed
573
	ir_node **const block_list = create_blocksched_array(&env);
574
	ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
575
576

	DEL_ARR_F(env.edges);
577
	obstack_free(&env.obst, NULL);
578
579
580
581

	return block_list;
}

Matthias Braun's avatar
Matthias Braun committed
582
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
583
void be_init_blocksched(void)
584
{
Matthias Braun's avatar
Matthias Braun committed
585
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
586
}