1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "insn-codes.h"
28 #include "optabs-tree.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
32 #include "fold-const.h"
35 #include "gimple-fold.h"
36 #include "gimple-iterator.h"
38 #include "tree-ssa-loop-niter.h"
39 #include "tree-ssa-loop.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-ssa-propagate.h"
44 #include "tree-chrec.h"
45 #include "omp-general.h"
46 #include "case-cfn-macros.h"
47 #include "alloc-pool.h"
49 #include "vr-values.h"
51 /* Set value range VR to a non-negative range of type TYPE. */
54 set_value_range_to_nonnegative (value_range
*vr
, tree type
)
56 tree zero
= build_int_cst (type
, 0);
57 set_value_range (vr
, VR_RANGE
, zero
, vrp_val_max (type
), vr
->equiv
);
60 /* Set value range VR to a range of a truthvalue of type TYPE. */
63 set_value_range_to_truthvalue (value_range
*vr
, tree type
)
65 if (TYPE_PRECISION (type
) == 1)
66 set_value_range_to_varying (vr
);
68 set_value_range (vr
, VR_RANGE
,
69 build_int_cst (type
, 0), build_int_cst (type
, 1),
74 /* Return value range information for VAR.
76 If we have no values ranges recorded (ie, VRP is not running), then
77 return NULL. Otherwise create an empty range if none existed for VAR. */
80 vr_values::get_value_range (const_tree var
)
82 static const value_range vr_const_varying
83 = { VR_VARYING
, NULL_TREE
, NULL_TREE
, NULL
};
86 unsigned ver
= SSA_NAME_VERSION (var
);
88 /* If we have no recorded ranges, then return NULL. */
92 /* If we query the range for a new SSA name return an unmodifiable VARYING.
93 We should get here at most from the substitute-and-fold stage which
94 will never try to change values. */
95 if (ver
>= num_vr_values
)
96 return CONST_CAST (value_range
*, &vr_const_varying
);
102 /* After propagation finished do not allocate new value-ranges. */
103 if (values_propagated
)
104 return CONST_CAST (value_range
*, &vr_const_varying
);
106 /* Create a default value range. */
107 vr_value
[ver
] = vr
= vrp_value_range_pool
.allocate ();
108 memset (vr
, 0, sizeof (*vr
));
110 /* Defer allocating the equivalence set. */
113 /* If VAR is a default definition of a parameter, the variable can
114 take any value in VAR's type. */
115 if (SSA_NAME_IS_DEFAULT_DEF (var
))
117 sym
= SSA_NAME_VAR (var
);
118 if (TREE_CODE (sym
) == PARM_DECL
)
120 /* Try to use the "nonnull" attribute to create ~[0, 0]
121 anti-ranges for pointers. Note that this is only valid with
122 default definitions of PARM_DECLs. */
123 if (POINTER_TYPE_P (TREE_TYPE (sym
))
124 && (nonnull_arg_p (sym
)
125 || get_ptr_nonnull (var
)))
126 set_value_range_to_nonnull (vr
, TREE_TYPE (sym
));
127 else if (INTEGRAL_TYPE_P (TREE_TYPE (sym
)))
130 value_range_type rtype
= get_range_info (var
, &min
, &max
);
131 if (rtype
== VR_RANGE
|| rtype
== VR_ANTI_RANGE
)
132 set_value_range (vr
, rtype
,
133 wide_int_to_tree (TREE_TYPE (var
), min
),
134 wide_int_to_tree (TREE_TYPE (var
), max
),
137 set_value_range_to_varying (vr
);
140 set_value_range_to_varying (vr
);
142 else if (TREE_CODE (sym
) == RESULT_DECL
143 && DECL_BY_REFERENCE (sym
))
144 set_value_range_to_nonnull (vr
, TREE_TYPE (sym
));
150 /* Set value-ranges of all SSA names defined by STMT to varying. */
153 vr_values::set_defs_to_varying (gimple
*stmt
)
157 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
159 value_range
*vr
= get_value_range (def
);
160 /* Avoid writing to vr_const_varying get_value_range may return. */
161 if (vr
->type
!= VR_VARYING
)
162 set_value_range_to_varying (vr
);
166 /* Update the value range and equivalence set for variable VAR to
167 NEW_VR. Return true if NEW_VR is different from VAR's previous
170 NOTE: This function assumes that NEW_VR is a temporary value range
171 object created for the sole purpose of updating VAR's range. The
172 storage used by the equivalence set from NEW_VR will be freed by
173 this function. Do not call update_value_range when NEW_VR
174 is the range object associated with another SSA name. */
177 vr_values::update_value_range (const_tree var
, value_range
*new_vr
)
182 /* If there is a value-range on the SSA name from earlier analysis
184 if (INTEGRAL_TYPE_P (TREE_TYPE (var
)))
187 value_range_type rtype
= get_range_info (var
, &min
, &max
);
188 if (rtype
== VR_RANGE
|| rtype
== VR_ANTI_RANGE
)
191 nr_min
= wide_int_to_tree (TREE_TYPE (var
), min
);
192 nr_max
= wide_int_to_tree (TREE_TYPE (var
), max
);
193 value_range nr
= VR_INITIALIZER
;
194 set_and_canonicalize_value_range (&nr
, rtype
, nr_min
, nr_max
, NULL
);
195 vrp_intersect_ranges (new_vr
, &nr
);
199 /* Update the value range, if necessary. */
200 old_vr
= get_value_range (var
);
201 is_new
= old_vr
->type
!= new_vr
->type
202 || !vrp_operand_equal_p (old_vr
->min
, new_vr
->min
)
203 || !vrp_operand_equal_p (old_vr
->max
, new_vr
->max
)
204 || !vrp_bitmap_equal_p (old_vr
->equiv
, new_vr
->equiv
);
208 /* Do not allow transitions up the lattice. The following
209 is slightly more awkward than just new_vr->type < old_vr->type
210 because VR_RANGE and VR_ANTI_RANGE need to be considered
211 the same. We may not have is_new when transitioning to
212 UNDEFINED. If old_vr->type is VARYING, we shouldn't be
214 if (new_vr
->type
== VR_UNDEFINED
)
216 BITMAP_FREE (new_vr
->equiv
);
217 set_value_range_to_varying (old_vr
);
218 set_value_range_to_varying (new_vr
);
222 set_value_range (old_vr
, new_vr
->type
, new_vr
->min
, new_vr
->max
,
226 BITMAP_FREE (new_vr
->equiv
);
232 /* Add VAR and VAR's equivalence set to EQUIV. This is the central
233 point where equivalence processing can be turned on/off. */
236 vr_values::add_equivalence (bitmap
*equiv
, const_tree var
)
238 unsigned ver
= SSA_NAME_VERSION (var
);
239 value_range
*vr
= get_value_range (var
);
242 *equiv
= BITMAP_ALLOC (&vrp_equiv_obstack
);
243 bitmap_set_bit (*equiv
, ver
);
245 bitmap_ior_into (*equiv
, vr
->equiv
);
248 /* Return true if value range VR involves exactly one symbol SYM. */
251 symbolic_range_based_on_p (value_range
*vr
, const_tree sym
)
253 bool neg
, min_has_symbol
, max_has_symbol
;
256 if (is_gimple_min_invariant (vr
->min
))
257 min_has_symbol
= false;
258 else if (get_single_symbol (vr
->min
, &neg
, &inv
) == sym
)
259 min_has_symbol
= true;
263 if (is_gimple_min_invariant (vr
->max
))
264 max_has_symbol
= false;
265 else if (get_single_symbol (vr
->max
, &neg
, &inv
) == sym
)
266 max_has_symbol
= true;
270 return (min_has_symbol
|| max_has_symbol
);
273 /* Return true if the result of assignment STMT is know to be non-zero. */
276 gimple_assign_nonzero_p (gimple
*stmt
)
278 enum tree_code code
= gimple_assign_rhs_code (stmt
);
279 bool strict_overflow_p
;
280 switch (get_gimple_rhs_class (code
))
282 case GIMPLE_UNARY_RHS
:
283 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
284 gimple_expr_type (stmt
),
285 gimple_assign_rhs1 (stmt
),
287 case GIMPLE_BINARY_RHS
:
288 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
289 gimple_expr_type (stmt
),
290 gimple_assign_rhs1 (stmt
),
291 gimple_assign_rhs2 (stmt
),
293 case GIMPLE_TERNARY_RHS
:
295 case GIMPLE_SINGLE_RHS
:
296 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt
),
298 case GIMPLE_INVALID_RHS
:
305 /* Return true if STMT is known to compute a non-zero value. */
308 gimple_stmt_nonzero_p (gimple
*stmt
)
310 switch (gimple_code (stmt
))
313 return gimple_assign_nonzero_p (stmt
);
316 tree fndecl
= gimple_call_fndecl (stmt
);
317 if (!fndecl
) return false;
318 if (flag_delete_null_pointer_checks
&& !flag_check_new
319 && DECL_IS_OPERATOR_NEW (fndecl
)
320 && !TREE_NOTHROW (fndecl
))
322 /* References are always non-NULL. */
323 if (flag_delete_null_pointer_checks
324 && TREE_CODE (TREE_TYPE (fndecl
)) == REFERENCE_TYPE
)
326 if (flag_delete_null_pointer_checks
&&
327 lookup_attribute ("returns_nonnull",
328 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
))))
331 gcall
*call_stmt
= as_a
<gcall
*> (stmt
);
332 unsigned rf
= gimple_call_return_flags (call_stmt
);
333 if (rf
& ERF_RETURNS_ARG
)
335 unsigned argnum
= rf
& ERF_RETURN_ARG_MASK
;
336 if (argnum
< gimple_call_num_args (call_stmt
))
338 tree arg
= gimple_call_arg (call_stmt
, argnum
);
340 && infer_nonnull_range_by_attribute (stmt
, arg
))
344 return gimple_alloca_call_p (stmt
);
350 /* Like tree_expr_nonzero_p, but this function uses value ranges
354 vr_values::vrp_stmt_computes_nonzero (gimple
*stmt
)
356 if (gimple_stmt_nonzero_p (stmt
))
359 /* If we have an expression of the form &X->a, then the expression
360 is nonnull if X is nonnull. */
361 if (is_gimple_assign (stmt
)
362 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
364 tree expr
= gimple_assign_rhs1 (stmt
);
365 tree base
= get_base_address (TREE_OPERAND (expr
, 0));
367 if (base
!= NULL_TREE
368 && TREE_CODE (base
) == MEM_REF
369 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
371 value_range
*vr
= get_value_range (TREE_OPERAND (base
, 0));
372 if (range_is_nonnull (vr
))
380 /* Returns true if EXPR is a valid value (as expected by compare_values) --
381 a gimple invariant, or SSA_NAME +- CST. */
384 valid_value_p (tree expr
)
386 if (TREE_CODE (expr
) == SSA_NAME
)
389 if (TREE_CODE (expr
) == PLUS_EXPR
390 || TREE_CODE (expr
) == MINUS_EXPR
)
391 return (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
392 && TREE_CODE (TREE_OPERAND (expr
, 1)) == INTEGER_CST
);
394 return is_gimple_min_invariant (expr
);
397 /* If OP has a value range with a single constant value return that,
398 otherwise return NULL_TREE. This returns OP itself if OP is a
402 vr_values::op_with_constant_singleton_value_range (tree op
)
404 if (is_gimple_min_invariant (op
))
407 if (TREE_CODE (op
) != SSA_NAME
)
410 return value_range_constant_singleton (get_value_range (op
));
413 /* Return true if op is in a boolean [0, 1] value-range. */
416 vr_values::op_with_boolean_value_range_p (tree op
)
420 if (TYPE_PRECISION (TREE_TYPE (op
)) == 1)
423 if (integer_zerop (op
)
424 || integer_onep (op
))
427 if (TREE_CODE (op
) != SSA_NAME
)
430 vr
= get_value_range (op
);
431 return (vr
->type
== VR_RANGE
432 && integer_zerop (vr
->min
)
433 && integer_onep (vr
->max
));
436 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
437 true and store it in *VR_P. */
440 vr_values::extract_range_for_var_from_comparison_expr (tree var
,
441 enum tree_code cond_code
,
446 value_range
*limit_vr
;
447 type
= TREE_TYPE (var
);
448 gcc_assert (limit
!= var
);
450 /* For pointer arithmetic, we only keep track of pointer equality
452 if (POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
454 set_value_range_to_varying (vr_p
);
458 /* If LIMIT is another SSA name and LIMIT has a range of its own,
459 try to use LIMIT's range to avoid creating symbolic ranges
461 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
463 /* LIMIT's range is only interesting if it has any useful information. */
465 || limit_vr
->type
== VR_UNDEFINED
466 || limit_vr
->type
== VR_VARYING
467 || (symbolic_range_p (limit_vr
)
468 && ! (limit_vr
->type
== VR_RANGE
469 && (limit_vr
->min
== limit_vr
->max
470 || operand_equal_p (limit_vr
->min
, limit_vr
->max
, 0)))))
473 /* Initially, the new range has the same set of equivalences of
474 VAR's range. This will be revised before returning the final
475 value. Since assertions may be chained via mutually exclusive
476 predicates, we will need to trim the set of equivalences before
478 gcc_assert (vr_p
->equiv
== NULL
);
479 add_equivalence (&vr_p
->equiv
, var
);
481 /* Extract a new range based on the asserted comparison for VAR and
482 LIMIT's value range. Notice that if LIMIT has an anti-range, we
483 will only use it for equality comparisons (EQ_EXPR). For any
484 other kind of assertion, we cannot derive a range from LIMIT's
485 anti-range that can be used to describe the new range. For
486 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
487 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
488 no single range for x_2 that could describe LE_EXPR, so we might
489 as well build the range [b_4, +INF] for it.
490 One special case we handle is extracting a range from a
491 range test encoded as (unsigned)var + CST <= limit. */
492 if (TREE_CODE (op
) == NOP_EXPR
493 || TREE_CODE (op
) == PLUS_EXPR
)
495 if (TREE_CODE (op
) == PLUS_EXPR
)
497 min
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (TREE_OPERAND (op
, 1)),
498 TREE_OPERAND (op
, 1));
499 max
= int_const_binop (PLUS_EXPR
, limit
, min
);
500 op
= TREE_OPERAND (op
, 0);
504 min
= build_int_cst (TREE_TYPE (var
), 0);
508 /* Make sure to not set TREE_OVERFLOW on the final type
509 conversion. We are willingly interpreting large positive
510 unsigned values as negative signed values here. */
511 min
= force_fit_type (TREE_TYPE (var
), wi::to_widest (min
), 0, false);
512 max
= force_fit_type (TREE_TYPE (var
), wi::to_widest (max
), 0, false);
514 /* We can transform a max, min range to an anti-range or
515 vice-versa. Use set_and_canonicalize_value_range which does
517 if (cond_code
== LE_EXPR
)
518 set_and_canonicalize_value_range (vr_p
, VR_RANGE
,
519 min
, max
, vr_p
->equiv
);
520 else if (cond_code
== GT_EXPR
)
521 set_and_canonicalize_value_range (vr_p
, VR_ANTI_RANGE
,
522 min
, max
, vr_p
->equiv
);
526 else if (cond_code
== EQ_EXPR
)
528 enum value_range_type range_type
;
532 range_type
= limit_vr
->type
;
538 range_type
= VR_RANGE
;
543 set_value_range (vr_p
, range_type
, min
, max
, vr_p
->equiv
);
545 /* When asserting the equality VAR == LIMIT and LIMIT is another
546 SSA name, the new range will also inherit the equivalence set
548 if (TREE_CODE (limit
) == SSA_NAME
)
549 add_equivalence (&vr_p
->equiv
, limit
);
551 else if (cond_code
== NE_EXPR
)
553 /* As described above, when LIMIT's range is an anti-range and
554 this assertion is an inequality (NE_EXPR), then we cannot
555 derive anything from the anti-range. For instance, if
556 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
557 not imply that VAR's range is [0, 0]. So, in the case of
558 anti-ranges, we just assert the inequality using LIMIT and
561 If LIMIT_VR is a range, we can only use it to build a new
562 anti-range if LIMIT_VR is a single-valued range. For
563 instance, if LIMIT_VR is [0, 1], the predicate
564 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
565 Rather, it means that for value 0 VAR should be ~[0, 0]
566 and for value 1, VAR should be ~[1, 1]. We cannot
567 represent these ranges.
569 The only situation in which we can build a valid
570 anti-range is when LIMIT_VR is a single-valued range
571 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
572 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
574 && limit_vr
->type
== VR_RANGE
575 && compare_values (limit_vr
->min
, limit_vr
->max
) == 0)
582 /* In any other case, we cannot use LIMIT's range to build a
587 /* If MIN and MAX cover the whole range for their type, then
588 just use the original LIMIT. */
589 if (INTEGRAL_TYPE_P (type
)
590 && vrp_val_is_min (min
)
591 && vrp_val_is_max (max
))
594 set_and_canonicalize_value_range (vr_p
, VR_ANTI_RANGE
,
595 min
, max
, vr_p
->equiv
);
597 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
599 min
= TYPE_MIN_VALUE (type
);
601 if (limit_vr
== NULL
|| limit_vr
->type
== VR_ANTI_RANGE
)
605 /* If LIMIT_VR is of the form [N1, N2], we need to build the
606 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
611 /* If the maximum value forces us to be out of bounds, simply punt.
612 It would be pointless to try and do anything more since this
613 all should be optimized away above us. */
614 if (cond_code
== LT_EXPR
615 && compare_values (max
, min
) == 0)
616 set_value_range_to_varying (vr_p
);
619 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
620 if (cond_code
== LT_EXPR
)
622 if (TYPE_PRECISION (TREE_TYPE (max
)) == 1
623 && !TYPE_UNSIGNED (TREE_TYPE (max
)))
624 max
= fold_build2 (PLUS_EXPR
, TREE_TYPE (max
), max
,
625 build_int_cst (TREE_TYPE (max
), -1));
627 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max
), max
,
628 build_int_cst (TREE_TYPE (max
), 1));
629 /* Signal to compare_values_warnv this expr doesn't overflow. */
631 TREE_NO_WARNING (max
) = 1;
634 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
637 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
639 max
= TYPE_MAX_VALUE (type
);
641 if (limit_vr
== NULL
|| limit_vr
->type
== VR_ANTI_RANGE
)
645 /* If LIMIT_VR is of the form [N1, N2], we need to build the
646 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
651 /* If the minimum value forces us to be out of bounds, simply punt.
652 It would be pointless to try and do anything more since this
653 all should be optimized away above us. */
654 if (cond_code
== GT_EXPR
655 && compare_values (min
, max
) == 0)
656 set_value_range_to_varying (vr_p
);
659 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
660 if (cond_code
== GT_EXPR
)
662 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
663 && !TYPE_UNSIGNED (TREE_TYPE (min
)))
664 min
= fold_build2 (MINUS_EXPR
, TREE_TYPE (min
), min
,
665 build_int_cst (TREE_TYPE (min
), -1));
667 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min
), min
,
668 build_int_cst (TREE_TYPE (min
), 1));
669 /* Signal to compare_values_warnv this expr doesn't overflow. */
671 TREE_NO_WARNING (min
) = 1;
674 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
680 /* Finally intersect the new range with what we already know about var. */
681 vrp_intersect_ranges (vr_p
, get_value_range (var
));
684 /* Extract value range information from an ASSERT_EXPR EXPR and store
688 vr_values::extract_range_from_assert (value_range
*vr_p
, tree expr
)
690 tree var
= ASSERT_EXPR_VAR (expr
);
691 tree cond
= ASSERT_EXPR_COND (expr
);
693 enum tree_code cond_code
;
694 gcc_assert (COMPARISON_CLASS_P (cond
));
696 /* Find VAR in the ASSERT_EXPR conditional. */
697 if (var
== TREE_OPERAND (cond
, 0)
698 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PLUS_EXPR
699 || TREE_CODE (TREE_OPERAND (cond
, 0)) == NOP_EXPR
)
701 /* If the predicate is of the form VAR COMP LIMIT, then we just
702 take LIMIT from the RHS and use the same comparison code. */
703 cond_code
= TREE_CODE (cond
);
704 limit
= TREE_OPERAND (cond
, 1);
705 op
= TREE_OPERAND (cond
, 0);
709 /* If the predicate is of the form LIMIT COMP VAR, then we need
710 to flip around the comparison code to create the proper range
712 cond_code
= swap_tree_comparison (TREE_CODE (cond
));
713 limit
= TREE_OPERAND (cond
, 0);
714 op
= TREE_OPERAND (cond
, 1);
716 extract_range_for_var_from_comparison_expr (var
, cond_code
, op
,
720 /* Extract range information from SSA name VAR and store it in VR. If
721 VAR has an interesting range, use it. Otherwise, create the
722 range [VAR, VAR] and return it. This is useful in situations where
723 we may have conditionals testing values of VARYING names. For
730 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
734 vr_values::extract_range_from_ssa_name (value_range
*vr
, tree var
)
736 value_range
*var_vr
= get_value_range (var
);
738 if (var_vr
->type
!= VR_VARYING
)
739 copy_value_range (vr
, var_vr
);
741 set_value_range (vr
, VR_RANGE
, var
, var
, NULL
);
743 add_equivalence (&vr
->equiv
, var
);
746 /* Extract range information from a binary expression OP0 CODE OP1 based on
747 the ranges of each of its operands with resulting type EXPR_TYPE.
748 The resulting range is stored in *VR. */
751 vr_values::extract_range_from_binary_expr (value_range
*vr
,
753 tree expr_type
, tree op0
, tree op1
)
755 value_range vr0
= VR_INITIALIZER
;
756 value_range vr1
= VR_INITIALIZER
;
758 /* Get value ranges for each operand. For constant operands, create
759 a new value range with the operand to simplify processing. */
760 if (TREE_CODE (op0
) == SSA_NAME
)
761 vr0
= *(get_value_range (op0
));
762 else if (is_gimple_min_invariant (op0
))
763 set_value_range_to_value (&vr0
, op0
, NULL
);
765 set_value_range_to_varying (&vr0
);
767 if (TREE_CODE (op1
) == SSA_NAME
)
768 vr1
= *(get_value_range (op1
));
769 else if (is_gimple_min_invariant (op1
))
770 set_value_range_to_value (&vr1
, op1
, NULL
);
772 set_value_range_to_varying (&vr1
);
774 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &vr0
, &vr1
);
776 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
777 and based on the other operand, for example if it was deduced from a
778 symbolic comparison. When a bound of the range of the first operand
779 is invariant, we set the corresponding bound of the new range to INF
780 in order to avoid recursing on the range of the second operand. */
781 if (vr
->type
== VR_VARYING
782 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
783 && TREE_CODE (op1
) == SSA_NAME
784 && vr0
.type
== VR_RANGE
785 && symbolic_range_based_on_p (&vr0
, op1
))
787 const bool minus_p
= (code
== MINUS_EXPR
);
788 value_range n_vr1
= VR_INITIALIZER
;
790 /* Try with VR0 and [-INF, OP1]. */
791 if (is_gimple_min_invariant (minus_p
? vr0
.max
: vr0
.min
))
792 set_value_range (&n_vr1
, VR_RANGE
, vrp_val_min (expr_type
), op1
, NULL
);
794 /* Try with VR0 and [OP1, +INF]. */
795 else if (is_gimple_min_invariant (minus_p
? vr0
.min
: vr0
.max
))
796 set_value_range (&n_vr1
, VR_RANGE
, op1
, vrp_val_max (expr_type
), NULL
);
798 /* Try with VR0 and [OP1, OP1]. */
800 set_value_range (&n_vr1
, VR_RANGE
, op1
, op1
, NULL
);
802 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &vr0
, &n_vr1
);
805 if (vr
->type
== VR_VARYING
806 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
807 && TREE_CODE (op0
) == SSA_NAME
808 && vr1
.type
== VR_RANGE
809 && symbolic_range_based_on_p (&vr1
, op0
))
811 const bool minus_p
= (code
== MINUS_EXPR
);
812 value_range n_vr0
= VR_INITIALIZER
;
814 /* Try with [-INF, OP0] and VR1. */
815 if (is_gimple_min_invariant (minus_p
? vr1
.max
: vr1
.min
))
816 set_value_range (&n_vr0
, VR_RANGE
, vrp_val_min (expr_type
), op0
, NULL
);
818 /* Try with [OP0, +INF] and VR1. */
819 else if (is_gimple_min_invariant (minus_p
? vr1
.min
: vr1
.max
))
820 set_value_range (&n_vr0
, VR_RANGE
, op0
, vrp_val_max (expr_type
), NULL
);
822 /* Try with [OP0, OP0] and VR1. */
824 set_value_range (&n_vr0
, VR_RANGE
, op0
, op0
, NULL
);
826 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &n_vr0
, &vr1
);
829 /* If we didn't derive a range for MINUS_EXPR, and
830 op1's range is ~[op0,op0] or vice-versa, then we
831 can derive a non-null range. This happens often for
832 pointer subtraction. */
833 if (vr
->type
== VR_VARYING
834 && code
== MINUS_EXPR
835 && TREE_CODE (op0
) == SSA_NAME
836 && ((vr0
.type
== VR_ANTI_RANGE
838 && vr0
.min
== vr0
.max
)
839 || (vr1
.type
== VR_ANTI_RANGE
841 && vr1
.min
== vr1
.max
)))
842 set_value_range_to_nonnull (vr
, TREE_TYPE (op0
));
845 /* Extract range information from a unary expression CODE OP0 based on
846 the range of its operand with resulting type TYPE.
847 The resulting range is stored in *VR. */
850 vr_values::extract_range_from_unary_expr (value_range
*vr
, enum tree_code code
,
853 value_range vr0
= VR_INITIALIZER
;
855 /* Get value ranges for the operand. For constant operands, create
856 a new value range with the operand to simplify processing. */
857 if (TREE_CODE (op0
) == SSA_NAME
)
858 vr0
= *(get_value_range (op0
));
859 else if (is_gimple_min_invariant (op0
))
860 set_value_range_to_value (&vr0
, op0
, NULL
);
862 set_value_range_to_varying (&vr0
);
864 ::extract_range_from_unary_expr (vr
, code
, type
, &vr0
, TREE_TYPE (op0
));
868 /* Extract range information from a conditional expression STMT based on
869 the ranges of each of its operands and the expression code. */
872 vr_values::extract_range_from_cond_expr (value_range
*vr
, gassign
*stmt
)
875 value_range vr0
= VR_INITIALIZER
;
876 value_range vr1
= VR_INITIALIZER
;
878 /* Get value ranges for each operand. For constant operands, create
879 a new value range with the operand to simplify processing. */
880 op0
= gimple_assign_rhs2 (stmt
);
881 if (TREE_CODE (op0
) == SSA_NAME
)
882 vr0
= *(get_value_range (op0
));
883 else if (is_gimple_min_invariant (op0
))
884 set_value_range_to_value (&vr0
, op0
, NULL
);
886 set_value_range_to_varying (&vr0
);
888 op1
= gimple_assign_rhs3 (stmt
);
889 if (TREE_CODE (op1
) == SSA_NAME
)
890 vr1
= *(get_value_range (op1
));
891 else if (is_gimple_min_invariant (op1
))
892 set_value_range_to_value (&vr1
, op1
, NULL
);
894 set_value_range_to_varying (&vr1
);
896 /* The resulting value range is the union of the operand ranges */
897 copy_value_range (vr
, &vr0
);
902 /* Extract range information from a comparison expression EXPR based
903 on the range of its operand and the expression code. */
906 vr_values::extract_range_from_comparison (value_range
*vr
, enum tree_code code
,
907 tree type
, tree op0
, tree op1
)
912 val
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, false, &sop
,
916 /* Since this expression was found on the RHS of an assignment,
917 its type may be different from _Bool. Convert VAL to EXPR's
919 val
= fold_convert (type
, val
);
920 if (is_gimple_min_invariant (val
))
921 set_value_range_to_value (vr
, val
, vr
->equiv
);
923 set_value_range (vr
, VR_RANGE
, val
, val
, vr
->equiv
);
926 /* The result of a comparison is always true or false. */
927 set_value_range_to_truthvalue (vr
, type
);
930 /* Helper function for simplify_internal_call_using_ranges and
931 extract_range_basic. Return true if OP0 SUBCODE OP1 for
932 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
933 always overflow. Set *OVF to true if it is known to always
937 vr_values::check_for_binary_op_overflow (enum tree_code subcode
, tree type
,
938 tree op0
, tree op1
, bool *ovf
)
940 value_range vr0
= VR_INITIALIZER
;
941 value_range vr1
= VR_INITIALIZER
;
942 if (TREE_CODE (op0
) == SSA_NAME
)
943 vr0
= *get_value_range (op0
);
944 else if (TREE_CODE (op0
) == INTEGER_CST
)
945 set_value_range_to_value (&vr0
, op0
, NULL
);
947 set_value_range_to_varying (&vr0
);
949 if (TREE_CODE (op1
) == SSA_NAME
)
950 vr1
= *get_value_range (op1
);
951 else if (TREE_CODE (op1
) == INTEGER_CST
)
952 set_value_range_to_value (&vr1
, op1
, NULL
);
954 set_value_range_to_varying (&vr1
);
956 if (!range_int_cst_p (&vr0
)
957 || TREE_OVERFLOW (vr0
.min
)
958 || TREE_OVERFLOW (vr0
.max
))
960 vr0
.min
= vrp_val_min (TREE_TYPE (op0
));
961 vr0
.max
= vrp_val_max (TREE_TYPE (op0
));
963 if (!range_int_cst_p (&vr1
)
964 || TREE_OVERFLOW (vr1
.min
)
965 || TREE_OVERFLOW (vr1
.max
))
967 vr1
.min
= vrp_val_min (TREE_TYPE (op1
));
968 vr1
.max
= vrp_val_max (TREE_TYPE (op1
));
970 *ovf
= arith_overflowed_p (subcode
, type
, vr0
.min
,
971 subcode
== MINUS_EXPR
? vr1
.max
: vr1
.min
);
972 if (arith_overflowed_p (subcode
, type
, vr0
.max
,
973 subcode
== MINUS_EXPR
? vr1
.min
: vr1
.max
) != *ovf
)
975 if (subcode
== MULT_EXPR
)
977 if (arith_overflowed_p (subcode
, type
, vr0
.min
, vr1
.max
) != *ovf
978 || arith_overflowed_p (subcode
, type
, vr0
.max
, vr1
.min
) != *ovf
)
983 /* So far we found that there is an overflow on the boundaries.
984 That doesn't prove that there is an overflow even for all values
985 in between the boundaries. For that compute widest_int range
986 of the result and see if it doesn't overlap the range of
988 widest_int wmin
, wmax
;
991 w
[0] = wi::to_widest (vr0
.min
);
992 w
[1] = wi::to_widest (vr0
.max
);
993 w
[2] = wi::to_widest (vr1
.min
);
994 w
[3] = wi::to_widest (vr1
.max
);
995 for (i
= 0; i
< 4; i
++)
1001 wt
= wi::add (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1004 wt
= wi::sub (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1007 wt
= wi::mul (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1019 wmin
= wi::smin (wmin
, wt
);
1020 wmax
= wi::smax (wmax
, wt
);
1023 /* The result of op0 CODE op1 is known to be in range
1025 widest_int wtmin
= wi::to_widest (vrp_val_min (type
));
1026 widest_int wtmax
= wi::to_widest (vrp_val_max (type
));
1027 /* If all values in [wmin, wmax] are smaller than
1028 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1029 the arithmetic operation will always overflow. */
1030 if (wmax
< wtmin
|| wmin
> wtmax
)
1037 /* Try to derive a nonnegative or nonzero range out of STMT relying
1038 primarily on generic routines in fold in conjunction with range data.
1039 Store the result in *VR */
1042 vr_values::extract_range_basic (value_range
*vr
, gimple
*stmt
)
1045 tree type
= gimple_expr_type (stmt
);
1047 if (is_gimple_call (stmt
))
1050 int mini
, maxi
, zerov
= 0, prec
;
1051 enum tree_code subcode
= ERROR_MARK
;
1052 combined_fn cfn
= gimple_call_combined_fn (stmt
);
1053 scalar_int_mode mode
;
1057 case CFN_BUILT_IN_CONSTANT_P
:
1058 /* If the call is __builtin_constant_p and the argument is a
1059 function parameter resolve it to false. This avoids bogus
1060 array bound warnings.
1061 ??? We could do this as early as inlining is finished. */
1062 arg
= gimple_call_arg (stmt
, 0);
1063 if (TREE_CODE (arg
) == SSA_NAME
1064 && SSA_NAME_IS_DEFAULT_DEF (arg
)
1065 && TREE_CODE (SSA_NAME_VAR (arg
)) == PARM_DECL
1066 && cfun
->after_inlining
)
1068 set_value_range_to_null (vr
, type
);
1072 /* Both __builtin_ffs* and __builtin_popcount return
1076 arg
= gimple_call_arg (stmt
, 0);
1077 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1080 if (TREE_CODE (arg
) == SSA_NAME
)
1082 value_range
*vr0
= get_value_range (arg
);
1083 /* If arg is non-zero, then ffs or popcount
1085 if ((vr0
->type
== VR_RANGE
1086 && range_includes_zero_p (vr0
->min
, vr0
->max
) == 0)
1087 || (vr0
->type
== VR_ANTI_RANGE
1088 && range_includes_zero_p (vr0
->min
, vr0
->max
) == 1))
1090 /* If some high bits are known to be zero,
1091 we can decrease the maximum. */
1092 if (vr0
->type
== VR_RANGE
1093 && TREE_CODE (vr0
->max
) == INTEGER_CST
1094 && !operand_less_p (vr0
->min
,
1095 build_zero_cst (TREE_TYPE (vr0
->min
))))
1096 maxi
= tree_floor_log2 (vr0
->max
) + 1;
1099 /* __builtin_parity* returns [0, 1]. */
1104 /* __builtin_c[lt]z* return [0, prec-1], except for
1105 when the argument is 0, but that is undefined behavior.
1106 On many targets where the CLZ RTL or optab value is defined
1107 for 0 the value is prec, so include that in the range
1110 arg
= gimple_call_arg (stmt
, 0);
1111 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1114 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1115 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
1116 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
)
1117 /* Handle only the single common value. */
1119 /* Magic value to give up, unless vr0 proves
1122 if (TREE_CODE (arg
) == SSA_NAME
)
1124 value_range
*vr0
= get_value_range (arg
);
1125 /* From clz of VR_RANGE minimum we can compute
1127 if (vr0
->type
== VR_RANGE
1128 && TREE_CODE (vr0
->min
) == INTEGER_CST
)
1130 maxi
= prec
- 1 - tree_floor_log2 (vr0
->min
);
1134 else if (vr0
->type
== VR_ANTI_RANGE
1135 && integer_zerop (vr0
->min
))
1142 /* From clz of VR_RANGE maximum we can compute
1144 if (vr0
->type
== VR_RANGE
1145 && TREE_CODE (vr0
->max
) == INTEGER_CST
)
1147 mini
= prec
- 1 - tree_floor_log2 (vr0
->max
);
1155 /* __builtin_ctz* return [0, prec-1], except for
1156 when the argument is 0, but that is undefined behavior.
1157 If there is a ctz optab for this mode and
1158 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1159 otherwise just assume 0 won't be seen. */
1161 arg
= gimple_call_arg (stmt
, 0);
1162 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1165 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1166 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1167 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
))
1169 /* Handle only the two common values. */
1172 else if (zerov
== prec
)
1175 /* Magic value to give up, unless vr0 proves
1179 if (TREE_CODE (arg
) == SSA_NAME
)
1181 value_range
*vr0
= get_value_range (arg
);
1182 /* If arg is non-zero, then use [0, prec - 1]. */
1183 if ((vr0
->type
== VR_RANGE
1184 && integer_nonzerop (vr0
->min
))
1185 || (vr0
->type
== VR_ANTI_RANGE
1186 && integer_zerop (vr0
->min
)))
1191 /* If some high bits are known to be zero,
1192 we can decrease the result maximum. */
1193 if (vr0
->type
== VR_RANGE
1194 && TREE_CODE (vr0
->max
) == INTEGER_CST
)
1196 maxi
= tree_floor_log2 (vr0
->max
);
1197 /* For vr0 [0, 0] give up. */
1205 /* __builtin_clrsb* returns [0, prec-1]. */
1207 arg
= gimple_call_arg (stmt
, 0);
1208 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1213 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, mini
),
1214 build_int_cst (type
, maxi
), NULL
);
1216 case CFN_UBSAN_CHECK_ADD
:
1217 subcode
= PLUS_EXPR
;
1219 case CFN_UBSAN_CHECK_SUB
:
1220 subcode
= MINUS_EXPR
;
1222 case CFN_UBSAN_CHECK_MUL
:
1223 subcode
= MULT_EXPR
;
1225 case CFN_GOACC_DIM_SIZE
:
1226 case CFN_GOACC_DIM_POS
:
1227 /* Optimizing these two internal functions helps the loop
1228 optimizer eliminate outer comparisons. Size is [1,N]
1229 and pos is [0,N-1]. */
1231 bool is_pos
= cfn
== CFN_GOACC_DIM_POS
;
1232 int axis
= oacc_get_ifn_dim_arg (stmt
);
1233 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1236 /* If it's dynamic, the backend might know a hardware
1238 size
= targetm
.goacc
.dim_limit (axis
);
1240 tree type
= TREE_TYPE (gimple_call_lhs (stmt
));
1241 set_value_range (vr
, VR_RANGE
,
1242 build_int_cst (type
, is_pos
? 0 : 1),
1243 size
? build_int_cst (type
, size
- is_pos
)
1244 : vrp_val_max (type
), NULL
);
1247 case CFN_BUILT_IN_STRLEN
:
1248 if (tree lhs
= gimple_call_lhs (stmt
))
1249 if (ptrdiff_type_node
1250 && (TYPE_PRECISION (ptrdiff_type_node
)
1251 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1253 tree type
= TREE_TYPE (lhs
);
1254 tree max
= vrp_val_max (ptrdiff_type_node
);
1255 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1256 tree range_min
= build_zero_cst (type
);
1257 tree range_max
= wide_int_to_tree (type
, wmax
- 1);
1258 set_value_range (vr
, VR_RANGE
, range_min
, range_max
, NULL
);
1265 if (subcode
!= ERROR_MARK
)
1267 bool saved_flag_wrapv
= flag_wrapv
;
1268 /* Pretend the arithmetics is wrapping. If there is
1269 any overflow, we'll complain, but will actually do
1270 wrapping operation. */
1272 extract_range_from_binary_expr (vr
, subcode
, type
,
1273 gimple_call_arg (stmt
, 0),
1274 gimple_call_arg (stmt
, 1));
1275 flag_wrapv
= saved_flag_wrapv
;
1277 /* If for both arguments vrp_valueize returned non-NULL,
1278 this should have been already folded and if not, it
1279 wasn't folded because of overflow. Avoid removing the
1280 UBSAN_CHECK_* calls in that case. */
1281 if (vr
->type
== VR_RANGE
1282 && (vr
->min
== vr
->max
1283 || operand_equal_p (vr
->min
, vr
->max
, 0)))
1284 set_value_range_to_varying (vr
);
1288 /* Handle extraction of the two results (result of arithmetics and
1289 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1290 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1291 else if (is_gimple_assign (stmt
)
1292 && (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
1293 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
)
1294 && INTEGRAL_TYPE_P (type
))
1296 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1297 tree op
= gimple_assign_rhs1 (stmt
);
1298 if (TREE_CODE (op
) == code
&& TREE_CODE (TREE_OPERAND (op
, 0)) == SSA_NAME
)
1300 gimple
*g
= SSA_NAME_DEF_STMT (TREE_OPERAND (op
, 0));
1301 if (is_gimple_call (g
) && gimple_call_internal_p (g
))
1303 enum tree_code subcode
= ERROR_MARK
;
1304 switch (gimple_call_internal_fn (g
))
1306 case IFN_ADD_OVERFLOW
:
1307 subcode
= PLUS_EXPR
;
1309 case IFN_SUB_OVERFLOW
:
1310 subcode
= MINUS_EXPR
;
1312 case IFN_MUL_OVERFLOW
:
1313 subcode
= MULT_EXPR
;
1315 case IFN_ATOMIC_COMPARE_EXCHANGE
:
1316 if (code
== IMAGPART_EXPR
)
1318 /* This is the boolean return value whether compare and
1319 exchange changed anything or not. */
1320 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, 0),
1321 build_int_cst (type
, 1), NULL
);
1328 if (subcode
!= ERROR_MARK
)
1330 tree op0
= gimple_call_arg (g
, 0);
1331 tree op1
= gimple_call_arg (g
, 1);
1332 if (code
== IMAGPART_EXPR
)
1335 if (check_for_binary_op_overflow (subcode
, type
,
1337 set_value_range_to_value (vr
,
1338 build_int_cst (type
, ovf
),
1340 else if (TYPE_PRECISION (type
) == 1
1341 && !TYPE_UNSIGNED (type
))
1342 set_value_range_to_varying (vr
);
1344 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, 0),
1345 build_int_cst (type
, 1), NULL
);
1347 else if (types_compatible_p (type
, TREE_TYPE (op0
))
1348 && types_compatible_p (type
, TREE_TYPE (op1
)))
1350 bool saved_flag_wrapv
= flag_wrapv
;
1351 /* Pretend the arithmetics is wrapping. If there is
1352 any overflow, IMAGPART_EXPR will be set. */
1354 extract_range_from_binary_expr (vr
, subcode
, type
,
1356 flag_wrapv
= saved_flag_wrapv
;
1360 value_range vr0
= VR_INITIALIZER
;
1361 value_range vr1
= VR_INITIALIZER
;
1362 bool saved_flag_wrapv
= flag_wrapv
;
1363 /* Pretend the arithmetics is wrapping. If there is
1364 any overflow, IMAGPART_EXPR will be set. */
1366 extract_range_from_unary_expr (&vr0
, NOP_EXPR
,
1368 extract_range_from_unary_expr (&vr1
, NOP_EXPR
,
1370 extract_range_from_binary_expr_1 (vr
, subcode
, type
,
1372 flag_wrapv
= saved_flag_wrapv
;
1379 if (INTEGRAL_TYPE_P (type
)
1380 && gimple_stmt_nonnegative_warnv_p (stmt
, &sop
))
1381 set_value_range_to_nonnegative (vr
, type
);
1382 else if (vrp_stmt_computes_nonzero (stmt
))
1383 set_value_range_to_nonnull (vr
, type
);
1385 set_value_range_to_varying (vr
);
1389 /* Try to compute a useful range out of assignment STMT and store it
1393 vr_values::extract_range_from_assignment (value_range
*vr
, gassign
*stmt
)
1395 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1397 if (code
== ASSERT_EXPR
)
1398 extract_range_from_assert (vr
, gimple_assign_rhs1 (stmt
));
1399 else if (code
== SSA_NAME
)
1400 extract_range_from_ssa_name (vr
, gimple_assign_rhs1 (stmt
));
1401 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
1402 extract_range_from_binary_expr (vr
, gimple_assign_rhs_code (stmt
),
1403 gimple_expr_type (stmt
),
1404 gimple_assign_rhs1 (stmt
),
1405 gimple_assign_rhs2 (stmt
));
1406 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1407 extract_range_from_unary_expr (vr
, gimple_assign_rhs_code (stmt
),
1408 gimple_expr_type (stmt
),
1409 gimple_assign_rhs1 (stmt
));
1410 else if (code
== COND_EXPR
)
1411 extract_range_from_cond_expr (vr
, stmt
);
1412 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1413 extract_range_from_comparison (vr
, gimple_assign_rhs_code (stmt
),
1414 gimple_expr_type (stmt
),
1415 gimple_assign_rhs1 (stmt
),
1416 gimple_assign_rhs2 (stmt
));
1417 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1418 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1419 set_value_range_to_value (vr
, gimple_assign_rhs1 (stmt
), NULL
);
1421 set_value_range_to_varying (vr
);
1423 if (vr
->type
== VR_VARYING
)
1424 extract_range_basic (vr
, stmt
);
1427 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1429 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1430 all the values in the ranges.
1432 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1434 - Return NULL_TREE if it is not always possible to determine the
1435 value of the comparison.
1437 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1438 assumed signed overflow is undefined. */
1442 compare_ranges (enum tree_code comp
, value_range
*vr0
, value_range
*vr1
,
1443 bool *strict_overflow_p
)
1445 /* VARYING or UNDEFINED ranges cannot be compared. */
1446 if (vr0
->type
== VR_VARYING
1447 || vr0
->type
== VR_UNDEFINED
1448 || vr1
->type
== VR_VARYING
1449 || vr1
->type
== VR_UNDEFINED
)
1452 /* Anti-ranges need to be handled separately. */
1453 if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
1455 /* If both are anti-ranges, then we cannot compute any
1457 if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
1460 /* These comparisons are never statically computable. */
1467 /* Equality can be computed only between a range and an
1468 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1469 if (vr0
->type
== VR_RANGE
)
1471 /* To simplify processing, make VR0 the anti-range. */
1472 value_range
*tmp
= vr0
;
1477 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1479 if (compare_values_warnv (vr0
->min
, vr1
->min
, strict_overflow_p
) == 0
1480 && compare_values_warnv (vr0
->max
, vr1
->max
, strict_overflow_p
) == 0)
1481 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1486 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1487 operands around and change the comparison code. */
1488 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1490 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1491 std::swap (vr0
, vr1
);
1494 if (comp
== EQ_EXPR
)
1496 /* Equality may only be computed if both ranges represent
1497 exactly one value. */
1498 if (compare_values_warnv (vr0
->min
, vr0
->max
, strict_overflow_p
) == 0
1499 && compare_values_warnv (vr1
->min
, vr1
->max
, strict_overflow_p
) == 0)
1501 int cmp_min
= compare_values_warnv (vr0
->min
, vr1
->min
,
1503 int cmp_max
= compare_values_warnv (vr0
->max
, vr1
->max
,
1505 if (cmp_min
== 0 && cmp_max
== 0)
1506 return boolean_true_node
;
1507 else if (cmp_min
!= -2 && cmp_max
!= -2)
1508 return boolean_false_node
;
1510 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1511 else if (compare_values_warnv (vr0
->min
, vr1
->max
,
1512 strict_overflow_p
) == 1
1513 || compare_values_warnv (vr1
->min
, vr0
->max
,
1514 strict_overflow_p
) == 1)
1515 return boolean_false_node
;
1519 else if (comp
== NE_EXPR
)
1523 /* If VR0 is completely to the left or completely to the right
1524 of VR1, they are always different. Notice that we need to
1525 make sure that both comparisons yield similar results to
1526 avoid comparing values that cannot be compared at
1528 cmp1
= compare_values_warnv (vr0
->max
, vr1
->min
, strict_overflow_p
);
1529 cmp2
= compare_values_warnv (vr0
->min
, vr1
->max
, strict_overflow_p
);
1530 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1531 return boolean_true_node
;
1533 /* If VR0 and VR1 represent a single value and are identical,
1535 else if (compare_values_warnv (vr0
->min
, vr0
->max
,
1536 strict_overflow_p
) == 0
1537 && compare_values_warnv (vr1
->min
, vr1
->max
,
1538 strict_overflow_p
) == 0
1539 && compare_values_warnv (vr0
->min
, vr1
->min
,
1540 strict_overflow_p
) == 0
1541 && compare_values_warnv (vr0
->max
, vr1
->max
,
1542 strict_overflow_p
) == 0)
1543 return boolean_false_node
;
1545 /* Otherwise, they may or may not be different. */
1549 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1553 /* If VR0 is to the left of VR1, return true. */
1554 tst
= compare_values_warnv (vr0
->max
, vr1
->min
, strict_overflow_p
);
1555 if ((comp
== LT_EXPR
&& tst
== -1)
1556 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1557 return boolean_true_node
;
1559 /* If VR0 is to the right of VR1, return false. */
1560 tst
= compare_values_warnv (vr0
->min
, vr1
->max
, strict_overflow_p
);
1561 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1562 || (comp
== LE_EXPR
&& tst
== 1))
1563 return boolean_false_node
;
1565 /* Otherwise, we don't know. */
1572 /* Given a value range VR, a value VAL and a comparison code COMP, return
1573 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1574 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1575 always returns false. Return NULL_TREE if it is not always
1576 possible to determine the value of the comparison. Also set
1577 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1578 assumed signed overflow is undefined. */
1581 compare_range_with_value (enum tree_code comp
, value_range
*vr
, tree val
,
1582 bool *strict_overflow_p
)
1584 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
1587 /* Anti-ranges need to be handled separately. */
1588 if (vr
->type
== VR_ANTI_RANGE
)
1590 /* For anti-ranges, the only predicates that we can compute at
1591 compile time are equality and inequality. */
1598 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1599 if (value_inside_range (val
, vr
->min
, vr
->max
) == 1)
1600 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1605 if (comp
== EQ_EXPR
)
1607 /* EQ_EXPR may only be computed if VR represents exactly
1609 if (compare_values_warnv (vr
->min
, vr
->max
, strict_overflow_p
) == 0)
1611 int cmp
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
1613 return boolean_true_node
;
1614 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1615 return boolean_false_node
;
1617 else if (compare_values_warnv (val
, vr
->min
, strict_overflow_p
) == -1
1618 || compare_values_warnv (vr
->max
, val
, strict_overflow_p
) == -1)
1619 return boolean_false_node
;
1623 else if (comp
== NE_EXPR
)
1625 /* If VAL is not inside VR, then they are always different. */
1626 if (compare_values_warnv (vr
->max
, val
, strict_overflow_p
) == -1
1627 || compare_values_warnv (vr
->min
, val
, strict_overflow_p
) == 1)
1628 return boolean_true_node
;
1630 /* If VR represents exactly one value equal to VAL, then return
1632 if (compare_values_warnv (vr
->min
, vr
->max
, strict_overflow_p
) == 0
1633 && compare_values_warnv (vr
->min
, val
, strict_overflow_p
) == 0)
1634 return boolean_false_node
;
1636 /* Otherwise, they may or may not be different. */
1639 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1643 /* If VR is to the left of VAL, return true. */
1644 tst
= compare_values_warnv (vr
->max
, val
, strict_overflow_p
);
1645 if ((comp
== LT_EXPR
&& tst
== -1)
1646 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1647 return boolean_true_node
;
1649 /* If VR is to the right of VAL, return false. */
1650 tst
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
1651 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1652 || (comp
== LE_EXPR
&& tst
== 1))
1653 return boolean_false_node
;
1655 /* Otherwise, we don't know. */
1658 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1662 /* If VR is to the right of VAL, return true. */
1663 tst
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
1664 if ((comp
== GT_EXPR
&& tst
== 1)
1665 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1666 return boolean_true_node
;
1668 /* If VR is to the left of VAL, return false. */
1669 tst
= compare_values_warnv (vr
->max
, val
, strict_overflow_p
);
1670 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1671 || (comp
== GE_EXPR
&& tst
== -1))
1672 return boolean_false_node
;
1674 /* Otherwise, we don't know. */
1680 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1681 would be profitable to adjust VR using scalar evolution information
1682 for VAR. If so, update VR with the new limits. */
1685 vr_values::adjust_range_with_scev (value_range
*vr
, struct loop
*loop
,
1686 gimple
*stmt
, tree var
)
1688 tree init
, step
, chrec
, tmin
, tmax
, min
, max
, type
, tem
;
1689 enum ev_direction dir
;
1691 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1692 better opportunities than a regular range, but I'm not sure. */
1693 if (vr
->type
== VR_ANTI_RANGE
)
1696 chrec
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, var
));
1698 /* Like in PR19590, scev can return a constant function. */
1699 if (is_gimple_min_invariant (chrec
))
1701 set_value_range_to_value (vr
, chrec
, vr
->equiv
);
1705 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1708 init
= initial_condition_in_loop_num (chrec
, loop
->num
);
1709 tem
= op_with_constant_singleton_value_range (init
);
1712 step
= evolution_part_in_loop_num (chrec
, loop
->num
);
1713 tem
= op_with_constant_singleton_value_range (step
);
1717 /* If STEP is symbolic, we can't know whether INIT will be the
1718 minimum or maximum value in the range. Also, unless INIT is
1719 a simple expression, compare_values and possibly other functions
1720 in tree-vrp won't be able to handle it. */
1721 if (step
== NULL_TREE
1722 || !is_gimple_min_invariant (step
)
1723 || !valid_value_p (init
))
1726 dir
= scev_direction (chrec
);
1727 if (/* Do not adjust ranges if we do not know whether the iv increases
1728 or decreases, ... */
1729 dir
== EV_DIR_UNKNOWN
1730 /* ... or if it may wrap. */
1731 || scev_probably_wraps_p (NULL_TREE
, init
, step
, stmt
,
1732 get_chrec_loop (chrec
), true))
1735 type
= TREE_TYPE (var
);
1736 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1737 tmin
= lower_bound_in_type (type
, type
);
1739 tmin
= TYPE_MIN_VALUE (type
);
1740 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1741 tmax
= upper_bound_in_type (type
, type
);
1743 tmax
= TYPE_MAX_VALUE (type
);
1745 /* Try to use estimated number of iterations for the loop to constrain the
1746 final value in the evolution. */
1747 if (TREE_CODE (step
) == INTEGER_CST
1748 && is_gimple_val (init
)
1749 && (TREE_CODE (init
) != SSA_NAME
1750 || get_value_range (init
)->type
== VR_RANGE
))
1754 /* We are only entering here for loop header PHI nodes, so using
1755 the number of latch executions is the correct thing to use. */
1756 if (max_loop_iterations (loop
, &nit
))
1758 value_range maxvr
= VR_INITIALIZER
;
1759 signop sgn
= TYPE_SIGN (TREE_TYPE (step
));
1762 widest_int wtmp
= wi::mul (wi::to_widest (step
), nit
, sgn
,
1764 /* If the multiplication overflowed we can't do a meaningful
1765 adjustment. Likewise if the result doesn't fit in the type
1766 of the induction variable. For a signed type we have to
1767 check whether the result has the expected signedness which
1768 is that of the step as number of iterations is unsigned. */
1770 && wi::fits_to_tree_p (wtmp
, TREE_TYPE (init
))
1772 || wi::gts_p (wtmp
, 0) == wi::gts_p (wi::to_wide (step
), 0)))
1774 tem
= wide_int_to_tree (TREE_TYPE (init
), wtmp
);
1775 extract_range_from_binary_expr (&maxvr
, PLUS_EXPR
,
1776 TREE_TYPE (init
), init
, tem
);
1777 /* Likewise if the addition did. */
1778 if (maxvr
.type
== VR_RANGE
)
1780 value_range initvr
= VR_INITIALIZER
;
1782 if (TREE_CODE (init
) == SSA_NAME
)
1783 initvr
= *(get_value_range (init
));
1784 else if (is_gimple_min_invariant (init
))
1785 set_value_range_to_value (&initvr
, init
, NULL
);
1789 /* Check if init + nit * step overflows. Though we checked
1790 scev {init, step}_loop doesn't wrap, it is not enough
1791 because the loop may exit immediately. Overflow could
1792 happen in the plus expression in this case. */
1793 if ((dir
== EV_DIR_DECREASES
1794 && compare_values (maxvr
.min
, initvr
.min
) != -1)
1795 || (dir
== EV_DIR_GROWS
1796 && compare_values (maxvr
.max
, initvr
.max
) != 1))
1806 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
1811 /* For VARYING or UNDEFINED ranges, just about anything we get
1812 from scalar evolutions should be better. */
1814 if (dir
== EV_DIR_DECREASES
)
1819 else if (vr
->type
== VR_RANGE
)
1824 if (dir
== EV_DIR_DECREASES
)
1826 /* INIT is the maximum value. If INIT is lower than VR->MAX
1827 but no smaller than VR->MIN, set VR->MAX to INIT. */
1828 if (compare_values (init
, max
) == -1)
1831 /* According to the loop information, the variable does not
1833 if (compare_values (min
, tmin
) == -1)
1839 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1840 if (compare_values (init
, min
) == 1)
1843 if (compare_values (tmax
, max
) == -1)
1850 /* If we just created an invalid range with the minimum
1851 greater than the maximum, we fail conservatively.
1852 This should happen only in unreachable
1853 parts of code, or for invalid programs. */
1854 if (compare_values (min
, max
) == 1)
1857 /* Even for valid range info, sometimes overflow flag will leak in.
1858 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1860 if (TREE_OVERFLOW_P (min
))
1861 min
= drop_tree_overflow (min
);
1862 if (TREE_OVERFLOW_P (max
))
1863 max
= drop_tree_overflow (max
);
1865 set_value_range (vr
, VR_RANGE
, min
, max
, vr
->equiv
);
1868 /* Dump value ranges of all SSA_NAMEs to FILE. */
1871 vr_values::dump_all_value_ranges (FILE *file
)
1875 for (i
= 0; i
< num_vr_values
; i
++)
1879 print_generic_expr (file
, ssa_name (i
));
1880 fprintf (file
, ": ");
1881 dump_value_range (file
, vr_value
[i
]);
1882 fprintf (file
, "\n");
1886 fprintf (file
, "\n");
1889 /* Initialize VRP lattice. */
1891 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
1893 values_propagated
= false;
1894 num_vr_values
= num_ssa_names
;
1895 vr_value
= XCNEWVEC (value_range
*, num_vr_values
);
1896 vr_phi_edge_counts
= XCNEWVEC (int, num_ssa_names
);
1897 bitmap_obstack_initialize (&vrp_equiv_obstack
);
1900 /* Free VRP lattice. */
1902 vr_values::~vr_values ()
1904 /* Free allocated memory. */
1906 free (vr_phi_edge_counts
);
1907 bitmap_obstack_release (&vrp_equiv_obstack
);
1908 vrp_value_range_pool
.release ();
1910 /* So that we can distinguish between VRP data being available
1911 and not available. */
1913 vr_phi_edge_counts
= NULL
;
1918 static class vr_values
*x_vr_values
;
1920 /* Return the singleton value-range for NAME or NAME. */
1923 vrp_valueize (tree name
)
1925 if (TREE_CODE (name
) == SSA_NAME
)
1927 value_range
*vr
= x_vr_values
->get_value_range (name
);
1928 if (vr
->type
== VR_RANGE
1929 && (TREE_CODE (vr
->min
) == SSA_NAME
1930 || is_gimple_min_invariant (vr
->min
))
1931 && vrp_operand_equal_p (vr
->min
, vr
->max
))
1937 /* Return the singleton value-range for NAME if that is a constant
1938 but signal to not follow SSA edges. */
1941 vrp_valueize_1 (tree name
)
1943 if (TREE_CODE (name
) == SSA_NAME
)
1945 /* If the definition may be simulated again we cannot follow
1946 this SSA edge as the SSA propagator does not necessarily
1947 re-visit the use. */
1948 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1949 if (!gimple_nop_p (def_stmt
)
1950 && prop_simulate_again_p (def_stmt
))
1952 value_range
*vr
= x_vr_values
->get_value_range (name
);
1953 if (range_int_cst_singleton_p (vr
))
1958 /* Visit assignment STMT. If it produces an interesting range, record
1959 the range in VR and set LHS to OUTPUT_P. */
1962 vr_values::vrp_visit_assignment_or_call (gimple
*stmt
, tree
*output_p
,
1966 enum gimple_code code
= gimple_code (stmt
);
1967 lhs
= gimple_get_lhs (stmt
);
1968 *output_p
= NULL_TREE
;
1970 /* We only keep track of ranges in integral and pointer types. */
1971 if (TREE_CODE (lhs
) == SSA_NAME
1972 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1973 /* It is valid to have NULL MIN/MAX values on a type. See
1974 build_range_type. */
1975 && TYPE_MIN_VALUE (TREE_TYPE (lhs
))
1976 && TYPE_MAX_VALUE (TREE_TYPE (lhs
)))
1977 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
1981 /* Try folding the statement to a constant first. */
1983 tree tem
= gimple_fold_stmt_to_constant_1 (stmt
, vrp_valueize
,
1988 if (TREE_CODE (tem
) == SSA_NAME
1989 && (SSA_NAME_IS_DEFAULT_DEF (tem
)
1990 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem
))))
1992 extract_range_from_ssa_name (vr
, tem
);
1995 else if (is_gimple_min_invariant (tem
))
1997 set_value_range_to_value (vr
, tem
, NULL
);
2001 /* Then dispatch to value-range extracting functions. */
2002 if (code
== GIMPLE_CALL
)
2003 extract_range_basic (vr
, stmt
);
2005 extract_range_from_assignment (vr
, as_a
<gassign
*> (stmt
));
2009 /* Helper that gets the value range of the SSA_NAME with version I
2010 or a symbolic range containing the SSA_NAME only if the value range
2011 is varying or undefined. */
2014 vr_values::get_vr_for_comparison (int i
)
2016 value_range vr
= *get_value_range (ssa_name (i
));
2018 /* If name N_i does not have a valid range, use N_i as its own
2019 range. This allows us to compare against names that may
2020 have N_i in their ranges. */
2021 if (vr
.type
== VR_VARYING
|| vr
.type
== VR_UNDEFINED
)
2024 vr
.min
= ssa_name (i
);
2025 vr
.max
= ssa_name (i
);
2031 /* Compare all the value ranges for names equivalent to VAR with VAL
2032 using comparison code COMP. Return the same value returned by
2033 compare_range_with_value, including the setting of
2034 *STRICT_OVERFLOW_P. */
2037 vr_values::compare_name_with_value (enum tree_code comp
, tree var
, tree val
,
2038 bool *strict_overflow_p
, bool use_equiv_p
)
2044 int used_strict_overflow
;
2046 value_range equiv_vr
;
2048 /* Get the set of equivalences for VAR. */
2049 e
= get_value_range (var
)->equiv
;
2051 /* Start at -1. Set it to 0 if we do a comparison without relying
2052 on overflow, or 1 if all comparisons rely on overflow. */
2053 used_strict_overflow
= -1;
2055 /* Compare vars' value range with val. */
2056 equiv_vr
= get_vr_for_comparison (SSA_NAME_VERSION (var
));
2058 retval
= compare_range_with_value (comp
, &equiv_vr
, val
, &sop
);
2060 used_strict_overflow
= sop
? 1 : 0;
2062 /* If the equiv set is empty we have done all work we need to do. */
2066 && used_strict_overflow
> 0)
2067 *strict_overflow_p
= true;
2071 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2073 tree name
= ssa_name (i
);
2078 && ! SSA_NAME_IS_DEFAULT_DEF (name
)
2079 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name
)))
2082 equiv_vr
= get_vr_for_comparison (i
);
2084 t
= compare_range_with_value (comp
, &equiv_vr
, val
, &sop
);
2087 /* If we get different answers from different members
2088 of the equivalence set this check must be in a dead
2089 code region. Folding it to a trap representation
2090 would be correct here. For now just return don't-know. */
2100 used_strict_overflow
= 0;
2101 else if (used_strict_overflow
< 0)
2102 used_strict_overflow
= 1;
2107 && used_strict_overflow
> 0)
2108 *strict_overflow_p
= true;
2114 /* Given a comparison code COMP and names N1 and N2, compare all the
2115 ranges equivalent to N1 against all the ranges equivalent to N2
2116 to determine the value of N1 COMP N2. Return the same value
2117 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2118 whether we relied on undefined signed overflow in the comparison. */
2122 vr_values::compare_names (enum tree_code comp
, tree n1
, tree n2
,
2123 bool *strict_overflow_p
)
2127 bitmap_iterator bi1
, bi2
;
2129 int used_strict_overflow
;
2130 static bitmap_obstack
*s_obstack
= NULL
;
2131 static bitmap s_e1
= NULL
, s_e2
= NULL
;
2133 /* Compare the ranges of every name equivalent to N1 against the
2134 ranges of every name equivalent to N2. */
2135 e1
= get_value_range (n1
)->equiv
;
2136 e2
= get_value_range (n2
)->equiv
;
2138 /* Use the fake bitmaps if e1 or e2 are not available. */
2139 if (s_obstack
== NULL
)
2141 s_obstack
= XNEW (bitmap_obstack
);
2142 bitmap_obstack_initialize (s_obstack
);
2143 s_e1
= BITMAP_ALLOC (s_obstack
);
2144 s_e2
= BITMAP_ALLOC (s_obstack
);
2151 /* Add N1 and N2 to their own set of equivalences to avoid
2152 duplicating the body of the loop just to check N1 and N2
2154 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2155 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2157 /* If the equivalence sets have a common intersection, then the two
2158 names can be compared without checking their ranges. */
2159 if (bitmap_intersect_p (e1
, e2
))
2161 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2162 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2164 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2166 : boolean_false_node
;
2169 /* Start at -1. Set it to 0 if we do a comparison without relying
2170 on overflow, or 1 if all comparisons rely on overflow. */
2171 used_strict_overflow
= -1;
2173 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2174 N2 to their own set of equivalences to avoid duplicating the body
2175 of the loop just to check N1 and N2 ranges. */
2176 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2178 if (! ssa_name (i1
))
2181 value_range vr1
= get_vr_for_comparison (i1
);
2183 t
= retval
= NULL_TREE
;
2184 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2186 if (! ssa_name (i2
))
2191 value_range vr2
= get_vr_for_comparison (i2
);
2193 t
= compare_ranges (comp
, &vr1
, &vr2
, &sop
);
2196 /* If we get different answers from different members
2197 of the equivalence set this check must be in a dead
2198 code region. Folding it to a trap representation
2199 would be correct here. For now just return don't-know. */
2203 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2204 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2210 used_strict_overflow
= 0;
2211 else if (used_strict_overflow
< 0)
2212 used_strict_overflow
= 1;
2218 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2219 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2220 if (used_strict_overflow
> 0)
2221 *strict_overflow_p
= true;
2226 /* None of the equivalent ranges are useful in computing this
2228 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2229 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2233 /* Helper function for vrp_evaluate_conditional_warnv & other
2237 vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2238 (enum tree_code code
, tree op0
, tree op1
, bool * strict_overflow_p
)
2240 value_range
*vr0
, *vr1
;
2242 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
2243 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
2245 tree res
= NULL_TREE
;
2247 res
= compare_ranges (code
, vr0
, vr1
, strict_overflow_p
);
2249 res
= compare_range_with_value (code
, vr0
, op1
, strict_overflow_p
);
2251 res
= (compare_range_with_value
2252 (swap_tree_comparison (code
), vr1
, op0
, strict_overflow_p
));
2256 /* Helper function for vrp_evaluate_conditional_warnv. */
2259 vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code
,
2262 bool *strict_overflow_p
,
2267 *only_ranges
= true;
2269 /* We only deal with integral and pointer types. */
2270 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2271 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
2274 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2275 as a simple equality test, then prefer that over its current form
2278 An overflow test which collapses to an equality test can always be
2279 expressed as a comparison of one argument against zero. Overflow
2280 occurs when the chosen argument is zero and does not occur if the
2281 chosen argument is not zero. */
2283 if (overflow_comparison_p (code
, op0
, op1
, use_equiv_p
, &x
))
2285 wide_int max
= wi::max_value (TYPE_PRECISION (TREE_TYPE (op0
)), UNSIGNED
);
2286 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2287 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2288 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2289 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2290 if (integer_zerop (x
))
2293 code
= (code
== LT_EXPR
|| code
== LE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2295 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2296 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2297 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2298 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2299 else if (wi::to_wide (x
) == max
- 1)
2302 op1
= wide_int_to_tree (TREE_TYPE (op0
), 0);
2303 code
= (code
== GT_EXPR
|| code
== GE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2307 if ((ret
= vrp_evaluate_conditional_warnv_with_ops_using_ranges
2308 (code
, op0
, op1
, strict_overflow_p
)))
2311 *only_ranges
= false;
2312 /* Do not use compare_names during propagation, it's quadratic. */
2313 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
2315 return compare_names (code
, op0
, op1
, strict_overflow_p
);
2316 else if (TREE_CODE (op0
) == SSA_NAME
)
2317 return compare_name_with_value (code
, op0
, op1
,
2318 strict_overflow_p
, use_equiv_p
);
2319 else if (TREE_CODE (op1
) == SSA_NAME
)
2320 return compare_name_with_value (swap_tree_comparison (code
), op1
, op0
,
2321 strict_overflow_p
, use_equiv_p
);
2325 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2326 information. Return NULL if the conditional can not be evaluated.
2327 The ranges of all the names equivalent with the operands in COND
2328 will be used when trying to compute the value. If the result is
2329 based on undefined signed overflow, issue a warning if
2333 vr_values::vrp_evaluate_conditional (tree_code code
, tree op0
,
2334 tree op1
, gimple
*stmt
)
2340 /* Some passes and foldings leak constants with overflow flag set
2341 into the IL. Avoid doing wrong things with these and bail out. */
2342 if ((TREE_CODE (op0
) == INTEGER_CST
2343 && TREE_OVERFLOW (op0
))
2344 || (TREE_CODE (op1
) == INTEGER_CST
2345 && TREE_OVERFLOW (op1
)))
2349 ret
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, true, &sop
,
2354 enum warn_strict_overflow_code wc
;
2355 const char* warnmsg
;
2357 if (is_gimple_min_invariant (ret
))
2359 wc
= WARN_STRICT_OVERFLOW_CONDITIONAL
;
2360 warnmsg
= G_("assuming signed overflow does not occur when "
2361 "simplifying conditional to constant");
2365 wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
2366 warnmsg
= G_("assuming signed overflow does not occur when "
2367 "simplifying conditional");
2370 if (issue_strict_overflow_warning (wc
))
2372 location_t location
;
2374 if (!gimple_has_location (stmt
))
2375 location
= input_location
;
2377 location
= gimple_location (stmt
);
2378 warning_at (location
, OPT_Wstrict_overflow
, "%s", warnmsg
);
2382 if (warn_type_limits
2383 && ret
&& only_ranges
2384 && TREE_CODE_CLASS (code
) == tcc_comparison
2385 && TREE_CODE (op0
) == SSA_NAME
)
2387 /* If the comparison is being folded and the operand on the LHS
2388 is being compared against a constant value that is outside of
2389 the natural range of OP0's type, then the predicate will
2390 always fold regardless of the value of OP0. If -Wtype-limits
2391 was specified, emit a warning. */
2392 tree type
= TREE_TYPE (op0
);
2393 value_range
*vr0
= get_value_range (op0
);
2395 if (vr0
->type
== VR_RANGE
2396 && INTEGRAL_TYPE_P (type
)
2397 && vrp_val_is_min (vr0
->min
)
2398 && vrp_val_is_max (vr0
->max
)
2399 && is_gimple_min_invariant (op1
))
2401 location_t location
;
2403 if (!gimple_has_location (stmt
))
2404 location
= input_location
;
2406 location
= gimple_location (stmt
);
2408 warning_at (location
, OPT_Wtype_limits
,
2410 ? G_("comparison always false "
2411 "due to limited range of data type")
2412 : G_("comparison always true "
2413 "due to limited range of data type"));
2421 /* Visit conditional statement STMT. If we can determine which edge
2422 will be taken out of STMT's basic block, record it in
2423 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2426 vr_values::vrp_visit_cond_stmt (gcond
*stmt
, edge
*taken_edge_p
)
2430 *taken_edge_p
= NULL
;
2432 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2437 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
2438 print_gimple_stmt (dump_file
, stmt
, 0);
2439 fprintf (dump_file
, "\nWith known ranges\n");
2441 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
2443 fprintf (dump_file
, "\t");
2444 print_generic_expr (dump_file
, use
);
2445 fprintf (dump_file
, ": ");
2446 dump_value_range (dump_file
, vr_value
[SSA_NAME_VERSION (use
)]);
2449 fprintf (dump_file
, "\n");
2452 /* Compute the value of the predicate COND by checking the known
2453 ranges of each of its operands.
2455 Note that we cannot evaluate all the equivalent ranges here
2456 because those ranges may not yet be final and with the current
2457 propagation strategy, we cannot determine when the value ranges
2458 of the names in the equivalence set have changed.
2460 For instance, given the following code fragment
2464 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2468 Assume that on the first visit to i_14, i_5 has the temporary
2469 range [8, 8] because the second argument to the PHI function is
2470 not yet executable. We derive the range ~[0, 0] for i_14 and the
2471 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2472 the first time, since i_14 is equivalent to the range [8, 8], we
2473 determine that the predicate is always false.
2475 On the next round of propagation, i_13 is determined to be
2476 VARYING, which causes i_5 to drop down to VARYING. So, another
2477 visit to i_14 is scheduled. In this second visit, we compute the
2478 exact same range and equivalence set for i_14, namely ~[0, 0] and
2479 { i_5 }. But we did not have the previous range for i_5
2480 registered, so vrp_visit_assignment thinks that the range for
2481 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2482 is not visited again, which stops propagation from visiting
2483 statements in the THEN clause of that if().
2485 To properly fix this we would need to keep the previous range
2486 value for the names in the equivalence set. This way we would've
2487 discovered that from one visit to the other i_5 changed from
2488 range [8, 8] to VR_VARYING.
2490 However, fixing this apparent limitation may not be worth the
2491 additional checking. Testing on several code bases (GCC, DLV,
2492 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2493 4 more predicates folded in SPEC. */
2496 val
= vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt
),
2497 gimple_cond_lhs (stmt
),
2498 gimple_cond_rhs (stmt
),
2501 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
2503 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2505 fprintf (dump_file
, "\nPredicate evaluates to: ");
2506 if (val
== NULL_TREE
)
2507 fprintf (dump_file
, "DON'T KNOW\n");
2509 print_generic_stmt (dump_file
, val
);
2513 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2514 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2515 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2516 Returns true if the default label is not needed. */
2519 find_case_label_ranges (gswitch
*stmt
, value_range
*vr
, size_t *min_idx1
,
2520 size_t *max_idx1
, size_t *min_idx2
,
2524 unsigned int n
= gimple_switch_num_labels (stmt
);
2526 tree case_low
, case_high
;
2527 tree min
= vr
->min
, max
= vr
->max
;
2529 gcc_checking_assert (vr
->type
== VR_RANGE
|| vr
->type
== VR_ANTI_RANGE
);
2531 take_default
= !find_case_label_range (stmt
, min
, max
, &i
, &j
);
2533 /* Set second range to emtpy. */
2537 if (vr
->type
== VR_RANGE
)
2541 return !take_default
;
2544 /* Set first range to all case labels. */
2551 /* Make sure all the values of case labels [i , j] are contained in
2552 range [MIN, MAX]. */
2553 case_low
= CASE_LOW (gimple_switch_label (stmt
, i
));
2554 case_high
= CASE_HIGH (gimple_switch_label (stmt
, j
));
2555 if (tree_int_cst_compare (case_low
, min
) < 0)
2557 if (case_high
!= NULL_TREE
2558 && tree_int_cst_compare (max
, case_high
) < 0)
2564 /* If the range spans case labels [i, j], the corresponding anti-range spans
2565 the labels [1, i - 1] and [j + 1, n - 1]. */
2591 /* Visit switch statement STMT. If we can determine which edge
2592 will be taken out of STMT's basic block, record it in
2593 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2596 vr_values::vrp_visit_switch_stmt (gswitch
*stmt
, edge
*taken_edge_p
)
2600 size_t i
= 0, j
= 0, k
, l
;
2603 *taken_edge_p
= NULL
;
2604 op
= gimple_switch_index (stmt
);
2605 if (TREE_CODE (op
) != SSA_NAME
)
2608 vr
= get_value_range (op
);
2609 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2611 fprintf (dump_file
, "\nVisiting switch expression with operand ");
2612 print_generic_expr (dump_file
, op
);
2613 fprintf (dump_file
, " with known range ");
2614 dump_value_range (dump_file
, vr
);
2615 fprintf (dump_file
, "\n");
2618 if ((vr
->type
!= VR_RANGE
2619 && vr
->type
!= VR_ANTI_RANGE
)
2620 || symbolic_range_p (vr
))
2623 /* Find the single edge that is taken from the switch expression. */
2624 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
2626 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2630 gcc_assert (take_default
);
2631 val
= gimple_switch_default_label (stmt
);
2635 /* Check if labels with index i to j and maybe the default label
2636 are all reaching the same label. */
2638 val
= gimple_switch_label (stmt
, i
);
2640 && CASE_LABEL (gimple_switch_default_label (stmt
))
2641 != CASE_LABEL (val
))
2643 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2644 fprintf (dump_file
, " not a single destination for this "
2648 for (++i
; i
<= j
; ++i
)
2650 if (CASE_LABEL (gimple_switch_label (stmt
, i
)) != CASE_LABEL (val
))
2652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2653 fprintf (dump_file
, " not a single destination for this "
2660 if (CASE_LABEL (gimple_switch_label (stmt
, k
)) != CASE_LABEL (val
))
2662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2663 fprintf (dump_file
, " not a single destination for this "
2670 *taken_edge_p
= find_edge (gimple_bb (stmt
),
2671 label_to_block (CASE_LABEL (val
)));
2673 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2675 fprintf (dump_file
, " will take edge to ");
2676 print_generic_stmt (dump_file
, CASE_LABEL (val
));
2681 /* Evaluate statement STMT. If the statement produces a useful range,
2682 set VR and corepsponding OUTPUT_P.
2684 If STMT is a conditional branch and we can determine its truth
2685 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2688 vr_values::extract_range_from_stmt (gimple
*stmt
, edge
*taken_edge_p
,
2689 tree
*output_p
, value_range
*vr
)
2692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2694 fprintf (dump_file
, "\nVisiting statement:\n");
2695 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
2698 if (!stmt_interesting_for_vrp (stmt
))
2699 gcc_assert (stmt_ends_bb_p (stmt
));
2700 else if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
2701 vrp_visit_assignment_or_call (stmt
, output_p
, vr
);
2702 else if (gimple_code (stmt
) == GIMPLE_COND
)
2703 vrp_visit_cond_stmt (as_a
<gcond
*> (stmt
), taken_edge_p
);
2704 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2705 vrp_visit_switch_stmt (as_a
<gswitch
*> (stmt
), taken_edge_p
);
2708 /* Visit all arguments for PHI node PHI that flow through executable
2709 edges. If a valid value range can be derived from all the incoming
2710 value ranges, set a new range in VR_RESULT. */
2713 vr_values::extract_range_from_phi_node (gphi
*phi
, value_range
*vr_result
)
2716 tree lhs
= PHI_RESULT (phi
);
2717 value_range
*lhs_vr
= get_value_range (lhs
);
2719 int edges
, old_edges
;
2722 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2724 fprintf (dump_file
, "\nVisiting PHI node: ");
2725 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
2728 bool may_simulate_backedge_again
= false;
2730 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2732 edge e
= gimple_phi_arg_edge (phi
, i
);
2734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2737 " Argument #%d (%d -> %d %sexecutable)\n",
2738 (int) i
, e
->src
->index
, e
->dest
->index
,
2739 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
2742 if (e
->flags
& EDGE_EXECUTABLE
)
2744 tree arg
= PHI_ARG_DEF (phi
, i
);
2749 if (TREE_CODE (arg
) == SSA_NAME
)
2751 /* See if we are eventually going to change one of the args. */
2752 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
2753 if (! gimple_nop_p (def_stmt
)
2754 && prop_simulate_again_p (def_stmt
)
2755 && e
->flags
& EDGE_DFS_BACK
)
2756 may_simulate_backedge_again
= true;
2758 vr_arg
= *(get_value_range (arg
));
2759 /* Do not allow equivalences or symbolic ranges to leak in from
2760 backedges. That creates invalid equivalencies.
2761 See PR53465 and PR54767. */
2762 if (e
->flags
& EDGE_DFS_BACK
)
2764 if (vr_arg
.type
== VR_RANGE
2765 || vr_arg
.type
== VR_ANTI_RANGE
)
2767 vr_arg
.equiv
= NULL
;
2768 if (symbolic_range_p (&vr_arg
))
2770 vr_arg
.type
= VR_VARYING
;
2771 vr_arg
.min
= NULL_TREE
;
2772 vr_arg
.max
= NULL_TREE
;
2778 /* If the non-backedge arguments range is VR_VARYING then
2779 we can still try recording a simple equivalence. */
2780 if (vr_arg
.type
== VR_VARYING
)
2782 vr_arg
.type
= VR_RANGE
;
2785 vr_arg
.equiv
= NULL
;
2791 if (TREE_OVERFLOW_P (arg
))
2792 arg
= drop_tree_overflow (arg
);
2794 vr_arg
.type
= VR_RANGE
;
2797 vr_arg
.equiv
= NULL
;
2800 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2802 fprintf (dump_file
, "\t");
2803 print_generic_expr (dump_file
, arg
, dump_flags
);
2804 fprintf (dump_file
, ": ");
2805 dump_value_range (dump_file
, &vr_arg
);
2806 fprintf (dump_file
, "\n");
2810 copy_value_range (vr_result
, &vr_arg
);
2812 vrp_meet (vr_result
, &vr_arg
);
2815 if (vr_result
->type
== VR_VARYING
)
2820 if (vr_result
->type
== VR_VARYING
)
2822 else if (vr_result
->type
== VR_UNDEFINED
)
2825 old_edges
= vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)];
2826 vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)] = edges
;
2828 /* To prevent infinite iterations in the algorithm, derive ranges
2829 when the new value is slightly bigger or smaller than the
2830 previous one. We don't do this if we have seen a new executable
2831 edge; this helps us avoid an infinity for conditionals
2832 which are not in a loop. If the old value-range was VR_UNDEFINED
2833 use the updated range and iterate one more time. If we will not
2834 simulate this PHI again via the backedge allow us to iterate. */
2836 && gimple_phi_num_args (phi
) > 1
2837 && edges
== old_edges
2838 && lhs_vr
->type
!= VR_UNDEFINED
2839 && may_simulate_backedge_again
)
2841 /* Compare old and new ranges, fall back to varying if the
2842 values are not comparable. */
2843 int cmp_min
= compare_values (lhs_vr
->min
, vr_result
->min
);
2846 int cmp_max
= compare_values (lhs_vr
->max
, vr_result
->max
);
2850 /* For non VR_RANGE or for pointers fall back to varying if
2851 the range changed. */
2852 if ((lhs_vr
->type
!= VR_RANGE
|| vr_result
->type
!= VR_RANGE
2853 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2854 && (cmp_min
!= 0 || cmp_max
!= 0))
2857 /* If the new minimum is larger than the previous one
2858 retain the old value. If the new minimum value is smaller
2859 than the previous one and not -INF go all the way to -INF + 1.
2860 In the first case, to avoid infinite bouncing between different
2861 minimums, and in the other case to avoid iterating millions of
2862 times to reach -INF. Going to -INF + 1 also lets the following
2863 iteration compute whether there will be any overflow, at the
2864 expense of one additional iteration. */
2866 vr_result
->min
= lhs_vr
->min
;
2867 else if (cmp_min
> 0
2868 && !vrp_val_is_min (vr_result
->min
))
2870 = int_const_binop (PLUS_EXPR
,
2871 vrp_val_min (TREE_TYPE (vr_result
->min
)),
2872 build_int_cst (TREE_TYPE (vr_result
->min
), 1));
2874 /* Similarly for the maximum value. */
2876 vr_result
->max
= lhs_vr
->max
;
2877 else if (cmp_max
< 0
2878 && !vrp_val_is_max (vr_result
->max
))
2880 = int_const_binop (MINUS_EXPR
,
2881 vrp_val_max (TREE_TYPE (vr_result
->min
)),
2882 build_int_cst (TREE_TYPE (vr_result
->min
), 1));
2884 /* If we dropped either bound to +-INF then if this is a loop
2885 PHI node SCEV may known more about its value-range. */
2886 if (cmp_min
> 0 || cmp_min
< 0
2887 || cmp_max
< 0 || cmp_max
> 0)
2890 goto infinite_check
;
2896 set_value_range_to_varying (vr_result
);
2899 /* If this is a loop PHI node SCEV may known more about its value-range.
2900 scev_check can be reached from two paths, one is a fall through from above
2901 "varying" label, the other is direct goto from code block which tries to
2902 avoid infinite simulation. */
2903 if ((l
= loop_containing_stmt (phi
))
2904 && l
->header
== gimple_bb (phi
))
2905 adjust_range_with_scev (vr_result
, l
, phi
, lhs
);
2908 /* If we will end up with a (-INF, +INF) range, set it to
2909 VARYING. Same if the previous max value was invalid for
2910 the type and we end up with vr_result.min > vr_result.max. */
2911 if ((vr_result
->type
== VR_RANGE
|| vr_result
->type
== VR_ANTI_RANGE
)
2912 && !((vrp_val_is_max (vr_result
->max
) && vrp_val_is_min (vr_result
->min
))
2913 || compare_values (vr_result
->min
, vr_result
->max
) > 0))
2916 set_value_range_to_varying (vr_result
);
2918 /* If the new range is different than the previous value, keep
2924 /* Simplify boolean operations if the source is known
2925 to be already a boolean. */
2927 vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator
*gsi
,
2930 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2932 bool need_conversion
;
2934 /* We handle only !=/== case here. */
2935 gcc_assert (rhs_code
== EQ_EXPR
|| rhs_code
== NE_EXPR
);
2937 op0
= gimple_assign_rhs1 (stmt
);
2938 if (!op_with_boolean_value_range_p (op0
))
2941 op1
= gimple_assign_rhs2 (stmt
);
2942 if (!op_with_boolean_value_range_p (op1
))
2945 /* Reduce number of cases to handle to NE_EXPR. As there is no
2946 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
2947 if (rhs_code
== EQ_EXPR
)
2949 if (TREE_CODE (op1
) == INTEGER_CST
)
2950 op1
= int_const_binop (BIT_XOR_EXPR
, op1
,
2951 build_int_cst (TREE_TYPE (op1
), 1));
2956 lhs
= gimple_assign_lhs (stmt
);
2958 = !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
));
2960 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
2962 && !TYPE_UNSIGNED (TREE_TYPE (op0
))
2963 && TYPE_PRECISION (TREE_TYPE (op0
)) == 1
2964 && TYPE_PRECISION (TREE_TYPE (lhs
)) > 1)
2967 /* For A != 0 we can substitute A itself. */
2968 if (integer_zerop (op1
))
2969 gimple_assign_set_rhs_with_ops (gsi
,
2971 ? NOP_EXPR
: TREE_CODE (op0
), op0
);
2972 /* For A != B we substitute A ^ B. Either with conversion. */
2973 else if (need_conversion
)
2975 tree tem
= make_ssa_name (TREE_TYPE (op0
));
2977 = gimple_build_assign (tem
, BIT_XOR_EXPR
, op0
, op1
);
2978 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
2979 if (INTEGRAL_TYPE_P (TREE_TYPE (tem
))
2980 && TYPE_PRECISION (TREE_TYPE (tem
)) > 1)
2981 set_range_info (tem
, VR_RANGE
,
2982 wi::zero (TYPE_PRECISION (TREE_TYPE (tem
))),
2983 wi::one (TYPE_PRECISION (TREE_TYPE (tem
))));
2984 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, tem
);
2988 gimple_assign_set_rhs_with_ops (gsi
, BIT_XOR_EXPR
, op0
, op1
);
2989 update_stmt (gsi_stmt (*gsi
));
2990 fold_stmt (gsi
, follow_single_use_edges
);
2995 /* Simplify a division or modulo operator to a right shift or bitwise and
2996 if the first operand is unsigned or is greater than zero and the second
2997 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
2998 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
2999 optimize it into just op0 if op0's range is known to be a subset of
3000 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3004 vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator
*gsi
,
3007 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3009 tree op0
= gimple_assign_rhs1 (stmt
);
3010 tree op1
= gimple_assign_rhs2 (stmt
);
3011 tree op0min
= NULL_TREE
, op0max
= NULL_TREE
;
3013 value_range
*vr
= NULL
;
3015 if (TREE_CODE (op0
) == INTEGER_CST
)
3022 vr
= get_value_range (op0
);
3023 if (range_int_cst_p (vr
))
3030 if (rhs_code
== TRUNC_MOD_EXPR
3031 && TREE_CODE (op1
) == SSA_NAME
)
3033 value_range
*vr1
= get_value_range (op1
);
3034 if (range_int_cst_p (vr1
))
3037 if (rhs_code
== TRUNC_MOD_EXPR
3038 && TREE_CODE (op1min
) == INTEGER_CST
3039 && tree_int_cst_sgn (op1min
) == 1
3041 && tree_int_cst_lt (op0max
, op1min
))
3043 if (TYPE_UNSIGNED (TREE_TYPE (op0
))
3044 || tree_int_cst_sgn (op0min
) >= 0
3045 || tree_int_cst_lt (fold_unary (NEGATE_EXPR
, TREE_TYPE (op1min
), op1min
),
3048 /* If op0 already has the range op0 % op1 has,
3049 then TRUNC_MOD_EXPR won't change anything. */
3050 gimple_assign_set_rhs_from_tree (gsi
, op0
);
3055 if (TREE_CODE (op0
) != SSA_NAME
)
3058 if (!integer_pow2p (op1
))
3060 /* X % -Y can be only optimized into X % Y either if
3061 X is not INT_MIN, or Y is not -1. Fold it now, as after
3062 remove_range_assertions the range info might be not available
3064 if (rhs_code
== TRUNC_MOD_EXPR
3065 && fold_stmt (gsi
, follow_single_use_edges
))
3070 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
3071 val
= integer_one_node
;
3076 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
3080 && integer_onep (val
)
3081 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3083 location_t location
;
3085 if (!gimple_has_location (stmt
))
3086 location
= input_location
;
3088 location
= gimple_location (stmt
);
3089 warning_at (location
, OPT_Wstrict_overflow
,
3090 "assuming signed overflow does not occur when "
3091 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3095 if (val
&& integer_onep (val
))
3099 if (rhs_code
== TRUNC_DIV_EXPR
)
3101 t
= build_int_cst (integer_type_node
, tree_log2 (op1
));
3102 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
3103 gimple_assign_set_rhs1 (stmt
, op0
);
3104 gimple_assign_set_rhs2 (stmt
, t
);
3108 t
= build_int_cst (TREE_TYPE (op1
), 1);
3109 t
= int_const_binop (MINUS_EXPR
, op1
, t
);
3110 t
= fold_convert (TREE_TYPE (op0
), t
);
3112 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
3113 gimple_assign_set_rhs1 (stmt
, op0
);
3114 gimple_assign_set_rhs2 (stmt
, t
);
3118 fold_stmt (gsi
, follow_single_use_edges
);
3125 /* Simplify a min or max if the ranges of the two operands are
3126 disjoint. Return true if we do simplify. */
3129 vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator
*gsi
,
3132 tree op0
= gimple_assign_rhs1 (stmt
);
3133 tree op1
= gimple_assign_rhs2 (stmt
);
3137 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3138 (LE_EXPR
, op0
, op1
, &sop
));
3142 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3143 (LT_EXPR
, op0
, op1
, &sop
));
3148 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3150 location_t location
;
3152 if (!gimple_has_location (stmt
))
3153 location
= input_location
;
3155 location
= gimple_location (stmt
);
3156 warning_at (location
, OPT_Wstrict_overflow
,
3157 "assuming signed overflow does not occur when "
3158 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3161 /* VAL == TRUE -> OP0 < or <= op1
3162 VAL == FALSE -> OP0 > or >= op1. */
3163 tree res
= ((gimple_assign_rhs_code (stmt
) == MAX_EXPR
)
3164 == integer_zerop (val
)) ? op0
: op1
;
3165 gimple_assign_set_rhs_from_tree (gsi
, res
);
3172 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3173 ABS_EXPR. If the operand is <= 0, then simplify the
3174 ABS_EXPR into a NEGATE_EXPR. */
3177 vr_values::simplify_abs_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3179 tree op
= gimple_assign_rhs1 (stmt
);
3180 value_range
*vr
= get_value_range (op
);
3187 val
= compare_range_with_value (LE_EXPR
, vr
, integer_zero_node
, &sop
);
3190 /* The range is neither <= 0 nor > 0. Now see if it is
3191 either < 0 or >= 0. */
3193 val
= compare_range_with_value (LT_EXPR
, vr
, integer_zero_node
,
3199 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3201 location_t location
;
3203 if (!gimple_has_location (stmt
))
3204 location
= input_location
;
3206 location
= gimple_location (stmt
);
3207 warning_at (location
, OPT_Wstrict_overflow
,
3208 "assuming signed overflow does not occur when "
3209 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3212 gimple_assign_set_rhs1 (stmt
, op
);
3213 if (integer_zerop (val
))
3214 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
3216 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
3218 fold_stmt (gsi
, follow_single_use_edges
);
3226 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3227 If all the bits that are being cleared by & are already
3228 known to be zero from VR, or all the bits that are being
3229 set by | are already known to be one from VR, the bit
3230 operation is redundant. */
3233 vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator
*gsi
,
3236 tree op0
= gimple_assign_rhs1 (stmt
);
3237 tree op1
= gimple_assign_rhs2 (stmt
);
3238 tree op
= NULL_TREE
;
3239 value_range vr0
= VR_INITIALIZER
;
3240 value_range vr1
= VR_INITIALIZER
;
3241 wide_int may_be_nonzero0
, may_be_nonzero1
;
3242 wide_int must_be_nonzero0
, must_be_nonzero1
;
3245 if (TREE_CODE (op0
) == SSA_NAME
)
3246 vr0
= *(get_value_range (op0
));
3247 else if (is_gimple_min_invariant (op0
))
3248 set_value_range_to_value (&vr0
, op0
, NULL
);
3252 if (TREE_CODE (op1
) == SSA_NAME
)
3253 vr1
= *(get_value_range (op1
));
3254 else if (is_gimple_min_invariant (op1
))
3255 set_value_range_to_value (&vr1
, op1
, NULL
);
3259 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op0
), &vr0
, &may_be_nonzero0
,
3262 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op1
), &vr1
, &may_be_nonzero1
,
3266 switch (gimple_assign_rhs_code (stmt
))
3269 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3275 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3283 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3289 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3300 if (op
== NULL_TREE
)
3303 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (op
), op
);
3304 update_stmt (gsi_stmt (*gsi
));
3308 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3309 a known value range VR.
3311 If there is one and only one value which will satisfy the
3312 conditional, then return that value. Else return NULL.
3314 If signed overflow must be undefined for the value to satisfy
3315 the conditional, then set *STRICT_OVERFLOW_P to true. */
3318 test_for_singularity (enum tree_code cond_code
, tree op0
,
3319 tree op1
, value_range
*vr
)
3324 /* Extract minimum/maximum values which satisfy the conditional as it was
3326 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
3328 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
3331 if (cond_code
== LT_EXPR
)
3333 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3334 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
3335 /* Signal to compare_values_warnv this expr doesn't overflow. */
3337 TREE_NO_WARNING (max
) = 1;
3340 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
3342 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
3345 if (cond_code
== GT_EXPR
)
3347 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3348 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
3349 /* Signal to compare_values_warnv this expr doesn't overflow. */
3351 TREE_NO_WARNING (min
) = 1;
3355 /* Now refine the minimum and maximum values using any
3356 value range information we have for op0. */
3359 if (compare_values (vr
->min
, min
) == 1)
3361 if (compare_values (vr
->max
, max
) == -1)
3364 /* If the new min/max values have converged to a single value,
3365 then there is only one value which can satisfy the condition,
3366 return that value. */
3367 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
3373 /* Return whether the value range *VR fits in an integer type specified
3374 by PRECISION and UNSIGNED_P. */
3377 range_fits_type_p (value_range
*vr
, unsigned dest_precision
, signop dest_sgn
)
3380 unsigned src_precision
;
3384 /* We can only handle integral and pointer types. */
3385 src_type
= TREE_TYPE (vr
->min
);
3386 if (!INTEGRAL_TYPE_P (src_type
)
3387 && !POINTER_TYPE_P (src_type
))
3390 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3391 and so is an identity transform. */
3392 src_precision
= TYPE_PRECISION (TREE_TYPE (vr
->min
));
3393 src_sgn
= TYPE_SIGN (src_type
);
3394 if ((src_precision
< dest_precision
3395 && !(dest_sgn
== UNSIGNED
&& src_sgn
== SIGNED
))
3396 || (src_precision
== dest_precision
&& src_sgn
== dest_sgn
))
3399 /* Now we can only handle ranges with constant bounds. */
3400 if (vr
->type
!= VR_RANGE
3401 || TREE_CODE (vr
->min
) != INTEGER_CST
3402 || TREE_CODE (vr
->max
) != INTEGER_CST
)
3405 /* For sign changes, the MSB of the wide_int has to be clear.
3406 An unsigned value with its MSB set cannot be represented by
3407 a signed wide_int, while a negative value cannot be represented
3408 by an unsigned wide_int. */
3409 if (src_sgn
!= dest_sgn
3410 && (wi::lts_p (wi::to_wide (vr
->min
), 0)
3411 || wi::lts_p (wi::to_wide (vr
->max
), 0)))
3414 /* Then we can perform the conversion on both ends and compare
3415 the result for equality. */
3416 tem
= wi::ext (wi::to_widest (vr
->min
), dest_precision
, dest_sgn
);
3417 if (tem
!= wi::to_widest (vr
->min
))
3419 tem
= wi::ext (wi::to_widest (vr
->max
), dest_precision
, dest_sgn
);
3420 if (tem
!= wi::to_widest (vr
->max
))
3426 /* Simplify a conditional using a relational operator to an equality
3427 test if the range information indicates only one value can satisfy
3428 the original conditional. */
3431 vr_values::simplify_cond_using_ranges_1 (gcond
*stmt
)
3433 tree op0
= gimple_cond_lhs (stmt
);
3434 tree op1
= gimple_cond_rhs (stmt
);
3435 enum tree_code cond_code
= gimple_cond_code (stmt
);
3437 if (cond_code
!= NE_EXPR
3438 && cond_code
!= EQ_EXPR
3439 && TREE_CODE (op0
) == SSA_NAME
3440 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3441 && is_gimple_min_invariant (op1
))
3443 value_range
*vr
= get_value_range (op0
);
3445 /* If we have range information for OP0, then we might be
3446 able to simplify this conditional. */
3447 if (vr
->type
== VR_RANGE
)
3449 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
3454 fprintf (dump_file
, "Simplified relational ");
3455 print_gimple_stmt (dump_file
, stmt
, 0);
3456 fprintf (dump_file
, " into ");
3459 gimple_cond_set_code (stmt
, EQ_EXPR
);
3460 gimple_cond_set_lhs (stmt
, op0
);
3461 gimple_cond_set_rhs (stmt
, new_tree
);
3467 print_gimple_stmt (dump_file
, stmt
, 0);
3468 fprintf (dump_file
, "\n");
3474 /* Try again after inverting the condition. We only deal
3475 with integral types here, so no need to worry about
3476 issues with inverting FP comparisons. */
3477 new_tree
= test_for_singularity
3478 (invert_tree_comparison (cond_code
, false),
3484 fprintf (dump_file
, "Simplified relational ");
3485 print_gimple_stmt (dump_file
, stmt
, 0);
3486 fprintf (dump_file
, " into ");
3489 gimple_cond_set_code (stmt
, NE_EXPR
);
3490 gimple_cond_set_lhs (stmt
, op0
);
3491 gimple_cond_set_rhs (stmt
, new_tree
);
3497 print_gimple_stmt (dump_file
, stmt
, 0);
3498 fprintf (dump_file
, "\n");
3508 /* STMT is a conditional at the end of a basic block.
3510 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3511 was set via a type conversion, try to replace the SSA_NAME with the RHS
3512 of the type conversion. Doing so makes the conversion dead which helps
3513 subsequent passes. */
3516 vr_values::simplify_cond_using_ranges_2 (gcond
*stmt
)
3518 tree op0
= gimple_cond_lhs (stmt
);
3519 tree op1
= gimple_cond_rhs (stmt
);
3521 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3522 see if OP0 was set by a type conversion where the source of
3523 the conversion is another SSA_NAME with a range that fits
3524 into the range of OP0's type.
3526 If so, the conversion is redundant as the earlier SSA_NAME can be
3527 used for the comparison directly if we just massage the constant in the
3529 if (TREE_CODE (op0
) == SSA_NAME
3530 && TREE_CODE (op1
) == INTEGER_CST
)
3532 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op0
);
3535 if (!is_gimple_assign (def_stmt
)
3536 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3539 innerop
= gimple_assign_rhs1 (def_stmt
);
3541 if (TREE_CODE (innerop
) == SSA_NAME
3542 && !POINTER_TYPE_P (TREE_TYPE (innerop
))
3543 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
)
3544 && desired_pro_or_demotion_p (TREE_TYPE (innerop
), TREE_TYPE (op0
)))
3546 value_range
*vr
= get_value_range (innerop
);
3548 if (range_int_cst_p (vr
)
3549 && range_fits_type_p (vr
,
3550 TYPE_PRECISION (TREE_TYPE (op0
)),
3551 TYPE_SIGN (TREE_TYPE (op0
)))
3552 && int_fits_type_p (op1
, TREE_TYPE (innerop
)))
3554 tree newconst
= fold_convert (TREE_TYPE (innerop
), op1
);
3555 gimple_cond_set_lhs (stmt
, innerop
);
3556 gimple_cond_set_rhs (stmt
, newconst
);
3558 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3560 fprintf (dump_file
, "Folded into: ");
3561 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3562 fprintf (dump_file
, "\n");
3569 /* Simplify a switch statement using the value range of the switch
3573 vr_values::simplify_switch_using_ranges (gswitch
*stmt
)
3575 tree op
= gimple_switch_index (stmt
);
3576 value_range
*vr
= NULL
;
3580 size_t i
= 0, j
= 0, n
, n2
;
3583 size_t k
= 1, l
= 0;
3585 if (TREE_CODE (op
) == SSA_NAME
)
3587 vr
= get_value_range (op
);
3589 /* We can only handle integer ranges. */
3590 if ((vr
->type
!= VR_RANGE
3591 && vr
->type
!= VR_ANTI_RANGE
)
3592 || symbolic_range_p (vr
))
3595 /* Find case label for min/max of the value range. */
3596 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
3598 else if (TREE_CODE (op
) == INTEGER_CST
)
3600 take_default
= !find_case_label_index (stmt
, 1, op
, &i
);
3614 n
= gimple_switch_num_labels (stmt
);
3616 /* We can truncate the case label ranges that partially overlap with OP's
3618 size_t min_idx
= 1, max_idx
= 0;
3620 find_case_label_range (stmt
, vr
->min
, vr
->max
, &min_idx
, &max_idx
);
3621 if (min_idx
<= max_idx
)
3623 tree min_label
= gimple_switch_label (stmt
, min_idx
);
3624 tree max_label
= gimple_switch_label (stmt
, max_idx
);
3626 /* Avoid changing the type of the case labels when truncating. */
3627 tree case_label_type
= TREE_TYPE (CASE_LOW (min_label
));
3628 tree vr_min
= fold_convert (case_label_type
, vr
->min
);
3629 tree vr_max
= fold_convert (case_label_type
, vr
->max
);
3631 if (vr
->type
== VR_RANGE
)
3633 /* If OP's value range is [2,8] and the low label range is
3634 0 ... 3, truncate the label's range to 2 .. 3. */
3635 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3636 && CASE_HIGH (min_label
) != NULL_TREE
3637 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3638 CASE_LOW (min_label
) = vr_min
;
3640 /* If OP's value range is [2,8] and the high label range is
3641 7 ... 10, truncate the label's range to 7 .. 8. */
3642 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3643 && CASE_HIGH (max_label
) != NULL_TREE
3644 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3645 CASE_HIGH (max_label
) = vr_max
;
3647 else if (vr
->type
== VR_ANTI_RANGE
)
3649 tree one_cst
= build_one_cst (case_label_type
);
3651 if (min_label
== max_label
)
3653 /* If OP's value range is ~[7,8] and the label's range is
3654 7 ... 10, truncate the label's range to 9 ... 10. */
3655 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) == 0
3656 && CASE_HIGH (min_label
) != NULL_TREE
3657 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) > 0)
3658 CASE_LOW (min_label
)
3659 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3661 /* If OP's value range is ~[7,8] and the label's range is
3662 5 ... 8, truncate the label's range to 5 ... 6. */
3663 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3664 && CASE_HIGH (min_label
) != NULL_TREE
3665 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) == 0)
3666 CASE_HIGH (min_label
)
3667 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3671 /* If OP's value range is ~[2,8] and the low label range is
3672 0 ... 3, truncate the label's range to 0 ... 1. */
3673 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3674 && CASE_HIGH (min_label
) != NULL_TREE
3675 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3676 CASE_HIGH (min_label
)
3677 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3679 /* If OP's value range is ~[2,8] and the high label range is
3680 7 ... 10, truncate the label's range to 9 ... 10. */
3681 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3682 && CASE_HIGH (max_label
) != NULL_TREE
3683 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3684 CASE_LOW (max_label
)
3685 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3689 /* Canonicalize singleton case ranges. */
3690 if (tree_int_cst_equal (CASE_LOW (min_label
), CASE_HIGH (min_label
)))
3691 CASE_HIGH (min_label
) = NULL_TREE
;
3692 if (tree_int_cst_equal (CASE_LOW (max_label
), CASE_HIGH (max_label
)))
3693 CASE_HIGH (max_label
) = NULL_TREE
;
3696 /* We can also eliminate case labels that lie completely outside OP's value
3699 /* Bail out if this is just all edges taken. */
3705 /* Build a new vector of taken case labels. */
3706 vec2
= make_tree_vec (j
- i
+ 1 + l
- k
+ 1 + (int)take_default
);
3709 /* Add the default edge, if necessary. */
3711 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
3713 for (; i
<= j
; ++i
, ++n2
)
3714 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
3716 for (; k
<= l
; ++k
, ++n2
)
3717 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, k
);
3719 /* Mark needed edges. */
3720 for (i
= 0; i
< n2
; ++i
)
3722 e
= find_edge (gimple_bb (stmt
),
3723 label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
3724 e
->aux
= (void *)-1;
3727 /* Queue not needed edges for later removal. */
3728 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
3730 if (e
->aux
== (void *)-1)
3736 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3738 fprintf (dump_file
, "removing unreachable case label\n");
3740 to_remove_edges
.safe_push (e
);
3741 e
->flags
&= ~EDGE_EXECUTABLE
;
3744 /* And queue an update for the stmt. */
3747 to_update_switch_stmts
.safe_push (su
);
3751 /* Simplify an integral conversion from an SSA name in STMT. */
3754 simplify_conversion_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3756 tree innerop
, middleop
, finaltype
;
3758 signop inner_sgn
, middle_sgn
, final_sgn
;
3759 unsigned inner_prec
, middle_prec
, final_prec
;
3760 widest_int innermin
, innermed
, innermax
, middlemin
, middlemed
, middlemax
;
3762 finaltype
= TREE_TYPE (gimple_assign_lhs (stmt
));
3763 if (!INTEGRAL_TYPE_P (finaltype
))
3765 middleop
= gimple_assign_rhs1 (stmt
);
3766 def_stmt
= SSA_NAME_DEF_STMT (middleop
);
3767 if (!is_gimple_assign (def_stmt
)
3768 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3770 innerop
= gimple_assign_rhs1 (def_stmt
);
3771 if (TREE_CODE (innerop
) != SSA_NAME
3772 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
))
3775 /* Get the value-range of the inner operand. Use get_range_info in
3776 case innerop was created during substitute-and-fold. */
3777 wide_int imin
, imax
;
3778 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
))
3779 || get_range_info (innerop
, &imin
, &imax
) != VR_RANGE
)
3781 innermin
= widest_int::from (imin
, TYPE_SIGN (TREE_TYPE (innerop
)));
3782 innermax
= widest_int::from (imax
, TYPE_SIGN (TREE_TYPE (innerop
)));
3784 /* Simulate the conversion chain to check if the result is equal if
3785 the middle conversion is removed. */
3786 inner_prec
= TYPE_PRECISION (TREE_TYPE (innerop
));
3787 middle_prec
= TYPE_PRECISION (TREE_TYPE (middleop
));
3788 final_prec
= TYPE_PRECISION (finaltype
);
3790 /* If the first conversion is not injective, the second must not
3792 if (wi::gtu_p (innermax
- innermin
,
3793 wi::mask
<widest_int
> (middle_prec
, false))
3794 && middle_prec
< final_prec
)
3796 /* We also want a medium value so that we can track the effect that
3797 narrowing conversions with sign change have. */
3798 inner_sgn
= TYPE_SIGN (TREE_TYPE (innerop
));
3799 if (inner_sgn
== UNSIGNED
)
3800 innermed
= wi::shifted_mask
<widest_int
> (1, inner_prec
- 1, false);
3803 if (wi::cmp (innermin
, innermed
, inner_sgn
) >= 0
3804 || wi::cmp (innermed
, innermax
, inner_sgn
) >= 0)
3805 innermed
= innermin
;
3807 middle_sgn
= TYPE_SIGN (TREE_TYPE (middleop
));
3808 middlemin
= wi::ext (innermin
, middle_prec
, middle_sgn
);
3809 middlemed
= wi::ext (innermed
, middle_prec
, middle_sgn
);
3810 middlemax
= wi::ext (innermax
, middle_prec
, middle_sgn
);
3812 /* Require that the final conversion applied to both the original
3813 and the intermediate range produces the same result. */
3814 final_sgn
= TYPE_SIGN (finaltype
);
3815 if (wi::ext (middlemin
, final_prec
, final_sgn
)
3816 != wi::ext (innermin
, final_prec
, final_sgn
)
3817 || wi::ext (middlemed
, final_prec
, final_sgn
)
3818 != wi::ext (innermed
, final_prec
, final_sgn
)
3819 || wi::ext (middlemax
, final_prec
, final_sgn
)
3820 != wi::ext (innermax
, final_prec
, final_sgn
))
3823 gimple_assign_set_rhs1 (stmt
, innerop
);
3824 fold_stmt (gsi
, follow_single_use_edges
);
3828 /* Simplify a conversion from integral SSA name to float in STMT. */
3831 vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator
*gsi
,
3834 tree rhs1
= gimple_assign_rhs1 (stmt
);
3835 value_range
*vr
= get_value_range (rhs1
);
3836 scalar_float_mode fltmode
3837 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
)));
3838 scalar_int_mode mode
;
3842 /* We can only handle constant ranges. */
3843 if (vr
->type
!= VR_RANGE
3844 || TREE_CODE (vr
->min
) != INTEGER_CST
3845 || TREE_CODE (vr
->max
) != INTEGER_CST
)
3848 /* First check if we can use a signed type in place of an unsigned. */
3849 scalar_int_mode rhs_mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1
));
3850 if (TYPE_UNSIGNED (TREE_TYPE (rhs1
))
3851 && can_float_p (fltmode
, rhs_mode
, 0) != CODE_FOR_nothing
3852 && range_fits_type_p (vr
, TYPE_PRECISION (TREE_TYPE (rhs1
)), SIGNED
))
3854 /* If we can do the conversion in the current input mode do nothing. */
3855 else if (can_float_p (fltmode
, rhs_mode
,
3856 TYPE_UNSIGNED (TREE_TYPE (rhs1
))) != CODE_FOR_nothing
)
3858 /* Otherwise search for a mode we can use, starting from the narrowest
3859 integer mode available. */
3862 mode
= NARROWEST_INT_MODE
;
3865 /* If we cannot do a signed conversion to float from mode
3866 or if the value-range does not fit in the signed type
3867 try with a wider mode. */
3868 if (can_float_p (fltmode
, mode
, 0) != CODE_FOR_nothing
3869 && range_fits_type_p (vr
, GET_MODE_PRECISION (mode
), SIGNED
))
3872 /* But do not widen the input. Instead leave that to the
3873 optabs expansion code. */
3874 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
3875 || GET_MODE_PRECISION (mode
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
3880 /* It works, insert a truncation or sign-change before the
3881 float conversion. */
3882 tem
= make_ssa_name (build_nonstandard_integer_type
3883 (GET_MODE_PRECISION (mode
), 0));
3884 conv
= gimple_build_assign (tem
, NOP_EXPR
, rhs1
);
3885 gsi_insert_before (gsi
, conv
, GSI_SAME_STMT
);
3886 gimple_assign_set_rhs1 (stmt
, tem
);
3887 fold_stmt (gsi
, follow_single_use_edges
);
3892 /* Simplify an internal fn call using ranges if possible. */
3895 vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator
*gsi
,
3898 enum tree_code subcode
;
3899 bool is_ubsan
= false;
3901 switch (gimple_call_internal_fn (stmt
))
3903 case IFN_UBSAN_CHECK_ADD
:
3904 subcode
= PLUS_EXPR
;
3907 case IFN_UBSAN_CHECK_SUB
:
3908 subcode
= MINUS_EXPR
;
3911 case IFN_UBSAN_CHECK_MUL
:
3912 subcode
= MULT_EXPR
;
3915 case IFN_ADD_OVERFLOW
:
3916 subcode
= PLUS_EXPR
;
3918 case IFN_SUB_OVERFLOW
:
3919 subcode
= MINUS_EXPR
;
3921 case IFN_MUL_OVERFLOW
:
3922 subcode
= MULT_EXPR
;
3928 tree op0
= gimple_call_arg (stmt
, 0);
3929 tree op1
= gimple_call_arg (stmt
, 1);
3933 type
= TREE_TYPE (op0
);
3934 if (VECTOR_TYPE_P (type
))
3937 else if (gimple_call_lhs (stmt
) == NULL_TREE
)
3940 type
= TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt
)));
3941 if (!check_for_binary_op_overflow (subcode
, type
, op0
, op1
, &ovf
)
3942 || (is_ubsan
&& ovf
))
3946 location_t loc
= gimple_location (stmt
);
3948 g
= gimple_build_assign (gimple_call_lhs (stmt
), subcode
, op0
, op1
);
3951 int prec
= TYPE_PRECISION (type
);
3954 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
3955 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
3956 utype
= build_nonstandard_integer_type (prec
, 1);
3957 if (TREE_CODE (op0
) == INTEGER_CST
)
3958 op0
= fold_convert (utype
, op0
);
3959 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op0
)))
3961 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op0
);
3962 gimple_set_location (g
, loc
);
3963 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
3964 op0
= gimple_assign_lhs (g
);
3966 if (TREE_CODE (op1
) == INTEGER_CST
)
3967 op1
= fold_convert (utype
, op1
);
3968 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op1
)))
3970 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op1
);
3971 gimple_set_location (g
, loc
);
3972 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
3973 op1
= gimple_assign_lhs (g
);
3975 g
= gimple_build_assign (make_ssa_name (utype
), subcode
, op0
, op1
);
3976 gimple_set_location (g
, loc
);
3977 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
3980 g
= gimple_build_assign (make_ssa_name (type
), NOP_EXPR
,
3981 gimple_assign_lhs (g
));
3982 gimple_set_location (g
, loc
);
3983 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
3985 g
= gimple_build_assign (gimple_call_lhs (stmt
), COMPLEX_EXPR
,
3986 gimple_assign_lhs (g
),
3987 build_int_cst (type
, ovf
));
3989 gimple_set_location (g
, loc
);
3990 gsi_replace (gsi
, g
, false);
3994 /* Return true if VAR is a two-valued variable. Set a and b with the
3995 two-values when it is true. Return false otherwise. */
3998 vr_values::two_valued_val_range_p (tree var
, tree
*a
, tree
*b
)
4000 value_range
*vr
= get_value_range (var
);
4001 if ((vr
->type
!= VR_RANGE
4002 && vr
->type
!= VR_ANTI_RANGE
)
4003 || TREE_CODE (vr
->min
) != INTEGER_CST
4004 || TREE_CODE (vr
->max
) != INTEGER_CST
)
4007 if (vr
->type
== VR_RANGE
4008 && wi::to_wide (vr
->max
) - wi::to_wide (vr
->min
) == 1)
4015 /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
4016 if (vr
->type
== VR_ANTI_RANGE
4017 && (wi::to_wide (vr
->min
)
4018 - wi::to_wide (vrp_val_min (TREE_TYPE (var
)))) == 1
4019 && (wi::to_wide (vrp_val_max (TREE_TYPE (var
)))
4020 - wi::to_wide (vr
->max
)) == 1)
4022 *a
= vrp_val_min (TREE_TYPE (var
));
4023 *b
= vrp_val_max (TREE_TYPE (var
));
4030 /* Simplify STMT using ranges if possible. */
4033 vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator
*gsi
)
4035 gimple
*stmt
= gsi_stmt (*gsi
);
4036 if (is_gimple_assign (stmt
))
4038 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
4039 tree rhs1
= gimple_assign_rhs1 (stmt
);
4040 tree rhs2
= gimple_assign_rhs2 (stmt
);
4041 tree lhs
= gimple_assign_lhs (stmt
);
4042 tree val1
= NULL_TREE
, val2
= NULL_TREE
;
4043 use_operand_p use_p
;
4048 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4050 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4054 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4056 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4058 if (TREE_CODE_CLASS (rhs_code
) == tcc_binary
4059 && INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
4060 && ((TREE_CODE (rhs1
) == INTEGER_CST
4061 && TREE_CODE (rhs2
) == SSA_NAME
)
4062 || (TREE_CODE (rhs2
) == INTEGER_CST
4063 && TREE_CODE (rhs1
) == SSA_NAME
))
4064 && single_imm_use (lhs
, &use_p
, &use_stmt
)
4065 && gimple_code (use_stmt
) == GIMPLE_COND
)
4068 tree new_rhs1
= NULL_TREE
;
4069 tree new_rhs2
= NULL_TREE
;
4070 tree cmp_var
= NULL_TREE
;
4072 if (TREE_CODE (rhs2
) == SSA_NAME
4073 && two_valued_val_range_p (rhs2
, &val1
, &val2
))
4075 /* Optimize RHS1 OP [VAL1, VAL2]. */
4076 new_rhs1
= int_const_binop (rhs_code
, rhs1
, val1
);
4077 new_rhs2
= int_const_binop (rhs_code
, rhs1
, val2
);
4080 else if (TREE_CODE (rhs1
) == SSA_NAME
4081 && two_valued_val_range_p (rhs1
, &val1
, &val2
))
4083 /* Optimize [VAL1, VAL2] OP RHS2. */
4084 new_rhs1
= int_const_binop (rhs_code
, val1
, rhs2
);
4085 new_rhs2
= int_const_binop (rhs_code
, val2
, rhs2
);
4089 /* If we could not find two-vals or the optimzation is invalid as
4090 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4091 if (new_rhs1
&& new_rhs2
)
4093 tree cond
= build2 (EQ_EXPR
, boolean_type_node
, cmp_var
, val1
);
4094 gimple_assign_set_rhs_with_ops (gsi
,
4098 update_stmt (gsi_stmt (*gsi
));
4099 fold_stmt (gsi
, follow_single_use_edges
);
4108 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4109 if the RHS is zero or one, and the LHS are known to be boolean
4111 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4112 return simplify_truth_ops_using_ranges (gsi
, stmt
);
4115 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4116 and BIT_AND_EXPR respectively if the first operand is greater
4117 than zero and the second operand is an exact power of two.
4118 Also optimize TRUNC_MOD_EXPR away if the second operand is
4119 constant and the first operand already has the right value
4121 case TRUNC_DIV_EXPR
:
4122 case TRUNC_MOD_EXPR
:
4123 if ((TREE_CODE (rhs1
) == SSA_NAME
4124 || TREE_CODE (rhs1
) == INTEGER_CST
)
4125 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4126 return simplify_div_or_mod_using_ranges (gsi
, stmt
);
4129 /* Transform ABS (X) into X or -X as appropriate. */
4131 if (TREE_CODE (rhs1
) == SSA_NAME
4132 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4133 return simplify_abs_using_ranges (gsi
, stmt
);
4138 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4139 if all the bits being cleared are already cleared or
4140 all the bits being set are already set. */
4141 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4142 return simplify_bit_ops_using_ranges (gsi
, stmt
);
4146 if (TREE_CODE (rhs1
) == SSA_NAME
4147 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4148 return simplify_conversion_using_ranges (gsi
, stmt
);
4152 if (TREE_CODE (rhs1
) == SSA_NAME
4153 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4154 return simplify_float_conversion_using_ranges (gsi
, stmt
);
4159 return simplify_min_or_max_using_ranges (gsi
, stmt
);
4165 else if (gimple_code (stmt
) == GIMPLE_COND
)
4166 return simplify_cond_using_ranges_1 (as_a
<gcond
*> (stmt
));
4167 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
4168 return simplify_switch_using_ranges (as_a
<gswitch
*> (stmt
));
4169 else if (is_gimple_call (stmt
)
4170 && gimple_call_internal_p (stmt
))
4171 return simplify_internal_call_using_ranges (gsi
, stmt
);
4177 vr_values::set_vr_value (tree var
, value_range
*vr
)
4179 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4181 vr_value
[SSA_NAME_VERSION (var
)] = vr
;