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