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