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;
 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; ) {
 426                 assert(get_irn_op(phi) == op_Phi);
 427
 428                 /* Find the new predecessors for the Phi */
 429                 p_preds = 0;
 430                 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
 431                         pred = get_Block_cfgpred_block(b, i);
 432
 433                         if (is_Block_dead(pred)) {
 434                                 /* case Phi 1: Do nothing */
 435                         } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 436                                 /* case Phi 2: It's an empty block and not yet visited. */
 437                                 ir_node *phi_pred = get_Phi_pred(phi, i);
 438
 439                                 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
 440                                         /* because of breaking loops, not all predecessors are Bad-clean,
 441                                          * so we must check this here again */
 442                                         if (! is_Bad(get_Block_cfgpred(pred, j))) {
 443                                                 if (get_nodes_block(phi_pred) == pred) {
 444                                                         /* case Phi 2a: */
 445                                                         assert(get_irn_op(phi_pred) == op_Phi);  /* Block is empty!! */
 446
 447                                                         in[p_preds++] = get_Phi_pred(phi_pred, j);
 448                                                 } else {
 449                                                         /* case Phi 2b: */
 450                                                         in[p_preds++] = phi_pred;
 451                                                 }
 452                                         }
 453                                 }
 454                         } else {
 455                                 /* case Phi 3: */
 456                                 in[p_preds++] = get_Phi_pred(phi, i);
 457                         }
 458                 }
 459                 assert(p_preds <= max_preds);
 460
 461                 /* Fix the node */
 462                 if (p_preds == 1)
 463                         /* By removal of Bad ins the Phi might be degenerated. */
 464                         exchange(phi, in[0]);
 465                 else
 466                         set_irn_in(phi, p_preds, in);
 467                 env->changed = 1;
 468
 469                 phi = get_irn_link(phi);
 470         }
 471
 472         /*- This happens only if merge between loop backedge and single loop entry.
 473             Moreover, it is only needed if predb is the direct dominator of b, else there can be no uses
 474             of the Phi's in predb ... -*/
 475         for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
 476                 ir_node *predb = get_nodes_block(get_Block_cfgpred(b, k));
 477
 478                 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
 479                         ir_node *next_phi;
 480
 481                         /* we found a predecessor block at position k that will be removed */
 482                         for (phi = get_irn_link(predb); phi; phi = next_phi) {
 483                                 int q_preds = 0;
 484                                 next_phi = get_irn_link(phi);
 485
 486                                 assert(is_Phi(phi));
 487
 488                                 if (get_Block_idom(b) != predb) {
 489                                         /* predb is not the dominator. There can't be uses of pred's Phi nodes, kill them .*/
 490                                         exchange(phi, new_Bad());
 491                                 } else {
 492                                         /* predb is the direct dominator of b. There might be uses of the Phi nodes from
 493                                            predb in further block, so move this phi from the predecessor into the block b */
 494                                         set_nodes_block(phi, b);
 495                                         set_irn_link(phi, get_irn_link(b));
 496                                         set_irn_link(b, phi);
 497                                         env->phis_moved = 1;
 498
 499                                         /* first, copy all 0..k-1 predecessors */
 500                                         for (i = 0; i < k; i++) {
 501                                                 pred = get_Block_cfgpred_block(b, i);
 502
 503                                                 if (is_Block_dead(pred)) {
 504                                                         /* Do nothing */
 505                                                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 506                                                         /* It's an empty block and not yet visited. */
 507                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 508                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 509                                                                         in[q_preds++] = phi;
 510                                                         }
 511                                                 } else {
 512                                                         in[q_preds++] = phi;
 513                                                 }
 514                                         }
 515
 516                                         /* now we are at k, copy the phi predecessors */
 517                                         pred = get_nodes_block(get_Block_cfgpred(b, k));
 518                                         for (i = 0; i < get_Phi_n_preds(phi); i++) {
 519                                                 if (! is_Bad(get_Block_cfgpred(pred, i)))
 520                                                         in[q_preds++] = get_Phi_pred(phi, i);
 521                                         }
 522
 523                                         /* and now all the rest */
 524                                         for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
 525                                                 pred = get_Block_cfgpred_block(b, i);
 526
 527                                                 if (is_Block_dead(pred)) {
 528                                                         /* Do nothing */
 529                                                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 530                                                         /* It's an empty block and not yet visited. */
 531                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 532                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 533                                                                         in[q_preds++] = phi;
 534                                                         }
 535                                                 } else {
 536                                                         in[q_preds++] = phi;
 537                                                 }
 538                                         }
 539
 540                                         /* Fix the node */
 541                                         if (q_preds == 1)
 542                                                 exchange(phi, in[0]);
 543                                         else
 544                                                 set_irn_in(phi, q_preds, in);
 545                                         env->changed = 1;
 546
 547                                         assert(q_preds <= max_preds);
 548                                         // assert(p_preds == q_preds && "Wrong Phi Fix");
 549                                 }
 550                         }
 551                 }
 552         }
 553
 554         /*- Fix the block -*/
 555         n_preds = 0;
 556         for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 557                 pred = get_Block_cfgpred_block(b, i);
 558
 559                 if (is_Block_dead(pred)) {
 560                         /* case 1: Do nothing */
 561                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 562                         /* case 2: It's an empty block and not yet visited. */
 563                         assert(get_Block_n_cfgpreds(b) > 1);
 564                         /* Else it should be optimized by equivalent_node. */
 565                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 566                                 ir_node *pred_X = get_Block_cfgpred(pred, j);
 567
 568                                 /* because of breaking loops, not all predecessors are Bad-clean,
 569                                  * so we must check this here again */
 570                                 if (! is_Bad(pred_X))
 571                                         in[n_preds++] = pred_X;
 572                         }
 573                         /* Remove block as it might be kept alive. */
 574                         exchange(pred, b/*new_Bad()*/);
 575                 } else {
 576                         /* case 3: */
 577                         in[n_preds++] = get_Block_cfgpred(b, i);
 578                 }
 579         }
 580         assert(n_preds <= max_preds);
 581
 582         set_irn_in(b, n_preds, in);
 583         env->changed = 1;
 584
 585         assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds && "Wrong Phi Fix"));
 586         xfree(in);
 587 }
 588
 589 /**
 590  * Block walker: optimize all blocks using the default optimizations.
 591  * This removes Blocks that with only a Jmp predecessor.
 592  */
 593 static void remove_simple_blocks(ir_node *block, void *ctx) {
 594         ir_node *new_blk = equivalent_node(block);
 595         merge_env *env = ctx;
 596
 597         if (new_blk != block) {
 598                 exchange(block, new_blk);
 599                 env->changed = 1;
 600         }
 601 }
 602
 603 /**
 604  * Handle pre-optimized table switch Cond's.
 605  * During iropt, all Projs from a switch-Cond are already removed except
 606  * the defProj and maybe the taken one.
 607  * The defProj cannot be removed WITHOUT looking backwards, so we do this here.
 608  *
 609  * @param cond the switch-Cond
 610  *
 611  * @return non-zero if a switch-Cond was optimized
 612  *
 613  * Expects all Proj's linked to the cond node
 614  */
 615 static int handle_switch_cond(ir_node *cond) {
 616         ir_node *sel = get_Cond_selector(cond);
 617
 618         ir_node *proj1 = get_irn_link(cond);
 619         ir_node *proj2 = get_irn_link(proj1);
 620         ir_node *jmp, *blk;
 621
 622         blk = get_nodes_block(cond);
 623
 624         if (proj2 == NULL) {
 625                 /* this Cond has only one Proj: must be the defProj */
 626                 assert(get_Cond_defaultProj(cond) == get_Proj_proj(proj1));
 627                 /* convert it into a Jmp */
 628                 jmp = new_r_Jmp(current_ir_graph, blk);
 629                 exchange(proj1, jmp);
 630                 return 1;
 631         } else if (get_irn_link(proj2) == NULL) {
 632                 /* We have two Proj's here. Check if the Cond has
 633                    a constant argument */
 634                 tarval *tv = value_of(sel);
 635
 636                 if (tv != tarval_bad) {
 637                         /* we have a constant switch */
 638                         long num     = get_tarval_long(tv);
 639                         long def_num = get_Cond_defaultProj(cond);
 640
 641                         if (def_num == get_Proj_proj(proj1)) {
 642                                 /* first one is the defProj */
 643                                 if (num == get_Proj_proj(proj2)) {
 644                                         jmp = new_r_Jmp(current_ir_graph, blk);
 645                                         exchange(proj2, jmp);
 646                                         exchange(proj1, new_Bad());
 647                                         return 1;
 648                                 }
 649                         } else if (def_num == get_Proj_proj(proj2)) {
 650                                 /* second one is the defProj */
 651                                 if (num == get_Proj_proj(proj1)) {
 652                                         jmp = new_r_Jmp(current_ir_graph, blk);
 653                                         exchange(proj1, jmp);
 654                                         exchange(proj2, new_Bad());
 655                                         return 1;
 656                                 }
 657                         } else {
 658                                 /* neither: strange, Cond was not optimized so far */
 659                                 if (num == get_Proj_proj(proj1)) {
 660                                         jmp = new_r_Jmp(current_ir_graph, blk);
 661                                         exchange(proj1, jmp);
 662                                         exchange(proj2, new_Bad());
 663                                         return 1;
 664                                 } else if (num == get_Proj_proj(proj2)) {
 665                                         jmp = new_r_Jmp(current_ir_graph, blk);
 666                                         exchange(proj2, jmp);
 667                                         exchange(proj1, new_Bad());
 668                                         return 1;
 669                                 }
 670                         }
 671                 }
 672         }
 673         return 0;
 674 }
 675
 676 /* Optimizations of the control flow that also require changes of Phi nodes.
 677  *
 678  * This optimization performs two passes over the graph.
 679  *
 680  * The first pass collects all Phi nodes in a link list in the block
 681  * nodes.  Further it performs simple control flow optimizations.
 682  * Finally it marks all blocks that do not contain useful
 683  * computations, i.e., these blocks might be removed.
 684  *
 685  * The second pass performs the optimizations intended by this algorithm.
 686  * It walks only over block nodes and adapts these and the Phi nodes in these blocks,
 687  * which it finds in a linked list computed by the first pass.
 688  *
 689  * We use the mark flag to mark removable blocks in the first
 690  * phase.
 691  */
 692 void optimize_cf(ir_graph *irg) {
 693         int i, j, n;
 694         ir_node **in = NULL;
 695         ir_node *cond, *end = get_irg_end(irg);
 696         ir_graph *rem = current_ir_graph;
 697         plist_element_t *el;
 698         merge_env env;
 699
 700         assert(get_irg_phase_state(irg) != phase_building);
 701
 702         /* if the graph is not pinned, we cannot determine empty blocks */
 703         assert(get_irg_pinned(irg) != op_pin_state_floats &&
 704                "Control flow optimization need a pinned graph");
 705
 706         current_ir_graph = irg;
 707
 708         /* FIXME: control flow opt destroys block edges. So edges are deactivated here. Fix the edges! */
 709         edges_deactivate(irg);
 710
 711         /* we use the mark flag to mark removable blocks */
 712         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
 713 restart:
 714         env.changed    = 0;
 715         env.phis_moved = 0;
 716
 717         /* ALWAYS kill unreachable control flow. Backend cannot handle it anyway.
 718            Use dominator info to kill blocks. Also optimize useless Conds. */
 719         assure_doms(irg);
 720         irg_block_walk_graph(irg, NULL, remove_unreachable_blocks_and_conds, &env.changed);
 721
 722         /* fix the keep-alives */
 723         for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
 724                 ir_node *ka = get_End_keepalive(end, i);
 725
 726                 if (is_Block(ka)) {
 727                         /* do NOT keep dead blocks */
 728                         if (is_Block_dead(ka) || get_Block_dom_depth(ka) < 0) {
 729                                 set_End_keepalive(end, i, new_Bad());
 730                                 env.changed = 1;
 731                         }
 732                 } else if (is_Block_dead(get_nodes_block(ka)) ||
 733                            get_Block_dom_depth(get_nodes_block(ka)) < 0) {
 734                         /* do NOT keep nodes in dead blocks */
 735                         set_End_keepalive(end, i, new_Bad());
 736                         env.changed = 1;
 737                 }
 738         }
 739
 740         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 741
 742         env.list = plist_new();
 743         irg_walk(end, merge_blocks, collect_nodes, &env);
 744
 745         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 746
 747         if (env.changed) {
 748                 /* Handle graph state if was changed. */
 749                 set_irg_outs_inconsistent(irg);
 750                 set_irg_doms_inconsistent(irg);
 751                 set_irg_extblk_inconsistent(irg);
 752                 set_irg_loopinfo_inconsistent(irg);
 753                 env.changed = 0;
 754         }
 755
 756         /* handle all collected switch-Conds */
 757         foreach_plist(env.list, el) {
 758                 cond = plist_element_get_value(el);
 759                 env.changed |= handle_switch_cond(cond);
 760         }
 761         plist_free(env.list);
 762
 763         if (env.changed) {
 764                 /* The Cond optimization might generate unreachable code, so restart if
 765                    it happens. */
 766                 goto restart;
 767         }
 768
 769         /* Optimize the standard code. */
 770         env.changed = 0;
 771         assure_doms(irg);
 772         irg_block_walk(get_irg_end_block(irg), optimize_blocks, remove_simple_blocks, &env);
 773
 774         /* Walk all keep alives, optimize them if block, add to new in-array
 775            for end if useful. */
 776         n  = get_End_n_keepalives(end);
 777         if (n > 0)
 778                 NEW_ARR_A(ir_node *, in, n);
 779
 780         /* in rare cases a node may be kept alive more than once, use the visited flag to detect this */
 781         inc_irg_visited(irg);
 782         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 783
 784         /* fix the keep alive */
 785         for (i = j = 0; i < n; i++) {
 786                 ir_node *ka = get_End_keepalive(end, i);
 787
 788                 if (!irn_visited(ka)) {
 789                         if (is_Block(ka)) {
 790                                 if (!Block_block_visited(ka)) {
 791                                         /* irg_block_walk() will increase the block visited flag, but we must visit only
 792                                            these blocks that are not visited yet, so decrease it first. */
 793                                         set_irg_block_visited(irg, get_irg_block_visited(irg) - 1);
 794                                         irg_block_walk(ka, optimize_blocks, remove_simple_blocks, &env.changed);
 795                                         mark_irn_visited(ka);
 796                                         in[j++] = ka;
 797                                 }
 798                         } else {
 799                                 mark_irn_visited(ka);
 800                                 /* don't keep alive dead blocks */
 801                                 if (!is_Bad(ka) && !is_Block_dead(get_nodes_block(ka)))
 802                                         in[j++] = ka;
 803                         }
 804                 }
 805         }
 806         if (j != n) {
 807                 set_End_keepalives(end, j, in);
 808                 env.changed = 1;
 809         }
 810
 811         ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_VISITED);
 812
 813         if (env.phis_moved) {
 814                 /* Bad: when we moved Phi's, we might produce dead Phi nodes
 815                    that are kept-alive.
 816                    Some other phases cannot copy with this, so will them.
 817                  */
 818                 n = get_End_n_keepalives(end);
 819                 if (n > 0) {
 820                         if (env.changed) {
 821                                 /* Handle graph state if was changed. */
 822                                 set_irg_outs_inconsistent(irg);
 823                         }
 824                         assure_irg_outs(irg);
 825
 826                         for (i = j = 0; i < n; ++i) {
 827                                 ir_node *ka = get_End_keepalive(end, i);
 828
 829                                 if (is_Phi(ka)) {
 830                                         int k;
 831
 832                                         for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
 833                                                 ir_node *user = get_irn_out(ka, k);
 834
 835                                                 if (user != ka && user != end) {
 836                                                         /* Is it a real user or just a self loop ? */
 837                                                         break;
 838                                                 }
 839                                         }
 840                                         if (k >= 0)
 841                                                 in[j++] = ka;
 842                                 } else
 843                                         in[j++] = ka;
 844                         }
 845                         if (j != n) {
 846                                 set_End_keepalives(end, j, in);
 847                                 env.changed = 1;
 848                         }
 849                 }
 850         }
 851
 852         if (env.changed) {
 853                 /* Handle graph state if was changed. */
 854                 set_irg_outs_inconsistent(irg);
 855                 set_irg_doms_inconsistent(irg);
 856                 set_irg_extblk_inconsistent(irg);
 857                 set_irg_loopinfo_inconsistent(irg);
 858         }
 859
 860
 861         /* the verifier doesn't work yet with floating nodes */
 862         if (get_irg_pinned(irg) == op_pin_state_pinned) {
 863                 /* after optimize_cf(), only Bad data flow may remain. */
 864                 if (irg_vrfy_bads(irg, BAD_DF | BAD_BLOCK | TUPLE)) {
 865                         dump_ir_block_graph(irg, "-vrfy-cf");
 866                         dump_ir_graph(irg, "-vrfy-cf");
 867                         fprintf(stderr, "VRFY_BAD in optimize_cf()\n");
 868                 }
 869         }
 870
 871         current_ir_graph = rem;
 872 }