1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2024 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-iterator.h"
36 #include "gimple-fold.h"
38 #include "tree-ssa-loop-niter.h"
39 #include "tree-ssa-loop.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-ssa-propagate.h"
44 #include "tree-chrec.h"
45 #include "omp-general.h"
46 #include "case-cfn-macros.h"
47 #include "alloc-pool.h"
50 #include "vr-values.h"
53 #include "gimple-range.h"
55 /* Return true if op is in a boolean [0, 1] value-range. */
58 simplify_using_ranges::op_with_boolean_value_range_p (tree op
, gimple
*s
)
60 if (TYPE_PRECISION (TREE_TYPE (op
)) == 1)
63 if (integer_zerop (op
)
67 if (TREE_CODE (op
) != SSA_NAME
)
70 /* ?? Errr, this should probably check for [0,0] and [1,1] as well
73 return (query
->range_of_expr (vr
, op
, s
)
74 && vr
== range_true_and_false (TREE_TYPE (op
)));
77 /* Helper function for simplify_internal_call_using_ranges and
78 extract_range_basic. Return true if OP0 SUBCODE OP1 for
79 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
80 always overflow. Set *OVF to true if it is known to always
84 check_for_binary_op_overflow (range_query
*query
,
85 enum tree_code subcode
, tree type
,
86 tree op0
, tree op1
, bool *ovf
, gimple
*s
= NULL
)
89 if (!query
->range_of_expr (vr0
, op0
, s
) || vr0
.undefined_p ())
90 vr0
.set_varying (TREE_TYPE (op0
));
91 if (!query
->range_of_expr (vr1
, op1
, s
) || vr1
.undefined_p ())
92 vr1
.set_varying (TREE_TYPE (op1
));
94 tree vr0min
= wide_int_to_tree (TREE_TYPE (op0
), vr0
.lower_bound ());
95 tree vr0max
= wide_int_to_tree (TREE_TYPE (op0
), vr0
.upper_bound ());
96 tree vr1min
= wide_int_to_tree (TREE_TYPE (op1
), vr1
.lower_bound ());
97 tree vr1max
= wide_int_to_tree (TREE_TYPE (op1
), vr1
.upper_bound ());
99 *ovf
= arith_overflowed_p (subcode
, type
, vr0min
,
100 subcode
== MINUS_EXPR
? vr1max
: vr1min
);
101 if (arith_overflowed_p (subcode
, type
, vr0max
,
102 subcode
== MINUS_EXPR
? vr1min
: vr1max
) != *ovf
)
104 if (subcode
== MULT_EXPR
)
106 if (arith_overflowed_p (subcode
, type
, vr0min
, vr1max
) != *ovf
107 || arith_overflowed_p (subcode
, type
, vr0max
, vr1min
) != *ovf
)
112 /* So far we found that there is an overflow on the boundaries.
113 That doesn't prove that there is an overflow even for all values
114 in between the boundaries. For that compute widest2_int range
115 of the result and see if it doesn't overlap the range of
117 widest2_int wmin
, wmax
;
120 signop sign0
= TYPE_SIGN (TREE_TYPE (op0
));
121 signop sign1
= TYPE_SIGN (TREE_TYPE (op1
));
122 w
[0] = widest2_int::from (vr0
.lower_bound (), sign0
);
123 w
[1] = widest2_int::from (vr0
.upper_bound (), sign0
);
124 w
[2] = widest2_int::from (vr1
.lower_bound (), sign1
);
125 w
[3] = widest2_int::from (vr1
.upper_bound (), sign1
);
126 for (i
= 0; i
< 4; i
++)
132 wt
= wi::add (w
[i
& 1], w
[2 + (i
& 2) / 2]);
135 wt
= wi::sub (w
[i
& 1], w
[2 + (i
& 2) / 2]);
138 wt
= wi::mul (w
[i
& 1], w
[2 + (i
& 2) / 2]);
150 wmin
= wi::smin (wmin
, wt
);
151 wmax
= wi::smax (wmax
, wt
);
154 /* The result of op0 CODE op1 is known to be in range
157 = widest2_int::from (irange_val_min (type
), TYPE_SIGN (type
));
159 = widest2_int::from (irange_val_max (type
), TYPE_SIGN (type
));
160 /* If all values in [wmin, wmax] are smaller than
161 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
162 the arithmetic operation will always overflow. */
163 if (wmax
< wtmin
|| wmin
> wtmax
)
170 /* Set INIT, STEP, and DIRECTION to the corresponding values of NAME
171 within LOOP, and return TRUE. Otherwise return FALSE, and set R to
172 the conservative range of NAME within the loop. */
175 get_scev_info (vrange
&r
, tree name
, gimple
*stmt
, class loop
*l
,
176 tree
&init
, tree
&step
, enum ev_direction
&dir
)
178 tree ev
= analyze_scalar_evolution (l
, name
);
179 tree chrec
= instantiate_parameters (l
, ev
);
180 tree type
= TREE_TYPE (name
);
181 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
183 r
.set_varying (type
);
186 if (is_gimple_min_invariant (chrec
))
188 if (is_gimple_constant (chrec
))
189 r
.set (chrec
, chrec
);
191 r
.set_varying (type
);
195 init
= initial_condition_in_loop_num (chrec
, l
->num
);
196 step
= evolution_part_in_loop_num (chrec
, l
->num
);
199 r
.set_varying (type
);
202 dir
= scev_direction (chrec
);
203 if (dir
== EV_DIR_UNKNOWN
204 || scev_probably_wraps_p (NULL
, init
, step
, stmt
,
205 get_chrec_loop (chrec
), true))
207 r
.set_varying (type
);
213 /* Return TRUE if STEP * NIT may overflow when calculated in TYPE. */
216 induction_variable_may_overflow_p (tree type
,
217 const wide_int
&step
, const widest_int
&nit
)
219 wi::overflow_type ovf
;
220 signop sign
= TYPE_SIGN (type
);
221 widest_int max_step
= wi::mul (widest_int::from (step
, sign
),
224 if (ovf
|| !wi::fits_to_tree_p (max_step
, type
))
227 /* For a signed type we have to check whether the result has the
228 expected signedness which is that of the step as number of
229 iterations is unsigned. */
230 return (sign
== SIGNED
231 && wi::gts_p (max_step
, 0) != wi::gts_p (step
, 0));
234 /* Set R to the range from BEGIN to END, assuming the direction of the
238 range_from_loop_direction (irange
&r
, tree type
,
239 const irange
&begin
, const irange
&end
,
242 signop sign
= TYPE_SIGN (type
);
244 if (begin
.undefined_p () || end
.undefined_p ())
245 r
.set_varying (type
);
246 else if (dir
== EV_DIR_GROWS
)
248 if (wi::gt_p (begin
.lower_bound (), end
.upper_bound (), sign
))
249 r
.set_varying (type
);
251 r
= int_range
<1> (type
, begin
.lower_bound (), end
.upper_bound ());
255 if (wi::gt_p (end
.lower_bound (), begin
.upper_bound (), sign
))
256 r
.set_varying (type
);
258 r
= int_range
<1> (type
, end
.lower_bound (), begin
.upper_bound ());
262 /* Set V to the range of NAME in STMT within LOOP. Return TRUE if a
266 range_of_var_in_loop (vrange
&v
, tree name
, class loop
*l
, gimple
*stmt
,
270 enum ev_direction dir
;
271 if (!get_scev_info (v
, name
, stmt
, l
, init
, step
, dir
))
274 // Calculate ranges for the values from SCEV.
275 irange
&r
= as_a
<irange
> (v
);
276 tree type
= TREE_TYPE (init
);
277 int_range
<2> rinit (type
), rstep (type
), max_init (type
);
278 if (!query
->range_of_expr (rinit
, init
, stmt
)
279 || !query
->range_of_expr (rstep
, step
, stmt
))
282 // Calculate the final range of NAME if possible.
283 if (rinit
.singleton_p () && rstep
.singleton_p ())
286 if (!max_loop_iterations (l
, &nit
))
289 if (!induction_variable_may_overflow_p (type
, rstep
.lower_bound (), nit
))
291 // Calculate the max bounds for init (init + niter * step).
292 wide_int w
= wide_int::from (nit
, TYPE_PRECISION (type
), TYPE_SIGN (type
));
293 int_range
<1> niter (type
, w
, w
);
294 int_range_max max_step
;
295 range_op_handler
mult_handler (MULT_EXPR
);
296 range_op_handler
plus_handler (PLUS_EXPR
);
297 if (!mult_handler
.fold_range (max_step
, type
, niter
, rstep
)
298 || !plus_handler
.fold_range (max_init
, type
, rinit
, max_step
))
302 range_from_loop_direction (r
, type
, rinit
, max_init
, dir
);
306 /* Helper function for vrp_evaluate_conditional_warnv & other
310 simplify_using_ranges::fold_cond_with_ops (enum tree_code code
,
311 tree op0
, tree op1
, gimple
*s
)
313 Value_Range
r0 (TREE_TYPE (op0
));
314 Value_Range
r1 (TREE_TYPE (op1
));
315 if (!query
->range_of_expr (r0
, op0
, s
)
316 || !query
->range_of_expr (r1
, op1
, s
))
319 tree type
= TREE_TYPE (op0
);
321 range_op_handler
handler (code
);
322 if (handler
&& handler
.fold_range (res
, type
, r0
, r1
))
324 if (res
== range_true ())
325 return boolean_true_node
;
326 if (res
== range_false ())
327 return boolean_false_node
;
332 /* Helper function for legacy_fold_cond. */
335 simplify_using_ranges::legacy_fold_cond_overflow (gimple
*stmt
)
338 tree_code code
= gimple_cond_code (stmt
);
339 tree op0
= gimple_cond_lhs (stmt
);
340 tree op1
= gimple_cond_rhs (stmt
);
342 /* We only deal with integral and pointer types. */
343 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
344 && !POINTER_TYPE_P (TREE_TYPE (op0
)))
347 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
348 as a simple equality test, then prefer that over its current form
351 An overflow test which collapses to an equality test can always be
352 expressed as a comparison of one argument against zero. Overflow
353 occurs when the chosen argument is zero and does not occur if the
354 chosen argument is not zero. */
356 if (overflow_comparison_p (code
, op0
, op1
, &x
))
358 wide_int max
= wi::max_value (TYPE_PRECISION (TREE_TYPE (op0
)), UNSIGNED
);
359 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
360 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
361 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
362 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
363 if (integer_zerop (x
))
366 code
= (code
== LT_EXPR
|| code
== LE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
368 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
369 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
370 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
371 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
372 else if (wi::to_wide (x
) == max
- 1)
375 op1
= wide_int_to_tree (TREE_TYPE (op0
), 0);
376 code
= (code
== GT_EXPR
|| code
== GE_EXPR
) ? EQ_EXPR
: NE_EXPR
;
380 value_range vro
, vri
;
381 tree type
= TREE_TYPE (op0
);
382 if (code
== GT_EXPR
|| code
== GE_EXPR
)
385 wi::to_wide (TYPE_MIN_VALUE (type
)),
386 wi::to_wide (x
), VR_ANTI_RANGE
);
388 wi::to_wide (TYPE_MIN_VALUE (type
)),
391 else if (code
== LT_EXPR
|| code
== LE_EXPR
)
394 wi::to_wide (TYPE_MIN_VALUE (type
)),
397 wi::to_wide (TYPE_MIN_VALUE (type
)),
404 if (!query
->range_of_expr (vr0
, op0
, stmt
))
405 vr0
.set_varying (TREE_TYPE (op0
));
406 /* If vro, the range for OP0 to pass the overflow test, has
407 no intersection with *vr0, OP0's known range, then the
408 overflow test can't pass, so return the node for false.
409 If it is the inverted range, vri, that has no
410 intersection, then the overflow test must pass, so return
411 the node for true. In other cases, we could proceed with
412 a simplified condition comparing OP0 and X, with LE_EXPR
413 for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
414 the comments next to the enclosing if suggest it's not
415 generally profitable to do so. */
417 if (vro
.undefined_p ())
418 return boolean_false_node
;
420 if (vri
.undefined_p ())
421 return boolean_true_node
;
425 if ((ret
= fold_cond_with_ops (code
, op0
, op1
, stmt
)))
430 /* Visit conditional statement STMT. If we can determine which edge
431 will be taken out of STMT's basic block, record it in
432 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
435 simplify_using_ranges::legacy_fold_cond (gcond
*stmt
, edge
*taken_edge_p
)
439 *taken_edge_p
= NULL
;
441 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
446 fprintf (dump_file
, "\nVisiting conditional with predicate: ");
447 print_gimple_stmt (dump_file
, stmt
, 0);
448 fprintf (dump_file
, "\nWith known ranges\n");
450 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
452 fprintf (dump_file
, "\t");
453 print_generic_expr (dump_file
, use
);
454 fprintf (dump_file
, ": ");
455 Value_Range
r (TREE_TYPE (use
));
456 query
->range_of_expr (r
, use
, stmt
);
460 fprintf (dump_file
, "\n");
463 val
= legacy_fold_cond_overflow (stmt
);
465 *taken_edge_p
= find_taken_edge (gimple_bb (stmt
), val
);
467 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
469 fprintf (dump_file
, "\nPredicate evaluates to: ");
470 if (val
== NULL_TREE
)
471 fprintf (dump_file
, "DON'T KNOW\n");
473 print_generic_stmt (dump_file
, val
);
477 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
478 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
479 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
480 Returns true if the default label is not needed. */
483 find_case_label_ranges (gswitch
*stmt
, const value_range
*vr
,
484 size_t *min_idx1
, size_t *max_idx1
,
485 size_t *min_idx2
, size_t *max_idx2
)
488 unsigned int n
= gimple_switch_num_labels (stmt
);
490 tree case_low
, case_high
;
492 value_range_kind kind
= get_legacy_range (*vr
, min
, max
);
494 gcc_checking_assert (!vr
->varying_p () && !vr
->undefined_p ());
496 take_default
= !find_case_label_range (stmt
, min
, max
, &i
, &j
);
498 /* Set second range to empty. */
502 if (kind
== VR_RANGE
)
506 return !take_default
;
509 /* Set first range to all case labels. */
516 /* Make sure all the values of case labels [i , j] are contained in
518 case_low
= CASE_LOW (gimple_switch_label (stmt
, i
));
519 case_high
= CASE_HIGH (gimple_switch_label (stmt
, j
));
520 if (tree_int_cst_compare (case_low
, min
) < 0)
522 if (case_high
!= NULL_TREE
523 && tree_int_cst_compare (max
, case_high
) < 0)
529 /* If the range spans case labels [i, j], the corresponding anti-range spans
530 the labels [1, i - 1] and [j + 1, n - 1]. */
556 /* Simplify boolean operations if the source is known
557 to be already a boolean. */
559 simplify_using_ranges::simplify_truth_ops_using_ranges
560 (gimple_stmt_iterator
*gsi
,
563 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
565 bool need_conversion
;
567 /* We handle only !=/== case here. */
568 gcc_assert (rhs_code
== EQ_EXPR
|| rhs_code
== NE_EXPR
);
570 op0
= gimple_assign_rhs1 (stmt
);
571 if (!op_with_boolean_value_range_p (op0
, stmt
))
574 op1
= gimple_assign_rhs2 (stmt
);
575 if (!op_with_boolean_value_range_p (op1
, stmt
))
578 /* Reduce number of cases to handle to NE_EXPR. As there is no
579 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
580 if (rhs_code
== EQ_EXPR
)
582 if (TREE_CODE (op1
) == INTEGER_CST
)
583 op1
= int_const_binop (BIT_XOR_EXPR
, op1
,
584 build_int_cst (TREE_TYPE (op1
), 1));
589 lhs
= gimple_assign_lhs (stmt
);
591 = !useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
));
593 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
595 && !TYPE_UNSIGNED (TREE_TYPE (op0
))
596 && TYPE_PRECISION (TREE_TYPE (op0
)) == 1
597 && TYPE_PRECISION (TREE_TYPE (lhs
)) > 1)
600 /* For A != 0 we can substitute A itself. */
601 if (integer_zerop (op1
))
602 gimple_assign_set_rhs_with_ops (gsi
,
604 ? NOP_EXPR
: TREE_CODE (op0
), op0
);
605 /* For A != B we substitute A ^ B. Either with conversion. */
606 else if (need_conversion
)
608 tree tem
= make_ssa_name (TREE_TYPE (op0
));
610 = gimple_build_assign (tem
, BIT_XOR_EXPR
, op0
, op1
);
611 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
612 if (INTEGRAL_TYPE_P (TREE_TYPE (tem
))
613 && TYPE_PRECISION (TREE_TYPE (tem
)) > 1)
615 value_range
vr (TREE_TYPE (tem
),
616 wi::zero (TYPE_PRECISION (TREE_TYPE (tem
))),
617 wi::one (TYPE_PRECISION (TREE_TYPE (tem
))));
618 set_range_info (tem
, vr
);
620 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, tem
);
624 gimple_assign_set_rhs_with_ops (gsi
, BIT_XOR_EXPR
, op0
, op1
);
625 update_stmt (gsi_stmt (*gsi
));
626 fold_stmt (gsi
, follow_single_use_edges
);
631 /* Simplify a division or modulo operator to a right shift or bitwise and
632 if the first operand is unsigned or is greater than zero and the second
633 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
634 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
635 optimize it into just op0 if op0's range is known to be a subset of
636 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
640 simplify_using_ranges::simplify_div_or_mod_using_ranges
641 (gimple_stmt_iterator
*gsi
,
644 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
646 tree op0
= gimple_assign_rhs1 (stmt
);
647 tree op1
= gimple_assign_rhs2 (stmt
);
648 tree op0min
= NULL_TREE
, op0max
= NULL_TREE
;
652 if (TREE_CODE (op0
) == INTEGER_CST
)
659 if (!query
->range_of_expr (vr
, op0
, stmt
))
660 vr
.set_varying (TREE_TYPE (op0
));
661 if (!vr
.varying_p () && !vr
.undefined_p ())
663 tree type
= vr
.type ();
664 op0min
= wide_int_to_tree (type
, vr
.lower_bound ());
665 op0max
= wide_int_to_tree (type
, vr
.upper_bound ());
669 if (rhs_code
== TRUNC_MOD_EXPR
670 && TREE_CODE (op1
) == SSA_NAME
)
673 if (!query
->range_of_expr (vr1
, op1
, stmt
))
674 vr1
.set_varying (TREE_TYPE (op1
));
675 if (!vr1
.varying_p () && !vr1
.undefined_p ())
676 op1min
= wide_int_to_tree (vr1
.type (), vr1
.lower_bound ());
678 if (rhs_code
== TRUNC_MOD_EXPR
679 && TREE_CODE (op1min
) == INTEGER_CST
680 && tree_int_cst_sgn (op1min
) == 1
682 && tree_int_cst_lt (op0max
, op1min
))
684 if (TYPE_UNSIGNED (TREE_TYPE (op0
))
685 || tree_int_cst_sgn (op0min
) >= 0
686 || tree_int_cst_lt (fold_unary (NEGATE_EXPR
, TREE_TYPE (op1min
), op1min
),
689 /* If op0 already has the range op0 % op1 has,
690 then TRUNC_MOD_EXPR won't change anything. */
691 gimple_assign_set_rhs_from_tree (gsi
, op0
);
696 if (TREE_CODE (op0
) != SSA_NAME
)
699 if (!integer_pow2p (op1
))
701 /* X % -Y can be only optimized into X % Y either if
702 X is not INT_MIN, or Y is not -1. Fold it now, as after
703 remove_range_assertions the range info might be not available
705 if (rhs_code
== TRUNC_MOD_EXPR
706 && fold_stmt (gsi
, follow_single_use_edges
))
711 if (TYPE_UNSIGNED (TREE_TYPE (op0
)))
712 val
= integer_one_node
;
715 tree zero
= build_zero_cst (TREE_TYPE (op0
));
716 val
= fold_cond_with_ops (GE_EXPR
, op0
, zero
, stmt
);
719 if (val
&& integer_onep (val
))
723 if (rhs_code
== TRUNC_DIV_EXPR
)
725 t
= build_int_cst (integer_type_node
, tree_log2 (op1
));
726 gimple_assign_set_rhs_code (stmt
, RSHIFT_EXPR
);
727 gimple_assign_set_rhs1 (stmt
, op0
);
728 gimple_assign_set_rhs2 (stmt
, t
);
732 t
= build_int_cst (TREE_TYPE (op1
), 1);
733 t
= int_const_binop (MINUS_EXPR
, op1
, t
);
734 t
= fold_convert (TREE_TYPE (op0
), t
);
736 gimple_assign_set_rhs_code (stmt
, BIT_AND_EXPR
);
737 gimple_assign_set_rhs1 (stmt
, op0
);
738 gimple_assign_set_rhs2 (stmt
, t
);
742 fold_stmt (gsi
, follow_single_use_edges
);
749 /* Simplify a min or max if the ranges of the two operands are
750 disjoint. Return true if we do simplify. */
753 simplify_using_ranges::simplify_min_or_max_using_ranges
754 (gimple_stmt_iterator
*gsi
,
757 tree op0
= gimple_assign_rhs1 (stmt
);
758 tree op1
= gimple_assign_rhs2 (stmt
);
761 val
= fold_cond_with_ops (LE_EXPR
, op0
, op1
, stmt
);
763 val
= fold_cond_with_ops (LT_EXPR
, op0
, op1
, stmt
);
767 /* VAL == TRUE -> OP0 < or <= op1
768 VAL == FALSE -> OP0 > or >= op1. */
769 tree res
= ((gimple_assign_rhs_code (stmt
) == MAX_EXPR
)
770 == integer_zerop (val
)) ? op0
: op1
;
771 gimple_assign_set_rhs_from_tree (gsi
, res
);
778 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
779 ABS_EXPR. If the operand is <= 0, then simplify the
780 ABS_EXPR into a NEGATE_EXPR. */
783 simplify_using_ranges::simplify_abs_using_ranges (gimple_stmt_iterator
*gsi
,
786 tree op
= gimple_assign_rhs1 (stmt
);
787 tree zero
= build_zero_cst (TREE_TYPE (op
));
788 tree val
= fold_cond_with_ops (LE_EXPR
, op
, zero
, stmt
);
792 /* The range is neither <= 0 nor > 0. Now see if it is
793 either < 0 or >= 0. */
794 val
= fold_cond_with_ops (LT_EXPR
, op
, zero
, stmt
);
798 gimple_assign_set_rhs1 (stmt
, op
);
799 if (integer_zerop (val
))
800 gimple_assign_set_rhs_code (stmt
, SSA_NAME
);
802 gimple_assign_set_rhs_code (stmt
, NEGATE_EXPR
);
804 fold_stmt (gsi
, follow_single_use_edges
);
810 /* value_range wrapper for wi_set_zero_nonzero_bits.
812 Return TRUE if VR was a constant range and we were able to compute
816 vr_set_zero_nonzero_bits (const tree expr_type
,
818 wide_int
*may_be_nonzero
,
819 wide_int
*must_be_nonzero
)
821 if (vr
->varying_p () || vr
->undefined_p ())
823 *may_be_nonzero
= wi::minus_one (TYPE_PRECISION (expr_type
));
824 *must_be_nonzero
= wi::zero (TYPE_PRECISION (expr_type
));
827 wi_set_zero_nonzero_bits (expr_type
, vr
->lower_bound (), vr
->upper_bound (),
828 *may_be_nonzero
, *must_be_nonzero
);
832 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
833 If all the bits that are being cleared by & are already
834 known to be zero from VR, or all the bits that are being
835 set by | are already known to be one from VR, the bit
836 operation is redundant. */
839 simplify_using_ranges::simplify_bit_ops_using_ranges
840 (gimple_stmt_iterator
*gsi
,
843 tree op0
= gimple_assign_rhs1 (stmt
);
844 tree op1
= gimple_assign_rhs2 (stmt
);
846 value_range vr0
, vr1
;
847 wide_int may_be_nonzero0
, may_be_nonzero1
;
848 wide_int must_be_nonzero0
, must_be_nonzero1
;
851 if (!query
->range_of_expr (vr0
, op0
, stmt
)
852 || vr0
.undefined_p ())
854 if (!query
->range_of_expr (vr1
, op1
, stmt
)
855 || vr1
.undefined_p ())
858 if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0
), &vr0
, &may_be_nonzero0
,
861 if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1
), &vr1
, &may_be_nonzero1
,
865 switch (gimple_assign_rhs_code (stmt
))
868 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
874 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
882 mask
= wi::bit_and_not (may_be_nonzero0
, must_be_nonzero1
);
888 mask
= wi::bit_and_not (may_be_nonzero1
, must_be_nonzero0
);
902 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (op
), op
);
903 update_stmt (gsi_stmt (*gsi
));
907 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
908 a known value range VR.
910 If there is one and only one value which will satisfy the
911 conditional, then return that value. Else return NULL.
913 If signed overflow must be undefined for the value to satisfy
914 the conditional, then set *STRICT_OVERFLOW_P to true. */
917 test_for_singularity (enum tree_code cond_code
, tree op0
,
918 tree op1
, const value_range
*vr
)
923 /* Extract minimum/maximum values which satisfy the conditional as it was
925 if (cond_code
== LE_EXPR
|| cond_code
== LT_EXPR
)
927 min
= TYPE_MIN_VALUE (TREE_TYPE (op0
));
930 if (cond_code
== LT_EXPR
)
932 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
933 max
= fold_build2 (MINUS_EXPR
, TREE_TYPE (op0
), max
, one
);
934 /* Signal to compare_values_warnv this expr doesn't overflow. */
936 suppress_warning (max
, OPT_Woverflow
);
939 else if (cond_code
== GE_EXPR
|| cond_code
== GT_EXPR
)
941 max
= TYPE_MAX_VALUE (TREE_TYPE (op0
));
944 if (cond_code
== GT_EXPR
)
946 tree one
= build_int_cst (TREE_TYPE (op0
), 1);
947 min
= fold_build2 (PLUS_EXPR
, TREE_TYPE (op0
), min
, one
);
948 /* Signal to compare_values_warnv this expr doesn't overflow. */
950 suppress_warning (min
, OPT_Woverflow
);
954 /* Now refine the minimum and maximum values using any
955 value range information we have for op0. */
958 tree type
= TREE_TYPE (op0
);
959 tree tmin
= wide_int_to_tree (type
, vr
->lower_bound ());
960 tree tmax
= wide_int_to_tree (type
, vr
->upper_bound ());
961 if (compare_values (tmin
, min
) == 1)
963 if (compare_values (tmax
, max
) == -1)
966 /* If the new min/max values have converged to a single value,
967 then there is only one value which can satisfy the condition,
968 return that value. */
969 if (operand_equal_p (min
, max
, 0) && is_gimple_min_invariant (min
))
975 /* Return whether the value range *VR fits in an integer type specified
976 by PRECISION and UNSIGNED_P. */
979 range_fits_type_p (const irange
*vr
,
980 unsigned dest_precision
, signop dest_sgn
)
983 unsigned src_precision
;
987 /* We can only handle integral and pointer types. */
988 src_type
= vr
->type ();
989 if (!INTEGRAL_TYPE_P (src_type
)
990 && !POINTER_TYPE_P (src_type
))
993 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
994 and so is an identity transform. */
995 src_precision
= TYPE_PRECISION (vr
->type ());
996 src_sgn
= TYPE_SIGN (src_type
);
997 if ((src_precision
< dest_precision
998 && !(dest_sgn
== UNSIGNED
&& src_sgn
== SIGNED
))
999 || (src_precision
== dest_precision
&& src_sgn
== dest_sgn
))
1002 /* Now we can only handle ranges with constant bounds. */
1003 if (vr
->undefined_p () || vr
->varying_p ())
1006 wide_int vrmin
= vr
->lower_bound ();
1007 wide_int vrmax
= vr
->upper_bound ();
1009 /* For sign changes, the MSB of the wide_int has to be clear.
1010 An unsigned value with its MSB set cannot be represented by
1011 a signed wide_int, while a negative value cannot be represented
1012 by an unsigned wide_int. */
1013 if (src_sgn
!= dest_sgn
1014 && (wi::lts_p (vrmin
, 0) || wi::lts_p (vrmax
, 0)))
1017 /* Then we can perform the conversion on both ends and compare
1018 the result for equality. */
1019 signop sign
= TYPE_SIGN (vr
->type ());
1020 tem
= wi::ext (widest_int::from (vrmin
, sign
), dest_precision
, dest_sgn
);
1021 if (tem
!= widest_int::from (vrmin
, sign
))
1023 tem
= wi::ext (widest_int::from (vrmax
, sign
), dest_precision
, dest_sgn
);
1024 if (tem
!= widest_int::from (vrmax
, sign
))
1030 // Clear edge E of EDGE_EXECUTABLE (it is unexecutable). If it wasn't
1031 // previously clear, propagate to successor blocks if appropriate.
1034 simplify_using_ranges::set_and_propagate_unexecutable (edge e
)
1036 // If not_executable is already set, we're done.
1037 // This works in the absence of a flag as well.
1038 if ((e
->flags
& m_not_executable_flag
) == m_not_executable_flag
)
1041 e
->flags
|= m_not_executable_flag
;
1042 m_flag_set_edges
.safe_push (e
);
1044 // Check if the destination block needs to propagate the property.
1045 basic_block bb
= e
->dest
;
1047 // If any incoming edge is executable, we are done.
1049 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1050 if ((e
->flags
& m_not_executable_flag
) == 0)
1053 // This block is also unexecutable, propagate to all exit edges as well.
1054 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1055 set_and_propagate_unexecutable (e
);
1058 /* If COND can be folded entirely as TRUE or FALSE, rewrite the
1059 conditional as such, and return TRUE. */
1062 simplify_using_ranges::fold_cond (gcond
*cond
)
1065 if (query
->range_of_stmt (r
, cond
) && r
.singleton_p ())
1067 // COND has already been folded if arguments are constant.
1068 if (TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
1069 && TREE_CODE (gimple_cond_rhs (cond
)) != SSA_NAME
)
1073 fprintf (dump_file
, "Folding predicate ");
1074 print_gimple_expr (dump_file
, cond
, 0);
1075 fprintf (dump_file
, " to ");
1077 edge e0
= EDGE_SUCC (gimple_bb (cond
), 0);
1078 edge e1
= EDGE_SUCC (gimple_bb (cond
), 1);
1082 fprintf (dump_file
, "0\n");
1083 gimple_cond_make_false (cond
);
1084 if (e0
->flags
& EDGE_TRUE_VALUE
)
1085 set_and_propagate_unexecutable (e0
);
1087 set_and_propagate_unexecutable (e1
);
1092 fprintf (dump_file
, "1\n");
1093 gimple_cond_make_true (cond
);
1094 if (e0
->flags
& EDGE_FALSE_VALUE
)
1095 set_and_propagate_unexecutable (e0
);
1097 set_and_propagate_unexecutable (e1
);
1103 // FIXME: Audit the code below and make sure it never finds anything.
1105 legacy_fold_cond (cond
, &taken_edge
);
1109 if (taken_edge
->flags
& EDGE_TRUE_VALUE
)
1111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1112 fprintf (dump_file
, "\nVRP Predicate evaluates to: 1\n");
1113 gimple_cond_make_true (cond
);
1115 else if (taken_edge
->flags
& EDGE_FALSE_VALUE
)
1117 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1118 fprintf (dump_file
, "\nVRP Predicate evaluates to: 0\n");
1119 gimple_cond_make_false (cond
);
1129 /* Simplify a conditional using a relational operator to an equality
1130 test if the range information indicates only one value can satisfy
1131 the original conditional. */
1134 simplify_using_ranges::simplify_cond_using_ranges_1 (gcond
*stmt
)
1136 tree op0
= gimple_cond_lhs (stmt
);
1137 tree op1
= gimple_cond_rhs (stmt
);
1138 enum tree_code cond_code
= gimple_cond_code (stmt
);
1140 if (fold_cond (stmt
))
1143 if (simplify_compare_using_ranges_1 (cond_code
, op0
, op1
, stmt
))
1147 fprintf (dump_file
, "Simplified relational ");
1148 print_gimple_stmt (dump_file
, stmt
, 0);
1149 fprintf (dump_file
, " into ");
1152 gimple_cond_set_code (stmt
, cond_code
);
1153 gimple_cond_set_lhs (stmt
, op0
);
1154 gimple_cond_set_rhs (stmt
, op1
);
1160 print_gimple_stmt (dump_file
, stmt
, 0);
1161 fprintf (dump_file
, "\n");
1168 /* Like simplify_cond_using_ranges_1 but for assignments rather
1169 than GIMPLE_COND. */
1172 simplify_using_ranges::simplify_compare_assign_using_ranges_1
1173 (gimple_stmt_iterator
*gsi
,
1176 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1177 tree op0
= gimple_assign_rhs1 (stmt
);
1178 tree op1
= gimple_assign_rhs2 (stmt
);
1179 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
1180 bool happened
= false;
1182 if (simplify_compare_using_ranges_1 (code
, op0
, op1
, stmt
))
1186 fprintf (dump_file
, "Simplified relational ");
1187 print_gimple_stmt (dump_file
, stmt
, 0);
1188 fprintf (dump_file
, " into ");
1191 gimple_assign_set_rhs_code (stmt
, code
);
1192 gimple_assign_set_rhs1 (stmt
, op0
);
1193 gimple_assign_set_rhs2 (stmt
, op1
);
1199 print_gimple_stmt (dump_file
, stmt
, 0);
1200 fprintf (dump_file
, "\n");
1205 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
1206 if the RHS is zero or one, and the LHS are known to be boolean
1208 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
1209 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
1210 && simplify_truth_ops_using_ranges (gsi
, stmt
))
1216 /* Try to simplify OP0 COND_CODE OP1 using a relational operator to an
1217 equality test if the range information indicates only one value can
1218 satisfy the original conditional. */
1221 simplify_using_ranges::simplify_compare_using_ranges_1 (tree_code
&cond_code
, tree
&op0
, tree
&op1
, gimple
*stmt
)
1223 bool happened
= false;
1224 if (cond_code
!= NE_EXPR
1225 && cond_code
!= EQ_EXPR
1226 && TREE_CODE (op0
) == SSA_NAME
1227 && INTEGRAL_TYPE_P (TREE_TYPE (op0
))
1228 && is_gimple_min_invariant (op1
))
1232 if (!query
->range_of_expr (vr
, op0
, stmt
))
1233 vr
.set_undefined ();
1235 /* If we have range information for OP0, then we might be
1236 able to simplify this conditional. */
1237 if (!vr
.undefined_p () && !vr
.varying_p ())
1239 tree new_tree
= test_for_singularity (cond_code
, op0
, op1
, &vr
);
1242 cond_code
= EQ_EXPR
;
1247 /* Try again after inverting the condition. We only deal
1248 with integral types here, so no need to worry about
1249 issues with inverting FP comparisons. */
1250 new_tree
= test_for_singularity
1251 (invert_tree_comparison (cond_code
, false),
1255 cond_code
= NE_EXPR
;
1261 // Try to simplify casted conditions.
1262 if (simplify_casted_compare (cond_code
, op0
, op1
))
1267 /* Simplify OP0 code OP1 when OP1 is a constant and OP0 was a SSA_NAME
1268 defined by a type conversion. Replacing OP0 with RHS of the type conversion.
1269 Doing so makes the conversion dead which helps subsequent passes. */
1272 simplify_using_ranges::simplify_casted_compare (tree_code
&, tree
&op0
, tree
&op1
)
1275 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
1276 see if OP0 was set by a type conversion where the source of
1277 the conversion is another SSA_NAME with a range that fits
1278 into the range of OP0's type.
1280 If so, the conversion is redundant as the earlier SSA_NAME can be
1281 used for the comparison directly if we just massage the constant in the
1283 if (TREE_CODE (op0
) == SSA_NAME
1284 && TREE_CODE (op1
) == INTEGER_CST
)
1286 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op0
);
1289 if (!is_gimple_assign (def_stmt
))
1292 switch (gimple_assign_rhs_code (def_stmt
))
1295 innerop
= gimple_assign_rhs1 (def_stmt
);
1297 case VIEW_CONVERT_EXPR
:
1298 innerop
= TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0);
1299 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
)))
1306 if (TREE_CODE (innerop
) == SSA_NAME
1307 && !POINTER_TYPE_P (TREE_TYPE (innerop
))
1308 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
)
1309 && desired_pro_or_demotion_p (TREE_TYPE (innerop
), TREE_TYPE (op0
)))
1313 if (query
->range_of_expr (vr
, innerop
)
1315 && !vr
.undefined_p ()
1316 && range_fits_type_p (&vr
,
1317 TYPE_PRECISION (TREE_TYPE (op0
)),
1318 TYPE_SIGN (TREE_TYPE (op0
)))
1319 && int_fits_type_p (op1
, TREE_TYPE (innerop
)))
1321 tree newconst
= fold_convert (TREE_TYPE (innerop
), op1
);
1331 /* Simplify a switch statement using the value range of the switch
1335 simplify_using_ranges::simplify_switch_using_ranges (gswitch
*stmt
)
1337 tree op
= gimple_switch_index (stmt
);
1342 size_t i
= 0, j
= 0, n
, n2
;
1345 size_t k
= 1, l
= 0;
1347 if (TREE_CODE (op
) == SSA_NAME
)
1349 if (!query
->range_of_expr (vr
, op
, stmt
)
1350 || vr
.varying_p () || vr
.undefined_p ())
1353 /* Find case label for min/max of the value range. */
1354 take_default
= !find_case_label_ranges (stmt
, &vr
, &i
, &j
, &k
, &l
);
1356 else if (TREE_CODE (op
) == INTEGER_CST
)
1358 take_default
= !find_case_label_index (stmt
, 1, op
, &i
);
1372 n
= gimple_switch_num_labels (stmt
);
1374 /* We can truncate the case label ranges that partially overlap with OP's
1376 size_t min_idx
= 1, max_idx
= 0;
1378 value_range_kind kind
= get_legacy_range (vr
, min
, max
);
1379 if (!vr
.undefined_p ())
1380 find_case_label_range (stmt
, min
, max
, &min_idx
, &max_idx
);
1381 if (min_idx
<= max_idx
)
1383 tree min_label
= gimple_switch_label (stmt
, min_idx
);
1384 tree max_label
= gimple_switch_label (stmt
, max_idx
);
1386 /* Avoid changing the type of the case labels when truncating. */
1387 tree case_label_type
= TREE_TYPE (CASE_LOW (min_label
));
1388 tree vr_min
= fold_convert (case_label_type
, min
);
1389 tree vr_max
= fold_convert (case_label_type
, max
);
1391 if (kind
== VR_RANGE
)
1393 /* If OP's value range is [2,8] and the low label range is
1394 0 ... 3, truncate the label's range to 2 .. 3. */
1395 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
1396 && CASE_HIGH (min_label
) != NULL_TREE
1397 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
1398 CASE_LOW (min_label
) = vr_min
;
1400 /* If OP's value range is [2,8] and the high label range is
1401 7 ... 10, truncate the label's range to 7 .. 8. */
1402 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
1403 && CASE_HIGH (max_label
) != NULL_TREE
1404 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
1405 CASE_HIGH (max_label
) = vr_max
;
1407 else if (kind
== VR_ANTI_RANGE
)
1409 tree one_cst
= build_one_cst (case_label_type
);
1411 if (min_label
== max_label
)
1413 /* If OP's value range is ~[7,8] and the label's range is
1414 7 ... 10, truncate the label's range to 9 ... 10. */
1415 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) == 0
1416 && CASE_HIGH (min_label
) != NULL_TREE
1417 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) > 0)
1418 CASE_LOW (min_label
)
1419 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
1421 /* If OP's value range is ~[7,8] and the label's range is
1422 5 ... 8, truncate the label's range to 5 ... 6. */
1423 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
1424 && CASE_HIGH (min_label
) != NULL_TREE
1425 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_max
) == 0)
1426 CASE_HIGH (min_label
)
1427 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
1431 /* If OP's value range is ~[2,8] and the low label range is
1432 0 ... 3, truncate the label's range to 0 ... 1. */
1433 if (tree_int_cst_compare (CASE_LOW (min_label
), vr_min
) < 0
1434 && CASE_HIGH (min_label
) != NULL_TREE
1435 && tree_int_cst_compare (CASE_HIGH (min_label
), vr_min
) >= 0)
1436 CASE_HIGH (min_label
)
1437 = int_const_binop (MINUS_EXPR
, vr_min
, one_cst
);
1439 /* If OP's value range is ~[2,8] and the high label range is
1440 7 ... 10, truncate the label's range to 9 ... 10. */
1441 if (tree_int_cst_compare (CASE_LOW (max_label
), vr_max
) <= 0
1442 && CASE_HIGH (max_label
) != NULL_TREE
1443 && tree_int_cst_compare (CASE_HIGH (max_label
), vr_max
) > 0)
1444 CASE_LOW (max_label
)
1445 = int_const_binop (PLUS_EXPR
, vr_max
, one_cst
);
1449 /* Canonicalize singleton case ranges. */
1450 if (tree_int_cst_equal (CASE_LOW (min_label
), CASE_HIGH (min_label
)))
1451 CASE_HIGH (min_label
) = NULL_TREE
;
1452 if (tree_int_cst_equal (CASE_LOW (max_label
), CASE_HIGH (max_label
)))
1453 CASE_HIGH (max_label
) = NULL_TREE
;
1456 /* We can also eliminate case labels that lie completely outside OP's value
1459 /* Bail out if this is just all edges taken. */
1465 /* Build a new vector of taken case labels. */
1466 vec2
= make_tree_vec (j
- i
+ 1 + l
- k
+ 1 + (int)take_default
);
1469 /* Add the default edge, if necessary. */
1471 TREE_VEC_ELT (vec2
, n2
++) = gimple_switch_default_label (stmt
);
1473 for (; i
<= j
; ++i
, ++n2
)
1474 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, i
);
1476 for (; k
<= l
; ++k
, ++n2
)
1477 TREE_VEC_ELT (vec2
, n2
) = gimple_switch_label (stmt
, k
);
1479 /* Mark needed edges. */
1480 for (i
= 0; i
< n2
; ++i
)
1482 e
= find_edge (gimple_bb (stmt
),
1483 label_to_block (cfun
,
1484 CASE_LABEL (TREE_VEC_ELT (vec2
, i
))));
1485 e
->aux
= (void *)-1;
1488 /* Queue not needed edges for later removal. */
1489 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1491 if (e
->aux
== (void *)-1)
1497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1499 fprintf (dump_file
, "removing unreachable case label\n");
1501 to_remove_edges
.safe_push (e
);
1502 set_and_propagate_unexecutable (e
);
1503 e
->flags
&= ~EDGE_EXECUTABLE
;
1504 e
->flags
|= EDGE_IGNORE
;
1507 /* And queue an update for the stmt. */
1510 to_update_switch_stmts
.safe_push (su
);
1515 simplify_using_ranges::cleanup_edges_and_switches (void)
1521 /* Clear any edges marked as not executable. */
1522 if (m_not_executable_flag
)
1524 FOR_EACH_VEC_ELT (m_flag_set_edges
, i
, e
)
1525 e
->flags
&= ~m_not_executable_flag
;
1527 /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
1528 CFG in a broken state and requires a cfg_cleanup run. */
1529 FOR_EACH_VEC_ELT (to_remove_edges
, i
, e
)
1532 /* Update SWITCH_EXPR case label vector. */
1533 FOR_EACH_VEC_ELT (to_update_switch_stmts
, i
, su
)
1536 size_t n
= TREE_VEC_LENGTH (su
->vec
);
1538 gimple_switch_set_num_labels (su
->stmt
, n
);
1539 for (j
= 0; j
< n
; j
++)
1540 gimple_switch_set_label (su
->stmt
, j
, TREE_VEC_ELT (su
->vec
, j
));
1541 /* As we may have replaced the default label with a regular one
1542 make sure to make it a real default label again. This ensures
1543 optimal expansion. */
1544 label
= gimple_switch_label (su
->stmt
, 0);
1545 CASE_LOW (label
) = NULL_TREE
;
1546 CASE_HIGH (label
) = NULL_TREE
;
1549 if (!to_remove_edges
.is_empty ())
1551 free_dominance_info (CDI_DOMINATORS
);
1552 loops_state_set (LOOPS_NEED_FIXUP
);
1555 to_remove_edges
.release ();
1556 to_update_switch_stmts
.release ();
1559 /* Simplify an integral conversion from an SSA name in STMT. */
1562 simplify_conversion_using_ranges (gimple_stmt_iterator
*gsi
, gimple
*stmt
)
1564 tree innerop
, middleop
, finaltype
;
1566 signop inner_sgn
, middle_sgn
, final_sgn
;
1567 unsigned inner_prec
, middle_prec
, final_prec
;
1568 widest_int innermin
, innermed
, innermax
, middlemin
, middlemed
, middlemax
;
1570 finaltype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1571 if (!INTEGRAL_TYPE_P (finaltype
))
1573 middleop
= gimple_assign_rhs1 (stmt
);
1574 def_stmt
= SSA_NAME_DEF_STMT (middleop
);
1575 if (!is_gimple_assign (def_stmt
)
1576 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
1578 innerop
= gimple_assign_rhs1 (def_stmt
);
1579 if (TREE_CODE (innerop
) != SSA_NAME
1580 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop
))
1583 /* Get the value-range of the inner operand. Use global ranges in
1584 case innerop was created during substitute-and-fold. */
1585 wide_int imin
, imax
;
1587 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop
)))
1589 get_range_query (cfun
)->range_of_expr (vr
, innerop
, stmt
);
1590 if (vr
.undefined_p () || vr
.varying_p ())
1592 innermin
= widest_int::from (vr
.lower_bound (), TYPE_SIGN (TREE_TYPE (innerop
)));
1593 innermax
= widest_int::from (vr
.upper_bound (), TYPE_SIGN (TREE_TYPE (innerop
)));
1595 /* Simulate the conversion chain to check if the result is equal if
1596 the middle conversion is removed. */
1597 inner_prec
= TYPE_PRECISION (TREE_TYPE (innerop
));
1598 middle_prec
= TYPE_PRECISION (TREE_TYPE (middleop
));
1599 final_prec
= TYPE_PRECISION (finaltype
);
1601 /* If the first conversion is not injective, the second must not
1603 if (wi::gtu_p (innermax
- innermin
,
1604 wi::mask
<widest_int
> (middle_prec
, false))
1605 && middle_prec
< final_prec
)
1607 /* We also want a medium value so that we can track the effect that
1608 narrowing conversions with sign change have. */
1609 inner_sgn
= TYPE_SIGN (TREE_TYPE (innerop
));
1610 if (inner_sgn
== UNSIGNED
)
1611 innermed
= wi::shifted_mask
<widest_int
> (1, inner_prec
- 1, false);
1614 if (wi::cmp (innermin
, innermed
, inner_sgn
) >= 0
1615 || wi::cmp (innermed
, innermax
, inner_sgn
) >= 0)
1616 innermed
= innermin
;
1618 middle_sgn
= TYPE_SIGN (TREE_TYPE (middleop
));
1619 middlemin
= wi::ext (innermin
, middle_prec
, middle_sgn
);
1620 middlemed
= wi::ext (innermed
, middle_prec
, middle_sgn
);
1621 middlemax
= wi::ext (innermax
, middle_prec
, middle_sgn
);
1623 /* Require that the final conversion applied to both the original
1624 and the intermediate range produces the same result. */
1625 final_sgn
= TYPE_SIGN (finaltype
);
1626 if (wi::ext (middlemin
, final_prec
, final_sgn
)
1627 != wi::ext (innermin
, final_prec
, final_sgn
)
1628 || wi::ext (middlemed
, final_prec
, final_sgn
)
1629 != wi::ext (innermed
, final_prec
, final_sgn
)
1630 || wi::ext (middlemax
, final_prec
, final_sgn
)
1631 != wi::ext (innermax
, final_prec
, final_sgn
))
1634 gimple_assign_set_rhs1 (stmt
, innerop
);
1635 fold_stmt (gsi
, follow_single_use_edges
);
1639 /* Simplify a conversion from integral SSA name to float in STMT. */
1642 simplify_using_ranges::simplify_float_conversion_using_ranges
1643 (gimple_stmt_iterator
*gsi
,
1646 tree rhs1
= gimple_assign_rhs1 (stmt
);
1648 scalar_float_mode fltmode
1649 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
)));
1650 scalar_int_mode mode
;
1654 /* We can only handle constant ranges. */
1655 if (!query
->range_of_expr (vr
, rhs1
, stmt
)
1657 || vr
.undefined_p ())
1660 /* The code below doesn't work for large/huge _BitInt, nor is really
1661 needed for those, bitint lowering does use ranges already. */
1662 if (TREE_CODE (TREE_TYPE (rhs1
)) == BITINT_TYPE
1663 && TYPE_MODE (TREE_TYPE (rhs1
)) == BLKmode
)
1665 /* First check if we can use a signed type in place of an unsigned. */
1666 scalar_int_mode rhs_mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1
));
1667 if (TYPE_UNSIGNED (TREE_TYPE (rhs1
))
1668 && can_float_p (fltmode
, rhs_mode
, 0) != CODE_FOR_nothing
1669 && range_fits_type_p (&vr
, TYPE_PRECISION (TREE_TYPE (rhs1
)), SIGNED
))
1671 /* If we can do the conversion in the current input mode do nothing. */
1672 else if (can_float_p (fltmode
, rhs_mode
,
1673 TYPE_UNSIGNED (TREE_TYPE (rhs1
))) != CODE_FOR_nothing
)
1675 /* Otherwise search for a mode we can use, starting from the narrowest
1676 integer mode available. */
1679 mode
= NARROWEST_INT_MODE
;
1682 /* If we cannot do a signed conversion to float from mode
1683 or if the value-range does not fit in the signed type
1684 try with a wider mode. */
1685 if (can_float_p (fltmode
, mode
, 0) != CODE_FOR_nothing
1686 && range_fits_type_p (&vr
, GET_MODE_PRECISION (mode
), SIGNED
))
1689 /* But do not widen the input. Instead leave that to the
1690 optabs expansion code. */
1691 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
1692 || GET_MODE_PRECISION (mode
) > TYPE_PRECISION (TREE_TYPE (rhs1
)))
1697 /* It works, insert a truncation or sign-change before the
1698 float conversion. */
1699 tem
= make_ssa_name (build_nonstandard_integer_type
1700 (GET_MODE_PRECISION (mode
), 0));
1701 conv
= gimple_build_assign (tem
, NOP_EXPR
, rhs1
);
1702 gsi_insert_before (gsi
, conv
, GSI_SAME_STMT
);
1703 gimple_assign_set_rhs1 (stmt
, tem
);
1704 fold_stmt (gsi
, follow_single_use_edges
);
1709 /* Simplify an internal fn call using ranges if possible. */
1712 simplify_using_ranges::simplify_internal_call_using_ranges
1713 (gimple_stmt_iterator
*gsi
,
1716 enum tree_code subcode
;
1717 bool is_ubsan
= false;
1719 switch (gimple_call_internal_fn (stmt
))
1721 case IFN_UBSAN_CHECK_ADD
:
1722 subcode
= PLUS_EXPR
;
1725 case IFN_UBSAN_CHECK_SUB
:
1726 subcode
= MINUS_EXPR
;
1729 case IFN_UBSAN_CHECK_MUL
:
1730 subcode
= MULT_EXPR
;
1733 case IFN_ADD_OVERFLOW
:
1734 subcode
= PLUS_EXPR
;
1736 case IFN_SUB_OVERFLOW
:
1737 subcode
= MINUS_EXPR
;
1739 case IFN_MUL_OVERFLOW
:
1740 subcode
= MULT_EXPR
;
1746 tree op0
= gimple_call_arg (stmt
, 0);
1747 tree op1
= gimple_call_arg (stmt
, 1);
1751 type
= TREE_TYPE (op0
);
1752 if (VECTOR_TYPE_P (type
))
1755 else if (gimple_call_lhs (stmt
) == NULL_TREE
)
1758 type
= TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt
)));
1759 if (!check_for_binary_op_overflow (query
, subcode
, type
, op0
, op1
, &ovf
, stmt
)
1760 || (is_ubsan
&& ovf
))
1764 location_t loc
= gimple_location (stmt
);
1766 g
= gimple_build_assign (gimple_call_lhs (stmt
), subcode
, op0
, op1
);
1771 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
1772 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
1773 utype
= unsigned_type_for (type
);
1774 if (TREE_CODE (op0
) == INTEGER_CST
)
1775 op0
= fold_convert (utype
, op0
);
1776 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op0
)))
1778 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op0
);
1779 gimple_set_location (g
, loc
);
1780 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1781 op0
= gimple_assign_lhs (g
);
1783 if (TREE_CODE (op1
) == INTEGER_CST
)
1784 op1
= fold_convert (utype
, op1
);
1785 else if (!useless_type_conversion_p (utype
, TREE_TYPE (op1
)))
1787 g
= gimple_build_assign (make_ssa_name (utype
), NOP_EXPR
, op1
);
1788 gimple_set_location (g
, loc
);
1789 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1790 op1
= gimple_assign_lhs (g
);
1792 g
= gimple_build_assign (make_ssa_name (utype
), subcode
, op0
, op1
);
1793 gimple_set_location (g
, loc
);
1794 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1797 g
= gimple_build_assign (make_ssa_name (type
), NOP_EXPR
,
1798 gimple_assign_lhs (g
));
1799 gimple_set_location (g
, loc
);
1800 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1802 g
= gimple_build_assign (gimple_call_lhs (stmt
), COMPLEX_EXPR
,
1803 gimple_assign_lhs (g
),
1804 build_int_cst (type
, ovf
));
1806 gimple_set_location (g
, loc
);
1807 gsi_replace (gsi
, g
, false);
1811 /* Return true if VAR is a two-valued variable. Set a and b with the
1812 two-values when it is true. Return false otherwise. */
1815 simplify_using_ranges::two_valued_val_range_p (tree var
, tree
*a
, tree
*b
,
1819 if (!query
->range_of_expr (vr
, var
, s
))
1821 if (vr
.varying_p () || vr
.undefined_p ())
1824 if ((vr
.num_pairs () == 1 && vr
.upper_bound () - vr
.lower_bound () == 1)
1825 || (vr
.num_pairs () == 2
1826 && vr
.lower_bound (0) == vr
.upper_bound (0)
1827 && vr
.lower_bound (1) == vr
.upper_bound (1)))
1829 *a
= wide_int_to_tree (TREE_TYPE (var
), vr
.lower_bound ());
1830 *b
= wide_int_to_tree (TREE_TYPE (var
), vr
.upper_bound ());
1836 simplify_using_ranges::simplify_using_ranges (range_query
*query
,
1837 int not_executable_flag
)
1840 to_remove_edges
= vNULL
;
1841 to_update_switch_stmts
= vNULL
;
1842 m_not_executable_flag
= not_executable_flag
;
1843 m_flag_set_edges
= vNULL
;
1846 simplify_using_ranges::~simplify_using_ranges ()
1848 cleanup_edges_and_switches ();
1849 m_flag_set_edges
.release ();
1852 /* Simplify STMT using ranges if possible. */
1855 simplify_using_ranges::simplify (gimple_stmt_iterator
*gsi
)
1857 gcc_checking_assert (query
);
1859 gimple
*stmt
= gsi_stmt (*gsi
);
1860 if (is_gimple_assign (stmt
))
1862 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
1863 tree rhs1
= gimple_assign_rhs1 (stmt
);
1864 tree rhs2
= gimple_assign_rhs2 (stmt
);
1865 tree lhs
= gimple_assign_lhs (stmt
);
1866 tree val1
= NULL_TREE
, val2
= NULL_TREE
;
1867 use_operand_p use_p
;
1872 Where VAR is two-valued and LHS is used in GIMPLE_COND only
1874 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
1878 Where VAR is two-valued and LHS is used in GIMPLE_COND only
1880 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
1882 if (TREE_CODE_CLASS (rhs_code
) == tcc_binary
1883 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
1884 && ((TREE_CODE (rhs1
) == INTEGER_CST
1885 && TREE_CODE (rhs2
) == SSA_NAME
)
1886 || (TREE_CODE (rhs2
) == INTEGER_CST
1887 && TREE_CODE (rhs1
) == SSA_NAME
))
1888 && single_imm_use (lhs
, &use_p
, &use_stmt
)
1889 && gimple_code (use_stmt
) == GIMPLE_COND
)
1892 tree new_rhs1
= NULL_TREE
;
1893 tree new_rhs2
= NULL_TREE
;
1894 tree cmp_var
= NULL_TREE
;
1896 if (TREE_CODE (rhs2
) == SSA_NAME
1897 && two_valued_val_range_p (rhs2
, &val1
, &val2
, stmt
))
1899 /* Optimize RHS1 OP [VAL1, VAL2]. */
1900 new_rhs1
= int_const_binop (rhs_code
, rhs1
, val1
);
1901 new_rhs2
= int_const_binop (rhs_code
, rhs1
, val2
);
1904 else if (TREE_CODE (rhs1
) == SSA_NAME
1905 && two_valued_val_range_p (rhs1
, &val1
, &val2
, stmt
))
1907 /* Optimize [VAL1, VAL2] OP RHS2. */
1908 new_rhs1
= int_const_binop (rhs_code
, val1
, rhs2
);
1909 new_rhs2
= int_const_binop (rhs_code
, val2
, rhs2
);
1913 /* If we could not find two-vals or the optimzation is invalid as
1914 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
1915 if (new_rhs1
&& new_rhs2
)
1917 tree cond
= gimple_build (gsi
, true, GSI_SAME_STMT
,
1919 EQ_EXPR
, boolean_type_node
,
1921 gimple_assign_set_rhs_with_ops (gsi
,
1925 update_stmt (gsi_stmt (*gsi
));
1926 fold_stmt (gsi
, follow_single_use_edges
);
1931 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
)
1932 return simplify_compare_assign_using_ranges_1 (gsi
, stmt
);
1937 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1938 and BIT_AND_EXPR respectively if the first operand is greater
1939 than zero and the second operand is an exact power of two.
1940 Also optimize TRUNC_MOD_EXPR away if the second operand is
1941 constant and the first operand already has the right value
1943 case TRUNC_DIV_EXPR
:
1944 case TRUNC_MOD_EXPR
:
1945 if ((TREE_CODE (rhs1
) == SSA_NAME
1946 || TREE_CODE (rhs1
) == INTEGER_CST
)
1947 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
1948 return simplify_div_or_mod_using_ranges (gsi
, stmt
);
1951 /* Transform ABS (X) into X or -X as appropriate. */
1953 if (TREE_CODE (rhs1
) == SSA_NAME
1954 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
1955 return simplify_abs_using_ranges (gsi
, stmt
);
1960 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
1961 if all the bits being cleared are already cleared or
1962 all the bits being set are already set. */
1963 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
1964 return simplify_bit_ops_using_ranges (gsi
, stmt
);
1968 if (TREE_CODE (rhs1
) == SSA_NAME
1969 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
1970 return simplify_conversion_using_ranges (gsi
, stmt
);
1974 if (TREE_CODE (rhs1
) == SSA_NAME
1975 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
1976 return simplify_float_conversion_using_ranges (gsi
, stmt
);
1981 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
1982 return simplify_min_or_max_using_ranges (gsi
, stmt
);
1987 tree op0
= gimple_assign_rhs1 (stmt
);
1988 tree type
= TREE_TYPE (op0
);
1989 int_range_max range
;
1990 if (TYPE_SIGN (type
) == SIGNED
1991 && query
->range_of_expr (range
, op0
, stmt
))
1993 unsigned prec
= TYPE_PRECISION (TREE_TYPE (op0
));
1994 int_range
<2> nzm1 (type
, wi::minus_one (prec
), wi::zero (prec
),
1996 range
.intersect (nzm1
);
1997 // If there are no ranges other than [-1, 0] remove the shift.
1998 if (range
.undefined_p ())
2000 gimple_assign_set_rhs_from_tree (gsi
, op0
);
2011 else if (gimple_code (stmt
) == GIMPLE_COND
)
2012 return simplify_cond_using_ranges_1 (as_a
<gcond
*> (stmt
));
2013 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2014 return simplify_switch_using_ranges (as_a
<gswitch
*> (stmt
));
2015 else if (is_gimple_call (stmt
)
2016 && gimple_call_internal_p (stmt
))
2017 return simplify_internal_call_using_ranges (gsi
, stmt
);