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 /* Determine whether VAL1 CODE VAL2 yields a growing value.
1000 Notice that we only need to handle the restricted set of
1001 operations handled by extract_range_from_binary_expr:
1003 VAL1 + VAL2 grows if VAL2 is >= 0.
1004 VAL1 * VAL2 grows if both VAL1 and VAL2 have the same sign.
1005 VAL1 - VAL2 grows if VAL2 is < 0 (because it becomes an addition).
1007 if ((code
== PLUS_EXPR
&& sgn2
>= 0)
1008 || (code
== MULT_EXPR
&& sgn1
== sgn2
)
1009 || (code
== MINUS_EXPR
&& sgn2
< 0))
1013 return TYPE_MAX_VALUE (TREE_TYPE (res
));
1015 return TYPE_MIN_VALUE (TREE_TYPE (res
));
1022 /* Extract range information from a binary expression EXPR based on
1023 the ranges of each of its operands and the expression code. */
1026 extract_range_from_binary_expr (value_range_t
*vr
, tree expr
)
1028 enum tree_code code
= TREE_CODE (expr
);
1029 tree op0
, op1
, min
, max
;
1031 value_range_t vr0
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
1032 value_range_t vr1
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
1034 /* Not all binary expressions can be applied to ranges in a
1035 meaningful way. Handle only arithmetic operations. */
1036 if (code
!= PLUS_EXPR
1037 && code
!= MINUS_EXPR
1038 && code
!= MULT_EXPR
1039 && code
!= TRUNC_DIV_EXPR
1040 && code
!= FLOOR_DIV_EXPR
1041 && code
!= CEIL_DIV_EXPR
1042 && code
!= EXACT_DIV_EXPR
1043 && code
!= ROUND_DIV_EXPR
1046 && code
!= TRUTH_ANDIF_EXPR
1047 && code
!= TRUTH_ORIF_EXPR
1048 && code
!= TRUTH_AND_EXPR
1049 && code
!= TRUTH_OR_EXPR
1050 && code
!= TRUTH_XOR_EXPR
)
1052 set_value_range_to_varying (vr
);
1056 /* Get value ranges for each operand. For constant operands, create
1057 a new value range with the operand to simplify processing. */
1058 op0
= TREE_OPERAND (expr
, 0);
1059 if (TREE_CODE (op0
) == SSA_NAME
)
1060 vr0
= *(get_value_range (op0
));
1061 else if (is_gimple_min_invariant (op0
))
1062 set_value_range (&vr0
, VR_RANGE
, op0
, op0
, NULL
);
1064 set_value_range_to_varying (&vr0
);
1066 op1
= TREE_OPERAND (expr
, 1);
1067 if (TREE_CODE (op1
) == SSA_NAME
)
1068 vr1
= *(get_value_range (op1
));
1069 else if (is_gimple_min_invariant (op1
))
1070 set_value_range (&vr1
, VR_RANGE
, op1
, op1
, NULL
);
1072 set_value_range_to_varying (&vr1
);
1074 /* If either range is UNDEFINED, so is the result. */
1075 if (vr0
.type
== VR_UNDEFINED
|| vr1
.type
== VR_UNDEFINED
)
1077 set_value_range_to_undefined (vr
);
1081 /* Refuse to operate on VARYING ranges, ranges of different kinds
1082 and symbolic ranges. TODO, we may be able to derive anti-ranges
1084 if (vr0
.type
== VR_VARYING
1085 || vr1
.type
== VR_VARYING
1086 || vr0
.type
!= vr1
.type
1087 || symbolic_range_p (&vr0
)
1088 || symbolic_range_p (&vr1
))
1090 set_value_range_to_varying (vr
);
1094 /* Now evaluate the expression to determine the new range. */
1095 if (POINTER_TYPE_P (TREE_TYPE (expr
))
1096 || POINTER_TYPE_P (TREE_TYPE (op0
))
1097 || POINTER_TYPE_P (TREE_TYPE (op1
)))
1099 /* For pointer types, we are really only interested in asserting
1100 whether the expression evaluates to non-NULL. FIXME, we used
1101 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1102 ivopts is generating expressions with pointer multiplication
1104 if (code
== PLUS_EXPR
)
1105 set_value_range_to_nonnull (vr
, TREE_TYPE (expr
));
1108 /* Subtracting from a pointer, may yield 0, so just drop the
1109 resulting range to varying. */
1110 set_value_range_to_varying (vr
);
1116 /* For integer ranges, apply the operation to each end of the
1117 range and see what we end up with. */
1118 if (code
== TRUTH_ANDIF_EXPR
1119 || code
== TRUTH_ORIF_EXPR
1120 || code
== TRUTH_AND_EXPR
1121 || code
== TRUTH_OR_EXPR
1122 || code
== TRUTH_XOR_EXPR
)
1124 /* Boolean expressions cannot be folded with int_const_binop. */
1125 min
= fold_binary (code
, TREE_TYPE (expr
), vr0
.min
, vr1
.min
);
1126 max
= fold_binary (code
, TREE_TYPE (expr
), vr0
.max
, vr1
.max
);
1128 else if (code
== PLUS_EXPR
1130 || code
== MAX_EXPR
)
1132 /* For operations that make the resulting range directly
1133 proportional to the original ranges, apply the operation to
1134 the same end of each range. */
1135 min
= vrp_int_const_binop (code
, vr0
.min
, vr1
.min
);
1136 max
= vrp_int_const_binop (code
, vr0
.max
, vr1
.max
);
1138 else if (code
== MULT_EXPR
1139 || code
== TRUNC_DIV_EXPR
1140 || code
== FLOOR_DIV_EXPR
1141 || code
== CEIL_DIV_EXPR
1142 || code
== EXACT_DIV_EXPR
1143 || code
== ROUND_DIV_EXPR
)
1148 /* Multiplications and divisions are a bit tricky to handle,
1149 depending on the mix of signs we have in the two ranges, we
1150 need to operate on different values to get the minimum and
1151 maximum values for the new range. One approach is to figure
1152 out all the variations of range combinations and do the
1155 However, this involves several calls to compare_values and it
1156 is pretty convoluted. It's simpler to do the 4 operations
1157 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
1158 MAX1) and then figure the smallest and largest values to form
1161 /* Divisions by zero result in a VARYING value. */
1162 if (code
!= MULT_EXPR
&& range_includes_zero_p (&vr1
))
1164 set_value_range_to_varying (vr
);
1168 /* Compute the 4 cross operations. */
1169 val
[0] = vrp_int_const_binop (code
, vr0
.min
, vr1
.min
);
1171 val
[1] = (vr1
.max
!= vr1
.min
)
1172 ? vrp_int_const_binop (code
, vr0
.min
, vr1
.max
)
1175 val
[2] = (vr0
.max
!= vr0
.min
)
1176 ? vrp_int_const_binop (code
, vr0
.max
, vr1
.min
)
1179 val
[3] = (vr0
.min
!= vr1
.min
&& vr0
.max
!= vr1
.max
)
1180 ? vrp_int_const_binop (code
, vr0
.max
, vr1
.max
)
1183 /* Set MIN to the minimum of VAL[i] and MAX to the maximum
1187 for (i
= 1; i
< 4; i
++)
1189 if (TREE_OVERFLOW (min
) || TREE_OVERFLOW (max
))
1194 if (TREE_OVERFLOW (val
[i
]))
1196 /* If we found an overflowed value, set MIN and MAX
1197 to it so that we set the resulting range to
1203 if (compare_values (val
[i
], min
) == -1)
1206 if (compare_values (val
[i
], max
) == 1)
1211 else if (code
== MINUS_EXPR
)
1213 /* For MINUS_EXPR, apply the operation to the opposite ends of
1215 min
= vrp_int_const_binop (code
, vr0
.min
, vr1
.max
);
1216 max
= vrp_int_const_binop (code
, vr0
.max
, vr1
.min
);
1221 /* If either MIN or MAX overflowed, then set the resulting range to
1223 if (TREE_OVERFLOW (min
) || TREE_OVERFLOW (max
))
1225 set_value_range_to_varying (vr
);
1229 cmp
= compare_values (min
, max
);
1230 if (cmp
== -2 || cmp
== 1)
1232 /* If the new range has its limits swapped around (MIN > MAX),
1233 then the operation caused one of them to wrap around, mark
1234 the new range VARYING. */
1235 set_value_range_to_varying (vr
);
1238 set_value_range (vr
, vr0
.type
, min
, max
, NULL
);
1242 /* Extract range information from a unary expression EXPR based on
1243 the range of its operand and the expression code. */
1246 extract_range_from_unary_expr (value_range_t
*vr
, tree expr
)
1248 enum tree_code code
= TREE_CODE (expr
);
1251 value_range_t vr0
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
1253 /* Refuse to operate on certain unary expressions for which we
1254 cannot easily determine a resulting range. */
1255 if (code
== FIX_TRUNC_EXPR
1256 || code
== FIX_CEIL_EXPR
1257 || code
== FIX_FLOOR_EXPR
1258 || code
== FIX_ROUND_EXPR
1259 || code
== FLOAT_EXPR
1260 || code
== BIT_NOT_EXPR
1261 || code
== NON_LVALUE_EXPR
1262 || code
== CONJ_EXPR
)
1264 set_value_range_to_varying (vr
);
1268 /* Get value ranges for the operand. For constant operands, create
1269 a new value range with the operand to simplify processing. */
1270 op0
= TREE_OPERAND (expr
, 0);
1271 if (TREE_CODE (op0
) == SSA_NAME
)
1272 vr0
= *(get_value_range (op0
));
1273 else if (is_gimple_min_invariant (op0
))
1274 set_value_range (&vr0
, VR_RANGE
, op0
, op0
, NULL
);
1276 set_value_range_to_varying (&vr0
);
1278 /* If VR0 is UNDEFINED, so is the result. */
1279 if (vr0
.type
== VR_UNDEFINED
)
1281 set_value_range_to_undefined (vr
);
1285 /* Refuse to operate on varying and symbolic ranges. Also, if the
1286 operand is neither a pointer nor an integral type, set the
1287 resulting range to VARYING. TODO, in some cases we may be able
1288 to derive anti-ranges (like non-zero values). */
1289 if (vr0
.type
== VR_VARYING
1290 || (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
1291 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
1292 || symbolic_range_p (&vr0
))
1294 set_value_range_to_varying (vr
);
1298 /* If the expression involves pointers, we are only interested in
1299 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
1300 if (POINTER_TYPE_P (TREE_TYPE (expr
)) || POINTER_TYPE_P (TREE_TYPE (op0
)))
1302 if (range_is_nonnull (&vr0
) || expr_computes_nonzero (expr
))
1303 set_value_range_to_nonnull (vr
, TREE_TYPE (expr
));
1304 else if (range_is_null (&vr0
))
1305 set_value_range_to_null (vr
, TREE_TYPE (expr
));
1307 set_value_range_to_varying (vr
);
1312 /* Handle unary expressions on integer ranges. */
1313 if (code
== NOP_EXPR
|| code
== CONVERT_EXPR
)
1315 tree inner_type
= TREE_TYPE (op0
);
1316 tree outer_type
= TREE_TYPE (expr
);
1318 /* When converting types of different sizes, set the result to
1319 VARYING. Things like sign extensions and precision loss may
1320 change the range. For instance, if x_3 is of type 'long long
1321 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1322 is impossible to know at compile time whether y_5 will be
1324 if (TYPE_SIZE (inner_type
) != TYPE_SIZE (outer_type
)
1325 || TYPE_PRECISION (inner_type
) != TYPE_PRECISION (outer_type
))
1327 set_value_range_to_varying (vr
);
1332 /* Apply the operation to each end of the range and see what we end
1334 if (code
== NEGATE_EXPR
1335 && !TYPE_UNSIGNED (TREE_TYPE (expr
)))
1337 /* Negating an anti-range doesn't really do anything to it. The
1338 new range will also not take on the same range of values
1339 excluded by the original anti-range. */
1340 if (vr0
.type
== VR_ANTI_RANGE
)
1342 copy_value_range (vr
, &vr0
);
1346 /* NEGATE_EXPR flips the range around. */
1347 min
= (vr0
.max
== TYPE_MAX_VALUE (TREE_TYPE (expr
)))
1348 ? TYPE_MIN_VALUE (TREE_TYPE (expr
))
1349 : fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.max
);
1351 max
= (vr0
.min
== TYPE_MIN_VALUE (TREE_TYPE (expr
)))
1352 ? TYPE_MAX_VALUE (TREE_TYPE (expr
))
1353 : fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.min
);
1355 else if (code
== ABS_EXPR
1356 && !TYPE_UNSIGNED (TREE_TYPE (expr
)))
1358 /* ABS_EXPR may flip the range around, if the original range
1359 included negative values. */
1360 min
= (vr0
.min
== TYPE_MIN_VALUE (TREE_TYPE (expr
)))
1361 ? TYPE_MAX_VALUE (TREE_TYPE (expr
))
1362 : fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.min
);
1364 max
= fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.max
);
1366 /* If the range was reversed, swap MIN and MAX. */
1367 if (compare_values (min
, max
) == 1)
1376 /* Otherwise, operate on each end of the range. */
1377 min
= fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.min
);
1378 max
= fold_unary_to_constant (code
, TREE_TYPE (expr
), vr0
.max
);
1381 cmp
= compare_values (min
, max
);
1382 if (cmp
== -2 || cmp
== 1)
1384 /* If the new range has its limits swapped around (MIN > MAX),
1385 then the operation caused one of them to wrap around, mark
1386 the new range VARYING. */
1387 set_value_range_to_varying (vr
);
1390 set_value_range (vr
, vr0
.type
, min
, max
, NULL
);
1394 /* Extract range information from a comparison expression EXPR based
1395 on the range of its operand and the expression code. */
1398 extract_range_from_comparison (value_range_t
*vr
, tree expr
)
1400 tree val
= vrp_evaluate_conditional (expr
, false);
1403 /* Since this expression was found on the RHS of an assignment,
1404 its type may be different from _Bool. Convert VAL to EXPR's
1406 val
= fold_convert (TREE_TYPE (expr
), val
);
1407 set_value_range (vr
, VR_RANGE
, val
, val
, vr
->equiv
);
1410 set_value_range_to_varying (vr
);
1414 /* Try to compute a useful range out of expression EXPR and store it
1418 extract_range_from_expr (value_range_t
*vr
, tree expr
)
1420 enum tree_code code
= TREE_CODE (expr
);
1422 if (code
== ASSERT_EXPR
)
1423 extract_range_from_assert (vr
, expr
);
1424 else if (code
== SSA_NAME
)
1425 extract_range_from_ssa_name (vr
, expr
);
1426 else if (TREE_CODE_CLASS (code
) == tcc_binary
1427 || code
== TRUTH_ANDIF_EXPR
1428 || code
== TRUTH_ORIF_EXPR
1429 || code
== TRUTH_AND_EXPR
1430 || code
== TRUTH_OR_EXPR
1431 || code
== TRUTH_XOR_EXPR
)
1432 extract_range_from_binary_expr (vr
, expr
);
1433 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1434 extract_range_from_unary_expr (vr
, expr
);
1435 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1436 extract_range_from_comparison (vr
, expr
);
1437 else if (vrp_expr_computes_nonzero (expr
))
1438 set_value_range_to_nonnull (vr
, TREE_TYPE (expr
));
1439 else if (is_gimple_min_invariant (expr
))
1440 set_value_range (vr
, VR_RANGE
, expr
, expr
, NULL
);
1442 set_value_range_to_varying (vr
);
1445 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1446 would be profitable to adjust VR using scalar evolution information
1447 for VAR. If so, update VR with the new limits. */
1450 adjust_range_with_scev (value_range_t
*vr
, struct loop
*loop
, tree stmt
,
1453 tree init
, step
, chrec
;
1456 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1457 better opportunities than a regular range, but I'm not sure. */
1458 if (vr
->type
== VR_ANTI_RANGE
)
1461 chrec
= analyze_scalar_evolution (loop
, var
);
1462 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1465 init
= CHREC_LEFT (chrec
);
1466 step
= CHREC_RIGHT (chrec
);
1468 /* If STEP is symbolic, we can't know whether INIT will be the
1469 minimum or maximum value in the range. */
1470 if (!is_gimple_min_invariant (step
))
1473 /* Do not adjust ranges when chrec may wrap. */
1474 if (scev_probably_wraps_p (chrec_type (chrec
), init
, step
, stmt
,
1475 cfg_loops
->parray
[CHREC_VARIABLE (chrec
)],
1479 if (!POINTER_TYPE_P (TREE_TYPE (init
))
1480 && (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
))
1482 /* For VARYING or UNDEFINED ranges, just about anything we get
1483 from scalar evolutions should be better. */
1485 set_value_range (vr
, VR_RANGE
, TYPE_MIN_VALUE (TREE_TYPE (init
)),
1488 set_value_range (vr
, VR_RANGE
, init
, TYPE_MAX_VALUE (TREE_TYPE (init
)),
1491 else if (vr
->type
== VR_RANGE
)
1498 /* INIT is the maximum value. If INIT is lower than VR->MAX
1499 but no smaller than VR->MIN, set VR->MAX to INIT. */
1500 if (compare_values (init
, max
) == -1)
1504 /* If we just created an invalid range with the minimum
1505 greater than the maximum, take the minimum all the
1507 if (compare_values (min
, max
) == 1)
1508 min
= TYPE_MIN_VALUE (TREE_TYPE (min
));
1513 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1514 if (compare_values (init
, min
) == 1)
1518 /* If we just created an invalid range with the minimum
1519 greater than the maximum, take the maximum all the
1521 if (compare_values (min
, max
) == 1)
1522 max
= TYPE_MAX_VALUE (TREE_TYPE (max
));
1526 set_value_range (vr
, VR_RANGE
, min
, max
, vr
->equiv
);
1531 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1533 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1534 all the values in the ranges.
1536 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1538 - Return NULL_TREE if it is not always possible to determine the
1539 value of the comparison. */
1543 compare_ranges (enum tree_code comp
, value_range_t
*vr0
, value_range_t
*vr1
)
1545 /* VARYING or UNDEFINED ranges cannot be compared. */
1546 if (vr0
->type
== VR_VARYING
1547 || vr0
->type
== VR_UNDEFINED
1548 || vr1
->type
== VR_VARYING
1549 || vr1
->type
== VR_UNDEFINED
)
1552 /* Anti-ranges need to be handled separately. */
1553 if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
1555 /* If both are anti-ranges, then we cannot compute any
1557 if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
1560 /* These comparisons are never statically computable. */
1567 /* Equality can be computed only between a range and an
1568 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1569 if (vr0
->type
== VR_RANGE
)
1571 /* To simplify processing, make VR0 the anti-range. */
1572 value_range_t
*tmp
= vr0
;
1577 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1579 if (compare_values (vr0
->min
, vr1
->min
) == 0
1580 && compare_values (vr0
->max
, vr1
->max
) == 0)
1581 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1586 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1587 operands around and change the comparison code. */
1588 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1591 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1597 if (comp
== EQ_EXPR
)
1599 /* Equality may only be computed if both ranges represent
1600 exactly one value. */
1601 if (compare_values (vr0
->min
, vr0
->max
) == 0
1602 && compare_values (vr1
->min
, vr1
->max
) == 0)
1604 int cmp_min
= compare_values (vr0
->min
, vr1
->min
);
1605 int cmp_max
= compare_values (vr0
->max
, vr1
->max
);
1606 if (cmp_min
== 0 && cmp_max
== 0)
1607 return boolean_true_node
;
1608 else if (cmp_min
!= -2 && cmp_max
!= -2)
1609 return boolean_false_node
;
1614 else if (comp
== NE_EXPR
)
1618 /* If VR0 is completely to the left or completely to the right
1619 of VR1, they are always different. Notice that we need to
1620 make sure that both comparisons yield similar results to
1621 avoid comparing values that cannot be compared at
1623 cmp1
= compare_values (vr0
->max
, vr1
->min
);
1624 cmp2
= compare_values (vr0
->min
, vr1
->max
);
1625 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1626 return boolean_true_node
;
1628 /* If VR0 and VR1 represent a single value and are identical,
1630 else if (compare_values (vr0
->min
, vr0
->max
) == 0
1631 && compare_values (vr1
->min
, vr1
->max
) == 0
1632 && compare_values (vr0
->min
, vr1
->min
) == 0
1633 && compare_values (vr0
->max
, vr1
->max
) == 0)
1634 return boolean_false_node
;
1636 /* Otherwise, they may or may not be different. */
1640 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1644 /* If VR0 is to the left of VR1, return true. */
1645 tst
= compare_values (vr0
->max
, vr1
->min
);
1646 if ((comp
== LT_EXPR
&& tst
== -1)
1647 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1648 return boolean_true_node
;
1650 /* If VR0 is to the right of VR1, return false. */
1651 tst
= compare_values (vr0
->min
, vr1
->max
);
1652 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1653 || (comp
== LE_EXPR
&& tst
== 1))
1654 return boolean_false_node
;
1656 /* Otherwise, we don't know. */
1664 /* Given a value range VR, a value VAL and a comparison code COMP, return
1665 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1666 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1667 always returns false. Return NULL_TREE if it is not always
1668 possible to determine the value of the comparison. */
1671 compare_range_with_value (enum tree_code comp
, value_range_t
*vr
, tree val
)
1673 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
1676 /* Anti-ranges need to be handled separately. */
1677 if (vr
->type
== VR_ANTI_RANGE
)
1679 /* For anti-ranges, the only predicates that we can compute at
1680 compile time are equality and inequality. */
1687 /* ~[VAL, VAL] == VAL is always false. */
1688 if (compare_values (vr
->min
, val
) == 0
1689 && compare_values (vr
->max
, val
) == 0)
1690 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1695 if (comp
== EQ_EXPR
)
1697 /* EQ_EXPR may only be computed if VR represents exactly
1699 if (compare_values (vr
->min
, vr
->max
) == 0)
1701 int cmp
= compare_values (vr
->min
, val
);
1703 return boolean_true_node
;
1704 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1705 return boolean_false_node
;
1707 else if (compare_values (val
, vr
->min
) == -1
1708 || compare_values (vr
->max
, val
) == -1)
1709 return boolean_false_node
;
1713 else if (comp
== NE_EXPR
)
1715 /* If VAL is not inside VR, then they are always different. */
1716 if (compare_values (vr
->max
, val
) == -1
1717 || compare_values (vr
->min
, val
) == 1)
1718 return boolean_true_node
;
1720 /* If VR represents exactly one value equal to VAL, then return
1722 if (compare_values (vr
->min
, vr
->max
) == 0
1723 && compare_values (vr
->min
, val
) == 0)
1724 return boolean_false_node
;
1726 /* Otherwise, they may or may not be different. */
1729 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1733 /* If VR is to the left of VAL, return true. */
1734 tst
= compare_values (vr
->max
, val
);
1735 if ((comp
== LT_EXPR
&& tst
== -1)
1736 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1737 return boolean_true_node
;
1739 /* If VR is to the right of VAL, return false. */
1740 tst
= compare_values (vr
->min
, val
);
1741 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1742 || (comp
== LE_EXPR
&& tst
== 1))
1743 return boolean_false_node
;
1745 /* Otherwise, we don't know. */
1748 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1752 /* If VR is to the right of VAL, return true. */
1753 tst
= compare_values (vr
->min
, val
);
1754 if ((comp
== GT_EXPR
&& tst
== 1)
1755 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1756 return boolean_true_node
;
1758 /* If VR is to the left of VAL, return false. */
1759 tst
= compare_values (vr
->max
, val
);
1760 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1761 || (comp
== GE_EXPR
&& tst
== -1))
1762 return boolean_false_node
;
1764 /* Otherwise, we don't know. */
1772 /* Debugging dumps. */
1774 void dump_value_range (FILE *, value_range_t
*);
1775 void debug_value_range (value_range_t
*);
1776 void dump_all_value_ranges (FILE *);
1777 void debug_all_value_ranges (void);
1778 void dump_vr_equiv (FILE *, bitmap
);
1779 void debug_vr_equiv (bitmap
);
1782 /* Dump value range VR to FILE. */
1785 dump_value_range (FILE *file
, value_range_t
*vr
)
1788 fprintf (file
, "[]");
1789 else if (vr
->type
== VR_UNDEFINED
)
1790 fprintf (file
, "UNDEFINED");
1791 else if (vr
->type
== VR_RANGE
|| vr
->type
== VR_ANTI_RANGE
)
1793 tree type
= TREE_TYPE (vr
->min
);
1795 fprintf (file
, "%s[", (vr
->type
== VR_ANTI_RANGE
) ? "~" : "");
1797 if (INTEGRAL_TYPE_P (type
)
1798 && !TYPE_UNSIGNED (type
)
1799 && vr
->min
== TYPE_MIN_VALUE (type
))
1800 fprintf (file
, "-INF");
1802 print_generic_expr (file
, vr
->min
, 0);
1804 fprintf (file
, ", ");
1806 if (INTEGRAL_TYPE_P (type
)
1807 && vr
->max
== TYPE_MAX_VALUE (type
))
1808 fprintf (file
, "+INF");
1810 print_generic_expr (file
, vr
->max
, 0);
1812 fprintf (file
, "]");
1819 fprintf (file
, " EQUIVALENCES: { ");
1821 EXECUTE_IF_SET_IN_BITMAP (vr
->equiv
, 0, i
, bi
)
1823 print_generic_expr (file
, ssa_name (i
), 0);
1824 fprintf (file
, " ");
1828 fprintf (file
, "} (%u elements)", c
);
1831 else if (vr
->type
== VR_VARYING
)
1832 fprintf (file
, "VARYING");
1834 fprintf (file
, "INVALID RANGE");
1838 /* Dump value range VR to stderr. */
1841 debug_value_range (value_range_t
*vr
)
1843 dump_value_range (stderr
, vr
);
1847 /* Dump value ranges of all SSA_NAMEs to FILE. */
1850 dump_all_value_ranges (FILE *file
)
1854 for (i
= 0; i
< num_ssa_names
; i
++)
1858 print_generic_expr (file
, ssa_name (i
), 0);
1859 fprintf (file
, ": ");
1860 dump_value_range (file
, vr_value
[i
]);
1861 fprintf (file
, "\n");
1865 fprintf (file
, "\n");
1869 /* Dump all value ranges to stderr. */
1872 debug_all_value_ranges (void)
1874 dump_all_value_ranges (stderr
);
1878 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1879 create a new SSA name N and return the assertion assignment
1880 'V = ASSERT_EXPR <V, V OP W>'. */
1883 build_assert_expr_for (tree cond
, tree v
)
1887 gcc_assert (TREE_CODE (v
) == SSA_NAME
);
1888 n
= duplicate_ssa_name (v
, NULL_TREE
);
1890 if (COMPARISON_CLASS_P (cond
))
1892 tree a
= build (ASSERT_EXPR
, TREE_TYPE (v
), v
, cond
);
1893 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, a
);
1895 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1897 /* Given !V, build the assignment N = false. */
1898 tree op0
= TREE_OPERAND (cond
, 0);
1899 gcc_assert (op0
== v
);
1900 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, boolean_false_node
);
1902 else if (TREE_CODE (cond
) == SSA_NAME
)
1904 /* Given V, build the assignment N = true. */
1905 gcc_assert (v
== cond
);
1906 assertion
= build (MODIFY_EXPR
, TREE_TYPE (v
), n
, boolean_true_node
);
1911 SSA_NAME_DEF_STMT (n
) = assertion
;
1913 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1914 operand of the ASSERT_EXPR. Register the new name and the old one
1915 in the replacement table so that we can fix the SSA web after
1916 adding all the ASSERT_EXPRs. */
1917 register_new_name_mapping (n
, v
);
1923 /* Return false if EXPR is a predicate expression involving floating
1927 fp_predicate (tree expr
)
1929 return (COMPARISON_CLASS_P (expr
)
1930 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr
, 0))));
1934 /* If the range of values taken by OP can be inferred after STMT executes,
1935 return the comparison code (COMP_CODE_P) and value (VAL_P) that
1936 describes the inferred range. Return true if a range could be
1940 infer_value_range (tree stmt
, tree op
, enum tree_code
*comp_code_p
, tree
*val_p
)
1943 *comp_code_p
= ERROR_MARK
;
1945 /* Do not attempt to infer anything in names that flow through
1947 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
1950 /* Similarly, don't infer anything from statements that may throw
1952 if (tree_could_throw_p (stmt
))
1955 if (POINTER_TYPE_P (TREE_TYPE (op
)))
1958 unsigned num_uses
, num_derefs
;
1960 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
, &is_store
);
1961 if (num_derefs
> 0 && flag_delete_null_pointer_checks
)
1963 /* We can only assume that a pointer dereference will yield
1964 non-NULL if -fdelete-null-pointer-checks is enabled. */
1965 *val_p
= build_int_cst (TREE_TYPE (op
), 0);
1966 *comp_code_p
= NE_EXPR
;
1975 void dump_asserts_for (FILE *, tree
);
1976 void debug_asserts_for (tree
);
1977 void dump_all_asserts (FILE *);
1978 void debug_all_asserts (void);
1980 /* Dump all the registered assertions for NAME to FILE. */
1983 dump_asserts_for (FILE *file
, tree name
)
1987 fprintf (file
, "Assertions to be inserted for ");
1988 print_generic_expr (file
, name
, 0);
1989 fprintf (file
, "\n");
1991 loc
= asserts_for
[SSA_NAME_VERSION (name
)];
1994 fprintf (file
, "\t");
1995 print_generic_expr (file
, bsi_stmt (loc
->si
), 0);
1996 fprintf (file
, "\n\tBB #%d", loc
->bb
->index
);
1999 fprintf (file
, "\n\tEDGE %d->%d", loc
->e
->src
->index
,
2000 loc
->e
->dest
->index
);
2001 dump_edge_info (file
, loc
->e
, 0);
2003 fprintf (file
, "\n\tPREDICATE: ");
2004 print_generic_expr (file
, name
, 0);
2005 fprintf (file
, " %s ", tree_code_name
[(int)loc
->comp_code
]);
2006 print_generic_expr (file
, loc
->val
, 0);
2007 fprintf (file
, "\n\n");
2011 fprintf (file
, "\n");
2015 /* Dump all the registered assertions for NAME to stderr. */
2018 debug_asserts_for (tree name
)
2020 dump_asserts_for (stderr
, name
);
2024 /* Dump all the registered assertions for all the names to FILE. */
2027 dump_all_asserts (FILE *file
)
2032 fprintf (file
, "\nASSERT_EXPRs to be inserted\n\n");
2033 EXECUTE_IF_SET_IN_BITMAP (need_assert_for
, 0, i
, bi
)
2034 dump_asserts_for (file
, ssa_name (i
));
2035 fprintf (file
, "\n");
2039 /* Dump all the registered assertions for all the names to stderr. */
2042 debug_all_asserts (void)
2044 dump_all_asserts (stderr
);
2048 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2049 'NAME COMP_CODE VAL' at a location that dominates block BB or
2050 E->DEST, then register this location as a possible insertion point
2051 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2053 BB, E and SI provide the exact insertion point for the new
2054 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
2055 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2056 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2057 must not be NULL. */
2060 register_new_assert_for (tree name
,
2061 enum tree_code comp_code
,
2065 block_stmt_iterator si
)
2067 assert_locus_t n
, loc
, last_loc
;
2069 basic_block dest_bb
;
2071 #if defined ENABLE_CHECKING
2072 gcc_assert (bb
== NULL
|| e
== NULL
);
2075 gcc_assert (TREE_CODE (bsi_stmt (si
)) != COND_EXPR
2076 && TREE_CODE (bsi_stmt (si
)) != SWITCH_EXPR
);
2079 /* The new assertion A will be inserted at BB or E. We need to
2080 determine if the new location is dominated by a previously
2081 registered location for A. If we are doing an edge insertion,
2082 assume that A will be inserted at E->DEST. Note that this is not
2085 If E is a critical edge, it will be split. But even if E is
2086 split, the new block will dominate the same set of blocks that
2089 The reverse, however, is not true, blocks dominated by E->DEST
2090 will not be dominated by the new block created to split E. So,
2091 if the insertion location is on a critical edge, we will not use
2092 the new location to move another assertion previously registered
2093 at a block dominated by E->DEST. */
2094 dest_bb
= (bb
) ? bb
: e
->dest
;
2096 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2097 VAL at a block dominating DEST_BB, then we don't need to insert a new
2098 one. Similarly, if the same assertion already exists at a block
2099 dominated by DEST_BB and the new location is not on a critical
2100 edge, then update the existing location for the assertion (i.e.,
2101 move the assertion up in the dominance tree).
2103 Note, this is implemented as a simple linked list because there
2104 should not be more than a handful of assertions registered per
2105 name. If this becomes a performance problem, a table hashed by
2106 COMP_CODE and VAL could be implemented. */
2107 loc
= asserts_for
[SSA_NAME_VERSION (name
)];
2112 if (loc
->comp_code
== comp_code
2114 || operand_equal_p (loc
->val
, val
, 0)))
2116 /* If the assertion NAME COMP_CODE VAL has already been
2117 registered at a basic block that dominates DEST_BB, then
2118 we don't need to insert the same assertion again. Note
2119 that we don't check strict dominance here to avoid
2120 replicating the same assertion inside the same basic
2121 block more than once (e.g., when a pointer is
2122 dereferenced several times inside a block).
2124 An exception to this rule are edge insertions. If the
2125 new assertion is to be inserted on edge E, then it will
2126 dominate all the other insertions that we may want to
2127 insert in DEST_BB. So, if we are doing an edge
2128 insertion, don't do this dominance check. */
2130 && dominated_by_p (CDI_DOMINATORS
, dest_bb
, loc
->bb
))
2133 /* Otherwise, if E is not a critical edge and DEST_BB
2134 dominates the existing location for the assertion, move
2135 the assertion up in the dominance tree by updating its
2136 location information. */
2137 if ((e
== NULL
|| !EDGE_CRITICAL_P (e
))
2138 && dominated_by_p (CDI_DOMINATORS
, loc
->bb
, dest_bb
))
2147 /* Update the last node of the list and move to the next one. */
2152 /* If we didn't find an assertion already registered for
2153 NAME COMP_CODE VAL, add a new one at the end of the list of
2154 assertions associated with NAME. */
2155 n
= xmalloc (sizeof (*n
));
2159 n
->comp_code
= comp_code
;
2166 asserts_for
[SSA_NAME_VERSION (name
)] = n
;
2168 bitmap_set_bit (need_assert_for
, SSA_NAME_VERSION (name
));
2172 /* Try to register an edge assertion for SSA name NAME on edge E for
2173 the conditional jump pointed by SI. Return true if an assertion
2174 for NAME could be registered. */
2177 register_edge_assert_for (tree name
, edge e
, block_stmt_iterator si
)
2180 enum tree_code comp_code
;
2182 stmt
= bsi_stmt (si
);
2184 /* Do not attempt to infer anything in names that flow through
2186 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
))
2189 /* If NAME was not found in the sub-graph reachable from E, then
2190 there's nothing to do. */
2191 if (!TEST_BIT (found_in_subgraph
, SSA_NAME_VERSION (name
)))
2194 /* We found a use of NAME in the sub-graph rooted at E->DEST.
2195 Register an assertion for NAME according to the value that NAME
2197 if (TREE_CODE (stmt
) == COND_EXPR
)
2199 /* If BB ends in a COND_EXPR then NAME then we should insert
2200 the original predicate on EDGE_TRUE_VALUE and the
2201 opposite predicate on EDGE_FALSE_VALUE. */
2202 tree cond
= COND_EXPR_COND (stmt
);
2203 bool is_else_edge
= (e
->flags
& EDGE_FALSE_VALUE
) != 0;
2205 /* Predicates may be a single SSA name or NAME OP VAL. */
2208 /* If the predicate is a name, it must be NAME, in which
2209 case we create the predicate NAME == true or
2210 NAME == false accordingly. */
2211 comp_code
= EQ_EXPR
;
2212 val
= (is_else_edge
) ? boolean_false_node
: boolean_true_node
;
2216 /* Otherwise, we have a comparison of the form NAME COMP VAL
2217 or VAL COMP NAME. */
2218 if (name
== TREE_OPERAND (cond
, 1))
2220 /* If the predicate is of the form VAL COMP NAME, flip
2221 COMP around because we need to register NAME as the
2222 first operand in the predicate. */
2223 comp_code
= opposite_comparison (TREE_CODE (cond
));
2224 val
= TREE_OPERAND (cond
, 0);
2228 /* The comparison is of the form NAME COMP VAL, so the
2229 comparison code remains unchanged. */
2230 comp_code
= TREE_CODE (cond
);
2231 val
= TREE_OPERAND (cond
, 1);
2234 /* If we are inserting the assertion on the ELSE edge, we
2235 need to invert the sign comparison. */
2237 comp_code
= invert_tree_comparison (comp_code
, 0);
2242 /* FIXME. Handle SWITCH_EXPR. */
2246 register_new_assert_for (name
, comp_code
, val
, NULL
, e
, si
);
2251 static bool find_assert_locations (basic_block bb
);
2253 /* Determine whether the outgoing edges of BB should receive an
2254 ASSERT_EXPR for each of the operands of BB's last statement. The
2255 last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2257 If any of the sub-graphs rooted at BB have an interesting use of
2258 the predicate operands, an assert location node is added to the
2259 list of assertions for the corresponding operands. */
2262 find_conditional_asserts (basic_block bb
)
2265 block_stmt_iterator last_si
;
2271 need_assert
= false;
2272 last_si
= bsi_last (bb
);
2273 last
= bsi_stmt (last_si
);
2275 /* Look for uses of the operands in each of the sub-graphs
2276 rooted at BB. We need to check each of the outgoing edges
2277 separately, so that we know what kind of ASSERT_EXPR to
2279 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2284 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2285 Otherwise, when we finish traversing each of the sub-graphs, we
2286 won't know whether the variables were found in the sub-graphs or
2287 if they had been found in a block upstream from BB. */
2288 FOR_EACH_SSA_TREE_OPERAND (op
, last
, iter
, SSA_OP_USE
)
2289 RESET_BIT (found_in_subgraph
, SSA_NAME_VERSION (op
));
2291 /* Traverse the strictly dominated sub-graph rooted at E->DEST
2292 to determine if any of the operands in the conditional
2293 predicate are used. */
2295 need_assert
|= find_assert_locations (e
->dest
);
2297 /* Register the necessary assertions for each operand in the
2298 conditional predicate. */
2299 FOR_EACH_SSA_TREE_OPERAND (op
, last
, iter
, SSA_OP_USE
)
2300 need_assert
|= register_edge_assert_for (op
, e
, last_si
);
2303 /* Finally, indicate that we have found the operands in the
2305 FOR_EACH_SSA_TREE_OPERAND (op
, last
, iter
, SSA_OP_USE
)
2306 SET_BIT (found_in_subgraph
, SSA_NAME_VERSION (op
));
2312 /* Traverse all the statements in block BB looking for statements that
2313 may generate useful assertions for the SSA names in their operand.
2314 If a statement produces a useful assertion A for name N_i, then the
2315 list of assertions already generated for N_i is scanned to
2316 determine if A is actually needed.
2318 If N_i already had the assertion A at a location dominating the
2319 current location, then nothing needs to be done. Otherwise, the
2320 new location for A is recorded instead.
2322 1- For every statement S in BB, all the variables used by S are
2323 added to bitmap FOUND_IN_SUBGRAPH.
2325 2- If statement S uses an operand N in a way that exposes a known
2326 value range for N, then if N was not already generated by an
2327 ASSERT_EXPR, create a new assert location for N. For instance,
2328 if N is a pointer and the statement dereferences it, we can
2329 assume that N is not NULL.
2331 3- COND_EXPRs are a special case of #2. We can derive range
2332 information from the predicate but need to insert different
2333 ASSERT_EXPRs for each of the sub-graphs rooted at the
2334 conditional block. If the last statement of BB is a conditional
2335 expression of the form 'X op Y', then
2337 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2339 b) If the conditional is the only entry point to the sub-graph
2340 corresponding to the THEN_CLAUSE, recurse into it. On
2341 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2342 an ASSERT_EXPR is added for the corresponding variable.
2344 c) Repeat step (b) on the ELSE_CLAUSE.
2346 d) Mark X and Y in FOUND_IN_SUBGRAPH.
2355 In this case, an assertion on the THEN clause is useful to
2356 determine that 'a' is always 9 on that edge. However, an assertion
2357 on the ELSE clause would be unnecessary.
2359 4- If BB does not end in a conditional expression, then we recurse
2360 into BB's dominator children.
2362 At the end of the recursive traversal, every SSA name will have a
2363 list of locations where ASSERT_EXPRs should be added. When a new
2364 location for name N is found, it is registered by calling
2365 register_new_assert_for. That function keeps track of all the
2366 registered assertions to prevent adding unnecessary assertions.
2367 For instance, if a pointer P_4 is dereferenced more than once in a
2368 dominator tree, only the location dominating all the dereference of
2369 P_4 will receive an ASSERT_EXPR.
2371 If this function returns true, then it means that there are names
2372 for which we need to generate ASSERT_EXPRs. Those assertions are
2373 inserted by process_assert_insertions.
2375 TODO. Handle SWITCH_EXPR. */
2378 find_assert_locations (basic_block bb
)
2380 block_stmt_iterator si
;
2385 if (TEST_BIT (blocks_visited
, bb
->index
))
2388 SET_BIT (blocks_visited
, bb
->index
);
2390 need_assert
= false;
2392 /* Traverse all PHI nodes in BB marking used operands. */
2393 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2395 use_operand_p arg_p
;
2398 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_USE
)
2400 tree arg
= USE_FROM_PTR (arg_p
);
2401 if (TREE_CODE (arg
) == SSA_NAME
)
2403 gcc_assert (is_gimple_reg (PHI_RESULT (phi
)));
2404 SET_BIT (found_in_subgraph
, SSA_NAME_VERSION (arg
));
2409 /* Traverse all the statements in BB marking used names and looking
2410 for statements that may infer assertions for their used operands. */
2412 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
2417 stmt
= bsi_stmt (si
);
2419 /* See if we can derive an assertion for any of STMT's operands. */
2420 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_USE
)
2423 enum tree_code comp_code
;
2425 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
2426 the sub-graph of a conditional block, when we return from
2427 this recursive walk, our parent will use the
2428 FOUND_IN_SUBGRAPH bitset to determine if one of the
2429 operands it was looking for was present in the sub-graph. */
2430 SET_BIT (found_in_subgraph
, SSA_NAME_VERSION (op
));
2432 /* If OP is used only once, namely in this STMT, don't
2433 bother creating an ASSERT_EXPR for it. Such an
2434 ASSERT_EXPR would do nothing but increase compile time.
2435 Experiments show that with this simple check, we can save
2436 more than 20% of ASSERT_EXPRs. */
2437 if (has_single_use (op
))
2440 /* If OP is used in such a way that we can infer a value
2441 range for it, and we don't find a previous assertion for
2442 it, create a new assertion location node for OP. */
2443 if (infer_value_range (stmt
, op
, &comp_code
, &value
))
2445 register_new_assert_for (op
, comp_code
, value
, bb
, NULL
, si
);
2450 /* Remember the last statement of the block. */
2454 /* If BB's last statement is a conditional expression
2455 involving integer operands, recurse into each of the sub-graphs
2456 rooted at BB to determine if we need to add ASSERT_EXPRs. */
2458 && TREE_CODE (last
) == COND_EXPR
2459 && !fp_predicate (COND_EXPR_COND (last
))
2460 && !ZERO_SSA_OPERANDS (last
, SSA_OP_USE
))
2461 need_assert
|= find_conditional_asserts (bb
);
2463 /* Recurse into the dominator children of BB. */
2464 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2466 son
= next_dom_son (CDI_DOMINATORS
, son
))
2467 need_assert
|= find_assert_locations (son
);
2473 /* Create an ASSERT_EXPR for NAME and insert it in the location
2474 indicated by LOC. Return true if we made any edge insertions. */
2477 process_assert_insertions_for (tree name
, assert_locus_t loc
)
2479 /* Build the comparison expression NAME_i COMP_CODE VAL. */
2480 tree stmt
, cond
, assert_expr
;
2484 cond
= build (loc
->comp_code
, boolean_type_node
, name
, loc
->val
);
2485 assert_expr
= build_assert_expr_for (cond
, name
);
2489 /* We have been asked to insert the assertion on an edge. This
2490 is used only by COND_EXPR and SWITCH_EXPR assertions. */
2491 #if defined ENABLE_CHECKING
2492 gcc_assert (TREE_CODE (bsi_stmt (loc
->si
)) == COND_EXPR
2493 || TREE_CODE (bsi_stmt (loc
->si
)) == SWITCH_EXPR
);
2496 bsi_insert_on_edge (loc
->e
, assert_expr
);
2500 /* Otherwise, we can insert right after LOC->SI iff the
2501 statement must not be the last statement in the block. */
2502 stmt
= bsi_stmt (loc
->si
);
2503 if (!stmt_ends_bb_p (stmt
))
2505 bsi_insert_after (&loc
->si
, assert_expr
, BSI_SAME_STMT
);
2509 /* If STMT must be the last statement in BB, we can only insert new
2510 assertions on the non-abnormal edge out of BB. Note that since
2511 STMT is not control flow, there may only be one non-abnormal edge
2513 FOR_EACH_EDGE (e
, ei
, loc
->bb
->succs
)
2514 if (!(e
->flags
& EDGE_ABNORMAL
))
2516 bsi_insert_on_edge (e
, assert_expr
);
2524 /* Process all the insertions registered for every name N_i registered
2525 in NEED_ASSERT_FOR. The list of assertions to be inserted are
2526 found in ASSERTS_FOR[i]. */
2529 process_assert_insertions (void)
2533 bool update_edges_p
= false;
2534 int num_asserts
= 0;
2536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2537 dump_all_asserts (dump_file
);
2539 EXECUTE_IF_SET_IN_BITMAP (need_assert_for
, 0, i
, bi
)
2541 assert_locus_t loc
= asserts_for
[i
];
2546 assert_locus_t next
= loc
->next
;
2547 update_edges_p
|= process_assert_insertions_for (ssa_name (i
), loc
);
2555 bsi_commit_edge_inserts ();
2557 if (dump_file
&& (dump_flags
& TDF_STATS
))
2558 fprintf (dump_file
, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
2563 /* Traverse the flowgraph looking for conditional jumps to insert range
2564 expressions. These range expressions are meant to provide information
2565 to optimizations that need to reason in terms of value ranges. They
2566 will not be expanded into RTL. For instance, given:
2575 this pass will transform the code into:
2581 x = ASSERT_EXPR <x, x < y>
2586 y = ASSERT_EXPR <y, x <= y>
2590 The idea is that once copy and constant propagation have run, other
2591 optimizations will be able to determine what ranges of values can 'x'
2592 take in different paths of the code, simply by checking the reaching
2593 definition of 'x'. */
2596 insert_range_assertions (void)
2602 found_in_subgraph
= sbitmap_alloc (num_ssa_names
);
2603 sbitmap_zero (found_in_subgraph
);
2605 blocks_visited
= sbitmap_alloc (last_basic_block
);
2606 sbitmap_zero (blocks_visited
);
2608 need_assert_for
= BITMAP_ALLOC (NULL
);
2609 asserts_for
= xmalloc (num_ssa_names
* sizeof (assert_locus_t
));
2610 memset (asserts_for
, 0, num_ssa_names
* sizeof (assert_locus_t
));
2612 calculate_dominance_info (CDI_DOMINATORS
);
2614 update_ssa_p
= false;
2615 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
2616 if (find_assert_locations (e
->dest
))
2617 update_ssa_p
= true;
2621 process_assert_insertions ();
2622 update_ssa (TODO_update_ssa_no_phi
);
2625 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2627 fprintf (dump_file
, "\nSSA form after inserting ASSERT_EXPRs\n");
2628 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
2631 sbitmap_free (found_in_subgraph
);
2633 BITMAP_FREE (need_assert_for
);
2637 /* Convert range assertion expressions into the implied copies.
2639 FIXME, this will eventually lead to copy propagation removing the
2640 names that had useful range information attached to them. For
2641 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
2642 then N_i will have the range [3, +INF].
2644 However, by converting the assertion into the implied copy
2645 operation N_i = N_j, we will then copy-propagate N_j into the uses
2646 of N_i and lose the range information. We may want to hold on to
2647 ASSERT_EXPRs a little while longer as the ranges could be used in
2648 things like jump threading.
2650 The problem with keeping ASSERT_EXPRs around is that passes after
2651 VRP need to handle them appropriately. */
2654 remove_range_assertions (void)
2657 block_stmt_iterator si
;
2660 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
2662 tree stmt
= bsi_stmt (si
);
2664 if (TREE_CODE (stmt
) == MODIFY_EXPR
2665 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == ASSERT_EXPR
)
2667 tree rhs
= TREE_OPERAND (stmt
, 1);
2668 tree cond
= fold (ASSERT_EXPR_COND (rhs
));
2669 gcc_assert (cond
!= boolean_false_node
);
2670 TREE_OPERAND (stmt
, 1) = ASSERT_EXPR_VAR (rhs
);
2677 /* Return true if STMT is interesting for VRP. */
2680 stmt_interesting_for_vrp (tree stmt
)
2682 if (TREE_CODE (stmt
) == PHI_NODE
2683 && is_gimple_reg (PHI_RESULT (stmt
))
2684 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt
)))
2685 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt
)))))
2687 else if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2689 tree lhs
= TREE_OPERAND (stmt
, 0);
2691 if (TREE_CODE (lhs
) == SSA_NAME
2692 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2693 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2694 && ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
2697 else if (TREE_CODE (stmt
) == COND_EXPR
|| TREE_CODE (stmt
) == SWITCH_EXPR
)
2704 /* Initialize local data structures for VRP. Return true if VRP
2705 is worth running (i.e. if we found any statements that could
2706 benefit from range information). */
2709 vrp_initialize (void)
2713 vr_value
= xmalloc (num_ssa_names
* sizeof (value_range_t
*));
2714 memset (vr_value
, 0, num_ssa_names
* sizeof (value_range_t
*));
2718 block_stmt_iterator si
;
2721 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2723 if (!stmt_interesting_for_vrp (phi
))
2725 tree lhs
= PHI_RESULT (phi
);
2726 set_value_range_to_varying (get_value_range (lhs
));
2727 DONT_SIMULATE_AGAIN (phi
) = true;
2730 DONT_SIMULATE_AGAIN (phi
) = false;
2733 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
2735 tree stmt
= bsi_stmt (si
);
2737 if (!stmt_interesting_for_vrp (stmt
))
2741 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
2742 set_value_range_to_varying (get_value_range (def
));
2743 DONT_SIMULATE_AGAIN (stmt
) = true;
2747 DONT_SIMULATE_AGAIN (stmt
) = false;
2754 /* Visit assignment STMT. If it produces an interesting range, record
2755 the SSA name in *OUTPUT_P. */
2757 static enum ssa_prop_result
2758 vrp_visit_assignment (tree stmt
, tree
*output_p
)
2763 lhs
= TREE_OPERAND (stmt
, 0);
2764 rhs
= TREE_OPERAND (stmt
, 1);
2766 /* We only keep track of ranges in integral and pointer types. */
2767 if (TREE_CODE (lhs
) == SSA_NAME
2768 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2769 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
2772 value_range_t new_vr
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
2774 extract_range_from_expr (&new_vr
, rhs
);
2776 /* If STMT is inside a loop, we may be able to know something
2777 else about the range of LHS by examining scalar evolution
2779 if (cfg_loops
&& (l
= loop_containing_stmt (stmt
)))
2780 adjust_range_with_scev (&new_vr
, l
, stmt
, lhs
);
2782 if (update_value_range (lhs
, &new_vr
))
2786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2788 fprintf (dump_file
, "Found new range for ");
2789 print_generic_expr (dump_file
, lhs
, 0);
2790 fprintf (dump_file
, ": ");
2791 dump_value_range (dump_file
, &new_vr
);
2792 fprintf (dump_file
, "\n\n");
2795 if (new_vr
.type
== VR_VARYING
)
2796 return SSA_PROP_VARYING
;
2798 return SSA_PROP_INTERESTING
;
2801 return SSA_PROP_NOT_INTERESTING
;
2804 /* Every other statement produces no useful ranges. */
2805 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
2806 set_value_range_to_varying (get_value_range (def
));
2808 return SSA_PROP_VARYING
;
2812 /* Compare all the value ranges for names equivalent to VAR with VAL
2813 using comparison code COMP. Return the same value returned by
2814 compare_range_with_value. */
2817 compare_name_with_value (enum tree_code comp
, tree var
, tree val
)
2824 t
= retval
= NULL_TREE
;
2826 /* Get the set of equivalences for VAR. */
2827 e
= get_value_range (var
)->equiv
;
2829 /* Add VAR to its own set of equivalences so that VAR's value range
2830 is processed by this loop (otherwise, we would have to replicate
2831 the body of the loop just to check VAR's value range). */
2832 bitmap_set_bit (e
, SSA_NAME_VERSION (var
));
2834 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2836 value_range_t equiv_vr
= *(vr_value
[i
]);
2838 /* If name N_i does not have a valid range, use N_i as its own
2839 range. This allows us to compare against names that may
2840 have N_i in their ranges. */
2841 if (equiv_vr
.type
== VR_VARYING
|| equiv_vr
.type
== VR_UNDEFINED
)
2843 equiv_vr
.type
= VR_RANGE
;
2844 equiv_vr
.min
= ssa_name (i
);
2845 equiv_vr
.max
= ssa_name (i
);
2848 t
= compare_range_with_value (comp
, &equiv_vr
, val
);
2851 /* All the ranges should compare the same against VAL. */
2852 gcc_assert (retval
== NULL
|| t
== retval
);
2857 /* Remove VAR from its own equivalence set. */
2858 bitmap_clear_bit (e
, SSA_NAME_VERSION (var
));
2863 /* We couldn't find a non-NULL value for the predicate. */
2868 /* Given a comparison code COMP and names N1 and N2, compare all the
2869 ranges equivalent to N1 against all the ranges equivalent to N2
2870 to determine the value of N1 COMP N2. Return the same value
2871 returned by compare_ranges. */
2874 compare_names (enum tree_code comp
, tree n1
, tree n2
)
2878 bitmap_iterator bi1
, bi2
;
2881 /* Compare the ranges of every name equivalent to N1 against the
2882 ranges of every name equivalent to N2. */
2883 e1
= get_value_range (n1
)->equiv
;
2884 e2
= get_value_range (n2
)->equiv
;
2886 /* Add N1 and N2 to their own set of equivalences to avoid
2887 duplicating the body of the loop just to check N1 and N2
2889 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2890 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2892 /* If the equivalence sets have a common intersection, then the two
2893 names can be compared without checking their ranges. */
2894 if (bitmap_intersect_p (e1
, e2
))
2896 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2897 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2899 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2901 : boolean_false_node
;
2904 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2905 N2 to their own set of equivalences to avoid duplicating the body
2906 of the loop just to check N1 and N2 ranges. */
2907 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2909 value_range_t vr1
= *(vr_value
[i1
]);
2911 /* If the range is VARYING or UNDEFINED, use the name itself. */
2912 if (vr1
.type
== VR_VARYING
|| vr1
.type
== VR_UNDEFINED
)
2914 vr1
.type
= VR_RANGE
;
2915 vr1
.min
= ssa_name (i1
);
2916 vr1
.max
= ssa_name (i1
);
2919 t
= retval
= NULL_TREE
;
2920 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2922 value_range_t vr2
= *(vr_value
[i2
]);
2924 if (vr2
.type
== VR_VARYING
|| vr2
.type
== VR_UNDEFINED
)
2926 vr2
.type
= VR_RANGE
;
2927 vr2
.min
= ssa_name (i2
);
2928 vr2
.max
= ssa_name (i2
);
2931 t
= compare_ranges (comp
, &vr1
, &vr2
);
2934 /* All the ranges in the equivalent sets should compare
2936 gcc_assert (retval
== NULL
|| t
== retval
);
2943 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2944 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2949 /* None of the equivalent ranges are useful in computing this
2951 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2952 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2957 /* Given a conditional predicate COND, try to determine if COND yields
2958 true or false based on the value ranges of its operands. Return
2959 BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
2960 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
2961 NULL if the conditional cannot be evaluated at compile time.
2963 If USE_EQUIV_P is true, the ranges of all the names equivalent with
2964 the operands in COND are used when trying to compute its value.
2965 This is only used during final substitution. During propagation,
2966 we only check the range of each variable and not its equivalents. */
2969 vrp_evaluate_conditional (tree cond
, bool use_equiv_p
)
2971 gcc_assert (TREE_CODE (cond
) == SSA_NAME
2972 || TREE_CODE_CLASS (TREE_CODE (cond
)) == tcc_comparison
);
2974 if (TREE_CODE (cond
) == SSA_NAME
)
2980 retval
= compare_name_with_value (NE_EXPR
, cond
, boolean_false_node
);
2983 value_range_t
*vr
= get_value_range (cond
);
2984 retval
= compare_range_with_value (NE_EXPR
, vr
, boolean_false_node
);
2987 /* If COND has a known boolean range, return it. */
2991 /* Otherwise, if COND has a symbolic range of exactly one value,
2993 vr
= get_value_range (cond
);
2994 if (vr
->type
== VR_RANGE
&& vr
->min
== vr
->max
)
2999 tree op0
= TREE_OPERAND (cond
, 0);
3000 tree op1
= TREE_OPERAND (cond
, 1);
3002 /* We only deal with integral and pointer types. */
3003 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3004 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
3009 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
)
3010 return compare_names (TREE_CODE (cond
), op0
, op1
);
3011 else if (TREE_CODE (op0
) == SSA_NAME
)
3012 return compare_name_with_value (TREE_CODE (cond
), op0
, op1
);
3013 else if (TREE_CODE (op1
) == SSA_NAME
)
3014 return compare_name_with_value (
3015 opposite_comparison (TREE_CODE (cond
)), op1
, op0
);
3019 value_range_t
*vr0
, *vr1
;
3021 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
3022 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
3025 return compare_ranges (TREE_CODE (cond
), vr0
, vr1
);
3026 else if (vr0
&& vr1
== NULL
)
3027 return compare_range_with_value (TREE_CODE (cond
), vr0
, op1
);
3028 else if (vr0
== NULL
&& vr1
)
3029 return compare_range_with_value (
3030 opposite_comparison (TREE_CODE (cond
)), vr1
, op0
);
3034 /* Anything else cannot be computed statically. */
3039 /* Visit conditional statement STMT. If we can determine which edge
3040 will be taken out of STMT's basic block, record it in
3041 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
3042 SSA_PROP_VARYING. */
3044 static enum ssa_prop_result
3045 vrp_visit_cond_stmt (tree stmt
, edge
*taken_edge_p
)
3049 *taken_edge_p
= NULL
;
3051 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
3052 add ASSERT_EXPRs for them. */
3053 if (TREE_CODE (stmt
) == SWITCH_EXPR
)
3054 return SSA_PROP_VARYING
;
3056 cond
= COND_EXPR_COND (stmt
);
3058 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3063 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
3064 print_generic_expr (dump_file
, cond
, 0);
3065 fprintf (dump_file
, "\nWith known ranges\n");
3067 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
3069 fprintf (dump_file
, "\t");
3070 print_generic_expr (dump_file
, use
, 0);
3071 fprintf (dump_file
, ": ");
3072 dump_value_range (dump_file
, vr_value
[SSA_NAME_VERSION (use
)]);
3075 fprintf (dump_file
, "\n");
3078 /* Compute the value of the predicate COND by checking the known
3079 ranges of each of its operands.
3081 Note that we cannot evaluate all the equivalent ranges here
3082 because those ranges may not yet be final and with the current
3083 propagation strategy, we cannot determine when the value ranges
3084 of the names in the equivalence set have changed.
3086 For instance, given the following code fragment
3090 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3094 Assume that on the first visit to i_14, i_5 has the temporary
3095 range [8, 8] because the second argument to the PHI function is
3096 not yet executable. We derive the range ~[0, 0] for i_14 and the
3097 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
3098 the first time, since i_14 is equivalent to the range [8, 8], we
3099 determine that the predicate is always false.
3101 On the next round of propagation, i_13 is determined to be
3102 VARYING, which causes i_5 to drop down to VARYING. So, another
3103 visit to i_14 is scheduled. In this second visit, we compute the
3104 exact same range and equivalence set for i_14, namely ~[0, 0] and
3105 { i_5 }. But we did not have the previous range for i_5
3106 registered, so vrp_visit_assignment thinks that the range for
3107 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
3108 is not visited again, which stops propagation from visiting
3109 statements in the THEN clause of that if().
3111 To properly fix this we would need to keep the previous range
3112 value for the names in the equivalence set. This way we would've
3113 discovered that from one visit to the other i_5 changed from
3114 range [8, 8] to VR_VARYING.
3116 However, fixing this apparent limitation may not be worth the
3117 additional checking. Testing on several code bases (GCC, DLV,
3118 MICO, TRAMP3D and SPEC2000) showed that doing this results in
3119 4 more predicates folded in SPEC. */
3120 val
= vrp_evaluate_conditional (cond
, false);
3122 *taken_edge_p
= find_taken_edge (bb_for_stmt (stmt
), val
);
3124 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3126 fprintf (dump_file
, "\nPredicate evaluates to: ");
3127 if (val
== NULL_TREE
)
3128 fprintf (dump_file
, "DON'T KNOW\n");
3130 print_generic_stmt (dump_file
, val
, 0);
3133 return (*taken_edge_p
) ? SSA_PROP_INTERESTING
: SSA_PROP_VARYING
;
3137 /* Evaluate statement STMT. If the statement produces a useful range,
3138 return SSA_PROP_INTERESTING and record the SSA name with the
3139 interesting range into *OUTPUT_P.
3141 If STMT is a conditional branch and we can determine its truth
3142 value, the taken edge is recorded in *TAKEN_EDGE_P.
3144 If STMT produces a varying value, return SSA_PROP_VARYING. */
3146 static enum ssa_prop_result
3147 vrp_visit_stmt (tree stmt
, edge
*taken_edge_p
, tree
*output_p
)
3153 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3155 fprintf (dump_file
, "\nVisiting statement:\n");
3156 print_generic_stmt (dump_file
, stmt
, dump_flags
);
3157 fprintf (dump_file
, "\n");
3160 ann
= stmt_ann (stmt
);
3161 if (TREE_CODE (stmt
) == MODIFY_EXPR
3162 && ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
3163 return vrp_visit_assignment (stmt
, output_p
);
3164 else if (TREE_CODE (stmt
) == COND_EXPR
|| TREE_CODE (stmt
) == SWITCH_EXPR
)
3165 return vrp_visit_cond_stmt (stmt
, taken_edge_p
);
3167 /* All other statements produce nothing of interest for VRP, so mark
3168 their outputs varying and prevent further simulation. */
3169 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
3170 set_value_range_to_varying (get_value_range (def
));
3172 return SSA_PROP_VARYING
;
3176 /* Meet operation for value ranges. Given two value ranges VR0 and
3177 VR1, store in VR0 the result of meeting VR0 and VR1.
3179 The meeting rules are as follows:
3181 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3183 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3184 union of VR0 and VR1. */
3187 vrp_meet (value_range_t
*vr0
, value_range_t
*vr1
)
3189 if (vr0
->type
== VR_UNDEFINED
)
3191 copy_value_range (vr0
, vr1
);
3195 if (vr1
->type
== VR_UNDEFINED
)
3197 /* Nothing to do. VR0 already has the resulting range. */
3201 if (vr0
->type
== VR_VARYING
)
3203 /* Nothing to do. VR0 already has the resulting range. */
3207 if (vr1
->type
== VR_VARYING
)
3209 set_value_range_to_varying (vr0
);
3213 if (vr0
->type
== VR_RANGE
&& vr1
->type
== VR_RANGE
)
3215 /* If VR0 and VR1 have a non-empty intersection, compute the
3216 union of both ranges. */
3217 if (value_ranges_intersect_p (vr0
, vr1
))
3222 /* The lower limit of the new range is the minimum of the
3223 two ranges. If they cannot be compared, the result is
3225 cmp
= compare_values (vr0
->min
, vr1
->min
);
3226 if (cmp
== 0 || cmp
== 1)
3232 set_value_range_to_varying (vr0
);
3236 /* Similarly, the upper limit of the new range is the
3237 maximum of the two ranges. If they cannot be compared,
3238 the result is VARYING. */
3239 cmp
= compare_values (vr0
->max
, vr1
->max
);
3240 if (cmp
== 0 || cmp
== -1)
3246 set_value_range_to_varying (vr0
);
3250 /* The resulting set of equivalences is the intersection of
3252 if (vr0
->equiv
&& vr1
->equiv
&& vr0
->equiv
!= vr1
->equiv
)
3253 bitmap_and_into (vr0
->equiv
, vr1
->equiv
);
3255 set_value_range (vr0
, vr0
->type
, min
, max
, vr0
->equiv
);
3260 else if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
3262 /* Two anti-ranges meet only if they are both identical. */
3263 if (compare_values (vr0
->min
, vr1
->min
) == 0
3264 && compare_values (vr0
->max
, vr1
->max
) == 0
3265 && compare_values (vr0
->min
, vr0
->max
) == 0)
3267 /* The resulting set of equivalences is the intersection of
3269 if (vr0
->equiv
&& vr1
->equiv
&& vr0
->equiv
!= vr1
->equiv
)
3270 bitmap_and_into (vr0
->equiv
, vr1
->equiv
);
3275 else if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
3277 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
3278 meet only if the ranges have an empty intersection. The
3279 result of the meet operation is the anti-range. */
3280 if (!symbolic_range_p (vr0
)
3281 && !symbolic_range_p (vr1
)
3282 && !value_ranges_intersect_p (vr0
, vr1
))
3284 if (vr1
->type
== VR_ANTI_RANGE
)
3285 copy_value_range (vr0
, vr1
);
3296 /* The two range VR0 and VR1 do not meet. Before giving up and
3297 setting the result to VARYING, see if we can at least derive a
3298 useful anti-range. */
3299 if (!symbolic_range_p (vr0
)
3300 && !range_includes_zero_p (vr0
)
3301 && !symbolic_range_p (vr1
)
3302 && !range_includes_zero_p (vr1
))
3303 set_value_range_to_nonnull (vr0
, TREE_TYPE (vr0
->min
));
3305 set_value_range_to_varying (vr0
);
3309 /* Visit all arguments for PHI node PHI that flow through executable
3310 edges. If a valid value range can be derived from all the incoming
3311 value ranges, set a new range for the LHS of PHI. */
3313 static enum ssa_prop_result
3314 vrp_visit_phi_node (tree phi
)
3317 tree lhs
= PHI_RESULT (phi
);
3318 value_range_t
*lhs_vr
= get_value_range (lhs
);
3319 value_range_t vr_result
= { VR_UNDEFINED
, NULL_TREE
, NULL_TREE
, NULL
};
3321 copy_value_range (&vr_result
, lhs_vr
);
3323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3325 fprintf (dump_file
, "\nVisiting PHI node: ");
3326 print_generic_expr (dump_file
, phi
, dump_flags
);
3329 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
3331 edge e
= PHI_ARG_EDGE (phi
, i
);
3333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3336 "\n Argument #%d (%d -> %d %sexecutable)\n",
3337 i
, e
->src
->index
, e
->dest
->index
,
3338 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
3341 if (e
->flags
& EDGE_EXECUTABLE
)
3343 tree arg
= PHI_ARG_DEF (phi
, i
);
3344 value_range_t vr_arg
;
3346 if (TREE_CODE (arg
) == SSA_NAME
)
3347 vr_arg
= *(get_value_range (arg
));
3350 vr_arg
.type
= VR_RANGE
;
3353 vr_arg
.equiv
= NULL
;
3356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3358 fprintf (dump_file
, "\t");
3359 print_generic_expr (dump_file
, arg
, dump_flags
);
3360 fprintf (dump_file
, "\n\tValue: ");
3361 dump_value_range (dump_file
, &vr_arg
);
3362 fprintf (dump_file
, "\n");
3365 vrp_meet (&vr_result
, &vr_arg
);
3367 if (vr_result
.type
== VR_VARYING
)
3372 if (vr_result
.type
== VR_VARYING
)
3375 /* To prevent infinite iterations in the algorithm, derive ranges
3376 when the new value is slightly bigger or smaller than the
3378 if (lhs_vr
->type
== VR_RANGE
)
3380 if (!POINTER_TYPE_P (TREE_TYPE (lhs
)))
3382 int cmp_min
= compare_values (lhs_vr
->min
, vr_result
.min
);
3383 int cmp_max
= compare_values (lhs_vr
->max
, vr_result
.max
);
3385 /* If the new minimum is smaller or larger than the previous
3386 one, go all the way to -INF. In the first case, to avoid
3387 iterating millions of times to reach -INF, and in the
3388 other case to avoid infinite bouncing between different
3390 if (cmp_min
> 0 || cmp_min
< 0)
3391 vr_result
.min
= TYPE_MIN_VALUE (TREE_TYPE (vr_result
.min
));
3393 /* Similarly, if the new maximum is smaller or larger than
3394 the previous one, go all the way to +INF. */
3395 if (cmp_max
< 0 || cmp_max
> 0)
3396 vr_result
.max
= TYPE_MAX_VALUE (TREE_TYPE (vr_result
.max
));
3398 /* If we ended up with a (-INF, +INF) range, set it to
3400 if (vr_result
.min
== TYPE_MIN_VALUE (TREE_TYPE (vr_result
.min
))
3401 && vr_result
.max
== TYPE_MAX_VALUE (TREE_TYPE (vr_result
.max
)))
3406 /* If the new range is different than the previous value, keep
3408 if (update_value_range (lhs
, &vr_result
))
3409 return SSA_PROP_INTERESTING
;
3411 /* Nothing changed, don't add outgoing edges. */
3412 return SSA_PROP_NOT_INTERESTING
;
3414 /* No match found. Set the LHS to VARYING. */
3416 set_value_range_to_varying (lhs_vr
);
3417 return SSA_PROP_VARYING
;
3420 /* Walk through the IL simplifying expressions using knowledge
3424 simplify_using_ranges (void)
3430 block_stmt_iterator bsi
;
3432 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3434 tree stmt
= bsi_stmt (bsi
);
3436 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
3438 tree rhs
= TREE_OPERAND (stmt
, 1);
3439 enum tree_code rhs_code
= TREE_CODE (rhs
);
3441 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
3442 and BIT_AND_EXPR respectively if the first operand is greater
3443 than zero and the second operand is an exact power of two. */
3444 if ((rhs_code
== TRUNC_DIV_EXPR
|| rhs_code
== TRUNC_MOD_EXPR
)
3445 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
3446 && integer_pow2p (TREE_OPERAND (rhs
, 1)))
3449 tree op
= TREE_OPERAND (rhs
, 0);
3450 value_range_t
*vr
= get_value_range (TREE_OPERAND (rhs
, 0));
3452 if (TYPE_UNSIGNED (TREE_TYPE (op
)))
3454 val
= integer_one_node
;
3458 val
= compare_range_with_value (GT_EXPR
, vr
,
3462 if (val
&& integer_onep (val
))
3465 tree op0
= TREE_OPERAND (rhs
, 0);
3466 tree op1
= TREE_OPERAND (rhs
, 1);
3468 if (rhs_code
== TRUNC_DIV_EXPR
)
3470 t
= build_int_cst (NULL_TREE
, tree_log2 (op1
));
3471 t
= build (RSHIFT_EXPR
, TREE_TYPE (op0
), op0
, t
);
3475 t
= build_int_cst (TREE_TYPE (op1
), 1);
3476 t
= int_const_binop (MINUS_EXPR
, op1
, t
, 0);
3477 t
= fold_convert (TREE_TYPE (op0
), t
);
3478 t
= build2 (BIT_AND_EXPR
, TREE_TYPE (op0
), op0
, t
);
3481 TREE_OPERAND (stmt
, 1) = t
;
3487 /* Transform ABS (X) into X or -X as appropriate. */
3488 if (rhs_code
== ABS_EXPR
3489 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
3490 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
3493 tree op
= TREE_OPERAND (rhs
, 0);
3494 tree type
= TREE_TYPE (op
);
3495 value_range_t
*vr
= get_value_range (TREE_OPERAND (rhs
, 0));
3497 if (TYPE_UNSIGNED (type
))
3499 val
= integer_zero_node
;
3503 val
= compare_range_with_value (LE_EXPR
, vr
,
3507 val
= compare_range_with_value (GE_EXPR
, vr
,
3512 if (integer_zerop (val
))
3513 val
= integer_one_node
;
3514 else if (integer_onep (val
))
3515 val
= integer_zero_node
;
3520 && (integer_onep (val
) || integer_zerop (val
)))
3524 if (integer_onep (val
))
3525 t
= build1 (NEGATE_EXPR
, TREE_TYPE (op
), op
);
3529 TREE_OPERAND (stmt
, 1) = t
;
3536 /* TODO. Simplify conditionals. */
3542 /* Traverse all the blocks folding conditionals with known ranges. */
3548 prop_value_t
*single_val_range
;
3549 bool do_value_subst_p
;
3553 fprintf (dump_file
, "\nValue ranges after VRP:\n\n");
3554 dump_all_value_ranges (dump_file
);
3555 fprintf (dump_file
, "\n");
3558 /* We may have ended with ranges that have exactly one value. Those
3559 values can be substituted as any other copy/const propagated
3560 value using substitute_and_fold. */
3561 single_val_range
= xmalloc (num_ssa_names
* sizeof (*single_val_range
));
3562 memset (single_val_range
, 0, num_ssa_names
* sizeof (*single_val_range
));
3564 do_value_subst_p
= false;
3565 for (i
= 0; i
< num_ssa_names
; i
++)
3567 && vr_value
[i
]->type
== VR_RANGE
3568 && vr_value
[i
]->min
== vr_value
[i
]->max
)
3570 single_val_range
[i
].value
= vr_value
[i
]->min
;
3571 do_value_subst_p
= true;
3574 if (!do_value_subst_p
)
3576 /* We found no single-valued ranges, don't waste time trying to
3577 do single value substitution in substitute_and_fold. */
3578 free (single_val_range
);
3579 single_val_range
= NULL
;
3582 substitute_and_fold (single_val_range
, true);
3584 /* One could argue all simplifications should be done here
3585 rather than using substitute_and_fold since this code
3586 is going to have to perform a complete walk through the
3588 simplify_using_ranges ();
3590 /* Free allocated memory. */
3591 for (i
= 0; i
< num_ssa_names
; i
++)
3594 BITMAP_FREE (vr_value
[i
]->equiv
);
3598 free (single_val_range
);
3603 /* Main entry point to VRP (Value Range Propagation). This pass is
3604 loosely based on J. R. C. Patterson, ``Accurate Static Branch
3605 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
3606 Programming Language Design and Implementation, pp. 67-78, 1995.
3607 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
3609 This is essentially an SSA-CCP pass modified to deal with ranges
3610 instead of constants.
3612 While propagating ranges, we may find that two or more SSA name
3613 have equivalent, though distinct ranges. For instance,
3616 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
3618 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
3622 In the code above, pointer p_5 has range [q_2, q_2], but from the
3623 code we can also determine that p_5 cannot be NULL and, if q_2 had
3624 a non-varying range, p_5's range should also be compatible with it.
3626 These equivalences are created by two expressions: ASSERT_EXPR and
3627 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
3628 result of another assertion, then we can use the fact that p_5 and
3629 p_4 are equivalent when evaluating p_5's range.
3631 Together with value ranges, we also propagate these equivalences
3632 between names so that we can take advantage of information from
3633 multiple ranges when doing final replacement. Note that this
3634 equivalency relation is transitive but not symmetric.
3636 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
3637 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
3638 in contexts where that assertion does not hold (e.g., in line 6).
3640 TODO, the main difference between this pass and Patterson's is that
3641 we do not propagate edge probabilities. We only compute whether
3642 edges can be taken or not. That is, instead of having a spectrum
3643 of jump probabilities between 0 and 1, we only deal with 0, 1 and
3644 DON'T KNOW. In the future, it may be worthwhile to propagate
3645 probabilities to aid branch prediction. */
3650 insert_range_assertions ();
3652 cfg_loops
= loop_optimizer_init (NULL
);
3654 scev_initialize (cfg_loops
);
3657 ssa_propagate (vrp_visit_stmt
, vrp_visit_phi_node
);
3663 loop_optimizer_finalize (cfg_loops
, NULL
);
3664 current_loops
= NULL
;
3667 remove_range_assertions ();
3673 return flag_tree_vrp
!= 0;
3676 struct tree_opt_pass pass_vrp
=
3679 gate_vrp
, /* gate */
3680 execute_vrp
, /* execute */
3683 0, /* static_pass_number */
3684 TV_TREE_VRP
, /* tv_id */
3685 PROP_ssa
| PROP_alias
, /* properties_required */
3686 0, /* properties_provided */
3687 0, /* properties_destroyed */
3688 0, /* todo_flags_start */
3693 | TODO_update_ssa
, /* todo_flags_finish */