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
  51 #include "array_t.h"
  52
  53 #include "irouts.h"
  54 #include "irbackedge_t.h"
  55
  56 #include "irflag_t.h"
  57 #include "firmstat.h"
  58 #include "irpass.h"
  59 #include "irphase_t.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 static void set_Block_removable(ir_node *block, bool removable)
  70 {
  71         set_Block_mark(block, removable);
  72 }
  73
  74 static bool is_Block_removable(ir_node *block)
  75 {
  76         return get_Block_mark(block);
  77 }
  78
  79 static bool is_switch_Cond(ir_node *cond) {
  80         ir_node *sel = get_Cond_selector(cond);
  81         return get_irn_mode(sel) != mode_b;
  82 }
  83
  84 static void clear_link(ir_node *node, void *ctx)
  85 {
  86         (void) ctx;
  87         set_irn_link(node, NULL);
  88         if (is_Block(node))
  89                 set_Block_removable(node, true);
  90 }
  91
  92 /**
  93  * Collects all Phi nodes in link list of Block.
  94  * Marks all blocks "non_removable" if they contain a node other
  95  * than Jmp (and Proj).
  96  * Links all Proj nodes to their predecessors.
  97  * Collects all switch-Conds in a list.
  98  */
  99 static void collect_nodes(ir_node *n, void *ctx)
 100 {
 101         ir_node ***switch_conds = (ir_node***)ctx;
 102
 103         if (is_Phi(n)) {
 104                 /* Collect Phi nodes to compact ins along with block's ins. */
 105                 ir_node *block = get_nodes_block(n);
 106                 set_irn_link(n, get_irn_link(block));
 107                 set_irn_link(block, n);
 108         } else if (is_Block(n)) {
 109                 if (has_Block_entity(n))
 110                         set_Block_removable(n, false);
 111                 return;
 112         } else if (!is_Jmp(n)) {  /* Check for non-empty block. */
 113                 ir_node *block = get_nodes_block(n);
 114                 set_Block_removable(block, false);
 115
 116                 if (is_Proj(n)) {
 117                         /* link Proj nodes */
 118                         ir_node *pred = get_Proj_pred(n);
 119                         set_irn_link(n, get_irn_link(pred));
 120                         set_irn_link(pred, n);
 121                 } else if (is_Cond(n) && is_switch_Cond(n)) {
 122                         /* found a switch-Cond, collect */
 123                         ARR_APP1(ir_node*, *switch_conds, n);
 124                 }
 125         }
 126 }
 127
 128 /** Returns true if pred is predecessor of block. */
 129 static bool is_pred_of(ir_node *pred, ir_node *b)
 130 {
 131         int i;
 132
 133         for (i = get_Block_n_cfgpreds(b) - 1; i >= 0; --i) {
 134                 ir_node *b_pred = get_Block_cfgpred_block(b, i);
 135                 if (b_pred == pred)
 136                         return true;
 137         }
 138         return false;
 139 }
 140
 141 /** Test whether we can optimize away pred block pos of b.
 142  *
 143  *  @param  b    A block node.
 144  *  @param  pos  The position of the predecessor block to judge about.
 145  *
 146  *  @returns     The number of predecessors
 147  *
 148  *  The test is rather tricky.
 149  *
 150  *  The situation is something like the following:
 151  *  @verbatim
 152  *                 if-block
 153  *                  /   \
 154  *              then-b  else-b
 155  *                  \   /
 156  *                    b
 157  *  @endverbatim
 158  *
 159  *  b merges the control flow of an if-then-else.  We may not remove
 160  *  the 'then' _and_ the 'else' block of an 'if' if there is a Phi
 161  *  node in b, even if both are empty.  The destruction of this Phi
 162  *  requires that a copy is added before the merge.  We have to
 163  *  keep one of the case blocks to place the copies in.
 164  *
 165  *  To perform the test for pos, we must regard predecessors before pos
 166  *  as already removed.
 167  **/
 168 static unsigned test_whether_dispensable(ir_node *b, int pos)
 169 {
 170         ir_node *pred  = get_Block_cfgpred(b, pos);
 171         ir_node *predb = get_nodes_block(pred);
 172
 173         if (is_Bad(pred) || !is_Block_removable(predb))
 174                 return 1;
 175
 176         /* can't remove self-loops */
 177         if (predb == b)
 178                 goto non_dispensable;
 179         if (is_unknown_jump(pred))
 180                 goto non_dispensable;
 181
 182         /* Seems to be empty. At least we detected this in collect_nodes. */
 183         if (get_irn_link(b) != NULL) {
 184                 int n_cfgpreds = get_Block_n_cfgpreds(b);
 185                 int i;
 186                 /* there are Phi nodes */
 187
 188                 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
 189                  * Handle all pred blocks with preds < pos as if they were already
 190                  * removed. */
 191                 for (i = 0; i < pos; i++) {
 192                         ir_node *other_pred  = get_Block_cfgpred(b, i);
 193                         ir_node *other_predb = get_nodes_block(other_pred);
 194                         if (is_Bad(other_pred))
 195                                 continue;
 196                         if (is_Block_removable(other_predb)
 197                             && !Block_block_visited(other_predb)) {
 198                                 int j;
 199                                 for (j = get_Block_n_cfgpreds(other_predb) - 1; j >= 0; --j) {
 200                                         ir_node *other_predpred
 201                                                 = get_Block_cfgpred_block(other_predb, j);
 202                                         if (is_pred_of(other_predpred, predb))
 203                                                 goto non_dispensable;
 204                                 }
 205                         } else if (is_pred_of(other_predb, predb)) {
 206                                 goto non_dispensable;
 207                         }
 208                 }
 209                 for (i = pos+1; i < n_cfgpreds; i++) {
 210                         ir_node *other_predb = get_Block_cfgpred_block(b, i);
 211                         if (is_pred_of(other_predb, predb))
 212                                 goto non_dispensable;
 213                 }
 214         }
 215         /* we will not dispense already visited blocks */
 216         if (Block_block_visited(predb))
 217                 return 1;
 218         /* if we get here, the block is dispensable, count useful preds */
 219         return get_irn_arity(predb);
 220
 221 non_dispensable:
 222         set_Block_removable(predb, false);
 223         return 1;
 224 }
 225
 226 /**
 227  * This method removes empty blocks.  A block is empty if it only contains Phi
 228  * and Jmp nodes.
 229  *
 230  * We first adapt Phi nodes, then Block nodes, as we need the old ins
 231  * of the Block to adapt the Phi nodes.  We do this by computing new
 232  * in arrays, and then replacing the old ones.  So far we compute new in arrays
 233  * for all nodes, not regarding whether there is a possibility for optimization.
 234  *
 235  * For each predecessor p of a Block b there are three cases:
 236  *  - The predecessor p is a Bad node: just skip it. The in array of b shrinks
 237  *    by one.
 238  *  - The predecessor p is empty. Remove p. All predecessors of p are now
 239  *    predecessors of b.
 240  *  - The predecessor p is a block containing useful code. Just keep p as is.
 241  *
 242  * For Phi nodes f we have to check the conditions at the Block of f.
 243  * For cases 1 and 3 we proceed as for Blocks.  For case 2 we can have two
 244  * cases:
 245  *  -2a: The old predecessor of the Phi f is a Phi pred_f IN THE BLOCK REMOVED.
 246  *       In this case we proceed as for blocks. We remove pred_f.  All
 247  *       predecessors of pred_f now are predecessors of f.
 248  *  -2b: The old predecessor of f is NOT in the block removed. It might be a Phi
 249  *       too. We have to replicate f for each predecessor of the removed block.
 250  *       Or, with other words, the removed predecessor block has exactly one
 251  *       predecessor.
 252  *
 253  * Further there is a special case for self referencing blocks:
 254  * @verbatim
 255  *
 256  *    then_b     else_b                              then_b  else_b
 257  *       \      /                                      \      /
 258  *        \    /                                        |    /
 259  *        pred_b                                        |   /
 260  *         |   ____                                     |  /  ____
 261  *         |  |    |                                    |  | |    |
 262  *         |  |    |       === optimized to ===>        \  | |    |
 263  *        loop_b   |                                     loop_b   |
 264  *         |  |    |                                      |  |    |
 265  *         |  |____|                                      |  |____|
 266  *         |                                              |
 267  * @endverbatim
 268  *
 269  * If there is a Phi in pred_b, but we remove pred_b, we have to generate a
 270  * Phi in loop_b, that has the ins of the Phi in pred_b and a self referencing
 271  * backedge.
 272  */
 273 static void optimize_blocks(ir_node *b, void *ctx)
 274 {
 275         int i, j, k, n, max_preds, n_preds, p_preds = -1;
 276         ir_node *pred, *phi, *next;
 277         ir_node **in;
 278         merge_env *env = (merge_env*)ctx;
 279
 280         /* Count the number of predecessor if this block is merged with pred blocks
 281            that are empty. */
 282         max_preds = 0;
 283         for (i = 0, k = get_Block_n_cfgpreds(b); i < k; ++i) {
 284                 max_preds += test_whether_dispensable(b, i);
 285         }
 286         in = XMALLOCN(ir_node*, max_preds);
 287
 288         /*- Fix the Phi nodes of the current block -*/
 289         for (phi = (ir_node*)get_irn_link(b); phi != NULL; phi = (ir_node*)next) {
 290                 assert(is_Phi(phi));
 291                 next = (ir_node*)get_irn_link(phi);
 292
 293                 /* Find the new predecessors for the Phi */
 294                 p_preds = 0;
 295                 for (i = 0, n = get_Block_n_cfgpreds(b); i < n; ++i) {
 296                         ir_graph *irg = get_irn_irg(b);
 297                         pred = get_Block_cfgpred_block(b, i);
 298
 299                         if (is_Bad(pred)) {
 300                                 /* case Phi 1: maintain Bads, as somebody else is responsible to remove them */
 301                                 in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
 302                         } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 303                                 /* case Phi 2: It's an empty block and not yet visited. */
 304                                 ir_node *phi_pred = get_Phi_pred(phi, i);
 305
 306                                 for (j = 0, k = get_Block_n_cfgpreds(pred); j < k; j++) {
 307                                         ir_node *pred_pred = get_Block_cfgpred(pred, j);
 308
 309                                         if (is_Bad(pred_pred)) {
 310                                                 in[p_preds++] = new_r_Bad(irg, get_irn_mode(phi));
 311                                                 continue;
 312                                         }
 313
 314                                         if (get_nodes_block(phi_pred) == pred) {
 315                                                 /* case Phi 2a: */
 316                                                 assert(is_Phi(phi_pred));  /* Block is empty!! */
 317
 318                                                 in[p_preds++] = get_Phi_pred(phi_pred, j);
 319                                         } else {
 320                                                 /* case Phi 2b: */
 321                                                 in[p_preds++] = phi_pred;
 322                                         }
 323                                 }
 324                         } else {
 325                                 /* case Phi 3: */
 326                                 in[p_preds++] = get_Phi_pred(phi, i);
 327                         }
 328                 }
 329                 assert(p_preds == max_preds);
 330
 331                 /* Fix the node */
 332                 if (p_preds == 1)
 333                         exchange(phi, in[0]);
 334                 else
 335                         set_irn_in(phi, p_preds, in);
 336                 env->changed = true;
 337         }
 338
 339         /*- This happens only if merge between loop backedge and single loop entry.
 340             Moreover, it is only needed if predb is the direct dominator of b,
 341             else there can be no uses of the Phi's in predb ... -*/
 342         for (k = 0, n = get_Block_n_cfgpreds(b); k < n; ++k) {
 343                 ir_node *pred  = get_Block_cfgpred(b, k);
 344                 ir_node *predb = get_nodes_block(pred);
 345                 if (is_Bad(pred))
 346                         continue;
 347
 348                 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
 349                         ir_node *next_phi;
 350
 351                         /* we found a predecessor block at position k that will be removed */
 352                         for (phi = (ir_node*)get_irn_link(predb); phi; phi = next_phi) {
 353                                 int q_preds = 0;
 354                                 next_phi = (ir_node*)get_irn_link(phi);
 355
 356                                 assert(is_Phi(phi));
 357
 358                                 if (get_Block_idom(b) != predb) {
 359                                         /* predb is not the dominator. There can't be uses of pred's Phi nodes, kill them .*/
 360                                         ir_graph *irg  = get_irn_irg(b);
 361                                         ir_mode  *mode = get_irn_mode(phi);
 362                                         exchange(phi, new_r_Bad(irg, mode));
 363                                 } else {
 364                                         /* predb is the direct dominator of b. There might be uses of the Phi nodes from
 365                                            predb in further block, so move this phi from the predecessor into the block b */
 366                                         set_nodes_block(phi, b);
 367                                         set_irn_link(phi, get_irn_link(b));
 368                                         set_irn_link(b, phi);
 369                                         env->phis_moved = true;
 370
 371                                         /* first, copy all 0..k-1 predecessors */
 372                                         for (i = 0; i < k; i++) {
 373                                                 pred = get_Block_cfgpred_block(b, i);
 374
 375                                                 if (is_Bad(pred)) {
 376                                                         in[q_preds++] = pred;
 377                                                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 378                                                         /* It's an empty block and not yet visited. */
 379                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 380                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 381                                                                         in[q_preds++] = phi;
 382                                                         }
 383                                                 } else {
 384                                                         in[q_preds++] = phi;
 385                                                 }
 386                                         }
 387
 388                                         /* now we are at k, copy the phi predecessors */
 389                                         pred = get_nodes_block(get_Block_cfgpred(b, k));
 390                                         for (i = 0; i < get_Phi_n_preds(phi); i++) {
 391                                                 in[q_preds++] = get_Phi_pred(phi, i);
 392                                         }
 393
 394                                         /* and now all the rest */
 395                                         for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
 396                                                 pred = get_Block_cfgpred_block(b, i);
 397
 398                                                 if (is_Bad(pred)) {
 399                                                         ir_graph *irg  = get_irn_irg(b);
 400                                                         ir_mode  *mode = get_irn_mode(phi);
 401                                                         in[q_preds++] = new_r_Bad(irg, mode);
 402                                                 } else if (is_Block_removable(pred) && !Block_block_visited(pred)) {
 403                                                         /* It's an empty block and not yet visited. */
 404                                                         for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
 405                                                                 if (! is_Bad(get_Block_cfgpred(pred, j)))
 406                                                                         in[q_preds++] = phi;
 407                                                         }
 408                                                 } else {
 409                                                         in[q_preds++] = phi;
 410                                                 }
 411                                         }
 412
 413                                         /* Fix the node */
 414                                         if (q_preds == 1)
 415                                                 exchange(phi, in[0]);
 416                                         else
 417                                                 set_irn_in(phi, q_preds, in);
 418                                         env->changed = true;
 419
 420                                         assert(q_preds <= max_preds);
 421                                         // assert(p_preds == q_preds && "Wrong Phi Fix");
 422                                 }
 423                         }
 424                 }
 425         }
 426
 427         /*- Fix the block -*/
 428         n_preds = 0;
 429         for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
 430                 ir_node *pred  = get_Block_cfgpred(b, i);
 431                 ir_node *predb = get_nodes_block(pred);
 432                 ir_graph *irg  = get_irn_irg(pred);
 433
 434                 /* case 1: Bad predecessor */
 435                 if (is_Bad(pred)) {
 436                         in[n_preds++] = new_r_Bad(irg, mode_X);
 437                         continue;
 438                 }
 439                 if (is_Block_removable(predb) && !Block_block_visited(predb)) {
 440                         /* case 2: It's an empty block and not yet visited. */
 441                         for (j = 0; j < get_Block_n_cfgpreds(predb); j++) {
 442                                 ir_node *predpred = get_Block_cfgpred(predb, j);
 443
 444                                 if (is_Bad(predpred)) {
 445                                         in[n_preds++] = new_r_Bad(irg, mode_X);
 446                                         continue;
 447                                 }
 448
 449                                 in[n_preds++] = predpred;
 450                         }
 451                         /* Remove block+jump as it might be kept alive. */
 452                         exchange(pred, new_r_Bad(get_irn_irg(b), mode_X));
 453                         exchange(predb, new_r_Bad(get_irn_irg(b), mode_BB));
 454                 } else {
 455                         /* case 3: */
 456                         in[n_preds++] = pred;
 457                 }
 458         }
 459         assert(n_preds == max_preds);
 460
 461         set_irn_in(b, n_preds, in);
 462         env->changed = true;
 463
 464         /* see if phi-fix was correct */
 465         assert(get_irn_link(b) == NULL || p_preds == -1 || (n_preds == p_preds));
 466         xfree(in);
 467 }
 468
 469 /**
 470  * Optimize table-switch Conds.
 471  *
 472  * @param cond the switch-Cond
 473  * @return true if the switch-Cond was optimized
 474  */
 475 static bool handle_switch_cond(ir_node *cond)
 476 {
 477         ir_node *sel   = get_Cond_selector(cond);
 478         ir_node *proj1 = (ir_node*)get_irn_link(cond);
 479         ir_node *proj2 = (ir_node*)get_irn_link(proj1);
 480         ir_node *blk   = get_nodes_block(cond);
 481
 482         /* exactly 1 Proj on the Cond node: must be the defaultProj */
 483         if (proj2 == NULL) {
 484                 ir_node *jmp = new_r_Jmp(blk);
 485                 assert(get_Cond_default_proj(cond) == get_Proj_proj(proj1));
 486                 /* convert it into a Jmp */
 487                 exchange(proj1, jmp);
 488                 return true;
 489         }
 490
 491         /* handle Cond nodes with constant argument. In this case the localopt rules
 492          * should have killed all obviously impossible cases.
 493          * So the only case left to handle here is 1 defaultProj + 1case
 494          * (this one case should be the one taken) */
 495         if (get_irn_link(proj2) == NULL) {
 496                 ir_tarval *tv = value_of(sel);
 497
 498                 if (tv != tarval_bad) {
 499                         /* we have a constant switch */
 500                         long      num     = get_tarval_long(tv);
 501                         long      def_num = get_Cond_default_proj(cond);
 502                         ir_graph *irg     = get_irn_irg(cond);
 503                         ir_node  *bad     = new_r_Bad(irg, mode_X);
 504
 505                         if (def_num == get_Proj_proj(proj1)) {
 506                                 /* first one is the defProj */
 507                                 if (num == get_Proj_proj(proj2)) {
 508                                         ir_node *jmp = new_r_Jmp(blk);
 509                                         exchange(proj2, jmp);
 510                                         exchange(proj1, bad);
 511                                         return true;
 512                                 }
 513                         } else if (def_num == get_Proj_proj(proj2)) {
 514                                 /* second one is the defProj */
 515                                 if (num == get_Proj_proj(proj1)) {
 516                                         ir_node *jmp = new_r_Jmp(blk);
 517                                         exchange(proj1, jmp);
 518                                         exchange(proj2, bad);
 519                                         return true;
 520                                 }
 521                         } else {
 522                                 /* neither: strange, Cond was not optimized so far */
 523                                 if (num == get_Proj_proj(proj1)) {
 524                                         ir_node *jmp = new_r_Jmp(blk);
 525                                         exchange(proj1, jmp);
 526                                         exchange(proj2, bad);
 527                                         return true;
 528                                 } else if (num == get_Proj_proj(proj2)) {
 529                                         ir_node *jmp = new_r_Jmp(blk);
 530                                         exchange(proj2, jmp);
 531                                         exchange(proj1, bad);
 532                                         return true;
 533                                 }
 534                         }
 535                 }
 536         }
 537         return false;
 538 }
 539
 540 static bool get_phase_flag(ir_phase *block_info, ir_node *block, int offset) {
 541         return ((int)phase_get_irn_data(block_info, block)) & (1<<offset);
 542 }
 543 static void set_phase_flag(ir_phase *block_info, ir_node *block, int offset) {
 544         int data = (int)phase_get_irn_data(block_info, block);
 545         data |= (1<<offset);
 546         phase_set_irn_data(block_info, block, (void*)data);
 547 }
 548
 549 static bool has_operations(ir_phase *block_info, ir_node *block) {
 550         return get_phase_flag(block_info, block, 1);
 551 }
 552 static void set_has_operations(ir_phase *block_info, ir_node *block) {
 553         set_phase_flag(block_info, block, 1);
 554 }
 555
 556 static bool has_phis(ir_phase *block_info, ir_node *block) {
 557         return get_phase_flag(block_info, block, 2);
 558 }
 559 static void set_has_phis(ir_phase *block_info, ir_node *block) {
 560         set_phase_flag(block_info, block, 2);
 561 }
 562
 563 static bool is_unknown_jump_target(ir_phase *block_info, ir_node *block) {
 564         return get_phase_flag(block_info, block, 3);
 565 }
 566 static void set_is_unknown_jump_target(ir_phase *block_info, ir_node *block) {
 567         set_phase_flag(block_info, block, 3);
 568 }
 569
 570 /**
 571  * Optimize Conds, where true and false jump to the same block into a Jmp
 572  *
 573  *        Cond
 574  *       /    \
 575  *  projA      projB   =>   Jmp     Bad
 576  *       \    /                \   /
 577  *       block                 block
 578  */
 579 static bool optimize_pred_cond(ir_node *block, int i, int j)
 580 {
 581         ir_node *projA, *projB, *cond, *pred_block, *jmp, *bad;
 582         assert(i != j);
 583
 584         projA = get_Block_cfgpred(block, i);
 585         if (!is_Proj(projA)) return false;
 586         projB = get_Block_cfgpred(block, j);
 587         if (!is_Proj(projB)) return false;
 588         cond  = get_Proj_pred(projA);
 589         if (!is_Cond(cond))  return false;
 590
 591         if (cond != get_Proj_pred(projB)) return false;
 592         if (is_switch_Cond(cond)) return false;
 593
 594         /* cond should actually be a Jmp */
 595         pred_block = get_nodes_block(cond);
 596         jmp = new_r_Jmp(pred_block);
 597         bad = new_r_Bad(get_irn_irg(block), mode_X);
 598
 599         assert(projA != projB);
 600         exchange(projA, jmp);
 601         exchange(projB, bad);
 602         return true;
 603 }
 604
 605 static void compute_block_info(ir_node *n, void *x)
 606 {
 607         ir_phase *block_info = (ir_phase *)x;
 608
 609         if (is_Block(n)) {
 610                 int i, max = get_Block_n_cfgpreds(n);
 611                 for (i=0; i<max; i++) {
 612                         ir_node *pred = get_Block_cfgpred(n,i);
 613                         if (is_unknown_jump(pred)) {
 614                                 set_is_unknown_jump_target(block_info, n);
 615                         }
 616                 }
 617         } else if (is_Phi(n)) {
 618                 ir_node *block = get_nodes_block(n);
 619                 set_has_phis(block_info, block);
 620         } else if (is_Jmp(n) || is_Cond(n) || is_Cmp(n) || is_Proj(n)) {
 621                 /* ignore */
 622         } else {
 623                 ir_node *block = get_nodes_block(n);
 624                 set_has_operations(block_info, block);
 625         }
 626 }
 627
 628 typedef struct skip_env {
 629         bool changed;
 630         ir_phase *phase;
 631 } skip_env;
 632
 633 static void optimize_conds(ir_node *b, void *x)
 634 {
 635         skip_env *env = (skip_env*)x;
 636         int i, j;
 637         int n_preds = get_Block_n_cfgpreds(b);
 638
 639         if (has_phis(env->phase,b)) return;
 640
 641         /* optimize Cond predecessors (might produce Bad predecessors) */
 642         for (i = 0; i < n_preds; i++) {
 643                 for (j = i+1; j < n_preds; j++) {
 644                         optimize_pred_cond(b, i, j);
 645                 }
 646         }
 647 }
 648
 649 static void remove_empty_blocks(ir_node *b, void *x)
 650 {
 651         skip_env *env = (skip_env*)x;
 652         int i;
 653         int n_preds = get_Block_n_cfgpreds(b);
 654
 655         for (i = 0; i < n_preds; ++i) {
 656                 ir_node *jmp, *jmp_block, *pred, *pred_block;
 657
 658                 jmp = get_Block_cfgpred(b, i);
 659                 if (!is_Jmp(jmp)) continue;
 660                 if (is_unknown_jump(jmp)) continue;
 661                 jmp_block = get_nodes_block(jmp);
 662                 if (is_unknown_jump_target(env->phase, jmp_block)) continue;
 663                 if (has_operations(env->phase,jmp_block)) continue;
 664                 /* jmp_block is an empty block! */
 665
 666                 if (get_Block_n_cfgpreds(jmp_block) != 1) continue;
 667                 pred = get_Block_cfgpred(jmp_block, 0);
 668                 exchange(jmp, pred);
 669                 env->changed = true;
 670
 671                 /* cleanup: jmp_block might have a Keep edge! */
 672                 pred_block = get_nodes_block(pred);
 673                 exchange(jmp_block, pred_block);
 674         }
 675 }
 676
 677 /*
 678  * Some cfg optimizations, which do not touch Phi nodes */
 679 static void cfgopt_ignoring_phis(ir_graph *irg) {
 680         ir_phase *block_info = new_phase(irg, NULL);
 681         skip_env env = { false, block_info };
 682
 683         irg_walk_graph(irg, compute_block_info, NULL, block_info);
 684
 685         for(;;) {
 686                 env.changed = false;
 687
 688                 /* Conds => Jmp optimization; might produce empty blocks */
 689                 irg_block_walk_graph(irg, optimize_conds, NULL, &env);
 690
 691                 /* Remove empty blocks */
 692                 irg_block_walk_graph(irg, remove_empty_blocks, NULL, &env);
 693                 if (env.changed) {
 694                         set_irg_doms_inconsistent(irg);
 695                         /* Removing blocks might enable more Cond optimizations */
 696                         continue;
 697                 } else {
 698                         break;
 699                 }
 700         }
 701
 702         phase_free(block_info);
 703 }
 704
 705 /* Optimizations of the control flow that also require changes of Phi nodes.  */
 706 void optimize_cf(ir_graph *irg)
 707 {
 708         int i, j, n;
 709         ir_node **in = NULL;
 710         ir_node *end = get_irg_end(irg);
 711         ir_node *new_end;
 712         merge_env env;
 713
 714         assert(get_irg_phase_state(irg) != phase_building);
 715
 716         /* if the graph is not pinned, we cannot determine empty blocks */
 717         assert(get_irg_pinned(irg) != op_pin_state_floats &&
 718                "Control flow optimization need a pinned graph");
 719
 720         /* FIXME: control flow opt destroys block edges. So edges are deactivated
 721          * here. Fix the edges! */
 722         edges_deactivate(irg);
 723
 724         cfgopt_ignoring_phis(irg);
 725
 726         /* we use the mark flag to mark removable blocks */
 727         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
 728
 729         /* The switch Cond optimization might expose unreachable code, so we loop */
 730         for (;;) {
 731                 int length;
 732                 ir_node **switch_conds = NULL;
 733                 env.changed    = false;
 734                 env.phis_moved = false;
 735
 736                 assure_doms(irg);
 737
 738                 /*
 739                  * This pass collects all Phi nodes in a link list in the block
 740                  * nodes.  Further it performs simple control flow optimizations.
 741                  * Finally it marks all blocks that do not contain useful
 742                  * computations, i.e., these blocks might be removed.
 743                  */
 744                 switch_conds = NEW_ARR_F(ir_node*, 0);
 745                 irg_walk(end, clear_link, collect_nodes, &switch_conds);
 746
 747                 /* handle all collected switch-Conds */
 748                 length = ARR_LEN(switch_conds);
 749                 for (i = 0; i < length; ++i) {
 750                         ir_node *cond = switch_conds[i];
 751                         env.changed |= handle_switch_cond(cond);
 752                 }
 753                 DEL_ARR_F(switch_conds);
 754
 755                 if (!env.changed) break;
 756
 757                 set_irg_doms_inconsistent(irg);
 758                 set_irg_extblk_inconsistent(irg);
 759                 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
 760         }
 761
 762         /* assert due to collect_nodes:
 763          * 1. removable blocks are now marked as such
 764          * 2. phi lists are up to date
 765          */
 766
 767         /* Optimize the standard code.
 768          * It walks only over block nodes and adapts these and the Phi nodes in these
 769          * blocks, which it finds in a linked list computed before.
 770          * */
 771         assure_doms(irg);
 772         irg_block_walk_graph(irg, optimize_blocks, NULL, &env);
 773
 774         new_end = optimize_in_place(end);
 775         if (new_end != end) {
 776                 set_irg_end(irg, new_end);
 777                 end = new_end;
 778         }
 779         remove_End_Bads_and_doublets(end);
 780
 781         ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK);
 782
 783         if (env.phis_moved) {
 784                 /* Bad: when we moved Phi's, we might produce dead Phi nodes
 785                    that are kept-alive.
 786                    Some other phases cannot copy with this, so will them.
 787                  */
 788                 n = get_End_n_keepalives(end);
 789                 if (n > 0) {
 790                         NEW_ARR_A(ir_node *, in, n);
 791                         assure_irg_outs(irg);
 792
 793                         for (i = j = 0; i < n; ++i) {
 794                                 ir_node *ka = get_End_keepalive(end, i);
 795
 796                                 if (is_Phi(ka)) {
 797                                         int k;
 798
 799                                         for (k = get_irn_n_outs(ka) - 1; k >= 0; --k) {
 800                                                 ir_node *user = get_irn_out(ka, k);
 801
 802                                                 if (user != ka && user != end) {
 803                                                         /* Is it a real user or just a self loop ? */
 804                                                         break;
 805                                                 }
 806                                         }
 807                                         if (k >= 0)
 808                                                 in[j++] = ka;
 809                                 } else
 810                                         in[j++] = ka;
 811                         }
 812                         if (j != n) {
 813                                 set_End_keepalives(end, j, in);
 814                                 env.changed = true;
 815                         }
 816                 }
 817         }
 818
 819         if (env.changed) {
 820                 /* Handle graph state if was changed. */
 821                 set_irg_doms_inconsistent(irg);
 822                 set_irg_extblk_inconsistent(irg);
 823                 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
 824         }
 825 }
 826
 827 /* Creates an ir_graph pass for optimize_cf. */
 828 ir_graph_pass_t *optimize_cf_pass(const char *name)
 829 {
 830         return def_graph_pass(name ? name : "optimize_cf", optimize_cf);
 831 }