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