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 = VR_INITIALIZER;
  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.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
  94     {
  95       if (old_vr->type == vr.type
  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->type == VR_RANGE
 114            || vr->type == VR_ANTI_RANGE)
 115           && (TREE_CODE (vr->min) == INTEGER_CST)
 116           && (TREE_CODE (vr->max) == INTEGER_CST))
 117         set_range_info (lhs, vr->type,
 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               push_value_range (vrs[i].first, vrs[i].second);
 210               if (is_fallthru
 211                   && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt))
 212                 {
 213                   set_ssa_range_info (vrs[i].first, vrs[i].second);
 214                   maybe_set_nonzero_bits (pred_e, vrs[i].first);
 215                 }
 216             }
 217         }
 218     }
 219 }
 220
 221 void
 222 evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
 223 {
 224   /* Visit PHI stmts and discover any new VRs possible.  */
 225   bool has_unvisited_preds = false;
 226   edge_iterator ei;
 227   edge e;
 228   FOR_EACH_EDGE (e, ei, bb->preds)
 229     if (e->flags & EDGE_EXECUTABLE
 230         && !(e->src->flags & BB_VISITED))
 231       {
 232         has_unvisited_preds = true;
 233         break;
 234       }
 235
 236   for (gphi_iterator gpi = gsi_start_phis (bb);
 237        !gsi_end_p (gpi); gsi_next (&gpi))
 238     {
 239       gphi *phi = gpi.phi ();
 240       tree lhs = PHI_RESULT (phi);
 241       if (virtual_operand_p (lhs))
 242         continue;
 243
 244       value_range vr_result = VR_INITIALIZER;
 245       bool interesting = stmt_interesting_for_vrp (phi);
 246       if (!has_unvisited_preds && interesting)
 247         vr_values->extract_range_from_phi_node (phi, &vr_result);
 248       else
 249         {
 250           set_value_range_to_varying (&vr_result);
 251           /* When we have an unvisited executable predecessor we can't
 252              use PHI arg ranges which may be still UNDEFINED but have
 253              to use VARYING for them.  But we can still resort to
 254              SCEV for loop header PHIs.  */
 255           struct loop *l;
 256           if (scev_initialized_p ()
 257               && interesting
 258               && (l = loop_containing_stmt (phi))
 259               && l->header == gimple_bb (phi))
 260           vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
 261         }
 262       vr_values->update_value_range (lhs, &vr_result);
 263
 264       /* Set the SSA with the value range.  */
 265       set_ssa_range_info (lhs, &vr_result);
 266     }
 267 }
 268
 269 /* Record ranges from STMT into our VR_VALUES class.  If TEMPORARY is
 270    true, then this is a temporary equivalence and should be recorded
 271    into the unwind table.  Othewise record the equivalence into the
 272    global table.  */
 273
 274 void
 275 evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary)
 276 {
 277   tree output = NULL_TREE;
 278
 279   if (!optimize)
 280     return;
 281
 282   if (dyn_cast <gcond *> (stmt))
 283     ;
 284   else if (stmt_interesting_for_vrp (stmt))
 285     {
 286       edge taken_edge;
 287       value_range vr = VR_INITIALIZER;
 288       vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
 289       if (output)
 290         {
 291           /* Set the SSA with the value range.  There are two cases to
 292              consider.  First (the the most common) is we are processing
 293              STMT in a context where its resulting range globally holds
 294              and thus it can be reflected into the global ranges and need
 295              not be unwound as we leave scope.
 296
 297              The second case occurs if we are processing a statement in
 298              a context where the resulting range must not be reflected
 299              into the global tables and must be unwound as we leave
 300              the current context.  This happens in jump threading for
 301              example.  */
 302           if (!temporary)
 303             {
 304               /* Case one.  We can just update the underlying range
 305                  information as well as the global information.  */
 306               vr_values->update_value_range (output, &vr);
 307               set_ssa_range_info (output, &vr);
 308             }
 309           else
 310             {
 311               /* We're going to need to unwind this range.  We can
 312                  not use VR as that's a stack object.  We have to allocate
 313                  a new range and push the old range onto the stack.  We
 314                  also have to be very careful about sharing the underlying
 315                  bitmaps.  Ugh.  */
 316               value_range *new_vr = vr_values->allocate_value_range ();
 317               *new_vr = vr;
 318               new_vr->equiv = NULL;
 319               push_value_range (output, new_vr);
 320             }
 321         }
 322       else
 323         vr_values->set_defs_to_varying (stmt);
 324     }
 325   else
 326     vr_values->set_defs_to_varying (stmt);
 327
 328   /* See if we can derive a range for any of STMT's operands.  */
 329   tree op;
 330   ssa_op_iter i;
 331   FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
 332     {
 333       tree value;
 334       enum tree_code comp_code;
 335
 336       /* If OP is used in such a way that we can infer a value
 337          range for it, and we don't find a previous assertion for
 338          it, create a new assertion location node for OP.  */
 339       if (infer_value_range (stmt, op, &comp_code, &value))
 340         {
 341           /* If we are able to infer a nonzero value range for OP,
 342              then walk backwards through the use-def chain to see if OP
 343              was set via a typecast.
 344              If so, then we can also infer a nonzero value range
 345              for the operand of the NOP_EXPR.  */
 346           if (comp_code == NE_EXPR && integer_zerop (value))
 347             {
 348               tree t = op;
 349               gimple *def_stmt = SSA_NAME_DEF_STMT (t);
 350               while (is_gimple_assign (def_stmt)
 351                      && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 352                      && TREE_CODE
 353                           (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
 354                      && POINTER_TYPE_P
 355                           (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
 356                 {
 357                   t = gimple_assign_rhs1 (def_stmt);
 358                   def_stmt = SSA_NAME_DEF_STMT (t);
 359
 360                   /* Add VR when (T COMP_CODE value) condition is
 361                      true.  */
 362                   value_range *op_range
 363                     = try_find_new_range (t, t, comp_code, value);
 364                   if (op_range)
 365                     push_value_range (t, op_range);
 366                 }
 367             }
 368           /* Add VR when (OP COMP_CODE value) condition is true.  */
 369           value_range *op_range = try_find_new_range (op, op,
 370                                                       comp_code, value);
 371           if (op_range)
 372             push_value_range (op, op_range);
 373         }
 374     }
 375 }
 376
 377 /* Unwind recorded ranges to their most recent state.  */
 378
 379 void
 380 evrp_range_analyzer::pop_to_marker (void)
 381 {
 382   gcc_checking_assert (!stack.is_empty ());
 383   while (stack.last ().first != NULL_TREE)
 384     pop_value_range (stack.last ().first);
 385   stack.pop ();
 386 }
 387
 388 /* Restore/pop VRs valid only for BB when we leave BB.  */
 389
 390 void
 391 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
 392 {
 393   if (!optimize)
 394     return;
 395   pop_to_marker ();
 396 }
 397
 398
 399 /* Push the Value Range of VAR to the stack and update it with new VR.  */
 400
 401 void
 402 evrp_range_analyzer::push_value_range (tree var, value_range *vr)
 403 {
 404   if (dump_file && (dump_flags & TDF_DETAILS))
 405     {
 406       fprintf (dump_file, "pushing new range for ");
 407       print_generic_expr (dump_file, var);
 408       fprintf (dump_file, ": ");
 409       dump_value_range (dump_file, vr);
 410       fprintf (dump_file, "\n");
 411     }
 412   stack.safe_push (std::make_pair (var, get_value_range (var)));
 413   vr_values->set_vr_value (var, vr);
 414 }
 415
 416 /* Pop the Value Range from the vrp_stack and update VAR with it.  */
 417
 418 value_range *
 419 evrp_range_analyzer::pop_value_range (tree var)
 420 {
 421   value_range *vr = stack.last ().second;
 422   gcc_checking_assert (var == stack.last ().first);
 423   if (dump_file && (dump_flags & TDF_DETAILS))
 424     {
 425       fprintf (dump_file, "popping range for ");
 426       print_generic_expr (dump_file, var);
 427       fprintf (dump_file, ", restoring ");
 428       dump_value_range (dump_file, vr);
 429       fprintf (dump_file, "\n");
 430     }
 431   vr_values->set_vr_value (var, vr);
 432   stack.pop ();
 433   return vr;
 434 }