3 * File name: ir/opt/cfopt.c
4 * Purpose: control flow optimizations
8 * Copyright: (c) 1998-2004 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
20 #include "irgraph_t.h"
33 #include "irbackedge_t.h"
40 /*------------------------------------------------------------------*/
41 /* Control flow optimization. */
43 /* Removes Bad control flow predecessors and empty blocks. A block */
44 /* is empty if it contains only a Jmp node. */
45 /* Blocks can only be removed if they are not needed for the */
46 /* semantics of Phi nodes. */
47 /*------------------------------------------------------------------*/
50 * Removes Tuples from Block control flow predecessors.
51 * Optimizes blocks with equivalent_node(). This is tricky,
52 * as we want to avoid nodes that have as block predecessor Bads.
53 * Therefore we also optimize at control flow operations, depending
54 * how we first reach the Block.
56 static void merge_blocks(ir_node *n, void *env) {
60 /* clear the link field for ALL nodes first */
61 set_irn_link(n, NULL);
63 if (get_irn_op(n) == op_Block) {
65 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
66 /* GL @@@ : is this possible? if (get_opt_normalize()) -- added, all tests go through.
67 A different order of optimizations might cause problems. */
68 if (get_opt_normalize())
69 set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i)));
73 new_block = equivalent_node(n);
74 if (new_block != n && ! is_Bad(new_block))
75 exchange (n, new_block);
77 } else if (get_opt_optimize() && (get_irn_mode(n) == mode_X)) {
78 /* We will soon visit a block. Optimize it before visiting! */
79 ir_node *b = get_nodes_block(skip_Proj(n));
82 new_block = equivalent_node(b);
84 while (irn_not_visited(b) && (!is_Bad(new_block)) && (new_block != b)) {
85 /* We would have to run gigo if new is bad, so we
86 promote it directly below. Nevertheless, we sometimes reach a block
87 the first time through a dataflow node. In this case we optimized the
88 block as such and have to promote the Bad here. */
89 assert((get_opt_control_flow_straightening() ||
90 get_opt_control_flow_weak_simplification()) &&
91 ("strange flag setting"));
92 exchange (b, new_block);
94 new_block = equivalent_node(b);
97 /* normally, we would create a Bad block here, but this must be
98 * prevented, so just set it's cf to Bad.
100 if (is_Bad(new_block))
101 exchange(n, new_Bad());
107 * Remove cf from dead block by inspecting dominance info
108 * Do not replace blocks by Bad. This optimization shall
109 * ensure, that all Bad cfg preds are removed, and no new
110 * other Bads are introduced.
112 * Must be run in the post walker.
114 static void remove_dead_block_cf(ir_node *block, void *env)
118 /* check block predecessors and turn control flow into bad */
119 for (i = 0, n = get_Block_n_cfgpreds(block); i < n; ++i) {
120 ir_node *pred_X = get_Block_cfgpred(block, i);
122 if (! is_Bad(pred_X)) {
123 ir_node *pred_bl = get_nodes_block(skip_Proj(pred_X));
125 if (is_Bad(pred_bl) || (get_Block_dom_depth(pred_bl) == -1))
126 exchange (pred_X, new_Bad());
132 * Collects all Phi nodes in link list of Block.
133 * Marks all blocks "block_visited" if they contain a node other
135 * Replaces n by Bad if n is unreachable control flow. We do that
136 * in the post walker, so we catch all blocks.
138 static void collect_nodes(ir_node *n, void *env) {
139 if (is_no_Block(n)) {
140 ir_node *b = get_nodes_block(n);
142 if ((get_irn_op(n) == op_Phi)) {
143 /* Collect Phi nodes to compact ins along with block's ins. */
144 set_irn_link(n, get_irn_link(b));
147 else if ((get_irn_op(n) != op_Jmp) && !is_Bad(b)) { /* Check for non empty block. */
148 mark_Block_block_visited(b);
153 /** Returns true if pred is predecessor of block. */
154 static int is_pred_of(ir_node *pred, ir_node *b) {
157 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
158 ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
159 if (b_pred == pred) return 1;
165 /** Test wether we can optimize away pred block pos of b.
167 * @param b A block node.
168 * @param pos The position of the predecessor block to judge about.
170 * @returns The number of predecessors
172 * The test is rather tricky.
174 * The situation is something like the following:
182 * b merges the control flow of an if-then-else. We may not remove
183 * the 'then' _and_ the 'else' block of an 'if' if there is a Phi
184 * node in b, even if both are empty. The destruction of this Phi
185 * requires that a copy is added before the merge. We have to
186 * keep one of the case blocks to place the copies in.
188 * To perform the test for pos, we must regard preds before pos
189 * as already removed.
191 static int test_whether_dispensable(ir_node *b, int pos) {
192 int i, j, n_preds = 1;
194 ir_node *cfop = get_Block_cfgpred(b, pos);
195 ir_node *pred = get_nodes_block(cfop);
197 /* Bad blocks will be optimized away, so we don't need space for them */
201 if (get_Block_block_visited(pred) + 1
202 < get_irg_block_visited(current_ir_graph)) {
204 if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
205 /* Mark block so that is will not be removed: optimization is turned off. */
206 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
210 /* Seems to be empty. At least we detected this in collect_nodes. */
211 if (!get_irn_link(b)) {
212 /* There are no Phi nodes ==> all predecessors are dispensable. */
213 n_preds = get_Block_n_cfgpreds(pred);
215 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
216 Work preds < pos as if they were already removed. */
217 for (i = 0; i < pos; i++) {
218 ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
219 if (get_Block_block_visited(b_pred) + 1
220 < get_irg_block_visited(current_ir_graph)) {
221 for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
222 ir_node *b_pred_pred = get_nodes_block(get_Block_cfgpred(b_pred, j));
223 if (is_pred_of(b_pred_pred, pred)) dispensable = 0;
226 if (is_pred_of(b_pred, pred)) dispensable = 0;
229 for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
230 ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
231 if (is_pred_of(b_pred, pred)) dispensable = 0;
234 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
237 n_preds = get_Block_n_cfgpreds(pred);
247 * This method removed Bad cf preds from Blocks and Phis, and removes
248 * empty blocks. A block is empty if it only contains Phi and Jmp nodes.
250 * We first adapt Phi nodes, then Block nodes, as we need the old ins
251 * of the Block to adapt the Phi nodes. We do this by computing new
252 * in arrays, and then replacing the old ones. So far we compute new in arrays
253 * for all nodes, not regarding whether there is a possibility for optimization.
255 * For each predecessor p of a Block b there are three cases:
256 * 1. The predecessor p is a Bad node: just skip it. The in array of b shrinks by one.
257 * 2. The predecessor p is empty. Remove p. All predecessors of p are now
259 * 3. The predecessor p is a block containing useful code. Just keep p as is.
261 * For Phi nodes f we have to check the conditions at the Block of f.
262 * For cases 1 and 3 we proceed as for Blocks. For case 2 we can have two
264 * 2a: The old precessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED. In this
265 * case we proceed as for blocks. We remove pred_f. All
266 * predecessors of pred_f now are predecessors of f.
267 * 2b: The old predecessor of f is NOT in the block removed. It might be a Phi, too.
268 * We have to replicate f for each predecessor of the removed block. Or, with
269 * other words, the removed predecessor block has exactly one predecessor.
271 * Further there is a special case for self referencing blocks:
273 * then_b else_b then_b else_b
279 * | | | === optimized to ===> \ | | |
285 * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
286 * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
288 * @@@ It is negotiable whether we should do this ... there might end up a copy
289 * from the Phi in the loop when removing the Phis.
291 static void optimize_blocks(ir_node *b, void *env) {
292 int i, j, k, n, max_preds, n_preds, p_preds;
296 /* Count the number of predecessor if this block is merged with pred blocks
299 for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
300 max_preds += test_whether_dispensable(b, i);
302 in = xmalloc(max_preds * sizeof(*in));
305 printf(" working on "); DDMN(b);
306 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
307 pred = get_nodes_block(get_Block_cfgpred(b, i));
308 if (is_Bad(get_Block_cfgpred(b, i))) {
309 printf(" removing Bad %i\n ", i);
310 } else if (get_Block_block_visited(pred) +1
311 < get_irg_block_visited(current_ir_graph)) {
312 printf(" removing pred %i ", i); DDMN(pred);
313 } else { printf(" Nothing to do for "); DDMN(pred); }
315 * end Debug output -*/
317 /*- Fix the Phi nodes of the current block -*/
318 for (phi = get_irn_link(b); phi; ) {
319 assert(get_irn_op(phi) == op_Phi);
321 /* Find the new predecessors for the Phi */
323 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
324 pred = get_nodes_block(get_Block_cfgpred(b, i));
326 if (is_Bad(get_Block_cfgpred(b, i))) {
327 /* case Phi 1: Do nothing */
329 else if (get_Block_block_visited(pred) + 1
330 < get_irg_block_visited(current_ir_graph)) {
331 /* case Phi 2: It's an empty block and not yet visited. */
332 ir_node *phi_pred = get_Phi_pred(phi, i);
334 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
335 /* because of breaking loops, not all predecessors are Bad-clean,
336 * so we must check this here again */
337 if (! is_Bad(get_Block_cfgpred(pred, j))) {
338 if (get_nodes_block(phi_pred) == pred) {
340 assert(get_irn_op(phi_pred) == op_Phi); /* Block is empty!! */
342 in[p_preds++] = get_Phi_pred(phi_pred, j);
345 in[p_preds++] = phi_pred;
350 /* The Phi_pred node is replaced now if it is a Phi.
352 Somehow the removed Phi node can be used legally in loops.
353 Therefore we replace the old phi by the new one.
355 Further we have to remove the old Phi node by replacing it
356 by Bad. Else it will remain in the keepalive array of End
357 and cause illegal situations. So if there is no loop, we should
360 if (get_nodes_block(phi_pred) == pred) {
361 /* remove the Phi as it might be kept alive. Further there
362 might be other users. */
363 exchange(phi_pred, phi); /* geht, ist aber doch semantisch falsch! Warum?? */
367 in[p_preds++] = get_Phi_pred(phi, i);
370 assert(p_preds <= max_preds);
374 /* By removal of Bad ins the Phi might be degenerated. */
375 exchange(phi, in[0]);
377 set_irn_in(phi, p_preds, in);
379 phi = get_irn_link(phi);
382 /*- This happens only if merge between loop backedge and single loop entry.
383 See special case above. -*/
384 for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
385 pred = get_nodes_block(get_Block_cfgpred(b, k));
387 if (get_Block_block_visited(pred) + 1 < get_irg_block_visited(current_ir_graph)) {
388 /* we found a predecessor block at position k that will be removed */
389 for (phi = get_irn_link(pred); phi;) {
391 * the previous phase may already changed the phi, and even
392 * removed it at all, so check here if this node is still a phi
394 if (get_irn_op(phi) == op_Phi) {
397 /* move this phi from the predecessor into the block b */
398 set_nodes_block(phi, b);
400 /* first, copy all 0..k-1 predecessors */
401 for (i = 0; i < k; i++) {
402 pred = get_nodes_block(get_Block_cfgpred(b, i));
404 if (is_Bad(get_Block_cfgpred(b, i))) {
406 } else if (get_Block_block_visited(pred) + 1
407 < get_irg_block_visited(current_ir_graph)) {
408 /* It's an empty block and not yet visited. */
409 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
410 /* @@@ Hier brauche ich Schleifeninformation!!! Kontrollflusskante
411 muss Rueckwaertskante sein! (An allen vier in[q_preds] = phi
412 Anweisungen.) Trotzdem tuts bisher!! */
413 if (! is_Bad(get_Block_cfgpred(pred, j)))
421 /* now we are at k, copy the phi predecessors */
422 pred = get_nodes_block(get_Block_cfgpred(b, k));
423 for (i = 0; i < get_Phi_n_preds(phi); i++) {
424 if (! is_Bad(get_Block_cfgpred(pred, i)))
425 in[q_preds++] = get_Phi_pred(phi, i);
428 /* and now all the rest */
429 for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
430 pred = get_nodes_block(get_Block_cfgpred(b, i));
432 if (is_Bad(get_Block_cfgpred(b, i))) {
434 } else if (get_Block_block_visited(pred) +1
435 < get_irg_block_visited(current_ir_graph)) {
436 /* It's an empty block and not yet visited. */
437 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
438 if (! is_Bad(get_Block_cfgpred(pred, j)))
448 exchange(phi, in[0]);
450 set_irn_in(phi, q_preds, in);
452 assert(q_preds <= max_preds);
453 // assert(p_preds == q_preds && "Wrong Phi Fix");
455 phi = get_irn_link(phi);
460 /*- Fix the block -*/
462 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
463 pred = get_nodes_block(get_Block_cfgpred(b, i));
465 if (is_Bad(get_Block_cfgpred(b, i))) {
466 /* case 1: Do nothing */
467 } else if (get_Block_block_visited(pred) +1
468 < get_irg_block_visited(current_ir_graph)) {
469 /* case 2: It's an empty block and not yet visited. */
470 assert(get_Block_n_cfgpreds(b) > 1);
471 /* Else it should be optimized by equivalent_node. */
472 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
473 ir_node *pred_block = get_Block_cfgpred(pred, j);
475 /* because of breaking loops, not all predecessors are Bad-clean,
476 * so we must check this here again */
477 if (! is_Bad(pred_block))
478 in[n_preds++] = pred_block;
480 /* Remove block as it might be kept alive. */
481 exchange(pred, b/*new_Bad()*/);
484 in[n_preds++] = get_Block_cfgpred(b, i);
487 assert(n_preds <= max_preds);
489 set_irn_in(b, n_preds, in);
491 assert(get_irn_link(b) == NULL || (n_preds == p_preds && "Wrong Phi Fix"));
497 /* Optimizations of the control flow that also require changes of Phi nodes.
499 * This optimization performs two passes over the graph.
501 * The first pass collects all Phi nodes in a link list in the block
502 * nodes. Further it performs simple control flow optimizations.
503 * Finally it marks all blocks that do not contain useful
504 * computations, i.e., these blocks might be removed.
506 * The second pass performs the optimizations intended by this algorithm.
507 * It walks only over block nodes and adapts these and the Phi nodes in these blocks,
508 * which it finds in a linked list computed by the first pass.
510 * We use the block_visited flag to mark empty blocks in the first
512 * @@@ It would be better to add a struct in the link field
513 * that keeps the Phi list and the mark. Place it on an obstack, as
514 * we will lose blocks and thereby generate mem leaks.
516 void optimize_cf(ir_graph *irg) {
519 ir_node *end = get_irg_end(irg);
520 ir_graph *rem = current_ir_graph;
521 irg_dom_state dom_state = get_irg_dom_state(current_ir_graph);
522 current_ir_graph = irg;
524 /* Handle graph state */
525 assert(get_irg_phase_state(irg) != phase_building);
526 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
527 set_irg_outs_inconsistent(current_ir_graph);
528 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
529 set_irg_dom_inconsistent(current_ir_graph);
531 if (dom_state == dom_consistent && get_opt_optimize() && get_opt_unreachable_code()) {
532 ir_node *end = get_irg_end(irg);
534 /* we have dominace info, we can kill dead block */
535 irg_block_walk_graph(irg, NULL, remove_dead_block_cf, NULL);
537 /* fix the keep-alives */
538 for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
539 ir_node *ka = get_End_keepalive(end, i);
541 if (is_Block(ka) && (get_Block_dom_depth(ka) == -1))
542 set_End_keepalive(end, i, new_Bad());
543 if (is_Phi(ka) && (get_Block_dom_depth(get_nodes_block(ka)) == -1))
544 set_End_keepalive(end, i, new_Bad());
548 /* Use block visited flag to mark non-empty blocks. */
549 inc_irg_block_visited(irg);
550 irg_walk(end, merge_blocks, collect_nodes, NULL);
552 /* Optimize the standard code. */
553 irg_block_walk(get_irg_end_block(irg), optimize_blocks, NULL, NULL);
555 /* Walk all keep alives, optimize them if block, add to new in-array
556 for end if useful. */
557 in = NEW_ARR_F (ir_node *, 1);
558 in[0] = get_nodes_block(end);
559 inc_irg_visited(current_ir_graph);
561 for (i = 0; i < get_End_n_keepalives(end); i++) {
562 ir_node *ka = get_End_keepalive(end, i);
564 if (irn_not_visited(ka)) {
565 if ((get_irn_op(ka) == op_Block) && Block_not_block_visited(ka)) {
566 set_irg_block_visited(current_ir_graph, /* Don't walk all the way to Start. */
567 get_irg_block_visited(current_ir_graph)-1);
568 irg_block_walk(ka, optimize_blocks, NULL, NULL);
569 mark_irn_visited(ka);
570 ARR_APP1 (ir_node *, in, ka);
571 } else if (get_irn_op(ka) == op_Phi) {
572 mark_irn_visited(ka);
573 ARR_APP1 (ir_node *, in, ka);
577 /* DEL_ARR_F(end->in); GL @@@ tut nicht ! */
580 /* the verifyer doesn't work yet with floating nodes */
581 if (get_irg_pinned(irg) == op_pin_state_pinned) {
582 /* after optimize_cf(), only Bad data flow may remain. */
583 if (irg_vrfy_bads(irg, BAD_DF | BAD_BLOCK | TUPLE)) {
584 dump_ir_block_graph(irg, "-vrfy-cf");
585 dump_ir_graph(irg, "-vrfy-cf");
586 fprintf(stderr, "VRFY_BAD in optimize_cf()\n");
590 current_ir_graph = rem;