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
)
152 /* If we have no recorded ranges, then return NULL. */
156 value_range_equiv
*vr
= get_lattice_entry (var
);
158 /* Reallocate the lattice if needed. */
161 unsigned int old_sz
= num_vr_values
;
162 num_vr_values
= num_ssa_names
+ num_ssa_names
/ 10;
163 vr_value
= XRESIZEVEC (value_range_equiv
*, vr_value
, num_vr_values
);
164 for ( ; old_sz
< num_vr_values
; old_sz
++)
165 vr_value
[old_sz
] = NULL
;
167 /* Now that the lattice has been resized, we should never fail. */
168 vr
= get_lattice_entry (var
);
175 /* Set the lattice entry for DEF to VARYING. */
178 vr_values::set_def_to_varying (const_tree def
)
180 value_range_equiv
*vr
= get_lattice_entry (def
);
182 vr
->set_varying (TREE_TYPE (def
));
185 /* Set value-ranges of all SSA names defined by STMT to varying. */
188 vr_values::set_defs_to_varying (gimple
*stmt
)
192 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_DEF
)
193 set_def_to_varying (def
);
196 /* Update the value range and equivalence set for variable VAR to
197 NEW_VR. Return true if NEW_VR is different from VAR's previous
200 NOTE: This function assumes that NEW_VR is a temporary value range
201 object created for the sole purpose of updating VAR's range. The
202 storage used by the equivalence set from NEW_VR will be freed by
203 this function. Do not call update_value_range when NEW_VR
204 is the range object associated with another SSA name. */
207 vr_values::update_value_range (const_tree var
, value_range_equiv
*new_vr
)
209 value_range_equiv
*old_vr
;
212 /* If there is a value-range on the SSA name from earlier analysis
214 if (INTEGRAL_TYPE_P (TREE_TYPE (var
)))
216 value_range_equiv nr
;
217 get_range_info (var
, nr
);
218 if (!nr
.undefined_p ())
219 new_vr
->intersect (&nr
);
222 /* Update the value range, if necessary. If we cannot allocate a lattice
223 entry for VAR keep it at VARYING. This happens when DOM feeds us stmts
224 with SSA names allocated after setting up the lattice. */
225 old_vr
= get_lattice_entry (var
);
228 is_new
= !old_vr
->equal_p (*new_vr
, /*ignore_equivs=*/false);
232 /* Do not allow transitions up the lattice. The following
233 is slightly more awkward than just new_vr->type < old_vr->type
234 because VR_RANGE and VR_ANTI_RANGE need to be considered
235 the same. We may not have is_new when transitioning to
236 UNDEFINED. If old_vr->type is VARYING, we shouldn't be
237 called, if we are anyway, keep it VARYING. */
238 if (old_vr
->varying_p ())
240 new_vr
->set_varying (TREE_TYPE (var
));
243 else if (new_vr
->undefined_p ())
245 old_vr
->set_varying (TREE_TYPE (var
));
246 new_vr
->set_varying (TREE_TYPE (var
));
250 old_vr
->set (new_vr
->min (), new_vr
->max (), new_vr
->equiv (),
254 new_vr
->equiv_clear ();
259 /* Return true if value range VR involves exactly one symbol SYM. */
262 symbolic_range_based_on_p (value_range
*vr
, const_tree sym
)
264 bool neg
, min_has_symbol
, max_has_symbol
;
267 if (is_gimple_min_invariant (vr
->min ()))
268 min_has_symbol
= false;
269 else if (get_single_symbol (vr
->min (), &neg
, &inv
) == sym
)
270 min_has_symbol
= true;
274 if (is_gimple_min_invariant (vr
->max ()))
275 max_has_symbol
= false;
276 else if (get_single_symbol (vr
->max (), &neg
, &inv
) == sym
)
277 max_has_symbol
= true;
281 return (min_has_symbol
|| max_has_symbol
);
284 /* Return true if the result of assignment STMT is know to be non-zero. */
287 gimple_assign_nonzero_p (gimple
*stmt
)
289 enum tree_code code
= gimple_assign_rhs_code (stmt
);
290 bool strict_overflow_p
;
291 switch (get_gimple_rhs_class (code
))
293 case GIMPLE_UNARY_RHS
:
294 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
295 gimple_expr_type (stmt
),
296 gimple_assign_rhs1 (stmt
),
298 case GIMPLE_BINARY_RHS
:
299 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt
),
300 gimple_expr_type (stmt
),
301 gimple_assign_rhs1 (stmt
),
302 gimple_assign_rhs2 (stmt
),
304 case GIMPLE_TERNARY_RHS
:
306 case GIMPLE_SINGLE_RHS
:
307 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt
),
309 case GIMPLE_INVALID_RHS
:
316 /* Return true if STMT is known to compute a non-zero value. */
319 gimple_stmt_nonzero_p (gimple
*stmt
)
321 switch (gimple_code (stmt
))
324 return gimple_assign_nonzero_p (stmt
);
327 gcall
*call_stmt
= as_a
<gcall
*> (stmt
);
328 return (gimple_call_nonnull_result_p (call_stmt
)
329 || gimple_call_nonnull_arg (call_stmt
));
335 /* Like tree_expr_nonzero_p, but this function uses value ranges
339 vr_values::vrp_stmt_computes_nonzero (gimple
*stmt
)
341 if (gimple_stmt_nonzero_p (stmt
))
344 /* If we have an expression of the form &X->a, then the expression
345 is nonnull if X is nonnull. */
346 if (is_gimple_assign (stmt
)
347 && gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
349 tree expr
= gimple_assign_rhs1 (stmt
);
350 poly_int64 bitsize
, bitpos
;
353 int unsignedp
, reversep
, volatilep
;
354 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
355 &bitpos
, &offset
, &mode
, &unsignedp
,
356 &reversep
, &volatilep
);
358 if (base
!= NULL_TREE
359 && TREE_CODE (base
) == MEM_REF
360 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
362 poly_offset_int off
= 0;
363 bool off_cst
= false;
364 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
366 off
= mem_ref_offset (base
);
368 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
370 off
<<= LOG2_BITS_PER_UNIT
;
374 /* If &X->a is equal to X and X is ~[0, 0], the result is too.
375 For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
376 allow going from non-NULL pointer to NULL. */
377 if ((off_cst
&& known_eq (off
, 0))
378 || (flag_delete_null_pointer_checks
379 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))))
381 const value_range_equiv
*vr
382 = get_value_range (TREE_OPERAND (base
, 0));
383 if (!range_includes_zero_p (vr
))
386 /* If MEM_REF has a "positive" offset, consider it non-NULL
387 always, for -fdelete-null-pointer-checks also "negative"
388 ones. Punt for unknown offsets (e.g. variable ones). */
389 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
392 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
400 /* Returns true if EXPR is a valid value (as expected by compare_values) --
401 a gimple invariant, or SSA_NAME +- CST. */
404 valid_value_p (tree expr
)
406 if (TREE_CODE (expr
) == SSA_NAME
)
409 if (TREE_CODE (expr
) == PLUS_EXPR
410 || TREE_CODE (expr
) == MINUS_EXPR
)
411 return (TREE_CODE (TREE_OPERAND (expr
, 0)) == SSA_NAME
412 && TREE_CODE (TREE_OPERAND (expr
, 1)) == INTEGER_CST
);
414 return is_gimple_min_invariant (expr
);
417 /* If OP has a value range with a single constant value return that,
418 otherwise return NULL_TREE. This returns OP itself if OP is a
422 vr_values::op_with_constant_singleton_value_range (tree op
)
424 if (is_gimple_min_invariant (op
))
427 if (TREE_CODE (op
) != SSA_NAME
)
431 if (get_value_range (op
)->singleton_p (&t
))
436 /* Return true if op is in a boolean [0, 1] value-range. */
439 simplify_using_ranges::op_with_boolean_value_range_p (tree op
)
441 if (TYPE_PRECISION (TREE_TYPE (op
)) == 1)
444 if (integer_zerop (op
)
445 || integer_onep (op
))
448 if (TREE_CODE (op
) != SSA_NAME
)
451 /* ?? Errr, this should probably check for [0,0] and [1,1] as well
453 const value_range
*vr
= get_value_range (op
);
454 return *vr
== value_range (build_zero_cst (TREE_TYPE (op
)),
455 build_one_cst (TREE_TYPE (op
)));
458 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
459 true and store it in *VR_P. */
462 vr_values::extract_range_for_var_from_comparison_expr (tree var
,
463 enum tree_code cond_code
,
465 value_range_equiv
*vr_p
)
468 const value_range_equiv
*limit_vr
;
469 type
= TREE_TYPE (var
);
471 /* For pointer arithmetic, we only keep track of pointer equality
472 and inequality. If we arrive here with unfolded conditions like
473 _1 > _1 do not derive anything. */
474 if ((POINTER_TYPE_P (type
) && cond_code
!= NE_EXPR
&& cond_code
!= EQ_EXPR
)
477 vr_p
->set_varying (type
);
481 /* If LIMIT is another SSA name and LIMIT has a range of its own,
482 try to use LIMIT's range to avoid creating symbolic ranges
484 limit_vr
= (TREE_CODE (limit
) == SSA_NAME
) ? get_value_range (limit
) : NULL
;
486 /* LIMIT's range is only interesting if it has any useful information. */
488 || limit_vr
->undefined_p ()
489 || limit_vr
->varying_p ()
490 || (limit_vr
->symbolic_p ()
491 && ! (limit_vr
->kind () == VR_RANGE
492 && (limit_vr
->min () == limit_vr
->max ()
493 || operand_equal_p (limit_vr
->min (),
494 limit_vr
->max (), 0)))))
497 /* Initially, the new range has the same set of equivalences of
498 VAR's range. This will be revised before returning the final
499 value. Since assertions may be chained via mutually exclusive
500 predicates, we will need to trim the set of equivalences before
502 gcc_assert (vr_p
->equiv () == NULL
);
503 vr_p
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
505 /* Extract a new range based on the asserted comparison for VAR and
506 LIMIT's value range. Notice that if LIMIT has an anti-range, we
507 will only use it for equality comparisons (EQ_EXPR). For any
508 other kind of assertion, we cannot derive a range from LIMIT's
509 anti-range that can be used to describe the new range. For
510 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
511 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
512 no single range for x_2 that could describe LE_EXPR, so we might
513 as well build the range [b_4, +INF] for it.
514 One special case we handle is extracting a range from a
515 range test encoded as (unsigned)var + CST <= limit. */
516 if (TREE_CODE (op
) == NOP_EXPR
517 || TREE_CODE (op
) == PLUS_EXPR
)
519 if (TREE_CODE (op
) == PLUS_EXPR
)
521 min
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (TREE_OPERAND (op
, 1)),
522 TREE_OPERAND (op
, 1));
523 max
= int_const_binop (PLUS_EXPR
, limit
, min
);
524 op
= TREE_OPERAND (op
, 0);
528 min
= build_int_cst (TREE_TYPE (var
), 0);
532 /* Make sure to not set TREE_OVERFLOW on the final type
533 conversion. We are willingly interpreting large positive
534 unsigned values as negative signed values here. */
535 min
= force_fit_type (TREE_TYPE (var
), wi::to_widest (min
), 0, false);
536 max
= force_fit_type (TREE_TYPE (var
), wi::to_widest (max
), 0, false);
538 /* We can transform a max, min range to an anti-range or
539 vice-versa. Use set_and_canonicalize which does this for
541 if (cond_code
== LE_EXPR
)
542 vr_p
->set (min
, max
, vr_p
->equiv ());
543 else if (cond_code
== GT_EXPR
)
544 vr_p
->set (min
, max
, vr_p
->equiv (), VR_ANTI_RANGE
);
548 else if (cond_code
== EQ_EXPR
)
550 enum value_range_kind range_kind
;
554 range_kind
= limit_vr
->kind ();
555 min
= limit_vr
->min ();
556 max
= limit_vr
->max ();
560 range_kind
= VR_RANGE
;
565 vr_p
->update (min
, max
, range_kind
);
567 /* When asserting the equality VAR == LIMIT and LIMIT is another
568 SSA name, the new range will also inherit the equivalence set
570 if (TREE_CODE (limit
) == SSA_NAME
)
571 vr_p
->equiv_add (limit
, get_value_range (limit
), &vrp_equiv_obstack
);
573 else if (cond_code
== NE_EXPR
)
575 /* As described above, when LIMIT's range is an anti-range and
576 this assertion is an inequality (NE_EXPR), then we cannot
577 derive anything from the anti-range. For instance, if
578 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
579 not imply that VAR's range is [0, 0]. So, in the case of
580 anti-ranges, we just assert the inequality using LIMIT and
583 If LIMIT_VR is a range, we can only use it to build a new
584 anti-range if LIMIT_VR is a single-valued range. For
585 instance, if LIMIT_VR is [0, 1], the predicate
586 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
587 Rather, it means that for value 0 VAR should be ~[0, 0]
588 and for value 1, VAR should be ~[1, 1]. We cannot
589 represent these ranges.
591 The only situation in which we can build a valid
592 anti-range is when LIMIT_VR is a single-valued range
593 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
594 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
596 && limit_vr
->kind () == VR_RANGE
597 && compare_values (limit_vr
->min (), limit_vr
->max ()) == 0)
599 min
= limit_vr
->min ();
600 max
= limit_vr
->max ();
604 /* In any other case, we cannot use LIMIT's range to build a
609 /* If MIN and MAX cover the whole range for their type, then
610 just use the original LIMIT. */
611 if (INTEGRAL_TYPE_P (type
)
612 && vrp_val_is_min (min
)
613 && vrp_val_is_max (max
))
616 vr_p
->set (min
, max
, vr_p
->equiv (), VR_ANTI_RANGE
);
618 else if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
620 min
= TYPE_MIN_VALUE (type
);
622 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
626 /* If LIMIT_VR is of the form [N1, N2], we need to build the
627 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
629 max
= limit_vr
->max ();
632 /* If the maximum value forces us to be out of bounds, simply punt.
633 It would be pointless to try and do anything more since this
634 all should be optimized away above us. */
635 if (cond_code
== LT_EXPR
636 && compare_values (max
, min
) == 0)
637 vr_p
->set_varying (TREE_TYPE (min
));
640 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
641 if (cond_code
== LT_EXPR
)
643 if (TYPE_PRECISION (TREE_TYPE (max
)) == 1
644 && !TYPE_UNSIGNED (TREE_TYPE (max
)))
645 max
= fold_build2 (PLUS_EXPR
, TREE_TYPE (max
), max
,
646 build_int_cst (TREE_TYPE (max
), -1));
648 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max
), max
,
649 build_int_cst (TREE_TYPE (max
), 1));
650 /* Signal to compare_values_warnv this expr doesn't overflow. */
652 TREE_NO_WARNING (max
) = 1;
655 vr_p
->update (min
, max
);
658 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
660 max
= TYPE_MAX_VALUE (type
);
662 if (limit_vr
== NULL
|| limit_vr
->kind () == VR_ANTI_RANGE
)
666 /* If LIMIT_VR is of the form [N1, N2], we need to build the
667 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
669 min
= limit_vr
->min ();
672 /* If the minimum value forces us to be out of bounds, simply punt.
673 It would be pointless to try and do anything more since this
674 all should be optimized away above us. */
675 if (cond_code
== GT_EXPR
676 && compare_values (min
, max
) == 0)
677 vr_p
->set_varying (TREE_TYPE (min
));
680 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
681 if (cond_code
== GT_EXPR
)
683 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
684 && !TYPE_UNSIGNED (TREE_TYPE (min
)))
685 min
= fold_build2 (MINUS_EXPR
, TREE_TYPE (min
), min
,
686 build_int_cst (TREE_TYPE (min
), -1));
688 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min
), min
,
689 build_int_cst (TREE_TYPE (min
), 1));
690 /* Signal to compare_values_warnv this expr doesn't overflow. */
692 TREE_NO_WARNING (min
) = 1;
695 vr_p
->update (min
, max
);
701 /* Finally intersect the new range with what we already know about var. */
702 vr_p
->intersect (get_value_range (var
));
705 /* Extract value range information from an ASSERT_EXPR EXPR and store
709 vr_values::extract_range_from_assert (value_range_equiv
*vr_p
, tree expr
)
711 tree var
= ASSERT_EXPR_VAR (expr
);
712 tree cond
= ASSERT_EXPR_COND (expr
);
714 enum tree_code cond_code
;
715 gcc_assert (COMPARISON_CLASS_P (cond
));
717 /* Find VAR in the ASSERT_EXPR conditional. */
718 if (var
== TREE_OPERAND (cond
, 0)
719 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PLUS_EXPR
720 || TREE_CODE (TREE_OPERAND (cond
, 0)) == NOP_EXPR
)
722 /* If the predicate is of the form VAR COMP LIMIT, then we just
723 take LIMIT from the RHS and use the same comparison code. */
724 cond_code
= TREE_CODE (cond
);
725 limit
= TREE_OPERAND (cond
, 1);
726 op
= TREE_OPERAND (cond
, 0);
730 /* If the predicate is of the form LIMIT COMP VAR, then we need
731 to flip around the comparison code to create the proper range
733 cond_code
= swap_tree_comparison (TREE_CODE (cond
));
734 limit
= TREE_OPERAND (cond
, 0);
735 op
= TREE_OPERAND (cond
, 1);
737 extract_range_for_var_from_comparison_expr (var
, cond_code
, op
,
741 /* Extract range information from SSA name VAR and store it in VR. If
742 VAR has an interesting range, use it. Otherwise, create the
743 range [VAR, VAR] and return it. This is useful in situations where
744 we may have conditionals testing values of VARYING names. For
751 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
755 vr_values::extract_range_from_ssa_name (value_range_equiv
*vr
, tree var
)
757 const value_range_equiv
*var_vr
= get_value_range (var
);
759 if (!var_vr
->varying_p ())
760 vr
->deep_copy (var_vr
);
764 if (!vr
->undefined_p ())
765 vr
->equiv_add (var
, get_value_range (var
), &vrp_equiv_obstack
);
768 /* Extract range information from a binary expression OP0 CODE OP1 based on
769 the ranges of each of its operands with resulting type EXPR_TYPE.
770 The resulting range is stored in *VR. */
773 vr_values::extract_range_from_binary_expr (value_range_equiv
*vr
,
775 tree expr_type
, tree op0
, tree op1
)
777 /* Get value ranges for each operand. For constant operands, create
778 a new value range with the operand to simplify processing. */
779 value_range vr0
, vr1
;
780 if (TREE_CODE (op0
) == SSA_NAME
)
781 vr0
= *(get_value_range (op0
));
782 else if (is_gimple_min_invariant (op0
))
785 vr0
.set_varying (TREE_TYPE (op0
));
787 if (TREE_CODE (op1
) == SSA_NAME
)
788 vr1
= *(get_value_range (op1
));
789 else if (is_gimple_min_invariant (op1
))
792 vr1
.set_varying (TREE_TYPE (op1
));
794 /* If one argument is varying, we can sometimes still deduce a
795 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
796 if (INTEGRAL_TYPE_P (TREE_TYPE (op0
))
797 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0
)))
799 if (vr0
.varying_p () && !vr1
.varying_p ())
800 vr0
= value_range (vrp_val_min (expr_type
), vrp_val_max (expr_type
));
801 else if (vr1
.varying_p () && !vr0
.varying_p ())
802 vr1
= value_range (vrp_val_min (expr_type
), vrp_val_max (expr_type
));
805 range_fold_binary_expr (vr
, code
, expr_type
, &vr0
, &vr1
);
807 /* Set value_range for n in following sequence:
808 def = __builtin_memchr (arg, 0, sz)
810 Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
813 && code
== POINTER_DIFF_EXPR
814 && TREE_CODE (op0
) == SSA_NAME
815 && TREE_CODE (op1
) == SSA_NAME
)
817 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
818 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
819 gcall
*call_stmt
= NULL
;
821 if (TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
822 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
823 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
824 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
825 && (call_stmt
= dyn_cast
<gcall
*>(SSA_NAME_DEF_STMT (op0
)))
826 && gimple_call_builtin_p (call_stmt
, BUILT_IN_MEMCHR
)
827 && operand_equal_p (op0
, gimple_call_lhs (call_stmt
), 0)
828 && operand_equal_p (op1
, gimple_call_arg (call_stmt
, 0), 0)
829 && integer_zerop (gimple_call_arg (call_stmt
, 1)))
831 tree max
= vrp_val_max (ptrdiff_type_node
);
832 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
833 tree range_min
= build_zero_cst (expr_type
);
834 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
835 vr
->set (range_min
, range_max
);
840 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
841 and based on the other operand, for example if it was deduced from a
842 symbolic comparison. When a bound of the range of the first operand
843 is invariant, we set the corresponding bound of the new range to INF
844 in order to avoid recursing on the range of the second operand. */
846 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
847 && TREE_CODE (op1
) == SSA_NAME
848 && vr0
.kind () == VR_RANGE
849 && symbolic_range_based_on_p (&vr0
, op1
))
851 const bool minus_p
= (code
== MINUS_EXPR
);
854 /* Try with VR0 and [-INF, OP1]. */
855 if (is_gimple_min_invariant (minus_p
? vr0
.max () : vr0
.min ()))
856 n_vr1
.set (vrp_val_min (expr_type
), op1
);
858 /* Try with VR0 and [OP1, +INF]. */
859 else if (is_gimple_min_invariant (minus_p
? vr0
.min () : vr0
.max ()))
860 n_vr1
.set (op1
, vrp_val_max (expr_type
));
862 /* Try with VR0 and [OP1, OP1]. */
864 n_vr1
.set (op1
, op1
);
866 range_fold_binary_expr (vr
, code
, expr_type
, &vr0
, &n_vr1
);
870 && (code
== PLUS_EXPR
|| code
== MINUS_EXPR
)
871 && TREE_CODE (op0
) == SSA_NAME
872 && vr1
.kind () == VR_RANGE
873 && symbolic_range_based_on_p (&vr1
, op0
))
875 const bool minus_p
= (code
== MINUS_EXPR
);
878 /* Try with [-INF, OP0] and VR1. */
879 if (is_gimple_min_invariant (minus_p
? vr1
.max () : vr1
.min ()))
880 n_vr0
.set (vrp_val_min (expr_type
), op0
);
882 /* Try with [OP0, +INF] and VR1. */
883 else if (is_gimple_min_invariant (minus_p
? vr1
.min (): vr1
.max ()))
884 n_vr0
.set (op0
, vrp_val_max (expr_type
));
886 /* Try with [OP0, OP0] and VR1. */
890 range_fold_binary_expr (vr
, code
, expr_type
, &n_vr0
, &vr1
);
893 /* If we didn't derive a range for MINUS_EXPR, and
894 op1's range is ~[op0,op0] or vice-versa, then we
895 can derive a non-null range. This happens often for
896 pointer subtraction. */
898 && (code
== MINUS_EXPR
|| code
== POINTER_DIFF_EXPR
)
899 && TREE_CODE (op0
) == SSA_NAME
900 && ((vr0
.kind () == VR_ANTI_RANGE
902 && vr0
.min () == vr0
.max ())
903 || (vr1
.kind () == VR_ANTI_RANGE
905 && vr1
.min () == vr1
.max ())))
907 vr
->set_nonzero (expr_type
);
912 /* Extract range information from a unary expression CODE OP0 based on
913 the range of its operand with resulting type TYPE.
914 The resulting range is stored in *VR. */
917 vr_values::extract_range_from_unary_expr (value_range_equiv
*vr
,
923 /* Get value ranges for the operand. For constant operands, create
924 a new value range with the operand to simplify processing. */
925 if (TREE_CODE (op0
) == SSA_NAME
)
926 vr0
= *(get_value_range (op0
));
927 else if (is_gimple_min_invariant (op0
))
930 vr0
.set_varying (type
);
932 range_fold_unary_expr (vr
, code
, type
, &vr0
, TREE_TYPE (op0
));
936 /* Extract range information from a conditional expression STMT based on
937 the ranges of each of its operands and the expression code. */
940 vr_values::extract_range_from_cond_expr (value_range_equiv
*vr
, gassign
*stmt
)
942 /* Get value ranges for each operand. For constant operands, create
943 a new value range with the operand to simplify processing. */
944 tree op0
= gimple_assign_rhs2 (stmt
);
945 value_range_equiv tem0
;
946 const value_range_equiv
*vr0
= &tem0
;
947 if (TREE_CODE (op0
) == SSA_NAME
)
948 vr0
= get_value_range (op0
);
949 else if (is_gimple_min_invariant (op0
))
952 tem0
.set_varying (TREE_TYPE (op0
));
954 tree op1
= gimple_assign_rhs3 (stmt
);
955 value_range_equiv tem1
;
956 const value_range_equiv
*vr1
= &tem1
;
957 if (TREE_CODE (op1
) == SSA_NAME
)
958 vr1
= get_value_range (op1
);
959 else if (is_gimple_min_invariant (op1
))
962 tem1
.set_varying (TREE_TYPE (op1
));
964 /* The resulting value range is the union of the operand ranges */
970 /* Extract range information from a comparison expression EXPR based
971 on the range of its operand and the expression code. */
974 vr_values::extract_range_from_comparison (value_range_equiv
*vr
,
976 tree type
, tree op0
, tree op1
)
980 = simplifier
.vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
,
984 /* Since this expression was found on the RHS of an assignment,
985 its type may be different from _Bool. Convert VAL to EXPR's
987 val
= fold_convert (type
, val
);
988 if (is_gimple_min_invariant (val
))
991 vr
->update (val
, val
);
994 /* The result of a comparison is always true or false. */
995 set_value_range_to_truthvalue (vr
, type
);
998 /* Helper function for simplify_internal_call_using_ranges and
999 extract_range_basic. Return true if OP0 SUBCODE OP1 for
1000 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
1001 always overflow. Set *OVF to true if it is known to always
1005 check_for_binary_op_overflow (vr_values
*store
,
1006 enum tree_code subcode
, tree type
,
1007 tree op0
, tree op1
, bool *ovf
)
1009 value_range vr0
, vr1
;
1010 if (TREE_CODE (op0
) == SSA_NAME
)
1011 vr0
= *store
->get_value_range (op0
);
1012 else if (TREE_CODE (op0
) == INTEGER_CST
)
1015 vr0
.set_varying (TREE_TYPE (op0
));
1017 if (TREE_CODE (op1
) == SSA_NAME
)
1018 vr1
= *store
->get_value_range (op1
);
1019 else if (TREE_CODE (op1
) == INTEGER_CST
)
1022 vr1
.set_varying (TREE_TYPE (op1
));
1024 tree vr0min
= vr0
.min (), vr0max
= vr0
.max ();
1025 tree vr1min
= vr1
.min (), vr1max
= vr1
.max ();
1026 if (!range_int_cst_p (&vr0
)
1027 || TREE_OVERFLOW (vr0min
)
1028 || TREE_OVERFLOW (vr0max
))
1030 vr0min
= vrp_val_min (TREE_TYPE (op0
));
1031 vr0max
= vrp_val_max (TREE_TYPE (op0
));
1033 if (!range_int_cst_p (&vr1
)
1034 || TREE_OVERFLOW (vr1min
)
1035 || TREE_OVERFLOW (vr1max
))
1037 vr1min
= vrp_val_min (TREE_TYPE (op1
));
1038 vr1max
= vrp_val_max (TREE_TYPE (op1
));
1040 *ovf
= arith_overflowed_p (subcode
, type
, vr0min
,
1041 subcode
== MINUS_EXPR
? vr1max
: vr1min
);
1042 if (arith_overflowed_p (subcode
, type
, vr0max
,
1043 subcode
== MINUS_EXPR
? vr1min
: vr1max
) != *ovf
)
1045 if (subcode
== MULT_EXPR
)
1047 if (arith_overflowed_p (subcode
, type
, vr0min
, vr1max
) != *ovf
1048 || arith_overflowed_p (subcode
, type
, vr0max
, vr1min
) != *ovf
)
1053 /* So far we found that there is an overflow on the boundaries.
1054 That doesn't prove that there is an overflow even for all values
1055 in between the boundaries. For that compute widest_int range
1056 of the result and see if it doesn't overlap the range of
1058 widest_int wmin
, wmax
;
1061 w
[0] = wi::to_widest (vr0min
);
1062 w
[1] = wi::to_widest (vr0max
);
1063 w
[2] = wi::to_widest (vr1min
);
1064 w
[3] = wi::to_widest (vr1max
);
1065 for (i
= 0; i
< 4; i
++)
1071 wt
= wi::add (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1074 wt
= wi::sub (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1077 wt
= wi::mul (w
[i
& 1], w
[2 + (i
& 2) / 2]);
1089 wmin
= wi::smin (wmin
, wt
);
1090 wmax
= wi::smax (wmax
, wt
);
1093 /* The result of op0 CODE op1 is known to be in range
1095 widest_int wtmin
= wi::to_widest (vrp_val_min (type
));
1096 widest_int wtmax
= wi::to_widest (vrp_val_max (type
));
1097 /* If all values in [wmin, wmax] are smaller than
1098 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1099 the arithmetic operation will always overflow. */
1100 if (wmax
< wtmin
|| wmin
> wtmax
)
1107 /* Try to derive a nonnegative or nonzero range out of STMT relying
1108 primarily on generic routines in fold in conjunction with range data.
1109 Store the result in *VR */
1112 vr_values::extract_range_basic (value_range_equiv
*vr
, gimple
*stmt
)
1115 tree type
= gimple_expr_type (stmt
);
1117 if (is_gimple_call (stmt
))
1120 int mini
, maxi
, zerov
= 0, prec
;
1121 enum tree_code subcode
= ERROR_MARK
;
1122 combined_fn cfn
= gimple_call_combined_fn (stmt
);
1123 scalar_int_mode mode
;
1127 case CFN_BUILT_IN_CONSTANT_P
:
1128 /* Resolve calls to __builtin_constant_p after inlining. */
1129 if (cfun
->after_inlining
)
1131 vr
->set_zero (type
);
1136 /* Both __builtin_ffs* and __builtin_popcount return
1140 arg
= gimple_call_arg (stmt
, 0);
1141 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1144 if (TREE_CODE (arg
) == SSA_NAME
)
1146 const value_range_equiv
*vr0
= get_value_range (arg
);
1147 /* If arg is non-zero, then ffs or popcount are non-zero. */
1148 if (range_includes_zero_p (vr0
) == 0)
1150 /* If some high bits are known to be zero,
1151 we can decrease the maximum. */
1152 if (vr0
->kind () == VR_RANGE
1153 && TREE_CODE (vr0
->max ()) == INTEGER_CST
1154 && !operand_less_p (vr0
->min (),
1155 build_zero_cst (TREE_TYPE (vr0
->min ()))))
1156 maxi
= tree_floor_log2 (vr0
->max ()) + 1;
1159 /* __builtin_parity* returns [0, 1]. */
1164 /* __builtin_c[lt]z* return [0, prec-1], except for
1165 when the argument is 0, but that is undefined behavior.
1166 On many targets where the CLZ RTL or optab value is defined
1167 for 0 the value is prec, so include that in the range
1170 arg
= gimple_call_arg (stmt
, 0);
1171 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1174 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1175 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
1176 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
)
1177 /* Handle only the single common value. */
1179 /* Magic value to give up, unless vr0 proves
1182 if (TREE_CODE (arg
) == SSA_NAME
)
1184 const value_range_equiv
*vr0
= get_value_range (arg
);
1185 /* From clz of VR_RANGE minimum we can compute
1187 if (vr0
->kind () == VR_RANGE
1188 && TREE_CODE (vr0
->min ()) == INTEGER_CST
)
1190 maxi
= prec
- 1 - tree_floor_log2 (vr0
->min ());
1194 else if (vr0
->kind () == VR_ANTI_RANGE
1195 && integer_zerop (vr0
->min ()))
1202 /* From clz of VR_RANGE maximum we can compute
1204 if (vr0
->kind () == VR_RANGE
1205 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1207 mini
= prec
- 1 - tree_floor_log2 (vr0
->max ());
1215 /* __builtin_ctz* return [0, prec-1], except for
1216 when the argument is 0, but that is undefined behavior.
1217 If there is a ctz optab for this mode and
1218 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1219 otherwise just assume 0 won't be seen. */
1221 arg
= gimple_call_arg (stmt
, 0);
1222 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1225 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1226 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1227 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
))
1229 /* Handle only the two common values. */
1232 else if (zerov
== prec
)
1235 /* Magic value to give up, unless vr0 proves
1239 if (TREE_CODE (arg
) == SSA_NAME
)
1241 const value_range_equiv
*vr0
= get_value_range (arg
);
1242 /* If arg is non-zero, then use [0, prec - 1]. */
1243 if ((vr0
->kind () == VR_RANGE
1244 && integer_nonzerop (vr0
->min ()))
1245 || (vr0
->kind () == VR_ANTI_RANGE
1246 && integer_zerop (vr0
->min ())))
1251 /* If some high bits are known to be zero,
1252 we can decrease the result maximum. */
1253 if (vr0
->kind () == VR_RANGE
1254 && TREE_CODE (vr0
->max ()) == INTEGER_CST
)
1256 maxi
= tree_floor_log2 (vr0
->max ());
1257 /* For vr0 [0, 0] give up. */
1265 /* __builtin_clrsb* returns [0, prec-1]. */
1267 arg
= gimple_call_arg (stmt
, 0);
1268 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1273 vr
->set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
1275 case CFN_UBSAN_CHECK_ADD
:
1276 subcode
= PLUS_EXPR
;
1278 case CFN_UBSAN_CHECK_SUB
:
1279 subcode
= MINUS_EXPR
;
1281 case CFN_UBSAN_CHECK_MUL
:
1282 subcode
= MULT_EXPR
;
1284 case CFN_GOACC_DIM_SIZE
:
1285 case CFN_GOACC_DIM_POS
:
1286 /* Optimizing these two internal functions helps the loop
1287 optimizer eliminate outer comparisons. Size is [1,N]
1288 and pos is [0,N-1]. */
1290 bool is_pos
= cfn
== CFN_GOACC_DIM_POS
;
1291 int axis
= oacc_get_ifn_dim_arg (stmt
);
1292 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1295 /* If it's dynamic, the backend might know a hardware
1297 size
= targetm
.goacc
.dim_limit (axis
);
1299 tree type
= TREE_TYPE (gimple_call_lhs (stmt
));
1300 vr
->set(build_int_cst (type
, is_pos
? 0 : 1),
1302 ? build_int_cst (type
, size
- is_pos
) : vrp_val_max (type
));
1305 case CFN_BUILT_IN_STRLEN
:
1306 if (tree lhs
= gimple_call_lhs (stmt
))
1307 if (ptrdiff_type_node
1308 && (TYPE_PRECISION (ptrdiff_type_node
)
1309 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1311 tree type
= TREE_TYPE (lhs
);
1312 tree max
= vrp_val_max (ptrdiff_type_node
);
1313 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1314 tree range_min
= build_zero_cst (type
);
1315 /* To account for the terminating NUL, the maximum length
1316 is one less than the maximum array size, which in turn
1317 is one less than PTRDIFF_MAX (or SIZE_MAX where it's
1318 smaller than the former type).
1319 FIXME: Use max_object_size() - 1 here. */
1320 tree range_max
= wide_int_to_tree (type
, wmax
- 2);
1321 vr
->set (range_min
, range_max
);
1328 if (subcode
!= ERROR_MARK
)
1330 bool saved_flag_wrapv
= flag_wrapv
;
1331 /* Pretend the arithmetics is wrapping. If there is
1332 any overflow, we'll complain, but will actually do
1333 wrapping operation. */
1335 extract_range_from_binary_expr (vr
, subcode
, type
,
1336 gimple_call_arg (stmt
, 0),
1337 gimple_call_arg (stmt
, 1));
1338 flag_wrapv
= saved_flag_wrapv
;
1340 /* If for both arguments vrp_valueize returned non-NULL,
1341 this should have been already folded and if not, it
1342 wasn't folded because of overflow. Avoid removing the
1343 UBSAN_CHECK_* calls in that case. */
1344 if (vr
->kind () == VR_RANGE
1345 && (vr
->min () == vr
->max ()
1346 || operand_equal_p (vr
->min (), vr
->max (), 0)))
1347 vr
->set_varying (vr
->type ());
1351 /* Handle extraction of the two results (result of arithmetics and
1352 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1353 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1354 else if (is_gimple_assign (stmt
)
1355 && (gimple_assign_rhs_code (stmt
) == REALPART_EXPR
1356 || gimple_assign_rhs_code (stmt
) == IMAGPART_EXPR
)
1357 && INTEGRAL_TYPE_P (type
))
1359 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1360 tree op
= gimple_assign_rhs1 (stmt
);
1361 if (TREE_CODE (op
) == code
&& TREE_CODE (TREE_OPERAND (op
, 0)) == SSA_NAME
)
1363 gimple
*g
= SSA_NAME_DEF_STMT (TREE_OPERAND (op
, 0));
1364 if (is_gimple_call (g
) && gimple_call_internal_p (g
))
1366 enum tree_code subcode
= ERROR_MARK
;
1367 switch (gimple_call_internal_fn (g
))
1369 case IFN_ADD_OVERFLOW
:
1370 subcode
= PLUS_EXPR
;
1372 case IFN_SUB_OVERFLOW
:
1373 subcode
= MINUS_EXPR
;
1375 case IFN_MUL_OVERFLOW
:
1376 subcode
= MULT_EXPR
;
1378 case IFN_ATOMIC_COMPARE_EXCHANGE
:
1379 if (code
== IMAGPART_EXPR
)
1381 /* This is the boolean return value whether compare and
1382 exchange changed anything or not. */
1383 vr
->set (build_int_cst (type
, 0),
1384 build_int_cst (type
, 1));
1391 if (subcode
!= ERROR_MARK
)
1393 tree op0
= gimple_call_arg (g
, 0);
1394 tree op1
= gimple_call_arg (g
, 1);
1395 if (code
== IMAGPART_EXPR
)
1398 if (check_for_binary_op_overflow (this, subcode
, type
,
1400 vr
->set (build_int_cst (type
, ovf
));
1401 else if (TYPE_PRECISION (type
) == 1
1402 && !TYPE_UNSIGNED (type
))
1403 vr
->set_varying (type
);
1405 vr
->set (build_int_cst (type
, 0),
1406 build_int_cst (type
, 1));
1408 else if (types_compatible_p (type
, TREE_TYPE (op0
))
1409 && types_compatible_p (type
, TREE_TYPE (op1
)))
1411 bool saved_flag_wrapv
= flag_wrapv
;
1412 /* Pretend the arithmetics is wrapping. If there is
1413 any overflow, IMAGPART_EXPR will be set. */
1415 extract_range_from_binary_expr (vr
, subcode
, type
,
1417 flag_wrapv
= saved_flag_wrapv
;
1421 value_range_equiv vr0
, vr1
;
1422 bool saved_flag_wrapv
= flag_wrapv
;
1423 /* Pretend the arithmetics is wrapping. If there is
1424 any overflow, IMAGPART_EXPR will be set. */
1426 extract_range_from_unary_expr (&vr0
, NOP_EXPR
,
1428 extract_range_from_unary_expr (&vr1
, NOP_EXPR
,
1430 range_fold_binary_expr (vr
, subcode
, type
, &vr0
, &vr1
);
1431 flag_wrapv
= saved_flag_wrapv
;
1438 if (INTEGRAL_TYPE_P (type
)
1439 && gimple_stmt_nonnegative_warnv_p (stmt
, &sop
))
1440 set_value_range_to_nonnegative (vr
, type
);
1441 else if (vrp_stmt_computes_nonzero (stmt
))
1443 vr
->set_nonzero (type
);
1447 vr
->set_varying (type
);
1451 /* Try to compute a useful range out of assignment STMT and store it
1455 vr_values::extract_range_from_assignment (value_range_equiv
*vr
, gassign
*stmt
)
1457 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1459 if (code
== ASSERT_EXPR
)
1460 extract_range_from_assert (vr
, gimple_assign_rhs1 (stmt
));
1461 else if (code
== SSA_NAME
)
1462 extract_range_from_ssa_name (vr
, gimple_assign_rhs1 (stmt
));
1463 else if (TREE_CODE_CLASS (code
) == tcc_binary
)
1464 extract_range_from_binary_expr (vr
, gimple_assign_rhs_code (stmt
),
1465 gimple_expr_type (stmt
),
1466 gimple_assign_rhs1 (stmt
),
1467 gimple_assign_rhs2 (stmt
));
1468 else if (TREE_CODE_CLASS (code
) == tcc_unary
)
1469 extract_range_from_unary_expr (vr
, gimple_assign_rhs_code (stmt
),
1470 gimple_expr_type (stmt
),
1471 gimple_assign_rhs1 (stmt
));
1472 else if (code
== COND_EXPR
)
1473 extract_range_from_cond_expr (vr
, stmt
);
1474 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1475 extract_range_from_comparison (vr
, gimple_assign_rhs_code (stmt
),
1476 gimple_expr_type (stmt
),
1477 gimple_assign_rhs1 (stmt
),
1478 gimple_assign_rhs2 (stmt
));
1479 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1480 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1481 vr
->set (gimple_assign_rhs1 (stmt
));
1483 vr
->set_varying (TREE_TYPE (gimple_assign_lhs (stmt
)));
1485 if (vr
->varying_p ())
1486 extract_range_basic (vr
, stmt
);
1489 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1491 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1492 all the values in the ranges.
1494 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1496 - Return NULL_TREE if it is not always possible to determine the
1497 value of the comparison.
1499 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1500 assumed signed overflow is undefined. */
1504 compare_ranges (enum tree_code comp
, const value_range_equiv
*vr0
,
1505 const value_range_equiv
*vr1
, bool *strict_overflow_p
)
1507 /* VARYING or UNDEFINED ranges cannot be compared. */
1508 if (vr0
->varying_p ()
1509 || vr0
->undefined_p ()
1510 || vr1
->varying_p ()
1511 || vr1
->undefined_p ())
1514 /* Anti-ranges need to be handled separately. */
1515 if (vr0
->kind () == VR_ANTI_RANGE
|| vr1
->kind () == VR_ANTI_RANGE
)
1517 /* If both are anti-ranges, then we cannot compute any
1519 if (vr0
->kind () == VR_ANTI_RANGE
&& vr1
->kind () == VR_ANTI_RANGE
)
1522 /* These comparisons are never statically computable. */
1529 /* Equality can be computed only between a range and an
1530 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1531 if (vr0
->kind () == VR_RANGE
)
1532 /* To simplify processing, make VR0 the anti-range. */
1533 std::swap (vr0
, vr1
);
1535 gcc_assert (comp
== NE_EXPR
|| comp
== EQ_EXPR
);
1537 if (compare_values_warnv (vr0
->min (), vr1
->min (), strict_overflow_p
) == 0
1538 && compare_values_warnv (vr0
->max (), vr1
->max (), strict_overflow_p
) == 0)
1539 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1544 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1545 operands around and change the comparison code. */
1546 if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1548 comp
= (comp
== GT_EXPR
) ? LT_EXPR
: LE_EXPR
;
1549 std::swap (vr0
, vr1
);
1552 if (comp
== EQ_EXPR
)
1554 /* Equality may only be computed if both ranges represent
1555 exactly one value. */
1556 if (compare_values_warnv (vr0
->min (), vr0
->max (), strict_overflow_p
) == 0
1557 && compare_values_warnv (vr1
->min (), vr1
->max (), strict_overflow_p
) == 0)
1559 int cmp_min
= compare_values_warnv (vr0
->min (), vr1
->min (),
1561 int cmp_max
= compare_values_warnv (vr0
->max (), vr1
->max (),
1563 if (cmp_min
== 0 && cmp_max
== 0)
1564 return boolean_true_node
;
1565 else if (cmp_min
!= -2 && cmp_max
!= -2)
1566 return boolean_false_node
;
1568 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1569 else if (compare_values_warnv (vr0
->min (), vr1
->max (),
1570 strict_overflow_p
) == 1
1571 || compare_values_warnv (vr1
->min (), vr0
->max (),
1572 strict_overflow_p
) == 1)
1573 return boolean_false_node
;
1577 else if (comp
== NE_EXPR
)
1581 /* If VR0 is completely to the left or completely to the right
1582 of VR1, they are always different. Notice that we need to
1583 make sure that both comparisons yield similar results to
1584 avoid comparing values that cannot be compared at
1586 cmp1
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1587 cmp2
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1588 if ((cmp1
== -1 && cmp2
== -1) || (cmp1
== 1 && cmp2
== 1))
1589 return boolean_true_node
;
1591 /* If VR0 and VR1 represent a single value and are identical,
1593 else if (compare_values_warnv (vr0
->min (), vr0
->max (),
1594 strict_overflow_p
) == 0
1595 && compare_values_warnv (vr1
->min (), vr1
->max (),
1596 strict_overflow_p
) == 0
1597 && compare_values_warnv (vr0
->min (), vr1
->min (),
1598 strict_overflow_p
) == 0
1599 && compare_values_warnv (vr0
->max (), vr1
->max (),
1600 strict_overflow_p
) == 0)
1601 return boolean_false_node
;
1603 /* Otherwise, they may or may not be different. */
1607 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1611 /* If VR0 is to the left of VR1, return true. */
1612 tst
= compare_values_warnv (vr0
->max (), vr1
->min (), strict_overflow_p
);
1613 if ((comp
== LT_EXPR
&& tst
== -1)
1614 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1615 return boolean_true_node
;
1617 /* If VR0 is to the right of VR1, return false. */
1618 tst
= compare_values_warnv (vr0
->min (), vr1
->max (), strict_overflow_p
);
1619 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1620 || (comp
== LE_EXPR
&& tst
== 1))
1621 return boolean_false_node
;
1623 /* Otherwise, we don't know. */
1630 /* Given a value range VR, a value VAL and a comparison code COMP, return
1631 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1632 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1633 always returns false. Return NULL_TREE if it is not always
1634 possible to determine the value of the comparison. Also set
1635 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1636 assumed signed overflow is undefined. */
1639 compare_range_with_value (enum tree_code comp
, const value_range
*vr
,
1640 tree val
, bool *strict_overflow_p
)
1642 if (vr
->varying_p () || vr
->undefined_p ())
1645 /* Anti-ranges need to be handled separately. */
1646 if (vr
->kind () == VR_ANTI_RANGE
)
1648 /* For anti-ranges, the only predicates that we can compute at
1649 compile time are equality and inequality. */
1656 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1657 if (!vr
->may_contain_p (val
))
1658 return (comp
== NE_EXPR
) ? boolean_true_node
: boolean_false_node
;
1663 if (comp
== EQ_EXPR
)
1665 /* EQ_EXPR may only be computed if VR represents exactly
1667 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0)
1669 int cmp
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1671 return boolean_true_node
;
1672 else if (cmp
== -1 || cmp
== 1 || cmp
== 2)
1673 return boolean_false_node
;
1675 else if (compare_values_warnv (val
, vr
->min (), strict_overflow_p
) == -1
1676 || compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1)
1677 return boolean_false_node
;
1681 else if (comp
== NE_EXPR
)
1683 /* If VAL is not inside VR, then they are always different. */
1684 if (compare_values_warnv (vr
->max (), val
, strict_overflow_p
) == -1
1685 || compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 1)
1686 return boolean_true_node
;
1688 /* If VR represents exactly one value equal to VAL, then return
1690 if (compare_values_warnv (vr
->min (), vr
->max (), strict_overflow_p
) == 0
1691 && compare_values_warnv (vr
->min (), val
, strict_overflow_p
) == 0)
1692 return boolean_false_node
;
1694 /* Otherwise, they may or may not be different. */
1697 else if (comp
== LT_EXPR
|| comp
== LE_EXPR
)
1701 /* If VR is to the left of VAL, return true. */
1702 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1703 if ((comp
== LT_EXPR
&& tst
== -1)
1704 || (comp
== LE_EXPR
&& (tst
== -1 || tst
== 0)))
1705 return boolean_true_node
;
1707 /* If VR is to the right of VAL, return false. */
1708 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1709 if ((comp
== LT_EXPR
&& (tst
== 0 || tst
== 1))
1710 || (comp
== LE_EXPR
&& tst
== 1))
1711 return boolean_false_node
;
1713 /* Otherwise, we don't know. */
1716 else if (comp
== GT_EXPR
|| comp
== GE_EXPR
)
1720 /* If VR is to the right of VAL, return true. */
1721 tst
= compare_values_warnv (vr
->min (), val
, strict_overflow_p
);
1722 if ((comp
== GT_EXPR
&& tst
== 1)
1723 || (comp
== GE_EXPR
&& (tst
== 0 || tst
== 1)))
1724 return boolean_true_node
;
1726 /* If VR is to the left of VAL, return false. */
1727 tst
= compare_values_warnv (vr
->max (), val
, strict_overflow_p
);
1728 if ((comp
== GT_EXPR
&& (tst
== -1 || tst
== 0))
1729 || (comp
== GE_EXPR
&& tst
== -1))
1730 return boolean_false_node
;
1732 /* Otherwise, we don't know. */
1738 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1739 would be profitable to adjust VR using scalar evolution information
1740 for VAR. If so, update VR with the new limits. */
1743 vr_values::adjust_range_with_scev (value_range_equiv
*vr
, class loop
*loop
,
1744 gimple
*stmt
, tree var
)
1746 tree init
, step
, chrec
, tmin
, tmax
, min
, max
, type
, tem
;
1747 enum ev_direction dir
;
1749 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1750 better opportunities than a regular range, but I'm not sure. */
1751 if (vr
->kind () == VR_ANTI_RANGE
)
1754 chrec
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, var
));
1756 /* Like in PR19590, scev can return a constant function. */
1757 if (is_gimple_min_invariant (chrec
))
1763 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1766 init
= initial_condition_in_loop_num (chrec
, loop
->num
);
1767 tem
= op_with_constant_singleton_value_range (init
);
1770 step
= evolution_part_in_loop_num (chrec
, loop
->num
);
1771 tem
= op_with_constant_singleton_value_range (step
);
1775 /* If STEP is symbolic, we can't know whether INIT will be the
1776 minimum or maximum value in the range. Also, unless INIT is
1777 a simple expression, compare_values and possibly other functions
1778 in tree-vrp won't be able to handle it. */
1779 if (step
== NULL_TREE
1780 || !is_gimple_min_invariant (step
)
1781 || !valid_value_p (init
))
1784 dir
= scev_direction (chrec
);
1785 if (/* Do not adjust ranges if we do not know whether the iv increases
1786 or decreases, ... */
1787 dir
== EV_DIR_UNKNOWN
1788 /* ... or if it may wrap. */
1789 || scev_probably_wraps_p (NULL_TREE
, init
, step
, stmt
,
1790 get_chrec_loop (chrec
), true))
1793 type
= TREE_TYPE (var
);
1794 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1795 tmin
= lower_bound_in_type (type
, type
);
1797 tmin
= TYPE_MIN_VALUE (type
);
1798 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1799 tmax
= upper_bound_in_type (type
, type
);
1801 tmax
= TYPE_MAX_VALUE (type
);
1803 /* Try to use estimated number of iterations for the loop to constrain the
1804 final value in the evolution. */
1805 if (TREE_CODE (step
) == INTEGER_CST
1806 && is_gimple_val (init
)
1807 && (TREE_CODE (init
) != SSA_NAME
1808 || get_value_range (init
)->kind () == VR_RANGE
))
1812 /* We are only entering here for loop header PHI nodes, so using
1813 the number of latch executions is the correct thing to use. */
1814 if (max_loop_iterations (loop
, &nit
))
1816 signop sgn
= TYPE_SIGN (TREE_TYPE (step
));
1817 wi::overflow_type overflow
;
1819 widest_int wtmp
= wi::mul (wi::to_widest (step
), nit
, sgn
,
1821 /* If the multiplication overflowed we can't do a meaningful
1822 adjustment. Likewise if the result doesn't fit in the type
1823 of the induction variable. For a signed type we have to
1824 check whether the result has the expected signedness which
1825 is that of the step as number of iterations is unsigned. */
1827 && wi::fits_to_tree_p (wtmp
, TREE_TYPE (init
))
1829 || wi::gts_p (wtmp
, 0) == wi::gts_p (wi::to_wide (step
), 0)))
1831 value_range_equiv maxvr
;
1832 tem
= wide_int_to_tree (TREE_TYPE (init
), wtmp
);
1833 extract_range_from_binary_expr (&maxvr
, PLUS_EXPR
,
1834 TREE_TYPE (init
), init
, tem
);
1835 /* Likewise if the addition did. */
1836 if (maxvr
.kind () == VR_RANGE
)
1840 if (TREE_CODE (init
) == SSA_NAME
)
1841 initvr
= *(get_value_range (init
));
1842 else if (is_gimple_min_invariant (init
))
1847 /* Check if init + nit * step overflows. Though we checked
1848 scev {init, step}_loop doesn't wrap, it is not enough
1849 because the loop may exit immediately. Overflow could
1850 happen in the plus expression in this case. */
1851 if ((dir
== EV_DIR_DECREASES
1852 && compare_values (maxvr
.min (), initvr
.min ()) != -1)
1853 || (dir
== EV_DIR_GROWS
1854 && compare_values (maxvr
.max (), initvr
.max ()) != 1))
1857 tmin
= maxvr
.min ();
1858 tmax
= maxvr
.max ();
1864 if (vr
->varying_p () || vr
->undefined_p ())
1869 /* For VARYING or UNDEFINED ranges, just about anything we get
1870 from scalar evolutions should be better. */
1872 if (dir
== EV_DIR_DECREASES
)
1877 else if (vr
->kind () == VR_RANGE
)
1882 if (dir
== EV_DIR_DECREASES
)
1884 /* INIT is the maximum value. If INIT is lower than VR->MAX ()
1885 but no smaller than VR->MIN (), set VR->MAX () to INIT. */
1886 if (compare_values (init
, max
) == -1)
1889 /* According to the loop information, the variable does not
1891 if (compare_values (min
, tmin
) == -1)
1897 /* If INIT is bigger than VR->MIN (), set VR->MIN () to INIT. */
1898 if (compare_values (init
, min
) == 1)
1901 if (compare_values (tmax
, max
) == -1)
1908 /* If we just created an invalid range with the minimum
1909 greater than the maximum, we fail conservatively.
1910 This should happen only in unreachable
1911 parts of code, or for invalid programs. */
1912 if (compare_values (min
, max
) == 1)
1915 /* Even for valid range info, sometimes overflow flag will leak in.
1916 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1918 if (TREE_OVERFLOW_P (min
))
1919 min
= drop_tree_overflow (min
);
1920 if (TREE_OVERFLOW_P (max
))
1921 max
= drop_tree_overflow (max
);
1923 vr
->update (min
, max
);
1926 /* Dump value ranges of all SSA_NAMEs to FILE. */
1929 vr_values::dump_all_value_ranges (FILE *file
)
1933 for (i
= 0; i
< num_vr_values
; i
++)
1937 print_generic_expr (file
, ssa_name (i
));
1938 fprintf (file
, ": ");
1939 dump_value_range (file
, vr_value
[i
]);
1940 fprintf (file
, "\n");
1944 fprintf (file
, "\n");
1947 /* Initialize VRP lattice. */
1949 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges"),
1952 values_propagated
= false;
1953 num_vr_values
= num_ssa_names
* 2;
1954 vr_value
= XCNEWVEC (value_range_equiv
*, num_vr_values
);
1955 vr_phi_edge_counts
= XCNEWVEC (int, num_ssa_names
);
1956 bitmap_obstack_initialize (&vrp_equiv_obstack
);
1959 /* Free VRP lattice. */
1961 vr_values::~vr_values ()
1963 /* Free allocated memory. */
1965 free (vr_phi_edge_counts
);
1966 bitmap_obstack_release (&vrp_equiv_obstack
);
1967 vrp_value_range_pool
.release ();
1969 /* So that we can distinguish between VRP data being available
1970 and not available. */
1972 vr_phi_edge_counts
= NULL
;
1977 static class vr_values
*x_vr_values
;
1979 /* Return the singleton value-range for NAME or NAME. */
1982 vrp_valueize (tree name
)
1984 if (TREE_CODE (name
) == SSA_NAME
)
1986 const value_range_equiv
*vr
= x_vr_values
->get_value_range (name
);
1987 if (vr
->kind () == VR_RANGE
1988 && (TREE_CODE (vr
->min ()) == SSA_NAME
1989 || is_gimple_min_invariant (vr
->min ()))
1990 && vrp_operand_equal_p (vr
->min (), vr
->max ()))
1996 /* Return the singleton value-range for NAME if that is a constant
1997 but signal to not follow SSA edges. */
2000 vrp_valueize_1 (tree name
)
2002 if (TREE_CODE (name
) == SSA_NAME
)
2004 /* If the definition may be simulated again we cannot follow
2005 this SSA edge as the SSA propagator does not necessarily
2006 re-visit the use. */
2007 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
2008 if (!gimple_nop_p (def_stmt
)
2009 && prop_simulate_again_p (def_stmt
))
2011 const value_range_equiv
*vr
= x_vr_values
->get_value_range (name
);
2013 if (vr
->singleton_p (&singleton
))
2019 /* Given STMT, an assignment or call, return its LHS if the type
2020 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
2023 get_output_for_vrp (gimple
*stmt
)
2025 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2028 /* We only keep track of ranges in integral and pointer types. */
2029 tree lhs
= gimple_get_lhs (stmt
);
2030 if (TREE_CODE (lhs
) == SSA_NAME
2031 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2032 /* It is valid to have NULL MIN/MAX values on a type. See
2033 build_range_type. */
2034 && TYPE_MIN_VALUE (TREE_TYPE (lhs
))
2035 && TYPE_MAX_VALUE (TREE_TYPE (lhs
)))
2036 || POINTER_TYPE_P (TREE_TYPE (lhs
))))
2042 /* Visit assignment STMT. If it produces an interesting range, record
2043 the range in VR and set LHS to OUTPUT_P. */
2046 vr_values::vrp_visit_assignment_or_call (gimple
*stmt
, tree
*output_p
,
2047 value_range_equiv
*vr
)
2049 tree lhs
= get_output_for_vrp (stmt
);
2052 /* We only keep track of ranges in integral and pointer types. */
2055 enum gimple_code code
= gimple_code (stmt
);
2057 /* Try folding the statement to a constant first. */
2059 tree tem
= gimple_fold_stmt_to_constant_1 (stmt
, vrp_valueize
,
2064 if (TREE_CODE (tem
) == SSA_NAME
2065 && (SSA_NAME_IS_DEFAULT_DEF (tem
)
2066 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem
))))
2068 extract_range_from_ssa_name (vr
, tem
);
2071 else if (is_gimple_min_invariant (tem
))
2077 /* Then dispatch to value-range extracting functions. */
2078 if (code
== GIMPLE_CALL
)
2079 extract_range_basic (vr
, stmt
);
2081 extract_range_from_assignment (vr
, as_a
<gassign
*> (stmt
));
2085 /* Helper that gets the value range of the SSA_NAME with version I
2086 or a symbolic range containing the SSA_NAME only if the value range
2087 is varying or undefined. Uses TEM as storage for the alternate range. */
2089 const value_range_equiv
*
2090 simplify_using_ranges::get_vr_for_comparison (int i
, value_range_equiv
*tem
)
2092 /* Shallow-copy equiv bitmap. */
2093 const value_range_equiv
*vr
= get_value_range (ssa_name (i
));
2095 /* If name N_i does not have a valid range, use N_i as its own
2096 range. This allows us to compare against names that may
2097 have N_i in their ranges. */
2098 if (vr
->varying_p () || vr
->undefined_p ())
2100 tem
->set (ssa_name (i
));
2107 /* Compare all the value ranges for names equivalent to VAR with VAL
2108 using comparison code COMP. Return the same value returned by
2109 compare_range_with_value, including the setting of
2110 *STRICT_OVERFLOW_P. */
2113 simplify_using_ranges::compare_name_with_value
2114 (enum tree_code comp
, tree var
, tree val
,
2115 bool *strict_overflow_p
, bool use_equiv_p
)
2117 /* Get the set of equivalences for VAR. */
2118 bitmap e
= get_value_range (var
)->equiv ();
2120 /* Start at -1. Set it to 0 if we do a comparison without relying
2121 on overflow, or 1 if all comparisons rely on overflow. */
2122 int used_strict_overflow
= -1;
2124 /* Compare vars' value range with val. */
2125 value_range_equiv tem_vr
;
2126 const value_range_equiv
*equiv_vr
2127 = get_vr_for_comparison (SSA_NAME_VERSION (var
), &tem_vr
);
2129 tree retval
= compare_range_with_value (comp
, equiv_vr
, val
, &sop
);
2131 used_strict_overflow
= sop
? 1 : 0;
2133 /* If the equiv set is empty we have done all work we need to do. */
2136 if (retval
&& used_strict_overflow
> 0)
2137 *strict_overflow_p
= true;
2143 EXECUTE_IF_SET_IN_BITMAP (e
, 0, i
, bi
)
2145 tree name
= ssa_name (i
);
2150 && !SSA_NAME_IS_DEFAULT_DEF (name
)
2151 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name
)))
2154 equiv_vr
= get_vr_for_comparison (i
, &tem_vr
);
2156 tree t
= compare_range_with_value (comp
, equiv_vr
, val
, &sop
);
2159 /* If we get different answers from different members
2160 of the equivalence set this check must be in a dead
2161 code region. Folding it to a trap representation
2162 would be correct here. For now just return don't-know. */
2172 used_strict_overflow
= 0;
2173 else if (used_strict_overflow
< 0)
2174 used_strict_overflow
= 1;
2178 if (retval
&& used_strict_overflow
> 0)
2179 *strict_overflow_p
= true;
2185 /* Given a comparison code COMP and names N1 and N2, compare all the
2186 ranges equivalent to N1 against all the ranges equivalent to N2
2187 to determine the value of N1 COMP N2. Return the same value
2188 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2189 whether we relied on undefined signed overflow in the comparison. */
2193 simplify_using_ranges::compare_names (enum tree_code comp
, tree n1
, tree n2
,
2194 bool *strict_overflow_p
)
2196 /* Compare the ranges of every name equivalent to N1 against the
2197 ranges of every name equivalent to N2. */
2198 bitmap e1
= get_value_range (n1
)->equiv ();
2199 bitmap e2
= get_value_range (n2
)->equiv ();
2201 /* Use the fake bitmaps if e1 or e2 are not available. */
2202 static bitmap s_e1
= NULL
, s_e2
= NULL
;
2203 static bitmap_obstack
*s_obstack
= NULL
;
2204 if (s_obstack
== NULL
)
2206 s_obstack
= XNEW (bitmap_obstack
);
2207 bitmap_obstack_initialize (s_obstack
);
2208 s_e1
= BITMAP_ALLOC (s_obstack
);
2209 s_e2
= BITMAP_ALLOC (s_obstack
);
2216 /* Add N1 and N2 to their own set of equivalences to avoid
2217 duplicating the body of the loop just to check N1 and N2
2219 bitmap_set_bit (e1
, SSA_NAME_VERSION (n1
));
2220 bitmap_set_bit (e2
, SSA_NAME_VERSION (n2
));
2222 /* If the equivalence sets have a common intersection, then the two
2223 names can be compared without checking their ranges. */
2224 if (bitmap_intersect_p (e1
, e2
))
2226 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2227 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2229 return (comp
== EQ_EXPR
|| comp
== GE_EXPR
|| comp
== LE_EXPR
)
2231 : boolean_false_node
;
2234 /* Start at -1. Set it to 0 if we do a comparison without relying
2235 on overflow, or 1 if all comparisons rely on overflow. */
2236 int used_strict_overflow
= -1;
2238 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2239 N2 to their own set of equivalences to avoid duplicating the body
2240 of the loop just to check N1 and N2 ranges. */
2241 bitmap_iterator bi1
;
2243 EXECUTE_IF_SET_IN_BITMAP (e1
, 0, i1
, bi1
)
2248 value_range_equiv tem_vr1
;
2249 const value_range_equiv
*vr1
= get_vr_for_comparison (i1
, &tem_vr1
);
2251 tree t
= NULL_TREE
, retval
= NULL_TREE
;
2252 bitmap_iterator bi2
;
2254 EXECUTE_IF_SET_IN_BITMAP (e2
, 0, i2
, bi2
)
2261 value_range_equiv tem_vr2
;
2262 const value_range_equiv
*vr2
= get_vr_for_comparison (i2
, &tem_vr2
);
2264 t
= compare_ranges (comp
, vr1
, vr2
, &sop
);
2267 /* If we get different answers from different members
2268 of the equivalence set this check must be in a dead
2269 code region. Folding it to a trap representation
2270 would be correct here. For now just return don't-know. */
2271 if (retval
!= NULL
&& t
!= retval
)
2273 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2274 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2280 used_strict_overflow
= 0;
2281 else if (used_strict_overflow
< 0)
2282 used_strict_overflow
= 1;
2288 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2289 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2290 if (used_strict_overflow
> 0)
2291 *strict_overflow_p
= true;
2296 /* None of the equivalent ranges are useful in computing this
2298 bitmap_clear_bit (e1
, SSA_NAME_VERSION (n1
));
2299 bitmap_clear_bit (e2
, SSA_NAME_VERSION (n2
));
2303 /* Helper function for vrp_evaluate_conditional_warnv & other
2307 simplify_using_ranges::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2308 (enum tree_code code
, tree op0
, tree op1
, bool * strict_overflow_p
)
2310 const value_range_equiv
*vr0
, *vr1
;
2311 vr0
= (TREE_CODE (op0
) == SSA_NAME
) ? get_value_range (op0
) : NULL
;
2312 vr1
= (TREE_CODE (op1
) == SSA_NAME
) ? get_value_range (op1
) : NULL
;
2314 tree res
= NULL_TREE
;
2316 res
= compare_ranges (code
, vr0
, vr1
, strict_overflow_p
);
2318 res
= compare_range_with_value (code
, vr0
, op1
, strict_overflow_p
);
2320 res
= (compare_range_with_value
2321 (swap_tree_comparison (code
), vr1
, op0
, strict_overflow_p
));
2325 /* Helper function for vrp_evaluate_conditional_warnv. */
2328 simplify_using_ranges::vrp_evaluate_conditional_warnv_with_ops
2329 (enum tree_code code
,
2332 bool *strict_overflow_p
,
2337 *only_ranges
= true;
2339 /* We only deal with integral and pointer types. */
2340 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
2341 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
2344 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2345 as a simple equality test, then prefer that over its current form
2348 An overflow test which collapses to an equality test can always be
2349 expressed as a comparison of one argument against zero. Overflow
2350 occurs when the chosen argument is zero and does not occur if the
2351 chosen argument is not zero. */
2353 if (overflow_comparison_p (code
, op0
, op1
, use_equiv_p
, &x
))
2355 wide_int max
= wi::max_value (TYPE_PRECISION (TREE_TYPE (op0
)), UNSIGNED
);
2356 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2357 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2358 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2359 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2360 if (integer_zerop (x
))
2363 code
= (code
== LT_EXPR
|| code
== LE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2365 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2366 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2367 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2368 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2369 else if (wi::to_wide (x
) == max
- 1)
2372 op1
= wide_int_to_tree (TREE_TYPE (op0
), 0);
2373 code
= (code
== GT_EXPR
|| code
== GE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
2377 value_range vro
, vri
;
2378 if (code
== GT_EXPR
|| code
== GE_EXPR
)
2380 vro
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
, VR_ANTI_RANGE
);
2381 vri
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2383 else if (code
== LT_EXPR
|| code
== LE_EXPR
)
2385 vro
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
);
2386 vri
.set (TYPE_MIN_VALUE (TREE_TYPE (op0
)), x
, VR_ANTI_RANGE
);
2390 const value_range_equiv
*vr0
= get_value_range (op0
);
2391 /* If vro, the range for OP0 to pass the overflow test, has
2392 no intersection with *vr0, OP0's known range, then the
2393 overflow test can't pass, so return the node for false.
2394 If it is the inverted range, vri, that has no
2395 intersection, then the overflow test must pass, so return
2396 the node for true. In other cases, we could proceed with
2397 a simplified condition comparing OP0 and X, with LE_EXPR
2398 for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
2399 the comments next to the enclosing if suggest it's not
2400 generally profitable to do so. */
2401 vro
.intersect (vr0
);
2402 if (vro
.undefined_p ())
2403 return boolean_false_node
;
2404 vri
.intersect (vr0
);
2405 if (vri
.undefined_p ())
2406 return boolean_true_node
;
2410 if ((ret
= vrp_evaluate_conditional_warnv_with_ops_using_ranges
2411 (code
, op0
, op1
, strict_overflow_p
)))
2414 *only_ranges
= false;
2415 /* Do not use compare_names during propagation, it's quadratic. */
2416 if (TREE_CODE (op0
) == SSA_NAME
&& TREE_CODE (op1
) == SSA_NAME
2418 return compare_names (code
, op0
, op1
, strict_overflow_p
);
2419 else if (TREE_CODE (op0
) == SSA_NAME
)
2420 return compare_name_with_value (code
, op0
, op1
,
2421 strict_overflow_p
, use_equiv_p
);
2422 else if (TREE_CODE (op1
) == SSA_NAME
)
2423 return compare_name_with_value (swap_tree_comparison (code
), op1
, op0
,
2424 strict_overflow_p
, use_equiv_p
);
2428 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2429 information. Return NULL if the conditional cannot be evaluated.
2430 The ranges of all the names equivalent with the operands in COND
2431 will be used when trying to compute the value. If the result is
2432 based on undefined signed overflow, issue a warning if
2436 simplify_using_ranges::vrp_evaluate_conditional (tree_code code
, tree op0
,
2437 tree op1
, gimple
*stmt
)
2443 /* Some passes and foldings leak constants with overflow flag set
2444 into the IL. Avoid doing wrong things with these and bail out. */
2445 if ((TREE_CODE (op0
) == INTEGER_CST
2446 && TREE_OVERFLOW (op0
))
2447 || (TREE_CODE (op1
) == INTEGER_CST
2448 && TREE_OVERFLOW (op1
)))
2452 ret
= vrp_evaluate_conditional_warnv_with_ops (code
, op0
, op1
, true, &sop
,
2457 enum warn_strict_overflow_code wc
;
2458 const char* warnmsg
;
2460 if (is_gimple_min_invariant (ret
))
2462 wc
= WARN_STRICT_OVERFLOW_CONDITIONAL
;
2463 warnmsg
= G_("assuming signed overflow does not occur when "
2464 "simplifying conditional to constant");
2468 wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
2469 warnmsg
= G_("assuming signed overflow does not occur when "
2470 "simplifying conditional");
2473 if (issue_strict_overflow_warning (wc
))
2475 location_t location
;
2477 if (!gimple_has_location (stmt
))
2478 location
= input_location
;
2480 location
= gimple_location (stmt
);
2481 warning_at (location
, OPT_Wstrict_overflow
, "%s", warnmsg
);
2485 if (warn_type_limits
2486 && ret
&& only_ranges
2487 && TREE_CODE_CLASS (code
) == tcc_comparison
2488 && TREE_CODE (op0
) == SSA_NAME
)
2490 /* If the comparison is being folded and the operand on the LHS
2491 is being compared against a constant value that is outside of
2492 the natural range of OP0's type, then the predicate will
2493 always fold regardless of the value of OP0. If -Wtype-limits
2494 was specified, emit a warning. */
2495 tree type
= TREE_TYPE (op0
);
2496 const value_range_equiv
*vr0
= get_value_range (op0
);
2498 if (vr0
->varying_p ()
2499 && INTEGRAL_TYPE_P (type
)
2500 && is_gimple_min_invariant (op1
))
2502 location_t location
;
2504 if (!gimple_has_location (stmt
))
2505 location
= input_location
;
2507 location
= gimple_location (stmt
);
2509 warning_at (location
, OPT_Wtype_limits
,
2511 ? G_("comparison always false "
2512 "due to limited range of data type")
2513 : G_("comparison always true "
2514 "due to limited range of data type"));
2522 /* Visit conditional statement STMT. If we can determine which edge
2523 will be taken out of STMT's basic block, record it in
2524 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2527 simplify_using_ranges::vrp_visit_cond_stmt (gcond
*stmt
, edge
*taken_edge_p
)
2531 *taken_edge_p
= NULL
;
2533 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2538 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
2539 print_gimple_stmt (dump_file
, stmt
, 0);
2540 fprintf (dump_file
, "\nWith known ranges\n");
2542 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
2544 fprintf (dump_file
, "\t");
2545 print_generic_expr (dump_file
, use
);
2546 fprintf (dump_file
, ": ");
2547 dump_value_range (dump_file
, get_value_range (use
));
2550 fprintf (dump_file
, "\n");
2553 /* Compute the value of the predicate COND by checking the known
2554 ranges of each of its operands.
2556 Note that we cannot evaluate all the equivalent ranges here
2557 because those ranges may not yet be final and with the current
2558 propagation strategy, we cannot determine when the value ranges
2559 of the names in the equivalence set have changed.
2561 For instance, given the following code fragment
2565 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2569 Assume that on the first visit to i_14, i_5 has the temporary
2570 range [8, 8] because the second argument to the PHI function is
2571 not yet executable. We derive the range ~[0, 0] for i_14 and the
2572 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2573 the first time, since i_14 is equivalent to the range [8, 8], we
2574 determine that the predicate is always false.
2576 On the next round of propagation, i_13 is determined to be
2577 VARYING, which causes i_5 to drop down to VARYING. So, another
2578 visit to i_14 is scheduled. In this second visit, we compute the
2579 exact same range and equivalence set for i_14, namely ~[0, 0] and
2580 { i_5 }. But we did not have the previous range for i_5
2581 registered, so vrp_visit_assignment thinks that the range for
2582 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2583 is not visited again, which stops propagation from visiting
2584 statements in the THEN clause of that if().
2586 To properly fix this we would need to keep the previous range
2587 value for the names in the equivalence set. This way we would've
2588 discovered that from one visit to the other i_5 changed from
2589 range [8, 8] to VR_VARYING.
2591 However, fixing this apparent limitation may not be worth the
2592 additional checking. Testing on several code bases (GCC, DLV,
2593 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2594 4 more predicates folded in SPEC. */
2597 val
= vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt
),
2598 gimple_cond_lhs (stmt
),
2599 gimple_cond_rhs (stmt
),
2602 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
2604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2606 fprintf (dump_file
, "\nPredicate evaluates to: ");
2607 if (val
== NULL_TREE
)
2608 fprintf (dump_file
, "DON'T KNOW\n");
2610 print_generic_stmt (dump_file
, val
);
2614 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2615 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2616 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2617 Returns true if the default label is not needed. */
2620 find_case_label_ranges (gswitch
*stmt
, const value_range
*vr
,
2621 size_t *min_idx1
, size_t *max_idx1
,
2622 size_t *min_idx2
, size_t *max_idx2
)
2625 unsigned int n
= gimple_switch_num_labels (stmt
);
2627 tree case_low
, case_high
;
2628 tree min
= vr
->min (), max
= vr
->max ();
2630 gcc_checking_assert (!vr
->varying_p () && !vr
->undefined_p ());
2632 take_default
= !find_case_label_range (stmt
, min
, max
, &i
, &j
);
2634 /* Set second range to empty. */
2638 if (vr
->kind () == VR_RANGE
)
2642 return !take_default
;
2645 /* Set first range to all case labels. */
2652 /* Make sure all the values of case labels [i , j] are contained in
2653 range [MIN, MAX]. */
2654 case_low
= CASE_LOW (gimple_switch_label (stmt
, i
));
2655 case_high
= CASE_HIGH (gimple_switch_label (stmt
, j
));
2656 if (tree_int_cst_compare (case_low
, min
) < 0)
2658 if (case_high
!= NULL_TREE
2659 && tree_int_cst_compare (max
, case_high
) < 0)
2665 /* If the range spans case labels [i, j], the corresponding anti-range spans
2666 the labels [1, i - 1] and [j + 1, n - 1]. */
2692 /* Visit switch statement STMT. If we can determine which edge
2693 will be taken out of STMT's basic block, record it in
2694 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2697 vr_values::vrp_visit_switch_stmt (gswitch
*stmt
, edge
*taken_edge_p
)
2700 const value_range_equiv
*vr
;
2701 size_t i
= 0, j
= 0, k
, l
;
2704 *taken_edge_p
= NULL
;
2705 op
= gimple_switch_index (stmt
);
2706 if (TREE_CODE (op
) != SSA_NAME
)
2709 vr
= get_value_range (op
);
2710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2712 fprintf (dump_file
, "\nVisiting switch expression with operand ");
2713 print_generic_expr (dump_file
, op
);
2714 fprintf (dump_file
, " with known range ");
2715 dump_value_range (dump_file
, vr
);
2716 fprintf (dump_file
, "\n");
2719 if (vr
->undefined_p ()
2721 || vr
->symbolic_p ())
2724 /* Find the single edge that is taken from the switch expression. */
2725 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
2727 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2731 gcc_assert (take_default
);
2732 val
= gimple_switch_default_label (stmt
);
2736 /* Check if labels with index i to j and maybe the default label
2737 are all reaching the same label. */
2739 val
= gimple_switch_label (stmt
, i
);
2741 && CASE_LABEL (gimple_switch_default_label (stmt
))
2742 != CASE_LABEL (val
))
2744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2745 fprintf (dump_file
, " not a single destination for this "
2749 for (++i
; i
<= j
; ++i
)
2751 if (CASE_LABEL (gimple_switch_label (stmt
, i
)) != CASE_LABEL (val
))
2753 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2754 fprintf (dump_file
, " not a single destination for this "
2761 if (CASE_LABEL (gimple_switch_label (stmt
, k
)) != CASE_LABEL (val
))
2763 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2764 fprintf (dump_file
, " not a single destination for this "
2771 *taken_edge_p
= find_edge (gimple_bb (stmt
),
2772 label_to_block (cfun
, CASE_LABEL (val
)));
2774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2776 fprintf (dump_file
, " will take edge to ");
2777 print_generic_stmt (dump_file
, CASE_LABEL (val
));
2782 /* Evaluate statement STMT. If the statement produces a useful range,
2783 set VR and corepsponding OUTPUT_P.
2785 If STMT is a conditional branch and we can determine its truth
2786 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2789 vr_values::extract_range_from_stmt (gimple
*stmt
, edge
*taken_edge_p
,
2790 tree
*output_p
, value_range_equiv
*vr
)
2793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2795 fprintf (dump_file
, "\nextract_range_from_stmt visiting:\n");
2796 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
2799 if (!stmt_interesting_for_vrp (stmt
))
2800 gcc_assert (stmt_ends_bb_p (stmt
));
2801 else if (is_gimple_assign (stmt
) || is_gimple_call (stmt
))
2802 vrp_visit_assignment_or_call (stmt
, output_p
, vr
);
2803 else if (gimple_code (stmt
) == GIMPLE_COND
)
2804 simplifier
.vrp_visit_cond_stmt (as_a
<gcond
*> (stmt
), taken_edge_p
);
2805 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2806 vrp_visit_switch_stmt (as_a
<gswitch
*> (stmt
), taken_edge_p
);
2809 /* Visit all arguments for PHI node PHI that flow through executable
2810 edges. If a valid value range can be derived from all the incoming
2811 value ranges, set a new range in VR_RESULT. */
2814 vr_values::extract_range_from_phi_node (gphi
*phi
,
2815 value_range_equiv
*vr_result
)
2817 tree lhs
= PHI_RESULT (phi
);
2818 const value_range_equiv
*lhs_vr
= get_value_range (lhs
);
2823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2825 fprintf (dump_file
, "\nVisiting PHI node: ");
2826 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
2829 bool may_simulate_backedge_again
= false;
2831 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2833 edge e
= gimple_phi_arg_edge (phi
, i
);
2835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2838 " Argument #%d (%d -> %d %sexecutable)\n",
2839 (int) i
, e
->src
->index
, e
->dest
->index
,
2840 (e
->flags
& EDGE_EXECUTABLE
) ? "" : "not ");
2843 if (e
->flags
& EDGE_EXECUTABLE
)
2845 value_range_equiv vr_arg_tem
;
2846 const value_range_equiv
*vr_arg
= &vr_arg_tem
;
2850 tree arg
= PHI_ARG_DEF (phi
, i
);
2851 if (TREE_CODE (arg
) == SSA_NAME
)
2853 /* See if we are eventually going to change one of the args. */
2854 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
2855 if (! gimple_nop_p (def_stmt
)
2856 && prop_simulate_again_p (def_stmt
)
2857 && e
->flags
& EDGE_DFS_BACK
)
2858 may_simulate_backedge_again
= true;
2860 const value_range_equiv
*vr_arg_
= get_value_range (arg
);
2861 /* Do not allow equivalences or symbolic ranges to leak in from
2862 backedges. That creates invalid equivalencies.
2863 See PR53465 and PR54767. */
2864 if (e
->flags
& EDGE_DFS_BACK
)
2866 if (!vr_arg_
->varying_p () && !vr_arg_
->undefined_p ())
2868 vr_arg_tem
.set (vr_arg_
->min (), vr_arg_
->max (), NULL
,
2870 if (vr_arg_tem
.symbolic_p ())
2871 vr_arg_tem
.set_varying (TREE_TYPE (arg
));
2876 /* If the non-backedge arguments range is VR_VARYING then
2877 we can still try recording a simple equivalence. */
2878 else if (vr_arg_
->varying_p ())
2879 vr_arg_tem
.set (arg
);
2885 if (TREE_OVERFLOW_P (arg
))
2886 arg
= drop_tree_overflow (arg
);
2888 vr_arg_tem
.set (arg
);
2891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2893 fprintf (dump_file
, "\t");
2894 print_generic_expr (dump_file
, arg
, dump_flags
);
2895 fprintf (dump_file
, ": ");
2896 dump_value_range (dump_file
, vr_arg
);
2897 fprintf (dump_file
, "\n");
2901 vr_result
->deep_copy (vr_arg
);
2903 vr_result
->union_ (vr_arg
);
2906 if (vr_result
->varying_p ())
2911 if (vr_result
->varying_p ())
2913 else if (vr_result
->undefined_p ())
2916 old_edges
= vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)];
2917 vr_phi_edge_counts
[SSA_NAME_VERSION (lhs
)] = edges
;
2919 /* To prevent infinite iterations in the algorithm, derive ranges
2920 when the new value is slightly bigger or smaller than the
2921 previous one. We don't do this if we have seen a new executable
2922 edge; this helps us avoid an infinity for conditionals
2923 which are not in a loop. If the old value-range was VR_UNDEFINED
2924 use the updated range and iterate one more time. If we will not
2925 simulate this PHI again via the backedge allow us to iterate. */
2927 && gimple_phi_num_args (phi
) > 1
2928 && edges
== old_edges
2929 && !lhs_vr
->undefined_p ()
2930 && may_simulate_backedge_again
)
2932 /* Compare old and new ranges, fall back to varying if the
2933 values are not comparable. */
2934 int cmp_min
= compare_values (lhs_vr
->min (), vr_result
->min ());
2937 int cmp_max
= compare_values (lhs_vr
->max (), vr_result
->max ());
2941 /* For non VR_RANGE or for pointers fall back to varying if
2942 the range changed. */
2943 if ((lhs_vr
->kind () != VR_RANGE
|| vr_result
->kind () != VR_RANGE
2944 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2945 && (cmp_min
!= 0 || cmp_max
!= 0))
2948 /* If the new minimum is larger than the previous one
2949 retain the old value. If the new minimum value is smaller
2950 than the previous one and not -INF go all the way to -INF + 1.
2951 In the first case, to avoid infinite bouncing between different
2952 minimums, and in the other case to avoid iterating millions of
2953 times to reach -INF. Going to -INF + 1 also lets the following
2954 iteration compute whether there will be any overflow, at the
2955 expense of one additional iteration. */
2956 tree new_min
= vr_result
->min ();
2957 tree new_max
= vr_result
->max ();
2959 new_min
= lhs_vr
->min ();
2960 else if (cmp_min
> 0
2961 && (TREE_CODE (vr_result
->min ()) != INTEGER_CST
2962 || tree_int_cst_lt (vrp_val_min (vr_result
->type ()),
2963 vr_result
->min ())))
2964 new_min
= int_const_binop (PLUS_EXPR
,
2965 vrp_val_min (vr_result
->type ()),
2966 build_int_cst (vr_result
->type (), 1));
2968 /* Similarly for the maximum value. */
2970 new_max
= lhs_vr
->max ();
2971 else if (cmp_max
< 0
2972 && (TREE_CODE (vr_result
->max ()) != INTEGER_CST
2973 || tree_int_cst_lt (vr_result
->max (),
2974 vrp_val_max (vr_result
->type ()))))
2975 new_max
= int_const_binop (MINUS_EXPR
,
2976 vrp_val_max (vr_result
->type ()),
2977 build_int_cst (vr_result
->type (), 1));
2979 vr_result
->update (new_min
, new_max
, vr_result
->kind ());
2981 /* If we dropped either bound to +-INF then if this is a loop
2982 PHI node SCEV may known more about its value-range. */
2983 if (cmp_min
> 0 || cmp_min
< 0
2984 || cmp_max
< 0 || cmp_max
> 0)
2987 goto infinite_check
;
2993 vr_result
->set_varying (TREE_TYPE (lhs
));
2996 /* If this is a loop PHI node SCEV may known more about its value-range.
2997 scev_check can be reached from two paths, one is a fall through from above
2998 "varying" label, the other is direct goto from code block which tries to
2999 avoid infinite simulation. */
3000 if (scev_initialized_p ()
3001 && (l
= loop_containing_stmt (phi
))
3002 && l
->header
== gimple_bb (phi
))
3003 adjust_range_with_scev (vr_result
, l
, phi
, lhs
);
3006 /* If we will end up with a (-INF, +INF) range, set it to
3007 VARYING. Same if the previous max value was invalid for
3008 the type and we end up with vr_result.min > vr_result.max. */
3009 if ((!vr_result
->varying_p () && !vr_result
->undefined_p ())
3010 && !((vrp_val_is_max (vr_result
->max ()) && vrp_val_is_min (vr_result
->min ()))
3011 || compare_values (vr_result
->min (), vr_result
->max ()) > 0))
3014 vr_result
->set_varying (TREE_TYPE (lhs
));
3016 /* If the new range is different than the previous value, keep
3022 /* Simplify boolean operations if the source is known
3023 to be already a boolean. */
3025 simplify_using_ranges::simplify_truth_ops_using_ranges
3026 (gimple_stmt_iterator
*gsi
,
3029 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3031 bool need_conversion
;
3033 /* We handle only !=/== case here. */
3034 gcc_assert (rhs_code
== EQ_EXPR
|| rhs_code
== NE_EXPR
);
3036 op0
= gimple_assign_rhs1 (stmt
);
3037 if (!op_with_boolean_value_range_p (op0
))
3040 op1
= gimple_assign_rhs2 (stmt
);
3041 if (!op_with_boolean_value_range_p (op1
))
3044 /* Reduce number of cases to handle to NE_EXPR. As there is no
3045 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
3046 if (rhs_code
== EQ_EXPR
)
3048 if (TREE_CODE (op1
) == INTEGER_CST
)
3049 op1
= int_const_binop (BIT_XOR_EXPR
, op1
,
3050 build_int_cst (TREE_TYPE (op1
), 1));
3055 lhs
= gimple_assign_lhs (stmt
);
3057 = !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
));
3059 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
3061 && !TYPE_UNSIGNED (TREE_TYPE (op0
))
3062 && TYPE_PRECISION (TREE_TYPE (op0
)) == 1
3063 && TYPE_PRECISION (TREE_TYPE (lhs
)) > 1)
3066 /* For A != 0 we can substitute A itself. */
3067 if (integer_zerop (op1
))
3068 gimple_assign_set_rhs_with_ops (gsi
,
3070 ? NOP_EXPR
: TREE_CODE (op0
), op0
);
3071 /* For A != B we substitute A ^ B. Either with conversion. */
3072 else if (need_conversion
)
3074 tree tem
= make_ssa_name (TREE_TYPE (op0
));
3076 = gimple_build_assign (tem
, BIT_XOR_EXPR
, op0
, op1
);
3077 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
3078 if (INTEGRAL_TYPE_P (TREE_TYPE (tem
))
3079 && TYPE_PRECISION (TREE_TYPE (tem
)) > 1)
3080 set_range_info (tem
, VR_RANGE
,
3081 wi::zero (TYPE_PRECISION (TREE_TYPE (tem
))),
3082 wi::one (TYPE_PRECISION (TREE_TYPE (tem
))));
3083 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, tem
);
3087 gimple_assign_set_rhs_with_ops (gsi
, BIT_XOR_EXPR
, op0
, op1
);
3088 update_stmt (gsi_stmt (*gsi
));
3089 fold_stmt (gsi
, follow_single_use_edges
);
3094 /* Simplify a division or modulo operator to a right shift or bitwise and
3095 if the first operand is unsigned or is greater than zero and the second
3096 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
3097 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
3098 optimize it into just op0 if op0's range is known to be a subset of
3099 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3103 simplify_using_ranges::simplify_div_or_mod_using_ranges
3104 (gimple_stmt_iterator
*gsi
,
3107 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
3109 tree op0
= gimple_assign_rhs1 (stmt
);
3110 tree op1
= gimple_assign_rhs2 (stmt
);
3111 tree op0min
= NULL_TREE
, op0max
= NULL_TREE
;
3113 const value_range
*vr
= NULL
;
3115 if (TREE_CODE (op0
) == INTEGER_CST
)
3122 vr
= get_value_range (op0
);
3123 if (range_int_cst_p (vr
))
3125 op0min
= vr
->min ();
3126 op0max
= vr
->max ();
3130 if (rhs_code
== TRUNC_MOD_EXPR
3131 && TREE_CODE (op1
) == SSA_NAME
)
3133 const value_range_equiv
*vr1
= get_value_range (op1
);
3134 if (range_int_cst_p (vr1
))
3135 op1min
= vr1
->min ();
3137 if (rhs_code
== TRUNC_MOD_EXPR
3138 && TREE_CODE (op1min
) == INTEGER_CST
3139 && tree_int_cst_sgn (op1min
) == 1
3141 && tree_int_cst_lt (op0max
, op1min
))
3143 if (TYPE_UNSIGNED (TREE_TYPE (op0
))
3144 || tree_int_cst_sgn (op0min
) >= 0
3145 || tree_int_cst_lt (fold_unary (NEGATE_EXPR
, TREE_TYPE (op1min
), op1min
),
3148 /* If op0 already has the range op0 % op1 has,
3149 then TRUNC_MOD_EXPR won't change anything. */
3150 gimple_assign_set_rhs_from_tree (gsi
, op0
);
3155 if (TREE_CODE (op0
) != SSA_NAME
)
3158 if (!integer_pow2p (op1
))
3160 /* X % -Y can be only optimized into X % Y either if
3161 X is not INT_MIN, or Y is not -1. Fold it now, as after
3162 remove_range_assertions the range info might be not available
3164 if (rhs_code
== TRUNC_MOD_EXPR
3165 && fold_stmt (gsi
, follow_single_use_edges
))
3170 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
3171 val
= integer_one_node
;
3176 val
= compare_range_with_value (GE_EXPR
, vr
, integer_zero_node
, &sop
);
3180 && integer_onep (val
)
3181 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3183 location_t location
;
3185 if (!gimple_has_location (stmt
))
3186 location
= input_location
;
3188 location
= gimple_location (stmt
);
3189 warning_at (location
, OPT_Wstrict_overflow
,
3190 "assuming signed overflow does not occur when "
3191 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3195 if (val
&& integer_onep (val
))
3199 if (rhs_code
== TRUNC_DIV_EXPR
)
3201 t
= build_int_cst (integer_type_node
, tree_log2 (op1
));
3202 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
3203 gimple_assign_set_rhs1 (stmt
, op0
);
3204 gimple_assign_set_rhs2 (stmt
, t
);
3208 t
= build_int_cst (TREE_TYPE (op1
), 1);
3209 t
= int_const_binop (MINUS_EXPR
, op1
, t
);
3210 t
= fold_convert (TREE_TYPE (op0
), t
);
3212 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
3213 gimple_assign_set_rhs1 (stmt
, op0
);
3214 gimple_assign_set_rhs2 (stmt
, t
);
3218 fold_stmt (gsi
, follow_single_use_edges
);
3225 /* Simplify a min or max if the ranges of the two operands are
3226 disjoint. Return true if we do simplify. */
3229 simplify_using_ranges::simplify_min_or_max_using_ranges
3230 (gimple_stmt_iterator
*gsi
,
3233 tree op0
= gimple_assign_rhs1 (stmt
);
3234 tree op1
= gimple_assign_rhs2 (stmt
);
3238 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3239 (LE_EXPR
, op0
, op1
, &sop
));
3243 val
= (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3244 (LT_EXPR
, op0
, op1
, &sop
));
3249 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3251 location_t location
;
3253 if (!gimple_has_location (stmt
))
3254 location
= input_location
;
3256 location
= gimple_location (stmt
);
3257 warning_at (location
, OPT_Wstrict_overflow
,
3258 "assuming signed overflow does not occur when "
3259 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3262 /* VAL == TRUE -> OP0 < or <= op1
3263 VAL == FALSE -> OP0 > or >= op1. */
3264 tree res
= ((gimple_assign_rhs_code (stmt
) == MAX_EXPR
)
3265 == integer_zerop (val
)) ? op0
: op1
;
3266 gimple_assign_set_rhs_from_tree (gsi
, res
);
3273 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3274 ABS_EXPR. If the operand is <= 0, then simplify the
3275 ABS_EXPR into a NEGATE_EXPR. */
3278 simplify_using_ranges::simplify_abs_using_ranges (gimple_stmt_iterator
*gsi
,
3281 tree op
= gimple_assign_rhs1 (stmt
);
3282 const value_range
*vr
= get_value_range (op
);
3289 val
= compare_range_with_value (LE_EXPR
, vr
, integer_zero_node
, &sop
);
3292 /* The range is neither <= 0 nor > 0. Now see if it is
3293 either < 0 or >= 0. */
3295 val
= compare_range_with_value (LT_EXPR
, vr
, integer_zero_node
,
3301 if (sop
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC
))
3303 location_t location
;
3305 if (!gimple_has_location (stmt
))
3306 location
= input_location
;
3308 location
= gimple_location (stmt
);
3309 warning_at (location
, OPT_Wstrict_overflow
,
3310 "assuming signed overflow does not occur when "
3311 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3314 gimple_assign_set_rhs1 (stmt
, op
);
3315 if (integer_zerop (val
))
3316 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
3318 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
3320 fold_stmt (gsi
, follow_single_use_edges
);
3328 /* value_range wrapper for wi_set_zero_nonzero_bits.
3330 Return TRUE if VR was a constant range and we were able to compute
3334 vr_set_zero_nonzero_bits (const tree expr_type
,
3335 const value_range
*vr
,
3336 wide_int
*may_be_nonzero
,
3337 wide_int
*must_be_nonzero
)
3339 if (range_int_cst_p (vr
))
3341 wi_set_zero_nonzero_bits (expr_type
,
3342 wi::to_wide (vr
->min ()),
3343 wi::to_wide (vr
->max ()),
3344 *may_be_nonzero
, *must_be_nonzero
);
3347 *may_be_nonzero
= wi::minus_one (TYPE_PRECISION (expr_type
));
3348 *must_be_nonzero
= wi::zero (TYPE_PRECISION (expr_type
));
3352 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3353 If all the bits that are being cleared by & are already
3354 known to be zero from VR, or all the bits that are being
3355 set by | are already known to be one from VR, the bit
3356 operation is redundant. */
3359 simplify_using_ranges::simplify_bit_ops_using_ranges
3360 (gimple_stmt_iterator
*gsi
,
3363 tree op0
= gimple_assign_rhs1 (stmt
);
3364 tree op1
= gimple_assign_rhs2 (stmt
);
3365 tree op
= NULL_TREE
;
3366 value_range vr0
, vr1
;
3367 wide_int may_be_nonzero0
, may_be_nonzero1
;
3368 wide_int must_be_nonzero0
, must_be_nonzero1
;
3371 if (TREE_CODE (op0
) == SSA_NAME
)
3372 vr0
= *(get_value_range (op0
));
3373 else if (is_gimple_min_invariant (op0
))
3378 if (TREE_CODE (op1
) == SSA_NAME
)
3379 vr1
= *(get_value_range (op1
));
3380 else if (is_gimple_min_invariant (op1
))
3385 if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0
), &vr0
, &may_be_nonzero0
,
3388 if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1
), &vr1
, &may_be_nonzero1
,
3392 switch (gimple_assign_rhs_code (stmt
))
3395 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3401 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3409 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
3415 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
3426 if (op
== NULL_TREE
)
3429 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (op
), op
);
3430 update_stmt (gsi_stmt (*gsi
));
3434 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3435 a known value range VR.
3437 If there is one and only one value which will satisfy the
3438 conditional, then return that value. Else return NULL.
3440 If signed overflow must be undefined for the value to satisfy
3441 the conditional, then set *STRICT_OVERFLOW_P to true. */
3444 test_for_singularity (enum tree_code cond_code
, tree op0
,
3445 tree op1
, const value_range
*vr
)
3450 /* Extract minimum/maximum values which satisfy the conditional as it was
3452 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
3454 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
3457 if (cond_code
== LT_EXPR
)
3459 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3460 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
3461 /* Signal to compare_values_warnv this expr doesn't overflow. */
3463 TREE_NO_WARNING (max
) = 1;
3466 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
3468 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
3471 if (cond_code
== GT_EXPR
)
3473 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
3474 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
3475 /* Signal to compare_values_warnv this expr doesn't overflow. */
3477 TREE_NO_WARNING (min
) = 1;
3481 /* Now refine the minimum and maximum values using any
3482 value range information we have for op0. */
3485 tree type
= TREE_TYPE (op0
);
3486 tree tmin
= wide_int_to_tree (type
, vr
->lower_bound ());
3487 tree tmax
= wide_int_to_tree (type
, vr
->upper_bound ());
3488 if (compare_values (tmin
, min
) == 1)
3490 if (compare_values (tmax
, max
) == -1)
3493 /* If the new min/max values have converged to a single value,
3494 then there is only one value which can satisfy the condition,
3495 return that value. */
3496 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
3502 /* Return whether the value range *VR fits in an integer type specified
3503 by PRECISION and UNSIGNED_P. */
3506 range_fits_type_p (const value_range
*vr
,
3507 unsigned dest_precision
, signop dest_sgn
)
3510 unsigned src_precision
;
3514 /* We can only handle integral and pointer types. */
3515 src_type
= vr
->type ();
3516 if (!INTEGRAL_TYPE_P (src_type
)
3517 && !POINTER_TYPE_P (src_type
))
3520 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3521 and so is an identity transform. */
3522 src_precision
= TYPE_PRECISION (vr
->type ());
3523 src_sgn
= TYPE_SIGN (src_type
);
3524 if ((src_precision
< dest_precision
3525 && !(dest_sgn
== UNSIGNED
&& src_sgn
== SIGNED
))
3526 || (src_precision
== dest_precision
&& src_sgn
== dest_sgn
))
3529 /* Now we can only handle ranges with constant bounds. */
3530 if (!range_int_cst_p (vr
))
3533 /* For sign changes, the MSB of the wide_int has to be clear.
3534 An unsigned value with its MSB set cannot be represented by
3535 a signed wide_int, while a negative value cannot be represented
3536 by an unsigned wide_int. */
3537 if (src_sgn
!= dest_sgn
3538 && (wi::lts_p (wi::to_wide (vr
->min ()), 0)
3539 || wi::lts_p (wi::to_wide (vr
->max ()), 0)))
3542 /* Then we can perform the conversion on both ends and compare
3543 the result for equality. */
3544 tem
= wi::ext (wi::to_widest (vr
->min ()), dest_precision
, dest_sgn
);
3545 if (tem
!= wi::to_widest (vr
->min ()))
3547 tem
= wi::ext (wi::to_widest (vr
->max ()), dest_precision
, dest_sgn
);
3548 if (tem
!= wi::to_widest (vr
->max ()))
3554 /* If COND can be folded entirely as TRUE or FALSE, rewrite the
3555 conditional as such, and return TRUE. */
3558 simplify_using_ranges::fold_cond (gcond
*cond
)
3560 /* ?? vrp_folder::fold_predicate_in() is a superset of this. At
3561 some point we should merge all variants of this code. */
3563 vrp_visit_cond_stmt (cond
, &taken_edge
);
3566 if (taken_edge
->flags
& EDGE_TRUE_VALUE
)
3567 gimple_cond_make_true (cond
);
3568 else if (taken_edge
->flags
& EDGE_FALSE_VALUE
)
3569 gimple_cond_make_false (cond
);
3578 /* Simplify a conditional using a relational operator to an equality
3579 test if the range information indicates only one value can satisfy
3580 the original conditional. */
3583 simplify_using_ranges::simplify_cond_using_ranges_1 (gcond
*stmt
)
3585 tree op0
= gimple_cond_lhs (stmt
);
3586 tree op1
= gimple_cond_rhs (stmt
);
3587 enum tree_code cond_code
= gimple_cond_code (stmt
);
3589 if (fold_cond (stmt
))
3592 if (cond_code
!= NE_EXPR
3593 && cond_code
!= EQ_EXPR
3594 && TREE_CODE (op0
) == SSA_NAME
3595 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3596 && is_gimple_min_invariant (op1
))
3598 const value_range
*vr
= get_value_range (op0
);
3600 /* If we have range information for OP0, then we might be
3601 able to simplify this conditional. */
3602 if (!vr
->undefined_p () && !vr
->varying_p ())
3604 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, vr
);
3609 fprintf (dump_file
, "Simplified relational ");
3610 print_gimple_stmt (dump_file
, stmt
, 0);
3611 fprintf (dump_file
, " into ");
3614 gimple_cond_set_code (stmt
, EQ_EXPR
);
3615 gimple_cond_set_lhs (stmt
, op0
);
3616 gimple_cond_set_rhs (stmt
, new_tree
);
3622 print_gimple_stmt (dump_file
, stmt
, 0);
3623 fprintf (dump_file
, "\n");
3629 /* Try again after inverting the condition. We only deal
3630 with integral types here, so no need to worry about
3631 issues with inverting FP comparisons. */
3632 new_tree
= test_for_singularity
3633 (invert_tree_comparison (cond_code
, false),
3639 fprintf (dump_file
, "Simplified relational ");
3640 print_gimple_stmt (dump_file
, stmt
, 0);
3641 fprintf (dump_file
, " into ");
3644 gimple_cond_set_code (stmt
, NE_EXPR
);
3645 gimple_cond_set_lhs (stmt
, op0
);
3646 gimple_cond_set_rhs (stmt
, new_tree
);
3652 print_gimple_stmt (dump_file
, stmt
, 0);
3653 fprintf (dump_file
, "\n");
3663 /* STMT is a conditional at the end of a basic block.
3665 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3666 was set via a type conversion, try to replace the SSA_NAME with the RHS
3667 of the type conversion. Doing so makes the conversion dead which helps
3668 subsequent passes. */
3671 simplify_cond_using_ranges_2 (vr_values
*store
, gcond
*stmt
)
3673 tree op0
= gimple_cond_lhs (stmt
);
3674 tree op1
= gimple_cond_rhs (stmt
);
3676 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3677 see if OP0 was set by a type conversion where the source of
3678 the conversion is another SSA_NAME with a range that fits
3679 into the range of OP0's type.
3681 If so, the conversion is redundant as the earlier SSA_NAME can be
3682 used for the comparison directly if we just massage the constant in the
3684 if (TREE_CODE (op0
) == SSA_NAME
3685 && TREE_CODE (op1
) == INTEGER_CST
)
3687 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op0
);
3690 if (!is_gimple_assign (def_stmt
)
3691 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3694 innerop
= gimple_assign_rhs1 (def_stmt
);
3696 if (TREE_CODE (innerop
) == SSA_NAME
3697 && !POINTER_TYPE_P (TREE_TYPE (innerop
))
3698 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
)
3699 && desired_pro_or_demotion_p (TREE_TYPE (innerop
), TREE_TYPE (op0
)))
3701 const value_range
*vr
= store
->get_value_range (innerop
);
3703 if (range_int_cst_p (vr
)
3704 && range_fits_type_p (vr
,
3705 TYPE_PRECISION (TREE_TYPE (op0
)),
3706 TYPE_SIGN (TREE_TYPE (op0
)))
3707 && int_fits_type_p (op1
, TREE_TYPE (innerop
)))
3709 tree newconst
= fold_convert (TREE_TYPE (innerop
), op1
);
3710 gimple_cond_set_lhs (stmt
, innerop
);
3711 gimple_cond_set_rhs (stmt
, newconst
);
3713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3715 fprintf (dump_file
, "Folded into: ");
3716 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3717 fprintf (dump_file
, "\n");
3724 /* Simplify a switch statement using the value range of the switch
3728 simplify_using_ranges::simplify_switch_using_ranges (gswitch
*stmt
)
3730 tree op
= gimple_switch_index (stmt
);
3731 const value_range
*vr
= NULL
;
3735 size_t i
= 0, j
= 0, n
, n2
;
3738 size_t k
= 1, l
= 0;
3740 if (TREE_CODE (op
) == SSA_NAME
)
3742 vr
= get_value_range (op
);
3744 /* We can only handle integer ranges. */
3745 if (vr
->varying_p ()
3746 || vr
->undefined_p ()
3747 || vr
->symbolic_p ())
3750 /* Find case label for min/max of the value range. */
3751 take_default
= !find_case_label_ranges (stmt
, vr
, &i
, &j
, &k
, &l
);
3753 else if (TREE_CODE (op
) == INTEGER_CST
)
3755 take_default
= !find_case_label_index (stmt
, 1, op
, &i
);
3769 n
= gimple_switch_num_labels (stmt
);
3771 /* We can truncate the case label ranges that partially overlap with OP's
3773 size_t min_idx
= 1, max_idx
= 0;
3775 find_case_label_range (stmt
, vr
->min (), vr
->max (), &min_idx
, &max_idx
);
3776 if (min_idx
<= max_idx
)
3778 tree min_label
= gimple_switch_label (stmt
, min_idx
);
3779 tree max_label
= gimple_switch_label (stmt
, max_idx
);
3781 /* Avoid changing the type of the case labels when truncating. */
3782 tree case_label_type
= TREE_TYPE (CASE_LOW (min_label
));
3783 tree vr_min
= fold_convert (case_label_type
, vr
->min ());
3784 tree vr_max
= fold_convert (case_label_type
, vr
->max ());
3786 if (vr
->kind () == VR_RANGE
)
3788 /* If OP's value range is [2,8] and the low label range is
3789 0 ... 3, truncate the label's range to 2 .. 3. */
3790 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3791 && CASE_HIGH (min_label
) != NULL_TREE
3792 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3793 CASE_LOW (min_label
) = vr_min
;
3795 /* If OP's value range is [2,8] and the high label range is
3796 7 ... 10, truncate the label's range to 7 .. 8. */
3797 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3798 && CASE_HIGH (max_label
) != NULL_TREE
3799 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3800 CASE_HIGH (max_label
) = vr_max
;
3802 else if (vr
->kind () == VR_ANTI_RANGE
)
3804 tree one_cst
= build_one_cst (case_label_type
);
3806 if (min_label
== max_label
)
3808 /* If OP's value range is ~[7,8] and the label's range is
3809 7 ... 10, truncate the label's range to 9 ... 10. */
3810 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) == 0
3811 && CASE_HIGH (min_label
) != NULL_TREE
3812 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) > 0)
3813 CASE_LOW (min_label
)
3814 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3816 /* If OP's value range is ~[7,8] and the label's range is
3817 5 ... 8, truncate the label's range to 5 ... 6. */
3818 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3819 && CASE_HIGH (min_label
) != NULL_TREE
3820 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) == 0)
3821 CASE_HIGH (min_label
)
3822 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3826 /* If OP's value range is ~[2,8] and the low label range is
3827 0 ... 3, truncate the label's range to 0 ... 1. */
3828 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
3829 && CASE_HIGH (min_label
) != NULL_TREE
3830 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
3831 CASE_HIGH (min_label
)
3832 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
3834 /* If OP's value range is ~[2,8] and the high label range is
3835 7 ... 10, truncate the label's range to 9 ... 10. */
3836 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
3837 && CASE_HIGH (max_label
) != NULL_TREE
3838 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
3839 CASE_LOW (max_label
)
3840 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
3844 /* Canonicalize singleton case ranges. */
3845 if (tree_int_cst_equal (CASE_LOW (min_label
), CASE_HIGH (min_label
)))
3846 CASE_HIGH (min_label
) = NULL_TREE
;
3847 if (tree_int_cst_equal (CASE_LOW (max_label
), CASE_HIGH (max_label
)))
3848 CASE_HIGH (max_label
) = NULL_TREE
;
3851 /* We can also eliminate case labels that lie completely outside OP's value
3854 /* Bail out if this is just all edges taken. */
3860 /* Build a new vector of taken case labels. */
3861 vec2
= make_tree_vec (j
- i
+ 1 + l
- k
+ 1 + (int)take_default
);
3864 /* Add the default edge, if necessary. */
3866 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
3868 for (; i
<= j
; ++i
, ++n2
)
3869 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
3871 for (; k
<= l
; ++k
, ++n2
)
3872 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, k
);
3874 /* Mark needed edges. */
3875 for (i
= 0; i
< n2
; ++i
)
3877 e
= find_edge (gimple_bb (stmt
),
3878 label_to_block (cfun
,
3879 CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
3880 e
->aux
= (void *)-1;
3883 /* Queue not needed edges for later removal. */
3884 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
3886 if (e
->aux
== (void *)-1)
3892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3894 fprintf (dump_file
, "removing unreachable case label\n");
3896 to_remove_edges
.safe_push (e
);
3897 e
->flags
&= ~EDGE_EXECUTABLE
;
3898 e
->flags
|= EDGE_IGNORE
;
3901 /* And queue an update for the stmt. */
3904 to_update_switch_stmts
.safe_push (su
);
3909 simplify_using_ranges::cleanup_edges_and_switches (void)
3915 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
3916 CFG in a broken state and requires a cfg_cleanup run. */
3917 FOR_EACH_VEC_ELT (to_remove_edges
, i
, e
)
3920 /* Update SWITCH_EXPR case label vector. */
3921 FOR_EACH_VEC_ELT (to_update_switch_stmts
, i
, su
)
3924 size_t n
= TREE_VEC_LENGTH (su
->vec
);
3926 gimple_switch_set_num_labels (su
->stmt
, n
);
3927 for (j
= 0; j
< n
; j
++)
3928 gimple_switch_set_label (su
->stmt
, j
, TREE_VEC_ELT (su
->vec
, j
));
3929 /* As we may have replaced the default label with a regular one
3930 make sure to make it a real default label again. This ensures
3931 optimal expansion. */
3932 label
= gimple_switch_label (su
->stmt
, 0);
3933 CASE_LOW (label
) = NULL_TREE
;
3934 CASE_HIGH (label
) = NULL_TREE
;
3937 if (!to_remove_edges
.is_empty ())
3939 free_dominance_info (CDI_DOMINATORS
);
3940 loops_state_set (LOOPS_NEED_FIXUP
);
3943 to_remove_edges
.release ();
3944 to_update_switch_stmts
.release ();
3947 /* Simplify an integral conversion from an SSA name in STMT. */
3950 simplify_conversion_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
3952 tree innerop
, middleop
, finaltype
;
3954 signop inner_sgn
, middle_sgn
, final_sgn
;
3955 unsigned inner_prec
, middle_prec
, final_prec
;
3956 widest_int innermin
, innermed
, innermax
, middlemin
, middlemed
, middlemax
;
3958 finaltype
= TREE_TYPE (gimple_assign_lhs (stmt
));
3959 if (!INTEGRAL_TYPE_P (finaltype
))
3961 middleop
= gimple_assign_rhs1 (stmt
);
3962 def_stmt
= SSA_NAME_DEF_STMT (middleop
);
3963 if (!is_gimple_assign (def_stmt
)
3964 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3966 innerop
= gimple_assign_rhs1 (def_stmt
);
3967 if (TREE_CODE (innerop
) != SSA_NAME
3968 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
))
3971 /* Get the value-range of the inner operand. Use get_range_info in
3972 case innerop was created during substitute-and-fold. */
3973 wide_int imin
, imax
;
3975 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
)))
3977 get_range_info (innerop
, vr
);
3978 if (vr
.undefined_p () || vr
.varying_p ())
3980 innermin
= widest_int::from (vr
.lower_bound (), TYPE_SIGN (TREE_TYPE (innerop
)));
3981 innermax
= widest_int::from (vr
.upper_bound (), TYPE_SIGN (TREE_TYPE (innerop
)));
3983 /* Simulate the conversion chain to check if the result is equal if
3984 the middle conversion is removed. */
3985 inner_prec
= TYPE_PRECISION (TREE_TYPE (innerop
));
3986 middle_prec
= TYPE_PRECISION (TREE_TYPE (middleop
));
3987 final_prec
= TYPE_PRECISION (finaltype
);
3989 /* If the first conversion is not injective, the second must not
3991 if (wi::gtu_p (innermax
- innermin
,
3992 wi::mask
<widest_int
> (middle_prec
, false))
3993 && middle_prec
< final_prec
)
3995 /* We also want a medium value so that we can track the effect that
3996 narrowing conversions with sign change have. */
3997 inner_sgn
= TYPE_SIGN (TREE_TYPE (innerop
));
3998 if (inner_sgn
== UNSIGNED
)
3999 innermed
= wi::shifted_mask
<widest_int
> (1, inner_prec
- 1, false);
4002 if (wi::cmp (innermin
, innermed
, inner_sgn
) >= 0
4003 || wi::cmp (innermed
, innermax
, inner_sgn
) >= 0)
4004 innermed
= innermin
;
4006 middle_sgn
= TYPE_SIGN (TREE_TYPE (middleop
));
4007 middlemin
= wi::ext (innermin
, middle_prec
, middle_sgn
);
4008 middlemed
= wi::ext (innermed
, middle_prec
, middle_sgn
);
4009 middlemax
= wi::ext (innermax
, middle_prec
, middle_sgn
);
4011 /* Require that the final conversion applied to both the original
4012 and the intermediate range produces the same result. */
4013 final_sgn
= TYPE_SIGN (finaltype
);
4014 if (wi::ext (middlemin
, final_prec
, final_sgn
)
4015 != wi::ext (innermin
, final_prec
, final_sgn
)
4016 || wi::ext (middlemed
, final_prec
, final_sgn
)
4017 != wi::ext (innermed
, final_prec
, final_sgn
)
4018 || wi::ext (middlemax
, final_prec
, final_sgn
)
4019 != wi::ext (innermax
, final_prec
, final_sgn
))
4022 gimple_assign_set_rhs1 (stmt
, innerop
);
4023 fold_stmt (gsi
, follow_single_use_edges
);
4027 /* Simplify a conversion from integral SSA name to float in STMT. */
4030 simplify_using_ranges::simplify_float_conversion_using_ranges
4031 (gimple_stmt_iterator
*gsi
,
4034 tree rhs1
= gimple_assign_rhs1 (stmt
);
4035 const value_range
*vr
= get_value_range (rhs1
);
4036 scalar_float_mode fltmode
4037 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
)));
4038 scalar_int_mode mode
;
4042 /* We can only handle constant ranges. */
4043 if (!range_int_cst_p (vr
))
4046 /* First check if we can use a signed type in place of an unsigned. */
4047 scalar_int_mode rhs_mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1
));
4048 if (TYPE_UNSIGNED (TREE_TYPE (rhs1
))
4049 && can_float_p (fltmode
, rhs_mode
, 0) != CODE_FOR_nothing
4050 && range_fits_type_p (vr
, TYPE_PRECISION (TREE_TYPE (rhs1
)), SIGNED
))
4052 /* If we can do the conversion in the current input mode do nothing. */
4053 else if (can_float_p (fltmode
, rhs_mode
,
4054 TYPE_UNSIGNED (TREE_TYPE (rhs1
))) != CODE_FOR_nothing
)
4056 /* Otherwise search for a mode we can use, starting from the narrowest
4057 integer mode available. */
4060 mode
= NARROWEST_INT_MODE
;
4063 /* If we cannot do a signed conversion to float from mode
4064 or if the value-range does not fit in the signed type
4065 try with a wider mode. */
4066 if (can_float_p (fltmode
, mode
, 0) != CODE_FOR_nothing
4067 && range_fits_type_p (vr
, GET_MODE_PRECISION (mode
), SIGNED
))
4070 /* But do not widen the input. Instead leave that to the
4071 optabs expansion code. */
4072 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
4073 || GET_MODE_PRECISION (mode
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
4078 /* It works, insert a truncation or sign-change before the
4079 float conversion. */
4080 tem
= make_ssa_name (build_nonstandard_integer_type
4081 (GET_MODE_PRECISION (mode
), 0));
4082 conv
= gimple_build_assign (tem
, NOP_EXPR
, rhs1
);
4083 gsi_insert_before (gsi
, conv
, GSI_SAME_STMT
);
4084 gimple_assign_set_rhs1 (stmt
, tem
);
4085 fold_stmt (gsi
, follow_single_use_edges
);
4090 /* Simplify an internal fn call using ranges if possible. */
4093 simplify_using_ranges::simplify_internal_call_using_ranges
4094 (gimple_stmt_iterator
*gsi
,
4097 enum tree_code subcode
;
4098 bool is_ubsan
= false;
4100 switch (gimple_call_internal_fn (stmt
))
4102 case IFN_UBSAN_CHECK_ADD
:
4103 subcode
= PLUS_EXPR
;
4106 case IFN_UBSAN_CHECK_SUB
:
4107 subcode
= MINUS_EXPR
;
4110 case IFN_UBSAN_CHECK_MUL
:
4111 subcode
= MULT_EXPR
;
4114 case IFN_ADD_OVERFLOW
:
4115 subcode
= PLUS_EXPR
;
4117 case IFN_SUB_OVERFLOW
:
4118 subcode
= MINUS_EXPR
;
4120 case IFN_MUL_OVERFLOW
:
4121 subcode
= MULT_EXPR
;
4127 tree op0
= gimple_call_arg (stmt
, 0);
4128 tree op1
= gimple_call_arg (stmt
, 1);
4132 type
= TREE_TYPE (op0
);
4133 if (VECTOR_TYPE_P (type
))
4136 else if (gimple_call_lhs (stmt
) == NULL_TREE
)
4139 type
= TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt
)));
4140 if (!check_for_binary_op_overflow (store
, subcode
, type
, op0
, op1
, &ovf
)
4141 || (is_ubsan
&& ovf
))
4145 location_t loc
= gimple_location (stmt
);
4147 g
= gimple_build_assign (gimple_call_lhs (stmt
), subcode
, op0
, op1
);
4150 int prec
= TYPE_PRECISION (type
);
4153 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
4154 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
4155 utype
= build_nonstandard_integer_type (prec
, 1);
4156 if (TREE_CODE (op0
) == INTEGER_CST
)
4157 op0
= fold_convert (utype
, op0
);
4158 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op0
)))
4160 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op0
);
4161 gimple_set_location (g
, loc
);
4162 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4163 op0
= gimple_assign_lhs (g
);
4165 if (TREE_CODE (op1
) == INTEGER_CST
)
4166 op1
= fold_convert (utype
, op1
);
4167 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op1
)))
4169 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op1
);
4170 gimple_set_location (g
, loc
);
4171 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4172 op1
= gimple_assign_lhs (g
);
4174 g
= gimple_build_assign (make_ssa_name (utype
), subcode
, op0
, op1
);
4175 gimple_set_location (g
, loc
);
4176 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4179 g
= gimple_build_assign (make_ssa_name (type
), NOP_EXPR
,
4180 gimple_assign_lhs (g
));
4181 gimple_set_location (g
, loc
);
4182 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
4184 g
= gimple_build_assign (gimple_call_lhs (stmt
), COMPLEX_EXPR
,
4185 gimple_assign_lhs (g
),
4186 build_int_cst (type
, ovf
));
4188 gimple_set_location (g
, loc
);
4189 gsi_replace (gsi
, g
, false);
4193 /* Return true if VAR is a two-valued variable. Set a and b with the
4194 two-values when it is true. Return false otherwise. */
4197 simplify_using_ranges::two_valued_val_range_p (tree var
, tree
*a
, tree
*b
)
4199 value_range vr
= *get_value_range (var
);
4200 vr
.normalize_symbolics ();
4201 if (vr
.varying_p () || vr
.undefined_p ())
4204 if ((vr
.num_pairs () == 1 && vr
.upper_bound () - vr
.lower_bound () == 1)
4205 || (vr
.num_pairs () == 2
4206 && vr
.lower_bound (0) == vr
.upper_bound (0)
4207 && vr
.lower_bound (1) == vr
.upper_bound (1)))
4209 *a
= wide_int_to_tree (TREE_TYPE (var
), vr
.lower_bound ());
4210 *b
= wide_int_to_tree (TREE_TYPE (var
), vr
.upper_bound ());
4216 simplify_using_ranges::simplify_using_ranges (vr_values
*store
)
4219 to_remove_edges
= vNULL
;
4220 to_update_switch_stmts
= vNULL
;
4223 simplify_using_ranges::~simplify_using_ranges ()
4225 cleanup_edges_and_switches ();
4228 /* Simplify STMT using ranges if possible. */
4231 simplify_using_ranges::simplify (gimple_stmt_iterator
*gsi
)
4233 gimple
*stmt
= gsi_stmt (*gsi
);
4234 if (is_gimple_assign (stmt
))
4236 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
4237 tree rhs1
= gimple_assign_rhs1 (stmt
);
4238 tree rhs2
= gimple_assign_rhs2 (stmt
);
4239 tree lhs
= gimple_assign_lhs (stmt
);
4240 tree val1
= NULL_TREE
, val2
= NULL_TREE
;
4241 use_operand_p use_p
;
4246 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4248 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4252 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4254 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4256 if (TREE_CODE_CLASS (rhs_code
) == tcc_binary
4257 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
4258 && ((TREE_CODE (rhs1
) == INTEGER_CST
4259 && TREE_CODE (rhs2
) == SSA_NAME
)
4260 || (TREE_CODE (rhs2
) == INTEGER_CST
4261 && TREE_CODE (rhs1
) == SSA_NAME
))
4262 && single_imm_use (lhs
, &use_p
, &use_stmt
)
4263 && gimple_code (use_stmt
) == GIMPLE_COND
)
4266 tree new_rhs1
= NULL_TREE
;
4267 tree new_rhs2
= NULL_TREE
;
4268 tree cmp_var
= NULL_TREE
;
4270 if (TREE_CODE (rhs2
) == SSA_NAME
4271 && two_valued_val_range_p (rhs2
, &val1
, &val2
))
4273 /* Optimize RHS1 OP [VAL1, VAL2]. */
4274 new_rhs1
= int_const_binop (rhs_code
, rhs1
, val1
);
4275 new_rhs2
= int_const_binop (rhs_code
, rhs1
, val2
);
4278 else if (TREE_CODE (rhs1
) == SSA_NAME
4279 && two_valued_val_range_p (rhs1
, &val1
, &val2
))
4281 /* Optimize [VAL1, VAL2] OP RHS2. */
4282 new_rhs1
= int_const_binop (rhs_code
, val1
, rhs2
);
4283 new_rhs2
= int_const_binop (rhs_code
, val2
, rhs2
);
4287 /* If we could not find two-vals or the optimzation is invalid as
4288 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4289 if (new_rhs1
&& new_rhs2
)
4291 tree cond
= build2 (EQ_EXPR
, boolean_type_node
, cmp_var
, val1
);
4292 gimple_assign_set_rhs_with_ops (gsi
,
4296 update_stmt (gsi_stmt (*gsi
));
4297 fold_stmt (gsi
, follow_single_use_edges
);
4306 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4307 if the RHS is zero or one, and the LHS are known to be boolean
4309 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4310 return simplify_truth_ops_using_ranges (gsi
, stmt
);
4313 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4314 and BIT_AND_EXPR respectively if the first operand is greater
4315 than zero and the second operand is an exact power of two.
4316 Also optimize TRUNC_MOD_EXPR away if the second operand is
4317 constant and the first operand already has the right value
4319 case TRUNC_DIV_EXPR
:
4320 case TRUNC_MOD_EXPR
:
4321 if ((TREE_CODE (rhs1
) == SSA_NAME
4322 || TREE_CODE (rhs1
) == INTEGER_CST
)
4323 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4324 return simplify_div_or_mod_using_ranges (gsi
, stmt
);
4327 /* Transform ABS (X) into X or -X as appropriate. */
4329 if (TREE_CODE (rhs1
) == SSA_NAME
4330 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4331 return simplify_abs_using_ranges (gsi
, stmt
);
4336 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4337 if all the bits being cleared are already cleared or
4338 all the bits being set are already set. */
4339 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4340 return simplify_bit_ops_using_ranges (gsi
, stmt
);
4344 if (TREE_CODE (rhs1
) == SSA_NAME
4345 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4346 return simplify_conversion_using_ranges (gsi
, stmt
);
4350 if (TREE_CODE (rhs1
) == SSA_NAME
4351 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4352 return simplify_float_conversion_using_ranges (gsi
, stmt
);
4357 return simplify_min_or_max_using_ranges (gsi
, stmt
);
4363 else if (gimple_code (stmt
) == GIMPLE_COND
)
4364 return simplify_cond_using_ranges_1 (as_a
<gcond
*> (stmt
));
4365 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
4366 return simplify_switch_using_ranges (as_a
<gswitch
*> (stmt
));
4367 else if (is_gimple_call (stmt
)
4368 && gimple_call_internal_p (stmt
))
4369 return simplify_internal_call_using_ranges (gsi
, stmt
);
4374 /* Set the lattice entry for VAR to VR. */
4377 vr_values::set_vr_value (tree var
, value_range_equiv
*vr
)
4379 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4381 vr_value
[SSA_NAME_VERSION (var
)] = vr
;
4384 /* Swap the lattice entry for VAR with VR and return the old entry. */
4387 vr_values::swap_vr_value (tree var
, value_range_equiv
*vr
)
4389 if (SSA_NAME_VERSION (var
) >= num_vr_values
)
4391 std::swap (vr_value
[SSA_NAME_VERSION (var
)], vr
);