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 static void remove_senseless_conds(ir_node *bl, void *data)
53 int n = get_irn_arity(bl);
57 for(i = 0; i < n; ++i) {
58 ir_node *pred_i = get_irn_n(bl, i);
59 ir_node *cond_i = skip_Proj(pred_i);
61 for(j = i + 1; j < n; ++j) {
62 ir_node *pred_j = get_irn_n(bl, j);
63 ir_node *cond_j = skip_Proj(pred_j);
66 && get_irn_opcode(cond_i) == iro_Cond
67 && get_irn_mode(get_Cond_selector(cond_i)) == mode_b) {
69 ir_node *jmp = new_r_Jmp(current_ir_graph, get_nodes_block(cond_i));
70 set_irn_n(bl, i, jmp);
71 set_irn_n(bl, j, new_Bad());
81 * Removes Tuples from Block control flow predecessors.
82 * Optimizes blocks with equivalent_node(). This is tricky,
83 * as we want to avoid nodes that have as block predecessor Bads.
84 * Therefore we also optimize at control flow operations, depending
85 * how we first reach the Block.
87 static void merge_blocks(ir_node *n, void *env) {
91 /* clear the link field for ALL nodes first */
92 set_irn_link(n, NULL);
94 if (get_irn_op(n) == op_Block) {
96 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
97 /* GL @@@ : is this possible? if (get_opt_normalize()) -- added, all tests go through.
98 A different order of optimizations might cause problems. */
99 if (get_opt_normalize())
100 set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i)));
104 new_block = equivalent_node(n);
105 if (new_block != n && ! is_Bad(new_block))
106 exchange (n, new_block);
108 } else if (get_opt_optimize() && (get_irn_mode(n) == mode_X)) {
109 /* We will soon visit a block. Optimize it before visiting! */
110 ir_node *b = get_nodes_block(skip_Proj(n));
113 new_block = equivalent_node(b);
115 while (irn_not_visited(b) && (!is_Bad(new_block)) && (new_block != b)) {
116 /* We would have to run gigo if new is bad, so we
117 promote it directly below. Nevertheless, we sometimes reach a block
118 the first time through a dataflow node. In this case we optimized the
119 block as such and have to promote the Bad here. */
120 assert((get_opt_control_flow_straightening() ||
121 get_opt_control_flow_weak_simplification()) &&
122 ("strange flag setting"));
123 exchange (b, new_block);
125 new_block = equivalent_node(b);
128 /* normally, we would create a Bad block here, but this must be
129 * prevented, so just set it's cf to Bad.
131 if (is_Bad(new_block))
132 exchange(n, new_Bad());
138 * Remove cf from dead block by inspecting dominance info
139 * Do not replace blocks by Bad. This optimization shall
140 * ensure, that all Bad cfg preds are removed, and no new
141 * other Bads are introduced.
143 * Must be run in the post walker.
145 static void remove_dead_block_cf(ir_node *block, void *env)
149 /* check block predecessors and turn control flow into bad */
150 for (i = 0, n = get_Block_n_cfgpreds(block); i < n; ++i) {
151 ir_node *pred_X = get_Block_cfgpred(block, i);
153 if (! is_Bad(pred_X)) {
154 ir_node *pred_bl = get_nodes_block(skip_Proj(pred_X));
156 if (is_Bad(pred_bl) || (get_Block_dom_depth(pred_bl) == -1))
157 exchange (pred_X, new_Bad());
163 * Collects all Phi nodes in link list of Block.
164 * Marks all blocks "block_visited" if they contain a node other
166 * Replaces n by Bad if n is unreachable control flow. We do that
167 * in the post walker, so we catch all blocks.
169 static void collect_nodes(ir_node *n, void *env) {
170 if (is_no_Block(n)) {
171 ir_node *b = get_nodes_block(n);
173 if ((get_irn_op(n) == op_Phi)) {
174 /* Collect Phi nodes to compact ins along with block's ins. */
175 set_irn_link(n, get_irn_link(b));
178 else if ((get_irn_op(n) != op_Jmp) && !is_Bad(b)) { /* Check for non empty block. */
179 mark_Block_block_visited(b);
184 /** Returns true if pred is predecessor of block. */
185 static int is_pred_of(ir_node *pred, ir_node *b) {
188 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
189 ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
190 if (b_pred == pred) return 1;
196 /** Test wether we can optimize away pred block pos of b.
198 * @param b A block node.
199 * @param pos The position of the predecessor block to judge about.
201 * @returns The number of predecessors
203 * The test is rather tricky.
205 * The situation is something like the following:
213 * b merges the control flow of an if-then-else. We may not remove
214 * the 'then' _and_ the 'else' block of an 'if' if there is a Phi
215 * node in b, even if both are empty. The destruction of this Phi
216 * requires that a copy is added before the merge. We have to
217 * keep one of the case blocks to place the copies in.
219 * To perform the test for pos, we must regard preds before pos
220 * as already removed.
222 static int test_whether_dispensable(ir_node *b, int pos) {
223 int i, j, n_preds = 1;
225 ir_node *cfop = get_Block_cfgpred(b, pos);
226 ir_node *pred = get_nodes_block(cfop);
228 /* Bad blocks will be optimized away, so we don't need space for them */
232 if (get_Block_block_visited(pred) + 1
233 < get_irg_block_visited(current_ir_graph)) {
235 if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
236 /* Mark block so that is will not be removed: optimization is turned off. */
237 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
241 /* Seems to be empty. At least we detected this in collect_nodes. */
242 if (!get_irn_link(b)) {
243 /* There are no Phi nodes ==> all predecessors are dispensable. */
244 n_preds = get_Block_n_cfgpreds(pred);
246 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
247 Work preds < pos as if they were already removed. */
248 for (i = 0; i < pos; i++) {
249 ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
250 if (get_Block_block_visited(b_pred) + 1
251 < get_irg_block_visited(current_ir_graph)) {
252 for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
253 ir_node *b_pred_pred = get_nodes_block(get_Block_cfgpred(b_pred, j));
254 if (is_pred_of(b_pred_pred, pred)) dispensable = 0;
257 if (is_pred_of(b_pred, pred)) dispensable = 0;
260 for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
261 ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
262 if (is_pred_of(b_pred, pred)) dispensable = 0;
265 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
268 n_preds = get_Block_n_cfgpreds(pred);
278 * This method removed Bad cf preds from Blocks and Phis, and removes
279 * empty blocks. A block is empty if it only contains Phi and Jmp nodes.
281 * We first adapt Phi nodes, then Block nodes, as we need the old ins
282 * of the Block to adapt the Phi nodes. We do this by computing new
283 * in arrays, and then replacing the old ones. So far we compute new in arrays
284 * for all nodes, not regarding whether there is a possibility for optimization.
286 * For each predecessor p of a Block b there are three cases:
287 * 1. The predecessor p is a Bad node: just skip it. The in array of b shrinks by one.
288 * 2. The predecessor p is empty. Remove p. All predecessors of p are now
290 * 3. The predecessor p is a block containing useful code. Just keep p as is.
292 * For Phi nodes f we have to check the conditions at the Block of f.
293 * For cases 1 and 3 we proceed as for Blocks. For case 2 we can have two
295 * 2a: The old precessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED. In this
296 * case we proceed as for blocks. We remove pred_f. All
297 * predecessors of pred_f now are predecessors of f.
298 * 2b: The old predecessor of f is NOT in the block removed. It might be a Phi, too.
299 * We have to replicate f for each predecessor of the removed block. Or, with
300 * other words, the removed predecessor block has exactly one predecessor.
302 * Further there is a special case for self referencing blocks:
304 * then_b else_b then_b else_b
310 * | | | === optimized to ===> \ | | |
316 * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
317 * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
319 * @@@ It is negotiable whether we should do this ... there might end up a copy
320 * from the Phi in the loop when removing the Phis.
322 static void optimize_blocks(ir_node *b, void *env) {
323 int i, j, k, n, max_preds, n_preds, p_preds;
327 /* Count the number of predecessor if this block is merged with pred blocks
330 for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
331 max_preds += test_whether_dispensable(b, i);
333 in = xmalloc(max_preds * sizeof(*in));
336 printf(" working on "); DDMN(b);
337 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
338 pred = get_nodes_block(get_Block_cfgpred(b, i));
339 if (is_Bad(get_Block_cfgpred(b, i))) {
340 printf(" removing Bad %i\n ", i);
341 } else if (get_Block_block_visited(pred) +1
342 < get_irg_block_visited(current_ir_graph)) {
343 printf(" removing pred %i ", i); DDMN(pred);
344 } else { printf(" Nothing to do for "); DDMN(pred); }
346 * end Debug output -*/
348 /*- Fix the Phi nodes of the current block -*/
349 for (phi = get_irn_link(b); phi; ) {
350 assert(get_irn_op(phi) == op_Phi);
352 /* Find the new predecessors for the Phi */
354 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
355 pred = get_nodes_block(get_Block_cfgpred(b, i));
357 if (is_Bad(get_Block_cfgpred(b, i))) {
358 /* case Phi 1: Do nothing */
360 else if (get_Block_block_visited(pred) + 1
361 < get_irg_block_visited(current_ir_graph)) {
362 /* case Phi 2: It's an empty block and not yet visited. */
363 ir_node *phi_pred = get_Phi_pred(phi, i);
365 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
366 /* because of breaking loops, not all predecessors are Bad-clean,
367 * so we must check this here again */
368 if (! is_Bad(get_Block_cfgpred(pred, j))) {
369 if (get_nodes_block(phi_pred) == pred) {
371 assert(get_irn_op(phi_pred) == op_Phi); /* Block is empty!! */
373 in[p_preds++] = get_Phi_pred(phi_pred, j);
376 in[p_preds++] = phi_pred;
381 /* The Phi_pred node is replaced now if it is a Phi.
383 Somehow the removed Phi node can be used legally in loops.
384 Therefore we replace the old phi by the new one.
386 Further we have to remove the old Phi node by replacing it
387 by Bad. Else it will remain in the keepalive array of End
388 and cause illegal situations. So if there is no loop, we should
391 if (get_nodes_block(phi_pred) == pred) {
392 /* remove the Phi as it might be kept alive. Further there
393 might be other users. */
394 exchange(phi_pred, phi); /* geht, ist aber doch semantisch falsch! Warum?? */
398 in[p_preds++] = get_Phi_pred(phi, i);
401 assert(p_preds <= max_preds);
405 /* By removal of Bad ins the Phi might be degenerated. */
406 exchange(phi, in[0]);
408 set_irn_in(phi, p_preds, in);
410 phi = get_irn_link(phi);
413 /*- This happens only if merge between loop backedge and single loop entry.
414 See special case above. -*/
415 for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
416 pred = get_nodes_block(get_Block_cfgpred(b, k));
418 if (get_Block_block_visited(pred) + 1 < get_irg_block_visited(current_ir_graph)) {
419 /* we found a predecessor block at position k that will be removed */
420 for (phi = get_irn_link(pred); phi;) {
422 * the previous phase may already changed the phi, and even
423 * removed it at all, so check here if this node is still a phi
425 if (get_irn_op(phi) == op_Phi) {
428 /* move this phi from the predecessor into the block b */
429 set_nodes_block(phi, b);
431 /* first, copy all 0..k-1 predecessors */
432 for (i = 0; i < k; i++) {
433 pred = get_nodes_block(get_Block_cfgpred(b, i));
435 if (is_Bad(get_Block_cfgpred(b, i))) {
437 } else if (get_Block_block_visited(pred) + 1
438 < get_irg_block_visited(current_ir_graph)) {
439 /* It's an empty block and not yet visited. */
440 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
441 /* @@@ Hier brauche ich Schleifeninformation!!! Kontrollflusskante
442 muss Rueckwaertskante sein! (An allen vier in[q_preds] = phi
443 Anweisungen.) Trotzdem tuts bisher!! */
444 if (! is_Bad(get_Block_cfgpred(pred, j)))
452 /* now we are at k, copy the phi predecessors */
453 pred = get_nodes_block(get_Block_cfgpred(b, k));
454 for (i = 0; i < get_Phi_n_preds(phi); i++) {
455 if (! is_Bad(get_Block_cfgpred(pred, i)))
456 in[q_preds++] = get_Phi_pred(phi, i);
459 /* and now all the rest */
460 for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
461 pred = get_nodes_block(get_Block_cfgpred(b, i));
463 if (is_Bad(get_Block_cfgpred(b, i))) {
465 } else if (get_Block_block_visited(pred) +1
466 < get_irg_block_visited(current_ir_graph)) {
467 /* It's an empty block and not yet visited. */
468 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
469 if (! is_Bad(get_Block_cfgpred(pred, j)))
479 exchange(phi, in[0]);
481 set_irn_in(phi, q_preds, in);
483 assert(q_preds <= max_preds);
484 // assert(p_preds == q_preds && "Wrong Phi Fix");
486 phi = get_irn_link(phi);
491 /*- Fix the block -*/
493 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
494 pred = get_nodes_block(get_Block_cfgpred(b, i));
496 if (is_Bad(get_Block_cfgpred(b, i))) {
497 /* case 1: Do nothing */
498 } else if (get_Block_block_visited(pred) +1
499 < get_irg_block_visited(current_ir_graph)) {
500 /* case 2: It's an empty block and not yet visited. */
501 assert(get_Block_n_cfgpreds(b) > 1);
502 /* Else it should be optimized by equivalent_node. */
503 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
504 ir_node *pred_block = get_Block_cfgpred(pred, j);
506 /* because of breaking loops, not all predecessors are Bad-clean,
507 * so we must check this here again */
508 if (! is_Bad(pred_block))
509 in[n_preds++] = pred_block;
511 /* Remove block as it might be kept alive. */
512 exchange(pred, b/*new_Bad()*/);
515 in[n_preds++] = get_Block_cfgpred(b, i);
518 assert(n_preds <= max_preds);
520 set_irn_in(b, n_preds, in);
522 assert(get_irn_link(b) == NULL || (n_preds == p_preds && "Wrong Phi Fix"));
528 /* Optimizations of the control flow that also require changes of Phi nodes.
530 * This optimization performs two passes over the graph.
532 * The first pass collects all Phi nodes in a link list in the block
533 * nodes. Further it performs simple control flow optimizations.
534 * Finally it marks all blocks that do not contain useful
535 * computations, i.e., these blocks might be removed.
537 * The second pass performs the optimizations intended by this algorithm.
538 * It walks only over block nodes and adapts these and the Phi nodes in these blocks,
539 * which it finds in a linked list computed by the first pass.
541 * We use the block_visited flag to mark empty blocks in the first
543 * @@@ It would be better to add a struct in the link field
544 * that keeps the Phi list and the mark. Place it on an obstack, as
545 * we will lose blocks and thereby generate mem leaks.
547 void optimize_cf(ir_graph *irg) {
550 ir_node *end = get_irg_end(irg);
551 ir_graph *rem = current_ir_graph;
552 irg_dom_state dom_state = get_irg_dom_state(current_ir_graph);
553 current_ir_graph = irg;
555 /* Handle graph state */
556 assert(get_irg_phase_state(irg) != phase_building);
557 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
558 set_irg_outs_inconsistent(current_ir_graph);
559 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
560 set_irg_dom_inconsistent(current_ir_graph);
562 if (dom_state == dom_consistent && get_opt_optimize() && get_opt_unreachable_code()) {
563 ir_node *end = get_irg_end(irg);
565 /* we have dominace info, we can kill dead block */
566 irg_block_walk_graph(irg, NULL, remove_dead_block_cf, NULL);
568 /* fix the keep-alives */
569 for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
570 ir_node *ka = get_End_keepalive(end, i);
572 if (is_Block(ka) && (get_Block_dom_depth(ka) == -1))
573 set_End_keepalive(end, i, new_Bad());
574 if (is_Phi(ka) && (get_Block_dom_depth(get_nodes_block(ka)) == -1))
575 set_End_keepalive(end, i, new_Bad());
579 irg_block_walk_graph(current_ir_graph, NULL, remove_senseless_conds, NULL);
580 /* Use block visited flag to mark non-empty blocks. */
581 inc_irg_block_visited(irg);
582 irg_walk(end, merge_blocks, collect_nodes, NULL);
584 /* Optimize the standard code. */
585 irg_block_walk(get_irg_end_block(irg), optimize_blocks, NULL, NULL);
587 /* Walk all keep alives, optimize them if block, add to new in-array
588 for end if useful. */
589 in = NEW_ARR_F (ir_node *, 1);
590 in[0] = get_nodes_block(end);
591 inc_irg_visited(current_ir_graph);
593 for (i = 0; i < get_End_n_keepalives(end); i++) {
594 ir_node *ka = get_End_keepalive(end, i);
596 if (irn_not_visited(ka)) {
597 if ((get_irn_op(ka) == op_Block) && Block_not_block_visited(ka)) {
598 set_irg_block_visited(current_ir_graph, /* Don't walk all the way to Start. */
599 get_irg_block_visited(current_ir_graph)-1);
600 irg_block_walk(ka, optimize_blocks, NULL, NULL);
601 mark_irn_visited(ka);
602 ARR_APP1 (ir_node *, in, ka);
603 } else if (get_irn_op(ka) == op_Phi) {
604 mark_irn_visited(ka);
605 ARR_APP1 (ir_node *, in, ka);
609 /* DEL_ARR_F(end->in); GL @@@ tut nicht ! */
613 /* the verifyer doesn't work yet with floating nodes */
614 if (get_irg_pinned(irg) == op_pin_state_pinned) {
615 /* after optimize_cf(), only Bad data flow may remain. */
616 if (irg_vrfy_bads(irg, BAD_DF | BAD_BLOCK | TUPLE)) {
617 dump_ir_block_graph(irg, "-vrfy-cf");
618 dump_ir_graph(irg, "-vrfy-cf");
619 fprintf(stderr, "VRFY_BAD in optimize_cf()\n");
623 current_ir_graph = rem;