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"
54 /* Set value range VR to a non-negative range of type TYPE. */
57 set_value_range_to_nonnegative (value_range_equiv
*vr
, tree type
)
59 tree zero
= build_int_cst (type
, 0);
60 vr
->update (zero
, vrp_val_max (type
));
63 /* Set value range VR to a range of a truthvalue of type TYPE. */
66 set_value_range_to_truthvalue (value_range_equiv
*vr
, tree type
)
68 if (TYPE_PRECISION (type
) == 1)
69 vr
->set_varying (type
);
71 vr
->update (build_int_cst (type
, 0), build_int_cst (type
, 1));
74 /* Return the lattice entry for VAR or NULL if it doesn't exist or cannot
78 vr_values::get_lattice_entry (const_tree var
)
80 value_range_equiv
*vr
;
82 unsigned ver
= SSA_NAME_VERSION (var
);
84 /* If we query the entry for a new SSA name avoid reallocating the lattice
85 since we should get here at most from the substitute-and-fold stage which
86 will never try to change values. */
87 if (ver
>= num_vr_values
)
94 /* Create a default value range. */
95 vr
= new (vrp_value_range_pool
.allocate ()) value_range_equiv
;
98 /* After propagation finished return varying. */
99 if (values_propagated
)
101 vr
->set_varying (TREE_TYPE (var
));
105 vr
->set_undefined ();
107 /* If VAR is a default definition of a parameter, the variable can
108 take any value in VAR's type. */
109 if (SSA_NAME_IS_DEFAULT_DEF (var
))
111 sym
= SSA_NAME_VAR (var
);
112 if (TREE_CODE (sym
) == PARM_DECL
)
114 /* Try to use the "nonnull" attribute to create ~[0, 0]
115 anti-ranges for pointers. Note that this is only valid with
116 default definitions of PARM_DECLs. */
117 if (POINTER_TYPE_P (TREE_TYPE (sym
))
118 && (nonnull_arg_p (sym
)
119 || get_ptr_nonnull (var
)))
121 vr
->set_nonzero (TREE_TYPE (sym
));
124 else if (INTEGRAL_TYPE_P (TREE_TYPE (sym
)))
126 get_range_info (var
, *vr
);
127 if (vr
->undefined_p ())
128 vr
->set_varying (TREE_TYPE (sym
));
131 vr
->set_varying (TREE_TYPE (sym
));
133 else if (TREE_CODE (sym
) == RESULT_DECL
134 && DECL_BY_REFERENCE (sym
))
136 vr
->set_nonzero (TREE_TYPE (sym
));
144 /* Return value range information for VAR.
146 If we have no values ranges recorded (ie, VRP is not running), then
147 return NULL. Otherwise create an empty range if none existed for VAR. */
149 const value_range_equiv
*
150 vr_values::get_value_range (const_tree var
,
151 gimple
*stmt ATTRIBUTE_UNUSED
)
153 /* If we have no recorded ranges, then return NULL. */
157 value_range_equiv
*vr
= get_lattice_entry (var
);
159 /* Reallocate the lattice if needed. */
162 unsigned int old_sz
= num_vr_values
;
163 num_vr_values
= num_ssa_names
+ num_ssa_names
/ 10;
164 vr_value
= XRESIZEVEC (value_range_equiv
*, vr_value
, num_vr_values
);
165 for ( ; old_sz
< num_vr_values
; old_sz
++)
166 vr_value
[old_sz
] = NULL
;
168 /* Now that the lattice has been resized, we should never fail. */
169 vr
= get_lattice_entry (var
);
176 /* Set the lattice entry for DEF to VARYING. */
179 vr_values::set_def_to_varying (const_tree def
)
181 value_range_equiv
*vr
= get_lattice_entry (def
);
183 vr
->set_varying (TREE_TYPE (def
));
186 /* Set value-ranges of all SSA names defined by STMT to varying. */
189 vr_values::set_defs_to_varying (gimple
*stmt
)
193 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
194 set_def_to_varying (def
);
197 /* Update the value range and equivalence set for variable VAR to
198 NEW_VR. Return true if NEW_VR is different from VAR's previous
201 NOTE: This function assumes that NEW_VR is a temporary value range
202 object created for the sole purpose of updating VAR's range. The
203 storage used by the equivalence set from NEW_VR will be freed by
204 this function. Do not call update_value_range when NEW_VR
205 is the range object associated with another SSA name. */
208 vr_values::update_value_range (const_tree var
, value_range_equiv
*new_vr
)
210 value_range_equiv
*old_vr
;
213 /* If there is a value-range on the SSA name from earlier analysis
215 if (INTEGRAL_TYPE_P (TREE_TYPE (var
)))
217 value_range_equiv nr
;
218 get_range_info (var
, nr
);
219 if (!nr
.undefined_p ())
220 new_vr
->intersect (&nr
);
223 /* Update the value range, if necessary. If we cannot allocate a lattice
224 entry for VAR keep it at VARYING. This happens when DOM feeds us stmts
225 with SSA names allocated after setting up the lattice. */
226 old_vr
= get_lattice_entry (var
);
229 is_new
= !old_vr
->equal_p (*new_vr
, /*ignore_equivs=*/false);
233 /* Do not allow transitions up the lattice. The following
234 is slightly more awkward than just new_vr->type < old_vr->type
235 because VR_RANGE and VR_ANTI_RANGE need to be considered
236 the same. We may not have is_new when transitioning to
237 UNDEFINED. If old_vr->type is VARYING, we shouldn't be
238 called, if we are anyway, keep it VARYING. */
239 if (old_vr
->varying_p ())
241 new_vr
->set_varying (TREE_TYPE (var
));
244 else if (new_vr
->undefined_p ())
246 old_vr
->set_varying (TREE_TYPE (var
));
247 new_vr
->set_varying (TREE_TYPE (var
));
251 old_vr
->set (new_vr
->min (), new_vr
->max (), new_vr
->equiv (),
255 new_vr
->equiv_clear ();
260 /* Return true if value range VR involves exactly one symbol SYM. */
263 symbolic_range_based_on_p (value_range
*vr
, const_tree sym
)
265 bool neg
, min_has_symbol
, max_has_symbol
;
268 if (is_gimple_min_invariant (vr
->min ()))
269 min_has_symbol
= false;
270 else if (get_single_symbol (vr
->min (), &neg
, &inv
) == sym
)
271 min_has_symbol
= true;
275 if (is_gimple_min_invariant (vr
->max ()))
276 max_has_symbol
= false;
277 else if (get_single_symbol (vr
->max (), &neg
, &inv
) == sym
)
278 max_has_symbol
= true;
282 return (min_has_symbol
|| max_has_symbol
);
285 /* Return true if the result of assignment STMT is know to be non-zero. */
288 gimple_assign_nonzero_p (gimple
*stmt
)
290 enum tree_code code
= gimple_assign_rhs_code (stmt
);
291 bool strict_overflow_p
;
292 switch (get_gimple_rhs_class (code
))
294 case GIMPLE_UNARY_RHS
:
295 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
296 gimple_expr_type (stmt
),
297 gimple_assign_rhs1 (stmt
),
299 case GIMPLE_BINARY_RHS
:
300 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
301 gimple_expr_type (stmt
),
302 gimple_assign_rhs1 (stmt
),
303 gimple_assign_rhs2 (stmt
),
305 case GIMPLE_TERNARY_RHS
:
307 case GIMPLE_SINGLE_RHS
:
308 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt
),
310 case GIMPLE_INVALID_RHS
:
317 /* Return true if STMT is known to compute a non-zero value. */
320 gimple_stmt_nonzero_p (gimple
*stmt
)
322 switch (gimple_code (stmt
))
325 return gimple_assign_nonzero_p (stmt
);
328 gcall
*call_stmt
= as_a
<gcall
*> (stmt
);
329 return (gimple_call_nonnull_result_p (call_stmt
)
330 || gimple_call_nonnull_arg (call_stmt
));
336 /* Like tree_expr_nonzero_p, but this function uses value ranges
340 vr_values::vrp_stmt_computes_nonzero (gimple
*stmt
)
342 if (gimple_stmt_nonzero_p (stmt
))
345 /* If we have an expression of the form &X->a, then the expression
346 is nonnull if X is nonnull. */
347 if (is_gimple_assign (stmt
)
348 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
350 tree expr
= gimple_assign_rhs1 (stmt
);
351 poly_int64 bitsize
, bitpos
;
354 int unsignedp
, reversep
, volatilep
;
355 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
356 &bitpos
, &offset
, &mode
, &unsignedp
,
357 &reversep
, &volatilep
);
359 if (base
!= NULL_TREE
360 && TREE_CODE (base
) == MEM_REF
361 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
363 poly_offset_int off
= 0;
364 bool off_cst
= false;
365 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
367 off
= mem_ref_offset (base
);
369 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
371 off
<<= LOG2_BITS_PER_UNIT
;
375 /* If &X->a is equal to X and X is ~[0, 0], the result is too.
376 For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
377 allow going from non-NULL pointer to NULL. */
378 if ((off_cst
&& known_eq (off
, 0))
379 || (flag_delete_null_pointer_checks
380 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))))
382 const value_range_equiv
*vr
383 = get_value_range (TREE_OPERAND (base
, 0));
384 if (!range_includes_zero_p (vr
))
387 /* If MEM_REF has a "positive" offset, consider it non-NULL
388 always, for -fdelete-null-pointer-checks also "negative"
389 ones. Punt for unknown offsets (e.g. variable ones). */
390 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
393 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
401 /* Returns true if EXPR is a valid value (as expected by compare_values) --
402 a gimple invariant, or SSA_NAME +- CST. */
405 valid_value_p (tree expr
)
407 if (TREE_CODE (expr
) == SSA_NAME
)
410 if (TREE_CODE (expr
) == PLUS_EXPR
411 || TREE_CODE (expr
) == MINUS_EXPR
)
412 return (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
413 && TREE_CODE (TREE_OPERAND (expr
, 1)) == INTEGER_CST
);
415 return is_gimple_min_invariant (expr
);
418 /* If OP has a value range with a single constant value return that,
419 otherwise return NULL_TREE. This returns OP itself if OP is a
423 vr_values::op_with_constant_singleton_value_range (tree op
)
425 if (is_gimple_min_invariant (op
))
428 if (TREE_CODE (op
) != SSA_NAME
)
432 if (get_value_range (op
)->singleton_p (&t
))
437 /* Return true if op is in a boolean [0, 1] value-range. */
440 simplify_using_ranges::op_with_boolean_value_range_p (tree op
)
442 if (TYPE_PRECISION (TREE_TYPE (op
)) == 1)
445 if (integer_zerop (op
)
446 || integer_onep (op
))
449 if (TREE_CODE (op
) != SSA_NAME
)
452 /* ?? Errr, this should probably check for [0,0] and [1,1] as well
454 const value_range
*vr
= get_value_range (op
);
455 return *vr
== value_range (build_zero_cst (TREE_TYPE (op
)),
456 build_one_cst (TREE_TYPE (op
)));
459 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
460 true and store it in *VR_P. */
463 vr_values::extract_range_for_var_from_comparison_expr (tree var
,
464 enum tree_code cond_code
,
466 value_range_equiv
*vr_p
)
469 const value_range_equiv
*limit_vr
;
470 type
= TREE_TYPE (var
);
472 /* For pointer arithmetic, we only keep track of pointer equality
473 and inequality. If we arrive here with unfolded conditions like
474 _1 > _1 do not derive anything. */
475 if ((POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
478 vr_p
->set_varying (type
);
482 /* If LIMIT is another SSA name and LIMIT has a range of its own,
483 try to use LIMIT's range to avoid creating symbolic ranges
485 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
487 /* LIMIT's range is only interesting if it has any useful information. */
489 || limit_vr
->undefined_p ()
490 || limit_vr
->varying_p ()
491 || (limit_vr
->symbolic_p ()
492 && ! (limit_vr
->kind () == VR_RANGE
493 && (limit_vr
->min () == limit_vr
->max ()
494 || operand_equal_p (limit_vr
->min (),
495 limit_vr
->max (), 0)))))
498 /* Initially, the new range has the same set of equivalences of
499 VAR's range. This will be revised before returning the final
500 value. Since assertions may be chained via mutually exclusive
501 predicates, we will need to trim the set of equivalences before
503 gcc_assert (vr_p
->equiv () == NULL
);
504 vr_p
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
506 /* Extract a new range based on the asserted comparison for VAR and
507 LIMIT's value range. Notice that if LIMIT has an anti-range, we
508 will only use it for equality comparisons (EQ_EXPR). For any
509 other kind of assertion, we cannot derive a range from LIMIT's
510 anti-range that can be used to describe the new range. For
511 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
512 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
513 no single range for x_2 that could describe LE_EXPR, so we might
514 as well build the range [b_4, +INF] for it.
515 One special case we handle is extracting a range from a
516 range test encoded as (unsigned)var + CST <= limit. */
517 if (TREE_CODE (op
) == NOP_EXPR
518 || TREE_CODE (op
) == PLUS_EXPR
)
520 if (TREE_CODE (op
) == PLUS_EXPR
)
522 min
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (TREE_OPERAND (op
, 1)),
523 TREE_OPERAND (op
, 1));
524 max
= int_const_binop (PLUS_EXPR
, limit
, min
);
525 op
= TREE_OPERAND (op
, 0);
529 min
= build_int_cst (TREE_TYPE (var
), 0);
533 /* Make sure to not set TREE_OVERFLOW on the final type
534 conversion. We are willingly interpreting large positive
535 unsigned values as negative signed values here. */
536 min
= force_fit_type (TREE_TYPE (var
), wi::to_widest (min
), 0, false);
537 max
= force_fit_type (TREE_TYPE (var
), wi::to_widest (max
), 0, false);
539 /* We can transform a max, min range to an anti-range or
540 vice-versa. Use set_and_canonicalize which does this for
542 if (cond_code
== LE_EXPR
)
543 vr_p
->set (min
, max
, vr_p
->equiv ());
544 else if (cond_code
== GT_EXPR
)
545 vr_p
->set (min
, max
, vr_p
->equiv (), VR_ANTI_RANGE
);
549 else if (cond_code
== EQ_EXPR
)
551 enum value_range_kind range_kind
;
555 range_kind
= limit_vr
->kind ();
556 min
= limit_vr
->min ();
557 max
= limit_vr
->max ();
561 range_kind
= VR_RANGE
;
566 vr_p
->update (min
, max
, range_kind
);
568 /* When asserting the equality VAR == LIMIT and LIMIT is another
569 SSA name, the new range will also inherit the equivalence set
571 if (TREE_CODE (limit
) == SSA_NAME
)
572 vr_p
->equiv_add (limit
, get_value_range (limit
), &vrp_equiv_obstack
);
574 else if (cond_code
== NE_EXPR
)
576 /* As described above, when LIMIT's range is an anti-range and
577 this assertion is an inequality (NE_EXPR), then we cannot
578 derive anything from the anti-range. For instance, if
579 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
580 not imply that VAR's range is [0, 0]. So, in the case of
581 anti-ranges, we just assert the inequality using LIMIT and
584 If LIMIT_VR is a range, we can only use it to build a new
585 anti-range if LIMIT_VR is a single-valued range. For
586 instance, if LIMIT_VR is [0, 1], the predicate
587 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
588 Rather, it means that for value 0 VAR should be ~[0, 0]
589 and for value 1, VAR should be ~[1, 1]. We cannot
590 represent these ranges.
592 The only situation in which we can build a valid
593 anti-range is when LIMIT_VR is a single-valued range
594 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
595 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
597 && limit_vr
->kind () == VR_RANGE
598 && compare_values (limit_vr
->min (), limit_vr
->max ()) == 0)
600 min
= limit_vr
->min ();
601 max
= limit_vr
->max ();
605 /* In any other case, we cannot use LIMIT's range to build a
610 /* If MIN and MAX cover the whole range for their type, then
611 just use the original LIMIT. */
612 if (INTEGRAL_TYPE_P (type
)
613 && vrp_val_is_min (min
)
614 && vrp_val_is_max (max
))
617 vr_p
->set (min
, max
, vr_p
->equiv (), VR_ANTI_RANGE
);
619 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
621 min
= TYPE_MIN_VALUE (type
);
623 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
627 /* If LIMIT_VR is of the form [N1, N2], we need to build the
628 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
630 max
= limit_vr
->max ();
633 /* If the maximum value forces us to be out of bounds, simply punt.
634 It would be pointless to try and do anything more since this
635 all should be optimized away above us. */
636 if (cond_code
== LT_EXPR
637 && compare_values (max
, min
) == 0)
638 vr_p
->set_varying (TREE_TYPE (min
));
641 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
642 if (cond_code
== LT_EXPR
)
644 if (TYPE_PRECISION (TREE_TYPE (max
)) == 1
645 && !TYPE_UNSIGNED (TREE_TYPE (max
)))
646 max
= fold_build2 (PLUS_EXPR
, TREE_TYPE (max
), max
,
647 build_int_cst (TREE_TYPE (max
), -1));
649 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max
), max
,
650 build_int_cst (TREE_TYPE (max
), 1));
651 /* Signal to compare_values_warnv this expr doesn't overflow. */
653 TREE_NO_WARNING (max
) = 1;
656 vr_p
->update (min
, max
);
659 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
661 max
= TYPE_MAX_VALUE (type
);
663 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
667 /* If LIMIT_VR is of the form [N1, N2], we need to build the
668 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
670 min
= limit_vr
->min ();
673 /* If the minimum value forces us to be out of bounds, simply punt.
674 It would be pointless to try and do anything more since this
675 all should be optimized away above us. */
676 if (cond_code
== GT_EXPR
677 && compare_values (min
, max
) == 0)
678 vr_p
->set_varying (TREE_TYPE (min
));
681 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
682 if (cond_code
== GT_EXPR
)
684 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
685 && !TYPE_UNSIGNED (TREE_TYPE (min
)))
686 min
= fold_build2 (MINUS_EXPR
, TREE_TYPE (min
), min
,
687 build_int_cst (TREE_TYPE (min
), -1));
689 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min
), min
,
690 build_int_cst (TREE_TYPE (min
), 1));
691 /* Signal to compare_values_warnv this expr doesn't overflow. */
693 TREE_NO_WARNING (min
) = 1;
696 vr_p
->update (min
, max
);
702 /* Finally intersect the new range with what we already know about var. */
703 vr_p
->intersect (get_value_range (var
));
706 /* Extract value range information from an ASSERT_EXPR EXPR and store
710 vr_values::extract_range_from_assert (value_range_equiv
*vr_p
, tree expr
)
712 tree var
= ASSERT_EXPR_VAR (expr
);
713 tree cond
= ASSERT_EXPR_COND (expr
);
715 enum tree_code cond_code
;
716 gcc_assert (COMPARISON_CLASS_P (cond
));
718 /* Find VAR in the ASSERT_EXPR conditional. */
719 if (var
== TREE_OPERAND (cond
, 0)
720 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PLUS_EXPR
721 || TREE_CODE (TREE_OPERAND (cond
, 0)) == NOP_EXPR
)
723 /* If the predicate is of the form VAR COMP LIMIT, then we just
724 take LIMIT from the RHS and use the same comparison code. */
725 cond_code
= TREE_CODE (cond
);
726 limit
= TREE_OPERAND (cond
, 1);
727 op
= TREE_OPERAND (cond
, 0);
731 /* If the predicate is of the form LIMIT COMP VAR, then we need
732 to flip around the comparison code to create the proper range
734 cond_code
= swap_tree_comparison (TREE_CODE (cond
));
735 limit
= TREE_OPERAND (cond
, 0);
736 op
= TREE_OPERAND (cond
, 1);
738 extract_range_for_var_from_comparison_expr (var
, cond_code
, op
,
742 /* Extract range information from SSA name VAR and store it in VR. If
743 VAR has an interesting range, use it. Otherwise, create the
744 range [VAR, VAR] and return it. This is useful in situations where
745 we may have conditionals testing values of VARYING names. For
752 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
756 vr_values::extract_range_from_ssa_name (value_range_equiv
*vr
, tree var
)
758 const value_range_equiv
*var_vr
= get_value_range (var
);
760 if (!var_vr
->varying_p ())
761 vr
->deep_copy (var_vr
);
765 if (!vr
->undefined_p ())
766 vr
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
769 /* Extract range information from a binary expression OP0 CODE OP1 based on
770 the ranges of each of its operands with resulting type EXPR_TYPE.
771 The resulting range is stored in *VR. */
774 vr_values::extract_range_from_binary_expr (value_range_equiv
*vr
,
776 tree expr_type
, tree op0
, tree op1
)
778 /* Get value ranges for each operand. For constant operands, create
779 a new value range with the operand to simplify processing. */
780 value_range vr0
, vr1
;
781 if (TREE_CODE (op0
) == SSA_NAME
)
782 vr0
= *(get_value_range (op0
));
783 else if (is_gimple_min_invariant (op0
))
786 vr0
.set_varying (TREE_TYPE (op0
));
788 if (TREE_CODE (op1
) == SSA_NAME
)
789 vr1
= *(get_value_range (op1
));
790 else if (is_gimple_min_invariant (op1
))
793 vr1
.set_varying (TREE_TYPE (op1
));
795 /* If one argument is varying, we can sometimes still deduce a
796 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
797 if (INTEGRAL_TYPE_P (TREE_TYPE (op0
))
798 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0
)))
800 if (vr0
.varying_p () && !vr1
.varying_p ())
801 vr0
= value_range (vrp_val_min (expr_type
), vrp_val_max (expr_type
));
802 else if (vr1
.varying_p () && !vr0
.varying_p ())
803 vr1
= value_range (vrp_val_min (expr_type
), vrp_val_max (expr_type
));
806 range_fold_binary_expr (vr
, code
, expr_type
, &vr0
, &vr1
);
808 /* Set value_range for n in following sequence:
809 def = __builtin_memchr (arg, 0, sz)
811 Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
814 && code
== POINTER_DIFF_EXPR
815 && TREE_CODE (op0
) == SSA_NAME
816 && TREE_CODE (op1
) == SSA_NAME
)
818 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
819 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
820 gcall
*call_stmt
= NULL
;
822 if (TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
823 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
824 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
825 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
826 && (call_stmt
= dyn_cast
<gcall
*>(SSA_NAME_DEF_STMT (op0
)))
827 && gimple_call_builtin_p (call_stmt
, BUILT_IN_MEMCHR
)
828 && operand_equal_p (op0
, gimple_call_lhs (call_stmt
), 0)
829 && operand_equal_p (op1
, gimple_call_arg (call_stmt
, 0), 0)
830 && integer_zerop (gimple_call_arg (call_stmt
, 1)))
832 tree max
= vrp_val_max (ptrdiff_type_node
);
833 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
834 tree range_min
= build_zero_cst (expr_type
);
835 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
836 vr
->set (range_min
, range_max
);
841 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
842 and based on the other operand, for example if it was deduced from a
843 symbolic comparison. When a bound of the range of the first operand
844 is invariant, we set the corresponding bound of the new range to INF
845 in order to avoid recursing on the range of the second operand. */
847 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
848 && TREE_CODE (op1
) == SSA_NAME
849 && vr0
.kind () == VR_RANGE
850 && symbolic_range_based_on_p (&vr0
, op1
))
852 const bool minus_p
= (code
== MINUS_EXPR
);
855 /* Try with VR0 and [-INF, OP1]. */
856 if (is_gimple_min_invariant (minus_p
? vr0
.max () : vr0
.min ()))
857 n_vr1
.set (vrp_val_min (expr_type
), op1
);
859 /* Try with VR0 and [OP1, +INF]. */
860 else if (is_gimple_min_invariant (minus_p
? vr0
.min () : vr0
.max ()))
861 n_vr1
.set (op1
, vrp_val_max (expr_type
));
863 /* Try with VR0 and [OP1, OP1]. */
865 n_vr1
.set (op1
, op1
);
867 range_fold_binary_expr (vr
, code
, expr_type
, &vr0
, &n_vr1
);
871 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
872 && TREE_CODE (op0
) == SSA_NAME
873 && vr1
.kind () == VR_RANGE
874 && symbolic_range_based_on_p (&vr1
, op0
))
876 const bool minus_p
= (code
== MINUS_EXPR
);
879 /* Try with [-INF, OP0] and VR1. */
880 if (is_gimple_min_invariant (minus_p
? vr1
.max () : vr1
.min ()))
881 n_vr0
.set (vrp_val_min (expr_type
), op0
);
883 /* Try with [OP0, +INF] and VR1. */
884 else if (is_gimple_min_invariant (minus_p
? vr1
.min (): vr1
.max ()))
885 n_vr0
.set (op0
, vrp_val_max (expr_type
));
887 /* Try with [OP0, OP0] and VR1. */
891 range_fold_binary_expr (vr
, code
, expr_type
, &n_vr0
, &vr1
);
894 /* If we didn't derive a range for MINUS_EXPR, and
895 op1's range is ~[op0,op0] or vice-versa, then we
896 can derive a non-null range. This happens often for
897 pointer subtraction. */
899 && (code
== MINUS_EXPR
|| code
== POINTER_DIFF_EXPR
)
900 && TREE_CODE (op0
) == SSA_NAME
901 && ((vr0
.kind () == VR_ANTI_RANGE
903 && vr0
.min () == vr0
.max ())
904 || (vr1
.kind () == VR_ANTI_RANGE
906 && vr1
.min () == vr1
.max ())))
908 vr
->set_nonzero (expr_type
);
913 /* Extract range information from a unary expression CODE OP0 based on
914 the range of its operand with resulting type TYPE.
915 The resulting range is stored in *VR. */
918 vr_values::extract_range_from_unary_expr (value_range_equiv
*vr
,
924 /* Get value ranges for the operand. For constant operands, create
925 a new value range with the operand to simplify processing. */
926 if (TREE_CODE (op0
) == SSA_NAME
)
927 vr0
= *(get_value_range (op0
));
928 else if (is_gimple_min_invariant (op0
))
931 vr0
.set_varying (type
);
933 range_fold_unary_expr (vr
, code
, type
, &vr0
, TREE_TYPE (op0
));
937 /* Extract range information from a conditional expression STMT based on
938 the ranges of each of its operands and the expression code. */
941 vr_values::extract_range_from_cond_expr (value_range_equiv
*vr
, gassign
*stmt
)
943 /* Get value ranges for each operand. For constant operands, create
944 a new value range with the operand to simplify processing. */
945 tree op0
= gimple_assign_rhs2 (stmt
);
946 value_range_equiv tem0
;
947 const value_range_equiv
*vr0
= &tem0
;
948 if (TREE_CODE (op0
) == SSA_NAME
)
949 vr0
= get_value_range (op0
);
950 else if (is_gimple_min_invariant (op0
))
953 tem0
.set_varying (TREE_TYPE (op0
));
955 tree op1
= gimple_assign_rhs3 (stmt
);
956 value_range_equiv tem1
;
957 const value_range_equiv
*vr1
= &tem1
;
958 if (TREE_CODE (op1
) == SSA_NAME
)
959 vr1
= get_value_range (op1
);
960 else if (is_gimple_min_invariant (op1
))
963 tem1
.set_varying (TREE_TYPE (op1
));
965 /* The resulting value range is the union of the operand ranges */
971 /* Extract range information from a comparison expression EXPR based
972 on the range of its operand and the expression code. */
975 vr_values::extract_range_from_comparison (value_range_equiv
*vr
,
978 enum tree_code code
= gimple_assign_rhs_code (stmt
);
979 tree type
= gimple_expr_type (stmt
);
980 tree op0
= gimple_assign_rhs1 (stmt
);
981 tree op1
= gimple_assign_rhs2 (stmt
);
984 = simplifier
.vrp_evaluate_conditional_warnv_with_ops (stmt
, code
, op0
, op1
,
988 /* Since this expression was found on the RHS of an assignment,
989 its type may be different from _Bool. Convert VAL to EXPR's
991 val
= fold_convert (type
, val
);
992 if (is_gimple_min_invariant (val
))
995 vr
->update (val
, val
);
998 /* The result of a comparison is always true or false. */
999 set_value_range_to_truthvalue (vr
, type
);
1002 /* Helper function for simplify_internal_call_using_ranges and
1003 extract_range_basic. Return true if OP0 SUBCODE OP1 for
1004 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
1005 always overflow. Set *OVF to true if it is known to always
1009 check_for_binary_op_overflow (range_query
*store
,
1010 enum tree_code subcode
, tree type
,
1011 tree op0
, tree op1
, bool *ovf
)
1013 value_range vr0
, vr1
;
1014 if (TREE_CODE (op0
) == SSA_NAME
)
1015 vr0
= *store
->get_value_range (op0
);
1016 else if (TREE_CODE (op0
) == INTEGER_CST
)
1019 vr0
.set_varying (TREE_TYPE (op0
));
1021 if (TREE_CODE (op1
) == SSA_NAME
)
1022 vr1
= *store
->get_value_range (op1
);
1023 else if (TREE_CODE (op1
) == INTEGER_CST
)
1026 vr1
.set_varying (TREE_TYPE (op1
));
1028 tree vr0min
= vr0
.min (), vr0max
= vr0
.max ();
1029 tree vr1min
= vr1
.min (), vr1max
= vr1
.max ();
1030 if (!range_int_cst_p (&vr0
)
1031 || TREE_OVERFLOW (vr0min
)
1032 || TREE_OVERFLOW (vr0max
))
1034 vr0min
= vrp_val_min (TREE_TYPE (op0
));
1035 vr0max
= vrp_val_max (TREE_TYPE (op0
));
1037 if (!range_int_cst_p (&vr1
)
1038 || TREE_OVERFLOW (vr1min
)
1039 || TREE_OVERFLOW (vr1max
))
1041 vr1min
= vrp_val_min (TREE_TYPE (op1
));
1042 vr1max
= vrp_val_max (TREE_TYPE (op1
));
1044 *ovf
= arith_overflowed_p (subcode
, type
, vr0min
,
1045 subcode
== MINUS_EXPR
? vr1max
: vr1min
);
1046 if (arith_overflowed_p (subcode
, type
, vr0max
,
1047 subcode
== MINUS_EXPR
? vr1min
: vr1max
) != *ovf
)
1049 if (subcode
== MULT_EXPR
)
1051 if (arith_overflowed_p (subcode
, type
, vr0min
, vr1max
) != *ovf
1052 || arith_overflowed_p (subcode
, type
, vr0max
, vr1min
) != *ovf
)
1057 /* So far we found that there is an overflow on the boundaries.
1058 That doesn't prove that there is an overflow even for all values
1059 in between the boundaries. For that compute widest_int range
1060 of the result and see if it doesn't overlap the range of
1062 widest_int wmin
, wmax
;
1065 w
[0] = wi::to_widest (vr0min
);
1066 w
[1] = wi::to_widest (vr0max
);
1067 w
[2] = wi::to_widest (vr1min
);
1068 w
[3] = wi::to_widest (vr1max
);
1069 for (i
= 0; i
< 4; i
++)
1075 wt
= wi::add (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1078 wt
= wi::sub (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1081 wt
= wi::mul (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1093 wmin
= wi::smin (wmin
, wt
);
1094 wmax
= wi::smax (wmax
, wt
);
1097 /* The result of op0 CODE op1 is known to be in range
1099 widest_int wtmin
= wi::to_widest (vrp_val_min (type
));
1100 widest_int wtmax
= wi::to_widest (vrp_val_max (type
));
1101 /* If all values in [wmin, wmax] are smaller than
1102 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1103 the arithmetic operation will always overflow. */
1104 if (wmax
< wtmin
|| wmin
> wtmax
)
1111 /* Try to derive a nonnegative or nonzero range out of STMT relying
1112 primarily on generic routines in fold in conjunction with range data.
1113 Store the result in *VR */
1116 vr_values::extract_range_basic (value_range_equiv
*vr
, gimple
*stmt
)
1119 tree type
= gimple_expr_type (stmt
);
1121 if (is_gimple_call (stmt
))
1124 int mini
, maxi
, zerov
= 0, prec
;
1125 enum tree_code subcode
= ERROR_MARK
;
1126 combined_fn cfn
= gimple_call_combined_fn (stmt
);
1127 scalar_int_mode mode
;
1131 case CFN_BUILT_IN_CONSTANT_P
:
1132 /* Resolve calls to __builtin_constant_p after inlining. */
1133 if (cfun
->after_inlining
)
1135 vr
->set_zero (type
);
1140 /* Both __builtin_ffs* and __builtin_popcount return
1144 arg
= gimple_call_arg (stmt
, 0);
1145 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1148 if (TREE_CODE (arg
) == SSA_NAME
)
1150 const value_range_equiv
*vr0
= get_value_range (arg
);
1151 /* If arg is non-zero, then ffs or popcount are non-zero. */
1152 if (range_includes_zero_p (vr0
) == 0)
1154 /* If some high bits are known to be zero,
1155 we can decrease the maximum. */
1156 if (vr0
->kind () == VR_RANGE
1157 && TREE_CODE (vr0
->max ()) == INTEGER_CST
1158 && !operand_less_p (vr0
->min (),
1159 build_zero_cst (TREE_TYPE (vr0
->min ()))))
1160 maxi
= tree_floor_log2 (vr0
->max ()) + 1;
1163 /* __builtin_parity* returns [0, 1]. */
1168 /* __builtin_c[lt]z* return [0, prec-1], except for
1169 when the argument is 0, but that is undefined behavior.
1170 On many targets where the CLZ RTL or optab value is defined
1171 for 0 the value is prec, so include that in the range
1174 arg
= gimple_call_arg (stmt
, 0);
1175 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1178 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1179 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
1180 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
)
1181 /* Handle only the single common value. */
1183 /* Magic value to give up, unless vr0 proves
1186 if (TREE_CODE (arg
) == SSA_NAME
)
1188 const value_range_equiv
*vr0
= get_value_range (arg
);
1189 /* From clz of VR_RANGE minimum we can compute
1191 if (vr0
->kind () == VR_RANGE
1192 && TREE_CODE (vr0
->min ()) == INTEGER_CST
)
1194 maxi
= prec
- 1 - tree_floor_log2 (vr0
->min ());
1198 else if (vr0
->kind () == VR_ANTI_RANGE
1199 && integer_zerop (vr0
->min ()))
1206 /* From clz of VR_RANGE maximum we can compute
1208 if (vr0
->kind () == VR_RANGE
1209 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1211 mini
= prec
- 1 - tree_floor_log2 (vr0
->max ());
1219 /* __builtin_ctz* return [0, prec-1], except for
1220 when the argument is 0, but that is undefined behavior.
1221 If there is a ctz optab for this mode and
1222 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1223 otherwise just assume 0 won't be seen. */
1225 arg
= gimple_call_arg (stmt
, 0);
1226 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1229 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1230 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1231 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
))
1233 /* Handle only the two common values. */
1236 else if (zerov
== prec
)
1239 /* Magic value to give up, unless vr0 proves
1243 if (TREE_CODE (arg
) == SSA_NAME
)
1245 const value_range_equiv
*vr0
= get_value_range (arg
);
1246 /* If arg is non-zero, then use [0, prec - 1]. */
1247 if ((vr0
->kind () == VR_RANGE
1248 && integer_nonzerop (vr0
->min ()))
1249 || (vr0
->kind () == VR_ANTI_RANGE
1250 && integer_zerop (vr0
->min ())))
1255 /* If some high bits are known to be zero,
1256 we can decrease the result maximum. */
1257 if (vr0
->kind () == VR_RANGE
1258 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1260 maxi
= tree_floor_log2 (vr0
->max ());
1261 /* For vr0 [0, 0] give up. */
1269 /* __builtin_clrsb* returns [0, prec-1]. */
1271 arg
= gimple_call_arg (stmt
, 0);
1272 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1277 vr
->set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
1279 case CFN_UBSAN_CHECK_ADD
:
1280 subcode
= PLUS_EXPR
;
1282 case CFN_UBSAN_CHECK_SUB
:
1283 subcode
= MINUS_EXPR
;
1285 case CFN_UBSAN_CHECK_MUL
:
1286 subcode
= MULT_EXPR
;
1288 case CFN_GOACC_DIM_SIZE
:
1289 case CFN_GOACC_DIM_POS
:
1290 /* Optimizing these two internal functions helps the loop
1291 optimizer eliminate outer comparisons. Size is [1,N]
1292 and pos is [0,N-1]. */
1294 bool is_pos
= cfn
== CFN_GOACC_DIM_POS
;
1295 int axis
= oacc_get_ifn_dim_arg (stmt
);
1296 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1299 /* If it's dynamic, the backend might know a hardware
1301 size
= targetm
.goacc
.dim_limit (axis
);
1303 tree type
= TREE_TYPE (gimple_call_lhs (stmt
));
1304 vr
->set(build_int_cst (type
, is_pos
? 0 : 1),
1306 ? build_int_cst (type
, size
- is_pos
) : vrp_val_max (type
));
1309 case CFN_BUILT_IN_STRLEN
:
1310 if (tree lhs
= gimple_call_lhs (stmt
))
1311 if (ptrdiff_type_node
1312 && (TYPE_PRECISION (ptrdiff_type_node
)
1313 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1315 tree type
= TREE_TYPE (lhs
);
1316 tree max
= vrp_val_max (ptrdiff_type_node
);
1317 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1318 tree range_min
= build_zero_cst (type
);
1319 /* To account for the terminating NUL, the maximum length
1320 is one less than the maximum array size, which in turn
1321 is one less than PTRDIFF_MAX (or SIZE_MAX where it's
1322 smaller than the former type).
1323 FIXME: Use max_object_size() - 1 here. */
1324 tree range_max
= wide_int_to_tree (type
, wmax
- 2);
1325 vr
->set (range_min
, range_max
);
1332 if (subcode
!= ERROR_MARK
)
1334 bool saved_flag_wrapv
= flag_wrapv
;
1335 /* Pretend the arithmetics is wrapping. If there is
1336 any overflow, we'll complain, but will actually do
1337 wrapping operation. */
1339 extract_range_from_binary_expr (vr
, subcode
, type
,
1340 gimple_call_arg (stmt
, 0),
1341 gimple_call_arg (stmt
, 1));
1342 flag_wrapv
= saved_flag_wrapv
;
1344 /* If for both arguments vrp_valueize returned non-NULL,
1345 this should have been already folded and if not, it
1346 wasn't folded because of overflow. Avoid removing the
1347 UBSAN_CHECK_* calls in that case. */
1348 if (vr
->kind () == VR_RANGE
1349 && (vr
->min () == vr
->max ()
1350 || operand_equal_p (vr
->min (), vr
->max (), 0)))
1351 vr
->set_varying (vr
->type ());
1355 /* Handle extraction of the two results (result of arithmetics and
1356 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1357 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1358 else if (is_gimple_assign (stmt
)
1359 && (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
1360 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
)
1361 && INTEGRAL_TYPE_P (type
))
1363 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1364 tree op
= gimple_assign_rhs1 (stmt
);
1365 if (TREE_CODE (op
) == code
&& TREE_CODE (TREE_OPERAND (op
, 0)) == SSA_NAME
)
1367 gimple
*g
= SSA_NAME_DEF_STMT (TREE_OPERAND (op
, 0));
1368 if (is_gimple_call (g
) && gimple_call_internal_p (g
))
1370 enum tree_code subcode
= ERROR_MARK
;
1371 switch (gimple_call_internal_fn (g
))
1373 case IFN_ADD_OVERFLOW
:
1374 subcode
= PLUS_EXPR
;
1376 case IFN_SUB_OVERFLOW
:
1377 subcode
= MINUS_EXPR
;
1379 case IFN_MUL_OVERFLOW
:
1380 subcode
= MULT_EXPR
;
1382 case IFN_ATOMIC_COMPARE_EXCHANGE
:
1383 if (code
== IMAGPART_EXPR
)
1385 /* This is the boolean return value whether compare and
1386 exchange changed anything or not. */
1387 vr
->set (build_int_cst (type
, 0),
1388 build_int_cst (type
, 1));
1395 if (subcode
!= ERROR_MARK
)
1397 tree op0
= gimple_call_arg (g
, 0);
1398 tree op1
= gimple_call_arg (g
, 1);
1399 if (code
== IMAGPART_EXPR
)
1402 if (check_for_binary_op_overflow (this, subcode
, type
,
1404 vr
->set (build_int_cst (type
, ovf
));
1405 else if (TYPE_PRECISION (type
) == 1
1406 && !TYPE_UNSIGNED (type
))
1407 vr
->set_varying (type
);
1409 vr
->set (build_int_cst (type
, 0),
1410 build_int_cst (type
, 1));
1412 else if (types_compatible_p (type
, TREE_TYPE (op0
))
1413 && types_compatible_p (type
, TREE_TYPE (op1
)))
1415 bool saved_flag_wrapv
= flag_wrapv
;
1416 /* Pretend the arithmetics is wrapping. If there is
1417 any overflow, IMAGPART_EXPR will be set. */
1419 extract_range_from_binary_expr (vr
, subcode
, type
,
1421 flag_wrapv
= saved_flag_wrapv
;
1425 value_range_equiv vr0
, vr1
;
1426 bool saved_flag_wrapv
= flag_wrapv
;
1427 /* Pretend the arithmetics is wrapping. If there is
1428 any overflow, IMAGPART_EXPR will be set. */
1430 extract_range_from_unary_expr (&vr0
, NOP_EXPR
,
1432 extract_range_from_unary_expr (&vr1
, NOP_EXPR
,
1434 range_fold_binary_expr (vr
, subcode
, type
, &vr0
, &vr1
);
1435 flag_wrapv
= saved_flag_wrapv
;
1442 if (INTEGRAL_TYPE_P (type
)
1443 && gimple_stmt_nonnegative_warnv_p (stmt
, &sop
))
1444 set_value_range_to_nonnegative (vr
, type
);
1445 else if (vrp_stmt_computes_nonzero (stmt
))
1447 vr
->set_nonzero (type
);
1451 vr
->set_varying (type
);
1455 /* Try to compute a useful range out of assignment STMT and store it
1459 vr_values::extract_range_from_assignment (value_range_equiv
*vr
, gassign
*stmt
)
1461 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1463 if (code
== ASSERT_EXPR
)
1464 extract_range_from_assert (vr
, gimple_assign_rhs1 (stmt
));
1465 else if (code
== SSA_NAME
)
1466 extract_range_from_ssa_name (vr
, gimple_assign_rhs1 (stmt
));
1467 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
1468 extract_range_from_binary_expr (vr
, gimple_assign_rhs_code (stmt
),
1469 gimple_expr_type (stmt
),
1470 gimple_assign_rhs1 (stmt
),
1471 gimple_assign_rhs2 (stmt
));
1472 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1473 extract_range_from_unary_expr (vr
, gimple_assign_rhs_code (stmt
),
1474 gimple_expr_type (stmt
),
1475 gimple_assign_rhs1 (stmt
));
1476 else if (code
== COND_EXPR
)
1477 extract_range_from_cond_expr (vr
, stmt
);
1478 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1479 extract_range_from_comparison (vr
, stmt
);
1480 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1481 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1482 vr
->set (gimple_assign_rhs1 (stmt
));
1484 vr
->set_varying (TREE_TYPE (gimple_assign_lhs (stmt
)));
1486 if (vr
->varying_p ())
1487 extract_range_basic (vr
, stmt
);
1490 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1492 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1493 all the values in the ranges.
1495 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1497 - Return NULL_TREE if it is not always possible to determine the
1498 value of the comparison.
1500 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1501 assumed signed overflow is undefined. */
1505 compare_ranges (enum tree_code comp
, const value_range_equiv
*vr0
,
1506 const value_range_equiv
*vr1
, bool *strict_overflow_p
)
1508 /* VARYING or UNDEFINED ranges cannot be compared. */
1509 if (vr0
->varying_p ()
1510 || vr0
->undefined_p ()
1511 || vr1
->varying_p ()
1512 || vr1
->undefined_p ())
1515 /* Anti-ranges need to be handled separately. */
1516 if (vr0
->kind () == VR_ANTI_RANGE
|| vr1
->kind () == VR_ANTI_RANGE
)
1518 /* If both are anti-ranges, then we cannot compute any
1520 if (vr0
->kind () == VR_ANTI_RANGE
&& vr1
->kind () == VR_ANTI_RANGE
)
1523 /* These comparisons are never statically computable. */
1530 /* Equality can be computed only between a range and an
1531 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1532 if (vr0
->kind () == VR_RANGE
)
1533 /* To simplify processing, make VR0 the anti-range. */
1534 std::swap (vr0
, vr1
);
1536 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1538 if (compare_values_warnv (vr0
->min (), vr1
->min (), strict_overflow_p
) == 0
1539 && compare_values_warnv (vr0
->max (), vr1
->max (), strict_overflow_p
) == 0)
1540 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1545 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1546 operands around and change the comparison code. */
1547 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1549 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1550 std::swap (vr0
, vr1
);
1553 if (comp
== EQ_EXPR
)
1555 /* Equality may only be computed if both ranges represent
1556 exactly one value. */
1557 if (compare_values_warnv (vr0
->min (), vr0
->max (), strict_overflow_p
) == 0
1558 && compare_values_warnv (vr1
->min (), vr1
->max (), strict_overflow_p
) == 0)
1560 int cmp_min
= compare_values_warnv (vr0
->min (), vr1
->min (),
1562 int cmp_max
= compare_values_warnv (vr0
->max (), vr1
->max (),
1564 if (cmp_min
== 0 && cmp_max
== 0)
1565 return boolean_true_node
;
1566 else if (cmp_min
!= -2 && cmp_max
!= -2)
1567 return boolean_false_node
;
1569 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1570 else if (compare_values_warnv (vr0
->min (), vr1
->max (),
1571 strict_overflow_p
) == 1
1572 || compare_values_warnv (vr1
->min (), vr0
->max (),
1573 strict_overflow_p
) == 1)
1574 return boolean_false_node
;
1578 else if (comp
== NE_EXPR
)
1582 /* If VR0 is completely to the left or completely to the right
1583 of VR1, they are always different. Notice that we need to
1584 make sure that both comparisons yield similar results to
1585 avoid comparing values that cannot be compared at
1587 cmp1
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1588 cmp2
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1589 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1590 return boolean_true_node
;
1592 /* If VR0 and VR1 represent a single value and are identical,
1594 else if (compare_values_warnv (vr0
->min (), vr0
->max (),
1595 strict_overflow_p
) == 0
1596 && compare_values_warnv (vr1
->min (), vr1
->max (),
1597 strict_overflow_p
) == 0
1598 && compare_values_warnv (vr0
->min (), vr1
->min (),
1599 strict_overflow_p
) == 0
1600 && compare_values_warnv (vr0
->max (), vr1
->max (),
1601 strict_overflow_p
) == 0)
1602 return boolean_false_node
;
1604 /* Otherwise, they may or may not be different. */
1608 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1612 /* If VR0 is to the left of VR1, return true. */
1613 tst
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1614 if ((comp
== LT_EXPR
&& tst
== -1)
1615 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1616 return boolean_true_node
;
1618 /* If VR0 is to the right of VR1, return false. */
1619 tst
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1620 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1621 || (comp
== LE_EXPR
&& tst
== 1))
1622 return boolean_false_node
;
1624 /* Otherwise, we don't know. */
1631 /* Given a value range VR, a value VAL and a comparison code COMP, return
1632 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1633 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1634 always returns false. Return NULL_TREE if it is not always
1635 possible to determine the value of the comparison. Also set
1636 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1637 assumed signed overflow is undefined. */
1640 compare_range_with_value (enum tree_code comp
, const value_range
*vr
,
1641 tree val
, bool *strict_overflow_p
)
1643 if (vr
->varying_p () || vr
->undefined_p ())
1646 /* Anti-ranges need to be handled separately. */
1647 if (vr
->kind () == VR_ANTI_RANGE
)
1649 /* For anti-ranges, the only predicates that we can compute at
1650 compile time are equality and inequality. */
1657 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1658 if (!vr
->may_contain_p (val
))
1659 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1664 if (comp
== EQ_EXPR
)
1666 /* EQ_EXPR may only be computed if VR represents exactly
1668 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0)
1670 int cmp
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1672 return boolean_true_node
;
1673 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1674 return boolean_false_node
;
1676 else if (compare_values_warnv (val
, vr
->min (), strict_overflow_p
) == -1
1677 || compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1)
1678 return boolean_false_node
;
1682 else if (comp
== NE_EXPR
)
1684 /* If VAL is not inside VR, then they are always different. */
1685 if (compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1
1686 || compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 1)
1687 return boolean_true_node
;
1689 /* If VR represents exactly one value equal to VAL, then return
1691 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0
1692 && compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 0)
1693 return boolean_false_node
;
1695 /* Otherwise, they may or may not be different. */
1698 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1702 /* If VR is to the left of VAL, return true. */
1703 tst
= compare_values_warnv (vr
->max (), val
, 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 VR is to the right of VAL, return false. */
1709 tst
= compare_values_warnv (vr
->min (), val
, 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. */
1717 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1721 /* If VR is to the right of VAL, return true. */
1722 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1723 if ((comp
== GT_EXPR
&& tst
== 1)
1724 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1725 return boolean_true_node
;
1727 /* If VR is to the left of VAL, return false. */
1728 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1729 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1730 || (comp
== GE_EXPR
&& tst
== -1))
1731 return boolean_false_node
;
1733 /* Otherwise, we don't know. */
1740 /* Given a VAR in STMT within LOOP, determine the bounds of the
1741 variable and store it in MIN/MAX and return TRUE. If no bounds
1742 could be determined, return FALSE. */
1745 bounds_of_var_in_loop (tree
*min
, tree
*max
, range_query
*query
,
1746 class loop
*loop
, gimple
*stmt
, tree var
)
1748 tree init
, step
, chrec
, tmin
, tmax
, type
= TREE_TYPE (var
);
1749 enum ev_direction dir
;
1751 chrec
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, var
));
1753 /* Like in PR19590, scev can return a constant function. */
1754 if (is_gimple_min_invariant (chrec
))
1756 *min
= *max
= chrec
;
1760 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1763 init
= initial_condition_in_loop_num (chrec
, loop
->num
);
1764 step
= evolution_part_in_loop_num (chrec
, loop
->num
);
1766 /* If INIT is an SSA with a singleton range, set INIT to said
1767 singleton, otherwise leave INIT alone. */
1768 if (TREE_CODE (init
) == SSA_NAME
)
1769 query
->get_value_range (init
, stmt
)->singleton_p (&init
);
1770 /* Likewise for step. */
1771 if (TREE_CODE (step
) == SSA_NAME
)
1772 query
->get_value_range (step
, stmt
)->singleton_p (&step
);
1774 /* If STEP is symbolic, we can't know whether INIT will be the
1775 minimum or maximum value in the range. Also, unless INIT is
1776 a simple expression, compare_values and possibly other functions
1777 in tree-vrp won't be able to handle it. */
1778 if (step
== NULL_TREE
1779 || !is_gimple_min_invariant (step
)
1780 || !valid_value_p (init
))
1783 dir
= scev_direction (chrec
);
1784 if (/* Do not adjust ranges if we do not know whether the iv increases
1785 or decreases, ... */
1786 dir
== EV_DIR_UNKNOWN
1787 /* ... or if it may wrap. */
1788 || scev_probably_wraps_p (NULL_TREE
, init
, step
, stmt
,
1789 get_chrec_loop (chrec
), true))
1792 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1793 tmin
= lower_bound_in_type (type
, type
);
1795 tmin
= TYPE_MIN_VALUE (type
);
1796 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1797 tmax
= upper_bound_in_type (type
, type
);
1799 tmax
= TYPE_MAX_VALUE (type
);
1801 /* Try to use estimated number of iterations for the loop to constrain the
1802 final value in the evolution. */
1803 if (TREE_CODE (step
) == INTEGER_CST
1804 && is_gimple_val (init
)
1805 && (TREE_CODE (init
) != SSA_NAME
1806 || query
->get_value_range (init
, stmt
)->kind () == VR_RANGE
))
1810 /* We are only entering here for loop header PHI nodes, so using
1811 the number of latch executions is the correct thing to use. */
1812 if (max_loop_iterations (loop
, &nit
))
1814 signop sgn
= TYPE_SIGN (TREE_TYPE (step
));
1815 wi::overflow_type overflow
;
1817 widest_int wtmp
= wi::mul (wi::to_widest (step
), nit
, sgn
,
1819 /* If the multiplication overflowed we can't do a meaningful
1820 adjustment. Likewise if the result doesn't fit in the type
1821 of the induction variable. For a signed type we have to
1822 check whether the result has the expected signedness which
1823 is that of the step as number of iterations is unsigned. */
1825 && wi::fits_to_tree_p (wtmp
, TREE_TYPE (init
))
1827 || wi::gts_p (wtmp
, 0) == wi::gts_p (wi::to_wide (step
), 0)))
1829 value_range maxvr
, vr0
, vr1
;
1830 if (TREE_CODE (init
) == SSA_NAME
)
1831 vr0
= *(query
->get_value_range (init
, stmt
));
1832 else if (is_gimple_min_invariant (init
))
1835 vr0
.set_varying (TREE_TYPE (init
));
1836 tree tem
= wide_int_to_tree (TREE_TYPE (init
), wtmp
);
1838 range_fold_binary_expr (&maxvr
, PLUS_EXPR
,
1839 TREE_TYPE (init
), &vr0
, &vr1
);
1841 /* Likewise if the addition did. */
1842 if (maxvr
.kind () == VR_RANGE
)
1846 if (TREE_CODE (init
) == SSA_NAME
)
1847 initvr
= *(query
->get_value_range (init
, stmt
));
1848 else if (is_gimple_min_invariant (init
))
1853 /* Check if init + nit * step overflows. Though we checked
1854 scev {init, step}_loop doesn't wrap, it is not enough
1855 because the loop may exit immediately. Overflow could
1856 happen in the plus expression in this case. */
1857 if ((dir
== EV_DIR_DECREASES
1858 && compare_values (maxvr
.min (), initvr
.min ()) != -1)
1859 || (dir
== EV_DIR_GROWS
1860 && compare_values (maxvr
.max (), initvr
.max ()) != 1))
1863 tmin
= maxvr
.min ();
1864 tmax
= maxvr
.max ();
1872 if (dir
== EV_DIR_DECREASES
)
1877 /* Even for valid range info, sometimes overflow flag will leak in.
1878 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1880 if (TREE_OVERFLOW_P (*min
))
1881 *min
= drop_tree_overflow (*min
);
1882 if (TREE_OVERFLOW_P (*max
))
1883 *max
= drop_tree_overflow (*max
);
1885 gcc_checking_assert (compare_values (*min
, *max
) != 1);
1889 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1890 would be profitable to adjust VR using scalar evolution information
1891 for VAR. If so, update VR with the new limits. */
1894 vr_values::adjust_range_with_scev (value_range_equiv
*vr
, class loop
*loop
,
1895 gimple
*stmt
, tree var
)
1898 if (bounds_of_var_in_loop (&min
, &max
, this, loop
, stmt
, var
))
1900 if (vr
->undefined_p () || vr
->varying_p ())
1902 /* For VARYING or UNDEFINED ranges, just about anything we get
1903 from scalar evolutions should be better. */
1904 vr
->update (min
, max
);
1906 else if (vr
->kind () == VR_RANGE
)
1908 /* Start with the input range... */
1909 tree vrmin
= vr
->min ();
1910 tree vrmax
= vr
->max ();
1912 /* ...and narrow it down with what we got from SCEV. */
1913 if (compare_values (min
, vrmin
) == 1)
1915 if (compare_values (max
, vrmax
) == -1)
1918 vr
->update (vrmin
, vrmax
);
1920 else if (vr
->kind () == VR_ANTI_RANGE
)
1922 /* ?? As an enhancement, if VR, MIN, and MAX are constants, one
1923 could just intersect VR with a range of [MIN,MAX]. */
1928 /* Dump value ranges of all SSA_NAMEs to FILE. */
1931 vr_values::dump_all_value_ranges (FILE *file
)
1935 for (i
= 0; i
< num_vr_values
; i
++)
1939 print_generic_expr (file
, ssa_name (i
));
1940 fprintf (file
, ": ");
1941 dump_value_range (file
, vr_value
[i
]);
1942 fprintf (file
, "\n");
1946 fprintf (file
, "\n");
1949 /* Initialize VRP lattice. */
1951 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges"),
1954 values_propagated
= false;
1955 num_vr_values
= num_ssa_names
* 2;
1956 vr_value
= XCNEWVEC (value_range_equiv
*, num_vr_values
);
1957 vr_phi_edge_counts
= XCNEWVEC (int, num_ssa_names
);
1958 bitmap_obstack_initialize (&vrp_equiv_obstack
);
1961 /* Free VRP lattice. */
1963 vr_values::~vr_values ()
1965 /* Free allocated memory. */
1967 free (vr_phi_edge_counts
);
1968 bitmap_obstack_release (&vrp_equiv_obstack
);
1969 vrp_value_range_pool
.release ();
1971 /* So that we can distinguish between VRP data being available
1972 and not available. */
1974 vr_phi_edge_counts
= NULL
;
1979 static class vr_values
*x_vr_values
;
1981 /* Return the singleton value-range for NAME or NAME. */
1984 vrp_valueize (tree name
)
1986 if (TREE_CODE (name
) == SSA_NAME
)
1988 const value_range_equiv
*vr
= x_vr_values
->get_value_range (name
);
1989 if (vr
->kind () == VR_RANGE
1990 && (TREE_CODE (vr
->min ()) == SSA_NAME
1991 || is_gimple_min_invariant (vr
->min ()))
1992 && vrp_operand_equal_p (vr
->min (), vr
->max ()))
1998 /* Return the singleton value-range for NAME if that is a constant
1999 but signal to not follow SSA edges. */
2002 vrp_valueize_1 (tree name
)
2004 if (TREE_CODE (name
) == SSA_NAME
)
2006 /* If the definition may be simulated again we cannot follow
2007 this SSA edge as the SSA propagator does not necessarily
2008 re-visit the use. */
2009 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
2010 if (!gimple_nop_p (def_stmt
)
2011 && prop_simulate_again_p (def_stmt
))
2013 const value_range_equiv
*vr
= x_vr_values
->get_value_range (name
);
2015 if (vr
->singleton_p (&singleton
))
2021 /* Given STMT, an assignment or call, return its LHS if the type
2022 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
2025 get_output_for_vrp (gimple
*stmt
)
2027 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2030 /* We only keep track of ranges in integral and pointer types. */
2031 tree lhs
= gimple_get_lhs (stmt
);
2032 if (TREE_CODE (lhs
) == SSA_NAME
2033 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2034 /* It is valid to have NULL MIN/MAX values on a type. See
2035 build_range_type. */
2036 && TYPE_MIN_VALUE (TREE_TYPE (lhs
))
2037 && TYPE_MAX_VALUE (TREE_TYPE (lhs
)))
2038 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
2044 /* Visit assignment STMT. If it produces an interesting range, record
2045 the range in VR and set LHS to OUTPUT_P. */
2048 vr_values::vrp_visit_assignment_or_call (gimple
*stmt
, tree
*output_p
,
2049 value_range_equiv
*vr
)
2051 tree lhs
= get_output_for_vrp (stmt
);
2054 /* We only keep track of ranges in integral and pointer types. */
2057 enum gimple_code code
= gimple_code (stmt
);
2059 /* Try folding the statement to a constant first. */
2061 tree tem
= gimple_fold_stmt_to_constant_1 (stmt
, vrp_valueize
,
2066 if (TREE_CODE (tem
) == SSA_NAME
2067 && (SSA_NAME_IS_DEFAULT_DEF (tem
)
2068 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem
))))
2070 extract_range_from_ssa_name (vr
, tem
);
2073 else if (is_gimple_min_invariant (tem
))
2079 /* Then dispatch to value-range extracting functions. */
2080 if (code
== GIMPLE_CALL
)
2081 extract_range_basic (vr
, stmt
);
2083 extract_range_from_assignment (vr
, as_a
<gassign
*> (stmt
));
2087 /* Helper that gets the value range of the SSA_NAME with version I
2088 or a symbolic range containing the SSA_NAME only if the value range
2089 is varying or undefined. Uses TEM as storage for the alternate range. */
2091 const value_range_equiv
*
2092 simplify_using_ranges::get_vr_for_comparison (int i
, value_range_equiv
*tem
)
2094 /* Shallow-copy equiv bitmap. */
2095 const value_range_equiv
*vr
= get_value_range (ssa_name (i
));
2097 /* If name N_i does not have a valid range, use N_i as its own
2098 range. This allows us to compare against names that may
2099 have N_i in their ranges. */
2100 if (vr
->varying_p () || vr
->undefined_p ())
2102 tem
->set (ssa_name (i
));
2109 /* Compare all the value ranges for names equivalent to VAR with VAL
2110 using comparison code COMP. Return the same value returned by
2111 compare_range_with_value, including the setting of
2112 *STRICT_OVERFLOW_P. */
2115 simplify_using_ranges::compare_name_with_value
2116 (enum tree_code comp
, tree var
, tree val
,
2117 bool *strict_overflow_p
, bool use_equiv_p
)
2119 /* Get the set of equivalences for VAR. */
2120 bitmap e
= get_value_range (var
)->equiv ();
2122 /* Start at -1. Set it to 0 if we do a comparison without relying
2123 on overflow, or 1 if all comparisons rely on overflow. */
2124 int used_strict_overflow
= -1;
2126 /* Compare vars' value range with val. */
2127 value_range_equiv tem_vr
;
2128 const value_range_equiv
*equiv_vr
2129 = get_vr_for_comparison (SSA_NAME_VERSION (var
), &tem_vr
);
2131 tree retval
= compare_range_with_value (comp
, equiv_vr
, val
, &sop
);
2133 used_strict_overflow
= sop
? 1 : 0;
2135 /* If the equiv set is empty we have done all work we need to do. */
2138 if (retval
&& used_strict_overflow
> 0)
2139 *strict_overflow_p
= true;
2145 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2147 tree name
= ssa_name (i
);
2152 && !SSA_NAME_IS_DEFAULT_DEF (name
)
2153 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name
)))
2156 equiv_vr
= get_vr_for_comparison (i
, &tem_vr
);
2158 tree t
= compare_range_with_value (comp
, equiv_vr
, val
, &sop
);
2161 /* If we get different answers from different members
2162 of the equivalence set this check must be in a dead
2163 code region. Folding it to a trap representation
2164 would be correct here. For now just return don't-know. */
2174 used_strict_overflow
= 0;
2175 else if (used_strict_overflow
< 0)
2176 used_strict_overflow
= 1;
2180 if (retval
&& used_strict_overflow
> 0)
2181 *strict_overflow_p
= true;
2187 /* Given a comparison code COMP and names N1 and N2, compare all the
2188 ranges equivalent to N1 against all the ranges equivalent to N2
2189 to determine the value of N1 COMP N2. Return the same value
2190 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2191 whether we relied on undefined signed overflow in the comparison. */
2195 simplify_using_ranges::compare_names (enum tree_code comp
, tree n1
, tree n2
,
2196 bool *strict_overflow_p
)
2198 /* Compare the ranges of every name equivalent to N1 against the
2199 ranges of every name equivalent to N2. */
2200 bitmap e1
= get_value_range (n1
)->equiv ();
2201 bitmap e2
= get_value_range (n2
)->equiv ();
2203 /* Use the fake bitmaps if e1 or e2 are not available. */
2204 static bitmap s_e1
= NULL
, s_e2
= NULL
;
2205 static bitmap_obstack
*s_obstack
= NULL
;
2206 if (s_obstack
== NULL
)
2208 s_obstack
= XNEW (bitmap_obstack
);
2209 bitmap_obstack_initialize (s_obstack
);
2210 s_e1
= BITMAP_ALLOC (s_obstack
);
2211 s_e2
= BITMAP_ALLOC (s_obstack
);
2218 /* Add N1 and N2 to their own set of equivalences to avoid
2219 duplicating the body of the loop just to check N1 and N2
2221 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2222 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2224 /* If the equivalence sets have a common intersection, then the two
2225 names can be compared without checking their ranges. */
2226 if (bitmap_intersect_p (e1
, e2
))
2228 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2229 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2231 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2233 : boolean_false_node
;
2236 /* Start at -1. Set it to 0 if we do a comparison without relying
2237 on overflow, or 1 if all comparisons rely on overflow. */
2238 int used_strict_overflow
= -1;
2240 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2241 N2 to their own set of equivalences to avoid duplicating the body
2242 of the loop just to check N1 and N2 ranges. */
2243 bitmap_iterator bi1
;
2245 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2250 value_range_equiv tem_vr1
;
2251 const value_range_equiv
*vr1
= get_vr_for_comparison (i1
, &tem_vr1
);
2253 tree t
= NULL_TREE
, retval
= NULL_TREE
;
2254 bitmap_iterator bi2
;
2256 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2263 value_range_equiv tem_vr2
;
2264 const value_range_equiv
*vr2
= get_vr_for_comparison (i2
, &tem_vr2
);
2266 t
= compare_ranges (comp
, vr1
, vr2
, &sop
);
2269 /* If we get different answers from different members
2270 of the equivalence set this check must be in a dead
2271 code region. Folding it to a trap representation
2272 would be correct here. For now just return don't-know. */
2273 if (retval
!= NULL
&& t
!= retval
)
2275 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2276 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2282 used_strict_overflow
= 0;
2283 else if (used_strict_overflow
< 0)
2284 used_strict_overflow
= 1;
2290 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2291 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2292 if (used_strict_overflow
> 0)
2293 *strict_overflow_p
= true;
2298 /* None of the equivalent ranges are useful in computing this
2300 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2301 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2305 /* Helper function for vrp_evaluate_conditional_warnv & other
2309 simplify_using_ranges::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2310 (enum tree_code code
, tree op0
, tree op1
, bool * strict_overflow_p
)
2312 const value_range_equiv
*vr0
, *vr1
;
2313 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
2314 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
2316 tree res
= NULL_TREE
;
2318 res
= compare_ranges (code
, vr0
, vr1
, strict_overflow_p
);
2320 res
= compare_range_with_value (code
, vr0
, op1
, strict_overflow_p
);
2322 res
= (compare_range_with_value
2323 (swap_tree_comparison (code
), vr1
, op0
, strict_overflow_p
));
2327 /* Helper function for vrp_evaluate_conditional_warnv. */
2330 simplify_using_ranges::vrp_evaluate_conditional_warnv_with_ops
2332 enum tree_code code
,
2335 bool *strict_overflow_p
,
2340 *only_ranges
= true;
2342 /* We only deal with integral and pointer types. */
2343 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2344 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
2347 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2348 as a simple equality test, then prefer that over its current form
2351 An overflow test which collapses to an equality test can always be
2352 expressed as a comparison of one argument against zero. Overflow
2353 occurs when the chosen argument is zero and does not occur if the
2354 chosen argument is not zero. */
2356 if (overflow_comparison_p (code
, op0
, op1
, use_equiv_p
, &x
))
2358 wide_int max
= wi::max_value (TYPE_PRECISION (TREE_TYPE (op0
)), UNSIGNED
);
2359 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2360 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2361 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2362 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2363 if (integer_zerop (x
))
2366 code
= (code
== LT_EXPR
|| code
== LE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2368 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2369 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2370 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2371 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2372 else if (wi::to_wide (x
) == max
- 1)
2375 op1
= wide_int_to_tree (TREE_TYPE (op0
), 0);
2376 code
= (code
== GT_EXPR
|| code
== GE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2380 value_range vro
, vri
;
2381 if (code
== GT_EXPR
|| code
== GE_EXPR
)
2383 vro
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
, VR_ANTI_RANGE
);
2384 vri
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2386 else if (code
== LT_EXPR
|| code
== LE_EXPR
)
2388 vro
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2389 vri
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
, VR_ANTI_RANGE
);
2393 const value_range_equiv
*vr0
= get_value_range (op0
, stmt
);
2394 /* If vro, the range for OP0 to pass the overflow test, has
2395 no intersection with *vr0, OP0's known range, then the
2396 overflow test can't pass, so return the node for false.
2397 If it is the inverted range, vri, that has no
2398 intersection, then the overflow test must pass, so return
2399 the node for true. In other cases, we could proceed with
2400 a simplified condition comparing OP0 and X, with LE_EXPR
2401 for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
2402 the comments next to the enclosing if suggest it's not
2403 generally profitable to do so. */
2404 vro
.intersect (vr0
);
2405 if (vro
.undefined_p ())
2406 return boolean_false_node
;
2407 vri
.intersect (vr0
);
2408 if (vri
.undefined_p ())
2409 return boolean_true_node
;
2413 if ((ret
= vrp_evaluate_conditional_warnv_with_ops_using_ranges
2414 (code
, op0
, op1
, strict_overflow_p
)))
2417 *only_ranges
= false;
2418 /* Do not use compare_names during propagation, it's quadratic. */
2419 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
2421 return compare_names (code
, op0
, op1
, strict_overflow_p
);
2422 else if (TREE_CODE (op0
) == SSA_NAME
)
2423 return compare_name_with_value (code
, op0
, op1
,
2424 strict_overflow_p
, use_equiv_p
);
2425 else if (TREE_CODE (op1
) == SSA_NAME
)
2426 return compare_name_with_value (swap_tree_comparison (code
), op1
, op0
,
2427 strict_overflow_p
, use_equiv_p
);
2431 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2432 information. Return NULL if the conditional cannot be evaluated.
2433 The ranges of all the names equivalent with the operands in COND
2434 will be used when trying to compute the value. If the result is
2435 based on undefined signed overflow, issue a warning if
2439 simplify_using_ranges::vrp_evaluate_conditional (tree_code code
, tree op0
,
2440 tree op1
, gimple
*stmt
)
2446 /* Some passes and foldings leak constants with overflow flag set
2447 into the IL. Avoid doing wrong things with these and bail out. */
2448 if ((TREE_CODE (op0
) == INTEGER_CST
2449 && TREE_OVERFLOW (op0
))
2450 || (TREE_CODE (op1
) == INTEGER_CST
2451 && TREE_OVERFLOW (op1
)))
2455 ret
= vrp_evaluate_conditional_warnv_with_ops (stmt
, code
, op0
, op1
, true,
2456 &sop
, &only_ranges
);
2460 enum warn_strict_overflow_code wc
;
2461 const char* warnmsg
;
2463 if (is_gimple_min_invariant (ret
))
2465 wc
= WARN_STRICT_OVERFLOW_CONDITIONAL
;
2466 warnmsg
= G_("assuming signed overflow does not occur when "
2467 "simplifying conditional to constant");
2471 wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
2472 warnmsg
= G_("assuming signed overflow does not occur when "
2473 "simplifying conditional");
2476 if (issue_strict_overflow_warning (wc
))
2478 location_t location
;
2480 if (!gimple_has_location (stmt
))
2481 location
= input_location
;
2483 location
= gimple_location (stmt
);
2484 warning_at (location
, OPT_Wstrict_overflow
, "%s", warnmsg
);
2488 if (warn_type_limits
2489 && ret
&& only_ranges
2490 && TREE_CODE_CLASS (code
) == tcc_comparison
2491 && TREE_CODE (op0
) == SSA_NAME
)
2493 /* If the comparison is being folded and the operand on the LHS
2494 is being compared against a constant value that is outside of
2495 the natural range of OP0's type, then the predicate will
2496 always fold regardless of the value of OP0. If -Wtype-limits
2497 was specified, emit a warning. */
2498 tree type
= TREE_TYPE (op0
);
2499 const value_range_equiv
*vr0
= get_value_range (op0
, stmt
);
2501 if (vr0
->varying_p ()
2502 && INTEGRAL_TYPE_P (type
)
2503 && is_gimple_min_invariant (op1
))
2505 location_t location
;
2507 if (!gimple_has_location (stmt
))
2508 location
= input_location
;
2510 location
= gimple_location (stmt
);
2512 warning_at (location
, OPT_Wtype_limits
,
2514 ? G_("comparison always false "
2515 "due to limited range of data type")
2516 : G_("comparison always true "
2517 "due to limited range of data type"));
2525 /* Visit conditional statement STMT. If we can determine which edge
2526 will be taken out of STMT's basic block, record it in
2527 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2530 simplify_using_ranges::vrp_visit_cond_stmt (gcond
*stmt
, edge
*taken_edge_p
)
2534 *taken_edge_p
= NULL
;
2536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2541 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
2542 print_gimple_stmt (dump_file
, stmt
, 0);
2543 fprintf (dump_file
, "\nWith known ranges\n");
2545 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
2547 fprintf (dump_file
, "\t");
2548 print_generic_expr (dump_file
, use
);
2549 fprintf (dump_file
, ": ");
2550 dump_value_range (dump_file
, get_value_range (use
, stmt
));
2553 fprintf (dump_file
, "\n");
2556 /* Compute the value of the predicate COND by checking the known
2557 ranges of each of its operands.
2559 Note that we cannot evaluate all the equivalent ranges here
2560 because those ranges may not yet be final and with the current
2561 propagation strategy, we cannot determine when the value ranges
2562 of the names in the equivalence set have changed.
2564 For instance, given the following code fragment
2568 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2572 Assume that on the first visit to i_14, i_5 has the temporary
2573 range [8, 8] because the second argument to the PHI function is
2574 not yet executable. We derive the range ~[0, 0] for i_14 and the
2575 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2576 the first time, since i_14 is equivalent to the range [8, 8], we
2577 determine that the predicate is always false.
2579 On the next round of propagation, i_13 is determined to be
2580 VARYING, which causes i_5 to drop down to VARYING. So, another
2581 visit to i_14 is scheduled. In this second visit, we compute the
2582 exact same range and equivalence set for i_14, namely ~[0, 0] and
2583 { i_5 }. But we did not have the previous range for i_5
2584 registered, so vrp_visit_assignment thinks that the range for
2585 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2586 is not visited again, which stops propagation from visiting
2587 statements in the THEN clause of that if().
2589 To properly fix this we would need to keep the previous range
2590 value for the names in the equivalence set. This way we would've
2591 discovered that from one visit to the other i_5 changed from
2592 range [8, 8] to VR_VARYING.
2594 However, fixing this apparent limitation may not be worth the
2595 additional checking. Testing on several code bases (GCC, DLV,
2596 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2597 4 more predicates folded in SPEC. */
2600 val
= vrp_evaluate_conditional_warnv_with_ops (stmt
,
2601 gimple_cond_code (stmt
),
2602 gimple_cond_lhs (stmt
),
2603 gimple_cond_rhs (stmt
),
2606 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
2608 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2610 fprintf (dump_file
, "\nPredicate evaluates to: ");
2611 if (val
== NULL_TREE
)
2612 fprintf (dump_file
, "DON'T KNOW\n");
2614 print_generic_stmt (dump_file
, val
);
2618 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2619 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2620 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2621 Returns true if the default label is not needed. */
2624 find_case_label_ranges (gswitch
*stmt
, const value_range
*vr
,
2625 size_t *min_idx1
, size_t *max_idx1
,
2626 size_t *min_idx2
, size_t *max_idx2
)
2629 unsigned int n
= gimple_switch_num_labels (stmt
);
2631 tree case_low
, case_high
;
2632 tree min
= vr
->min (), max
= vr
->max ();
2634 gcc_checking_assert (!vr
->varying_p () && !vr
->undefined_p ());
2636 take_default
= !find_case_label_range (stmt
, min
, max
, &i
, &j
);
2638 /* Set second range to empty. */
2642 if (vr
->kind () == VR_RANGE
)
2646 return !take_default
;
2649 /* Set first range to all case labels. */
2656 /* Make sure all the values of case labels [i , j] are contained in
2657 range [MIN, MAX]. */
2658 case_low
= CASE_LOW (gimple_switch_label (stmt
, i
));
2659 case_high
= CASE_HIGH (gimple_switch_label (stmt
, j
));
2660 if (tree_int_cst_compare (case_low
, min
) < 0)
2662 if (case_high
!= NULL_TREE
2663 && tree_int_cst_compare (max
, case_high
) < 0)
2669 /* If the range spans case labels [i, j], the corresponding anti-range spans
2670 the labels [1, i - 1] and [j + 1, n - 1]. */
2696 /* Visit switch statement STMT. If we can determine which edge
2697 will be taken out of STMT's basic block, record it in
2698 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2701 vr_values::vrp_visit_switch_stmt (gswitch
*stmt
, edge
*taken_edge_p
)
2704 const value_range_equiv
*vr
;
2705 size_t i
= 0, j
= 0, k
, l
;
2708 *taken_edge_p
= NULL
;
2709 op
= gimple_switch_index (stmt
);
2710 if (TREE_CODE (op
) != SSA_NAME
)
2713 vr
= get_value_range (op
);
2714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2716 fprintf (dump_file
, "\nVisiting switch expression with operand ");
2717 print_generic_expr (dump_file
, op
);
2718 fprintf (dump_file
, " with known range ");
2719 dump_value_range (dump_file
, vr
);
2720 fprintf (dump_file
, "\n");
2723 if (vr
->undefined_p ()
2725 || vr
->symbolic_p ())
2728 /* Find the single edge that is taken from the switch expression. */
2729 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
2731 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2735 gcc_assert (take_default
);
2736 val
= gimple_switch_default_label (stmt
);
2740 /* Check if labels with index i to j and maybe the default label
2741 are all reaching the same label. */
2743 val
= gimple_switch_label (stmt
, i
);
2745 && CASE_LABEL (gimple_switch_default_label (stmt
))
2746 != CASE_LABEL (val
))
2748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2749 fprintf (dump_file
, " not a single destination for this "
2753 for (++i
; i
<= j
; ++i
)
2755 if (CASE_LABEL (gimple_switch_label (stmt
, i
)) != CASE_LABEL (val
))
2757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2758 fprintf (dump_file
, " not a single destination for this "
2765 if (CASE_LABEL (gimple_switch_label (stmt
, k
)) != CASE_LABEL (val
))
2767 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2768 fprintf (dump_file
, " not a single destination for this "
2775 *taken_edge_p
= find_edge (gimple_bb (stmt
),
2776 label_to_block (cfun
, CASE_LABEL (val
)));
2778 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2780 fprintf (dump_file
, " will take edge to ");
2781 print_generic_stmt (dump_file
, CASE_LABEL (val
));
2786 /* Evaluate statement STMT. If the statement produces a useful range,
2787 set VR and corepsponding OUTPUT_P.
2789 If STMT is a conditional branch and we can determine its truth
2790 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2793 vr_values::extract_range_from_stmt (gimple
*stmt
, edge
*taken_edge_p
,
2794 tree
*output_p
, value_range_equiv
*vr
)
2797 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2799 fprintf (dump_file
, "\nextract_range_from_stmt visiting:\n");
2800 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
2803 if (!stmt_interesting_for_vrp (stmt
))
2804 gcc_assert (stmt_ends_bb_p (stmt
));
2805 else if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
2806 vrp_visit_assignment_or_call (stmt
, output_p
, vr
);
2807 else if (gimple_code (stmt
) == GIMPLE_COND
)
2808 simplifier
.vrp_visit_cond_stmt (as_a
<gcond
*> (stmt
), taken_edge_p
);
2809 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2810 vrp_visit_switch_stmt (as_a
<gswitch
*> (stmt
), taken_edge_p
);
2813 /* Visit all arguments for PHI node PHI that flow through executable
2814 edges. If a valid value range can be derived from all the incoming
2815 value ranges, set a new range in VR_RESULT. */
2818 vr_values::extract_range_from_phi_node (gphi
*phi
,
2819 value_range_equiv
*vr_result
)
2821 tree lhs
= PHI_RESULT (phi
);
2822 const value_range_equiv
*lhs_vr
= get_value_range (lhs
);
2827 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2829 fprintf (dump_file
, "\nVisiting PHI node: ");
2830 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
2833 bool may_simulate_backedge_again
= false;
2835 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2837 edge e
= gimple_phi_arg_edge (phi
, i
);
2839 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2842 " Argument #%d (%d -> %d %sexecutable)\n",
2843 (int) i
, e
->src
->index
, e
->dest
->index
,
2844 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
2847 if (e
->flags
& EDGE_EXECUTABLE
)
2849 value_range_equiv vr_arg_tem
;
2850 const value_range_equiv
*vr_arg
= &vr_arg_tem
;
2854 tree arg
= PHI_ARG_DEF (phi
, i
);
2855 if (TREE_CODE (arg
) == SSA_NAME
)
2857 /* See if we are eventually going to change one of the args. */
2858 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
2859 if (! gimple_nop_p (def_stmt
)
2860 && prop_simulate_again_p (def_stmt
)
2861 && e
->flags
& EDGE_DFS_BACK
)
2862 may_simulate_backedge_again
= true;
2864 const value_range_equiv
*vr_arg_
= get_value_range (arg
);
2865 /* Do not allow equivalences or symbolic ranges to leak in from
2866 backedges. That creates invalid equivalencies.
2867 See PR53465 and PR54767. */
2868 if (e
->flags
& EDGE_DFS_BACK
)
2870 if (!vr_arg_
->varying_p () && !vr_arg_
->undefined_p ())
2872 vr_arg_tem
.set (vr_arg_
->min (), vr_arg_
->max (), NULL
,
2874 if (vr_arg_tem
.symbolic_p ())
2875 vr_arg_tem
.set_varying (TREE_TYPE (arg
));
2880 /* If the non-backedge arguments range is VR_VARYING then
2881 we can still try recording a simple equivalence. */
2882 else if (vr_arg_
->varying_p ())
2883 vr_arg_tem
.set (arg
);
2889 if (TREE_OVERFLOW_P (arg
))
2890 arg
= drop_tree_overflow (arg
);
2892 vr_arg_tem
.set (arg
);
2895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2897 fprintf (dump_file
, "\t");
2898 print_generic_expr (dump_file
, arg
, dump_flags
);
2899 fprintf (dump_file
, ": ");
2900 dump_value_range (dump_file
, vr_arg
);
2901 fprintf (dump_file
, "\n");
2905 vr_result
->deep_copy (vr_arg
);
2907 vr_result
->union_ (vr_arg
);
2910 if (vr_result
->varying_p ())
2915 if (vr_result
->varying_p ())
2917 else if (vr_result
->undefined_p ())
2920 old_edges
= vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)];
2921 vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)] = edges
;
2923 /* To prevent infinite iterations in the algorithm, derive ranges
2924 when the new value is slightly bigger or smaller than the
2925 previous one. We don't do this if we have seen a new executable
2926 edge; this helps us avoid an infinity for conditionals
2927 which are not in a loop. If the old value-range was VR_UNDEFINED
2928 use the updated range and iterate one more time. If we will not
2929 simulate this PHI again via the backedge allow us to iterate. */
2931 && gimple_phi_num_args (phi
) > 1
2932 && edges
== old_edges
2933 && !lhs_vr
->undefined_p ()
2934 && may_simulate_backedge_again
)
2936 /* Compare old and new ranges, fall back to varying if the
2937 values are not comparable. */
2938 int cmp_min
= compare_values (lhs_vr
->min (), vr_result
->min ());
2941 int cmp_max
= compare_values (lhs_vr
->max (), vr_result
->max ());
2945 /* For non VR_RANGE or for pointers fall back to varying if
2946 the range changed. */
2947 if ((lhs_vr
->kind () != VR_RANGE
|| vr_result
->kind () != VR_RANGE
2948 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2949 && (cmp_min
!= 0 || cmp_max
!= 0))
2952 /* If the new minimum is larger than the previous one
2953 retain the old value. If the new minimum value is smaller
2954 than the previous one and not -INF go all the way to -INF + 1.
2955 In the first case, to avoid infinite bouncing between different
2956 minimums, and in the other case to avoid iterating millions of
2957 times to reach -INF. Going to -INF + 1 also lets the following
2958 iteration compute whether there will be any overflow, at the
2959 expense of one additional iteration. */
2960 tree new_min
= vr_result
->min ();
2961 tree new_max
= vr_result
->max ();
2963 new_min
= lhs_vr
->min ();
2964 else if (cmp_min
> 0
2965 && (TREE_CODE (vr_result
->min ()) != INTEGER_CST
2966 || tree_int_cst_lt (vrp_val_min (vr_result
->type ()),
2967 vr_result
->min ())))
2968 new_min
= int_const_binop (PLUS_EXPR
,
2969 vrp_val_min (vr_result
->type ()),
2970 build_int_cst (vr_result
->type (), 1));
2972 /* Similarly for the maximum value. */
2974 new_max
= lhs_vr
->max ();
2975 else if (cmp_max
< 0
2976 && (TREE_CODE (vr_result
->max ()) != INTEGER_CST
2977 || tree_int_cst_lt (vr_result
->max (),
2978 vrp_val_max (vr_result
->type ()))))
2979 new_max
= int_const_binop (MINUS_EXPR
,
2980 vrp_val_max (vr_result
->type ()),
2981 build_int_cst (vr_result
->type (), 1));
2983 vr_result
->update (new_min
, new_max
, vr_result
->kind ());
2985 /* If we dropped either bound to +-INF then if this is a loop
2986 PHI node SCEV may known more about its value-range. */
2987 if (cmp_min
> 0 || cmp_min
< 0
2988 || cmp_max
< 0 || cmp_max
> 0)
2991 goto infinite_check
;
2997 vr_result
->set_varying (TREE_TYPE (lhs
));
3000 /* If this is a loop PHI node SCEV may known more about its value-range.
3001 scev_check can be reached from two paths, one is a fall through from above
3002 "varying" label, the other is direct goto from code block which tries to
3003 avoid infinite simulation. */
3004 if (scev_initialized_p ()
3005 && (l
= loop_containing_stmt (phi
))
3006 && l
->header
== gimple_bb (phi
))
3007 adjust_range_with_scev (vr_result
, l
, phi
, lhs
);
3010 /* If we will end up with a (-INF, +INF) range, set it to
3011 VARYING. Same if the previous max value was invalid for
3012 the type and we end up with vr_result.min > vr_result.max. */
3013 if ((!vr_result
->varying_p () && !vr_result
->undefined_p ())
3014 && !((vrp_val_is_max (vr_result
->max ()) && vrp_val_is_min (vr_result
->min ()))
3015 || compare_values (vr_result
->min (), vr_result
->max ()) > 0))
3018 vr_result
->set_varying (TREE_TYPE (lhs
));
3020 /* If the new range is different than the previous value, keep
3026 /* Simplify boolean operations if the source is known
3027 to be already a boolean. */
3029 simplify_using_ranges::simplify_truth_ops_using_ranges
3030 (gimple_stmt_iterator
*gsi
,
3033 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3035 bool need_conversion
;
3037 /* We handle only !=/== case here. */
3038 gcc_assert (rhs_code
== EQ_EXPR
|| rhs_code
== NE_EXPR
);
3040 op0
= gimple_assign_rhs1 (stmt
);
3041 if (!op_with_boolean_value_range_p (op0
))
3044 op1
= gimple_assign_rhs2 (stmt
);
3045 if (!op_with_boolean_value_range_p (op1
))
3048 /* Reduce number of cases to handle to NE_EXPR. As there is no
3049 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
3050 if (rhs_code
== EQ_EXPR
)
3052 if (TREE_CODE (op1
) == INTEGER_CST
)
3053 op1
= int_const_binop (BIT_XOR_EXPR
, op1
,
3054 build_int_cst (TREE_TYPE (op1
), 1));
3059 lhs
= gimple_assign_lhs (stmt
);
3061 = !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
));
3063 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
3065 && !TYPE_UNSIGNED (TREE_TYPE (op0
))
3066 && TYPE_PRECISION (TREE_TYPE (op0
)) == 1
3067 && TYPE_PRECISION (TREE_TYPE (lhs
)) > 1)
3070 /* For A != 0 we can substitute A itself. */
3071 if (integer_zerop (op1
))
3072 gimple_assign_set_rhs_with_ops (gsi
,
3074 ? NOP_EXPR
: TREE_CODE (op0
), op0
);
3075 /* For A != B we substitute A ^ B. Either with conversion. */
3076 else if (need_conversion
)
3078 tree tem
= make_ssa_name (TREE_TYPE (op0
));
3080 = gimple_build_assign (tem
, BIT_XOR_EXPR
, op0
, op1
);
3081 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
3082 if (INTEGRAL_TYPE_P (TREE_TYPE (tem
))
3083 && TYPE_PRECISION (TREE_TYPE (tem
)) > 1)
3084 set_range_info (tem
, VR_RANGE
,
3085 wi::zero (TYPE_PRECISION (TREE_TYPE (tem
))),
3086 wi::one (TYPE_PRECISION (TREE_TYPE (tem
))));
3087 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, tem
);
3091 gimple_assign_set_rhs_with_ops (gsi
, BIT_XOR_EXPR
, op0
, op1
);
3092 update_stmt (gsi_stmt (*gsi
));
3093 fold_stmt (gsi
, follow_single_use_edges
);
3098 /* Simplify a division or modulo operator to a right shift or bitwise and
3099 if the first operand is unsigned or is greater than zero and the second
3100 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
3101 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
3102 optimize it into just op0 if op0's range is known to be a subset of
3103 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3107 simplify_using_ranges::simplify_div_or_mod_using_ranges
3108 (gimple_stmt_iterator
*gsi
,
3111 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3113 tree op0
= gimple_assign_rhs1 (stmt
);
3114 tree op1
= gimple_assign_rhs2 (stmt
);
3115 tree op0min
= NULL_TREE
, op0max
= NULL_TREE
;
3117 const value_range
*vr
= NULL
;
3119 if (TREE_CODE (op0
) == INTEGER_CST
)
3126 vr
= get_value_range (op0
, stmt
);
3127 if (range_int_cst_p (vr
))
3129 op0min
= vr
->min ();
3130 op0max
= vr
->max ();
3134 if (rhs_code
== TRUNC_MOD_EXPR
3135 && TREE_CODE (op1
) == SSA_NAME
)
3137 const value_range_equiv
*vr1
= get_value_range (op1
, stmt
);
3138 if (range_int_cst_p (vr1
))
3139 op1min
= vr1
->min ();
3141 if (rhs_code
== TRUNC_MOD_EXPR
3142 && TREE_CODE (op1min
) == INTEGER_CST
3143 && tree_int_cst_sgn (op1min
) == 1
3145 && tree_int_cst_lt (op0max
, op1min
))
3147 if (TYPE_UNSIGNED (TREE_TYPE (op0
))
3148 || tree_int_cst_sgn (op0min
) >= 0
3149 || tree_int_cst_lt (fold_unary (NEGATE_EXPR
, TREE_TYPE (op1min
), op1min
),
3152 /* If op0 already has the range op0 % op1 has,
3153 then TRUNC_MOD_EXPR won't change anything. */
3154 gimple_assign_set_rhs_from_tree (gsi
, op0
);
3159 if (TREE_CODE (op0
) != SSA_NAME
)
3162 if (!integer_pow2p (op1
))
3164 /* X % -Y can be only optimized into X % Y either if
3165 X is not INT_MIN, or Y is not -1. Fold it now, as after
3166 remove_range_assertions the range info might be not available
3168 if (rhs_code
== TRUNC_MOD_EXPR
3169 && fold_stmt (gsi
, follow_single_use_edges
))
3174 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
3175 val
= integer_one_node
;
3180 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
3184 && integer_onep (val
)
3185 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3187 location_t location
;
3189 if (!gimple_has_location (stmt
))
3190 location
= input_location
;
3192 location
= gimple_location (stmt
);
3193 warning_at (location
, OPT_Wstrict_overflow
,
3194 "assuming signed overflow does not occur when "
3195 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3199 if (val
&& integer_onep (val
))
3203 if (rhs_code
== TRUNC_DIV_EXPR
)
3205 t
= build_int_cst (integer_type_node
, tree_log2 (op1
));
3206 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
3207 gimple_assign_set_rhs1 (stmt
, op0
);
3208 gimple_assign_set_rhs2 (stmt
, t
);
3212 t
= build_int_cst (TREE_TYPE (op1
), 1);
3213 t
= int_const_binop (MINUS_EXPR
, op1
, t
);
3214 t
= fold_convert (TREE_TYPE (op0
), t
);
3216 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
3217 gimple_assign_set_rhs1 (stmt
, op0
);
3218 gimple_assign_set_rhs2 (stmt
, t
);
3222 fold_stmt (gsi
, follow_single_use_edges
);
3229 /* Simplify a min or max if the ranges of the two operands are
3230 disjoint. Return true if we do simplify. */
3233 simplify_using_ranges::simplify_min_or_max_using_ranges
3234 (gimple_stmt_iterator
*gsi
,
3237 tree op0
= gimple_assign_rhs1 (stmt
);
3238 tree op1
= gimple_assign_rhs2 (stmt
);
3242 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3243 (LE_EXPR
, op0
, op1
, &sop
));
3247 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3248 (LT_EXPR
, op0
, op1
, &sop
));
3253 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3255 location_t location
;
3257 if (!gimple_has_location (stmt
))
3258 location
= input_location
;
3260 location
= gimple_location (stmt
);
3261 warning_at (location
, OPT_Wstrict_overflow
,
3262 "assuming signed overflow does not occur when "
3263 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3266 /* VAL == TRUE -> OP0 < or <= op1
3267 VAL == FALSE -> OP0 > or >= op1. */
3268 tree res
= ((gimple_assign_rhs_code (stmt
) == MAX_EXPR
)
3269 == integer_zerop (val
)) ? op0
: op1
;
3270 gimple_assign_set_rhs_from_tree (gsi
, res
);
3277 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3278 ABS_EXPR. If the operand is <= 0, then simplify the
3279 ABS_EXPR into a NEGATE_EXPR. */
3282 simplify_using_ranges::simplify_abs_using_ranges (gimple_stmt_iterator
*gsi
,
3285 tree op
= gimple_assign_rhs1 (stmt
);
3286 const value_range
*vr
= get_value_range (op
, stmt
);
3293 val
= compare_range_with_value (LE_EXPR
, vr
, integer_zero_node
, &sop
);
3296 /* The range is neither <= 0 nor > 0. Now see if it is
3297 either < 0 or >= 0. */
3299 val
= compare_range_with_value (LT_EXPR
, vr
, integer_zero_node
,
3305 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3307 location_t location
;
3309 if (!gimple_has_location (stmt
))
3310 location
= input_location
;
3312 location
= gimple_location (stmt
);
3313 warning_at (location
, OPT_Wstrict_overflow
,
3314 "assuming signed overflow does not occur when "
3315 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3318 gimple_assign_set_rhs1 (stmt
, op
);
3319 if (integer_zerop (val
))
3320 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
3322 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
3324 fold_stmt (gsi
, follow_single_use_edges
);
3332 /* value_range wrapper for wi_set_zero_nonzero_bits.
3334 Return TRUE if VR was a constant range and we were able to compute
3338 vr_set_zero_nonzero_bits (const tree expr_type
,
3339 const value_range
*vr
,
3340 wide_int
*may_be_nonzero
,
3341 wide_int
*must_be_nonzero
)
3343 if (range_int_cst_p (vr
))
3345 wi_set_zero_nonzero_bits (expr_type
,
3346 wi::to_wide (vr
->min ()),
3347 wi::to_wide (vr
->max ()),
3348 *may_be_nonzero
, *must_be_nonzero
);
3351 *may_be_nonzero
= wi::minus_one (TYPE_PRECISION (expr_type
));
3352 *must_be_nonzero
= wi::zero (TYPE_PRECISION (expr_type
));
3356 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3357 If all the bits that are being cleared by & are already
3358 known to be zero from VR, or all the bits that are being
3359 set by | are already known to be one from VR, the bit
3360 operation is redundant. */
3363 simplify_using_ranges::simplify_bit_ops_using_ranges
3364 (gimple_stmt_iterator
*gsi
,
3367 tree op0
= gimple_assign_rhs1 (stmt
);
3368 tree op1
= gimple_assign_rhs2 (stmt
);
3369 tree op
= NULL_TREE
;
3370 value_range vr0
, vr1
;
3371 wide_int may_be_nonzero0
, may_be_nonzero1
;
3372 wide_int must_be_nonzero0
, must_be_nonzero1
;
3375 if (TREE_CODE (op0
) == SSA_NAME
)
3376 vr0
= *(get_value_range (op0
, stmt
));
3377 else if (is_gimple_min_invariant (op0
))
3382 if (TREE_CODE (op1
) == SSA_NAME
)
3383 vr1
= *(get_value_range (op1
, stmt
));
3384 else if (is_gimple_min_invariant (op1
))
3389 if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0
), &vr0
, &may_be_nonzero0
,
3392 if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1
), &vr1
, &may_be_nonzero1
,
3396 switch (gimple_assign_rhs_code (stmt
))
3399 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3405 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3413 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3419 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3430 if (op
== NULL_TREE
)
3433 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (op
), op
);
3434 update_stmt (gsi_stmt (*gsi
));
3438 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3439 a known value range VR.
3441 If there is one and only one value which will satisfy the
3442 conditional, then return that value. Else return NULL.
3444 If signed overflow must be undefined for the value to satisfy
3445 the conditional, then set *STRICT_OVERFLOW_P to true. */
3448 test_for_singularity (enum tree_code cond_code
, tree op0
,
3449 tree op1
, const value_range
*vr
)
3454 /* Extract minimum/maximum values which satisfy the conditional as it was
3456 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
3458 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
3461 if (cond_code
== LT_EXPR
)
3463 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3464 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
3465 /* Signal to compare_values_warnv this expr doesn't overflow. */
3467 TREE_NO_WARNING (max
) = 1;
3470 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
3472 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
3475 if (cond_code
== GT_EXPR
)
3477 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3478 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
3479 /* Signal to compare_values_warnv this expr doesn't overflow. */
3481 TREE_NO_WARNING (min
) = 1;
3485 /* Now refine the minimum and maximum values using any
3486 value range information we have for op0. */
3489 tree type
= TREE_TYPE (op0
);
3490 tree tmin
= wide_int_to_tree (type
, vr
->lower_bound ());
3491 tree tmax
= wide_int_to_tree (type
, vr
->upper_bound ());
3492 if (compare_values (tmin
, min
) == 1)
3494 if (compare_values (tmax
, max
) == -1)
3497 /* If the new min/max values have converged to a single value,
3498 then there is only one value which can satisfy the condition,
3499 return that value. */
3500 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
3506 /* Return whether the value range *VR fits in an integer type specified
3507 by PRECISION and UNSIGNED_P. */
3510 range_fits_type_p (const value_range
*vr
,
3511 unsigned dest_precision
, signop dest_sgn
)
3514 unsigned src_precision
;
3518 /* We can only handle integral and pointer types. */
3519 src_type
= vr
->type ();
3520 if (!INTEGRAL_TYPE_P (src_type
)
3521 && !POINTER_TYPE_P (src_type
))
3524 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3525 and so is an identity transform. */
3526 src_precision
= TYPE_PRECISION (vr
->type ());
3527 src_sgn
= TYPE_SIGN (src_type
);
3528 if ((src_precision
< dest_precision
3529 && !(dest_sgn
== UNSIGNED
&& src_sgn
== SIGNED
))
3530 || (src_precision
== dest_precision
&& src_sgn
== dest_sgn
))
3533 /* Now we can only handle ranges with constant bounds. */
3534 if (!range_int_cst_p (vr
))
3537 /* For sign changes, the MSB of the wide_int has to be clear.
3538 An unsigned value with its MSB set cannot be represented by
3539 a signed wide_int, while a negative value cannot be represented
3540 by an unsigned wide_int. */
3541 if (src_sgn
!= dest_sgn
3542 && (wi::lts_p (wi::to_wide (vr
->min ()), 0)
3543 || wi::lts_p (wi::to_wide (vr
->max ()), 0)))
3546 /* Then we can perform the conversion on both ends and compare
3547 the result for equality. */
3548 tem
= wi::ext (wi::to_widest (vr
->min ()), dest_precision
, dest_sgn
);
3549 if (tem
!= wi::to_widest (vr
->min ()))
3551 tem
= wi::ext (wi::to_widest (vr
->max ()), dest_precision
, dest_sgn
);
3552 if (tem
!= wi::to_widest (vr
->max ()))
3558 /* If COND can be folded entirely as TRUE or FALSE, rewrite the
3559 conditional as such, and return TRUE. */
3562 simplify_using_ranges::fold_cond (gcond
*cond
)
3564 /* ?? vrp_folder::fold_predicate_in() is a superset of this. At
3565 some point we should merge all variants of this code. */
3567 vrp_visit_cond_stmt (cond
, &taken_edge
);
3570 if (taken_edge
->flags
& EDGE_TRUE_VALUE
)
3571 gimple_cond_make_true (cond
);
3572 else if (taken_edge
->flags
& EDGE_FALSE_VALUE
)
3573 gimple_cond_make_false (cond
);
3582 /* Simplify a conditional using a relational operator to an equality
3583 test if the range information indicates only one value can satisfy
3584 the original conditional. */
3587 simplify_using_ranges::simplify_cond_using_ranges_1 (gcond
*stmt
)
3589 tree op0
= gimple_cond_lhs (stmt
);
3590 tree op1
= gimple_cond_rhs (stmt
);
3591 enum tree_code cond_code
= gimple_cond_code (stmt
);
3593 if (fold_cond (stmt
))
3596 if (cond_code
!= NE_EXPR
3597 && cond_code
!= EQ_EXPR
3598 && TREE_CODE (op0
) == SSA_NAME
3599 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3600 && is_gimple_min_invariant (op1
))
3602 const value_range
*vr
= get_value_range (op0
, stmt
);
3604 /* If we have range information for OP0, then we might be
3605 able to simplify this conditional. */
3606 if (!vr
->undefined_p () && !vr
->varying_p ())
3608 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
3613 fprintf (dump_file
, "Simplified relational ");
3614 print_gimple_stmt (dump_file
, stmt
, 0);
3615 fprintf (dump_file
, " into ");
3618 gimple_cond_set_code (stmt
, EQ_EXPR
);
3619 gimple_cond_set_lhs (stmt
, op0
);
3620 gimple_cond_set_rhs (stmt
, new_tree
);
3626 print_gimple_stmt (dump_file
, stmt
, 0);
3627 fprintf (dump_file
, "\n");
3633 /* Try again after inverting the condition. We only deal
3634 with integral types here, so no need to worry about
3635 issues with inverting FP comparisons. */
3636 new_tree
= test_for_singularity
3637 (invert_tree_comparison (cond_code
, false),
3643 fprintf (dump_file
, "Simplified relational ");
3644 print_gimple_stmt (dump_file
, stmt
, 0);
3645 fprintf (dump_file
, " into ");
3648 gimple_cond_set_code (stmt
, NE_EXPR
);
3649 gimple_cond_set_lhs (stmt
, op0
);
3650 gimple_cond_set_rhs (stmt
, new_tree
);
3656 print_gimple_stmt (dump_file
, stmt
, 0);
3657 fprintf (dump_file
, "\n");
3667 /* STMT is a conditional at the end of a basic block.
3669 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3670 was set via a type conversion, try to replace the SSA_NAME with the RHS
3671 of the type conversion. Doing so makes the conversion dead which helps
3672 subsequent passes. */
3675 simplify_cond_using_ranges_2 (vr_values
*store
, gcond
*stmt
)
3677 tree op0
= gimple_cond_lhs (stmt
);
3678 tree op1
= gimple_cond_rhs (stmt
);
3680 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3681 see if OP0 was set by a type conversion where the source of
3682 the conversion is another SSA_NAME with a range that fits
3683 into the range of OP0's type.
3685 If so, the conversion is redundant as the earlier SSA_NAME can be
3686 used for the comparison directly if we just massage the constant in the
3688 if (TREE_CODE (op0
) == SSA_NAME
3689 && TREE_CODE (op1
) == INTEGER_CST
)
3691 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op0
);
3694 if (!is_gimple_assign (def_stmt
)
3695 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3698 innerop
= gimple_assign_rhs1 (def_stmt
);
3700 if (TREE_CODE (innerop
) == SSA_NAME
3701 && !POINTER_TYPE_P (TREE_TYPE (innerop
))
3702 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
)
3703 && desired_pro_or_demotion_p (TREE_TYPE (innerop
), TREE_TYPE (op0
)))
3705 const value_range
*vr
= store
->get_value_range (innerop
);
3707 if (range_int_cst_p (vr
)
3708 && range_fits_type_p (vr
,
3709 TYPE_PRECISION (TREE_TYPE (op0
)),
3710 TYPE_SIGN (TREE_TYPE (op0
)))
3711 && int_fits_type_p (op1
, TREE_TYPE (innerop
)))
3713 tree newconst
= fold_convert (TREE_TYPE (innerop
), op1
);
3714 gimple_cond_set_lhs (stmt
, innerop
);
3715 gimple_cond_set_rhs (stmt
, newconst
);
3717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3719 fprintf (dump_file
, "Folded into: ");
3720 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3721 fprintf (dump_file
, "\n");
3728 /* Simplify a switch statement using the value range of the switch
3732 simplify_using_ranges::simplify_switch_using_ranges (gswitch
*stmt
)
3734 tree op
= gimple_switch_index (stmt
);
3735 const value_range
*vr
= NULL
;
3739 size_t i
= 0, j
= 0, n
, n2
;
3742 size_t k
= 1, l
= 0;
3744 if (TREE_CODE (op
) == SSA_NAME
)
3746 vr
= get_value_range (op
, stmt
);
3748 /* We can only handle integer ranges. */
3749 if (vr
->varying_p ()
3750 || vr
->undefined_p ()
3751 || vr
->symbolic_p ())
3754 /* Find case label for min/max of the value range. */
3755 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
3757 else if (TREE_CODE (op
) == INTEGER_CST
)
3759 take_default
= !find_case_label_index (stmt
, 1, op
, &i
);
3773 n
= gimple_switch_num_labels (stmt
);
3775 /* We can truncate the case label ranges that partially overlap with OP's
3777 size_t min_idx
= 1, max_idx
= 0;
3779 find_case_label_range (stmt
, vr
->min (), vr
->max (), &min_idx
, &max_idx
);
3780 if (min_idx
<= max_idx
)
3782 tree min_label
= gimple_switch_label (stmt
, min_idx
);
3783 tree max_label
= gimple_switch_label (stmt
, max_idx
);
3785 /* Avoid changing the type of the case labels when truncating. */
3786 tree case_label_type
= TREE_TYPE (CASE_LOW (min_label
));
3787 tree vr_min
= fold_convert (case_label_type
, vr
->min ());
3788 tree vr_max
= fold_convert (case_label_type
, vr
->max ());
3790 if (vr
->kind () == VR_RANGE
)
3792 /* If OP's value range is [2,8] and the low label range is
3793 0 ... 3, truncate the label's range to 2 .. 3. */
3794 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3795 && CASE_HIGH (min_label
) != NULL_TREE
3796 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3797 CASE_LOW (min_label
) = vr_min
;
3799 /* If OP's value range is [2,8] and the high label range is
3800 7 ... 10, truncate the label's range to 7 .. 8. */
3801 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3802 && CASE_HIGH (max_label
) != NULL_TREE
3803 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3804 CASE_HIGH (max_label
) = vr_max
;
3806 else if (vr
->kind () == VR_ANTI_RANGE
)
3808 tree one_cst
= build_one_cst (case_label_type
);
3810 if (min_label
== max_label
)
3812 /* If OP's value range is ~[7,8] and the label's range is
3813 7 ... 10, truncate the label's range to 9 ... 10. */
3814 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) == 0
3815 && CASE_HIGH (min_label
) != NULL_TREE
3816 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) > 0)
3817 CASE_LOW (min_label
)
3818 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3820 /* If OP's value range is ~[7,8] and the label's range is
3821 5 ... 8, truncate the label's range to 5 ... 6. */
3822 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3823 && CASE_HIGH (min_label
) != NULL_TREE
3824 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) == 0)
3825 CASE_HIGH (min_label
)
3826 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3830 /* If OP's value range is ~[2,8] and the low label range is
3831 0 ... 3, truncate the label's range to 0 ... 1. */
3832 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3833 && CASE_HIGH (min_label
) != NULL_TREE
3834 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3835 CASE_HIGH (min_label
)
3836 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3838 /* If OP's value range is ~[2,8] and the high label range is
3839 7 ... 10, truncate the label's range to 9 ... 10. */
3840 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3841 && CASE_HIGH (max_label
) != NULL_TREE
3842 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3843 CASE_LOW (max_label
)
3844 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3848 /* Canonicalize singleton case ranges. */
3849 if (tree_int_cst_equal (CASE_LOW (min_label
), CASE_HIGH (min_label
)))
3850 CASE_HIGH (min_label
) = NULL_TREE
;
3851 if (tree_int_cst_equal (CASE_LOW (max_label
), CASE_HIGH (max_label
)))
3852 CASE_HIGH (max_label
) = NULL_TREE
;
3855 /* We can also eliminate case labels that lie completely outside OP's value
3858 /* Bail out if this is just all edges taken. */
3864 /* Build a new vector of taken case labels. */
3865 vec2
= make_tree_vec (j
- i
+ 1 + l
- k
+ 1 + (int)take_default
);
3868 /* Add the default edge, if necessary. */
3870 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
3872 for (; i
<= j
; ++i
, ++n2
)
3873 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
3875 for (; k
<= l
; ++k
, ++n2
)
3876 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, k
);
3878 /* Mark needed edges. */
3879 for (i
= 0; i
< n2
; ++i
)
3881 e
= find_edge (gimple_bb (stmt
),
3882 label_to_block (cfun
,
3883 CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
3884 e
->aux
= (void *)-1;
3887 /* Queue not needed edges for later removal. */
3888 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
3890 if (e
->aux
== (void *)-1)
3896 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3898 fprintf (dump_file
, "removing unreachable case label\n");
3900 to_remove_edges
.safe_push (e
);
3901 e
->flags
&= ~EDGE_EXECUTABLE
;
3902 e
->flags
|= EDGE_IGNORE
;
3905 /* And queue an update for the stmt. */
3908 to_update_switch_stmts
.safe_push (su
);
3913 simplify_using_ranges::cleanup_edges_and_switches (void)
3919 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
3920 CFG in a broken state and requires a cfg_cleanup run. */
3921 FOR_EACH_VEC_ELT (to_remove_edges
, i
, e
)
3924 /* Update SWITCH_EXPR case label vector. */
3925 FOR_EACH_VEC_ELT (to_update_switch_stmts
, i
, su
)
3928 size_t n
= TREE_VEC_LENGTH (su
->vec
);
3930 gimple_switch_set_num_labels (su
->stmt
, n
);
3931 for (j
= 0; j
< n
; j
++)
3932 gimple_switch_set_label (su
->stmt
, j
, TREE_VEC_ELT (su
->vec
, j
));
3933 /* As we may have replaced the default label with a regular one
3934 make sure to make it a real default label again. This ensures
3935 optimal expansion. */
3936 label
= gimple_switch_label (su
->stmt
, 0);
3937 CASE_LOW (label
) = NULL_TREE
;
3938 CASE_HIGH (label
) = NULL_TREE
;
3941 if (!to_remove_edges
.is_empty ())
3943 free_dominance_info (CDI_DOMINATORS
);
3944 loops_state_set (LOOPS_NEED_FIXUP
);
3947 to_remove_edges
.release ();
3948 to_update_switch_stmts
.release ();
3951 /* Simplify an integral conversion from an SSA name in STMT. */
3954 simplify_conversion_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3956 tree innerop
, middleop
, finaltype
;
3958 signop inner_sgn
, middle_sgn
, final_sgn
;
3959 unsigned inner_prec
, middle_prec
, final_prec
;
3960 widest_int innermin
, innermed
, innermax
, middlemin
, middlemed
, middlemax
;
3962 finaltype
= TREE_TYPE (gimple_assign_lhs (stmt
));
3963 if (!INTEGRAL_TYPE_P (finaltype
))
3965 middleop
= gimple_assign_rhs1 (stmt
);
3966 def_stmt
= SSA_NAME_DEF_STMT (middleop
);
3967 if (!is_gimple_assign (def_stmt
)
3968 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3970 innerop
= gimple_assign_rhs1 (def_stmt
);
3971 if (TREE_CODE (innerop
) != SSA_NAME
3972 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
))
3975 /* Get the value-range of the inner operand. Use get_range_info in
3976 case innerop was created during substitute-and-fold. */
3977 wide_int imin
, imax
;
3979 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
)))
3981 get_range_info (innerop
, vr
);
3982 if (vr
.undefined_p () || vr
.varying_p ())
3984 innermin
= widest_int::from (vr
.lower_bound (), TYPE_SIGN (TREE_TYPE (innerop
)));
3985 innermax
= widest_int::from (vr
.upper_bound (), TYPE_SIGN (TREE_TYPE (innerop
)));
3987 /* Simulate the conversion chain to check if the result is equal if
3988 the middle conversion is removed. */
3989 inner_prec
= TYPE_PRECISION (TREE_TYPE (innerop
));
3990 middle_prec
= TYPE_PRECISION (TREE_TYPE (middleop
));
3991 final_prec
= TYPE_PRECISION (finaltype
);
3993 /* If the first conversion is not injective, the second must not
3995 if (wi::gtu_p (innermax
- innermin
,
3996 wi::mask
<widest_int
> (middle_prec
, false))
3997 && middle_prec
< final_prec
)
3999 /* We also want a medium value so that we can track the effect that
4000 narrowing conversions with sign change have. */
4001 inner_sgn
= TYPE_SIGN (TREE_TYPE (innerop
));
4002 if (inner_sgn
== UNSIGNED
)
4003 innermed
= wi::shifted_mask
<widest_int
> (1, inner_prec
- 1, false);
4006 if (wi::cmp (innermin
, innermed
, inner_sgn
) >= 0
4007 || wi::cmp (innermed
, innermax
, inner_sgn
) >= 0)
4008 innermed
= innermin
;
4010 middle_sgn
= TYPE_SIGN (TREE_TYPE (middleop
));
4011 middlemin
= wi::ext (innermin
, middle_prec
, middle_sgn
);
4012 middlemed
= wi::ext (innermed
, middle_prec
, middle_sgn
);
4013 middlemax
= wi::ext (innermax
, middle_prec
, middle_sgn
);
4015 /* Require that the final conversion applied to both the original
4016 and the intermediate range produces the same result. */
4017 final_sgn
= TYPE_SIGN (finaltype
);
4018 if (wi::ext (middlemin
, final_prec
, final_sgn
)
4019 != wi::ext (innermin
, final_prec
, final_sgn
)
4020 || wi::ext (middlemed
, final_prec
, final_sgn
)
4021 != wi::ext (innermed
, final_prec
, final_sgn
)
4022 || wi::ext (middlemax
, final_prec
, final_sgn
)
4023 != wi::ext (innermax
, final_prec
, final_sgn
))
4026 gimple_assign_set_rhs1 (stmt
, innerop
);
4027 fold_stmt (gsi
, follow_single_use_edges
);
4031 /* Simplify a conversion from integral SSA name to float in STMT. */
4034 simplify_using_ranges::simplify_float_conversion_using_ranges
4035 (gimple_stmt_iterator
*gsi
,
4038 tree rhs1
= gimple_assign_rhs1 (stmt
);
4039 const value_range
*vr
= get_value_range (rhs1
, stmt
);
4040 scalar_float_mode fltmode
4041 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
)));
4042 scalar_int_mode mode
;
4046 /* We can only handle constant ranges. */
4047 if (!range_int_cst_p (vr
))
4050 /* First check if we can use a signed type in place of an unsigned. */
4051 scalar_int_mode rhs_mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1
));
4052 if (TYPE_UNSIGNED (TREE_TYPE (rhs1
))
4053 && can_float_p (fltmode
, rhs_mode
, 0) != CODE_FOR_nothing
4054 && range_fits_type_p (vr
, TYPE_PRECISION (TREE_TYPE (rhs1
)), SIGNED
))
4056 /* If we can do the conversion in the current input mode do nothing. */
4057 else if (can_float_p (fltmode
, rhs_mode
,
4058 TYPE_UNSIGNED (TREE_TYPE (rhs1
))) != CODE_FOR_nothing
)
4060 /* Otherwise search for a mode we can use, starting from the narrowest
4061 integer mode available. */
4064 mode
= NARROWEST_INT_MODE
;
4067 /* If we cannot do a signed conversion to float from mode
4068 or if the value-range does not fit in the signed type
4069 try with a wider mode. */
4070 if (can_float_p (fltmode
, mode
, 0) != CODE_FOR_nothing
4071 && range_fits_type_p (vr
, GET_MODE_PRECISION (mode
), SIGNED
))
4074 /* But do not widen the input. Instead leave that to the
4075 optabs expansion code. */
4076 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
4077 || GET_MODE_PRECISION (mode
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
4082 /* It works, insert a truncation or sign-change before the
4083 float conversion. */
4084 tem
= make_ssa_name (build_nonstandard_integer_type
4085 (GET_MODE_PRECISION (mode
), 0));
4086 conv
= gimple_build_assign (tem
, NOP_EXPR
, rhs1
);
4087 gsi_insert_before (gsi
, conv
, GSI_SAME_STMT
);
4088 gimple_assign_set_rhs1 (stmt
, tem
);
4089 fold_stmt (gsi
, follow_single_use_edges
);
4094 /* Simplify an internal fn call using ranges if possible. */
4097 simplify_using_ranges::simplify_internal_call_using_ranges
4098 (gimple_stmt_iterator
*gsi
,
4101 enum tree_code subcode
;
4102 bool is_ubsan
= false;
4104 switch (gimple_call_internal_fn (stmt
))
4106 case IFN_UBSAN_CHECK_ADD
:
4107 subcode
= PLUS_EXPR
;
4110 case IFN_UBSAN_CHECK_SUB
:
4111 subcode
= MINUS_EXPR
;
4114 case IFN_UBSAN_CHECK_MUL
:
4115 subcode
= MULT_EXPR
;
4118 case IFN_ADD_OVERFLOW
:
4119 subcode
= PLUS_EXPR
;
4121 case IFN_SUB_OVERFLOW
:
4122 subcode
= MINUS_EXPR
;
4124 case IFN_MUL_OVERFLOW
:
4125 subcode
= MULT_EXPR
;
4131 tree op0
= gimple_call_arg (stmt
, 0);
4132 tree op1
= gimple_call_arg (stmt
, 1);
4136 type
= TREE_TYPE (op0
);
4137 if (VECTOR_TYPE_P (type
))
4140 else if (gimple_call_lhs (stmt
) == NULL_TREE
)
4143 type
= TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt
)));
4144 if (!check_for_binary_op_overflow (store
, subcode
, type
, op0
, op1
, &ovf
)
4145 || (is_ubsan
&& ovf
))
4149 location_t loc
= gimple_location (stmt
);
4151 g
= gimple_build_assign (gimple_call_lhs (stmt
), subcode
, op0
, op1
);
4154 int prec
= TYPE_PRECISION (type
);
4157 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
4158 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
4159 utype
= build_nonstandard_integer_type (prec
, 1);
4160 if (TREE_CODE (op0
) == INTEGER_CST
)
4161 op0
= fold_convert (utype
, op0
);
4162 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op0
)))
4164 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op0
);
4165 gimple_set_location (g
, loc
);
4166 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4167 op0
= gimple_assign_lhs (g
);
4169 if (TREE_CODE (op1
) == INTEGER_CST
)
4170 op1
= fold_convert (utype
, op1
);
4171 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op1
)))
4173 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op1
);
4174 gimple_set_location (g
, loc
);
4175 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4176 op1
= gimple_assign_lhs (g
);
4178 g
= gimple_build_assign (make_ssa_name (utype
), subcode
, op0
, op1
);
4179 gimple_set_location (g
, loc
);
4180 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4183 g
= gimple_build_assign (make_ssa_name (type
), NOP_EXPR
,
4184 gimple_assign_lhs (g
));
4185 gimple_set_location (g
, loc
);
4186 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4188 g
= gimple_build_assign (gimple_call_lhs (stmt
), COMPLEX_EXPR
,
4189 gimple_assign_lhs (g
),
4190 build_int_cst (type
, ovf
));
4192 gimple_set_location (g
, loc
);
4193 gsi_replace (gsi
, g
, false);
4197 /* Return true if VAR is a two-valued variable. Set a and b with the
4198 two-values when it is true. Return false otherwise. */
4201 simplify_using_ranges::two_valued_val_range_p (tree var
, tree
*a
, tree
*b
)
4203 value_range vr
= *get_value_range (var
);
4204 vr
.normalize_symbolics ();
4205 if (vr
.varying_p () || vr
.undefined_p ())
4208 if ((vr
.num_pairs () == 1 && vr
.upper_bound () - vr
.lower_bound () == 1)
4209 || (vr
.num_pairs () == 2
4210 && vr
.lower_bound (0) == vr
.upper_bound (0)
4211 && vr
.lower_bound (1) == vr
.upper_bound (1)))
4213 *a
= wide_int_to_tree (TREE_TYPE (var
), vr
.lower_bound ());
4214 *b
= wide_int_to_tree (TREE_TYPE (var
), vr
.upper_bound ());
4220 simplify_using_ranges::simplify_using_ranges (range_query
*store
)
4223 to_remove_edges
= vNULL
;
4224 to_update_switch_stmts
= vNULL
;
4227 simplify_using_ranges::~simplify_using_ranges ()
4229 cleanup_edges_and_switches ();
4232 /* Simplify STMT using ranges if possible. */
4235 simplify_using_ranges::simplify (gimple_stmt_iterator
*gsi
)
4237 gimple
*stmt
= gsi_stmt (*gsi
);
4238 if (is_gimple_assign (stmt
))
4240 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
4241 tree rhs1
= gimple_assign_rhs1 (stmt
);
4242 tree rhs2
= gimple_assign_rhs2 (stmt
);
4243 tree lhs
= gimple_assign_lhs (stmt
);
4244 tree val1
= NULL_TREE
, val2
= NULL_TREE
;
4245 use_operand_p use_p
;
4250 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4252 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4256 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4258 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4260 if (TREE_CODE_CLASS (rhs_code
) == tcc_binary
4261 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4262 && ((TREE_CODE (rhs1
) == INTEGER_CST
4263 && TREE_CODE (rhs2
) == SSA_NAME
)
4264 || (TREE_CODE (rhs2
) == INTEGER_CST
4265 && TREE_CODE (rhs1
) == SSA_NAME
))
4266 && single_imm_use (lhs
, &use_p
, &use_stmt
)
4267 && gimple_code (use_stmt
) == GIMPLE_COND
)
4270 tree new_rhs1
= NULL_TREE
;
4271 tree new_rhs2
= NULL_TREE
;
4272 tree cmp_var
= NULL_TREE
;
4274 if (TREE_CODE (rhs2
) == SSA_NAME
4275 && two_valued_val_range_p (rhs2
, &val1
, &val2
))
4277 /* Optimize RHS1 OP [VAL1, VAL2]. */
4278 new_rhs1
= int_const_binop (rhs_code
, rhs1
, val1
);
4279 new_rhs2
= int_const_binop (rhs_code
, rhs1
, val2
);
4282 else if (TREE_CODE (rhs1
) == SSA_NAME
4283 && two_valued_val_range_p (rhs1
, &val1
, &val2
))
4285 /* Optimize [VAL1, VAL2] OP RHS2. */
4286 new_rhs1
= int_const_binop (rhs_code
, val1
, rhs2
);
4287 new_rhs2
= int_const_binop (rhs_code
, val2
, rhs2
);
4291 /* If we could not find two-vals or the optimzation is invalid as
4292 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4293 if (new_rhs1
&& new_rhs2
)
4295 tree cond
= build2 (EQ_EXPR
, boolean_type_node
, cmp_var
, val1
);
4296 gimple_assign_set_rhs_with_ops (gsi
,
4300 update_stmt (gsi_stmt (*gsi
));
4301 fold_stmt (gsi
, follow_single_use_edges
);
4310 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4311 if the RHS is zero or one, and the LHS are known to be boolean
4313 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4314 return simplify_truth_ops_using_ranges (gsi
, stmt
);
4317 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4318 and BIT_AND_EXPR respectively if the first operand is greater
4319 than zero and the second operand is an exact power of two.
4320 Also optimize TRUNC_MOD_EXPR away if the second operand is
4321 constant and the first operand already has the right value
4323 case TRUNC_DIV_EXPR
:
4324 case TRUNC_MOD_EXPR
:
4325 if ((TREE_CODE (rhs1
) == SSA_NAME
4326 || TREE_CODE (rhs1
) == INTEGER_CST
)
4327 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4328 return simplify_div_or_mod_using_ranges (gsi
, stmt
);
4331 /* Transform ABS (X) into X or -X as appropriate. */
4333 if (TREE_CODE (rhs1
) == SSA_NAME
4334 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4335 return simplify_abs_using_ranges (gsi
, stmt
);
4340 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4341 if all the bits being cleared are already cleared or
4342 all the bits being set are already set. */
4343 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4344 return simplify_bit_ops_using_ranges (gsi
, stmt
);
4348 if (TREE_CODE (rhs1
) == SSA_NAME
4349 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4350 return simplify_conversion_using_ranges (gsi
, stmt
);
4354 if (TREE_CODE (rhs1
) == SSA_NAME
4355 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4356 return simplify_float_conversion_using_ranges (gsi
, stmt
);
4361 return simplify_min_or_max_using_ranges (gsi
, stmt
);
4367 else if (gimple_code (stmt
) == GIMPLE_COND
)
4368 return simplify_cond_using_ranges_1 (as_a
<gcond
*> (stmt
));
4369 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
4370 return simplify_switch_using_ranges (as_a
<gswitch
*> (stmt
));
4371 else if (is_gimple_call (stmt
)
4372 && gimple_call_internal_p (stmt
))
4373 return simplify_internal_call_using_ranges (gsi
, stmt
);
4378 /* Set the lattice entry for VAR to VR. */
4381 vr_values::set_vr_value (tree var
, value_range_equiv
*vr
)
4383 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4385 vr_value
[SSA_NAME_VERSION (var
)] = vr
;
4388 /* Swap the lattice entry for VAR with VR and return the old entry. */
4391 vr_values::swap_vr_value (tree var
, value_range_equiv
*vr
)
4393 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4395 std::swap (vr_value
[SSA_NAME_VERSION (var
)], vr
);