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 } 440