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.
27 #include "irgraph_t.h"
40 #include "irbackedge_t.h"
46 #include "iropt_dbg.h"
48 /*------------------------------------------------------------------*/
49 /* Control flow optimization. */
51 /* Removes Bad control flow predecessors and empty blocks. A block */
52 /* is empty if it contains only a Jmp node. */
53 /* Blocks can only be removed if they are not needed for the */
54 /* semantics of Phi nodes. */
55 /*------------------------------------------------------------------*/
58 * Replace binary Conds that jumps twice into the same block
64 * ProjX True ProjX False ==> | /
69 * Such pattern are the result of if-conversion.
71 * Note that the simple case that Block has only these two
72 * predecessors are already handled in equivalent_node_Block().
74 static void remove_senseless_conds(ir_node *bl, void *data)
77 int n = get_Block_n_cfgpreds(bl);
81 for (i = 0; i < n; ++i) {
82 ir_node *pred_i = get_Block_cfgpred(bl, i);
83 ir_node *cond_i = skip_Proj(pred_i);
85 for (j = i + 1; j < n; ++j) {
86 ir_node *pred_j = get_Block_cfgpred(bl, j);
87 ir_node *cond_j = skip_Proj(pred_j);
90 && get_irn_op(cond_i) == op_Cond
91 && get_irn_mode(get_Cond_selector(cond_i)) == mode_b) {
93 ir_node *jmp = new_r_Jmp(current_ir_graph, get_nodes_block(cond_i));
94 set_irn_n(bl, i, jmp);
95 set_irn_n(bl, j, new_Bad());
97 DBG_OPT_IFSIM2(cond_i, jmp);
106 * Removes Tuples from Block control flow predecessors.
107 * Optimizes blocks with equivalent_node(). This is tricky,
108 * as we want to avoid nodes that have as block predecessor Bads.
109 * Therefore we also optimize at control flow operations, depending
110 * how we first reach the Block.
112 static void merge_blocks(ir_node *n, void *env) {
116 /* clear the link field for ALL nodes first */
117 set_irn_link(n, NULL);
119 if (get_irn_op(n) == op_Block) {
121 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
122 /* GL @@@ : is this possible? if (get_opt_normalize()) -- added, all tests go through.
123 A different order of optimizations might cause problems. */
124 if (get_opt_normalize())
125 set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i)));
129 new_block = equivalent_node(n);
130 if (new_block != n && ! is_Block_dead(new_block))
131 exchange (n, new_block);
133 } else if (get_opt_optimize() && (get_irn_mode(n) == mode_X)) {
134 /* We will soon visit a block. Optimize it before visiting! */
135 ir_node *b = get_nodes_block(skip_Proj(n));
137 if (!is_Block_dead(b)) {
138 new_block = equivalent_node(b);
140 while (irn_not_visited(b) && (!is_Block_dead(new_block)) && (new_block != b)) {
141 /* We would have to run gigo() if new is bad, so we
142 promote it directly below. Nevertheless, we sometimes reach a block
143 the first time through a dataflow node. In this case we optimized the
144 block as such and have to promote the Bad here. */
145 assert((get_opt_control_flow_straightening() ||
146 get_opt_control_flow_weak_simplification()) &&
147 ("strange flag setting"));
148 exchange (b, new_block);
150 new_block = equivalent_node(b);
153 /* normally, we would create a Bad block here, but this must be
154 * prevented, so just set it's cf to Bad.
156 if (is_Block_dead(new_block))
157 exchange(n, new_Bad());
163 * Remove cf from dead block by inspecting dominance info
164 * Do not replace blocks by Bad. This optimization shall
165 * ensure, that all Bad control flow predecessors are
166 * removed, and no new other Bads are introduced.
168 * Must be run in the post walker.
170 static void remove_dead_block_cf(ir_node *block, void *env)
174 /* check block predecessors and turn control flow into bad */
175 for (i = 0, n = get_Block_n_cfgpreds(block); i < n; ++i) {
176 ir_node *pred_X = get_Block_cfgpred(block, i);
178 if (! is_Bad(pred_X)) {
179 ir_node *pred_bl = get_nodes_block(skip_Proj(pred_X));
181 if (is_Block_dead(pred_bl) || (get_Block_dom_depth(pred_bl) < 0))
182 exchange (pred_X, new_Bad());
188 * Collects all Phi nodes in link list of Block.
189 * Marks all blocks "block_visited" if they contain a node other
191 * Replaces n by Bad if n is unreachable control flow. We do that
192 * in the post walker, so we catch all blocks.
194 static void collect_nodes(ir_node *n, void *env) {
195 if (is_no_Block(n)) {
196 ir_node *b = get_nodes_block(n);
198 if ((get_irn_op(n) == op_Phi)) {
199 /* Collect Phi nodes to compact ins along with block's ins. */
200 set_irn_link(n, get_irn_link(b));
203 else if ((get_irn_op(n) != op_Jmp) && !is_Bad(b)) { /* Check for non empty block. */
204 mark_Block_block_visited(b);
209 /** Returns true if pred is predecessor of block. */
210 static int is_pred_of(ir_node *pred, ir_node *b) {
213 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
214 ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
215 if (b_pred == pred) return 1;
221 /** Test whether we can optimize away pred block pos of b.
223 * @param b A block node.
224 * @param pos The position of the predecessor block to judge about.
226 * @returns The number of predecessors
228 * The test is rather tricky.
230 * The situation is something like the following:
239 * b merges the control flow of an if-then-else. We may not remove
240 * the 'then' _and_ the 'else' block of an 'if' if there is a Phi
241 * node in b, even if both are empty. The destruction of this Phi
242 * requires that a copy is added before the merge. We have to
243 * keep one of the case blocks to place the copies in.
245 * To perform the test for pos, we must regard predecessors before pos
246 * as already removed.
248 static int test_whether_dispensable(ir_node *b, int pos) {
249 int i, j, n_preds = 1;
250 ir_node *pred = get_Block_cfgpred_block(b, pos);
252 /* Bad blocks will be optimized away, so we don't need space for them */
253 if (is_Block_dead(pred))
256 if (get_Block_block_visited(pred) + 1
257 < get_irg_block_visited(current_ir_graph)) {
259 if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
260 /* Mark block so that is will not be removed: optimization is turned off. */
261 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
265 /* Seems to be empty. At least we detected this in collect_nodes. */
266 if (!get_irn_link(b)) {
267 /* There are no Phi nodes ==> all predecessors are dispensable. */
268 n_preds = get_Block_n_cfgpreds(pred);
270 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
271 Handle all pred blocks with preds < pos as if they were already removed. */
272 for (i = 0; i < pos; i++) {
273 ir_node *b_pred = get_Block_cfgpred_block(b, i);
274 if (! is_Block_dead(b_pred) &&
275 get_Block_block_visited(b_pred) + 1
276 < get_irg_block_visited(current_ir_graph)) {
277 for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
278 ir_node *b_pred_pred = get_Block_cfgpred_block(b_pred, j);
279 if (is_pred_of(b_pred_pred, pred))
280 goto non_dispensable;
283 if (is_pred_of(b_pred, pred))
284 goto non_dispensable;
287 for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
288 ir_node *b_pred = get_Block_cfgpred_block(b, i);
289 if (is_pred_of(b_pred, pred))
290 goto non_dispensable;
292 /* if we get here, the block is dispensable */
293 n_preds = get_Block_n_cfgpreds(pred);
300 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
305 * Store to defer the exchanged of Phi nodes.
307 typedef struct _defer_ex_phi {
308 ir_node *phi_pred; /**< the previous Phi node that will be replaced */
309 ir_node *phi; /**< the new Phi node that replaces phi_pred */
313 * This method removed Bad cf predecessors from Blocks and Phis, and removes
314 * empty blocks. A block is empty if it only contains Phi and Jmp nodes.
316 * We first adapt Phi nodes, then Block nodes, as we need the old ins
317 * of the Block to adapt the Phi nodes. We do this by computing new
318 * in arrays, and then replacing the old ones. So far we compute new in arrays
319 * for all nodes, not regarding whether there is a possibility for optimization.
321 * For each predecessor p of a Block b there are three cases:
322 * -1. The predecessor p is a Bad node: just skip it. The in array of b shrinks by one.
323 * -2. The predecessor p is empty. Remove p. All predecessors of p are now
325 * -3. The predecessor p is a block containing useful code. Just keep p as is.
327 * For Phi nodes f we have to check the conditions at the Block of f.
328 * For cases 1 and 3 we proceed as for Blocks. For case 2 we can have two
330 * -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED. In this
331 * case we proceed as for blocks. We remove pred_f. All
332 * predecessors of pred_f now are predecessors of f.
333 * -2b: The old predecessor of f is NOT in the block removed. It might be a Phi, too.
334 * We have to replicate f for each predecessor of the removed block. Or, with
335 * other words, the removed predecessor block has exactly one predecessor.
337 * Further there is a special case for self referencing blocks:
340 * then_b else_b then_b else_b
346 * | | | === optimized to ===> \ | | |
353 * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
354 * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
356 * @@@ It is negotiable whether we should do this ... there might end up a copy
357 * from the Phi in the loop when removing the Phis.
359 static void optimize_blocks(ir_node *b, void *env) {
360 int i, j, k, n, max_preds, n_preds, p_preds;
363 defer_ex_phi *defers;
365 /* Count the number of predecessor if this block is merged with pred blocks
368 for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
369 max_preds += test_whether_dispensable(b, i);
371 in = xmalloc(max_preds * sizeof(*in));
373 defers = NEW_ARR_F(defer_ex_phi, 0);
376 printf(" working on "); DDMN(b);
377 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
378 pred = get_nodes_block(get_Block_cfgpred(b, i));
379 if (is_Bad(get_Block_cfgpred(b, i))) {
380 printf(" removing Bad %i\n ", i);
381 } else if (get_Block_block_visited(pred) +1
382 < get_irg_block_visited(current_ir_graph)) {
383 printf(" removing pred %i ", i); DDMN(pred);
384 } else { printf(" Nothing to do for "); DDMN(pred); }
386 * end Debug output -*/
388 /*- Fix the Phi nodes of the current block -*/
389 for (phi = get_irn_link(b); phi; ) {
390 assert(get_irn_op(phi) == op_Phi);
392 /* Find the new predecessors for the Phi */
394 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
395 pred = get_Block_cfgpred_block(b, i);
397 if (is_Bad(get_Block_cfgpred(b, i))) {
398 /* case Phi 1: Do nothing */
400 else if (get_Block_block_visited(pred) + 1
401 < get_irg_block_visited(current_ir_graph)) {
402 /* case Phi 2: It's an empty block and not yet visited. */
403 ir_node *phi_pred = get_Phi_pred(phi, i);
405 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
406 /* because of breaking loops, not all predecessors are Bad-clean,
407 * so we must check this here again */
408 if (! is_Bad(get_Block_cfgpred(pred, j))) {
409 if (get_nodes_block(phi_pred) == pred) {
411 assert(get_irn_op(phi_pred) == op_Phi); /* Block is empty!! */
413 in[p_preds++] = get_Phi_pred(phi_pred, j);
416 in[p_preds++] = phi_pred;
421 /* The Phi_pred node is replaced now if it is a Phi.
423 Somehow the removed Phi node can be used legally in loops.
424 Therefore we replace the old phi by the new one.
425 This must be done _AFTER_ all Phis are optimized, or
426 it will fail if two Phis use the same pred_Phi.
428 FIXME: Is the following true? We ALWAYS replace it by the new one.
430 Further we have to remove the old Phi node by replacing it
431 by Bad. Else it will remain in the keep alive array of End
432 and cause illegal situations. So if there is no loop, we should
435 if (get_nodes_block(phi_pred) == pred) {
437 /* remove the Phi as it might be kept alive. Further there
438 might be other users. */
439 for (i = ARR_LEN(defers) - 1; i >= 0; --i)
440 if (defers[i].phi_pred == phi_pred)
444 /* we have a new replacement */
447 elem.phi_pred = phi_pred;
449 ARR_APP1(defer_ex_phi, defers, elem);
454 in[p_preds++] = get_Phi_pred(phi, i);
457 assert(p_preds <= max_preds);
461 /* By removal of Bad ins the Phi might be degenerated. */
462 exchange(phi, in[0]);
464 set_irn_in(phi, p_preds, in);
466 phi = get_irn_link(phi);
469 /* now, exchange all Phis */
470 for (i = ARR_LEN(defers) - 1; i >= 0; --i) {
471 exchange(defers[i].phi_pred, defers[i].phi);
475 /*- This happens only if merge between loop backedge and single loop entry.
476 See special case above. -*/
477 for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
478 pred = get_nodes_block(get_Block_cfgpred(b, k));
480 if (get_Block_block_visited(pred) + 1 < get_irg_block_visited(current_ir_graph)) {
481 /* we found a predecessor block at position k that will be removed */
482 for (phi = get_irn_link(pred); phi;) {
484 * the previous phase may already changed the phi, and even
485 * removed it at all, so check here if this node is still a phi
487 if (get_irn_op(phi) == op_Phi) {
490 /* move this phi from the predecessor into the block b */
491 set_nodes_block(phi, b);
493 /* first, copy all 0..k-1 predecessors */
494 for (i = 0; i < k; i++) {
495 pred = get_nodes_block(get_Block_cfgpred(b, i));
497 if (is_Bad(get_Block_cfgpred(b, i))) {
499 } else if (get_Block_block_visited(pred) + 1
500 < get_irg_block_visited(current_ir_graph)) {
501 /* It's an empty block and not yet visited. */
502 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
503 /* @@@ Hier brauche ich Schleifeninformation!!! Kontrollflusskante
504 muss Rueckwaertskante sein! (An allen vier in[q_preds] = phi
505 Anweisungen.) Trotzdem tuts bisher!! */
506 if (! is_Bad(get_Block_cfgpred(pred, j)))
514 /* now we are at k, copy the phi predecessors */
515 pred = get_nodes_block(get_Block_cfgpred(b, k));
516 for (i = 0; i < get_Phi_n_preds(phi); i++) {
517 if (! is_Bad(get_Block_cfgpred(pred, i)))
518 in[q_preds++] = get_Phi_pred(phi, i);
521 /* and now all the rest */
522 for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
523 pred = get_nodes_block(get_Block_cfgpred(b, i));
525 if (is_Bad(get_Block_cfgpred(b, i))) {
527 } else if (get_Block_block_visited(pred) +1
528 < get_irg_block_visited(current_ir_graph)) {
529 /* It's an empty block and not yet visited. */
530 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
531 if (! is_Bad(get_Block_cfgpred(pred, j)))
541 exchange(phi, in[0]);
543 set_irn_in(phi, q_preds, in);
545 assert(q_preds <= max_preds);
546 // assert(p_preds == q_preds && "Wrong Phi Fix");
548 phi = get_irn_link(phi);
553 /*- Fix the block -*/
555 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
556 pred = get_nodes_block(get_Block_cfgpred(b, i));
558 if (is_Bad(get_Block_cfgpred(b, i))) {
559 /* case 1: Do nothing */
560 } else if (get_Block_block_visited(pred) +1
561 < get_irg_block_visited(current_ir_graph)) {
562 /* case 2: It's an empty block and not yet visited. */
563 assert(get_Block_n_cfgpreds(b) > 1);
564 /* Else it should be optimized by equivalent_node. */
565 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
566 ir_node *pred_block = get_Block_cfgpred(pred, j);
568 /* because of breaking loops, not all predecessors are Bad-clean,
569 * so we must check this here again */
570 if (! is_Bad(pred_block))
571 in[n_preds++] = pred_block;
573 /* Remove block as it might be kept alive. */
574 exchange(pred, b/*new_Bad()*/);
577 in[n_preds++] = get_Block_cfgpred(b, i);
580 assert(n_preds <= max_preds);
582 set_irn_in(b, n_preds, in);
584 assert(get_irn_link(b) == NULL || (n_preds == p_preds && "Wrong Phi Fix"));
590 /* Optimizations of the control flow that also require changes of Phi nodes.
592 * This optimization performs two passes over the graph.
594 * The first pass collects all Phi nodes in a link list in the block
595 * nodes. Further it performs simple control flow optimizations.
596 * Finally it marks all blocks that do not contain useful
597 * computations, i.e., these blocks might be removed.
599 * The second pass performs the optimizations intended by this algorithm.
600 * It walks only over block nodes and adapts these and the Phi nodes in these blocks,
601 * which it finds in a linked list computed by the first pass.
603 * We use the block_visited flag to mark empty blocks in the first
605 * @@@ It would be better to add a struct in the link field
606 * that keeps the Phi list and the mark. Place it on an obstack, as
607 * we will lose blocks and thereby generate memory leaks.
609 void optimize_cf(ir_graph *irg) {
612 ir_node *end = get_irg_end(irg);
613 ir_graph *rem = current_ir_graph;
614 irg_dom_state dom_state = get_irg_dom_state(current_ir_graph);
615 current_ir_graph = irg;
617 /* if the graph is not pinned, we cannot determine empty blocks */
618 assert(get_irg_pinned(irg) != op_pin_state_floats &&
619 "Control flow optimization need a pinned graph");
621 /* Handle graph state */
622 assert(get_irg_phase_state(irg) != phase_building);
623 set_irg_outs_inconsistent(current_ir_graph);
624 set_irg_extblk_inconsistent(current_ir_graph);
625 set_irg_loopinfo_inconsistent(current_ir_graph);
626 set_irg_doms_inconsistent(current_ir_graph);
628 if (dom_state == dom_consistent && get_opt_optimize() && get_opt_unreachable_code()) {
629 ir_node *end = get_irg_end(irg);
631 /* we have dominance info, we can kill dead block */
632 irg_block_walk_graph(irg, NULL, remove_dead_block_cf, NULL);
634 /* fix the keep-alives */
635 for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
636 ir_node *ka = get_End_keepalive(end, i);
639 /* do NOT keep dead blocks */
640 if (get_Block_dom_depth(ka) == -1)
641 set_End_keepalive(end, i, new_Bad());
643 else if (is_Block_dead(get_nodes_block(ka)) ||
644 get_Block_dom_depth(get_nodes_block(ka)) == -1)
645 /* do NOT keep nodes in dead blocks */
646 set_End_keepalive(end, i, new_Bad());
649 irg_block_walk_graph(current_ir_graph, NULL, remove_senseless_conds, NULL);
651 /* Use block visited flag to mark non-empty blocks. */
652 inc_irg_block_visited(irg);
653 irg_walk(end, merge_blocks, collect_nodes, NULL);
655 /* Optimize the standard code. */
656 irg_block_walk(get_irg_end_block(irg), optimize_blocks, NULL, NULL);
658 /* Walk all keep alives, optimize them if block, add to new in-array
659 for end if useful. */
660 n = get_End_n_keepalives(end);
662 NEW_ARR_A (ir_node *, in, n);
663 inc_irg_visited(current_ir_graph);
665 /* fix the keep alive */
666 for (i = j = 0; i < n; i++) {
667 ir_node *ka = get_End_keepalive(end, i);
669 if (irn_not_visited(ka)) {
670 ir_op *op = get_irn_op(ka);
672 if ((op == op_Block) && Block_not_block_visited(ka)) {
673 set_irg_block_visited(current_ir_graph, /* Don't walk all the way to Start. */
674 get_irg_block_visited(current_ir_graph)-1);
675 irg_block_walk(ka, optimize_blocks, NULL, NULL);
676 mark_irn_visited(ka);
678 } else if (op == op_Phi) {
679 mark_irn_visited(ka);
680 if (! is_Block_dead(get_nodes_block(ka)))
682 } else if (is_op_keep(op)) {
683 mark_irn_visited(ka);
684 if (! is_Block_dead(get_nodes_block(ka)))
690 set_End_keepalives(end, j, in);
692 /* the verifier doesn't work yet with floating nodes */
693 if (get_irg_pinned(irg) == op_pin_state_pinned) {
694 /* after optimize_cf(), only Bad data flow may remain. */
695 if (irg_vrfy_bads(irg, BAD_DF | BAD_BLOCK | TUPLE)) {
696 dump_ir_block_graph(irg, "-vrfy-cf");
697 dump_ir_graph(irg, "-vrfy-cf");
698 fprintf(stderr, "VRFY_BAD in optimize_cf()\n");
702 current_ir_graph = rem;