1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "insn-codes.h"
28 #include "optabs-tree.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
32 #include "fold-const.h"
35 #include "gimple-fold.h"
36 #include "gimple-iterator.h"
38 #include "tree-ssa-loop-niter.h"
39 #include "tree-ssa-loop.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-ssa-propagate.h"
44 #include "tree-chrec.h"
45 #include "omp-general.h"
46 #include "case-cfn-macros.h"
47 #include "alloc-pool.h"
49 #include "vr-values.h"
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 set_value_range_to_nonnull (vr
, 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 set_value_range_to_nonnull (vr
, 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
!= *new_vr
;
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 set_value_range (old_vr
, 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
*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 tree base
= get_base_address (TREE_OPERAND (expr
, 0));
302 if (base
!= NULL_TREE
303 && TREE_CODE (base
) == MEM_REF
304 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
306 value_range
*vr
= get_value_range (TREE_OPERAND (base
, 0));
307 if (!range_includes_zero_p (vr
))
315 /* Returns true if EXPR is a valid value (as expected by compare_values) --
316 a gimple invariant, or SSA_NAME +- CST. */
319 valid_value_p (tree expr
)
321 if (TREE_CODE (expr
) == SSA_NAME
)
324 if (TREE_CODE (expr
) == PLUS_EXPR
325 || TREE_CODE (expr
) == MINUS_EXPR
)
326 return (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
327 && TREE_CODE (TREE_OPERAND (expr
, 1)) == INTEGER_CST
);
329 return is_gimple_min_invariant (expr
);
332 /* If OP has a value range with a single constant value return that,
333 otherwise return NULL_TREE. This returns OP itself if OP is a
337 vr_values::op_with_constant_singleton_value_range (tree op
)
339 if (is_gimple_min_invariant (op
))
342 if (TREE_CODE (op
) != SSA_NAME
)
345 return value_range_constant_singleton (get_value_range (op
));
348 /* Return true if op is in a boolean [0, 1] value-range. */
351 vr_values::op_with_boolean_value_range_p (tree op
)
355 if (TYPE_PRECISION (TREE_TYPE (op
)) == 1)
358 if (integer_zerop (op
)
359 || integer_onep (op
))
362 if (TREE_CODE (op
) != SSA_NAME
)
365 vr
= get_value_range (op
);
366 return (vr
->kind () == VR_RANGE
367 && integer_zerop (vr
->min ())
368 && integer_onep (vr
->max ()));
371 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
372 true and store it in *VR_P. */
375 vr_values::extract_range_for_var_from_comparison_expr (tree var
,
376 enum tree_code cond_code
,
381 value_range
*limit_vr
;
382 type
= TREE_TYPE (var
);
384 /* For pointer arithmetic, we only keep track of pointer equality
385 and inequality. If we arrive here with unfolded conditions like
386 _1 > _1 do not derive anything. */
387 if ((POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
390 vr_p
->set_varying ();
394 /* If LIMIT is another SSA name and LIMIT has a range of its own,
395 try to use LIMIT's range to avoid creating symbolic ranges
397 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
399 /* LIMIT's range is only interesting if it has any useful information. */
401 || limit_vr
->undefined_p ()
402 || limit_vr
->varying_p ()
403 || (limit_vr
->symbolic_p ()
404 && ! (limit_vr
->kind () == VR_RANGE
405 && (limit_vr
->min () == limit_vr
->max ()
406 || operand_equal_p (limit_vr
->min (),
407 limit_vr
->max (), 0)))))
410 /* Initially, the new range has the same set of equivalences of
411 VAR's range. This will be revised before returning the final
412 value. Since assertions may be chained via mutually exclusive
413 predicates, we will need to trim the set of equivalences before
415 gcc_assert (vr_p
->equiv () == NULL
);
416 vr_p
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
418 /* Extract a new range based on the asserted comparison for VAR and
419 LIMIT's value range. Notice that if LIMIT has an anti-range, we
420 will only use it for equality comparisons (EQ_EXPR). For any
421 other kind of assertion, we cannot derive a range from LIMIT's
422 anti-range that can be used to describe the new range. For
423 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
424 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
425 no single range for x_2 that could describe LE_EXPR, so we might
426 as well build the range [b_4, +INF] for it.
427 One special case we handle is extracting a range from a
428 range test encoded as (unsigned)var + CST <= limit. */
429 if (TREE_CODE (op
) == NOP_EXPR
430 || TREE_CODE (op
) == PLUS_EXPR
)
432 if (TREE_CODE (op
) == PLUS_EXPR
)
434 min
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (TREE_OPERAND (op
, 1)),
435 TREE_OPERAND (op
, 1));
436 max
= int_const_binop (PLUS_EXPR
, limit
, min
);
437 op
= TREE_OPERAND (op
, 0);
441 min
= build_int_cst (TREE_TYPE (var
), 0);
445 /* Make sure to not set TREE_OVERFLOW on the final type
446 conversion. We are willingly interpreting large positive
447 unsigned values as negative signed values here. */
448 min
= force_fit_type (TREE_TYPE (var
), wi::to_widest (min
), 0, false);
449 max
= force_fit_type (TREE_TYPE (var
), wi::to_widest (max
), 0, false);
451 /* We can transform a max, min range to an anti-range or
452 vice-versa. Use set_and_canonicalize which does this for
454 if (cond_code
== LE_EXPR
)
455 vr_p
->set_and_canonicalize (VR_RANGE
, min
, max
, vr_p
->equiv ());
456 else if (cond_code
== GT_EXPR
)
457 vr_p
->set_and_canonicalize (VR_ANTI_RANGE
, min
, max
, vr_p
->equiv ());
461 else if (cond_code
== EQ_EXPR
)
463 enum value_range_kind range_type
;
467 range_type
= limit_vr
->kind ();
468 min
= limit_vr
->min ();
469 max
= limit_vr
->max ();
473 range_type
= VR_RANGE
;
478 vr_p
->update (range_type
, min
, max
);
480 /* When asserting the equality VAR == LIMIT and LIMIT is another
481 SSA name, the new range will also inherit the equivalence set
483 if (TREE_CODE (limit
) == SSA_NAME
)
484 vr_p
->equiv_add (limit
, get_value_range (limit
), &vrp_equiv_obstack
);
486 else if (cond_code
== NE_EXPR
)
488 /* As described above, when LIMIT's range is an anti-range and
489 this assertion is an inequality (NE_EXPR), then we cannot
490 derive anything from the anti-range. For instance, if
491 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
492 not imply that VAR's range is [0, 0]. So, in the case of
493 anti-ranges, we just assert the inequality using LIMIT and
496 If LIMIT_VR is a range, we can only use it to build a new
497 anti-range if LIMIT_VR is a single-valued range. For
498 instance, if LIMIT_VR is [0, 1], the predicate
499 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
500 Rather, it means that for value 0 VAR should be ~[0, 0]
501 and for value 1, VAR should be ~[1, 1]. We cannot
502 represent these ranges.
504 The only situation in which we can build a valid
505 anti-range is when LIMIT_VR is a single-valued range
506 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
507 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
509 && limit_vr
->kind () == VR_RANGE
510 && compare_values (limit_vr
->min (), limit_vr
->max ()) == 0)
512 min
= limit_vr
->min ();
513 max
= limit_vr
->max ();
517 /* In any other case, we cannot use LIMIT's range to build a
522 /* If MIN and MAX cover the whole range for their type, then
523 just use the original LIMIT. */
524 if (INTEGRAL_TYPE_P (type
)
525 && vrp_val_is_min (min
)
526 && vrp_val_is_max (max
))
529 vr_p
->set_and_canonicalize (VR_ANTI_RANGE
, min
, max
, vr_p
->equiv ());
531 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
533 min
= TYPE_MIN_VALUE (type
);
535 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
539 /* If LIMIT_VR is of the form [N1, N2], we need to build the
540 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
542 max
= limit_vr
->max ();
545 /* If the maximum value forces us to be out of bounds, simply punt.
546 It would be pointless to try and do anything more since this
547 all should be optimized away above us. */
548 if (cond_code
== LT_EXPR
549 && compare_values (max
, min
) == 0)
550 vr_p
->set_varying ();
553 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
554 if (cond_code
== LT_EXPR
)
556 if (TYPE_PRECISION (TREE_TYPE (max
)) == 1
557 && !TYPE_UNSIGNED (TREE_TYPE (max
)))
558 max
= fold_build2 (PLUS_EXPR
, TREE_TYPE (max
), max
,
559 build_int_cst (TREE_TYPE (max
), -1));
561 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max
), max
,
562 build_int_cst (TREE_TYPE (max
), 1));
563 /* Signal to compare_values_warnv this expr doesn't overflow. */
565 TREE_NO_WARNING (max
) = 1;
568 vr_p
->update (VR_RANGE
, min
, max
);
571 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
573 max
= TYPE_MAX_VALUE (type
);
575 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
579 /* If LIMIT_VR is of the form [N1, N2], we need to build the
580 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
582 min
= limit_vr
->min ();
585 /* If the minimum value forces us to be out of bounds, simply punt.
586 It would be pointless to try and do anything more since this
587 all should be optimized away above us. */
588 if (cond_code
== GT_EXPR
589 && compare_values (min
, max
) == 0)
590 vr_p
->set_varying ();
593 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
594 if (cond_code
== GT_EXPR
)
596 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
597 && !TYPE_UNSIGNED (TREE_TYPE (min
)))
598 min
= fold_build2 (MINUS_EXPR
, TREE_TYPE (min
), min
,
599 build_int_cst (TREE_TYPE (min
), -1));
601 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min
), min
,
602 build_int_cst (TREE_TYPE (min
), 1));
603 /* Signal to compare_values_warnv this expr doesn't overflow. */
605 TREE_NO_WARNING (min
) = 1;
608 vr_p
->update (VR_RANGE
, min
, max
);
614 /* Finally intersect the new range with what we already know about var. */
615 vr_p
->intersect (get_value_range (var
));
618 /* Extract value range information from an ASSERT_EXPR EXPR and store
622 vr_values::extract_range_from_assert (value_range
*vr_p
, tree expr
)
624 tree var
= ASSERT_EXPR_VAR (expr
);
625 tree cond
= ASSERT_EXPR_COND (expr
);
627 enum tree_code cond_code
;
628 gcc_assert (COMPARISON_CLASS_P (cond
));
630 /* Find VAR in the ASSERT_EXPR conditional. */
631 if (var
== TREE_OPERAND (cond
, 0)
632 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PLUS_EXPR
633 || TREE_CODE (TREE_OPERAND (cond
, 0)) == NOP_EXPR
)
635 /* If the predicate is of the form VAR COMP LIMIT, then we just
636 take LIMIT from the RHS and use the same comparison code. */
637 cond_code
= TREE_CODE (cond
);
638 limit
= TREE_OPERAND (cond
, 1);
639 op
= TREE_OPERAND (cond
, 0);
643 /* If the predicate is of the form LIMIT COMP VAR, then we need
644 to flip around the comparison code to create the proper range
646 cond_code
= swap_tree_comparison (TREE_CODE (cond
));
647 limit
= TREE_OPERAND (cond
, 0);
648 op
= TREE_OPERAND (cond
, 1);
650 extract_range_for_var_from_comparison_expr (var
, cond_code
, op
,
654 /* Extract range information from SSA name VAR and store it in VR. If
655 VAR has an interesting range, use it. Otherwise, create the
656 range [VAR, VAR] and return it. This is useful in situations where
657 we may have conditionals testing values of VARYING names. For
664 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
668 vr_values::extract_range_from_ssa_name (value_range
*vr
, tree var
)
670 value_range
*var_vr
= get_value_range (var
);
672 if (!var_vr
->varying_p ())
673 vr
->deep_copy (var_vr
);
675 set_value_range (vr
, VR_RANGE
, var
, var
, NULL
);
677 vr
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
680 /* Extract range information from a binary expression OP0 CODE OP1 based on
681 the ranges of each of its operands with resulting type EXPR_TYPE.
682 The resulting range is stored in *VR. */
685 vr_values::extract_range_from_binary_expr (value_range
*vr
,
687 tree expr_type
, tree op0
, tree op1
)
689 /* Get value ranges for each operand. For constant operands, create
690 a new value range with the operand to simplify processing. */
691 value_range vr0
, vr1
;
692 if (TREE_CODE (op0
) == SSA_NAME
)
693 vr0
= *(get_value_range (op0
));
694 else if (is_gimple_min_invariant (op0
))
695 set_value_range_to_value (&vr0
, op0
, NULL
);
699 if (TREE_CODE (op1
) == SSA_NAME
)
700 vr1
= *(get_value_range (op1
));
701 else if (is_gimple_min_invariant (op1
))
702 set_value_range_to_value (&vr1
, op1
, NULL
);
706 /* If one argument is varying, we can sometimes still deduce a
707 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
708 if (INTEGRAL_TYPE_P (TREE_TYPE (op0
))
709 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0
)))
711 if (vr0
.varying_p () && !vr1
.varying_p ())
712 vr0
= value_range (VR_RANGE
,
713 vrp_val_min (expr_type
),
714 vrp_val_max (expr_type
));
715 else if (vr1
.varying_p () && !vr0
.varying_p ())
716 vr1
= value_range (VR_RANGE
,
717 vrp_val_min (expr_type
),
718 vrp_val_max (expr_type
));
721 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &vr0
, &vr1
);
723 /* Set value_range for n in following sequence:
724 def = __builtin_memchr (arg, 0, sz)
726 Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
729 && code
== POINTER_DIFF_EXPR
730 && TREE_CODE (op0
) == SSA_NAME
731 && TREE_CODE (op1
) == SSA_NAME
)
733 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
734 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
735 gcall
*call_stmt
= NULL
;
737 if (TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
738 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
739 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
740 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
741 && (call_stmt
= dyn_cast
<gcall
*>(SSA_NAME_DEF_STMT (op0
)))
742 && gimple_call_builtin_p (call_stmt
, BUILT_IN_MEMCHR
)
743 && operand_equal_p (op0
, gimple_call_lhs (call_stmt
), 0)
744 && operand_equal_p (op1
, gimple_call_arg (call_stmt
, 0), 0)
745 && integer_zerop (gimple_call_arg (call_stmt
, 1)))
747 tree max
= vrp_val_max (ptrdiff_type_node
);
748 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
749 tree range_min
= build_zero_cst (expr_type
);
750 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
751 set_value_range (vr
, VR_RANGE
, range_min
, range_max
, NULL
);
756 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
757 and based on the other operand, for example if it was deduced from a
758 symbolic comparison. When a bound of the range of the first operand
759 is invariant, we set the corresponding bound of the new range to INF
760 in order to avoid recursing on the range of the second operand. */
762 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
763 && TREE_CODE (op1
) == SSA_NAME
764 && vr0
.kind () == VR_RANGE
765 && symbolic_range_based_on_p (&vr0
, op1
))
767 const bool minus_p
= (code
== MINUS_EXPR
);
770 /* Try with VR0 and [-INF, OP1]. */
771 if (is_gimple_min_invariant (minus_p
? vr0
.max () : vr0
.min ()))
772 set_value_range (&n_vr1
, VR_RANGE
, vrp_val_min (expr_type
), op1
, NULL
);
774 /* Try with VR0 and [OP1, +INF]. */
775 else if (is_gimple_min_invariant (minus_p
? vr0
.min () : vr0
.max ()))
776 set_value_range (&n_vr1
, VR_RANGE
, op1
, vrp_val_max (expr_type
), NULL
);
778 /* Try with VR0 and [OP1, OP1]. */
780 set_value_range (&n_vr1
, VR_RANGE
, op1
, op1
, NULL
);
782 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &vr0
, &n_vr1
);
786 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
787 && TREE_CODE (op0
) == SSA_NAME
788 && vr1
.kind () == VR_RANGE
789 && symbolic_range_based_on_p (&vr1
, op0
))
791 const bool minus_p
= (code
== MINUS_EXPR
);
794 /* Try with [-INF, OP0] and VR1. */
795 if (is_gimple_min_invariant (minus_p
? vr1
.max () : vr1
.min ()))
796 set_value_range (&n_vr0
, VR_RANGE
, vrp_val_min (expr_type
), op0
, NULL
);
798 /* Try with [OP0, +INF] and VR1. */
799 else if (is_gimple_min_invariant (minus_p
? vr1
.min (): vr1
.max ()))
800 set_value_range (&n_vr0
, VR_RANGE
, op0
, vrp_val_max (expr_type
), NULL
);
802 /* Try with [OP0, OP0] and VR1. */
804 set_value_range (&n_vr0
, VR_RANGE
, op0
, op0
, NULL
);
806 extract_range_from_binary_expr_1 (vr
, code
, expr_type
, &n_vr0
, &vr1
);
809 /* If we didn't derive a range for MINUS_EXPR, and
810 op1's range is ~[op0,op0] or vice-versa, then we
811 can derive a non-null range. This happens often for
812 pointer subtraction. */
814 && (code
== MINUS_EXPR
|| code
== POINTER_DIFF_EXPR
)
815 && TREE_CODE (op0
) == SSA_NAME
816 && ((vr0
.kind () == VR_ANTI_RANGE
818 && vr0
.min () == vr0
.max ())
819 || (vr1
.kind () == VR_ANTI_RANGE
821 && vr1
.min () == vr1
.max ())))
822 set_value_range_to_nonnull (vr
, expr_type
);
825 /* Extract range information from a unary expression CODE OP0 based on
826 the range of its operand with resulting type TYPE.
827 The resulting range is stored in *VR. */
830 vr_values::extract_range_from_unary_expr (value_range
*vr
, enum tree_code code
,
835 /* Get value ranges for the operand. For constant operands, create
836 a new value range with the operand to simplify processing. */
837 if (TREE_CODE (op0
) == SSA_NAME
)
838 vr0
= *(get_value_range (op0
));
839 else if (is_gimple_min_invariant (op0
))
840 set_value_range_to_value (&vr0
, op0
, NULL
);
844 ::extract_range_from_unary_expr (vr
, code
, type
, &vr0
, TREE_TYPE (op0
));
848 /* Extract range information from a conditional expression STMT based on
849 the ranges of each of its operands and the expression code. */
852 vr_values::extract_range_from_cond_expr (value_range
*vr
, gassign
*stmt
)
854 /* Get value ranges for each operand. For constant operands, create
855 a new value range with the operand to simplify processing. */
856 tree op0
= gimple_assign_rhs2 (stmt
);
858 if (TREE_CODE (op0
) == SSA_NAME
)
859 vr0
= *(get_value_range (op0
));
860 else if (is_gimple_min_invariant (op0
))
861 set_value_range_to_value (&vr0
, op0
, NULL
);
865 tree op1
= gimple_assign_rhs3 (stmt
);
867 if (TREE_CODE (op1
) == SSA_NAME
)
868 vr1
= *(get_value_range (op1
));
869 else if (is_gimple_min_invariant (op1
))
870 set_value_range_to_value (&vr1
, op1
, NULL
);
874 /* The resulting value range is the union of the operand ranges */
875 vr
->deep_copy (&vr0
);
880 /* Extract range information from a comparison expression EXPR based
881 on the range of its operand and the expression code. */
884 vr_values::extract_range_from_comparison (value_range
*vr
, enum tree_code code
,
885 tree type
, tree op0
, tree op1
)
890 val
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, false, &sop
,
894 /* Since this expression was found on the RHS of an assignment,
895 its type may be different from _Bool. Convert VAL to EXPR's
897 val
= fold_convert (type
, val
);
898 if (is_gimple_min_invariant (val
))
899 set_value_range_to_value (vr
, val
, NULL
);
901 vr
->update (VR_RANGE
, val
, val
);
904 /* The result of a comparison is always true or false. */
905 set_value_range_to_truthvalue (vr
, type
);
908 /* Helper function for simplify_internal_call_using_ranges and
909 extract_range_basic. Return true if OP0 SUBCODE OP1 for
910 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
911 always overflow. Set *OVF to true if it is known to always
915 vr_values::check_for_binary_op_overflow (enum tree_code subcode
, tree type
,
916 tree op0
, tree op1
, bool *ovf
)
918 value_range vr0
, vr1
;
919 if (TREE_CODE (op0
) == SSA_NAME
)
920 vr0
= *get_value_range (op0
);
921 else if (TREE_CODE (op0
) == INTEGER_CST
)
922 set_value_range_to_value (&vr0
, op0
, NULL
);
926 if (TREE_CODE (op1
) == SSA_NAME
)
927 vr1
= *get_value_range (op1
);
928 else if (TREE_CODE (op1
) == INTEGER_CST
)
929 set_value_range_to_value (&vr1
, op1
, NULL
);
933 tree vr0min
= vr0
.min (), vr0max
= vr0
.max ();
934 tree vr1min
= vr1
.min (), vr1max
= vr1
.max ();
935 if (!range_int_cst_p (&vr0
)
936 || TREE_OVERFLOW (vr0min
)
937 || TREE_OVERFLOW (vr0max
))
939 vr0min
= vrp_val_min (TREE_TYPE (op0
));
940 vr0max
= vrp_val_max (TREE_TYPE (op0
));
942 if (!range_int_cst_p (&vr1
)
943 || TREE_OVERFLOW (vr1min
)
944 || TREE_OVERFLOW (vr1max
))
946 vr1min
= vrp_val_min (TREE_TYPE (op1
));
947 vr1max
= vrp_val_max (TREE_TYPE (op1
));
949 *ovf
= arith_overflowed_p (subcode
, type
, vr0min
,
950 subcode
== MINUS_EXPR
? vr1max
: vr1min
);
951 if (arith_overflowed_p (subcode
, type
, vr0max
,
952 subcode
== MINUS_EXPR
? vr1min
: vr1max
) != *ovf
)
954 if (subcode
== MULT_EXPR
)
956 if (arith_overflowed_p (subcode
, type
, vr0min
, vr1max
) != *ovf
957 || arith_overflowed_p (subcode
, type
, vr0max
, vr1min
) != *ovf
)
962 /* So far we found that there is an overflow on the boundaries.
963 That doesn't prove that there is an overflow even for all values
964 in between the boundaries. For that compute widest_int range
965 of the result and see if it doesn't overlap the range of
967 widest_int wmin
, wmax
;
970 w
[0] = wi::to_widest (vr0min
);
971 w
[1] = wi::to_widest (vr0max
);
972 w
[2] = wi::to_widest (vr1min
);
973 w
[3] = wi::to_widest (vr1max
);
974 for (i
= 0; i
< 4; i
++)
980 wt
= wi::add (w
[i
& 1], w
[2 + (i
& 2) / 2]);
983 wt
= wi::sub (w
[i
& 1], w
[2 + (i
& 2) / 2]);
986 wt
= wi::mul (w
[i
& 1], w
[2 + (i
& 2) / 2]);
998 wmin
= wi::smin (wmin
, wt
);
999 wmax
= wi::smax (wmax
, wt
);
1002 /* The result of op0 CODE op1 is known to be in range
1004 widest_int wtmin
= wi::to_widest (vrp_val_min (type
));
1005 widest_int wtmax
= wi::to_widest (vrp_val_max (type
));
1006 /* If all values in [wmin, wmax] are smaller than
1007 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1008 the arithmetic operation will always overflow. */
1009 if (wmax
< wtmin
|| wmin
> wtmax
)
1016 /* Try to derive a nonnegative or nonzero range out of STMT relying
1017 primarily on generic routines in fold in conjunction with range data.
1018 Store the result in *VR */
1021 vr_values::extract_range_basic (value_range
*vr
, gimple
*stmt
)
1024 tree type
= gimple_expr_type (stmt
);
1026 if (is_gimple_call (stmt
))
1029 int mini
, maxi
, zerov
= 0, prec
;
1030 enum tree_code subcode
= ERROR_MARK
;
1031 combined_fn cfn
= gimple_call_combined_fn (stmt
);
1032 scalar_int_mode mode
;
1036 case CFN_BUILT_IN_CONSTANT_P
:
1037 /* If the call is __builtin_constant_p and the argument is a
1038 function parameter resolve it to false. This avoids bogus
1039 array bound warnings.
1040 ??? We could do this as early as inlining is finished. */
1041 arg
= gimple_call_arg (stmt
, 0);
1042 if (TREE_CODE (arg
) == SSA_NAME
1043 && SSA_NAME_IS_DEFAULT_DEF (arg
)
1044 && TREE_CODE (SSA_NAME_VAR (arg
)) == PARM_DECL
1045 && cfun
->after_inlining
)
1047 set_value_range_to_null (vr
, type
);
1051 /* Both __builtin_ffs* and __builtin_popcount return
1055 arg
= gimple_call_arg (stmt
, 0);
1056 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1059 if (TREE_CODE (arg
) == SSA_NAME
)
1061 value_range
*vr0
= get_value_range (arg
);
1062 /* If arg is non-zero, then ffs or popcount are non-zero. */
1063 if (range_includes_zero_p (vr0
) == 0)
1065 /* If some high bits are known to be zero,
1066 we can decrease the maximum. */
1067 if (vr0
->kind () == VR_RANGE
1068 && TREE_CODE (vr0
->max ()) == INTEGER_CST
1069 && !operand_less_p (vr0
->min (),
1070 build_zero_cst (TREE_TYPE (vr0
->min ()))))
1071 maxi
= tree_floor_log2 (vr0
->max ()) + 1;
1074 /* __builtin_parity* returns [0, 1]. */
1079 /* __builtin_c[lt]z* return [0, prec-1], except for
1080 when the argument is 0, but that is undefined behavior.
1081 On many targets where the CLZ RTL or optab value is defined
1082 for 0 the value is prec, so include that in the range
1085 arg
= gimple_call_arg (stmt
, 0);
1086 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1089 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1090 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
1091 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
)
1092 /* Handle only the single common value. */
1094 /* Magic value to give up, unless vr0 proves
1097 if (TREE_CODE (arg
) == SSA_NAME
)
1099 value_range
*vr0
= get_value_range (arg
);
1100 /* From clz of VR_RANGE minimum we can compute
1102 if (vr0
->kind () == VR_RANGE
1103 && TREE_CODE (vr0
->min ()) == INTEGER_CST
)
1105 maxi
= prec
- 1 - tree_floor_log2 (vr0
->min ());
1109 else if (vr0
->kind () == VR_ANTI_RANGE
1110 && integer_zerop (vr0
->min ()))
1117 /* From clz of VR_RANGE maximum we can compute
1119 if (vr0
->kind () == VR_RANGE
1120 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1122 mini
= prec
- 1 - tree_floor_log2 (vr0
->max ());
1130 /* __builtin_ctz* return [0, prec-1], except for
1131 when the argument is 0, but that is undefined behavior.
1132 If there is a ctz optab for this mode and
1133 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1134 otherwise just assume 0 won't be seen. */
1136 arg
= gimple_call_arg (stmt
, 0);
1137 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1140 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1141 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1142 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
))
1144 /* Handle only the two common values. */
1147 else if (zerov
== prec
)
1150 /* Magic value to give up, unless vr0 proves
1154 if (TREE_CODE (arg
) == SSA_NAME
)
1156 value_range
*vr0
= get_value_range (arg
);
1157 /* If arg is non-zero, then use [0, prec - 1]. */
1158 if ((vr0
->kind () == VR_RANGE
1159 && integer_nonzerop (vr0
->min ()))
1160 || (vr0
->kind () == VR_ANTI_RANGE
1161 && integer_zerop (vr0
->min ())))
1166 /* If some high bits are known to be zero,
1167 we can decrease the result maximum. */
1168 if (vr0
->kind () == VR_RANGE
1169 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1171 maxi
= tree_floor_log2 (vr0
->max ());
1172 /* For vr0 [0, 0] give up. */
1180 /* __builtin_clrsb* returns [0, prec-1]. */
1182 arg
= gimple_call_arg (stmt
, 0);
1183 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1188 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, mini
),
1189 build_int_cst (type
, maxi
), NULL
);
1191 case CFN_UBSAN_CHECK_ADD
:
1192 subcode
= PLUS_EXPR
;
1194 case CFN_UBSAN_CHECK_SUB
:
1195 subcode
= MINUS_EXPR
;
1197 case CFN_UBSAN_CHECK_MUL
:
1198 subcode
= MULT_EXPR
;
1200 case CFN_GOACC_DIM_SIZE
:
1201 case CFN_GOACC_DIM_POS
:
1202 /* Optimizing these two internal functions helps the loop
1203 optimizer eliminate outer comparisons. Size is [1,N]
1204 and pos is [0,N-1]. */
1206 bool is_pos
= cfn
== CFN_GOACC_DIM_POS
;
1207 int axis
= oacc_get_ifn_dim_arg (stmt
);
1208 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1211 /* If it's dynamic, the backend might know a hardware
1213 size
= targetm
.goacc
.dim_limit (axis
);
1215 tree type
= TREE_TYPE (gimple_call_lhs (stmt
));
1216 set_value_range (vr
, VR_RANGE
,
1217 build_int_cst (type
, is_pos
? 0 : 1),
1218 size
? build_int_cst (type
, size
- is_pos
)
1219 : vrp_val_max (type
), NULL
);
1222 case CFN_BUILT_IN_STRLEN
:
1223 if (tree lhs
= gimple_call_lhs (stmt
))
1224 if (ptrdiff_type_node
1225 && (TYPE_PRECISION (ptrdiff_type_node
)
1226 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1228 tree type
= TREE_TYPE (lhs
);
1229 tree max
= vrp_val_max (ptrdiff_type_node
);
1230 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1231 tree range_min
= build_zero_cst (type
);
1232 tree range_max
= wide_int_to_tree (type
, wmax
- 1);
1233 set_value_range (vr
, VR_RANGE
, range_min
, range_max
, NULL
);
1240 if (subcode
!= ERROR_MARK
)
1242 bool saved_flag_wrapv
= flag_wrapv
;
1243 /* Pretend the arithmetics is wrapping. If there is
1244 any overflow, we'll complain, but will actually do
1245 wrapping operation. */
1247 extract_range_from_binary_expr (vr
, subcode
, type
,
1248 gimple_call_arg (stmt
, 0),
1249 gimple_call_arg (stmt
, 1));
1250 flag_wrapv
= saved_flag_wrapv
;
1252 /* If for both arguments vrp_valueize returned non-NULL,
1253 this should have been already folded and if not, it
1254 wasn't folded because of overflow. Avoid removing the
1255 UBSAN_CHECK_* calls in that case. */
1256 if (vr
->kind () == VR_RANGE
1257 && (vr
->min () == vr
->max ()
1258 || operand_equal_p (vr
->min (), vr
->max (), 0)))
1263 /* Handle extraction of the two results (result of arithmetics and
1264 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1265 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1266 else if (is_gimple_assign (stmt
)
1267 && (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
1268 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
)
1269 && INTEGRAL_TYPE_P (type
))
1271 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1272 tree op
= gimple_assign_rhs1 (stmt
);
1273 if (TREE_CODE (op
) == code
&& TREE_CODE (TREE_OPERAND (op
, 0)) == SSA_NAME
)
1275 gimple
*g
= SSA_NAME_DEF_STMT (TREE_OPERAND (op
, 0));
1276 if (is_gimple_call (g
) && gimple_call_internal_p (g
))
1278 enum tree_code subcode
= ERROR_MARK
;
1279 switch (gimple_call_internal_fn (g
))
1281 case IFN_ADD_OVERFLOW
:
1282 subcode
= PLUS_EXPR
;
1284 case IFN_SUB_OVERFLOW
:
1285 subcode
= MINUS_EXPR
;
1287 case IFN_MUL_OVERFLOW
:
1288 subcode
= MULT_EXPR
;
1290 case IFN_ATOMIC_COMPARE_EXCHANGE
:
1291 if (code
== IMAGPART_EXPR
)
1293 /* This is the boolean return value whether compare and
1294 exchange changed anything or not. */
1295 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, 0),
1296 build_int_cst (type
, 1), NULL
);
1303 if (subcode
!= ERROR_MARK
)
1305 tree op0
= gimple_call_arg (g
, 0);
1306 tree op1
= gimple_call_arg (g
, 1);
1307 if (code
== IMAGPART_EXPR
)
1310 if (check_for_binary_op_overflow (subcode
, type
,
1312 set_value_range_to_value (vr
,
1313 build_int_cst (type
, ovf
),
1315 else if (TYPE_PRECISION (type
) == 1
1316 && !TYPE_UNSIGNED (type
))
1319 set_value_range (vr
, VR_RANGE
, build_int_cst (type
, 0),
1320 build_int_cst (type
, 1), NULL
);
1322 else if (types_compatible_p (type
, TREE_TYPE (op0
))
1323 && types_compatible_p (type
, TREE_TYPE (op1
)))
1325 bool saved_flag_wrapv
= flag_wrapv
;
1326 /* Pretend the arithmetics is wrapping. If there is
1327 any overflow, IMAGPART_EXPR will be set. */
1329 extract_range_from_binary_expr (vr
, subcode
, type
,
1331 flag_wrapv
= saved_flag_wrapv
;
1335 value_range vr0
, vr1
;
1336 bool saved_flag_wrapv
= flag_wrapv
;
1337 /* Pretend the arithmetics is wrapping. If there is
1338 any overflow, IMAGPART_EXPR will be set. */
1340 extract_range_from_unary_expr (&vr0
, NOP_EXPR
,
1342 extract_range_from_unary_expr (&vr1
, NOP_EXPR
,
1344 extract_range_from_binary_expr_1 (vr
, subcode
, type
,
1346 flag_wrapv
= saved_flag_wrapv
;
1353 if (INTEGRAL_TYPE_P (type
)
1354 && gimple_stmt_nonnegative_warnv_p (stmt
, &sop
))
1355 set_value_range_to_nonnegative (vr
, type
);
1356 else if (vrp_stmt_computes_nonzero (stmt
))
1357 set_value_range_to_nonnull (vr
, type
);
1363 /* Try to compute a useful range out of assignment STMT and store it
1367 vr_values::extract_range_from_assignment (value_range
*vr
, gassign
*stmt
)
1369 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1371 if (code
== ASSERT_EXPR
)
1372 extract_range_from_assert (vr
, gimple_assign_rhs1 (stmt
));
1373 else if (code
== SSA_NAME
)
1374 extract_range_from_ssa_name (vr
, gimple_assign_rhs1 (stmt
));
1375 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
1376 extract_range_from_binary_expr (vr
, gimple_assign_rhs_code (stmt
),
1377 gimple_expr_type (stmt
),
1378 gimple_assign_rhs1 (stmt
),
1379 gimple_assign_rhs2 (stmt
));
1380 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1381 extract_range_from_unary_expr (vr
, gimple_assign_rhs_code (stmt
),
1382 gimple_expr_type (stmt
),
1383 gimple_assign_rhs1 (stmt
));
1384 else if (code
== COND_EXPR
)
1385 extract_range_from_cond_expr (vr
, stmt
);
1386 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1387 extract_range_from_comparison (vr
, gimple_assign_rhs_code (stmt
),
1388 gimple_expr_type (stmt
),
1389 gimple_assign_rhs1 (stmt
),
1390 gimple_assign_rhs2 (stmt
));
1391 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1392 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1393 set_value_range_to_value (vr
, gimple_assign_rhs1 (stmt
), NULL
);
1397 if (vr
->varying_p ())
1398 extract_range_basic (vr
, stmt
);
1401 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1403 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1404 all the values in the ranges.
1406 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1408 - Return NULL_TREE if it is not always possible to determine the
1409 value of the comparison.
1411 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1412 assumed signed overflow is undefined. */
1416 compare_ranges (enum tree_code comp
, value_range
*vr0
, value_range
*vr1
,
1417 bool *strict_overflow_p
)
1419 /* VARYING or UNDEFINED ranges cannot be compared. */
1420 if (vr0
->varying_p ()
1421 || vr0
->undefined_p ()
1422 || vr1
->varying_p ()
1423 || vr1
->undefined_p ())
1426 /* Anti-ranges need to be handled separately. */
1427 if (vr0
->kind () == VR_ANTI_RANGE
|| vr1
->kind () == VR_ANTI_RANGE
)
1429 /* If both are anti-ranges, then we cannot compute any
1431 if (vr0
->kind () == VR_ANTI_RANGE
&& vr1
->kind () == VR_ANTI_RANGE
)
1434 /* These comparisons are never statically computable. */
1441 /* Equality can be computed only between a range and an
1442 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1443 if (vr0
->kind () == VR_RANGE
)
1445 /* To simplify processing, make VR0 the anti-range. */
1446 value_range
*tmp
= vr0
;
1451 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1453 if (compare_values_warnv (vr0
->min (), vr1
->min (), strict_overflow_p
) == 0
1454 && compare_values_warnv (vr0
->max (), vr1
->max (), strict_overflow_p
) == 0)
1455 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1460 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1461 operands around and change the comparison code. */
1462 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1464 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1465 std::swap (vr0
, vr1
);
1468 if (comp
== EQ_EXPR
)
1470 /* Equality may only be computed if both ranges represent
1471 exactly one value. */
1472 if (compare_values_warnv (vr0
->min (), vr0
->max (), strict_overflow_p
) == 0
1473 && compare_values_warnv (vr1
->min (), vr1
->max (), strict_overflow_p
) == 0)
1475 int cmp_min
= compare_values_warnv (vr0
->min (), vr1
->min (),
1477 int cmp_max
= compare_values_warnv (vr0
->max (), vr1
->max (),
1479 if (cmp_min
== 0 && cmp_max
== 0)
1480 return boolean_true_node
;
1481 else if (cmp_min
!= -2 && cmp_max
!= -2)
1482 return boolean_false_node
;
1484 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1485 else if (compare_values_warnv (vr0
->min (), vr1
->max (),
1486 strict_overflow_p
) == 1
1487 || compare_values_warnv (vr1
->min (), vr0
->max (),
1488 strict_overflow_p
) == 1)
1489 return boolean_false_node
;
1493 else if (comp
== NE_EXPR
)
1497 /* If VR0 is completely to the left or completely to the right
1498 of VR1, they are always different. Notice that we need to
1499 make sure that both comparisons yield similar results to
1500 avoid comparing values that cannot be compared at
1502 cmp1
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1503 cmp2
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1504 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1505 return boolean_true_node
;
1507 /* If VR0 and VR1 represent a single value and are identical,
1509 else if (compare_values_warnv (vr0
->min (), vr0
->max (),
1510 strict_overflow_p
) == 0
1511 && compare_values_warnv (vr1
->min (), vr1
->max (),
1512 strict_overflow_p
) == 0
1513 && compare_values_warnv (vr0
->min (), vr1
->min (),
1514 strict_overflow_p
) == 0
1515 && compare_values_warnv (vr0
->max (), vr1
->max (),
1516 strict_overflow_p
) == 0)
1517 return boolean_false_node
;
1519 /* Otherwise, they may or may not be different. */
1523 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1527 /* If VR0 is to the left of VR1, return true. */
1528 tst
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1529 if ((comp
== LT_EXPR
&& tst
== -1)
1530 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1531 return boolean_true_node
;
1533 /* If VR0 is to the right of VR1, return false. */
1534 tst
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1535 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1536 || (comp
== LE_EXPR
&& tst
== 1))
1537 return boolean_false_node
;
1539 /* Otherwise, we don't know. */
1546 /* Given a value range VR, a value VAL and a comparison code COMP, return
1547 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1548 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1549 always returns false. Return NULL_TREE if it is not always
1550 possible to determine the value of the comparison. Also set
1551 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1552 assumed signed overflow is undefined. */
1555 compare_range_with_value (enum tree_code comp
, value_range
*vr
, tree val
,
1556 bool *strict_overflow_p
)
1558 if (vr
->varying_p () || vr
->undefined_p ())
1561 /* Anti-ranges need to be handled separately. */
1562 if (vr
->kind () == VR_ANTI_RANGE
)
1564 /* For anti-ranges, the only predicates that we can compute at
1565 compile time are equality and inequality. */
1572 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1573 if (value_inside_range (val
, vr
->min (), vr
->max ()) == 1)
1574 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1579 if (comp
== EQ_EXPR
)
1581 /* EQ_EXPR may only be computed if VR represents exactly
1583 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0)
1585 int cmp
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1587 return boolean_true_node
;
1588 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1589 return boolean_false_node
;
1591 else if (compare_values_warnv (val
, vr
->min (), strict_overflow_p
) == -1
1592 || compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1)
1593 return boolean_false_node
;
1597 else if (comp
== NE_EXPR
)
1599 /* If VAL is not inside VR, then they are always different. */
1600 if (compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1
1601 || compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 1)
1602 return boolean_true_node
;
1604 /* If VR represents exactly one value equal to VAL, then return
1606 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0
1607 && compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 0)
1608 return boolean_false_node
;
1610 /* Otherwise, they may or may not be different. */
1613 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1617 /* If VR is to the left of VAL, return true. */
1618 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1619 if ((comp
== LT_EXPR
&& tst
== -1)
1620 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1621 return boolean_true_node
;
1623 /* If VR is to the right of VAL, return false. */
1624 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1625 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1626 || (comp
== LE_EXPR
&& tst
== 1))
1627 return boolean_false_node
;
1629 /* Otherwise, we don't know. */
1632 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1636 /* If VR is to the right of VAL, return true. */
1637 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1638 if ((comp
== GT_EXPR
&& tst
== 1)
1639 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1640 return boolean_true_node
;
1642 /* If VR is to the left of VAL, return false. */
1643 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1644 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1645 || (comp
== GE_EXPR
&& tst
== -1))
1646 return boolean_false_node
;
1648 /* Otherwise, we don't know. */
1654 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1655 would be profitable to adjust VR using scalar evolution information
1656 for VAR. If so, update VR with the new limits. */
1659 vr_values::adjust_range_with_scev (value_range
*vr
, struct loop
*loop
,
1660 gimple
*stmt
, tree var
)
1662 tree init
, step
, chrec
, tmin
, tmax
, min
, max
, type
, tem
;
1663 enum ev_direction dir
;
1665 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1666 better opportunities than a regular range, but I'm not sure. */
1667 if (vr
->kind () == VR_ANTI_RANGE
)
1670 chrec
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, var
));
1672 /* Like in PR19590, scev can return a constant function. */
1673 if (is_gimple_min_invariant (chrec
))
1675 set_value_range_to_value (vr
, chrec
, NULL
);
1679 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1682 init
= initial_condition_in_loop_num (chrec
, loop
->num
);
1683 tem
= op_with_constant_singleton_value_range (init
);
1686 step
= evolution_part_in_loop_num (chrec
, loop
->num
);
1687 tem
= op_with_constant_singleton_value_range (step
);
1691 /* If STEP is symbolic, we can't know whether INIT will be the
1692 minimum or maximum value in the range. Also, unless INIT is
1693 a simple expression, compare_values and possibly other functions
1694 in tree-vrp won't be able to handle it. */
1695 if (step
== NULL_TREE
1696 || !is_gimple_min_invariant (step
)
1697 || !valid_value_p (init
))
1700 dir
= scev_direction (chrec
);
1701 if (/* Do not adjust ranges if we do not know whether the iv increases
1702 or decreases, ... */
1703 dir
== EV_DIR_UNKNOWN
1704 /* ... or if it may wrap. */
1705 || scev_probably_wraps_p (NULL_TREE
, init
, step
, stmt
,
1706 get_chrec_loop (chrec
), true))
1709 type
= TREE_TYPE (var
);
1710 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1711 tmin
= lower_bound_in_type (type
, type
);
1713 tmin
= TYPE_MIN_VALUE (type
);
1714 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1715 tmax
= upper_bound_in_type (type
, type
);
1717 tmax
= TYPE_MAX_VALUE (type
);
1719 /* Try to use estimated number of iterations for the loop to constrain the
1720 final value in the evolution. */
1721 if (TREE_CODE (step
) == INTEGER_CST
1722 && is_gimple_val (init
)
1723 && (TREE_CODE (init
) != SSA_NAME
1724 || get_value_range (init
)->kind () == VR_RANGE
))
1728 /* We are only entering here for loop header PHI nodes, so using
1729 the number of latch executions is the correct thing to use. */
1730 if (max_loop_iterations (loop
, &nit
))
1733 signop sgn
= TYPE_SIGN (TREE_TYPE (step
));
1734 wi::overflow_type overflow
;
1736 widest_int wtmp
= wi::mul (wi::to_widest (step
), nit
, sgn
,
1738 /* If the multiplication overflowed we can't do a meaningful
1739 adjustment. Likewise if the result doesn't fit in the type
1740 of the induction variable. For a signed type we have to
1741 check whether the result has the expected signedness which
1742 is that of the step as number of iterations is unsigned. */
1744 && wi::fits_to_tree_p (wtmp
, TREE_TYPE (init
))
1746 || wi::gts_p (wtmp
, 0) == wi::gts_p (wi::to_wide (step
), 0)))
1748 tem
= wide_int_to_tree (TREE_TYPE (init
), wtmp
);
1749 extract_range_from_binary_expr (&maxvr
, PLUS_EXPR
,
1750 TREE_TYPE (init
), init
, tem
);
1751 /* Likewise if the addition did. */
1752 if (maxvr
.kind () == VR_RANGE
)
1756 if (TREE_CODE (init
) == SSA_NAME
)
1757 initvr
= *(get_value_range (init
));
1758 else if (is_gimple_min_invariant (init
))
1759 set_value_range_to_value (&initvr
, init
, NULL
);
1763 /* Check if init + nit * step overflows. Though we checked
1764 scev {init, step}_loop doesn't wrap, it is not enough
1765 because the loop may exit immediately. Overflow could
1766 happen in the plus expression in this case. */
1767 if ((dir
== EV_DIR_DECREASES
1768 && compare_values (maxvr
.min (), initvr
.min ()) != -1)
1769 || (dir
== EV_DIR_GROWS
1770 && compare_values (maxvr
.max (), initvr
.max ()) != 1))
1773 tmin
= maxvr
.min ();
1774 tmax
= maxvr
.max ();
1780 if (vr
->varying_p () || vr
->undefined_p ())
1785 /* For VARYING or UNDEFINED ranges, just about anything we get
1786 from scalar evolutions should be better. */
1788 if (dir
== EV_DIR_DECREASES
)
1793 else if (vr
->kind () == VR_RANGE
)
1798 if (dir
== EV_DIR_DECREASES
)
1800 /* INIT is the maximum value. If INIT is lower than VR->MAX ()
1801 but no smaller than VR->MIN (), set VR->MAX () to INIT. */
1802 if (compare_values (init
, max
) == -1)
1805 /* According to the loop information, the variable does not
1807 if (compare_values (min
, tmin
) == -1)
1813 /* If INIT is bigger than VR->MIN (), set VR->MIN () to INIT. */
1814 if (compare_values (init
, min
) == 1)
1817 if (compare_values (tmax
, max
) == -1)
1824 /* If we just created an invalid range with the minimum
1825 greater than the maximum, we fail conservatively.
1826 This should happen only in unreachable
1827 parts of code, or for invalid programs. */
1828 if (compare_values (min
, max
) == 1)
1831 /* Even for valid range info, sometimes overflow flag will leak in.
1832 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1834 if (TREE_OVERFLOW_P (min
))
1835 min
= drop_tree_overflow (min
);
1836 if (TREE_OVERFLOW_P (max
))
1837 max
= drop_tree_overflow (max
);
1839 vr
->update (VR_RANGE
, min
, max
);
1842 /* Dump value ranges of all SSA_NAMEs to FILE. */
1845 vr_values::dump_all_value_ranges (FILE *file
)
1849 for (i
= 0; i
< num_vr_values
; i
++)
1853 print_generic_expr (file
, ssa_name (i
));
1854 fprintf (file
, ": ");
1855 dump_value_range (file
, vr_value
[i
]);
1856 fprintf (file
, "\n");
1860 fprintf (file
, "\n");
1863 /* Initialize VRP lattice. */
1865 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
1867 values_propagated
= false;
1868 num_vr_values
= num_ssa_names
;
1869 vr_value
= XCNEWVEC (value_range
*, num_vr_values
);
1870 vr_phi_edge_counts
= XCNEWVEC (int, num_ssa_names
);
1871 bitmap_obstack_initialize (&vrp_equiv_obstack
);
1872 to_remove_edges
= vNULL
;
1873 to_update_switch_stmts
= vNULL
;
1876 /* Free VRP lattice. */
1878 vr_values::~vr_values ()
1880 /* Free allocated memory. */
1882 free (vr_phi_edge_counts
);
1883 bitmap_obstack_release (&vrp_equiv_obstack
);
1884 vrp_value_range_pool
.release ();
1886 /* So that we can distinguish between VRP data being available
1887 and not available. */
1889 vr_phi_edge_counts
= NULL
;
1891 /* If there are entries left in TO_REMOVE_EDGES or TO_UPDATE_SWITCH_STMTS
1892 then an EVRP client did not clean up properly. Catch it now rather
1893 than seeing something more obscure later. */
1894 gcc_assert (to_remove_edges
.is_empty ()
1895 && to_update_switch_stmts
.is_empty ());
1900 static class vr_values
*x_vr_values
;
1902 /* Return the singleton value-range for NAME or NAME. */
1905 vrp_valueize (tree name
)
1907 if (TREE_CODE (name
) == SSA_NAME
)
1909 value_range
*vr
= x_vr_values
->get_value_range (name
);
1910 if (vr
->kind () == VR_RANGE
1911 && (TREE_CODE (vr
->min ()) == SSA_NAME
1912 || is_gimple_min_invariant (vr
->min ()))
1913 && vrp_operand_equal_p (vr
->min (), vr
->max ()))
1919 /* Return the singleton value-range for NAME if that is a constant
1920 but signal to not follow SSA edges. */
1923 vrp_valueize_1 (tree name
)
1925 if (TREE_CODE (name
) == SSA_NAME
)
1927 /* If the definition may be simulated again we cannot follow
1928 this SSA edge as the SSA propagator does not necessarily
1929 re-visit the use. */
1930 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1931 if (!gimple_nop_p (def_stmt
)
1932 && prop_simulate_again_p (def_stmt
))
1934 value_range
*vr
= x_vr_values
->get_value_range (name
);
1936 if (vr
->singleton_p (&singleton
))
1942 /* Given STMT, an assignment or call, return its LHS if the type
1943 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
1946 get_output_for_vrp (gimple
*stmt
)
1948 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
1951 /* We only keep track of ranges in integral and pointer types. */
1952 tree lhs
= gimple_get_lhs (stmt
);
1953 if (TREE_CODE (lhs
) == SSA_NAME
1954 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1955 /* It is valid to have NULL MIN/MAX values on a type. See
1956 build_range_type. */
1957 && TYPE_MIN_VALUE (TREE_TYPE (lhs
))
1958 && TYPE_MAX_VALUE (TREE_TYPE (lhs
)))
1959 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
1965 /* Visit assignment STMT. If it produces an interesting range, record
1966 the range in VR and set LHS to OUTPUT_P. */
1969 vr_values::vrp_visit_assignment_or_call (gimple
*stmt
, tree
*output_p
,
1972 tree lhs
= get_output_for_vrp (stmt
);
1975 /* We only keep track of ranges in integral and pointer types. */
1978 enum gimple_code code
= gimple_code (stmt
);
1980 /* Try folding the statement to a constant first. */
1982 tree tem
= gimple_fold_stmt_to_constant_1 (stmt
, vrp_valueize
,
1987 if (TREE_CODE (tem
) == SSA_NAME
1988 && (SSA_NAME_IS_DEFAULT_DEF (tem
)
1989 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem
))))
1991 extract_range_from_ssa_name (vr
, tem
);
1994 else if (is_gimple_min_invariant (tem
))
1996 set_value_range_to_value (vr
, tem
, NULL
);
2000 /* Then dispatch to value-range extracting functions. */
2001 if (code
== GIMPLE_CALL
)
2002 extract_range_basic (vr
, stmt
);
2004 extract_range_from_assignment (vr
, as_a
<gassign
*> (stmt
));
2008 /* Helper that gets the value range of the SSA_NAME with version I
2009 or a symbolic range containing the SSA_NAME only if the value range
2010 is varying or undefined. */
2013 vr_values::get_vr_for_comparison (int i
)
2015 value_range vr
= *get_value_range (ssa_name (i
));
2017 /* If name N_i does not have a valid range, use N_i as its own
2018 range. This allows us to compare against names that may
2019 have N_i in their ranges. */
2020 if (vr
.varying_p () || vr
.undefined_p ())
2021 vr
= value_range (VR_RANGE
, ssa_name (i
), ssa_name (i
), NULL
);
2026 /* Compare all the value ranges for names equivalent to VAR with VAL
2027 using comparison code COMP. Return the same value returned by
2028 compare_range_with_value, including the setting of
2029 *STRICT_OVERFLOW_P. */
2032 vr_values::compare_name_with_value (enum tree_code comp
, tree var
, tree val
,
2033 bool *strict_overflow_p
, bool use_equiv_p
)
2039 int used_strict_overflow
;
2041 value_range equiv_vr
;
2043 /* Get the set of equivalences for VAR. */
2044 e
= get_value_range (var
)->equiv ();
2046 /* Start at -1. Set it to 0 if we do a comparison without relying
2047 on overflow, or 1 if all comparisons rely on overflow. */
2048 used_strict_overflow
= -1;
2050 /* Compare vars' value range with val. */
2051 equiv_vr
= get_vr_for_comparison (SSA_NAME_VERSION (var
));
2053 retval
= compare_range_with_value (comp
, &equiv_vr
, val
, &sop
);
2055 used_strict_overflow
= sop
? 1 : 0;
2057 /* If the equiv set is empty we have done all work we need to do. */
2061 && used_strict_overflow
> 0)
2062 *strict_overflow_p
= true;
2066 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2068 tree name
= ssa_name (i
);
2073 && ! SSA_NAME_IS_DEFAULT_DEF (name
)
2074 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name
)))
2077 equiv_vr
= get_vr_for_comparison (i
);
2079 t
= compare_range_with_value (comp
, &equiv_vr
, val
, &sop
);
2082 /* If we get different answers from different members
2083 of the equivalence set this check must be in a dead
2084 code region. Folding it to a trap representation
2085 would be correct here. For now just return don't-know. */
2095 used_strict_overflow
= 0;
2096 else if (used_strict_overflow
< 0)
2097 used_strict_overflow
= 1;
2102 && used_strict_overflow
> 0)
2103 *strict_overflow_p
= true;
2109 /* Given a comparison code COMP and names N1 and N2, compare all the
2110 ranges equivalent to N1 against all the ranges equivalent to N2
2111 to determine the value of N1 COMP N2. Return the same value
2112 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2113 whether we relied on undefined signed overflow in the comparison. */
2117 vr_values::compare_names (enum tree_code comp
, tree n1
, tree n2
,
2118 bool *strict_overflow_p
)
2122 bitmap_iterator bi1
, bi2
;
2124 int used_strict_overflow
;
2125 static bitmap_obstack
*s_obstack
= NULL
;
2126 static bitmap s_e1
= NULL
, s_e2
= NULL
;
2128 /* Compare the ranges of every name equivalent to N1 against the
2129 ranges of every name equivalent to N2. */
2130 e1
= get_value_range (n1
)->equiv ();
2131 e2
= get_value_range (n2
)->equiv ();
2133 /* Use the fake bitmaps if e1 or e2 are not available. */
2134 if (s_obstack
== NULL
)
2136 s_obstack
= XNEW (bitmap_obstack
);
2137 bitmap_obstack_initialize (s_obstack
);
2138 s_e1
= BITMAP_ALLOC (s_obstack
);
2139 s_e2
= BITMAP_ALLOC (s_obstack
);
2146 /* Add N1 and N2 to their own set of equivalences to avoid
2147 duplicating the body of the loop just to check N1 and N2
2149 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2150 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2152 /* If the equivalence sets have a common intersection, then the two
2153 names can be compared without checking their ranges. */
2154 if (bitmap_intersect_p (e1
, e2
))
2156 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2157 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2159 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2161 : boolean_false_node
;
2164 /* Start at -1. Set it to 0 if we do a comparison without relying
2165 on overflow, or 1 if all comparisons rely on overflow. */
2166 used_strict_overflow
= -1;
2168 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2169 N2 to their own set of equivalences to avoid duplicating the body
2170 of the loop just to check N1 and N2 ranges. */
2171 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2173 if (! ssa_name (i1
))
2176 value_range vr1
= get_vr_for_comparison (i1
);
2178 t
= retval
= NULL_TREE
;
2179 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2181 if (! ssa_name (i2
))
2186 value_range vr2
= get_vr_for_comparison (i2
);
2188 t
= compare_ranges (comp
, &vr1
, &vr2
, &sop
);
2191 /* If we get different answers from different members
2192 of the equivalence set this check must be in a dead
2193 code region. Folding it to a trap representation
2194 would be correct here. For now just return don't-know. */
2198 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2199 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2205 used_strict_overflow
= 0;
2206 else if (used_strict_overflow
< 0)
2207 used_strict_overflow
= 1;
2213 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2214 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2215 if (used_strict_overflow
> 0)
2216 *strict_overflow_p
= true;
2221 /* None of the equivalent ranges are useful in computing this
2223 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2224 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2228 /* Helper function for vrp_evaluate_conditional_warnv & other
2232 vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2233 (enum tree_code code
, tree op0
, tree op1
, bool * strict_overflow_p
)
2235 value_range
*vr0
, *vr1
;
2237 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
2238 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
2240 tree res
= NULL_TREE
;
2242 res
= compare_ranges (code
, vr0
, vr1
, strict_overflow_p
);
2244 res
= compare_range_with_value (code
, vr0
, op1
, strict_overflow_p
);
2246 res
= (compare_range_with_value
2247 (swap_tree_comparison (code
), vr1
, op0
, strict_overflow_p
));
2251 /* Helper function for vrp_evaluate_conditional_warnv. */
2254 vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code
,
2257 bool *strict_overflow_p
,
2262 *only_ranges
= true;
2264 /* We only deal with integral and pointer types. */
2265 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2266 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
2269 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2270 as a simple equality test, then prefer that over its current form
2273 An overflow test which collapses to an equality test can always be
2274 expressed as a comparison of one argument against zero. Overflow
2275 occurs when the chosen argument is zero and does not occur if the
2276 chosen argument is not zero. */
2278 if (overflow_comparison_p (code
, op0
, op1
, use_equiv_p
, &x
))
2280 wide_int max
= wi::max_value (TYPE_PRECISION (TREE_TYPE (op0
)), UNSIGNED
);
2281 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2282 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2283 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2284 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2285 if (integer_zerop (x
))
2288 code
= (code
== LT_EXPR
|| code
== LE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2290 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2291 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2292 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2293 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2294 else if (wi::to_wide (x
) == max
- 1)
2297 op1
= wide_int_to_tree (TREE_TYPE (op0
), 0);
2298 code
= (code
== GT_EXPR
|| code
== GE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2302 if ((ret
= vrp_evaluate_conditional_warnv_with_ops_using_ranges
2303 (code
, op0
, op1
, strict_overflow_p
)))
2306 *only_ranges
= false;
2307 /* Do not use compare_names during propagation, it's quadratic. */
2308 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
2310 return compare_names (code
, op0
, op1
, strict_overflow_p
);
2311 else if (TREE_CODE (op0
) == SSA_NAME
)
2312 return compare_name_with_value (code
, op0
, op1
,
2313 strict_overflow_p
, use_equiv_p
);
2314 else if (TREE_CODE (op1
) == SSA_NAME
)
2315 return compare_name_with_value (swap_tree_comparison (code
), op1
, op0
,
2316 strict_overflow_p
, use_equiv_p
);
2320 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2321 information. Return NULL if the conditional can not be evaluated.
2322 The ranges of all the names equivalent with the operands in COND
2323 will be used when trying to compute the value. If the result is
2324 based on undefined signed overflow, issue a warning if
2328 vr_values::vrp_evaluate_conditional (tree_code code
, tree op0
,
2329 tree op1
, gimple
*stmt
)
2335 /* Some passes and foldings leak constants with overflow flag set
2336 into the IL. Avoid doing wrong things with these and bail out. */
2337 if ((TREE_CODE (op0
) == INTEGER_CST
2338 && TREE_OVERFLOW (op0
))
2339 || (TREE_CODE (op1
) == INTEGER_CST
2340 && TREE_OVERFLOW (op1
)))
2344 ret
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, true, &sop
,
2349 enum warn_strict_overflow_code wc
;
2350 const char* warnmsg
;
2352 if (is_gimple_min_invariant (ret
))
2354 wc
= WARN_STRICT_OVERFLOW_CONDITIONAL
;
2355 warnmsg
= G_("assuming signed overflow does not occur when "
2356 "simplifying conditional to constant");
2360 wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
2361 warnmsg
= G_("assuming signed overflow does not occur when "
2362 "simplifying conditional");
2365 if (issue_strict_overflow_warning (wc
))
2367 location_t location
;
2369 if (!gimple_has_location (stmt
))
2370 location
= input_location
;
2372 location
= gimple_location (stmt
);
2373 warning_at (location
, OPT_Wstrict_overflow
, "%s", warnmsg
);
2377 if (warn_type_limits
2378 && ret
&& only_ranges
2379 && TREE_CODE_CLASS (code
) == tcc_comparison
2380 && TREE_CODE (op0
) == SSA_NAME
)
2382 /* If the comparison is being folded and the operand on the LHS
2383 is being compared against a constant value that is outside of
2384 the natural range of OP0's type, then the predicate will
2385 always fold regardless of the value of OP0. If -Wtype-limits
2386 was specified, emit a warning. */
2387 tree type
= TREE_TYPE (op0
);
2388 value_range
*vr0
= get_value_range (op0
);
2390 if (vr0
->kind () == VR_RANGE
2391 && INTEGRAL_TYPE_P (type
)
2392 && vrp_val_is_min (vr0
->min ())
2393 && vrp_val_is_max (vr0
->max ())
2394 && is_gimple_min_invariant (op1
))
2396 location_t location
;
2398 if (!gimple_has_location (stmt
))
2399 location
= input_location
;
2401 location
= gimple_location (stmt
);
2403 warning_at (location
, OPT_Wtype_limits
,
2405 ? G_("comparison always false "
2406 "due to limited range of data type")
2407 : G_("comparison always true "
2408 "due to limited range of data type"));
2416 /* Visit conditional statement STMT. If we can determine which edge
2417 will be taken out of STMT's basic block, record it in
2418 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2421 vr_values::vrp_visit_cond_stmt (gcond
*stmt
, edge
*taken_edge_p
)
2425 *taken_edge_p
= NULL
;
2427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2432 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
2433 print_gimple_stmt (dump_file
, stmt
, 0);
2434 fprintf (dump_file
, "\nWith known ranges\n");
2436 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
2438 fprintf (dump_file
, "\t");
2439 print_generic_expr (dump_file
, use
);
2440 fprintf (dump_file
, ": ");
2441 dump_value_range (dump_file
, vr_value
[SSA_NAME_VERSION (use
)]);
2444 fprintf (dump_file
, "\n");
2447 /* Compute the value of the predicate COND by checking the known
2448 ranges of each of its operands.
2450 Note that we cannot evaluate all the equivalent ranges here
2451 because those ranges may not yet be final and with the current
2452 propagation strategy, we cannot determine when the value ranges
2453 of the names in the equivalence set have changed.
2455 For instance, given the following code fragment
2459 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2463 Assume that on the first visit to i_14, i_5 has the temporary
2464 range [8, 8] because the second argument to the PHI function is
2465 not yet executable. We derive the range ~[0, 0] for i_14 and the
2466 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2467 the first time, since i_14 is equivalent to the range [8, 8], we
2468 determine that the predicate is always false.
2470 On the next round of propagation, i_13 is determined to be
2471 VARYING, which causes i_5 to drop down to VARYING. So, another
2472 visit to i_14 is scheduled. In this second visit, we compute the
2473 exact same range and equivalence set for i_14, namely ~[0, 0] and
2474 { i_5 }. But we did not have the previous range for i_5
2475 registered, so vrp_visit_assignment thinks that the range for
2476 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2477 is not visited again, which stops propagation from visiting
2478 statements in the THEN clause of that if().
2480 To properly fix this we would need to keep the previous range
2481 value for the names in the equivalence set. This way we would've
2482 discovered that from one visit to the other i_5 changed from
2483 range [8, 8] to VR_VARYING.
2485 However, fixing this apparent limitation may not be worth the
2486 additional checking. Testing on several code bases (GCC, DLV,
2487 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2488 4 more predicates folded in SPEC. */
2491 val
= vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt
),
2492 gimple_cond_lhs (stmt
),
2493 gimple_cond_rhs (stmt
),
2496 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
2498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2500 fprintf (dump_file
, "\nPredicate evaluates to: ");
2501 if (val
== NULL_TREE
)
2502 fprintf (dump_file
, "DON'T KNOW\n");
2504 print_generic_stmt (dump_file
, val
);
2508 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2509 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2510 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2511 Returns true if the default label is not needed. */
2514 find_case_label_ranges (gswitch
*stmt
, value_range
*vr
, size_t *min_idx1
,
2515 size_t *max_idx1
, size_t *min_idx2
,
2519 unsigned int n
= gimple_switch_num_labels (stmt
);
2521 tree case_low
, case_high
;
2522 tree min
= vr
->min (), max
= vr
->max ();
2524 gcc_checking_assert (!vr
->varying_p () && !vr
->undefined_p ());
2526 take_default
= !find_case_label_range (stmt
, min
, max
, &i
, &j
);
2528 /* Set second range to emtpy. */
2532 if (vr
->kind () == VR_RANGE
)
2536 return !take_default
;
2539 /* Set first range to all case labels. */
2546 /* Make sure all the values of case labels [i , j] are contained in
2547 range [MIN, MAX]. */
2548 case_low
= CASE_LOW (gimple_switch_label (stmt
, i
));
2549 case_high
= CASE_HIGH (gimple_switch_label (stmt
, j
));
2550 if (tree_int_cst_compare (case_low
, min
) < 0)
2552 if (case_high
!= NULL_TREE
2553 && tree_int_cst_compare (max
, case_high
) < 0)
2559 /* If the range spans case labels [i, j], the corresponding anti-range spans
2560 the labels [1, i - 1] and [j + 1, n - 1]. */
2586 /* Visit switch statement STMT. If we can determine which edge
2587 will be taken out of STMT's basic block, record it in
2588 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2591 vr_values::vrp_visit_switch_stmt (gswitch
*stmt
, edge
*taken_edge_p
)
2595 size_t i
= 0, j
= 0, k
, l
;
2598 *taken_edge_p
= NULL
;
2599 op
= gimple_switch_index (stmt
);
2600 if (TREE_CODE (op
) != SSA_NAME
)
2603 vr
= get_value_range (op
);
2604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2606 fprintf (dump_file
, "\nVisiting switch expression with operand ");
2607 print_generic_expr (dump_file
, op
);
2608 fprintf (dump_file
, " with known range ");
2609 dump_value_range (dump_file
, vr
);
2610 fprintf (dump_file
, "\n");
2613 if (vr
->undefined_p ()
2615 || vr
->symbolic_p ())
2618 /* Find the single edge that is taken from the switch expression. */
2619 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
2621 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2625 gcc_assert (take_default
);
2626 val
= gimple_switch_default_label (stmt
);
2630 /* Check if labels with index i to j and maybe the default label
2631 are all reaching the same label. */
2633 val
= gimple_switch_label (stmt
, i
);
2635 && CASE_LABEL (gimple_switch_default_label (stmt
))
2636 != CASE_LABEL (val
))
2638 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2639 fprintf (dump_file
, " not a single destination for this "
2643 for (++i
; i
<= j
; ++i
)
2645 if (CASE_LABEL (gimple_switch_label (stmt
, i
)) != CASE_LABEL (val
))
2647 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2648 fprintf (dump_file
, " not a single destination for this "
2655 if (CASE_LABEL (gimple_switch_label (stmt
, k
)) != CASE_LABEL (val
))
2657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2658 fprintf (dump_file
, " not a single destination for this "
2665 *taken_edge_p
= find_edge (gimple_bb (stmt
),
2666 label_to_block (cfun
, CASE_LABEL (val
)));
2668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2670 fprintf (dump_file
, " will take edge to ");
2671 print_generic_stmt (dump_file
, CASE_LABEL (val
));
2676 /* Evaluate statement STMT. If the statement produces a useful range,
2677 set VR and corepsponding OUTPUT_P.
2679 If STMT is a conditional branch and we can determine its truth
2680 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2683 vr_values::extract_range_from_stmt (gimple
*stmt
, edge
*taken_edge_p
,
2684 tree
*output_p
, value_range
*vr
)
2687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2689 fprintf (dump_file
, "\nVisiting statement:\n");
2690 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
2693 if (!stmt_interesting_for_vrp (stmt
))
2694 gcc_assert (stmt_ends_bb_p (stmt
));
2695 else if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
2696 vrp_visit_assignment_or_call (stmt
, output_p
, vr
);
2697 else if (gimple_code (stmt
) == GIMPLE_COND
)
2698 vrp_visit_cond_stmt (as_a
<gcond
*> (stmt
), taken_edge_p
);
2699 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2700 vrp_visit_switch_stmt (as_a
<gswitch
*> (stmt
), taken_edge_p
);
2703 /* Visit all arguments for PHI node PHI that flow through executable
2704 edges. If a valid value range can be derived from all the incoming
2705 value ranges, set a new range in VR_RESULT. */
2708 vr_values::extract_range_from_phi_node (gphi
*phi
, value_range
*vr_result
)
2711 tree lhs
= PHI_RESULT (phi
);
2712 value_range
*lhs_vr
= get_value_range (lhs
);
2714 int edges
, old_edges
;
2717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2719 fprintf (dump_file
, "\nVisiting PHI node: ");
2720 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
2723 bool may_simulate_backedge_again
= false;
2725 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2727 edge e
= gimple_phi_arg_edge (phi
, i
);
2729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2732 " Argument #%d (%d -> %d %sexecutable)\n",
2733 (int) i
, e
->src
->index
, e
->dest
->index
,
2734 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
2737 if (e
->flags
& EDGE_EXECUTABLE
)
2739 tree arg
= PHI_ARG_DEF (phi
, i
);
2744 if (TREE_CODE (arg
) == SSA_NAME
)
2746 /* See if we are eventually going to change one of the args. */
2747 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
2748 if (! gimple_nop_p (def_stmt
)
2749 && prop_simulate_again_p (def_stmt
)
2750 && e
->flags
& EDGE_DFS_BACK
)
2751 may_simulate_backedge_again
= true;
2753 vr_arg
= *(get_value_range (arg
));
2754 /* Do not allow equivalences or symbolic ranges to leak in from
2755 backedges. That creates invalid equivalencies.
2756 See PR53465 and PR54767. */
2757 if (e
->flags
& EDGE_DFS_BACK
)
2759 if (!vr_arg
.varying_p () && !vr_arg
.undefined_p ())
2761 vr_arg
.equiv_clear ();
2762 if (vr_arg
.symbolic_p ())
2763 vr_arg
.set_varying ();
2766 /* If the non-backedge arguments range is VR_VARYING then
2767 we can still try recording a simple equivalence. */
2768 else if (vr_arg
.varying_p ())
2769 vr_arg
= value_range (VR_RANGE
, arg
, arg
, NULL
);
2773 if (TREE_OVERFLOW_P (arg
))
2774 arg
= drop_tree_overflow (arg
);
2776 vr_arg
= value_range (VR_RANGE
, arg
, arg
);
2779 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2781 fprintf (dump_file
, "\t");
2782 print_generic_expr (dump_file
, arg
, dump_flags
);
2783 fprintf (dump_file
, ": ");
2784 dump_value_range (dump_file
, &vr_arg
);
2785 fprintf (dump_file
, "\n");
2789 vr_result
->deep_copy (&vr_arg
);
2791 vr_result
->union_ (&vr_arg
);
2794 if (vr_result
->varying_p ())
2799 if (vr_result
->varying_p ())
2801 else if (vr_result
->undefined_p ())
2804 old_edges
= vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)];
2805 vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)] = edges
;
2807 /* To prevent infinite iterations in the algorithm, derive ranges
2808 when the new value is slightly bigger or smaller than the
2809 previous one. We don't do this if we have seen a new executable
2810 edge; this helps us avoid an infinity for conditionals
2811 which are not in a loop. If the old value-range was VR_UNDEFINED
2812 use the updated range and iterate one more time. If we will not
2813 simulate this PHI again via the backedge allow us to iterate. */
2815 && gimple_phi_num_args (phi
) > 1
2816 && edges
== old_edges
2817 && !lhs_vr
->undefined_p ()
2818 && may_simulate_backedge_again
)
2820 /* Compare old and new ranges, fall back to varying if the
2821 values are not comparable. */
2822 int cmp_min
= compare_values (lhs_vr
->min (), vr_result
->min ());
2825 int cmp_max
= compare_values (lhs_vr
->max (), vr_result
->max ());
2829 /* For non VR_RANGE or for pointers fall back to varying if
2830 the range changed. */
2831 if ((lhs_vr
->kind () != VR_RANGE
|| vr_result
->kind () != VR_RANGE
2832 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2833 && (cmp_min
!= 0 || cmp_max
!= 0))
2836 /* If the new minimum is larger than the previous one
2837 retain the old value. If the new minimum value is smaller
2838 than the previous one and not -INF go all the way to -INF + 1.
2839 In the first case, to avoid infinite bouncing between different
2840 minimums, and in the other case to avoid iterating millions of
2841 times to reach -INF. Going to -INF + 1 also lets the following
2842 iteration compute whether there will be any overflow, at the
2843 expense of one additional iteration. */
2844 tree new_min
= vr_result
->min ();
2845 tree new_max
= vr_result
->max ();
2847 new_min
= lhs_vr
->min ();
2848 else if (cmp_min
> 0
2849 && !vrp_val_is_min (vr_result
->min ()))
2850 new_min
= int_const_binop (PLUS_EXPR
,
2851 vrp_val_min (vr_result
->type ()),
2852 build_int_cst (vr_result
->type (), 1));
2854 /* Similarly for the maximum value. */
2856 new_max
= lhs_vr
->max ();
2857 else if (cmp_max
< 0
2858 && !vrp_val_is_max (vr_result
->max ()))
2859 new_max
= int_const_binop (MINUS_EXPR
,
2860 vrp_val_max (vr_result
->type ()),
2861 build_int_cst (vr_result
->type (), 1));
2863 *vr_result
= value_range (vr_result
->kind (), new_min
, new_max
,
2864 vr_result
->equiv ());
2866 /* If we dropped either bound to +-INF then if this is a loop
2867 PHI node SCEV may known more about its value-range. */
2868 if (cmp_min
> 0 || cmp_min
< 0
2869 || cmp_max
< 0 || cmp_max
> 0)
2872 goto infinite_check
;
2878 vr_result
->set_varying ();
2881 /* If this is a loop PHI node SCEV may known more about its value-range.
2882 scev_check can be reached from two paths, one is a fall through from above
2883 "varying" label, the other is direct goto from code block which tries to
2884 avoid infinite simulation. */
2885 if (scev_initialized_p ()
2886 && (l
= loop_containing_stmt (phi
))
2887 && l
->header
== gimple_bb (phi
))
2888 adjust_range_with_scev (vr_result
, l
, phi
, lhs
);
2891 /* If we will end up with a (-INF, +INF) range, set it to
2892 VARYING. Same if the previous max value was invalid for
2893 the type and we end up with vr_result.min > vr_result.max. */
2894 if ((!vr_result
->varying_p () && !vr_result
->undefined_p ())
2895 && !((vrp_val_is_max (vr_result
->max ()) && vrp_val_is_min (vr_result
->min ()))
2896 || compare_values (vr_result
->min (), vr_result
->max ()) > 0))
2899 vr_result
->set_varying ();
2901 /* If the new range is different than the previous value, keep
2907 /* Simplify boolean operations if the source is known
2908 to be already a boolean. */
2910 vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator
*gsi
,
2913 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2915 bool need_conversion
;
2917 /* We handle only !=/== case here. */
2918 gcc_assert (rhs_code
== EQ_EXPR
|| rhs_code
== NE_EXPR
);
2920 op0
= gimple_assign_rhs1 (stmt
);
2921 if (!op_with_boolean_value_range_p (op0
))
2924 op1
= gimple_assign_rhs2 (stmt
);
2925 if (!op_with_boolean_value_range_p (op1
))
2928 /* Reduce number of cases to handle to NE_EXPR. As there is no
2929 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
2930 if (rhs_code
== EQ_EXPR
)
2932 if (TREE_CODE (op1
) == INTEGER_CST
)
2933 op1
= int_const_binop (BIT_XOR_EXPR
, op1
,
2934 build_int_cst (TREE_TYPE (op1
), 1));
2939 lhs
= gimple_assign_lhs (stmt
);
2941 = !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
));
2943 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
2945 && !TYPE_UNSIGNED (TREE_TYPE (op0
))
2946 && TYPE_PRECISION (TREE_TYPE (op0
)) == 1
2947 && TYPE_PRECISION (TREE_TYPE (lhs
)) > 1)
2950 /* For A != 0 we can substitute A itself. */
2951 if (integer_zerop (op1
))
2952 gimple_assign_set_rhs_with_ops (gsi
,
2954 ? NOP_EXPR
: TREE_CODE (op0
), op0
);
2955 /* For A != B we substitute A ^ B. Either with conversion. */
2956 else if (need_conversion
)
2958 tree tem
= make_ssa_name (TREE_TYPE (op0
));
2960 = gimple_build_assign (tem
, BIT_XOR_EXPR
, op0
, op1
);
2961 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
2962 if (INTEGRAL_TYPE_P (TREE_TYPE (tem
))
2963 && TYPE_PRECISION (TREE_TYPE (tem
)) > 1)
2964 set_range_info (tem
, VR_RANGE
,
2965 wi::zero (TYPE_PRECISION (TREE_TYPE (tem
))),
2966 wi::one (TYPE_PRECISION (TREE_TYPE (tem
))));
2967 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, tem
);
2971 gimple_assign_set_rhs_with_ops (gsi
, BIT_XOR_EXPR
, op0
, op1
);
2972 update_stmt (gsi_stmt (*gsi
));
2973 fold_stmt (gsi
, follow_single_use_edges
);
2978 /* Simplify a division or modulo operator to a right shift or bitwise and
2979 if the first operand is unsigned or is greater than zero and the second
2980 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
2981 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
2982 optimize it into just op0 if op0's range is known to be a subset of
2983 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
2987 vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator
*gsi
,
2990 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2992 tree op0
= gimple_assign_rhs1 (stmt
);
2993 tree op1
= gimple_assign_rhs2 (stmt
);
2994 tree op0min
= NULL_TREE
, op0max
= NULL_TREE
;
2996 value_range
*vr
= NULL
;
2998 if (TREE_CODE (op0
) == INTEGER_CST
)
3005 vr
= get_value_range (op0
);
3006 if (range_int_cst_p (vr
))
3008 op0min
= vr
->min ();
3009 op0max
= vr
->max ();
3013 if (rhs_code
== TRUNC_MOD_EXPR
3014 && TREE_CODE (op1
) == SSA_NAME
)
3016 value_range
*vr1
= get_value_range (op1
);
3017 if (range_int_cst_p (vr1
))
3018 op1min
= vr1
->min ();
3020 if (rhs_code
== TRUNC_MOD_EXPR
3021 && TREE_CODE (op1min
) == INTEGER_CST
3022 && tree_int_cst_sgn (op1min
) == 1
3024 && tree_int_cst_lt (op0max
, op1min
))
3026 if (TYPE_UNSIGNED (TREE_TYPE (op0
))
3027 || tree_int_cst_sgn (op0min
) >= 0
3028 || tree_int_cst_lt (fold_unary (NEGATE_EXPR
, TREE_TYPE (op1min
), op1min
),
3031 /* If op0 already has the range op0 % op1 has,
3032 then TRUNC_MOD_EXPR won't change anything. */
3033 gimple_assign_set_rhs_from_tree (gsi
, op0
);
3038 if (TREE_CODE (op0
) != SSA_NAME
)
3041 if (!integer_pow2p (op1
))
3043 /* X % -Y can be only optimized into X % Y either if
3044 X is not INT_MIN, or Y is not -1. Fold it now, as after
3045 remove_range_assertions the range info might be not available
3047 if (rhs_code
== TRUNC_MOD_EXPR
3048 && fold_stmt (gsi
, follow_single_use_edges
))
3053 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
3054 val
= integer_one_node
;
3059 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
3063 && integer_onep (val
)
3064 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3066 location_t location
;
3068 if (!gimple_has_location (stmt
))
3069 location
= input_location
;
3071 location
= gimple_location (stmt
);
3072 warning_at (location
, OPT_Wstrict_overflow
,
3073 "assuming signed overflow does not occur when "
3074 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3078 if (val
&& integer_onep (val
))
3082 if (rhs_code
== TRUNC_DIV_EXPR
)
3084 t
= build_int_cst (integer_type_node
, tree_log2 (op1
));
3085 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
3086 gimple_assign_set_rhs1 (stmt
, op0
);
3087 gimple_assign_set_rhs2 (stmt
, t
);
3091 t
= build_int_cst (TREE_TYPE (op1
), 1);
3092 t
= int_const_binop (MINUS_EXPR
, op1
, t
);
3093 t
= fold_convert (TREE_TYPE (op0
), t
);
3095 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
3096 gimple_assign_set_rhs1 (stmt
, op0
);
3097 gimple_assign_set_rhs2 (stmt
, t
);
3101 fold_stmt (gsi
, follow_single_use_edges
);
3108 /* Simplify a min or max if the ranges of the two operands are
3109 disjoint. Return true if we do simplify. */
3112 vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator
*gsi
,
3115 tree op0
= gimple_assign_rhs1 (stmt
);
3116 tree op1
= gimple_assign_rhs2 (stmt
);
3120 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3121 (LE_EXPR
, op0
, op1
, &sop
));
3125 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3126 (LT_EXPR
, op0
, op1
, &sop
));
3131 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3133 location_t location
;
3135 if (!gimple_has_location (stmt
))
3136 location
= input_location
;
3138 location
= gimple_location (stmt
);
3139 warning_at (location
, OPT_Wstrict_overflow
,
3140 "assuming signed overflow does not occur when "
3141 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3144 /* VAL == TRUE -> OP0 < or <= op1
3145 VAL == FALSE -> OP0 > or >= op1. */
3146 tree res
= ((gimple_assign_rhs_code (stmt
) == MAX_EXPR
)
3147 == integer_zerop (val
)) ? op0
: op1
;
3148 gimple_assign_set_rhs_from_tree (gsi
, res
);
3155 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3156 ABS_EXPR. If the operand is <= 0, then simplify the
3157 ABS_EXPR into a NEGATE_EXPR. */
3160 vr_values::simplify_abs_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3162 tree op
= gimple_assign_rhs1 (stmt
);
3163 value_range
*vr
= get_value_range (op
);
3170 val
= compare_range_with_value (LE_EXPR
, vr
, integer_zero_node
, &sop
);
3173 /* The range is neither <= 0 nor > 0. Now see if it is
3174 either < 0 or >= 0. */
3176 val
= compare_range_with_value (LT_EXPR
, vr
, integer_zero_node
,
3182 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3184 location_t location
;
3186 if (!gimple_has_location (stmt
))
3187 location
= input_location
;
3189 location
= gimple_location (stmt
);
3190 warning_at (location
, OPT_Wstrict_overflow
,
3191 "assuming signed overflow does not occur when "
3192 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3195 gimple_assign_set_rhs1 (stmt
, op
);
3196 if (integer_zerop (val
))
3197 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
3199 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
3201 fold_stmt (gsi
, follow_single_use_edges
);
3209 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3210 If all the bits that are being cleared by & are already
3211 known to be zero from VR, or all the bits that are being
3212 set by | are already known to be one from VR, the bit
3213 operation is redundant. */
3216 vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator
*gsi
,
3219 tree op0
= gimple_assign_rhs1 (stmt
);
3220 tree op1
= gimple_assign_rhs2 (stmt
);
3221 tree op
= NULL_TREE
;
3222 value_range vr0
, vr1
;
3223 wide_int may_be_nonzero0
, may_be_nonzero1
;
3224 wide_int must_be_nonzero0
, must_be_nonzero1
;
3227 if (TREE_CODE (op0
) == SSA_NAME
)
3228 vr0
= *(get_value_range (op0
));
3229 else if (is_gimple_min_invariant (op0
))
3230 set_value_range_to_value (&vr0
, op0
, NULL
);
3234 if (TREE_CODE (op1
) == SSA_NAME
)
3235 vr1
= *(get_value_range (op1
));
3236 else if (is_gimple_min_invariant (op1
))
3237 set_value_range_to_value (&vr1
, op1
, NULL
);
3241 if (!vrp_set_zero_nonzero_bits (TREE_TYPE (op0
), &vr0
, &may_be_nonzero0
,
3244 if (!vrp_set_zero_nonzero_bits (TREE_TYPE (op1
), &vr1
, &may_be_nonzero1
,
3248 switch (gimple_assign_rhs_code (stmt
))
3251 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3257 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3265 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3271 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3282 if (op
== NULL_TREE
)
3285 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (op
), op
);
3286 update_stmt (gsi_stmt (*gsi
));
3290 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3291 a known value range VR.
3293 If there is one and only one value which will satisfy the
3294 conditional, then return that value. Else return NULL.
3296 If signed overflow must be undefined for the value to satisfy
3297 the conditional, then set *STRICT_OVERFLOW_P to true. */
3300 test_for_singularity (enum tree_code cond_code
, tree op0
,
3301 tree op1
, value_range
*vr
)
3306 /* Extract minimum/maximum values which satisfy the conditional as it was
3308 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
3310 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
3313 if (cond_code
== LT_EXPR
)
3315 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3316 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
3317 /* Signal to compare_values_warnv this expr doesn't overflow. */
3319 TREE_NO_WARNING (max
) = 1;
3322 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
3324 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
3327 if (cond_code
== GT_EXPR
)
3329 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3330 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
3331 /* Signal to compare_values_warnv this expr doesn't overflow. */
3333 TREE_NO_WARNING (min
) = 1;
3337 /* Now refine the minimum and maximum values using any
3338 value range information we have for op0. */
3341 if (compare_values (vr
->min (), min
) == 1)
3343 if (compare_values (vr
->max (), max
) == -1)
3346 /* If the new min/max values have converged to a single value,
3347 then there is only one value which can satisfy the condition,
3348 return that value. */
3349 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
3355 /* Return whether the value range *VR fits in an integer type specified
3356 by PRECISION and UNSIGNED_P. */
3359 range_fits_type_p (value_range
*vr
, unsigned dest_precision
, signop dest_sgn
)
3362 unsigned src_precision
;
3366 /* We can only handle integral and pointer types. */
3367 src_type
= vr
->type ();
3368 if (!INTEGRAL_TYPE_P (src_type
)
3369 && !POINTER_TYPE_P (src_type
))
3372 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3373 and so is an identity transform. */
3374 src_precision
= TYPE_PRECISION (vr
->type ());
3375 src_sgn
= TYPE_SIGN (src_type
);
3376 if ((src_precision
< dest_precision
3377 && !(dest_sgn
== UNSIGNED
&& src_sgn
== SIGNED
))
3378 || (src_precision
== dest_precision
&& src_sgn
== dest_sgn
))
3381 /* Now we can only handle ranges with constant bounds. */
3382 if (!range_int_cst_p (vr
))
3385 /* For sign changes, the MSB of the wide_int has to be clear.
3386 An unsigned value with its MSB set cannot be represented by
3387 a signed wide_int, while a negative value cannot be represented
3388 by an unsigned wide_int. */
3389 if (src_sgn
!= dest_sgn
3390 && (wi::lts_p (wi::to_wide (vr
->min ()), 0)
3391 || wi::lts_p (wi::to_wide (vr
->max ()), 0)))
3394 /* Then we can perform the conversion on both ends and compare
3395 the result for equality. */
3396 tem
= wi::ext (wi::to_widest (vr
->min ()), dest_precision
, dest_sgn
);
3397 if (tem
!= wi::to_widest (vr
->min ()))
3399 tem
= wi::ext (wi::to_widest (vr
->max ()), dest_precision
, dest_sgn
);
3400 if (tem
!= wi::to_widest (vr
->max ()))
3406 /* Simplify a conditional using a relational operator to an equality
3407 test if the range information indicates only one value can satisfy
3408 the original conditional. */
3411 vr_values::simplify_cond_using_ranges_1 (gcond
*stmt
)
3413 tree op0
= gimple_cond_lhs (stmt
);
3414 tree op1
= gimple_cond_rhs (stmt
);
3415 enum tree_code cond_code
= gimple_cond_code (stmt
);
3417 if (cond_code
!= NE_EXPR
3418 && cond_code
!= EQ_EXPR
3419 && TREE_CODE (op0
) == SSA_NAME
3420 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3421 && is_gimple_min_invariant (op1
))
3423 value_range
*vr
= get_value_range (op0
);
3425 /* If we have range information for OP0, then we might be
3426 able to simplify this conditional. */
3427 if (vr
->kind () == VR_RANGE
)
3429 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
3434 fprintf (dump_file
, "Simplified relational ");
3435 print_gimple_stmt (dump_file
, stmt
, 0);
3436 fprintf (dump_file
, " into ");
3439 gimple_cond_set_code (stmt
, EQ_EXPR
);
3440 gimple_cond_set_lhs (stmt
, op0
);
3441 gimple_cond_set_rhs (stmt
, new_tree
);
3447 print_gimple_stmt (dump_file
, stmt
, 0);
3448 fprintf (dump_file
, "\n");
3454 /* Try again after inverting the condition. We only deal
3455 with integral types here, so no need to worry about
3456 issues with inverting FP comparisons. */
3457 new_tree
= test_for_singularity
3458 (invert_tree_comparison (cond_code
, false),
3464 fprintf (dump_file
, "Simplified relational ");
3465 print_gimple_stmt (dump_file
, stmt
, 0);
3466 fprintf (dump_file
, " into ");
3469 gimple_cond_set_code (stmt
, NE_EXPR
);
3470 gimple_cond_set_lhs (stmt
, op0
);
3471 gimple_cond_set_rhs (stmt
, new_tree
);
3477 print_gimple_stmt (dump_file
, stmt
, 0);
3478 fprintf (dump_file
, "\n");
3488 /* STMT is a conditional at the end of a basic block.
3490 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3491 was set via a type conversion, try to replace the SSA_NAME with the RHS
3492 of the type conversion. Doing so makes the conversion dead which helps
3493 subsequent passes. */
3496 vr_values::simplify_cond_using_ranges_2 (gcond
*stmt
)
3498 tree op0
= gimple_cond_lhs (stmt
);
3499 tree op1
= gimple_cond_rhs (stmt
);
3501 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3502 see if OP0 was set by a type conversion where the source of
3503 the conversion is another SSA_NAME with a range that fits
3504 into the range of OP0's type.
3506 If so, the conversion is redundant as the earlier SSA_NAME can be
3507 used for the comparison directly if we just massage the constant in the
3509 if (TREE_CODE (op0
) == SSA_NAME
3510 && TREE_CODE (op1
) == INTEGER_CST
)
3512 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op0
);
3515 if (!is_gimple_assign (def_stmt
)
3516 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3519 innerop
= gimple_assign_rhs1 (def_stmt
);
3521 if (TREE_CODE (innerop
) == SSA_NAME
3522 && !POINTER_TYPE_P (TREE_TYPE (innerop
))
3523 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
)
3524 && desired_pro_or_demotion_p (TREE_TYPE (innerop
), TREE_TYPE (op0
)))
3526 value_range
*vr
= get_value_range (innerop
);
3528 if (range_int_cst_p (vr
)
3529 && range_fits_type_p (vr
,
3530 TYPE_PRECISION (TREE_TYPE (op0
)),
3531 TYPE_SIGN (TREE_TYPE (op0
)))
3532 && int_fits_type_p (op1
, TREE_TYPE (innerop
)))
3534 tree newconst
= fold_convert (TREE_TYPE (innerop
), op1
);
3535 gimple_cond_set_lhs (stmt
, innerop
);
3536 gimple_cond_set_rhs (stmt
, newconst
);
3538 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3540 fprintf (dump_file
, "Folded into: ");
3541 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3542 fprintf (dump_file
, "\n");
3549 /* Simplify a switch statement using the value range of the switch
3553 vr_values::simplify_switch_using_ranges (gswitch
*stmt
)
3555 tree op
= gimple_switch_index (stmt
);
3556 value_range
*vr
= NULL
;
3560 size_t i
= 0, j
= 0, n
, n2
;
3563 size_t k
= 1, l
= 0;
3565 if (TREE_CODE (op
) == SSA_NAME
)
3567 vr
= get_value_range (op
);
3569 /* We can only handle integer ranges. */
3570 if (vr
->varying_p ()
3571 || vr
->undefined_p ()
3572 || vr
->symbolic_p ())
3575 /* Find case label for min/max of the value range. */
3576 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
3578 else if (TREE_CODE (op
) == INTEGER_CST
)
3580 take_default
= !find_case_label_index (stmt
, 1, op
, &i
);
3594 n
= gimple_switch_num_labels (stmt
);
3596 /* We can truncate the case label ranges that partially overlap with OP's
3598 size_t min_idx
= 1, max_idx
= 0;
3600 find_case_label_range (stmt
, vr
->min (), vr
->max (), &min_idx
, &max_idx
);
3601 if (min_idx
<= max_idx
)
3603 tree min_label
= gimple_switch_label (stmt
, min_idx
);
3604 tree max_label
= gimple_switch_label (stmt
, max_idx
);
3606 /* Avoid changing the type of the case labels when truncating. */
3607 tree case_label_type
= TREE_TYPE (CASE_LOW (min_label
));
3608 tree vr_min
= fold_convert (case_label_type
, vr
->min ());
3609 tree vr_max
= fold_convert (case_label_type
, vr
->max ());
3611 if (vr
->kind () == VR_RANGE
)
3613 /* If OP's value range is [2,8] and the low label range is
3614 0 ... 3, truncate the label's range to 2 .. 3. */
3615 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3616 && CASE_HIGH (min_label
) != NULL_TREE
3617 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3618 CASE_LOW (min_label
) = vr_min
;
3620 /* If OP's value range is [2,8] and the high label range is
3621 7 ... 10, truncate the label's range to 7 .. 8. */
3622 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3623 && CASE_HIGH (max_label
) != NULL_TREE
3624 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3625 CASE_HIGH (max_label
) = vr_max
;
3627 else if (vr
->kind () == VR_ANTI_RANGE
)
3629 tree one_cst
= build_one_cst (case_label_type
);
3631 if (min_label
== max_label
)
3633 /* If OP's value range is ~[7,8] and the label's range is
3634 7 ... 10, truncate the label's range to 9 ... 10. */
3635 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) == 0
3636 && CASE_HIGH (min_label
) != NULL_TREE
3637 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) > 0)
3638 CASE_LOW (min_label
)
3639 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3641 /* If OP's value range is ~[7,8] and the label's range is
3642 5 ... 8, truncate the label's range to 5 ... 6. */
3643 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3644 && CASE_HIGH (min_label
) != NULL_TREE
3645 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) == 0)
3646 CASE_HIGH (min_label
)
3647 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3651 /* If OP's value range is ~[2,8] and the low label range is
3652 0 ... 3, truncate the label's range to 0 ... 1. */
3653 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3654 && CASE_HIGH (min_label
) != NULL_TREE
3655 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3656 CASE_HIGH (min_label
)
3657 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3659 /* If OP's value range is ~[2,8] and the high label range is
3660 7 ... 10, truncate the label's range to 9 ... 10. */
3661 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3662 && CASE_HIGH (max_label
) != NULL_TREE
3663 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3664 CASE_LOW (max_label
)
3665 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3669 /* Canonicalize singleton case ranges. */
3670 if (tree_int_cst_equal (CASE_LOW (min_label
), CASE_HIGH (min_label
)))
3671 CASE_HIGH (min_label
) = NULL_TREE
;
3672 if (tree_int_cst_equal (CASE_LOW (max_label
), CASE_HIGH (max_label
)))
3673 CASE_HIGH (max_label
) = NULL_TREE
;
3676 /* We can also eliminate case labels that lie completely outside OP's value
3679 /* Bail out if this is just all edges taken. */
3685 /* Build a new vector of taken case labels. */
3686 vec2
= make_tree_vec (j
- i
+ 1 + l
- k
+ 1 + (int)take_default
);
3689 /* Add the default edge, if necessary. */
3691 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
3693 for (; i
<= j
; ++i
, ++n2
)
3694 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
3696 for (; k
<= l
; ++k
, ++n2
)
3697 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, k
);
3699 /* Mark needed edges. */
3700 for (i
= 0; i
< n2
; ++i
)
3702 e
= find_edge (gimple_bb (stmt
),
3703 label_to_block (cfun
,
3704 CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
3705 e
->aux
= (void *)-1;
3708 /* Queue not needed edges for later removal. */
3709 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
3711 if (e
->aux
== (void *)-1)
3717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3719 fprintf (dump_file
, "removing unreachable case label\n");
3721 to_remove_edges
.safe_push (e
);
3722 e
->flags
&= ~EDGE_EXECUTABLE
;
3723 e
->flags
|= EDGE_IGNORE
;
3726 /* And queue an update for the stmt. */
3729 to_update_switch_stmts
.safe_push (su
);
3734 vr_values::cleanup_edges_and_switches (void)
3740 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
3741 CFG in a broken state and requires a cfg_cleanup run. */
3742 FOR_EACH_VEC_ELT (to_remove_edges
, i
, e
)
3745 /* Update SWITCH_EXPR case label vector. */
3746 FOR_EACH_VEC_ELT (to_update_switch_stmts
, i
, su
)
3749 size_t n
= TREE_VEC_LENGTH (su
->vec
);
3751 gimple_switch_set_num_labels (su
->stmt
, n
);
3752 for (j
= 0; j
< n
; j
++)
3753 gimple_switch_set_label (su
->stmt
, j
, TREE_VEC_ELT (su
->vec
, j
));
3754 /* As we may have replaced the default label with a regular one
3755 make sure to make it a real default label again. This ensures
3756 optimal expansion. */
3757 label
= gimple_switch_label (su
->stmt
, 0);
3758 CASE_LOW (label
) = NULL_TREE
;
3759 CASE_HIGH (label
) = NULL_TREE
;
3762 if (!to_remove_edges
.is_empty ())
3764 free_dominance_info (CDI_DOMINATORS
);
3765 loops_state_set (LOOPS_NEED_FIXUP
);
3768 to_remove_edges
.release ();
3769 to_update_switch_stmts
.release ();
3772 /* Simplify an integral conversion from an SSA name in STMT. */
3775 simplify_conversion_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3777 tree innerop
, middleop
, finaltype
;
3779 signop inner_sgn
, middle_sgn
, final_sgn
;
3780 unsigned inner_prec
, middle_prec
, final_prec
;
3781 widest_int innermin
, innermed
, innermax
, middlemin
, middlemed
, middlemax
;
3783 finaltype
= TREE_TYPE (gimple_assign_lhs (stmt
));
3784 if (!INTEGRAL_TYPE_P (finaltype
))
3786 middleop
= gimple_assign_rhs1 (stmt
);
3787 def_stmt
= SSA_NAME_DEF_STMT (middleop
);
3788 if (!is_gimple_assign (def_stmt
)
3789 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3791 innerop
= gimple_assign_rhs1 (def_stmt
);
3792 if (TREE_CODE (innerop
) != SSA_NAME
3793 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
))
3796 /* Get the value-range of the inner operand. Use get_range_info in
3797 case innerop was created during substitute-and-fold. */
3798 wide_int imin
, imax
;
3799 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
))
3800 || get_range_info (innerop
, &imin
, &imax
) != VR_RANGE
)
3802 innermin
= widest_int::from (imin
, TYPE_SIGN (TREE_TYPE (innerop
)));
3803 innermax
= widest_int::from (imax
, TYPE_SIGN (TREE_TYPE (innerop
)));
3805 /* Simulate the conversion chain to check if the result is equal if
3806 the middle conversion is removed. */
3807 inner_prec
= TYPE_PRECISION (TREE_TYPE (innerop
));
3808 middle_prec
= TYPE_PRECISION (TREE_TYPE (middleop
));
3809 final_prec
= TYPE_PRECISION (finaltype
);
3811 /* If the first conversion is not injective, the second must not
3813 if (wi::gtu_p (innermax
- innermin
,
3814 wi::mask
<widest_int
> (middle_prec
, false))
3815 && middle_prec
< final_prec
)
3817 /* We also want a medium value so that we can track the effect that
3818 narrowing conversions with sign change have. */
3819 inner_sgn
= TYPE_SIGN (TREE_TYPE (innerop
));
3820 if (inner_sgn
== UNSIGNED
)
3821 innermed
= wi::shifted_mask
<widest_int
> (1, inner_prec
- 1, false);
3824 if (wi::cmp (innermin
, innermed
, inner_sgn
) >= 0
3825 || wi::cmp (innermed
, innermax
, inner_sgn
) >= 0)
3826 innermed
= innermin
;
3828 middle_sgn
= TYPE_SIGN (TREE_TYPE (middleop
));
3829 middlemin
= wi::ext (innermin
, middle_prec
, middle_sgn
);
3830 middlemed
= wi::ext (innermed
, middle_prec
, middle_sgn
);
3831 middlemax
= wi::ext (innermax
, middle_prec
, middle_sgn
);
3833 /* Require that the final conversion applied to both the original
3834 and the intermediate range produces the same result. */
3835 final_sgn
= TYPE_SIGN (finaltype
);
3836 if (wi::ext (middlemin
, final_prec
, final_sgn
)
3837 != wi::ext (innermin
, final_prec
, final_sgn
)
3838 || wi::ext (middlemed
, final_prec
, final_sgn
)
3839 != wi::ext (innermed
, final_prec
, final_sgn
)
3840 || wi::ext (middlemax
, final_prec
, final_sgn
)
3841 != wi::ext (innermax
, final_prec
, final_sgn
))
3844 gimple_assign_set_rhs1 (stmt
, innerop
);
3845 fold_stmt (gsi
, follow_single_use_edges
);
3849 /* Simplify a conversion from integral SSA name to float in STMT. */
3852 vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator
*gsi
,
3855 tree rhs1
= gimple_assign_rhs1 (stmt
);
3856 value_range
*vr
= get_value_range (rhs1
);
3857 scalar_float_mode fltmode
3858 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
)));
3859 scalar_int_mode mode
;
3863 /* We can only handle constant ranges. */
3864 if (!range_int_cst_p (vr
))
3867 /* First check if we can use a signed type in place of an unsigned. */
3868 scalar_int_mode rhs_mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1
));
3869 if (TYPE_UNSIGNED (TREE_TYPE (rhs1
))
3870 && can_float_p (fltmode
, rhs_mode
, 0) != CODE_FOR_nothing
3871 && range_fits_type_p (vr
, TYPE_PRECISION (TREE_TYPE (rhs1
)), SIGNED
))
3873 /* If we can do the conversion in the current input mode do nothing. */
3874 else if (can_float_p (fltmode
, rhs_mode
,
3875 TYPE_UNSIGNED (TREE_TYPE (rhs1
))) != CODE_FOR_nothing
)
3877 /* Otherwise search for a mode we can use, starting from the narrowest
3878 integer mode available. */
3881 mode
= NARROWEST_INT_MODE
;
3884 /* If we cannot do a signed conversion to float from mode
3885 or if the value-range does not fit in the signed type
3886 try with a wider mode. */
3887 if (can_float_p (fltmode
, mode
, 0) != CODE_FOR_nothing
3888 && range_fits_type_p (vr
, GET_MODE_PRECISION (mode
), SIGNED
))
3891 /* But do not widen the input. Instead leave that to the
3892 optabs expansion code. */
3893 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
3894 || GET_MODE_PRECISION (mode
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
3899 /* It works, insert a truncation or sign-change before the
3900 float conversion. */
3901 tem
= make_ssa_name (build_nonstandard_integer_type
3902 (GET_MODE_PRECISION (mode
), 0));
3903 conv
= gimple_build_assign (tem
, NOP_EXPR
, rhs1
);
3904 gsi_insert_before (gsi
, conv
, GSI_SAME_STMT
);
3905 gimple_assign_set_rhs1 (stmt
, tem
);
3906 fold_stmt (gsi
, follow_single_use_edges
);
3911 /* Simplify an internal fn call using ranges if possible. */
3914 vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator
*gsi
,
3917 enum tree_code subcode
;
3918 bool is_ubsan
= false;
3920 switch (gimple_call_internal_fn (stmt
))
3922 case IFN_UBSAN_CHECK_ADD
:
3923 subcode
= PLUS_EXPR
;
3926 case IFN_UBSAN_CHECK_SUB
:
3927 subcode
= MINUS_EXPR
;
3930 case IFN_UBSAN_CHECK_MUL
:
3931 subcode
= MULT_EXPR
;
3934 case IFN_ADD_OVERFLOW
:
3935 subcode
= PLUS_EXPR
;
3937 case IFN_SUB_OVERFLOW
:
3938 subcode
= MINUS_EXPR
;
3940 case IFN_MUL_OVERFLOW
:
3941 subcode
= MULT_EXPR
;
3947 tree op0
= gimple_call_arg (stmt
, 0);
3948 tree op1
= gimple_call_arg (stmt
, 1);
3952 type
= TREE_TYPE (op0
);
3953 if (VECTOR_TYPE_P (type
))
3956 else if (gimple_call_lhs (stmt
) == NULL_TREE
)
3959 type
= TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt
)));
3960 if (!check_for_binary_op_overflow (subcode
, type
, op0
, op1
, &ovf
)
3961 || (is_ubsan
&& ovf
))
3965 location_t loc
= gimple_location (stmt
);
3967 g
= gimple_build_assign (gimple_call_lhs (stmt
), subcode
, op0
, op1
);
3970 int prec
= TYPE_PRECISION (type
);
3973 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
3974 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
3975 utype
= build_nonstandard_integer_type (prec
, 1);
3976 if (TREE_CODE (op0
) == INTEGER_CST
)
3977 op0
= fold_convert (utype
, op0
);
3978 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op0
)))
3980 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op0
);
3981 gimple_set_location (g
, loc
);
3982 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
3983 op0
= gimple_assign_lhs (g
);
3985 if (TREE_CODE (op1
) == INTEGER_CST
)
3986 op1
= fold_convert (utype
, op1
);
3987 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op1
)))
3989 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op1
);
3990 gimple_set_location (g
, loc
);
3991 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
3992 op1
= gimple_assign_lhs (g
);
3994 g
= gimple_build_assign (make_ssa_name (utype
), subcode
, op0
, op1
);
3995 gimple_set_location (g
, loc
);
3996 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
3999 g
= gimple_build_assign (make_ssa_name (type
), NOP_EXPR
,
4000 gimple_assign_lhs (g
));
4001 gimple_set_location (g
, loc
);
4002 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4004 g
= gimple_build_assign (gimple_call_lhs (stmt
), COMPLEX_EXPR
,
4005 gimple_assign_lhs (g
),
4006 build_int_cst (type
, ovf
));
4008 gimple_set_location (g
, loc
);
4009 gsi_replace (gsi
, g
, false);
4013 /* Return true if VAR is a two-valued variable. Set a and b with the
4014 two-values when it is true. Return false otherwise. */
4017 vr_values::two_valued_val_range_p (tree var
, tree
*a
, tree
*b
)
4019 value_range
*vr
= get_value_range (var
);
4020 if (vr
->varying_p ()
4021 || vr
->undefined_p ()
4022 || TREE_CODE (vr
->min ()) != INTEGER_CST
4023 || TREE_CODE (vr
->max ()) != INTEGER_CST
)
4026 if (vr
->kind () == VR_RANGE
4027 && wi::to_wide (vr
->max ()) - wi::to_wide (vr
->min ()) == 1)
4034 /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
4035 if (vr
->kind () == VR_ANTI_RANGE
4036 && (wi::to_wide (vr
->min ())
4037 - wi::to_wide (vrp_val_min (TREE_TYPE (var
)))) == 1
4038 && (wi::to_wide (vrp_val_max (TREE_TYPE (var
)))
4039 - wi::to_wide (vr
->max ())) == 1)
4041 *a
= vrp_val_min (TREE_TYPE (var
));
4042 *b
= vrp_val_max (TREE_TYPE (var
));
4049 /* Simplify STMT using ranges if possible. */
4052 vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator
*gsi
)
4054 gimple
*stmt
= gsi_stmt (*gsi
);
4055 if (is_gimple_assign (stmt
))
4057 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
4058 tree rhs1
= gimple_assign_rhs1 (stmt
);
4059 tree rhs2
= gimple_assign_rhs2 (stmt
);
4060 tree lhs
= gimple_assign_lhs (stmt
);
4061 tree val1
= NULL_TREE
, val2
= NULL_TREE
;
4062 use_operand_p use_p
;
4067 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4069 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4073 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4075 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4077 if (TREE_CODE_CLASS (rhs_code
) == tcc_binary
4078 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4079 && ((TREE_CODE (rhs1
) == INTEGER_CST
4080 && TREE_CODE (rhs2
) == SSA_NAME
)
4081 || (TREE_CODE (rhs2
) == INTEGER_CST
4082 && TREE_CODE (rhs1
) == SSA_NAME
))
4083 && single_imm_use (lhs
, &use_p
, &use_stmt
)
4084 && gimple_code (use_stmt
) == GIMPLE_COND
)
4087 tree new_rhs1
= NULL_TREE
;
4088 tree new_rhs2
= NULL_TREE
;
4089 tree cmp_var
= NULL_TREE
;
4091 if (TREE_CODE (rhs2
) == SSA_NAME
4092 && two_valued_val_range_p (rhs2
, &val1
, &val2
))
4094 /* Optimize RHS1 OP [VAL1, VAL2]. */
4095 new_rhs1
= int_const_binop (rhs_code
, rhs1
, val1
);
4096 new_rhs2
= int_const_binop (rhs_code
, rhs1
, val2
);
4099 else if (TREE_CODE (rhs1
) == SSA_NAME
4100 && two_valued_val_range_p (rhs1
, &val1
, &val2
))
4102 /* Optimize [VAL1, VAL2] OP RHS2. */
4103 new_rhs1
= int_const_binop (rhs_code
, val1
, rhs2
);
4104 new_rhs2
= int_const_binop (rhs_code
, val2
, rhs2
);
4108 /* If we could not find two-vals or the optimzation is invalid as
4109 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4110 if (new_rhs1
&& new_rhs2
)
4112 tree cond
= build2 (EQ_EXPR
, boolean_type_node
, cmp_var
, val1
);
4113 gimple_assign_set_rhs_with_ops (gsi
,
4117 update_stmt (gsi_stmt (*gsi
));
4118 fold_stmt (gsi
, follow_single_use_edges
);
4127 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4128 if the RHS is zero or one, and the LHS are known to be boolean
4130 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4131 return simplify_truth_ops_using_ranges (gsi
, stmt
);
4134 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4135 and BIT_AND_EXPR respectively if the first operand is greater
4136 than zero and the second operand is an exact power of two.
4137 Also optimize TRUNC_MOD_EXPR away if the second operand is
4138 constant and the first operand already has the right value
4140 case TRUNC_DIV_EXPR
:
4141 case TRUNC_MOD_EXPR
:
4142 if ((TREE_CODE (rhs1
) == SSA_NAME
4143 || TREE_CODE (rhs1
) == INTEGER_CST
)
4144 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4145 return simplify_div_or_mod_using_ranges (gsi
, stmt
);
4148 /* Transform ABS (X) into X or -X as appropriate. */
4150 if (TREE_CODE (rhs1
) == SSA_NAME
4151 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4152 return simplify_abs_using_ranges (gsi
, stmt
);
4157 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4158 if all the bits being cleared are already cleared or
4159 all the bits being set are already set. */
4160 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4161 return simplify_bit_ops_using_ranges (gsi
, stmt
);
4165 if (TREE_CODE (rhs1
) == SSA_NAME
4166 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4167 return simplify_conversion_using_ranges (gsi
, stmt
);
4171 if (TREE_CODE (rhs1
) == SSA_NAME
4172 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4173 return simplify_float_conversion_using_ranges (gsi
, stmt
);
4178 return simplify_min_or_max_using_ranges (gsi
, stmt
);
4184 else if (gimple_code (stmt
) == GIMPLE_COND
)
4185 return simplify_cond_using_ranges_1 (as_a
<gcond
*> (stmt
));
4186 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
4187 return simplify_switch_using_ranges (as_a
<gswitch
*> (stmt
));
4188 else if (is_gimple_call (stmt
)
4189 && gimple_call_internal_p (stmt
))
4190 return simplify_internal_call_using_ranges (gsi
, stmt
);
4196 vr_values::set_vr_value (tree var
, value_range
*vr
)
4198 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4200 vr_value
[SSA_NAME_VERSION (var
)] = vr
;