gcc/gimple-ssa-evrp-analyze.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 #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 void
  60 evrp_range_analyzer::enter (basic_block bb)
  61 {
  62   stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
  63   record_ranges_from_incoming_edge (bb);
  64   record_ranges_from_phis (bb);
  65   bb->flags |= BB_VISITED;
  66 }
  67
  68 /* Find new range for NAME such that (OP CODE LIMIT) is true.  */
  69 value_range *
  70 evrp_range_analyzer::try_find_new_range (tree name,
  71                                     tree op, tree_code code, tree limit)
  72 {
  73   value_range vr = VR_INITIALIZER;
  74   value_range *old_vr = get_value_range (name);
  75
  76   /* Discover VR when condition is true.  */
  77   vr_values->extract_range_for_var_from_comparison_expr (name, code, op,
  78                                                          limit, &vr);
  79   /* If we found any usable VR, set the VR to ssa_name and create a
  80      PUSH old value in the stack with the old VR.  */
  81   if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
  82     {
  83       if (old_vr->type == vr.type
  84           && vrp_operand_equal_p (old_vr->min, vr.min)
  85           && vrp_operand_equal_p (old_vr->max, vr.max))
  86         return NULL;
  87       value_range *new_vr = vr_values->allocate_value_range ();
  88       *new_vr = vr;
  89       return new_vr;
  90     }
  91   return NULL;
  92 }
  93
  94 /* For LHS record VR in the SSA info.  */
  95 void
  96 evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr)
  97 {
  98   /* Set the SSA with the value range.  */
  99   if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
 100     {
 101       if ((vr->type == VR_RANGE
 102            || vr->type == VR_ANTI_RANGE)
 103           && (TREE_CODE (vr->min) == INTEGER_CST)
 104           && (TREE_CODE (vr->max) == INTEGER_CST))
 105         set_range_info (lhs, vr->type,
 106                         wi::to_wide (vr->min),
 107                         wi::to_wide (vr->max));
 108     }
 109   else if (POINTER_TYPE_P (TREE_TYPE (lhs))
 110            && ((vr->type == VR_RANGE
 111                 && range_includes_zero_p (vr->min,
 112                                           vr->max) == 0)
 113                || (vr->type == VR_ANTI_RANGE
 114                    && range_includes_zero_p (vr->min,
 115                                              vr->max) == 1)))
 116     set_ptr_nonnull (lhs);
 117 }
 118
 119 /* Return true if all uses of NAME are dominated by STMT or feed STMT
 120    via a chain of single immediate uses.  */
 121
 122 static bool
 123 all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt)
 124 {
 125   use_operand_p use_p, use2_p;
 126   imm_use_iterator iter;
 127   basic_block stmt_bb = gimple_bb (stmt);
 128
 129   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
 130     {
 131       gimple *use_stmt = USE_STMT (use_p), *use_stmt2;
 132       if (use_stmt == stmt
 133           || is_gimple_debug (use_stmt)
 134           || (gimple_bb (use_stmt) != stmt_bb
 135               && dominated_by_p (CDI_DOMINATORS,
 136                                  gimple_bb (use_stmt), stmt_bb)))
 137         continue;
 138       while (use_stmt != stmt
 139              && is_gimple_assign (use_stmt)
 140              && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
 141              && single_imm_use (gimple_assign_lhs (use_stmt),
 142                                 &use2_p, &use_stmt2))
 143         use_stmt = use_stmt2;
 144       if (use_stmt != stmt)
 145         return false;
 146     }
 147   return true;
 148 }
 149
 150 void
 151 evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb)
 152 {
 153   edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
 154   if (pred_e)
 155     {
 156       gimple *stmt = last_stmt (pred_e->src);
 157       tree op0 = NULL_TREE;
 158
 159       if (stmt
 160           && gimple_code (stmt) == GIMPLE_COND
 161           && (op0 = gimple_cond_lhs (stmt))
 162           && TREE_CODE (op0) == SSA_NAME
 163           && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
 164               || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
 165         {
 166           if (dump_file && (dump_flags & TDF_DETAILS))
 167             {
 168               fprintf (dump_file, "Visiting controlling predicate ");
 169               print_gimple_stmt (dump_file, stmt, 0);
 170             }
 171           /* Entering a new scope.  Try to see if we can find a VR
 172              here.  */
 173           tree op1 = gimple_cond_rhs (stmt);
 174           if (TREE_OVERFLOW_P (op1))
 175             op1 = drop_tree_overflow (op1);
 176           tree_code code = gimple_cond_code (stmt);
 177
 178           auto_vec<assert_info, 8> asserts;
 179           register_edge_assert_for (op0, pred_e, code, op0, op1, asserts);
 180           if (TREE_CODE (op1) == SSA_NAME)
 181             register_edge_assert_for (op1, pred_e, code, op0, op1, asserts);
 182
 183           auto_vec<std::pair<tree, value_range *>, 8> vrs;
 184           for (unsigned i = 0; i < asserts.length (); ++i)
 185             {
 186               value_range *vr = try_find_new_range (asserts[i].name,
 187                                                     asserts[i].expr,
 188                                                     asserts[i].comp_code,
 189                                                     asserts[i].val);
 190               if (vr)
 191                 vrs.safe_push (std::make_pair (asserts[i].name, vr));
 192             }
 193
 194           /* If pred_e is really a fallthru we can record value ranges
 195              in SSA names as well.  */
 196           bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e);
 197
 198           /* Push updated ranges only after finding all of them to avoid
 199              ordering issues that can lead to worse ranges.  */
 200           for (unsigned i = 0; i < vrs.length (); ++i)
 201             {
 202               push_value_range (vrs[i].first, vrs[i].second);
 203               if (is_fallthru
 204                   && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt))
 205                 {
 206                   set_ssa_range_info (vrs[i].first, vrs[i].second);
 207                   maybe_set_nonzero_bits (pred_e, vrs[i].first);
 208                 }
 209             }
 210         }
 211     }
 212 }
 213
 214 void
 215 evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
 216 {
 217   /* Visit PHI stmts and discover any new VRs possible.  */
 218   bool has_unvisited_preds = false;
 219   edge_iterator ei;
 220   edge e;
 221   FOR_EACH_EDGE (e, ei, bb->preds)
 222     if (e->flags & EDGE_EXECUTABLE
 223         && !(e->src->flags & BB_VISITED))
 224       {
 225         has_unvisited_preds = true;
 226         break;
 227       }
 228
 229   for (gphi_iterator gpi = gsi_start_phis (bb);
 230        !gsi_end_p (gpi); gsi_next (&gpi))
 231     {
 232       gphi *phi = gpi.phi ();
 233       tree lhs = PHI_RESULT (phi);
 234       if (virtual_operand_p (lhs))
 235         continue;
 236
 237       value_range vr_result = VR_INITIALIZER;
 238       bool interesting = stmt_interesting_for_vrp (phi);
 239       if (!has_unvisited_preds && interesting)
 240         vr_values->extract_range_from_phi_node (phi, &vr_result);
 241       else
 242         {
 243           set_value_range_to_varying (&vr_result);
 244           /* When we have an unvisited executable predecessor we can't
 245              use PHI arg ranges which may be still UNDEFINED but have
 246              to use VARYING for them.  But we can still resort to
 247              SCEV for loop header PHIs.  */
 248           struct loop *l;
 249           if (scev_initialized_p ()
 250               && interesting
 251               && (l = loop_containing_stmt (phi))
 252               && l->header == gimple_bb (phi))
 253           vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
 254         }
 255       vr_values->update_value_range (lhs, &vr_result);
 256
 257       /* Set the SSA with the value range.  */
 258       set_ssa_range_info (lhs, &vr_result);
 259     }
 260 }
 261
 262 void
 263 evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt)
 264 {
 265   tree output = NULL_TREE;
 266
 267   if (dyn_cast <gcond *> (stmt))
 268     ;
 269   else if (stmt_interesting_for_vrp (stmt))
 270     {
 271       edge taken_edge;
 272       value_range vr = VR_INITIALIZER;
 273       vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
 274       if (output
 275           && (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE))
 276         {
 277           vr_values->update_value_range (output, &vr);
 278
 279           /* Set the SSA with the value range.  */
 280           set_ssa_range_info (output, &vr);
 281         }
 282       else
 283         vr_values->set_defs_to_varying (stmt);
 284     }
 285   else
 286     vr_values->set_defs_to_varying (stmt);
 287
 288   /* See if we can derive a range for any of STMT's operands.  */
 289   tree op;
 290   ssa_op_iter i;
 291   FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
 292     {
 293       tree value;
 294       enum tree_code comp_code;
 295
 296       /* If OP is used in such a way that we can infer a value
 297          range for it, and we don't find a previous assertion for
 298          it, create a new assertion location node for OP.  */
 299       if (infer_value_range (stmt, op, &comp_code, &value))
 300         {
 301           /* If we are able to infer a nonzero value range for OP,
 302              then walk backwards through the use-def chain to see if OP
 303              was set via a typecast.
 304              If so, then we can also infer a nonzero value range
 305              for the operand of the NOP_EXPR.  */
 306           if (comp_code == NE_EXPR && integer_zerop (value))
 307             {
 308               tree t = op;
 309               gimple *def_stmt = SSA_NAME_DEF_STMT (t);
 310               while (is_gimple_assign (def_stmt)
 311                      && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 312                      && TREE_CODE
 313                           (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
 314                      && POINTER_TYPE_P
 315                           (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
 316                 {
 317                   t = gimple_assign_rhs1 (def_stmt);
 318                   def_stmt = SSA_NAME_DEF_STMT (t);
 319
 320                   /* Add VR when (T COMP_CODE value) condition is
 321                      true.  */
 322                   value_range *op_range
 323                     = try_find_new_range (t, t, comp_code, value);
 324                   if (op_range)
 325                     push_value_range (t, op_range);
 326                 }
 327             }
 328           /* Add VR when (OP COMP_CODE value) condition is true.  */
 329           value_range *op_range = try_find_new_range (op, op,
 330                                                       comp_code, value);
 331           if (op_range)
 332             push_value_range (op, op_range);
 333         }
 334     }
 335 }
 336
 337 /* Restore/pop VRs valid only for BB when we leave BB.  */
 338
 339 void
 340 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
 341 {
 342   gcc_checking_assert (!stack.is_empty ());
 343   while (stack.last ().first != NULL_TREE)
 344     pop_value_range (stack.last ().first);
 345   stack.pop ();
 346 }
 347
 348 /* Push the Value Range of VAR to the stack and update it with new VR.  */
 349
 350 void
 351 evrp_range_analyzer::push_value_range (tree var, value_range *vr)
 352 {
 353   if (dump_file && (dump_flags & TDF_DETAILS))
 354     {
 355       fprintf (dump_file, "pushing new range for ");
 356       print_generic_expr (dump_file, var);
 357       fprintf (dump_file, ": ");
 358       dump_value_range (dump_file, vr);
 359       fprintf (dump_file, "\n");
 360     }
 361   stack.safe_push (std::make_pair (var, get_value_range (var)));
 362   vr_values->set_vr_value (var, vr);
 363 }
 364
 365 /* Pop the Value Range from the vrp_stack and update VAR with it.  */
 366
 367 value_range *
 368 evrp_range_analyzer::pop_value_range (tree var)
 369 {
 370   value_range *vr = stack.last ().second;
 371   gcc_checking_assert (var == stack.last ().first);
 372   if (dump_file && (dump_flags & TDF_DETAILS))
 373     {
 374       fprintf (dump_file, "popping range for ");
 375       print_generic_expr (dump_file, var);
 376       fprintf (dump_file, ", restoring ");
 377       dump_value_range (dump_file, vr);
 378       fprintf (dump_file, "\n");
 379     }
 380   vr_values->set_vr_value (var, vr);
 381   stack.pop ();
 382   return vr;
 383 }