code_placement.c 11.4 KB
Newer Older
Michael Beck's avatar
Michael Beck committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Michael Beck's avatar
Michael Beck committed
4
5
6
7
 */

/**
 * @file
8
9
 * @brief    Move nodes to a block where they will be executed the least
 *           often.
Michael Beck's avatar
Michael Beck committed
10
11
 * @author   Christian Schaefer, Goetz Lindenmaier, Sebastian Felis,
 *           Michael Beck
12
13
14
15
 *
 * The idea here is to push nodes as deep into the dominance tree as their
 * dependencies allow. After pushing them back up out of as many loops as
 * possible.
Michael Beck's avatar
Michael Beck committed
16
 */
17
18
#include <stdbool.h>

19
#include "iroptimize.h"
Michael Beck's avatar
Michael Beck committed
20
21
#include "adt/pdeq.h"
#include "irnode_t.h"
22
#include "iredges_t.h"
Michael Beck's avatar
Michael Beck committed
23
24
#include "irgopt.h"

yb9976's avatar
yb9976 committed
25
#ifndef NDEBUG
26
static bool is_block_reachable(ir_node *block)
27
{
28
29
	return get_Block_dom_depth(block) >= 0;
}
yb9976's avatar
yb9976 committed
30
#endif
31

Michael Beck's avatar
Michael Beck committed
32
33
34
35
36
/**
 * Find the earliest correct block for node n.  --- Place n into the
 * same Block as its dominance-deepest Input.
 *
 * move_out_of_loops() expects that place_floats_early() have placed
yb9976's avatar
yb9976 committed
37
 * all "living" nodes into a living block. That is why we must
Michael Beck's avatar
Michael Beck committed
38
39
 * move nodes in dead block with "live" successors into a valid
 * block.
40
 * We move them just into the same block as its successor (or
Michael Beck's avatar
Michael Beck committed
41
42
43
44
 * in case of a Phi into the effective use block). For Phi successors,
 * this may still be a dead block, but then there is no real use, as
 * the control flow will be dead later.
 */
45
46
static void place_floats_early(ir_node *n, waitq *worklist)
{
Michael Beck's avatar
Michael Beck committed
47
	/* we must not run into an infinite loop */
48
49
50
51
52
53
54
55
56
	if (irn_visited_else_mark(n))
		return;

	/* The algorithm relies on the fact that all predecessors of a block are
	 * moved up after a call to place_float_early of the predecessors
	 * (see the loop below).
	 * However we have to break cycles somewhere. Relying on the visited flag
	 * will result in nodes not being moved up despite their place_floats_early
	 * call.
yb9976's avatar
yb9976 committed
57
	 * Instead we break cycles at pinned nodes which will not move anyway:
58
59
	 * This works because in firm each cycle contains a Phi or Block node
	 * (which are pinned)
Michael Beck's avatar
Michael Beck committed
60
	 */
61
	if (get_irn_pinned(n) != op_pin_state_floats || only_used_by_keepalive(n)) {
yb9976's avatar
yb9976 committed
62
		/* we cannot move pinned nodes */
63
		foreach_irn_in(n, i, pred) {
64
			pdeq_putr(worklist, pred);
Michael Beck's avatar
Michael Beck committed
65
		}
66
67
68
69
		if (!is_Block(n))
			pdeq_putr(worklist, get_nodes_block(n));
		return;
	}
Michael Beck's avatar
Michael Beck committed
70

yb9976's avatar
yb9976 committed
71
	ir_node *block = get_nodes_block(n);
72
73
74

	/* first move predecessors up */
	place_floats_early(block, worklist);
75
	foreach_irn_in(n, i, pred) {
76
77
		place_floats_early(pred, worklist);
	}
Michael Beck's avatar
Michael Beck committed
78

79
	/* determine earliest point */
yb9976's avatar
yb9976 committed
80
81
	ir_node *new_block = NULL;
	int      new_depth = 0;
82
	foreach_irn_in(n, i, pred) {
83
84
85
86
87
		ir_node *pred_block = get_nodes_block(pred);
		int      pred_depth = get_Block_dom_depth(pred_block);
		if (pred_depth > new_depth) {
			new_depth = pred_depth;
			new_block = pred_block;
Michael Beck's avatar
Michael Beck committed
88
89
		}
	}
90
91

	/* avoid moving nodes into the start block if we are not in the backend */
yb9976's avatar
yb9976 committed
92
93
	ir_graph *irg         = get_irn_irg(n);
	ir_node  *start_block = get_irg_start_block(irg);
94
	if (new_block == start_block && block != start_block &&
95
		!irg_is_constrained(irg, IR_GRAPH_CONSTRAINT_BACKEND)) {
96
97
98
		assert(get_irn_n_edges_kind(start_block, EDGE_KIND_BLOCK) == 1);
		const ir_edge_t *edge = get_block_succ_first(start_block);
		new_block = get_edge_src_irn(edge);
99
100
101
102
103
	}

	/* Set the new block */
	if (new_block != NULL)
		set_nodes_block(n, new_block);
Michael Beck's avatar
Michael Beck committed
104
105
106
107
}

