1 /* Support routines for Value Range Propagation (VRP). 2 Copyright (C) 2005-2019 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 "insn-codes.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "ssa.h" 28 #include "optabs-tree.h" 29 #include "gimple-pretty-print.h" 30 #include "diagnostic-core.h" 31 #include "flags.h" 32 #include "fold-const.h" 33 #include "calls.h" 34 #include "cfganal.h" 35 #include "gimple-fold.h" 36 #include "gimple-iterator.h" 37 #include "tree-cfg.h" 38 #include "tree-ssa-loop-niter.h" 39 #include "tree-ssa-loop.h" 40 #include "intl.h" 41 #include "cfgloop.h" 42 #include "tree-scalar-evolution.h" 43 #include "tree-ssa-propagate.h" 44 #include "tree-chrec.h" 45 #include "omp-general.h" 46 #include "case-cfn-macros.h" 47 #include "alloc-pool.h" 48 #include "attribs.h" 49 #include "vr-values.h" 50 #include "cfghooks.h" 51 52 /* Set value range VR to a non-negative range of type TYPE. */ 53 54 static inline void 55 set_value_range_to_nonnegative (value_range *vr, tree type) 56 { 57 tree zero = build_int_cst (type, 0); 58 vr->update (VR_RANGE, zero, vrp_val_max (type)); 59 } 60 61 /* Set value range VR to a range of a truthvalue of type TYPE. */ 62 63 static inline void 64 set_value_range_to_truthvalue (value_range *vr, tree type) 65 { 66 if (TYPE_PRECISION (type) == 1) 67 vr->set_varying (); 68 else 69 vr->update (VR_RANGE, build_int_cst (type, 0), build_int_cst (type, 1)); 70 } 71 72 73 /* Return value range information for VAR. 74 75 If we have no values ranges recorded (ie, VRP is not running), then 76 return NULL. Otherwise create an empty range if none existed for VAR. */ 77 78 value_range * 79 vr_values::get_value_range (const_tree var) 80 { 81 static const value_range vr_const_varying (VR_VARYING, NULL, NULL); 82 value_range *vr; 83 tree sym; 84 unsigned ver = SSA_NAME_VERSION (var); 85 86 /* If we have no recorded ranges, then return NULL. */ 87 if (! vr_value) 88 return NULL; 89 90 /* If we query the range for a new SSA name return an unmodifiable VARYING. 91 We should get here at most from the substitute-and-fold stage which 92 will never try to change values. */ 93 if (ver >= num_vr_values) 94 return CONST_CAST (value_range *, &vr_const_varying); 95 96 vr = vr_value[ver]; 97 if (vr) 98 return vr; 99 100 /* After propagation finished do not allocate new value-ranges. */ 101 if (values_propagated) 102 return CONST_CAST (value_range *, &vr_const_varying); 103 104 /* Create a default value range. */ 105 vr_value[ver] = vr = vrp_value_range_pool.allocate (); 106 vr->set_undefined (); 107 108 /* If VAR is a default definition of a parameter, the variable can 109 take any value in VAR's type. */ 110 if (SSA_NAME_IS_DEFAULT_DEF (var)) 111 { 112 sym = SSA_NAME_VAR (var); 113 if (TREE_CODE (sym) == PARM_DECL) 114 { 115 /* Try to use the "nonnull" attribute to create ~[0, 0] 116 anti-ranges for pointers. Note that this is only valid with 117 default definitions of PARM_DECLs. */ 118 if (POINTER_TYPE_P (TREE_TYPE (sym)) 119 && (nonnull_arg_p (sym) 120 || get_ptr_nonnull (var))) 121 vr->set_nonnull (TREE_TYPE (sym)); 122 else if (INTEGRAL_TYPE_P (TREE_TYPE (sym))) 123 { 124 get_range_info (var, *vr); 125 if (vr->undefined_p ()) 126 vr->set_varying (); 127 } 128 else 129 vr->set_varying (); 130 } 131 else if (TREE_CODE (sym) == RESULT_DECL 132 && DECL_BY_REFERENCE (sym)) 133 vr->set_nonnull (TREE_TYPE (sym)); 134 } 135 136 return vr; 137 } 138 139 /* Set value-ranges of all SSA names defined by STMT to varying. */ 140 141 void 142 vr_values::set_defs_to_varying (gimple *stmt) 143 { 144 ssa_op_iter i; 145 tree def; 146 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF) 147 { 148 value_range *vr = get_value_range (def); 149 /* Avoid writing to vr_const_varying get_value_range may return. */ 150 if (!vr->varying_p ()) 151 vr->set_varying (); 152 } 153 } 154 155 /* Update the value range and equivalence set for variable VAR to 156 NEW_VR. Return true if NEW_VR is different from VAR's previous 157 value. 158 159 NOTE: This function assumes that NEW_VR is a temporary value range 160 object created for the sole purpose of updating VAR's range. The 161 storage used by the equivalence set from NEW_VR will be freed by 162 this function. Do not call update_value_range when NEW_VR 163 is the range object associated with another SSA name. */ 164 165 bool 166 vr_values::update_value_range (const_tree var, value_range *new_vr) 167 { 168 value_range *old_vr; 169 bool is_new; 170 171 /* If there is a value-range on the SSA name from earlier analysis 172 factor that in. */ 173 if (INTEGRAL_TYPE_P (TREE_TYPE (var))) 174 { 175 value_range nr; 176 value_range_kind rtype = get_range_info (var, nr); 177 if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE) 178 new_vr->intersect (&nr); 179 } 180 181 /* Update the value range, if necessary. */ 182 old_vr = get_value_range (var); 183 is_new = !old_vr->equal_p (*new_vr, /*ignore_equivs=*/false); 184 185 if (is_new) 186 { 187 /* Do not allow transitions up the lattice. The following 188 is slightly more awkward than just new_vr->type < old_vr->type 189 because VR_RANGE and VR_ANTI_RANGE need to be considered 190 the same. We may not have is_new when transitioning to 191 UNDEFINED. If old_vr->type is VARYING, we shouldn't be 192 called, if we are anyway, keep it VARYING. */ 193 if (old_vr->varying_p ()) 194 { 195 new_vr->set_varying (); 196 is_new = false; 197 } 198 else if (new_vr->undefined_p ()) 199 { 200 old_vr->set_varying (); 201 new_vr->set_varying (); 202 return true; 203 } 204 else 205 old_vr->set (new_vr->kind (), 206 new_vr->min (), new_vr->max (), new_vr->equiv ()); 207 } 208 209 new_vr->equiv_clear (); 210 211 return is_new; 212 } 213 214 /* Return true if value range VR involves exactly one symbol SYM. */ 215 216 static bool 217 symbolic_range_based_on_p (value_range_base *vr, const_tree sym) 218 { 219 bool neg, min_has_symbol, max_has_symbol; 220 tree inv; 221 222 if (is_gimple_min_invariant (vr->min ())) 223 min_has_symbol = false; 224 else if (get_single_symbol (vr->min (), &neg, &inv) == sym) 225 min_has_symbol = true; 226 else 227 return false; 228 229 if (is_gimple_min_invariant (vr->max ())) 230 max_has_symbol = false; 231 else if (get_single_symbol (vr->max (), &neg, &inv) == sym) 232 max_has_symbol = true; 233 else 234 return false; 235 236 return (min_has_symbol || max_has_symbol); 237 } 238 239 /* Return true if the result of assignment STMT is know to be non-zero. */ 240 241 static bool 242 gimple_assign_nonzero_p (gimple *stmt) 243 { 244 enum tree_code code = gimple_assign_rhs_code (stmt); 245 bool strict_overflow_p; 246 switch (get_gimple_rhs_class (code)) 247 { 248 case GIMPLE_UNARY_RHS: 249 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt), 250 gimple_expr_type (stmt), 251 gimple_assign_rhs1 (stmt), 252 &strict_overflow_p); 253 case GIMPLE_BINARY_RHS: 254 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt), 255 gimple_expr_type (stmt), 256 gimple_assign_rhs1 (stmt), 257 gimple_assign_rhs2 (stmt), 258 &strict_overflow_p); 259 case GIMPLE_TERNARY_RHS: 260 return false; 261 case GIMPLE_SINGLE_RHS: 262 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt), 263 &strict_overflow_p); 264 case GIMPLE_INVALID_RHS: 265 gcc_unreachable (); 266 default: 267 gcc_unreachable (); 268 } 269 } 270 271 /* Return true if STMT is known to compute a non-zero value. */ 272 273 static bool 274 gimple_stmt_nonzero_p (gimple *stmt) 275 { 276 switch (gimple_code (stmt)) 277 { 278 case GIMPLE_ASSIGN: 279 return gimple_assign_nonzero_p (stmt); 280 case GIMPLE_CALL: 281 { 282 gcall *call_stmt = as_a<gcall *> (stmt); 283 return (gimple_call_nonnull_result_p (call_stmt) 284 || gimple_call_nonnull_arg (call_stmt)); 285 } 286 default: 287 gcc_unreachable (); 288 } 289 } 290 /* Like tree_expr_nonzero_p, but this function uses value ranges 291 obtained so far. */ 292 293 bool 294 vr_values::vrp_stmt_computes_nonzero (gimple *stmt) 295 { 296 if (gimple_stmt_nonzero_p (stmt)) 297 return true; 298 299 /* If we have an expression of the form &X->a, then the expression 300 is nonnull if X is nonnull. */ 301 if (is_gimple_assign (stmt) 302 && gimple_assign_rhs_code (stmt) == ADDR_EXPR) 303 { 304 tree expr = gimple_assign_rhs1 (stmt); 305 poly_int64 bitsize, bitpos; 306 tree offset; 307 machine_mode mode; 308 int unsignedp, reversep, volatilep; 309 tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, 310 &bitpos, &offset, &mode, &unsignedp, 311 &reversep, &volatilep); 312 313 if (base != NULL_TREE 314 && TREE_CODE (base) == MEM_REF 315 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) 316 { 317 poly_offset_int off = 0; 318 bool off_cst = false; 319 if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST) 320 { 321 off = mem_ref_offset (base); 322 if (offset) 323 off += poly_offset_int::from (wi::to_poly_wide (offset), 324 SIGNED); 325 off <<= LOG2_BITS_PER_UNIT; 326 off += bitpos; 327 off_cst = true; 328 } 329 /* If &X->a is equal to X and X is ~[0, 0], the result is too. 330 For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't 331 allow going from non-NULL pointer to NULL. */ 332 if ((off_cst && known_eq (off, 0)) 333 || (flag_delete_null_pointer_checks 334 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)))) 335 { 336 value_range *vr = get_value_range (TREE_OPERAND (base, 0)); 337 if (!range_includes_zero_p (vr)) 338 return true; 339 } 340 /* If MEM_REF has a "positive" offset, consider it non-NULL 341 always, for -fdelete-null-pointer-checks also "negative" 342 ones. Punt for unknown offsets (e.g. variable ones). */ 343 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)) 344 && off_cst 345 && known_ne (off, 0) 346 && (flag_delete_null_pointer_checks || known_gt (off, 0))) 347 return true; 348 } 349 } 350 351 return false; 352 } 353 354 /* Returns true if EXPR is a valid value (as expected by compare_values) -- 355 a gimple invariant, or SSA_NAME +- CST. */ 356 357 static bool 358 valid_value_p (tree expr) 359 { 360 if (TREE_CODE (expr) == SSA_NAME) 361 return true; 362 363 if (TREE_CODE (expr) == PLUS_EXPR 364 || TREE_CODE (expr) == MINUS_EXPR) 365 return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME 366 && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST); 367 368 return is_gimple_min_invariant (expr); 369 } 370 371 /* If OP has a value range with a single constant value return that, 372 otherwise return NULL_TREE. This returns OP itself if OP is a 373 constant. */ 374 375 tree 376 vr_values::op_with_constant_singleton_value_range (tree op) 377 { 378 if (is_gimple_min_invariant (op)) 379 return op; 380 381 if (TREE_CODE (op) != SSA_NAME) 382 return NULL_TREE; 383 384 return value_range_constant_singleton (get_value_range (op)); 385 } 386 387 /* Return true if op is in a boolean [0, 1] value-range. */ 388 389 bool 390 vr_values::op_with_boolean_value_range_p (tree op) 391 { 392 value_range *vr; 393 394 if (TYPE_PRECISION (TREE_TYPE (op)) == 1) 395 return true; 396 397 if (integer_zerop (op) 398 || integer_onep (op)) 399 return true; 400 401 if (TREE_CODE (op) != SSA_NAME) 402 return false; 403 404 vr = get_value_range (op); 405 return (vr->kind () == VR_RANGE 406 && integer_zerop (vr->min ()) 407 && integer_onep (vr->max ())); 408 } 409 410 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is 411 true and store it in *VR_P. */ 412 413 void 414 vr_values::extract_range_for_var_from_comparison_expr (tree var, 415 enum tree_code cond_code, 416 tree op, tree limit, 417 value_range *vr_p) 418 { 419 tree min, max, type; 420 value_range *limit_vr; 421 type = TREE_TYPE (var); 422 423 /* For pointer arithmetic, we only keep track of pointer equality 424 and inequality. If we arrive here with unfolded conditions like 425 _1 > _1 do not derive anything. */ 426 if ((POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR) 427 || limit == var) 428 { 429 vr_p->set_varying (); 430 return; 431 } 432 433 /* If LIMIT is another SSA name and LIMIT has a range of its own, 434 try to use LIMIT's range to avoid creating symbolic ranges 435 unnecessarily. */ 436 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL; 437 438 /* LIMIT's range is only interesting if it has any useful information. */ 439 if (! limit_vr 440 || limit_vr->undefined_p () 441 || limit_vr->varying_p () 442 || (limit_vr->symbolic_p () 443 && ! (limit_vr->kind () == VR_RANGE 444 && (limit_vr->min () == limit_vr->max () 445 || operand_equal_p (limit_vr->min (), 446 limit_vr->max (), 0))))) 447 limit_vr = NULL; 448 449 /* Initially, the new range has the same set of equivalences of 450 VAR's range. This will be revised before returning the final 451 value. Since assertions may be chained via mutually exclusive 452 predicates, we will need to trim the set of equivalences before 453 we are done. */ 454 gcc_assert (vr_p->equiv () == NULL); 455 vr_p->equiv_add (var, get_value_range (var), &vrp_equiv_obstack); 456 457 /* Extract a new range based on the asserted comparison for VAR and 458 LIMIT's value range. Notice that if LIMIT has an anti-range, we 459 will only use it for equality comparisons (EQ_EXPR). For any 460 other kind of assertion, we cannot derive a range from LIMIT's 461 anti-range that can be used to describe the new range. For 462 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10], 463 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is 464 no single range for x_2 that could describe LE_EXPR, so we might 465 as well build the range [b_4, +INF] for it. 466 One special case we handle is extracting a range from a 467 range test encoded as (unsigned)var + CST <= limit. */ 468 if (TREE_CODE (op) == NOP_EXPR 469 || TREE_CODE (op) == PLUS_EXPR) 470 { 471 if (TREE_CODE (op) == PLUS_EXPR) 472 { 473 min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)), 474 TREE_OPERAND (op, 1)); 475 max = int_const_binop (PLUS_EXPR, limit, min); 476 op = TREE_OPERAND (op, 0); 477 } 478 else 479 { 480 min = build_int_cst (TREE_TYPE (var), 0); 481 max = limit; 482 } 483 484 /* Make sure to not set TREE_OVERFLOW on the final type 485 conversion. We are willingly interpreting large positive 486 unsigned values as negative signed values here. */ 487 min = force_fit_type (TREE_TYPE (var), wi::to_widest (min), 0, false); 488 max = force_fit_type (TREE_TYPE (var), wi::to_widest (max), 0, false); 489 490 /* We can transform a max, min range to an anti-range or 491 vice-versa. Use set_and_canonicalize which does this for 492 us. */ 493 if (cond_code == LE_EXPR) 494 vr_p->set_and_canonicalize (VR_RANGE, min, max, vr_p->equiv ()); 495 else if (cond_code == GT_EXPR) 496 vr_p->set_and_canonicalize (VR_ANTI_RANGE, min, max, vr_p->equiv ()); 497 else 498 gcc_unreachable (); 499 } 500 else if (cond_code == EQ_EXPR) 501 { 502 enum value_range_kind range_type; 503 504 if (limit_vr) 505 { 506 range_type = limit_vr->kind (); 507 min = limit_vr->min (); 508 max = limit_vr->max (); 509 } 510 else 511 { 512 range_type = VR_RANGE; 513 min = limit; 514 max = limit; 515 } 516 517 vr_p->update (range_type, min, max); 518 519 /* When asserting the equality VAR == LIMIT and LIMIT is another 520 SSA name, the new range will also inherit the equivalence set 521 from LIMIT. */ 522 if (TREE_CODE (limit) == SSA_NAME) 523 vr_p->equiv_add (limit, get_value_range (limit), &vrp_equiv_obstack); 524 } 525 else if (cond_code == NE_EXPR) 526 { 527 /* As described above, when LIMIT's range is an anti-range and 528 this assertion is an inequality (NE_EXPR), then we cannot 529 derive anything from the anti-range. For instance, if 530 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does 531 not imply that VAR's range is [0, 0]. So, in the case of 532 anti-ranges, we just assert the inequality using LIMIT and 533 not its anti-range. 534 535 If LIMIT_VR is a range, we can only use it to build a new 536 anti-range if LIMIT_VR is a single-valued range. For 537 instance, if LIMIT_VR is [0, 1], the predicate 538 VAR != [0, 1] does not mean that VAR's range is ~[0, 1]. 539 Rather, it means that for value 0 VAR should be ~[0, 0] 540 and for value 1, VAR should be ~[1, 1]. We cannot 541 represent these ranges. 542 543 The only situation in which we can build a valid 544 anti-range is when LIMIT_VR is a single-valued range 545 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case, 546 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */ 547 if (limit_vr 548 && limit_vr->kind () == VR_RANGE 549 && compare_values (limit_vr->min (), limit_vr->max ()) == 0) 550 { 551 min = limit_vr->min (); 552 max = limit_vr->max (); 553 } 554 else 555 { 556 /* In any other case, we cannot use LIMIT's range to build a 557 valid anti-range. */ 558 min = max = limit; 559 } 560 561 /* If MIN and MAX cover the whole range for their type, then 562 just use the original LIMIT. */ 563 if (INTEGRAL_TYPE_P (type) 564 && vrp_val_is_min (min) 565 && vrp_val_is_max (max)) 566 min = max = limit; 567 568 vr_p->set_and_canonicalize (VR_ANTI_RANGE, min, max, vr_p->equiv ()); 569 } 570 else if (cond_code == LE_EXPR || cond_code == LT_EXPR) 571 { 572 min = TYPE_MIN_VALUE (type); 573 574 if (limit_vr == NULL || limit_vr->kind () == VR_ANTI_RANGE) 575 max = limit; 576 else 577 { 578 /* If LIMIT_VR is of the form [N1, N2], we need to build the 579 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for 580 LT_EXPR. */ 581 max = limit_vr->max (); 582 } 583 584 /* If the maximum value forces us to be out of bounds, simply punt. 585 It would be pointless to try and do anything more since this 586 all should be optimized away above us. */ 587 if (cond_code == LT_EXPR 588 && compare_values (max, min) == 0) 589 vr_p->set_varying (); 590 else 591 { 592 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */ 593 if (cond_code == LT_EXPR) 594 { 595 if (TYPE_PRECISION (TREE_TYPE (max)) == 1 596 && !TYPE_UNSIGNED (TREE_TYPE (max))) 597 max = fold_build2 (PLUS_EXPR, TREE_TYPE (max), max, 598 build_int_cst (TREE_TYPE (max), -1)); 599 else 600 max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, 601 build_int_cst (TREE_TYPE (max), 1)); 602 /* Signal to compare_values_warnv this expr doesn't overflow. */ 603 if (EXPR_P (max)) 604 TREE_NO_WARNING (max) = 1; 605 } 606 607 vr_p->update (VR_RANGE, min, max); 608 } 609 } 610 else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 611 { 612 max = TYPE_MAX_VALUE (type); 613 614 if (limit_vr == NULL || limit_vr->kind () == VR_ANTI_RANGE) 615 min = limit; 616 else 617 { 618 /* If LIMIT_VR is of the form [N1, N2], we need to build the 619 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for 620 GT_EXPR. */ 621 min = limit_vr->min (); 622 } 623 624 /* If the minimum value forces us to be out of bounds, simply punt. 625 It would be pointless to try and do anything more since this 626 all should be optimized away above us. */ 627 if (cond_code == GT_EXPR 628 && compare_values (min, max) == 0) 629 vr_p->set_varying (); 630 else 631 { 632 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */ 633 if (cond_code == GT_EXPR) 634 { 635 if (TYPE_PRECISION (TREE_TYPE (min)) == 1 636 && !TYPE_UNSIGNED (TREE_TYPE (min))) 637 min = fold_build2 (MINUS_EXPR, TREE_TYPE (min), min, 638 build_int_cst (TREE_TYPE (min), -1)); 639 else 640 min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min, 641 build_int_cst (TREE_TYPE (min), 1)); 642 /* Signal to compare_values_warnv this expr doesn't overflow. */ 643 if (EXPR_P (min)) 644 TREE_NO_WARNING (min) = 1; 645 } 646 647 vr_p->update (VR_RANGE, min, max); 648 } 649 } 650 else 651 gcc_unreachable (); 652 653 /* Finally intersect the new range with what we already know about var. */ 654 vr_p->intersect (get_value_range (var)); 655 } 656 657 /* Extract value range information from an ASSERT_EXPR EXPR and store 658 it in *VR_P. */ 659 660 void 661 vr_values::extract_range_from_assert (value_range *vr_p, tree expr) 662 { 663 tree var = ASSERT_EXPR_VAR (expr); 664 tree cond = ASSERT_EXPR_COND (expr); 665 tree limit, op; 666 enum tree_code cond_code; 667 gcc_assert (COMPARISON_CLASS_P (cond)); 668 669 /* Find VAR in the ASSERT_EXPR conditional. */ 670 if (var == TREE_OPERAND (cond, 0) 671 || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR 672 || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR) 673 { 674 /* If the predicate is of the form VAR COMP LIMIT, then we just 675 take LIMIT from the RHS and use the same comparison code. */ 676 cond_code = TREE_CODE (cond); 677 limit = TREE_OPERAND (cond, 1); 678 op = TREE_OPERAND (cond, 0); 679 } 680 else 681 { 682 /* If the predicate is of the form LIMIT COMP VAR, then we need 683 to flip around the comparison code to create the proper range 684 for VAR. */ 685 cond_code = swap_tree_comparison (TREE_CODE (cond)); 686 limit = TREE_OPERAND (cond, 0); 687 op = TREE_OPERAND (cond, 1); 688 } 689 extract_range_for_var_from_comparison_expr (var, cond_code, op, 690 limit, vr_p); 691 } 692 693 /* Extract range information from SSA name VAR and store it in VR. If 694 VAR has an interesting range, use it. Otherwise, create the 695 range [VAR, VAR] and return it. This is useful in situations where 696 we may have conditionals testing values of VARYING names. For 697 instance, 698 699 x_3 = y_5; 700 if (x_3 > y_5) 701 ... 702 703 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is 704 always false. */ 705 706 void 707 vr_values::extract_range_from_ssa_name (value_range *vr, tree var) 708 { 709 value_range *var_vr = get_value_range (var); 710 711 if (!var_vr->varying_p ()) 712 vr->deep_copy (var_vr); 713 else 714 vr->set (var); 715 716 vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack); 717 } 718 719 /* Extract range information from a binary expression OP0 CODE OP1 based on 720 the ranges of each of its operands with resulting type EXPR_TYPE. 721 The resulting range is stored in *VR. */ 722 723 void 724 vr_values::extract_range_from_binary_expr (value_range *vr, 725 enum tree_code code, 726 tree expr_type, tree op0, tree op1) 727 { 728 /* Get value ranges for each operand. For constant operands, create 729 a new value range with the operand to simplify processing. */ 730 value_range_base vr0, vr1; 731 if (TREE_CODE (op0) == SSA_NAME) 732 vr0 = *(get_value_range (op0)); 733 else if (is_gimple_min_invariant (op0)) 734 vr0.set (op0); 735 else 736 vr0.set_varying (); 737 738 if (TREE_CODE (op1) == SSA_NAME) 739 vr1 = *(get_value_range (op1)); 740 else if (is_gimple_min_invariant (op1)) 741 vr1.set (op1); 742 else 743 vr1.set_varying (); 744 745 /* If one argument is varying, we can sometimes still deduce a 746 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */ 747 if (INTEGRAL_TYPE_P (TREE_TYPE (op0)) 748 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))) 749 { 750 if (vr0.varying_p () && !vr1.varying_p ()) 751 vr0 = value_range (VR_RANGE, 752 vrp_val_min (expr_type), 753 vrp_val_max (expr_type)); 754 else if (vr1.varying_p () && !vr0.varying_p ()) 755 vr1 = value_range (VR_RANGE, 756 vrp_val_min (expr_type), 757 vrp_val_max (expr_type)); 758 } 759 760 ::extract_range_from_binary_expr (vr, code, expr_type, &vr0, &vr1); 761 762 /* Set value_range for n in following sequence: 763 def = __builtin_memchr (arg, 0, sz) 764 n = def - arg 765 Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */ 766 767 if (vr->varying_p () 768 && code == POINTER_DIFF_EXPR 769 && TREE_CODE (op0) == SSA_NAME 770 && TREE_CODE (op1) == SSA_NAME) 771 { 772 tree op0_ptype = TREE_TYPE (TREE_TYPE (op0)); 773 tree op1_ptype = TREE_TYPE (TREE_TYPE (op1)); 774 gcall *call_stmt = NULL; 775 776 if (TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node) 777 && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node) 778 && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node) 779 && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node) 780 && (call_stmt = dyn_cast<gcall *>(SSA_NAME_DEF_STMT (op0))) 781 && gimple_call_builtin_p (call_stmt, BUILT_IN_MEMCHR) 782 && operand_equal_p (op0, gimple_call_lhs (call_stmt), 0) 783 && operand_equal_p (op1, gimple_call_arg (call_stmt, 0), 0) 784 && integer_zerop (gimple_call_arg (call_stmt, 1))) 785 { 786 tree max = vrp_val_max (ptrdiff_type_node); 787 wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); 788 tree range_min = build_zero_cst (expr_type); 789 tree range_max = wide_int_to_tree (expr_type, wmax - 1); 790 vr->set (VR_RANGE, range_min, range_max); 791 return; 792 } 793 } 794 795 /* Try harder for PLUS and MINUS if the range of one operand is symbolic 796 and based on the other operand, for example if it was deduced from a 797 symbolic comparison. When a bound of the range of the first operand 798 is invariant, we set the corresponding bound of the new range to INF 799 in order to avoid recursing on the range of the second operand. */ 800 if (vr->varying_p () 801 && (code == PLUS_EXPR || code == MINUS_EXPR) 802 && TREE_CODE (op1) == SSA_NAME 803 && vr0.kind () == VR_RANGE 804 && symbolic_range_based_on_p (&vr0, op1)) 805 { 806 const bool minus_p = (code == MINUS_EXPR); 807 value_range n_vr1; 808 809 /* Try with VR0 and [-INF, OP1]. */ 810 if (is_gimple_min_invariant (minus_p ? vr0.max () : vr0.min ())) 811 n_vr1.set (VR_RANGE, vrp_val_min (expr_type), op1); 812 813 /* Try with VR0 and [OP1, +INF]. */ 814 else if (is_gimple_min_invariant (minus_p ? vr0.min () : vr0.max ())) 815 n_vr1.set (VR_RANGE, op1, vrp_val_max (expr_type)); 816 817 /* Try with VR0 and [OP1, OP1]. */ 818 else 819 n_vr1.set (VR_RANGE, op1, op1); 820 821 ::extract_range_from_binary_expr (vr, code, expr_type, &vr0, &n_vr1); 822 } 823 824 if (vr->varying_p () 825 && (code == PLUS_EXPR || code == MINUS_EXPR) 826 && TREE_CODE (op0) == SSA_NAME 827 && vr1.kind () == VR_RANGE 828 && symbolic_range_based_on_p (&vr1, op0)) 829 { 830 const bool minus_p = (code == MINUS_EXPR); 831 value_range n_vr0; 832 833 /* Try with [-INF, OP0] and VR1. */ 834 if (is_gimple_min_invariant (minus_p ? vr1.max () : vr1.min ())) 835 n_vr0.set (VR_RANGE, vrp_val_min (expr_type), op0); 836 837 /* Try with [OP0, +INF] and VR1. */ 838 else if (is_gimple_min_invariant (minus_p ? vr1.min (): vr1.max ())) 839 n_vr0.set (VR_RANGE, op0, vrp_val_max (expr_type)); 840 841 /* Try with [OP0, OP0] and VR1. */ 842 else 843 n_vr0.set (op0); 844 845 ::extract_range_from_binary_expr (vr, code, expr_type, &n_vr0, &vr1); 846 } 847 848 /* If we didn't derive a range for MINUS_EXPR, and 849 op1's range is ~[op0,op0] or vice-versa, then we 850 can derive a non-null range. This happens often for 851 pointer subtraction. */ 852 if (vr->varying_p () 853 && (code == MINUS_EXPR || code == POINTER_DIFF_EXPR) 854 && TREE_CODE (op0) == SSA_NAME 855 && ((vr0.kind () == VR_ANTI_RANGE 856 && vr0.min () == op1 857 && vr0.min () == vr0.max ()) 858 || (vr1.kind () == VR_ANTI_RANGE 859 && vr1.min () == op0 860 && vr1.min () == vr1.max ()))) 861 vr->set_nonnull (expr_type); 862 } 863 864 /* Extract range information from a unary expression CODE OP0 based on 865 the range of its operand with resulting type TYPE. 866 The resulting range is stored in *VR. */ 867 868 void 869 vr_values::extract_range_from_unary_expr (value_range *vr, enum tree_code code, 870 tree type, tree op0) 871 { 872 value_range_base vr0; 873 874 /* Get value ranges for the operand. For constant operands, create 875 a new value range with the operand to simplify processing. */ 876 if (TREE_CODE (op0) == SSA_NAME) 877 vr0 = *(get_value_range (op0)); 878 else if (is_gimple_min_invariant (op0)) 879 vr0.set (op0); 880 else 881 vr0.set_varying (); 882 883 ::extract_range_from_unary_expr (vr, code, type, &vr0, TREE_TYPE (op0)); 884 } 885 886 887 /* Extract range information from a conditional expression STMT based on 888 the ranges of each of its operands and the expression code. */ 889 890 void 891 vr_values::extract_range_from_cond_expr (value_range *vr, gassign *stmt) 892 { 893 /* Get value ranges for each operand. For constant operands, create 894 a new value range with the operand to simplify processing. */ 895 tree op0 = gimple_assign_rhs2 (stmt); 896 value_range tem0; 897 value_range *vr0 = &tem0; 898 if (TREE_CODE (op0) == SSA_NAME) 899 vr0 = get_value_range (op0); 900 else if (is_gimple_min_invariant (op0)) 901 tem0.set (op0); 902 else 903 tem0.set_varying (); 904 905 tree op1 = gimple_assign_rhs3 (stmt); 906 value_range tem1; 907 value_range *vr1 = &tem1; 908 if (TREE_CODE (op1) == SSA_NAME) 909 vr1 = get_value_range (op1); 910 else if (is_gimple_min_invariant (op1)) 911 tem1.set (op1); 912 else 913 tem1.set_varying (); 914 915 /* The resulting value range is the union of the operand ranges */ 916 vr->deep_copy (vr0); 917 vr->union_ (vr1); 918 } 919 920 921 /* Extract range information from a comparison expression EXPR based 922 on the range of its operand and the expression code. */ 923 924 void 925 vr_values::extract_range_from_comparison (value_range *vr, enum tree_code code, 926 tree type, tree op0, tree op1) 927 { 928 bool sop; 929 tree val; 930 931 val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop, 932 NULL); 933 if (val) 934 { 935 /* Since this expression was found on the RHS of an assignment, 936 its type may be different from _Bool. Convert VAL to EXPR's 937 type. */ 938 val = fold_convert (type, val); 939 if (is_gimple_min_invariant (val)) 940 vr->set (val); 941 else 942 vr->update (VR_RANGE, val, val); 943 } 944 else 945 /* The result of a comparison is always true or false. */ 946 set_value_range_to_truthvalue (vr, type); 947 } 948 949 /* Helper function for simplify_internal_call_using_ranges and 950 extract_range_basic. Return true if OP0 SUBCODE OP1 for 951 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or 952 always overflow. Set *OVF to true if it is known to always 953 overflow. */ 954 955 bool 956 vr_values::check_for_binary_op_overflow (enum tree_code subcode, tree type, 957 tree op0, tree op1, bool *ovf) 958 { 959 value_range_base vr0, vr1; 960 if (TREE_CODE (op0) == SSA_NAME) 961 vr0 = *get_value_range (op0); 962 else if (TREE_CODE (op0) == INTEGER_CST) 963 vr0.set (op0); 964 else 965 vr0.set_varying (); 966 967 if (TREE_CODE (op1) == SSA_NAME) 968 vr1 = *get_value_range (op1); 969 else if (TREE_CODE (op1) == INTEGER_CST) 970 vr1.set (op1); 971 else 972 vr1.set_varying (); 973 974 tree vr0min = vr0.min (), vr0max = vr0.max (); 975 tree vr1min = vr1.min (), vr1max = vr1.max (); 976 if (!range_int_cst_p (&vr0) 977 || TREE_OVERFLOW (vr0min) 978 || TREE_OVERFLOW (vr0max)) 979 { 980 vr0min = vrp_val_min (TREE_TYPE (op0)); 981 vr0max = vrp_val_max (TREE_TYPE (op0)); 982 } 983 if (!range_int_cst_p (&vr1) 984 || TREE_OVERFLOW (vr1min) 985 || TREE_OVERFLOW (vr1max)) 986 { 987 vr1min = vrp_val_min (TREE_TYPE (op1)); 988 vr1max = vrp_val_max (TREE_TYPE (op1)); 989 } 990 *ovf = arith_overflowed_p (subcode, type, vr0min, 991 subcode == MINUS_EXPR ? vr1max : vr1min); 992 if (arith_overflowed_p (subcode, type, vr0max, 993 subcode == MINUS_EXPR ? vr1min : vr1max) != *ovf) 994 return false; 995 if (subcode == MULT_EXPR) 996 { 997 if (arith_overflowed_p (subcode, type, vr0min, vr1max) != *ovf 998 || arith_overflowed_p (subcode, type, vr0max, vr1min) != *ovf) 999 return false; 1000 } 1001 if (*ovf) 1002 { 1003 /* So far we found that there is an overflow on the boundaries. 1004 That doesn't prove that there is an overflow even for all values 1005 in between the boundaries. For that compute widest_int range 1006 of the result and see if it doesn't overlap the range of 1007 type. */ 1008 widest_int wmin, wmax; 1009 widest_int w[4]; 1010 int i; 1011 w[0] = wi::to_widest (vr0min); 1012 w[1] = wi::to_widest (vr0max); 1013 w[2] = wi::to_widest (vr1min); 1014 w[3] = wi::to_widest (vr1max); 1015 for (i = 0; i < 4; i++) 1016 { 1017 widest_int wt; 1018 switch (subcode) 1019 { 1020 case PLUS_EXPR: 1021 wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]); 1022 break; 1023 case MINUS_EXPR: 1024 wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]); 1025 break; 1026 case MULT_EXPR: 1027 wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]); 1028 break; 1029 default: 1030 gcc_unreachable (); 1031 } 1032 if (i == 0) 1033 { 1034 wmin = wt; 1035 wmax = wt; 1036 } 1037 else 1038 { 1039 wmin = wi::smin (wmin, wt); 1040 wmax = wi::smax (wmax, wt); 1041 } 1042 } 1043 /* The result of op0 CODE op1 is known to be in range 1044 [wmin, wmax]. */ 1045 widest_int wtmin = wi::to_widest (vrp_val_min (type)); 1046 widest_int wtmax = wi::to_widest (vrp_val_max (type)); 1047 /* If all values in [wmin, wmax] are smaller than 1048 [wtmin, wtmax] or all are larger than [wtmin, wtmax], 1049 the arithmetic operation will always overflow. */ 1050 if (wmax < wtmin || wmin > wtmax) 1051 return true; 1052 return false; 1053 } 1054 return true; 1055 } 1056 1057 /* Try to derive a nonnegative or nonzero range out of STMT relying 1058 primarily on generic routines in fold in conjunction with range data. 1059 Store the result in *VR */ 1060 1061 void 1062 vr_values::extract_range_basic (value_range *vr, gimple *stmt) 1063 { 1064 bool sop; 1065 tree type = gimple_expr_type (stmt); 1066 1067 if (is_gimple_call (stmt)) 1068 { 1069 tree arg; 1070 int mini, maxi, zerov = 0, prec; 1071 enum tree_code subcode = ERROR_MARK; 1072 combined_fn cfn = gimple_call_combined_fn (stmt); 1073 scalar_int_mode mode; 1074 1075 switch (cfn) 1076 { 1077 case CFN_BUILT_IN_CONSTANT_P: 1078 /* If the call is __builtin_constant_p and the argument is a 1079 function parameter resolve it to false. This avoids bogus 1080 array bound warnings. 1081 ??? We could do this as early as inlining is finished. */ 1082 arg = gimple_call_arg (stmt, 0); 1083 if (TREE_CODE (arg) == SSA_NAME 1084 && SSA_NAME_IS_DEFAULT_DEF (arg) 1085 && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL 1086 && cfun->after_inlining) 1087 { 1088 vr->set_null (type); 1089 return; 1090 } 1091 break; 1092 /* Both __builtin_ffs* and __builtin_popcount return 1093 [0, prec]. */ 1094 CASE_CFN_FFS: 1095 CASE_CFN_POPCOUNT: 1096 arg = gimple_call_arg (stmt, 0); 1097 prec = TYPE_PRECISION (TREE_TYPE (arg)); 1098 mini = 0; 1099 maxi = prec; 1100 if (TREE_CODE (arg) == SSA_NAME) 1101 { 1102 value_range *vr0 = get_value_range (arg); 1103 /* If arg is non-zero, then ffs or popcount are non-zero. */ 1104 if (range_includes_zero_p (vr0) == 0) 1105 mini = 1; 1106 /* If some high bits are known to be zero, 1107 we can decrease the maximum. */ 1108 if (vr0->kind () == VR_RANGE 1109 && TREE_CODE (vr0->max ()) == INTEGER_CST 1110 && !operand_less_p (vr0->min (), 1111 build_zero_cst (TREE_TYPE (vr0->min ())))) 1112 maxi = tree_floor_log2 (vr0->max ()) + 1; 1113 } 1114 goto bitop_builtin; 1115 /* __builtin_parity* returns [0, 1]. */ 1116 CASE_CFN_PARITY: 1117 mini = 0; 1118 maxi = 1; 1119 goto bitop_builtin; 1120 /* __builtin_c[lt]z* return [0, prec-1], except for 1121 when the argument is 0, but that is undefined behavior. 1122 On many targets where the CLZ RTL or optab value is defined 1123 for 0 the value is prec, so include that in the range 1124 by default. */ 1125 CASE_CFN_CLZ: 1126 arg = gimple_call_arg (stmt, 0); 1127 prec = TYPE_PRECISION (TREE_TYPE (arg)); 1128 mini = 0; 1129 maxi = prec; 1130 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); 1131 if (optab_handler (clz_optab, mode) != CODE_FOR_nothing 1132 && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) 1133 /* Handle only the single common value. */ 1134 && zerov != prec) 1135 /* Magic value to give up, unless vr0 proves 1136 arg is non-zero. */ 1137 mini = -2; 1138 if (TREE_CODE (arg) == SSA_NAME) 1139 { 1140 value_range *vr0 = get_value_range (arg); 1141 /* From clz of VR_RANGE minimum we can compute 1142 result maximum. */ 1143 if (vr0->kind () == VR_RANGE 1144 && TREE_CODE (vr0->min ()) == INTEGER_CST) 1145 { 1146 maxi = prec - 1 - tree_floor_log2 (vr0->min ()); 1147 if (maxi != prec) 1148 mini = 0; 1149 } 1150 else if (vr0->kind () == VR_ANTI_RANGE 1151 && integer_zerop (vr0->min ())) 1152 { 1153 maxi = prec - 1; 1154 mini = 0; 1155 } 1156 if (mini == -2) 1157 break; 1158 /* From clz of VR_RANGE maximum we can compute 1159 result minimum. */ 1160 if (vr0->kind () == VR_RANGE 1161 && TREE_CODE (vr0->max ()) == INTEGER_CST) 1162 { 1163 mini = prec - 1 - tree_floor_log2 (vr0->max ()); 1164 if (mini == prec) 1165 break; 1166 } 1167 } 1168 if (mini == -2) 1169 break; 1170 goto bitop_builtin; 1171 /* __builtin_ctz* return [0, prec-1], except for 1172 when the argument is 0, but that is undefined behavior. 1173 If there is a ctz optab for this mode and 1174 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range, 1175 otherwise just assume 0 won't be seen. */ 1176 CASE_CFN_CTZ: 1177 arg = gimple_call_arg (stmt, 0); 1178 prec = TYPE_PRECISION (TREE_TYPE (arg)); 1179 mini = 0; 1180 maxi = prec - 1; 1181 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); 1182 if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing 1183 && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov)) 1184 { 1185 /* Handle only the two common values. */ 1186 if (zerov == -1) 1187 mini = -1; 1188 else if (zerov == prec) 1189 maxi = prec; 1190 else 1191 /* Magic value to give up, unless vr0 proves 1192 arg is non-zero. */ 1193 mini = -2; 1194 } 1195 if (TREE_CODE (arg) == SSA_NAME) 1196 { 1197 value_range *vr0 = get_value_range (arg); 1198 /* If arg is non-zero, then use [0, prec - 1]. */ 1199 if ((vr0->kind () == VR_RANGE 1200 && integer_nonzerop (vr0->min ())) 1201 || (vr0->kind () == VR_ANTI_RANGE 1202 && integer_zerop (vr0->min ()))) 1203 { 1204 mini = 0; 1205 maxi = prec - 1; 1206 } 1207 /* If some high bits are known to be zero, 1208 we can decrease the result maximum. */ 1209 if (vr0->kind () == VR_RANGE 1210 && TREE_CODE (vr0->max ()) == INTEGER_CST) 1211 { 1212 maxi = tree_floor_log2 (vr0->max ()); 1213 /* For vr0 [0, 0] give up. */ 1214 if (maxi == -1) 1215 break; 1216 } 1217 } 1218 if (mini == -2) 1219 break; 1220 goto bitop_builtin; 1221 /* __builtin_clrsb* returns [0, prec-1]. */ 1222 CASE_CFN_CLRSB: 1223 arg = gimple_call_arg (stmt, 0); 1224 prec = TYPE_PRECISION (TREE_TYPE (arg)); 1225 mini = 0; 1226 maxi = prec - 1; 1227 goto bitop_builtin; 1228 bitop_builtin: 1229 vr->set (VR_RANGE, build_int_cst (type, mini), 1230 build_int_cst (type, maxi)); 1231 return; 1232 case CFN_UBSAN_CHECK_ADD: 1233 subcode = PLUS_EXPR; 1234 break; 1235 case CFN_UBSAN_CHECK_SUB: 1236 subcode = MINUS_EXPR; 1237 break; 1238 case CFN_UBSAN_CHECK_MUL: 1239 subcode = MULT_EXPR; 1240 break; 1241 case CFN_GOACC_DIM_SIZE: 1242 case CFN_GOACC_DIM_POS: 1243 /* Optimizing these two internal functions helps the loop 1244 optimizer eliminate outer comparisons. Size is [1,N] 1245 and pos is [0,N-1]. */ 1246 { 1247 bool is_pos = cfn == CFN_GOACC_DIM_POS; 1248 int axis = oacc_get_ifn_dim_arg (stmt); 1249 int size = oacc_get_fn_dim_size (current_function_decl, axis); 1250 1251 if (!size) 1252 /* If it's dynamic, the backend might know a hardware 1253 limitation. */ 1254 size = targetm.goacc.dim_limit (axis); 1255 1256 tree type = TREE_TYPE (gimple_call_lhs (stmt)); 1257 vr->set(VR_RANGE, build_int_cst (type, is_pos ? 0 : 1), 1258 size 1259 ? build_int_cst (type, size - is_pos) : vrp_val_max (type)); 1260 } 1261 return; 1262 case CFN_BUILT_IN_STRLEN: 1263 if (tree lhs = gimple_call_lhs (stmt)) 1264 if (ptrdiff_type_node 1265 && (TYPE_PRECISION (ptrdiff_type_node) 1266 == TYPE_PRECISION (TREE_TYPE (lhs)))) 1267 { 1268 tree type = TREE_TYPE (lhs); 1269 tree max = vrp_val_max (ptrdiff_type_node); 1270 wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); 1271 tree range_min = build_zero_cst (type); 1272 tree range_max = wide_int_to_tree (type, wmax - 1); 1273 vr->set (VR_RANGE, range_min, range_max); 1274 return; 1275 } 1276 break; 1277 default: 1278 break; 1279 } 1280 if (subcode != ERROR_MARK) 1281 { 1282 bool saved_flag_wrapv = flag_wrapv; 1283 /* Pretend the arithmetics is wrapping. If there is 1284 any overflow, we'll complain, but will actually do 1285 wrapping operation. */ 1286 flag_wrapv = 1; 1287 extract_range_from_binary_expr (vr, subcode, type, 1288 gimple_call_arg (stmt, 0), 1289 gimple_call_arg (stmt, 1)); 1290 flag_wrapv = saved_flag_wrapv; 1291 1292 /* If for both arguments vrp_valueize returned non-NULL, 1293 this should have been already folded and if not, it 1294 wasn't folded because of overflow. Avoid removing the 1295 UBSAN_CHECK_* calls in that case. */ 1296 if (vr->kind () == VR_RANGE 1297 && (vr->min () == vr->max () 1298 || operand_equal_p (vr->min (), vr->max (), 0))) 1299 vr->set_varying (); 1300 return; 1301 } 1302 } 1303 /* Handle extraction of the two results (result of arithmetics and 1304 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW 1305 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */ 1306 else if (is_gimple_assign (stmt) 1307 && (gimple_assign_rhs_code (stmt) == REALPART_EXPR 1308 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR) 1309 && INTEGRAL_TYPE_P (type)) 1310 { 1311 enum tree_code code = gimple_assign_rhs_code (stmt); 1312 tree op = gimple_assign_rhs1 (stmt); 1313 if (TREE_CODE (op) == code && TREE_CODE (TREE_OPERAND (op, 0)) == SSA_NAME) 1314 { 1315 gimple *g = SSA_NAME_DEF_STMT (TREE_OPERAND (op, 0)); 1316 if (is_gimple_call (g) && gimple_call_internal_p (g)) 1317 { 1318 enum tree_code subcode = ERROR_MARK; 1319 switch (gimple_call_internal_fn (g)) 1320 { 1321 case IFN_ADD_OVERFLOW: 1322 subcode = PLUS_EXPR; 1323 break; 1324 case IFN_SUB_OVERFLOW: 1325 subcode = MINUS_EXPR; 1326 break; 1327 case IFN_MUL_OVERFLOW: 1328 subcode = MULT_EXPR; 1329 break; 1330 case IFN_ATOMIC_COMPARE_EXCHANGE: 1331 if (code == IMAGPART_EXPR) 1332 { 1333 /* This is the boolean return value whether compare and 1334 exchange changed anything or not. */ 1335 vr->set (VR_RANGE, build_int_cst (type, 0), 1336 build_int_cst (type, 1)); 1337 return; 1338 } 1339 break; 1340 default: 1341 break; 1342 } 1343 if (subcode != ERROR_MARK) 1344 { 1345 tree op0 = gimple_call_arg (g, 0); 1346 tree op1 = gimple_call_arg (g, 1); 1347 if (code == IMAGPART_EXPR) 1348 { 1349 bool ovf = false; 1350 if (check_for_binary_op_overflow (subcode, type, 1351 op0, op1, &ovf)) 1352 vr->set (build_int_cst (type, ovf)); 1353 else if (TYPE_PRECISION (type) == 1 1354 && !TYPE_UNSIGNED (type)) 1355 vr->set_varying (); 1356 else 1357 vr->set (VR_RANGE, build_int_cst (type, 0), 1358 build_int_cst (type, 1)); 1359 } 1360 else if (types_compatible_p (type, TREE_TYPE (op0)) 1361 && types_compatible_p (type, TREE_TYPE (op1))) 1362 { 1363 bool saved_flag_wrapv = flag_wrapv; 1364 /* Pretend the arithmetics is wrapping. If there is 1365 any overflow, IMAGPART_EXPR will be set. */ 1366 flag_wrapv = 1; 1367 extract_range_from_binary_expr (vr, subcode, type, 1368 op0, op1); 1369 flag_wrapv = saved_flag_wrapv; 1370 } 1371 else 1372 { 1373 value_range vr0, vr1; 1374 bool saved_flag_wrapv = flag_wrapv; 1375 /* Pretend the arithmetics is wrapping. If there is 1376 any overflow, IMAGPART_EXPR will be set. */ 1377 flag_wrapv = 1; 1378 extract_range_from_unary_expr (&vr0, NOP_EXPR, 1379 type, op0); 1380 extract_range_from_unary_expr (&vr1, NOP_EXPR, 1381 type, op1); 1382 ::extract_range_from_binary_expr (vr, subcode, type, 1383 &vr0, &vr1); 1384 flag_wrapv = saved_flag_wrapv; 1385 } 1386 return; 1387 } 1388 } 1389 } 1390 } 1391 if (INTEGRAL_TYPE_P (type) 1392 && gimple_stmt_nonnegative_warnv_p (stmt, &sop)) 1393 set_value_range_to_nonnegative (vr, type); 1394 else if (vrp_stmt_computes_nonzero (stmt)) 1395 vr->set_nonnull (type); 1396 else 1397 vr->set_varying (); 1398 } 1399 1400 1401 /* Try to compute a useful range out of assignment STMT and store it 1402 in *VR. */ 1403 1404 void 1405 vr_values::extract_range_from_assignment (value_range *vr, gassign *stmt) 1406 { 1407 enum tree_code code = gimple_assign_rhs_code (stmt); 1408 1409 if (code == ASSERT_EXPR) 1410 extract_range_from_assert (vr, gimple_assign_rhs1 (stmt)); 1411 else if (code == SSA_NAME) 1412 extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt)); 1413 else if (TREE_CODE_CLASS (code) == tcc_binary) 1414 extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt), 1415 gimple_expr_type (stmt), 1416 gimple_assign_rhs1 (stmt), 1417 gimple_assign_rhs2 (stmt)); 1418 else if (TREE_CODE_CLASS (code) == tcc_unary) 1419 extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt), 1420 gimple_expr_type (stmt), 1421 gimple_assign_rhs1 (stmt)); 1422 else if (code == COND_EXPR) 1423 extract_range_from_cond_expr (vr, stmt); 1424 else if (TREE_CODE_CLASS (code) == tcc_comparison) 1425 extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt), 1426 gimple_expr_type (stmt), 1427 gimple_assign_rhs1 (stmt), 1428 gimple_assign_rhs2 (stmt)); 1429 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS 1430 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) 1431 vr->set (gimple_assign_rhs1 (stmt)); 1432 else 1433 vr->set_varying (); 1434 1435 if (vr->varying_p ()) 1436 extract_range_basic (vr, stmt); 1437 } 1438 1439 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP: 1440 1441 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for 1442 all the values in the ranges. 1443 1444 - Return BOOLEAN_FALSE_NODE if the comparison always returns false. 1445 1446 - Return NULL_TREE if it is not always possible to determine the 1447 value of the comparison. 1448 1449 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation 1450 assumed signed overflow is undefined. */ 1451 1452 1453 static tree 1454 compare_ranges (enum tree_code comp, value_range *vr0, value_range *vr1, 1455 bool *strict_overflow_p) 1456 { 1457 /* VARYING or UNDEFINED ranges cannot be compared. */ 1458 if (vr0->varying_p () 1459 || vr0->undefined_p () 1460 || vr1->varying_p () 1461 || vr1->undefined_p ()) 1462 return NULL_TREE; 1463 1464 /* Anti-ranges need to be handled separately. */ 1465 if (vr0->kind () == VR_ANTI_RANGE || vr1->kind () == VR_ANTI_RANGE) 1466 { 1467 /* If both are anti-ranges, then we cannot compute any 1468 comparison. */ 1469 if (vr0->kind () == VR_ANTI_RANGE && vr1->kind () == VR_ANTI_RANGE) 1470 return NULL_TREE; 1471 1472 /* These comparisons are never statically computable. */ 1473 if (comp == GT_EXPR 1474 || comp == GE_EXPR 1475 || comp == LT_EXPR 1476 || comp == LE_EXPR) 1477 return NULL_TREE; 1478 1479 /* Equality can be computed only between a range and an 1480 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */ 1481 if (vr0->kind () == VR_RANGE) 1482 { 1483 /* To simplify processing, make VR0 the anti-range. */ 1484 value_range *tmp = vr0; 1485 vr0 = vr1; 1486 vr1 = tmp; 1487 } 1488 1489 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR); 1490 1491 if (compare_values_warnv (vr0->min (), vr1->min (), strict_overflow_p) == 0 1492 && compare_values_warnv (vr0->max (), vr1->max (), strict_overflow_p) == 0) 1493 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 1494 1495 return NULL_TREE; 1496 } 1497 1498 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the 1499 operands around and change the comparison code. */ 1500 if (comp == GT_EXPR || comp == GE_EXPR) 1501 { 1502 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR; 1503 std::swap (vr0, vr1); 1504 } 1505 1506 if (comp == EQ_EXPR) 1507 { 1508 /* Equality may only be computed if both ranges represent 1509 exactly one value. */ 1510 if (compare_values_warnv (vr0->min (), vr0->max (), strict_overflow_p) == 0 1511 && compare_values_warnv (vr1->min (), vr1->max (), strict_overflow_p) == 0) 1512 { 1513 int cmp_min = compare_values_warnv (vr0->min (), vr1->min (), 1514 strict_overflow_p); 1515 int cmp_max = compare_values_warnv (vr0->max (), vr1->max (), 1516 strict_overflow_p); 1517 if (cmp_min == 0 && cmp_max == 0) 1518 return boolean_true_node; 1519 else if (cmp_min != -2 && cmp_max != -2) 1520 return boolean_false_node; 1521 } 1522 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */ 1523 else if (compare_values_warnv (vr0->min (), vr1->max (), 1524 strict_overflow_p) == 1 1525 || compare_values_warnv (vr1->min (), vr0->max (), 1526 strict_overflow_p) == 1) 1527 return boolean_false_node; 1528 1529 return NULL_TREE; 1530 } 1531 else if (comp == NE_EXPR) 1532 { 1533 int cmp1, cmp2; 1534 1535 /* If VR0 is completely to the left or completely to the right 1536 of VR1, they are always different. Notice that we need to 1537 make sure that both comparisons yield similar results to 1538 avoid comparing values that cannot be compared at 1539 compile-time. */ 1540 cmp1 = compare_values_warnv (vr0->max (), vr1->min (), strict_overflow_p); 1541 cmp2 = compare_values_warnv (vr0->min (), vr1->max (), strict_overflow_p); 1542 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1)) 1543 return boolean_true_node; 1544 1545 /* If VR0 and VR1 represent a single value and are identical, 1546 return false. */ 1547 else if (compare_values_warnv (vr0->min (), vr0->max (), 1548 strict_overflow_p) == 0 1549 && compare_values_warnv (vr1->min (), vr1->max (), 1550 strict_overflow_p) == 0 1551 && compare_values_warnv (vr0->min (), vr1->min (), 1552 strict_overflow_p) == 0 1553 && compare_values_warnv (vr0->max (), vr1->max (), 1554 strict_overflow_p) == 0) 1555 return boolean_false_node; 1556 1557 /* Otherwise, they may or may not be different. */ 1558 else 1559 return NULL_TREE; 1560 } 1561 else if (comp == LT_EXPR || comp == LE_EXPR) 1562 { 1563 int tst; 1564 1565 /* If VR0 is to the left of VR1, return true. */ 1566 tst = compare_values_warnv (vr0->max (), vr1->min (), strict_overflow_p); 1567 if ((comp == LT_EXPR && tst == -1) 1568 || (comp == LE_EXPR && (tst == -1 || tst == 0))) 1569 return boolean_true_node; 1570 1571 /* If VR0 is to the right of VR1, return false. */ 1572 tst = compare_values_warnv (vr0->min (), vr1->max (), strict_overflow_p); 1573 if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 1574 || (comp == LE_EXPR && tst == 1)) 1575 return boolean_false_node; 1576 1577 /* Otherwise, we don't know. */ 1578 return NULL_TREE; 1579 } 1580 1581 gcc_unreachable (); 1582 } 1583 1584 /* Given a value range VR, a value VAL and a comparison code COMP, return 1585 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the 1586 values in VR. Return BOOLEAN_FALSE_NODE if the comparison 1587 always returns false. Return NULL_TREE if it is not always 1588 possible to determine the value of the comparison. Also set 1589 *STRICT_OVERFLOW_P to indicate whether comparision evaluation 1590 assumed signed overflow is undefined. */ 1591 1592 static tree 1593 compare_range_with_value (enum tree_code comp, value_range *vr, tree val, 1594 bool *strict_overflow_p) 1595 { 1596 if (vr->varying_p () || vr->undefined_p ()) 1597 return NULL_TREE; 1598 1599 /* Anti-ranges need to be handled separately. */ 1600 if (vr->kind () == VR_ANTI_RANGE) 1601 { 1602 /* For anti-ranges, the only predicates that we can compute at 1603 compile time are equality and inequality. */ 1604 if (comp == GT_EXPR 1605 || comp == GE_EXPR 1606 || comp == LT_EXPR 1607 || comp == LE_EXPR) 1608 return NULL_TREE; 1609 1610 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */ 1611 if (value_inside_range (val, vr->min (), vr->max ()) == 1) 1612 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 1613 1614 return NULL_TREE; 1615 } 1616 1617 if (comp == EQ_EXPR) 1618 { 1619 /* EQ_EXPR may only be computed if VR represents exactly 1620 one value. */ 1621 if (compare_values_warnv (vr->min (), vr->max (), strict_overflow_p) == 0) 1622 { 1623 int cmp = compare_values_warnv (vr->min (), val, strict_overflow_p); 1624 if (cmp == 0) 1625 return boolean_true_node; 1626 else if (cmp == -1 || cmp == 1 || cmp == 2) 1627 return boolean_false_node; 1628 } 1629 else if (compare_values_warnv (val, vr->min (), strict_overflow_p) == -1 1630 || compare_values_warnv (vr->max (), val, strict_overflow_p) == -1) 1631 return boolean_false_node; 1632 1633 return NULL_TREE; 1634 } 1635 else if (comp == NE_EXPR) 1636 { 1637 /* If VAL is not inside VR, then they are always different. */ 1638 if (compare_values_warnv (vr->max (), val, strict_overflow_p) == -1 1639 || compare_values_warnv (vr->min (), val, strict_overflow_p) == 1) 1640 return boolean_true_node; 1641 1642 /* If VR represents exactly one value equal to VAL, then return 1643 false. */ 1644 if (compare_values_warnv (vr->min (), vr->max (), strict_overflow_p) == 0 1645 && compare_values_warnv (vr->min (), val, strict_overflow_p) == 0) 1646 return boolean_false_node; 1647 1648 /* Otherwise, they may or may not be different. */ 1649 return NULL_TREE; 1650 } 1651 else if (comp == LT_EXPR || comp == LE_EXPR) 1652 { 1653 int tst; 1654 1655 /* If VR is to the left of VAL, return true. */ 1656 tst = compare_values_warnv (vr->max (), val, strict_overflow_p); 1657 if ((comp == LT_EXPR && tst == -1) 1658 || (comp == LE_EXPR && (tst == -1 || tst == 0))) 1659 return boolean_true_node; 1660 1661 /* If VR is to the right of VAL, return false. */ 1662 tst = compare_values_warnv (vr->min (), val, strict_overflow_p); 1663 if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 1664 || (comp == LE_EXPR && tst == 1)) 1665 return boolean_false_node; 1666 1667 /* Otherwise, we don't know. */ 1668 return NULL_TREE; 1669 } 1670 else if (comp == GT_EXPR || comp == GE_EXPR) 1671 { 1672 int tst; 1673 1674 /* If VR is to the right of VAL, return true. */ 1675 tst = compare_values_warnv (vr->min (), val, strict_overflow_p); 1676 if ((comp == GT_EXPR && tst == 1) 1677 || (comp == GE_EXPR && (tst == 0 || tst == 1))) 1678 return boolean_true_node; 1679 1680 /* If VR is to the left of VAL, return false. */ 1681 tst = compare_values_warnv (vr->max (), val, strict_overflow_p); 1682 if ((comp == GT_EXPR && (tst == -1 || tst == 0)) 1683 || (comp == GE_EXPR && tst == -1)) 1684 return boolean_false_node; 1685 1686 /* Otherwise, we don't know. */ 1687 return NULL_TREE; 1688 } 1689 1690 gcc_unreachable (); 1691 } 1692 /* Given a range VR, a LOOP and a variable VAR, determine whether it 1693 would be profitable to adjust VR using scalar evolution information 1694 for VAR. If so, update VR with the new limits. */ 1695 1696 void 1697 vr_values::adjust_range_with_scev (value_range *vr, struct loop *loop, 1698 gimple *stmt, tree var) 1699 { 1700 tree init, step, chrec, tmin, tmax, min, max, type, tem; 1701 enum ev_direction dir; 1702 1703 /* TODO. Don't adjust anti-ranges. An anti-range may provide 1704 better opportunities than a regular range, but I'm not sure. */ 1705 if (vr->kind () == VR_ANTI_RANGE) 1706 return; 1707 1708 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); 1709 1710 /* Like in PR19590, scev can return a constant function. */ 1711 if (is_gimple_min_invariant (chrec)) 1712 { 1713 vr->set (chrec); 1714 return; 1715 } 1716 1717 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 1718 return; 1719 1720 init = initial_condition_in_loop_num (chrec, loop->num); 1721 tem = op_with_constant_singleton_value_range (init); 1722 if (tem) 1723 init = tem; 1724 step = evolution_part_in_loop_num (chrec, loop->num); 1725 tem = op_with_constant_singleton_value_range (step); 1726 if (tem) 1727 step = tem; 1728 1729 /* If STEP is symbolic, we can't know whether INIT will be the 1730 minimum or maximum value in the range. Also, unless INIT is 1731 a simple expression, compare_values and possibly other functions 1732 in tree-vrp won't be able to handle it. */ 1733 if (step == NULL_TREE 1734 || !is_gimple_min_invariant (step) 1735 || !valid_value_p (init)) 1736 return; 1737 1738 dir = scev_direction (chrec); 1739 if (/* Do not adjust ranges if we do not know whether the iv increases 1740 or decreases, ... */ 1741 dir == EV_DIR_UNKNOWN 1742 /* ... or if it may wrap. */ 1743 || scev_probably_wraps_p (NULL_TREE, init, step, stmt, 1744 get_chrec_loop (chrec), true)) 1745 return; 1746 1747 type = TREE_TYPE (var); 1748 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) 1749 tmin = lower_bound_in_type (type, type); 1750 else 1751 tmin = TYPE_MIN_VALUE (type); 1752 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) 1753 tmax = upper_bound_in_type (type, type); 1754 else 1755 tmax = TYPE_MAX_VALUE (type); 1756 1757 /* Try to use estimated number of iterations for the loop to constrain the 1758 final value in the evolution. */ 1759 if (TREE_CODE (step) == INTEGER_CST 1760 && is_gimple_val (init) 1761 && (TREE_CODE (init) != SSA_NAME 1762 || get_value_range (init)->kind () == VR_RANGE)) 1763 { 1764 widest_int nit; 1765 1766 /* We are only entering here for loop header PHI nodes, so using 1767 the number of latch executions is the correct thing to use. */ 1768 if (max_loop_iterations (loop, &nit)) 1769 { 1770 value_range maxvr; 1771 signop sgn = TYPE_SIGN (TREE_TYPE (step)); 1772 wi::overflow_type overflow; 1773 1774 widest_int wtmp = wi::mul (wi::to_widest (step), nit, sgn, 1775 &overflow); 1776 /* If the multiplication overflowed we can't do a meaningful 1777 adjustment. Likewise if the result doesn't fit in the type 1778 of the induction variable. For a signed type we have to 1779 check whether the result has the expected signedness which 1780 is that of the step as number of iterations is unsigned. */ 1781 if (!overflow 1782 && wi::fits_to_tree_p (wtmp, TREE_TYPE (init)) 1783 && (sgn == UNSIGNED 1784 || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0))) 1785 { 1786 tem = wide_int_to_tree (TREE_TYPE (init), wtmp); 1787 extract_range_from_binary_expr (&maxvr, PLUS_EXPR, 1788 TREE_TYPE (init), init, tem); 1789 /* Likewise if the addition did. */ 1790 if (maxvr.kind () == VR_RANGE) 1791 { 1792 value_range_base initvr; 1793 1794 if (TREE_CODE (init) == SSA_NAME) 1795 initvr = *(get_value_range (init)); 1796 else if (is_gimple_min_invariant (init)) 1797 initvr.set (init); 1798 else 1799 return; 1800 1801 /* Check if init + nit * step overflows. Though we checked 1802 scev {init, step}_loop doesn't wrap, it is not enough 1803 because the loop may exit immediately. Overflow could 1804 happen in the plus expression in this case. */ 1805 if ((dir == EV_DIR_DECREASES 1806 && compare_values (maxvr.min (), initvr.min ()) != -1) 1807 || (dir == EV_DIR_GROWS 1808 && compare_values (maxvr.max (), initvr.max ()) != 1)) 1809 return; 1810 1811 tmin = maxvr.min (); 1812 tmax = maxvr.max (); 1813 } 1814 } 1815 } 1816 } 1817 1818 if (vr->varying_p () || vr->undefined_p ()) 1819 { 1820 min = tmin; 1821 max = tmax; 1822 1823 /* For VARYING or UNDEFINED ranges, just about anything we get 1824 from scalar evolutions should be better. */ 1825 1826 if (dir == EV_DIR_DECREASES) 1827 max = init; 1828 else 1829 min = init; 1830 } 1831 else if (vr->kind () == VR_RANGE) 1832 { 1833 min = vr->min (); 1834 max = vr->max (); 1835 1836 if (dir == EV_DIR_DECREASES) 1837 { 1838 /* INIT is the maximum value. If INIT is lower than VR->MAX () 1839 but no smaller than VR->MIN (), set VR->MAX () to INIT. */ 1840 if (compare_values (init, max) == -1) 1841 max = init; 1842 1843 /* According to the loop information, the variable does not 1844 overflow. */ 1845 if (compare_values (min, tmin) == -1) 1846 min = tmin; 1847 1848 } 1849 else 1850 { 1851 /* If INIT is bigger than VR->MIN (), set VR->MIN () to INIT. */ 1852 if (compare_values (init, min) == 1) 1853 min = init; 1854 1855 if (compare_values (tmax, max) == -1) 1856 max = tmax; 1857 } 1858 } 1859 else 1860 return; 1861 1862 /* If we just created an invalid range with the minimum 1863 greater than the maximum, we fail conservatively. 1864 This should happen only in unreachable 1865 parts of code, or for invalid programs. */ 1866 if (compare_values (min, max) == 1) 1867 return; 1868 1869 /* Even for valid range info, sometimes overflow flag will leak in. 1870 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we 1871 drop them. */ 1872 if (TREE_OVERFLOW_P (min)) 1873 min = drop_tree_overflow (min); 1874 if (TREE_OVERFLOW_P (max)) 1875 max = drop_tree_overflow (max); 1876 1877 vr->update (VR_RANGE, min, max); 1878 } 1879 1880 /* Dump value ranges of all SSA_NAMEs to FILE. */ 1881 1882 void 1883 vr_values::dump_all_value_ranges (FILE *file) 1884 { 1885 size_t i; 1886 1887 for (i = 0; i < num_vr_values; i++) 1888 { 1889 if (vr_value[i]) 1890 { 1891 print_generic_expr (file, ssa_name (i)); 1892 fprintf (file, ": "); 1893 dump_value_range (file, vr_value[i]); 1894 fprintf (file, "\n"); 1895 } 1896 } 1897 1898 fprintf (file, "\n"); 1899 } 1900 1901 /* Initialize VRP lattice. */ 1902 1903 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges") 1904 { 1905 values_propagated = false; 1906 num_vr_values = num_ssa_names; 1907 vr_value = XCNEWVEC (value_range *, num_vr_values); 1908 vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); 1909 bitmap_obstack_initialize (&vrp_equiv_obstack); 1910 to_remove_edges = vNULL; 1911 to_update_switch_stmts = vNULL; 1912 } 1913 1914 /* Free VRP lattice. */ 1915 1916 vr_values::~vr_values () 1917 { 1918 /* Free allocated memory. */ 1919 free (vr_value); 1920 free (vr_phi_edge_counts); 1921 bitmap_obstack_release (&vrp_equiv_obstack); 1922 vrp_value_range_pool.release (); 1923 1924 /* So that we can distinguish between VRP data being available 1925 and not available. */ 1926 vr_value = NULL; 1927 vr_phi_edge_counts = NULL; 1928 1929 /* If there are entries left in TO_REMOVE_EDGES or TO_UPDATE_SWITCH_STMTS 1930 then an EVRP client did not clean up properly. Catch it now rather 1931 than seeing something more obscure later. */ 1932 gcc_assert (to_remove_edges.is_empty () 1933 && to_update_switch_stmts.is_empty ()); 1934 } 1935 1936 1937 /* A hack. */ 1938 static class vr_values *x_vr_values; 1939 1940 /* Return the singleton value-range for NAME or NAME. */ 1941 1942 static inline tree 1943 vrp_valueize (tree name) 1944 { 1945 if (TREE_CODE (name) == SSA_NAME) 1946 { 1947 value_range *vr = x_vr_values->get_value_range (name); 1948 if (vr->kind () == VR_RANGE 1949 && (TREE_CODE (vr->min ()) == SSA_NAME 1950 || is_gimple_min_invariant (vr->min ())) 1951 && vrp_operand_equal_p (vr->min (), vr->max ())) 1952 return vr->min (); 1953 } 1954 return name; 1955 } 1956 1957 /* Return the singleton value-range for NAME if that is a constant 1958 but signal to not follow SSA edges. */ 1959 1960 static inline tree 1961 vrp_valueize_1 (tree name) 1962 { 1963 if (TREE_CODE (name) == SSA_NAME) 1964 { 1965 /* If the definition may be simulated again we cannot follow 1966 this SSA edge as the SSA propagator does not necessarily 1967 re-visit the use. */ 1968 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 1969 if (!gimple_nop_p (def_stmt) 1970 && prop_simulate_again_p (def_stmt)) 1971 return NULL_TREE; 1972 value_range *vr = x_vr_values->get_value_range (name); 1973 tree singleton; 1974 if (vr->singleton_p (&singleton)) 1975 return singleton; 1976 } 1977 return name; 1978 } 1979 1980 /* Given STMT, an assignment or call, return its LHS if the type 1981 of the LHS is suitable for VRP analysis, else return NULL_TREE. */ 1982 1983 tree 1984 get_output_for_vrp (gimple *stmt) 1985 { 1986 if (!is_gimple_assign (stmt) && !is_gimple_call (stmt)) 1987 return NULL_TREE; 1988 1989 /* We only keep track of ranges in integral and pointer types. */ 1990 tree lhs = gimple_get_lhs (stmt); 1991 if (TREE_CODE (lhs) == SSA_NAME 1992 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 1993 /* It is valid to have NULL MIN/MAX values on a type. See 1994 build_range_type. */ 1995 && TYPE_MIN_VALUE (TREE_TYPE (lhs)) 1996 && TYPE_MAX_VALUE (TREE_TYPE (lhs))) 1997 || POINTER_TYPE_P (TREE_TYPE (lhs)))) 1998 return lhs; 1999 2000 return NULL_TREE; 2001 } 2002 2003 /* Visit assignment STMT. If it produces an interesting range, record 2004 the range in VR and set LHS to OUTPUT_P. */ 2005 2006 void 2007 vr_values::vrp_visit_assignment_or_call (gimple *stmt, tree *output_p, 2008 value_range *vr) 2009 { 2010 tree lhs = get_output_for_vrp (stmt); 2011 *output_p = lhs; 2012 2013 /* We only keep track of ranges in integral and pointer types. */ 2014 if (lhs) 2015 { 2016 enum gimple_code code = gimple_code (stmt); 2017 2018 /* Try folding the statement to a constant first. */ 2019 x_vr_values = this; 2020 tree tem = gimple_fold_stmt_to_constant_1 (stmt, vrp_valueize, 2021 vrp_valueize_1); 2022 x_vr_values = NULL; 2023 if (tem) 2024 { 2025 if (TREE_CODE (tem) == SSA_NAME 2026 && (SSA_NAME_IS_DEFAULT_DEF (tem) 2027 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem)))) 2028 { 2029 extract_range_from_ssa_name (vr, tem); 2030 return; 2031 } 2032 else if (is_gimple_min_invariant (tem)) 2033 { 2034 vr->set (tem); 2035 return; 2036 } 2037 } 2038 /* Then dispatch to value-range extracting functions. */ 2039 if (code == GIMPLE_CALL) 2040 extract_range_basic (vr, stmt); 2041 else 2042 extract_range_from_assignment (vr, as_a <gassign *> (stmt)); 2043 } 2044 } 2045 2046 /* Helper that gets the value range of the SSA_NAME with version I 2047 or a symbolic range containing the SSA_NAME only if the value range 2048 is varying or undefined. Uses TEM as storage for the alternate range. */ 2049 2050 value_range * 2051 vr_values::get_vr_for_comparison (int i, value_range *tem) 2052 { 2053 /* Shallow-copy equiv bitmap. */ 2054 value_range *vr = get_value_range (ssa_name (i)); 2055 2056 /* If name N_i does not have a valid range, use N_i as its own 2057 range. This allows us to compare against names that may 2058 have N_i in their ranges. */ 2059 if (vr->varying_p () || vr->undefined_p ()) 2060 { 2061 tem->set (ssa_name (i)); 2062 return tem; 2063 } 2064 2065 return vr; 2066 } 2067 2068 /* Compare all the value ranges for names equivalent to VAR with VAL 2069 using comparison code COMP. Return the same value returned by 2070 compare_range_with_value, including the setting of 2071 *STRICT_OVERFLOW_P. */ 2072 2073 tree 2074 vr_values::compare_name_with_value (enum tree_code comp, tree var, tree val, 2075 bool *strict_overflow_p, bool use_equiv_p) 2076 { 2077 bitmap_iterator bi; 2078 unsigned i; 2079 bitmap e; 2080 tree retval, t; 2081 int used_strict_overflow; 2082 bool sop; 2083 value_range *equiv_vr, tem_vr; 2084 2085 /* Get the set of equivalences for VAR. */ 2086 e = get_value_range (var)->equiv (); 2087 2088 /* Start at -1. Set it to 0 if we do a comparison without relying 2089 on overflow, or 1 if all comparisons rely on overflow. */ 2090 used_strict_overflow = -1; 2091 2092 /* Compare vars' value range with val. */ 2093 equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var), &tem_vr); 2094 sop = false; 2095 retval = compare_range_with_value (comp, equiv_vr, val, &sop); 2096 if (retval) 2097 used_strict_overflow = sop ? 1 : 0; 2098 2099 /* If the equiv set is empty we have done all work we need to do. */ 2100 if (e == NULL) 2101 { 2102 if (retval 2103 && used_strict_overflow > 0) 2104 *strict_overflow_p = true; 2105 return retval; 2106 } 2107 2108 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) 2109 { 2110 tree name = ssa_name (i); 2111 if (! name) 2112 continue; 2113 2114 if (! use_equiv_p 2115 && ! SSA_NAME_IS_DEFAULT_DEF (name) 2116 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name))) 2117 continue; 2118 2119 equiv_vr = get_vr_for_comparison (i, &tem_vr); 2120 sop = false; 2121 t = compare_range_with_value (comp, equiv_vr, val, &sop); 2122 if (t) 2123 { 2124 /* If we get different answers from different members 2125 of the equivalence set this check must be in a dead 2126 code region. Folding it to a trap representation 2127 would be correct here. For now just return don't-know. */ 2128 if (retval != NULL 2129 && t != retval) 2130 { 2131 retval = NULL_TREE; 2132 break; 2133 } 2134 retval = t; 2135 2136 if (!sop) 2137 used_strict_overflow = 0; 2138 else if (used_strict_overflow < 0) 2139 used_strict_overflow = 1; 2140 } 2141 } 2142 2143 if (retval 2144 && used_strict_overflow > 0) 2145 *strict_overflow_p = true; 2146 2147 return retval; 2148 } 2149 2150 2151 /* Given a comparison code COMP and names N1 and N2, compare all the 2152 ranges equivalent to N1 against all the ranges equivalent to N2 2153 to determine the value of N1 COMP N2. Return the same value 2154 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate 2155 whether we relied on undefined signed overflow in the comparison. */ 2156 2157 2158 tree 2159 vr_values::compare_names (enum tree_code comp, tree n1, tree n2, 2160 bool *strict_overflow_p) 2161 { 2162 tree t, retval; 2163 bitmap e1, e2; 2164 bitmap_iterator bi1, bi2; 2165 unsigned i1, i2; 2166 int used_strict_overflow; 2167 static bitmap_obstack *s_obstack = NULL; 2168 static bitmap s_e1 = NULL, s_e2 = NULL; 2169 2170 /* Compare the ranges of every name equivalent to N1 against the 2171 ranges of every name equivalent to N2. */ 2172 e1 = get_value_range (n1)->equiv (); 2173 e2 = get_value_range (n2)->equiv (); 2174 2175 /* Use the fake bitmaps if e1 or e2 are not available. */ 2176 if (s_obstack == NULL) 2177 { 2178 s_obstack = XNEW (bitmap_obstack); 2179 bitmap_obstack_initialize (s_obstack); 2180 s_e1 = BITMAP_ALLOC (s_obstack); 2181 s_e2 = BITMAP_ALLOC (s_obstack); 2182 } 2183 if (e1 == NULL) 2184 e1 = s_e1; 2185 if (e2 == NULL) 2186 e2 = s_e2; 2187 2188 /* Add N1 and N2 to their own set of equivalences to avoid 2189 duplicating the body of the loop just to check N1 and N2 2190 ranges. */ 2191 bitmap_set_bit (e1, SSA_NAME_VERSION (n1)); 2192 bitmap_set_bit (e2, SSA_NAME_VERSION (n2)); 2193 2194 /* If the equivalence sets have a common intersection, then the two 2195 names can be compared without checking their ranges. */ 2196 if (bitmap_intersect_p (e1, e2)) 2197 { 2198 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 2199 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 2200 2201 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR) 2202 ? boolean_true_node 2203 : boolean_false_node; 2204 } 2205 2206 /* Start at -1. Set it to 0 if we do a comparison without relying 2207 on overflow, or 1 if all comparisons rely on overflow. */ 2208 used_strict_overflow = -1; 2209 2210 /* Otherwise, compare all the equivalent ranges. First, add N1 and 2211 N2 to their own set of equivalences to avoid duplicating the body 2212 of the loop just to check N1 and N2 ranges. */ 2213 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) 2214 { 2215 if (! ssa_name (i1)) 2216 continue; 2217 2218 value_range tem_vr1; 2219 value_range *vr1 = get_vr_for_comparison (i1, &tem_vr1); 2220 2221 t = retval = NULL_TREE; 2222 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) 2223 { 2224 if (! ssa_name (i2)) 2225 continue; 2226 2227 bool sop = false; 2228 2229 value_range tem_vr2; 2230 value_range *vr2 = get_vr_for_comparison (i2, &tem_vr2); 2231 2232 t = compare_ranges (comp, vr1, vr2, &sop); 2233 if (t) 2234 { 2235 /* If we get different answers from different members 2236 of the equivalence set this check must be in a dead 2237 code region. Folding it to a trap representation 2238 would be correct here. For now just return don't-know. */ 2239 if (retval != NULL 2240 && t != retval) 2241 { 2242 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 2243 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 2244 return NULL_TREE; 2245 } 2246 retval = t; 2247 2248 if (!sop) 2249 used_strict_overflow = 0; 2250 else if (used_strict_overflow < 0) 2251 used_strict_overflow = 1; 2252 } 2253 } 2254 2255 if (retval) 2256 { 2257 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 2258 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 2259 if (used_strict_overflow > 0) 2260 *strict_overflow_p = true; 2261 return retval; 2262 } 2263 } 2264 2265 /* None of the equivalent ranges are useful in computing this 2266 comparison. */ 2267 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 2268 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 2269 return NULL_TREE; 2270 } 2271 2272 /* Helper function for vrp_evaluate_conditional_warnv & other 2273 optimizers. */ 2274 2275 tree 2276 vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges 2277 (enum tree_code code, tree op0, tree op1, bool * strict_overflow_p) 2278 { 2279 value_range *vr0, *vr1; 2280 2281 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL; 2282 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; 2283 2284 tree res = NULL_TREE; 2285 if (vr0 && vr1) 2286 res = compare_ranges (code, vr0, vr1, strict_overflow_p); 2287 if (!res && vr0) 2288 res = compare_range_with_value (code, vr0, op1, strict_overflow_p); 2289 if (!res && vr1) 2290 res = (compare_range_with_value 2291 (swap_tree_comparison (code), vr1, op0, strict_overflow_p)); 2292 return res; 2293 } 2294 2295 /* Helper function for vrp_evaluate_conditional_warnv. */ 2296 2297 tree 2298 vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code, 2299 tree op0, tree op1, 2300 bool use_equiv_p, 2301 bool *strict_overflow_p, 2302 bool *only_ranges) 2303 { 2304 tree ret; 2305 if (only_ranges) 2306 *only_ranges = true; 2307 2308 /* We only deal with integral and pointer types. */ 2309 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 2310 && !POINTER_TYPE_P (TREE_TYPE (op0))) 2311 return NULL_TREE; 2312 2313 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed 2314 as a simple equality test, then prefer that over its current form 2315 for evaluation. 2316 2317 An overflow test which collapses to an equality test can always be 2318 expressed as a comparison of one argument against zero. Overflow 2319 occurs when the chosen argument is zero and does not occur if the 2320 chosen argument is not zero. */ 2321 tree x; 2322 if (overflow_comparison_p (code, op0, op1, use_equiv_p, &x)) 2323 { 2324 wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED); 2325 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0) 2326 B = A - 1; if (A > B) -> B = A - 1; if (A != 0) 2327 B = A + 1; if (B < A) -> B = A + 1; if (B == 0) 2328 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */ 2329 if (integer_zerop (x)) 2330 { 2331 op1 = x; 2332 code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR; 2333 } 2334 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0) 2335 B = A + 1; if (A < B) -> B = A + 1; if (B != 0) 2336 B = A - 1; if (B > A) -> B = A - 1; if (A == 0) 2337 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */ 2338 else if (wi::to_wide (x) == max - 1) 2339 { 2340 op0 = op1; 2341 op1 = wide_int_to_tree (TREE_TYPE (op0), 0); 2342 code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR; 2343 } 2344 else 2345 { 2346 value_range vro, vri; 2347 if (code == GT_EXPR || code == GE_EXPR) 2348 { 2349 vro.set (VR_ANTI_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x); 2350 vri.set (VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x); 2351 } 2352 else if (code == LT_EXPR || code == LE_EXPR) 2353 { 2354 vro.set (VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x); 2355 vri.set (VR_ANTI_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x); 2356 } 2357 else 2358 gcc_unreachable (); 2359 value_range *vr0 = get_value_range (op0); 2360 /* If vro, the range for OP0 to pass the overflow test, has 2361 no intersection with *vr0, OP0's known range, then the 2362 overflow test can't pass, so return the node for false. 2363 If it is the inverted range, vri, that has no 2364 intersection, then the overflow test must pass, so return 2365 the node for true. In other cases, we could proceed with 2366 a simplified condition comparing OP0 and X, with LE_EXPR 2367 for previously LE_ or LT_EXPR and GT_EXPR otherwise, but 2368 the comments next to the enclosing if suggest it's not 2369 generally profitable to do so. */ 2370 vro.intersect (vr0); 2371 if (vro.undefined_p ()) 2372 return boolean_false_node; 2373 vri.intersect (vr0); 2374 if (vri.undefined_p ()) 2375 return boolean_true_node; 2376 } 2377 } 2378 2379 if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges 2380 (code, op0, op1, strict_overflow_p))) 2381 return ret; 2382 if (only_ranges) 2383 *only_ranges = false; 2384 /* Do not use compare_names during propagation, it's quadratic. */ 2385 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME 2386 && use_equiv_p) 2387 return compare_names (code, op0, op1, strict_overflow_p); 2388 else if (TREE_CODE (op0) == SSA_NAME) 2389 return compare_name_with_value (code, op0, op1, 2390 strict_overflow_p, use_equiv_p); 2391 else if (TREE_CODE (op1) == SSA_NAME) 2392 return compare_name_with_value (swap_tree_comparison (code), op1, op0, 2393 strict_overflow_p, use_equiv_p); 2394 return NULL_TREE; 2395 } 2396 2397 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range 2398 information. Return NULL if the conditional cannot be evaluated. 2399 The ranges of all the names equivalent with the operands in COND 2400 will be used when trying to compute the value. If the result is 2401 based on undefined signed overflow, issue a warning if 2402 appropriate. */ 2403 2404 tree 2405 vr_values::vrp_evaluate_conditional (tree_code code, tree op0, 2406 tree op1, gimple *stmt) 2407 { 2408 bool sop; 2409 tree ret; 2410 bool only_ranges; 2411 2412 /* Some passes and foldings leak constants with overflow flag set 2413 into the IL. Avoid doing wrong things with these and bail out. */ 2414 if ((TREE_CODE (op0) == INTEGER_CST 2415 && TREE_OVERFLOW (op0)) 2416 || (TREE_CODE (op1) == INTEGER_CST 2417 && TREE_OVERFLOW (op1))) 2418 return NULL_TREE; 2419 2420 sop = false; 2421 ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop, 2422 &only_ranges); 2423 2424 if (ret && sop) 2425 { 2426 enum warn_strict_overflow_code wc; 2427 const char* warnmsg; 2428 2429 if (is_gimple_min_invariant (ret)) 2430 { 2431 wc = WARN_STRICT_OVERFLOW_CONDITIONAL; 2432 warnmsg = G_("assuming signed overflow does not occur when " 2433 "simplifying conditional to constant"); 2434 } 2435 else 2436 { 2437 wc = WARN_STRICT_OVERFLOW_COMPARISON; 2438 warnmsg = G_("assuming signed overflow does not occur when " 2439 "simplifying conditional"); 2440 } 2441 2442 if (issue_strict_overflow_warning (wc)) 2443 { 2444 location_t location; 2445 2446 if (!gimple_has_location (stmt)) 2447 location = input_location; 2448 else 2449 location = gimple_location (stmt); 2450 warning_at (location, OPT_Wstrict_overflow, "%s", warnmsg); 2451 } 2452 } 2453 2454 if (warn_type_limits 2455 && ret && only_ranges 2456 && TREE_CODE_CLASS (code) == tcc_comparison 2457 && TREE_CODE (op0) == SSA_NAME) 2458 { 2459 /* If the comparison is being folded and the operand on the LHS 2460 is being compared against a constant value that is outside of 2461 the natural range of OP0's type, then the predicate will 2462 always fold regardless of the value of OP0. If -Wtype-limits 2463 was specified, emit a warning. */ 2464 tree type = TREE_TYPE (op0); 2465 value_range *vr0 = get_value_range (op0); 2466 2467 if (vr0->kind () == VR_RANGE 2468 && INTEGRAL_TYPE_P (type) 2469 && vrp_val_is_min (vr0->min ()) 2470 && vrp_val_is_max (vr0->max ()) 2471 && is_gimple_min_invariant (op1)) 2472 { 2473 location_t location; 2474 2475 if (!gimple_has_location (stmt)) 2476 location = input_location; 2477 else 2478 location = gimple_location (stmt); 2479 2480 warning_at (location, OPT_Wtype_limits, 2481 integer_zerop (ret) 2482 ? G_("comparison always false " 2483 "due to limited range of data type") 2484 : G_("comparison always true " 2485 "due to limited range of data type")); 2486 } 2487 } 2488 2489 return ret; 2490 } 2491 2492 2493 /* Visit conditional statement STMT. If we can determine which edge 2494 will be taken out of STMT's basic block, record it in 2495 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */ 2496 2497 void 2498 vr_values::vrp_visit_cond_stmt (gcond *stmt, edge *taken_edge_p) 2499 { 2500 tree val; 2501 2502 *taken_edge_p = NULL; 2503 2504 if (dump_file && (dump_flags & TDF_DETAILS)) 2505 { 2506 tree use; 2507 ssa_op_iter i; 2508 2509 fprintf (dump_file, "\nVisiting conditional with predicate: "); 2510 print_gimple_stmt (dump_file, stmt, 0); 2511 fprintf (dump_file, "\nWith known ranges\n"); 2512 2513 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) 2514 { 2515 fprintf (dump_file, "\t"); 2516 print_generic_expr (dump_file, use); 2517 fprintf (dump_file, ": "); 2518 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]); 2519 } 2520 2521 fprintf (dump_file, "\n"); 2522 } 2523 2524 /* Compute the value of the predicate COND by checking the known 2525 ranges of each of its operands. 2526 2527 Note that we cannot evaluate all the equivalent ranges here 2528 because those ranges may not yet be final and with the current 2529 propagation strategy, we cannot determine when the value ranges 2530 of the names in the equivalence set have changed. 2531 2532 For instance, given the following code fragment 2533 2534 i_5 = PHI <8, i_13> 2535 ... 2536 i_14 = ASSERT_EXPR <i_5, i_5 != 0> 2537 if (i_14 == 1) 2538 ... 2539 2540 Assume that on the first visit to i_14, i_5 has the temporary 2541 range [8, 8] because the second argument to the PHI function is 2542 not yet executable. We derive the range ~[0, 0] for i_14 and the 2543 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for 2544 the first time, since i_14 is equivalent to the range [8, 8], we 2545 determine that the predicate is always false. 2546 2547 On the next round of propagation, i_13 is determined to be 2548 VARYING, which causes i_5 to drop down to VARYING. So, another 2549 visit to i_14 is scheduled. In this second visit, we compute the 2550 exact same range and equivalence set for i_14, namely ~[0, 0] and 2551 { i_5 }. But we did not have the previous range for i_5 2552 registered, so vrp_visit_assignment thinks that the range for 2553 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)' 2554 is not visited again, which stops propagation from visiting 2555 statements in the THEN clause of that if(). 2556 2557 To properly fix this we would need to keep the previous range 2558 value for the names in the equivalence set. This way we would've 2559 discovered that from one visit to the other i_5 changed from 2560 range [8, 8] to VR_VARYING. 2561 2562 However, fixing this apparent limitation may not be worth the 2563 additional checking. Testing on several code bases (GCC, DLV, 2564 MICO, TRAMP3D and SPEC2000) showed that doing this results in 2565 4 more predicates folded in SPEC. */ 2566 2567 bool sop; 2568 val = vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt), 2569 gimple_cond_lhs (stmt), 2570 gimple_cond_rhs (stmt), 2571 false, &sop, NULL); 2572 if (val) 2573 *taken_edge_p = find_taken_edge (gimple_bb (stmt), val); 2574 2575 if (dump_file && (dump_flags & TDF_DETAILS)) 2576 { 2577 fprintf (dump_file, "\nPredicate evaluates to: "); 2578 if (val == NULL_TREE) 2579 fprintf (dump_file, "DON'T KNOW\n"); 2580 else 2581 print_generic_stmt (dump_file, val); 2582 } 2583 } 2584 2585 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are 2586 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and 2587 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1. 2588 Returns true if the default label is not needed. */ 2589 2590 static bool 2591 find_case_label_ranges (gswitch *stmt, value_range *vr, size_t *min_idx1, 2592 size_t *max_idx1, size_t *min_idx2, 2593 size_t *max_idx2) 2594 { 2595 size_t i, j, k, l; 2596 unsigned int n = gimple_switch_num_labels (stmt); 2597 bool take_default; 2598 tree case_low, case_high; 2599 tree min = vr->min (), max = vr->max (); 2600 2601 gcc_checking_assert (!vr->varying_p () && !vr->undefined_p ()); 2602 2603 take_default = !find_case_label_range (stmt, min, max, &i, &j); 2604 2605 /* Set second range to empty. */ 2606 *min_idx2 = 1; 2607 *max_idx2 = 0; 2608 2609 if (vr->kind () == VR_RANGE) 2610 { 2611 *min_idx1 = i; 2612 *max_idx1 = j; 2613 return !take_default; 2614 } 2615 2616 /* Set first range to all case labels. */ 2617 *min_idx1 = 1; 2618 *max_idx1 = n - 1; 2619 2620 if (i > j) 2621 return false; 2622 2623 /* Make sure all the values of case labels [i , j] are contained in 2624 range [MIN, MAX]. */ 2625 case_low = CASE_LOW (gimple_switch_label (stmt, i)); 2626 case_high = CASE_HIGH (gimple_switch_label (stmt, j)); 2627 if (tree_int_cst_compare (case_low, min) < 0) 2628 i += 1; 2629 if (case_high != NULL_TREE 2630 && tree_int_cst_compare (max, case_high) < 0) 2631 j -= 1; 2632 2633 if (i > j) 2634 return false; 2635 2636 /* If the range spans case labels [i, j], the corresponding anti-range spans 2637 the labels [1, i - 1] and [j + 1, n - 1]. */ 2638 k = j + 1; 2639 l = n - 1; 2640 if (k > l) 2641 { 2642 k = 1; 2643 l = 0; 2644 } 2645 2646 j = i - 1; 2647 i = 1; 2648 if (i > j) 2649 { 2650 i = k; 2651 j = l; 2652 k = 1; 2653 l = 0; 2654 } 2655 2656 *min_idx1 = i; 2657 *max_idx1 = j; 2658 *min_idx2 = k; 2659 *max_idx2 = l; 2660 return false; 2661 } 2662 2663 /* Visit switch statement STMT. If we can determine which edge 2664 will be taken out of STMT's basic block, record it in 2665 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */ 2666 2667 void 2668 vr_values::vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p) 2669 { 2670 tree op, val; 2671 value_range *vr; 2672 size_t i = 0, j = 0, k, l; 2673 bool take_default; 2674 2675 *taken_edge_p = NULL; 2676 op = gimple_switch_index (stmt); 2677 if (TREE_CODE (op) != SSA_NAME) 2678 return; 2679 2680 vr = get_value_range (op); 2681 if (dump_file && (dump_flags & TDF_DETAILS)) 2682 { 2683 fprintf (dump_file, "\nVisiting switch expression with operand "); 2684 print_generic_expr (dump_file, op); 2685 fprintf (dump_file, " with known range "); 2686 dump_value_range (dump_file, vr); 2687 fprintf (dump_file, "\n"); 2688 } 2689 2690 if (vr->undefined_p () 2691 || vr->varying_p () 2692 || vr->symbolic_p ()) 2693 return; 2694 2695 /* Find the single edge that is taken from the switch expression. */ 2696 take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l); 2697 2698 /* Check if the range spans no CASE_LABEL. If so, we only reach the default 2699 label */ 2700 if (j < i) 2701 { 2702 gcc_assert (take_default); 2703 val = gimple_switch_default_label (stmt); 2704 } 2705 else 2706 { 2707 /* Check if labels with index i to j and maybe the default label 2708 are all reaching the same label. */ 2709 2710 val = gimple_switch_label (stmt, i); 2711 if (take_default 2712 && CASE_LABEL (gimple_switch_default_label (stmt)) 2713 != CASE_LABEL (val)) 2714 { 2715 if (dump_file && (dump_flags & TDF_DETAILS)) 2716 fprintf (dump_file, " not a single destination for this " 2717 "range\n"); 2718 return; 2719 } 2720 for (++i; i <= j; ++i) 2721 { 2722 if (CASE_LABEL (gimple_switch_label (stmt, i)) != CASE_LABEL (val)) 2723 { 2724 if (dump_file && (dump_flags & TDF_DETAILS)) 2725 fprintf (dump_file, " not a single destination for this " 2726 "range\n"); 2727 return; 2728 } 2729 } 2730 for (; k <= l; ++k) 2731 { 2732 if (CASE_LABEL (gimple_switch_label (stmt, k)) != CASE_LABEL (val)) 2733 { 2734 if (dump_file && (dump_flags & TDF_DETAILS)) 2735 fprintf (dump_file, " not a single destination for this " 2736 "range\n"); 2737 return; 2738 } 2739 } 2740 } 2741 2742 *taken_edge_p = find_edge (gimple_bb (stmt), 2743 label_to_block (cfun, CASE_LABEL (val))); 2744 2745 if (dump_file && (dump_flags & TDF_DETAILS)) 2746 { 2747 fprintf (dump_file, " will take edge to "); 2748 print_generic_stmt (dump_file, CASE_LABEL (val)); 2749 } 2750 } 2751 2752 2753 /* Evaluate statement STMT. If the statement produces a useful range, 2754 set VR and corepsponding OUTPUT_P. 2755 2756 If STMT is a conditional branch and we can determine its truth 2757 value, the taken edge is recorded in *TAKEN_EDGE_P. */ 2758 2759 void 2760 vr_values::extract_range_from_stmt (gimple *stmt, edge *taken_edge_p, 2761 tree *output_p, value_range *vr) 2762 { 2763 2764 if (dump_file && (dump_flags & TDF_DETAILS)) 2765 { 2766 fprintf (dump_file, "\nVisiting statement:\n"); 2767 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 2768 } 2769 2770 if (!stmt_interesting_for_vrp (stmt)) 2771 gcc_assert (stmt_ends_bb_p (stmt)); 2772 else if (is_gimple_assign (stmt) || is_gimple_call (stmt)) 2773 vrp_visit_assignment_or_call (stmt, output_p, vr); 2774 else if (gimple_code (stmt) == GIMPLE_COND) 2775 vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p); 2776 else if (gimple_code (stmt) == GIMPLE_SWITCH) 2777 vrp_visit_switch_stmt (as_a <gswitch *> (stmt), taken_edge_p); 2778 } 2779 2780 /* Visit all arguments for PHI node PHI that flow through executable 2781 edges. If a valid value range can be derived from all the incoming 2782 value ranges, set a new range in VR_RESULT. */ 2783 2784 void 2785 vr_values::extract_range_from_phi_node (gphi *phi, value_range *vr_result) 2786 { 2787 size_t i; 2788 tree lhs = PHI_RESULT (phi); 2789 value_range *lhs_vr = get_value_range (lhs); 2790 bool first = true; 2791 int edges, old_edges; 2792 struct loop *l; 2793 2794 if (dump_file && (dump_flags & TDF_DETAILS)) 2795 { 2796 fprintf (dump_file, "\nVisiting PHI node: "); 2797 print_gimple_stmt (dump_file, phi, 0, dump_flags); 2798 } 2799 2800 bool may_simulate_backedge_again = false; 2801 edges = 0; 2802 for (i = 0; i < gimple_phi_num_args (phi); i++) 2803 { 2804 edge e = gimple_phi_arg_edge (phi, i); 2805 2806 if (dump_file && (dump_flags & TDF_DETAILS)) 2807 { 2808 fprintf (dump_file, 2809 " Argument #%d (%d -> %d %sexecutable)\n", 2810 (int) i, e->src->index, e->dest->index, 2811 (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 2812 } 2813 2814 if (e->flags & EDGE_EXECUTABLE) 2815 { 2816 tree arg = PHI_ARG_DEF (phi, i); 2817 value_range vr_arg_tem; 2818 value_range *vr_arg = &vr_arg_tem; 2819 2820 ++edges; 2821 2822 if (TREE_CODE (arg) == SSA_NAME) 2823 { 2824 /* See if we are eventually going to change one of the args. */ 2825 gimple *def_stmt = SSA_NAME_DEF_STMT (arg); 2826 if (! gimple_nop_p (def_stmt) 2827 && prop_simulate_again_p (def_stmt) 2828 && e->flags & EDGE_DFS_BACK) 2829 may_simulate_backedge_again = true; 2830 2831 value_range *vr_arg_ = get_value_range (arg); 2832 /* Do not allow equivalences or symbolic ranges to leak in from 2833 backedges. That creates invalid equivalencies. 2834 See PR53465 and PR54767. */ 2835 if (e->flags & EDGE_DFS_BACK) 2836 { 2837 if (!vr_arg_->varying_p () && !vr_arg_->undefined_p ()) 2838 { 2839 vr_arg_tem.set (vr_arg_->kind (), vr_arg_->min (), 2840 vr_arg_->max (), NULL); 2841 if (vr_arg_tem.symbolic_p ()) 2842 vr_arg_tem.set_varying (); 2843 } 2844 else 2845 vr_arg = vr_arg_; 2846 } 2847 /* If the non-backedge arguments range is VR_VARYING then 2848 we can still try recording a simple equivalence. */ 2849 else if (vr_arg_->varying_p ()) 2850 vr_arg_tem.set (arg); 2851 else 2852 vr_arg = vr_arg_; 2853 } 2854 else 2855 { 2856 if (TREE_OVERFLOW_P (arg)) 2857 arg = drop_tree_overflow (arg); 2858 2859 vr_arg_tem.set (arg); 2860 } 2861 2862 if (dump_file && (dump_flags & TDF_DETAILS)) 2863 { 2864 fprintf (dump_file, "\t"); 2865 print_generic_expr (dump_file, arg, dump_flags); 2866 fprintf (dump_file, ": "); 2867 dump_value_range (dump_file, vr_arg); 2868 fprintf (dump_file, "\n"); 2869 } 2870 2871 if (first) 2872 vr_result->deep_copy (vr_arg); 2873 else 2874 vr_result->union_ (vr_arg); 2875 first = false; 2876 2877 if (vr_result->varying_p ()) 2878 break; 2879 } 2880 } 2881 2882 if (vr_result->varying_p ()) 2883 goto varying; 2884 else if (vr_result->undefined_p ()) 2885 goto update_range; 2886 2887 old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)]; 2888 vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges; 2889 2890 /* To prevent infinite iterations in the algorithm, derive ranges 2891 when the new value is slightly bigger or smaller than the 2892 previous one. We don't do this if we have seen a new executable 2893 edge; this helps us avoid an infinity for conditionals 2894 which are not in a loop. If the old value-range was VR_UNDEFINED 2895 use the updated range and iterate one more time. If we will not 2896 simulate this PHI again via the backedge allow us to iterate. */ 2897 if (edges > 0 2898 && gimple_phi_num_args (phi) > 1 2899 && edges == old_edges 2900 && !lhs_vr->undefined_p () 2901 && may_simulate_backedge_again) 2902 { 2903 /* Compare old and new ranges, fall back to varying if the 2904 values are not comparable. */ 2905 int cmp_min = compare_values (lhs_vr->min (), vr_result->min ()); 2906 if (cmp_min == -2) 2907 goto varying; 2908 int cmp_max = compare_values (lhs_vr->max (), vr_result->max ()); 2909 if (cmp_max == -2) 2910 goto varying; 2911 2912 /* For non VR_RANGE or for pointers fall back to varying if 2913 the range changed. */ 2914 if ((lhs_vr->kind () != VR_RANGE || vr_result->kind () != VR_RANGE 2915 || POINTER_TYPE_P (TREE_TYPE (lhs))) 2916 && (cmp_min != 0 || cmp_max != 0)) 2917 goto varying; 2918 2919 /* If the new minimum is larger than the previous one 2920 retain the old value. If the new minimum value is smaller 2921 than the previous one and not -INF go all the way to -INF + 1. 2922 In the first case, to avoid infinite bouncing between different 2923 minimums, and in the other case to avoid iterating millions of 2924 times to reach -INF. Going to -INF + 1 also lets the following 2925 iteration compute whether there will be any overflow, at the 2926 expense of one additional iteration. */ 2927 tree new_min = vr_result->min (); 2928 tree new_max = vr_result->max (); 2929 if (cmp_min < 0) 2930 new_min = lhs_vr->min (); 2931 else if (cmp_min > 0 2932 && (TREE_CODE (vr_result->min ()) != INTEGER_CST 2933 || tree_int_cst_lt (vrp_val_min (vr_result->type ()), 2934 vr_result->min ()))) 2935 new_min = int_const_binop (PLUS_EXPR, 2936 vrp_val_min (vr_result->type ()), 2937 build_int_cst (vr_result->type (), 1)); 2938 2939 /* Similarly for the maximum value. */ 2940 if (cmp_max > 0) 2941 new_max = lhs_vr->max (); 2942 else if (cmp_max < 0 2943 && (TREE_CODE (vr_result->max ()) != INTEGER_CST 2944 || tree_int_cst_lt (vr_result->max (), 2945 vrp_val_max (vr_result->type ())))) 2946 new_max = int_const_binop (MINUS_EXPR, 2947 vrp_val_max (vr_result->type ()), 2948 build_int_cst (vr_result->type (), 1)); 2949 2950 vr_result->update (vr_result->kind (), new_min, new_max); 2951 2952 /* If we dropped either bound to +-INF then if this is a loop 2953 PHI node SCEV may known more about its value-range. */ 2954 if (cmp_min > 0 || cmp_min < 0 2955 || cmp_max < 0 || cmp_max > 0) 2956 goto scev_check; 2957 2958 goto infinite_check; 2959 } 2960 2961 goto update_range; 2962 2963 varying: 2964 vr_result->set_varying (); 2965 2966 scev_check: 2967 /* If this is a loop PHI node SCEV may known more about its value-range. 2968 scev_check can be reached from two paths, one is a fall through from above 2969 "varying" label, the other is direct goto from code block which tries to 2970 avoid infinite simulation. */ 2971 if (scev_initialized_p () 2972 && (l = loop_containing_stmt (phi)) 2973 && l->header == gimple_bb (phi)) 2974 adjust_range_with_scev (vr_result, l, phi, lhs); 2975 2976 infinite_check: 2977 /* If we will end up with a (-INF, +INF) range, set it to 2978 VARYING. Same if the previous max value was invalid for 2979 the type and we end up with vr_result.min > vr_result.max. */ 2980 if ((!vr_result->varying_p () && !vr_result->undefined_p ()) 2981 && !((vrp_val_is_max (vr_result->max ()) && vrp_val_is_min (vr_result->min ())) 2982 || compare_values (vr_result->min (), vr_result->max ()) > 0)) 2983 ; 2984 else 2985 vr_result->set_varying (); 2986 2987 /* If the new range is different than the previous value, keep 2988 iterating. */ 2989 update_range: 2990 return; 2991 } 2992 2993 /* Simplify boolean operations if the source is known 2994 to be already a boolean. */ 2995 bool 2996 vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, 2997 gimple *stmt) 2998 { 2999 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 3000 tree lhs, op0, op1; 3001 bool need_conversion; 3002 3003 /* We handle only !=/== case here. */ 3004 gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR); 3005 3006 op0 = gimple_assign_rhs1 (stmt); 3007 if (!op_with_boolean_value_range_p (op0)) 3008 return false; 3009 3010 op1 = gimple_assign_rhs2 (stmt); 3011 if (!op_with_boolean_value_range_p (op1)) 3012 return false; 3013 3014 /* Reduce number of cases to handle to NE_EXPR. As there is no 3015 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */ 3016 if (rhs_code == EQ_EXPR) 3017 { 3018 if (TREE_CODE (op1) == INTEGER_CST) 3019 op1 = int_const_binop (BIT_XOR_EXPR, op1, 3020 build_int_cst (TREE_TYPE (op1), 1)); 3021 else 3022 return false; 3023 } 3024 3025 lhs = gimple_assign_lhs (stmt); 3026 need_conversion 3027 = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)); 3028 3029 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */ 3030 if (need_conversion 3031 && !TYPE_UNSIGNED (TREE_TYPE (op0)) 3032 && TYPE_PRECISION (TREE_TYPE (op0)) == 1 3033 && TYPE_PRECISION (TREE_TYPE (lhs)) > 1) 3034 return false; 3035 3036 /* For A != 0 we can substitute A itself. */ 3037 if (integer_zerop (op1)) 3038 gimple_assign_set_rhs_with_ops (gsi, 3039 need_conversion 3040 ? NOP_EXPR : TREE_CODE (op0), op0); 3041 /* For A != B we substitute A ^ B. Either with conversion. */ 3042 else if (need_conversion) 3043 { 3044 tree tem = make_ssa_name (TREE_TYPE (op0)); 3045 gassign *newop 3046 = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1); 3047 gsi_insert_before (gsi, newop, GSI_SAME_STMT); 3048 if (INTEGRAL_TYPE_P (TREE_TYPE (tem)) 3049 && TYPE_PRECISION (TREE_TYPE (tem)) > 1) 3050 set_range_info (tem, VR_RANGE, 3051 wi::zero (TYPE_PRECISION (TREE_TYPE (tem))), 3052 wi::one (TYPE_PRECISION (TREE_TYPE (tem)))); 3053 gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem); 3054 } 3055 /* Or without. */ 3056 else 3057 gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1); 3058 update_stmt (gsi_stmt (*gsi)); 3059 fold_stmt (gsi, follow_single_use_edges); 3060 3061 return true; 3062 } 3063 3064 /* Simplify a division or modulo operator to a right shift or bitwise and 3065 if the first operand is unsigned or is greater than zero and the second 3066 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with 3067 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range, 3068 optimize it into just op0 if op0's range is known to be a subset of 3069 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned 3070 modulo. */ 3071 3072 bool 3073 vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator *gsi, 3074 gimple *stmt) 3075 { 3076 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 3077 tree val = NULL; 3078 tree op0 = gimple_assign_rhs1 (stmt); 3079 tree op1 = gimple_assign_rhs2 (stmt); 3080 tree op0min = NULL_TREE, op0max = NULL_TREE; 3081 tree op1min = op1; 3082 value_range *vr = NULL; 3083 3084 if (TREE_CODE (op0) == INTEGER_CST) 3085 { 3086 op0min = op0; 3087 op0max = op0; 3088 } 3089 else 3090 { 3091 vr = get_value_range (op0); 3092 if (range_int_cst_p (vr)) 3093 { 3094 op0min = vr->min (); 3095 op0max = vr->max (); 3096 } 3097 } 3098 3099 if (rhs_code == TRUNC_MOD_EXPR 3100 && TREE_CODE (op1) == SSA_NAME) 3101 { 3102 value_range *vr1 = get_value_range (op1); 3103 if (range_int_cst_p (vr1)) 3104 op1min = vr1->min (); 3105 } 3106 if (rhs_code == TRUNC_MOD_EXPR 3107 && TREE_CODE (op1min) == INTEGER_CST 3108 && tree_int_cst_sgn (op1min) == 1 3109 && op0max 3110 && tree_int_cst_lt (op0max, op1min)) 3111 { 3112 if (TYPE_UNSIGNED (TREE_TYPE (op0)) 3113 || tree_int_cst_sgn (op0min) >= 0 3114 || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min), 3115 op0min)) 3116 { 3117 /* If op0 already has the range op0 % op1 has, 3118 then TRUNC_MOD_EXPR won't change anything. */ 3119 gimple_assign_set_rhs_from_tree (gsi, op0); 3120 return true; 3121 } 3122 } 3123 3124 if (TREE_CODE (op0) != SSA_NAME) 3125 return false; 3126 3127 if (!integer_pow2p (op1)) 3128 { 3129 /* X % -Y can be only optimized into X % Y either if 3130 X is not INT_MIN, or Y is not -1. Fold it now, as after 3131 remove_range_assertions the range info might be not available 3132 anymore. */ 3133 if (rhs_code == TRUNC_MOD_EXPR 3134 && fold_stmt (gsi, follow_single_use_edges)) 3135 return true; 3136 return false; 3137 } 3138 3139 if (TYPE_UNSIGNED (TREE_TYPE (op0))) 3140 val = integer_one_node; 3141 else 3142 { 3143 bool sop = false; 3144 3145 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop); 3146 3147 if (val 3148 && sop 3149 && integer_onep (val) 3150 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 3151 { 3152 location_t location; 3153 3154 if (!gimple_has_location (stmt)) 3155 location = input_location; 3156 else 3157 location = gimple_location (stmt); 3158 warning_at (location, OPT_Wstrict_overflow, 3159 "assuming signed overflow does not occur when " 3160 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>"); 3161 } 3162 } 3163 3164 if (val && integer_onep (val)) 3165 { 3166 tree t; 3167 3168 if (rhs_code == TRUNC_DIV_EXPR) 3169 { 3170 t = build_int_cst (integer_type_node, tree_log2 (op1)); 3171 gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR); 3172 gimple_assign_set_rhs1 (stmt, op0); 3173 gimple_assign_set_rhs2 (stmt, t); 3174 } 3175 else 3176 { 3177 t = build_int_cst (TREE_TYPE (op1), 1); 3178 t = int_const_binop (MINUS_EXPR, op1, t); 3179 t = fold_convert (TREE_TYPE (op0), t); 3180 3181 gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR); 3182 gimple_assign_set_rhs1 (stmt, op0); 3183 gimple_assign_set_rhs2 (stmt, t); 3184 } 3185 3186 update_stmt (stmt); 3187 fold_stmt (gsi, follow_single_use_edges); 3188 return true; 3189 } 3190 3191 return false; 3192 } 3193 3194 /* Simplify a min or max if the ranges of the two operands are 3195 disjoint. Return true if we do simplify. */ 3196 3197 bool 3198 vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator *gsi, 3199 gimple *stmt) 3200 { 3201 tree op0 = gimple_assign_rhs1 (stmt); 3202 tree op1 = gimple_assign_rhs2 (stmt); 3203 bool sop = false; 3204 tree val; 3205 3206 val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges 3207 (LE_EXPR, op0, op1, &sop)); 3208 if (!val) 3209 { 3210 sop = false; 3211 val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges 3212 (LT_EXPR, op0, op1, &sop)); 3213 } 3214 3215 if (val) 3216 { 3217 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 3218 { 3219 location_t location; 3220 3221 if (!gimple_has_location (stmt)) 3222 location = input_location; 3223 else 3224 location = gimple_location (stmt); 3225 warning_at (location, OPT_Wstrict_overflow, 3226 "assuming signed overflow does not occur when " 3227 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>"); 3228 } 3229 3230 /* VAL == TRUE -> OP0 < or <= op1 3231 VAL == FALSE -> OP0 > or >= op1. */ 3232 tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR) 3233 == integer_zerop (val)) ? op0 : op1; 3234 gimple_assign_set_rhs_from_tree (gsi, res); 3235 return true; 3236 } 3237 3238 return false; 3239 } 3240 3241 /* If the operand to an ABS_EXPR is >= 0, then eliminate the 3242 ABS_EXPR. If the operand is <= 0, then simplify the 3243 ABS_EXPR into a NEGATE_EXPR. */ 3244 3245 bool 3246 vr_values::simplify_abs_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) 3247 { 3248 tree op = gimple_assign_rhs1 (stmt); 3249 value_range *vr = get_value_range (op); 3250 3251 if (vr) 3252 { 3253 tree val = NULL; 3254 bool sop = false; 3255 3256 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop); 3257 if (!val) 3258 { 3259 /* The range is neither <= 0 nor > 0. Now see if it is 3260 either < 0 or >= 0. */ 3261 sop = false; 3262 val = compare_range_with_value (LT_EXPR, vr, integer_zero_node, 3263 &sop); 3264 } 3265 3266 if (val) 3267 { 3268 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 3269 { 3270 location_t location; 3271 3272 if (!gimple_has_location (stmt)) 3273 location = input_location; 3274 else 3275 location = gimple_location (stmt); 3276 warning_at (location, OPT_Wstrict_overflow, 3277 "assuming signed overflow does not occur when " 3278 "simplifying %<abs (X)%> to %<X%> or %<-X%>"); 3279 } 3280 3281 gimple_assign_set_rhs1 (stmt, op); 3282 if (integer_zerop (val)) 3283 gimple_assign_set_rhs_code (stmt, SSA_NAME); 3284 else 3285 gimple_assign_set_rhs_code (stmt, NEGATE_EXPR); 3286 update_stmt (stmt); 3287 fold_stmt (gsi, follow_single_use_edges); 3288 return true; 3289 } 3290 } 3291 3292 return false; 3293 } 3294 3295 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR. 3296 If all the bits that are being cleared by & are already 3297 known to be zero from VR, or all the bits that are being 3298 set by | are already known to be one from VR, the bit 3299 operation is redundant. */ 3300 3301 bool 3302 vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi, 3303 gimple *stmt) 3304 { 3305 tree op0 = gimple_assign_rhs1 (stmt); 3306 tree op1 = gimple_assign_rhs2 (stmt); 3307 tree op = NULL_TREE; 3308 value_range_base vr0, vr1; 3309 wide_int may_be_nonzero0, may_be_nonzero1; 3310 wide_int must_be_nonzero0, must_be_nonzero1; 3311 wide_int mask; 3312 3313 if (TREE_CODE (op0) == SSA_NAME) 3314 vr0 = *(get_value_range (op0)); 3315 else if (is_gimple_min_invariant (op0)) 3316 vr0.set (op0); 3317 else 3318 return false; 3319 3320 if (TREE_CODE (op1) == SSA_NAME) 3321 vr1 = *(get_value_range (op1)); 3322 else if (is_gimple_min_invariant (op1)) 3323 vr1.set (op1); 3324 else 3325 return false; 3326 3327 if (!vrp_set_zero_nonzero_bits (TREE_TYPE (op0), &vr0, &may_be_nonzero0, 3328 &must_be_nonzero0)) 3329 return false; 3330 if (!vrp_set_zero_nonzero_bits (TREE_TYPE (op1), &vr1, &may_be_nonzero1, 3331 &must_be_nonzero1)) 3332 return false; 3333 3334 switch (gimple_assign_rhs_code (stmt)) 3335 { 3336 case BIT_AND_EXPR: 3337 mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1); 3338 if (mask == 0) 3339 { 3340 op = op0; 3341 break; 3342 } 3343 mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0); 3344 if (mask == 0) 3345 { 3346 op = op1; 3347 break; 3348 } 3349 break; 3350 case BIT_IOR_EXPR: 3351 mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1); 3352 if (mask == 0) 3353 { 3354 op = op1; 3355 break; 3356 } 3357 mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0); 3358 if (mask == 0) 3359 { 3360 op = op0; 3361 break; 3362 } 3363 break; 3364 default: 3365 gcc_unreachable (); 3366 } 3367 3368 if (op == NULL_TREE) 3369 return false; 3370 3371 gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op); 3372 update_stmt (gsi_stmt (*gsi)); 3373 return true; 3374 } 3375 3376 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has 3377 a known value range VR. 3378 3379 If there is one and only one value which will satisfy the 3380 conditional, then return that value. Else return NULL. 3381 3382 If signed overflow must be undefined for the value to satisfy 3383 the conditional, then set *STRICT_OVERFLOW_P to true. */ 3384 3385 static tree 3386 test_for_singularity (enum tree_code cond_code, tree op0, 3387 tree op1, value_range *vr) 3388 { 3389 tree min = NULL; 3390 tree max = NULL; 3391 3392 /* Extract minimum/maximum values which satisfy the conditional as it was 3393 written. */ 3394 if (cond_code == LE_EXPR || cond_code == LT_EXPR) 3395 { 3396 min = TYPE_MIN_VALUE (TREE_TYPE (op0)); 3397 3398 max = op1; 3399 if (cond_code == LT_EXPR) 3400 { 3401 tree one = build_int_cst (TREE_TYPE (op0), 1); 3402 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); 3403 /* Signal to compare_values_warnv this expr doesn't overflow. */ 3404 if (EXPR_P (max)) 3405 TREE_NO_WARNING (max) = 1; 3406 } 3407 } 3408 else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 3409 { 3410 max = TYPE_MAX_VALUE (TREE_TYPE (op0)); 3411 3412 min = op1; 3413 if (cond_code == GT_EXPR) 3414 { 3415 tree one = build_int_cst (TREE_TYPE (op0), 1); 3416 min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one); 3417 /* Signal to compare_values_warnv this expr doesn't overflow. */ 3418 if (EXPR_P (min)) 3419 TREE_NO_WARNING (min) = 1; 3420 } 3421 } 3422 3423 /* Now refine the minimum and maximum values using any 3424 value range information we have for op0. */ 3425 if (min && max) 3426 { 3427 if (compare_values (vr->min (), min) == 1) 3428 min = vr->min (); 3429 if (compare_values (vr->max (), max) == -1) 3430 max = vr->max (); 3431 3432 /* If the new min/max values have converged to a single value, 3433 then there is only one value which can satisfy the condition, 3434 return that value. */ 3435 if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min)) 3436 return min; 3437 } 3438 return NULL; 3439 } 3440 3441 /* Return whether the value range *VR fits in an integer type specified 3442 by PRECISION and UNSIGNED_P. */ 3443 3444 static bool 3445 range_fits_type_p (value_range *vr, unsigned dest_precision, signop dest_sgn) 3446 { 3447 tree src_type; 3448 unsigned src_precision; 3449 widest_int tem; 3450 signop src_sgn; 3451 3452 /* We can only handle integral and pointer types. */ 3453 src_type = vr->type (); 3454 if (!INTEGRAL_TYPE_P (src_type) 3455 && !POINTER_TYPE_P (src_type)) 3456 return false; 3457 3458 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED, 3459 and so is an identity transform. */ 3460 src_precision = TYPE_PRECISION (vr->type ()); 3461 src_sgn = TYPE_SIGN (src_type); 3462 if ((src_precision < dest_precision 3463 && !(dest_sgn == UNSIGNED && src_sgn == SIGNED)) 3464 || (src_precision == dest_precision && src_sgn == dest_sgn)) 3465 return true; 3466 3467 /* Now we can only handle ranges with constant bounds. */ 3468 if (!range_int_cst_p (vr)) 3469 return false; 3470 3471 /* For sign changes, the MSB of the wide_int has to be clear. 3472 An unsigned value with its MSB set cannot be represented by 3473 a signed wide_int, while a negative value cannot be represented 3474 by an unsigned wide_int. */ 3475 if (src_sgn != dest_sgn 3476 && (wi::lts_p (wi::to_wide (vr->min ()), 0) 3477 || wi::lts_p (wi::to_wide (vr->max ()), 0))) 3478 return false; 3479 3480 /* Then we can perform the conversion on both ends and compare 3481 the result for equality. */ 3482 tem = wi::ext (wi::to_widest (vr->min ()), dest_precision, dest_sgn); 3483 if (tem != wi::to_widest (vr->min ())) 3484 return false; 3485 tem = wi::ext (wi::to_widest (vr->max ()), dest_precision, dest_sgn); 3486 if (tem != wi::to_widest (vr->max ())) 3487 return false; 3488 3489 return true; 3490 } 3491 3492 /* Simplify a conditional using a relational operator to an equality 3493 test if the range information indicates only one value can satisfy 3494 the original conditional. */ 3495 3496 bool 3497 vr_values::simplify_cond_using_ranges_1 (gcond *stmt) 3498 { 3499 tree op0 = gimple_cond_lhs (stmt); 3500 tree op1 = gimple_cond_rhs (stmt); 3501 enum tree_code cond_code = gimple_cond_code (stmt); 3502 3503 if (cond_code != NE_EXPR 3504 && cond_code != EQ_EXPR 3505 && TREE_CODE (op0) == SSA_NAME 3506 && INTEGRAL_TYPE_P (TREE_TYPE (op0)) 3507 && is_gimple_min_invariant (op1)) 3508 { 3509 value_range *vr = get_value_range (op0); 3510 3511 /* If we have range information for OP0, then we might be 3512 able to simplify this conditional. */ 3513 if (vr->kind () == VR_RANGE) 3514 { 3515 tree new_tree = test_for_singularity (cond_code, op0, op1, vr); 3516 if (new_tree) 3517 { 3518 if (dump_file) 3519 { 3520 fprintf (dump_file, "Simplified relational "); 3521 print_gimple_stmt (dump_file, stmt, 0); 3522 fprintf (dump_file, " into "); 3523 } 3524 3525 gimple_cond_set_code (stmt, EQ_EXPR); 3526 gimple_cond_set_lhs (stmt, op0); 3527 gimple_cond_set_rhs (stmt, new_tree); 3528 3529 update_stmt (stmt); 3530 3531 if (dump_file) 3532 { 3533 print_gimple_stmt (dump_file, stmt, 0); 3534 fprintf (dump_file, "\n"); 3535 } 3536 3537 return true; 3538 } 3539 3540 /* Try again after inverting the condition. We only deal 3541 with integral types here, so no need to worry about 3542 issues with inverting FP comparisons. */ 3543 new_tree = test_for_singularity 3544 (invert_tree_comparison (cond_code, false), 3545 op0, op1, vr); 3546 if (new_tree) 3547 { 3548 if (dump_file) 3549 { 3550 fprintf (dump_file, "Simplified relational "); 3551 print_gimple_stmt (dump_file, stmt, 0); 3552 fprintf (dump_file, " into "); 3553 } 3554 3555 gimple_cond_set_code (stmt, NE_EXPR); 3556 gimple_cond_set_lhs (stmt, op0); 3557 gimple_cond_set_rhs (stmt, new_tree); 3558 3559 update_stmt (stmt); 3560 3561 if (dump_file) 3562 { 3563 print_gimple_stmt (dump_file, stmt, 0); 3564 fprintf (dump_file, "\n"); 3565 } 3566 3567 return true; 3568 } 3569 } 3570 } 3571 return false; 3572 } 3573 3574 /* STMT is a conditional at the end of a basic block. 3575 3576 If the conditional is of the form SSA_NAME op constant and the SSA_NAME 3577 was set via a type conversion, try to replace the SSA_NAME with the RHS 3578 of the type conversion. Doing so makes the conversion dead which helps 3579 subsequent passes. */ 3580 3581 void 3582 vr_values::simplify_cond_using_ranges_2 (gcond *stmt) 3583 { 3584 tree op0 = gimple_cond_lhs (stmt); 3585 tree op1 = gimple_cond_rhs (stmt); 3586 3587 /* If we have a comparison of an SSA_NAME (OP0) against a constant, 3588 see if OP0 was set by a type conversion where the source of 3589 the conversion is another SSA_NAME with a range that fits 3590 into the range of OP0's type. 3591 3592 If so, the conversion is redundant as the earlier SSA_NAME can be 3593 used for the comparison directly if we just massage the constant in the 3594 comparison. */ 3595 if (TREE_CODE (op0) == SSA_NAME 3596 && TREE_CODE (op1) == INTEGER_CST) 3597 { 3598 gimple *def_stmt = SSA_NAME_DEF_STMT (op0); 3599 tree innerop; 3600 3601 if (!is_gimple_assign (def_stmt) 3602 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) 3603 return; 3604 3605 innerop = gimple_assign_rhs1 (def_stmt); 3606 3607 if (TREE_CODE (innerop) == SSA_NAME 3608 && !POINTER_TYPE_P (TREE_TYPE (innerop)) 3609 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop) 3610 && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0))) 3611 { 3612 value_range *vr = get_value_range (innerop); 3613 3614 if (range_int_cst_p (vr) 3615 && range_fits_type_p (vr, 3616 TYPE_PRECISION (TREE_TYPE (op0)), 3617 TYPE_SIGN (TREE_TYPE (op0))) 3618 && int_fits_type_p (op1, TREE_TYPE (innerop))) 3619 { 3620 tree newconst = fold_convert (TREE_TYPE (innerop), op1); 3621 gimple_cond_set_lhs (stmt, innerop); 3622 gimple_cond_set_rhs (stmt, newconst); 3623 update_stmt (stmt); 3624 if (dump_file && (dump_flags & TDF_DETAILS)) 3625 { 3626 fprintf (dump_file, "Folded into: "); 3627 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 3628 fprintf (dump_file, "\n"); 3629 } 3630 } 3631 } 3632 } 3633 } 3634 3635 /* Simplify a switch statement using the value range of the switch 3636 argument. */ 3637 3638 bool 3639 vr_values::simplify_switch_using_ranges (gswitch *stmt) 3640 { 3641 tree op = gimple_switch_index (stmt); 3642 value_range *vr = NULL; 3643 bool take_default; 3644 edge e; 3645 edge_iterator ei; 3646 size_t i = 0, j = 0, n, n2; 3647 tree vec2; 3648 switch_update su; 3649 size_t k = 1, l = 0; 3650 3651 if (TREE_CODE (op) == SSA_NAME) 3652 { 3653 vr = get_value_range (op); 3654 3655 /* We can only handle integer ranges. */ 3656 if (vr->varying_p () 3657 || vr->undefined_p () 3658 || vr->symbolic_p ()) 3659 return false; 3660 3661 /* Find case label for min/max of the value range. */ 3662 take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l); 3663 } 3664 else if (TREE_CODE (op) == INTEGER_CST) 3665 { 3666 take_default = !find_case_label_index (stmt, 1, op, &i); 3667 if (take_default) 3668 { 3669 i = 1; 3670 j = 0; 3671 } 3672 else 3673 { 3674 j = i; 3675 } 3676 } 3677 else 3678 return false; 3679 3680 n = gimple_switch_num_labels (stmt); 3681 3682 /* We can truncate the case label ranges that partially overlap with OP's 3683 value range. */ 3684 size_t min_idx = 1, max_idx = 0; 3685 if (vr != NULL) 3686 find_case_label_range (stmt, vr->min (), vr->max (), &min_idx, &max_idx); 3687 if (min_idx <= max_idx) 3688 { 3689 tree min_label = gimple_switch_label (stmt, min_idx); 3690 tree max_label = gimple_switch_label (stmt, max_idx); 3691 3692 /* Avoid changing the type of the case labels when truncating. */ 3693 tree case_label_type = TREE_TYPE (CASE_LOW (min_label)); 3694 tree vr_min = fold_convert (case_label_type, vr->min ()); 3695 tree vr_max = fold_convert (case_label_type, vr->max ()); 3696 3697 if (vr->kind () == VR_RANGE) 3698 { 3699 /* If OP's value range is [2,8] and the low label range is 3700 0 ... 3, truncate the label's range to 2 .. 3. */ 3701 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0 3702 && CASE_HIGH (min_label) != NULL_TREE 3703 && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0) 3704 CASE_LOW (min_label) = vr_min; 3705 3706 /* If OP's value range is [2,8] and the high label range is 3707 7 ... 10, truncate the label's range to 7 .. 8. */ 3708 if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0 3709 && CASE_HIGH (max_label) != NULL_TREE 3710 && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0) 3711 CASE_HIGH (max_label) = vr_max; 3712 } 3713 else if (vr->kind () == VR_ANTI_RANGE) 3714 { 3715 tree one_cst = build_one_cst (case_label_type); 3716 3717 if (min_label == max_label) 3718 { 3719 /* If OP's value range is ~[7,8] and the label's range is 3720 7 ... 10, truncate the label's range to 9 ... 10. */ 3721 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) == 0 3722 && CASE_HIGH (min_label) != NULL_TREE 3723 && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) > 0) 3724 CASE_LOW (min_label) 3725 = int_const_binop (PLUS_EXPR, vr_max, one_cst); 3726 3727 /* If OP's value range is ~[7,8] and the label's range is 3728 5 ... 8, truncate the label's range to 5 ... 6. */ 3729 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0 3730 && CASE_HIGH (min_label) != NULL_TREE 3731 && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) == 0) 3732 CASE_HIGH (min_label) 3733 = int_const_binop (MINUS_EXPR, vr_min, one_cst); 3734 } 3735 else 3736 { 3737 /* If OP's value range is ~[2,8] and the low label range is 3738 0 ... 3, truncate the label's range to 0 ... 1. */ 3739 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0 3740 && CASE_HIGH (min_label) != NULL_TREE 3741 && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0) 3742 CASE_HIGH (min_label) 3743 = int_const_binop (MINUS_EXPR, vr_min, one_cst); 3744 3745 /* If OP's value range is ~[2,8] and the high label range is 3746 7 ... 10, truncate the label's range to 9 ... 10. */ 3747 if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0 3748 && CASE_HIGH (max_label) != NULL_TREE 3749 && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0) 3750 CASE_LOW (max_label) 3751 = int_const_binop (PLUS_EXPR, vr_max, one_cst); 3752 } 3753 } 3754 3755 /* Canonicalize singleton case ranges. */ 3756 if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label))) 3757 CASE_HIGH (min_label) = NULL_TREE; 3758 if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label))) 3759 CASE_HIGH (max_label) = NULL_TREE; 3760 } 3761 3762 /* We can also eliminate case labels that lie completely outside OP's value 3763 range. */ 3764 3765 /* Bail out if this is just all edges taken. */ 3766 if (i == 1 3767 && j == n - 1 3768 && take_default) 3769 return false; 3770 3771 /* Build a new vector of taken case labels. */ 3772 vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default); 3773 n2 = 0; 3774 3775 /* Add the default edge, if necessary. */ 3776 if (take_default) 3777 TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt); 3778 3779 for (; i <= j; ++i, ++n2) 3780 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i); 3781 3782 for (; k <= l; ++k, ++n2) 3783 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k); 3784 3785 /* Mark needed edges. */ 3786 for (i = 0; i < n2; ++i) 3787 { 3788 e = find_edge (gimple_bb (stmt), 3789 label_to_block (cfun, 3790 CASE_LABEL (TREE_VEC_ELT (vec2, i)))); 3791 e->aux = (void *)-1; 3792 } 3793 3794 /* Queue not needed edges for later removal. */ 3795 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) 3796 { 3797 if (e->aux == (void *)-1) 3798 { 3799 e->aux = NULL; 3800 continue; 3801 } 3802 3803 if (dump_file && (dump_flags & TDF_DETAILS)) 3804 { 3805 fprintf (dump_file, "removing unreachable case label\n"); 3806 } 3807 to_remove_edges.safe_push (e); 3808 e->flags &= ~EDGE_EXECUTABLE; 3809 e->flags |= EDGE_IGNORE; 3810 } 3811 3812 /* And queue an update for the stmt. */ 3813 su.stmt = stmt; 3814 su.vec = vec2; 3815 to_update_switch_stmts.safe_push (su); 3816 return false; 3817 } 3818 3819 void 3820 vr_values::cleanup_edges_and_switches (void) 3821 { 3822 int i; 3823 edge e; 3824 switch_update *su; 3825 3826 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the 3827 CFG in a broken state and requires a cfg_cleanup run. */ 3828 FOR_EACH_VEC_ELT (to_remove_edges, i, e) 3829 remove_edge (e); 3830 3831 /* Update SWITCH_EXPR case label vector. */ 3832 FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su) 3833 { 3834 size_t j; 3835 size_t n = TREE_VEC_LENGTH (su->vec); 3836 tree label; 3837 gimple_switch_set_num_labels (su->stmt, n); 3838 for (j = 0; j < n; j++) 3839 gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j)); 3840 /* As we may have replaced the default label with a regular one 3841 make sure to make it a real default label again. This ensures 3842 optimal expansion. */ 3843 label = gimple_switch_label (su->stmt, 0); 3844 CASE_LOW (label) = NULL_TREE; 3845 CASE_HIGH (label) = NULL_TREE; 3846 } 3847 3848 if (!to_remove_edges.is_empty ()) 3849 { 3850 free_dominance_info (CDI_DOMINATORS); 3851 loops_state_set (LOOPS_NEED_FIXUP); 3852 } 3853 3854 to_remove_edges.release (); 3855 to_update_switch_stmts.release (); 3856 } 3857 3858 /* Simplify an integral conversion from an SSA name in STMT. */ 3859 3860 static bool 3861 simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) 3862 { 3863 tree innerop, middleop, finaltype; 3864 gimple *def_stmt; 3865 signop inner_sgn, middle_sgn, final_sgn; 3866 unsigned inner_prec, middle_prec, final_prec; 3867 widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax; 3868 3869 finaltype = TREE_TYPE (gimple_assign_lhs (stmt)); 3870 if (!INTEGRAL_TYPE_P (finaltype)) 3871 return false; 3872 middleop = gimple_assign_rhs1 (stmt); 3873 def_stmt = SSA_NAME_DEF_STMT (middleop); 3874 if (!is_gimple_assign (def_stmt) 3875 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) 3876 return false; 3877 innerop = gimple_assign_rhs1 (def_stmt); 3878 if (TREE_CODE (innerop) != SSA_NAME 3879 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)) 3880 return false; 3881 3882 /* Get the value-range of the inner operand. Use get_range_info in 3883 case innerop was created during substitute-and-fold. */ 3884 wide_int imin, imax; 3885 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop)) 3886 || get_range_info (innerop, &imin, &imax) != VR_RANGE) 3887 return false; 3888 innermin = widest_int::from (imin, TYPE_SIGN (TREE_TYPE (innerop))); 3889 innermax = widest_int::from (imax, TYPE_SIGN (TREE_TYPE (innerop))); 3890 3891 /* Simulate the conversion chain to check if the result is equal if 3892 the middle conversion is removed. */ 3893 inner_prec = TYPE_PRECISION (TREE_TYPE (innerop)); 3894 middle_prec = TYPE_PRECISION (TREE_TYPE (middleop)); 3895 final_prec = TYPE_PRECISION (finaltype); 3896 3897 /* If the first conversion is not injective, the second must not 3898 be widening. */ 3899 if (wi::gtu_p (innermax - innermin, 3900 wi::mask <widest_int> (middle_prec, false)) 3901 && middle_prec < final_prec) 3902 return false; 3903 /* We also want a medium value so that we can track the effect that 3904 narrowing conversions with sign change have. */ 3905 inner_sgn = TYPE_SIGN (TREE_TYPE (innerop)); 3906 if (inner_sgn == UNSIGNED) 3907 innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false); 3908 else 3909 innermed = 0; 3910 if (wi::cmp (innermin, innermed, inner_sgn) >= 0 3911 || wi::cmp (innermed, innermax, inner_sgn) >= 0) 3912 innermed = innermin; 3913 3914 middle_sgn = TYPE_SIGN (TREE_TYPE (middleop)); 3915 middlemin = wi::ext (innermin, middle_prec, middle_sgn); 3916 middlemed = wi::ext (innermed, middle_prec, middle_sgn); 3917 middlemax = wi::ext (innermax, middle_prec, middle_sgn); 3918 3919 /* Require that the final conversion applied to both the original 3920 and the intermediate range produces the same result. */ 3921 final_sgn = TYPE_SIGN (finaltype); 3922 if (wi::ext (middlemin, final_prec, final_sgn) 3923 != wi::ext (innermin, final_prec, final_sgn) 3924 || wi::ext (middlemed, final_prec, final_sgn) 3925 != wi::ext (innermed, final_prec, final_sgn) 3926 || wi::ext (middlemax, final_prec, final_sgn) 3927 != wi::ext (innermax, final_prec, final_sgn)) 3928 return false; 3929 3930 gimple_assign_set_rhs1 (stmt, innerop); 3931 fold_stmt (gsi, follow_single_use_edges); 3932 return true; 3933 } 3934 3935 /* Simplify a conversion from integral SSA name to float in STMT. */ 3936 3937 bool 3938 vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi, 3939 gimple *stmt) 3940 { 3941 tree rhs1 = gimple_assign_rhs1 (stmt); 3942 value_range *vr = get_value_range (rhs1); 3943 scalar_float_mode fltmode 3944 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))); 3945 scalar_int_mode mode; 3946 tree tem; 3947 gassign *conv; 3948 3949 /* We can only handle constant ranges. */ 3950 if (!range_int_cst_p (vr)) 3951 return false; 3952 3953 /* First check if we can use a signed type in place of an unsigned. */ 3954 scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1)); 3955 if (TYPE_UNSIGNED (TREE_TYPE (rhs1)) 3956 && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing 3957 && range_fits_type_p (vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED)) 3958 mode = rhs_mode; 3959 /* If we can do the conversion in the current input mode do nothing. */ 3960 else if (can_float_p (fltmode, rhs_mode, 3961 TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing) 3962 return false; 3963 /* Otherwise search for a mode we can use, starting from the narrowest 3964 integer mode available. */ 3965 else 3966 { 3967 mode = NARROWEST_INT_MODE; 3968 for (;;) 3969 { 3970 /* If we cannot do a signed conversion to float from mode 3971 or if the value-range does not fit in the signed type 3972 try with a wider mode. */ 3973 if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing 3974 && range_fits_type_p (vr, GET_MODE_PRECISION (mode), SIGNED)) 3975 break; 3976 3977 /* But do not widen the input. Instead leave that to the 3978 optabs expansion code. */ 3979 if (!GET_MODE_WIDER_MODE (mode).exists (&mode) 3980 || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1))) 3981 return false; 3982 } 3983 } 3984 3985 /* It works, insert a truncation or sign-change before the 3986 float conversion. */ 3987 tem = make_ssa_name (build_nonstandard_integer_type 3988 (GET_MODE_PRECISION (mode), 0)); 3989 conv = gimple_build_assign (tem, NOP_EXPR, rhs1); 3990 gsi_insert_before (gsi, conv, GSI_SAME_STMT); 3991 gimple_assign_set_rhs1 (stmt, tem); 3992 fold_stmt (gsi, follow_single_use_edges); 3993 3994 return true; 3995 } 3996 3997 /* Simplify an internal fn call using ranges if possible. */ 3998 3999 bool 4000 vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi, 4001 gimple *stmt) 4002 { 4003 enum tree_code subcode; 4004 bool is_ubsan = false; 4005 bool ovf = false; 4006 switch (gimple_call_internal_fn (stmt)) 4007 { 4008 case IFN_UBSAN_CHECK_ADD: 4009 subcode = PLUS_EXPR; 4010 is_ubsan = true; 4011 break; 4012 case IFN_UBSAN_CHECK_SUB: 4013 subcode = MINUS_EXPR; 4014 is_ubsan = true; 4015 break; 4016 case IFN_UBSAN_CHECK_MUL: 4017 subcode = MULT_EXPR; 4018 is_ubsan = true; 4019 break; 4020 case IFN_ADD_OVERFLOW: 4021 subcode = PLUS_EXPR; 4022 break; 4023 case IFN_SUB_OVERFLOW: 4024 subcode = MINUS_EXPR; 4025 break; 4026 case IFN_MUL_OVERFLOW: 4027 subcode = MULT_EXPR; 4028 break; 4029 default: 4030 return false; 4031 } 4032 4033 tree op0 = gimple_call_arg (stmt, 0); 4034 tree op1 = gimple_call_arg (stmt, 1); 4035 tree type; 4036 if (is_ubsan) 4037 { 4038 type = TREE_TYPE (op0); 4039 if (VECTOR_TYPE_P (type)) 4040 return false; 4041 } 4042 else if (gimple_call_lhs (stmt) == NULL_TREE) 4043 return false; 4044 else 4045 type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt))); 4046 if (!check_for_binary_op_overflow (subcode, type, op0, op1, &ovf) 4047 || (is_ubsan && ovf)) 4048 return false; 4049 4050 gimple *g; 4051 location_t loc = gimple_location (stmt); 4052 if (is_ubsan) 4053 g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1); 4054 else 4055 { 4056 int prec = TYPE_PRECISION (type); 4057 tree utype = type; 4058 if (ovf 4059 || !useless_type_conversion_p (type, TREE_TYPE (op0)) 4060 || !useless_type_conversion_p (type, TREE_TYPE (op1))) 4061 utype = build_nonstandard_integer_type (prec, 1); 4062 if (TREE_CODE (op0) == INTEGER_CST) 4063 op0 = fold_convert (utype, op0); 4064 else if (!useless_type_conversion_p (utype, TREE_TYPE (op0))) 4065 { 4066 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0); 4067 gimple_set_location (g, loc); 4068 gsi_insert_before (gsi, g, GSI_SAME_STMT); 4069 op0 = gimple_assign_lhs (g); 4070 } 4071 if (TREE_CODE (op1) == INTEGER_CST) 4072 op1 = fold_convert (utype, op1); 4073 else if (!useless_type_conversion_p (utype, TREE_TYPE (op1))) 4074 { 4075 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1); 4076 gimple_set_location (g, loc); 4077 gsi_insert_before (gsi, g, GSI_SAME_STMT); 4078 op1 = gimple_assign_lhs (g); 4079 } 4080 g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1); 4081 gimple_set_location (g, loc); 4082 gsi_insert_before (gsi, g, GSI_SAME_STMT); 4083 if (utype != type) 4084 { 4085 g = gimple_build_assign (make_ssa_name (type), NOP_EXPR, 4086 gimple_assign_lhs (g)); 4087 gimple_set_location (g, loc); 4088 gsi_insert_before (gsi, g, GSI_SAME_STMT); 4089 } 4090 g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR, 4091 gimple_assign_lhs (g), 4092 build_int_cst (type, ovf)); 4093 } 4094 gimple_set_location (g, loc); 4095 gsi_replace (gsi, g, false); 4096 return true; 4097 } 4098 4099 /* Return true if VAR is a two-valued variable. Set a and b with the 4100 two-values when it is true. Return false otherwise. */ 4101 4102 bool 4103 vr_values::two_valued_val_range_p (tree var, tree *a, tree *b) 4104 { 4105 value_range *vr = get_value_range (var); 4106 if (vr->varying_p () 4107 || vr->undefined_p () 4108 || TREE_CODE (vr->min ()) != INTEGER_CST 4109 || TREE_CODE (vr->max ()) != INTEGER_CST) 4110 return false; 4111 4112 if (vr->kind () == VR_RANGE 4113 && wi::to_wide (vr->max ()) - wi::to_wide (vr->min ()) == 1) 4114 { 4115 *a = vr->min (); 4116 *b = vr->max (); 4117 return true; 4118 } 4119 4120 /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */ 4121 if (vr->kind () == VR_ANTI_RANGE 4122 && (wi::to_wide (vr->min ()) 4123 - wi::to_wide (vrp_val_min (TREE_TYPE (var)))) == 1 4124 && (wi::to_wide (vrp_val_max (TREE_TYPE (var))) 4125 - wi::to_wide (vr->max ())) == 1) 4126 { 4127 *a = vrp_val_min (TREE_TYPE (var)); 4128 *b = vrp_val_max (TREE_TYPE (var)); 4129 return true; 4130 } 4131 4132 return false; 4133 } 4134 4135 /* Simplify STMT using ranges if possible. */ 4136 4137 bool 4138 vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator *gsi) 4139 { 4140 gimple *stmt = gsi_stmt (*gsi); 4141 if (is_gimple_assign (stmt)) 4142 { 4143 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 4144 tree rhs1 = gimple_assign_rhs1 (stmt); 4145 tree rhs2 = gimple_assign_rhs2 (stmt); 4146 tree lhs = gimple_assign_lhs (stmt); 4147 tree val1 = NULL_TREE, val2 = NULL_TREE; 4148 use_operand_p use_p; 4149 gimple *use_stmt; 4150 4151 /* Convert: 4152 LHS = CST BINOP VAR 4153 Where VAR is two-valued and LHS is used in GIMPLE_COND only 4154 To: 4155 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2) 4156 4157 Also handles: 4158 LHS = VAR BINOP CST 4159 Where VAR is two-valued and LHS is used in GIMPLE_COND only 4160 To: 4161 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */ 4162 4163 if (TREE_CODE_CLASS (rhs_code) == tcc_binary 4164 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) 4165 && ((TREE_CODE (rhs1) == INTEGER_CST 4166 && TREE_CODE (rhs2) == SSA_NAME) 4167 || (TREE_CODE (rhs2) == INTEGER_CST 4168 && TREE_CODE (rhs1) == SSA_NAME)) 4169 && single_imm_use (lhs, &use_p, &use_stmt) 4170 && gimple_code (use_stmt) == GIMPLE_COND) 4171 4172 { 4173 tree new_rhs1 = NULL_TREE; 4174 tree new_rhs2 = NULL_TREE; 4175 tree cmp_var = NULL_TREE; 4176 4177 if (TREE_CODE (rhs2) == SSA_NAME 4178 && two_valued_val_range_p (rhs2, &val1, &val2)) 4179 { 4180 /* Optimize RHS1 OP [VAL1, VAL2]. */ 4181 new_rhs1 = int_const_binop (rhs_code, rhs1, val1); 4182 new_rhs2 = int_const_binop (rhs_code, rhs1, val2); 4183 cmp_var = rhs2; 4184 } 4185 else if (TREE_CODE (rhs1) == SSA_NAME 4186 && two_valued_val_range_p (rhs1, &val1, &val2)) 4187 { 4188 /* Optimize [VAL1, VAL2] OP RHS2. */ 4189 new_rhs1 = int_const_binop (rhs_code, val1, rhs2); 4190 new_rhs2 = int_const_binop (rhs_code, val2, rhs2); 4191 cmp_var = rhs1; 4192 } 4193 4194 /* If we could not find two-vals or the optimzation is invalid as 4195 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */ 4196 if (new_rhs1 && new_rhs2) 4197 { 4198 tree cond = build2 (EQ_EXPR, boolean_type_node, cmp_var, val1); 4199 gimple_assign_set_rhs_with_ops (gsi, 4200 COND_EXPR, cond, 4201 new_rhs1, 4202 new_rhs2); 4203 update_stmt (gsi_stmt (*gsi)); 4204 fold_stmt (gsi, follow_single_use_edges); 4205 return true; 4206 } 4207 } 4208 4209 switch (rhs_code) 4210 { 4211 case EQ_EXPR: 4212 case NE_EXPR: 4213 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity 4214 if the RHS is zero or one, and the LHS are known to be boolean 4215 values. */ 4216 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) 4217 return simplify_truth_ops_using_ranges (gsi, stmt); 4218 break; 4219 4220 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR 4221 and BIT_AND_EXPR respectively if the first operand is greater 4222 than zero and the second operand is an exact power of two. 4223 Also optimize TRUNC_MOD_EXPR away if the second operand is 4224 constant and the first operand already has the right value 4225 range. */ 4226 case TRUNC_DIV_EXPR: 4227 case TRUNC_MOD_EXPR: 4228 if ((TREE_CODE (rhs1) == SSA_NAME 4229 || TREE_CODE (rhs1) == INTEGER_CST) 4230 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) 4231 return simplify_div_or_mod_using_ranges (gsi, stmt); 4232 break; 4233 4234 /* Transform ABS (X) into X or -X as appropriate. */ 4235 case ABS_EXPR: 4236 if (TREE_CODE (rhs1) == SSA_NAME 4237 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) 4238 return simplify_abs_using_ranges (gsi, stmt); 4239 break; 4240 4241 case BIT_AND_EXPR: 4242 case BIT_IOR_EXPR: 4243 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR 4244 if all the bits being cleared are already cleared or 4245 all the bits being set are already set. */ 4246 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) 4247 return simplify_bit_ops_using_ranges (gsi, stmt); 4248 break; 4249 4250 CASE_CONVERT: 4251 if (TREE_CODE (rhs1) == SSA_NAME 4252 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) 4253 return simplify_conversion_using_ranges (gsi, stmt); 4254 break; 4255 4256 case FLOAT_EXPR: 4257 if (TREE_CODE (rhs1) == SSA_NAME 4258 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) 4259 return simplify_float_conversion_using_ranges (gsi, stmt); 4260 break; 4261 4262 case MIN_EXPR: 4263 case MAX_EXPR: 4264 return simplify_min_or_max_using_ranges (gsi, stmt); 4265 4266 default: 4267 break; 4268 } 4269 } 4270 else if (gimple_code (stmt) == GIMPLE_COND) 4271 return simplify_cond_using_ranges_1 (as_a <gcond *> (stmt)); 4272 else if (gimple_code (stmt) == GIMPLE_SWITCH) 4273 return simplify_switch_using_ranges (as_a <gswitch *> (stmt)); 4274 else if (is_gimple_call (stmt) 4275 && gimple_call_internal_p (stmt)) 4276 return simplify_internal_call_using_ranges (gsi, stmt); 4277 4278 return false; 4279 } 4280 4281 void 4282 vr_values::set_vr_value (tree var, value_range *vr) 4283 { 4284 if (SSA_NAME_VERSION (var) >= num_vr_values) 4285 return; 4286 vr_value[SSA_NAME_VERSION (var)] = vr; 4287 } 4288 4289