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            && ((vr->type == VR_RANGE
 123                 && range_includes_zero_p (vr->min,
 124                                           vr->max) == 0)
 125                || (vr->type == VR_ANTI_RANGE
 126                    && range_includes_zero_p (vr->min,
 127                                              vr->max) == 1)))
 128     set_ptr_nonnull (lhs);
 129 }
 130
 131 /* Return true if all uses of NAME are dominated by STMT or feed STMT
 132    via a chain of single immediate uses.  */
 133
 134 static bool
 135 all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt)
 136 {
 137   use_operand_p use_p, use2_p;
 138   imm_use_iterator iter;
 139   basic_block stmt_bb = gimple_bb (stmt);
 140
 141   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
 142     {
 143       gimple *use_stmt = USE_STMT (use_p), *use_stmt2;
 144       if (use_stmt == stmt
 145           || is_gimple_debug (use_stmt)
 146           || (gimple_bb (use_stmt) != stmt_bb
 147               && dominated_by_p (CDI_DOMINATORS,
 148                                  gimple_bb (use_stmt), stmt_bb)))
 149         continue;
 150       while (use_stmt != stmt
 151              && is_gimple_assign (use_stmt)
 152              && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
 153              && single_imm_use (gimple_assign_lhs (use_stmt),
 154                                 &use2_p, &use_stmt2))
 155         use_stmt = use_stmt2;
 156       if (use_stmt != stmt)
 157         return false;
 158     }
 159   return true;
 160 }
 161
 162 void
 163 evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb)
 164 {
 165   edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
 166   if (pred_e)
 167     {
 168       gimple *stmt = last_stmt (pred_e->src);
 169       tree op0 = NULL_TREE;
 170
 171       if (stmt
 172           && gimple_code (stmt) == GIMPLE_COND
 173           && (op0 = gimple_cond_lhs (stmt))
 174           && TREE_CODE (op0) == SSA_NAME
 175           && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
 176               || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
 177         {
 178           if (dump_file && (dump_flags & TDF_DETAILS))
 179             {
 180               fprintf (dump_file, "Visiting controlling predicate ");
 181               print_gimple_stmt (dump_file, stmt, 0);
 182             }
 183           /* Entering a new scope.  Try to see if we can find a VR
 184              here.  */
 185           tree op1 = gimple_cond_rhs (stmt);
 186           if (TREE_OVERFLOW_P (op1))
 187             op1 = drop_tree_overflow (op1);
 188           tree_code code = gimple_cond_code (stmt);
 189
 190           auto_vec<assert_info, 8> asserts;
 191           register_edge_assert_for (op0, pred_e, code, op0, op1, asserts);
 192           if (TREE_CODE (op1) == SSA_NAME)
 193             register_edge_assert_for (op1, pred_e, code, op0, op1, asserts);
 194
 195           auto_vec<std::pair<tree, value_range *>, 8> vrs;
 196           for (unsigned i = 0; i < asserts.length (); ++i)
 197             {
 198               value_range *vr = try_find_new_range (asserts[i].name,
 199                                                     asserts[i].expr,
 200                                                     asserts[i].comp_code,
 201                                                     asserts[i].val);
 202               if (vr)
 203                 vrs.safe_push (std::make_pair (asserts[i].name, vr));
 204             }
 205
 206           /* If pred_e is really a fallthru we can record value ranges
 207              in SSA names as well.  */
 208           bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e);
 209
 210           /* Push updated ranges only after finding all of them to avoid
 211              ordering issues that can lead to worse ranges.  */
 212           for (unsigned i = 0; i < vrs.length (); ++i)
 213             {
 214               push_value_range (vrs[i].first, vrs[i].second);
 215               if (is_fallthru
 216                   && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt))
 217                 {
 218                   set_ssa_range_info (vrs[i].first, vrs[i].second);
 219                   maybe_set_nonzero_bits (pred_e, vrs[i].first);
 220                 }
 221             }
 222         }
 223     }
 224 }
 225
 226 void
 227 evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
 228 {
 229   /* Visit PHI stmts and discover any new VRs possible.  */
 230   bool has_unvisited_preds = false;
 231   edge_iterator ei;
 232   edge e;
 233   FOR_EACH_EDGE (e, ei, bb->preds)
 234     if (e->flags & EDGE_EXECUTABLE
 235         && !(e->src->flags & BB_VISITED))
 236       {
 237         has_unvisited_preds = true;
 238         break;
 239       }
 240
 241   for (gphi_iterator gpi = gsi_start_phis (bb);
 242        !gsi_end_p (gpi); gsi_next (&gpi))
 243     {
 244       gphi *phi = gpi.phi ();
 245       tree lhs = PHI_RESULT (phi);
 246       if (virtual_operand_p (lhs))
 247         continue;
 248
 249       value_range vr_result = VR_INITIALIZER;
 250       bool interesting = stmt_interesting_for_vrp (phi);
 251       if (!has_unvisited_preds && interesting)
 252         vr_values->extract_range_from_phi_node (phi, &vr_result);
 253       else
 254         {
 255           set_value_range_to_varying (&vr_result);
 256           /* When we have an unvisited executable predecessor we can't
 257              use PHI arg ranges which may be still UNDEFINED but have
 258              to use VARYING for them.  But we can still resort to
 259              SCEV for loop header PHIs.  */
 260           struct loop *l;
 261           if (scev_initialized_p ()
 262               && interesting
 263               && (l = loop_containing_stmt (phi))
 264               && l->header == gimple_bb (phi))
 265           vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
 266         }
 267       vr_values->update_value_range (lhs, &vr_result);
 268
 269       /* Set the SSA with the value range.  */
 270       set_ssa_range_info (lhs, &vr_result);
 271     }
 272 }
 273
 274 /* Record ranges from STMT into our VR_VALUES class.  If TEMPORARY is
 275    true, then this is a temporary equivalence and should be recorded
 276    into the unwind table.  Othewise record the equivalence into the
 277    global table.  */
 278
 279 void
 280 evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary)
 281 {
 282   tree output = NULL_TREE;
 283
 284   if (!optimize)
 285     return;
 286
 287   if (dyn_cast <gcond *> (stmt))
 288     ;
 289   else if (stmt_interesting_for_vrp (stmt))
 290     {
 291       edge taken_edge;
 292       value_range vr = VR_INITIALIZER;
 293       vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
 294       if (output)
 295         {
 296           /* Set the SSA with the value range.  There are two cases to
 297              consider.  First (the the most common) is we are processing
 298              STMT in a context where its resulting range globally holds
 299              and thus it can be reflected into the global ranges and need
 300              not be unwound as we leave scope.
 301
 302              The second case occurs if we are processing a statement in
 303              a context where the resulting range must not be reflected
 304              into the global tables and must be unwound as we leave
 305              the current context.  This happens in jump threading for
 306              example.  */
 307           if (!temporary)
 308             {
 309               /* Case one.  We can just update the underlying range
 310                  information as well as the global information.  */
 311               vr_values->update_value_range (output, &vr);
 312               set_ssa_range_info (output, &vr);
 313             }
 314           else
 315             {
 316               /* We're going to need to unwind this range.  We can
 317                  not use VR as that's a stack object.  We have to allocate
 318                  a new range and push the old range onto the stack.  We
 319                  also have to be very careful about sharing the underlying
 320                  bitmaps.  Ugh.  */
 321               value_range *new_vr = vr_values->allocate_value_range ();
 322               *new_vr = vr;
 323               new_vr->equiv = NULL;
 324               push_value_range (output, new_vr);
 325             }
 326         }
 327       else
 328         vr_values->set_defs_to_varying (stmt);
 329     }
 330   else
 331     vr_values->set_defs_to_varying (stmt);
 332
 333   /* See if we can derive a range for any of STMT's operands.  */
 334   tree op;
 335   ssa_op_iter i;
 336   FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
 337     {
 338       tree value;
 339       enum tree_code comp_code;
 340
 341       /* If OP is used in such a way that we can infer a value
 342          range for it, and we don't find a previous assertion for
 343          it, create a new assertion location node for OP.  */
 344       if (infer_value_range (stmt, op, &comp_code, &value))
 345         {
 346           /* If we are able to infer a nonzero value range for OP,
 347              then walk backwards through the use-def chain to see if OP
 348              was set via a typecast.
 349              If so, then we can also infer a nonzero value range
 350              for the operand of the NOP_EXPR.  */
 351           if (comp_code == NE_EXPR && integer_zerop (value))
 352             {
 353               tree t = op;
 354               gimple *def_stmt = SSA_NAME_DEF_STMT (t);
 355               while (is_gimple_assign (def_stmt)
 356                      && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 357                      && TREE_CODE
 358                           (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
 359                      && POINTER_TYPE_P
 360                           (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
 361                 {
 362                   t = gimple_assign_rhs1 (def_stmt);
 363                   def_stmt = SSA_NAME_DEF_STMT (t);
 364
 365                   /* Add VR when (T COMP_CODE value) condition is
 366                      true.  */
 367                   value_range *op_range
 368                     = try_find_new_range (t, t, comp_code, value);
 369                   if (op_range)
 370                     push_value_range (t, op_range);
 371                 }
 372             }
 373           /* Add VR when (OP COMP_CODE value) condition is true.  */
 374           value_range *op_range = try_find_new_range (op, op,
 375                                                       comp_code, value);
 376           if (op_range)
 377             push_value_range (op, op_range);
 378         }
 379     }
 380 }
 381
 382 /* Unwind recorded ranges to their most recent state.  */
 383
 384 void
 385 evrp_range_analyzer::pop_to_marker (void)
 386 {
 387   gcc_checking_assert (!stack.is_empty ());
 388   while (stack.last ().first != NULL_TREE)
 389     pop_value_range (stack.last ().first);
 390   stack.pop ();
 391 }
 392
 393 /* Restore/pop VRs valid only for BB when we leave BB.  */
 394
 395 void
 396 evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
 397 {
 398   if (!optimize)
 399     return;
 400   pop_to_marker ();
 401 }
 402
 403
 404 /* Push the Value Range of VAR to the stack and update it with new VR.  */
 405
 406 void
 407 evrp_range_analyzer::push_value_range (tree var, value_range *vr)
 408 {
 409   if (dump_file && (dump_flags & TDF_DETAILS))
 410     {
 411       fprintf (dump_file, "pushing new range for ");
 412       print_generic_expr (dump_file, var);
 413       fprintf (dump_file, ": ");
 414       dump_value_range (dump_file, vr);
 415       fprintf (dump_file, "\n");
 416     }
 417   stack.safe_push (std::make_pair (var, get_value_range (var)));
 418   vr_values->set_vr_value (var, vr);
 419 }
 420
 421 /* Pop the Value Range from the vrp_stack and update VAR with it.  */
 422
 423 value_range *
 424 evrp_range_analyzer::pop_value_range (tree var)
 425 {
 426   value_range *vr = stack.last ().second;
 427   gcc_checking_assert (var == stack.last ().first);
 428   if (dump_file && (dump_flags & TDF_DETAILS))
 429     {
 430       fprintf (dump_file, "popping range for ");
 431       print_generic_expr (dump_file, var);
 432       fprintf (dump_file, ", restoring ");
 433       dump_value_range (dump_file, vr);
 434       fprintf (dump_file, "\n");
 435     }
 436   vr_values->set_vr_value (var, vr);
 437   stack.pop ();
 438   return vr;
 439 }