1/* Support routines for Value Range Propagation (VRP). 2 Copyright (C) 2005 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 "cfgloop.h" 36#include "tree-scalar-evolution.h" 37#include "tree-ssa-propagate.h" 38#include "tree-chrec.h" 39 40/* Set of SSA names found during the dominator traversal of a 41 sub-graph in find_assert_locations. */ 42static sbitmap found_in_subgraph; 43 44/* Loop structure of the program. Used to analyze scalar evolutions 45 inside adjust_range_with_scev. */ 46static struct loops *cfg_loops; 47 48/* Local functions. */ 49static int compare_values (tree val1, tree val2); 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 true if ARG is marked with the nonnull attribute in the 99 current function signature. */ 100 101static bool 102nonnull_arg_p (tree arg) 103{ 104 tree t, attrs, fntype; 105 unsigned HOST_WIDE_INT arg_num; 106 107 gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg))); 108 109 /* The static chain decl is always non null. */ 110 if (arg == cfun->static_chain_decl) 111 return true; 112 113 fntype = TREE_TYPE (current_function_decl); 114 attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype)); 115 116 /* If "nonnull" wasn't specified, we know nothing about the argument. */ 117 if (attrs == NULL_TREE) 118 return false; 119 120 /* If "nonnull" applies to all the arguments, then ARG is non-null. */ 121 if (TREE_VALUE (attrs) == NULL_TREE) 122 return true; 123 124 /* Get the position number for ARG in the function signature. */ 125 for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl); 126 t; 127 t = TREE_CHAIN (t), arg_num++) 128 { 129 if (t == arg) 130 break; 131 } 132 133 gcc_assert (t == arg); 134 135 /* Now see if ARG_NUM is mentioned in the nonnull list. */ 136 for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t)) 137 { 138 if (compare_tree_int (TREE_VALUE (t), arg_num) == 0) 139 return true; 140 } 141 142 return false; 143} 144 145 146/* Set value range VR to {T, MIN, MAX, EQUIV}. */ 147 148static void 149set_value_range (value_range_t *vr, enum value_range_type t, tree min, 150 tree max, bitmap equiv) 151{ 152#if defined ENABLE_CHECKING 153 /* Check the validity of the range. */ 154 if (t == VR_RANGE || t == VR_ANTI_RANGE) 155 { 156 int cmp; 157 158 gcc_assert (min && max); 159 160 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE) 161 gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min)) 162 || max != TYPE_MAX_VALUE (TREE_TYPE (max))); 163 164 cmp = compare_values (min, max); 165 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); 166 } 167 168 if (t == VR_UNDEFINED || t == VR_VARYING) 169 gcc_assert (min == NULL_TREE && max == NULL_TREE); 170 171 if (t == VR_UNDEFINED || t == VR_VARYING) 172 gcc_assert (equiv == NULL || bitmap_empty_p (equiv)); 173#endif 174 175 vr->type = t; 176 vr->min = min; 177 vr->max = max; 178 179 /* Since updating the equivalence set involves deep copying the 180 bitmaps, only do it if absolutely necessary. */ 181 if (vr->equiv == NULL) 182 vr->equiv = BITMAP_ALLOC (NULL); 183 184 if (equiv != vr->equiv) 185 { 186 if (equiv && !bitmap_empty_p (equiv)) 187 bitmap_copy (vr->equiv, equiv); 188 else 189 bitmap_clear (vr->equiv); 190 } 191} 192 193 194/* Copy value range FROM into value range TO. */ 195 196static inline void 197copy_value_range (value_range_t *to, value_range_t *from) 198{ 199 set_value_range (to, from->type, from->min, from->max, from->equiv); 200} 201 202 203/* Set value range VR to a non-NULL range of type TYPE. */ 204 205static inline void 206set_value_range_to_nonnull (value_range_t *vr, tree type) 207{ 208 tree zero = build_int_cst (type, 0); 209 set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv); 210} 211 212 213/* Set value range VR to a NULL range of type TYPE. */ 214 215static inline void 216set_value_range_to_null (value_range_t *vr, tree type) 217{ 218 tree zero = build_int_cst (type, 0); 219 set_value_range (vr, VR_RANGE, zero, zero, vr->equiv); 220} 221 222 223/* Set value range VR to VR_VARYING. */ 224 225static inline void 226set_value_range_to_varying (value_range_t *vr) 227{ 228 vr->type = VR_VARYING; 229 vr->min = vr->max = NULL_TREE; 230 if (vr->equiv) 231 bitmap_clear (vr->equiv); 232} 233 234 235/* Set value range VR to VR_UNDEFINED. */ 236 237static inline void 238set_value_range_to_undefined (value_range_t *vr) 239{ 240 vr->type = VR_UNDEFINED; 241 vr->min = vr->max = NULL_TREE; 242 if (vr->equiv) 243 bitmap_clear (vr->equiv); 244} 245 246 247/* Return value range information for VAR. Create an empty range 248 if none existed. */ 249 250static value_range_t * 251get_value_range (tree var) 252{ 253 value_range_t *vr; 254 tree sym; 255 unsigned ver = SSA_NAME_VERSION (var); 256 257 vr = vr_value[ver]; 258 if (vr) 259 return vr; 260 261 /* Create a default value range. */ 262 vr_value[ver] = vr = xmalloc (sizeof (*vr)); 263 memset (vr, 0, sizeof (*vr)); 264 265 /* Allocate an equivalence set. */ 266 vr->equiv = BITMAP_ALLOC (NULL); 267 268 /* If VAR is a default definition, the variable can take any value 269 in VAR's type. */ 270 sym = SSA_NAME_VAR (var); 271 if (var == default_def (sym)) 272 { 273 /* Try to use the "nonnull" attribute to create ~[0, 0] 274 anti-ranges for pointers. Note that this is only valid with 275 default definitions of PARM_DECLs. */ 276 if (TREE_CODE (sym) == PARM_DECL 277 && POINTER_TYPE_P (TREE_TYPE (sym)) 278 && nonnull_arg_p (sym)) 279 set_value_range_to_nonnull (vr, TREE_TYPE (sym)); 280 else 281 set_value_range_to_varying (vr); 282 } 283 284 return vr; 285} 286 287/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ 288 289static inline bool 290vrp_operand_equal_p (tree val1, tree val2) 291{ 292 return (val1 == val2 293 || (val1 && val2 294 && operand_equal_p (val1, val2, 0))); 295} 296 297/* Return true, if the bitmaps B1 and B2 are equal. */ 298 299static inline bool 300vrp_bitmap_equal_p (bitmap b1, bitmap b2) 301{ 302 return (b1 == b2 303 || (b1 && b2 304 && bitmap_equal_p (b1, b2))); 305} 306 307/* Update the value range and equivalence set for variable VAR to 308 NEW_VR. Return true if NEW_VR is different from VAR's previous 309 value. 310 311 NOTE: This function assumes that NEW_VR is a temporary value range 312 object created for the sole purpose of updating VAR's range. The 313 storage used by the equivalence set from NEW_VR will be freed by 314 this function. Do not call update_value_range when NEW_VR 315 is the range object associated with another SSA name. */ 316 317static inline bool 318update_value_range (tree var, value_range_t *new_vr) 319{ 320 value_range_t *old_vr; 321 bool is_new; 322 323 /* Update the value range, if necessary. */ 324 old_vr = get_value_range (var); 325 is_new = old_vr->type != new_vr->type 326 || !vrp_operand_equal_p (old_vr->min, new_vr->min) 327 || !vrp_operand_equal_p (old_vr->max, new_vr->max) 328 || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv); 329 330 if (is_new) 331 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max, 332 new_vr->equiv); 333 334 BITMAP_FREE (new_vr->equiv); 335 new_vr->equiv = NULL; 336 337 return is_new; 338} 339 340 341/* Add VAR and VAR's equivalence set to EQUIV. */ 342 343static void 344add_equivalence (bitmap equiv, tree var) 345{ 346 unsigned ver = SSA_NAME_VERSION (var); 347 value_range_t *vr = vr_value[ver]; 348 349 bitmap_set_bit (equiv, ver); 350 if (vr && vr->equiv) 351 bitmap_ior_into (equiv, vr->equiv); 352} 353 354 355/* Return true if VR is ~[0, 0]. */ 356 357static inline bool 358range_is_nonnull (value_range_t *vr) 359{ 360 return vr->type == VR_ANTI_RANGE 361 && integer_zerop (vr->min) 362 && integer_zerop (vr->max); 363} 364 365 366/* Return true if VR is [0, 0]. */ 367 368static inline bool 369range_is_null (value_range_t *vr) 370{ 371 return vr->type == VR_RANGE 372 && integer_zerop (vr->min) 373 && integer_zerop (vr->max); 374} 375 376 377/* Return true if value range VR involves at least one symbol. */ 378 379static inline bool 380symbolic_range_p (value_range_t *vr) 381{ 382 return (!is_gimple_min_invariant (vr->min) 383 || !is_gimple_min_invariant (vr->max)); 384} 385 386 387/* Like tree_expr_nonzero_p, but this function uses value ranges 388 obtained so far. */ 389 390static bool 391vrp_expr_computes_nonzero (tree expr) 392{ 393 if (tree_expr_nonzero_p (expr)) 394 return true; 395 396 /* If we have an expression of the form &X->a, then the expression 397 is nonnull if X is nonnull. */ 398 if (TREE_CODE (expr) == ADDR_EXPR) 399 { 400 tree base = get_base_address (TREE_OPERAND (expr, 0)); 401 402 if (base != NULL_TREE 403 && TREE_CODE (base) == INDIRECT_REF 404 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) 405 { 406 value_range_t *vr = get_value_range (TREE_OPERAND (base, 0)); 407 if (range_is_nonnull (vr)) 408 return true; 409 } 410 } 411 412 return false; 413} 414 415 416/* Compare two values VAL1 and VAL2. Return 417 418 -2 if VAL1 and VAL2 cannot be compared at compile-time, 419 -1 if VAL1 < VAL2, 420 0 if VAL1 == VAL2, 421 +1 if VAL1 > VAL2, and 422 +2 if VAL1 != VAL2 423 424 This is similar to tree_int_cst_compare but supports pointer values 425 and values that cannot be compared at compile time. */ 426 427static int 428compare_values (tree val1, tree val2) 429{ 430 if (val1 == val2) 431 return 0; 432 433 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or 434 both integers. */ 435 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) 436 == POINTER_TYPE_P (TREE_TYPE (val2))); 437 438 /* Do some limited symbolic comparisons. */ 439 if (!POINTER_TYPE_P (TREE_TYPE (val1))) 440 { 441 /* We can determine some comparisons against +INF and -INF even 442 if the other value is an expression. */ 443 if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1)) 444 && TREE_CODE (val2) == MINUS_EXPR) 445 { 446 /* +INF > NAME - CST. */ 447 return 1; 448 } 449 else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1)) 450 && TREE_CODE (val2) == PLUS_EXPR) 451 { 452 /* -INF < NAME + CST. */ 453 return -1; 454 } 455 else if (TREE_CODE (val1) == MINUS_EXPR 456 && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2))) 457 { 458 /* NAME - CST < +INF. */ 459 return -1; 460 } 461 else if (TREE_CODE (val1) == PLUS_EXPR 462 && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2))) 463 { 464 /* NAME + CST > -INF. */ 465 return 1; 466 } 467 } 468 469 if ((TREE_CODE (val1) == SSA_NAME 470 || TREE_CODE (val1) == PLUS_EXPR 471 || TREE_CODE (val1) == MINUS_EXPR) 472 && (TREE_CODE (val2) == SSA_NAME 473 || TREE_CODE (val2) == PLUS_EXPR 474 || TREE_CODE (val2) == MINUS_EXPR)) 475 { 476 tree n1, c1, n2, c2; 477 478 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', 479 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the 480 same name, return -2. */ 481 if (TREE_CODE (val1) == SSA_NAME) 482 { 483 n1 = val1; 484 c1 = NULL_TREE; 485 } 486 else 487 { 488 n1 = TREE_OPERAND (val1, 0); 489 c1 = TREE_OPERAND (val1, 1); 490 } 491 492 if (TREE_CODE (val2) == SSA_NAME) 493 { 494 n2 = val2; 495 c2 = NULL_TREE; 496 } 497 else 498 { 499 n2 = TREE_OPERAND (val2, 0); 500 c2 = TREE_OPERAND (val2, 1); 501 } 502 503 /* Both values must use the same name. */ 504 if (n1 != n2) 505 return -2; 506 507 if (TREE_CODE (val1) == SSA_NAME) 508 { 509 if (TREE_CODE (val2) == SSA_NAME) 510 /* NAME == NAME */ 511 return 0; 512 else if (TREE_CODE (val2) == PLUS_EXPR) 513 /* NAME < NAME + CST */ 514 return -1; 515 else if (TREE_CODE (val2) == MINUS_EXPR) 516 /* NAME > NAME - CST */ 517 return 1; 518 } 519 else if (TREE_CODE (val1) == PLUS_EXPR) 520 { 521 if (TREE_CODE (val2) == SSA_NAME) 522 /* NAME + CST > NAME */ 523 return 1; 524 else if (TREE_CODE (val2) == PLUS_EXPR) 525 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */ 526 return compare_values (c1, c2); 527 else if (TREE_CODE (val2) == MINUS_EXPR) 528 /* NAME + CST1 > NAME - CST2 */ 529 return 1; 530 } 531 else if (TREE_CODE (val1) == MINUS_EXPR) 532 { 533 if (TREE_CODE (val2) == SSA_NAME) 534 /* NAME - CST < NAME */ 535 return -1; 536 else if (TREE_CODE (val2) == PLUS_EXPR) 537 /* NAME - CST1 < NAME + CST2 */ 538 return -1; 539 else if (TREE_CODE (val2) == MINUS_EXPR) 540 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that 541 C1 and C2 are swapped in the call to compare_values. */ 542 return compare_values (c2, c1); 543 } 544 545 gcc_unreachable (); 546 } 547 548 /* We cannot compare non-constants. */ 549 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)) 550 return -2; 551 552 /* We cannot compare overflowed values. */ 553 if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) 554 return -2; 555 556 if (!POINTER_TYPE_P (TREE_TYPE (val1))) 557 return tree_int_cst_compare (val1, val2); 558 else 559 { 560 tree t; 561 562 /* First see if VAL1 and VAL2 are not the same. */ 563 if (val1 == val2 || operand_equal_p (val1, val2, 0)) 564 return 0; 565 566 /* If VAL1 is a lower address than VAL2, return -1. */ 567 t = fold_binary (LT_EXPR, boolean_type_node, val1, val2); 568 if (t == boolean_true_node) 569 return -1; 570 571 /* If VAL1 is a higher address than VAL2, return +1. */ 572 t = fold_binary (GT_EXPR, boolean_type_node, val1, val2); 573 if (t == boolean_true_node) 574 return 1; 575 576 /* If VAL1 is different than VAL2, return +2. */ 577 t = fold_binary (NE_EXPR, boolean_type_node, val1, val2); 578 if (t == boolean_true_node) 579 return 2; 580 581 return -2; 582 } 583} 584 585 586/* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX), 587 0 if VAL is not inside VR, 588 -2 if we cannot tell either way. 589 590 FIXME, the current semantics of this functions are a bit quirky 591 when taken in the context of VRP. In here we do not care 592 about VR's type. If VR is the anti-range ~[3, 5] the call 593 value_inside_range (4, VR) will return 1. 594 595 This is counter-intuitive in a strict sense, but the callers 596 currently expect this. They are calling the function 597 merely to determine whether VR->MIN <= VAL <= VR->MAX. The 598 callers are applying the VR_RANGE/VR_ANTI_RANGE semantics 599 themselves. 600 601 This also applies to value_ranges_intersect_p and 602 range_includes_zero_p. The semantics of VR_RANGE and 603 VR_ANTI_RANGE should be encoded here, but that also means 604 adapting the users of these functions to the new semantics. */ 605 606static inline int 607value_inside_range (tree val, value_range_t *vr) 608{ 609 int cmp1, cmp2; 610 611 cmp1 = compare_values (val, vr->min); 612 if (cmp1 == -2 || cmp1 == 2) 613 return -2; 614 615 cmp2 = compare_values (val, vr->max); 616 if (cmp2 == -2 || cmp2 == 2) 617 return -2; 618 619 return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0); 620} 621 622 623/* Return true if value ranges VR0 and VR1 have a non-empty 624 intersection. */ 625 626static inline bool 627value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1) 628{ 629 return (value_inside_range (vr1->min, vr0) == 1 630 || value_inside_range (vr1->max, vr0) == 1 631 || value_inside_range (vr0->min, vr1) == 1 632 || value_inside_range (vr0->max, vr1) == 1); 633} 634 635 636/* Return true if VR includes the value zero, false otherwise. FIXME, 637 currently this will return false for an anti-range like ~[-4, 3]. 638 This will be wrong when the semantics of value_inside_range are 639 modified (currently the users of this function expect these 640 semantics). */ 641 642static inline bool 643range_includes_zero_p (value_range_t *vr) 644{ 645 tree zero; 646 647 gcc_assert (vr->type != VR_UNDEFINED 648 && vr->type != VR_VARYING 649 && !symbolic_range_p (vr)); 650 651 zero = build_int_cst (TREE_TYPE (vr->min), 0); 652 return (value_inside_range (zero, vr) == 1); 653} 654 655 656/* Extract value range information from an ASSERT_EXPR EXPR and store 657 it in *VR_P. */ 658 659static void 660extract_range_from_assert (value_range_t *vr_p, tree expr) 661{ 662 tree var, cond, limit, min, max, type; 663 value_range_t *var_vr, *limit_vr; 664 enum tree_code cond_code; 665 666 var = ASSERT_EXPR_VAR (expr); 667 cond = ASSERT_EXPR_COND (expr); 668 669 gcc_assert (COMPARISON_CLASS_P (cond)); 670 671 /* Find VAR in the ASSERT_EXPR conditional. */ 672 if (var == TREE_OPERAND (cond, 0)) 673 { 674 /* If the predicate is of the form VAR COMP LIMIT, then we just 675 take LIMIT from the RHS and use the same comparison code. */ 676 limit = TREE_OPERAND (cond, 1); 677 cond_code = TREE_CODE (cond); 678 } 679 else 680 { 681 /* If the predicate is of the form LIMIT COMP VAR, then we need 682 to flip around the comparison code to create the proper range 683 for VAR. */ 684 limit = TREE_OPERAND (cond, 0); 685 cond_code = swap_tree_comparison (TREE_CODE (cond)); 686 } 687 688 type = TREE_TYPE (limit); 689 gcc_assert (limit != var); 690 691 /* For pointer arithmetic, we only keep track of pointer equality 692 and inequality. */ 693 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR) 694 { 695 set_value_range_to_varying (vr_p); 696 return; 697 } 698 699 /* If LIMIT is another SSA name and LIMIT has a range of its own, 700 try to use LIMIT's range to avoid creating symbolic ranges 701 unnecessarily. */ 702 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL; 703 704 /* LIMIT's range is only interesting if it has any useful information. */ 705 if (limit_vr 706 && (limit_vr->type == VR_UNDEFINED 707 || limit_vr->type == VR_VARYING 708 || symbolic_range_p (limit_vr))) 709 limit_vr = NULL; 710 711 /* Special handling for integral types with super-types. Some FEs 712 construct integral types derived from other types and restrict 713 the range of values these new types may take. 714 715 It may happen that LIMIT is actually smaller than TYPE's minimum 716 value. For instance, the Ada FE is generating code like this 717 during bootstrap: 718 719 D.1480_32 = nam_30 - 300000361; 720 if (D.1480_32 <= 1) goto <L112>; else goto <L52>; 721 <L112>:; 722 D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>; 723 724 All the names are of type types__name_id___XDLU_300000000__399999999 725 which has min == 300000000 and max == 399999999. This means that 726 the ASSERT_EXPR would try to create the range [3000000, 1] which 727 is invalid. 728 729 The fact that the type specifies MIN and MAX values does not 730 automatically mean that every variable of that type will always 731 be within that range, so the predicate may well be true at run 732 time. If we had symbolic -INF and +INF values, we could 733 represent this range, but we currently represent -INF and +INF 734 using the type's min and max values. 735 736 So, the only sensible thing we can do for now is set the 737 resulting range to VR_VARYING. TODO, would having symbolic -INF 738 and +INF values be worth the trouble? */ 739 if (TREE_CODE (limit) != SSA_NAME 740 && INTEGRAL_TYPE_P (type) 741 && TREE_TYPE (type)) 742 { 743 if (cond_code == LE_EXPR || cond_code == LT_EXPR) 744 { 745 tree type_min = TYPE_MIN_VALUE (type); 746 int cmp = compare_values (limit, type_min); 747 748 /* For < or <= comparisons, if LIMIT is smaller than 749 TYPE_MIN, set the range to VR_VARYING. */ 750 if (cmp == -1 || cmp == 0) 751 { 752 set_value_range_to_varying (vr_p); 753 return; 754 } 755 } 756 else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 757 { 758 tree type_max = TYPE_MIN_VALUE (type); 759 int cmp = compare_values (limit, type_max); 760 761 /* For > or >= comparisons, if LIMIT is bigger than 762 TYPE_MAX, set the range to VR_VARYING. */ 763 if (cmp == 1 || cmp == 0) 764 { 765 set_value_range_to_varying (vr_p); 766 return; 767 } 768 } 769 } 770 771 /* Initially, the new range has the same set of equivalences of 772 VAR's range. This will be revised before returning the final 773 value. Since assertions may be chained via mutually exclusive 774 predicates, we will need to trim the set of equivalences before 775 we are done. */ 776 gcc_assert (vr_p->equiv == NULL); 777 vr_p->equiv = BITMAP_ALLOC (NULL); 778 add_equivalence (vr_p->equiv, var); 779 780 /* Extract a new range based on the asserted comparison for VAR and 781 LIMIT's value range. Notice that if LIMIT has an anti-range, we 782 will only use it for equality comparisons (EQ_EXPR). For any 783 other kind of assertion, we cannot derive a range from LIMIT's 784 anti-range that can be used to describe the new range. For 785 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10], 786 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is 787 no single range for x_2 that could describe LE_EXPR, so we might 788 as well build the range [b_4, +INF] for it. */ 789 if (cond_code == EQ_EXPR) 790 { 791 enum value_range_type range_type; 792 793 if (limit_vr) 794 { 795 range_type = limit_vr->type; 796 min = limit_vr->min; 797 max = limit_vr->max; 798 } 799 else 800 { 801 range_type = VR_RANGE; 802 min = limit; 803 max = limit; 804 } 805 806 set_value_range (vr_p, range_type, min, max, vr_p->equiv); 807 808 /* When asserting the equality VAR == LIMIT and LIMIT is another 809 SSA name, the new range will also inherit the equivalence set 810 from LIMIT. */ 811 if (TREE_CODE (limit) == SSA_NAME) 812 add_equivalence (vr_p->equiv, limit); 813 } 814 else if (cond_code == NE_EXPR) 815 { 816 /* As described above, when LIMIT's range is an anti-range and 817 this assertion is an inequality (NE_EXPR), then we cannot 818 derive anything from the anti-range. For instance, if 819 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does 820 not imply that VAR's range is [0, 0]. So, in the case of 821 anti-ranges, we just assert the inequality using LIMIT and 822 not its anti-range. 823 824 If LIMIT_VR is a range, we can only use it to build a new 825 anti-range if LIMIT_VR is a single-valued range. For 826 instance, if LIMIT_VR is [0, 1], the predicate 827 VAR != [0, 1] does not mean that VAR's range is ~[0, 1]. 828 Rather, it means that for value 0 VAR should be ~[0, 0] 829 and for value 1, VAR should be ~[1, 1]. We cannot 830 represent these ranges. 831 832 The only situation in which we can build a valid 833 anti-range is when LIMIT_VR is a single-valued range 834 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case, 835 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */ 836 if (limit_vr 837 && limit_vr->type == VR_RANGE 838 && compare_values (limit_vr->min, limit_vr->max) == 0) 839 { 840 min = limit_vr->min; 841 max = limit_vr->max; 842 } 843 else 844 { 845 /* In any other case, we cannot use LIMIT's range to build a 846 valid anti-range. */ 847 min = max = limit; 848 } 849 850 /* If MIN and MAX cover the whole range for their type, then 851 just use the original LIMIT. */ 852 if (INTEGRAL_TYPE_P (type) 853 && min == TYPE_MIN_VALUE (type) 854 && max == TYPE_MAX_VALUE (type)) 855 min = max = limit; 856 857 set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv); 858 } 859 else if (cond_code == LE_EXPR || cond_code == LT_EXPR) 860 { 861 min = TYPE_MIN_VALUE (type); 862 863 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE) 864 max = limit; 865 else 866 { 867 /* If LIMIT_VR is of the form [N1, N2], we need to build the 868 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for 869 LT_EXPR. */ 870 max = limit_vr->max; 871 } 872 873 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */ 874 if (cond_code == LT_EXPR) 875 { 876 tree one = build_int_cst (type, 1); 877 max = fold_build2 (MINUS_EXPR, type, max, one); 878 } 879 880 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 881 } 882 else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 883 { 884 max = TYPE_MAX_VALUE (type); 885 886 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE) 887 min = limit; 888 else 889 { 890 /* If LIMIT_VR is of the form [N1, N2], we need to build the 891 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for 892 GT_EXPR. */ 893 min = limit_vr->min; 894 } 895 896 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */ 897 if (cond_code == GT_EXPR) 898 { 899 tree one = build_int_cst (type, 1); 900 min = fold_build2 (PLUS_EXPR, type, min, one); 901 } 902 903 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 904 } 905 else 906 gcc_unreachable (); 907 908 /* If VAR already had a known range, it may happen that the new 909 range we have computed and VAR's range are not compatible. For 910 instance, 911 912 if (p_5 == NULL) 913 p_6 = ASSERT_EXPR <p_5, p_5 == NULL>; 914 x_7 = p_6->fld; 915 p_8 = ASSERT_EXPR <p_6, p_6 != NULL>; 916 917 While the above comes from a faulty program, it will cause an ICE 918 later because p_8 and p_6 will have incompatible ranges and at 919 the same time will be considered equivalent. A similar situation 920 would arise from 921 922 if (i_5 > 10) 923 i_6 = ASSERT_EXPR <i_5, i_5 > 10>; 924 if (i_5 < 5) 925 i_7 = ASSERT_EXPR <i_6, i_6 < 5>; 926 927 Again i_6 and i_7 will have incompatible ranges. It would be 928 pointless to try and do anything with i_7's range because 929 anything dominated by 'if (i_5 < 5)' will be optimized away. 930 Note, due to the wa in which simulation proceeds, the statement 931 i_7 = ASSERT_EXPR <...> we would never be visited because the 932 conditional 'if (i_5 < 5)' always evaluates to false. However, 933 this extra check does not hurt and may protect against future 934 changes to VRP that may get into a situation similar to the 935 NULL pointer dereference example. 936 937 Note that these compatibility tests are only needed when dealing 938 with ranges or a mix of range and anti-range. If VAR_VR and VR_P 939 are both anti-ranges, they will always be compatible, because two 940 anti-ranges will always have a non-empty intersection. */ 941 942 var_vr = get_value_range (var); 943 944 /* We may need to make adjustments when VR_P and VAR_VR are numeric 945 ranges or anti-ranges. */ 946 if (vr_p->type == VR_VARYING 947 || vr_p->type == VR_UNDEFINED 948 || var_vr->type == VR_VARYING 949 || var_vr->type == VR_UNDEFINED 950 || symbolic_range_p (vr_p) 951 || symbolic_range_p (var_vr)) 952 return; 953 954 if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE) 955 { 956 /* If the two ranges have a non-empty intersection, we can 957 refine the resulting range. Since the assert expression 958 creates an equivalency and at the same time it asserts a 959 predicate, we can take the intersection of the two ranges to 960 get better precision. */ 961 if (value_ranges_intersect_p (var_vr, vr_p)) 962 { 963 /* Use the larger of the two minimums. */ 964 if (compare_values (vr_p->min, var_vr->min) == -1) 965 min = var_vr->min; 966 else 967 min = vr_p->min; 968 969 /* Use the smaller of the two maximums. */ 970 if (compare_values (vr_p->max, var_vr->max) == 1) 971 max = var_vr->max; 972 else 973 max = vr_p->max; 974 975 set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv); 976 } 977 else 978 { 979 /* The two ranges do not intersect, set the new range to 980 VARYING, because we will not be able to do anything 981 meaningful with it. */ 982 set_value_range_to_varying (vr_p); 983 } 984 } 985 else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE) 986 || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE)) 987 { 988 /* A range and an anti-range will cancel each other only if 989 their ends are the same. For instance, in the example above, 990 p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible, 991 so VR_P should be set to VR_VARYING. */ 992 if (compare_values (var_vr->min, vr_p->min) == 0 993 && compare_values (var_vr->max, vr_p->max) == 0) 994 set_value_range_to_varying (vr_p); 995 } 996} 997 998 999/* Extract range information from SSA name VAR and store it in VR. If 1000 VAR has an interesting range, use it. Otherwise, create the 1001 range [VAR, VAR] and return it. This is useful in situations where 1002 we may have conditionals testing values of VARYING names. For 1003 instance, 1004 1005 x_3 = y_5; 1006 if (x_3 > y_5) 1007 ... 1008 1009 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is 1010 always false. */ 1011 1012static void 1013extract_range_from_ssa_name (value_range_t *vr, tree var) 1014{ 1015 value_range_t *var_vr = get_value_range (var); 1016 1017 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING) 1018 copy_value_range (vr, var_vr); 1019 else 1020 set_value_range (vr, VR_RANGE, var, var, NULL); 1021 1022 add_equivalence (vr->equiv, var); 1023} 1024 1025 1026/* Wrapper around int_const_binop. If the operation overflows and we 1027 are not using wrapping arithmetic, then adjust the result to be 1028 -INF or +INF depending on CODE, VAL1 and VAL2. */ 1029 1030static inline tree 1031vrp_int_const_binop (enum tree_code code, tree val1, tree val2) 1032{ 1033 tree res; 1034 1035 if (flag_wrapv) 1036 return int_const_binop (code, val1, val2, 0); 1037 1038 /* If we are not using wrapping arithmetic, operate symbolically 1039 on -INF and +INF. */ 1040 res = int_const_binop (code, val1, val2, 0); 1041 1042 if (TYPE_UNSIGNED (TREE_TYPE (val1))) 1043 { 1044 int checkz = compare_values (res, val1); 1045 bool overflow = false; 1046 1047 /* Ensure that res = val1 [+*] val2 >= val1 1048 or that res = val1 - val2 <= val1. */ 1049 if ((code == PLUS_EXPR 1050 && !(checkz == 1 || checkz == 0)) 1051 || (code == MINUS_EXPR 1052 && !(checkz == 0 || checkz == -1))) 1053 { 1054 overflow = true; 1055 } 1056 /* Checking for multiplication overflow is done by dividing the 1057 output of the multiplication by the first input of the 1058 multiplication. If the result of that division operation is 1059 not equal to the second input of the multiplication, then the 1060 multiplication overflowed. */ 1061 else if (code == MULT_EXPR && !integer_zerop (val1)) 1062 { 1063 tree tmp = int_const_binop (TRUNC_DIV_EXPR, 1064 TYPE_MAX_VALUE (TREE_TYPE (val1)), 1065 val1, 0); 1066 int check = compare_values (tmp, val2); 1067 1068 if (check != 0) 1069 overflow = true; 1070 } 1071 1072 if (overflow) 1073 { 1074 res = copy_node (res); 1075 TREE_OVERFLOW (res) = 1; 1076 } 1077 1078 } 1079 else if (TREE_OVERFLOW (res) 1080 && !TREE_OVERFLOW (val1) 1081 && !TREE_OVERFLOW (val2)) 1082 { 1083 /* If the operation overflowed but neither VAL1 nor VAL2 are 1084 overflown, return -INF or +INF depending on the operation 1085 and the combination of signs of the operands. */ 1086 int sgn1 = tree_int_cst_sgn (val1); 1087 int sgn2 = tree_int_cst_sgn (val2); 1088 1089 /* Notice that we only need to handle the restricted set of 1090 operations handled by extract_range_from_binary_expr. 1091 Among them, only multiplication, addition and subtraction 1092 can yield overflow without overflown operands because we 1093 are working with integral types only... except in the 1094 case VAL1 = -INF and VAL2 = -1 which overflows to +INF 1095 for division too. */ 1096 1097 /* For multiplication, the sign of the overflow is given 1098 by the comparison of the signs of the operands. */ 1099 if ((code == MULT_EXPR && sgn1 == sgn2) 1100 /* For addition, the operands must be of the same sign 1101 to yield an overflow. Its sign is therefore that 1102 of one of the operands, for example the first. */ 1103 || (code == PLUS_EXPR && sgn1 > 0) 1104 /* For subtraction, the operands must be of different 1105 signs to yield an overflow. Its sign is therefore 1106 that of the first operand or the opposite of that 1107 of the second operand. A first operand of 0 counts 1108 as positive here, for the corner case 0 - (-INF), 1109 which overflows, but must yield +INF. */ 1110 || (code == MINUS_EXPR && sgn1 >= 0) 1111 /* For division, the only case is -INF / -1 = +INF. */ 1112 || code == TRUNC_DIV_EXPR 1113 || code == FLOOR_DIV_EXPR 1114 || code == CEIL_DIV_EXPR 1115 || code == EXACT_DIV_EXPR 1116 || code == ROUND_DIV_EXPR) 1117 return TYPE_MAX_VALUE (TREE_TYPE (res)); 1118 else 1119 return TYPE_MIN_VALUE (TREE_TYPE (res)); 1120 } 1121 1122 return res; 1123} 1124 1125 1126/* Extract range information from a binary expression EXPR based on 1127 the ranges of each of its operands and the expression code. */ 1128 1129static void 1130extract_range_from_binary_expr (value_range_t *vr, tree expr) 1131{ 1132 enum tree_code code = TREE_CODE (expr); 1133 tree op0, op1, min, max; 1134 int cmp; 1135 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 1136 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 1137 1138 /* Not all binary expressions can be applied to ranges in a 1139 meaningful way. Handle only arithmetic operations. */ 1140 if (code != PLUS_EXPR 1141 && code != MINUS_EXPR 1142 && code != MULT_EXPR 1143 && code != TRUNC_DIV_EXPR 1144 && code != FLOOR_DIV_EXPR 1145 && code != CEIL_DIV_EXPR 1146 && code != EXACT_DIV_EXPR 1147 && code != ROUND_DIV_EXPR 1148 && code != MIN_EXPR 1149 && code != MAX_EXPR 1150 && code != TRUTH_ANDIF_EXPR 1151 && code != TRUTH_ORIF_EXPR 1152 && code != TRUTH_AND_EXPR 1153 && code != TRUTH_OR_EXPR 1154 && code != TRUTH_XOR_EXPR) 1155 { 1156 set_value_range_to_varying (vr); 1157 return; 1158 } 1159 1160 /* Get value ranges for each operand. For constant operands, create 1161 a new value range with the operand to simplify processing. */ 1162 op0 = TREE_OPERAND (expr, 0); 1163 if (TREE_CODE (op0) == SSA_NAME) 1164 vr0 = *(get_value_range (op0)); 1165 else if (is_gimple_min_invariant (op0)) 1166 set_value_range (&vr0, VR_RANGE, op0, op0, NULL); 1167 else 1168 set_value_range_to_varying (&vr0); 1169 1170 op1 = TREE_OPERAND (expr, 1); 1171 if (TREE_CODE (op1) == SSA_NAME) 1172 vr1 = *(get_value_range (op1)); 1173 else if (is_gimple_min_invariant (op1)) 1174 set_value_range (&vr1, VR_RANGE, op1, op1, NULL); 1175 else 1176 set_value_range_to_varying (&vr1); 1177 1178 /* If either range is UNDEFINED, so is the result. */ 1179 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED) 1180 { 1181 set_value_range_to_undefined (vr); 1182 return; 1183 } 1184 1185 /* Refuse to operate on VARYING ranges, ranges of different kinds 1186 and symbolic ranges. TODO, we may be able to derive anti-ranges 1187 in some cases. */ 1188 if (vr0.type == VR_VARYING 1189 || vr1.type == VR_VARYING 1190 || vr0.type != vr1.type 1191 || symbolic_range_p (&vr0) 1192 || symbolic_range_p (&vr1)) 1193 { 1194 set_value_range_to_varying (vr); 1195 return; 1196 } 1197 1198 /* Now evaluate the expression to determine the new range. */ 1199 if (POINTER_TYPE_P (TREE_TYPE (expr)) 1200 || POINTER_TYPE_P (TREE_TYPE (op0)) 1201 || POINTER_TYPE_P (TREE_TYPE (op1))) 1202 { 1203 /* For pointer types, we are really only interested in asserting 1204 whether the expression evaluates to non-NULL. FIXME, we used 1205 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but 1206 ivopts is generating expressions with pointer multiplication 1207 in them. */ 1208 if (code == PLUS_EXPR) 1209 { 1210 if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1)) 1211 set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 1212 else if (range_is_null (&vr0) && range_is_null (&vr1)) 1213 set_value_range_to_null (vr, TREE_TYPE (expr)); 1214 else 1215 set_value_range_to_varying (vr); 1216 } 1217 else 1218 { 1219 /* Subtracting from a pointer, may yield 0, so just drop the 1220 resulting range to varying. */ 1221 set_value_range_to_varying (vr); 1222 } 1223 1224 return; 1225 } 1226 1227 /* For integer ranges, apply the operation to each end of the 1228 range and see what we end up with. */ 1229 if (code == TRUTH_ANDIF_EXPR 1230 || code == TRUTH_ORIF_EXPR 1231 || code == TRUTH_AND_EXPR 1232 || code == TRUTH_OR_EXPR 1233 || code == TRUTH_XOR_EXPR) 1234 { 1235 /* Boolean expressions cannot be folded with int_const_binop. */ 1236 min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min); 1237 max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max); 1238 } 1239 else if (code == PLUS_EXPR 1240 || code == MIN_EXPR 1241 || code == MAX_EXPR) 1242 { 1243 /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to 1244 VR_VARYING. It would take more effort to compute a precise 1245 range for such a case. For example, if we have op0 == 1 and 1246 op1 == -1 with their ranges both being ~[0,0], we would have 1247 op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0]. 1248 Note that we are guaranteed to have vr0.type == vr1.type at 1249 this point. */ 1250 if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE) 1251 { 1252 set_value_range_to_varying (vr); 1253 return; 1254 } 1255 1256 /* For operations that make the resulting range directly 1257 proportional to the original ranges, apply the operation to 1258 the same end of each range. */ 1259 min = vrp_int_const_binop (code, vr0.min, vr1.min); 1260 max = vrp_int_const_binop (code, vr0.max, vr1.max); 1261 } 1262 else if (code == MULT_EXPR 1263 || code == TRUNC_DIV_EXPR 1264 || code == FLOOR_DIV_EXPR 1265 || code == CEIL_DIV_EXPR 1266 || code == EXACT_DIV_EXPR 1267 || code == ROUND_DIV_EXPR) 1268 { 1269 tree val[4]; 1270 size_t i; 1271 1272 /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs, 1273 drop to VR_VARYING. It would take more effort to compute a 1274 precise range for such a case. For example, if we have 1275 op0 == 65536 and op1 == 65536 with their ranges both being 1276 ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so 1277 we cannot claim that the product is in ~[0,0]. Note that we 1278 are guaranteed to have vr0.type == vr1.type at this 1279 point. */ 1280 if (code == MULT_EXPR 1281 && vr0.type == VR_ANTI_RANGE 1282 && (flag_wrapv || TYPE_UNSIGNED (TREE_TYPE (op0)))) 1283 { 1284 set_value_range_to_varying (vr); 1285 return; 1286 } 1287 1288 /* Multiplications and divisions are a bit tricky to handle, 1289 depending on the mix of signs we have in the two ranges, we 1290 need to operate on different values to get the minimum and 1291 maximum values for the new range. One approach is to figure 1292 out all the variations of range combinations and do the 1293 operations. 1294 1295 However, this involves several calls to compare_values and it 1296 is pretty convoluted. It's simpler to do the 4 operations 1297 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP 1298 MAX1) and then figure the smallest and largest values to form 1299 the new range. */ 1300 1301 /* Divisions by zero result in a VARYING value. */ 1302 if (code != MULT_EXPR 1303 && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1))) 1304 { 1305 set_value_range_to_varying (vr); 1306 return; 1307 } 1308 1309 /* Compute the 4 cross operations. */ 1310 val[0] = vrp_int_const_binop (code, vr0.min, vr1.min); 1311 1312 val[1] = (vr1.max != vr1.min) 1313 ? vrp_int_const_binop (code, vr0.min, vr1.max) 1314 : NULL_TREE; 1315 1316 val[2] = (vr0.max != vr0.min) 1317 ? vrp_int_const_binop (code, vr0.max, vr1.min) 1318 : NULL_TREE; 1319 1320 val[3] = (vr0.min != vr0.max && vr1.min != vr1.max) 1321 ? vrp_int_const_binop (code, vr0.max, vr1.max) 1322 : NULL_TREE; 1323 1324 /* Set MIN to the minimum of VAL[i] and MAX to the maximum 1325 of VAL[i]. */ 1326 min = val[0]; 1327 max = val[0]; 1328 for (i = 1; i < 4; i++) 1329 { 1330 if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max)) 1331 break; 1332 1333 if (val[i]) 1334 { 1335 if (TREE_OVERFLOW (val[i])) 1336 { 1337 /* If we found an overflowed value, set MIN and MAX 1338 to it so that we set the resulting range to 1339 VARYING. */ 1340 min = max = val[i]; 1341 break; 1342 } 1343 1344 if (compare_values (val[i], min) == -1) 1345 min = val[i]; 1346 1347 if (compare_values (val[i], max) == 1) 1348 max = val[i]; 1349 } 1350 } 1351 } 1352 else if (code == MINUS_EXPR) 1353 { 1354 /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to 1355 VR_VARYING. It would take more effort to compute a precise 1356 range for such a case. For example, if we have op0 == 1 and 1357 op1 == 1 with their ranges both being ~[0,0], we would have 1358 op0 - op1 == 0, so we cannot claim that the difference is in 1359 ~[0,0]. Note that we are guaranteed to have 1360 vr0.type == vr1.type at this point. */ 1361 if (vr0.type == VR_ANTI_RANGE) 1362 { 1363 set_value_range_to_varying (vr); 1364 return; 1365 } 1366 1367 /* For MINUS_EXPR, apply the operation to the opposite ends of 1368 each range. */ 1369 min = vrp_int_const_binop (code, vr0.min, vr1.max); 1370 max = vrp_int_const_binop (code, vr0.max, vr1.min); 1371 } 1372 else 1373 gcc_unreachable (); 1374 1375 /* If either MIN or MAX overflowed, then set the resulting range to 1376 VARYING. */ 1377 if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max)) 1378 { 1379 set_value_range_to_varying (vr); 1380 return; 1381 } 1382 1383 cmp = compare_values (min, max); 1384 if (cmp == -2 || cmp == 1) 1385 { 1386 /* If the new range has its limits swapped around (MIN > MAX), 1387 then the operation caused one of them to wrap around, mark 1388 the new range VARYING. */ 1389 set_value_range_to_varying (vr); 1390 } 1391 else 1392 set_value_range (vr, vr0.type, min, max, NULL); 1393} 1394 1395 1396/* Extract range information from a unary expression EXPR based on 1397 the range of its operand and the expression code. */ 1398 1399static void 1400extract_range_from_unary_expr (value_range_t *vr, tree expr) 1401{ 1402 enum tree_code code = TREE_CODE (expr); 1403 tree min, max, op0; 1404 int cmp; 1405 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 1406 1407 /* Refuse to operate on certain unary expressions for which we 1408 cannot easily determine a resulting range. */ 1409 if (code == FIX_TRUNC_EXPR 1410 || code == FIX_CEIL_EXPR 1411 || code == FIX_FLOOR_EXPR 1412 || code == FIX_ROUND_EXPR 1413 || code == FLOAT_EXPR 1414 || code == BIT_NOT_EXPR 1415 || code == NON_LVALUE_EXPR 1416 || code == CONJ_EXPR) 1417 { 1418 set_value_range_to_varying (vr); 1419 return; 1420 } 1421 1422 /* Get value ranges for the operand. For constant operands, create 1423 a new value range with the operand to simplify processing. */ 1424 op0 = TREE_OPERAND (expr, 0); 1425 if (TREE_CODE (op0) == SSA_NAME) 1426 vr0 = *(get_value_range (op0)); 1427 else if (is_gimple_min_invariant (op0)) 1428 set_value_range (&vr0, VR_RANGE, op0, op0, NULL); 1429 else 1430 set_value_range_to_varying (&vr0); 1431 1432 /* If VR0 is UNDEFINED, so is the result. */ 1433 if (vr0.type == VR_UNDEFINED) 1434 { 1435 set_value_range_to_undefined (vr); 1436 return; 1437 } 1438 1439 /* Refuse to operate on varying and symbolic ranges. Also, if the 1440 operand is neither a pointer nor an integral type, set the 1441 resulting range to VARYING. TODO, in some cases we may be able 1442 to derive anti-ranges (like nonzero values). */ 1443 if (vr0.type == VR_VARYING 1444 || (!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 1445 && !POINTER_TYPE_P (TREE_TYPE (op0))) 1446 || symbolic_range_p (&vr0)) 1447 { 1448 set_value_range_to_varying (vr); 1449 return; 1450 } 1451 1452 /* If the expression involves pointers, we are only interested in 1453 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */ 1454 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0))) 1455 { 1456 if (range_is_nonnull (&vr0) || tree_expr_nonzero_p (expr)) 1457 set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 1458 else if (range_is_null (&vr0)) 1459 set_value_range_to_null (vr, TREE_TYPE (expr)); 1460 else 1461 set_value_range_to_varying (vr); 1462 1463 return; 1464 } 1465 1466 /* Handle unary expressions on integer ranges. */ 1467 if (code == NOP_EXPR || code == CONVERT_EXPR) 1468 { 1469 tree inner_type = TREE_TYPE (op0); 1470 tree outer_type = TREE_TYPE (expr); 1471 1472 /* If VR0 represents a simple range, then try to convert 1473 the min and max values for the range to the same type 1474 as OUTER_TYPE. If the results compare equal to VR0's 1475 min and max values and the new min is still less than 1476 or equal to the new max, then we can safely use the newly 1477 computed range for EXPR. This allows us to compute 1478 accurate ranges through many casts. */ 1479 if (vr0.type == VR_RANGE) 1480 { 1481 tree new_min, new_max; 1482 1483 /* Convert VR0's min/max to OUTER_TYPE. */ 1484 new_min = fold_convert (outer_type, vr0.min); 1485 new_max = fold_convert (outer_type, vr0.max); 1486 1487 /* Verify the new min/max values are gimple values and 1488 that they compare equal to VR0's min/max values. */ 1489 if (is_gimple_val (new_min) 1490 && is_gimple_val (new_max) 1491 && tree_int_cst_equal (new_min, vr0.min) 1492 && tree_int_cst_equal (new_max, vr0.max) 1493 && compare_values (new_min, new_max) <= 0 1494 && compare_values (new_min, new_max) >= -1) 1495 { 1496 set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv); 1497 return; 1498 } 1499 } 1500 1501 /* When converting types of different sizes, set the result to 1502 VARYING. Things like sign extensions and precision loss may 1503 change the range. For instance, if x_3 is of type 'long long 1504 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it 1505 is impossible to know at compile time whether y_5 will be 1506 ~[0, 0]. */ 1507 if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type) 1508 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type)) 1509 { 1510 set_value_range_to_varying (vr); 1511 return; 1512 } 1513 } 1514 1515 /* Apply the operation to each end of the range and see what we end 1516 up with. */ 1517 if (code == NEGATE_EXPR 1518 && !TYPE_UNSIGNED (TREE_TYPE (expr))) 1519 { 1520 /* NEGATE_EXPR flips the range around. We need to treat 1521 TYPE_MIN_VALUE specially dependent on wrapping, range type 1522 and if it was used as minimum or maximum value: 1523 -~[MIN, MIN] == ~[MIN, MIN] 1524 -[MIN, 0] == [0, MAX] for -fno-wrapv 1525 -[MIN, 0] == [0, MIN] for -fwrapv (will be set to varying later) */ 1526 min = tree_int_cst_equal (vr0.max, TYPE_MIN_VALUE (TREE_TYPE (expr))) 1527 ? TYPE_MIN_VALUE (TREE_TYPE (expr)) 1528 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 1529 1530 max = tree_int_cst_equal (vr0.min, TYPE_MIN_VALUE (TREE_TYPE (expr))) 1531 ? (vr0.type == VR_ANTI_RANGE || flag_wrapv 1532 ? TYPE_MIN_VALUE (TREE_TYPE (expr)) 1533 : TYPE_MAX_VALUE (TREE_TYPE (expr))) 1534 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 1535 } 1536 else if (code == ABS_EXPR 1537 && !TYPE_UNSIGNED (TREE_TYPE (expr))) 1538 { 1539 /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a 1540 useful range. */ 1541 if (flag_wrapv 1542 && ((vr0.type == VR_RANGE 1543 && tree_int_cst_equal (vr0.min, TYPE_MIN_VALUE (TREE_TYPE (expr)))) 1544 || (vr0.type == VR_ANTI_RANGE 1545 && !tree_int_cst_equal (vr0.min, TYPE_MIN_VALUE (TREE_TYPE (expr))) 1546 && !range_includes_zero_p (&vr0)))) 1547 { 1548 set_value_range_to_varying (vr); 1549 return; 1550 } 1551 1552 /* ABS_EXPR may flip the range around, if the original range 1553 included negative values. */ 1554 min = (tree_int_cst_equal (vr0.min, TYPE_MIN_VALUE (TREE_TYPE (expr)))) 1555 ? TYPE_MAX_VALUE (TREE_TYPE (expr)) 1556 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 1557 1558 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 1559 1560 cmp = compare_values (min, max); 1561 1562 /* If a VR_ANTI_RANGEs contains zero, then we have 1563 ~[-INF, min(MIN, MAX)]. */ 1564 if (vr0.type == VR_ANTI_RANGE) 1565 { 1566 if (range_includes_zero_p (&vr0)) 1567 { 1568 tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr)); 1569 1570 /* Take the lower of the two values. */ 1571 if (cmp != 1) 1572 max = min; 1573 1574 /* Create ~[-INF, min (abs(MIN), abs(MAX))] 1575 or ~[-INF + 1, min (abs(MIN), abs(MAX))] when 1576 flag_wrapv is set and the original anti-range doesn't include 1577 TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */ 1578 min = (flag_wrapv && !tree_int_cst_equal (vr0.min, type_min_value) 1579 ? int_const_binop (PLUS_EXPR, 1580 type_min_value, 1581 integer_one_node, 0) 1582 : type_min_value); 1583 } 1584 else 1585 { 1586 /* All else has failed, so create the range [0, INF], even for 1587 flag_wrapv since TYPE_MIN_VALUE is in the original 1588 anti-range. */ 1589 vr0.type = VR_RANGE; 1590 min = build_int_cst (TREE_TYPE (expr), 0); 1591 max = TYPE_MAX_VALUE (TREE_TYPE (expr)); 1592 } 1593 } 1594 1595 /* If the range contains zero then we know that the minimum value in the 1596 range will be zero. */ 1597 else if (range_includes_zero_p (&vr0)) 1598 { 1599 if (cmp == 1) 1600 max = min; 1601 min = build_int_cst (TREE_TYPE (expr), 0); 1602 } 1603 else 1604 { 1605 /* If the range was reversed, swap MIN and MAX. */ 1606 if (cmp == 1) 1607 { 1608 tree t = min; 1609 min = max; 1610 max = t; 1611 } 1612 } 1613 } 1614 else 1615 { 1616 /* Otherwise, operate on each end of the range. */ 1617 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 1618 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 1619 } 1620 1621 cmp = compare_values (min, max); 1622 if (cmp == -2 || cmp == 1) 1623 { 1624 /* If the new range has its limits swapped around (MIN > MAX), 1625 then the operation caused one of them to wrap around, mark 1626 the new range VARYING. */ 1627 set_value_range_to_varying (vr); 1628 } 1629 else 1630 set_value_range (vr, vr0.type, min, max, NULL); 1631} 1632 1633 1634/* Extract range information from a comparison expression EXPR based 1635 on the range of its operand and the expression code. */ 1636 1637static void 1638extract_range_from_comparison (value_range_t *vr, tree expr) 1639{ 1640 tree val = vrp_evaluate_conditional (expr, false); 1641 if (val) 1642 { 1643 /* Since this expression was found on the RHS of an assignment, 1644 its type may be different from _Bool. Convert VAL to EXPR's 1645 type. */ 1646 val = fold_convert (TREE_TYPE (expr), val); 1647 set_value_range (vr, VR_RANGE, val, val, vr->equiv); 1648 } 1649 else 1650 set_value_range_to_varying (vr); 1651} 1652 1653 1654/* Try to compute a useful range out of expression EXPR and store it 1655 in *VR. */ 1656 1657static void 1658extract_range_from_expr (value_range_t *vr, tree expr) 1659{ 1660 enum tree_code code = TREE_CODE (expr); 1661 1662 if (code == ASSERT_EXPR) 1663 extract_range_from_assert (vr, expr); 1664 else if (code == SSA_NAME) 1665 extract_range_from_ssa_name (vr, expr); 1666 else if (TREE_CODE_CLASS (code) == tcc_binary 1667 || code == TRUTH_ANDIF_EXPR 1668 || code == TRUTH_ORIF_EXPR 1669 || code == TRUTH_AND_EXPR 1670 || code == TRUTH_OR_EXPR 1671 || code == TRUTH_XOR_EXPR) 1672 extract_range_from_binary_expr (vr, expr); 1673 else if (TREE_CODE_CLASS (code) == tcc_unary) 1674 extract_range_from_unary_expr (vr, expr); 1675 else if (TREE_CODE_CLASS (code) == tcc_comparison) 1676 extract_range_from_comparison (vr, expr); 1677 else if (is_gimple_min_invariant (expr)) 1678 set_value_range (vr, VR_RANGE, expr, expr, NULL); 1679 else if (vrp_expr_computes_nonzero (expr)) 1680 set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 1681 else 1682 set_value_range_to_varying (vr); 1683} 1684 1685/* Given a range VR, a LOOP and a variable VAR, determine whether it 1686 would be profitable to adjust VR using scalar evolution information 1687 for VAR. If so, update VR with the new limits. */ 1688 1689static void 1690adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, 1691 tree var) 1692{ 1693 tree init, step, chrec; 1694 enum ev_direction dir; 1695 1696 /* TODO. Don't adjust anti-ranges. An anti-range may provide 1697 better opportunities than a regular range, but I'm not sure. */ 1698 if (vr->type == VR_ANTI_RANGE) 1699 return; 1700 1701 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); 1702 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 1703 return; 1704 1705 init = initial_condition_in_loop_num (chrec, loop->num); 1706 step = evolution_part_in_loop_num (chrec, loop->num); 1707 1708 /* If STEP is symbolic, we can't know whether INIT will be the 1709 minimum or maximum value in the range. */ 1710 if (step == NULL_TREE 1711 || !is_gimple_min_invariant (step)) 1712 return; 1713 1714 dir = scev_direction (chrec); 1715 if (/* Do not adjust ranges if we do not know whether the iv increases 1716 or decreases, ... */ 1717 dir == EV_DIR_UNKNOWN 1718 /* ... or if it may wrap. */ 1719 || scev_probably_wraps_p (init, step, stmt, 1720 cfg_loops->parray[CHREC_VARIABLE (chrec)], 1721 true)) 1722 return; 1723 1724 if (!POINTER_TYPE_P (TREE_TYPE (init)) 1725 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)) 1726 { 1727 /* For VARYING or UNDEFINED ranges, just about anything we get 1728 from scalar evolutions should be better. */ 1729 if (dir == EV_DIR_DECREASES) 1730 set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)), 1731 init, vr->equiv); 1732 else 1733 set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)), 1734 vr->equiv); 1735 } 1736 else if (vr->type == VR_RANGE) 1737 { 1738 tree min = vr->min; 1739 tree max = vr->max; 1740 1741 if (dir == EV_DIR_DECREASES) 1742 { 1743 /* INIT is the maximum value. If INIT is lower than VR->MAX 1744 but no smaller than VR->MIN, set VR->MAX to INIT. */ 1745 if (compare_values (init, max) == -1) 1746 { 1747 max = init; 1748 1749 /* If we just created an invalid range with the minimum 1750 greater than the maximum, we fail conservatively. 1751 This should happen only in unreachable 1752 parts of code, or for invalid programs. */ 1753 if (compare_values (min, max) == 1) 1754 return; 1755 } 1756 } 1757 else 1758 { 1759 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */ 1760 if (compare_values (init, min) == 1) 1761 { 1762 min = init; 1763 1764 /* Again, avoid creating invalid range by failing. */ 1765 if (compare_values (min, max) == 1) 1766 return; 1767 } 1768 } 1769 1770 set_value_range (vr, VR_RANGE, min, max, vr->equiv); 1771 } 1772} 1773 1774 1775/* Given two numeric value ranges VR0, VR1 and a comparison code COMP: 1776 1777 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for 1778 all the values in the ranges. 1779 1780 - Return BOOLEAN_FALSE_NODE if the comparison always returns false. 1781 1782 - Return NULL_TREE if it is not always possible to determine the 1783 value of the comparison. */ 1784 1785 1786static tree 1787compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1) 1788{ 1789 /* VARYING or UNDEFINED ranges cannot be compared. */ 1790 if (vr0->type == VR_VARYING 1791 || vr0->type == VR_UNDEFINED 1792 || vr1->type == VR_VARYING 1793 || vr1->type == VR_UNDEFINED) 1794 return NULL_TREE; 1795 1796 /* Anti-ranges need to be handled separately. */ 1797 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 1798 { 1799 /* If both are anti-ranges, then we cannot compute any 1800 comparison. */ 1801 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 1802 return NULL_TREE; 1803 1804 /* These comparisons are never statically computable. */ 1805 if (comp == GT_EXPR 1806 || comp == GE_EXPR 1807 || comp == LT_EXPR 1808 || comp == LE_EXPR) 1809 return NULL_TREE; 1810 1811 /* Equality can be computed only between a range and an 1812 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */ 1813 if (vr0->type == VR_RANGE) 1814 { 1815 /* To simplify processing, make VR0 the anti-range. */ 1816 value_range_t *tmp = vr0; 1817 vr0 = vr1; 1818 vr1 = tmp; 1819 } 1820 1821 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR); 1822 1823 if (compare_values (vr0->min, vr1->min) == 0 1824 && compare_values (vr0->max, vr1->max) == 0) 1825 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 1826 1827 return NULL_TREE; 1828 } 1829 1830 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the 1831 operands around and change the comparison code. */ 1832 if (comp == GT_EXPR || comp == GE_EXPR) 1833 { 1834 value_range_t *tmp; 1835 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR; 1836 tmp = vr0; 1837 vr0 = vr1; 1838 vr1 = tmp; 1839 } 1840 1841 if (comp == EQ_EXPR) 1842 { 1843 /* Equality may only be computed if both ranges represent 1844 exactly one value. */ 1845 if (compare_values (vr0->min, vr0->max) == 0 1846 && compare_values (vr1->min, vr1->max) == 0) 1847 { 1848 int cmp_min = compare_values (vr0->min, vr1->min); 1849 int cmp_max = compare_values (vr0->max, vr1->max); 1850 if (cmp_min == 0 && cmp_max == 0) 1851 return boolean_true_node; 1852 else if (cmp_min != -2 && cmp_max != -2) 1853 return boolean_false_node; 1854 } 1855 1856 return NULL_TREE; 1857 } 1858 else if (comp == NE_EXPR) 1859 { 1860 int cmp1, cmp2; 1861 1862 /* If VR0 is completely to the left or completely to the right 1863 of VR1, they are always different. Notice that we need to 1864 make sure that both comparisons yield similar results to 1865 avoid comparing values that cannot be compared at 1866 compile-time. */ 1867 cmp1 = compare_values (vr0->max, vr1->min); 1868 cmp2 = compare_values (vr0->min, vr1->max); 1869 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1)) 1870 return boolean_true_node; 1871 1872 /* If VR0 and VR1 represent a single value and are identical, 1873 return false. */ 1874 else if (compare_values (vr0->min, vr0->max) == 0 1875 && compare_values (vr1->min, vr1->max) == 0 1876 && compare_values (vr0->min, vr1->min) == 0 1877 && compare_values (vr0->max, vr1->max) == 0) 1878 return boolean_false_node; 1879 1880 /* Otherwise, they may or may not be different. */ 1881 else 1882 return NULL_TREE; 1883 } 1884 else if (comp == LT_EXPR || comp == LE_EXPR) 1885 { 1886 int tst; 1887 1888 /* If VR0 is to the left of VR1, return true. */ 1889 tst = compare_values (vr0->max, vr1->min); 1890 if ((comp == LT_EXPR && tst == -1) 1891 || (comp == LE_EXPR && (tst == -1 || tst == 0))) 1892 return boolean_true_node; 1893 1894 /* If VR0 is to the right of VR1, return false. */ 1895 tst = compare_values (vr0->min, vr1->max); 1896 if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 1897 || (comp == LE_EXPR && tst == 1)) 1898 return boolean_false_node; 1899 1900 /* Otherwise, we don't know. */ 1901 return NULL_TREE; 1902 } 1903 1904 gcc_unreachable (); 1905} 1906 1907 1908/* Given a value range VR, a value VAL and a comparison code COMP, return 1909 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the 1910 values in VR. Return BOOLEAN_FALSE_NODE if the comparison 1911 always returns false. Return NULL_TREE if it is not always 1912 possible to determine the value of the comparison. */ 1913 1914static tree 1915compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val) 1916{ 1917 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 1918 return NULL_TREE; 1919 1920 /* Anti-ranges need to be handled separately. */ 1921 if (vr->type == VR_ANTI_RANGE) 1922 { 1923 /* For anti-ranges, the only predicates that we can compute at 1924 compile time are equality and inequality. */ 1925 if (comp == GT_EXPR 1926 || comp == GE_EXPR 1927 || comp == LT_EXPR 1928 || comp == LE_EXPR) 1929 return NULL_TREE; 1930 1931 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */ 1932 if (value_inside_range (val, vr) == 1) 1933 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 1934 1935 return NULL_TREE; 1936 } 1937 1938 if (comp == EQ_EXPR) 1939 { 1940 /* EQ_EXPR may only be computed if VR represents exactly 1941 one value. */ 1942 if (compare_values (vr->min, vr->max) == 0) 1943 { 1944 int cmp = compare_values (vr->min, val); 1945 if (cmp == 0) 1946 return boolean_true_node; 1947 else if (cmp == -1 || cmp == 1 || cmp == 2) 1948 return boolean_false_node; 1949 } 1950 else if (compare_values (val, vr->min) == -1 1951 || compare_values (vr->max, val) == -1) 1952 return boolean_false_node; 1953 1954 return NULL_TREE; 1955 } 1956 else if (comp == NE_EXPR) 1957 { 1958 /* If VAL is not inside VR, then they are always different. */ 1959 if (compare_values (vr->max, val) == -1 1960 || compare_values (vr->min, val) == 1) 1961 return boolean_true_node; 1962 1963 /* If VR represents exactly one value equal to VAL, then return 1964 false. */ 1965 if (compare_values (vr->min, vr->max) == 0 1966 && compare_values (vr->min, val) == 0) 1967 return boolean_false_node; 1968 1969 /* Otherwise, they may or may not be different. */ 1970 return NULL_TREE; 1971 } 1972 else if (comp == LT_EXPR || comp == LE_EXPR) 1973 { 1974 int tst; 1975 1976 /* If VR is to the left of VAL, return true. */ 1977 tst = compare_values (vr->max, val); 1978 if ((comp == LT_EXPR && tst == -1) 1979 || (comp == LE_EXPR && (tst == -1 || tst == 0))) 1980 return boolean_true_node; 1981 1982 /* If VR is to the right of VAL, return false. */ 1983 tst = compare_values (vr->min, val); 1984 if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 1985 || (comp == LE_EXPR && tst == 1)) 1986 return boolean_false_node; 1987 1988 /* Otherwise, we don't know. */ 1989 return NULL_TREE; 1990 } 1991 else if (comp == GT_EXPR || comp == GE_EXPR) 1992 { 1993 int tst; 1994 1995 /* If VR is to the right of VAL, return true. */ 1996 tst = compare_values (vr->min, val); 1997 if ((comp == GT_EXPR && tst == 1) 1998 || (comp == GE_EXPR && (tst == 0 || tst == 1))) 1999 return boolean_true_node; 2000 2001 /* If VR is to the left of VAL, return false. */ 2002 tst = compare_values (vr->max, val); 2003 if ((comp == GT_EXPR && (tst == -1 || tst == 0)) 2004 || (comp == GE_EXPR && tst == -1)) 2005 return boolean_false_node; 2006 2007 /* Otherwise, we don't know. */ 2008 return NULL_TREE; 2009 } 2010 2011 gcc_unreachable (); 2012} 2013 2014 2015/* Debugging dumps. */ 2016 2017void dump_value_range (FILE *, value_range_t *); 2018void debug_value_range (value_range_t *); 2019void dump_all_value_ranges (FILE *); 2020void debug_all_value_ranges (void); 2021void dump_vr_equiv (FILE *, bitmap); 2022void debug_vr_equiv (bitmap); 2023 2024 2025/* Dump value range VR to FILE. */ 2026 2027void 2028dump_value_range (FILE *file, value_range_t *vr) 2029{ 2030 if (vr == NULL) 2031 fprintf (file, "[]"); 2032 else if (vr->type == VR_UNDEFINED) 2033 fprintf (file, "UNDEFINED"); 2034 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE) 2035 { 2036 tree type = TREE_TYPE (vr->min); 2037 2038 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); 2039 2040 if (INTEGRAL_TYPE_P (type) 2041 && !TYPE_UNSIGNED (type) 2042 && vr->min == TYPE_MIN_VALUE (type)) 2043 fprintf (file, "-INF"); 2044 else 2045 print_generic_expr (file, vr->min, 0); 2046 2047 fprintf (file, ", "); 2048 2049 if (INTEGRAL_TYPE_P (type) 2050 && vr->max == TYPE_MAX_VALUE (type)) 2051 fprintf (file, "+INF"); 2052 else 2053 print_generic_expr (file, vr->max, 0); 2054 2055 fprintf (file, "]"); 2056 2057 if (vr->equiv) 2058 { 2059 bitmap_iterator bi; 2060 unsigned i, c = 0; 2061 2062 fprintf (file, " EQUIVALENCES: { "); 2063 2064 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi) 2065 { 2066 print_generic_expr (file, ssa_name (i), 0); 2067 fprintf (file, " "); 2068 c++; 2069 } 2070 2071 fprintf (file, "} (%u elements)", c); 2072 } 2073 } 2074 else if (vr->type == VR_VARYING) 2075 fprintf (file, "VARYING"); 2076 else 2077 fprintf (file, "INVALID RANGE"); 2078} 2079 2080 2081/* Dump value range VR to stderr. */ 2082 2083void 2084debug_value_range (value_range_t *vr) 2085{ 2086 dump_value_range (stderr, vr); 2087 fprintf (stderr, "\n"); 2088} 2089 2090 2091/* Dump value ranges of all SSA_NAMEs to FILE. */ 2092 2093void 2094dump_all_value_ranges (FILE *file) 2095{ 2096 size_t i; 2097 2098 for (i = 0; i < num_ssa_names; i++) 2099 { 2100 if (vr_value[i]) 2101 { 2102 print_generic_expr (file, ssa_name (i), 0); 2103 fprintf (file, ": "); 2104 dump_value_range (file, vr_value[i]); 2105 fprintf (file, "\n"); 2106 } 2107 } 2108 2109 fprintf (file, "\n"); 2110} 2111 2112 2113/* Dump all value ranges to stderr. */ 2114 2115void 2116debug_all_value_ranges (void) 2117{ 2118 dump_all_value_ranges (stderr); 2119} 2120 2121 2122/* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V, 2123 create a new SSA name N and return the assertion assignment 2124 'V = ASSERT_EXPR <V, V OP W>'. */ 2125 2126static tree 2127build_assert_expr_for (tree cond, tree v) 2128{ 2129 tree n, assertion; 2130 2131 gcc_assert (TREE_CODE (v) == SSA_NAME); 2132 n = duplicate_ssa_name (v, NULL_TREE); 2133 2134 if (COMPARISON_CLASS_P (cond)) 2135 { 2136 tree a = build (ASSERT_EXPR, TREE_TYPE (v), v, cond); 2137 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, a); 2138 } 2139 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 2140 { 2141 /* Given !V, build the assignment N = false. */ 2142 tree op0 = TREE_OPERAND (cond, 0); 2143 gcc_assert (op0 == v); 2144 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node); 2145 } 2146 else if (TREE_CODE (cond) == SSA_NAME) 2147 { 2148 /* Given V, build the assignment N = true. */ 2149 gcc_assert (v == cond); 2150 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node); 2151 } 2152 else 2153 gcc_unreachable (); 2154 2155 SSA_NAME_DEF_STMT (n) = assertion; 2156 2157 /* The new ASSERT_EXPR, creates a new SSA name that replaces the 2158 operand of the ASSERT_EXPR. Register the new name and the old one 2159 in the replacement table so that we can fix the SSA web after 2160 adding all the ASSERT_EXPRs. */ 2161 register_new_name_mapping (n, v); 2162 2163 return assertion; 2164} 2165 2166 2167/* Return false if EXPR is a predicate expression involving floating 2168 point values. */ 2169 2170static inline bool 2171fp_predicate (tree expr) 2172{ 2173 return (COMPARISON_CLASS_P (expr) 2174 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))); 2175} 2176 2177 2178/* If the range of values taken by OP can be inferred after STMT executes, 2179 return the comparison code (COMP_CODE_P) and value (VAL_P) that 2180 describes the inferred range. Return true if a range could be 2181 inferred. */ 2182 2183static bool 2184infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p) 2185{ 2186 *val_p = NULL_TREE; 2187 *comp_code_p = ERROR_MARK; 2188 2189 /* Do not attempt to infer anything in names that flow through 2190 abnormal edges. */ 2191 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) 2192 return false; 2193 2194 /* Similarly, don't infer anything from statements that may throw 2195 exceptions. */ 2196 if (tree_could_throw_p (stmt)) 2197 return false; 2198 2199 /* If STMT is the last statement of a basic block with no 2200 successors, there is no point inferring anything about any of its 2201 operands. We would not be able to find a proper insertion point 2202 for the assertion, anyway. */ 2203 if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0) 2204 return false; 2205 2206 if (POINTER_TYPE_P (TREE_TYPE (op))) 2207 { 2208 bool is_store; 2209 unsigned num_uses, num_derefs; 2210 2211 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); 2212 if (num_derefs > 0 && flag_delete_null_pointer_checks) 2213 { 2214 /* We can only assume that a pointer dereference will yield 2215 non-NULL if -fdelete-null-pointer-checks is enabled. */ 2216 *val_p = build_int_cst (TREE_TYPE (op), 0); 2217 *comp_code_p = NE_EXPR; 2218 return true; 2219 } 2220 } 2221 2222 return false; 2223} 2224 2225 2226void dump_asserts_for (FILE *, tree); 2227void debug_asserts_for (tree); 2228void dump_all_asserts (FILE *); 2229void debug_all_asserts (void); 2230 2231/* Dump all the registered assertions for NAME to FILE. */ 2232 2233void 2234dump_asserts_for (FILE *file, tree name) 2235{ 2236 assert_locus_t loc; 2237 2238 fprintf (file, "Assertions to be inserted for "); 2239 print_generic_expr (file, name, 0); 2240 fprintf (file, "\n"); 2241 2242 loc = asserts_for[SSA_NAME_VERSION (name)]; 2243 while (loc) 2244 { 2245 fprintf (file, "\t"); 2246 print_generic_expr (file, bsi_stmt (loc->si), 0); 2247 fprintf (file, "\n\tBB #%d", loc->bb->index); 2248 if (loc->e) 2249 { 2250 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index, 2251 loc->e->dest->index); 2252 dump_edge_info (file, loc->e, 0); 2253 } 2254 fprintf (file, "\n\tPREDICATE: "); 2255 print_generic_expr (file, name, 0); 2256 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]); 2257 print_generic_expr (file, loc->val, 0); 2258 fprintf (file, "\n\n"); 2259 loc = loc->next; 2260 } 2261 2262 fprintf (file, "\n"); 2263} 2264 2265 2266/* Dump all the registered assertions for NAME to stderr. */ 2267 2268void 2269debug_asserts_for (tree name) 2270{ 2271 dump_asserts_for (stderr, name); 2272} 2273 2274 2275/* Dump all the registered assertions for all the names to FILE. */ 2276 2277void 2278dump_all_asserts (FILE *file) 2279{ 2280 unsigned i; 2281 bitmap_iterator bi; 2282 2283 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n"); 2284 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 2285 dump_asserts_for (file, ssa_name (i)); 2286 fprintf (file, "\n"); 2287} 2288 2289 2290/* Dump all the registered assertions for all the names to stderr. */ 2291 2292void 2293debug_all_asserts (void) 2294{ 2295 dump_all_asserts (stderr); 2296} 2297 2298 2299/* If NAME doesn't have an ASSERT_EXPR registered for asserting 2300 'NAME COMP_CODE VAL' at a location that dominates block BB or 2301 E->DEST, then register this location as a possible insertion point 2302 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>. 2303 2304 BB, E and SI provide the exact insertion point for the new 2305 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted 2306 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on 2307 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E 2308 must not be NULL. */ 2309 2310static void 2311register_new_assert_for (tree name, 2312 enum tree_code comp_code, 2313 tree val, 2314 basic_block bb, 2315 edge e, 2316 block_stmt_iterator si) 2317{ 2318 assert_locus_t n, loc, last_loc; 2319 bool found; 2320 basic_block dest_bb; 2321 2322#if defined ENABLE_CHECKING 2323 gcc_assert (bb == NULL || e == NULL); 2324 2325 if (e == NULL) 2326 gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR 2327 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR); 2328#endif 2329 2330 /* The new assertion A will be inserted at BB or E. We need to 2331 determine if the new location is dominated by a previously 2332 registered location for A. If we are doing an edge insertion, 2333 assume that A will be inserted at E->DEST. Note that this is not 2334 necessarily true. 2335 2336 If E is a critical edge, it will be split. But even if E is 2337 split, the new block will dominate the same set of blocks that 2338 E->DEST dominates. 2339 2340 The reverse, however, is not true, blocks dominated by E->DEST 2341 will not be dominated by the new block created to split E. So, 2342 if the insertion location is on a critical edge, we will not use 2343 the new location to move another assertion previously registered 2344 at a block dominated by E->DEST. */ 2345 dest_bb = (bb) ? bb : e->dest; 2346 2347 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and 2348 VAL at a block dominating DEST_BB, then we don't need to insert a new 2349 one. Similarly, if the same assertion already exists at a block 2350 dominated by DEST_BB and the new location is not on a critical 2351 edge, then update the existing location for the assertion (i.e., 2352 move the assertion up in the dominance tree). 2353 2354 Note, this is implemented as a simple linked list because there 2355 should not be more than a handful of assertions registered per 2356 name. If this becomes a performance problem, a table hashed by 2357 COMP_CODE and VAL could be implemented. */ 2358 loc = asserts_for[SSA_NAME_VERSION (name)]; 2359 last_loc = loc; 2360 found = false; 2361 while (loc) 2362 { 2363 if (loc->comp_code == comp_code 2364 && (loc->val == val 2365 || operand_equal_p (loc->val, val, 0))) 2366 { 2367 /* If the assertion NAME COMP_CODE VAL has already been 2368 registered at a basic block that dominates DEST_BB, then 2369 we don't need to insert the same assertion again. Note 2370 that we don't check strict dominance here to avoid 2371 replicating the same assertion inside the same basic 2372 block more than once (e.g., when a pointer is 2373 dereferenced several times inside a block). 2374 2375 An exception to this rule are edge insertions. If the 2376 new assertion is to be inserted on edge E, then it will 2377 dominate all the other insertions that we may want to 2378 insert in DEST_BB. So, if we are doing an edge 2379 insertion, don't do this dominance check. */ 2380 if (e == NULL 2381 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb)) 2382 return; 2383 2384 /* Otherwise, if E is not a critical edge and DEST_BB 2385 dominates the existing location for the assertion, move 2386 the assertion up in the dominance tree by updating its 2387 location information. */ 2388 if ((e == NULL || !EDGE_CRITICAL_P (e)) 2389 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb)) 2390 { 2391 loc->bb = dest_bb; 2392 loc->e = e; 2393 loc->si = si; 2394 return; 2395 } 2396 } 2397 2398 /* Update the last node of the list and move to the next one. */ 2399 last_loc = loc; 2400 loc = loc->next; 2401 } 2402 2403 /* If we didn't find an assertion already registered for 2404 NAME COMP_CODE VAL, add a new one at the end of the list of 2405 assertions associated with NAME. */ 2406 n = xmalloc (sizeof (*n)); 2407 n->bb = dest_bb; 2408 n->e = e; 2409 n->si = si; 2410 n->comp_code = comp_code; 2411 n->val = val; 2412 n->next = NULL; 2413 2414 if (last_loc) 2415 last_loc->next = n; 2416 else 2417 asserts_for[SSA_NAME_VERSION (name)] = n; 2418 2419 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name)); 2420} 2421 2422 2423/* Try to register an edge assertion for SSA name NAME on edge E for 2424 the conditional jump pointed to by SI. Return true if an assertion 2425 for NAME could be registered. */ 2426 2427static bool 2428register_edge_assert_for (tree name, edge e, block_stmt_iterator si) 2429{ 2430 tree val, stmt; 2431 enum tree_code comp_code; 2432 2433 stmt = bsi_stmt (si); 2434 2435 /* Do not attempt to infer anything in names that flow through 2436 abnormal edges. */ 2437 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 2438 return false; 2439 2440 /* If NAME was not found in the sub-graph reachable from E, then 2441 there's nothing to do. */ 2442 if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))) 2443 return false; 2444 2445 /* We found a use of NAME in the sub-graph rooted at E->DEST. 2446 Register an assertion for NAME according to the value that NAME 2447 takes on edge E. */ 2448 if (TREE_CODE (stmt) == COND_EXPR) 2449 { 2450 /* If BB ends in a COND_EXPR then NAME then we should insert 2451 the original predicate on EDGE_TRUE_VALUE and the 2452 opposite predicate on EDGE_FALSE_VALUE. */ 2453 tree cond = COND_EXPR_COND (stmt); 2454 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0; 2455 2456 /* Predicates may be a single SSA name or NAME OP VAL. */ 2457 if (cond == name) 2458 { 2459 /* If the predicate is a name, it must be NAME, in which 2460 case we create the predicate NAME == true or 2461 NAME == false accordingly. */ 2462 comp_code = EQ_EXPR; 2463 val = (is_else_edge) ? boolean_false_node : boolean_true_node; 2464 } 2465 else 2466 { 2467 /* Otherwise, we have a comparison of the form NAME COMP VAL 2468 or VAL COMP NAME. */ 2469 if (name == TREE_OPERAND (cond, 1)) 2470 { 2471 /* If the predicate is of the form VAL COMP NAME, flip 2472 COMP around because we need to register NAME as the 2473 first operand in the predicate. */ 2474 comp_code = swap_tree_comparison (TREE_CODE (cond)); 2475 val = TREE_OPERAND (cond, 0); 2476 } 2477 else 2478 { 2479 /* The comparison is of the form NAME COMP VAL, so the 2480 comparison code remains unchanged. */ 2481 comp_code = TREE_CODE (cond); 2482 val = TREE_OPERAND (cond, 1); 2483 } 2484 2485 /* If we are inserting the assertion on the ELSE edge, we 2486 need to invert the sign comparison. */ 2487 if (is_else_edge) 2488 comp_code = invert_tree_comparison (comp_code, 0); 2489 2490 /* Do not register always-false predicates. FIXME, this 2491 works around a limitation in fold() when dealing with 2492 enumerations. Given 'enum { N1, N2 } x;', fold will not 2493 fold 'if (x > N2)' to 'if (0)'. */ 2494 if ((comp_code == GT_EXPR || comp_code == LT_EXPR) 2495 && (INTEGRAL_TYPE_P (TREE_TYPE (val)) 2496 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))) 2497 { 2498 tree min = TYPE_MIN_VALUE (TREE_TYPE (val)); 2499 tree max = TYPE_MAX_VALUE (TREE_TYPE (val)); 2500 2501 if (comp_code == GT_EXPR && compare_values (val, max) == 0) 2502 return false; 2503 2504 if (comp_code == LT_EXPR && compare_values (val, min) == 0) 2505 return false; 2506 } 2507 } 2508 } 2509 else 2510 { 2511 /* FIXME. Handle SWITCH_EXPR. */ 2512 gcc_unreachable (); 2513 } 2514 2515 register_new_assert_for (name, comp_code, val, NULL, e, si); 2516 return true; 2517} 2518 2519 2520static bool find_assert_locations (basic_block bb); 2521 2522/* Determine whether the outgoing edges of BB should receive an 2523 ASSERT_EXPR for each of the operands of BB's last statement. The 2524 last statement of BB must be a COND_EXPR or a SWITCH_EXPR. 2525 2526 If any of the sub-graphs rooted at BB have an interesting use of 2527 the predicate operands, an assert location node is added to the 2528 list of assertions for the corresponding operands. */ 2529 2530static bool 2531find_conditional_asserts (basic_block bb) 2532{ 2533 bool need_assert; 2534 block_stmt_iterator last_si; 2535 tree op, last; 2536 edge_iterator ei; 2537 edge e; 2538 ssa_op_iter iter; 2539 2540 need_assert = false; 2541 last_si = bsi_last (bb); 2542 last = bsi_stmt (last_si); 2543 2544 /* Look for uses of the operands in each of the sub-graphs 2545 rooted at BB. We need to check each of the outgoing edges 2546 separately, so that we know what kind of ASSERT_EXPR to 2547 insert. */ 2548 FOR_EACH_EDGE (e, ei, bb->succs) 2549 { 2550 if (e->dest == bb) 2551 continue; 2552 2553 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap. 2554 Otherwise, when we finish traversing each of the sub-graphs, we 2555 won't know whether the variables were found in the sub-graphs or 2556 if they had been found in a block upstream from BB. */ 2557 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 2558 RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 2559 2560 /* Traverse the strictly dominated sub-graph rooted at E->DEST 2561 to determine if any of the operands in the conditional 2562 predicate are used. */ 2563 if (e->dest != bb) 2564 need_assert |= find_assert_locations (e->dest); 2565 2566 /* Register the necessary assertions for each operand in the 2567 conditional predicate. */ 2568 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 2569 need_assert |= register_edge_assert_for (op, e, last_si); 2570 } 2571 2572 /* Finally, indicate that we have found the operands in the 2573 conditional. */ 2574 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 2575 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 2576 2577 return need_assert; 2578} 2579 2580 2581/* Traverse all the statements in block BB looking for statements that 2582 may generate useful assertions for the SSA names in their operand. 2583 If a statement produces a useful assertion A for name N_i, then the 2584 list of assertions already generated for N_i is scanned to 2585 determine if A is actually needed. 2586 2587 If N_i already had the assertion A at a location dominating the 2588 current location, then nothing needs to be done. Otherwise, the 2589 new location for A is recorded instead. 2590 2591 1- For every statement S in BB, all the variables used by S are 2592 added to bitmap FOUND_IN_SUBGRAPH. 2593 2594 2- If statement S uses an operand N in a way that exposes a known 2595 value range for N, then if N was not already generated by an 2596 ASSERT_EXPR, create a new assert location for N. For instance, 2597 if N is a pointer and the statement dereferences it, we can 2598 assume that N is not NULL. 2599 2600 3- COND_EXPRs are a special case of #2. We can derive range 2601 information from the predicate but need to insert different 2602 ASSERT_EXPRs for each of the sub-graphs rooted at the 2603 conditional block. If the last statement of BB is a conditional 2604 expression of the form 'X op Y', then 2605 2606 a) Remove X and Y from the set FOUND_IN_SUBGRAPH. 2607 2608 b) If the conditional is the only entry point to the sub-graph 2609 corresponding to the THEN_CLAUSE, recurse into it. On 2610 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then 2611 an ASSERT_EXPR is added for the corresponding variable. 2612 2613 c) Repeat step (b) on the ELSE_CLAUSE. 2614 2615 d) Mark X and Y in FOUND_IN_SUBGRAPH. 2616 2617 For instance, 2618 2619 if (a == 9) 2620 b = a; 2621 else 2622 b = c + 1; 2623 2624 In this case, an assertion on the THEN clause is useful to 2625 determine that 'a' is always 9 on that edge. However, an assertion 2626 on the ELSE clause would be unnecessary. 2627 2628 4- If BB does not end in a conditional expression, then we recurse 2629 into BB's dominator children. 2630 2631 At the end of the recursive traversal, every SSA name will have a 2632 list of locations where ASSERT_EXPRs should be added. When a new 2633 location for name N is found, it is registered by calling 2634 register_new_assert_for. That function keeps track of all the 2635 registered assertions to prevent adding unnecessary assertions. 2636 For instance, if a pointer P_4 is dereferenced more than once in a 2637 dominator tree, only the location dominating all the dereference of 2638 P_4 will receive an ASSERT_EXPR. 2639 2640 If this function returns true, then it means that there are names 2641 for which we need to generate ASSERT_EXPRs. Those assertions are 2642 inserted by process_assert_insertions. 2643 2644 TODO. Handle SWITCH_EXPR. */ 2645 2646static bool 2647find_assert_locations (basic_block bb) 2648{ 2649 block_stmt_iterator si; 2650 tree last, phi; 2651 bool need_assert; 2652 basic_block son; 2653 2654 if (TEST_BIT (blocks_visited, bb->index)) 2655 return false; 2656 2657 SET_BIT (blocks_visited, bb->index); 2658 2659 need_assert = false; 2660 2661 /* Traverse all PHI nodes in BB marking used operands. */ 2662 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2663 { 2664 use_operand_p arg_p; 2665 ssa_op_iter i; 2666 2667 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) 2668 { 2669 tree arg = USE_FROM_PTR (arg_p); 2670 if (TREE_CODE (arg) == SSA_NAME) 2671 { 2672 gcc_assert (is_gimple_reg (PHI_RESULT (phi))); 2673 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg)); 2674 } 2675 } 2676 } 2677 2678 /* Traverse all the statements in BB marking used names and looking 2679 for statements that may infer assertions for their used operands. */ 2680 last = NULL_TREE; 2681 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 2682 { 2683 tree stmt, op; 2684 ssa_op_iter i; 2685 2686 stmt = bsi_stmt (si); 2687 2688 /* See if we can derive an assertion for any of STMT's operands. */ 2689 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 2690 { 2691 tree value; 2692 enum tree_code comp_code; 2693 2694 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside 2695 the sub-graph of a conditional block, when we return from 2696 this recursive walk, our parent will use the 2697 FOUND_IN_SUBGRAPH bitset to determine if one of the 2698 operands it was looking for was present in the sub-graph. */ 2699 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 2700 2701 /* If OP is used only once, namely in this STMT, don't 2702 bother creating an ASSERT_EXPR for it. Such an 2703 ASSERT_EXPR would do nothing but increase compile time. 2704 Experiments show that with this simple check, we can save 2705 more than 20% of ASSERT_EXPRs. */ 2706 if (has_single_use (op)) 2707 continue; 2708 2709 /* If OP is used in such a way that we can infer a value 2710 range for it, and we don't find a previous assertion for 2711 it, create a new assertion location node for OP. */ 2712 if (infer_value_range (stmt, op, &comp_code, &value)) 2713 { 2714 register_new_assert_for (op, comp_code, value, bb, NULL, si); 2715 need_assert = true; 2716 } 2717 } 2718 2719 /* Remember the last statement of the block. */ 2720 last = stmt; 2721 } 2722 2723 /* If BB's last statement is a conditional expression 2724 involving integer operands, recurse into each of the sub-graphs 2725 rooted at BB to determine if we need to add ASSERT_EXPRs. */ 2726 if (last 2727 && TREE_CODE (last) == COND_EXPR 2728 && !fp_predicate (COND_EXPR_COND (last)) 2729 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) 2730 need_assert |= find_conditional_asserts (bb); 2731 2732 /* Recurse into the dominator children of BB. */ 2733 for (son = first_dom_son (CDI_DOMINATORS, bb); 2734 son; 2735 son = next_dom_son (CDI_DOMINATORS, son)) 2736 need_assert |= find_assert_locations (son); 2737 2738 return need_assert; 2739} 2740 2741 2742/* Create an ASSERT_EXPR for NAME and insert it in the location 2743 indicated by LOC. Return true if we made any edge insertions. */ 2744 2745static bool 2746process_assert_insertions_for (tree name, assert_locus_t loc) 2747{ 2748 /* Build the comparison expression NAME_i COMP_CODE VAL. */ 2749 tree stmt, cond, assert_expr; 2750 edge_iterator ei; 2751 edge e; 2752 2753 cond = build (loc->comp_code, boolean_type_node, name, loc->val); 2754 assert_expr = build_assert_expr_for (cond, name); 2755 2756 if (loc->e) 2757 { 2758 /* We have been asked to insert the assertion on an edge. This 2759 is used only by COND_EXPR and SWITCH_EXPR assertions. */ 2760#if defined ENABLE_CHECKING 2761 gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR 2762 || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR); 2763#endif 2764 2765 bsi_insert_on_edge (loc->e, assert_expr); 2766 return true; 2767 } 2768 2769 /* Otherwise, we can insert right after LOC->SI iff the 2770 statement must not be the last statement in the block. */ 2771 stmt = bsi_stmt (loc->si); 2772 if (!stmt_ends_bb_p (stmt)) 2773 { 2774 bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT); 2775 return false; 2776 } 2777 2778 /* If STMT must be the last statement in BB, we can only insert new 2779 assertions on the non-abnormal edge out of BB. Note that since 2780 STMT is not control flow, there may only be one non-abnormal edge 2781 out of BB. */ 2782 FOR_EACH_EDGE (e, ei, loc->bb->succs) 2783 if (!(e->flags & EDGE_ABNORMAL)) 2784 { 2785 bsi_insert_on_edge (e, assert_expr); 2786 return true; 2787 } 2788 2789 gcc_unreachable (); 2790} 2791 2792 2793/* Process all the insertions registered for every name N_i registered 2794 in NEED_ASSERT_FOR. The list of assertions to be inserted are 2795 found in ASSERTS_FOR[i]. */ 2796 2797static void 2798process_assert_insertions (void) 2799{ 2800 unsigned i; 2801 bitmap_iterator bi; 2802 bool update_edges_p = false; 2803 int num_asserts = 0; 2804 2805 if (dump_file && (dump_flags & TDF_DETAILS)) 2806 dump_all_asserts (dump_file); 2807 2808 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 2809 { 2810 assert_locus_t loc = asserts_for[i]; 2811 gcc_assert (loc); 2812 2813 while (loc) 2814 { 2815 assert_locus_t next = loc->next; 2816 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc); 2817 free (loc); 2818 loc = next; 2819 num_asserts++; 2820 } 2821 } 2822 2823 if (update_edges_p) 2824 bsi_commit_edge_inserts (); 2825 2826 if (dump_file && (dump_flags & TDF_STATS)) 2827 fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n", 2828 num_asserts); 2829} 2830 2831 2832/* Traverse the flowgraph looking for conditional jumps to insert range 2833 expressions. These range expressions are meant to provide information 2834 to optimizations that need to reason in terms of value ranges. They 2835 will not be expanded into RTL. For instance, given: 2836 2837 x = ... 2838 y = ... 2839 if (x < y) 2840 y = x - 2; 2841 else 2842 x = y + 3; 2843 2844 this pass will transform the code into: 2845 2846 x = ... 2847 y = ... 2848 if (x < y) 2849 { 2850 x = ASSERT_EXPR <x, x < y> 2851 y = x - 2 2852 } 2853 else 2854 { 2855 y = ASSERT_EXPR <y, x <= y> 2856 x = y + 3 2857 } 2858 2859 The idea is that once copy and constant propagation have run, other 2860 optimizations will be able to determine what ranges of values can 'x' 2861 take in different paths of the code, simply by checking the reaching 2862 definition of 'x'. */ 2863 2864static void 2865insert_range_assertions (void) 2866{ 2867 edge e; 2868 edge_iterator ei; 2869 bool update_ssa_p; 2870 2871 found_in_subgraph = sbitmap_alloc (num_ssa_names); 2872 sbitmap_zero (found_in_subgraph); 2873 2874 blocks_visited = sbitmap_alloc (last_basic_block); 2875 sbitmap_zero (blocks_visited); 2876 2877 need_assert_for = BITMAP_ALLOC (NULL); 2878 asserts_for = xmalloc (num_ssa_names * sizeof (assert_locus_t)); 2879 memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t)); 2880 2881 calculate_dominance_info (CDI_DOMINATORS); 2882 2883 update_ssa_p = false; 2884 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 2885 if (find_assert_locations (e->dest)) 2886 update_ssa_p = true; 2887 2888 if (update_ssa_p) 2889 { 2890 process_assert_insertions (); 2891 update_ssa (TODO_update_ssa_no_phi); 2892 } 2893 2894 if (dump_file && (dump_flags & TDF_DETAILS)) 2895 { 2896 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n"); 2897 dump_function_to_file (current_function_decl, dump_file, dump_flags); 2898 } 2899 2900 sbitmap_free (found_in_subgraph); 2901 free (asserts_for); 2902 BITMAP_FREE (need_assert_for); 2903} 2904 2905 2906/* Replaces all uses of NAME by VAL. */ 2907 2908static void 2909replace_uses_by_vrp (tree name, tree val) 2910{ 2911 imm_use_iterator imm_iter; 2912 use_operand_p use; 2913 tree stmt; 2914 edge e; 2915 unsigned i; 2916 VEC(tree,heap) *stmts = VEC_alloc (tree, heap, 20); 2917 2918 FOR_EACH_IMM_USE_SAFE (use, imm_iter, name) 2919 { 2920 stmt = USE_STMT (use); 2921 SET_USE (use, val); 2922 2923 if (TREE_CODE (stmt) == PHI_NODE) 2924 { 2925 e = PHI_ARG_EDGE (stmt, PHI_ARG_INDEX_FROM_USE (use)); 2926 if (e->flags & EDGE_ABNORMAL) 2927 { 2928 /* This can only occur for virtual operands, since 2929 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 2930 would prevent replacement. */ 2931 gcc_assert (!is_gimple_reg (name)); 2932 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1; 2933 } 2934 } 2935 else 2936 VEC_safe_push (tree, heap, stmts, stmt); 2937 } 2938 2939 /* We do not update the statements in the loop above. Consider 2940 x = w * w; 2941 2942 If we performed the update in the first loop, the statement 2943 would be rescanned after first occurrence of w is replaced, 2944 the new uses would be placed to the beginning of the list, 2945 and we would never process them. */ 2946 for (i = 0; VEC_iterate (tree, stmts, i, stmt); i++) 2947 update_stmt (stmt); 2948 2949 VEC_free (tree, heap, stmts); 2950 2951 /* Also update the trees stored in loop structures. */ 2952 if (current_loops) 2953 { 2954 struct loop *loop; 2955 2956 for (i = 0; i < current_loops->num; i++) 2957 { 2958 loop = current_loops->parray[i]; 2959 if (loop) 2960 substitute_in_loop_info (loop, name, val); 2961 } 2962 } 2963} 2964 2965 2966/* Convert range assertion expressions into the implied copies and 2967 copy propagate away the copies. Doing the trivial copy propagation 2968 here avoids the need to run the full copy propagation pass after 2969 VRP. 2970 2971 FIXME, this will eventually lead to copy propagation removing the 2972 names that had useful range information attached to them. For 2973 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>, 2974 then N_i will have the range [3, +INF]. 2975 2976 However, by converting the assertion into the implied copy 2977 operation N_i = N_j, we will then copy-propagate N_j into the uses 2978 of N_i and lose the range information. We may want to hold on to 2979 ASSERT_EXPRs a little while longer as the ranges could be used in 2980 things like jump threading. 2981 2982 The problem with keeping ASSERT_EXPRs around is that passes after 2983 VRP need to handle them appropriately. 2984 2985 Another approach would be to make the range information a first 2986 class property of the SSA_NAME so that it can be queried from 2987 any pass. This is made somewhat more complex by the need for 2988 multiple ranges to be associated with one SSA_NAME. */ 2989 2990static void 2991remove_range_assertions (void) 2992{ 2993 basic_block bb; 2994 block_stmt_iterator si; 2995 2996 /* Note that the BSI iterator bump happens at the bottom of the 2997 loop and no bump is necessary if we're removing the statement 2998 referenced by the current BSI. */ 2999 FOR_EACH_BB (bb) 3000 for (si = bsi_start (bb); !bsi_end_p (si);) 3001 { 3002 tree stmt = bsi_stmt (si); 3003 3004 if (TREE_CODE (stmt) == MODIFY_EXPR 3005 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) 3006 { 3007 tree rhs = TREE_OPERAND (stmt, 1); 3008 tree cond = fold (ASSERT_EXPR_COND (rhs)); 3009 tree lhs = TREE_OPERAND (stmt, 0); 3010 3011 gcc_assert (cond != boolean_false_node); 3012 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs); 3013 update_stmt (stmt); 3014 3015 /* The statement is now a copy. Propagate the RHS into 3016 every use of the LHS. */ 3017 replace_uses_by_vrp (lhs, ASSERT_EXPR_VAR (rhs)); 3018 3019 /* And finally, remove the copy, it is not needed. */ 3020 bsi_remove (&si); 3021 } 3022 else 3023 bsi_next (&si); 3024 } 3025 3026 sbitmap_free (blocks_visited); 3027} 3028 3029 3030/* Return true if STMT is interesting for VRP. */ 3031 3032static bool 3033stmt_interesting_for_vrp (tree stmt) 3034{ 3035 if (TREE_CODE (stmt) == PHI_NODE 3036 && is_gimple_reg (PHI_RESULT (stmt)) 3037 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))) 3038 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))))) 3039 return true; 3040 else if (TREE_CODE (stmt) == MODIFY_EXPR) 3041 { 3042 tree lhs = TREE_OPERAND (stmt, 0); 3043 3044 if (TREE_CODE (lhs) == SSA_NAME 3045 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 3046 || POINTER_TYPE_P (TREE_TYPE (lhs))) 3047 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 3048 return true; 3049 } 3050 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 3051 return true; 3052 3053 return false; 3054} 3055 3056 3057/* Initialize local data structures for VRP. */ 3058 3059static void 3060vrp_initialize (void) 3061{ 3062 basic_block bb; 3063 3064 vr_value = xmalloc (num_ssa_names * sizeof (value_range_t *)); 3065 memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *)); 3066 3067 FOR_EACH_BB (bb) 3068 { 3069 block_stmt_iterator si; 3070 tree phi; 3071 3072 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 3073 { 3074 if (!stmt_interesting_for_vrp (phi)) 3075 { 3076 tree lhs = PHI_RESULT (phi); 3077 set_value_range_to_varying (get_value_range (lhs)); 3078 DONT_SIMULATE_AGAIN (phi) = true; 3079 } 3080 else 3081 DONT_SIMULATE_AGAIN (phi) = false; 3082 } 3083 3084 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 3085 { 3086 tree stmt = bsi_stmt (si); 3087 3088 if (!stmt_interesting_for_vrp (stmt)) 3089 { 3090 ssa_op_iter i; 3091 tree def; 3092 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF) 3093 set_value_range_to_varying (get_value_range (def)); 3094 DONT_SIMULATE_AGAIN (stmt) = true; 3095 } 3096 else 3097 { 3098 DONT_SIMULATE_AGAIN (stmt) = false; 3099 } 3100 } 3101 } 3102} 3103 3104 3105/* Visit assignment STMT. If it produces an interesting range, record 3106 the SSA name in *OUTPUT_P. */ 3107 3108static enum ssa_prop_result 3109vrp_visit_assignment (tree stmt, tree *output_p) 3110{ 3111 tree lhs, rhs, def; 3112 ssa_op_iter iter; 3113 3114 lhs = TREE_OPERAND (stmt, 0); 3115 rhs = TREE_OPERAND (stmt, 1); 3116 3117 /* We only keep track of ranges in integral and pointer types. */ 3118 if (TREE_CODE (lhs) == SSA_NAME 3119 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 3120 || POINTER_TYPE_P (TREE_TYPE (lhs)))) 3121 { 3122 struct loop *l; 3123 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 3124 3125 extract_range_from_expr (&new_vr, rhs); 3126 3127 /* If STMT is inside a loop, we may be able to know something 3128 else about the range of LHS by examining scalar evolution 3129 information. */ 3130 if (cfg_loops && (l = loop_containing_stmt (stmt))) 3131 adjust_range_with_scev (&new_vr, l, stmt, lhs); 3132 3133 if (update_value_range (lhs, &new_vr)) 3134 { 3135 *output_p = lhs; 3136 3137 if (dump_file && (dump_flags & TDF_DETAILS)) 3138 { 3139 fprintf (dump_file, "Found new range for "); 3140 print_generic_expr (dump_file, lhs, 0); 3141 fprintf (dump_file, ": "); 3142 dump_value_range (dump_file, &new_vr); 3143 fprintf (dump_file, "\n\n"); 3144 } 3145 3146 if (new_vr.type == VR_VARYING) 3147 return SSA_PROP_VARYING; 3148 3149 return SSA_PROP_INTERESTING; 3150 } 3151 3152 return SSA_PROP_NOT_INTERESTING; 3153 } 3154 3155 /* Every other statement produces no useful ranges. */ 3156 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 3157 set_value_range_to_varying (get_value_range (def)); 3158 3159 return SSA_PROP_VARYING; 3160} 3161 3162 3163/* Compare all the value ranges for names equivalent to VAR with VAL 3164 using comparison code COMP. Return the same value returned by 3165 compare_range_with_value. */ 3166 3167static tree 3168compare_name_with_value (enum tree_code comp, tree var, tree val) 3169{ 3170 bitmap_iterator bi; 3171 unsigned i; 3172 bitmap e; 3173 tree retval, t; 3174 3175 t = retval = NULL_TREE; 3176 3177 /* Get the set of equivalences for VAR. */ 3178 e = get_value_range (var)->equiv; 3179 3180 /* Add VAR to its own set of equivalences so that VAR's value range 3181 is processed by this loop (otherwise, we would have to replicate 3182 the body of the loop just to check VAR's value range). */ 3183 bitmap_set_bit (e, SSA_NAME_VERSION (var)); 3184 3185 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) 3186 { 3187 value_range_t equiv_vr = *(vr_value[i]); 3188 3189 /* If name N_i does not have a valid range, use N_i as its own 3190 range. This allows us to compare against names that may 3191 have N_i in their ranges. */ 3192 if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED) 3193 { 3194 equiv_vr.type = VR_RANGE; 3195 equiv_vr.min = ssa_name (i); 3196 equiv_vr.max = ssa_name (i); 3197 } 3198 3199 t = compare_range_with_value (comp, &equiv_vr, val); 3200 if (t) 3201 { 3202 /* If we get different answers from different members 3203 of the equivalence set this check must be in a dead 3204 code region. Folding it to a trap representation 3205 would be correct here. For now just return don't-know. */ 3206 if (retval != NULL 3207 && t != retval) 3208 { 3209 retval = NULL_TREE; 3210 break; 3211 } 3212 retval = t; 3213 } 3214 } 3215 3216 /* Remove VAR from its own equivalence set. */ 3217 bitmap_clear_bit (e, SSA_NAME_VERSION (var)); 3218 3219 if (retval) 3220 return retval; 3221 3222 /* We couldn't find a non-NULL value for the predicate. */ 3223 return NULL_TREE; 3224} 3225 3226 3227/* Given a comparison code COMP and names N1 and N2, compare all the 3228 ranges equivalent to N1 against all the ranges equivalent to N2 3229 to determine the value of N1 COMP N2. Return the same value 3230 returned by compare_ranges. */ 3231 3232static tree 3233compare_names (enum tree_code comp, tree n1, tree n2) 3234{ 3235 tree t, retval; 3236 bitmap e1, e2; 3237 bitmap_iterator bi1, bi2; 3238 unsigned i1, i2; 3239 3240 /* Compare the ranges of every name equivalent to N1 against the 3241 ranges of every name equivalent to N2. */ 3242 e1 = get_value_range (n1)->equiv; 3243 e2 = get_value_range (n2)->equiv; 3244 3245 /* Add N1 and N2 to their own set of equivalences to avoid 3246 duplicating the body of the loop just to check N1 and N2 3247 ranges. */ 3248 bitmap_set_bit (e1, SSA_NAME_VERSION (n1)); 3249 bitmap_set_bit (e2, SSA_NAME_VERSION (n2)); 3250 3251 /* If the equivalence sets have a common intersection, then the two 3252 names can be compared without checking their ranges. */ 3253 if (bitmap_intersect_p (e1, e2)) 3254 { 3255 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 3256 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 3257 3258 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR) 3259 ? boolean_true_node 3260 : boolean_false_node; 3261 } 3262 3263 /* Otherwise, compare all the equivalent ranges. First, add N1 and 3264 N2 to their own set of equivalences to avoid duplicating the body 3265 of the loop just to check N1 and N2 ranges. */ 3266 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) 3267 { 3268 value_range_t vr1 = *(vr_value[i1]); 3269 3270 /* If the range is VARYING or UNDEFINED, use the name itself. */ 3271 if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED) 3272 { 3273 vr1.type = VR_RANGE; 3274 vr1.min = ssa_name (i1); 3275 vr1.max = ssa_name (i1); 3276 } 3277 3278 t = retval = NULL_TREE; 3279 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) 3280 { 3281 value_range_t vr2 = *(vr_value[i2]); 3282 3283 if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED) 3284 { 3285 vr2.type = VR_RANGE; 3286 vr2.min = ssa_name (i2); 3287 vr2.max = ssa_name (i2); 3288 } 3289 3290 t = compare_ranges (comp, &vr1, &vr2); 3291 if (t) 3292 { 3293 /* If we get different answers from different members 3294 of the equivalence set this check must be in a dead 3295 code region. Folding it to a trap representation 3296 would be correct here. For now just return don't-know. */ 3297 if (retval != NULL 3298 && t != retval) 3299 { 3300 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 3301 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 3302 return NULL_TREE; 3303 } 3304 retval = t; 3305 } 3306 } 3307 3308 if (retval) 3309 { 3310 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 3311 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 3312 return retval; 3313 } 3314 } 3315 3316 /* None of the equivalent ranges are useful in computing this 3317 comparison. */ 3318 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 3319 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 3320 return NULL_TREE; 3321} 3322 3323 3324/* Given a conditional predicate COND, try to determine if COND yields 3325 true or false based on the value ranges of its operands. Return 3326 BOOLEAN_TRUE_NODE if the conditional always evaluates to true, 3327 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and, 3328 NULL if the conditional cannot be evaluated at compile time. 3329 3330 If USE_EQUIV_P is true, the ranges of all the names equivalent with 3331 the operands in COND are used when trying to compute its value. 3332 This is only used during final substitution. During propagation, 3333 we only check the range of each variable and not its equivalents. */ 3334 3335tree 3336vrp_evaluate_conditional (tree cond, bool use_equiv_p) 3337{ 3338 gcc_assert (TREE_CODE (cond) == SSA_NAME 3339 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison); 3340 3341 if (TREE_CODE (cond) == SSA_NAME) 3342 { 3343 value_range_t *vr; 3344 tree retval; 3345 3346 if (use_equiv_p) 3347 retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node); 3348 else 3349 { 3350 value_range_t *vr = get_value_range (cond); 3351 retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node); 3352 } 3353 3354 /* If COND has a known boolean range, return it. */ 3355 if (retval) 3356 return retval; 3357 3358 /* Otherwise, if COND has a symbolic range of exactly one value, 3359 return it. */ 3360 vr = get_value_range (cond); 3361 if (vr->type == VR_RANGE && vr->min == vr->max) 3362 return vr->min; 3363 } 3364 else 3365 { 3366 tree op0 = TREE_OPERAND (cond, 0); 3367 tree op1 = TREE_OPERAND (cond, 1); 3368 3369 /* We only deal with integral and pointer types. */ 3370 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 3371 && !POINTER_TYPE_P (TREE_TYPE (op0))) 3372 return NULL_TREE; 3373 3374 if (use_equiv_p) 3375 { 3376 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) 3377 return compare_names (TREE_CODE (cond), op0, op1); 3378 else if (TREE_CODE (op0) == SSA_NAME) 3379 return compare_name_with_value (TREE_CODE (cond), op0, op1); 3380 else if (TREE_CODE (op1) == SSA_NAME) 3381 return compare_name_with_value ( 3382 swap_tree_comparison (TREE_CODE (cond)), op1, op0); 3383 } 3384 else 3385 { 3386 value_range_t *vr0, *vr1; 3387 3388 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL; 3389 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; 3390 3391 if (vr0 && vr1) 3392 return compare_ranges (TREE_CODE (cond), vr0, vr1); 3393 else if (vr0 && vr1 == NULL) 3394 return compare_range_with_value (TREE_CODE (cond), vr0, op1); 3395 else if (vr0 == NULL && vr1) 3396 return compare_range_with_value ( 3397 swap_tree_comparison (TREE_CODE (cond)), vr1, op0); 3398 } 3399 } 3400 3401 /* Anything else cannot be computed statically. */ 3402 return NULL_TREE; 3403} 3404 3405 3406/* Visit conditional statement STMT. If we can determine which edge 3407 will be taken out of STMT's basic block, record it in 3408 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return 3409 SSA_PROP_VARYING. */ 3410 3411static enum ssa_prop_result 3412vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) 3413{ 3414 tree cond, val; 3415 3416 *taken_edge_p = NULL; 3417 3418 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to 3419 add ASSERT_EXPRs for them. */ 3420 if (TREE_CODE (stmt) == SWITCH_EXPR) 3421 return SSA_PROP_VARYING; 3422 3423 cond = COND_EXPR_COND (stmt); 3424 3425 if (dump_file && (dump_flags & TDF_DETAILS)) 3426 { 3427 tree use; 3428 ssa_op_iter i; 3429 3430 fprintf (dump_file, "\nVisiting conditional with predicate: "); 3431 print_generic_expr (dump_file, cond, 0); 3432 fprintf (dump_file, "\nWith known ranges\n"); 3433 3434 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) 3435 { 3436 fprintf (dump_file, "\t"); 3437 print_generic_expr (dump_file, use, 0); 3438 fprintf (dump_file, ": "); 3439 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]); 3440 } 3441 3442 fprintf (dump_file, "\n"); 3443 } 3444 3445 /* Compute the value of the predicate COND by checking the known 3446 ranges of each of its operands. 3447 3448 Note that we cannot evaluate all the equivalent ranges here 3449 because those ranges may not yet be final and with the current 3450 propagation strategy, we cannot determine when the value ranges 3451 of the names in the equivalence set have changed. 3452 3453 For instance, given the following code fragment 3454 3455 i_5 = PHI <8, i_13> 3456 ... 3457 i_14 = ASSERT_EXPR <i_5, i_5 != 0> 3458 if (i_14 == 1) 3459 ... 3460 3461 Assume that on the first visit to i_14, i_5 has the temporary 3462 range [8, 8] because the second argument to the PHI function is 3463 not yet executable. We derive the range ~[0, 0] for i_14 and the 3464 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for 3465 the first time, since i_14 is equivalent to the range [8, 8], we 3466 determine that the predicate is always false. 3467 3468 On the next round of propagation, i_13 is determined to be 3469 VARYING, which causes i_5 to drop down to VARYING. So, another 3470 visit to i_14 is scheduled. In this second visit, we compute the 3471 exact same range and equivalence set for i_14, namely ~[0, 0] and 3472 { i_5 }. But we did not have the previous range for i_5 3473 registered, so vrp_visit_assignment thinks that the range for 3474 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)' 3475 is not visited again, which stops propagation from visiting 3476 statements in the THEN clause of that if(). 3477 3478 To properly fix this we would need to keep the previous range 3479 value for the names in the equivalence set. This way we would've 3480 discovered that from one visit to the other i_5 changed from 3481 range [8, 8] to VR_VARYING. 3482 3483 However, fixing this apparent limitation may not be worth the 3484 additional checking. Testing on several code bases (GCC, DLV, 3485 MICO, TRAMP3D and SPEC2000) showed that doing this results in 3486 4 more predicates folded in SPEC. */ 3487 val = vrp_evaluate_conditional (cond, false); 3488 if (val) 3489 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val); 3490 3491 if (dump_file && (dump_flags & TDF_DETAILS)) 3492 { 3493 fprintf (dump_file, "\nPredicate evaluates to: "); 3494 if (val == NULL_TREE) 3495 fprintf (dump_file, "DON'T KNOW\n"); 3496 else 3497 print_generic_stmt (dump_file, val, 0); 3498 } 3499 3500 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 3501} 3502 3503 3504/* Evaluate statement STMT. If the statement produces a useful range, 3505 return SSA_PROP_INTERESTING and record the SSA name with the 3506 interesting range into *OUTPUT_P. 3507 3508 If STMT is a conditional branch and we can determine its truth 3509 value, the taken edge is recorded in *TAKEN_EDGE_P. 3510 3511 If STMT produces a varying value, return SSA_PROP_VARYING. */ 3512 3513static enum ssa_prop_result 3514vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p) 3515{ 3516 tree def; 3517 ssa_op_iter iter; 3518 stmt_ann_t ann; 3519 3520 if (dump_file && (dump_flags & TDF_DETAILS)) 3521 { 3522 fprintf (dump_file, "\nVisiting statement:\n"); 3523 print_generic_stmt (dump_file, stmt, dump_flags); 3524 fprintf (dump_file, "\n"); 3525 } 3526 3527 ann = stmt_ann (stmt); 3528 if (TREE_CODE (stmt) == MODIFY_EXPR 3529 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 3530 return vrp_visit_assignment (stmt, output_p); 3531 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 3532 return vrp_visit_cond_stmt (stmt, taken_edge_p); 3533 3534 /* All other statements produce nothing of interest for VRP, so mark 3535 their outputs varying and prevent further simulation. */ 3536 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 3537 set_value_range_to_varying (get_value_range (def)); 3538 3539 return SSA_PROP_VARYING; 3540} 3541 3542 3543/* Meet operation for value ranges. Given two value ranges VR0 and 3544 VR1, store in VR0 the result of meeting VR0 and VR1. 3545 3546 The meeting rules are as follows: 3547 3548 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING. 3549 3550 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the 3551 union of VR0 and VR1. */ 3552 3553static void 3554vrp_meet (value_range_t *vr0, value_range_t *vr1) 3555{ 3556 if (vr0->type == VR_UNDEFINED) 3557 { 3558 copy_value_range (vr0, vr1); 3559 return; 3560 } 3561 3562 if (vr1->type == VR_UNDEFINED) 3563 { 3564 /* Nothing to do. VR0 already has the resulting range. */ 3565 return; 3566 } 3567 3568 if (vr0->type == VR_VARYING) 3569 { 3570 /* Nothing to do. VR0 already has the resulting range. */ 3571 return; 3572 } 3573 3574 if (vr1->type == VR_VARYING) 3575 { 3576 set_value_range_to_varying (vr0); 3577 return; 3578 } 3579 3580 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE) 3581 { 3582 /* If VR0 and VR1 have a non-empty intersection, compute the 3583 union of both ranges. */ 3584 if (value_ranges_intersect_p (vr0, vr1)) 3585 { 3586 int cmp; 3587 tree min, max; 3588 3589 /* The lower limit of the new range is the minimum of the 3590 two ranges. If they cannot be compared, the result is 3591 VARYING. */ 3592 cmp = compare_values (vr0->min, vr1->min); 3593 if (cmp == 0 || cmp == 1) 3594 min = vr1->min; 3595 else if (cmp == -1) 3596 min = vr0->min; 3597 else 3598 { 3599 set_value_range_to_varying (vr0); 3600 return; 3601 } 3602 3603 /* Similarly, the upper limit of the new range is the 3604 maximum of the two ranges. If they cannot be compared, 3605 the result is VARYING. */ 3606 cmp = compare_values (vr0->max, vr1->max); 3607 if (cmp == 0 || cmp == -1) 3608 max = vr1->max; 3609 else if (cmp == 1) 3610 max = vr0->max; 3611 else 3612 { 3613 set_value_range_to_varying (vr0); 3614 return; 3615 } 3616 3617 /* The resulting set of equivalences is the intersection of 3618 the two sets. */ 3619 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 3620 bitmap_and_into (vr0->equiv, vr1->equiv); 3621 else if (vr0->equiv && !vr1->equiv) 3622 bitmap_clear (vr0->equiv); 3623 3624 set_value_range (vr0, vr0->type, min, max, vr0->equiv); 3625 } 3626 else 3627 goto no_meet; 3628 } 3629 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 3630 { 3631 /* Two anti-ranges meet only if they are both identical. */ 3632 if (compare_values (vr0->min, vr1->min) == 0 3633 && compare_values (vr0->max, vr1->max) == 0 3634 && compare_values (vr0->min, vr0->max) == 0) 3635 { 3636 /* The resulting set of equivalences is the intersection of 3637 the two sets. */ 3638 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 3639 bitmap_and_into (vr0->equiv, vr1->equiv); 3640 else if (vr0->equiv && !vr1->equiv) 3641 bitmap_clear (vr0->equiv); 3642 } 3643 else 3644 goto no_meet; 3645 } 3646 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 3647 { 3648 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] 3649 meet only if the ranges have an empty intersection. The 3650 result of the meet operation is the anti-range. */ 3651 if (!symbolic_range_p (vr0) 3652 && !symbolic_range_p (vr1) 3653 && !value_ranges_intersect_p (vr0, vr1)) 3654 { 3655 /* Copy most of VR1 into VR0. Don't copy VR1's equivalence 3656 set. We need to compute the intersection of the two 3657 equivalence sets. */ 3658 if (vr1->type == VR_ANTI_RANGE) 3659 set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv); 3660 3661 /* The resulting set of equivalences is the intersection of 3662 the two sets. */ 3663 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 3664 bitmap_and_into (vr0->equiv, vr1->equiv); 3665 else if (vr0->equiv && !vr1->equiv) 3666 bitmap_clear (vr0->equiv); 3667 } 3668 else 3669 goto no_meet; 3670 } 3671 else 3672 gcc_unreachable (); 3673 3674 return; 3675 3676no_meet: 3677 /* The two range VR0 and VR1 do not meet. Before giving up and 3678 setting the result to VARYING, see if we can at least derive a 3679 useful anti-range. FIXME, all this nonsense about distinguishing 3680 anti-ranges from ranges is necessary because of the odd 3681 semantics of range_includes_zero_p and friends. */ 3682 if (!symbolic_range_p (vr0) 3683 && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0)) 3684 || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0))) 3685 && !symbolic_range_p (vr1) 3686 && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1)) 3687 || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1)))) 3688 { 3689 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min)); 3690 3691 /* Since this meet operation did not result from the meeting of 3692 two equivalent names, VR0 cannot have any equivalences. */ 3693 if (vr0->equiv) 3694 bitmap_clear (vr0->equiv); 3695 } 3696 else 3697 set_value_range_to_varying (vr0); 3698} 3699 3700 3701/* Visit all arguments for PHI node PHI that flow through executable 3702 edges. If a valid value range can be derived from all the incoming 3703 value ranges, set a new range for the LHS of PHI. */ 3704 3705static enum ssa_prop_result 3706vrp_visit_phi_node (tree phi) 3707{ 3708 int i; 3709 tree lhs = PHI_RESULT (phi); 3710 value_range_t *lhs_vr = get_value_range (lhs); 3711 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 3712 3713 copy_value_range (&vr_result, lhs_vr); 3714 3715 if (dump_file && (dump_flags & TDF_DETAILS)) 3716 { 3717 fprintf (dump_file, "\nVisiting PHI node: "); 3718 print_generic_expr (dump_file, phi, dump_flags); 3719 } 3720 3721 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 3722 { 3723 edge e = PHI_ARG_EDGE (phi, i); 3724 3725 if (dump_file && (dump_flags & TDF_DETAILS)) 3726 { 3727 fprintf (dump_file, 3728 "\n Argument #%d (%d -> %d %sexecutable)\n", 3729 i, e->src->index, e->dest->index, 3730 (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 3731 } 3732 3733 if (e->flags & EDGE_EXECUTABLE) 3734 { 3735 tree arg = PHI_ARG_DEF (phi, i); 3736 value_range_t vr_arg; 3737 3738 if (TREE_CODE (arg) == SSA_NAME) 3739 vr_arg = *(get_value_range (arg)); 3740 else 3741 { 3742 vr_arg.type = VR_RANGE; 3743 vr_arg.min = arg; 3744 vr_arg.max = arg; 3745 vr_arg.equiv = NULL; 3746 } 3747 3748 if (dump_file && (dump_flags & TDF_DETAILS)) 3749 { 3750 fprintf (dump_file, "\t"); 3751 print_generic_expr (dump_file, arg, dump_flags); 3752 fprintf (dump_file, "\n\tValue: "); 3753 dump_value_range (dump_file, &vr_arg); 3754 fprintf (dump_file, "\n"); 3755 } 3756 3757 vrp_meet (&vr_result, &vr_arg); 3758 3759 if (vr_result.type == VR_VARYING) 3760 break; 3761 } 3762 } 3763 3764 if (vr_result.type == VR_VARYING) 3765 goto varying; 3766 3767 /* To prevent infinite iterations in the algorithm, derive ranges 3768 when the new value is slightly bigger or smaller than the 3769 previous one. */ 3770 if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE) 3771 { 3772 if (!POINTER_TYPE_P (TREE_TYPE (lhs))) 3773 { 3774 int cmp_min = compare_values (lhs_vr->min, vr_result.min); 3775 int cmp_max = compare_values (lhs_vr->max, vr_result.max); 3776 3777 /* If the new minimum is smaller or larger than the previous 3778 one, go all the way to -INF. In the first case, to avoid 3779 iterating millions of times to reach -INF, and in the 3780 other case to avoid infinite bouncing between different 3781 minimums. */ 3782 if (cmp_min > 0 || cmp_min < 0) 3783 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); 3784 3785 /* Similarly, if the new maximum is smaller or larger than 3786 the previous one, go all the way to +INF. */ 3787 if (cmp_max < 0 || cmp_max > 0) 3788 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); 3789 3790 /* If we ended up with a (-INF, +INF) range, set it to 3791 VARYING. */ 3792 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)) 3793 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max))) 3794 goto varying; 3795 } 3796 } 3797 3798 /* If the new range is different than the previous value, keep 3799 iterating. */ 3800 if (update_value_range (lhs, &vr_result)) 3801 return SSA_PROP_INTERESTING; 3802 3803 /* Nothing changed, don't add outgoing edges. */ 3804 return SSA_PROP_NOT_INTERESTING; 3805 3806 /* No match found. Set the LHS to VARYING. */ 3807varying: 3808 set_value_range_to_varying (lhs_vr); 3809 return SSA_PROP_VARYING; 3810} 3811 3812/* Simplify a division or modulo operator to a right shift or 3813 bitwise and if the first operand is unsigned or is greater 3814 than zero and the second operand is an exact power of two. */ 3815 3816static void 3817simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code) 3818{ 3819 tree val = NULL; 3820 tree op = TREE_OPERAND (rhs, 0); 3821 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 3822 3823 if (TYPE_UNSIGNED (TREE_TYPE (op))) 3824 { 3825 val = integer_one_node; 3826 } 3827 else 3828 { 3829 val = compare_range_with_value (GT_EXPR, vr, integer_zero_node); 3830 } 3831 3832 if (val && integer_onep (val)) 3833 { 3834 tree t; 3835 tree op0 = TREE_OPERAND (rhs, 0); 3836 tree op1 = TREE_OPERAND (rhs, 1); 3837 3838 if (rhs_code == TRUNC_DIV_EXPR) 3839 { 3840 t = build_int_cst (NULL_TREE, tree_log2 (op1)); 3841 t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t); 3842 } 3843 else 3844 { 3845 t = build_int_cst (TREE_TYPE (op1), 1); 3846 t = int_const_binop (MINUS_EXPR, op1, t, 0); 3847 t = fold_convert (TREE_TYPE (op0), t); 3848 t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t); 3849 } 3850 3851 TREE_OPERAND (stmt, 1) = t; 3852 update_stmt (stmt); 3853 } 3854} 3855 3856/* If the operand to an ABS_EXPR is >= 0, then eliminate the 3857 ABS_EXPR. If the operand is <= 0, then simplify the 3858 ABS_EXPR into a NEGATE_EXPR. */ 3859 3860static void 3861simplify_abs_using_ranges (tree stmt, tree rhs) 3862{ 3863 tree val = NULL; 3864 tree op = TREE_OPERAND (rhs, 0); 3865 tree type = TREE_TYPE (op); 3866 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 3867 3868 if (TYPE_UNSIGNED (type)) 3869 { 3870 val = integer_zero_node; 3871 } 3872 else if (vr) 3873 { 3874 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node); 3875 if (!val) 3876 { 3877 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node); 3878 3879 if (val) 3880 { 3881 if (integer_zerop (val)) 3882 val = integer_one_node; 3883 else if (integer_onep (val)) 3884 val = integer_zero_node; 3885 } 3886 } 3887 3888 if (val 3889 && (integer_onep (val) || integer_zerop (val))) 3890 { 3891 tree t; 3892 3893 if (integer_onep (val)) 3894 t = build1 (NEGATE_EXPR, TREE_TYPE (op), op); 3895 else 3896 t = op; 3897 3898 TREE_OPERAND (stmt, 1) = t; 3899 update_stmt (stmt); 3900 } 3901 } 3902} 3903 3904/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has 3905 a known value range VR. 3906 3907 If there is one and only one value which will satisfy the 3908 conditional, then return that value. Else return NULL. */ 3909 3910static tree 3911test_for_singularity (enum tree_code cond_code, tree op0, 3912 tree op1, value_range_t *vr) 3913{ 3914 tree min = NULL; 3915 tree max = NULL; 3916 3917 /* Extract minimum/maximum values which satisfy the 3918 the conditional as it was written. */ 3919 if (cond_code == LE_EXPR || cond_code == LT_EXPR) 3920 { 3921 min = TYPE_MIN_VALUE (TREE_TYPE (op0)); 3922 3923 max = op1; 3924 if (cond_code == LT_EXPR) 3925 { 3926 tree one = build_int_cst (TREE_TYPE (op0), 1); 3927 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); 3928 } 3929 } 3930 else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 3931 { 3932 max = TYPE_MAX_VALUE (TREE_TYPE (op0)); 3933 3934 min = op1; 3935 if (cond_code == GT_EXPR) 3936 { 3937 tree one = build_int_cst (TREE_TYPE (op0), 1); 3938 max = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), max, one); 3939 } 3940 } 3941 3942 /* Now refine the minimum and maximum values using any 3943 value range information we have for op0. */ 3944 if (min && max) 3945 { 3946 if (compare_values (vr->min, min) == -1) 3947 min = min; 3948 else 3949 min = vr->min; 3950 if (compare_values (vr->max, max) == 1) 3951 max = max; 3952 else 3953 max = vr->max; 3954 3955 /* If the new min/max values have converged to a 3956 single value, then there is only one value which 3957 can satisfy the condition, return that value. */ 3958 if (min == max && is_gimple_min_invariant (min)) 3959 return min; 3960 } 3961 return NULL; 3962} 3963 3964/* Simplify a conditional using a relational operator to an equality 3965 test if the range information indicates only one value can satisfy 3966 the original conditional. */ 3967 3968static void 3969simplify_cond_using_ranges (tree stmt) 3970{ 3971 tree cond = COND_EXPR_COND (stmt); 3972 tree op0 = TREE_OPERAND (cond, 0); 3973 tree op1 = TREE_OPERAND (cond, 1); 3974 enum tree_code cond_code = TREE_CODE (cond); 3975 3976 if (cond_code != NE_EXPR 3977 && cond_code != EQ_EXPR 3978 && TREE_CODE (op0) == SSA_NAME 3979 && INTEGRAL_TYPE_P (TREE_TYPE (op0)) 3980 && is_gimple_min_invariant (op1)) 3981 { 3982 value_range_t *vr = get_value_range (op0); 3983 3984 /* If we have range information for OP0, then we might be 3985 able to simplify this conditional. */ 3986 if (vr->type == VR_RANGE) 3987 { 3988 tree new = test_for_singularity (cond_code, op0, op1, vr); 3989 3990 if (new) 3991 { 3992 if (dump_file) 3993 { 3994 fprintf (dump_file, "Simplified relational "); 3995 print_generic_expr (dump_file, cond, 0); 3996 fprintf (dump_file, " into "); 3997 } 3998 3999 COND_EXPR_COND (stmt) 4000 = build (EQ_EXPR, boolean_type_node, op0, new); 4001 update_stmt (stmt); 4002 4003 if (dump_file) 4004 { 4005 print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 4006 fprintf (dump_file, "\n"); 4007 } 4008 return; 4009 4010 } 4011 4012 /* Try again after inverting the condition. We only deal 4013 with integral types here, so no need to worry about 4014 issues with inverting FP comparisons. */ 4015 cond_code = invert_tree_comparison (cond_code, false); 4016 new = test_for_singularity (cond_code, op0, op1, vr); 4017 4018 if (new) 4019 { 4020 if (dump_file) 4021 { 4022 fprintf (dump_file, "Simplified relational "); 4023 print_generic_expr (dump_file, cond, 0); 4024 fprintf (dump_file, " into "); 4025 } 4026 4027 COND_EXPR_COND (stmt) 4028 = build (NE_EXPR, boolean_type_node, op0, new); 4029 update_stmt (stmt); 4030 4031 if (dump_file) 4032 { 4033 print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 4034 fprintf (dump_file, "\n"); 4035 } 4036 return; 4037 4038 } 4039 } 4040 } 4041} 4042 4043/* Simplify STMT using ranges if possible. */ 4044 4045void 4046simplify_stmt_using_ranges (tree stmt) 4047{ 4048 if (TREE_CODE (stmt) == MODIFY_EXPR) 4049 { 4050 tree rhs = TREE_OPERAND (stmt, 1); 4051 enum tree_code rhs_code = TREE_CODE (rhs); 4052 4053 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR 4054 and BIT_AND_EXPR respectively if the first operand is greater 4055 than zero and the second operand is an exact power of two. */ 4056 if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR) 4057 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))) 4058 && integer_pow2p (TREE_OPERAND (rhs, 1))) 4059 simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code); 4060 4061 /* Transform ABS (X) into X or -X as appropriate. */ 4062 if (rhs_code == ABS_EXPR 4063 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME 4064 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))) 4065 simplify_abs_using_ranges (stmt, rhs); 4066 } 4067 else if (TREE_CODE (stmt) == COND_EXPR 4068 && COMPARISON_CLASS_P (COND_EXPR_COND (stmt))) 4069 { 4070 simplify_cond_using_ranges (stmt); 4071 } 4072} 4073 4074 4075 4076/* Traverse all the blocks folding conditionals with known ranges. */ 4077 4078static void 4079vrp_finalize (void) 4080{ 4081 size_t i; 4082 prop_value_t *single_val_range; 4083 bool do_value_subst_p; 4084 4085 if (dump_file) 4086 { 4087 fprintf (dump_file, "\nValue ranges after VRP:\n\n"); 4088 dump_all_value_ranges (dump_file); 4089 fprintf (dump_file, "\n"); 4090 } 4091 4092 /* We may have ended with ranges that have exactly one value. Those 4093 values can be substituted as any other copy/const propagated 4094 value using substitute_and_fold. */ 4095 single_val_range = xmalloc (num_ssa_names * sizeof (*single_val_range)); 4096 memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range)); 4097 4098 do_value_subst_p = false; 4099 for (i = 0; i < num_ssa_names; i++) 4100 if (vr_value[i] 4101 && vr_value[i]->type == VR_RANGE 4102 && vr_value[i]->min == vr_value[i]->max) 4103 { 4104 single_val_range[i].value = vr_value[i]->min; 4105 do_value_subst_p = true; 4106 } 4107 4108 if (!do_value_subst_p) 4109 { 4110 /* We found no single-valued ranges, don't waste time trying to 4111 do single value substitution in substitute_and_fold. */ 4112 free (single_val_range); 4113 single_val_range = NULL; 4114 } 4115 4116 substitute_and_fold (single_val_range, true); 4117 4118 /* Free allocated memory. */ 4119 for (i = 0; i < num_ssa_names; i++) 4120 if (vr_value[i]) 4121 { 4122 BITMAP_FREE (vr_value[i]->equiv); 4123 free (vr_value[i]); 4124 } 4125 4126 free (single_val_range); 4127 free (vr_value); 4128} 4129 4130 4131/* Main entry point to VRP (Value Range Propagation). This pass is 4132 loosely based on J. R. C. Patterson, ``Accurate Static Branch 4133 Prediction by Value Range Propagation,'' in SIGPLAN Conference on 4134 Programming Language Design and Implementation, pp. 67-78, 1995. 4135 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html 4136 4137 This is essentially an SSA-CCP pass modified to deal with ranges 4138 instead of constants. 4139 4140 While propagating ranges, we may find that two or more SSA name 4141 have equivalent, though distinct ranges. For instance, 4142 4143 1 x_9 = p_3->a; 4144 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0> 4145 3 if (p_4 == q_2) 4146 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>; 4147 5 endif 4148 6 if (q_2) 4149 4150 In the code above, pointer p_5 has range [q_2, q_2], but from the 4151 code we can also determine that p_5 cannot be NULL and, if q_2 had 4152 a non-varying range, p_5's range should also be compatible with it. 4153 4154 These equivalences are created by two expressions: ASSERT_EXPR and 4155 copy operations. Since p_5 is an assertion on p_4, and p_4 was the 4156 result of another assertion, then we can use the fact that p_5 and 4157 p_4 are equivalent when evaluating p_5's range. 4158 4159 Together with value ranges, we also propagate these equivalences 4160 between names so that we can take advantage of information from 4161 multiple ranges when doing final replacement. Note that this 4162 equivalency relation is transitive but not symmetric. 4163 4164 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we 4165 cannot assert that q_2 is equivalent to p_5 because q_2 may be used 4166 in contexts where that assertion does not hold (e.g., in line 6). 4167 4168 TODO, the main difference between this pass and Patterson's is that 4169 we do not propagate edge probabilities. We only compute whether 4170 edges can be taken or not. That is, instead of having a spectrum 4171 of jump probabilities between 0 and 1, we only deal with 0, 1 and 4172 DON'T KNOW. In the future, it may be worthwhile to propagate 4173 probabilities to aid branch prediction. */ 4174 4175static void 4176execute_vrp (void) 4177{ 4178 insert_range_assertions (); 4179 4180 cfg_loops = loop_optimizer_init (NULL); 4181 if (cfg_loops) 4182 scev_initialize (cfg_loops); 4183 4184 vrp_initialize (); 4185 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); 4186 vrp_finalize (); 4187 4188 if (cfg_loops) 4189 { 4190 scev_finalize (); 4191 loop_optimizer_finalize (cfg_loops, NULL); 4192 current_loops = NULL; 4193 } 4194 4195 remove_range_assertions (); 4196} 4197 4198static bool 4199gate_vrp (void) 4200{ 4201 return flag_tree_vrp != 0; 4202} 4203 4204struct tree_opt_pass pass_vrp = 4205{ 4206 "vrp", /* name */ 4207 gate_vrp, /* gate */ 4208 execute_vrp, /* execute */ 4209 NULL, /* sub */ 4210 NULL, /* next */ 4211 0, /* static_pass_number */ 4212 TV_TREE_VRP, /* tv_id */ 4213 PROP_ssa | PROP_alias, /* properties_required */ 4214 0, /* properties_provided */ 4215 0, /* properties_destroyed */ 4216 0, /* todo_flags_start */ 4217 TODO_cleanup_cfg 4218 | TODO_ggc_collect 4219 | TODO_verify_ssa 4220 | TODO_dump_func 4221 | TODO_update_ssa, /* todo_flags_finish */ 4222 0 /* letter */ 4223}; 4224