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         {
 276           vr_values->update_value_range (output, &vr);
 277
 278           /* Set the SSA with the value range.  */
 279           set_ssa_range_info (output, &vr);
 280         }
 281       else
 282         vr_values->set_defs_to_varying (stmt);
 283     }
 284   else
 285     vr_values->set_defs_to_varying (stmt);
 286
 287   /* See if we can derive a range for any of STMT's operands.  */
 288   tree op;
 289   ssa_op_iter i;
 290   FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
 291     {
 292       tree value;
 293       enum tree_code comp_code;
 294
 295       /* If OP is used in such a way that we can infer a value
 296          range for it, and we don't find a previous assertion for
 297          it, create a new assertion location node for OP.  */
 298       if (infer_value_range (stmt, op, &comp_code, &value))
 299         {
 300           /* If we are able to infer a nonzero value range for OP,
 301              then walk backwards through the use-def chain to see if OP
 302              was set via a typecast.
 303              If so, then we can also infer a nonzero value range
 304              for the operand of the NOP_EXPR.  */
 305           if (comp_code == NE_EXPR && integer_zerop (value))
 306             {
 307               tree t = op;
 308               gimple *def_stmt = SSA_NAME_DEF_STMT (t);
 309               while (is_gimple_assign (def_stmt)
 310                      && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 311                      && TREE_CODE
 312                           (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
 313                      && POINTER_TYPE_P
 314                           (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
 315                 {
 316                   t = gimple_assign_rhs1 (def_stmt);
 317                   def_stmt = SSA_NAME_DEF_STMT (t);
 318
 319                   /* Add VR when (T COMP_CODE value) condition is
 320                      true.  */
 321                   value_range *op_range
 322                     = try_find_new_range (t, t, comp_code, value);
 323                   if (op_range)
 324                     push_value_range (t, op_range);
 325                 }
 326             }
 327           /* Add VR when (OP COMP_CODE value) condition is true.  */
 328           value_range *op_range = try_find_new_range (op, op,
 329                                                       comp_code, value);
 330           if (op_range)
 331             push_value_range (op, op_range);
 332         }
 333     }
 334 }
 335
 336 /* Restore/pop VRs valid only for BB when we leave BB.  */
 337
 338 void
 339 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
 340 {
 341   gcc_checking_assert (!stack.is_empty ());
 342   while (stack.last ().first != NULL_TREE)
 343     pop_value_range (stack.last ().first);
 344   stack.pop ();
 345 }
 346
 347 /* Push the Value Range of VAR to the stack and update it with new VR.  */
 348
 349 void
 350 evrp_range_analyzer::push_value_range (tree var, value_range *vr)
 351 {
 352   if (dump_file && (dump_flags & TDF_DETAILS))
 353     {
 354       fprintf (dump_file, "pushing new range for ");
 355       print_generic_expr (dump_file, var);
 356       fprintf (dump_file, ": ");
 357       dump_value_range (dump_file, vr);
 358       fprintf (dump_file, "\n");
 359     }
 360   stack.safe_push (std::make_pair (var, get_value_range (var)));
 361   vr_values->set_vr_value (var, vr);
 362 }
 363
 364 /* Pop the Value Range from the vrp_stack and update VAR with it.  */
 365
 366 value_range *
 367 evrp_range_analyzer::pop_value_range (tree var)
 368 {
 369   value_range *vr = stack.last ().second;
 370   gcc_checking_assert (var == stack.last ().first);
 371   if (dump_file && (dump_flags & TDF_DETAILS))
 372     {
 373       fprintf (dump_file, "popping range for ");
 374       print_generic_expr (dump_file, var);
 375       fprintf (dump_file, ", restoring ");
 376       dump_value_range (dump_file, vr);
 377       fprintf (dump_file, "\n");
 378     }
 379   vr_values->set_vr_value (var, vr);
 380   stack.pop ();
 381   return vr;
 382 }