nsz Git - libfirm/blob - ir/opt/cfopt.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/cfopt.c
   4  * Purpose:     control flow optimizations
   5  * Author:
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 1998-2004 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11
  12 #ifdef HAVE_CONFIG_H
  13 # include <config.h>
  14 #endif
  15
  16 #include <assert.h>
  17
  18 #include "irnode_t.h"
  19 #include "irgraph_t.h"
  20 #include "irprog_t.h"
  21
  22 #include "ircons.h"
  23 #include "iropt_t.h"
  24 #include "irgwalk.h"
  25 #include "irvrfy.h"
  26
  27 #include "array.h"
  28
  29 #include "irouts.h"
  30 #include "irbackedge_t.h"
  31
  32 #include "irflag_t.h"
  33 #include "firmstat.h"
  34
  35 #include "cfopt.h"
  36
  37 /*------------------------------------------------------------------*/
  38 /* Control flow optimization.                                       */
  39 /* Removes Bad control flow predecessors and empty blocks.  A block */
  40 /* is empty if it contains only a Jmp node.                         */
  41 /* Blocks can only be removed if they are not needed for the        */
  42 /* semantics of Phi nodes.                                          */
  43 /*------------------------------------------------------------------*/
  44
  45 /**
  46  * Removes Tuples from Block control flow predecessors.
  47  * Optimizes blocks with equivalent_node().  This is tricky,
  48  * as we want to avoid nodes that have as block predecessor Bads.
  49  * Therefore we also optimize at control flow operations, depending
  50  * how we first reach the Block.
  51  */
  52 static void merge_blocks(ir_node *n, void *env) {
  53   int i;
  54   ir_node *new_block;
  55
  56   set_irn_link(n, NULL);
  57
  58   if (get_irn_op(n) == op_Block) {
  59     /* Remove Tuples */
  60     for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
  61       /* GL @@@ : is this possible? if (get_opt_normalize()) -- added, all tests go through.
  62          A different order of optimizations might cause problems. */
  63       if (get_opt_normalize())
  64         set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i)));
  65     }
  66     new_block = equivalent_node(n);
  67     if (new_block != n)
  68       exchange (n, new_block);
  69
  70   } else if (get_opt_optimize() && (get_irn_mode(n) == mode_X)) {
  71     /* We will soon visit a block.  Optimize it before visiting! */
  72     ir_node *b        = get_nodes_block(n);
  73
  74     if (!is_Bad(b)) {
  75       new_block = equivalent_node(b);
  76
  77       while (irn_not_visited(b) && (!is_Bad(new_block)) && (new_block != b)) {
  78         /* We would have to run gigo if new is bad, so we
  79            promote it directly below. Nevertheless, we somtimes reach a block
  80            the first time through a dataflow node.  In this case we optimized the
  81            block as such and have to promote the Bad here. */
  82         assert(((b == new_block) ||
  83             get_opt_control_flow_straightening() ||
  84             get_opt_control_flow_weak_simplification()) &&
  85            ("strange flag setting"));
  86         exchange (b, new_block);
  87         b = new_block;
  88         new_block = equivalent_node(b);
  89       }
  90       b = new_block;
  91     }
  92
  93     /*
  94      * BEWARE: do not kill floating notes here as they might be needed in
  95      * valid blocks because of global CSE.
  96      */
  97     if (is_Bad(b) && get_opt_normalize() &&
  98         get_op_pinned(get_irn_op(n)) == op_pin_state_pinned)
  99       exchange(n, new_Bad());
 100   }
 101 }
 102
 103 /**
 104  * Collects all Phi nodes in link list of Block.
 105  * Marks all blocks "block_visited" if they contain a node other
 106  * than Jmp.
 107  * Replaces n by Bad if n is unreachable control flow. We do that
 108  * in the post walker, so we catch all blocks.
 109  */
 110 static void collect_nodes(ir_node *n, void *env) {
 111   irg_dom_state *dom_state = env;
 112
 113   if (is_no_Block(n)) {
 114     ir_node *b = get_nodes_block(n);
 115
 116     /*
 117      * BEWARE: do not kill floating notes here as they might be needed in
 118      * valid blocks because of global CSE.
 119      */
 120     if (is_Bad(b) &&
 121         get_op_pinned(get_irn_op(n)) == op_pin_state_pinned) {
 122       /* previous merge_blocks() may have killed dead blocks */
 123       exchange(n, new_Bad());
 124     }
 125     else if ((get_irn_op(n) == op_Phi)) {
 126       /* Collect Phi nodes to compact ins along with block's ins. */
 127       set_irn_link(n, get_irn_link(b));
 128       set_irn_link(b, n);
 129     } else if ((get_irn_op(n) != op_Jmp) && !is_Bad(b)) {  /* Check for non empty block. */
 130       mark_Block_block_visited(b);
 131     }
 132   }
 133   else {
 134     /* delete dead blocks: if we have dominator information, this can easily be detected
 135      * BEWARE: don't kill the end block */
 136     if (*dom_state == dom_consistent &&
 137         n != get_irg_end_block(current_ir_graph) &&
 138         get_Block_dom_depth(n) == -1 &&
 139         get_opt_unreachable_code()) {
 140       exchange (n, new_Bad());
 141     }
 142   }
 143 }
 144
 145 /** Returns true if pred is predecessor of block. */
 146 static int is_pred_of(ir_node *pred, ir_node *b) {
 147   int i;
 148   for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 149     ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
 150     if (b_pred == pred) return 1;
 151   }
 152   return 0;
 153 }
 154
 155
 156 static int test_whether_dispensable(ir_node *b, int pos) {
 157   int i, j, n_preds = 1;
 158   int dispensable = 1;
 159   ir_node *cfop = get_Block_cfgpred(b, pos);
 160   ir_node *pred = get_nodes_block(cfop);
 161
 162   if (get_Block_block_visited(pred) + 1
 163       < get_irg_block_visited(current_ir_graph)) {
 164     if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
 165       /* Mark block so that is will not be removed. */
 166       set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
 167       return 1;
 168     }
 169     /* Seems to be empty. */
 170     if (!get_irn_link(b)) {
 171       /* There are no Phi nodes ==> dispensable. */
 172       n_preds = get_Block_n_cfgpreds(pred);
 173     } else {
 174       /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
 175          Work preds < pos as if they were already removed. */
 176       for (i = 0; i < pos; i++) {
 177         ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
 178         if (get_Block_block_visited(b_pred) + 1
 179             < get_irg_block_visited(current_ir_graph)) {
 180           for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
 181             ir_node *b_pred_pred = get_nodes_block(get_Block_cfgpred(b_pred, j));
 182             if (is_pred_of(b_pred_pred, pred)) dispensable = 0;
 183           }
 184         } else {
 185           if (is_pred_of(b_pred, pred)) dispensable = 0;
 186         }
 187       }
 188       for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
 189         ir_node *b_pred = get_nodes_block(get_Block_cfgpred(b, i));
 190         if (is_pred_of(b_pred, pred)) dispensable = 0;
 191       }
 192       if (!dispensable) {
 193         set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
 194         n_preds = 1;
 195       } else {
 196         n_preds = get_Block_n_cfgpreds(pred);
 197       }
 198     }
 199   }
 200
 201   return n_preds;
 202 }
 203
 204 static void optimize_blocks(ir_node *b, void *env) {
 205   int i, j, k, max_preds, n_preds;
 206   ir_node *pred, *phi;
 207   ir_node **in;
 208
 209   /* Count the number of predecessor if this block is merged with pred blocks
 210      that are empty. */
 211   max_preds = 0;
 212   for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 213     max_preds += test_whether_dispensable(b, i);
 214   }
 215   in = (ir_node **) malloc(max_preds * sizeof(ir_node *));
 216
 217 /*-
 218   printf(" working on "); DDMN(b);
 219   for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 220     pred = get_nodes_block(get_Block_cfgpred(b, i));
 221     if (is_Bad(get_Block_cfgpred(b, i))) {
 222       printf("  removing Bad %i\n ", i);
 223     } else if (get_Block_block_visited(pred) +1
 224            < get_irg_block_visited(current_ir_graph)) {
 225       printf("  removing pred %i ", i); DDMN(pred);
 226     } else { printf("  Nothing to do for "); DDMN(pred); }
 227   }
 228   * end Debug output -*/
 229
 230   /*- Fix the Phi nodes -*/
 231   phi = get_irn_link(b);
 232   while (phi) {
 233     assert(get_irn_op(phi) == op_Phi);
 234     /* Find the new predecessors for the Phi */
 235     n_preds = 0;
 236     for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 237       pred = get_nodes_block(get_Block_cfgpred(b, i));
 238       if (is_Bad(get_Block_cfgpred(b, i))) {
 239         /* Do nothing */
 240       } else if (get_Block_block_visited(pred) + 1
 241                  < get_irg_block_visited(current_ir_graph)) {
 242         /* It's an empty block and not yet visited. */
 243         ir_node *phi_pred = get_Phi_pred(phi, i);
 244
 245         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 246           if (get_nodes_block(phi_pred) == pred) {
 247             assert(get_irn_op(phi_pred) == op_Phi);  /* Block is empty!! */
 248             in[n_preds] = get_Phi_pred(phi_pred, j);
 249           } else {
 250             in[n_preds] = phi_pred;
 251           }
 252           n_preds++;
 253         }
 254         /* The Phi_pred node is replaced now if it is a Phi.
 255            In Schleifen kann offenbar der entfernte Phi Knoten legal verwendet werden.
 256            Daher muss der Phiknoten durch den neuen ersetzt werden.
 257            Weiter muss der alte Phiknoten entfernt werden (durch ersetzen oder
 258            durch einen Bad) damit er aus den keep_alive verschwinden kann.
 259            Man sollte also, falls keine Schleife vorliegt, exchange mit new_Bad
 260            aufrufen.  */
 261         if (get_nodes_block(phi_pred) == pred) {
 262           /* remove the Phi as it might be kept alive. Further there
 263              might be other users. */
 264           exchange(phi_pred, phi);  /* geht, ist aber doch semantisch falsch! Warum?? */
 265         }
 266       } else {
 267         in[n_preds] = get_Phi_pred(phi, i);
 268         n_preds ++;
 269       }
 270     }
 271     /* Fix the node */
 272     if (n_preds == 1)
 273       exchange(phi, in[0]);
 274     else
 275       set_irn_in(phi, n_preds, in);
 276
 277     phi = get_irn_link(phi);
 278   }
 279
 280   /*- This happens only if merge between loop backedge and single loop entry. -*/
 281   for (k = 0; k < get_Block_n_cfgpreds(b); k++) {
 282     pred = get_nodes_block(get_Block_cfgpred(b, k));
 283     if (get_Block_block_visited(pred)+1 < get_irg_block_visited(current_ir_graph)) {
 284       phi = get_irn_link(pred);
 285       while (phi) {
 286         if (get_irn_op(phi) == op_Phi) {
 287           set_nodes_block(phi, b);
 288
 289           n_preds = 0;
 290           for (i = 0; i < k; i++) {
 291             pred = get_nodes_block(get_Block_cfgpred(b, i));
 292             if (is_Bad(get_Block_cfgpred(b, i))) {
 293               /* Do nothing */
 294             } else if (get_Block_block_visited(pred) +1
 295                < get_irg_block_visited(current_ir_graph)) {
 296               /* It's an empty block and not yet visited. */
 297               for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 298                 /* @@@ Hier brauche ich Schleifeninformation!!! Kontrollflusskante
 299                    muss Rueckwaertskante sein! (An allen vier in[n_preds] = phi
 300                    Anweisungen.) Trotzdem tuts bisher!! */
 301                 in[n_preds] = phi;
 302                 n_preds++;
 303               }
 304             } else {
 305               in[n_preds] = phi;
 306               n_preds++;
 307             }
 308           }
 309           for (i = 0; i < get_Phi_n_preds(phi); i++) {
 310             in[n_preds] = get_Phi_pred(phi, i);
 311             n_preds++;
 312           }
 313           for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
 314             pred = get_nodes_block(get_Block_cfgpred(b, i));
 315             if (is_Bad(get_Block_cfgpred(b, i))) {
 316               /* Do nothing */
 317             } else if (get_Block_block_visited(pred) +1
 318                < get_irg_block_visited(current_ir_graph)) {
 319               /* It's an empty block and not yet visited. */
 320               for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 321                 in[n_preds] = phi;
 322                 n_preds++;
 323               }
 324             } else {
 325               in[n_preds] = phi;
 326               n_preds++;
 327             }
 328           }
 329           if (n_preds == 1)
 330             exchange(phi, in[0]);
 331           else
 332             set_irn_in(phi, n_preds, in);
 333         }
 334         phi = get_irn_link(phi);
 335       }
 336     }
 337   }
 338
 339   /*- Fix the block -*/
 340   n_preds = 0;
 341   for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 342     pred = get_nodes_block(get_Block_cfgpred(b, i));
 343     if (is_Bad(get_Block_cfgpred(b, i))) {
 344       /* Do nothing */
 345     } else if (get_Block_block_visited(pred) +1
 346            < get_irg_block_visited(current_ir_graph)) {
 347       /* It's an empty block and not yet visited. */
 348       assert(get_Block_n_cfgpreds(b) > 1);
 349                         /* Else it should be optimized by equivalent_node. */
 350       for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 351         in[n_preds] = get_Block_cfgpred(pred, j);
 352         n_preds++;
 353       }
 354       /* Remove block as it might be kept alive. */
 355       exchange(pred, b/*new_Bad()*/);
 356     } else {
 357       in[n_preds] = get_Block_cfgpred(b, i);
 358       n_preds ++;
 359     }
 360   }
 361   set_irn_in(b, n_preds, in);
 362   free(in);
 363 }
 364
 365 void optimize_cf(ir_graph *irg) {
 366   int i;
 367   ir_node **in;
 368   ir_node *end = get_irg_end(irg);
 369   ir_graph *rem = current_ir_graph;
 370   irg_dom_state dom_state = get_irg_dom_state(current_ir_graph);
 371   current_ir_graph = irg;
 372
 373   /* Handle graph state */
 374   assert(get_irg_phase_state(irg) != phase_building);
 375   if (get_irg_outs_state(current_ir_graph) == outs_consistent)
 376     set_irg_outs_inconsistent(current_ir_graph);
 377   if (get_irg_dom_state(current_ir_graph) == dom_consistent)
 378     set_irg_dom_inconsistent(current_ir_graph);
 379
 380   /* Use block visited flag to mark non-empty blocks. */
 381   inc_irg_block_visited(irg);
 382   irg_walk(end, merge_blocks, collect_nodes, &dom_state);
 383
 384   /* Optimize the standard code. */
 385   irg_block_walk(get_irg_end_block(irg), optimize_blocks, NULL, NULL);
 386
 387   /* Walk all keep alives, optimize them if block, add to new in-array
 388      for end if useful. */
 389   in = NEW_ARR_F (ir_node *, 1);
 390   in[0] = get_nodes_block(end);
 391   inc_irg_visited(current_ir_graph);
 392   for(i = 0; i < get_End_n_keepalives(end); i++) {
 393     ir_node *ka = get_End_keepalive(end, i);
 394     if (irn_not_visited(ka)) {
 395       if ((get_irn_op(ka) == op_Block) && Block_not_block_visited(ka)) {
 396         set_irg_block_visited(current_ir_graph,  /* Don't walk all the way to Start. */
 397               get_irg_block_visited(current_ir_graph)-1);
 398         irg_block_walk(ka, optimize_blocks, NULL, NULL);
 399         mark_irn_visited(ka);
 400         ARR_APP1 (ir_node *, in, ka);
 401       } else if (get_irn_op(ka) == op_Phi) {
 402         mark_irn_visited(ka);
 403         ARR_APP1 (ir_node *, in, ka);
 404       }
 405     }
 406   }
 407   /* DEL_ARR_F(end->in);   GL @@@ tut nicht ! */
 408   end->in = in;
 409
 410   /* after optimize_cf(), only Bad data flow may remain. */
 411   if (irg_vrfy_bads(irg, BAD_DF | BAD_BLOCK | TUPLE)) {
 412     dump_ir_block_graph(irg, "-vrfy-cf");
 413     dump_ir_graph(irg, "-vrfy-cf");
 414     fprintf(stderr, "VRFY_BAD in optimize_cf()\n");
 415   }
 416
 417   current_ir_graph = rem;
 418 }