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