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 that have NO label */
 228         if (has_Block_label(block))
 229                 set_Block_removable(block);
 230         else
 231                 set_Block_non_removable(block);
 232 }
 233
 234 /**
 235  * Collects all Phi nodes in link list of Block.
 236  * Marks all blocks "non_removable" if they contain a node other
 237  * than Jmp (and Proj).
 238  * Links all Proj nodes to their predecessors.
 239  * Collects all switch-Conds in a list.
 240  */
 241 static void collect_nodes(ir_node *n, void *ctx) {
 242         ir_opcode code = get_irn_opcode(n);
 243         merge_env *env = ctx;
 244
 245         if (code == iro_Block) {
 246                 /* mark the block as non-removable if it is labeled */
 247                 if (has_Block_label(n))
 248                         set_Block_non_removable(n);
 249         } else {
 250                 ir_node *b = get_nodes_block(n);
 251
 252                 if (code == iro_Phi && get_irn_arity(n) > 0) {
 253                         /* Collect Phi nodes to compact ins along with block's ins. */
 254                         set_irn_link(n, get_irn_link(b));
 255                         set_irn_link(b, n);
 256                 } else if (code != iro_Jmp && !is_Bad(b)) {  /* Check for non-empty block. */
 257                         set_Block_non_removable(b);
 258
 259                         if (code == iro_Proj) {               /* link Proj nodes */
 260                                 ir_node *pred = get_Proj_pred(n);
 261
 262                                 set_irn_link(n, get_irn_link(pred));
 263                                 set_irn_link(pred, n);
 264                         } else if (code == iro_Cond) {
 265                                 ir_node *sel = get_Cond_selector(n);
 266                                 if (mode_is_int(get_irn_mode(sel))) {
 267                                         /* found a switch-Cond, collect */
 268                                         plist_insert_back(env->list, n);
 269                                 }
 270                         }
 271                 }
 272         }
 273 }
 274
 275 /** Returns true if pred is predecessor of block. */
 276 static int is_pred_of(ir_node *pred, ir_node *b) {
 277         int i;
 278
 279         for (i = get_Block_n_cfgpreds(b) - 1; i >= 0; --i) {
 280                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 281                 if (b_pred == pred)
 282                         return 1;
 283         }
 284         return 0;
 285 }
 286
 287 /** Test whether we can optimize away pred block pos of b.
 288  *
 289  *  @param  b    A block node.
 290  *  @param  pos  The position of the predecessor block to judge about.
 291  *
 292  *  @returns     The number of predecessors
 293  *
 294  *  The test is rather tricky.
 295  *
 296  *  The situation is something like the following:
 297  *  @verbatim
 298  *                 if-block
 299  *                  /   \
 300  *              then-b  else-b
 301  *                  \   /
 302  *                    b
 303  *  @endverbatim
 304  *
 305  *  b merges the control flow of an if-then-else.  We may not remove
 306  *  the 'then' _and_ the 'else' block of an 'if' if there is a Phi
 307  *  node in b, even if both are empty.  The destruction of this Phi
 308  *  requires that a copy is added before the merge.  We have to
 309  *  keep one of the case blocks to place the copies in.
 310  *
 311  *  To perform the test for pos, we must regard predecessors before pos
 312  *  as already removed.
 313  **/
 314 static int test_whether_dispensable(ir_node *b, int pos) {
 315         int i, j, n_preds = 1;
 316         ir_node *pred = get_Block_cfgpred_block(b, pos);
 317
 318         /* Bad blocks will be optimized away, so we don't need space for them */
 319         if (is_Block_dead(pred))
 320                 return 0;
 321
 322         if (is_Block_removable(pred)) {
 323                 if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
 324                         /* Mark block so that is will not be removed: optimization is turned off. */
 325                         set_Block_non_removable(pred);
 326                         return 1;
 327                 }
 328
 329                 /* Seems to be empty. At least we detected this in collect_nodes. */
 330                 if (get_irn_link(b) == NULL) {
 331                         /* There are no Phi nodes ==> all predecessors are dispensable. */
 332                         n_preds = get_Block_n_cfgpreds(pred);
 333                 } else {
 334                         /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
 335                            Handle all pred blocks with preds < pos as if they were already removed. */
 336                         for (i = 0; i < pos; i++) {
 337                                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 338                                 if (! is_Block_dead(b_pred) && is_Block_removable(b_pred)) {
 339                                         for (j = get_Block_n_cfgpreds(b_pred) - 1; j >= 0; --j) {
 340                                                 ir_node *b_pred_pred = get_Block_cfgpred_block(b_pred, j);
 341                                                 if (is_pred_of(b_pred_pred, pred))
 342                                                         goto non_dispensable;
 343                                         }
 344                                 } else {
 345                                         if (is_pred_of(b_pred, pred))
 346                                                 goto non_dispensable;
 347                                 }
 348                         }
 349                         for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
 350                                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 351                                 if (is_pred_of(b_pred, pred))
 352                                         goto non_dispensable;
 353                         }
 354                         /* if we get here, the block is dispensable */
 355                         n_preds = get_Block_n_cfgpreds(pred);
 356                 }
 357         }
 358
 359         return n_preds;
 360
 361 non_dispensable:
 362         set_Block_non_removable(pred);
 363         return 1;
 364 }
 365
 366 /**
 367  * This method removed Bad cf predecessors from Blocks and Phis, and removes
 368  * empty blocks.  A block is empty if it only contains Phi and Jmp nodes.
 369  *
 370  * We first adapt Phi nodes, then Block nodes, as we need the old ins
 371  * of the Block to adapt the Phi nodes.  We do this by computing new
 372  * in arrays, and then replacing the old ones.  So far we compute new in arrays
 373  * for all nodes, not regarding whether there is a possibility for optimization.
 374  *
 375  * For each predecessor p of a Block b there are three cases:
 376  *  -1. The predecessor p is a Bad node:  just skip it.  The in array of b shrinks by one.
 377  *  -2. The predecessor p is empty.  Remove p.  All predecessors of p are now
 378  *      predecessors of b.
 379  *  -3. The predecessor p is a block containing useful code.  Just keep p as is.
 380  *
 381  * For Phi nodes f we have to check the conditions at the Block of f.
 382  * For cases 1 and 3 we proceed as for Blocks.  For case 2 we can have two
 383  * cases:
 384  *  -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED.  In this
 385  *      case we proceed as for blocks. We remove pred_f.  All
 386  *      predecessors of pred_f now are predecessors of f.
 387  *  -2b: The old predecessor of f is NOT in the block removed. It might be a Phi, too.
 388  *      We have to replicate f for each predecessor of the removed block. Or, with
 389  *      other words, the removed predecessor block has exactly one predecessor.
 390  *
 391  * Further there is a special case for self referencing blocks:
 392  * @verbatim
 393  *
 394  *    then_b     else_b                              then_b  else_b
 395  *       \      /                                      \      /
 396  *        \    /                                        |    /
 397  *        pred_b                                        |   /
 398  *         |   ____                                     |  /  ____
 399  *         |  |    |                                    |  | |    |
 400  *         |  |    |       === optimized to ===>        \  | |    |
 401  *        loop_b   |                                     loop_b   |
 402  *         |  |    |                                      |  |    |
 403  *         |  |____|                                      |  |____|
 404  *         |                                              |
 405  * @endverbatim
 406  *
 407  * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
 408  * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
 409  * backedge.
 410  * @@@ It is negotiable whether we should do this ... there might end up a copy
 411  * from the Phi in the loop when removing the Phis.
 412  */
 413 static void optimize_blocks(ir_node *b, void *ctx) {
 414         int i, j, k, n, max_preds, n_preds, p_preds = -1;
 415         ir_node *pred, *phi, *next;
 416         ir_node **in;
 417         merge_env *env = ctx;
 418
 419         /* Count the number of predecessor if this block is merged with pred blocks
 420            that are empty. */
 421         max_preds = 0;
 422         for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
 423                 max_preds += test_whether_dispensable(b, i);
 424         }
 425         in = XMALLOCN(ir_node*, max_preds);
 426
 427         /*- Fix the Phi nodes of the current block -*/
 428         for (phi = get_irn_link(b); phi != NULL; phi = next) {
 429                 assert(is_Phi(phi));
 430                 next = get_irn_link(phi);
 431
 432                 /* Find the new predecessors for the Phi */
 433                 p_preds = 0;
 434                 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
 435                         pred = get_Block_cfgpred_block(b, i);
 436
 437                         if (is_Block_dead(pred)) {
 438                                 /* case Phi 1: Do nothing */
 439                         } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 440                                 /* case Phi 2: It's an empty block and not yet visited. */
 441                                 ir_node *phi_pred = get_Phi_pred(phi, i);
 442
 443                                 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
 444                                         /* because of breaking loops, not all predecessors are Bad-clean,
 445                                          * so we must check this here again */
 446                                         if (! is_Bad(get_Block_cfgpred(pred, j))) {
 447                                                 if (get_nodes_block(phi_pred) == pred) {
 448                                                         /* case Phi 2a: */
 449                                                         assert(is_Phi(phi_pred));  /* Block is empty!! */
 450
 451                                                         in[p_preds++] = get_Phi_pred(phi_pred, j);
 452                                                 } else {
 453                                                         /* case Phi 2b: */
 454                                                         in[p_preds++] = phi_pred;
 455                                                 }
 456                                         }
 457                                 }
 458                         } else {
 459                                 /* case Phi 3: */
 460                                 in[p_preds++] = get_Phi_pred(phi, i);
 461                         }
 462                 }
 463                 assert(p_preds <= max_preds);
 464
 465                 /* Fix the node */
 466                 if (p_preds == 1)
 467                         /* By removal of Bad ins the Phi might be degenerated. */
 468                         exchange(phi, in[0]);
 469                 else
 470                         set_irn_in(phi, p_preds, in);
 471                 env->changed = 1;
 472         }
 473
 474         /*- This happens only if merge between loop backedge and single loop entry.
 475             Moreover, it is only needed if predb is the direct dominator of b, else there can be no uses
 476             of the Phi's in predb ... -*/
 477         for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
 478                 ir_node *predb = get_nodes_block(get_Block_cfgpred(b, k));
 479
 480                 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
 481                         ir_node *next_phi;
 482
 483                         /* we found a predecessor block at position k that will be removed */
 484                         for (phi = get_irn_link(predb); phi; phi = next_phi) {
 485                                 int q_preds = 0;
 486                                 next_phi = get_irn_link(phi);
 487
 488                                 assert(is_Phi(phi));
 489
 490                                 if (get_Block_idom(b) != predb) {
 491                                         /* predb is not the dominator. There can't be uses of pred's Phi nodes, kill them .*/
 492                                         exchange(phi, new_Bad());
 493                                 } else {
 494                                         /* predb is the direct dominator of b. There might be uses of the Phi nodes from
 495                                            predb in further block, so move this phi from the predecessor into the block b */
 496                                         set_nodes_block(phi, b);
 497                                         set_irn_link(phi, get_irn_link(b));
 498                                         set_irn_link(b, phi);
 499                                         env->phis_moved = 1;
 500
 501                                         /* first, copy all 0..k-1 predecessors */
 502                                         for (i = 0; i < k; i++) {
 503                                                 pred = get_Block_cfgpred_block(b, i);
 504
 505                                                 if (is_Block_dead(pred)) {
 506                                                         /* Do nothing */
 507                                                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 508                                                         /* It's an empty block and not yet visited. */
 509                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 510                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 511                                                                         in[q_preds++] = phi;
 512                                                         }
 513                                                 } else {
 514                                                         in[q_preds++] = phi;
 515                                                 }
 516                                         }
 517
 518                                         /* now we are at k, copy the phi predecessors */
 519                                         pred = get_nodes_block(get_Block_cfgpred(b, k));
 520                                         for (i = 0; i < get_Phi_n_preds(phi); i++) {
 521                                                 if (! is_Bad(get_Block_cfgpred(pred, i)))
 522                                                         in[q_preds++] = get_Phi_pred(phi, i);
 523                                         }
 524
 525                                         /* and now all the rest */
 526                                         for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
 527                                                 pred = get_Block_cfgpred_block(b, i);
 528
 529                                                 if (is_Block_dead(pred)) {
 530                                                         /* Do nothing */
 531                                                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 532                                                         /* It's an empty block and not yet visited. */
 533                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 534                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 535                                                                         in[q_preds++] = phi;
 536                                                         }
 537                                                 } else {
 538                                                         in[q_preds++] = phi;
 539                                                 }
 540                                         }
 541
 542                                         /* Fix the node */
 543                                         if (q_preds == 1)
 544                                                 exchange(phi, in[0]);
 545                                         else
 546                                                 set_irn_in(phi, q_preds, in);
 547                                         env->changed = 1;
 548
 549                                         assert(q_preds <= max_preds);
 550                                         // assert(p_preds == q_preds && "Wrong Phi Fix");
 551                                 }
 552                         }
 553                 }
 554         }
 555
 556         /*- Fix the block -*/
 557         n_preds = 0;
 558         for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 559                 pred = get_Block_cfgpred_block(b, i);
 560
 561                 if (is_Block_dead(pred)) {
 562                         /* case 1: Do nothing */
 563                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 564                         /* case 2: It's an empty block and not yet visited. */
 565                         assert(get_Block_n_cfgpreds(b) > 1);
 566                         /* Else it should be optimized by equivalent_node. */
 567                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 568                                 ir_node *pred_X = get_Block_cfgpred(pred, j);
 569
 570                                 /* because of breaking loops, not all predecessors are Bad-clean,
 571                                  * so we must check this here again */
 572                                 if (! is_Bad(pred_X))
 573                                         in[n_preds++] = pred_X;
 574                         }
 575                         /* Remove block as it might be kept alive. */
 576                         exchange(pred, b/*new_Bad()*/);
 577                 } else {
 578                         /* case 3: */
 579                         in[n_preds++] = get_Block_cfgpred(b, i);
 580                 }
 581         }
 582         assert(n_preds <= max_preds);
 583
 584         set_irn_in(b, n_preds, in);
 585         env->changed = 1;
 586
 587         assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds && "Wrong Phi Fix"));
 588         xfree(in);
 589 }
 590
 591 /**
 592  * Block walker: optimize all blocks using the default optimizations.
 593  * This removes Blocks that with only a Jmp predecessor.
 594  */
 595 static void remove_simple_blocks(ir_node *block, void *ctx) {
 596         ir_node *new_blk = equivalent_node(block);
 597         merge_env *env = ctx;
 598
 599         if (new_blk != block) {
 600                 exchange(block, new_blk);
 601                 env->changed = 1;
 602         }
 603 }
 604
 605 /**
 606  * Handle pre-optimized table switch Cond's.
 607  * During iropt, all Projs from a switch-Cond are already removed except
 608  * the defProj and maybe the taken one.
 609  * The defProj cannot be removed WITHOUT looking backwards, so we do this here.
 610  *
 611  * @param cond the switch-Cond
 612  *
 613  * @return non-zero if a switch-Cond was optimized
 614  *
 615  * Expects all Proj's linked to the cond node
 616  */
 617 static int handle_switch_cond(ir_node *cond) {
 618         ir_node *sel = get_Cond_selector(cond);
 619
 620         ir_node *proj1 = get_irn_link(cond);
 621         ir_node *proj2 = get_irn_link(proj1);
 622         ir_node *jmp, *blk;
 623
 624         blk = get_nodes_block(cond);
 625
 626         if (proj2 == NULL) {
 627                 /* this Cond has only one Proj: must be the defProj */
 628                 assert(get_Cond_defaultProj(cond) == get_Proj_proj(proj1));
 629                 /* convert it into a Jmp */
 630                 jmp = new_r_Jmp(current_ir_graph, blk);
 631                 exchange(proj1, jmp);
 632                 return 1;
 633         } else if (get_irn_link(proj2) == NULL) {
 634                 /* We have two Proj's here. Check if the Cond has
 635                    a constant argument */
 636                 tarval *tv = value_of(sel);
 637
 638                 if (tv != tarval_bad) {
 639                         /* we have a constant switch */
 640                         long num     = get_tarval_long(tv);
 641                         long def_num = get_Cond_defaultProj(cond);
 642
 643                         if (def_num == get_Proj_proj(proj1)) {
 644                                 /* first one is the defProj */
 645                                 if (num == get_Proj_proj(proj2)) {
 646                                         jmp = new_r_Jmp(current_ir_graph, blk);
 647                                         exchange(proj2, jmp);
 648                                         exchange(proj1, new_Bad());
 649                                         return 1;
 650                                 }
 651                         } else if (def_num == get_Proj_proj(proj2)) {
 652                                 /* second one is the defProj */
 653                                 if (num == get_Proj_proj(proj1)) {
 654                                         jmp = new_r_Jmp(current_ir_graph, blk);
 655                                         exchange(proj1, jmp);
 656                                         exchange(proj2, new_Bad());
 657                                         return 1;
 658                                 }
 659                         } else {
 660                                 /* neither: strange, Cond was not optimized so far */
 661                                 if (num == get_Proj_proj(proj1)) {
 662                                         jmp = new_r_Jmp(current_ir_graph, blk);
 663                                         exchange(proj1, jmp);
 664                                         exchange(proj2, new_Bad());
 665                                         return 1;
 666                                 } else if (num == get_Proj_proj(proj2)) {
 667                                         jmp = new_r_Jmp(current_ir_graph, blk);
 668                                         exchange(proj2, jmp);
 669                                         exchange(proj1, new_Bad());
 670                                         return 1;
 671                                 }
 672                         }
 673                 }
 674         }
 675         return 0;
 676 }
 677
 678 /* Optimizations of the control flow that also require changes of Phi nodes.
 679  *
 680  * This optimization performs two passes over the graph.
 681  *
 682  * The first pass collects all Phi nodes in a link list in the block
 683  * nodes.  Further it performs simple control flow optimizations.
 684  * Finally it marks all blocks that do not contain useful
 685  * computations, i.e., these blocks might be removed.
 686  *
 687  * The second pass performs the optimizations intended by this algorithm.
 688  * It walks only over block nodes and adapts these and the Phi nodes in these blocks,
 689  * which it finds in a linked list computed by the first pass.
 690  *
 691  * We use the mark flag to mark removable blocks in the first
 692  * phase.
 693  */
 694 void optimize_cf(ir_graph *irg) {
 695         int i, j, n;
 696         ir_node **in = NULL;
 697         ir_node *cond, *end = get_irg_end(irg);
 698         ir_graph *rem = current_ir_graph;
 699         plist_element_t *el;
 700         merge_env env;
 701
 702         assert(get_irg_phase_state(irg) != phase_building);
 703
 704         /* if the graph is not pinned, we cannot determine empty blocks */
 705         assert(get_irg_pinned(irg) != op_pin_state_floats &&
 706                "Control flow optimization need a pinned graph");
 707
 708         current_ir_graph = irg;
 709
 710         /* FIXME: control flow opt destroys block edges. So edges are deactivated here. Fix the edges! */
 711         edges_deactivate(irg);
 712
 713         /* we use the mark flag to mark removable blocks */
 714         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
 715 restart:
 716         env.changed    = 0;
 717         env.phis_moved = 0;
 718
 719         /* ALWAYS kill unreachable control flow. Backend cannot handle it anyway.
 720            Use dominator info to kill blocks. Also optimize useless Conds. */
 721         assure_doms(irg);
 722         irg_block_walk_graph(irg, NULL, remove_unreachable_blocks_and_conds, &env.changed);
 723
 724         /* fix the keep-alives */
 725         for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
 726                 ir_node *ka = get_End_keepalive(end, i);
 727
 728                 if (is_Block(ka)) {
 729                         /* do NOT keep dead blocks */
 730                         if (is_Block_dead(ka) || get_Block_dom_depth(ka) < 0) {
 731                                 set_End_keepalive(end, i, new_Bad());
 732                                 env.changed = 1;
 733                         }
 734                 } else if (is_Block_dead(get_nodes_block(ka)) ||
 735                            get_Block_dom_depth(get_nodes_block(ka)) < 0) {
 736                         /* do NOT keep nodes in dead blocks */
 737                         set_End_keepalive(end, i, new_Bad());
 738                         env.changed = 1;
 739                 }
 740         }
 741
 742         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 743
 744         env.list = plist_new();
 745         irg_walk(end, merge_blocks, collect_nodes, &env);
 746
 747         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 748
 749         if (env.changed) {
 750                 /* Handle graph state if was changed. */
 751                 set_irg_outs_inconsistent(irg);
 752                 set_irg_doms_inconsistent(irg);
 753                 set_irg_extblk_inconsistent(irg);
 754                 set_irg_loopinfo_inconsistent(irg);
 755                 env.changed = 0;
 756         }
 757
 758         /* handle all collected switch-Conds */
 759         foreach_plist(env.list, el) {
 760                 cond = plist_element_get_value(el);
 761                 env.changed |= handle_switch_cond(cond);
 762         }
 763         plist_free(env.list);
 764
 765         if (env.changed) {
 766                 /* The Cond optimization might generate unreachable code, so restart if
 767                    it happens. */
 768                 goto restart;
 769         }
 770
 771         /* Optimize the standard code. */
 772         env.changed = 0;
 773         assure_doms(irg);
 774         irg_block_walk(get_irg_end_block(irg), optimize_blocks, remove_simple_blocks, &env);
 775
 776         /* Walk all keep alives, optimize them if block, add to new in-array
 777            for end if useful. */
 778         n  = get_End_n_keepalives(end);
 779         if (n > 0)
 780                 NEW_ARR_A(ir_node *, in, n);
 781
 782         /* in rare cases a node may be kept alive more than once, use the visited flag to detect this */
 783         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 784         inc_irg_visited(irg);
 785
 786         /* fix the keep alive */
 787         for (i = j = 0; i < n; i++) {
 788                 ir_node *ka = get_End_keepalive(end, i);
 789
 790                 if (!irn_visited(ka)) {
 791                         if (is_Block(ka)) {
 792                                 if (!Block_block_visited(ka)) {
 793                                         /* irg_block_walk() will increase the block visited flag, but we must visit only
 794                                            these blocks that are not visited yet, so decrease it first. */
 795                                         set_irg_block_visited(irg, get_irg_block_visited(irg) - 1);
 796                                         irg_block_walk(ka, optimize_blocks, remove_simple_blocks, &env.changed);
 797                                         mark_irn_visited(ka);
 798                                         in[j++] = ka;
 799                                 }
 800                         } else {
 801                                 mark_irn_visited(ka);
 802                                 /* don't keep alive dead blocks */
 803                                 if (!is_Bad(ka) && !is_Block_dead(get_nodes_block(ka)))
 804                                         in[j++] = ka;
 805                         }
 806                 }
 807         }
 808         if (j != n) {
 809                 set_End_keepalives(end, j, in);
 810                 env.changed = 1;
 811         }
 812
 813         ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_VISITED);
 814
 815         if (env.phis_moved) {
 816                 /* Bad: when we moved Phi's, we might produce dead Phi nodes
 817                    that are kept-alive.
 818                    Some other phases cannot copy with this, so will them.
 819                  */
 820                 n = get_End_n_keepalives(end);
 821                 if (n > 0) {
 822                         if (env.changed) {
 823                                 /* Handle graph state if was changed. */
 824                                 set_irg_outs_inconsistent(irg);
 825                         }
 826                         assure_irg_outs(irg);
 827
 828                         for (i = j = 0; i < n; ++i) {
 829                                 ir_node *ka = get_End_keepalive(end, i);
 830
 831                                 if (is_Phi(ka)) {
 832                                         int k;
 833
 834                                         for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
 835                                                 ir_node *user = get_irn_out(ka, k);
 836
 837                                                 if (user != ka && user != end) {
 838                                                         /* Is it a real user or just a self loop ? */
 839                                                         break;
 840                                                 }
 841                                         }
 842                                         if (k >= 0)
 843                                                 in[j++] = ka;
 844                                 } else
 845                                         in[j++] = ka;
 846                         }
 847                         if (j != n) {
 848                                 set_End_keepalives(end, j, in);
 849                                 env.changed = 1;
 850                         }
 851                 }
 852         }
 853
 854         if (env.changed) {
 855                 /* Handle graph state if was changed. */
 856                 set_irg_outs_inconsistent(irg);
 857                 set_irg_doms_inconsistent(irg);
 858                 set_irg_extblk_inconsistent(irg);
 859                 set_irg_loopinfo_inconsistent(irg);
 860         }
 861
 862
 863         /* the verifier doesn't work yet with floating nodes */
 864         if (get_irg_pinned(irg) == op_pin_state_pinned) {
 865                 /* after optimize_cf(), only Bad data flow may remain. */
 866                 if (irg_vrfy_bads(irg, BAD_DF | BAD_BLOCK | TUPLE)) {
 867                         dump_ir_block_graph(irg, "-vrfy-cf");
 868                         dump_ir_graph(irg, "-vrfy-cf");
 869                         fprintf(stderr, "VRFY_BAD in optimize_cf()\n");
 870                 }
 871         }
 872
 873         current_ir_graph = rem;
 874 }