gcc/tree-ssa-dce.c

   1 /* Dead code elimination pass for the GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
   3    Free Software Foundation, Inc.
   4    Contributed by Ben Elliston <bje@redhat.com>
   5    and Andrew MacLeod <amacleod@redhat.com>
   6    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify it
  11 under the terms of the GNU General Public License as published by the
  12 Free Software Foundation; either version 3, or (at your option) any
  13 later version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT
  16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING3.  If not see
  22 <http://www.gnu.org/licenses/>.  */
  23
  24 /* Dead code elimination.
  25
  26    References:
  27
  28      Building an Optimizing Compiler,
  29      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
  30
  31      Advanced Compiler Design and Implementation,
  32      Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
  33
  34    Dead-code elimination is the removal of statements which have no
  35    impact on the program's output.  "Dead statements" have no impact
  36    on the program's output, while "necessary statements" may have
  37    impact on the output.
  38
  39    The algorithm consists of three phases:
  40    1. Marking as necessary all statements known to be necessary,
  41       e.g. most function calls, writing a value to memory, etc;
  42    2. Propagating necessary statements, e.g., the statements
  43       giving values to operands in necessary statements; and
  44    3. Removing dead statements.  */
  45
  46 #include "config.h"
  47 #include "system.h"
  48 #include "coretypes.h"
  49 #include "tm.h"
  50 #include "ggc.h"
  51 #include "diagnostic.h"
  52 #include "toplev.h"
  53 /* These RTL headers are needed for basic-block.h.  */
  54 #include "rtl.h"
  55 #include "tm_p.h"
  56 #include "hard-reg-set.h"
  57 #include "obstack.h"
  58 #include "basic-block.h"
  59
  60 #include "tree.h"
  61 #include "diagnostic.h"
  62 #include "tree-flow.h"
  63 #include "tree-gimple.h"
  64 #include "tree-dump.h"
  65 #include "tree-pass.h"
  66 #include "timevar.h"
  67 #include "flags.h"
  68 #include "cfgloop.h"
  69 #include "tree-scalar-evolution.h"
  70 \f
  71 static struct stmt_stats
  72 {
  73   int total;
  74   int total_phis;
  75   int removed;
  76   int removed_phis;
  77 } stats;
  78
  79
  80 static VEC (tree, heap) *worklist;
  81 static VEC (tree, heap) *cond_dead_built_in_calls;
  82
  83 /* Vector indicating an SSA name has already been processed and marked
  84    as necessary.  */
  85 static sbitmap processed;
  86
  87 /* Vector indicating that last_stmt if a basic block has already been
  88    marked as necessary.  */
  89 static sbitmap last_stmt_necessary;
  90
  91 /* Before we can determine whether a control branch is dead, we need to
  92    compute which blocks are control dependent on which edges.
  93
  94    We expect each block to be control dependent on very few edges so we
  95    use a bitmap for each block recording its edges.  An array holds the
  96    bitmap.  The Ith bit in the bitmap is set if that block is dependent
  97    on the Ith edge.  */
  98 static bitmap *control_dependence_map;
  99
 100 /* Vector indicating that a basic block has already had all the edges
 101    processed that it is control dependent on.  */
 102 static sbitmap visited_control_parents;
 103
 104 /* TRUE if this pass alters the CFG (by removing control statements).
 105    FALSE otherwise.
 106
 107    If this pass alters the CFG, then it will arrange for the dominators
 108    to be recomputed.  */
 109 static bool cfg_altered;
 110
 111 /* Execute code that follows the macro for each edge (given number
 112    EDGE_NUMBER within the CODE) for which the block with index N is
 113    control dependent.  */
 114 #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER)        \
 115   EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0,     \
 116                             (EDGE_NUMBER), (BI))
 117
 118
 119 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
 120 static inline void
 121 set_control_dependence_map_bit (basic_block bb, int edge_index)
 122 {
 123   if (bb == ENTRY_BLOCK_PTR)
 124     return;
 125   gcc_assert (bb != EXIT_BLOCK_PTR);
 126   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
 127 }
 128
 129 /* Clear all control dependences for block BB.  */
 130 static inline void
 131 clear_control_dependence_bitmap (basic_block bb)
 132 {
 133   bitmap_clear (control_dependence_map[bb->index]);
 134 }
 135
 136
 137 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
 138    This function is necessary because some blocks have negative numbers.  */
 139
 140 static inline basic_block
 141 find_pdom (basic_block block)
 142 {
 143   gcc_assert (block != ENTRY_BLOCK_PTR);
 144
 145   if (block == EXIT_BLOCK_PTR)
 146     return EXIT_BLOCK_PTR;
 147   else
 148     {
 149       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
 150       if (! bb)
 151         return EXIT_BLOCK_PTR;
 152       return bb;
 153     }
 154 }
 155
 156
 157 /* Determine all blocks' control dependences on the given edge with edge_list
 158    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
 159
 160 static void
 161 find_control_dependence (struct edge_list *el, int edge_index)
 162 {
 163   basic_block current_block;
 164   basic_block ending_block;
 165
 166   gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
 167
 168   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
 169     ending_block = single_succ (ENTRY_BLOCK_PTR);
 170   else
 171     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
 172
 173   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
 174        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
 175        current_block = find_pdom (current_block))
 176     {
 177       edge e = INDEX_EDGE (el, edge_index);
 178
 179       /* For abnormal edges, we don't make current_block control
 180          dependent because instructions that throw are always necessary
 181          anyway.  */
 182       if (e->flags & EDGE_ABNORMAL)
 183         continue;
 184
 185       set_control_dependence_map_bit (current_block, edge_index);
 186     }
 187 }
 188
 189
 190 /* Record all blocks' control dependences on all edges in the edge
 191    list EL, ala Morgan, Section 3.6.  */
 192
 193 static void
 194 find_all_control_dependences (struct edge_list *el)
 195 {
 196   int i;
 197
 198   for (i = 0; i < NUM_EDGES (el); ++i)
 199     find_control_dependence (el, i);
 200 }
 201
 202
 203 #define NECESSARY(stmt)         stmt->base.asm_written_flag
 204
 205 /*  Conditional dead call elimination
 206
 207    Some builtin functions can set errno on error conditions, but they
 208    are otherwise pure. If the result of a call to such a function is
 209    not used, the compiler can still not eliminate the call without
 210    powerful interprocedural analysis to prove that the errno is not
 211    checked. However, if the conditions under which the error occurs
 212    are known, compiler can conditionally dead code eliminate the calls
 213    by shrink-wrapping the semi-dead calls into the error condition:
 214
 215         built_in_call(args)
 216           ==>
 217         if (error_cond(args))
 218              built_in_call(args)
 219
 220     An actual simple exampl is :
 221          log (x);   // Mostly dead call
 222      ==>
 223          if (x < 0)
 224              log(x);
 225      With this change, call to log(x) is effectively eliminated, as
 226      in majority of the cases, log won't be called with x out of
 227      range. The branch is totally predicatible, so the branch cost
 228      is low.  Such optimization improves the performance of
 229      an important application in a big search company.
 230
 231    Note that library functions are not supposed to clear errno to zero without
 232    error.
 233
 234    In this implementation, only 'pow' and 'log' are handled. ('sin' and 'cos'
 235    seem to be wrongly handled by gcc -- they are treated as not touching errno
 236    which is not correct.)
 237
 238    The condition wrapping the builtin call is conservatively set to avoid too
 239    aggressive (wrong) shrink wrapping. The optimization is called conditional
 240    dead call elimination because the call is eliminated under the condition
 241    that the input arguments would not lead to domain or range error (for
 242    instance when x <= 0 for a log(x) call), however the chances that the error
 243    condition is hit is very low (those builtin calls which are conditionally
 244    dead are usually part of the C++ abstraction penalty exposed after
 245    inlining).  */
 246
 247
 248 /* A helper method to help select calls to pow that are suitable for
 249    conditional DCE transformation. Returns true if the pow call is
 250    a candidate.*/
 251
 252 static bool
 253 check_pow (tree pow_call)
 254 {
 255   tree base, expn;
 256   enum tree_code bc, ec;
 257
 258   gcc_assert (TREE_CODE (pow_call) == CALL_EXPR);
 259   if (call_expr_nargs (pow_call) != 2)
 260     return false;
 261
 262   base = CALL_EXPR_ARG (pow_call, 0);
 263   expn = CALL_EXPR_ARG (pow_call, 1);
 264
 265   bc = TREE_CODE (base);
 266   ec = TREE_CODE (expn);
 267
 268   gcc_assert (TREE_CODE_CLASS (bc) != tcc_constant
 269              || bc == REAL_CST);
 270   gcc_assert (TREE_CODE_CLASS (ec) != tcc_constant
 271              || ec == REAL_CST);
 272
 273   /* Folding candidates are not interesting.  */
 274   if (ec == REAL_CST && bc == REAL_CST)
 275     return false;
 276
 277   if (bc == REAL_CST)
 278    {
 279      /* Only handle a fixed range of constant.  */
 280      REAL_VALUE_TYPE mv;
 281      REAL_VALUE_TYPE bcv = TREE_REAL_CST (base);
 282      if (REAL_VALUES_EQUAL (bcv, dconst1))
 283        return false;
 284      if (REAL_VALUES_LESS (bcv, dconst1))
 285        return false;
 286      real_from_integer (&mv, VOIDmode,256,0,1);
 287      if (REAL_VALUES_LESS (mv, bcv))
 288        return false;
 289      return true;
 290    }
 291   else if (bc == SSA_NAME)
 292    {
 293      tree def, nm, rhs, rhs0, var, typ;
 294      int sz;
 295
 296      def = SSA_NAME_DEF_STMT (base);
 297      if (TREE_CODE (def) != GIMPLE_MODIFY_STMT)
 298        return false;
 299
 300      nm = GIMPLE_STMT_OPERAND (def,0);
 301      gcc_assert (TREE_CODE (nm) == SSA_NAME);
 302      if (nm != base)
 303        return false;
 304
 305      rhs = GIMPLE_STMT_OPERAND (def,1);
 306
 307      if (TREE_CODE (rhs) != FLOAT_EXPR)
 308        return false;
 309      rhs0 = TREE_OPERAND (rhs,0);
 310
 311      if (TREE_CODE (rhs0) != SSA_NAME)
 312        return false;
 313
 314      var = SSA_NAME_VAR (rhs0);
 315      if (TREE_CODE (var) != VAR_DECL &&
 316          TREE_CODE (var) != PARM_DECL)
 317        return false;
 318
 319      typ = TREE_TYPE (var);
 320      if (TREE_CODE (typ) != INTEGER_TYPE)
 321        return false;
 322      sz = int_size_in_bytes (typ);
 323      if (sz == -1 || sz > INT_TYPE_SIZE)
 324        return false;
 325
 326      return true;
 327    }
 328   else
 329     return false;
 330 }
 331
 332 /* A helper function to help select candidate calls to log that are
 333    suitable for conditional DCE. Returns true if the log call is a
 334     candidate. */
 335
 336 static bool
 337 check_log (tree log_call)
 338 {
 339   tree arg_typ;
 340   gcc_assert (TREE_CODE (log_call) == CALL_EXPR);
 341   if (call_expr_nargs (log_call) != 1)
 342     return false;
 343
 344   arg_typ = TREE_TYPE (CALL_EXPR_ARG (log_call, 0));
 345   if (!is_gimple_reg_type (arg_typ))
 346     return false;
 347   return true;
 348 }
 349
 350
 351 /* A helper function to determine if a builtin function call is a
 352    candidate for conditional DCE. Returns true if the builtin call
 353    is a candidate. */
 354
 355 static bool
 356 is_unnecessary_except_errno_call (tree call)
 357 {
 358   tree fn;
 359   bool is_unnecessary_except_errno = false;
 360   enum built_in_function fnc;
 361
 362   if (!flag_tree_builtin_dce)
 363     return false;
 364
 365   gcc_assert (call && TREE_CODE (call) == CALL_EXPR);
 366
 367   fn = get_callee_fndecl (call);
 368   if (!fn || !DECL_BUILT_IN (fn))
 369     return false;
 370
 371   fnc = DECL_FUNCTION_CODE (fn);
 372   switch (fnc)
 373     {
 374     CASE_FLT_FN (BUILT_IN_POW):
 375       if (check_pow (call))
 376         is_unnecessary_except_errno = true;
 377       break;
 378
 379     CASE_FLT_FN (BUILT_IN_LOG):
 380       if (check_log (call))
 381         is_unnecessary_except_errno = true;
 382       break;
 383     default :
 384       is_unnecessary_except_errno = false;
 385       break;
 386    }
 387
 388   return is_unnecessary_except_errno;
 389 }
 390
 391
 392 /* If STMT is not already marked necessary, mark it, and add it to the
 393    worklist if ADD_TO_WORKLIST is true.  */
 394 static inline void
 395 mark_stmt_necessary (tree stmt, bool add_to_worklist)
 396 {
 397   gcc_assert (stmt);
 398   gcc_assert (!DECL_P (stmt));
 399
 400   if (NECESSARY (stmt))
 401     return;
 402
 403   if (dump_file && (dump_flags & TDF_DETAILS))
 404     {
 405       fprintf (dump_file, "Marking useful stmt: ");
 406       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 407       fprintf (dump_file, "\n");
 408     }
 409
 410   NECESSARY (stmt) = 1;
 411   if (add_to_worklist)
 412     VEC_safe_push (tree, heap, worklist, stmt);
 413 }
 414
 415
 416 /* Mark the statement defining operand OP as necessary.  */
 417
 418 static inline void
 419 mark_operand_necessary (tree op)
 420 {
 421   tree stmt;
 422   int ver;
 423
 424   gcc_assert (op);
 425
 426   ver = SSA_NAME_VERSION (op);
 427   if (TEST_BIT (processed, ver))
 428     return;
 429   SET_BIT (processed, ver);
 430
 431   stmt = SSA_NAME_DEF_STMT (op);
 432   gcc_assert (stmt);
 433
 434   if (NECESSARY (stmt) || IS_EMPTY_STMT (stmt))
 435     return;
 436
 437   if (dump_file && (dump_flags & TDF_DETAILS))
 438    {
 439      fprintf (dump_file, " Marked as necessary: ");
 440      print_generic_stmt (dump_file, stmt, TDF_SLIM);
 441      fprintf (dump_file, "\n");
 442    }
 443
 444   NECESSARY (stmt) = 1;
 445   VEC_safe_push (tree, heap, worklist, stmt);
 446 }
 447
 448
 449 /* Mark STMT as necessary if it obviously is.  Add it to the worklist if
 450    it can make other statements necessary.
 451
 452    If AGGRESSIVE is false, control statements are conservatively marked as
 453    necessary.  */
 454
 455 static void
 456 mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
 457 {
 458   stmt_ann_t ann;
 459   tree op;
 460
 461   /* With non-call exceptions, we have to assume that all statements could
 462      throw.  If a statement may throw, it is inherently necessary.  */
 463   if (flag_non_call_exceptions
 464       && tree_could_throw_p (stmt))
 465     {
 466       mark_stmt_necessary (stmt, true);
 467       return;
 468     }
 469
 470   /* Statements that are implicitly live.  Most function calls, asm and return
 471      statements are required.  Labels and BIND_EXPR nodes are kept because
 472      they are control flow, and we have no way of knowing whether they can be
 473      removed.  DCE can eliminate all the other statements in a block, and CFG
 474      can then remove the block and labels.  */
 475   switch (TREE_CODE (stmt))
 476     {
 477     case PREDICT_EXPR:
 478     case LABEL_EXPR:
 479     case CASE_LABEL_EXPR:
 480       mark_stmt_necessary (stmt, false);
 481       return;
 482
 483     case ASM_EXPR:
 484     case RESX_EXPR:
 485     case RETURN_EXPR:
 486     case CHANGE_DYNAMIC_TYPE_EXPR:
 487       mark_stmt_necessary (stmt, true);
 488       return;
 489
 490     case CALL_EXPR:
 491       /* Most, but not all function calls are required.  Function calls that
 492          produce no result and have no side effects (i.e. const pure
 493          functions) are unnecessary.  */
 494       if (TREE_SIDE_EFFECTS (stmt))
 495         mark_stmt_necessary (stmt, true);
 496
 497       return;
 498
 499     case GIMPLE_MODIFY_STMT:
 500       op = get_call_expr_in (stmt);
 501       if (op && TREE_SIDE_EFFECTS (op))
 502         {
 503           mark_stmt_necessary (stmt, true);
 504           return;
 505         }
 506
 507       /* These values are mildly magic bits of the EH runtime.  We can't
 508          see the entire lifetime of these values until landing pads are
 509          generated.  */
 510       if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == EXC_PTR_EXPR
 511           || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == FILTER_EXPR)
 512         {
 513           mark_stmt_necessary (stmt, true);
 514           return;
 515         }
 516       break;
 517
 518     case GOTO_EXPR:
 519       gcc_assert (!simple_goto_p (stmt));
 520       mark_stmt_necessary (stmt, true);
 521       return;
 522
 523     case COND_EXPR:
 524       gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2);
 525       /* Fall through.  */
 526
 527     case SWITCH_EXPR:
 528       if (! aggressive)
 529         mark_stmt_necessary (stmt, true);
 530       break;
 531
 532     default:
 533       break;
 534     }
 535
 536   ann = stmt_ann (stmt);
 537
 538   /* If the statement has volatile operands, it needs to be preserved.
 539      Same for statements that can alter control flow in unpredictable
 540      ways.  */
 541   if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt))
 542     {
 543       mark_stmt_necessary (stmt, true);
 544       return;
 545     }
 546
 547   if (is_hidden_global_store (stmt))
 548     {
 549       mark_stmt_necessary (stmt, true);
 550       return;
 551     }
 552
 553   return;
 554 }
 555
 556
 557 /* Make corresponding control dependent edges necessary.  We only
 558    have to do this once for each basic block, so we clear the bitmap
 559    after we're done.  */
 560 static void
 561 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 562 {
 563   bitmap_iterator bi;
 564   unsigned edge_number;
 565
 566   gcc_assert (bb != EXIT_BLOCK_PTR);
 567
 568   if (bb == ENTRY_BLOCK_PTR)
 569     return;
 570
 571   EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
 572     {
 573       tree t;
 574       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 575
 576       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 577         continue;
 578       SET_BIT (last_stmt_necessary, cd_bb->index);
 579
 580       t = last_stmt (cd_bb);
 581       if (t && is_ctrl_stmt (t))
 582         mark_stmt_necessary (t, true);
 583     }
 584 }
 585
 586
 587 /* Find obviously necessary statements.  These are things like most function
 588    calls, and stores to file level variables.
 589
 590    If EL is NULL, control statements are conservatively marked as
 591    necessary.  Otherwise it contains the list of edges used by control
 592    dependence analysis.  */
 593
 594 static void
 595 find_obviously_necessary_stmts (struct edge_list *el)
 596 {
 597   basic_block bb;
 598   block_stmt_iterator i;
 599   edge e;
 600
 601   FOR_EACH_BB (bb)
 602     {
 603       tree phi;
 604
 605       /* PHI nodes are never inherently necessary.  */
 606       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 607         NECESSARY (phi) = 0;
 608
 609       /* Check all statements in the block.  */
 610       for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
 611         {
 612           tree stmt = bsi_stmt (i);
 613           NECESSARY (stmt) = 0;
 614           mark_stmt_if_obviously_necessary (stmt, el != NULL);
 615         }
 616     }
 617
 618   if (el)
 619     {
 620       /* Prevent the loops from being removed.  We must keep the infinite loops,
 621          and we currently do not have a means to recognize the finite ones.  */
 622       FOR_EACH_BB (bb)
 623         {
 624           edge_iterator ei;
 625           FOR_EACH_EDGE (e, ei, bb->succs)
 626             if (e->flags & EDGE_DFS_BACK)
 627               mark_control_dependent_edges_necessary (e->dest, el);
 628         }
 629     }
 630 }
 631
 632
 633 /* Propagate necessity using the operands of necessary statements.
 634    Process the uses on each statement in the worklist, and add all
 635    feeding statements which contribute to the calculation of this
 636    value to the worklist.
 637
 638    In conservative mode, EL is NULL.  */
 639
 640 static void
 641 propagate_necessity (struct edge_list *el)
 642 {
 643   tree stmt;
 644   bool aggressive = (el ? true : false);
 645
 646   if (dump_file && (dump_flags & TDF_DETAILS))
 647     fprintf (dump_file, "\nProcessing worklist:\n");
 648
 649   while (VEC_length (tree, worklist) > 0)
 650     {
 651       /* Take STMT from worklist.  */
 652       stmt = VEC_pop (tree, worklist);
 653
 654       if (dump_file && (dump_flags & TDF_DETAILS))
 655         {
 656           fprintf (dump_file, "processing: ");
 657           print_generic_stmt (dump_file, stmt, TDF_SLIM);
 658           fprintf (dump_file, "\n");
 659         }
 660
 661       if (aggressive)
 662         {
 663           /* Mark the last statements of the basic blocks that the block
 664              containing STMT is control dependent on, but only if we haven't
 665              already done so.  */
 666           basic_block bb = bb_for_stmt (stmt);
 667           if (bb != ENTRY_BLOCK_PTR
 668               && ! TEST_BIT (visited_control_parents, bb->index))
 669             {
 670               SET_BIT (visited_control_parents, bb->index);
 671               mark_control_dependent_edges_necessary (bb, el);
 672             }
 673         }
 674
 675       if (TREE_CODE (stmt) == PHI_NODE)
 676         {
 677           /* PHI nodes are somewhat special in that each PHI alternative has
 678              data and control dependencies.  All the statements feeding the
 679              PHI node's arguments are always necessary.  In aggressive mode,
 680              we also consider the control dependent edges leading to the
 681              predecessor block associated with each PHI alternative as
 682              necessary.  */
 683           int k;
 684
 685           for (k = 0; k < PHI_NUM_ARGS (stmt); k++)
 686             {
 687               tree arg = PHI_ARG_DEF (stmt, k);
 688               if (TREE_CODE (arg) == SSA_NAME)
 689                 mark_operand_necessary (arg);
 690             }
 691
 692           if (aggressive)
 693             {
 694               for (k = 0; k < PHI_NUM_ARGS (stmt); k++)
 695                 {
 696                   basic_block arg_bb = PHI_ARG_EDGE (stmt, k)->src;
 697                   if (arg_bb != ENTRY_BLOCK_PTR
 698                       && ! TEST_BIT (visited_control_parents, arg_bb->index))
 699                     {
 700                       SET_BIT (visited_control_parents, arg_bb->index);
 701                       mark_control_dependent_edges_necessary (arg_bb, el);
 702                     }
 703                 }
 704             }
 705         }
 706       else
 707         {
 708           /* Propagate through the operands.  Examine all the USE, VUSE and
 709              VDEF operands in this statement.  Mark all the statements
 710              which feed this statement's uses as necessary.  The
 711              operands of VDEF expressions are also needed as they
 712              represent potential definitions that may reach this
 713              statement (VDEF operands allow us to follow def-def
 714              links).  */
 715           ssa_op_iter iter;
 716           tree use;
 717
 718           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
 719             mark_operand_necessary (use);
 720         }
 721     }
 722 }
 723
 724 /* Method to generate conditional statements for guarding condionally
 725    dead calls to pow. One or more statements can be generated for
 726    each logical condition. Statement groups of different conditions
 727    are separated by a NULL tree and they are stored in the VEC
 728    conds. The number of logical conditions are stored in *nconds. */
 729 static void
 730 gen_conditions_for_pow (tree pow_call, enum built_in_function fnc,
 731                         VEC (tree, heap)* conds, unsigned * nconds)
 732 {
 733   tree base, expn;
 734   enum tree_code bc, ec;
 735   gcc_assert (TREE_CODE (pow_call) == CALL_EXPR);
 736   gcc_assert (call_expr_nargs (pow_call) == 2);
 737   gcc_assert (fnc == BUILT_IN_POW);
 738
 739   *nconds = 0;
 740
 741   base = CALL_EXPR_ARG (pow_call, 0);
 742   expn = CALL_EXPR_ARG (pow_call, 1);
 743
 744   bc = TREE_CODE (base);
 745   ec = TREE_CODE (expn);
 746
 747   gcc_assert (TREE_CODE_CLASS (bc) != tcc_constant ||
 748              bc == REAL_CST);
 749   gcc_assert (TREE_CODE_CLASS (ec) != tcc_constant ||
 750              ec == REAL_CST);
 751
 752   if (bc == REAL_CST)
 753    {
 754      tree float_typ, max_exp_real_cst;
 755      tree temp, tempn, tempc, tempcn, stmt1, stmt2, stmt3;
 756      REAL_VALUE_TYPE mv;
 757
 758      /* See candidate selection in check_pow.
 759         Since the candidates have a given range
 760         of base values, the guard code generated
 761         for such calls: pow(const,y) are simple:
 762            if ( y > max_y )
 763                pow(const, y);
 764         max_y can be computed separately for each
 765         const base, but in this implemetation, we
 766         choose to compute it using the max base
 767         in the allowed range.  */
 768
 769      REAL_VALUE_TYPE bcv = TREE_REAL_CST (base);
 770      gcc_assert (!REAL_VALUES_EQUAL (bcv, dconst1));
 771      gcc_assert (!REAL_VALUES_LESS (bcv, dconst1));
 772      real_from_integer (&mv, VOIDmode,256,0,1),
 773      gcc_assert (!REAL_VALUES_LESS (mv, bcv));
 774      float_typ = TREE_TYPE (expn);
 775
 776      max_exp_real_cst = build_real (float_typ, mv);
 777      temp = create_tmp_var (float_typ, "DCE_COND");
 778      stmt1 = build_gimple_modify_stmt (temp, expn);
 779      tempn = make_ssa_name (temp, stmt1);
 780      GIMPLE_STMT_OPERAND (stmt1, 0) = tempn;
 781
 782      tempc = create_tmp_var (boolean_type_node, "DCE_COND_TEST");
 783      stmt2 = build_gimple_modify_stmt (tempc,
 784                                        build2 (GT_EXPR,
 785                                                boolean_type_node,
 786                                                tempn, max_exp_real_cst));
 787      tempcn = make_ssa_name (tempc, stmt2);
 788      GIMPLE_STMT_OPERAND (stmt2, 0) = tempcn;
 789
 790      stmt3 = build3 (COND_EXPR, void_type_node,
 791                      tempcn, NULL_TREE, NULL_TREE);
 792      VEC_safe_push (tree, heap, conds, stmt1);
 793      VEC_safe_push (tree, heap, conds, stmt2);
 794      VEC_safe_push (tree, heap, conds, stmt3);
 795      (*nconds)++;
 796
 797    }
 798   else if (bc == SSA_NAME)
 799    {
 800      tree def, nm, rhs, rhs0, var, int_typ, float_typ;
 801      tree max_exp_cst, max_exp_real_cst;
 802      tree temp1, temp1n, temp2, temp2n, temp2c, temp2cn;
 803      tree cst0, stmt1, stmt2, stmt3;
 804      int sz, max_exp;
 805
 806      /* Generate error condition code for pow calls with
 807         non constant base value. The candidates selected
 808         have their base argument value converted from
 809         integer (see check_pow) value (1,2,4 bytes), and
 810         the max exp value is computed based on the size
 811         of the integer type.  The code below first does
 812         sanity check and then does code generation.  */
 813
 814      def = SSA_NAME_DEF_STMT (base);
 815      gcc_assert (TREE_CODE (def) == GIMPLE_MODIFY_STMT);
 816
 817      nm = GIMPLE_STMT_OPERAND (def,0);
 818      gcc_assert (TREE_CODE (nm) == SSA_NAME);
 819      gcc_assert (nm == base);
 820
 821      rhs = GIMPLE_STMT_OPERAND (def,1);
 822
 823      gcc_assert (TREE_CODE (rhs) == FLOAT_EXPR);
 824      rhs0 = TREE_OPERAND (rhs,0);
 825      gcc_assert (TREE_CODE (rhs0) == SSA_NAME);
 826
 827      var = SSA_NAME_VAR (rhs0);
 828      gcc_assert (TREE_CODE (var) == VAR_DECL
 829                  || TREE_CODE (var) == PARM_DECL);
 830
 831      int_typ = TREE_TYPE (var);
 832      gcc_assert (TREE_CODE (int_typ) == INTEGER_TYPE);
 833
 834      sz = int_size_in_bytes (int_typ);
 835      gcc_assert (sz > 0 && sz <= INT_TYPE_SIZE) ;
 836
 837
 838      float_typ = TREE_TYPE (SSA_NAME_VAR (expn));
 839      if (sz == 1)
 840        max_exp = 128;
 841      else if (sz == 2)
 842        max_exp = 64;
 843      else
 844       {
 845         gcc_assert (sz == 4);
 846         max_exp = 32;
 847       }
 848      max_exp_cst = build_int_cst (integer_type_node, max_exp);
 849      max_exp_real_cst = build_real_from_int_cst (float_typ, max_exp_cst);
 850
 851      /* For pow ((dobule)x,y), generate the following conditions:
 852       cond 1:
 853         temp1 = x;
 854         if (temp1 <= 0)
 855
 856       cond 2:
 857         temp2 = y;
 858         if (temp2 > max_exp_real_cst)  */
 859
 860      temp2 = create_tmp_var (float_typ, "DCE_COND2");
 861      stmt1 = build_gimple_modify_stmt (temp2, expn);
 862      temp2n = make_ssa_name (temp2, stmt1);
 863      GIMPLE_STMT_OPERAND (stmt1,0) = temp2n;
 864
 865      temp2c = create_tmp_var (boolean_type_node, "DCE_COND2_TEST");
 866      stmt2 = build_gimple_modify_stmt (temp2c,
 867                                        build2 (GT_EXPR,
 868                                                boolean_type_node,
 869                                                temp2n, max_exp_real_cst));
 870      temp2cn = make_ssa_name (temp2c, stmt2);
 871      GIMPLE_STMT_OPERAND (stmt2, 0) = temp2cn;
 872
 873      stmt3 = build3 (COND_EXPR, void_type_node,
 874                      temp2cn, NULL_TREE, NULL_TREE);
 875      VEC_safe_push (tree, heap, conds, stmt1);
 876      VEC_safe_push (tree, heap, conds, stmt2);
 877      VEC_safe_push (tree, heap, conds, stmt3);
 878      (*nconds)++;
 879
 880      /* Now a seperator*/
 881      VEC_safe_push (tree, heap, conds, NULL);
 882
 883      temp1 = create_tmp_var (int_typ, "DCE_COND1");
 884      cst0 = build_int_cst (int_typ, 0);
 885      stmt1 = build_gimple_modify_stmt (temp1, rhs0);
 886      temp1n = make_ssa_name (temp1, stmt1);
 887      GIMPLE_STMT_OPERAND (stmt1,0) = temp1n;
 888      stmt2 = build3 (COND_EXPR, void_type_node,
 889                      build2 (LE_EXPR, boolean_type_node, temp1n, cst0),
 890                      NULL_TREE, NULL_TREE);
 891
 892      VEC_safe_push (tree, heap, conds, stmt1);
 893      VEC_safe_push (tree, heap, conds, stmt2);
 894      (*nconds)++;
 895
 896    }
 897   else
 898     gcc_unreachable ();
 899 }
 900
 901 /* The method to generate error condition guard code for log(x)
 902    calls. */
 903 static void
 904 gen_conditions_for_log (tree call, enum built_in_function fnc,
 905                         VEC (tree, heap)* conds, unsigned * nconds)
 906 {
 907   tree arg, cst0, temp, tempn, tempc, tempcn, stmt1, stmt2, stmt3;
 908   gcc_assert (TREE_CODE (call) == CALL_EXPR);
 909   gcc_assert (fnc == BUILT_IN_LOG || fnc == BUILT_IN_LOGF || fnc == BUILT_IN_LOGL);
 910
 911   *nconds = 0;
 912
 913   /* for log(x),
 914    Generate condition
 915
 916    temp = x
 917    if (x <= 0)
 918   */
 919   arg = CALL_EXPR_ARG (call, 0);
 920   cst0 = build_real (TREE_TYPE (arg), dconst0);
 921   temp = create_tmp_var (TREE_TYPE (arg), "DCE_COND");
 922   stmt1 = build_gimple_modify_stmt (temp, arg);
 923   tempn = make_ssa_name (temp, stmt1);
 924   GIMPLE_STMT_OPERAND (stmt1,0) = tempn;
 925
 926   tempc = create_tmp_var (boolean_type_node, "DCE_COND_TEST");
 927   stmt2 = build_gimple_modify_stmt (tempc,
 928                                     build2 (LE_EXPR,
 929                                             boolean_type_node,
 930                                             tempn, cst0));
 931   tempcn = make_ssa_name (tempc, stmt2);
 932   GIMPLE_STMT_OPERAND (stmt2, 0) = tempcn;
 933
 934   stmt3 = build3 (COND_EXPR, void_type_node, tempcn,
 935                        NULL_TREE, NULL_TREE);
 936
 937   VEC_safe_push (tree, heap, conds, stmt1);
 938   VEC_safe_push (tree, heap, conds, stmt2);
 939   VEC_safe_push (tree, heap, conds, stmt3);
 940   (*nconds)++;
 941
 942 }
 943
 944
 945 /*  The method to generate shrink wrap conditions for partially
 946     a dead builtin call whose return value is not used anywhere,
 947     but has to be kept live due to potential error condition.
 948
 949     BI_CALL:  the builtin call
 950     CONDS  :  the vector of statements for condition code
 951     NCODES :  the pointer to the number of logical conditions,
 952               which may be different from the length of CONDS
 953               vector. Statements belonging to different logical
 954               condition are separated by NULL tree in the vector
 955 */
 956
 957 static void
 958 gen_shrink_wrap_conditions (tree bi_call, VEC (tree, heap)* conds, unsigned int * nconds)
 959 {
 960   tree call, fn;
 961   enum built_in_function fnc;
 962   gcc_assert (nconds && conds);
 963   gcc_assert (VEC_length(tree, conds) == 0);
 964   gcc_assert (TREE_CODE (bi_call) == GIMPLE_MODIFY_STMT
 965               || TREE_CODE (bi_call) == CALL_EXPR);
 966
 967   call = bi_call;
 968   if (TREE_CODE (call) == GIMPLE_MODIFY_STMT)
 969     call = get_call_expr_in (bi_call);
 970
 971   fn = get_callee_fndecl (call);
 972   gcc_assert (fn && DECL_BUILT_IN (fn));
 973   fnc = DECL_FUNCTION_CODE (fn);
 974   *nconds = 0;
 975
 976   switch (fnc)
 977     {
 978      case BUILT_IN_POW:
 979        gen_conditions_for_pow (call, fnc, conds, nconds);
 980        break;
 981      case BUILT_IN_LOG:
 982      case BUILT_IN_LOGF:
 983      case BUILT_IN_LOGL:
 984        gen_conditions_for_log (call, fnc, conds, nconds);
 985        break;
 986      default :
 987        gcc_unreachable();
 988      break;
 989    }
 990
 991   gcc_assert (*nconds);
 992   return;
 993 }
 994
 995
 996 /* Propability of the branch (to the call) is taken. */
 997 #define ERR_PROB 0.01
 998
 999 /*  The method to shrink wrap a partially  dead builtin call
1000     whose return value is not used anywhere, but has to be kept
1001     live due to potential error condition.  */
1002 static void
1003 shrink_wrap_one_built_in_call (tree bi_call)
1004 {
1005   block_stmt_iterator bi_call_bsi, join_tgt_bsi;
1006   basic_block bi_call_bb, join_tgt_bb, guard_bb, guard_bb0;
1007   edge join_tgt_in_edge_from_call, join_tgt_in_edge_fall_thru;
1008   tree join_tgt_label_decl, join_tgt_label;
1009   edge bi_call_in_edge0, guard_bb_in_edge;
1010   VEC (tree, heap) *conds;
1011   unsigned tn_cond_stmts, nconds;
1012   unsigned ci;
1013   tree cond_expr = NULL;
1014   tree cond_expr_start;
1015   tree bi_call_label_decl;
1016   tree bi_call_label;
1017
1018   conds = VEC_alloc (tree, heap, 10);
1019   gen_shrink_wrap_conditions (bi_call, conds, &nconds);
1020
1021   gcc_assert (nconds > 0);
1022   /* Make sure no reallocation happens. */
1023   gcc_assert (VEC_length (tree, conds) <= 10);
1024   gcc_assert (VEC_length (tree, conds) >= nconds);
1025   bi_call_bb = bb_for_stmt (bi_call);
1026
1027   /* Now find the join target bb -- split
1028      bi_call_bb if needed */
1029   bi_call_bsi = bsi_for_stmt (bi_call);
1030
1031   gcc_assert (!bsi_end_p (bi_call_bsi));
1032   join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call);
1033   bi_call_bsi = bsi_for_stmt (bi_call);
1034
1035   join_tgt_bb = join_tgt_in_edge_from_call->dest;
1036   join_tgt_label_decl = create_artificial_label ();
1037   join_tgt_label = build1 (LABEL_EXPR, void_type_node, join_tgt_label_decl);
1038   join_tgt_bsi = bsi_start (join_tgt_bb);
1039   bsi_insert_before (&join_tgt_bsi, join_tgt_label, BSI_SAME_STMT);
1040
1041   /* Now it is time to insert the first condtional expression
1042      into bi_call_bb and split this bb so that bi_call is
1043      shrink-wrapped*/
1044   tn_cond_stmts = VEC_length (tree, conds);
1045   cond_expr = NULL;
1046   cond_expr_start = VEC_index (tree, conds,0);
1047   for (ci = 0; ci < tn_cond_stmts; ci++)
1048    {
1049      tree c = VEC_index (tree, conds, ci);
1050      gcc_assert ( c || ci != 0 );
1051      if (!c)
1052        break;
1053      bsi_insert_before (&bi_call_bsi, c, BSI_SAME_STMT);
1054      cond_expr = c;
1055    }
1056   nconds --;
1057   ci ++;
1058   gcc_assert (cond_expr && TREE_CODE (cond_expr) == COND_EXPR);
1059
1060   /* Now the label*/
1061   bi_call_label_decl = create_artificial_label ();
1062   bi_call_label = build1 (LABEL_EXPR, void_type_node, bi_call_label_decl);
1063   bsi_insert_before (&bi_call_bsi, bi_call_label, BSI_SAME_STMT);
1064
1065   bi_call_in_edge0 = split_block (bi_call_bb, cond_expr);
1066   bi_call_in_edge0->flags &= ~EDGE_FALLTHRU;
1067   bi_call_in_edge0->flags |= EDGE_TRUE_VALUE;
1068   guard_bb0 = bi_call_bb;
1069   bi_call_bb = bi_call_in_edge0->dest;
1070   join_tgt_in_edge_fall_thru = make_edge (guard_bb0, join_tgt_bb, EDGE_FALSE_VALUE);
1071
1072   bi_call_in_edge0->probability = REG_BR_PROB_BASE*ERR_PROB;
1073   join_tgt_in_edge_fall_thru->probability =
1074       REG_BR_PROB_BASE - bi_call_in_edge0->probability;
1075
1076   /* Code generation for the rest of the conditions */
1077   guard_bb = guard_bb0;
1078   for (; nconds > 0; )
1079    {
1080      unsigned ci0;
1081      edge bi_call_in_edge;
1082      block_stmt_iterator guard_bsi = bsi_for_stmt (cond_expr_start);
1083      ci0 = ci;
1084      cond_expr_start = VEC_index (tree, conds, ci0);
1085      for (; ci < tn_cond_stmts; ci++)
1086       {
1087         tree c = VEC_index (tree, conds, ci);
1088         gcc_assert ( c || ci != ci0 );
1089         if (!c)
1090           break;
1091         bsi_insert_before (&guard_bsi, c, BSI_SAME_STMT);
1092         cond_expr = c;
1093       }
1094      nconds --;
1095      ci ++;
1096      gcc_assert (cond_expr && TREE_CODE (cond_expr) == COND_EXPR);
1097      guard_bb_in_edge = split_block (guard_bb, cond_expr);
1098      guard_bb_in_edge->flags &= ~EDGE_FALLTHRU;
1099      guard_bb_in_edge->flags |= EDGE_FALSE_VALUE;
1100
1101      bi_call_in_edge = make_edge (guard_bb, bi_call_bb, EDGE_TRUE_VALUE);
1102
1103      bi_call_in_edge->probability = REG_BR_PROB_BASE * ERR_PROB;
1104      guard_bb_in_edge->probability =
1105          REG_BR_PROB_BASE - bi_call_in_edge->probability;
1106
1107    }
1108
1109   VEC_free (tree, heap, conds);
1110   if (dump_file && (dump_flags & TDF_DETAILS))
1111    {
1112      location_t loc;
1113      loc = EXPR_LOCATION (bi_call);
1114      inform (
1115          "%Hfunction call is shrink-wrapped into error conditions.",
1116          &loc);
1117    }
1118 }
1119
1120 /*  The top level method for conditional dead code shrink
1121     wrapping transformation.  */
1122
1123 static bool
1124 shrink_wrap_conditional_dead_built_in_calls (void)
1125 {
1126   unsigned i = 0;
1127   unsigned n = VEC_length (tree, cond_dead_built_in_calls);
1128   if (n == 0) return false;
1129
1130   for (; i < n ; i++)
1131    {
1132      tree bi_call = VEC_index (tree,  cond_dead_built_in_calls, i);
1133      shrink_wrap_one_built_in_call (bi_call);
1134    }
1135
1136   cfg_altered = true;
1137
1138   return true;
1139 }
1140
1141 /* Remove dead PHI nodes from block BB.  */
1142
1143 static bool
1144 remove_dead_phis (basic_block bb)
1145 {
1146   tree prev, phi;
1147   bool something_changed = false;
1148
1149   prev = NULL_TREE;
1150   phi = phi_nodes (bb);
1151   while (phi)
1152     {
1153       stats.total_phis++;
1154
1155       if (! NECESSARY (phi))
1156         {
1157           tree next = PHI_CHAIN (phi);
1158
1159           something_changed = true;
1160           if (dump_file && (dump_flags & TDF_DETAILS))
1161             {
1162               fprintf (dump_file, "Deleting : ");
1163               print_generic_stmt (dump_file, phi, TDF_SLIM);
1164               fprintf (dump_file, "\n");
1165             }
1166
1167           remove_phi_node (phi, prev, true);
1168           stats.removed_phis++;
1169           phi = next;
1170         }
1171       else
1172         {
1173           prev = phi;
1174           phi = PHI_CHAIN (phi);
1175         }
1176     }
1177   return something_changed;
1178 }
1179
1180
1181 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
1182    containing I so that we don't have to look it up.  */
1183
1184 static void
1185 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
1186 {
1187   tree t = bsi_stmt (*i);
1188
1189   if (dump_file && (dump_flags & TDF_DETAILS))
1190     {
1191       fprintf (dump_file, "Deleting : ");
1192       print_generic_stmt (dump_file, t, TDF_SLIM);
1193       fprintf (dump_file, "\n");
1194     }
1195
1196   stats.removed++;
1197
1198   /* If we have determined that a conditional branch statement contributes
1199      nothing to the program, then we not only remove it, but we also change
1200      the flow graph so that the current block will simply fall-thru to its
1201      immediate post-dominator.  The blocks we are circumventing will be
1202      removed by cleanup_tree_cfg if this change in the flow graph makes them
1203      unreachable.  */
1204   if (is_ctrl_stmt (t))
1205     {
1206       basic_block post_dom_bb;
1207
1208       /* The post dominance info has to be up-to-date.  */
1209       gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
1210       /* Get the immediate post dominator of bb.  */
1211       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
1212
1213       /* There are three particularly problematical cases.
1214
1215          1. Blocks that do not have an immediate post dominator.  This
1216             can happen with infinite loops.
1217
1218          2. Blocks that are only post dominated by the exit block.  These
1219             can also happen for infinite loops as we create fake edges
1220             in the dominator tree.
1221
1222          3. If the post dominator has PHI nodes we may be able to compute
1223             the right PHI args for them.
1224
1225          In each of these cases we must remove the control statement
1226          as it may reference SSA_NAMEs which are going to be removed and
1227          we remove all but one outgoing edge from the block.  */
1228       if (! post_dom_bb
1229           || post_dom_bb == EXIT_BLOCK_PTR
1230           || phi_nodes (post_dom_bb))
1231         ;
1232       else
1233         {
1234           /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
1235           redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
1236           PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
1237
1238           /* It is not sufficient to set cfg_altered below during edge
1239              removal, in case BB has two successors and one of them
1240              is POST_DOM_BB.  */
1241           cfg_altered = true;
1242         }
1243       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
1244       EDGE_SUCC (bb, 0)->count = bb->count;
1245
1246       /* The edge is no longer associated with a conditional, so it does
1247          not have TRUE/FALSE flags.  */
1248       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
1249
1250       /* The lone outgoing edge from BB will be a fallthru edge.  */
1251       EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
1252
1253       /* Remove the remaining the outgoing edges.  */
1254       while (!single_succ_p (bb))
1255         {
1256           /* FIXME.  When we remove the edge, we modify the CFG, which
1257              in turn modifies the dominator and post-dominator tree.
1258              Is it safe to postpone recomputing the dominator and
1259              post-dominator tree until the end of this pass given that
1260              the post-dominators are used above?  */
1261           cfg_altered = true;
1262           remove_edge (EDGE_SUCC (bb, 1));
1263         }
1264     }
1265
1266   bsi_remove (i, true);
1267   release_defs (t);
1268 }
1269
1270
1271 /* Eliminate unnecessary statements. Any instruction not marked as necessary
1272    contributes nothing to the program, and can be deleted.  */
1273
1274 static bool
1275 eliminate_unnecessary_stmts (void)
1276 {
1277   bool something_changed = false;
1278   basic_block bb;
1279   block_stmt_iterator i;
1280
1281   if (dump_file && (dump_flags & TDF_DETAILS))
1282     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1283
1284   clear_special_calls ();
1285   FOR_EACH_BB (bb)
1286     {
1287       /* Remove dead PHI nodes.  */
1288       something_changed |= remove_dead_phis (bb);
1289     }
1290
1291   FOR_EACH_BB (bb)
1292     {
1293       /* Remove dead statements.  */
1294       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
1295         {
1296           tree t = bsi_stmt (i);
1297
1298           stats.total++;
1299
1300           /* If `i' is not necessary then remove it.  */
1301           if (! NECESSARY (t))
1302             {
1303               remove_dead_stmt (&i, bb);
1304               something_changed = true;
1305             }
1306           else
1307             {
1308               tree call = get_call_expr_in (t);
1309               if (call)
1310                 {
1311                   tree name;
1312
1313                   /* When LHS of var = call (); is dead, simplify it into
1314                      call (); saving one operand.  */
1315                   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
1316                       && (TREE_CODE ((name = GIMPLE_STMT_OPERAND (t, 0)))
1317                           == SSA_NAME)
1318                       && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
1319                     {
1320                       tree oldlhs = GIMPLE_STMT_OPERAND (t, 0);
1321                       something_changed = true;
1322                       if (dump_file && (dump_flags & TDF_DETAILS))
1323                         {
1324                           fprintf (dump_file, "Deleting LHS of call: ");
1325                           print_generic_stmt (dump_file, t, TDF_SLIM);
1326                           fprintf (dump_file, "\n");
1327                         }
1328
1329                       if (is_unnecessary_except_errno_call (call))
1330                        {
1331                          if (dump_file && (dump_flags & TDF_DETAILS))
1332                           {
1333                             fprintf (dump_file, "Found conditional dead call: ");
1334                             print_generic_stmt (dump_file, t, TDF_SLIM);
1335                             fprintf (dump_file, "\n");
1336                           }
1337                          VEC_safe_push (tree, heap, cond_dead_built_in_calls, call);
1338                        }
1339
1340                       push_stmt_changes (bsi_stmt_ptr (i));
1341                       TREE_BLOCK (call) = TREE_BLOCK (t);
1342                       bsi_replace (&i, call, false);
1343                       maybe_clean_or_replace_eh_stmt (t, call);
1344                       mark_symbols_for_renaming (call);
1345                       pop_stmt_changes (bsi_stmt_ptr (i));
1346                       release_ssa_name (oldlhs);
1347
1348
1349                     }
1350                   notice_special_calls (call);
1351                 }
1352               bsi_next (&i);
1353             }
1354         }
1355     }
1356
1357   something_changed |=
1358       shrink_wrap_conditional_dead_built_in_calls ();
1359
1360   return something_changed;
1361 }
1362
1363
1364 /* Print out removed statement statistics.  */
1365
1366 static void
1367 print_stats (void)
1368 {
1369   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
1370     {
1371       float percg;
1372
1373       percg = ((float) stats.removed / (float) stats.total) * 100;
1374       fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1375                stats.removed, stats.total, (int) percg);
1376
1377       if (stats.total_phis == 0)
1378         percg = 0;
1379       else
1380         percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1381
1382       fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1383                stats.removed_phis, stats.total_phis, (int) percg);
1384     }
1385 }
1386 \f
1387 /* Initialization for this pass.  Set up the used data structures.  */
1388
1389 static void
1390 tree_dce_init (bool aggressive)
1391 {
1392   memset ((void *) &stats, 0, sizeof (stats));
1393
1394   if (aggressive)
1395     {
1396       int i;
1397
1398       control_dependence_map = XNEWVEC (bitmap, last_basic_block);
1399       for (i = 0; i < last_basic_block; ++i)
1400         control_dependence_map[i] = BITMAP_ALLOC (NULL);
1401
1402       last_stmt_necessary = sbitmap_alloc (last_basic_block);
1403       sbitmap_zero (last_stmt_necessary);
1404     }
1405
1406   processed = sbitmap_alloc (num_ssa_names + 1);
1407   sbitmap_zero (processed);
1408
1409   worklist = VEC_alloc (tree, heap, 64);
1410   cond_dead_built_in_calls = VEC_alloc (tree, heap,64);
1411   cfg_altered = false;
1412
1413 }
1414
1415 /* Cleanup after this pass.  */
1416
1417 static void
1418 tree_dce_done (bool aggressive)
1419 {
1420   if (aggressive)
1421     {
1422       int i;
1423
1424       for (i = 0; i < last_basic_block; ++i)
1425         BITMAP_FREE (control_dependence_map[i]);
1426       free (control_dependence_map);
1427
1428       sbitmap_free (visited_control_parents);
1429       sbitmap_free (last_stmt_necessary);
1430     }
1431
1432   sbitmap_free (processed);
1433
1434   VEC_free (tree, heap, worklist);
1435   VEC_free (tree, heap, cond_dead_built_in_calls);
1436 }
1437
1438 \f
1439 /* Main routine to eliminate dead code.
1440
1441    AGGRESSIVE controls the aggressiveness of the algorithm.
1442    In conservative mode, we ignore control dependence and simply declare
1443    all but the most trivially dead branches necessary.  This mode is fast.
1444    In aggressive mode, control dependences are taken into account, which
1445    results in more dead code elimination, but at the cost of some time.
1446
1447    FIXME: Aggressive mode before PRE doesn't work currently because
1448           the dominance info is not invalidated after DCE1.  This is
1449           not an issue right now because we only run aggressive DCE
1450           as the last tree SSA pass, but keep this in mind when you
1451           start experimenting with pass ordering.  */
1452
1453 static unsigned int
1454 perform_tree_ssa_dce (bool aggressive)
1455 {
1456   struct edge_list *el = NULL;
1457   bool something_changed = 0;
1458
1459   tree_dce_init (aggressive);
1460
1461   if (aggressive)
1462     {
1463       /* Compute control dependence.  */
1464       timevar_push (TV_CONTROL_DEPENDENCES);
1465       calculate_dominance_info (CDI_POST_DOMINATORS);
1466       el = create_edge_list ();
1467       find_all_control_dependences (el);
1468       timevar_pop (TV_CONTROL_DEPENDENCES);
1469
1470       visited_control_parents = sbitmap_alloc (last_basic_block);
1471       sbitmap_zero (visited_control_parents);
1472
1473       mark_dfs_back_edges ();
1474     }
1475
1476   find_obviously_necessary_stmts (el);
1477
1478   propagate_necessity (el);
1479
1480   something_changed |= eliminate_unnecessary_stmts ();
1481   something_changed |= cfg_altered;
1482
1483   /* We do not update postdominators, so free them unconditionally.  */
1484   free_dominance_info (CDI_POST_DOMINATORS);
1485
1486   /* If we removed paths in the CFG, then we need to update
1487      dominators as well.  I haven't investigated the possibility
1488      of incrementally updating dominators.  */
1489   if (cfg_altered)
1490     free_dominance_info (CDI_DOMINATORS);
1491
1492   /* Debugging dumps.  */
1493   if (dump_file)
1494     print_stats ();
1495
1496   tree_dce_done (aggressive);
1497
1498   free_edge_list (el);
1499
1500   if (something_changed)
1501     return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
1502             | TODO_remove_unused_locals);
1503   else
1504     return 0;
1505 }
1506
1507 /* Pass entry points.  */
1508 static unsigned int
1509 tree_ssa_dce (void)
1510 {
1511   return perform_tree_ssa_dce (/*aggressive=*/false);
1512 }
1513
1514 static unsigned int
1515 tree_ssa_dce_loop (void)
1516 {
1517   unsigned int todo;
1518   todo = perform_tree_ssa_dce (/*aggressive=*/false);
1519   if (todo)
1520     {
1521       free_numbers_of_iterations_estimates ();
1522       scev_reset ();
1523     }
1524   return todo;
1525 }
1526
1527 static unsigned int
1528 tree_ssa_cd_dce (void)
1529 {
1530   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
1531 }
1532
1533 static bool
1534 gate_dce (void)
1535 {
1536   return flag_tree_dce != 0;
1537 }
1538
1539 struct gimple_opt_pass pass_dce =
1540 {
1541  {
1542   GIMPLE_PASS,
1543   "dce",                                /* name */
1544   gate_dce,                             /* gate */
1545   tree_ssa_dce,                         /* execute */
1546   NULL,                                 /* sub */
1547   NULL,                                 /* next */
1548   0,                                    /* static_pass_number */
1549   TV_TREE_DCE,                          /* tv_id */
1550   PROP_cfg | PROP_ssa,                  /* properties_required */
1551   0,                                    /* properties_provided */
1552   0,                                    /* properties_destroyed */
1553   0,                                    /* todo_flags_start */
1554   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1555  }
1556 };
1557
1558 struct gimple_opt_pass pass_dce_loop =
1559 {
1560  {
1561   GIMPLE_PASS,
1562   "dceloop",                            /* name */
1563   gate_dce,                             /* gate */
1564   tree_ssa_dce_loop,                    /* execute */
1565   NULL,                                 /* sub */
1566   NULL,                                 /* next */
1567   0,                                    /* static_pass_number */
1568   TV_TREE_DCE,                          /* tv_id */
1569   PROP_cfg | PROP_ssa,                  /* properties_required */
1570   0,                                    /* properties_provided */
1571   0,                                    /* properties_destroyed */
1572   0,                                    /* todo_flags_start */
1573   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1574  }
1575 };
1576
1577 struct gimple_opt_pass pass_cd_dce =
1578 {
1579  {
1580   GIMPLE_PASS,
1581   "cddce",                              /* name */
1582   gate_dce,                             /* gate */
1583   tree_ssa_cd_dce,                      /* execute */
1584   NULL,                                 /* sub */
1585   NULL,                                 /* next */
1586   0,                                    /* static_pass_number */
1587   TV_TREE_CD_DCE,                       /* tv_id */
1588   PROP_cfg | PROP_ssa,                  /* properties_required */
1589   0,                                    /* properties_provided */
1590   0,                                    /* properties_destroyed */
1591   0,                                    /* todo_flags_start */
1592   TODO_dump_func | TODO_verify_ssa
1593   | TODO_verify_flow                    /* todo_flags_finish */
1594  }
1595 };