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

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