1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2018 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 gcall
*call_stmt
= as_a
<gcall
*> (stmt
);
317 return (gimple_call_nonnull_result_p (call_stmt
)
318 || gimple_call_nonnull_arg (call_stmt
));
324 /* Like tree_expr_nonzero_p, but this function uses value ranges
328 vr_values::vrp_stmt_computes_nonzero (gimple
*stmt
)
330 if (gimple_stmt_nonzero_p (stmt
))
333 /* If we have an expression of the form &X->a, then the expression
334 is nonnull if X is nonnull. */
335 if (is_gimple_assign (stmt
)
336 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
338 tree expr
= gimple_assign_rhs1 (stmt
);
339 tree base
= get_base_address (TREE_OPERAND (expr
, 0));
341 if (base
!= NULL_TREE
342 && TREE_CODE (base
) == MEM_REF
343 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
345 value_range
*vr
= get_value_range (TREE_OPERAND (base
, 0));
346 if (range_is_nonnull (vr
))
354 /* Returns true if EXPR is a valid value (as expected by compare_values) --
355 a gimple invariant, or SSA_NAME +- CST. */
358 valid_value_p (tree expr
)
360 if (TREE_CODE (expr
) == SSA_NAME
)
363 if (TREE_CODE (expr
) == PLUS_EXPR
364 || TREE_CODE (expr
) == MINUS_EXPR
)
365 return (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
366 && TREE_CODE (TREE_OPERAND (expr
, 1)) == INTEGER_CST
);
368 return is_gimple_min_invariant (expr
);
371 /* If OP has a value range with a single constant value return that,
372 otherwise return NULL_TREE. This returns OP itself if OP is a
376 vr_values::op_with_constant_singleton_value_range (tree op
)
378 if (is_gimple_min_invariant (op
))
381 if (TREE_CODE (op
) != SSA_NAME
)
384 return value_range_constant_singleton (get_value_range (op
));
387 /* Return true if op is in a boolean [0, 1] value-range. */
390 vr_values::op_with_boolean_value_range_p (tree op
)
394 if (TYPE_PRECISION (TREE_TYPE (op
)) == 1)
397 if (integer_zerop (op
)
398 || integer_onep (op
))
401 if (TREE_CODE (op
) != SSA_NAME
)
404 vr
= get_value_range (op
);
405 return (vr
->type
== VR_RANGE
406 && integer_zerop (vr
->min
)
407 && integer_onep (vr
->max
));
410 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
411 true and store it in *VR_P. */
414 vr_values::extract_range_for_var_from_comparison_expr (tree var
,
415 enum tree_code cond_code
,
420 value_range
*limit_vr
;
421 type
= TREE_TYPE (var
);
423 /* For pointer arithmetic, we only keep track of pointer equality
424 and inequality. If we arrive here with unfolded conditions like
425 _1 > _1 do not derive anything. */
426 if ((POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
429 set_value_range_to_varying (vr_p
);
433 /* If LIMIT is another SSA name and LIMIT has a range of its own,
434 try to use LIMIT's range to avoid creating symbolic ranges
436 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
438 /* LIMIT's range is only interesting if it has any useful information. */
440 || limit_vr
->type
== VR_UNDEFINED
441 || limit_vr
->type
== VR_VARYING
442 || (symbolic_range_p (limit_vr
)
443 && ! (limit_vr
->type
== VR_RANGE
444 && (limit_vr
->min
== limit_vr
->max
445 || operand_equal_p (limit_vr
->min
, limit_vr
->max
, 0)))))
448 /* Initially, the new range has the same set of equivalences of
449 VAR's range. This will be revised before returning the final
450 value. Since assertions may be chained via mutually exclusive
451 predicates, we will need to trim the set of equivalences before
453 gcc_assert (vr_p
->equiv
== NULL
);
454 add_equivalence (&vr_p
->equiv
, var
);
456 /* Extract a new range based on the asserted comparison for VAR and
457 LIMIT's value range. Notice that if LIMIT has an anti-range, we
458 will only use it for equality comparisons (EQ_EXPR). For any
459 other kind of assertion, we cannot derive a range from LIMIT's
460 anti-range that can be used to describe the new range. For
461 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
462 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
463 no single range for x_2 that could describe LE_EXPR, so we might
464 as well build the range [b_4, +INF] for it.
465 One special case we handle is extracting a range from a
466 range test encoded as (unsigned)var + CST <= limit. */
467 if (TREE_CODE (op
) == NOP_EXPR
468 || TREE_CODE (op
) == PLUS_EXPR
)
470 if (TREE_CODE (op
) == PLUS_EXPR
)
472 min
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (TREE_OPERAND (op
, 1)),
473 TREE_OPERAND (op
, 1));
474 max
= int_const_binop (PLUS_EXPR
, limit
, min
);
475 op
= TREE_OPERAND (op
, 0);
479 min
= build_int_cst (TREE_TYPE (var
), 0);
483 /* Make sure to not set TREE_OVERFLOW on the final type
484 conversion. We are willingly interpreting large positive
485 unsigned values as negative signed values here. */
486 min
= force_fit_type (TREE_TYPE (var
), wi::to_widest (min
), 0, false);
487 max
= force_fit_type (TREE_TYPE (var
), wi::to_widest (max
), 0, false);
489 /* We can transform a max, min range to an anti-range or
490 vice-versa. Use set_and_canonicalize_value_range which does
492 if (cond_code
== LE_EXPR
)
493 set_and_canonicalize_value_range (vr_p
, VR_RANGE
,
494 min
, max
, vr_p
->equiv
);
495 else if (cond_code
== GT_EXPR
)
496 set_and_canonicalize_value_range (vr_p
, VR_ANTI_RANGE
,
497 min
, max
, vr_p
->equiv
);
501 else if (cond_code
== EQ_EXPR
)
503 enum value_range_type range_type
;
507 range_type
= limit_vr
->type
;
513 range_type
= VR_RANGE
;
518 set_value_range (vr_p
, range_type
, min
, max
, vr_p
->equiv
);
520 /* When asserting the equality VAR == LIMIT and LIMIT is another
521 SSA name, the new range will also inherit the equivalence set
523 if (TREE_CODE (limit
) == SSA_NAME
)
524 add_equivalence (&vr_p
->equiv
, limit
);
526 else if (cond_code
== NE_EXPR
)
528 /* As described above, when LIMIT's range is an anti-range and
529 this assertion is an inequality (NE_EXPR), then we cannot
530 derive anything from the anti-range. For instance, if
531 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
532 not imply that VAR's range is [0, 0]. So, in the case of
533 anti-ranges, we just assert the inequality using LIMIT and
536 If LIMIT_VR is a range, we can only use it to build a new
537 anti-range if LIMIT_VR is a single-valued range. For
538 instance, if LIMIT_VR is [0, 1], the predicate
539 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
540 Rather, it means that for value 0 VAR should be ~[0, 0]
541 and for value 1, VAR should be ~[1, 1]. We cannot
542 represent these ranges.
544 The only situation in which we can build a valid
545 anti-range is when LIMIT_VR is a single-valued range
546 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
547 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
549 && limit_vr
->type
== VR_RANGE
550 && compare_values (limit_vr
->min
, limit_vr
->max
) == 0)
557 /* In any other case, we cannot use LIMIT's range to build a
562 /* If MIN and MAX cover the whole range for their type, then
563 just use the original LIMIT. */
564 if (INTEGRAL_TYPE_P (type
)
565 && vrp_val_is_min (min
)
566 && vrp_val_is_max (max
))
569 set_and_canonicalize_value_range (vr_p
, VR_ANTI_RANGE
,
570 min
, max
, vr_p
->equiv
);
572 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
574 min
= TYPE_MIN_VALUE (type
);
576 if (limit_vr
== NULL
|| limit_vr
->type
== VR_ANTI_RANGE
)
580 /* If LIMIT_VR is of the form [N1, N2], we need to build the
581 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
586 /* If the maximum value forces us to be out of bounds, simply punt.
587 It would be pointless to try and do anything more since this
588 all should be optimized away above us. */
589 if (cond_code
== LT_EXPR
590 && compare_values (max
, min
) == 0)
591 set_value_range_to_varying (vr_p
);
594 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
595 if (cond_code
== LT_EXPR
)
597 if (TYPE_PRECISION (TREE_TYPE (max
)) == 1
598 && !TYPE_UNSIGNED (TREE_TYPE (max
)))
599 max
= fold_build2 (PLUS_EXPR
, TREE_TYPE (max
), max
,
600 build_int_cst (TREE_TYPE (max
), -1));
602 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max
), max
,
603 build_int_cst (TREE_TYPE (max
), 1));
604 /* Signal to compare_values_warnv this expr doesn't overflow. */
606 TREE_NO_WARNING (max
) = 1;
609 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
612 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
614 max
= TYPE_MAX_VALUE (type
);
616 if (limit_vr
== NULL
|| limit_vr
->type
== VR_ANTI_RANGE
)
620 /* If LIMIT_VR is of the form [N1, N2], we need to build the
621 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
626 /* If the minimum value forces us to be out of bounds, simply punt.
627 It would be pointless to try and do anything more since this
628 all should be optimized away above us. */
629 if (cond_code
== GT_EXPR
630 && compare_values (min
, max
) == 0)
631 set_value_range_to_varying (vr_p
);
634 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
635 if (cond_code
== GT_EXPR
)
637 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
638 && !TYPE_UNSIGNED (TREE_TYPE (min
)))
639 min
= fold_build2 (MINUS_EXPR
, TREE_TYPE (min
), min
,
640 build_int_cst (TREE_TYPE (min
), -1));
642 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min
), min
,
643 build_int_cst (TREE_TYPE (min
), 1));
644 /* Signal to compare_values_warnv this expr doesn't overflow. */
646 TREE_NO_WARNING (min
) = 1;
649 set_value_range (vr_p
, VR_RANGE
, min
, max
, vr_p
->equiv
);
655 /* Finally intersect the new range with what we already know about var. */
656 vrp_intersect_ranges (vr_p
, get_value_range (var
));
659 /* Extract value range information from an ASSERT_EXPR EXPR and store
663 vr_values::extract_range_from_assert (value_range
*vr_p
, tree expr
)
665 tree var
= ASSERT_EXPR_VAR (expr
);
666 tree cond
= ASSERT_EXPR_COND (expr
);
668 enum tree_code cond_code
;
669 gcc_assert (COMPARISON_CLASS_P (cond
));
671 /* Find VAR in the ASSERT_EXPR conditional. */
672 if (var
== TREE_OPERAND (cond
, 0)
673 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PLUS_EXPR
674 || TREE_CODE (TREE_OPERAND (cond
, 0)) == NOP_EXPR
)
676 /* If the predicate is of the form VAR COMP LIMIT, then we just
677 take LIMIT from the RHS and use the same comparison code. */
678 cond_code
= TREE_CODE (cond
);
679 limit
= TREE_OPERAND (cond
, 1);
680 op
= TREE_OPERAND (cond
, 0);
684 /* If the predicate is of the form LIMIT COMP VAR, then we need
685 to flip around the comparison code to create the proper range
687 cond_code
= swap_tree_comparison (TREE_CODE (cond
));
688 limit
= TREE_OPERAND (cond
, 0);
689 op
= TREE_OPERAND (cond
, 1);
691 extract_range_for_var_from_comparison_expr (var
, cond_code
, op
,
695 /* Extract range information from SSA name VAR and store it in VR. If
696 VAR has an interesting range, use it. Otherwise, create the
697 range [VAR, VAR] and return it. This is useful in situations where
698 we may have conditionals testing values of VARYING names. For
705 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
709 vr_values::extract_range_from_ssa_name (value_range
*vr
, tree var
)
711 value_range
*var_vr
= get_value_range (var
);
713 if (var_vr
->type
!= VR_VARYING
)
714 copy_value_range (vr
, var_vr
);
716 set_value_range (vr
, VR_RANGE
, var
, var
, NULL
);
718 add_equivalence (&vr
->equiv
, var
);
721 /* Extract range information from a binary expression OP0 CODE OP1 based on
722 the ranges of each of its operands with resulting type EXPR_TYPE.
723 The resulting range is stored in *VR. */
726 vr_values::extract_range_from_binary_expr (value_range
*vr
,
728 tree expr_type
, tree op0
, tree op1
)
730 value_range vr0
= VR_INITIALIZER
;
731 value_range vr1
= VR_INITIALIZER
;
733 /* Get value ranges for each operand. For constant operands, create
734 a new value range with the operand to simplify processing. */
735 if (TREE_CODE (op0
) == SSA_NAME
)
736 vr0
= *(get_value_range (op0
));
737 else if (is_gimple_min_invariant (op0
))
738 set_value_range_to_value (&vr0
, op0
, NULL
);
740 set_value_range_to_varying (&vr0
);
742 if (TREE_CODE (op1
) == SSA_NAME
)
743 vr1
= *(get_value_range (op1
));
744 else if (is_gimple_min_invariant (op1
))
745 set_value_range_to_value (&vr1
, op1
, NULL
);
747 set_value_range_to_varying (&vr1
);
749 /* If one argument is varying, we can sometimes still deduce a
750 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
751 if (INTEGRAL_TYPE_P (TREE_TYPE (op0
))
752 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0
)))
754 if (vr0
.type
== VR_VARYING
&& vr1
.type
!= VR_VARYING
)
757 vr0
.min
= vrp_val_min (expr_type
);
758 vr0
.max
= vrp_val_max (expr_type
);
760 else if (vr1
.type
== VR_VARYING
&& vr0
.type
!= VR_VARYING
)
763 vr1
.min
= vrp_val_min (expr_type
);
764 vr1
.max
= vrp_val_max (expr_type
);
768 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &vr0
, &vr1
);
770 /* Set value_range for n in following sequence:
771 def = __builtin_memchr (arg, 0, sz)
773 Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
775 if (vr
->type
== VR_VARYING
776 && code
== POINTER_DIFF_EXPR
777 && TREE_CODE (op0
) == SSA_NAME
778 && TREE_CODE (op1
) == SSA_NAME
)
780 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
781 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
782 gcall
*call_stmt
= NULL
;
784 if (TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
785 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
786 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
787 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
788 && (call_stmt
= dyn_cast
<gcall
*>(SSA_NAME_DEF_STMT (op0
)))
789 && gimple_call_builtin_p (call_stmt
, BUILT_IN_MEMCHR
)
790 && operand_equal_p (op0
, gimple_call_lhs (call_stmt
), 0)
791 && operand_equal_p (op1
, gimple_call_arg (call_stmt
, 0), 0)
792 && integer_zerop (gimple_call_arg (call_stmt
, 1)))
794 tree max
= vrp_val_max (ptrdiff_type_node
);
795 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
796 tree range_min
= build_zero_cst (expr_type
);
797 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
798 set_value_range (vr
, VR_RANGE
, range_min
, range_max
, NULL
);
803 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
804 and based on the other operand, for example if it was deduced from a
805 symbolic comparison. When a bound of the range of the first operand
806 is invariant, we set the corresponding bound of the new range to INF
807 in order to avoid recursing on the range of the second operand. */
808 if (vr
->type
== VR_VARYING
809 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
810 && TREE_CODE (op1
) == SSA_NAME
811 && vr0
.type
== VR_RANGE
812 && symbolic_range_based_on_p (&vr0
, op1
))
814 const bool minus_p
= (code
== MINUS_EXPR
);
815 value_range n_vr1
= VR_INITIALIZER
;
817 /* Try with VR0 and [-INF, OP1]. */
818 if (is_gimple_min_invariant (minus_p
? vr0
.max
: vr0
.min
))
819 set_value_range (&n_vr1
, VR_RANGE
, vrp_val_min (expr_type
), op1
, NULL
);
821 /* Try with VR0 and [OP1, +INF]. */
822 else if (is_gimple_min_invariant (minus_p
? vr0
.min
: vr0
.max
))
823 set_value_range (&n_vr1
, VR_RANGE
, op1
, vrp_val_max (expr_type
), NULL
);
825 /* Try with VR0 and [OP1, OP1]. */
827 set_value_range (&n_vr1
, VR_RANGE
, op1
, op1
, NULL
);
829 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &vr0
, &n_vr1
);
832 if (vr
->type
== VR_VARYING
833 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
834 && TREE_CODE (op0
) == SSA_NAME
835 && vr1
.type
== VR_RANGE
836 && symbolic_range_based_on_p (&vr1
, op0
))
838 const bool minus_p
= (code
== MINUS_EXPR
);
839 value_range n_vr0
= VR_INITIALIZER
;
841 /* Try with [-INF, OP0] and VR1. */
842 if (is_gimple_min_invariant (minus_p
? vr1
.max
: vr1
.min
))
843 set_value_range (&n_vr0
, VR_RANGE
, vrp_val_min (expr_type
), op0
, NULL
);
845 /* Try with [OP0, +INF] and VR1. */
846 else if (is_gimple_min_invariant (minus_p
? vr1
.min
: vr1
.max
))
847 set_value_range (&n_vr0
, VR_RANGE
, op0
, vrp_val_max (expr_type
), NULL
);
849 /* Try with [OP0, OP0] and VR1. */
851 set_value_range (&n_vr0
, VR_RANGE
, op0
, op0
, NULL
);
853 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &n_vr0
, &vr1
);
856 /* If we didn't derive a range for MINUS_EXPR, and
857 op1's range is ~[op0,op0] or vice-versa, then we
858 can derive a non-null range. This happens often for
859 pointer subtraction. */
860 if (vr
->type
== VR_VARYING
861 && (code
== MINUS_EXPR
|| code
== POINTER_DIFF_EXPR
)
862 && TREE_CODE (op0
) == SSA_NAME
863 && ((vr0
.type
== VR_ANTI_RANGE
865 && vr0
.min
== vr0
.max
)
866 || (vr1
.type
== VR_ANTI_RANGE
868 && vr1
.min
== vr1
.max
)))
869 set_value_range_to_nonnull (vr
, expr_type
);
872 /* Extract range information from a unary expression CODE OP0 based on
873 the range of its operand with resulting type TYPE.
874 The resulting range is stored in *VR. */
877 vr_values::extract_range_from_unary_expr (value_range
*vr
, enum tree_code code
,
880 value_range vr0
= VR_INITIALIZER
;
882 /* Get value ranges for the operand. For constant operands, create
883 a new value range with the operand to simplify processing. */
884 if (TREE_CODE (op0
) == SSA_NAME
)
885 vr0
= *(get_value_range (op0
));
886 else if (is_gimple_min_invariant (op0
))
887 set_value_range_to_value (&vr0
, op0
, NULL
);
889 set_value_range_to_varying (&vr0
);
891 ::extract_range_from_unary_expr (vr
, code
, type
, &vr0
, TREE_TYPE (op0
));
895 /* Extract range information from a conditional expression STMT based on
896 the ranges of each of its operands and the expression code. */
899 vr_values::extract_range_from_cond_expr (value_range
*vr
, gassign
*stmt
)
902 value_range vr0
= VR_INITIALIZER
;
903 value_range vr1
= VR_INITIALIZER
;
905 /* Get value ranges for each operand. For constant operands, create
906 a new value range with the operand to simplify processing. */
907 op0
= gimple_assign_rhs2 (stmt
);
908 if (TREE_CODE (op0
) == SSA_NAME
)
909 vr0
= *(get_value_range (op0
));
910 else if (is_gimple_min_invariant (op0
))
911 set_value_range_to_value (&vr0
, op0
, NULL
);
913 set_value_range_to_varying (&vr0
);
915 op1
= gimple_assign_rhs3 (stmt
);
916 if (TREE_CODE (op1
) == SSA_NAME
)
917 vr1
= *(get_value_range (op1
));
918 else if (is_gimple_min_invariant (op1
))
919 set_value_range_to_value (&vr1
, op1
, NULL
);
921 set_value_range_to_varying (&vr1
);
923 /* The resulting value range is the union of the operand ranges */
924 copy_value_range (vr
, &vr0
);
929 /* Extract range information from a comparison expression EXPR based
930 on the range of its operand and the expression code. */
933 vr_values::extract_range_from_comparison (value_range
*vr
, enum tree_code code
,
934 tree type
, tree op0
, tree op1
)
939 val
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, false, &sop
,
943 /* Since this expression was found on the RHS of an assignment,
944 its type may be different from _Bool. Convert VAL to EXPR's
946 val
= fold_convert (type
, val
);
947 if (is_gimple_min_invariant (val
))
948 set_value_range_to_value (vr
, val
, vr
->equiv
);
950 set_value_range (vr
, VR_RANGE
, val
, val
, vr
->equiv
);
953 /* The result of a comparison is always true or false. */
954 set_value_range_to_truthvalue (vr
, type
);
957 /* Helper function for simplify_internal_call_using_ranges and
958 extract_range_basic. Return true if OP0 SUBCODE OP1 for
959 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
960 always overflow. Set *OVF to true if it is known to always
964 vr_values::check_for_binary_op_overflow (enum tree_code subcode
, tree type
,
965 tree op0
, tree op1
, bool *ovf
)
967 value_range vr0
= VR_INITIALIZER
;
968 value_range vr1
= VR_INITIALIZER
;
969 if (TREE_CODE (op0
) == SSA_NAME
)
970 vr0
= *get_value_range (op0
);
971 else if (TREE_CODE (op0
) == INTEGER_CST
)
972 set_value_range_to_value (&vr0
, op0
, NULL
);
974 set_value_range_to_varying (&vr0
);
976 if (TREE_CODE (op1
) == SSA_NAME
)
977 vr1
= *get_value_range (op1
);
978 else if (TREE_CODE (op1
) == INTEGER_CST
)
979 set_value_range_to_value (&vr1
, op1
, NULL
);
981 set_value_range_to_varying (&vr1
);
983 if (!range_int_cst_p (&vr0
)
984 || TREE_OVERFLOW (vr0
.min
)
985 || TREE_OVERFLOW (vr0
.max
))
987 vr0
.min
= vrp_val_min (TREE_TYPE (op0
));
988 vr0
.max
= vrp_val_max (TREE_TYPE (op0
));
990 if (!range_int_cst_p (&vr1
)
991 || TREE_OVERFLOW (vr1
.min
)
992 || TREE_OVERFLOW (vr1
.max
))
994 vr1
.min
= vrp_val_min (TREE_TYPE (op1
));
995 vr1
.max
= vrp_val_max (TREE_TYPE (op1
));
997 *ovf
= arith_overflowed_p (subcode
, type
, vr0
.min
,
998 subcode
== MINUS_EXPR
? vr1
.max
: vr1
.min
);
999 if (arith_overflowed_p (subcode
, type
, vr0
.max
,
1000 subcode
== MINUS_EXPR
? vr1
.min
: vr1
.max
) != *ovf
)
1002 if (subcode
== MULT_EXPR
)
1004 if (arith_overflowed_p (subcode
, type
, vr0
.min
, vr1
.max
) != *ovf
1005 || arith_overflowed_p (subcode
, type
, vr0
.max
, vr1
.min
) != *ovf
)
1010 /* So far we found that there is an overflow on the boundaries.
1011 That doesn't prove that there is an overflow even for all values
1012 in between the boundaries. For that compute widest_int range
1013 of the result and see if it doesn't overlap the range of
1015 widest_int wmin
, wmax
;
1018 w
[0] = wi::to_widest (vr0
.min
);
1019 w
[1] = wi::to_widest (vr0
.max
);
1020 w
[2] = wi::to_widest (vr1
.min
);
1021 w
[3] = wi::to_widest (vr1
.max
);
1022 for (i
= 0; i
< 4; i
++)
1028 wt
= wi::add (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1031 wt
= wi::sub (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1034 wt
= wi::mul (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1046 wmin
= wi::smin (wmin
, wt
);
1047 wmax
= wi::smax (wmax
, wt
);
1050 /* The result of op0 CODE op1 is known to be in range
1052 widest_int wtmin
= wi::to_widest (vrp_val_min (type
));
1053 widest_int wtmax
= wi::to_widest (vrp_val_max (type
));
1054 /* If all values in [wmin, wmax] are smaller than
1055 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1056 the arithmetic operation will always overflow. */
1057 if (wmax
< wtmin
|| wmin
> wtmax
)
1064 /* Try to derive a nonnegative or nonzero range out of STMT relying
1065 primarily on generic routines in fold in conjunction with range data.
1066 Store the result in *VR */
1069 vr_values::extract_range_basic (value_range
*vr
, gimple
*stmt
)
1072 tree type
= gimple_expr_type (stmt
);
1074 if (is_gimple_call (stmt
))
1077 int mini
, maxi
, zerov
= 0, prec
;
1078 enum tree_code subcode
= ERROR_MARK
;
1079 combined_fn cfn
= gimple_call_combined_fn (stmt
);
1080 scalar_int_mode mode
;
1084 case CFN_BUILT_IN_CONSTANT_P
:
1085 /* If the call is __builtin_constant_p and the argument is a
1086 function parameter resolve it to false. This avoids bogus
1087 array bound warnings.
1088 ??? We could do this as early as inlining is finished. */
1089 arg
= gimple_call_arg (stmt
, 0);
1090 if (TREE_CODE (arg
) == SSA_NAME
1091 && SSA_NAME_IS_DEFAULT_DEF (arg
)
1092 && TREE_CODE (SSA_NAME_VAR (arg
)) == PARM_DECL
1093 && cfun
->after_inlining
)
1095 set_value_range_to_null (vr
, type
);
1099 /* Both __builtin_ffs* and __builtin_popcount return
1103 arg
= gimple_call_arg (stmt
, 0);
1104 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1107 if (TREE_CODE (arg
) == SSA_NAME
)
1109 value_range
*vr0
= get_value_range (arg
);
1110 /* If arg is non-zero, then ffs or popcount
1112 if ((vr0
->type
== VR_RANGE
1113 && range_includes_zero_p (vr0
->min
, vr0
->max
) == 0)
1114 || (vr0
->type
== VR_ANTI_RANGE
1115 && range_includes_zero_p (vr0
->min
, vr0
->max
) == 1))
1117 /* If some high bits are known to be zero,
1118 we can decrease the maximum. */
1119 if (vr0
->type
== VR_RANGE
1120 && TREE_CODE (vr0
->max
) == INTEGER_CST
1121 && !operand_less_p (vr0
->min
,
1122 build_zero_cst (TREE_TYPE (vr0
->min
))))
1123 maxi
= tree_floor_log2 (vr0
->max
) + 1;
1126 /* __builtin_parity* returns [0, 1]. */
1131 /* __builtin_c[lt]z* return [0, prec-1], except for
1132 when the argument is 0, but that is undefined behavior.
1133 On many targets where the CLZ RTL or optab value is defined
1134 for 0 the value is prec, so include that in the range
1137 arg
= gimple_call_arg (stmt
, 0);
1138 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1141 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1142 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
1143 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
)
1144 /* Handle only the single common value. */
1146 /* Magic value to give up, unless vr0 proves
1149 if (TREE_CODE (arg
) == SSA_NAME
)
1151 value_range
*vr0
= get_value_range (arg
);
1152 /* From clz of VR_RANGE minimum we can compute
1154 if (vr0
->type
== VR_RANGE
1155 && TREE_CODE (vr0
->min
) == INTEGER_CST
)
1157 maxi
= prec
- 1 - tree_floor_log2 (vr0
->min
);
1161 else if (vr0
->type
== VR_ANTI_RANGE
1162 && integer_zerop (vr0
->min
))
1169 /* From clz of VR_RANGE maximum we can compute
1171 if (vr0
->type
== VR_RANGE
1172 && TREE_CODE (vr0
->max
) == INTEGER_CST
)
1174 mini
= prec
- 1 - tree_floor_log2 (vr0
->max
);
1182 /* __builtin_ctz* return [0, prec-1], except for
1183 when the argument is 0, but that is undefined behavior.
1184 If there is a ctz optab for this mode and
1185 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1186 otherwise just assume 0 won't be seen. */
1188 arg
= gimple_call_arg (stmt
, 0);
1189 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1192 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1193 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1194 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
))
1196 /* Handle only the two common values. */
1199 else if (zerov
== prec
)
1202 /* Magic value to give up, unless vr0 proves
1206 if (TREE_CODE (arg
) == SSA_NAME
)
1208 value_range
*vr0
= get_value_range (arg
);
1209 /* If arg is non-zero, then use [0, prec - 1]. */
1210 if ((vr0
->type
== VR_RANGE
1211 && integer_nonzerop (vr0
->min
))
1212 || (vr0
->type
== VR_ANTI_RANGE
1213 && integer_zerop (vr0
->min
)))
1218 /* If some high bits are known to be zero,
1219 we can decrease the result maximum. */
1220 if (vr0
->type
== VR_RANGE
1221 && TREE_CODE (vr0
->max
) == INTEGER_CST
)
1223 maxi
= tree_floor_log2 (vr0
->max
);
1224 /* For vr0 [0, 0] give up. */
1232 /* __builtin_clrsb* returns [0, prec-1]. */
1234 arg
= gimple_call_arg (stmt
, 0);
1235 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1240 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, mini
),
1241 build_int_cst (type
, maxi
), NULL
);
1243 case CFN_UBSAN_CHECK_ADD
:
1244 subcode
= PLUS_EXPR
;
1246 case CFN_UBSAN_CHECK_SUB
:
1247 subcode
= MINUS_EXPR
;
1249 case CFN_UBSAN_CHECK_MUL
:
1250 subcode
= MULT_EXPR
;
1252 case CFN_GOACC_DIM_SIZE
:
1253 case CFN_GOACC_DIM_POS
:
1254 /* Optimizing these two internal functions helps the loop
1255 optimizer eliminate outer comparisons. Size is [1,N]
1256 and pos is [0,N-1]. */
1258 bool is_pos
= cfn
== CFN_GOACC_DIM_POS
;
1259 int axis
= oacc_get_ifn_dim_arg (stmt
);
1260 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1263 /* If it's dynamic, the backend might know a hardware
1265 size
= targetm
.goacc
.dim_limit (axis
);
1267 tree type
= TREE_TYPE (gimple_call_lhs (stmt
));
1268 set_value_range (vr
, VR_RANGE
,
1269 build_int_cst (type
, is_pos
? 0 : 1),
1270 size
? build_int_cst (type
, size
- is_pos
)
1271 : vrp_val_max (type
), NULL
);
1274 case CFN_BUILT_IN_STRLEN
:
1275 if (tree lhs
= gimple_call_lhs (stmt
))
1276 if (ptrdiff_type_node
1277 && (TYPE_PRECISION (ptrdiff_type_node
)
1278 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1280 tree type
= TREE_TYPE (lhs
);
1281 tree max
= vrp_val_max (ptrdiff_type_node
);
1282 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1283 tree range_min
= build_zero_cst (type
);
1284 tree range_max
= wide_int_to_tree (type
, wmax
- 1);
1285 set_value_range (vr
, VR_RANGE
, range_min
, range_max
, NULL
);
1292 if (subcode
!= ERROR_MARK
)
1294 bool saved_flag_wrapv
= flag_wrapv
;
1295 /* Pretend the arithmetics is wrapping. If there is
1296 any overflow, we'll complain, but will actually do
1297 wrapping operation. */
1299 extract_range_from_binary_expr (vr
, subcode
, type
,
1300 gimple_call_arg (stmt
, 0),
1301 gimple_call_arg (stmt
, 1));
1302 flag_wrapv
= saved_flag_wrapv
;
1304 /* If for both arguments vrp_valueize returned non-NULL,
1305 this should have been already folded and if not, it
1306 wasn't folded because of overflow. Avoid removing the
1307 UBSAN_CHECK_* calls in that case. */
1308 if (vr
->type
== VR_RANGE
1309 && (vr
->min
== vr
->max
1310 || operand_equal_p (vr
->min
, vr
->max
, 0)))
1311 set_value_range_to_varying (vr
);
1315 /* Handle extraction of the two results (result of arithmetics and
1316 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1317 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1318 else if (is_gimple_assign (stmt
)
1319 && (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
1320 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
)
1321 && INTEGRAL_TYPE_P (type
))
1323 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1324 tree op
= gimple_assign_rhs1 (stmt
);
1325 if (TREE_CODE (op
) == code
&& TREE_CODE (TREE_OPERAND (op
, 0)) == SSA_NAME
)
1327 gimple
*g
= SSA_NAME_DEF_STMT (TREE_OPERAND (op
, 0));
1328 if (is_gimple_call (g
) && gimple_call_internal_p (g
))
1330 enum tree_code subcode
= ERROR_MARK
;
1331 switch (gimple_call_internal_fn (g
))
1333 case IFN_ADD_OVERFLOW
:
1334 subcode
= PLUS_EXPR
;
1336 case IFN_SUB_OVERFLOW
:
1337 subcode
= MINUS_EXPR
;
1339 case IFN_MUL_OVERFLOW
:
1340 subcode
= MULT_EXPR
;
1342 case IFN_ATOMIC_COMPARE_EXCHANGE
:
1343 if (code
== IMAGPART_EXPR
)
1345 /* This is the boolean return value whether compare and
1346 exchange changed anything or not. */
1347 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, 0),
1348 build_int_cst (type
, 1), NULL
);
1355 if (subcode
!= ERROR_MARK
)
1357 tree op0
= gimple_call_arg (g
, 0);
1358 tree op1
= gimple_call_arg (g
, 1);
1359 if (code
== IMAGPART_EXPR
)
1362 if (check_for_binary_op_overflow (subcode
, type
,
1364 set_value_range_to_value (vr
,
1365 build_int_cst (type
, ovf
),
1367 else if (TYPE_PRECISION (type
) == 1
1368 && !TYPE_UNSIGNED (type
))
1369 set_value_range_to_varying (vr
);
1371 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, 0),
1372 build_int_cst (type
, 1), NULL
);
1374 else if (types_compatible_p (type
, TREE_TYPE (op0
))
1375 && types_compatible_p (type
, TREE_TYPE (op1
)))
1377 bool saved_flag_wrapv
= flag_wrapv
;
1378 /* Pretend the arithmetics is wrapping. If there is
1379 any overflow, IMAGPART_EXPR will be set. */
1381 extract_range_from_binary_expr (vr
, subcode
, type
,
1383 flag_wrapv
= saved_flag_wrapv
;
1387 value_range vr0
= VR_INITIALIZER
;
1388 value_range vr1
= VR_INITIALIZER
;
1389 bool saved_flag_wrapv
= flag_wrapv
;
1390 /* Pretend the arithmetics is wrapping. If there is
1391 any overflow, IMAGPART_EXPR will be set. */
1393 extract_range_from_unary_expr (&vr0
, NOP_EXPR
,
1395 extract_range_from_unary_expr (&vr1
, NOP_EXPR
,
1397 extract_range_from_binary_expr_1 (vr
, subcode
, type
,
1399 flag_wrapv
= saved_flag_wrapv
;
1406 if (INTEGRAL_TYPE_P (type
)
1407 && gimple_stmt_nonnegative_warnv_p (stmt
, &sop
))
1408 set_value_range_to_nonnegative (vr
, type
);
1409 else if (vrp_stmt_computes_nonzero (stmt
))
1410 set_value_range_to_nonnull (vr
, type
);
1412 set_value_range_to_varying (vr
);
1416 /* Try to compute a useful range out of assignment STMT and store it
1420 vr_values::extract_range_from_assignment (value_range
*vr
, gassign
*stmt
)
1422 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1424 if (code
== ASSERT_EXPR
)
1425 extract_range_from_assert (vr
, gimple_assign_rhs1 (stmt
));
1426 else if (code
== SSA_NAME
)
1427 extract_range_from_ssa_name (vr
, gimple_assign_rhs1 (stmt
));
1428 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
1429 extract_range_from_binary_expr (vr
, gimple_assign_rhs_code (stmt
),
1430 gimple_expr_type (stmt
),
1431 gimple_assign_rhs1 (stmt
),
1432 gimple_assign_rhs2 (stmt
));
1433 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1434 extract_range_from_unary_expr (vr
, gimple_assign_rhs_code (stmt
),
1435 gimple_expr_type (stmt
),
1436 gimple_assign_rhs1 (stmt
));
1437 else if (code
== COND_EXPR
)
1438 extract_range_from_cond_expr (vr
, stmt
);
1439 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1440 extract_range_from_comparison (vr
, gimple_assign_rhs_code (stmt
),
1441 gimple_expr_type (stmt
),
1442 gimple_assign_rhs1 (stmt
),
1443 gimple_assign_rhs2 (stmt
));
1444 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1445 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1446 set_value_range_to_value (vr
, gimple_assign_rhs1 (stmt
), NULL
);
1448 set_value_range_to_varying (vr
);
1450 if (vr
->type
== VR_VARYING
)
1451 extract_range_basic (vr
, stmt
);
1454 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1456 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1457 all the values in the ranges.
1459 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1461 - Return NULL_TREE if it is not always possible to determine the
1462 value of the comparison.
1464 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1465 assumed signed overflow is undefined. */
1469 compare_ranges (enum tree_code comp
, value_range
*vr0
, value_range
*vr1
,
1470 bool *strict_overflow_p
)
1472 /* VARYING or UNDEFINED ranges cannot be compared. */
1473 if (vr0
->type
== VR_VARYING
1474 || vr0
->type
== VR_UNDEFINED
1475 || vr1
->type
== VR_VARYING
1476 || vr1
->type
== VR_UNDEFINED
)
1479 /* Anti-ranges need to be handled separately. */
1480 if (vr0
->type
== VR_ANTI_RANGE
|| vr1
->type
== VR_ANTI_RANGE
)
1482 /* If both are anti-ranges, then we cannot compute any
1484 if (vr0
->type
== VR_ANTI_RANGE
&& vr1
->type
== VR_ANTI_RANGE
)
1487 /* These comparisons are never statically computable. */
1494 /* Equality can be computed only between a range and an
1495 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1496 if (vr0
->type
== VR_RANGE
)
1498 /* To simplify processing, make VR0 the anti-range. */
1499 value_range
*tmp
= vr0
;
1504 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1506 if (compare_values_warnv (vr0
->min
, vr1
->min
, strict_overflow_p
) == 0
1507 && compare_values_warnv (vr0
->max
, vr1
->max
, strict_overflow_p
) == 0)
1508 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1513 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1514 operands around and change the comparison code. */
1515 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1517 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1518 std::swap (vr0
, vr1
);
1521 if (comp
== EQ_EXPR
)
1523 /* Equality may only be computed if both ranges represent
1524 exactly one value. */
1525 if (compare_values_warnv (vr0
->min
, vr0
->max
, strict_overflow_p
) == 0
1526 && compare_values_warnv (vr1
->min
, vr1
->max
, strict_overflow_p
) == 0)
1528 int cmp_min
= compare_values_warnv (vr0
->min
, vr1
->min
,
1530 int cmp_max
= compare_values_warnv (vr0
->max
, vr1
->max
,
1532 if (cmp_min
== 0 && cmp_max
== 0)
1533 return boolean_true_node
;
1534 else if (cmp_min
!= -2 && cmp_max
!= -2)
1535 return boolean_false_node
;
1537 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1538 else if (compare_values_warnv (vr0
->min
, vr1
->max
,
1539 strict_overflow_p
) == 1
1540 || compare_values_warnv (vr1
->min
, vr0
->max
,
1541 strict_overflow_p
) == 1)
1542 return boolean_false_node
;
1546 else if (comp
== NE_EXPR
)
1550 /* If VR0 is completely to the left or completely to the right
1551 of VR1, they are always different. Notice that we need to
1552 make sure that both comparisons yield similar results to
1553 avoid comparing values that cannot be compared at
1555 cmp1
= compare_values_warnv (vr0
->max
, vr1
->min
, strict_overflow_p
);
1556 cmp2
= compare_values_warnv (vr0
->min
, vr1
->max
, strict_overflow_p
);
1557 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1558 return boolean_true_node
;
1560 /* If VR0 and VR1 represent a single value and are identical,
1562 else if (compare_values_warnv (vr0
->min
, vr0
->max
,
1563 strict_overflow_p
) == 0
1564 && compare_values_warnv (vr1
->min
, vr1
->max
,
1565 strict_overflow_p
) == 0
1566 && compare_values_warnv (vr0
->min
, vr1
->min
,
1567 strict_overflow_p
) == 0
1568 && compare_values_warnv (vr0
->max
, vr1
->max
,
1569 strict_overflow_p
) == 0)
1570 return boolean_false_node
;
1572 /* Otherwise, they may or may not be different. */
1576 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1580 /* If VR0 is to the left of VR1, return true. */
1581 tst
= compare_values_warnv (vr0
->max
, vr1
->min
, strict_overflow_p
);
1582 if ((comp
== LT_EXPR
&& tst
== -1)
1583 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1584 return boolean_true_node
;
1586 /* If VR0 is to the right of VR1, return false. */
1587 tst
= compare_values_warnv (vr0
->min
, vr1
->max
, strict_overflow_p
);
1588 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1589 || (comp
== LE_EXPR
&& tst
== 1))
1590 return boolean_false_node
;
1592 /* Otherwise, we don't know. */
1599 /* Given a value range VR, a value VAL and a comparison code COMP, return
1600 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1601 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1602 always returns false. Return NULL_TREE if it is not always
1603 possible to determine the value of the comparison. Also set
1604 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1605 assumed signed overflow is undefined. */
1608 compare_range_with_value (enum tree_code comp
, value_range
*vr
, tree val
,
1609 bool *strict_overflow_p
)
1611 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
1614 /* Anti-ranges need to be handled separately. */
1615 if (vr
->type
== VR_ANTI_RANGE
)
1617 /* For anti-ranges, the only predicates that we can compute at
1618 compile time are equality and inequality. */
1625 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1626 if (value_inside_range (val
, vr
->min
, vr
->max
) == 1)
1627 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1632 if (comp
== EQ_EXPR
)
1634 /* EQ_EXPR may only be computed if VR represents exactly
1636 if (compare_values_warnv (vr
->min
, vr
->max
, strict_overflow_p
) == 0)
1638 int cmp
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
1640 return boolean_true_node
;
1641 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1642 return boolean_false_node
;
1644 else if (compare_values_warnv (val
, vr
->min
, strict_overflow_p
) == -1
1645 || compare_values_warnv (vr
->max
, val
, strict_overflow_p
) == -1)
1646 return boolean_false_node
;
1650 else if (comp
== NE_EXPR
)
1652 /* If VAL is not inside VR, then they are always different. */
1653 if (compare_values_warnv (vr
->max
, val
, strict_overflow_p
) == -1
1654 || compare_values_warnv (vr
->min
, val
, strict_overflow_p
) == 1)
1655 return boolean_true_node
;
1657 /* If VR represents exactly one value equal to VAL, then return
1659 if (compare_values_warnv (vr
->min
, vr
->max
, strict_overflow_p
) == 0
1660 && compare_values_warnv (vr
->min
, val
, strict_overflow_p
) == 0)
1661 return boolean_false_node
;
1663 /* Otherwise, they may or may not be different. */
1666 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1670 /* If VR is to the left of VAL, return true. */
1671 tst
= compare_values_warnv (vr
->max
, val
, strict_overflow_p
);
1672 if ((comp
== LT_EXPR
&& tst
== -1)
1673 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1674 return boolean_true_node
;
1676 /* If VR is to the right of VAL, return false. */
1677 tst
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
1678 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1679 || (comp
== LE_EXPR
&& tst
== 1))
1680 return boolean_false_node
;
1682 /* Otherwise, we don't know. */
1685 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1689 /* If VR is to the right of VAL, return true. */
1690 tst
= compare_values_warnv (vr
->min
, val
, strict_overflow_p
);
1691 if ((comp
== GT_EXPR
&& tst
== 1)
1692 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1693 return boolean_true_node
;
1695 /* If VR is to the left of VAL, return false. */
1696 tst
= compare_values_warnv (vr
->max
, val
, strict_overflow_p
);
1697 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1698 || (comp
== GE_EXPR
&& tst
== -1))
1699 return boolean_false_node
;
1701 /* Otherwise, we don't know. */
1707 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1708 would be profitable to adjust VR using scalar evolution information
1709 for VAR. If so, update VR with the new limits. */
1712 vr_values::adjust_range_with_scev (value_range
*vr
, struct loop
*loop
,
1713 gimple
*stmt
, tree var
)
1715 tree init
, step
, chrec
, tmin
, tmax
, min
, max
, type
, tem
;
1716 enum ev_direction dir
;
1718 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1719 better opportunities than a regular range, but I'm not sure. */
1720 if (vr
->type
== VR_ANTI_RANGE
)
1723 chrec
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, var
));
1725 /* Like in PR19590, scev can return a constant function. */
1726 if (is_gimple_min_invariant (chrec
))
1728 set_value_range_to_value (vr
, chrec
, vr
->equiv
);
1732 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1735 init
= initial_condition_in_loop_num (chrec
, loop
->num
);
1736 tem
= op_with_constant_singleton_value_range (init
);
1739 step
= evolution_part_in_loop_num (chrec
, loop
->num
);
1740 tem
= op_with_constant_singleton_value_range (step
);
1744 /* If STEP is symbolic, we can't know whether INIT will be the
1745 minimum or maximum value in the range. Also, unless INIT is
1746 a simple expression, compare_values and possibly other functions
1747 in tree-vrp won't be able to handle it. */
1748 if (step
== NULL_TREE
1749 || !is_gimple_min_invariant (step
)
1750 || !valid_value_p (init
))
1753 dir
= scev_direction (chrec
);
1754 if (/* Do not adjust ranges if we do not know whether the iv increases
1755 or decreases, ... */
1756 dir
== EV_DIR_UNKNOWN
1757 /* ... or if it may wrap. */
1758 || scev_probably_wraps_p (NULL_TREE
, init
, step
, stmt
,
1759 get_chrec_loop (chrec
), true))
1762 type
= TREE_TYPE (var
);
1763 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1764 tmin
= lower_bound_in_type (type
, type
);
1766 tmin
= TYPE_MIN_VALUE (type
);
1767 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1768 tmax
= upper_bound_in_type (type
, type
);
1770 tmax
= TYPE_MAX_VALUE (type
);
1772 /* Try to use estimated number of iterations for the loop to constrain the
1773 final value in the evolution. */
1774 if (TREE_CODE (step
) == INTEGER_CST
1775 && is_gimple_val (init
)
1776 && (TREE_CODE (init
) != SSA_NAME
1777 || get_value_range (init
)->type
== VR_RANGE
))
1781 /* We are only entering here for loop header PHI nodes, so using
1782 the number of latch executions is the correct thing to use. */
1783 if (max_loop_iterations (loop
, &nit
))
1785 value_range maxvr
= VR_INITIALIZER
;
1786 signop sgn
= TYPE_SIGN (TREE_TYPE (step
));
1787 wi::overflow_type overflow
;
1789 widest_int wtmp
= wi::mul (wi::to_widest (step
), nit
, sgn
,
1791 /* If the multiplication overflowed we can't do a meaningful
1792 adjustment. Likewise if the result doesn't fit in the type
1793 of the induction variable. For a signed type we have to
1794 check whether the result has the expected signedness which
1795 is that of the step as number of iterations is unsigned. */
1797 && wi::fits_to_tree_p (wtmp
, TREE_TYPE (init
))
1799 || wi::gts_p (wtmp
, 0) == wi::gts_p (wi::to_wide (step
), 0)))
1801 tem
= wide_int_to_tree (TREE_TYPE (init
), wtmp
);
1802 extract_range_from_binary_expr (&maxvr
, PLUS_EXPR
,
1803 TREE_TYPE (init
), init
, tem
);
1804 /* Likewise if the addition did. */
1805 if (maxvr
.type
== VR_RANGE
)
1807 value_range initvr
= VR_INITIALIZER
;
1809 if (TREE_CODE (init
) == SSA_NAME
)
1810 initvr
= *(get_value_range (init
));
1811 else if (is_gimple_min_invariant (init
))
1812 set_value_range_to_value (&initvr
, init
, NULL
);
1816 /* Check if init + nit * step overflows. Though we checked
1817 scev {init, step}_loop doesn't wrap, it is not enough
1818 because the loop may exit immediately. Overflow could
1819 happen in the plus expression in this case. */
1820 if ((dir
== EV_DIR_DECREASES
1821 && compare_values (maxvr
.min
, initvr
.min
) != -1)
1822 || (dir
== EV_DIR_GROWS
1823 && compare_values (maxvr
.max
, initvr
.max
) != 1))
1833 if (vr
->type
== VR_VARYING
|| vr
->type
== VR_UNDEFINED
)
1838 /* For VARYING or UNDEFINED ranges, just about anything we get
1839 from scalar evolutions should be better. */
1841 if (dir
== EV_DIR_DECREASES
)
1846 else if (vr
->type
== VR_RANGE
)
1851 if (dir
== EV_DIR_DECREASES
)
1853 /* INIT is the maximum value. If INIT is lower than VR->MAX
1854 but no smaller than VR->MIN, set VR->MAX to INIT. */
1855 if (compare_values (init
, max
) == -1)
1858 /* According to the loop information, the variable does not
1860 if (compare_values (min
, tmin
) == -1)
1866 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1867 if (compare_values (init
, min
) == 1)
1870 if (compare_values (tmax
, max
) == -1)
1877 /* If we just created an invalid range with the minimum
1878 greater than the maximum, we fail conservatively.
1879 This should happen only in unreachable
1880 parts of code, or for invalid programs. */
1881 if (compare_values (min
, max
) == 1)
1884 /* Even for valid range info, sometimes overflow flag will leak in.
1885 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1887 if (TREE_OVERFLOW_P (min
))
1888 min
= drop_tree_overflow (min
);
1889 if (TREE_OVERFLOW_P (max
))
1890 max
= drop_tree_overflow (max
);
1892 set_value_range (vr
, VR_RANGE
, min
, max
, vr
->equiv
);
1895 /* Dump value ranges of all SSA_NAMEs to FILE. */
1898 vr_values::dump_all_value_ranges (FILE *file
)
1902 for (i
= 0; i
< num_vr_values
; i
++)
1906 print_generic_expr (file
, ssa_name (i
));
1907 fprintf (file
, ": ");
1908 dump_value_range (file
, vr_value
[i
]);
1909 fprintf (file
, "\n");
1913 fprintf (file
, "\n");
1916 /* Initialize VRP lattice. */
1918 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
1920 values_propagated
= false;
1921 num_vr_values
= num_ssa_names
;
1922 vr_value
= XCNEWVEC (value_range
*, num_vr_values
);
1923 vr_phi_edge_counts
= XCNEWVEC (int, num_ssa_names
);
1924 bitmap_obstack_initialize (&vrp_equiv_obstack
);
1927 /* Free VRP lattice. */
1929 vr_values::~vr_values ()
1931 /* Free allocated memory. */
1933 free (vr_phi_edge_counts
);
1934 bitmap_obstack_release (&vrp_equiv_obstack
);
1935 vrp_value_range_pool
.release ();
1937 /* So that we can distinguish between VRP data being available
1938 and not available. */
1940 vr_phi_edge_counts
= NULL
;
1945 static class vr_values
*x_vr_values
;
1947 /* Return the singleton value-range for NAME or NAME. */
1950 vrp_valueize (tree name
)
1952 if (TREE_CODE (name
) == SSA_NAME
)
1954 value_range
*vr
= x_vr_values
->get_value_range (name
);
1955 if (vr
->type
== VR_RANGE
1956 && (TREE_CODE (vr
->min
) == SSA_NAME
1957 || is_gimple_min_invariant (vr
->min
))
1958 && vrp_operand_equal_p (vr
->min
, vr
->max
))
1964 /* Return the singleton value-range for NAME if that is a constant
1965 but signal to not follow SSA edges. */
1968 vrp_valueize_1 (tree name
)
1970 if (TREE_CODE (name
) == SSA_NAME
)
1972 /* If the definition may be simulated again we cannot follow
1973 this SSA edge as the SSA propagator does not necessarily
1974 re-visit the use. */
1975 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1976 if (!gimple_nop_p (def_stmt
)
1977 && prop_simulate_again_p (def_stmt
))
1979 value_range
*vr
= x_vr_values
->get_value_range (name
);
1980 if (range_int_cst_singleton_p (vr
))
1986 /* Given STMT, an assignment or call, return its LHS if the type
1987 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
1990 get_output_for_vrp (gimple
*stmt
)
1992 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
1995 /* We only keep track of ranges in integral and pointer types. */
1996 tree lhs
= gimple_get_lhs (stmt
);
1997 if (TREE_CODE (lhs
) == SSA_NAME
1998 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1999 /* It is valid to have NULL MIN/MAX values on a type. See
2000 build_range_type. */
2001 && TYPE_MIN_VALUE (TREE_TYPE (lhs
))
2002 && TYPE_MAX_VALUE (TREE_TYPE (lhs
)))
2003 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
2009 /* Visit assignment STMT. If it produces an interesting range, record
2010 the range in VR and set LHS to OUTPUT_P. */
2013 vr_values::vrp_visit_assignment_or_call (gimple
*stmt
, tree
*output_p
,
2016 tree lhs
= get_output_for_vrp (stmt
);
2019 /* We only keep track of ranges in integral and pointer types. */
2022 enum gimple_code code
= gimple_code (stmt
);
2024 /* Try folding the statement to a constant first. */
2026 tree tem
= gimple_fold_stmt_to_constant_1 (stmt
, vrp_valueize
,
2031 if (TREE_CODE (tem
) == SSA_NAME
2032 && (SSA_NAME_IS_DEFAULT_DEF (tem
)
2033 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem
))))
2035 extract_range_from_ssa_name (vr
, tem
);
2038 else if (is_gimple_min_invariant (tem
))
2040 set_value_range_to_value (vr
, tem
, NULL
);
2044 /* Then dispatch to value-range extracting functions. */
2045 if (code
== GIMPLE_CALL
)
2046 extract_range_basic (vr
, stmt
);
2048 extract_range_from_assignment (vr
, as_a
<gassign
*> (stmt
));
2052 /* Helper that gets the value range of the SSA_NAME with version I
2053 or a symbolic range containing the SSA_NAME only if the value range
2054 is varying or undefined. */
2057 vr_values::get_vr_for_comparison (int i
)
2059 value_range vr
= *get_value_range (ssa_name (i
));
2061 /* If name N_i does not have a valid range, use N_i as its own
2062 range. This allows us to compare against names that may
2063 have N_i in their ranges. */
2064 if (vr
.type
== VR_VARYING
|| vr
.type
== VR_UNDEFINED
)
2067 vr
.min
= ssa_name (i
);
2068 vr
.max
= ssa_name (i
);
2074 /* Compare all the value ranges for names equivalent to VAR with VAL
2075 using comparison code COMP. Return the same value returned by
2076 compare_range_with_value, including the setting of
2077 *STRICT_OVERFLOW_P. */
2080 vr_values::compare_name_with_value (enum tree_code comp
, tree var
, tree val
,
2081 bool *strict_overflow_p
, bool use_equiv_p
)
2087 int used_strict_overflow
;
2089 value_range equiv_vr
;
2091 /* Get the set of equivalences for VAR. */
2092 e
= get_value_range (var
)->equiv
;
2094 /* Start at -1. Set it to 0 if we do a comparison without relying
2095 on overflow, or 1 if all comparisons rely on overflow. */
2096 used_strict_overflow
= -1;
2098 /* Compare vars' value range with val. */
2099 equiv_vr
= get_vr_for_comparison (SSA_NAME_VERSION (var
));
2101 retval
= compare_range_with_value (comp
, &equiv_vr
, val
, &sop
);
2103 used_strict_overflow
= sop
? 1 : 0;
2105 /* If the equiv set is empty we have done all work we need to do. */
2109 && used_strict_overflow
> 0)
2110 *strict_overflow_p
= true;
2114 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2116 tree name
= ssa_name (i
);
2121 && ! SSA_NAME_IS_DEFAULT_DEF (name
)
2122 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name
)))
2125 equiv_vr
= get_vr_for_comparison (i
);
2127 t
= compare_range_with_value (comp
, &equiv_vr
, val
, &sop
);
2130 /* If we get different answers from different members
2131 of the equivalence set this check must be in a dead
2132 code region. Folding it to a trap representation
2133 would be correct here. For now just return don't-know. */
2143 used_strict_overflow
= 0;
2144 else if (used_strict_overflow
< 0)
2145 used_strict_overflow
= 1;
2150 && used_strict_overflow
> 0)
2151 *strict_overflow_p
= true;
2157 /* Given a comparison code COMP and names N1 and N2, compare all the
2158 ranges equivalent to N1 against all the ranges equivalent to N2
2159 to determine the value of N1 COMP N2. Return the same value
2160 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2161 whether we relied on undefined signed overflow in the comparison. */
2165 vr_values::compare_names (enum tree_code comp
, tree n1
, tree n2
,
2166 bool *strict_overflow_p
)
2170 bitmap_iterator bi1
, bi2
;
2172 int used_strict_overflow
;
2173 static bitmap_obstack
*s_obstack
= NULL
;
2174 static bitmap s_e1
= NULL
, s_e2
= NULL
;
2176 /* Compare the ranges of every name equivalent to N1 against the
2177 ranges of every name equivalent to N2. */
2178 e1
= get_value_range (n1
)->equiv
;
2179 e2
= get_value_range (n2
)->equiv
;
2181 /* Use the fake bitmaps if e1 or e2 are not available. */
2182 if (s_obstack
== NULL
)
2184 s_obstack
= XNEW (bitmap_obstack
);
2185 bitmap_obstack_initialize (s_obstack
);
2186 s_e1
= BITMAP_ALLOC (s_obstack
);
2187 s_e2
= BITMAP_ALLOC (s_obstack
);
2194 /* Add N1 and N2 to their own set of equivalences to avoid
2195 duplicating the body of the loop just to check N1 and N2
2197 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2198 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2200 /* If the equivalence sets have a common intersection, then the two
2201 names can be compared without checking their ranges. */
2202 if (bitmap_intersect_p (e1
, e2
))
2204 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2205 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2207 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2209 : boolean_false_node
;
2212 /* Start at -1. Set it to 0 if we do a comparison without relying
2213 on overflow, or 1 if all comparisons rely on overflow. */
2214 used_strict_overflow
= -1;
2216 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2217 N2 to their own set of equivalences to avoid duplicating the body
2218 of the loop just to check N1 and N2 ranges. */
2219 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2221 if (! ssa_name (i1
))
2224 value_range vr1
= get_vr_for_comparison (i1
);
2226 t
= retval
= NULL_TREE
;
2227 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2229 if (! ssa_name (i2
))
2234 value_range vr2
= get_vr_for_comparison (i2
);
2236 t
= compare_ranges (comp
, &vr1
, &vr2
, &sop
);
2239 /* If we get different answers from different members
2240 of the equivalence set this check must be in a dead
2241 code region. Folding it to a trap representation
2242 would be correct here. For now just return don't-know. */
2246 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2247 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2253 used_strict_overflow
= 0;
2254 else if (used_strict_overflow
< 0)
2255 used_strict_overflow
= 1;
2261 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2262 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2263 if (used_strict_overflow
> 0)
2264 *strict_overflow_p
= true;
2269 /* None of the equivalent ranges are useful in computing this
2271 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2272 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2276 /* Helper function for vrp_evaluate_conditional_warnv & other
2280 vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2281 (enum tree_code code
, tree op0
, tree op1
, bool * strict_overflow_p
)
2283 value_range
*vr0
, *vr1
;
2285 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
2286 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
2288 tree res
= NULL_TREE
;
2290 res
= compare_ranges (code
, vr0
, vr1
, strict_overflow_p
);
2292 res
= compare_range_with_value (code
, vr0
, op1
, strict_overflow_p
);
2294 res
= (compare_range_with_value
2295 (swap_tree_comparison (code
), vr1
, op0
, strict_overflow_p
));
2299 /* Helper function for vrp_evaluate_conditional_warnv. */
2302 vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code
,
2305 bool *strict_overflow_p
,
2310 *only_ranges
= true;
2312 /* We only deal with integral and pointer types. */
2313 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2314 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
2317 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2318 as a simple equality test, then prefer that over its current form
2321 An overflow test which collapses to an equality test can always be
2322 expressed as a comparison of one argument against zero. Overflow
2323 occurs when the chosen argument is zero and does not occur if the
2324 chosen argument is not zero. */
2326 if (overflow_comparison_p (code
, op0
, op1
, use_equiv_p
, &x
))
2328 wide_int max
= wi::max_value (TYPE_PRECISION (TREE_TYPE (op0
)), UNSIGNED
);
2329 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2330 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2331 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2332 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2333 if (integer_zerop (x
))
2336 code
= (code
== LT_EXPR
|| code
== LE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2338 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2339 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2340 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2341 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2342 else if (wi::to_wide (x
) == max
- 1)
2345 op1
= wide_int_to_tree (TREE_TYPE (op0
), 0);
2346 code
= (code
== GT_EXPR
|| code
== GE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2350 if ((ret
= vrp_evaluate_conditional_warnv_with_ops_using_ranges
2351 (code
, op0
, op1
, strict_overflow_p
)))
2354 *only_ranges
= false;
2355 /* Do not use compare_names during propagation, it's quadratic. */
2356 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
2358 return compare_names (code
, op0
, op1
, strict_overflow_p
);
2359 else if (TREE_CODE (op0
) == SSA_NAME
)
2360 return compare_name_with_value (code
, op0
, op1
,
2361 strict_overflow_p
, use_equiv_p
);
2362 else if (TREE_CODE (op1
) == SSA_NAME
)
2363 return compare_name_with_value (swap_tree_comparison (code
), op1
, op0
,
2364 strict_overflow_p
, use_equiv_p
);
2368 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2369 information. Return NULL if the conditional can not be evaluated.
2370 The ranges of all the names equivalent with the operands in COND
2371 will be used when trying to compute the value. If the result is
2372 based on undefined signed overflow, issue a warning if
2376 vr_values::vrp_evaluate_conditional (tree_code code
, tree op0
,
2377 tree op1
, gimple
*stmt
)
2383 /* Some passes and foldings leak constants with overflow flag set
2384 into the IL. Avoid doing wrong things with these and bail out. */
2385 if ((TREE_CODE (op0
) == INTEGER_CST
2386 && TREE_OVERFLOW (op0
))
2387 || (TREE_CODE (op1
) == INTEGER_CST
2388 && TREE_OVERFLOW (op1
)))
2392 ret
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, true, &sop
,
2397 enum warn_strict_overflow_code wc
;
2398 const char* warnmsg
;
2400 if (is_gimple_min_invariant (ret
))
2402 wc
= WARN_STRICT_OVERFLOW_CONDITIONAL
;
2403 warnmsg
= G_("assuming signed overflow does not occur when "
2404 "simplifying conditional to constant");
2408 wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
2409 warnmsg
= G_("assuming signed overflow does not occur when "
2410 "simplifying conditional");
2413 if (issue_strict_overflow_warning (wc
))
2415 location_t location
;
2417 if (!gimple_has_location (stmt
))
2418 location
= input_location
;
2420 location
= gimple_location (stmt
);
2421 warning_at (location
, OPT_Wstrict_overflow
, "%s", warnmsg
);
2425 if (warn_type_limits
2426 && ret
&& only_ranges
2427 && TREE_CODE_CLASS (code
) == tcc_comparison
2428 && TREE_CODE (op0
) == SSA_NAME
)
2430 /* If the comparison is being folded and the operand on the LHS
2431 is being compared against a constant value that is outside of
2432 the natural range of OP0's type, then the predicate will
2433 always fold regardless of the value of OP0. If -Wtype-limits
2434 was specified, emit a warning. */
2435 tree type
= TREE_TYPE (op0
);
2436 value_range
*vr0
= get_value_range (op0
);
2438 if (vr0
->type
== VR_RANGE
2439 && INTEGRAL_TYPE_P (type
)
2440 && vrp_val_is_min (vr0
->min
)
2441 && vrp_val_is_max (vr0
->max
)
2442 && is_gimple_min_invariant (op1
))
2444 location_t location
;
2446 if (!gimple_has_location (stmt
))
2447 location
= input_location
;
2449 location
= gimple_location (stmt
);
2451 warning_at (location
, OPT_Wtype_limits
,
2453 ? G_("comparison always false "
2454 "due to limited range of data type")
2455 : G_("comparison always true "
2456 "due to limited range of data type"));
2464 /* Visit conditional statement STMT. If we can determine which edge
2465 will be taken out of STMT's basic block, record it in
2466 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2469 vr_values::vrp_visit_cond_stmt (gcond
*stmt
, edge
*taken_edge_p
)
2473 *taken_edge_p
= NULL
;
2475 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2480 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
2481 print_gimple_stmt (dump_file
, stmt
, 0);
2482 fprintf (dump_file
, "\nWith known ranges\n");
2484 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
2486 fprintf (dump_file
, "\t");
2487 print_generic_expr (dump_file
, use
);
2488 fprintf (dump_file
, ": ");
2489 dump_value_range (dump_file
, vr_value
[SSA_NAME_VERSION (use
)]);
2492 fprintf (dump_file
, "\n");
2495 /* Compute the value of the predicate COND by checking the known
2496 ranges of each of its operands.
2498 Note that we cannot evaluate all the equivalent ranges here
2499 because those ranges may not yet be final and with the current
2500 propagation strategy, we cannot determine when the value ranges
2501 of the names in the equivalence set have changed.
2503 For instance, given the following code fragment
2507 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2511 Assume that on the first visit to i_14, i_5 has the temporary
2512 range [8, 8] because the second argument to the PHI function is
2513 not yet executable. We derive the range ~[0, 0] for i_14 and the
2514 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2515 the first time, since i_14 is equivalent to the range [8, 8], we
2516 determine that the predicate is always false.
2518 On the next round of propagation, i_13 is determined to be
2519 VARYING, which causes i_5 to drop down to VARYING. So, another
2520 visit to i_14 is scheduled. In this second visit, we compute the
2521 exact same range and equivalence set for i_14, namely ~[0, 0] and
2522 { i_5 }. But we did not have the previous range for i_5
2523 registered, so vrp_visit_assignment thinks that the range for
2524 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2525 is not visited again, which stops propagation from visiting
2526 statements in the THEN clause of that if().
2528 To properly fix this we would need to keep the previous range
2529 value for the names in the equivalence set. This way we would've
2530 discovered that from one visit to the other i_5 changed from
2531 range [8, 8] to VR_VARYING.
2533 However, fixing this apparent limitation may not be worth the
2534 additional checking. Testing on several code bases (GCC, DLV,
2535 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2536 4 more predicates folded in SPEC. */
2539 val
= vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt
),
2540 gimple_cond_lhs (stmt
),
2541 gimple_cond_rhs (stmt
),
2544 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
2546 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2548 fprintf (dump_file
, "\nPredicate evaluates to: ");
2549 if (val
== NULL_TREE
)
2550 fprintf (dump_file
, "DON'T KNOW\n");
2552 print_generic_stmt (dump_file
, val
);
2556 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2557 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2558 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2559 Returns true if the default label is not needed. */
2562 find_case_label_ranges (gswitch
*stmt
, value_range
*vr
, size_t *min_idx1
,
2563 size_t *max_idx1
, size_t *min_idx2
,
2567 unsigned int n
= gimple_switch_num_labels (stmt
);
2569 tree case_low
, case_high
;
2570 tree min
= vr
->min
, max
= vr
->max
;
2572 gcc_checking_assert (vr
->type
== VR_RANGE
|| vr
->type
== VR_ANTI_RANGE
);
2574 take_default
= !find_case_label_range (stmt
, min
, max
, &i
, &j
);
2576 /* Set second range to emtpy. */
2580 if (vr
->type
== VR_RANGE
)
2584 return !take_default
;
2587 /* Set first range to all case labels. */
2594 /* Make sure all the values of case labels [i , j] are contained in
2595 range [MIN, MAX]. */
2596 case_low
= CASE_LOW (gimple_switch_label (stmt
, i
));
2597 case_high
= CASE_HIGH (gimple_switch_label (stmt
, j
));
2598 if (tree_int_cst_compare (case_low
, min
) < 0)
2600 if (case_high
!= NULL_TREE
2601 && tree_int_cst_compare (max
, case_high
) < 0)
2607 /* If the range spans case labels [i, j], the corresponding anti-range spans
2608 the labels [1, i - 1] and [j + 1, n - 1]. */
2634 /* Visit switch statement STMT. If we can determine which edge
2635 will be taken out of STMT's basic block, record it in
2636 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2639 vr_values::vrp_visit_switch_stmt (gswitch
*stmt
, edge
*taken_edge_p
)
2643 size_t i
= 0, j
= 0, k
, l
;
2646 *taken_edge_p
= NULL
;
2647 op
= gimple_switch_index (stmt
);
2648 if (TREE_CODE (op
) != SSA_NAME
)
2651 vr
= get_value_range (op
);
2652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2654 fprintf (dump_file
, "\nVisiting switch expression with operand ");
2655 print_generic_expr (dump_file
, op
);
2656 fprintf (dump_file
, " with known range ");
2657 dump_value_range (dump_file
, vr
);
2658 fprintf (dump_file
, "\n");
2661 if ((vr
->type
!= VR_RANGE
2662 && vr
->type
!= VR_ANTI_RANGE
)
2663 || symbolic_range_p (vr
))
2666 /* Find the single edge that is taken from the switch expression. */
2667 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
2669 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2673 gcc_assert (take_default
);
2674 val
= gimple_switch_default_label (stmt
);
2678 /* Check if labels with index i to j and maybe the default label
2679 are all reaching the same label. */
2681 val
= gimple_switch_label (stmt
, i
);
2683 && CASE_LABEL (gimple_switch_default_label (stmt
))
2684 != CASE_LABEL (val
))
2686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2687 fprintf (dump_file
, " not a single destination for this "
2691 for (++i
; i
<= j
; ++i
)
2693 if (CASE_LABEL (gimple_switch_label (stmt
, i
)) != CASE_LABEL (val
))
2695 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2696 fprintf (dump_file
, " not a single destination for this "
2703 if (CASE_LABEL (gimple_switch_label (stmt
, k
)) != CASE_LABEL (val
))
2705 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2706 fprintf (dump_file
, " not a single destination for this "
2713 *taken_edge_p
= find_edge (gimple_bb (stmt
),
2714 label_to_block (CASE_LABEL (val
)));
2716 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2718 fprintf (dump_file
, " will take edge to ");
2719 print_generic_stmt (dump_file
, CASE_LABEL (val
));
2724 /* Evaluate statement STMT. If the statement produces a useful range,
2725 set VR and corepsponding OUTPUT_P.
2727 If STMT is a conditional branch and we can determine its truth
2728 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2731 vr_values::extract_range_from_stmt (gimple
*stmt
, edge
*taken_edge_p
,
2732 tree
*output_p
, value_range
*vr
)
2735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2737 fprintf (dump_file
, "\nVisiting statement:\n");
2738 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
2741 if (!stmt_interesting_for_vrp (stmt
))
2742 gcc_assert (stmt_ends_bb_p (stmt
));
2743 else if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
2744 vrp_visit_assignment_or_call (stmt
, output_p
, vr
);
2745 else if (gimple_code (stmt
) == GIMPLE_COND
)
2746 vrp_visit_cond_stmt (as_a
<gcond
*> (stmt
), taken_edge_p
);
2747 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2748 vrp_visit_switch_stmt (as_a
<gswitch
*> (stmt
), taken_edge_p
);
2751 /* Visit all arguments for PHI node PHI that flow through executable
2752 edges. If a valid value range can be derived from all the incoming
2753 value ranges, set a new range in VR_RESULT. */
2756 vr_values::extract_range_from_phi_node (gphi
*phi
, value_range
*vr_result
)
2759 tree lhs
= PHI_RESULT (phi
);
2760 value_range
*lhs_vr
= get_value_range (lhs
);
2762 int edges
, old_edges
;
2765 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2767 fprintf (dump_file
, "\nVisiting PHI node: ");
2768 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
2771 bool may_simulate_backedge_again
= false;
2773 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2775 edge e
= gimple_phi_arg_edge (phi
, i
);
2777 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2780 " Argument #%d (%d -> %d %sexecutable)\n",
2781 (int) i
, e
->src
->index
, e
->dest
->index
,
2782 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
2785 if (e
->flags
& EDGE_EXECUTABLE
)
2787 tree arg
= PHI_ARG_DEF (phi
, i
);
2792 if (TREE_CODE (arg
) == SSA_NAME
)
2794 /* See if we are eventually going to change one of the args. */
2795 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
2796 if (! gimple_nop_p (def_stmt
)
2797 && prop_simulate_again_p (def_stmt
)
2798 && e
->flags
& EDGE_DFS_BACK
)
2799 may_simulate_backedge_again
= true;
2801 vr_arg
= *(get_value_range (arg
));
2802 /* Do not allow equivalences or symbolic ranges to leak in from
2803 backedges. That creates invalid equivalencies.
2804 See PR53465 and PR54767. */
2805 if (e
->flags
& EDGE_DFS_BACK
)
2807 if (vr_arg
.type
== VR_RANGE
2808 || vr_arg
.type
== VR_ANTI_RANGE
)
2810 vr_arg
.equiv
= NULL
;
2811 if (symbolic_range_p (&vr_arg
))
2813 vr_arg
.type
= VR_VARYING
;
2814 vr_arg
.min
= NULL_TREE
;
2815 vr_arg
.max
= NULL_TREE
;
2821 /* If the non-backedge arguments range is VR_VARYING then
2822 we can still try recording a simple equivalence. */
2823 if (vr_arg
.type
== VR_VARYING
)
2825 vr_arg
.type
= VR_RANGE
;
2828 vr_arg
.equiv
= NULL
;
2834 if (TREE_OVERFLOW_P (arg
))
2835 arg
= drop_tree_overflow (arg
);
2837 vr_arg
.type
= VR_RANGE
;
2840 vr_arg
.equiv
= NULL
;
2843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2845 fprintf (dump_file
, "\t");
2846 print_generic_expr (dump_file
, arg
, dump_flags
);
2847 fprintf (dump_file
, ": ");
2848 dump_value_range (dump_file
, &vr_arg
);
2849 fprintf (dump_file
, "\n");
2853 copy_value_range (vr_result
, &vr_arg
);
2855 vrp_meet (vr_result
, &vr_arg
);
2858 if (vr_result
->type
== VR_VARYING
)
2863 if (vr_result
->type
== VR_VARYING
)
2865 else if (vr_result
->type
== VR_UNDEFINED
)
2868 old_edges
= vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)];
2869 vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)] = edges
;
2871 /* To prevent infinite iterations in the algorithm, derive ranges
2872 when the new value is slightly bigger or smaller than the
2873 previous one. We don't do this if we have seen a new executable
2874 edge; this helps us avoid an infinity for conditionals
2875 which are not in a loop. If the old value-range was VR_UNDEFINED
2876 use the updated range and iterate one more time. If we will not
2877 simulate this PHI again via the backedge allow us to iterate. */
2879 && gimple_phi_num_args (phi
) > 1
2880 && edges
== old_edges
2881 && lhs_vr
->type
!= VR_UNDEFINED
2882 && may_simulate_backedge_again
)
2884 /* Compare old and new ranges, fall back to varying if the
2885 values are not comparable. */
2886 int cmp_min
= compare_values (lhs_vr
->min
, vr_result
->min
);
2889 int cmp_max
= compare_values (lhs_vr
->max
, vr_result
->max
);
2893 /* For non VR_RANGE or for pointers fall back to varying if
2894 the range changed. */
2895 if ((lhs_vr
->type
!= VR_RANGE
|| vr_result
->type
!= VR_RANGE
2896 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2897 && (cmp_min
!= 0 || cmp_max
!= 0))
2900 /* If the new minimum is larger than the previous one
2901 retain the old value. If the new minimum value is smaller
2902 than the previous one and not -INF go all the way to -INF + 1.
2903 In the first case, to avoid infinite bouncing between different
2904 minimums, and in the other case to avoid iterating millions of
2905 times to reach -INF. Going to -INF + 1 also lets the following
2906 iteration compute whether there will be any overflow, at the
2907 expense of one additional iteration. */
2909 vr_result
->min
= lhs_vr
->min
;
2910 else if (cmp_min
> 0
2911 && !vrp_val_is_min (vr_result
->min
))
2913 = int_const_binop (PLUS_EXPR
,
2914 vrp_val_min (TREE_TYPE (vr_result
->min
)),
2915 build_int_cst (TREE_TYPE (vr_result
->min
), 1));
2917 /* Similarly for the maximum value. */
2919 vr_result
->max
= lhs_vr
->max
;
2920 else if (cmp_max
< 0
2921 && !vrp_val_is_max (vr_result
->max
))
2923 = int_const_binop (MINUS_EXPR
,
2924 vrp_val_max (TREE_TYPE (vr_result
->min
)),
2925 build_int_cst (TREE_TYPE (vr_result
->min
), 1));
2927 /* If we dropped either bound to +-INF then if this is a loop
2928 PHI node SCEV may known more about its value-range. */
2929 if (cmp_min
> 0 || cmp_min
< 0
2930 || cmp_max
< 0 || cmp_max
> 0)
2933 goto infinite_check
;
2939 set_value_range_to_varying (vr_result
);
2942 /* If this is a loop PHI node SCEV may known more about its value-range.
2943 scev_check can be reached from two paths, one is a fall through from above
2944 "varying" label, the other is direct goto from code block which tries to
2945 avoid infinite simulation. */
2946 if (scev_initialized_p ()
2947 && (l
= loop_containing_stmt (phi
))
2948 && l
->header
== gimple_bb (phi
))
2949 adjust_range_with_scev (vr_result
, l
, phi
, lhs
);
2952 /* If we will end up with a (-INF, +INF) range, set it to
2953 VARYING. Same if the previous max value was invalid for
2954 the type and we end up with vr_result.min > vr_result.max. */
2955 if ((vr_result
->type
== VR_RANGE
|| vr_result
->type
== VR_ANTI_RANGE
)
2956 && !((vrp_val_is_max (vr_result
->max
) && vrp_val_is_min (vr_result
->min
))
2957 || compare_values (vr_result
->min
, vr_result
->max
) > 0))
2960 set_value_range_to_varying (vr_result
);
2962 /* If the new range is different than the previous value, keep
2968 /* Simplify boolean operations if the source is known
2969 to be already a boolean. */
2971 vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator
*gsi
,
2974 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2976 bool need_conversion
;
2978 /* We handle only !=/== case here. */
2979 gcc_assert (rhs_code
== EQ_EXPR
|| rhs_code
== NE_EXPR
);
2981 op0
= gimple_assign_rhs1 (stmt
);
2982 if (!op_with_boolean_value_range_p (op0
))
2985 op1
= gimple_assign_rhs2 (stmt
);
2986 if (!op_with_boolean_value_range_p (op1
))
2989 /* Reduce number of cases to handle to NE_EXPR. As there is no
2990 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
2991 if (rhs_code
== EQ_EXPR
)
2993 if (TREE_CODE (op1
) == INTEGER_CST
)
2994 op1
= int_const_binop (BIT_XOR_EXPR
, op1
,
2995 build_int_cst (TREE_TYPE (op1
), 1));
3000 lhs
= gimple_assign_lhs (stmt
);
3002 = !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
));
3004 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
3006 && !TYPE_UNSIGNED (TREE_TYPE (op0
))
3007 && TYPE_PRECISION (TREE_TYPE (op0
)) == 1
3008 && TYPE_PRECISION (TREE_TYPE (lhs
)) > 1)
3011 /* For A != 0 we can substitute A itself. */
3012 if (integer_zerop (op1
))
3013 gimple_assign_set_rhs_with_ops (gsi
,
3015 ? NOP_EXPR
: TREE_CODE (op0
), op0
);
3016 /* For A != B we substitute A ^ B. Either with conversion. */
3017 else if (need_conversion
)
3019 tree tem
= make_ssa_name (TREE_TYPE (op0
));
3021 = gimple_build_assign (tem
, BIT_XOR_EXPR
, op0
, op1
);
3022 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
3023 if (INTEGRAL_TYPE_P (TREE_TYPE (tem
))
3024 && TYPE_PRECISION (TREE_TYPE (tem
)) > 1)
3025 set_range_info (tem
, VR_RANGE
,
3026 wi::zero (TYPE_PRECISION (TREE_TYPE (tem
))),
3027 wi::one (TYPE_PRECISION (TREE_TYPE (tem
))));
3028 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, tem
);
3032 gimple_assign_set_rhs_with_ops (gsi
, BIT_XOR_EXPR
, op0
, op1
);
3033 update_stmt (gsi_stmt (*gsi
));
3034 fold_stmt (gsi
, follow_single_use_edges
);
3039 /* Simplify a division or modulo operator to a right shift or bitwise and
3040 if the first operand is unsigned or is greater than zero and the second
3041 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
3042 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
3043 optimize it into just op0 if op0's range is known to be a subset of
3044 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3048 vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator
*gsi
,
3051 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3053 tree op0
= gimple_assign_rhs1 (stmt
);
3054 tree op1
= gimple_assign_rhs2 (stmt
);
3055 tree op0min
= NULL_TREE
, op0max
= NULL_TREE
;
3057 value_range
*vr
= NULL
;
3059 if (TREE_CODE (op0
) == INTEGER_CST
)
3066 vr
= get_value_range (op0
);
3067 if (range_int_cst_p (vr
))
3074 if (rhs_code
== TRUNC_MOD_EXPR
3075 && TREE_CODE (op1
) == SSA_NAME
)
3077 value_range
*vr1
= get_value_range (op1
);
3078 if (range_int_cst_p (vr1
))
3081 if (rhs_code
== TRUNC_MOD_EXPR
3082 && TREE_CODE (op1min
) == INTEGER_CST
3083 && tree_int_cst_sgn (op1min
) == 1
3085 && tree_int_cst_lt (op0max
, op1min
))
3087 if (TYPE_UNSIGNED (TREE_TYPE (op0
))
3088 || tree_int_cst_sgn (op0min
) >= 0
3089 || tree_int_cst_lt (fold_unary (NEGATE_EXPR
, TREE_TYPE (op1min
), op1min
),
3092 /* If op0 already has the range op0 % op1 has,
3093 then TRUNC_MOD_EXPR won't change anything. */
3094 gimple_assign_set_rhs_from_tree (gsi
, op0
);
3099 if (TREE_CODE (op0
) != SSA_NAME
)
3102 if (!integer_pow2p (op1
))
3104 /* X % -Y can be only optimized into X % Y either if
3105 X is not INT_MIN, or Y is not -1. Fold it now, as after
3106 remove_range_assertions the range info might be not available
3108 if (rhs_code
== TRUNC_MOD_EXPR
3109 && fold_stmt (gsi
, follow_single_use_edges
))
3114 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
3115 val
= integer_one_node
;
3120 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
3124 && integer_onep (val
)
3125 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3127 location_t location
;
3129 if (!gimple_has_location (stmt
))
3130 location
= input_location
;
3132 location
= gimple_location (stmt
);
3133 warning_at (location
, OPT_Wstrict_overflow
,
3134 "assuming signed overflow does not occur when "
3135 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3139 if (val
&& integer_onep (val
))
3143 if (rhs_code
== TRUNC_DIV_EXPR
)
3145 t
= build_int_cst (integer_type_node
, tree_log2 (op1
));
3146 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
3147 gimple_assign_set_rhs1 (stmt
, op0
);
3148 gimple_assign_set_rhs2 (stmt
, t
);
3152 t
= build_int_cst (TREE_TYPE (op1
), 1);
3153 t
= int_const_binop (MINUS_EXPR
, op1
, t
);
3154 t
= fold_convert (TREE_TYPE (op0
), t
);
3156 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
3157 gimple_assign_set_rhs1 (stmt
, op0
);
3158 gimple_assign_set_rhs2 (stmt
, t
);
3162 fold_stmt (gsi
, follow_single_use_edges
);
3169 /* Simplify a min or max if the ranges of the two operands are
3170 disjoint. Return true if we do simplify. */
3173 vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator
*gsi
,
3176 tree op0
= gimple_assign_rhs1 (stmt
);
3177 tree op1
= gimple_assign_rhs2 (stmt
);
3181 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3182 (LE_EXPR
, op0
, op1
, &sop
));
3186 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3187 (LT_EXPR
, op0
, op1
, &sop
));
3192 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3194 location_t location
;
3196 if (!gimple_has_location (stmt
))
3197 location
= input_location
;
3199 location
= gimple_location (stmt
);
3200 warning_at (location
, OPT_Wstrict_overflow
,
3201 "assuming signed overflow does not occur when "
3202 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3205 /* VAL == TRUE -> OP0 < or <= op1
3206 VAL == FALSE -> OP0 > or >= op1. */
3207 tree res
= ((gimple_assign_rhs_code (stmt
) == MAX_EXPR
)
3208 == integer_zerop (val
)) ? op0
: op1
;
3209 gimple_assign_set_rhs_from_tree (gsi
, res
);
3216 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3217 ABS_EXPR. If the operand is <= 0, then simplify the
3218 ABS_EXPR into a NEGATE_EXPR. */
3221 vr_values::simplify_abs_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3223 tree op
= gimple_assign_rhs1 (stmt
);
3224 value_range
*vr
= get_value_range (op
);
3231 val
= compare_range_with_value (LE_EXPR
, vr
, integer_zero_node
, &sop
);
3234 /* The range is neither <= 0 nor > 0. Now see if it is
3235 either < 0 or >= 0. */
3237 val
= compare_range_with_value (LT_EXPR
, vr
, integer_zero_node
,
3243 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3245 location_t location
;
3247 if (!gimple_has_location (stmt
))
3248 location
= input_location
;
3250 location
= gimple_location (stmt
);
3251 warning_at (location
, OPT_Wstrict_overflow
,
3252 "assuming signed overflow does not occur when "
3253 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3256 gimple_assign_set_rhs1 (stmt
, op
);
3257 if (integer_zerop (val
))
3258 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
3260 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
3262 fold_stmt (gsi
, follow_single_use_edges
);
3270 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3271 If all the bits that are being cleared by & are already
3272 known to be zero from VR, or all the bits that are being
3273 set by | are already known to be one from VR, the bit
3274 operation is redundant. */
3277 vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator
*gsi
,
3280 tree op0
= gimple_assign_rhs1 (stmt
);
3281 tree op1
= gimple_assign_rhs2 (stmt
);
3282 tree op
= NULL_TREE
;
3283 value_range vr0
= VR_INITIALIZER
;
3284 value_range vr1
= VR_INITIALIZER
;
3285 wide_int may_be_nonzero0
, may_be_nonzero1
;
3286 wide_int must_be_nonzero0
, must_be_nonzero1
;
3289 if (TREE_CODE (op0
) == SSA_NAME
)
3290 vr0
= *(get_value_range (op0
));
3291 else if (is_gimple_min_invariant (op0
))
3292 set_value_range_to_value (&vr0
, op0
, NULL
);
3296 if (TREE_CODE (op1
) == SSA_NAME
)
3297 vr1
= *(get_value_range (op1
));
3298 else if (is_gimple_min_invariant (op1
))
3299 set_value_range_to_value (&vr1
, op1
, NULL
);
3303 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op0
), &vr0
, &may_be_nonzero0
,
3306 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op1
), &vr1
, &may_be_nonzero1
,
3310 switch (gimple_assign_rhs_code (stmt
))
3313 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3319 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3327 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3333 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3344 if (op
== NULL_TREE
)
3347 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (op
), op
);
3348 update_stmt (gsi_stmt (*gsi
));
3352 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3353 a known value range VR.
3355 If there is one and only one value which will satisfy the
3356 conditional, then return that value. Else return NULL.
3358 If signed overflow must be undefined for the value to satisfy
3359 the conditional, then set *STRICT_OVERFLOW_P to true. */
3362 test_for_singularity (enum tree_code cond_code
, tree op0
,
3363 tree op1
, value_range
*vr
)
3368 /* Extract minimum/maximum values which satisfy the conditional as it was
3370 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
3372 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
3375 if (cond_code
== LT_EXPR
)
3377 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3378 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
3379 /* Signal to compare_values_warnv this expr doesn't overflow. */
3381 TREE_NO_WARNING (max
) = 1;
3384 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
3386 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
3389 if (cond_code
== GT_EXPR
)
3391 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3392 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
3393 /* Signal to compare_values_warnv this expr doesn't overflow. */
3395 TREE_NO_WARNING (min
) = 1;
3399 /* Now refine the minimum and maximum values using any
3400 value range information we have for op0. */
3403 if (compare_values (vr
->min
, min
) == 1)
3405 if (compare_values (vr
->max
, max
) == -1)
3408 /* If the new min/max values have converged to a single value,
3409 then there is only one value which can satisfy the condition,
3410 return that value. */
3411 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
3417 /* Return whether the value range *VR fits in an integer type specified
3418 by PRECISION and UNSIGNED_P. */
3421 range_fits_type_p (value_range
*vr
, unsigned dest_precision
, signop dest_sgn
)
3424 unsigned src_precision
;
3428 /* We can only handle integral and pointer types. */
3429 src_type
= TREE_TYPE (vr
->min
);
3430 if (!INTEGRAL_TYPE_P (src_type
)
3431 && !POINTER_TYPE_P (src_type
))
3434 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3435 and so is an identity transform. */
3436 src_precision
= TYPE_PRECISION (TREE_TYPE (vr
->min
));
3437 src_sgn
= TYPE_SIGN (src_type
);
3438 if ((src_precision
< dest_precision
3439 && !(dest_sgn
== UNSIGNED
&& src_sgn
== SIGNED
))
3440 || (src_precision
== dest_precision
&& src_sgn
== dest_sgn
))
3443 /* Now we can only handle ranges with constant bounds. */
3444 if (vr
->type
!= VR_RANGE
3445 || TREE_CODE (vr
->min
) != INTEGER_CST
3446 || TREE_CODE (vr
->max
) != INTEGER_CST
)
3449 /* For sign changes, the MSB of the wide_int has to be clear.
3450 An unsigned value with its MSB set cannot be represented by
3451 a signed wide_int, while a negative value cannot be represented
3452 by an unsigned wide_int. */
3453 if (src_sgn
!= dest_sgn
3454 && (wi::lts_p (wi::to_wide (vr
->min
), 0)
3455 || wi::lts_p (wi::to_wide (vr
->max
), 0)))
3458 /* Then we can perform the conversion on both ends and compare
3459 the result for equality. */
3460 tem
= wi::ext (wi::to_widest (vr
->min
), dest_precision
, dest_sgn
);
3461 if (tem
!= wi::to_widest (vr
->min
))
3463 tem
= wi::ext (wi::to_widest (vr
->max
), dest_precision
, dest_sgn
);
3464 if (tem
!= wi::to_widest (vr
->max
))
3470 /* Simplify a conditional using a relational operator to an equality
3471 test if the range information indicates only one value can satisfy
3472 the original conditional. */
3475 vr_values::simplify_cond_using_ranges_1 (gcond
*stmt
)
3477 tree op0
= gimple_cond_lhs (stmt
);
3478 tree op1
= gimple_cond_rhs (stmt
);
3479 enum tree_code cond_code
= gimple_cond_code (stmt
);
3481 if (cond_code
!= NE_EXPR
3482 && cond_code
!= EQ_EXPR
3483 && TREE_CODE (op0
) == SSA_NAME
3484 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3485 && is_gimple_min_invariant (op1
))
3487 value_range
*vr
= get_value_range (op0
);
3489 /* If we have range information for OP0, then we might be
3490 able to simplify this conditional. */
3491 if (vr
->type
== VR_RANGE
)
3493 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
3498 fprintf (dump_file
, "Simplified relational ");
3499 print_gimple_stmt (dump_file
, stmt
, 0);
3500 fprintf (dump_file
, " into ");
3503 gimple_cond_set_code (stmt
, EQ_EXPR
);
3504 gimple_cond_set_lhs (stmt
, op0
);
3505 gimple_cond_set_rhs (stmt
, new_tree
);
3511 print_gimple_stmt (dump_file
, stmt
, 0);
3512 fprintf (dump_file
, "\n");
3518 /* Try again after inverting the condition. We only deal
3519 with integral types here, so no need to worry about
3520 issues with inverting FP comparisons. */
3521 new_tree
= test_for_singularity
3522 (invert_tree_comparison (cond_code
, false),
3528 fprintf (dump_file
, "Simplified relational ");
3529 print_gimple_stmt (dump_file
, stmt
, 0);
3530 fprintf (dump_file
, " into ");
3533 gimple_cond_set_code (stmt
, NE_EXPR
);
3534 gimple_cond_set_lhs (stmt
, op0
);
3535 gimple_cond_set_rhs (stmt
, new_tree
);
3541 print_gimple_stmt (dump_file
, stmt
, 0);
3542 fprintf (dump_file
, "\n");
3552 /* STMT is a conditional at the end of a basic block.
3554 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3555 was set via a type conversion, try to replace the SSA_NAME with the RHS
3556 of the type conversion. Doing so makes the conversion dead which helps
3557 subsequent passes. */
3560 vr_values::simplify_cond_using_ranges_2 (gcond
*stmt
)
3562 tree op0
= gimple_cond_lhs (stmt
);
3563 tree op1
= gimple_cond_rhs (stmt
);
3565 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3566 see if OP0 was set by a type conversion where the source of
3567 the conversion is another SSA_NAME with a range that fits
3568 into the range of OP0's type.
3570 If so, the conversion is redundant as the earlier SSA_NAME can be
3571 used for the comparison directly if we just massage the constant in the
3573 if (TREE_CODE (op0
) == SSA_NAME
3574 && TREE_CODE (op1
) == INTEGER_CST
)
3576 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op0
);
3579 if (!is_gimple_assign (def_stmt
)
3580 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3583 innerop
= gimple_assign_rhs1 (def_stmt
);
3585 if (TREE_CODE (innerop
) == SSA_NAME
3586 && !POINTER_TYPE_P (TREE_TYPE (innerop
))
3587 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
)
3588 && desired_pro_or_demotion_p (TREE_TYPE (innerop
), TREE_TYPE (op0
)))
3590 value_range
*vr
= get_value_range (innerop
);
3592 if (range_int_cst_p (vr
)
3593 && range_fits_type_p (vr
,
3594 TYPE_PRECISION (TREE_TYPE (op0
)),
3595 TYPE_SIGN (TREE_TYPE (op0
)))
3596 && int_fits_type_p (op1
, TREE_TYPE (innerop
)))
3598 tree newconst
= fold_convert (TREE_TYPE (innerop
), op1
);
3599 gimple_cond_set_lhs (stmt
, innerop
);
3600 gimple_cond_set_rhs (stmt
, newconst
);
3602 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3604 fprintf (dump_file
, "Folded into: ");
3605 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3606 fprintf (dump_file
, "\n");
3613 /* Simplify a switch statement using the value range of the switch
3617 vr_values::simplify_switch_using_ranges (gswitch
*stmt
)
3619 tree op
= gimple_switch_index (stmt
);
3620 value_range
*vr
= NULL
;
3624 size_t i
= 0, j
= 0, n
, n2
;
3627 size_t k
= 1, l
= 0;
3629 if (TREE_CODE (op
) == SSA_NAME
)
3631 vr
= get_value_range (op
);
3633 /* We can only handle integer ranges. */
3634 if ((vr
->type
!= VR_RANGE
3635 && vr
->type
!= VR_ANTI_RANGE
)
3636 || symbolic_range_p (vr
))
3639 /* Find case label for min/max of the value range. */
3640 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
3642 else if (TREE_CODE (op
) == INTEGER_CST
)
3644 take_default
= !find_case_label_index (stmt
, 1, op
, &i
);
3658 n
= gimple_switch_num_labels (stmt
);
3660 /* We can truncate the case label ranges that partially overlap with OP's
3662 size_t min_idx
= 1, max_idx
= 0;
3664 find_case_label_range (stmt
, vr
->min
, vr
->max
, &min_idx
, &max_idx
);
3665 if (min_idx
<= max_idx
)
3667 tree min_label
= gimple_switch_label (stmt
, min_idx
);
3668 tree max_label
= gimple_switch_label (stmt
, max_idx
);
3670 /* Avoid changing the type of the case labels when truncating. */
3671 tree case_label_type
= TREE_TYPE (CASE_LOW (min_label
));
3672 tree vr_min
= fold_convert (case_label_type
, vr
->min
);
3673 tree vr_max
= fold_convert (case_label_type
, vr
->max
);
3675 if (vr
->type
== VR_RANGE
)
3677 /* If OP's value range is [2,8] and the low label range is
3678 0 ... 3, truncate the label's range to 2 .. 3. */
3679 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3680 && CASE_HIGH (min_label
) != NULL_TREE
3681 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3682 CASE_LOW (min_label
) = vr_min
;
3684 /* If OP's value range is [2,8] and the high label range is
3685 7 ... 10, truncate the label's range to 7 .. 8. */
3686 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3687 && CASE_HIGH (max_label
) != NULL_TREE
3688 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3689 CASE_HIGH (max_label
) = vr_max
;
3691 else if (vr
->type
== VR_ANTI_RANGE
)
3693 tree one_cst
= build_one_cst (case_label_type
);
3695 if (min_label
== max_label
)
3697 /* If OP's value range is ~[7,8] and the label's range is
3698 7 ... 10, truncate the label's range to 9 ... 10. */
3699 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) == 0
3700 && CASE_HIGH (min_label
) != NULL_TREE
3701 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) > 0)
3702 CASE_LOW (min_label
)
3703 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3705 /* If OP's value range is ~[7,8] and the label's range is
3706 5 ... 8, truncate the label's range to 5 ... 6. */
3707 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3708 && CASE_HIGH (min_label
) != NULL_TREE
3709 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) == 0)
3710 CASE_HIGH (min_label
)
3711 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3715 /* If OP's value range is ~[2,8] and the low label range is
3716 0 ... 3, truncate the label's range to 0 ... 1. */
3717 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3718 && CASE_HIGH (min_label
) != NULL_TREE
3719 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3720 CASE_HIGH (min_label
)
3721 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3723 /* If OP's value range is ~[2,8] and the high label range is
3724 7 ... 10, truncate the label's range to 9 ... 10. */
3725 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3726 && CASE_HIGH (max_label
) != NULL_TREE
3727 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3728 CASE_LOW (max_label
)
3729 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3733 /* Canonicalize singleton case ranges. */
3734 if (tree_int_cst_equal (CASE_LOW (min_label
), CASE_HIGH (min_label
)))
3735 CASE_HIGH (min_label
) = NULL_TREE
;
3736 if (tree_int_cst_equal (CASE_LOW (max_label
), CASE_HIGH (max_label
)))
3737 CASE_HIGH (max_label
) = NULL_TREE
;
3740 /* We can also eliminate case labels that lie completely outside OP's value
3743 /* Bail out if this is just all edges taken. */
3749 /* Build a new vector of taken case labels. */
3750 vec2
= make_tree_vec (j
- i
+ 1 + l
- k
+ 1 + (int)take_default
);
3753 /* Add the default edge, if necessary. */
3755 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
3757 for (; i
<= j
; ++i
, ++n2
)
3758 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
3760 for (; k
<= l
; ++k
, ++n2
)
3761 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, k
);
3763 /* Mark needed edges. */
3764 for (i
= 0; i
< n2
; ++i
)
3766 e
= find_edge (gimple_bb (stmt
),
3767 label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
3768 e
->aux
= (void *)-1;
3771 /* Queue not needed edges for later removal. */
3772 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
3774 if (e
->aux
== (void *)-1)
3780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3782 fprintf (dump_file
, "removing unreachable case label\n");
3784 to_remove_edges
.safe_push (e
);
3785 e
->flags
&= ~EDGE_EXECUTABLE
;
3788 /* And queue an update for the stmt. */
3791 to_update_switch_stmts
.safe_push (su
);
3795 /* Simplify an integral conversion from an SSA name in STMT. */
3798 simplify_conversion_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3800 tree innerop
, middleop
, finaltype
;
3802 signop inner_sgn
, middle_sgn
, final_sgn
;
3803 unsigned inner_prec
, middle_prec
, final_prec
;
3804 widest_int innermin
, innermed
, innermax
, middlemin
, middlemed
, middlemax
;
3806 finaltype
= TREE_TYPE (gimple_assign_lhs (stmt
));
3807 if (!INTEGRAL_TYPE_P (finaltype
))
3809 middleop
= gimple_assign_rhs1 (stmt
);
3810 def_stmt
= SSA_NAME_DEF_STMT (middleop
);
3811 if (!is_gimple_assign (def_stmt
)
3812 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3814 innerop
= gimple_assign_rhs1 (def_stmt
);
3815 if (TREE_CODE (innerop
) != SSA_NAME
3816 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
))
3819 /* Get the value-range of the inner operand. Use get_range_info in
3820 case innerop was created during substitute-and-fold. */
3821 wide_int imin
, imax
;
3822 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
))
3823 || get_range_info (innerop
, &imin
, &imax
) != VR_RANGE
)
3825 innermin
= widest_int::from (imin
, TYPE_SIGN (TREE_TYPE (innerop
)));
3826 innermax
= widest_int::from (imax
, TYPE_SIGN (TREE_TYPE (innerop
)));
3828 /* Simulate the conversion chain to check if the result is equal if
3829 the middle conversion is removed. */
3830 inner_prec
= TYPE_PRECISION (TREE_TYPE (innerop
));
3831 middle_prec
= TYPE_PRECISION (TREE_TYPE (middleop
));
3832 final_prec
= TYPE_PRECISION (finaltype
);
3834 /* If the first conversion is not injective, the second must not
3836 if (wi::gtu_p (innermax
- innermin
,
3837 wi::mask
<widest_int
> (middle_prec
, false))
3838 && middle_prec
< final_prec
)
3840 /* We also want a medium value so that we can track the effect that
3841 narrowing conversions with sign change have. */
3842 inner_sgn
= TYPE_SIGN (TREE_TYPE (innerop
));
3843 if (inner_sgn
== UNSIGNED
)
3844 innermed
= wi::shifted_mask
<widest_int
> (1, inner_prec
- 1, false);
3847 if (wi::cmp (innermin
, innermed
, inner_sgn
) >= 0
3848 || wi::cmp (innermed
, innermax
, inner_sgn
) >= 0)
3849 innermed
= innermin
;
3851 middle_sgn
= TYPE_SIGN (TREE_TYPE (middleop
));
3852 middlemin
= wi::ext (innermin
, middle_prec
, middle_sgn
);
3853 middlemed
= wi::ext (innermed
, middle_prec
, middle_sgn
);
3854 middlemax
= wi::ext (innermax
, middle_prec
, middle_sgn
);
3856 /* Require that the final conversion applied to both the original
3857 and the intermediate range produces the same result. */
3858 final_sgn
= TYPE_SIGN (finaltype
);
3859 if (wi::ext (middlemin
, final_prec
, final_sgn
)
3860 != wi::ext (innermin
, final_prec
, final_sgn
)
3861 || wi::ext (middlemed
, final_prec
, final_sgn
)
3862 != wi::ext (innermed
, final_prec
, final_sgn
)
3863 || wi::ext (middlemax
, final_prec
, final_sgn
)
3864 != wi::ext (innermax
, final_prec
, final_sgn
))
3867 gimple_assign_set_rhs1 (stmt
, innerop
);
3868 fold_stmt (gsi
, follow_single_use_edges
);
3872 /* Simplify a conversion from integral SSA name to float in STMT. */
3875 vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator
*gsi
,
3878 tree rhs1
= gimple_assign_rhs1 (stmt
);
3879 value_range
*vr
= get_value_range (rhs1
);
3880 scalar_float_mode fltmode
3881 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
)));
3882 scalar_int_mode mode
;
3886 /* We can only handle constant ranges. */
3887 if (vr
->type
!= VR_RANGE
3888 || TREE_CODE (vr
->min
) != INTEGER_CST
3889 || TREE_CODE (vr
->max
) != INTEGER_CST
)
3892 /* First check if we can use a signed type in place of an unsigned. */
3893 scalar_int_mode rhs_mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1
));
3894 if (TYPE_UNSIGNED (TREE_TYPE (rhs1
))
3895 && can_float_p (fltmode
, rhs_mode
, 0) != CODE_FOR_nothing
3896 && range_fits_type_p (vr
, TYPE_PRECISION (TREE_TYPE (rhs1
)), SIGNED
))
3898 /* If we can do the conversion in the current input mode do nothing. */
3899 else if (can_float_p (fltmode
, rhs_mode
,
3900 TYPE_UNSIGNED (TREE_TYPE (rhs1
))) != CODE_FOR_nothing
)
3902 /* Otherwise search for a mode we can use, starting from the narrowest
3903 integer mode available. */
3906 mode
= NARROWEST_INT_MODE
;
3909 /* If we cannot do a signed conversion to float from mode
3910 or if the value-range does not fit in the signed type
3911 try with a wider mode. */
3912 if (can_float_p (fltmode
, mode
, 0) != CODE_FOR_nothing
3913 && range_fits_type_p (vr
, GET_MODE_PRECISION (mode
), SIGNED
))
3916 /* But do not widen the input. Instead leave that to the
3917 optabs expansion code. */
3918 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
3919 || GET_MODE_PRECISION (mode
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
3924 /* It works, insert a truncation or sign-change before the
3925 float conversion. */
3926 tem
= make_ssa_name (build_nonstandard_integer_type
3927 (GET_MODE_PRECISION (mode
), 0));
3928 conv
= gimple_build_assign (tem
, NOP_EXPR
, rhs1
);
3929 gsi_insert_before (gsi
, conv
, GSI_SAME_STMT
);
3930 gimple_assign_set_rhs1 (stmt
, tem
);
3931 fold_stmt (gsi
, follow_single_use_edges
);
3936 /* Simplify an internal fn call using ranges if possible. */
3939 vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator
*gsi
,
3942 enum tree_code subcode
;
3943 bool is_ubsan
= false;
3945 switch (gimple_call_internal_fn (stmt
))
3947 case IFN_UBSAN_CHECK_ADD
:
3948 subcode
= PLUS_EXPR
;
3951 case IFN_UBSAN_CHECK_SUB
:
3952 subcode
= MINUS_EXPR
;
3955 case IFN_UBSAN_CHECK_MUL
:
3956 subcode
= MULT_EXPR
;
3959 case IFN_ADD_OVERFLOW
:
3960 subcode
= PLUS_EXPR
;
3962 case IFN_SUB_OVERFLOW
:
3963 subcode
= MINUS_EXPR
;
3965 case IFN_MUL_OVERFLOW
:
3966 subcode
= MULT_EXPR
;
3972 tree op0
= gimple_call_arg (stmt
, 0);
3973 tree op1
= gimple_call_arg (stmt
, 1);
3977 type
= TREE_TYPE (op0
);
3978 if (VECTOR_TYPE_P (type
))
3981 else if (gimple_call_lhs (stmt
) == NULL_TREE
)
3984 type
= TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt
)));
3985 if (!check_for_binary_op_overflow (subcode
, type
, op0
, op1
, &ovf
)
3986 || (is_ubsan
&& ovf
))
3990 location_t loc
= gimple_location (stmt
);
3992 g
= gimple_build_assign (gimple_call_lhs (stmt
), subcode
, op0
, op1
);
3995 int prec
= TYPE_PRECISION (type
);
3998 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
3999 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
4000 utype
= build_nonstandard_integer_type (prec
, 1);
4001 if (TREE_CODE (op0
) == INTEGER_CST
)
4002 op0
= fold_convert (utype
, op0
);
4003 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op0
)))
4005 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op0
);
4006 gimple_set_location (g
, loc
);
4007 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4008 op0
= gimple_assign_lhs (g
);
4010 if (TREE_CODE (op1
) == INTEGER_CST
)
4011 op1
= fold_convert (utype
, op1
);
4012 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op1
)))
4014 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op1
);
4015 gimple_set_location (g
, loc
);
4016 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4017 op1
= gimple_assign_lhs (g
);
4019 g
= gimple_build_assign (make_ssa_name (utype
), subcode
, op0
, op1
);
4020 gimple_set_location (g
, loc
);
4021 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4024 g
= gimple_build_assign (make_ssa_name (type
), NOP_EXPR
,
4025 gimple_assign_lhs (g
));
4026 gimple_set_location (g
, loc
);
4027 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4029 g
= gimple_build_assign (gimple_call_lhs (stmt
), COMPLEX_EXPR
,
4030 gimple_assign_lhs (g
),
4031 build_int_cst (type
, ovf
));
4033 gimple_set_location (g
, loc
);
4034 gsi_replace (gsi
, g
, false);
4038 /* Return true if VAR is a two-valued variable. Set a and b with the
4039 two-values when it is true. Return false otherwise. */
4042 vr_values::two_valued_val_range_p (tree var
, tree
*a
, tree
*b
)
4044 value_range
*vr
= get_value_range (var
);
4045 if ((vr
->type
!= VR_RANGE
4046 && vr
->type
!= VR_ANTI_RANGE
)
4047 || TREE_CODE (vr
->min
) != INTEGER_CST
4048 || TREE_CODE (vr
->max
) != INTEGER_CST
)
4051 if (vr
->type
== VR_RANGE
4052 && wi::to_wide (vr
->max
) - wi::to_wide (vr
->min
) == 1)
4059 /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
4060 if (vr
->type
== VR_ANTI_RANGE
4061 && (wi::to_wide (vr
->min
)
4062 - wi::to_wide (vrp_val_min (TREE_TYPE (var
)))) == 1
4063 && (wi::to_wide (vrp_val_max (TREE_TYPE (var
)))
4064 - wi::to_wide (vr
->max
)) == 1)
4066 *a
= vrp_val_min (TREE_TYPE (var
));
4067 *b
= vrp_val_max (TREE_TYPE (var
));
4074 /* Simplify STMT using ranges if possible. */
4077 vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator
*gsi
)
4079 gimple
*stmt
= gsi_stmt (*gsi
);
4080 if (is_gimple_assign (stmt
))
4082 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
4083 tree rhs1
= gimple_assign_rhs1 (stmt
);
4084 tree rhs2
= gimple_assign_rhs2 (stmt
);
4085 tree lhs
= gimple_assign_lhs (stmt
);
4086 tree val1
= NULL_TREE
, val2
= NULL_TREE
;
4087 use_operand_p use_p
;
4092 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4094 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4098 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4100 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4102 if (TREE_CODE_CLASS (rhs_code
) == tcc_binary
4103 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4104 && ((TREE_CODE (rhs1
) == INTEGER_CST
4105 && TREE_CODE (rhs2
) == SSA_NAME
)
4106 || (TREE_CODE (rhs2
) == INTEGER_CST
4107 && TREE_CODE (rhs1
) == SSA_NAME
))
4108 && single_imm_use (lhs
, &use_p
, &use_stmt
)
4109 && gimple_code (use_stmt
) == GIMPLE_COND
)
4112 tree new_rhs1
= NULL_TREE
;
4113 tree new_rhs2
= NULL_TREE
;
4114 tree cmp_var
= NULL_TREE
;
4116 if (TREE_CODE (rhs2
) == SSA_NAME
4117 && two_valued_val_range_p (rhs2
, &val1
, &val2
))
4119 /* Optimize RHS1 OP [VAL1, VAL2]. */
4120 new_rhs1
= int_const_binop (rhs_code
, rhs1
, val1
);
4121 new_rhs2
= int_const_binop (rhs_code
, rhs1
, val2
);
4124 else if (TREE_CODE (rhs1
) == SSA_NAME
4125 && two_valued_val_range_p (rhs1
, &val1
, &val2
))
4127 /* Optimize [VAL1, VAL2] OP RHS2. */
4128 new_rhs1
= int_const_binop (rhs_code
, val1
, rhs2
);
4129 new_rhs2
= int_const_binop (rhs_code
, val2
, rhs2
);
4133 /* If we could not find two-vals or the optimzation is invalid as
4134 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4135 if (new_rhs1
&& new_rhs2
)
4137 tree cond
= build2 (EQ_EXPR
, boolean_type_node
, cmp_var
, val1
);
4138 gimple_assign_set_rhs_with_ops (gsi
,
4142 update_stmt (gsi_stmt (*gsi
));
4143 fold_stmt (gsi
, follow_single_use_edges
);
4152 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4153 if the RHS is zero or one, and the LHS are known to be boolean
4155 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4156 return simplify_truth_ops_using_ranges (gsi
, stmt
);
4159 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4160 and BIT_AND_EXPR respectively if the first operand is greater
4161 than zero and the second operand is an exact power of two.
4162 Also optimize TRUNC_MOD_EXPR away if the second operand is
4163 constant and the first operand already has the right value
4165 case TRUNC_DIV_EXPR
:
4166 case TRUNC_MOD_EXPR
:
4167 if ((TREE_CODE (rhs1
) == SSA_NAME
4168 || TREE_CODE (rhs1
) == INTEGER_CST
)
4169 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4170 return simplify_div_or_mod_using_ranges (gsi
, stmt
);
4173 /* Transform ABS (X) into X or -X as appropriate. */
4175 if (TREE_CODE (rhs1
) == SSA_NAME
4176 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4177 return simplify_abs_using_ranges (gsi
, stmt
);
4182 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4183 if all the bits being cleared are already cleared or
4184 all the bits being set are already set. */
4185 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4186 return simplify_bit_ops_using_ranges (gsi
, stmt
);
4190 if (TREE_CODE (rhs1
) == SSA_NAME
4191 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4192 return simplify_conversion_using_ranges (gsi
, stmt
);
4196 if (TREE_CODE (rhs1
) == SSA_NAME
4197 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4198 return simplify_float_conversion_using_ranges (gsi
, stmt
);
4203 return simplify_min_or_max_using_ranges (gsi
, stmt
);
4209 else if (gimple_code (stmt
) == GIMPLE_COND
)
4210 return simplify_cond_using_ranges_1 (as_a
<gcond
*> (stmt
));
4211 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
4212 return simplify_switch_using_ranges (as_a
<gswitch
*> (stmt
));
4213 else if (is_gimple_call (stmt
)
4214 && gimple_call_internal_p (stmt
))
4215 return simplify_internal_call_using_ranges (gsi
, stmt
);
4221 vr_values::set_vr_value (tree var
, value_range
*vr
)
4223 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4225 vr_value
[SSA_NAME_VERSION (var
)] = vr
;