1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "tree-flow.h"
30 #include "tree-pass.h"
31 #include "tree-dump.h"
33 #include "diagnostic.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-ssa-propagate.h"
39 #include "tree-chrec.h"
42 /* Set of SSA names found live during the RPO traversal of the function
43 for still active basic-blocks. */
46 /* Return true if the SSA name NAME is live on the edge E. */
49 live_on_edge (edge e
, tree name
)
51 return (live
[e
->dest
->index
]
52 && TEST_BIT (live
[e
->dest
->index
], SSA_NAME_VERSION (name
)));
55 /* Local functions. */
56 static int compare_values (tree val1
, tree val2
);
57 static int compare_values_warnv (tree val1
, tree val2
, bool *);
58 static void vrp_meet (value_range_t
*, value_range_t
*);
59 static tree
vrp_evaluate_conditional_warnv_with_ops (enum tree_code
,
60 tree
, tree
, bool, bool *,
63 /* Location information for ASSERT_EXPRs. Each instance of this
64 structure describes an ASSERT_EXPR for an SSA name. Since a single
65 SSA name may have more than one assertion associated with it, these
66 locations are kept in a linked list attached to the corresponding
70 /* Basic block where the assertion would be inserted. */
73 /* Some assertions need to be inserted on an edge (e.g., assertions
74 generated by COND_EXPRs). In those cases, BB will be NULL. */
77 /* Pointer to the statement that generated this assertion. */
78 gimple_stmt_iterator si
;
80 /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
81 enum tree_code comp_code
;
83 /* Value being compared against. */
86 /* Expression to compare. */
89 /* Next node in the linked list. */
90 struct assert_locus_d
*next
;
93 typedef struct assert_locus_d
*assert_locus_t
;
95 /* If bit I is present, it means that SSA name N_i has a list of
96 assertions that should be inserted in the IL. */
97 static bitmap need_assert_for
;
99 /* Array of locations lists where to insert assertions. ASSERTS_FOR[I]
100 holds a list of ASSERT_LOCUS_T nodes that describe where
101 ASSERT_EXPRs for SSA name N_I should be inserted. */
102 static assert_locus_t
*asserts_for
;
104 /* Value range array. After propagation, VR_VALUE[I] holds the range
105 of values that SSA name N_I may take. */
106 static value_range_t
**vr_value
;
108 /* For a PHI node which sets SSA name N_I, VR_COUNTS[I] holds the
109 number of executable edges we saw the last time we visited the
111 static int *vr_phi_edge_counts
;
118 static VEC (edge
, heap
) *to_remove_edges
;
119 DEF_VEC_O(switch_update
);
120 DEF_VEC_ALLOC_O(switch_update
, heap
);
121 static VEC (switch_update
, heap
) *to_update_switch_stmts
;
124 /* Return the maximum value for TYPEs base type. */
127 vrp_val_max (const_tree type
)
129 if (!INTEGRAL_TYPE_P (type
))
132 /* For integer sub-types the values for the base type are relevant. */
133 if (TREE_TYPE (type
))
134 type
= TREE_TYPE (type
);
136 return TYPE_MAX_VALUE (type
);
139 /* Return the minimum value for TYPEs base type. */
142 vrp_val_min (const_tree type
)
144 if (!INTEGRAL_TYPE_P (type
))
147 /* For integer sub-types the values for the base type are relevant. */
148 if (TREE_TYPE (type
))
149 type
= TREE_TYPE (type
);
151 return TYPE_MIN_VALUE (type
);
154 /* Return whether VAL is equal to the maximum value of its type. This
155 will be true for a positive overflow infinity. We can't do a
156 simple equality comparison with TYPE_MAX_VALUE because C typedefs
157 and Ada subtypes can produce types whose TYPE_MAX_VALUE is not ==
158 to the integer constant with the same value in the type. */
161 vrp_val_is_max (const_tree val
)
163 tree type_max
= vrp_val_max (TREE_TYPE (val
));
164 return (val
== type_max
165 || (type_max
!= NULL_TREE
166 && operand_equal_p (val
, type_max
, 0)));
169 /* Return whether VAL is equal to the minimum value of its type. This
170 will be true for a negative overflow infinity. */
173 vrp_val_is_min (const_tree val
)
175 tree type_min
= vrp_val_min (TREE_TYPE (val
));
176 return (val
== type_min
177 || (type_min
!= NULL_TREE
178 && operand_equal_p (val
, type_min
, 0)));
182 /* Return whether TYPE should use an overflow infinity distinct from
183 TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to
184 represent a signed overflow during VRP computations. An infinity
185 is distinct from a half-range, which will go from some number to
186 TYPE_{MIN,MAX}_VALUE. */
189 needs_overflow_infinity (const_tree type
)
191 return (INTEGRAL_TYPE_P (type
)
192 && !TYPE_OVERFLOW_WRAPS (type
)
193 /* Integer sub-types never overflow as they are never
194 operands of arithmetic operators. */
195 && !(TREE_TYPE (type
) && TREE_TYPE (type
) != type
));
198 /* Return whether TYPE can support our overflow infinity
199 representation: we use the TREE_OVERFLOW flag, which only exists
200 for constants. If TYPE doesn't support this, we don't optimize
201 cases which would require signed overflow--we drop them to
205 supports_overflow_infinity (const_tree type
)
207 tree min
= vrp_val_min (type
), max
= vrp_val_max (type
);
208 #ifdef ENABLE_CHECKING
209 gcc_assert (needs_overflow_infinity (type
));
211 return (min
!= NULL_TREE
212 && CONSTANT_CLASS_P (min
)
214 && CONSTANT_CLASS_P (max
));
217 /* VAL is the maximum or minimum value of a type. Return a
218 corresponding overflow infinity. */
221 make_overflow_infinity (tree val
)
223 #ifdef ENABLE_CHECKING
224 gcc_assert (val
!= NULL_TREE
&& CONSTANT_CLASS_P (val
));
226 val
= copy_node (val
);
227 TREE_OVERFLOW (val
) = 1;
231 /* Return a negative overflow infinity for TYPE. */
234 negative_overflow_infinity (tree type
)
236 #ifdef ENABLE_CHECKING
237 gcc_assert (supports_overflow_infinity (type
));
239 return make_overflow_infinity (vrp_val_min (type
));
242 /* Return a positive overflow infinity for TYPE. */
245 positive_overflow_infinity (tree type
)
247 #ifdef ENABLE_CHECKING
248 gcc_assert (supports_overflow_infinity (type
));
250 return make_overflow_infinity (vrp_val_max (type
));
253 /* Return whether VAL is a negative overflow infinity. */
256 is_negative_overflow_infinity (const_tree val
)
258 return (needs_overflow_infinity (TREE_TYPE (val
))
259 && CONSTANT_CLASS_P (val
)
260 && TREE_OVERFLOW (val
)
261 && vrp_val_is_min (val
));
264 /* Return whether VAL is a positive overflow infinity. */
267 is_positive_overflow_infinity (const_tree val
)
269 return (needs_overflow_infinity (TREE_TYPE (val
))
270 && CONSTANT_CLASS_P (val
)
271 && TREE_OVERFLOW (val
)
272 && vrp_val_is_max (val
));
275 /* Return whether VAL is a positive or negative overflow infinity. */
278 is_overflow_infinity (const_tree val
)
280 return (needs_overflow_infinity (TREE_TYPE (val
))
281 && CONSTANT_CLASS_P (val
)
282 && TREE_OVERFLOW (val
)
283 && (vrp_val_is_min (val
) || vrp_val_is_max (val
)));
286 /* Return whether STMT has a constant rhs that is_overflow_infinity. */
289 stmt_overflow_infinity (gimple stmt
)
291 if (is_gimple_assign (stmt
)
292 && get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)) ==
294 return is_overflow_infinity (gimple_assign_rhs1 (stmt
));
298 /* If VAL is now an overflow infinity, return VAL. Otherwise, return
299 the same value with TREE_OVERFLOW clear. This can be used to avoid
300 confusing a regular value with an overflow value. */
303 avoid_overflow_infinity (tree val
)
305 if (!is_overflow_infinity (val
))
308 if (vrp_val_is_max (val
))
309 return vrp_val_max (TREE_TYPE (val
));
312 #ifdef ENABLE_CHECKING
313 gcc_assert (vrp_val_is_min (val
));
315 return vrp_val_min (TREE_TYPE (val
));
320 /* Return true if ARG is marked with the nonnull attribute in the
321 current function signature. */
324 nonnull_arg_p (const_tree arg
)
326 tree t
, attrs
, fntype
;
327 unsigned HOST_WIDE_INT arg_num
;
329 gcc_assert (TREE_CODE (arg
) == PARM_DECL
&& POINTER_TYPE_P (TREE_TYPE (arg
)));
331 /* The static chain decl is always non null. */
332 if (arg
== cfun
->static_chain_decl
)
335 fntype
= TREE_TYPE (current_function_decl
);
336 attrs
= lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype
));
338 /* If "nonnull" wasn't specified, we know nothing about the argument. */
339 if (attrs
== NULL_TREE
)
342 /* If "nonnull" applies to all the arguments, then ARG is non-null. */
343 if (TREE_VALUE (attrs
) == NULL_TREE
)
346 /* Get the position number for ARG in the function signature. */
347 for (arg_num
= 1, t
= DECL_ARGUMENTS (current_function_decl
);
349 t
= TREE_CHAIN (t
), arg_num
++)
355 gcc_assert (t
== arg
);
357 /* Now see if ARG_NUM is mentioned in the nonnull list. */
358 for (t
= TREE_VALUE (attrs
); t
; t
= TREE_CHAIN (t
))
360 if (compare_tree_int (TREE_VALUE (t
), arg_num
) == 0)
368 /* Set value range VR to VR_VARYING. */
371 set_value_range_to_varying (value_range_t
*vr
)
373 vr
->type
= VR_VARYING
;
374 vr
->min
= vr
->max
= NULL_TREE
;
376 bitmap_clear (vr
->equiv
);
380 /* Set value range VR to {T, MIN, MAX, EQUIV}. */
383 set_value_range (value_range_t
*vr
, enum value_range_type t
, tree min
,
384 tree max
, bitmap equiv
)
386 #if defined ENABLE_CHECKING
387 /* Check the validity of the range. */
388 if (t
== VR_RANGE
|| t
== VR_ANTI_RANGE
)
392 gcc_assert (min
&& max
);
394 if (INTEGRAL_TYPE_P (TREE_TYPE (min
)) && t
== VR_ANTI_RANGE
)
395 gcc_assert (!vrp_val_is_min (min
) || !vrp_val_is_max (max
));
397 cmp
= compare_values (min
, max
);
398 gcc_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
400 if (needs_overflow_infinity (TREE_TYPE (min
)))
401 gcc_assert (!is_overflow_infinity (min
)
402 || !is_overflow_infinity (max
));
405 if (t
== VR_UNDEFINED
|| t
== VR_VARYING
)
406 gcc_assert (min
== NULL_TREE
&& max
== NULL_TREE
);
408 if (t
== VR_UNDEFINED
|| t
== VR_VARYING
)
409 gcc_assert (equiv
== NULL
|| bitmap_empty_p (equiv
));
416 /* Since updating the equivalence set involves deep copying the
417 bitmaps, only do it if absolutely necessary. */
418 if (vr
->equiv
== NULL
420 vr
->equiv
= BITMAP_ALLOC (NULL
);
422 if (equiv
!= vr
->equiv
)
424 if (equiv
&& !bitmap_empty_p (equiv
))
425 bitmap_copy (vr
->equiv
, equiv
);
427 bitmap_clear (vr
->equiv
);
432 /* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
433 This means adjusting T, MIN and MAX representing the case of a
434 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
435 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
436 In corner cases where MAX+1 or MIN-1 wraps this will fall back
438 This routine exists to ease canonicalization in the case where we
439 extract ranges from var + CST op limit. */
442 set_and_canonicalize_value_range (value_range_t
*vr
, enum value_range_type t
,
443 tree min
, tree max
, bitmap equiv
)
445 /* Nothing to canonicalize for symbolic or unknown or varying ranges. */
447 && t
!= VR_ANTI_RANGE
)
448 || TREE_CODE (min
) != INTEGER_CST
449 || TREE_CODE (max
) != INTEGER_CST
)
451 set_value_range (vr
, t
, min
, max
, equiv
);
455 /* Wrong order for min and max, to swap them and the VR type we need
457 if (tree_int_cst_lt (max
, min
))
459 tree one
= build_int_cst (TREE_TYPE (min
), 1);
460 tree tmp
= int_const_binop (PLUS_EXPR
, max
, one
, 0);
461 max
= int_const_binop (MINUS_EXPR
, min
, one
, 0);
464 /* There's one corner case, if we had [C+1, C] before we now have
465 that again. But this represents an empty value range, so drop
466 to varying in this case. */
467 if (tree_int_cst_lt (max
, min
))
469 set_value_range_to_varying (vr
);
473 t
= t
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
476 /* Anti-ranges that can be represented as ranges should be so. */
477 if (t
== VR_ANTI_RANGE
)
479 bool is_min
= vrp_val_is_min (min
);
480 bool is_max
= vrp_val_is_max (max
);
482 if (is_min
&& is_max
)
484 /* We cannot deal with empty ranges, drop to varying. */
485 set_value_range_to_varying (vr
);
489 /* As a special exception preserve non-null ranges. */
490 && !(TYPE_UNSIGNED (TREE_TYPE (min
))
491 && integer_zerop (max
)))
493 tree one
= build_int_cst (TREE_TYPE (max
), 1);
494 min
= int_const_binop (PLUS_EXPR
, max
, one
, 0);
495 max
= vrp_val_max (TREE_TYPE (max
));
500 tree one
= build_int_cst (TREE_TYPE (min
), 1);
501 max
= int_const_binop (MINUS_EXPR
, min
, one
, 0);
502 min
= vrp_val_min (TREE_TYPE (min
));
507 set_value_range (vr
, t
, min
, max
, equiv
);
510 /* Copy value range FROM into value range TO. */
513 copy_value_range (value_range_t
*to
, value_range_t
*from
)
515 set_value_range (to
, from
->type
, from
->min
, from
->max
, from
->equiv
);
518 /* Set value range VR to a single value. This function is only called
519 with values we get from statements, and exists to clear the
520 TREE_OVERFLOW flag so that we don't think we have an overflow
521 infinity when we shouldn't. */
524 set_value_range_to_value (value_range_t
*vr
, tree val
, bitmap equiv
)
526 gcc_assert (is_gimple_min_invariant (val
));
527 val
= avoid_overflow_infinity (val
);
528 set_value_range (vr
, VR_RANGE
, val
, val
, equiv
);
531 /* Set value range VR to a non-negative range of type TYPE.
532 OVERFLOW_INFINITY indicates whether to use an overflow infinity
533 rather than TYPE_MAX_VALUE; this should be true if we determine
534 that the range is nonnegative based on the assumption that signed
535 overflow does not occur. */
538 set_value_range_to_nonnegative (value_range_t
*vr
, tree type
,
539 bool overflow_infinity
)
543 if (overflow_infinity
&& !supports_overflow_infinity (type
))
545 set_value_range_to_varying (vr
);
549 zero
= build_int_cst (type
, 0);
550 set_value_range (vr
, VR_RANGE
, zero
,
552 ? positive_overflow_infinity (type
)
553 : TYPE_MAX_VALUE (type
)),
557 /* Set value range VR to a non-NULL range of type TYPE. */
560 set_value_range_to_nonnull (value_range_t
*vr
, tree type
)
562 tree zero
= build_int_cst (type
, 0);
563 set_value_range (vr
, VR_ANTI_RANGE
, zero
, zero
, vr
->equiv
);
567 /* Set value range VR to a NULL range of type TYPE. */
570 set_value_range_to_null (value_range_t
*vr
, tree type
)
572 set_value_range_to_value (vr
, build_int_cst (type
, 0), vr
->equiv
);
576 /* Set value range VR to a range of a truthvalue of type TYPE. */
579 set_value_range_to_truthvalue (value_range_t
*vr
, tree type
)
581 if (TYPE_PRECISION (type
) == 1)
582 set_value_range_to_varying (vr
);
584 set_value_range (vr
, VR_RANGE
,
585 build_int_cst (type
, 0), build_int_cst (type
, 1),
590 /* Set value range VR to VR_UNDEFINED. */
593 set_value_range_to_undefined (value_range_t
*vr
)
595 vr
->type
= VR_UNDEFINED
;
596 vr
->min
= vr
->max
= NULL_TREE
;
598 bitmap_clear (vr
->equiv
);
602 /* Return value range information for VAR.
604 If we have no values ranges recorded (ie, VRP is not running), then
605 return NULL. Otherwise create an empty range if none existed for VAR. */
607 static value_range_t
*
608 get_value_range (const_tree var
)
612 unsigned ver
= SSA_NAME_VERSION (var
);
614 /* If we have no recorded ranges, then return NULL. */
622 /* Create a default value range. */
623 vr_value
[ver
] = vr
= XCNEW (value_range_t
);
625 /* Defer allocating the equivalence set. */
628 /* If VAR is a default definition, the variable can take any value
630 sym
= SSA_NAME_VAR (var
);
631 if (SSA_NAME_IS_DEFAULT_DEF (var
))
633 /* Try to use the "nonnull" attribute to create ~[0, 0]
634 anti-ranges for pointers. Note that this is only valid with
635 default definitions of PARM_DECLs. */
636 if (TREE_CODE (sym
) == PARM_DECL
637 && POINTER_TYPE_P (TREE_TYPE (sym
))
638 && nonnull_arg_p (sym
))
639 set_value_range_to_nonnull (vr
, TREE_TYPE (sym
));
641 set_value_range_to_varying (vr
);
647 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
650 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
654 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
656 if (is_overflow_infinity (val1
))
657 return is_overflow_infinity (val2
);
661 /* Return true, if the bitmaps B1 and B2 are equal. */
664 vrp_bitmap_equal_p (const_bitmap b1
, const_bitmap b2
)
668 && bitmap_equal_p (b1
, b2
)));
671 /* Update the value range and equivalence set for variable VAR to
672 NEW_VR. Return true if NEW_VR is different from VAR's previous
675 NOTE: This function assumes that NEW_VR is a temporary value range
676 object created for the sole purpose of updating VAR's range. The
677 storage used by the equivalence set from NEW_VR will be freed by
678 this function. Do not call update_value_range when NEW_VR
679 is the range object associated with another SSA name. */
682 update_value_range (const_tree var
, value_range_t
*new_vr
)
684 value_range_t
*old_vr
;
687 /* Update the value range, if necessary. */
688 old_vr
= get_value_range (var
);
689 is_new
= old_vr
->type
!= new_vr
->type
690 || !vrp_operand_equal_p (old_vr
->min
, new_vr
->min
)
691 || !vrp_operand_equal_p (old_vr
->max
, new_vr
->max
)
692 || !vrp_bitmap_equal_p (old_vr
->equiv
, new_vr
->equiv
);
695 set_value_range (old_vr
, new_vr
->type
, new_vr
->min
, new_vr
->max
,
698 BITMAP_FREE (new_vr
->equiv
);
704 /* Add VAR and VAR's equivalence set to EQUIV. This is the central
705 point where equivalence processing can be turned on/off. */
708 add_equivalence (bitmap
*equiv
, const_tree var
)
710 unsigned ver
= SSA_NAME_VERSION (var
);
711 value_range_t
*vr
= vr_value
[ver
];
714 *equiv
= BITMAP_ALLOC (NULL
);
715 bitmap_set_bit (*equiv
, ver
);
717 bitmap_ior_into (*equiv
, vr
->equiv
);
721 /* Return true if VR is ~[0, 0]. */
724 range_is_nonnull (value_range_t
*vr
)
726 return vr
->type
== VR_ANTI_RANGE
727 && integer_zerop (vr
->min
)
728 && integer_zerop (vr
->max
);
732 /* Return true if VR is [0, 0]. */
735 range_is_null (value_range_t
*vr
)
737 return vr
->type
== VR_RANGE
738 && integer_zerop (vr
->min
)
739 && integer_zerop (vr
->max
);
743 /* Return true if value range VR involves at least one symbol. */
746 symbolic_range_p (value_range_t
*vr
)
748 return (!is_gimple_min_invariant (vr
->min
)
749 || !is_gimple_min_invariant (vr
->max
));
752 /* Return true if value range VR uses an overflow infinity. */
755 overflow_infinity_range_p (value_range_t
*vr
)
757 return (vr
->type
== VR_RANGE
758 && (is_overflow_infinity (vr
->min
)
759 || is_overflow_infinity (vr
->max
)));
762 /* Return false if we can not make a valid comparison based on VR;
763 this will be the case if it uses an overflow infinity and overflow
764 is not undefined (i.e., -fno-strict-overflow is in effect).
765 Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR
766 uses an overflow infinity. */
769 usable_range_p (value_range_t
*vr
, bool *strict_overflow_p
)
771 gcc_assert (vr
->type
== VR_RANGE
);
772 if (is_overflow_infinity (vr
->min
))
774 *strict_overflow_p
= true;
775 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr
->min
)))
778 if (is_overflow_infinity (vr
->max
))
780 *strict_overflow_p
= true;
781 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr
->max
)))
788 /* Like tree_expr_nonnegative_warnv_p, but this function uses value
789 ranges obtained so far. */
792 vrp_expr_computes_nonnegative (tree expr
, bool *strict_overflow_p
)
794 return (tree_expr_nonnegative_warnv_p (expr
, strict_overflow_p
)
795 || (TREE_CODE (expr
) == SSA_NAME
796 && ssa_name_nonnegative_p (expr
)));
799 /* Return true if the result of assignment STMT is know to be non-negative.
800 If the return value is based on the assumption that signed overflow is
801 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
802 *STRICT_OVERFLOW_P.*/
805 gimple_assign_nonnegative_warnv_p (gimple stmt
, bool *strict_overflow_p
)
807 enum tree_code code
= gimple_assign_rhs_code (stmt
);
808 switch (get_gimple_rhs_class (code
))
810 case GIMPLE_UNARY_RHS
:
811 return tree_unary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt
),
812 gimple_expr_type (stmt
),
813 gimple_assign_rhs1 (stmt
),
815 case GIMPLE_BINARY_RHS
:
816 return tree_binary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt
),
817 gimple_expr_type (stmt
),
818 gimple_assign_rhs1 (stmt
),
819 gimple_assign_rhs2 (stmt
),
821 case GIMPLE_SINGLE_RHS
:
822 return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt
),
824 case GIMPLE_INVALID_RHS
:
831 /* Return true if return value of call STMT is know to be non-negative.
832 If the return value is based on the assumption that signed overflow is
833 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
834 *STRICT_OVERFLOW_P.*/
837 gimple_call_nonnegative_warnv_p (gimple stmt
, bool *strict_overflow_p
)
839 tree arg0
= gimple_call_num_args (stmt
) > 0 ?
840 gimple_call_arg (stmt
, 0) : NULL_TREE
;
841 tree arg1
= gimple_call_num_args (stmt
) > 1 ?
842 gimple_call_arg (stmt
, 1) : NULL_TREE
;
844 return tree_call_nonnegative_warnv_p (gimple_expr_type (stmt
),
845 gimple_call_fndecl (stmt
),
851 /* Return true if STMT is know to to compute a non-negative value.
852 If the return value is based on the assumption that signed overflow is
853 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
854 *STRICT_OVERFLOW_P.*/
857 gimple_stmt_nonnegative_warnv_p (gimple stmt
, bool *strict_overflow_p
)
859 switch (gimple_code (stmt
))
862 return gimple_assign_nonnegative_warnv_p (stmt
, strict_overflow_p
);
864 return gimple_call_nonnegative_warnv_p (stmt
, strict_overflow_p
);
870 /* Return true if the result of assignment STMT is know to be non-zero.
871 If the return value is based on the assumption that signed overflow is
872 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
873 *STRICT_OVERFLOW_P.*/
876 gimple_assign_nonzero_warnv_p (gimple stmt
, bool *strict_overflow_p
)
878 enum tree_code code
= gimple_assign_rhs_code (stmt
);
879 switch (get_gimple_rhs_class (code
))
881 case GIMPLE_UNARY_RHS
:
882 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
883 gimple_expr_type (stmt
),
884 gimple_assign_rhs1 (stmt
),
886 case GIMPLE_BINARY_RHS
:
887 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
888 gimple_expr_type (stmt
),
889 gimple_assign_rhs1 (stmt
),
890 gimple_assign_rhs2 (stmt
),
892 case GIMPLE_SINGLE_RHS
:
893 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt
),
895 case GIMPLE_INVALID_RHS
:
902 /* Return true if STMT is know to to compute a non-zero value.
903 If the return value is based on the assumption that signed overflow is
904 undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
905 *STRICT_OVERFLOW_P.*/
908 gimple_stmt_nonzero_warnv_p (gimple stmt
, bool *strict_overflow_p
)
910 switch (gimple_code (stmt
))
913 return gimple_assign_nonzero_warnv_p (stmt
, strict_overflow_p
);
915 return gimple_alloca_call_p (stmt
);
921 /* Like tree_expr_nonzero_warnv_p, but this function uses value ranges
925 vrp_stmt_computes_nonzero (gimple stmt
, bool *strict_overflow_p
)
927 if (gimple_stmt_nonzero_warnv_p (stmt
, strict_overflow_p
))
930 /* If we have an expression of the form &X->a, then the expression
931 is nonnull if X is nonnull. */
932 if (is_gimple_assign (stmt
)
933 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
935 tree expr
= gimple_assign_rhs1 (stmt
);
936 tree base
= get_base_address (TREE_OPERAND (expr
, 0));
938 if (base
!= NULL_TREE
939 && TREE_CODE (base
) == INDIRECT_REF
940 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
942 value_range_t
*vr
= get_value_range (TREE_OPERAND (base
, 0));
943 if (range_is_nonnull (vr
))
951 /* Returns true if EXPR is a valid value (as expected by compare_values) --
952 a gimple invariant, or SSA_NAME +- CST. */
955 valid_value_p (tree expr
)
957 if (TREE_CODE (expr
) == SSA_NAME
)
960 if (TREE_CODE (expr
) == PLUS_EXPR
961 || TREE_CODE (expr
) == MINUS_EXPR
)
962 return (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
963 && TREE_CODE (TREE_OPERAND (expr
, 1)) == INTEGER_CST
);
965 return is_gimple_min_invariant (expr
);
971 -2 if those are incomparable. */
973 operand_less_p (tree val
, tree val2
)
975 /* LT is folded faster than GE and others. Inline the common case. */
976 if (TREE_CODE (val
) == INTEGER_CST
&& TREE_CODE (val2
) == INTEGER_CST
)
978 if (TYPE_UNSIGNED (TREE_TYPE (val
)))
979 return INT_CST_LT_UNSIGNED (val
, val2
);
982 if (INT_CST_LT (val
, val2
))
990 fold_defer_overflow_warnings ();
992 tcmp
= fold_binary_to_constant (LT_EXPR
, boolean_type_node
, val
, val2
);
994 fold_undefer_and_ignore_overflow_warnings ();
997 || TREE_CODE (tcmp
) != INTEGER_CST
)
1000 if (!integer_zerop (tcmp
))
1004 /* val >= val2, not considering overflow infinity. */
1005 if (is_negative_overflow_infinity (val
))
1006 return is_negative_overflow_infinity (val2
) ? 0 : 1;
1007 else if (is_positive_overflow_infinity (val2
))
1008 return is_positive_overflow_infinity (val
) ? 0 : 1;
1013 /* Compare two values VAL1 and VAL2. Return
1015 -2 if VAL1 and VAL2 cannot be compared at compile-time,
1018 +1 if VAL1 > VAL2, and
1021 This is similar to tree_int_cst_compare but supports pointer values
1022 and values that cannot be compared at compile time.
1024 If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to
1025 true if the return value is only valid if we assume that signed
1026 overflow is undefined. */
1029 compare_values_warnv (tree val1
, tree val2
, bool *strict_overflow_p
)
1034 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
1036 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1
))
1037 == POINTER_TYPE_P (TREE_TYPE (val2
)));
1038 /* Convert the two values into the same type. This is needed because
1039 sizetype causes sign extension even for unsigned types. */
1040 val2
= fold_convert (TREE_TYPE (val1
), val2
);
1041 STRIP_USELESS_TYPE_CONVERSION (val2
);
1043 if ((TREE_CODE (val1
) == SSA_NAME
1044 || TREE_CODE (val1
) == PLUS_EXPR
1045 || TREE_CODE (val1
) == MINUS_EXPR
)
1046 && (TREE_CODE (val2
) == SSA_NAME
1047 || TREE_CODE (val2
) == PLUS_EXPR
1048 || TREE_CODE (val2
) == MINUS_EXPR
))
1050 tree n1
, c1
, n2
, c2
;
1051 enum tree_code code1
, code2
;
1053 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
1054 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
1055 same name, return -2. */
1056 if (TREE_CODE (val1
) == SSA_NAME
)
1064 code1
= TREE_CODE (val1
);
1065 n1
= TREE_OPERAND (val1
, 0);
1066 c1
= TREE_OPERAND (val1
, 1);
1067 if (tree_int_cst_sgn (c1
) == -1)
1069 if (is_negative_overflow_infinity (c1
))
1071 c1
= fold_unary_to_constant (NEGATE_EXPR
, TREE_TYPE (c1
), c1
);
1074 code1
= code1
== MINUS_EXPR
? PLUS_EXPR
: MINUS_EXPR
;
1078 if (TREE_CODE (val2
) == SSA_NAME
)
1086 code2
= TREE_CODE (val2
);
1087 n2
= TREE_OPERAND (val2
, 0);
1088 c2
= TREE_OPERAND (val2
, 1);
1089 if (tree_int_cst_sgn (c2
) == -1)
1091 if (is_negative_overflow_infinity (c2
))
1093 c2
= fold_unary_to_constant (NEGATE_EXPR
, TREE_TYPE (c2
), c2
);
1096 code2
= code2
== MINUS_EXPR
? PLUS_EXPR
: MINUS_EXPR
;
1100 /* Both values must use the same name. */
1104 if (code1
== SSA_NAME
1105 && code2
== SSA_NAME
)
1109 /* If overflow is defined we cannot simplify more. */
1110 if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1
)))
1113 if (strict_overflow_p
!= NULL
1114 && (code1
== SSA_NAME
|| !TREE_NO_WARNING (val1
))
1115 && (code2
== SSA_NAME
|| !TREE_NO_WARNING (val2
)))
1116 *strict_overflow_p
= true;
1118 if (code1
== SSA_NAME
)
1120 if (code2
== PLUS_EXPR
)
1121 /* NAME < NAME + CST */
1123 else if (code2
== MINUS_EXPR
)
1124 /* NAME > NAME - CST */
1127 else if (code1
== PLUS_EXPR
)
1129 if (code2
== SSA_NAME
)
1130 /* NAME + CST > NAME */
1132 else if (code2
== PLUS_EXPR
)
1133 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
1134 return compare_values_warnv (c1
, c2
, strict_overflow_p
);
1135 else if (code2
== MINUS_EXPR
)
1136 /* NAME + CST1 > NAME - CST2 */
1139 else if (code1
== MINUS_EXPR
)
1141 if (code2
== SSA_NAME
)
1142 /* NAME - CST < NAME */
1144 else if (code2
== PLUS_EXPR
)
1145 /* NAME - CST1 < NAME + CST2 */
1147 else if (code2
== MINUS_EXPR
)
1148 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
1149 C1 and C2 are swapped in the call to compare_values. */
1150 return compare_values_warnv (c2
, c1
, strict_overflow_p
);
1156 /* We cannot compare non-constants. */
1157 if (!is_gimple_min_invariant (val1
) || !is_gimple_min_invariant (val2
))
1160 if (!POINTER_TYPE_P (TREE_TYPE (val1
)))
1162 /* We cannot compare overflowed values, except for overflow
1164 if (TREE_OVERFLOW (val1
) || TREE_OVERFLOW (val2
))
1166 if (strict_overflow_p
!= NULL
)
1167 *strict_overflow_p
= true;
1168 if (is_negative_overflow_infinity (val1
))
1169 return is_negative_overflow_infinity (val2
) ? 0 : -1;
1170 else if (is_negative_overflow_infinity (val2
))
1172 else if (is_positive_overflow_infinity (val1
))
1173 return is_positive_overflow_infinity (val2
) ? 0 : 1;
1174 else if (is_positive_overflow_infinity (val2
))
1179 return tree_int_cst_compare (val1
, val2
);
1185 /* First see if VAL1 and VAL2 are not the same. */
1186 if (val1
== val2
|| operand_equal_p (val1
, val2
, 0))
1189 /* If VAL1 is a lower address than VAL2, return -1. */
1190 if (operand_less_p (val1
, val2
) == 1)
1193 /* If VAL1 is a higher address than VAL2, return +1. */
1194 if (operand_less_p (val2
, val1
) == 1)
1197 /* If VAL1 is different than VAL2, return +2.
1198 For integer constants we either have already returned -1 or 1
1199 or they are equivalent. We still might succeed in proving
1200 something about non-trivial operands. */
1201 if (TREE_CODE (val1
) != INTEGER_CST
1202 || TREE_CODE (val2
) != INTEGER_CST
)
1204 t
= fold_binary_to_constant (NE_EXPR
, boolean_type_node
, val1
, val2
);
1205 if (t
&& integer_onep (t
))
1213 /* Compare values like compare_values_warnv, but treat comparisons of
1214 nonconstants which rely on undefined overflow as incomparable. */
1217 compare_values (tree val1
, tree val2
)
1223 ret
= compare_values_warnv (val1
, val2
, &sop
);
1225 && (!is_gimple_min_invariant (val1
) || !is_gimple_min_invariant (val2
)))
1231 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
1232 0 if VAL is not inside VR,
1233 -2 if we cannot tell either way.
1235 FIXME, the current semantics of this functions are a bit quirky
1236 when taken in the context of VRP. In here we do not care
1237 about VR's type. If VR is the anti-range ~[3, 5] the call
1238 value_inside_range (4, VR) will return 1.
1240 This is counter-intuitive in a strict sense, but the callers
1241 currently expect this. They are calling the function
1242 merely to determine whether VR->MIN <= VAL <= VR->MAX. The
1243 callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
1246 This also applies to value_ranges_intersect_p and
1247 range_includes_zero_p. The semantics of VR_RANGE and
1248 VR_ANTI_RANGE should be encoded here, but that also means
1249 adapting the users of these functions to the new semantics.
1251 Benchmark compile/20001226-1.c compilation time after changing this
1255 value_inside_range (tree val
, value_range_t
* vr
)
1259 cmp1
= operand_less_p (val
, vr
->min
);
1265 cmp2
= operand_less_p (vr
->max
, val
);
1273 /* Return true if value ranges VR0 and VR1 have a non-empty
1276 Benchmark compile/20001226-1.c compilation time after changing this
1281 value_ranges_intersect_p (value_range_t
*vr0
, value_range_t
*vr1
)
1283 /* The value ranges do not intersect if the maximum of the first range is
1284 less than the minimum of the second range or vice versa.
1285 When those relations are unknown, we can't do any better. */
1286 if (operand_less_p (vr0
->max
, vr1
->min
) != 0)
1288 if (operand_less_p (vr1
->max
, vr0
->min
) != 0)
1294 /* Return true if VR includes the value zero, false otherwise. FIXME,
1295 currently this will return false for an anti-range like ~[-4, 3].
1296 This will be wrong when the semantics of value_inside_range are
1297 modified (currently the users of this function expect these
1301 range_includes_zero_p (value_range_t
*vr
)
1305 gcc_assert (vr
->type
!= VR_UNDEFINED
1306 && vr
->type
!= VR_VARYING
1307 && !symbolic_range_p (vr
));
1309 zero
= build_int_cst (TREE_TYPE (vr
->min
), 0);
1310 return (value_inside_range (zero
, vr
) == 1);
1313 /* Return true if T, an SSA_NAME, is known to be nonnegative. Return
1314 false otherwise or if no value range information is available. */
1317 ssa_name_nonnegative_p (const_tree t
)
1319 value_range_t
*vr
= get_value_range (t
);
1324 /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
1325 which would return a useful value should be encoded as a VR_RANGE. */
1326 if (vr
->type
== VR_RANGE
)
1328 int result
= compare_values (vr
->min
, integer_zero_node
);
1330 return (result
== 0 || result
== 1);
1335 /* Return true if T, an SSA_NAME, is known to be nonzero. Return
1336 false otherwise or if no value range information is available. */
1339 ssa_name_nonzero_p (const_tree t
)
1341 value_range_t
*vr
= get_value_range (t
);
1346 /* A VR_RANGE which does not include zero is a nonzero value. */
1347 if (vr
->type
== VR_RANGE
&& !symbolic_range_p (vr
))
1348 return ! range_includes_zero_p (vr
);
1350 /* A VR_ANTI_RANGE which does include zero is a nonzero value. */
1351 if (vr
->type
== VR_ANTI_RANGE
&& !symbolic_range_p (vr
))
1352 return range_includes_zero_p (vr
);
1357 /* If OP has a value range with a single constant value return that,
1358 otherwise return NULL_TREE. This returns OP itself if OP is a
1362 op_with_constant_singleton_value_range (tree op
)
1366 if (is_gimple_min_invariant (op
))
1369 if (TREE_CODE (op
) != SSA_NAME
)
1372 vr
= get_value_range (op
);
1373 if (vr
->type
== VR_RANGE
1374 && operand_equal_p (vr
->min
, vr
->max
, 0)
1375 && is_gimple_min_invariant (vr
->min
))
1382 /* Extract value range information from an ASSERT_EXPR EXPR and store
1386 extract_range_from_assert (value_range_t
*vr_p
, tree expr
)
1388 tree var
, cond
, limit
, min
, max
, type
;
1389 value_range_t
*var_vr
, *limit_vr
;
1390 enum tree_code cond_code
;
1392 var
= ASSERT_EXPR_VAR (expr
);
1393 cond
= ASSERT_EXPR_COND (expr
);
1395 gcc_assert (COMPARISON_CLASS_P (cond
));
1397 /* Find VAR in the ASSERT_EXPR conditional. */
1398 if (var
== TREE_OPERAND (cond
, 0)
1399 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PLUS_EXPR
1400 || TREE_CODE (TREE_OPERAND (cond
, 0)) == NOP_EXPR
)
1402 /* If the predicate is of the form VAR COMP LIMIT, then we just
1403 take LIMIT from the RHS and use the same comparison code. */
1404 cond_code
= TREE_CODE (cond
);
1405 limit
= TREE_OPERAND (cond
, 1);
1406 cond
= TREE_OPERAND (cond
, 0);
1410 /* If the predicate is of the form LIMIT COMP VAR, then we need
1411 to flip around the comparison code to create the proper range
1413 cond_code
= swap_tree_comparison (TREE_CODE (cond
));
1414 limit
= TREE_OPERAND (cond
, 0);
1415 cond
= TREE_OPERAND (cond
, 1);
1418 limit
= avoid_overflow_infinity (limit
);
1420 type
= TREE_TYPE (limit
);
1421 gcc_assert (limit
!= var
);
1423 /* For pointer arithmetic, we only keep track of pointer equality
1425 if (POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
1427 set_value_range_to_varying (vr_p
);
1431 /* If LIMIT is another SSA name and LIMIT has a range of its own,
1432 try to use LIMIT's range to avoid creating symbolic ranges
1434 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
1436 /* LIMIT's range is only interesting if it has any useful information. */
1438 && (limit_vr
->type
== VR_UNDEFINED
1439 || limit_vr
->type
== VR_VARYING
1440 || symbolic_range_p (limit_vr
)))
1443 /* Initially, the new range has the same set of equivalences of
1444 VAR's range. This will be revised before returning the final
1445 value. Since assertions may be chained via mutually exclusive
1446 predicates, we will need to trim the set of equivalences before
1448 gcc_assert (vr_p
->equiv
== NULL
);
1449 add_equivalence (&vr_p
->equiv
, var
);
1451 /* Extract a new range based on the asserted comparison for VAR and
1452 LIMIT's value range. Notice that if LIMIT has an anti-range, we
1453 will only use it for equality comparisons (EQ_EXPR). For any
1454 other kind of assertion, we cannot derive a range from LIMIT's
1455 anti-range that can be used to describe the new range. For
1456 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
1457 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
1458 no single range for x_2 that could describe LE_EXPR, so we might
1459 as well build the range [b_4, +INF] for it.
1460 One special case we handle is extracting a range from a
1461 range test encoded as (unsigned)var + CST <= limit. */
1462 if (TREE_CODE (cond
) == NOP_EXPR
1463 || TREE_CODE (cond
) == PLUS_EXPR
)
1465 if (TREE_CODE (cond
) == PLUS_EXPR
)
1467 min
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (TREE_OPERAND (cond
, 1)),
1468 TREE_OPERAND (cond
, 1));
1469 max
= int_const_binop (PLUS_EXPR
, limit
, min
, 0);
1470 cond
= TREE_OPERAND (cond
, 0);
1474 min
= build_int_cst (TREE_TYPE (var
), 0);
1478 /* Make sure to not set TREE_OVERFLOW on the final type
1479 conversion. We are willingly interpreting large positive
1480 unsigned values as negative singed values here. */
1481 min
= force_fit_type_double (TREE_TYPE (var
), TREE_INT_CST_LOW (min
),
1482 TREE_INT_CST_HIGH (min
), 0, false);
1483 max
= force_fit_type_double (TREE_TYPE (var
), TREE_INT_CST_LOW (max
),
1484 TREE_INT_CST_HIGH (max
), 0, false);
1486 /* We can transform a max, min range to an anti-range or
1487 vice-versa. Use set_and_canonicalize_value_range which does
1489 if (cond_code
== LE_EXPR
)
1490 set_and_canonicalize_value_range (vr_p
, VR_RANGE
,
1491 min
, max
, vr_p
->equiv
);
1492 else if (cond_code
== GT_EXPR
)
1493 set_and_canonicalize_value_range (vr_p
, VR_ANTI_RANGE
,
1494 min
, max
, vr_p
->equiv
);
1498 else if (cond_code
== EQ_EXPR
)
1500 enum value_range_type range_type
;
1504 range_type
= limit_vr
->type
;
1505 min
= limit_vr
->min
;
1506 max
= limit_vr
->max
;
1510 range_type
= VR_RANGE
;
1515 set_value_range (vr_p
, range_type
, min
, max
, vr_p
->equiv
);
1517 /* When asserting the equality VAR == LIMIT and LIMIT is another
1518 SSA name, the new range will also inherit the equivalence set
1520 if (TREE_CODE (limit
) == SSA_NAME
)
1521 add_equivalence (&vr_p
->equiv
, limit
);
1523 else if (cond_code
== NE_EXPR
)
1525 /* As described above, when LIMIT's range is an anti-range and
1526 this assertion is an inequality (NE_EXPR), then we cannot
1527 derive anything from the anti-range. For instance, if
1528 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
1529 not imply that VAR's range is [0, 0]. So, in the case of
1530 anti-ranges, we just assert the inequality using LIMIT and
1533 If LIMIT_VR is a range, we can only use it to build a new
1534 anti-range if LIMIT_VR is a single-valued range. For
1535 instance, if LIMIT_VR is [0, 1], the predicate
1536 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
1537 Rather, it means that for value 0 VAR should be ~[0, 0]
1538 and for value 1, VAR should be ~[1, 1]. We cannot
1539 represent these ranges.
1541 The only situation in which we can build a valid
1542 anti-range is when LIMIT_VR is a single-valued range
1543 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
1544 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
1546 && limit_vr
->type
== VR_RANGE
1547 && compare_values (limit_vr
->min
, limit_vr
->max
) == 0)
1549 min
= limit_vr
->min
;
1550 max
= limit_vr
->max
;
1554 /* In any other case, we cannot use LIMIT's range to build a
1555 valid anti-range. */
1559 /* If MIN and MAX cover the whole range for their type, then
1560 just use the original LIMIT. */
1561 if (INTEGRAL_TYPE_P (type
)
1562 && vrp_val_is_min (min
)
1563 && vrp_val_is_max (max
))
1566 set_value_range (vr_p
, VR_ANTI_RANGE
, min
, max
, vr_p
->equiv
);
1568 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
1570 min
= TYPE_MIN_VALUE (type
);
1572 if (limit_vr
== NULL
|| limit_vr
->type
== VR_ANTI_RANGE
)
1576 /* If LIMIT_VR is of the form [N1, N2], we need to build the
1577 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
1579 max
= limit_vr
->max
;
1582 /* If the maximum value forces us to be out of bounds, simply punt.
1583 It would be pointless to try and do anything more since this
1584 all should be optimized away above us. */
1585 if ((cond_code
== LT_EXPR
1586 && compare_values (max
, min
) == 0)
1587 || is_overflow_infinity (max
))
1588 set_value_range_to_varying (vr_p
);
1591 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
1592 if (cond_code
== LT_EXPR
)
1594 tree one
= build_int_cst (type
, 1);
1595 max
= fold_build2 (MINUS_EXPR
, type
, max
, one
);
1597 TREE_NO_WARNING (max
) = 1;
1600 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
1603 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
1605 max
= TYPE_MAX_VALUE (type
);
1607 if (limit_vr
== NULL
|| limit_vr
->type
== VR_ANTI_RANGE
)
1611 /* If LIMIT_VR is of the form [N1, N2], we need to build the
1612 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
1614 min
= limit_vr
->min
;
1617 /* If the minimum value forces us to be out of bounds, simply punt.
1618 It would be pointless to try and do anything more since this
1619 all should be optimized away above us. */
1620 if ((cond_code
== GT_EXPR
1621 && compare_values (min
, max
) == 0)
1622 || is_overflow_infinity (min
))
1623 set_value_range_to_varying (vr_p
);
1626 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
1627 if (cond_code
== GT_EXPR
)
1629 tree one
= build_int_cst (type
, 1);
1630 min
= fold_build2 (PLUS_EXPR
, type
, min
, one
);
1632 TREE_NO_WARNING (min
) = 1;
1635 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
1641 /* If VAR already had a known range, it may happen that the new
1642 range we have computed and VAR's range are not compatible. For
1646 p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
1648 p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
1650 While the above comes from a faulty program, it will cause an ICE
1651 later because p_8 and p_6 will have incompatible ranges and at
1652 the same time will be considered equivalent. A similar situation
1656 i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
1658 i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
1660 Again i_6 and i_7 will have incompatible ranges. It would be
1661 pointless to try and do anything with i_7's range because
1662 anything dominated by 'if (i_5 < 5)' will be optimized away.
1663 Note, due to the wa in which simulation proceeds, the statement
1664 i_7 = ASSERT_EXPR <...> we would never be visited because the
1665 conditional 'if (i_5 < 5)' always evaluates to false. However,
1666 this extra check does not hurt and may protect against future
1667 changes to VRP that may get into a situation similar to the
1668 NULL pointer dereference example.
1670 Note that these compatibility tests are only needed when dealing
1671 with ranges or a mix of range and anti-range. If VAR_VR and VR_P
1672 are both anti-ranges, they will always be compatible, because two
1673 anti-ranges will always have a non-empty intersection. */
1675 var_vr
= get_value_range (var
);
1677 /* We may need to make adjustments when VR_P and VAR_VR are numeric
1678 ranges or anti-ranges. */
1679 if (vr_p
->type
== VR_VARYING
1680 || vr_p
->type
== VR_UNDEFINED
1681 || var_vr
->type
== VR_VARYING
1682 || var_vr
->type
== VR_UNDEFINED
1683 || symbolic_range_p (vr_p
)
1684 || symbolic_range_p (var_vr
))
1687 if (var_vr
->type
== VR_RANGE
&& vr_p
->type
== VR_RANGE
)
1689 /* If the two ranges have a non-empty intersection, we can
1690 refine the resulting range. Since the assert expression
1691 creates an equivalency and at the same time it asserts a
1692 predicate, we can take the intersection of the two ranges to
1693 get better precision. */
1694 if (value_ranges_intersect_p (var_vr
, vr_p
))
1696 /* Use the larger of the two minimums. */
1697 if (compare_values (vr_p
->min
, var_vr
->min
) == -1)
1702 /* Use the smaller of the two maximums. */
1703 if (compare_values (vr_p
->max
, var_vr
->max
) == 1)
1708 set_value_range (vr_p
, vr_p
->type
, min
, max
, vr_p
->equiv
);
1712 /* The two ranges do not intersect, set the new range to
1713 VARYING, because we will not be able to do anything
1714 meaningful with it. */
1715 set_value_range_to_varying (vr_p
);
1718 else if ((var_vr
->type
== VR_RANGE
&& vr_p
->type
== VR_ANTI_RANGE
)
1719 || (var_vr
->type
== VR_ANTI_RANGE
&& vr_p
->type
== VR_RANGE
))
1721 /* A range and an anti-range will cancel each other only if
1722 their ends are the same. For instance, in the example above,
1723 p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1724 so VR_P should be set to VR_VARYING. */
1725 if (compare_values (var_vr
->min
, vr_p
->min
) == 0
1726 && compare_values (var_vr
->max
, vr_p
->max
) == 0)
1727 set_value_range_to_varying (vr_p
);
1730 tree min
, max
, anti_min
, anti_max
, real_min
, real_max
;
1733 /* We want to compute the logical AND of the two ranges;
1734 there are three cases to consider.
1737 1. The VR_ANTI_RANGE range is completely within the
1738 VR_RANGE and the endpoints of the ranges are
1739 different. In that case the resulting range
1740 should be whichever range is more precise.
1741 Typically that will be the VR_RANGE.
1743 2. The VR_ANTI_RANGE is completely disjoint from
1744 the VR_RANGE. In this case the resulting range
1745 should be the VR_RANGE.
1747 3. There is some overlap between the VR_ANTI_RANGE
1750 3a. If the high limit of the VR_ANTI_RANGE resides
1751 within the VR_RANGE, then the result is a new
1752 VR_RANGE starting at the high limit of the
1753 VR_ANTI_RANGE + 1 and extending to the
1754 high limit of the original VR_RANGE.
1756 3b. If the low limit of the VR_ANTI_RANGE resides
1757 within the VR_RANGE, then the result is a new
1758 VR_RANGE starting at the low limit of the original
1759 VR_RANGE and extending to the low limit of the
1760 VR_ANTI_RANGE - 1. */
1761 if (vr_p
->type
== VR_ANTI_RANGE
)
1763 anti_min
= vr_p
->min
;
1764 anti_max
= vr_p
->max
;
1765 real_min
= var_vr
->min
;
1766 real_max
= var_vr
->max
;
1770 anti_min
= var_vr
->min
;
1771 anti_max
= var_vr
->max
;
1772 real_min
= vr_p
->min
;
1773 real_max
= vr_p
->max
;
1777 /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1778 not including any endpoints. */
1779 if (compare_values (anti_max
, real_max
) == -1
1780 && compare_values (anti_min
, real_min
) == 1)
1782 /* If the range is covering the whole valid range of
1783 the type keep the anti-range. */
1784 if (!vrp_val_is_min (real_min
)
1785 || !vrp_val_is_max (real_max
))
1786 set_value_range (vr_p
, VR_RANGE
, real_min
,
1787 real_max
, vr_p
->equiv
);
1789 /* Case 2, VR_ANTI_RANGE completely disjoint from
1791 else if (compare_values (anti_min
, real_max
) == 1
1792 || compare_values (anti_max
, real_min
) == -1)
1794 set_value_range (vr_p
, VR_RANGE
, real_min
,
1795 real_max
, vr_p
->equiv
);
1797 /* Case 3a, the anti-range extends into the low
1798 part of the real range. Thus creating a new
1799 low for the real range. */
1800 else if (((cmp
= compare_values (anti_max
, real_min
)) == 1
1802 && compare_values (anti_max
, real_max
) == -1)
1804 gcc_assert (!is_positive_overflow_infinity (anti_max
));
1805 if (needs_overflow_infinity (TREE_TYPE (anti_max
))
1806 && vrp_val_is_max (anti_max
))
1808 if (!supports_overflow_infinity (TREE_TYPE (var_vr
->min
)))
1810 set_value_range_to_varying (vr_p
);
1813 min
= positive_overflow_infinity (TREE_TYPE (var_vr
->min
));
1815 else if (!POINTER_TYPE_P (TREE_TYPE (var_vr
->min
)))
1816 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (var_vr
->min
),
1818 build_int_cst (TREE_TYPE (var_vr
->min
), 1));
1820 min
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (var_vr
->min
),
1821 anti_max
, size_int (1));
1823 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
1825 /* Case 3b, the anti-range extends into the high
1826 part of the real range. Thus creating a new
1827 higher for the real range. */
1828 else if (compare_values (anti_min
, real_min
) == 1
1829 && ((cmp
= compare_values (anti_min
, real_max
)) == -1
1832 gcc_assert (!is_negative_overflow_infinity (anti_min
));
1833 if (needs_overflow_infinity (TREE_TYPE (anti_min
))
1834 && vrp_val_is_min (anti_min
))
1836 if (!supports_overflow_infinity (TREE_TYPE (var_vr
->min
)))
1838 set_value_range_to_varying (vr_p
);
1841 max
= negative_overflow_infinity (TREE_TYPE (var_vr
->min
));
1843 else if (!POINTER_TYPE_P (TREE_TYPE (var_vr
->min
)))
1844 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (var_vr
->min
),
1846 build_int_cst (TREE_TYPE (var_vr
->min
), 1));
1848 max
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (var_vr
->min
),
1852 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
1859 /* Extract range information from SSA name VAR and store it in VR. If
1860 VAR has an interesting range, use it. Otherwise, create the
1861 range [VAR, VAR] and return it. This is useful in situations where
1862 we may have conditionals testing values of VARYING names. For
1869 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1873 extract_range_from_ssa_name (value_range_t
*vr
, tree var
)
1875 value_range_t
*var_vr
= get_value_range (var
);
1877 if (var_vr
->type
!= VR_UNDEFINED
&& var_vr
->type
!= VR_VARYING
)
1878 copy_value_range (vr
, var_vr
);
1880 set_value_range (vr
, VR_RANGE
, var
, var
, NULL
);
1882 add_equivalence (&vr
->equiv
, var
);
1886 /* Wrapper around int_const_binop. If the operation overflows and we
1887 are not using wrapping arithmetic, then adjust the result to be
1888 -INF or +INF depending on CODE, VAL1 and VAL2. This can return
1889 NULL_TREE if we need to use an overflow infinity representation but
1890 the type does not support it. */
1893 vrp_int_const_binop (enum tree_code code
, tree val1
, tree val2
)
1897 res
= int_const_binop (code
, val1
, val2
, 0);
1899 /* If we are not using wrapping arithmetic, operate symbolically
1900 on -INF and +INF. */
1901 if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1
)))
1903 int checkz
= compare_values (res
, val1
);
1904 bool overflow
= false;
1906 /* Ensure that res = val1 [+*] val2 >= val1
1907 or that res = val1 - val2 <= val1. */
1908 if ((code
== PLUS_EXPR
1909 && !(checkz
== 1 || checkz
== 0))
1910 || (code
== MINUS_EXPR
1911 && !(checkz
== 0 || checkz
== -1)))
1915 /* Checking for multiplication overflow is done by dividing the
1916 output of the multiplication by the first input of the
1917 multiplication. If the result of that division operation is
1918 not equal to the second input of the multiplication, then the
1919 multiplication overflowed. */
1920 else if (code
== MULT_EXPR
&& !integer_zerop (val1
))
1922 tree tmp
= int_const_binop (TRUNC_DIV_EXPR
,
1925 int check
= compare_values (tmp
, val2
);
1933 res
= copy_node (res
);
1934 TREE_OVERFLOW (res
) = 1;
1938 else if ((TREE_OVERFLOW (res
)
1939 && !TREE_OVERFLOW (val1
)
1940 && !TREE_OVERFLOW (val2
))
1941 || is_overflow_infinity (val1
)
1942 || is_overflow_infinity (val2
))
1944 /* If the operation overflowed but neither VAL1 nor VAL2 are
1945 overflown, return -INF or +INF depending on the operation
1946 and the combination of signs of the operands. */
1947 int sgn1
= tree_int_cst_sgn (val1
);
1948 int sgn2
= tree_int_cst_sgn (val2
);
1950 if (needs_overflow_infinity (TREE_TYPE (res
))
1951 && !supports_overflow_infinity (TREE_TYPE (res
)))
1954 /* We have to punt on adding infinities of different signs,
1955 since we can't tell what the sign of the result should be.
1956 Likewise for subtracting infinities of the same sign. */
1957 if (((code
== PLUS_EXPR
&& sgn1
!= sgn2
)
1958 || (code
== MINUS_EXPR
&& sgn1
== sgn2
))
1959 && is_overflow_infinity (val1
)
1960 && is_overflow_infinity (val2
))
1963 /* Don't try to handle division or shifting of infinities. */
1964 if ((code
== TRUNC_DIV_EXPR
1965 || code
== FLOOR_DIV_EXPR
1966 || code
== CEIL_DIV_EXPR
1967 || code
== EXACT_DIV_EXPR
1968 || code
== ROUND_DIV_EXPR
1969 || code
== RSHIFT_EXPR
)
1970 && (is_overflow_infinity (val1
)
1971 || is_overflow_infinity (val2
)))
1974 /* Notice that we only need to handle the restricted set of
1975 operations handled by extract_range_from_binary_expr.
1976 Among them, only multiplication, addition and subtraction
1977 can yield overflow without overflown operands because we
1978 are working with integral types only... except in the
1979 case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1980 for division too. */
1982 /* For multiplication, the sign of the overflow is given
1983 by the comparison of the signs of the operands. */
1984 if ((code
== MULT_EXPR
&& sgn1
== sgn2
)
1985 /* For addition, the operands must be of the same sign
1986 to yield an overflow. Its sign is therefore that
1987 of one of the operands, for example the first. For
1988 infinite operands X + -INF is negative, not positive. */
1989 || (code
== PLUS_EXPR
1991 ? !is_negative_overflow_infinity (val2
)
1992 : is_positive_overflow_infinity (val2
)))
1993 /* For subtraction, non-infinite operands must be of
1994 different signs to yield an overflow. Its sign is
1995 therefore that of the first operand or the opposite of
1996 that of the second operand. A first operand of 0 counts
1997 as positive here, for the corner case 0 - (-INF), which
1998 overflows, but must yield +INF. For infinite operands 0
1999 - INF is negative, not positive. */
2000 || (code
== MINUS_EXPR
2002 ? !is_positive_overflow_infinity (val2
)
2003 : is_negative_overflow_infinity (val2
)))
2004 /* We only get in here with positive shift count, so the
2005 overflow direction is the same as the sign of val1.
2006 Actually rshift does not overflow at all, but we only
2007 handle the case of shifting overflowed -INF and +INF. */
2008 || (code
== RSHIFT_EXPR
2010 /* For division, the only case is -INF / -1 = +INF. */
2011 || code
== TRUNC_DIV_EXPR
2012 || code
== FLOOR_DIV_EXPR
2013 || code
== CEIL_DIV_EXPR
2014 || code
== EXACT_DIV_EXPR
2015 || code
== ROUND_DIV_EXPR
)
2016 return (needs_overflow_infinity (TREE_TYPE (res
))
2017 ? positive_overflow_infinity (TREE_TYPE (res
))
2018 : TYPE_MAX_VALUE (TREE_TYPE (res
)));
2020 return (needs_overflow_infinity (TREE_TYPE (res
))
2021 ? negative_overflow_infinity (TREE_TYPE (res
))
2022 : TYPE_MIN_VALUE (TREE_TYPE (res
)));
2029 /* Extract range information from a binary expression EXPR based on
2030 the ranges of each of its operands and the expression code. */
2033 extract_range_from_binary_expr (value_range_t
*vr
,
2034 enum tree_code code
,
2035 tree expr_type
, tree op0
, tree op1
)
2037 enum value_range_type type
;
2040 value_range_t vr0
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
2041 value_range_t vr1
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
2043 /* Not all binary expressions can be applied to ranges in a
2044 meaningful way. Handle only arithmetic operations. */
2045 if (code
!= PLUS_EXPR
2046 && code
!= MINUS_EXPR
2047 && code
!= POINTER_PLUS_EXPR
2048 && code
!= MULT_EXPR
2049 && code
!= TRUNC_DIV_EXPR
2050 && code
!= FLOOR_DIV_EXPR
2051 && code
!= CEIL_DIV_EXPR
2052 && code
!= EXACT_DIV_EXPR
2053 && code
!= ROUND_DIV_EXPR
2054 && code
!= RSHIFT_EXPR
2057 && code
!= BIT_AND_EXPR
2058 && code
!= BIT_IOR_EXPR
2059 && code
!= TRUTH_AND_EXPR
2060 && code
!= TRUTH_OR_EXPR
)
2062 /* We can still do constant propagation here. */
2063 tree const_op0
= op_with_constant_singleton_value_range (op0
);
2064 tree const_op1
= op_with_constant_singleton_value_range (op1
);
2065 if (const_op0
|| const_op1
)
2067 tree tem
= fold_binary (code
, expr_type
,
2068 const_op0
? const_op0
: op0
,
2069 const_op1
? const_op1
: op1
);
2071 && is_gimple_min_invariant (tem
)
2072 && !is_overflow_infinity (tem
))
2074 set_value_range (vr
, VR_RANGE
, tem
, tem
, NULL
);
2078 set_value_range_to_varying (vr
);
2082 /* Get value ranges for each operand. For constant operands, create
2083 a new value range with the operand to simplify processing. */
2084 if (TREE_CODE (op0
) == SSA_NAME
)
2085 vr0
= *(get_value_range (op0
));
2086 else if (is_gimple_min_invariant (op0
))
2087 set_value_range_to_value (&vr0
, op0
, NULL
);
2089 set_value_range_to_varying (&vr0
);
2091 if (TREE_CODE (op1
) == SSA_NAME
)
2092 vr1
= *(get_value_range (op1
));
2093 else if (is_gimple_min_invariant (op1
))
2094 set_value_range_to_value (&vr1
, op1
, NULL
);
2096 set_value_range_to_varying (&vr1
);
2098 /* If either range is UNDEFINED, so is the result. */
2099 if (vr0
.type
== VR_UNDEFINED
|| vr1
.type
== VR_UNDEFINED
)
2101 set_value_range_to_undefined (vr
);
2105 /* The type of the resulting value range defaults to VR0.TYPE. */
2108 /* Refuse to operate on VARYING ranges, ranges of different kinds
2109 and symbolic ranges. As an exception, we allow BIT_AND_EXPR
2110 because we may be able to derive a useful range even if one of
2111 the operands is VR_VARYING or symbolic range. TODO, we may be
2112 able to derive anti-ranges in some cases. */
2113 if (code
!= BIT_AND_EXPR
2114 && code
!= TRUTH_AND_EXPR
2115 && code
!= TRUTH_OR_EXPR
2116 && (vr0
.type
== VR_VARYING
2117 || vr1
.type
== VR_VARYING
2118 || vr0
.type
!= vr1
.type
2119 || symbolic_range_p (&vr0
)
2120 || symbolic_range_p (&vr1
)))
2122 set_value_range_to_varying (vr
);
2126 /* Now evaluate the expression to determine the new range. */
2127 if (POINTER_TYPE_P (expr_type
)
2128 || POINTER_TYPE_P (TREE_TYPE (op0
))
2129 || POINTER_TYPE_P (TREE_TYPE (op1
)))
2131 if (code
== MIN_EXPR
|| code
== MAX_EXPR
)
2133 /* For MIN/MAX expressions with pointers, we only care about
2134 nullness, if both are non null, then the result is nonnull.
2135 If both are null, then the result is null. Otherwise they
2137 if (range_is_nonnull (&vr0
) && range_is_nonnull (&vr1
))
2138 set_value_range_to_nonnull (vr
, expr_type
);
2139 else if (range_is_null (&vr0
) && range_is_null (&vr1
))
2140 set_value_range_to_null (vr
, expr_type
);
2142 set_value_range_to_varying (vr
);
2146 gcc_assert (code
== POINTER_PLUS_EXPR
);
2147 /* For pointer types, we are really only interested in asserting
2148 whether the expression evaluates to non-NULL. */
2149 if (range_is_nonnull (&vr0
) || range_is_nonnull (&vr1
))
2150 set_value_range_to_nonnull (vr
, expr_type
);
2151 else if (range_is_null (&vr0
) && range_is_null (&vr1
))
2152 set_value_range_to_null (vr
, expr_type
);
2154 set_value_range_to_varying (vr
);
2159 /* For integer ranges, apply the operation to each end of the
2160 range and see what we end up with. */
2161 if (code
== TRUTH_AND_EXPR
2162 || code
== TRUTH_OR_EXPR
)
2164 /* If one of the operands is zero, we know that the whole
2165 expression evaluates zero. */
2166 if (code
== TRUTH_AND_EXPR
2167 && ((vr0
.type
== VR_RANGE
2168 && integer_zerop (vr0
.min
)
2169 && integer_zerop (vr0
.max
))
2170 || (vr1
.type
== VR_RANGE
2171 && integer_zerop (vr1
.min
)
2172 && integer_zerop (vr1
.max
))))
2175 min
= max
= build_int_cst (expr_type
, 0);
2177 /* If one of the operands is one, we know that the whole
2178 expression evaluates one. */
2179 else if (code
== TRUTH_OR_EXPR
2180 && ((vr0
.type
== VR_RANGE
2181 && integer_onep (vr0
.min
)
2182 && integer_onep (vr0
.max
))
2183 || (vr1
.type
== VR_RANGE
2184 && integer_onep (vr1
.min
)
2185 && integer_onep (vr1
.max
))))
2188 min
= max
= build_int_cst (expr_type
, 1);
2190 else if (vr0
.type
!= VR_VARYING
2191 && vr1
.type
!= VR_VARYING
2192 && vr0
.type
== vr1
.type
2193 && !symbolic_range_p (&vr0
)
2194 && !overflow_infinity_range_p (&vr0
)
2195 && !symbolic_range_p (&vr1
)
2196 && !overflow_infinity_range_p (&vr1
))
2198 /* Boolean expressions cannot be folded with int_const_binop. */
2199 min
= fold_binary (code
, expr_type
, vr0
.min
, vr1
.min
);
2200 max
= fold_binary (code
, expr_type
, vr0
.max
, vr1
.max
);
2204 /* The result of a TRUTH_*_EXPR is always true or false. */
2205 set_value_range_to_truthvalue (vr
, expr_type
);
2209 else if (code
== PLUS_EXPR
2211 || code
== MAX_EXPR
)
2213 /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
2214 VR_VARYING. It would take more effort to compute a precise
2215 range for such a case. For example, if we have op0 == 1 and
2216 op1 == -1 with their ranges both being ~[0,0], we would have
2217 op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
2218 Note that we are guaranteed to have vr0.type == vr1.type at
2220 if (code
== PLUS_EXPR
&& vr0
.type
== VR_ANTI_RANGE
)
2222 set_value_range_to_varying (vr
);
2226 /* For operations that make the resulting range directly
2227 proportional to the original ranges, apply the operation to
2228 the same end of each range. */
2229 min
= vrp_int_const_binop (code
, vr0
.min
, vr1
.min
);
2230 max
= vrp_int_const_binop (code
, vr0
.max
, vr1
.max
);
2232 else if (code
== MULT_EXPR
2233 || code
== TRUNC_DIV_EXPR
2234 || code
== FLOOR_DIV_EXPR
2235 || code
== CEIL_DIV_EXPR
2236 || code
== EXACT_DIV_EXPR
2237 || code
== ROUND_DIV_EXPR
2238 || code
== RSHIFT_EXPR
)
2244 /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
2245 drop to VR_VARYING. It would take more effort to compute a
2246 precise range for such a case. For example, if we have
2247 op0 == 65536 and op1 == 65536 with their ranges both being
2248 ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
2249 we cannot claim that the product is in ~[0,0]. Note that we
2250 are guaranteed to have vr0.type == vr1.type at this
2252 if (code
== MULT_EXPR
2253 && vr0
.type
== VR_ANTI_RANGE
2254 && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0
)))
2256 set_value_range_to_varying (vr
);
2260 /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
2261 then drop to VR_VARYING. Outside of this range we get undefined
2262 behavior from the shift operation. We cannot even trust
2263 SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
2264 shifts, and the operation at the tree level may be widened. */
2265 if (code
== RSHIFT_EXPR
)
2267 if (vr1
.type
== VR_ANTI_RANGE
2268 || !vrp_expr_computes_nonnegative (op1
, &sop
)
2270 (build_int_cst (TREE_TYPE (vr1
.max
),
2271 TYPE_PRECISION (expr_type
) - 1),
2274 set_value_range_to_varying (vr
);
2279 /* Multiplications and divisions are a bit tricky to handle,
2280 depending on the mix of signs we have in the two ranges, we
2281 need to operate on different values to get the minimum and
2282 maximum values for the new range. One approach is to figure
2283 out all the variations of range combinations and do the
2286 However, this involves several calls to compare_values and it
2287 is pretty convoluted. It's simpler to do the 4 operations
2288 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
2289 MAX1) and then figure the smallest and largest values to form
2292 /* Divisions by zero result in a VARYING value. */
2293 else if (code
!= MULT_EXPR
2294 && (vr0
.type
== VR_ANTI_RANGE
|| range_includes_zero_p (&vr1
)))
2296 set_value_range_to_varying (vr
);
2300 /* Compute the 4 cross operations. */
2302 val
[0] = vrp_int_const_binop (code
, vr0
.min
, vr1
.min
);
2303 if (val
[0] == NULL_TREE
)
2306 if (vr1
.max
== vr1
.min
)
2310 val
[1] = vrp_int_const_binop (code
, vr0
.min
, vr1
.max
);
2311 if (val
[1] == NULL_TREE
)
2315 if (vr0
.max
== vr0
.min
)
2319 val
[2] = vrp_int_const_binop (code
, vr0
.max
, vr1
.min
);
2320 if (val
[2] == NULL_TREE
)
2324 if (vr0
.min
== vr0
.max
|| vr1
.min
== vr1
.max
)
2328 val
[3] = vrp_int_const_binop (code
, vr0
.max
, vr1
.max
);
2329 if (val
[3] == NULL_TREE
)
2335 set_value_range_to_varying (vr
);
2339 /* Set MIN to the minimum of VAL[i] and MAX to the maximum
2343 for (i
= 1; i
< 4; i
++)
2345 if (!is_gimple_min_invariant (min
)
2346 || (TREE_OVERFLOW (min
) && !is_overflow_infinity (min
))
2347 || !is_gimple_min_invariant (max
)
2348 || (TREE_OVERFLOW (max
) && !is_overflow_infinity (max
)))
2353 if (!is_gimple_min_invariant (val
[i
])
2354 || (TREE_OVERFLOW (val
[i
])
2355 && !is_overflow_infinity (val
[i
])))
2357 /* If we found an overflowed value, set MIN and MAX
2358 to it so that we set the resulting range to
2364 if (compare_values (val
[i
], min
) == -1)
2367 if (compare_values (val
[i
], max
) == 1)
2372 else if (code
== MINUS_EXPR
)
2374 /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
2375 VR_VARYING. It would take more effort to compute a precise
2376 range for such a case. For example, if we have op0 == 1 and
2377 op1 == 1 with their ranges both being ~[0,0], we would have
2378 op0 - op1 == 0, so we cannot claim that the difference is in
2379 ~[0,0]. Note that we are guaranteed to have
2380 vr0.type == vr1.type at this point. */
2381 if (vr0
.type
== VR_ANTI_RANGE
)
2383 set_value_range_to_varying (vr
);
2387 /* For MINUS_EXPR, apply the operation to the opposite ends of
2389 min
= vrp_int_const_binop (code
, vr0
.min
, vr1
.max
);
2390 max
= vrp_int_const_binop (code
, vr0
.max
, vr1
.min
);
2392 else if (code
== BIT_AND_EXPR
)
2394 if (vr0
.type
== VR_RANGE
2395 && vr0
.min
== vr0
.max
2396 && TREE_CODE (vr0
.max
) == INTEGER_CST
2397 && !TREE_OVERFLOW (vr0
.max
)
2398 && tree_int_cst_sgn (vr0
.max
) >= 0)
2400 min
= build_int_cst (expr_type
, 0);
2403 else if (vr1
.type
== VR_RANGE
2404 && vr1
.min
== vr1
.max
2405 && TREE_CODE (vr1
.max
) == INTEGER_CST
2406 && !TREE_OVERFLOW (vr1
.max
)
2407 && tree_int_cst_sgn (vr1
.max
) >= 0)
2410 min
= build_int_cst (expr_type
, 0);
2415 set_value_range_to_varying (vr
);
2419 else if (code
== BIT_IOR_EXPR
)
2421 if (vr0
.type
== VR_RANGE
2422 && vr1
.type
== VR_RANGE
2423 && TREE_CODE (vr0
.min
) == INTEGER_CST
2424 && TREE_CODE (vr1
.min
) == INTEGER_CST
2425 && TREE_CODE (vr0
.max
) == INTEGER_CST
2426 && TREE_CODE (vr1
.max
) == INTEGER_CST
2427 && tree_int_cst_sgn (vr0
.min
) >= 0
2428 && tree_int_cst_sgn (vr1
.min
) >= 0)
2430 double_int vr0_max
= tree_to_double_int (vr0
.max
);
2431 double_int vr1_max
= tree_to_double_int (vr1
.max
);
2434 /* Set all bits to the right of the most significant one to 1.
2435 For example, [0, 4] | [4, 4] = [4, 7]. */
2436 ior_max
.low
= vr0_max
.low
| vr1_max
.low
;
2437 ior_max
.high
= vr0_max
.high
| vr1_max
.high
;
2438 if (ior_max
.high
!= 0)
2441 ior_max
.high
|= ((HOST_WIDE_INT
) 1
2442 << floor_log2 (ior_max
.high
)) - 1;
2445 ior_max
.low
|= ((unsigned HOST_WIDE_INT
) 1u
2446 << floor_log2 (ior_max
.low
)) - 1;
2448 /* Both of these endpoints are conservative. */
2449 min
= vrp_int_const_binop (MAX_EXPR
, vr0
.min
, vr1
.min
);
2450 max
= double_int_to_tree (expr_type
, ior_max
);
2454 set_value_range_to_varying (vr
);
2461 /* If either MIN or MAX overflowed, then set the resulting range to
2462 VARYING. But we do accept an overflow infinity
2464 if (min
== NULL_TREE
2465 || !is_gimple_min_invariant (min
)
2466 || (TREE_OVERFLOW (min
) && !is_overflow_infinity (min
))
2468 || !is_gimple_min_invariant (max
)
2469 || (TREE_OVERFLOW (max
) && !is_overflow_infinity (max
)))
2471 set_value_range_to_varying (vr
);
2477 2) [-INF, +-INF(OVF)]
2478 3) [+-INF(OVF), +INF]
2479 4) [+-INF(OVF), +-INF(OVF)]
2480 We learn nothing when we have INF and INF(OVF) on both sides.
2481 Note that we do accept [-INF, -INF] and [+INF, +INF] without
2483 if ((vrp_val_is_min (min
) || is_overflow_infinity (min
))
2484 && (vrp_val_is_max (max
) || is_overflow_infinity (max
)))
2486 set_value_range_to_varying (vr
);
2490 cmp
= compare_values (min
, max
);
2491 if (cmp
== -2 || cmp
== 1)
2493 /* If the new range has its limits swapped around (MIN > MAX),
2494 then the operation caused one of them to wrap around, mark
2495 the new range VARYING. */
2496 set_value_range_to_varying (vr
);
2499 set_value_range (vr
, type
, min
, max
, NULL
);
2503 /* Extract range information from a unary expression EXPR based on
2504 the range of its operand and the expression code. */
2507 extract_range_from_unary_expr (value_range_t
*vr
, enum tree_code code
,
2508 tree type
, tree op0
)
2512 value_range_t vr0
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
2514 /* Refuse to operate on certain unary expressions for which we
2515 cannot easily determine a resulting range. */
2516 if (code
== FIX_TRUNC_EXPR
2517 || code
== FLOAT_EXPR
2518 || code
== BIT_NOT_EXPR
2519 || code
== CONJ_EXPR
)
2521 /* We can still do constant propagation here. */
2522 if ((op0
= op_with_constant_singleton_value_range (op0
)) != NULL_TREE
)
2524 tree tem
= fold_unary (code
, type
, op0
);
2526 && is_gimple_min_invariant (tem
)
2527 && !is_overflow_infinity (tem
))
2529 set_value_range (vr
, VR_RANGE
, tem
, tem
, NULL
);
2533 set_value_range_to_varying (vr
);
2537 /* Get value ranges for the operand. For constant operands, create
2538 a new value range with the operand to simplify processing. */
2539 if (TREE_CODE (op0
) == SSA_NAME
)
2540 vr0
= *(get_value_range (op0
));
2541 else if (is_gimple_min_invariant (op0
))
2542 set_value_range_to_value (&vr0
, op0
, NULL
);
2544 set_value_range_to_varying (&vr0
);
2546 /* If VR0 is UNDEFINED, so is the result. */
2547 if (vr0
.type
== VR_UNDEFINED
)
2549 set_value_range_to_undefined (vr
);
2553 /* Refuse to operate on symbolic ranges, or if neither operand is
2554 a pointer or integral type. */
2555 if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2556 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
2557 || (vr0
.type
!= VR_VARYING
2558 && symbolic_range_p (&vr0
)))
2560 set_value_range_to_varying (vr
);
2564 /* If the expression involves pointers, we are only interested in
2565 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
2566 if (POINTER_TYPE_P (type
) || POINTER_TYPE_P (TREE_TYPE (op0
)))
2571 if (range_is_nonnull (&vr0
)
2572 || (tree_unary_nonzero_warnv_p (code
, type
, op0
, &sop
)
2574 set_value_range_to_nonnull (vr
, type
);
2575 else if (range_is_null (&vr0
))
2576 set_value_range_to_null (vr
, type
);
2578 set_value_range_to_varying (vr
);
2583 /* Handle unary expressions on integer ranges. */
2584 if (CONVERT_EXPR_CODE_P (code
)
2585 && INTEGRAL_TYPE_P (type
)
2586 && INTEGRAL_TYPE_P (TREE_TYPE (op0
)))
2588 tree inner_type
= TREE_TYPE (op0
);
2589 tree outer_type
= type
;
2591 /* Always use base-types here. This is important for the
2592 correct signedness. */
2593 if (TREE_TYPE (inner_type
))
2594 inner_type
= TREE_TYPE (inner_type
);
2595 if (TREE_TYPE (outer_type
))
2596 outer_type
= TREE_TYPE (outer_type
);
2598 /* If VR0 is varying and we increase the type precision, assume
2599 a full range for the following transformation. */
2600 if (vr0
.type
== VR_VARYING
2601 && TYPE_PRECISION (inner_type
) < TYPE_PRECISION (outer_type
))
2603 vr0
.type
= VR_RANGE
;
2604 vr0
.min
= TYPE_MIN_VALUE (inner_type
);
2605 vr0
.max
= TYPE_MAX_VALUE (inner_type
);
2608 /* If VR0 is a constant range or anti-range and the conversion is
2609 not truncating we can convert the min and max values and
2610 canonicalize the resulting range. Otherwise we can do the
2611 conversion if the size of the range is less than what the
2612 precision of the target type can represent and the range is
2613 not an anti-range. */
2614 if ((vr0
.type
== VR_RANGE
2615 || vr0
.type
== VR_ANTI_RANGE
)
2616 && TREE_CODE (vr0
.min
) == INTEGER_CST
2617 && TREE_CODE (vr0
.max
) == INTEGER_CST
2618 && !is_overflow_infinity (vr0
.min
)
2619 && !is_overflow_infinity (vr0
.max
)
2620 && (TYPE_PRECISION (outer_type
) >= TYPE_PRECISION (inner_type
)
2621 || (vr0
.type
== VR_RANGE
2622 && integer_zerop (int_const_binop (RSHIFT_EXPR
,
2623 int_const_binop (MINUS_EXPR
, vr0
.max
, vr0
.min
, 0),
2624 size_int (TYPE_PRECISION (outer_type
)), 0)))))
2626 tree new_min
, new_max
;
2627 new_min
= force_fit_type_double (outer_type
,
2628 TREE_INT_CST_LOW (vr0
.min
),
2629 TREE_INT_CST_HIGH (vr0
.min
), 0, 0);
2630 new_max
= force_fit_type_double (outer_type
,
2631 TREE_INT_CST_LOW (vr0
.max
),
2632 TREE_INT_CST_HIGH (vr0
.max
), 0, 0);
2633 set_and_canonicalize_value_range (vr
, vr0
.type
,
2634 new_min
, new_max
, NULL
);
2638 set_value_range_to_varying (vr
);
2642 /* Conversion of a VR_VARYING value to a wider type can result
2643 in a usable range. So wait until after we've handled conversions
2644 before dropping the result to VR_VARYING if we had a source
2645 operand that is VR_VARYING. */
2646 if (vr0
.type
== VR_VARYING
)
2648 set_value_range_to_varying (vr
);
2652 /* Apply the operation to each end of the range and see what we end
2654 if (code
== NEGATE_EXPR
2655 && !TYPE_UNSIGNED (type
))
2657 /* NEGATE_EXPR flips the range around. We need to treat
2658 TYPE_MIN_VALUE specially. */
2659 if (is_positive_overflow_infinity (vr0
.max
))
2660 min
= negative_overflow_infinity (type
);
2661 else if (is_negative_overflow_infinity (vr0
.max
))
2662 min
= positive_overflow_infinity (type
);
2663 else if (!vrp_val_is_min (vr0
.max
))
2664 min
= fold_unary_to_constant (code
, type
, vr0
.max
);
2665 else if (needs_overflow_infinity (type
))
2667 if (supports_overflow_infinity (type
)
2668 && !is_overflow_infinity (vr0
.min
)
2669 && !vrp_val_is_min (vr0
.min
))
2670 min
= positive_overflow_infinity (type
);
2673 set_value_range_to_varying (vr
);
2678 min
= TYPE_MIN_VALUE (type
);
2680 if (is_positive_overflow_infinity (vr0
.min
))
2681 max
= negative_overflow_infinity (type
);
2682 else if (is_negative_overflow_infinity (vr0
.min
))
2683 max
= positive_overflow_infinity (type
);
2684 else if (!vrp_val_is_min (vr0
.min
))
2685 max
= fold_unary_to_constant (code
, type
, vr0
.min
);
2686 else if (needs_overflow_infinity (type
))
2688 if (supports_overflow_infinity (type
))
2689 max
= positive_overflow_infinity (type
);
2692 set_value_range_to_varying (vr
);
2697 max
= TYPE_MIN_VALUE (type
);
2699 else if (code
== NEGATE_EXPR
2700 && TYPE_UNSIGNED (type
))
2702 if (!range_includes_zero_p (&vr0
))
2704 max
= fold_unary_to_constant (code
, type
, vr0
.min
);
2705 min
= fold_unary_to_constant (code
, type
, vr0
.max
);
2709 if (range_is_null (&vr0
))
2710 set_value_range_to_null (vr
, type
);
2712 set_value_range_to_varying (vr
);
2716 else if (code
== ABS_EXPR
2717 && !TYPE_UNSIGNED (type
))
2719 /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
2721 if (!TYPE_OVERFLOW_UNDEFINED (type
)
2722 && ((vr0
.type
== VR_RANGE
2723 && vrp_val_is_min (vr0
.min
))
2724 || (vr0
.type
== VR_ANTI_RANGE
2725 && !vrp_val_is_min (vr0
.min
)
2726 && !range_includes_zero_p (&vr0
))))
2728 set_value_range_to_varying (vr
);
2732 /* ABS_EXPR may flip the range around, if the original range
2733 included negative values. */
2734 if (is_overflow_infinity (vr0
.min
))
2735 min
= positive_overflow_infinity (type
);
2736 else if (!vrp_val_is_min (vr0
.min
))
2737 min
= fold_unary_to_constant (code
, type
, vr0
.min
);
2738 else if (!needs_overflow_infinity (type
))
2739 min
= TYPE_MAX_VALUE (type
);
2740 else if (supports_overflow_infinity (type
))
2741 min
= positive_overflow_infinity (type
);
2744 set_value_range_to_varying (vr
);
2748 if (is_overflow_infinity (vr0
.max
))
2749 max
= positive_overflow_infinity (type
);
2750 else if (!vrp_val_is_min (vr0
.max
))
2751 max
= fold_unary_to_constant (code
, type
, vr0
.max
);
2752 else if (!needs_overflow_infinity (type
))
2753 max
= TYPE_MAX_VALUE (type
);
2754 else if (supports_overflow_infinity (type
)
2755 /* We shouldn't generate [+INF, +INF] as set_value_range
2756 doesn't like this and ICEs. */
2757 && !is_positive_overflow_infinity (min
))
2758 max
= positive_overflow_infinity (type
);
2761 set_value_range_to_varying (vr
);
2765 cmp
= compare_values (min
, max
);
2767 /* If a VR_ANTI_RANGEs contains zero, then we have
2768 ~[-INF, min(MIN, MAX)]. */
2769 if (vr0
.type
== VR_ANTI_RANGE
)
2771 if (range_includes_zero_p (&vr0
))
2773 /* Take the lower of the two values. */
2777 /* Create ~[-INF, min (abs(MIN), abs(MAX))]
2778 or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
2779 flag_wrapv is set and the original anti-range doesn't include
2780 TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */
2781 if (TYPE_OVERFLOW_WRAPS (type
))
2783 tree type_min_value
= TYPE_MIN_VALUE (type
);
2785 min
= (vr0
.min
!= type_min_value
2786 ? int_const_binop (PLUS_EXPR
, type_min_value
,
2787 integer_one_node
, 0)
2792 if (overflow_infinity_range_p (&vr0
))
2793 min
= negative_overflow_infinity (type
);
2795 min
= TYPE_MIN_VALUE (type
);
2800 /* All else has failed, so create the range [0, INF], even for
2801 flag_wrapv since TYPE_MIN_VALUE is in the original
2803 vr0
.type
= VR_RANGE
;
2804 min
= build_int_cst (type
, 0);
2805 if (needs_overflow_infinity (type
))
2807 if (supports_overflow_infinity (type
))
2808 max
= positive_overflow_infinity (type
);
2811 set_value_range_to_varying (vr
);
2816 max
= TYPE_MAX_VALUE (type
);
2820 /* If the range contains zero then we know that the minimum value in the
2821 range will be zero. */
2822 else if (range_includes_zero_p (&vr0
))
2826 min
= build_int_cst (type
, 0);
2830 /* If the range was reversed, swap MIN and MAX. */
2841 /* Otherwise, operate on each end of the range. */
2842 min
= fold_unary_to_constant (code
, type
, vr0
.min
);
2843 max
= fold_unary_to_constant (code
, type
, vr0
.max
);
2845 if (needs_overflow_infinity (type
))
2847 gcc_assert (code
!= NEGATE_EXPR
&& code
!= ABS_EXPR
);
2849 /* If both sides have overflowed, we don't know
2851 if ((is_overflow_infinity (vr0
.min
)
2852 || TREE_OVERFLOW (min
))
2853 && (is_overflow_infinity (vr0
.max
)
2854 || TREE_OVERFLOW (max
)))
2856 set_value_range_to_varying (vr
);
2860 if (is_overflow_infinity (vr0
.min
))
2862 else if (TREE_OVERFLOW (min
))
2864 if (supports_overflow_infinity (type
))
2865 min
= (tree_int_cst_sgn (min
) >= 0
2866 ? positive_overflow_infinity (TREE_TYPE (min
))
2867 : negative_overflow_infinity (TREE_TYPE (min
)));
2870 set_value_range_to_varying (vr
);
2875 if (is_overflow_infinity (vr0
.max
))
2877 else if (TREE_OVERFLOW (max
))
2879 if (supports_overflow_infinity (type
))
2880 max
= (tree_int_cst_sgn (max
) >= 0
2881 ? positive_overflow_infinity (TREE_TYPE (max
))
2882 : negative_overflow_infinity (TREE_TYPE (max
)));
2885 set_value_range_to_varying (vr
);
2892 cmp
= compare_values (min
, max
);
2893 if (cmp
== -2 || cmp
== 1)
2895 /* If the new range has its limits swapped around (MIN > MAX),
2896 then the operation caused one of them to wrap around, mark
2897 the new range VARYING. */
2898 set_value_range_to_varying (vr
);
2901 set_value_range (vr
, vr0
.type
, min
, max
, NULL
);
2905 /* Extract range information from a conditional expression EXPR based on
2906 the ranges of each of its operands and the expression code. */
2909 extract_range_from_cond_expr (value_range_t
*vr
, tree expr
)
2912 value_range_t vr0
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
2913 value_range_t vr1
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
2915 /* Get value ranges for each operand. For constant operands, create
2916 a new value range with the operand to simplify processing. */
2917 op0
= COND_EXPR_THEN (expr
);
2918 if (TREE_CODE (op0
) == SSA_NAME
)
2919 vr0
= *(get_value_range (op0
));
2920 else if (is_gimple_min_invariant (op0
))
2921 set_value_range_to_value (&vr0
, op0
, NULL
);
2923 set_value_range_to_varying (&vr0
);
2925 op1
= COND_EXPR_ELSE (expr
);
2926 if (TREE_CODE (op1
) == SSA_NAME
)
2927 vr1
= *(get_value_range (op1
));
2928 else if (is_gimple_min_invariant (op1
))
2929 set_value_range_to_value (&vr1
, op1
, NULL
);
2931 set_value_range_to_varying (&vr1
);
2933 /* The resulting value range is the union of the operand ranges */
2934 vrp_meet (&vr0
, &vr1
);
2935 copy_value_range (vr
, &vr0
);
2939 /* Extract range information from a comparison expression EXPR based
2940 on the range of its operand and the expression code. */
2943 extract_range_from_comparison (value_range_t
*vr
, enum tree_code code
,
2944 tree type
, tree op0
, tree op1
)
2949 val
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, false, &sop
,
2952 /* A disadvantage of using a special infinity as an overflow
2953 representation is that we lose the ability to record overflow
2954 when we don't have an infinity. So we have to ignore a result
2955 which relies on overflow. */
2957 if (val
&& !is_overflow_infinity (val
) && !sop
)
2959 /* Since this expression was found on the RHS of an assignment,
2960 its type may be different from _Bool. Convert VAL to EXPR's
2962 val
= fold_convert (type
, val
);
2963 if (is_gimple_min_invariant (val
))
2964 set_value_range_to_value (vr
, val
, vr
->equiv
);
2966 set_value_range (vr
, VR_RANGE
, val
, val
, vr
->equiv
);
2969 /* The result of a comparison is always true or false. */
2970 set_value_range_to_truthvalue (vr
, type
);
2973 /* Try to derive a nonnegative or nonzero range out of STMT relying
2974 primarily on generic routines in fold in conjunction with range data.
2975 Store the result in *VR */
2978 extract_range_basic (value_range_t
*vr
, gimple stmt
)
2981 tree type
= gimple_expr_type (stmt
);
2983 if (INTEGRAL_TYPE_P (type
)
2984 && gimple_stmt_nonnegative_warnv_p (stmt
, &sop
))
2985 set_value_range_to_nonnegative (vr
, type
,
2986 sop
|| stmt_overflow_infinity (stmt
));
2987 else if (vrp_stmt_computes_nonzero (stmt
, &sop
)
2989 set_value_range_to_nonnull (vr
, type
);
2991 set_value_range_to_varying (vr
);
2995 /* Try to compute a useful range out of assignment STMT and store it
2999 extract_range_from_assignment (value_range_t
*vr
, gimple stmt
)
3001 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3003 if (code
== ASSERT_EXPR
)
3004 extract_range_from_assert (vr
, gimple_assign_rhs1 (stmt
));
3005 else if (code
== SSA_NAME
)
3006 extract_range_from_ssa_name (vr
, gimple_assign_rhs1 (stmt
));
3007 else if (TREE_CODE_CLASS (code
) == tcc_binary
3008 || code
== TRUTH_AND_EXPR
3009 || code
== TRUTH_OR_EXPR
3010 || code
== TRUTH_XOR_EXPR
)
3011 extract_range_from_binary_expr (vr
, gimple_assign_rhs_code (stmt
),
3012 gimple_expr_type (stmt
),
3013 gimple_assign_rhs1 (stmt
),
3014 gimple_assign_rhs2 (stmt
));
3015 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
3016 extract_range_from_unary_expr (vr
, gimple_assign_rhs_code (stmt
),
3017 gimple_expr_type (stmt
),
3018 gimple_assign_rhs1 (stmt
));
3019 else if (code
== COND_EXPR
)
3020 extract_range_from_cond_expr (vr
, gimple_assign_rhs1 (stmt
));
3021 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
3022 extract_range_from_comparison (vr
, gimple_assign_rhs_code (stmt
),
3023 gimple_expr_type (stmt
),
3024 gimple_assign_rhs1 (stmt
),
3025 gimple_assign_rhs2 (stmt
));
3026 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
3027 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
3028 set_value_range_to_value (vr
, gimple_assign_rhs1 (stmt
), NULL
);
3030 set_value_range_to_varying (vr
);
3032 if (vr
->type
== VR_VARYING
)
3033 extract_range_basic (vr
, stmt
);
3036 /* Given a range VR, a LOOP and a variable VAR, determine whether it
3037 would be profitable to adjust VR using scalar evolution information
3038 for VAR. If so, update VR with the new limits. */
3041 adjust_range_with_scev (value_range_t
*vr
, struct loop
*loop
,
3042 gimple stmt
, tree var
)
3044 tree init
, step
, chrec
, tmin
, tmax
, min
, max
, type
;
3045 enum ev_direction dir
;
3047 /* TODO. Don't adjust anti-ranges. An anti-range may provide
3048 better opportunities than a regular range, but I'm not sure. */
3049 if (vr
->type
== VR_ANTI_RANGE
)
3052 chrec
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, var
));
3054 /* Like in PR19590, scev can return a constant function. */
3055 if (is_gimple_min_invariant (chrec
))
3057 set_value_range_to_value (vr
, chrec
, vr
->equiv
);
3061 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
3064 init
= initial_condition_in_loop_num (chrec
, loop
->num
);
3065 step
= evolution_part_in_loop_num (chrec
, loop
->num
);
3067 /* If STEP is symbolic, we can't know whether INIT will be the
3068 minimum or maximum value in the range. Also, unless INIT is
3069 a simple expression, compare_values and possibly other functions
3070 in tree-vrp won't be able to handle it. */
3071 if (step
== NULL_TREE
3072 || !is_gimple_min_invariant (step
)
3073 || !valid_value_p (init
))
3076 dir
= scev_direction (chrec
);
3077 if (/* Do not adjust ranges if we do not know whether the iv increases
3078 or decreases, ... */
3079 dir
== EV_DIR_UNKNOWN
3080 /* ... or if it may wrap. */
3081 || scev_probably_wraps_p (init
, step
, stmt
, get_chrec_loop (chrec
),
3085 /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
3086 negative_overflow_infinity and positive_overflow_infinity,
3087 because we have concluded that the loop probably does not
3090 type
= TREE_TYPE (var
);
3091 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
3092 tmin
= lower_bound_in_type (type
, type
);
3094 tmin
= TYPE_MIN_VALUE (type
);
3095 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
3096 tmax
= upper_bound_in_type (type
, type
);
3098 tmax
= TYPE_MAX_VALUE (type
);
3100 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
3105 /* For VARYING or UNDEFINED ranges, just about anything we get
3106 from scalar evolutions should be better. */
3108 if (dir
== EV_DIR_DECREASES
)
3113 /* If we would create an invalid range, then just assume we
3114 know absolutely nothing. This may be over-conservative,
3115 but it's clearly safe, and should happen only in unreachable
3116 parts of code, or for invalid programs. */
3117 if (compare_values (min
, max
) == 1)
3120 set_value_range (vr
, VR_RANGE
, min
, max
, vr
->equiv
);
3122 else if (vr
->type
== VR_RANGE
)
3127 if (dir
== EV_DIR_DECREASES
)
3129 /* INIT is the maximum value. If INIT is lower than VR->MAX
3130 but no smaller than VR->MIN, set VR->MAX to INIT. */
3131 if (compare_values (init
, max
) == -1)
3135 /* If we just created an invalid range with the minimum
3136 greater than the maximum, we fail conservatively.
3137 This should happen only in unreachable
3138 parts of code, or for invalid programs. */
3139 if (compare_values (min
, max
) == 1)
3143 /* According to the loop information, the variable does not
3144 overflow. If we think it does, probably because of an
3145 overflow due to arithmetic on a different INF value,
3147 if (is_negative_overflow_infinity (min
))
3152 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
3153 if (compare_values (init
, min
) == 1)
3157 /* Again, avoid creating invalid range by failing. */
3158 if (compare_values (min
, max
) == 1)
3162 if (is_positive_overflow_infinity (max
))
3166 set_value_range (vr
, VR_RANGE
, min
, max
, vr
->equiv
);
3170 /* Return true if VAR may overflow at STMT. This checks any available
3171 loop information to see if we can determine that VAR does not
3175 vrp_var_may_overflow (tree var
, gimple stmt
)
3178 tree chrec
, init
, step
;
3180 if (current_loops
== NULL
)
3183 l
= loop_containing_stmt (stmt
);
3187 chrec
= instantiate_parameters (l
, analyze_scalar_evolution (l
, var
));
3188 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
3191 init
= initial_condition_in_loop_num (chrec
, l
->num
);
3192 step
= evolution_part_in_loop_num (chrec
, l
->num
);
3194 if (step
== NULL_TREE
3195 || !is_gimple_min_invariant (step
)
3196 || !valid_value_p (init
))
3199 /* If we get here, we know something useful about VAR based on the
3200 loop information. If it wraps, it may overflow. */
3202 if (scev_probably_wraps_p (init
, step
, stmt
, get_chrec_loop (chrec
),
3206 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3208 print_generic_expr (dump_file
, var
, 0);
3209 fprintf (dump_file
, ": loop information indicates does not overflow\n");
3216 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
3218 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
3219 all the values in the ranges.
3221 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
3223 - Return NULL_TREE if it is not always possible to determine the
3224 value of the comparison.
3226 Also set *STRICT_OVERFLOW_P to indicate whether a range with an
3227 overflow infinity was used in the test. */
3231 compare_ranges (enum tree_code comp
, value_range_t
*vr0
, value_range_t
*vr1
,
3232 bool *strict_overflow_p
)
3234 /* VARYING or UNDEFINED ranges cannot be compared. */
3235 if (vr0
->type
== VR_VARYING
3236 || vr0
->type
== VR_UNDEFINED
3237 || vr1
->type
== VR_VARYING
3238 || vr1
->type
== VR_UNDEFINED
)
3241 /* Anti-ranges need to be handled separately. */
3242 if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
3244 /* If both are anti-ranges, then we cannot compute any
3246 if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
3249 /* These comparisons are never statically computable. */
3256 /* Equality can be computed only between a range and an
3257 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
3258 if (vr0
->type
== VR_RANGE
)
3260 /* To simplify processing, make VR0 the anti-range. */
3261 value_range_t
*tmp
= vr0
;
3266 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
3268 if (compare_values_warnv (vr0
->min
, vr1
->min
, strict_overflow_p
) == 0
3269 && compare_values_warnv (vr0
->max
, vr1
->max
, strict_overflow_p
) == 0)
3270 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
3275 if (!usable_range_p (vr0
, strict_overflow_p
)
3276 || !usable_range_p (vr1
, strict_overflow_p
))
3279 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
3280 operands around and change the comparison code. */
3281 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
3284 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
3290 if (comp
== EQ_EXPR
)
3292 /* Equality may only be computed if both ranges represent
3293 exactly one value. */
3294 if (compare_values_warnv (vr0
->min
, vr0
->max
, strict_overflow_p
) == 0
3295 && compare_values_warnv (vr1
->min
, vr1
->max
, strict_overflow_p
) == 0)
3297 int cmp_min
= compare_values_warnv (vr0
->min
, vr1
->min
,
3299 int cmp_max
= compare_values_warnv (vr0
->max
, vr1
->max
,
3301 if (cmp_min
== 0 && cmp_max
== 0)
3302 return boolean_true_node
;
3303 else if (cmp_min
!= -2 && cmp_max
!= -2)
3304 return boolean_false_node
;
3306 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
3307 else if (compare_values_warnv (vr0
->min
, vr1
->max
,
3308 strict_overflow_p
) == 1
3309 || compare_values_warnv (vr1
->min
, vr0
->max
,
3310 strict_overflow_p
) == 1)
3311 return boolean_false_node
;
3315 else if (comp
== NE_EXPR
)
3319 /* If VR0 is completely to the left or completely to the right
3320 of VR1, they are always different. Notice that we need to
3321 make sure that both comparisons yield similar results to
3322 avoid comparing values that cannot be compared at
3324 cmp1
= compare_values_warnv (vr0
->max
, vr1
->min
, strict_overflow_p
);
3325 cmp2
= compare_values_warnv (vr0
->min
, vr1
->max
, strict_overflow_p
);
3326 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
3327 return boolean_true_node
;
3329 /* If VR0 and VR1 represent a single value and are identical,
3331 else if (compare_values_warnv (vr0
->min
, vr0
->max
,
3332 strict_overflow_p
) == 0
3333 && compare_values_warnv (vr1
->min
, vr1
->max
,
3334 strict_overflow_p
) == 0
3335 && compare_values_warnv (vr0
->min
, vr1
->min
,
3336 strict_overflow_p
) == 0
3337 && compare_values_warnv (vr0
->max
, vr1
->max
,
3338 strict_overflow_p
) == 0)
3339 return boolean_false_node
;
3341 /* Otherwise, they may or may not be different. */
3345 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
3349 /* If VR0 is to the left of VR1, return true. */
3350 tst
= compare_values_warnv (vr0
->max
, vr1
->min
, strict_overflow_p
);
3351 if ((comp
== LT_EXPR
&& tst
== -1)
3352 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
3354 if (overflow_infinity_range_p (vr0
)
3355 || overflow_infinity_range_p (vr1
))
3356 *strict_overflow_p
= true;
3357 return boolean_true_node
;
3360 /* If VR0 is to the right of VR1, return false. */
3361 tst
= compare_values_warnv (vr0
->min
, vr1
->max
, strict_overflow_p
);
3362 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
3363 || (comp
== LE_EXPR
&& tst
== 1))
3365 if (overflow_infinity_range_p (vr0
)
3366 || overflow_infinity_range_p (vr1
))
3367 *strict_overflow_p
= true;
3368 return boolean_false_node
;
3371 /* Otherwise, we don't know. */
3379 /* Given a value range VR, a value VAL and a comparison code COMP, return
3380 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
3381 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
3382 always returns false. Return NULL_TREE if it is not always
3383 possible to determine the value of the comparison. Also set
3384 *STRICT_OVERFLOW_P to indicate whether a range with an overflow
3385 infinity was used in the test. */
3388 compare_range_with_value (enum tree_code comp
, value_range_t
*vr
, tree val
,
3389 bool *strict_overflow_p
)
3391 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
3394 /* Anti-ranges need to be handled separately. */
3395 if (vr
->type
== VR_ANTI_RANGE
)
3397 /* For anti-ranges, the only predicates that we can compute at
3398 compile time are equality and inequality. */
3405 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
3406 if (value_inside_range (val
, vr
) == 1)
3407 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
3412 if (!usable_range_p (vr
, strict_overflow_p
))
3415 if (comp
== EQ_EXPR
)
3417 /* EQ_EXPR may only be computed if VR represents exactly
3419 if (compare_values_warnv (vr
->min
, vr
->max
, strict_overflow_p
) == 0)
3421 int cmp
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
3423 return boolean_true_node
;
3424 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
3425 return boolean_false_node
;
3427 else if (compare_values_warnv (val
, vr
->min
, strict_overflow_p
) == -1
3428 || compare_values_warnv (vr
->max
, val
, strict_overflow_p
) == -1)
3429 return boolean_false_node
;
3433 else if (comp
== NE_EXPR
)
3435 /* If VAL is not inside VR, then they are always different. */
3436 if (compare_values_warnv (vr
->max
, val
, strict_overflow_p
) == -1
3437 || compare_values_warnv (vr
->min
, val
, strict_overflow_p
) == 1)
3438 return boolean_true_node
;
3440 /* If VR represents exactly one value equal to VAL, then return
3442 if (compare_values_warnv (vr
->min
, vr
->max
, strict_overflow_p
) == 0
3443 && compare_values_warnv (vr
->min
, val
, strict_overflow_p
) == 0)
3444 return boolean_false_node
;
3446 /* Otherwise, they may or may not be different. */
3449 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
3453 /* If VR is to the left of VAL, return true. */
3454 tst
= compare_values_warnv (vr
->max
, val
, strict_overflow_p
);
3455 if ((comp
== LT_EXPR
&& tst
== -1)
3456 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
3458 if (overflow_infinity_range_p (vr
))
3459 *strict_overflow_p
= true;
3460 return boolean_true_node
;
3463 /* If VR is to the right of VAL, return false. */
3464 tst
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
3465 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
3466 || (comp
== LE_EXPR
&& tst
== 1))
3468 if (overflow_infinity_range_p (vr
))
3469 *strict_overflow_p
= true;
3470 return boolean_false_node
;
3473 /* Otherwise, we don't know. */
3476 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
3480 /* If VR is to the right of VAL, return true. */
3481 tst
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
3482 if ((comp
== GT_EXPR
&& tst
== 1)
3483 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
3485 if (overflow_infinity_range_p (vr
))
3486 *strict_overflow_p
= true;
3487 return boolean_true_node
;
3490 /* If VR is to the left of VAL, return false. */
3491 tst
= compare_values_warnv (vr
->max
, val
, strict_overflow_p
);
3492 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
3493 || (comp
== GE_EXPR
&& tst
== -1))
3495 if (overflow_infinity_range_p (vr
))
3496 *strict_overflow_p
= true;
3497 return boolean_false_node
;
3500 /* Otherwise, we don't know. */
3508 /* Debugging dumps. */
3510 void dump_value_range (FILE *, value_range_t
*);
3511 void debug_value_range (value_range_t
*);
3512 void dump_all_value_ranges (FILE *);
3513 void debug_all_value_ranges (void);
3514 void dump_vr_equiv (FILE *, bitmap
);
3515 void debug_vr_equiv (bitmap
);
3518 /* Dump value range VR to FILE. */
3521 dump_value_range (FILE *file
, value_range_t
*vr
)
3524 fprintf (file
, "[]");
3525 else if (vr
->type
== VR_UNDEFINED
)
3526 fprintf (file
, "UNDEFINED");
3527 else if (vr
->type
== VR_RANGE
|| vr
->type
== VR_ANTI_RANGE
)
3529 tree type
= TREE_TYPE (vr
->min
);
3531 fprintf (file
, "%s[", (vr
->type
== VR_ANTI_RANGE
) ? "~" : "");
3533 if (is_negative_overflow_infinity (vr
->min
))
3534 fprintf (file
, "-INF(OVF)");
3535 else if (INTEGRAL_TYPE_P (type
)
3536 && !TYPE_UNSIGNED (type
)
3537 && vrp_val_is_min (vr
->min
))
3538 fprintf (file
, "-INF");
3540 print_generic_expr (file
, vr
->min
, 0);
3542 fprintf (file
, ", ");
3544 if (is_positive_overflow_infinity (vr
->max
))
3545 fprintf (file
, "+INF(OVF)");
3546 else if (INTEGRAL_TYPE_P (type
)
3547 && vrp_val_is_max (vr
->max
))
3548 fprintf (file
, "+INF");
3550 print_generic_expr (file
, vr
->max
, 0);
3552 fprintf (file
, "]");
3559 fprintf (file
, " EQUIVALENCES: { ");
3561 EXECUTE_IF_SET_IN_BITMAP (vr
->equiv
, 0, i
, bi
)
3563 print_generic_expr (file
, ssa_name (i
), 0);
3564 fprintf (file
, " ");
3568 fprintf (file
, "} (%u elements)", c
);
3571 else if (vr
->type
== VR_VARYING
)
3572 fprintf (file
, "VARYING");
3574 fprintf (file
, "INVALID RANGE");
3578 /* Dump value range VR to stderr. */
3581 debug_value_range (value_range_t
*vr
)
3583 dump_value_range (stderr
, vr
);
3584 fprintf (stderr
, "\n");
3588 /* Dump value ranges of all SSA_NAMEs to FILE. */
3591 dump_all_value_ranges (FILE *file
)
3595 for (i
= 0; i
< num_ssa_names
; i
++)
3599 print_generic_expr (file
, ssa_name (i
), 0);
3600 fprintf (file
, ": ");
3601 dump_value_range (file
, vr_value
[i
]);
3602 fprintf (file
, "\n");
3606 fprintf (file
, "\n");
3610 /* Dump all value ranges to stderr. */
3613 debug_all_value_ranges (void)
3615 dump_all_value_ranges (stderr
);
3619 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
3620 create a new SSA name N and return the assertion assignment
3621 'V = ASSERT_EXPR <V, V OP W>'. */
3624 build_assert_expr_for (tree cond
, tree v
)
3629 gcc_assert (TREE_CODE (v
) == SSA_NAME
);
3630 n
= duplicate_ssa_name (v
, NULL
);
3632 if (COMPARISON_CLASS_P (cond
))
3634 tree a
= build2 (ASSERT_EXPR
, TREE_TYPE (v
), v
, cond
);
3635 assertion
= gimple_build_assign (n
, a
);
3637 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
3639 /* Given !V, build the assignment N = false. */
3640 tree op0
= TREE_OPERAND (cond
, 0);
3641 gcc_assert (op0
== v
);
3642 assertion
= gimple_build_assign (n
, boolean_false_node
);
3644 else if (TREE_CODE (cond
) == SSA_NAME
)
3646 /* Given V, build the assignment N = true. */
3647 gcc_assert (v
== cond
);
3648 assertion
= gimple_build_assign (n
, boolean_true_node
);
3653 SSA_NAME_DEF_STMT (n
) = assertion
;
3655 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
3656 operand of the ASSERT_EXPR. Register the new name and the old one
3657 in the replacement table so that we can fix the SSA web after
3658 adding all the ASSERT_EXPRs. */
3659 register_new_name_mapping (n
, v
);
3665 /* Return false if EXPR is a predicate expression involving floating
3669 fp_predicate (gimple stmt
)
3671 GIMPLE_CHECK (stmt
, GIMPLE_COND
);
3673 return FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)));
3677 /* If the range of values taken by OP can be inferred after STMT executes,
3678 return the comparison code (COMP_CODE_P) and value (VAL_P) that
3679 describes the inferred range. Return true if a range could be
3683 infer_value_range (gimple stmt
, tree op
, enum tree_code
*comp_code_p
, tree
*val_p
)
3686 *comp_code_p
= ERROR_MARK
;
3688 /* Do not attempt to infer anything in names that flow through
3690 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
3693 /* Similarly, don't infer anything from statements that may throw
3695 if (stmt_could_throw_p (stmt
))
3698 /* If STMT is the last statement of a basic block with no
3699 successors, there is no point inferring anything about any of its
3700 operands. We would not be able to find a proper insertion point
3701 for the assertion, anyway. */
3702 if (stmt_ends_bb_p (stmt
) && EDGE_COUNT (gimple_bb (stmt
)->succs
) == 0)
3705 /* We can only assume that a pointer dereference will yield
3706 non-NULL if -fdelete-null-pointer-checks is enabled. */
3707 if (flag_delete_null_pointer_checks
3708 && POINTER_TYPE_P (TREE_TYPE (op
))
3709 && gimple_code (stmt
) != GIMPLE_ASM
)
3711 unsigned num_uses
, num_loads
, num_stores
;
3713 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_loads
, &num_stores
);
3714 if (num_loads
+ num_stores
> 0)
3716 *val_p
= build_int_cst (TREE_TYPE (op
), 0);
3717 *comp_code_p
= NE_EXPR
;
3726 void dump_asserts_for (FILE *, tree
);
3727 void debug_asserts_for (tree
);
3728 void dump_all_asserts (FILE *);
3729 void debug_all_asserts (void);
3731 /* Dump all the registered assertions for NAME to FILE. */
3734 dump_asserts_for (FILE *file
, tree name
)
3738 fprintf (file
, "Assertions to be inserted for ");
3739 print_generic_expr (file
, name
, 0);
3740 fprintf (file
, "\n");
3742 loc
= asserts_for
[SSA_NAME_VERSION (name
)];
3745 fprintf (file
, "\t");
3746 print_gimple_stmt (file
, gsi_stmt (loc
->si
), 0, 0);
3747 fprintf (file
, "\n\tBB #%d", loc
->bb
->index
);
3750 fprintf (file
, "\n\tEDGE %d->%d", loc
->e
->src
->index
,
3751 loc
->e
->dest
->index
);
3752 dump_edge_info (file
, loc
->e
, 0);
3754 fprintf (file
, "\n\tPREDICATE: ");
3755 print_generic_expr (file
, name
, 0);
3756 fprintf (file
, " %s ", tree_code_name
[(int)loc
->comp_code
]);
3757 print_generic_expr (file
, loc
->val
, 0);
3758 fprintf (file
, "\n\n");
3762 fprintf (file
, "\n");
3766 /* Dump all the registered assertions for NAME to stderr. */
3769 debug_asserts_for (tree name
)
3771 dump_asserts_for (stderr
, name
);
3775 /* Dump all the registered assertions for all the names to FILE. */
3778 dump_all_asserts (FILE *file
)
3783 fprintf (file
, "\nASSERT_EXPRs to be inserted\n\n");
3784 EXECUTE_IF_SET_IN_BITMAP (need_assert_for
, 0, i
, bi
)
3785 dump_asserts_for (file
, ssa_name (i
));
3786 fprintf (file
, "\n");
3790 /* Dump all the registered assertions for all the names to stderr. */
3793 debug_all_asserts (void)
3795 dump_all_asserts (stderr
);
3799 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
3800 'EXPR COMP_CODE VAL' at a location that dominates block BB or
3801 E->DEST, then register this location as a possible insertion point
3802 for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
3804 BB, E and SI provide the exact insertion point for the new
3805 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
3806 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
3807 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
3808 must not be NULL. */
3811 register_new_assert_for (tree name
, tree expr
,
3812 enum tree_code comp_code
,
3816 gimple_stmt_iterator si
)
3818 assert_locus_t n
, loc
, last_loc
;
3820 basic_block dest_bb
;
3822 #if defined ENABLE_CHECKING
3823 gcc_assert (bb
== NULL
|| e
== NULL
);
3826 gcc_assert (gimple_code (gsi_stmt (si
)) != GIMPLE_COND
3827 && gimple_code (gsi_stmt (si
)) != GIMPLE_SWITCH
);
3830 /* Never build an assert comparing against an integer constant with
3831 TREE_OVERFLOW set. This confuses our undefined overflow warning
3833 if (TREE_CODE (val
) == INTEGER_CST
3834 && TREE_OVERFLOW (val
))
3835 val
= build_int_cst_wide (TREE_TYPE (val
),
3836 TREE_INT_CST_LOW (val
), TREE_INT_CST_HIGH (val
));
3838 /* The new assertion A will be inserted at BB or E. We need to
3839 determine if the new location is dominated by a previously
3840 registered location for A. If we are doing an edge insertion,
3841 assume that A will be inserted at E->DEST. Note that this is not
3844 If E is a critical edge, it will be split. But even if E is
3845 split, the new block will dominate the same set of blocks that
3848 The reverse, however, is not true, blocks dominated by E->DEST
3849 will not be dominated by the new block created to split E. So,
3850 if the insertion location is on a critical edge, we will not use
3851 the new location to move another assertion previously registered
3852 at a block dominated by E->DEST. */
3853 dest_bb
= (bb
) ? bb
: e
->dest
;
3855 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
3856 VAL at a block dominating DEST_BB, then we don't need to insert a new
3857 one. Similarly, if the same assertion already exists at a block
3858 dominated by DEST_BB and the new location is not on a critical
3859 edge, then update the existing location for the assertion (i.e.,
3860 move the assertion up in the dominance tree).
3862 Note, this is implemented as a simple linked list because there
3863 should not be more than a handful of assertions registered per
3864 name. If this becomes a performance problem, a table hashed by
3865 COMP_CODE and VAL could be implemented. */
3866 loc
= asserts_for
[SSA_NAME_VERSION (name
)];
3871 if (loc
->comp_code
== comp_code
3873 || operand_equal_p (loc
->val
, val
, 0))
3874 && (loc
->expr
== expr
3875 || operand_equal_p (loc
->expr
, expr
, 0)))
3877 /* If the assertion NAME COMP_CODE VAL has already been
3878 registered at a basic block that dominates DEST_BB, then
3879 we don't need to insert the same assertion again. Note
3880 that we don't check strict dominance here to avoid
3881 replicating the same assertion inside the same basic
3882 block more than once (e.g., when a pointer is
3883 dereferenced several times inside a block).
3885 An exception to this rule are edge insertions. If the
3886 new assertion is to be inserted on edge E, then it will
3887 dominate all the other insertions that we may want to
3888 insert in DEST_BB. So, if we are doing an edge
3889 insertion, don't do this dominance check. */
3891 && dominated_by_p (CDI_DOMINATORS
, dest_bb
, loc
->bb
))
3894 /* Otherwise, if E is not a critical edge and DEST_BB
3895 dominates the existing location for the assertion, move
3896 the assertion up in the dominance tree by updating its
3897 location information. */
3898 if ((e
== NULL
|| !EDGE_CRITICAL_P (e
))
3899 && dominated_by_p (CDI_DOMINATORS
, loc
->bb
, dest_bb
))
3908 /* Update the last node of the list and move to the next one. */
3913 /* If we didn't find an assertion already registered for
3914 NAME COMP_CODE VAL, add a new one at the end of the list of
3915 assertions associated with NAME. */
3916 n
= XNEW (struct assert_locus_d
);
3920 n
->comp_code
= comp_code
;
3928 asserts_for
[SSA_NAME_VERSION (name
)] = n
;
3930 bitmap_set_bit (need_assert_for
, SSA_NAME_VERSION (name
));
3933 /* (COND_OP0 COND_CODE COND_OP1) is a predicate which uses NAME.
3934 Extract a suitable test code and value and store them into *CODE_P and
3935 *VAL_P so the predicate is normalized to NAME *CODE_P *VAL_P.
3937 If no extraction was possible, return FALSE, otherwise return TRUE.
3939 If INVERT is true, then we invert the result stored into *CODE_P. */
3942 extract_code_and_val_from_cond_with_ops (tree name
, enum tree_code cond_code
,
3943 tree cond_op0
, tree cond_op1
,
3944 bool invert
, enum tree_code
*code_p
,
3947 enum tree_code comp_code
;
3950 /* Otherwise, we have a comparison of the form NAME COMP VAL
3951 or VAL COMP NAME. */
3952 if (name
== cond_op1
)
3954 /* If the predicate is of the form VAL COMP NAME, flip
3955 COMP around because we need to register NAME as the
3956 first operand in the predicate. */
3957 comp_code
= swap_tree_comparison (cond_code
);
3962 /* The comparison is of the form NAME COMP VAL, so the
3963 comparison code remains unchanged. */
3964 comp_code
= cond_code
;
3968 /* Invert the comparison code as necessary. */
3970 comp_code
= invert_tree_comparison (comp_code
, 0);
3972 /* VRP does not handle float types. */
3973 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val
)))
3976 /* Do not register always-false predicates.
3977 FIXME: this works around a limitation in fold() when dealing with
3978 enumerations. Given 'enum { N1, N2 } x;', fold will not
3979 fold 'if (x > N2)' to 'if (0)'. */
3980 if ((comp_code
== GT_EXPR
|| comp_code
== LT_EXPR
)
3981 && INTEGRAL_TYPE_P (TREE_TYPE (val
)))
3983 tree min
= TYPE_MIN_VALUE (TREE_TYPE (val
));
3984 tree max
= TYPE_MAX_VALUE (TREE_TYPE (val
));
3986 if (comp_code
== GT_EXPR
3988 || compare_values (val
, max
) == 0))
3991 if (comp_code
== LT_EXPR
3993 || compare_values (val
, min
) == 0))
3996 *code_p
= comp_code
;
4001 /* Try to register an edge assertion for SSA name NAME on edge E for
4002 the condition COND contributing to the conditional jump pointed to by BSI.
4003 Invert the condition COND if INVERT is true.
4004 Return true if an assertion for NAME could be registered. */
4007 register_edge_assert_for_2 (tree name
, edge e
, gimple_stmt_iterator bsi
,
4008 enum tree_code cond_code
,
4009 tree cond_op0
, tree cond_op1
, bool invert
)
4012 enum tree_code comp_code
;
4013 bool retval
= false;
4015 if (!extract_code_and_val_from_cond_with_ops (name
, cond_code
,
4018 invert
, &comp_code
, &val
))
4021 /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
4022 reachable from E. */
4023 if (live_on_edge (e
, name
)
4024 && !has_single_use (name
))
4026 register_new_assert_for (name
, name
, comp_code
, val
, NULL
, e
, bsi
);
4030 /* In the case of NAME <= CST and NAME being defined as
4031 NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
4032 and NAME2 <= CST - CST2. We can do the same for NAME > CST.
4033 This catches range and anti-range tests. */
4034 if ((comp_code
== LE_EXPR
4035 || comp_code
== GT_EXPR
)
4036 && TREE_CODE (val
) == INTEGER_CST
4037 && TYPE_UNSIGNED (TREE_TYPE (val
)))
4039 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
4040 tree cst2
= NULL_TREE
, name2
= NULL_TREE
, name3
= NULL_TREE
;
4042 /* Extract CST2 from the (optional) addition. */
4043 if (is_gimple_assign (def_stmt
)
4044 && gimple_assign_rhs_code (def_stmt
) == PLUS_EXPR
)
4046 name2
= gimple_assign_rhs1 (def_stmt
);
4047 cst2
= gimple_assign_rhs2 (def_stmt
);
4048 if (TREE_CODE (name2
) == SSA_NAME
4049 && TREE_CODE (cst2
) == INTEGER_CST
)
4050 def_stmt
= SSA_NAME_DEF_STMT (name2
);
4053 /* Extract NAME2 from the (optional) sign-changing cast. */
4054 if (gimple_assign_cast_p (def_stmt
))
4056 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
))
4057 && ! TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def_stmt
)))
4058 && (TYPE_PRECISION (gimple_expr_type (def_stmt
))
4059 == TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt
)))))
4060 name3
= gimple_assign_rhs1 (def_stmt
);
4063 /* If name3 is used later, create an ASSERT_EXPR for it. */
4064 if (name3
!= NULL_TREE
4065 && TREE_CODE (name3
) == SSA_NAME
4066 && (cst2
== NULL_TREE
4067 || TREE_CODE (cst2
) == INTEGER_CST
)
4068 && INTEGRAL_TYPE_P (TREE_TYPE (name3
))
4069 && live_on_edge (e
, name3
)
4070 && !has_single_use (name3
))
4074 /* Build an expression for the range test. */
4075 tmp
= build1 (NOP_EXPR
, TREE_TYPE (name
), name3
);
4076 if (cst2
!= NULL_TREE
)
4077 tmp
= build2 (PLUS_EXPR
, TREE_TYPE (name
), tmp
, cst2
);
4081 fprintf (dump_file
, "Adding assert for ");
4082 print_generic_expr (dump_file
, name3
, 0);
4083 fprintf (dump_file
, " from ");
4084 print_generic_expr (dump_file
, tmp
, 0);
4085 fprintf (dump_file
, "\n");
4088 register_new_assert_for (name3
, tmp
, comp_code
, val
, NULL
, e
, bsi
);
4093 /* If name2 is used later, create an ASSERT_EXPR for it. */
4094 if (name2
!= NULL_TREE
4095 && TREE_CODE (name2
) == SSA_NAME
4096 && TREE_CODE (cst2
) == INTEGER_CST
4097 && INTEGRAL_TYPE_P (TREE_TYPE (name2
))
4098 && live_on_edge (e
, name2
)
4099 && !has_single_use (name2
))
4103 /* Build an expression for the range test. */
4105 if (TREE_TYPE (name
) != TREE_TYPE (name2
))
4106 tmp
= build1 (NOP_EXPR
, TREE_TYPE (name
), tmp
);
4107 if (cst2
!= NULL_TREE
)
4108 tmp
= build2 (PLUS_EXPR
, TREE_TYPE (name
), tmp
, cst2
);
4112 fprintf (dump_file
, "Adding assert for ");
4113 print_generic_expr (dump_file
, name2
, 0);
4114 fprintf (dump_file
, " from ");
4115 print_generic_expr (dump_file
, tmp
, 0);
4116 fprintf (dump_file
, "\n");
4119 register_new_assert_for (name2
, tmp
, comp_code
, val
, NULL
, e
, bsi
);
4128 /* OP is an operand of a truth value expression which is known to have
4129 a particular value. Register any asserts for OP and for any
4130 operands in OP's defining statement.
4132 If CODE is EQ_EXPR, then we want to register OP is zero (false),
4133 if CODE is NE_EXPR, then we want to register OP is nonzero (true). */
4136 register_edge_assert_for_1 (tree op
, enum tree_code code
,
4137 edge e
, gimple_stmt_iterator bsi
)
4139 bool retval
= false;
4142 enum tree_code rhs_code
;
4144 /* We only care about SSA_NAMEs. */
4145 if (TREE_CODE (op
) != SSA_NAME
)
4148 /* We know that OP will have a zero or nonzero value. If OP is used
4149 more than once go ahead and register an assert for OP.
4151 The FOUND_IN_SUBGRAPH support is not helpful in this situation as
4152 it will always be set for OP (because OP is used in a COND_EXPR in
4154 if (!has_single_use (op
))
4156 val
= build_int_cst (TREE_TYPE (op
), 0);
4157 register_new_assert_for (op
, op
, code
, val
, NULL
, e
, bsi
);
4161 /* Now look at how OP is set. If it's set from a comparison,
4162 a truth operation or some bit operations, then we may be able
4163 to register information about the operands of that assignment. */
4164 op_def
= SSA_NAME_DEF_STMT (op
);
4165 if (gimple_code (op_def
) != GIMPLE_ASSIGN
)
4168 rhs_code
= gimple_assign_rhs_code (op_def
);
4170 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
)
4172 bool invert
= (code
== EQ_EXPR
? true : false);
4173 tree op0
= gimple_assign_rhs1 (op_def
);
4174 tree op1
= gimple_assign_rhs2 (op_def
);
4176 if (TREE_CODE (op0
) == SSA_NAME
)
4177 retval
|= register_edge_assert_for_2 (op0
, e
, bsi
, rhs_code
, op0
, op1
,
4179 if (TREE_CODE (op1
) == SSA_NAME
)
4180 retval
|= register_edge_assert_for_2 (op1
, e
, bsi
, rhs_code
, op0
, op1
,
4183 else if ((code
== NE_EXPR
4184 && (gimple_assign_rhs_code (op_def
) == TRUTH_AND_EXPR
4185 || gimple_assign_rhs_code (op_def
) == BIT_AND_EXPR
))
4187 && (gimple_assign_rhs_code (op_def
) == TRUTH_OR_EXPR
4188 || gimple_assign_rhs_code (op_def
) == BIT_IOR_EXPR
)))
4190 /* Recurse on each operand. */
4191 retval
|= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def
),
4193 retval
|= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def
),
4196 else if (gimple_assign_rhs_code (op_def
) == TRUTH_NOT_EXPR
)
4198 /* Recurse, flipping CODE. */
4199 code
= invert_tree_comparison (code
, false);
4200 retval
|= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def
),
4203 else if (gimple_assign_rhs_code (op_def
) == SSA_NAME
)
4205 /* Recurse through the copy. */
4206 retval
|= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def
),
4209 else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def
)))
4211 /* Recurse through the type conversion. */
4212 retval
|= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def
),
4219 /* Try to register an edge assertion for SSA name NAME on edge E for
4220 the condition COND contributing to the conditional jump pointed to by SI.
4221 Return true if an assertion for NAME could be registered. */
4224 register_edge_assert_for (tree name
, edge e
, gimple_stmt_iterator si
,
4225 enum tree_code cond_code
, tree cond_op0
,
4229 enum tree_code comp_code
;
4230 bool retval
= false;
4231 bool is_else_edge
= (e
->flags
& EDGE_FALSE_VALUE
) != 0;
4233 /* Do not attempt to infer anything in names that flow through
4235 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
))
4238 if (!extract_code_and_val_from_cond_with_ops (name
, cond_code
,
4244 /* Register ASSERT_EXPRs for name. */
4245 retval
|= register_edge_assert_for_2 (name
, e
, si
, cond_code
, cond_op0
,
4246 cond_op1
, is_else_edge
);
4249 /* If COND is effectively an equality test of an SSA_NAME against
4250 the value zero or one, then we may be able to assert values
4251 for SSA_NAMEs which flow into COND. */
4253 /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
4254 statement of NAME we can assert both operands of the TRUTH_AND_EXPR
4255 have nonzero value. */
4256 if (((comp_code
== EQ_EXPR
&& integer_onep (val
))
4257 || (comp_code
== NE_EXPR
&& integer_zerop (val
))))
4259 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
4261 if (is_gimple_assign (def_stmt
)
4262 && (gimple_assign_rhs_code (def_stmt
) == TRUTH_AND_EXPR
4263 || gimple_assign_rhs_code (def_stmt
) == BIT_AND_EXPR
))
4265 tree op0
= gimple_assign_rhs1 (def_stmt
);
4266 tree op1
= gimple_assign_rhs2 (def_stmt
);
4267 retval
|= register_edge_assert_for_1 (op0
, NE_EXPR
, e
, si
);
4268 retval
|= register_edge_assert_for_1 (op1
, NE_EXPR
, e
, si
);
4272 /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
4273 statement of NAME we can assert both operands of the TRUTH_OR_EXPR
4275 if (((comp_code
== EQ_EXPR
&& integer_zerop (val
))
4276 || (comp_code
== NE_EXPR
&& integer_onep (val
))))
4278 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
4280 if (is_gimple_assign (def_stmt
)
4281 && (gimple_assign_rhs_code (def_stmt
) == TRUTH_OR_EXPR
4282 /* For BIT_IOR_EXPR only if NAME == 0 both operands have
4283 necessarily zero value. */
4284 || (comp_code
== EQ_EXPR
4285 && (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
))))
4287 tree op0
= gimple_assign_rhs1 (def_stmt
);
4288 tree op1
= gimple_assign_rhs2 (def_stmt
);
4289 retval
|= register_edge_assert_for_1 (op0
, EQ_EXPR
, e
, si
);
4290 retval
|= register_edge_assert_for_1 (op1
, EQ_EXPR
, e
, si
);
4298 /* Determine whether the outgoing edges of BB should receive an
4299 ASSERT_EXPR for each of the operands of BB's LAST statement.
4300 The last statement of BB must be a COND_EXPR.
4302 If any of the sub-graphs rooted at BB have an interesting use of
4303 the predicate operands, an assert location node is added to the
4304 list of assertions for the corresponding operands. */
4307 find_conditional_asserts (basic_block bb
, gimple last
)
4310 gimple_stmt_iterator bsi
;
4316 need_assert
= false;
4317 bsi
= gsi_for_stmt (last
);
4319 /* Look for uses of the operands in each of the sub-graphs
4320 rooted at BB. We need to check each of the outgoing edges
4321 separately, so that we know what kind of ASSERT_EXPR to
4323 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4328 /* Register the necessary assertions for each operand in the
4329 conditional predicate. */
4330 FOR_EACH_SSA_TREE_OPERAND (op
, last
, iter
, SSA_OP_USE
)
4332 need_assert
|= register_edge_assert_for (op
, e
, bsi
,
4333 gimple_cond_code (last
),
4334 gimple_cond_lhs (last
),
4335 gimple_cond_rhs (last
));
4342 /* Compare two case labels sorting first by the destination label uid
4343 and then by the case value. */
4346 compare_case_labels (const void *p1
, const void *p2
)
4348 const_tree
const case1
= *(const_tree
const*)p1
;
4349 const_tree
const case2
= *(const_tree
const*)p2
;
4350 unsigned int uid1
= DECL_UID (CASE_LABEL (case1
));
4351 unsigned int uid2
= DECL_UID (CASE_LABEL (case2
));
4355 else if (uid1
== uid2
)
4357 /* Make sure the default label is first in a group. */
4358 if (!CASE_LOW (case1
))
4360 else if (!CASE_LOW (case2
))
4363 return tree_int_cst_compare (CASE_LOW (case1
), CASE_LOW (case2
));
4369 /* Determine whether the outgoing edges of BB should receive an
4370 ASSERT_EXPR for each of the operands of BB's LAST statement.
4371 The last statement of BB must be a SWITCH_EXPR.
4373 If any of the sub-graphs rooted at BB have an interesting use of
4374 the predicate operands, an assert location node is added to the
4375 list of assertions for the corresponding operands. */
4378 find_switch_asserts (basic_block bb
, gimple last
)
4381 gimple_stmt_iterator bsi
;
4385 size_t n
= gimple_switch_num_labels(last
);
4386 #if GCC_VERSION >= 4000
4389 /* Work around GCC 3.4 bug (PR 37086). */
4390 volatile unsigned int idx
;
4393 need_assert
= false;
4394 bsi
= gsi_for_stmt (last
);
4395 op
= gimple_switch_index (last
);
4396 if (TREE_CODE (op
) != SSA_NAME
)
4399 /* Build a vector of case labels sorted by destination label. */
4400 vec2
= make_tree_vec (n
);
4401 for (idx
= 0; idx
< n
; ++idx
)
4402 TREE_VEC_ELT (vec2
, idx
) = gimple_switch_label (last
, idx
);
4403 qsort (&TREE_VEC_ELT (vec2
, 0), n
, sizeof (tree
), compare_case_labels
);
4405 for (idx
= 0; idx
< n
; ++idx
)
4408 tree cl
= TREE_VEC_ELT (vec2
, idx
);
4410 min
= CASE_LOW (cl
);
4411 max
= CASE_HIGH (cl
);
4413 /* If there are multiple case labels with the same destination
4414 we need to combine them to a single value range for the edge. */
4416 && CASE_LABEL (cl
) == CASE_LABEL (TREE_VEC_ELT (vec2
, idx
+ 1)))
4418 /* Skip labels until the last of the group. */
4422 && CASE_LABEL (cl
) == CASE_LABEL (TREE_VEC_ELT (vec2
, idx
)));
4425 /* Pick up the maximum of the case label range. */
4426 if (CASE_HIGH (TREE_VEC_ELT (vec2
, idx
)))
4427 max
= CASE_HIGH (TREE_VEC_ELT (vec2
, idx
));
4429 max
= CASE_LOW (TREE_VEC_ELT (vec2
, idx
));
4432 /* Nothing to do if the range includes the default label until we
4433 can register anti-ranges. */
4434 if (min
== NULL_TREE
)
4437 /* Find the edge to register the assert expr on. */
4438 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
4440 /* Register the necessary assertions for the operand in the
4442 need_assert
|= register_edge_assert_for (op
, e
, bsi
,
4443 max
? GE_EXPR
: EQ_EXPR
,
4445 fold_convert (TREE_TYPE (op
),
4449 need_assert
|= register_edge_assert_for (op
, e
, bsi
, LE_EXPR
,
4451 fold_convert (TREE_TYPE (op
),
4460 /* Traverse all the statements in block BB looking for statements that
4461 may generate useful assertions for the SSA names in their operand.
4462 If a statement produces a useful assertion A for name N_i, then the
4463 list of assertions already generated for N_i is scanned to
4464 determine if A is actually needed.
4466 If N_i already had the assertion A at a location dominating the
4467 current location, then nothing needs to be done. Otherwise, the
4468 new location for A is recorded instead.
4470 1- For every statement S in BB, all the variables used by S are
4471 added to bitmap FOUND_IN_SUBGRAPH.
4473 2- If statement S uses an operand N in a way that exposes a known
4474 value range for N, then if N was not already generated by an
4475 ASSERT_EXPR, create a new assert location for N. For instance,
4476 if N is a pointer and the statement dereferences it, we can
4477 assume that N is not NULL.
4479 3- COND_EXPRs are a special case of #2. We can derive range
4480 information from the predicate but need to insert different
4481 ASSERT_EXPRs for each of the sub-graphs rooted at the
4482 conditional block. If the last statement of BB is a conditional
4483 expression of the form 'X op Y', then
4485 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
4487 b) If the conditional is the only entry point to the sub-graph
4488 corresponding to the THEN_CLAUSE, recurse into it. On
4489 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
4490 an ASSERT_EXPR is added for the corresponding variable.
4492 c) Repeat step (b) on the ELSE_CLAUSE.
4494 d) Mark X and Y in FOUND_IN_SUBGRAPH.
4503 In this case, an assertion on the THEN clause is useful to
4504 determine that 'a' is always 9 on that edge. However, an assertion
4505 on the ELSE clause would be unnecessary.
4507 4- If BB does not end in a conditional expression, then we recurse
4508 into BB's dominator children.
4510 At the end of the recursive traversal, every SSA name will have a
4511 list of locations where ASSERT_EXPRs should be added. When a new
4512 location for name N is found, it is registered by calling
4513 register_new_assert_for. That function keeps track of all the
4514 registered assertions to prevent adding unnecessary assertions.
4515 For instance, if a pointer P_4 is dereferenced more than once in a
4516 dominator tree, only the location dominating all the dereference of
4517 P_4 will receive an ASSERT_EXPR.
4519 If this function returns true, then it means that there are names
4520 for which we need to generate ASSERT_EXPRs. Those assertions are
4521 inserted by process_assert_insertions. */
4524 find_assert_locations_1 (basic_block bb
, sbitmap live
)
4526 gimple_stmt_iterator si
;
4531 need_assert
= false;
4532 last
= last_stmt (bb
);
4534 /* If BB's last statement is a conditional statement involving integer
4535 operands, determine if we need to add ASSERT_EXPRs. */
4537 && gimple_code (last
) == GIMPLE_COND
4538 && !fp_predicate (last
)
4539 && !ZERO_SSA_OPERANDS (last
, SSA_OP_USE
))
4540 need_assert
|= find_conditional_asserts (bb
, last
);
4542 /* If BB's last statement is a switch statement involving integer
4543 operands, determine if we need to add ASSERT_EXPRs. */
4545 && gimple_code (last
) == GIMPLE_SWITCH
4546 && !ZERO_SSA_OPERANDS (last
, SSA_OP_USE
))
4547 need_assert
|= find_switch_asserts (bb
, last
);
4549 /* Traverse all the statements in BB marking used names and looking
4550 for statements that may infer assertions for their used operands. */
4551 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
4557 stmt
= gsi_stmt (si
);
4559 /* See if we can derive an assertion for any of STMT's operands. */
4560 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
4563 enum tree_code comp_code
;
4565 /* Mark OP in our live bitmap. */
4566 SET_BIT (live
, SSA_NAME_VERSION (op
));
4568 /* If OP is used in such a way that we can infer a value
4569 range for it, and we don't find a previous assertion for
4570 it, create a new assertion location node for OP. */
4571 if (infer_value_range (stmt
, op
, &comp_code
, &value
))
4573 /* If we are able to infer a nonzero value range for OP,
4574 then walk backwards through the use-def chain to see if OP
4575 was set via a typecast.
4577 If so, then we can also infer a nonzero value range
4578 for the operand of the NOP_EXPR. */
4579 if (comp_code
== NE_EXPR
&& integer_zerop (value
))
4582 gimple def_stmt
= SSA_NAME_DEF_STMT (t
);
4584 while (is_gimple_assign (def_stmt
)
4585 && gimple_assign_rhs_code (def_stmt
) == NOP_EXPR
4587 (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
4589 (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))))
4591 t
= gimple_assign_rhs1 (def_stmt
);
4592 def_stmt
= SSA_NAME_DEF_STMT (t
);
4594 /* Note we want to register the assert for the
4595 operand of the NOP_EXPR after SI, not after the
4597 if (! has_single_use (t
))
4599 register_new_assert_for (t
, t
, comp_code
, value
,
4606 /* If OP is used only once, namely in this STMT, don't
4607 bother creating an ASSERT_EXPR for it. Such an
4608 ASSERT_EXPR would do nothing but increase compile time. */
4609 if (!has_single_use (op
))
4611 register_new_assert_for (op
, op
, comp_code
, value
,
4619 /* Traverse all PHI nodes in BB marking used operands. */
4620 for (si
= gsi_start_phis (bb
); !gsi_end_p(si
); gsi_next (&si
))
4622 use_operand_p arg_p
;
4624 phi
= gsi_stmt (si
);
4626 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_USE
)
4628 tree arg
= USE_FROM_PTR (arg_p
);
4629 if (TREE_CODE (arg
) == SSA_NAME
)
4630 SET_BIT (live
, SSA_NAME_VERSION (arg
));
4637 /* Do an RPO walk over the function computing SSA name liveness
4638 on-the-fly and deciding on assert expressions to insert.
4639 Returns true if there are assert expressions to be inserted. */
4642 find_assert_locations (void)
4644 int *rpo
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
4645 int *bb_rpo
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
4646 int *last_rpo
= XCNEWVEC (int, last_basic_block
+ NUM_FIXED_BLOCKS
);
4650 live
= XCNEWVEC (sbitmap
, last_basic_block
+ NUM_FIXED_BLOCKS
);
4651 rpo_cnt
= pre_and_rev_post_order_compute (NULL
, rpo
, false);
4652 for (i
= 0; i
< rpo_cnt
; ++i
)
4655 need_asserts
= false;
4656 for (i
= rpo_cnt
-1; i
>= 0; --i
)
4658 basic_block bb
= BASIC_BLOCK (rpo
[i
]);
4664 live
[rpo
[i
]] = sbitmap_alloc (num_ssa_names
);
4665 sbitmap_zero (live
[rpo
[i
]]);
4668 /* Process BB and update the live information with uses in
4670 need_asserts
|= find_assert_locations_1 (bb
, live
[rpo
[i
]]);
4672 /* Merge liveness into the predecessor blocks and free it. */
4673 if (!sbitmap_empty_p (live
[rpo
[i
]]))
4676 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4678 int pred
= e
->src
->index
;
4679 if (e
->flags
& EDGE_DFS_BACK
)
4684 live
[pred
] = sbitmap_alloc (num_ssa_names
);
4685 sbitmap_zero (live
[pred
]);
4687 sbitmap_a_or_b (live
[pred
], live
[pred
], live
[rpo
[i
]]);
4689 if (bb_rpo
[pred
] < pred_rpo
)
4690 pred_rpo
= bb_rpo
[pred
];
4693 /* Record the RPO number of the last visited block that needs
4694 live information from this block. */
4695 last_rpo
[rpo
[i
]] = pred_rpo
;
4699 sbitmap_free (live
[rpo
[i
]]);
4700 live
[rpo
[i
]] = NULL
;
4703 /* We can free all successors live bitmaps if all their
4704 predecessors have been visited already. */
4705 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4706 if (last_rpo
[e
->dest
->index
] == i
4707 && live
[e
->dest
->index
])
4709 sbitmap_free (live
[e
->dest
->index
]);
4710 live
[e
->dest
->index
] = NULL
;
4715 XDELETEVEC (bb_rpo
);
4716 XDELETEVEC (last_rpo
);
4717 for (i
= 0; i
< last_basic_block
+ NUM_FIXED_BLOCKS
; ++i
)
4719 sbitmap_free (live
[i
]);
4722 return need_asserts
;
4725 /* Create an ASSERT_EXPR for NAME and insert it in the location
4726 indicated by LOC. Return true if we made any edge insertions. */
4729 process_assert_insertions_for (tree name
, assert_locus_t loc
)
4731 /* Build the comparison expression NAME_i COMP_CODE VAL. */
4738 cond
= build2 (loc
->comp_code
, boolean_type_node
, loc
->expr
, loc
->val
);
4739 assert_stmt
= build_assert_expr_for (cond
, name
);
4742 /* We have been asked to insert the assertion on an edge. This
4743 is used only by COND_EXPR and SWITCH_EXPR assertions. */
4744 #if defined ENABLE_CHECKING
4745 gcc_assert (gimple_code (gsi_stmt (loc
->si
)) == GIMPLE_COND
4746 || gimple_code (gsi_stmt (loc
->si
)) == GIMPLE_SWITCH
);
4749 gsi_insert_on_edge (loc
->e
, assert_stmt
);
4753 /* Otherwise, we can insert right after LOC->SI iff the
4754 statement must not be the last statement in the block. */
4755 stmt
= gsi_stmt (loc
->si
);
4756 if (!stmt_ends_bb_p (stmt
))
4758 gsi_insert_after (&loc
->si
, assert_stmt
, GSI_SAME_STMT
);
4762 /* If STMT must be the last statement in BB, we can only insert new
4763 assertions on the non-abnormal edge out of BB. Note that since
4764 STMT is not control flow, there may only be one non-abnormal edge
4766 FOR_EACH_EDGE (e
, ei
, loc
->bb
->succs
)
4767 if (!(e
->flags
& EDGE_ABNORMAL
))
4769 gsi_insert_on_edge (e
, assert_stmt
);
4777 /* Process all the insertions registered for every name N_i registered
4778 in NEED_ASSERT_FOR. The list of assertions to be inserted are
4779 found in ASSERTS_FOR[i]. */
4782 process_assert_insertions (void)
4786 bool update_edges_p
= false;
4787 int num_asserts
= 0;
4789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4790 dump_all_asserts (dump_file
);
4792 EXECUTE_IF_SET_IN_BITMAP (need_assert_for
, 0, i
, bi
)
4794 assert_locus_t loc
= asserts_for
[i
];
4799 assert_locus_t next
= loc
->next
;
4800 update_edges_p
|= process_assert_insertions_for (ssa_name (i
), loc
);
4808 gsi_commit_edge_inserts ();
4810 statistics_counter_event (cfun
, "Number of ASSERT_EXPR expressions inserted",
4815 /* Traverse the flowgraph looking for conditional jumps to insert range
4816 expressions. These range expressions are meant to provide information
4817 to optimizations that need to reason in terms of value ranges. They
4818 will not be expanded into RTL. For instance, given:
4827 this pass will transform the code into:
4833 x = ASSERT_EXPR <x, x < y>
4838 y = ASSERT_EXPR <y, x <= y>
4842 The idea is that once copy and constant propagation have run, other
4843 optimizations will be able to determine what ranges of values can 'x'
4844 take in different paths of the code, simply by checking the reaching
4845 definition of 'x'. */
4848 insert_range_assertions (void)
4850 need_assert_for
= BITMAP_ALLOC (NULL
);
4851 asserts_for
= XCNEWVEC (assert_locus_t
, num_ssa_names
);
4853 calculate_dominance_info (CDI_DOMINATORS
);
4855 if (find_assert_locations ())
4857 process_assert_insertions ();
4858 update_ssa (TODO_update_ssa_no_phi
);
4861 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4863 fprintf (dump_file
, "\nSSA form after inserting ASSERT_EXPRs\n");
4864 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
4868 BITMAP_FREE (need_assert_for
);
4871 /* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible arrays
4872 and "struct" hacks. If VRP can determine that the
4873 array subscript is a constant, check if it is outside valid
4874 range. If the array subscript is a RANGE, warn if it is
4875 non-overlapping with valid range.
4876 IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR. */
4879 check_array_ref (tree ref
, const location_t
*location
, bool ignore_off_by_one
)
4881 value_range_t
* vr
= NULL
;
4882 tree low_sub
, up_sub
;
4883 tree low_bound
, up_bound
= array_ref_up_bound (ref
);
4885 low_sub
= up_sub
= TREE_OPERAND (ref
, 1);
4887 if (!up_bound
|| TREE_NO_WARNING (ref
)
4888 || TREE_CODE (up_bound
) != INTEGER_CST
4889 /* Can not check flexible arrays. */
4890 || (TYPE_SIZE (TREE_TYPE (ref
)) == NULL_TREE
4891 && TYPE_DOMAIN (TREE_TYPE (ref
)) != NULL_TREE
4892 && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref
))) == NULL_TREE
)
4893 /* Accesses after the end of arrays of size 0 (gcc
4894 extension) and 1 are likely intentional ("struct
4896 || compare_tree_int (up_bound
, 1) <= 0)
4899 low_bound
= array_ref_low_bound (ref
);
4901 if (TREE_CODE (low_sub
) == SSA_NAME
)
4903 vr
= get_value_range (low_sub
);
4904 if (vr
->type
== VR_RANGE
|| vr
->type
== VR_ANTI_RANGE
)
4906 low_sub
= vr
->type
== VR_RANGE
? vr
->max
: vr
->min
;
4907 up_sub
= vr
->type
== VR_RANGE
? vr
->min
: vr
->max
;
4911 if (vr
&& vr
->type
== VR_ANTI_RANGE
)
4913 if (TREE_CODE (up_sub
) == INTEGER_CST
4914 && tree_int_cst_lt (up_bound
, up_sub
)
4915 && TREE_CODE (low_sub
) == INTEGER_CST
4916 && tree_int_cst_lt (low_sub
, low_bound
))
4918 warning (OPT_Warray_bounds
,
4919 "%Harray subscript is outside array bounds", location
);
4920 TREE_NO_WARNING (ref
) = 1;
4923 else if (TREE_CODE (up_sub
) == INTEGER_CST
4924 && tree_int_cst_lt (up_bound
, up_sub
)
4925 && !tree_int_cst_equal (up_bound
, up_sub
)
4926 && (!ignore_off_by_one
4927 || !tree_int_cst_equal (int_const_binop (PLUS_EXPR
,
4933 warning (OPT_Warray_bounds
, "%Harray subscript is above array bounds",
4935 TREE_NO_WARNING (ref
) = 1;
4937 else if (TREE_CODE (low_sub
) == INTEGER_CST
4938 && tree_int_cst_lt (low_sub
, low_bound
))
4940 warning (OPT_Warray_bounds
, "%Harray subscript is below array bounds",
4942 TREE_NO_WARNING (ref
) = 1;
4946 /* Searches if the expr T, located at LOCATION computes
4947 address of an ARRAY_REF, and call check_array_ref on it. */
4950 search_for_addr_array(tree t
, const location_t
*location
)
4952 while (TREE_CODE (t
) == SSA_NAME
)
4954 gimple g
= SSA_NAME_DEF_STMT (t
);
4956 if (gimple_code (g
) != GIMPLE_ASSIGN
)
4959 if (get_gimple_rhs_class (gimple_assign_rhs_code (g
)) !=
4963 t
= gimple_assign_rhs1 (g
);
4967 /* We are only interested in addresses of ARRAY_REF's. */
4968 if (TREE_CODE (t
) != ADDR_EXPR
)
4971 /* Check each ARRAY_REFs in the reference chain. */
4974 if (TREE_CODE (t
) == ARRAY_REF
)
4975 check_array_ref (t
, location
, true /*ignore_off_by_one*/);
4977 t
= TREE_OPERAND(t
,0);
4979 while (handled_component_p (t
));
4982 /* walk_tree() callback that checks if *TP is
4983 an ARRAY_REF inside an ADDR_EXPR (in which an array
4984 subscript one outside the valid range is allowed). Call
4985 check_array_ref for each ARRAY_REF found. The location is
4989 check_array_bounds (tree
*tp
, int *walk_subtree
, void *data
)
4992 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
4993 const location_t
*location
= (const location_t
*) wi
->info
;
4995 *walk_subtree
= TRUE
;
4997 if (TREE_CODE (t
) == ARRAY_REF
)
4998 check_array_ref (t
, location
, false /*ignore_off_by_one*/);
5000 if (TREE_CODE (t
) == INDIRECT_REF
5001 || (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0)))
5002 search_for_addr_array (TREE_OPERAND (t
, 0), location
);
5004 if (TREE_CODE (t
) == ADDR_EXPR
)
5005 *walk_subtree
= FALSE
;
5010 /* Walk over all statements of all reachable BBs and call check_array_bounds
5014 check_all_array_refs (void)
5017 gimple_stmt_iterator si
;
5021 /* Skip bb's that are clearly unreachable. */
5022 if (single_pred_p (bb
))
5024 basic_block pred_bb
= EDGE_PRED (bb
, 0)->src
;
5027 if (!gsi_end_p (gsi_last_bb (pred_bb
)))
5028 ls
= gsi_stmt (gsi_last_bb (pred_bb
));
5030 if (ls
&& gimple_code (ls
) == GIMPLE_COND
5031 && ((gimple_cond_false_p (ls
)
5032 && (EDGE_PRED (bb
, 0)->flags
& EDGE_TRUE_VALUE
))
5033 || (gimple_cond_true_p (ls
)
5034 && (EDGE_PRED (bb
, 0)->flags
& EDGE_FALSE_VALUE
))))
5037 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
5039 gimple stmt
= gsi_stmt (si
);
5040 const location_t
*location
= gimple_location_ptr (stmt
);
5041 struct walk_stmt_info wi
;
5042 if (!gimple_has_location (stmt
))
5045 if (is_gimple_call (stmt
))
5048 size_t n
= gimple_call_num_args (stmt
);
5049 for (i
= 0; i
< n
; i
++)
5051 tree arg
= gimple_call_arg (stmt
, i
);
5052 search_for_addr_array (arg
, location
);
5057 memset (&wi
, 0, sizeof (wi
));
5058 wi
.info
= CONST_CAST (void *, (const void *) location
);
5060 walk_gimple_op (gsi_stmt (si
),
5068 /* Convert range assertion expressions into the implied copies and
5069 copy propagate away the copies. Doing the trivial copy propagation
5070 here avoids the need to run the full copy propagation pass after
5073 FIXME, this will eventually lead to copy propagation removing the
5074 names that had useful range information attached to them. For
5075 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
5076 then N_i will have the range [3, +INF].
5078 However, by converting the assertion into the implied copy
5079 operation N_i = N_j, we will then copy-propagate N_j into the uses
5080 of N_i and lose the range information. We may want to hold on to
5081 ASSERT_EXPRs a little while longer as the ranges could be used in
5082 things like jump threading.
5084 The problem with keeping ASSERT_EXPRs around is that passes after
5085 VRP need to handle them appropriately.
5087 Another approach would be to make the range information a first
5088 class property of the SSA_NAME so that it can be queried from
5089 any pass. This is made somewhat more complex by the need for
5090 multiple ranges to be associated with one SSA_NAME. */
5093 remove_range_assertions (void)
5096 gimple_stmt_iterator si
;
5098 /* Note that the BSI iterator bump happens at the bottom of the
5099 loop and no bump is necessary if we're removing the statement
5100 referenced by the current BSI. */
5102 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
);)
5104 gimple stmt
= gsi_stmt (si
);
5107 if (is_gimple_assign (stmt
)
5108 && gimple_assign_rhs_code (stmt
) == ASSERT_EXPR
)
5110 tree rhs
= gimple_assign_rhs1 (stmt
);
5112 tree cond
= fold (ASSERT_EXPR_COND (rhs
));
5113 use_operand_p use_p
;
5114 imm_use_iterator iter
;
5116 gcc_assert (cond
!= boolean_false_node
);
5118 /* Propagate the RHS into every use of the LHS. */
5119 var
= ASSERT_EXPR_VAR (rhs
);
5120 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
,
5121 gimple_assign_lhs (stmt
))
5122 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
5124 SET_USE (use_p
, var
);
5125 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
5128 /* And finally, remove the copy, it is not needed. */
5129 gsi_remove (&si
, true);
5130 release_defs (stmt
);
5138 /* Return true if STMT is interesting for VRP. */
5141 stmt_interesting_for_vrp (gimple stmt
)
5143 if (gimple_code (stmt
) == GIMPLE_PHI
5144 && is_gimple_reg (gimple_phi_result (stmt
))
5145 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_phi_result (stmt
)))
5146 || POINTER_TYPE_P (TREE_TYPE (gimple_phi_result (stmt
)))))
5148 else if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
5150 tree lhs
= gimple_get_lhs (stmt
);
5152 /* In general, assignments with virtual operands are not useful
5153 for deriving ranges, with the obvious exception of calls to
5154 builtin functions. */
5155 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
5156 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
5157 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
5158 && ((is_gimple_call (stmt
)
5159 && gimple_call_fndecl (stmt
) != NULL_TREE
5160 && DECL_IS_BUILTIN (gimple_call_fndecl (stmt
)))
5161 || ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
)))
5164 else if (gimple_code (stmt
) == GIMPLE_COND
5165 || gimple_code (stmt
) == GIMPLE_SWITCH
)
5172 /* Initialize local data structures for VRP. */
5175 vrp_initialize (void)
5179 vr_value
= XCNEWVEC (value_range_t
*, num_ssa_names
);
5180 vr_phi_edge_counts
= XCNEWVEC (int, num_ssa_names
);
5184 gimple_stmt_iterator si
;
5186 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
5188 gimple phi
= gsi_stmt (si
);
5189 if (!stmt_interesting_for_vrp (phi
))
5191 tree lhs
= PHI_RESULT (phi
);
5192 set_value_range_to_varying (get_value_range (lhs
));
5193 prop_set_simulate_again (phi
, false);
5196 prop_set_simulate_again (phi
, true);
5199 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
5201 gimple stmt
= gsi_stmt (si
);
5203 if (!stmt_interesting_for_vrp (stmt
))
5207 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
5208 set_value_range_to_varying (get_value_range (def
));
5209 prop_set_simulate_again (stmt
, false);
5213 prop_set_simulate_again (stmt
, true);
5220 /* Visit assignment STMT. If it produces an interesting range, record
5221 the SSA name in *OUTPUT_P. */
5223 static enum ssa_prop_result
5224 vrp_visit_assignment_or_call (gimple stmt
, tree
*output_p
)
5228 enum gimple_code code
= gimple_code (stmt
);
5229 lhs
= gimple_get_lhs (stmt
);
5231 /* We only keep track of ranges in integral and pointer types. */
5232 if (TREE_CODE (lhs
) == SSA_NAME
5233 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
5234 /* It is valid to have NULL MIN/MAX values on a type. See
5235 build_range_type. */
5236 && TYPE_MIN_VALUE (TREE_TYPE (lhs
))
5237 && TYPE_MAX_VALUE (TREE_TYPE (lhs
)))
5238 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
5241 value_range_t new_vr
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
5243 if (code
== GIMPLE_CALL
)
5244 extract_range_basic (&new_vr
, stmt
);
5246 extract_range_from_assignment (&new_vr
, stmt
);
5248 /* If STMT is inside a loop, we may be able to know something
5249 else about the range of LHS by examining scalar evolution
5251 if (current_loops
&& (l
= loop_containing_stmt (stmt
)))
5252 adjust_range_with_scev (&new_vr
, l
, stmt
, lhs
);
5254 if (update_value_range (lhs
, &new_vr
))
5258 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5260 fprintf (dump_file
, "Found new range for ");
5261 print_generic_expr (dump_file
, lhs
, 0);
5262 fprintf (dump_file
, ": ");
5263 dump_value_range (dump_file
, &new_vr
);
5264 fprintf (dump_file
, "\n\n");
5267 if (new_vr
.type
== VR_VARYING
)
5268 return SSA_PROP_VARYING
;
5270 return SSA_PROP_INTERESTING
;
5273 return SSA_PROP_NOT_INTERESTING
;
5276 /* Every other statement produces no useful ranges. */
5277 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
5278 set_value_range_to_varying (get_value_range (def
));
5280 return SSA_PROP_VARYING
;
5283 /* Helper that gets the value range of the SSA_NAME with version I
5284 or a symbolic range containing the SSA_NAME only if the value range
5285 is varying or undefined. */
5287 static inline value_range_t
5288 get_vr_for_comparison (int i
)
5290 value_range_t vr
= *(vr_value
[i
]);
5292 /* If name N_i does not have a valid range, use N_i as its own
5293 range. This allows us to compare against names that may
5294 have N_i in their ranges. */
5295 if (vr
.type
== VR_VARYING
|| vr
.type
== VR_UNDEFINED
)
5298 vr
.min
= ssa_name (i
);
5299 vr
.max
= ssa_name (i
);
5305 /* Compare all the value ranges for names equivalent to VAR with VAL
5306 using comparison code COMP. Return the same value returned by
5307 compare_range_with_value, including the setting of
5308 *STRICT_OVERFLOW_P. */
5311 compare_name_with_value (enum tree_code comp
, tree var
, tree val
,
5312 bool *strict_overflow_p
)
5318 int used_strict_overflow
;
5320 value_range_t equiv_vr
;
5322 /* Get the set of equivalences for VAR. */
5323 e
= get_value_range (var
)->equiv
;
5325 /* Start at -1. Set it to 0 if we do a comparison without relying
5326 on overflow, or 1 if all comparisons rely on overflow. */
5327 used_strict_overflow
= -1;
5329 /* Compare vars' value range with val. */
5330 equiv_vr
= get_vr_for_comparison (SSA_NAME_VERSION (var
));
5332 retval
= compare_range_with_value (comp
, &equiv_vr
, val
, &sop
);
5334 used_strict_overflow
= sop
? 1 : 0;
5336 /* If the equiv set is empty we have done all work we need to do. */
5340 && used_strict_overflow
> 0)
5341 *strict_overflow_p
= true;
5345 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
5347 equiv_vr
= get_vr_for_comparison (i
);
5349 t
= compare_range_with_value (comp
, &equiv_vr
, val
, &sop
);
5352 /* If we get different answers from different members
5353 of the equivalence set this check must be in a dead
5354 code region. Folding it to a trap representation
5355 would be correct here. For now just return don't-know. */
5365 used_strict_overflow
= 0;
5366 else if (used_strict_overflow
< 0)
5367 used_strict_overflow
= 1;
5372 && used_strict_overflow
> 0)
5373 *strict_overflow_p
= true;
5379 /* Given a comparison code COMP and names N1 and N2, compare all the
5380 ranges equivalent to N1 against all the ranges equivalent to N2
5381 to determine the value of N1 COMP N2. Return the same value
5382 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
5383 whether we relied on an overflow infinity in the comparison. */
5387 compare_names (enum tree_code comp
, tree n1
, tree n2
,
5388 bool *strict_overflow_p
)
5392 bitmap_iterator bi1
, bi2
;
5394 int used_strict_overflow
;
5395 static bitmap_obstack
*s_obstack
= NULL
;
5396 static bitmap s_e1
= NULL
, s_e2
= NULL
;
5398 /* Compare the ranges of every name equivalent to N1 against the
5399 ranges of every name equivalent to N2. */
5400 e1
= get_value_range (n1
)->equiv
;
5401 e2
= get_value_range (n2
)->equiv
;
5403 /* Use the fake bitmaps if e1 or e2 are not available. */
5404 if (s_obstack
== NULL
)
5406 s_obstack
= XNEW (bitmap_obstack
);
5407 bitmap_obstack_initialize (s_obstack
);
5408 s_e1
= BITMAP_ALLOC (s_obstack
);
5409 s_e2
= BITMAP_ALLOC (s_obstack
);
5416 /* Add N1 and N2 to their own set of equivalences to avoid
5417 duplicating the body of the loop just to check N1 and N2
5419 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
5420 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
5422 /* If the equivalence sets have a common intersection, then the two
5423 names can be compared without checking their ranges. */
5424 if (bitmap_intersect_p (e1
, e2
))
5426 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
5427 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
5429 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
5431 : boolean_false_node
;
5434 /* Start at -1. Set it to 0 if we do a comparison without relying
5435 on overflow, or 1 if all comparisons rely on overflow. */
5436 used_strict_overflow
= -1;
5438 /* Otherwise, compare all the equivalent ranges. First, add N1 and
5439 N2 to their own set of equivalences to avoid duplicating the body
5440 of the loop just to check N1 and N2 ranges. */
5441 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
5443 value_range_t vr1
= get_vr_for_comparison (i1
);
5445 t
= retval
= NULL_TREE
;
5446 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
5450 value_range_t vr2
= get_vr_for_comparison (i2
);
5452 t
= compare_ranges (comp
, &vr1
, &vr2
, &sop
);
5455 /* If we get different answers from different members
5456 of the equivalence set this check must be in a dead
5457 code region. Folding it to a trap representation
5458 would be correct here. For now just return don't-know. */
5462 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
5463 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
5469 used_strict_overflow
= 0;
5470 else if (used_strict_overflow
< 0)
5471 used_strict_overflow
= 1;
5477 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
5478 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
5479 if (used_strict_overflow
> 0)
5480 *strict_overflow_p
= true;
5485 /* None of the equivalent ranges are useful in computing this
5487 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
5488 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
5492 /* Helper function for vrp_evaluate_conditional_warnv. */
5495 vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code code
,
5497 bool * strict_overflow_p
)
5499 value_range_t
*vr0
, *vr1
;
5501 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
5502 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
5505 return compare_ranges (code
, vr0
, vr1
, strict_overflow_p
);
5506 else if (vr0
&& vr1
== NULL
)
5507 return compare_range_with_value (code
, vr0
, op1
, strict_overflow_p
);
5508 else if (vr0
== NULL
&& vr1
)
5509 return (compare_range_with_value
5510 (swap_tree_comparison (code
), vr1
, op0
, strict_overflow_p
));
5514 /* Helper function for vrp_evaluate_conditional_warnv. */
5517 vrp_evaluate_conditional_warnv_with_ops (enum tree_code code
, tree op0
,
5518 tree op1
, bool use_equiv_p
,
5519 bool *strict_overflow_p
, bool *only_ranges
)
5523 *only_ranges
= true;
5525 /* We only deal with integral and pointer types. */
5526 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
5527 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
5533 && (ret
= vrp_evaluate_conditional_warnv_with_ops_using_ranges
5534 (code
, op0
, op1
, strict_overflow_p
)))
5536 *only_ranges
= false;
5537 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
)
5538 return compare_names (code
, op0
, op1
, strict_overflow_p
);
5539 else if (TREE_CODE (op0
) == SSA_NAME
)
5540 return compare_name_with_value (code
, op0
, op1
, strict_overflow_p
);
5541 else if (TREE_CODE (op1
) == SSA_NAME
)
5542 return (compare_name_with_value
5543 (swap_tree_comparison (code
), op1
, op0
, strict_overflow_p
));
5546 return vrp_evaluate_conditional_warnv_with_ops_using_ranges (code
, op0
, op1
,
5551 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
5552 information. Return NULL if the conditional can not be evaluated.
5553 The ranges of all the names equivalent with the operands in COND
5554 will be used when trying to compute the value. If the result is
5555 based on undefined signed overflow, issue a warning if
5559 vrp_evaluate_conditional (enum tree_code code
, tree op0
, tree op1
, gimple stmt
)
5566 ret
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, true, &sop
,
5571 enum warn_strict_overflow_code wc
;
5572 const char* warnmsg
;
5574 if (is_gimple_min_invariant (ret
))
5576 wc
= WARN_STRICT_OVERFLOW_CONDITIONAL
;
5577 warnmsg
= G_("assuming signed overflow does not occur when "
5578 "simplifying conditional to constant");
5582 wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
5583 warnmsg
= G_("assuming signed overflow does not occur when "
5584 "simplifying conditional");
5587 if (issue_strict_overflow_warning (wc
))
5589 location_t location
;
5591 if (!gimple_has_location (stmt
))
5592 location
= input_location
;
5594 location
= gimple_location (stmt
);
5595 warning (OPT_Wstrict_overflow
, "%H%s", &location
, warnmsg
);
5599 if (warn_type_limits
5600 && ret
&& only_ranges
5601 && TREE_CODE_CLASS (code
) == tcc_comparison
5602 && TREE_CODE (op0
) == SSA_NAME
)
5604 /* If the comparison is being folded and the operand on the LHS
5605 is being compared against a constant value that is outside of
5606 the natural range of OP0's type, then the predicate will
5607 always fold regardless of the value of OP0. If -Wtype-limits
5608 was specified, emit a warning. */
5609 const char *warnmsg
= NULL
;
5610 tree type
= TREE_TYPE (op0
);
5611 value_range_t
*vr0
= get_value_range (op0
);
5613 if (vr0
->type
!= VR_VARYING
5614 && INTEGRAL_TYPE_P (type
)
5615 && vrp_val_is_min (vr0
->min
)
5616 && vrp_val_is_max (vr0
->max
)
5617 && is_gimple_min_invariant (op1
))
5619 if (integer_zerop (ret
))
5620 warnmsg
= G_("comparison always false due to limited range of "
5623 warnmsg
= G_("comparison always true due to limited range of "
5629 location_t location
;
5631 if (!gimple_has_location (stmt
))
5632 location
= input_location
;
5634 location
= gimple_location (stmt
);
5636 warning (OPT_Wtype_limits
, "%H%s", &location
, warnmsg
);
5644 /* Visit conditional statement STMT. If we can determine which edge
5645 will be taken out of STMT's basic block, record it in
5646 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
5647 SSA_PROP_VARYING. */
5649 static enum ssa_prop_result
5650 vrp_visit_cond_stmt (gimple stmt
, edge
*taken_edge_p
)
5655 *taken_edge_p
= NULL
;
5657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5662 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
5663 print_gimple_stmt (dump_file
, stmt
, 0, 0);
5664 fprintf (dump_file
, "\nWith known ranges\n");
5666 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
5668 fprintf (dump_file
, "\t");
5669 print_generic_expr (dump_file
, use
, 0);
5670 fprintf (dump_file
, ": ");
5671 dump_value_range (dump_file
, vr_value
[SSA_NAME_VERSION (use
)]);
5674 fprintf (dump_file
, "\n");
5677 /* Compute the value of the predicate COND by checking the known
5678 ranges of each of its operands.
5680 Note that we cannot evaluate all the equivalent ranges here
5681 because those ranges may not yet be final and with the current
5682 propagation strategy, we cannot determine when the value ranges
5683 of the names in the equivalence set have changed.
5685 For instance, given the following code fragment
5689 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
5693 Assume that on the first visit to i_14, i_5 has the temporary
5694 range [8, 8] because the second argument to the PHI function is
5695 not yet executable. We derive the range ~[0, 0] for i_14 and the
5696 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
5697 the first time, since i_14 is equivalent to the range [8, 8], we
5698 determine that the predicate is always false.
5700 On the next round of propagation, i_13 is determined to be
5701 VARYING, which causes i_5 to drop down to VARYING. So, another
5702 visit to i_14 is scheduled. In this second visit, we compute the
5703 exact same range and equivalence set for i_14, namely ~[0, 0] and
5704 { i_5 }. But we did not have the previous range for i_5
5705 registered, so vrp_visit_assignment thinks that the range for
5706 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
5707 is not visited again, which stops propagation from visiting
5708 statements in the THEN clause of that if().
5710 To properly fix this we would need to keep the previous range
5711 value for the names in the equivalence set. This way we would've
5712 discovered that from one visit to the other i_5 changed from
5713 range [8, 8] to VR_VARYING.
5715 However, fixing this apparent limitation may not be worth the
5716 additional checking. Testing on several code bases (GCC, DLV,
5717 MICO, TRAMP3D and SPEC2000) showed that doing this results in
5718 4 more predicates folded in SPEC. */
5721 val
= vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt
),
5722 gimple_cond_lhs (stmt
),
5723 gimple_cond_rhs (stmt
),
5728 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
5731 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5733 "\nIgnoring predicate evaluation because "
5734 "it assumes that signed overflow is undefined");
5739 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5741 fprintf (dump_file
, "\nPredicate evaluates to: ");
5742 if (val
== NULL_TREE
)
5743 fprintf (dump_file
, "DON'T KNOW\n");
5745 print_generic_stmt (dump_file
, val
, 0);
5748 return (*taken_edge_p
) ? SSA_PROP_INTERESTING
: SSA_PROP_VARYING
;
5751 /* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
5752 that includes the value VAL. The search is restricted to the range
5753 [START_IDX, n - 1] where n is the size of VEC.
5755 If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
5758 If there is no CASE_LABEL for VAL and the is one that is larger than VAL,
5759 it is placed in IDX and false is returned.
5761 If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
5765 find_case_label_index (gimple stmt
, size_t start_idx
, tree val
, size_t *idx
)
5767 size_t n
= gimple_switch_num_labels (stmt
);
5770 /* Find case label for minimum of the value range or the next one.
5771 At each iteration we are searching in [low, high - 1]. */
5773 for (low
= start_idx
, high
= n
; high
!= low
; )
5777 /* Note that i != high, so we never ask for n. */
5778 size_t i
= (high
+ low
) / 2;
5779 t
= gimple_switch_label (stmt
, i
);
5781 /* Cache the result of comparing CASE_LOW and val. */
5782 cmp
= tree_int_cst_compare (CASE_LOW (t
), val
);
5786 /* Ranges cannot be empty. */
5795 if (CASE_HIGH (t
) != NULL
5796 && tree_int_cst_compare (CASE_HIGH (t
), val
) >= 0)
5808 /* Searches the case label vector VEC for the range of CASE_LABELs that is used
5809 for values between MIN and MAX. The first index is placed in MIN_IDX. The
5810 last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
5811 then MAX_IDX < MIN_IDX.
5812 Returns true if the default label is not needed. */
5815 find_case_label_range (gimple stmt
, tree min
, tree max
, size_t *min_idx
,
5819 bool min_take_default
= !find_case_label_index (stmt
, 1, min
, &i
);
5820 bool max_take_default
= !find_case_label_index (stmt
, i
, max
, &j
);
5824 && max_take_default
)
5826 /* Only the default case label reached.
5827 Return an empty range. */
5834 bool take_default
= min_take_default
|| max_take_default
;
5838 if (max_take_default
)
5841 /* If the case label range is continuous, we do not need
5842 the default case label. Verify that. */
5843 high
= CASE_LOW (gimple_switch_label (stmt
, i
));
5844 if (CASE_HIGH (gimple_switch_label (stmt
, i
)))
5845 high
= CASE_HIGH (gimple_switch_label (stmt
, i
));
5846 for (k
= i
+ 1; k
<= j
; ++k
)
5848 low
= CASE_LOW (gimple_switch_label (stmt
, k
));
5849 if (!integer_onep (int_const_binop (MINUS_EXPR
, low
, high
, 0)))
5851 take_default
= true;
5855 if (CASE_HIGH (gimple_switch_label (stmt
, k
)))
5856 high
= CASE_HIGH (gimple_switch_label (stmt
, k
));
5861 return !take_default
;
5865 /* Visit switch statement STMT. If we can determine which edge
5866 will be taken out of STMT's basic block, record it in
5867 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
5868 SSA_PROP_VARYING. */
5870 static enum ssa_prop_result
5871 vrp_visit_switch_stmt (gimple stmt
, edge
*taken_edge_p
)
5875 size_t i
= 0, j
= 0, n
;
5878 *taken_edge_p
= NULL
;
5879 op
= gimple_switch_index (stmt
);
5880 if (TREE_CODE (op
) != SSA_NAME
)
5881 return SSA_PROP_VARYING
;
5883 vr
= get_value_range (op
);
5884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5886 fprintf (dump_file
, "\nVisiting switch expression with operand ");
5887 print_generic_expr (dump_file
, op
, 0);
5888 fprintf (dump_file
, " with known range ");
5889 dump_value_range (dump_file
, vr
);
5890 fprintf (dump_file
, "\n");
5893 if (vr
->type
!= VR_RANGE
5894 || symbolic_range_p (vr
))
5895 return SSA_PROP_VARYING
;
5897 /* Find the single edge that is taken from the switch expression. */
5898 n
= gimple_switch_num_labels (stmt
);
5900 take_default
= !find_case_label_range (stmt
, vr
->min
, vr
->max
, &i
, &j
);
5902 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
5906 gcc_assert (take_default
);
5907 val
= gimple_switch_default_label (stmt
);
5911 /* Check if labels with index i to j and maybe the default label
5912 are all reaching the same label. */
5914 val
= gimple_switch_label (stmt
, i
);
5916 && CASE_LABEL (gimple_switch_default_label (stmt
))
5917 != CASE_LABEL (val
))
5919 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5920 fprintf (dump_file
, " not a single destination for this "
5922 return SSA_PROP_VARYING
;
5924 for (++i
; i
<= j
; ++i
)
5926 if (CASE_LABEL (gimple_switch_label (stmt
, i
)) != CASE_LABEL (val
))
5928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5929 fprintf (dump_file
, " not a single destination for this "
5931 return SSA_PROP_VARYING
;
5936 *taken_edge_p
= find_edge (gimple_bb (stmt
),
5937 label_to_block (CASE_LABEL (val
)));
5939 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5941 fprintf (dump_file
, " will take edge to ");
5942 print_generic_stmt (dump_file
, CASE_LABEL (val
), 0);
5945 return SSA_PROP_INTERESTING
;
5949 /* Evaluate statement STMT. If the statement produces a useful range,
5950 return SSA_PROP_INTERESTING and record the SSA name with the
5951 interesting range into *OUTPUT_P.
5953 If STMT is a conditional branch and we can determine its truth
5954 value, the taken edge is recorded in *TAKEN_EDGE_P.
5956 If STMT produces a varying value, return SSA_PROP_VARYING. */
5958 static enum ssa_prop_result
5959 vrp_visit_stmt (gimple stmt
, edge
*taken_edge_p
, tree
*output_p
)
5964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5966 fprintf (dump_file
, "\nVisiting statement:\n");
5967 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
5968 fprintf (dump_file
, "\n");
5971 if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
5973 /* In general, assignments with virtual operands are not useful
5974 for deriving ranges, with the obvious exception of calls to
5975 builtin functions. */
5977 if ((is_gimple_call (stmt
)
5978 && gimple_call_fndecl (stmt
) != NULL_TREE
5979 && DECL_IS_BUILTIN (gimple_call_fndecl (stmt
)))
5980 || ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
5981 return vrp_visit_assignment_or_call (stmt
, output_p
);
5983 else if (gimple_code (stmt
) == GIMPLE_COND
)
5984 return vrp_visit_cond_stmt (stmt
, taken_edge_p
);
5985 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
5986 return vrp_visit_switch_stmt (stmt
, taken_edge_p
);
5988 /* All other statements produce nothing of interest for VRP, so mark
5989 their outputs varying and prevent further simulation. */
5990 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
5991 set_value_range_to_varying (get_value_range (def
));
5993 return SSA_PROP_VARYING
;
5997 /* Meet operation for value ranges. Given two value ranges VR0 and
5998 VR1, store in VR0 a range that contains both VR0 and VR1. This
5999 may not be the smallest possible such range. */
6002 vrp_meet (value_range_t
*vr0
, value_range_t
*vr1
)
6004 if (vr0
->type
== VR_UNDEFINED
)
6006 copy_value_range (vr0
, vr1
);
6010 if (vr1
->type
== VR_UNDEFINED
)
6012 /* Nothing to do. VR0 already has the resulting range. */
6016 if (vr0
->type
== VR_VARYING
)
6018 /* Nothing to do. VR0 already has the resulting range. */
6022 if (vr1
->type
== VR_VARYING
)
6024 set_value_range_to_varying (vr0
);
6028 if (vr0
->type
== VR_RANGE
&& vr1
->type
== VR_RANGE
)
6033 /* Compute the convex hull of the ranges. The lower limit of
6034 the new range is the minimum of the two ranges. If they
6035 cannot be compared, then give up. */
6036 cmp
= compare_values (vr0
->min
, vr1
->min
);
6037 if (cmp
== 0 || cmp
== 1)
6044 /* Similarly, the upper limit of the new range is the maximum
6045 of the two ranges. If they cannot be compared, then
6047 cmp
= compare_values (vr0
->max
, vr1
->max
);
6048 if (cmp
== 0 || cmp
== -1)
6055 /* Check for useless ranges. */
6056 if (INTEGRAL_TYPE_P (TREE_TYPE (min
))
6057 && ((vrp_val_is_min (min
) || is_overflow_infinity (min
))
6058 && (vrp_val_is_max (max
) || is_overflow_infinity (max
))))
6061 /* The resulting set of equivalences is the intersection of
6063 if (vr0
->equiv
&& vr1
->equiv
&& vr0
->equiv
!= vr1
->equiv
)
6064 bitmap_and_into (vr0
->equiv
, vr1
->equiv
);
6065 else if (vr0
->equiv
&& !vr1
->equiv
)
6066 bitmap_clear (vr0
->equiv
);
6068 set_value_range (vr0
, vr0
->type
, min
, max
, vr0
->equiv
);
6070 else if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
6072 /* Two anti-ranges meet only if their complements intersect.
6073 Only handle the case of identical ranges. */
6074 if (compare_values (vr0
->min
, vr1
->min
) == 0
6075 && compare_values (vr0
->max
, vr1
->max
) == 0
6076 && compare_values (vr0
->min
, vr0
->max
) == 0)
6078 /* The resulting set of equivalences is the intersection of
6080 if (vr0
->equiv
&& vr1
->equiv
&& vr0
->equiv
!= vr1
->equiv
)
6081 bitmap_and_into (vr0
->equiv
, vr1
->equiv
);
6082 else if (vr0
->equiv
&& !vr1
->equiv
)
6083 bitmap_clear (vr0
->equiv
);
6088 else if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
6090 /* For a numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4],
6091 only handle the case where the ranges have an empty intersection.
6092 The result of the meet operation is the anti-range. */
6093 if (!symbolic_range_p (vr0
)
6094 && !symbolic_range_p (vr1
)
6095 && !value_ranges_intersect_p (vr0
, vr1
))
6097 /* Copy most of VR1 into VR0. Don't copy VR1's equivalence
6098 set. We need to compute the intersection of the two
6099 equivalence sets. */
6100 if (vr1
->type
== VR_ANTI_RANGE
)
6101 set_value_range (vr0
, vr1
->type
, vr1
->min
, vr1
->max
, vr0
->equiv
);
6103 /* The resulting set of equivalences is the intersection of
6105 if (vr0
->equiv
&& vr1
->equiv
&& vr0
->equiv
!= vr1
->equiv
)
6106 bitmap_and_into (vr0
->equiv
, vr1
->equiv
);
6107 else if (vr0
->equiv
&& !vr1
->equiv
)
6108 bitmap_clear (vr0
->equiv
);
6119 /* Failed to find an efficient meet. Before giving up and setting
6120 the result to VARYING, see if we can at least derive a useful
6121 anti-range. FIXME, all this nonsense about distinguishing
6122 anti-ranges from ranges is necessary because of the odd
6123 semantics of range_includes_zero_p and friends. */
6124 if (!symbolic_range_p (vr0
)
6125 && ((vr0
->type
== VR_RANGE
&& !range_includes_zero_p (vr0
))
6126 || (vr0
->type
== VR_ANTI_RANGE
&& range_includes_zero_p (vr0
)))
6127 && !symbolic_range_p (vr1
)
6128 && ((vr1
->type
== VR_RANGE
&& !range_includes_zero_p (vr1
))
6129 || (vr1
->type
== VR_ANTI_RANGE
&& range_includes_zero_p (vr1
))))
6131 set_value_range_to_nonnull (vr0
, TREE_TYPE (vr0
->min
));
6133 /* Since this meet operation did not result from the meeting of
6134 two equivalent names, VR0 cannot have any equivalences. */
6136 bitmap_clear (vr0
->equiv
);
6139 set_value_range_to_varying (vr0
);
6143 /* Visit all arguments for PHI node PHI that flow through executable
6144 edges. If a valid value range can be derived from all the incoming
6145 value ranges, set a new range for the LHS of PHI. */
6147 static enum ssa_prop_result
6148 vrp_visit_phi_node (gimple phi
)
6151 tree lhs
= PHI_RESULT (phi
);
6152 value_range_t
*lhs_vr
= get_value_range (lhs
);
6153 value_range_t vr_result
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
6154 int edges
, old_edges
;
6156 copy_value_range (&vr_result
, lhs_vr
);
6158 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6160 fprintf (dump_file
, "\nVisiting PHI node: ");
6161 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
6165 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
6167 edge e
= gimple_phi_arg_edge (phi
, i
);
6169 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6172 "\n Argument #%d (%d -> %d %sexecutable)\n",
6173 (int) i
, e
->src
->index
, e
->dest
->index
,
6174 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
6177 if (e
->flags
& EDGE_EXECUTABLE
)
6179 tree arg
= PHI_ARG_DEF (phi
, i
);
6180 value_range_t vr_arg
;
6184 if (TREE_CODE (arg
) == SSA_NAME
)
6186 vr_arg
= *(get_value_range (arg
));
6190 if (is_overflow_infinity (arg
))
6192 arg
= copy_node (arg
);
6193 TREE_OVERFLOW (arg
) = 0;
6196 vr_arg
.type
= VR_RANGE
;
6199 vr_arg
.equiv
= NULL
;
6202 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6204 fprintf (dump_file
, "\t");
6205 print_generic_expr (dump_file
, arg
, dump_flags
);
6206 fprintf (dump_file
, "\n\tValue: ");
6207 dump_value_range (dump_file
, &vr_arg
);
6208 fprintf (dump_file
, "\n");
6211 vrp_meet (&vr_result
, &vr_arg
);
6213 if (vr_result
.type
== VR_VARYING
)
6218 if (vr_result
.type
== VR_VARYING
)
6221 old_edges
= vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)];
6222 vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)] = edges
;
6224 /* To prevent infinite iterations in the algorithm, derive ranges
6225 when the new value is slightly bigger or smaller than the
6226 previous one. We don't do this if we have seen a new executable
6227 edge; this helps us avoid an overflow infinity for conditionals
6228 which are not in a loop. */
6229 if (lhs_vr
->type
== VR_RANGE
&& vr_result
.type
== VR_RANGE
6230 && edges
<= old_edges
)
6232 if (!POINTER_TYPE_P (TREE_TYPE (lhs
)))
6234 int cmp_min
= compare_values (lhs_vr
->min
, vr_result
.min
);
6235 int cmp_max
= compare_values (lhs_vr
->max
, vr_result
.max
);
6237 /* If the new minimum is smaller or larger than the previous
6238 one, go all the way to -INF. In the first case, to avoid
6239 iterating millions of times to reach -INF, and in the
6240 other case to avoid infinite bouncing between different
6242 if (cmp_min
> 0 || cmp_min
< 0)
6244 /* If we will end up with a (-INF, +INF) range, set it
6246 if (vrp_val_is_max (vr_result
.max
))
6249 if (!needs_overflow_infinity (TREE_TYPE (vr_result
.min
))
6250 || !vrp_var_may_overflow (lhs
, phi
))
6251 vr_result
.min
= TYPE_MIN_VALUE (TREE_TYPE (vr_result
.min
));
6252 else if (supports_overflow_infinity (TREE_TYPE (vr_result
.min
)))
6254 negative_overflow_infinity (TREE_TYPE (vr_result
.min
));
6259 /* Similarly, if the new maximum is smaller or larger than
6260 the previous one, go all the way to +INF. */
6261 if (cmp_max
< 0 || cmp_max
> 0)
6263 /* If we will end up with a (-INF, +INF) range, set it
6265 if (vrp_val_is_min (vr_result
.min
))
6268 if (!needs_overflow_infinity (TREE_TYPE (vr_result
.max
))
6269 || !vrp_var_may_overflow (lhs
, phi
))
6270 vr_result
.max
= TYPE_MAX_VALUE (TREE_TYPE (vr_result
.max
));
6271 else if (supports_overflow_infinity (TREE_TYPE (vr_result
.max
)))
6273 positive_overflow_infinity (TREE_TYPE (vr_result
.max
));
6280 /* If the new range is different than the previous value, keep
6282 if (update_value_range (lhs
, &vr_result
))
6283 return SSA_PROP_INTERESTING
;
6285 /* Nothing changed, don't add outgoing edges. */
6286 return SSA_PROP_NOT_INTERESTING
;
6288 /* No match found. Set the LHS to VARYING. */
6290 set_value_range_to_varying (lhs_vr
);
6291 return SSA_PROP_VARYING
;
6294 /* Simplify boolean operations if the source is known
6295 to be already a boolean. */
6297 simplify_truth_ops_using_ranges (gimple_stmt_iterator
*gsi
, gimple stmt
)
6299 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
6304 bool need_conversion
;
6306 op0
= gimple_assign_rhs1 (stmt
);
6307 if (TYPE_PRECISION (TREE_TYPE (op0
)) != 1)
6309 if (TREE_CODE (op0
) != SSA_NAME
)
6311 vr
= get_value_range (op0
);
6313 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
6314 if (!val
|| !integer_onep (val
))
6317 val
= compare_range_with_value (LE_EXPR
, vr
, integer_one_node
, &sop
);
6318 if (!val
|| !integer_onep (val
))
6322 if (rhs_code
== TRUTH_NOT_EXPR
)
6325 op1
= build_int_cst (TREE_TYPE (op0
), 1);
6329 op1
= gimple_assign_rhs2 (stmt
);
6331 /* Reduce number of cases to handle. */
6332 if (is_gimple_min_invariant (op1
))
6334 /* Exclude anything that should have been already folded. */
6335 if (rhs_code
!= EQ_EXPR
6336 && rhs_code
!= NE_EXPR
6337 && rhs_code
!= TRUTH_XOR_EXPR
)
6340 if (!integer_zerop (op1
)
6341 && !integer_onep (op1
)
6342 && !integer_all_onesp (op1
))
6345 /* Limit the number of cases we have to consider. */
6346 if (rhs_code
== EQ_EXPR
)
6349 op1
= fold_unary (TRUTH_NOT_EXPR
, TREE_TYPE (op1
), op1
);
6354 /* Punt on A == B as there is no BIT_XNOR_EXPR. */
6355 if (rhs_code
== EQ_EXPR
)
6358 if (TYPE_PRECISION (TREE_TYPE (op1
)) != 1)
6360 vr
= get_value_range (op1
);
6361 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
6362 if (!val
|| !integer_onep (val
))
6365 val
= compare_range_with_value (LE_EXPR
, vr
, integer_one_node
, &sop
);
6366 if (!val
|| !integer_onep (val
))
6372 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
6374 location_t location
;
6376 if (!gimple_has_location (stmt
))
6377 location
= input_location
;
6379 location
= gimple_location (stmt
);
6381 if (rhs_code
== TRUTH_AND_EXPR
|| rhs_code
== TRUTH_OR_EXPR
)
6382 warning_at (location
, OPT_Wstrict_overflow
,
6383 _("assuming signed overflow does not occur when "
6384 "simplifying && or || to & or |"));
6386 warning_at (location
, OPT_Wstrict_overflow
,
6387 _("assuming signed overflow does not occur when "
6388 "simplifying ==, != or ! to identity or ^"));
6392 !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt
)),
6397 case TRUTH_AND_EXPR
:
6398 rhs_code
= BIT_AND_EXPR
;
6401 rhs_code
= BIT_IOR_EXPR
;
6403 case TRUTH_XOR_EXPR
:
6405 if (integer_zerop (op1
))
6407 gimple_assign_set_rhs_with_ops (gsi
,
6408 need_conversion
? NOP_EXPR
: SSA_NAME
,
6410 update_stmt (gsi_stmt (*gsi
));
6414 rhs_code
= BIT_XOR_EXPR
;
6420 if (need_conversion
)
6423 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, op0
, op1
);
6424 update_stmt (gsi_stmt (*gsi
));
6428 /* Simplify a division or modulo operator to a right shift or
6429 bitwise and if the first operand is unsigned or is greater
6430 than zero and the second operand is an exact power of two. */
6433 simplify_div_or_mod_using_ranges (gimple stmt
)
6435 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
6437 tree op0
= gimple_assign_rhs1 (stmt
);
6438 tree op1
= gimple_assign_rhs2 (stmt
);
6439 value_range_t
*vr
= get_value_range (gimple_assign_rhs1 (stmt
));
6441 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
6443 val
= integer_one_node
;
6449 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
6453 && integer_onep (val
)
6454 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
6456 location_t location
;
6458 if (!gimple_has_location (stmt
))
6459 location
= input_location
;
6461 location
= gimple_location (stmt
);
6462 warning (OPT_Wstrict_overflow
,
6463 ("%Hassuming signed overflow does not occur when "
6464 "simplifying / or %% to >> or &"),
6469 if (val
&& integer_onep (val
))
6473 if (rhs_code
== TRUNC_DIV_EXPR
)
6475 t
= build_int_cst (NULL_TREE
, tree_log2 (op1
));
6476 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
6477 gimple_assign_set_rhs1 (stmt
, op0
);
6478 gimple_assign_set_rhs2 (stmt
, t
);
6482 t
= build_int_cst (TREE_TYPE (op1
), 1);
6483 t
= int_const_binop (MINUS_EXPR
, op1
, t
, 0);
6484 t
= fold_convert (TREE_TYPE (op0
), t
);
6486 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
6487 gimple_assign_set_rhs1 (stmt
, op0
);
6488 gimple_assign_set_rhs2 (stmt
, t
);
6498 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
6499 ABS_EXPR. If the operand is <= 0, then simplify the
6500 ABS_EXPR into a NEGATE_EXPR. */
6503 simplify_abs_using_ranges (gimple stmt
)
6506 tree op
= gimple_assign_rhs1 (stmt
);
6507 tree type
= TREE_TYPE (op
);
6508 value_range_t
*vr
= get_value_range (op
);
6510 if (TYPE_UNSIGNED (type
))
6512 val
= integer_zero_node
;
6518 val
= compare_range_with_value (LE_EXPR
, vr
, integer_zero_node
, &sop
);
6522 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
,
6527 if (integer_zerop (val
))
6528 val
= integer_one_node
;
6529 else if (integer_onep (val
))
6530 val
= integer_zero_node
;
6535 && (integer_onep (val
) || integer_zerop (val
)))
6537 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
6539 location_t location
;
6541 if (!gimple_has_location (stmt
))
6542 location
= input_location
;
6544 location
= gimple_location (stmt
);
6545 warning (OPT_Wstrict_overflow
,
6546 ("%Hassuming signed overflow does not occur when "
6547 "simplifying abs (X) to X or -X"),
6551 gimple_assign_set_rhs1 (stmt
, op
);
6552 if (integer_onep (val
))
6553 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
6555 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
6564 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
6565 a known value range VR.
6567 If there is one and only one value which will satisfy the
6568 conditional, then return that value. Else return NULL. */
6571 test_for_singularity (enum tree_code cond_code
, tree op0
,
6572 tree op1
, value_range_t
*vr
)
6577 /* Extract minimum/maximum values which satisfy the
6578 the conditional as it was written. */
6579 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
6581 /* This should not be negative infinity; there is no overflow
6583 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
6586 if (cond_code
== LT_EXPR
&& !is_overflow_infinity (max
))
6588 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
6589 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
6591 TREE_NO_WARNING (max
) = 1;
6594 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
6596 /* This should not be positive infinity; there is no overflow
6598 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
6601 if (cond_code
== GT_EXPR
&& !is_overflow_infinity (min
))
6603 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
6604 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
6606 TREE_NO_WARNING (min
) = 1;
6610 /* Now refine the minimum and maximum values using any
6611 value range information we have for op0. */
6614 if (compare_values (vr
->min
, min
) == -1)
6618 if (compare_values (vr
->max
, max
) == 1)
6623 /* If the new min/max values have converged to a single value,
6624 then there is only one value which can satisfy the condition,
6625 return that value. */
6626 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
6632 /* Simplify a conditional using a relational operator to an equality
6633 test if the range information indicates only one value can satisfy
6634 the original conditional. */
6637 simplify_cond_using_ranges (gimple stmt
)
6639 tree op0
= gimple_cond_lhs (stmt
);
6640 tree op1
= gimple_cond_rhs (stmt
);
6641 enum tree_code cond_code
= gimple_cond_code (stmt
);
6643 if (cond_code
!= NE_EXPR
6644 && cond_code
!= EQ_EXPR
6645 && TREE_CODE (op0
) == SSA_NAME
6646 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
6647 && is_gimple_min_invariant (op1
))
6649 value_range_t
*vr
= get_value_range (op0
);
6651 /* If we have range information for OP0, then we might be
6652 able to simplify this conditional. */
6653 if (vr
->type
== VR_RANGE
)
6655 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
6661 fprintf (dump_file
, "Simplified relational ");
6662 print_gimple_stmt (dump_file
, stmt
, 0, 0);
6663 fprintf (dump_file
, " into ");
6666 gimple_cond_set_code (stmt
, EQ_EXPR
);
6667 gimple_cond_set_lhs (stmt
, op0
);
6668 gimple_cond_set_rhs (stmt
, new_tree
);
6674 print_gimple_stmt (dump_file
, stmt
, 0, 0);
6675 fprintf (dump_file
, "\n");
6681 /* Try again after inverting the condition. We only deal
6682 with integral types here, so no need to worry about
6683 issues with inverting FP comparisons. */
6684 cond_code
= invert_tree_comparison (cond_code
, false);
6685 new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
6691 fprintf (dump_file
, "Simplified relational ");
6692 print_gimple_stmt (dump_file
, stmt
, 0, 0);
6693 fprintf (dump_file
, " into ");
6696 gimple_cond_set_code (stmt
, NE_EXPR
);
6697 gimple_cond_set_lhs (stmt
, op0
);
6698 gimple_cond_set_rhs (stmt
, new_tree
);
6704 print_gimple_stmt (dump_file
, stmt
, 0, 0);
6705 fprintf (dump_file
, "\n");
6716 /* Simplify a switch statement using the value range of the switch
6720 simplify_switch_using_ranges (gimple stmt
)
6722 tree op
= gimple_switch_index (stmt
);
6727 size_t i
= 0, j
= 0, n
, n2
;
6731 if (TREE_CODE (op
) != SSA_NAME
)
6734 vr
= get_value_range (op
);
6736 /* We can only handle integer ranges. */
6737 if (vr
->type
!= VR_RANGE
6738 || symbolic_range_p (vr
))
6741 /* Find case label for min/max of the value range. */
6742 n
= gimple_switch_num_labels (stmt
);
6743 take_default
= !find_case_label_range (stmt
, vr
->min
, vr
->max
, &i
, &j
);
6745 /* Bail out if this is just all edges taken. */
6751 /* Build a new vector of taken case labels. */
6752 vec2
= make_tree_vec (j
- i
+ 1 + (int)take_default
);
6755 /* Add the default edge, if necessary. */
6757 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
6759 for (; i
<= j
; ++i
, ++n2
)
6760 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
6762 /* Mark needed edges. */
6763 for (i
= 0; i
< n2
; ++i
)
6765 e
= find_edge (gimple_bb (stmt
),
6766 label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
6767 e
->aux
= (void *)-1;
6770 /* Queue not needed edges for later removal. */
6771 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
6773 if (e
->aux
== (void *)-1)
6779 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6781 fprintf (dump_file
, "removing unreachable case label\n");
6783 VEC_safe_push (edge
, heap
, to_remove_edges
, e
);
6786 /* And queue an update for the stmt. */
6789 VEC_safe_push (switch_update
, heap
, to_update_switch_stmts
, &su
);
6793 /* Simplify STMT using ranges if possible. */
6796 simplify_stmt_using_ranges (gimple_stmt_iterator
*gsi
)
6798 gimple stmt
= gsi_stmt (*gsi
);
6799 if (is_gimple_assign (stmt
))
6801 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
6807 case TRUTH_NOT_EXPR
:
6808 case TRUTH_AND_EXPR
:
6810 case TRUTH_XOR_EXPR
:
6811 /* Transform EQ_EXPR, NE_EXPR, TRUTH_NOT_EXPR into BIT_XOR_EXPR
6812 or identity if the RHS is zero or one, and the LHS are known
6813 to be boolean values. Transform all TRUTH_*_EXPR into
6814 BIT_*_EXPR if both arguments are known to be boolean values. */
6815 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
))))
6816 return simplify_truth_ops_using_ranges (gsi
, stmt
);
6819 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
6820 and BIT_AND_EXPR respectively if the first operand is greater
6821 than zero and the second operand is an exact power of two. */
6822 case TRUNC_DIV_EXPR
:
6823 case TRUNC_MOD_EXPR
:
6824 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))
6825 && integer_pow2p (gimple_assign_rhs2 (stmt
)))
6826 return simplify_div_or_mod_using_ranges (stmt
);
6829 /* Transform ABS (X) into X or -X as appropriate. */
6831 if (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
6832 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
))))
6833 return simplify_abs_using_ranges (stmt
);
6840 else if (gimple_code (stmt
) == GIMPLE_COND
)
6841 return simplify_cond_using_ranges (stmt
);
6842 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
6843 return simplify_switch_using_ranges (stmt
);
6848 /* Stack of dest,src equivalency pairs that need to be restored after
6849 each attempt to thread a block's incoming edge to an outgoing edge.
6851 A NULL entry is used to mark the end of pairs which need to be
6853 static VEC(tree
,heap
) *stack
;
6855 /* A trivial wrapper so that we can present the generic jump threading
6856 code with a simple API for simplifying statements. STMT is the
6857 statement we want to simplify, WITHIN_STMT provides the location
6858 for any overflow warnings. */
6861 simplify_stmt_for_jump_threading (gimple stmt
, gimple within_stmt
)
6863 /* We only use VRP information to simplify conditionals. This is
6864 overly conservative, but it's unclear if doing more would be
6865 worth the compile time cost. */
6866 if (gimple_code (stmt
) != GIMPLE_COND
)
6869 return vrp_evaluate_conditional (gimple_cond_code (stmt
),
6870 gimple_cond_lhs (stmt
),
6871 gimple_cond_rhs (stmt
), within_stmt
);
6874 /* Blocks which have more than one predecessor and more than
6875 one successor present jump threading opportunities, i.e.,
6876 when the block is reached from a specific predecessor, we
6877 may be able to determine which of the outgoing edges will
6878 be traversed. When this optimization applies, we are able
6879 to avoid conditionals at runtime and we may expose secondary
6880 optimization opportunities.
6882 This routine is effectively a driver for the generic jump
6883 threading code. It basically just presents the generic code
6884 with edges that may be suitable for jump threading.
6886 Unlike DOM, we do not iterate VRP if jump threading was successful.
6887 While iterating may expose new opportunities for VRP, it is expected
6888 those opportunities would be very limited and the compile time cost
6889 to expose those opportunities would be significant.
6891 As jump threading opportunities are discovered, they are registered
6892 for later realization. */
6895 identify_jump_threads (void)
6902 /* Ugh. When substituting values earlier in this pass we can
6903 wipe the dominance information. So rebuild the dominator
6904 information as we need it within the jump threading code. */
6905 calculate_dominance_info (CDI_DOMINATORS
);
6907 /* We do not allow VRP information to be used for jump threading
6908 across a back edge in the CFG. Otherwise it becomes too
6909 difficult to avoid eliminating loop exit tests. Of course
6910 EDGE_DFS_BACK is not accurate at this time so we have to
6912 mark_dfs_back_edges ();
6914 /* Do not thread across edges we are about to remove. Just marking
6915 them as EDGE_DFS_BACK will do. */
6916 for (i
= 0; VEC_iterate (edge
, to_remove_edges
, i
, e
); ++i
)
6917 e
->flags
|= EDGE_DFS_BACK
;
6919 /* Allocate our unwinder stack to unwind any temporary equivalences
6920 that might be recorded. */
6921 stack
= VEC_alloc (tree
, heap
, 20);
6923 /* To avoid lots of silly node creation, we create a single
6924 conditional and just modify it in-place when attempting to
6926 dummy
= gimple_build_cond (EQ_EXPR
,
6927 integer_zero_node
, integer_zero_node
,
6930 /* Walk through all the blocks finding those which present a
6931 potential jump threading opportunity. We could set this up
6932 as a dominator walker and record data during the walk, but
6933 I doubt it's worth the effort for the classes of jump
6934 threading opportunities we are trying to identify at this
6935 point in compilation. */
6940 /* If the generic jump threading code does not find this block
6941 interesting, then there is nothing to do. */
6942 if (! potentially_threadable_block (bb
))
6945 /* We only care about blocks ending in a COND_EXPR. While there
6946 may be some value in handling SWITCH_EXPR here, I doubt it's
6947 terribly important. */
6948 last
= gsi_stmt (gsi_last_bb (bb
));
6949 if (gimple_code (last
) != GIMPLE_COND
)
6952 /* We're basically looking for any kind of conditional with
6953 integral type arguments. */
6954 if (TREE_CODE (gimple_cond_lhs (last
)) == SSA_NAME
6955 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last
)))
6956 && (TREE_CODE (gimple_cond_rhs (last
)) == SSA_NAME
6957 || is_gimple_min_invariant (gimple_cond_rhs (last
)))
6958 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_rhs (last
))))
6962 /* We've got a block with multiple predecessors and multiple
6963 successors which also ends in a suitable conditional. For
6964 each predecessor, see if we can thread it to a specific
6966 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6968 /* Do not thread across back edges or abnormal edges
6970 if (e
->flags
& (EDGE_DFS_BACK
| EDGE_COMPLEX
))
6973 thread_across_edge (dummy
, e
, true, &stack
,
6974 simplify_stmt_for_jump_threading
);
6979 /* We do not actually update the CFG or SSA graphs at this point as
6980 ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
6981 handle ASSERT_EXPRs gracefully. */
6984 /* We identified all the jump threading opportunities earlier, but could
6985 not transform the CFG at that time. This routine transforms the
6986 CFG and arranges for the dominator tree to be rebuilt if necessary.
6988 Note the SSA graph update will occur during the normal TODO
6989 processing by the pass manager. */
6991 finalize_jump_threads (void)
6993 thread_through_all_blocks (false);
6994 VEC_free (tree
, heap
, stack
);
6998 /* Traverse all the blocks folding conditionals with known ranges. */
7004 prop_value_t
*single_val_range
;
7005 bool do_value_subst_p
;
7009 fprintf (dump_file
, "\nValue ranges after VRP:\n\n");
7010 dump_all_value_ranges (dump_file
);
7011 fprintf (dump_file
, "\n");
7014 /* We may have ended with ranges that have exactly one value. Those
7015 values can be substituted as any other copy/const propagated
7016 value using substitute_and_fold. */
7017 single_val_range
= XCNEWVEC (prop_value_t
, num_ssa_names
);
7019 do_value_subst_p
= false;
7020 for (i
= 0; i
< num_ssa_names
; i
++)
7022 && vr_value
[i
]->type
== VR_RANGE
7023 && vr_value
[i
]->min
== vr_value
[i
]->max
)
7025 single_val_range
[i
].value
= vr_value
[i
]->min
;
7026 do_value_subst_p
= true;
7029 if (!do_value_subst_p
)
7031 /* We found no single-valued ranges, don't waste time trying to
7032 do single value substitution in substitute_and_fold. */
7033 free (single_val_range
);
7034 single_val_range
= NULL
;
7037 substitute_and_fold (single_val_range
, true);
7039 if (warn_array_bounds
)
7040 check_all_array_refs ();
7042 /* We must identify jump threading opportunities before we release
7043 the datastructures built by VRP. */
7044 identify_jump_threads ();
7046 /* Free allocated memory. */
7047 for (i
= 0; i
< num_ssa_names
; i
++)
7050 BITMAP_FREE (vr_value
[i
]->equiv
);
7054 free (single_val_range
);
7056 free (vr_phi_edge_counts
);
7058 /* So that we can distinguish between VRP data being available
7059 and not available. */
7061 vr_phi_edge_counts
= NULL
;
7065 /* Main entry point to VRP (Value Range Propagation). This pass is
7066 loosely based on J. R. C. Patterson, ``Accurate Static Branch
7067 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
7068 Programming Language Design and Implementation, pp. 67-78, 1995.
7069 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
7071 This is essentially an SSA-CCP pass modified to deal with ranges
7072 instead of constants.
7074 While propagating ranges, we may find that two or more SSA name
7075 have equivalent, though distinct ranges. For instance,
7078 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
7080 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
7084 In the code above, pointer p_5 has range [q_2, q_2], but from the
7085 code we can also determine that p_5 cannot be NULL and, if q_2 had
7086 a non-varying range, p_5's range should also be compatible with it.
7088 These equivalences are created by two expressions: ASSERT_EXPR and
7089 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
7090 result of another assertion, then we can use the fact that p_5 and
7091 p_4 are equivalent when evaluating p_5's range.
7093 Together with value ranges, we also propagate these equivalences
7094 between names so that we can take advantage of information from
7095 multiple ranges when doing final replacement. Note that this
7096 equivalency relation is transitive but not symmetric.
7098 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
7099 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
7100 in contexts where that assertion does not hold (e.g., in line 6).
7102 TODO, the main difference between this pass and Patterson's is that
7103 we do not propagate edge probabilities. We only compute whether
7104 edges can be taken or not. That is, instead of having a spectrum
7105 of jump probabilities between 0 and 1, we only deal with 0, 1 and
7106 DON'T KNOW. In the future, it may be worthwhile to propagate
7107 probabilities to aid branch prediction. */
7116 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
7117 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
7120 insert_range_assertions ();
7122 to_remove_edges
= VEC_alloc (edge
, heap
, 10);
7123 to_update_switch_stmts
= VEC_alloc (switch_update
, heap
, 5);
7126 ssa_propagate (vrp_visit_stmt
, vrp_visit_phi_node
);
7129 /* ASSERT_EXPRs must be removed before finalizing jump threads
7130 as finalizing jump threads calls the CFG cleanup code which
7131 does not properly handle ASSERT_EXPRs. */
7132 remove_range_assertions ();
7134 /* If we exposed any new variables, go ahead and put them into
7135 SSA form now, before we handle jump threading. This simplifies
7136 interactions between rewriting of _DECL nodes into SSA form
7137 and rewriting SSA_NAME nodes into SSA form after block
7138 duplication and CFG manipulation. */
7139 update_ssa (TODO_update_ssa
);
7141 finalize_jump_threads ();
7143 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
7144 CFG in a broken state and requires a cfg_cleanup run. */
7145 for (i
= 0; VEC_iterate (edge
, to_remove_edges
, i
, e
); ++i
)
7147 /* Update SWITCH_EXPR case label vector. */
7148 for (i
= 0; VEC_iterate (switch_update
, to_update_switch_stmts
, i
, su
); ++i
)
7151 size_t n
= TREE_VEC_LENGTH (su
->vec
);
7153 gimple_switch_set_num_labels (su
->stmt
, n
);
7154 for (j
= 0; j
< n
; j
++)
7155 gimple_switch_set_label (su
->stmt
, j
, TREE_VEC_ELT (su
->vec
, j
));
7156 /* As we may have replaced the default label with a regular one
7157 make sure to make it a real default label again. This ensures
7158 optimal expansion. */
7159 label
= gimple_switch_default_label (su
->stmt
);
7160 CASE_LOW (label
) = NULL_TREE
;
7161 CASE_HIGH (label
) = NULL_TREE
;
7164 if (VEC_length (edge
, to_remove_edges
) > 0)
7165 free_dominance_info (CDI_DOMINATORS
);
7167 VEC_free (edge
, heap
, to_remove_edges
);
7168 VEC_free (switch_update
, heap
, to_update_switch_stmts
);
7171 loop_optimizer_finalize ();
7178 return flag_tree_vrp
!= 0;
7181 struct gimple_opt_pass pass_vrp
=
7186 gate_vrp
, /* gate */
7187 execute_vrp
, /* execute */
7190 0, /* static_pass_number */
7191 TV_TREE_VRP
, /* tv_id */
7192 PROP_ssa
| PROP_alias
, /* properties_required */
7193 0, /* properties_provided */
7194 0, /* properties_destroyed */
7195 0, /* todo_flags_start */
7200 | TODO_update_ssa
/* todo_flags_finish */