* gimple-ssa-evrp.c (class evrp_range_analyzer): New class extracted
[official-gcc.git] / gcc / vr-values.c
blob3e760a378fcd77676e9fa75e0682c0e63bc4ac1e
1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2017 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)
9 any later version.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "insn-codes.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "ssa.h"
28 #include "optabs-tree.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "flags.h"
32 #include "fold-const.h"
33 #include "calls.h"
34 #include "cfganal.h"
35 #include "gimple-fold.h"
36 #include "gimple-iterator.h"
37 #include "tree-cfg.h"
38 #include "tree-ssa-loop-niter.h"
39 #include "tree-ssa-loop.h"
40 #include "intl.h"
41 #include "cfgloop.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"
48 #include "attribs.h"
49 #include "vr-values.h"
51 /* Set value range VR to a non-negative range of type TYPE. */
53 static inline void
54 set_value_range_to_nonnegative (value_range *vr, tree type)
56 tree zero = build_int_cst (type, 0);
57 set_value_range (vr, VR_RANGE, zero, vrp_val_max (type), vr->equiv);
60 /* Set value range VR to a range of a truthvalue of type TYPE. */
62 static inline void
63 set_value_range_to_truthvalue (value_range *vr, tree type)
65 if (TYPE_PRECISION (type) == 1)
66 set_value_range_to_varying (vr);
67 else
68 set_value_range (vr, VR_RANGE,
69 build_int_cst (type, 0), build_int_cst (type, 1),
70 vr->equiv);
74 /* Return value range information for VAR.
76 If we have no values ranges recorded (ie, VRP is not running), then
77 return NULL. Otherwise create an empty range if none existed for VAR. */
79 value_range *
80 vr_values::get_value_range (const_tree var)
82 static const value_range vr_const_varying
83 = { VR_VARYING, NULL_TREE, NULL_TREE, NULL };
84 value_range *vr;
85 tree sym;
86 unsigned ver = SSA_NAME_VERSION (var);
88 /* If we have no recorded ranges, then return NULL. */
89 if (! vr_value)
90 return NULL;
92 /* If we query the range for a new SSA name return an unmodifiable VARYING.
93 We should get here at most from the substitute-and-fold stage which
94 will never try to change values. */
95 if (ver >= num_vr_values)
96 return CONST_CAST (value_range *, &vr_const_varying);
98 vr = vr_value[ver];
99 if (vr)
100 return vr;
102 /* After propagation finished do not allocate new value-ranges. */
103 if (values_propagated)
104 return CONST_CAST (value_range *, &vr_const_varying);
106 /* Create a default value range. */
107 vr_value[ver] = vr = vrp_value_range_pool.allocate ();
108 memset (vr, 0, sizeof (*vr));
110 /* Defer allocating the equivalence set. */
111 vr->equiv = NULL;
113 /* If VAR is a default definition of a parameter, the variable can
114 take any value in VAR's type. */
115 if (SSA_NAME_IS_DEFAULT_DEF (var))
117 sym = SSA_NAME_VAR (var);
118 if (TREE_CODE (sym) == PARM_DECL)
120 /* Try to use the "nonnull" attribute to create ~[0, 0]
121 anti-ranges for pointers. Note that this is only valid with
122 default definitions of PARM_DECLs. */
123 if (POINTER_TYPE_P (TREE_TYPE (sym))
124 && (nonnull_arg_p (sym)
125 || get_ptr_nonnull (var)))
126 set_value_range_to_nonnull (vr, TREE_TYPE (sym));
127 else if (INTEGRAL_TYPE_P (TREE_TYPE (sym)))
129 wide_int min, max;
130 value_range_type rtype = get_range_info (var, &min, &max);
131 if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE)
132 set_value_range (vr, rtype,
133 wide_int_to_tree (TREE_TYPE (var), min),
134 wide_int_to_tree (TREE_TYPE (var), max),
135 NULL);
136 else
137 set_value_range_to_varying (vr);
139 else
140 set_value_range_to_varying (vr);
142 else if (TREE_CODE (sym) == RESULT_DECL
143 && DECL_BY_REFERENCE (sym))
144 set_value_range_to_nonnull (vr, TREE_TYPE (sym));
147 return vr;
150 /* Set value-ranges of all SSA names defined by STMT to varying. */
152 void
153 vr_values::set_defs_to_varying (gimple *stmt)
155 ssa_op_iter i;
156 tree def;
157 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
159 value_range *vr = get_value_range (def);
160 /* Avoid writing to vr_const_varying get_value_range may return. */
161 if (vr->type != VR_VARYING)
162 set_value_range_to_varying (vr);
166 /* Update the value range and equivalence set for variable VAR to
167 NEW_VR. Return true if NEW_VR is different from VAR's previous
168 value.
170 NOTE: This function assumes that NEW_VR is a temporary value range
171 object created for the sole purpose of updating VAR's range. The
172 storage used by the equivalence set from NEW_VR will be freed by
173 this function. Do not call update_value_range when NEW_VR
174 is the range object associated with another SSA name. */
176 bool
177 vr_values::update_value_range (const_tree var, value_range *new_vr)
179 value_range *old_vr;
180 bool is_new;
182 /* If there is a value-range on the SSA name from earlier analysis
183 factor that in. */
184 if (INTEGRAL_TYPE_P (TREE_TYPE (var)))
186 wide_int min, max;
187 value_range_type rtype = get_range_info (var, &min, &max);
188 if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE)
190 tree nr_min, nr_max;
191 nr_min = wide_int_to_tree (TREE_TYPE (var), min);
192 nr_max = wide_int_to_tree (TREE_TYPE (var), max);
193 value_range nr = VR_INITIALIZER;
194 set_and_canonicalize_value_range (&nr, rtype, nr_min, nr_max, NULL);
195 vrp_intersect_ranges (new_vr, &nr);
199 /* Update the value range, if necessary. */
200 old_vr = get_value_range (var);
201 is_new = old_vr->type != new_vr->type
202 || !vrp_operand_equal_p (old_vr->min, new_vr->min)
203 || !vrp_operand_equal_p (old_vr->max, new_vr->max)
204 || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
206 if (is_new)
208 /* Do not allow transitions up the lattice. The following
209 is slightly more awkward than just new_vr->type < old_vr->type
210 because VR_RANGE and VR_ANTI_RANGE need to be considered
211 the same. We may not have is_new when transitioning to
212 UNDEFINED. If old_vr->type is VARYING, we shouldn't be
213 called. */
214 if (new_vr->type == VR_UNDEFINED)
216 BITMAP_FREE (new_vr->equiv);
217 set_value_range_to_varying (old_vr);
218 set_value_range_to_varying (new_vr);
219 return true;
221 else
222 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
223 new_vr->equiv);
226 BITMAP_FREE (new_vr->equiv);
228 return is_new;
232 /* Add VAR and VAR's equivalence set to EQUIV. This is the central
233 point where equivalence processing can be turned on/off. */
235 void
236 vr_values::add_equivalence (bitmap *equiv, const_tree var)
238 unsigned ver = SSA_NAME_VERSION (var);
239 value_range *vr = get_value_range (var);
241 if (*equiv == NULL)
242 *equiv = BITMAP_ALLOC (&vrp_equiv_obstack);
243 bitmap_set_bit (*equiv, ver);
244 if (vr && vr->equiv)
245 bitmap_ior_into (*equiv, vr->equiv);
248 /* Return true if value range VR involves exactly one symbol SYM. */
250 static bool
251 symbolic_range_based_on_p (value_range *vr, const_tree sym)
253 bool neg, min_has_symbol, max_has_symbol;
254 tree inv;
256 if (is_gimple_min_invariant (vr->min))
257 min_has_symbol = false;
258 else if (get_single_symbol (vr->min, &neg, &inv) == sym)
259 min_has_symbol = true;
260 else
261 return false;
263 if (is_gimple_min_invariant (vr->max))
264 max_has_symbol = false;
265 else if (get_single_symbol (vr->max, &neg, &inv) == sym)
266 max_has_symbol = true;
267 else
268 return false;
270 return (min_has_symbol || max_has_symbol);
273 /* Return true if the result of assignment STMT is know to be non-zero. */
275 static bool
276 gimple_assign_nonzero_p (gimple *stmt)
278 enum tree_code code = gimple_assign_rhs_code (stmt);
279 bool strict_overflow_p;
280 switch (get_gimple_rhs_class (code))
282 case GIMPLE_UNARY_RHS:
283 return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
284 gimple_expr_type (stmt),
285 gimple_assign_rhs1 (stmt),
286 &strict_overflow_p);
287 case GIMPLE_BINARY_RHS:
288 return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
289 gimple_expr_type (stmt),
290 gimple_assign_rhs1 (stmt),
291 gimple_assign_rhs2 (stmt),
292 &strict_overflow_p);
293 case GIMPLE_TERNARY_RHS:
294 return false;
295 case GIMPLE_SINGLE_RHS:
296 return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt),
297 &strict_overflow_p);
298 case GIMPLE_INVALID_RHS:
299 gcc_unreachable ();
300 default:
301 gcc_unreachable ();
305 /* Return true if STMT is known to compute a non-zero value. */
307 static bool
308 gimple_stmt_nonzero_p (gimple *stmt)
310 switch (gimple_code (stmt))
312 case GIMPLE_ASSIGN:
313 return gimple_assign_nonzero_p (stmt);
314 case GIMPLE_CALL:
316 tree fndecl = gimple_call_fndecl (stmt);
317 if (!fndecl) return false;
318 if (flag_delete_null_pointer_checks && !flag_check_new
319 && DECL_IS_OPERATOR_NEW (fndecl)
320 && !TREE_NOTHROW (fndecl))
321 return true;
322 /* References are always non-NULL. */
323 if (flag_delete_null_pointer_checks
324 && TREE_CODE (TREE_TYPE (fndecl)) == REFERENCE_TYPE)
325 return true;
326 if (flag_delete_null_pointer_checks &&
327 lookup_attribute ("returns_nonnull",
328 TYPE_ATTRIBUTES (gimple_call_fntype (stmt))))
329 return true;
331 gcall *call_stmt = as_a<gcall *> (stmt);
332 unsigned rf = gimple_call_return_flags (call_stmt);
333 if (rf & ERF_RETURNS_ARG)
335 unsigned argnum = rf & ERF_RETURN_ARG_MASK;
336 if (argnum < gimple_call_num_args (call_stmt))
338 tree arg = gimple_call_arg (call_stmt, argnum);
339 if (SSA_VAR_P (arg)
340 && infer_nonnull_range_by_attribute (stmt, arg))
341 return true;
344 return gimple_alloca_call_p (stmt);
346 default:
347 gcc_unreachable ();
350 /* Like tree_expr_nonzero_p, but this function uses value ranges
351 obtained so far. */
353 bool
354 vr_values::vrp_stmt_computes_nonzero (gimple *stmt)
356 if (gimple_stmt_nonzero_p (stmt))
357 return true;
359 /* If we have an expression of the form &X->a, then the expression
360 is nonnull if X is nonnull. */
361 if (is_gimple_assign (stmt)
362 && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
364 tree expr = gimple_assign_rhs1 (stmt);
365 tree base = get_base_address (TREE_OPERAND (expr, 0));
367 if (base != NULL_TREE
368 && TREE_CODE (base) == MEM_REF
369 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
371 value_range *vr = get_value_range (TREE_OPERAND (base, 0));
372 if (range_is_nonnull (vr))
373 return true;
377 return false;
380 /* Returns true if EXPR is a valid value (as expected by compare_values) --
381 a gimple invariant, or SSA_NAME +- CST. */
383 static bool
384 valid_value_p (tree expr)
386 if (TREE_CODE (expr) == SSA_NAME)
387 return true;
389 if (TREE_CODE (expr) == PLUS_EXPR
390 || TREE_CODE (expr) == MINUS_EXPR)
391 return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
392 && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
394 return is_gimple_min_invariant (expr);
397 /* If OP has a value range with a single constant value return that,
398 otherwise return NULL_TREE. This returns OP itself if OP is a
399 constant. */
401 tree
402 vr_values::op_with_constant_singleton_value_range (tree op)
404 if (is_gimple_min_invariant (op))
405 return op;
407 if (TREE_CODE (op) != SSA_NAME)
408 return NULL_TREE;
410 return value_range_constant_singleton (get_value_range (op));
413 /* Return true if op is in a boolean [0, 1] value-range. */
415 bool
416 vr_values::op_with_boolean_value_range_p (tree op)
418 value_range *vr;
420 if (TYPE_PRECISION (TREE_TYPE (op)) == 1)
421 return true;
423 if (integer_zerop (op)
424 || integer_onep (op))
425 return true;
427 if (TREE_CODE (op) != SSA_NAME)
428 return false;
430 vr = get_value_range (op);
431 return (vr->type == VR_RANGE
432 && integer_zerop (vr->min)
433 && integer_onep (vr->max));
436 /* Extract value range information for VAR when (OP COND_CODE LIMIT) is
437 true and store it in *VR_P. */
439 void
440 vr_values::extract_range_for_var_from_comparison_expr (tree var,
441 enum tree_code cond_code,
442 tree op, tree limit,
443 value_range *vr_p)
445 tree min, max, type;
446 value_range *limit_vr;
447 type = TREE_TYPE (var);
448 gcc_assert (limit != var);
450 /* For pointer arithmetic, we only keep track of pointer equality
451 and inequality. */
452 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
454 set_value_range_to_varying (vr_p);
455 return;
458 /* If LIMIT is another SSA name and LIMIT has a range of its own,
459 try to use LIMIT's range to avoid creating symbolic ranges
460 unnecessarily. */
461 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
463 /* LIMIT's range is only interesting if it has any useful information. */
464 if (! limit_vr
465 || limit_vr->type == VR_UNDEFINED
466 || limit_vr->type == VR_VARYING
467 || (symbolic_range_p (limit_vr)
468 && ! (limit_vr->type == VR_RANGE
469 && (limit_vr->min == limit_vr->max
470 || operand_equal_p (limit_vr->min, limit_vr->max, 0)))))
471 limit_vr = NULL;
473 /* Initially, the new range has the same set of equivalences of
474 VAR's range. This will be revised before returning the final
475 value. Since assertions may be chained via mutually exclusive
476 predicates, we will need to trim the set of equivalences before
477 we are done. */
478 gcc_assert (vr_p->equiv == NULL);
479 add_equivalence (&vr_p->equiv, var);
481 /* Extract a new range based on the asserted comparison for VAR and
482 LIMIT's value range. Notice that if LIMIT has an anti-range, we
483 will only use it for equality comparisons (EQ_EXPR). For any
484 other kind of assertion, we cannot derive a range from LIMIT's
485 anti-range that can be used to describe the new range. For
486 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
487 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
488 no single range for x_2 that could describe LE_EXPR, so we might
489 as well build the range [b_4, +INF] for it.
490 One special case we handle is extracting a range from a
491 range test encoded as (unsigned)var + CST <= limit. */
492 if (TREE_CODE (op) == NOP_EXPR
493 || TREE_CODE (op) == PLUS_EXPR)
495 if (TREE_CODE (op) == PLUS_EXPR)
497 min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)),
498 TREE_OPERAND (op, 1));
499 max = int_const_binop (PLUS_EXPR, limit, min);
500 op = TREE_OPERAND (op, 0);
502 else
504 min = build_int_cst (TREE_TYPE (var), 0);
505 max = limit;
508 /* Make sure to not set TREE_OVERFLOW on the final type
509 conversion. We are willingly interpreting large positive
510 unsigned values as negative signed values here. */
511 min = force_fit_type (TREE_TYPE (var), wi::to_widest (min), 0, false);
512 max = force_fit_type (TREE_TYPE (var), wi::to_widest (max), 0, false);
514 /* We can transform a max, min range to an anti-range or
515 vice-versa. Use set_and_canonicalize_value_range which does
516 this for us. */
517 if (cond_code == LE_EXPR)
518 set_and_canonicalize_value_range (vr_p, VR_RANGE,
519 min, max, vr_p->equiv);
520 else if (cond_code == GT_EXPR)
521 set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
522 min, max, vr_p->equiv);
523 else
524 gcc_unreachable ();
526 else if (cond_code == EQ_EXPR)
528 enum value_range_type range_type;
530 if (limit_vr)
532 range_type = limit_vr->type;
533 min = limit_vr->min;
534 max = limit_vr->max;
536 else
538 range_type = VR_RANGE;
539 min = limit;
540 max = limit;
543 set_value_range (vr_p, range_type, min, max, vr_p->equiv);
545 /* When asserting the equality VAR == LIMIT and LIMIT is another
546 SSA name, the new range will also inherit the equivalence set
547 from LIMIT. */
548 if (TREE_CODE (limit) == SSA_NAME)
549 add_equivalence (&vr_p->equiv, limit);
551 else if (cond_code == NE_EXPR)
553 /* As described above, when LIMIT's range is an anti-range and
554 this assertion is an inequality (NE_EXPR), then we cannot
555 derive anything from the anti-range. For instance, if
556 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
557 not imply that VAR's range is [0, 0]. So, in the case of
558 anti-ranges, we just assert the inequality using LIMIT and
559 not its anti-range.
561 If LIMIT_VR is a range, we can only use it to build a new
562 anti-range if LIMIT_VR is a single-valued range. For
563 instance, if LIMIT_VR is [0, 1], the predicate
564 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
565 Rather, it means that for value 0 VAR should be ~[0, 0]
566 and for value 1, VAR should be ~[1, 1]. We cannot
567 represent these ranges.
569 The only situation in which we can build a valid
570 anti-range is when LIMIT_VR is a single-valued range
571 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
572 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
573 if (limit_vr
574 && limit_vr->type == VR_RANGE
575 && compare_values (limit_vr->min, limit_vr->max) == 0)
577 min = limit_vr->min;
578 max = limit_vr->max;
580 else
582 /* In any other case, we cannot use LIMIT's range to build a
583 valid anti-range. */
584 min = max = limit;
587 /* If MIN and MAX cover the whole range for their type, then
588 just use the original LIMIT. */
589 if (INTEGRAL_TYPE_P (type)
590 && vrp_val_is_min (min)
591 && vrp_val_is_max (max))
592 min = max = limit;
594 set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
595 min, max, vr_p->equiv);
597 else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
599 min = TYPE_MIN_VALUE (type);
601 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
602 max = limit;
603 else
605 /* If LIMIT_VR is of the form [N1, N2], we need to build the
606 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
607 LT_EXPR. */
608 max = limit_vr->max;
611 /* If the maximum value forces us to be out of bounds, simply punt.
612 It would be pointless to try and do anything more since this
613 all should be optimized away above us. */
614 if (cond_code == LT_EXPR
615 && compare_values (max, min) == 0)
616 set_value_range_to_varying (vr_p);
617 else
619 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
620 if (cond_code == LT_EXPR)
622 if (TYPE_PRECISION (TREE_TYPE (max)) == 1
623 && !TYPE_UNSIGNED (TREE_TYPE (max)))
624 max = fold_build2 (PLUS_EXPR, TREE_TYPE (max), max,
625 build_int_cst (TREE_TYPE (max), -1));
626 else
627 max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max,
628 build_int_cst (TREE_TYPE (max), 1));
629 /* Signal to compare_values_warnv this expr doesn't overflow. */
630 if (EXPR_P (max))
631 TREE_NO_WARNING (max) = 1;
634 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
637 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
639 max = TYPE_MAX_VALUE (type);
641 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
642 min = limit;
643 else
645 /* If LIMIT_VR is of the form [N1, N2], we need to build the
646 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
647 GT_EXPR. */
648 min = limit_vr->min;
651 /* If the minimum value forces us to be out of bounds, simply punt.
652 It would be pointless to try and do anything more since this
653 all should be optimized away above us. */
654 if (cond_code == GT_EXPR
655 && compare_values (min, max) == 0)
656 set_value_range_to_varying (vr_p);
657 else
659 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
660 if (cond_code == GT_EXPR)
662 if (TYPE_PRECISION (TREE_TYPE (min)) == 1
663 && !TYPE_UNSIGNED (TREE_TYPE (min)))
664 min = fold_build2 (MINUS_EXPR, TREE_TYPE (min), min,
665 build_int_cst (TREE_TYPE (min), -1));
666 else
667 min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min,
668 build_int_cst (TREE_TYPE (min), 1));
669 /* Signal to compare_values_warnv this expr doesn't overflow. */
670 if (EXPR_P (min))
671 TREE_NO_WARNING (min) = 1;
674 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
677 else
678 gcc_unreachable ();
680 /* Finally intersect the new range with what we already know about var. */
681 vrp_intersect_ranges (vr_p, get_value_range (var));
684 /* Extract value range information from an ASSERT_EXPR EXPR and store
685 it in *VR_P. */
687 void
688 vr_values::extract_range_from_assert (value_range *vr_p, tree expr)
690 tree var = ASSERT_EXPR_VAR (expr);
691 tree cond = ASSERT_EXPR_COND (expr);
692 tree limit, op;
693 enum tree_code cond_code;
694 gcc_assert (COMPARISON_CLASS_P (cond));
696 /* Find VAR in the ASSERT_EXPR conditional. */
697 if (var == TREE_OPERAND (cond, 0)
698 || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
699 || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
701 /* If the predicate is of the form VAR COMP LIMIT, then we just
702 take LIMIT from the RHS and use the same comparison code. */
703 cond_code = TREE_CODE (cond);
704 limit = TREE_OPERAND (cond, 1);
705 op = TREE_OPERAND (cond, 0);
707 else
709 /* If the predicate is of the form LIMIT COMP VAR, then we need
710 to flip around the comparison code to create the proper range
711 for VAR. */
712 cond_code = swap_tree_comparison (TREE_CODE (cond));
713 limit = TREE_OPERAND (cond, 0);
714 op = TREE_OPERAND (cond, 1);
716 extract_range_for_var_from_comparison_expr (var, cond_code, op,
717 limit, vr_p);
720 /* Extract range information from SSA name VAR and store it in VR. If
721 VAR has an interesting range, use it. Otherwise, create the
722 range [VAR, VAR] and return it. This is useful in situations where
723 we may have conditionals testing values of VARYING names. For
724 instance,
726 x_3 = y_5;
727 if (x_3 > y_5)
730 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
731 always false. */
733 void
734 vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
736 value_range *var_vr = get_value_range (var);
738 if (var_vr->type != VR_VARYING)
739 copy_value_range (vr, var_vr);
740 else
741 set_value_range (vr, VR_RANGE, var, var, NULL);
743 add_equivalence (&vr->equiv, var);
746 /* Extract range information from a binary expression OP0 CODE OP1 based on
747 the ranges of each of its operands with resulting type EXPR_TYPE.
748 The resulting range is stored in *VR. */
750 void
751 vr_values::extract_range_from_binary_expr (value_range *vr,
752 enum tree_code code,
753 tree expr_type, tree op0, tree op1)
755 value_range vr0 = VR_INITIALIZER;
756 value_range vr1 = VR_INITIALIZER;
758 /* Get value ranges for each operand. For constant operands, create
759 a new value range with the operand to simplify processing. */
760 if (TREE_CODE (op0) == SSA_NAME)
761 vr0 = *(get_value_range (op0));
762 else if (is_gimple_min_invariant (op0))
763 set_value_range_to_value (&vr0, op0, NULL);
764 else
765 set_value_range_to_varying (&vr0);
767 if (TREE_CODE (op1) == SSA_NAME)
768 vr1 = *(get_value_range (op1));
769 else if (is_gimple_min_invariant (op1))
770 set_value_range_to_value (&vr1, op1, NULL);
771 else
772 set_value_range_to_varying (&vr1);
774 extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
776 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
777 and based on the other operand, for example if it was deduced from a
778 symbolic comparison. When a bound of the range of the first operand
779 is invariant, we set the corresponding bound of the new range to INF
780 in order to avoid recursing on the range of the second operand. */
781 if (vr->type == VR_VARYING
782 && (code == PLUS_EXPR || code == MINUS_EXPR)
783 && TREE_CODE (op1) == SSA_NAME
784 && vr0.type == VR_RANGE
785 && symbolic_range_based_on_p (&vr0, op1))
787 const bool minus_p = (code == MINUS_EXPR);
788 value_range n_vr1 = VR_INITIALIZER;
790 /* Try with VR0 and [-INF, OP1]. */
791 if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min))
792 set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL);
794 /* Try with VR0 and [OP1, +INF]. */
795 else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max))
796 set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL);
798 /* Try with VR0 and [OP1, OP1]. */
799 else
800 set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL);
802 extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1);
805 if (vr->type == VR_VARYING
806 && (code == PLUS_EXPR || code == MINUS_EXPR)
807 && TREE_CODE (op0) == SSA_NAME
808 && vr1.type == VR_RANGE
809 && symbolic_range_based_on_p (&vr1, op0))
811 const bool minus_p = (code == MINUS_EXPR);
812 value_range n_vr0 = VR_INITIALIZER;
814 /* Try with [-INF, OP0] and VR1. */
815 if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min))
816 set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL);
818 /* Try with [OP0, +INF] and VR1. */
819 else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max))
820 set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL);
822 /* Try with [OP0, OP0] and VR1. */
823 else
824 set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL);
826 extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
829 /* If we didn't derive a range for MINUS_EXPR, and
830 op1's range is ~[op0,op0] or vice-versa, then we
831 can derive a non-null range. This happens often for
832 pointer subtraction. */
833 if (vr->type == VR_VARYING
834 && code == MINUS_EXPR
835 && TREE_CODE (op0) == SSA_NAME
836 && ((vr0.type == VR_ANTI_RANGE
837 && vr0.min == op1
838 && vr0.min == vr0.max)
839 || (vr1.type == VR_ANTI_RANGE
840 && vr1.min == op0
841 && vr1.min == vr1.max)))
842 set_value_range_to_nonnull (vr, TREE_TYPE (op0));
845 /* Extract range information from a unary expression CODE OP0 based on
846 the range of its operand with resulting type TYPE.
847 The resulting range is stored in *VR. */
849 void
850 vr_values::extract_range_from_unary_expr (value_range *vr, enum tree_code code,
851 tree type, tree op0)
853 value_range vr0 = VR_INITIALIZER;
855 /* Get value ranges for the operand. For constant operands, create
856 a new value range with the operand to simplify processing. */
857 if (TREE_CODE (op0) == SSA_NAME)
858 vr0 = *(get_value_range (op0));
859 else if (is_gimple_min_invariant (op0))
860 set_value_range_to_value (&vr0, op0, NULL);
861 else
862 set_value_range_to_varying (&vr0);
864 ::extract_range_from_unary_expr (vr, code, type, &vr0, TREE_TYPE (op0));
868 /* Extract range information from a conditional expression STMT based on
869 the ranges of each of its operands and the expression code. */
871 void
872 vr_values::extract_range_from_cond_expr (value_range *vr, gassign *stmt)
874 tree op0, op1;
875 value_range vr0 = VR_INITIALIZER;
876 value_range vr1 = VR_INITIALIZER;
878 /* Get value ranges for each operand. For constant operands, create
879 a new value range with the operand to simplify processing. */
880 op0 = gimple_assign_rhs2 (stmt);
881 if (TREE_CODE (op0) == SSA_NAME)
882 vr0 = *(get_value_range (op0));
883 else if (is_gimple_min_invariant (op0))
884 set_value_range_to_value (&vr0, op0, NULL);
885 else
886 set_value_range_to_varying (&vr0);
888 op1 = gimple_assign_rhs3 (stmt);
889 if (TREE_CODE (op1) == SSA_NAME)
890 vr1 = *(get_value_range (op1));
891 else if (is_gimple_min_invariant (op1))
892 set_value_range_to_value (&vr1, op1, NULL);
893 else
894 set_value_range_to_varying (&vr1);
896 /* The resulting value range is the union of the operand ranges */
897 copy_value_range (vr, &vr0);
898 vrp_meet (vr, &vr1);
902 /* Extract range information from a comparison expression EXPR based
903 on the range of its operand and the expression code. */
905 void
906 vr_values::extract_range_from_comparison (value_range *vr, enum tree_code code,
907 tree type, tree op0, tree op1)
909 bool sop;
910 tree val;
912 val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
913 NULL);
914 if (val)
916 /* Since this expression was found on the RHS of an assignment,
917 its type may be different from _Bool. Convert VAL to EXPR's
918 type. */
919 val = fold_convert (type, val);
920 if (is_gimple_min_invariant (val))
921 set_value_range_to_value (vr, val, vr->equiv);
922 else
923 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
925 else
926 /* The result of a comparison is always true or false. */
927 set_value_range_to_truthvalue (vr, type);
930 /* Helper function for simplify_internal_call_using_ranges and
931 extract_range_basic. Return true if OP0 SUBCODE OP1 for
932 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
933 always overflow. Set *OVF to true if it is known to always
934 overflow. */
936 bool
937 vr_values::check_for_binary_op_overflow (enum tree_code subcode, tree type,
938 tree op0, tree op1, bool *ovf)
940 value_range vr0 = VR_INITIALIZER;
941 value_range vr1 = VR_INITIALIZER;
942 if (TREE_CODE (op0) == SSA_NAME)
943 vr0 = *get_value_range (op0);
944 else if (TREE_CODE (op0) == INTEGER_CST)
945 set_value_range_to_value (&vr0, op0, NULL);
946 else
947 set_value_range_to_varying (&vr0);
949 if (TREE_CODE (op1) == SSA_NAME)
950 vr1 = *get_value_range (op1);
951 else if (TREE_CODE (op1) == INTEGER_CST)
952 set_value_range_to_value (&vr1, op1, NULL);
953 else
954 set_value_range_to_varying (&vr1);
956 if (!range_int_cst_p (&vr0)
957 || TREE_OVERFLOW (vr0.min)
958 || TREE_OVERFLOW (vr0.max))
960 vr0.min = vrp_val_min (TREE_TYPE (op0));
961 vr0.max = vrp_val_max (TREE_TYPE (op0));
963 if (!range_int_cst_p (&vr1)
964 || TREE_OVERFLOW (vr1.min)
965 || TREE_OVERFLOW (vr1.max))
967 vr1.min = vrp_val_min (TREE_TYPE (op1));
968 vr1.max = vrp_val_max (TREE_TYPE (op1));
970 *ovf = arith_overflowed_p (subcode, type, vr0.min,
971 subcode == MINUS_EXPR ? vr1.max : vr1.min);
972 if (arith_overflowed_p (subcode, type, vr0.max,
973 subcode == MINUS_EXPR ? vr1.min : vr1.max) != *ovf)
974 return false;
975 if (subcode == MULT_EXPR)
977 if (arith_overflowed_p (subcode, type, vr0.min, vr1.max) != *ovf
978 || arith_overflowed_p (subcode, type, vr0.max, vr1.min) != *ovf)
979 return false;
981 if (*ovf)
983 /* So far we found that there is an overflow on the boundaries.
984 That doesn't prove that there is an overflow even for all values
985 in between the boundaries. For that compute widest_int range
986 of the result and see if it doesn't overlap the range of
987 type. */
988 widest_int wmin, wmax;
989 widest_int w[4];
990 int i;
991 w[0] = wi::to_widest (vr0.min);
992 w[1] = wi::to_widest (vr0.max);
993 w[2] = wi::to_widest (vr1.min);
994 w[3] = wi::to_widest (vr1.max);
995 for (i = 0; i < 4; i++)
997 widest_int wt;
998 switch (subcode)
1000 case PLUS_EXPR:
1001 wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]);
1002 break;
1003 case MINUS_EXPR:
1004 wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]);
1005 break;
1006 case MULT_EXPR:
1007 wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]);
1008 break;
1009 default:
1010 gcc_unreachable ();
1012 if (i == 0)
1014 wmin = wt;
1015 wmax = wt;
1017 else
1019 wmin = wi::smin (wmin, wt);
1020 wmax = wi::smax (wmax, wt);
1023 /* The result of op0 CODE op1 is known to be in range
1024 [wmin, wmax]. */
1025 widest_int wtmin = wi::to_widest (vrp_val_min (type));
1026 widest_int wtmax = wi::to_widest (vrp_val_max (type));
1027 /* If all values in [wmin, wmax] are smaller than
1028 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1029 the arithmetic operation will always overflow. */
1030 if (wmax < wtmin || wmin > wtmax)
1031 return true;
1032 return false;
1034 return true;
1037 /* Try to derive a nonnegative or nonzero range out of STMT relying
1038 primarily on generic routines in fold in conjunction with range data.
1039 Store the result in *VR */
1041 void
1042 vr_values::extract_range_basic (value_range *vr, gimple *stmt)
1044 bool sop;
1045 tree type = gimple_expr_type (stmt);
1047 if (is_gimple_call (stmt))
1049 tree arg;
1050 int mini, maxi, zerov = 0, prec;
1051 enum tree_code subcode = ERROR_MARK;
1052 combined_fn cfn = gimple_call_combined_fn (stmt);
1053 scalar_int_mode mode;
1055 switch (cfn)
1057 case CFN_BUILT_IN_CONSTANT_P:
1058 /* If the call is __builtin_constant_p and the argument is a
1059 function parameter resolve it to false. This avoids bogus
1060 array bound warnings.
1061 ??? We could do this as early as inlining is finished. */
1062 arg = gimple_call_arg (stmt, 0);
1063 if (TREE_CODE (arg) == SSA_NAME
1064 && SSA_NAME_IS_DEFAULT_DEF (arg)
1065 && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL
1066 && cfun->after_inlining)
1068 set_value_range_to_null (vr, type);
1069 return;
1071 break;
1072 /* Both __builtin_ffs* and __builtin_popcount return
1073 [0, prec]. */
1074 CASE_CFN_FFS:
1075 CASE_CFN_POPCOUNT:
1076 arg = gimple_call_arg (stmt, 0);
1077 prec = TYPE_PRECISION (TREE_TYPE (arg));
1078 mini = 0;
1079 maxi = prec;
1080 if (TREE_CODE (arg) == SSA_NAME)
1082 value_range *vr0 = get_value_range (arg);
1083 /* If arg is non-zero, then ffs or popcount
1084 are non-zero. */
1085 if ((vr0->type == VR_RANGE
1086 && range_includes_zero_p (vr0->min, vr0->max) == 0)
1087 || (vr0->type == VR_ANTI_RANGE
1088 && range_includes_zero_p (vr0->min, vr0->max) == 1))
1089 mini = 1;
1090 /* If some high bits are known to be zero,
1091 we can decrease the maximum. */
1092 if (vr0->type == VR_RANGE
1093 && TREE_CODE (vr0->max) == INTEGER_CST
1094 && !operand_less_p (vr0->min,
1095 build_zero_cst (TREE_TYPE (vr0->min))))
1096 maxi = tree_floor_log2 (vr0->max) + 1;
1098 goto bitop_builtin;
1099 /* __builtin_parity* returns [0, 1]. */
1100 CASE_CFN_PARITY:
1101 mini = 0;
1102 maxi = 1;
1103 goto bitop_builtin;
1104 /* __builtin_c[lt]z* return [0, prec-1], except for
1105 when the argument is 0, but that is undefined behavior.
1106 On many targets where the CLZ RTL or optab value is defined
1107 for 0 the value is prec, so include that in the range
1108 by default. */
1109 CASE_CFN_CLZ:
1110 arg = gimple_call_arg (stmt, 0);
1111 prec = TYPE_PRECISION (TREE_TYPE (arg));
1112 mini = 0;
1113 maxi = prec;
1114 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
1115 if (optab_handler (clz_optab, mode) != CODE_FOR_nothing
1116 && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov)
1117 /* Handle only the single common value. */
1118 && zerov != prec)
1119 /* Magic value to give up, unless vr0 proves
1120 arg is non-zero. */
1121 mini = -2;
1122 if (TREE_CODE (arg) == SSA_NAME)
1124 value_range *vr0 = get_value_range (arg);
1125 /* From clz of VR_RANGE minimum we can compute
1126 result maximum. */
1127 if (vr0->type == VR_RANGE
1128 && TREE_CODE (vr0->min) == INTEGER_CST)
1130 maxi = prec - 1 - tree_floor_log2 (vr0->min);
1131 if (maxi != prec)
1132 mini = 0;
1134 else if (vr0->type == VR_ANTI_RANGE
1135 && integer_zerop (vr0->min))
1137 maxi = prec - 1;
1138 mini = 0;
1140 if (mini == -2)
1141 break;
1142 /* From clz of VR_RANGE maximum we can compute
1143 result minimum. */
1144 if (vr0->type == VR_RANGE
1145 && TREE_CODE (vr0->max) == INTEGER_CST)
1147 mini = prec - 1 - tree_floor_log2 (vr0->max);
1148 if (mini == prec)
1149 break;
1152 if (mini == -2)
1153 break;
1154 goto bitop_builtin;
1155 /* __builtin_ctz* return [0, prec-1], except for
1156 when the argument is 0, but that is undefined behavior.
1157 If there is a ctz optab for this mode and
1158 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1159 otherwise just assume 0 won't be seen. */
1160 CASE_CFN_CTZ:
1161 arg = gimple_call_arg (stmt, 0);
1162 prec = TYPE_PRECISION (TREE_TYPE (arg));
1163 mini = 0;
1164 maxi = prec - 1;
1165 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
1166 if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing
1167 && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov))
1169 /* Handle only the two common values. */
1170 if (zerov == -1)
1171 mini = -1;
1172 else if (zerov == prec)
1173 maxi = prec;
1174 else
1175 /* Magic value to give up, unless vr0 proves
1176 arg is non-zero. */
1177 mini = -2;
1179 if (TREE_CODE (arg) == SSA_NAME)
1181 value_range *vr0 = get_value_range (arg);
1182 /* If arg is non-zero, then use [0, prec - 1]. */
1183 if ((vr0->type == VR_RANGE
1184 && integer_nonzerop (vr0->min))
1185 || (vr0->type == VR_ANTI_RANGE
1186 && integer_zerop (vr0->min)))
1188 mini = 0;
1189 maxi = prec - 1;
1191 /* If some high bits are known to be zero,
1192 we can decrease the result maximum. */
1193 if (vr0->type == VR_RANGE
1194 && TREE_CODE (vr0->max) == INTEGER_CST)
1196 maxi = tree_floor_log2 (vr0->max);
1197 /* For vr0 [0, 0] give up. */
1198 if (maxi == -1)
1199 break;
1202 if (mini == -2)
1203 break;
1204 goto bitop_builtin;
1205 /* __builtin_clrsb* returns [0, prec-1]. */
1206 CASE_CFN_CLRSB:
1207 arg = gimple_call_arg (stmt, 0);
1208 prec = TYPE_PRECISION (TREE_TYPE (arg));
1209 mini = 0;
1210 maxi = prec - 1;
1211 goto bitop_builtin;
1212 bitop_builtin:
1213 set_value_range (vr, VR_RANGE, build_int_cst (type, mini),
1214 build_int_cst (type, maxi), NULL);
1215 return;
1216 case CFN_UBSAN_CHECK_ADD:
1217 subcode = PLUS_EXPR;
1218 break;
1219 case CFN_UBSAN_CHECK_SUB:
1220 subcode = MINUS_EXPR;
1221 break;
1222 case CFN_UBSAN_CHECK_MUL:
1223 subcode = MULT_EXPR;
1224 break;
1225 case CFN_GOACC_DIM_SIZE:
1226 case CFN_GOACC_DIM_POS:
1227 /* Optimizing these two internal functions helps the loop
1228 optimizer eliminate outer comparisons. Size is [1,N]
1229 and pos is [0,N-1]. */
1231 bool is_pos = cfn == CFN_GOACC_DIM_POS;
1232 int axis = oacc_get_ifn_dim_arg (stmt);
1233 int size = oacc_get_fn_dim_size (current_function_decl, axis);
1235 if (!size)
1236 /* If it's dynamic, the backend might know a hardware
1237 limitation. */
1238 size = targetm.goacc.dim_limit (axis);
1240 tree type = TREE_TYPE (gimple_call_lhs (stmt));
1241 set_value_range (vr, VR_RANGE,
1242 build_int_cst (type, is_pos ? 0 : 1),
1243 size ? build_int_cst (type, size - is_pos)
1244 : vrp_val_max (type), NULL);
1246 return;
1247 case CFN_BUILT_IN_STRLEN:
1248 if (tree lhs = gimple_call_lhs (stmt))
1249 if (ptrdiff_type_node
1250 && (TYPE_PRECISION (ptrdiff_type_node)
1251 == TYPE_PRECISION (TREE_TYPE (lhs))))
1253 tree type = TREE_TYPE (lhs);
1254 tree max = vrp_val_max (ptrdiff_type_node);
1255 wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
1256 tree range_min = build_zero_cst (type);
1257 tree range_max = wide_int_to_tree (type, wmax - 1);
1258 set_value_range (vr, VR_RANGE, range_min, range_max, NULL);
1259 return;
1261 break;
1262 default:
1263 break;
1265 if (subcode != ERROR_MARK)
1267 bool saved_flag_wrapv = flag_wrapv;
1268 /* Pretend the arithmetics is wrapping. If there is
1269 any overflow, we'll complain, but will actually do
1270 wrapping operation. */
1271 flag_wrapv = 1;
1272 extract_range_from_binary_expr (vr, subcode, type,
1273 gimple_call_arg (stmt, 0),
1274 gimple_call_arg (stmt, 1));
1275 flag_wrapv = saved_flag_wrapv;
1277 /* If for both arguments vrp_valueize returned non-NULL,
1278 this should have been already folded and if not, it
1279 wasn't folded because of overflow. Avoid removing the
1280 UBSAN_CHECK_* calls in that case. */
1281 if (vr->type == VR_RANGE
1282 && (vr->min == vr->max
1283 || operand_equal_p (vr->min, vr->max, 0)))
1284 set_value_range_to_varying (vr);
1285 return;
1288 /* Handle extraction of the two results (result of arithmetics and
1289 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1290 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1291 else if (is_gimple_assign (stmt)
1292 && (gimple_assign_rhs_code (stmt) == REALPART_EXPR
1293 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR)
1294 && INTEGRAL_TYPE_P (type))
1296 enum tree_code code = gimple_assign_rhs_code (stmt);
1297 tree op = gimple_assign_rhs1 (stmt);
1298 if (TREE_CODE (op) == code && TREE_CODE (TREE_OPERAND (op, 0)) == SSA_NAME)
1300 gimple *g = SSA_NAME_DEF_STMT (TREE_OPERAND (op, 0));
1301 if (is_gimple_call (g) && gimple_call_internal_p (g))
1303 enum tree_code subcode = ERROR_MARK;
1304 switch (gimple_call_internal_fn (g))
1306 case IFN_ADD_OVERFLOW:
1307 subcode = PLUS_EXPR;
1308 break;
1309 case IFN_SUB_OVERFLOW:
1310 subcode = MINUS_EXPR;
1311 break;
1312 case IFN_MUL_OVERFLOW:
1313 subcode = MULT_EXPR;
1314 break;
1315 case IFN_ATOMIC_COMPARE_EXCHANGE:
1316 if (code == IMAGPART_EXPR)
1318 /* This is the boolean return value whether compare and
1319 exchange changed anything or not. */
1320 set_value_range (vr, VR_RANGE, build_int_cst (type, 0),
1321 build_int_cst (type, 1), NULL);
1322 return;
1324 break;
1325 default:
1326 break;
1328 if (subcode != ERROR_MARK)
1330 tree op0 = gimple_call_arg (g, 0);
1331 tree op1 = gimple_call_arg (g, 1);
1332 if (code == IMAGPART_EXPR)
1334 bool ovf = false;
1335 if (check_for_binary_op_overflow (subcode, type,
1336 op0, op1, &ovf))
1337 set_value_range_to_value (vr,
1338 build_int_cst (type, ovf),
1339 NULL);
1340 else if (TYPE_PRECISION (type) == 1
1341 && !TYPE_UNSIGNED (type))
1342 set_value_range_to_varying (vr);
1343 else
1344 set_value_range (vr, VR_RANGE, build_int_cst (type, 0),
1345 build_int_cst (type, 1), NULL);
1347 else if (types_compatible_p (type, TREE_TYPE (op0))
1348 && types_compatible_p (type, TREE_TYPE (op1)))
1350 bool saved_flag_wrapv = flag_wrapv;
1351 /* Pretend the arithmetics is wrapping. If there is
1352 any overflow, IMAGPART_EXPR will be set. */
1353 flag_wrapv = 1;
1354 extract_range_from_binary_expr (vr, subcode, type,
1355 op0, op1);
1356 flag_wrapv = saved_flag_wrapv;
1358 else
1360 value_range vr0 = VR_INITIALIZER;
1361 value_range vr1 = VR_INITIALIZER;
1362 bool saved_flag_wrapv = flag_wrapv;
1363 /* Pretend the arithmetics is wrapping. If there is
1364 any overflow, IMAGPART_EXPR will be set. */
1365 flag_wrapv = 1;
1366 extract_range_from_unary_expr (&vr0, NOP_EXPR,
1367 type, op0);
1368 extract_range_from_unary_expr (&vr1, NOP_EXPR,
1369 type, op1);
1370 extract_range_from_binary_expr_1 (vr, subcode, type,
1371 &vr0, &vr1);
1372 flag_wrapv = saved_flag_wrapv;
1374 return;
1379 if (INTEGRAL_TYPE_P (type)
1380 && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
1381 set_value_range_to_nonnegative (vr, type);
1382 else if (vrp_stmt_computes_nonzero (stmt))
1383 set_value_range_to_nonnull (vr, type);
1384 else
1385 set_value_range_to_varying (vr);
1389 /* Try to compute a useful range out of assignment STMT and store it
1390 in *VR. */
1392 void
1393 vr_values::extract_range_from_assignment (value_range *vr, gassign *stmt)
1395 enum tree_code code = gimple_assign_rhs_code (stmt);
1397 if (code == ASSERT_EXPR)
1398 extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
1399 else if (code == SSA_NAME)
1400 extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
1401 else if (TREE_CODE_CLASS (code) == tcc_binary)
1402 extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
1403 gimple_expr_type (stmt),
1404 gimple_assign_rhs1 (stmt),
1405 gimple_assign_rhs2 (stmt));
1406 else if (TREE_CODE_CLASS (code) == tcc_unary)
1407 extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
1408 gimple_expr_type (stmt),
1409 gimple_assign_rhs1 (stmt));
1410 else if (code == COND_EXPR)
1411 extract_range_from_cond_expr (vr, stmt);
1412 else if (TREE_CODE_CLASS (code) == tcc_comparison)
1413 extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
1414 gimple_expr_type (stmt),
1415 gimple_assign_rhs1 (stmt),
1416 gimple_assign_rhs2 (stmt));
1417 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
1418 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1419 set_value_range_to_value (vr, gimple_assign_rhs1 (stmt), NULL);
1420 else
1421 set_value_range_to_varying (vr);
1423 if (vr->type == VR_VARYING)
1424 extract_range_basic (vr, stmt);
1427 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1429 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1430 all the values in the ranges.
1432 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1434 - Return NULL_TREE if it is not always possible to determine the
1435 value of the comparison.
1437 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1438 assumed signed overflow is undefined. */
1441 static tree
1442 compare_ranges (enum tree_code comp, value_range *vr0, value_range *vr1,
1443 bool *strict_overflow_p)
1445 /* VARYING or UNDEFINED ranges cannot be compared. */
1446 if (vr0->type == VR_VARYING
1447 || vr0->type == VR_UNDEFINED
1448 || vr1->type == VR_VARYING
1449 || vr1->type == VR_UNDEFINED)
1450 return NULL_TREE;
1452 /* Anti-ranges need to be handled separately. */
1453 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
1455 /* If both are anti-ranges, then we cannot compute any
1456 comparison. */
1457 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
1458 return NULL_TREE;
1460 /* These comparisons are never statically computable. */
1461 if (comp == GT_EXPR
1462 || comp == GE_EXPR
1463 || comp == LT_EXPR
1464 || comp == LE_EXPR)
1465 return NULL_TREE;
1467 /* Equality can be computed only between a range and an
1468 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1469 if (vr0->type == VR_RANGE)
1471 /* To simplify processing, make VR0 the anti-range. */
1472 value_range *tmp = vr0;
1473 vr0 = vr1;
1474 vr1 = tmp;
1477 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
1479 if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
1480 && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
1481 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1483 return NULL_TREE;
1486 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1487 operands around and change the comparison code. */
1488 if (comp == GT_EXPR || comp == GE_EXPR)
1490 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
1491 std::swap (vr0, vr1);
1494 if (comp == EQ_EXPR)
1496 /* Equality may only be computed if both ranges represent
1497 exactly one value. */
1498 if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
1499 && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
1501 int cmp_min = compare_values_warnv (vr0->min, vr1->min,
1502 strict_overflow_p);
1503 int cmp_max = compare_values_warnv (vr0->max, vr1->max,
1504 strict_overflow_p);
1505 if (cmp_min == 0 && cmp_max == 0)
1506 return boolean_true_node;
1507 else if (cmp_min != -2 && cmp_max != -2)
1508 return boolean_false_node;
1510 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1511 else if (compare_values_warnv (vr0->min, vr1->max,
1512 strict_overflow_p) == 1
1513 || compare_values_warnv (vr1->min, vr0->max,
1514 strict_overflow_p) == 1)
1515 return boolean_false_node;
1517 return NULL_TREE;
1519 else if (comp == NE_EXPR)
1521 int cmp1, cmp2;
1523 /* If VR0 is completely to the left or completely to the right
1524 of VR1, they are always different. Notice that we need to
1525 make sure that both comparisons yield similar results to
1526 avoid comparing values that cannot be compared at
1527 compile-time. */
1528 cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
1529 cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
1530 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1531 return boolean_true_node;
1533 /* If VR0 and VR1 represent a single value and are identical,
1534 return false. */
1535 else if (compare_values_warnv (vr0->min, vr0->max,
1536 strict_overflow_p) == 0
1537 && compare_values_warnv (vr1->min, vr1->max,
1538 strict_overflow_p) == 0
1539 && compare_values_warnv (vr0->min, vr1->min,
1540 strict_overflow_p) == 0
1541 && compare_values_warnv (vr0->max, vr1->max,
1542 strict_overflow_p) == 0)
1543 return boolean_false_node;
1545 /* Otherwise, they may or may not be different. */
1546 else
1547 return NULL_TREE;
1549 else if (comp == LT_EXPR || comp == LE_EXPR)
1551 int tst;
1553 /* If VR0 is to the left of VR1, return true. */
1554 tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
1555 if ((comp == LT_EXPR && tst == -1)
1556 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1557 return boolean_true_node;
1559 /* If VR0 is to the right of VR1, return false. */
1560 tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
1561 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1562 || (comp == LE_EXPR && tst == 1))
1563 return boolean_false_node;
1565 /* Otherwise, we don't know. */
1566 return NULL_TREE;
1569 gcc_unreachable ();
1572 /* Given a value range VR, a value VAL and a comparison code COMP, return
1573 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1574 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1575 always returns false. Return NULL_TREE if it is not always
1576 possible to determine the value of the comparison. Also set
1577 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1578 assumed signed overflow is undefined. */
1580 static tree
1581 compare_range_with_value (enum tree_code comp, value_range *vr, tree val,
1582 bool *strict_overflow_p)
1584 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1585 return NULL_TREE;
1587 /* Anti-ranges need to be handled separately. */
1588 if (vr->type == VR_ANTI_RANGE)
1590 /* For anti-ranges, the only predicates that we can compute at
1591 compile time are equality and inequality. */
1592 if (comp == GT_EXPR
1593 || comp == GE_EXPR
1594 || comp == LT_EXPR
1595 || comp == LE_EXPR)
1596 return NULL_TREE;
1598 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1599 if (value_inside_range (val, vr->min, vr->max) == 1)
1600 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1602 return NULL_TREE;
1605 if (comp == EQ_EXPR)
1607 /* EQ_EXPR may only be computed if VR represents exactly
1608 one value. */
1609 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0)
1611 int cmp = compare_values_warnv (vr->min, val, strict_overflow_p);
1612 if (cmp == 0)
1613 return boolean_true_node;
1614 else if (cmp == -1 || cmp == 1 || cmp == 2)
1615 return boolean_false_node;
1617 else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1
1618 || compare_values_warnv (vr->max, val, strict_overflow_p) == -1)
1619 return boolean_false_node;
1621 return NULL_TREE;
1623 else if (comp == NE_EXPR)
1625 /* If VAL is not inside VR, then they are always different. */
1626 if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1
1627 || compare_values_warnv (vr->min, val, strict_overflow_p) == 1)
1628 return boolean_true_node;
1630 /* If VR represents exactly one value equal to VAL, then return
1631 false. */
1632 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0
1633 && compare_values_warnv (vr->min, val, strict_overflow_p) == 0)
1634 return boolean_false_node;
1636 /* Otherwise, they may or may not be different. */
1637 return NULL_TREE;
1639 else if (comp == LT_EXPR || comp == LE_EXPR)
1641 int tst;
1643 /* If VR is to the left of VAL, return true. */
1644 tst = compare_values_warnv (vr->max, val, strict_overflow_p);
1645 if ((comp == LT_EXPR && tst == -1)
1646 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1647 return boolean_true_node;
1649 /* If VR is to the right of VAL, return false. */
1650 tst = compare_values_warnv (vr->min, val, strict_overflow_p);
1651 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1652 || (comp == LE_EXPR && tst == 1))
1653 return boolean_false_node;
1655 /* Otherwise, we don't know. */
1656 return NULL_TREE;
1658 else if (comp == GT_EXPR || comp == GE_EXPR)
1660 int tst;
1662 /* If VR is to the right of VAL, return true. */
1663 tst = compare_values_warnv (vr->min, val, strict_overflow_p);
1664 if ((comp == GT_EXPR && tst == 1)
1665 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1666 return boolean_true_node;
1668 /* If VR is to the left of VAL, return false. */
1669 tst = compare_values_warnv (vr->max, val, strict_overflow_p);
1670 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1671 || (comp == GE_EXPR && tst == -1))
1672 return boolean_false_node;
1674 /* Otherwise, we don't know. */
1675 return NULL_TREE;
1678 gcc_unreachable ();
1680 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1681 would be profitable to adjust VR using scalar evolution information
1682 for VAR. If so, update VR with the new limits. */
1684 void
1685 vr_values::adjust_range_with_scev (value_range *vr, struct loop *loop,
1686 gimple *stmt, tree var)
1688 tree init, step, chrec, tmin, tmax, min, max, type, tem;
1689 enum ev_direction dir;
1691 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1692 better opportunities than a regular range, but I'm not sure. */
1693 if (vr->type == VR_ANTI_RANGE)
1694 return;
1696 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
1698 /* Like in PR19590, scev can return a constant function. */
1699 if (is_gimple_min_invariant (chrec))
1701 set_value_range_to_value (vr, chrec, vr->equiv);
1702 return;
1705 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1706 return;
1708 init = initial_condition_in_loop_num (chrec, loop->num);
1709 tem = op_with_constant_singleton_value_range (init);
1710 if (tem)
1711 init = tem;
1712 step = evolution_part_in_loop_num (chrec, loop->num);
1713 tem = op_with_constant_singleton_value_range (step);
1714 if (tem)
1715 step = tem;
1717 /* If STEP is symbolic, we can't know whether INIT will be the
1718 minimum or maximum value in the range. Also, unless INIT is
1719 a simple expression, compare_values and possibly other functions
1720 in tree-vrp won't be able to handle it. */
1721 if (step == NULL_TREE
1722 || !is_gimple_min_invariant (step)
1723 || !valid_value_p (init))
1724 return;
1726 dir = scev_direction (chrec);
1727 if (/* Do not adjust ranges if we do not know whether the iv increases
1728 or decreases, ... */
1729 dir == EV_DIR_UNKNOWN
1730 /* ... or if it may wrap. */
1731 || scev_probably_wraps_p (NULL_TREE, init, step, stmt,
1732 get_chrec_loop (chrec), true))
1733 return;
1735 type = TREE_TYPE (var);
1736 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1737 tmin = lower_bound_in_type (type, type);
1738 else
1739 tmin = TYPE_MIN_VALUE (type);
1740 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1741 tmax = upper_bound_in_type (type, type);
1742 else
1743 tmax = TYPE_MAX_VALUE (type);
1745 /* Try to use estimated number of iterations for the loop to constrain the
1746 final value in the evolution. */
1747 if (TREE_CODE (step) == INTEGER_CST
1748 && is_gimple_val (init)
1749 && (TREE_CODE (init) != SSA_NAME
1750 || get_value_range (init)->type == VR_RANGE))
1752 widest_int nit;
1754 /* We are only entering here for loop header PHI nodes, so using
1755 the number of latch executions is the correct thing to use. */
1756 if (max_loop_iterations (loop, &nit))
1758 value_range maxvr = VR_INITIALIZER;
1759 signop sgn = TYPE_SIGN (TREE_TYPE (step));
1760 bool overflow;
1762 widest_int wtmp = wi::mul (wi::to_widest (step), nit, sgn,
1763 &overflow);
1764 /* If the multiplication overflowed we can't do a meaningful
1765 adjustment. Likewise if the result doesn't fit in the type
1766 of the induction variable. For a signed type we have to
1767 check whether the result has the expected signedness which
1768 is that of the step as number of iterations is unsigned. */
1769 if (!overflow
1770 && wi::fits_to_tree_p (wtmp, TREE_TYPE (init))
1771 && (sgn == UNSIGNED
1772 || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0)))
1774 tem = wide_int_to_tree (TREE_TYPE (init), wtmp);
1775 extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
1776 TREE_TYPE (init), init, tem);
1777 /* Likewise if the addition did. */
1778 if (maxvr.type == VR_RANGE)
1780 value_range initvr = VR_INITIALIZER;
1782 if (TREE_CODE (init) == SSA_NAME)
1783 initvr = *(get_value_range (init));
1784 else if (is_gimple_min_invariant (init))
1785 set_value_range_to_value (&initvr, init, NULL);
1786 else
1787 return;
1789 /* Check if init + nit * step overflows. Though we checked
1790 scev {init, step}_loop doesn't wrap, it is not enough
1791 because the loop may exit immediately. Overflow could
1792 happen in the plus expression in this case. */
1793 if ((dir == EV_DIR_DECREASES
1794 && compare_values (maxvr.min, initvr.min) != -1)
1795 || (dir == EV_DIR_GROWS
1796 && compare_values (maxvr.max, initvr.max) != 1))
1797 return;
1799 tmin = maxvr.min;
1800 tmax = maxvr.max;
1806 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1808 min = tmin;
1809 max = tmax;
1811 /* For VARYING or UNDEFINED ranges, just about anything we get
1812 from scalar evolutions should be better. */
1814 if (dir == EV_DIR_DECREASES)
1815 max = init;
1816 else
1817 min = init;
1819 else if (vr->type == VR_RANGE)
1821 min = vr->min;
1822 max = vr->max;
1824 if (dir == EV_DIR_DECREASES)
1826 /* INIT is the maximum value. If INIT is lower than VR->MAX
1827 but no smaller than VR->MIN, set VR->MAX to INIT. */
1828 if (compare_values (init, max) == -1)
1829 max = init;
1831 /* According to the loop information, the variable does not
1832 overflow. */
1833 if (compare_values (min, tmin) == -1)
1834 min = tmin;
1837 else
1839 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1840 if (compare_values (init, min) == 1)
1841 min = init;
1843 if (compare_values (tmax, max) == -1)
1844 max = tmax;
1847 else
1848 return;
1850 /* If we just created an invalid range with the minimum
1851 greater than the maximum, we fail conservatively.
1852 This should happen only in unreachable
1853 parts of code, or for invalid programs. */
1854 if (compare_values (min, max) == 1)
1855 return;
1857 /* Even for valid range info, sometimes overflow flag will leak in.
1858 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1859 drop them. */
1860 if (TREE_OVERFLOW_P (min))
1861 min = drop_tree_overflow (min);
1862 if (TREE_OVERFLOW_P (max))
1863 max = drop_tree_overflow (max);
1865 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1868 /* Dump value ranges of all SSA_NAMEs to FILE. */
1870 void
1871 vr_values::dump_all_value_ranges (FILE *file)
1873 size_t i;
1875 for (i = 0; i < num_vr_values; i++)
1877 if (vr_value[i])
1879 print_generic_expr (file, ssa_name (i));
1880 fprintf (file, ": ");
1881 dump_value_range (file, vr_value[i]);
1882 fprintf (file, "\n");
1886 fprintf (file, "\n");
1889 /* Initialize VRP lattice. */
1891 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
1893 values_propagated = false;
1894 num_vr_values = num_ssa_names;
1895 vr_value = XCNEWVEC (value_range *, num_vr_values);
1896 vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
1897 bitmap_obstack_initialize (&vrp_equiv_obstack);
1900 /* Free VRP lattice. */
1902 vr_values::~vr_values ()
1904 /* Free allocated memory. */
1905 free (vr_value);
1906 free (vr_phi_edge_counts);
1907 bitmap_obstack_release (&vrp_equiv_obstack);
1908 vrp_value_range_pool.release ();
1910 /* So that we can distinguish between VRP data being available
1911 and not available. */
1912 vr_value = NULL;
1913 vr_phi_edge_counts = NULL;
1917 /* A hack. */
1918 static class vr_values *x_vr_values;
1920 /* Return the singleton value-range for NAME or NAME. */
1922 static inline tree
1923 vrp_valueize (tree name)
1925 if (TREE_CODE (name) == SSA_NAME)
1927 value_range *vr = x_vr_values->get_value_range (name);
1928 if (vr->type == VR_RANGE
1929 && (TREE_CODE (vr->min) == SSA_NAME
1930 || is_gimple_min_invariant (vr->min))
1931 && vrp_operand_equal_p (vr->min, vr->max))
1932 return vr->min;
1934 return name;
1937 /* Return the singleton value-range for NAME if that is a constant
1938 but signal to not follow SSA edges. */
1940 static inline tree
1941 vrp_valueize_1 (tree name)
1943 if (TREE_CODE (name) == SSA_NAME)
1945 /* If the definition may be simulated again we cannot follow
1946 this SSA edge as the SSA propagator does not necessarily
1947 re-visit the use. */
1948 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1949 if (!gimple_nop_p (def_stmt)
1950 && prop_simulate_again_p (def_stmt))
1951 return NULL_TREE;
1952 value_range *vr = x_vr_values->get_value_range (name);
1953 if (range_int_cst_singleton_p (vr))
1954 return vr->min;
1956 return name;
1959 /* Given STMT, an assignment or call, return its LHS if the type
1960 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
1962 tree
1963 get_output_for_vrp (gimple *stmt)
1965 if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
1966 return NULL_TREE;
1968 /* We only keep track of ranges in integral and pointer types. */
1969 tree lhs = gimple_get_lhs (stmt);
1970 if (TREE_CODE (lhs) == SSA_NAME
1971 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1972 /* It is valid to have NULL MIN/MAX values on a type. See
1973 build_range_type. */
1974 && TYPE_MIN_VALUE (TREE_TYPE (lhs))
1975 && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
1976 || POINTER_TYPE_P (TREE_TYPE (lhs))))
1977 return lhs;
1979 return NULL_TREE;
1982 /* Visit assignment STMT. If it produces an interesting range, record
1983 the range in VR and set LHS to OUTPUT_P. */
1985 void
1986 vr_values::vrp_visit_assignment_or_call (gimple *stmt, tree *output_p,
1987 value_range *vr)
1989 tree lhs = get_output_for_vrp (stmt);
1990 *output_p = lhs;
1992 /* We only keep track of ranges in integral and pointer types. */
1993 if (lhs)
1995 enum gimple_code code = gimple_code (stmt);
1997 /* Try folding the statement to a constant first. */
1998 x_vr_values = this;
1999 tree tem = gimple_fold_stmt_to_constant_1 (stmt, vrp_valueize,
2000 vrp_valueize_1);
2001 x_vr_values = NULL;
2002 if (tem)
2004 if (TREE_CODE (tem) == SSA_NAME
2005 && (SSA_NAME_IS_DEFAULT_DEF (tem)
2006 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem))))
2008 extract_range_from_ssa_name (vr, tem);
2009 return;
2011 else if (is_gimple_min_invariant (tem))
2013 set_value_range_to_value (vr, tem, NULL);
2014 return;
2017 /* Then dispatch to value-range extracting functions. */
2018 if (code == GIMPLE_CALL)
2019 extract_range_basic (vr, stmt);
2020 else
2021 extract_range_from_assignment (vr, as_a <gassign *> (stmt));
2025 /* Helper that gets the value range of the SSA_NAME with version I
2026 or a symbolic range containing the SSA_NAME only if the value range
2027 is varying or undefined. */
2029 value_range
2030 vr_values::get_vr_for_comparison (int i)
2032 value_range vr = *get_value_range (ssa_name (i));
2034 /* If name N_i does not have a valid range, use N_i as its own
2035 range. This allows us to compare against names that may
2036 have N_i in their ranges. */
2037 if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
2039 vr.type = VR_RANGE;
2040 vr.min = ssa_name (i);
2041 vr.max = ssa_name (i);
2044 return vr;
2047 /* Compare all the value ranges for names equivalent to VAR with VAL
2048 using comparison code COMP. Return the same value returned by
2049 compare_range_with_value, including the setting of
2050 *STRICT_OVERFLOW_P. */
2052 tree
2053 vr_values::compare_name_with_value (enum tree_code comp, tree var, tree val,
2054 bool *strict_overflow_p, bool use_equiv_p)
2056 bitmap_iterator bi;
2057 unsigned i;
2058 bitmap e;
2059 tree retval, t;
2060 int used_strict_overflow;
2061 bool sop;
2062 value_range equiv_vr;
2064 /* Get the set of equivalences for VAR. */
2065 e = get_value_range (var)->equiv;
2067 /* Start at -1. Set it to 0 if we do a comparison without relying
2068 on overflow, or 1 if all comparisons rely on overflow. */
2069 used_strict_overflow = -1;
2071 /* Compare vars' value range with val. */
2072 equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
2073 sop = false;
2074 retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
2075 if (retval)
2076 used_strict_overflow = sop ? 1 : 0;
2078 /* If the equiv set is empty we have done all work we need to do. */
2079 if (e == NULL)
2081 if (retval
2082 && used_strict_overflow > 0)
2083 *strict_overflow_p = true;
2084 return retval;
2087 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
2089 tree name = ssa_name (i);
2090 if (! name)
2091 continue;
2093 if (! use_equiv_p
2094 && ! SSA_NAME_IS_DEFAULT_DEF (name)
2095 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name)))
2096 continue;
2098 equiv_vr = get_vr_for_comparison (i);
2099 sop = false;
2100 t = compare_range_with_value (comp, &equiv_vr, val, &sop);
2101 if (t)
2103 /* If we get different answers from different members
2104 of the equivalence set this check must be in a dead
2105 code region. Folding it to a trap representation
2106 would be correct here. For now just return don't-know. */
2107 if (retval != NULL
2108 && t != retval)
2110 retval = NULL_TREE;
2111 break;
2113 retval = t;
2115 if (!sop)
2116 used_strict_overflow = 0;
2117 else if (used_strict_overflow < 0)
2118 used_strict_overflow = 1;
2122 if (retval
2123 && used_strict_overflow > 0)
2124 *strict_overflow_p = true;
2126 return retval;
2130 /* Given a comparison code COMP and names N1 and N2, compare all the
2131 ranges equivalent to N1 against all the ranges equivalent to N2
2132 to determine the value of N1 COMP N2. Return the same value
2133 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2134 whether we relied on undefined signed overflow in the comparison. */
2137 tree
2138 vr_values::compare_names (enum tree_code comp, tree n1, tree n2,
2139 bool *strict_overflow_p)
2141 tree t, retval;
2142 bitmap e1, e2;
2143 bitmap_iterator bi1, bi2;
2144 unsigned i1, i2;
2145 int used_strict_overflow;
2146 static bitmap_obstack *s_obstack = NULL;
2147 static bitmap s_e1 = NULL, s_e2 = NULL;
2149 /* Compare the ranges of every name equivalent to N1 against the
2150 ranges of every name equivalent to N2. */
2151 e1 = get_value_range (n1)->equiv;
2152 e2 = get_value_range (n2)->equiv;
2154 /* Use the fake bitmaps if e1 or e2 are not available. */
2155 if (s_obstack == NULL)
2157 s_obstack = XNEW (bitmap_obstack);
2158 bitmap_obstack_initialize (s_obstack);
2159 s_e1 = BITMAP_ALLOC (s_obstack);
2160 s_e2 = BITMAP_ALLOC (s_obstack);
2162 if (e1 == NULL)
2163 e1 = s_e1;
2164 if (e2 == NULL)
2165 e2 = s_e2;
2167 /* Add N1 and N2 to their own set of equivalences to avoid
2168 duplicating the body of the loop just to check N1 and N2
2169 ranges. */
2170 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
2171 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
2173 /* If the equivalence sets have a common intersection, then the two
2174 names can be compared without checking their ranges. */
2175 if (bitmap_intersect_p (e1, e2))
2177 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2178 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2180 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
2181 ? boolean_true_node
2182 : boolean_false_node;
2185 /* Start at -1. Set it to 0 if we do a comparison without relying
2186 on overflow, or 1 if all comparisons rely on overflow. */
2187 used_strict_overflow = -1;
2189 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2190 N2 to their own set of equivalences to avoid duplicating the body
2191 of the loop just to check N1 and N2 ranges. */
2192 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
2194 if (! ssa_name (i1))
2195 continue;
2197 value_range vr1 = get_vr_for_comparison (i1);
2199 t = retval = NULL_TREE;
2200 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
2202 if (! ssa_name (i2))
2203 continue;
2205 bool sop = false;
2207 value_range vr2 = get_vr_for_comparison (i2);
2209 t = compare_ranges (comp, &vr1, &vr2, &sop);
2210 if (t)
2212 /* If we get different answers from different members
2213 of the equivalence set this check must be in a dead
2214 code region. Folding it to a trap representation
2215 would be correct here. For now just return don't-know. */
2216 if (retval != NULL
2217 && t != retval)
2219 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2220 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2221 return NULL_TREE;
2223 retval = t;
2225 if (!sop)
2226 used_strict_overflow = 0;
2227 else if (used_strict_overflow < 0)
2228 used_strict_overflow = 1;
2232 if (retval)
2234 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2235 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2236 if (used_strict_overflow > 0)
2237 *strict_overflow_p = true;
2238 return retval;
2242 /* None of the equivalent ranges are useful in computing this
2243 comparison. */
2244 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2245 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2246 return NULL_TREE;
2249 /* Helper function for vrp_evaluate_conditional_warnv & other
2250 optimizers. */
2252 tree
2253 vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2254 (enum tree_code code, tree op0, tree op1, bool * strict_overflow_p)
2256 value_range *vr0, *vr1;
2258 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
2259 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
2261 tree res = NULL_TREE;
2262 if (vr0 && vr1)
2263 res = compare_ranges (code, vr0, vr1, strict_overflow_p);
2264 if (!res && vr0)
2265 res = compare_range_with_value (code, vr0, op1, strict_overflow_p);
2266 if (!res && vr1)
2267 res = (compare_range_with_value
2268 (swap_tree_comparison (code), vr1, op0, strict_overflow_p));
2269 return res;
2272 /* Helper function for vrp_evaluate_conditional_warnv. */
2274 tree
2275 vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
2276 tree op0, tree op1,
2277 bool use_equiv_p,
2278 bool *strict_overflow_p,
2279 bool *only_ranges)
2281 tree ret;
2282 if (only_ranges)
2283 *only_ranges = true;
2285 /* We only deal with integral and pointer types. */
2286 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2287 && !POINTER_TYPE_P (TREE_TYPE (op0)))
2288 return NULL_TREE;
2290 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2291 as a simple equality test, then prefer that over its current form
2292 for evaluation.
2294 An overflow test which collapses to an equality test can always be
2295 expressed as a comparison of one argument against zero. Overflow
2296 occurs when the chosen argument is zero and does not occur if the
2297 chosen argument is not zero. */
2298 tree x;
2299 if (overflow_comparison_p (code, op0, op1, use_equiv_p, &x))
2301 wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
2302 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2303 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2304 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2305 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2306 if (integer_zerop (x))
2308 op1 = x;
2309 code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
2311 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2312 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2313 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2314 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2315 else if (wi::to_wide (x) == max - 1)
2317 op0 = op1;
2318 op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
2319 code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
2323 if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
2324 (code, op0, op1, strict_overflow_p)))
2325 return ret;
2326 if (only_ranges)
2327 *only_ranges = false;
2328 /* Do not use compare_names during propagation, it's quadratic. */
2329 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME
2330 && use_equiv_p)
2331 return compare_names (code, op0, op1, strict_overflow_p);
2332 else if (TREE_CODE (op0) == SSA_NAME)
2333 return compare_name_with_value (code, op0, op1,
2334 strict_overflow_p, use_equiv_p);
2335 else if (TREE_CODE (op1) == SSA_NAME)
2336 return compare_name_with_value (swap_tree_comparison (code), op1, op0,
2337 strict_overflow_p, use_equiv_p);
2338 return NULL_TREE;
2341 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2342 information. Return NULL if the conditional can not be evaluated.
2343 The ranges of all the names equivalent with the operands in COND
2344 will be used when trying to compute the value. If the result is
2345 based on undefined signed overflow, issue a warning if
2346 appropriate. */
2348 tree
2349 vr_values::vrp_evaluate_conditional (tree_code code, tree op0,
2350 tree op1, gimple *stmt)
2352 bool sop;
2353 tree ret;
2354 bool only_ranges;
2356 /* Some passes and foldings leak constants with overflow flag set
2357 into the IL. Avoid doing wrong things with these and bail out. */
2358 if ((TREE_CODE (op0) == INTEGER_CST
2359 && TREE_OVERFLOW (op0))
2360 || (TREE_CODE (op1) == INTEGER_CST
2361 && TREE_OVERFLOW (op1)))
2362 return NULL_TREE;
2364 sop = false;
2365 ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop,
2366 &only_ranges);
2368 if (ret && sop)
2370 enum warn_strict_overflow_code wc;
2371 const char* warnmsg;
2373 if (is_gimple_min_invariant (ret))
2375 wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
2376 warnmsg = G_("assuming signed overflow does not occur when "
2377 "simplifying conditional to constant");
2379 else
2381 wc = WARN_STRICT_OVERFLOW_COMPARISON;
2382 warnmsg = G_("assuming signed overflow does not occur when "
2383 "simplifying conditional");
2386 if (issue_strict_overflow_warning (wc))
2388 location_t location;
2390 if (!gimple_has_location (stmt))
2391 location = input_location;
2392 else
2393 location = gimple_location (stmt);
2394 warning_at (location, OPT_Wstrict_overflow, "%s", warnmsg);
2398 if (warn_type_limits
2399 && ret && only_ranges
2400 && TREE_CODE_CLASS (code) == tcc_comparison
2401 && TREE_CODE (op0) == SSA_NAME)
2403 /* If the comparison is being folded and the operand on the LHS
2404 is being compared against a constant value that is outside of
2405 the natural range of OP0's type, then the predicate will
2406 always fold regardless of the value of OP0. If -Wtype-limits
2407 was specified, emit a warning. */
2408 tree type = TREE_TYPE (op0);
2409 value_range *vr0 = get_value_range (op0);
2411 if (vr0->type == VR_RANGE
2412 && INTEGRAL_TYPE_P (type)
2413 && vrp_val_is_min (vr0->min)
2414 && vrp_val_is_max (vr0->max)
2415 && is_gimple_min_invariant (op1))
2417 location_t location;
2419 if (!gimple_has_location (stmt))
2420 location = input_location;
2421 else
2422 location = gimple_location (stmt);
2424 warning_at (location, OPT_Wtype_limits,
2425 integer_zerop (ret)
2426 ? G_("comparison always false "
2427 "due to limited range of data type")
2428 : G_("comparison always true "
2429 "due to limited range of data type"));
2433 return ret;
2437 /* Visit conditional statement STMT. If we can determine which edge
2438 will be taken out of STMT's basic block, record it in
2439 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2441 void
2442 vr_values::vrp_visit_cond_stmt (gcond *stmt, edge *taken_edge_p)
2444 tree val;
2446 *taken_edge_p = NULL;
2448 if (dump_file && (dump_flags & TDF_DETAILS))
2450 tree use;
2451 ssa_op_iter i;
2453 fprintf (dump_file, "\nVisiting conditional with predicate: ");
2454 print_gimple_stmt (dump_file, stmt, 0);
2455 fprintf (dump_file, "\nWith known ranges\n");
2457 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
2459 fprintf (dump_file, "\t");
2460 print_generic_expr (dump_file, use);
2461 fprintf (dump_file, ": ");
2462 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
2465 fprintf (dump_file, "\n");
2468 /* Compute the value of the predicate COND by checking the known
2469 ranges of each of its operands.
2471 Note that we cannot evaluate all the equivalent ranges here
2472 because those ranges may not yet be final and with the current
2473 propagation strategy, we cannot determine when the value ranges
2474 of the names in the equivalence set have changed.
2476 For instance, given the following code fragment
2478 i_5 = PHI <8, i_13>
2480 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2481 if (i_14 == 1)
2484 Assume that on the first visit to i_14, i_5 has the temporary
2485 range [8, 8] because the second argument to the PHI function is
2486 not yet executable. We derive the range ~[0, 0] for i_14 and the
2487 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2488 the first time, since i_14 is equivalent to the range [8, 8], we
2489 determine that the predicate is always false.
2491 On the next round of propagation, i_13 is determined to be
2492 VARYING, which causes i_5 to drop down to VARYING. So, another
2493 visit to i_14 is scheduled. In this second visit, we compute the
2494 exact same range and equivalence set for i_14, namely ~[0, 0] and
2495 { i_5 }. But we did not have the previous range for i_5
2496 registered, so vrp_visit_assignment thinks that the range for
2497 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2498 is not visited again, which stops propagation from visiting
2499 statements in the THEN clause of that if().
2501 To properly fix this we would need to keep the previous range
2502 value for the names in the equivalence set. This way we would've
2503 discovered that from one visit to the other i_5 changed from
2504 range [8, 8] to VR_VARYING.
2506 However, fixing this apparent limitation may not be worth the
2507 additional checking. Testing on several code bases (GCC, DLV,
2508 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2509 4 more predicates folded in SPEC. */
2511 bool sop;
2512 val = vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt),
2513 gimple_cond_lhs (stmt),
2514 gimple_cond_rhs (stmt),
2515 false, &sop, NULL);
2516 if (val)
2517 *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
2519 if (dump_file && (dump_flags & TDF_DETAILS))
2521 fprintf (dump_file, "\nPredicate evaluates to: ");
2522 if (val == NULL_TREE)
2523 fprintf (dump_file, "DON'T KNOW\n");
2524 else
2525 print_generic_stmt (dump_file, val);
2529 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2530 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2531 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2532 Returns true if the default label is not needed. */
2534 static bool
2535 find_case_label_ranges (gswitch *stmt, value_range *vr, size_t *min_idx1,
2536 size_t *max_idx1, size_t *min_idx2,
2537 size_t *max_idx2)
2539 size_t i, j, k, l;
2540 unsigned int n = gimple_switch_num_labels (stmt);
2541 bool take_default;
2542 tree case_low, case_high;
2543 tree min = vr->min, max = vr->max;
2545 gcc_checking_assert (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE);
2547 take_default = !find_case_label_range (stmt, min, max, &i, &j);
2549 /* Set second range to emtpy. */
2550 *min_idx2 = 1;
2551 *max_idx2 = 0;
2553 if (vr->type == VR_RANGE)
2555 *min_idx1 = i;
2556 *max_idx1 = j;
2557 return !take_default;
2560 /* Set first range to all case labels. */
2561 *min_idx1 = 1;
2562 *max_idx1 = n - 1;
2564 if (i > j)
2565 return false;
2567 /* Make sure all the values of case labels [i , j] are contained in
2568 range [MIN, MAX]. */
2569 case_low = CASE_LOW (gimple_switch_label (stmt, i));
2570 case_high = CASE_HIGH (gimple_switch_label (stmt, j));
2571 if (tree_int_cst_compare (case_low, min) < 0)
2572 i += 1;
2573 if (case_high != NULL_TREE
2574 && tree_int_cst_compare (max, case_high) < 0)
2575 j -= 1;
2577 if (i > j)
2578 return false;
2580 /* If the range spans case labels [i, j], the corresponding anti-range spans
2581 the labels [1, i - 1] and [j + 1, n - 1]. */
2582 k = j + 1;
2583 l = n - 1;
2584 if (k > l)
2586 k = 1;
2587 l = 0;
2590 j = i - 1;
2591 i = 1;
2592 if (i > j)
2594 i = k;
2595 j = l;
2596 k = 1;
2597 l = 0;
2600 *min_idx1 = i;
2601 *max_idx1 = j;
2602 *min_idx2 = k;
2603 *max_idx2 = l;
2604 return false;
2607 /* Visit switch statement STMT. If we can determine which edge
2608 will be taken out of STMT's basic block, record it in
2609 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2611 void
2612 vr_values::vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p)
2614 tree op, val;
2615 value_range *vr;
2616 size_t i = 0, j = 0, k, l;
2617 bool take_default;
2619 *taken_edge_p = NULL;
2620 op = gimple_switch_index (stmt);
2621 if (TREE_CODE (op) != SSA_NAME)
2622 return;
2624 vr = get_value_range (op);
2625 if (dump_file && (dump_flags & TDF_DETAILS))
2627 fprintf (dump_file, "\nVisiting switch expression with operand ");
2628 print_generic_expr (dump_file, op);
2629 fprintf (dump_file, " with known range ");
2630 dump_value_range (dump_file, vr);
2631 fprintf (dump_file, "\n");
2634 if ((vr->type != VR_RANGE
2635 && vr->type != VR_ANTI_RANGE)
2636 || symbolic_range_p (vr))
2637 return;
2639 /* Find the single edge that is taken from the switch expression. */
2640 take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
2642 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2643 label */
2644 if (j < i)
2646 gcc_assert (take_default);
2647 val = gimple_switch_default_label (stmt);
2649 else
2651 /* Check if labels with index i to j and maybe the default label
2652 are all reaching the same label. */
2654 val = gimple_switch_label (stmt, i);
2655 if (take_default
2656 && CASE_LABEL (gimple_switch_default_label (stmt))
2657 != CASE_LABEL (val))
2659 if (dump_file && (dump_flags & TDF_DETAILS))
2660 fprintf (dump_file, " not a single destination for this "
2661 "range\n");
2662 return;
2664 for (++i; i <= j; ++i)
2666 if (CASE_LABEL (gimple_switch_label (stmt, i)) != CASE_LABEL (val))
2668 if (dump_file && (dump_flags & TDF_DETAILS))
2669 fprintf (dump_file, " not a single destination for this "
2670 "range\n");
2671 return;
2674 for (; k <= l; ++k)
2676 if (CASE_LABEL (gimple_switch_label (stmt, k)) != CASE_LABEL (val))
2678 if (dump_file && (dump_flags & TDF_DETAILS))
2679 fprintf (dump_file, " not a single destination for this "
2680 "range\n");
2681 return;
2686 *taken_edge_p = find_edge (gimple_bb (stmt),
2687 label_to_block (CASE_LABEL (val)));
2689 if (dump_file && (dump_flags & TDF_DETAILS))
2691 fprintf (dump_file, " will take edge to ");
2692 print_generic_stmt (dump_file, CASE_LABEL (val));
2697 /* Evaluate statement STMT. If the statement produces a useful range,
2698 set VR and corepsponding OUTPUT_P.
2700 If STMT is a conditional branch and we can determine its truth
2701 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2703 void
2704 vr_values::extract_range_from_stmt (gimple *stmt, edge *taken_edge_p,
2705 tree *output_p, value_range *vr)
2708 if (dump_file && (dump_flags & TDF_DETAILS))
2710 fprintf (dump_file, "\nVisiting statement:\n");
2711 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2714 if (!stmt_interesting_for_vrp (stmt))
2715 gcc_assert (stmt_ends_bb_p (stmt));
2716 else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
2717 vrp_visit_assignment_or_call (stmt, output_p, vr);
2718 else if (gimple_code (stmt) == GIMPLE_COND)
2719 vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p);
2720 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2721 vrp_visit_switch_stmt (as_a <gswitch *> (stmt), taken_edge_p);
2724 /* Visit all arguments for PHI node PHI that flow through executable
2725 edges. If a valid value range can be derived from all the incoming
2726 value ranges, set a new range in VR_RESULT. */
2728 void
2729 vr_values::extract_range_from_phi_node (gphi *phi, value_range *vr_result)
2731 size_t i;
2732 tree lhs = PHI_RESULT (phi);
2733 value_range *lhs_vr = get_value_range (lhs);
2734 bool first = true;
2735 int edges, old_edges;
2736 struct loop *l;
2738 if (dump_file && (dump_flags & TDF_DETAILS))
2740 fprintf (dump_file, "\nVisiting PHI node: ");
2741 print_gimple_stmt (dump_file, phi, 0, dump_flags);
2744 bool may_simulate_backedge_again = false;
2745 edges = 0;
2746 for (i = 0; i < gimple_phi_num_args (phi); i++)
2748 edge e = gimple_phi_arg_edge (phi, i);
2750 if (dump_file && (dump_flags & TDF_DETAILS))
2752 fprintf (dump_file,
2753 " Argument #%d (%d -> %d %sexecutable)\n",
2754 (int) i, e->src->index, e->dest->index,
2755 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2758 if (e->flags & EDGE_EXECUTABLE)
2760 tree arg = PHI_ARG_DEF (phi, i);
2761 value_range vr_arg;
2763 ++edges;
2765 if (TREE_CODE (arg) == SSA_NAME)
2767 /* See if we are eventually going to change one of the args. */
2768 gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
2769 if (! gimple_nop_p (def_stmt)
2770 && prop_simulate_again_p (def_stmt)
2771 && e->flags & EDGE_DFS_BACK)
2772 may_simulate_backedge_again = true;
2774 vr_arg = *(get_value_range (arg));
2775 /* Do not allow equivalences or symbolic ranges to leak in from
2776 backedges. That creates invalid equivalencies.
2777 See PR53465 and PR54767. */
2778 if (e->flags & EDGE_DFS_BACK)
2780 if (vr_arg.type == VR_RANGE
2781 || vr_arg.type == VR_ANTI_RANGE)
2783 vr_arg.equiv = NULL;
2784 if (symbolic_range_p (&vr_arg))
2786 vr_arg.type = VR_VARYING;
2787 vr_arg.min = NULL_TREE;
2788 vr_arg.max = NULL_TREE;
2792 else
2794 /* If the non-backedge arguments range is VR_VARYING then
2795 we can still try recording a simple equivalence. */
2796 if (vr_arg.type == VR_VARYING)
2798 vr_arg.type = VR_RANGE;
2799 vr_arg.min = arg;
2800 vr_arg.max = arg;
2801 vr_arg.equiv = NULL;
2805 else
2807 if (TREE_OVERFLOW_P (arg))
2808 arg = drop_tree_overflow (arg);
2810 vr_arg.type = VR_RANGE;
2811 vr_arg.min = arg;
2812 vr_arg.max = arg;
2813 vr_arg.equiv = NULL;
2816 if (dump_file && (dump_flags & TDF_DETAILS))
2818 fprintf (dump_file, "\t");
2819 print_generic_expr (dump_file, arg, dump_flags);
2820 fprintf (dump_file, ": ");
2821 dump_value_range (dump_file, &vr_arg);
2822 fprintf (dump_file, "\n");
2825 if (first)
2826 copy_value_range (vr_result, &vr_arg);
2827 else
2828 vrp_meet (vr_result, &vr_arg);
2829 first = false;
2831 if (vr_result->type == VR_VARYING)
2832 break;
2836 if (vr_result->type == VR_VARYING)
2837 goto varying;
2838 else if (vr_result->type == VR_UNDEFINED)
2839 goto update_range;
2841 old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
2842 vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
2844 /* To prevent infinite iterations in the algorithm, derive ranges
2845 when the new value is slightly bigger or smaller than the
2846 previous one. We don't do this if we have seen a new executable
2847 edge; this helps us avoid an infinity for conditionals
2848 which are not in a loop. If the old value-range was VR_UNDEFINED
2849 use the updated range and iterate one more time. If we will not
2850 simulate this PHI again via the backedge allow us to iterate. */
2851 if (edges > 0
2852 && gimple_phi_num_args (phi) > 1
2853 && edges == old_edges
2854 && lhs_vr->type != VR_UNDEFINED
2855 && may_simulate_backedge_again)
2857 /* Compare old and new ranges, fall back to varying if the
2858 values are not comparable. */
2859 int cmp_min = compare_values (lhs_vr->min, vr_result->min);
2860 if (cmp_min == -2)
2861 goto varying;
2862 int cmp_max = compare_values (lhs_vr->max, vr_result->max);
2863 if (cmp_max == -2)
2864 goto varying;
2866 /* For non VR_RANGE or for pointers fall back to varying if
2867 the range changed. */
2868 if ((lhs_vr->type != VR_RANGE || vr_result->type != VR_RANGE
2869 || POINTER_TYPE_P (TREE_TYPE (lhs)))
2870 && (cmp_min != 0 || cmp_max != 0))
2871 goto varying;
2873 /* If the new minimum is larger than the previous one
2874 retain the old value. If the new minimum value is smaller
2875 than the previous one and not -INF go all the way to -INF + 1.
2876 In the first case, to avoid infinite bouncing between different
2877 minimums, and in the other case to avoid iterating millions of
2878 times to reach -INF. Going to -INF + 1 also lets the following
2879 iteration compute whether there will be any overflow, at the
2880 expense of one additional iteration. */
2881 if (cmp_min < 0)
2882 vr_result->min = lhs_vr->min;
2883 else if (cmp_min > 0
2884 && !vrp_val_is_min (vr_result->min))
2885 vr_result->min
2886 = int_const_binop (PLUS_EXPR,
2887 vrp_val_min (TREE_TYPE (vr_result->min)),
2888 build_int_cst (TREE_TYPE (vr_result->min), 1));
2890 /* Similarly for the maximum value. */
2891 if (cmp_max > 0)
2892 vr_result->max = lhs_vr->max;
2893 else if (cmp_max < 0
2894 && !vrp_val_is_max (vr_result->max))
2895 vr_result->max
2896 = int_const_binop (MINUS_EXPR,
2897 vrp_val_max (TREE_TYPE (vr_result->min)),
2898 build_int_cst (TREE_TYPE (vr_result->min), 1));
2900 /* If we dropped either bound to +-INF then if this is a loop
2901 PHI node SCEV may known more about its value-range. */
2902 if (cmp_min > 0 || cmp_min < 0
2903 || cmp_max < 0 || cmp_max > 0)
2904 goto scev_check;
2906 goto infinite_check;
2909 goto update_range;
2911 varying:
2912 set_value_range_to_varying (vr_result);
2914 scev_check:
2915 /* If this is a loop PHI node SCEV may known more about its value-range.
2916 scev_check can be reached from two paths, one is a fall through from above
2917 "varying" label, the other is direct goto from code block which tries to
2918 avoid infinite simulation. */
2919 if ((l = loop_containing_stmt (phi))
2920 && l->header == gimple_bb (phi))
2921 adjust_range_with_scev (vr_result, l, phi, lhs);
2923 infinite_check:
2924 /* If we will end up with a (-INF, +INF) range, set it to
2925 VARYING. Same if the previous max value was invalid for
2926 the type and we end up with vr_result.min > vr_result.max. */
2927 if ((vr_result->type == VR_RANGE || vr_result->type == VR_ANTI_RANGE)
2928 && !((vrp_val_is_max (vr_result->max) && vrp_val_is_min (vr_result->min))
2929 || compare_values (vr_result->min, vr_result->max) > 0))
2931 else
2932 set_value_range_to_varying (vr_result);
2934 /* If the new range is different than the previous value, keep
2935 iterating. */
2936 update_range:
2937 return;
2940 /* Simplify boolean operations if the source is known
2941 to be already a boolean. */
2942 bool
2943 vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi,
2944 gimple *stmt)
2946 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
2947 tree lhs, op0, op1;
2948 bool need_conversion;
2950 /* We handle only !=/== case here. */
2951 gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
2953 op0 = gimple_assign_rhs1 (stmt);
2954 if (!op_with_boolean_value_range_p (op0))
2955 return false;
2957 op1 = gimple_assign_rhs2 (stmt);
2958 if (!op_with_boolean_value_range_p (op1))
2959 return false;
2961 /* Reduce number of cases to handle to NE_EXPR. As there is no
2962 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
2963 if (rhs_code == EQ_EXPR)
2965 if (TREE_CODE (op1) == INTEGER_CST)
2966 op1 = int_const_binop (BIT_XOR_EXPR, op1,
2967 build_int_cst (TREE_TYPE (op1), 1));
2968 else
2969 return false;
2972 lhs = gimple_assign_lhs (stmt);
2973 need_conversion
2974 = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0));
2976 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
2977 if (need_conversion
2978 && !TYPE_UNSIGNED (TREE_TYPE (op0))
2979 && TYPE_PRECISION (TREE_TYPE (op0)) == 1
2980 && TYPE_PRECISION (TREE_TYPE (lhs)) > 1)
2981 return false;
2983 /* For A != 0 we can substitute A itself. */
2984 if (integer_zerop (op1))
2985 gimple_assign_set_rhs_with_ops (gsi,
2986 need_conversion
2987 ? NOP_EXPR : TREE_CODE (op0), op0);
2988 /* For A != B we substitute A ^ B. Either with conversion. */
2989 else if (need_conversion)
2991 tree tem = make_ssa_name (TREE_TYPE (op0));
2992 gassign *newop
2993 = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1);
2994 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
2995 if (INTEGRAL_TYPE_P (TREE_TYPE (tem))
2996 && TYPE_PRECISION (TREE_TYPE (tem)) > 1)
2997 set_range_info (tem, VR_RANGE,
2998 wi::zero (TYPE_PRECISION (TREE_TYPE (tem))),
2999 wi::one (TYPE_PRECISION (TREE_TYPE (tem))));
3000 gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem);
3002 /* Or without. */
3003 else
3004 gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1);
3005 update_stmt (gsi_stmt (*gsi));
3006 fold_stmt (gsi, follow_single_use_edges);
3008 return true;
3011 /* Simplify a division or modulo operator to a right shift or bitwise and
3012 if the first operand is unsigned or is greater than zero and the second
3013 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
3014 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
3015 optimize it into just op0 if op0's range is known to be a subset of
3016 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3017 modulo. */
3019 bool
3020 vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator *gsi,
3021 gimple *stmt)
3023 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3024 tree val = NULL;
3025 tree op0 = gimple_assign_rhs1 (stmt);
3026 tree op1 = gimple_assign_rhs2 (stmt);
3027 tree op0min = NULL_TREE, op0max = NULL_TREE;
3028 tree op1min = op1;
3029 value_range *vr = NULL;
3031 if (TREE_CODE (op0) == INTEGER_CST)
3033 op0min = op0;
3034 op0max = op0;
3036 else
3038 vr = get_value_range (op0);
3039 if (range_int_cst_p (vr))
3041 op0min = vr->min;
3042 op0max = vr->max;
3046 if (rhs_code == TRUNC_MOD_EXPR
3047 && TREE_CODE (op1) == SSA_NAME)
3049 value_range *vr1 = get_value_range (op1);
3050 if (range_int_cst_p (vr1))
3051 op1min = vr1->min;
3053 if (rhs_code == TRUNC_MOD_EXPR
3054 && TREE_CODE (op1min) == INTEGER_CST
3055 && tree_int_cst_sgn (op1min) == 1
3056 && op0max
3057 && tree_int_cst_lt (op0max, op1min))
3059 if (TYPE_UNSIGNED (TREE_TYPE (op0))
3060 || tree_int_cst_sgn (op0min) >= 0
3061 || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min),
3062 op0min))
3064 /* If op0 already has the range op0 % op1 has,
3065 then TRUNC_MOD_EXPR won't change anything. */
3066 gimple_assign_set_rhs_from_tree (gsi, op0);
3067 return true;
3071 if (TREE_CODE (op0) != SSA_NAME)
3072 return false;
3074 if (!integer_pow2p (op1))
3076 /* X % -Y can be only optimized into X % Y either if
3077 X is not INT_MIN, or Y is not -1. Fold it now, as after
3078 remove_range_assertions the range info might be not available
3079 anymore. */
3080 if (rhs_code == TRUNC_MOD_EXPR
3081 && fold_stmt (gsi, follow_single_use_edges))
3082 return true;
3083 return false;
3086 if (TYPE_UNSIGNED (TREE_TYPE (op0)))
3087 val = integer_one_node;
3088 else
3090 bool sop = false;
3092 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
3094 if (val
3095 && sop
3096 && integer_onep (val)
3097 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3099 location_t location;
3101 if (!gimple_has_location (stmt))
3102 location = input_location;
3103 else
3104 location = gimple_location (stmt);
3105 warning_at (location, OPT_Wstrict_overflow,
3106 "assuming signed overflow does not occur when "
3107 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3111 if (val && integer_onep (val))
3113 tree t;
3115 if (rhs_code == TRUNC_DIV_EXPR)
3117 t = build_int_cst (integer_type_node, tree_log2 (op1));
3118 gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
3119 gimple_assign_set_rhs1 (stmt, op0);
3120 gimple_assign_set_rhs2 (stmt, t);
3122 else
3124 t = build_int_cst (TREE_TYPE (op1), 1);
3125 t = int_const_binop (MINUS_EXPR, op1, t);
3126 t = fold_convert (TREE_TYPE (op0), t);
3128 gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
3129 gimple_assign_set_rhs1 (stmt, op0);
3130 gimple_assign_set_rhs2 (stmt, t);
3133 update_stmt (stmt);
3134 fold_stmt (gsi, follow_single_use_edges);
3135 return true;
3138 return false;
3141 /* Simplify a min or max if the ranges of the two operands are
3142 disjoint. Return true if we do simplify. */
3144 bool
3145 vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator *gsi,
3146 gimple *stmt)
3148 tree op0 = gimple_assign_rhs1 (stmt);
3149 tree op1 = gimple_assign_rhs2 (stmt);
3150 bool sop = false;
3151 tree val;
3153 val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3154 (LE_EXPR, op0, op1, &sop));
3155 if (!val)
3157 sop = false;
3158 val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3159 (LT_EXPR, op0, op1, &sop));
3162 if (val)
3164 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3166 location_t location;
3168 if (!gimple_has_location (stmt))
3169 location = input_location;
3170 else
3171 location = gimple_location (stmt);
3172 warning_at (location, OPT_Wstrict_overflow,
3173 "assuming signed overflow does not occur when "
3174 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3177 /* VAL == TRUE -> OP0 < or <= op1
3178 VAL == FALSE -> OP0 > or >= op1. */
3179 tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
3180 == integer_zerop (val)) ? op0 : op1;
3181 gimple_assign_set_rhs_from_tree (gsi, res);
3182 return true;
3185 return false;
3188 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3189 ABS_EXPR. If the operand is <= 0, then simplify the
3190 ABS_EXPR into a NEGATE_EXPR. */
3192 bool
3193 vr_values::simplify_abs_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
3195 tree op = gimple_assign_rhs1 (stmt);
3196 value_range *vr = get_value_range (op);
3198 if (vr)
3200 tree val = NULL;
3201 bool sop = false;
3203 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop);
3204 if (!val)
3206 /* The range is neither <= 0 nor > 0. Now see if it is
3207 either < 0 or >= 0. */
3208 sop = false;
3209 val = compare_range_with_value (LT_EXPR, vr, integer_zero_node,
3210 &sop);
3213 if (val)
3215 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3217 location_t location;
3219 if (!gimple_has_location (stmt))
3220 location = input_location;
3221 else
3222 location = gimple_location (stmt);
3223 warning_at (location, OPT_Wstrict_overflow,
3224 "assuming signed overflow does not occur when "
3225 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3228 gimple_assign_set_rhs1 (stmt, op);
3229 if (integer_zerop (val))
3230 gimple_assign_set_rhs_code (stmt, SSA_NAME);
3231 else
3232 gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
3233 update_stmt (stmt);
3234 fold_stmt (gsi, follow_single_use_edges);
3235 return true;
3239 return false;
3242 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3243 If all the bits that are being cleared by & are already
3244 known to be zero from VR, or all the bits that are being
3245 set by | are already known to be one from VR, the bit
3246 operation is redundant. */
3248 bool
3249 vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi,
3250 gimple *stmt)
3252 tree op0 = gimple_assign_rhs1 (stmt);
3253 tree op1 = gimple_assign_rhs2 (stmt);
3254 tree op = NULL_TREE;
3255 value_range vr0 = VR_INITIALIZER;
3256 value_range vr1 = VR_INITIALIZER;
3257 wide_int may_be_nonzero0, may_be_nonzero1;
3258 wide_int must_be_nonzero0, must_be_nonzero1;
3259 wide_int mask;
3261 if (TREE_CODE (op0) == SSA_NAME)
3262 vr0 = *(get_value_range (op0));
3263 else if (is_gimple_min_invariant (op0))
3264 set_value_range_to_value (&vr0, op0, NULL);
3265 else
3266 return false;
3268 if (TREE_CODE (op1) == SSA_NAME)
3269 vr1 = *(get_value_range (op1));
3270 else if (is_gimple_min_invariant (op1))
3271 set_value_range_to_value (&vr1, op1, NULL);
3272 else
3273 return false;
3275 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op0), &vr0, &may_be_nonzero0,
3276 &must_be_nonzero0))
3277 return false;
3278 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op1), &vr1, &may_be_nonzero1,
3279 &must_be_nonzero1))
3280 return false;
3282 switch (gimple_assign_rhs_code (stmt))
3284 case BIT_AND_EXPR:
3285 mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
3286 if (mask == 0)
3288 op = op0;
3289 break;
3291 mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
3292 if (mask == 0)
3294 op = op1;
3295 break;
3297 break;
3298 case BIT_IOR_EXPR:
3299 mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
3300 if (mask == 0)
3302 op = op1;
3303 break;
3305 mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
3306 if (mask == 0)
3308 op = op0;
3309 break;
3311 break;
3312 default:
3313 gcc_unreachable ();
3316 if (op == NULL_TREE)
3317 return false;
3319 gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op);
3320 update_stmt (gsi_stmt (*gsi));
3321 return true;
3324 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3325 a known value range VR.
3327 If there is one and only one value which will satisfy the
3328 conditional, then return that value. Else return NULL.
3330 If signed overflow must be undefined for the value to satisfy
3331 the conditional, then set *STRICT_OVERFLOW_P to true. */
3333 static tree
3334 test_for_singularity (enum tree_code cond_code, tree op0,
3335 tree op1, value_range *vr)
3337 tree min = NULL;
3338 tree max = NULL;
3340 /* Extract minimum/maximum values which satisfy the conditional as it was
3341 written. */
3342 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
3344 min = TYPE_MIN_VALUE (TREE_TYPE (op0));
3346 max = op1;
3347 if (cond_code == LT_EXPR)
3349 tree one = build_int_cst (TREE_TYPE (op0), 1);
3350 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
3351 /* Signal to compare_values_warnv this expr doesn't overflow. */
3352 if (EXPR_P (max))
3353 TREE_NO_WARNING (max) = 1;
3356 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
3358 max = TYPE_MAX_VALUE (TREE_TYPE (op0));
3360 min = op1;
3361 if (cond_code == GT_EXPR)
3363 tree one = build_int_cst (TREE_TYPE (op0), 1);
3364 min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
3365 /* Signal to compare_values_warnv this expr doesn't overflow. */
3366 if (EXPR_P (min))
3367 TREE_NO_WARNING (min) = 1;
3371 /* Now refine the minimum and maximum values using any
3372 value range information we have for op0. */
3373 if (min && max)
3375 if (compare_values (vr->min, min) == 1)
3376 min = vr->min;
3377 if (compare_values (vr->max, max) == -1)
3378 max = vr->max;
3380 /* If the new min/max values have converged to a single value,
3381 then there is only one value which can satisfy the condition,
3382 return that value. */
3383 if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
3384 return min;
3386 return NULL;
3389 /* Return whether the value range *VR fits in an integer type specified
3390 by PRECISION and UNSIGNED_P. */
3392 static bool
3393 range_fits_type_p (value_range *vr, unsigned dest_precision, signop dest_sgn)
3395 tree src_type;
3396 unsigned src_precision;
3397 widest_int tem;
3398 signop src_sgn;
3400 /* We can only handle integral and pointer types. */
3401 src_type = TREE_TYPE (vr->min);
3402 if (!INTEGRAL_TYPE_P (src_type)
3403 && !POINTER_TYPE_P (src_type))
3404 return false;
3406 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3407 and so is an identity transform. */
3408 src_precision = TYPE_PRECISION (TREE_TYPE (vr->min));
3409 src_sgn = TYPE_SIGN (src_type);
3410 if ((src_precision < dest_precision
3411 && !(dest_sgn == UNSIGNED && src_sgn == SIGNED))
3412 || (src_precision == dest_precision && src_sgn == dest_sgn))
3413 return true;
3415 /* Now we can only handle ranges with constant bounds. */
3416 if (vr->type != VR_RANGE
3417 || TREE_CODE (vr->min) != INTEGER_CST
3418 || TREE_CODE (vr->max) != INTEGER_CST)
3419 return false;
3421 /* For sign changes, the MSB of the wide_int has to be clear.
3422 An unsigned value with its MSB set cannot be represented by
3423 a signed wide_int, while a negative value cannot be represented
3424 by an unsigned wide_int. */
3425 if (src_sgn != dest_sgn
3426 && (wi::lts_p (wi::to_wide (vr->min), 0)
3427 || wi::lts_p (wi::to_wide (vr->max), 0)))
3428 return false;
3430 /* Then we can perform the conversion on both ends and compare
3431 the result for equality. */
3432 tem = wi::ext (wi::to_widest (vr->min), dest_precision, dest_sgn);
3433 if (tem != wi::to_widest (vr->min))
3434 return false;
3435 tem = wi::ext (wi::to_widest (vr->max), dest_precision, dest_sgn);
3436 if (tem != wi::to_widest (vr->max))
3437 return false;
3439 return true;
3442 /* Simplify a conditional using a relational operator to an equality
3443 test if the range information indicates only one value can satisfy
3444 the original conditional. */
3446 bool
3447 vr_values::simplify_cond_using_ranges_1 (gcond *stmt)
3449 tree op0 = gimple_cond_lhs (stmt);
3450 tree op1 = gimple_cond_rhs (stmt);
3451 enum tree_code cond_code = gimple_cond_code (stmt);
3453 if (cond_code != NE_EXPR
3454 && cond_code != EQ_EXPR
3455 && TREE_CODE (op0) == SSA_NAME
3456 && INTEGRAL_TYPE_P (TREE_TYPE (op0))
3457 && is_gimple_min_invariant (op1))
3459 value_range *vr = get_value_range (op0);
3461 /* If we have range information for OP0, then we might be
3462 able to simplify this conditional. */
3463 if (vr->type == VR_RANGE)
3465 tree new_tree = test_for_singularity (cond_code, op0, op1, vr);
3466 if (new_tree)
3468 if (dump_file)
3470 fprintf (dump_file, "Simplified relational ");
3471 print_gimple_stmt (dump_file, stmt, 0);
3472 fprintf (dump_file, " into ");
3475 gimple_cond_set_code (stmt, EQ_EXPR);
3476 gimple_cond_set_lhs (stmt, op0);
3477 gimple_cond_set_rhs (stmt, new_tree);
3479 update_stmt (stmt);
3481 if (dump_file)
3483 print_gimple_stmt (dump_file, stmt, 0);
3484 fprintf (dump_file, "\n");
3487 return true;
3490 /* Try again after inverting the condition. We only deal
3491 with integral types here, so no need to worry about
3492 issues with inverting FP comparisons. */
3493 new_tree = test_for_singularity
3494 (invert_tree_comparison (cond_code, false),
3495 op0, op1, vr);
3496 if (new_tree)
3498 if (dump_file)
3500 fprintf (dump_file, "Simplified relational ");
3501 print_gimple_stmt (dump_file, stmt, 0);
3502 fprintf (dump_file, " into ");
3505 gimple_cond_set_code (stmt, NE_EXPR);
3506 gimple_cond_set_lhs (stmt, op0);
3507 gimple_cond_set_rhs (stmt, new_tree);
3509 update_stmt (stmt);
3511 if (dump_file)
3513 print_gimple_stmt (dump_file, stmt, 0);
3514 fprintf (dump_file, "\n");
3517 return true;
3521 return false;
3524 /* STMT is a conditional at the end of a basic block.
3526 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3527 was set via a type conversion, try to replace the SSA_NAME with the RHS
3528 of the type conversion. Doing so makes the conversion dead which helps
3529 subsequent passes. */
3531 void
3532 vr_values::simplify_cond_using_ranges_2 (gcond *stmt)
3534 tree op0 = gimple_cond_lhs (stmt);
3535 tree op1 = gimple_cond_rhs (stmt);
3537 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3538 see if OP0 was set by a type conversion where the source of
3539 the conversion is another SSA_NAME with a range that fits
3540 into the range of OP0's type.
3542 If so, the conversion is redundant as the earlier SSA_NAME can be
3543 used for the comparison directly if we just massage the constant in the
3544 comparison. */
3545 if (TREE_CODE (op0) == SSA_NAME
3546 && TREE_CODE (op1) == INTEGER_CST)
3548 gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
3549 tree innerop;
3551 if (!is_gimple_assign (def_stmt)
3552 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
3553 return;
3555 innerop = gimple_assign_rhs1 (def_stmt);
3557 if (TREE_CODE (innerop) == SSA_NAME
3558 && !POINTER_TYPE_P (TREE_TYPE (innerop))
3559 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
3560 && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
3562 value_range *vr = get_value_range (innerop);
3564 if (range_int_cst_p (vr)
3565 && range_fits_type_p (vr,
3566 TYPE_PRECISION (TREE_TYPE (op0)),
3567 TYPE_SIGN (TREE_TYPE (op0)))
3568 && int_fits_type_p (op1, TREE_TYPE (innerop)))
3570 tree newconst = fold_convert (TREE_TYPE (innerop), op1);
3571 gimple_cond_set_lhs (stmt, innerop);
3572 gimple_cond_set_rhs (stmt, newconst);
3573 update_stmt (stmt);
3574 if (dump_file && (dump_flags & TDF_DETAILS))
3576 fprintf (dump_file, "Folded into: ");
3577 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3578 fprintf (dump_file, "\n");
3585 /* Simplify a switch statement using the value range of the switch
3586 argument. */
3588 bool
3589 vr_values::simplify_switch_using_ranges (gswitch *stmt)
3591 tree op = gimple_switch_index (stmt);
3592 value_range *vr = NULL;
3593 bool take_default;
3594 edge e;
3595 edge_iterator ei;
3596 size_t i = 0, j = 0, n, n2;
3597 tree vec2;
3598 switch_update su;
3599 size_t k = 1, l = 0;
3601 if (TREE_CODE (op) == SSA_NAME)
3603 vr = get_value_range (op);
3605 /* We can only handle integer ranges. */
3606 if ((vr->type != VR_RANGE
3607 && vr->type != VR_ANTI_RANGE)
3608 || symbolic_range_p (vr))
3609 return false;
3611 /* Find case label for min/max of the value range. */
3612 take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
3614 else if (TREE_CODE (op) == INTEGER_CST)
3616 take_default = !find_case_label_index (stmt, 1, op, &i);
3617 if (take_default)
3619 i = 1;
3620 j = 0;
3622 else
3624 j = i;
3627 else
3628 return false;
3630 n = gimple_switch_num_labels (stmt);
3632 /* We can truncate the case label ranges that partially overlap with OP's
3633 value range. */
3634 size_t min_idx = 1, max_idx = 0;
3635 if (vr != NULL)
3636 find_case_label_range (stmt, vr->min, vr->max, &min_idx, &max_idx);
3637 if (min_idx <= max_idx)
3639 tree min_label = gimple_switch_label (stmt, min_idx);
3640 tree max_label = gimple_switch_label (stmt, max_idx);
3642 /* Avoid changing the type of the case labels when truncating. */
3643 tree case_label_type = TREE_TYPE (CASE_LOW (min_label));
3644 tree vr_min = fold_convert (case_label_type, vr->min);
3645 tree vr_max = fold_convert (case_label_type, vr->max);
3647 if (vr->type == VR_RANGE)
3649 /* If OP's value range is [2,8] and the low label range is
3650 0 ... 3, truncate the label's range to 2 .. 3. */
3651 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3652 && CASE_HIGH (min_label) != NULL_TREE
3653 && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
3654 CASE_LOW (min_label) = vr_min;
3656 /* If OP's value range is [2,8] and the high label range is
3657 7 ... 10, truncate the label's range to 7 .. 8. */
3658 if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
3659 && CASE_HIGH (max_label) != NULL_TREE
3660 && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
3661 CASE_HIGH (max_label) = vr_max;
3663 else if (vr->type == VR_ANTI_RANGE)
3665 tree one_cst = build_one_cst (case_label_type);
3667 if (min_label == max_label)
3669 /* If OP's value range is ~[7,8] and the label's range is
3670 7 ... 10, truncate the label's range to 9 ... 10. */
3671 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) == 0
3672 && CASE_HIGH (min_label) != NULL_TREE
3673 && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) > 0)
3674 CASE_LOW (min_label)
3675 = int_const_binop (PLUS_EXPR, vr_max, one_cst);
3677 /* If OP's value range is ~[7,8] and the label's range is
3678 5 ... 8, truncate the label's range to 5 ... 6. */
3679 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3680 && CASE_HIGH (min_label) != NULL_TREE
3681 && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) == 0)
3682 CASE_HIGH (min_label)
3683 = int_const_binop (MINUS_EXPR, vr_min, one_cst);
3685 else
3687 /* If OP's value range is ~[2,8] and the low label range is
3688 0 ... 3, truncate the label's range to 0 ... 1. */
3689 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3690 && CASE_HIGH (min_label) != NULL_TREE
3691 && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
3692 CASE_HIGH (min_label)
3693 = int_const_binop (MINUS_EXPR, vr_min, one_cst);
3695 /* If OP's value range is ~[2,8] and the high label range is
3696 7 ... 10, truncate the label's range to 9 ... 10. */
3697 if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
3698 && CASE_HIGH (max_label) != NULL_TREE
3699 && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
3700 CASE_LOW (max_label)
3701 = int_const_binop (PLUS_EXPR, vr_max, one_cst);
3705 /* Canonicalize singleton case ranges. */
3706 if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label)))
3707 CASE_HIGH (min_label) = NULL_TREE;
3708 if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label)))
3709 CASE_HIGH (max_label) = NULL_TREE;
3712 /* We can also eliminate case labels that lie completely outside OP's value
3713 range. */
3715 /* Bail out if this is just all edges taken. */
3716 if (i == 1
3717 && j == n - 1
3718 && take_default)
3719 return false;
3721 /* Build a new vector of taken case labels. */
3722 vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default);
3723 n2 = 0;
3725 /* Add the default edge, if necessary. */
3726 if (take_default)
3727 TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt);
3729 for (; i <= j; ++i, ++n2)
3730 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i);
3732 for (; k <= l; ++k, ++n2)
3733 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k);
3735 /* Mark needed edges. */
3736 for (i = 0; i < n2; ++i)
3738 e = find_edge (gimple_bb (stmt),
3739 label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
3740 e->aux = (void *)-1;
3743 /* Queue not needed edges for later removal. */
3744 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
3746 if (e->aux == (void *)-1)
3748 e->aux = NULL;
3749 continue;
3752 if (dump_file && (dump_flags & TDF_DETAILS))
3754 fprintf (dump_file, "removing unreachable case label\n");
3756 to_remove_edges.safe_push (e);
3757 e->flags &= ~EDGE_EXECUTABLE;
3760 /* And queue an update for the stmt. */
3761 su.stmt = stmt;
3762 su.vec = vec2;
3763 to_update_switch_stmts.safe_push (su);
3764 return false;
3767 /* Simplify an integral conversion from an SSA name in STMT. */
3769 static bool
3770 simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
3772 tree innerop, middleop, finaltype;
3773 gimple *def_stmt;
3774 signop inner_sgn, middle_sgn, final_sgn;
3775 unsigned inner_prec, middle_prec, final_prec;
3776 widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
3778 finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
3779 if (!INTEGRAL_TYPE_P (finaltype))
3780 return false;
3781 middleop = gimple_assign_rhs1 (stmt);
3782 def_stmt = SSA_NAME_DEF_STMT (middleop);
3783 if (!is_gimple_assign (def_stmt)
3784 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
3785 return false;
3786 innerop = gimple_assign_rhs1 (def_stmt);
3787 if (TREE_CODE (innerop) != SSA_NAME
3788 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
3789 return false;
3791 /* Get the value-range of the inner operand. Use get_range_info in
3792 case innerop was created during substitute-and-fold. */
3793 wide_int imin, imax;
3794 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop))
3795 || get_range_info (innerop, &imin, &imax) != VR_RANGE)
3796 return false;
3797 innermin = widest_int::from (imin, TYPE_SIGN (TREE_TYPE (innerop)));
3798 innermax = widest_int::from (imax, TYPE_SIGN (TREE_TYPE (innerop)));
3800 /* Simulate the conversion chain to check if the result is equal if
3801 the middle conversion is removed. */
3802 inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
3803 middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
3804 final_prec = TYPE_PRECISION (finaltype);
3806 /* If the first conversion is not injective, the second must not
3807 be widening. */
3808 if (wi::gtu_p (innermax - innermin,
3809 wi::mask <widest_int> (middle_prec, false))
3810 && middle_prec < final_prec)
3811 return false;
3812 /* We also want a medium value so that we can track the effect that
3813 narrowing conversions with sign change have. */
3814 inner_sgn = TYPE_SIGN (TREE_TYPE (innerop));
3815 if (inner_sgn == UNSIGNED)
3816 innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false);
3817 else
3818 innermed = 0;
3819 if (wi::cmp (innermin, innermed, inner_sgn) >= 0
3820 || wi::cmp (innermed, innermax, inner_sgn) >= 0)
3821 innermed = innermin;
3823 middle_sgn = TYPE_SIGN (TREE_TYPE (middleop));
3824 middlemin = wi::ext (innermin, middle_prec, middle_sgn);
3825 middlemed = wi::ext (innermed, middle_prec, middle_sgn);
3826 middlemax = wi::ext (innermax, middle_prec, middle_sgn);
3828 /* Require that the final conversion applied to both the original
3829 and the intermediate range produces the same result. */
3830 final_sgn = TYPE_SIGN (finaltype);
3831 if (wi::ext (middlemin, final_prec, final_sgn)
3832 != wi::ext (innermin, final_prec, final_sgn)
3833 || wi::ext (middlemed, final_prec, final_sgn)
3834 != wi::ext (innermed, final_prec, final_sgn)
3835 || wi::ext (middlemax, final_prec, final_sgn)
3836 != wi::ext (innermax, final_prec, final_sgn))
3837 return false;
3839 gimple_assign_set_rhs1 (stmt, innerop);
3840 fold_stmt (gsi, follow_single_use_edges);
3841 return true;
3844 /* Simplify a conversion from integral SSA name to float in STMT. */
3846 bool
3847 vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi,
3848 gimple *stmt)
3850 tree rhs1 = gimple_assign_rhs1 (stmt);
3851 value_range *vr = get_value_range (rhs1);
3852 scalar_float_mode fltmode
3853 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
3854 scalar_int_mode mode;
3855 tree tem;
3856 gassign *conv;
3858 /* We can only handle constant ranges. */
3859 if (vr->type != VR_RANGE
3860 || TREE_CODE (vr->min) != INTEGER_CST
3861 || TREE_CODE (vr->max) != INTEGER_CST)
3862 return false;
3864 /* First check if we can use a signed type in place of an unsigned. */
3865 scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1));
3866 if (TYPE_UNSIGNED (TREE_TYPE (rhs1))
3867 && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing
3868 && range_fits_type_p (vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED))
3869 mode = rhs_mode;
3870 /* If we can do the conversion in the current input mode do nothing. */
3871 else if (can_float_p (fltmode, rhs_mode,
3872 TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing)
3873 return false;
3874 /* Otherwise search for a mode we can use, starting from the narrowest
3875 integer mode available. */
3876 else
3878 mode = NARROWEST_INT_MODE;
3879 for (;;)
3881 /* If we cannot do a signed conversion to float from mode
3882 or if the value-range does not fit in the signed type
3883 try with a wider mode. */
3884 if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing
3885 && range_fits_type_p (vr, GET_MODE_PRECISION (mode), SIGNED))
3886 break;
3888 /* But do not widen the input. Instead leave that to the
3889 optabs expansion code. */
3890 if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
3891 || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1)))
3892 return false;
3896 /* It works, insert a truncation or sign-change before the
3897 float conversion. */
3898 tem = make_ssa_name (build_nonstandard_integer_type
3899 (GET_MODE_PRECISION (mode), 0));
3900 conv = gimple_build_assign (tem, NOP_EXPR, rhs1);
3901 gsi_insert_before (gsi, conv, GSI_SAME_STMT);
3902 gimple_assign_set_rhs1 (stmt, tem);
3903 fold_stmt (gsi, follow_single_use_edges);
3905 return true;
3908 /* Simplify an internal fn call using ranges if possible. */
3910 bool
3911 vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi,
3912 gimple *stmt)
3914 enum tree_code subcode;
3915 bool is_ubsan = false;
3916 bool ovf = false;
3917 switch (gimple_call_internal_fn (stmt))
3919 case IFN_UBSAN_CHECK_ADD:
3920 subcode = PLUS_EXPR;
3921 is_ubsan = true;
3922 break;
3923 case IFN_UBSAN_CHECK_SUB:
3924 subcode = MINUS_EXPR;
3925 is_ubsan = true;
3926 break;
3927 case IFN_UBSAN_CHECK_MUL:
3928 subcode = MULT_EXPR;
3929 is_ubsan = true;
3930 break;
3931 case IFN_ADD_OVERFLOW:
3932 subcode = PLUS_EXPR;
3933 break;
3934 case IFN_SUB_OVERFLOW:
3935 subcode = MINUS_EXPR;
3936 break;
3937 case IFN_MUL_OVERFLOW:
3938 subcode = MULT_EXPR;
3939 break;
3940 default:
3941 return false;
3944 tree op0 = gimple_call_arg (stmt, 0);
3945 tree op1 = gimple_call_arg (stmt, 1);
3946 tree type;
3947 if (is_ubsan)
3949 type = TREE_TYPE (op0);
3950 if (VECTOR_TYPE_P (type))
3951 return false;
3953 else if (gimple_call_lhs (stmt) == NULL_TREE)
3954 return false;
3955 else
3956 type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt)));
3957 if (!check_for_binary_op_overflow (subcode, type, op0, op1, &ovf)
3958 || (is_ubsan && ovf))
3959 return false;
3961 gimple *g;
3962 location_t loc = gimple_location (stmt);
3963 if (is_ubsan)
3964 g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1);
3965 else
3967 int prec = TYPE_PRECISION (type);
3968 tree utype = type;
3969 if (ovf
3970 || !useless_type_conversion_p (type, TREE_TYPE (op0))
3971 || !useless_type_conversion_p (type, TREE_TYPE (op1)))
3972 utype = build_nonstandard_integer_type (prec, 1);
3973 if (TREE_CODE (op0) == INTEGER_CST)
3974 op0 = fold_convert (utype, op0);
3975 else if (!useless_type_conversion_p (utype, TREE_TYPE (op0)))
3977 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0);
3978 gimple_set_location (g, loc);
3979 gsi_insert_before (gsi, g, GSI_SAME_STMT);
3980 op0 = gimple_assign_lhs (g);
3982 if (TREE_CODE (op1) == INTEGER_CST)
3983 op1 = fold_convert (utype, op1);
3984 else if (!useless_type_conversion_p (utype, TREE_TYPE (op1)))
3986 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1);
3987 gimple_set_location (g, loc);
3988 gsi_insert_before (gsi, g, GSI_SAME_STMT);
3989 op1 = gimple_assign_lhs (g);
3991 g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1);
3992 gimple_set_location (g, loc);
3993 gsi_insert_before (gsi, g, GSI_SAME_STMT);
3994 if (utype != type)
3996 g = gimple_build_assign (make_ssa_name (type), NOP_EXPR,
3997 gimple_assign_lhs (g));
3998 gimple_set_location (g, loc);
3999 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4001 g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR,
4002 gimple_assign_lhs (g),
4003 build_int_cst (type, ovf));
4005 gimple_set_location (g, loc);
4006 gsi_replace (gsi, g, false);
4007 return true;
4010 /* Return true if VAR is a two-valued variable. Set a and b with the
4011 two-values when it is true. Return false otherwise. */
4013 bool
4014 vr_values::two_valued_val_range_p (tree var, tree *a, tree *b)
4016 value_range *vr = get_value_range (var);
4017 if ((vr->type != VR_RANGE
4018 && vr->type != VR_ANTI_RANGE)
4019 || TREE_CODE (vr->min) != INTEGER_CST
4020 || TREE_CODE (vr->max) != INTEGER_CST)
4021 return false;
4023 if (vr->type == VR_RANGE
4024 && wi::to_wide (vr->max) - wi::to_wide (vr->min) == 1)
4026 *a = vr->min;
4027 *b = vr->max;
4028 return true;
4031 /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
4032 if (vr->type == VR_ANTI_RANGE
4033 && (wi::to_wide (vr->min)
4034 - wi::to_wide (vrp_val_min (TREE_TYPE (var)))) == 1
4035 && (wi::to_wide (vrp_val_max (TREE_TYPE (var)))
4036 - wi::to_wide (vr->max)) == 1)
4038 *a = vrp_val_min (TREE_TYPE (var));
4039 *b = vrp_val_max (TREE_TYPE (var));
4040 return true;
4043 return false;
4046 /* Simplify STMT using ranges if possible. */
4048 bool
4049 vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
4051 gimple *stmt = gsi_stmt (*gsi);
4052 if (is_gimple_assign (stmt))
4054 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
4055 tree rhs1 = gimple_assign_rhs1 (stmt);
4056 tree rhs2 = gimple_assign_rhs2 (stmt);
4057 tree lhs = gimple_assign_lhs (stmt);
4058 tree val1 = NULL_TREE, val2 = NULL_TREE;
4059 use_operand_p use_p;
4060 gimple *use_stmt;
4062 /* Convert:
4063 LHS = CST BINOP VAR
4064 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4066 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4068 Also handles:
4069 LHS = VAR BINOP CST
4070 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4072 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4074 if (TREE_CODE_CLASS (rhs_code) == tcc_binary
4075 && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4076 && ((TREE_CODE (rhs1) == INTEGER_CST
4077 && TREE_CODE (rhs2) == SSA_NAME)
4078 || (TREE_CODE (rhs2) == INTEGER_CST
4079 && TREE_CODE (rhs1) == SSA_NAME))
4080 && single_imm_use (lhs, &use_p, &use_stmt)
4081 && gimple_code (use_stmt) == GIMPLE_COND)
4084 tree new_rhs1 = NULL_TREE;
4085 tree new_rhs2 = NULL_TREE;
4086 tree cmp_var = NULL_TREE;
4088 if (TREE_CODE (rhs2) == SSA_NAME
4089 && two_valued_val_range_p (rhs2, &val1, &val2))
4091 /* Optimize RHS1 OP [VAL1, VAL2]. */
4092 new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
4093 new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
4094 cmp_var = rhs2;
4096 else if (TREE_CODE (rhs1) == SSA_NAME
4097 && two_valued_val_range_p (rhs1, &val1, &val2))
4099 /* Optimize [VAL1, VAL2] OP RHS2. */
4100 new_rhs1 = int_const_binop (rhs_code, val1, rhs2);
4101 new_rhs2 = int_const_binop (rhs_code, val2, rhs2);
4102 cmp_var = rhs1;
4105 /* If we could not find two-vals or the optimzation is invalid as
4106 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4107 if (new_rhs1 && new_rhs2)
4109 tree cond = build2 (EQ_EXPR, boolean_type_node, cmp_var, val1);
4110 gimple_assign_set_rhs_with_ops (gsi,
4111 COND_EXPR, cond,
4112 new_rhs1,
4113 new_rhs2);
4114 update_stmt (gsi_stmt (*gsi));
4115 fold_stmt (gsi, follow_single_use_edges);
4116 return true;
4120 switch (rhs_code)
4122 case EQ_EXPR:
4123 case NE_EXPR:
4124 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4125 if the RHS is zero or one, and the LHS are known to be boolean
4126 values. */
4127 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4128 return simplify_truth_ops_using_ranges (gsi, stmt);
4129 break;
4131 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4132 and BIT_AND_EXPR respectively if the first operand is greater
4133 than zero and the second operand is an exact power of two.
4134 Also optimize TRUNC_MOD_EXPR away if the second operand is
4135 constant and the first operand already has the right value
4136 range. */
4137 case TRUNC_DIV_EXPR:
4138 case TRUNC_MOD_EXPR:
4139 if ((TREE_CODE (rhs1) == SSA_NAME
4140 || TREE_CODE (rhs1) == INTEGER_CST)
4141 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4142 return simplify_div_or_mod_using_ranges (gsi, stmt);
4143 break;
4145 /* Transform ABS (X) into X or -X as appropriate. */
4146 case ABS_EXPR:
4147 if (TREE_CODE (rhs1) == SSA_NAME
4148 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4149 return simplify_abs_using_ranges (gsi, stmt);
4150 break;
4152 case BIT_AND_EXPR:
4153 case BIT_IOR_EXPR:
4154 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4155 if all the bits being cleared are already cleared or
4156 all the bits being set are already set. */
4157 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4158 return simplify_bit_ops_using_ranges (gsi, stmt);
4159 break;
4161 CASE_CONVERT:
4162 if (TREE_CODE (rhs1) == SSA_NAME
4163 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4164 return simplify_conversion_using_ranges (gsi, stmt);
4165 break;
4167 case FLOAT_EXPR:
4168 if (TREE_CODE (rhs1) == SSA_NAME
4169 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4170 return simplify_float_conversion_using_ranges (gsi, stmt);
4171 break;
4173 case MIN_EXPR:
4174 case MAX_EXPR:
4175 return simplify_min_or_max_using_ranges (gsi, stmt);
4177 default:
4178 break;
4181 else if (gimple_code (stmt) == GIMPLE_COND)
4182 return simplify_cond_using_ranges_1 (as_a <gcond *> (stmt));
4183 else if (gimple_code (stmt) == GIMPLE_SWITCH)
4184 return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
4185 else if (is_gimple_call (stmt)
4186 && gimple_call_internal_p (stmt))
4187 return simplify_internal_call_using_ranges (gsi, stmt);
4189 return false;
4192 void
4193 vr_values::set_vr_value (tree var, value_range *vr)
4195 if (SSA_NAME_VERSION (var) >= num_vr_values)
4196 return;
4197 vr_value[SSA_NAME_VERSION (var)] = vr;