1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005 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 2, 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 COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
34 #include "diagnostic.h"
36 #include "tree-scalar-evolution.h"
37 #include "tree-ssa-propagate.h"
38 #include "tree-chrec.h"
40 /* Set of SSA names found during the dominator traversal of a
41 sub-graph in find_assert_locations. */
42 static sbitmap found_in_subgraph
;
44 /* Loop structure of the program. Used to analyze scalar evolutions
45 inside adjust_range_with_scev. */
46 static struct loops
*cfg_loops
;
48 /* Local functions. */
49 static int compare_values (tree val1
, tree val2
);
51 /* Location information for ASSERT_EXPRs. Each instance of this
52 structure describes an ASSERT_EXPR for an SSA name. Since a single
53 SSA name may have more than one assertion associated with it, these
54 locations are kept in a linked list attached to the corresponding
58 /* Basic block where the assertion would be inserted. */
61 /* Some assertions need to be inserted on an edge (e.g., assertions
62 generated by COND_EXPRs). In those cases, BB will be NULL. */
65 /* Pointer to the statement that generated this assertion. */
66 block_stmt_iterator si
;
68 /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
69 enum tree_code comp_code
;
71 /* Value being compared against. */
74 /* Next node in the linked list. */
75 struct assert_locus_d
*next
;
78 typedef struct assert_locus_d
*assert_locus_t
;
80 /* If bit I is present, it means that SSA name N_i has a list of
81 assertions that should be inserted in the IL. */
82 static bitmap need_assert_for
;
84 /* Array of locations lists where to insert assertions. ASSERTS_FOR[I]
85 holds a list of ASSERT_LOCUS_T nodes that describe where
86 ASSERT_EXPRs for SSA name N_I should be inserted. */
87 static assert_locus_t
*asserts_for
;
89 /* Set of blocks visited in find_assert_locations. Used to avoid
90 visiting the same block more than once. */
91 static sbitmap blocks_visited
;
93 /* Value range array. After propagation, VR_VALUE[I] holds the range
94 of values that SSA name N_I may take. */
95 static value_range_t
**vr_value
;
97 /* Given a comparison code, return its opposite. Note that this is *not*
98 the same as inverting its truth value (invert_tree_comparison). Here we
99 just want to literally flip the comparison around.
101 So, '<' gets '>', '<=' gets '>='. Both '==' and '!=' are returned
104 static enum tree_code
105 opposite_comparison (enum tree_code code
)
138 /* Return true if EXPR computes a non-zero value. */
141 expr_computes_nonzero (tree expr
)
143 /* Type casts won't change anything, so just strip them. */
146 /* Calling alloca, guarantees that the value is non-NULL. */
147 if (alloca_call_p (expr
))
150 /* The address of a non-weak symbol is never NULL, unless the user
151 has requested not to remove NULL pointer checks. */
152 if (flag_delete_null_pointer_checks
153 && TREE_CODE (expr
) == ADDR_EXPR
154 && DECL_P (TREE_OPERAND (expr
, 0))
155 && !DECL_WEAK (TREE_OPERAND (expr
, 0)))
158 /* IOR of any value with a nonzero value will result in a nonzero
160 if (TREE_CODE (expr
) == BIT_IOR_EXPR
161 && integer_nonzerop (TREE_OPERAND (expr
, 1)))
168 /* Return true if ARG is marked with the nonnull attribute in the
169 current function signature. */
172 nonnull_arg_p (tree arg
)
174 tree t
, attrs
, fntype
;
175 unsigned HOST_WIDE_INT arg_num
;
177 gcc_assert (TREE_CODE (arg
) == PARM_DECL
&& POINTER_TYPE_P (TREE_TYPE (arg
)));
179 fntype
= TREE_TYPE (current_function_decl
);
180 attrs
= lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype
));
182 /* If "nonnull" wasn't specified, we know nothing about the argument. */
183 if (attrs
== NULL_TREE
)
186 /* If "nonnull" applies to all the arguments, then ARG is non-null. */
187 if (TREE_VALUE (attrs
) == NULL_TREE
)
190 /* Get the position number for ARG in the function signature. */
191 for (arg_num
= 1, t
= DECL_ARGUMENTS (current_function_decl
);
193 t
= TREE_CHAIN (t
), arg_num
++)
199 gcc_assert (t
== arg
);
201 /* Now see if ARG_NUM is mentioned in the nonnull list. */
202 for (t
= TREE_VALUE (attrs
); t
; t
= TREE_CHAIN (t
))
204 if (compare_tree_int (TREE_VALUE (t
), arg_num
) == 0)
212 /* Set value range VR to {T, MIN, MAX, EQUIV}. */
215 set_value_range (value_range_t
*vr
, enum value_range_type t
, tree min
,
216 tree max
, bitmap equiv
)
218 #if defined ENABLE_CHECKING
219 /* Check the validity of the range. */
220 if (t
== VR_RANGE
|| t
== VR_ANTI_RANGE
)
224 gcc_assert (min
&& max
);
226 if (INTEGRAL_TYPE_P (TREE_TYPE (min
)) && t
== VR_ANTI_RANGE
)
227 gcc_assert (min
!= TYPE_MIN_VALUE (TREE_TYPE (min
))
228 || max
!= TYPE_MAX_VALUE (TREE_TYPE (max
)));
230 cmp
= compare_values (min
, max
);
231 gcc_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
234 if (t
== VR_UNDEFINED
|| t
== VR_VARYING
)
235 gcc_assert (min
== NULL_TREE
&& max
== NULL_TREE
);
237 if (t
== VR_UNDEFINED
|| t
== VR_VARYING
)
238 gcc_assert (equiv
== NULL
|| bitmap_empty_p (equiv
));
245 /* Since updating the equivalence set involves deep copying the
246 bitmaps, only do it if absolutely necessary. */
247 if (vr
->equiv
== NULL
)
248 vr
->equiv
= BITMAP_ALLOC (NULL
);
250 if (equiv
!= vr
->equiv
)
252 if (equiv
&& !bitmap_empty_p (equiv
))
253 bitmap_copy (vr
->equiv
, equiv
);
255 bitmap_clear (vr
->equiv
);
260 /* Copy value range FROM into value range TO. */
263 copy_value_range (value_range_t
*to
, value_range_t
*from
)
265 set_value_range (to
, from
->type
, from
->min
, from
->max
, from
->equiv
);
269 /* Set value range VR to a non-NULL range of type TYPE. */
272 set_value_range_to_nonnull (value_range_t
*vr
, tree type
)
274 tree zero
= build_int_cst (type
, 0);
275 set_value_range (vr
, VR_ANTI_RANGE
, zero
, zero
, vr
->equiv
);
279 /* Set value range VR to a NULL range of type TYPE. */
282 set_value_range_to_null (value_range_t
*vr
, tree type
)
284 tree zero
= build_int_cst (type
, 0);
285 set_value_range (vr
, VR_RANGE
, zero
, zero
, vr
->equiv
);
289 /* Set value range VR to VR_VARYING. */
292 set_value_range_to_varying (value_range_t
*vr
)
294 vr
->type
= VR_VARYING
;
295 vr
->min
= vr
->max
= NULL_TREE
;
297 bitmap_clear (vr
->equiv
);
301 /* Set value range VR to VR_UNDEFINED. */
304 set_value_range_to_undefined (value_range_t
*vr
)
306 vr
->type
= VR_UNDEFINED
;
307 vr
->min
= vr
->max
= NULL_TREE
;
309 bitmap_clear (vr
->equiv
);
313 /* Return value range information for VAR. Create an empty range
316 static value_range_t
*
317 get_value_range (tree var
)
321 unsigned ver
= SSA_NAME_VERSION (var
);
327 /* Create a default value range. */
328 vr_value
[ver
] = vr
= xmalloc (sizeof (*vr
));
329 memset (vr
, 0, sizeof (*vr
));
331 /* Allocate an equivalence set. */
332 vr
->equiv
= BITMAP_ALLOC (NULL
);
334 /* If VAR is a default definition, the variable can take any value
336 sym
= SSA_NAME_VAR (var
);
337 if (var
== var_ann (sym
)->default_def
)
339 /* Try to use the "nonnull" attribute to create ~[0, 0]
340 anti-ranges for pointers. Note that this is only valid with
341 default definitions of PARM_DECLs. */
342 if (TREE_CODE (sym
) == PARM_DECL
343 && POINTER_TYPE_P (TREE_TYPE (sym
))
344 && nonnull_arg_p (sym
))
345 set_value_range_to_nonnull (vr
, TREE_TYPE (sym
));
347 set_value_range_to_varying (vr
);
354 /* Update the value range and equivalence set for variable VAR to
355 NEW_VR. Return true if NEW_VR is different from VAR's previous
358 NOTE: This function assumes that NEW_VR is a temporary value range
359 object created for the sole purpose of updating VAR's range. The
360 storage used by the equivalence set from NEW_VR will be freed by
361 this function. Do not call update_value_range when NEW_VR
362 is the range object associated with another SSA name. */
365 update_value_range (tree var
, value_range_t
*new_vr
)
367 value_range_t
*old_vr
;
370 /* Update the value range, if necessary. */
371 old_vr
= get_value_range (var
);
372 is_new
= old_vr
->type
!= new_vr
->type
373 || old_vr
->min
!= new_vr
->min
374 || old_vr
->max
!= new_vr
->max
375 || (old_vr
->equiv
== NULL
&& new_vr
->equiv
)
376 || (old_vr
->equiv
&& new_vr
->equiv
== NULL
)
377 || (!bitmap_equal_p (old_vr
->equiv
, new_vr
->equiv
));
380 set_value_range (old_vr
, new_vr
->type
, new_vr
->min
, new_vr
->max
,
383 BITMAP_FREE (new_vr
->equiv
);
384 new_vr
->equiv
= NULL
;
390 /* Add VAR and VAR's equivalence set to EQUIV. */
393 add_equivalence (bitmap equiv
, tree var
)
395 unsigned ver
= SSA_NAME_VERSION (var
);
396 value_range_t
*vr
= vr_value
[ver
];
398 bitmap_set_bit (equiv
, ver
);
400 bitmap_ior_into (equiv
, vr
->equiv
);
404 /* Return true if VR is ~[0, 0]. */
407 range_is_nonnull (value_range_t
*vr
)
409 return vr
->type
== VR_ANTI_RANGE
410 && integer_zerop (vr
->min
)
411 && integer_zerop (vr
->max
);
415 /* Return true if VR is [0, 0]. */
418 range_is_null (value_range_t
*vr
)
420 return vr
->type
== VR_RANGE
421 && integer_zerop (vr
->min
)
422 && integer_zerop (vr
->max
);
426 /* Return true if value range VR involves at least one symbol. */
429 symbolic_range_p (value_range_t
*vr
)
431 return (!is_gimple_min_invariant (vr
->min
)
432 || !is_gimple_min_invariant (vr
->max
));
436 /* Like expr_computes_nonzero, but this function uses value ranges
440 vrp_expr_computes_nonzero (tree expr
)
442 if (expr_computes_nonzero (expr
))
445 /* If we have an expression of the form &X->a, then the expression
446 is nonnull if X is nonnull. */
447 if (TREE_CODE (expr
) == ADDR_EXPR
)
449 tree base
= get_base_address (TREE_OPERAND (expr
, 0));
451 if (base
!= NULL_TREE
452 && TREE_CODE (base
) == INDIRECT_REF
453 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
455 value_range_t
*vr
= get_value_range (TREE_OPERAND (base
, 0));
456 if (range_is_nonnull (vr
))
465 /* Compare two values VAL1 and VAL2. Return
467 -2 if VAL1 and VAL2 cannot be compared at compile-time,
470 +1 if VAL1 > VAL2, and
473 This is similar to tree_int_cst_compare but supports pointer values
474 and values that cannot be compared at compile time. */
477 compare_values (tree val1
, tree val2
)
482 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
484 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1
))
485 == POINTER_TYPE_P (TREE_TYPE (val2
)));
487 /* Do some limited symbolic comparisons. */
488 if (!POINTER_TYPE_P (TREE_TYPE (val1
)))
490 /* We can determine some comparisons against +INF and -INF even
491 if the other value is an expression. */
492 if (val1
== TYPE_MAX_VALUE (TREE_TYPE (val1
))
493 && TREE_CODE (val2
) == MINUS_EXPR
)
495 /* +INF > NAME - CST. */
498 else if (val1
== TYPE_MIN_VALUE (TREE_TYPE (val1
))
499 && TREE_CODE (val2
) == PLUS_EXPR
)
501 /* -INF < NAME + CST. */
504 else if (TREE_CODE (val1
) == MINUS_EXPR
505 && val2
== TYPE_MAX_VALUE (TREE_TYPE (val2
)))
507 /* NAME - CST < +INF. */
510 else if (TREE_CODE (val1
) == PLUS_EXPR
511 && val2
== TYPE_MIN_VALUE (TREE_TYPE (val2
)))
513 /* NAME + CST > -INF. */
518 if ((TREE_CODE (val1
) == SSA_NAME
519 || TREE_CODE (val1
) == PLUS_EXPR
520 || TREE_CODE (val1
) == MINUS_EXPR
)
521 && (TREE_CODE (val2
) == SSA_NAME
522 || TREE_CODE (val2
) == PLUS_EXPR
523 || TREE_CODE (val2
) == MINUS_EXPR
))
527 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
528 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
529 same name, return -2. */
530 if (TREE_CODE (val1
) == SSA_NAME
)
537 n1
= TREE_OPERAND (val1
, 0);
538 c1
= TREE_OPERAND (val1
, 1);
541 if (TREE_CODE (val2
) == SSA_NAME
)
548 n2
= TREE_OPERAND (val2
, 0);
549 c2
= TREE_OPERAND (val2
, 1);
552 /* Both values must use the same name. */
556 if (TREE_CODE (val1
) == SSA_NAME
)
558 if (TREE_CODE (val2
) == SSA_NAME
)
561 else if (TREE_CODE (val2
) == PLUS_EXPR
)
562 /* NAME < NAME + CST */
564 else if (TREE_CODE (val2
) == MINUS_EXPR
)
565 /* NAME > NAME - CST */
568 else if (TREE_CODE (val1
) == PLUS_EXPR
)
570 if (TREE_CODE (val2
) == SSA_NAME
)
571 /* NAME + CST > NAME */
573 else if (TREE_CODE (val2
) == PLUS_EXPR
)
574 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
575 return compare_values (c1
, c2
);
576 else if (TREE_CODE (val2
) == MINUS_EXPR
)
577 /* NAME + CST1 > NAME - CST2 */
580 else if (TREE_CODE (val1
) == MINUS_EXPR
)
582 if (TREE_CODE (val2
) == SSA_NAME
)
583 /* NAME - CST < NAME */
585 else if (TREE_CODE (val2
) == PLUS_EXPR
)
586 /* NAME - CST1 < NAME + CST2 */
588 else if (TREE_CODE (val2
) == MINUS_EXPR
)
589 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
590 C1 and C2 are swapped in the call to compare_values. */
591 return compare_values (c2
, c1
);
597 /* We cannot compare non-constants. */
598 if (!is_gimple_min_invariant (val1
) || !is_gimple_min_invariant (val2
))
601 /* We cannot compare overflowed values. */
602 if (TREE_OVERFLOW (val1
) || TREE_OVERFLOW (val2
))
605 if (!POINTER_TYPE_P (TREE_TYPE (val1
)))
606 return tree_int_cst_compare (val1
, val2
);
611 /* First see if VAL1 and VAL2 are not the same. */
612 if (val1
== val2
|| operand_equal_p (val1
, val2
, 0))
615 /* If VAL1 is a lower address than VAL2, return -1. */
616 t
= fold_binary (LT_EXPR
, boolean_type_node
, val1
, val2
);
617 if (t
== boolean_true_node
)
620 /* If VAL1 is a higher address than VAL2, return +1. */
621 t
= fold_binary (GT_EXPR
, boolean_type_node
, val1
, val2
);
622 if (t
== boolean_true_node
)
625 /* If VAL1 is different than VAL2, return +2. */
626 t
= fold_binary (NE_EXPR
, boolean_type_node
, val1
, val2
);
627 if (t
== boolean_true_node
)
635 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
636 0 if VAL is not inside VR,
637 -2 if we cannot tell either way. */
640 value_inside_range (tree val
, value_range_t
*vr
)
644 cmp1
= compare_values (val
, vr
->min
);
645 if (cmp1
== -2 || cmp1
== 2)
648 cmp2
= compare_values (val
, vr
->max
);
649 if (cmp2
== -2 || cmp2
== 2)
652 return (cmp1
== 0 || cmp1
== 1) && (cmp2
== -1 || cmp2
== 0);
656 /* Return true if value ranges VR0 and VR1 have a non-empty
660 value_ranges_intersect_p (value_range_t
*vr0
, value_range_t
*vr1
)
662 return (value_inside_range (vr1
->min
, vr0
) == 1
663 || value_inside_range (vr1
->max
, vr0
) == 1
664 || value_inside_range (vr0
->min
, vr1
) == 1
665 || value_inside_range (vr0
->max
, vr1
) == 1);
669 /* Return true if VR includes the value zero, false otherwise. */
672 range_includes_zero_p (value_range_t
*vr
)
676 gcc_assert (vr
->type
!= VR_UNDEFINED
677 && vr
->type
!= VR_VARYING
678 && !symbolic_range_p (vr
));
680 zero
= build_int_cst (TREE_TYPE (vr
->min
), 0);
681 return (value_inside_range (zero
, vr
) == 1);
685 /* Extract value range information from an ASSERT_EXPR EXPR and store
689 extract_range_from_assert (value_range_t
*vr_p
, tree expr
)
691 tree var
, cond
, limit
, min
, max
, type
;
692 value_range_t
*var_vr
, *limit_vr
;
693 enum tree_code cond_code
;
695 var
= ASSERT_EXPR_VAR (expr
);
696 cond
= ASSERT_EXPR_COND (expr
);
698 gcc_assert (COMPARISON_CLASS_P (cond
));
700 /* Find VAR in the ASSERT_EXPR conditional. */
701 if (var
== TREE_OPERAND (cond
, 0))
703 /* If the predicate is of the form VAR COMP LIMIT, then we just
704 take LIMIT from the RHS and use the same comparison code. */
705 limit
= TREE_OPERAND (cond
, 1);
706 cond_code
= TREE_CODE (cond
);
710 /* If the predicate is of the form LIMIT COMP VAR, then we need
711 to flip around the comparison code to create the proper range
713 limit
= TREE_OPERAND (cond
, 0);
714 cond_code
= opposite_comparison (TREE_CODE (cond
));
717 type
= TREE_TYPE (limit
);
718 gcc_assert (limit
!= var
);
720 /* For pointer arithmetic, we only keep track of pointer equality
722 if (POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
724 set_value_range_to_varying (vr_p
);
728 /* If LIMIT is another SSA name and LIMIT has a range of its own,
729 try to use LIMIT's range to avoid creating symbolic ranges
731 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
733 /* LIMIT's range is only interesting if it has any useful information. */
735 && (limit_vr
->type
== VR_UNDEFINED
736 || limit_vr
->type
== VR_VARYING
737 || symbolic_range_p (limit_vr
)))
740 /* Special handling for integral types with super-types. Some FEs
741 construct integral types derived from other types and restrict
742 the range of values these new types may take.
744 It may happen that LIMIT is actually smaller than TYPE's minimum
745 value. For instance, the Ada FE is generating code like this
748 D.1480_32 = nam_30 - 300000361;
749 if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
751 D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
753 All the names are of type types__name_id___XDLU_300000000__399999999
754 which has min == 300000000 and max == 399999999. This means that
755 the ASSERT_EXPR would try to create the range [3000000, 1] which
758 The fact that the type specifies MIN and MAX values does not
759 automatically mean that every variable of that type will always
760 be within that range, so the predicate may well be true at run
761 time. If we had symbolic -INF and +INF values, we could
762 represent this range, but we currently represent -INF and +INF
763 using the type's min and max values.
765 So, the only sensible thing we can do for now is set the
766 resulting range to VR_VARYING. TODO, would having symbolic -INF
767 and +INF values be worth the trouble? */
768 if (TREE_CODE (limit
) != SSA_NAME
769 && INTEGRAL_TYPE_P (type
)
772 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
774 tree type_min
= TYPE_MIN_VALUE (type
);
775 int cmp
= compare_values (limit
, type_min
);
777 /* For < or <= comparisons, if LIMIT is smaller than
778 TYPE_MIN, set the range to VR_VARYING. */
779 if (cmp
== -1 || cmp
== 0)
781 set_value_range_to_varying (vr_p
);
785 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
787 tree type_max
= TYPE_MIN_VALUE (type
);
788 int cmp
= compare_values (limit
, type_max
);
790 /* For > or >= comparisons, if LIMIT is bigger than
791 TYPE_MAX, set the range to VR_VARYING. */
792 if (cmp
== 1 || cmp
== 0)
794 set_value_range_to_varying (vr_p
);
800 /* The new range has the same set of equivalences of VAR's range. */
801 gcc_assert (vr_p
->equiv
== NULL
);
802 vr_p
->equiv
= BITMAP_ALLOC (NULL
);
803 add_equivalence (vr_p
->equiv
, var
);
805 /* Extract a new range based on the asserted comparison for VAR and
806 LIMIT's value range. Notice that if LIMIT has an anti-range, we
807 will only use it for equality comparisons (EQ_EXPR). For any
808 other kind of assertion, we cannot derive a range from LIMIT's
809 anti-range that can be used to describe the new range. For
810 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
811 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
812 no single range for x_2 that could describe LE_EXPR, so we might
813 as well build the range [b_4, +INF] for it. */
814 if (cond_code
== EQ_EXPR
)
816 enum value_range_type range_type
;
820 range_type
= limit_vr
->type
;
826 range_type
= VR_RANGE
;
831 set_value_range (vr_p
, range_type
, min
, max
, vr_p
->equiv
);
833 /* When asserting the equality VAR == LIMIT and LIMIT is another
834 SSA name, the new range will also inherit the equivalence set
836 if (TREE_CODE (limit
) == SSA_NAME
)
837 add_equivalence (vr_p
->equiv
, limit
);
839 else if (cond_code
== NE_EXPR
)
841 /* As described above, when LIMIT's range is an anti-range and
842 this assertion is an inequality (NE_EXPR), then we cannot
843 derive anything from the anti-range. For instance, if
844 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
845 not imply that VAR's range is [0, 0]. So, in the case of
846 anti-ranges, we just assert the inequality using LIMIT and
847 not its anti-range. */
849 || limit_vr
->type
== VR_ANTI_RANGE
)
860 /* If MIN and MAX cover the whole range for their type, then
861 just use the original LIMIT. */
862 if (INTEGRAL_TYPE_P (type
)
863 && min
== TYPE_MIN_VALUE (type
)
864 && max
== TYPE_MAX_VALUE (type
))
867 set_value_range (vr_p
, VR_ANTI_RANGE
, min
, max
, vr_p
->equiv
);
869 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
871 min
= TYPE_MIN_VALUE (type
);
873 if (limit_vr
== NULL
|| limit_vr
->type
== VR_ANTI_RANGE
)
877 /* If LIMIT_VR is of the form [N1, N2], we need to build the
878 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
883 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
884 if (cond_code
== LT_EXPR
)
886 tree one
= build_int_cst (type
, 1);
887 max
= fold (build (MINUS_EXPR
, type
, max
, one
));
890 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
892 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
894 max
= TYPE_MAX_VALUE (type
);
896 if (limit_vr
== NULL
|| limit_vr
->type
== VR_ANTI_RANGE
)
900 /* If LIMIT_VR is of the form [N1, N2], we need to build the
901 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
906 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
907 if (cond_code
== GT_EXPR
)
909 tree one
= build_int_cst (type
, 1);
910 min
= fold (build (PLUS_EXPR
, type
, min
, one
));
913 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
918 /* If VAR already had a known range and the two ranges have a
919 non-empty intersection, we can refine the resulting range.
920 Since the assert expression creates an equivalency and at the
921 same time it asserts a predicate, we can take the intersection of
922 the two ranges to get better precision. */
923 var_vr
= get_value_range (var
);
924 if (var_vr
->type
== VR_RANGE
925 && vr_p
->type
== VR_RANGE
926 && value_ranges_intersect_p (var_vr
, vr_p
))
928 /* Use the larger of the two minimums. */
929 if (compare_values (vr_p
->min
, var_vr
->min
) == -1)
934 /* Use the smaller of the two maximums. */
935 if (compare_values (vr_p
->max
, var_vr
->max
) == 1)
940 set_value_range (vr_p
, vr_p
->type
, min
, max
, vr_p
->equiv
);
945 /* Extract range information from SSA name VAR and store it in VR. If
946 VAR has an interesting range, use it. Otherwise, create the
947 range [VAR, VAR] and return it. This is useful in situations where
948 we may have conditionals testing values of VARYING names. For
955 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
959 extract_range_from_ssa_name (value_range_t
*vr
, tree var
)
961 value_range_t
*var_vr
= get_value_range (var
);
963 if (var_vr
->type
!= VR_UNDEFINED
&& var_vr
->type
!= VR_VARYING
)
964 copy_value_range (vr
, var_vr
);
966 set_value_range (vr
, VR_RANGE
, var
, var
, NULL
);
968 add_equivalence (vr
->equiv
, var
);
972 /* Wrapper around int_const_binop. If the operation overflows and we
973 are not using wrapping arithmetic, then adjust the result to be
974 -INF or +INF depending on CODE, VAL1 and VAL2. */
977 vrp_int_const_binop (enum tree_code code
, tree val1
, tree val2
)
982 return int_const_binop (code
, val1
, val2
, 0);
984 /* If we are not using wrapping arithmetic, operate symbolically
986 res
= int_const_binop (code
, val1
, val2
, 0);
988 /* If the operation overflowed but neither VAL1 nor VAL2 are
989 overflown, return -INF or +INF depending on whether VAL1 CODE
990 VAL2 is a growing function or not. */
991 if (TREE_OVERFLOW (res
)
992 && !TREE_OVERFLOW (val1
)
993 && !TREE_OVERFLOW (val2
))
996 int sgn1
= tree_int_cst_sgn (val1
);
997 int sgn2
= tree_int_cst_sgn (val2
);
999 /* Notice that we only need to handle the restricted set of
1000 operations handled by extract_range_from_binary_expr. */
1001 if (((code
== PLUS_EXPR
|| code
== MAX_EXPR
) && sgn2
>= 0)
1002 || (code
== MULT_EXPR
&& sgn1
== sgn2
)
1003 || (code
== MINUS_EXPR
&& sgn2
< 0))
1007 return TYPE_MAX_VALUE (TREE_TYPE (res
));
1009 return TYPE_MIN_VALUE (TREE_TYPE (res
));
1016 /* Extract range information from a binary expression EXPR based on
1017 the ranges of each of its operands and the expression code. */
1020 extract_range_from_binary_expr (value_range_t
*vr
, tree expr
)
1022 enum tree_code code
= TREE_CODE (expr
);
1023 tree op0
, op1
, min
, max
;
1025 value_range_t vr0
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
1026 value_range_t vr1
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
1028 /* Not all binary expressions can be applied to ranges in a
1029 meaningful way. Handle only arithmetic operations. */
1030 if (code
!= PLUS_EXPR
1031 && code
!= MINUS_EXPR
1032 && code
!= MULT_EXPR
1033 && code
!= TRUNC_DIV_EXPR
1034 && code
!= FLOOR_DIV_EXPR
1035 && code
!= CEIL_DIV_EXPR
1036 && code
!= EXACT_DIV_EXPR
1037 && code
!= ROUND_DIV_EXPR
1040 && code
!= TRUTH_ANDIF_EXPR
1041 && code
!= TRUTH_ORIF_EXPR
1042 && code
!= TRUTH_AND_EXPR
1043 && code
!= TRUTH_OR_EXPR
1044 && code
!= TRUTH_XOR_EXPR
)
1046 set_value_range_to_varying (vr
);
1050 /* Get value ranges for each operand. For constant operands, create
1051 a new value range with the operand to simplify processing. */
1052 op0
= TREE_OPERAND (expr
, 0);
1053 if (TREE_CODE (op0
) == SSA_NAME
)
1054 vr0
= *(get_value_range (op0
));
1055 else if (is_gimple_min_invariant (op0
))
1056 set_value_range (&vr0
, VR_RANGE
, op0
, op0
, NULL
);
1058 set_value_range_to_varying (&vr0
);
1060 op1
= TREE_OPERAND (expr
, 1);
1061 if (TREE_CODE (op1
) == SSA_NAME
)
1062 vr1
= *(get_value_range (op1
));
1063 else if (is_gimple_min_invariant (op1
))
1064 set_value_range (&vr1
, VR_RANGE
, op1
, op1
, NULL
);
1066 set_value_range_to_varying (&vr1
);
1068 /* If either range is UNDEFINED, so is the result. */
1069 if (vr0
.type
== VR_UNDEFINED
|| vr1
.type
== VR_UNDEFINED
)
1071 set_value_range_to_undefined (vr
);
1075 /* Refuse to operate on VARYING ranges, ranges of different kinds
1076 and symbolic ranges. TODO, we may be able to derive anti-ranges
1078 if (vr0
.type
== VR_VARYING
1079 || vr1
.type
== VR_VARYING
1080 || vr0
.type
!= vr1
.type
1081 || symbolic_range_p (&vr0
)
1082 || symbolic_range_p (&vr1
))
1084 set_value_range_to_varying (vr
);
1088 /* Now evaluate the expression to determine the new range. */
1089 if (POINTER_TYPE_P (TREE_TYPE (expr
))
1090 || POINTER_TYPE_P (TREE_TYPE (op0
))
1091 || POINTER_TYPE_P (TREE_TYPE (op1
)))
1093 /* For pointer types, we are really only interested in asserting
1094 whether the expression evaluates to non-NULL. FIXME, we used
1095 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1096 ivopts is generating expressions with pointer multiplication
1098 if (code
== PLUS_EXPR
)
1099 set_value_range_to_nonnull (vr
, TREE_TYPE (expr
));
1102 /* Subtracting from a pointer, may yield 0, so just drop the
1103 resulting range to varying. */
1104 set_value_range_to_varying (vr
);
1110 /* For integer ranges, apply the operation to each end of the
1111 range and see what we end up with. */
1112 if (code
== TRUTH_ANDIF_EXPR
1113 || code
== TRUTH_ORIF_EXPR
1114 || code
== TRUTH_AND_EXPR
1115 || code
== TRUTH_OR_EXPR
1116 || code
== TRUTH_XOR_EXPR
)
1118 /* Boolean expressions cannot be folded with int_const_binop. */
1119 min
= fold_binary (code
, TREE_TYPE (expr
), vr0
.min
, vr1
.min
);
1120 max
= fold_binary (code
, TREE_TYPE (expr
), vr0
.max
, vr1
.max
);
1122 else if (code
== PLUS_EXPR
1124 || code
== MAX_EXPR
)
1126 /* For operations that make the resulting range directly
1127 proportional to the original ranges, apply the operation to
1128 the same end of each range. */
1129 min
= vrp_int_const_binop (code
, vr0
.min
, vr1
.min
);
1130 max
= vrp_int_const_binop (code
, vr0
.max
, vr1
.max
);
1132 else if (code
== MULT_EXPR
1133 || code
== TRUNC_DIV_EXPR
1134 || code
== FLOOR_DIV_EXPR
1135 || code
== CEIL_DIV_EXPR
1136 || code
== EXACT_DIV_EXPR
1137 || code
== ROUND_DIV_EXPR
)
1142 /* Multiplications and divisions are a bit tricky to handle,
1143 depending on the mix of signs we have in the two ranges, we
1144 need to operate on different values to get the minimum and
1145 maximum values for the new range. One approach is to figure
1146 out all the variations of range combinations and do the
1149 However, this involves several calls to compare_values and it
1150 is pretty convoluted. It's simpler to do the 4 operations
1151 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
1152 MAX1) and then figure the smallest and largest values to form
1155 /* Divisions by zero result in a VARYING value. */
1156 if (code
!= MULT_EXPR
&& range_includes_zero_p (&vr1
))
1158 set_value_range_to_varying (vr
);
1162 /* Compute the 4 cross operations. */
1163 val
[0] = vrp_int_const_binop (code
, vr0
.min
, vr1
.min
);
1165 val
[1] = (vr1
.max
!= vr1
.min
)
1166 ? vrp_int_const_binop (code
, vr0
.min
, vr1
.max
)
1169 val
[2] = (vr0
.max
!= vr0
.min
)
1170 ? vrp_int_const_binop (code
, vr0
.max
, vr1
.min
)
1173 val
[3] = (vr0
.min
!= vr1
.min
&& vr0
.max
!= vr1
.max
)
1174 ? vrp_int_const_binop (code
, vr0
.max
, vr1
.max
)
1177 /* Set MIN to the minimum of VAL[i] and MAX to the maximum
1181 for (i
= 1; i
< 4; i
++)
1183 if (TREE_OVERFLOW (min
) || TREE_OVERFLOW (max
))
1188 if (TREE_OVERFLOW (val
[i
]))
1190 /* If we found an overflowed value, set MIN and MAX
1191 to it so that we set the resulting range to
1197 if (compare_values (val
[i
], min
) == -1)
1200 if (compare_values (val
[i
], max
) == 1)
1205 else if (code
== MINUS_EXPR
)
1207 /* For MINUS_EXPR, apply the operation to the opposite ends of
1209 min
= vrp_int_const_binop (code
, vr0
.min
, vr1
.max
);
1210 max
= vrp_int_const_binop (code
, vr0
.max
, vr1
.min
);
1215 /* If either MIN or MAX overflowed, then set the resulting range to
1217 if (TREE_OVERFLOW (min
) || TREE_OVERFLOW (max
))
1219 set_value_range_to_varying (vr
);
1223 cmp
= compare_values (min
, max
);
1224 if (cmp
== -2 || cmp
== 1)
1226 /* If the new range has its limits swapped around (MIN > MAX),
1227 then the operation caused one of them to wrap around, mark
1228 the new range VARYING. */
1229 set_value_range_to_varying (vr
);
1232 set_value_range (vr
, vr0
.type
, min
, max
, NULL
);
1236 /* Extract range information from a unary expression EXPR based on
1237 the range of its operand and the expression code. */
1240 extract_range_from_unary_expr (value_range_t
*vr
, tree expr
)
1242 enum tree_code code
= TREE_CODE (expr
);
1245 value_range_t vr0
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
1247 /* Refuse to operate on certain unary expressions for which we
1248 cannot easily determine a resulting range. */
1249 if (code
== FIX_TRUNC_EXPR
1250 || code
== FIX_CEIL_EXPR
1251 || code
== FIX_FLOOR_EXPR
1252 || code
== FIX_ROUND_EXPR
1253 || code
== FLOAT_EXPR
1254 || code
== BIT_NOT_EXPR
1255 || code
== NON_LVALUE_EXPR
1256 || code
== CONJ_EXPR
)
1258 set_value_range_to_varying (vr
);
1262 /* Get value ranges for the operand. For constant operands, create
1263 a new value range with the operand to simplify processing. */
1264 op0
= TREE_OPERAND (expr
, 0);
1265 if (TREE_CODE (op0
) == SSA_NAME
)
1266 vr0
= *(get_value_range (op0
));
1267 else if (is_gimple_min_invariant (op0
))
1268 set_value_range (&vr0
, VR_RANGE
, op0
, op0
, NULL
);
1270 set_value_range_to_varying (&vr0
);
1272 /* If VR0 is UNDEFINED, so is the result. */
1273 if (vr0
.type
== VR_UNDEFINED
)
1275 set_value_range_to_undefined (vr
);
1279 /* Refuse to operate on varying and symbolic ranges. Also, if the
1280 operand is neither a pointer nor an integral type, set the
1281 resulting range to VARYING. TODO, in some cases we may be able
1282 to derive anti-ranges (like non-zero values). */
1283 if (vr0
.type
== VR_VARYING
1284 || (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
1285 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
1286 || symbolic_range_p (&vr0
))
1288 set_value_range_to_varying (vr
);
1292 /* If the expression involves pointers, we are only interested in
1293 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
1294 if (POINTER_TYPE_P (TREE_TYPE (expr
)) || POINTER_TYPE_P (TREE_TYPE (op0
)))
1296 if (range_is_nonnull (&vr0
) || expr_computes_nonzero (expr
))
1297 set_value_range_to_nonnull (vr
, TREE_TYPE (expr
));
1298 else if (range_is_null (&vr0
))
1299 set_value_range_to_null (vr
, TREE_TYPE (expr
));
1301 set_value_range_to_varying (vr
);
1306 /* Handle unary expressions on integer ranges. */
1307 if (code
== NOP_EXPR
|| code
== CONVERT_EXPR
)
1309 tree inner_type
= TREE_TYPE (op0
);
1310 tree outer_type
= TREE_TYPE (expr
);
1312 /* When converting types of different sizes, set the result to
1313 VARYING. Things like sign extensions and precision loss may
1314 change the range. For instance, if x_3 is of type 'long long
1315 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1316 is impossible to know at compile time whether y_5 will be
1318 if (TYPE_SIZE (inner_type
) != TYPE_SIZE (outer_type
)
1319 || TYPE_PRECISION (inner_type
) != TYPE_PRECISION (outer_type
))
1321 set_value_range_to_varying (vr
);
1326 /* Apply the operation to each end of the range and see what we end
1328 if (code
== NEGATE_EXPR
1329 && !TYPE_UNSIGNED (TREE_TYPE (expr
)))
1331 /* Negating an anti-range doesn't really do anything to it. The
1332 new range will also not take on the same range of values
1333 excluded by the original anti-range. */
1334 if (vr0
.type
== VR_ANTI_RANGE
)
1336 copy_value_range (vr
, &vr0
);
1340 /* NEGATE_EXPR flips the range around. */
1341 min
= (vr0
.max
== TYPE_MAX_VALUE (TREE_TYPE (expr
)))
1342 ? TYPE_MIN_VALUE (TREE_TYPE (expr
))
1343 : fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.max
);
1345 max
= (vr0
.min
== TYPE_MIN_VALUE (TREE_TYPE (expr
)))
1346 ? TYPE_MAX_VALUE (TREE_TYPE (expr
))
1347 : fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.min
);
1349 else if (code
== ABS_EXPR
1350 && !TYPE_UNSIGNED (TREE_TYPE (expr
)))
1352 /* ABS_EXPR may flip the range around, if the original range
1353 included negative values. */
1354 min
= (vr0
.min
== TYPE_MIN_VALUE (TREE_TYPE (expr
)))
1355 ? TYPE_MAX_VALUE (TREE_TYPE (expr
))
1356 : fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.min
);
1358 max
= fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.max
);
1360 /* If the range was reversed, swap MIN and MAX. */
1361 if (compare_values (min
, max
) == 1)
1370 /* Otherwise, operate on each end of the range. */
1371 min
= fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.min
);
1372 max
= fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.max
);
1375 cmp
= compare_values (min
, max
);
1376 if (cmp
== -2 || cmp
== 1)
1378 /* If the new range has its limits swapped around (MIN > MAX),
1379 then the operation caused one of them to wrap around, mark
1380 the new range VARYING. */
1381 set_value_range_to_varying (vr
);
1384 set_value_range (vr
, vr0
.type
, min
, max
, NULL
);
1388 /* Extract range information from a comparison expression EXPR based
1389 on the range of its operand and the expression code. */
1392 extract_range_from_comparison (value_range_t
*vr
, tree expr
)
1394 tree val
= vrp_evaluate_conditional (expr
, false);
1397 /* Since this expression was found on the RHS of an assignment,
1398 its type may be different from _Bool. Convert VAL to EXPR's
1400 val
= fold_convert (TREE_TYPE (expr
), val
);
1401 set_value_range (vr
, VR_RANGE
, val
, val
, vr
->equiv
);
1404 set_value_range_to_varying (vr
);
1408 /* Try to compute a useful range out of expression EXPR and store it
1412 extract_range_from_expr (value_range_t
*vr
, tree expr
)
1414 enum tree_code code
= TREE_CODE (expr
);
1416 if (code
== ASSERT_EXPR
)
1417 extract_range_from_assert (vr
, expr
);
1418 else if (code
== SSA_NAME
)
1419 extract_range_from_ssa_name (vr
, expr
);
1420 else if (TREE_CODE_CLASS (code
) == tcc_binary
1421 || code
== TRUTH_ANDIF_EXPR
1422 || code
== TRUTH_ORIF_EXPR
1423 || code
== TRUTH_AND_EXPR
1424 || code
== TRUTH_OR_EXPR
1425 || code
== TRUTH_XOR_EXPR
)
1426 extract_range_from_binary_expr (vr
, expr
);
1427 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1428 extract_range_from_unary_expr (vr
, expr
);
1429 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1430 extract_range_from_comparison (vr
, expr
);
1431 else if (vrp_expr_computes_nonzero (expr
))
1432 set_value_range_to_nonnull (vr
, TREE_TYPE (expr
));
1433 else if (is_gimple_min_invariant (expr
))
1434 set_value_range (vr
, VR_RANGE
, expr
, expr
, NULL
);
1436 set_value_range_to_varying (vr
);
1439 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1440 would be profitable to adjust VR using scalar evolution information
1441 for VAR. If so, update VR with the new limits. */
1444 adjust_range_with_scev (value_range_t
*vr
, struct loop
*loop
, tree stmt
,
1447 tree init
, step
, chrec
;
1450 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1451 better opportunities than a regular range, but I'm not sure. */
1452 if (vr
->type
== VR_ANTI_RANGE
)
1455 chrec
= analyze_scalar_evolution (loop
, var
);
1456 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1459 init
= CHREC_LEFT (chrec
);
1460 step
= CHREC_RIGHT (chrec
);
1462 /* If STEP is symbolic, we can't know whether INIT will be the
1463 minimum or maximum value in the range. */
1464 if (!is_gimple_min_invariant (step
))
1467 /* Do not adjust ranges when chrec may wrap. */
1468 if (scev_probably_wraps_p (chrec_type (chrec
), init
, step
, stmt
,
1469 cfg_loops
->parray
[CHREC_VARIABLE (chrec
)],
1473 if (!POINTER_TYPE_P (TREE_TYPE (init
))
1474 && (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
))
1476 /* For VARYING or UNDEFINED ranges, just about anything we get
1477 from scalar evolutions should be better. */
1479 set_value_range (vr
, VR_RANGE
, TYPE_MIN_VALUE (TREE_TYPE (init
)),
1482 set_value_range (vr
, VR_RANGE
, init
, TYPE_MAX_VALUE (TREE_TYPE (init
)),
1485 else if (vr
->type
== VR_RANGE
)
1492 /* INIT is the maximum value. If INIT is lower than VR->MAX
1493 but no smaller than VR->MIN, set VR->MAX to INIT. */
1494 if (compare_values (init
, max
) == -1)
1498 /* If we just created an invalid range with the minimum
1499 greater than the maximum, take the minimum all the
1501 if (compare_values (min
, max
) == 1)
1502 min
= TYPE_MIN_VALUE (TREE_TYPE (min
));
1507 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1508 if (compare_values (init
, min
) == 1)
1512 /* If we just created an invalid range with the minimum
1513 greater than the maximum, take the maximum all the
1515 if (compare_values (min
, max
) == 1)
1516 max
= TYPE_MAX_VALUE (TREE_TYPE (max
));
1520 set_value_range (vr
, VR_RANGE
, min
, max
, vr
->equiv
);
1525 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1527 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1528 all the values in the ranges.
1530 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1532 - Return NULL_TREE if it is not always possible to determine the
1533 value of the comparison. */
1537 compare_ranges (enum tree_code comp
, value_range_t
*vr0
, value_range_t
*vr1
)
1539 /* VARYING or UNDEFINED ranges cannot be compared. */
1540 if (vr0
->type
== VR_VARYING
1541 || vr0
->type
== VR_UNDEFINED
1542 || vr1
->type
== VR_VARYING
1543 || vr1
->type
== VR_UNDEFINED
)
1546 /* Anti-ranges need to be handled separately. */
1547 if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
1549 /* If both are anti-ranges, then we cannot compute any
1551 if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
1554 /* These comparisons are never statically computable. */
1561 /* Equality can be computed only between a range and an
1562 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1563 if (vr0
->type
== VR_RANGE
)
1565 /* To simplify processing, make VR0 the anti-range. */
1566 value_range_t
*tmp
= vr0
;
1571 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1573 if (compare_values (vr0
->min
, vr1
->min
) == 0
1574 && compare_values (vr0
->max
, vr1
->max
) == 0)
1575 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1580 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1581 operands around and change the comparison code. */
1582 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1585 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1591 if (comp
== EQ_EXPR
)
1593 /* Equality may only be computed if both ranges represent
1594 exactly one value. */
1595 if (compare_values (vr0
->min
, vr0
->max
) == 0
1596 && compare_values (vr1
->min
, vr1
->max
) == 0)
1598 int cmp_min
= compare_values (vr0
->min
, vr1
->min
);
1599 int cmp_max
= compare_values (vr0
->max
, vr1
->max
);
1600 if (cmp_min
== 0 && cmp_max
== 0)
1601 return boolean_true_node
;
1602 else if (cmp_min
!= -2 && cmp_max
!= -2)
1603 return boolean_false_node
;
1608 else if (comp
== NE_EXPR
)
1612 /* If VR0 is completely to the left or completely to the right
1613 of VR1, they are always different. Notice that we need to
1614 make sure that both comparisons yield similar results to
1615 avoid comparing values that cannot be compared at
1617 cmp1
= compare_values (vr0
->max
, vr1
->min
);
1618 cmp2
= compare_values (vr0
->min
, vr1
->max
);
1619 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1620 return boolean_true_node
;
1622 /* If VR0 and VR1 represent a single value and are identical,
1624 else if (compare_values (vr0
->min
, vr0
->max
) == 0
1625 && compare_values (vr1
->min
, vr1
->max
) == 0
1626 && compare_values (vr0
->min
, vr1
->min
) == 0
1627 && compare_values (vr0
->max
, vr1
->max
) == 0)
1628 return boolean_false_node
;
1630 /* Otherwise, they may or may not be different. */
1634 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1638 /* If VR0 is to the left of VR1, return true. */
1639 tst
= compare_values (vr0
->max
, vr1
->min
);
1640 if ((comp
== LT_EXPR
&& tst
== -1)
1641 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1642 return boolean_true_node
;
1644 /* If VR0 is to the right of VR1, return false. */
1645 tst
= compare_values (vr0
->min
, vr1
->max
);
1646 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1647 || (comp
== LE_EXPR
&& tst
== 1))
1648 return boolean_false_node
;
1650 /* Otherwise, we don't know. */
1658 /* Given a value range VR, a value VAL and a comparison code COMP, return
1659 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1660 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1661 always returns false. Return NULL_TREE if it is not always
1662 possible to determine the value of the comparison. */
1665 compare_range_with_value (enum tree_code comp
, value_range_t
*vr
, tree val
)
1667 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
1670 /* Anti-ranges need to be handled separately. */
1671 if (vr
->type
== VR_ANTI_RANGE
)
1673 /* For anti-ranges, the only predicates that we can compute at
1674 compile time are equality and inequality. */
1681 /* ~[VAL, VAL] == VAL is always false. */
1682 if (compare_values (vr
->min
, val
) == 0
1683 && compare_values (vr
->max
, val
) == 0)
1684 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1689 if (comp
== EQ_EXPR
)
1691 /* EQ_EXPR may only be computed if VR represents exactly
1693 if (compare_values (vr
->min
, vr
->max
) == 0)
1695 int cmp
= compare_values (vr
->min
, val
);
1697 return boolean_true_node
;
1698 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1699 return boolean_false_node
;
1701 else if (compare_values (val
, vr
->min
) == -1
1702 || compare_values (vr
->max
, val
) == -1)
1703 return boolean_false_node
;
1707 else if (comp
== NE_EXPR
)
1709 /* If VAL is not inside VR, then they are always different. */
1710 if (compare_values (vr
->max
, val
) == -1
1711 || compare_values (vr
->min
, val
) == 1)
1712 return boolean_true_node
;
1714 /* If VR represents exactly one value equal to VAL, then return
1716 if (compare_values (vr
->min
, vr
->max
) == 0
1717 && compare_values (vr
->min
, val
) == 0)
1718 return boolean_false_node
;
1720 /* Otherwise, they may or may not be different. */
1723 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1727 /* If VR is to the left of VAL, return true. */
1728 tst
= compare_values (vr
->max
, val
);
1729 if ((comp
== LT_EXPR
&& tst
== -1)
1730 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1731 return boolean_true_node
;
1733 /* If VR is to the right of VAL, return false. */
1734 tst
= compare_values (vr
->min
, val
);
1735 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1736 || (comp
== LE_EXPR
&& tst
== 1))
1737 return boolean_false_node
;
1739 /* Otherwise, we don't know. */
1742 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1746 /* If VR is to the right of VAL, return true. */
1747 tst
= compare_values (vr
->min
, val
);
1748 if ((comp
== GT_EXPR
&& tst
== 1)
1749 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1750 return boolean_true_node
;
1752 /* If VR is to the left of VAL, return false. */
1753 tst
= compare_values (vr
->max
, val
);
1754 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1755 || (comp
== GE_EXPR
&& tst
== -1))
1756 return boolean_false_node
;
1758 /* Otherwise, we don't know. */
1766 /* Debugging dumps. */
1768 void dump_value_range (FILE *, value_range_t
*);
1769 void debug_value_range (value_range_t
*);
1770 void dump_all_value_ranges (FILE *);
1771 void debug_all_value_ranges (void);
1772 void dump_vr_equiv (FILE *, bitmap
);
1773 void debug_vr_equiv (bitmap
);
1776 /* Dump value range VR to FILE. */
1779 dump_value_range (FILE *file
, value_range_t
*vr
)
1782 fprintf (file
, "[]");
1783 else if (vr
->type
== VR_UNDEFINED
)
1784 fprintf (file
, "UNDEFINED");
1785 else if (vr
->type
== VR_RANGE
|| vr
->type
== VR_ANTI_RANGE
)
1787 tree type
= TREE_TYPE (vr
->min
);
1789 fprintf (file
, "%s[", (vr
->type
== VR_ANTI_RANGE
) ? "~" : "");
1791 if (INTEGRAL_TYPE_P (type
)
1792 && !TYPE_UNSIGNED (type
)
1793 && vr
->min
== TYPE_MIN_VALUE (type
))
1794 fprintf (file
, "-INF");
1796 print_generic_expr (file
, vr
->min
, 0);
1798 fprintf (file
, ", ");
1800 if (INTEGRAL_TYPE_P (type
)
1801 && vr
->max
== TYPE_MAX_VALUE (type
))
1802 fprintf (file
, "+INF");
1804 print_generic_expr (file
, vr
->max
, 0);
1806 fprintf (file
, "]");
1813 fprintf (file
, " EQUIVALENCES: { ");
1815 EXECUTE_IF_SET_IN_BITMAP (vr
->equiv
, 0, i
, bi
)
1817 print_generic_expr (file
, ssa_name (i
), 0);
1818 fprintf (file
, " ");
1822 fprintf (file
, "} (%u elements)", c
);
1825 else if (vr
->type
== VR_VARYING
)
1826 fprintf (file
, "VARYING");
1828 fprintf (file
, "INVALID RANGE");
1832 /* Dump value range VR to stderr. */
1835 debug_value_range (value_range_t
*vr
)
1837 dump_value_range (stderr
, vr
);
1841 /* Dump value ranges of all SSA_NAMEs to FILE. */
1844 dump_all_value_ranges (FILE *file
)
1848 for (i
= 0; i
< num_ssa_names
; i
++)
1852 print_generic_expr (file
, ssa_name (i
), 0);
1853 fprintf (file
, ": ");
1854 dump_value_range (file
, vr_value
[i
]);
1855 fprintf (file
, "\n");
1859 fprintf (file
, "\n");
1863 /* Dump all value ranges to stderr. */
1866 debug_all_value_ranges (void)
1868 dump_all_value_ranges (stderr
);
1872 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1873 create a new SSA name N and return the assertion assignment
1874 'V = ASSERT_EXPR <V, V OP W>'. */
1877 build_assert_expr_for (tree cond
, tree v
)
1881 gcc_assert (TREE_CODE (v
) == SSA_NAME
);
1882 n
= duplicate_ssa_name (v
, NULL_TREE
);
1884 if (COMPARISON_CLASS_P (cond
))
1886 tree a
= build (ASSERT_EXPR
, TREE_TYPE (v
), v
, cond
);
1887 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, a
);
1889 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1891 /* Given !V, build the assignment N = false. */
1892 tree op0
= TREE_OPERAND (cond
, 0);
1893 gcc_assert (op0
== v
);
1894 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, boolean_false_node
);
1896 else if (TREE_CODE (cond
) == SSA_NAME
)
1898 /* Given V, build the assignment N = true. */
1899 gcc_assert (v
== cond
);
1900 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, boolean_true_node
);
1905 SSA_NAME_DEF_STMT (n
) = assertion
;
1907 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1908 operand of the ASSERT_EXPR. Register the new name and the old one
1909 in the replacement table so that we can fix the SSA web after
1910 adding all the ASSERT_EXPRs. */
1911 register_new_name_mapping (n
, v
);
1917 /* Return false if EXPR is a predicate expression involving floating
1921 fp_predicate (tree expr
)
1923 return (COMPARISON_CLASS_P (expr
)
1924 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr
, 0))));
1928 /* If the range of values taken by OP can be inferred after STMT executes,
1929 return the comparison code (COMP_CODE_P) and value (VAL_P) that
1930 describes the inferred range. Return true if a range could be
1934 infer_value_range (tree stmt
, tree op
, enum tree_code
*comp_code_p
, tree
*val_p
)
1937 *comp_code_p
= ERROR_MARK
;
1939 /* Do not attempt to infer anything in names that flow through
1941 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
1944 /* Similarly, don't infer anything from statements that may throw
1946 if (tree_could_throw_p (stmt
))
1949 if (POINTER_TYPE_P (TREE_TYPE (op
)))
1952 unsigned num_uses
, num_derefs
;
1954 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
1955 if (num_derefs
> 0 && flag_delete_null_pointer_checks
)
1957 /* We can only assume that a pointer dereference will yield
1958 non-NULL if -fdelete-null-pointer-checks is enabled. */
1959 *val_p
= build_int_cst (TREE_TYPE (op
), 0);
1960 *comp_code_p
= NE_EXPR
;
1969 void dump_asserts_for (FILE *, tree
);
1970 void debug_asserts_for (tree
);
1971 void dump_all_asserts (FILE *);
1972 void debug_all_asserts (void);
1974 /* Dump all the registered assertions for NAME to FILE. */
1977 dump_asserts_for (FILE *file
, tree name
)
1981 fprintf (file
, "Assertions to be inserted for ");
1982 print_generic_expr (file
, name
, 0);
1983 fprintf (file
, "\n");
1985 loc
= asserts_for
[SSA_NAME_VERSION (name
)];
1988 fprintf (file
, "\t");
1989 print_generic_expr (file
, bsi_stmt (loc
->si
), 0);
1990 fprintf (file
, "\n\tBB #%d", loc
->bb
->index
);
1993 fprintf (file
, "\n\tEDGE %d->%d", loc
->e
->src
->index
,
1994 loc
->e
->dest
->index
);
1995 dump_edge_info (file
, loc
->e
, 0);
1997 fprintf (file
, "\n\tPREDICATE: ");
1998 print_generic_expr (file
, name
, 0);
1999 fprintf (file
, " %s ", tree_code_name
[(int)loc
->comp_code
]);
2000 print_generic_expr (file
, loc
->val
, 0);
2001 fprintf (file
, "\n\n");
2005 fprintf (file
, "\n");
2009 /* Dump all the registered assertions for NAME to stderr. */
2012 debug_asserts_for (tree name
)
2014 dump_asserts_for (stderr
, name
);
2018 /* Dump all the registered assertions for all the names to FILE. */
2021 dump_all_asserts (FILE *file
)
2026 fprintf (file
, "\nASSERT_EXPRs to be inserted\n\n");
2027 EXECUTE_IF_SET_IN_BITMAP (need_assert_for
, 0, i
, bi
)
2028 dump_asserts_for (file
, ssa_name (i
));
2029 fprintf (file
, "\n");
2033 /* Dump all the registered assertions for all the names to stderr. */
2036 debug_all_asserts (void)
2038 dump_all_asserts (stderr
);
2042 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2043 'NAME COMP_CODE VAL' at a location that dominates block BB or
2044 E->DEST, then register this location as a possible insertion point
2045 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2047 BB, E and SI provide the exact insertion point for the new
2048 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
2049 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2050 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2051 must not be NULL. */
2054 register_new_assert_for (tree name
,
2055 enum tree_code comp_code
,
2059 block_stmt_iterator si
)
2061 assert_locus_t n
, loc
, last_loc
;
2063 basic_block dest_bb
;
2065 #if defined ENABLE_CHECKING
2066 gcc_assert (bb
== NULL
|| e
== NULL
);
2069 gcc_assert (TREE_CODE (bsi_stmt (si
)) != COND_EXPR
2070 && TREE_CODE (bsi_stmt (si
)) != SWITCH_EXPR
);
2073 /* The new assertion A will be inserted at BB or E. We need to
2074 determine if the new location is dominated by a previously
2075 registered location for A. If we are doing an edge insertion,
2076 assume that A will be inserted at E->DEST. Note that this is not
2079 If E is a critical edge, it will be split. But even if E is
2080 split, the new block will dominate the same set of blocks that
2083 The reverse, however, is not true, blocks dominated by E->DEST
2084 will not be dominated by the new block created to split E. So,
2085 if the insertion location is on a critical edge, we will not use
2086 the new location to move another assertion previously registered
2087 at a block dominated by E->DEST. */
2088 dest_bb
= (bb
) ? bb
: e
->dest
;
2090 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2091 VAL at a block dominating DEST_BB, then we don't need to insert a new
2092 one. Similarly, if the same assertion already exists at a block
2093 dominated by DEST_BB and the new location is not on a critical
2094 edge, then update the existing location for the assertion (i.e.,
2095 move the assertion up in the dominance tree).
2097 Note, this is implemented as a simple linked list because there
2098 should not be more than a handful of assertions registered per
2099 name. If this becomes a performance problem, a table hashed by
2100 COMP_CODE and VAL could be implemented. */
2101 loc
= asserts_for
[SSA_NAME_VERSION (name
)];
2106 if (loc
->comp_code
== comp_code
2108 || operand_equal_p (loc
->val
, val
, 0)))
2110 /* If the assertion NAME COMP_CODE VAL has already been
2111 registered at a basic block that dominates DEST_BB, then
2112 we don't need to insert the same assertion again. Note
2113 that we don't check strict dominance here to avoid
2114 replicating the same assertion inside the same basic
2115 block more than once (e.g., when a pointer is
2116 dereferenced several times inside a block).
2118 An exception to this rule are edge insertions. If the
2119 new assertion is to be inserted on edge E, then it will
2120 dominate all the other insertions that we may want to
2121 insert in DEST_BB. So, if we are doing an edge
2122 insertion, don't do this dominance check. */
2124 && dominated_by_p (CDI_DOMINATORS
, dest_bb
, loc
->bb
))
2127 /* Otherwise, if E is not a critical edge and DEST_BB
2128 dominates the existing location for the assertion, move
2129 the assertion up in the dominance tree by updating its
2130 location information. */
2131 if ((e
== NULL
|| !EDGE_CRITICAL_P (e
))
2132 && dominated_by_p (CDI_DOMINATORS
, loc
->bb
, dest_bb
))
2141 /* Update the last node of the list and move to the next one. */
2146 /* If we didn't find an assertion already registered for
2147 NAME COMP_CODE VAL, add a new one at the end of the list of
2148 assertions associated with NAME. */
2149 n
= xmalloc (sizeof (*n
));
2153 n
->comp_code
= comp_code
;
2160 asserts_for
[SSA_NAME_VERSION (name
)] = n
;
2162 bitmap_set_bit (need_assert_for
, SSA_NAME_VERSION (name
));
2166 /* Try to register an edge assertion for SSA name NAME on edge E for
2167 the conditional jump pointed by SI. Return true if an assertion
2168 for NAME could be registered. */
2171 register_edge_assert_for (tree name
, edge e
, block_stmt_iterator si
)
2174 enum tree_code comp_code
;
2176 stmt
= bsi_stmt (si
);
2178 /* Do not attempt to infer anything in names that flow through
2180 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
))
2183 /* If NAME was not found in the sub-graph reachable from E, then
2184 there's nothing to do. */
2185 if (!TEST_BIT (found_in_subgraph
, SSA_NAME_VERSION (name
)))
2188 /* We found a use of NAME in the sub-graph rooted at E->DEST.
2189 Register an assertion for NAME according to the value that NAME
2191 if (TREE_CODE (stmt
) == COND_EXPR
)
2193 /* If BB ends in a COND_EXPR then NAME then we should insert
2194 the original predicate on EDGE_TRUE_VALUE and the
2195 opposite predicate on EDGE_FALSE_VALUE. */
2196 tree cond
= COND_EXPR_COND (stmt
);
2197 bool is_else_edge
= (e
->flags
& EDGE_FALSE_VALUE
) != 0;
2199 /* Predicates may be a single SSA name or NAME OP VAL. */
2202 /* If the predicate is a name, it must be NAME, in which
2203 case we create the predicate NAME == true or
2204 NAME == false accordingly. */
2205 comp_code
= EQ_EXPR
;
2206 val
= (is_else_edge
) ? boolean_false_node
: boolean_true_node
;
2210 /* Otherwise, we have a comparison of the form NAME COMP VAL
2211 or VAL COMP NAME. */
2212 if (name
== TREE_OPERAND (cond
, 1))
2214 /* If the predicate is of the form VAL COMP NAME, flip
2215 COMP around because we need to register NAME as the
2216 first operand in the predicate. */
2217 comp_code
= opposite_comparison (TREE_CODE (cond
));
2218 val
= TREE_OPERAND (cond
, 0);
2222 /* The comparison is of the form NAME COMP VAL, so the
2223 comparison code remains unchanged. */
2224 comp_code
= TREE_CODE (cond
);
2225 val
= TREE_OPERAND (cond
, 1);
2228 /* If we are inserting the assertion on the ELSE edge, we
2229 need to invert the sign comparison. */
2231 comp_code
= invert_tree_comparison (comp_code
, 0);
2236 /* FIXME. Handle SWITCH_EXPR. */
2240 register_new_assert_for (name
, comp_code
, val
, NULL
, e
, si
);
2245 static bool find_assert_locations (basic_block bb
);
2247 /* Determine whether the outgoing edges of BB should receive an
2248 ASSERT_EXPR for each of the operands of BB's last statement. The
2249 last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2251 If any of the sub-graphs rooted at BB have an interesting use of
2252 the predicate operands, an assert location node is added to the
2253 list of assertions for the corresponding operands. */
2256 find_conditional_asserts (basic_block bb
)
2259 block_stmt_iterator last_si
;
2265 need_assert
= false;
2266 last_si
= bsi_last (bb
);
2267 last
= bsi_stmt (last_si
);
2269 /* Look for uses of the operands in each of the sub-graphs
2270 rooted at BB. We need to check each of the outgoing edges
2271 separately, so that we know what kind of ASSERT_EXPR to
2273 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2278 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2279 Otherwise, when we finish traversing each of the sub-graphs, we
2280 won't know whether the variables were found in the sub-graphs or
2281 if they had been found in a block upstream from BB. */
2282 FOR_EACH_SSA_TREE_OPERAND (op
, last
, iter
, SSA_OP_USE
)
2283 RESET_BIT (found_in_subgraph
, SSA_NAME_VERSION (op
));
2285 /* Traverse the strictly dominated sub-graph rooted at E->DEST
2286 to determine if any of the operands in the conditional
2287 predicate are used. */
2289 need_assert
|= find_assert_locations (e
->dest
);
2291 /* Register the necessary assertions for each operand in the
2292 conditional predicate. */
2293 FOR_EACH_SSA_TREE_OPERAND (op
, last
, iter
, SSA_OP_USE
)
2294 need_assert
|= register_edge_assert_for (op
, e
, last_si
);
2297 /* Finally, indicate that we have found the operands in the
2299 FOR_EACH_SSA_TREE_OPERAND (op
, last
, iter
, SSA_OP_USE
)
2300 SET_BIT (found_in_subgraph
, SSA_NAME_VERSION (op
));
2306 /* Traverse all the statements in block BB looking for statements that
2307 may generate useful assertions for the SSA names in their operand.
2308 If a statement produces a useful assertion A for name N_i, then the
2309 list of assertions already generated for N_i is scanned to
2310 determine if A is actually needed.
2312 If N_i already had the assertion A at a location dominating the
2313 current location, then nothing needs to be done. Otherwise, the
2314 new location for A is recorded instead.
2316 1- For every statement S in BB, all the variables used by S are
2317 added to bitmap FOUND_IN_SUBGRAPH.
2319 2- If statement S uses an operand N in a way that exposes a known
2320 value range for N, then if N was not already generated by an
2321 ASSERT_EXPR, create a new assert location for N. For instance,
2322 if N is a pointer and the statement dereferences it, we can
2323 assume that N is not NULL.
2325 3- COND_EXPRs are a special case of #2. We can derive range
2326 information from the predicate but need to insert different
2327 ASSERT_EXPRs for each of the sub-graphs rooted at the
2328 conditional block. If the last statement of BB is a conditional
2329 expression of the form 'X op Y', then
2331 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2333 b) If the conditional is the only entry point to the sub-graph
2334 corresponding to the THEN_CLAUSE, recurse into it. On
2335 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2336 an ASSERT_EXPR is added for the corresponding variable.
2338 c) Repeat step (b) on the ELSE_CLAUSE.
2340 d) Mark X and Y in FOUND_IN_SUBGRAPH.
2349 In this case, an assertion on the THEN clause is useful to
2350 determine that 'a' is always 9 on that edge. However, an assertion
2351 on the ELSE clause would be unnecessary.
2353 4- If BB does not end in a conditional expression, then we recurse
2354 into BB's dominator children.
2356 At the end of the recursive traversal, every SSA name will have a
2357 list of locations where ASSERT_EXPRs should be added. When a new
2358 location for name N is found, it is registered by calling
2359 register_new_assert_for. That function keeps track of all the
2360 registered assertions to prevent adding unnecessary assertions.
2361 For instance, if a pointer P_4 is dereferenced more than once in a
2362 dominator tree, only the location dominating all the dereference of
2363 P_4 will receive an ASSERT_EXPR.
2365 If this function returns true, then it means that there are names
2366 for which we need to generate ASSERT_EXPRs. Those assertions are
2367 inserted by process_assert_insertions.
2369 TODO. Handle SWITCH_EXPR. */
2372 find_assert_locations (basic_block bb
)
2374 block_stmt_iterator si
;
2379 if (TEST_BIT (blocks_visited
, bb
->index
))
2382 SET_BIT (blocks_visited
, bb
->index
);
2384 need_assert
= false;
2386 /* Traverse all PHI nodes in BB marking used operands. */
2387 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2389 use_operand_p arg_p
;
2392 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_USE
)
2394 tree arg
= USE_FROM_PTR (arg_p
);
2395 if (TREE_CODE (arg
) == SSA_NAME
)
2397 gcc_assert (is_gimple_reg (PHI_RESULT (phi
)));
2398 SET_BIT (found_in_subgraph
, SSA_NAME_VERSION (arg
));
2403 /* Traverse all the statements in BB marking used names and looking
2404 for statements that may infer assertions for their used operands. */
2406 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
2411 stmt
= bsi_stmt (si
);
2413 /* See if we can derive an assertion for any of STMT's operands. */
2414 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
2417 enum tree_code comp_code
;
2419 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
2420 the sub-graph of a conditional block, when we return from
2421 this recursive walk, our parent will use the
2422 FOUND_IN_SUBGRAPH bitset to determine if one of the
2423 operands it was looking for was present in the sub-graph. */
2424 SET_BIT (found_in_subgraph
, SSA_NAME_VERSION (op
));
2426 /* If OP is used only once, namely in this STMT, don't
2427 bother creating an ASSERT_EXPR for it. Such an
2428 ASSERT_EXPR would do nothing but increase compile time.
2429 Experiments show that with this simple check, we can save
2430 more than 20% of ASSERT_EXPRs. */
2431 if (has_single_use (op
))
2434 /* If OP is used in such a way that we can infer a value
2435 range for it, and we don't find a previous assertion for
2436 it, create a new assertion location node for OP. */
2437 if (infer_value_range (stmt
, op
, &comp_code
, &value
))
2439 register_new_assert_for (op
, comp_code
, value
, bb
, NULL
, si
);
2444 /* Remember the last statement of the block. */
2448 /* If BB's last statement is a conditional expression
2449 involving integer operands, recurse into each of the sub-graphs
2450 rooted at BB to determine if we need to add ASSERT_EXPRs. */
2452 && TREE_CODE (last
) == COND_EXPR
2453 && !fp_predicate (COND_EXPR_COND (last
))
2454 && !ZERO_SSA_OPERANDS (last
, SSA_OP_USE
))
2455 need_assert
|= find_conditional_asserts (bb
);
2457 /* Recurse into the dominator children of BB. */
2458 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2460 son
= next_dom_son (CDI_DOMINATORS
, son
))
2461 need_assert
|= find_assert_locations (son
);
2467 /* Create an ASSERT_EXPR for NAME and insert it in the location
2468 indicated by LOC. Return true if we made any edge insertions. */
2471 process_assert_insertions_for (tree name
, assert_locus_t loc
)
2473 /* Build the comparison expression NAME_i COMP_CODE VAL. */
2474 tree stmt
, cond
, assert_expr
;
2478 cond
= build (loc
->comp_code
, boolean_type_node
, name
, loc
->val
);
2479 assert_expr
= build_assert_expr_for (cond
, name
);
2483 /* We have been asked to insert the assertion on an edge. This
2484 is used only by COND_EXPR and SWITCH_EXPR assertions. */
2485 #if defined ENABLE_CHECKING
2486 gcc_assert (TREE_CODE (bsi_stmt (loc
->si
)) == COND_EXPR
2487 || TREE_CODE (bsi_stmt (loc
->si
)) == SWITCH_EXPR
);
2490 bsi_insert_on_edge (loc
->e
, assert_expr
);
2494 /* Otherwise, we can insert right after LOC->SI iff the
2495 statement must not be the last statement in the block. */
2496 stmt
= bsi_stmt (loc
->si
);
2497 if (!stmt_ends_bb_p (stmt
))
2499 bsi_insert_after (&loc
->si
, assert_expr
, BSI_SAME_STMT
);
2503 /* If STMT must be the last statement in BB, we can only insert new
2504 assertions on the non-abnormal edge out of BB. Note that since
2505 STMT is not control flow, there may only be one non-abnormal edge
2507 FOR_EACH_EDGE (e
, ei
, loc
->bb
->succs
)
2508 if (!(e
->flags
& EDGE_ABNORMAL
))
2510 bsi_insert_on_edge (e
, assert_expr
);
2518 /* Process all the insertions registered for every name N_i registered
2519 in NEED_ASSERT_FOR. The list of assertions to be inserted are
2520 found in ASSERTS_FOR[i]. */
2523 process_assert_insertions (void)
2527 bool update_edges_p
= false;
2528 int num_asserts
= 0;
2530 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2531 dump_all_asserts (dump_file
);
2533 EXECUTE_IF_SET_IN_BITMAP (need_assert_for
, 0, i
, bi
)
2535 assert_locus_t loc
= asserts_for
[i
];
2540 assert_locus_t next
= loc
->next
;
2541 update_edges_p
|= process_assert_insertions_for (ssa_name (i
), loc
);
2549 bsi_commit_edge_inserts ();
2551 if (dump_file
&& (dump_flags
& TDF_STATS
))
2552 fprintf (dump_file
, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
2557 /* Traverse the flowgraph looking for conditional jumps to insert range
2558 expressions. These range expressions are meant to provide information
2559 to optimizations that need to reason in terms of value ranges. They
2560 will not be expanded into RTL. For instance, given:
2569 this pass will transform the code into:
2575 x = ASSERT_EXPR <x, x < y>
2580 y = ASSERT_EXPR <y, x <= y>
2584 The idea is that once copy and constant propagation have run, other
2585 optimizations will be able to determine what ranges of values can 'x'
2586 take in different paths of the code, simply by checking the reaching
2587 definition of 'x'. */
2590 insert_range_assertions (void)
2596 found_in_subgraph
= sbitmap_alloc (num_ssa_names
);
2597 sbitmap_zero (found_in_subgraph
);
2599 blocks_visited
= sbitmap_alloc (last_basic_block
);
2600 sbitmap_zero (blocks_visited
);
2602 need_assert_for
= BITMAP_ALLOC (NULL
);
2603 asserts_for
= xmalloc (num_ssa_names
* sizeof (assert_locus_t
));
2604 memset (asserts_for
, 0, num_ssa_names
* sizeof (assert_locus_t
));
2606 calculate_dominance_info (CDI_DOMINATORS
);
2608 update_ssa_p
= false;
2609 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
2610 if (find_assert_locations (e
->dest
))
2611 update_ssa_p
= true;
2615 process_assert_insertions ();
2616 update_ssa (TODO_update_ssa_no_phi
);
2619 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2621 fprintf (dump_file
, "\nSSA form after inserting ASSERT_EXPRs\n");
2622 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
2625 sbitmap_free (found_in_subgraph
);
2627 BITMAP_FREE (need_assert_for
);
2631 /* Convert range assertion expressions into the implied copies.
2633 FIXME, this will eventually lead to copy propagation removing the
2634 names that had useful range information attached to them. For
2635 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
2636 then N_i will have the range [3, +INF].
2638 However, by converting the assertion into the implied copy
2639 operation N_i = N_j, we will then copy-propagate N_j into the uses
2640 of N_i and lose the range information. We may want to hold on to
2641 ASSERT_EXPRs a little while longer as the ranges could be used in
2642 things like jump threading.
2644 The problem with keeping ASSERT_EXPRs around is that passes after
2645 VRP need to handle them appropriately. */
2648 remove_range_assertions (void)
2651 block_stmt_iterator si
;
2654 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
2656 tree stmt
= bsi_stmt (si
);
2658 if (TREE_CODE (stmt
) == MODIFY_EXPR
2659 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ASSERT_EXPR
)
2661 tree rhs
= TREE_OPERAND (stmt
, 1);
2662 tree cond
= fold (ASSERT_EXPR_COND (rhs
));
2663 gcc_assert (cond
!= boolean_false_node
);
2664 TREE_OPERAND (stmt
, 1) = ASSERT_EXPR_VAR (rhs
);
2671 /* Return true if STMT is interesting for VRP. */
2674 stmt_interesting_for_vrp (tree stmt
)
2676 if (TREE_CODE (stmt
) == PHI_NODE
2677 && is_gimple_reg (PHI_RESULT (stmt
))
2678 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt
)))
2679 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt
)))))
2681 else if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2683 tree lhs
= TREE_OPERAND (stmt
, 0);
2685 if (TREE_CODE (lhs
) == SSA_NAME
2686 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2687 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2688 && ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
2691 else if (TREE_CODE (stmt
) == COND_EXPR
|| TREE_CODE (stmt
) == SWITCH_EXPR
)
2698 /* Initialize local data structures for VRP. Return true if VRP
2699 is worth running (i.e. if we found any statements that could
2700 benefit from range information). */
2703 vrp_initialize (void)
2707 vr_value
= xmalloc (num_ssa_names
* sizeof (value_range_t
*));
2708 memset (vr_value
, 0, num_ssa_names
* sizeof (value_range_t
*));
2712 block_stmt_iterator si
;
2715 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2717 if (!stmt_interesting_for_vrp (phi
))
2719 tree lhs
= PHI_RESULT (phi
);
2720 set_value_range_to_varying (get_value_range (lhs
));
2721 DONT_SIMULATE_AGAIN (phi
) = true;
2724 DONT_SIMULATE_AGAIN (phi
) = false;
2727 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
2729 tree stmt
= bsi_stmt (si
);
2731 if (!stmt_interesting_for_vrp (stmt
))
2735 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
2736 set_value_range_to_varying (get_value_range (def
));
2737 DONT_SIMULATE_AGAIN (stmt
) = true;
2741 DONT_SIMULATE_AGAIN (stmt
) = false;
2748 /* Visit assignment STMT. If it produces an interesting range, record
2749 the SSA name in *OUTPUT_P. */
2751 static enum ssa_prop_result
2752 vrp_visit_assignment (tree stmt
, tree
*output_p
)
2757 lhs
= TREE_OPERAND (stmt
, 0);
2758 rhs
= TREE_OPERAND (stmt
, 1);
2760 /* We only keep track of ranges in integral and pointer types. */
2761 if (TREE_CODE (lhs
) == SSA_NAME
2762 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2763 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
2766 value_range_t new_vr
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
2768 extract_range_from_expr (&new_vr
, rhs
);
2770 /* If STMT is inside a loop, we may be able to know something
2771 else about the range of LHS by examining scalar evolution
2773 if (cfg_loops
&& (l
= loop_containing_stmt (stmt
)))
2774 adjust_range_with_scev (&new_vr
, l
, stmt
, lhs
);
2776 if (update_value_range (lhs
, &new_vr
))
2780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2782 fprintf (dump_file
, "Found new range for ");
2783 print_generic_expr (dump_file
, lhs
, 0);
2784 fprintf (dump_file
, ": ");
2785 dump_value_range (dump_file
, &new_vr
);
2786 fprintf (dump_file
, "\n\n");
2789 if (new_vr
.type
== VR_VARYING
)
2790 return SSA_PROP_VARYING
;
2792 return SSA_PROP_INTERESTING
;
2795 return SSA_PROP_NOT_INTERESTING
;
2798 /* Every other statement produces no useful ranges. */
2799 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
2800 set_value_range_to_varying (get_value_range (def
));
2802 return SSA_PROP_VARYING
;
2806 /* Compare all the value ranges for names equivalent to VAR with VAL
2807 using comparison code COMP. Return the same value returned by
2808 compare_range_with_value. */
2811 compare_name_with_value (enum tree_code comp
, tree var
, tree val
)
2818 t
= retval
= NULL_TREE
;
2820 /* Get the set of equivalences for VAR. */
2821 e
= get_value_range (var
)->equiv
;
2823 /* Add VAR to its own set of equivalences so that VAR's value range
2824 is processed by this loop (otherwise, we would have to replicate
2825 the body of the loop just to check VAR's value range). */
2826 bitmap_set_bit (e
, SSA_NAME_VERSION (var
));
2828 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2830 value_range_t equiv_vr
= *(vr_value
[i
]);
2832 /* If name N_i does not have a valid range, use N_i as its own
2833 range. This allows us to compare against names that may
2834 have N_i in their ranges. */
2835 if (equiv_vr
.type
== VR_VARYING
|| equiv_vr
.type
== VR_UNDEFINED
)
2837 equiv_vr
.type
= VR_RANGE
;
2838 equiv_vr
.min
= ssa_name (i
);
2839 equiv_vr
.max
= ssa_name (i
);
2842 t
= compare_range_with_value (comp
, &equiv_vr
, val
);
2845 /* All the ranges should compare the same against VAL. */
2846 gcc_assert (retval
== NULL
|| t
== retval
);
2851 /* Remove VAR from its own equivalence set. */
2852 bitmap_clear_bit (e
, SSA_NAME_VERSION (var
));
2857 /* We couldn't find a non-NULL value for the predicate. */
2862 /* Given a comparison code COMP and names N1 and N2, compare all the
2863 ranges equivalent to N1 against all the ranges equivalent to N2
2864 to determine the value of N1 COMP N2. Return the same value
2865 returned by compare_ranges. */
2868 compare_names (enum tree_code comp
, tree n1
, tree n2
)
2872 bitmap_iterator bi1
, bi2
;
2875 /* Compare the ranges of every name equivalent to N1 against the
2876 ranges of every name equivalent to N2. */
2877 e1
= get_value_range (n1
)->equiv
;
2878 e2
= get_value_range (n2
)->equiv
;
2880 /* Add N1 and N2 to their own set of equivalences to avoid
2881 duplicating the body of the loop just to check N1 and N2
2883 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2884 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2886 /* If the equivalence sets have a common intersection, then the two
2887 names can be compared without checking their ranges. */
2888 if (bitmap_intersect_p (e1
, e2
))
2890 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2891 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2893 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2895 : boolean_false_node
;
2898 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2899 N2 to their own set of equivalences to avoid duplicating the body
2900 of the loop just to check N1 and N2 ranges. */
2901 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2903 value_range_t vr1
= *(vr_value
[i1
]);
2905 /* If the range is VARYING or UNDEFINED, use the name itself. */
2906 if (vr1
.type
== VR_VARYING
|| vr1
.type
== VR_UNDEFINED
)
2908 vr1
.type
= VR_RANGE
;
2909 vr1
.min
= ssa_name (i1
);
2910 vr1
.max
= ssa_name (i1
);
2913 t
= retval
= NULL_TREE
;
2914 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2916 value_range_t vr2
= *(vr_value
[i2
]);
2918 if (vr2
.type
== VR_VARYING
|| vr2
.type
== VR_UNDEFINED
)
2920 vr2
.type
= VR_RANGE
;
2921 vr2
.min
= ssa_name (i2
);
2922 vr2
.max
= ssa_name (i2
);
2925 t
= compare_ranges (comp
, &vr1
, &vr2
);
2928 /* All the ranges in the equivalent sets should compare
2930 gcc_assert (retval
== NULL
|| t
== retval
);
2937 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2938 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2943 /* None of the equivalent ranges are useful in computing this
2945 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2946 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2951 /* Given a conditional predicate COND, try to determine if COND yields
2952 true or false based on the value ranges of its operands. Return
2953 BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
2954 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
2955 NULL if the conditional cannot be evaluated at compile time.
2957 If USE_EQUIV_P is true, the ranges of all the names equivalent with
2958 the operands in COND are used when trying to compute its value.
2959 This is only used during final substitution. During propagation,
2960 we only check the range of each variable and not its equivalents. */
2963 vrp_evaluate_conditional (tree cond
, bool use_equiv_p
)
2965 gcc_assert (TREE_CODE (cond
) == SSA_NAME
2966 || TREE_CODE_CLASS (TREE_CODE (cond
)) == tcc_comparison
);
2968 if (TREE_CODE (cond
) == SSA_NAME
)
2974 retval
= compare_name_with_value (NE_EXPR
, cond
, boolean_false_node
);
2977 value_range_t
*vr
= get_value_range (cond
);
2978 retval
= compare_range_with_value (NE_EXPR
, vr
, boolean_false_node
);
2981 /* If COND has a known boolean range, return it. */
2985 /* Otherwise, if COND has a symbolic range of exactly one value,
2987 vr
= get_value_range (cond
);
2988 if (vr
->type
== VR_RANGE
&& vr
->min
== vr
->max
)
2993 tree op0
= TREE_OPERAND (cond
, 0);
2994 tree op1
= TREE_OPERAND (cond
, 1);
2996 /* We only deal with integral and pointer types. */
2997 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2998 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
3003 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
)
3004 return compare_names (TREE_CODE (cond
), op0
, op1
);
3005 else if (TREE_CODE (op0
) == SSA_NAME
)
3006 return compare_name_with_value (TREE_CODE (cond
), op0
, op1
);
3007 else if (TREE_CODE (op1
) == SSA_NAME
)
3008 return compare_name_with_value (
3009 opposite_comparison (TREE_CODE (cond
)), op1
, op0
);
3013 value_range_t
*vr0
, *vr1
;
3015 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
3016 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
3019 return compare_ranges (TREE_CODE (cond
), vr0
, vr1
);
3020 else if (vr0
&& vr1
== NULL
)
3021 return compare_range_with_value (TREE_CODE (cond
), vr0
, op1
);
3022 else if (vr0
== NULL
&& vr1
)
3023 return compare_range_with_value (
3024 opposite_comparison (TREE_CODE (cond
)), vr1
, op0
);
3028 /* Anything else cannot be computed statically. */
3033 /* Visit conditional statement STMT. If we can determine which edge
3034 will be taken out of STMT's basic block, record it in
3035 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
3036 SSA_PROP_VARYING. */
3038 static enum ssa_prop_result
3039 vrp_visit_cond_stmt (tree stmt
, edge
*taken_edge_p
)
3043 *taken_edge_p
= NULL
;
3045 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
3046 add ASSERT_EXPRs for them. */
3047 if (TREE_CODE (stmt
) == SWITCH_EXPR
)
3048 return SSA_PROP_VARYING
;
3050 cond
= COND_EXPR_COND (stmt
);
3052 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3057 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
3058 print_generic_expr (dump_file
, cond
, 0);
3059 fprintf (dump_file
, "\nWith known ranges\n");
3061 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
3063 fprintf (dump_file
, "\t");
3064 print_generic_expr (dump_file
, use
, 0);
3065 fprintf (dump_file
, ": ");
3066 dump_value_range (dump_file
, vr_value
[SSA_NAME_VERSION (use
)]);
3069 fprintf (dump_file
, "\n");
3072 /* Compute the value of the predicate COND by checking the known
3073 ranges of each of its operands.
3075 Note that we cannot evaluate all the equivalent ranges here
3076 because those ranges may not yet be final and with the current
3077 propagation strategy, we cannot determine when the value ranges
3078 of the names in the equivalence set have changed.
3080 For instance, given the following code fragment
3084 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3088 Assume that on the first visit to i_14, i_5 has the temporary
3089 range [8, 8] because the second argument to the PHI function is
3090 not yet executable. We derive the range ~[0, 0] for i_14 and the
3091 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
3092 the first time, since i_14 is equivalent to the range [8, 8], we
3093 determine that the predicate is always false.
3095 On the next round of propagation, i_13 is determined to be
3096 VARYING, which causes i_5 to drop down to VARYING. So, another
3097 visit to i_14 is scheduled. In this second visit, we compute the
3098 exact same range and equivalence set for i_14, namely ~[0, 0] and
3099 { i_5 }. But we did not have the previous range for i_5
3100 registered, so vrp_visit_assignment thinks that the range for
3101 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
3102 is not visited again, which stops propagation from visiting
3103 statements in the THEN clause of that if().
3105 To properly fix this we would need to keep the previous range
3106 value for the names in the equivalence set. This way we would've
3107 discovered that from one visit to the other i_5 changed from
3108 range [8, 8] to VR_VARYING.
3110 However, fixing this apparent limitation may not be worth the
3111 additional checking. Testing on several code bases (GCC, DLV,
3112 MICO, TRAMP3D and SPEC2000) showed that doing this results in
3113 4 more predicates folded in SPEC. */
3114 val
= vrp_evaluate_conditional (cond
, false);
3116 *taken_edge_p
= find_taken_edge (bb_for_stmt (stmt
), val
);
3118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3120 fprintf (dump_file
, "\nPredicate evaluates to: ");
3121 if (val
== NULL_TREE
)
3122 fprintf (dump_file
, "DON'T KNOW\n");
3124 print_generic_stmt (dump_file
, val
, 0);
3127 return (*taken_edge_p
) ? SSA_PROP_INTERESTING
: SSA_PROP_VARYING
;
3131 /* Evaluate statement STMT. If the statement produces a useful range,
3132 return SSA_PROP_INTERESTING and record the SSA name with the
3133 interesting range into *OUTPUT_P.
3135 If STMT is a conditional branch and we can determine its truth
3136 value, the taken edge is recorded in *TAKEN_EDGE_P.
3138 If STMT produces a varying value, return SSA_PROP_VARYING. */
3140 static enum ssa_prop_result
3141 vrp_visit_stmt (tree stmt
, edge
*taken_edge_p
, tree
*output_p
)
3147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3149 fprintf (dump_file
, "\nVisiting statement:\n");
3150 print_generic_stmt (dump_file
, stmt
, dump_flags
);
3151 fprintf (dump_file
, "\n");
3154 ann
= stmt_ann (stmt
);
3155 if (TREE_CODE (stmt
) == MODIFY_EXPR
3156 && ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
3157 return vrp_visit_assignment (stmt
, output_p
);
3158 else if (TREE_CODE (stmt
) == COND_EXPR
|| TREE_CODE (stmt
) == SWITCH_EXPR
)
3159 return vrp_visit_cond_stmt (stmt
, taken_edge_p
);
3161 /* All other statements produce nothing of interest for VRP, so mark
3162 their outputs varying and prevent further simulation. */
3163 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
3164 set_value_range_to_varying (get_value_range (def
));
3166 return SSA_PROP_VARYING
;
3170 /* Meet operation for value ranges. Given two value ranges VR0 and
3171 VR1, store in VR0 the result of meeting VR0 and VR1.
3173 The meeting rules are as follows:
3175 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3177 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3178 union of VR0 and VR1. */
3181 vrp_meet (value_range_t
*vr0
, value_range_t
*vr1
)
3183 if (vr0
->type
== VR_UNDEFINED
)
3185 copy_value_range (vr0
, vr1
);
3189 if (vr1
->type
== VR_UNDEFINED
)
3191 /* Nothing to do. VR0 already has the resulting range. */
3195 if (vr0
->type
== VR_VARYING
)
3197 /* Nothing to do. VR0 already has the resulting range. */
3201 if (vr1
->type
== VR_VARYING
)
3203 set_value_range_to_varying (vr0
);
3207 if (vr0
->type
== VR_RANGE
&& vr1
->type
== VR_RANGE
)
3209 /* If VR0 and VR1 have a non-empty intersection, compute the
3210 union of both ranges. */
3211 if (value_ranges_intersect_p (vr0
, vr1
))
3216 /* The lower limit of the new range is the minimum of the
3217 two ranges. If they cannot be compared, the result is
3219 cmp
= compare_values (vr0
->min
, vr1
->min
);
3220 if (cmp
== 0 || cmp
== 1)
3226 set_value_range_to_varying (vr0
);
3230 /* Similarly, the upper limit of the new range is the
3231 maximum of the two ranges. If they cannot be compared,
3232 the result is VARYING. */
3233 cmp
= compare_values (vr0
->max
, vr1
->max
);
3234 if (cmp
== 0 || cmp
== -1)
3240 set_value_range_to_varying (vr0
);
3244 /* The resulting set of equivalences is the intersection of
3246 if (vr0
->equiv
&& vr1
->equiv
&& vr0
->equiv
!= vr1
->equiv
)
3247 bitmap_and_into (vr0
->equiv
, vr1
->equiv
);
3249 set_value_range (vr0
, vr0
->type
, min
, max
, vr0
->equiv
);
3254 else if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
3256 /* Two anti-ranges meet only if they are both identical. */
3257 if (compare_values (vr0
->min
, vr1
->min
) == 0
3258 && compare_values (vr0
->max
, vr1
->max
) == 0
3259 && compare_values (vr0
->min
, vr0
->max
) == 0)
3261 /* The resulting set of equivalences is the intersection of
3263 if (vr0
->equiv
&& vr1
->equiv
&& vr0
->equiv
!= vr1
->equiv
)
3264 bitmap_and_into (vr0
->equiv
, vr1
->equiv
);
3269 else if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
3271 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
3272 meet only if the ranges have an empty intersection. The
3273 result of the meet operation is the anti-range. */
3274 if (!symbolic_range_p (vr0
)
3275 && !symbolic_range_p (vr1
)
3276 && !value_ranges_intersect_p (vr0
, vr1
))
3278 if (vr1
->type
== VR_ANTI_RANGE
)
3279 copy_value_range (vr0
, vr1
);
3290 /* The two range VR0 and VR1 do not meet. Before giving up and
3291 setting the result to VARYING, see if we can at least derive a
3292 useful anti-range. */
3293 if (!symbolic_range_p (vr0
)
3294 && !range_includes_zero_p (vr0
)
3295 && !symbolic_range_p (vr1
)
3296 && !range_includes_zero_p (vr1
))
3297 set_value_range_to_nonnull (vr0
, TREE_TYPE (vr0
->min
));
3299 set_value_range_to_varying (vr0
);
3303 /* Visit all arguments for PHI node PHI that flow through executable
3304 edges. If a valid value range can be derived from all the incoming
3305 value ranges, set a new range for the LHS of PHI. */
3307 static enum ssa_prop_result
3308 vrp_visit_phi_node (tree phi
)
3311 tree lhs
= PHI_RESULT (phi
);
3312 value_range_t
*lhs_vr
= get_value_range (lhs
);
3313 value_range_t vr_result
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
3315 copy_value_range (&vr_result
, lhs_vr
);
3317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3319 fprintf (dump_file
, "\nVisiting PHI node: ");
3320 print_generic_expr (dump_file
, phi
, dump_flags
);
3323 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
3325 edge e
= PHI_ARG_EDGE (phi
, i
);
3327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3330 "\n Argument #%d (%d -> %d %sexecutable)\n",
3331 i
, e
->src
->index
, e
->dest
->index
,
3332 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
3335 if (e
->flags
& EDGE_EXECUTABLE
)
3337 tree arg
= PHI_ARG_DEF (phi
, i
);
3338 value_range_t vr_arg
;
3340 if (TREE_CODE (arg
) == SSA_NAME
)
3341 vr_arg
= *(get_value_range (arg
));
3344 vr_arg
.type
= VR_RANGE
;
3347 vr_arg
.equiv
= NULL
;
3350 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3352 fprintf (dump_file
, "\t");
3353 print_generic_expr (dump_file
, arg
, dump_flags
);
3354 fprintf (dump_file
, "\n\tValue: ");
3355 dump_value_range (dump_file
, &vr_arg
);
3356 fprintf (dump_file
, "\n");
3359 vrp_meet (&vr_result
, &vr_arg
);
3361 if (vr_result
.type
== VR_VARYING
)
3366 if (vr_result
.type
== VR_VARYING
)
3369 /* To prevent infinite iterations in the algorithm, derive ranges
3370 when the new value is slightly bigger or smaller than the
3372 if (lhs_vr
->type
== VR_RANGE
)
3374 if (!POINTER_TYPE_P (TREE_TYPE (lhs
)))
3376 int cmp_min
= compare_values (lhs_vr
->min
, vr_result
.min
);
3377 int cmp_max
= compare_values (lhs_vr
->max
, vr_result
.max
);
3379 /* If the new minimum is smaller or larger than the previous
3380 one, go all the way to -INF. In the first case, to avoid
3381 iterating millions of times to reach -INF, and in the
3382 other case to avoid infinite bouncing between different
3384 if (cmp_min
> 0 || cmp_min
< 0)
3385 vr_result
.min
= TYPE_MIN_VALUE (TREE_TYPE (vr_result
.min
));
3387 /* Similarly, if the new maximum is smaller or larger than
3388 the previous one, go all the way to +INF. */
3389 if (cmp_max
< 0 || cmp_max
> 0)
3390 vr_result
.max
= TYPE_MAX_VALUE (TREE_TYPE (vr_result
.max
));
3392 /* If we ended up with a (-INF, +INF) range, set it to
3394 if (vr_result
.min
== TYPE_MIN_VALUE (TREE_TYPE (vr_result
.min
))
3395 && vr_result
.max
== TYPE_MAX_VALUE (TREE_TYPE (vr_result
.max
)))
3400 /* If the new range is different than the previous value, keep
3402 if (update_value_range (lhs
, &vr_result
))
3403 return SSA_PROP_INTERESTING
;
3405 /* Nothing changed, don't add outgoing edges. */
3406 return SSA_PROP_NOT_INTERESTING
;
3408 /* No match found. Set the LHS to VARYING. */
3410 set_value_range_to_varying (lhs_vr
);
3411 return SSA_PROP_VARYING
;
3414 /* Walk through the IL simplifying expressions using knowledge
3418 simplify_using_ranges (void)
3424 block_stmt_iterator bsi
;
3426 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3428 tree stmt
= bsi_stmt (bsi
);
3430 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
3432 tree rhs
= TREE_OPERAND (stmt
, 1);
3433 enum tree_code rhs_code
= TREE_CODE (rhs
);
3435 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
3436 and BIT_AND_EXPR respectively if the first operand is greater
3437 than zero and the second operand is an exact power of two. */
3438 if ((rhs_code
== TRUNC_DIV_EXPR
|| rhs_code
== TRUNC_MOD_EXPR
)
3439 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
3440 && integer_pow2p (TREE_OPERAND (rhs
, 1)))
3443 tree op
= TREE_OPERAND (rhs
, 0);
3444 value_range_t
*vr
= get_value_range (TREE_OPERAND (rhs
, 0));
3446 if (TYPE_UNSIGNED (TREE_TYPE (op
)))
3448 val
= integer_one_node
;
3452 val
= compare_range_with_value (GT_EXPR
, vr
,
3456 if (val
&& integer_onep (val
))
3459 tree op0
= TREE_OPERAND (rhs
, 0);
3460 tree op1
= TREE_OPERAND (rhs
, 1);
3462 if (rhs_code
== TRUNC_DIV_EXPR
)
3464 t
= build_int_cst (NULL_TREE
, tree_log2 (op1
));
3465 t
= build (RSHIFT_EXPR
, TREE_TYPE (op0
), op0
, t
);
3469 t
= build_int_cst (TREE_TYPE (op1
), 1);
3470 t
= int_const_binop (MINUS_EXPR
, op1
, t
, 0);
3471 t
= fold_convert (TREE_TYPE (op0
), t
);
3472 t
= build2 (BIT_AND_EXPR
, TREE_TYPE (op0
), op0
, t
);
3475 TREE_OPERAND (stmt
, 1) = t
;
3481 /* Transform ABS (X) into X or -X as appropriate. */
3482 if (rhs_code
== ABS_EXPR
3483 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
3484 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
3487 tree op
= TREE_OPERAND (rhs
, 0);
3488 tree type
= TREE_TYPE (op
);
3489 value_range_t
*vr
= get_value_range (TREE_OPERAND (rhs
, 0));
3491 if (TYPE_UNSIGNED (type
))
3493 val
= integer_zero_node
;
3497 val
= compare_range_with_value (LE_EXPR
, vr
,
3501 val
= compare_range_with_value (GE_EXPR
, vr
,
3506 if (integer_zerop (val
))
3507 val
= integer_one_node
;
3508 else if (integer_onep (val
))
3509 val
= integer_zero_node
;
3514 && (integer_onep (val
) || integer_zerop (val
)))
3518 if (integer_onep (val
))
3519 t
= build1 (NEGATE_EXPR
, TREE_TYPE (op
), op
);
3523 TREE_OPERAND (stmt
, 1) = t
;
3530 /* TODO. Simplify conditionals. */
3536 /* Traverse all the blocks folding conditionals with known ranges. */
3542 prop_value_t
*single_val_range
;
3543 bool do_value_subst_p
;
3547 fprintf (dump_file
, "\nValue ranges after VRP:\n\n");
3548 dump_all_value_ranges (dump_file
);
3549 fprintf (dump_file
, "\n");
3552 /* We may have ended with ranges that have exactly one value. Those
3553 values can be substituted as any other copy/const propagated
3554 value using substitute_and_fold. */
3555 single_val_range
= xmalloc (num_ssa_names
* sizeof (*single_val_range
));
3556 memset (single_val_range
, 0, num_ssa_names
* sizeof (*single_val_range
));
3558 do_value_subst_p
= false;
3559 for (i
= 0; i
< num_ssa_names
; i
++)
3561 && vr_value
[i
]->type
== VR_RANGE
3562 && vr_value
[i
]->min
== vr_value
[i
]->max
)
3564 single_val_range
[i
].value
= vr_value
[i
]->min
;
3565 do_value_subst_p
= true;
3568 if (!do_value_subst_p
)
3570 /* We found no single-valued ranges, don't waste time trying to
3571 do single value substitution in substitute_and_fold. */
3572 free (single_val_range
);
3573 single_val_range
= NULL
;
3576 substitute_and_fold (single_val_range
, true);
3578 /* One could argue all simplifications should be done here
3579 rather than using substitute_and_fold since this code
3580 is going to have to perform a complete walk through the
3582 simplify_using_ranges ();
3584 /* Free allocated memory. */
3585 for (i
= 0; i
< num_ssa_names
; i
++)
3588 BITMAP_FREE (vr_value
[i
]->equiv
);
3592 free (single_val_range
);
3597 /* Main entry point to VRP (Value Range Propagation). This pass is
3598 loosely based on J. R. C. Patterson, ``Accurate Static Branch
3599 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
3600 Programming Language Design and Implementation, pp. 67-78, 1995.
3601 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
3603 This is essentially an SSA-CCP pass modified to deal with ranges
3604 instead of constants.
3606 While propagating ranges, we may find that two or more SSA name
3607 have equivalent, though distinct ranges. For instance,
3610 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
3612 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
3616 In the code above, pointer p_5 has range [q_2, q_2], but from the
3617 code we can also determine that p_5 cannot be NULL and, if q_2 had
3618 a non-varying range, p_5's range should also be compatible with it.
3620 These equivalences are created by two expressions: ASSERT_EXPR and
3621 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
3622 result of another assertion, then we can use the fact that p_5 and
3623 p_4 are equivalent when evaluating p_5's range.
3625 Together with value ranges, we also propagate these equivalences
3626 between names so that we can take advantage of information from
3627 multiple ranges when doing final replacement. Note that this
3628 equivalency relation is transitive but not symmetric.
3630 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
3631 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
3632 in contexts where that assertion does not hold (e.g., in line 6).
3634 TODO, the main difference between this pass and Patterson's is that
3635 we do not propagate edge probabilities. We only compute whether
3636 edges can be taken or not. That is, instead of having a spectrum
3637 of jump probabilities between 0 and 1, we only deal with 0, 1 and
3638 DON'T KNOW. In the future, it may be worthwhile to propagate
3639 probabilities to aid branch prediction. */
3644 insert_range_assertions ();
3646 cfg_loops
= loop_optimizer_init (NULL
);
3648 scev_initialize (cfg_loops
);
3651 ssa_propagate (vrp_visit_stmt
, vrp_visit_phi_node
);
3657 loop_optimizer_finalize (cfg_loops
, NULL
);
3658 current_loops
= NULL
;
3661 remove_range_assertions ();
3667 return flag_tree_vrp
!= 0;
3670 struct tree_opt_pass pass_vrp
=
3673 gate_vrp
, /* gate */
3674 execute_vrp
, /* execute */
3677 0, /* static_pass_number */
3678 TV_TREE_VRP
, /* tv_id */
3679 PROP_ssa
| PROP_alias
, /* properties_required */
3680 0, /* properties_provided */
3681 0, /* properties_destroyed */
3682 0, /* todo_flags_start */
3687 | TODO_update_ssa
, /* todo_flags_finish */