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