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
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) {
65
		if (!(arch_get_irn_flags(node) & arch_irn_flag_simple_jump))
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
			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;
		}
119
		panic("unexpected node %+F in block %+F with empty schedule", node, block);
120
121
	}

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

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

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

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

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

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

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

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

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

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

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

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

242
			execfreq = get_block_execfreq(pred_block);
243

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

438
439
	env->blockcount++;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	pick_block_successor(succ_entry, env);
}

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

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

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

531
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
532

533
534
535
	return entry;
}

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

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

	return block_list;
}

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

565
	assure_loopinfo(irg);
566

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

570
	remove_empty_blocks(irg);
571

572
	coalesce_blocks(&env);
573

Matthias Braun's avatar
Matthias Braun committed
574
575
576
577
	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));
578
579

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

	return block_list;
}

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