/**
 * Floating nodes form subgraphs that begin at nodes as Const, Load,
108
109
110
111
 * Start, Call and that end at op_pin_state_pinned nodes as Store, Call.
 * Place_early places all floating nodes reachable from its argument through
 * floating nodes and adds all beginnings at op_pin_state_pinned nodes to the
 * worklist.
Michael Beck's avatar
Michael Beck committed
112
113
114
 *
 * @param worklist   a worklist, used for the algorithm, empty on in/output
 */
115
static void place_early(ir_graph *irg, waitq *worklist)
116
{
Michael Beck's avatar
Michael Beck committed
117
	assert(worklist);
118
	inc_irg_visited(irg);
Michael Beck's avatar
Michael Beck committed
119

yb9976's avatar
yb9976 committed
120
	/* this initializes the worklist */
121
	place_floats_early(get_irg_end(irg), worklist);
Michael Beck's avatar
Michael Beck committed
122
123
124

	/* Work the content of the worklist. */
	while (!waitq_empty(worklist)) {
125
		ir_node *n = (ir_node*)waitq_get(worklist);
126
		if (!irn_visited(n))
Michael Beck's avatar
Michael Beck committed
127
128
			place_floats_early(n, worklist);
	}
129
	set_irg_pinned(irg, op_pin_state_pinned);
Michael Beck's avatar
Michael Beck committed
130
131
132
}

/**
133
134
135
136
137
138
139
 * Compute the deepest common dominator tree ancestor of block and dca.
 *
 * @param dca    the deepest common dominator tree ancestor so far,
 *               might be NULL
 * @param block  a block
 *
 * @return  the deepest common dominator tree ancestor of block and dca
Michael Beck's avatar
Michael Beck committed
140
 */
141
142
143
static ir_node *calc_dom_dca(ir_node *dca, ir_node *block)
{
	assert(block != NULL);
Michael Beck's avatar
Michael Beck committed
144
145

	/* We found a first legal placement. */
146
147
	if (!dca)
		return block;
Michael Beck's avatar
Michael Beck committed
148
149
150
151
152
153
154
155
156
157

	/* Find a placement that is dominates both, dca and block. */
	while (get_Block_dom_depth(block) > get_Block_dom_depth(dca))
		block = get_Block_idom(block);

	while (get_Block_dom_depth(dca) > get_Block_dom_depth(block)) {
		dca = get_Block_idom(dca);
	}

	while (block != dca) {
yb9976's avatar
yb9976 committed
158
159
		block = get_Block_idom(block);
		dca   = get_Block_idom(dca);
Michael Beck's avatar
Michael Beck committed
160
161
162
163
	}
	return dca;
}

164
165
/**
 * Deepest common dominance ancestor of DCA and CONSUMER of PRODUCER.
Michael Beck's avatar
Michael Beck committed
166
167
168
 * I.e., DCA is the block where we might place PRODUCER.
 * A data flow edge points from producer to consumer.
 */
169
170
static ir_node *consumer_dom_dca(ir_node *dca, ir_node *consumer,
                                 ir_node *producer)
Michael Beck's avatar
Michael Beck committed
171
172
173
174
175
176
177
178
179
{
	/* Compute the last block into which we can place a node so that it is
	   before consumer. */
	if (is_Phi(consumer)) {
		/* our consumer is a Phi-node, the effective use is in all those
		   blocks through which the Phi-node reaches producer */
		ir_node *phi_block = get_nodes_block(consumer);
		int      arity     = get_irn_arity(consumer);

yb9976's avatar
yb9976 committed
180
		for (int i = 0;  i < arity; i++) {
Michael Beck's avatar
Michael Beck committed
181
182
			if (get_Phi_pred(consumer, i) == producer) {
				ir_node *new_block = get_Block_cfgpred_block(phi_block, i);
183
				if (new_block == NULL)
184
					continue;
Michael Beck's avatar
Michael Beck committed
185

Andreas Zwinkau's avatar
Andreas Zwinkau committed
186
187
				assert(is_block_reachable(new_block));
				dca = calc_dom_dca(dca, new_block);
Michael Beck's avatar
Michael Beck committed
188
189
190
			}
		}
	} else {
191
		dca = calc_dom_dca(dca, get_nodes_block(consumer));
Michael Beck's avatar
Michael Beck committed
192
193
194
195
	}
	return dca;
}

