1 /* Support routines for Value Range Propagation (VRP). 2 Copyright (C) 2005-2018 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com>. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "backend.h" 25 #include "insn-codes.h" 26 #include "rtl.h" 27 #include "tree.h" 28 #include "gimple.h" 29 #include "cfghooks.h" 30 #include "tree-pass.h" 31 #include "ssa.h" 32 #include "optabs-tree.h" 33 #include "gimple-pretty-print.h" 34 #include "diagnostic-core.h" 35 #include "flags.h" 36 #include "fold-const.h" 37 #include "stor-layout.h" 38 #include "calls.h" 39 #include "cfganal.h" 40 #include "gimple-fold.h" 41 #include "tree-eh.h" 42 #include "gimple-iterator.h" 43 #include "gimple-walk.h" 44 #include "tree-cfg.h" 45 #include "tree-dfa.h" 46 #include "tree-ssa-loop-manip.h" 47 #include "tree-ssa-loop-niter.h" 48 #include "tree-ssa-loop.h" 49 #include "tree-into-ssa.h" 50 #include "tree-ssa.h" 51 #include "intl.h" 52 #include "cfgloop.h" 53 #include "tree-scalar-evolution.h" 54 #include "tree-ssa-propagate.h" 55 #include "tree-chrec.h" 56 #include "tree-ssa-threadupdate.h" 57 #include "tree-ssa-scopedtables.h" 58 #include "tree-ssa-threadedge.h" 59 #include "omp-general.h" 60 #include "target.h" 61 #include "case-cfn-macros.h" 62 #include "params.h" 63 #include "alloc-pool.h" 64 #include "domwalk.h" 65 #include "tree-cfgcleanup.h" 66 #include "stringpool.h" 67 #include "attribs.h" 68 #include "vr-values.h" 69 #include "builtins.h" 70 71 /* Set of SSA names found live during the RPO traversal of the function 72 for still active basic-blocks. */ 73 static sbitmap *live; 74 75 /* Return true if the SSA name NAME is live on the edge E. */ 76 77 static bool 78 live_on_edge (edge e, tree name) 79 { 80 return (live[e->dest->index] 81 && bitmap_bit_p (live[e->dest->index], SSA_NAME_VERSION (name))); 82 } 83 84 /* Location information for ASSERT_EXPRs. Each instance of this 85 structure describes an ASSERT_EXPR for an SSA name. Since a single 86 SSA name may have more than one assertion associated with it, these 87 locations are kept in a linked list attached to the corresponding 88 SSA name. */ 89 struct assert_locus 90 { 91 /* Basic block where the assertion would be inserted. */ 92 basic_block bb; 93 94 /* Some assertions need to be inserted on an edge (e.g., assertions 95 generated by COND_EXPRs). In those cases, BB will be NULL. */ 96 edge e; 97 98 /* Pointer to the statement that generated this assertion. */ 99 gimple_stmt_iterator si; 100 101 /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */ 102 enum tree_code comp_code; 103 104 /* Value being compared against. */ 105 tree val; 106 107 /* Expression to compare. */ 108 tree expr; 109 110 /* Next node in the linked list. */ 111 assert_locus *next; 112 }; 113 114 /* If bit I is present, it means that SSA name N_i has a list of 115 assertions that should be inserted in the IL. */ 116 static bitmap need_assert_for; 117 118 /* Array of locations lists where to insert assertions. ASSERTS_FOR[I] 119 holds a list of ASSERT_LOCUS_T nodes that describe where 120 ASSERT_EXPRs for SSA name N_I should be inserted. */ 121 static assert_locus **asserts_for; 122 123 vec<edge> to_remove_edges; 124 vec<switch_update> to_update_switch_stmts; 125 126 127 /* Return the maximum value for TYPE. */ 128 129 tree 130 vrp_val_max (const_tree type) 131 { 132 if (!INTEGRAL_TYPE_P (type)) 133 return NULL_TREE; 134 135 return TYPE_MAX_VALUE (type); 136 } 137 138 /* Return the minimum value for TYPE. */ 139 140 tree 141 vrp_val_min (const_tree type) 142 { 143 if (!INTEGRAL_TYPE_P (type)) 144 return NULL_TREE; 145 146 return TYPE_MIN_VALUE (type); 147 } 148 149 /* Return whether VAL is equal to the maximum value of its type. 150 We can't do a simple equality comparison with TYPE_MAX_VALUE because 151 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE 152 is not == to the integer constant with the same value in the type. */ 153 154 bool 155 vrp_val_is_max (const_tree val) 156 { 157 tree type_max = vrp_val_max (TREE_TYPE (val)); 158 return (val == type_max 159 || (type_max != NULL_TREE 160 && operand_equal_p (val, type_max, 0))); 161 } 162 163 /* Return whether VAL is equal to the minimum value of its type. */ 164 165 bool 166 vrp_val_is_min (const_tree val) 167 { 168 tree type_min = vrp_val_min (TREE_TYPE (val)); 169 return (val == type_min 170 || (type_min != NULL_TREE 171 && operand_equal_p (val, type_min, 0))); 172 } 173 174 /* VR_TYPE describes a range with mininum value *MIN and maximum 175 value *MAX. Restrict the range to the set of values that have 176 no bits set outside NONZERO_BITS. Update *MIN and *MAX and 177 return the new range type. 178 179 SGN gives the sign of the values described by the range. */ 180 181 enum value_range_type 182 intersect_range_with_nonzero_bits (enum value_range_type vr_type, 183 wide_int *min, wide_int *max, 184 const wide_int &nonzero_bits, 185 signop sgn) 186 { 187 if (vr_type == VR_ANTI_RANGE) 188 { 189 /* The VR_ANTI_RANGE is equivalent to the union of the ranges 190 A: [-INF, *MIN) and B: (*MAX, +INF]. First use NONZERO_BITS 191 to create an inclusive upper bound for A and an inclusive lower 192 bound for B. */ 193 wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits); 194 wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits); 195 196 /* If the calculation of A_MAX wrapped, A is effectively empty 197 and A_MAX is the highest value that satisfies NONZERO_BITS. 198 Likewise if the calculation of B_MIN wrapped, B is effectively 199 empty and B_MIN is the lowest value that satisfies NONZERO_BITS. */ 200 bool a_empty = wi::ge_p (a_max, *min, sgn); 201 bool b_empty = wi::le_p (b_min, *max, sgn); 202 203 /* If both A and B are empty, there are no valid values. */ 204 if (a_empty && b_empty) 205 return VR_UNDEFINED; 206 207 /* If exactly one of A or B is empty, return a VR_RANGE for the 208 other one. */ 209 if (a_empty || b_empty) 210 { 211 *min = b_min; 212 *max = a_max; 213 gcc_checking_assert (wi::le_p (*min, *max, sgn)); 214 return VR_RANGE; 215 } 216 217 /* Update the VR_ANTI_RANGE bounds. */ 218 *min = a_max + 1; 219 *max = b_min - 1; 220 gcc_checking_assert (wi::le_p (*min, *max, sgn)); 221 222 /* Now check whether the excluded range includes any values that 223 satisfy NONZERO_BITS. If not, switch to a full VR_RANGE. */ 224 if (wi::round_up_for_mask (*min, nonzero_bits) == b_min) 225 { 226 unsigned int precision = min->get_precision (); 227 *min = wi::min_value (precision, sgn); 228 *max = wi::max_value (precision, sgn); 229 vr_type = VR_RANGE; 230 } 231 } 232 if (vr_type == VR_RANGE) 233 { 234 *max = wi::round_down_for_mask (*max, nonzero_bits); 235 236 /* Check that the range contains at least one valid value. */ 237 if (wi::gt_p (*min, *max, sgn)) 238 return VR_UNDEFINED; 239 240 *min = wi::round_up_for_mask (*min, nonzero_bits); 241 gcc_checking_assert (wi::le_p (*min, *max, sgn)); 242 } 243 return vr_type; 244 } 245 246 /* Set value range VR to VR_UNDEFINED. */ 247 248 static inline void 249 set_value_range_to_undefined (value_range *vr) 250 { 251 vr->type = VR_UNDEFINED; 252 vr->min = vr->max = NULL_TREE; 253 if (vr->equiv) 254 bitmap_clear (vr->equiv); 255 } 256 257 /* Set value range VR to VR_VARYING. */ 258 259 void 260 set_value_range_to_varying (value_range *vr) 261 { 262 vr->type = VR_VARYING; 263 vr->min = vr->max = NULL_TREE; 264 if (vr->equiv) 265 bitmap_clear (vr->equiv); 266 } 267 268 /* Set value range VR to {T, MIN, MAX, EQUIV}. */ 269 270 void 271 set_value_range (value_range *vr, enum value_range_type t, tree min, 272 tree max, bitmap equiv) 273 { 274 /* Check the validity of the range. */ 275 if (flag_checking 276 && (t == VR_RANGE || t == VR_ANTI_RANGE)) 277 { 278 int cmp; 279 280 gcc_assert (min && max); 281 282 gcc_assert (!TREE_OVERFLOW_P (min) && !TREE_OVERFLOW_P (max)); 283 284 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE) 285 gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max)); 286 287 cmp = compare_values (min, max); 288 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); 289 } 290 291 if (flag_checking 292 && (t == VR_UNDEFINED || t == VR_VARYING)) 293 { 294 gcc_assert (min == NULL_TREE && max == NULL_TREE); 295 gcc_assert (equiv == NULL || bitmap_empty_p (equiv)); 296 } 297 298 vr->type = t; 299 vr->min = min; 300 vr->max = max; 301 302 /* Since updating the equivalence set involves deep copying the 303 bitmaps, only do it if absolutely necessary. 304 305 All equivalence bitmaps are allocated from the same obstack. So 306 we can use the obstack associated with EQUIV to allocate vr->equiv. */ 307 if (vr->equiv == NULL 308 && equiv != NULL) 309 vr->equiv = BITMAP_ALLOC (equiv->obstack); 310 311 if (equiv != vr->equiv) 312 { 313 if (equiv && !bitmap_empty_p (equiv)) 314 bitmap_copy (vr->equiv, equiv); 315 else 316 bitmap_clear (vr->equiv); 317 } 318 } 319 320 321 /* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}. 322 This means adjusting T, MIN and MAX representing the case of a 323 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX] 324 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges. 325 In corner cases where MAX+1 or MIN-1 wraps this will fall back 326 to varying. 327 This routine exists to ease canonicalization in the case where we 328 extract ranges from var + CST op limit. */ 329 330 void 331 set_and_canonicalize_value_range (value_range *vr, enum value_range_type t, 332 tree min, tree max, bitmap equiv) 333 { 334 /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ 335 if (t == VR_UNDEFINED) 336 { 337 set_value_range_to_undefined (vr); 338 return; 339 } 340 else if (t == VR_VARYING) 341 { 342 set_value_range_to_varying (vr); 343 return; 344 } 345 346 /* Nothing to canonicalize for symbolic ranges. */ 347 if (TREE_CODE (min) != INTEGER_CST 348 || TREE_CODE (max) != INTEGER_CST) 349 { 350 set_value_range (vr, t, min, max, equiv); 351 return; 352 } 353 354 /* Wrong order for min and max, to swap them and the VR type we need 355 to adjust them. */ 356 if (tree_int_cst_lt (max, min)) 357 { 358 tree one, tmp; 359 360 /* For one bit precision if max < min, then the swapped 361 range covers all values, so for VR_RANGE it is varying and 362 for VR_ANTI_RANGE empty range, so drop to varying as well. */ 363 if (TYPE_PRECISION (TREE_TYPE (min)) == 1) 364 { 365 set_value_range_to_varying (vr); 366 return; 367 } 368 369 one = build_int_cst (TREE_TYPE (min), 1); 370 tmp = int_const_binop (PLUS_EXPR, max, one); 371 max = int_const_binop (MINUS_EXPR, min, one); 372 min = tmp; 373 374 /* There's one corner case, if we had [C+1, C] before we now have 375 that again. But this represents an empty value range, so drop 376 to varying in this case. */ 377 if (tree_int_cst_lt (max, min)) 378 { 379 set_value_range_to_varying (vr); 380 return; 381 } 382 383 t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE; 384 } 385 386 /* Anti-ranges that can be represented as ranges should be so. */ 387 if (t == VR_ANTI_RANGE) 388 { 389 /* For -fstrict-enums we may receive out-of-range ranges so consider 390 values < -INF and values > INF as -INF/INF as well. */ 391 tree type = TREE_TYPE (min); 392 bool is_min = (INTEGRAL_TYPE_P (type) 393 && tree_int_cst_compare (min, TYPE_MIN_VALUE (type)) <= 0); 394 bool is_max = (INTEGRAL_TYPE_P (type) 395 && tree_int_cst_compare (max, TYPE_MAX_VALUE (type)) >= 0); 396 397 if (is_min && is_max) 398 { 399 /* We cannot deal with empty ranges, drop to varying. 400 ??? This could be VR_UNDEFINED instead. */ 401 set_value_range_to_varying (vr); 402 return; 403 } 404 else if (TYPE_PRECISION (TREE_TYPE (min)) == 1 405 && (is_min || is_max)) 406 { 407 /* Non-empty boolean ranges can always be represented 408 as a singleton range. */ 409 if (is_min) 410 min = max = vrp_val_max (TREE_TYPE (min)); 411 else 412 min = max = vrp_val_min (TREE_TYPE (min)); 413 t = VR_RANGE; 414 } 415 else if (is_min 416 /* As a special exception preserve non-null ranges. */ 417 && !(TYPE_UNSIGNED (TREE_TYPE (min)) 418 && integer_zerop (max))) 419 { 420 tree one = build_int_cst (TREE_TYPE (max), 1); 421 min = int_const_binop (PLUS_EXPR, max, one); 422 max = vrp_val_max (TREE_TYPE (max)); 423 t = VR_RANGE; 424 } 425 else if (is_max) 426 { 427 tree one = build_int_cst (TREE_TYPE (min), 1); 428 max = int_const_binop (MINUS_EXPR, min, one); 429 min = vrp_val_min (TREE_TYPE (min)); 430 t = VR_RANGE; 431 } 432 } 433 434 /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky 435 to make sure VRP iteration terminates, otherwise we can get into 436 oscillations. */ 437 438 set_value_range (vr, t, min, max, equiv); 439 } 440 441 /* Copy value range FROM into value range TO. */ 442 443 void 444 copy_value_range (value_range *to, value_range *from) 445 { 446 set_value_range (to, from->type, from->min, from->max, from->equiv); 447 } 448 449 /* Set value range VR to a single value. This function is only called 450 with values we get from statements, and exists to clear the 451 TREE_OVERFLOW flag. */ 452 453 void 454 set_value_range_to_value (value_range *vr, tree val, bitmap equiv) 455 { 456 gcc_assert (is_gimple_min_invariant (val)); 457 if (TREE_OVERFLOW_P (val)) 458 val = drop_tree_overflow (val); 459 set_value_range (vr, VR_RANGE, val, val, equiv); 460 } 461 462 /* Set value range VR to a non-NULL range of type TYPE. */ 463 464 void 465 set_value_range_to_nonnull (value_range *vr, tree type) 466 { 467 tree zero = build_int_cst (type, 0); 468 set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv); 469 } 470 471 472 /* Set value range VR to a NULL range of type TYPE. */ 473 474 void 475 set_value_range_to_null (value_range *vr, tree type) 476 { 477 set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv); 478 } 479 480 481 /* If abs (min) < abs (max), set VR to [-max, max], if 482 abs (min) >= abs (max), set VR to [-min, min]. */ 483 484 static void 485 abs_extent_range (value_range *vr, tree min, tree max) 486 { 487 int cmp; 488 489 gcc_assert (TREE_CODE (min) == INTEGER_CST); 490 gcc_assert (TREE_CODE (max) == INTEGER_CST); 491 gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min))); 492 gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min))); 493 min = fold_unary (ABS_EXPR, TREE_TYPE (min), min); 494 max = fold_unary (ABS_EXPR, TREE_TYPE (max), max); 495 if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max)) 496 { 497 set_value_range_to_varying (vr); 498 return; 499 } 500 cmp = compare_values (min, max); 501 if (cmp == -1) 502 min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max); 503 else if (cmp == 0 || cmp == 1) 504 { 505 max = min; 506 min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min); 507 } 508 else 509 { 510 set_value_range_to_varying (vr); 511 return; 512 } 513 set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); 514 } 515 516 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ 517 518 bool 519 vrp_operand_equal_p (const_tree val1, const_tree val2) 520 { 521 if (val1 == val2) 522 return true; 523 if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) 524 return false; 525 return true; 526 } 527 528 /* Return true, if the bitmaps B1 and B2 are equal. */ 529 530 bool 531 vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2) 532 { 533 return (b1 == b2 534 || ((!b1 || bitmap_empty_p (b1)) 535 && (!b2 || bitmap_empty_p (b2))) 536 || (b1 && b2 537 && bitmap_equal_p (b1, b2))); 538 } 539 540 /* Return true if VR is ~[0, 0]. */ 541 542 bool 543 range_is_nonnull (value_range *vr) 544 { 545 return vr->type == VR_ANTI_RANGE 546 && integer_zerop (vr->min) 547 && integer_zerop (vr->max); 548 } 549 550 551 /* Return true if VR is [0, 0]. */ 552 553 static inline bool 554 range_is_null (value_range *vr) 555 { 556 return vr->type == VR_RANGE 557 && integer_zerop (vr->min) 558 && integer_zerop (vr->max); 559 } 560 561 /* Return true if max and min of VR are INTEGER_CST. It's not necessary 562 a singleton. */ 563 564 bool 565 range_int_cst_p (value_range *vr) 566 { 567 return (vr->type == VR_RANGE 568 && TREE_CODE (vr->max) == INTEGER_CST 569 && TREE_CODE (vr->min) == INTEGER_CST); 570 } 571 572 /* Return true if VR is a INTEGER_CST singleton. */ 573 574 bool 575 range_int_cst_singleton_p (value_range *vr) 576 { 577 return (range_int_cst_p (vr) 578 && tree_int_cst_equal (vr->min, vr->max)); 579 } 580 581 /* Return true if value range VR involves at least one symbol. */ 582 583 bool 584 symbolic_range_p (value_range *vr) 585 { 586 return (!is_gimple_min_invariant (vr->min) 587 || !is_gimple_min_invariant (vr->max)); 588 } 589 590 /* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE 591 otherwise. We only handle additive operations and set NEG to true if the 592 symbol is negated and INV to the invariant part, if any. */ 593 594 tree 595 get_single_symbol (tree t, bool *neg, tree *inv) 596 { 597 bool neg_; 598 tree inv_; 599 600 *inv = NULL_TREE; 601 *neg = false; 602 603 if (TREE_CODE (t) == PLUS_EXPR 604 || TREE_CODE (t) == POINTER_PLUS_EXPR 605 || TREE_CODE (t) == MINUS_EXPR) 606 { 607 if (is_gimple_min_invariant (TREE_OPERAND (t, 0))) 608 { 609 neg_ = (TREE_CODE (t) == MINUS_EXPR); 610 inv_ = TREE_OPERAND (t, 0); 611 t = TREE_OPERAND (t, 1); 612 } 613 else if (is_gimple_min_invariant (TREE_OPERAND (t, 1))) 614 { 615 neg_ = false; 616 inv_ = TREE_OPERAND (t, 1); 617 t = TREE_OPERAND (t, 0); 618 } 619 else 620 return NULL_TREE; 621 } 622 else 623 { 624 neg_ = false; 625 inv_ = NULL_TREE; 626 } 627 628 if (TREE_CODE (t) == NEGATE_EXPR) 629 { 630 t = TREE_OPERAND (t, 0); 631 neg_ = !neg_; 632 } 633 634 if (TREE_CODE (t) != SSA_NAME) 635 return NULL_TREE; 636 637 if (inv_ && TREE_OVERFLOW_P (inv_)) 638 inv_ = drop_tree_overflow (inv_); 639 640 *neg = neg_; 641 *inv = inv_; 642 return t; 643 } 644 645 /* The reverse operation: build a symbolic expression with TYPE 646 from symbol SYM, negated according to NEG, and invariant INV. */ 647 648 static tree 649 build_symbolic_expr (tree type, tree sym, bool neg, tree inv) 650 { 651 const bool pointer_p = POINTER_TYPE_P (type); 652 tree t = sym; 653 654 if (neg) 655 t = build1 (NEGATE_EXPR, type, t); 656 657 if (integer_zerop (inv)) 658 return t; 659 660 return build2 (pointer_p ? POINTER_PLUS_EXPR : PLUS_EXPR, type, t, inv); 661 } 662 663 /* Return 664 1 if VAL < VAL2 665 0 if !(VAL < VAL2) 666 -2 if those are incomparable. */ 667 int 668 operand_less_p (tree val, tree val2) 669 { 670 /* LT is folded faster than GE and others. Inline the common case. */ 671 if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST) 672 return tree_int_cst_lt (val, val2); 673 else 674 { 675 tree tcmp; 676 677 fold_defer_overflow_warnings (); 678 679 tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2); 680 681 fold_undefer_and_ignore_overflow_warnings (); 682 683 if (!tcmp 684 || TREE_CODE (tcmp) != INTEGER_CST) 685 return -2; 686 687 if (!integer_zerop (tcmp)) 688 return 1; 689 } 690 691 return 0; 692 } 693 694 /* Compare two values VAL1 and VAL2. Return 695 696 -2 if VAL1 and VAL2 cannot be compared at compile-time, 697 -1 if VAL1 < VAL2, 698 0 if VAL1 == VAL2, 699 +1 if VAL1 > VAL2, and 700 +2 if VAL1 != VAL2 701 702 This is similar to tree_int_cst_compare but supports pointer values 703 and values that cannot be compared at compile time. 704 705 If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to 706 true if the return value is only valid if we assume that signed 707 overflow is undefined. */ 708 709 int 710 compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) 711 { 712 if (val1 == val2) 713 return 0; 714 715 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or 716 both integers. */ 717 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) 718 == POINTER_TYPE_P (TREE_TYPE (val2))); 719 720 /* Convert the two values into the same type. This is needed because 721 sizetype causes sign extension even for unsigned types. */ 722 val2 = fold_convert (TREE_TYPE (val1), val2); 723 STRIP_USELESS_TYPE_CONVERSION (val2); 724 725 const bool overflow_undefined 726 = INTEGRAL_TYPE_P (TREE_TYPE (val1)) 727 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)); 728 tree inv1, inv2; 729 bool neg1, neg2; 730 tree sym1 = get_single_symbol (val1, &neg1, &inv1); 731 tree sym2 = get_single_symbol (val2, &neg2, &inv2); 732 733 /* If VAL1 and VAL2 are of the form '[-]NAME [+ CST]', return -1 or +1 734 accordingly. If VAL1 and VAL2 don't use the same name, return -2. */ 735 if (sym1 && sym2) 736 { 737 /* Both values must use the same name with the same sign. */ 738 if (sym1 != sym2 || neg1 != neg2) 739 return -2; 740 741 /* [-]NAME + CST == [-]NAME + CST. */ 742 if (inv1 == inv2) 743 return 0; 744 745 /* If overflow is defined we cannot simplify more. */ 746 if (!overflow_undefined) 747 return -2; 748 749 if (strict_overflow_p != NULL 750 /* Symbolic range building sets TREE_NO_WARNING to declare 751 that overflow doesn't happen. */ 752 && (!inv1 || !TREE_NO_WARNING (val1)) 753 && (!inv2 || !TREE_NO_WARNING (val2))) 754 *strict_overflow_p = true; 755 756 if (!inv1) 757 inv1 = build_int_cst (TREE_TYPE (val1), 0); 758 if (!inv2) 759 inv2 = build_int_cst (TREE_TYPE (val2), 0); 760 761 return wi::cmp (wi::to_wide (inv1), wi::to_wide (inv2), 762 TYPE_SIGN (TREE_TYPE (val1))); 763 } 764 765 const bool cst1 = is_gimple_min_invariant (val1); 766 const bool cst2 = is_gimple_min_invariant (val2); 767 768 /* If one is of the form '[-]NAME + CST' and the other is constant, then 769 it might be possible to say something depending on the constants. */ 770 if ((sym1 && inv1 && cst2) || (sym2 && inv2 && cst1)) 771 { 772 if (!overflow_undefined) 773 return -2; 774 775 if (strict_overflow_p != NULL 776 /* Symbolic range building sets TREE_NO_WARNING to declare 777 that overflow doesn't happen. */ 778 && (!sym1 || !TREE_NO_WARNING (val1)) 779 && (!sym2 || !TREE_NO_WARNING (val2))) 780 *strict_overflow_p = true; 781 782 const signop sgn = TYPE_SIGN (TREE_TYPE (val1)); 783 tree cst = cst1 ? val1 : val2; 784 tree inv = cst1 ? inv2 : inv1; 785 786 /* Compute the difference between the constants. If it overflows or 787 underflows, this means that we can trivially compare the NAME with 788 it and, consequently, the two values with each other. */ 789 wide_int diff = wi::to_wide (cst) - wi::to_wide (inv); 790 if (wi::cmp (0, wi::to_wide (inv), sgn) 791 != wi::cmp (diff, wi::to_wide (cst), sgn)) 792 { 793 const int res = wi::cmp (wi::to_wide (cst), wi::to_wide (inv), sgn); 794 return cst1 ? res : -res; 795 } 796 797 return -2; 798 } 799 800 /* We cannot say anything more for non-constants. */ 801 if (!cst1 || !cst2) 802 return -2; 803 804 if (!POINTER_TYPE_P (TREE_TYPE (val1))) 805 { 806 /* We cannot compare overflowed values. */ 807 if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) 808 return -2; 809 810 if (TREE_CODE (val1) == INTEGER_CST 811 && TREE_CODE (val2) == INTEGER_CST) 812 return tree_int_cst_compare (val1, val2); 813 814 if (poly_int_tree_p (val1) && poly_int_tree_p (val2)) 815 { 816 if (known_eq (wi::to_poly_widest (val1), 817 wi::to_poly_widest (val2))) 818 return 0; 819 if (known_lt (wi::to_poly_widest (val1), 820 wi::to_poly_widest (val2))) 821 return -1; 822 if (known_gt (wi::to_poly_widest (val1), 823 wi::to_poly_widest (val2))) 824 return 1; 825 } 826 827 return -2; 828 } 829 else 830 { 831 tree t; 832 833 /* First see if VAL1 and VAL2 are not the same. */ 834 if (val1 == val2 || operand_equal_p (val1, val2, 0)) 835 return 0; 836 837 /* If VAL1 is a lower address than VAL2, return -1. */ 838 if (operand_less_p (val1, val2) == 1) 839 return -1; 840 841 /* If VAL1 is a higher address than VAL2, return +1. */ 842 if (operand_less_p (val2, val1) == 1) 843 return 1; 844 845 /* If VAL1 is different than VAL2, return +2. 846 For integer constants we either have already returned -1 or 1 847 or they are equivalent. We still might succeed in proving 848 something about non-trivial operands. */ 849 if (TREE_CODE (val1) != INTEGER_CST 850 || TREE_CODE (val2) != INTEGER_CST) 851 { 852 t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2); 853 if (t && integer_onep (t)) 854 return 2; 855 } 856 857 return -2; 858 } 859 } 860 861 /* Compare values like compare_values_warnv. */ 862 863 int 864 compare_values (tree val1, tree val2) 865 { 866 bool sop; 867 return compare_values_warnv (val1, val2, &sop); 868 } 869 870 871 /* Return 1 if VAL is inside value range MIN <= VAL <= MAX, 872 0 if VAL is not inside [MIN, MAX], 873 -2 if we cannot tell either way. 874 875 Benchmark compile/20001226-1.c compilation time after changing this 876 function. */ 877 878 int 879 value_inside_range (tree val, tree min, tree max) 880 { 881 int cmp1, cmp2; 882 883 cmp1 = operand_less_p (val, min); 884 if (cmp1 == -2) 885 return -2; 886 if (cmp1 == 1) 887 return 0; 888 889 cmp2 = operand_less_p (max, val); 890 if (cmp2 == -2) 891 return -2; 892 893 return !cmp2; 894 } 895 896 897 /* Return true if value ranges VR0 and VR1 have a non-empty 898 intersection. 899 900 Benchmark compile/20001226-1.c compilation time after changing this 901 function. 902 */ 903 904 static inline bool 905 value_ranges_intersect_p (value_range *vr0, value_range *vr1) 906 { 907 /* The value ranges do not intersect if the maximum of the first range is 908 less than the minimum of the second range or vice versa. 909 When those relations are unknown, we can't do any better. */ 910 if (operand_less_p (vr0->max, vr1->min) != 0) 911 return false; 912 if (operand_less_p (vr1->max, vr0->min) != 0) 913 return false; 914 return true; 915 } 916 917 918 /* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not 919 include the value zero, -2 if we cannot tell. */ 920 921 int 922 range_includes_zero_p (tree min, tree max) 923 { 924 tree zero = build_int_cst (TREE_TYPE (min), 0); 925 return value_inside_range (zero, min, max); 926 } 927 928 /* Return true if *VR is know to only contain nonnegative values. */ 929 930 static inline bool 931 value_range_nonnegative_p (value_range *vr) 932 { 933 /* Testing for VR_ANTI_RANGE is not useful here as any anti-range 934 which would return a useful value should be encoded as a 935 VR_RANGE. */ 936 if (vr->type == VR_RANGE) 937 { 938 int result = compare_values (vr->min, integer_zero_node); 939 return (result == 0 || result == 1); 940 } 941 942 return false; 943 } 944 945 /* If *VR has a value rante that is a single constant value return that, 946 otherwise return NULL_TREE. */ 947 948 tree 949 value_range_constant_singleton (value_range *vr) 950 { 951 if (vr->type == VR_RANGE 952 && vrp_operand_equal_p (vr->min, vr->max) 953 && is_gimple_min_invariant (vr->min)) 954 return vr->min; 955 956 return NULL_TREE; 957 } 958 959 /* Wrapper around int_const_binop. Return true if we can compute the 960 result; i.e. if the operation doesn't overflow or if the overflow is 961 undefined. In the latter case (if the operation overflows and 962 overflow is undefined), then adjust the result to be -INF or +INF 963 depending on CODE, VAL1 and VAL2. Return the value in *RES. 964 965 Return false for division by zero, for which the result is 966 indeterminate. */ 967 968 static bool 969 vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) 970 { 971 bool overflow = false; 972 signop sign = TYPE_SIGN (TREE_TYPE (val1)); 973 974 switch (code) 975 { 976 case RSHIFT_EXPR: 977 case LSHIFT_EXPR: 978 { 979 wide_int wval2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); 980 if (wi::neg_p (wval2)) 981 { 982 wval2 = -wval2; 983 if (code == RSHIFT_EXPR) 984 code = LSHIFT_EXPR; 985 else 986 code = RSHIFT_EXPR; 987 } 988 989 if (code == RSHIFT_EXPR) 990 /* It's unclear from the C standard whether shifts can overflow. 991 The following code ignores overflow; perhaps a C standard 992 interpretation ruling is needed. */ 993 *res = wi::rshift (wi::to_wide (val1), wval2, sign); 994 else 995 *res = wi::lshift (wi::to_wide (val1), wval2); 996 break; 997 } 998 999 case MULT_EXPR: 1000 *res = wi::mul (wi::to_wide (val1), 1001 wi::to_wide (val2), sign, &overflow); 1002 break; 1003 1004 case TRUNC_DIV_EXPR: 1005 case EXACT_DIV_EXPR: 1006 if (val2 == 0) 1007 return false; 1008 else 1009 *res = wi::div_trunc (wi::to_wide (val1), 1010 wi::to_wide (val2), sign, &overflow); 1011 break; 1012 1013 case FLOOR_DIV_EXPR: 1014 if (val2 == 0) 1015 return false; 1016 *res = wi::div_floor (wi::to_wide (val1), 1017 wi::to_wide (val2), sign, &overflow); 1018 break; 1019 1020 case CEIL_DIV_EXPR: 1021 if (val2 == 0) 1022 return false; 1023 *res = wi::div_ceil (wi::to_wide (val1), 1024 wi::to_wide (val2), sign, &overflow); 1025 break; 1026 1027 case ROUND_DIV_EXPR: 1028 if (val2 == 0) 1029 return false; 1030 *res = wi::div_round (wi::to_wide (val1), 1031 wi::to_wide (val2), sign, &overflow); 1032 break; 1033 1034 default: 1035 gcc_unreachable (); 1036 } 1037 1038 if (overflow 1039 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) 1040 { 1041 /* If the operation overflowed return -INF or +INF depending 1042 on the operation and the combination of signs of the operands. */ 1043 int sgn1 = tree_int_cst_sgn (val1); 1044 int sgn2 = tree_int_cst_sgn (val2); 1045 1046 /* Notice that we only need to handle the restricted set of 1047 operations handled by extract_range_from_binary_expr. 1048 Among them, only multiplication, addition and subtraction 1049 can yield overflow without overflown operands because we 1050 are working with integral types only... except in the 1051 case VAL1 = -INF and VAL2 = -1 which overflows to +INF 1052 for division too. */ 1053 1054 /* For multiplication, the sign of the overflow is given 1055 by the comparison of the signs of the operands. */ 1056 if ((code == MULT_EXPR && sgn1 == sgn2) 1057 /* For addition, the operands must be of the same sign 1058 to yield an overflow. Its sign is therefore that 1059 of one of the operands, for example the first. */ 1060 || (code == PLUS_EXPR && sgn1 >= 0) 1061 /* For subtraction, operands must be of 1062 different signs to yield an overflow. Its sign is 1063 therefore that of the first operand or the opposite of 1064 that of the second operand. A first operand of 0 counts 1065 as positive here, for the corner case 0 - (-INF), which 1066 overflows, but must yield +INF. */ 1067 || (code == MINUS_EXPR && sgn1 >= 0) 1068 /* For division, the only case is -INF / -1 = +INF. */ 1069 || code == TRUNC_DIV_EXPR 1070 || code == FLOOR_DIV_EXPR 1071 || code == CEIL_DIV_EXPR 1072 || code == EXACT_DIV_EXPR 1073 || code == ROUND_DIV_EXPR) 1074 *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), 1075 TYPE_SIGN (TREE_TYPE (val1))); 1076 else 1077 *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), 1078 TYPE_SIGN (TREE_TYPE (val1))); 1079 return true; 1080 } 1081 1082 return !overflow; 1083 } 1084 1085 1086 /* For range VR compute two wide_int bitmasks. In *MAY_BE_NONZERO 1087 bitmask if some bit is unset, it means for all numbers in the range 1088 the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO 1089 bitmask if some bit is set, it means for all numbers in the range 1090 the bit is 1, otherwise it might be 0 or 1. */ 1091 1092 bool 1093 zero_nonzero_bits_from_vr (const tree expr_type, 1094 value_range *vr, 1095 wide_int *may_be_nonzero, 1096 wide_int *must_be_nonzero) 1097 { 1098 *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); 1099 *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); 1100 if (!range_int_cst_p (vr)) 1101 return false; 1102 1103 if (range_int_cst_singleton_p (vr)) 1104 { 1105 *may_be_nonzero = wi::to_wide (vr->min); 1106 *must_be_nonzero = *may_be_nonzero; 1107 } 1108 else if (tree_int_cst_sgn (vr->min) >= 0 1109 || tree_int_cst_sgn (vr->max) < 0) 1110 { 1111 wide_int xor_mask = wi::to_wide (vr->min) ^ wi::to_wide (vr->max); 1112 *may_be_nonzero = wi::to_wide (vr->min) | wi::to_wide (vr->max); 1113 *must_be_nonzero = wi::to_wide (vr->min) & wi::to_wide (vr->max); 1114 if (xor_mask != 0) 1115 { 1116 wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, 1117 may_be_nonzero->get_precision ()); 1118 *may_be_nonzero = *may_be_nonzero | mask; 1119 *must_be_nonzero = wi::bit_and_not (*must_be_nonzero, mask); 1120 } 1121 } 1122 1123 return true; 1124 } 1125 1126 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR 1127 so that *VR0 U *VR1 == *AR. Returns true if that is possible, 1128 false otherwise. If *AR can be represented with a single range 1129 *VR1 will be VR_UNDEFINED. */ 1130 1131 static bool 1132 ranges_from_anti_range (value_range *ar, 1133 value_range *vr0, value_range *vr1) 1134 { 1135 tree type = TREE_TYPE (ar->min); 1136 1137 vr0->type = VR_UNDEFINED; 1138 vr1->type = VR_UNDEFINED; 1139 1140 if (ar->type != VR_ANTI_RANGE 1141 || TREE_CODE (ar->min) != INTEGER_CST 1142 || TREE_CODE (ar->max) != INTEGER_CST 1143 || !vrp_val_min (type) 1144 || !vrp_val_max (type)) 1145 return false; 1146 1147 if (!vrp_val_is_min (ar->min)) 1148 { 1149 vr0->type = VR_RANGE; 1150 vr0->min = vrp_val_min (type); 1151 vr0->max = wide_int_to_tree (type, wi::to_wide (ar->min) - 1); 1152 } 1153 if (!vrp_val_is_max (ar->max)) 1154 { 1155 vr1->type = VR_RANGE; 1156 vr1->min = wide_int_to_tree (type, wi::to_wide (ar->max) + 1); 1157 vr1->max = vrp_val_max (type); 1158 } 1159 if (vr0->type == VR_UNDEFINED) 1160 { 1161 *vr0 = *vr1; 1162 vr1->type = VR_UNDEFINED; 1163 } 1164 1165 return vr0->type != VR_UNDEFINED; 1166 } 1167 1168 /* Helper to extract a value-range *VR for a multiplicative operation 1169 *VR0 CODE *VR1. */ 1170 1171 static void 1172 extract_range_from_multiplicative_op_1 (value_range *vr, 1173 enum tree_code code, 1174 value_range *vr0, value_range *vr1) 1175 { 1176 enum value_range_type rtype; 1177 wide_int val, min, max; 1178 tree type; 1179 1180 /* Multiplications, divisions and shifts are a bit tricky to handle, 1181 depending on the mix of signs we have in the two ranges, we 1182 need to operate on different values to get the minimum and 1183 maximum values for the new range. One approach is to figure 1184 out all the variations of range combinations and do the 1185 operations. 1186 1187 However, this involves several calls to compare_values and it 1188 is pretty convoluted. It's simpler to do the 4 operations 1189 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP 1190 MAX1) and then figure the smallest and largest values to form 1191 the new range. */ 1192 gcc_assert (code == MULT_EXPR 1193 || code == TRUNC_DIV_EXPR 1194 || code == FLOOR_DIV_EXPR 1195 || code == CEIL_DIV_EXPR 1196 || code == EXACT_DIV_EXPR 1197 || code == ROUND_DIV_EXPR 1198 || code == RSHIFT_EXPR 1199 || code == LSHIFT_EXPR); 1200 gcc_assert (vr0->type == VR_RANGE 1201 && vr0->type == vr1->type); 1202 1203 rtype = vr0->type; 1204 type = TREE_TYPE (vr0->min); 1205 signop sgn = TYPE_SIGN (type); 1206 1207 /* Compute the 4 cross operations and their minimum and maximum value. */ 1208 if (!vrp_int_const_binop (code, vr0->min, vr1->min, &val)) 1209 { 1210 set_value_range_to_varying (vr); 1211 return; 1212 } 1213 min = max = val; 1214 1215 if (vr1->max != vr1->min) 1216 { 1217 if (!vrp_int_const_binop (code, vr0->min, vr1->max, &val)) 1218 { 1219 set_value_range_to_varying (vr); 1220 return; 1221 } 1222 if (wi::lt_p (val, min, sgn)) 1223 min = val; 1224 else if (wi::gt_p (val, max, sgn)) 1225 max = val; 1226 } 1227 1228 if (vr0->max != vr0->min) 1229 { 1230 if (!vrp_int_const_binop (code, vr0->max, vr1->min, &val)) 1231 { 1232 set_value_range_to_varying (vr); 1233 return; 1234 } 1235 if (wi::lt_p (val, min, sgn)) 1236 min = val; 1237 else if (wi::gt_p (val, max, sgn)) 1238 max = val; 1239 } 1240 1241 if (vr0->min != vr0->max && vr1->min != vr1->max) 1242 { 1243 if (!vrp_int_const_binop (code, vr0->max, vr1->max, &val)) 1244 { 1245 set_value_range_to_varying (vr); 1246 return; 1247 } 1248 if (wi::lt_p (val, min, sgn)) 1249 min = val; 1250 else if (wi::gt_p (val, max, sgn)) 1251 max = val; 1252 } 1253 1254 /* If the new range has its limits swapped around (MIN > MAX), 1255 then the operation caused one of them to wrap around, mark 1256 the new range VARYING. */ 1257 if (wi::gt_p (min, max, sgn)) 1258 { 1259 set_value_range_to_varying (vr); 1260 return; 1261 } 1262 1263 /* We punt for [-INF, +INF]. 1264 We learn nothing when we have INF on both sides. 1265 Note that we do accept [-INF, -INF] and [+INF, +INF]. */ 1266 if (wi::eq_p (min, wi::min_value (TYPE_PRECISION (type), sgn)) 1267 && wi::eq_p (max, wi::max_value (TYPE_PRECISION (type), sgn))) 1268 { 1269 set_value_range_to_varying (vr); 1270 return; 1271 } 1272 1273 set_value_range (vr, rtype, 1274 wide_int_to_tree (type, min), 1275 wide_int_to_tree (type, max), NULL); 1276 } 1277 1278 /* Extract range information from a binary operation CODE based on 1279 the ranges of each of its operands *VR0 and *VR1 with resulting 1280 type EXPR_TYPE. The resulting range is stored in *VR. */ 1281 1282 void 1283 extract_range_from_binary_expr_1 (value_range *vr, 1284 enum tree_code code, tree expr_type, 1285 value_range *vr0_, value_range *vr1_) 1286 { 1287 value_range vr0 = *vr0_, vr1 = *vr1_; 1288 value_range vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER; 1289 enum value_range_type type; 1290 tree min = NULL_TREE, max = NULL_TREE; 1291 int cmp; 1292 1293 if (!INTEGRAL_TYPE_P (expr_type) 1294 && !POINTER_TYPE_P (expr_type)) 1295 { 1296 set_value_range_to_varying (vr); 1297 return; 1298 } 1299 1300 /* Not all binary expressions can be applied to ranges in a 1301 meaningful way. Handle only arithmetic operations. */ 1302 if (code != PLUS_EXPR 1303 && code != MINUS_EXPR 1304 && code != POINTER_PLUS_EXPR 1305 && code != MULT_EXPR 1306 && code != TRUNC_DIV_EXPR 1307 && code != FLOOR_DIV_EXPR 1308 && code != CEIL_DIV_EXPR 1309 && code != EXACT_DIV_EXPR 1310 && code != ROUND_DIV_EXPR 1311 && code != TRUNC_MOD_EXPR 1312 && code != RSHIFT_EXPR 1313 && code != LSHIFT_EXPR 1314 && code != MIN_EXPR 1315 && code != MAX_EXPR 1316 && code != BIT_AND_EXPR 1317 && code != BIT_IOR_EXPR 1318 && code != BIT_XOR_EXPR) 1319 { 1320 set_value_range_to_varying (vr); 1321 return; 1322 } 1323 1324 /* If both ranges are UNDEFINED, so is the result. */ 1325 if (vr0.type == VR_UNDEFINED && vr1.type == VR_UNDEFINED) 1326 { 1327 set_value_range_to_undefined (vr); 1328 return; 1329 } 1330 /* If one of the ranges is UNDEFINED drop it to VARYING for the following 1331 code. At some point we may want to special-case operations that 1332 have UNDEFINED result for all or some value-ranges of the not UNDEFINED 1333 operand. */ 1334 else if (vr0.type == VR_UNDEFINED) 1335 set_value_range_to_varying (&vr0); 1336 else if (vr1.type == VR_UNDEFINED) 1337 set_value_range_to_varying (&vr1); 1338 1339 /* We get imprecise results from ranges_from_anti_range when 1340 code is EXACT_DIV_EXPR. We could mask out bits in the resulting 1341 range, but then we also need to hack up vrp_meet. It's just 1342 easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR. */ 1343 if (code == EXACT_DIV_EXPR 1344 && vr0.type == VR_ANTI_RANGE 1345 && vr0.min == vr0.max 1346 && integer_zerop (vr0.min)) 1347 { 1348 set_value_range_to_nonnull (vr, expr_type); 1349 return; 1350 } 1351 1352 /* Now canonicalize anti-ranges to ranges when they are not symbolic 1353 and express ~[] op X as ([]' op X) U ([]'' op X). */ 1354 if (vr0.type == VR_ANTI_RANGE 1355 && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1)) 1356 { 1357 extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_); 1358 if (vrtem1.type != VR_UNDEFINED) 1359 { 1360 value_range vrres = VR_INITIALIZER; 1361 extract_range_from_binary_expr_1 (&vrres, code, expr_type, 1362 &vrtem1, vr1_); 1363 vrp_meet (vr, &vrres); 1364 } 1365 return; 1366 } 1367 /* Likewise for X op ~[]. */ 1368 if (vr1.type == VR_ANTI_RANGE 1369 && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1)) 1370 { 1371 extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0); 1372 if (vrtem1.type != VR_UNDEFINED) 1373 { 1374 value_range vrres = VR_INITIALIZER; 1375 extract_range_from_binary_expr_1 (&vrres, code, expr_type, 1376 vr0_, &vrtem1); 1377 vrp_meet (vr, &vrres); 1378 } 1379 return; 1380 } 1381 1382 /* The type of the resulting value range defaults to VR0.TYPE. */ 1383 type = vr0.type; 1384 1385 /* Refuse to operate on VARYING ranges, ranges of different kinds 1386 and symbolic ranges. As an exception, we allow BIT_{AND,IOR} 1387 because we may be able to derive a useful range even if one of 1388 the operands is VR_VARYING or symbolic range. Similarly for 1389 divisions, MIN/MAX and PLUS/MINUS. 1390 1391 TODO, we may be able to derive anti-ranges in some cases. */ 1392 if (code != BIT_AND_EXPR 1393 && code != BIT_IOR_EXPR 1394 && code != TRUNC_DIV_EXPR 1395 && code != FLOOR_DIV_EXPR 1396 && code != CEIL_DIV_EXPR 1397 && code != EXACT_DIV_EXPR 1398 && code != ROUND_DIV_EXPR 1399 && code != TRUNC_MOD_EXPR 1400 && code != MIN_EXPR 1401 && code != MAX_EXPR 1402 && code != PLUS_EXPR 1403 && code != MINUS_EXPR 1404 && code != RSHIFT_EXPR 1405 && (vr0.type == VR_VARYING 1406 || vr1.type == VR_VARYING 1407 || vr0.type != vr1.type 1408 || symbolic_range_p (&vr0) 1409 || symbolic_range_p (&vr1))) 1410 { 1411 set_value_range_to_varying (vr); 1412 return; 1413 } 1414 1415 /* Now evaluate the expression to determine the new range. */ 1416 if (POINTER_TYPE_P (expr_type)) 1417 { 1418 if (code == MIN_EXPR || code == MAX_EXPR) 1419 { 1420 /* For MIN/MAX expressions with pointers, we only care about 1421 nullness, if both are non null, then the result is nonnull. 1422 If both are null, then the result is null. Otherwise they 1423 are varying. */ 1424 if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1)) 1425 set_value_range_to_nonnull (vr, expr_type); 1426 else if (range_is_null (&vr0) && range_is_null (&vr1)) 1427 set_value_range_to_null (vr, expr_type); 1428 else 1429 set_value_range_to_varying (vr); 1430 } 1431 else if (code == POINTER_PLUS_EXPR) 1432 { 1433 /* For pointer types, we are really only interested in asserting 1434 whether the expression evaluates to non-NULL. */ 1435 if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1)) 1436 set_value_range_to_nonnull (vr, expr_type); 1437 else if (range_is_null (&vr0) && range_is_null (&vr1)) 1438 set_value_range_to_null (vr, expr_type); 1439 else 1440 set_value_range_to_varying (vr); 1441 } 1442 else if (code == BIT_AND_EXPR) 1443 { 1444 /* For pointer types, we are really only interested in asserting 1445 whether the expression evaluates to non-NULL. */ 1446 if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1)) 1447 set_value_range_to_nonnull (vr, expr_type); 1448 else if (range_is_null (&vr0) || range_is_null (&vr1)) 1449 set_value_range_to_null (vr, expr_type); 1450 else 1451 set_value_range_to_varying (vr); 1452 } 1453 else 1454 set_value_range_to_varying (vr); 1455 1456 return; 1457 } 1458 1459 /* For integer ranges, apply the operation to each end of the 1460 range and see what we end up with. */ 1461 if (code == PLUS_EXPR || code == MINUS_EXPR) 1462 { 1463 const bool minus_p = (code == MINUS_EXPR); 1464 tree min_op0 = vr0.min; 1465 tree min_op1 = minus_p ? vr1.max : vr1.min; 1466 tree max_op0 = vr0.max; 1467 tree max_op1 = minus_p ? vr1.min : vr1.max; 1468 tree sym_min_op0 = NULL_TREE; 1469 tree sym_min_op1 = NULL_TREE; 1470 tree sym_max_op0 = NULL_TREE; 1471 tree sym_max_op1 = NULL_TREE; 1472 bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1; 1473 1474 /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or 1475 single-symbolic ranges, try to compute the precise resulting range, 1476 but only if we know that this resulting range will also be constant 1477 or single-symbolic. */ 1478 if (vr0.type == VR_RANGE && vr1.type == VR_RANGE 1479 && (TREE_CODE (min_op0) == INTEGER_CST 1480 || (sym_min_op0 1481 = get_single_symbol (min_op0, &neg_min_op0, &min_op0))) 1482 && (TREE_CODE (min_op1) == INTEGER_CST 1483 || (sym_min_op1 1484 = get_single_symbol (min_op1, &neg_min_op1, &min_op1))) 1485 && (!(sym_min_op0 && sym_min_op1) 1486 || (sym_min_op0 == sym_min_op1 1487 && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1))) 1488 && (TREE_CODE (max_op0) == INTEGER_CST 1489 || (sym_max_op0 1490 = get_single_symbol (max_op0, &neg_max_op0, &max_op0))) 1491 && (TREE_CODE (max_op1) == INTEGER_CST 1492 || (sym_max_op1 1493 = get_single_symbol (max_op1, &neg_max_op1, &max_op1))) 1494 && (!(sym_max_op0 && sym_max_op1) 1495 || (sym_max_op0 == sym_max_op1 1496 && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1)))) 1497 { 1498 const signop sgn = TYPE_SIGN (expr_type); 1499 const unsigned int prec = TYPE_PRECISION (expr_type); 1500 wide_int type_min, type_max, wmin, wmax; 1501 int min_ovf = 0; 1502 int max_ovf = 0; 1503 1504 /* Get the lower and upper bounds of the type. */ 1505 if (TYPE_OVERFLOW_WRAPS (expr_type)) 1506 { 1507 type_min = wi::min_value (prec, sgn); 1508 type_max = wi::max_value (prec, sgn); 1509 } 1510 else 1511 { 1512 type_min = wi::to_wide (vrp_val_min (expr_type)); 1513 type_max = wi::to_wide (vrp_val_max (expr_type)); 1514 } 1515 1516 /* Combine the lower bounds, if any. */ 1517 if (min_op0 && min_op1) 1518 { 1519 if (minus_p) 1520 { 1521 wmin = wi::to_wide (min_op0) - wi::to_wide (min_op1); 1522 1523 /* Check for overflow. */ 1524 if (wi::cmp (0, wi::to_wide (min_op1), sgn) 1525 != wi::cmp (wmin, wi::to_wide (min_op0), sgn)) 1526 min_ovf = wi::cmp (wi::to_wide (min_op0), 1527 wi::to_wide (min_op1), sgn); 1528 } 1529 else 1530 { 1531 wmin = wi::to_wide (min_op0) + wi::to_wide (min_op1); 1532 1533 /* Check for overflow. */ 1534 if (wi::cmp (wi::to_wide (min_op1), 0, sgn) 1535 != wi::cmp (wmin, wi::to_wide (min_op0), sgn)) 1536 min_ovf = wi::cmp (wi::to_wide (min_op0), wmin, sgn); 1537 } 1538 } 1539 else if (min_op0) 1540 wmin = wi::to_wide (min_op0); 1541 else if (min_op1) 1542 { 1543 if (minus_p) 1544 { 1545 wmin = -wi::to_wide (min_op1); 1546 1547 /* Check for overflow. */ 1548 if (sgn == SIGNED 1549 && wi::neg_p (wi::to_wide (min_op1)) 1550 && wi::neg_p (wmin)) 1551 min_ovf = 1; 1552 else if (sgn == UNSIGNED && wi::to_wide (min_op1) != 0) 1553 min_ovf = -1; 1554 } 1555 else 1556 wmin = wi::to_wide (min_op1); 1557 } 1558 else 1559 wmin = wi::shwi (0, prec); 1560 1561 /* Combine the upper bounds, if any. */ 1562 if (max_op0 && max_op1) 1563 { 1564 if (minus_p) 1565 { 1566 wmax = wi::to_wide (max_op0) - wi::to_wide (max_op1); 1567 1568 /* Check for overflow. */ 1569 if (wi::cmp (0, wi::to_wide (max_op1), sgn) 1570 != wi::cmp (wmax, wi::to_wide (max_op0), sgn)) 1571 max_ovf = wi::cmp (wi::to_wide (max_op0), 1572 wi::to_wide (max_op1), sgn); 1573 } 1574 else 1575 { 1576 wmax = wi::to_wide (max_op0) + wi::to_wide (max_op1); 1577 1578 if (wi::cmp (wi::to_wide (max_op1), 0, sgn) 1579 != wi::cmp (wmax, wi::to_wide (max_op0), sgn)) 1580 max_ovf = wi::cmp (wi::to_wide (max_op0), wmax, sgn); 1581 } 1582 } 1583 else if (max_op0) 1584 wmax = wi::to_wide (max_op0); 1585 else if (max_op1) 1586 { 1587 if (minus_p) 1588 { 1589 wmax = -wi::to_wide (max_op1); 1590 1591 /* Check for overflow. */ 1592 if (sgn == SIGNED 1593 && wi::neg_p (wi::to_wide (max_op1)) 1594 && wi::neg_p (wmax)) 1595 max_ovf = 1; 1596 else if (sgn == UNSIGNED && wi::to_wide (max_op1) != 0) 1597 max_ovf = -1; 1598 } 1599 else 1600 wmax = wi::to_wide (max_op1); 1601 } 1602 else 1603 wmax = wi::shwi (0, prec); 1604 1605 /* Check for type overflow. */ 1606 if (min_ovf == 0) 1607 { 1608 if (wi::cmp (wmin, type_min, sgn) == -1) 1609 min_ovf = -1; 1610 else if (wi::cmp (wmin, type_max, sgn) == 1) 1611 min_ovf = 1; 1612 } 1613 if (max_ovf == 0) 1614 { 1615 if (wi::cmp (wmax, type_min, sgn) == -1) 1616 max_ovf = -1; 1617 else if (wi::cmp (wmax, type_max, sgn) == 1) 1618 max_ovf = 1; 1619 } 1620 1621 /* If the resulting range will be symbolic, we need to eliminate any 1622 explicit or implicit overflow introduced in the above computation 1623 because compare_values could make an incorrect use of it. That's 1624 why we require one of the ranges to be a singleton. */ 1625 if ((sym_min_op0 != sym_min_op1 || sym_max_op0 != sym_max_op1) 1626 && (min_ovf || max_ovf 1627 || (min_op0 != max_op0 && min_op1 != max_op1))) 1628 { 1629 set_value_range_to_varying (vr); 1630 return; 1631 } 1632 1633 if (TYPE_OVERFLOW_WRAPS (expr_type)) 1634 { 1635 /* If overflow wraps, truncate the values and adjust the 1636 range kind and bounds appropriately. */ 1637 wide_int tmin = wide_int::from (wmin, prec, sgn); 1638 wide_int tmax = wide_int::from (wmax, prec, sgn); 1639 if (min_ovf == max_ovf) 1640 { 1641 /* No overflow or both overflow or underflow. The 1642 range kind stays VR_RANGE. */ 1643 min = wide_int_to_tree (expr_type, tmin); 1644 max = wide_int_to_tree (expr_type, tmax); 1645 } 1646 else if ((min_ovf == -1 && max_ovf == 0) 1647 || (max_ovf == 1 && min_ovf == 0)) 1648 { 1649 /* Min underflow or max overflow. The range kind 1650 changes to VR_ANTI_RANGE. */ 1651 bool covers = false; 1652 wide_int tem = tmin; 1653 type = VR_ANTI_RANGE; 1654 tmin = tmax + 1; 1655 if (wi::cmp (tmin, tmax, sgn) < 0) 1656 covers = true; 1657 tmax = tem - 1; 1658 if (wi::cmp (tmax, tem, sgn) > 0) 1659 covers = true; 1660 /* If the anti-range would cover nothing, drop to varying. 1661 Likewise if the anti-range bounds are outside of the 1662 types values. */ 1663 if (covers || wi::cmp (tmin, tmax, sgn) > 0) 1664 { 1665 set_value_range_to_varying (vr); 1666 return; 1667 } 1668 min = wide_int_to_tree (expr_type, tmin); 1669 max = wide_int_to_tree (expr_type, tmax); 1670 } 1671 else 1672 { 1673 /* Other underflow and/or overflow, drop to VR_VARYING. */ 1674 set_value_range_to_varying (vr); 1675 return; 1676 } 1677 } 1678 else 1679 { 1680 /* If overflow does not wrap, saturate to the types min/max 1681 value. */ 1682 if (min_ovf == -1) 1683 min = wide_int_to_tree (expr_type, type_min); 1684 else if (min_ovf == 1) 1685 min = wide_int_to_tree (expr_type, type_max); 1686 else 1687 min = wide_int_to_tree (expr_type, wmin); 1688 1689 if (max_ovf == -1) 1690 max = wide_int_to_tree (expr_type, type_min); 1691 else if (max_ovf == 1) 1692 max = wide_int_to_tree (expr_type, type_max); 1693 else 1694 max = wide_int_to_tree (expr_type, wmax); 1695 } 1696 1697 /* If the result lower bound is constant, we're done; 1698 otherwise, build the symbolic lower bound. */ 1699 if (sym_min_op0 == sym_min_op1) 1700 ; 1701 else if (sym_min_op0) 1702 min = build_symbolic_expr (expr_type, sym_min_op0, 1703 neg_min_op0, min); 1704 else if (sym_min_op1) 1705 { 1706 /* We may not negate if that might introduce 1707 undefined overflow. */ 1708 if (! minus_p 1709 || neg_min_op1 1710 || TYPE_OVERFLOW_WRAPS (expr_type)) 1711 min = build_symbolic_expr (expr_type, sym_min_op1, 1712 neg_min_op1 ^ minus_p, min); 1713 else 1714 min = NULL_TREE; 1715 } 1716 1717 /* Likewise for the upper bound. */ 1718 if (sym_max_op0 == sym_max_op1) 1719 ; 1720 else if (sym_max_op0) 1721 max = build_symbolic_expr (expr_type, sym_max_op0, 1722 neg_max_op0, max); 1723 else if (sym_max_op1) 1724 { 1725 /* We may not negate if that might introduce 1726 undefined overflow. */ 1727 if (! minus_p 1728 || neg_max_op1 1729 || TYPE_OVERFLOW_WRAPS (expr_type)) 1730 max = build_symbolic_expr (expr_type, sym_max_op1, 1731 neg_max_op1 ^ minus_p, max); 1732 else 1733 max = NULL_TREE; 1734 } 1735 } 1736 else 1737 { 1738 /* For other cases, for example if we have a PLUS_EXPR with two 1739 VR_ANTI_RANGEs, drop to VR_VARYING. It would take more effort 1740 to compute a precise range for such a case. 1741 ??? General even mixed range kind operations can be expressed 1742 by for example transforming ~[3, 5] + [1, 2] to range-only 1743 operations and a union primitive: 1744 [-INF, 2] + [1, 2] U [5, +INF] + [1, 2] 1745 [-INF+1, 4] U [6, +INF(OVF)] 1746 though usually the union is not exactly representable with 1747 a single range or anti-range as the above is 1748 [-INF+1, +INF(OVF)] intersected with ~[5, 5] 1749 but one could use a scheme similar to equivalences for this. */ 1750 set_value_range_to_varying (vr); 1751 return; 1752 } 1753 } 1754 else if (code == MIN_EXPR 1755 || code == MAX_EXPR) 1756 { 1757 if (vr0.type == VR_RANGE 1758 && !symbolic_range_p (&vr0)) 1759 { 1760 type = VR_RANGE; 1761 if (vr1.type == VR_RANGE 1762 && !symbolic_range_p (&vr1)) 1763 { 1764 /* For operations that make the resulting range directly 1765 proportional to the original ranges, apply the operation to 1766 the same end of each range. */ 1767 min = int_const_binop (code, vr0.min, vr1.min); 1768 max = int_const_binop (code, vr0.max, vr1.max); 1769 } 1770 else if (code == MIN_EXPR) 1771 { 1772 min = vrp_val_min (expr_type); 1773 max = vr0.max; 1774 } 1775 else if (code == MAX_EXPR) 1776 { 1777 min = vr0.min; 1778 max = vrp_val_max (expr_type); 1779 } 1780 } 1781 else if (vr1.type == VR_RANGE 1782 && !symbolic_range_p (&vr1)) 1783 { 1784 type = VR_RANGE; 1785 if (code == MIN_EXPR) 1786 { 1787 min = vrp_val_min (expr_type); 1788 max = vr1.max; 1789 } 1790 else if (code == MAX_EXPR) 1791 { 1792 min = vr1.min; 1793 max = vrp_val_max (expr_type); 1794 } 1795 } 1796 else 1797 { 1798 set_value_range_to_varying (vr); 1799 return; 1800 } 1801 } 1802 else if (code == MULT_EXPR) 1803 { 1804 /* Fancy code so that with unsigned, [-3,-1]*[-3,-1] does not 1805 drop to varying. This test requires 2*prec bits if both 1806 operands are signed and 2*prec + 2 bits if either is not. */ 1807 1808 signop sign = TYPE_SIGN (expr_type); 1809 unsigned int prec = TYPE_PRECISION (expr_type); 1810 1811 if (!range_int_cst_p (&vr0) 1812 || !range_int_cst_p (&vr1)) 1813 { 1814 set_value_range_to_varying (vr); 1815 return; 1816 } 1817 1818 if (TYPE_OVERFLOW_WRAPS (expr_type)) 1819 { 1820 typedef FIXED_WIDE_INT (WIDE_INT_MAX_PRECISION * 2) vrp_int; 1821 typedef generic_wide_int 1822 <wi::extended_tree <WIDE_INT_MAX_PRECISION * 2> > vrp_int_cst; 1823 vrp_int sizem1 = wi::mask <vrp_int> (prec, false); 1824 vrp_int size = sizem1 + 1; 1825 1826 /* Extend the values using the sign of the result to PREC2. 1827 From here on out, everthing is just signed math no matter 1828 what the input types were. */ 1829 vrp_int min0 = vrp_int_cst (vr0.min); 1830 vrp_int max0 = vrp_int_cst (vr0.max); 1831 vrp_int min1 = vrp_int_cst (vr1.min); 1832 vrp_int max1 = vrp_int_cst (vr1.max); 1833 /* Canonicalize the intervals. */ 1834 if (sign == UNSIGNED) 1835 { 1836 if (wi::ltu_p (size, min0 + max0)) 1837 { 1838 min0 -= size; 1839 max0 -= size; 1840 } 1841 1842 if (wi::ltu_p (size, min1 + max1)) 1843 { 1844 min1 -= size; 1845 max1 -= size; 1846 } 1847 } 1848 1849 vrp_int prod0 = min0 * min1; 1850 vrp_int prod1 = min0 * max1; 1851 vrp_int prod2 = max0 * min1; 1852 vrp_int prod3 = max0 * max1; 1853 1854 /* Sort the 4 products so that min is in prod0 and max is in 1855 prod3. */ 1856 /* min0min1 > max0max1 */ 1857 if (prod0 > prod3) 1858 std::swap (prod0, prod3); 1859 1860 /* min0max1 > max0min1 */ 1861 if (prod1 > prod2) 1862 std::swap (prod1, prod2); 1863 1864 if (prod0 > prod1) 1865 std::swap (prod0, prod1); 1866 1867 if (prod2 > prod3) 1868 std::swap (prod2, prod3); 1869 1870 /* diff = max - min. */ 1871 prod2 = prod3 - prod0; 1872 if (wi::geu_p (prod2, sizem1)) 1873 { 1874 /* the range covers all values. */ 1875 set_value_range_to_varying (vr); 1876 return; 1877 } 1878 1879 /* The following should handle the wrapping and selecting 1880 VR_ANTI_RANGE for us. */ 1881 min = wide_int_to_tree (expr_type, prod0); 1882 max = wide_int_to_tree (expr_type, prod3); 1883 set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); 1884 return; 1885 } 1886 1887 /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs, 1888 drop to VR_VARYING. It would take more effort to compute a 1889 precise range for such a case. For example, if we have 1890 op0 == 65536 and op1 == 65536 with their ranges both being 1891 ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so 1892 we cannot claim that the product is in ~[0,0]. Note that we 1893 are guaranteed to have vr0.type == vr1.type at this 1894 point. */ 1895 if (vr0.type == VR_ANTI_RANGE 1896 && !TYPE_OVERFLOW_UNDEFINED (expr_type)) 1897 { 1898 set_value_range_to_varying (vr); 1899 return; 1900 } 1901 1902 extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1); 1903 return; 1904 } 1905 else if (code == RSHIFT_EXPR 1906 || code == LSHIFT_EXPR) 1907 { 1908 /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1], 1909 then drop to VR_VARYING. Outside of this range we get undefined 1910 behavior from the shift operation. We cannot even trust 1911 SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl 1912 shifts, and the operation at the tree level may be widened. */ 1913 if (range_int_cst_p (&vr1) 1914 && compare_tree_int (vr1.min, 0) >= 0 1915 && compare_tree_int (vr1.max, TYPE_PRECISION (expr_type)) == -1) 1916 { 1917 if (code == RSHIFT_EXPR) 1918 { 1919 /* Even if vr0 is VARYING or otherwise not usable, we can derive 1920 useful ranges just from the shift count. E.g. 1921 x >> 63 for signed 64-bit x is always [-1, 0]. */ 1922 if (vr0.type != VR_RANGE || symbolic_range_p (&vr0)) 1923 { 1924 vr0.type = type = VR_RANGE; 1925 vr0.min = vrp_val_min (expr_type); 1926 vr0.max = vrp_val_max (expr_type); 1927 } 1928 extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1); 1929 return; 1930 } 1931 /* We can map lshifts by constants to MULT_EXPR handling. */ 1932 else if (code == LSHIFT_EXPR 1933 && range_int_cst_singleton_p (&vr1)) 1934 { 1935 bool saved_flag_wrapv; 1936 value_range vr1p = VR_INITIALIZER; 1937 vr1p.type = VR_RANGE; 1938 vr1p.min = (wide_int_to_tree 1939 (expr_type, 1940 wi::set_bit_in_zero (tree_to_shwi (vr1.min), 1941 TYPE_PRECISION (expr_type)))); 1942 vr1p.max = vr1p.min; 1943 /* We have to use a wrapping multiply though as signed overflow 1944 on lshifts is implementation defined in C89. */ 1945 saved_flag_wrapv = flag_wrapv; 1946 flag_wrapv = 1; 1947 extract_range_from_binary_expr_1 (vr, MULT_EXPR, expr_type, 1948 &vr0, &vr1p); 1949 flag_wrapv = saved_flag_wrapv; 1950 return; 1951 } 1952 else if (code == LSHIFT_EXPR 1953 && range_int_cst_p (&vr0)) 1954 { 1955 int prec = TYPE_PRECISION (expr_type); 1956 int overflow_pos = prec; 1957 int bound_shift; 1958 wide_int low_bound, high_bound; 1959 bool uns = TYPE_UNSIGNED (expr_type); 1960 bool in_bounds = false; 1961 1962 if (!uns) 1963 overflow_pos -= 1; 1964 1965 bound_shift = overflow_pos - tree_to_shwi (vr1.max); 1966 /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can 1967 overflow. However, for that to happen, vr1.max needs to be 1968 zero, which means vr1 is a singleton range of zero, which 1969 means it should be handled by the previous LSHIFT_EXPR 1970 if-clause. */ 1971 wide_int bound = wi::set_bit_in_zero (bound_shift, prec); 1972 wide_int complement = ~(bound - 1); 1973 1974 if (uns) 1975 { 1976 low_bound = bound; 1977 high_bound = complement; 1978 if (wi::ltu_p (wi::to_wide (vr0.max), low_bound)) 1979 { 1980 /* [5, 6] << [1, 2] == [10, 24]. */ 1981 /* We're shifting out only zeroes, the value increases 1982 monotonically. */ 1983 in_bounds = true; 1984 } 1985 else if (wi::ltu_p (high_bound, wi::to_wide (vr0.min))) 1986 { 1987 /* [0xffffff00, 0xffffffff] << [1, 2] 1988 == [0xfffffc00, 0xfffffffe]. */ 1989 /* We're shifting out only ones, the value decreases 1990 monotonically. */ 1991 in_bounds = true; 1992 } 1993 } 1994 else 1995 { 1996 /* [-1, 1] << [1, 2] == [-4, 4]. */ 1997 low_bound = complement; 1998 high_bound = bound; 1999 if (wi::lts_p (wi::to_wide (vr0.max), high_bound) 2000 && wi::lts_p (low_bound, wi::to_wide (vr0.min))) 2001 { 2002 /* For non-negative numbers, we're shifting out only 2003 zeroes, the value increases monotonically. 2004 For negative numbers, we're shifting out only ones, the 2005 value decreases monotomically. */ 2006 in_bounds = true; 2007 } 2008 } 2009 2010 if (in_bounds) 2011 { 2012 extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1); 2013 return; 2014 } 2015 } 2016 } 2017 set_value_range_to_varying (vr); 2018 return; 2019 } 2020 else if (code == TRUNC_DIV_EXPR 2021 || code == FLOOR_DIV_EXPR 2022 || code == CEIL_DIV_EXPR 2023 || code == EXACT_DIV_EXPR 2024 || code == ROUND_DIV_EXPR) 2025 { 2026 if (vr0.type != VR_RANGE || symbolic_range_p (&vr0)) 2027 { 2028 /* For division, if op1 has VR_RANGE but op0 does not, something 2029 can be deduced just from that range. Say [min, max] / [4, max] 2030 gives [min / 4, max / 4] range. */ 2031 if (vr1.type == VR_RANGE 2032 && !symbolic_range_p (&vr1) 2033 && range_includes_zero_p (vr1.min, vr1.max) == 0) 2034 { 2035 vr0.type = type = VR_RANGE; 2036 vr0.min = vrp_val_min (expr_type); 2037 vr0.max = vrp_val_max (expr_type); 2038 } 2039 else 2040 { 2041 set_value_range_to_varying (vr); 2042 return; 2043 } 2044 } 2045 2046 /* For divisions, if flag_non_call_exceptions is true, we must 2047 not eliminate a division by zero. */ 2048 if (cfun->can_throw_non_call_exceptions 2049 && (vr1.type != VR_RANGE 2050 || range_includes_zero_p (vr1.min, vr1.max) != 0)) 2051 { 2052 set_value_range_to_varying (vr); 2053 return; 2054 } 2055 2056 /* For divisions, if op0 is VR_RANGE, we can deduce a range 2057 even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can 2058 include 0. */ 2059 if (vr0.type == VR_RANGE 2060 && (vr1.type != VR_RANGE 2061 || range_includes_zero_p (vr1.min, vr1.max) != 0)) 2062 { 2063 tree zero = build_int_cst (TREE_TYPE (vr0.min), 0); 2064 int cmp; 2065 2066 min = NULL_TREE; 2067 max = NULL_TREE; 2068 if (TYPE_UNSIGNED (expr_type) 2069 || value_range_nonnegative_p (&vr1)) 2070 { 2071 /* For unsigned division or when divisor is known 2072 to be non-negative, the range has to cover 2073 all numbers from 0 to max for positive max 2074 and all numbers from min to 0 for negative min. */ 2075 cmp = compare_values (vr0.max, zero); 2076 if (cmp == -1) 2077 { 2078 /* When vr0.max < 0, vr1.min != 0 and value 2079 ranges for dividend and divisor are available. */ 2080 if (vr1.type == VR_RANGE 2081 && !symbolic_range_p (&vr0) 2082 && !symbolic_range_p (&vr1) 2083 && compare_values (vr1.min, zero) != 0) 2084 max = int_const_binop (code, vr0.max, vr1.min); 2085 else 2086 max = zero; 2087 } 2088 else if (cmp == 0 || cmp == 1) 2089 max = vr0.max; 2090 else 2091 type = VR_VARYING; 2092 cmp = compare_values (vr0.min, zero); 2093 if (cmp == 1) 2094 { 2095 /* For unsigned division when value ranges for dividend 2096 and divisor are available. */ 2097 if (vr1.type == VR_RANGE 2098 && !symbolic_range_p (&vr0) 2099 && !symbolic_range_p (&vr1) 2100 && compare_values (vr1.max, zero) != 0) 2101 min = int_const_binop (code, vr0.min, vr1.max); 2102 else 2103 min = zero; 2104 } 2105 else if (cmp == 0 || cmp == -1) 2106 min = vr0.min; 2107 else 2108 type = VR_VARYING; 2109 } 2110 else 2111 { 2112 /* Otherwise the range is -max .. max or min .. -min 2113 depending on which bound is bigger in absolute value, 2114 as the division can change the sign. */ 2115 abs_extent_range (vr, vr0.min, vr0.max); 2116 return; 2117 } 2118 if (type == VR_VARYING) 2119 { 2120 set_value_range_to_varying (vr); 2121 return; 2122 } 2123 } 2124 else if (range_int_cst_p (&vr0) && range_int_cst_p (&vr1)) 2125 { 2126 extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1); 2127 return; 2128 } 2129 } 2130 else if (code == TRUNC_MOD_EXPR) 2131 { 2132 if (range_is_null (&vr1)) 2133 { 2134 set_value_range_to_undefined (vr); 2135 return; 2136 } 2137 /* ABS (A % B) < ABS (B) and either 2138 0 <= A % B <= A or A <= A % B <= 0. */ 2139 type = VR_RANGE; 2140 signop sgn = TYPE_SIGN (expr_type); 2141 unsigned int prec = TYPE_PRECISION (expr_type); 2142 wide_int wmin, wmax, tmp; 2143 if (vr1.type == VR_RANGE && !symbolic_range_p (&vr1)) 2144 { 2145 wmax = wi::to_wide (vr1.max) - 1; 2146 if (sgn == SIGNED) 2147 { 2148 tmp = -1 - wi::to_wide (vr1.min); 2149 wmax = wi::smax (wmax, tmp); 2150 } 2151 } 2152 else 2153 { 2154 wmax = wi::max_value (prec, sgn); 2155 /* X % INT_MIN may be INT_MAX. */ 2156 if (sgn == UNSIGNED) 2157 wmax = wmax - 1; 2158 } 2159 2160 if (sgn == UNSIGNED) 2161 wmin = wi::zero (prec); 2162 else 2163 { 2164 wmin = -wmax; 2165 if (vr0.type == VR_RANGE && TREE_CODE (vr0.min) == INTEGER_CST) 2166 { 2167 tmp = wi::to_wide (vr0.min); 2168 if (wi::gts_p (tmp, 0)) 2169 tmp = wi::zero (prec); 2170 wmin = wi::smax (wmin, tmp); 2171 } 2172 } 2173 2174 if (vr0.type == VR_RANGE && TREE_CODE (vr0.max) == INTEGER_CST) 2175 { 2176 tmp = wi::to_wide (vr0.max); 2177 if (sgn == SIGNED && wi::neg_p (tmp)) 2178 tmp = wi::zero (prec); 2179 wmax = wi::min (wmax, tmp, sgn); 2180 } 2181 2182 min = wide_int_to_tree (expr_type, wmin); 2183 max = wide_int_to_tree (expr_type, wmax); 2184 } 2185 else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR) 2186 { 2187 bool int_cst_range0, int_cst_range1; 2188 wide_int may_be_nonzero0, may_be_nonzero1; 2189 wide_int must_be_nonzero0, must_be_nonzero1; 2190 2191 int_cst_range0 = zero_nonzero_bits_from_vr (expr_type, &vr0, 2192 &may_be_nonzero0, 2193 &must_be_nonzero0); 2194 int_cst_range1 = zero_nonzero_bits_from_vr (expr_type, &vr1, 2195 &may_be_nonzero1, 2196 &must_be_nonzero1); 2197 2198 if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR) 2199 { 2200 value_range *vr0p = NULL, *vr1p = NULL; 2201 if (range_int_cst_singleton_p (&vr1)) 2202 { 2203 vr0p = &vr0; 2204 vr1p = &vr1; 2205 } 2206 else if (range_int_cst_singleton_p (&vr0)) 2207 { 2208 vr0p = &vr1; 2209 vr1p = &vr0; 2210 } 2211 /* For op & or | attempt to optimize: 2212 [x, y] op z into [x op z, y op z] 2213 if z is a constant which (for op | its bitwise not) has n 2214 consecutive least significant bits cleared followed by m 1 2215 consecutive bits set immediately above it and either 2216 m + n == precision, or (x >> (m + n)) == (y >> (m + n)). 2217 The least significant n bits of all the values in the range are 2218 cleared or set, the m bits above it are preserved and any bits 2219 above these are required to be the same for all values in the 2220 range. */ 2221 if (vr0p && range_int_cst_p (vr0p)) 2222 { 2223 wide_int w = wi::to_wide (vr1p->min); 2224 int m = 0, n = 0; 2225 if (code == BIT_IOR_EXPR) 2226 w = ~w; 2227 if (wi::eq_p (w, 0)) 2228 n = TYPE_PRECISION (expr_type); 2229 else 2230 { 2231 n = wi::ctz (w); 2232 w = ~(w | wi::mask (n, false, w.get_precision ())); 2233 if (wi::eq_p (w, 0)) 2234 m = TYPE_PRECISION (expr_type) - n; 2235 else 2236 m = wi::ctz (w) - n; 2237 } 2238 wide_int mask = wi::mask (m + n, true, w.get_precision ()); 2239 if ((mask & wi::to_wide (vr0p->min)) 2240 == (mask & wi::to_wide (vr0p->max))) 2241 { 2242 min = int_const_binop (code, vr0p->min, vr1p->min); 2243 max = int_const_binop (code, vr0p->max, vr1p->min); 2244 } 2245 } 2246 } 2247 2248 type = VR_RANGE; 2249 if (min && max) 2250 /* Optimized above already. */; 2251 else if (code == BIT_AND_EXPR) 2252 { 2253 min = wide_int_to_tree (expr_type, 2254 must_be_nonzero0 & must_be_nonzero1); 2255 wide_int wmax = may_be_nonzero0 & may_be_nonzero1; 2256 /* If both input ranges contain only negative values we can 2257 truncate the result range maximum to the minimum of the 2258 input range maxima. */ 2259 if (int_cst_range0 && int_cst_range1 2260 && tree_int_cst_sgn (vr0.max) < 0 2261 && tree_int_cst_sgn (vr1.max) < 0) 2262 { 2263 wmax = wi::min (wmax, wi::to_wide (vr0.max), 2264 TYPE_SIGN (expr_type)); 2265 wmax = wi::min (wmax, wi::to_wide (vr1.max), 2266 TYPE_SIGN (expr_type)); 2267 } 2268 /* If either input range contains only non-negative values 2269 we can truncate the result range maximum to the respective 2270 maximum of the input range. */ 2271 if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0) 2272 wmax = wi::min (wmax, wi::to_wide (vr0.max), 2273 TYPE_SIGN (expr_type)); 2274 if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0) 2275 wmax = wi::min (wmax, wi::to_wide (vr1.max), 2276 TYPE_SIGN (expr_type)); 2277 max = wide_int_to_tree (expr_type, wmax); 2278 cmp = compare_values (min, max); 2279 /* PR68217: In case of signed & sign-bit-CST should 2280 result in [-INF, 0] instead of [-INF, INF]. */ 2281 if (cmp == -2 || cmp == 1) 2282 { 2283 wide_int sign_bit 2284 = wi::set_bit_in_zero (TYPE_PRECISION (expr_type) - 1, 2285 TYPE_PRECISION (expr_type)); 2286 if (!TYPE_UNSIGNED (expr_type) 2287 && ((int_cst_range0 2288 && value_range_constant_singleton (&vr0) 2289 && !wi::cmps (wi::to_wide (vr0.min), sign_bit)) 2290 || (int_cst_range1 2291 && value_range_constant_singleton (&vr1) 2292 && !wi::cmps (wi::to_wide (vr1.min), sign_bit)))) 2293 { 2294 min = TYPE_MIN_VALUE (expr_type); 2295 max = build_int_cst (expr_type, 0); 2296 } 2297 } 2298 } 2299 else if (code == BIT_IOR_EXPR) 2300 { 2301 max = wide_int_to_tree (expr_type, 2302 may_be_nonzero0 | may_be_nonzero1); 2303 wide_int wmin = must_be_nonzero0 | must_be_nonzero1; 2304 /* If the input ranges contain only positive values we can 2305 truncate the minimum of the result range to the maximum 2306 of the input range minima. */ 2307 if (int_cst_range0 && int_cst_range1 2308 && tree_int_cst_sgn (vr0.min) >= 0 2309 && tree_int_cst_sgn (vr1.min) >= 0) 2310 { 2311 wmin = wi::max (wmin, wi::to_wide (vr0.min), 2312 TYPE_SIGN (expr_type)); 2313 wmin = wi::max (wmin, wi::to_wide (vr1.min), 2314 TYPE_SIGN (expr_type)); 2315 } 2316 /* If either input range contains only negative values 2317 we can truncate the minimum of the result range to the 2318 respective minimum range. */ 2319 if (int_cst_range0 && tree_int_cst_sgn (vr0.max) < 0) 2320 wmin = wi::max (wmin, wi::to_wide (vr0.min), 2321 TYPE_SIGN (expr_type)); 2322 if (int_cst_range1 && tree_int_cst_sgn (vr1.max) < 0) 2323 wmin = wi::max (wmin, wi::to_wide (vr1.min), 2324 TYPE_SIGN (expr_type)); 2325 min = wide_int_to_tree (expr_type, wmin); 2326 } 2327 else if (code == BIT_XOR_EXPR) 2328 { 2329 wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1) 2330 | ~(may_be_nonzero0 | may_be_nonzero1)); 2331 wide_int result_one_bits 2332 = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1) 2333 | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0)); 2334 max = wide_int_to_tree (expr_type, ~result_zero_bits); 2335 min = wide_int_to_tree (expr_type, result_one_bits); 2336 /* If the range has all positive or all negative values the 2337 result is better than VARYING. */ 2338 if (tree_int_cst_sgn (min) < 0 2339 || tree_int_cst_sgn (max) >= 0) 2340 ; 2341 else 2342 max = min = NULL_TREE; 2343 } 2344 } 2345 else 2346 gcc_unreachable (); 2347 2348 /* If either MIN or MAX overflowed, then set the resulting range to 2349 VARYING. */ 2350 if (min == NULL_TREE 2351 || TREE_OVERFLOW_P (min) 2352 || max == NULL_TREE 2353 || TREE_OVERFLOW_P (max)) 2354 { 2355 set_value_range_to_varying (vr); 2356 return; 2357 } 2358 2359 /* We punt for [-INF, +INF]. 2360 We learn nothing when we have INF on both sides. 2361 Note that we do accept [-INF, -INF] and [+INF, +INF]. */ 2362 if (vrp_val_is_min (min) && vrp_val_is_max (max)) 2363 { 2364 set_value_range_to_varying (vr); 2365 return; 2366 } 2367 2368 cmp = compare_values (min, max); 2369 if (cmp == -2 || cmp == 1) 2370 { 2371 /* If the new range has its limits swapped around (MIN > MAX), 2372 then the operation caused one of them to wrap around, mark 2373 the new range VARYING. */ 2374 set_value_range_to_varying (vr); 2375 } 2376 else 2377 set_value_range (vr, type, min, max, NULL); 2378 } 2379 2380 /* Extract range information from a unary operation CODE based on 2381 the range of its operand *VR0 with type OP0_TYPE with resulting type TYPE. 2382 The resulting range is stored in *VR. */ 2383 2384 void 2385 extract_range_from_unary_expr (value_range *vr, 2386 enum tree_code code, tree type, 2387 value_range *vr0_, tree op0_type) 2388 { 2389 value_range vr0 = *vr0_, vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER; 2390 2391 /* VRP only operates on integral and pointer types. */ 2392 if (!(INTEGRAL_TYPE_P (op0_type) 2393 || POINTER_TYPE_P (op0_type)) 2394 || !(INTEGRAL_TYPE_P (type) 2395 || POINTER_TYPE_P (type))) 2396 { 2397 set_value_range_to_varying (vr); 2398 return; 2399 } 2400 2401 /* If VR0 is UNDEFINED, so is the result. */ 2402 if (vr0.type == VR_UNDEFINED) 2403 { 2404 set_value_range_to_undefined (vr); 2405 return; 2406 } 2407 2408 /* Handle operations that we express in terms of others. */ 2409 if (code == PAREN_EXPR || code == OBJ_TYPE_REF) 2410 { 2411 /* PAREN_EXPR and OBJ_TYPE_REF are simple copies. */ 2412 copy_value_range (vr, &vr0); 2413 return; 2414 } 2415 else if (code == NEGATE_EXPR) 2416 { 2417 /* -X is simply 0 - X, so re-use existing code that also handles 2418 anti-ranges fine. */ 2419 value_range zero = VR_INITIALIZER; 2420 set_value_range_to_value (&zero, build_int_cst (type, 0), NULL); 2421 extract_range_from_binary_expr_1 (vr, MINUS_EXPR, type, &zero, &vr0); 2422 return; 2423 } 2424 else if (code == BIT_NOT_EXPR) 2425 { 2426 /* ~X is simply -1 - X, so re-use existing code that also handles 2427 anti-ranges fine. */ 2428 value_range minusone = VR_INITIALIZER; 2429 set_value_range_to_value (&minusone, build_int_cst (type, -1), NULL); 2430 extract_range_from_binary_expr_1 (vr, MINUS_EXPR, 2431 type, &minusone, &vr0); 2432 return; 2433 } 2434 2435 /* Now canonicalize anti-ranges to ranges when they are not symbolic 2436 and express op ~[] as (op []') U (op []''). */ 2437 if (vr0.type == VR_ANTI_RANGE 2438 && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1)) 2439 { 2440 extract_range_from_unary_expr (vr, code, type, &vrtem0, op0_type); 2441 if (vrtem1.type != VR_UNDEFINED) 2442 { 2443 value_range vrres = VR_INITIALIZER; 2444 extract_range_from_unary_expr (&vrres, code, type, 2445 &vrtem1, op0_type); 2446 vrp_meet (vr, &vrres); 2447 } 2448 return; 2449 } 2450 2451 if (CONVERT_EXPR_CODE_P (code)) 2452 { 2453 tree inner_type = op0_type; 2454 tree outer_type = type; 2455 2456 /* If the expression evaluates to a pointer, we are only interested in 2457 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */ 2458 if (POINTER_TYPE_P (type)) 2459 { 2460 if (range_is_nonnull (&vr0)) 2461 set_value_range_to_nonnull (vr, type); 2462 else if (range_is_null (&vr0)) 2463 set_value_range_to_null (vr, type); 2464 else 2465 set_value_range_to_varying (vr); 2466 return; 2467 } 2468 2469 /* If VR0 is varying and we increase the type precision, assume 2470 a full range for the following transformation. */ 2471 if (vr0.type == VR_VARYING 2472 && INTEGRAL_TYPE_P (inner_type) 2473 && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type)) 2474 { 2475 vr0.type = VR_RANGE; 2476 vr0.min = TYPE_MIN_VALUE (inner_type); 2477 vr0.max = TYPE_MAX_VALUE (inner_type); 2478 } 2479 2480 /* If VR0 is a constant range or anti-range and the conversion is 2481 not truncating we can convert the min and max values and 2482 canonicalize the resulting range. Otherwise we can do the 2483 conversion if the size of the range is less than what the 2484 precision of the target type can represent and the range is 2485 not an anti-range. */ 2486 if ((vr0.type == VR_RANGE 2487 || vr0.type == VR_ANTI_RANGE) 2488 && TREE_CODE (vr0.min) == INTEGER_CST 2489 && TREE_CODE (vr0.max) == INTEGER_CST 2490 && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type) 2491 || (vr0.type == VR_RANGE 2492 && integer_zerop (int_const_binop (RSHIFT_EXPR, 2493 int_const_binop (MINUS_EXPR, vr0.max, vr0.min), 2494 size_int (TYPE_PRECISION (outer_type))))))) 2495 { 2496 tree new_min, new_max; 2497 new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), 2498 0, false); 2499 new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), 2500 0, false); 2501 set_and_canonicalize_value_range (vr, vr0.type, 2502 new_min, new_max, NULL); 2503 return; 2504 } 2505 2506 set_value_range_to_varying (vr); 2507 return; 2508 } 2509 else if (code == ABS_EXPR) 2510 { 2511 tree min, max; 2512 int cmp; 2513 2514 /* Pass through vr0 in the easy cases. */ 2515 if (TYPE_UNSIGNED (type) 2516 || value_range_nonnegative_p (&vr0)) 2517 { 2518 copy_value_range (vr, &vr0); 2519 return; 2520 } 2521 2522 /* For the remaining varying or symbolic ranges we can't do anything 2523 useful. */ 2524 if (vr0.type == VR_VARYING 2525 || symbolic_range_p (&vr0)) 2526 { 2527 set_value_range_to_varying (vr); 2528 return; 2529 } 2530 2531 /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a 2532 useful range. */ 2533 if (!TYPE_OVERFLOW_UNDEFINED (type) 2534 && ((vr0.type == VR_RANGE 2535 && vrp_val_is_min (vr0.min)) 2536 || (vr0.type == VR_ANTI_RANGE 2537 && !vrp_val_is_min (vr0.min)))) 2538 { 2539 set_value_range_to_varying (vr); 2540 return; 2541 } 2542 2543 /* ABS_EXPR may flip the range around, if the original range 2544 included negative values. */ 2545 if (!vrp_val_is_min (vr0.min)) 2546 min = fold_unary_to_constant (code, type, vr0.min); 2547 else 2548 min = TYPE_MAX_VALUE (type); 2549 2550 if (!vrp_val_is_min (vr0.max)) 2551 max = fold_unary_to_constant (code, type, vr0.max); 2552 else 2553 max = TYPE_MAX_VALUE (type); 2554 2555 cmp = compare_values (min, max); 2556 2557 /* If a VR_ANTI_RANGEs contains zero, then we have 2558 ~[-INF, min(MIN, MAX)]. */ 2559 if (vr0.type == VR_ANTI_RANGE) 2560 { 2561 if (range_includes_zero_p (vr0.min, vr0.max) == 1) 2562 { 2563 /* Take the lower of the two values. */ 2564 if (cmp != 1) 2565 max = min; 2566 2567 /* Create ~[-INF, min (abs(MIN), abs(MAX))] 2568 or ~[-INF + 1, min (abs(MIN), abs(MAX))] when 2569 flag_wrapv is set and the original anti-range doesn't include 2570 TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */ 2571 if (TYPE_OVERFLOW_WRAPS (type)) 2572 { 2573 tree type_min_value = TYPE_MIN_VALUE (type); 2574 2575 min = (vr0.min != type_min_value 2576 ? int_const_binop (PLUS_EXPR, type_min_value, 2577 build_int_cst (TREE_TYPE (type_min_value), 1)) 2578 : type_min_value); 2579 } 2580 else 2581 min = TYPE_MIN_VALUE (type); 2582 } 2583 else 2584 { 2585 /* All else has failed, so create the range [0, INF], even for 2586 flag_wrapv since TYPE_MIN_VALUE is in the original 2587 anti-range. */ 2588 vr0.type = VR_RANGE; 2589 min = build_int_cst (type, 0); 2590 max = TYPE_MAX_VALUE (type); 2591 } 2592 } 2593 2594 /* If the range contains zero then we know that the minimum value in the 2595 range will be zero. */ 2596 else if (range_includes_zero_p (vr0.min, vr0.max) == 1) 2597 { 2598 if (cmp == 1) 2599 max = min; 2600 min = build_int_cst (type, 0); 2601 } 2602 else 2603 { 2604 /* If the range was reversed, swap MIN and MAX. */ 2605 if (cmp == 1) 2606 std::swap (min, max); 2607 } 2608 2609 cmp = compare_values (min, max); 2610 if (cmp == -2 || cmp == 1) 2611 { 2612 /* If the new range has its limits swapped around (MIN > MAX), 2613 then the operation caused one of them to wrap around, mark 2614 the new range VARYING. */ 2615 set_value_range_to_varying (vr); 2616 } 2617 else 2618 set_value_range (vr, vr0.type, min, max, NULL); 2619 return; 2620 } 2621 2622 /* For unhandled operations fall back to varying. */ 2623 set_value_range_to_varying (vr); 2624 return; 2625 } 2626 2627 /* Debugging dumps. */ 2628 2629 void dump_value_range (FILE *, const value_range *); 2630 void debug_value_range (value_range *); 2631 void dump_all_value_ranges (FILE *); 2632 void dump_vr_equiv (FILE *, bitmap); 2633 void debug_vr_equiv (bitmap); 2634 2635 2636 /* Dump value range VR to FILE. */ 2637 2638 void 2639 dump_value_range (FILE *file, const value_range *vr) 2640 { 2641 if (vr == NULL) 2642 fprintf (file, "[]"); 2643 else if (vr->type == VR_UNDEFINED) 2644 fprintf (file, "UNDEFINED"); 2645 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE) 2646 { 2647 tree type = TREE_TYPE (vr->min); 2648 2649 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); 2650 2651 if (INTEGRAL_TYPE_P (type) 2652 && !TYPE_UNSIGNED (type) 2653 && vrp_val_is_min (vr->min)) 2654 fprintf (file, "-INF"); 2655 else 2656 print_generic_expr (file, vr->min); 2657 2658 fprintf (file, ", "); 2659 2660 if (INTEGRAL_TYPE_P (type) 2661 && vrp_val_is_max (vr->max)) 2662 fprintf (file, "+INF"); 2663 else 2664 print_generic_expr (file, vr->max); 2665 2666 fprintf (file, "]"); 2667 2668 if (vr->equiv) 2669 { 2670 bitmap_iterator bi; 2671 unsigned i, c = 0; 2672 2673 fprintf (file, " EQUIVALENCES: { "); 2674 2675 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi) 2676 { 2677 print_generic_expr (file, ssa_name (i)); 2678 fprintf (file, " "); 2679 c++; 2680 } 2681 2682 fprintf (file, "} (%u elements)", c); 2683 } 2684 } 2685 else if (vr->type == VR_VARYING) 2686 fprintf (file, "VARYING"); 2687 else 2688 fprintf (file, "INVALID RANGE"); 2689 } 2690 2691 2692 /* Dump value range VR to stderr. */ 2693 2694 DEBUG_FUNCTION void 2695 debug_value_range (value_range *vr) 2696 { 2697 dump_value_range (stderr, vr); 2698 fprintf (stderr, "\n"); 2699 } 2700 2701 2702 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V, 2703 create a new SSA name N and return the assertion assignment 2704 'N = ASSERT_EXPR <V, V OP W>'. */ 2705 2706 static gimple * 2707 build_assert_expr_for (tree cond, tree v) 2708 { 2709 tree a; 2710 gassign *assertion; 2711 2712 gcc_assert (TREE_CODE (v) == SSA_NAME 2713 && COMPARISON_CLASS_P (cond)); 2714 2715 a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond); 2716 assertion = gimple_build_assign (NULL_TREE, a); 2717 2718 /* The new ASSERT_EXPR, creates a new SSA name that replaces the 2719 operand of the ASSERT_EXPR. Create it so the new name and the old one 2720 are registered in the replacement table so that we can fix the SSA web 2721 after adding all the ASSERT_EXPRs. */ 2722 tree new_def = create_new_def_for (v, assertion, NULL); 2723 /* Make sure we preserve abnormalness throughout an ASSERT_EXPR chain 2724 given we have to be able to fully propagate those out to re-create 2725 valid SSA when removing the asserts. */ 2726 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (v)) 2727 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_def) = 1; 2728 2729 return assertion; 2730 } 2731 2732 2733 /* Return false if EXPR is a predicate expression involving floating 2734 point values. */ 2735 2736 static inline bool 2737 fp_predicate (gimple *stmt) 2738 { 2739 GIMPLE_CHECK (stmt, GIMPLE_COND); 2740 2741 return FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))); 2742 } 2743 2744 /* If the range of values taken by OP can be inferred after STMT executes, 2745 return the comparison code (COMP_CODE_P) and value (VAL_P) that 2746 describes the inferred range. Return true if a range could be 2747 inferred. */ 2748 2749 bool 2750 infer_value_range (gimple *stmt, tree op, tree_code *comp_code_p, tree *val_p) 2751 { 2752 *val_p = NULL_TREE; 2753 *comp_code_p = ERROR_MARK; 2754 2755 /* Do not attempt to infer anything in names that flow through 2756 abnormal edges. */ 2757 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) 2758 return false; 2759 2760 /* If STMT is the last statement of a basic block with no normal 2761 successors, there is no point inferring anything about any of its 2762 operands. We would not be able to find a proper insertion point 2763 for the assertion, anyway. */ 2764 if (stmt_ends_bb_p (stmt)) 2765 { 2766 edge_iterator ei; 2767 edge e; 2768 2769 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) 2770 if (!(e->flags & (EDGE_ABNORMAL|EDGE_EH))) 2771 break; 2772 if (e == NULL) 2773 return false; 2774 } 2775 2776 if (infer_nonnull_range (stmt, op)) 2777 { 2778 *val_p = build_int_cst (TREE_TYPE (op), 0); 2779 *comp_code_p = NE_EXPR; 2780 return true; 2781 } 2782 2783 return false; 2784 } 2785 2786 2787 void dump_asserts_for (FILE *, tree); 2788 void debug_asserts_for (tree); 2789 void dump_all_asserts (FILE *); 2790 void debug_all_asserts (void); 2791 2792 /* Dump all the registered assertions for NAME to FILE. */ 2793 2794 void 2795 dump_asserts_for (FILE *file, tree name) 2796 { 2797 assert_locus *loc; 2798 2799 fprintf (file, "Assertions to be inserted for "); 2800 print_generic_expr (file, name); 2801 fprintf (file, "\n"); 2802 2803 loc = asserts_for[SSA_NAME_VERSION (name)]; 2804 while (loc) 2805 { 2806 fprintf (file, "\t"); 2807 print_gimple_stmt (file, gsi_stmt (loc->si), 0); 2808 fprintf (file, "\n\tBB #%d", loc->bb->index); 2809 if (loc->e) 2810 { 2811 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index, 2812 loc->e->dest->index); 2813 dump_edge_info (file, loc->e, dump_flags, 0); 2814 } 2815 fprintf (file, "\n\tPREDICATE: "); 2816 print_generic_expr (file, loc->expr); 2817 fprintf (file, " %s ", get_tree_code_name (loc->comp_code)); 2818 print_generic_expr (file, loc->val); 2819 fprintf (file, "\n\n"); 2820 loc = loc->next; 2821 } 2822 2823 fprintf (file, "\n"); 2824 } 2825 2826 2827 /* Dump all the registered assertions for NAME to stderr. */ 2828 2829 DEBUG_FUNCTION void 2830 debug_asserts_for (tree name) 2831 { 2832 dump_asserts_for (stderr, name); 2833 } 2834 2835 2836 /* Dump all the registered assertions for all the names to FILE. */ 2837 2838 void 2839 dump_all_asserts (FILE *file) 2840 { 2841 unsigned i; 2842 bitmap_iterator bi; 2843 2844 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n"); 2845 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 2846 dump_asserts_for (file, ssa_name (i)); 2847 fprintf (file, "\n"); 2848 } 2849 2850 2851 /* Dump all the registered assertions for all the names to stderr. */ 2852 2853 DEBUG_FUNCTION void 2854 debug_all_asserts (void) 2855 { 2856 dump_all_asserts (stderr); 2857 } 2858 2859 /* Push the assert info for NAME, EXPR, COMP_CODE and VAL to ASSERTS. */ 2860 2861 static void 2862 add_assert_info (vec<assert_info> &asserts, 2863 tree name, tree expr, enum tree_code comp_code, tree val) 2864 { 2865 assert_info info; 2866 info.comp_code = comp_code; 2867 info.name = name; 2868 if (TREE_OVERFLOW_P (val)) 2869 val = drop_tree_overflow (val); 2870 info.val = val; 2871 info.expr = expr; 2872 asserts.safe_push (info); 2873 } 2874 2875 /* If NAME doesn't have an ASSERT_EXPR registered for asserting 2876 'EXPR COMP_CODE VAL' at a location that dominates block BB or 2877 E->DEST, then register this location as a possible insertion point 2878 for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>. 2879 2880 BB, E and SI provide the exact insertion point for the new 2881 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted 2882 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on 2883 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E 2884 must not be NULL. */ 2885 2886 static void 2887 register_new_assert_for (tree name, tree expr, 2888 enum tree_code comp_code, 2889 tree val, 2890 basic_block bb, 2891 edge e, 2892 gimple_stmt_iterator si) 2893 { 2894 assert_locus *n, *loc, *last_loc; 2895 basic_block dest_bb; 2896 2897 gcc_checking_assert (bb == NULL || e == NULL); 2898 2899 if (e == NULL) 2900 gcc_checking_assert (gimple_code (gsi_stmt (si)) != GIMPLE_COND 2901 && gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH); 2902 2903 /* Never build an assert comparing against an integer constant with 2904 TREE_OVERFLOW set. This confuses our undefined overflow warning 2905 machinery. */ 2906 if (TREE_OVERFLOW_P (val)) 2907 val = drop_tree_overflow (val); 2908 2909 /* The new assertion A will be inserted at BB or E. We need to 2910 determine if the new location is dominated by a previously 2911 registered location for A. If we are doing an edge insertion, 2912 assume that A will be inserted at E->DEST. Note that this is not 2913 necessarily true. 2914 2915 If E is a critical edge, it will be split. But even if E is 2916 split, the new block will dominate the same set of blocks that 2917 E->DEST dominates. 2918 2919 The reverse, however, is not true, blocks dominated by E->DEST 2920 will not be dominated by the new block created to split E. So, 2921 if the insertion location is on a critical edge, we will not use 2922 the new location to move another assertion previously registered 2923 at a block dominated by E->DEST. */ 2924 dest_bb = (bb) ? bb : e->dest; 2925 2926 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and 2927 VAL at a block dominating DEST_BB, then we don't need to insert a new 2928 one. Similarly, if the same assertion already exists at a block 2929 dominated by DEST_BB and the new location is not on a critical 2930 edge, then update the existing location for the assertion (i.e., 2931 move the assertion up in the dominance tree). 2932 2933 Note, this is implemented as a simple linked list because there 2934 should not be more than a handful of assertions registered per 2935 name. If this becomes a performance problem, a table hashed by 2936 COMP_CODE and VAL could be implemented. */ 2937 loc = asserts_for[SSA_NAME_VERSION (name)]; 2938 last_loc = loc; 2939 while (loc) 2940 { 2941 if (loc->comp_code == comp_code 2942 && (loc->val == val 2943 || operand_equal_p (loc->val, val, 0)) 2944 && (loc->expr == expr 2945 || operand_equal_p (loc->expr, expr, 0))) 2946 { 2947 /* If E is not a critical edge and DEST_BB 2948 dominates the existing location for the assertion, move 2949 the assertion up in the dominance tree by updating its 2950 location information. */ 2951 if ((e == NULL || !EDGE_CRITICAL_P (e)) 2952 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb)) 2953 { 2954 loc->bb = dest_bb; 2955 loc->e = e; 2956 loc->si = si; 2957 return; 2958 } 2959 } 2960 2961 /* Update the last node of the list and move to the next one. */ 2962 last_loc = loc; 2963 loc = loc->next; 2964 } 2965 2966 /* If we didn't find an assertion already registered for 2967 NAME COMP_CODE VAL, add a new one at the end of the list of 2968 assertions associated with NAME. */ 2969 n = XNEW (struct assert_locus); 2970 n->bb = dest_bb; 2971 n->e = e; 2972 n->si = si; 2973 n->comp_code = comp_code; 2974 n->val = val; 2975 n->expr = expr; 2976 n->next = NULL; 2977 2978 if (last_loc) 2979 last_loc->next = n; 2980 else 2981 asserts_for[SSA_NAME_VERSION (name)] = n; 2982 2983 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name)); 2984 } 2985 2986 /* (COND_OP0 COND_CODE COND_OP1) is a predicate which uses NAME. 2987 Extract a suitable test code and value and store them into *CODE_P and 2988 *VAL_P so the predicate is normalized to NAME *CODE_P *VAL_P. 2989 2990 If no extraction was possible, return FALSE, otherwise return TRUE. 2991 2992 If INVERT is true, then we invert the result stored into *CODE_P. */ 2993 2994 static bool 2995 extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code, 2996 tree cond_op0, tree cond_op1, 2997 bool invert, enum tree_code *code_p, 2998 tree *val_p) 2999 { 3000 enum tree_code comp_code; 3001 tree val; 3002 3003 /* Otherwise, we have a comparison of the form NAME COMP VAL 3004 or VAL COMP NAME. */ 3005 if (name == cond_op1) 3006 { 3007 /* If the predicate is of the form VAL COMP NAME, flip 3008 COMP around because we need to register NAME as the 3009 first operand in the predicate. */ 3010 comp_code = swap_tree_comparison (cond_code); 3011 val = cond_op0; 3012 } 3013 else if (name == cond_op0) 3014 { 3015 /* The comparison is of the form NAME COMP VAL, so the 3016 comparison code remains unchanged. */ 3017 comp_code = cond_code; 3018 val = cond_op1; 3019 } 3020 else 3021 gcc_unreachable (); 3022 3023 /* Invert the comparison code as necessary. */ 3024 if (invert) 3025 comp_code = invert_tree_comparison (comp_code, 0); 3026 3027 /* VRP only handles integral and pointer types. */ 3028 if (! INTEGRAL_TYPE_P (TREE_TYPE (val)) 3029 && ! POINTER_TYPE_P (TREE_TYPE (val))) 3030 return false; 3031 3032 /* Do not register always-false predicates. 3033 FIXME: this works around a limitation in fold() when dealing with 3034 enumerations. Given 'enum { N1, N2 } x;', fold will not 3035 fold 'if (x > N2)' to 'if (0)'. */ 3036 if ((comp_code == GT_EXPR || comp_code == LT_EXPR) 3037 && INTEGRAL_TYPE_P (TREE_TYPE (val))) 3038 { 3039 tree min = TYPE_MIN_VALUE (TREE_TYPE (val)); 3040 tree max = TYPE_MAX_VALUE (TREE_TYPE (val)); 3041 3042 if (comp_code == GT_EXPR 3043 && (!max 3044 || compare_values (val, max) == 0)) 3045 return false; 3046 3047 if (comp_code == LT_EXPR 3048 && (!min 3049 || compare_values (val, min) == 0)) 3050 return false; 3051 } 3052 *code_p = comp_code; 3053 *val_p = val; 3054 return true; 3055 } 3056 3057 /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any 3058 (otherwise return VAL). VAL and MASK must be zero-extended for 3059 precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT 3060 (to transform signed values into unsigned) and at the end xor 3061 SGNBIT back. */ 3062 3063 static wide_int 3064 masked_increment (const wide_int &val_in, const wide_int &mask, 3065 const wide_int &sgnbit, unsigned int prec) 3066 { 3067 wide_int bit = wi::one (prec), res; 3068 unsigned int i; 3069 3070 wide_int val = val_in ^ sgnbit; 3071 for (i = 0; i < prec; i++, bit += bit) 3072 { 3073 res = mask; 3074 if ((res & bit) == 0) 3075 continue; 3076 res = bit - 1; 3077 res = wi::bit_and_not (val + bit, res); 3078 res &= mask; 3079 if (wi::gtu_p (res, val)) 3080 return res ^ sgnbit; 3081 } 3082 return val ^ sgnbit; 3083 } 3084 3085 /* Helper for overflow_comparison_p 3086 3087 OP0 CODE OP1 is a comparison. Examine the comparison and potentially 3088 OP1's defining statement to see if it ultimately has the form 3089 OP0 CODE (OP0 PLUS INTEGER_CST) 3090 3091 If so, return TRUE indicating this is an overflow test and store into 3092 *NEW_CST an updated constant that can be used in a narrowed range test. 3093 3094 REVERSED indicates if the comparison was originally: 3095 3096 OP1 CODE' OP0. 3097 3098 This affects how we build the updated constant. */ 3099 3100 static bool 3101 overflow_comparison_p_1 (enum tree_code code, tree op0, tree op1, 3102 bool follow_assert_exprs, bool reversed, tree *new_cst) 3103 { 3104 /* See if this is a relational operation between two SSA_NAMES with 3105 unsigned, overflow wrapping values. If so, check it more deeply. */ 3106 if ((code == LT_EXPR || code == LE_EXPR 3107 || code == GE_EXPR || code == GT_EXPR) 3108 && TREE_CODE (op0) == SSA_NAME 3109 && TREE_CODE (op1) == SSA_NAME 3110 && INTEGRAL_TYPE_P (TREE_TYPE (op0)) 3111 && TYPE_UNSIGNED (TREE_TYPE (op0)) 3112 && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op0))) 3113 { 3114 gimple *op1_def = SSA_NAME_DEF_STMT (op1); 3115 3116 /* If requested, follow any ASSERT_EXPRs backwards for OP1. */ 3117 if (follow_assert_exprs) 3118 { 3119 while (gimple_assign_single_p (op1_def) 3120 && TREE_CODE (gimple_assign_rhs1 (op1_def)) == ASSERT_EXPR) 3121 { 3122 op1 = TREE_OPERAND (gimple_assign_rhs1 (op1_def), 0); 3123 if (TREE_CODE (op1) != SSA_NAME) 3124 break; 3125 op1_def = SSA_NAME_DEF_STMT (op1); 3126 } 3127 } 3128 3129 /* Now look at the defining statement of OP1 to see if it adds 3130 or subtracts a nonzero constant from another operand. */ 3131 if (op1_def 3132 && is_gimple_assign (op1_def) 3133 && gimple_assign_rhs_code (op1_def) == PLUS_EXPR 3134 && TREE_CODE (gimple_assign_rhs2 (op1_def)) == INTEGER_CST 3135 && !integer_zerop (gimple_assign_rhs2 (op1_def))) 3136 { 3137 tree target = gimple_assign_rhs1 (op1_def); 3138 3139 /* If requested, follow ASSERT_EXPRs backwards for op0 looking 3140 for one where TARGET appears on the RHS. */ 3141 if (follow_assert_exprs) 3142 { 3143 /* Now see if that "other operand" is op0, following the chain 3144 of ASSERT_EXPRs if necessary. */ 3145 gimple *op0_def = SSA_NAME_DEF_STMT (op0); 3146 while (op0 != target 3147 && gimple_assign_single_p (op0_def) 3148 && TREE_CODE (gimple_assign_rhs1 (op0_def)) == ASSERT_EXPR) 3149 { 3150 op0 = TREE_OPERAND (gimple_assign_rhs1 (op0_def), 0); 3151 if (TREE_CODE (op0) != SSA_NAME) 3152 break; 3153 op0_def = SSA_NAME_DEF_STMT (op0); 3154 } 3155 } 3156 3157 /* If we did not find our target SSA_NAME, then this is not 3158 an overflow test. */ 3159 if (op0 != target) 3160 return false; 3161 3162 tree type = TREE_TYPE (op0); 3163 wide_int max = wi::max_value (TYPE_PRECISION (type), UNSIGNED); 3164 tree inc = gimple_assign_rhs2 (op1_def); 3165 if (reversed) 3166 *new_cst = wide_int_to_tree (type, max + wi::to_wide (inc)); 3167 else 3168 *new_cst = wide_int_to_tree (type, max - wi::to_wide (inc)); 3169 return true; 3170 } 3171 } 3172 return false; 3173 } 3174 3175 /* OP0 CODE OP1 is a comparison. Examine the comparison and potentially 3176 OP1's defining statement to see if it ultimately has the form 3177 OP0 CODE (OP0 PLUS INTEGER_CST) 3178 3179 If so, return TRUE indicating this is an overflow test and store into 3180 *NEW_CST an updated constant that can be used in a narrowed range test. 3181 3182 These statements are left as-is in the IL to facilitate discovery of 3183 {ADD,SUB}_OVERFLOW sequences later in the optimizer pipeline. But 3184 the alternate range representation is often useful within VRP. */ 3185 3186 bool 3187 overflow_comparison_p (tree_code code, tree name, tree val, 3188 bool use_equiv_p, tree *new_cst) 3189 { 3190 if (overflow_comparison_p_1 (code, name, val, use_equiv_p, false, new_cst)) 3191 return true; 3192 return overflow_comparison_p_1 (swap_tree_comparison (code), val, name, 3193 use_equiv_p, true, new_cst); 3194 } 3195 3196 3197 /* Try to register an edge assertion for SSA name NAME on edge E for 3198 the condition COND contributing to the conditional jump pointed to by BSI. 3199 Invert the condition COND if INVERT is true. */ 3200 3201 static void 3202 register_edge_assert_for_2 (tree name, edge e, 3203 enum tree_code cond_code, 3204 tree cond_op0, tree cond_op1, bool invert, 3205 vec<assert_info> &asserts) 3206 { 3207 tree val; 3208 enum tree_code comp_code; 3209 3210 if (!extract_code_and_val_from_cond_with_ops (name, cond_code, 3211 cond_op0, 3212 cond_op1, 3213 invert, &comp_code, &val)) 3214 return; 3215 3216 /* Queue the assert. */ 3217 tree x; 3218 if (overflow_comparison_p (comp_code, name, val, false, &x)) 3219 { 3220 enum tree_code new_code = ((comp_code == GT_EXPR || comp_code == GE_EXPR) 3221 ? GT_EXPR : LE_EXPR); 3222 add_assert_info (asserts, name, name, new_code, x); 3223 } 3224 add_assert_info (asserts, name, name, comp_code, val); 3225 3226 /* In the case of NAME <= CST and NAME being defined as 3227 NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2 3228 and NAME2 <= CST - CST2. We can do the same for NAME > CST. 3229 This catches range and anti-range tests. */ 3230 if ((comp_code == LE_EXPR 3231 || comp_code == GT_EXPR) 3232 && TREE_CODE (val) == INTEGER_CST 3233 && TYPE_UNSIGNED (TREE_TYPE (val))) 3234 { 3235 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 3236 tree cst2 = NULL_TREE, name2 = NULL_TREE, name3 = NULL_TREE; 3237 3238 /* Extract CST2 from the (optional) addition. */ 3239 if (is_gimple_assign (def_stmt) 3240 && gimple_assign_rhs_code (def_stmt) == PLUS_EXPR) 3241 { 3242 name2 = gimple_assign_rhs1 (def_stmt); 3243 cst2 = gimple_assign_rhs2 (def_stmt); 3244 if (TREE_CODE (name2) == SSA_NAME 3245 && TREE_CODE (cst2) == INTEGER_CST) 3246 def_stmt = SSA_NAME_DEF_STMT (name2); 3247 } 3248 3249 /* Extract NAME2 from the (optional) sign-changing cast. */ 3250 if (gimple_assign_cast_p (def_stmt)) 3251 { 3252 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)) 3253 && ! TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def_stmt))) 3254 && (TYPE_PRECISION (gimple_expr_type (def_stmt)) 3255 == TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))) 3256 name3 = gimple_assign_rhs1 (def_stmt); 3257 } 3258 3259 /* If name3 is used later, create an ASSERT_EXPR for it. */ 3260 if (name3 != NULL_TREE 3261 && TREE_CODE (name3) == SSA_NAME 3262 && (cst2 == NULL_TREE 3263 || TREE_CODE (cst2) == INTEGER_CST) 3264 && INTEGRAL_TYPE_P (TREE_TYPE (name3))) 3265 { 3266 tree tmp; 3267 3268 /* Build an expression for the range test. */ 3269 tmp = build1 (NOP_EXPR, TREE_TYPE (name), name3); 3270 if (cst2 != NULL_TREE) 3271 tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2); 3272 3273 if (dump_file) 3274 { 3275 fprintf (dump_file, "Adding assert for "); 3276 print_generic_expr (dump_file, name3); 3277 fprintf (dump_file, " from "); 3278 print_generic_expr (dump_file, tmp); 3279 fprintf (dump_file, "\n"); 3280 } 3281 3282 add_assert_info (asserts, name3, tmp, comp_code, val); 3283 } 3284 3285 /* If name2 is used later, create an ASSERT_EXPR for it. */ 3286 if (name2 != NULL_TREE 3287 && TREE_CODE (name2) == SSA_NAME 3288 && TREE_CODE (cst2) == INTEGER_CST 3289 && INTEGRAL_TYPE_P (TREE_TYPE (name2))) 3290 { 3291 tree tmp; 3292 3293 /* Build an expression for the range test. */ 3294 tmp = name2; 3295 if (TREE_TYPE (name) != TREE_TYPE (name2)) 3296 tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp); 3297 if (cst2 != NULL_TREE) 3298 tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2); 3299 3300 if (dump_file) 3301 { 3302 fprintf (dump_file, "Adding assert for "); 3303 print_generic_expr (dump_file, name2); 3304 fprintf (dump_file, " from "); 3305 print_generic_expr (dump_file, tmp); 3306 fprintf (dump_file, "\n"); 3307 } 3308 3309 add_assert_info (asserts, name2, tmp, comp_code, val); 3310 } 3311 } 3312 3313 /* In the case of post-in/decrement tests like if (i++) ... and uses 3314 of the in/decremented value on the edge the extra name we want to 3315 assert for is not on the def chain of the name compared. Instead 3316 it is in the set of use stmts. 3317 Similar cases happen for conversions that were simplified through 3318 fold_{sign_changed,widened}_comparison. */ 3319 if ((comp_code == NE_EXPR 3320 || comp_code == EQ_EXPR) 3321 && TREE_CODE (val) == INTEGER_CST) 3322 { 3323 imm_use_iterator ui; 3324 gimple *use_stmt; 3325 FOR_EACH_IMM_USE_STMT (use_stmt, ui, name) 3326 { 3327 if (!is_gimple_assign (use_stmt)) 3328 continue; 3329 3330 /* Cut off to use-stmts that are dominating the predecessor. */ 3331 if (!dominated_by_p (CDI_DOMINATORS, e->src, gimple_bb (use_stmt))) 3332 continue; 3333 3334 tree name2 = gimple_assign_lhs (use_stmt); 3335 if (TREE_CODE (name2) != SSA_NAME) 3336 continue; 3337 3338 enum tree_code code = gimple_assign_rhs_code (use_stmt); 3339 tree cst; 3340 if (code == PLUS_EXPR 3341 || code == MINUS_EXPR) 3342 { 3343 cst = gimple_assign_rhs2 (use_stmt); 3344 if (TREE_CODE (cst) != INTEGER_CST) 3345 continue; 3346 cst = int_const_binop (code, val, cst); 3347 } 3348 else if (CONVERT_EXPR_CODE_P (code)) 3349 { 3350 /* For truncating conversions we cannot record 3351 an inequality. */ 3352 if (comp_code == NE_EXPR 3353 && (TYPE_PRECISION (TREE_TYPE (name2)) 3354 < TYPE_PRECISION (TREE_TYPE (name)))) 3355 continue; 3356 cst = fold_convert (TREE_TYPE (name2), val); 3357 } 3358 else 3359 continue; 3360 3361 if (TREE_OVERFLOW_P (cst)) 3362 cst = drop_tree_overflow (cst); 3363 add_assert_info (asserts, name2, name2, comp_code, cst); 3364 } 3365 } 3366 3367 if (TREE_CODE_CLASS (comp_code) == tcc_comparison 3368 && TREE_CODE (val) == INTEGER_CST) 3369 { 3370 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 3371 tree name2 = NULL_TREE, names[2], cst2 = NULL_TREE; 3372 tree val2 = NULL_TREE; 3373 unsigned int prec = TYPE_PRECISION (TREE_TYPE (val)); 3374 wide_int mask = wi::zero (prec); 3375 unsigned int nprec = prec; 3376 enum tree_code rhs_code = ERROR_MARK; 3377 3378 if (is_gimple_assign (def_stmt)) 3379 rhs_code = gimple_assign_rhs_code (def_stmt); 3380 3381 /* In the case of NAME != CST1 where NAME = A +- CST2 we can 3382 assert that A != CST1 -+ CST2. */ 3383 if ((comp_code == EQ_EXPR || comp_code == NE_EXPR) 3384 && (rhs_code == PLUS_EXPR || rhs_code == MINUS_EXPR)) 3385 { 3386 tree op0 = gimple_assign_rhs1 (def_stmt); 3387 tree op1 = gimple_assign_rhs2 (def_stmt); 3388 if (TREE_CODE (op0) == SSA_NAME 3389 && TREE_CODE (op1) == INTEGER_CST) 3390 { 3391 enum tree_code reverse_op = (rhs_code == PLUS_EXPR 3392 ? MINUS_EXPR : PLUS_EXPR); 3393 op1 = int_const_binop (reverse_op, val, op1); 3394 if (TREE_OVERFLOW (op1)) 3395 op1 = drop_tree_overflow (op1); 3396 add_assert_info (asserts, op0, op0, comp_code, op1); 3397 } 3398 } 3399 3400 /* Add asserts for NAME cmp CST and NAME being defined 3401 as NAME = (int) NAME2. */ 3402 if (!TYPE_UNSIGNED (TREE_TYPE (val)) 3403 && (comp_code == LE_EXPR || comp_code == LT_EXPR 3404 || comp_code == GT_EXPR || comp_code == GE_EXPR) 3405 && gimple_assign_cast_p (def_stmt)) 3406 { 3407 name2 = gimple_assign_rhs1 (def_stmt); 3408 if (CONVERT_EXPR_CODE_P (rhs_code) 3409 && INTEGRAL_TYPE_P (TREE_TYPE (name2)) 3410 && TYPE_UNSIGNED (TREE_TYPE (name2)) 3411 && prec == TYPE_PRECISION (TREE_TYPE (name2)) 3412 && (comp_code == LE_EXPR || comp_code == GT_EXPR 3413 || !tree_int_cst_equal (val, 3414 TYPE_MIN_VALUE (TREE_TYPE (val))))) 3415 { 3416 tree tmp, cst; 3417 enum tree_code new_comp_code = comp_code; 3418 3419 cst = fold_convert (TREE_TYPE (name2), 3420 TYPE_MIN_VALUE (TREE_TYPE (val))); 3421 /* Build an expression for the range test. */ 3422 tmp = build2 (PLUS_EXPR, TREE_TYPE (name2), name2, cst); 3423 cst = fold_build2 (PLUS_EXPR, TREE_TYPE (name2), cst, 3424 fold_convert (TREE_TYPE (name2), val)); 3425 if (comp_code == LT_EXPR || comp_code == GE_EXPR) 3426 { 3427 new_comp_code = comp_code == LT_EXPR ? LE_EXPR : GT_EXPR; 3428 cst = fold_build2 (MINUS_EXPR, TREE_TYPE (name2), cst, 3429 build_int_cst (TREE_TYPE (name2), 1)); 3430 } 3431 3432 if (dump_file) 3433 { 3434 fprintf (dump_file, "Adding assert for "); 3435 print_generic_expr (dump_file, name2); 3436 fprintf (dump_file, " from "); 3437 print_generic_expr (dump_file, tmp); 3438 fprintf (dump_file, "\n"); 3439 } 3440 3441 add_assert_info (asserts, name2, tmp, new_comp_code, cst); 3442 } 3443 } 3444 3445 /* Add asserts for NAME cmp CST and NAME being defined as 3446 NAME = NAME2 >> CST2. 3447 3448 Extract CST2 from the right shift. */ 3449 if (rhs_code == RSHIFT_EXPR) 3450 { 3451 name2 = gimple_assign_rhs1 (def_stmt); 3452 cst2 = gimple_assign_rhs2 (def_stmt); 3453 if (TREE_CODE (name2) == SSA_NAME 3454 && tree_fits_uhwi_p (cst2) 3455 && INTEGRAL_TYPE_P (TREE_TYPE (name2)) 3456 && IN_RANGE (tree_to_uhwi (cst2), 1, prec - 1) 3457 && type_has_mode_precision_p (TREE_TYPE (val))) 3458 { 3459 mask = wi::mask (tree_to_uhwi (cst2), false, prec); 3460 val2 = fold_binary (LSHIFT_EXPR, TREE_TYPE (val), val, cst2); 3461 } 3462 } 3463 if (val2 != NULL_TREE 3464 && TREE_CODE (val2) == INTEGER_CST 3465 && simple_cst_equal (fold_build2 (RSHIFT_EXPR, 3466 TREE_TYPE (val), 3467 val2, cst2), val)) 3468 { 3469 enum tree_code new_comp_code = comp_code; 3470 tree tmp, new_val; 3471 3472 tmp = name2; 3473 if (comp_code == EQ_EXPR || comp_code == NE_EXPR) 3474 { 3475 if (!TYPE_UNSIGNED (TREE_TYPE (val))) 3476 { 3477 tree type = build_nonstandard_integer_type (prec, 1); 3478 tmp = build1 (NOP_EXPR, type, name2); 3479 val2 = fold_convert (type, val2); 3480 } 3481 tmp = fold_build2 (MINUS_EXPR, TREE_TYPE (tmp), tmp, val2); 3482 new_val = wide_int_to_tree (TREE_TYPE (tmp), mask); 3483 new_comp_code = comp_code == EQ_EXPR ? LE_EXPR : GT_EXPR; 3484 } 3485 else if (comp_code == LT_EXPR || comp_code == GE_EXPR) 3486 { 3487 wide_int minval 3488 = wi::min_value (prec, TYPE_SIGN (TREE_TYPE (val))); 3489 new_val = val2; 3490 if (minval == wi::to_wide (new_val)) 3491 new_val = NULL_TREE; 3492 } 3493 else 3494 { 3495 wide_int maxval 3496 = wi::max_value (prec, TYPE_SIGN (TREE_TYPE (val))); 3497 mask |= wi::to_wide (val2); 3498 if (wi::eq_p (mask, maxval)) 3499 new_val = NULL_TREE; 3500 else 3501 new_val = wide_int_to_tree (TREE_TYPE (val2), mask); 3502 } 3503 3504 if (new_val) 3505 { 3506 if (dump_file) 3507 { 3508 fprintf (dump_file, "Adding assert for "); 3509 print_generic_expr (dump_file, name2); 3510 fprintf (dump_file, " from "); 3511 print_generic_expr (dump_file, tmp); 3512 fprintf (dump_file, "\n"); 3513 } 3514 3515 add_assert_info (asserts, name2, tmp, new_comp_code, new_val); 3516 } 3517 } 3518 3519 /* Add asserts for NAME cmp CST and NAME being defined as 3520 NAME = NAME2 & CST2. 3521 3522 Extract CST2 from the and. 3523 3524 Also handle 3525 NAME = (unsigned) NAME2; 3526 casts where NAME's type is unsigned and has smaller precision 3527 than NAME2's type as if it was NAME = NAME2 & MASK. */ 3528 names[0] = NULL_TREE; 3529 names[1] = NULL_TREE; 3530 cst2 = NULL_TREE; 3531 if (rhs_code == BIT_AND_EXPR 3532 || (CONVERT_EXPR_CODE_P (rhs_code) 3533 && INTEGRAL_TYPE_P (TREE_TYPE (val)) 3534 && TYPE_UNSIGNED (TREE_TYPE (val)) 3535 && TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))) 3536 > prec)) 3537 { 3538 name2 = gimple_assign_rhs1 (def_stmt); 3539 if (rhs_code == BIT_AND_EXPR) 3540 cst2 = gimple_assign_rhs2 (def_stmt); 3541 else 3542 { 3543 cst2 = TYPE_MAX_VALUE (TREE_TYPE (val)); 3544 nprec = TYPE_PRECISION (TREE_TYPE (name2)); 3545 } 3546 if (TREE_CODE (name2) == SSA_NAME 3547 && INTEGRAL_TYPE_P (TREE_TYPE (name2)) 3548 && TREE_CODE (cst2) == INTEGER_CST 3549 && !integer_zerop (cst2) 3550 && (nprec > 1 3551 || TYPE_UNSIGNED (TREE_TYPE (val)))) 3552 { 3553 gimple *def_stmt2 = SSA_NAME_DEF_STMT (name2); 3554 if (gimple_assign_cast_p (def_stmt2)) 3555 { 3556 names[1] = gimple_assign_rhs1 (def_stmt2); 3557 if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt2)) 3558 || !INTEGRAL_TYPE_P (TREE_TYPE (names[1])) 3559 || (TYPE_PRECISION (TREE_TYPE (name2)) 3560 != TYPE_PRECISION (TREE_TYPE (names[1])))) 3561 names[1] = NULL_TREE; 3562 } 3563 names[0] = name2; 3564 } 3565 } 3566 if (names[0] || names[1]) 3567 { 3568 wide_int minv, maxv, valv, cst2v; 3569 wide_int tem, sgnbit; 3570 bool valid_p = false, valn, cst2n; 3571 enum tree_code ccode = comp_code; 3572 3573 valv = wide_int::from (wi::to_wide (val), nprec, UNSIGNED); 3574 cst2v = wide_int::from (wi::to_wide (cst2), nprec, UNSIGNED); 3575 valn = wi::neg_p (valv, TYPE_SIGN (TREE_TYPE (val))); 3576 cst2n = wi::neg_p (cst2v, TYPE_SIGN (TREE_TYPE (val))); 3577 /* If CST2 doesn't have most significant bit set, 3578 but VAL is negative, we have comparison like 3579 if ((x & 0x123) > -4) (always true). Just give up. */ 3580 if (!cst2n && valn) 3581 ccode = ERROR_MARK; 3582 if (cst2n) 3583 sgnbit = wi::set_bit_in_zero (nprec - 1, nprec); 3584 else 3585 sgnbit = wi::zero (nprec); 3586 minv = valv & cst2v; 3587 switch (ccode) 3588 { 3589 case EQ_EXPR: 3590 /* Minimum unsigned value for equality is VAL & CST2 3591 (should be equal to VAL, otherwise we probably should 3592 have folded the comparison into false) and 3593 maximum unsigned value is VAL | ~CST2. */ 3594 maxv = valv | ~cst2v; 3595 valid_p = true; 3596 break; 3597 3598 case NE_EXPR: 3599 tem = valv | ~cst2v; 3600 /* If VAL is 0, handle (X & CST2) != 0 as (X & CST2) > 0U. */ 3601 if (valv == 0) 3602 { 3603 cst2n = false; 3604 sgnbit = wi::zero (nprec); 3605 goto gt_expr; 3606 } 3607 /* If (VAL | ~CST2) is all ones, handle it as 3608 (X & CST2) < VAL. */ 3609 if (tem == -1) 3610 { 3611 cst2n = false; 3612 valn = false; 3613 sgnbit = wi::zero (nprec); 3614 goto lt_expr; 3615 } 3616 if (!cst2n && wi::neg_p (cst2v)) 3617 sgnbit = wi::set_bit_in_zero (nprec - 1, nprec); 3618 if (sgnbit != 0) 3619 { 3620 if (valv == sgnbit) 3621 { 3622 cst2n = true; 3623 valn = true; 3624 goto gt_expr; 3625 } 3626 if (tem == wi::mask (nprec - 1, false, nprec)) 3627 { 3628 cst2n = true; 3629 goto lt_expr; 3630 } 3631 if (!cst2n) 3632 sgnbit = wi::zero (nprec); 3633 } 3634 break; 3635 3636 case GE_EXPR: 3637 /* Minimum unsigned value for >= if (VAL & CST2) == VAL 3638 is VAL and maximum unsigned value is ~0. For signed 3639 comparison, if CST2 doesn't have most significant bit 3640 set, handle it similarly. If CST2 has MSB set, 3641 the minimum is the same, and maximum is ~0U/2. */ 3642 if (minv != valv) 3643 { 3644 /* If (VAL & CST2) != VAL, X & CST2 can't be equal to 3645 VAL. */ 3646 minv = masked_increment (valv, cst2v, sgnbit, nprec); 3647 if (minv == valv) 3648 break; 3649 } 3650 maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec); 3651 valid_p = true; 3652 break; 3653 3654 case GT_EXPR: 3655 gt_expr: 3656 /* Find out smallest MINV where MINV > VAL 3657 && (MINV & CST2) == MINV, if any. If VAL is signed and 3658 CST2 has MSB set, compute it biased by 1 << (nprec - 1). */ 3659 minv = masked_increment (valv, cst2v, sgnbit, nprec); 3660 if (minv == valv) 3661 break; 3662 maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec); 3663 valid_p = true; 3664 break; 3665 3666 case LE_EXPR: 3667 /* Minimum unsigned value for <= is 0 and maximum 3668 unsigned value is VAL | ~CST2 if (VAL & CST2) == VAL. 3669 Otherwise, find smallest VAL2 where VAL2 > VAL 3670 && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2 3671 as maximum. 3672 For signed comparison, if CST2 doesn't have most 3673 significant bit set, handle it similarly. If CST2 has 3674 MSB set, the maximum is the same and minimum is INT_MIN. */ 3675 if (minv == valv) 3676 maxv = valv; 3677 else 3678 { 3679 maxv = masked_increment (valv, cst2v, sgnbit, nprec); 3680 if (maxv == valv) 3681 break; 3682 maxv -= 1; 3683 } 3684 maxv |= ~cst2v; 3685 minv = sgnbit; 3686 valid_p = true; 3687 break; 3688 3689 case LT_EXPR: 3690 lt_expr: 3691 /* Minimum unsigned value for < is 0 and maximum 3692 unsigned value is (VAL-1) | ~CST2 if (VAL & CST2) == VAL. 3693 Otherwise, find smallest VAL2 where VAL2 > VAL 3694 && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2 3695 as maximum. 3696 For signed comparison, if CST2 doesn't have most 3697 significant bit set, handle it similarly. If CST2 has 3698 MSB set, the maximum is the same and minimum is INT_MIN. */ 3699 if (minv == valv) 3700 { 3701 if (valv == sgnbit) 3702 break; 3703 maxv = valv; 3704 } 3705 else 3706 { 3707 maxv = masked_increment (valv, cst2v, sgnbit, nprec); 3708 if (maxv == valv) 3709 break; 3710 } 3711 maxv -= 1; 3712 maxv |= ~cst2v; 3713 minv = sgnbit; 3714 valid_p = true; 3715 break; 3716 3717 default: 3718 break; 3719 } 3720 if (valid_p 3721 && (maxv - minv) != -1) 3722 { 3723 tree tmp, new_val, type; 3724 int i; 3725 3726 for (i = 0; i < 2; i++) 3727 if (names[i]) 3728 { 3729 wide_int maxv2 = maxv; 3730 tmp = names[i]; 3731 type = TREE_TYPE (names[i]); 3732 if (!TYPE_UNSIGNED (type)) 3733 { 3734 type = build_nonstandard_integer_type (nprec, 1); 3735 tmp = build1 (NOP_EXPR, type, names[i]); 3736 } 3737 if (minv != 0) 3738 { 3739 tmp = build2 (PLUS_EXPR, type, tmp, 3740 wide_int_to_tree (type, -minv)); 3741 maxv2 = maxv - minv; 3742 } 3743 new_val = wide_int_to_tree (type, maxv2); 3744 3745 if (dump_file) 3746 { 3747 fprintf (dump_file, "Adding assert for "); 3748 print_generic_expr (dump_file, names[i]); 3749 fprintf (dump_file, " from "); 3750 print_generic_expr (dump_file, tmp); 3751 fprintf (dump_file, "\n"); 3752 } 3753 3754 add_assert_info (asserts, names[i], tmp, LE_EXPR, new_val); 3755 } 3756 } 3757 } 3758 } 3759 } 3760 3761 /* OP is an operand of a truth value expression which is known to have 3762 a particular value. Register any asserts for OP and for any 3763 operands in OP's defining statement. 3764 3765 If CODE is EQ_EXPR, then we want to register OP is zero (false), 3766 if CODE is NE_EXPR, then we want to register OP is nonzero (true). */ 3767 3768 static void 3769 register_edge_assert_for_1 (tree op, enum tree_code code, 3770 edge e, vec<assert_info> &asserts) 3771 { 3772 gimple *op_def; 3773 tree val; 3774 enum tree_code rhs_code; 3775 3776 /* We only care about SSA_NAMEs. */ 3777 if (TREE_CODE (op) != SSA_NAME) 3778 return; 3779 3780 /* We know that OP will have a zero or nonzero value. */ 3781 val = build_int_cst (TREE_TYPE (op), 0); 3782 add_assert_info (asserts, op, op, code, val); 3783 3784 /* Now look at how OP is set. If it's set from a comparison, 3785 a truth operation or some bit operations, then we may be able 3786 to register information about the operands of that assignment. */ 3787 op_def = SSA_NAME_DEF_STMT (op); 3788 if (gimple_code (op_def) != GIMPLE_ASSIGN) 3789 return; 3790 3791 rhs_code = gimple_assign_rhs_code (op_def); 3792 3793 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison) 3794 { 3795 bool invert = (code == EQ_EXPR ? true : false); 3796 tree op0 = gimple_assign_rhs1 (op_def); 3797 tree op1 = gimple_assign_rhs2 (op_def); 3798 3799 if (TREE_CODE (op0) == SSA_NAME) 3800 register_edge_assert_for_2 (op0, e, rhs_code, op0, op1, invert, asserts); 3801 if (TREE_CODE (op1) == SSA_NAME) 3802 register_edge_assert_for_2 (op1, e, rhs_code, op0, op1, invert, asserts); 3803 } 3804 else if ((code == NE_EXPR 3805 && gimple_assign_rhs_code (op_def) == BIT_AND_EXPR) 3806 || (code == EQ_EXPR 3807 && gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR)) 3808 { 3809 /* Recurse on each operand. */ 3810 tree op0 = gimple_assign_rhs1 (op_def); 3811 tree op1 = gimple_assign_rhs2 (op_def); 3812 if (TREE_CODE (op0) == SSA_NAME 3813 && has_single_use (op0)) 3814 register_edge_assert_for_1 (op0, code, e, asserts); 3815 if (TREE_CODE (op1) == SSA_NAME 3816 && has_single_use (op1)) 3817 register_edge_assert_for_1 (op1, code, e, asserts); 3818 } 3819 else if (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR 3820 && TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (op_def))) == 1) 3821 { 3822 /* Recurse, flipping CODE. */ 3823 code = invert_tree_comparison (code, false); 3824 register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e, asserts); 3825 } 3826 else if (gimple_assign_rhs_code (op_def) == SSA_NAME) 3827 { 3828 /* Recurse through the copy. */ 3829 register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e, asserts); 3830 } 3831 else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def))) 3832 { 3833 /* Recurse through the type conversion, unless it is a narrowing 3834 conversion or conversion from non-integral type. */ 3835 tree rhs = gimple_assign_rhs1 (op_def); 3836 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs)) 3837 && (TYPE_PRECISION (TREE_TYPE (rhs)) 3838 <= TYPE_PRECISION (TREE_TYPE (op)))) 3839 register_edge_assert_for_1 (rhs, code, e, asserts); 3840 } 3841 } 3842 3843 /* Check if comparison 3844 NAME COND_OP INTEGER_CST 3845 has a form of 3846 (X & 11...100..0) COND_OP XX...X00...0 3847 Such comparison can yield assertions like 3848 X >= XX...X00...0 3849 X <= XX...X11...1 3850 in case of COND_OP being EQ_EXPR or 3851 X < XX...X00...0 3852 X > XX...X11...1 3853 in case of NE_EXPR. */ 3854 3855 static bool 3856 is_masked_range_test (tree name, tree valt, enum tree_code cond_code, 3857 tree *new_name, tree *low, enum tree_code *low_code, 3858 tree *high, enum tree_code *high_code) 3859 { 3860 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 3861 3862 if (!is_gimple_assign (def_stmt) 3863 || gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR) 3864 return false; 3865 3866 tree t = gimple_assign_rhs1 (def_stmt); 3867 tree maskt = gimple_assign_rhs2 (def_stmt); 3868 if (TREE_CODE (t) != SSA_NAME || TREE_CODE (maskt) != INTEGER_CST) 3869 return false; 3870 3871 wi::tree_to_wide_ref mask = wi::to_wide (maskt); 3872 wide_int inv_mask = ~mask; 3873 /* Must have been removed by now so don't bother optimizing. */ 3874 if (mask == 0 || inv_mask == 0) 3875 return false; 3876 3877 /* Assume VALT is INTEGER_CST. */ 3878 wi::tree_to_wide_ref val = wi::to_wide (valt); 3879 3880 if ((inv_mask & (inv_mask + 1)) != 0 3881 || (val & mask) != val) 3882 return false; 3883 3884 bool is_range = cond_code == EQ_EXPR; 3885 3886 tree type = TREE_TYPE (t); 3887 wide_int min = wi::min_value (type), 3888 max = wi::max_value (type); 3889 3890 if (is_range) 3891 { 3892 *low_code = val == min ? ERROR_MARK : GE_EXPR; 3893 *high_code = val == max ? ERROR_MARK : LE_EXPR; 3894 } 3895 else 3896 { 3897 /* We can still generate assertion if one of alternatives 3898 is known to always be false. */ 3899 if (val == min) 3900 { 3901 *low_code = (enum tree_code) 0; 3902 *high_code = GT_EXPR; 3903 } 3904 else if ((val | inv_mask) == max) 3905 { 3906 *low_code = LT_EXPR; 3907 *high_code = (enum tree_code) 0; 3908 } 3909 else 3910 return false; 3911 } 3912 3913 *new_name = t; 3914 *low = wide_int_to_tree (type, val); 3915 *high = wide_int_to_tree (type, val | inv_mask); 3916 3917 return true; 3918 } 3919 3920 /* Try to register an edge assertion for SSA name NAME on edge E for 3921 the condition COND contributing to the conditional jump pointed to by 3922 SI. */ 3923 3924 void 3925 register_edge_assert_for (tree name, edge e, 3926 enum tree_code cond_code, tree cond_op0, 3927 tree cond_op1, vec<assert_info> &asserts) 3928 { 3929 tree val; 3930 enum tree_code comp_code; 3931 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0; 3932 3933 /* Do not attempt to infer anything in names that flow through 3934 abnormal edges. */ 3935 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 3936 return; 3937 3938 if (!extract_code_and_val_from_cond_with_ops (name, cond_code, 3939 cond_op0, cond_op1, 3940 is_else_edge, 3941 &comp_code, &val)) 3942 return; 3943 3944 /* Register ASSERT_EXPRs for name. */ 3945 register_edge_assert_for_2 (name, e, cond_code, cond_op0, 3946 cond_op1, is_else_edge, asserts); 3947 3948 3949 /* If COND is effectively an equality test of an SSA_NAME against 3950 the value zero or one, then we may be able to assert values 3951 for SSA_NAMEs which flow into COND. */ 3952 3953 /* In the case of NAME == 1 or NAME != 0, for BIT_AND_EXPR defining 3954 statement of NAME we can assert both operands of the BIT_AND_EXPR 3955 have nonzero value. */ 3956 if (((comp_code == EQ_EXPR && integer_onep (val)) 3957 || (comp_code == NE_EXPR && integer_zerop (val)))) 3958 { 3959 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 3960 3961 if (is_gimple_assign (def_stmt) 3962 && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR) 3963 { 3964 tree op0 = gimple_assign_rhs1 (def_stmt); 3965 tree op1 = gimple_assign_rhs2 (def_stmt); 3966 register_edge_assert_for_1 (op0, NE_EXPR, e, asserts); 3967 register_edge_assert_for_1 (op1, NE_EXPR, e, asserts); 3968 } 3969 } 3970 3971 /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining 3972 statement of NAME we can assert both operands of the BIT_IOR_EXPR 3973 have zero value. */ 3974 if (((comp_code == EQ_EXPR && integer_zerop (val)) 3975 || (comp_code == NE_EXPR && integer_onep (val)))) 3976 { 3977 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 3978 3979 /* For BIT_IOR_EXPR only if NAME == 0 both operands have 3980 necessarily zero value, or if type-precision is one. */ 3981 if (is_gimple_assign (def_stmt) 3982 && (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR 3983 && (TYPE_PRECISION (TREE_TYPE (name)) == 1 3984 || comp_code == EQ_EXPR))) 3985 { 3986 tree op0 = gimple_assign_rhs1 (def_stmt); 3987 tree op1 = gimple_assign_rhs2 (def_stmt); 3988 register_edge_assert_for_1 (op0, EQ_EXPR, e, asserts); 3989 register_edge_assert_for_1 (op1, EQ_EXPR, e, asserts); 3990 } 3991 } 3992 3993 /* Sometimes we can infer ranges from (NAME & MASK) == VALUE. */ 3994 if ((comp_code == EQ_EXPR || comp_code == NE_EXPR) 3995 && TREE_CODE (val) == INTEGER_CST) 3996 { 3997 enum tree_code low_code, high_code; 3998 tree low, high; 3999 if (is_masked_range_test (name, val, comp_code, &name, &low, 4000 &low_code, &high, &high_code)) 4001 { 4002 if (low_code != ERROR_MARK) 4003 register_edge_assert_for_2 (name, e, low_code, name, 4004 low, /*invert*/false, asserts); 4005 if (high_code != ERROR_MARK) 4006 register_edge_assert_for_2 (name, e, high_code, name, 4007 high, /*invert*/false, asserts); 4008 } 4009 } 4010 } 4011 4012 /* Finish found ASSERTS for E and register them at GSI. */ 4013 4014 static void 4015 finish_register_edge_assert_for (edge e, gimple_stmt_iterator gsi, 4016 vec<assert_info> &asserts) 4017 { 4018 for (unsigned i = 0; i < asserts.length (); ++i) 4019 /* Only register an ASSERT_EXPR if NAME was found in the sub-graph 4020 reachable from E. */ 4021 if (live_on_edge (e, asserts[i].name)) 4022 register_new_assert_for (asserts[i].name, asserts[i].expr, 4023 asserts[i].comp_code, asserts[i].val, 4024 NULL, e, gsi); 4025 } 4026 4027 4028 4029 /* Determine whether the outgoing edges of BB should receive an 4030 ASSERT_EXPR for each of the operands of BB's LAST statement. 4031 The last statement of BB must be a COND_EXPR. 4032 4033 If any of the sub-graphs rooted at BB have an interesting use of 4034 the predicate operands, an assert location node is added to the 4035 list of assertions for the corresponding operands. */ 4036 4037 static void 4038 find_conditional_asserts (basic_block bb, gcond *last) 4039 { 4040 gimple_stmt_iterator bsi; 4041 tree op; 4042 edge_iterator ei; 4043 edge e; 4044 ssa_op_iter iter; 4045 4046 bsi = gsi_for_stmt (last); 4047 4048 /* Look for uses of the operands in each of the sub-graphs 4049 rooted at BB. We need to check each of the outgoing edges 4050 separately, so that we know what kind of ASSERT_EXPR to 4051 insert. */ 4052 FOR_EACH_EDGE (e, ei, bb->succs) 4053 { 4054 if (e->dest == bb) 4055 continue; 4056 4057 /* Register the necessary assertions for each operand in the 4058 conditional predicate. */ 4059 auto_vec<assert_info, 8> asserts; 4060 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 4061 register_edge_assert_for (op, e, 4062 gimple_cond_code (last), 4063 gimple_cond_lhs (last), 4064 gimple_cond_rhs (last), asserts); 4065 finish_register_edge_assert_for (e, bsi, asserts); 4066 } 4067 } 4068 4069 struct case_info 4070 { 4071 tree expr; 4072 basic_block bb; 4073 }; 4074 4075 /* Compare two case labels sorting first by the destination bb index 4076 and then by the case value. */ 4077 4078 static int 4079 compare_case_labels (const void *p1, const void *p2) 4080 { 4081 const struct case_info *ci1 = (const struct case_info *) p1; 4082 const struct case_info *ci2 = (const struct case_info *) p2; 4083 int idx1 = ci1->bb->index; 4084 int idx2 = ci2->bb->index; 4085 4086 if (idx1 < idx2) 4087 return -1; 4088 else if (idx1 == idx2) 4089 { 4090 /* Make sure the default label is first in a group. */ 4091 if (!CASE_LOW (ci1->expr)) 4092 return -1; 4093 else if (!CASE_LOW (ci2->expr)) 4094 return 1; 4095 else 4096 return tree_int_cst_compare (CASE_LOW (ci1->expr), 4097 CASE_LOW (ci2->expr)); 4098 } 4099 else 4100 return 1; 4101 } 4102 4103 /* Determine whether the outgoing edges of BB should receive an 4104 ASSERT_EXPR for each of the operands of BB's LAST statement. 4105 The last statement of BB must be a SWITCH_EXPR. 4106 4107 If any of the sub-graphs rooted at BB have an interesting use of 4108 the predicate operands, an assert location node is added to the 4109 list of assertions for the corresponding operands. */ 4110 4111 static void 4112 find_switch_asserts (basic_block bb, gswitch *last) 4113 { 4114 gimple_stmt_iterator bsi; 4115 tree op; 4116 edge e; 4117 struct case_info *ci; 4118 size_t n = gimple_switch_num_labels (last); 4119 #if GCC_VERSION >= 4000 4120 unsigned int idx; 4121 #else 4122 /* Work around GCC 3.4 bug (PR 37086). */ 4123 volatile unsigned int idx; 4124 #endif 4125 4126 bsi = gsi_for_stmt (last); 4127 op = gimple_switch_index (last); 4128 if (TREE_CODE (op) != SSA_NAME) 4129 return; 4130 4131 /* Build a vector of case labels sorted by destination label. */ 4132 ci = XNEWVEC (struct case_info, n); 4133 for (idx = 0; idx < n; ++idx) 4134 { 4135 ci[idx].expr = gimple_switch_label (last, idx); 4136 ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr)); 4137 } 4138 edge default_edge = find_edge (bb, ci[0].bb); 4139 qsort (ci, n, sizeof (struct case_info), compare_case_labels); 4140 4141 for (idx = 0; idx < n; ++idx) 4142 { 4143 tree min, max; 4144 tree cl = ci[idx].expr; 4145 basic_block cbb = ci[idx].bb; 4146 4147 min = CASE_LOW (cl); 4148 max = CASE_HIGH (cl); 4149 4150 /* If there are multiple case labels with the same destination 4151 we need to combine them to a single value range for the edge. */ 4152 if (idx + 1 < n && cbb == ci[idx + 1].bb) 4153 { 4154 /* Skip labels until the last of the group. */ 4155 do { 4156 ++idx; 4157 } while (idx < n && cbb == ci[idx].bb); 4158 --idx; 4159 4160 /* Pick up the maximum of the case label range. */ 4161 if (CASE_HIGH (ci[idx].expr)) 4162 max = CASE_HIGH (ci[idx].expr); 4163 else 4164 max = CASE_LOW (ci[idx].expr); 4165 } 4166 4167 /* Can't extract a useful assertion out of a range that includes the 4168 default label. */ 4169 if (min == NULL_TREE) 4170 continue; 4171 4172 /* Find the edge to register the assert expr on. */ 4173 e = find_edge (bb, cbb); 4174 4175 /* Register the necessary assertions for the operand in the 4176 SWITCH_EXPR. */ 4177 auto_vec<assert_info, 8> asserts; 4178 register_edge_assert_for (op, e, 4179 max ? GE_EXPR : EQ_EXPR, 4180 op, fold_convert (TREE_TYPE (op), min), 4181 asserts); 4182 if (max) 4183 register_edge_assert_for (op, e, LE_EXPR, op, 4184 fold_convert (TREE_TYPE (op), max), 4185 asserts); 4186 finish_register_edge_assert_for (e, bsi, asserts); 4187 } 4188 4189 XDELETEVEC (ci); 4190 4191 if (!live_on_edge (default_edge, op)) 4192 return; 4193 4194 /* Now register along the default label assertions that correspond to the 4195 anti-range of each label. */ 4196 int insertion_limit = PARAM_VALUE (PARAM_MAX_VRP_SWITCH_ASSERTIONS); 4197 if (insertion_limit == 0) 4198 return; 4199 4200 /* We can't do this if the default case shares a label with another case. */ 4201 tree default_cl = gimple_switch_default_label (last); 4202 for (idx = 1; idx < n; idx++) 4203 { 4204 tree min, max; 4205 tree cl = gimple_switch_label (last, idx); 4206 if (CASE_LABEL (cl) == CASE_LABEL (default_cl)) 4207 continue; 4208 4209 min = CASE_LOW (cl); 4210 max = CASE_HIGH (cl); 4211 4212 /* Combine contiguous case ranges to reduce the number of assertions 4213 to insert. */ 4214 for (idx = idx + 1; idx < n; idx++) 4215 { 4216 tree next_min, next_max; 4217 tree next_cl = gimple_switch_label (last, idx); 4218 if (CASE_LABEL (next_cl) == CASE_LABEL (default_cl)) 4219 break; 4220 4221 next_min = CASE_LOW (next_cl); 4222 next_max = CASE_HIGH (next_cl); 4223 4224 wide_int difference = (wi::to_wide (next_min) 4225 - wi::to_wide (max ? max : min)); 4226 if (wi::eq_p (difference, 1)) 4227 max = next_max ? next_max : next_min; 4228 else 4229 break; 4230 } 4231 idx--; 4232 4233 if (max == NULL_TREE) 4234 { 4235 /* Register the assertion OP != MIN. */ 4236 auto_vec<assert_info, 8> asserts; 4237 min = fold_convert (TREE_TYPE (op), min); 4238 register_edge_assert_for (op, default_edge, NE_EXPR, op, min, 4239 asserts); 4240 finish_register_edge_assert_for (default_edge, bsi, asserts); 4241 } 4242 else 4243 { 4244 /* Register the assertion (unsigned)OP - MIN > (MAX - MIN), 4245 which will give OP the anti-range ~[MIN,MAX]. */ 4246 tree uop = fold_convert (unsigned_type_for (TREE_TYPE (op)), op); 4247 min = fold_convert (TREE_TYPE (uop), min); 4248 max = fold_convert (TREE_TYPE (uop), max); 4249 4250 tree lhs = fold_build2 (MINUS_EXPR, TREE_TYPE (uop), uop, min); 4251 tree rhs = int_const_binop (MINUS_EXPR, max, min); 4252 register_new_assert_for (op, lhs, GT_EXPR, rhs, 4253 NULL, default_edge, bsi); 4254 } 4255 4256 if (--insertion_limit == 0) 4257 break; 4258 } 4259 } 4260 4261 4262 /* Traverse all the statements in block BB looking for statements that 4263 may generate useful assertions for the SSA names in their operand. 4264 If a statement produces a useful assertion A for name N_i, then the 4265 list of assertions already generated for N_i is scanned to 4266 determine if A is actually needed. 4267 4268 If N_i already had the assertion A at a location dominating the 4269 current location, then nothing needs to be done. Otherwise, the 4270 new location for A is recorded instead. 4271 4272 1- For every statement S in BB, all the variables used by S are 4273 added to bitmap FOUND_IN_SUBGRAPH. 4274 4275 2- If statement S uses an operand N in a way that exposes a known 4276 value range for N, then if N was not already generated by an 4277 ASSERT_EXPR, create a new assert location for N. For instance, 4278 if N is a pointer and the statement dereferences it, we can 4279 assume that N is not NULL. 4280 4281 3- COND_EXPRs are a special case of #2. We can derive range 4282 information from the predicate but need to insert different 4283 ASSERT_EXPRs for each of the sub-graphs rooted at the 4284 conditional block. If the last statement of BB is a conditional 4285 expression of the form 'X op Y', then 4286 4287 a) Remove X and Y from the set FOUND_IN_SUBGRAPH. 4288 4289 b) If the conditional is the only entry point to the sub-graph 4290 corresponding to the THEN_CLAUSE, recurse into it. On 4291 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then 4292 an ASSERT_EXPR is added for the corresponding variable. 4293 4294 c) Repeat step (b) on the ELSE_CLAUSE. 4295 4296 d) Mark X and Y in FOUND_IN_SUBGRAPH. 4297 4298 For instance, 4299 4300 if (a == 9) 4301 b = a; 4302 else 4303 b = c + 1; 4304 4305 In this case, an assertion on the THEN clause is useful to 4306 determine that 'a' is always 9 on that edge. However, an assertion 4307 on the ELSE clause would be unnecessary. 4308 4309 4- If BB does not end in a conditional expression, then we recurse 4310 into BB's dominator children. 4311 4312 At the end of the recursive traversal, every SSA name will have a 4313 list of locations where ASSERT_EXPRs should be added. When a new 4314 location for name N is found, it is registered by calling 4315 register_new_assert_for. That function keeps track of all the 4316 registered assertions to prevent adding unnecessary assertions. 4317 For instance, if a pointer P_4 is dereferenced more than once in a 4318 dominator tree, only the location dominating all the dereference of 4319 P_4 will receive an ASSERT_EXPR. */ 4320 4321 static void 4322 find_assert_locations_1 (basic_block bb, sbitmap live) 4323 { 4324 gimple *last; 4325 4326 last = last_stmt (bb); 4327 4328 /* If BB's last statement is a conditional statement involving integer 4329 operands, determine if we need to add ASSERT_EXPRs. */ 4330 if (last 4331 && gimple_code (last) == GIMPLE_COND 4332 && !fp_predicate (last) 4333 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) 4334 find_conditional_asserts (bb, as_a <gcond *> (last)); 4335 4336 /* If BB's last statement is a switch statement involving integer 4337 operands, determine if we need to add ASSERT_EXPRs. */ 4338 if (last 4339 && gimple_code (last) == GIMPLE_SWITCH 4340 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) 4341 find_switch_asserts (bb, as_a <gswitch *> (last)); 4342 4343 /* Traverse all the statements in BB marking used names and looking 4344 for statements that may infer assertions for their used operands. */ 4345 for (gimple_stmt_iterator si = gsi_last_bb (bb); !gsi_end_p (si); 4346 gsi_prev (&si)) 4347 { 4348 gimple *stmt; 4349 tree op; 4350 ssa_op_iter i; 4351 4352 stmt = gsi_stmt (si); 4353 4354 if (is_gimple_debug (stmt)) 4355 continue; 4356 4357 /* See if we can derive an assertion for any of STMT's operands. */ 4358 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 4359 { 4360 tree value; 4361 enum tree_code comp_code; 4362 4363 /* If op is not live beyond this stmt, do not bother to insert 4364 asserts for it. */ 4365 if (!bitmap_bit_p (live, SSA_NAME_VERSION (op))) 4366 continue; 4367 4368 /* If OP is used in such a way that we can infer a value 4369 range for it, and we don't find a previous assertion for 4370 it, create a new assertion location node for OP. */ 4371 if (infer_value_range (stmt, op, &comp_code, &value)) 4372 { 4373 /* If we are able to infer a nonzero value range for OP, 4374 then walk backwards through the use-def chain to see if OP 4375 was set via a typecast. 4376 4377 If so, then we can also infer a nonzero value range 4378 for the operand of the NOP_EXPR. */ 4379 if (comp_code == NE_EXPR && integer_zerop (value)) 4380 { 4381 tree t = op; 4382 gimple *def_stmt = SSA_NAME_DEF_STMT (t); 4383 4384 while (is_gimple_assign (def_stmt) 4385 && CONVERT_EXPR_CODE_P 4386 (gimple_assign_rhs_code (def_stmt)) 4387 && TREE_CODE 4388 (gimple_assign_rhs1 (def_stmt)) == SSA_NAME 4389 && POINTER_TYPE_P 4390 (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) 4391 { 4392 t = gimple_assign_rhs1 (def_stmt); 4393 def_stmt = SSA_NAME_DEF_STMT (t); 4394 4395 /* Note we want to register the assert for the 4396 operand of the NOP_EXPR after SI, not after the 4397 conversion. */ 4398 if (bitmap_bit_p (live, SSA_NAME_VERSION (t))) 4399 register_new_assert_for (t, t, comp_code, value, 4400 bb, NULL, si); 4401 } 4402 } 4403 4404 register_new_assert_for (op, op, comp_code, value, bb, NULL, si); 4405 } 4406 } 4407 4408 /* Update live. */ 4409 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 4410 bitmap_set_bit (live, SSA_NAME_VERSION (op)); 4411 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF) 4412 bitmap_clear_bit (live, SSA_NAME_VERSION (op)); 4413 } 4414 4415 /* Traverse all PHI nodes in BB, updating live. */ 4416 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); 4417 gsi_next (&si)) 4418 { 4419 use_operand_p arg_p; 4420 ssa_op_iter i; 4421 gphi *phi = si.phi (); 4422 tree res = gimple_phi_result (phi); 4423 4424 if (virtual_operand_p (res)) 4425 continue; 4426 4427 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) 4428 { 4429 tree arg = USE_FROM_PTR (arg_p); 4430 if (TREE_CODE (arg) == SSA_NAME) 4431 bitmap_set_bit (live, SSA_NAME_VERSION (arg)); 4432 } 4433 4434 bitmap_clear_bit (live, SSA_NAME_VERSION (res)); 4435 } 4436 } 4437 4438 /* Do an RPO walk over the function computing SSA name liveness 4439 on-the-fly and deciding on assert expressions to insert. */ 4440 4441 static void 4442 find_assert_locations (void) 4443 { 4444 int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); 4445 int *bb_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); 4446 int *last_rpo = XCNEWVEC (int, last_basic_block_for_fn (cfun)); 4447 int rpo_cnt, i; 4448 4449 live = XCNEWVEC (sbitmap, last_basic_block_for_fn (cfun)); 4450 rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false); 4451 for (i = 0; i < rpo_cnt; ++i) 4452 bb_rpo[rpo[i]] = i; 4453 4454 /* Pre-seed loop latch liveness from loop header PHI nodes. Due to 4455 the order we compute liveness and insert asserts we otherwise 4456 fail to insert asserts into the loop latch. */ 4457 loop_p loop; 4458 FOR_EACH_LOOP (loop, 0) 4459 { 4460 i = loop->latch->index; 4461 unsigned int j = single_succ_edge (loop->latch)->dest_idx; 4462 for (gphi_iterator gsi = gsi_start_phis (loop->header); 4463 !gsi_end_p (gsi); gsi_next (&gsi)) 4464 { 4465 gphi *phi = gsi.phi (); 4466 if (virtual_operand_p (gimple_phi_result (phi))) 4467 continue; 4468 tree arg = gimple_phi_arg_def (phi, j); 4469 if (TREE_CODE (arg) == SSA_NAME) 4470 { 4471 if (live[i] == NULL) 4472 { 4473 live[i] = sbitmap_alloc (num_ssa_names); 4474 bitmap_clear (live[i]); 4475 } 4476 bitmap_set_bit (live[i], SSA_NAME_VERSION (arg)); 4477 } 4478 } 4479 } 4480 4481 for (i = rpo_cnt - 1; i >= 0; --i) 4482 { 4483 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]); 4484 edge e; 4485 edge_iterator ei; 4486 4487 if (!live[rpo[i]]) 4488 { 4489 live[rpo[i]] = sbitmap_alloc (num_ssa_names); 4490 bitmap_clear (live[rpo[i]]); 4491 } 4492 4493 /* Process BB and update the live information with uses in 4494 this block. */ 4495 find_assert_locations_1 (bb, live[rpo[i]]); 4496 4497 /* Merge liveness into the predecessor blocks and free it. */ 4498 if (!bitmap_empty_p (live[rpo[i]])) 4499 { 4500 int pred_rpo = i; 4501 FOR_EACH_EDGE (e, ei, bb->preds) 4502 { 4503 int pred = e->src->index; 4504 if ((e->flags & EDGE_DFS_BACK) || pred == ENTRY_BLOCK) 4505 continue; 4506 4507 if (!live[pred]) 4508 { 4509 live[pred] = sbitmap_alloc (num_ssa_names); 4510 bitmap_clear (live[pred]); 4511 } 4512 bitmap_ior (live[pred], live[pred], live[rpo[i]]); 4513 4514 if (bb_rpo[pred] < pred_rpo) 4515 pred_rpo = bb_rpo[pred]; 4516 } 4517 4518 /* Record the RPO number of the last visited block that needs 4519 live information from this block. */ 4520 last_rpo[rpo[i]] = pred_rpo; 4521 } 4522 else 4523 { 4524 sbitmap_free (live[rpo[i]]); 4525 live[rpo[i]] = NULL; 4526 } 4527 4528 /* We can free all successors live bitmaps if all their 4529 predecessors have been visited already. */ 4530 FOR_EACH_EDGE (e, ei, bb->succs) 4531 if (last_rpo[e->dest->index] == i 4532 && live[e->dest->index]) 4533 { 4534 sbitmap_free (live[e->dest->index]); 4535 live[e->dest->index] = NULL; 4536 } 4537 } 4538 4539 XDELETEVEC (rpo); 4540 XDELETEVEC (bb_rpo); 4541 XDELETEVEC (last_rpo); 4542 for (i = 0; i < last_basic_block_for_fn (cfun); ++i) 4543 if (live[i]) 4544 sbitmap_free (live[i]); 4545 XDELETEVEC (live); 4546 } 4547 4548 /* Create an ASSERT_EXPR for NAME and insert it in the location 4549 indicated by LOC. Return true if we made any edge insertions. */ 4550 4551 static bool 4552 process_assert_insertions_for (tree name, assert_locus *loc) 4553 { 4554 /* Build the comparison expression NAME_i COMP_CODE VAL. */ 4555 gimple *stmt; 4556 tree cond; 4557 gimple *assert_stmt; 4558 edge_iterator ei; 4559 edge e; 4560 4561 /* If we have X <=> X do not insert an assert expr for that. */ 4562 if (loc->expr == loc->val) 4563 return false; 4564 4565 cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val); 4566 assert_stmt = build_assert_expr_for (cond, name); 4567 if (loc->e) 4568 { 4569 /* We have been asked to insert the assertion on an edge. This 4570 is used only by COND_EXPR and SWITCH_EXPR assertions. */ 4571 gcc_checking_assert (gimple_code (gsi_stmt (loc->si)) == GIMPLE_COND 4572 || (gimple_code (gsi_stmt (loc->si)) 4573 == GIMPLE_SWITCH)); 4574 4575 gsi_insert_on_edge (loc->e, assert_stmt); 4576 return true; 4577 } 4578 4579 /* If the stmt iterator points at the end then this is an insertion 4580 at the beginning of a block. */ 4581 if (gsi_end_p (loc->si)) 4582 { 4583 gimple_stmt_iterator si = gsi_after_labels (loc->bb); 4584 gsi_insert_before (&si, assert_stmt, GSI_SAME_STMT); 4585 return false; 4586 4587 } 4588 /* Otherwise, we can insert right after LOC->SI iff the 4589 statement must not be the last statement in the block. */ 4590 stmt = gsi_stmt (loc->si); 4591 if (!stmt_ends_bb_p (stmt)) 4592 { 4593 gsi_insert_after (&loc->si, assert_stmt, GSI_SAME_STMT); 4594 return false; 4595 } 4596 4597 /* If STMT must be the last statement in BB, we can only insert new 4598 assertions on the non-abnormal edge out of BB. Note that since 4599 STMT is not control flow, there may only be one non-abnormal/eh edge 4600 out of BB. */ 4601 FOR_EACH_EDGE (e, ei, loc->bb->succs) 4602 if (!(e->flags & (EDGE_ABNORMAL|EDGE_EH))) 4603 { 4604 gsi_insert_on_edge (e, assert_stmt); 4605 return true; 4606 } 4607 4608 gcc_unreachable (); 4609 } 4610 4611 /* Qsort helper for sorting assert locations. If stable is true, don't 4612 use iterative_hash_expr because it can be unstable for -fcompare-debug, 4613 on the other side some pointers might be NULL. */ 4614 4615 template <bool stable> 4616 static int 4617 compare_assert_loc (const void *pa, const void *pb) 4618 { 4619 assert_locus * const a = *(assert_locus * const *)pa; 4620 assert_locus * const b = *(assert_locus * const *)pb; 4621 4622 /* If stable, some asserts might be optimized away already, sort 4623 them last. */ 4624 if (stable) 4625 { 4626 if (a == NULL) 4627 return b != NULL; 4628 else if (b == NULL) 4629 return -1; 4630 } 4631 4632 if (a->e == NULL && b->e != NULL) 4633 return 1; 4634 else if (a->e != NULL && b->e == NULL) 4635 return -1; 4636 4637 /* After the above checks, we know that (a->e == NULL) == (b->e == NULL), 4638 no need to test both a->e and b->e. */ 4639 4640 /* Sort after destination index. */ 4641 if (a->e == NULL) 4642 ; 4643 else if (a->e->dest->index > b->e->dest->index) 4644 return 1; 4645 else if (a->e->dest->index < b->e->dest->index) 4646 return -1; 4647 4648 /* Sort after comp_code. */ 4649 if (a->comp_code > b->comp_code) 4650 return 1; 4651 else if (a->comp_code < b->comp_code) 4652 return -1; 4653 4654 hashval_t ha, hb; 4655 4656 /* E.g. if a->val is ADDR_EXPR of a VAR_DECL, iterative_hash_expr 4657 uses DECL_UID of the VAR_DECL, so sorting might differ between 4658 -g and -g0. When doing the removal of redundant assert exprs 4659 and commonization to successors, this does not matter, but for 4660 the final sort needs to be stable. */ 4661 if (stable) 4662 { 4663 ha = 0; 4664 hb = 0; 4665 } 4666 else 4667 { 4668 ha = iterative_hash_expr (a->expr, iterative_hash_expr (a->val, 0)); 4669 hb = iterative_hash_expr (b->expr, iterative_hash_expr (b->val, 0)); 4670 } 4671 4672 /* Break the tie using hashing and source/bb index. */ 4673 if (ha == hb) 4674 return (a->e != NULL 4675 ? a->e->src->index - b->e->src->index 4676 : a->bb->index - b->bb->index); 4677 return ha > hb ? 1 : -1; 4678 } 4679 4680 /* Process all the insertions registered for every name N_i registered 4681 in NEED_ASSERT_FOR. The list of assertions to be inserted are 4682 found in ASSERTS_FOR[i]. */ 4683 4684 static void 4685 process_assert_insertions (void) 4686 { 4687 unsigned i; 4688 bitmap_iterator bi; 4689 bool update_edges_p = false; 4690 int num_asserts = 0; 4691 4692 if (dump_file && (dump_flags & TDF_DETAILS)) 4693 dump_all_asserts (dump_file); 4694 4695 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 4696 { 4697 assert_locus *loc = asserts_for[i]; 4698 gcc_assert (loc); 4699 4700 auto_vec<assert_locus *, 16> asserts; 4701 for (; loc; loc = loc->next) 4702 asserts.safe_push (loc); 4703 asserts.qsort (compare_assert_loc<false>); 4704 4705 /* Push down common asserts to successors and remove redundant ones. */ 4706 unsigned ecnt = 0; 4707 assert_locus *common = NULL; 4708 unsigned commonj = 0; 4709 for (unsigned j = 0; j < asserts.length (); ++j) 4710 { 4711 loc = asserts[j]; 4712 if (! loc->e) 4713 common = NULL; 4714 else if (! common 4715 || loc->e->dest != common->e->dest 4716 || loc->comp_code != common->comp_code 4717 || ! operand_equal_p (loc->val, common->val, 0) 4718 || ! operand_equal_p (loc->expr, common->expr, 0)) 4719 { 4720 commonj = j; 4721 common = loc; 4722 ecnt = 1; 4723 } 4724 else if (loc->e == asserts[j-1]->e) 4725 { 4726 /* Remove duplicate asserts. */ 4727 if (commonj == j - 1) 4728 { 4729 commonj = j; 4730 common = loc; 4731 } 4732 free (asserts[j-1]); 4733 asserts[j-1] = NULL; 4734 } 4735 else 4736 { 4737 ecnt++; 4738 if (EDGE_COUNT (common->e->dest->preds) == ecnt) 4739 { 4740 /* We have the same assertion on all incoming edges of a BB. 4741 Insert it at the beginning of that block. */ 4742 loc->bb = loc->e->dest; 4743 loc->e = NULL; 4744 loc->si = gsi_none (); 4745 common = NULL; 4746 /* Clear asserts commoned. */ 4747 for (; commonj != j; ++commonj) 4748 if (asserts[commonj]) 4749 { 4750 free (asserts[commonj]); 4751 asserts[commonj] = NULL; 4752 } 4753 } 4754 } 4755 } 4756 4757 /* The asserts vector sorting above might be unstable for 4758 -fcompare-debug, sort again to ensure a stable sort. */ 4759 asserts.qsort (compare_assert_loc<true>); 4760 for (unsigned j = 0; j < asserts.length (); ++j) 4761 { 4762 loc = asserts[j]; 4763 if (! loc) 4764 break; 4765 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc); 4766 num_asserts++; 4767 free (loc); 4768 } 4769 } 4770 4771 if (update_edges_p) 4772 gsi_commit_edge_inserts (); 4773 4774 statistics_counter_event (cfun, "Number of ASSERT_EXPR expressions inserted", 4775 num_asserts); 4776 } 4777 4778 4779 /* Traverse the flowgraph looking for conditional jumps to insert range 4780 expressions. These range expressions are meant to provide information 4781 to optimizations that need to reason in terms of value ranges. They 4782 will not be expanded into RTL. For instance, given: 4783 4784 x = ... 4785 y = ... 4786 if (x < y) 4787 y = x - 2; 4788 else 4789 x = y + 3; 4790 4791 this pass will transform the code into: 4792 4793 x = ... 4794 y = ... 4795 if (x < y) 4796 { 4797 x = ASSERT_EXPR <x, x < y> 4798 y = x - 2 4799 } 4800 else 4801 { 4802 y = ASSERT_EXPR <y, x >= y> 4803 x = y + 3 4804 } 4805 4806 The idea is that once copy and constant propagation have run, other 4807 optimizations will be able to determine what ranges of values can 'x' 4808 take in different paths of the code, simply by checking the reaching 4809 definition of 'x'. */ 4810 4811 static void 4812 insert_range_assertions (void) 4813 { 4814 need_assert_for = BITMAP_ALLOC (NULL); 4815 asserts_for = XCNEWVEC (assert_locus *, num_ssa_names); 4816 4817 calculate_dominance_info (CDI_DOMINATORS); 4818 4819 find_assert_locations (); 4820 if (!bitmap_empty_p (need_assert_for)) 4821 { 4822 process_assert_insertions (); 4823 update_ssa (TODO_update_ssa_no_phi); 4824 } 4825 4826 if (dump_file && (dump_flags & TDF_DETAILS)) 4827 { 4828 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n"); 4829 dump_function_to_file (current_function_decl, dump_file, dump_flags); 4830 } 4831 4832 free (asserts_for); 4833 BITMAP_FREE (need_assert_for); 4834 } 4835 4836 class vrp_prop : public ssa_propagation_engine 4837 { 4838 public: 4839 enum ssa_prop_result visit_stmt (gimple *, edge *, tree *) FINAL OVERRIDE; 4840 enum ssa_prop_result visit_phi (gphi *) FINAL OVERRIDE; 4841 4842 void vrp_initialize (void); 4843 void vrp_finalize (bool); 4844 void check_all_array_refs (void); 4845 void check_array_ref (location_t, tree, bool); 4846 void search_for_addr_array (tree, location_t); 4847 4848 class vr_values vr_values; 4849 /* Temporary delegator to minimize code churn. */ 4850 value_range *get_value_range (const_tree op) 4851 { return vr_values.get_value_range (op); } 4852 void set_defs_to_varying (gimple *stmt) 4853 { return vr_values.set_defs_to_varying (stmt); } 4854 void extract_range_from_stmt (gimple *stmt, edge *taken_edge_p, 4855 tree *output_p, value_range *vr) 4856 { vr_values.extract_range_from_stmt (stmt, taken_edge_p, output_p, vr); } 4857 bool update_value_range (const_tree op, value_range *vr) 4858 { return vr_values.update_value_range (op, vr); } 4859 void extract_range_basic (value_range *vr, gimple *stmt) 4860 { vr_values.extract_range_basic (vr, stmt); } 4861 void extract_range_from_phi_node (gphi *phi, value_range *vr) 4862 { vr_values.extract_range_from_phi_node (phi, vr); } 4863 }; 4864 /* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible arrays 4865 and "struct" hacks. If VRP can determine that the 4866 array subscript is a constant, check if it is outside valid 4867 range. If the array subscript is a RANGE, warn if it is 4868 non-overlapping with valid range. 4869 IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR. */ 4870 4871 void 4872 vrp_prop::check_array_ref (location_t location, tree ref, 4873 bool ignore_off_by_one) 4874 { 4875 value_range *vr = NULL; 4876 tree low_sub, up_sub; 4877 tree low_bound, up_bound, up_bound_p1; 4878 4879 if (TREE_NO_WARNING (ref)) 4880 return; 4881 4882 low_sub = up_sub = TREE_OPERAND (ref, 1); 4883 up_bound = array_ref_up_bound (ref); 4884 4885 if (!up_bound 4886 || TREE_CODE (up_bound) != INTEGER_CST 4887 || (warn_array_bounds < 2 4888 && array_at_struct_end_p (ref))) 4889 { 4890 /* Accesses to trailing arrays via pointers may access storage 4891 beyond the types array bounds. For such arrays, or for flexible 4892 array members, as well as for other arrays of an unknown size, 4893 replace the upper bound with a more permissive one that assumes 4894 the size of the largest object is PTRDIFF_MAX. */ 4895 tree eltsize = array_ref_element_size (ref); 4896 4897 if (TREE_CODE (eltsize) != INTEGER_CST 4898 || integer_zerop (eltsize)) 4899 { 4900 up_bound = NULL_TREE; 4901 up_bound_p1 = NULL_TREE; 4902 } 4903 else 4904 { 4905 tree maxbound = TYPE_MAX_VALUE (ptrdiff_type_node); 4906 tree arg = TREE_OPERAND (ref, 0); 4907 poly_int64 off; 4908 4909 if (get_addr_base_and_unit_offset (arg, &off) && known_gt (off, 0)) 4910 maxbound = wide_int_to_tree (sizetype, 4911 wi::sub (wi::to_wide (maxbound), 4912 off)); 4913 else 4914 maxbound = fold_convert (sizetype, maxbound); 4915 4916 up_bound_p1 = int_const_binop (TRUNC_DIV_EXPR, maxbound, eltsize); 4917 4918 up_bound = int_const_binop (MINUS_EXPR, up_bound_p1, 4919 build_int_cst (ptrdiff_type_node, 1)); 4920 } 4921 } 4922 else 4923 up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound, 4924 build_int_cst (TREE_TYPE (up_bound), 1)); 4925 4926 low_bound = array_ref_low_bound (ref); 4927 4928 tree artype = TREE_TYPE (TREE_OPERAND (ref, 0)); 4929 4930 /* Empty array. */ 4931 if (up_bound && tree_int_cst_equal (low_bound, up_bound_p1)) 4932 { 4933 warning_at (location, OPT_Warray_bounds, 4934 "array subscript %E is above array bounds of %qT", 4935 low_bound, artype); 4936 TREE_NO_WARNING (ref) = 1; 4937 } 4938 4939 if (TREE_CODE (low_sub) == SSA_NAME) 4940 { 4941 vr = get_value_range (low_sub); 4942 if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE) 4943 { 4944 low_sub = vr->type == VR_RANGE ? vr->max : vr->min; 4945 up_sub = vr->type == VR_RANGE ? vr->min : vr->max; 4946 } 4947 } 4948 4949 if (vr && vr->type == VR_ANTI_RANGE) 4950 { 4951 if (up_bound 4952 && TREE_CODE (up_sub) == INTEGER_CST 4953 && (ignore_off_by_one 4954 ? tree_int_cst_lt (up_bound, up_sub) 4955 : tree_int_cst_le (up_bound, up_sub)) 4956 && TREE_CODE (low_sub) == INTEGER_CST 4957 && tree_int_cst_le (low_sub, low_bound)) 4958 { 4959 warning_at (location, OPT_Warray_bounds, 4960 "array subscript [%E, %E] is outside array bounds of %qT", 4961 low_sub, up_sub, artype); 4962 TREE_NO_WARNING (ref) = 1; 4963 } 4964 } 4965 else if (up_bound 4966 && TREE_CODE (up_sub) == INTEGER_CST 4967 && (ignore_off_by_one 4968 ? !tree_int_cst_le (up_sub, up_bound_p1) 4969 : !tree_int_cst_le (up_sub, up_bound))) 4970 { 4971 if (dump_file && (dump_flags & TDF_DETAILS)) 4972 { 4973 fprintf (dump_file, "Array bound warning for "); 4974 dump_generic_expr (MSG_NOTE, TDF_SLIM, ref); 4975 fprintf (dump_file, "\n"); 4976 } 4977 warning_at (location, OPT_Warray_bounds, 4978 "array subscript %E is above array bounds of %qT", 4979 up_sub, artype); 4980 TREE_NO_WARNING (ref) = 1; 4981 } 4982 else if (TREE_CODE (low_sub) == INTEGER_CST 4983 && tree_int_cst_lt (low_sub, low_bound)) 4984 { 4985 if (dump_file && (dump_flags & TDF_DETAILS)) 4986 { 4987 fprintf (dump_file, "Array bound warning for "); 4988 dump_generic_expr (MSG_NOTE, TDF_SLIM, ref); 4989 fprintf (dump_file, "\n"); 4990 } 4991 warning_at (location, OPT_Warray_bounds, 4992 "array subscript %E is below array bounds of %qT", 4993 low_sub, artype); 4994 TREE_NO_WARNING (ref) = 1; 4995 } 4996 } 4997 4998 /* Searches if the expr T, located at LOCATION computes 4999 address of an ARRAY_REF, and call check_array_ref on it. */ 5000 5001 void 5002 vrp_prop::search_for_addr_array (tree t, location_t location) 5003 { 5004 /* Check each ARRAY_REFs in the reference chain. */ 5005 do 5006 { 5007 if (TREE_CODE (t) == ARRAY_REF) 5008 check_array_ref (location, t, true /*ignore_off_by_one*/); 5009 5010 t = TREE_OPERAND (t, 0); 5011 } 5012 while (handled_component_p (t)); 5013 5014 if (TREE_CODE (t) == MEM_REF 5015 && TREE_CODE (TREE_OPERAND (t, 0)) == ADDR_EXPR 5016 && !TREE_NO_WARNING (t)) 5017 { 5018 tree tem = TREE_OPERAND (TREE_OPERAND (t, 0), 0); 5019 tree low_bound, up_bound, el_sz; 5020 offset_int idx; 5021 if (TREE_CODE (TREE_TYPE (tem)) != ARRAY_TYPE 5022 || TREE_CODE (TREE_TYPE (TREE_TYPE (tem))) == ARRAY_TYPE 5023 || !TYPE_DOMAIN (TREE_TYPE (tem))) 5024 return; 5025 5026 low_bound = TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (tem))); 5027 up_bound = TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (tem))); 5028 el_sz = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (tem))); 5029 if (!low_bound 5030 || TREE_CODE (low_bound) != INTEGER_CST 5031 || !up_bound 5032 || TREE_CODE (up_bound) != INTEGER_CST 5033 || !el_sz 5034 || TREE_CODE (el_sz) != INTEGER_CST) 5035 return; 5036 5037 if (!mem_ref_offset (t).is_constant (&idx)) 5038 return; 5039 5040 idx = wi::sdiv_trunc (idx, wi::to_offset (el_sz)); 5041 if (idx < 0) 5042 { 5043 if (dump_file && (dump_flags & TDF_DETAILS)) 5044 { 5045 fprintf (dump_file, "Array bound warning for "); 5046 dump_generic_expr (MSG_NOTE, TDF_SLIM, t); 5047 fprintf (dump_file, "\n"); 5048 } 5049 warning_at (location, OPT_Warray_bounds, 5050 "array subscript %wi is below array bounds of %qT", 5051 idx.to_shwi (), TREE_TYPE (tem)); 5052 TREE_NO_WARNING (t) = 1; 5053 } 5054 else if (idx > (wi::to_offset (up_bound) 5055 - wi::to_offset (low_bound) + 1)) 5056 { 5057 if (dump_file && (dump_flags & TDF_DETAILS)) 5058 { 5059 fprintf (dump_file, "Array bound warning for "); 5060 dump_generic_expr (MSG_NOTE, TDF_SLIM, t); 5061 fprintf (dump_file, "\n"); 5062 } 5063 warning_at (location, OPT_Warray_bounds, 5064 "array subscript %wu is above array bounds of %qT", 5065 idx.to_uhwi (), TREE_TYPE (tem)); 5066 TREE_NO_WARNING (t) = 1; 5067 } 5068 } 5069 } 5070 5071 /* walk_tree() callback that checks if *TP is 5072 an ARRAY_REF inside an ADDR_EXPR (in which an array 5073 subscript one outside the valid range is allowed). Call 5074 check_array_ref for each ARRAY_REF found. The location is 5075 passed in DATA. */ 5076 5077 static tree 5078 check_array_bounds (tree *tp, int *walk_subtree, void *data) 5079 { 5080 tree t = *tp; 5081 struct walk_stmt_info *wi = (struct walk_stmt_info *) data; 5082 location_t location; 5083 5084 if (EXPR_HAS_LOCATION (t)) 5085 location = EXPR_LOCATION (t); 5086 else 5087 location = gimple_location (wi->stmt); 5088 5089 *walk_subtree = TRUE; 5090 5091 vrp_prop *vrp_prop = (class vrp_prop *)wi->info; 5092 if (TREE_CODE (t) == ARRAY_REF) 5093 vrp_prop->check_array_ref (location, t, false /*ignore_off_by_one*/); 5094 5095 else if (TREE_CODE (t) == ADDR_EXPR) 5096 { 5097 vrp_prop->search_for_addr_array (t, location); 5098 *walk_subtree = FALSE; 5099 } 5100 5101 return NULL_TREE; 5102 } 5103 5104 /* A dom_walker subclass for use by vrp_prop::check_all_array_refs, 5105 to walk over all statements of all reachable BBs and call 5106 check_array_bounds on them. */ 5107 5108 class check_array_bounds_dom_walker : public dom_walker 5109 { 5110 public: 5111 check_array_bounds_dom_walker (vrp_prop *prop) 5112 : dom_walker (CDI_DOMINATORS, 5113 /* Discover non-executable edges, preserving EDGE_EXECUTABLE 5114 flags, so that we can merge in information on 5115 non-executable edges from vrp_folder . */ 5116 REACHABLE_BLOCKS_PRESERVING_FLAGS), 5117 m_prop (prop) {} 5118 ~check_array_bounds_dom_walker () {} 5119 5120 edge before_dom_children (basic_block) FINAL OVERRIDE; 5121 5122 private: 5123 vrp_prop *m_prop; 5124 }; 5125 5126 /* Implementation of dom_walker::before_dom_children. 5127 5128 Walk over all statements of BB and call check_array_bounds on them, 5129 and determine if there's a unique successor edge. */ 5130 5131 edge 5132 check_array_bounds_dom_walker::before_dom_children (basic_block bb) 5133 { 5134 gimple_stmt_iterator si; 5135 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) 5136 { 5137 gimple *stmt = gsi_stmt (si); 5138 struct walk_stmt_info wi; 5139 if (!gimple_has_location (stmt) 5140 || is_gimple_debug (stmt)) 5141 continue; 5142 5143 memset (&wi, 0, sizeof (wi)); 5144 5145 wi.info = m_prop; 5146 5147 walk_gimple_op (stmt, check_array_bounds, &wi); 5148 } 5149 5150 /* Determine if there's a unique successor edge, and if so, return 5151 that back to dom_walker, ensuring that we don't visit blocks that 5152 became unreachable during the VRP propagation 5153 (PR tree-optimization/83312). */ 5154 return find_taken_edge (bb, NULL_TREE); 5155 } 5156 5157 /* Walk over all statements of all reachable BBs and call check_array_bounds 5158 on them. */ 5159 5160 void 5161 vrp_prop::check_all_array_refs () 5162 { 5163 check_array_bounds_dom_walker w (this); 5164 w.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); 5165 } 5166 5167 /* Return true if all imm uses of VAR are either in STMT, or 5168 feed (optionally through a chain of single imm uses) GIMPLE_COND 5169 in basic block COND_BB. */ 5170 5171 static bool 5172 all_imm_uses_in_stmt_or_feed_cond (tree var, gimple *stmt, basic_block cond_bb) 5173 { 5174 use_operand_p use_p, use2_p; 5175 imm_use_iterator iter; 5176 5177 FOR_EACH_IMM_USE_FAST (use_p, iter, var) 5178 if (USE_STMT (use_p) != stmt) 5179 { 5180 gimple *use_stmt = USE_STMT (use_p), *use_stmt2; 5181 if (is_gimple_debug (use_stmt)) 5182 continue; 5183 while (is_gimple_assign (use_stmt) 5184 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME 5185 && single_imm_use (gimple_assign_lhs (use_stmt), 5186 &use2_p, &use_stmt2)) 5187 use_stmt = use_stmt2; 5188 if (gimple_code (use_stmt) != GIMPLE_COND 5189 || gimple_bb (use_stmt) != cond_bb) 5190 return false; 5191 } 5192 return true; 5193 } 5194 5195 /* Handle 5196 _4 = x_3 & 31; 5197 if (_4 != 0) 5198 goto <bb 6>; 5199 else 5200 goto <bb 7>; 5201 <bb 6>: 5202 __builtin_unreachable (); 5203 <bb 7>: 5204 x_5 = ASSERT_EXPR <x_3, ...>; 5205 If x_3 has no other immediate uses (checked by caller), 5206 var is the x_3 var from ASSERT_EXPR, we can clear low 5 bits 5207 from the non-zero bitmask. */ 5208 5209 void 5210 maybe_set_nonzero_bits (edge e, tree var) 5211 { 5212 basic_block cond_bb = e->src; 5213 gimple *stmt = last_stmt (cond_bb); 5214 tree cst; 5215 5216 if (stmt == NULL 5217 || gimple_code (stmt) != GIMPLE_COND 5218 || gimple_cond_code (stmt) != ((e->flags & EDGE_TRUE_VALUE) 5219 ? EQ_EXPR : NE_EXPR) 5220 || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME 5221 || !integer_zerop (gimple_cond_rhs (stmt))) 5222 return; 5223 5224 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt)); 5225 if (!is_gimple_assign (stmt) 5226 || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR 5227 || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST) 5228 return; 5229 if (gimple_assign_rhs1 (stmt) != var) 5230 { 5231 gimple *stmt2; 5232 5233 if (TREE_CODE (gimple_assign_rhs1 (stmt)) != SSA_NAME) 5234 return; 5235 stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); 5236 if (!gimple_assign_cast_p (stmt2) 5237 || gimple_assign_rhs1 (stmt2) != var 5238 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt2)) 5239 || (TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))) 5240 != TYPE_PRECISION (TREE_TYPE (var)))) 5241 return; 5242 } 5243 cst = gimple_assign_rhs2 (stmt); 5244 set_nonzero_bits (var, wi::bit_and_not (get_nonzero_bits (var), 5245 wi::to_wide (cst))); 5246 } 5247 5248 /* Convert range assertion expressions into the implied copies and 5249 copy propagate away the copies. Doing the trivial copy propagation 5250 here avoids the need to run the full copy propagation pass after 5251 VRP. 5252 5253 FIXME, this will eventually lead to copy propagation removing the 5254 names that had useful range information attached to them. For 5255 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>, 5256 then N_i will have the range [3, +INF]. 5257 5258 However, by converting the assertion into the implied copy 5259 operation N_i = N_j, we will then copy-propagate N_j into the uses 5260 of N_i and lose the range information. We may want to hold on to 5261 ASSERT_EXPRs a little while longer as the ranges could be used in 5262 things like jump threading. 5263 5264 The problem with keeping ASSERT_EXPRs around is that passes after 5265 VRP need to handle them appropriately. 5266 5267 Another approach would be to make the range information a first 5268 class property of the SSA_NAME so that it can be queried from 5269 any pass. This is made somewhat more complex by the need for 5270 multiple ranges to be associated with one SSA_NAME. */ 5271 5272 static void 5273 remove_range_assertions (void) 5274 { 5275 basic_block bb; 5276 gimple_stmt_iterator si; 5277 /* 1 if looking at ASSERT_EXPRs immediately at the beginning of 5278 a basic block preceeded by GIMPLE_COND branching to it and 5279 __builtin_trap, -1 if not yet checked, 0 otherwise. */ 5280 int is_unreachable; 5281 5282 /* Note that the BSI iterator bump happens at the bottom of the 5283 loop and no bump is necessary if we're removing the statement 5284 referenced by the current BSI. */ 5285 FOR_EACH_BB_FN (bb, cfun) 5286 for (si = gsi_after_labels (bb), is_unreachable = -1; !gsi_end_p (si);) 5287 { 5288 gimple *stmt = gsi_stmt (si); 5289 5290 if (is_gimple_assign (stmt) 5291 && gimple_assign_rhs_code (stmt) == ASSERT_EXPR) 5292 { 5293 tree lhs = gimple_assign_lhs (stmt); 5294 tree rhs = gimple_assign_rhs1 (stmt); 5295 tree var; 5296 5297 var = ASSERT_EXPR_VAR (rhs); 5298 5299 if (TREE_CODE (var) == SSA_NAME 5300 && !POINTER_TYPE_P (TREE_TYPE (lhs)) 5301 && SSA_NAME_RANGE_INFO (lhs)) 5302 { 5303 if (is_unreachable == -1) 5304 { 5305 is_unreachable = 0; 5306 if (single_pred_p (bb) 5307 && assert_unreachable_fallthru_edge_p 5308 (single_pred_edge (bb))) 5309 is_unreachable = 1; 5310 } 5311 /* Handle 5312 if (x_7 >= 10 && x_7 < 20) 5313 __builtin_unreachable (); 5314 x_8 = ASSERT_EXPR <x_7, ...>; 5315 if the only uses of x_7 are in the ASSERT_EXPR and 5316 in the condition. In that case, we can copy the 5317 range info from x_8 computed in this pass also 5318 for x_7. */ 5319 if (is_unreachable 5320 && all_imm_uses_in_stmt_or_feed_cond (var, stmt, 5321 single_pred (bb))) 5322 { 5323 set_range_info (var, SSA_NAME_RANGE_TYPE (lhs), 5324 SSA_NAME_RANGE_INFO (lhs)->get_min (), 5325 SSA_NAME_RANGE_INFO (lhs)->get_max ()); 5326 maybe_set_nonzero_bits (single_pred_edge (bb), var); 5327 } 5328 } 5329 5330 /* Propagate the RHS into every use of the LHS. For SSA names 5331 also propagate abnormals as it merely restores the original 5332 IL in this case (an replace_uses_by would assert). */ 5333 if (TREE_CODE (var) == SSA_NAME) 5334 { 5335 imm_use_iterator iter; 5336 use_operand_p use_p; 5337 gimple *use_stmt; 5338 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 5339 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 5340 SET_USE (use_p, var); 5341 } 5342 else 5343 replace_uses_by (lhs, var); 5344 5345 /* And finally, remove the copy, it is not needed. */ 5346 gsi_remove (&si, true); 5347 release_defs (stmt); 5348 } 5349 else 5350 { 5351 if (!is_gimple_debug (gsi_stmt (si))) 5352 is_unreachable = 0; 5353 gsi_next (&si); 5354 } 5355 } 5356 } 5357 5358 /* Return true if STMT is interesting for VRP. */ 5359 5360 bool 5361 stmt_interesting_for_vrp (gimple *stmt) 5362 { 5363 if (gimple_code (stmt) == GIMPLE_PHI) 5364 { 5365 tree res = gimple_phi_result (stmt); 5366 return (!virtual_operand_p (res) 5367 && (INTEGRAL_TYPE_P (TREE_TYPE (res)) 5368 || POINTER_TYPE_P (TREE_TYPE (res)))); 5369 } 5370 else if (is_gimple_assign (stmt) || is_gimple_call (stmt)) 5371 { 5372 tree lhs = gimple_get_lhs (stmt); 5373 5374 /* In general, assignments with virtual operands are not useful 5375 for deriving ranges, with the obvious exception of calls to 5376 builtin functions. */ 5377 if (lhs && TREE_CODE (lhs) == SSA_NAME 5378 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 5379 || POINTER_TYPE_P (TREE_TYPE (lhs))) 5380 && (is_gimple_call (stmt) 5381 || !gimple_vuse (stmt))) 5382 return true; 5383 else if (is_gimple_call (stmt) && gimple_call_internal_p (stmt)) 5384 switch (gimple_call_internal_fn (stmt)) 5385 { 5386 case IFN_ADD_OVERFLOW: 5387 case IFN_SUB_OVERFLOW: 5388 case IFN_MUL_OVERFLOW: 5389 case IFN_ATOMIC_COMPARE_EXCHANGE: 5390 /* These internal calls return _Complex integer type, 5391 but are interesting to VRP nevertheless. */ 5392 if (lhs && TREE_CODE (lhs) == SSA_NAME) 5393 return true; 5394 break; 5395 default: 5396 break; 5397 } 5398 } 5399 else if (gimple_code (stmt) == GIMPLE_COND 5400 || gimple_code (stmt) == GIMPLE_SWITCH) 5401 return true; 5402 5403 return false; 5404 } 5405 5406 /* Initialization required by ssa_propagate engine. */ 5407 5408 void 5409 vrp_prop::vrp_initialize () 5410 { 5411 basic_block bb; 5412 5413 FOR_EACH_BB_FN (bb, cfun) 5414 { 5415 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); 5416 gsi_next (&si)) 5417 { 5418 gphi *phi = si.phi (); 5419 if (!stmt_interesting_for_vrp (phi)) 5420 { 5421 tree lhs = PHI_RESULT (phi); 5422 set_value_range_to_varying (get_value_range (lhs)); 5423 prop_set_simulate_again (phi, false); 5424 } 5425 else 5426 prop_set_simulate_again (phi, true); 5427 } 5428 5429 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); 5430 gsi_next (&si)) 5431 { 5432 gimple *stmt = gsi_stmt (si); 5433 5434 /* If the statement is a control insn, then we do not 5435 want to avoid simulating the statement once. Failure 5436 to do so means that those edges will never get added. */ 5437 if (stmt_ends_bb_p (stmt)) 5438 prop_set_simulate_again (stmt, true); 5439 else if (!stmt_interesting_for_vrp (stmt)) 5440 { 5441 set_defs_to_varying (stmt); 5442 prop_set_simulate_again (stmt, false); 5443 } 5444 else 5445 prop_set_simulate_again (stmt, true); 5446 } 5447 } 5448 } 5449 5450 /* Searches the case label vector VEC for the index *IDX of the CASE_LABEL 5451 that includes the value VAL. The search is restricted to the range 5452 [START_IDX, n - 1] where n is the size of VEC. 5453 5454 If there is a CASE_LABEL for VAL, its index is placed in IDX and true is 5455 returned. 5456 5457 If there is no CASE_LABEL for VAL and there is one that is larger than VAL, 5458 it is placed in IDX and false is returned. 5459 5460 If VAL is larger than any CASE_LABEL, n is placed on IDX and false is 5461 returned. */ 5462 5463 bool 5464 find_case_label_index (gswitch *stmt, size_t start_idx, tree val, size_t *idx) 5465 { 5466 size_t n = gimple_switch_num_labels (stmt); 5467 size_t low, high; 5468 5469 /* Find case label for minimum of the value range or the next one. 5470 At each iteration we are searching in [low, high - 1]. */ 5471 5472 for (low = start_idx, high = n; high != low; ) 5473 { 5474 tree t; 5475 int cmp; 5476 /* Note that i != high, so we never ask for n. */ 5477 size_t i = (high + low) / 2; 5478 t = gimple_switch_label (stmt, i); 5479 5480 /* Cache the result of comparing CASE_LOW and val. */ 5481 cmp = tree_int_cst_compare (CASE_LOW (t), val); 5482 5483 if (cmp == 0) 5484 { 5485 /* Ranges cannot be empty. */ 5486 *idx = i; 5487 return true; 5488 } 5489 else if (cmp > 0) 5490 high = i; 5491 else 5492 { 5493 low = i + 1; 5494 if (CASE_HIGH (t) != NULL 5495 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0) 5496 { 5497 *idx = i; 5498 return true; 5499 } 5500 } 5501 } 5502 5503 *idx = high; 5504 return false; 5505 } 5506 5507 /* Searches the case label vector VEC for the range of CASE_LABELs that is used 5508 for values between MIN and MAX. The first index is placed in MIN_IDX. The 5509 last index is placed in MAX_IDX. If the range of CASE_LABELs is empty 5510 then MAX_IDX < MIN_IDX. 5511 Returns true if the default label is not needed. */ 5512 5513 bool 5514 find_case_label_range (gswitch *stmt, tree min, tree max, size_t *min_idx, 5515 size_t *max_idx) 5516 { 5517 size_t i, j; 5518 bool min_take_default = !find_case_label_index (stmt, 1, min, &i); 5519 bool max_take_default = !find_case_label_index (stmt, i, max, &j); 5520 5521 if (i == j 5522 && min_take_default 5523 && max_take_default) 5524 { 5525 /* Only the default case label reached. 5526 Return an empty range. */ 5527 *min_idx = 1; 5528 *max_idx = 0; 5529 return false; 5530 } 5531 else 5532 { 5533 bool take_default = min_take_default || max_take_default; 5534 tree low, high; 5535 size_t k; 5536 5537 if (max_take_default) 5538 j--; 5539 5540 /* If the case label range is continuous, we do not need 5541 the default case label. Verify that. */ 5542 high = CASE_LOW (gimple_switch_label (stmt, i)); 5543 if (CASE_HIGH (gimple_switch_label (stmt, i))) 5544 high = CASE_HIGH (gimple_switch_label (stmt, i)); 5545 for (k = i + 1; k <= j; ++k) 5546 { 5547 low = CASE_LOW (gimple_switch_label (stmt, k)); 5548 if (!integer_onep (int_const_binop (MINUS_EXPR, low, high))) 5549 { 5550 take_default = true; 5551 break; 5552 } 5553 high = low; 5554 if (CASE_HIGH (gimple_switch_label (stmt, k))) 5555 high = CASE_HIGH (gimple_switch_label (stmt, k)); 5556 } 5557 5558 *min_idx = i; 5559 *max_idx = j; 5560 return !take_default; 5561 } 5562 } 5563 5564 /* Evaluate statement STMT. If the statement produces a useful range, 5565 return SSA_PROP_INTERESTING and record the SSA name with the 5566 interesting range into *OUTPUT_P. 5567 5568 If STMT is a conditional branch and we can determine its truth 5569 value, the taken edge is recorded in *TAKEN_EDGE_P. 5570 5571 If STMT produces a varying value, return SSA_PROP_VARYING. */ 5572 5573 enum ssa_prop_result 5574 vrp_prop::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) 5575 { 5576 value_range vr = VR_INITIALIZER; 5577 tree lhs = gimple_get_lhs (stmt); 5578 extract_range_from_stmt (stmt, taken_edge_p, output_p, &vr); 5579 5580 if (*output_p) 5581 { 5582 if (update_value_range (*output_p, &vr)) 5583 { 5584 if (dump_file && (dump_flags & TDF_DETAILS)) 5585 { 5586 fprintf (dump_file, "Found new range for "); 5587 print_generic_expr (dump_file, *output_p); 5588 fprintf (dump_file, ": "); 5589 dump_value_range (dump_file, &vr); 5590 fprintf (dump_file, "\n"); 5591 } 5592 5593 if (vr.type == VR_VARYING) 5594 return SSA_PROP_VARYING; 5595 5596 return SSA_PROP_INTERESTING; 5597 } 5598 return SSA_PROP_NOT_INTERESTING; 5599 } 5600 5601 if (is_gimple_call (stmt) && gimple_call_internal_p (stmt)) 5602 switch (gimple_call_internal_fn (stmt)) 5603 { 5604 case IFN_ADD_OVERFLOW: 5605 case IFN_SUB_OVERFLOW: 5606 case IFN_MUL_OVERFLOW: 5607 case IFN_ATOMIC_COMPARE_EXCHANGE: 5608 /* These internal calls return _Complex integer type, 5609 which VRP does not track, but the immediate uses 5610 thereof might be interesting. */ 5611 if (lhs && TREE_CODE (lhs) == SSA_NAME) 5612 { 5613 imm_use_iterator iter; 5614 use_operand_p use_p; 5615 enum ssa_prop_result res = SSA_PROP_VARYING; 5616 5617 set_value_range_to_varying (get_value_range (lhs)); 5618 5619 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs) 5620 { 5621 gimple *use_stmt = USE_STMT (use_p); 5622 if (!is_gimple_assign (use_stmt)) 5623 continue; 5624 enum tree_code rhs_code = gimple_assign_rhs_code (use_stmt); 5625 if (rhs_code != REALPART_EXPR && rhs_code != IMAGPART_EXPR) 5626 continue; 5627 tree rhs1 = gimple_assign_rhs1 (use_stmt); 5628 tree use_lhs = gimple_assign_lhs (use_stmt); 5629 if (TREE_CODE (rhs1) != rhs_code 5630 || TREE_OPERAND (rhs1, 0) != lhs 5631 || TREE_CODE (use_lhs) != SSA_NAME 5632 || !stmt_interesting_for_vrp (use_stmt) 5633 || (!INTEGRAL_TYPE_P (TREE_TYPE (use_lhs)) 5634 || !TYPE_MIN_VALUE (TREE_TYPE (use_lhs)) 5635 || !TYPE_MAX_VALUE (TREE_TYPE (use_lhs)))) 5636 continue; 5637 5638 /* If there is a change in the value range for any of the 5639 REALPART_EXPR/IMAGPART_EXPR immediate uses, return 5640 SSA_PROP_INTERESTING. If there are any REALPART_EXPR 5641 or IMAGPART_EXPR immediate uses, but none of them have 5642 a change in their value ranges, return 5643 SSA_PROP_NOT_INTERESTING. If there are no 5644 {REAL,IMAG}PART_EXPR uses at all, 5645 return SSA_PROP_VARYING. */ 5646 value_range new_vr = VR_INITIALIZER; 5647 extract_range_basic (&new_vr, use_stmt); 5648 value_range *old_vr = get_value_range (use_lhs); 5649 if (old_vr->type != new_vr.type 5650 || !vrp_operand_equal_p (old_vr->min, new_vr.min) 5651 || !vrp_operand_equal_p (old_vr->max, new_vr.max) 5652 || !vrp_bitmap_equal_p (old_vr->equiv, new_vr.equiv)) 5653 res = SSA_PROP_INTERESTING; 5654 else 5655 res = SSA_PROP_NOT_INTERESTING; 5656 BITMAP_FREE (new_vr.equiv); 5657 if (res == SSA_PROP_INTERESTING) 5658 { 5659 *output_p = lhs; 5660 return res; 5661 } 5662 } 5663 5664 return res; 5665 } 5666 break; 5667 default: 5668 break; 5669 } 5670 5671 /* All other statements produce nothing of interest for VRP, so mark 5672 their outputs varying and prevent further simulation. */ 5673 set_defs_to_varying (stmt); 5674 5675 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 5676 } 5677 5678 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and 5679 { VR1TYPE, VR0MIN, VR0MAX } and store the result 5680 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest 5681 possible such range. The resulting range is not canonicalized. */ 5682 5683 static void 5684 union_ranges (enum value_range_type *vr0type, 5685 tree *vr0min, tree *vr0max, 5686 enum value_range_type vr1type, 5687 tree vr1min, tree vr1max) 5688 { 5689 bool mineq = vrp_operand_equal_p (*vr0min, vr1min); 5690 bool maxeq = vrp_operand_equal_p (*vr0max, vr1max); 5691 5692 /* [] is vr0, () is vr1 in the following classification comments. */ 5693 if (mineq && maxeq) 5694 { 5695 /* [( )] */ 5696 if (*vr0type == vr1type) 5697 /* Nothing to do for equal ranges. */ 5698 ; 5699 else if ((*vr0type == VR_RANGE 5700 && vr1type == VR_ANTI_RANGE) 5701 || (*vr0type == VR_ANTI_RANGE 5702 && vr1type == VR_RANGE)) 5703 { 5704 /* For anti-range with range union the result is varying. */ 5705 goto give_up; 5706 } 5707 else 5708 gcc_unreachable (); 5709 } 5710 else if (operand_less_p (*vr0max, vr1min) == 1 5711 || operand_less_p (vr1max, *vr0min) == 1) 5712 { 5713 /* [ ] ( ) or ( ) [ ] 5714 If the ranges have an empty intersection, result of the union 5715 operation is the anti-range or if both are anti-ranges 5716 it covers all. */ 5717 if (*vr0type == VR_ANTI_RANGE 5718 && vr1type == VR_ANTI_RANGE) 5719 goto give_up; 5720 else if (*vr0type == VR_ANTI_RANGE 5721 && vr1type == VR_RANGE) 5722 ; 5723 else if (*vr0type == VR_RANGE 5724 && vr1type == VR_ANTI_RANGE) 5725 { 5726 *vr0type = vr1type; 5727 *vr0min = vr1min; 5728 *vr0max = vr1max; 5729 } 5730 else if (*vr0type == VR_RANGE 5731 && vr1type == VR_RANGE) 5732 { 5733 /* The result is the convex hull of both ranges. */ 5734 if (operand_less_p (*vr0max, vr1min) == 1) 5735 { 5736 /* If the result can be an anti-range, create one. */ 5737 if (TREE_CODE (*vr0max) == INTEGER_CST 5738 && TREE_CODE (vr1min) == INTEGER_CST 5739 && vrp_val_is_min (*vr0min) 5740 && vrp_val_is_max (vr1max)) 5741 { 5742 tree min = int_const_binop (PLUS_EXPR, 5743 *vr0max, 5744 build_int_cst (TREE_TYPE (*vr0max), 1)); 5745 tree max = int_const_binop (MINUS_EXPR, 5746 vr1min, 5747 build_int_cst (TREE_TYPE (vr1min), 1)); 5748 if (!operand_less_p (max, min)) 5749 { 5750 *vr0type = VR_ANTI_RANGE; 5751 *vr0min = min; 5752 *vr0max = max; 5753 } 5754 else 5755 *vr0max = vr1max; 5756 } 5757 else 5758 *vr0max = vr1max; 5759 } 5760 else 5761 { 5762 /* If the result can be an anti-range, create one. */ 5763 if (TREE_CODE (vr1max) == INTEGER_CST 5764 && TREE_CODE (*vr0min) == INTEGER_CST 5765 && vrp_val_is_min (vr1min) 5766 && vrp_val_is_max (*vr0max)) 5767 { 5768 tree min = int_const_binop (PLUS_EXPR, 5769 vr1max, 5770 build_int_cst (TREE_TYPE (vr1max), 1)); 5771 tree max = int_const_binop (MINUS_EXPR, 5772 *vr0min, 5773 build_int_cst (TREE_TYPE (*vr0min), 1)); 5774 if (!operand_less_p (max, min)) 5775 { 5776 *vr0type = VR_ANTI_RANGE; 5777 *vr0min = min; 5778 *vr0max = max; 5779 } 5780 else 5781 *vr0min = vr1min; 5782 } 5783 else 5784 *vr0min = vr1min; 5785 } 5786 } 5787 else 5788 gcc_unreachable (); 5789 } 5790 else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1) 5791 && (mineq || operand_less_p (*vr0min, vr1min) == 1)) 5792 { 5793 /* [ ( ) ] or [( ) ] or [ ( )] */ 5794 if (*vr0type == VR_RANGE 5795 && vr1type == VR_RANGE) 5796 ; 5797 else if (*vr0type == VR_ANTI_RANGE 5798 && vr1type == VR_ANTI_RANGE) 5799 { 5800 *vr0type = vr1type; 5801 *vr0min = vr1min; 5802 *vr0max = vr1max; 5803 } 5804 else if (*vr0type == VR_ANTI_RANGE 5805 && vr1type == VR_RANGE) 5806 { 5807 /* Arbitrarily choose the right or left gap. */ 5808 if (!mineq && TREE_CODE (vr1min) == INTEGER_CST) 5809 *vr0max = int_const_binop (MINUS_EXPR, vr1min, 5810 build_int_cst (TREE_TYPE (vr1min), 1)); 5811 else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST) 5812 *vr0min = int_const_binop (PLUS_EXPR, vr1max, 5813 build_int_cst (TREE_TYPE (vr1max), 1)); 5814 else 5815 goto give_up; 5816 } 5817 else if (*vr0type == VR_RANGE 5818 && vr1type == VR_ANTI_RANGE) 5819 /* The result covers everything. */ 5820 goto give_up; 5821 else 5822 gcc_unreachable (); 5823 } 5824 else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1) 5825 && (mineq || operand_less_p (vr1min, *vr0min) == 1)) 5826 { 5827 /* ( [ ] ) or ([ ] ) or ( [ ]) */ 5828 if (*vr0type == VR_RANGE 5829 && vr1type == VR_RANGE) 5830 { 5831 *vr0type = vr1type; 5832 *vr0min = vr1min; 5833 *vr0max = vr1max; 5834 } 5835 else if (*vr0type == VR_ANTI_RANGE 5836 && vr1type == VR_ANTI_RANGE) 5837 ; 5838 else if (*vr0type == VR_RANGE 5839 && vr1type == VR_ANTI_RANGE) 5840 { 5841 *vr0type = VR_ANTI_RANGE; 5842 if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST) 5843 { 5844 *vr0max = int_const_binop (MINUS_EXPR, *vr0min, 5845 build_int_cst (TREE_TYPE (*vr0min), 1)); 5846 *vr0min = vr1min; 5847 } 5848 else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST) 5849 { 5850 *vr0min = int_const_binop (PLUS_EXPR, *vr0max, 5851 build_int_cst (TREE_TYPE (*vr0max), 1)); 5852 *vr0max = vr1max; 5853 } 5854 else 5855 goto give_up; 5856 } 5857 else if (*vr0type == VR_ANTI_RANGE 5858 && vr1type == VR_RANGE) 5859 /* The result covers everything. */ 5860 goto give_up; 5861 else 5862 gcc_unreachable (); 5863 } 5864 else if ((operand_less_p (vr1min, *vr0max) == 1 5865 || operand_equal_p (vr1min, *vr0max, 0)) 5866 && operand_less_p (*vr0min, vr1min) == 1 5867 && operand_less_p (*vr0max, vr1max) == 1) 5868 { 5869 /* [ ( ] ) or [ ]( ) */ 5870 if (*vr0type == VR_RANGE 5871 && vr1type == VR_RANGE) 5872 *vr0max = vr1max; 5873 else if (*vr0type == VR_ANTI_RANGE 5874 && vr1type == VR_ANTI_RANGE) 5875 *vr0min = vr1min; 5876 else if (*vr0type == VR_ANTI_RANGE 5877 && vr1type == VR_RANGE) 5878 { 5879 if (TREE_CODE (vr1min) == INTEGER_CST) 5880 *vr0max = int_const_binop (MINUS_EXPR, vr1min, 5881 build_int_cst (TREE_TYPE (vr1min), 1)); 5882 else 5883 goto give_up; 5884 } 5885 else if (*vr0type == VR_RANGE 5886 && vr1type == VR_ANTI_RANGE) 5887 { 5888 if (TREE_CODE (*vr0max) == INTEGER_CST) 5889 { 5890 *vr0type = vr1type; 5891 *vr0min = int_const_binop (PLUS_EXPR, *vr0max, 5892 build_int_cst (TREE_TYPE (*vr0max), 1)); 5893 *vr0max = vr1max; 5894 } 5895 else 5896 goto give_up; 5897 } 5898 else 5899 gcc_unreachable (); 5900 } 5901 else if ((operand_less_p (*vr0min, vr1max) == 1 5902 || operand_equal_p (*vr0min, vr1max, 0)) 5903 && operand_less_p (vr1min, *vr0min) == 1 5904 && operand_less_p (vr1max, *vr0max) == 1) 5905 { 5906 /* ( [ ) ] or ( )[ ] */ 5907 if (*vr0type == VR_RANGE 5908 && vr1type == VR_RANGE) 5909 *vr0min = vr1min; 5910 else if (*vr0type == VR_ANTI_RANGE 5911 && vr1type == VR_ANTI_RANGE) 5912 *vr0max = vr1max; 5913 else if (*vr0type == VR_ANTI_RANGE 5914 && vr1type == VR_RANGE) 5915 { 5916 if (TREE_CODE (vr1max) == INTEGER_CST) 5917 *vr0min = int_const_binop (PLUS_EXPR, vr1max, 5918 build_int_cst (TREE_TYPE (vr1max), 1)); 5919 else 5920 goto give_up; 5921 } 5922 else if (*vr0type == VR_RANGE 5923 && vr1type == VR_ANTI_RANGE) 5924 { 5925 if (TREE_CODE (*vr0min) == INTEGER_CST) 5926 { 5927 *vr0type = vr1type; 5928 *vr0max = int_const_binop (MINUS_EXPR, *vr0min, 5929 build_int_cst (TREE_TYPE (*vr0min), 1)); 5930 *vr0min = vr1min; 5931 } 5932 else 5933 goto give_up; 5934 } 5935 else 5936 gcc_unreachable (); 5937 } 5938 else 5939 goto give_up; 5940 5941 return; 5942 5943 give_up: 5944 *vr0type = VR_VARYING; 5945 *vr0min = NULL_TREE; 5946 *vr0max = NULL_TREE; 5947 } 5948 5949 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and 5950 { VR1TYPE, VR0MIN, VR0MAX } and store the result 5951 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest 5952 possible such range. The resulting range is not canonicalized. */ 5953 5954 static void 5955 intersect_ranges (enum value_range_type *vr0type, 5956 tree *vr0min, tree *vr0max, 5957 enum value_range_type vr1type, 5958 tree vr1min, tree vr1max) 5959 { 5960 bool mineq = vrp_operand_equal_p (*vr0min, vr1min); 5961 bool maxeq = vrp_operand_equal_p (*vr0max, vr1max); 5962 5963 /* [] is vr0, () is vr1 in the following classification comments. */ 5964 if (mineq && maxeq) 5965 { 5966 /* [( )] */ 5967 if (*vr0type == vr1type) 5968 /* Nothing to do for equal ranges. */ 5969 ; 5970 else if ((*vr0type == VR_RANGE 5971 && vr1type == VR_ANTI_RANGE) 5972 || (*vr0type == VR_ANTI_RANGE 5973 && vr1type == VR_RANGE)) 5974 { 5975 /* For anti-range with range intersection the result is empty. */ 5976 *vr0type = VR_UNDEFINED; 5977 *vr0min = NULL_TREE; 5978 *vr0max = NULL_TREE; 5979 } 5980 else 5981 gcc_unreachable (); 5982 } 5983 else if (operand_less_p (*vr0max, vr1min) == 1 5984 || operand_less_p (vr1max, *vr0min) == 1) 5985 { 5986 /* [ ] ( ) or ( ) [ ] 5987 If the ranges have an empty intersection, the result of the 5988 intersect operation is the range for intersecting an 5989 anti-range with a range or empty when intersecting two ranges. */ 5990 if (*vr0type == VR_RANGE 5991 && vr1type == VR_ANTI_RANGE) 5992 ; 5993 else if (*vr0type == VR_ANTI_RANGE 5994 && vr1type == VR_RANGE) 5995 { 5996 *vr0type = vr1type; 5997 *vr0min = vr1min; 5998 *vr0max = vr1max; 5999 } 6000 else if (*vr0type == VR_RANGE 6001 && vr1type == VR_RANGE) 6002 { 6003 *vr0type = VR_UNDEFINED; 6004 *vr0min = NULL_TREE; 6005 *vr0max = NULL_TREE; 6006 } 6007 else if (*vr0type == VR_ANTI_RANGE 6008 && vr1type == VR_ANTI_RANGE) 6009 { 6010 /* If the anti-ranges are adjacent to each other merge them. */ 6011 if (TREE_CODE (*vr0max) == INTEGER_CST 6012 && TREE_CODE (vr1min) == INTEGER_CST 6013 && operand_less_p (*vr0max, vr1min) == 1 6014 && integer_onep (int_const_binop (MINUS_EXPR, 6015 vr1min, *vr0max))) 6016 *vr0max = vr1max; 6017 else if (TREE_CODE (vr1max) == INTEGER_CST 6018 && TREE_CODE (*vr0min) == INTEGER_CST 6019 && operand_less_p (vr1max, *vr0min) == 1 6020 && integer_onep (int_const_binop (MINUS_EXPR, 6021 *vr0min, vr1max))) 6022 *vr0min = vr1min; 6023 /* Else arbitrarily take VR0. */ 6024 } 6025 } 6026 else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1) 6027 && (mineq || operand_less_p (*vr0min, vr1min) == 1)) 6028 { 6029 /* [ ( ) ] or [( ) ] or [ ( )] */ 6030 if (*vr0type == VR_RANGE 6031 && vr1type == VR_RANGE) 6032 { 6033 /* If both are ranges the result is the inner one. */ 6034 *vr0type = vr1type; 6035 *vr0min = vr1min; 6036 *vr0max = vr1max; 6037 } 6038 else if (*vr0type == VR_RANGE 6039 && vr1type == VR_ANTI_RANGE) 6040 { 6041 /* Choose the right gap if the left one is empty. */ 6042 if (mineq) 6043 { 6044 if (TREE_CODE (vr1max) != INTEGER_CST) 6045 *vr0min = vr1max; 6046 else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1 6047 && !TYPE_UNSIGNED (TREE_TYPE (vr1max))) 6048 *vr0min 6049 = int_const_binop (MINUS_EXPR, vr1max, 6050 build_int_cst (TREE_TYPE (vr1max), -1)); 6051 else 6052 *vr0min 6053 = int_const_binop (PLUS_EXPR, vr1max, 6054 build_int_cst (TREE_TYPE (vr1max), 1)); 6055 } 6056 /* Choose the left gap if the right one is empty. */ 6057 else if (maxeq) 6058 { 6059 if (TREE_CODE (vr1min) != INTEGER_CST) 6060 *vr0max = vr1min; 6061 else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1 6062 && !TYPE_UNSIGNED (TREE_TYPE (vr1min))) 6063 *vr0max 6064 = int_const_binop (PLUS_EXPR, vr1min, 6065 build_int_cst (TREE_TYPE (vr1min), -1)); 6066 else 6067 *vr0max 6068 = int_const_binop (MINUS_EXPR, vr1min, 6069 build_int_cst (TREE_TYPE (vr1min), 1)); 6070 } 6071 /* Choose the anti-range if the range is effectively varying. */ 6072 else if (vrp_val_is_min (*vr0min) 6073 && vrp_val_is_max (*vr0max)) 6074 { 6075 *vr0type = vr1type; 6076 *vr0min = vr1min; 6077 *vr0max = vr1max; 6078 } 6079 /* Else choose the range. */ 6080 } 6081 else if (*vr0type == VR_ANTI_RANGE 6082 && vr1type == VR_ANTI_RANGE) 6083 /* If both are anti-ranges the result is the outer one. */ 6084 ; 6085 else if (*vr0type == VR_ANTI_RANGE 6086 && vr1type == VR_RANGE) 6087 { 6088 /* The intersection is empty. */ 6089 *vr0type = VR_UNDEFINED; 6090 *vr0min = NULL_TREE; 6091 *vr0max = NULL_TREE; 6092 } 6093 else 6094 gcc_unreachable (); 6095 } 6096 else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1) 6097 && (mineq || operand_less_p (vr1min, *vr0min) == 1)) 6098 { 6099 /* ( [ ] ) or ([ ] ) or ( [ ]) */ 6100 if (*vr0type == VR_RANGE 6101 && vr1type == VR_RANGE) 6102 /* Choose the inner range. */ 6103 ; 6104 else if (*vr0type == VR_ANTI_RANGE 6105 && vr1type == VR_RANGE) 6106 { 6107 /* Choose the right gap if the left is empty. */ 6108 if (mineq) 6109 { 6110 *vr0type = VR_RANGE; 6111 if (TREE_CODE (*vr0max) != INTEGER_CST) 6112 *vr0min = *vr0max; 6113 else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1 6114 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max))) 6115 *vr0min 6116 = int_const_binop (MINUS_EXPR, *vr0max, 6117 build_int_cst (TREE_TYPE (*vr0max), -1)); 6118 else 6119 *vr0min 6120 = int_const_binop (PLUS_EXPR, *vr0max, 6121 build_int_cst (TREE_TYPE (*vr0max), 1)); 6122 *vr0max = vr1max; 6123 } 6124 /* Choose the left gap if the right is empty. */ 6125 else if (maxeq) 6126 { 6127 *vr0type = VR_RANGE; 6128 if (TREE_CODE (*vr0min) != INTEGER_CST) 6129 *vr0max = *vr0min; 6130 else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1 6131 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min))) 6132 *vr0max 6133 = int_const_binop (PLUS_EXPR, *vr0min, 6134 build_int_cst (TREE_TYPE (*vr0min), -1)); 6135 else 6136 *vr0max 6137 = int_const_binop (MINUS_EXPR, *vr0min, 6138 build_int_cst (TREE_TYPE (*vr0min), 1)); 6139 *vr0min = vr1min; 6140 } 6141 /* Choose the anti-range if the range is effectively varying. */ 6142 else if (vrp_val_is_min (vr1min) 6143 && vrp_val_is_max (vr1max)) 6144 ; 6145 /* Choose the anti-range if it is ~[0,0], that range is special 6146 enough to special case when vr1's range is relatively wide. 6147 At least for types bigger than int - this covers pointers 6148 and arguments to functions like ctz. */ 6149 else if (*vr0min == *vr0max 6150 && integer_zerop (*vr0min) 6151 && ((TYPE_PRECISION (TREE_TYPE (*vr0min)) 6152 >= TYPE_PRECISION (integer_type_node)) 6153 || POINTER_TYPE_P (TREE_TYPE (*vr0min))) 6154 && TREE_CODE (vr1max) == INTEGER_CST 6155 && TREE_CODE (vr1min) == INTEGER_CST 6156 && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min)) 6157 < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2)) 6158 ; 6159 /* Else choose the range. */ 6160 else 6161 { 6162 *vr0type = vr1type; 6163 *vr0min = vr1min; 6164 *vr0max = vr1max; 6165 } 6166 } 6167 else if (*vr0type == VR_ANTI_RANGE 6168 && vr1type == VR_ANTI_RANGE) 6169 { 6170 /* If both are anti-ranges the result is the outer one. */ 6171 *vr0type = vr1type; 6172 *vr0min = vr1min; 6173 *vr0max = vr1max; 6174 } 6175 else if (vr1type == VR_ANTI_RANGE 6176 && *vr0type == VR_RANGE) 6177 { 6178 /* The intersection is empty. */ 6179 *vr0type = VR_UNDEFINED; 6180 *vr0min = NULL_TREE; 6181 *vr0max = NULL_TREE; 6182 } 6183 else 6184 gcc_unreachable (); 6185 } 6186 else if ((operand_less_p (vr1min, *vr0max) == 1 6187 || operand_equal_p (vr1min, *vr0max, 0)) 6188 && operand_less_p (*vr0min, vr1min) == 1) 6189 { 6190 /* [ ( ] ) or [ ]( ) */ 6191 if (*vr0type == VR_ANTI_RANGE 6192 && vr1type == VR_ANTI_RANGE) 6193 *vr0max = vr1max; 6194 else if (*vr0type == VR_RANGE 6195 && vr1type == VR_RANGE) 6196 *vr0min = vr1min; 6197 else if (*vr0type == VR_RANGE 6198 && vr1type == VR_ANTI_RANGE) 6199 { 6200 if (TREE_CODE (vr1min) == INTEGER_CST) 6201 *vr0max = int_const_binop (MINUS_EXPR, vr1min, 6202 build_int_cst (TREE_TYPE (vr1min), 1)); 6203 else 6204 *vr0max = vr1min; 6205 } 6206 else if (*vr0type == VR_ANTI_RANGE 6207 && vr1type == VR_RANGE) 6208 { 6209 *vr0type = VR_RANGE; 6210 if (TREE_CODE (*vr0max) == INTEGER_CST) 6211 *vr0min = int_const_binop (PLUS_EXPR, *vr0max, 6212 build_int_cst (TREE_TYPE (*vr0max), 1)); 6213 else 6214 *vr0min = *vr0max; 6215 *vr0max = vr1max; 6216 } 6217 else 6218 gcc_unreachable (); 6219 } 6220 else if ((operand_less_p (*vr0min, vr1max) == 1 6221 || operand_equal_p (*vr0min, vr1max, 0)) 6222 && operand_less_p (vr1min, *vr0min) == 1) 6223 { 6224 /* ( [ ) ] or ( )[ ] */ 6225 if (*vr0type == VR_ANTI_RANGE 6226 && vr1type == VR_ANTI_RANGE) 6227 *vr0min = vr1min; 6228 else if (*vr0type == VR_RANGE 6229 && vr1type == VR_RANGE) 6230 *vr0max = vr1max; 6231 else if (*vr0type == VR_RANGE 6232 && vr1type == VR_ANTI_RANGE) 6233 { 6234 if (TREE_CODE (vr1max) == INTEGER_CST) 6235 *vr0min = int_const_binop (PLUS_EXPR, vr1max, 6236 build_int_cst (TREE_TYPE (vr1max), 1)); 6237 else 6238 *vr0min = vr1max; 6239 } 6240 else if (*vr0type == VR_ANTI_RANGE 6241 && vr1type == VR_RANGE) 6242 { 6243 *vr0type = VR_RANGE; 6244 if (TREE_CODE (*vr0min) == INTEGER_CST) 6245 *vr0max = int_const_binop (MINUS_EXPR, *vr0min, 6246 build_int_cst (TREE_TYPE (*vr0min), 1)); 6247 else 6248 *vr0max = *vr0min; 6249 *vr0min = vr1min; 6250 } 6251 else 6252 gcc_unreachable (); 6253 } 6254 6255 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as 6256 result for the intersection. That's always a conservative 6257 correct estimate unless VR1 is a constant singleton range 6258 in which case we choose that. */ 6259 if (vr1type == VR_RANGE 6260 && is_gimple_min_invariant (vr1min) 6261 && vrp_operand_equal_p (vr1min, vr1max)) 6262 { 6263 *vr0type = vr1type; 6264 *vr0min = vr1min; 6265 *vr0max = vr1max; 6266 } 6267 6268 return; 6269 } 6270 6271 6272 /* Intersect the two value-ranges *VR0 and *VR1 and store the result 6273 in *VR0. This may not be the smallest possible such range. */ 6274 6275 static void 6276 vrp_intersect_ranges_1 (value_range *vr0, value_range *vr1) 6277 { 6278 value_range saved; 6279 6280 /* If either range is VR_VARYING the other one wins. */ 6281 if (vr1->type == VR_VARYING) 6282 return; 6283 if (vr0->type == VR_VARYING) 6284 { 6285 copy_value_range (vr0, vr1); 6286 return; 6287 } 6288 6289 /* When either range is VR_UNDEFINED the resulting range is 6290 VR_UNDEFINED, too. */ 6291 if (vr0->type == VR_UNDEFINED) 6292 return; 6293 if (vr1->type == VR_UNDEFINED) 6294 { 6295 set_value_range_to_undefined (vr0); 6296 return; 6297 } 6298 6299 /* Save the original vr0 so we can return it as conservative intersection 6300 result when our worker turns things to varying. */ 6301 saved = *vr0; 6302 intersect_ranges (&vr0->type, &vr0->min, &vr0->max, 6303 vr1->type, vr1->min, vr1->max); 6304 /* Make sure to canonicalize the result though as the inversion of a 6305 VR_RANGE can still be a VR_RANGE. */ 6306 set_and_canonicalize_value_range (vr0, vr0->type, 6307 vr0->min, vr0->max, vr0->equiv); 6308 /* If that failed, use the saved original VR0. */ 6309 if (vr0->type == VR_VARYING) 6310 { 6311 *vr0 = saved; 6312 return; 6313 } 6314 /* If the result is VR_UNDEFINED there is no need to mess with 6315 the equivalencies. */ 6316 if (vr0->type == VR_UNDEFINED) 6317 return; 6318 6319 /* The resulting set of equivalences for range intersection is the union of 6320 the two sets. */ 6321 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 6322 bitmap_ior_into (vr0->equiv, vr1->equiv); 6323 else if (vr1->equiv && !vr0->equiv) 6324 { 6325 /* All equivalence bitmaps are allocated from the same obstack. So 6326 we can use the obstack associated with VR to allocate vr0->equiv. */ 6327 vr0->equiv = BITMAP_ALLOC (vr1->equiv->obstack); 6328 bitmap_copy (vr0->equiv, vr1->equiv); 6329 } 6330 } 6331 6332 void 6333 vrp_intersect_ranges (value_range *vr0, value_range *vr1) 6334 { 6335 if (dump_file && (dump_flags & TDF_DETAILS)) 6336 { 6337 fprintf (dump_file, "Intersecting\n "); 6338 dump_value_range (dump_file, vr0); 6339 fprintf (dump_file, "\nand\n "); 6340 dump_value_range (dump_file, vr1); 6341 fprintf (dump_file, "\n"); 6342 } 6343 vrp_intersect_ranges_1 (vr0, vr1); 6344 if (dump_file && (dump_flags & TDF_DETAILS)) 6345 { 6346 fprintf (dump_file, "to\n "); 6347 dump_value_range (dump_file, vr0); 6348 fprintf (dump_file, "\n"); 6349 } 6350 } 6351 6352 /* Meet operation for value ranges. Given two value ranges VR0 and 6353 VR1, store in VR0 a range that contains both VR0 and VR1. This 6354 may not be the smallest possible such range. */ 6355 6356 static void 6357 vrp_meet_1 (value_range *vr0, const value_range *vr1) 6358 { 6359 value_range saved; 6360 6361 if (vr0->type == VR_UNDEFINED) 6362 { 6363 set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv); 6364 return; 6365 } 6366 6367 if (vr1->type == VR_UNDEFINED) 6368 { 6369 /* VR0 already has the resulting range. */ 6370 return; 6371 } 6372 6373 if (vr0->type == VR_VARYING) 6374 { 6375 /* Nothing to do. VR0 already has the resulting range. */ 6376 return; 6377 } 6378 6379 if (vr1->type == VR_VARYING) 6380 { 6381 set_value_range_to_varying (vr0); 6382 return; 6383 } 6384 6385 saved = *vr0; 6386 union_ranges (&vr0->type, &vr0->min, &vr0->max, 6387 vr1->type, vr1->min, vr1->max); 6388 if (vr0->type == VR_VARYING) 6389 { 6390 /* Failed to find an efficient meet. Before giving up and setting 6391 the result to VARYING, see if we can at least derive a useful 6392 anti-range. FIXME, all this nonsense about distinguishing 6393 anti-ranges from ranges is necessary because of the odd 6394 semantics of range_includes_zero_p and friends. */ 6395 if (((saved.type == VR_RANGE 6396 && range_includes_zero_p (saved.min, saved.max) == 0) 6397 || (saved.type == VR_ANTI_RANGE 6398 && range_includes_zero_p (saved.min, saved.max) == 1)) 6399 && ((vr1->type == VR_RANGE 6400 && range_includes_zero_p (vr1->min, vr1->max) == 0) 6401 || (vr1->type == VR_ANTI_RANGE 6402 && range_includes_zero_p (vr1->min, vr1->max) == 1))) 6403 { 6404 set_value_range_to_nonnull (vr0, TREE_TYPE (saved.min)); 6405 6406 /* Since this meet operation did not result from the meeting of 6407 two equivalent names, VR0 cannot have any equivalences. */ 6408 if (vr0->equiv) 6409 bitmap_clear (vr0->equiv); 6410 return; 6411 } 6412 6413 set_value_range_to_varying (vr0); 6414 return; 6415 } 6416 set_and_canonicalize_value_range (vr0, vr0->type, vr0->min, vr0->max, 6417 vr0->equiv); 6418 if (vr0->type == VR_VARYING) 6419 return; 6420 6421 /* The resulting set of equivalences is always the intersection of 6422 the two sets. */ 6423 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 6424 bitmap_and_into (vr0->equiv, vr1->equiv); 6425 else if (vr0->equiv && !vr1->equiv) 6426 bitmap_clear (vr0->equiv); 6427 } 6428 6429 void 6430 vrp_meet (value_range *vr0, const value_range *vr1) 6431 { 6432 if (dump_file && (dump_flags & TDF_DETAILS)) 6433 { 6434 fprintf (dump_file, "Meeting\n "); 6435 dump_value_range (dump_file, vr0); 6436 fprintf (dump_file, "\nand\n "); 6437 dump_value_range (dump_file, vr1); 6438 fprintf (dump_file, "\n"); 6439 } 6440 vrp_meet_1 (vr0, vr1); 6441 if (dump_file && (dump_flags & TDF_DETAILS)) 6442 { 6443 fprintf (dump_file, "to\n "); 6444 dump_value_range (dump_file, vr0); 6445 fprintf (dump_file, "\n"); 6446 } 6447 } 6448 6449 6450 /* Visit all arguments for PHI node PHI that flow through executable 6451 edges. If a valid value range can be derived from all the incoming 6452 value ranges, set a new range for the LHS of PHI. */ 6453 6454 enum ssa_prop_result 6455 vrp_prop::visit_phi (gphi *phi) 6456 { 6457 tree lhs = PHI_RESULT (phi); 6458 value_range vr_result = VR_INITIALIZER; 6459 extract_range_from_phi_node (phi, &vr_result); 6460 if (update_value_range (lhs, &vr_result)) 6461 { 6462 if (dump_file && (dump_flags & TDF_DETAILS)) 6463 { 6464 fprintf (dump_file, "Found new range for "); 6465 print_generic_expr (dump_file, lhs); 6466 fprintf (dump_file, ": "); 6467 dump_value_range (dump_file, &vr_result); 6468 fprintf (dump_file, "\n"); 6469 } 6470 6471 if (vr_result.type == VR_VARYING) 6472 return SSA_PROP_VARYING; 6473 6474 return SSA_PROP_INTERESTING; 6475 } 6476 6477 /* Nothing changed, don't add outgoing edges. */ 6478 return SSA_PROP_NOT_INTERESTING; 6479 } 6480 6481 class vrp_folder : public substitute_and_fold_engine 6482 { 6483 public: 6484 tree get_value (tree) FINAL OVERRIDE; 6485 bool fold_stmt (gimple_stmt_iterator *) FINAL OVERRIDE; 6486 bool fold_predicate_in (gimple_stmt_iterator *); 6487 6488 class vr_values *vr_values; 6489 6490 /* Delegators. */ 6491 tree vrp_evaluate_conditional (tree_code code, tree op0, 6492 tree op1, gimple *stmt) 6493 { return vr_values->vrp_evaluate_conditional (code, op0, op1, stmt); } 6494 bool simplify_stmt_using_ranges (gimple_stmt_iterator *gsi) 6495 { return vr_values->simplify_stmt_using_ranges (gsi); } 6496 tree op_with_constant_singleton_value_range (tree op) 6497 { return vr_values->op_with_constant_singleton_value_range (op); } 6498 }; 6499 6500 /* If the statement pointed by SI has a predicate whose value can be 6501 computed using the value range information computed by VRP, compute 6502 its value and return true. Otherwise, return false. */ 6503 6504 bool 6505 vrp_folder::fold_predicate_in (gimple_stmt_iterator *si) 6506 { 6507 bool assignment_p = false; 6508 tree val; 6509 gimple *stmt = gsi_stmt (*si); 6510 6511 if (is_gimple_assign (stmt) 6512 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison) 6513 { 6514 assignment_p = true; 6515 val = vrp_evaluate_conditional (gimple_assign_rhs_code (stmt), 6516 gimple_assign_rhs1 (stmt), 6517 gimple_assign_rhs2 (stmt), 6518 stmt); 6519 } 6520 else if (gcond *cond_stmt = dyn_cast <gcond *> (stmt)) 6521 val = vrp_evaluate_conditional (gimple_cond_code (cond_stmt), 6522 gimple_cond_lhs (cond_stmt), 6523 gimple_cond_rhs (cond_stmt), 6524 stmt); 6525 else 6526 return false; 6527 6528 if (val) 6529 { 6530 if (assignment_p) 6531 val = fold_convert (gimple_expr_type (stmt), val); 6532 6533 if (dump_file) 6534 { 6535 fprintf (dump_file, "Folding predicate "); 6536 print_gimple_expr (dump_file, stmt, 0); 6537 fprintf (dump_file, " to "); 6538 print_generic_expr (dump_file, val); 6539 fprintf (dump_file, "\n"); 6540 } 6541 6542 if (is_gimple_assign (stmt)) 6543 gimple_assign_set_rhs_from_tree (si, val); 6544 else 6545 { 6546 gcc_assert (gimple_code (stmt) == GIMPLE_COND); 6547 gcond *cond_stmt = as_a <gcond *> (stmt); 6548 if (integer_zerop (val)) 6549 gimple_cond_make_false (cond_stmt); 6550 else if (integer_onep (val)) 6551 gimple_cond_make_true (cond_stmt); 6552 else 6553 gcc_unreachable (); 6554 } 6555 6556 return true; 6557 } 6558 6559 return false; 6560 } 6561 6562 /* Callback for substitute_and_fold folding the stmt at *SI. */ 6563 6564 bool 6565 vrp_folder::fold_stmt (gimple_stmt_iterator *si) 6566 { 6567 if (fold_predicate_in (si)) 6568 return true; 6569 6570 return simplify_stmt_using_ranges (si); 6571 } 6572 6573 /* If OP has a value range with a single constant value return that, 6574 otherwise return NULL_TREE. This returns OP itself if OP is a 6575 constant. 6576 6577 Implemented as a pure wrapper right now, but this will change. */ 6578 6579 tree 6580 vrp_folder::get_value (tree op) 6581 { 6582 return op_with_constant_singleton_value_range (op); 6583 } 6584 6585 /* Return the LHS of any ASSERT_EXPR where OP appears as the first 6586 argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates 6587 BB. If no such ASSERT_EXPR is found, return OP. */ 6588 6589 static tree 6590 lhs_of_dominating_assert (tree op, basic_block bb, gimple *stmt) 6591 { 6592 imm_use_iterator imm_iter; 6593 gimple *use_stmt; 6594 use_operand_p use_p; 6595 6596 if (TREE_CODE (op) == SSA_NAME) 6597 { 6598 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op) 6599 { 6600 use_stmt = USE_STMT (use_p); 6601 if (use_stmt != stmt 6602 && gimple_assign_single_p (use_stmt) 6603 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR 6604 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op 6605 && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt))) 6606 return gimple_assign_lhs (use_stmt); 6607 } 6608 } 6609 return op; 6610 } 6611 6612 /* A hack. */ 6613 static class vr_values *x_vr_values; 6614 6615 /* A trivial wrapper so that we can present the generic jump threading 6616 code with a simple API for simplifying statements. STMT is the 6617 statement we want to simplify, WITHIN_STMT provides the location 6618 for any overflow warnings. */ 6619 6620 static tree 6621 simplify_stmt_for_jump_threading (gimple *stmt, gimple *within_stmt, 6622 class avail_exprs_stack *avail_exprs_stack ATTRIBUTE_UNUSED, 6623 basic_block bb) 6624 { 6625 /* First see if the conditional is in the hash table. */ 6626 tree cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, false, true); 6627 if (cached_lhs && is_gimple_min_invariant (cached_lhs)) 6628 return cached_lhs; 6629 6630 vr_values *vr_values = x_vr_values; 6631 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt)) 6632 { 6633 tree op0 = gimple_cond_lhs (cond_stmt); 6634 op0 = lhs_of_dominating_assert (op0, bb, stmt); 6635 6636 tree op1 = gimple_cond_rhs (cond_stmt); 6637 op1 = lhs_of_dominating_assert (op1, bb, stmt); 6638 6639 return vr_values->vrp_evaluate_conditional (gimple_cond_code (cond_stmt), 6640 op0, op1, within_stmt); 6641 } 6642 6643 /* We simplify a switch statement by trying to determine which case label 6644 will be taken. If we are successful then we return the corresponding 6645 CASE_LABEL_EXPR. */ 6646 if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt)) 6647 { 6648 tree op = gimple_switch_index (switch_stmt); 6649 if (TREE_CODE (op) != SSA_NAME) 6650 return NULL_TREE; 6651 6652 op = lhs_of_dominating_assert (op, bb, stmt); 6653 6654 value_range *vr = vr_values->get_value_range (op); 6655 if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE) 6656 || symbolic_range_p (vr)) 6657 return NULL_TREE; 6658 6659 if (vr->type == VR_RANGE) 6660 { 6661 size_t i, j; 6662 /* Get the range of labels that contain a part of the operand's 6663 value range. */ 6664 find_case_label_range (switch_stmt, vr->min, vr->max, &i, &j); 6665 6666 /* Is there only one such label? */ 6667 if (i == j) 6668 { 6669 tree label = gimple_switch_label (switch_stmt, i); 6670 6671 /* The i'th label will be taken only if the value range of the 6672 operand is entirely within the bounds of this label. */ 6673 if (CASE_HIGH (label) != NULL_TREE 6674 ? (tree_int_cst_compare (CASE_LOW (label), vr->min) <= 0 6675 && tree_int_cst_compare (CASE_HIGH (label), vr->max) >= 0) 6676 : (tree_int_cst_equal (CASE_LOW (label), vr->min) 6677 && tree_int_cst_equal (vr->min, vr->max))) 6678 return label; 6679 } 6680 6681 /* If there are no such labels then the default label will be 6682 taken. */ 6683 if (i > j) 6684 return gimple_switch_label (switch_stmt, 0); 6685 } 6686 6687 if (vr->type == VR_ANTI_RANGE) 6688 { 6689 unsigned n = gimple_switch_num_labels (switch_stmt); 6690 tree min_label = gimple_switch_label (switch_stmt, 1); 6691 tree max_label = gimple_switch_label (switch_stmt, n - 1); 6692 6693 /* The default label will be taken only if the anti-range of the 6694 operand is entirely outside the bounds of all the (non-default) 6695 case labels. */ 6696 if (tree_int_cst_compare (vr->min, CASE_LOW (min_label)) <= 0 6697 && (CASE_HIGH (max_label) != NULL_TREE 6698 ? tree_int_cst_compare (vr->max, CASE_HIGH (max_label)) >= 0 6699 : tree_int_cst_compare (vr->max, CASE_LOW (max_label)) >= 0)) 6700 return gimple_switch_label (switch_stmt, 0); 6701 } 6702 6703 return NULL_TREE; 6704 } 6705 6706 if (gassign *assign_stmt = dyn_cast <gassign *> (stmt)) 6707 { 6708 tree lhs = gimple_assign_lhs (assign_stmt); 6709 if (TREE_CODE (lhs) == SSA_NAME 6710 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 6711 || POINTER_TYPE_P (TREE_TYPE (lhs))) 6712 && stmt_interesting_for_vrp (stmt)) 6713 { 6714 edge dummy_e; 6715 tree dummy_tree; 6716 value_range new_vr = VR_INITIALIZER; 6717 vr_values->extract_range_from_stmt (stmt, &dummy_e, 6718 &dummy_tree, &new_vr); 6719 if (range_int_cst_singleton_p (&new_vr)) 6720 return new_vr.min; 6721 } 6722 } 6723 6724 return NULL_TREE; 6725 } 6726 6727 class vrp_dom_walker : public dom_walker 6728 { 6729 public: 6730 vrp_dom_walker (cdi_direction direction, 6731 class const_and_copies *const_and_copies, 6732 class avail_exprs_stack *avail_exprs_stack) 6733 : dom_walker (direction, REACHABLE_BLOCKS), 6734 m_const_and_copies (const_and_copies), 6735 m_avail_exprs_stack (avail_exprs_stack), 6736 m_dummy_cond (NULL) {} 6737 6738 virtual edge before_dom_children (basic_block); 6739 virtual void after_dom_children (basic_block); 6740 6741 class vr_values *vr_values; 6742 6743 private: 6744 class const_and_copies *m_const_and_copies; 6745 class avail_exprs_stack *m_avail_exprs_stack; 6746 6747 gcond *m_dummy_cond; 6748 6749 }; 6750 6751 /* Called before processing dominator children of BB. We want to look 6752 at ASSERT_EXPRs and record information from them in the appropriate 6753 tables. 6754 6755 We could look at other statements here. It's not seen as likely 6756 to significantly increase the jump threads we discover. */ 6757 6758 edge 6759 vrp_dom_walker::before_dom_children (basic_block bb) 6760 { 6761 gimple_stmt_iterator gsi; 6762 6763 m_avail_exprs_stack->push_marker (); 6764 m_const_and_copies->push_marker (); 6765 for (gsi = gsi_start_nondebug_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 6766 { 6767 gimple *stmt = gsi_stmt (gsi); 6768 if (gimple_assign_single_p (stmt) 6769 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR) 6770 { 6771 tree rhs1 = gimple_assign_rhs1 (stmt); 6772 tree cond = TREE_OPERAND (rhs1, 1); 6773 tree inverted = invert_truthvalue (cond); 6774 vec<cond_equivalence> p; 6775 p.create (3); 6776 record_conditions (&p, cond, inverted); 6777 for (unsigned int i = 0; i < p.length (); i++) 6778 m_avail_exprs_stack->record_cond (&p[i]); 6779 6780 tree lhs = gimple_assign_lhs (stmt); 6781 m_const_and_copies->record_const_or_copy (lhs, 6782 TREE_OPERAND (rhs1, 0)); 6783 p.release (); 6784 continue; 6785 } 6786 break; 6787 } 6788 return NULL; 6789 } 6790 6791 /* Called after processing dominator children of BB. This is where we 6792 actually call into the threader. */ 6793 void 6794 vrp_dom_walker::after_dom_children (basic_block bb) 6795 { 6796 if (!m_dummy_cond) 6797 m_dummy_cond = gimple_build_cond (NE_EXPR, 6798 integer_zero_node, integer_zero_node, 6799 NULL, NULL); 6800 6801 x_vr_values = vr_values; 6802 thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies, 6803 m_avail_exprs_stack, NULL, 6804 simplify_stmt_for_jump_threading); 6805 x_vr_values = NULL; 6806 6807 m_avail_exprs_stack->pop_to_marker (); 6808 m_const_and_copies->pop_to_marker (); 6809 } 6810 6811 /* Blocks which have more than one predecessor and more than 6812 one successor present jump threading opportunities, i.e., 6813 when the block is reached from a specific predecessor, we 6814 may be able to determine which of the outgoing edges will 6815 be traversed. When this optimization applies, we are able 6816 to avoid conditionals at runtime and we may expose secondary 6817 optimization opportunities. 6818 6819 This routine is effectively a driver for the generic jump 6820 threading code. It basically just presents the generic code 6821 with edges that may be suitable for jump threading. 6822 6823 Unlike DOM, we do not iterate VRP if jump threading was successful. 6824 While iterating may expose new opportunities for VRP, it is expected 6825 those opportunities would be very limited and the compile time cost 6826 to expose those opportunities would be significant. 6827 6828 As jump threading opportunities are discovered, they are registered 6829 for later realization. */ 6830 6831 static void 6832 identify_jump_threads (class vr_values *vr_values) 6833 { 6834 int i; 6835 edge e; 6836 6837 /* Ugh. When substituting values earlier in this pass we can 6838 wipe the dominance information. So rebuild the dominator 6839 information as we need it within the jump threading code. */ 6840 calculate_dominance_info (CDI_DOMINATORS); 6841 6842 /* We do not allow VRP information to be used for jump threading 6843 across a back edge in the CFG. Otherwise it becomes too 6844 difficult to avoid eliminating loop exit tests. Of course 6845 EDGE_DFS_BACK is not accurate at this time so we have to 6846 recompute it. */ 6847 mark_dfs_back_edges (); 6848 6849 /* Do not thread across edges we are about to remove. Just marking 6850 them as EDGE_IGNORE will do. */ 6851 FOR_EACH_VEC_ELT (to_remove_edges, i, e) 6852 e->flags |= EDGE_IGNORE; 6853 6854 /* Allocate our unwinder stack to unwind any temporary equivalences 6855 that might be recorded. */ 6856 const_and_copies *equiv_stack = new const_and_copies (); 6857 6858 hash_table<expr_elt_hasher> *avail_exprs 6859 = new hash_table<expr_elt_hasher> (1024); 6860 avail_exprs_stack *avail_exprs_stack 6861 = new class avail_exprs_stack (avail_exprs); 6862 6863 vrp_dom_walker walker (CDI_DOMINATORS, equiv_stack, avail_exprs_stack); 6864 walker.vr_values = vr_values; 6865 walker.walk (cfun->cfg->x_entry_block_ptr); 6866 6867 /* Clear EDGE_IGNORE. */ 6868 FOR_EACH_VEC_ELT (to_remove_edges, i, e) 6869 e->flags &= ~EDGE_IGNORE; 6870 6871 /* We do not actually update the CFG or SSA graphs at this point as 6872 ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet 6873 handle ASSERT_EXPRs gracefully. */ 6874 delete equiv_stack; 6875 delete avail_exprs; 6876 delete avail_exprs_stack; 6877 } 6878 6879 /* Traverse all the blocks folding conditionals with known ranges. */ 6880 6881 void 6882 vrp_prop::vrp_finalize (bool warn_array_bounds_p) 6883 { 6884 size_t i; 6885 6886 /* We have completed propagating through the lattice. */ 6887 vr_values.set_lattice_propagation_complete (); 6888 6889 if (dump_file) 6890 { 6891 fprintf (dump_file, "\nValue ranges after VRP:\n\n"); 6892 vr_values.dump_all_value_ranges (dump_file); 6893 fprintf (dump_file, "\n"); 6894 } 6895 6896 /* Set value range to non pointer SSA_NAMEs. */ 6897 for (i = 0; i < num_ssa_names; i++) 6898 { 6899 tree name = ssa_name (i); 6900 if (!name) 6901 continue; 6902 6903 value_range *vr = get_value_range (name); 6904 if (!name 6905 || (vr->type == VR_VARYING) 6906 || (vr->type == VR_UNDEFINED) 6907 || (TREE_CODE (vr->min) != INTEGER_CST) 6908 || (TREE_CODE (vr->max) != INTEGER_CST)) 6909 continue; 6910 6911 if (POINTER_TYPE_P (TREE_TYPE (name)) 6912 && ((vr->type == VR_RANGE 6913 && range_includes_zero_p (vr->min, vr->max) == 0) 6914 || (vr->type == VR_ANTI_RANGE 6915 && range_includes_zero_p (vr->min, vr->max) == 1))) 6916 set_ptr_nonnull (name); 6917 else if (!POINTER_TYPE_P (TREE_TYPE (name))) 6918 set_range_info (name, vr->type, 6919 wi::to_wide (vr->min), 6920 wi::to_wide (vr->max)); 6921 } 6922 6923 /* If we're checking array refs, we want to merge information on 6924 the executability of each edge between vrp_folder and the 6925 check_array_bounds_dom_walker: each can clear the 6926 EDGE_EXECUTABLE flag on edges, in different ways. 6927 6928 Hence, if we're going to call check_all_array_refs, set 6929 the flag on every edge now, rather than in 6930 check_array_bounds_dom_walker's ctor; vrp_folder may clear 6931 it from some edges. */ 6932 if (warn_array_bounds && warn_array_bounds_p) 6933 set_all_edges_as_executable (cfun); 6934 6935 class vrp_folder vrp_folder; 6936 vrp_folder.vr_values = &vr_values; 6937 vrp_folder.substitute_and_fold (); 6938 6939 if (warn_array_bounds && warn_array_bounds_p) 6940 check_all_array_refs (); 6941 } 6942 6943 /* Main entry point to VRP (Value Range Propagation). This pass is 6944 loosely based on J. R. C. Patterson, ``Accurate Static Branch 6945 Prediction by Value Range Propagation,'' in SIGPLAN Conference on 6946 Programming Language Design and Implementation, pp. 67-78, 1995. 6947 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html 6948 6949 This is essentially an SSA-CCP pass modified to deal with ranges 6950 instead of constants. 6951 6952 While propagating ranges, we may find that two or more SSA name 6953 have equivalent, though distinct ranges. For instance, 6954 6955 1 x_9 = p_3->a; 6956 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0> 6957 3 if (p_4 == q_2) 6958 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>; 6959 5 endif 6960 6 if (q_2) 6961 6962 In the code above, pointer p_5 has range [q_2, q_2], but from the 6963 code we can also determine that p_5 cannot be NULL and, if q_2 had 6964 a non-varying range, p_5's range should also be compatible with it. 6965 6966 These equivalences are created by two expressions: ASSERT_EXPR and 6967 copy operations. Since p_5 is an assertion on p_4, and p_4 was the 6968 result of another assertion, then we can use the fact that p_5 and 6969 p_4 are equivalent when evaluating p_5's range. 6970 6971 Together with value ranges, we also propagate these equivalences 6972 between names so that we can take advantage of information from 6973 multiple ranges when doing final replacement. Note that this 6974 equivalency relation is transitive but not symmetric. 6975 6976 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we 6977 cannot assert that q_2 is equivalent to p_5 because q_2 may be used 6978 in contexts where that assertion does not hold (e.g., in line 6). 6979 6980 TODO, the main difference between this pass and Patterson's is that 6981 we do not propagate edge probabilities. We only compute whether 6982 edges can be taken or not. That is, instead of having a spectrum 6983 of jump probabilities between 0 and 1, we only deal with 0, 1 and 6984 DON'T KNOW. In the future, it may be worthwhile to propagate 6985 probabilities to aid branch prediction. */ 6986 6987 static unsigned int 6988 execute_vrp (bool warn_array_bounds_p) 6989 { 6990 int i; 6991 edge e; 6992 switch_update *su; 6993 6994 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); 6995 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 6996 scev_initialize (); 6997 6998 /* ??? This ends up using stale EDGE_DFS_BACK for liveness computation. 6999 Inserting assertions may split edges which will invalidate 7000 EDGE_DFS_BACK. */ 7001 insert_range_assertions (); 7002 7003 to_remove_edges.create (10); 7004 to_update_switch_stmts.create (5); 7005 threadedge_initialize_values (); 7006 7007 /* For visiting PHI nodes we need EDGE_DFS_BACK computed. */ 7008 mark_dfs_back_edges (); 7009 7010 class vrp_prop vrp_prop; 7011 vrp_prop.vrp_initialize (); 7012 vrp_prop.ssa_propagate (); 7013 vrp_prop.vrp_finalize (warn_array_bounds_p); 7014 7015 /* We must identify jump threading opportunities before we release 7016 the datastructures built by VRP. */ 7017 identify_jump_threads (&vrp_prop.vr_values); 7018 7019 /* A comparison of an SSA_NAME against a constant where the SSA_NAME 7020 was set by a type conversion can often be rewritten to use the 7021 RHS of the type conversion. 7022 7023 However, doing so inhibits jump threading through the comparison. 7024 So that transformation is not performed until after jump threading 7025 is complete. */ 7026 basic_block bb; 7027 FOR_EACH_BB_FN (bb, cfun) 7028 { 7029 gimple *last = last_stmt (bb); 7030 if (last && gimple_code (last) == GIMPLE_COND) 7031 vrp_prop.vr_values.simplify_cond_using_ranges_2 (as_a <gcond *> (last)); 7032 } 7033 7034 free_numbers_of_iterations_estimates (cfun); 7035 7036 /* ASSERT_EXPRs must be removed before finalizing jump threads 7037 as finalizing jump threads calls the CFG cleanup code which 7038 does not properly handle ASSERT_EXPRs. */ 7039 remove_range_assertions (); 7040 7041 /* If we exposed any new variables, go ahead and put them into 7042 SSA form now, before we handle jump threading. This simplifies 7043 interactions between rewriting of _DECL nodes into SSA form 7044 and rewriting SSA_NAME nodes into SSA form after block 7045 duplication and CFG manipulation. */ 7046 update_ssa (TODO_update_ssa); 7047 7048 /* We identified all the jump threading opportunities earlier, but could 7049 not transform the CFG at that time. This routine transforms the 7050 CFG and arranges for the dominator tree to be rebuilt if necessary. 7051 7052 Note the SSA graph update will occur during the normal TODO 7053 processing by the pass manager. */ 7054 thread_through_all_blocks (false); 7055 7056 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the 7057 CFG in a broken state and requires a cfg_cleanup run. */ 7058 FOR_EACH_VEC_ELT (to_remove_edges, i, e) 7059 remove_edge (e); 7060 /* Update SWITCH_EXPR case label vector. */ 7061 FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su) 7062 { 7063 size_t j; 7064 size_t n = TREE_VEC_LENGTH (su->vec); 7065 tree label; 7066 gimple_switch_set_num_labels (su->stmt, n); 7067 for (j = 0; j < n; j++) 7068 gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j)); 7069 /* As we may have replaced the default label with a regular one 7070 make sure to make it a real default label again. This ensures 7071 optimal expansion. */ 7072 label = gimple_switch_label (su->stmt, 0); 7073 CASE_LOW (label) = NULL_TREE; 7074 CASE_HIGH (label) = NULL_TREE; 7075 } 7076 7077 if (to_remove_edges.length () > 0) 7078 { 7079 free_dominance_info (CDI_DOMINATORS); 7080 loops_state_set (LOOPS_NEED_FIXUP); 7081 } 7082 7083 to_remove_edges.release (); 7084 to_update_switch_stmts.release (); 7085 threadedge_finalize_values (); 7086 7087 scev_finalize (); 7088 loop_optimizer_finalize (); 7089 return 0; 7090 } 7091 7092 namespace { 7093 7094 const pass_data pass_data_vrp = 7095 { 7096 GIMPLE_PASS, /* type */ 7097 "vrp", /* name */ 7098 OPTGROUP_NONE, /* optinfo_flags */ 7099 TV_TREE_VRP, /* tv_id */ 7100 PROP_ssa, /* properties_required */ 7101 0, /* properties_provided */ 7102 0, /* properties_destroyed */ 7103 0, /* todo_flags_start */ 7104 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */ 7105 }; 7106 7107 class pass_vrp : public gimple_opt_pass 7108 { 7109 public: 7110 pass_vrp (gcc::context *ctxt) 7111 : gimple_opt_pass (pass_data_vrp, ctxt), warn_array_bounds_p (false) 7112 {} 7113 7114 /* opt_pass methods: */ 7115 opt_pass * clone () { return new pass_vrp (m_ctxt); } 7116 void set_pass_param (unsigned int n, bool param) 7117 { 7118 gcc_assert (n == 0); 7119 warn_array_bounds_p = param; 7120 } 7121 virtual bool gate (function *) { return flag_tree_vrp != 0; } 7122 virtual unsigned int execute (function *) 7123 { return execute_vrp (warn_array_bounds_p); } 7124 7125 private: 7126 bool warn_array_bounds_p; 7127 }; // class pass_vrp 7128 7129 } // anon namespace 7130 7131 gimple_opt_pass * 7132 make_pass_vrp (gcc::context *ctxt) 7133 { 7134 return new pass_vrp (ctxt); 7135 } 7136