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