196
197
static inline int get_block_loop_depth(ir_node *block)
{
Michael Beck's avatar
Michael Beck committed
198
	return get_loop_depth(get_irn_loop(block));
Michael Beck's avatar
Michael Beck committed
199
200
201
}

/**
202
 * Move n to a block with less loop depth than its current block. The
Michael Beck's avatar
Michael Beck committed
203
204
205
206
207
 * new block must be dominated by early.
 *
 * @param n      the node that should be moved
 * @param early  the earliest block we can n move to
 */
208
209
static void move_out_of_loops(ir_node *n, ir_node *early)
{
210
211
212
	ir_node *block      = get_nodes_block(n);
	ir_node *best       = block;
	int      best_depth = get_block_loop_depth(best);
Michael Beck's avatar
Michael Beck committed
213
214
215
216

	/* Find the region deepest in the dominator tree dominating
	   dca with the least loop nesting depth, but still dominated
	   by our early placement. */
217
218
219
220
221
222
	while (block != early) {
		ir_node *idom       = get_Block_idom(block);
		int      idom_depth = get_block_loop_depth(idom);
		if (idom_depth < best_depth) {
			best       = idom;
			best_depth = idom_depth;
Michael Beck's avatar
Michael Beck committed
223
		}
224
		block = idom;
Michael Beck's avatar
Michael Beck committed
225
	}
226
	if (best != get_nodes_block(n))
Michael Beck's avatar
Michael Beck committed
227
228
229
		set_nodes_block(n, best);
}

230
231
232
233
234
235
236
237
238
239
/**
 * Calculate the deepest common ancestor in the dominator tree of all nodes'
 * blocks depending on node; our final placement has to dominate DCA.
 *
 * @param node  the definition node
 * @param dca   the deepest common ancestor block so far, initially
 *              NULL
 *
 * @return the deepest common dominator ancestor of all blocks of node's users
 */
240
241
static ir_node *get_deepest_common_dom_ancestor(ir_node *node, ir_node *dca)
{
242
243
	foreach_out_edge(node, edge) {
		ir_node *succ = get_edge_src_irn(edge);
Michael Beck's avatar
Michael Beck committed
244

yb9976's avatar
yb9976 committed
245
		/* keepalive edges are special and do not respect the dominance */
246
		if (is_End(succ))
Michael Beck's avatar
Michael Beck committed
247
248
249
			continue;

		if (is_Proj(succ)) {
250
251
252
			/* Proj nodes are in the same block as node, so
			 * the users of Proj are our users. */
			dca = get_deepest_common_dom_ancestor(succ, dca);
Michael Beck's avatar
Michael Beck committed
253
		} else {
Andreas Zwinkau's avatar
Andreas Zwinkau committed
254
			assert(is_block_reachable(get_nodes_block(succ)));
Michael Beck's avatar
Michael Beck committed
255
256
257
			dca = consumer_dom_dca(dca, succ, node);
		}
	}
258
259
260
261
262
263
264
	/* respect the keepalive rule: if our only user is a keepalive, then we must
	 * not move the node any further */
	if (dca == NULL) {
		assert(only_used_by_keepalive(node));
		return get_nodes_block(node);
	}

265
266
267
268
269
	foreach_out_edge_kind(node, edge, EDGE_KIND_DEP) {
		ir_node *succ = get_edge_src_irn(edge);
		assert(is_block_reachable(get_nodes_block(succ)));
		dca = consumer_dom_dca(dca, succ, node);
	}
Michael Beck's avatar
Michael Beck committed
270
271
272
	return dca;
}

Michael Beck's avatar
Michael Beck committed
273
274
275
276
277
278
/**
 * Put all the Proj nodes of a node into a given block.
 *
 * @param node   the mode_T node
 * @param block  the block to put the Proj nodes to
 */
279
280
static void set_projs_block(ir_node *node, ir_node *block)
{
281
282
	foreach_out_edge(node, edge) {
		ir_node *succ = get_edge_src_irn(edge);
Michael Beck's avatar
Michael Beck committed
283

284
285
		if (!is_Proj(succ))
			continue;
Michael Beck's avatar
Michael Beck committed
286

287
		set_nodes_block(succ, block);
Michael Beck's avatar
Michael Beck committed
288
		if (get_irn_mode(succ) == mode_T) {
Michael Beck's avatar
Michael Beck committed
289
290
291
292
293
294
295
296
297
298
299
300
301
			set_projs_block(succ, block);
		}
	}
}

