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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Control flow optimizations.
  23  * @author  Goetz Lindenmaier, Michael Beck, Sebastian Hack
  24  * @version $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include "iroptimize.h"
  31
  32 #include <assert.h>
  33
  34 #include "plist.h"
  35 #include "xmalloc.h"
  36 #include "irnode_t.h"
  37 #include "irgraph_t.h"
  38 #include "irprog_t.h"
  39
  40 #include "ircons.h"
  41 #include "iropt_t.h"
  42 #include "irgwalk.h"
  43 #include "irgmod.h"
  44 #include "irdump.h"
  45 #include "irvrfy.h"
  46 #include "iredges.h"
  47
  48 #include "array.h"
  49
  50 #include "irouts.h"
  51 #include "irbackedge_t.h"
  52
  53 #include "irflag_t.h"
  54 #include "firmstat.h"
  55
  56 #include "iropt_dbg.h"
  57
  58 /*------------------------------------------------------------------*/
  59 /* Control flow optimization.                                       */
  60 /*                                                                  */
  61 /* Removes Bad control flow predecessors and empty blocks.  A block */
  62 /* is empty if it contains only a Jmp node.                         */
  63 /* Blocks can only be removed if they are not needed for the        */
  64 /* semantics of Phi nodes.                                          */
  65 /* Further, we NEVER remove labeled blocks (even if we could move   */
  66 /* the label.                                                       */
  67 /*------------------------------------------------------------------*/
  68
  69 /**
  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  * Block walker removing control flow from dead block by
 192  * inspecting dominance info.
 193  * Do not replace blocks by Bad.  This optimization shall
 194  * ensure, that all Bad control flow predecessors are
 195  * removed, and no new other Bads are introduced.
 196  *
 197  * Must be run in the post walker.
 198  */
 199 static void remove_dead_block_cf(ir_node *block, void *env) {
 200         int i;
 201         int *changed = env;
 202
 203         /* check block predecessors and turn control flow into bad */
 204         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
 205                 ir_node *pred_X = get_Block_cfgpred(block, i);
 206
 207                 if (! is_Bad(pred_X)) {
 208                         ir_node *pred_bl = get_nodes_block(skip_Proj(pred_X));
 209
 210                         if (is_Block_dead(pred_bl) || (get_Block_dom_depth(pred_bl) < 0)) {
 211                                 set_Block_dead(pred_bl);
 212                                 exchange(pred_X, new_Bad());
 213                                 *changed = 1;
 214                         }
 215                 }
 216         }
 217 }
 218
 219 /**
 220  * Collects all Phi nodes in link list of Block.
 221  * Marks all blocks "block_visited" if they contain a node other
 222  * than Jmp (and Proj).
 223  * Links all Proj nodes to their predecessors.
 224  * Collects all switch-Conds in a list.
 225  */
 226 static void collect_nodes(ir_node *n, void *ctx) {
 227         ir_op *op = get_irn_op(n);
 228         merge_env *env = ctx;
 229
 230         if (op == op_Block) {
 231                 /* mark the block as non-empty if it is labeled */
 232                 if (has_Block_label(n))
 233                         mark_Block_block_visited(n);
 234         } else {
 235                 ir_node *b  = get_nodes_block(n);
 236
 237                 if (op == op_Phi && get_irn_arity(n) > 0) {
 238                         /* Collect Phi nodes to compact ins along with block's ins. */
 239                         set_irn_link(n, get_irn_link(b));
 240                         set_irn_link(b, n);
 241                 } else if (op != op_Jmp && !is_Bad(b)) {  /* Check for non empty block. */
 242                         mark_Block_block_visited(b);
 243
 244                         if (op == op_Proj) {               /* link Proj nodes */
 245                                 ir_node *pred = get_Proj_pred(n);
 246
 247                                 set_irn_link(n, get_irn_link(pred));
 248                                 set_irn_link(pred, n);
 249                         } else if (op == op_Cond) {
 250                                 ir_node *sel = get_Cond_selector(n);
 251                                 if (mode_is_int(get_irn_mode(sel))) {
 252                                         /* found a switch-Cond, collect */
 253                                         plist_insert_back(env->list, n);
 254                                 }
 255                         }
 256                 }
 257         }
 258 }
 259
 260 /** Returns true if pred is predecessor of block. */
 261 static int is_pred_of(ir_node *pred, ir_node *b) {
 262         int i, n;
 263
 264         for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
 265                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 266                 if (b_pred == pred) return 1;
 267         }
 268         return 0;
 269 }
 270
 271 /** Test whether we can optimize away pred block pos of b.
 272  *
 273  *  @param  b    A block node.
 274  *  @param  pos  The position of the predecessor block to judge about.
 275  *
 276  *  @returns     The number of predecessors
 277  *
 278  *  The test is rather tricky.
 279  *
 280  *  The situation is something like the following:
 281  *  @verbatim
 282  *                 if-block
 283  *                  /   \
 284  *              then-b  else-b
 285  *                  \   /
 286  *                    b
 287  *  @endverbatim
 288  *
 289  *  b merges the control flow of an if-then-else.  We may not remove
 290  *  the 'then' _and_ the 'else' block of an 'if' if there is a Phi
 291  *  node in b, even if both are empty.  The destruction of this Phi
 292  *  requires that a copy is added before the merge.  We have to
 293  *  keep one of the case blocks to place the copies in.
 294  *
 295  *  To perform the test for pos, we must regard predecessors before pos
 296  *  as already removed.
 297  **/
 298 static int test_whether_dispensable(ir_node *b, int pos) {
 299         int i, j, n_preds = 1;
 300         ir_node *pred = get_Block_cfgpred_block(b, pos);
 301
 302         /* Bad blocks will be optimized away, so we don't need space for them */
 303         if (is_Block_dead(pred))
 304                 return 0;
 305
 306         if (get_Block_block_visited(pred) + 1
 307                 < get_irg_block_visited(current_ir_graph)) {
 308
 309                 if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
 310                         /* Mark block so that is will not be removed: optimization is turned off. */
 311                         set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
 312                         return 1;
 313                 }
 314
 315                 /* Seems to be empty. At least we detected this in collect_nodes. */
 316                 if (get_irn_link(b) == NULL) {
 317                         /* There are no Phi nodes ==> all predecessors are dispensable. */
 318                         n_preds = get_Block_n_cfgpreds(pred);
 319                 } else {
 320                         /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
 321                            Handle all pred blocks with preds < pos as if they were already removed. */
 322                         for (i = 0; i < pos; i++) {
 323                                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 324                                 if (! is_Block_dead(b_pred) &&
 325                                         get_Block_block_visited(b_pred) + 1
 326                                         < get_irg_block_visited(current_ir_graph)) {
 327                                         for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
 328                                                 ir_node *b_pred_pred = get_Block_cfgpred_block(b_pred, j);
 329                                                 if (is_pred_of(b_pred_pred, pred))
 330                                                         goto non_dispensable;
 331                                         }
 332                                 } else {
 333                                         if (is_pred_of(b_pred, pred))
 334                                                 goto non_dispensable;
 335                                 }
 336                         }
 337                         for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
 338                                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 339                                 if (is_pred_of(b_pred, pred))
 340                                         goto non_dispensable;
 341                         }
 342                         /* if we get here, the block is dispensable */
 343                         n_preds = get_Block_n_cfgpreds(pred);
 344                 }
 345         }
 346
 347         return n_preds;
 348
 349 non_dispensable:
 350         set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
 351         return 1;
 352 }
 353
 354 /**
 355  * This method removed Bad cf predecessors from Blocks and Phis, and removes
 356  * empty blocks.  A block is empty if it only contains Phi and Jmp nodes.
 357  *
 358  * We first adapt Phi nodes, then Block nodes, as we need the old ins
 359  * of the Block to adapt the Phi nodes.  We do this by computing new
 360  * in arrays, and then replacing the old ones.  So far we compute new in arrays
 361  * for all nodes, not regarding whether there is a possibility for optimization.
 362  *
 363  * For each predecessor p of a Block b there are three cases:
 364  *  -1. The predecessor p is a Bad node:  just skip it.  The in array of b shrinks by one.
 365  *  -2. The predecessor p is empty.  Remove p.  All predecessors of p are now
 366  *      predecessors of b.
 367  *  -3. The predecessor p is a block containing useful code.  Just keep p as is.
 368  *
 369  * For Phi nodes f we have to check the conditions at the Block of f.
 370  * For cases 1 and 3 we proceed as for Blocks.  For case 2 we can have two
 371  * cases:
 372  *  -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED.  In this
 373  *      case we proceed as for blocks. We remove pred_f.  All
 374  *      predecessors of pred_f now are predecessors of f.
 375  *  -2b: The old predecessor of f is NOT in the block removed. It might be a Phi, too.
 376  *      We have to replicate f for each predecessor of the removed block. Or, with
 377  *      other words, the removed predecessor block has exactly one predecessor.
 378  *
 379  * Further there is a special case for self referencing blocks:
 380  * @verbatim
 381  *
 382  *    then_b     else_b                              then_b  else_b
 383  *       \      /                                      \      /
 384  *        \    /                                        |    /
 385  *        pred_b                                        |   /
 386  *         |   ____                                     |  /  ____
 387  *         |  |    |                                    |  | |    |
 388  *         |  |    |       === optimized to ===>        \  | |    |
 389  *        loop_b   |                                     loop_b   |
 390  *         |  |    |                                      |  |    |
 391  *         |  |____|                                      |  |____|
 392  *         |                                              |
 393  * @endverbatim
 394  *
 395  * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
 396  * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
 397  * backedge.
 398  * @@@ It is negotiable whether we should do this ... there might end up a copy
 399  * from the Phi in the loop when removing the Phis.
 400  */
 401 static void optimize_blocks(ir_node *b, void *ctx) {
 402         int i, j, k, n, max_preds, n_preds, p_preds = -1;
 403         ir_node *pred, *phi;
 404         ir_node **in;
 405         merge_env *env = ctx;
 406
 407         /* Count the number of predecessor if this block is merged with pred blocks
 408            that are empty. */
 409         max_preds = 0;
 410         for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
 411                 max_preds += test_whether_dispensable(b, i);
 412         }
 413         in = xmalloc(max_preds * sizeof(*in));
 414
 415         /*- Fix the Phi nodes of the current block -*/
 416         for (phi = get_irn_link(b); phi; ) {
 417                 assert(get_irn_op(phi) == op_Phi);
 418
 419                 /* Find the new predecessors for the Phi */
 420                 p_preds = 0;
 421                 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
 422                         pred = get_Block_cfgpred_block(b, i);
 423
 424                         if (is_Bad(get_Block_cfgpred(b, i))) {
 425                                 /* case Phi 1: Do nothing */
 426                         }
 427                         else if (get_Block_block_visited(pred) + 1
 428                                  < get_irg_block_visited(current_ir_graph)) {
 429                                 /* case Phi 2: It's an empty block and not yet visited. */
 430                                 ir_node *phi_pred = get_Phi_pred(phi, i);
 431
 432                                 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
 433                                         /* because of breaking loops, not all predecessors are Bad-clean,
 434                                          * so we must check this here again */
 435                                         if (! is_Bad(get_Block_cfgpred(pred, j))) {
 436                                                 if (get_nodes_block(phi_pred) == pred) {
 437                                                         /* case Phi 2a: */
 438                                                         assert(get_irn_op(phi_pred) == op_Phi);  /* Block is empty!! */
 439
 440                                                         in[p_preds++] = get_Phi_pred(phi_pred, j);
 441                                                 } else {
 442                                                         /* case Phi 2b: */
 443                                                         in[p_preds++] = phi_pred;
 444                                                 }
 445                                         }
 446                                 }
 447                         } else {
 448                                 /* case Phi 3: */
 449                                 in[p_preds++] = get_Phi_pred(phi, i);
 450                         }
 451                 }
 452                 assert(p_preds <= max_preds);
 453
 454                 /* Fix the node */
 455                 if (p_preds == 1)
 456                         /* By removal of Bad ins the Phi might be degenerated. */
 457                         exchange(phi, in[0]);
 458                 else
 459                         set_irn_in(phi, p_preds, in);
 460                 env->changed = 1;
 461
 462                 phi = get_irn_link(phi);
 463         }
 464
 465         /*- This happens only if merge between loop backedge and single loop entry.
 466             Moreover, it is only needed if predb is the direct dominator of b, else there can be no uses
 467             of the Phi's in predb ... -*/
 468         for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
 469                 ir_node *predb = get_nodes_block(get_Block_cfgpred(b, k));
 470
 471                 if (get_Block_block_visited(predb) + 1 < get_irg_block_visited(current_ir_graph)) {
 472                         ir_node *next_phi;
 473
 474                         /* we found a predecessor block at position k that will be removed */
 475                         for (phi = get_irn_link(predb); phi; phi = next_phi) {
 476                                 int q_preds = 0;
 477                                 next_phi = get_irn_link(phi);
 478
 479                                 assert(is_Phi(phi));
 480
 481                                 if (get_Block_idom(b) != predb) {
 482                                         /* predb is not the dominator. There can't be uses of pred's Phi nodes, kill them .*/
 483                                         exchange(phi, new_Bad());
 484                                 } else {
 485                                         /* predb is the direct dominator of b. There might be uses of the Phi nodes from
 486                                            predb in further block, so move this phi from the predecessor into the block b */
 487                                         set_nodes_block(phi, b);
 488                                         set_irn_link(phi, get_irn_link(b));
 489                                         set_irn_link(b, phi);
 490                                         env->phis_moved = 1;
 491
 492                                         /* first, copy all 0..k-1 predecessors */
 493                                         for (i = 0; i < k; i++) {
 494                                                 pred = get_Block_cfgpred_block(b, i);
 495
 496                                                 if (is_Bad(pred)) {
 497                                                         /* Do nothing */
 498                                                 } else if (get_Block_block_visited(pred) + 1
 499                                                         < get_irg_block_visited(current_ir_graph)) {
 500                                                         /* It's an empty block and not yet visited. */
 501                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 502                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 503                                                                         in[q_preds++] = phi;
 504                                                         }
 505                                                 } else {
 506                                                         in[q_preds++] = phi;
 507                                                 }
 508                                         }
 509
 510                                         /* now we are at k, copy the phi predecessors */
 511                                         pred = get_nodes_block(get_Block_cfgpred(b, k));
 512                                         for (i = 0; i < get_Phi_n_preds(phi); i++) {
 513                                                 if (! is_Bad(get_Block_cfgpred(pred, i)))
 514                                                         in[q_preds++] = get_Phi_pred(phi, i);
 515                                         }
 516
 517                                         /* and now all the rest */
 518                                         for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
 519                                                 pred = get_nodes_block(get_Block_cfgpred(b, i));
 520
 521                                                 if (is_Bad(get_Block_cfgpred(b, i))) {
 522                                                         /* Do nothing */
 523                                                 } else if (get_Block_block_visited(pred) +1
 524                                                         < get_irg_block_visited(current_ir_graph)) {
 525                                                         /* It's an empty block and not yet visited. */
 526                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 527                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 528                                                                         in[q_preds++] = phi;
 529                                                         }
 530                                                 } else {
 531                                                         in[q_preds++] = phi;
 532                                                 }
 533                                         }
 534
 535                                         /* Fix the node */
 536                                         if (q_preds == 1)
 537                                                 exchange(phi, in[0]);
 538                                         else
 539                                                 set_irn_in(phi, q_preds, in);
 540                                         env->changed = 1;
 541
 542                                         assert(q_preds <= max_preds);
 543                                         // assert(p_preds == q_preds && "Wrong Phi Fix");
 544                                 }
 545                         }
 546                 }
 547         }
 548
 549         /*- Fix the block -*/
 550         n_preds = 0;
 551         for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 552                 pred = get_Block_cfgpred_block(b, i);
 553
 554                 if (is_Bad(pred)) {
 555                         /* case 1: Do nothing */
 556                 } else if (get_Block_block_visited(pred) +1
 557                         < get_irg_block_visited(current_ir_graph)) {
 558                         /* case 2: It's an empty block and not yet visited. */
 559                         assert(get_Block_n_cfgpreds(b) > 1);
 560                         /* Else it should be optimized by equivalent_node. */
 561                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 562                                 ir_node *pred_block = get_Block_cfgpred(pred, j);
 563
 564                                 /* because of breaking loops, not all predecessors are Bad-clean,
 565                                  * so we must check this here again */
 566                                 if (! is_Bad(pred_block))
 567                                         in[n_preds++] = pred_block;
 568                         }
 569                         /* Remove block as it might be kept alive. */
 570                         exchange(pred, b/*new_Bad()*/);
 571                 } else {
 572                         /* case 3: */
 573                         in[n_preds++] = get_Block_cfgpred(b, i);
 574                 }
 575         }
 576         assert(n_preds <= max_preds);
 577
 578         set_irn_in(b, n_preds, in);
 579         env->changed = 1;
 580
 581         assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds && "Wrong Phi Fix"));
 582         xfree(in);
 583 }
 584
 585 /**
 586  * Block walker: optimize all blocks using the default optimizations.
 587  * This removes Blocks that with only a Jmp predecessor.
 588  */
 589 static void remove_simple_blocks(ir_node *block, void *ctx) {
 590         ir_node *new_blk = equivalent_node(block);
 591         merge_env *env = ctx;
 592
 593         if (new_blk != block) {
 594                 exchange(block, new_blk);
 595                 env->changed = 1;
 596         }
 597 }
 598
 599 /**
 600  * Handle pre-optimized table switch Cond's.
 601  * During iropt, all Projs from a switch-Cond are already removed except
 602  * the defProj and maybe the taken one.
 603  * The defProj cannot be removed WITHOUT looking backwards, so we do this here.
 604  *
 605  * @param cond the switch-Cond
 606  *
 607  * @return non-zero if a switch-Cond was optimized
 608  *
 609  * Expects all Proj's linked to the cond node
 610  */
 611 static int handle_switch_cond(ir_node *cond) {
 612         ir_node *sel = get_Cond_selector(cond);
 613
 614         ir_node *proj1 = get_irn_link(cond);
 615         ir_node *proj2 = get_irn_link(proj1);
 616         ir_node *jmp, *blk;
 617
 618         blk = get_nodes_block(cond);
 619
 620         if (proj2 == NULL) {
 621                 /* this Cond has only one Proj: must be the defProj */
 622                 assert(get_Cond_defaultProj(cond) == get_Proj_proj(proj1));
 623                 /* convert it into a Jmp */
 624                 jmp = new_r_Jmp(current_ir_graph, blk);
 625                 exchange(proj1, jmp);
 626                 return 1;
 627         } else if (get_irn_link(proj2) == NULL) {
 628                 /* We have two Proj's here. Check if the Cond has
 629                    a constant argument */
 630                 tarval *tv = value_of(sel);
 631
 632                 if (tv != tarval_bad) {
 633                         /* we have a constant switch */
 634                         long num     = get_tarval_long(tv);
 635                         long def_num = get_Cond_defaultProj(cond);
 636
 637                         if (def_num == get_Proj_proj(proj1)) {
 638                                 /* first one is the defProj */
 639                                 if (num == get_Proj_proj(proj2)) {
 640                                         jmp = new_r_Jmp(current_ir_graph, blk);
 641                                         exchange(proj2, jmp);
 642                                         exchange(proj1, new_Bad());
 643                                         return 1;
 644                                 }
 645                         } else if (def_num == get_Proj_proj(proj2)) {
 646                                 /* second one is the defProj */
 647                                 if (num == get_Proj_proj(proj1)) {
 648                                         jmp = new_r_Jmp(current_ir_graph, blk);
 649                                         exchange(proj1, jmp);
 650                                         exchange(proj2, new_Bad());
 651                                         return 1;
 652                                 }
 653                         } else {
 654                                 /* neither: strange, Cond was not optimized so far */
 655                                 if (num == get_Proj_proj(proj1)) {
 656                                         jmp = new_r_Jmp(current_ir_graph, blk);
 657                                         exchange(proj1, jmp);
 658                                         exchange(proj2, new_Bad());
 659                                         return 1;
 660                                 } else if (num == get_Proj_proj(proj2)) {
 661                                         jmp = new_r_Jmp(current_ir_graph, blk);
 662                                         exchange(proj2, jmp);
 663                                         exchange(proj1, new_Bad());
 664                                         return 1;
 665                                 }
 666                         }
 667                 }
 668         }
 669         return 0;
 670 }
 671
 672 /* Optimizations of the control flow that also require changes of Phi nodes.
 673  *
 674  * This optimization performs two passes over the graph.
 675  *
 676  * The first pass collects all Phi nodes in a link list in the block
 677  * nodes.  Further it performs simple control flow optimizations.
 678  * Finally it marks all blocks that do not contain useful
 679  * computations, i.e., these blocks might be removed.
 680  *
 681  * The second pass performs the optimizations intended by this algorithm.
 682  * It walks only over block nodes and adapts these and the Phi nodes in these blocks,
 683  * which it finds in a linked list computed by the first pass.
 684  *
 685  * We use the block_visited flag to mark empty blocks in the first
 686  * phase.
 687  * @@@ It would be better to add a struct in the link field
 688  * that keeps the Phi list and the mark.  Place it on an obstack, as
 689  * we will lose blocks and thereby generate memory leaks.
 690  */
 691 void optimize_cf(ir_graph *irg) {
 692         int i, j, n;
 693         ir_node **in = NULL;
 694         ir_node *cond, *end = get_irg_end(irg);
 695         ir_graph *rem = current_ir_graph;
 696         plist_element_t *el;
 697         merge_env env;
 698
 699         assert(get_irg_phase_state(irg) != phase_building);
 700
 701         /* if the graph is not pinned, we cannot determine empty blocks */
 702         assert(get_irg_pinned(irg) != op_pin_state_floats &&
 703                "Control flow optimization need a pinned graph");
 704
 705         current_ir_graph = irg;
 706
 707         /* FIXME: is this still needed? */
 708         edges_deactivate(irg);
 709
 710 restart:
 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                 goto restart;
 767         }
 768
 769         /* Optimize the standard code. */
 770         env.changed = 0;
 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_irn_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_irn_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 }