gcc/gimple-ssa-evrp.c

   1 /* Support routines for Value Range Propagation (VRP).
   2    Copyright (C) 2005-2017 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "tree-pass.h"
  27 #include "ssa.h"
  28 #include "gimple-pretty-print.h"
  29 #include "cfganal.h"
  30 #include "gimple-fold.h"
  31 #include "tree-eh.h"
  32 #include "gimple-iterator.h"
  33 #include "tree-cfg.h"
  34 #include "tree-ssa-loop-manip.h"
  35 #include "tree-ssa-loop.h"
  36 #include "cfgloop.h"
  37 #include "tree-scalar-evolution.h"
  38 #include "tree-ssa-propagate.h"
  39 #include "alloc-pool.h"
  40 #include "domwalk.h"
  41 #include "tree-cfgcleanup.h"
  42 #include "vr-values.h"
  43
  44 class evrp_folder : public substitute_and_fold_engine
  45 {
  46  public:
  47   tree get_value (tree) FINAL OVERRIDE;
  48
  49   class vr_values *vr_values;
  50 };
  51
  52 tree
  53 evrp_folder::get_value (tree op)
  54 {
  55   return vr_values->op_with_constant_singleton_value_range (op);
  56 }
  57
  58 class evrp_range_analyzer
  59 {
  60  public:
  61   evrp_range_analyzer (void);
  62   ~evrp_range_analyzer (void) { stack.release (); }
  63
  64   void enter (basic_block);
  65   void leave (basic_block);
  66   void record_ranges_from_stmt (gimple *);
  67
  68   class vr_values vr_values;
  69
  70  private:
  71   DISABLE_COPY_AND_ASSIGN (evrp_range_analyzer);
  72   void push_value_range (tree var, value_range *vr);
  73   value_range *pop_value_range (tree var);
  74   value_range *try_find_new_range (tree, tree op, tree_code code, tree limit);
  75   void record_ranges_from_incoming_edge (basic_block);
  76   void record_ranges_from_phis (basic_block);
  77
  78   /* STACK holds the old VR.  */
  79   auto_vec<std::pair <tree, value_range*> > stack;
  80
  81   /* Temporary delegators.  */
  82   value_range *get_value_range (const_tree op)
  83     { return vr_values.get_value_range (op); }
  84   bool update_value_range (const_tree op, value_range *vr)
  85     { return vr_values.update_value_range (op, vr); }
  86   void extract_range_from_phi_node (gphi *phi, value_range *vr)
  87     { vr_values.extract_range_from_phi_node (phi, vr); }
  88   void adjust_range_with_scev (value_range *vr, struct loop *loop,
  89                                gimple *stmt, tree var)
  90     { vr_values.adjust_range_with_scev (vr, loop, stmt, var); }
  91   void extract_range_from_stmt (gimple *stmt, edge *taken_edge_p,
  92                                 tree *output_p, value_range *vr)
  93     { vr_values.extract_range_from_stmt (stmt, taken_edge_p, output_p, vr); }
  94   void set_defs_to_varying (gimple *stmt)
  95     { return vr_values.set_defs_to_varying (stmt); }
  96   void set_vr_value (tree name, value_range *vr)
  97     { vr_values.set_vr_value (name, vr); }
  98   void extract_range_for_var_from_comparison_expr (tree var,
  99                                                    enum tree_code cond_code,
 100                                                    tree op, tree limit,
 101                                                    value_range *vr_p)
 102     { vr_values.extract_range_for_var_from_comparison_expr (var, cond_code,
 103                                                             op, limit, vr_p); }
 104 };
 105
 106 evrp_range_analyzer::evrp_range_analyzer () : stack (10)
 107 {
 108   edge e;
 109   edge_iterator ei;
 110   basic_block bb;
 111
 112   FOR_EACH_BB_FN (bb, cfun)
 113     {
 114       bb->flags &= ~BB_VISITED;
 115       FOR_EACH_EDGE (e, ei, bb->preds)
 116         e->flags |= EDGE_EXECUTABLE;
 117     }
 118 }
 119
 120
 121 /* evrp_dom_walker visits the basic blocks in the dominance order and set
 122    the Value Ranges (VR) for SSA_NAMEs in the scope.  Use this VR to
 123    discover more VRs.  */
 124
 125 class evrp_dom_walker : public dom_walker
 126 {
 127 public:
 128   evrp_dom_walker () : dom_walker (CDI_DOMINATORS)
 129     {
 130       need_eh_cleanup = BITMAP_ALLOC (NULL);
 131     }
 132   ~evrp_dom_walker ()
 133     {
 134       BITMAP_FREE (need_eh_cleanup);
 135     }
 136   virtual edge before_dom_children (basic_block);
 137   virtual void after_dom_children (basic_block);
 138   void cleanup (void);
 139
 140  private:
 141   DISABLE_COPY_AND_ASSIGN (evrp_dom_walker);
 142   bitmap need_eh_cleanup;
 143   auto_vec<gimple *> stmts_to_fixup;
 144   auto_vec<gimple *> stmts_to_remove;
 145
 146   class evrp_range_analyzer evrp_range_analyzer;
 147
 148   /* Temporary delegators.  */
 149   value_range *get_value_range (const_tree op)
 150     { return evrp_range_analyzer.vr_values.get_value_range (op); }
 151   tree op_with_constant_singleton_value_range (tree op)
 152     { return evrp_range_analyzer.vr_values.op_with_constant_singleton_value_range (op); }
 153   void vrp_visit_cond_stmt (gcond *cond, edge *e)
 154     { evrp_range_analyzer.vr_values.vrp_visit_cond_stmt (cond, e); }
 155 };
 156
 157 void
 158 evrp_range_analyzer::enter (basic_block bb)
 159 {
 160   stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
 161   record_ranges_from_incoming_edge (bb);
 162   record_ranges_from_phis (bb);
 163 }
 164
 165 /* Find new range for NAME such that (OP CODE LIMIT) is true.  */
 166 value_range *
 167 evrp_range_analyzer::try_find_new_range (tree name,
 168                                     tree op, tree_code code, tree limit)
 169 {
 170   value_range vr = VR_INITIALIZER;
 171   value_range *old_vr = get_value_range (name);
 172
 173   /* Discover VR when condition is true.  */
 174   extract_range_for_var_from_comparison_expr (name, code, op,
 175                                               limit, &vr);
 176   /* If we found any usable VR, set the VR to ssa_name and create a
 177      PUSH old value in the stack with the old VR.  */
 178   if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
 179     {
 180       if (old_vr->type == vr.type
 181           && vrp_operand_equal_p (old_vr->min, vr.min)
 182           && vrp_operand_equal_p (old_vr->max, vr.max))
 183         return NULL;
 184       value_range *new_vr = vr_values.vrp_value_range_pool.allocate ();
 185       *new_vr = vr;
 186       return new_vr;
 187     }
 188   return NULL;
 189 }
 190
 191 /* If BB is reached by a single incoming edge (ignoring loop edges),
 192    then derive ranges implied by traversing that edge.  */
 193
 194 void
 195 evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb)
 196 {
 197   edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
 198   if (pred_e)
 199     {
 200       gimple *stmt = last_stmt (pred_e->src);
 201       tree op0 = NULL_TREE;
 202
 203       if (stmt
 204           && gimple_code (stmt) == GIMPLE_COND
 205           && (op0 = gimple_cond_lhs (stmt))
 206           && TREE_CODE (op0) == SSA_NAME
 207           && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
 208               || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
 209         {
 210           if (dump_file && (dump_flags & TDF_DETAILS))
 211             {
 212               fprintf (dump_file, "Visiting controlling predicate ");
 213               print_gimple_stmt (dump_file, stmt, 0);
 214             }
 215           /* Entering a new scope.  Try to see if we can find a VR
 216              here.  */
 217           tree op1 = gimple_cond_rhs (stmt);
 218           if (TREE_OVERFLOW_P (op1))
 219             op1 = drop_tree_overflow (op1);
 220           tree_code code = gimple_cond_code (stmt);
 221
 222           auto_vec<assert_info, 8> asserts;
 223           register_edge_assert_for (op0, pred_e, code, op0, op1, asserts);
 224           if (TREE_CODE (op1) == SSA_NAME)
 225             register_edge_assert_for (op1, pred_e, code, op0, op1, asserts);
 226
 227           auto_vec<std::pair<tree, value_range *>, 8> vrs;
 228           for (unsigned i = 0; i < asserts.length (); ++i)
 229             {
 230               value_range *vr = try_find_new_range (asserts[i].name,
 231                                                     asserts[i].expr,
 232                                                     asserts[i].comp_code,
 233                                                     asserts[i].val);
 234               if (vr)
 235                 vrs.safe_push (std::make_pair (asserts[i].name, vr));
 236             }
 237           /* Push updated ranges only after finding all of them to avoid
 238              ordering issues that can lead to worse ranges.  */
 239           for (unsigned i = 0; i < vrs.length (); ++i)
 240             push_value_range (vrs[i].first, vrs[i].second);
 241         }
 242     }
 243 }
 244
 245 void
 246 evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
 247 {
 248   /* Visit PHI stmts and discover any new VRs possible.  */
 249   bool has_unvisited_preds = false;
 250   edge_iterator ei;
 251   edge e;
 252   FOR_EACH_EDGE (e, ei, bb->preds)
 253     if (e->flags & EDGE_EXECUTABLE
 254         && !(e->src->flags & BB_VISITED))
 255       {
 256         has_unvisited_preds = true;
 257         break;
 258       }
 259
 260   for (gphi_iterator gpi = gsi_start_phis (bb);
 261        !gsi_end_p (gpi); gsi_next (&gpi))
 262     {
 263       gphi *phi = gpi.phi ();
 264       tree lhs = PHI_RESULT (phi);
 265       if (virtual_operand_p (lhs))
 266         continue;
 267
 268       value_range vr_result = VR_INITIALIZER;
 269       bool interesting = stmt_interesting_for_vrp (phi);
 270       if (!has_unvisited_preds && interesting)
 271         extract_range_from_phi_node (phi, &vr_result);
 272       else
 273         {
 274           set_value_range_to_varying (&vr_result);
 275           /* When we have an unvisited executable predecessor we can't
 276              use PHI arg ranges which may be still UNDEFINED but have
 277              to use VARYING for them.  But we can still resort to
 278              SCEV for loop header PHIs.  */
 279           struct loop *l;
 280           if (interesting
 281               && (l = loop_containing_stmt (phi))
 282               && l->header == gimple_bb (phi))
 283           adjust_range_with_scev (&vr_result, l, phi, lhs);
 284         }
 285       update_value_range (lhs, &vr_result);
 286
 287       /* Set the SSA with the value range.  */
 288       if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
 289         {
 290           if ((vr_result.type == VR_RANGE
 291                || vr_result.type == VR_ANTI_RANGE)
 292               && (TREE_CODE (vr_result.min) == INTEGER_CST)
 293               && (TREE_CODE (vr_result.max) == INTEGER_CST))
 294             set_range_info (lhs, vr_result.type,
 295                             wi::to_wide (vr_result.min),
 296                             wi::to_wide (vr_result.max));
 297         }
 298       else if (POINTER_TYPE_P (TREE_TYPE (lhs))
 299                && ((vr_result.type == VR_RANGE
 300                     && range_includes_zero_p (vr_result.min,
 301                                               vr_result.max) == 0)
 302                    || (vr_result.type == VR_ANTI_RANGE
 303                        && range_includes_zero_p (vr_result.min,
 304                                                  vr_result.max) == 1)))
 305         set_ptr_nonnull (lhs);
 306     }
 307 }
 308
 309 /* Record any ranges created by statement STMT.  */
 310
 311 void
 312 evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt)
 313 {
 314   tree output = NULL_TREE;
 315
 316   if (dyn_cast <gcond *> (stmt))
 317     ;
 318   else if (stmt_interesting_for_vrp (stmt))
 319     {
 320       edge taken_edge;
 321       value_range vr = VR_INITIALIZER;
 322       extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
 323       if (output && (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE))
 324         {
 325           update_value_range (output, &vr);
 326
 327           /* Set the SSA with the value range.  */
 328           if (INTEGRAL_TYPE_P (TREE_TYPE (output)))
 329             {
 330               if ((vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
 331                   && (TREE_CODE (vr.min) == INTEGER_CST)
 332                   && (TREE_CODE (vr.max) == INTEGER_CST))
 333                 set_range_info (output, vr.type,
 334                                 wi::to_wide (vr.min),
 335                                 wi::to_wide (vr.max));
 336             }
 337           else if (POINTER_TYPE_P (TREE_TYPE (output))
 338                    && ((vr.type == VR_RANGE
 339                         && range_includes_zero_p (vr.min, vr.max) == 0)
 340                        || (vr.type == VR_ANTI_RANGE
 341                            && range_includes_zero_p (vr.min, vr.max) == 1)))
 342             set_ptr_nonnull (output);
 343         }
 344       else
 345         set_defs_to_varying (stmt);
 346     }
 347   else
 348     set_defs_to_varying (stmt);
 349
 350   /* See if we can derive a range for any of STMT's operands.  */
 351   tree op;
 352   ssa_op_iter i;
 353   FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
 354     {
 355       tree value;
 356       enum tree_code comp_code;
 357
 358       /* If OP is used in such a way that we can infer a value
 359          range for it, and we don't find a previous assertion for
 360          it, create a new assertion location node for OP.  */
 361       if (infer_value_range (stmt, op, &comp_code, &value))
 362         {
 363           /* If we are able to infer a nonzero value range for OP,
 364              then walk backwards through the use-def chain to see if OP
 365              was set via a typecast.
 366              If so, then we can also infer a nonzero value range
 367              for the operand of the NOP_EXPR.  */
 368           if (comp_code == NE_EXPR && integer_zerop (value))
 369             {
 370               tree t = op;
 371               gimple *def_stmt = SSA_NAME_DEF_STMT (t);
 372               while (is_gimple_assign (def_stmt)
 373                      && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 374                      && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
 375                      && POINTER_TYPE_P
 376                           (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
 377                 {
 378                   t = gimple_assign_rhs1 (def_stmt);
 379                   def_stmt = SSA_NAME_DEF_STMT (t);
 380
 381                   /* Add VR when (T COMP_CODE value) condition is true.  */
 382                   value_range *op_range
 383                     = try_find_new_range (t, t, comp_code, value);
 384                   if (op_range)
 385                     push_value_range (t, op_range);
 386                 }
 387             }
 388           /* Add VR when (OP COMP_CODE value) condition is true.  */
 389           value_range *op_range = try_find_new_range (op, op,
 390                                                       comp_code, value);
 391           if (op_range)
 392             push_value_range (op, op_range);
 393         }
 394     }
 395 }
 396
 397 edge
 398 evrp_dom_walker::before_dom_children (basic_block bb)
 399 {
 400   if (dump_file && (dump_flags & TDF_DETAILS))
 401     fprintf (dump_file, "Visiting BB%d\n", bb->index);
 402
 403   evrp_range_analyzer.enter (bb);
 404
 405   for (gphi_iterator gpi = gsi_start_phis (bb);
 406        !gsi_end_p (gpi); gsi_next (&gpi))
 407     {
 408       gphi *phi = gpi.phi ();
 409       tree lhs = PHI_RESULT (phi);
 410       if (virtual_operand_p (lhs))
 411         continue;
 412
 413       /* Mark PHIs whose lhs we fully propagate for removal.  */
 414       tree val = op_with_constant_singleton_value_range (lhs);
 415       if (val && may_propagate_copy (lhs, val))
 416         {
 417           stmts_to_remove.safe_push (phi);
 418           continue;
 419         }
 420     }
 421
 422   edge taken_edge = NULL;
 423
 424   /* Visit all other stmts and discover any new VRs possible.  */
 425   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 426        !gsi_end_p (gsi); gsi_next (&gsi))
 427     {
 428       gimple *stmt = gsi_stmt (gsi);
 429       tree output = NULL_TREE;
 430       gimple *old_stmt = stmt;
 431       bool was_noreturn = (is_gimple_call (stmt)
 432                            && gimple_call_noreturn_p (stmt));
 433
 434       if (dump_file && (dump_flags & TDF_DETAILS))
 435         {
 436           fprintf (dump_file, "Visiting stmt ");
 437           print_gimple_stmt (dump_file, stmt, 0);
 438         }
 439
 440       evrp_range_analyzer.record_ranges_from_stmt (stmt);
 441
 442       if (gcond *cond = dyn_cast <gcond *> (stmt))
 443         {
 444           vrp_visit_cond_stmt (cond, &taken_edge);
 445           if (taken_edge)
 446             {
 447               if (taken_edge->flags & EDGE_TRUE_VALUE)
 448                 gimple_cond_make_true (cond);
 449               else if (taken_edge->flags & EDGE_FALSE_VALUE)
 450                 gimple_cond_make_false (cond);
 451               else
 452                 gcc_unreachable ();
 453               update_stmt (stmt);
 454             }
 455         }
 456       else if (stmt_interesting_for_vrp (stmt))
 457         {
 458           value_range vr = VR_INITIALIZER;
 459           output = get_output_for_vrp (stmt);
 460           if (output)
 461             {
 462               tree val;
 463               vr = *get_value_range (output);
 464
 465               /* Mark stmts whose output we fully propagate for removal.  */
 466               if ((vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
 467                   && (val = op_with_constant_singleton_value_range (output))
 468                   && may_propagate_copy (output, val)
 469                   && !stmt_could_throw_p (stmt)
 470                   && !gimple_has_side_effects (stmt))
 471                 {
 472                   stmts_to_remove.safe_push (stmt);
 473                   continue;
 474                 }
 475             }
 476         }
 477
 478       /* Try folding stmts with the VR discovered.  */
 479       class evrp_folder evrp_folder;
 480       evrp_folder.vr_values = &evrp_range_analyzer.vr_values;
 481       bool did_replace = evrp_folder.replace_uses_in (stmt);
 482       if (fold_stmt (&gsi, follow_single_use_edges)
 483           || did_replace)
 484         {
 485           stmt = gsi_stmt (gsi);
 486           update_stmt (stmt);
 487           did_replace = true;
 488         }
 489
 490       if (did_replace)
 491         {
 492           /* If we cleaned up EH information from the statement,
 493              remove EH edges.  */
 494           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
 495             bitmap_set_bit (need_eh_cleanup, bb->index);
 496
 497           /* If we turned a not noreturn call into a noreturn one
 498              schedule it for fixup.  */
 499           if (!was_noreturn
 500               && is_gimple_call (stmt)
 501               && gimple_call_noreturn_p (stmt))
 502             stmts_to_fixup.safe_push (stmt);
 503
 504           if (gimple_assign_single_p (stmt))
 505             {
 506               tree rhs = gimple_assign_rhs1 (stmt);
 507               if (TREE_CODE (rhs) == ADDR_EXPR)
 508                 recompute_tree_invariant_for_addr_expr (rhs);
 509             }
 510         }
 511     }
 512
 513   /* Visit BB successor PHI nodes and replace PHI args.  */
 514   edge e;
 515   edge_iterator ei;
 516   FOR_EACH_EDGE (e, ei, bb->succs)
 517     {
 518       for (gphi_iterator gpi = gsi_start_phis (e->dest);
 519            !gsi_end_p (gpi); gsi_next (&gpi))
 520         {
 521           gphi *phi = gpi.phi ();
 522           use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
 523           tree arg = USE_FROM_PTR (use_p);
 524           if (TREE_CODE (arg) != SSA_NAME
 525               || virtual_operand_p (arg))
 526             continue;
 527           tree val = op_with_constant_singleton_value_range (arg);
 528           if (val && may_propagate_copy (arg, val))
 529             propagate_value (use_p, val);
 530         }
 531     }
 532
 533   bb->flags |= BB_VISITED;
 534
 535   return taken_edge;
 536 }
 537
 538 void
 539 evrp_dom_walker::after_dom_children (basic_block bb)
 540 {
 541   evrp_range_analyzer.leave (bb);
 542 }
 543
 544 /* Restore/pop VRs valid only for BB when we leave BB.  */
 545
 546 void
 547 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
 548 {
 549   gcc_checking_assert (!stack.is_empty ());
 550   while (stack.last ().first != NULL_TREE)
 551     pop_value_range (stack.last ().first);
 552   stack.pop ();
 553 }
 554
 555 /* Push the Value Range of VAR to the stack and update it with new VR.  */
 556
 557 void
 558 evrp_range_analyzer::push_value_range (tree var, value_range *vr)
 559 {
 560   if (dump_file && (dump_flags & TDF_DETAILS))
 561     {
 562       fprintf (dump_file, "pushing new range for ");
 563       print_generic_expr (dump_file, var);
 564       fprintf (dump_file, ": ");
 565       dump_value_range (dump_file, vr);
 566       fprintf (dump_file, "\n");
 567     }
 568   stack.safe_push (std::make_pair (var, get_value_range (var)));
 569   set_vr_value (var, vr);
 570 }
 571
 572 /* Pop the Value Range from the vrp_stack and update VAR with it.  */
 573
 574 value_range *
 575 evrp_range_analyzer::pop_value_range (tree var)
 576 {
 577   value_range *vr = stack.last ().second;
 578   gcc_checking_assert (var == stack.last ().first);
 579   if (dump_file && (dump_flags & TDF_DETAILS))
 580     {
 581       fprintf (dump_file, "popping range for ");
 582       print_generic_expr (dump_file, var);
 583       fprintf (dump_file, ", restoring ");
 584       dump_value_range (dump_file, vr);
 585       fprintf (dump_file, "\n");
 586     }
 587   set_vr_value (var, vr);
 588   stack.pop ();
 589   return vr;
 590 }
 591
 592 /* Perform any cleanups after the main phase of EVRP has completed.  */
 593
 594 void
 595 evrp_dom_walker::cleanup (void)
 596 {
 597   if (dump_file)
 598     {
 599       fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
 600       evrp_range_analyzer.vr_values.dump_all_value_ranges (dump_file);
 601       fprintf (dump_file, "\n");
 602     }
 603
 604   /* Remove stmts in reverse order to make debug stmt creation possible.  */
 605   while (! stmts_to_remove.is_empty ())
 606     {
 607       gimple *stmt = stmts_to_remove.pop ();
 608       if (dump_file && dump_flags & TDF_DETAILS)
 609         {
 610           fprintf (dump_file, "Removing dead stmt ");
 611           print_gimple_stmt (dump_file, stmt, 0);
 612           fprintf (dump_file, "\n");
 613         }
 614       gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 615       if (gimple_code (stmt) == GIMPLE_PHI)
 616         remove_phi_node (&gsi, true);
 617       else
 618         {
 619           unlink_stmt_vdef (stmt);
 620           gsi_remove (&gsi, true);
 621           release_defs (stmt);
 622         }
 623     }
 624
 625   if (!bitmap_empty_p (need_eh_cleanup))
 626     gimple_purge_all_dead_eh_edges (need_eh_cleanup);
 627
 628   /* Fixup stmts that became noreturn calls.  This may require splitting
 629      blocks and thus isn't possible during the dominator walk.  Do this
 630      in reverse order so we don't inadvertedly remove a stmt we want to
 631      fixup by visiting a dominating now noreturn call first.  */
 632   while (!stmts_to_fixup.is_empty ())
 633     {
 634       gimple *stmt = stmts_to_fixup.pop ();
 635       fixup_noreturn_call (stmt);
 636     }
 637 }
 638
 639 /* Main entry point for the early vrp pass which is a simplified non-iterative
 640    version of vrp where basic blocks are visited in dominance order.  Value
 641    ranges discovered in early vrp will also be used by ipa-vrp.  */
 642
 643 static unsigned int
 644 execute_early_vrp ()
 645 {
 646   /* Ideally this setup code would move into the ctor for the dominator
 647      walk.  However, this setup can change the number of blocks which
 648      invalidates the internal arrays that are set up by the dominator
 649      walker.  */
 650   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 651   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 652   scev_initialize ();
 653   calculate_dominance_info (CDI_DOMINATORS);
 654
 655   /* Walk stmts in dominance order and propagate VRP.  */
 656   evrp_dom_walker walker;
 657   walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
 658   walker.cleanup ();
 659
 660   scev_finalize ();
 661   loop_optimizer_finalize ();
 662   return 0;
 663 }
 664
 665 namespace {
 666
 667 const pass_data pass_data_early_vrp =
 668 {
 669   GIMPLE_PASS, /* type */
 670   "evrp", /* name */
 671   OPTGROUP_NONE, /* optinfo_flags */
 672   TV_TREE_EARLY_VRP, /* tv_id */
 673   PROP_ssa, /* properties_required */
 674   0, /* properties_provided */
 675   0, /* properties_destroyed */
 676   0, /* todo_flags_start */
 677   ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
 678 };
 679
 680 class pass_early_vrp : public gimple_opt_pass
 681 {
 682 public:
 683   pass_early_vrp (gcc::context *ctxt)
 684     : gimple_opt_pass (pass_data_early_vrp, ctxt)
 685     {}
 686
 687   /* opt_pass methods: */
 688   opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
 689   virtual bool gate (function *)
 690     {
 691       return flag_tree_vrp != 0;
 692     }
 693   virtual unsigned int execute (function *)
 694     { return execute_early_vrp (); }
 695
 696 }; // class pass_vrp
 697 } // anon namespace
 698
 699 gimple_opt_pass *
 700 make_pass_early_vrp (gcc::context *ctxt)
 701 {
 702   return new pass_early_vrp (ctxt);
 703 }
 704