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 "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
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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
118
119
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;
		}
120
		panic("unexpected node %+F in block %+F with empty schedule", node, block);
121
122
	}

123
	ir_graph *irg = get_irn_irg(block);
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
158
159
	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);
	}
}

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

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

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

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

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

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

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

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

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

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

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

243
			execfreq = get_block_execfreq(pred_block);
244

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

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

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

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

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

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

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

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

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

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

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

Matthias Braun's avatar
Matthias Braun committed
342
343
344
		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);
345

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

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

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

360
361
362
	/* run2: pick loop fallthroughs */
	clear_loop_links(get_irg_loop(env->irg));

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

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

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

Matthias Braun's avatar
Matthias Braun committed
377
378
379
		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);
380
381
382
383
384

		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
385
		ir_loop *loop = get_irn_loop(pred_block);
386
387
388
389
390
391
392
393
394
395
		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
396
		ir_loop *outer_loop = get_irn_loop(block);
397
398
399
400
401
402
403
404
		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 */
405
	QSORT_ARR(edges, cmp_edges);
406
407

	/* run3: remaining edges */
Matthias Braun's avatar
Matthias Braun committed
408
	for (size_t i = 0; i < edge_count; ++i) {
409
410
411
412
413
414
		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)))
415
416
			continue;

Matthias Braun's avatar
Matthias Braun committed
417
418
419
		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);
420

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

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

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

439
440
	env->blockcount++;

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

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

447
		if (irn_visited(succ_block))
448
449
			continue;

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

463
		if (irn_visited(succ_entry->block))
464
465
			continue;

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

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

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

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

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

485
		if (irn_visited(succ_block))
486
487
			continue;

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

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

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

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

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

	pick_block_successor(succ_entry, env);
}

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

524
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
525
526
527
528
529
530
531
	inc_irg_visited(irg);

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

532
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
533

534
535
536
	return entry;
}

537
538
539
static ir_node **create_blocksched_array(blocksched_env_t *env,
                                         blocksched_entry_t *first,
                                         int count, struct obstack* obst)
540
{
Matthias Braun's avatar
Matthias Braun committed
541
542
	(void)env;
	ir_node **block_list = NEW_ARR_D(ir_node *, obst, count);
543
	DB((dbg, LEVEL_1, "Blockschedule:\n"));
544

Matthias Braun's avatar
Matthias Braun committed
545
546
547
	int i = 0;
	for (blocksched_entry_t *entry = first; entry != NULL;
	     entry = entry->next) {
548
549
		assert(i < count);
		block_list[i++] = entry->block;
550
		DB((dbg, LEVEL_1, "\t%+F\n", entry->block));
551
552
553
554
555
556
	}
	assert(i == count);

	return block_list;
}

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

566
	assure_loopinfo(irg);
567

568
569
570
	// collect edge execution frequencies
	irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);

571
	remove_empty_blocks(irg);
572

573
	coalesce_blocks(&env);
574

Matthias Braun's avatar
Matthias Braun committed
575
576
577
578
	blocksched_entry_t *start_entry = finish_block_schedule(&env);
	ir_node           **block_list
		= create_blocksched_array(&env, start_entry, env.blockcount,
		                          be_get_be_obst(irg));
579
580

	DEL_ARR_F(env.edges);
581
	obstack_free(&env.obst, NULL);
582
583
584
585

	return block_list;
}

Matthias Braun's avatar
Matthias Braun committed
586
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
587
void be_init_blocksched(void)
588
{
Matthias Braun's avatar
Matthias Braun committed
589
	FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
590
}