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  * Removes Bad control flow predecessors and empty blocks.  A block is empty
  27  * if it contains only a Jmp node. Blocks can only be removed if they are not
  28  * needed for the semantics of Phi nodes. Further, we NEVER remove labeled
  29  * blocks (even if we could move the label).
  30  */
  31 #include "config.h"
  32
  33 #include "iroptimize.h"
  34
  35 #include <assert.h>
  36 #include <stdbool.h>
  37
  38 #include "xmalloc.h"
  39 #include "irnode_t.h"
  40 #include "irgraph_t.h"
  41 #include "irprog_t.h"
  42
  43 #include "ircons.h"
  44 #include "iropt_t.h"
  45 #include "irgwalk.h"
  46 #include "irgmod.h"
  47 #include "irdump.h"
  48 #include "irverify.h"
  49 #include "iredges.h"
  50 #include "opt_manage.h"
  51
  52 #include "array_t.h"
  53
  54 #include "irouts.h"
  55 #include "irbackedge_t.h"
  56
  57 #include "irflag_t.h"
  58 #include "firmstat.h"
  59 #include "irpass.h"
  60 #include "irnodehashmap.h"
  61 #include "irtools.h"
  62
  63 #include "iropt_dbg.h"
  64
  65 /** An environment for merge_blocks and collect nodes. */
  66 typedef struct merge_env {
  67         bool      changed;      /**< Set if the graph was changed. */
  68         bool      phis_moved;   /**< Set if Phi nodes were moved. */
  69 } merge_env;
  70
  71 /** set or reset the removable property of a block. */
  72 static void set_Block_removable(ir_node *block, bool removable)
  73 {
  74         set_Block_mark(block, removable);
  75 }
  76
  77 /** check if a block has the removable property set. */
  78 static bool is_Block_removable(const ir_node *block)
  79 {
  80         return get_Block_mark(block);
  81 }
  82
  83 /** checks if a given Cond node is a switch Cond. */
  84 static bool is_switch_Cond(const ir_node *cond)
  85 {
  86         ir_node *sel = get_Cond_selector(cond);
  87         return get_irn_mode(sel) != mode_b;
  88 }
  89
  90 /** Walker: clear link fields and mark all blocks as removable. */
  91 static void clear_link_and_mark_blocks_removable(ir_node *node, void *ctx)
  92 {
  93         (void) ctx;
  94         set_irn_link(node, NULL);
  95         if (is_Block(node)) {
  96                 set_Block_removable(node, true);
  97                 set_Block_phis(node, NULL);
  98         } else if (is_Phi(node)) {
  99                 set_Phi_next(node, NULL);
 100         }
 101 }
 102
 103 /**
 104  * Collects all Phi nodes in link list of Block.
 105  * Marks all blocks "non_removable" if they contain a node other
 106  * than Jmp (and Proj).
 107  * Links all Proj nodes to their predecessors.
 108  * Collects all switch-Conds in a list.
 109  */
 110 static void collect_nodes(ir_node *n, void *ctx)
 111 {
 112         ir_node ***switch_conds = (ir_node***)ctx;
 113
 114         if (is_Phi(n)) {
 115                 /* Collect Phi nodes to compact ins along with block's ins. */
 116                 ir_node *block = get_nodes_block(n);
 117                 add_Block_phi(block, n);
 118         } else if (is_Block(n)) {
 119                 if (has_Block_entity(n)) {
 120                         /* block with a jump label attached cannot be removed. */
 121                         set_Block_removable(n, false);
 122                 }
 123         } else if (is_Bad(n) || is_Jmp(n)) {
 124                 /* ignore these */
 125                 return;
 126         } else {
 127                 /* Check for non-empty block. */
 128                 ir_node *block = get_nodes_block(n);
 129
 130                 set_Block_removable(block, false);
 131
 132                 if (is_Proj(n)) {
 133                         /* link Proj nodes */
 134                         ir_node *pred = get_Proj_pred(n);
 135                         set_irn_link(n, get_irn_link(pred));
 136                         set_irn_link(pred, n);
 137                 } else if (is_Cond(n) && is_switch_Cond(n)) {
 138                         /* found a switch-Cond, collect */
 139                         ARR_APP1(ir_node*, *switch_conds, n);
 140                 }
 141         }
 142 }
 143
 144 /** Returns true if pred is predecessor of block b. */
 145 static bool is_pred_of(const ir_node *pred, const ir_node *b)
 146 {
 147         int i;
 148
 149         for (i = get_Block_n_cfgpreds(b) - 1; i >= 0; --i) {
 150                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 151                 if (b_pred == pred)
 152                         return true;
 153         }
 154         return false;
 155 }
 156
 157 /** Test whether we can optimize away pred block pos of b.
 158  *
 159  *  @param  b    A block node.
 160  *  @param  pos  The position of the predecessor block to judge about.
 161  *
 162  *  @returns     The number of predecessors
 163  *
 164  *  The test is rather tricky.
 165  *
 166  *  The situation is something like the following:
 167  *  @verbatim
 168  *                 if-block
 169  *                  /   \
 170  *              then-b  else-b
 171  *                  \   /
 172  *                    b
 173  *  @endverbatim
 174  *
 175  *  b merges the control flow of an if-then-else.  We may not remove
 176  *  the 'then' _and_ the 'else' block of an 'if' if there is a Phi
 177  *  node in b, even if both are empty.  The destruction of this Phi
 178  *  requires that a copy is added before the merge.  We have to
 179  *  keep one of the case blocks to place the copies in.
 180  *
 181  *  To perform the test for pos, we must regard predecessors before pos
 182  *  as already removed.
 183  **/
 184 static unsigned test_whether_dispensable(const ir_node *b, int pos)
 185 {
 186         ir_node *pred  = get_Block_cfgpred(b, pos);
 187         ir_node *predb = get_nodes_block(pred);
 188
 189         if (is_Bad(pred) || !is_Block_removable(predb))
 190                 return 1;
 191
 192         /* can't remove self-loops */
 193         if (predb == b)
 194                 goto non_dispensable;
 195         if (is_unknown_jump(pred))
 196                 goto non_dispensable;
 197
 198         /* Seems to be empty. At least we detected this in collect_nodes. */
 199         if (get_Block_phis(b) != NULL) {
 200                 int n_cfgpreds = get_Block_n_cfgpreds(b);
 201                 int i;
 202                 /* there are Phi nodes */
 203
 204                 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
 205                  * Handle all pred blocks with preds < pos as if they were already
 206                  * removed. */
 207                 for (i = 0; i < pos; i++) {
 208                         ir_node *other_pred  = get_Block_cfgpred(b, i);
 209                         ir_node *other_predb = get_nodes_block(other_pred);
 210                         if (is_Bad(other_pred))
 211                                 continue;
 212                         if (is_Block_removable(other_predb)
 213                             && !Block_block_visited(other_predb)) {
 214                                 int j;
 215                                 for (j = get_Block_n_cfgpreds(other_predb) - 1; j >= 0; --j) {
 216                                         ir_node *other_predpred
 217                                                 = get_Block_cfgpred_block(other_predb, j);
 218                                         if (is_pred_of(other_predpred, predb))
 219                                                 goto non_dispensable;
 220                                 }
 221                         } else if (is_pred_of(other_predb, predb)) {
 222                                 goto non_dispensable;
 223                         }
 224                 }
 225                 for (i = pos+1; i < n_cfgpreds; i++) {
 226                         ir_node *other_predb = get_Block_cfgpred_block(b, i);
 227                         if (is_pred_of(other_predb, predb))
 228                                 goto non_dispensable;
 229                 }
 230         }
 231         /* we will not dispense already visited blocks */
 232         if (Block_block_visited(predb))
 233                 return 1;
 234         /* if we get here, the block is dispensable, count useful preds */
 235         return get_irn_arity(predb);
 236
 237 non_dispensable:
 238         set_Block_removable(predb, false);
 239         return 1;
 240 }
 241
 242 /**
 243  * This method removes empty blocks.  A block is empty if it only contains Phi
 244  * and Jmp nodes.
 245  *
 246  * We first adapt Phi nodes, then Block nodes, as we need the old ins
 247  * of the Block to adapt the Phi nodes.  We do this by computing new
 248  * in arrays, and then replacing the old ones.  So far we compute new in arrays
 249  * for all nodes, not regarding whether there is a possibility for optimization.
 250  *
 251  * For each predecessor p of a Block b there are three cases:
 252  *  - The predecessor p is a Bad node: just skip it. The in array of b shrinks
 253  *    by one.
 254  *  - The predecessor p is empty. Remove p. All predecessors of p are now
 255  *    predecessors of b.
 256  *  - The predecessor p is a block containing useful code. Just keep p as is.
 257  *
 258  * For Phi nodes f we have to check the conditions at the Block of f.
 259  * For cases 1 and 3 we proceed as for Blocks.  For case 2 we can have two
 260  * cases:
 261  *  -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED.
 262  *       In this case we proceed as for blocks. We remove pred_f.  All
 263  *       predecessors of pred_f now are predecessors of f.
 264  *  -2b: The old predecessor of f is NOT in the block removed. It might be a Phi
 265  *       too. We have to replicate f for each predecessor of the removed block.
 266  *       Or, with other words, the removed predecessor block has exactly one
 267  *       predecessor.
 268  *
 269  * Further there is a special case for self referencing blocks:
 270  * @verbatim
 271  *
 272  *    then_b     else_b                              then_b  else_b
 273  *       \      /                                      \      /
 274  *        \    /                                        |    /
 275  *        pred_b                                        |   /
 276  *         |   ____                                     |  /  ____
 277  *         |  |    |                                    |  | |    |
 278  *         |  |    |       === optimized to ===>        \  | |    |
 279  *        loop_b   |                                     loop_b   |
 280  *         |  |    |                                      |  |    |
 281  *         |  |____|                                      |  |____|
 282  *         |                                              |
 283  * @endverbatim
 284  *
 285  * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
 286  * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
 287  * backedge.
 288  */
 289 static void optimize_blocks(ir_node *b, void *ctx)
 290 {
 291         int i, j, k, n, max_preds, n_preds, p_preds = -1;
 292         ir_node *phi;
 293         ir_node *next;
 294         ir_node **in;
 295         merge_env *env = (merge_env*)ctx;
 296
 297         if (get_Block_dom_depth(b) < 0) {
 298                 /* ignore unreachable blocks */
 299                 return;
 300         }
 301
 302         /* Count the number of predecessor if this block is merged with pred blocks
 303            that are empty. */
 304         max_preds = 0;
 305         for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
 306                 max_preds += test_whether_dispensable(b, i);
 307         }
 308         in = XMALLOCN(ir_node*, max_preds);
 309
 310         /*- Fix the Phi nodes of the current block -*/
 311         for (phi = get_Block_phis(b); phi != NULL; phi = next) {
 312                 next = get_Phi_next(phi);
 313
 314                 /* Find the new predecessors for the Phi */
 315                 p_preds = 0;
 316                 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
 317                         ir_graph *irg = get_irn_irg(b);
 318                         ir_node *predx = get_Block_cfgpred(b, i);
 319                         ir_node *pred;
 320
 321                         /* case Phi 1: maintain Bads, as somebody else is responsible to
 322                          * remove them */
 323                         if (is_Bad(predx)) {
 324                                 in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
 325                                 continue;
 326                         }
 327
 328                         pred = get_nodes_block(predx);
 329
 330                         /* case Phi 2: It's an empty block and not yet visited. */
 331                         if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 332                                 ir_node *phi_pred = get_Phi_pred(phi, i);
 333
 334                                 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
 335                                         ir_node *pred_pred = get_Block_cfgpred(pred, j);
 336
 337                                         if (is_Bad(pred_pred)) {
 338                                                 in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
 339                                                 continue;
 340                                         }
 341
 342                                         if (get_nodes_block(phi_pred) == pred) {
 343                                                 /* case Phi 2a: */
 344                                                 assert(is_Phi(phi_pred));  /* Block is empty!! */
 345
 346                                                 in[p_preds++] = get_Phi_pred(phi_pred, j);
 347                                         } else {
 348                                                 /* case Phi 2b: */
 349                                                 in[p_preds++] = phi_pred;
 350                                         }
 351                                 }
 352                         } else {
 353                                 /* case Phi 3: */
 354                                 in[p_preds++] = get_Phi_pred(phi, i);
 355                         }
 356                 }
 357                 assert(p_preds == max_preds);
 358
 359                 /* Fix the node */
 360                 if (p_preds == 1) {
 361                         exchange(phi, in[0]);
 362                 } else {
 363                         set_irn_in(phi, p_preds, in);
 364                 }
 365                 env->changed = true;
 366         }
 367
 368         /*- This happens only if merge between loop backedge and single loop entry.
 369             Moreover, it is only needed if predb is the direct dominator of b,
 370             else there can be no uses of the Phi's in predb ... -*/
 371         for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
 372                 ir_node *pred  = get_Block_cfgpred(b, k);
 373                 ir_node *predb = get_nodes_block(pred);
 374                 if (is_Bad(pred))
 375                         continue;
 376
 377                 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
 378                         ir_node *next_phi;
 379
 380                         /* we found a predecessor block at position k that will be removed */
 381                         for (phi = get_Block_phis(predb); phi != NULL; phi = next_phi) {
 382                                 int q_preds = 0;
 383                                 next_phi = get_Phi_next(phi);
 384
 385                                 if (get_Block_idom(b) != predb) {
 386                                         /* predb is not the dominator. There can't be uses of
 387                                          * pred's Phi nodes, kill them .*/
 388                                         ir_graph *irg  = get_irn_irg(b);
 389                                         ir_mode  *mode = get_irn_mode(phi);
 390                                         exchange(phi, new_r_Bad(irg, mode));
 391                                 } else {
 392                                         /* predb is the direct dominator of b. There might be uses
 393                                          * of the Phi nodes from predb in further block, so move
 394                                          * this phi from the predecessor into the block b */
 395                                         set_nodes_block(phi, b);
 396                                         set_Phi_next(phi, get_Block_phis(b));
 397                                         set_Block_phis(b, phi);
 398                                         env->phis_moved = true;
 399
 400                                         /* first, copy all 0..k-1 predecessors */
 401                                         for (i = 0; i < k; i++) {
 402                                                 ir_node *predx = get_Block_cfgpred(b, i);
 403                                                 ir_node *pred_block;
 404
 405                                                 if (is_Bad(predx)) {
 406                                                         ir_graph *irg  = get_irn_irg(b);
 407                                                         ir_mode  *mode = get_irn_mode(phi);
 408                                                         in[q_preds++] = new_r_Bad(irg, mode);
 409                                                         continue;
 410                                                 }
 411                                                 pred_block = get_nodes_block(predx);
 412                                                 if (is_Block_removable(pred_block)
 413                                                            && !Block_block_visited(pred_block)) {
 414                                                         int n_cfgpreds = get_Block_n_cfgpreds(pred_block);
 415                                                         /* It's an empty block and not yet visited. */
 416                                                         for (j = 0; j < n_cfgpreds; j++) {
 417                                                                 if (!is_Bad(get_Block_cfgpred(pred_block, j))) {
 418                                                                         in[q_preds++] = phi;
 419                                                                 } else {
 420                                                                         ir_graph *irg  = get_irn_irg(b);
 421                                                                         ir_mode  *mode = get_irn_mode(phi);
 422                                                                         in[q_preds++] = new_r_Bad(irg, mode);
 423                                                                 }
 424                                                         }
 425                                                 } else {
 426                                                         in[q_preds++] = phi;
 427                                                 }
 428                                         }
 429
 430                                         /* now we are at k, copy the phi predecessors */
 431                                         pred = get_nodes_block(get_Block_cfgpred(b, k));
 432                                         for (i = 0; i < get_Phi_n_preds(phi); i++) {
 433                                                 in[q_preds++] = get_Phi_pred(phi, i);
 434                                         }
 435
 436                                         /* and now all the rest */
 437                                         for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
 438                                                 pred = get_Block_cfgpred_block(b, i);
 439
 440                                                 if (is_Bad(pred)) {
 441                                                         ir_graph *irg  = get_irn_irg(b);
 442                                                         ir_mode  *mode = get_irn_mode(phi);
 443                                                         in[q_preds++] = new_r_Bad(irg, mode);
 444                                                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 445                                                         /* It's an empty block and not yet visited. */
 446                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 447                                                                 if (! is_Bad(get_Block_cfgpred(pred, j))) {
 448                                                                         in[q_preds++] = phi;
 449                                                                 } else {
 450                                                                         ir_graph *irg  = get_irn_irg(b);
 451                                                                         ir_mode  *mode = get_irn_mode(phi);
 452                                                                         in[q_preds++] = new_r_Bad(irg, mode);
 453                                                                 }
 454                                                         }
 455                                                 } else {
 456                                                         in[q_preds++] = phi;
 457                                                 }
 458                                         }
 459
 460                                         /* Fix the node */
 461                                         if (q_preds == 1)
 462                                                 exchange(phi, in[0]);
 463                                         else
 464                                                 set_irn_in(phi, q_preds, in);
 465                                         env->changed = true;
 466
 467                                         assert(q_preds <= max_preds);
 468                                         // assert(p_preds == q_preds && "Wrong Phi Fix");
 469                                 }
 470                         }
 471                 }
 472         }
 473
 474         /*- Fix the block -*/
 475         n_preds = 0;
 476         for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 477                 ir_node *pred  = get_Block_cfgpred(b, i);
 478                 ir_node *predb = get_nodes_block(pred);
 479                 ir_graph *irg  = get_irn_irg(pred);
 480
 481                 /* case 1: Bad predecessor */
 482                 if (is_Bad(pred)) {
 483                         in[n_preds++] = new_r_Bad(irg, mode_X);
 484                         continue;
 485                 }
 486                 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
 487                         /* case 2: It's an empty block and not yet visited. */
 488                         for (j = 0; j < get_Block_n_cfgpreds(predb); j++) {
 489                                 ir_node *predpred = get_Block_cfgpred(predb, j);
 490
 491                                 if (is_Bad(predpred)) {
 492                                         in[n_preds++] = new_r_Bad(irg, mode_X);
 493                                         continue;
 494                                 }
 495
 496                                 in[n_preds++] = predpred;
 497                         }
 498                         /* Remove block+jump as it might be kept alive. */
 499                         exchange(pred, new_r_Bad(get_irn_irg(b), mode_X));
 500                         exchange(predb, new_r_Bad(get_irn_irg(b), mode_BB));
 501                 } else {
 502                         /* case 3: */
 503                         in[n_preds++] = pred;
 504                 }
 505         }
 506         assert(n_preds == max_preds);
 507
 508         set_irn_in(b, n_preds, in);
 509         env->changed = true;
 510
 511         /* see if phi-fix was correct */
 512         assert(get_Block_phis(b) == NULL || p_preds == -1 || (n_preds == p_preds));
 513         xfree(in);
 514 }
 515
 516 /**
 517  * Optimize table-switch Conds.
 518  *
 519  * @param cond the switch-Cond
 520  * @return true if the switch-Cond was optimized
 521  */
 522 static bool handle_switch_cond(ir_node *cond)
 523 {
 524         ir_node *sel   = get_Cond_selector(cond);
 525         ir_node *proj1 = (ir_node*)get_irn_link(cond);
 526         ir_node *proj2 = (ir_node*)get_irn_link(proj1);
 527         ir_node *blk   = get_nodes_block(cond);
 528
 529         /* exactly 1 Proj on the Cond node: must be the defaultProj */
 530         if (proj2 == NULL) {
 531                 ir_node *jmp = new_r_Jmp(blk);
 532                 assert(get_Cond_default_proj(cond) == get_Proj_proj(proj1));
 533                 /* convert it into a Jmp */
 534                 exchange(proj1, jmp);
 535                 return true;
 536         }
 537
 538         /* handle Cond nodes with constant argument. In this case the localopt rules
 539          * should have killed all obviously impossible cases.
 540          * So the only case left to handle here is 1 defaultProj + 1 case
 541          * (this one case should be the one taken) */
 542         if (get_irn_link(proj2) == NULL) {
 543                 ir_tarval *tv = value_of(sel);
 544
 545                 if (tv != tarval_bad) {
 546                         /* we have a constant switch */
 547                         long      num     = get_tarval_long(tv);
 548                         long      def_num = get_Cond_default_proj(cond);
 549                         ir_graph *irg     = get_irn_irg(cond);
 550                         ir_node  *bad     = new_r_Bad(irg, mode_X);
 551
 552                         if (def_num == get_Proj_proj(proj1)) {
 553                                 /* first one is the defProj */
 554                                 if (num == get_Proj_proj(proj2)) {
 555                                         ir_node *jmp = new_r_Jmp(blk);
 556                                         exchange(proj2, jmp);
 557                                         exchange(proj1, bad);
 558                                         return true;
 559                                 }
 560                         } else if (def_num == get_Proj_proj(proj2)) {
 561                                 /* second one is the defProj */
 562                                 if (num == get_Proj_proj(proj1)) {
 563                                         ir_node *jmp = new_r_Jmp(blk);
 564                                         exchange(proj1, jmp);
 565                                         exchange(proj2, bad);
 566                                         return true;
 567                                 }
 568                         } else {
 569                                 /* neither: strange, Cond was not optimized so far */
 570                                 if (num == get_Proj_proj(proj1)) {
 571                                         ir_node *jmp = new_r_Jmp(blk);
 572                                         exchange(proj1, jmp);
 573                                         exchange(proj2, bad);
 574                                         return true;
 575                                 } else if (num == get_Proj_proj(proj2)) {
 576                                         ir_node *jmp = new_r_Jmp(blk);
 577                                         exchange(proj2, jmp);
 578                                         exchange(proj1, bad);
 579                                         return true;
 580                                 }
 581                         }
 582                 }
 583         }
 584         return false;
 585 }
 586
 587 /**
 588  * Optimize boolean Conds, where true and false jump to the same block into a Jmp
 589  * Block must contain no Phi nodes.
 590  *
 591  *        Cond
 592  *       /    \
 593  *  projA      projB   =>   Jmp     Bad
 594  *       \    /                \   /
 595  *       block                 block
 596  */
 597 static bool optimize_pred_cond(ir_node *block, int i, int j)
 598 {
 599         ir_node *projA, *projB, *cond, *pred_block, *jmp, *bad;
 600         assert(i != j);
 601
 602         projA = get_Block_cfgpred(block, i);
 603         if (!is_Proj(projA)) return false;
 604         projB = get_Block_cfgpred(block, j);
 605         if (!is_Proj(projB)) return false;
 606         cond  = get_Proj_pred(projA);
 607         if (!is_Cond(cond))  return false;
 608
 609         if (cond != get_Proj_pred(projB)) return false;
 610         if (is_switch_Cond(cond)) return false;
 611
 612         /* cond should actually be a Jmp */
 613         pred_block = get_nodes_block(cond);
 614         jmp = new_r_Jmp(pred_block);
 615         bad = new_r_Bad(get_irn_irg(block), mode_X);
 616
 617         assert(projA != projB);
 618         exchange(projA, jmp);
 619         exchange(projB, bad);
 620         return true;
 621 }
 622
 623 typedef enum block_flags_t {
 624         BF_HAS_OPERATIONS         = 1 << 0,
 625         BF_HAS_PHIS               = 1 << 1,
 626         BF_IS_UNKNOWN_JUMP_TARGET = 1 << 2,
 627 } block_flags_t;
 628
 629 static bool get_block_flag(const ir_nodehashmap_t *infos, const ir_node *block,
 630                            int flag)
 631 {
 632         return PTR_TO_INT(ir_nodehashmap_get(infos, block)) & flag;
 633 }
 634
 635 static void set_block_flag(ir_nodehashmap_t *infos, ir_node *block,
 636                            block_flags_t flag)
 637 {
 638         int data = PTR_TO_INT(ir_nodehashmap_get(infos, block));
 639         data |= flag;
 640         ir_nodehashmap_insert(infos, block, INT_TO_PTR(data));
 641 }
 642
 643 static void clear_block_flag(ir_nodehashmap_t *infos, const ir_node *block)
 644 {
 645         ir_nodehashmap_remove(infos, block);
 646 }
 647
 648 static bool has_operations(ir_nodehashmap_t *infos, const ir_node *block)
 649 {
 650         return get_block_flag(infos, block, BF_HAS_OPERATIONS);
 651 }
 652
 653 static void set_has_operations(ir_nodehashmap_t *infos, ir_node *block)
 654 {
 655         set_block_flag(infos, block, BF_HAS_OPERATIONS);
 656 }
 657
 658 static bool has_phis(ir_nodehashmap_t *infos, const ir_node *block)
 659 {
 660         return get_block_flag(infos, block, BF_HAS_PHIS);
 661 }
 662
 663 static void set_has_phis(ir_nodehashmap_t *infos, ir_node *block)
 664 {
 665         set_block_flag(infos, block, BF_HAS_PHIS);
 666 }
 667
 668 static bool is_unknown_jump_target(ir_nodehashmap_t *infos, const ir_node *block)
 669 {
 670         return get_block_flag(infos, block, BF_IS_UNKNOWN_JUMP_TARGET);
 671 }
 672
 673 static void set_is_unknown_jump_target(ir_nodehashmap_t *infos, ir_node *block)
 674 {
 675         set_block_flag(infos, block, BF_IS_UNKNOWN_JUMP_TARGET);
 676 }
 677
 678 /**
 679  * Pre-Walker: fill block info information.
 680  */
 681 static void compute_block_info(ir_node *n, void *x)
 682 {
 683         ir_nodehashmap_t *infos = (ir_nodehashmap_t*)x;
 684
 685         if (is_Block(n)) {
 686                 int i, max = get_Block_n_cfgpreds(n);
 687                 for (i=0; i<max; i++) {
 688                         ir_node *pred = get_Block_cfgpred(n,i);
 689                         if (is_unknown_jump(pred)) {
 690                                 set_is_unknown_jump_target(infos, n);
 691                         }
 692                 }
 693         } else if (is_Phi(n)) {
 694                 ir_node *block = get_nodes_block(n);
 695                 set_has_phis(infos, block);
 696         } else if (is_Jmp(n) || is_Cond(n) || is_Proj(n)) {
 697                 /* ignore */
 698         } else {
 699                 ir_node *block = get_nodes_block(n);
 700                 set_has_operations(infos, block);
 701         }
 702 }
 703
 704 static void clear_block_info(ir_node *block, void *x)
 705 {
 706         ir_nodehashmap_t *infos = (ir_nodehashmap_t*)x;
 707         clear_block_flag(infos, block);
 708 }
 709
 710 typedef struct skip_env {
 711         bool             changed;
 712         ir_nodehashmap_t block_infos;
 713 } skip_env;
 714
 715 /**
 716  * Post-Block-walker: Optimize useless if's (boolean Cond nodes
 717  * with same true/false target) away.
 718  */
 719 static void optimize_ifs(ir_node *block, void *x)
 720 {
 721         skip_env *env = (skip_env*)x;
 722         int i, j;
 723         int n_preds = get_Block_n_cfgpreds(block);
 724
 725         if (has_phis(&env->block_infos, block))
 726                 return;
 727
 728         /* optimize Cond predecessors (might produce Bad predecessors) */
 729         for (i = 0; i < n_preds; ++i) {
 730                 for (j = i+1; j < n_preds; ++j) {
 731                         optimize_pred_cond(block, i, j);
 732                 }
 733         }
 734 }
 735
 736 /**
 737  * Pre-Block walker: remove empty blocks (only contain a Jmp)
 738  * that are control flow predecessors of the current block.
 739  */
 740 static void remove_empty_blocks(ir_node *block, void *x)
 741 {
 742         skip_env *env = (skip_env*)x;
 743         int i;
 744         int n_preds = get_Block_n_cfgpreds(block);
 745
 746         for (i = 0; i < n_preds; ++i) {
 747                 ir_node *jmp, *jmp_block, *pred, *pred_block;
 748                 int n_jpreds = 0;
 749
 750                 jmp = get_Block_cfgpred(block, i);
 751                 if (!is_Jmp(jmp))
 752                         continue;
 753                 jmp_block = get_nodes_block(jmp);
 754                 if (jmp_block == block)
 755                         continue; /* this infinite loop cannot be optimized any further */
 756                 if (is_unknown_jump_target(&env->block_infos, jmp_block))
 757                         continue; /* unknown jump target must not be optimized */
 758                 if (has_operations(&env->block_infos,jmp_block))
 759                         continue; /* this block contains operations and cannot be skipped */
 760                 if (has_phis(&env->block_infos,jmp_block))
 761                         continue; /* this block contains Phis and is not skipped */
 762                 if (Block_block_visited(jmp_block)) {
 763                         continue;
 764                         /* otherwise we could break the walker,
 765                          * if block was reached via
 766                          *     KeepAlive edge -> jmp_block -> A ---> block,
 767                          * because the walker cannot handle Id nodes.
 768                          *
 769                          *   A      B
 770                          *    \    /
 771                          *   jmp_block
 772                          *    /    \
 773                          * block    End
 774                          */
 775                 }
 776
 777                 /* jmp_block is an empty block and can be optimized! */
 778
 779                 n_jpreds = get_Block_n_cfgpreds(jmp_block);
 780                 /**
 781                  * If the jmp block has only one predecessor this is straightforward.
 782                  * However, if there are more predecessors, we only handle this,
 783                  * if block has no Phis.
 784                  */
 785                 if (n_jpreds == 1) {
 786                         /* skip jmp block by rerouting its predecessor to block
 787                          *
 788                          *     A              A
 789                          *     |              |
 790                          *  jmp_block   =>    |
 791                          *     |              |
 792                          *   block          block
 793                          */
 794                         pred = get_Block_cfgpred(jmp_block, 0);
 795                         exchange(jmp, pred);
 796
 797                         /* cleanup: jmp_block might have a Keep edge! */
 798                         pred_block = get_nodes_block(pred);
 799                         exchange(jmp_block, pred_block);
 800                         env->changed = true;
 801                 } else if (! has_phis(&env->block_infos, block)) {
 802                         /* all predecessors can skip the jmp block, so block gets some new
 803                          * predecessors
 804                          *
 805                          *  A     B                 A  B
 806                          *   \   /                  |  |
 807                          * jmp_block  C  =>  Bad  C |  |
 808                          *      \    /          \ | | /
 809                          *      block            block
 810                          */
 811                         ir_node **ins = ALLOCAN(ir_node*, n_preds+n_jpreds);
 812                         int j;
 813                         /* first copy the old predecessors, because the outer loop (i)
 814                          * still walks over them */
 815                         for (j = 0; j < n_preds; ++j) {
 816                                 ins[j] = get_Block_cfgpred(block, j);
 817                         }
 818                         /* now append the new predecessors */
 819                         for (j = 0; j < n_jpreds; ++j) {
 820                                 pred = get_Block_cfgpred(jmp_block, j);
 821                                 ins[n_preds+j] = pred;
 822                         }
 823                         set_irn_in(block, n_preds+n_jpreds, ins);
 824                         /* convert the jmp_block to Bad */
 825                         ir_graph *irg = get_irn_irg(block);
 826                         exchange(jmp_block, new_r_Bad(irg, mode_BB));
 827                         exchange(jmp, new_r_Bad(irg, mode_X));
 828                         /* let the outer loop walk over the new predecessors as well */
 829                         n_preds += n_jpreds;
 830                         env->changed = true;
 831                         // TODO What if jmp_block had a KeepAlive edge?
 832                 } else {
 833                         /* This would involve Phis ... */
 834                 }
 835         }
 836 }
 837
 838 /*
 839  * All cfg optimizations, which do not touch Phi nodes.
 840  *
 841  * Note that this might create critical edges.
 842  */
 843 static void cfgopt_ignoring_phis(ir_graph *irg)
 844 {
 845         skip_env env;
 846
 847         env.changed = true;
 848         ir_nodehashmap_init(&env.block_infos);
 849
 850         while (env.changed) {
 851                 irg_walk_graph(irg, compute_block_info, NULL, &env.block_infos);
 852                 env.changed = false;
 853
 854                 /* Remove blocks, which only consist of a Jmp */
 855                 irg_block_walk_graph(irg, remove_empty_blocks, NULL, &env);
 856
 857                 /* Optimize Cond->Jmp, where then- and else-block are the same. */
 858                 irg_block_walk_graph(irg, NULL, optimize_ifs, &env);
 859
 860                 if (env.changed) {
 861                         clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
 862                         /* clear block info, because it must be recomputed */
 863                         irg_block_walk_graph(irg, clear_block_info, NULL, &env.block_infos);
 864                         /* Removing blocks and Conds might enable more optimizations */
 865                         continue;
 866                 } else {
 867                         break;
 868                 }
 869         }
 870
 871         ir_nodehashmap_destroy(&env.block_infos);
 872 }
 873
 874 /* Optimizations of the control flow that also require changes of Phi nodes.  */
 875 static ir_graph_state_t do_cfopt(ir_graph *irg)
 876 {
 877         int i, j, n;
 878         ir_node **in = NULL;
 879         ir_node *end = get_irg_end(irg);
 880         ir_node *new_end;
 881         merge_env env;
 882
 883         env.changed    = false;
 884         env.phis_moved = false;
 885
 886         assert(get_irg_phase_state(irg) != phase_building);
 887
 888         /* if the graph is not pinned, we cannot determine empty blocks */
 889         assert(get_irg_pinned(irg) != op_pin_state_floats &&
 890                "Control flow optimization need a pinned graph");
 891
 892         edges_deactivate(irg);
 893
 894         /* First the "simple" optimizations, which do not touch Phis */
 895         cfgopt_ignoring_phis(irg);
 896
 897         /* we use the mark flag to mark removable blocks */
 898         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK
 899                              | IR_RESOURCE_PHI_LIST);
 900
 901         /* The switch Cond optimization might expose unreachable code, so we loop */
 902         for (;;) {
 903                 int length;
 904                 ir_node **switch_conds = NULL;
 905                 bool changed = false;
 906
 907                 assure_doms(irg);
 908
 909                 /*
 910                  * This pass collects all Phi nodes in a link list in the block
 911                  * nodes.  Further it performs simple control flow optimizations.
 912                  * Finally it marks all blocks that do not contain useful
 913                  * computations, i.e., these blocks might be removed.
 914                  */
 915                 switch_conds = NEW_ARR_F(ir_node*, 0);
 916                 irg_walk(end, clear_link_and_mark_blocks_removable, collect_nodes, &switch_conds);
 917
 918                 /* handle all collected switch-Conds */
 919                 length = ARR_LEN(switch_conds);
 920                 for (i = 0; i < length; ++i) {
 921                         ir_node *cond = switch_conds[i];
 922                         changed |= handle_switch_cond(cond);
 923                 }
 924                 DEL_ARR_F(switch_conds);
 925
 926                 if (!changed)
 927                         break;
 928
 929                 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE
 930                                    | IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS
 931                                    | IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE);
 932         }
 933
 934         /* assert due to collect_nodes:
 935          * 1. removable blocks are now marked as such
 936          * 2. phi lists are up to date
 937          */
 938
 939         /* Optimize the standard code.
 940          * It walks only over block nodes and adapts these and the Phi nodes in these
 941          * blocks, which it finds in a linked list computed before.
 942          * */
 943         assure_doms(irg);
 944         irg_block_walk_graph(irg, optimize_blocks, NULL, &env);
 945
 946         new_end = optimize_in_place(end);
 947         if (new_end != end) {
 948                 set_irg_end(irg, new_end);
 949                 end = new_end;
 950         }
 951         remove_End_Bads_and_doublets(end);
 952
 953         ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK
 954                           | IR_RESOURCE_PHI_LIST);
 955
 956         if (env.phis_moved) {
 957                 /* Bad: when we moved Phi's, we might produce dead Phi nodes
 958                    that are kept-alive.
 959                    Some other phases cannot copy with this, so kill them.
 960                  */
 961                 n = get_End_n_keepalives(end);
 962                 if (n > 0) {
 963                         NEW_ARR_A(ir_node *, in, n);
 964                         assure_irg_outs(irg);
 965
 966                         for (i = j = 0; i < n; ++i) {
 967                                 ir_node *ka = get_End_keepalive(end, i);
 968
 969                                 if (is_Phi(ka)) {
 970                                         int k;
 971
 972                                         for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
 973                                                 ir_node *user = get_irn_out(ka, k);
 974
 975                                                 if (user != ka && user != end) {
 976                                                         /* Is it a real user or just a self loop ? */
 977                                                         break;
 978                                                 }
 979                                         }
 980                                         if (k >= 0)
 981                                                 in[j++] = ka;
 982                                 } else
 983                                         in[j++] = ka;
 984                         }
 985                         if (j != n) {
 986                                 set_End_keepalives(end, j, in);
 987                                 env.changed = true;
 988                         }
 989                 }
 990         }
 991
 992         return 0;
 993 }
 994
 995 static optdesc_t opt_cf = {
 996         "control-flow",
 997         IR_GRAPH_STATE_NO_UNREACHABLE_CODE,
 998         do_cfopt,
 999 };
1000
1001 void optimize_cf(ir_graph *irg)
1002 {
1003         perform_irg_optimization(irg, &opt_cf);
1004 }
1005
1006 /* Creates an ir_graph pass for optimize_cf. */
1007 ir_graph_pass_t *optimize_cf_pass(const char *name)
1008 {
1009         return def_graph_pass(name ? name : "optimize_cf", optimize_cf);
1010 }