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 /* 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   push_marker ();
  73   record_ranges_from_incoming_edge (bb);
  74   record_ranges_from_phis (bb);
  75   bb->flags |= BB_VISITED;
  76 }
  77
  78 /* Find new range for NAME such that (OP CODE LIMIT) is true.  */
  79 value_range *
  80 evrp_range_analyzer::try_find_new_range (tree name,
  81                                     tree op, tree_code code, tree limit)
  82 {
  83   value_range vr = VR_INITIALIZER;
  84   value_range *old_vr = get_value_range (name);
  85
  86   /* Discover VR when condition is true.  */
  87   vr_values->extract_range_for_var_from_comparison_expr (name, code, op,
  88                                                          limit, &vr);
  89   /* If we found any usable VR, set the VR to ssa_name and create a
  90      PUSH old value in the stack with the old VR.  */
  91   if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
  92     {
  93       if (old_vr->type == vr.type
  94           && vrp_operand_equal_p (old_vr->min, vr.min)
  95           && vrp_operand_equal_p (old_vr->max, vr.max))
  96         return NULL;
  97       value_range *new_vr = vr_values->allocate_value_range ();
  98       *new_vr = vr;
  99       return new_vr;
 100     }
 101   return NULL;
 102 }
 103
 104 /* For LHS record VR in the SSA info.  */
 105 void
 106 evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr)
 107 {
 108   /* Set the SSA with the value range.  */
 109   if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
 110     {
 111       if ((vr->type == VR_RANGE
 112            || vr->type == VR_ANTI_RANGE)
 113           && (TREE_CODE (vr->min) == INTEGER_CST)
 114           && (TREE_CODE (vr->max) == INTEGER_CST))
 115         set_range_info (lhs, vr->type,
 116                         wi::to_wide (vr->min),
 117                         wi::to_wide (vr->max));
 118     }
 119   else if (POINTER_TYPE_P (TREE_TYPE (lhs))
 120            && ((vr->type == VR_RANGE
 121                 && range_includes_zero_p (vr->min,
 122                                           vr->max) == 0)
 123                || (vr->type == VR_ANTI_RANGE
 124                    && range_includes_zero_p (vr->min,
 125                                              vr->max) == 1)))
 126     set_ptr_nonnull (lhs);
 127 }
 128
 129 /* Return true if all uses of NAME are dominated by STMT or feed STMT
 130    via a chain of single immediate uses.  */
 131
 132 static bool
 133 all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt)
 134 {
 135   use_operand_p use_p, use2_p;
 136   imm_use_iterator iter;
 137   basic_block stmt_bb = gimple_bb (stmt);
 138
 139   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
 140     {
 141       gimple *use_stmt = USE_STMT (use_p), *use_stmt2;
 142       if (use_stmt == stmt
 143           || is_gimple_debug (use_stmt)
 144           || (gimple_bb (use_stmt) != stmt_bb
 145               && dominated_by_p (CDI_DOMINATORS,
 146                                  gimple_bb (use_stmt), stmt_bb)))
 147         continue;
 148       while (use_stmt != stmt
 149              && is_gimple_assign (use_stmt)
 150              && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
 151              && single_imm_use (gimple_assign_lhs (use_stmt),
 152                                 &use2_p, &use_stmt2))
 153         use_stmt = use_stmt2;
 154       if (use_stmt != stmt)
 155         return false;
 156     }
 157   return true;
 158 }
 159
 160 void
 161 evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb)
 162 {
 163   edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
 164   if (pred_e)
 165     {
 166       gimple *stmt = last_stmt (pred_e->src);
 167       tree op0 = NULL_TREE;
 168
 169       if (stmt
 170           && gimple_code (stmt) == GIMPLE_COND
 171           && (op0 = gimple_cond_lhs (stmt))
 172           && TREE_CODE (op0) == SSA_NAME
 173           && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
 174               || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
 175         {
 176           if (dump_file && (dump_flags & TDF_DETAILS))
 177             {
 178               fprintf (dump_file, "Visiting controlling predicate ");
 179               print_gimple_stmt (dump_file, stmt, 0);
 180             }
 181           /* Entering a new scope.  Try to see if we can find a VR
 182              here.  */
 183           tree op1 = gimple_cond_rhs (stmt);
 184           if (TREE_OVERFLOW_P (op1))
 185             op1 = drop_tree_overflow (op1);
 186           tree_code code = gimple_cond_code (stmt);
 187
 188           auto_vec<assert_info, 8> asserts;
 189           register_edge_assert_for (op0, pred_e, code, op0, op1, asserts);
 190           if (TREE_CODE (op1) == SSA_NAME)
 191             register_edge_assert_for (op1, pred_e, code, op0, op1, asserts);
 192
 193           auto_vec<std::pair<tree, value_range *>, 8> vrs;
 194           for (unsigned i = 0; i < asserts.length (); ++i)
 195             {
 196               value_range *vr = try_find_new_range (asserts[i].name,
 197                                                     asserts[i].expr,
 198                                                     asserts[i].comp_code,
 199                                                     asserts[i].val);
 200               if (vr)
 201                 vrs.safe_push (std::make_pair (asserts[i].name, vr));
 202             }
 203
 204           /* If pred_e is really a fallthru we can record value ranges
 205              in SSA names as well.  */
 206           bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e);
 207
 208           /* Push updated ranges only after finding all of them to avoid
 209              ordering issues that can lead to worse ranges.  */
 210           for (unsigned i = 0; i < vrs.length (); ++i)
 211             {
 212               push_value_range (vrs[i].first, vrs[i].second);
 213               if (is_fallthru
 214                   && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt))
 215                 {
 216                   set_ssa_range_info (vrs[i].first, vrs[i].second);
 217                   maybe_set_nonzero_bits (pred_e, vrs[i].first);
 218                 }
 219             }
 220         }
 221     }
 222 }
 223
 224 void
 225 evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
 226 {
 227   /* Visit PHI stmts and discover any new VRs possible.  */
 228   bool has_unvisited_preds = false;
 229   edge_iterator ei;
 230   edge e;
 231   FOR_EACH_EDGE (e, ei, bb->preds)
 232     if (e->flags & EDGE_EXECUTABLE
 233         && !(e->src->flags & BB_VISITED))
 234       {
 235         has_unvisited_preds = true;
 236         break;
 237       }
 238
 239   for (gphi_iterator gpi = gsi_start_phis (bb);
 240        !gsi_end_p (gpi); gsi_next (&gpi))
 241     {
 242       gphi *phi = gpi.phi ();
 243       tree lhs = PHI_RESULT (phi);
 244       if (virtual_operand_p (lhs))
 245         continue;
 246
 247       value_range vr_result = VR_INITIALIZER;
 248       bool interesting = stmt_interesting_for_vrp (phi);
 249       if (!has_unvisited_preds && interesting)
 250         vr_values->extract_range_from_phi_node (phi, &vr_result);
 251       else
 252         {
 253           set_value_range_to_varying (&vr_result);
 254           /* When we have an unvisited executable predecessor we can't
 255              use PHI arg ranges which may be still UNDEFINED but have
 256              to use VARYING for them.  But we can still resort to
 257              SCEV for loop header PHIs.  */
 258           struct loop *l;
 259           if (scev_initialized_p ()
 260               && interesting
 261               && (l = loop_containing_stmt (phi))
 262               && l->header == gimple_bb (phi))
 263           vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
 264         }
 265       vr_values->update_value_range (lhs, &vr_result);
 266
 267       /* Set the SSA with the value range.  */
 268       set_ssa_range_info (lhs, &vr_result);
 269     }
 270 }
 271
 272 /* Record ranges from STMT into our VR_VALUES class.  If TEMPORARY is
 273    true, then this is a temporary equivalence and should be recorded
 274    into the unwind table.  Othewise record the equivalence into the
 275    global table.  */
 276
 277 void
 278 evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary)
 279 {
 280   tree output = NULL_TREE;
 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   pop_to_marker ();
 394 }
 395
 396
 397 /* Push the Value Range of VAR to the stack and update it with new VR.  */
 398
 399 void
 400 evrp_range_analyzer::push_value_range (tree var, value_range *vr)
 401 {
 402   if (dump_file && (dump_flags & TDF_DETAILS))
 403     {
 404       fprintf (dump_file, "pushing new range for ");
 405       print_generic_expr (dump_file, var);
 406       fprintf (dump_file, ": ");
 407       dump_value_range (dump_file, vr);
 408       fprintf (dump_file, "\n");
 409     }
 410   stack.safe_push (std::make_pair (var, get_value_range (var)));
 411   vr_values->set_vr_value (var, vr);
 412 }
 413
 414 /* Pop the Value Range from the vrp_stack and update VAR with it.  */
 415
 416 value_range *
 417 evrp_range_analyzer::pop_value_range (tree var)
 418 {
 419   value_range *vr = stack.last ().second;
 420   gcc_checking_assert (var == stack.last ().first);
 421   if (dump_file && (dump_flags & TDF_DETAILS))
 422     {
 423       fprintf (dump_file, "popping range for ");
 424       print_generic_expr (dump_file, var);
 425       fprintf (dump_file, ", restoring ");
 426       dump_value_range (dump_file, vr);
 427       fprintf (dump_file, "\n");
 428     }
 429   vr_values->set_vr_value (var, vr);
 430   stack.pop ();
 431   return vr;
 432 }