1/* Support routines for Value Range Propagation (VRP). 2 Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com>. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "ggc.h" 27#include "flags.h" 28#include "tree.h" 29#include "basic-block.h" 30#include "tree-flow.h" 31#include "tree-pass.h" 32#include "tree-dump.h" 33#include "timevar.h" 34#include "diagnostic.h" 35#include "toplev.h" 36#include "intl.h" 37#include "cfgloop.h" 38#include "tree-scalar-evolution.h" 39#include "tree-ssa-propagate.h" 40#include "tree-chrec.h" 41 42/* Set of SSA names found during the dominator traversal of a 43 sub-graph in find_assert_locations. */ 44static sbitmap found_in_subgraph; 45 46/* Local functions. */ 47static int compare_values (tree val1, tree val2); 48static int compare_values_warnv (tree val1, tree val2, bool *); 49static tree vrp_evaluate_conditional_warnv (tree, bool, bool *); 50 51/* Location information for ASSERT_EXPRs. Each instance of this 52 structure describes an ASSERT_EXPR for an SSA name. Since a single 53 SSA name may have more than one assertion associated with it, these 54 locations are kept in a linked list attached to the corresponding 55 SSA name. */ 56struct assert_locus_d 57{ 58 /* Basic block where the assertion would be inserted. */ 59 basic_block bb; 60 61 /* Some assertions need to be inserted on an edge (e.g., assertions 62 generated by COND_EXPRs). In those cases, BB will be NULL. */ 63 edge e; 64 65 /* Pointer to the statement that generated this assertion. */ 66 block_stmt_iterator si; 67 68 /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */ 69 enum tree_code comp_code; 70 71 /* Value being compared against. */ 72 tree val; 73 74 /* Next node in the linked list. */ 75 struct assert_locus_d *next; 76}; 77 78typedef struct assert_locus_d *assert_locus_t; 79 80/* If bit I is present, it means that SSA name N_i has a list of 81 assertions that should be inserted in the IL. */ 82static bitmap need_assert_for; 83 84/* Array of locations lists where to insert assertions. ASSERTS_FOR[I] 85 holds a list of ASSERT_LOCUS_T nodes that describe where 86 ASSERT_EXPRs for SSA name N_I should be inserted. */ 87static assert_locus_t *asserts_for; 88 89/* Set of blocks visited in find_assert_locations. Used to avoid 90 visiting the same block more than once. */ 91static sbitmap blocks_visited; 92 93/* Value range array. After propagation, VR_VALUE[I] holds the range 94 of values that SSA name N_I may take. */ 95static value_range_t **vr_value; 96 97 98/* Return whether TYPE should use an overflow infinity distinct from 99 TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to 100 represent a signed overflow during VRP computations. An infinity 101 is distinct from a half-range, which will go from some number to 102 TYPE_{MIN,MAX}_VALUE. */ 103 104static inline bool 105needs_overflow_infinity (tree type) 106{ 107 return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type); 108} 109 110/* Return whether TYPE can support our overflow infinity 111 representation: we use the TREE_OVERFLOW flag, which only exists 112 for constants. If TYPE doesn't support this, we don't optimize 113 cases which would require signed overflow--we drop them to 114 VARYING. */ 115 116static inline bool 117supports_overflow_infinity (tree type) 118{ 119#ifdef ENABLE_CHECKING 120 gcc_assert (needs_overflow_infinity (type)); 121#endif 122 return (TYPE_MIN_VALUE (type) != NULL_TREE 123 && CONSTANT_CLASS_P (TYPE_MIN_VALUE (type)) 124 && TYPE_MAX_VALUE (type) != NULL_TREE 125 && CONSTANT_CLASS_P (TYPE_MAX_VALUE (type))); 126} 127 128/* VAL is the maximum or minimum value of a type. Return a 129 corresponding overflow infinity. */ 130 131static inline tree 132make_overflow_infinity (tree val) 133{ 134#ifdef ENABLE_CHECKING 135 gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val)); 136#endif 137 val = copy_node (val); 138 TREE_OVERFLOW (val) = 1; 139 return val; 140} 141 142/* Return a negative overflow infinity for TYPE. */ 143 144static inline tree 145negative_overflow_infinity (tree type) 146{ 147#ifdef ENABLE_CHECKING 148 gcc_assert (supports_overflow_infinity (type)); 149#endif 150 return make_overflow_infinity (TYPE_MIN_VALUE (type)); 151} 152 153/* Return a positive overflow infinity for TYPE. */ 154 155static inline tree 156positive_overflow_infinity (tree type) 157{ 158#ifdef ENABLE_CHECKING 159 gcc_assert (supports_overflow_infinity (type)); 160#endif 161 return make_overflow_infinity (TYPE_MAX_VALUE (type)); 162} 163 164/* Return whether VAL is a negative overflow infinity. */ 165 166static inline bool 167is_negative_overflow_infinity (tree val) 168{ 169 return (needs_overflow_infinity (TREE_TYPE (val)) 170 && CONSTANT_CLASS_P (val) 171 && TREE_OVERFLOW (val) 172 && operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); 173} 174 175/* Return whether VAL is a positive overflow infinity. */ 176 177static inline bool 178is_positive_overflow_infinity (tree val) 179{ 180 return (needs_overflow_infinity (TREE_TYPE (val)) 181 && CONSTANT_CLASS_P (val) 182 && TREE_OVERFLOW (val) 183 && operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)); 184} 185 186/* Return whether VAL is a positive or negative overflow infinity. */ 187 188static inline bool 189is_overflow_infinity (tree val) 190{ 191 return (needs_overflow_infinity (TREE_TYPE (val)) 192 && CONSTANT_CLASS_P (val) 193 && TREE_OVERFLOW (val) 194 && (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0) 195 || operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0))); 196} 197 198/* If VAL is now an overflow infinity, return VAL. Otherwise, return 199 the same value with TREE_OVERFLOW clear. This can be used to avoid 200 confusing a regular value with an overflow value. */ 201 202static inline tree 203avoid_overflow_infinity (tree val) 204{ 205 if (!is_overflow_infinity (val)) 206 return val; 207 208 if (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)) 209 return TYPE_MAX_VALUE (TREE_TYPE (val)); 210 else 211 { 212#ifdef ENABLE_CHECKING 213 gcc_assert (operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); 214#endif 215 return TYPE_MIN_VALUE (TREE_TYPE (val)); 216 } 217} 218 219 220/* Return whether VAL is equal to the maximum value of its type. This 221 will be true for a positive overflow infinity. We can't do a 222 simple equality comparison with TYPE_MAX_VALUE because C typedefs 223 and Ada subtypes can produce types whose TYPE_MAX_VALUE is not == 224 to the integer constant with the same value in the type. */ 225 226static inline bool 227vrp_val_is_max (tree val) 228{ 229 tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val)); 230 231 return (val == type_max 232 || (type_max != NULL_TREE 233 && operand_equal_p (val, type_max, 0))); 234} 235 236/* Return whether VAL is equal to the minimum value of its type. This 237 will be true for a negative overflow infinity. */ 238 239static inline bool 240vrp_val_is_min (tree val) 241{ 242 tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val)); 243 244 return (val == type_min 245 || (type_min != NULL_TREE 246 && operand_equal_p (val, type_min, 0))); 247} 248 249 250/* Return true if ARG is marked with the nonnull attribute in the 251 current function signature. */ 252 253static bool 254nonnull_arg_p (tree arg) 255{ 256 tree t, attrs, fntype; 257 unsigned HOST_WIDE_INT arg_num; 258 259 gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg))); 260 261 /* The static chain decl is always non null. */ 262 if (arg == cfun->static_chain_decl) 263 return true; 264 265 fntype = TREE_TYPE (current_function_decl); 266 attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype)); 267 268 /* If "nonnull" wasn't specified, we know nothing about the argument. */ 269 if (attrs == NULL_TREE) 270 return false; 271 272 /* If "nonnull" applies to all the arguments, then ARG is non-null. */ 273 if (TREE_VALUE (attrs) == NULL_TREE) 274 return true; 275 276 /* Get the position number for ARG in the function signature. */ 277 for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl); 278 t; 279 t = TREE_CHAIN (t), arg_num++) 280 { 281 if (t == arg) 282 break; 283 } 284 285 gcc_assert (t == arg); 286 287 /* Now see if ARG_NUM is mentioned in the nonnull list. */ 288 for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t)) 289 { 290 if (compare_tree_int (TREE_VALUE (t), arg_num) == 0) 291 return true; 292 } 293 294 return false; 295} 296 297 298/* Set value range VR to {T, MIN, MAX, EQUIV}. */ 299 300static void 301set_value_range (value_range_t *vr, enum value_range_type t, tree min, 302 tree max, bitmap equiv) 303{ 304#if defined ENABLE_CHECKING 305 /* Check the validity of the range. */ 306 if (t == VR_RANGE || t == VR_ANTI_RANGE) 307 { 308 int cmp; 309 310 gcc_assert (min && max); 311 312 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE) 313 gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max)); 314 315 cmp = compare_values (min, max); 316 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); 317 318 if (needs_overflow_infinity (TREE_TYPE (min))) 319 gcc_assert (!is_overflow_infinity (min) 320 || !is_overflow_infinity (max)); 321 } 322 323 if (t == VR_UNDEFINED || t == VR_VARYING) 324 gcc_assert (min == NULL_TREE && max == NULL_TREE); 325 326 if (t == VR_UNDEFINED || t == VR_VARYING) 327 gcc_assert (equiv == NULL || bitmap_empty_p (equiv)); 328#endif 329 330 vr->type = t; 331 vr->min = min; 332 vr->max = max; 333 334 /* Since updating the equivalence set involves deep copying the 335 bitmaps, only do it if absolutely necessary. */ 336 if (vr->equiv == NULL) 337 vr->equiv = BITMAP_ALLOC (NULL); 338 339 if (equiv != vr->equiv) 340 { 341 if (equiv && !bitmap_empty_p (equiv)) 342 bitmap_copy (vr->equiv, equiv); 343 else 344 bitmap_clear (vr->equiv); 345 } 346} 347 348 349/* Copy value range FROM into value range TO. */ 350 351static inline void 352copy_value_range (value_range_t *to, value_range_t *from) 353{ 354 set_value_range (to, from->type, from->min, from->max, from->equiv); 355} 356 357 358/* Set value range VR to VR_VARYING. */ 359 360static inline void 361set_value_range_to_varying (value_range_t *vr) 362{ 363 vr->type = VR_VARYING; 364 vr->min = vr->max = NULL_TREE; 365 if (vr->equiv) 366 bitmap_clear (vr->equiv); 367} 368 369/* Set value range VR to a single value. This function is only called 370 with values we get from statements, and exists to clear the 371 TREE_OVERFLOW flag so that we don't think we have an overflow 372 infinity when we shouldn't. */ 373 374static inline void 375set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv) 376{ 377 gcc_assert (is_gimple_min_invariant (val)); 378 val = avoid_overflow_infinity (val); 379 set_value_range (vr, VR_RANGE, val, val, equiv); 380} 381 382/* Set value range VR to a non-negative range of type TYPE. 383 OVERFLOW_INFINITY indicates whether to use a overflow infinity 384 rather than TYPE_MAX_VALUE; this should be true if we determine 385 that the range is nonnegative based on the assumption that signed 386 overflow does not occur. */ 387 388static inline void 389set_value_range_to_nonnegative (value_range_t *vr, tree type, 390 bool overflow_infinity) 391{ 392 tree zero; 393 394 if (overflow_infinity && !supports_overflow_infinity (type)) 395 { 396 set_value_range_to_varying (vr); 397 return; 398 } 399 400 zero = build_int_cst (type, 0); 401 set_value_range (vr, VR_RANGE, zero, 402 (overflow_infinity 403 ? positive_overflow_infinity (type) 404 : TYPE_MAX_VALUE (type)), 405 vr->equiv); 406} 407 408/* Set value range VR to a non-NULL range of type TYPE. */ 409 410static inline void 411set_value_range_to_nonnull (value_range_t *vr, tree type) 412{ 413 tree zero = build_int_cst (type, 0); 414 set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv); 415} 416 417 418/* Set value range VR to a NULL range of type TYPE. */ 419 420static inline void 421set_value_range_to_null (value_range_t *vr, tree type) 422{ 423 set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv); 424} 425 426 427/* Set value range VR to VR_UNDEFINED. */ 428 429static inline void 430set_value_range_to_undefined (value_range_t *vr) 431{ 432 vr->type = VR_UNDEFINED; 433 vr->min = vr->max = NULL_TREE; 434 if (vr->equiv) 435 bitmap_clear (vr->equiv); 436} 437 438 439/* Return value range information for VAR. 440 441 If we have no values ranges recorded (ie, VRP is not running), then 442 return NULL. Otherwise create an empty range if none existed for VAR. */ 443 444static value_range_t * 445get_value_range (tree var) 446{ 447 value_range_t *vr; 448 tree sym; 449 unsigned ver = SSA_NAME_VERSION (var); 450 451 /* If we have no recorded ranges, then return NULL. */ 452 if (! vr_value) 453 return NULL; 454 455 vr = vr_value[ver]; 456 if (vr) 457 return vr; 458 459 /* Create a default value range. */ 460 vr_value[ver] = vr = XNEW (value_range_t); 461 memset (vr, 0, sizeof (*vr)); 462 463 /* Allocate an equivalence set. */ 464 vr->equiv = BITMAP_ALLOC (NULL); 465 466 /* If VAR is a default definition, the variable can take any value 467 in VAR's type. */ 468 sym = SSA_NAME_VAR (var); 469 if (var == default_def (sym)) 470 { 471 /* Try to use the "nonnull" attribute to create ~[0, 0] 472 anti-ranges for pointers. Note that this is only valid with 473 default definitions of PARM_DECLs. */ 474 if (TREE_CODE (sym) == PARM_DECL 475 && POINTER_TYPE_P (TREE_TYPE (sym)) 476 && nonnull_arg_p (sym)) 477 set_value_range_to_nonnull (vr, TREE_TYPE (sym)); 478 else 479 set_value_range_to_varying (vr); 480 } 481 482 return vr; 483} 484 485/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ 486 487static inline bool 488vrp_operand_equal_p (tree val1, tree val2) 489{ 490 if (val1 == val2) 491 return true; 492 if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) 493 return false; 494 if (is_overflow_infinity (val1)) 495 return is_overflow_infinity (val2); 496 return true; 497} 498 499/* Return true, if the bitmaps B1 and B2 are equal. */ 500 501static inline bool 502vrp_bitmap_equal_p (bitmap b1, bitmap b2) 503{ 504 return (b1 == b2 505 || (b1 && b2 506 && bitmap_equal_p (b1, b2))); 507} 508 509/* Update the value range and equivalence set for variable VAR to 510 NEW_VR. Return true if NEW_VR is different from VAR's previous 511 value. 512 513 NOTE: This function assumes that NEW_VR is a temporary value range 514 object created for the sole purpose of updating VAR's range. The 515 storage used by the equivalence set from NEW_VR will be freed by 516 this function. Do not call update_value_range when NEW_VR 517 is the range object associated with another SSA name. */ 518 519static inline bool 520update_value_range (tree var, value_range_t *new_vr) 521{ 522 value_range_t *old_vr; 523 bool is_new; 524 525 /* Update the value range, if necessary. */ 526 old_vr = get_value_range (var); 527 is_new = old_vr->type != new_vr->type 528 || !vrp_operand_equal_p (old_vr->min, new_vr->min) 529 || !vrp_operand_equal_p (old_vr->max, new_vr->max) 530 || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv); 531 532 if (is_new) 533 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max, 534 new_vr->equiv); 535 536 BITMAP_FREE (new_vr->equiv); 537 new_vr->equiv = NULL; 538 539 return is_new; 540} 541 542 543/* Add VAR and VAR's equivalence set to EQUIV. */ 544 545static void 546add_equivalence (bitmap equiv, tree var) 547{ 548 unsigned ver = SSA_NAME_VERSION (var); 549 value_range_t *vr = vr_value[ver]; 550 551 bitmap_set_bit (equiv, ver); 552 if (vr && vr->equiv) 553 bitmap_ior_into (equiv, vr->equiv); 554} 555 556 557/* Return true if VR is ~[0, 0]. */ 558 559static inline bool 560range_is_nonnull (value_range_t *vr) 561{ 562 return vr->type == VR_ANTI_RANGE 563 && integer_zerop (vr->min) 564 && integer_zerop (vr->max); 565} 566 567 568/* Return true if VR is [0, 0]. */ 569 570static inline bool 571range_is_null (value_range_t *vr) 572{ 573 return vr->type == VR_RANGE 574 && integer_zerop (vr->min) 575 && integer_zerop (vr->max); 576} 577 578 579/* Return true if value range VR involves at least one symbol. */ 580 581static inline bool 582symbolic_range_p (value_range_t *vr) 583{ 584 return (!is_gimple_min_invariant (vr->min) 585 || !is_gimple_min_invariant (vr->max)); 586} 587 588/* Return true if value range VR uses a overflow infinity. */ 589 590static inline bool 591overflow_infinity_range_p (value_range_t *vr) 592{ 593 return (vr->type == VR_RANGE 594 && (is_overflow_infinity (vr->min) 595 || is_overflow_infinity (vr->max))); 596} 597 598/* Return false if we can not make a valid comparison based on VR; 599 this will be the case if it uses an overflow infinity and overflow 600 is not undefined (i.e., -fno-strict-overflow is in effect). 601 Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR 602 uses an overflow infinity. */ 603 604static bool 605usable_range_p (value_range_t *vr, bool *strict_overflow_p) 606{ 607 gcc_assert (vr->type == VR_RANGE); 608 if (is_overflow_infinity (vr->min)) 609 { 610 *strict_overflow_p = true; 611 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min))) 612 return false; 613 } 614 if (is_overflow_infinity (vr->max)) 615 { 616 *strict_overflow_p = true; 617 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max))) 618 return false; 619 } 620 return true; 621} 622 623 624/* Like tree_expr_nonnegative_warnv_p, but this function uses value 625 ranges obtained so far. */ 626 627static bool 628vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p) 629{ 630 return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p); 631} 632 633/* Like tree_expr_nonzero_warnv_p, but this function uses value ranges 634 obtained so far. */ 635 636static bool 637vrp_expr_computes_nonzero (tree expr, bool *strict_overflow_p) 638{ 639 if (tree_expr_nonzero_warnv_p (expr, strict_overflow_p)) 640 return true; 641 642 /* If we have an expression of the form &X->a, then the expression 643 is nonnull if X is nonnull. */ 644 if (TREE_CODE (expr) == ADDR_EXPR) 645 { 646 tree base = get_base_address (TREE_OPERAND (expr, 0)); 647 648 if (base != NULL_TREE 649 && TREE_CODE (base) == INDIRECT_REF 650 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) 651 { 652 value_range_t *vr = get_value_range (TREE_OPERAND (base, 0)); 653 if (range_is_nonnull (vr)) 654 return true; 655 } 656 } 657 658 return false; 659} 660 661/* Returns true if EXPR is a valid value (as expected by compare_values) -- 662 a gimple invariant, or SSA_NAME +- CST. */ 663 664static bool 665valid_value_p (tree expr) 666{ 667 if (TREE_CODE (expr) == SSA_NAME) 668 return true; 669 670 if (TREE_CODE (expr) == PLUS_EXPR 671 || TREE_CODE (expr) == MINUS_EXPR) 672 return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME 673 && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST); 674 675 return is_gimple_min_invariant (expr); 676} 677 678/* Compare two values VAL1 and VAL2. Return 679 680 -2 if VAL1 and VAL2 cannot be compared at compile-time, 681 -1 if VAL1 < VAL2, 682 0 if VAL1 == VAL2, 683 +1 if VAL1 > VAL2, and 684 +2 if VAL1 != VAL2 685 686 This is similar to tree_int_cst_compare but supports pointer values 687 and values that cannot be compared at compile time. 688 689 If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to 690 true if the return value is only valid if we assume that signed 691 overflow is undefined. */ 692 693static int 694compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) 695{ 696 if (val1 == val2) 697 return 0; 698 699 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or 700 both integers. */ 701 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) 702 == POINTER_TYPE_P (TREE_TYPE (val2))); 703 704 if ((TREE_CODE (val1) == SSA_NAME 705 || TREE_CODE (val1) == PLUS_EXPR 706 || TREE_CODE (val1) == MINUS_EXPR) 707 && (TREE_CODE (val2) == SSA_NAME 708 || TREE_CODE (val2) == PLUS_EXPR 709 || TREE_CODE (val2) == MINUS_EXPR)) 710 { 711 tree n1, c1, n2, c2; 712 enum tree_code code1, code2; 713 714 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', 715 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the 716 same name, return -2. */ 717 if (TREE_CODE (val1) == SSA_NAME) 718 { 719 code1 = SSA_NAME; 720 n1 = val1; 721 c1 = NULL_TREE; 722 } 723 else 724 { 725 code1 = TREE_CODE (val1); 726 n1 = TREE_OPERAND (val1, 0); 727 c1 = TREE_OPERAND (val1, 1); 728 if (tree_int_cst_sgn (c1) == -1) 729 { 730 if (is_negative_overflow_infinity (c1)) 731 return -2; 732 c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1); 733 if (!c1) 734 return -2; 735 code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR; 736 } 737 } 738 739 if (TREE_CODE (val2) == SSA_NAME) 740 { 741 code2 = SSA_NAME; 742 n2 = val2; 743 c2 = NULL_TREE; 744 } 745 else 746 { 747 code2 = TREE_CODE (val2); 748 n2 = TREE_OPERAND (val2, 0); 749 c2 = TREE_OPERAND (val2, 1); 750 if (tree_int_cst_sgn (c2) == -1) 751 { 752 if (is_negative_overflow_infinity (c2)) 753 return -2; 754 c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2); 755 if (!c2) 756 return -2; 757 code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR; 758 } 759 } 760 761 /* Both values must use the same name. */ 762 if (n1 != n2) 763 return -2; 764 765 if (code1 == SSA_NAME 766 && code2 == SSA_NAME) 767 /* NAME == NAME */ 768 return 0; 769 770 /* If overflow is defined we cannot simplify more. */ 771 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) 772 return -2; 773 774 if (strict_overflow_p != NULL 775 && (code1 == SSA_NAME || !TREE_NO_WARNING (val1)) 776 && (code2 == SSA_NAME || !TREE_NO_WARNING (val2))) 777 *strict_overflow_p = true; 778 779 if (code1 == SSA_NAME) 780 { 781 if (code2 == PLUS_EXPR) 782 /* NAME < NAME + CST */ 783 return -1; 784 else if (code2 == MINUS_EXPR) 785 /* NAME > NAME - CST */ 786 return 1; 787 } 788 else if (code1 == PLUS_EXPR) 789 { 790 if (code2 == SSA_NAME) 791 /* NAME + CST > NAME */ 792 return 1; 793 else if (code2 == PLUS_EXPR) 794 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */ 795 return compare_values_warnv (c1, c2, strict_overflow_p); 796 else if (code2 == MINUS_EXPR) 797 /* NAME + CST1 > NAME - CST2 */ 798 return 1; 799 } 800 else if (code1 == MINUS_EXPR) 801 { 802 if (code2 == SSA_NAME) 803 /* NAME - CST < NAME */ 804 return -1; 805 else if (code2 == PLUS_EXPR) 806 /* NAME - CST1 < NAME + CST2 */ 807 return -1; 808 else if (code2 == MINUS_EXPR) 809 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that 810 C1 and C2 are swapped in the call to compare_values. */ 811 return compare_values_warnv (c2, c1, strict_overflow_p); 812 } 813 814 gcc_unreachable (); 815 } 816 817 /* We cannot compare non-constants. */ 818 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)) 819 return -2; 820 821 if (!POINTER_TYPE_P (TREE_TYPE (val1))) 822 { 823 /* We cannot compare overflowed values, except for overflow 824 infinities. */ 825 if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) 826 { 827 if (strict_overflow_p != NULL) 828 *strict_overflow_p = true; 829 if (is_negative_overflow_infinity (val1)) 830 return is_negative_overflow_infinity (val2) ? 0 : -1; 831 else if (is_negative_overflow_infinity (val2)) 832 return 1; 833 else if (is_positive_overflow_infinity (val1)) 834 return is_positive_overflow_infinity (val2) ? 0 : 1; 835 else if (is_positive_overflow_infinity (val2)) 836 return -1; 837 return -2; 838 } 839 840 return tree_int_cst_compare (val1, val2); 841 } 842 else 843 { 844 tree t; 845 846 /* First see if VAL1 and VAL2 are not the same. */ 847 if (val1 == val2 || operand_equal_p (val1, val2, 0)) 848 return 0; 849 850 /* If VAL1 is a lower address than VAL2, return -1. */ 851 t = fold_binary (LT_EXPR, boolean_type_node, val1, val2); 852 if (t == boolean_true_node) 853 return -1; 854 855 /* If VAL1 is a higher address than VAL2, return +1. */ 856 t = fold_binary (GT_EXPR, boolean_type_node, val1, val2); 857 if (t == boolean_true_node) 858 return 1; 859 860 /* If VAL1 is different than VAL2, return +2. */ 861 t = fold_binary (NE_EXPR, boolean_type_node, val1, val2); 862 if (t == boolean_true_node) 863 return 2; 864 865 return -2; 866 } 867} 868 869/* Compare values like compare_values_warnv, but treat comparisons of 870 nonconstants which rely on undefined overflow as incomparable. */ 871 872static int 873compare_values (tree val1, tree val2) 874{ 875 bool sop; 876 int ret; 877 878 sop = false; 879 ret = compare_values_warnv (val1, val2, &sop); 880 if (sop 881 && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))) 882 ret = -2; 883 return ret; 884} 885 886 887/* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX), 888 0 if VAL is not inside VR, 889 -2 if we cannot tell either way. 890 891 FIXME, the current semantics of this functions are a bit quirky 892 when taken in the context of VRP. In here we do not care 893 about VR's type. If VR is the anti-range ~[3, 5] the call 894 value_inside_range (4, VR) will return 1. 895 896 This is counter-intuitive in a strict sense, but the callers 897 currently expect this. They are calling the function 898 merely to determine whether VR->MIN <= VAL <= VR->MAX. The 899 callers are applying the VR_RANGE/VR_ANTI_RANGE semantics 900 themselves. 901 902 This also applies to value_ranges_intersect_p and 903 range_includes_zero_p. The semantics of VR_RANGE and 904 VR_ANTI_RANGE should be encoded here, but that also means 905 adapting the users of these functions to the new semantics. */ 906 907static inline int 908value_inside_range (tree val, value_range_t *vr) 909{ 910 tree cmp1, cmp2; 911 912 fold_defer_overflow_warnings (); 913 914 cmp1 = fold_binary_to_constant (GE_EXPR, boolean_type_node, val, vr->min); 915 if (!cmp1) 916 { 917 fold_undefer_and_ignore_overflow_warnings (); 918 return -2; 919 } 920 921 cmp2 = fold_binary_to_constant (LE_EXPR, boolean_type_node, val, vr->max); 922 923 fold_undefer_and_ignore_overflow_warnings (); 924 925 if (!cmp2) 926 return -2; 927 928 return cmp1 == boolean_true_node && cmp2 == boolean_true_node; 929} 930 931 932/* Return true if value ranges VR0 and VR1 have a non-empty 933 intersection. */ 934 935static inline bool 936value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1) 937{ 938 return (value_inside_range (vr1->min, vr0) == 1 939 || value_inside_range (vr1->max, vr0) == 1 940 || value_inside_range (vr0->min, vr1) == 1 941 || value_inside_range (vr0->max, vr1) == 1); 942} 943 944 945/* Return true if VR includes the value zero, false otherwise. FIXME, 946 currently this will return false for an anti-range like ~[-4, 3]. 947 This will be wrong when the semantics of value_inside_range are 948 modified (currently the users of this function expect these 949 semantics). */ 950 951static inline bool 952range_includes_zero_p (value_range_t *vr) 953{ 954 tree zero; 955 956 gcc_assert (vr->type != VR_UNDEFINED 957 && vr->type != VR_VARYING 958 && !symbolic_range_p (vr)); 959 960 zero = build_int_cst (TREE_TYPE (vr->min), 0); 961 return (value_inside_range (zero, vr) == 1); 962} 963 964/* Return true if T, an SSA_NAME, is known to be nonnegative. Return 965 false otherwise or if no value range information is available. */ 966 967bool 968ssa_name_nonnegative_p (tree t) 969{ 970 value_range_t *vr = get_value_range (t); 971 972 if (!vr) 973 return false; 974 975 /* Testing for VR_ANTI_RANGE is not useful here as any anti-range 976 which would return a useful value should be encoded as a VR_RANGE. */ 977 if (vr->type == VR_RANGE) 978 { 979 int result = compare_values (vr->min, integer_zero_node); 980 981 return (result == 0 || result == 1); 982 } 983 return false; 984} 985 986/* Return true if T, an SSA_NAME, is known to be nonzero. Return 987 false otherwise or if no value range information is available. */ 988 989bool 990ssa_name_nonzero_p (tree t) 991{ 992 value_range_t *vr = get_value_range (t); 993 994 if (!vr) 995 return false; 996 997 /* A VR_RANGE which does not include zero is a nonzero value. */ 998 if (vr->type == VR_RANGE && !symbolic_range_p (vr)) 999 return ! range_includes_zero_p (vr); 1000 1001 /* A VR_ANTI_RANGE which does include zero is a nonzero value. */ 1002 if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr)) 1003 return range_includes_zero_p (vr); 1004 1005 return false; 1006} 1007 1008 1009/* Extract value range information from an ASSERT_EXPR EXPR and store 1010 it in *VR_P. */ 1011 1012static void 1013extract_range_from_assert (value_range_t *vr_p, tree expr) 1014{ 1015 tree var, cond, limit, min, max, type; 1016 value_range_t *var_vr, *limit_vr; 1017 enum tree_code cond_code; 1018 1019 var = ASSERT_EXPR_VAR (expr); 1020 cond = ASSERT_EXPR_COND (expr); 1021 1022 gcc_assert (COMPARISON_CLASS_P (cond)); 1023 1024 /* Find VAR in the ASSERT_EXPR conditional. */ 1025 if (var == TREE_OPERAND (cond, 0)) 1026 { 1027 /* If the predicate is of the form VAR COMP LIMIT, then we just 1028 take LIMIT from the RHS and use the same comparison code. */ 1029 limit = TREE_OPERAND (cond, 1); 1030 cond_code = TREE_CODE (cond); 1031 } 1032 else 1033 { 1034 /* If the predicate is of the form LIMIT COMP VAR, then we need 1035 to flip around the comparison code to create the proper range 1036 for VAR. */ 1037 limit = TREE_OPERAND (cond, 0); 1038 cond_code = swap_tree_comparison (TREE_CODE (cond)); 1039 } 1040 1041 limit = avoid_overflow_infinity (limit); 1042 1043 type = TREE_TYPE (limit); 1044 gcc_assert (limit != var); 1045 1046 /* For pointer arithmetic, we only keep track of pointer equality 1047 and inequality. */ 1048 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR) 1049 { 1050 set_value_range_to_varying (vr_p); 1051 return; 1052 } 1053 1054 /* If LIMIT is another SSA name and LIMIT has a range of its own, 1055 try to use LIMIT's range to avoid creating symbolic ranges 1056 unnecessarily. */ 1057 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL; 1058 1059 /* LIMIT's range is only interesting if it has any useful information. */ 1060 if (limit_vr 1061 && (limit_vr->type == VR_UNDEFINED 1062 || limit_vr->type == VR_VARYING 1063 || symbolic_range_p (limit_vr))) 1064 limit_vr = NULL; 1065 1066 /* Initially, the new range has the same set of equivalences of 1067 VAR's range. This will be revised before returning the final 1068 value. Since assertions may be chained via mutually exclusive 1069 predicates, we will need to trim the set of equivalences before 1070 we are done. */ 1071 gcc_assert (vr_p->equiv == NULL); 1072 vr_p->equiv = BITMAP_ALLOC (NULL); 1073 add_equivalence (vr_p->equiv, var); 1074 1075 /* Extract a new range based on the asserted comparison for VAR and 1076 LIMIT's value range. Notice that if LIMIT has an anti-range, we 1077 will only use it for equality comparisons (EQ_EXPR). For any 1078 other kind of assertion, we cannot derive a range from LIMIT's 1079 anti-range that can be used to describe the new range. For 1080 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10], 1081 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is 1082 no single range for x_2 that could describe LE_EXPR, so we might 1083 as well build the range [b_4, +INF] for it. */ 1084 if (cond_code == EQ_EXPR) 1085 { 1086 enum value_range_type range_type; 1087 1088 if (limit_vr) 1089 { 1090 range_type = limit_vr->type; 1091 min = limit_vr->min; 1092 max = limit_vr->max; 1093 } 1094 else 1095 { 1096 range_type = VR_RANGE; 1097 min = limit; 1098 max = limit; 1099 } 1100 1101 set_value_range (vr_p, range_type, min, max, vr_p->equiv); 1102 1103 /* When asserting the equality VAR == LIMIT and LIMIT is another 1104 SSA name, the new range will also inherit the equivalence set 1105 from LIMIT. */ 1106 if (TREE_CODE (limit) == SSA_NAME) 1107 add_equivalence (vr_p->equiv, limit); 1108 } 1109 else if (cond_code == NE_EXPR) 1110 { 1111 /* As described above, when LIMIT's range is an anti-range and 1112 this assertion is an inequality (NE_EXPR), then we cannot 1113 derive anything from the anti-range. For instance, if 1114 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does 1115 not imply that VAR's range is [0, 0]. So, in the case of 1116 anti-ranges, we just assert the inequality using LIMIT and 1117 not its anti-range. 1118 1119 If LIMIT_VR is a range, we can only use it to build a new 1120 anti-range if LIMIT_VR is a single-valued range. For 1121 instance, if LIMIT_VR is [0, 1], the predicate 1122 VAR != [0, 1] does not mean that VAR's range is ~[0, 1]. 1123 Rather, it means that for value 0 VAR should be ~[0, 0] 1124 and for value 1, VAR should be ~[1, 1]. We cannot 1125 represent these ranges. 1126 1127 The only situation in which we can build a valid 1128 anti-range is when LIMIT_VR is a single-valued range 1129 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case, 1130 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */ 1131 if (limit_vr 1132 && limit_vr->type == VR_RANGE 1133 && compare_values (limit_vr->min, limit_vr->max) == 0) 1134 { 1135 min = limit_vr->min; 1136 max = limit_vr->max; 1137 } 1138 else 1139 { 1140 /* In any other case, we cannot use LIMIT's range to build a 1141 valid anti-range. */ 1142 min = max = limit; 1143 } 1144 1145 /* If MIN and MAX cover the whole range for their type, then 1146 just use the original LIMIT. */ 1147 if (INTEGRAL_TYPE_P (type) 1148 && vrp_val_is_min (min) 1149 && vrp_val_is_max (max)) 1150 min = max = limit; 1151 1152 set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv); 1153 } 1154 else if (cond_code == LE_EXPR || cond_code == LT_EXPR) 1155 { 1156 min = TYPE_MIN_VALUE (type); 1157 1158 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE) 1159 max = limit; 1160 else 1161 { 1162 /* If LIMIT_VR is of the form [N1, N2], we need to build the 1163 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for 1164 LT_EXPR. */ 1165 max = limit_vr->max; 1166 } 1167 1168 /* If the maximum value forces us to be out of bounds, simply punt. 1169 It would be pointless to try and do anything more since this 1170 all should be optimized away above us. */ 1171 if ((cond_code == LT_EXPR 1172 && compare_values (max, min) == 0) 1173 || is_overflow_infinity (max)) 1174 set_value_range_to_varying (vr_p); 1175 else 1176 { 1177 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */ 1178 if (cond_code == LT_EXPR) 1179 { 1180 tree one = build_int_cst (type, 1); 1181 max = fold_build2 (MINUS_EXPR, type, max, one); 1182 if (EXPR_P (max)) 1183 TREE_NO_WARNING (max) = 1; 1184 } 1185 1186 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 1187 } 1188 } 1189 else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 1190 { 1191 max = TYPE_MAX_VALUE (type); 1192 1193 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE) 1194 min = limit; 1195 else 1196 { 1197 /* If LIMIT_VR is of the form [N1, N2], we need to build the 1198 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for 1199 GT_EXPR. */ 1200 min = limit_vr->min; 1201 } 1202 1203 /* If the minimum value forces us to be out of bounds, simply punt. 1204 It would be pointless to try and do anything more since this 1205 all should be optimized away above us. */ 1206 if ((cond_code == GT_EXPR 1207 && compare_values (min, max) == 0) 1208 || is_overflow_infinity (min)) 1209 set_value_range_to_varying (vr_p); 1210 else 1211 { 1212 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */ 1213 if (cond_code == GT_EXPR) 1214 { 1215 tree one = build_int_cst (type, 1); 1216 min = fold_build2 (PLUS_EXPR, type, min, one); 1217 if (EXPR_P (min)) 1218 TREE_NO_WARNING (min) = 1; 1219 } 1220 1221 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 1222 } 1223 } 1224 else 1225 gcc_unreachable (); 1226 1227 /* If VAR already had a known range, it may happen that the new 1228 range we have computed and VAR's range are not compatible. For 1229 instance, 1230 1231 if (p_5 == NULL) 1232 p_6 = ASSERT_EXPR <p_5, p_5 == NULL>; 1233 x_7 = p_6->fld; 1234 p_8 = ASSERT_EXPR <p_6, p_6 != NULL>; 1235 1236 While the above comes from a faulty program, it will cause an ICE 1237 later because p_8 and p_6 will have incompatible ranges and at 1238 the same time will be considered equivalent. A similar situation 1239 would arise from 1240 1241 if (i_5 > 10) 1242 i_6 = ASSERT_EXPR <i_5, i_5 > 10>; 1243 if (i_5 < 5) 1244 i_7 = ASSERT_EXPR <i_6, i_6 < 5>; 1245 1246 Again i_6 and i_7 will have incompatible ranges. It would be 1247 pointless to try and do anything with i_7's range because 1248 anything dominated by 'if (i_5 < 5)' will be optimized away. 1249 Note, due to the wa in which simulation proceeds, the statement 1250 i_7 = ASSERT_EXPR <...> we would never be visited because the 1251 conditional 'if (i_5 < 5)' always evaluates to false. However, 1252 this extra check does not hurt and may protect against future 1253 changes to VRP that may get into a situation similar to the 1254 NULL pointer dereference example. 1255 1256 Note that these compatibility tests are only needed when dealing 1257 with ranges or a mix of range and anti-range. If VAR_VR and VR_P 1258 are both anti-ranges, they will always be compatible, because two 1259 anti-ranges will always have a non-empty intersection. */ 1260 1261 var_vr = get_value_range (var); 1262 1263 /* We may need to make adjustments when VR_P and VAR_VR are numeric 1264 ranges or anti-ranges. */ 1265 if (vr_p->type == VR_VARYING 1266 || vr_p->type == VR_UNDEFINED 1267 || var_vr->type == VR_VARYING 1268 || var_vr->type == VR_UNDEFINED 1269 || symbolic_range_p (vr_p) 1270 || symbolic_range_p (var_vr)) 1271 return; 1272 1273 if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE) 1274 { 1275 /* If the two ranges have a non-empty intersection, we can 1276 refine the resulting range. Since the assert expression 1277 creates an equivalency and at the same time it asserts a 1278 predicate, we can take the intersection of the two ranges to 1279 get better precision. */ 1280 if (value_ranges_intersect_p (var_vr, vr_p)) 1281 { 1282 /* Use the larger of the two minimums. */ 1283 if (compare_values (vr_p->min, var_vr->min) == -1) 1284 min = var_vr->min; 1285 else 1286 min = vr_p->min; 1287 1288 /* Use the smaller of the two maximums. */ 1289 if (compare_values (vr_p->max, var_vr->max) == 1) 1290 max = var_vr->max; 1291 else 1292 max = vr_p->max; 1293 1294 set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv); 1295 } 1296 else 1297 { 1298 /* The two ranges do not intersect, set the new range to 1299 VARYING, because we will not be able to do anything 1300 meaningful with it. */ 1301 set_value_range_to_varying (vr_p); 1302 } 1303 } 1304 else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE) 1305 || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE)) 1306 { 1307 /* A range and an anti-range will cancel each other only if 1308 their ends are the same. For instance, in the example above, 1309 p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible, 1310 so VR_P should be set to VR_VARYING. */ 1311 if (compare_values (var_vr->min, vr_p->min) == 0 1312 && compare_values (var_vr->max, vr_p->max) == 0) 1313 set_value_range_to_varying (vr_p); 1314 else 1315 { 1316 tree min, max, anti_min, anti_max, real_min, real_max; 1317 1318 /* We want to compute the logical AND of the two ranges; 1319 there are three cases to consider. 1320 1321 1322 1. The VR_ANTI_RANGE range is completely within the 1323 VR_RANGE and the endpoints of the ranges are 1324 different. In that case the resulting range 1325 should be whichever range is more precise. 1326 Typically that will be the VR_RANGE. 1327 1328 2. The VR_ANTI_RANGE is completely disjoint from 1329 the VR_RANGE. In this case the resulting range 1330 should be the VR_RANGE. 1331 1332 3. There is some overlap between the VR_ANTI_RANGE 1333 and the VR_RANGE. 1334 1335 3a. If the high limit of the VR_ANTI_RANGE resides 1336 within the VR_RANGE, then the result is a new 1337 VR_RANGE starting at the high limit of the 1338 the VR_ANTI_RANGE + 1 and extending to the 1339 high limit of the original VR_RANGE. 1340 1341 3b. If the low limit of the VR_ANTI_RANGE resides 1342 within the VR_RANGE, then the result is a new 1343 VR_RANGE starting at the low limit of the original 1344 VR_RANGE and extending to the low limit of the 1345 VR_ANTI_RANGE - 1. */ 1346 if (vr_p->type == VR_ANTI_RANGE) 1347 { 1348 anti_min = vr_p->min; 1349 anti_max = vr_p->max; 1350 real_min = var_vr->min; 1351 real_max = var_vr->max; 1352 } 1353 else 1354 { 1355 anti_min = var_vr->min; 1356 anti_max = var_vr->max; 1357 real_min = vr_p->min; 1358 real_max = vr_p->max; 1359 } 1360 1361 1362 /* Case 1, VR_ANTI_RANGE completely within VR_RANGE, 1363 not including any endpoints. */ 1364 if (compare_values (anti_max, real_max) == -1 1365 && compare_values (anti_min, real_min) == 1) 1366 { 1367 set_value_range (vr_p, VR_RANGE, real_min, 1368 real_max, vr_p->equiv); 1369 } 1370 /* Case 2, VR_ANTI_RANGE completely disjoint from 1371 VR_RANGE. */ 1372 else if (compare_values (anti_min, real_max) == 1 1373 || compare_values (anti_max, real_min) == -1) 1374 { 1375 set_value_range (vr_p, VR_RANGE, real_min, 1376 real_max, vr_p->equiv); 1377 } 1378 /* Case 3a, the anti-range extends into the low 1379 part of the real range. Thus creating a new 1380 low for the real range. */ 1381 else if ((compare_values (anti_max, real_min) == 1 1382 || compare_values (anti_max, real_min) == 0) 1383 && compare_values (anti_max, real_max) == -1) 1384 { 1385 gcc_assert (!is_positive_overflow_infinity (anti_max)); 1386 if (needs_overflow_infinity (TREE_TYPE (anti_max)) 1387 && vrp_val_is_max (anti_max)) 1388 { 1389 if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) 1390 { 1391 set_value_range_to_varying (vr_p); 1392 return; 1393 } 1394 min = positive_overflow_infinity (TREE_TYPE (var_vr->min)); 1395 } 1396 else 1397 min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min), 1398 anti_max, 1399 build_int_cst (TREE_TYPE (var_vr->min), 1)); 1400 max = real_max; 1401 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 1402 } 1403 /* Case 3b, the anti-range extends into the high 1404 part of the real range. Thus creating a new 1405 higher for the real range. */ 1406 else if (compare_values (anti_min, real_min) == 1 1407 && (compare_values (anti_min, real_max) == -1 1408 || compare_values (anti_min, real_max) == 0)) 1409 { 1410 gcc_assert (!is_negative_overflow_infinity (anti_min)); 1411 if (needs_overflow_infinity (TREE_TYPE (anti_min)) 1412 && vrp_val_is_min (anti_min)) 1413 { 1414 if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) 1415 { 1416 set_value_range_to_varying (vr_p); 1417 return; 1418 } 1419 max = negative_overflow_infinity (TREE_TYPE (var_vr->min)); 1420 } 1421 else 1422 max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min), 1423 anti_min, 1424 build_int_cst (TREE_TYPE (var_vr->min), 1)); 1425 min = real_min; 1426 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 1427 } 1428 } 1429 } 1430} 1431 1432 1433/* Extract range information from SSA name VAR and store it in VR. If 1434 VAR has an interesting range, use it. Otherwise, create the 1435 range [VAR, VAR] and return it. This is useful in situations where 1436 we may have conditionals testing values of VARYING names. For 1437 instance, 1438 1439 x_3 = y_5; 1440 if (x_3 > y_5) 1441 ... 1442 1443 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is 1444 always false. */ 1445 1446static void 1447extract_range_from_ssa_name (value_range_t *vr, tree var) 1448{ 1449 value_range_t *var_vr = get_value_range (var); 1450 1451 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING) 1452 copy_value_range (vr, var_vr); 1453 else 1454 set_value_range (vr, VR_RANGE, var, var, NULL); 1455 1456 add_equivalence (vr->equiv, var); 1457} 1458 1459 1460/* Wrapper around int_const_binop. If the operation overflows and we 1461 are not using wrapping arithmetic, then adjust the result to be 1462 -INF or +INF depending on CODE, VAL1 and VAL2. This can return 1463 NULL_TREE if we need to use an overflow infinity representation but 1464 the type does not support it. */ 1465 1466static tree 1467vrp_int_const_binop (enum tree_code code, tree val1, tree val2) 1468{ 1469 tree res; 1470 1471 res = int_const_binop (code, val1, val2, 0); 1472 1473 /* If we are not using wrapping arithmetic, operate symbolically 1474 on -INF and +INF. */ 1475 if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1))) 1476 { 1477 int checkz = compare_values (res, val1); 1478 bool overflow = false; 1479 1480 /* Ensure that res = val1 [+*] val2 >= val1 1481 or that res = val1 - val2 <= val1. */ 1482 if ((code == PLUS_EXPR 1483 && !(checkz == 1 || checkz == 0)) 1484 || (code == MINUS_EXPR 1485 && !(checkz == 0 || checkz == -1))) 1486 { 1487 overflow = true; 1488 } 1489 /* Checking for multiplication overflow is done by dividing the 1490 output of the multiplication by the first input of the 1491 multiplication. If the result of that division operation is 1492 not equal to the second input of the multiplication, then the 1493 multiplication overflowed. */ 1494 else if (code == MULT_EXPR && !integer_zerop (val1)) 1495 { 1496 tree tmp = int_const_binop (TRUNC_DIV_EXPR, 1497 res, 1498 val1, 0); 1499 int check = compare_values (tmp, val2); 1500 1501 if (check != 0) 1502 overflow = true; 1503 } 1504 1505 if (overflow) 1506 { 1507 res = copy_node (res); 1508 TREE_OVERFLOW (res) = 1; 1509 } 1510 1511 } 1512 else if ((TREE_OVERFLOW (res) 1513 && !TREE_OVERFLOW (val1) 1514 && !TREE_OVERFLOW (val2)) 1515 || is_overflow_infinity (val1) 1516 || is_overflow_infinity (val2)) 1517 { 1518 /* If the operation overflowed but neither VAL1 nor VAL2 are 1519 overflown, return -INF or +INF depending on the operation 1520 and the combination of signs of the operands. */ 1521 int sgn1 = tree_int_cst_sgn (val1); 1522 int sgn2 = tree_int_cst_sgn (val2); 1523 1524 if (needs_overflow_infinity (TREE_TYPE (res)) 1525 && !supports_overflow_infinity (TREE_TYPE (res))) 1526 return NULL_TREE; 1527 1528 /* We have to punt on adding infinities of different signs, 1529 since we can't tell what the sign of the result should be. 1530 Likewise for subtracting infinities of the same sign. */ 1531 if (((code == PLUS_EXPR && sgn1 != sgn2) 1532 || (code == MINUS_EXPR && sgn1 == sgn2)) 1533 && is_overflow_infinity (val1) 1534 && is_overflow_infinity (val2)) 1535 return NULL_TREE; 1536 1537 /* Don't try to handle division or shifting of infinities. */ 1538 if ((code == TRUNC_DIV_EXPR 1539 || code == FLOOR_DIV_EXPR 1540 || code == CEIL_DIV_EXPR 1541 || code == EXACT_DIV_EXPR 1542 || code == ROUND_DIV_EXPR 1543 || code == RSHIFT_EXPR) 1544 && (is_overflow_infinity (val1) 1545 || is_overflow_infinity (val2))) 1546 return NULL_TREE; 1547 1548 /* Notice that we only need to handle the restricted set of 1549 operations handled by extract_range_from_binary_expr. 1550 Among them, only multiplication, addition and subtraction 1551 can yield overflow without overflown operands because we 1552 are working with integral types only... except in the 1553 case VAL1 = -INF and VAL2 = -1 which overflows to +INF 1554 for division too. */ 1555 1556 /* For multiplication, the sign of the overflow is given 1557 by the comparison of the signs of the operands. */ 1558 if ((code == MULT_EXPR && sgn1 == sgn2) 1559 /* For addition, the operands must be of the same sign 1560 to yield an overflow. Its sign is therefore that 1561 of one of the operands, for example the first. For 1562 infinite operands X + -INF is negative, not positive. */ 1563 || (code == PLUS_EXPR 1564 && (sgn1 >= 0 1565 ? !is_negative_overflow_infinity (val2) 1566 : is_positive_overflow_infinity (val2))) 1567 /* For subtraction, non-infinite operands must be of 1568 different signs to yield an overflow. Its sign is 1569 therefore that of the first operand or the opposite of 1570 that of the second operand. A first operand of 0 counts 1571 as positive here, for the corner case 0 - (-INF), which 1572 overflows, but must yield +INF. For infinite operands 0 1573 - INF is negative, not positive. */ 1574 || (code == MINUS_EXPR 1575 && (sgn1 >= 0 1576 ? !is_positive_overflow_infinity (val2) 1577 : is_negative_overflow_infinity (val2))) 1578 /* For division, the only case is -INF / -1 = +INF. */ 1579 || code == TRUNC_DIV_EXPR 1580 || code == FLOOR_DIV_EXPR 1581 || code == CEIL_DIV_EXPR 1582 || code == EXACT_DIV_EXPR 1583 || code == ROUND_DIV_EXPR) 1584 return (needs_overflow_infinity (TREE_TYPE (res)) 1585 ? positive_overflow_infinity (TREE_TYPE (res)) 1586 : TYPE_MAX_VALUE (TREE_TYPE (res))); 1587 else 1588 return (needs_overflow_infinity (TREE_TYPE (res)) 1589 ? negative_overflow_infinity (TREE_TYPE (res)) 1590 : TYPE_MIN_VALUE (TREE_TYPE (res))); 1591 } 1592 1593 return res; 1594} 1595 1596 1597/* Extract range information from a binary expression EXPR based on 1598 the ranges of each of its operands and the expression code. */ 1599 1600static void 1601extract_range_from_binary_expr (value_range_t *vr, tree expr) 1602{ 1603 enum tree_code code = TREE_CODE (expr); 1604 enum value_range_type type; 1605 tree op0, op1, min, max; 1606 int cmp; 1607 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 1608 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 1609 1610 /* Not all binary expressions can be applied to ranges in a 1611 meaningful way. Handle only arithmetic operations. */ 1612 if (code != PLUS_EXPR 1613 && code != MINUS_EXPR 1614 && code != MULT_EXPR 1615 && code != TRUNC_DIV_EXPR 1616 && code != FLOOR_DIV_EXPR 1617 && code != CEIL_DIV_EXPR 1618 && code != EXACT_DIV_EXPR 1619 && code != ROUND_DIV_EXPR 1620 && code != MIN_EXPR 1621 && code != MAX_EXPR 1622 && code != BIT_AND_EXPR 1623 && code != TRUTH_ANDIF_EXPR 1624 && code != TRUTH_ORIF_EXPR 1625 && code != TRUTH_AND_EXPR 1626 && code != TRUTH_OR_EXPR) 1627 { 1628 set_value_range_to_varying (vr); 1629 return; 1630 } 1631 1632 /* Get value ranges for each operand. For constant operands, create 1633 a new value range with the operand to simplify processing. */ 1634 op0 = TREE_OPERAND (expr, 0); 1635 if (TREE_CODE (op0) == SSA_NAME) 1636 vr0 = *(get_value_range (op0)); 1637 else if (is_gimple_min_invariant (op0)) 1638 set_value_range_to_value (&vr0, op0, NULL); 1639 else 1640 set_value_range_to_varying (&vr0); 1641 1642 op1 = TREE_OPERAND (expr, 1); 1643 if (TREE_CODE (op1) == SSA_NAME) 1644 vr1 = *(get_value_range (op1)); 1645 else if (is_gimple_min_invariant (op1)) 1646 set_value_range_to_value (&vr1, op1, NULL); 1647 else 1648 set_value_range_to_varying (&vr1); 1649 1650 /* If either range is UNDEFINED, so is the result. */ 1651 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED) 1652 { 1653 set_value_range_to_undefined (vr); 1654 return; 1655 } 1656 1657 /* The type of the resulting value range defaults to VR0.TYPE. */ 1658 type = vr0.type; 1659 1660 /* Refuse to operate on VARYING ranges, ranges of different kinds 1661 and symbolic ranges. As an exception, we allow BIT_AND_EXPR 1662 because we may be able to derive a useful range even if one of 1663 the operands is VR_VARYING or symbolic range. TODO, we may be 1664 able to derive anti-ranges in some cases. */ 1665 if (code != BIT_AND_EXPR 1666 && code != TRUTH_AND_EXPR 1667 && code != TRUTH_OR_EXPR 1668 && (vr0.type == VR_VARYING 1669 || vr1.type == VR_VARYING 1670 || vr0.type != vr1.type 1671 || symbolic_range_p (&vr0) 1672 || symbolic_range_p (&vr1))) 1673 { 1674 set_value_range_to_varying (vr); 1675 return; 1676 } 1677 1678 /* Now evaluate the expression to determine the new range. */ 1679 if (POINTER_TYPE_P (TREE_TYPE (expr)) 1680 || POINTER_TYPE_P (TREE_TYPE (op0)) 1681 || POINTER_TYPE_P (TREE_TYPE (op1))) 1682 { 1683 /* For pointer types, we are really only interested in asserting 1684 whether the expression evaluates to non-NULL. FIXME, we used 1685 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but 1686 ivopts is generating expressions with pointer multiplication 1687 in them. */ 1688 if (code == PLUS_EXPR) 1689 { 1690 if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1)) 1691 set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 1692 else if (range_is_null (&vr0) && range_is_null (&vr1)) 1693 set_value_range_to_null (vr, TREE_TYPE (expr)); 1694 else 1695 set_value_range_to_varying (vr); 1696 } 1697 else 1698 { 1699 /* Subtracting from a pointer, may yield 0, so just drop the 1700 resulting range to varying. */ 1701 set_value_range_to_varying (vr); 1702 } 1703 1704 return; 1705 } 1706 1707 /* For integer ranges, apply the operation to each end of the 1708 range and see what we end up with. */ 1709 if (code == TRUTH_ANDIF_EXPR 1710 || code == TRUTH_ORIF_EXPR 1711 || code == TRUTH_AND_EXPR 1712 || code == TRUTH_OR_EXPR) 1713 { 1714 /* If one of the operands is zero, we know that the whole 1715 expression evaluates zero. */ 1716 if (code == TRUTH_AND_EXPR 1717 && ((vr0.type == VR_RANGE 1718 && integer_zerop (vr0.min) 1719 && integer_zerop (vr0.max)) 1720 || (vr1.type == VR_RANGE 1721 && integer_zerop (vr1.min) 1722 && integer_zerop (vr1.max)))) 1723 { 1724 type = VR_RANGE; 1725 min = max = build_int_cst (TREE_TYPE (expr), 0); 1726 } 1727 /* If one of the operands is one, we know that the whole 1728 expression evaluates one. */ 1729 else if (code == TRUTH_OR_EXPR 1730 && ((vr0.type == VR_RANGE 1731 && integer_onep (vr0.min) 1732 && integer_onep (vr0.max)) 1733 || (vr1.type == VR_RANGE 1734 && integer_onep (vr1.min) 1735 && integer_onep (vr1.max)))) 1736 { 1737 type = VR_RANGE; 1738 min = max = build_int_cst (TREE_TYPE (expr), 1); 1739 } 1740 else if (vr0.type != VR_VARYING 1741 && vr1.type != VR_VARYING 1742 && vr0.type == vr1.type 1743 && !symbolic_range_p (&vr0) 1744 && !overflow_infinity_range_p (&vr0) 1745 && !symbolic_range_p (&vr1) 1746 && !overflow_infinity_range_p (&vr1)) 1747 { 1748 /* Boolean expressions cannot be folded with int_const_binop. */ 1749 min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min); 1750 max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max); 1751 } 1752 else 1753 { 1754 set_value_range_to_varying (vr); 1755 return; 1756 } 1757 } 1758 else if (code == PLUS_EXPR 1759 || code == MIN_EXPR 1760 || code == MAX_EXPR) 1761 { 1762 /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to 1763 VR_VARYING. It would take more effort to compute a precise 1764 range for such a case. For example, if we have op0 == 1 and 1765 op1 == -1 with their ranges both being ~[0,0], we would have 1766 op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0]. 1767 Note that we are guaranteed to have vr0.type == vr1.type at 1768 this point. */ 1769 if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE) 1770 { 1771 set_value_range_to_varying (vr); 1772 return; 1773 } 1774 1775 /* For operations that make the resulting range directly 1776 proportional to the original ranges, apply the operation to 1777 the same end of each range. */ 1778 min = vrp_int_const_binop (code, vr0.min, vr1.min); 1779 max = vrp_int_const_binop (code, vr0.max, vr1.max); 1780 } 1781 else if (code == MULT_EXPR 1782 || code == TRUNC_DIV_EXPR 1783 || code == FLOOR_DIV_EXPR 1784 || code == CEIL_DIV_EXPR 1785 || code == EXACT_DIV_EXPR 1786 || code == ROUND_DIV_EXPR) 1787 { 1788 tree val[4]; 1789 size_t i; 1790 bool sop; 1791 1792 /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs, 1793 drop to VR_VARYING. It would take more effort to compute a 1794 precise range for such a case. For example, if we have 1795 op0 == 65536 and op1 == 65536 with their ranges both being 1796 ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so 1797 we cannot claim that the product is in ~[0,0]. Note that we 1798 are guaranteed to have vr0.type == vr1.type at this 1799 point. */ 1800 if (code == MULT_EXPR 1801 && vr0.type == VR_ANTI_RANGE 1802 && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))) 1803 { 1804 set_value_range_to_varying (vr); 1805 return; 1806 } 1807 1808 /* Multiplications and divisions are a bit tricky to handle, 1809 depending on the mix of signs we have in the two ranges, we 1810 need to operate on different values to get the minimum and 1811 maximum values for the new range. One approach is to figure 1812 out all the variations of range combinations and do the 1813 operations. 1814 1815 However, this involves several calls to compare_values and it 1816 is pretty convoluted. It's simpler to do the 4 operations 1817 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP 1818 MAX1) and then figure the smallest and largest values to form 1819 the new range. */ 1820 1821 /* Divisions by zero result in a VARYING value. */ 1822 if (code != MULT_EXPR 1823 && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1))) 1824 { 1825 set_value_range_to_varying (vr); 1826 return; 1827 } 1828 1829 /* Compute the 4 cross operations. */ 1830 sop = false; 1831 val[0] = vrp_int_const_binop (code, vr0.min, vr1.min); 1832 if (val[0] == NULL_TREE) 1833 sop = true; 1834 1835 if (vr1.max == vr1.min) 1836 val[1] = NULL_TREE; 1837 else 1838 { 1839 val[1] = vrp_int_const_binop (code, vr0.min, vr1.max); 1840 if (val[1] == NULL_TREE) 1841 sop = true; 1842 } 1843 1844 if (vr0.max == vr0.min) 1845 val[2] = NULL_TREE; 1846 else 1847 { 1848 val[2] = vrp_int_const_binop (code, vr0.max, vr1.min); 1849 if (val[2] == NULL_TREE) 1850 sop = true; 1851 } 1852 1853 if (vr0.min == vr0.max || vr1.min == vr1.max) 1854 val[3] = NULL_TREE; 1855 else 1856 { 1857 val[3] = vrp_int_const_binop (code, vr0.max, vr1.max); 1858 if (val[3] == NULL_TREE) 1859 sop = true; 1860 } 1861 1862 if (sop) 1863 { 1864 set_value_range_to_varying (vr); 1865 return; 1866 } 1867 1868 /* Set MIN to the minimum of VAL[i] and MAX to the maximum 1869 of VAL[i]. */ 1870 min = val[0]; 1871 max = val[0]; 1872 for (i = 1; i < 4; i++) 1873 { 1874 if (!is_gimple_min_invariant (min) 1875 || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) 1876 || !is_gimple_min_invariant (max) 1877 || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) 1878 break; 1879 1880 if (val[i]) 1881 { 1882 if (!is_gimple_min_invariant (val[i]) 1883 || (TREE_OVERFLOW (val[i]) 1884 && !is_overflow_infinity (val[i]))) 1885 { 1886 /* If we found an overflowed value, set MIN and MAX 1887 to it so that we set the resulting range to 1888 VARYING. */ 1889 min = max = val[i]; 1890 break; 1891 } 1892 1893 if (compare_values (val[i], min) == -1) 1894 min = val[i]; 1895 1896 if (compare_values (val[i], max) == 1) 1897 max = val[i]; 1898 } 1899 } 1900 } 1901 else if (code == MINUS_EXPR) 1902 { 1903 /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to 1904 VR_VARYING. It would take more effort to compute a precise 1905 range for such a case. For example, if we have op0 == 1 and 1906 op1 == 1 with their ranges both being ~[0,0], we would have 1907 op0 - op1 == 0, so we cannot claim that the difference is in 1908 ~[0,0]. Note that we are guaranteed to have 1909 vr0.type == vr1.type at this point. */ 1910 if (vr0.type == VR_ANTI_RANGE) 1911 { 1912 set_value_range_to_varying (vr); 1913 return; 1914 } 1915 1916 /* For MINUS_EXPR, apply the operation to the opposite ends of 1917 each range. */ 1918 min = vrp_int_const_binop (code, vr0.min, vr1.max); 1919 max = vrp_int_const_binop (code, vr0.max, vr1.min); 1920 } 1921 else if (code == BIT_AND_EXPR) 1922 { 1923 if (vr0.type == VR_RANGE 1924 && vr0.min == vr0.max 1925 && TREE_CODE (vr0.max) == INTEGER_CST 1926 && !TREE_OVERFLOW (vr0.max) 1927 && tree_int_cst_sgn (vr0.max) >= 0) 1928 { 1929 min = build_int_cst (TREE_TYPE (expr), 0); 1930 max = vr0.max; 1931 } 1932 else if (vr1.type == VR_RANGE 1933 && vr1.min == vr1.max 1934 && TREE_CODE (vr1.max) == INTEGER_CST 1935 && !TREE_OVERFLOW (vr1.max) 1936 && tree_int_cst_sgn (vr1.max) >= 0) 1937 { 1938 type = VR_RANGE; 1939 min = build_int_cst (TREE_TYPE (expr), 0); 1940 max = vr1.max; 1941 } 1942 else 1943 { 1944 set_value_range_to_varying (vr); 1945 return; 1946 } 1947 } 1948 else 1949 gcc_unreachable (); 1950 1951 /* If either MIN or MAX overflowed, then set the resulting range to 1952 VARYING. But we do accept an overflow infinity 1953 representation. */ 1954 if (min == NULL_TREE 1955 || !is_gimple_min_invariant (min) 1956 || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) 1957 || max == NULL_TREE 1958 || !is_gimple_min_invariant (max) 1959 || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) 1960 { 1961 set_value_range_to_varying (vr); 1962 return; 1963 } 1964 1965 /* We punt if: 1966 1) [-INF, +INF] 1967 2) [-INF, +-INF(OVF)] 1968 3) [+-INF(OVF), +INF] 1969 4) [+-INF(OVF), +-INF(OVF)] 1970 We learn nothing when we have INF and INF(OVF) on both sides. 1971 Note that we do accept [-INF, -INF] and [+INF, +INF] without 1972 overflow. */ 1973 if ((vrp_val_is_min (min) || is_overflow_infinity (min)) 1974 && (vrp_val_is_max (max) || is_overflow_infinity (max))) 1975 { 1976 set_value_range_to_varying (vr); 1977 return; 1978 } 1979 1980 cmp = compare_values (min, max); 1981 if (cmp == -2 || cmp == 1) 1982 { 1983 /* If the new range has its limits swapped around (MIN > MAX), 1984 then the operation caused one of them to wrap around, mark 1985 the new range VARYING. */ 1986 set_value_range_to_varying (vr); 1987 } 1988 else 1989 set_value_range (vr, type, min, max, NULL); 1990} 1991 1992 1993/* Extract range information from a unary expression EXPR based on 1994 the range of its operand and the expression code. */ 1995 1996static void 1997extract_range_from_unary_expr (value_range_t *vr, tree expr) 1998{ 1999 enum tree_code code = TREE_CODE (expr); 2000 tree min, max, op0; 2001 int cmp; 2002 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 2003 2004 /* Refuse to operate on certain unary expressions for which we 2005 cannot easily determine a resulting range. */ 2006 if (code == FIX_TRUNC_EXPR 2007 || code == FIX_CEIL_EXPR 2008 || code == FIX_FLOOR_EXPR 2009 || code == FIX_ROUND_EXPR 2010 || code == FLOAT_EXPR 2011 || code == BIT_NOT_EXPR 2012 || code == NON_LVALUE_EXPR 2013 || code == CONJ_EXPR) 2014 { 2015 set_value_range_to_varying (vr); 2016 return; 2017 } 2018 2019 /* Get value ranges for the operand. For constant operands, create 2020 a new value range with the operand to simplify processing. */ 2021 op0 = TREE_OPERAND (expr, 0); 2022 if (TREE_CODE (op0) == SSA_NAME) 2023 vr0 = *(get_value_range (op0)); 2024 else if (is_gimple_min_invariant (op0)) 2025 set_value_range_to_value (&vr0, op0, NULL); 2026 else 2027 set_value_range_to_varying (&vr0); 2028 2029 /* If VR0 is UNDEFINED, so is the result. */ 2030 if (vr0.type == VR_UNDEFINED) 2031 { 2032 set_value_range_to_undefined (vr); 2033 return; 2034 } 2035 2036 /* Refuse to operate on symbolic ranges, or if neither operand is 2037 a pointer or integral type. */ 2038 if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 2039 && !POINTER_TYPE_P (TREE_TYPE (op0))) 2040 || (vr0.type != VR_VARYING 2041 && symbolic_range_p (&vr0))) 2042 { 2043 set_value_range_to_varying (vr); 2044 return; 2045 } 2046 2047 /* If the expression involves pointers, we are only interested in 2048 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */ 2049 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0))) 2050 { 2051 bool sop; 2052 2053 sop = false; 2054 if (range_is_nonnull (&vr0) 2055 || (tree_expr_nonzero_warnv_p (expr, &sop) 2056 && !sop)) 2057 set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 2058 else if (range_is_null (&vr0)) 2059 set_value_range_to_null (vr, TREE_TYPE (expr)); 2060 else 2061 set_value_range_to_varying (vr); 2062 2063 return; 2064 } 2065 2066 /* Handle unary expressions on integer ranges. */ 2067 if (code == NOP_EXPR || code == CONVERT_EXPR) 2068 { 2069 tree inner_type = TREE_TYPE (op0); 2070 tree outer_type = TREE_TYPE (expr); 2071 2072 /* If VR0 represents a simple range, then try to convert 2073 the min and max values for the range to the same type 2074 as OUTER_TYPE. If the results compare equal to VR0's 2075 min and max values and the new min is still less than 2076 or equal to the new max, then we can safely use the newly 2077 computed range for EXPR. This allows us to compute 2078 accurate ranges through many casts. */ 2079 if ((vr0.type == VR_RANGE 2080 && !overflow_infinity_range_p (&vr0)) 2081 || (vr0.type == VR_VARYING 2082 && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type))) 2083 { 2084 tree new_min, new_max, orig_min, orig_max; 2085 2086 /* Convert the input operand min/max to OUTER_TYPE. If 2087 the input has no range information, then use the min/max 2088 for the input's type. */ 2089 if (vr0.type == VR_RANGE) 2090 { 2091 orig_min = vr0.min; 2092 orig_max = vr0.max; 2093 } 2094 else 2095 { 2096 orig_min = TYPE_MIN_VALUE (inner_type); 2097 orig_max = TYPE_MAX_VALUE (inner_type); 2098 } 2099 2100 new_min = fold_convert (outer_type, orig_min); 2101 new_max = fold_convert (outer_type, orig_max); 2102 2103 /* Verify the new min/max values are gimple values and 2104 that they compare equal to the original input's 2105 min/max values. */ 2106 if (is_gimple_val (new_min) 2107 && is_gimple_val (new_max) 2108 && tree_int_cst_equal (new_min, orig_min) 2109 && tree_int_cst_equal (new_max, orig_max) 2110 && (!is_overflow_infinity (new_min) 2111 || !is_overflow_infinity (new_max)) 2112 && compare_values (new_min, new_max) <= 0 2113 && compare_values (new_min, new_max) >= -1) 2114 { 2115 set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv); 2116 return; 2117 } 2118 } 2119 2120 /* When converting types of different sizes, set the result to 2121 VARYING. Things like sign extensions and precision loss may 2122 change the range. For instance, if x_3 is of type 'long long 2123 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it 2124 is impossible to know at compile time whether y_5 will be 2125 ~[0, 0]. */ 2126 if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type) 2127 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type)) 2128 { 2129 set_value_range_to_varying (vr); 2130 return; 2131 } 2132 } 2133 2134 /* Conversion of a VR_VARYING value to a wider type can result 2135 in a usable range. So wait until after we've handled conversions 2136 before dropping the result to VR_VARYING if we had a source 2137 operand that is VR_VARYING. */ 2138 if (vr0.type == VR_VARYING) 2139 { 2140 set_value_range_to_varying (vr); 2141 return; 2142 } 2143 2144 /* Apply the operation to each end of the range and see what we end 2145 up with. */ 2146 if (code == NEGATE_EXPR 2147 && !TYPE_UNSIGNED (TREE_TYPE (expr))) 2148 { 2149 /* NEGATE_EXPR flips the range around. We need to treat 2150 TYPE_MIN_VALUE specially. */ 2151 if (is_positive_overflow_infinity (vr0.max)) 2152 min = negative_overflow_infinity (TREE_TYPE (expr)); 2153 else if (is_negative_overflow_infinity (vr0.max)) 2154 min = positive_overflow_infinity (TREE_TYPE (expr)); 2155 else if (!vrp_val_is_min (vr0.max)) 2156 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 2157 else if (needs_overflow_infinity (TREE_TYPE (expr))) 2158 { 2159 if (supports_overflow_infinity (TREE_TYPE (expr)) 2160 && !is_overflow_infinity (vr0.min) 2161 && !vrp_val_is_min (vr0.min)) 2162 min = positive_overflow_infinity (TREE_TYPE (expr)); 2163 else 2164 { 2165 set_value_range_to_varying (vr); 2166 return; 2167 } 2168 } 2169 else 2170 min = TYPE_MIN_VALUE (TREE_TYPE (expr)); 2171 2172 if (is_positive_overflow_infinity (vr0.min)) 2173 max = negative_overflow_infinity (TREE_TYPE (expr)); 2174 else if (is_negative_overflow_infinity (vr0.min)) 2175 max = positive_overflow_infinity (TREE_TYPE (expr)); 2176 else if (!vrp_val_is_min (vr0.min)) 2177 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 2178 else if (needs_overflow_infinity (TREE_TYPE (expr))) 2179 { 2180 if (supports_overflow_infinity (TREE_TYPE (expr))) 2181 max = positive_overflow_infinity (TREE_TYPE (expr)); 2182 else 2183 { 2184 set_value_range_to_varying (vr); 2185 return; 2186 } 2187 } 2188 else 2189 max = TYPE_MIN_VALUE (TREE_TYPE (expr)); 2190 } 2191 else if (code == NEGATE_EXPR 2192 && TYPE_UNSIGNED (TREE_TYPE (expr))) 2193 { 2194 if (!range_includes_zero_p (&vr0)) 2195 { 2196 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 2197 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 2198 } 2199 else 2200 { 2201 if (range_is_null (&vr0)) 2202 set_value_range_to_null (vr, TREE_TYPE (expr)); 2203 else 2204 set_value_range_to_varying (vr); 2205 return; 2206 } 2207 } 2208 else if (code == ABS_EXPR 2209 && !TYPE_UNSIGNED (TREE_TYPE (expr))) 2210 { 2211 /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a 2212 useful range. */ 2213 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (expr)) 2214 && ((vr0.type == VR_RANGE 2215 && vrp_val_is_min (vr0.min)) 2216 || (vr0.type == VR_ANTI_RANGE 2217 && !vrp_val_is_min (vr0.min) 2218 && !range_includes_zero_p (&vr0)))) 2219 { 2220 set_value_range_to_varying (vr); 2221 return; 2222 } 2223 2224 /* ABS_EXPR may flip the range around, if the original range 2225 included negative values. */ 2226 if (is_overflow_infinity (vr0.min)) 2227 min = positive_overflow_infinity (TREE_TYPE (expr)); 2228 else if (!vrp_val_is_min (vr0.min)) 2229 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 2230 else if (!needs_overflow_infinity (TREE_TYPE (expr))) 2231 min = TYPE_MAX_VALUE (TREE_TYPE (expr)); 2232 else if (supports_overflow_infinity (TREE_TYPE (expr))) 2233 min = positive_overflow_infinity (TREE_TYPE (expr)); 2234 else 2235 { 2236 set_value_range_to_varying (vr); 2237 return; 2238 } 2239 2240 if (is_overflow_infinity (vr0.max)) 2241 max = positive_overflow_infinity (TREE_TYPE (expr)); 2242 else if (!vrp_val_is_min (vr0.max)) 2243 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 2244 else if (!needs_overflow_infinity (TREE_TYPE (expr))) 2245 max = TYPE_MAX_VALUE (TREE_TYPE (expr)); 2246 else if (supports_overflow_infinity (TREE_TYPE (expr))) 2247 max = positive_overflow_infinity (TREE_TYPE (expr)); 2248 else 2249 { 2250 set_value_range_to_varying (vr); 2251 return; 2252 } 2253 2254 cmp = compare_values (min, max); 2255 2256 /* If a VR_ANTI_RANGEs contains zero, then we have 2257 ~[-INF, min(MIN, MAX)]. */ 2258 if (vr0.type == VR_ANTI_RANGE) 2259 { 2260 if (range_includes_zero_p (&vr0)) 2261 { 2262 /* Take the lower of the two values. */ 2263 if (cmp != 1) 2264 max = min; 2265 2266 /* Create ~[-INF, min (abs(MIN), abs(MAX))] 2267 or ~[-INF + 1, min (abs(MIN), abs(MAX))] when 2268 flag_wrapv is set and the original anti-range doesn't include 2269 TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */ 2270 if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) 2271 { 2272 tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr)); 2273 2274 min = (vr0.min != type_min_value 2275 ? int_const_binop (PLUS_EXPR, type_min_value, 2276 integer_one_node, 0) 2277 : type_min_value); 2278 } 2279 else 2280 { 2281 if (overflow_infinity_range_p (&vr0)) 2282 min = negative_overflow_infinity (TREE_TYPE (expr)); 2283 else 2284 min = TYPE_MIN_VALUE (TREE_TYPE (expr)); 2285 } 2286 } 2287 else 2288 { 2289 /* All else has failed, so create the range [0, INF], even for 2290 flag_wrapv since TYPE_MIN_VALUE is in the original 2291 anti-range. */ 2292 vr0.type = VR_RANGE; 2293 min = build_int_cst (TREE_TYPE (expr), 0); 2294 if (needs_overflow_infinity (TREE_TYPE (expr))) 2295 { 2296 if (supports_overflow_infinity (TREE_TYPE (expr))) 2297 max = positive_overflow_infinity (TREE_TYPE (expr)); 2298 else 2299 { 2300 set_value_range_to_varying (vr); 2301 return; 2302 } 2303 } 2304 else 2305 max = TYPE_MAX_VALUE (TREE_TYPE (expr)); 2306 } 2307 } 2308 2309 /* If the range contains zero then we know that the minimum value in the 2310 range will be zero. */ 2311 else if (range_includes_zero_p (&vr0)) 2312 { 2313 if (cmp == 1) 2314 max = min; 2315 min = build_int_cst (TREE_TYPE (expr), 0); 2316 } 2317 else 2318 { 2319 /* If the range was reversed, swap MIN and MAX. */ 2320 if (cmp == 1) 2321 { 2322 tree t = min; 2323 min = max; 2324 max = t; 2325 } 2326 } 2327 } 2328 else 2329 { 2330 /* Otherwise, operate on each end of the range. */ 2331 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 2332 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 2333 2334 if (needs_overflow_infinity (TREE_TYPE (expr))) 2335 { 2336 gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR); 2337 2338 /* If both sides have overflowed, we don't know 2339 anything. */ 2340 if ((is_overflow_infinity (vr0.min) 2341 || TREE_OVERFLOW (min)) 2342 && (is_overflow_infinity (vr0.max) 2343 || TREE_OVERFLOW (max))) 2344 { 2345 set_value_range_to_varying (vr); 2346 return; 2347 } 2348 2349 if (is_overflow_infinity (vr0.min)) 2350 min = vr0.min; 2351 else if (TREE_OVERFLOW (min)) 2352 { 2353 if (supports_overflow_infinity (TREE_TYPE (expr))) 2354 min = (tree_int_cst_sgn (min) >= 0 2355 ? positive_overflow_infinity (TREE_TYPE (min)) 2356 : negative_overflow_infinity (TREE_TYPE (min))); 2357 else 2358 { 2359 set_value_range_to_varying (vr); 2360 return; 2361 } 2362 } 2363 2364 if (is_overflow_infinity (vr0.max)) 2365 max = vr0.max; 2366 else if (TREE_OVERFLOW (max)) 2367 { 2368 if (supports_overflow_infinity (TREE_TYPE (expr))) 2369 max = (tree_int_cst_sgn (max) >= 0 2370 ? positive_overflow_infinity (TREE_TYPE (max)) 2371 : negative_overflow_infinity (TREE_TYPE (max))); 2372 else 2373 { 2374 set_value_range_to_varying (vr); 2375 return; 2376 } 2377 } 2378 } 2379 } 2380 2381 cmp = compare_values (min, max); 2382 if (cmp == -2 || cmp == 1) 2383 { 2384 /* If the new range has its limits swapped around (MIN > MAX), 2385 then the operation caused one of them to wrap around, mark 2386 the new range VARYING. */ 2387 set_value_range_to_varying (vr); 2388 } 2389 else 2390 set_value_range (vr, vr0.type, min, max, NULL); 2391} 2392 2393 2394/* Extract range information from a comparison expression EXPR based 2395 on the range of its operand and the expression code. */ 2396 2397static void 2398extract_range_from_comparison (value_range_t *vr, tree expr) 2399{ 2400 bool sop = false; 2401 tree val = vrp_evaluate_conditional_warnv (expr, false, &sop); 2402 2403 /* A disadvantage of using a special infinity as an overflow 2404 representation is that we lose the ability to record overflow 2405 when we don't have an infinity. So we have to ignore a result 2406 which relies on overflow. */ 2407 2408 if (val && !is_overflow_infinity (val) && !sop) 2409 { 2410 /* Since this expression was found on the RHS of an assignment, 2411 its type may be different from _Bool. Convert VAL to EXPR's 2412 type. */ 2413 val = fold_convert (TREE_TYPE (expr), val); 2414 if (is_gimple_min_invariant (val)) 2415 set_value_range_to_value (vr, val, vr->equiv); 2416 else 2417 set_value_range (vr, VR_RANGE, val, val, vr->equiv); 2418 } 2419 else 2420 set_value_range_to_varying (vr); 2421} 2422 2423 2424/* Try to compute a useful range out of expression EXPR and store it 2425 in *VR. */ 2426 2427static void 2428extract_range_from_expr (value_range_t *vr, tree expr) 2429{ 2430 enum tree_code code = TREE_CODE (expr); 2431 2432 if (code == ASSERT_EXPR) 2433 extract_range_from_assert (vr, expr); 2434 else if (code == SSA_NAME) 2435 extract_range_from_ssa_name (vr, expr); 2436 else if (TREE_CODE_CLASS (code) == tcc_binary 2437 || code == TRUTH_ANDIF_EXPR 2438 || code == TRUTH_ORIF_EXPR 2439 || code == TRUTH_AND_EXPR 2440 || code == TRUTH_OR_EXPR 2441 || code == TRUTH_XOR_EXPR) 2442 extract_range_from_binary_expr (vr, expr); 2443 else if (TREE_CODE_CLASS (code) == tcc_unary) 2444 extract_range_from_unary_expr (vr, expr); 2445 else if (TREE_CODE_CLASS (code) == tcc_comparison) 2446 extract_range_from_comparison (vr, expr); 2447 else if (is_gimple_min_invariant (expr)) 2448 set_value_range_to_value (vr, expr, NULL); 2449 else 2450 set_value_range_to_varying (vr); 2451 2452 /* If we got a varying range from the tests above, try a final 2453 time to derive a nonnegative or nonzero range. This time 2454 relying primarily on generic routines in fold in conjunction 2455 with range data. */ 2456 if (vr->type == VR_VARYING) 2457 { 2458 bool sop = false; 2459 2460 if (INTEGRAL_TYPE_P (TREE_TYPE (expr)) 2461 && vrp_expr_computes_nonnegative (expr, &sop)) 2462 set_value_range_to_nonnegative (vr, TREE_TYPE (expr), 2463 sop || is_overflow_infinity (expr)); 2464 else if (vrp_expr_computes_nonzero (expr, &sop) 2465 && !sop) 2466 set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 2467 } 2468} 2469 2470/* Given a range VR, a LOOP and a variable VAR, determine whether it 2471 would be profitable to adjust VR using scalar evolution information 2472 for VAR. If so, update VR with the new limits. */ 2473 2474static void 2475adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, 2476 tree var) 2477{ 2478 tree init, step, chrec, tmin, tmax, min, max, type; 2479 enum ev_direction dir; 2480 2481 /* TODO. Don't adjust anti-ranges. An anti-range may provide 2482 better opportunities than a regular range, but I'm not sure. */ 2483 if (vr->type == VR_ANTI_RANGE) 2484 return; 2485 2486 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); 2487 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 2488 return; 2489 2490 init = initial_condition_in_loop_num (chrec, loop->num); 2491 step = evolution_part_in_loop_num (chrec, loop->num); 2492 2493 /* If STEP is symbolic, we can't know whether INIT will be the 2494 minimum or maximum value in the range. Also, unless INIT is 2495 a simple expression, compare_values and possibly other functions 2496 in tree-vrp won't be able to handle it. */ 2497 if (step == NULL_TREE 2498 || !is_gimple_min_invariant (step) 2499 || !valid_value_p (init)) 2500 return; 2501 2502 dir = scev_direction (chrec); 2503 if (/* Do not adjust ranges if we do not know whether the iv increases 2504 or decreases, ... */ 2505 dir == EV_DIR_UNKNOWN 2506 /* ... or if it may wrap. */ 2507 || scev_probably_wraps_p (init, step, stmt, 2508 current_loops->parray[CHREC_VARIABLE (chrec)], 2509 true)) 2510 return; 2511 2512 type = TREE_TYPE (var); 2513 2514 /* If we see a pointer type starting at a constant, then we have an 2515 unusual ivopt. It may legitimately wrap. */ 2516 if (POINTER_TYPE_P (type) && is_gimple_min_invariant (init)) 2517 return; 2518 2519 /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of 2520 negative_overflow_infinity and positive_overflow_infinity, 2521 because we have concluded that the loop probably does not 2522 wrap. */ 2523 2524 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) 2525 tmin = lower_bound_in_type (type, type); 2526 else 2527 tmin = TYPE_MIN_VALUE (type); 2528 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) 2529 tmax = upper_bound_in_type (type, type); 2530 else 2531 tmax = TYPE_MAX_VALUE (type); 2532 2533 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 2534 { 2535 min = tmin; 2536 max = tmax; 2537 2538 /* For VARYING or UNDEFINED ranges, just about anything we get 2539 from scalar evolutions should be better. */ 2540 2541 if (dir == EV_DIR_DECREASES) 2542 max = init; 2543 else 2544 min = init; 2545 2546 /* If we would create an invalid range, then just assume we 2547 know absolutely nothing. This may be over-conservative, 2548 but it's clearly safe, and should happen only in unreachable 2549 parts of code, or for invalid programs. */ 2550 if (compare_values (min, max) == 1) 2551 return; 2552 2553 set_value_range (vr, VR_RANGE, min, max, vr->equiv); 2554 } 2555 else if (vr->type == VR_RANGE) 2556 { 2557 min = vr->min; 2558 max = vr->max; 2559 2560 if (dir == EV_DIR_DECREASES) 2561 { 2562 /* INIT is the maximum value. If INIT is lower than VR->MAX 2563 but no smaller than VR->MIN, set VR->MAX to INIT. */ 2564 if (compare_values (init, max) == -1) 2565 { 2566 max = init; 2567 2568 /* If we just created an invalid range with the minimum 2569 greater than the maximum, we fail conservatively. 2570 This should happen only in unreachable 2571 parts of code, or for invalid programs. */ 2572 if (compare_values (min, max) == 1) 2573 return; 2574 } 2575 2576 /* According to the loop information, the variable does not 2577 overflow. If we think it does, probably because of an 2578 overflow due to arithmetic on a different INF value, 2579 reset now. */ 2580 if (is_negative_overflow_infinity (min)) 2581 min = tmin; 2582 } 2583 else 2584 { 2585 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */ 2586 if (compare_values (init, min) == 1) 2587 { 2588 min = init; 2589 2590 /* Again, avoid creating invalid range by failing. */ 2591 if (compare_values (min, max) == 1) 2592 return; 2593 } 2594 2595 if (is_positive_overflow_infinity (max)) 2596 max = tmax; 2597 } 2598 2599 set_value_range (vr, VR_RANGE, min, max, vr->equiv); 2600 } 2601} 2602 2603/* Return true if VAR may overflow at STMT. This checks any available 2604 loop information to see if we can determine that VAR does not 2605 overflow. */ 2606 2607static bool 2608vrp_var_may_overflow (tree var, tree stmt) 2609{ 2610 struct loop *l; 2611 tree chrec, init, step; 2612 2613 if (current_loops == NULL) 2614 return true; 2615 2616 l = loop_containing_stmt (stmt); 2617 if (l == NULL) 2618 return true; 2619 2620 chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var)); 2621 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 2622 return true; 2623 2624 init = initial_condition_in_loop_num (chrec, l->num); 2625 step = evolution_part_in_loop_num (chrec, l->num); 2626 2627 if (step == NULL_TREE 2628 || !is_gimple_min_invariant (step) 2629 || !valid_value_p (init)) 2630 return true; 2631 2632 /* If we get here, we know something useful about VAR based on the 2633 loop information. If it wraps, it may overflow. */ 2634 2635 if (scev_probably_wraps_p (init, step, stmt, 2636 current_loops->parray[CHREC_VARIABLE (chrec)], 2637 true)) 2638 return true; 2639 2640 if (dump_file && (dump_flags & TDF_DETAILS) != 0) 2641 { 2642 print_generic_expr (dump_file, var, 0); 2643 fprintf (dump_file, ": loop information indicates does not overflow\n"); 2644 } 2645 2646 return false; 2647} 2648 2649 2650/* Given two numeric value ranges VR0, VR1 and a comparison code COMP: 2651 2652 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for 2653 all the values in the ranges. 2654 2655 - Return BOOLEAN_FALSE_NODE if the comparison always returns false. 2656 2657 - Return NULL_TREE if it is not always possible to determine the 2658 value of the comparison. 2659 2660 Also set *STRICT_OVERFLOW_P to indicate whether a range with an 2661 overflow infinity was used in the test. */ 2662 2663 2664static tree 2665compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1, 2666 bool *strict_overflow_p) 2667{ 2668 /* VARYING or UNDEFINED ranges cannot be compared. */ 2669 if (vr0->type == VR_VARYING 2670 || vr0->type == VR_UNDEFINED 2671 || vr1->type == VR_VARYING 2672 || vr1->type == VR_UNDEFINED) 2673 return NULL_TREE; 2674 2675 /* Anti-ranges need to be handled separately. */ 2676 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 2677 { 2678 /* If both are anti-ranges, then we cannot compute any 2679 comparison. */ 2680 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 2681 return NULL_TREE; 2682 2683 /* These comparisons are never statically computable. */ 2684 if (comp == GT_EXPR 2685 || comp == GE_EXPR 2686 || comp == LT_EXPR 2687 || comp == LE_EXPR) 2688 return NULL_TREE; 2689 2690 /* Equality can be computed only between a range and an 2691 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */ 2692 if (vr0->type == VR_RANGE) 2693 { 2694 /* To simplify processing, make VR0 the anti-range. */ 2695 value_range_t *tmp = vr0; 2696 vr0 = vr1; 2697 vr1 = tmp; 2698 } 2699 2700 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR); 2701 2702 if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0 2703 && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0) 2704 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 2705 2706 return NULL_TREE; 2707 } 2708 2709 if (!usable_range_p (vr0, strict_overflow_p) 2710 || !usable_range_p (vr1, strict_overflow_p)) 2711 return NULL_TREE; 2712 2713 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the 2714 operands around and change the comparison code. */ 2715 if (comp == GT_EXPR || comp == GE_EXPR) 2716 { 2717 value_range_t *tmp; 2718 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR; 2719 tmp = vr0; 2720 vr0 = vr1; 2721 vr1 = tmp; 2722 } 2723 2724 if (comp == EQ_EXPR) 2725 { 2726 /* Equality may only be computed if both ranges represent 2727 exactly one value. */ 2728 if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0 2729 && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0) 2730 { 2731 int cmp_min = compare_values_warnv (vr0->min, vr1->min, 2732 strict_overflow_p); 2733 int cmp_max = compare_values_warnv (vr0->max, vr1->max, 2734 strict_overflow_p); 2735 if (cmp_min == 0 && cmp_max == 0) 2736 return boolean_true_node; 2737 else if (cmp_min != -2 && cmp_max != -2) 2738 return boolean_false_node; 2739 } 2740 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */ 2741 else if (compare_values_warnv (vr0->min, vr1->max, 2742 strict_overflow_p) == 1 2743 || compare_values_warnv (vr1->min, vr0->max, 2744 strict_overflow_p) == 1) 2745 return boolean_false_node; 2746 2747 return NULL_TREE; 2748 } 2749 else if (comp == NE_EXPR) 2750 { 2751 int cmp1, cmp2; 2752 2753 /* If VR0 is completely to the left or completely to the right 2754 of VR1, they are always different. Notice that we need to 2755 make sure that both comparisons yield similar results to 2756 avoid comparing values that cannot be compared at 2757 compile-time. */ 2758 cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); 2759 cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); 2760 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1)) 2761 return boolean_true_node; 2762 2763 /* If VR0 and VR1 represent a single value and are identical, 2764 return false. */ 2765 else if (compare_values_warnv (vr0->min, vr0->max, 2766 strict_overflow_p) == 0 2767 && compare_values_warnv (vr1->min, vr1->max, 2768 strict_overflow_p) == 0 2769 && compare_values_warnv (vr0->min, vr1->min, 2770 strict_overflow_p) == 0 2771 && compare_values_warnv (vr0->max, vr1->max, 2772 strict_overflow_p) == 0) 2773 return boolean_false_node; 2774 2775 /* Otherwise, they may or may not be different. */ 2776 else 2777 return NULL_TREE; 2778 } 2779 else if (comp == LT_EXPR || comp == LE_EXPR) 2780 { 2781 int tst; 2782 2783 /* If VR0 is to the left of VR1, return true. */ 2784 tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); 2785 if ((comp == LT_EXPR && tst == -1) 2786 || (comp == LE_EXPR && (tst == -1 || tst == 0))) 2787 { 2788 if (overflow_infinity_range_p (vr0) 2789 || overflow_infinity_range_p (vr1)) 2790 *strict_overflow_p = true; 2791 return boolean_true_node; 2792 } 2793 2794 /* If VR0 is to the right of VR1, return false. */ 2795 tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); 2796 if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 2797 || (comp == LE_EXPR && tst == 1)) 2798 { 2799 if (overflow_infinity_range_p (vr0) 2800 || overflow_infinity_range_p (vr1)) 2801 *strict_overflow_p = true; 2802 return boolean_false_node; 2803 } 2804 2805 /* Otherwise, we don't know. */ 2806 return NULL_TREE; 2807 } 2808 2809 gcc_unreachable (); 2810} 2811 2812 2813/* Given a value range VR, a value VAL and a comparison code COMP, return 2814 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the 2815 values in VR. Return BOOLEAN_FALSE_NODE if the comparison 2816 always returns false. Return NULL_TREE if it is not always 2817 possible to determine the value of the comparison. Also set 2818 *STRICT_OVERFLOW_P to indicate whether a range with an overflow 2819 infinity was used in the test. */ 2820 2821static tree 2822compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val, 2823 bool *strict_overflow_p) 2824{ 2825 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 2826 return NULL_TREE; 2827 2828 /* Anti-ranges need to be handled separately. */ 2829 if (vr->type == VR_ANTI_RANGE) 2830 { 2831 /* For anti-ranges, the only predicates that we can compute at 2832 compile time are equality and inequality. */ 2833 if (comp == GT_EXPR 2834 || comp == GE_EXPR 2835 || comp == LT_EXPR 2836 || comp == LE_EXPR) 2837 return NULL_TREE; 2838 2839 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */ 2840 if (value_inside_range (val, vr) == 1) 2841 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 2842 2843 return NULL_TREE; 2844 } 2845 2846 if (!usable_range_p (vr, strict_overflow_p)) 2847 return NULL_TREE; 2848 2849 if (comp == EQ_EXPR) 2850 { 2851 /* EQ_EXPR may only be computed if VR represents exactly 2852 one value. */ 2853 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0) 2854 { 2855 int cmp = compare_values_warnv (vr->min, val, strict_overflow_p); 2856 if (cmp == 0) 2857 return boolean_true_node; 2858 else if (cmp == -1 || cmp == 1 || cmp == 2) 2859 return boolean_false_node; 2860 } 2861 else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1 2862 || compare_values_warnv (vr->max, val, strict_overflow_p) == -1) 2863 return boolean_false_node; 2864 2865 return NULL_TREE; 2866 } 2867 else if (comp == NE_EXPR) 2868 { 2869 /* If VAL is not inside VR, then they are always different. */ 2870 if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1 2871 || compare_values_warnv (vr->min, val, strict_overflow_p) == 1) 2872 return boolean_true_node; 2873 2874 /* If VR represents exactly one value equal to VAL, then return 2875 false. */ 2876 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0 2877 && compare_values_warnv (vr->min, val, strict_overflow_p) == 0) 2878 return boolean_false_node; 2879 2880 /* Otherwise, they may or may not be different. */ 2881 return NULL_TREE; 2882 } 2883 else if (comp == LT_EXPR || comp == LE_EXPR) 2884 { 2885 int tst; 2886 2887 /* If VR is to the left of VAL, return true. */ 2888 tst = compare_values_warnv (vr->max, val, strict_overflow_p); 2889 if ((comp == LT_EXPR && tst == -1) 2890 || (comp == LE_EXPR && (tst == -1 || tst == 0))) 2891 { 2892 if (overflow_infinity_range_p (vr)) 2893 *strict_overflow_p = true; 2894 return boolean_true_node; 2895 } 2896 2897 /* If VR is to the right of VAL, return false. */ 2898 tst = compare_values_warnv (vr->min, val, strict_overflow_p); 2899 if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 2900 || (comp == LE_EXPR && tst == 1)) 2901 { 2902 if (overflow_infinity_range_p (vr)) 2903 *strict_overflow_p = true; 2904 return boolean_false_node; 2905 } 2906 2907 /* Otherwise, we don't know. */ 2908 return NULL_TREE; 2909 } 2910 else if (comp == GT_EXPR || comp == GE_EXPR) 2911 { 2912 int tst; 2913 2914 /* If VR is to the right of VAL, return true. */ 2915 tst = compare_values_warnv (vr->min, val, strict_overflow_p); 2916 if ((comp == GT_EXPR && tst == 1) 2917 || (comp == GE_EXPR && (tst == 0 || tst == 1))) 2918 { 2919 if (overflow_infinity_range_p (vr)) 2920 *strict_overflow_p = true; 2921 return boolean_true_node; 2922 } 2923 2924 /* If VR is to the left of VAL, return false. */ 2925 tst = compare_values_warnv (vr->max, val, strict_overflow_p); 2926 if ((comp == GT_EXPR && (tst == -1 || tst == 0)) 2927 || (comp == GE_EXPR && tst == -1)) 2928 { 2929 if (overflow_infinity_range_p (vr)) 2930 *strict_overflow_p = true; 2931 return boolean_false_node; 2932 } 2933 2934 /* Otherwise, we don't know. */ 2935 return NULL_TREE; 2936 } 2937 2938 gcc_unreachable (); 2939} 2940 2941 2942/* Debugging dumps. */ 2943 2944void dump_value_range (FILE *, value_range_t *); 2945void debug_value_range (value_range_t *); 2946void dump_all_value_ranges (FILE *); 2947void debug_all_value_ranges (void); 2948void dump_vr_equiv (FILE *, bitmap); 2949void debug_vr_equiv (bitmap); 2950 2951 2952/* Dump value range VR to FILE. */ 2953 2954void 2955dump_value_range (FILE *file, value_range_t *vr) 2956{ 2957 if (vr == NULL) 2958 fprintf (file, "[]"); 2959 else if (vr->type == VR_UNDEFINED) 2960 fprintf (file, "UNDEFINED"); 2961 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE) 2962 { 2963 tree type = TREE_TYPE (vr->min); 2964 2965 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); 2966 2967 if (is_negative_overflow_infinity (vr->min)) 2968 fprintf (file, "-INF(OVF)"); 2969 else if (INTEGRAL_TYPE_P (type) 2970 && !TYPE_UNSIGNED (type) 2971 && vrp_val_is_min (vr->min)) 2972 fprintf (file, "-INF"); 2973 else 2974 print_generic_expr (file, vr->min, 0); 2975 2976 fprintf (file, ", "); 2977 2978 if (is_positive_overflow_infinity (vr->max)) 2979 fprintf (file, "+INF(OVF)"); 2980 else if (INTEGRAL_TYPE_P (type) 2981 && vrp_val_is_max (vr->max)) 2982 fprintf (file, "+INF"); 2983 else 2984 print_generic_expr (file, vr->max, 0); 2985 2986 fprintf (file, "]"); 2987 2988 if (vr->equiv) 2989 { 2990 bitmap_iterator bi; 2991 unsigned i, c = 0; 2992 2993 fprintf (file, " EQUIVALENCES: { "); 2994 2995 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi) 2996 { 2997 print_generic_expr (file, ssa_name (i), 0); 2998 fprintf (file, " "); 2999 c++; 3000 } 3001 3002 fprintf (file, "} (%u elements)", c); 3003 } 3004 } 3005 else if (vr->type == VR_VARYING) 3006 fprintf (file, "VARYING"); 3007 else 3008 fprintf (file, "INVALID RANGE"); 3009} 3010 3011 3012/* Dump value range VR to stderr. */ 3013 3014void 3015debug_value_range (value_range_t *vr) 3016{ 3017 dump_value_range (stderr, vr); 3018 fprintf (stderr, "\n"); 3019} 3020 3021 3022/* Dump value ranges of all SSA_NAMEs to FILE. */ 3023 3024void 3025dump_all_value_ranges (FILE *file) 3026{ 3027 size_t i; 3028 3029 for (i = 0; i < num_ssa_names; i++) 3030 { 3031 if (vr_value[i]) 3032 { 3033 print_generic_expr (file, ssa_name (i), 0); 3034 fprintf (file, ": "); 3035 dump_value_range (file, vr_value[i]); 3036 fprintf (file, "\n"); 3037 } 3038 } 3039 3040 fprintf (file, "\n"); 3041} 3042 3043 3044/* Dump all value ranges to stderr. */ 3045 3046void 3047debug_all_value_ranges (void) 3048{ 3049 dump_all_value_ranges (stderr); 3050} 3051 3052 3053/* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V, 3054 create a new SSA name N and return the assertion assignment 3055 'V = ASSERT_EXPR <V, V OP W>'. */ 3056 3057static tree 3058build_assert_expr_for (tree cond, tree v) 3059{ 3060 tree n, assertion; 3061 3062 gcc_assert (TREE_CODE (v) == SSA_NAME); 3063 n = duplicate_ssa_name (v, NULL_TREE); 3064 3065 if (COMPARISON_CLASS_P (cond)) 3066 { 3067 tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond); 3068 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a); 3069 } 3070 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 3071 { 3072 /* Given !V, build the assignment N = false. */ 3073 tree op0 = TREE_OPERAND (cond, 0); 3074 gcc_assert (op0 == v); 3075 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node); 3076 } 3077 else if (TREE_CODE (cond) == SSA_NAME) 3078 { 3079 /* Given V, build the assignment N = true. */ 3080 gcc_assert (v == cond); 3081 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node); 3082 } 3083 else 3084 gcc_unreachable (); 3085 3086 SSA_NAME_DEF_STMT (n) = assertion; 3087 3088 /* The new ASSERT_EXPR, creates a new SSA name that replaces the 3089 operand of the ASSERT_EXPR. Register the new name and the old one 3090 in the replacement table so that we can fix the SSA web after 3091 adding all the ASSERT_EXPRs. */ 3092 register_new_name_mapping (n, v); 3093 3094 return assertion; 3095} 3096 3097 3098/* Return false if EXPR is a predicate expression involving floating 3099 point values. */ 3100 3101static inline bool 3102fp_predicate (tree expr) 3103{ 3104 return (COMPARISON_CLASS_P (expr) 3105 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))); 3106} 3107 3108 3109/* If the range of values taken by OP can be inferred after STMT executes, 3110 return the comparison code (COMP_CODE_P) and value (VAL_P) that 3111 describes the inferred range. Return true if a range could be 3112 inferred. */ 3113 3114static bool 3115infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p) 3116{ 3117 *val_p = NULL_TREE; 3118 *comp_code_p = ERROR_MARK; 3119 3120 /* Do not attempt to infer anything in names that flow through 3121 abnormal edges. */ 3122 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) 3123 return false; 3124 3125 /* Similarly, don't infer anything from statements that may throw 3126 exceptions. */ 3127 if (tree_could_throw_p (stmt)) 3128 return false; 3129 3130 /* If STMT is the last statement of a basic block with no 3131 successors, there is no point inferring anything about any of its 3132 operands. We would not be able to find a proper insertion point 3133 for the assertion, anyway. */ 3134 if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0) 3135 return false; 3136 3137 /* We can only assume that a pointer dereference will yield 3138 non-NULL if -fdelete-null-pointer-checks is enabled. */ 3139 if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op))) 3140 { 3141 bool is_store; 3142 unsigned num_uses, num_derefs; 3143 3144 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); 3145 if (num_derefs > 0) 3146 { 3147 *val_p = build_int_cst (TREE_TYPE (op), 0); 3148 *comp_code_p = NE_EXPR; 3149 return true; 3150 } 3151 } 3152 3153 return false; 3154} 3155 3156 3157void dump_asserts_for (FILE *, tree); 3158void debug_asserts_for (tree); 3159void dump_all_asserts (FILE *); 3160void debug_all_asserts (void); 3161 3162/* Dump all the registered assertions for NAME to FILE. */ 3163 3164void 3165dump_asserts_for (FILE *file, tree name) 3166{ 3167 assert_locus_t loc; 3168 3169 fprintf (file, "Assertions to be inserted for "); 3170 print_generic_expr (file, name, 0); 3171 fprintf (file, "\n"); 3172 3173 loc = asserts_for[SSA_NAME_VERSION (name)]; 3174 while (loc) 3175 { 3176 fprintf (file, "\t"); 3177 print_generic_expr (file, bsi_stmt (loc->si), 0); 3178 fprintf (file, "\n\tBB #%d", loc->bb->index); 3179 if (loc->e) 3180 { 3181 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index, 3182 loc->e->dest->index); 3183 dump_edge_info (file, loc->e, 0); 3184 } 3185 fprintf (file, "\n\tPREDICATE: "); 3186 print_generic_expr (file, name, 0); 3187 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]); 3188 print_generic_expr (file, loc->val, 0); 3189 fprintf (file, "\n\n"); 3190 loc = loc->next; 3191 } 3192 3193 fprintf (file, "\n"); 3194} 3195 3196 3197/* Dump all the registered assertions for NAME to stderr. */ 3198 3199void 3200debug_asserts_for (tree name) 3201{ 3202 dump_asserts_for (stderr, name); 3203} 3204 3205 3206/* Dump all the registered assertions for all the names to FILE. */ 3207 3208void 3209dump_all_asserts (FILE *file) 3210{ 3211 unsigned i; 3212 bitmap_iterator bi; 3213 3214 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n"); 3215 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 3216 dump_asserts_for (file, ssa_name (i)); 3217 fprintf (file, "\n"); 3218} 3219 3220 3221/* Dump all the registered assertions for all the names to stderr. */ 3222 3223void 3224debug_all_asserts (void) 3225{ 3226 dump_all_asserts (stderr); 3227} 3228 3229 3230/* If NAME doesn't have an ASSERT_EXPR registered for asserting 3231 'NAME COMP_CODE VAL' at a location that dominates block BB or 3232 E->DEST, then register this location as a possible insertion point 3233 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>. 3234 3235 BB, E and SI provide the exact insertion point for the new 3236 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted 3237 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on 3238 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E 3239 must not be NULL. */ 3240 3241static void 3242register_new_assert_for (tree name, 3243 enum tree_code comp_code, 3244 tree val, 3245 basic_block bb, 3246 edge e, 3247 block_stmt_iterator si) 3248{ 3249 assert_locus_t n, loc, last_loc; 3250 bool found; 3251 basic_block dest_bb; 3252 3253#if defined ENABLE_CHECKING 3254 gcc_assert (bb == NULL || e == NULL); 3255 3256 if (e == NULL) 3257 gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR 3258 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR); 3259#endif 3260 3261 /* The new assertion A will be inserted at BB or E. We need to 3262 determine if the new location is dominated by a previously 3263 registered location for A. If we are doing an edge insertion, 3264 assume that A will be inserted at E->DEST. Note that this is not 3265 necessarily true. 3266 3267 If E is a critical edge, it will be split. But even if E is 3268 split, the new block will dominate the same set of blocks that 3269 E->DEST dominates. 3270 3271 The reverse, however, is not true, blocks dominated by E->DEST 3272 will not be dominated by the new block created to split E. So, 3273 if the insertion location is on a critical edge, we will not use 3274 the new location to move another assertion previously registered 3275 at a block dominated by E->DEST. */ 3276 dest_bb = (bb) ? bb : e->dest; 3277 3278 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and 3279 VAL at a block dominating DEST_BB, then we don't need to insert a new 3280 one. Similarly, if the same assertion already exists at a block 3281 dominated by DEST_BB and the new location is not on a critical 3282 edge, then update the existing location for the assertion (i.e., 3283 move the assertion up in the dominance tree). 3284 3285 Note, this is implemented as a simple linked list because there 3286 should not be more than a handful of assertions registered per 3287 name. If this becomes a performance problem, a table hashed by 3288 COMP_CODE and VAL could be implemented. */ 3289 loc = asserts_for[SSA_NAME_VERSION (name)]; 3290 last_loc = loc; 3291 found = false; 3292 while (loc) 3293 { 3294 if (loc->comp_code == comp_code 3295 && (loc->val == val 3296 || operand_equal_p (loc->val, val, 0))) 3297 { 3298 /* If the assertion NAME COMP_CODE VAL has already been 3299 registered at a basic block that dominates DEST_BB, then 3300 we don't need to insert the same assertion again. Note 3301 that we don't check strict dominance here to avoid 3302 replicating the same assertion inside the same basic 3303 block more than once (e.g., when a pointer is 3304 dereferenced several times inside a block). 3305 3306 An exception to this rule are edge insertions. If the 3307 new assertion is to be inserted on edge E, then it will 3308 dominate all the other insertions that we may want to 3309 insert in DEST_BB. So, if we are doing an edge 3310 insertion, don't do this dominance check. */ 3311 if (e == NULL 3312 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb)) 3313 return; 3314 3315 /* Otherwise, if E is not a critical edge and DEST_BB 3316 dominates the existing location for the assertion, move 3317 the assertion up in the dominance tree by updating its 3318 location information. */ 3319 if ((e == NULL || !EDGE_CRITICAL_P (e)) 3320 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb)) 3321 { 3322 loc->bb = dest_bb; 3323 loc->e = e; 3324 loc->si = si; 3325 return; 3326 } 3327 } 3328 3329 /* Update the last node of the list and move to the next one. */ 3330 last_loc = loc; 3331 loc = loc->next; 3332 } 3333 3334 /* If we didn't find an assertion already registered for 3335 NAME COMP_CODE VAL, add a new one at the end of the list of 3336 assertions associated with NAME. */ 3337 n = XNEW (struct assert_locus_d); 3338 n->bb = dest_bb; 3339 n->e = e; 3340 n->si = si; 3341 n->comp_code = comp_code; 3342 n->val = val; 3343 n->next = NULL; 3344 3345 if (last_loc) 3346 last_loc->next = n; 3347 else 3348 asserts_for[SSA_NAME_VERSION (name)] = n; 3349 3350 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name)); 3351} 3352 3353 3354/* Try to register an edge assertion for SSA name NAME on edge E for 3355 the conditional jump pointed to by SI. Return true if an assertion 3356 for NAME could be registered. */ 3357 3358static bool 3359register_edge_assert_for (tree name, edge e, block_stmt_iterator si) 3360{ 3361 tree val, stmt; 3362 enum tree_code comp_code; 3363 3364 stmt = bsi_stmt (si); 3365 3366 /* Do not attempt to infer anything in names that flow through 3367 abnormal edges. */ 3368 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 3369 return false; 3370 3371 /* If NAME was not found in the sub-graph reachable from E, then 3372 there's nothing to do. */ 3373 if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))) 3374 return false; 3375 3376 /* We found a use of NAME in the sub-graph rooted at E->DEST. 3377 Register an assertion for NAME according to the value that NAME 3378 takes on edge E. */ 3379 if (TREE_CODE (stmt) == COND_EXPR) 3380 { 3381 /* If BB ends in a COND_EXPR then NAME then we should insert 3382 the original predicate on EDGE_TRUE_VALUE and the 3383 opposite predicate on EDGE_FALSE_VALUE. */ 3384 tree cond = COND_EXPR_COND (stmt); 3385 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0; 3386 3387 /* Predicates may be a single SSA name or NAME OP VAL. */ 3388 if (cond == name) 3389 { 3390 /* If the predicate is a name, it must be NAME, in which 3391 case we create the predicate NAME == true or 3392 NAME == false accordingly. */ 3393 comp_code = EQ_EXPR; 3394 val = (is_else_edge) ? boolean_false_node : boolean_true_node; 3395 } 3396 else 3397 { 3398 /* Otherwise, we have a comparison of the form NAME COMP VAL 3399 or VAL COMP NAME. */ 3400 if (name == TREE_OPERAND (cond, 1)) 3401 { 3402 /* If the predicate is of the form VAL COMP NAME, flip 3403 COMP around because we need to register NAME as the 3404 first operand in the predicate. */ 3405 comp_code = swap_tree_comparison (TREE_CODE (cond)); 3406 val = TREE_OPERAND (cond, 0); 3407 } 3408 else 3409 { 3410 /* The comparison is of the form NAME COMP VAL, so the 3411 comparison code remains unchanged. */ 3412 comp_code = TREE_CODE (cond); 3413 val = TREE_OPERAND (cond, 1); 3414 } 3415 3416 /* If we are inserting the assertion on the ELSE edge, we 3417 need to invert the sign comparison. */ 3418 if (is_else_edge) 3419 comp_code = invert_tree_comparison (comp_code, 0); 3420 3421 /* Do not register always-false predicates. FIXME, this 3422 works around a limitation in fold() when dealing with 3423 enumerations. Given 'enum { N1, N2 } x;', fold will not 3424 fold 'if (x > N2)' to 'if (0)'. */ 3425 if ((comp_code == GT_EXPR || comp_code == LT_EXPR) 3426 && (INTEGRAL_TYPE_P (TREE_TYPE (val)) 3427 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))) 3428 { 3429 tree min = TYPE_MIN_VALUE (TREE_TYPE (val)); 3430 tree max = TYPE_MAX_VALUE (TREE_TYPE (val)); 3431 3432 if (comp_code == GT_EXPR && compare_values (val, max) == 0) 3433 return false; 3434 3435 if (comp_code == LT_EXPR && compare_values (val, min) == 0) 3436 return false; 3437 } 3438 } 3439 } 3440 else 3441 { 3442 /* FIXME. Handle SWITCH_EXPR. */ 3443 gcc_unreachable (); 3444 } 3445 3446 register_new_assert_for (name, comp_code, val, NULL, e, si); 3447 return true; 3448} 3449 3450 3451static bool find_assert_locations (basic_block bb); 3452 3453/* Determine whether the outgoing edges of BB should receive an 3454 ASSERT_EXPR for each of the operands of BB's last statement. The 3455 last statement of BB must be a COND_EXPR or a SWITCH_EXPR. 3456 3457 If any of the sub-graphs rooted at BB have an interesting use of 3458 the predicate operands, an assert location node is added to the 3459 list of assertions for the corresponding operands. */ 3460 3461static bool 3462find_conditional_asserts (basic_block bb) 3463{ 3464 bool need_assert; 3465 block_stmt_iterator last_si; 3466 tree op, last; 3467 edge_iterator ei; 3468 edge e; 3469 ssa_op_iter iter; 3470 3471 need_assert = false; 3472 last_si = bsi_last (bb); 3473 last = bsi_stmt (last_si); 3474 3475 /* Look for uses of the operands in each of the sub-graphs 3476 rooted at BB. We need to check each of the outgoing edges 3477 separately, so that we know what kind of ASSERT_EXPR to 3478 insert. */ 3479 FOR_EACH_EDGE (e, ei, bb->succs) 3480 { 3481 if (e->dest == bb) 3482 continue; 3483 3484 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap. 3485 Otherwise, when we finish traversing each of the sub-graphs, we 3486 won't know whether the variables were found in the sub-graphs or 3487 if they had been found in a block upstream from BB. 3488 3489 This is actually a bad idea is some cases, particularly jump 3490 threading. Consider a CFG like the following: 3491 3492 0 3493 /| 3494 1 | 3495 \| 3496 2 3497 / \ 3498 3 4 3499 3500 Assume that one or more operands in the conditional at the 3501 end of block 0 are used in a conditional in block 2, but not 3502 anywhere in block 1. In this case we will not insert any 3503 assert statements in block 1, which may cause us to miss 3504 opportunities to optimize, particularly for jump threading. */ 3505 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3506 RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3507 3508 /* Traverse the strictly dominated sub-graph rooted at E->DEST 3509 to determine if any of the operands in the conditional 3510 predicate are used. */ 3511 if (e->dest != bb) 3512 need_assert |= find_assert_locations (e->dest); 3513 3514 /* Register the necessary assertions for each operand in the 3515 conditional predicate. */ 3516 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3517 need_assert |= register_edge_assert_for (op, e, last_si); 3518 } 3519 3520 /* Finally, indicate that we have found the operands in the 3521 conditional. */ 3522 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3523 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3524 3525 return need_assert; 3526} 3527 3528 3529/* Traverse all the statements in block BB looking for statements that 3530 may generate useful assertions for the SSA names in their operand. 3531 If a statement produces a useful assertion A for name N_i, then the 3532 list of assertions already generated for N_i is scanned to 3533 determine if A is actually needed. 3534 3535 If N_i already had the assertion A at a location dominating the 3536 current location, then nothing needs to be done. Otherwise, the 3537 new location for A is recorded instead. 3538 3539 1- For every statement S in BB, all the variables used by S are 3540 added to bitmap FOUND_IN_SUBGRAPH. 3541 3542 2- If statement S uses an operand N in a way that exposes a known 3543 value range for N, then if N was not already generated by an 3544 ASSERT_EXPR, create a new assert location for N. For instance, 3545 if N is a pointer and the statement dereferences it, we can 3546 assume that N is not NULL. 3547 3548 3- COND_EXPRs are a special case of #2. We can derive range 3549 information from the predicate but need to insert different 3550 ASSERT_EXPRs for each of the sub-graphs rooted at the 3551 conditional block. If the last statement of BB is a conditional 3552 expression of the form 'X op Y', then 3553 3554 a) Remove X and Y from the set FOUND_IN_SUBGRAPH. 3555 3556 b) If the conditional is the only entry point to the sub-graph 3557 corresponding to the THEN_CLAUSE, recurse into it. On 3558 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then 3559 an ASSERT_EXPR is added for the corresponding variable. 3560 3561 c) Repeat step (b) on the ELSE_CLAUSE. 3562 3563 d) Mark X and Y in FOUND_IN_SUBGRAPH. 3564 3565 For instance, 3566 3567 if (a == 9) 3568 b = a; 3569 else 3570 b = c + 1; 3571 3572 In this case, an assertion on the THEN clause is useful to 3573 determine that 'a' is always 9 on that edge. However, an assertion 3574 on the ELSE clause would be unnecessary. 3575 3576 4- If BB does not end in a conditional expression, then we recurse 3577 into BB's dominator children. 3578 3579 At the end of the recursive traversal, every SSA name will have a 3580 list of locations where ASSERT_EXPRs should be added. When a new 3581 location for name N is found, it is registered by calling 3582 register_new_assert_for. That function keeps track of all the 3583 registered assertions to prevent adding unnecessary assertions. 3584 For instance, if a pointer P_4 is dereferenced more than once in a 3585 dominator tree, only the location dominating all the dereference of 3586 P_4 will receive an ASSERT_EXPR. 3587 3588 If this function returns true, then it means that there are names 3589 for which we need to generate ASSERT_EXPRs. Those assertions are 3590 inserted by process_assert_insertions. 3591 3592 TODO. Handle SWITCH_EXPR. */ 3593 3594static bool 3595find_assert_locations (basic_block bb) 3596{ 3597 block_stmt_iterator si; 3598 tree last, phi; 3599 bool need_assert; 3600 basic_block son; 3601 3602 if (TEST_BIT (blocks_visited, bb->index)) 3603 return false; 3604 3605 SET_BIT (blocks_visited, bb->index); 3606 3607 need_assert = false; 3608 3609 /* Traverse all PHI nodes in BB marking used operands. */ 3610 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 3611 { 3612 use_operand_p arg_p; 3613 ssa_op_iter i; 3614 3615 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) 3616 { 3617 tree arg = USE_FROM_PTR (arg_p); 3618 if (TREE_CODE (arg) == SSA_NAME) 3619 { 3620 gcc_assert (is_gimple_reg (PHI_RESULT (phi))); 3621 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg)); 3622 } 3623 } 3624 } 3625 3626 /* Traverse all the statements in BB marking used names and looking 3627 for statements that may infer assertions for their used operands. */ 3628 last = NULL_TREE; 3629 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 3630 { 3631 tree stmt, op; 3632 ssa_op_iter i; 3633 3634 stmt = bsi_stmt (si); 3635 3636 /* See if we can derive an assertion for any of STMT's operands. */ 3637 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 3638 { 3639 tree value; 3640 enum tree_code comp_code; 3641 3642 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside 3643 the sub-graph of a conditional block, when we return from 3644 this recursive walk, our parent will use the 3645 FOUND_IN_SUBGRAPH bitset to determine if one of the 3646 operands it was looking for was present in the sub-graph. */ 3647 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3648 3649 /* If OP is used in such a way that we can infer a value 3650 range for it, and we don't find a previous assertion for 3651 it, create a new assertion location node for OP. */ 3652 if (infer_value_range (stmt, op, &comp_code, &value)) 3653 { 3654 /* If we are able to infer a nonzero value range for OP, 3655 then walk backwards through the use-def chain to see if OP 3656 was set via a typecast. 3657 3658 If so, then we can also infer a nonzero value range 3659 for the operand of the NOP_EXPR. */ 3660 if (comp_code == NE_EXPR && integer_zerop (value)) 3661 { 3662 tree t = op; 3663 tree def_stmt = SSA_NAME_DEF_STMT (t); 3664 3665 while (TREE_CODE (def_stmt) == MODIFY_EXPR 3666 && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR 3667 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME 3668 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)))) 3669 { 3670 t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0); 3671 def_stmt = SSA_NAME_DEF_STMT (t); 3672 3673 /* Note we want to register the assert for the 3674 operand of the NOP_EXPR after SI, not after the 3675 conversion. */ 3676 if (! has_single_use (t)) 3677 { 3678 register_new_assert_for (t, comp_code, value, 3679 bb, NULL, si); 3680 need_assert = true; 3681 } 3682 } 3683 } 3684 3685 /* If OP is used only once, namely in this STMT, don't 3686 bother creating an ASSERT_EXPR for it. Such an 3687 ASSERT_EXPR would do nothing but increase compile time. */ 3688 if (!has_single_use (op)) 3689 { 3690 register_new_assert_for (op, comp_code, value, bb, NULL, si); 3691 need_assert = true; 3692 } 3693 } 3694 } 3695 3696 /* Remember the last statement of the block. */ 3697 last = stmt; 3698 } 3699 3700 /* If BB's last statement is a conditional expression 3701 involving integer operands, recurse into each of the sub-graphs 3702 rooted at BB to determine if we need to add ASSERT_EXPRs. */ 3703 if (last 3704 && TREE_CODE (last) == COND_EXPR 3705 && !fp_predicate (COND_EXPR_COND (last)) 3706 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) 3707 need_assert |= find_conditional_asserts (bb); 3708 3709 /* Recurse into the dominator children of BB. */ 3710 for (son = first_dom_son (CDI_DOMINATORS, bb); 3711 son; 3712 son = next_dom_son (CDI_DOMINATORS, son)) 3713 need_assert |= find_assert_locations (son); 3714 3715 return need_assert; 3716} 3717 3718 3719/* Create an ASSERT_EXPR for NAME and insert it in the location 3720 indicated by LOC. Return true if we made any edge insertions. */ 3721 3722static bool 3723process_assert_insertions_for (tree name, assert_locus_t loc) 3724{ 3725 /* Build the comparison expression NAME_i COMP_CODE VAL. */ 3726 tree stmt, cond, assert_expr; 3727 edge_iterator ei; 3728 edge e; 3729 3730 cond = build2 (loc->comp_code, boolean_type_node, name, loc->val); 3731 assert_expr = build_assert_expr_for (cond, name); 3732 3733 if (loc->e) 3734 { 3735 /* We have been asked to insert the assertion on an edge. This 3736 is used only by COND_EXPR and SWITCH_EXPR assertions. */ 3737#if defined ENABLE_CHECKING 3738 gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR 3739 || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR); 3740#endif 3741 3742 bsi_insert_on_edge (loc->e, assert_expr); 3743 return true; 3744 } 3745 3746 /* Otherwise, we can insert right after LOC->SI iff the 3747 statement must not be the last statement in the block. */ 3748 stmt = bsi_stmt (loc->si); 3749 if (!stmt_ends_bb_p (stmt)) 3750 { 3751 bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT); 3752 return false; 3753 } 3754 3755 /* If STMT must be the last statement in BB, we can only insert new 3756 assertions on the non-abnormal edge out of BB. Note that since 3757 STMT is not control flow, there may only be one non-abnormal edge 3758 out of BB. */ 3759 FOR_EACH_EDGE (e, ei, loc->bb->succs) 3760 if (!(e->flags & EDGE_ABNORMAL)) 3761 { 3762 bsi_insert_on_edge (e, assert_expr); 3763 return true; 3764 } 3765 3766 gcc_unreachable (); 3767} 3768 3769 3770/* Process all the insertions registered for every name N_i registered 3771 in NEED_ASSERT_FOR. The list of assertions to be inserted are 3772 found in ASSERTS_FOR[i]. */ 3773 3774static void 3775process_assert_insertions (void) 3776{ 3777 unsigned i; 3778 bitmap_iterator bi; 3779 bool update_edges_p = false; 3780 int num_asserts = 0; 3781 3782 if (dump_file && (dump_flags & TDF_DETAILS)) 3783 dump_all_asserts (dump_file); 3784 3785 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 3786 { 3787 assert_locus_t loc = asserts_for[i]; 3788 gcc_assert (loc); 3789 3790 while (loc) 3791 { 3792 assert_locus_t next = loc->next; 3793 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc); 3794 free (loc); 3795 loc = next; 3796 num_asserts++; 3797 } 3798 } 3799 3800 if (update_edges_p) 3801 bsi_commit_edge_inserts (); 3802 3803 if (dump_file && (dump_flags & TDF_STATS)) 3804 fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n", 3805 num_asserts); 3806} 3807 3808 3809/* Traverse the flowgraph looking for conditional jumps to insert range 3810 expressions. These range expressions are meant to provide information 3811 to optimizations that need to reason in terms of value ranges. They 3812 will not be expanded into RTL. For instance, given: 3813 3814 x = ... 3815 y = ... 3816 if (x < y) 3817 y = x - 2; 3818 else 3819 x = y + 3; 3820 3821 this pass will transform the code into: 3822 3823 x = ... 3824 y = ... 3825 if (x < y) 3826 { 3827 x = ASSERT_EXPR <x, x < y> 3828 y = x - 2 3829 } 3830 else 3831 { 3832 y = ASSERT_EXPR <y, x <= y> 3833 x = y + 3 3834 } 3835 3836 The idea is that once copy and constant propagation have run, other 3837 optimizations will be able to determine what ranges of values can 'x' 3838 take in different paths of the code, simply by checking the reaching 3839 definition of 'x'. */ 3840 3841static void 3842insert_range_assertions (void) 3843{ 3844 edge e; 3845 edge_iterator ei; 3846 bool update_ssa_p; 3847 3848 found_in_subgraph = sbitmap_alloc (num_ssa_names); 3849 sbitmap_zero (found_in_subgraph); 3850 3851 blocks_visited = sbitmap_alloc (last_basic_block); 3852 sbitmap_zero (blocks_visited); 3853 3854 need_assert_for = BITMAP_ALLOC (NULL); 3855 asserts_for = XNEWVEC (assert_locus_t, num_ssa_names); 3856 memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t)); 3857 3858 calculate_dominance_info (CDI_DOMINATORS); 3859 3860 update_ssa_p = false; 3861 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 3862 if (find_assert_locations (e->dest)) 3863 update_ssa_p = true; 3864 3865 if (update_ssa_p) 3866 { 3867 process_assert_insertions (); 3868 update_ssa (TODO_update_ssa_no_phi); 3869 } 3870 3871 if (dump_file && (dump_flags & TDF_DETAILS)) 3872 { 3873 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n"); 3874 dump_function_to_file (current_function_decl, dump_file, dump_flags); 3875 } 3876 3877 sbitmap_free (found_in_subgraph); 3878 free (asserts_for); 3879 BITMAP_FREE (need_assert_for); 3880} 3881 3882 3883/* Convert range assertion expressions into the implied copies and 3884 copy propagate away the copies. Doing the trivial copy propagation 3885 here avoids the need to run the full copy propagation pass after 3886 VRP. 3887 3888 FIXME, this will eventually lead to copy propagation removing the 3889 names that had useful range information attached to them. For 3890 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>, 3891 then N_i will have the range [3, +INF]. 3892 3893 However, by converting the assertion into the implied copy 3894 operation N_i = N_j, we will then copy-propagate N_j into the uses 3895 of N_i and lose the range information. We may want to hold on to 3896 ASSERT_EXPRs a little while longer as the ranges could be used in 3897 things like jump threading. 3898 3899 The problem with keeping ASSERT_EXPRs around is that passes after 3900 VRP need to handle them appropriately. 3901 3902 Another approach would be to make the range information a first 3903 class property of the SSA_NAME so that it can be queried from 3904 any pass. This is made somewhat more complex by the need for 3905 multiple ranges to be associated with one SSA_NAME. */ 3906 3907static void 3908remove_range_assertions (void) 3909{ 3910 basic_block bb; 3911 block_stmt_iterator si; 3912 3913 /* Note that the BSI iterator bump happens at the bottom of the 3914 loop and no bump is necessary if we're removing the statement 3915 referenced by the current BSI. */ 3916 FOR_EACH_BB (bb) 3917 for (si = bsi_start (bb); !bsi_end_p (si);) 3918 { 3919 tree stmt = bsi_stmt (si); 3920 tree use_stmt; 3921 3922 if (TREE_CODE (stmt) == MODIFY_EXPR 3923 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) 3924 { 3925 tree rhs = TREE_OPERAND (stmt, 1), var; 3926 tree cond = fold (ASSERT_EXPR_COND (rhs)); 3927 use_operand_p use_p; 3928 imm_use_iterator iter; 3929 3930 gcc_assert (cond != boolean_false_node); 3931 3932 /* Propagate the RHS into every use of the LHS. */ 3933 var = ASSERT_EXPR_VAR (rhs); 3934 FOR_EACH_IMM_USE_STMT (use_stmt, iter, TREE_OPERAND (stmt, 0)) 3935 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 3936 { 3937 SET_USE (use_p, var); 3938 gcc_assert (TREE_CODE (var) == SSA_NAME); 3939 } 3940 3941 /* And finally, remove the copy, it is not needed. */ 3942 bsi_remove (&si, true); 3943 } 3944 else 3945 bsi_next (&si); 3946 } 3947 3948 sbitmap_free (blocks_visited); 3949} 3950 3951 3952/* Return true if STMT is interesting for VRP. */ 3953 3954static bool 3955stmt_interesting_for_vrp (tree stmt) 3956{ 3957 if (TREE_CODE (stmt) == PHI_NODE 3958 && is_gimple_reg (PHI_RESULT (stmt)) 3959 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))) 3960 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))))) 3961 return true; 3962 else if (TREE_CODE (stmt) == MODIFY_EXPR) 3963 { 3964 tree lhs = TREE_OPERAND (stmt, 0); 3965 tree rhs = TREE_OPERAND (stmt, 1); 3966 3967 /* In general, assignments with virtual operands are not useful 3968 for deriving ranges, with the obvious exception of calls to 3969 builtin functions. */ 3970 if (TREE_CODE (lhs) == SSA_NAME 3971 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 3972 || POINTER_TYPE_P (TREE_TYPE (lhs))) 3973 && ((TREE_CODE (rhs) == CALL_EXPR 3974 && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 3975 && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 3976 && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 3977 || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))) 3978 return true; 3979 } 3980 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 3981 return true; 3982 3983 return false; 3984} 3985 3986 3987/* Initialize local data structures for VRP. */ 3988 3989static void 3990vrp_initialize (void) 3991{ 3992 basic_block bb; 3993 3994 vr_value = XNEWVEC (value_range_t *, num_ssa_names); 3995 memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *)); 3996 3997 FOR_EACH_BB (bb) 3998 { 3999 block_stmt_iterator si; 4000 tree phi; 4001 4002 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 4003 { 4004 if (!stmt_interesting_for_vrp (phi)) 4005 { 4006 tree lhs = PHI_RESULT (phi); 4007 set_value_range_to_varying (get_value_range (lhs)); 4008 DONT_SIMULATE_AGAIN (phi) = true; 4009 } 4010 else 4011 DONT_SIMULATE_AGAIN (phi) = false; 4012 } 4013 4014 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 4015 { 4016 tree stmt = bsi_stmt (si); 4017 4018 if (!stmt_interesting_for_vrp (stmt)) 4019 { 4020 ssa_op_iter i; 4021 tree def; 4022 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF) 4023 set_value_range_to_varying (get_value_range (def)); 4024 DONT_SIMULATE_AGAIN (stmt) = true; 4025 } 4026 else 4027 { 4028 DONT_SIMULATE_AGAIN (stmt) = false; 4029 } 4030 } 4031 } 4032} 4033 4034 4035/* Visit assignment STMT. If it produces an interesting range, record 4036 the SSA name in *OUTPUT_P. */ 4037 4038static enum ssa_prop_result 4039vrp_visit_assignment (tree stmt, tree *output_p) 4040{ 4041 tree lhs, rhs, def; 4042 ssa_op_iter iter; 4043 4044 lhs = TREE_OPERAND (stmt, 0); 4045 rhs = TREE_OPERAND (stmt, 1); 4046 4047 /* We only keep track of ranges in integral and pointer types. */ 4048 if (TREE_CODE (lhs) == SSA_NAME 4049 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 4050 /* It is valid to have NULL MIN/MAX values on a type. See 4051 build_range_type. */ 4052 && TYPE_MIN_VALUE (TREE_TYPE (lhs)) 4053 && TYPE_MAX_VALUE (TREE_TYPE (lhs))) 4054 || POINTER_TYPE_P (TREE_TYPE (lhs)))) 4055 { 4056 struct loop *l; 4057 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 4058 4059 extract_range_from_expr (&new_vr, rhs); 4060 4061 /* If STMT is inside a loop, we may be able to know something 4062 else about the range of LHS by examining scalar evolution 4063 information. */ 4064 if (current_loops && (l = loop_containing_stmt (stmt))) 4065 adjust_range_with_scev (&new_vr, l, stmt, lhs); 4066 4067 if (update_value_range (lhs, &new_vr)) 4068 { 4069 *output_p = lhs; 4070 4071 if (dump_file && (dump_flags & TDF_DETAILS)) 4072 { 4073 fprintf (dump_file, "Found new range for "); 4074 print_generic_expr (dump_file, lhs, 0); 4075 fprintf (dump_file, ": "); 4076 dump_value_range (dump_file, &new_vr); 4077 fprintf (dump_file, "\n\n"); 4078 } 4079 4080 if (new_vr.type == VR_VARYING) 4081 return SSA_PROP_VARYING; 4082 4083 return SSA_PROP_INTERESTING; 4084 } 4085 4086 return SSA_PROP_NOT_INTERESTING; 4087 } 4088 4089 /* Every other statement produces no useful ranges. */ 4090 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 4091 set_value_range_to_varying (get_value_range (def)); 4092 4093 return SSA_PROP_VARYING; 4094} 4095 4096 4097/* Compare all the value ranges for names equivalent to VAR with VAL 4098 using comparison code COMP. Return the same value returned by 4099 compare_range_with_value, including the setting of 4100 *STRICT_OVERFLOW_P. */ 4101 4102static tree 4103compare_name_with_value (enum tree_code comp, tree var, tree val, 4104 bool *strict_overflow_p) 4105{ 4106 bitmap_iterator bi; 4107 unsigned i; 4108 bitmap e; 4109 tree retval, t; 4110 int used_strict_overflow; 4111 4112 t = retval = NULL_TREE; 4113 4114 /* Get the set of equivalences for VAR. */ 4115 e = get_value_range (var)->equiv; 4116 4117 /* Add VAR to its own set of equivalences so that VAR's value range 4118 is processed by this loop (otherwise, we would have to replicate 4119 the body of the loop just to check VAR's value range). */ 4120 bitmap_set_bit (e, SSA_NAME_VERSION (var)); 4121 4122 /* Start at -1. Set it to 0 if we do a comparison without relying 4123 on overflow, or 1 if all comparisons rely on overflow. */ 4124 used_strict_overflow = -1; 4125 4126 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) 4127 { 4128 bool sop; 4129 4130 value_range_t equiv_vr = *(vr_value[i]); 4131 4132 /* If name N_i does not have a valid range, use N_i as its own 4133 range. This allows us to compare against names that may 4134 have N_i in their ranges. */ 4135 if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED) 4136 { 4137 equiv_vr.type = VR_RANGE; 4138 equiv_vr.min = ssa_name (i); 4139 equiv_vr.max = ssa_name (i); 4140 } 4141 4142 sop = false; 4143 t = compare_range_with_value (comp, &equiv_vr, val, &sop); 4144 if (t) 4145 { 4146 /* If we get different answers from different members 4147 of the equivalence set this check must be in a dead 4148 code region. Folding it to a trap representation 4149 would be correct here. For now just return don't-know. */ 4150 if (retval != NULL 4151 && t != retval) 4152 { 4153 retval = NULL_TREE; 4154 break; 4155 } 4156 retval = t; 4157 4158 if (!sop) 4159 used_strict_overflow = 0; 4160 else if (used_strict_overflow < 0) 4161 used_strict_overflow = 1; 4162 } 4163 } 4164 4165 /* Remove VAR from its own equivalence set. */ 4166 bitmap_clear_bit (e, SSA_NAME_VERSION (var)); 4167 4168 if (retval) 4169 { 4170 if (used_strict_overflow > 0) 4171 *strict_overflow_p = true; 4172 return retval; 4173 } 4174 4175 /* We couldn't find a non-NULL value for the predicate. */ 4176 return NULL_TREE; 4177} 4178 4179 4180/* Given a comparison code COMP and names N1 and N2, compare all the 4181 ranges equivalent to N1 against all the ranges equivalent to N2 4182 to determine the value of N1 COMP N2. Return the same value 4183 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate 4184 whether we relied on an overflow infinity in the comparison. */ 4185 4186 4187static tree 4188compare_names (enum tree_code comp, tree n1, tree n2, 4189 bool *strict_overflow_p) 4190{ 4191 tree t, retval; 4192 bitmap e1, e2; 4193 bitmap_iterator bi1, bi2; 4194 unsigned i1, i2; 4195 int used_strict_overflow; 4196 4197 /* Compare the ranges of every name equivalent to N1 against the 4198 ranges of every name equivalent to N2. */ 4199 e1 = get_value_range (n1)->equiv; 4200 e2 = get_value_range (n2)->equiv; 4201 4202 /* Add N1 and N2 to their own set of equivalences to avoid 4203 duplicating the body of the loop just to check N1 and N2 4204 ranges. */ 4205 bitmap_set_bit (e1, SSA_NAME_VERSION (n1)); 4206 bitmap_set_bit (e2, SSA_NAME_VERSION (n2)); 4207 4208 /* If the equivalence sets have a common intersection, then the two 4209 names can be compared without checking their ranges. */ 4210 if (bitmap_intersect_p (e1, e2)) 4211 { 4212 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4213 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4214 4215 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR) 4216 ? boolean_true_node 4217 : boolean_false_node; 4218 } 4219 4220 /* Start at -1. Set it to 0 if we do a comparison without relying 4221 on overflow, or 1 if all comparisons rely on overflow. */ 4222 used_strict_overflow = -1; 4223 4224 /* Otherwise, compare all the equivalent ranges. First, add N1 and 4225 N2 to their own set of equivalences to avoid duplicating the body 4226 of the loop just to check N1 and N2 ranges. */ 4227 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) 4228 { 4229 value_range_t vr1 = *(vr_value[i1]); 4230 4231 /* If the range is VARYING or UNDEFINED, use the name itself. */ 4232 if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED) 4233 { 4234 vr1.type = VR_RANGE; 4235 vr1.min = ssa_name (i1); 4236 vr1.max = ssa_name (i1); 4237 } 4238 4239 t = retval = NULL_TREE; 4240 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) 4241 { 4242 bool sop = false; 4243 4244 value_range_t vr2 = *(vr_value[i2]); 4245 4246 if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED) 4247 { 4248 vr2.type = VR_RANGE; 4249 vr2.min = ssa_name (i2); 4250 vr2.max = ssa_name (i2); 4251 } 4252 4253 t = compare_ranges (comp, &vr1, &vr2, &sop); 4254 if (t) 4255 { 4256 /* If we get different answers from different members 4257 of the equivalence set this check must be in a dead 4258 code region. Folding it to a trap representation 4259 would be correct here. For now just return don't-know. */ 4260 if (retval != NULL 4261 && t != retval) 4262 { 4263 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4264 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4265 return NULL_TREE; 4266 } 4267 retval = t; 4268 4269 if (!sop) 4270 used_strict_overflow = 0; 4271 else if (used_strict_overflow < 0) 4272 used_strict_overflow = 1; 4273 } 4274 } 4275 4276 if (retval) 4277 { 4278 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4279 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4280 if (used_strict_overflow > 0) 4281 *strict_overflow_p = true; 4282 return retval; 4283 } 4284 } 4285 4286 /* None of the equivalent ranges are useful in computing this 4287 comparison. */ 4288 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4289 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4290 return NULL_TREE; 4291} 4292 4293 4294/* Given a conditional predicate COND, try to determine if COND yields 4295 true or false based on the value ranges of its operands. Return 4296 BOOLEAN_TRUE_NODE if the conditional always evaluates to true, 4297 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and, 4298 NULL if the conditional cannot be evaluated at compile time. 4299 4300 If USE_EQUIV_P is true, the ranges of all the names equivalent with 4301 the operands in COND are used when trying to compute its value. 4302 This is only used during final substitution. During propagation, 4303 we only check the range of each variable and not its equivalents. 4304 4305 Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow 4306 infinity to produce the result. */ 4307 4308static tree 4309vrp_evaluate_conditional_warnv (tree cond, bool use_equiv_p, 4310 bool *strict_overflow_p) 4311{ 4312 gcc_assert (TREE_CODE (cond) == SSA_NAME 4313 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison); 4314 4315 if (TREE_CODE (cond) == SSA_NAME) 4316 { 4317 value_range_t *vr; 4318 tree retval; 4319 4320 if (use_equiv_p) 4321 retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node, 4322 strict_overflow_p); 4323 else 4324 { 4325 value_range_t *vr = get_value_range (cond); 4326 retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node, 4327 strict_overflow_p); 4328 } 4329 4330 /* If COND has a known boolean range, return it. */ 4331 if (retval) 4332 return retval; 4333 4334 /* Otherwise, if COND has a symbolic range of exactly one value, 4335 return it. */ 4336 vr = get_value_range (cond); 4337 if (vr->type == VR_RANGE && vr->min == vr->max) 4338 return vr->min; 4339 } 4340 else 4341 { 4342 tree op0 = TREE_OPERAND (cond, 0); 4343 tree op1 = TREE_OPERAND (cond, 1); 4344 4345 /* We only deal with integral and pointer types. */ 4346 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 4347 && !POINTER_TYPE_P (TREE_TYPE (op0))) 4348 return NULL_TREE; 4349 4350 if (use_equiv_p) 4351 { 4352 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) 4353 return compare_names (TREE_CODE (cond), op0, op1, 4354 strict_overflow_p); 4355 else if (TREE_CODE (op0) == SSA_NAME) 4356 return compare_name_with_value (TREE_CODE (cond), op0, op1, 4357 strict_overflow_p); 4358 else if (TREE_CODE (op1) == SSA_NAME) 4359 return (compare_name_with_value 4360 (swap_tree_comparison (TREE_CODE (cond)), op1, op0, 4361 strict_overflow_p)); 4362 } 4363 else 4364 { 4365 value_range_t *vr0, *vr1; 4366 4367 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL; 4368 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; 4369 4370 if (vr0 && vr1) 4371 return compare_ranges (TREE_CODE (cond), vr0, vr1, 4372 strict_overflow_p); 4373 else if (vr0 && vr1 == NULL) 4374 return compare_range_with_value (TREE_CODE (cond), vr0, op1, 4375 strict_overflow_p); 4376 else if (vr0 == NULL && vr1) 4377 return (compare_range_with_value 4378 (swap_tree_comparison (TREE_CODE (cond)), vr1, op0, 4379 strict_overflow_p)); 4380 } 4381 } 4382 4383 /* Anything else cannot be computed statically. */ 4384 return NULL_TREE; 4385} 4386 4387/* Given COND within STMT, try to simplify it based on value range 4388 information. Return NULL if the conditional can not be evaluated. 4389 The ranges of all the names equivalent with the operands in COND 4390 will be used when trying to compute the value. If the result is 4391 based on undefined signed overflow, issue a warning if 4392 appropriate. */ 4393 4394tree 4395vrp_evaluate_conditional (tree cond, tree stmt) 4396{ 4397 bool sop; 4398 tree ret; 4399 4400 sop = false; 4401 ret = vrp_evaluate_conditional_warnv (cond, true, &sop); 4402 4403 if (ret && sop) 4404 { 4405 enum warn_strict_overflow_code wc; 4406 const char* warnmsg; 4407 4408 if (is_gimple_min_invariant (ret)) 4409 { 4410 wc = WARN_STRICT_OVERFLOW_CONDITIONAL; 4411 warnmsg = G_("assuming signed overflow does not occur when " 4412 "simplifying conditional to constant"); 4413 } 4414 else 4415 { 4416 wc = WARN_STRICT_OVERFLOW_COMPARISON; 4417 warnmsg = G_("assuming signed overflow does not occur when " 4418 "simplifying conditional"); 4419 } 4420 4421 if (issue_strict_overflow_warning (wc)) 4422 { 4423 location_t locus; 4424 4425 if (!EXPR_HAS_LOCATION (stmt)) 4426 locus = input_location; 4427 else 4428 locus = EXPR_LOCATION (stmt); 4429 warning (OPT_Wstrict_overflow, "%H%s", &locus, warnmsg); 4430 } 4431 } 4432 4433 return ret; 4434} 4435 4436 4437/* Visit conditional statement STMT. If we can determine which edge 4438 will be taken out of STMT's basic block, record it in 4439 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return 4440 SSA_PROP_VARYING. */ 4441 4442static enum ssa_prop_result 4443vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) 4444{ 4445 tree cond, val; 4446 bool sop; 4447 4448 *taken_edge_p = NULL; 4449 4450 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to 4451 add ASSERT_EXPRs for them. */ 4452 if (TREE_CODE (stmt) == SWITCH_EXPR) 4453 return SSA_PROP_VARYING; 4454 4455 cond = COND_EXPR_COND (stmt); 4456 4457 if (dump_file && (dump_flags & TDF_DETAILS)) 4458 { 4459 tree use; 4460 ssa_op_iter i; 4461 4462 fprintf (dump_file, "\nVisiting conditional with predicate: "); 4463 print_generic_expr (dump_file, cond, 0); 4464 fprintf (dump_file, "\nWith known ranges\n"); 4465 4466 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) 4467 { 4468 fprintf (dump_file, "\t"); 4469 print_generic_expr (dump_file, use, 0); 4470 fprintf (dump_file, ": "); 4471 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]); 4472 } 4473 4474 fprintf (dump_file, "\n"); 4475 } 4476 4477 /* Compute the value of the predicate COND by checking the known 4478 ranges of each of its operands. 4479 4480 Note that we cannot evaluate all the equivalent ranges here 4481 because those ranges may not yet be final and with the current 4482 propagation strategy, we cannot determine when the value ranges 4483 of the names in the equivalence set have changed. 4484 4485 For instance, given the following code fragment 4486 4487 i_5 = PHI <8, i_13> 4488 ... 4489 i_14 = ASSERT_EXPR <i_5, i_5 != 0> 4490 if (i_14 == 1) 4491 ... 4492 4493 Assume that on the first visit to i_14, i_5 has the temporary 4494 range [8, 8] because the second argument to the PHI function is 4495 not yet executable. We derive the range ~[0, 0] for i_14 and the 4496 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for 4497 the first time, since i_14 is equivalent to the range [8, 8], we 4498 determine that the predicate is always false. 4499 4500 On the next round of propagation, i_13 is determined to be 4501 VARYING, which causes i_5 to drop down to VARYING. So, another 4502 visit to i_14 is scheduled. In this second visit, we compute the 4503 exact same range and equivalence set for i_14, namely ~[0, 0] and 4504 { i_5 }. But we did not have the previous range for i_5 4505 registered, so vrp_visit_assignment thinks that the range for 4506 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)' 4507 is not visited again, which stops propagation from visiting 4508 statements in the THEN clause of that if(). 4509 4510 To properly fix this we would need to keep the previous range 4511 value for the names in the equivalence set. This way we would've 4512 discovered that from one visit to the other i_5 changed from 4513 range [8, 8] to VR_VARYING. 4514 4515 However, fixing this apparent limitation may not be worth the 4516 additional checking. Testing on several code bases (GCC, DLV, 4517 MICO, TRAMP3D and SPEC2000) showed that doing this results in 4518 4 more predicates folded in SPEC. */ 4519 sop = false; 4520 val = vrp_evaluate_conditional_warnv (cond, false, &sop); 4521 if (val) 4522 { 4523 if (!sop) 4524 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val); 4525 else 4526 { 4527 if (dump_file && (dump_flags & TDF_DETAILS)) 4528 fprintf (dump_file, 4529 "\nIgnoring predicate evaluation because " 4530 "it assumes that signed overflow is undefined"); 4531 val = NULL_TREE; 4532 } 4533 } 4534 4535 if (dump_file && (dump_flags & TDF_DETAILS)) 4536 { 4537 fprintf (dump_file, "\nPredicate evaluates to: "); 4538 if (val == NULL_TREE) 4539 fprintf (dump_file, "DON'T KNOW\n"); 4540 else 4541 print_generic_stmt (dump_file, val, 0); 4542 } 4543 4544 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 4545} 4546 4547 4548/* Evaluate statement STMT. If the statement produces a useful range, 4549 return SSA_PROP_INTERESTING and record the SSA name with the 4550 interesting range into *OUTPUT_P. 4551 4552 If STMT is a conditional branch and we can determine its truth 4553 value, the taken edge is recorded in *TAKEN_EDGE_P. 4554 4555 If STMT produces a varying value, return SSA_PROP_VARYING. */ 4556 4557static enum ssa_prop_result 4558vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p) 4559{ 4560 tree def; 4561 ssa_op_iter iter; 4562 stmt_ann_t ann; 4563 4564 if (dump_file && (dump_flags & TDF_DETAILS)) 4565 { 4566 fprintf (dump_file, "\nVisiting statement:\n"); 4567 print_generic_stmt (dump_file, stmt, dump_flags); 4568 fprintf (dump_file, "\n"); 4569 } 4570 4571 ann = stmt_ann (stmt); 4572 if (TREE_CODE (stmt) == MODIFY_EXPR) 4573 { 4574 tree rhs = TREE_OPERAND (stmt, 1); 4575 4576 /* In general, assignments with virtual operands are not useful 4577 for deriving ranges, with the obvious exception of calls to 4578 builtin functions. */ 4579 if ((TREE_CODE (rhs) == CALL_EXPR 4580 && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 4581 && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 4582 && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 4583 || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 4584 return vrp_visit_assignment (stmt, output_p); 4585 } 4586 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 4587 return vrp_visit_cond_stmt (stmt, taken_edge_p); 4588 4589 /* All other statements produce nothing of interest for VRP, so mark 4590 their outputs varying and prevent further simulation. */ 4591 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 4592 set_value_range_to_varying (get_value_range (def)); 4593 4594 return SSA_PROP_VARYING; 4595} 4596 4597 4598/* Meet operation for value ranges. Given two value ranges VR0 and 4599 VR1, store in VR0 the result of meeting VR0 and VR1. 4600 4601 The meeting rules are as follows: 4602 4603 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING. 4604 4605 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the 4606 union of VR0 and VR1. */ 4607 4608static void 4609vrp_meet (value_range_t *vr0, value_range_t *vr1) 4610{ 4611 if (vr0->type == VR_UNDEFINED) 4612 { 4613 copy_value_range (vr0, vr1); 4614 return; 4615 } 4616 4617 if (vr1->type == VR_UNDEFINED) 4618 { 4619 /* Nothing to do. VR0 already has the resulting range. */ 4620 return; 4621 } 4622 4623 if (vr0->type == VR_VARYING) 4624 { 4625 /* Nothing to do. VR0 already has the resulting range. */ 4626 return; 4627 } 4628 4629 if (vr1->type == VR_VARYING) 4630 { 4631 set_value_range_to_varying (vr0); 4632 return; 4633 } 4634 4635 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE) 4636 { 4637 /* If VR0 and VR1 have a non-empty intersection, compute the 4638 union of both ranges. */ 4639 if (value_ranges_intersect_p (vr0, vr1)) 4640 { 4641 int cmp; 4642 tree min, max; 4643 4644 /* The lower limit of the new range is the minimum of the 4645 two ranges. If they cannot be compared, the result is 4646 VARYING. */ 4647 cmp = compare_values (vr0->min, vr1->min); 4648 if (cmp == 0 || cmp == 1) 4649 min = vr1->min; 4650 else if (cmp == -1) 4651 min = vr0->min; 4652 else 4653 { 4654 set_value_range_to_varying (vr0); 4655 return; 4656 } 4657 4658 /* Similarly, the upper limit of the new range is the 4659 maximum of the two ranges. If they cannot be compared, 4660 the result is VARYING. */ 4661 cmp = compare_values (vr0->max, vr1->max); 4662 if (cmp == 0 || cmp == -1) 4663 max = vr1->max; 4664 else if (cmp == 1) 4665 max = vr0->max; 4666 else 4667 { 4668 set_value_range_to_varying (vr0); 4669 return; 4670 } 4671 4672 /* Check for useless ranges. */ 4673 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) 4674 && ((vrp_val_is_min (min) || is_overflow_infinity (min)) 4675 && (vrp_val_is_max (max) || is_overflow_infinity (max)))) 4676 { 4677 set_value_range_to_varying (vr0); 4678 return; 4679 } 4680 4681 /* The resulting set of equivalences is the intersection of 4682 the two sets. */ 4683 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4684 bitmap_and_into (vr0->equiv, vr1->equiv); 4685 else if (vr0->equiv && !vr1->equiv) 4686 bitmap_clear (vr0->equiv); 4687 4688 set_value_range (vr0, vr0->type, min, max, vr0->equiv); 4689 } 4690 else 4691 goto no_meet; 4692 } 4693 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 4694 { 4695 /* Two anti-ranges meet only if they are both identical. */ 4696 if (compare_values (vr0->min, vr1->min) == 0 4697 && compare_values (vr0->max, vr1->max) == 0 4698 && compare_values (vr0->min, vr0->max) == 0) 4699 { 4700 /* The resulting set of equivalences is the intersection of 4701 the two sets. */ 4702 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4703 bitmap_and_into (vr0->equiv, vr1->equiv); 4704 else if (vr0->equiv && !vr1->equiv) 4705 bitmap_clear (vr0->equiv); 4706 } 4707 else 4708 goto no_meet; 4709 } 4710 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 4711 { 4712 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] 4713 meet only if the ranges have an empty intersection. The 4714 result of the meet operation is the anti-range. */ 4715 if (!symbolic_range_p (vr0) 4716 && !symbolic_range_p (vr1) 4717 && !value_ranges_intersect_p (vr0, vr1)) 4718 { 4719 /* Copy most of VR1 into VR0. Don't copy VR1's equivalence 4720 set. We need to compute the intersection of the two 4721 equivalence sets. */ 4722 if (vr1->type == VR_ANTI_RANGE) 4723 set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv); 4724 4725 /* The resulting set of equivalences is the intersection of 4726 the two sets. */ 4727 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4728 bitmap_and_into (vr0->equiv, vr1->equiv); 4729 else if (vr0->equiv && !vr1->equiv) 4730 bitmap_clear (vr0->equiv); 4731 } 4732 else 4733 goto no_meet; 4734 } 4735 else 4736 gcc_unreachable (); 4737 4738 return; 4739 4740no_meet: 4741 /* The two range VR0 and VR1 do not meet. Before giving up and 4742 setting the result to VARYING, see if we can at least derive a 4743 useful anti-range. FIXME, all this nonsense about distinguishing 4744 anti-ranges from ranges is necessary because of the odd 4745 semantics of range_includes_zero_p and friends. */ 4746 if (!symbolic_range_p (vr0) 4747 && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0)) 4748 || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0))) 4749 && !symbolic_range_p (vr1) 4750 && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1)) 4751 || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1)))) 4752 { 4753 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min)); 4754 4755 /* Since this meet operation did not result from the meeting of 4756 two equivalent names, VR0 cannot have any equivalences. */ 4757 if (vr0->equiv) 4758 bitmap_clear (vr0->equiv); 4759 } 4760 else 4761 set_value_range_to_varying (vr0); 4762} 4763 4764 4765/* Visit all arguments for PHI node PHI that flow through executable 4766 edges. If a valid value range can be derived from all the incoming 4767 value ranges, set a new range for the LHS of PHI. */ 4768 4769static enum ssa_prop_result 4770vrp_visit_phi_node (tree phi) 4771{ 4772 int i; 4773 tree lhs = PHI_RESULT (phi); 4774 value_range_t *lhs_vr = get_value_range (lhs); 4775 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 4776 4777 copy_value_range (&vr_result, lhs_vr); 4778 4779 if (dump_file && (dump_flags & TDF_DETAILS)) 4780 { 4781 fprintf (dump_file, "\nVisiting PHI node: "); 4782 print_generic_expr (dump_file, phi, dump_flags); 4783 } 4784 4785 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 4786 { 4787 edge e = PHI_ARG_EDGE (phi, i); 4788 4789 if (dump_file && (dump_flags & TDF_DETAILS)) 4790 { 4791 fprintf (dump_file, 4792 "\n Argument #%d (%d -> %d %sexecutable)\n", 4793 i, e->src->index, e->dest->index, 4794 (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 4795 } 4796 4797 if (e->flags & EDGE_EXECUTABLE) 4798 { 4799 tree arg = PHI_ARG_DEF (phi, i); 4800 value_range_t vr_arg; 4801 4802 if (TREE_CODE (arg) == SSA_NAME) 4803 vr_arg = *(get_value_range (arg)); 4804 else 4805 { 4806 if (is_overflow_infinity (arg)) 4807 { 4808 arg = copy_node (arg); 4809 TREE_OVERFLOW (arg) = 0; 4810 } 4811 4812 vr_arg.type = VR_RANGE; 4813 vr_arg.min = arg; 4814 vr_arg.max = arg; 4815 vr_arg.equiv = NULL; 4816 } 4817 4818 if (dump_file && (dump_flags & TDF_DETAILS)) 4819 { 4820 fprintf (dump_file, "\t"); 4821 print_generic_expr (dump_file, arg, dump_flags); 4822 fprintf (dump_file, "\n\tValue: "); 4823 dump_value_range (dump_file, &vr_arg); 4824 fprintf (dump_file, "\n"); 4825 } 4826 4827 vrp_meet (&vr_result, &vr_arg); 4828 4829 if (vr_result.type == VR_VARYING) 4830 break; 4831 } 4832 } 4833 4834 if (vr_result.type == VR_VARYING) 4835 goto varying; 4836 4837 /* To prevent infinite iterations in the algorithm, derive ranges 4838 when the new value is slightly bigger or smaller than the 4839 previous one. */ 4840 if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE) 4841 { 4842 if (!POINTER_TYPE_P (TREE_TYPE (lhs))) 4843 { 4844 int cmp_min = compare_values (lhs_vr->min, vr_result.min); 4845 int cmp_max = compare_values (lhs_vr->max, vr_result.max); 4846 4847 /* If the new minimum is smaller or larger than the previous 4848 one, go all the way to -INF. In the first case, to avoid 4849 iterating millions of times to reach -INF, and in the 4850 other case to avoid infinite bouncing between different 4851 minimums. */ 4852 if (cmp_min > 0 || cmp_min < 0) 4853 { 4854 /* If we will end up with a (-INF, +INF) range, set it 4855 to VARYING. */ 4856 if (vrp_val_is_max (vr_result.max)) 4857 goto varying; 4858 4859 if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)) 4860 || !vrp_var_may_overflow (lhs, phi)) 4861 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); 4862 else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) 4863 vr_result.min = 4864 negative_overflow_infinity (TREE_TYPE (vr_result.min)); 4865 else 4866 goto varying; 4867 } 4868 4869 /* Similarly, if the new maximum is smaller or larger than 4870 the previous one, go all the way to +INF. */ 4871 if (cmp_max < 0 || cmp_max > 0) 4872 { 4873 /* If we will end up with a (-INF, +INF) range, set it 4874 to VARYING. */ 4875 if (vrp_val_is_min (vr_result.min)) 4876 goto varying; 4877 4878 if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)) 4879 || !vrp_var_may_overflow (lhs, phi)) 4880 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); 4881 else if (supports_overflow_infinity (TREE_TYPE (vr_result.max))) 4882 vr_result.max = 4883 positive_overflow_infinity (TREE_TYPE (vr_result.max)); 4884 else 4885 goto varying; 4886 } 4887 } 4888 } 4889 4890 /* If the new range is different than the previous value, keep 4891 iterating. */ 4892 if (update_value_range (lhs, &vr_result)) 4893 return SSA_PROP_INTERESTING; 4894 4895 /* Nothing changed, don't add outgoing edges. */ 4896 return SSA_PROP_NOT_INTERESTING; 4897 4898 /* No match found. Set the LHS to VARYING. */ 4899varying: 4900 set_value_range_to_varying (lhs_vr); 4901 return SSA_PROP_VARYING; 4902} 4903 4904/* Simplify a division or modulo operator to a right shift or 4905 bitwise and if the first operand is unsigned or is greater 4906 than zero and the second operand is an exact power of two. */ 4907 4908static void 4909simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code) 4910{ 4911 tree val = NULL; 4912 tree op = TREE_OPERAND (rhs, 0); 4913 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 4914 4915 if (TYPE_UNSIGNED (TREE_TYPE (op))) 4916 { 4917 val = integer_one_node; 4918 } 4919 else 4920 { 4921 bool sop = false; 4922 4923 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop); 4924 4925 if (val 4926 && sop 4927 && integer_onep (val) 4928 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 4929 { 4930 location_t locus; 4931 4932 if (!EXPR_HAS_LOCATION (stmt)) 4933 locus = input_location; 4934 else 4935 locus = EXPR_LOCATION (stmt); 4936 warning (OPT_Wstrict_overflow, 4937 ("%Hassuming signed overflow does not occur when " 4938 "simplifying / or %% to >> or &"), 4939 &locus); 4940 } 4941 } 4942 4943 if (val && integer_onep (val)) 4944 { 4945 tree t; 4946 tree op0 = TREE_OPERAND (rhs, 0); 4947 tree op1 = TREE_OPERAND (rhs, 1); 4948 4949 if (rhs_code == TRUNC_DIV_EXPR) 4950 { 4951 t = build_int_cst (NULL_TREE, tree_log2 (op1)); 4952 t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t); 4953 } 4954 else 4955 { 4956 t = build_int_cst (TREE_TYPE (op1), 1); 4957 t = int_const_binop (MINUS_EXPR, op1, t, 0); 4958 t = fold_convert (TREE_TYPE (op0), t); 4959 t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t); 4960 } 4961 4962 TREE_OPERAND (stmt, 1) = t; 4963 update_stmt (stmt); 4964 } 4965} 4966 4967/* If the operand to an ABS_EXPR is >= 0, then eliminate the 4968 ABS_EXPR. If the operand is <= 0, then simplify the 4969 ABS_EXPR into a NEGATE_EXPR. */ 4970 4971static void 4972simplify_abs_using_ranges (tree stmt, tree rhs) 4973{ 4974 tree val = NULL; 4975 tree op = TREE_OPERAND (rhs, 0); 4976 tree type = TREE_TYPE (op); 4977 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 4978 4979 if (TYPE_UNSIGNED (type)) 4980 { 4981 val = integer_zero_node; 4982 } 4983 else if (vr) 4984 { 4985 bool sop = false; 4986 4987 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop); 4988 if (!val) 4989 { 4990 sop = false; 4991 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, 4992 &sop); 4993 4994 if (val) 4995 { 4996 if (integer_zerop (val)) 4997 val = integer_one_node; 4998 else if (integer_onep (val)) 4999 val = integer_zero_node; 5000 } 5001 } 5002 5003 if (val 5004 && (integer_onep (val) || integer_zerop (val))) 5005 { 5006 tree t; 5007 5008 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 5009 { 5010 location_t locus; 5011 5012 if (!EXPR_HAS_LOCATION (stmt)) 5013 locus = input_location; 5014 else 5015 locus = EXPR_LOCATION (stmt); 5016 warning (OPT_Wstrict_overflow, 5017 ("%Hassuming signed overflow does not occur when " 5018 "simplifying abs (X) to X or -X"), 5019 &locus); 5020 } 5021 5022 if (integer_onep (val)) 5023 t = build1 (NEGATE_EXPR, TREE_TYPE (op), op); 5024 else 5025 t = op; 5026 5027 TREE_OPERAND (stmt, 1) = t; 5028 update_stmt (stmt); 5029 } 5030 } 5031} 5032 5033/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has 5034 a known value range VR. 5035 5036 If there is one and only one value which will satisfy the 5037 conditional, then return that value. Else return NULL. */ 5038 5039static tree 5040test_for_singularity (enum tree_code cond_code, tree op0, 5041 tree op1, value_range_t *vr) 5042{ 5043 tree min = NULL; 5044 tree max = NULL; 5045 5046 /* Extract minimum/maximum values which satisfy the 5047 the conditional as it was written. */ 5048 if (cond_code == LE_EXPR || cond_code == LT_EXPR) 5049 { 5050 /* This should not be negative infinity; there is no overflow 5051 here. */ 5052 min = TYPE_MIN_VALUE (TREE_TYPE (op0)); 5053 5054 max = op1; 5055 if (cond_code == LT_EXPR && !is_overflow_infinity (max)) 5056 { 5057 tree one = build_int_cst (TREE_TYPE (op0), 1); 5058 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); 5059 if (EXPR_P (max)) 5060 TREE_NO_WARNING (max) = 1; 5061 } 5062 } 5063 else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 5064 { 5065 /* This should not be positive infinity; there is no overflow 5066 here. */ 5067 max = TYPE_MAX_VALUE (TREE_TYPE (op0)); 5068 5069 min = op1; 5070 if (cond_code == GT_EXPR && !is_overflow_infinity (min)) 5071 { 5072 tree one = build_int_cst (TREE_TYPE (op0), 1); 5073 min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one); 5074 if (EXPR_P (min)) 5075 TREE_NO_WARNING (min) = 1; 5076 } 5077 } 5078 5079 /* Now refine the minimum and maximum values using any 5080 value range information we have for op0. */ 5081 if (min && max) 5082 { 5083 if (compare_values (vr->min, min) == -1) 5084 min = min; 5085 else 5086 min = vr->min; 5087 if (compare_values (vr->max, max) == 1) 5088 max = max; 5089 else 5090 max = vr->max; 5091 5092 /* If the new min/max values have converged to a single value, 5093 then there is only one value which can satisfy the condition, 5094 return that value. */ 5095 if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min)) 5096 return min; 5097 } 5098 return NULL; 5099} 5100 5101/* Simplify a conditional using a relational operator to an equality 5102 test if the range information indicates only one value can satisfy 5103 the original conditional. */ 5104 5105static void 5106simplify_cond_using_ranges (tree stmt) 5107{ 5108 tree cond = COND_EXPR_COND (stmt); 5109 tree op0 = TREE_OPERAND (cond, 0); 5110 tree op1 = TREE_OPERAND (cond, 1); 5111 enum tree_code cond_code = TREE_CODE (cond); 5112 5113 if (cond_code != NE_EXPR 5114 && cond_code != EQ_EXPR 5115 && TREE_CODE (op0) == SSA_NAME 5116 && INTEGRAL_TYPE_P (TREE_TYPE (op0)) 5117 && is_gimple_min_invariant (op1)) 5118 { 5119 value_range_t *vr = get_value_range (op0); 5120 5121 /* If we have range information for OP0, then we might be 5122 able to simplify this conditional. */ 5123 if (vr->type == VR_RANGE) 5124 { 5125 tree new = test_for_singularity (cond_code, op0, op1, vr); 5126 5127 if (new) 5128 { 5129 if (dump_file) 5130 { 5131 fprintf (dump_file, "Simplified relational "); 5132 print_generic_expr (dump_file, cond, 0); 5133 fprintf (dump_file, " into "); 5134 } 5135 5136 COND_EXPR_COND (stmt) 5137 = build2 (EQ_EXPR, boolean_type_node, op0, new); 5138 update_stmt (stmt); 5139 5140 if (dump_file) 5141 { 5142 print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 5143 fprintf (dump_file, "\n"); 5144 } 5145 return; 5146 5147 } 5148 5149 /* Try again after inverting the condition. We only deal 5150 with integral types here, so no need to worry about 5151 issues with inverting FP comparisons. */ 5152 cond_code = invert_tree_comparison (cond_code, false); 5153 new = test_for_singularity (cond_code, op0, op1, vr); 5154 5155 if (new) 5156 { 5157 if (dump_file) 5158 { 5159 fprintf (dump_file, "Simplified relational "); 5160 print_generic_expr (dump_file, cond, 0); 5161 fprintf (dump_file, " into "); 5162 } 5163 5164 COND_EXPR_COND (stmt) 5165 = build2 (NE_EXPR, boolean_type_node, op0, new); 5166 update_stmt (stmt); 5167 5168 if (dump_file) 5169 { 5170 print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 5171 fprintf (dump_file, "\n"); 5172 } 5173 return; 5174 5175 } 5176 } 5177 } 5178} 5179 5180/* Simplify STMT using ranges if possible. */ 5181 5182void 5183simplify_stmt_using_ranges (tree stmt) 5184{ 5185 if (TREE_CODE (stmt) == MODIFY_EXPR) 5186 { 5187 tree rhs = TREE_OPERAND (stmt, 1); 5188 enum tree_code rhs_code = TREE_CODE (rhs); 5189 5190 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR 5191 and BIT_AND_EXPR respectively if the first operand is greater 5192 than zero and the second operand is an exact power of two. */ 5193 if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR) 5194 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))) 5195 && integer_pow2p (TREE_OPERAND (rhs, 1))) 5196 simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code); 5197 5198 /* Transform ABS (X) into X or -X as appropriate. */ 5199 if (rhs_code == ABS_EXPR 5200 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME 5201 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))) 5202 simplify_abs_using_ranges (stmt, rhs); 5203 } 5204 else if (TREE_CODE (stmt) == COND_EXPR 5205 && COMPARISON_CLASS_P (COND_EXPR_COND (stmt))) 5206 { 5207 simplify_cond_using_ranges (stmt); 5208 } 5209} 5210 5211/* Stack of dest,src equivalency pairs that need to be restored after 5212 each attempt to thread a block's incoming edge to an outgoing edge. 5213 5214 A NULL entry is used to mark the end of pairs which need to be 5215 restored. */ 5216static VEC(tree,heap) *stack; 5217 5218/* A trivial wrapper so that we can present the generic jump threading 5219 code with a simple API for simplifying statements. STMT is the 5220 statement we want to simplify, WITHIN_STMT provides the location 5221 for any overflow warnings. */ 5222 5223static tree 5224simplify_stmt_for_jump_threading (tree stmt, tree within_stmt) 5225{ 5226 /* We only use VRP information to simplify conditionals. This is 5227 overly conservative, but it's unclear if doing more would be 5228 worth the compile time cost. */ 5229 if (TREE_CODE (stmt) != COND_EXPR) 5230 return NULL; 5231 5232 return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt); 5233} 5234 5235/* Blocks which have more than one predecessor and more than 5236 one successor present jump threading opportunities. ie, 5237 when the block is reached from a specific predecessor, we 5238 may be able to determine which of the outgoing edges will 5239 be traversed. When this optimization applies, we are able 5240 to avoid conditionals at runtime and we may expose secondary 5241 optimization opportunities. 5242 5243 This routine is effectively a driver for the generic jump 5244 threading code. It basically just presents the generic code 5245 with edges that may be suitable for jump threading. 5246 5247 Unlike DOM, we do not iterate VRP if jump threading was successful. 5248 While iterating may expose new opportunities for VRP, it is expected 5249 those opportunities would be very limited and the compile time cost 5250 to expose those opportunities would be significant. 5251 5252 As jump threading opportunities are discovered, they are registered 5253 for later realization. */ 5254 5255static void 5256identify_jump_threads (void) 5257{ 5258 basic_block bb; 5259 tree dummy; 5260 5261 /* Ugh. When substituting values earlier in this pass we can 5262 wipe the dominance information. So rebuild the dominator 5263 information as we need it within the jump threading code. */ 5264 calculate_dominance_info (CDI_DOMINATORS); 5265 5266 /* We do not allow VRP information to be used for jump threading 5267 across a back edge in the CFG. Otherwise it becomes too 5268 difficult to avoid eliminating loop exit tests. Of course 5269 EDGE_DFS_BACK is not accurate at this time so we have to 5270 recompute it. */ 5271 mark_dfs_back_edges (); 5272 5273 /* Allocate our unwinder stack to unwind any temporary equivalences 5274 that might be recorded. */ 5275 stack = VEC_alloc (tree, heap, 20); 5276 5277 /* To avoid lots of silly node creation, we create a single 5278 conditional and just modify it in-place when attempting to 5279 thread jumps. */ 5280 dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL); 5281 dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL); 5282 5283 /* Walk through all the blocks finding those which present a 5284 potential jump threading opportunity. We could set this up 5285 as a dominator walker and record data during the walk, but 5286 I doubt it's worth the effort for the classes of jump 5287 threading opportunities we are trying to identify at this 5288 point in compilation. */ 5289 FOR_EACH_BB (bb) 5290 { 5291 tree last, cond; 5292 5293 /* If the generic jump threading code does not find this block 5294 interesting, then there is nothing to do. */ 5295 if (! potentially_threadable_block (bb)) 5296 continue; 5297 5298 /* We only care about blocks ending in a COND_EXPR. While there 5299 may be some value in handling SWITCH_EXPR here, I doubt it's 5300 terribly important. */ 5301 last = bsi_stmt (bsi_last (bb)); 5302 if (TREE_CODE (last) != COND_EXPR) 5303 continue; 5304 5305 /* We're basically looking for any kind of conditional with 5306 integral type arguments. */ 5307 cond = COND_EXPR_COND (last); 5308 if ((TREE_CODE (cond) == SSA_NAME 5309 && INTEGRAL_TYPE_P (TREE_TYPE (cond))) 5310 || (COMPARISON_CLASS_P (cond) 5311 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 5312 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0))) 5313 && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME 5314 || is_gimple_min_invariant (TREE_OPERAND (cond, 1))) 5315 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1))))) 5316 { 5317 edge_iterator ei; 5318 edge e; 5319 5320 /* We've got a block with multiple predecessors and multiple 5321 successors which also ends in a suitable conditional. For 5322 each predecessor, see if we can thread it to a specific 5323 successor. */ 5324 FOR_EACH_EDGE (e, ei, bb->preds) 5325 { 5326 /* Do not thread across back edges or abnormal edges 5327 in the CFG. */ 5328 if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) 5329 continue; 5330 5331 thread_across_edge (dummy, e, true, 5332 &stack, 5333 simplify_stmt_for_jump_threading); 5334 } 5335 } 5336 } 5337 5338 /* We do not actually update the CFG or SSA graphs at this point as 5339 ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet 5340 handle ASSERT_EXPRs gracefully. */ 5341} 5342 5343/* We identified all the jump threading opportunities earlier, but could 5344 not transform the CFG at that time. This routine transforms the 5345 CFG and arranges for the dominator tree to be rebuilt if necessary. 5346 5347 Note the SSA graph update will occur during the normal TODO 5348 processing by the pass manager. */ 5349static void 5350finalize_jump_threads (void) 5351{ 5352 bool cfg_altered = false; 5353 cfg_altered = thread_through_all_blocks (); 5354 5355 /* If we threaded jumps, then we need to recompute the dominance 5356 information, to safely do that we must clean up the CFG first. */ 5357 if (cfg_altered) 5358 { 5359 free_dominance_info (CDI_DOMINATORS); 5360 cleanup_tree_cfg (); 5361 calculate_dominance_info (CDI_DOMINATORS); 5362 } 5363 VEC_free (tree, heap, stack); 5364} 5365 5366 5367/* Traverse all the blocks folding conditionals with known ranges. */ 5368 5369static void 5370vrp_finalize (void) 5371{ 5372 size_t i; 5373 prop_value_t *single_val_range; 5374 bool do_value_subst_p; 5375 5376 if (dump_file) 5377 { 5378 fprintf (dump_file, "\nValue ranges after VRP:\n\n"); 5379 dump_all_value_ranges (dump_file); 5380 fprintf (dump_file, "\n"); 5381 } 5382 5383 /* We may have ended with ranges that have exactly one value. Those 5384 values can be substituted as any other copy/const propagated 5385 value using substitute_and_fold. */ 5386 single_val_range = XNEWVEC (prop_value_t, num_ssa_names); 5387 memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range)); 5388 5389 do_value_subst_p = false; 5390 for (i = 0; i < num_ssa_names; i++) 5391 if (vr_value[i] 5392 && vr_value[i]->type == VR_RANGE 5393 && vr_value[i]->min == vr_value[i]->max) 5394 { 5395 single_val_range[i].value = vr_value[i]->min; 5396 do_value_subst_p = true; 5397 } 5398 5399 if (!do_value_subst_p) 5400 { 5401 /* We found no single-valued ranges, don't waste time trying to 5402 do single value substitution in substitute_and_fold. */ 5403 free (single_val_range); 5404 single_val_range = NULL; 5405 } 5406 5407 substitute_and_fold (single_val_range, true); 5408 5409 /* We must identify jump threading opportunities before we release 5410 the datastructures built by VRP. */ 5411 identify_jump_threads (); 5412 5413 /* Free allocated memory. */ 5414 for (i = 0; i < num_ssa_names; i++) 5415 if (vr_value[i]) 5416 { 5417 BITMAP_FREE (vr_value[i]->equiv); 5418 free (vr_value[i]); 5419 } 5420 5421 free (single_val_range); 5422 free (vr_value); 5423 5424 /* So that we can distinguish between VRP data being available 5425 and not available. */ 5426 vr_value = NULL; 5427} 5428 5429 5430/* Main entry point to VRP (Value Range Propagation). This pass is 5431 loosely based on J. R. C. Patterson, ``Accurate Static Branch 5432 Prediction by Value Range Propagation,'' in SIGPLAN Conference on 5433 Programming Language Design and Implementation, pp. 67-78, 1995. 5434 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html 5435 5436 This is essentially an SSA-CCP pass modified to deal with ranges 5437 instead of constants. 5438 5439 While propagating ranges, we may find that two or more SSA name 5440 have equivalent, though distinct ranges. For instance, 5441 5442 1 x_9 = p_3->a; 5443 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0> 5444 3 if (p_4 == q_2) 5445 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>; 5446 5 endif 5447 6 if (q_2) 5448 5449 In the code above, pointer p_5 has range [q_2, q_2], but from the 5450 code we can also determine that p_5 cannot be NULL and, if q_2 had 5451 a non-varying range, p_5's range should also be compatible with it. 5452 5453 These equivalences are created by two expressions: ASSERT_EXPR and 5454 copy operations. Since p_5 is an assertion on p_4, and p_4 was the 5455 result of another assertion, then we can use the fact that p_5 and 5456 p_4 are equivalent when evaluating p_5's range. 5457 5458 Together with value ranges, we also propagate these equivalences 5459 between names so that we can take advantage of information from 5460 multiple ranges when doing final replacement. Note that this 5461 equivalency relation is transitive but not symmetric. 5462 5463 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we 5464 cannot assert that q_2 is equivalent to p_5 because q_2 may be used 5465 in contexts where that assertion does not hold (e.g., in line 6). 5466 5467 TODO, the main difference between this pass and Patterson's is that 5468 we do not propagate edge probabilities. We only compute whether 5469 edges can be taken or not. That is, instead of having a spectrum 5470 of jump probabilities between 0 and 1, we only deal with 0, 1 and 5471 DON'T KNOW. In the future, it may be worthwhile to propagate 5472 probabilities to aid branch prediction. */ 5473 5474static unsigned int 5475execute_vrp (void) 5476{ 5477 insert_range_assertions (); 5478 5479 current_loops = loop_optimizer_init (LOOPS_NORMAL); 5480 if (current_loops) 5481 scev_initialize (current_loops); 5482 5483 vrp_initialize (); 5484 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); 5485 vrp_finalize (); 5486 5487 if (current_loops) 5488 { 5489 scev_finalize (); 5490 loop_optimizer_finalize (current_loops); 5491 current_loops = NULL; 5492 } 5493 5494 /* ASSERT_EXPRs must be removed before finalizing jump threads 5495 as finalizing jump threads calls the CFG cleanup code which 5496 does not properly handle ASSERT_EXPRs. */ 5497 remove_range_assertions (); 5498 5499 /* If we exposed any new variables, go ahead and put them into 5500 SSA form now, before we handle jump threading. This simplifies 5501 interactions between rewriting of _DECL nodes into SSA form 5502 and rewriting SSA_NAME nodes into SSA form after block 5503 duplication and CFG manipulation. */ 5504 update_ssa (TODO_update_ssa); 5505 5506 finalize_jump_threads (); 5507 return 0; 5508} 5509 5510static bool 5511gate_vrp (void) 5512{ 5513 return flag_tree_vrp != 0; 5514} 5515 5516struct tree_opt_pass pass_vrp = 5517{ 5518 "vrp", /* name */ 5519 gate_vrp, /* gate */ 5520 execute_vrp, /* execute */ 5521 NULL, /* sub */ 5522 NULL, /* next */ 5523 0, /* static_pass_number */ 5524 TV_TREE_VRP, /* tv_id */ 5525 PROP_ssa | PROP_alias, /* properties_required */ 5526 0, /* properties_provided */ 5527 PROP_smt_usage, /* properties_destroyed */ 5528 0, /* todo_flags_start */ 5529 TODO_cleanup_cfg 5530 | TODO_ggc_collect 5531 | TODO_verify_ssa 5532 | TODO_dump_func 5533 | TODO_update_ssa 5534 | TODO_update_smt_usage, /* todo_flags_finish */ 5535 0 /* letter */ 5536}; 5537