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"
39 #include "iropt_dbg.h"
41 /*------------------------------------------------------------------*/
42 /* Control flow optimization. */
44 /* Removes Bad control flow predecessors and empty blocks. A block */
45 /* is empty if it contains only a Jmp node. */
46 /* Blocks can only be removed if they are not needed for the */
47 /* semantics of Phi nodes. */
48 /*------------------------------------------------------------------*/
51 * Replace binary Conds that jumps twice into the same block
57 * ProjX True ProjX False ==> | /
62 * Such pattern are the result of if-conversion.
64 * Note that the simple case that Block has only these two
65 * predecessors are already handled in equivalent_node_Block().
67 static void remove_senseless_conds(ir_node *bl, void *data)
70 int n = get_Block_n_cfgpreds(bl);
74 for (i = 0; i < n; ++i) {
75 ir_node *pred_i = get_Block_cfgpred(bl, i);
76 ir_node *cond_i = skip_Proj(pred_i);
78 for (j = i + 1; j < n; ++j) {
79 ir_node *pred_j = get_Block_cfgpred(bl, j);
80 ir_node *cond_j = skip_Proj(pred_j);
83 && get_irn_op(cond_i) == op_Cond
84 && get_irn_mode(get_Cond_selector(cond_i)) == mode_b) {
86 ir_node *jmp = new_r_Jmp(current_ir_graph, get_nodes_block(cond_i));
87 set_irn_n(bl, i, jmp);
88 set_irn_n(bl, j, new_Bad());
90 DBG_OPT_IFSIM2(cond_i, jmp);
99 * Removes Tuples from Block control flow predecessors.
100 * Optimizes blocks with equivalent_node(). This is tricky,
101 * as we want to avoid nodes that have as block predecessor Bads.
102 * Therefore we also optimize at control flow operations, depending
103 * how we first reach the Block.
105 static void merge_blocks(ir_node *n, void *env) {
109 /* clear the link field for ALL nodes first */
110 set_irn_link(n, NULL);
112 if (get_irn_op(n) == op_Block) {
114 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
115 /* GL @@@ : is this possible? if (get_opt_normalize()) -- added, all tests go through.
116 A different order of optimizations might cause problems. */
117 if (get_opt_normalize())
118 set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i)));
122 new_block = equivalent_node(n);
123 if (new_block != n && ! is_Block_dead(new_block))
124 exchange (n, new_block);
126 } else if (get_opt_optimize() && (get_irn_mode(n) == mode_X)) {
127 /* We will soon visit a block. Optimize it before visiting! */
128 ir_node *b = get_nodes_block(skip_Proj(n));
130 if (!is_Block_dead(b)) {
131 new_block = equivalent_node(b);
133 while (irn_not_visited(b) && (!is_Block_dead(new_block)) && (new_block != b)) {
134 /* We would have to run gigo() if new is bad, so we
135 promote it directly below. Nevertheless, we sometimes reach a block
136 the first time through a dataflow node. In this case we optimized the
137 block as such and have to promote the Bad here. */
138 assert((get_opt_control_flow_straightening() ||
139 get_opt_control_flow_weak_simplification()) &&
140 ("strange flag setting"));
141 exchange (b, new_block);
143 new_block = equivalent_node(b);
146 /* normally, we would create a Bad block here, but this must be
147 * prevented, so just set it's cf to Bad.
149 if (is_Block_dead(new_block))
150 exchange(n, new_Bad());
156 * Remove cf from dead block by inspecting dominance info
157 * Do not replace blocks by Bad. This optimization shall
158 * ensure, that all Bad control flow predecessors are
159 * removed, and no new other Bads are introduced.
161 * Must be run in the post walker.
163 static void remove_dead_block_cf(ir_node *block, void *env)
167 /* check block predecessors and turn control flow into bad */
168 for (i = 0, n = get_Block_n_cfgpreds(block); i < n; ++i) {
169 ir_node *pred_X = get_Block_cfgpred(block, i);
171 if (! is_Bad(pred_X)) {
172 ir_node *pred_bl = get_nodes_block(skip_Proj(pred_X));
174 if (is_Block_dead(pred_bl) || (get_Block_dom_depth(pred_bl) < 0))
175 exchange (pred_X, new_Bad());
181 * Collects all Phi nodes in link list of Block.
182 * Marks all blocks "block_visited" if they contain a node other
184 * Replaces n by Bad if n is unreachable control flow. We do that
185 * in the post walker, so we catch all blocks.
187 static void collect_nodes(ir_node *n, void *env) {
188 if (is_no_Block(n)) {
189 ir_node *b = get_nodes_block(n);
191 if ((get_irn_op(n) == op_Phi)) {
192 /* Collect Phi nodes to compact ins along with block's ins. */
193 set_irn_link(n, get_irn_link(b));
196 else if ((get_irn_op(n) != op_Jmp) && !is_Bad(b)) { /* Check for non empty block. */
197 mark_Block_block_visited(b);
202 /** Returns true if pred is predecessor of block. */
203 static int is_pred_of(ir_node *pred, ir_node *b) {
206 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
207 ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
208 if (b_pred == pred) return 1;
214 /** Test whether we can optimize away pred block pos of b.
216 * @param b A block node.
217 * @param pos The position of the predecessor block to judge about.
219 * @returns The number of predecessors
221 * The test is rather tricky.
223 * The situation is something like the following:
232 * b merges the control flow of an if-then-else. We may not remove
233 * the 'then' _and_ the 'else' block of an 'if' if there is a Phi
234 * node in b, even if both are empty. The destruction of this Phi
235 * requires that a copy is added before the merge. We have to
236 * keep one of the case blocks to place the copies in.
238 * To perform the test for pos, we must regard predecessors before pos
239 * as already removed.
241 static int test_whether_dispensable(ir_node *b, int pos) {
242 int i, j, n_preds = 1;
243 ir_node *pred = get_Block_cfgpred_block(b, pos);
245 /* Bad blocks will be optimized away, so we don't need space for them */
246 if (is_Block_dead(pred))
249 if (get_Block_block_visited(pred) + 1
250 < get_irg_block_visited(current_ir_graph)) {
252 if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
253 /* Mark block so that is will not be removed: optimization is turned off. */
254 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
258 /* Seems to be empty. At least we detected this in collect_nodes. */
259 if (!get_irn_link(b)) {
260 /* There are no Phi nodes ==> all predecessors are dispensable. */
261 n_preds = get_Block_n_cfgpreds(pred);
263 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
264 Handle all pred blocks with preds < pos as if they were already removed. */
265 for (i = 0; i < pos; i++) {
266 ir_node *b_pred = get_Block_cfgpred_block(b, i);
267 if (! is_Block_dead(b_pred) &&
268 get_Block_block_visited(b_pred) + 1
269 < get_irg_block_visited(current_ir_graph)) {
270 for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
271 ir_node *b_pred_pred = get_Block_cfgpred_block(b_pred, j);
272 if (is_pred_of(b_pred_pred, pred))
273 goto non_dispensable;
276 if (is_pred_of(b_pred, pred))
277 goto non_dispensable;
280 for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
281 ir_node *b_pred = get_Block_cfgpred_block(b, i);
282 if (is_pred_of(b_pred, pred))
283 goto non_dispensable;
285 /* if we get here, the block is dispensable */
286 n_preds = get_Block_n_cfgpreds(pred);
293 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
298 * Store to defer the exchanged of Phi nodes.
300 typedef struct _defer_ex_phi {
301 ir_node *phi_pred; /**< the previous Phi node that will be replaced */
302 ir_node *phi; /**< the new Phi node that replaces phi_pred */
306 * This method removed Bad cf predecessors from Blocks and Phis, and removes
307 * empty blocks. A block is empty if it only contains Phi and Jmp nodes.
309 * We first adapt Phi nodes, then Block nodes, as we need the old ins
310 * of the Block to adapt the Phi nodes. We do this by computing new
311 * in arrays, and then replacing the old ones. So far we compute new in arrays
312 * for all nodes, not regarding whether there is a possibility for optimization.
314 * For each predecessor p of a Block b there are three cases:
315 * -1. The predecessor p is a Bad node: just skip it. The in array of b shrinks by one.
316 * -2. The predecessor p is empty. Remove p. All predecessors of p are now
318 * -3. The predecessor p is a block containing useful code. Just keep p as is.
320 * For Phi nodes f we have to check the conditions at the Block of f.
321 * For cases 1 and 3 we proceed as for Blocks. For case 2 we can have two
323 * -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED. In this
324 * case we proceed as for blocks. We remove pred_f. All
325 * predecessors of pred_f now are predecessors of f.
326 * -2b: The old predecessor of f is NOT in the block removed. It might be a Phi, too.
327 * We have to replicate f for each predecessor of the removed block. Or, with
328 * other words, the removed predecessor block has exactly one predecessor.
330 * Further there is a special case for self referencing blocks:
333 * then_b else_b then_b else_b
339 * | | | === optimized to ===> \ | | |
346 * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
347 * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
349 * @@@ It is negotiable whether we should do this ... there might end up a copy
350 * from the Phi in the loop when removing the Phis.
352 static void optimize_blocks(ir_node *b, void *env) {
353 int i, j, k, n, max_preds, n_preds, p_preds;
356 defer_ex_phi *defers;
358 /* Count the number of predecessor if this block is merged with pred blocks
361 for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
362 max_preds += test_whether_dispensable(b, i);
364 in = xmalloc(max_preds * sizeof(*in));
366 defers = NEW_ARR_F(defer_ex_phi, 0);
369 printf(" working on "); DDMN(b);
370 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
371 pred = get_nodes_block(get_Block_cfgpred(b, i));
372 if (is_Bad(get_Block_cfgpred(b, i))) {
373 printf(" removing Bad %i\n ", i);
374 } else if (get_Block_block_visited(pred) +1
375 < get_irg_block_visited(current_ir_graph)) {
376 printf(" removing pred %i ", i); DDMN(pred);
377 } else { printf(" Nothing to do for "); DDMN(pred); }
379 * end Debug output -*/
381 /*- Fix the Phi nodes of the current block -*/
382 for (phi = get_irn_link(b); phi; ) {
383 assert(get_irn_op(phi) == op_Phi);
385 /* Find the new predecessors for the Phi */
387 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
388 pred = get_Block_cfgpred_block(b, i);
390 if (is_Bad(get_Block_cfgpred(b, i))) {
391 /* case Phi 1: Do nothing */
393 else if (get_Block_block_visited(pred) + 1
394 < get_irg_block_visited(current_ir_graph)) {
395 /* case Phi 2: It's an empty block and not yet visited. */
396 ir_node *phi_pred = get_Phi_pred(phi, i);
398 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
399 /* because of breaking loops, not all predecessors are Bad-clean,
400 * so we must check this here again */
401 if (! is_Bad(get_Block_cfgpred(pred, j))) {
402 if (get_nodes_block(phi_pred) == pred) {
404 assert(get_irn_op(phi_pred) == op_Phi); /* Block is empty!! */
406 in[p_preds++] = get_Phi_pred(phi_pred, j);
409 in[p_preds++] = phi_pred;
414 /* The Phi_pred node is replaced now if it is a Phi.
416 Somehow the removed Phi node can be used legally in loops.
417 Therefore we replace the old phi by the new one.
418 This must be done _AFTER_ all Phis are optimized, or
419 it will fail if two Phis use the same pred_Phi.
421 FIXME: Is the following true? We ALWAYS replace it by the new one.
423 Further we have to remove the old Phi node by replacing it
424 by Bad. Else it will remain in the keep alive array of End
425 and cause illegal situations. So if there is no loop, we should
428 if (get_nodes_block(phi_pred) == pred) {
430 /* remove the Phi as it might be kept alive. Further there
431 might be other users. */
432 for (i = ARR_LEN(defers) - 1; i >= 0; --i)
433 if (defers[i].phi_pred == phi_pred)
437 /* we have a new replacement */
440 elem.phi_pred = phi_pred;
442 ARR_APP1(defer_ex_phi, defers, elem);
447 in[p_preds++] = get_Phi_pred(phi, i);
450 assert(p_preds <= max_preds);
454 /* By removal of Bad ins the Phi might be degenerated. */
455 exchange(phi, in[0]);
457 set_irn_in(phi, p_preds, in);
459 phi = get_irn_link(phi);
462 /* now, exchange all Phis */
463 for (i = ARR_LEN(defers) - 1; i >= 0; --i) {
464 exchange(defers[i].phi_pred, defers[i].phi);
468 /*- This happens only if merge between loop backedge and single loop entry.
469 See special case above. -*/
470 for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
471 pred = get_nodes_block(get_Block_cfgpred(b, k));
473 if (get_Block_block_visited(pred) + 1 < get_irg_block_visited(current_ir_graph)) {
474 /* we found a predecessor block at position k that will be removed */
475 for (phi = get_irn_link(pred); phi;) {
477 * the previous phase may already changed the phi, and even
478 * removed it at all, so check here if this node is still a phi
480 if (get_irn_op(phi) == op_Phi) {
483 /* move this phi from the predecessor into the block b */
484 set_nodes_block(phi, b);
486 /* first, copy all 0..k-1 predecessors */
487 for (i = 0; i < k; i++) {
488 pred = get_nodes_block(get_Block_cfgpred(b, i));
490 if (is_Bad(get_Block_cfgpred(b, i))) {
492 } else if (get_Block_block_visited(pred) + 1
493 < get_irg_block_visited(current_ir_graph)) {
494 /* It's an empty block and not yet visited. */
495 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
496 /* @@@ Hier brauche ich Schleifeninformation!!! Kontrollflusskante
497 muss Rueckwaertskante sein! (An allen vier in[q_preds] = phi
498 Anweisungen.) Trotzdem tuts bisher!! */
499 if (! is_Bad(get_Block_cfgpred(pred, j)))
507 /* now we are at k, copy the phi predecessors */
508 pred = get_nodes_block(get_Block_cfgpred(b, k));
509 for (i = 0; i < get_Phi_n_preds(phi); i++) {
510 if (! is_Bad(get_Block_cfgpred(pred, i)))
511 in[q_preds++] = get_Phi_pred(phi, i);
514 /* and now all the rest */
515 for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
516 pred = get_nodes_block(get_Block_cfgpred(b, i));
518 if (is_Bad(get_Block_cfgpred(b, i))) {
520 } else if (get_Block_block_visited(pred) +1
521 < get_irg_block_visited(current_ir_graph)) {
522 /* It's an empty block and not yet visited. */
523 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
524 if (! is_Bad(get_Block_cfgpred(pred, j)))
534 exchange(phi, in[0]);
536 set_irn_in(phi, q_preds, in);
538 assert(q_preds <= max_preds);
539 // assert(p_preds == q_preds && "Wrong Phi Fix");
541 phi = get_irn_link(phi);
546 /*- Fix the block -*/
548 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
549 pred = get_nodes_block(get_Block_cfgpred(b, i));
551 if (is_Bad(get_Block_cfgpred(b, i))) {
552 /* case 1: Do nothing */
553 } else if (get_Block_block_visited(pred) +1
554 < get_irg_block_visited(current_ir_graph)) {
555 /* case 2: It's an empty block and not yet visited. */
556 assert(get_Block_n_cfgpreds(b) > 1);
557 /* Else it should be optimized by equivalent_node. */
558 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
559 ir_node *pred_block = get_Block_cfgpred(pred, j);
561 /* because of breaking loops, not all predecessors are Bad-clean,
562 * so we must check this here again */
563 if (! is_Bad(pred_block))
564 in[n_preds++] = pred_block;
566 /* Remove block as it might be kept alive. */
567 exchange(pred, b/*new_Bad()*/);
570 in[n_preds++] = get_Block_cfgpred(b, i);
573 assert(n_preds <= max_preds);
575 set_irn_in(b, n_preds, in);
577 assert(get_irn_link(b) == NULL || (n_preds == p_preds && "Wrong Phi Fix"));
583 /* Optimizations of the control flow that also require changes of Phi nodes.
585 * This optimization performs two passes over the graph.
587 * The first pass collects all Phi nodes in a link list in the block
588 * nodes. Further it performs simple control flow optimizations.
589 * Finally it marks all blocks that do not contain useful
590 * computations, i.e., these blocks might be removed.
592 * The second pass performs the optimizations intended by this algorithm.
593 * It walks only over block nodes and adapts these and the Phi nodes in these blocks,
594 * which it finds in a linked list computed by the first pass.
596 * We use the block_visited flag to mark empty blocks in the first
598 * @@@ It would be better to add a struct in the link field
599 * that keeps the Phi list and the mark. Place it on an obstack, as
600 * we will lose blocks and thereby generate memory leaks.
602 void optimize_cf(ir_graph *irg) {
605 ir_node *end = get_irg_end(irg);
606 ir_graph *rem = current_ir_graph;
607 irg_dom_state dom_state = get_irg_dom_state(current_ir_graph);
608 current_ir_graph = irg;
610 /* if the graph is not pinned, we cannot determine empty blocks */
611 assert(get_irg_pinned(irg) != op_pin_state_floats &&
612 "Control flow optimization need a pinned graph");
614 /* Handle graph state */
615 assert(get_irg_phase_state(irg) != phase_building);
616 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
617 set_irg_outs_inconsistent(current_ir_graph);
618 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
619 set_irg_dom_inconsistent(current_ir_graph);
621 if (dom_state == dom_consistent && get_opt_optimize() && get_opt_unreachable_code()) {
622 ir_node *end = get_irg_end(irg);
624 /* we have dominance info, we can kill dead block */
625 irg_block_walk_graph(irg, NULL, remove_dead_block_cf, NULL);
627 /* fix the keep-alives */
628 for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
629 ir_node *ka = get_End_keepalive(end, i);
632 if (get_Block_dom_depth(ka) == -1)
633 set_End_keepalive(end, i, new_Bad());
635 else if (is_Block_dead(get_nodes_block(ka)) || get_Block_dom_depth(get_nodes_block(ka)) == -1)
636 set_End_keepalive(end, i, new_Bad());
639 irg_block_walk_graph(current_ir_graph, NULL, remove_senseless_conds, NULL);
641 /* Use block visited flag to mark non-empty blocks. */
642 inc_irg_block_visited(irg);
643 irg_walk(end, merge_blocks, collect_nodes, NULL);
645 /* Optimize the standard code. */
646 irg_block_walk(get_irg_end_block(irg), optimize_blocks, NULL, NULL);
648 /* Walk all keep alives, optimize them if block, add to new in-array
649 for end if useful. */
650 in = NEW_ARR_F (ir_node *, 1);
651 in[0] = get_nodes_block(end);
652 inc_irg_visited(current_ir_graph);
654 for (i = 0, n = get_End_n_keepalives(end); i < n; i++) {
655 ir_node *ka = get_End_keepalive(end, i);
657 if (irn_not_visited(ka)) {
658 if ((get_irn_op(ka) == op_Block) && Block_not_block_visited(ka)) {
659 set_irg_block_visited(current_ir_graph, /* Don't walk all the way to Start. */
660 get_irg_block_visited(current_ir_graph)-1);
661 irg_block_walk(ka, optimize_blocks, NULL, NULL);
662 mark_irn_visited(ka);
663 ARR_APP1 (ir_node *, in, ka);
664 } else if (get_irn_op(ka) == op_Phi) {
665 mark_irn_visited(ka);
666 if (! is_Block_dead(get_nodes_block(ka)))
667 ARR_APP1 (ir_node *, in, ka);
668 } else if (get_irn_op(ka) == op_IJmp) {
669 mark_irn_visited(ka);
670 if (! is_Block_dead(get_nodes_block(ka)))
671 ARR_APP1 (ir_node *, in, ka);
675 DEL_ARR_F(end->in); /* GL @@@ tut nicht! MMB Warum? */
679 /* the verifier doesn't work yet with floating nodes */
680 if (get_irg_pinned(irg) == op_pin_state_pinned) {
681 /* after optimize_cf(), only Bad data flow may remain. */
682 if (irg_vrfy_bads(irg, BAD_DF | BAD_BLOCK | TUPLE)) {
683 dump_ir_block_graph(irg, "-vrfy-cf");
684 dump_ir_graph(irg, "-vrfy-cf");
685 fprintf(stderr, "VRFY_BAD in optimize_cf()\n");
689 current_ir_graph = rem;