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