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