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