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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Control flow optimizations.
  23  * @author  Goetz Lindenmaier, Michael Beck, Sebastian Hack
  24  * @version $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include "iroptimize.h"
  31
  32 #include <assert.h>
  33
  34 #include "plist.h"
  35 #include "xmalloc.h"
  36 #include "irnode_t.h"
  37 #include "irgraph_t.h"
  38 #include "irprog_t.h"
  39
  40 #include "ircons.h"
  41 #include "iropt_t.h"
  42 #include "irgwalk.h"
  43 #include "irgmod.h"
  44 #include "irdump.h"
  45 #include "irvrfy.h"
  46 #include "iredges.h"
  47
  48 #include "array.h"
  49
  50 #include "irouts.h"
  51 #include "irbackedge_t.h"
  52
  53 #include "irflag_t.h"
  54 #include "firmstat.h"
  55
  56 #include "iropt_dbg.h"
  57
  58 /*------------------------------------------------------------------*/
  59 /* Control flow optimization.                                       */
  60 /*                                                                  */
  61 /* Removes Bad control flow predecessors and empty blocks.  A block */
  62 /* is empty if it contains only a Jmp node.                         */
  63 /* Blocks can only be removed if they are not needed for the        */
  64 /* semantics of Phi nodes.                                          */
  65 /* Further, we NEVER remove labeled blocks (even if we could move   */
  66 /* the label.                                                       */
  67 /*------------------------------------------------------------------*/
  68
  69 #define set_Block_removable(block)      set_Block_mark(block, 1)
  70 #define set_Block_non_removable(block)  set_Block_mark(block, 0)
  71 #define is_Block_removable(block)       (get_Block_mark(block) != 0)
  72
  73 /**
  74  * Replace binary Conds that jumps twice into the same block
  75  * by a simple Jmp.
  76  * E.g.
  77  * @verbatim
  78  *               Cond                     Jmp  Bad
  79  *             /       \                   |   /
  80  *       ProjX True   ProjX False  ==>     |  /
  81  *             \       /                   | /
  82  *               Block                    Block
  83  * @endverbatim
  84  *
  85  * Such pattern are the result of if-conversion.
  86  *
  87  * Note that the simple case that Block has only these two
  88  * predecessors are already handled in equivalent_node_Block().
  89  */
  90 static int remove_senseless_conds(ir_node *bl) {
  91         int i, j;
  92         int n = get_Block_n_cfgpreds(bl);
  93         int changed = 0;
  94
  95         for (i = 0; i < n; ++i) {
  96                 ir_node *pred_i = get_Block_cfgpred(bl, i);
  97                 ir_node *cond_i = skip_Proj(pred_i);
  98
  99                 /* binary Cond */
 100                 if (is_Cond(cond_i) && get_irn_mode(get_Cond_selector(cond_i)) == mode_b) {
 101
 102                         for (j = i + 1; j < n; ++j) {
 103                                 ir_node *pred_j = get_Block_cfgpred(bl, j);
 104                                 ir_node *cond_j = skip_Proj(pred_j);
 105
 106                                 if (cond_j == cond_i) {
 107                                         ir_node *jmp = new_r_Jmp(current_ir_graph, get_nodes_block(cond_i));
 108                                         set_irn_n(bl, i, jmp);
 109                                         set_irn_n(bl, j, new_Bad());
 110
 111                                         DBG_OPT_IFSIM2(cond_i, jmp);
 112                                         changed = 1;
 113                                         break;
 114                                 }
 115                         }
 116                 }
 117         }
 118         return changed;
 119 }
 120
 121 /** An environment for merge_blocks and collect nodes. */
 122 typedef struct _merge_env {
 123         int changed;    /**< Set if the graph was changed. */
 124         int phis_moved; /**< Set if Phi nodes were moved. */
 125         plist_t *list;  /**< Helper list for all found Switch Conds. */
 126 } merge_env;
 127
 128 /**
 129  * Removes Tuples from Block control flow predecessors.
 130  * Optimizes blocks with equivalent_node().  This is tricky,
 131  * as we want to avoid nodes that have as block predecessor Bads.
 132  * Therefore we also optimize at control flow operations, depending
 133  * how we first reach the Block.
 134  */
 135 static void merge_blocks(ir_node *node, void *ctx) {
 136         int i;
 137         ir_node *new_block;
 138         merge_env *env = ctx;
 139
 140         /* clear the link field for ALL nodes first */
 141         set_irn_link(node, NULL);
 142
 143         if (is_Block(node)) {
 144                 /* Remove Tuples */
 145                 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 146                         ir_node *pred = get_Block_cfgpred(node, i);
 147                         ir_node *skipped = skip_Tuple(pred);
 148                         if (pred != skipped) {
 149                                 set_Block_cfgpred(node, i, skipped);
 150                                 env->changed = 1;
 151                         }
 152                 }
 153
 154                 /* see below */
 155                 new_block = equivalent_node(node);
 156                 if (new_block != node && ! is_Block_dead(new_block)) {
 157                         exchange(node, new_block);
 158                         env->changed = 1;
 159                 }
 160
 161         } else if (get_opt_optimize() && (get_irn_mode(node) == mode_X)) {
 162                 /* We will soon visit a block.  Optimize it before visiting! */
 163                 ir_node *b = get_nodes_block(skip_Proj(node));
 164
 165                 if (!is_Block_dead(b)) {
 166                         new_block = equivalent_node(b);
 167
 168                         while (irn_not_visited(b) && (!is_Block_dead(new_block)) && (new_block != b)) {
 169                                 /* We would have to run gigo() if new is bad, so we
 170                                    promote it directly below. Nevertheless, we sometimes reach a block
 171                                    the first time through a dataflow node.  In this case we optimized the
 172                                    block as such and have to promote the Bad here. */
 173                                 assert((get_opt_control_flow_straightening() ||
 174                                         get_opt_control_flow_weak_simplification()) &&
 175                                         ("strange flag setting"));
 176                                 exchange(b, new_block);
 177                                 env->changed = 1;
 178                                 b = new_block;
 179                                 new_block = equivalent_node(b);
 180                         }
 181
 182                         /* normally, we would create a Bad block here, but this must be
 183                          * prevented, so just set it's cf to Bad.
 184                          */
 185                         if (is_Block_dead(new_block)) {
 186                                 exchange(node, new_Bad());
 187                                 env->changed = 1;
 188                         }
 189                 }
 190         }
 191 }
 192
 193 /**
 194  * Block walker removing control flow from dead block by
 195  * inspecting dominance info.
 196  * Do not replace blocks by Bad.  This optimization shall
 197  * ensure, that all Bad control flow predecessors are
 198  * removed, and no new other Bads are introduced.
 199  * Further removed useless Conds and clear the mark of all blocks.
 200  *
 201  * Must be run in the post walker.
 202  */
 203 static void remove_unreachable_blocks_and_conds(ir_node *block, void *env) {
 204         int i;
 205         int *changed = env;
 206
 207         /* Check block predecessors and turn control flow into bad.
 208            Beware of Tuple, kill them. */
 209         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
 210                 ir_node *pred_X  = get_Block_cfgpred(block, i);
 211                 ir_node *skipped = skip_Tuple(pred_X);
 212
 213                 if (! is_Bad(skipped)) {
 214                         ir_node *pred_bl = get_nodes_block(skip_Proj(skipped));
 215
 216                         if (is_Block_dead(pred_bl) || (get_Block_dom_depth(pred_bl) < 0)) {
 217                                 set_Block_dead(pred_bl);
 218                                 exchange(pred_X, new_Bad());
 219                                 *changed = 1;
 220                         } else if (skipped != pred_X) {
 221                                 set_Block_cfgpred(block, i, skipped);
 222                                 *changed = 1;
 223                         }
 224                 }
 225         }
 226
 227         *changed |= remove_senseless_conds(block);
 228
 229         /* clear the block mark of all blocks */
 230         set_Block_removable(block);
 231 }
 232
 233 /**
 234  * Collects all Phi nodes in link list of Block.
 235  * Marks all blocks "non_removable" if they contain a node other
 236  * than Jmp (and Proj).
 237  * Links all Proj nodes to their predecessors.
 238  * Collects all switch-Conds in a list.
 239  */
 240 static void collect_nodes(ir_node *n, void *ctx) {
 241         ir_opcode code = get_irn_opcode(n);
 242         merge_env *env = ctx;
 243
 244         if (code == iro_Block) {
 245                 /* mark the block as non-removable if it is labeled */
 246                 if (has_Block_label(n))
 247                         set_Block_non_removable(n);
 248         } else {
 249                 ir_node *b = get_nodes_block(n);
 250
 251                 if (code == iro_Phi && get_irn_arity(n) > 0) {
 252                         /* Collect Phi nodes to compact ins along with block's ins. */
 253                         set_irn_link(n, get_irn_link(b));
 254                         set_irn_link(b, n);
 255                 } else if (code != iro_Jmp && !is_Bad(b)) {  /* Check for non-empty block. */
 256                         set_Block_non_removable(b);
 257
 258                         if (code == iro_Proj) {               /* link Proj nodes */
 259                                 ir_node *pred = get_Proj_pred(n);
 260
 261                                 set_irn_link(n, get_irn_link(pred));
 262                                 set_irn_link(pred, n);
 263                         } else if (code == iro_Cond) {
 264                                 ir_node *sel = get_Cond_selector(n);
 265                                 if (mode_is_int(get_irn_mode(sel))) {
 266                                         /* found a switch-Cond, collect */
 267                                         plist_insert_back(env->list, n);
 268                                 }
 269                         }
 270                 }
 271         }
 272 }
 273
 274 /** Returns true if pred is predecessor of block. */
 275 static int is_pred_of(ir_node *pred, ir_node *b) {
 276         int i;
 277
 278         for (i = get_Block_n_cfgpreds(b) - 1; i >= 0; --i) {
 279                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 280                 if (b_pred == pred)
 281                         return 1;
 282         }
 283         return 0;
 284 }
 285
 286 /** Test whether we can optimize away pred block pos of b.
 287  *
 288  *  @param  b    A block node.
 289  *  @param  pos  The position of the predecessor block to judge about.
 290  *
 291  *  @returns     The number of predecessors
 292  *
 293  *  The test is rather tricky.
 294  *
 295  *  The situation is something like the following:
 296  *  @verbatim
 297  *                 if-block
 298  *                  /   \
 299  *              then-b  else-b
 300  *                  \   /
 301  *                    b
 302  *  @endverbatim
 303  *
 304  *  b merges the control flow of an if-then-else.  We may not remove
 305  *  the 'then' _and_ the 'else' block of an 'if' if there is a Phi
 306  *  node in b, even if both are empty.  The destruction of this Phi
 307  *  requires that a copy is added before the merge.  We have to
 308  *  keep one of the case blocks to place the copies in.
 309  *
 310  *  To perform the test for pos, we must regard predecessors before pos
 311  *  as already removed.
 312  **/
 313 static int test_whether_dispensable(ir_node *b, int pos) {
 314         int i, j, n_preds = 1;
 315         ir_node *pred = get_Block_cfgpred_block(b, pos);
 316
 317         /* Bad blocks will be optimized away, so we don't need space for them */
 318         if (is_Block_dead(pred))
 319                 return 0;
 320
 321         if (is_Block_removable(pred)) {
 322                 if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
 323                         /* Mark block so that is will not be removed: optimization is turned off. */
 324                         set_Block_non_removable(pred);
 325                         return 1;
 326                 }
 327
 328                 /* Seems to be empty. At least we detected this in collect_nodes. */
 329                 if (get_irn_link(b) == NULL) {
 330                         /* There are no Phi nodes ==> all predecessors are dispensable. */
 331                         n_preds = get_Block_n_cfgpreds(pred);
 332                 } else {
 333                         /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
 334                            Handle all pred blocks with preds < pos as if they were already removed. */
 335                         for (i = 0; i < pos; i++) {
 336                                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 337                                 if (! is_Block_dead(b_pred) && is_Block_removable(b_pred)) {
 338                                         for (j = get_Block_n_cfgpreds(b_pred) - 1; j >= 0; --j) {
 339                                                 ir_node *b_pred_pred = get_Block_cfgpred_block(b_pred, j);
 340                                                 if (is_pred_of(b_pred_pred, pred))
 341                                                         goto non_dispensable;
 342                                         }
 343                                 } else {
 344                                         if (is_pred_of(b_pred, pred))
 345                                                 goto non_dispensable;
 346                                 }
 347                         }
 348                         for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
 349                                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 350                                 if (is_pred_of(b_pred, pred))
 351                                         goto non_dispensable;
 352                         }
 353                         /* if we get here, the block is dispensable */
 354                         n_preds = get_Block_n_cfgpreds(pred);
 355                 }
 356         }
 357
 358         return n_preds;
 359
 360 non_dispensable:
 361         set_Block_non_removable(pred);
 362         return 1;
 363 }
 364
 365 /**
 366  * This method removed Bad cf predecessors from Blocks and Phis, and removes
 367  * empty blocks.  A block is empty if it only contains Phi and Jmp nodes.
 368  *
 369  * We first adapt Phi nodes, then Block nodes, as we need the old ins
 370  * of the Block to adapt the Phi nodes.  We do this by computing new
 371  * in arrays, and then replacing the old ones.  So far we compute new in arrays
 372  * for all nodes, not regarding whether there is a possibility for optimization.
 373  *
 374  * For each predecessor p of a Block b there are three cases:
 375  *  -1. The predecessor p is a Bad node:  just skip it.  The in array of b shrinks by one.
 376  *  -2. The predecessor p is empty.  Remove p.  All predecessors of p are now
 377  *      predecessors of b.
 378  *  -3. The predecessor p is a block containing useful code.  Just keep p as is.
 379  *
 380  * For Phi nodes f we have to check the conditions at the Block of f.
 381  * For cases 1 and 3 we proceed as for Blocks.  For case 2 we can have two
 382  * cases:
 383  *  -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED.  In this
 384  *      case we proceed as for blocks. We remove pred_f.  All
 385  *      predecessors of pred_f now are predecessors of f.
 386  *  -2b: The old predecessor of f is NOT in the block removed. It might be a Phi, too.
 387  *      We have to replicate f for each predecessor of the removed block. Or, with
 388  *      other words, the removed predecessor block has exactly one predecessor.
 389  *
 390  * Further there is a special case for self referencing blocks:
 391  * @verbatim
 392  *
 393  *    then_b     else_b                              then_b  else_b
 394  *       \      /                                      \      /
 395  *        \    /                                        |    /
 396  *        pred_b                                        |   /
 397  *         |   ____                                     |  /  ____
 398  *         |  |    |                                    |  | |    |
 399  *         |  |    |       === optimized to ===>        \  | |    |
 400  *        loop_b   |                                     loop_b   |
 401  *         |  |    |                                      |  |    |
 402  *         |  |____|                                      |  |____|
 403  *         |                                              |
 404  * @endverbatim
 405  *
 406  * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
 407  * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
 408  * backedge.
 409  * @@@ It is negotiable whether we should do this ... there might end up a copy
 410  * from the Phi in the loop when removing the Phis.
 411  */
 412 static void optimize_blocks(ir_node *b, void *ctx) {
 413         int i, j, k, n, max_preds, n_preds, p_preds = -1;
 414         ir_node *pred, *phi;
 415         ir_node **in;
 416         merge_env *env = ctx;
 417
 418         /* Count the number of predecessor if this block is merged with pred blocks
 419            that are empty. */
 420         max_preds = 0;
 421         for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
 422                 max_preds += test_whether_dispensable(b, i);
 423         }
 424         in = xmalloc(max_preds * sizeof(*in));
 425
 426         /*- Fix the Phi nodes of the current block -*/
 427         for (phi = get_irn_link(b); phi; ) {
 428                 assert(get_irn_op(phi) == op_Phi);
 429
 430                 /* Find the new predecessors for the Phi */
 431                 p_preds = 0;
 432                 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
 433                         pred = get_Block_cfgpred_block(b, i);
 434
 435                         if (is_Block_dead(pred)) {
 436                                 /* case Phi 1: Do nothing */
 437                         }
 438                         else if (is_Block_removable(pred) && Block_not_block_visited(pred)) {
 439                                 /* case Phi 2: It's an empty block and not yet visited. */
 440                                 ir_node *phi_pred = get_Phi_pred(phi, i);
 441
 442                                 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
 443                                         /* because of breaking loops, not all predecessors are Bad-clean,
 444                                          * so we must check this here again */
 445                                         if (! is_Bad(get_Block_cfgpred(pred, j))) {
 446                                                 if (get_nodes_block(phi_pred) == pred) {
 447                                                         /* case Phi 2a: */
 448                                                         assert(get_irn_op(phi_pred) == op_Phi);  /* Block is empty!! */
 449
 450                                                         in[p_preds++] = get_Phi_pred(phi_pred, j);
 451                                                 } else {
 452                                                         /* case Phi 2b: */
 453                                                         in[p_preds++] = phi_pred;
 454                                                 }
 455                                         }
 456                                 }
 457                         } else {
 458                                 /* case Phi 3: */
 459                                 in[p_preds++] = get_Phi_pred(phi, i);
 460                         }
 461                 }
 462                 assert(p_preds <= max_preds);
 463
 464                 /* Fix the node */
 465                 if (p_preds == 1)
 466                         /* By removal of Bad ins the Phi might be degenerated. */
 467                         exchange(phi, in[0]);
 468                 else
 469                         set_irn_in(phi, p_preds, in);
 470                 env->changed = 1;
 471
 472                 phi = get_irn_link(phi);
 473         }
 474
 475         /*- This happens only if merge between loop backedge and single loop entry.
 476             Moreover, it is only needed if predb is the direct dominator of b, else there can be no uses
 477             of the Phi's in predb ... -*/
 478         for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
 479                 ir_node *predb = get_nodes_block(get_Block_cfgpred(b, k));
 480
 481                 if (is_Block_removable(predb) && Block_not_block_visited(predb)) {
 482                         ir_node *next_phi;
 483
 484                         /* we found a predecessor block at position k that will be removed */
 485                         for (phi = get_irn_link(predb); phi; phi = next_phi) {
 486                                 int q_preds = 0;
 487                                 next_phi = get_irn_link(phi);
 488
 489                                 assert(is_Phi(phi));
 490
 491                                 if (get_Block_idom(b) != predb) {
 492                                         /* predb is not the dominator. There can't be uses of pred's Phi nodes, kill them .*/
 493                                         exchange(phi, new_Bad());
 494                                 } else {
 495                                         /* predb is the direct dominator of b. There might be uses of the Phi nodes from
 496                                            predb in further block, so move this phi from the predecessor into the block b */
 497                                         set_nodes_block(phi, b);
 498                                         set_irn_link(phi, get_irn_link(b));
 499                                         set_irn_link(b, phi);
 500                                         env->phis_moved = 1;
 501
 502                                         /* first, copy all 0..k-1 predecessors */
 503                                         for (i = 0; i < k; i++) {
 504                                                 pred = get_Block_cfgpred_block(b, i);
 505
 506                                                 if (is_Block_dead(pred)) {
 507                                                         /* Do nothing */
 508                                                 } else if (is_Block_removable(pred) && Block_not_block_visited(pred)) {
 509                                                         /* It's an empty block and not yet visited. */
 510                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 511                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 512                                                                         in[q_preds++] = phi;
 513                                                         }
 514                                                 } else {
 515                                                         in[q_preds++] = phi;
 516                                                 }
 517                                         }
 518
 519                                         /* now we are at k, copy the phi predecessors */
 520                                         pred = get_nodes_block(get_Block_cfgpred(b, k));
 521                                         for (i = 0; i < get_Phi_n_preds(phi); i++) {
 522                                                 if (! is_Bad(get_Block_cfgpred(pred, i)))
 523                                                         in[q_preds++] = get_Phi_pred(phi, i);
 524                                         }
 525
 526                                         /* and now all the rest */
 527                                         for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
 528                                                 pred = get_Block_cfgpred_block(b, i);
 529
 530                                                 if (is_Block_dead(pred)) {
 531                                                         /* Do nothing */
 532                                                 } else if (is_Block_removable(pred) && Block_not_block_visited(pred)) {
 533                                                         /* It's an empty block and not yet visited. */
 534                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 535                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 536                                                                         in[q_preds++] = phi;
 537                                                         }
 538                                                 } else {
 539                                                         in[q_preds++] = phi;
 540                                                 }
 541                                         }
 542
 543                                         /* Fix the node */
 544                                         if (q_preds == 1)
 545                                                 exchange(phi, in[0]);
 546                                         else
 547                                                 set_irn_in(phi, q_preds, in);
 548                                         env->changed = 1;
 549
 550                                         assert(q_preds <= max_preds);
 551                                         // assert(p_preds == q_preds && "Wrong Phi Fix");
 552                                 }
 553                         }
 554                 }
 555         }
 556
 557         /*- Fix the block -*/
 558         n_preds = 0;
 559         for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 560                 pred = get_Block_cfgpred_block(b, i);
 561
 562                 if (is_Block_dead(pred)) {
 563                         /* case 1: Do nothing */
 564                 } else if (is_Block_removable(pred) && Block_not_block_visited(pred)) {
 565                         /* case 2: It's an empty block and not yet visited. */
 566                         assert(get_Block_n_cfgpreds(b) > 1);
 567                         /* Else it should be optimized by equivalent_node. */
 568                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 569                                 ir_node *pred_X = get_Block_cfgpred(pred, j);
 570
 571                                 /* because of breaking loops, not all predecessors are Bad-clean,
 572                                  * so we must check this here again */
 573                                 if (! is_Bad(pred_X))
 574                                         in[n_preds++] = pred_X;
 575                         }
 576                         /* Remove block as it might be kept alive. */
 577                         exchange(pred, b/*new_Bad()*/);
 578                 } else {
 579                         /* case 3: */
 580                         in[n_preds++] = get_Block_cfgpred(b, i);
 581                 }
 582         }
 583         assert(n_preds <= max_preds);
 584
 585         set_irn_in(b, n_preds, in);
 586         env->changed = 1;
 587
 588         assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds && "Wrong Phi Fix"));
 589         xfree(in);
 590 }
 591
 592 /**
 593  * Block walker: optimize all blocks using the default optimizations.
 594  * This removes Blocks that with only a Jmp predecessor.
 595  */
 596 static void remove_simple_blocks(ir_node *block, void *ctx) {
 597         ir_node *new_blk = equivalent_node(block);
 598         merge_env *env = ctx;
 599
 600         if (new_blk != block) {
 601                 exchange(block, new_blk);
 602                 env->changed = 1;
 603         }
 604 }
 605
 606 /**
 607  * Handle pre-optimized table switch Cond's.
 608  * During iropt, all Projs from a switch-Cond are already removed except
 609  * the defProj and maybe the taken one.
 610  * The defProj cannot be removed WITHOUT looking backwards, so we do this here.
 611  *
 612  * @param cond the switch-Cond
 613  *
 614  * @return non-zero if a switch-Cond was optimized
 615  *
 616  * Expects all Proj's linked to the cond node
 617  */
 618 static int handle_switch_cond(ir_node *cond) {
 619         ir_node *sel = get_Cond_selector(cond);
 620
 621         ir_node *proj1 = get_irn_link(cond);
 622         ir_node *proj2 = get_irn_link(proj1);
 623         ir_node *jmp, *blk;
 624
 625         blk = get_nodes_block(cond);
 626
 627         if (proj2 == NULL) {
 628                 /* this Cond has only one Proj: must be the defProj */
 629                 assert(get_Cond_defaultProj(cond) == get_Proj_proj(proj1));
 630                 /* convert it into a Jmp */
 631                 jmp = new_r_Jmp(current_ir_graph, blk);
 632                 exchange(proj1, jmp);
 633                 return 1;
 634         } else if (get_irn_link(proj2) == NULL) {
 635                 /* We have two Proj's here. Check if the Cond has
 636                    a constant argument */
 637                 tarval *tv = value_of(sel);
 638
 639                 if (tv != tarval_bad) {
 640                         /* we have a constant switch */
 641                         long num     = get_tarval_long(tv);
 642                         long def_num = get_Cond_defaultProj(cond);
 643
 644                         if (def_num == get_Proj_proj(proj1)) {
 645                                 /* first one is the defProj */
 646                                 if (num == get_Proj_proj(proj2)) {
 647                                         jmp = new_r_Jmp(current_ir_graph, blk);
 648                                         exchange(proj2, jmp);
 649                                         exchange(proj1, new_Bad());
 650                                         return 1;
 651                                 }
 652                         } else if (def_num == get_Proj_proj(proj2)) {
 653                                 /* second one is the defProj */
 654                                 if (num == get_Proj_proj(proj1)) {
 655                                         jmp = new_r_Jmp(current_ir_graph, blk);
 656                                         exchange(proj1, jmp);
 657                                         exchange(proj2, new_Bad());
 658                                         return 1;
 659                                 }
 660                         } else {
 661                                 /* neither: strange, Cond was not optimized so far */
 662                                 if (num == get_Proj_proj(proj1)) {
 663                                         jmp = new_r_Jmp(current_ir_graph, blk);
 664                                         exchange(proj1, jmp);
 665                                         exchange(proj2, new_Bad());
 666                                         return 1;
 667                                 } else if (num == get_Proj_proj(proj2)) {
 668                                         jmp = new_r_Jmp(current_ir_graph, blk);
 669                                         exchange(proj2, jmp);
 670                                         exchange(proj1, new_Bad());
 671                                         return 1;
 672                                 }
 673                         }
 674                 }
 675         }
 676         return 0;
 677 }
 678
 679 /* Optimizations of the control flow that also require changes of Phi nodes.
 680  *
 681  * This optimization performs two passes over the graph.
 682  *
 683  * The first pass collects all Phi nodes in a link list in the block
 684  * nodes.  Further it performs simple control flow optimizations.
 685  * Finally it marks all blocks that do not contain useful
 686  * computations, i.e., these blocks might be removed.
 687  *
 688  * The second pass performs the optimizations intended by this algorithm.
 689  * It walks only over block nodes and adapts these and the Phi nodes in these blocks,
 690  * which it finds in a linked list computed by the first pass.
 691  *
 692  * We use the mark flag to mark removable blocks in the first
 693  * phase.
 694  */
 695 void optimize_cf(ir_graph *irg) {
 696         int i, j, n;
 697         ir_node **in = NULL;
 698         ir_node *cond, *end = get_irg_end(irg);
 699         ir_graph *rem = current_ir_graph;
 700         plist_element_t *el;
 701         merge_env env;
 702
 703         assert(get_irg_phase_state(irg) != phase_building);
 704
 705         /* if the graph is not pinned, we cannot determine empty blocks */
 706         assert(get_irg_pinned(irg) != op_pin_state_floats &&
 707                "Control flow optimization need a pinned graph");
 708
 709         current_ir_graph = irg;
 710
 711         /* FIXME: control flow opt destroys block edges. So edges are deactivated here. Fix the edges! */
 712         edges_deactivate(irg);
 713
 714         /* we use the mark flag to mark removable blocks */
 715         set_using_block_mark(irg);
 716 restart:
 717         env.changed    = 0;
 718         env.phis_moved = 0;
 719
 720         /* ALWAYS kill unreachable control flow. Backend cannot handle it anyway.
 721            Use dominator info to kill blocks. Also optimize useless Conds. */
 722         assure_doms(irg);
 723         irg_block_walk_graph(irg, NULL, remove_unreachable_blocks_and_conds, &env.changed);
 724
 725         /* fix the keep-alives */
 726         for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
 727                 ir_node *ka = get_End_keepalive(end, i);
 728
 729                 if (is_Block(ka)) {
 730                         /* do NOT keep dead blocks */
 731                         if (is_Block_dead(ka) || get_Block_dom_depth(ka) < 0) {
 732                                 set_End_keepalive(end, i, new_Bad());
 733                                 env.changed = 1;
 734                         }
 735                 } else if (is_Block_dead(get_nodes_block(ka)) ||
 736                            get_Block_dom_depth(get_nodes_block(ka)) < 0) {
 737                         /* do NOT keep nodes in dead blocks */
 738                         set_End_keepalive(end, i, new_Bad());
 739                         env.changed = 1;
 740                 }
 741         }
 742
 743         set_using_irn_link(irg);
 744
 745         env.list = plist_new();
 746         irg_walk(end, merge_blocks, collect_nodes, &env);
 747
 748         clear_using_irn_link(irg);
 749
 750         if (env.changed) {
 751                 /* Handle graph state if was changed. */
 752                 set_irg_outs_inconsistent(irg);
 753                 set_irg_doms_inconsistent(irg);
 754                 set_irg_extblk_inconsistent(irg);
 755                 set_irg_loopinfo_inconsistent(irg);
 756                 env.changed = 0;
 757         }
 758
 759         /* handle all collected switch-Conds */
 760         foreach_plist(env.list, el) {
 761                 cond = plist_element_get_value(el);
 762                 env.changed |= handle_switch_cond(cond);
 763         }
 764         plist_free(env.list);
 765
 766         if (env.changed) {
 767                 /* The Cond optimization might generate unreachable code, so restart if
 768                    it happens. */
 769                 goto restart;
 770         }
 771
 772         /* Optimize the standard code. */
 773         env.changed = 0;
 774         assure_doms(irg);
 775         irg_block_walk(get_irg_end_block(irg), optimize_blocks, remove_simple_blocks, &env);
 776
 777         /* Walk all keep alives, optimize them if block, add to new in-array
 778            for end if useful. */
 779         n  = get_End_n_keepalives(end);
 780         if (n > 0)
 781                 NEW_ARR_A(ir_node *, in, n);
 782
 783         /* in rare cases a node may be kept alive more than once, use the visited flag to detect this */
 784         inc_irg_visited(irg);
 785         set_using_irn_visited(irg);
 786
 787         /* fix the keep alive */
 788         for (i = j = 0; i < n; i++) {
 789                 ir_node *ka = get_End_keepalive(end, i);
 790
 791                 if (irn_not_visited(ka)) {
 792                         ir_op *op = get_irn_op(ka);
 793
 794                         if ((op == op_Block) && Block_not_block_visited(ka)) {
 795                                 /* irg_block_walk() will increase the block visited flag, but we must visit only
 796                                    these blocks that are not visited yet, so decrease it first. */
 797                                 set_irg_block_visited(irg, get_irg_block_visited(irg) - 1);
 798                                 irg_block_walk(ka, optimize_blocks, remove_simple_blocks, &env.changed);
 799                                 mark_irn_visited(ka);
 800                                 in[j++] = ka;
 801                         } else if (op == op_Phi) {
 802                                 mark_irn_visited(ka);
 803                                 /* don't keep alive dead blocks */
 804                                 if (! is_Block_dead(get_nodes_block(ka)))
 805                                         in[j++] = ka;
 806                         } else if (is_op_keep(op)) {
 807                                 mark_irn_visited(ka);
 808                                 if (! is_Block_dead(get_nodes_block(ka)))
 809                                         in[j++] = ka;
 810                         }
 811                 }
 812         }
 813         if (j != n) {
 814                 set_End_keepalives(end, j, in);
 815                 env.changed = 1;
 816         }
 817
 818         clear_using_block_mark(irg);
 819         clear_using_irn_visited(irg);
 820
 821         if (env.phis_moved) {
 822                 /* Bad: when we moved Phi's, we might produce dead Phi nodes
 823                    that are kept-alive.
 824                    Some other phases cannot copy with this, so will them.
 825                  */
 826                 n = get_End_n_keepalives(end);
 827                 if (n > 0) {
 828                         if (env.changed) {
 829                                 /* Handle graph state if was changed. */
 830                                 set_irg_outs_inconsistent(irg);
 831                         }
 832                         assure_irg_outs(irg);
 833
 834                         for (i = j = 0; i < n; ++i) {
 835                                 ir_node *ka = get_End_keepalive(end, i);
 836
 837                                 if (is_Phi(ka)) {
 838                                         int k;
 839
 840                                         for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
 841                                                 ir_node *user = get_irn_out(ka, k);
 842
 843                                                 if (user != ka && user != end) {
 844                                                         /* Is it a real user or just a self loop ? */
 845                                                         break;
 846                                                 }
 847                                         }
 848                                         if (k >= 0)
 849                                                 in[j++] = ka;
 850                                 } else
 851                                         in[j++] = ka;
 852                         }
 853                         if (j != n) {
 854                                 set_End_keepalives(end, j, in);
 855                                 env.changed = 1;
 856                         }
 857                 }
 858         }
 859
 860         if (env.changed) {
 861                 /* Handle graph state if was changed. */
 862                 set_irg_outs_inconsistent(irg);
 863                 set_irg_doms_inconsistent(irg);
 864                 set_irg_extblk_inconsistent(irg);
 865                 set_irg_loopinfo_inconsistent(irg);
 866         }
 867
 868
 869         /* the verifier doesn't work yet with floating nodes */
 870         if (get_irg_pinned(irg) == op_pin_state_pinned) {
 871                 /* after optimize_cf(), only Bad data flow may remain. */
 872                 if (irg_vrfy_bads(irg, BAD_DF | BAD_BLOCK | TUPLE)) {
 873                         dump_ir_block_graph(irg, "-vrfy-cf");
 874                         dump_ir_graph(irg, "-vrfy-cf");
 875                         fprintf(stderr, "VRFY_BAD in optimize_cf()\n");
 876                 }
 877         }
 878
 879         current_ir_graph = rem;
 880 }