1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
34 #include "tree-pretty-print.h"
35 #include "gimple-pretty-print.h"
36 #include "diagnostic-core.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-ssa-propagate.h"
41 #include "tree-chrec.h"
44 /* Type of value ranges. See value_range_d for a description of these
46 enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
48 /* Range of values that can be associated with an SSA_NAME after VRP
52 /* Lattice value represented by this range. */
53 enum value_range_type type;
55 /* Minimum and maximum values represented by this range. These
56 values should be interpreted as follows:
58 - If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must
61 - If TYPE == VR_RANGE then MIN holds the minimum value and
62 MAX holds the maximum value of the range [MIN, MAX].
64 - If TYPE == ANTI_RANGE the variable is known to NOT
65 take any values in the range [MIN, MAX]. */
69 /* Set of SSA names whose value ranges are equivalent to this one.
70 This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */
74 typedef struct value_range_d value_range_t;
76 /* Set of SSA names found live during the RPO traversal of the function
77 for still active basic-blocks. */
80 /* Return true if the SSA name NAME is live on the edge E. */
83 live_on_edge (edge e, tree name)
85 return (live[e->dest->index]
86 && TEST_BIT (live[e->dest->index], SSA_NAME_VERSION (name)));
89 /* Local functions. */
90 static int compare_values (tree val1, tree val2);
91 static int compare_values_warnv (tree val1, tree val2, bool *);
92 static void vrp_meet (value_range_t *, value_range_t *);
93 static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
94 tree, tree, bool, bool *,
97 /* Location information for ASSERT_EXPRs. Each instance of this
98 structure describes an ASSERT_EXPR for an SSA name. Since a single
99 SSA name may have more than one assertion associated with it, these
100 locations are kept in a linked list attached to the corresponding
102 struct assert_locus_d
104 /* Basic block where the assertion would be inserted. */
107 /* Some assertions need to be inserted on an edge (e.g., assertions
108 generated by COND_EXPRs). In those cases, BB will be NULL. */
111 /* Pointer to the statement that generated this assertion. */
112 gimple_stmt_iterator si;
114 /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
115 enum tree_code comp_code;
117 /* Value being compared against. */
120 /* Expression to compare. */
123 /* Next node in the linked list. */
124 struct assert_locus_d *next;
127 typedef struct assert_locus_d *assert_locus_t;
129 /* If bit I is present, it means that SSA name N_i has a list of
130 assertions that should be inserted in the IL. */
131 static bitmap need_assert_for;
133 /* Array of locations lists where to insert assertions. ASSERTS_FOR[I]
134 holds a list of ASSERT_LOCUS_T nodes that describe where
135 ASSERT_EXPRs for SSA name N_I should be inserted. */
136 static assert_locus_t *asserts_for;
138 /* Value range array. After propagation, VR_VALUE[I] holds the range
139 of values that SSA name N_I may take. */
140 static value_range_t **vr_value;
142 /* For a PHI node which sets SSA name N_I, VR_COUNTS[I] holds the
143 number of executable edges we saw the last time we visited the
145 static int *vr_phi_edge_counts;
152 static VEC (edge, heap) *to_remove_edges;
153 DEF_VEC_O(switch_update);
154 DEF_VEC_ALLOC_O(switch_update, heap);
155 static VEC (switch_update, heap) *to_update_switch_stmts;
158 /* Return the maximum value for TYPE. */
161 vrp_val_max (const_tree type)
163 if (!INTEGRAL_TYPE_P (type))
166 return TYPE_MAX_VALUE (type);
169 /* Return the minimum value for TYPE. */
172 vrp_val_min (const_tree type)
174 if (!INTEGRAL_TYPE_P (type))
177 return TYPE_MIN_VALUE (type);
180 /* Return whether VAL is equal to the maximum value of its type. This
181 will be true for a positive overflow infinity. We can't do a
182 simple equality comparison with TYPE_MAX_VALUE because C typedefs
183 and Ada subtypes can produce types whose TYPE_MAX_VALUE is not ==
184 to the integer constant with the same value in the type. */
187 vrp_val_is_max (const_tree val)
189 tree type_max = vrp_val_max (TREE_TYPE (val));
190 return (val == type_max
191 || (type_max != NULL_TREE
192 && operand_equal_p (val, type_max, 0)));
195 /* Return whether VAL is equal to the minimum value of its type. This
196 will be true for a negative overflow infinity. */
199 vrp_val_is_min (const_tree val)
201 tree type_min = vrp_val_min (TREE_TYPE (val));
202 return (val == type_min
203 || (type_min != NULL_TREE
204 && operand_equal_p (val, type_min, 0)));
208 /* Return whether TYPE should use an overflow infinity distinct from
209 TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to
210 represent a signed overflow during VRP computations. An infinity
211 is distinct from a half-range, which will go from some number to
212 TYPE_{MIN,MAX}_VALUE. */
215 needs_overflow_infinity (const_tree type)
217 return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type);
220 /* Return whether TYPE can support our overflow infinity
221 representation: we use the TREE_OVERFLOW flag, which only exists
222 for constants. If TYPE doesn't support this, we don't optimize
223 cases which would require signed overflow--we drop them to
227 supports_overflow_infinity (const_tree type)
229 tree min = vrp_val_min (type), max = vrp_val_max (type);
230 #ifdef ENABLE_CHECKING
231 gcc_assert (needs_overflow_infinity (type));
233 return (min != NULL_TREE
234 && CONSTANT_CLASS_P (min)
236 && CONSTANT_CLASS_P (max));
239 /* VAL is the maximum or minimum value of a type. Return a
240 corresponding overflow infinity. */
243 make_overflow_infinity (tree val)
245 gcc_checking_assert (val != NULL_TREE && CONSTANT_CLASS_P (val));
246 val = copy_node (val);
247 TREE_OVERFLOW (val) = 1;
251 /* Return a negative overflow infinity for TYPE. */
254 negative_overflow_infinity (tree type)
256 gcc_checking_assert (supports_overflow_infinity (type));
257 return make_overflow_infinity (vrp_val_min (type));
260 /* Return a positive overflow infinity for TYPE. */
263 positive_overflow_infinity (tree type)
265 gcc_checking_assert (supports_overflow_infinity (type));
266 return make_overflow_infinity (vrp_val_max (type));
269 /* Return whether VAL is a negative overflow infinity. */
272 is_negative_overflow_infinity (const_tree val)
274 return (needs_overflow_infinity (TREE_TYPE (val))
275 && CONSTANT_CLASS_P (val)
276 && TREE_OVERFLOW (val)
277 && vrp_val_is_min (val));
280 /* Return whether VAL is a positive overflow infinity. */
283 is_positive_overflow_infinity (const_tree val)
285 return (needs_overflow_infinity (TREE_TYPE (val))
286 && CONSTANT_CLASS_P (val)
287 && TREE_OVERFLOW (val)
288 && vrp_val_is_max (val));
291 /* Return whether VAL is a positive or negative overflow infinity. */
294 is_overflow_infinity (const_tree val)
296 return (needs_overflow_infinity (TREE_TYPE (val))
297 && CONSTANT_CLASS_P (val)
298 && TREE_OVERFLOW (val)
299 && (vrp_val_is_min (val) || vrp_val_is_max (val)));
302 /* Return whether STMT has a constant rhs that is_overflow_infinity. */
305 stmt_overflow_infinity (gimple stmt)
307 if (is_gimple_assign (stmt)
308 && get_gimple_rhs_class (gimple_assign_rhs_code (stmt)) ==
310 return is_overflow_infinity (gimple_assign_rhs1 (stmt));
314 /* If VAL is now an overflow infinity, return VAL. Otherwise, return
315 the same value with TREE_OVERFLOW clear. This can be used to avoid
316 confusing a regular value with an overflow value. */
319 avoid_overflow_infinity (tree val)
321 if (!is_overflow_infinity (val))
324 if (vrp_val_is_max (val))
325 return vrp_val_max (TREE_TYPE (val));
328 gcc_checking_assert (vrp_val_is_min (val));
329 return vrp_val_min (TREE_TYPE (val));
334 /* Return true if ARG is marked with the nonnull attribute in the
335 current function signature. */
338 nonnull_arg_p (const_tree arg)
340 tree t, attrs, fntype;
341 unsigned HOST_WIDE_INT arg_num;
343 gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
345 /* The static chain decl is always non null. */
346 if (arg == cfun->static_chain_decl)
349 fntype = TREE_TYPE (current_function_decl);
350 attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
352 /* If "nonnull" wasn't specified, we know nothing about the argument. */
353 if (attrs == NULL_TREE)
356 /* If "nonnull" applies to all the arguments, then ARG is non-null. */
357 if (TREE_VALUE (attrs) == NULL_TREE)
360 /* Get the position number for ARG in the function signature. */
361 for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
363 t = DECL_CHAIN (t), arg_num++)
369 gcc_assert (t == arg);
371 /* Now see if ARG_NUM is mentioned in the nonnull list. */
372 for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
374 if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
382 /* Set value range VR to VR_VARYING. */
385 set_value_range_to_varying (value_range_t *vr)
387 vr->type = VR_VARYING;
388 vr->min = vr->max = NULL_TREE;
390 bitmap_clear (vr->equiv);
394 /* Set value range VR to {T, MIN, MAX, EQUIV}. */
397 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
398 tree max, bitmap equiv)
400 #if defined ENABLE_CHECKING
401 /* Check the validity of the range. */
402 if (t == VR_RANGE || t == VR_ANTI_RANGE)
406 gcc_assert (min && max);
408 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
409 gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max));
411 cmp = compare_values (min, max);
412 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
414 if (needs_overflow_infinity (TREE_TYPE (min)))
415 gcc_assert (!is_overflow_infinity (min)
416 || !is_overflow_infinity (max));
419 if (t == VR_UNDEFINED || t == VR_VARYING)
420 gcc_assert (min == NULL_TREE && max == NULL_TREE);
422 if (t == VR_UNDEFINED || t == VR_VARYING)
423 gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
430 /* Since updating the equivalence set involves deep copying the
431 bitmaps, only do it if absolutely necessary. */
432 if (vr->equiv == NULL
434 vr->equiv = BITMAP_ALLOC (NULL);
436 if (equiv != vr->equiv)
438 if (equiv && !bitmap_empty_p (equiv))
439 bitmap_copy (vr->equiv, equiv);
441 bitmap_clear (vr->equiv);
446 /* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
447 This means adjusting T, MIN and MAX representing the case of a
448 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
449 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
450 In corner cases where MAX+1 or MIN-1 wraps this will fall back
452 This routine exists to ease canonicalization in the case where we
453 extract ranges from var + CST op limit. */
456 set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
457 tree min, tree max, bitmap equiv)
459 /* Nothing to canonicalize for symbolic or unknown or varying ranges. */
461 && t != VR_ANTI_RANGE)
462 || TREE_CODE (min) != INTEGER_CST
463 || TREE_CODE (max) != INTEGER_CST)
465 set_value_range (vr, t, min, max, equiv);
469 /* Wrong order for min and max, to swap them and the VR type we need
471 if (tree_int_cst_lt (max, min))
473 tree one = build_int_cst (TREE_TYPE (min), 1);
474 tree tmp = int_const_binop (PLUS_EXPR, max, one, 0);
475 max = int_const_binop (MINUS_EXPR, min, one, 0);
478 /* There's one corner case, if we had [C+1, C] before we now have
479 that again. But this represents an empty value range, so drop
480 to varying in this case. */
481 if (tree_int_cst_lt (max, min))
483 set_value_range_to_varying (vr);
487 t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
490 /* Anti-ranges that can be represented as ranges should be so. */
491 if (t == VR_ANTI_RANGE)
493 bool is_min = vrp_val_is_min (min);
494 bool is_max = vrp_val_is_max (max);
496 if (is_min && is_max)
498 /* We cannot deal with empty ranges, drop to varying. */
499 set_value_range_to_varying (vr);
503 /* As a special exception preserve non-null ranges. */
504 && !(TYPE_UNSIGNED (TREE_TYPE (min))
505 && integer_zerop (max)))
507 tree one = build_int_cst (TREE_TYPE (max), 1);
508 min = int_const_binop (PLUS_EXPR, max, one, 0);
509 max = vrp_val_max (TREE_TYPE (max));
514 tree one = build_int_cst (TREE_TYPE (min), 1);
515 max = int_const_binop (MINUS_EXPR, min, one, 0);
516 min = vrp_val_min (TREE_TYPE (min));
521 set_value_range (vr, t, min, max, equiv);
524 /* Copy value range FROM into value range TO. */
527 copy_value_range (value_range_t *to, value_range_t *from)
529 set_value_range (to, from->type, from->min, from->max, from->equiv);
532 /* Set value range VR to a single value. This function is only called
533 with values we get from statements, and exists to clear the
534 TREE_OVERFLOW flag so that we don't think we have an overflow
535 infinity when we shouldn't. */
538 set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv)
540 gcc_assert (is_gimple_min_invariant (val));
541 val = avoid_overflow_infinity (val);
542 set_value_range (vr, VR_RANGE, val, val, equiv);
545 /* Set value range VR to a non-negative range of type TYPE.
546 OVERFLOW_INFINITY indicates whether to use an overflow infinity
547 rather than TYPE_MAX_VALUE; this should be true if we determine
548 that the range is nonnegative based on the assumption that signed
549 overflow does not occur. */
552 set_value_range_to_nonnegative (value_range_t *vr, tree type,
553 bool overflow_infinity)
557 if (overflow_infinity && !supports_overflow_infinity (type))
559 set_value_range_to_varying (vr);
563 zero = build_int_cst (type, 0);
564 set_value_range (vr, VR_RANGE, zero,
566 ? positive_overflow_infinity (type)
567 : TYPE_MAX_VALUE (type)),
571 /* Set value range VR to a non-NULL range of type TYPE. */
574 set_value_range_to_nonnull (value_range_t *vr, tree type)
576 tree zero = build_int_cst (type, 0);
577 set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
581 /* Set value range VR to a NULL range of type TYPE. */
584 set_value_range_to_null (value_range_t *vr, tree type)
586 set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
590 /* Set value range VR to a range of a truthvalue of type TYPE. */
593 set_value_range_to_truthvalue (value_range_t *vr, tree type)
595 if (TYPE_PRECISION (type) == 1)
596 set_value_range_to_varying (vr);
598 set_value_range (vr, VR_RANGE,
599 build_int_cst (type, 0), build_int_cst (type, 1),
604 /* Set value range VR to VR_UNDEFINED. */
607 set_value_range_to_undefined (value_range_t *vr)
609 vr->type = VR_UNDEFINED;
610 vr->min = vr->max = NULL_TREE;
612 bitmap_clear (vr->equiv);
616 /* If abs (min) < abs (max), set VR to [-max, max], if
617 abs (min) >= abs (max), set VR to [-min, min]. */
620 abs_extent_range (value_range_t *vr, tree min, tree max)
624 gcc_assert (TREE_CODE (min) == INTEGER_CST);
625 gcc_assert (TREE_CODE (max) == INTEGER_CST);
626 gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min)));
627 gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min)));
628 min = fold_unary (ABS_EXPR, TREE_TYPE (min), min);
629 max = fold_unary (ABS_EXPR, TREE_TYPE (max), max);
630 if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
632 set_value_range_to_varying (vr);
635 cmp = compare_values (min, max);
637 min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max);
638 else if (cmp == 0 || cmp == 1)
641 min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min);
645 set_value_range_to_varying (vr);
648 set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
652 /* Return value range information for VAR.
654 If we have no values ranges recorded (ie, VRP is not running), then
655 return NULL. Otherwise create an empty range if none existed for VAR. */
657 static value_range_t *
658 get_value_range (const_tree var)
662 unsigned ver = SSA_NAME_VERSION (var);
664 /* If we have no recorded ranges, then return NULL. */
672 /* Create a default value range. */
673 vr_value[ver] = vr = XCNEW (value_range_t);
675 /* Defer allocating the equivalence set. */
678 /* If VAR is a default definition, the variable can take any value
680 sym = SSA_NAME_VAR (var);
681 if (SSA_NAME_IS_DEFAULT_DEF (var))
683 /* Try to use the "nonnull" attribute to create ~[0, 0]
684 anti-ranges for pointers. Note that this is only valid with
685 default definitions of PARM_DECLs. */
686 if (TREE_CODE (sym) == PARM_DECL
687 && POINTER_TYPE_P (TREE_TYPE (sym))
688 && nonnull_arg_p (sym))
689 set_value_range_to_nonnull (vr, TREE_TYPE (sym));
691 set_value_range_to_varying (vr);
697 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
700 vrp_operand_equal_p (const_tree val1, const_tree val2)
704 if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
706 if (is_overflow_infinity (val1))
707 return is_overflow_infinity (val2);
711 /* Return true, if the bitmaps B1 and B2 are equal. */
714 vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
717 || ((!b1 || bitmap_empty_p (b1))
718 && (!b2 || bitmap_empty_p (b2)))
720 && bitmap_equal_p (b1, b2)));
723 /* Update the value range and equivalence set for variable VAR to
724 NEW_VR. Return true if NEW_VR is different from VAR's previous
727 NOTE: This function assumes that NEW_VR is a temporary value range
728 object created for the sole purpose of updating VAR's range. The
729 storage used by the equivalence set from NEW_VR will be freed by
730 this function. Do not call update_value_range when NEW_VR
731 is the range object associated with another SSA name. */
734 update_value_range (const_tree var, value_range_t *new_vr)
736 value_range_t *old_vr;
739 /* Update the value range, if necessary. */
740 old_vr = get_value_range (var);
741 is_new = old_vr->type != new_vr->type
742 || !vrp_operand_equal_p (old_vr->min, new_vr->min)
743 || !vrp_operand_equal_p (old_vr->max, new_vr->max)
744 || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
747 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
750 BITMAP_FREE (new_vr->equiv);
756 /* Add VAR and VAR's equivalence set to EQUIV. This is the central
757 point where equivalence processing can be turned on/off. */
760 add_equivalence (bitmap *equiv, const_tree var)
762 unsigned ver = SSA_NAME_VERSION (var);
763 value_range_t *vr = vr_value[ver];
766 *equiv = BITMAP_ALLOC (NULL);
767 bitmap_set_bit (*equiv, ver);
769 bitmap_ior_into (*equiv, vr->equiv);
773 /* Return true if VR is ~[0, 0]. */
776 range_is_nonnull (value_range_t *vr)
778 return vr->type == VR_ANTI_RANGE
779 && integer_zerop (vr->min)
780 && integer_zerop (vr->max);
784 /* Return true if VR is [0, 0]. */
787 range_is_null (value_range_t *vr)
789 return vr->type == VR_RANGE
790 && integer_zerop (vr->min)
791 && integer_zerop (vr->max);
794 /* Return true if max and min of VR are INTEGER_CST. It's not necessary
798 range_int_cst_p (value_range_t *vr)
800 return (vr->type == VR_RANGE
801 && TREE_CODE (vr->max) == INTEGER_CST
802 && TREE_CODE (vr->min) == INTEGER_CST
803 && !TREE_OVERFLOW (vr->max)
804 && !TREE_OVERFLOW (vr->min));
807 /* Return true if VR is a INTEGER_CST singleton. */
810 range_int_cst_singleton_p (value_range_t *vr)
812 return (range_int_cst_p (vr)
813 && tree_int_cst_equal (vr->min, vr->max));
816 /* Return true if value range VR involves at least one symbol. */
819 symbolic_range_p (value_range_t *vr)
821 return (!is_gimple_min_invariant (vr->min)
822 || !is_gimple_min_invariant (vr->max));
825 /* Return true if value range VR uses an overflow infinity. */
828 overflow_infinity_range_p (value_range_t *vr)
830 return (vr->type == VR_RANGE
831 && (is_overflow_infinity (vr->min)
832 || is_overflow_infinity (vr->max)));
835 /* Return false if we can not make a valid comparison based on VR;
836 this will be the case if it uses an overflow infinity and overflow
837 is not undefined (i.e., -fno-strict-overflow is in effect).
838 Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR
839 uses an overflow infinity. */
842 usable_range_p (value_range_t *vr, bool *strict_overflow_p)
844 gcc_assert (vr->type == VR_RANGE);
845 if (is_overflow_infinity (vr->min))
847 *strict_overflow_p = true;
848 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min)))
851 if (is_overflow_infinity (vr->max))
853 *strict_overflow_p = true;
854 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max)))
861 /* Like tree_expr_nonnegative_warnv_p, but this function uses value
862 ranges obtained so far. */
865 vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p)
867 return (tree_expr_nonnegative_warnv_p (expr, strict_overflow_p)
868 || (TREE_CODE (expr) == SSA_NAME
869 && ssa_name_nonnegative_p (expr)));
872 /* Return true if the result of assignment STMT is know to be non-negative.
873 If the return value is based on the assumption that signed overflow is
874 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
875 *STRICT_OVERFLOW_P.*/
878 gimple_assign_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
880 enum tree_code code = gimple_assign_rhs_code (stmt);
881 switch (get_gimple_rhs_class (code))
883 case GIMPLE_UNARY_RHS:
884 return tree_unary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt),
885 gimple_expr_type (stmt),
886 gimple_assign_rhs1 (stmt),
888 case GIMPLE_BINARY_RHS:
889 return tree_binary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt),
890 gimple_expr_type (stmt),
891 gimple_assign_rhs1 (stmt),
892 gimple_assign_rhs2 (stmt),
894 case GIMPLE_TERNARY_RHS:
896 case GIMPLE_SINGLE_RHS:
897 return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt),
899 case GIMPLE_INVALID_RHS:
906 /* Return true if return value of call STMT is know to be non-negative.
907 If the return value is based on the assumption that signed overflow is
908 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
909 *STRICT_OVERFLOW_P.*/
912 gimple_call_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
914 tree arg0 = gimple_call_num_args (stmt) > 0 ?
915 gimple_call_arg (stmt, 0) : NULL_TREE;
916 tree arg1 = gimple_call_num_args (stmt) > 1 ?
917 gimple_call_arg (stmt, 1) : NULL_TREE;
919 return tree_call_nonnegative_warnv_p (gimple_expr_type (stmt),
920 gimple_call_fndecl (stmt),
926 /* Return true if STMT is know to to compute a non-negative value.
927 If the return value is based on the assumption that signed overflow is
928 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
929 *STRICT_OVERFLOW_P.*/
932 gimple_stmt_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
934 switch (gimple_code (stmt))
937 return gimple_assign_nonnegative_warnv_p (stmt, strict_overflow_p);
939 return gimple_call_nonnegative_warnv_p (stmt, strict_overflow_p);
945 /* Return true if the result of assignment STMT is know to be non-zero.
946 If the return value is based on the assumption that signed overflow is
947 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
948 *STRICT_OVERFLOW_P.*/
951 gimple_assign_nonzero_warnv_p (gimple stmt, bool *strict_overflow_p)
953 enum tree_code code = gimple_assign_rhs_code (stmt);
954 switch (get_gimple_rhs_class (code))
956 case GIMPLE_UNARY_RHS:
957 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
958 gimple_expr_type (stmt),
959 gimple_assign_rhs1 (stmt),
961 case GIMPLE_BINARY_RHS:
962 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
963 gimple_expr_type (stmt),
964 gimple_assign_rhs1 (stmt),
965 gimple_assign_rhs2 (stmt),
967 case GIMPLE_TERNARY_RHS:
969 case GIMPLE_SINGLE_RHS:
970 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt),
972 case GIMPLE_INVALID_RHS:
979 /* Return true if STMT is know to to compute a non-zero value.
980 If the return value is based on the assumption that signed overflow is
981 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
982 *STRICT_OVERFLOW_P.*/
985 gimple_stmt_nonzero_warnv_p (gimple stmt, bool *strict_overflow_p)
987 switch (gimple_code (stmt))
990 return gimple_assign_nonzero_warnv_p (stmt, strict_overflow_p);
992 return gimple_alloca_call_p (stmt);
998 /* Like tree_expr_nonzero_warnv_p, but this function uses value ranges
1002 vrp_stmt_computes_nonzero (gimple stmt, bool *strict_overflow_p)
1004 if (gimple_stmt_nonzero_warnv_p (stmt, strict_overflow_p))
1007 /* If we have an expression of the form &X->a, then the expression
1008 is nonnull if X is nonnull. */
1009 if (is_gimple_assign (stmt)
1010 && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
1012 tree expr = gimple_assign_rhs1 (stmt);
1013 tree base = get_base_address (TREE_OPERAND (expr, 0));
1015 if (base != NULL_TREE
1016 && TREE_CODE (base) == MEM_REF
1017 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
1019 value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
1020 if (range_is_nonnull (vr))
1028 /* Returns true if EXPR is a valid value (as expected by compare_values) --
1029 a gimple invariant, or SSA_NAME +- CST. */
1032 valid_value_p (tree expr)
1034 if (TREE_CODE (expr) == SSA_NAME)
1037 if (TREE_CODE (expr) == PLUS_EXPR
1038 || TREE_CODE (expr) == MINUS_EXPR)
1039 return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
1040 && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
1042 return is_gimple_min_invariant (expr);
1048 -2 if those are incomparable. */
1050 operand_less_p (tree val, tree val2)
1052 /* LT is folded faster than GE and others. Inline the common case. */
1053 if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
1055 if (TYPE_UNSIGNED (TREE_TYPE (val)))
1056 return INT_CST_LT_UNSIGNED (val, val2);
1059 if (INT_CST_LT (val, val2))
1067 fold_defer_overflow_warnings ();
1069 tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
1071 fold_undefer_and_ignore_overflow_warnings ();
1074 || TREE_CODE (tcmp) != INTEGER_CST)
1077 if (!integer_zerop (tcmp))
1081 /* val >= val2, not considering overflow infinity. */
1082 if (is_negative_overflow_infinity (val))
1083 return is_negative_overflow_infinity (val2) ? 0 : 1;
1084 else if (is_positive_overflow_infinity (val2))
1085 return is_positive_overflow_infinity (val) ? 0 : 1;
1090 /* Compare two values VAL1 and VAL2. Return
1092 -2 if VAL1 and VAL2 cannot be compared at compile-time,
1095 +1 if VAL1 > VAL2, and
1098 This is similar to tree_int_cst_compare but supports pointer values
1099 and values that cannot be compared at compile time.
1101 If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to
1102 true if the return value is only valid if we assume that signed
1103 overflow is undefined. */
1106 compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p)
1111 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
1113 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
1114 == POINTER_TYPE_P (TREE_TYPE (val2)));
1115 /* Convert the two values into the same type. This is needed because
1116 sizetype causes sign extension even for unsigned types. */
1117 val2 = fold_convert (TREE_TYPE (val1), val2);
1118 STRIP_USELESS_TYPE_CONVERSION (val2);
1120 if ((TREE_CODE (val1) == SSA_NAME
1121 || TREE_CODE (val1) == PLUS_EXPR
1122 || TREE_CODE (val1) == MINUS_EXPR)
1123 && (TREE_CODE (val2) == SSA_NAME
1124 || TREE_CODE (val2) == PLUS_EXPR
1125 || TREE_CODE (val2) == MINUS_EXPR))
1127 tree n1, c1, n2, c2;
1128 enum tree_code code1, code2;
1130 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
1131 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
1132 same name, return -2. */
1133 if (TREE_CODE (val1) == SSA_NAME)
1141 code1 = TREE_CODE (val1);
1142 n1 = TREE_OPERAND (val1, 0);
1143 c1 = TREE_OPERAND (val1, 1);
1144 if (tree_int_cst_sgn (c1) == -1)
1146 if (is_negative_overflow_infinity (c1))
1148 c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
1151 code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
1155 if (TREE_CODE (val2) == SSA_NAME)
1163 code2 = TREE_CODE (val2);
1164 n2 = TREE_OPERAND (val2, 0);
1165 c2 = TREE_OPERAND (val2, 1);
1166 if (tree_int_cst_sgn (c2) == -1)
1168 if (is_negative_overflow_infinity (c2))
1170 c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
1173 code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
1177 /* Both values must use the same name. */
1181 if (code1 == SSA_NAME
1182 && code2 == SSA_NAME)
1186 /* If overflow is defined we cannot simplify more. */
1187 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
1190 if (strict_overflow_p != NULL
1191 && (code1 == SSA_NAME || !TREE_NO_WARNING (val1))
1192 && (code2 == SSA_NAME || !TREE_NO_WARNING (val2)))
1193 *strict_overflow_p = true;
1195 if (code1 == SSA_NAME)
1197 if (code2 == PLUS_EXPR)
1198 /* NAME < NAME + CST */
1200 else if (code2 == MINUS_EXPR)
1201 /* NAME > NAME - CST */
1204 else if (code1 == PLUS_EXPR)
1206 if (code2 == SSA_NAME)
1207 /* NAME + CST > NAME */
1209 else if (code2 == PLUS_EXPR)
1210 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
1211 return compare_values_warnv (c1, c2, strict_overflow_p);
1212 else if (code2 == MINUS_EXPR)
1213 /* NAME + CST1 > NAME - CST2 */
1216 else if (code1 == MINUS_EXPR)
1218 if (code2 == SSA_NAME)
1219 /* NAME - CST < NAME */
1221 else if (code2 == PLUS_EXPR)
1222 /* NAME - CST1 < NAME + CST2 */
1224 else if (code2 == MINUS_EXPR)
1225 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
1226 C1 and C2 are swapped in the call to compare_values. */
1227 return compare_values_warnv (c2, c1, strict_overflow_p);
1233 /* We cannot compare non-constants. */
1234 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
1237 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
1239 /* We cannot compare overflowed values, except for overflow
1241 if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
1243 if (strict_overflow_p != NULL)
1244 *strict_overflow_p = true;
1245 if (is_negative_overflow_infinity (val1))
1246 return is_negative_overflow_infinity (val2) ? 0 : -1;
1247 else if (is_negative_overflow_infinity (val2))
1249 else if (is_positive_overflow_infinity (val1))
1250 return is_positive_overflow_infinity (val2) ? 0 : 1;
1251 else if (is_positive_overflow_infinity (val2))
1256 return tree_int_cst_compare (val1, val2);
1262 /* First see if VAL1 and VAL2 are not the same. */
1263 if (val1 == val2 || operand_equal_p (val1, val2, 0))
1266 /* If VAL1 is a lower address than VAL2, return -1. */
1267 if (operand_less_p (val1, val2) == 1)
1270 /* If VAL1 is a higher address than VAL2, return +1. */
1271 if (operand_less_p (val2, val1) == 1)
1274 /* If VAL1 is different than VAL2, return +2.
1275 For integer constants we either have already returned -1 or 1
1276 or they are equivalent. We still might succeed in proving
1277 something about non-trivial operands. */
1278 if (TREE_CODE (val1) != INTEGER_CST
1279 || TREE_CODE (val2) != INTEGER_CST)
1281 t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
1282 if (t && integer_onep (t))
1290 /* Compare values like compare_values_warnv, but treat comparisons of
1291 nonconstants which rely on undefined overflow as incomparable. */
1294 compare_values (tree val1, tree val2)
1300 ret = compare_values_warnv (val1, val2, &sop);
1302 && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)))
1308 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
1309 0 if VAL is not inside VR,
1310 -2 if we cannot tell either way.
1312 FIXME, the current semantics of this functions are a bit quirky
1313 when taken in the context of VRP. In here we do not care
1314 about VR's type. If VR is the anti-range ~[3, 5] the call
1315 value_inside_range (4, VR) will return 1.
1317 This is counter-intuitive in a strict sense, but the callers
1318 currently expect this. They are calling the function
1319 merely to determine whether VR->MIN <= VAL <= VR->MAX. The
1320 callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
1323 This also applies to value_ranges_intersect_p and
1324 range_includes_zero_p. The semantics of VR_RANGE and
1325 VR_ANTI_RANGE should be encoded here, but that also means
1326 adapting the users of these functions to the new semantics.
1328 Benchmark compile/20001226-1.c compilation time after changing this
1332 value_inside_range (tree val, value_range_t * vr)
1336 cmp1 = operand_less_p (val, vr->min);
1342 cmp2 = operand_less_p (vr->max, val);
1350 /* Return true if value ranges VR0 and VR1 have a non-empty
1353 Benchmark compile/20001226-1.c compilation time after changing this
1358 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
1360 /* The value ranges do not intersect if the maximum of the first range is
1361 less than the minimum of the second range or vice versa.
1362 When those relations are unknown, we can't do any better. */
1363 if (operand_less_p (vr0->max, vr1->min) != 0)
1365 if (operand_less_p (vr1->max, vr0->min) != 0)
1371 /* Return true if VR includes the value zero, false otherwise. FIXME,
1372 currently this will return false for an anti-range like ~[-4, 3].
1373 This will be wrong when the semantics of value_inside_range are
1374 modified (currently the users of this function expect these
1378 range_includes_zero_p (value_range_t *vr)
1382 gcc_assert (vr->type != VR_UNDEFINED
1383 && vr->type != VR_VARYING
1384 && !symbolic_range_p (vr));
1386 zero = build_int_cst (TREE_TYPE (vr->min), 0);
1387 return (value_inside_range (zero, vr) == 1);
1390 /* Return true if T, an SSA_NAME, is known to be nonnegative. Return
1391 false otherwise or if no value range information is available. */
1394 ssa_name_nonnegative_p (const_tree t)
1396 value_range_t *vr = get_value_range (t);
1398 if (INTEGRAL_TYPE_P (t)
1399 && TYPE_UNSIGNED (t))
1405 /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
1406 which would return a useful value should be encoded as a VR_RANGE. */
1407 if (vr->type == VR_RANGE)
1409 int result = compare_values (vr->min, integer_zero_node);
1411 return (result == 0 || result == 1);
1416 /* If OP has a value range with a single constant value return that,
1417 otherwise return NULL_TREE. This returns OP itself if OP is a
1421 op_with_constant_singleton_value_range (tree op)
1425 if (is_gimple_min_invariant (op))
1428 if (TREE_CODE (op) != SSA_NAME)
1431 vr = get_value_range (op);
1432 if (vr->type == VR_RANGE
1433 && operand_equal_p (vr->min, vr->max, 0)
1434 && is_gimple_min_invariant (vr->min))
1441 /* Extract value range information from an ASSERT_EXPR EXPR and store
1445 extract_range_from_assert (value_range_t *vr_p, tree expr)
1447 tree var, cond, limit, min, max, type;
1448 value_range_t *var_vr, *limit_vr;
1449 enum tree_code cond_code;
1451 var = ASSERT_EXPR_VAR (expr);
1452 cond = ASSERT_EXPR_COND (expr);
1454 gcc_assert (COMPARISON_CLASS_P (cond));
1456 /* Find VAR in the ASSERT_EXPR conditional. */
1457 if (var == TREE_OPERAND (cond, 0)
1458 || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
1459 || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
1461 /* If the predicate is of the form VAR COMP LIMIT, then we just
1462 take LIMIT from the RHS and use the same comparison code. */
1463 cond_code = TREE_CODE (cond);
1464 limit = TREE_OPERAND (cond, 1);
1465 cond = TREE_OPERAND (cond, 0);
1469 /* If the predicate is of the form LIMIT COMP VAR, then we need
1470 to flip around the comparison code to create the proper range
1472 cond_code = swap_tree_comparison (TREE_CODE (cond));
1473 limit = TREE_OPERAND (cond, 0);
1474 cond = TREE_OPERAND (cond, 1);
1477 limit = avoid_overflow_infinity (limit);
1479 type = TREE_TYPE (var);
1480 gcc_assert (limit != var);
1482 /* For pointer arithmetic, we only keep track of pointer equality
1484 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
1486 set_value_range_to_varying (vr_p);
1490 /* If LIMIT is another SSA name and LIMIT has a range of its own,
1491 try to use LIMIT's range to avoid creating symbolic ranges
1493 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
1495 /* LIMIT's range is only interesting if it has any useful information. */
1497 && (limit_vr->type == VR_UNDEFINED
1498 || limit_vr->type == VR_VARYING
1499 || symbolic_range_p (limit_vr)))
1502 /* Initially, the new range has the same set of equivalences of
1503 VAR's range. This will be revised before returning the final
1504 value. Since assertions may be chained via mutually exclusive
1505 predicates, we will need to trim the set of equivalences before
1507 gcc_assert (vr_p->equiv == NULL);
1508 add_equivalence (&vr_p->equiv, var);
1510 /* Extract a new range based on the asserted comparison for VAR and
1511 LIMIT's value range. Notice that if LIMIT has an anti-range, we
1512 will only use it for equality comparisons (EQ_EXPR). For any
1513 other kind of assertion, we cannot derive a range from LIMIT's
1514 anti-range that can be used to describe the new range. For
1515 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
1516 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
1517 no single range for x_2 that could describe LE_EXPR, so we might
1518 as well build the range [b_4, +INF] for it.
1519 One special case we handle is extracting a range from a
1520 range test encoded as (unsigned)var + CST <= limit. */
1521 if (TREE_CODE (cond) == NOP_EXPR
1522 || TREE_CODE (cond) == PLUS_EXPR)
1524 if (TREE_CODE (cond) == PLUS_EXPR)
1526 min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)),
1527 TREE_OPERAND (cond, 1));
1528 max = int_const_binop (PLUS_EXPR, limit, min, 0);
1529 cond = TREE_OPERAND (cond, 0);
1533 min = build_int_cst (TREE_TYPE (var), 0);
1537 /* Make sure to not set TREE_OVERFLOW on the final type
1538 conversion. We are willingly interpreting large positive
1539 unsigned values as negative singed values here. */
1540 min = force_fit_type_double (TREE_TYPE (var), tree_to_double_int (min),
1542 max = force_fit_type_double (TREE_TYPE (var), tree_to_double_int (max),
1545 /* We can transform a max, min range to an anti-range or
1546 vice-versa. Use set_and_canonicalize_value_range which does
1548 if (cond_code == LE_EXPR)
1549 set_and_canonicalize_value_range (vr_p, VR_RANGE,
1550 min, max, vr_p->equiv);
1551 else if (cond_code == GT_EXPR)
1552 set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
1553 min, max, vr_p->equiv);
1557 else if (cond_code == EQ_EXPR)
1559 enum value_range_type range_type;
1563 range_type = limit_vr->type;
1564 min = limit_vr->min;
1565 max = limit_vr->max;
1569 range_type = VR_RANGE;
1574 set_value_range (vr_p, range_type, min, max, vr_p->equiv);
1576 /* When asserting the equality VAR == LIMIT and LIMIT is another
1577 SSA name, the new range will also inherit the equivalence set
1579 if (TREE_CODE (limit) == SSA_NAME)
1580 add_equivalence (&vr_p->equiv, limit);
1582 else if (cond_code == NE_EXPR)
1584 /* As described above, when LIMIT's range is an anti-range and
1585 this assertion is an inequality (NE_EXPR), then we cannot
1586 derive anything from the anti-range. For instance, if
1587 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
1588 not imply that VAR's range is [0, 0]. So, in the case of
1589 anti-ranges, we just assert the inequality using LIMIT and
1592 If LIMIT_VR is a range, we can only use it to build a new
1593 anti-range if LIMIT_VR is a single-valued range. For
1594 instance, if LIMIT_VR is [0, 1], the predicate
1595 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
1596 Rather, it means that for value 0 VAR should be ~[0, 0]
1597 and for value 1, VAR should be ~[1, 1]. We cannot
1598 represent these ranges.
1600 The only situation in which we can build a valid
1601 anti-range is when LIMIT_VR is a single-valued range
1602 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
1603 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
1605 && limit_vr->type == VR_RANGE
1606 && compare_values (limit_vr->min, limit_vr->max) == 0)
1608 min = limit_vr->min;
1609 max = limit_vr->max;
1613 /* In any other case, we cannot use LIMIT's range to build a
1614 valid anti-range. */
1618 /* If MIN and MAX cover the whole range for their type, then
1619 just use the original LIMIT. */
1620 if (INTEGRAL_TYPE_P (type)
1621 && vrp_val_is_min (min)
1622 && vrp_val_is_max (max))
1625 set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
1627 else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
1629 min = TYPE_MIN_VALUE (type);
1631 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
1635 /* If LIMIT_VR is of the form [N1, N2], we need to build the
1636 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
1638 max = limit_vr->max;
1641 /* If the maximum value forces us to be out of bounds, simply punt.
1642 It would be pointless to try and do anything more since this
1643 all should be optimized away above us. */
1644 if ((cond_code == LT_EXPR
1645 && compare_values (max, min) == 0)
1646 || (CONSTANT_CLASS_P (max) && TREE_OVERFLOW (max)))
1647 set_value_range_to_varying (vr_p);
1650 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
1651 if (cond_code == LT_EXPR)
1653 tree one = build_int_cst (TREE_TYPE (max), 1);
1654 max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, one);
1656 TREE_NO_WARNING (max) = 1;
1659 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1662 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
1664 max = TYPE_MAX_VALUE (type);
1666 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
1670 /* If LIMIT_VR is of the form [N1, N2], we need to build the
1671 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
1673 min = limit_vr->min;
1676 /* If the minimum value forces us to be out of bounds, simply punt.
1677 It would be pointless to try and do anything more since this
1678 all should be optimized away above us. */
1679 if ((cond_code == GT_EXPR
1680 && compare_values (min, max) == 0)
1681 || (CONSTANT_CLASS_P (min) && TREE_OVERFLOW (min)))
1682 set_value_range_to_varying (vr_p);
1685 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
1686 if (cond_code == GT_EXPR)
1688 tree one = build_int_cst (TREE_TYPE (min), 1);
1689 min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min, one);
1691 TREE_NO_WARNING (min) = 1;
1694 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1700 /* If VAR already had a known range, it may happen that the new
1701 range we have computed and VAR's range are not compatible. For
1705 p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
1707 p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
1709 While the above comes from a faulty program, it will cause an ICE
1710 later because p_8 and p_6 will have incompatible ranges and at
1711 the same time will be considered equivalent. A similar situation
1715 i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
1717 i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
1719 Again i_6 and i_7 will have incompatible ranges. It would be
1720 pointless to try and do anything with i_7's range because
1721 anything dominated by 'if (i_5 < 5)' will be optimized away.
1722 Note, due to the wa in which simulation proceeds, the statement
1723 i_7 = ASSERT_EXPR <...> we would never be visited because the
1724 conditional 'if (i_5 < 5)' always evaluates to false. However,
1725 this extra check does not hurt and may protect against future
1726 changes to VRP that may get into a situation similar to the
1727 NULL pointer dereference example.
1729 Note that these compatibility tests are only needed when dealing
1730 with ranges or a mix of range and anti-range. If VAR_VR and VR_P
1731 are both anti-ranges, they will always be compatible, because two
1732 anti-ranges will always have a non-empty intersection. */
1734 var_vr = get_value_range (var);
1736 /* We may need to make adjustments when VR_P and VAR_VR are numeric
1737 ranges or anti-ranges. */
1738 if (vr_p->type == VR_VARYING
1739 || vr_p->type == VR_UNDEFINED
1740 || var_vr->type == VR_VARYING
1741 || var_vr->type == VR_UNDEFINED
1742 || symbolic_range_p (vr_p)
1743 || symbolic_range_p (var_vr))
1746 if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1748 /* If the two ranges have a non-empty intersection, we can
1749 refine the resulting range. Since the assert expression
1750 creates an equivalency and at the same time it asserts a
1751 predicate, we can take the intersection of the two ranges to
1752 get better precision. */
1753 if (value_ranges_intersect_p (var_vr, vr_p))
1755 /* Use the larger of the two minimums. */
1756 if (compare_values (vr_p->min, var_vr->min) == -1)
1761 /* Use the smaller of the two maximums. */
1762 if (compare_values (vr_p->max, var_vr->max) == 1)
1767 set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1771 /* The two ranges do not intersect, set the new range to
1772 VARYING, because we will not be able to do anything
1773 meaningful with it. */
1774 set_value_range_to_varying (vr_p);
1777 else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1778 || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1780 /* A range and an anti-range will cancel each other only if
1781 their ends are the same. For instance, in the example above,
1782 p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1783 so VR_P should be set to VR_VARYING. */
1784 if (compare_values (var_vr->min, vr_p->min) == 0
1785 && compare_values (var_vr->max, vr_p->max) == 0)
1786 set_value_range_to_varying (vr_p);
1789 tree min, max, anti_min, anti_max, real_min, real_max;
1792 /* We want to compute the logical AND of the two ranges;
1793 there are three cases to consider.
1796 1. The VR_ANTI_RANGE range is completely within the
1797 VR_RANGE and the endpoints of the ranges are
1798 different. In that case the resulting range
1799 should be whichever range is more precise.
1800 Typically that will be the VR_RANGE.
1802 2. The VR_ANTI_RANGE is completely disjoint from
1803 the VR_RANGE. In this case the resulting range
1804 should be the VR_RANGE.
1806 3. There is some overlap between the VR_ANTI_RANGE
1809 3a. If the high limit of the VR_ANTI_RANGE resides
1810 within the VR_RANGE, then the result is a new
1811 VR_RANGE starting at the high limit of the
1812 VR_ANTI_RANGE + 1 and extending to the
1813 high limit of the original VR_RANGE.
1815 3b. If the low limit of the VR_ANTI_RANGE resides
1816 within the VR_RANGE, then the result is a new
1817 VR_RANGE starting at the low limit of the original
1818 VR_RANGE and extending to the low limit of the
1819 VR_ANTI_RANGE - 1. */
1820 if (vr_p->type == VR_ANTI_RANGE)
1822 anti_min = vr_p->min;
1823 anti_max = vr_p->max;
1824 real_min = var_vr->min;
1825 real_max = var_vr->max;
1829 anti_min = var_vr->min;
1830 anti_max = var_vr->max;
1831 real_min = vr_p->min;
1832 real_max = vr_p->max;
1836 /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1837 not including any endpoints. */
1838 if (compare_values (anti_max, real_max) == -1
1839 && compare_values (anti_min, real_min) == 1)
1841 /* If the range is covering the whole valid range of
1842 the type keep the anti-range. */
1843 if (!vrp_val_is_min (real_min)
1844 || !vrp_val_is_max (real_max))
1845 set_value_range (vr_p, VR_RANGE, real_min,
1846 real_max, vr_p->equiv);
1848 /* Case 2, VR_ANTI_RANGE completely disjoint from
1850 else if (compare_values (anti_min, real_max) == 1
1851 || compare_values (anti_max, real_min) == -1)
1853 set_value_range (vr_p, VR_RANGE, real_min,
1854 real_max, vr_p->equiv);
1856 /* Case 3a, the anti-range extends into the low
1857 part of the real range. Thus creating a new
1858 low for the real range. */
1859 else if (((cmp = compare_values (anti_max, real_min)) == 1
1861 && compare_values (anti_max, real_max) == -1)
1863 gcc_assert (!is_positive_overflow_infinity (anti_max));
1864 if (needs_overflow_infinity (TREE_TYPE (anti_max))
1865 && vrp_val_is_max (anti_max))
1867 if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
1869 set_value_range_to_varying (vr_p);
1872 min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
1874 else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
1875 min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1877 build_int_cst (TREE_TYPE (var_vr->min), 1));
1879 min = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
1880 anti_max, size_int (1));
1882 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1884 /* Case 3b, the anti-range extends into the high
1885 part of the real range. Thus creating a new
1886 higher for the real range. */
1887 else if (compare_values (anti_min, real_min) == 1
1888 && ((cmp = compare_values (anti_min, real_max)) == -1
1891 gcc_assert (!is_negative_overflow_infinity (anti_min));
1892 if (needs_overflow_infinity (TREE_TYPE (anti_min))
1893 && vrp_val_is_min (anti_min))
1895 if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
1897 set_value_range_to_varying (vr_p);
1900 max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
1902 else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
1903 max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1905 build_int_cst (TREE_TYPE (var_vr->min), 1));
1907 max = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
1911 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1918 /* Extract range information from SSA name VAR and store it in VR. If
1919 VAR has an interesting range, use it. Otherwise, create the
1920 range [VAR, VAR] and return it. This is useful in situations where
1921 we may have conditionals testing values of VARYING names. For
1928 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1932 extract_range_from_ssa_name (value_range_t *vr, tree var)
1934 value_range_t *var_vr = get_value_range (var);
1936 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1937 copy_value_range (vr, var_vr);
1939 set_value_range (vr, VR_RANGE, var, var, NULL);
1941 add_equivalence (&vr->equiv, var);
1945 /* Wrapper around int_const_binop. If the operation overflows and we
1946 are not using wrapping arithmetic, then adjust the result to be
1947 -INF or +INF depending on CODE, VAL1 and VAL2. This can return
1948 NULL_TREE if we need to use an overflow infinity representation but
1949 the type does not support it. */
1952 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1956 res = int_const_binop (code, val1, val2, 0);
1958 /* If we are using unsigned arithmetic, operate symbolically
1959 on -INF and +INF as int_const_binop only handles signed overflow. */
1960 if (TYPE_UNSIGNED (TREE_TYPE (val1)))
1962 int checkz = compare_values (res, val1);
1963 bool overflow = false;
1965 /* Ensure that res = val1 [+*] val2 >= val1
1966 or that res = val1 - val2 <= val1. */
1967 if ((code == PLUS_EXPR
1968 && !(checkz == 1 || checkz == 0))
1969 || (code == MINUS_EXPR
1970 && !(checkz == 0 || checkz == -1)))
1974 /* Checking for multiplication overflow is done by dividing the
1975 output of the multiplication by the first input of the
1976 multiplication. If the result of that division operation is
1977 not equal to the second input of the multiplication, then the
1978 multiplication overflowed. */
1979 else if (code == MULT_EXPR && !integer_zerop (val1))
1981 tree tmp = int_const_binop (TRUNC_DIV_EXPR,
1984 int check = compare_values (tmp, val2);
1992 res = copy_node (res);
1993 TREE_OVERFLOW (res) = 1;
1997 else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
1998 /* If the singed operation wraps then int_const_binop has done
1999 everything we want. */
2001 else if ((TREE_OVERFLOW (res)
2002 && !TREE_OVERFLOW (val1)
2003 && !TREE_OVERFLOW (val2))
2004 || is_overflow_infinity (val1)
2005 || is_overflow_infinity (val2))
2007 /* If the operation overflowed but neither VAL1 nor VAL2 are
2008 overflown, return -INF or +INF depending on the operation
2009 and the combination of signs of the operands. */
2010 int sgn1 = tree_int_cst_sgn (val1);
2011 int sgn2 = tree_int_cst_sgn (val2);
2013 if (needs_overflow_infinity (TREE_TYPE (res))
2014 && !supports_overflow_infinity (TREE_TYPE (res)))
2017 /* We have to punt on adding infinities of different signs,
2018 since we can't tell what the sign of the result should be.
2019 Likewise for subtracting infinities of the same sign. */
2020 if (((code == PLUS_EXPR && sgn1 != sgn2)
2021 || (code == MINUS_EXPR && sgn1 == sgn2))
2022 && is_overflow_infinity (val1)
2023 && is_overflow_infinity (val2))
2026 /* Don't try to handle division or shifting of infinities. */
2027 if ((code == TRUNC_DIV_EXPR
2028 || code == FLOOR_DIV_EXPR
2029 || code == CEIL_DIV_EXPR
2030 || code == EXACT_DIV_EXPR
2031 || code == ROUND_DIV_EXPR
2032 || code == RSHIFT_EXPR)
2033 && (is_overflow_infinity (val1)
2034 || is_overflow_infinity (val2)))
2037 /* Notice that we only need to handle the restricted set of
2038 operations handled by extract_range_from_binary_expr.
2039 Among them, only multiplication, addition and subtraction
2040 can yield overflow without overflown operands because we
2041 are working with integral types only... except in the
2042 case VAL1 = -INF and VAL2 = -1 which overflows to +INF
2043 for division too. */
2045 /* For multiplication, the sign of the overflow is given
2046 by the comparison of the signs of the operands. */
2047 if ((code == MULT_EXPR && sgn1 == sgn2)
2048 /* For addition, the operands must be of the same sign
2049 to yield an overflow. Its sign is therefore that
2050 of one of the operands, for example the first. For
2051 infinite operands X + -INF is negative, not positive. */
2052 || (code == PLUS_EXPR
2054 ? !is_negative_overflow_infinity (val2)
2055 : is_positive_overflow_infinity (val2)))
2056 /* For subtraction, non-infinite operands must be of
2057 different signs to yield an overflow. Its sign is
2058 therefore that of the first operand or the opposite of
2059 that of the second operand. A first operand of 0 counts
2060 as positive here, for the corner case 0 - (-INF), which
2061 overflows, but must yield +INF. For infinite operands 0
2062 - INF is negative, not positive. */
2063 || (code == MINUS_EXPR
2065 ? !is_positive_overflow_infinity (val2)
2066 : is_negative_overflow_infinity (val2)))
2067 /* We only get in here with positive shift count, so the
2068 overflow direction is the same as the sign of val1.
2069 Actually rshift does not overflow at all, but we only
2070 handle the case of shifting overflowed -INF and +INF. */
2071 || (code == RSHIFT_EXPR
2073 /* For division, the only case is -INF / -1 = +INF. */
2074 || code == TRUNC_DIV_EXPR
2075 || code == FLOOR_DIV_EXPR
2076 || code == CEIL_DIV_EXPR
2077 || code == EXACT_DIV_EXPR
2078 || code == ROUND_DIV_EXPR)
2079 return (needs_overflow_infinity (TREE_TYPE (res))
2080 ? positive_overflow_infinity (TREE_TYPE (res))
2081 : TYPE_MAX_VALUE (TREE_TYPE (res)));
2083 return (needs_overflow_infinity (TREE_TYPE (res))
2084 ? negative_overflow_infinity (TREE_TYPE (res))
2085 : TYPE_MIN_VALUE (TREE_TYPE (res)));
2092 /* For range VR compute two double_int bitmasks. In *MAY_BE_NONZERO
2093 bitmask if some bit is unset, it means for all numbers in the range
2094 the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO
2095 bitmask if some bit is set, it means for all numbers in the range
2096 the bit is 1, otherwise it might be 0 or 1. */
2099 zero_nonzero_bits_from_vr (value_range_t *vr, double_int *may_be_nonzero,
2100 double_int *must_be_nonzero)
2102 if (range_int_cst_p (vr))
2104 if (range_int_cst_singleton_p (vr))
2106 *may_be_nonzero = tree_to_double_int (vr->min);
2107 *must_be_nonzero = *may_be_nonzero;
2110 if (tree_int_cst_sgn (vr->min) >= 0)
2112 double_int dmin = tree_to_double_int (vr->min);
2113 double_int dmax = tree_to_double_int (vr->max);
2114 double_int xor_mask = double_int_xor (dmin, dmax);
2115 *may_be_nonzero = double_int_ior (dmin, dmax);
2116 *must_be_nonzero = double_int_and (dmin, dmax);
2117 if (xor_mask.high != 0)
2119 unsigned HOST_WIDE_INT mask
2120 = ((unsigned HOST_WIDE_INT) 1
2121 << floor_log2 (xor_mask.high)) - 1;
2122 may_be_nonzero->low = ALL_ONES;
2123 may_be_nonzero->high |= mask;
2124 must_be_nonzero->low = 0;
2125 must_be_nonzero->high &= ~mask;
2127 else if (xor_mask.low != 0)
2129 unsigned HOST_WIDE_INT mask
2130 = ((unsigned HOST_WIDE_INT) 1
2131 << floor_log2 (xor_mask.low)) - 1;
2132 may_be_nonzero->low |= mask;
2133 must_be_nonzero->low &= ~mask;
2138 may_be_nonzero->low = ALL_ONES;
2139 may_be_nonzero->high = ALL_ONES;
2140 must_be_nonzero->low = 0;
2141 must_be_nonzero->high = 0;
2146 /* Extract range information from a binary expression EXPR based on
2147 the ranges of each of its operands and the expression code. */
2150 extract_range_from_binary_expr (value_range_t *vr,
2151 enum tree_code code,
2152 tree expr_type, tree op0, tree op1)
2154 enum value_range_type type;
2157 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2158 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2160 /* Not all binary expressions can be applied to ranges in a
2161 meaningful way. Handle only arithmetic operations. */
2162 if (code != PLUS_EXPR
2163 && code != MINUS_EXPR
2164 && code != POINTER_PLUS_EXPR
2165 && code != MULT_EXPR
2166 && code != TRUNC_DIV_EXPR
2167 && code != FLOOR_DIV_EXPR
2168 && code != CEIL_DIV_EXPR
2169 && code != EXACT_DIV_EXPR
2170 && code != ROUND_DIV_EXPR
2171 && code != TRUNC_MOD_EXPR
2172 && code != RSHIFT_EXPR
2175 && code != BIT_AND_EXPR
2176 && code != BIT_IOR_EXPR
2177 && code != TRUTH_AND_EXPR
2178 && code != TRUTH_OR_EXPR)
2180 /* We can still do constant propagation here. */
2181 tree const_op0 = op_with_constant_singleton_value_range (op0);
2182 tree const_op1 = op_with_constant_singleton_value_range (op1);
2183 if (const_op0 || const_op1)
2185 tree tem = fold_binary (code, expr_type,
2186 const_op0 ? const_op0 : op0,
2187 const_op1 ? const_op1 : op1);
2189 && is_gimple_min_invariant (tem)
2190 && !is_overflow_infinity (tem))
2192 set_value_range (vr, VR_RANGE, tem, tem, NULL);
2196 set_value_range_to_varying (vr);
2200 /* Get value ranges for each operand. For constant operands, create
2201 a new value range with the operand to simplify processing. */
2202 if (TREE_CODE (op0) == SSA_NAME)
2203 vr0 = *(get_value_range (op0));
2204 else if (is_gimple_min_invariant (op0))
2205 set_value_range_to_value (&vr0, op0, NULL);
2207 set_value_range_to_varying (&vr0);
2209 if (TREE_CODE (op1) == SSA_NAME)
2210 vr1 = *(get_value_range (op1));
2211 else if (is_gimple_min_invariant (op1))
2212 set_value_range_to_value (&vr1, op1, NULL);
2214 set_value_range_to_varying (&vr1);
2216 /* If either range is UNDEFINED, so is the result. */
2217 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
2219 set_value_range_to_undefined (vr);
2223 /* The type of the resulting value range defaults to VR0.TYPE. */
2226 /* Refuse to operate on VARYING ranges, ranges of different kinds
2227 and symbolic ranges. As an exception, we allow BIT_AND_EXPR
2228 because we may be able to derive a useful range even if one of
2229 the operands is VR_VARYING or symbolic range. Similarly for
2230 divisions. TODO, we may be able to derive anti-ranges in
2232 if (code != BIT_AND_EXPR
2233 && code != TRUTH_AND_EXPR
2234 && code != TRUTH_OR_EXPR
2235 && code != TRUNC_DIV_EXPR
2236 && code != FLOOR_DIV_EXPR
2237 && code != CEIL_DIV_EXPR
2238 && code != EXACT_DIV_EXPR
2239 && code != ROUND_DIV_EXPR
2240 && code != TRUNC_MOD_EXPR
2241 && (vr0.type == VR_VARYING
2242 || vr1.type == VR_VARYING
2243 || vr0.type != vr1.type
2244 || symbolic_range_p (&vr0)
2245 || symbolic_range_p (&vr1)))
2247 set_value_range_to_varying (vr);
2251 /* Now evaluate the expression to determine the new range. */
2252 if (POINTER_TYPE_P (expr_type)
2253 || POINTER_TYPE_P (TREE_TYPE (op0))
2254 || POINTER_TYPE_P (TREE_TYPE (op1)))
2256 if (code == MIN_EXPR || code == MAX_EXPR)
2258 /* For MIN/MAX expressions with pointers, we only care about
2259 nullness, if both are non null, then the result is nonnull.
2260 If both are null, then the result is null. Otherwise they
2262 if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
2263 set_value_range_to_nonnull (vr, expr_type);
2264 else if (range_is_null (&vr0) && range_is_null (&vr1))
2265 set_value_range_to_null (vr, expr_type);
2267 set_value_range_to_varying (vr);
2271 if (code == POINTER_PLUS_EXPR)
2273 /* For pointer types, we are really only interested in asserting
2274 whether the expression evaluates to non-NULL. */
2275 if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
2276 set_value_range_to_nonnull (vr, expr_type);
2277 else if (range_is_null (&vr0) && range_is_null (&vr1))
2278 set_value_range_to_null (vr, expr_type);
2280 set_value_range_to_varying (vr);
2282 else if (code == BIT_AND_EXPR)
2284 /* For pointer types, we are really only interested in asserting
2285 whether the expression evaluates to non-NULL. */
2286 if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
2287 set_value_range_to_nonnull (vr, expr_type);
2288 else if (range_is_null (&vr0) || range_is_null (&vr1))
2289 set_value_range_to_null (vr, expr_type);
2291 set_value_range_to_varying (vr);
2299 /* For integer ranges, apply the operation to each end of the
2300 range and see what we end up with. */
2301 if (code == TRUTH_AND_EXPR
2302 || code == TRUTH_OR_EXPR)
2304 /* If one of the operands is zero, we know that the whole
2305 expression evaluates zero. */
2306 if (code == TRUTH_AND_EXPR
2307 && ((vr0.type == VR_RANGE
2308 && integer_zerop (vr0.min)
2309 && integer_zerop (vr0.max))
2310 || (vr1.type == VR_RANGE
2311 && integer_zerop (vr1.min)
2312 && integer_zerop (vr1.max))))
2315 min = max = build_int_cst (expr_type, 0);
2317 /* If one of the operands is one, we know that the whole
2318 expression evaluates one. */
2319 else if (code == TRUTH_OR_EXPR
2320 && ((vr0.type == VR_RANGE
2321 && integer_onep (vr0.min)
2322 && integer_onep (vr0.max))
2323 || (vr1.type == VR_RANGE
2324 && integer_onep (vr1.min)
2325 && integer_onep (vr1.max))))
2328 min = max = build_int_cst (expr_type, 1);
2330 else if (vr0.type != VR_VARYING
2331 && vr1.type != VR_VARYING
2332 && vr0.type == vr1.type
2333 && !symbolic_range_p (&vr0)
2334 && !overflow_infinity_range_p (&vr0)
2335 && !symbolic_range_p (&vr1)
2336 && !overflow_infinity_range_p (&vr1))
2338 /* Boolean expressions cannot be folded with int_const_binop. */
2339 min = fold_binary (code, expr_type, vr0.min, vr1.min);
2340 max = fold_binary (code, expr_type, vr0.max, vr1.max);
2344 /* The result of a TRUTH_*_EXPR is always true or false. */
2345 set_value_range_to_truthvalue (vr, expr_type);
2349 else if (code == PLUS_EXPR
2351 || code == MAX_EXPR)
2353 /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
2354 VR_VARYING. It would take more effort to compute a precise
2355 range for such a case. For example, if we have op0 == 1 and
2356 op1 == -1 with their ranges both being ~[0,0], we would have
2357 op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
2358 Note that we are guaranteed to have vr0.type == vr1.type at
2360 if (vr0.type == VR_ANTI_RANGE)
2362 if (code == PLUS_EXPR)
2364 set_value_range_to_varying (vr);
2367 /* For MIN_EXPR and MAX_EXPR with two VR_ANTI_RANGEs,
2368 the resulting VR_ANTI_RANGE is the same - intersection
2369 of the two ranges. */
2370 min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
2371 max = vrp_int_const_binop (MIN_EXPR, vr0.max, vr1.max);
2375 /* For operations that make the resulting range directly
2376 proportional to the original ranges, apply the operation to
2377 the same end of each range. */
2378 min = vrp_int_const_binop (code, vr0.min, vr1.min);
2379 max = vrp_int_const_binop (code, vr0.max, vr1.max);
2382 /* If both additions overflowed the range kind is still correct.
2383 This happens regularly with subtracting something in unsigned
2385 ??? See PR30318 for all the cases we do not handle. */
2386 if (code == PLUS_EXPR
2387 && (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2388 && (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2390 min = build_int_cst_wide (TREE_TYPE (min),
2391 TREE_INT_CST_LOW (min),
2392 TREE_INT_CST_HIGH (min));
2393 max = build_int_cst_wide (TREE_TYPE (max),
2394 TREE_INT_CST_LOW (max),
2395 TREE_INT_CST_HIGH (max));
2398 else if (code == MULT_EXPR
2399 || code == TRUNC_DIV_EXPR
2400 || code == FLOOR_DIV_EXPR
2401 || code == CEIL_DIV_EXPR
2402 || code == EXACT_DIV_EXPR
2403 || code == ROUND_DIV_EXPR
2404 || code == RSHIFT_EXPR)
2410 /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
2411 drop to VR_VARYING. It would take more effort to compute a
2412 precise range for such a case. For example, if we have
2413 op0 == 65536 and op1 == 65536 with their ranges both being
2414 ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
2415 we cannot claim that the product is in ~[0,0]. Note that we
2416 are guaranteed to have vr0.type == vr1.type at this
2418 if (code == MULT_EXPR
2419 && vr0.type == VR_ANTI_RANGE
2420 && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
2422 set_value_range_to_varying (vr);
2426 /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
2427 then drop to VR_VARYING. Outside of this range we get undefined
2428 behavior from the shift operation. We cannot even trust
2429 SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
2430 shifts, and the operation at the tree level may be widened. */
2431 if (code == RSHIFT_EXPR)
2433 if (vr1.type == VR_ANTI_RANGE
2434 || !vrp_expr_computes_nonnegative (op1, &sop)
2436 (build_int_cst (TREE_TYPE (vr1.max),
2437 TYPE_PRECISION (expr_type) - 1),
2440 set_value_range_to_varying (vr);
2445 else if ((code == TRUNC_DIV_EXPR
2446 || code == FLOOR_DIV_EXPR
2447 || code == CEIL_DIV_EXPR
2448 || code == EXACT_DIV_EXPR
2449 || code == ROUND_DIV_EXPR)
2450 && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
2452 /* For division, if op1 has VR_RANGE but op0 does not, something
2453 can be deduced just from that range. Say [min, max] / [4, max]
2454 gives [min / 4, max / 4] range. */
2455 if (vr1.type == VR_RANGE
2456 && !symbolic_range_p (&vr1)
2457 && !range_includes_zero_p (&vr1))
2459 vr0.type = type = VR_RANGE;
2460 vr0.min = vrp_val_min (TREE_TYPE (op0));
2461 vr0.max = vrp_val_max (TREE_TYPE (op1));
2465 set_value_range_to_varying (vr);
2470 /* For divisions, if flag_non_call_exceptions is true, we must
2471 not eliminate a division by zero. */
2472 if ((code == TRUNC_DIV_EXPR
2473 || code == FLOOR_DIV_EXPR
2474 || code == CEIL_DIV_EXPR
2475 || code == EXACT_DIV_EXPR
2476 || code == ROUND_DIV_EXPR)
2477 && cfun->can_throw_non_call_exceptions
2478 && (vr1.type != VR_RANGE
2479 || symbolic_range_p (&vr1)
2480 || range_includes_zero_p (&vr1)))
2482 set_value_range_to_varying (vr);
2486 /* For divisions, if op0 is VR_RANGE, we can deduce a range
2487 even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
2489 if ((code == TRUNC_DIV_EXPR
2490 || code == FLOOR_DIV_EXPR
2491 || code == CEIL_DIV_EXPR
2492 || code == EXACT_DIV_EXPR
2493 || code == ROUND_DIV_EXPR)
2494 && vr0.type == VR_RANGE
2495 && (vr1.type != VR_RANGE
2496 || symbolic_range_p (&vr1)
2497 || range_includes_zero_p (&vr1)))
2499 tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
2505 if (vrp_expr_computes_nonnegative (op1, &sop) && !sop)
2507 /* For unsigned division or when divisor is known
2508 to be non-negative, the range has to cover
2509 all numbers from 0 to max for positive max
2510 and all numbers from min to 0 for negative min. */
2511 cmp = compare_values (vr0.max, zero);
2514 else if (cmp == 0 || cmp == 1)
2518 cmp = compare_values (vr0.min, zero);
2521 else if (cmp == 0 || cmp == -1)
2528 /* Otherwise the range is -max .. max or min .. -min
2529 depending on which bound is bigger in absolute value,
2530 as the division can change the sign. */
2531 abs_extent_range (vr, vr0.min, vr0.max);
2534 if (type == VR_VARYING)
2536 set_value_range_to_varying (vr);
2541 /* Multiplications and divisions are a bit tricky to handle,
2542 depending on the mix of signs we have in the two ranges, we
2543 need to operate on different values to get the minimum and
2544 maximum values for the new range. One approach is to figure
2545 out all the variations of range combinations and do the
2548 However, this involves several calls to compare_values and it
2549 is pretty convoluted. It's simpler to do the 4 operations
2550 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
2551 MAX1) and then figure the smallest and largest values to form
2555 gcc_assert ((vr0.type == VR_RANGE
2556 || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
2557 && vr0.type == vr1.type);
2559 /* Compute the 4 cross operations. */
2561 val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
2562 if (val[0] == NULL_TREE)
2565 if (vr1.max == vr1.min)
2569 val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
2570 if (val[1] == NULL_TREE)
2574 if (vr0.max == vr0.min)
2578 val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
2579 if (val[2] == NULL_TREE)
2583 if (vr0.min == vr0.max || vr1.min == vr1.max)
2587 val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
2588 if (val[3] == NULL_TREE)
2594 set_value_range_to_varying (vr);
2598 /* Set MIN to the minimum of VAL[i] and MAX to the maximum
2602 for (i = 1; i < 4; i++)
2604 if (!is_gimple_min_invariant (min)
2605 || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2606 || !is_gimple_min_invariant (max)
2607 || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2612 if (!is_gimple_min_invariant (val[i])
2613 || (TREE_OVERFLOW (val[i])
2614 && !is_overflow_infinity (val[i])))
2616 /* If we found an overflowed value, set MIN and MAX
2617 to it so that we set the resulting range to
2623 if (compare_values (val[i], min) == -1)
2626 if (compare_values (val[i], max) == 1)
2632 else if (code == TRUNC_MOD_EXPR)
2635 if (vr1.type != VR_RANGE
2636 || symbolic_range_p (&vr1)
2637 || range_includes_zero_p (&vr1)
2638 || vrp_val_is_min (vr1.min))
2640 set_value_range_to_varying (vr);
2644 /* Compute MAX <|vr1.min|, |vr1.max|> - 1. */
2645 max = fold_unary_to_constant (ABS_EXPR, TREE_TYPE (vr1.min), vr1.min);
2646 if (tree_int_cst_lt (max, vr1.max))
2648 max = int_const_binop (MINUS_EXPR, max, integer_one_node, 0);
2649 /* If the dividend is non-negative the modulus will be
2650 non-negative as well. */
2651 if (TYPE_UNSIGNED (TREE_TYPE (max))
2652 || (vrp_expr_computes_nonnegative (op0, &sop) && !sop))
2653 min = build_int_cst (TREE_TYPE (max), 0);
2655 min = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (max), max);
2657 else if (code == MINUS_EXPR)
2659 /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
2660 VR_VARYING. It would take more effort to compute a precise
2661 range for such a case. For example, if we have op0 == 1 and
2662 op1 == 1 with their ranges both being ~[0,0], we would have
2663 op0 - op1 == 0, so we cannot claim that the difference is in
2664 ~[0,0]. Note that we are guaranteed to have
2665 vr0.type == vr1.type at this point. */
2666 if (vr0.type == VR_ANTI_RANGE)
2668 set_value_range_to_varying (vr);
2672 /* For MINUS_EXPR, apply the operation to the opposite ends of
2674 min = vrp_int_const_binop (code, vr0.min, vr1.max);
2675 max = vrp_int_const_binop (code, vr0.max, vr1.min);
2677 else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
2679 bool vr0_int_cst_singleton_p, vr1_int_cst_singleton_p;
2680 bool int_cst_range0, int_cst_range1;
2681 double_int may_be_nonzero0, may_be_nonzero1;
2682 double_int must_be_nonzero0, must_be_nonzero1;
2684 vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
2685 vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
2686 int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0,
2688 int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1,
2692 if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
2693 min = max = int_const_binop (code, vr0.max, vr1.max, 0);
2694 else if (!int_cst_range0 && !int_cst_range1)
2696 set_value_range_to_varying (vr);
2699 else if (code == BIT_AND_EXPR)
2701 min = double_int_to_tree (expr_type,
2702 double_int_and (must_be_nonzero0,
2704 max = double_int_to_tree (expr_type,
2705 double_int_and (may_be_nonzero0,
2707 if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
2709 if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
2711 if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
2713 if (min == NULL_TREE)
2714 min = build_int_cst (expr_type, 0);
2715 if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
2718 if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
2720 if (min == NULL_TREE)
2721 min = build_int_cst (expr_type, 0);
2722 if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
2726 else if (!int_cst_range0
2728 || tree_int_cst_sgn (vr0.min) < 0
2729 || tree_int_cst_sgn (vr1.min) < 0)
2731 set_value_range_to_varying (vr);
2736 min = double_int_to_tree (expr_type,
2737 double_int_ior (must_be_nonzero0,
2739 max = double_int_to_tree (expr_type,
2740 double_int_ior (may_be_nonzero0,
2742 if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
2745 min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
2746 if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
2748 min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
2754 /* If either MIN or MAX overflowed, then set the resulting range to
2755 VARYING. But we do accept an overflow infinity
2757 if (min == NULL_TREE
2758 || !is_gimple_min_invariant (min)
2759 || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2761 || !is_gimple_min_invariant (max)
2762 || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2764 set_value_range_to_varying (vr);
2770 2) [-INF, +-INF(OVF)]
2771 3) [+-INF(OVF), +INF]
2772 4) [+-INF(OVF), +-INF(OVF)]
2773 We learn nothing when we have INF and INF(OVF) on both sides.
2774 Note that we do accept [-INF, -INF] and [+INF, +INF] without
2776 if ((vrp_val_is_min (min) || is_overflow_infinity (min))
2777 && (vrp_val_is_max (max) || is_overflow_infinity (max)))
2779 set_value_range_to_varying (vr);
2783 cmp = compare_values (min, max);
2784 if (cmp == -2 || cmp == 1)
2786 /* If the new range has its limits swapped around (MIN > MAX),
2787 then the operation caused one of them to wrap around, mark
2788 the new range VARYING. */
2789 set_value_range_to_varying (vr);
2792 set_value_range (vr, type, min, max, NULL);
2796 /* Extract range information from a unary expression EXPR based on
2797 the range of its operand and the expression code. */
2800 extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
2801 tree type, tree op0)
2805 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2807 /* Refuse to operate on certain unary expressions for which we
2808 cannot easily determine a resulting range. */
2809 if (code == FIX_TRUNC_EXPR
2810 || code == FLOAT_EXPR
2811 || code == BIT_NOT_EXPR
2812 || code == CONJ_EXPR)
2814 /* We can still do constant propagation here. */
2815 if ((op0 = op_with_constant_singleton_value_range (op0)) != NULL_TREE)
2817 tree tem = fold_unary (code, type, op0);
2819 && is_gimple_min_invariant (tem)
2820 && !is_overflow_infinity (tem))
2822 set_value_range (vr, VR_RANGE, tem, tem, NULL);
2826 set_value_range_to_varying (vr);
2830 /* Get value ranges for the operand. For constant operands, create
2831 a new value range with the operand to simplify processing. */
2832 if (TREE_CODE (op0) == SSA_NAME)
2833 vr0 = *(get_value_range (op0));
2834 else if (is_gimple_min_invariant (op0))
2835 set_value_range_to_value (&vr0, op0, NULL);
2837 set_value_range_to_varying (&vr0);
2839 /* If VR0 is UNDEFINED, so is the result. */
2840 if (vr0.type == VR_UNDEFINED)
2842 set_value_range_to_undefined (vr);
2846 /* Refuse to operate on symbolic ranges, or if neither operand is
2847 a pointer or integral type. */
2848 if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2849 && !POINTER_TYPE_P (TREE_TYPE (op0)))
2850 || (vr0.type != VR_VARYING
2851 && symbolic_range_p (&vr0)))
2853 set_value_range_to_varying (vr);
2857 /* If the expression involves pointers, we are only interested in
2858 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
2859 if (POINTER_TYPE_P (type) || POINTER_TYPE_P (TREE_TYPE (op0)))
2864 if (range_is_nonnull (&vr0)
2865 || (tree_unary_nonzero_warnv_p (code, type, op0, &sop)
2867 set_value_range_to_nonnull (vr, type);
2868 else if (range_is_null (&vr0))
2869 set_value_range_to_null (vr, type);
2871 set_value_range_to_varying (vr);
2876 /* Handle unary expressions on integer ranges. */
2877 if (CONVERT_EXPR_CODE_P (code)
2878 && INTEGRAL_TYPE_P (type)
2879 && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2881 tree inner_type = TREE_TYPE (op0);
2882 tree outer_type = type;
2884 /* If VR0 is varying and we increase the type precision, assume
2885 a full range for the following transformation. */
2886 if (vr0.type == VR_VARYING
2887 && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type))
2889 vr0.type = VR_RANGE;
2890 vr0.min = TYPE_MIN_VALUE (inner_type);
2891 vr0.max = TYPE_MAX_VALUE (inner_type);
2894 /* If VR0 is a constant range or anti-range and the conversion is
2895 not truncating we can convert the min and max values and
2896 canonicalize the resulting range. Otherwise we can do the
2897 conversion if the size of the range is less than what the
2898 precision of the target type can represent and the range is
2899 not an anti-range. */
2900 if ((vr0.type == VR_RANGE
2901 || vr0.type == VR_ANTI_RANGE)
2902 && TREE_CODE (vr0.min) == INTEGER_CST
2903 && TREE_CODE (vr0.max) == INTEGER_CST
2904 && (!is_overflow_infinity (vr0.min)
2905 || (vr0.type == VR_RANGE
2906 && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
2907 && needs_overflow_infinity (outer_type)
2908 && supports_overflow_infinity (outer_type)))
2909 && (!is_overflow_infinity (vr0.max)
2910 || (vr0.type == VR_RANGE
2911 && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
2912 && needs_overflow_infinity (outer_type)
2913 && supports_overflow_infinity (outer_type)))
2914 && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
2915 || (vr0.type == VR_RANGE
2916 && integer_zerop (int_const_binop (RSHIFT_EXPR,
2917 int_const_binop (MINUS_EXPR, vr0.max, vr0.min, 0),
2918 size_int (TYPE_PRECISION (outer_type)), 0)))))
2920 tree new_min, new_max;
2921 new_min = force_fit_type_double (outer_type,
2922 tree_to_double_int (vr0.min),
2924 new_max = force_fit_type_double (outer_type,
2925 tree_to_double_int (vr0.max),
2927 if (is_overflow_infinity (vr0.min))
2928 new_min = negative_overflow_infinity (outer_type);
2929 if (is_overflow_infinity (vr0.max))
2930 new_max = positive_overflow_infinity (outer_type);
2931 set_and_canonicalize_value_range (vr, vr0.type,
2932 new_min, new_max, NULL);
2936 set_value_range_to_varying (vr);
2940 /* Conversion of a VR_VARYING value to a wider type can result
2941 in a usable range. So wait until after we've handled conversions
2942 before dropping the result to VR_VARYING if we had a source
2943 operand that is VR_VARYING. */
2944 if (vr0.type == VR_VARYING)
2946 set_value_range_to_varying (vr);
2950 /* Apply the operation to each end of the range and see what we end
2952 if (code == NEGATE_EXPR
2953 && !TYPE_UNSIGNED (type))
2955 /* NEGATE_EXPR flips the range around. We need to treat
2956 TYPE_MIN_VALUE specially. */
2957 if (is_positive_overflow_infinity (vr0.max))
2958 min = negative_overflow_infinity (type);
2959 else if (is_negative_overflow_infinity (vr0.max))
2960 min = positive_overflow_infinity (type);
2961 else if (!vrp_val_is_min (vr0.max))
2962 min = fold_unary_to_constant (code, type, vr0.max);
2963 else if (needs_overflow_infinity (type))
2965 if (supports_overflow_infinity (type)
2966 && !is_overflow_infinity (vr0.min)
2967 && !vrp_val_is_min (vr0.min))
2968 min = positive_overflow_infinity (type);
2971 set_value_range_to_varying (vr);
2976 min = TYPE_MIN_VALUE (type);
2978 if (is_positive_overflow_infinity (vr0.min))
2979 max = negative_overflow_infinity (type);
2980 else if (is_negative_overflow_infinity (vr0.min))
2981 max = positive_overflow_infinity (type);
2982 else if (!vrp_val_is_min (vr0.min))
2983 max = fold_unary_to_constant (code, type, vr0.min);
2984 else if (needs_overflow_infinity (type))
2986 if (supports_overflow_infinity (type))
2987 max = positive_overflow_infinity (type);
2990 set_value_range_to_varying (vr);
2995 max = TYPE_MIN_VALUE (type);
2997 else if (code == NEGATE_EXPR
2998 && TYPE_UNSIGNED (type))
3000 if (!range_includes_zero_p (&vr0))
3002 max = fold_unary_to_constant (code, type, vr0.min);
3003 min = fold_unary_to_constant (code, type, vr0.max);
3007 if (range_is_null (&vr0))
3008 set_value_range_to_null (vr, type);
3010 set_value_range_to_varying (vr);
3014 else if (code == ABS_EXPR
3015 && !TYPE_UNSIGNED (type))
3017 /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
3019 if (!TYPE_OVERFLOW_UNDEFINED (type)
3020 && ((vr0.type == VR_RANGE
3021 && vrp_val_is_min (vr0.min))
3022 || (vr0.type == VR_ANTI_RANGE
3023 && !vrp_val_is_min (vr0.min)
3024 && !range_includes_zero_p (&vr0))))
3026 set_value_range_to_varying (vr);
3030 /* ABS_EXPR may flip the range around, if the original range
3031 included negative values. */
3032 if (is_overflow_infinity (vr0.min))
3033 min = positive_overflow_infinity (type);
3034 else if (!vrp_val_is_min (vr0.min))
3035 min = fold_unary_to_constant (code, type, vr0.min);
3036 else if (!needs_overflow_infinity (type))
3037 min = TYPE_MAX_VALUE (type);
3038 else if (supports_overflow_infinity (type))
3039 min = positive_overflow_infinity (type);
3042 set_value_range_to_varying (vr);
3046 if (is_overflow_infinity (vr0.max))
3047 max = positive_overflow_infinity (type);
3048 else if (!vrp_val_is_min (vr0.max))
3049 max = fold_unary_to_constant (code, type, vr0.max);
3050 else if (!needs_overflow_infinity (type))
3051 max = TYPE_MAX_VALUE (type);
3052 else if (supports_overflow_infinity (type)
3053 /* We shouldn't generate [+INF, +INF] as set_value_range
3054 doesn't like this and ICEs. */
3055 && !is_positive_overflow_infinity (min))
3056 max = positive_overflow_infinity (type);
3059 set_value_range_to_varying (vr);
3063 cmp = compare_values (min, max);
3065 /* If a VR_ANTI_RANGEs contains zero, then we have
3066 ~[-INF, min(MIN, MAX)]. */
3067 if (vr0.type == VR_ANTI_RANGE)
3069 if (range_includes_zero_p (&vr0))
3071 /* Take the lower of the two values. */
3075 /* Create ~[-INF, min (abs(MIN), abs(MAX))]
3076 or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
3077 flag_wrapv is set and the original anti-range doesn't include
3078 TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */
3079 if (TYPE_OVERFLOW_WRAPS (type))
3081 tree type_min_value = TYPE_MIN_VALUE (type);
3083 min = (vr0.min != type_min_value
3084 ? int_const_binop (PLUS_EXPR, type_min_value,
3085 integer_one_node, 0)
3090 if (overflow_infinity_range_p (&vr0))
3091 min = negative_overflow_infinity (type);
3093 min = TYPE_MIN_VALUE (type);
3098 /* All else has failed, so create the range [0, INF], even for
3099 flag_wrapv since TYPE_MIN_VALUE is in the original
3101 vr0.type = VR_RANGE;
3102 min = build_int_cst (type, 0);
3103 if (needs_overflow_infinity (type))
3105 if (supports_overflow_infinity (type))
3106 max = positive_overflow_infinity (type);
3109 set_value_range_to_varying (vr);
3114 max = TYPE_MAX_VALUE (type);
3118 /* If the range contains zero then we know that the minimum value in the
3119 range will be zero. */
3120 else if (range_includes_zero_p (&vr0))
3124 min = build_int_cst (type, 0);
3128 /* If the range was reversed, swap MIN and MAX. */
3139 /* Otherwise, operate on each end of the range. */
3140 min = fold_unary_to_constant (code, type, vr0.min);
3141 max = fold_unary_to_constant (code, type, vr0.max);
3143 if (needs_overflow_infinity (type))
3145 gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
3147 /* If both sides have overflowed, we don't know
3149 if ((is_overflow_infinity (vr0.min)
3150 || TREE_OVERFLOW (min))
3151 && (is_overflow_infinity (vr0.max)
3152 || TREE_OVERFLOW (max)))
3154 set_value_range_to_varying (vr);
3158 if (is_overflow_infinity (vr0.min))
3160 else if (TREE_OVERFLOW (min))
3162 if (supports_overflow_infinity (type))
3163 min = (tree_int_cst_sgn (min) >= 0
3164 ? positive_overflow_infinity (TREE_TYPE (min))
3165 : negative_overflow_infinity (TREE_TYPE (min)));
3168 set_value_range_to_varying (vr);
3173 if (is_overflow_infinity (vr0.max))
3175 else if (TREE_OVERFLOW (max))
3177 if (supports_overflow_infinity (type))
3178 max = (tree_int_cst_sgn (max) >= 0
3179 ? positive_overflow_infinity (TREE_TYPE (max))
3180 : negative_overflow_infinity (TREE_TYPE (max)));
3183 set_value_range_to_varying (vr);
3190 cmp = compare_values (min, max);
3191 if (cmp == -2 || cmp == 1)
3193 /* If the new range has its limits swapped around (MIN > MAX),
3194 then the operation caused one of them to wrap around, mark
3195 the new range VARYING. */
3196 set_value_range_to_varying (vr);
3199 set_value_range (vr, vr0.type, min, max, NULL);
3203 /* Extract range information from a conditional expression EXPR based on
3204 the ranges of each of its operands and the expression code. */
3207 extract_range_from_cond_expr (value_range_t *vr, tree expr)
3210 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3211 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3213 /* Get value ranges for each operand. For constant operands, create
3214 a new value range with the operand to simplify processing. */
3215 op0 = COND_EXPR_THEN (expr);
3216 if (TREE_CODE (op0) == SSA_NAME)
3217 vr0 = *(get_value_range (op0));
3218 else if (is_gimple_min_invariant (op0))
3219 set_value_range_to_value (&vr0, op0, NULL);
3221 set_value_range_to_varying (&vr0);
3223 op1 = COND_EXPR_ELSE (expr);
3224 if (TREE_CODE (op1) == SSA_NAME)
3225 vr1 = *(get_value_range (op1));
3226 else if (is_gimple_min_invariant (op1))
3227 set_value_range_to_value (&vr1, op1, NULL);
3229 set_value_range_to_varying (&vr1);
3231 /* The resulting value range is the union of the operand ranges */
3232 vrp_meet (&vr0, &vr1);
3233 copy_value_range (vr, &vr0);
3237 /* Extract range information from a comparison expression EXPR based
3238 on the range of its operand and the expression code. */
3241 extract_range_from_comparison (value_range_t *vr, enum tree_code code,
3242 tree type, tree op0, tree op1)
3247 val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
3250 /* A disadvantage of using a special infinity as an overflow
3251 representation is that we lose the ability to record overflow
3252 when we don't have an infinity. So we have to ignore a result
3253 which relies on overflow. */
3255 if (val && !is_overflow_infinity (val) && !sop)
3257 /* Since this expression was found on the RHS of an assignment,
3258 its type may be different from _Bool. Convert VAL to EXPR's
3260 val = fold_convert (type, val);
3261 if (is_gimple_min_invariant (val))
3262 set_value_range_to_value (vr, val, vr->equiv);
3264 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
3267 /* The result of a comparison is always true or false. */
3268 set_value_range_to_truthvalue (vr, type);
3271 /* Try to derive a nonnegative or nonzero range out of STMT relying
3272 primarily on generic routines in fold in conjunction with range data.
3273 Store the result in *VR */
3276 extract_range_basic (value_range_t *vr, gimple stmt)
3279 tree type = gimple_expr_type (stmt);
3281 if (INTEGRAL_TYPE_P (type)
3282 && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
3283 set_value_range_to_nonnegative (vr, type,
3284 sop || stmt_overflow_infinity (stmt));
3285 else if (vrp_stmt_computes_nonzero (stmt, &sop)
3287 set_value_range_to_nonnull (vr, type);
3289 set_value_range_to_varying (vr);
3293 /* Try to compute a useful range out of assignment STMT and store it
3297 extract_range_from_assignment (value_range_t *vr, gimple stmt)
3299 enum tree_code code = gimple_assign_rhs_code (stmt);
3301 if (code == ASSERT_EXPR)
3302 extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
3303 else if (code == SSA_NAME)
3304 extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
3305 else if (TREE_CODE_CLASS (code) == tcc_binary
3306 || code == TRUTH_AND_EXPR
3307 || code == TRUTH_OR_EXPR
3308 || code == TRUTH_XOR_EXPR)
3309 extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
3310 gimple_expr_type (stmt),
3311 gimple_assign_rhs1 (stmt),
3312 gimple_assign_rhs2 (stmt));
3313 else if (TREE_CODE_CLASS (code) == tcc_unary)
3314 extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
3315 gimple_expr_type (stmt),
3316 gimple_assign_rhs1 (stmt));
3317 else if (code == COND_EXPR)
3318 extract_range_from_cond_expr (vr, gimple_assign_rhs1 (stmt));
3319 else if (TREE_CODE_CLASS (code) == tcc_comparison)
3320 extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
3321 gimple_expr_type (stmt),
3322 gimple_assign_rhs1 (stmt),
3323 gimple_assign_rhs2 (stmt));
3324 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
3325 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
3326 set_value_range_to_value (vr, gimple_assign_rhs1 (stmt), NULL);
3328 set_value_range_to_varying (vr);
3330 if (vr->type == VR_VARYING)
3331 extract_range_basic (vr, stmt);
3334 /* Given a range VR, a LOOP and a variable VAR, determine whether it
3335 would be profitable to adjust VR using scalar evolution information
3336 for VAR. If so, update VR with the new limits. */
3339 adjust_range_with_scev (value_range_t *vr, struct loop *loop,
3340 gimple stmt, tree var)
3342 tree init, step, chrec, tmin, tmax, min, max, type, tem;
3343 enum ev_direction dir;
3345 /* TODO. Don't adjust anti-ranges. An anti-range may provide
3346 better opportunities than a regular range, but I'm not sure. */
3347 if (vr->type == VR_ANTI_RANGE)
3350 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
3352 /* Like in PR19590, scev can return a constant function. */
3353 if (is_gimple_min_invariant (chrec))
3355 set_value_range_to_value (vr, chrec, vr->equiv);
3359 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
3362 init = initial_condition_in_loop_num (chrec, loop->num);
3363 tem = op_with_constant_singleton_value_range (init);
3366 step = evolution_part_in_loop_num (chrec, loop->num);
3367 tem = op_with_constant_singleton_value_range (step);
3371 /* If STEP is symbolic, we can't know whether INIT will be the
3372 minimum or maximum value in the range. Also, unless INIT is
3373 a simple expression, compare_values and possibly other functions
3374 in tree-vrp won't be able to handle it. */
3375 if (step == NULL_TREE
3376 || !is_gimple_min_invariant (step)
3377 || !valid_value_p (init))
3380 dir = scev_direction (chrec);
3381 if (/* Do not adjust ranges if we do not know whether the iv increases
3382 or decreases, ... */
3383 dir == EV_DIR_UNKNOWN
3384 /* ... or if it may wrap. */
3385 || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
3389 /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
3390 negative_overflow_infinity and positive_overflow_infinity,
3391 because we have concluded that the loop probably does not
3394 type = TREE_TYPE (var);
3395 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
3396 tmin = lower_bound_in_type (type, type);
3398 tmin = TYPE_MIN_VALUE (type);
3399 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
3400 tmax = upper_bound_in_type (type, type);
3402 tmax = TYPE_MAX_VALUE (type);
3404 /* Try to use estimated number of iterations for the loop to constrain the
3405 final value in the evolution.
3406 We are interested in the number of executions of the latch, while
3407 nb_iterations_upper_bound includes the last execution of the exit test. */
3408 if (TREE_CODE (step) == INTEGER_CST
3409 && loop->any_upper_bound
3410 && !double_int_zero_p (loop->nb_iterations_upper_bound)
3411 && is_gimple_val (init)
3412 && (TREE_CODE (init) != SSA_NAME
3413 || get_value_range (init)->type == VR_RANGE))
3415 value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3417 bool unsigned_p = TYPE_UNSIGNED (TREE_TYPE (step));
3420 dtmp = double_int_mul_with_sign (tree_to_double_int (step),
3422 loop->nb_iterations_upper_bound,
3424 unsigned_p, &overflow);
3425 /* If the multiplication overflowed we can't do a meaningful
3426 adjustment. Likewise if the result doesn't fit in the type
3427 of the induction variable. For a signed type we have to
3428 check whether the result has the expected signedness which
3429 is that of the step as nb_iterations_upper_bound is unsigned. */
3431 && double_int_fits_to_tree_p (TREE_TYPE (init), dtmp)
3433 || ((dtmp.high ^ TREE_INT_CST_HIGH (step)) >= 0)))
3435 tem = double_int_to_tree (TREE_TYPE (init), dtmp);
3436 extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
3437 TREE_TYPE (init), init, tem);
3438 /* Likewise if the addition did. */
3439 if (maxvr.type == VR_RANGE)
3447 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
3452 /* For VARYING or UNDEFINED ranges, just about anything we get
3453 from scalar evolutions should be better. */
3455 if (dir == EV_DIR_DECREASES)
3460 /* If we would create an invalid range, then just assume we
3461 know absolutely nothing. This may be over-conservative,
3462 but it's clearly safe, and should happen only in unreachable
3463 parts of code, or for invalid programs. */
3464 if (compare_values (min, max) == 1)
3467 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
3469 else if (vr->type == VR_RANGE)
3474 if (dir == EV_DIR_DECREASES)
3476 /* INIT is the maximum value. If INIT is lower than VR->MAX
3477 but no smaller than VR->MIN, set VR->MAX to INIT. */
3478 if (compare_values (init, max) == -1)
3481 /* According to the loop information, the variable does not
3482 overflow. If we think it does, probably because of an
3483 overflow due to arithmetic on a different INF value,
3485 if (is_negative_overflow_infinity (min)
3486 || compare_values (min, tmin) == -1)
3492 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
3493 if (compare_values (init, min) == 1)
3496 if (is_positive_overflow_infinity (max)
3497 || compare_values (tmax, max) == -1)
3501 /* If we just created an invalid range with the minimum
3502 greater than the maximum, we fail conservatively.
3503 This should happen only in unreachable
3504 parts of code, or for invalid programs. */
3505 if (compare_values (min, max) == 1)
3508 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
3512 /* Return true if VAR may overflow at STMT. This checks any available
3513 loop information to see if we can determine that VAR does not
3517 vrp_var_may_overflow (tree var, gimple stmt)
3520 tree chrec, init, step;
3522 if (current_loops == NULL)
3525 l = loop_containing_stmt (stmt);
3530 chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
3531 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
3534 init = initial_condition_in_loop_num (chrec, l->num);
3535 step = evolution_part_in_loop_num (chrec, l->num);
3537 if (step == NULL_TREE
3538 || !is_gimple_min_invariant (step)
3539 || !valid_value_p (init))
3542 /* If we get here, we know something useful about VAR based on the
3543 loop information. If it wraps, it may overflow. */
3545 if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
3549 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
3551 print_generic_expr (dump_file, var, 0);
3552 fprintf (dump_file, ": loop information indicates does not overflow\n");
3559 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
3561 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
3562 all the values in the ranges.
3564 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
3566 - Return NULL_TREE if it is not always possible to determine the
3567 value of the comparison.
3569 Also set *STRICT_OVERFLOW_P to indicate whether a range with an
3570 overflow infinity was used in the test. */
3574 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1,
3575 bool *strict_overflow_p)
3577 /* VARYING or UNDEFINED ranges cannot be compared. */
3578 if (vr0->type == VR_VARYING
3579 || vr0->type == VR_UNDEFINED
3580 || vr1->type == VR_VARYING
3581 || vr1->type == VR_UNDEFINED)
3584 /* Anti-ranges need to be handled separately. */
3585 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3587 /* If both are anti-ranges, then we cannot compute any
3589 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3592 /* These comparisons are never statically computable. */
3599 /* Equality can be computed only between a range and an
3600 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
3601 if (vr0->type == VR_RANGE)
3603 /* To simplify processing, make VR0 the anti-range. */
3604 value_range_t *tmp = vr0;
3609 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
3611 if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
3612 && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
3613 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3618 if (!usable_range_p (vr0, strict_overflow_p)
3619 || !usable_range_p (vr1, strict_overflow_p))
3622 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
3623 operands around and change the comparison code. */
3624 if (comp == GT_EXPR || comp == GE_EXPR)
3627 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
3633 if (comp == EQ_EXPR)
3635 /* Equality may only be computed if both ranges represent
3636 exactly one value. */
3637 if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
3638 && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
3640 int cmp_min = compare_values_warnv (vr0->min, vr1->min,
3642 int cmp_max = compare_values_warnv (vr0->max, vr1->max,
3644 if (cmp_min == 0 && cmp_max == 0)
3645 return boolean_true_node;
3646 else if (cmp_min != -2 && cmp_max != -2)
3647 return boolean_false_node;
3649 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
3650 else if (compare_values_warnv (vr0->min, vr1->max,
3651 strict_overflow_p) == 1
3652 || compare_values_warnv (vr1->min, vr0->max,
3653 strict_overflow_p) == 1)
3654 return boolean_false_node;
3658 else if (comp == NE_EXPR)
3662 /* If VR0 is completely to the left or completely to the right
3663 of VR1, they are always different. Notice that we need to
3664 make sure that both comparisons yield similar results to
3665 avoid comparing values that cannot be compared at
3667 cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
3668 cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
3669 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
3670 return boolean_true_node;
3672 /* If VR0 and VR1 represent a single value and are identical,
3674 else if (compare_values_warnv (vr0->min, vr0->max,
3675 strict_overflow_p) == 0
3676 && compare_values_warnv (vr1->min, vr1->max,
3677 strict_overflow_p) == 0
3678 && compare_values_warnv (vr0->min, vr1->min,
3679 strict_overflow_p) == 0
3680 && compare_values_warnv (vr0->max, vr1->max,
3681 strict_overflow_p) == 0)
3682 return boolean_false_node;
3684 /* Otherwise, they may or may not be different. */
3688 else if (comp == LT_EXPR || comp == LE_EXPR)
3692 /* If VR0 is to the left of VR1, return true. */
3693 tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
3694 if ((comp == LT_EXPR && tst == -1)
3695 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
3697 if (overflow_infinity_range_p (vr0)
3698 || overflow_infinity_range_p (vr1))
3699 *strict_overflow_p = true;
3700 return boolean_true_node;
3703 /* If VR0 is to the right of VR1, return false. */
3704 tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
3705 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
3706 || (comp == LE_EXPR && tst == 1))
3708 if (overflow_infinity_range_p (vr0)
3709 || overflow_infinity_range_p (vr1))
3710 *strict_overflow_p = true;
3711 return boolean_false_node;
3714 /* Otherwise, we don't know. */
3722 /* Given a value range VR, a value VAL and a comparison code COMP, return
3723 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
3724 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
3725 always returns false. Return NULL_TREE if it is not always
3726 possible to determine the value of the comparison. Also set
3727 *STRICT_OVERFLOW_P to indicate whether a range with an overflow
3728 infinity was used in the test. */
3731 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val,
3732 bool *strict_overflow_p)
3734 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
3737 /* Anti-ranges need to be handled separately. */
3738 if (vr->type == VR_ANTI_RANGE)
3740 /* For anti-ranges, the only predicates that we can compute at
3741 compile time are equality and inequality. */
3748 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
3749 if (value_inside_range (val, vr) == 1)
3750 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3755 if (!usable_range_p (vr, strict_overflow_p))
3758 if (comp == EQ_EXPR)
3760 /* EQ_EXPR may only be computed if VR represents exactly
3762 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0)
3764 int cmp = compare_values_warnv (vr->min, val, strict_overflow_p);
3766 return boolean_true_node;
3767 else if (cmp == -1 || cmp == 1 || cmp == 2)
3768 return boolean_false_node;
3770 else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1
3771 || compare_values_warnv (vr->max, val, strict_overflow_p) == -1)
3772 return boolean_false_node;
3776 else if (comp == NE_EXPR)
3778 /* If VAL is not inside VR, then they are always different. */
3779 if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1
3780 || compare_values_warnv (vr->min, val, strict_overflow_p) == 1)
3781 return boolean_true_node;
3783 /* If VR represents exactly one value equal to VAL, then return
3785 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0
3786 && compare_values_warnv (vr->min, val, strict_overflow_p) == 0)
3787 return boolean_false_node;
3789 /* Otherwise, they may or may not be different. */
3792 else if (comp == LT_EXPR || comp == LE_EXPR)
3796 /* If VR is to the left of VAL, return true. */
3797 tst = compare_values_warnv (vr->max, val, strict_overflow_p);
3798 if ((comp == LT_EXPR && tst == -1)
3799 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
3801 if (overflow_infinity_range_p (vr))
3802 *strict_overflow_p = true;
3803 return boolean_true_node;
3806 /* If VR is to the right of VAL, return false. */
3807 tst = compare_values_warnv (vr->min, val, strict_overflow_p);
3808 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
3809 || (comp == LE_EXPR && tst == 1))
3811 if (overflow_infinity_range_p (vr))
3812 *strict_overflow_p = true;
3813 return boolean_false_node;
3816 /* Otherwise, we don't know. */
3819 else if (comp == GT_EXPR || comp == GE_EXPR)
3823 /* If VR is to the right of VAL, return true. */
3824 tst = compare_values_warnv (vr->min, val, strict_overflow_p);
3825 if ((comp == GT_EXPR && tst == 1)
3826 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
3828 if (overflow_infinity_range_p (vr))
3829 *strict_overflow_p = true;
3830 return boolean_true_node;
3833 /* If VR is to the left of VAL, return false. */
3834 tst = compare_values_warnv (vr->max, val, strict_overflow_p);
3835 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
3836 || (comp == GE_EXPR && tst == -1))
3838 if (overflow_infinity_range_p (vr))
3839 *strict_overflow_p = true;
3840 return boolean_false_node;
3843 /* Otherwise, we don't know. */
3851 /* Debugging dumps. */
3853 void dump_value_range (FILE *, value_range_t *);
3854 void debug_value_range (value_range_t *);
3855 void dump_all_value_ranges (FILE *);
3856 void debug_all_value_ranges (void);
3857 void dump_vr_equiv (FILE *, bitmap);
3858 void debug_vr_equiv (bitmap);
3861 /* Dump value range VR to FILE. */
3864 dump_value_range (FILE *file, value_range_t *vr)
3867 fprintf (file, "[]");
3868 else if (vr->type == VR_UNDEFINED)
3869 fprintf (file, "UNDEFINED");
3870 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
3872 tree type = TREE_TYPE (vr->min);
3874 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
3876 if (is_negative_overflow_infinity (vr->min))
3877 fprintf (file, "-INF(OVF)");
3878 else if (INTEGRAL_TYPE_P (type)
3879 && !TYPE_UNSIGNED (type)
3880 && vrp_val_is_min (vr->min))
3881 fprintf (file, "-INF");
3883 print_generic_expr (file, vr->min, 0);
3885 fprintf (file, ", ");
3887 if (is_positive_overflow_infinity (vr->max))
3888 fprintf (file, "+INF(OVF)");
3889 else if (INTEGRAL_TYPE_P (type)
3890 && vrp_val_is_max (vr->max))
3891 fprintf (file, "+INF");
3893 print_generic_expr (file, vr->max, 0);
3895 fprintf (file, "]");
3902 fprintf (file, " EQUIVALENCES: { ");
3904 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
3906 print_generic_expr (file, ssa_name (i), 0);
3907 fprintf (file, " ");
3911 fprintf (file, "} (%u elements)", c);
3914 else if (vr->type == VR_VARYING)
3915 fprintf (file, "VARYING");
3917 fprintf (file, "INVALID RANGE");
3921 /* Dump value range VR to stderr. */
3924 debug_value_range (value_range_t *vr)
3926 dump_value_range (stderr, vr);
3927 fprintf (stderr, "\n");
3931 /* Dump value ranges of all SSA_NAMEs to FILE. */
3934 dump_all_value_ranges (FILE *file)
3938 for (i = 0; i < num_ssa_names; i++)
3942 print_generic_expr (file, ssa_name (i), 0);
3943 fprintf (file, ": ");
3944 dump_value_range (file, vr_value[i]);
3945 fprintf (file, "\n");
3949 fprintf (file, "\n");
3953 /* Dump all value ranges to stderr. */
3956 debug_all_value_ranges (void)
3958 dump_all_value_ranges (stderr);
3962 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
3963 create a new SSA name N and return the assertion assignment
3964 'V = ASSERT_EXPR <V, V OP W>'. */
3967 build_assert_expr_for (tree cond, tree v)
3972 gcc_assert (TREE_CODE (v) == SSA_NAME);
3973 n = duplicate_ssa_name (v, NULL);
3975 if (COMPARISON_CLASS_P (cond))
3977 tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
3978 assertion = gimple_build_assign (n, a);
3980 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
3982 /* Given !V, build the assignment N = false. */
3983 tree op0 = TREE_OPERAND (cond, 0);
3984 gcc_assert (op0 == v);
3985 assertion = gimple_build_assign (n, boolean_false_node);
3987 else if (TREE_CODE (cond) == SSA_NAME)
3989 /* Given V, build the assignment N = true. */
3990 gcc_assert (v == cond);
3991 assertion = gimple_build_assign (n, boolean_true_node);
3996 SSA_NAME_DEF_STMT (n) = assertion;
3998 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
3999 operand of the ASSERT_EXPR. Register the new name and the old one
4000 in the replacement table so that we can fix the SSA web after
4001 adding all the ASSERT_EXPRs. */
4002 register_new_name_mapping (n, v);
4008 /* Return false if EXPR is a predicate expression involving floating
4012 fp_predicate (gimple stmt)
4014 GIMPLE_CHECK (stmt, GIMPLE_COND);
4016 return FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)));
4020 /* If the range of values taken by OP can be inferred after STMT executes,
4021 return the comparison code (COMP_CODE_P) and value (VAL_P) that
4022 describes the inferred range. Return true if a range could be
4026 infer_value_range (gimple stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
4029 *comp_code_p = ERROR_MARK;
4031 /* Do not attempt to infer anything in names that flow through
4033 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
4036 /* Similarly, don't infer anything from statements that may throw
4038 if (stmt_could_throw_p (stmt))
4041 /* If STMT is the last statement of a basic block with no
4042 successors, there is no point inferring anything about any of its
4043 operands. We would not be able to find a proper insertion point
4044 for the assertion, anyway. */
4045 if (stmt_ends_bb_p (stmt) && EDGE_COUNT (gimple_bb (stmt)->succs) == 0)
4048 /* We can only assume that a pointer dereference will yield
4049 non-NULL if -fdelete-null-pointer-checks is enabled. */
4050 if (flag_delete_null_pointer_checks
4051 && POINTER_TYPE_P (TREE_TYPE (op))
4052 && gimple_code (stmt) != GIMPLE_ASM)
4054 unsigned num_uses, num_loads, num_stores;
4056 count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
4057 if (num_loads + num_stores > 0)
4059 *val_p = build_int_cst (TREE_TYPE (op), 0);
4060 *comp_code_p = NE_EXPR;
4069 void dump_asserts_for (FILE *, tree);
4070 void debug_asserts_for (tree);
4071 void dump_all_asserts (FILE *);
4072 void debug_all_asserts (void);
4074 /* Dump all the registered assertions for NAME to FILE. */
4077 dump_asserts_for (FILE *file, tree name)
4081 fprintf (file, "Assertions to be inserted for ");
4082 print_generic_expr (file, name, 0);
4083 fprintf (file, "\n");
4085 loc = asserts_for[SSA_NAME_VERSION (name)];
4088 fprintf (file, "\t");
4089 print_gimple_stmt (file, gsi_stmt (loc->si), 0, 0);
4090 fprintf (file, "\n\tBB #%d", loc->bb->index);
4093 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
4094 loc->e->dest->index);
4095 dump_edge_info (file, loc->e, 0);
4097 fprintf (file, "\n\tPREDICATE: ");
4098 print_generic_expr (file, name, 0);
4099 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
4100 print_generic_expr (file, loc->val, 0);
4101 fprintf (file, "\n\n");
4105 fprintf (file, "\n");
4109 /* Dump all the registered assertions for NAME to stderr. */
4112 debug_asserts_for (tree name)
4114 dump_asserts_for (stderr, name);
4118 /* Dump all the registered assertions for all the names to FILE. */
4121 dump_all_asserts (FILE *file)
4126 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
4127 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
4128 dump_asserts_for (file, ssa_name (i));
4129 fprintf (file, "\n");
4133 /* Dump all the registered assertions for all the names to stderr. */
4136 debug_all_asserts (void)
4138 dump_all_asserts (stderr);
4142 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
4143 'EXPR COMP_CODE VAL' at a location that dominates block BB or
4144 E->DEST, then register this location as a possible insertion point
4145 for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
4147 BB, E and SI provide the exact insertion point for the new
4148 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
4149 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
4150 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
4151 must not be NULL. */
4154 register_new_assert_for (tree name, tree expr,
4155 enum tree_code comp_code,
4159 gimple_stmt_iterator si)
4161 assert_locus_t n, loc, last_loc;
4162 basic_block dest_bb;
4164 gcc_checking_assert (bb == NULL || e == NULL);
4167 gcc_checking_assert (gimple_code (gsi_stmt (si)) != GIMPLE_COND
4168 && gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH);
4170 /* Never build an assert comparing against an integer constant with
4171 TREE_OVERFLOW set. This confuses our undefined overflow warning
4173 if (TREE_CODE (val) == INTEGER_CST
4174 && TREE_OVERFLOW (val))
4175 val = build_int_cst_wide (TREE_TYPE (val),
4176 TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val));
4178 /* The new assertion A will be inserted at BB or E. We need to
4179 determine if the new location is dominated by a previously
4180 registered location for A. If we are doing an edge insertion,
4181 assume that A will be inserted at E->DEST. Note that this is not
4184 If E is a critical edge, it will be split. But even if E is
4185 split, the new block will dominate the same set of blocks that
4188 The reverse, however, is not true, blocks dominated by E->DEST
4189 will not be dominated by the new block created to split E. So,
4190 if the insertion location is on a critical edge, we will not use
4191 the new location to move another assertion previously registered
4192 at a block dominated by E->DEST. */
4193 dest_bb = (bb) ? bb : e->dest;
4195 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
4196 VAL at a block dominating DEST_BB, then we don't need to insert a new
4197 one. Similarly, if the same assertion already exists at a block
4198 dominated by DEST_BB and the new location is not on a critical
4199 edge, then update the existing location for the assertion (i.e.,
4200 move the assertion up in the dominance tree).
4202 Note, this is implemented as a simple linked list because there
4203 should not be more than a handful of assertions registered per
4204 name. If this becomes a performance problem, a table hashed by
4205 COMP_CODE and VAL could be implemented. */
4206 loc = asserts_for[SSA_NAME_VERSION (name)];
4210 if (loc->comp_code == comp_code
4212 || operand_equal_p (loc->val, val, 0))
4213 && (loc->expr == expr
4214 || operand_equal_p (loc->expr, expr, 0)))
4216 /* If the assertion NAME COMP_CODE VAL has already been
4217 registered at a basic block that dominates DEST_BB, then
4218 we don't need to insert the same assertion again. Note
4219 that we don't check strict dominance here to avoid
4220 replicating the same assertion inside the same basic
4221 block more than once (e.g., when a pointer is
4222 dereferenced several times inside a block).
4224 An exception to this rule are edge insertions. If the
4225 new assertion is to be inserted on edge E, then it will
4226 dominate all the other insertions that we may want to
4227 insert in DEST_BB. So, if we are doing an edge
4228 insertion, don't do this dominance check. */
4230 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
4233 /* Otherwise, if E is not a critical edge and DEST_BB
4234 dominates the existing location for the assertion, move
4235 the assertion up in the dominance tree by updating its
4236 location information. */
4237 if ((e == NULL || !EDGE_CRITICAL_P (e))
4238 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
4247 /* Update the last node of the list and move to the next one. */
4252 /* If we didn't find an assertion already registered for
4253 NAME COMP_CODE VAL, add a new one at the end of the list of
4254 assertions associated with NAME. */
4255 n = XNEW (struct assert_locus_d);
4259 n->comp_code = comp_code;
4267 asserts_for[SSA_NAME_VERSION (name)] = n;
4269 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
4272 /* (COND_OP0 COND_CODE COND_OP1) is a predicate which uses NAME.
4273 Extract a suitable test code and value and store them into *CODE_P and
4274 *VAL_P so the predicate is normalized to NAME *CODE_P *VAL_P.
4276 If no extraction was possible, return FALSE, otherwise return TRUE.
4278 If INVERT is true, then we invert the result stored into *CODE_P. */
4281 extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
4282 tree cond_op0, tree cond_op1,
4283 bool invert, enum tree_code *code_p,
4286 enum tree_code comp_code;
4289 /* Otherwise, we have a comparison of the form NAME COMP VAL
4290 or VAL COMP NAME. */
4291 if (name == cond_op1)
4293 /* If the predicate is of the form VAL COMP NAME, flip
4294 COMP around because we need to register NAME as the
4295 first operand in the predicate. */
4296 comp_code = swap_tree_comparison (cond_code);
4301 /* The comparison is of the form NAME COMP VAL, so the
4302 comparison code remains unchanged. */
4303 comp_code = cond_code;
4307 /* Invert the comparison code as necessary. */
4309 comp_code = invert_tree_comparison (comp_code, 0);
4311 /* VRP does not handle float types. */
4312 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))
4315 /* Do not register always-false predicates.
4316 FIXME: this works around a limitation in fold() when dealing with
4317 enumerations. Given 'enum { N1, N2 } x;', fold will not
4318 fold 'if (x > N2)' to 'if (0)'. */
4319 if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
4320 && INTEGRAL_TYPE_P (TREE_TYPE (val)))
4322 tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
4323 tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
4325 if (comp_code == GT_EXPR
4327 || compare_values (val, max) == 0))
4330 if (comp_code == LT_EXPR
4332 || compare_values (val, min) == 0))
4335 *code_p = comp_code;
4340 /* Try to register an edge assertion for SSA name NAME on edge E for
4341 the condition COND contributing to the conditional jump pointed to by BSI.
4342 Invert the condition COND if INVERT is true.
4343 Return true if an assertion for NAME could be registered. */
4346 register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
4347 enum tree_code cond_code,
4348 tree cond_op0, tree cond_op1, bool invert)
4351 enum tree_code comp_code;
4352 bool retval = false;
4354 if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
4357 invert, &comp_code, &val))
4360 /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
4361 reachable from E. */
4362 if (live_on_edge (e, name)
4363 && !has_single_use (name))
4365 register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
4369 /* In the case of NAME <= CST and NAME being defined as
4370 NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
4371 and NAME2 <= CST - CST2. We can do the same for NAME > CST.
4372 This catches range and anti-range tests. */
4373 if ((comp_code == LE_EXPR
4374 || comp_code == GT_EXPR)
4375 && TREE_CODE (val) == INTEGER_CST
4376 && TYPE_UNSIGNED (TREE_TYPE (val)))
4378 gimple def_stmt = SSA_NAME_DEF_STMT (name);
4379 tree cst2 = NULL_TREE, name2 = NULL_TREE, name3 = NULL_TREE;
4381 /* Extract CST2 from the (optional) addition. */
4382 if (is_gimple_assign (def_stmt)
4383 && gimple_assign_rhs_code (def_stmt) == PLUS_EXPR)
4385 name2 = gimple_assign_rhs1 (def_stmt);
4386 cst2 = gimple_assign_rhs2 (def_stmt);
4387 if (TREE_CODE (name2) == SSA_NAME
4388 && TREE_CODE (cst2) == INTEGER_CST)
4389 def_stmt = SSA_NAME_DEF_STMT (name2);
4392 /* Extract NAME2 from the (optional) sign-changing cast. */
4393 if (gimple_assign_cast_p (def_stmt))
4395 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
4396 && ! TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))
4397 && (TYPE_PRECISION (gimple_expr_type (def_stmt))
4398 == TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))))
4399 name3 = gimple_assign_rhs1 (def_stmt);
4402 /* If name3 is used later, create an ASSERT_EXPR for it. */
4403 if (name3 != NULL_TREE
4404 && TREE_CODE (name3) == SSA_NAME
4405 && (cst2 == NULL_TREE
4406 || TREE_CODE (cst2) == INTEGER_CST)
4407 && INTEGRAL_TYPE_P (TREE_TYPE (name3))
4408 && live_on_edge (e, name3)
4409 && !has_single_use (name3))
4413 /* Build an expression for the range test. */
4414 tmp = build1 (NOP_EXPR, TREE_TYPE (name), name3);
4415 if (cst2 != NULL_TREE)
4416 tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
4420 fprintf (dump_file, "Adding assert for ");
4421 print_generic_expr (dump_file, name3, 0);
4422 fprintf (dump_file, " from ");
4423 print_generic_expr (dump_file, tmp, 0);
4424 fprintf (dump_file, "\n");
4427 register_new_assert_for (name3, tmp, comp_code, val, NULL, e, bsi);
4432 /* If name2 is used later, create an ASSERT_EXPR for it. */
4433 if (name2 != NULL_TREE
4434 && TREE_CODE (name2) == SSA_NAME
4435 && TREE_CODE (cst2) == INTEGER_CST
4436 && INTEGRAL_TYPE_P (TREE_TYPE (name2))
4437 && live_on_edge (e, name2)
4438 && !has_single_use (name2))
4442 /* Build an expression for the range test. */
4444 if (TREE_TYPE (name) != TREE_TYPE (name2))
4445 tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp);
4446 if (cst2 != NULL_TREE)
4447 tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
4451 fprintf (dump_file, "Adding assert for ");
4452 print_generic_expr (dump_file, name2, 0);
4453 fprintf (dump_file, " from ");
4454 print_generic_expr (dump_file, tmp, 0);
4455 fprintf (dump_file, "\n");
4458 register_new_assert_for (name2, tmp, comp_code, val, NULL, e, bsi);
4467 /* OP is an operand of a truth value expression which is known to have
4468 a particular value. Register any asserts for OP and for any
4469 operands in OP's defining statement.
4471 If CODE is EQ_EXPR, then we want to register OP is zero (false),
4472 if CODE is NE_EXPR, then we want to register OP is nonzero (true). */
4475 register_edge_assert_for_1 (tree op, enum tree_code code,
4476 edge e, gimple_stmt_iterator bsi)
4478 bool retval = false;
4481 enum tree_code rhs_code;
4483 /* We only care about SSA_NAMEs. */
4484 if (TREE_CODE (op) != SSA_NAME)
4487 /* We know that OP will have a zero or nonzero value. If OP is used
4488 more than once go ahead and register an assert for OP.
4490 The FOUND_IN_SUBGRAPH support is not helpful in this situation as
4491 it will always be set for OP (because OP is used in a COND_EXPR in
4493 if (!has_single_use (op))
4495 val = build_int_cst (TREE_TYPE (op), 0);
4496 register_new_assert_for (op, op, code, val, NULL, e, bsi);
4500 /* Now look at how OP is set. If it's set from a comparison,
4501 a truth operation or some bit operations, then we may be able
4502 to register information about the operands of that assignment. */
4503 op_def = SSA_NAME_DEF_STMT (op);
4504 if (gimple_code (op_def) != GIMPLE_ASSIGN)
4507 rhs_code = gimple_assign_rhs_code (op_def);
4509 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
4511 bool invert = (code == EQ_EXPR ? true : false);
4512 tree op0 = gimple_assign_rhs1 (op_def);
4513 tree op1 = gimple_assign_rhs2 (op_def);
4515 if (TREE_CODE (op0) == SSA_NAME)
4516 retval |= register_edge_assert_for_2 (op0, e, bsi, rhs_code, op0, op1,
4518 if (TREE_CODE (op1) == SSA_NAME)
4519 retval |= register_edge_assert_for_2 (op1, e, bsi, rhs_code, op0, op1,
4522 else if ((code == NE_EXPR
4523 && (gimple_assign_rhs_code (op_def) == TRUTH_AND_EXPR
4524 || gimple_assign_rhs_code (op_def) == BIT_AND_EXPR))
4526 && (gimple_assign_rhs_code (op_def) == TRUTH_OR_EXPR
4527 || gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR)))
4529 /* Recurse on each operand. */
4530 retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
4532 retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
4535 else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
4537 /* Recurse, flipping CODE. */
4538 code = invert_tree_comparison (code, false);
4539 retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
4542 else if (gimple_assign_rhs_code (op_def) == SSA_NAME)
4544 /* Recurse through the copy. */
4545 retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
4548 else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def)))
4550 /* Recurse through the type conversion. */
4551 retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
4558 /* Try to register an edge assertion for SSA name NAME on edge E for
4559 the condition COND contributing to the conditional jump pointed to by SI.
4560 Return true if an assertion for NAME could be registered. */
4563 register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si,
4564 enum tree_code cond_code, tree cond_op0,
4568 enum tree_code comp_code;
4569 bool retval = false;
4570 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
4572 /* Do not attempt to infer anything in names that flow through
4574 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
4577 if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
4583 /* Register ASSERT_EXPRs for name. */
4584 retval |= register_edge_assert_for_2 (name, e, si, cond_code, cond_op0,
4585 cond_op1, is_else_edge);
4588 /* If COND is effectively an equality test of an SSA_NAME against
4589 the value zero or one, then we may be able to assert values
4590 for SSA_NAMEs which flow into COND. */
4592 /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
4593 statement of NAME we can assert both operands of the TRUTH_AND_EXPR
4594 have nonzero value. */
4595 if (((comp_code == EQ_EXPR && integer_onep (val))
4596 || (comp_code == NE_EXPR && integer_zerop (val))))
4598 gimple def_stmt = SSA_NAME_DEF_STMT (name);
4600 if (is_gimple_assign (def_stmt)
4601 && (gimple_assign_rhs_code (def_stmt) == TRUTH_AND_EXPR
4602 || gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR))
4604 tree op0 = gimple_assign_rhs1 (def_stmt);
4605 tree op1 = gimple_assign_rhs2 (def_stmt);
4606 retval |= register_edge_assert_for_1 (op0, NE_EXPR, e, si);
4607 retval |= register_edge_assert_for_1 (op1, NE_EXPR, e, si);
4611 /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
4612 statement of NAME we can assert both operands of the TRUTH_OR_EXPR
4614 if (((comp_code == EQ_EXPR && integer_zerop (val))
4615 || (comp_code == NE_EXPR && integer_onep (val))))
4617 gimple def_stmt = SSA_NAME_DEF_STMT (name);
4619 if (is_gimple_assign (def_stmt)
4620 && (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
4621 /* For BIT_IOR_EXPR only if NAME == 0 both operands have
4622 necessarily zero value. */
4623 || (comp_code == EQ_EXPR
4624 && (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR))))
4626 tree op0 = gimple_assign_rhs1 (def_stmt);
4627 tree op1 = gimple_assign_rhs2 (def_stmt);
4628 retval |= register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
4629 retval |= register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
4637 /* Determine whether the outgoing edges of BB should receive an
4638 ASSERT_EXPR for each of the operands of BB's LAST statement.
4639 The last statement of BB must be a COND_EXPR.
4641 If any of the sub-graphs rooted at BB have an interesting use of
4642 the predicate operands, an assert location node is added to the
4643 list of assertions for the corresponding operands. */
4646 find_conditional_asserts (basic_block bb, gimple last)
4649 gimple_stmt_iterator bsi;
4655 need_assert = false;
4656 bsi = gsi_for_stmt (last);
4658 /* Look for uses of the operands in each of the sub-graphs
4659 rooted at BB. We need to check each of the outgoing edges
4660 separately, so that we know what kind of ASSERT_EXPR to
4662 FOR_EACH_EDGE (e, ei, bb->succs)
4667 /* Register the necessary assertions for each operand in the
4668 conditional predicate. */
4669 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
4671 need_assert |= register_edge_assert_for (op, e, bsi,
4672 gimple_cond_code (last),
4673 gimple_cond_lhs (last),
4674 gimple_cond_rhs (last));
4687 /* Compare two case labels sorting first by the destination bb index
4688 and then by the case value. */
4691 compare_case_labels (const void *p1, const void *p2)
4693 const struct case_info *ci1 = (const struct case_info *) p1;
4694 const struct case_info *ci2 = (const struct case_info *) p2;
4695 int idx1 = ci1->bb->index;
4696 int idx2 = ci2->bb->index;
4700 else if (idx1 == idx2)
4702 /* Make sure the default label is first in a group. */
4703 if (!CASE_LOW (ci1->expr))
4705 else if (!CASE_LOW (ci2->expr))
4708 return tree_int_cst_compare (CASE_LOW (ci1->expr),
4709 CASE_LOW (ci2->expr));
4715 /* Determine whether the outgoing edges of BB should receive an
4716 ASSERT_EXPR for each of the operands of BB's LAST statement.
4717 The last statement of BB must be a SWITCH_EXPR.
4719 If any of the sub-graphs rooted at BB have an interesting use of
4720 the predicate operands, an assert location node is added to the
4721 list of assertions for the corresponding operands. */
4724 find_switch_asserts (basic_block bb, gimple last)
4727 gimple_stmt_iterator bsi;
4730 struct case_info *ci;
4731 size_t n = gimple_switch_num_labels (last);
4732 #if GCC_VERSION >= 4000
4735 /* Work around GCC 3.4 bug (PR 37086). */
4736 volatile unsigned int idx;
4739 need_assert = false;
4740 bsi = gsi_for_stmt (last);
4741 op = gimple_switch_index (last);
4742 if (TREE_CODE (op) != SSA_NAME)
4745 /* Build a vector of case labels sorted by destination label. */
4746 ci = XNEWVEC (struct case_info, n);
4747 for (idx = 0; idx < n; ++idx)
4749 ci[idx].expr = gimple_switch_label (last, idx);
4750 ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr));
4752 qsort (ci, n, sizeof (struct case_info), compare_case_labels);
4754 for (idx = 0; idx < n; ++idx)
4757 tree cl = ci[idx].expr;
4758 basic_block cbb = ci[idx].bb;
4760 min = CASE_LOW (cl);
4761 max = CASE_HIGH (cl);
4763 /* If there are multiple case labels with the same destination
4764 we need to combine them to a single value range for the edge. */
4765 if (idx + 1 < n && cbb == ci[idx + 1].bb)
4767 /* Skip labels until the last of the group. */
4770 } while (idx < n && cbb == ci[idx].bb);
4773 /* Pick up the maximum of the case label range. */
4774 if (CASE_HIGH (ci[idx].expr))
4775 max = CASE_HIGH (ci[idx].expr);
4777 max = CASE_LOW (ci[idx].expr);
4780 /* Nothing to do if the range includes the default label until we
4781 can register anti-ranges. */
4782 if (min == NULL_TREE)
4785 /* Find the edge to register the assert expr on. */
4786 e = find_edge (bb, cbb);
4788 /* Register the necessary assertions for the operand in the
4790 need_assert |= register_edge_assert_for (op, e, bsi,
4791 max ? GE_EXPR : EQ_EXPR,
4793 fold_convert (TREE_TYPE (op),
4797 need_assert |= register_edge_assert_for (op, e, bsi, LE_EXPR,
4799 fold_convert (TREE_TYPE (op),
4809 /* Traverse all the statements in block BB looking for statements that
4810 may generate useful assertions for the SSA names in their operand.
4811 If a statement produces a useful assertion A for name N_i, then the
4812 list of assertions already generated for N_i is scanned to
4813 determine if A is actually needed.
4815 If N_i already had the assertion A at a location dominating the
4816 current location, then nothing needs to be done. Otherwise, the
4817 new location for A is recorded instead.
4819 1- For every statement S in BB, all the variables used by S are
4820 added to bitmap FOUND_IN_SUBGRAPH.
4822 2- If statement S uses an operand N in a way that exposes a known
4823 value range for N, then if N was not already generated by an
4824 ASSERT_EXPR, create a new assert location for N. For instance,
4825 if N is a pointer and the statement dereferences it, we can
4826 assume that N is not NULL.
4828 3- COND_EXPRs are a special case of #2. We can derive range
4829 information from the predicate but need to insert different
4830 ASSERT_EXPRs for each of the sub-graphs rooted at the
4831 conditional block. If the last statement of BB is a conditional
4832 expression of the form 'X op Y', then
4834 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
4836 b) If the conditional is the only entry point to the sub-graph
4837 corresponding to the THEN_CLAUSE, recurse into it. On
4838 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
4839 an ASSERT_EXPR is added for the corresponding variable.
4841 c) Repeat step (b) on the ELSE_CLAUSE.
4843 d) Mark X and Y in FOUND_IN_SUBGRAPH.
4852 In this case, an assertion on the THEN clause is useful to
4853 determine that 'a' is always 9 on that edge. However, an assertion
4854 on the ELSE clause would be unnecessary.
4856 4- If BB does not end in a conditional expression, then we recurse
4857 into BB's dominator children.
4859 At the end of the recursive traversal, every SSA name will have a
4860 list of locations where ASSERT_EXPRs should be added. When a new
4861 location for name N is found, it is registered by calling
4862 register_new_assert_for. That function keeps track of all the
4863 registered assertions to prevent adding unnecessary assertions.
4864 For instance, if a pointer P_4 is dereferenced more than once in a
4865 dominator tree, only the location dominating all the dereference of
4866 P_4 will receive an ASSERT_EXPR.
4868 If this function returns true, then it means that there are names
4869 for which we need to generate ASSERT_EXPRs. Those assertions are
4870 inserted by process_assert_insertions. */
4873 find_assert_locations_1 (basic_block bb, sbitmap live)
4875 gimple_stmt_iterator si;
4880 need_assert = false;
4881 last = last_stmt (bb);
4883 /* If BB's last statement is a conditional statement involving integer
4884 operands, determine if we need to add ASSERT_EXPRs. */
4886 && gimple_code (last) == GIMPLE_COND
4887 && !fp_predicate (last)
4888 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
4889 need_assert |= find_conditional_asserts (bb, last);
4891 /* If BB's last statement is a switch statement involving integer
4892 operands, determine if we need to add ASSERT_EXPRs. */
4894 && gimple_code (last) == GIMPLE_SWITCH
4895 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
4896 need_assert |= find_switch_asserts (bb, last);
4898 /* Traverse all the statements in BB marking used names and looking
4899 for statements that may infer assertions for their used operands. */
4900 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
4906 stmt = gsi_stmt (si);
4908 if (is_gimple_debug (stmt))
4911 /* See if we can derive an assertion for any of STMT's operands. */
4912 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
4915 enum tree_code comp_code;
4917 /* Mark OP in our live bitmap. */
4918 SET_BIT (live, SSA_NAME_VERSION (op));
4920 /* If OP is used in such a way that we can infer a value
4921 range for it, and we don't find a previous assertion for
4922 it, create a new assertion location node for OP. */
4923 if (infer_value_range (stmt, op, &comp_code, &value))
4925 /* If we are able to infer a nonzero value range for OP,
4926 then walk backwards through the use-def chain to see if OP
4927 was set via a typecast.
4929 If so, then we can also infer a nonzero value range
4930 for the operand of the NOP_EXPR. */
4931 if (comp_code == NE_EXPR && integer_zerop (value))
4934 gimple def_stmt = SSA_NAME_DEF_STMT (t);
4936 while (is_gimple_assign (def_stmt)
4937 && gimple_assign_rhs_code (def_stmt) == NOP_EXPR
4939 (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
4941 (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
4943 t = gimple_assign_rhs1 (def_stmt);
4944 def_stmt = SSA_NAME_DEF_STMT (t);
4946 /* Note we want to register the assert for the
4947 operand of the NOP_EXPR after SI, not after the
4949 if (! has_single_use (t))
4951 register_new_assert_for (t, t, comp_code, value,
4958 /* If OP is used only once, namely in this STMT, don't
4959 bother creating an ASSERT_EXPR for it. Such an
4960 ASSERT_EXPR would do nothing but increase compile time. */
4961 if (!has_single_use (op))
4963 register_new_assert_for (op, op, comp_code, value,
4971 /* Traverse all PHI nodes in BB marking used operands. */
4972 for (si = gsi_start_phis (bb); !gsi_end_p(si); gsi_next (&si))
4974 use_operand_p arg_p;
4976 phi = gsi_stmt (si);
4978 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
4980 tree arg = USE_FROM_PTR (arg_p);
4981 if (TREE_CODE (arg) == SSA_NAME)
4982 SET_BIT (live, SSA_NAME_VERSION (arg));
4989 /* Do an RPO walk over the function computing SSA name liveness
4990 on-the-fly and deciding on assert expressions to insert.
4991 Returns true if there are assert expressions to be inserted. */
4994 find_assert_locations (void)
4996 int *rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
4997 int *bb_rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
4998 int *last_rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
5002 live = XCNEWVEC (sbitmap, last_basic_block + NUM_FIXED_BLOCKS);
5003 rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
5004 for (i = 0; i < rpo_cnt; ++i)
5007 need_asserts = false;
5008 for (i = rpo_cnt-1; i >= 0; --i)
5010 basic_block bb = BASIC_BLOCK (rpo[i]);
5016 live[rpo[i]] = sbitmap_alloc (num_ssa_names);
5017 sbitmap_zero (live[rpo[i]]);
5020 /* Process BB and update the live information with uses in
5022 need_asserts |= find_assert_locations_1 (bb, live[rpo[i]]);
5024 /* Merge liveness into the predecessor blocks and free it. */
5025 if (!sbitmap_empty_p (live[rpo[i]]))
5028 FOR_EACH_EDGE (e, ei, bb->preds)
5030 int pred = e->src->index;
5031 if (e->flags & EDGE_DFS_BACK)
5036 live[pred] = sbitmap_alloc (num_ssa_names);
5037 sbitmap_zero (live[pred]);
5039 sbitmap_a_or_b (live[pred], live[pred], live[rpo[i]]);
5041 if (bb_rpo[pred] < pred_rpo)
5042 pred_rpo = bb_rpo[pred];
5045 /* Record the RPO number of the last visited block that needs
5046 live information from this block. */
5047 last_rpo[rpo[i]] = pred_rpo;
5051 sbitmap_free (live[rpo[i]]);
5052 live[rpo[i]] = NULL;
5055 /* We can free all successors live bitmaps if all their
5056 predecessors have been visited already. */
5057 FOR_EACH_EDGE (e, ei, bb->succs)
5058 if (last_rpo[e->dest->index] == i
5059 && live[e->dest->index])
5061 sbitmap_free (live[e->dest->index]);
5062 live[e->dest->index] = NULL;
5067 XDELETEVEC (bb_rpo);
5068 XDELETEVEC (last_rpo);
5069 for (i = 0; i < last_basic_block + NUM_FIXED_BLOCKS; ++i)
5071 sbitmap_free (live[i]);
5074 return need_asserts;
5077 /* Create an ASSERT_EXPR for NAME and insert it in the location
5078 indicated by LOC. Return true if we made any edge insertions. */
5081 process_assert_insertions_for (tree name, assert_locus_t loc)
5083 /* Build the comparison expression NAME_i COMP_CODE VAL. */
5090 /* If we have X <=> X do not insert an assert expr for that. */
5091 if (loc->expr == loc->val)
5094 cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
5095 assert_stmt = build_assert_expr_for (cond, name);
5098 /* We have been asked to insert the assertion on an edge. This
5099 is used only by COND_EXPR and SWITCH_EXPR assertions. */
5100 gcc_checking_assert (gimple_code (gsi_stmt (loc->si)) == GIMPLE_COND
5101 || (gimple_code (gsi_stmt (loc->si))
5104 gsi_insert_on_edge (loc->e, assert_stmt);
5108 /* Otherwise, we can insert right after LOC->SI iff the
5109 statement must not be the last statement in the block. */
5110 stmt = gsi_stmt (loc->si);
5111 if (!stmt_ends_bb_p (stmt))
5113 gsi_insert_after (&loc->si, assert_stmt, GSI_SAME_STMT);
5117 /* If STMT must be the last statement in BB, we can only insert new
5118 assertions on the non-abnormal edge out of BB. Note that since
5119 STMT is not control flow, there may only be one non-abnormal edge
5121 FOR_EACH_EDGE (e, ei, loc->bb->succs)
5122 if (!(e->flags & EDGE_ABNORMAL))
5124 gsi_insert_on_edge (e, assert_stmt);
5132 /* Process all the insertions registered for every name N_i registered
5133 in NEED_ASSERT_FOR. The list of assertions to be inserted are
5134 found in ASSERTS_FOR[i]. */
5137 process_assert_insertions (void)
5141 bool update_edges_p = false;
5142 int num_asserts = 0;
5144 if (dump_file && (dump_flags & TDF_DETAILS))
5145 dump_all_asserts (dump_file);
5147 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
5149 assert_locus_t loc = asserts_for[i];
5154 assert_locus_t next = loc->next;
5155 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
5163 gsi_commit_edge_inserts ();
5165 statistics_counter_event (cfun, "Number of ASSERT_EXPR expressions inserted",
5170 /* Traverse the flowgraph looking for conditional jumps to insert range
5171 expressions. These range expressions are meant to provide information
5172 to optimizations that need to reason in terms of value ranges. They
5173 will not be expanded into RTL. For instance, given:
5182 this pass will transform the code into:
5188 x = ASSERT_EXPR <x, x < y>
5193 y = ASSERT_EXPR <y, x <= y>
5197 The idea is that once copy and constant propagation have run, other
5198 optimizations will be able to determine what ranges of values can 'x'
5199 take in different paths of the code, simply by checking the reaching
5200 definition of 'x'. */
5203 insert_range_assertions (void)
5205 need_assert_for = BITMAP_ALLOC (NULL);
5206 asserts_for = XCNEWVEC (assert_locus_t, num_ssa_names);
5208 calculate_dominance_info (CDI_DOMINATORS);
5210 if (find_assert_locations ())
5212 process_assert_insertions ();
5213 update_ssa (TODO_update_ssa_no_phi);
5216 if (dump_file && (dump_flags & TDF_DETAILS))
5218 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
5219 dump_function_to_file (current_function_decl, dump_file, dump_flags);
5223 BITMAP_FREE (need_assert_for);
5226 /* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible arrays
5227 and "struct" hacks. If VRP can determine that the
5228 array subscript is a constant, check if it is outside valid
5229 range. If the array subscript is a RANGE, warn if it is
5230 non-overlapping with valid range.
5231 IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR. */
5234 check_array_ref (location_t location, tree ref, bool ignore_off_by_one)
5236 value_range_t* vr = NULL;
5237 tree low_sub, up_sub;
5238 tree low_bound, up_bound, up_bound_p1;
5241 if (TREE_NO_WARNING (ref))
5244 low_sub = up_sub = TREE_OPERAND (ref, 1);
5245 up_bound = array_ref_up_bound (ref);
5247 /* Can not check flexible arrays. */
5249 || TREE_CODE (up_bound) != INTEGER_CST)
5252 /* Accesses to trailing arrays via pointers may access storage
5253 beyond the types array bounds. */
5254 base = get_base_address (ref);
5255 if (base && TREE_CODE (base) == MEM_REF)
5257 tree cref, next = NULL_TREE;
5259 if (TREE_CODE (TREE_OPERAND (ref, 0)) != COMPONENT_REF)
5262 cref = TREE_OPERAND (ref, 0);
5263 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (cref, 0))) == RECORD_TYPE)
5264 for (next = DECL_CHAIN (TREE_OPERAND (cref, 1));
5265 next && TREE_CODE (next) != FIELD_DECL;
5266 next = DECL_CHAIN (next))
5269 /* If this is the last field in a struct type or a field in a
5270 union type do not warn. */
5275 low_bound = array_ref_low_bound (ref);
5276 up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound, integer_one_node, 0);
5278 if (TREE_CODE (low_sub) == SSA_NAME)
5280 vr = get_value_range (low_sub);
5281 if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
5283 low_sub = vr->type == VR_RANGE ? vr->max : vr->min;
5284 up_sub = vr->type == VR_RANGE ? vr->min : vr->max;
5288 if (vr && vr->type == VR_ANTI_RANGE)
5290 if (TREE_CODE (up_sub) == INTEGER_CST
5291 && tree_int_cst_lt (up_bound, up_sub)
5292 && TREE_CODE (low_sub) == INTEGER_CST
5293 && tree_int_cst_lt (low_sub, low_bound))
5295 warning_at (location, OPT_Warray_bounds,
5296 "array subscript is outside array bounds");
5297 TREE_NO_WARNING (ref) = 1;
5300 else if (TREE_CODE (up_sub) == INTEGER_CST
5301 && (ignore_off_by_one
5302 ? (tree_int_cst_lt (up_bound, up_sub)
5303 && !tree_int_cst_equal (up_bound_p1, up_sub))
5304 : (tree_int_cst_lt (up_bound, up_sub)
5305 || tree_int_cst_equal (up_bound_p1, up_sub))))
5307 warning_at (location, OPT_Warray_bounds,
5308 "array subscript is above array bounds");
5309 TREE_NO_WARNING (ref) = 1;
5311 else if (TREE_CODE (low_sub) == INTEGER_CST
5312 && tree_int_cst_lt (low_sub, low_bound))
5314 warning_at (location, OPT_Warray_bounds,
5315 "array subscript is below array bounds");
5316 TREE_NO_WARNING (ref) = 1;
5320 /* Searches if the expr T, located at LOCATION computes
5321 address of an ARRAY_REF, and call check_array_ref on it. */
5324 search_for_addr_array (tree t, location_t location)
5326 while (TREE_CODE (t) == SSA_NAME)
5328 gimple g = SSA_NAME_DEF_STMT (t);
5330 if (gimple_code (g) != GIMPLE_ASSIGN)
5333 if (get_gimple_rhs_class (gimple_assign_rhs_code (g))
5334 != GIMPLE_SINGLE_RHS)
5337 t = gimple_assign_rhs1 (g);
5341 /* We are only interested in addresses of ARRAY_REF's. */
5342 if (TREE_CODE (t) != ADDR_EXPR)
5345 /* Check each ARRAY_REFs in the reference chain. */
5348 if (TREE_CODE (t) == ARRAY_REF)
5349 check_array_ref (location, t, true /*ignore_off_by_one*/);
5351 t = TREE_OPERAND (t, 0);
5353 while (handled_component_p (t));
5355 if (TREE_CODE (t) == MEM_REF
5356 && TREE_CODE (TREE_OPERAND (t, 0)) == ADDR_EXPR
5357 && !TREE_NO_WARNING (t))
5359 tree tem = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
5360 tree low_bound, up_bound, el_sz;
5362 if (TREE_CODE (TREE_TYPE (tem)) != ARRAY_TYPE
5363 || TREE_CODE (TREE_TYPE (TREE_TYPE (tem))) == ARRAY_TYPE
5364 || !TYPE_DOMAIN (TREE_TYPE (tem)))
5367 low_bound = TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
5368 up_bound = TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
5369 el_sz = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (tem)));
5371 || TREE_CODE (low_bound) != INTEGER_CST
5373 || TREE_CODE (up_bound) != INTEGER_CST
5375 || TREE_CODE (el_sz) != INTEGER_CST)
5378 idx = mem_ref_offset (t);
5379 idx = double_int_sdiv (idx, tree_to_double_int (el_sz), TRUNC_DIV_EXPR);
5380 if (double_int_scmp (idx, double_int_zero) < 0)
5382 warning_at (location, OPT_Warray_bounds,
5383 "array subscript is below array bounds");
5384 TREE_NO_WARNING (t) = 1;
5386 else if (double_int_scmp (idx,
5389 (tree_to_double_int (up_bound),
5391 (tree_to_double_int (low_bound))),
5392 double_int_one)) > 0)
5394 warning_at (location, OPT_Warray_bounds,
5395 "array subscript is above array bounds");
5396 TREE_NO_WARNING (t) = 1;
5401 /* walk_tree() callback that checks if *TP is
5402 an ARRAY_REF inside an ADDR_EXPR (in which an array
5403 subscript one outside the valid range is allowed). Call
5404 check_array_ref for each ARRAY_REF found. The location is
5408 check_array_bounds (tree *tp, int *walk_subtree, void *data)
5411 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5412 location_t location;
5414 if (EXPR_HAS_LOCATION (t))
5415 location = EXPR_LOCATION (t);
5418 location_t *locp = (location_t *) wi->info;
5422 *walk_subtree = TRUE;
5424 if (TREE_CODE (t) == ARRAY_REF)
5425 check_array_ref (location, t, false /*ignore_off_by_one*/);
5427 if (TREE_CODE (t) == MEM_REF
5428 || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
5429 search_for_addr_array (TREE_OPERAND (t, 0), location);
5431 if (TREE_CODE (t) == ADDR_EXPR)
5432 *walk_subtree = FALSE;
5437 /* Walk over all statements of all reachable BBs and call check_array_bounds
5441 check_all_array_refs (void)
5444 gimple_stmt_iterator si;
5450 bool executable = false;
5452 /* Skip blocks that were found to be unreachable. */
5453 FOR_EACH_EDGE (e, ei, bb->preds)
5454 executable |= !!(e->flags & EDGE_EXECUTABLE);
5458 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5460 gimple stmt = gsi_stmt (si);
5461 struct walk_stmt_info wi;
5462 if (!gimple_has_location (stmt))
5465 if (is_gimple_call (stmt))
5468 size_t n = gimple_call_num_args (stmt);
5469 for (i = 0; i < n; i++)
5471 tree arg = gimple_call_arg (stmt, i);
5472 search_for_addr_array (arg, gimple_location (stmt));
5477 memset (&wi, 0, sizeof (wi));
5478 wi.info = CONST_CAST (void *, (const void *)
5479 gimple_location_ptr (stmt));
5481 walk_gimple_op (gsi_stmt (si),
5489 /* Convert range assertion expressions into the implied copies and
5490 copy propagate away the copies. Doing the trivial copy propagation
5491 here avoids the need to run the full copy propagation pass after
5494 FIXME, this will eventually lead to copy propagation removing the
5495 names that had useful range information attached to them. For
5496 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
5497 then N_i will have the range [3, +INF].
5499 However, by converting the assertion into the implied copy
5500 operation N_i = N_j, we will then copy-propagate N_j into the uses
5501 of N_i and lose the range information. We may want to hold on to
5502 ASSERT_EXPRs a little while longer as the ranges could be used in
5503 things like jump threading.
5505 The problem with keeping ASSERT_EXPRs around is that passes after
5506 VRP need to handle them appropriately.
5508 Another approach would be to make the range information a first
5509 class property of the SSA_NAME so that it can be queried from
5510 any pass. This is made somewhat more complex by the need for
5511 multiple ranges to be associated with one SSA_NAME. */
5514 remove_range_assertions (void)
5517 gimple_stmt_iterator si;
5519 /* Note that the BSI iterator bump happens at the bottom of the
5520 loop and no bump is necessary if we're removing the statement
5521 referenced by the current BSI. */
5523 for (si = gsi_start_bb (bb); !gsi_end_p (si);)
5525 gimple stmt = gsi_stmt (si);
5528 if (is_gimple_assign (stmt)
5529 && gimple_assign_rhs_code (stmt) == ASSERT_EXPR)
5531 tree rhs = gimple_assign_rhs1 (stmt);
5533 tree cond = fold (ASSERT_EXPR_COND (rhs));
5534 use_operand_p use_p;
5535 imm_use_iterator iter;
5537 gcc_assert (cond != boolean_false_node);
5539 /* Propagate the RHS into every use of the LHS. */
5540 var = ASSERT_EXPR_VAR (rhs);
5541 FOR_EACH_IMM_USE_STMT (use_stmt, iter,
5542 gimple_assign_lhs (stmt))
5543 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
5545 SET_USE (use_p, var);
5546 gcc_assert (TREE_CODE (var) == SSA_NAME);
5549 /* And finally, remove the copy, it is not needed. */
5550 gsi_remove (&si, true);
5551 release_defs (stmt);
5559 /* Return true if STMT is interesting for VRP. */
5562 stmt_interesting_for_vrp (gimple stmt)
5564 if (gimple_code (stmt) == GIMPLE_PHI
5565 && is_gimple_reg (gimple_phi_result (stmt))
5566 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_phi_result (stmt)))
5567 || POINTER_TYPE_P (TREE_TYPE (gimple_phi_result (stmt)))))
5569 else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
5571 tree lhs = gimple_get_lhs (stmt);
5573 /* In general, assignments with virtual operands are not useful
5574 for deriving ranges, with the obvious exception of calls to
5575 builtin functions. */
5576 if (lhs && TREE_CODE (lhs) == SSA_NAME
5577 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
5578 || POINTER_TYPE_P (TREE_TYPE (lhs)))
5579 && ((is_gimple_call (stmt)
5580 && gimple_call_fndecl (stmt) != NULL_TREE
5581 && DECL_IS_BUILTIN (gimple_call_fndecl (stmt)))
5582 || !gimple_vuse (stmt)))
5585 else if (gimple_code (stmt) == GIMPLE_COND
5586 || gimple_code (stmt) == GIMPLE_SWITCH)
5593 /* Initialize local data structures for VRP. */
5596 vrp_initialize (void)
5600 vr_value = XCNEWVEC (value_range_t *, num_ssa_names);
5601 vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
5605 gimple_stmt_iterator si;
5607 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5609 gimple phi = gsi_stmt (si);
5610 if (!stmt_interesting_for_vrp (phi))
5612 tree lhs = PHI_RESULT (phi);
5613 set_value_range_to_varying (get_value_range (lhs));
5614 prop_set_simulate_again (phi, false);
5617 prop_set_simulate_again (phi, true);
5620 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5622 gimple stmt = gsi_stmt (si);
5624 /* If the statement is a control insn, then we do not
5625 want to avoid simulating the statement once. Failure
5626 to do so means that those edges will never get added. */
5627 if (stmt_ends_bb_p (stmt))
5628 prop_set_simulate_again (stmt, true);
5629 else if (!stmt_interesting_for_vrp (stmt))
5633 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
5634 set_value_range_to_varying (get_value_range (def));
5635 prop_set_simulate_again (stmt, false);
5638 prop_set_simulate_again (stmt, true);
5644 /* Visit assignment STMT. If it produces an interesting range, record
5645 the SSA name in *OUTPUT_P. */
5647 static enum ssa_prop_result
5648 vrp_visit_assignment_or_call (gimple stmt, tree *output_p)
5652 enum gimple_code code = gimple_code (stmt);
5653 lhs = gimple_get_lhs (stmt);
5655 /* We only keep track of ranges in integral and pointer types. */
5656 if (TREE_CODE (lhs) == SSA_NAME
5657 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
5658 /* It is valid to have NULL MIN/MAX values on a type. See
5659 build_range_type. */
5660 && TYPE_MIN_VALUE (TREE_TYPE (lhs))
5661 && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
5662 || POINTER_TYPE_P (TREE_TYPE (lhs))))
5664 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
5666 if (code == GIMPLE_CALL)
5667 extract_range_basic (&new_vr, stmt);
5669 extract_range_from_assignment (&new_vr, stmt);
5671 if (update_value_range (lhs, &new_vr))
5675 if (dump_file && (dump_flags & TDF_DETAILS))
5677 fprintf (dump_file, "Found new range for ");
5678 print_generic_expr (dump_file, lhs, 0);
5679 fprintf (dump_file, ": ");
5680 dump_value_range (dump_file, &new_vr);
5681 fprintf (dump_file, "\n\n");
5684 if (new_vr.type == VR_VARYING)
5685 return SSA_PROP_VARYING;
5687 return SSA_PROP_INTERESTING;
5690 return SSA_PROP_NOT_INTERESTING;
5693 /* Every other statement produces no useful ranges. */
5694 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
5695 set_value_range_to_varying (get_value_range (def));
5697 return SSA_PROP_VARYING;
5700 /* Helper that gets the value range of the SSA_NAME with version I
5701 or a symbolic range containing the SSA_NAME only if the value range
5702 is varying or undefined. */
5704 static inline value_range_t
5705 get_vr_for_comparison (int i)
5707 value_range_t vr = *(vr_value[i]);
5709 /* If name N_i does not have a valid range, use N_i as its own
5710 range. This allows us to compare against names that may
5711 have N_i in their ranges. */
5712 if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
5715 vr.min = ssa_name (i);
5716 vr.max = ssa_name (i);
5722 /* Compare all the value ranges for names equivalent to VAR with VAL
5723 using comparison code COMP. Return the same value returned by
5724 compare_range_with_value, including the setting of
5725 *STRICT_OVERFLOW_P. */
5728 compare_name_with_value (enum tree_code comp, tree var, tree val,
5729 bool *strict_overflow_p)
5735 int used_strict_overflow;
5737 value_range_t equiv_vr;
5739 /* Get the set of equivalences for VAR. */
5740 e = get_value_range (var)->equiv;
5742 /* Start at -1. Set it to 0 if we do a comparison without relying
5743 on overflow, or 1 if all comparisons rely on overflow. */
5744 used_strict_overflow = -1;
5746 /* Compare vars' value range with val. */
5747 equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
5749 retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
5751 used_strict_overflow = sop ? 1 : 0;
5753 /* If the equiv set is empty we have done all work we need to do. */
5757 && used_strict_overflow > 0)
5758 *strict_overflow_p = true;
5762 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
5764 equiv_vr = get_vr_for_comparison (i);
5766 t = compare_range_with_value (comp, &equiv_vr, val, &sop);
5769 /* If we get different answers from different members
5770 of the equivalence set this check must be in a dead
5771 code region. Folding it to a trap representation
5772 would be correct here. For now just return don't-know. */
5782 used_strict_overflow = 0;
5783 else if (used_strict_overflow < 0)
5784 used_strict_overflow = 1;
5789 && used_strict_overflow > 0)
5790 *strict_overflow_p = true;
5796 /* Given a comparison code COMP and names N1 and N2, compare all the
5797 ranges equivalent to N1 against all the ranges equivalent to N2
5798 to determine the value of N1 COMP N2. Return the same value
5799 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
5800 whether we relied on an overflow infinity in the comparison. */
5804 compare_names (enum tree_code comp, tree n1, tree n2,
5805 bool *strict_overflow_p)
5809 bitmap_iterator bi1, bi2;
5811 int used_strict_overflow;
5812 static bitmap_obstack *s_obstack = NULL;
5813 static bitmap s_e1 = NULL, s_e2 = NULL;
5815 /* Compare the ranges of every name equivalent to N1 against the
5816 ranges of every name equivalent to N2. */
5817 e1 = get_value_range (n1)->equiv;
5818 e2 = get_value_range (n2)->equiv;
5820 /* Use the fake bitmaps if e1 or e2 are not available. */
5821 if (s_obstack == NULL)
5823 s_obstack = XNEW (bitmap_obstack);
5824 bitmap_obstack_initialize (s_obstack);
5825 s_e1 = BITMAP_ALLOC (s_obstack);
5826 s_e2 = BITMAP_ALLOC (s_obstack);
5833 /* Add N1 and N2 to their own set of equivalences to avoid
5834 duplicating the body of the loop just to check N1 and N2
5836 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
5837 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
5839 /* If the equivalence sets have a common intersection, then the two
5840 names can be compared without checking their ranges. */
5841 if (bitmap_intersect_p (e1, e2))
5843 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5844 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5846 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
5848 : boolean_false_node;
5851 /* Start at -1. Set it to 0 if we do a comparison without relying
5852 on overflow, or 1 if all comparisons rely on overflow. */
5853 used_strict_overflow = -1;
5855 /* Otherwise, compare all the equivalent ranges. First, add N1 and
5856 N2 to their own set of equivalences to avoid duplicating the body
5857 of the loop just to check N1 and N2 ranges. */
5858 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
5860 value_range_t vr1 = get_vr_for_comparison (i1);
5862 t = retval = NULL_TREE;
5863 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
5867 value_range_t vr2 = get_vr_for_comparison (i2);
5869 t = compare_ranges (comp, &vr1, &vr2, &sop);
5872 /* If we get different answers from different members
5873 of the equivalence set this check must be in a dead
5874 code region. Folding it to a trap representation
5875 would be correct here. For now just return don't-know. */
5879 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5880 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5886 used_strict_overflow = 0;
5887 else if (used_strict_overflow < 0)
5888 used_strict_overflow = 1;
5894 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5895 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5896 if (used_strict_overflow > 0)
5897 *strict_overflow_p = true;
5902 /* None of the equivalent ranges are useful in computing this
5904 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5905 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5909 /* Helper function for vrp_evaluate_conditional_warnv. */
5912 vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code code,
5914 bool * strict_overflow_p)
5916 value_range_t *vr0, *vr1;
5918 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
5919 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
5922 return compare_ranges (code, vr0, vr1, strict_overflow_p);
5923 else if (vr0 && vr1 == NULL)
5924 return compare_range_with_value (code, vr0, op1, strict_overflow_p);
5925 else if (vr0 == NULL && vr1)
5926 return (compare_range_with_value
5927 (swap_tree_comparison (code), vr1, op0, strict_overflow_p));
5931 /* Helper function for vrp_evaluate_conditional_warnv. */
5934 vrp_evaluate_conditional_warnv_with_ops (enum tree_code code, tree op0,
5935 tree op1, bool use_equiv_p,
5936 bool *strict_overflow_p, bool *only_ranges)
5940 *only_ranges = true;
5942 /* We only deal with integral and pointer types. */
5943 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
5944 && !POINTER_TYPE_P (TREE_TYPE (op0)))
5950 && (ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
5951 (code, op0, op1, strict_overflow_p)))
5953 *only_ranges = false;
5954 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
5955 return compare_names (code, op0, op1, strict_overflow_p);
5956 else if (TREE_CODE (op0) == SSA_NAME)
5957 return compare_name_with_value (code, op0, op1, strict_overflow_p);
5958 else if (TREE_CODE (op1) == SSA_NAME)
5959 return (compare_name_with_value
5960 (swap_tree_comparison (code), op1, op0, strict_overflow_p));
5963 return vrp_evaluate_conditional_warnv_with_ops_using_ranges (code, op0, op1,
5968 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
5969 information. Return NULL if the conditional can not be evaluated.
5970 The ranges of all the names equivalent with the operands in COND
5971 will be used when trying to compute the value. If the result is
5972 based on undefined signed overflow, issue a warning if
5976 vrp_evaluate_conditional (enum tree_code code, tree op0, tree op1, gimple stmt)
5982 /* Some passes and foldings leak constants with overflow flag set
5983 into the IL. Avoid doing wrong things with these and bail out. */
5984 if ((TREE_CODE (op0) == INTEGER_CST
5985 && TREE_OVERFLOW (op0))
5986 || (TREE_CODE (op1) == INTEGER_CST
5987 && TREE_OVERFLOW (op1)))
5991 ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop,
5996 enum warn_strict_overflow_code wc;
5997 const char* warnmsg;
5999 if (is_gimple_min_invariant (ret))
6001 wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
6002 warnmsg = G_("assuming signed overflow does not occur when "
6003 "simplifying conditional to constant");
6007 wc = WARN_STRICT_OVERFLOW_COMPARISON;
6008 warnmsg = G_("assuming signed overflow does not occur when "
6009 "simplifying conditional");
6012 if (issue_strict_overflow_warning (wc))
6014 location_t location;
6016 if (!gimple_has_location (stmt))
6017 location = input_location;
6019 location = gimple_location (stmt);
6020 warning_at (location, OPT_Wstrict_overflow, "%s", warnmsg);
6024 if (warn_type_limits
6025 && ret && only_ranges
6026 && TREE_CODE_CLASS (code) == tcc_comparison
6027 && TREE_CODE (op0) == SSA_NAME)
6029 /* If the comparison is being folded and the operand on the LHS
6030 is being compared against a constant value that is outside of
6031 the natural range of OP0's type, then the predicate will
6032 always fold regardless of the value of OP0. If -Wtype-limits
6033 was specified, emit a warning. */
6034 tree type = TREE_TYPE (op0);
6035 value_range_t *vr0 = get_value_range (op0);
6037 if (vr0->type != VR_VARYING
6038 && INTEGRAL_TYPE_P (type)
6039 && vrp_val_is_min (vr0->min)
6040 && vrp_val_is_max (vr0->max)
6041 && is_gimple_min_invariant (op1))
6043 location_t location;
6045 if (!gimple_has_location (stmt))
6046 location = input_location;
6048 location = gimple_location (stmt);
6050 warning_at (location, OPT_Wtype_limits,
6052 ? G_("comparison always false "
6053 "due to limited range of data type")
6054 : G_("comparison always true "
6055 "due to limited range of data type"));
6063 /* Visit conditional statement STMT. If we can determine which edge
6064 will be taken out of STMT's basic block, record it in
6065 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
6066 SSA_PROP_VARYING. */
6068 static enum ssa_prop_result
6069 vrp_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
6074 *taken_edge_p = NULL;
6076 if (dump_file && (dump_flags & TDF_DETAILS))
6081 fprintf (dump_file, "\nVisiting conditional with predicate: ");
6082 print_gimple_stmt (dump_file, stmt, 0, 0);
6083 fprintf (dump_file, "\nWith known ranges\n");
6085 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
6087 fprintf (dump_file, "\t");
6088 print_generic_expr (dump_file, use, 0);
6089 fprintf (dump_file, ": ");
6090 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
6093 fprintf (dump_file, "\n");
6096 /* Compute the value of the predicate COND by checking the known
6097 ranges of each of its operands.
6099 Note that we cannot evaluate all the equivalent ranges here
6100 because those ranges may not yet be final and with the current
6101 propagation strategy, we cannot determine when the value ranges
6102 of the names in the equivalence set have changed.
6104 For instance, given the following code fragment
6108 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
6112 Assume that on the first visit to i_14, i_5 has the temporary
6113 range [8, 8] because the second argument to the PHI function is
6114 not yet executable. We derive the range ~[0, 0] for i_14 and the
6115 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
6116 the first time, since i_14 is equivalent to the range [8, 8], we
6117 determine that the predicate is always false.
6119 On the next round of propagation, i_13 is determined to be
6120 VARYING, which causes i_5 to drop down to VARYING. So, another
6121 visit to i_14 is scheduled. In this second visit, we compute the
6122 exact same range and equivalence set for i_14, namely ~[0, 0] and
6123 { i_5 }. But we did not have the previous range for i_5
6124 registered, so vrp_visit_assignment thinks that the range for
6125 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
6126 is not visited again, which stops propagation from visiting
6127 statements in the THEN clause of that if().
6129 To properly fix this we would need to keep the previous range
6130 value for the names in the equivalence set. This way we would've
6131 discovered that from one visit to the other i_5 changed from
6132 range [8, 8] to VR_VARYING.
6134 However, fixing this apparent limitation may not be worth the
6135 additional checking. Testing on several code bases (GCC, DLV,
6136 MICO, TRAMP3D and SPEC2000) showed that doing this results in
6137 4 more predicates folded in SPEC. */
6140 val = vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt),
6141 gimple_cond_lhs (stmt),
6142 gimple_cond_rhs (stmt),
6147 *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
6150 if (dump_file && (dump_flags & TDF_DETAILS))
6152 "\nIgnoring predicate evaluation because "
6153 "it assumes that signed overflow is undefined");
6158 if (dump_file && (dump_flags & TDF_DETAILS))
6160 fprintf (dump_file, "\nPredicate evaluates to: ");
6161 if (val == NULL_TREE)
6162 fprintf (dump_file, "DON'T KNOW\n");
6164 print_generic_stmt (dump_file, val, 0);
6167 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
6170 /* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
6171 that includes the value VAL. The search is restricted to the range
6172 [START_IDX, n - 1] where n is the size of VEC.
6174 If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
6177 If there is no CASE_LABEL for VAL and there is one that is larger than VAL,
6178 it is placed in IDX and false is returned.
6180 If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
6184 find_case_label_index (gimple stmt, size_t start_idx, tree val, size_t *idx)
6186 size_t n = gimple_switch_num_labels (stmt);
6189 /* Find case label for minimum of the value range or the next one.
6190 At each iteration we are searching in [low, high - 1]. */
6192 for (low = start_idx, high = n; high != low; )
6196 /* Note that i != high, so we never ask for n. */
6197 size_t i = (high + low) / 2;
6198 t = gimple_switch_label (stmt, i);
6200 /* Cache the result of comparing CASE_LOW and val. */
6201 cmp = tree_int_cst_compare (CASE_LOW (t), val);
6205 /* Ranges cannot be empty. */
6214 if (CASE_HIGH (t) != NULL
6215 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
6227 /* Searches the case label vector VEC for the range of CASE_LABELs that is used
6228 for values between MIN and MAX. The first index is placed in MIN_IDX. The
6229 last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
6230 then MAX_IDX < MIN_IDX.
6231 Returns true if the default label is not needed. */
6234 find_case_label_range (gimple stmt, tree min, tree max, size_t *min_idx,
6238 bool min_take_default = !find_case_label_index (stmt, 1, min, &i);
6239 bool max_take_default = !find_case_label_index (stmt, i, max, &j);
6243 && max_take_default)
6245 /* Only the default case label reached.
6246 Return an empty range. */
6253 bool take_default = min_take_default || max_take_default;
6257 if (max_take_default)
6260 /* If the case label range is continuous, we do not need
6261 the default case label. Verify that. */
6262 high = CASE_LOW (gimple_switch_label (stmt, i));
6263 if (CASE_HIGH (gimple_switch_label (stmt, i)))
6264 high = CASE_HIGH (gimple_switch_label (stmt, i));
6265 for (k = i + 1; k <= j; ++k)
6267 low = CASE_LOW (gimple_switch_label (stmt, k));
6268 if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0)))
6270 take_default = true;
6274 if (CASE_HIGH (gimple_switch_label (stmt, k)))
6275 high = CASE_HIGH (gimple_switch_label (stmt, k));
6280 return !take_default;
6284 /* Visit switch statement STMT. If we can determine which edge
6285 will be taken out of STMT's basic block, record it in
6286 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
6287 SSA_PROP_VARYING. */
6289 static enum ssa_prop_result
6290 vrp_visit_switch_stmt (gimple stmt, edge *taken_edge_p)
6294 size_t i = 0, j = 0;
6297 *taken_edge_p = NULL;
6298 op = gimple_switch_index (stmt);
6299 if (TREE_CODE (op) != SSA_NAME)
6300 return SSA_PROP_VARYING;
6302 vr = get_value_range (op);
6303 if (dump_file && (dump_flags & TDF_DETAILS))
6305 fprintf (dump_file, "\nVisiting switch expression with operand ");
6306 print_generic_expr (dump_file, op, 0);
6307 fprintf (dump_file, " with known range ");
6308 dump_value_range (dump_file, vr);
6309 fprintf (dump_file, "\n");
6312 if (vr->type != VR_RANGE
6313 || symbolic_range_p (vr))
6314 return SSA_PROP_VARYING;
6316 /* Find the single edge that is taken from the switch expression. */
6317 take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
6319 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
6323 gcc_assert (take_default);
6324 val = gimple_switch_default_label (stmt);
6328 /* Check if labels with index i to j and maybe the default label
6329 are all reaching the same label. */
6331 val = gimple_switch_label (stmt, i);
6333 && CASE_LABEL (gimple_switch_default_label (stmt))
6334 != CASE_LABEL (val))
6336 if (dump_file && (dump_flags & TDF_DETAILS))
6337 fprintf (dump_file, " not a single destination for this "
6339 return SSA_PROP_VARYING;
6341 for (++i; i <= j; ++i)
6343 if (CASE_LABEL (gimple_switch_label (stmt, i)) != CASE_LABEL (val))
6345 if (dump_file && (dump_flags & TDF_DETAILS))
6346 fprintf (dump_file, " not a single destination for this "
6348 return SSA_PROP_VARYING;
6353 *taken_edge_p = find_edge (gimple_bb (stmt),
6354 label_to_block (CASE_LABEL (val)));
6356 if (dump_file && (dump_flags & TDF_DETAILS))
6358 fprintf (dump_file, " will take edge to ");
6359 print_generic_stmt (dump_file, CASE_LABEL (val), 0);
6362 return SSA_PROP_INTERESTING;
6366 /* Evaluate statement STMT. If the statement produces a useful range,
6367 return SSA_PROP_INTERESTING and record the SSA name with the
6368 interesting range into *OUTPUT_P.
6370 If STMT is a conditional branch and we can determine its truth
6371 value, the taken edge is recorded in *TAKEN_EDGE_P.
6373 If STMT produces a varying value, return SSA_PROP_VARYING. */
6375 static enum ssa_prop_result
6376 vrp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p)
6381 if (dump_file && (dump_flags & TDF_DETAILS))
6383 fprintf (dump_file, "\nVisiting statement:\n");
6384 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
6385 fprintf (dump_file, "\n");
6388 if (!stmt_interesting_for_vrp (stmt))
6389 gcc_assert (stmt_ends_bb_p (stmt));
6390 else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
6392 /* In general, assignments with virtual operands are not useful
6393 for deriving ranges, with the obvious exception of calls to
6394 builtin functions. */
6396 if ((is_gimple_call (stmt)
6397 && gimple_call_fndecl (stmt) != NULL_TREE
6398 && DECL_IS_BUILTIN (gimple_call_fndecl (stmt)))
6399 || !gimple_vuse (stmt))
6400 return vrp_visit_assignment_or_call (stmt, output_p);
6402 else if (gimple_code (stmt) == GIMPLE_COND)
6403 return vrp_visit_cond_stmt (stmt, taken_edge_p);
6404 else if (gimple_code (stmt) == GIMPLE_SWITCH)
6405 return vrp_visit_switch_stmt (stmt, taken_edge_p);
6407 /* All other statements produce nothing of interest for VRP, so mark
6408 their outputs varying and prevent further simulation. */
6409 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
6410 set_value_range_to_varying (get_value_range (def));
6412 return SSA_PROP_VARYING;
6416 /* Meet operation for value ranges. Given two value ranges VR0 and
6417 VR1, store in VR0 a range that contains both VR0 and VR1. This
6418 may not be the smallest possible such range. */
6421 vrp_meet (value_range_t *vr0, value_range_t *vr1)
6423 if (vr0->type == VR_UNDEFINED)
6425 copy_value_range (vr0, vr1);
6429 if (vr1->type == VR_UNDEFINED)
6431 /* Nothing to do. VR0 already has the resulting range. */
6435 if (vr0->type == VR_VARYING)
6437 /* Nothing to do. VR0 already has the resulting range. */
6441 if (vr1->type == VR_VARYING)
6443 set_value_range_to_varying (vr0);
6447 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
6452 /* Compute the convex hull of the ranges. The lower limit of
6453 the new range is the minimum of the two ranges. If they
6454 cannot be compared, then give up. */
6455 cmp = compare_values (vr0->min, vr1->min);
6456 if (cmp == 0 || cmp == 1)
6463 /* Similarly, the upper limit of the new range is the maximum
6464 of the two ranges. If they cannot be compared, then
6466 cmp = compare_values (vr0->max, vr1->max);
6467 if (cmp == 0 || cmp == -1)
6474 /* Check for useless ranges. */
6475 if (INTEGRAL_TYPE_P (TREE_TYPE (min))
6476 && ((vrp_val_is_min (min) || is_overflow_infinity (min))
6477 && (vrp_val_is_max (max) || is_overflow_infinity (max))))
6480 /* The resulting set of equivalences is the intersection of
6482 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
6483 bitmap_and_into (vr0->equiv, vr1->equiv);
6484 else if (vr0->equiv && !vr1->equiv)
6485 bitmap_clear (vr0->equiv);
6487 set_value_range (vr0, vr0->type, min, max, vr0->equiv);
6489 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
6491 /* Two anti-ranges meet only if their complements intersect.
6492 Only handle the case of identical ranges. */
6493 if (compare_values (vr0->min, vr1->min) == 0
6494 && compare_values (vr0->max, vr1->max) == 0
6495 && compare_values (vr0->min, vr0->max) == 0)
6497 /* The resulting set of equivalences is the intersection of
6499 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
6500 bitmap_and_into (vr0->equiv, vr1->equiv);
6501 else if (vr0->equiv && !vr1->equiv)
6502 bitmap_clear (vr0->equiv);
6507 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
6509 /* For a numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4],
6510 only handle the case where the ranges have an empty intersection.
6511 The result of the meet operation is the anti-range. */
6512 if (!symbolic_range_p (vr0)
6513 && !symbolic_range_p (vr1)
6514 && !value_ranges_intersect_p (vr0, vr1))
6516 /* Copy most of VR1 into VR0. Don't copy VR1's equivalence
6517 set. We need to compute the intersection of the two
6518 equivalence sets. */
6519 if (vr1->type == VR_ANTI_RANGE)
6520 set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
6522 /* The resulting set of equivalences is the intersection of
6524 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
6525 bitmap_and_into (vr0->equiv, vr1->equiv);
6526 else if (vr0->equiv && !vr1->equiv)
6527 bitmap_clear (vr0->equiv);
6538 /* Failed to find an efficient meet. Before giving up and setting
6539 the result to VARYING, see if we can at least derive a useful
6540 anti-range. FIXME, all this nonsense about distinguishing
6541 anti-ranges from ranges is necessary because of the odd
6542 semantics of range_includes_zero_p and friends. */
6543 if (!symbolic_range_p (vr0)
6544 && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0))
6545 || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0)))
6546 && !symbolic_range_p (vr1)
6547 && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1))
6548 || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1))))
6550 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
6552 /* Since this meet operation did not result from the meeting of
6553 two equivalent names, VR0 cannot have any equivalences. */
6555 bitmap_clear (vr0->equiv);
6558 set_value_range_to_varying (vr0);
6562 /* Visit all arguments for PHI node PHI that flow through executable
6563 edges. If a valid value range can be derived from all the incoming
6564 value ranges, set a new range for the LHS of PHI. */
6566 static enum ssa_prop_result
6567 vrp_visit_phi_node (gimple phi)
6570 tree lhs = PHI_RESULT (phi);
6571 value_range_t *lhs_vr = get_value_range (lhs);
6572 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
6573 int edges, old_edges;
6576 if (dump_file && (dump_flags & TDF_DETAILS))
6578 fprintf (dump_file, "\nVisiting PHI node: ");
6579 print_gimple_stmt (dump_file, phi, 0, dump_flags);
6583 for (i = 0; i < gimple_phi_num_args (phi); i++)
6585 edge e = gimple_phi_arg_edge (phi, i);
6587 if (dump_file && (dump_flags & TDF_DETAILS))
6590 "\n Argument #%d (%d -> %d %sexecutable)\n",
6591 (int) i, e->src->index, e->dest->index,
6592 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
6595 if (e->flags & EDGE_EXECUTABLE)
6597 tree arg = PHI_ARG_DEF (phi, i);
6598 value_range_t vr_arg;
6602 if (TREE_CODE (arg) == SSA_NAME)
6604 vr_arg = *(get_value_range (arg));
6608 if (is_overflow_infinity (arg))
6610 arg = copy_node (arg);
6611 TREE_OVERFLOW (arg) = 0;
6614 vr_arg.type = VR_RANGE;
6617 vr_arg.equiv = NULL;
6620 if (dump_file && (dump_flags & TDF_DETAILS))
6622 fprintf (dump_file, "\t");
6623 print_generic_expr (dump_file, arg, dump_flags);
6624 fprintf (dump_file, "\n\tValue: ");
6625 dump_value_range (dump_file, &vr_arg);
6626 fprintf (dump_file, "\n");
6629 vrp_meet (&vr_result, &vr_arg);
6631 if (vr_result.type == VR_VARYING)
6636 if (vr_result.type == VR_VARYING)
6639 old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
6640 vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
6642 /* To prevent infinite iterations in the algorithm, derive ranges
6643 when the new value is slightly bigger or smaller than the
6644 previous one. We don't do this if we have seen a new executable
6645 edge; this helps us avoid an overflow infinity for conditionals
6646 which are not in a loop. */
6648 && gimple_phi_num_args (phi) > 1
6649 && edges == old_edges)
6651 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
6652 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
6654 /* For non VR_RANGE or for pointers fall back to varying if
6655 the range changed. */
6656 if ((lhs_vr->type != VR_RANGE || vr_result.type != VR_RANGE
6657 || POINTER_TYPE_P (TREE_TYPE (lhs)))
6658 && (cmp_min != 0 || cmp_max != 0))
6661 /* If the new minimum is smaller or larger than the previous
6662 one, go all the way to -INF. In the first case, to avoid
6663 iterating millions of times to reach -INF, and in the
6664 other case to avoid infinite bouncing between different
6666 if (cmp_min > 0 || cmp_min < 0)
6668 if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
6669 || !vrp_var_may_overflow (lhs, phi))
6670 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
6671 else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
6673 negative_overflow_infinity (TREE_TYPE (vr_result.min));
6676 /* Similarly, if the new maximum is smaller or larger than
6677 the previous one, go all the way to +INF. */
6678 if (cmp_max < 0 || cmp_max > 0)
6680 if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
6681 || !vrp_var_may_overflow (lhs, phi))
6682 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
6683 else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
6685 positive_overflow_infinity (TREE_TYPE (vr_result.max));
6688 /* If we dropped either bound to +-INF then if this is a loop
6689 PHI node SCEV may known more about its value-range. */
6690 if ((cmp_min > 0 || cmp_min < 0
6691 || cmp_max < 0 || cmp_max > 0)
6693 && (l = loop_containing_stmt (phi))
6694 && l->header == gimple_bb (phi))
6695 adjust_range_with_scev (&vr_result, l, phi, lhs);
6697 /* If we will end up with a (-INF, +INF) range, set it to
6698 VARYING. Same if the previous max value was invalid for
6699 the type and we end up with vr_result.min > vr_result.max. */
6700 if ((vrp_val_is_max (vr_result.max)
6701 && vrp_val_is_min (vr_result.min))
6702 || compare_values (vr_result.min,
6707 /* If the new range is different than the previous value, keep
6709 if (update_value_range (lhs, &vr_result))
6711 if (dump_file && (dump_flags & TDF_DETAILS))
6713 fprintf (dump_file, "Found new range for ");
6714 print_generic_expr (dump_file, lhs, 0);
6715 fprintf (dump_file, ": ");
6716 dump_value_range (dump_file, &vr_result);
6717 fprintf (dump_file, "\n\n");
6720 return SSA_PROP_INTERESTING;
6723 /* Nothing changed, don't add outgoing edges. */
6724 return SSA_PROP_NOT_INTERESTING;
6726 /* No match found. Set the LHS to VARYING. */
6728 set_value_range_to_varying (lhs_vr);
6729 return SSA_PROP_VARYING;
6732 /* Simplify boolean operations if the source is known
6733 to be already a boolean. */
6735 simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
6737 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
6742 bool need_conversion;
6744 op0 = gimple_assign_rhs1 (stmt);
6745 if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
6747 if (TREE_CODE (op0) != SSA_NAME)
6749 vr = get_value_range (op0);
6751 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
6752 if (!val || !integer_onep (val))
6755 val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
6756 if (!val || !integer_onep (val))
6760 if (rhs_code == TRUTH_NOT_EXPR)
6763 op1 = build_int_cst (TREE_TYPE (op0), 1);
6767 op1 = gimple_assign_rhs2 (stmt);
6769 /* Reduce number of cases to handle. */
6770 if (is_gimple_min_invariant (op1))
6772 /* Exclude anything that should have been already folded. */
6773 if (rhs_code != EQ_EXPR
6774 && rhs_code != NE_EXPR
6775 && rhs_code != TRUTH_XOR_EXPR)
6778 if (!integer_zerop (op1)
6779 && !integer_onep (op1)
6780 && !integer_all_onesp (op1))
6783 /* Limit the number of cases we have to consider. */
6784 if (rhs_code == EQ_EXPR)
6787 op1 = fold_unary (TRUTH_NOT_EXPR, TREE_TYPE (op1), op1);
6792 /* Punt on A == B as there is no BIT_XNOR_EXPR. */
6793 if (rhs_code == EQ_EXPR)
6796 if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
6798 vr = get_value_range (op1);
6799 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
6800 if (!val || !integer_onep (val))
6803 val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
6804 if (!val || !integer_onep (val))
6810 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
6812 location_t location;
6814 if (!gimple_has_location (stmt))
6815 location = input_location;
6817 location = gimple_location (stmt);
6819 if (rhs_code == TRUTH_AND_EXPR || rhs_code == TRUTH_OR_EXPR)
6820 warning_at (location, OPT_Wstrict_overflow,
6821 _("assuming signed overflow does not occur when "
6822 "simplifying && or || to & or |"));
6824 warning_at (location, OPT_Wstrict_overflow,
6825 _("assuming signed overflow does not occur when "
6826 "simplifying ==, != or ! to identity or ^"));
6830 !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
6833 /* Make sure to not sign-extend -1 as a boolean value. */
6835 && !TYPE_UNSIGNED (TREE_TYPE (op0))
6836 && TYPE_PRECISION (TREE_TYPE (op0)) == 1)
6841 case TRUTH_AND_EXPR:
6842 rhs_code = BIT_AND_EXPR;
6845 rhs_code = BIT_IOR_EXPR;
6847 case TRUTH_XOR_EXPR:
6849 if (integer_zerop (op1))
6851 gimple_assign_set_rhs_with_ops (gsi,
6852 need_conversion ? NOP_EXPR : SSA_NAME,
6854 update_stmt (gsi_stmt (*gsi));
6858 rhs_code = BIT_XOR_EXPR;
6864 if (need_conversion)
6867 gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
6868 update_stmt (gsi_stmt (*gsi));
6872 /* Simplify a division or modulo operator to a right shift or
6873 bitwise and if the first operand is unsigned or is greater
6874 than zero and the second operand is an exact power of two. */
6877 simplify_div_or_mod_using_ranges (gimple stmt)
6879 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
6881 tree op0 = gimple_assign_rhs1 (stmt);
6882 tree op1 = gimple_assign_rhs2 (stmt);
6883 value_range_t *vr = get_value_range (gimple_assign_rhs1 (stmt));
6885 if (TYPE_UNSIGNED (TREE_TYPE (op0)))
6887 val = integer_one_node;
6893 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
6897 && integer_onep (val)
6898 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
6900 location_t location;
6902 if (!gimple_has_location (stmt))
6903 location = input_location;
6905 location = gimple_location (stmt);
6906 warning_at (location, OPT_Wstrict_overflow,
6907 "assuming signed overflow does not occur when "
6908 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
6912 if (val && integer_onep (val))
6916 if (rhs_code == TRUNC_DIV_EXPR)
6918 t = build_int_cst (NULL_TREE, tree_log2 (op1));
6919 gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
6920 gimple_assign_set_rhs1 (stmt, op0);
6921 gimple_assign_set_rhs2 (stmt, t);
6925 t = build_int_cst (TREE_TYPE (op1), 1);
6926 t = int_const_binop (MINUS_EXPR, op1, t, 0);
6927 t = fold_convert (TREE_TYPE (op0), t);
6929 gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
6930 gimple_assign_set_rhs1 (stmt, op0);
6931 gimple_assign_set_rhs2 (stmt, t);
6941 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
6942 ABS_EXPR. If the operand is <= 0, then simplify the
6943 ABS_EXPR into a NEGATE_EXPR. */
6946 simplify_abs_using_ranges (gimple stmt)
6949 tree op = gimple_assign_rhs1 (stmt);
6950 tree type = TREE_TYPE (op);
6951 value_range_t *vr = get_value_range (op);
6953 if (TYPE_UNSIGNED (type))
6955 val = integer_zero_node;
6961 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop);
6965 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node,
6970 if (integer_zerop (val))
6971 val = integer_one_node;
6972 else if (integer_onep (val))
6973 val = integer_zero_node;
6978 && (integer_onep (val) || integer_zerop (val)))
6980 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
6982 location_t location;
6984 if (!gimple_has_location (stmt))
6985 location = input_location;
6987 location = gimple_location (stmt);
6988 warning_at (location, OPT_Wstrict_overflow,
6989 "assuming signed overflow does not occur when "
6990 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
6993 gimple_assign_set_rhs1 (stmt, op);
6994 if (integer_onep (val))
6995 gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
6997 gimple_assign_set_rhs_code (stmt, SSA_NAME);
7006 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
7007 If all the bits that are being cleared by & are already
7008 known to be zero from VR, or all the bits that are being
7009 set by | are already known to be one from VR, the bit
7010 operation is redundant. */
7013 simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
7015 tree op0 = gimple_assign_rhs1 (stmt);
7016 tree op1 = gimple_assign_rhs2 (stmt);
7017 tree op = NULL_TREE;
7018 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
7019 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
7020 double_int may_be_nonzero0, may_be_nonzero1;
7021 double_int must_be_nonzero0, must_be_nonzero1;
7024 if (TREE_CODE (op0) == SSA_NAME)
7025 vr0 = *(get_value_range (op0));
7026 else if (is_gimple_min_invariant (op0))
7027 set_value_range_to_value (&vr0, op0, NULL);
7031 if (TREE_CODE (op1) == SSA_NAME)
7032 vr1 = *(get_value_range (op1));
7033 else if (is_gimple_min_invariant (op1))
7034 set_value_range_to_value (&vr1, op1, NULL);
7038 if (!zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0, &must_be_nonzero0))
7040 if (!zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1, &must_be_nonzero1))
7043 switch (gimple_assign_rhs_code (stmt))
7046 mask = double_int_and_not (may_be_nonzero0, must_be_nonzero1);
7047 if (double_int_zero_p (mask))
7052 mask = double_int_and_not (may_be_nonzero1, must_be_nonzero0);
7053 if (double_int_zero_p (mask))
7060 mask = double_int_and_not (may_be_nonzero0, must_be_nonzero1);
7061 if (double_int_zero_p (mask))
7066 mask = double_int_and_not (may_be_nonzero1, must_be_nonzero0);
7067 if (double_int_zero_p (mask))
7077 if (op == NULL_TREE)
7080 gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op, NULL);
7081 update_stmt (gsi_stmt (*gsi));
7085 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
7086 a known value range VR.
7088 If there is one and only one value which will satisfy the
7089 conditional, then return that value. Else return NULL. */
7092 test_for_singularity (enum tree_code cond_code, tree op0,
7093 tree op1, value_range_t *vr)
7098 /* Extract minimum/maximum values which satisfy the
7099 the conditional as it was written. */
7100 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
7102 /* This should not be negative infinity; there is no overflow
7104 min = TYPE_MIN_VALUE (TREE_TYPE (op0));
7107 if (cond_code == LT_EXPR && !is_overflow_infinity (max))
7109 tree one = build_int_cst (TREE_TYPE (op0), 1);
7110 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
7112 TREE_NO_WARNING (max) = 1;
7115 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
7117 /* This should not be positive infinity; there is no overflow
7119 max = TYPE_MAX_VALUE (TREE_TYPE (op0));
7122 if (cond_code == GT_EXPR && !is_overflow_infinity (min))
7124 tree one = build_int_cst (TREE_TYPE (op0), 1);
7125 min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
7127 TREE_NO_WARNING (min) = 1;
7131 /* Now refine the minimum and maximum values using any
7132 value range information we have for op0. */
7135 if (compare_values (vr->min, min) == 1)
7137 if (compare_values (vr->max, max) == -1)
7140 /* If the new min/max values have converged to a single value,
7141 then there is only one value which can satisfy the condition,
7142 return that value. */
7143 if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
7149 /* Simplify a conditional using a relational operator to an equality
7150 test if the range information indicates only one value can satisfy
7151 the original conditional. */
7154 simplify_cond_using_ranges (gimple stmt)
7156 tree op0 = gimple_cond_lhs (stmt);
7157 tree op1 = gimple_cond_rhs (stmt);
7158 enum tree_code cond_code = gimple_cond_code (stmt);
7160 if (cond_code != NE_EXPR
7161 && cond_code != EQ_EXPR
7162 && TREE_CODE (op0) == SSA_NAME
7163 && INTEGRAL_TYPE_P (TREE_TYPE (op0))
7164 && is_gimple_min_invariant (op1))
7166 value_range_t *vr = get_value_range (op0);
7168 /* If we have range information for OP0, then we might be
7169 able to simplify this conditional. */
7170 if (vr->type == VR_RANGE)
7172 tree new_tree = test_for_singularity (cond_code, op0, op1, vr);
7178 fprintf (dump_file, "Simplified relational ");
7179 print_gimple_stmt (dump_file, stmt, 0, 0);
7180 fprintf (dump_file, " into ");
7183 gimple_cond_set_code (stmt, EQ_EXPR);
7184 gimple_cond_set_lhs (stmt, op0);
7185 gimple_cond_set_rhs (stmt, new_tree);
7191 print_gimple_stmt (dump_file, stmt, 0, 0);
7192 fprintf (dump_file, "\n");
7198 /* Try again after inverting the condition. We only deal
7199 with integral types here, so no need to worry about
7200 issues with inverting FP comparisons. */
7201 cond_code = invert_tree_comparison (cond_code, false);
7202 new_tree = test_for_singularity (cond_code, op0, op1, vr);
7208 fprintf (dump_file, "Simplified relational ");
7209 print_gimple_stmt (dump_file, stmt, 0, 0);
7210 fprintf (dump_file, " into ");
7213 gimple_cond_set_code (stmt, NE_EXPR);
7214 gimple_cond_set_lhs (stmt, op0);
7215 gimple_cond_set_rhs (stmt, new_tree);
7221 print_gimple_stmt (dump_file, stmt, 0, 0);
7222 fprintf (dump_file, "\n");
7233 /* Simplify a switch statement using the value range of the switch
7237 simplify_switch_using_ranges (gimple stmt)
7239 tree op = gimple_switch_index (stmt);
7244 size_t i = 0, j = 0, n, n2;
7248 if (TREE_CODE (op) == SSA_NAME)
7250 vr = get_value_range (op);
7252 /* We can only handle integer ranges. */
7253 if (vr->type != VR_RANGE
7254 || symbolic_range_p (vr))
7257 /* Find case label for min/max of the value range. */
7258 take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
7260 else if (TREE_CODE (op) == INTEGER_CST)
7262 take_default = !find_case_label_index (stmt, 1, op, &i);
7276 n = gimple_switch_num_labels (stmt);
7278 /* Bail out if this is just all edges taken. */
7284 /* Build a new vector of taken case labels. */
7285 vec2 = make_tree_vec (j - i + 1 + (int)take_default);
7288 /* Add the default edge, if necessary. */
7290 TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt);
7292 for (; i <= j; ++i, ++n2)
7293 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i);
7295 /* Mark needed edges. */
7296 for (i = 0; i < n2; ++i)
7298 e = find_edge (gimple_bb (stmt),
7299 label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
7300 e->aux = (void *)-1;
7303 /* Queue not needed edges for later removal. */
7304 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
7306 if (e->aux == (void *)-1)
7312 if (dump_file && (dump_flags & TDF_DETAILS))
7314 fprintf (dump_file, "removing unreachable case label\n");
7316 VEC_safe_push (edge, heap, to_remove_edges, e);
7317 e->flags &= ~EDGE_EXECUTABLE;
7320 /* And queue an update for the stmt. */
7323 VEC_safe_push (switch_update, heap, to_update_switch_stmts, &su);
7327 /* Simplify STMT using ranges if possible. */
7330 simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
7332 gimple stmt = gsi_stmt (*gsi);
7333 if (is_gimple_assign (stmt))
7335 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
7341 case TRUTH_NOT_EXPR:
7342 case TRUTH_AND_EXPR:
7344 case TRUTH_XOR_EXPR:
7345 /* Transform EQ_EXPR, NE_EXPR, TRUTH_NOT_EXPR into BIT_XOR_EXPR
7346 or identity if the RHS is zero or one, and the LHS are known
7347 to be boolean values. Transform all TRUTH_*_EXPR into
7348 BIT_*_EXPR if both arguments are known to be boolean values. */
7349 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
7350 return simplify_truth_ops_using_ranges (gsi, stmt);
7353 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
7354 and BIT_AND_EXPR respectively if the first operand is greater
7355 than zero and the second operand is an exact power of two. */
7356 case TRUNC_DIV_EXPR:
7357 case TRUNC_MOD_EXPR:
7358 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))
7359 && integer_pow2p (gimple_assign_rhs2 (stmt)))
7360 return simplify_div_or_mod_using_ranges (stmt);
7363 /* Transform ABS (X) into X or -X as appropriate. */
7365 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
7366 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
7367 return simplify_abs_using_ranges (stmt);
7372 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
7373 if all the bits being cleared are already cleared or
7374 all the bits being set are already set. */
7375 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
7376 return simplify_bit_ops_using_ranges (gsi, stmt);
7383 else if (gimple_code (stmt) == GIMPLE_COND)
7384 return simplify_cond_using_ranges (stmt);
7385 else if (gimple_code (stmt) == GIMPLE_SWITCH)
7386 return simplify_switch_using_ranges (stmt);
7391 /* If the statement pointed by SI has a predicate whose value can be
7392 computed using the value range information computed by VRP, compute
7393 its value and return true. Otherwise, return false. */
7396 fold_predicate_in (gimple_stmt_iterator *si)
7398 bool assignment_p = false;
7400 gimple stmt = gsi_stmt (*si);
7402 if (is_gimple_assign (stmt)
7403 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
7405 assignment_p = true;
7406 val = vrp_evaluate_conditional (gimple_assign_rhs_code (stmt),
7407 gimple_assign_rhs1 (stmt),
7408 gimple_assign_rhs2 (stmt),
7411 else if (gimple_code (stmt) == GIMPLE_COND)
7412 val = vrp_evaluate_conditional (gimple_cond_code (stmt),
7413 gimple_cond_lhs (stmt),
7414 gimple_cond_rhs (stmt),
7422 val = fold_convert (gimple_expr_type (stmt), val);
7426 fprintf (dump_file, "Folding predicate ");
7427 print_gimple_expr (dump_file, stmt, 0, 0);
7428 fprintf (dump_file, " to ");
7429 print_generic_expr (dump_file, val, 0);
7430 fprintf (dump_file, "\n");
7433 if (is_gimple_assign (stmt))
7434 gimple_assign_set_rhs_from_tree (si, val);
7437 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
7438 if (integer_zerop (val))
7439 gimple_cond_make_false (stmt);
7440 else if (integer_onep (val))
7441 gimple_cond_make_true (stmt);
7452 /* Callback for substitute_and_fold folding the stmt at *SI. */
7455 vrp_fold_stmt (gimple_stmt_iterator *si)
7457 if (fold_predicate_in (si))
7460 return simplify_stmt_using_ranges (si);
7463 /* Stack of dest,src equivalency pairs that need to be restored after
7464 each attempt to thread a block's incoming edge to an outgoing edge.
7466 A NULL entry is used to mark the end of pairs which need to be
7468 static VEC(tree,heap) *stack;
7470 /* A trivial wrapper so that we can present the generic jump threading
7471 code with a simple API for simplifying statements. STMT is the
7472 statement we want to simplify, WITHIN_STMT provides the location
7473 for any overflow warnings. */
7476 simplify_stmt_for_jump_threading (gimple stmt, gimple within_stmt)
7478 /* We only use VRP information to simplify conditionals. This is
7479 overly conservative, but it's unclear if doing more would be
7480 worth the compile time cost. */
7481 if (gimple_code (stmt) != GIMPLE_COND)
7484 return vrp_evaluate_conditional (gimple_cond_code (stmt),
7485 gimple_cond_lhs (stmt),
7486 gimple_cond_rhs (stmt), within_stmt);
7489 /* Blocks which have more than one predecessor and more than
7490 one successor present jump threading opportunities, i.e.,
7491 when the block is reached from a specific predecessor, we
7492 may be able to determine which of the outgoing edges will
7493 be traversed. When this optimization applies, we are able
7494 to avoid conditionals at runtime and we may expose secondary
7495 optimization opportunities.
7497 This routine is effectively a driver for the generic jump
7498 threading code. It basically just presents the generic code
7499 with edges that may be suitable for jump threading.
7501 Unlike DOM, we do not iterate VRP if jump threading was successful.
7502 While iterating may expose new opportunities for VRP, it is expected
7503 those opportunities would be very limited and the compile time cost
7504 to expose those opportunities would be significant.
7506 As jump threading opportunities are discovered, they are registered
7507 for later realization. */
7510 identify_jump_threads (void)
7517 /* Ugh. When substituting values earlier in this pass we can
7518 wipe the dominance information. So rebuild the dominator
7519 information as we need it within the jump threading code. */
7520 calculate_dominance_info (CDI_DOMINATORS);
7522 /* We do not allow VRP information to be used for jump threading
7523 across a back edge in the CFG. Otherwise it becomes too
7524 difficult to avoid eliminating loop exit tests. Of course
7525 EDGE_DFS_BACK is not accurate at this time so we have to
7527 mark_dfs_back_edges ();
7529 /* Do not thread across edges we are about to remove. Just marking
7530 them as EDGE_DFS_BACK will do. */
7531 FOR_EACH_VEC_ELT (edge, to_remove_edges, i, e)
7532 e->flags |= EDGE_DFS_BACK;
7534 /* Allocate our unwinder stack to unwind any temporary equivalences
7535 that might be recorded. */
7536 stack = VEC_alloc (tree, heap, 20);
7538 /* To avoid lots of silly node creation, we create a single
7539 conditional and just modify it in-place when attempting to
7541 dummy = gimple_build_cond (EQ_EXPR,
7542 integer_zero_node, integer_zero_node,
7545 /* Walk through all the blocks finding those which present a
7546 potential jump threading opportunity. We could set this up
7547 as a dominator walker and record data during the walk, but
7548 I doubt it's worth the effort for the classes of jump
7549 threading opportunities we are trying to identify at this
7550 point in compilation. */
7555 /* If the generic jump threading code does not find this block
7556 interesting, then there is nothing to do. */
7557 if (! potentially_threadable_block (bb))
7560 /* We only care about blocks ending in a COND_EXPR. While there
7561 may be some value in handling SWITCH_EXPR here, I doubt it's
7562 terribly important. */
7563 last = gsi_stmt (gsi_last_bb (bb));
7564 if (gimple_code (last) != GIMPLE_COND)
7567 /* We're basically looking for any kind of conditional with
7568 integral type arguments. */
7569 if (TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
7570 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
7571 && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
7572 || is_gimple_min_invariant (gimple_cond_rhs (last)))
7573 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_rhs (last))))
7577 /* We've got a block with multiple predecessors and multiple
7578 successors which also ends in a suitable conditional. For
7579 each predecessor, see if we can thread it to a specific
7581 FOR_EACH_EDGE (e, ei, bb->preds)
7583 /* Do not thread across back edges or abnormal edges
7585 if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
7588 thread_across_edge (dummy, e, true, &stack,
7589 simplify_stmt_for_jump_threading);
7594 /* We do not actually update the CFG or SSA graphs at this point as
7595 ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
7596 handle ASSERT_EXPRs gracefully. */
7599 /* We identified all the jump threading opportunities earlier, but could
7600 not transform the CFG at that time. This routine transforms the
7601 CFG and arranges for the dominator tree to be rebuilt if necessary.
7603 Note the SSA graph update will occur during the normal TODO
7604 processing by the pass manager. */
7606 finalize_jump_threads (void)
7608 thread_through_all_blocks (false);
7609 VEC_free (tree, heap, stack);
7613 /* Traverse all the blocks folding conditionals with known ranges. */
7619 unsigned num = num_ssa_names;
7623 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
7624 dump_all_value_ranges (dump_file);
7625 fprintf (dump_file, "\n");
7628 substitute_and_fold (op_with_constant_singleton_value_range,
7629 vrp_fold_stmt, false);
7631 if (warn_array_bounds)
7632 check_all_array_refs ();
7634 /* We must identify jump threading opportunities before we release
7635 the datastructures built by VRP. */
7636 identify_jump_threads ();
7638 /* Free allocated memory. */
7639 for (i = 0; i < num; i++)
7642 BITMAP_FREE (vr_value[i]->equiv);
7647 free (vr_phi_edge_counts);
7649 /* So that we can distinguish between VRP data being available
7650 and not available. */
7652 vr_phi_edge_counts = NULL;
7656 /* Main entry point to VRP (Value Range Propagation). This pass is
7657 loosely based on J. R. C. Patterson, ``Accurate Static Branch
7658 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
7659 Programming Language Design and Implementation, pp. 67-78, 1995.
7660 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
7662 This is essentially an SSA-CCP pass modified to deal with ranges
7663 instead of constants.
7665 While propagating ranges, we may find that two or more SSA name
7666 have equivalent, though distinct ranges. For instance,
7669 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
7671 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
7675 In the code above, pointer p_5 has range [q_2, q_2], but from the
7676 code we can also determine that p_5 cannot be NULL and, if q_2 had
7677 a non-varying range, p_5's range should also be compatible with it.
7679 These equivalences are created by two expressions: ASSERT_EXPR and
7680 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
7681 result of another assertion, then we can use the fact that p_5 and
7682 p_4 are equivalent when evaluating p_5's range.
7684 Together with value ranges, we also propagate these equivalences
7685 between names so that we can take advantage of information from
7686 multiple ranges when doing final replacement. Note that this
7687 equivalency relation is transitive but not symmetric.
7689 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
7690 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
7691 in contexts where that assertion does not hold (e.g., in line 6).
7693 TODO, the main difference between this pass and Patterson's is that
7694 we do not propagate edge probabilities. We only compute whether
7695 edges can be taken or not. That is, instead of having a spectrum
7696 of jump probabilities between 0 and 1, we only deal with 0, 1 and
7697 DON'T KNOW. In the future, it may be worthwhile to propagate
7698 probabilities to aid branch prediction. */
7707 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
7708 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
7711 insert_range_assertions ();
7713 /* Estimate number of iterations - but do not use undefined behavior
7714 for this. We can't do this lazily as other functions may compute
7715 this using undefined behavior. */
7716 free_numbers_of_iterations_estimates ();
7717 estimate_numbers_of_iterations (false);
7719 to_remove_edges = VEC_alloc (edge, heap, 10);
7720 to_update_switch_stmts = VEC_alloc (switch_update, heap, 5);
7721 threadedge_initialize_values ();
7724 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
7727 free_numbers_of_iterations_estimates ();
7729 /* ASSERT_EXPRs must be removed before finalizing jump threads
7730 as finalizing jump threads calls the CFG cleanup code which
7731 does not properly handle ASSERT_EXPRs. */
7732 remove_range_assertions ();
7734 /* If we exposed any new variables, go ahead and put them into
7735 SSA form now, before we handle jump threading. This simplifies
7736 interactions between rewriting of _DECL nodes into SSA form
7737 and rewriting SSA_NAME nodes into SSA form after block
7738 duplication and CFG manipulation. */
7739 update_ssa (TODO_update_ssa);
7741 finalize_jump_threads ();
7743 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
7744 CFG in a broken state and requires a cfg_cleanup run. */
7745 FOR_EACH_VEC_ELT (edge, to_remove_edges, i, e)
7747 /* Update SWITCH_EXPR case label vector. */
7748 FOR_EACH_VEC_ELT (switch_update, to_update_switch_stmts, i, su)
7751 size_t n = TREE_VEC_LENGTH (su->vec);
7753 gimple_switch_set_num_labels (su->stmt, n);
7754 for (j = 0; j < n; j++)
7755 gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
7756 /* As we may have replaced the default label with a regular one
7757 make sure to make it a real default label again. This ensures
7758 optimal expansion. */
7759 label = gimple_switch_default_label (su->stmt);
7760 CASE_LOW (label) = NULL_TREE;
7761 CASE_HIGH (label) = NULL_TREE;
7764 if (VEC_length (edge, to_remove_edges) > 0)
7765 free_dominance_info (CDI_DOMINATORS);
7767 VEC_free (edge, heap, to_remove_edges);
7768 VEC_free (switch_update, heap, to_update_switch_stmts);
7769 threadedge_finalize_values ();
7772 loop_optimizer_finalize ();
7779 return flag_tree_vrp != 0;
7782 struct gimple_opt_pass pass_vrp =
7787 gate_vrp, /* gate */
7788 execute_vrp, /* execute */
7791 0, /* static_pass_number */
7792 TV_TREE_VRP, /* tv_id */
7793 PROP_ssa, /* properties_required */
7794 0, /* properties_provided */
7795 0, /* properties_destroyed */
7796 0, /* todo_flags_start */
7802 | TODO_ggc_collect /* todo_flags_finish */