1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2020 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"
50 #include "vr-values.h"
53 #include "gimple-range.h"
55 /* Set value range VR to a non-negative range of type TYPE. */
58 set_value_range_to_nonnegative (value_range_equiv
*vr
, tree type
)
60 tree zero
= build_int_cst (type
, 0);
61 vr
->update (zero
, vrp_val_max (type
));
64 /* Set value range VR to a range of a truthvalue of type TYPE. */
67 set_value_range_to_truthvalue (value_range_equiv
*vr
, tree type
)
69 if (TYPE_PRECISION (type
) == 1)
70 vr
->set_varying (type
);
72 vr
->update (build_int_cst (type
, 0), build_int_cst (type
, 1));
75 /* Return the lattice entry for VAR or NULL if it doesn't exist or cannot
79 vr_values::get_lattice_entry (const_tree var
)
81 value_range_equiv
*vr
;
83 unsigned ver
= SSA_NAME_VERSION (var
);
85 /* If we query the entry for a new SSA name avoid reallocating the lattice
86 since we should get here at most from the substitute-and-fold stage which
87 will never try to change values. */
88 if (ver
>= num_vr_values
)
95 /* Create a default value range. */
96 vr
= allocate_value_range_equiv ();
99 /* After propagation finished return varying. */
100 if (values_propagated
)
102 vr
->set_varying (TREE_TYPE (var
));
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
)))
122 vr
->set_nonzero (TREE_TYPE (sym
));
125 else if (INTEGRAL_TYPE_P (TREE_TYPE (sym
)))
127 get_range_info (var
, *vr
);
128 if (vr
->undefined_p ())
129 vr
->set_varying (TREE_TYPE (sym
));
132 vr
->set_varying (TREE_TYPE (sym
));
134 else if (TREE_CODE (sym
) == RESULT_DECL
135 && DECL_BY_REFERENCE (sym
))
137 vr
->set_nonzero (TREE_TYPE (sym
));
145 /* Return value range information for VAR.
147 If we have no values ranges recorded (ie, VRP is not running), then
148 return NULL. Otherwise create an empty range if none existed for VAR. */
150 const value_range_equiv
*
151 vr_values::get_value_range (const_tree var
,
152 gimple
*stmt ATTRIBUTE_UNUSED
)
154 /* If we have no recorded ranges, then return NULL. */
158 value_range_equiv
*vr
= get_lattice_entry (var
);
160 /* Reallocate the lattice if needed. */
163 unsigned int old_sz
= num_vr_values
;
164 num_vr_values
= num_ssa_names
+ num_ssa_names
/ 10;
165 vr_value
= XRESIZEVEC (value_range_equiv
*, vr_value
, num_vr_values
);
166 for ( ; old_sz
< num_vr_values
; old_sz
++)
167 vr_value
[old_sz
] = NULL
;
169 /* Now that the lattice has been resized, we should never fail. */
170 vr
= get_lattice_entry (var
);
178 vr_values::range_of_expr (irange
&r
, tree expr
, gimple
*stmt
)
180 if (!gimple_range_ssa_p (expr
))
181 return get_tree_range (r
, expr
);
183 if (const value_range
*vr
= get_value_range (expr
, stmt
))
185 if (vr
->undefined_p () || vr
->varying_p () || vr
->constant_p ())
189 value_range tmp
= *vr
;
190 tmp
.normalize_symbolics ();
199 vr_values::value_of_expr (tree op
, gimple
*)
201 return op_with_constant_singleton_value_range (op
);
205 vr_values::value_on_edge (edge
, tree op
)
207 return op_with_constant_singleton_value_range (op
);
211 vr_values::value_of_stmt (gimple
*stmt
, tree op
)
214 op
= gimple_get_lhs (stmt
);
216 gcc_checking_assert (!op
|| op
== gimple_get_lhs (stmt
));
219 return op_with_constant_singleton_value_range (op
);
223 /* Set the lattice entry for DEF to VARYING. */
226 vr_values::set_def_to_varying (const_tree def
)
228 value_range_equiv
*vr
= get_lattice_entry (def
);
230 vr
->set_varying (TREE_TYPE (def
));
233 /* Set value-ranges of all SSA names defined by STMT to varying. */
236 vr_values::set_defs_to_varying (gimple
*stmt
)
240 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
241 set_def_to_varying (def
);
244 /* Update the value range and equivalence set for variable VAR to
245 NEW_VR. Return true if NEW_VR is different from VAR's previous
248 NOTE: This function assumes that NEW_VR is a temporary value range
249 object created for the sole purpose of updating VAR's range. The
250 storage used by the equivalence set from NEW_VR will be freed by
251 this function. Do not call update_value_range when NEW_VR
252 is the range object associated with another SSA name. */
255 vr_values::update_value_range (const_tree var
, value_range_equiv
*new_vr
)
257 value_range_equiv
*old_vr
;
260 /* If there is a value-range on the SSA name from earlier analysis
262 if (INTEGRAL_TYPE_P (TREE_TYPE (var
)))
264 value_range_equiv nr
;
265 get_range_info (var
, nr
);
266 if (!nr
.undefined_p ())
267 new_vr
->intersect (&nr
);
270 /* Update the value range, if necessary. If we cannot allocate a lattice
271 entry for VAR keep it at VARYING. This happens when DOM feeds us stmts
272 with SSA names allocated after setting up the lattice. */
273 old_vr
= get_lattice_entry (var
);
276 is_new
= !old_vr
->equal_p (*new_vr
, /*ignore_equivs=*/false);
280 /* Do not allow transitions up the lattice. The following
281 is slightly more awkward than just new_vr->type < old_vr->type
282 because VR_RANGE and VR_ANTI_RANGE need to be considered
283 the same. We may not have is_new when transitioning to
284 UNDEFINED. If old_vr->type is VARYING, we shouldn't be
285 called, if we are anyway, keep it VARYING. */
286 if (old_vr
->varying_p ())
288 new_vr
->set_varying (TREE_TYPE (var
));
291 else if (new_vr
->undefined_p ())
293 old_vr
->set_varying (TREE_TYPE (var
));
294 new_vr
->set_varying (TREE_TYPE (var
));
298 old_vr
->set (new_vr
->min (), new_vr
->max (), new_vr
->equiv (),
302 new_vr
->equiv_clear ();
307 /* Return true if value range VR involves exactly one symbol SYM. */
310 symbolic_range_based_on_p (value_range
*vr
, const_tree sym
)
312 bool neg
, min_has_symbol
, max_has_symbol
;
315 if (is_gimple_min_invariant (vr
->min ()))
316 min_has_symbol
= false;
317 else if (get_single_symbol (vr
->min (), &neg
, &inv
) == sym
)
318 min_has_symbol
= true;
322 if (is_gimple_min_invariant (vr
->max ()))
323 max_has_symbol
= false;
324 else if (get_single_symbol (vr
->max (), &neg
, &inv
) == sym
)
325 max_has_symbol
= true;
329 return (min_has_symbol
|| max_has_symbol
);
332 /* Return true if the result of assignment STMT is know to be non-zero. */
335 gimple_assign_nonzero_p (gimple
*stmt
)
337 enum tree_code code
= gimple_assign_rhs_code (stmt
);
338 bool strict_overflow_p
;
339 switch (get_gimple_rhs_class (code
))
341 case GIMPLE_UNARY_RHS
:
342 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
343 gimple_expr_type (stmt
),
344 gimple_assign_rhs1 (stmt
),
346 case GIMPLE_BINARY_RHS
:
347 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
348 gimple_expr_type (stmt
),
349 gimple_assign_rhs1 (stmt
),
350 gimple_assign_rhs2 (stmt
),
352 case GIMPLE_TERNARY_RHS
:
354 case GIMPLE_SINGLE_RHS
:
355 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt
),
357 case GIMPLE_INVALID_RHS
:
364 /* Return true if STMT is known to compute a non-zero value. */
367 gimple_stmt_nonzero_p (gimple
*stmt
)
369 switch (gimple_code (stmt
))
372 return gimple_assign_nonzero_p (stmt
);
375 gcall
*call_stmt
= as_a
<gcall
*> (stmt
);
376 return (gimple_call_nonnull_result_p (call_stmt
)
377 || gimple_call_nonnull_arg (call_stmt
));
383 /* Like tree_expr_nonzero_p, but this function uses value ranges
387 vr_values::vrp_stmt_computes_nonzero (gimple
*stmt
)
389 if (gimple_stmt_nonzero_p (stmt
))
392 /* If we have an expression of the form &X->a, then the expression
393 is nonnull if X is nonnull. */
394 if (is_gimple_assign (stmt
)
395 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
397 tree expr
= gimple_assign_rhs1 (stmt
);
398 poly_int64 bitsize
, bitpos
;
401 int unsignedp
, reversep
, volatilep
;
402 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
403 &bitpos
, &offset
, &mode
, &unsignedp
,
404 &reversep
, &volatilep
);
406 if (base
!= NULL_TREE
407 && TREE_CODE (base
) == MEM_REF
408 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
410 poly_offset_int off
= 0;
411 bool off_cst
= false;
412 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
414 off
= mem_ref_offset (base
);
416 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
418 off
<<= LOG2_BITS_PER_UNIT
;
422 /* If &X->a is equal to X and X is ~[0, 0], the result is too.
423 For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
424 allow going from non-NULL pointer to NULL. */
425 if ((off_cst
&& known_eq (off
, 0))
426 || (flag_delete_null_pointer_checks
427 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))))
429 const value_range_equiv
*vr
430 = get_value_range (TREE_OPERAND (base
, 0));
431 if (!range_includes_zero_p (vr
))
434 /* If MEM_REF has a "positive" offset, consider it non-NULL
435 always, for -fdelete-null-pointer-checks also "negative"
436 ones. Punt for unknown offsets (e.g. variable ones). */
437 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
440 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
448 /* Returns true if EXPR is a valid value (as expected by compare_values) --
449 a gimple invariant, or SSA_NAME +- CST. */
452 valid_value_p (tree expr
)
454 if (TREE_CODE (expr
) == SSA_NAME
)
457 if (TREE_CODE (expr
) == PLUS_EXPR
458 || TREE_CODE (expr
) == MINUS_EXPR
)
459 return (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
460 && TREE_CODE (TREE_OPERAND (expr
, 1)) == INTEGER_CST
);
462 return is_gimple_min_invariant (expr
);
465 /* If OP has a value range with a single constant value return that,
466 otherwise return NULL_TREE. This returns OP itself if OP is a
470 vr_values::op_with_constant_singleton_value_range (tree op
)
472 if (is_gimple_min_invariant (op
))
475 if (TREE_CODE (op
) != SSA_NAME
)
479 if (get_value_range (op
)->singleton_p (&t
))
484 /* Return true if op is in a boolean [0, 1] value-range. */
487 simplify_using_ranges::op_with_boolean_value_range_p (tree op
)
489 if (TYPE_PRECISION (TREE_TYPE (op
)) == 1)
492 if (integer_zerop (op
)
493 || integer_onep (op
))
496 if (TREE_CODE (op
) != SSA_NAME
)
499 /* ?? Errr, this should probably check for [0,0] and [1,1] as well
501 const value_range
*vr
= query
->get_value_range (op
);
502 return *vr
== value_range (build_zero_cst (TREE_TYPE (op
)),
503 build_one_cst (TREE_TYPE (op
)));
506 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
507 true and store it in *VR_P. */
510 vr_values::extract_range_for_var_from_comparison_expr (tree var
,
511 enum tree_code cond_code
,
513 value_range_equiv
*vr_p
)
516 const value_range_equiv
*limit_vr
;
517 type
= TREE_TYPE (var
);
519 /* For pointer arithmetic, we only keep track of pointer equality
520 and inequality. If we arrive here with unfolded conditions like
521 _1 > _1 do not derive anything. */
522 if ((POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
525 vr_p
->set_varying (type
);
529 /* If LIMIT is another SSA name and LIMIT has a range of its own,
530 try to use LIMIT's range to avoid creating symbolic ranges
532 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
534 /* LIMIT's range is only interesting if it has any useful information. */
536 || limit_vr
->undefined_p ()
537 || limit_vr
->varying_p ()
538 || (limit_vr
->symbolic_p ()
539 && ! (limit_vr
->kind () == VR_RANGE
540 && (limit_vr
->min () == limit_vr
->max ()
541 || operand_equal_p (limit_vr
->min (),
542 limit_vr
->max (), 0)))))
545 /* Initially, the new range has the same set of equivalences of
546 VAR's range. This will be revised before returning the final
547 value. Since assertions may be chained via mutually exclusive
548 predicates, we will need to trim the set of equivalences before
550 gcc_assert (vr_p
->equiv () == NULL
);
551 vr_p
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
553 /* Extract a new range based on the asserted comparison for VAR and
554 LIMIT's value range. Notice that if LIMIT has an anti-range, we
555 will only use it for equality comparisons (EQ_EXPR). For any
556 other kind of assertion, we cannot derive a range from LIMIT's
557 anti-range that can be used to describe the new range. For
558 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
559 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
560 no single range for x_2 that could describe LE_EXPR, so we might
561 as well build the range [b_4, +INF] for it.
562 One special case we handle is extracting a range from a
563 range test encoded as (unsigned)var + CST <= limit. */
564 if (TREE_CODE (op
) == NOP_EXPR
565 || TREE_CODE (op
) == PLUS_EXPR
)
567 if (TREE_CODE (op
) == PLUS_EXPR
)
569 min
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (TREE_OPERAND (op
, 1)),
570 TREE_OPERAND (op
, 1));
571 max
= int_const_binop (PLUS_EXPR
, limit
, min
);
572 op
= TREE_OPERAND (op
, 0);
576 min
= build_int_cst (TREE_TYPE (var
), 0);
580 /* Make sure to not set TREE_OVERFLOW on the final type
581 conversion. We are willingly interpreting large positive
582 unsigned values as negative signed values here. */
583 min
= force_fit_type (TREE_TYPE (var
), wi::to_widest (min
), 0, false);
584 max
= force_fit_type (TREE_TYPE (var
), wi::to_widest (max
), 0, false);
586 /* We can transform a max, min range to an anti-range or
587 vice-versa. Use set_and_canonicalize which does this for
589 if (cond_code
== LE_EXPR
)
590 vr_p
->set (min
, max
, vr_p
->equiv ());
591 else if (cond_code
== GT_EXPR
)
592 vr_p
->set (min
, max
, vr_p
->equiv (), VR_ANTI_RANGE
);
596 else if (cond_code
== EQ_EXPR
)
598 enum value_range_kind range_kind
;
602 range_kind
= limit_vr
->kind ();
603 min
= limit_vr
->min ();
604 max
= limit_vr
->max ();
608 range_kind
= VR_RANGE
;
613 vr_p
->update (min
, max
, range_kind
);
615 /* When asserting the equality VAR == LIMIT and LIMIT is another
616 SSA name, the new range will also inherit the equivalence set
618 if (TREE_CODE (limit
) == SSA_NAME
)
619 vr_p
->equiv_add (limit
, get_value_range (limit
), &vrp_equiv_obstack
);
621 else if (cond_code
== NE_EXPR
)
623 /* As described above, when LIMIT's range is an anti-range and
624 this assertion is an inequality (NE_EXPR), then we cannot
625 derive anything from the anti-range. For instance, if
626 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
627 not imply that VAR's range is [0, 0]. So, in the case of
628 anti-ranges, we just assert the inequality using LIMIT and
631 If LIMIT_VR is a range, we can only use it to build a new
632 anti-range if LIMIT_VR is a single-valued range. For
633 instance, if LIMIT_VR is [0, 1], the predicate
634 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
635 Rather, it means that for value 0 VAR should be ~[0, 0]
636 and for value 1, VAR should be ~[1, 1]. We cannot
637 represent these ranges.
639 The only situation in which we can build a valid
640 anti-range is when LIMIT_VR is a single-valued range
641 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
642 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
644 && limit_vr
->kind () == VR_RANGE
645 && compare_values (limit_vr
->min (), limit_vr
->max ()) == 0)
647 min
= limit_vr
->min ();
648 max
= limit_vr
->max ();
652 /* In any other case, we cannot use LIMIT's range to build a
657 /* If MIN and MAX cover the whole range for their type, then
658 just use the original LIMIT. */
659 if (INTEGRAL_TYPE_P (type
)
660 && vrp_val_is_min (min
)
661 && vrp_val_is_max (max
))
664 vr_p
->set (min
, max
, vr_p
->equiv (), VR_ANTI_RANGE
);
666 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
668 min
= TYPE_MIN_VALUE (type
);
670 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
674 /* If LIMIT_VR is of the form [N1, N2], we need to build the
675 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
677 max
= limit_vr
->max ();
680 /* If the maximum value forces us to be out of bounds, simply punt.
681 It would be pointless to try and do anything more since this
682 all should be optimized away above us. */
683 if (cond_code
== LT_EXPR
684 && compare_values (max
, min
) == 0)
685 vr_p
->set_varying (TREE_TYPE (min
));
688 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
689 if (cond_code
== LT_EXPR
)
691 if (TYPE_PRECISION (TREE_TYPE (max
)) == 1
692 && !TYPE_UNSIGNED (TREE_TYPE (max
)))
693 max
= fold_build2 (PLUS_EXPR
, TREE_TYPE (max
), max
,
694 build_int_cst (TREE_TYPE (max
), -1));
696 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max
), max
,
697 build_int_cst (TREE_TYPE (max
), 1));
698 /* Signal to compare_values_warnv this expr doesn't overflow. */
700 TREE_NO_WARNING (max
) = 1;
703 vr_p
->update (min
, max
);
706 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
708 max
= TYPE_MAX_VALUE (type
);
710 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
714 /* If LIMIT_VR is of the form [N1, N2], we need to build the
715 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
717 min
= limit_vr
->min ();
720 /* If the minimum value forces us to be out of bounds, simply punt.
721 It would be pointless to try and do anything more since this
722 all should be optimized away above us. */
723 if (cond_code
== GT_EXPR
724 && compare_values (min
, max
) == 0)
725 vr_p
->set_varying (TREE_TYPE (min
));
728 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
729 if (cond_code
== GT_EXPR
)
731 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
732 && !TYPE_UNSIGNED (TREE_TYPE (min
)))
733 min
= fold_build2 (MINUS_EXPR
, TREE_TYPE (min
), min
,
734 build_int_cst (TREE_TYPE (min
), -1));
736 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min
), min
,
737 build_int_cst (TREE_TYPE (min
), 1));
738 /* Signal to compare_values_warnv this expr doesn't overflow. */
740 TREE_NO_WARNING (min
) = 1;
743 vr_p
->update (min
, max
);
749 /* Finally intersect the new range with what we already know about var. */
750 vr_p
->intersect (get_value_range (var
));
753 /* Extract value range information from an ASSERT_EXPR EXPR and store
757 vr_values::extract_range_from_assert (value_range_equiv
*vr_p
, tree expr
)
759 tree var
= ASSERT_EXPR_VAR (expr
);
760 tree cond
= ASSERT_EXPR_COND (expr
);
762 enum tree_code cond_code
;
763 gcc_assert (COMPARISON_CLASS_P (cond
));
765 /* Find VAR in the ASSERT_EXPR conditional. */
766 if (var
== TREE_OPERAND (cond
, 0)
767 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PLUS_EXPR
768 || TREE_CODE (TREE_OPERAND (cond
, 0)) == NOP_EXPR
)
770 /* If the predicate is of the form VAR COMP LIMIT, then we just
771 take LIMIT from the RHS and use the same comparison code. */
772 cond_code
= TREE_CODE (cond
);
773 limit
= TREE_OPERAND (cond
, 1);
774 op
= TREE_OPERAND (cond
, 0);
778 /* If the predicate is of the form LIMIT COMP VAR, then we need
779 to flip around the comparison code to create the proper range
781 cond_code
= swap_tree_comparison (TREE_CODE (cond
));
782 limit
= TREE_OPERAND (cond
, 0);
783 op
= TREE_OPERAND (cond
, 1);
785 extract_range_for_var_from_comparison_expr (var
, cond_code
, op
,
789 /* Extract range information from SSA name VAR and store it in VR. If
790 VAR has an interesting range, use it. Otherwise, create the
791 range [VAR, VAR] and return it. This is useful in situations where
792 we may have conditionals testing values of VARYING names. For
799 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
803 vr_values::extract_range_from_ssa_name (value_range_equiv
*vr
, tree var
)
805 const value_range_equiv
*var_vr
= get_value_range (var
);
807 if (!var_vr
->varying_p ())
808 vr
->deep_copy (var_vr
);
812 if (!vr
->undefined_p ())
813 vr
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
816 /* Extract range information from a binary expression OP0 CODE OP1 based on
817 the ranges of each of its operands with resulting type EXPR_TYPE.
818 The resulting range is stored in *VR. */
821 vr_values::extract_range_from_binary_expr (value_range_equiv
*vr
,
823 tree expr_type
, tree op0
, tree op1
)
825 /* Get value ranges for each operand. For constant operands, create
826 a new value range with the operand to simplify processing. */
827 value_range vr0
, vr1
;
828 if (TREE_CODE (op0
) == SSA_NAME
)
829 vr0
= *(get_value_range (op0
));
830 else if (is_gimple_min_invariant (op0
))
833 vr0
.set_varying (TREE_TYPE (op0
));
835 if (TREE_CODE (op1
) == SSA_NAME
)
836 vr1
= *(get_value_range (op1
));
837 else if (is_gimple_min_invariant (op1
))
840 vr1
.set_varying (TREE_TYPE (op1
));
842 /* If one argument is varying, we can sometimes still deduce a
843 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
844 if (INTEGRAL_TYPE_P (TREE_TYPE (op0
))
845 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0
)))
847 if (vr0
.varying_p () && !vr1
.varying_p ())
848 vr0
= value_range (vrp_val_min (expr_type
), vrp_val_max (expr_type
));
849 else if (vr1
.varying_p () && !vr0
.varying_p ())
850 vr1
= value_range (vrp_val_min (expr_type
), vrp_val_max (expr_type
));
853 range_fold_binary_expr (vr
, code
, expr_type
, &vr0
, &vr1
);
855 /* Set value_range for n in following sequence:
856 def = __builtin_memchr (arg, 0, sz)
858 Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
861 && code
== POINTER_DIFF_EXPR
862 && TREE_CODE (op0
) == SSA_NAME
863 && TREE_CODE (op1
) == SSA_NAME
)
865 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
866 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
867 gcall
*call_stmt
= NULL
;
869 if (TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
870 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
871 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
872 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
873 && (call_stmt
= dyn_cast
<gcall
*>(SSA_NAME_DEF_STMT (op0
)))
874 && gimple_call_builtin_p (call_stmt
, BUILT_IN_MEMCHR
)
875 && operand_equal_p (op0
, gimple_call_lhs (call_stmt
), 0)
876 && operand_equal_p (op1
, gimple_call_arg (call_stmt
, 0), 0)
877 && integer_zerop (gimple_call_arg (call_stmt
, 1)))
879 tree max
= vrp_val_max (ptrdiff_type_node
);
880 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
881 tree range_min
= build_zero_cst (expr_type
);
882 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
883 vr
->set (range_min
, range_max
);
888 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
889 and based on the other operand, for example if it was deduced from a
890 symbolic comparison. When a bound of the range of the first operand
891 is invariant, we set the corresponding bound of the new range to INF
892 in order to avoid recursing on the range of the second operand. */
894 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
895 && TREE_CODE (op1
) == SSA_NAME
896 && vr0
.kind () == VR_RANGE
897 && symbolic_range_based_on_p (&vr0
, op1
))
899 const bool minus_p
= (code
== MINUS_EXPR
);
902 /* Try with VR0 and [-INF, OP1]. */
903 if (is_gimple_min_invariant (minus_p
? vr0
.max () : vr0
.min ()))
904 n_vr1
.set (vrp_val_min (expr_type
), op1
);
906 /* Try with VR0 and [OP1, +INF]. */
907 else if (is_gimple_min_invariant (minus_p
? vr0
.min () : vr0
.max ()))
908 n_vr1
.set (op1
, vrp_val_max (expr_type
));
910 /* Try with VR0 and [OP1, OP1]. */
912 n_vr1
.set (op1
, op1
);
914 range_fold_binary_expr (vr
, code
, expr_type
, &vr0
, &n_vr1
);
918 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
919 && TREE_CODE (op0
) == SSA_NAME
920 && vr1
.kind () == VR_RANGE
921 && symbolic_range_based_on_p (&vr1
, op0
))
923 const bool minus_p
= (code
== MINUS_EXPR
);
926 /* Try with [-INF, OP0] and VR1. */
927 if (is_gimple_min_invariant (minus_p
? vr1
.max () : vr1
.min ()))
928 n_vr0
.set (vrp_val_min (expr_type
), op0
);
930 /* Try with [OP0, +INF] and VR1. */
931 else if (is_gimple_min_invariant (minus_p
? vr1
.min (): vr1
.max ()))
932 n_vr0
.set (op0
, vrp_val_max (expr_type
));
934 /* Try with [OP0, OP0] and VR1. */
938 range_fold_binary_expr (vr
, code
, expr_type
, &n_vr0
, &vr1
);
941 /* If we didn't derive a range for MINUS_EXPR, and
942 op1's range is ~[op0,op0] or vice-versa, then we
943 can derive a non-null range. This happens often for
944 pointer subtraction. */
946 && (code
== MINUS_EXPR
|| code
== POINTER_DIFF_EXPR
)
947 && TREE_CODE (op0
) == SSA_NAME
948 && ((vr0
.kind () == VR_ANTI_RANGE
950 && vr0
.min () == vr0
.max ())
951 || (vr1
.kind () == VR_ANTI_RANGE
953 && vr1
.min () == vr1
.max ())))
955 vr
->set_nonzero (expr_type
);
960 /* Extract range information from a unary expression CODE OP0 based on
961 the range of its operand with resulting type TYPE.
962 The resulting range is stored in *VR. */
965 vr_values::extract_range_from_unary_expr (value_range_equiv
*vr
,
971 /* Get value ranges for the operand. For constant operands, create
972 a new value range with the operand to simplify processing. */
973 if (TREE_CODE (op0
) == SSA_NAME
)
974 vr0
= *(get_value_range (op0
));
975 else if (is_gimple_min_invariant (op0
))
978 vr0
.set_varying (type
);
980 range_fold_unary_expr (vr
, code
, type
, &vr0
, TREE_TYPE (op0
));
984 /* Extract range information from a conditional expression STMT based on
985 the ranges of each of its operands and the expression code. */
988 vr_values::extract_range_from_cond_expr (value_range_equiv
*vr
, gassign
*stmt
)
990 /* Get value ranges for each operand. For constant operands, create
991 a new value range with the operand to simplify processing. */
992 tree op0
= gimple_assign_rhs2 (stmt
);
993 value_range_equiv tem0
;
994 const value_range_equiv
*vr0
= &tem0
;
995 if (TREE_CODE (op0
) == SSA_NAME
)
996 vr0
= get_value_range (op0
);
997 else if (is_gimple_min_invariant (op0
))
1000 tem0
.set_varying (TREE_TYPE (op0
));
1002 tree op1
= gimple_assign_rhs3 (stmt
);
1003 value_range_equiv tem1
;
1004 const value_range_equiv
*vr1
= &tem1
;
1005 if (TREE_CODE (op1
) == SSA_NAME
)
1006 vr1
= get_value_range (op1
);
1007 else if (is_gimple_min_invariant (op1
))
1010 tem1
.set_varying (TREE_TYPE (op1
));
1012 /* The resulting value range is the union of the operand ranges */
1013 vr
->deep_copy (vr0
);
1018 /* Extract range information from a comparison expression EXPR based
1019 on the range of its operand and the expression code. */
1022 vr_values::extract_range_from_comparison (value_range_equiv
*vr
,
1025 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1026 tree type
= gimple_expr_type (stmt
);
1027 tree op0
= gimple_assign_rhs1 (stmt
);
1028 tree op1
= gimple_assign_rhs2 (stmt
);
1031 = simplifier
.vrp_evaluate_conditional_warnv_with_ops (stmt
, code
, op0
, op1
,
1035 /* Since this expression was found on the RHS of an assignment,
1036 its type may be different from _Bool. Convert VAL to EXPR's
1038 val
= fold_convert (type
, val
);
1039 if (is_gimple_min_invariant (val
))
1042 vr
->update (val
, val
);
1045 /* The result of a comparison is always true or false. */
1046 set_value_range_to_truthvalue (vr
, type
);
1049 /* Helper function for simplify_internal_call_using_ranges and
1050 extract_range_basic. Return true if OP0 SUBCODE OP1 for
1051 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
1052 always overflow. Set *OVF to true if it is known to always
1056 check_for_binary_op_overflow (range_query
*query
,
1057 enum tree_code subcode
, tree type
,
1058 tree op0
, tree op1
, bool *ovf
)
1060 value_range vr0
, vr1
;
1061 if (TREE_CODE (op0
) == SSA_NAME
)
1062 vr0
= *query
->get_value_range (op0
);
1063 else if (TREE_CODE (op0
) == INTEGER_CST
)
1066 vr0
.set_varying (TREE_TYPE (op0
));
1068 if (TREE_CODE (op1
) == SSA_NAME
)
1069 vr1
= *query
->get_value_range (op1
);
1070 else if (TREE_CODE (op1
) == INTEGER_CST
)
1073 vr1
.set_varying (TREE_TYPE (op1
));
1075 tree vr0min
= vr0
.min (), vr0max
= vr0
.max ();
1076 tree vr1min
= vr1
.min (), vr1max
= vr1
.max ();
1077 if (!range_int_cst_p (&vr0
)
1078 || TREE_OVERFLOW (vr0min
)
1079 || TREE_OVERFLOW (vr0max
))
1081 vr0min
= vrp_val_min (TREE_TYPE (op0
));
1082 vr0max
= vrp_val_max (TREE_TYPE (op0
));
1084 if (!range_int_cst_p (&vr1
)
1085 || TREE_OVERFLOW (vr1min
)
1086 || TREE_OVERFLOW (vr1max
))
1088 vr1min
= vrp_val_min (TREE_TYPE (op1
));
1089 vr1max
= vrp_val_max (TREE_TYPE (op1
));
1091 *ovf
= arith_overflowed_p (subcode
, type
, vr0min
,
1092 subcode
== MINUS_EXPR
? vr1max
: vr1min
);
1093 if (arith_overflowed_p (subcode
, type
, vr0max
,
1094 subcode
== MINUS_EXPR
? vr1min
: vr1max
) != *ovf
)
1096 if (subcode
== MULT_EXPR
)
1098 if (arith_overflowed_p (subcode
, type
, vr0min
, vr1max
) != *ovf
1099 || arith_overflowed_p (subcode
, type
, vr0max
, vr1min
) != *ovf
)
1104 /* So far we found that there is an overflow on the boundaries.
1105 That doesn't prove that there is an overflow even for all values
1106 in between the boundaries. For that compute widest_int range
1107 of the result and see if it doesn't overlap the range of
1109 widest_int wmin
, wmax
;
1112 w
[0] = wi::to_widest (vr0min
);
1113 w
[1] = wi::to_widest (vr0max
);
1114 w
[2] = wi::to_widest (vr1min
);
1115 w
[3] = wi::to_widest (vr1max
);
1116 for (i
= 0; i
< 4; i
++)
1122 wt
= wi::add (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1125 wt
= wi::sub (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1128 wt
= wi::mul (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1140 wmin
= wi::smin (wmin
, wt
);
1141 wmax
= wi::smax (wmax
, wt
);
1144 /* The result of op0 CODE op1 is known to be in range
1146 widest_int wtmin
= wi::to_widest (vrp_val_min (type
));
1147 widest_int wtmax
= wi::to_widest (vrp_val_max (type
));
1148 /* If all values in [wmin, wmax] are smaller than
1149 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1150 the arithmetic operation will always overflow. */
1151 if (wmax
< wtmin
|| wmin
> wtmax
)
1158 /* Derive a range from a builtin. Set range in VR and return TRUE if
1162 vr_values::extract_range_builtin (value_range_equiv
*vr
, gimple
*stmt
)
1164 gcc_assert (is_gimple_call (stmt
));
1165 tree type
= gimple_expr_type (stmt
);
1167 int mini
, maxi
, zerov
= 0, prec
;
1168 enum tree_code subcode
= ERROR_MARK
;
1169 combined_fn cfn
= gimple_call_combined_fn (stmt
);
1170 scalar_int_mode mode
;
1174 case CFN_BUILT_IN_CONSTANT_P
:
1175 /* Resolve calls to __builtin_constant_p after inlining. */
1176 if (cfun
->after_inlining
)
1178 vr
->set_zero (type
);
1183 /* Both __builtin_ffs* and __builtin_popcount return
1187 arg
= gimple_call_arg (stmt
, 0);
1188 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1191 if (TREE_CODE (arg
) == SSA_NAME
)
1193 const value_range_equiv
*vr0
= get_value_range (arg
);
1194 /* If arg is non-zero, then ffs or popcount are non-zero. */
1195 if (range_includes_zero_p (vr0
) == 0)
1197 /* If some high bits are known to be zero,
1198 we can decrease the maximum. */
1199 if (vr0
->kind () == VR_RANGE
1200 && TREE_CODE (vr0
->max ()) == INTEGER_CST
1201 && !operand_less_p (vr0
->min (),
1202 build_zero_cst (TREE_TYPE (vr0
->min ()))))
1203 maxi
= tree_floor_log2 (vr0
->max ()) + 1;
1206 /* __builtin_parity* returns [0, 1]. */
1211 /* __builtin_clz* return [0, prec-1], except for
1212 when the argument is 0, but that is undefined behavior.
1213 Always handle __builtin_clz* which can be only written
1214 by user as UB on 0 and so [0, prec-1] range, and the internal-fn
1215 calls depending on how CLZ_DEFINED_VALUE_AT_ZERO is defined. */
1217 arg
= gimple_call_arg (stmt
, 0);
1218 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1221 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1222 if (gimple_call_internal_p (stmt
))
1224 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
1225 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
1227 /* Handle only the single common value. */
1230 /* Magic value to give up, unless vr0 proves
1236 if (TREE_CODE (arg
) == SSA_NAME
)
1238 const value_range_equiv
*vr0
= get_value_range (arg
);
1239 /* From clz of VR_RANGE minimum we can compute
1241 if (vr0
->kind () == VR_RANGE
1242 && TREE_CODE (vr0
->min ()) == INTEGER_CST
1243 && integer_nonzerop (vr0
->min ()))
1245 maxi
= prec
- 1 - tree_floor_log2 (vr0
->min ());
1249 else if (vr0
->kind () == VR_ANTI_RANGE
1250 && integer_zerop (vr0
->min ()))
1257 /* From clz of VR_RANGE maximum we can compute
1259 if (vr0
->kind () == VR_RANGE
1260 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1262 int newmini
= prec
- 1 - tree_floor_log2 (vr0
->max ());
1263 if (newmini
== prec
)
1275 /* __builtin_ctz* return [0, prec-1], except for
1276 when the argument is 0, but that is undefined behavior.
1277 Always handle __builtin_ctz* which can be only written
1278 by user as UB on 0 and so [0, prec-1] range, and the internal-fn
1279 calls depending on how CTZ_DEFINED_VALUE_AT_ZERO is defined. */
1281 arg
= gimple_call_arg (stmt
, 0);
1282 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1285 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1286 if (gimple_call_internal_p (stmt
))
1288 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1289 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
1291 /* Handle only the two common values. */
1294 else if (zerov
== prec
)
1297 /* Magic value to give up, unless vr0 proves
1302 if (TREE_CODE (arg
) == SSA_NAME
)
1304 const value_range_equiv
*vr0
= get_value_range (arg
);
1305 /* If arg is non-zero, then use [0, prec - 1]. */
1306 if ((vr0
->kind () == VR_RANGE
1307 && integer_nonzerop (vr0
->min ()))
1308 || (vr0
->kind () == VR_ANTI_RANGE
1309 && integer_zerop (vr0
->min ())))
1314 /* If some high bits are known to be zero,
1315 we can decrease the result maximum. */
1316 if (vr0
->kind () == VR_RANGE
1317 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1319 int newmaxi
= tree_floor_log2 (vr0
->max ());
1324 else if (maxi
== prec
)
1327 else if (maxi
!= prec
)
1334 /* __builtin_clrsb* returns [0, prec-1]. */
1336 arg
= gimple_call_arg (stmt
, 0);
1337 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1342 vr
->set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
1344 case CFN_UBSAN_CHECK_ADD
:
1345 subcode
= PLUS_EXPR
;
1347 case CFN_UBSAN_CHECK_SUB
:
1348 subcode
= MINUS_EXPR
;
1350 case CFN_UBSAN_CHECK_MUL
:
1351 subcode
= MULT_EXPR
;
1353 case CFN_GOACC_DIM_SIZE
:
1354 case CFN_GOACC_DIM_POS
:
1355 /* Optimizing these two internal functions helps the loop
1356 optimizer eliminate outer comparisons. Size is [1,N]
1357 and pos is [0,N-1]. */
1359 bool is_pos
= cfn
== CFN_GOACC_DIM_POS
;
1360 int axis
= oacc_get_ifn_dim_arg (stmt
);
1361 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1364 /* If it's dynamic, the backend might know a hardware
1366 size
= targetm
.goacc
.dim_limit (axis
);
1368 tree type
= TREE_TYPE (gimple_call_lhs (stmt
));
1369 vr
->set(build_int_cst (type
, is_pos
? 0 : 1),
1371 ? build_int_cst (type
, size
- is_pos
) : vrp_val_max (type
));
1374 case CFN_BUILT_IN_STRLEN
:
1375 if (tree lhs
= gimple_call_lhs (stmt
))
1376 if (ptrdiff_type_node
1377 && (TYPE_PRECISION (ptrdiff_type_node
)
1378 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1380 tree type
= TREE_TYPE (lhs
);
1381 tree max
= vrp_val_max (ptrdiff_type_node
);
1382 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1383 tree range_min
= build_zero_cst (type
);
1384 /* To account for the terminating NUL, the maximum length
1385 is one less than the maximum array size, which in turn
1386 is one less than PTRDIFF_MAX (or SIZE_MAX where it's
1387 smaller than the former type).
1388 FIXME: Use max_object_size() - 1 here. */
1389 tree range_max
= wide_int_to_tree (type
, wmax
- 2);
1390 vr
->set (range_min
, range_max
);
1397 if (subcode
!= ERROR_MARK
)
1399 bool saved_flag_wrapv
= flag_wrapv
;
1400 /* Pretend the arithmetics is wrapping. If there is
1401 any overflow, we'll complain, but will actually do
1402 wrapping operation. */
1404 extract_range_from_binary_expr (vr
, subcode
, type
,
1405 gimple_call_arg (stmt
, 0),
1406 gimple_call_arg (stmt
, 1));
1407 flag_wrapv
= saved_flag_wrapv
;
1409 /* If for both arguments vrp_valueize returned non-NULL,
1410 this should have been already folded and if not, it
1411 wasn't folded because of overflow. Avoid removing the
1412 UBSAN_CHECK_* calls in that case. */
1413 if (vr
->kind () == VR_RANGE
1414 && (vr
->min () == vr
->max ()
1415 || operand_equal_p (vr
->min (), vr
->max (), 0)))
1416 vr
->set_varying (vr
->type ());
1418 return !vr
->varying_p ();
1423 /* Try to derive a nonnegative or nonzero range out of STMT relying
1424 primarily on generic routines in fold in conjunction with range data.
1425 Store the result in *VR */
1428 vr_values::extract_range_basic (value_range_equiv
*vr
, gimple
*stmt
)
1431 tree type
= gimple_expr_type (stmt
);
1433 if (is_gimple_call (stmt
) && extract_range_builtin (vr
, stmt
))
1435 value_range_equiv tmp
;
1436 /* Assert that any ranges vr_values::extract_range_builtin gets
1437 are also handled by the ranger counterpart. */
1438 gcc_assert (range_of_builtin_call (*this, tmp
, as_a
<gcall
*> (stmt
)));
1440 /* Disable this while PR97505 is resolved. */
1441 gcc_assert (tmp
.equal_p (*vr
, /*ignore_equivs=*/false));
1445 /* Handle extraction of the two results (result of arithmetics and
1446 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1447 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1448 else if (is_gimple_assign (stmt
)
1449 && (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
1450 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
)
1451 && INTEGRAL_TYPE_P (type
))
1453 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1454 tree op
= gimple_assign_rhs1 (stmt
);
1455 if (TREE_CODE (op
) == code
&& TREE_CODE (TREE_OPERAND (op
, 0)) == SSA_NAME
)
1457 gimple
*g
= SSA_NAME_DEF_STMT (TREE_OPERAND (op
, 0));
1458 if (is_gimple_call (g
) && gimple_call_internal_p (g
))
1460 enum tree_code subcode
= ERROR_MARK
;
1461 switch (gimple_call_internal_fn (g
))
1463 case IFN_ADD_OVERFLOW
:
1464 subcode
= PLUS_EXPR
;
1466 case IFN_SUB_OVERFLOW
:
1467 subcode
= MINUS_EXPR
;
1469 case IFN_MUL_OVERFLOW
:
1470 subcode
= MULT_EXPR
;
1472 case IFN_ATOMIC_COMPARE_EXCHANGE
:
1473 if (code
== IMAGPART_EXPR
)
1475 /* This is the boolean return value whether compare and
1476 exchange changed anything or not. */
1477 vr
->set (build_int_cst (type
, 0),
1478 build_int_cst (type
, 1));
1485 if (subcode
!= ERROR_MARK
)
1487 tree op0
= gimple_call_arg (g
, 0);
1488 tree op1
= gimple_call_arg (g
, 1);
1489 if (code
== IMAGPART_EXPR
)
1492 if (check_for_binary_op_overflow (this, subcode
, type
,
1494 vr
->set (build_int_cst (type
, ovf
));
1495 else if (TYPE_PRECISION (type
) == 1
1496 && !TYPE_UNSIGNED (type
))
1497 vr
->set_varying (type
);
1499 vr
->set (build_int_cst (type
, 0),
1500 build_int_cst (type
, 1));
1502 else if (types_compatible_p (type
, TREE_TYPE (op0
))
1503 && types_compatible_p (type
, TREE_TYPE (op1
)))
1505 bool saved_flag_wrapv
= flag_wrapv
;
1506 /* Pretend the arithmetics is wrapping. If there is
1507 any overflow, IMAGPART_EXPR will be set. */
1509 extract_range_from_binary_expr (vr
, subcode
, type
,
1511 flag_wrapv
= saved_flag_wrapv
;
1515 value_range_equiv vr0
, vr1
;
1516 bool saved_flag_wrapv
= flag_wrapv
;
1517 /* Pretend the arithmetics is wrapping. If there is
1518 any overflow, IMAGPART_EXPR will be set. */
1520 extract_range_from_unary_expr (&vr0
, NOP_EXPR
,
1522 extract_range_from_unary_expr (&vr1
, NOP_EXPR
,
1524 range_fold_binary_expr (vr
, subcode
, type
, &vr0
, &vr1
);
1525 flag_wrapv
= saved_flag_wrapv
;
1532 if (INTEGRAL_TYPE_P (type
)
1533 && gimple_stmt_nonnegative_warnv_p (stmt
, &sop
))
1534 set_value_range_to_nonnegative (vr
, type
);
1535 else if (vrp_stmt_computes_nonzero (stmt
))
1537 vr
->set_nonzero (type
);
1541 vr
->set_varying (type
);
1545 /* Try to compute a useful range out of assignment STMT and store it
1549 vr_values::extract_range_from_assignment (value_range_equiv
*vr
, gassign
*stmt
)
1551 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1553 if (code
== ASSERT_EXPR
)
1554 extract_range_from_assert (vr
, gimple_assign_rhs1 (stmt
));
1555 else if (code
== SSA_NAME
)
1556 extract_range_from_ssa_name (vr
, gimple_assign_rhs1 (stmt
));
1557 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
1558 extract_range_from_binary_expr (vr
, gimple_assign_rhs_code (stmt
),
1559 gimple_expr_type (stmt
),
1560 gimple_assign_rhs1 (stmt
),
1561 gimple_assign_rhs2 (stmt
));
1562 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1563 extract_range_from_unary_expr (vr
, gimple_assign_rhs_code (stmt
),
1564 gimple_expr_type (stmt
),
1565 gimple_assign_rhs1 (stmt
));
1566 else if (code
== COND_EXPR
)
1567 extract_range_from_cond_expr (vr
, stmt
);
1568 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1569 extract_range_from_comparison (vr
, stmt
);
1570 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1571 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1572 vr
->set (gimple_assign_rhs1 (stmt
));
1574 vr
->set_varying (TREE_TYPE (gimple_assign_lhs (stmt
)));
1576 if (vr
->varying_p ())
1577 extract_range_basic (vr
, stmt
);
1580 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1582 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1583 all the values in the ranges.
1585 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1587 - Return NULL_TREE if it is not always possible to determine the
1588 value of the comparison.
1590 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1591 assumed signed overflow is undefined. */
1595 compare_ranges (enum tree_code comp
, const value_range_equiv
*vr0
,
1596 const value_range_equiv
*vr1
, bool *strict_overflow_p
)
1598 /* VARYING or UNDEFINED ranges cannot be compared. */
1599 if (vr0
->varying_p ()
1600 || vr0
->undefined_p ()
1601 || vr1
->varying_p ()
1602 || vr1
->undefined_p ())
1605 /* Anti-ranges need to be handled separately. */
1606 if (vr0
->kind () == VR_ANTI_RANGE
|| vr1
->kind () == VR_ANTI_RANGE
)
1608 /* If both are anti-ranges, then we cannot compute any
1610 if (vr0
->kind () == VR_ANTI_RANGE
&& vr1
->kind () == VR_ANTI_RANGE
)
1613 /* These comparisons are never statically computable. */
1620 /* Equality can be computed only between a range and an
1621 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1622 if (vr0
->kind () == VR_RANGE
)
1623 /* To simplify processing, make VR0 the anti-range. */
1624 std::swap (vr0
, vr1
);
1626 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1628 if (compare_values_warnv (vr0
->min (), vr1
->min (), strict_overflow_p
) == 0
1629 && compare_values_warnv (vr0
->max (), vr1
->max (), strict_overflow_p
) == 0)
1630 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1635 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1636 operands around and change the comparison code. */
1637 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1639 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1640 std::swap (vr0
, vr1
);
1643 if (comp
== EQ_EXPR
)
1645 /* Equality may only be computed if both ranges represent
1646 exactly one value. */
1647 if (compare_values_warnv (vr0
->min (), vr0
->max (), strict_overflow_p
) == 0
1648 && compare_values_warnv (vr1
->min (), vr1
->max (), strict_overflow_p
) == 0)
1650 int cmp_min
= compare_values_warnv (vr0
->min (), vr1
->min (),
1652 int cmp_max
= compare_values_warnv (vr0
->max (), vr1
->max (),
1654 if (cmp_min
== 0 && cmp_max
== 0)
1655 return boolean_true_node
;
1656 else if (cmp_min
!= -2 && cmp_max
!= -2)
1657 return boolean_false_node
;
1659 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1660 else if (compare_values_warnv (vr0
->min (), vr1
->max (),
1661 strict_overflow_p
) == 1
1662 || compare_values_warnv (vr1
->min (), vr0
->max (),
1663 strict_overflow_p
) == 1)
1664 return boolean_false_node
;
1668 else if (comp
== NE_EXPR
)
1672 /* If VR0 is completely to the left or completely to the right
1673 of VR1, they are always different. Notice that we need to
1674 make sure that both comparisons yield similar results to
1675 avoid comparing values that cannot be compared at
1677 cmp1
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1678 cmp2
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1679 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1680 return boolean_true_node
;
1682 /* If VR0 and VR1 represent a single value and are identical,
1684 else if (compare_values_warnv (vr0
->min (), vr0
->max (),
1685 strict_overflow_p
) == 0
1686 && compare_values_warnv (vr1
->min (), vr1
->max (),
1687 strict_overflow_p
) == 0
1688 && compare_values_warnv (vr0
->min (), vr1
->min (),
1689 strict_overflow_p
) == 0
1690 && compare_values_warnv (vr0
->max (), vr1
->max (),
1691 strict_overflow_p
) == 0)
1692 return boolean_false_node
;
1694 /* Otherwise, they may or may not be different. */
1698 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1702 /* If VR0 is to the left of VR1, return true. */
1703 tst
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1704 if ((comp
== LT_EXPR
&& tst
== -1)
1705 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1706 return boolean_true_node
;
1708 /* If VR0 is to the right of VR1, return false. */
1709 tst
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1710 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1711 || (comp
== LE_EXPR
&& tst
== 1))
1712 return boolean_false_node
;
1714 /* Otherwise, we don't know. */
1721 /* Given a value range VR, a value VAL and a comparison code COMP, return
1722 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1723 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1724 always returns false. Return NULL_TREE if it is not always
1725 possible to determine the value of the comparison. Also set
1726 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1727 assumed signed overflow is undefined. */
1730 compare_range_with_value (enum tree_code comp
, const value_range
*vr
,
1731 tree val
, bool *strict_overflow_p
)
1733 if (vr
->varying_p () || vr
->undefined_p ())
1736 /* Anti-ranges need to be handled separately. */
1737 if (vr
->kind () == VR_ANTI_RANGE
)
1739 /* For anti-ranges, the only predicates that we can compute at
1740 compile time are equality and inequality. */
1747 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1748 if (!vr
->may_contain_p (val
))
1749 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1754 if (comp
== EQ_EXPR
)
1756 /* EQ_EXPR may only be computed if VR represents exactly
1758 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0)
1760 int cmp
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1762 return boolean_true_node
;
1763 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1764 return boolean_false_node
;
1766 else if (compare_values_warnv (val
, vr
->min (), strict_overflow_p
) == -1
1767 || compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1)
1768 return boolean_false_node
;
1772 else if (comp
== NE_EXPR
)
1774 /* If VAL is not inside VR, then they are always different. */
1775 if (compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1
1776 || compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 1)
1777 return boolean_true_node
;
1779 /* If VR represents exactly one value equal to VAL, then return
1781 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0
1782 && compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 0)
1783 return boolean_false_node
;
1785 /* Otherwise, they may or may not be different. */
1788 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1792 /* If VR is to the left of VAL, return true. */
1793 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1794 if ((comp
== LT_EXPR
&& tst
== -1)
1795 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1796 return boolean_true_node
;
1798 /* If VR is to the right of VAL, return false. */
1799 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1800 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1801 || (comp
== LE_EXPR
&& tst
== 1))
1802 return boolean_false_node
;
1804 /* Otherwise, we don't know. */
1807 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1811 /* If VR is to the right of VAL, return true. */
1812 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1813 if ((comp
== GT_EXPR
&& tst
== 1)
1814 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1815 return boolean_true_node
;
1817 /* If VR is to the left of VAL, return false. */
1818 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1819 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1820 || (comp
== GE_EXPR
&& tst
== -1))
1821 return boolean_false_node
;
1823 /* Otherwise, we don't know. */
1830 /* Given a VAR in STMT within LOOP, determine the bounds of the
1831 variable and store it in MIN/MAX and return TRUE. If no bounds
1832 could be determined, return FALSE. */
1835 bounds_of_var_in_loop (tree
*min
, tree
*max
, range_query
*query
,
1836 class loop
*loop
, gimple
*stmt
, tree var
)
1838 tree init
, step
, chrec
, tmin
, tmax
, type
= TREE_TYPE (var
);
1839 enum ev_direction dir
;
1841 chrec
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, var
));
1843 /* Like in PR19590, scev can return a constant function. */
1844 if (is_gimple_min_invariant (chrec
))
1846 *min
= *max
= chrec
;
1850 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1853 init
= initial_condition_in_loop_num (chrec
, loop
->num
);
1854 step
= evolution_part_in_loop_num (chrec
, loop
->num
);
1856 /* If INIT is an SSA with a singleton range, set INIT to said
1857 singleton, otherwise leave INIT alone. */
1858 if (TREE_CODE (init
) == SSA_NAME
)
1859 query
->get_value_range (init
, stmt
)->singleton_p (&init
);
1860 /* Likewise for step. */
1861 if (TREE_CODE (step
) == SSA_NAME
)
1862 query
->get_value_range (step
, stmt
)->singleton_p (&step
);
1864 /* If STEP is symbolic, we can't know whether INIT will be the
1865 minimum or maximum value in the range. Also, unless INIT is
1866 a simple expression, compare_values and possibly other functions
1867 in tree-vrp won't be able to handle it. */
1868 if (step
== NULL_TREE
1869 || !is_gimple_min_invariant (step
)
1870 || !valid_value_p (init
))
1873 dir
= scev_direction (chrec
);
1874 if (/* Do not adjust ranges if we do not know whether the iv increases
1875 or decreases, ... */
1876 dir
== EV_DIR_UNKNOWN
1877 /* ... or if it may wrap. */
1878 || scev_probably_wraps_p (NULL_TREE
, init
, step
, stmt
,
1879 get_chrec_loop (chrec
), true))
1882 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1883 tmin
= lower_bound_in_type (type
, type
);
1885 tmin
= TYPE_MIN_VALUE (type
);
1886 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1887 tmax
= upper_bound_in_type (type
, type
);
1889 tmax
= TYPE_MAX_VALUE (type
);
1891 /* Try to use estimated number of iterations for the loop to constrain the
1892 final value in the evolution. */
1893 if (TREE_CODE (step
) == INTEGER_CST
1894 && is_gimple_val (init
)
1895 && (TREE_CODE (init
) != SSA_NAME
1896 || query
->get_value_range (init
, stmt
)->kind () == VR_RANGE
))
1900 /* We are only entering here for loop header PHI nodes, so using
1901 the number of latch executions is the correct thing to use. */
1902 if (max_loop_iterations (loop
, &nit
))
1904 signop sgn
= TYPE_SIGN (TREE_TYPE (step
));
1905 wi::overflow_type overflow
;
1907 widest_int wtmp
= wi::mul (wi::to_widest (step
), nit
, sgn
,
1909 /* If the multiplication overflowed we can't do a meaningful
1910 adjustment. Likewise if the result doesn't fit in the type
1911 of the induction variable. For a signed type we have to
1912 check whether the result has the expected signedness which
1913 is that of the step as number of iterations is unsigned. */
1915 && wi::fits_to_tree_p (wtmp
, TREE_TYPE (init
))
1917 || wi::gts_p (wtmp
, 0) == wi::gts_p (wi::to_wide (step
), 0)))
1919 value_range maxvr
, vr0
, vr1
;
1920 if (TREE_CODE (init
) == SSA_NAME
)
1921 vr0
= *(query
->get_value_range (init
, stmt
));
1922 else if (is_gimple_min_invariant (init
))
1925 vr0
.set_varying (TREE_TYPE (init
));
1926 tree tem
= wide_int_to_tree (TREE_TYPE (init
), wtmp
);
1928 range_fold_binary_expr (&maxvr
, PLUS_EXPR
,
1929 TREE_TYPE (init
), &vr0
, &vr1
);
1931 /* Likewise if the addition did. */
1932 if (maxvr
.kind () == VR_RANGE
)
1936 if (TREE_CODE (init
) == SSA_NAME
)
1937 initvr
= *(query
->get_value_range (init
, stmt
));
1938 else if (is_gimple_min_invariant (init
))
1943 /* Check if init + nit * step overflows. Though we checked
1944 scev {init, step}_loop doesn't wrap, it is not enough
1945 because the loop may exit immediately. Overflow could
1946 happen in the plus expression in this case. */
1947 if ((dir
== EV_DIR_DECREASES
1948 && compare_values (maxvr
.min (), initvr
.min ()) != -1)
1949 || (dir
== EV_DIR_GROWS
1950 && compare_values (maxvr
.max (), initvr
.max ()) != 1))
1953 tmin
= maxvr
.min ();
1954 tmax
= maxvr
.max ();
1962 if (dir
== EV_DIR_DECREASES
)
1968 /* Even for valid range info, sometimes overflow flag will leak in.
1969 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1971 if (TREE_OVERFLOW_P (*min
))
1972 *min
= drop_tree_overflow (*min
);
1973 if (TREE_OVERFLOW_P (*max
))
1974 *max
= drop_tree_overflow (*max
);
1976 gcc_checking_assert (compare_values (*min
, *max
) != 1);
1980 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1981 would be profitable to adjust VR using scalar evolution information
1982 for VAR. If so, update VR with the new limits. */
1985 vr_values::adjust_range_with_scev (value_range_equiv
*vr
, class loop
*loop
,
1986 gimple
*stmt
, tree var
)
1989 if (bounds_of_var_in_loop (&min
, &max
, this, loop
, stmt
, var
))
1991 if (vr
->undefined_p () || vr
->varying_p ())
1993 /* For VARYING or UNDEFINED ranges, just about anything we get
1994 from scalar evolutions should be better. */
1995 vr
->update (min
, max
);
1997 else if (vr
->kind () == VR_RANGE
)
1999 /* Start with the input range... */
2000 tree vrmin
= vr
->min ();
2001 tree vrmax
= vr
->max ();
2003 /* ...and narrow it down with what we got from SCEV. */
2004 if (compare_values (min
, vrmin
) == 1)
2006 if (compare_values (max
, vrmax
) == -1)
2009 vr
->update (vrmin
, vrmax
);
2011 else if (vr
->kind () == VR_ANTI_RANGE
)
2013 /* ?? As an enhancement, if VR, MIN, and MAX are constants, one
2014 could just intersect VR with a range of [MIN,MAX]. */
2019 /* Dump value ranges of all SSA_NAMEs to FILE. */
2022 vr_values::dump_all_value_ranges (FILE *file
)
2026 for (i
= 0; i
< num_vr_values
; i
++)
2028 if (vr_value
[i
] && ssa_name (i
))
2030 print_generic_expr (file
, ssa_name (i
));
2031 fprintf (file
, ": ");
2032 dump_value_range (file
, vr_value
[i
]);
2033 fprintf (file
, "\n");
2037 fprintf (file
, "\n");
2040 /* Initialize VRP lattice. */
2042 vr_values::vr_values () : simplifier (this)
2044 values_propagated
= false;
2045 num_vr_values
= num_ssa_names
* 2;
2046 vr_value
= XCNEWVEC (value_range_equiv
*, num_vr_values
);
2047 vr_phi_edge_counts
= XCNEWVEC (int, num_ssa_names
);
2048 bitmap_obstack_initialize (&vrp_equiv_obstack
);
2051 /* Free VRP lattice. */
2053 vr_values::~vr_values ()
2055 /* Free allocated memory. */
2057 free (vr_phi_edge_counts
);
2058 bitmap_obstack_release (&vrp_equiv_obstack
);
2060 /* So that we can distinguish between VRP data being available
2061 and not available. */
2063 vr_phi_edge_counts
= NULL
;
2068 static class vr_values
*x_vr_values
;
2070 /* Return the singleton value-range for NAME or NAME. */
2073 vrp_valueize (tree name
)
2075 if (TREE_CODE (name
) == SSA_NAME
)
2077 const value_range_equiv
*vr
= x_vr_values
->get_value_range (name
);
2078 if (vr
->kind () == VR_RANGE
2079 && (TREE_CODE (vr
->min ()) == SSA_NAME
2080 || is_gimple_min_invariant (vr
->min ()))
2081 && vrp_operand_equal_p (vr
->min (), vr
->max ()))
2087 /* Return the singleton value-range for NAME if that is a constant
2088 but signal to not follow SSA edges. */
2091 vrp_valueize_1 (tree name
)
2093 if (TREE_CODE (name
) == SSA_NAME
)
2095 /* If the definition may be simulated again we cannot follow
2096 this SSA edge as the SSA propagator does not necessarily
2097 re-visit the use. */
2098 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
2099 if (!gimple_nop_p (def_stmt
)
2100 && prop_simulate_again_p (def_stmt
))
2102 const value_range_equiv
*vr
= x_vr_values
->get_value_range (name
);
2104 if (vr
->singleton_p (&singleton
))
2110 /* Given STMT, an assignment or call, return its LHS if the type
2111 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
2114 get_output_for_vrp (gimple
*stmt
)
2116 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2119 /* We only keep track of ranges in integral and pointer types. */
2120 tree lhs
= gimple_get_lhs (stmt
);
2121 if (TREE_CODE (lhs
) == SSA_NAME
2122 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2123 /* It is valid to have NULL MIN/MAX values on a type. See
2124 build_range_type. */
2125 && TYPE_MIN_VALUE (TREE_TYPE (lhs
))
2126 && TYPE_MAX_VALUE (TREE_TYPE (lhs
)))
2127 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
2133 /* Visit assignment STMT. If it produces an interesting range, record
2134 the range in VR and set LHS to OUTPUT_P. */
2137 vr_values::vrp_visit_assignment_or_call (gimple
*stmt
, tree
*output_p
,
2138 value_range_equiv
*vr
)
2140 tree lhs
= get_output_for_vrp (stmt
);
2143 /* We only keep track of ranges in integral and pointer types. */
2146 enum gimple_code code
= gimple_code (stmt
);
2148 /* Try folding the statement to a constant first. */
2150 tree tem
= gimple_fold_stmt_to_constant_1 (stmt
, vrp_valueize
,
2155 if (TREE_CODE (tem
) == SSA_NAME
2156 && (SSA_NAME_IS_DEFAULT_DEF (tem
)
2157 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem
))))
2159 extract_range_from_ssa_name (vr
, tem
);
2162 else if (is_gimple_min_invariant (tem
))
2168 /* Then dispatch to value-range extracting functions. */
2169 if (code
== GIMPLE_CALL
)
2170 extract_range_basic (vr
, stmt
);
2172 extract_range_from_assignment (vr
, as_a
<gassign
*> (stmt
));
2176 /* Helper that gets the value range of the SSA_NAME with version I
2177 or a symbolic range containing the SSA_NAME only if the value range
2178 is varying or undefined. Uses TEM as storage for the alternate range. */
2180 const value_range_equiv
*
2181 simplify_using_ranges::get_vr_for_comparison (int i
, value_range_equiv
*tem
)
2183 /* Shallow-copy equiv bitmap. */
2184 const value_range_equiv
*vr
= query
->get_value_range (ssa_name (i
));
2186 /* If name N_i does not have a valid range, use N_i as its own
2187 range. This allows us to compare against names that may
2188 have N_i in their ranges. */
2189 if (vr
->varying_p () || vr
->undefined_p ())
2191 tem
->set (ssa_name (i
));
2198 /* Compare all the value ranges for names equivalent to VAR with VAL
2199 using comparison code COMP. Return the same value returned by
2200 compare_range_with_value, including the setting of
2201 *STRICT_OVERFLOW_P. */
2204 simplify_using_ranges::compare_name_with_value
2205 (enum tree_code comp
, tree var
, tree val
,
2206 bool *strict_overflow_p
, bool use_equiv_p
)
2208 /* Get the set of equivalences for VAR. */
2209 bitmap e
= query
->get_value_range (var
)->equiv ();
2211 /* Start at -1. Set it to 0 if we do a comparison without relying
2212 on overflow, or 1 if all comparisons rely on overflow. */
2213 int used_strict_overflow
= -1;
2215 /* Compare vars' value range with val. */
2216 value_range_equiv tem_vr
;
2217 const value_range_equiv
*equiv_vr
2218 = get_vr_for_comparison (SSA_NAME_VERSION (var
), &tem_vr
);
2220 tree retval
= compare_range_with_value (comp
, equiv_vr
, val
, &sop
);
2222 used_strict_overflow
= sop
? 1 : 0;
2224 /* If the equiv set is empty we have done all work we need to do. */
2227 if (retval
&& used_strict_overflow
> 0)
2228 *strict_overflow_p
= true;
2234 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2236 tree name
= ssa_name (i
);
2241 && !SSA_NAME_IS_DEFAULT_DEF (name
)
2242 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name
)))
2245 equiv_vr
= get_vr_for_comparison (i
, &tem_vr
);
2247 tree t
= compare_range_with_value (comp
, equiv_vr
, val
, &sop
);
2250 /* If we get different answers from different members
2251 of the equivalence set this check must be in a dead
2252 code region. Folding it to a trap representation
2253 would be correct here. For now just return don't-know. */
2263 used_strict_overflow
= 0;
2264 else if (used_strict_overflow
< 0)
2265 used_strict_overflow
= 1;
2269 if (retval
&& used_strict_overflow
> 0)
2270 *strict_overflow_p
= true;
2276 /* Given a comparison code COMP and names N1 and N2, compare all the
2277 ranges equivalent to N1 against all the ranges equivalent to N2
2278 to determine the value of N1 COMP N2. Return the same value
2279 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2280 whether we relied on undefined signed overflow in the comparison. */
2284 simplify_using_ranges::compare_names (enum tree_code comp
, tree n1
, tree n2
,
2285 bool *strict_overflow_p
)
2287 /* Compare the ranges of every name equivalent to N1 against the
2288 ranges of every name equivalent to N2. */
2289 bitmap e1
= query
->get_value_range (n1
)->equiv ();
2290 bitmap e2
= query
->get_value_range (n2
)->equiv ();
2292 /* Use the fake bitmaps if e1 or e2 are not available. */
2293 static bitmap s_e1
= NULL
, s_e2
= NULL
;
2294 static bitmap_obstack
*s_obstack
= NULL
;
2295 if (s_obstack
== NULL
)
2297 s_obstack
= XNEW (bitmap_obstack
);
2298 bitmap_obstack_initialize (s_obstack
);
2299 s_e1
= BITMAP_ALLOC (s_obstack
);
2300 s_e2
= BITMAP_ALLOC (s_obstack
);
2307 /* Add N1 and N2 to their own set of equivalences to avoid
2308 duplicating the body of the loop just to check N1 and N2
2310 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2311 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2313 /* If the equivalence sets have a common intersection, then the two
2314 names can be compared without checking their ranges. */
2315 if (bitmap_intersect_p (e1
, e2
))
2317 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2318 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2320 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2322 : boolean_false_node
;
2325 /* Start at -1. Set it to 0 if we do a comparison without relying
2326 on overflow, or 1 if all comparisons rely on overflow. */
2327 int used_strict_overflow
= -1;
2329 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2330 N2 to their own set of equivalences to avoid duplicating the body
2331 of the loop just to check N1 and N2 ranges. */
2332 bitmap_iterator bi1
;
2334 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2339 value_range_equiv tem_vr1
;
2340 const value_range_equiv
*vr1
= get_vr_for_comparison (i1
, &tem_vr1
);
2342 tree t
= NULL_TREE
, retval
= NULL_TREE
;
2343 bitmap_iterator bi2
;
2345 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2352 value_range_equiv tem_vr2
;
2353 const value_range_equiv
*vr2
= get_vr_for_comparison (i2
, &tem_vr2
);
2355 t
= compare_ranges (comp
, vr1
, vr2
, &sop
);
2358 /* If we get different answers from different members
2359 of the equivalence set this check must be in a dead
2360 code region. Folding it to a trap representation
2361 would be correct here. For now just return don't-know. */
2362 if (retval
!= NULL
&& t
!= retval
)
2364 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2365 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2371 used_strict_overflow
= 0;
2372 else if (used_strict_overflow
< 0)
2373 used_strict_overflow
= 1;
2379 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2380 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2381 if (used_strict_overflow
> 0)
2382 *strict_overflow_p
= true;
2387 /* None of the equivalent ranges are useful in computing this
2389 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2390 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2394 /* Helper function for vrp_evaluate_conditional_warnv & other
2398 simplify_using_ranges::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2399 (enum tree_code code
, tree op0
, tree op1
, bool * strict_overflow_p
)
2401 const value_range_equiv
*vr0
, *vr1
;
2402 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? query
->get_value_range (op0
) : NULL
;
2403 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? query
->get_value_range (op1
) : NULL
;
2405 tree res
= NULL_TREE
;
2407 res
= compare_ranges (code
, vr0
, vr1
, strict_overflow_p
);
2409 res
= compare_range_with_value (code
, vr0
, op1
, strict_overflow_p
);
2411 res
= (compare_range_with_value
2412 (swap_tree_comparison (code
), vr1
, op0
, strict_overflow_p
));
2416 /* Helper function for vrp_evaluate_conditional_warnv. */
2419 simplify_using_ranges::vrp_evaluate_conditional_warnv_with_ops
2421 enum tree_code code
,
2424 bool *strict_overflow_p
,
2429 *only_ranges
= true;
2431 /* We only deal with integral and pointer types. */
2432 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2433 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
2436 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2437 as a simple equality test, then prefer that over its current form
2440 An overflow test which collapses to an equality test can always be
2441 expressed as a comparison of one argument against zero. Overflow
2442 occurs when the chosen argument is zero and does not occur if the
2443 chosen argument is not zero. */
2445 if (overflow_comparison_p (code
, op0
, op1
, use_equiv_p
, &x
))
2447 wide_int max
= wi::max_value (TYPE_PRECISION (TREE_TYPE (op0
)), UNSIGNED
);
2448 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2449 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2450 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2451 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2452 if (integer_zerop (x
))
2455 code
= (code
== LT_EXPR
|| code
== LE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2457 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2458 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2459 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2460 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2461 else if (wi::to_wide (x
) == max
- 1)
2464 op1
= wide_int_to_tree (TREE_TYPE (op0
), 0);
2465 code
= (code
== GT_EXPR
|| code
== GE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2469 value_range vro
, vri
;
2470 if (code
== GT_EXPR
|| code
== GE_EXPR
)
2472 vro
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
, VR_ANTI_RANGE
);
2473 vri
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2475 else if (code
== LT_EXPR
|| code
== LE_EXPR
)
2477 vro
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2478 vri
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
, VR_ANTI_RANGE
);
2482 const value_range_equiv
*vr0
= query
->get_value_range (op0
, stmt
);
2483 /* If vro, the range for OP0 to pass the overflow test, has
2484 no intersection with *vr0, OP0's known range, then the
2485 overflow test can't pass, so return the node for false.
2486 If it is the inverted range, vri, that has no
2487 intersection, then the overflow test must pass, so return
2488 the node for true. In other cases, we could proceed with
2489 a simplified condition comparing OP0 and X, with LE_EXPR
2490 for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
2491 the comments next to the enclosing if suggest it's not
2492 generally profitable to do so. */
2493 vro
.intersect (vr0
);
2494 if (vro
.undefined_p ())
2495 return boolean_false_node
;
2496 vri
.intersect (vr0
);
2497 if (vri
.undefined_p ())
2498 return boolean_true_node
;
2502 if ((ret
= vrp_evaluate_conditional_warnv_with_ops_using_ranges
2503 (code
, op0
, op1
, strict_overflow_p
)))
2506 *only_ranges
= false;
2507 /* Do not use compare_names during propagation, it's quadratic. */
2508 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
2510 return compare_names (code
, op0
, op1
, strict_overflow_p
);
2511 else if (TREE_CODE (op0
) == SSA_NAME
)
2512 return compare_name_with_value (code
, op0
, op1
,
2513 strict_overflow_p
, use_equiv_p
);
2514 else if (TREE_CODE (op1
) == SSA_NAME
)
2515 return compare_name_with_value (swap_tree_comparison (code
), op1
, op0
,
2516 strict_overflow_p
, use_equiv_p
);
2520 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2521 information. Return NULL if the conditional cannot be evaluated.
2522 The ranges of all the names equivalent with the operands in COND
2523 will be used when trying to compute the value. If the result is
2524 based on undefined signed overflow, issue a warning if
2528 simplify_using_ranges::vrp_evaluate_conditional (tree_code code
, tree op0
,
2529 tree op1
, gimple
*stmt
)
2535 /* Some passes and foldings leak constants with overflow flag set
2536 into the IL. Avoid doing wrong things with these and bail out. */
2537 if ((TREE_CODE (op0
) == INTEGER_CST
2538 && TREE_OVERFLOW (op0
))
2539 || (TREE_CODE (op1
) == INTEGER_CST
2540 && TREE_OVERFLOW (op1
)))
2544 ret
= vrp_evaluate_conditional_warnv_with_ops (stmt
, code
, op0
, op1
, true,
2545 &sop
, &only_ranges
);
2549 enum warn_strict_overflow_code wc
;
2550 const char* warnmsg
;
2552 if (is_gimple_min_invariant (ret
))
2554 wc
= WARN_STRICT_OVERFLOW_CONDITIONAL
;
2555 warnmsg
= G_("assuming signed overflow does not occur when "
2556 "simplifying conditional to constant");
2560 wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
2561 warnmsg
= G_("assuming signed overflow does not occur when "
2562 "simplifying conditional");
2565 if (issue_strict_overflow_warning (wc
))
2567 location_t location
;
2569 if (!gimple_has_location (stmt
))
2570 location
= input_location
;
2572 location
= gimple_location (stmt
);
2573 warning_at (location
, OPT_Wstrict_overflow
, "%s", warnmsg
);
2577 if (warn_type_limits
2578 && ret
&& only_ranges
2579 && TREE_CODE_CLASS (code
) == tcc_comparison
2580 && TREE_CODE (op0
) == SSA_NAME
)
2582 /* If the comparison is being folded and the operand on the LHS
2583 is being compared against a constant value that is outside of
2584 the natural range of OP0's type, then the predicate will
2585 always fold regardless of the value of OP0. If -Wtype-limits
2586 was specified, emit a warning. */
2587 tree type
= TREE_TYPE (op0
);
2588 const value_range_equiv
*vr0
= query
->get_value_range (op0
, stmt
);
2590 if (vr0
->varying_p ()
2591 && INTEGRAL_TYPE_P (type
)
2592 && is_gimple_min_invariant (op1
))
2594 location_t location
;
2596 if (!gimple_has_location (stmt
))
2597 location
= input_location
;
2599 location
= gimple_location (stmt
);
2601 warning_at (location
, OPT_Wtype_limits
,
2603 ? G_("comparison always false "
2604 "due to limited range of data type")
2605 : G_("comparison always true "
2606 "due to limited range of data type"));
2614 /* Visit conditional statement STMT. If we can determine which edge
2615 will be taken out of STMT's basic block, record it in
2616 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2619 simplify_using_ranges::vrp_visit_cond_stmt (gcond
*stmt
, edge
*taken_edge_p
)
2623 *taken_edge_p
= NULL
;
2625 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2630 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
2631 print_gimple_stmt (dump_file
, stmt
, 0);
2632 fprintf (dump_file
, "\nWith known ranges\n");
2634 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
2636 fprintf (dump_file
, "\t");
2637 print_generic_expr (dump_file
, use
);
2638 fprintf (dump_file
, ": ");
2639 dump_value_range (dump_file
, query
->get_value_range (use
, stmt
));
2642 fprintf (dump_file
, "\n");
2645 /* Compute the value of the predicate COND by checking the known
2646 ranges of each of its operands.
2648 Note that we cannot evaluate all the equivalent ranges here
2649 because those ranges may not yet be final and with the current
2650 propagation strategy, we cannot determine when the value ranges
2651 of the names in the equivalence set have changed.
2653 For instance, given the following code fragment
2657 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2661 Assume that on the first visit to i_14, i_5 has the temporary
2662 range [8, 8] because the second argument to the PHI function is
2663 not yet executable. We derive the range ~[0, 0] for i_14 and the
2664 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2665 the first time, since i_14 is equivalent to the range [8, 8], we
2666 determine that the predicate is always false.
2668 On the next round of propagation, i_13 is determined to be
2669 VARYING, which causes i_5 to drop down to VARYING. So, another
2670 visit to i_14 is scheduled. In this second visit, we compute the
2671 exact same range and equivalence set for i_14, namely ~[0, 0] and
2672 { i_5 }. But we did not have the previous range for i_5
2673 registered, so vrp_visit_assignment thinks that the range for
2674 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2675 is not visited again, which stops propagation from visiting
2676 statements in the THEN clause of that if().
2678 To properly fix this we would need to keep the previous range
2679 value for the names in the equivalence set. This way we would've
2680 discovered that from one visit to the other i_5 changed from
2681 range [8, 8] to VR_VARYING.
2683 However, fixing this apparent limitation may not be worth the
2684 additional checking. Testing on several code bases (GCC, DLV,
2685 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2686 4 more predicates folded in SPEC. */
2689 val
= vrp_evaluate_conditional_warnv_with_ops (stmt
,
2690 gimple_cond_code (stmt
),
2691 gimple_cond_lhs (stmt
),
2692 gimple_cond_rhs (stmt
),
2695 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
2697 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2699 fprintf (dump_file
, "\nPredicate evaluates to: ");
2700 if (val
== NULL_TREE
)
2701 fprintf (dump_file
, "DON'T KNOW\n");
2703 print_generic_stmt (dump_file
, val
);
2707 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2708 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2709 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2710 Returns true if the default label is not needed. */
2713 find_case_label_ranges (gswitch
*stmt
, const value_range
*vr
,
2714 size_t *min_idx1
, size_t *max_idx1
,
2715 size_t *min_idx2
, size_t *max_idx2
)
2718 unsigned int n
= gimple_switch_num_labels (stmt
);
2720 tree case_low
, case_high
;
2721 tree min
= vr
->min (), max
= vr
->max ();
2723 gcc_checking_assert (!vr
->varying_p () && !vr
->undefined_p ());
2725 take_default
= !find_case_label_range (stmt
, min
, max
, &i
, &j
);
2727 /* Set second range to empty. */
2731 if (vr
->kind () == VR_RANGE
)
2735 return !take_default
;
2738 /* Set first range to all case labels. */
2745 /* Make sure all the values of case labels [i , j] are contained in
2746 range [MIN, MAX]. */
2747 case_low
= CASE_LOW (gimple_switch_label (stmt
, i
));
2748 case_high
= CASE_HIGH (gimple_switch_label (stmt
, j
));
2749 if (tree_int_cst_compare (case_low
, min
) < 0)
2751 if (case_high
!= NULL_TREE
2752 && tree_int_cst_compare (max
, case_high
) < 0)
2758 /* If the range spans case labels [i, j], the corresponding anti-range spans
2759 the labels [1, i - 1] and [j + 1, n - 1]. */
2785 /* Visit switch statement STMT. If we can determine which edge
2786 will be taken out of STMT's basic block, record it in
2787 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2790 vr_values::vrp_visit_switch_stmt (gswitch
*stmt
, edge
*taken_edge_p
)
2793 const value_range_equiv
*vr
;
2794 size_t i
= 0, j
= 0, k
, l
;
2797 *taken_edge_p
= NULL
;
2798 op
= gimple_switch_index (stmt
);
2799 if (TREE_CODE (op
) != SSA_NAME
)
2802 vr
= get_value_range (op
);
2803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2805 fprintf (dump_file
, "\nVisiting switch expression with operand ");
2806 print_generic_expr (dump_file
, op
);
2807 fprintf (dump_file
, " with known range ");
2808 dump_value_range (dump_file
, vr
);
2809 fprintf (dump_file
, "\n");
2812 if (vr
->undefined_p ()
2814 || vr
->symbolic_p ())
2817 /* Find the single edge that is taken from the switch expression. */
2818 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
2820 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2824 gcc_assert (take_default
);
2825 val
= gimple_switch_default_label (stmt
);
2829 /* Check if labels with index i to j and maybe the default label
2830 are all reaching the same label. */
2832 val
= gimple_switch_label (stmt
, i
);
2834 && CASE_LABEL (gimple_switch_default_label (stmt
))
2835 != CASE_LABEL (val
))
2837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2838 fprintf (dump_file
, " not a single destination for this "
2842 for (++i
; i
<= j
; ++i
)
2844 if (CASE_LABEL (gimple_switch_label (stmt
, i
)) != CASE_LABEL (val
))
2846 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2847 fprintf (dump_file
, " not a single destination for this "
2854 if (CASE_LABEL (gimple_switch_label (stmt
, k
)) != CASE_LABEL (val
))
2856 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2857 fprintf (dump_file
, " not a single destination for this "
2864 *taken_edge_p
= find_edge (gimple_bb (stmt
),
2865 label_to_block (cfun
, CASE_LABEL (val
)));
2867 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2869 fprintf (dump_file
, " will take edge to ");
2870 print_generic_stmt (dump_file
, CASE_LABEL (val
));
2875 /* Evaluate statement STMT. If the statement produces a useful range,
2876 set VR and corepsponding OUTPUT_P.
2878 If STMT is a conditional branch and we can determine its truth
2879 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2882 vr_values::extract_range_from_stmt (gimple
*stmt
, edge
*taken_edge_p
,
2883 tree
*output_p
, value_range_equiv
*vr
)
2886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2888 fprintf (dump_file
, "\nextract_range_from_stmt visiting:\n");
2889 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
2892 if (!stmt_interesting_for_vrp (stmt
))
2893 gcc_assert (stmt_ends_bb_p (stmt
));
2894 else if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
2895 vrp_visit_assignment_or_call (stmt
, output_p
, vr
);
2896 else if (gimple_code (stmt
) == GIMPLE_COND
)
2897 simplifier
.vrp_visit_cond_stmt (as_a
<gcond
*> (stmt
), taken_edge_p
);
2898 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2899 vrp_visit_switch_stmt (as_a
<gswitch
*> (stmt
), taken_edge_p
);
2902 /* Visit all arguments for PHI node PHI that flow through executable
2903 edges. If a valid value range can be derived from all the incoming
2904 value ranges, set a new range in VR_RESULT. */
2907 vr_values::extract_range_from_phi_node (gphi
*phi
,
2908 value_range_equiv
*vr_result
)
2910 tree lhs
= PHI_RESULT (phi
);
2911 const value_range_equiv
*lhs_vr
= get_value_range (lhs
);
2916 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2918 fprintf (dump_file
, "\nVisiting PHI node: ");
2919 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
2922 bool may_simulate_backedge_again
= false;
2924 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2926 edge e
= gimple_phi_arg_edge (phi
, i
);
2928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2931 " Argument #%d (%d -> %d %sexecutable)\n",
2932 (int) i
, e
->src
->index
, e
->dest
->index
,
2933 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
2936 if (e
->flags
& EDGE_EXECUTABLE
)
2938 value_range_equiv vr_arg_tem
;
2939 const value_range_equiv
*vr_arg
= &vr_arg_tem
;
2943 tree arg
= PHI_ARG_DEF (phi
, i
);
2944 if (TREE_CODE (arg
) == SSA_NAME
)
2946 /* See if we are eventually going to change one of the args. */
2947 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
2948 if (! gimple_nop_p (def_stmt
)
2949 && prop_simulate_again_p (def_stmt
)
2950 && e
->flags
& EDGE_DFS_BACK
)
2951 may_simulate_backedge_again
= true;
2953 const value_range_equiv
*vr_arg_
= get_value_range (arg
);
2954 /* Do not allow equivalences or symbolic ranges to leak in from
2955 backedges. That creates invalid equivalencies.
2956 See PR53465 and PR54767. */
2957 if (e
->flags
& EDGE_DFS_BACK
)
2959 if (!vr_arg_
->varying_p () && !vr_arg_
->undefined_p ())
2961 vr_arg_tem
.set (vr_arg_
->min (), vr_arg_
->max (), NULL
,
2963 if (vr_arg_tem
.symbolic_p ())
2964 vr_arg_tem
.set_varying (TREE_TYPE (arg
));
2969 /* If the non-backedge arguments range is VR_VARYING then
2970 we can still try recording a simple equivalence. */
2971 else if (vr_arg_
->varying_p ())
2972 vr_arg_tem
.set (arg
);
2978 if (TREE_OVERFLOW_P (arg
))
2979 arg
= drop_tree_overflow (arg
);
2981 vr_arg_tem
.set (arg
);
2984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2986 fprintf (dump_file
, "\t");
2987 print_generic_expr (dump_file
, arg
, dump_flags
);
2988 fprintf (dump_file
, ": ");
2989 dump_value_range (dump_file
, vr_arg
);
2990 fprintf (dump_file
, "\n");
2994 vr_result
->deep_copy (vr_arg
);
2996 vr_result
->union_ (vr_arg
);
2999 if (vr_result
->varying_p ())
3004 if (vr_result
->varying_p ())
3006 else if (vr_result
->undefined_p ())
3009 old_edges
= vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)];
3010 vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)] = edges
;
3012 /* To prevent infinite iterations in the algorithm, derive ranges
3013 when the new value is slightly bigger or smaller than the
3014 previous one. We don't do this if we have seen a new executable
3015 edge; this helps us avoid an infinity for conditionals
3016 which are not in a loop. If the old value-range was VR_UNDEFINED
3017 use the updated range and iterate one more time. If we will not
3018 simulate this PHI again via the backedge allow us to iterate. */
3020 && gimple_phi_num_args (phi
) > 1
3021 && edges
== old_edges
3022 && !lhs_vr
->undefined_p ()
3023 && may_simulate_backedge_again
)
3025 /* Compare old and new ranges, fall back to varying if the
3026 values are not comparable. */
3027 int cmp_min
= compare_values (lhs_vr
->min (), vr_result
->min ());
3030 int cmp_max
= compare_values (lhs_vr
->max (), vr_result
->max ());
3034 /* For non VR_RANGE or for pointers fall back to varying if
3035 the range changed. */
3036 if ((lhs_vr
->kind () != VR_RANGE
|| vr_result
->kind () != VR_RANGE
3037 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
3038 && (cmp_min
!= 0 || cmp_max
!= 0))
3041 /* If the new minimum is larger than the previous one
3042 retain the old value. If the new minimum value is smaller
3043 than the previous one and not -INF go all the way to -INF + 1.
3044 In the first case, to avoid infinite bouncing between different
3045 minimums, and in the other case to avoid iterating millions of
3046 times to reach -INF. Going to -INF + 1 also lets the following
3047 iteration compute whether there will be any overflow, at the
3048 expense of one additional iteration. */
3049 tree new_min
= vr_result
->min ();
3050 tree new_max
= vr_result
->max ();
3052 new_min
= lhs_vr
->min ();
3053 else if (cmp_min
> 0
3054 && (TREE_CODE (vr_result
->min ()) != INTEGER_CST
3055 || tree_int_cst_lt (vrp_val_min (vr_result
->type ()),
3056 vr_result
->min ())))
3057 new_min
= int_const_binop (PLUS_EXPR
,
3058 vrp_val_min (vr_result
->type ()),
3059 build_int_cst (vr_result
->type (), 1));
3061 /* Similarly for the maximum value. */
3063 new_max
= lhs_vr
->max ();
3064 else if (cmp_max
< 0
3065 && (TREE_CODE (vr_result
->max ()) != INTEGER_CST
3066 || tree_int_cst_lt (vr_result
->max (),
3067 vrp_val_max (vr_result
->type ()))))
3068 new_max
= int_const_binop (MINUS_EXPR
,
3069 vrp_val_max (vr_result
->type ()),
3070 build_int_cst (vr_result
->type (), 1));
3072 vr_result
->update (new_min
, new_max
, vr_result
->kind ());
3074 /* If we dropped either bound to +-INF then if this is a loop
3075 PHI node SCEV may known more about its value-range. */
3076 if (cmp_min
> 0 || cmp_min
< 0
3077 || cmp_max
< 0 || cmp_max
> 0)
3080 goto infinite_check
;
3086 vr_result
->set_varying (TREE_TYPE (lhs
));
3089 /* If this is a loop PHI node SCEV may known more about its value-range.
3090 scev_check can be reached from two paths, one is a fall through from above
3091 "varying" label, the other is direct goto from code block which tries to
3092 avoid infinite simulation. */
3093 if (scev_initialized_p ()
3094 && (l
= loop_containing_stmt (phi
))
3095 && l
->header
== gimple_bb (phi
))
3096 adjust_range_with_scev (vr_result
, l
, phi
, lhs
);
3099 /* If we will end up with a (-INF, +INF) range, set it to
3100 VARYING. Same if the previous max value was invalid for
3101 the type and we end up with vr_result.min > vr_result.max. */
3102 if ((!vr_result
->varying_p () && !vr_result
->undefined_p ())
3103 && !((vrp_val_is_max (vr_result
->max ()) && vrp_val_is_min (vr_result
->min ()))
3104 || compare_values (vr_result
->min (), vr_result
->max ()) > 0))
3107 vr_result
->set_varying (TREE_TYPE (lhs
));
3109 /* If the new range is different than the previous value, keep
3115 /* Simplify boolean operations if the source is known
3116 to be already a boolean. */
3118 simplify_using_ranges::simplify_truth_ops_using_ranges
3119 (gimple_stmt_iterator
*gsi
,
3122 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3124 bool need_conversion
;
3126 /* We handle only !=/== case here. */
3127 gcc_assert (rhs_code
== EQ_EXPR
|| rhs_code
== NE_EXPR
);
3129 op0
= gimple_assign_rhs1 (stmt
);
3130 if (!op_with_boolean_value_range_p (op0
))
3133 op1
= gimple_assign_rhs2 (stmt
);
3134 if (!op_with_boolean_value_range_p (op1
))
3137 /* Reduce number of cases to handle to NE_EXPR. As there is no
3138 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
3139 if (rhs_code
== EQ_EXPR
)
3141 if (TREE_CODE (op1
) == INTEGER_CST
)
3142 op1
= int_const_binop (BIT_XOR_EXPR
, op1
,
3143 build_int_cst (TREE_TYPE (op1
), 1));
3148 lhs
= gimple_assign_lhs (stmt
);
3150 = !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
));
3152 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
3154 && !TYPE_UNSIGNED (TREE_TYPE (op0
))
3155 && TYPE_PRECISION (TREE_TYPE (op0
)) == 1
3156 && TYPE_PRECISION (TREE_TYPE (lhs
)) > 1)
3159 /* For A != 0 we can substitute A itself. */
3160 if (integer_zerop (op1
))
3161 gimple_assign_set_rhs_with_ops (gsi
,
3163 ? NOP_EXPR
: TREE_CODE (op0
), op0
);
3164 /* For A != B we substitute A ^ B. Either with conversion. */
3165 else if (need_conversion
)
3167 tree tem
= make_ssa_name (TREE_TYPE (op0
));
3169 = gimple_build_assign (tem
, BIT_XOR_EXPR
, op0
, op1
);
3170 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
3171 if (INTEGRAL_TYPE_P (TREE_TYPE (tem
))
3172 && TYPE_PRECISION (TREE_TYPE (tem
)) > 1)
3173 set_range_info (tem
, VR_RANGE
,
3174 wi::zero (TYPE_PRECISION (TREE_TYPE (tem
))),
3175 wi::one (TYPE_PRECISION (TREE_TYPE (tem
))));
3176 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, tem
);
3180 gimple_assign_set_rhs_with_ops (gsi
, BIT_XOR_EXPR
, op0
, op1
);
3181 update_stmt (gsi_stmt (*gsi
));
3182 fold_stmt (gsi
, follow_single_use_edges
);
3187 /* Simplify a division or modulo operator to a right shift or bitwise and
3188 if the first operand is unsigned or is greater than zero and the second
3189 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
3190 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
3191 optimize it into just op0 if op0's range is known to be a subset of
3192 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3196 simplify_using_ranges::simplify_div_or_mod_using_ranges
3197 (gimple_stmt_iterator
*gsi
,
3200 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3202 tree op0
= gimple_assign_rhs1 (stmt
);
3203 tree op1
= gimple_assign_rhs2 (stmt
);
3204 tree op0min
= NULL_TREE
, op0max
= NULL_TREE
;
3206 const value_range
*vr
= NULL
;
3208 if (TREE_CODE (op0
) == INTEGER_CST
)
3215 vr
= query
->get_value_range (op0
, stmt
);
3216 if (range_int_cst_p (vr
))
3218 op0min
= vr
->min ();
3219 op0max
= vr
->max ();
3223 if (rhs_code
== TRUNC_MOD_EXPR
3224 && TREE_CODE (op1
) == SSA_NAME
)
3226 const value_range_equiv
*vr1
= query
->get_value_range (op1
, stmt
);
3227 if (range_int_cst_p (vr1
))
3228 op1min
= vr1
->min ();
3230 if (rhs_code
== TRUNC_MOD_EXPR
3231 && TREE_CODE (op1min
) == INTEGER_CST
3232 && tree_int_cst_sgn (op1min
) == 1
3234 && tree_int_cst_lt (op0max
, op1min
))
3236 if (TYPE_UNSIGNED (TREE_TYPE (op0
))
3237 || tree_int_cst_sgn (op0min
) >= 0
3238 || tree_int_cst_lt (fold_unary (NEGATE_EXPR
, TREE_TYPE (op1min
), op1min
),
3241 /* If op0 already has the range op0 % op1 has,
3242 then TRUNC_MOD_EXPR won't change anything. */
3243 gimple_assign_set_rhs_from_tree (gsi
, op0
);
3248 if (TREE_CODE (op0
) != SSA_NAME
)
3251 if (!integer_pow2p (op1
))
3253 /* X % -Y can be only optimized into X % Y either if
3254 X is not INT_MIN, or Y is not -1. Fold it now, as after
3255 remove_range_assertions the range info might be not available
3257 if (rhs_code
== TRUNC_MOD_EXPR
3258 && fold_stmt (gsi
, follow_single_use_edges
))
3263 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
3264 val
= integer_one_node
;
3269 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
3273 && integer_onep (val
)
3274 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3276 location_t location
;
3278 if (!gimple_has_location (stmt
))
3279 location
= input_location
;
3281 location
= gimple_location (stmt
);
3282 warning_at (location
, OPT_Wstrict_overflow
,
3283 "assuming signed overflow does not occur when "
3284 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3288 if (val
&& integer_onep (val
))
3292 if (rhs_code
== TRUNC_DIV_EXPR
)
3294 t
= build_int_cst (integer_type_node
, tree_log2 (op1
));
3295 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
3296 gimple_assign_set_rhs1 (stmt
, op0
);
3297 gimple_assign_set_rhs2 (stmt
, t
);
3301 t
= build_int_cst (TREE_TYPE (op1
), 1);
3302 t
= int_const_binop (MINUS_EXPR
, op1
, t
);
3303 t
= fold_convert (TREE_TYPE (op0
), t
);
3305 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
3306 gimple_assign_set_rhs1 (stmt
, op0
);
3307 gimple_assign_set_rhs2 (stmt
, t
);
3311 fold_stmt (gsi
, follow_single_use_edges
);
3318 /* Simplify a min or max if the ranges of the two operands are
3319 disjoint. Return true if we do simplify. */
3322 simplify_using_ranges::simplify_min_or_max_using_ranges
3323 (gimple_stmt_iterator
*gsi
,
3326 tree op0
= gimple_assign_rhs1 (stmt
);
3327 tree op1
= gimple_assign_rhs2 (stmt
);
3331 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3332 (LE_EXPR
, op0
, op1
, &sop
));
3336 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3337 (LT_EXPR
, op0
, op1
, &sop
));
3342 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3344 location_t location
;
3346 if (!gimple_has_location (stmt
))
3347 location
= input_location
;
3349 location
= gimple_location (stmt
);
3350 warning_at (location
, OPT_Wstrict_overflow
,
3351 "assuming signed overflow does not occur when "
3352 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3355 /* VAL == TRUE -> OP0 < or <= op1
3356 VAL == FALSE -> OP0 > or >= op1. */
3357 tree res
= ((gimple_assign_rhs_code (stmt
) == MAX_EXPR
)
3358 == integer_zerop (val
)) ? op0
: op1
;
3359 gimple_assign_set_rhs_from_tree (gsi
, res
);
3366 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3367 ABS_EXPR. If the operand is <= 0, then simplify the
3368 ABS_EXPR into a NEGATE_EXPR. */
3371 simplify_using_ranges::simplify_abs_using_ranges (gimple_stmt_iterator
*gsi
,
3374 tree op
= gimple_assign_rhs1 (stmt
);
3375 const value_range
*vr
= query
->get_value_range (op
, stmt
);
3382 val
= compare_range_with_value (LE_EXPR
, vr
, integer_zero_node
, &sop
);
3385 /* The range is neither <= 0 nor > 0. Now see if it is
3386 either < 0 or >= 0. */
3388 val
= compare_range_with_value (LT_EXPR
, vr
, integer_zero_node
,
3394 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3396 location_t location
;
3398 if (!gimple_has_location (stmt
))
3399 location
= input_location
;
3401 location
= gimple_location (stmt
);
3402 warning_at (location
, OPT_Wstrict_overflow
,
3403 "assuming signed overflow does not occur when "
3404 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3407 gimple_assign_set_rhs1 (stmt
, op
);
3408 if (integer_zerop (val
))
3409 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
3411 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
3413 fold_stmt (gsi
, follow_single_use_edges
);
3421 /* value_range wrapper for wi_set_zero_nonzero_bits.
3423 Return TRUE if VR was a constant range and we were able to compute
3427 vr_set_zero_nonzero_bits (const tree expr_type
,
3428 const value_range
*vr
,
3429 wide_int
*may_be_nonzero
,
3430 wide_int
*must_be_nonzero
)
3432 if (range_int_cst_p (vr
))
3434 wi_set_zero_nonzero_bits (expr_type
,
3435 wi::to_wide (vr
->min ()),
3436 wi::to_wide (vr
->max ()),
3437 *may_be_nonzero
, *must_be_nonzero
);
3440 *may_be_nonzero
= wi::minus_one (TYPE_PRECISION (expr_type
));
3441 *must_be_nonzero
= wi::zero (TYPE_PRECISION (expr_type
));
3445 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3446 If all the bits that are being cleared by & are already
3447 known to be zero from VR, or all the bits that are being
3448 set by | are already known to be one from VR, the bit
3449 operation is redundant. */
3452 simplify_using_ranges::simplify_bit_ops_using_ranges
3453 (gimple_stmt_iterator
*gsi
,
3456 tree op0
= gimple_assign_rhs1 (stmt
);
3457 tree op1
= gimple_assign_rhs2 (stmt
);
3458 tree op
= NULL_TREE
;
3459 value_range vr0
, vr1
;
3460 wide_int may_be_nonzero0
, may_be_nonzero1
;
3461 wide_int must_be_nonzero0
, must_be_nonzero1
;
3464 if (TREE_CODE (op0
) == SSA_NAME
)
3465 vr0
= *(query
->get_value_range (op0
, stmt
));
3466 else if (is_gimple_min_invariant (op0
))
3471 if (TREE_CODE (op1
) == SSA_NAME
)
3472 vr1
= *(query
->get_value_range (op1
, stmt
));
3473 else if (is_gimple_min_invariant (op1
))
3478 if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0
), &vr0
, &may_be_nonzero0
,
3481 if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1
), &vr1
, &may_be_nonzero1
,
3485 switch (gimple_assign_rhs_code (stmt
))
3488 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3494 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3502 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3508 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3519 if (op
== NULL_TREE
)
3522 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (op
), op
);
3523 update_stmt (gsi_stmt (*gsi
));
3527 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3528 a known value range VR.
3530 If there is one and only one value which will satisfy the
3531 conditional, then return that value. Else return NULL.
3533 If signed overflow must be undefined for the value to satisfy
3534 the conditional, then set *STRICT_OVERFLOW_P to true. */
3537 test_for_singularity (enum tree_code cond_code
, tree op0
,
3538 tree op1
, const value_range
*vr
)
3543 /* Extract minimum/maximum values which satisfy the conditional as it was
3545 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
3547 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
3550 if (cond_code
== LT_EXPR
)
3552 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3553 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
3554 /* Signal to compare_values_warnv this expr doesn't overflow. */
3556 TREE_NO_WARNING (max
) = 1;
3559 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
3561 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
3564 if (cond_code
== GT_EXPR
)
3566 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3567 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
3568 /* Signal to compare_values_warnv this expr doesn't overflow. */
3570 TREE_NO_WARNING (min
) = 1;
3574 /* Now refine the minimum and maximum values using any
3575 value range information we have for op0. */
3578 tree type
= TREE_TYPE (op0
);
3579 tree tmin
= wide_int_to_tree (type
, vr
->lower_bound ());
3580 tree tmax
= wide_int_to_tree (type
, vr
->upper_bound ());
3581 if (compare_values (tmin
, min
) == 1)
3583 if (compare_values (tmax
, max
) == -1)
3586 /* If the new min/max values have converged to a single value,
3587 then there is only one value which can satisfy the condition,
3588 return that value. */
3589 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
3595 /* Return whether the value range *VR fits in an integer type specified
3596 by PRECISION and UNSIGNED_P. */
3599 range_fits_type_p (const value_range
*vr
,
3600 unsigned dest_precision
, signop dest_sgn
)
3603 unsigned src_precision
;
3607 /* We can only handle integral and pointer types. */
3608 src_type
= vr
->type ();
3609 if (!INTEGRAL_TYPE_P (src_type
)
3610 && !POINTER_TYPE_P (src_type
))
3613 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3614 and so is an identity transform. */
3615 src_precision
= TYPE_PRECISION (vr
->type ());
3616 src_sgn
= TYPE_SIGN (src_type
);
3617 if ((src_precision
< dest_precision
3618 && !(dest_sgn
== UNSIGNED
&& src_sgn
== SIGNED
))
3619 || (src_precision
== dest_precision
&& src_sgn
== dest_sgn
))
3622 /* Now we can only handle ranges with constant bounds. */
3623 if (!range_int_cst_p (vr
))
3626 /* For sign changes, the MSB of the wide_int has to be clear.
3627 An unsigned value with its MSB set cannot be represented by
3628 a signed wide_int, while a negative value cannot be represented
3629 by an unsigned wide_int. */
3630 if (src_sgn
!= dest_sgn
3631 && (wi::lts_p (wi::to_wide (vr
->min ()), 0)
3632 || wi::lts_p (wi::to_wide (vr
->max ()), 0)))
3635 /* Then we can perform the conversion on both ends and compare
3636 the result for equality. */
3637 tem
= wi::ext (wi::to_widest (vr
->min ()), dest_precision
, dest_sgn
);
3638 if (tem
!= wi::to_widest (vr
->min ()))
3640 tem
= wi::ext (wi::to_widest (vr
->max ()), dest_precision
, dest_sgn
);
3641 if (tem
!= wi::to_widest (vr
->max ()))
3647 /* If COND can be folded entirely as TRUE or FALSE, rewrite the
3648 conditional as such, and return TRUE. */
3651 simplify_using_ranges::fold_cond (gcond
*cond
)
3653 /* ?? vrp_folder::fold_predicate_in() is a superset of this. At
3654 some point we should merge all variants of this code. */
3656 vrp_visit_cond_stmt (cond
, &taken_edge
);
3659 if (query
->range_of_stmt (r
, cond
) && r
.singleton_p ())
3661 // COND has already been folded if arguments are constant.
3662 if (TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
3663 && TREE_CODE (gimple_cond_rhs (cond
)) != SSA_NAME
)
3668 gcc_checking_assert (!taken_edge
3669 || taken_edge
->flags
& EDGE_FALSE_VALUE
);
3670 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && !taken_edge
)
3671 fprintf (dump_file
, "\nPredicate evaluates to: 0\n");
3672 gimple_cond_make_false (cond
);
3676 gcc_checking_assert (!taken_edge
3677 || taken_edge
->flags
& EDGE_TRUE_VALUE
);
3678 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && !taken_edge
)
3679 fprintf (dump_file
, "\nPredicate evaluates to: 1\n");
3680 gimple_cond_make_true (cond
);
3688 if (taken_edge
->flags
& EDGE_TRUE_VALUE
)
3689 gimple_cond_make_true (cond
);
3690 else if (taken_edge
->flags
& EDGE_FALSE_VALUE
)
3691 gimple_cond_make_false (cond
);
3700 /* Simplify a conditional using a relational operator to an equality
3701 test if the range information indicates only one value can satisfy
3702 the original conditional. */
3705 simplify_using_ranges::simplify_cond_using_ranges_1 (gcond
*stmt
)
3707 tree op0
= gimple_cond_lhs (stmt
);
3708 tree op1
= gimple_cond_rhs (stmt
);
3709 enum tree_code cond_code
= gimple_cond_code (stmt
);
3711 if (fold_cond (stmt
))
3714 if (cond_code
!= NE_EXPR
3715 && cond_code
!= EQ_EXPR
3716 && TREE_CODE (op0
) == SSA_NAME
3717 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3718 && is_gimple_min_invariant (op1
))
3720 const value_range
*vr
= query
->get_value_range (op0
, stmt
);
3722 /* If we have range information for OP0, then we might be
3723 able to simplify this conditional. */
3724 if (!vr
->undefined_p () && !vr
->varying_p ())
3726 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
3731 fprintf (dump_file
, "Simplified relational ");
3732 print_gimple_stmt (dump_file
, stmt
, 0);
3733 fprintf (dump_file
, " into ");
3736 gimple_cond_set_code (stmt
, EQ_EXPR
);
3737 gimple_cond_set_lhs (stmt
, op0
);
3738 gimple_cond_set_rhs (stmt
, new_tree
);
3744 print_gimple_stmt (dump_file
, stmt
, 0);
3745 fprintf (dump_file
, "\n");
3751 /* Try again after inverting the condition. We only deal
3752 with integral types here, so no need to worry about
3753 issues with inverting FP comparisons. */
3754 new_tree
= test_for_singularity
3755 (invert_tree_comparison (cond_code
, false),
3761 fprintf (dump_file
, "Simplified relational ");
3762 print_gimple_stmt (dump_file
, stmt
, 0);
3763 fprintf (dump_file
, " into ");
3766 gimple_cond_set_code (stmt
, NE_EXPR
);
3767 gimple_cond_set_lhs (stmt
, op0
);
3768 gimple_cond_set_rhs (stmt
, new_tree
);
3774 print_gimple_stmt (dump_file
, stmt
, 0);
3775 fprintf (dump_file
, "\n");
3785 /* Simplify a switch statement using the value range of the switch
3789 simplify_using_ranges::simplify_switch_using_ranges (gswitch
*stmt
)
3791 tree op
= gimple_switch_index (stmt
);
3792 const value_range
*vr
= NULL
;
3796 size_t i
= 0, j
= 0, n
, n2
;
3799 size_t k
= 1, l
= 0;
3801 if (TREE_CODE (op
) == SSA_NAME
)
3803 vr
= query
->get_value_range (op
, stmt
);
3805 /* We can only handle integer ranges. */
3806 if (vr
->varying_p ()
3807 || vr
->undefined_p ()
3808 || vr
->symbolic_p ())
3811 /* Find case label for min/max of the value range. */
3812 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
3814 else if (TREE_CODE (op
) == INTEGER_CST
)
3816 take_default
= !find_case_label_index (stmt
, 1, op
, &i
);
3830 n
= gimple_switch_num_labels (stmt
);
3832 /* We can truncate the case label ranges that partially overlap with OP's
3834 size_t min_idx
= 1, max_idx
= 0;
3836 find_case_label_range (stmt
, vr
->min (), vr
->max (), &min_idx
, &max_idx
);
3837 if (min_idx
<= max_idx
)
3839 tree min_label
= gimple_switch_label (stmt
, min_idx
);
3840 tree max_label
= gimple_switch_label (stmt
, max_idx
);
3842 /* Avoid changing the type of the case labels when truncating. */
3843 tree case_label_type
= TREE_TYPE (CASE_LOW (min_label
));
3844 tree vr_min
= fold_convert (case_label_type
, vr
->min ());
3845 tree vr_max
= fold_convert (case_label_type
, vr
->max ());
3847 if (vr
->kind () == VR_RANGE
)
3849 /* If OP's value range is [2,8] and the low label range is
3850 0 ... 3, truncate the label's range to 2 .. 3. */
3851 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3852 && CASE_HIGH (min_label
) != NULL_TREE
3853 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3854 CASE_LOW (min_label
) = vr_min
;
3856 /* If OP's value range is [2,8] and the high label range is
3857 7 ... 10, truncate the label's range to 7 .. 8. */
3858 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3859 && CASE_HIGH (max_label
) != NULL_TREE
3860 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3861 CASE_HIGH (max_label
) = vr_max
;
3863 else if (vr
->kind () == VR_ANTI_RANGE
)
3865 tree one_cst
= build_one_cst (case_label_type
);
3867 if (min_label
== max_label
)
3869 /* If OP's value range is ~[7,8] and the label's range is
3870 7 ... 10, truncate the label's range to 9 ... 10. */
3871 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) == 0
3872 && CASE_HIGH (min_label
) != NULL_TREE
3873 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) > 0)
3874 CASE_LOW (min_label
)
3875 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3877 /* If OP's value range is ~[7,8] and the label's range is
3878 5 ... 8, truncate the label's range to 5 ... 6. */
3879 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3880 && CASE_HIGH (min_label
) != NULL_TREE
3881 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) == 0)
3882 CASE_HIGH (min_label
)
3883 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3887 /* If OP's value range is ~[2,8] and the low label range is
3888 0 ... 3, truncate the label's range to 0 ... 1. */
3889 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3890 && CASE_HIGH (min_label
) != NULL_TREE
3891 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3892 CASE_HIGH (min_label
)
3893 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3895 /* If OP's value range is ~[2,8] and the high label range is
3896 7 ... 10, truncate the label's range to 9 ... 10. */
3897 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3898 && CASE_HIGH (max_label
) != NULL_TREE
3899 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3900 CASE_LOW (max_label
)
3901 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3905 /* Canonicalize singleton case ranges. */
3906 if (tree_int_cst_equal (CASE_LOW (min_label
), CASE_HIGH (min_label
)))
3907 CASE_HIGH (min_label
) = NULL_TREE
;
3908 if (tree_int_cst_equal (CASE_LOW (max_label
), CASE_HIGH (max_label
)))
3909 CASE_HIGH (max_label
) = NULL_TREE
;
3912 /* We can also eliminate case labels that lie completely outside OP's value
3915 /* Bail out if this is just all edges taken. */
3921 /* Build a new vector of taken case labels. */
3922 vec2
= make_tree_vec (j
- i
+ 1 + l
- k
+ 1 + (int)take_default
);
3925 /* Add the default edge, if necessary. */
3927 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
3929 for (; i
<= j
; ++i
, ++n2
)
3930 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
3932 for (; k
<= l
; ++k
, ++n2
)
3933 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, k
);
3935 /* Mark needed edges. */
3936 for (i
= 0; i
< n2
; ++i
)
3938 e
= find_edge (gimple_bb (stmt
),
3939 label_to_block (cfun
,
3940 CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
3941 e
->aux
= (void *)-1;
3944 /* Queue not needed edges for later removal. */
3945 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
3947 if (e
->aux
== (void *)-1)
3953 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3955 fprintf (dump_file
, "removing unreachable case label\n");
3957 to_remove_edges
.safe_push (e
);
3958 e
->flags
&= ~EDGE_EXECUTABLE
;
3959 e
->flags
|= EDGE_IGNORE
;
3962 /* And queue an update for the stmt. */
3965 to_update_switch_stmts
.safe_push (su
);
3970 simplify_using_ranges::cleanup_edges_and_switches (void)
3976 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
3977 CFG in a broken state and requires a cfg_cleanup run. */
3978 FOR_EACH_VEC_ELT (to_remove_edges
, i
, e
)
3981 /* Update SWITCH_EXPR case label vector. */
3982 FOR_EACH_VEC_ELT (to_update_switch_stmts
, i
, su
)
3985 size_t n
= TREE_VEC_LENGTH (su
->vec
);
3987 gimple_switch_set_num_labels (su
->stmt
, n
);
3988 for (j
= 0; j
< n
; j
++)
3989 gimple_switch_set_label (su
->stmt
, j
, TREE_VEC_ELT (su
->vec
, j
));
3990 /* As we may have replaced the default label with a regular one
3991 make sure to make it a real default label again. This ensures
3992 optimal expansion. */
3993 label
= gimple_switch_label (su
->stmt
, 0);
3994 CASE_LOW (label
) = NULL_TREE
;
3995 CASE_HIGH (label
) = NULL_TREE
;
3998 if (!to_remove_edges
.is_empty ())
4000 free_dominance_info (CDI_DOMINATORS
);
4001 loops_state_set (LOOPS_NEED_FIXUP
);
4004 to_remove_edges
.release ();
4005 to_update_switch_stmts
.release ();
4008 /* Simplify an integral conversion from an SSA name in STMT. */
4011 simplify_conversion_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
4013 tree innerop
, middleop
, finaltype
;
4015 signop inner_sgn
, middle_sgn
, final_sgn
;
4016 unsigned inner_prec
, middle_prec
, final_prec
;
4017 widest_int innermin
, innermed
, innermax
, middlemin
, middlemed
, middlemax
;
4019 finaltype
= TREE_TYPE (gimple_assign_lhs (stmt
));
4020 if (!INTEGRAL_TYPE_P (finaltype
))
4022 middleop
= gimple_assign_rhs1 (stmt
);
4023 def_stmt
= SSA_NAME_DEF_STMT (middleop
);
4024 if (!is_gimple_assign (def_stmt
)
4025 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
4027 innerop
= gimple_assign_rhs1 (def_stmt
);
4028 if (TREE_CODE (innerop
) != SSA_NAME
4029 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
))
4032 /* Get the value-range of the inner operand. Use get_range_info in
4033 case innerop was created during substitute-and-fold. */
4034 wide_int imin
, imax
;
4036 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
)))
4038 get_range_info (innerop
, vr
);
4039 if (vr
.undefined_p () || vr
.varying_p ())
4041 innermin
= widest_int::from (vr
.lower_bound (), TYPE_SIGN (TREE_TYPE (innerop
)));
4042 innermax
= widest_int::from (vr
.upper_bound (), TYPE_SIGN (TREE_TYPE (innerop
)));
4044 /* Simulate the conversion chain to check if the result is equal if
4045 the middle conversion is removed. */
4046 inner_prec
= TYPE_PRECISION (TREE_TYPE (innerop
));
4047 middle_prec
= TYPE_PRECISION (TREE_TYPE (middleop
));
4048 final_prec
= TYPE_PRECISION (finaltype
);
4050 /* If the first conversion is not injective, the second must not
4052 if (wi::gtu_p (innermax
- innermin
,
4053 wi::mask
<widest_int
> (middle_prec
, false))
4054 && middle_prec
< final_prec
)
4056 /* We also want a medium value so that we can track the effect that
4057 narrowing conversions with sign change have. */
4058 inner_sgn
= TYPE_SIGN (TREE_TYPE (innerop
));
4059 if (inner_sgn
== UNSIGNED
)
4060 innermed
= wi::shifted_mask
<widest_int
> (1, inner_prec
- 1, false);
4063 if (wi::cmp (innermin
, innermed
, inner_sgn
) >= 0
4064 || wi::cmp (innermed
, innermax
, inner_sgn
) >= 0)
4065 innermed
= innermin
;
4067 middle_sgn
= TYPE_SIGN (TREE_TYPE (middleop
));
4068 middlemin
= wi::ext (innermin
, middle_prec
, middle_sgn
);
4069 middlemed
= wi::ext (innermed
, middle_prec
, middle_sgn
);
4070 middlemax
= wi::ext (innermax
, middle_prec
, middle_sgn
);
4072 /* Require that the final conversion applied to both the original
4073 and the intermediate range produces the same result. */
4074 final_sgn
= TYPE_SIGN (finaltype
);
4075 if (wi::ext (middlemin
, final_prec
, final_sgn
)
4076 != wi::ext (innermin
, final_prec
, final_sgn
)
4077 || wi::ext (middlemed
, final_prec
, final_sgn
)
4078 != wi::ext (innermed
, final_prec
, final_sgn
)
4079 || wi::ext (middlemax
, final_prec
, final_sgn
)
4080 != wi::ext (innermax
, final_prec
, final_sgn
))
4083 gimple_assign_set_rhs1 (stmt
, innerop
);
4084 fold_stmt (gsi
, follow_single_use_edges
);
4088 /* Simplify a conversion from integral SSA name to float in STMT. */
4091 simplify_using_ranges::simplify_float_conversion_using_ranges
4092 (gimple_stmt_iterator
*gsi
,
4095 tree rhs1
= gimple_assign_rhs1 (stmt
);
4096 const value_range
*vr
= query
->get_value_range (rhs1
, stmt
);
4097 scalar_float_mode fltmode
4098 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
)));
4099 scalar_int_mode mode
;
4103 /* We can only handle constant ranges. */
4104 if (!range_int_cst_p (vr
))
4107 /* First check if we can use a signed type in place of an unsigned. */
4108 scalar_int_mode rhs_mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1
));
4109 if (TYPE_UNSIGNED (TREE_TYPE (rhs1
))
4110 && can_float_p (fltmode
, rhs_mode
, 0) != CODE_FOR_nothing
4111 && range_fits_type_p (vr
, TYPE_PRECISION (TREE_TYPE (rhs1
)), SIGNED
))
4113 /* If we can do the conversion in the current input mode do nothing. */
4114 else if (can_float_p (fltmode
, rhs_mode
,
4115 TYPE_UNSIGNED (TREE_TYPE (rhs1
))) != CODE_FOR_nothing
)
4117 /* Otherwise search for a mode we can use, starting from the narrowest
4118 integer mode available. */
4121 mode
= NARROWEST_INT_MODE
;
4124 /* If we cannot do a signed conversion to float from mode
4125 or if the value-range does not fit in the signed type
4126 try with a wider mode. */
4127 if (can_float_p (fltmode
, mode
, 0) != CODE_FOR_nothing
4128 && range_fits_type_p (vr
, GET_MODE_PRECISION (mode
), SIGNED
))
4131 /* But do not widen the input. Instead leave that to the
4132 optabs expansion code. */
4133 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
4134 || GET_MODE_PRECISION (mode
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
4139 /* It works, insert a truncation or sign-change before the
4140 float conversion. */
4141 tem
= make_ssa_name (build_nonstandard_integer_type
4142 (GET_MODE_PRECISION (mode
), 0));
4143 conv
= gimple_build_assign (tem
, NOP_EXPR
, rhs1
);
4144 gsi_insert_before (gsi
, conv
, GSI_SAME_STMT
);
4145 gimple_assign_set_rhs1 (stmt
, tem
);
4146 fold_stmt (gsi
, follow_single_use_edges
);
4151 /* Simplify an internal fn call using ranges if possible. */
4154 simplify_using_ranges::simplify_internal_call_using_ranges
4155 (gimple_stmt_iterator
*gsi
,
4158 enum tree_code subcode
;
4159 bool is_ubsan
= false;
4161 switch (gimple_call_internal_fn (stmt
))
4163 case IFN_UBSAN_CHECK_ADD
:
4164 subcode
= PLUS_EXPR
;
4167 case IFN_UBSAN_CHECK_SUB
:
4168 subcode
= MINUS_EXPR
;
4171 case IFN_UBSAN_CHECK_MUL
:
4172 subcode
= MULT_EXPR
;
4175 case IFN_ADD_OVERFLOW
:
4176 subcode
= PLUS_EXPR
;
4178 case IFN_SUB_OVERFLOW
:
4179 subcode
= MINUS_EXPR
;
4181 case IFN_MUL_OVERFLOW
:
4182 subcode
= MULT_EXPR
;
4188 tree op0
= gimple_call_arg (stmt
, 0);
4189 tree op1
= gimple_call_arg (stmt
, 1);
4193 type
= TREE_TYPE (op0
);
4194 if (VECTOR_TYPE_P (type
))
4197 else if (gimple_call_lhs (stmt
) == NULL_TREE
)
4200 type
= TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt
)));
4201 if (!check_for_binary_op_overflow (query
, subcode
, type
, op0
, op1
, &ovf
)
4202 || (is_ubsan
&& ovf
))
4206 location_t loc
= gimple_location (stmt
);
4208 g
= gimple_build_assign (gimple_call_lhs (stmt
), subcode
, op0
, op1
);
4211 int prec
= TYPE_PRECISION (type
);
4214 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
4215 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
4216 utype
= build_nonstandard_integer_type (prec
, 1);
4217 if (TREE_CODE (op0
) == INTEGER_CST
)
4218 op0
= fold_convert (utype
, op0
);
4219 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op0
)))
4221 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op0
);
4222 gimple_set_location (g
, loc
);
4223 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4224 op0
= gimple_assign_lhs (g
);
4226 if (TREE_CODE (op1
) == INTEGER_CST
)
4227 op1
= fold_convert (utype
, op1
);
4228 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op1
)))
4230 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op1
);
4231 gimple_set_location (g
, loc
);
4232 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4233 op1
= gimple_assign_lhs (g
);
4235 g
= gimple_build_assign (make_ssa_name (utype
), subcode
, op0
, op1
);
4236 gimple_set_location (g
, loc
);
4237 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4240 g
= gimple_build_assign (make_ssa_name (type
), NOP_EXPR
,
4241 gimple_assign_lhs (g
));
4242 gimple_set_location (g
, loc
);
4243 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4245 g
= gimple_build_assign (gimple_call_lhs (stmt
), COMPLEX_EXPR
,
4246 gimple_assign_lhs (g
),
4247 build_int_cst (type
, ovf
));
4249 gimple_set_location (g
, loc
);
4250 gsi_replace (gsi
, g
, false);
4254 /* Return true if VAR is a two-valued variable. Set a and b with the
4255 two-values when it is true. Return false otherwise. */
4258 simplify_using_ranges::two_valued_val_range_p (tree var
, tree
*a
, tree
*b
)
4260 value_range vr
= *query
->get_value_range (var
);
4261 vr
.normalize_symbolics ();
4262 if (vr
.varying_p () || vr
.undefined_p ())
4265 if ((vr
.num_pairs () == 1 && vr
.upper_bound () - vr
.lower_bound () == 1)
4266 || (vr
.num_pairs () == 2
4267 && vr
.lower_bound (0) == vr
.upper_bound (0)
4268 && vr
.lower_bound (1) == vr
.upper_bound (1)))
4270 *a
= wide_int_to_tree (TREE_TYPE (var
), vr
.lower_bound ());
4271 *b
= wide_int_to_tree (TREE_TYPE (var
), vr
.upper_bound ());
4277 simplify_using_ranges::simplify_using_ranges (range_query
*query
)
4280 to_remove_edges
= vNULL
;
4281 to_update_switch_stmts
= vNULL
;
4284 simplify_using_ranges::~simplify_using_ranges ()
4286 cleanup_edges_and_switches ();
4289 /* Simplify STMT using ranges if possible. */
4292 simplify_using_ranges::simplify (gimple_stmt_iterator
*gsi
)
4294 gcc_checking_assert (query
);
4296 gimple
*stmt
= gsi_stmt (*gsi
);
4297 if (is_gimple_assign (stmt
))
4299 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
4300 tree rhs1
= gimple_assign_rhs1 (stmt
);
4301 tree rhs2
= gimple_assign_rhs2 (stmt
);
4302 tree lhs
= gimple_assign_lhs (stmt
);
4303 tree val1
= NULL_TREE
, val2
= NULL_TREE
;
4304 use_operand_p use_p
;
4309 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4311 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4315 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4317 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4319 if (TREE_CODE_CLASS (rhs_code
) == tcc_binary
4320 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4321 && ((TREE_CODE (rhs1
) == INTEGER_CST
4322 && TREE_CODE (rhs2
) == SSA_NAME
)
4323 || (TREE_CODE (rhs2
) == INTEGER_CST
4324 && TREE_CODE (rhs1
) == SSA_NAME
))
4325 && single_imm_use (lhs
, &use_p
, &use_stmt
)
4326 && gimple_code (use_stmt
) == GIMPLE_COND
)
4329 tree new_rhs1
= NULL_TREE
;
4330 tree new_rhs2
= NULL_TREE
;
4331 tree cmp_var
= NULL_TREE
;
4333 if (TREE_CODE (rhs2
) == SSA_NAME
4334 && two_valued_val_range_p (rhs2
, &val1
, &val2
))
4336 /* Optimize RHS1 OP [VAL1, VAL2]. */
4337 new_rhs1
= int_const_binop (rhs_code
, rhs1
, val1
);
4338 new_rhs2
= int_const_binop (rhs_code
, rhs1
, val2
);
4341 else if (TREE_CODE (rhs1
) == SSA_NAME
4342 && two_valued_val_range_p (rhs1
, &val1
, &val2
))
4344 /* Optimize [VAL1, VAL2] OP RHS2. */
4345 new_rhs1
= int_const_binop (rhs_code
, val1
, rhs2
);
4346 new_rhs2
= int_const_binop (rhs_code
, val2
, rhs2
);
4350 /* If we could not find two-vals or the optimzation is invalid as
4351 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4352 if (new_rhs1
&& new_rhs2
)
4354 tree cond
= build2 (EQ_EXPR
, boolean_type_node
, cmp_var
, val1
);
4355 gimple_assign_set_rhs_with_ops (gsi
,
4359 update_stmt (gsi_stmt (*gsi
));
4360 fold_stmt (gsi
, follow_single_use_edges
);
4369 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4370 if the RHS is zero or one, and the LHS are known to be boolean
4372 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4373 return simplify_truth_ops_using_ranges (gsi
, stmt
);
4376 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4377 and BIT_AND_EXPR respectively if the first operand is greater
4378 than zero and the second operand is an exact power of two.
4379 Also optimize TRUNC_MOD_EXPR away if the second operand is
4380 constant and the first operand already has the right value
4382 case TRUNC_DIV_EXPR
:
4383 case TRUNC_MOD_EXPR
:
4384 if ((TREE_CODE (rhs1
) == SSA_NAME
4385 || TREE_CODE (rhs1
) == INTEGER_CST
)
4386 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4387 return simplify_div_or_mod_using_ranges (gsi
, stmt
);
4390 /* Transform ABS (X) into X or -X as appropriate. */
4392 if (TREE_CODE (rhs1
) == SSA_NAME
4393 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4394 return simplify_abs_using_ranges (gsi
, stmt
);
4399 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4400 if all the bits being cleared are already cleared or
4401 all the bits being set are already set. */
4402 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4403 return simplify_bit_ops_using_ranges (gsi
, stmt
);
4407 if (TREE_CODE (rhs1
) == SSA_NAME
4408 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4409 return simplify_conversion_using_ranges (gsi
, stmt
);
4413 if (TREE_CODE (rhs1
) == SSA_NAME
4414 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4415 return simplify_float_conversion_using_ranges (gsi
, stmt
);
4420 return simplify_min_or_max_using_ranges (gsi
, stmt
);
4426 else if (gimple_code (stmt
) == GIMPLE_COND
)
4427 return simplify_cond_using_ranges_1 (as_a
<gcond
*> (stmt
));
4428 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
4429 return simplify_switch_using_ranges (as_a
<gswitch
*> (stmt
));
4430 else if (is_gimple_call (stmt
)
4431 && gimple_call_internal_p (stmt
))
4432 return simplify_internal_call_using_ranges (gsi
, stmt
);
4437 /* Set the lattice entry for VAR to VR. */
4440 vr_values::set_vr_value (tree var
, value_range_equiv
*vr
)
4442 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4444 vr_value
[SSA_NAME_VERSION (var
)] = vr
;
4447 /* Swap the lattice entry for VAR with VR and return the old entry. */
4450 vr_values::swap_vr_value (tree var
, value_range_equiv
*vr
)
4452 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4454 std::swap (vr_value
[SSA_NAME_VERSION (var
)], vr
);