1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2019 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"
52 /* Set value range VR to a non-negative range of type TYPE. */
55 set_value_range_to_nonnegative (value_range
*vr
, tree type
)
57 tree zero
= build_int_cst (type
, 0);
58 vr
->update (VR_RANGE
, zero
, vrp_val_max (type
));
61 /* Set value range VR to a range of a truthvalue of type TYPE. */
64 set_value_range_to_truthvalue (value_range
*vr
, tree type
)
66 if (TYPE_PRECISION (type
) == 1)
69 vr
->update (VR_RANGE
, build_int_cst (type
, 0), build_int_cst (type
, 1));
73 /* Return value range information for VAR.
75 If we have no values ranges recorded (ie, VRP is not running), then
76 return NULL. Otherwise create an empty range if none existed for VAR. */
79 vr_values::get_value_range (const_tree var
)
81 static const value_range
vr_const_varying (VR_VARYING
, NULL
, NULL
);
84 unsigned ver
= SSA_NAME_VERSION (var
);
86 /* If we have no recorded ranges, then return NULL. */
90 /* If we query the range for a new SSA name return an unmodifiable VARYING.
91 We should get here at most from the substitute-and-fold stage which
92 will never try to change values. */
93 if (ver
>= num_vr_values
)
94 return CONST_CAST (value_range
*, &vr_const_varying
);
100 /* After propagation finished do not allocate new value-ranges. */
101 if (values_propagated
)
102 return CONST_CAST (value_range
*, &vr_const_varying
);
104 /* Create a default value range. */
105 vr_value
[ver
] = vr
= vrp_value_range_pool
.allocate ();
106 vr
->set_undefined ();
108 /* If VAR is a default definition of a parameter, the variable can
109 take any value in VAR's type. */
110 if (SSA_NAME_IS_DEFAULT_DEF (var
))
112 sym
= SSA_NAME_VAR (var
);
113 if (TREE_CODE (sym
) == PARM_DECL
)
115 /* Try to use the "nonnull" attribute to create ~[0, 0]
116 anti-ranges for pointers. Note that this is only valid with
117 default definitions of PARM_DECLs. */
118 if (POINTER_TYPE_P (TREE_TYPE (sym
))
119 && (nonnull_arg_p (sym
)
120 || get_ptr_nonnull (var
)))
121 vr
->set_nonnull (TREE_TYPE (sym
));
122 else if (INTEGRAL_TYPE_P (TREE_TYPE (sym
)))
124 get_range_info (var
, *vr
);
125 if (vr
->undefined_p ())
131 else if (TREE_CODE (sym
) == RESULT_DECL
132 && DECL_BY_REFERENCE (sym
))
133 vr
->set_nonnull (TREE_TYPE (sym
));
139 /* Set value-ranges of all SSA names defined by STMT to varying. */
142 vr_values::set_defs_to_varying (gimple
*stmt
)
146 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
148 value_range
*vr
= get_value_range (def
);
149 /* Avoid writing to vr_const_varying get_value_range may return. */
150 if (!vr
->varying_p ())
155 /* Update the value range and equivalence set for variable VAR to
156 NEW_VR. Return true if NEW_VR is different from VAR's previous
159 NOTE: This function assumes that NEW_VR is a temporary value range
160 object created for the sole purpose of updating VAR's range. The
161 storage used by the equivalence set from NEW_VR will be freed by
162 this function. Do not call update_value_range when NEW_VR
163 is the range object associated with another SSA name. */
166 vr_values::update_value_range (const_tree var
, value_range
*new_vr
)
171 /* If there is a value-range on the SSA name from earlier analysis
173 if (INTEGRAL_TYPE_P (TREE_TYPE (var
)))
176 value_range_kind rtype
= get_range_info (var
, nr
);
177 if (rtype
== VR_RANGE
|| rtype
== VR_ANTI_RANGE
)
178 new_vr
->intersect (&nr
);
181 /* Update the value range, if necessary. */
182 old_vr
= get_value_range (var
);
183 is_new
= !old_vr
->equal_p (*new_vr
, /*ignore_equivs=*/false);
187 /* Do not allow transitions up the lattice. The following
188 is slightly more awkward than just new_vr->type < old_vr->type
189 because VR_RANGE and VR_ANTI_RANGE need to be considered
190 the same. We may not have is_new when transitioning to
191 UNDEFINED. If old_vr->type is VARYING, we shouldn't be
193 if (new_vr
->undefined_p ())
195 old_vr
->set_varying ();
196 new_vr
->set_varying ();
200 old_vr
->set (new_vr
->kind (),
201 new_vr
->min (), new_vr
->max (), new_vr
->equiv ());
204 new_vr
->equiv_clear ();
209 /* Return true if value range VR involves exactly one symbol SYM. */
212 symbolic_range_based_on_p (value_range_base
*vr
, const_tree sym
)
214 bool neg
, min_has_symbol
, max_has_symbol
;
217 if (is_gimple_min_invariant (vr
->min ()))
218 min_has_symbol
= false;
219 else if (get_single_symbol (vr
->min (), &neg
, &inv
) == sym
)
220 min_has_symbol
= true;
224 if (is_gimple_min_invariant (vr
->max ()))
225 max_has_symbol
= false;
226 else if (get_single_symbol (vr
->max (), &neg
, &inv
) == sym
)
227 max_has_symbol
= true;
231 return (min_has_symbol
|| max_has_symbol
);
234 /* Return true if the result of assignment STMT is know to be non-zero. */
237 gimple_assign_nonzero_p (gimple
*stmt
)
239 enum tree_code code
= gimple_assign_rhs_code (stmt
);
240 bool strict_overflow_p
;
241 switch (get_gimple_rhs_class (code
))
243 case GIMPLE_UNARY_RHS
:
244 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
245 gimple_expr_type (stmt
),
246 gimple_assign_rhs1 (stmt
),
248 case GIMPLE_BINARY_RHS
:
249 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
250 gimple_expr_type (stmt
),
251 gimple_assign_rhs1 (stmt
),
252 gimple_assign_rhs2 (stmt
),
254 case GIMPLE_TERNARY_RHS
:
256 case GIMPLE_SINGLE_RHS
:
257 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt
),
259 case GIMPLE_INVALID_RHS
:
266 /* Return true if STMT is known to compute a non-zero value. */
269 gimple_stmt_nonzero_p (gimple
*stmt
)
271 switch (gimple_code (stmt
))
274 return gimple_assign_nonzero_p (stmt
);
277 gcall
*call_stmt
= as_a
<gcall
*> (stmt
);
278 return (gimple_call_nonnull_result_p (call_stmt
)
279 || gimple_call_nonnull_arg (call_stmt
));
285 /* Like tree_expr_nonzero_p, but this function uses value ranges
289 vr_values::vrp_stmt_computes_nonzero (gimple
*stmt
)
291 if (gimple_stmt_nonzero_p (stmt
))
294 /* If we have an expression of the form &X->a, then the expression
295 is nonnull if X is nonnull. */
296 if (is_gimple_assign (stmt
)
297 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
299 tree expr
= gimple_assign_rhs1 (stmt
);
300 poly_int64 bitsize
, bitpos
;
303 int unsignedp
, reversep
, volatilep
;
304 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
305 &bitpos
, &offset
, &mode
, &unsignedp
,
306 &reversep
, &volatilep
);
308 if (base
!= NULL_TREE
309 && TREE_CODE (base
) == MEM_REF
310 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
312 poly_offset_int off
= 0;
313 bool off_cst
= false;
314 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
316 off
= mem_ref_offset (base
);
318 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
320 off
<<= LOG2_BITS_PER_UNIT
;
324 /* If &X->a is equal to X and X is ~[0, 0], the result is too.
325 For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
326 allow going from non-NULL pointer to NULL. */
327 if ((off_cst
&& known_eq (off
, 0))
328 || (flag_delete_null_pointer_checks
329 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))))
331 value_range
*vr
= get_value_range (TREE_OPERAND (base
, 0));
332 if (!range_includes_zero_p (vr
))
335 /* If MEM_REF has a "positive" offset, consider it non-NULL
336 always, for -fdelete-null-pointer-checks also "negative"
337 ones. Punt for unknown offsets (e.g. variable ones). */
338 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
341 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
349 /* Returns true if EXPR is a valid value (as expected by compare_values) --
350 a gimple invariant, or SSA_NAME +- CST. */
353 valid_value_p (tree expr
)
355 if (TREE_CODE (expr
) == SSA_NAME
)
358 if (TREE_CODE (expr
) == PLUS_EXPR
359 || TREE_CODE (expr
) == MINUS_EXPR
)
360 return (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
361 && TREE_CODE (TREE_OPERAND (expr
, 1)) == INTEGER_CST
);
363 return is_gimple_min_invariant (expr
);
366 /* If OP has a value range with a single constant value return that,
367 otherwise return NULL_TREE. This returns OP itself if OP is a
371 vr_values::op_with_constant_singleton_value_range (tree op
)
373 if (is_gimple_min_invariant (op
))
376 if (TREE_CODE (op
) != SSA_NAME
)
379 return value_range_constant_singleton (get_value_range (op
));
382 /* Return true if op is in a boolean [0, 1] value-range. */
385 vr_values::op_with_boolean_value_range_p (tree op
)
389 if (TYPE_PRECISION (TREE_TYPE (op
)) == 1)
392 if (integer_zerop (op
)
393 || integer_onep (op
))
396 if (TREE_CODE (op
) != SSA_NAME
)
399 vr
= get_value_range (op
);
400 return (vr
->kind () == VR_RANGE
401 && integer_zerop (vr
->min ())
402 && integer_onep (vr
->max ()));
405 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
406 true and store it in *VR_P. */
409 vr_values::extract_range_for_var_from_comparison_expr (tree var
,
410 enum tree_code cond_code
,
415 value_range
*limit_vr
;
416 type
= TREE_TYPE (var
);
418 /* For pointer arithmetic, we only keep track of pointer equality
419 and inequality. If we arrive here with unfolded conditions like
420 _1 > _1 do not derive anything. */
421 if ((POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
424 vr_p
->set_varying ();
428 /* If LIMIT is another SSA name and LIMIT has a range of its own,
429 try to use LIMIT's range to avoid creating symbolic ranges
431 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
433 /* LIMIT's range is only interesting if it has any useful information. */
435 || limit_vr
->undefined_p ()
436 || limit_vr
->varying_p ()
437 || (limit_vr
->symbolic_p ()
438 && ! (limit_vr
->kind () == VR_RANGE
439 && (limit_vr
->min () == limit_vr
->max ()
440 || operand_equal_p (limit_vr
->min (),
441 limit_vr
->max (), 0)))))
444 /* Initially, the new range has the same set of equivalences of
445 VAR's range. This will be revised before returning the final
446 value. Since assertions may be chained via mutually exclusive
447 predicates, we will need to trim the set of equivalences before
449 gcc_assert (vr_p
->equiv () == NULL
);
450 vr_p
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
452 /* Extract a new range based on the asserted comparison for VAR and
453 LIMIT's value range. Notice that if LIMIT has an anti-range, we
454 will only use it for equality comparisons (EQ_EXPR). For any
455 other kind of assertion, we cannot derive a range from LIMIT's
456 anti-range that can be used to describe the new range. For
457 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
458 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
459 no single range for x_2 that could describe LE_EXPR, so we might
460 as well build the range [b_4, +INF] for it.
461 One special case we handle is extracting a range from a
462 range test encoded as (unsigned)var + CST <= limit. */
463 if (TREE_CODE (op
) == NOP_EXPR
464 || TREE_CODE (op
) == PLUS_EXPR
)
466 if (TREE_CODE (op
) == PLUS_EXPR
)
468 min
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (TREE_OPERAND (op
, 1)),
469 TREE_OPERAND (op
, 1));
470 max
= int_const_binop (PLUS_EXPR
, limit
, min
);
471 op
= TREE_OPERAND (op
, 0);
475 min
= build_int_cst (TREE_TYPE (var
), 0);
479 /* Make sure to not set TREE_OVERFLOW on the final type
480 conversion. We are willingly interpreting large positive
481 unsigned values as negative signed values here. */
482 min
= force_fit_type (TREE_TYPE (var
), wi::to_widest (min
), 0, false);
483 max
= force_fit_type (TREE_TYPE (var
), wi::to_widest (max
), 0, false);
485 /* We can transform a max, min range to an anti-range or
486 vice-versa. Use set_and_canonicalize which does this for
488 if (cond_code
== LE_EXPR
)
489 vr_p
->set_and_canonicalize (VR_RANGE
, min
, max
, vr_p
->equiv ());
490 else if (cond_code
== GT_EXPR
)
491 vr_p
->set_and_canonicalize (VR_ANTI_RANGE
, min
, max
, vr_p
->equiv ());
495 else if (cond_code
== EQ_EXPR
)
497 enum value_range_kind range_type
;
501 range_type
= limit_vr
->kind ();
502 min
= limit_vr
->min ();
503 max
= limit_vr
->max ();
507 range_type
= VR_RANGE
;
512 vr_p
->update (range_type
, min
, max
);
514 /* When asserting the equality VAR == LIMIT and LIMIT is another
515 SSA name, the new range will also inherit the equivalence set
517 if (TREE_CODE (limit
) == SSA_NAME
)
518 vr_p
->equiv_add (limit
, get_value_range (limit
), &vrp_equiv_obstack
);
520 else if (cond_code
== NE_EXPR
)
522 /* As described above, when LIMIT's range is an anti-range and
523 this assertion is an inequality (NE_EXPR), then we cannot
524 derive anything from the anti-range. For instance, if
525 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
526 not imply that VAR's range is [0, 0]. So, in the case of
527 anti-ranges, we just assert the inequality using LIMIT and
530 If LIMIT_VR is a range, we can only use it to build a new
531 anti-range if LIMIT_VR is a single-valued range. For
532 instance, if LIMIT_VR is [0, 1], the predicate
533 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
534 Rather, it means that for value 0 VAR should be ~[0, 0]
535 and for value 1, VAR should be ~[1, 1]. We cannot
536 represent these ranges.
538 The only situation in which we can build a valid
539 anti-range is when LIMIT_VR is a single-valued range
540 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
541 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
543 && limit_vr
->kind () == VR_RANGE
544 && compare_values (limit_vr
->min (), limit_vr
->max ()) == 0)
546 min
= limit_vr
->min ();
547 max
= limit_vr
->max ();
551 /* In any other case, we cannot use LIMIT's range to build a
556 /* If MIN and MAX cover the whole range for their type, then
557 just use the original LIMIT. */
558 if (INTEGRAL_TYPE_P (type
)
559 && vrp_val_is_min (min
)
560 && vrp_val_is_max (max
))
563 vr_p
->set_and_canonicalize (VR_ANTI_RANGE
, min
, max
, vr_p
->equiv ());
565 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
567 min
= TYPE_MIN_VALUE (type
);
569 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
573 /* If LIMIT_VR is of the form [N1, N2], we need to build the
574 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
576 max
= limit_vr
->max ();
579 /* If the maximum value forces us to be out of bounds, simply punt.
580 It would be pointless to try and do anything more since this
581 all should be optimized away above us. */
582 if (cond_code
== LT_EXPR
583 && compare_values (max
, min
) == 0)
584 vr_p
->set_varying ();
587 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
588 if (cond_code
== LT_EXPR
)
590 if (TYPE_PRECISION (TREE_TYPE (max
)) == 1
591 && !TYPE_UNSIGNED (TREE_TYPE (max
)))
592 max
= fold_build2 (PLUS_EXPR
, TREE_TYPE (max
), max
,
593 build_int_cst (TREE_TYPE (max
), -1));
595 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max
), max
,
596 build_int_cst (TREE_TYPE (max
), 1));
597 /* Signal to compare_values_warnv this expr doesn't overflow. */
599 TREE_NO_WARNING (max
) = 1;
602 vr_p
->update (VR_RANGE
, min
, max
);
605 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
607 max
= TYPE_MAX_VALUE (type
);
609 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
613 /* If LIMIT_VR is of the form [N1, N2], we need to build the
614 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
616 min
= limit_vr
->min ();
619 /* If the minimum value forces us to be out of bounds, simply punt.
620 It would be pointless to try and do anything more since this
621 all should be optimized away above us. */
622 if (cond_code
== GT_EXPR
623 && compare_values (min
, max
) == 0)
624 vr_p
->set_varying ();
627 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
628 if (cond_code
== GT_EXPR
)
630 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
631 && !TYPE_UNSIGNED (TREE_TYPE (min
)))
632 min
= fold_build2 (MINUS_EXPR
, TREE_TYPE (min
), min
,
633 build_int_cst (TREE_TYPE (min
), -1));
635 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min
), min
,
636 build_int_cst (TREE_TYPE (min
), 1));
637 /* Signal to compare_values_warnv this expr doesn't overflow. */
639 TREE_NO_WARNING (min
) = 1;
642 vr_p
->update (VR_RANGE
, min
, max
);
648 /* Finally intersect the new range with what we already know about var. */
649 vr_p
->intersect (get_value_range (var
));
652 /* Extract value range information from an ASSERT_EXPR EXPR and store
656 vr_values::extract_range_from_assert (value_range
*vr_p
, tree expr
)
658 tree var
= ASSERT_EXPR_VAR (expr
);
659 tree cond
= ASSERT_EXPR_COND (expr
);
661 enum tree_code cond_code
;
662 gcc_assert (COMPARISON_CLASS_P (cond
));
664 /* Find VAR in the ASSERT_EXPR conditional. */
665 if (var
== TREE_OPERAND (cond
, 0)
666 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PLUS_EXPR
667 || TREE_CODE (TREE_OPERAND (cond
, 0)) == NOP_EXPR
)
669 /* If the predicate is of the form VAR COMP LIMIT, then we just
670 take LIMIT from the RHS and use the same comparison code. */
671 cond_code
= TREE_CODE (cond
);
672 limit
= TREE_OPERAND (cond
, 1);
673 op
= TREE_OPERAND (cond
, 0);
677 /* If the predicate is of the form LIMIT COMP VAR, then we need
678 to flip around the comparison code to create the proper range
680 cond_code
= swap_tree_comparison (TREE_CODE (cond
));
681 limit
= TREE_OPERAND (cond
, 0);
682 op
= TREE_OPERAND (cond
, 1);
684 extract_range_for_var_from_comparison_expr (var
, cond_code
, op
,
688 /* Extract range information from SSA name VAR and store it in VR. If
689 VAR has an interesting range, use it. Otherwise, create the
690 range [VAR, VAR] and return it. This is useful in situations where
691 we may have conditionals testing values of VARYING names. For
698 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
702 vr_values::extract_range_from_ssa_name (value_range
*vr
, tree var
)
704 value_range
*var_vr
= get_value_range (var
);
706 if (!var_vr
->varying_p ())
707 vr
->deep_copy (var_vr
);
711 vr
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
714 /* Extract range information from a binary expression OP0 CODE OP1 based on
715 the ranges of each of its operands with resulting type EXPR_TYPE.
716 The resulting range is stored in *VR. */
719 vr_values::extract_range_from_binary_expr (value_range
*vr
,
721 tree expr_type
, tree op0
, tree op1
)
723 /* Get value ranges for each operand. For constant operands, create
724 a new value range with the operand to simplify processing. */
725 value_range_base vr0
, vr1
;
726 if (TREE_CODE (op0
) == SSA_NAME
)
727 vr0
= *(get_value_range (op0
));
728 else if (is_gimple_min_invariant (op0
))
733 if (TREE_CODE (op1
) == SSA_NAME
)
734 vr1
= *(get_value_range (op1
));
735 else if (is_gimple_min_invariant (op1
))
740 /* If one argument is varying, we can sometimes still deduce a
741 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
742 if (INTEGRAL_TYPE_P (TREE_TYPE (op0
))
743 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0
)))
745 if (vr0
.varying_p () && !vr1
.varying_p ())
746 vr0
= value_range (VR_RANGE
,
747 vrp_val_min (expr_type
),
748 vrp_val_max (expr_type
));
749 else if (vr1
.varying_p () && !vr0
.varying_p ())
750 vr1
= value_range (VR_RANGE
,
751 vrp_val_min (expr_type
),
752 vrp_val_max (expr_type
));
755 ::extract_range_from_binary_expr (vr
, code
, expr_type
, &vr0
, &vr1
);
757 /* Set value_range for n in following sequence:
758 def = __builtin_memchr (arg, 0, sz)
760 Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
763 && code
== POINTER_DIFF_EXPR
764 && TREE_CODE (op0
) == SSA_NAME
765 && TREE_CODE (op1
) == SSA_NAME
)
767 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
768 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
769 gcall
*call_stmt
= NULL
;
771 if (TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
772 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
773 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
774 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
775 && (call_stmt
= dyn_cast
<gcall
*>(SSA_NAME_DEF_STMT (op0
)))
776 && gimple_call_builtin_p (call_stmt
, BUILT_IN_MEMCHR
)
777 && operand_equal_p (op0
, gimple_call_lhs (call_stmt
), 0)
778 && operand_equal_p (op1
, gimple_call_arg (call_stmt
, 0), 0)
779 && integer_zerop (gimple_call_arg (call_stmt
, 1)))
781 tree max
= vrp_val_max (ptrdiff_type_node
);
782 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
783 tree range_min
= build_zero_cst (expr_type
);
784 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
785 vr
->set (VR_RANGE
, range_min
, range_max
);
790 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
791 and based on the other operand, for example if it was deduced from a
792 symbolic comparison. When a bound of the range of the first operand
793 is invariant, we set the corresponding bound of the new range to INF
794 in order to avoid recursing on the range of the second operand. */
796 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
797 && TREE_CODE (op1
) == SSA_NAME
798 && vr0
.kind () == VR_RANGE
799 && symbolic_range_based_on_p (&vr0
, op1
))
801 const bool minus_p
= (code
== MINUS_EXPR
);
804 /* Try with VR0 and [-INF, OP1]. */
805 if (is_gimple_min_invariant (minus_p
? vr0
.max () : vr0
.min ()))
806 n_vr1
.set (VR_RANGE
, vrp_val_min (expr_type
), op1
);
808 /* Try with VR0 and [OP1, +INF]. */
809 else if (is_gimple_min_invariant (minus_p
? vr0
.min () : vr0
.max ()))
810 n_vr1
.set (VR_RANGE
, op1
, vrp_val_max (expr_type
));
812 /* Try with VR0 and [OP1, OP1]. */
814 n_vr1
.set (VR_RANGE
, op1
, op1
);
816 ::extract_range_from_binary_expr (vr
, code
, expr_type
, &vr0
, &n_vr1
);
820 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
821 && TREE_CODE (op0
) == SSA_NAME
822 && vr1
.kind () == VR_RANGE
823 && symbolic_range_based_on_p (&vr1
, op0
))
825 const bool minus_p
= (code
== MINUS_EXPR
);
828 /* Try with [-INF, OP0] and VR1. */
829 if (is_gimple_min_invariant (minus_p
? vr1
.max () : vr1
.min ()))
830 n_vr0
.set (VR_RANGE
, vrp_val_min (expr_type
), op0
);
832 /* Try with [OP0, +INF] and VR1. */
833 else if (is_gimple_min_invariant (minus_p
? vr1
.min (): vr1
.max ()))
834 n_vr0
.set (VR_RANGE
, op0
, vrp_val_max (expr_type
));
836 /* Try with [OP0, OP0] and VR1. */
840 ::extract_range_from_binary_expr (vr
, code
, expr_type
, &n_vr0
, &vr1
);
843 /* If we didn't derive a range for MINUS_EXPR, and
844 op1's range is ~[op0,op0] or vice-versa, then we
845 can derive a non-null range. This happens often for
846 pointer subtraction. */
848 && (code
== MINUS_EXPR
|| code
== POINTER_DIFF_EXPR
)
849 && TREE_CODE (op0
) == SSA_NAME
850 && ((vr0
.kind () == VR_ANTI_RANGE
852 && vr0
.min () == vr0
.max ())
853 || (vr1
.kind () == VR_ANTI_RANGE
855 && vr1
.min () == vr1
.max ())))
856 vr
->set_nonnull (expr_type
);
859 /* Extract range information from a unary expression CODE OP0 based on
860 the range of its operand with resulting type TYPE.
861 The resulting range is stored in *VR. */
864 vr_values::extract_range_from_unary_expr (value_range
*vr
, enum tree_code code
,
867 value_range_base vr0
;
869 /* Get value ranges for the operand. For constant operands, create
870 a new value range with the operand to simplify processing. */
871 if (TREE_CODE (op0
) == SSA_NAME
)
872 vr0
= *(get_value_range (op0
));
873 else if (is_gimple_min_invariant (op0
))
878 ::extract_range_from_unary_expr (vr
, code
, type
, &vr0
, TREE_TYPE (op0
));
882 /* Extract range information from a conditional expression STMT based on
883 the ranges of each of its operands and the expression code. */
886 vr_values::extract_range_from_cond_expr (value_range
*vr
, gassign
*stmt
)
888 /* Get value ranges for each operand. For constant operands, create
889 a new value range with the operand to simplify processing. */
890 tree op0
= gimple_assign_rhs2 (stmt
);
892 value_range
*vr0
= &tem0
;
893 if (TREE_CODE (op0
) == SSA_NAME
)
894 vr0
= get_value_range (op0
);
895 else if (is_gimple_min_invariant (op0
))
900 tree op1
= gimple_assign_rhs3 (stmt
);
902 value_range
*vr1
= &tem1
;
903 if (TREE_CODE (op1
) == SSA_NAME
)
904 vr1
= get_value_range (op1
);
905 else if (is_gimple_min_invariant (op1
))
910 /* The resulting value range is the union of the operand ranges */
916 /* Extract range information from a comparison expression EXPR based
917 on the range of its operand and the expression code. */
920 vr_values::extract_range_from_comparison (value_range
*vr
, enum tree_code code
,
921 tree type
, tree op0
, tree op1
)
926 val
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, false, &sop
,
930 /* Since this expression was found on the RHS of an assignment,
931 its type may be different from _Bool. Convert VAL to EXPR's
933 val
= fold_convert (type
, val
);
934 if (is_gimple_min_invariant (val
))
937 vr
->update (VR_RANGE
, val
, val
);
940 /* The result of a comparison is always true or false. */
941 set_value_range_to_truthvalue (vr
, type
);
944 /* Helper function for simplify_internal_call_using_ranges and
945 extract_range_basic. Return true if OP0 SUBCODE OP1 for
946 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
947 always overflow. Set *OVF to true if it is known to always
951 vr_values::check_for_binary_op_overflow (enum tree_code subcode
, tree type
,
952 tree op0
, tree op1
, bool *ovf
)
954 value_range_base vr0
, vr1
;
955 if (TREE_CODE (op0
) == SSA_NAME
)
956 vr0
= *get_value_range (op0
);
957 else if (TREE_CODE (op0
) == INTEGER_CST
)
962 if (TREE_CODE (op1
) == SSA_NAME
)
963 vr1
= *get_value_range (op1
);
964 else if (TREE_CODE (op1
) == INTEGER_CST
)
969 tree vr0min
= vr0
.min (), vr0max
= vr0
.max ();
970 tree vr1min
= vr1
.min (), vr1max
= vr1
.max ();
971 if (!range_int_cst_p (&vr0
)
972 || TREE_OVERFLOW (vr0min
)
973 || TREE_OVERFLOW (vr0max
))
975 vr0min
= vrp_val_min (TREE_TYPE (op0
));
976 vr0max
= vrp_val_max (TREE_TYPE (op0
));
978 if (!range_int_cst_p (&vr1
)
979 || TREE_OVERFLOW (vr1min
)
980 || TREE_OVERFLOW (vr1max
))
982 vr1min
= vrp_val_min (TREE_TYPE (op1
));
983 vr1max
= vrp_val_max (TREE_TYPE (op1
));
985 *ovf
= arith_overflowed_p (subcode
, type
, vr0min
,
986 subcode
== MINUS_EXPR
? vr1max
: vr1min
);
987 if (arith_overflowed_p (subcode
, type
, vr0max
,
988 subcode
== MINUS_EXPR
? vr1min
: vr1max
) != *ovf
)
990 if (subcode
== MULT_EXPR
)
992 if (arith_overflowed_p (subcode
, type
, vr0min
, vr1max
) != *ovf
993 || arith_overflowed_p (subcode
, type
, vr0max
, vr1min
) != *ovf
)
998 /* So far we found that there is an overflow on the boundaries.
999 That doesn't prove that there is an overflow even for all values
1000 in between the boundaries. For that compute widest_int range
1001 of the result and see if it doesn't overlap the range of
1003 widest_int wmin
, wmax
;
1006 w
[0] = wi::to_widest (vr0min
);
1007 w
[1] = wi::to_widest (vr0max
);
1008 w
[2] = wi::to_widest (vr1min
);
1009 w
[3] = wi::to_widest (vr1max
);
1010 for (i
= 0; i
< 4; i
++)
1016 wt
= wi::add (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1019 wt
= wi::sub (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1022 wt
= wi::mul (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1034 wmin
= wi::smin (wmin
, wt
);
1035 wmax
= wi::smax (wmax
, wt
);
1038 /* The result of op0 CODE op1 is known to be in range
1040 widest_int wtmin
= wi::to_widest (vrp_val_min (type
));
1041 widest_int wtmax
= wi::to_widest (vrp_val_max (type
));
1042 /* If all values in [wmin, wmax] are smaller than
1043 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1044 the arithmetic operation will always overflow. */
1045 if (wmax
< wtmin
|| wmin
> wtmax
)
1052 /* Try to derive a nonnegative or nonzero range out of STMT relying
1053 primarily on generic routines in fold in conjunction with range data.
1054 Store the result in *VR */
1057 vr_values::extract_range_basic (value_range
*vr
, gimple
*stmt
)
1060 tree type
= gimple_expr_type (stmt
);
1062 if (is_gimple_call (stmt
))
1065 int mini
, maxi
, zerov
= 0, prec
;
1066 enum tree_code subcode
= ERROR_MARK
;
1067 combined_fn cfn
= gimple_call_combined_fn (stmt
);
1068 scalar_int_mode mode
;
1072 case CFN_BUILT_IN_CONSTANT_P
:
1073 /* If the call is __builtin_constant_p and the argument is a
1074 function parameter resolve it to false. This avoids bogus
1075 array bound warnings.
1076 ??? We could do this as early as inlining is finished. */
1077 arg
= gimple_call_arg (stmt
, 0);
1078 if (TREE_CODE (arg
) == SSA_NAME
1079 && SSA_NAME_IS_DEFAULT_DEF (arg
)
1080 && TREE_CODE (SSA_NAME_VAR (arg
)) == PARM_DECL
1081 && cfun
->after_inlining
)
1083 vr
->set_null (type
);
1087 /* Both __builtin_ffs* and __builtin_popcount return
1091 arg
= gimple_call_arg (stmt
, 0);
1092 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1095 if (TREE_CODE (arg
) == SSA_NAME
)
1097 value_range
*vr0
= get_value_range (arg
);
1098 /* If arg is non-zero, then ffs or popcount are non-zero. */
1099 if (range_includes_zero_p (vr0
) == 0)
1101 /* If some high bits are known to be zero,
1102 we can decrease the maximum. */
1103 if (vr0
->kind () == VR_RANGE
1104 && TREE_CODE (vr0
->max ()) == INTEGER_CST
1105 && !operand_less_p (vr0
->min (),
1106 build_zero_cst (TREE_TYPE (vr0
->min ()))))
1107 maxi
= tree_floor_log2 (vr0
->max ()) + 1;
1110 /* __builtin_parity* returns [0, 1]. */
1115 /* __builtin_c[lt]z* return [0, prec-1], except for
1116 when the argument is 0, but that is undefined behavior.
1117 On many targets where the CLZ RTL or optab value is defined
1118 for 0 the value is prec, so include that in the range
1121 arg
= gimple_call_arg (stmt
, 0);
1122 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1125 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1126 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
1127 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
)
1128 /* Handle only the single common value. */
1130 /* Magic value to give up, unless vr0 proves
1133 if (TREE_CODE (arg
) == SSA_NAME
)
1135 value_range
*vr0
= get_value_range (arg
);
1136 /* From clz of VR_RANGE minimum we can compute
1138 if (vr0
->kind () == VR_RANGE
1139 && TREE_CODE (vr0
->min ()) == INTEGER_CST
)
1141 maxi
= prec
- 1 - tree_floor_log2 (vr0
->min ());
1145 else if (vr0
->kind () == VR_ANTI_RANGE
1146 && integer_zerop (vr0
->min ()))
1153 /* From clz of VR_RANGE maximum we can compute
1155 if (vr0
->kind () == VR_RANGE
1156 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1158 mini
= prec
- 1 - tree_floor_log2 (vr0
->max ());
1166 /* __builtin_ctz* return [0, prec-1], except for
1167 when the argument is 0, but that is undefined behavior.
1168 If there is a ctz optab for this mode and
1169 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1170 otherwise just assume 0 won't be seen. */
1172 arg
= gimple_call_arg (stmt
, 0);
1173 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1176 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1177 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1178 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
))
1180 /* Handle only the two common values. */
1183 else if (zerov
== prec
)
1186 /* Magic value to give up, unless vr0 proves
1190 if (TREE_CODE (arg
) == SSA_NAME
)
1192 value_range
*vr0
= get_value_range (arg
);
1193 /* If arg is non-zero, then use [0, prec - 1]. */
1194 if ((vr0
->kind () == VR_RANGE
1195 && integer_nonzerop (vr0
->min ()))
1196 || (vr0
->kind () == VR_ANTI_RANGE
1197 && integer_zerop (vr0
->min ())))
1202 /* If some high bits are known to be zero,
1203 we can decrease the result maximum. */
1204 if (vr0
->kind () == VR_RANGE
1205 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1207 maxi
= tree_floor_log2 (vr0
->max ());
1208 /* For vr0 [0, 0] give up. */
1216 /* __builtin_clrsb* returns [0, prec-1]. */
1218 arg
= gimple_call_arg (stmt
, 0);
1219 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1224 vr
->set (VR_RANGE
, build_int_cst (type
, mini
),
1225 build_int_cst (type
, maxi
));
1227 case CFN_UBSAN_CHECK_ADD
:
1228 subcode
= PLUS_EXPR
;
1230 case CFN_UBSAN_CHECK_SUB
:
1231 subcode
= MINUS_EXPR
;
1233 case CFN_UBSAN_CHECK_MUL
:
1234 subcode
= MULT_EXPR
;
1236 case CFN_GOACC_DIM_SIZE
:
1237 case CFN_GOACC_DIM_POS
:
1238 /* Optimizing these two internal functions helps the loop
1239 optimizer eliminate outer comparisons. Size is [1,N]
1240 and pos is [0,N-1]. */
1242 bool is_pos
= cfn
== CFN_GOACC_DIM_POS
;
1243 int axis
= oacc_get_ifn_dim_arg (stmt
);
1244 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1247 /* If it's dynamic, the backend might know a hardware
1249 size
= targetm
.goacc
.dim_limit (axis
);
1251 tree type
= TREE_TYPE (gimple_call_lhs (stmt
));
1252 vr
->set(VR_RANGE
, build_int_cst (type
, is_pos
? 0 : 1),
1254 ? build_int_cst (type
, size
- is_pos
) : vrp_val_max (type
));
1257 case CFN_BUILT_IN_STRLEN
:
1258 if (tree lhs
= gimple_call_lhs (stmt
))
1259 if (ptrdiff_type_node
1260 && (TYPE_PRECISION (ptrdiff_type_node
)
1261 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1263 tree type
= TREE_TYPE (lhs
);
1264 tree max
= vrp_val_max (ptrdiff_type_node
);
1265 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1266 tree range_min
= build_zero_cst (type
);
1267 tree range_max
= wide_int_to_tree (type
, wmax
- 1);
1268 vr
->set (VR_RANGE
, range_min
, range_max
);
1275 if (subcode
!= ERROR_MARK
)
1277 bool saved_flag_wrapv
= flag_wrapv
;
1278 /* Pretend the arithmetics is wrapping. If there is
1279 any overflow, we'll complain, but will actually do
1280 wrapping operation. */
1282 extract_range_from_binary_expr (vr
, subcode
, type
,
1283 gimple_call_arg (stmt
, 0),
1284 gimple_call_arg (stmt
, 1));
1285 flag_wrapv
= saved_flag_wrapv
;
1287 /* If for both arguments vrp_valueize returned non-NULL,
1288 this should have been already folded and if not, it
1289 wasn't folded because of overflow. Avoid removing the
1290 UBSAN_CHECK_* calls in that case. */
1291 if (vr
->kind () == VR_RANGE
1292 && (vr
->min () == vr
->max ()
1293 || operand_equal_p (vr
->min (), vr
->max (), 0)))
1298 /* Handle extraction of the two results (result of arithmetics and
1299 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1300 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1301 else if (is_gimple_assign (stmt
)
1302 && (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
1303 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
)
1304 && INTEGRAL_TYPE_P (type
))
1306 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1307 tree op
= gimple_assign_rhs1 (stmt
);
1308 if (TREE_CODE (op
) == code
&& TREE_CODE (TREE_OPERAND (op
, 0)) == SSA_NAME
)
1310 gimple
*g
= SSA_NAME_DEF_STMT (TREE_OPERAND (op
, 0));
1311 if (is_gimple_call (g
) && gimple_call_internal_p (g
))
1313 enum tree_code subcode
= ERROR_MARK
;
1314 switch (gimple_call_internal_fn (g
))
1316 case IFN_ADD_OVERFLOW
:
1317 subcode
= PLUS_EXPR
;
1319 case IFN_SUB_OVERFLOW
:
1320 subcode
= MINUS_EXPR
;
1322 case IFN_MUL_OVERFLOW
:
1323 subcode
= MULT_EXPR
;
1325 case IFN_ATOMIC_COMPARE_EXCHANGE
:
1326 if (code
== IMAGPART_EXPR
)
1328 /* This is the boolean return value whether compare and
1329 exchange changed anything or not. */
1330 vr
->set (VR_RANGE
, build_int_cst (type
, 0),
1331 build_int_cst (type
, 1));
1338 if (subcode
!= ERROR_MARK
)
1340 tree op0
= gimple_call_arg (g
, 0);
1341 tree op1
= gimple_call_arg (g
, 1);
1342 if (code
== IMAGPART_EXPR
)
1345 if (check_for_binary_op_overflow (subcode
, type
,
1347 vr
->set (build_int_cst (type
, ovf
));
1348 else if (TYPE_PRECISION (type
) == 1
1349 && !TYPE_UNSIGNED (type
))
1352 vr
->set (VR_RANGE
, build_int_cst (type
, 0),
1353 build_int_cst (type
, 1));
1355 else if (types_compatible_p (type
, TREE_TYPE (op0
))
1356 && types_compatible_p (type
, TREE_TYPE (op1
)))
1358 bool saved_flag_wrapv
= flag_wrapv
;
1359 /* Pretend the arithmetics is wrapping. If there is
1360 any overflow, IMAGPART_EXPR will be set. */
1362 extract_range_from_binary_expr (vr
, subcode
, type
,
1364 flag_wrapv
= saved_flag_wrapv
;
1368 value_range vr0
, vr1
;
1369 bool saved_flag_wrapv
= flag_wrapv
;
1370 /* Pretend the arithmetics is wrapping. If there is
1371 any overflow, IMAGPART_EXPR will be set. */
1373 extract_range_from_unary_expr (&vr0
, NOP_EXPR
,
1375 extract_range_from_unary_expr (&vr1
, NOP_EXPR
,
1377 ::extract_range_from_binary_expr (vr
, subcode
, type
,
1379 flag_wrapv
= saved_flag_wrapv
;
1386 if (INTEGRAL_TYPE_P (type
)
1387 && gimple_stmt_nonnegative_warnv_p (stmt
, &sop
))
1388 set_value_range_to_nonnegative (vr
, type
);
1389 else if (vrp_stmt_computes_nonzero (stmt
))
1390 vr
->set_nonnull (type
);
1396 /* Try to compute a useful range out of assignment STMT and store it
1400 vr_values::extract_range_from_assignment (value_range
*vr
, gassign
*stmt
)
1402 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1404 if (code
== ASSERT_EXPR
)
1405 extract_range_from_assert (vr
, gimple_assign_rhs1 (stmt
));
1406 else if (code
== SSA_NAME
)
1407 extract_range_from_ssa_name (vr
, gimple_assign_rhs1 (stmt
));
1408 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
1409 extract_range_from_binary_expr (vr
, gimple_assign_rhs_code (stmt
),
1410 gimple_expr_type (stmt
),
1411 gimple_assign_rhs1 (stmt
),
1412 gimple_assign_rhs2 (stmt
));
1413 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1414 extract_range_from_unary_expr (vr
, gimple_assign_rhs_code (stmt
),
1415 gimple_expr_type (stmt
),
1416 gimple_assign_rhs1 (stmt
));
1417 else if (code
== COND_EXPR
)
1418 extract_range_from_cond_expr (vr
, stmt
);
1419 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1420 extract_range_from_comparison (vr
, gimple_assign_rhs_code (stmt
),
1421 gimple_expr_type (stmt
),
1422 gimple_assign_rhs1 (stmt
),
1423 gimple_assign_rhs2 (stmt
));
1424 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1425 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1426 vr
->set (gimple_assign_rhs1 (stmt
));
1430 if (vr
->varying_p ())
1431 extract_range_basic (vr
, stmt
);
1434 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1436 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1437 all the values in the ranges.
1439 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1441 - Return NULL_TREE if it is not always possible to determine the
1442 value of the comparison.
1444 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1445 assumed signed overflow is undefined. */
1449 compare_ranges (enum tree_code comp
, value_range
*vr0
, value_range
*vr1
,
1450 bool *strict_overflow_p
)
1452 /* VARYING or UNDEFINED ranges cannot be compared. */
1453 if (vr0
->varying_p ()
1454 || vr0
->undefined_p ()
1455 || vr1
->varying_p ()
1456 || vr1
->undefined_p ())
1459 /* Anti-ranges need to be handled separately. */
1460 if (vr0
->kind () == VR_ANTI_RANGE
|| vr1
->kind () == VR_ANTI_RANGE
)
1462 /* If both are anti-ranges, then we cannot compute any
1464 if (vr0
->kind () == VR_ANTI_RANGE
&& vr1
->kind () == VR_ANTI_RANGE
)
1467 /* These comparisons are never statically computable. */
1474 /* Equality can be computed only between a range and an
1475 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1476 if (vr0
->kind () == VR_RANGE
)
1478 /* To simplify processing, make VR0 the anti-range. */
1479 value_range
*tmp
= vr0
;
1484 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1486 if (compare_values_warnv (vr0
->min (), vr1
->min (), strict_overflow_p
) == 0
1487 && compare_values_warnv (vr0
->max (), vr1
->max (), strict_overflow_p
) == 0)
1488 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1493 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1494 operands around and change the comparison code. */
1495 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1497 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1498 std::swap (vr0
, vr1
);
1501 if (comp
== EQ_EXPR
)
1503 /* Equality may only be computed if both ranges represent
1504 exactly one value. */
1505 if (compare_values_warnv (vr0
->min (), vr0
->max (), strict_overflow_p
) == 0
1506 && compare_values_warnv (vr1
->min (), vr1
->max (), strict_overflow_p
) == 0)
1508 int cmp_min
= compare_values_warnv (vr0
->min (), vr1
->min (),
1510 int cmp_max
= compare_values_warnv (vr0
->max (), vr1
->max (),
1512 if (cmp_min
== 0 && cmp_max
== 0)
1513 return boolean_true_node
;
1514 else if (cmp_min
!= -2 && cmp_max
!= -2)
1515 return boolean_false_node
;
1517 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1518 else if (compare_values_warnv (vr0
->min (), vr1
->max (),
1519 strict_overflow_p
) == 1
1520 || compare_values_warnv (vr1
->min (), vr0
->max (),
1521 strict_overflow_p
) == 1)
1522 return boolean_false_node
;
1526 else if (comp
== NE_EXPR
)
1530 /* If VR0 is completely to the left or completely to the right
1531 of VR1, they are always different. Notice that we need to
1532 make sure that both comparisons yield similar results to
1533 avoid comparing values that cannot be compared at
1535 cmp1
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1536 cmp2
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1537 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1538 return boolean_true_node
;
1540 /* If VR0 and VR1 represent a single value and are identical,
1542 else if (compare_values_warnv (vr0
->min (), vr0
->max (),
1543 strict_overflow_p
) == 0
1544 && compare_values_warnv (vr1
->min (), vr1
->max (),
1545 strict_overflow_p
) == 0
1546 && compare_values_warnv (vr0
->min (), vr1
->min (),
1547 strict_overflow_p
) == 0
1548 && compare_values_warnv (vr0
->max (), vr1
->max (),
1549 strict_overflow_p
) == 0)
1550 return boolean_false_node
;
1552 /* Otherwise, they may or may not be different. */
1556 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1560 /* If VR0 is to the left of VR1, return true. */
1561 tst
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1562 if ((comp
== LT_EXPR
&& tst
== -1)
1563 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1564 return boolean_true_node
;
1566 /* If VR0 is to the right of VR1, return false. */
1567 tst
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1568 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1569 || (comp
== LE_EXPR
&& tst
== 1))
1570 return boolean_false_node
;
1572 /* Otherwise, we don't know. */
1579 /* Given a value range VR, a value VAL and a comparison code COMP, return
1580 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1581 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1582 always returns false. Return NULL_TREE if it is not always
1583 possible to determine the value of the comparison. Also set
1584 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1585 assumed signed overflow is undefined. */
1588 compare_range_with_value (enum tree_code comp
, value_range
*vr
, tree val
,
1589 bool *strict_overflow_p
)
1591 if (vr
->varying_p () || vr
->undefined_p ())
1594 /* Anti-ranges need to be handled separately. */
1595 if (vr
->kind () == VR_ANTI_RANGE
)
1597 /* For anti-ranges, the only predicates that we can compute at
1598 compile time are equality and inequality. */
1605 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1606 if (value_inside_range (val
, vr
->min (), vr
->max ()) == 1)
1607 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1612 if (comp
== EQ_EXPR
)
1614 /* EQ_EXPR may only be computed if VR represents exactly
1616 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0)
1618 int cmp
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1620 return boolean_true_node
;
1621 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1622 return boolean_false_node
;
1624 else if (compare_values_warnv (val
, vr
->min (), strict_overflow_p
) == -1
1625 || compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1)
1626 return boolean_false_node
;
1630 else if (comp
== NE_EXPR
)
1632 /* If VAL is not inside VR, then they are always different. */
1633 if (compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1
1634 || compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 1)
1635 return boolean_true_node
;
1637 /* If VR represents exactly one value equal to VAL, then return
1639 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0
1640 && compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 0)
1641 return boolean_false_node
;
1643 /* Otherwise, they may or may not be different. */
1646 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1650 /* If VR is to the left of VAL, return true. */
1651 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1652 if ((comp
== LT_EXPR
&& tst
== -1)
1653 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1654 return boolean_true_node
;
1656 /* If VR is to the right of VAL, return false. */
1657 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1658 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1659 || (comp
== LE_EXPR
&& tst
== 1))
1660 return boolean_false_node
;
1662 /* Otherwise, we don't know. */
1665 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1669 /* If VR is to the right of VAL, return true. */
1670 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1671 if ((comp
== GT_EXPR
&& tst
== 1)
1672 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1673 return boolean_true_node
;
1675 /* If VR is to the left of VAL, return false. */
1676 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1677 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1678 || (comp
== GE_EXPR
&& tst
== -1))
1679 return boolean_false_node
;
1681 /* Otherwise, we don't know. */
1687 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1688 would be profitable to adjust VR using scalar evolution information
1689 for VAR. If so, update VR with the new limits. */
1692 vr_values::adjust_range_with_scev (value_range
*vr
, struct loop
*loop
,
1693 gimple
*stmt
, tree var
)
1695 tree init
, step
, chrec
, tmin
, tmax
, min
, max
, type
, tem
;
1696 enum ev_direction dir
;
1698 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1699 better opportunities than a regular range, but I'm not sure. */
1700 if (vr
->kind () == VR_ANTI_RANGE
)
1703 chrec
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, var
));
1705 /* Like in PR19590, scev can return a constant function. */
1706 if (is_gimple_min_invariant (chrec
))
1712 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1715 init
= initial_condition_in_loop_num (chrec
, loop
->num
);
1716 tem
= op_with_constant_singleton_value_range (init
);
1719 step
= evolution_part_in_loop_num (chrec
, loop
->num
);
1720 tem
= op_with_constant_singleton_value_range (step
);
1724 /* If STEP is symbolic, we can't know whether INIT will be the
1725 minimum or maximum value in the range. Also, unless INIT is
1726 a simple expression, compare_values and possibly other functions
1727 in tree-vrp won't be able to handle it. */
1728 if (step
== NULL_TREE
1729 || !is_gimple_min_invariant (step
)
1730 || !valid_value_p (init
))
1733 dir
= scev_direction (chrec
);
1734 if (/* Do not adjust ranges if we do not know whether the iv increases
1735 or decreases, ... */
1736 dir
== EV_DIR_UNKNOWN
1737 /* ... or if it may wrap. */
1738 || scev_probably_wraps_p (NULL_TREE
, init
, step
, stmt
,
1739 get_chrec_loop (chrec
), true))
1742 type
= TREE_TYPE (var
);
1743 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1744 tmin
= lower_bound_in_type (type
, type
);
1746 tmin
= TYPE_MIN_VALUE (type
);
1747 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1748 tmax
= upper_bound_in_type (type
, type
);
1750 tmax
= TYPE_MAX_VALUE (type
);
1752 /* Try to use estimated number of iterations for the loop to constrain the
1753 final value in the evolution. */
1754 if (TREE_CODE (step
) == INTEGER_CST
1755 && is_gimple_val (init
)
1756 && (TREE_CODE (init
) != SSA_NAME
1757 || get_value_range (init
)->kind () == VR_RANGE
))
1761 /* We are only entering here for loop header PHI nodes, so using
1762 the number of latch executions is the correct thing to use. */
1763 if (max_loop_iterations (loop
, &nit
))
1766 signop sgn
= TYPE_SIGN (TREE_TYPE (step
));
1767 wi::overflow_type overflow
;
1769 widest_int wtmp
= wi::mul (wi::to_widest (step
), nit
, sgn
,
1771 /* If the multiplication overflowed we can't do a meaningful
1772 adjustment. Likewise if the result doesn't fit in the type
1773 of the induction variable. For a signed type we have to
1774 check whether the result has the expected signedness which
1775 is that of the step as number of iterations is unsigned. */
1777 && wi::fits_to_tree_p (wtmp
, TREE_TYPE (init
))
1779 || wi::gts_p (wtmp
, 0) == wi::gts_p (wi::to_wide (step
), 0)))
1781 tem
= wide_int_to_tree (TREE_TYPE (init
), wtmp
);
1782 extract_range_from_binary_expr (&maxvr
, PLUS_EXPR
,
1783 TREE_TYPE (init
), init
, tem
);
1784 /* Likewise if the addition did. */
1785 if (maxvr
.kind () == VR_RANGE
)
1787 value_range_base initvr
;
1789 if (TREE_CODE (init
) == SSA_NAME
)
1790 initvr
= *(get_value_range (init
));
1791 else if (is_gimple_min_invariant (init
))
1796 /* Check if init + nit * step overflows. Though we checked
1797 scev {init, step}_loop doesn't wrap, it is not enough
1798 because the loop may exit immediately. Overflow could
1799 happen in the plus expression in this case. */
1800 if ((dir
== EV_DIR_DECREASES
1801 && compare_values (maxvr
.min (), initvr
.min ()) != -1)
1802 || (dir
== EV_DIR_GROWS
1803 && compare_values (maxvr
.max (), initvr
.max ()) != 1))
1806 tmin
= maxvr
.min ();
1807 tmax
= maxvr
.max ();
1813 if (vr
->varying_p () || vr
->undefined_p ())
1818 /* For VARYING or UNDEFINED ranges, just about anything we get
1819 from scalar evolutions should be better. */
1821 if (dir
== EV_DIR_DECREASES
)
1826 else if (vr
->kind () == VR_RANGE
)
1831 if (dir
== EV_DIR_DECREASES
)
1833 /* INIT is the maximum value. If INIT is lower than VR->MAX ()
1834 but no smaller than VR->MIN (), set VR->MAX () to INIT. */
1835 if (compare_values (init
, max
) == -1)
1838 /* According to the loop information, the variable does not
1840 if (compare_values (min
, tmin
) == -1)
1846 /* If INIT is bigger than VR->MIN (), set VR->MIN () to INIT. */
1847 if (compare_values (init
, min
) == 1)
1850 if (compare_values (tmax
, max
) == -1)
1857 /* If we just created an invalid range with the minimum
1858 greater than the maximum, we fail conservatively.
1859 This should happen only in unreachable
1860 parts of code, or for invalid programs. */
1861 if (compare_values (min
, max
) == 1)
1864 /* Even for valid range info, sometimes overflow flag will leak in.
1865 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1867 if (TREE_OVERFLOW_P (min
))
1868 min
= drop_tree_overflow (min
);
1869 if (TREE_OVERFLOW_P (max
))
1870 max
= drop_tree_overflow (max
);
1872 vr
->update (VR_RANGE
, min
, max
);
1875 /* Dump value ranges of all SSA_NAMEs to FILE. */
1878 vr_values::dump_all_value_ranges (FILE *file
)
1882 for (i
= 0; i
< num_vr_values
; i
++)
1886 print_generic_expr (file
, ssa_name (i
));
1887 fprintf (file
, ": ");
1888 dump_value_range (file
, vr_value
[i
]);
1889 fprintf (file
, "\n");
1893 fprintf (file
, "\n");
1896 /* Initialize VRP lattice. */
1898 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
1900 values_propagated
= false;
1901 num_vr_values
= num_ssa_names
;
1902 vr_value
= XCNEWVEC (value_range
*, num_vr_values
);
1903 vr_phi_edge_counts
= XCNEWVEC (int, num_ssa_names
);
1904 bitmap_obstack_initialize (&vrp_equiv_obstack
);
1905 to_remove_edges
= vNULL
;
1906 to_update_switch_stmts
= vNULL
;
1909 /* Free VRP lattice. */
1911 vr_values::~vr_values ()
1913 /* Free allocated memory. */
1915 free (vr_phi_edge_counts
);
1916 bitmap_obstack_release (&vrp_equiv_obstack
);
1917 vrp_value_range_pool
.release ();
1919 /* So that we can distinguish between VRP data being available
1920 and not available. */
1922 vr_phi_edge_counts
= NULL
;
1924 /* If there are entries left in TO_REMOVE_EDGES or TO_UPDATE_SWITCH_STMTS
1925 then an EVRP client did not clean up properly. Catch it now rather
1926 than seeing something more obscure later. */
1927 gcc_assert (to_remove_edges
.is_empty ()
1928 && to_update_switch_stmts
.is_empty ());
1933 static class vr_values
*x_vr_values
;
1935 /* Return the singleton value-range for NAME or NAME. */
1938 vrp_valueize (tree name
)
1940 if (TREE_CODE (name
) == SSA_NAME
)
1942 value_range
*vr
= x_vr_values
->get_value_range (name
);
1943 if (vr
->kind () == VR_RANGE
1944 && (TREE_CODE (vr
->min ()) == SSA_NAME
1945 || is_gimple_min_invariant (vr
->min ()))
1946 && vrp_operand_equal_p (vr
->min (), vr
->max ()))
1952 /* Return the singleton value-range for NAME if that is a constant
1953 but signal to not follow SSA edges. */
1956 vrp_valueize_1 (tree name
)
1958 if (TREE_CODE (name
) == SSA_NAME
)
1960 /* If the definition may be simulated again we cannot follow
1961 this SSA edge as the SSA propagator does not necessarily
1962 re-visit the use. */
1963 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1964 if (!gimple_nop_p (def_stmt
)
1965 && prop_simulate_again_p (def_stmt
))
1967 value_range
*vr
= x_vr_values
->get_value_range (name
);
1969 if (vr
->singleton_p (&singleton
))
1975 /* Given STMT, an assignment or call, return its LHS if the type
1976 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
1979 get_output_for_vrp (gimple
*stmt
)
1981 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
1984 /* We only keep track of ranges in integral and pointer types. */
1985 tree lhs
= gimple_get_lhs (stmt
);
1986 if (TREE_CODE (lhs
) == SSA_NAME
1987 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1988 /* It is valid to have NULL MIN/MAX values on a type. See
1989 build_range_type. */
1990 && TYPE_MIN_VALUE (TREE_TYPE (lhs
))
1991 && TYPE_MAX_VALUE (TREE_TYPE (lhs
)))
1992 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
1998 /* Visit assignment STMT. If it produces an interesting range, record
1999 the range in VR and set LHS to OUTPUT_P. */
2002 vr_values::vrp_visit_assignment_or_call (gimple
*stmt
, tree
*output_p
,
2005 tree lhs
= get_output_for_vrp (stmt
);
2008 /* We only keep track of ranges in integral and pointer types. */
2011 enum gimple_code code
= gimple_code (stmt
);
2013 /* Try folding the statement to a constant first. */
2015 tree tem
= gimple_fold_stmt_to_constant_1 (stmt
, vrp_valueize
,
2020 if (TREE_CODE (tem
) == SSA_NAME
2021 && (SSA_NAME_IS_DEFAULT_DEF (tem
)
2022 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem
))))
2024 extract_range_from_ssa_name (vr
, tem
);
2027 else if (is_gimple_min_invariant (tem
))
2033 /* Then dispatch to value-range extracting functions. */
2034 if (code
== GIMPLE_CALL
)
2035 extract_range_basic (vr
, stmt
);
2037 extract_range_from_assignment (vr
, as_a
<gassign
*> (stmt
));
2041 /* Helper that gets the value range of the SSA_NAME with version I
2042 or a symbolic range containing the SSA_NAME only if the value range
2043 is varying or undefined. Uses TEM as storage for the alternate range. */
2046 vr_values::get_vr_for_comparison (int i
, value_range
*tem
)
2048 /* Shallow-copy equiv bitmap. */
2049 value_range
*vr
= get_value_range (ssa_name (i
));
2051 /* If name N_i does not have a valid range, use N_i as its own
2052 range. This allows us to compare against names that may
2053 have N_i in their ranges. */
2054 if (vr
->varying_p () || vr
->undefined_p ())
2056 tem
->set (ssa_name (i
));
2063 /* Compare all the value ranges for names equivalent to VAR with VAL
2064 using comparison code COMP. Return the same value returned by
2065 compare_range_with_value, including the setting of
2066 *STRICT_OVERFLOW_P. */
2069 vr_values::compare_name_with_value (enum tree_code comp
, tree var
, tree val
,
2070 bool *strict_overflow_p
, bool use_equiv_p
)
2076 int used_strict_overflow
;
2078 value_range
*equiv_vr
, tem_vr
;
2080 /* Get the set of equivalences for VAR. */
2081 e
= get_value_range (var
)->equiv ();
2083 /* Start at -1. Set it to 0 if we do a comparison without relying
2084 on overflow, or 1 if all comparisons rely on overflow. */
2085 used_strict_overflow
= -1;
2087 /* Compare vars' value range with val. */
2088 equiv_vr
= get_vr_for_comparison (SSA_NAME_VERSION (var
), &tem_vr
);
2090 retval
= compare_range_with_value (comp
, equiv_vr
, val
, &sop
);
2092 used_strict_overflow
= sop
? 1 : 0;
2094 /* If the equiv set is empty we have done all work we need to do. */
2098 && used_strict_overflow
> 0)
2099 *strict_overflow_p
= true;
2103 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2105 tree name
= ssa_name (i
);
2110 && ! SSA_NAME_IS_DEFAULT_DEF (name
)
2111 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name
)))
2114 equiv_vr
= get_vr_for_comparison (i
, &tem_vr
);
2116 t
= compare_range_with_value (comp
, equiv_vr
, val
, &sop
);
2119 /* If we get different answers from different members
2120 of the equivalence set this check must be in a dead
2121 code region. Folding it to a trap representation
2122 would be correct here. For now just return don't-know. */
2132 used_strict_overflow
= 0;
2133 else if (used_strict_overflow
< 0)
2134 used_strict_overflow
= 1;
2139 && used_strict_overflow
> 0)
2140 *strict_overflow_p
= true;
2146 /* Given a comparison code COMP and names N1 and N2, compare all the
2147 ranges equivalent to N1 against all the ranges equivalent to N2
2148 to determine the value of N1 COMP N2. Return the same value
2149 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2150 whether we relied on undefined signed overflow in the comparison. */
2154 vr_values::compare_names (enum tree_code comp
, tree n1
, tree n2
,
2155 bool *strict_overflow_p
)
2159 bitmap_iterator bi1
, bi2
;
2161 int used_strict_overflow
;
2162 static bitmap_obstack
*s_obstack
= NULL
;
2163 static bitmap s_e1
= NULL
, s_e2
= NULL
;
2165 /* Compare the ranges of every name equivalent to N1 against the
2166 ranges of every name equivalent to N2. */
2167 e1
= get_value_range (n1
)->equiv ();
2168 e2
= get_value_range (n2
)->equiv ();
2170 /* Use the fake bitmaps if e1 or e2 are not available. */
2171 if (s_obstack
== NULL
)
2173 s_obstack
= XNEW (bitmap_obstack
);
2174 bitmap_obstack_initialize (s_obstack
);
2175 s_e1
= BITMAP_ALLOC (s_obstack
);
2176 s_e2
= BITMAP_ALLOC (s_obstack
);
2183 /* Add N1 and N2 to their own set of equivalences to avoid
2184 duplicating the body of the loop just to check N1 and N2
2186 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2187 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2189 /* If the equivalence sets have a common intersection, then the two
2190 names can be compared without checking their ranges. */
2191 if (bitmap_intersect_p (e1
, e2
))
2193 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2194 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2196 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2198 : boolean_false_node
;
2201 /* Start at -1. Set it to 0 if we do a comparison without relying
2202 on overflow, or 1 if all comparisons rely on overflow. */
2203 used_strict_overflow
= -1;
2205 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2206 N2 to their own set of equivalences to avoid duplicating the body
2207 of the loop just to check N1 and N2 ranges. */
2208 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2210 if (! ssa_name (i1
))
2213 value_range tem_vr1
;
2214 value_range
*vr1
= get_vr_for_comparison (i1
, &tem_vr1
);
2216 t
= retval
= NULL_TREE
;
2217 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2219 if (! ssa_name (i2
))
2224 value_range tem_vr2
;
2225 value_range
*vr2
= get_vr_for_comparison (i2
, &tem_vr2
);
2227 t
= compare_ranges (comp
, vr1
, vr2
, &sop
);
2230 /* If we get different answers from different members
2231 of the equivalence set this check must be in a dead
2232 code region. Folding it to a trap representation
2233 would be correct here. For now just return don't-know. */
2237 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2238 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2244 used_strict_overflow
= 0;
2245 else if (used_strict_overflow
< 0)
2246 used_strict_overflow
= 1;
2252 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2253 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2254 if (used_strict_overflow
> 0)
2255 *strict_overflow_p
= true;
2260 /* None of the equivalent ranges are useful in computing this
2262 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2263 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2267 /* Helper function for vrp_evaluate_conditional_warnv & other
2271 vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2272 (enum tree_code code
, tree op0
, tree op1
, bool * strict_overflow_p
)
2274 value_range
*vr0
, *vr1
;
2276 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
2277 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
2279 tree res
= NULL_TREE
;
2281 res
= compare_ranges (code
, vr0
, vr1
, strict_overflow_p
);
2283 res
= compare_range_with_value (code
, vr0
, op1
, strict_overflow_p
);
2285 res
= (compare_range_with_value
2286 (swap_tree_comparison (code
), vr1
, op0
, strict_overflow_p
));
2290 /* Helper function for vrp_evaluate_conditional_warnv. */
2293 vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code
,
2296 bool *strict_overflow_p
,
2301 *only_ranges
= true;
2303 /* We only deal with integral and pointer types. */
2304 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2305 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
2308 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2309 as a simple equality test, then prefer that over its current form
2312 An overflow test which collapses to an equality test can always be
2313 expressed as a comparison of one argument against zero. Overflow
2314 occurs when the chosen argument is zero and does not occur if the
2315 chosen argument is not zero. */
2317 if (overflow_comparison_p (code
, op0
, op1
, use_equiv_p
, &x
))
2319 wide_int max
= wi::max_value (TYPE_PRECISION (TREE_TYPE (op0
)), UNSIGNED
);
2320 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2321 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2322 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2323 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2324 if (integer_zerop (x
))
2327 code
= (code
== LT_EXPR
|| code
== LE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2329 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2330 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2331 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2332 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2333 else if (wi::to_wide (x
) == max
- 1)
2336 op1
= wide_int_to_tree (TREE_TYPE (op0
), 0);
2337 code
= (code
== GT_EXPR
|| code
== GE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2341 value_range vro
, vri
;
2342 if (code
== GT_EXPR
|| code
== GE_EXPR
)
2344 vro
.set (VR_ANTI_RANGE
, TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2345 vri
.set (VR_RANGE
, TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2347 else if (code
== LT_EXPR
|| code
== LE_EXPR
)
2349 vro
.set (VR_RANGE
, TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2350 vri
.set (VR_ANTI_RANGE
, TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2354 value_range
*vr0
= get_value_range (op0
);
2355 /* If vro, the range for OP0 to pass the overflow test, has
2356 no intersection with *vr0, OP0's known range, then the
2357 overflow test can't pass, so return the node for false.
2358 If it is the inverted range, vri, that has no
2359 intersection, then the overflow test must pass, so return
2360 the node for true. In other cases, we could proceed with
2361 a simplified condition comparing OP0 and X, with LE_EXPR
2362 for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
2363 the comments next to the enclosing if suggest it's not
2364 generally profitable to do so. */
2365 vro
.intersect (vr0
);
2366 if (vro
.undefined_p ())
2367 return boolean_false_node
;
2368 vri
.intersect (vr0
);
2369 if (vri
.undefined_p ())
2370 return boolean_true_node
;
2374 if ((ret
= vrp_evaluate_conditional_warnv_with_ops_using_ranges
2375 (code
, op0
, op1
, strict_overflow_p
)))
2378 *only_ranges
= false;
2379 /* Do not use compare_names during propagation, it's quadratic. */
2380 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
2382 return compare_names (code
, op0
, op1
, strict_overflow_p
);
2383 else if (TREE_CODE (op0
) == SSA_NAME
)
2384 return compare_name_with_value (code
, op0
, op1
,
2385 strict_overflow_p
, use_equiv_p
);
2386 else if (TREE_CODE (op1
) == SSA_NAME
)
2387 return compare_name_with_value (swap_tree_comparison (code
), op1
, op0
,
2388 strict_overflow_p
, use_equiv_p
);
2392 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2393 information. Return NULL if the conditional cannot be evaluated.
2394 The ranges of all the names equivalent with the operands in COND
2395 will be used when trying to compute the value. If the result is
2396 based on undefined signed overflow, issue a warning if
2400 vr_values::vrp_evaluate_conditional (tree_code code
, tree op0
,
2401 tree op1
, gimple
*stmt
)
2407 /* Some passes and foldings leak constants with overflow flag set
2408 into the IL. Avoid doing wrong things with these and bail out. */
2409 if ((TREE_CODE (op0
) == INTEGER_CST
2410 && TREE_OVERFLOW (op0
))
2411 || (TREE_CODE (op1
) == INTEGER_CST
2412 && TREE_OVERFLOW (op1
)))
2416 ret
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, true, &sop
,
2421 enum warn_strict_overflow_code wc
;
2422 const char* warnmsg
;
2424 if (is_gimple_min_invariant (ret
))
2426 wc
= WARN_STRICT_OVERFLOW_CONDITIONAL
;
2427 warnmsg
= G_("assuming signed overflow does not occur when "
2428 "simplifying conditional to constant");
2432 wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
2433 warnmsg
= G_("assuming signed overflow does not occur when "
2434 "simplifying conditional");
2437 if (issue_strict_overflow_warning (wc
))
2439 location_t location
;
2441 if (!gimple_has_location (stmt
))
2442 location
= input_location
;
2444 location
= gimple_location (stmt
);
2445 warning_at (location
, OPT_Wstrict_overflow
, "%s", warnmsg
);
2449 if (warn_type_limits
2450 && ret
&& only_ranges
2451 && TREE_CODE_CLASS (code
) == tcc_comparison
2452 && TREE_CODE (op0
) == SSA_NAME
)
2454 /* If the comparison is being folded and the operand on the LHS
2455 is being compared against a constant value that is outside of
2456 the natural range of OP0's type, then the predicate will
2457 always fold regardless of the value of OP0. If -Wtype-limits
2458 was specified, emit a warning. */
2459 tree type
= TREE_TYPE (op0
);
2460 value_range
*vr0
= get_value_range (op0
);
2462 if (vr0
->kind () == VR_RANGE
2463 && INTEGRAL_TYPE_P (type
)
2464 && vrp_val_is_min (vr0
->min ())
2465 && vrp_val_is_max (vr0
->max ())
2466 && is_gimple_min_invariant (op1
))
2468 location_t location
;
2470 if (!gimple_has_location (stmt
))
2471 location
= input_location
;
2473 location
= gimple_location (stmt
);
2475 warning_at (location
, OPT_Wtype_limits
,
2477 ? G_("comparison always false "
2478 "due to limited range of data type")
2479 : G_("comparison always true "
2480 "due to limited range of data type"));
2488 /* Visit conditional statement STMT. If we can determine which edge
2489 will be taken out of STMT's basic block, record it in
2490 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2493 vr_values::vrp_visit_cond_stmt (gcond
*stmt
, edge
*taken_edge_p
)
2497 *taken_edge_p
= NULL
;
2499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2504 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
2505 print_gimple_stmt (dump_file
, stmt
, 0);
2506 fprintf (dump_file
, "\nWith known ranges\n");
2508 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
2510 fprintf (dump_file
, "\t");
2511 print_generic_expr (dump_file
, use
);
2512 fprintf (dump_file
, ": ");
2513 dump_value_range (dump_file
, vr_value
[SSA_NAME_VERSION (use
)]);
2516 fprintf (dump_file
, "\n");
2519 /* Compute the value of the predicate COND by checking the known
2520 ranges of each of its operands.
2522 Note that we cannot evaluate all the equivalent ranges here
2523 because those ranges may not yet be final and with the current
2524 propagation strategy, we cannot determine when the value ranges
2525 of the names in the equivalence set have changed.
2527 For instance, given the following code fragment
2531 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2535 Assume that on the first visit to i_14, i_5 has the temporary
2536 range [8, 8] because the second argument to the PHI function is
2537 not yet executable. We derive the range ~[0, 0] for i_14 and the
2538 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2539 the first time, since i_14 is equivalent to the range [8, 8], we
2540 determine that the predicate is always false.
2542 On the next round of propagation, i_13 is determined to be
2543 VARYING, which causes i_5 to drop down to VARYING. So, another
2544 visit to i_14 is scheduled. In this second visit, we compute the
2545 exact same range and equivalence set for i_14, namely ~[0, 0] and
2546 { i_5 }. But we did not have the previous range for i_5
2547 registered, so vrp_visit_assignment thinks that the range for
2548 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2549 is not visited again, which stops propagation from visiting
2550 statements in the THEN clause of that if().
2552 To properly fix this we would need to keep the previous range
2553 value for the names in the equivalence set. This way we would've
2554 discovered that from one visit to the other i_5 changed from
2555 range [8, 8] to VR_VARYING.
2557 However, fixing this apparent limitation may not be worth the
2558 additional checking. Testing on several code bases (GCC, DLV,
2559 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2560 4 more predicates folded in SPEC. */
2563 val
= vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt
),
2564 gimple_cond_lhs (stmt
),
2565 gimple_cond_rhs (stmt
),
2568 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
2570 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2572 fprintf (dump_file
, "\nPredicate evaluates to: ");
2573 if (val
== NULL_TREE
)
2574 fprintf (dump_file
, "DON'T KNOW\n");
2576 print_generic_stmt (dump_file
, val
);
2580 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2581 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2582 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2583 Returns true if the default label is not needed. */
2586 find_case_label_ranges (gswitch
*stmt
, value_range
*vr
, size_t *min_idx1
,
2587 size_t *max_idx1
, size_t *min_idx2
,
2591 unsigned int n
= gimple_switch_num_labels (stmt
);
2593 tree case_low
, case_high
;
2594 tree min
= vr
->min (), max
= vr
->max ();
2596 gcc_checking_assert (!vr
->varying_p () && !vr
->undefined_p ());
2598 take_default
= !find_case_label_range (stmt
, min
, max
, &i
, &j
);
2600 /* Set second range to empty. */
2604 if (vr
->kind () == VR_RANGE
)
2608 return !take_default
;
2611 /* Set first range to all case labels. */
2618 /* Make sure all the values of case labels [i , j] are contained in
2619 range [MIN, MAX]. */
2620 case_low
= CASE_LOW (gimple_switch_label (stmt
, i
));
2621 case_high
= CASE_HIGH (gimple_switch_label (stmt
, j
));
2622 if (tree_int_cst_compare (case_low
, min
) < 0)
2624 if (case_high
!= NULL_TREE
2625 && tree_int_cst_compare (max
, case_high
) < 0)
2631 /* If the range spans case labels [i, j], the corresponding anti-range spans
2632 the labels [1, i - 1] and [j + 1, n - 1]. */
2658 /* Visit switch statement STMT. If we can determine which edge
2659 will be taken out of STMT's basic block, record it in
2660 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2663 vr_values::vrp_visit_switch_stmt (gswitch
*stmt
, edge
*taken_edge_p
)
2667 size_t i
= 0, j
= 0, k
, l
;
2670 *taken_edge_p
= NULL
;
2671 op
= gimple_switch_index (stmt
);
2672 if (TREE_CODE (op
) != SSA_NAME
)
2675 vr
= get_value_range (op
);
2676 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2678 fprintf (dump_file
, "\nVisiting switch expression with operand ");
2679 print_generic_expr (dump_file
, op
);
2680 fprintf (dump_file
, " with known range ");
2681 dump_value_range (dump_file
, vr
);
2682 fprintf (dump_file
, "\n");
2685 if (vr
->undefined_p ()
2687 || vr
->symbolic_p ())
2690 /* Find the single edge that is taken from the switch expression. */
2691 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
2693 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2697 gcc_assert (take_default
);
2698 val
= gimple_switch_default_label (stmt
);
2702 /* Check if labels with index i to j and maybe the default label
2703 are all reaching the same label. */
2705 val
= gimple_switch_label (stmt
, i
);
2707 && CASE_LABEL (gimple_switch_default_label (stmt
))
2708 != CASE_LABEL (val
))
2710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2711 fprintf (dump_file
, " not a single destination for this "
2715 for (++i
; i
<= j
; ++i
)
2717 if (CASE_LABEL (gimple_switch_label (stmt
, i
)) != CASE_LABEL (val
))
2719 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2720 fprintf (dump_file
, " not a single destination for this "
2727 if (CASE_LABEL (gimple_switch_label (stmt
, k
)) != CASE_LABEL (val
))
2729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2730 fprintf (dump_file
, " not a single destination for this "
2737 *taken_edge_p
= find_edge (gimple_bb (stmt
),
2738 label_to_block (cfun
, CASE_LABEL (val
)));
2740 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2742 fprintf (dump_file
, " will take edge to ");
2743 print_generic_stmt (dump_file
, CASE_LABEL (val
));
2748 /* Evaluate statement STMT. If the statement produces a useful range,
2749 set VR and corepsponding OUTPUT_P.
2751 If STMT is a conditional branch and we can determine its truth
2752 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2755 vr_values::extract_range_from_stmt (gimple
*stmt
, edge
*taken_edge_p
,
2756 tree
*output_p
, value_range
*vr
)
2759 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2761 fprintf (dump_file
, "\nVisiting statement:\n");
2762 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
2765 if (!stmt_interesting_for_vrp (stmt
))
2766 gcc_assert (stmt_ends_bb_p (stmt
));
2767 else if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
2768 vrp_visit_assignment_or_call (stmt
, output_p
, vr
);
2769 else if (gimple_code (stmt
) == GIMPLE_COND
)
2770 vrp_visit_cond_stmt (as_a
<gcond
*> (stmt
), taken_edge_p
);
2771 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2772 vrp_visit_switch_stmt (as_a
<gswitch
*> (stmt
), taken_edge_p
);
2775 /* Visit all arguments for PHI node PHI that flow through executable
2776 edges. If a valid value range can be derived from all the incoming
2777 value ranges, set a new range in VR_RESULT. */
2780 vr_values::extract_range_from_phi_node (gphi
*phi
, value_range
*vr_result
)
2783 tree lhs
= PHI_RESULT (phi
);
2784 value_range
*lhs_vr
= get_value_range (lhs
);
2786 int edges
, old_edges
;
2789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2791 fprintf (dump_file
, "\nVisiting PHI node: ");
2792 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
2795 bool may_simulate_backedge_again
= false;
2797 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2799 edge e
= gimple_phi_arg_edge (phi
, i
);
2801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2804 " Argument #%d (%d -> %d %sexecutable)\n",
2805 (int) i
, e
->src
->index
, e
->dest
->index
,
2806 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
2809 if (e
->flags
& EDGE_EXECUTABLE
)
2811 tree arg
= PHI_ARG_DEF (phi
, i
);
2812 value_range vr_arg_tem
;
2813 value_range
*vr_arg
= &vr_arg_tem
;
2817 if (TREE_CODE (arg
) == SSA_NAME
)
2819 /* See if we are eventually going to change one of the args. */
2820 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
2821 if (! gimple_nop_p (def_stmt
)
2822 && prop_simulate_again_p (def_stmt
)
2823 && e
->flags
& EDGE_DFS_BACK
)
2824 may_simulate_backedge_again
= true;
2826 value_range
*vr_arg_
= get_value_range (arg
);
2827 /* Do not allow equivalences or symbolic ranges to leak in from
2828 backedges. That creates invalid equivalencies.
2829 See PR53465 and PR54767. */
2830 if (e
->flags
& EDGE_DFS_BACK
)
2832 if (!vr_arg_
->varying_p () && !vr_arg_
->undefined_p ())
2834 vr_arg_tem
.set (vr_arg_
->kind (), vr_arg_
->min (),
2835 vr_arg_
->max (), NULL
);
2836 if (vr_arg_tem
.symbolic_p ())
2837 vr_arg_tem
.set_varying ();
2842 /* If the non-backedge arguments range is VR_VARYING then
2843 we can still try recording a simple equivalence. */
2844 else if (vr_arg_
->varying_p ())
2845 vr_arg_tem
.set (arg
);
2851 if (TREE_OVERFLOW_P (arg
))
2852 arg
= drop_tree_overflow (arg
);
2854 vr_arg_tem
.set (arg
);
2857 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2859 fprintf (dump_file
, "\t");
2860 print_generic_expr (dump_file
, arg
, dump_flags
);
2861 fprintf (dump_file
, ": ");
2862 dump_value_range (dump_file
, vr_arg
);
2863 fprintf (dump_file
, "\n");
2867 vr_result
->deep_copy (vr_arg
);
2869 vr_result
->union_ (vr_arg
);
2872 if (vr_result
->varying_p ())
2877 if (vr_result
->varying_p ())
2879 else if (vr_result
->undefined_p ())
2882 old_edges
= vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)];
2883 vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)] = edges
;
2885 /* To prevent infinite iterations in the algorithm, derive ranges
2886 when the new value is slightly bigger or smaller than the
2887 previous one. We don't do this if we have seen a new executable
2888 edge; this helps us avoid an infinity for conditionals
2889 which are not in a loop. If the old value-range was VR_UNDEFINED
2890 use the updated range and iterate one more time. If we will not
2891 simulate this PHI again via the backedge allow us to iterate. */
2893 && gimple_phi_num_args (phi
) > 1
2894 && edges
== old_edges
2895 && !lhs_vr
->undefined_p ()
2896 && may_simulate_backedge_again
)
2898 /* Compare old and new ranges, fall back to varying if the
2899 values are not comparable. */
2900 int cmp_min
= compare_values (lhs_vr
->min (), vr_result
->min ());
2903 int cmp_max
= compare_values (lhs_vr
->max (), vr_result
->max ());
2907 /* For non VR_RANGE or for pointers fall back to varying if
2908 the range changed. */
2909 if ((lhs_vr
->kind () != VR_RANGE
|| vr_result
->kind () != VR_RANGE
2910 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2911 && (cmp_min
!= 0 || cmp_max
!= 0))
2914 /* If the new minimum is larger than the previous one
2915 retain the old value. If the new minimum value is smaller
2916 than the previous one and not -INF go all the way to -INF + 1.
2917 In the first case, to avoid infinite bouncing between different
2918 minimums, and in the other case to avoid iterating millions of
2919 times to reach -INF. Going to -INF + 1 also lets the following
2920 iteration compute whether there will be any overflow, at the
2921 expense of one additional iteration. */
2922 tree new_min
= vr_result
->min ();
2923 tree new_max
= vr_result
->max ();
2925 new_min
= lhs_vr
->min ();
2926 else if (cmp_min
> 0
2927 && (TREE_CODE (vr_result
->min ()) != INTEGER_CST
2928 || tree_int_cst_lt (vrp_val_min (vr_result
->type ()),
2929 vr_result
->min ())))
2930 new_min
= int_const_binop (PLUS_EXPR
,
2931 vrp_val_min (vr_result
->type ()),
2932 build_int_cst (vr_result
->type (), 1));
2934 /* Similarly for the maximum value. */
2936 new_max
= lhs_vr
->max ();
2937 else if (cmp_max
< 0
2938 && (TREE_CODE (vr_result
->max ()) != INTEGER_CST
2939 || tree_int_cst_lt (vr_result
->max (),
2940 vrp_val_max (vr_result
->type ()))))
2941 new_max
= int_const_binop (MINUS_EXPR
,
2942 vrp_val_max (vr_result
->type ()),
2943 build_int_cst (vr_result
->type (), 1));
2945 vr_result
->update (vr_result
->kind (), new_min
, new_max
);
2947 /* If we dropped either bound to +-INF then if this is a loop
2948 PHI node SCEV may known more about its value-range. */
2949 if (cmp_min
> 0 || cmp_min
< 0
2950 || cmp_max
< 0 || cmp_max
> 0)
2953 goto infinite_check
;
2959 vr_result
->set_varying ();
2962 /* If this is a loop PHI node SCEV may known more about its value-range.
2963 scev_check can be reached from two paths, one is a fall through from above
2964 "varying" label, the other is direct goto from code block which tries to
2965 avoid infinite simulation. */
2966 if (scev_initialized_p ()
2967 && (l
= loop_containing_stmt (phi
))
2968 && l
->header
== gimple_bb (phi
))
2969 adjust_range_with_scev (vr_result
, l
, phi
, lhs
);
2972 /* If we will end up with a (-INF, +INF) range, set it to
2973 VARYING. Same if the previous max value was invalid for
2974 the type and we end up with vr_result.min > vr_result.max. */
2975 if ((!vr_result
->varying_p () && !vr_result
->undefined_p ())
2976 && !((vrp_val_is_max (vr_result
->max ()) && vrp_val_is_min (vr_result
->min ()))
2977 || compare_values (vr_result
->min (), vr_result
->max ()) > 0))
2980 vr_result
->set_varying ();
2982 /* If the new range is different than the previous value, keep
2988 /* Simplify boolean operations if the source is known
2989 to be already a boolean. */
2991 vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator
*gsi
,
2994 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2996 bool need_conversion
;
2998 /* We handle only !=/== case here. */
2999 gcc_assert (rhs_code
== EQ_EXPR
|| rhs_code
== NE_EXPR
);
3001 op0
= gimple_assign_rhs1 (stmt
);
3002 if (!op_with_boolean_value_range_p (op0
))
3005 op1
= gimple_assign_rhs2 (stmt
);
3006 if (!op_with_boolean_value_range_p (op1
))
3009 /* Reduce number of cases to handle to NE_EXPR. As there is no
3010 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
3011 if (rhs_code
== EQ_EXPR
)
3013 if (TREE_CODE (op1
) == INTEGER_CST
)
3014 op1
= int_const_binop (BIT_XOR_EXPR
, op1
,
3015 build_int_cst (TREE_TYPE (op1
), 1));
3020 lhs
= gimple_assign_lhs (stmt
);
3022 = !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
));
3024 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
3026 && !TYPE_UNSIGNED (TREE_TYPE (op0
))
3027 && TYPE_PRECISION (TREE_TYPE (op0
)) == 1
3028 && TYPE_PRECISION (TREE_TYPE (lhs
)) > 1)
3031 /* For A != 0 we can substitute A itself. */
3032 if (integer_zerop (op1
))
3033 gimple_assign_set_rhs_with_ops (gsi
,
3035 ? NOP_EXPR
: TREE_CODE (op0
), op0
);
3036 /* For A != B we substitute A ^ B. Either with conversion. */
3037 else if (need_conversion
)
3039 tree tem
= make_ssa_name (TREE_TYPE (op0
));
3041 = gimple_build_assign (tem
, BIT_XOR_EXPR
, op0
, op1
);
3042 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
3043 if (INTEGRAL_TYPE_P (TREE_TYPE (tem
))
3044 && TYPE_PRECISION (TREE_TYPE (tem
)) > 1)
3045 set_range_info (tem
, VR_RANGE
,
3046 wi::zero (TYPE_PRECISION (TREE_TYPE (tem
))),
3047 wi::one (TYPE_PRECISION (TREE_TYPE (tem
))));
3048 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, tem
);
3052 gimple_assign_set_rhs_with_ops (gsi
, BIT_XOR_EXPR
, op0
, op1
);
3053 update_stmt (gsi_stmt (*gsi
));
3054 fold_stmt (gsi
, follow_single_use_edges
);
3059 /* Simplify a division or modulo operator to a right shift or bitwise and
3060 if the first operand is unsigned or is greater than zero and the second
3061 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
3062 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
3063 optimize it into just op0 if op0's range is known to be a subset of
3064 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3068 vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator
*gsi
,
3071 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3073 tree op0
= gimple_assign_rhs1 (stmt
);
3074 tree op1
= gimple_assign_rhs2 (stmt
);
3075 tree op0min
= NULL_TREE
, op0max
= NULL_TREE
;
3077 value_range
*vr
= NULL
;
3079 if (TREE_CODE (op0
) == INTEGER_CST
)
3086 vr
= get_value_range (op0
);
3087 if (range_int_cst_p (vr
))
3089 op0min
= vr
->min ();
3090 op0max
= vr
->max ();
3094 if (rhs_code
== TRUNC_MOD_EXPR
3095 && TREE_CODE (op1
) == SSA_NAME
)
3097 value_range
*vr1
= get_value_range (op1
);
3098 if (range_int_cst_p (vr1
))
3099 op1min
= vr1
->min ();
3101 if (rhs_code
== TRUNC_MOD_EXPR
3102 && TREE_CODE (op1min
) == INTEGER_CST
3103 && tree_int_cst_sgn (op1min
) == 1
3105 && tree_int_cst_lt (op0max
, op1min
))
3107 if (TYPE_UNSIGNED (TREE_TYPE (op0
))
3108 || tree_int_cst_sgn (op0min
) >= 0
3109 || tree_int_cst_lt (fold_unary (NEGATE_EXPR
, TREE_TYPE (op1min
), op1min
),
3112 /* If op0 already has the range op0 % op1 has,
3113 then TRUNC_MOD_EXPR won't change anything. */
3114 gimple_assign_set_rhs_from_tree (gsi
, op0
);
3119 if (TREE_CODE (op0
) != SSA_NAME
)
3122 if (!integer_pow2p (op1
))
3124 /* X % -Y can be only optimized into X % Y either if
3125 X is not INT_MIN, or Y is not -1. Fold it now, as after
3126 remove_range_assertions the range info might be not available
3128 if (rhs_code
== TRUNC_MOD_EXPR
3129 && fold_stmt (gsi
, follow_single_use_edges
))
3134 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
3135 val
= integer_one_node
;
3140 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
3144 && integer_onep (val
)
3145 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3147 location_t location
;
3149 if (!gimple_has_location (stmt
))
3150 location
= input_location
;
3152 location
= gimple_location (stmt
);
3153 warning_at (location
, OPT_Wstrict_overflow
,
3154 "assuming signed overflow does not occur when "
3155 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3159 if (val
&& integer_onep (val
))
3163 if (rhs_code
== TRUNC_DIV_EXPR
)
3165 t
= build_int_cst (integer_type_node
, tree_log2 (op1
));
3166 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
3167 gimple_assign_set_rhs1 (stmt
, op0
);
3168 gimple_assign_set_rhs2 (stmt
, t
);
3172 t
= build_int_cst (TREE_TYPE (op1
), 1);
3173 t
= int_const_binop (MINUS_EXPR
, op1
, t
);
3174 t
= fold_convert (TREE_TYPE (op0
), t
);
3176 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
3177 gimple_assign_set_rhs1 (stmt
, op0
);
3178 gimple_assign_set_rhs2 (stmt
, t
);
3182 fold_stmt (gsi
, follow_single_use_edges
);
3189 /* Simplify a min or max if the ranges of the two operands are
3190 disjoint. Return true if we do simplify. */
3193 vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator
*gsi
,
3196 tree op0
= gimple_assign_rhs1 (stmt
);
3197 tree op1
= gimple_assign_rhs2 (stmt
);
3201 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3202 (LE_EXPR
, op0
, op1
, &sop
));
3206 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3207 (LT_EXPR
, op0
, op1
, &sop
));
3212 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3214 location_t location
;
3216 if (!gimple_has_location (stmt
))
3217 location
= input_location
;
3219 location
= gimple_location (stmt
);
3220 warning_at (location
, OPT_Wstrict_overflow
,
3221 "assuming signed overflow does not occur when "
3222 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3225 /* VAL == TRUE -> OP0 < or <= op1
3226 VAL == FALSE -> OP0 > or >= op1. */
3227 tree res
= ((gimple_assign_rhs_code (stmt
) == MAX_EXPR
)
3228 == integer_zerop (val
)) ? op0
: op1
;
3229 gimple_assign_set_rhs_from_tree (gsi
, res
);
3236 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3237 ABS_EXPR. If the operand is <= 0, then simplify the
3238 ABS_EXPR into a NEGATE_EXPR. */
3241 vr_values::simplify_abs_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3243 tree op
= gimple_assign_rhs1 (stmt
);
3244 value_range
*vr
= get_value_range (op
);
3251 val
= compare_range_with_value (LE_EXPR
, vr
, integer_zero_node
, &sop
);
3254 /* The range is neither <= 0 nor > 0. Now see if it is
3255 either < 0 or >= 0. */
3257 val
= compare_range_with_value (LT_EXPR
, vr
, integer_zero_node
,
3263 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3265 location_t location
;
3267 if (!gimple_has_location (stmt
))
3268 location
= input_location
;
3270 location
= gimple_location (stmt
);
3271 warning_at (location
, OPT_Wstrict_overflow
,
3272 "assuming signed overflow does not occur when "
3273 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3276 gimple_assign_set_rhs1 (stmt
, op
);
3277 if (integer_zerop (val
))
3278 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
3280 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
3282 fold_stmt (gsi
, follow_single_use_edges
);
3290 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3291 If all the bits that are being cleared by & are already
3292 known to be zero from VR, or all the bits that are being
3293 set by | are already known to be one from VR, the bit
3294 operation is redundant. */
3297 vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator
*gsi
,
3300 tree op0
= gimple_assign_rhs1 (stmt
);
3301 tree op1
= gimple_assign_rhs2 (stmt
);
3302 tree op
= NULL_TREE
;
3303 value_range_base vr0
, vr1
;
3304 wide_int may_be_nonzero0
, may_be_nonzero1
;
3305 wide_int must_be_nonzero0
, must_be_nonzero1
;
3308 if (TREE_CODE (op0
) == SSA_NAME
)
3309 vr0
= *(get_value_range (op0
));
3310 else if (is_gimple_min_invariant (op0
))
3315 if (TREE_CODE (op1
) == SSA_NAME
)
3316 vr1
= *(get_value_range (op1
));
3317 else if (is_gimple_min_invariant (op1
))
3322 if (!vrp_set_zero_nonzero_bits (TREE_TYPE (op0
), &vr0
, &may_be_nonzero0
,
3325 if (!vrp_set_zero_nonzero_bits (TREE_TYPE (op1
), &vr1
, &may_be_nonzero1
,
3329 switch (gimple_assign_rhs_code (stmt
))
3332 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3338 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3346 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3352 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3363 if (op
== NULL_TREE
)
3366 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (op
), op
);
3367 update_stmt (gsi_stmt (*gsi
));
3371 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3372 a known value range VR.
3374 If there is one and only one value which will satisfy the
3375 conditional, then return that value. Else return NULL.
3377 If signed overflow must be undefined for the value to satisfy
3378 the conditional, then set *STRICT_OVERFLOW_P to true. */
3381 test_for_singularity (enum tree_code cond_code
, tree op0
,
3382 tree op1
, value_range
*vr
)
3387 /* Extract minimum/maximum values which satisfy the conditional as it was
3389 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
3391 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
3394 if (cond_code
== LT_EXPR
)
3396 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3397 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
3398 /* Signal to compare_values_warnv this expr doesn't overflow. */
3400 TREE_NO_WARNING (max
) = 1;
3403 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
3405 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
3408 if (cond_code
== GT_EXPR
)
3410 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3411 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
3412 /* Signal to compare_values_warnv this expr doesn't overflow. */
3414 TREE_NO_WARNING (min
) = 1;
3418 /* Now refine the minimum and maximum values using any
3419 value range information we have for op0. */
3422 if (compare_values (vr
->min (), min
) == 1)
3424 if (compare_values (vr
->max (), max
) == -1)
3427 /* If the new min/max values have converged to a single value,
3428 then there is only one value which can satisfy the condition,
3429 return that value. */
3430 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
3436 /* Return whether the value range *VR fits in an integer type specified
3437 by PRECISION and UNSIGNED_P. */
3440 range_fits_type_p (value_range
*vr
, unsigned dest_precision
, signop dest_sgn
)
3443 unsigned src_precision
;
3447 /* We can only handle integral and pointer types. */
3448 src_type
= vr
->type ();
3449 if (!INTEGRAL_TYPE_P (src_type
)
3450 && !POINTER_TYPE_P (src_type
))
3453 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3454 and so is an identity transform. */
3455 src_precision
= TYPE_PRECISION (vr
->type ());
3456 src_sgn
= TYPE_SIGN (src_type
);
3457 if ((src_precision
< dest_precision
3458 && !(dest_sgn
== UNSIGNED
&& src_sgn
== SIGNED
))
3459 || (src_precision
== dest_precision
&& src_sgn
== dest_sgn
))
3462 /* Now we can only handle ranges with constant bounds. */
3463 if (!range_int_cst_p (vr
))
3466 /* For sign changes, the MSB of the wide_int has to be clear.
3467 An unsigned value with its MSB set cannot be represented by
3468 a signed wide_int, while a negative value cannot be represented
3469 by an unsigned wide_int. */
3470 if (src_sgn
!= dest_sgn
3471 && (wi::lts_p (wi::to_wide (vr
->min ()), 0)
3472 || wi::lts_p (wi::to_wide (vr
->max ()), 0)))
3475 /* Then we can perform the conversion on both ends and compare
3476 the result for equality. */
3477 tem
= wi::ext (wi::to_widest (vr
->min ()), dest_precision
, dest_sgn
);
3478 if (tem
!= wi::to_widest (vr
->min ()))
3480 tem
= wi::ext (wi::to_widest (vr
->max ()), dest_precision
, dest_sgn
);
3481 if (tem
!= wi::to_widest (vr
->max ()))
3487 /* Simplify a conditional using a relational operator to an equality
3488 test if the range information indicates only one value can satisfy
3489 the original conditional. */
3492 vr_values::simplify_cond_using_ranges_1 (gcond
*stmt
)
3494 tree op0
= gimple_cond_lhs (stmt
);
3495 tree op1
= gimple_cond_rhs (stmt
);
3496 enum tree_code cond_code
= gimple_cond_code (stmt
);
3498 if (cond_code
!= NE_EXPR
3499 && cond_code
!= EQ_EXPR
3500 && TREE_CODE (op0
) == SSA_NAME
3501 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3502 && is_gimple_min_invariant (op1
))
3504 value_range
*vr
= get_value_range (op0
);
3506 /* If we have range information for OP0, then we might be
3507 able to simplify this conditional. */
3508 if (vr
->kind () == VR_RANGE
)
3510 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
3515 fprintf (dump_file
, "Simplified relational ");
3516 print_gimple_stmt (dump_file
, stmt
, 0);
3517 fprintf (dump_file
, " into ");
3520 gimple_cond_set_code (stmt
, EQ_EXPR
);
3521 gimple_cond_set_lhs (stmt
, op0
);
3522 gimple_cond_set_rhs (stmt
, new_tree
);
3528 print_gimple_stmt (dump_file
, stmt
, 0);
3529 fprintf (dump_file
, "\n");
3535 /* Try again after inverting the condition. We only deal
3536 with integral types here, so no need to worry about
3537 issues with inverting FP comparisons. */
3538 new_tree
= test_for_singularity
3539 (invert_tree_comparison (cond_code
, false),
3545 fprintf (dump_file
, "Simplified relational ");
3546 print_gimple_stmt (dump_file
, stmt
, 0);
3547 fprintf (dump_file
, " into ");
3550 gimple_cond_set_code (stmt
, NE_EXPR
);
3551 gimple_cond_set_lhs (stmt
, op0
);
3552 gimple_cond_set_rhs (stmt
, new_tree
);
3558 print_gimple_stmt (dump_file
, stmt
, 0);
3559 fprintf (dump_file
, "\n");
3569 /* STMT is a conditional at the end of a basic block.
3571 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3572 was set via a type conversion, try to replace the SSA_NAME with the RHS
3573 of the type conversion. Doing so makes the conversion dead which helps
3574 subsequent passes. */
3577 vr_values::simplify_cond_using_ranges_2 (gcond
*stmt
)
3579 tree op0
= gimple_cond_lhs (stmt
);
3580 tree op1
= gimple_cond_rhs (stmt
);
3582 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3583 see if OP0 was set by a type conversion where the source of
3584 the conversion is another SSA_NAME with a range that fits
3585 into the range of OP0's type.
3587 If so, the conversion is redundant as the earlier SSA_NAME can be
3588 used for the comparison directly if we just massage the constant in the
3590 if (TREE_CODE (op0
) == SSA_NAME
3591 && TREE_CODE (op1
) == INTEGER_CST
)
3593 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op0
);
3596 if (!is_gimple_assign (def_stmt
)
3597 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3600 innerop
= gimple_assign_rhs1 (def_stmt
);
3602 if (TREE_CODE (innerop
) == SSA_NAME
3603 && !POINTER_TYPE_P (TREE_TYPE (innerop
))
3604 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
)
3605 && desired_pro_or_demotion_p (TREE_TYPE (innerop
), TREE_TYPE (op0
)))
3607 value_range
*vr
= get_value_range (innerop
);
3609 if (range_int_cst_p (vr
)
3610 && range_fits_type_p (vr
,
3611 TYPE_PRECISION (TREE_TYPE (op0
)),
3612 TYPE_SIGN (TREE_TYPE (op0
)))
3613 && int_fits_type_p (op1
, TREE_TYPE (innerop
)))
3615 tree newconst
= fold_convert (TREE_TYPE (innerop
), op1
);
3616 gimple_cond_set_lhs (stmt
, innerop
);
3617 gimple_cond_set_rhs (stmt
, newconst
);
3619 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3621 fprintf (dump_file
, "Folded into: ");
3622 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3623 fprintf (dump_file
, "\n");
3630 /* Simplify a switch statement using the value range of the switch
3634 vr_values::simplify_switch_using_ranges (gswitch
*stmt
)
3636 tree op
= gimple_switch_index (stmt
);
3637 value_range
*vr
= NULL
;
3641 size_t i
= 0, j
= 0, n
, n2
;
3644 size_t k
= 1, l
= 0;
3646 if (TREE_CODE (op
) == SSA_NAME
)
3648 vr
= get_value_range (op
);
3650 /* We can only handle integer ranges. */
3651 if (vr
->varying_p ()
3652 || vr
->undefined_p ()
3653 || vr
->symbolic_p ())
3656 /* Find case label for min/max of the value range. */
3657 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
3659 else if (TREE_CODE (op
) == INTEGER_CST
)
3661 take_default
= !find_case_label_index (stmt
, 1, op
, &i
);
3675 n
= gimple_switch_num_labels (stmt
);
3677 /* We can truncate the case label ranges that partially overlap with OP's
3679 size_t min_idx
= 1, max_idx
= 0;
3681 find_case_label_range (stmt
, vr
->min (), vr
->max (), &min_idx
, &max_idx
);
3682 if (min_idx
<= max_idx
)
3684 tree min_label
= gimple_switch_label (stmt
, min_idx
);
3685 tree max_label
= gimple_switch_label (stmt
, max_idx
);
3687 /* Avoid changing the type of the case labels when truncating. */
3688 tree case_label_type
= TREE_TYPE (CASE_LOW (min_label
));
3689 tree vr_min
= fold_convert (case_label_type
, vr
->min ());
3690 tree vr_max
= fold_convert (case_label_type
, vr
->max ());
3692 if (vr
->kind () == VR_RANGE
)
3694 /* If OP's value range is [2,8] and the low label range is
3695 0 ... 3, truncate the label's range to 2 .. 3. */
3696 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3697 && CASE_HIGH (min_label
) != NULL_TREE
3698 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3699 CASE_LOW (min_label
) = vr_min
;
3701 /* If OP's value range is [2,8] and the high label range is
3702 7 ... 10, truncate the label's range to 7 .. 8. */
3703 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3704 && CASE_HIGH (max_label
) != NULL_TREE
3705 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3706 CASE_HIGH (max_label
) = vr_max
;
3708 else if (vr
->kind () == VR_ANTI_RANGE
)
3710 tree one_cst
= build_one_cst (case_label_type
);
3712 if (min_label
== max_label
)
3714 /* If OP's value range is ~[7,8] and the label's range is
3715 7 ... 10, truncate the label's range to 9 ... 10. */
3716 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) == 0
3717 && CASE_HIGH (min_label
) != NULL_TREE
3718 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) > 0)
3719 CASE_LOW (min_label
)
3720 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3722 /* If OP's value range is ~[7,8] and the label's range is
3723 5 ... 8, truncate the label's range to 5 ... 6. */
3724 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3725 && CASE_HIGH (min_label
) != NULL_TREE
3726 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) == 0)
3727 CASE_HIGH (min_label
)
3728 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3732 /* If OP's value range is ~[2,8] and the low label range is
3733 0 ... 3, truncate the label's range to 0 ... 1. */
3734 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3735 && CASE_HIGH (min_label
) != NULL_TREE
3736 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3737 CASE_HIGH (min_label
)
3738 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3740 /* If OP's value range is ~[2,8] and the high label range is
3741 7 ... 10, truncate the label's range to 9 ... 10. */
3742 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3743 && CASE_HIGH (max_label
) != NULL_TREE
3744 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3745 CASE_LOW (max_label
)
3746 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3750 /* Canonicalize singleton case ranges. */
3751 if (tree_int_cst_equal (CASE_LOW (min_label
), CASE_HIGH (min_label
)))
3752 CASE_HIGH (min_label
) = NULL_TREE
;
3753 if (tree_int_cst_equal (CASE_LOW (max_label
), CASE_HIGH (max_label
)))
3754 CASE_HIGH (max_label
) = NULL_TREE
;
3757 /* We can also eliminate case labels that lie completely outside OP's value
3760 /* Bail out if this is just all edges taken. */
3766 /* Build a new vector of taken case labels. */
3767 vec2
= make_tree_vec (j
- i
+ 1 + l
- k
+ 1 + (int)take_default
);
3770 /* Add the default edge, if necessary. */
3772 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
3774 for (; i
<= j
; ++i
, ++n2
)
3775 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
3777 for (; k
<= l
; ++k
, ++n2
)
3778 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, k
);
3780 /* Mark needed edges. */
3781 for (i
= 0; i
< n2
; ++i
)
3783 e
= find_edge (gimple_bb (stmt
),
3784 label_to_block (cfun
,
3785 CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
3786 e
->aux
= (void *)-1;
3789 /* Queue not needed edges for later removal. */
3790 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
3792 if (e
->aux
== (void *)-1)
3798 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3800 fprintf (dump_file
, "removing unreachable case label\n");
3802 to_remove_edges
.safe_push (e
);
3803 e
->flags
&= ~EDGE_EXECUTABLE
;
3804 e
->flags
|= EDGE_IGNORE
;
3807 /* And queue an update for the stmt. */
3810 to_update_switch_stmts
.safe_push (su
);
3815 vr_values::cleanup_edges_and_switches (void)
3821 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
3822 CFG in a broken state and requires a cfg_cleanup run. */
3823 FOR_EACH_VEC_ELT (to_remove_edges
, i
, e
)
3826 /* Update SWITCH_EXPR case label vector. */
3827 FOR_EACH_VEC_ELT (to_update_switch_stmts
, i
, su
)
3830 size_t n
= TREE_VEC_LENGTH (su
->vec
);
3832 gimple_switch_set_num_labels (su
->stmt
, n
);
3833 for (j
= 0; j
< n
; j
++)
3834 gimple_switch_set_label (su
->stmt
, j
, TREE_VEC_ELT (su
->vec
, j
));
3835 /* As we may have replaced the default label with a regular one
3836 make sure to make it a real default label again. This ensures
3837 optimal expansion. */
3838 label
= gimple_switch_label (su
->stmt
, 0);
3839 CASE_LOW (label
) = NULL_TREE
;
3840 CASE_HIGH (label
) = NULL_TREE
;
3843 if (!to_remove_edges
.is_empty ())
3845 free_dominance_info (CDI_DOMINATORS
);
3846 loops_state_set (LOOPS_NEED_FIXUP
);
3849 to_remove_edges
.release ();
3850 to_update_switch_stmts
.release ();
3853 /* Simplify an integral conversion from an SSA name in STMT. */
3856 simplify_conversion_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3858 tree innerop
, middleop
, finaltype
;
3860 signop inner_sgn
, middle_sgn
, final_sgn
;
3861 unsigned inner_prec
, middle_prec
, final_prec
;
3862 widest_int innermin
, innermed
, innermax
, middlemin
, middlemed
, middlemax
;
3864 finaltype
= TREE_TYPE (gimple_assign_lhs (stmt
));
3865 if (!INTEGRAL_TYPE_P (finaltype
))
3867 middleop
= gimple_assign_rhs1 (stmt
);
3868 def_stmt
= SSA_NAME_DEF_STMT (middleop
);
3869 if (!is_gimple_assign (def_stmt
)
3870 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3872 innerop
= gimple_assign_rhs1 (def_stmt
);
3873 if (TREE_CODE (innerop
) != SSA_NAME
3874 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
))
3877 /* Get the value-range of the inner operand. Use get_range_info in
3878 case innerop was created during substitute-and-fold. */
3879 wide_int imin
, imax
;
3880 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
))
3881 || get_range_info (innerop
, &imin
, &imax
) != VR_RANGE
)
3883 innermin
= widest_int::from (imin
, TYPE_SIGN (TREE_TYPE (innerop
)));
3884 innermax
= widest_int::from (imax
, TYPE_SIGN (TREE_TYPE (innerop
)));
3886 /* Simulate the conversion chain to check if the result is equal if
3887 the middle conversion is removed. */
3888 inner_prec
= TYPE_PRECISION (TREE_TYPE (innerop
));
3889 middle_prec
= TYPE_PRECISION (TREE_TYPE (middleop
));
3890 final_prec
= TYPE_PRECISION (finaltype
);
3892 /* If the first conversion is not injective, the second must not
3894 if (wi::gtu_p (innermax
- innermin
,
3895 wi::mask
<widest_int
> (middle_prec
, false))
3896 && middle_prec
< final_prec
)
3898 /* We also want a medium value so that we can track the effect that
3899 narrowing conversions with sign change have. */
3900 inner_sgn
= TYPE_SIGN (TREE_TYPE (innerop
));
3901 if (inner_sgn
== UNSIGNED
)
3902 innermed
= wi::shifted_mask
<widest_int
> (1, inner_prec
- 1, false);
3905 if (wi::cmp (innermin
, innermed
, inner_sgn
) >= 0
3906 || wi::cmp (innermed
, innermax
, inner_sgn
) >= 0)
3907 innermed
= innermin
;
3909 middle_sgn
= TYPE_SIGN (TREE_TYPE (middleop
));
3910 middlemin
= wi::ext (innermin
, middle_prec
, middle_sgn
);
3911 middlemed
= wi::ext (innermed
, middle_prec
, middle_sgn
);
3912 middlemax
= wi::ext (innermax
, middle_prec
, middle_sgn
);
3914 /* Require that the final conversion applied to both the original
3915 and the intermediate range produces the same result. */
3916 final_sgn
= TYPE_SIGN (finaltype
);
3917 if (wi::ext (middlemin
, final_prec
, final_sgn
)
3918 != wi::ext (innermin
, final_prec
, final_sgn
)
3919 || wi::ext (middlemed
, final_prec
, final_sgn
)
3920 != wi::ext (innermed
, final_prec
, final_sgn
)
3921 || wi::ext (middlemax
, final_prec
, final_sgn
)
3922 != wi::ext (innermax
, final_prec
, final_sgn
))
3925 gimple_assign_set_rhs1 (stmt
, innerop
);
3926 fold_stmt (gsi
, follow_single_use_edges
);
3930 /* Simplify a conversion from integral SSA name to float in STMT. */
3933 vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator
*gsi
,
3936 tree rhs1
= gimple_assign_rhs1 (stmt
);
3937 value_range
*vr
= get_value_range (rhs1
);
3938 scalar_float_mode fltmode
3939 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
)));
3940 scalar_int_mode mode
;
3944 /* We can only handle constant ranges. */
3945 if (!range_int_cst_p (vr
))
3948 /* First check if we can use a signed type in place of an unsigned. */
3949 scalar_int_mode rhs_mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1
));
3950 if (TYPE_UNSIGNED (TREE_TYPE (rhs1
))
3951 && can_float_p (fltmode
, rhs_mode
, 0) != CODE_FOR_nothing
3952 && range_fits_type_p (vr
, TYPE_PRECISION (TREE_TYPE (rhs1
)), SIGNED
))
3954 /* If we can do the conversion in the current input mode do nothing. */
3955 else if (can_float_p (fltmode
, rhs_mode
,
3956 TYPE_UNSIGNED (TREE_TYPE (rhs1
))) != CODE_FOR_nothing
)
3958 /* Otherwise search for a mode we can use, starting from the narrowest
3959 integer mode available. */
3962 mode
= NARROWEST_INT_MODE
;
3965 /* If we cannot do a signed conversion to float from mode
3966 or if the value-range does not fit in the signed type
3967 try with a wider mode. */
3968 if (can_float_p (fltmode
, mode
, 0) != CODE_FOR_nothing
3969 && range_fits_type_p (vr
, GET_MODE_PRECISION (mode
), SIGNED
))
3972 /* But do not widen the input. Instead leave that to the
3973 optabs expansion code. */
3974 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
3975 || GET_MODE_PRECISION (mode
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
3980 /* It works, insert a truncation or sign-change before the
3981 float conversion. */
3982 tem
= make_ssa_name (build_nonstandard_integer_type
3983 (GET_MODE_PRECISION (mode
), 0));
3984 conv
= gimple_build_assign (tem
, NOP_EXPR
, rhs1
);
3985 gsi_insert_before (gsi
, conv
, GSI_SAME_STMT
);
3986 gimple_assign_set_rhs1 (stmt
, tem
);
3987 fold_stmt (gsi
, follow_single_use_edges
);
3992 /* Simplify an internal fn call using ranges if possible. */
3995 vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator
*gsi
,
3998 enum tree_code subcode
;
3999 bool is_ubsan
= false;
4001 switch (gimple_call_internal_fn (stmt
))
4003 case IFN_UBSAN_CHECK_ADD
:
4004 subcode
= PLUS_EXPR
;
4007 case IFN_UBSAN_CHECK_SUB
:
4008 subcode
= MINUS_EXPR
;
4011 case IFN_UBSAN_CHECK_MUL
:
4012 subcode
= MULT_EXPR
;
4015 case IFN_ADD_OVERFLOW
:
4016 subcode
= PLUS_EXPR
;
4018 case IFN_SUB_OVERFLOW
:
4019 subcode
= MINUS_EXPR
;
4021 case IFN_MUL_OVERFLOW
:
4022 subcode
= MULT_EXPR
;
4028 tree op0
= gimple_call_arg (stmt
, 0);
4029 tree op1
= gimple_call_arg (stmt
, 1);
4033 type
= TREE_TYPE (op0
);
4034 if (VECTOR_TYPE_P (type
))
4037 else if (gimple_call_lhs (stmt
) == NULL_TREE
)
4040 type
= TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt
)));
4041 if (!check_for_binary_op_overflow (subcode
, type
, op0
, op1
, &ovf
)
4042 || (is_ubsan
&& ovf
))
4046 location_t loc
= gimple_location (stmt
);
4048 g
= gimple_build_assign (gimple_call_lhs (stmt
), subcode
, op0
, op1
);
4051 int prec
= TYPE_PRECISION (type
);
4054 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
4055 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
4056 utype
= build_nonstandard_integer_type (prec
, 1);
4057 if (TREE_CODE (op0
) == INTEGER_CST
)
4058 op0
= fold_convert (utype
, op0
);
4059 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op0
)))
4061 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op0
);
4062 gimple_set_location (g
, loc
);
4063 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4064 op0
= gimple_assign_lhs (g
);
4066 if (TREE_CODE (op1
) == INTEGER_CST
)
4067 op1
= fold_convert (utype
, op1
);
4068 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op1
)))
4070 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op1
);
4071 gimple_set_location (g
, loc
);
4072 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4073 op1
= gimple_assign_lhs (g
);
4075 g
= gimple_build_assign (make_ssa_name (utype
), subcode
, op0
, op1
);
4076 gimple_set_location (g
, loc
);
4077 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4080 g
= gimple_build_assign (make_ssa_name (type
), NOP_EXPR
,
4081 gimple_assign_lhs (g
));
4082 gimple_set_location (g
, loc
);
4083 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4085 g
= gimple_build_assign (gimple_call_lhs (stmt
), COMPLEX_EXPR
,
4086 gimple_assign_lhs (g
),
4087 build_int_cst (type
, ovf
));
4089 gimple_set_location (g
, loc
);
4090 gsi_replace (gsi
, g
, false);
4094 /* Return true if VAR is a two-valued variable. Set a and b with the
4095 two-values when it is true. Return false otherwise. */
4098 vr_values::two_valued_val_range_p (tree var
, tree
*a
, tree
*b
)
4100 value_range
*vr
= get_value_range (var
);
4101 if (vr
->varying_p ()
4102 || vr
->undefined_p ()
4103 || TREE_CODE (vr
->min ()) != INTEGER_CST
4104 || TREE_CODE (vr
->max ()) != INTEGER_CST
)
4107 if (vr
->kind () == VR_RANGE
4108 && wi::to_wide (vr
->max ()) - wi::to_wide (vr
->min ()) == 1)
4115 /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
4116 if (vr
->kind () == VR_ANTI_RANGE
4117 && (wi::to_wide (vr
->min ())
4118 - wi::to_wide (vrp_val_min (TREE_TYPE (var
)))) == 1
4119 && (wi::to_wide (vrp_val_max (TREE_TYPE (var
)))
4120 - wi::to_wide (vr
->max ())) == 1)
4122 *a
= vrp_val_min (TREE_TYPE (var
));
4123 *b
= vrp_val_max (TREE_TYPE (var
));
4130 /* Simplify STMT using ranges if possible. */
4133 vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator
*gsi
)
4135 gimple
*stmt
= gsi_stmt (*gsi
);
4136 if (is_gimple_assign (stmt
))
4138 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
4139 tree rhs1
= gimple_assign_rhs1 (stmt
);
4140 tree rhs2
= gimple_assign_rhs2 (stmt
);
4141 tree lhs
= gimple_assign_lhs (stmt
);
4142 tree val1
= NULL_TREE
, val2
= NULL_TREE
;
4143 use_operand_p use_p
;
4148 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4150 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4154 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4156 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4158 if (TREE_CODE_CLASS (rhs_code
) == tcc_binary
4159 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4160 && ((TREE_CODE (rhs1
) == INTEGER_CST
4161 && TREE_CODE (rhs2
) == SSA_NAME
)
4162 || (TREE_CODE (rhs2
) == INTEGER_CST
4163 && TREE_CODE (rhs1
) == SSA_NAME
))
4164 && single_imm_use (lhs
, &use_p
, &use_stmt
)
4165 && gimple_code (use_stmt
) == GIMPLE_COND
)
4168 tree new_rhs1
= NULL_TREE
;
4169 tree new_rhs2
= NULL_TREE
;
4170 tree cmp_var
= NULL_TREE
;
4172 if (TREE_CODE (rhs2
) == SSA_NAME
4173 && two_valued_val_range_p (rhs2
, &val1
, &val2
))
4175 /* Optimize RHS1 OP [VAL1, VAL2]. */
4176 new_rhs1
= int_const_binop (rhs_code
, rhs1
, val1
);
4177 new_rhs2
= int_const_binop (rhs_code
, rhs1
, val2
);
4180 else if (TREE_CODE (rhs1
) == SSA_NAME
4181 && two_valued_val_range_p (rhs1
, &val1
, &val2
))
4183 /* Optimize [VAL1, VAL2] OP RHS2. */
4184 new_rhs1
= int_const_binop (rhs_code
, val1
, rhs2
);
4185 new_rhs2
= int_const_binop (rhs_code
, val2
, rhs2
);
4189 /* If we could not find two-vals or the optimzation is invalid as
4190 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4191 if (new_rhs1
&& new_rhs2
)
4193 tree cond
= build2 (EQ_EXPR
, boolean_type_node
, cmp_var
, val1
);
4194 gimple_assign_set_rhs_with_ops (gsi
,
4198 update_stmt (gsi_stmt (*gsi
));
4199 fold_stmt (gsi
, follow_single_use_edges
);
4208 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4209 if the RHS is zero or one, and the LHS are known to be boolean
4211 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4212 return simplify_truth_ops_using_ranges (gsi
, stmt
);
4215 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4216 and BIT_AND_EXPR respectively if the first operand is greater
4217 than zero and the second operand is an exact power of two.
4218 Also optimize TRUNC_MOD_EXPR away if the second operand is
4219 constant and the first operand already has the right value
4221 case TRUNC_DIV_EXPR
:
4222 case TRUNC_MOD_EXPR
:
4223 if ((TREE_CODE (rhs1
) == SSA_NAME
4224 || TREE_CODE (rhs1
) == INTEGER_CST
)
4225 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4226 return simplify_div_or_mod_using_ranges (gsi
, stmt
);
4229 /* Transform ABS (X) into X or -X as appropriate. */
4231 if (TREE_CODE (rhs1
) == SSA_NAME
4232 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4233 return simplify_abs_using_ranges (gsi
, stmt
);
4238 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4239 if all the bits being cleared are already cleared or
4240 all the bits being set are already set. */
4241 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4242 return simplify_bit_ops_using_ranges (gsi
, stmt
);
4246 if (TREE_CODE (rhs1
) == SSA_NAME
4247 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4248 return simplify_conversion_using_ranges (gsi
, stmt
);
4252 if (TREE_CODE (rhs1
) == SSA_NAME
4253 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4254 return simplify_float_conversion_using_ranges (gsi
, stmt
);
4259 return simplify_min_or_max_using_ranges (gsi
, stmt
);
4265 else if (gimple_code (stmt
) == GIMPLE_COND
)
4266 return simplify_cond_using_ranges_1 (as_a
<gcond
*> (stmt
));
4267 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
4268 return simplify_switch_using_ranges (as_a
<gswitch
*> (stmt
));
4269 else if (is_gimple_call (stmt
)
4270 && gimple_call_internal_p (stmt
))
4271 return simplify_internal_call_using_ranges (gsi
, stmt
);
4277 vr_values::set_vr_value (tree var
, value_range
*vr
)
4279 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4281 vr_value
[SSA_NAME_VERSION (var
)] = vr
;