/**
 * Find the latest legal block for N and place N into the
 * `optimal' Block between the latest and earliest legal block.
 * The `optimal' block is the dominance-deepest block of those
 * with the least loop-nesting-depth.  This places N out of as many
 * loops as possible and then makes it as control dependent as
 * possible.
 */
302
303
static void place_floats_late(ir_node *n, pdeq *worklist)
{
304
305
306
307
308
	if (irn_visited_else_mark(n))
		return;

	/* break cycles at pinned nodes (see place place_floats_early) as to why */
	if (get_irn_pinned(n) != op_pin_state_floats) {
309
310
		foreach_out_edge(n, edge) {
			ir_node *succ = get_edge_src_irn(edge);
311
			pdeq_putr(worklist, succ);
Michael Beck's avatar
Michael Beck committed
312
		}
313
		return;
Michael Beck's avatar
Michael Beck committed
314
315
	}

316
	/* place our users */
317
318
	foreach_out_edge(n, edge) {
		ir_node *succ = get_edge_src_irn(edge);
319
320
321
322
323
324
		place_floats_late(succ, worklist);
	}

	/* no point in moving Projs around, they are moved with their predecessor */
	if (is_Proj(n))
		return;
yb9976's avatar
yb9976 committed
325
	/* some nodes should simply stay in the start block */
326
	if (is_irn_start_block_placed(n)) {
Christoph Mallon's avatar
Christoph Mallon committed
327
		assert(get_nodes_block(n) == get_irg_start_block(get_irn_irg(n)));
328
329
330
		return;
	}

yb9976's avatar
yb9976 committed
331
	ir_node *block = get_nodes_block(n);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
332
	assert(is_block_reachable(block));
333
334
335
336

	/* deepest common ancestor in the dominator tree of all nodes'
	   blocks depending on us; our final placement has to dominate
	   DCA. */
yb9976's avatar
yb9976 committed
337
338
339
340
341
342
	ir_node *dca = get_deepest_common_dom_ancestor(n, NULL);
	assert(dca != NULL);
	set_nodes_block(n, dca);
	move_out_of_loops(n, block);
	if (get_irn_mode(n) == mode_T) {
		set_projs_block(n, get_nodes_block(n));
Michael Beck's avatar
Michael Beck committed
343
344
345
346
347
348
349
350
351
	}
}

/**
 * Place floating nodes on the given worklist as late as possible using
 * the dominance tree.
 *
 * @param worklist   the worklist containing the nodes to place
 */
352
static void place_late(ir_graph *irg, waitq *worklist)
353
{
Michael Beck's avatar
Michael Beck committed
354
	assert(worklist);
355
	inc_irg_visited(irg);
Michael Beck's avatar
Michael Beck committed
356
357

	/* This fills the worklist initially. */
358
	place_floats_late(get_irg_start_block(irg), worklist);
Michael Beck's avatar
Michael Beck committed
359
360
361

	/* And now empty the worklist again... */
	while (!waitq_empty(worklist)) {
362
		ir_node *n = (ir_node*)waitq_get(worklist);
363
		if (!irn_visited(n))
Michael Beck's avatar
Michael Beck committed
364
365
366
367
			place_floats_late(n, worklist);
	}
}

368
/* Code Placement. */
369
void place_code(ir_graph *irg)
370
{
Michael Beck's avatar
Michael Beck committed
371
	/* Handle graph state */
372
373
374
	assure_irg_properties(irg,
		IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES |
		IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE |
375
		IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES |
376
377
		IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE |
		IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
Michael Beck's avatar
Michael Beck committed
378
379
380

	/* Place all floating nodes as early as possible. This guarantees
	 a legal code placement. */
yb9976's avatar
yb9976 committed
381
	waitq *worklist = new_waitq();
382
	place_early(irg, worklist);
Michael Beck's avatar
Michael Beck committed
383

Andreas Zwinkau's avatar
Andreas Zwinkau committed
384
385
386
	/* While GCSE might place nodes in unreachable blocks,
	 * these are now placed in reachable blocks. */

387
388
	/* Note: place_early changes only blocks, no data edges. So, the
	 * data out edges are still valid, no need to recalculate them here. */
Michael Beck's avatar
Michael Beck committed
389
390
391

	/* Now move the nodes down in the dominator tree. This reduces the
	   unnecessary executions of the node. */
392
	place_late(irg, worklist);
Michael Beck's avatar
Michael Beck committed
393
394

	del_waitq(worklist);
395
	confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_CONTROL_FLOW);
Michael Beck's avatar
Michael Beck committed
396
}