gcc/gimple-ssa-evrp-analyze.c

   1 /* Support routines for Value Range Propagation (VRP).
   2    Copyright (C) 2005-2018 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 #include "gimple-ssa-evrp-analyze.h"
  44
  45 evrp_range_analyzer::evrp_range_analyzer () : stack (10)
  46 {
  47   edge e;
  48   edge_iterator ei;
  49   basic_block bb;
  50   FOR_EACH_BB_FN (bb, cfun)
  51     {
  52       bb->flags &= ~BB_VISITED;
  53       FOR_EACH_EDGE (e, ei, bb->preds)
  54         e->flags |= EDGE_EXECUTABLE;
  55     }
  56   vr_values = new class vr_values;
  57 }
  58
  59 /* Push an unwinding marker onto the unwinding stack.  */
  60
  61 void
  62 evrp_range_analyzer::push_marker ()
  63 {
  64   stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
  65 }
  66
  67 /* Analyze ranges as we enter basic block BB.  */
  68
  69 void
  70 evrp_range_analyzer::enter (basic_block bb)
  71 {
  72   if (!optimize)
  73     return;
  74   push_marker ();
  75   record_ranges_from_incoming_edge (bb);
  76   record_ranges_from_phis (bb);
  77   bb->flags |= BB_VISITED;
  78 }
  79
  80 /* Find new range for NAME such that (OP CODE LIMIT) is true.  */
  81 value_range *
  82 evrp_range_analyzer::try_find_new_range (tree name,
  83                                     tree op, tree_code code, tree limit)
  84 {
  85   value_range vr;
  86   value_range *old_vr = get_value_range (name);
  87
  88   /* Discover VR when condition is true.  */
  89   vr_values->extract_range_for_var_from_comparison_expr (name, code, op,
  90                                                          limit, &vr);
  91   /* If we found any usable VR, set the VR to ssa_name and create a
  92      PUSH old value in the stack with the old VR.  */
  93   if (!vr.undefined_p () && !vr.varying_p ())
  94     {
  95       if (old_vr->kind () == vr.kind ()
  96           && vrp_operand_equal_p (old_vr->min (), vr.min ())
  97           && vrp_operand_equal_p (old_vr->max (), vr.max ()))
  98         return NULL;
  99       value_range *new_vr = vr_values->allocate_value_range ();
 100       *new_vr = vr;
 101       return new_vr;
 102     }
 103   return NULL;
 104 }
 105
 106 /* For LHS record VR in the SSA info.  */
 107 void
 108 evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr)
 109 {
 110   /* Set the SSA with the value range.  */
 111   if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
 112     {
 113       if (vr->constant_p ())
 114         set_range_info (lhs, vr->kind (),
 115                         wi::to_wide (vr->min ()),
 116                         wi::to_wide (vr->max ()));
 117     }
 118   else if (POINTER_TYPE_P (TREE_TYPE (lhs))
 119            && range_includes_zero_p (vr) == 0)
 120     set_ptr_nonnull (lhs);
 121 }
 122
 123 /* Return true if all uses of NAME are dominated by STMT or feed STMT
 124    via a chain of single immediate uses.  */
 125
 126 static bool
 127 all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt)
 128 {
 129   use_operand_p use_p, use2_p;
 130   imm_use_iterator iter;
 131   basic_block stmt_bb = gimple_bb (stmt);
 132
 133   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
 134     {
 135       gimple *use_stmt = USE_STMT (use_p), *use_stmt2;
 136       if (use_stmt == stmt
 137           || is_gimple_debug (use_stmt)
 138           || (gimple_bb (use_stmt) != stmt_bb
 139               && dominated_by_p (CDI_DOMINATORS,
 140                                  gimple_bb (use_stmt), stmt_bb)))
 141         continue;
 142       while (use_stmt != stmt
 143              && is_gimple_assign (use_stmt)
 144              && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
 145              && single_imm_use (gimple_assign_lhs (use_stmt),
 146                                 &use2_p, &use_stmt2))
 147         use_stmt = use_stmt2;
 148       if (use_stmt != stmt)
 149         return false;
 150     }
 151   return true;
 152 }
 153
 154 void
 155 evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb)
 156 {
 157   edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
 158   if (pred_e)
 159     {
 160       gimple *stmt = last_stmt (pred_e->src);
 161       tree op0 = NULL_TREE;
 162
 163       if (stmt
 164           && gimple_code (stmt) == GIMPLE_COND
 165           && (op0 = gimple_cond_lhs (stmt))
 166           && TREE_CODE (op0) == SSA_NAME
 167           && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
 168               || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
 169         {
 170           if (dump_file && (dump_flags & TDF_DETAILS))
 171             {
 172               fprintf (dump_file, "Visiting controlling predicate ");
 173               print_gimple_stmt (dump_file, stmt, 0);
 174             }
 175           /* Entering a new scope.  Try to see if we can find a VR
 176              here.  */
 177           tree op1 = gimple_cond_rhs (stmt);
 178           if (TREE_OVERFLOW_P (op1))
 179             op1 = drop_tree_overflow (op1);
 180           tree_code code = gimple_cond_code (stmt);
 181
 182           auto_vec<assert_info, 8> asserts;
 183           register_edge_assert_for (op0, pred_e, code, op0, op1, asserts);
 184           if (TREE_CODE (op1) == SSA_NAME)
 185             register_edge_assert_for (op1, pred_e, code, op0, op1, asserts);
 186
 187           auto_vec<std::pair<tree, value_range *>, 8> vrs;
 188           for (unsigned i = 0; i < asserts.length (); ++i)
 189             {
 190               value_range *vr = try_find_new_range (asserts[i].name,
 191                                                     asserts[i].expr,
 192                                                     asserts[i].comp_code,
 193                                                     asserts[i].val);
 194               if (vr)
 195                 vrs.safe_push (std::make_pair (asserts[i].name, vr));
 196             }
 197
 198           /* If pred_e is really a fallthru we can record value ranges
 199              in SSA names as well.  */
 200           bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e);
 201
 202           /* Push updated ranges only after finding all of them to avoid
 203              ordering issues that can lead to worse ranges.  */
 204           for (unsigned i = 0; i < vrs.length (); ++i)
 205             {
 206               /* But make sure we do not weaken ranges like when
 207                  getting first [64, +INF] and then ~[0, 0] from
 208                  conditions like (s & 0x3cc0) == 0).  */
 209               value_range *old_vr = get_value_range (vrs[i].first);
 210               value_range tem (old_vr->kind (), old_vr->min (), old_vr->max ());
 211               tem.intersect (vrs[i].second);
 212               if (tem.ignore_equivs_equal_p (*old_vr))
 213                 continue;
 214               push_value_range (vrs[i].first, vrs[i].second);
 215               if (is_fallthru
 216                   && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt))
 217                 {
 218                   set_ssa_range_info (vrs[i].first, vrs[i].second);
 219                   maybe_set_nonzero_bits (pred_e, vrs[i].first);
 220                 }
 221             }
 222         }
 223     }
 224 }
 225
 226 void
 227 evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
 228 {
 229   /* Visit PHI stmts and discover any new VRs possible.  */
 230   bool has_unvisited_preds = false;
 231   edge_iterator ei;
 232   edge e;
 233   FOR_EACH_EDGE (e, ei, bb->preds)
 234     if (e->flags & EDGE_EXECUTABLE
 235         && !(e->src->flags & BB_VISITED))
 236       {
 237         has_unvisited_preds = true;
 238         break;
 239       }
 240
 241   for (gphi_iterator gpi = gsi_start_phis (bb);
 242        !gsi_end_p (gpi); gsi_next (&gpi))
 243     {
 244       gphi *phi = gpi.phi ();
 245       tree lhs = PHI_RESULT (phi);
 246       if (virtual_operand_p (lhs))
 247         continue;
 248
 249       value_range vr_result;
 250       bool interesting = stmt_interesting_for_vrp (phi);
 251       if (!has_unvisited_preds && interesting)
 252         vr_values->extract_range_from_phi_node (phi, &vr_result);
 253       else
 254         {
 255           set_value_range_to_varying (&vr_result);
 256           /* When we have an unvisited executable predecessor we can't
 257              use PHI arg ranges which may be still UNDEFINED but have
 258              to use VARYING for them.  But we can still resort to
 259              SCEV for loop header PHIs.  */
 260           struct loop *l;
 261           if (scev_initialized_p ()
 262               && interesting
 263               && (l = loop_containing_stmt (phi))
 264               && l->header == gimple_bb (phi))
 265           vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
 266         }
 267       vr_values->update_value_range (lhs, &vr_result);
 268
 269       /* Set the SSA with the value range.  */
 270       set_ssa_range_info (lhs, &vr_result);
 271     }
 272 }
 273
 274 /* Record ranges from STMT into our VR_VALUES class.  If TEMPORARY is
 275    true, then this is a temporary equivalence and should be recorded
 276    into the unwind table.  Othewise record the equivalence into the
 277    global table.  */
 278
 279 void
 280 evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary)
 281 {
 282   tree output = NULL_TREE;
 283
 284   if (!optimize)
 285     return;
 286
 287   if (dyn_cast <gcond *> (stmt))
 288     ;
 289   else if (stmt_interesting_for_vrp (stmt))
 290     {
 291       edge taken_edge;
 292       value_range vr;
 293       vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
 294       if (output)
 295         {
 296           /* Set the SSA with the value range.  There are two cases to
 297              consider.  First (the the most common) is we are processing
 298              STMT in a context where its resulting range globally holds
 299              and thus it can be reflected into the global ranges and need
 300              not be unwound as we leave scope.
 301
 302              The second case occurs if we are processing a statement in
 303              a context where the resulting range must not be reflected
 304              into the global tables and must be unwound as we leave
 305              the current context.  This happens in jump threading for
 306              example.  */
 307           if (!temporary)
 308             {
 309               /* Case one.  We can just update the underlying range
 310                  information as well as the global information.  */
 311               vr_values->update_value_range (output, &vr);
 312               set_ssa_range_info (output, &vr);
 313             }
 314           else
 315             {
 316               /* We're going to need to unwind this range.  We can
 317                  not use VR as that's a stack object.  We have to allocate
 318                  a new range and push the old range onto the stack.  We
 319                  also have to be very careful about sharing the underlying
 320                  bitmaps.  Ugh.  */
 321               value_range *new_vr = vr_values->allocate_value_range ();
 322               *new_vr = vr;
 323               new_vr->equiv_clear ();
 324               push_value_range (output, new_vr);
 325             }
 326         }
 327       else
 328         vr_values->set_defs_to_varying (stmt);
 329     }
 330   else
 331     vr_values->set_defs_to_varying (stmt);
 332
 333   /* See if we can derive a range for any of STMT's operands.  */
 334   tree op;
 335   ssa_op_iter i;
 336   FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
 337     {
 338       tree value;
 339       enum tree_code comp_code;
 340
 341       /* If OP is used in such a way that we can infer a value
 342          range for it, and we don't find a previous assertion for
 343          it, create a new assertion location node for OP.  */
 344       if (infer_value_range (stmt, op, &comp_code, &value))
 345         {
 346           /* If we are able to infer a nonzero value range for OP,
 347              then walk backwards through the use-def chain to see if OP
 348              was set via a typecast.
 349              If so, then we can also infer a nonzero value range
 350              for the operand of the NOP_EXPR.  */
 351           if (comp_code == NE_EXPR && integer_zerop (value))
 352             {
 353               tree t = op;
 354               gimple *def_stmt = SSA_NAME_DEF_STMT (t);
 355               while (is_gimple_assign (def_stmt)
 356                      && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 357                      && TREE_CODE
 358                           (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
 359                      && POINTER_TYPE_P
 360                           (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
 361                 {
 362                   t = gimple_assign_rhs1 (def_stmt);
 363                   def_stmt = SSA_NAME_DEF_STMT (t);
 364
 365                   /* Add VR when (T COMP_CODE value) condition is
 366                      true.  */
 367                   value_range *op_range
 368                     = try_find_new_range (t, t, comp_code, value);
 369                   if (op_range)
 370                     push_value_range (t, op_range);
 371                 }
 372             }
 373           /* Add VR when (OP COMP_CODE value) condition is true.  */
 374           value_range *op_range = try_find_new_range (op, op,
 375                                                       comp_code, value);
 376           if (op_range)
 377             push_value_range (op, op_range);
 378         }
 379     }
 380 }
 381
 382 /* Unwind recorded ranges to their most recent state.  */
 383
 384 void
 385 evrp_range_analyzer::pop_to_marker (void)
 386 {
 387   gcc_checking_assert (!stack.is_empty ());
 388   while (stack.last ().first != NULL_TREE)
 389     pop_value_range (stack.last ().first);
 390   stack.pop ();
 391 }
 392
 393 /* Restore/pop VRs valid only for BB when we leave BB.  */
 394
 395 void
 396 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
 397 {
 398   if (!optimize)
 399     return;
 400   pop_to_marker ();
 401 }
 402
 403
 404 /* Push the Value Range of VAR to the stack and update it with new VR.  */
 405
 406 void
 407 evrp_range_analyzer::push_value_range (tree var, value_range *vr)
 408 {
 409   if (dump_file && (dump_flags & TDF_DETAILS))
 410     {
 411       fprintf (dump_file, "pushing new range for ");
 412       print_generic_expr (dump_file, var);
 413       fprintf (dump_file, ": ");
 414       dump_value_range (dump_file, vr);
 415       fprintf (dump_file, "\n");
 416     }
 417   stack.safe_push (std::make_pair (var, get_value_range (var)));
 418   vr_values->set_vr_value (var, vr);
 419 }
 420
 421 /* Pop the Value Range from the vrp_stack and update VAR with it.  */
 422
 423 value_range *
 424 evrp_range_analyzer::pop_value_range (tree var)
 425 {
 426   value_range *vr = stack.last ().second;
 427   gcc_checking_assert (var == stack.last ().first);
 428   if (dump_file && (dump_flags & TDF_DETAILS))
 429     {
 430       fprintf (dump_file, "popping range for ");
 431       print_generic_expr (dump_file, var);
 432       fprintf (dump_file, ", restoring ");
 433       dump_value_range (dump_file, vr);
 434       fprintf (dump_file, "\n");
 435     }
 436   vr_values->set_vr_value (var, vr);
 437   stack.pop ();
 438   return vr;
 439 }