1/* Support routines for Value Range Propagation (VRP). 2 Copyright (C) 2005-2020 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 3, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 45evrp_range_analyzer::evrp_range_analyzer (bool update_global_ranges) 46 : stack (10), m_update_global_ranges (update_global_ranges) 47{ 48 edge e; 49 edge_iterator ei; 50 basic_block bb; 51 FOR_EACH_BB_FN (bb, cfun) 52 { 53 bb->flags &= ~BB_VISITED; 54 FOR_EACH_EDGE (e, ei, bb->preds) 55 e->flags |= EDGE_EXECUTABLE; 56 } 57 vr_values = new class vr_values; 58} 59 60/* Push an unwinding marker onto the unwinding stack. */ 61 62void 63evrp_range_analyzer::push_marker () 64{ 65 stack.safe_push (std::make_pair (NULL_TREE, (value_range_equiv *)NULL)); 66} 67 68/* Analyze ranges as we enter basic block BB. */ 69 70void 71evrp_range_analyzer::enter (basic_block bb) 72{ 73 if (!optimize) 74 return; 75 push_marker (); 76 record_ranges_from_incoming_edge (bb); 77 record_ranges_from_phis (bb); 78 bb->flags |= BB_VISITED; 79} 80 81/* Find new range for NAME such that (OP CODE LIMIT) is true. */ 82value_range_equiv * 83evrp_range_analyzer::try_find_new_range (tree name, 84 tree op, tree_code code, tree limit) 85{ 86 value_range_equiv vr; 87 const value_range_equiv *old_vr = get_value_range (name); 88 89 /* Discover VR when condition is true. */ 90 vr_values->extract_range_for_var_from_comparison_expr (name, code, op, 91 limit, &vr); 92 /* If we found any usable VR, set the VR to ssa_name and create a 93 PUSH old value in the stack with the old VR. */ 94 if (!vr.undefined_p () && !vr.varying_p ()) 95 { 96 if (old_vr->equal_p (vr, /*ignore_equivs=*/true)) 97 return NULL; 98 value_range_equiv *new_vr = vr_values->allocate_value_range_equiv (); 99 new_vr->move (&vr); 100 return new_vr; 101 } 102 return NULL; 103} 104 105/* For LHS record VR in the SSA info. */ 106void 107evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range_equiv *vr) 108{ 109 gcc_assert (m_update_global_ranges); 110 111 /* Set the SSA with the value range. */ 112 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))) 113 { 114 if (vr->constant_p ()) 115 set_range_info (lhs, vr->kind (), 116 wi::to_wide (vr->min ()), 117 wi::to_wide (vr->max ())); 118 } 119 else if (POINTER_TYPE_P (TREE_TYPE (lhs)) 120 && range_includes_zero_p (vr) == 0) 121 set_ptr_nonnull (lhs); 122} 123 124/* Return true if all uses of NAME are dominated by STMT or feed STMT 125 via a chain of single immediate uses. */ 126 127static bool 128all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt) 129{ 130 use_operand_p use_p, use2_p; 131 imm_use_iterator iter; 132 basic_block stmt_bb = gimple_bb (stmt); 133 134 FOR_EACH_IMM_USE_FAST (use_p, iter, name) 135 { 136 gimple *use_stmt = USE_STMT (use_p), *use_stmt2; 137 if (use_stmt == stmt 138 || is_gimple_debug (use_stmt) 139 || (gimple_bb (use_stmt) != stmt_bb 140 && dominated_by_p (CDI_DOMINATORS, 141 gimple_bb (use_stmt), stmt_bb))) 142 continue; 143 while (use_stmt != stmt 144 && is_gimple_assign (use_stmt) 145 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME 146 && single_imm_use (gimple_assign_lhs (use_stmt), 147 &use2_p, &use_stmt2)) 148 use_stmt = use_stmt2; 149 if (use_stmt != stmt) 150 return false; 151 } 152 return true; 153} 154 155void 156evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb) 157{ 158 edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false); 159 if (pred_e) 160 { 161 gimple *stmt = last_stmt (pred_e->src); 162 tree op0 = NULL_TREE; 163 164 if (stmt 165 && gimple_code (stmt) == GIMPLE_COND 166 && (op0 = gimple_cond_lhs (stmt)) 167 && TREE_CODE (op0) == SSA_NAME 168 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) 169 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) 170 { 171 if (dump_file && (dump_flags & TDF_DETAILS)) 172 { 173 fprintf (dump_file, "Visiting controlling predicate "); 174 print_gimple_stmt (dump_file, stmt, 0); 175 } 176 /* Entering a new scope. Try to see if we can find a VR 177 here. */ 178 tree op1 = gimple_cond_rhs (stmt); 179 if (TREE_OVERFLOW_P (op1)) 180 op1 = drop_tree_overflow (op1); 181 tree_code code = gimple_cond_code (stmt); 182 183 auto_vec<assert_info, 8> asserts; 184 register_edge_assert_for (op0, pred_e, code, op0, op1, asserts); 185 if (TREE_CODE (op1) == SSA_NAME) 186 register_edge_assert_for (op1, pred_e, code, op0, op1, asserts); 187 188 auto_vec<std::pair<tree, value_range_equiv *>, 8> vrs; 189 for (unsigned i = 0; i < asserts.length (); ++i) 190 { 191 value_range_equiv *vr 192 = try_find_new_range (asserts[i].name, 193 asserts[i].expr, 194 asserts[i].comp_code, 195 asserts[i].val); 196 if (vr) 197 vrs.safe_push (std::make_pair (asserts[i].name, vr)); 198 } 199 200 /* If pred_e is really a fallthru we can record value ranges 201 in SSA names as well. */ 202 bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e); 203 204 /* Push updated ranges only after finding all of them to avoid 205 ordering issues that can lead to worse ranges. */ 206 for (unsigned i = 0; i < vrs.length (); ++i) 207 { 208 /* But make sure we do not weaken ranges like when 209 getting first [64, +INF] and then ~[0, 0] from 210 conditions like (s & 0x3cc0) == 0). */ 211 const value_range_equiv *old_vr 212 = get_value_range (vrs[i].first); 213 value_range tem (*old_vr); 214 tem.intersect (vrs[i].second); 215 if (tem.equal_p (*old_vr)) 216 { 217 vr_values->free_value_range (vrs[i].second); 218 continue; 219 } 220 push_value_range (vrs[i].first, vrs[i].second); 221 if (is_fallthru 222 && m_update_global_ranges 223 && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt) 224 /* The condition must post-dominate the definition point. */ 225 && (SSA_NAME_IS_DEFAULT_DEF (vrs[i].first) 226 || (gimple_bb (SSA_NAME_DEF_STMT (vrs[i].first)) 227 == pred_e->src))) 228 { 229 set_ssa_range_info (vrs[i].first, vrs[i].second); 230 maybe_set_nonzero_bits (pred_e, vrs[i].first); 231 } 232 } 233 } 234 } 235} 236 237void 238evrp_range_analyzer::record_ranges_from_phis (basic_block bb) 239{ 240 /* Visit PHI stmts and discover any new VRs possible. */ 241 bool has_unvisited_preds = false; 242 edge_iterator ei; 243 edge e; 244 FOR_EACH_EDGE (e, ei, bb->preds) 245 if (e->flags & EDGE_EXECUTABLE 246 && !(e->src->flags & BB_VISITED)) 247 { 248 has_unvisited_preds = true; 249 break; 250 } 251 252 for (gphi_iterator gpi = gsi_start_phis (bb); 253 !gsi_end_p (gpi); gsi_next (&gpi)) 254 { 255 gphi *phi = gpi.phi (); 256 tree lhs = PHI_RESULT (phi); 257 if (virtual_operand_p (lhs)) 258 continue; 259 260 /* Skips floats and other things we can't represent in a 261 range. */ 262 if (!value_range::supports_type_p (TREE_TYPE (lhs))) 263 continue; 264 265 value_range_equiv vr_result; 266 bool interesting = stmt_interesting_for_vrp (phi); 267 if (!has_unvisited_preds && interesting) 268 vr_values->extract_range_from_phi_node (phi, &vr_result); 269 else 270 { 271 vr_result.set_varying (TREE_TYPE (lhs)); 272 /* When we have an unvisited executable predecessor we can't 273 use PHI arg ranges which may be still UNDEFINED but have 274 to use VARYING for them. But we can still resort to 275 SCEV for loop header PHIs. */ 276 class loop *l; 277 if (scev_initialized_p () 278 && interesting 279 && (l = loop_containing_stmt (phi)) 280 && l->header == gimple_bb (phi)) 281 vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs); 282 } 283 vr_values->update_value_range (lhs, &vr_result); 284 285 /* Set the SSA with the value range. */ 286 if (m_update_global_ranges) 287 set_ssa_range_info (lhs, &vr_result); 288 } 289} 290 291/* Record ranges from STMT into our VR_VALUES class. If TEMPORARY is 292 true, then this is a temporary equivalence and should be recorded 293 into the unwind table. Othewise record the equivalence into the 294 global table. */ 295 296void 297evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary) 298{ 299 tree output = NULL_TREE; 300 301 if (!optimize) 302 return; 303 304 if (dyn_cast <gcond *> (stmt)) 305 ; 306 else if (stmt_interesting_for_vrp (stmt)) 307 { 308 edge taken_edge; 309 value_range_equiv vr; 310 vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr); 311 if (output) 312 { 313 /* Set the SSA with the value range. There are two cases to 314 consider. First (the the most common) is we are processing 315 STMT in a context where its resulting range globally holds 316 and thus it can be reflected into the global ranges and need 317 not be unwound as we leave scope. 318 319 The second case occurs if we are processing a statement in 320 a context where the resulting range must not be reflected 321 into the global tables and must be unwound as we leave 322 the current context. This happens in jump threading for 323 example. */ 324 if (!temporary) 325 { 326 /* Case one. We can just update the underlying range 327 information as well as the global information. */ 328 vr_values->update_value_range (output, &vr); 329 if (m_update_global_ranges) 330 set_ssa_range_info (output, &vr); 331 } 332 else 333 { 334 /* We're going to need to unwind this range. We cannot 335 use VR as that's a stack object. We have to allocate 336 a new range and push the old range onto the stack. We 337 also have to be very careful about sharing the underlying 338 bitmaps. Ugh. */ 339 value_range_equiv *new_vr 340 = vr_values->allocate_value_range_equiv (); 341 new_vr->set (vr.min (), vr.max (), NULL, vr.kind ()); 342 vr.equiv_clear (); 343 push_value_range (output, new_vr); 344 } 345 } 346 else 347 vr_values->set_defs_to_varying (stmt); 348 } 349 else 350 vr_values->set_defs_to_varying (stmt); 351 352 /* See if we can derive a range for any of STMT's operands. */ 353 tree op; 354 ssa_op_iter i; 355 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 356 { 357 tree value; 358 enum tree_code comp_code; 359 360 /* If OP is used in such a way that we can infer a value 361 range for it, and we don't find a previous assertion for 362 it, create a new assertion location node for OP. */ 363 if (infer_value_range (stmt, op, &comp_code, &value)) 364 { 365 /* If we are able to infer a nonzero value range for OP, 366 then walk backwards through the use-def chain to see if OP 367 was set via a typecast. 368 If so, then we can also infer a nonzero value range 369 for the operand of the NOP_EXPR. */ 370 if (comp_code == NE_EXPR && integer_zerop (value)) 371 { 372 tree t = op; 373 gimple *def_stmt = SSA_NAME_DEF_STMT (t); 374 while (is_gimple_assign (def_stmt) 375 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)) 376 && TREE_CODE 377 (gimple_assign_rhs1 (def_stmt)) == SSA_NAME 378 && POINTER_TYPE_P 379 (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) 380 { 381 t = gimple_assign_rhs1 (def_stmt); 382 def_stmt = SSA_NAME_DEF_STMT (t); 383 384 /* Add VR when (T COMP_CODE value) condition is 385 true. */ 386 value_range_equiv *op_range 387 = try_find_new_range (t, t, comp_code, value); 388 if (op_range) 389 push_value_range (t, op_range); 390 } 391 } 392 /* Add VR when (OP COMP_CODE value) condition is true. */ 393 value_range_equiv *op_range = try_find_new_range (op, op, 394 comp_code, value); 395 if (op_range) 396 push_value_range (op, op_range); 397 } 398 } 399} 400 401/* Unwind recorded ranges to their most recent state. */ 402 403void 404evrp_range_analyzer::pop_to_marker (void) 405{ 406 gcc_checking_assert (!stack.is_empty ()); 407 while (stack.last ().first != NULL_TREE) 408 pop_value_range (); 409 stack.pop (); 410} 411 412/* Restore/pop VRs valid only for BB when we leave BB. */ 413 414void 415evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED) 416{ 417 if (!optimize) 418 return; 419 pop_to_marker (); 420} 421 422 423/* Push the Value Range of VAR to the stack and update it with new VR. */ 424 425void 426evrp_range_analyzer::push_value_range (tree var, value_range_equiv *vr) 427{ 428 if (dump_file && (dump_flags & TDF_DETAILS)) 429 { 430 fprintf (dump_file, "pushing new range for "); 431 print_generic_expr (dump_file, var); 432 fprintf (dump_file, ": "); 433 dump_value_range (dump_file, vr); 434 fprintf (dump_file, "\n"); 435 } 436 value_range_equiv *old_vr = vr_values->swap_vr_value (var, vr); 437 stack.safe_push (std::make_pair (var, old_vr)); 438} 439 440/* Pop a Value Range from the vrp_stack. */ 441 442void 443evrp_range_analyzer::pop_value_range () 444{ 445 std::pair<tree, value_range_equiv *> e = stack.pop (); 446 tree var = e.first; 447 value_range_equiv *vr = e.second; 448 if (dump_file && (dump_flags & TDF_DETAILS)) 449 { 450 fprintf (dump_file, "popping range for "); 451 print_generic_expr (dump_file, var); 452 fprintf (dump_file, ", restoring "); 453 dump_value_range (dump_file, vr); 454 fprintf (dump_file, "\n"); 455 } 456 /* We saved off a lattice entry, now give it back and release 457 the one we popped. */ 458 value_range_equiv *popped_vr = vr_values->swap_vr_value (var, vr); 459 if (popped_vr) 460 vr_values->free_value_range (popped_vr); 461} 462