Daily bump.
[official-gcc.git] / gcc / vr-values.c
blob74f813e7334f78c864c9bb358a7000192060c6cc
1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2018 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);
449 /* For pointer arithmetic, we only keep track of pointer equality
450 and inequality. If we arrive here with unfolded conditions like
451 _1 > _1 do not derive anything. */
452 if ((POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
453 || limit == var)
455 set_value_range_to_varying (vr_p);
456 return;
459 /* If LIMIT is another SSA name and LIMIT has a range of its own,
460 try to use LIMIT's range to avoid creating symbolic ranges
461 unnecessarily. */
462 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
464 /* LIMIT's range is only interesting if it has any useful information. */
465 if (! limit_vr
466 || limit_vr->type == VR_UNDEFINED
467 || limit_vr->type == VR_VARYING
468 || (symbolic_range_p (limit_vr)
469 && ! (limit_vr->type == VR_RANGE
470 && (limit_vr->min == limit_vr->max
471 || operand_equal_p (limit_vr->min, limit_vr->max, 0)))))
472 limit_vr = NULL;
474 /* Initially, the new range has the same set of equivalences of
475 VAR's range. This will be revised before returning the final
476 value. Since assertions may be chained via mutually exclusive
477 predicates, we will need to trim the set of equivalences before
478 we are done. */
479 gcc_assert (vr_p->equiv == NULL);
480 add_equivalence (&vr_p->equiv, var);
482 /* Extract a new range based on the asserted comparison for VAR and
483 LIMIT's value range. Notice that if LIMIT has an anti-range, we
484 will only use it for equality comparisons (EQ_EXPR). For any
485 other kind of assertion, we cannot derive a range from LIMIT's
486 anti-range that can be used to describe the new range. For
487 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
488 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
489 no single range for x_2 that could describe LE_EXPR, so we might
490 as well build the range [b_4, +INF] for it.
491 One special case we handle is extracting a range from a
492 range test encoded as (unsigned)var + CST <= limit. */
493 if (TREE_CODE (op) == NOP_EXPR
494 || TREE_CODE (op) == PLUS_EXPR)
496 if (TREE_CODE (op) == PLUS_EXPR)
498 min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)),
499 TREE_OPERAND (op, 1));
500 max = int_const_binop (PLUS_EXPR, limit, min);
501 op = TREE_OPERAND (op, 0);
503 else
505 min = build_int_cst (TREE_TYPE (var), 0);
506 max = limit;
509 /* Make sure to not set TREE_OVERFLOW on the final type
510 conversion. We are willingly interpreting large positive
511 unsigned values as negative signed values here. */
512 min = force_fit_type (TREE_TYPE (var), wi::to_widest (min), 0, false);
513 max = force_fit_type (TREE_TYPE (var), wi::to_widest (max), 0, false);
515 /* We can transform a max, min range to an anti-range or
516 vice-versa. Use set_and_canonicalize_value_range which does
517 this for us. */
518 if (cond_code == LE_EXPR)
519 set_and_canonicalize_value_range (vr_p, VR_RANGE,
520 min, max, vr_p->equiv);
521 else if (cond_code == GT_EXPR)
522 set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
523 min, max, vr_p->equiv);
524 else
525 gcc_unreachable ();
527 else if (cond_code == EQ_EXPR)
529 enum value_range_type range_type;
531 if (limit_vr)
533 range_type = limit_vr->type;
534 min = limit_vr->min;
535 max = limit_vr->max;
537 else
539 range_type = VR_RANGE;
540 min = limit;
541 max = limit;
544 set_value_range (vr_p, range_type, min, max, vr_p->equiv);
546 /* When asserting the equality VAR == LIMIT and LIMIT is another
547 SSA name, the new range will also inherit the equivalence set
548 from LIMIT. */
549 if (TREE_CODE (limit) == SSA_NAME)
550 add_equivalence (&vr_p->equiv, limit);
552 else if (cond_code == NE_EXPR)
554 /* As described above, when LIMIT's range is an anti-range and
555 this assertion is an inequality (NE_EXPR), then we cannot
556 derive anything from the anti-range. For instance, if
557 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
558 not imply that VAR's range is [0, 0]. So, in the case of
559 anti-ranges, we just assert the inequality using LIMIT and
560 not its anti-range.
562 If LIMIT_VR is a range, we can only use it to build a new
563 anti-range if LIMIT_VR is a single-valued range. For
564 instance, if LIMIT_VR is [0, 1], the predicate
565 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
566 Rather, it means that for value 0 VAR should be ~[0, 0]
567 and for value 1, VAR should be ~[1, 1]. We cannot
568 represent these ranges.
570 The only situation in which we can build a valid
571 anti-range is when LIMIT_VR is a single-valued range
572 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
573 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
574 if (limit_vr
575 && limit_vr->type == VR_RANGE
576 && compare_values (limit_vr->min, limit_vr->max) == 0)
578 min = limit_vr->min;
579 max = limit_vr->max;
581 else
583 /* In any other case, we cannot use LIMIT's range to build a
584 valid anti-range. */
585 min = max = limit;
588 /* If MIN and MAX cover the whole range for their type, then
589 just use the original LIMIT. */
590 if (INTEGRAL_TYPE_P (type)
591 && vrp_val_is_min (min)
592 && vrp_val_is_max (max))
593 min = max = limit;
595 set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
596 min, max, vr_p->equiv);
598 else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
600 min = TYPE_MIN_VALUE (type);
602 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
603 max = limit;
604 else
606 /* If LIMIT_VR is of the form [N1, N2], we need to build the
607 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
608 LT_EXPR. */
609 max = limit_vr->max;
612 /* If the maximum value forces us to be out of bounds, simply punt.
613 It would be pointless to try and do anything more since this
614 all should be optimized away above us. */
615 if (cond_code == LT_EXPR
616 && compare_values (max, min) == 0)
617 set_value_range_to_varying (vr_p);
618 else
620 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
621 if (cond_code == LT_EXPR)
623 if (TYPE_PRECISION (TREE_TYPE (max)) == 1
624 && !TYPE_UNSIGNED (TREE_TYPE (max)))
625 max = fold_build2 (PLUS_EXPR, TREE_TYPE (max), max,
626 build_int_cst (TREE_TYPE (max), -1));
627 else
628 max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max,
629 build_int_cst (TREE_TYPE (max), 1));
630 /* Signal to compare_values_warnv this expr doesn't overflow. */
631 if (EXPR_P (max))
632 TREE_NO_WARNING (max) = 1;
635 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
638 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
640 max = TYPE_MAX_VALUE (type);
642 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
643 min = limit;
644 else
646 /* If LIMIT_VR is of the form [N1, N2], we need to build the
647 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
648 GT_EXPR. */
649 min = limit_vr->min;
652 /* If the minimum value forces us to be out of bounds, simply punt.
653 It would be pointless to try and do anything more since this
654 all should be optimized away above us. */
655 if (cond_code == GT_EXPR
656 && compare_values (min, max) == 0)
657 set_value_range_to_varying (vr_p);
658 else
660 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
661 if (cond_code == GT_EXPR)
663 if (TYPE_PRECISION (TREE_TYPE (min)) == 1
664 && !TYPE_UNSIGNED (TREE_TYPE (min)))
665 min = fold_build2 (MINUS_EXPR, TREE_TYPE (min), min,
666 build_int_cst (TREE_TYPE (min), -1));
667 else
668 min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min,
669 build_int_cst (TREE_TYPE (min), 1));
670 /* Signal to compare_values_warnv this expr doesn't overflow. */
671 if (EXPR_P (min))
672 TREE_NO_WARNING (min) = 1;
675 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
678 else
679 gcc_unreachable ();
681 /* Finally intersect the new range with what we already know about var. */
682 vrp_intersect_ranges (vr_p, get_value_range (var));
685 /* Extract value range information from an ASSERT_EXPR EXPR and store
686 it in *VR_P. */
688 void
689 vr_values::extract_range_from_assert (value_range *vr_p, tree expr)
691 tree var = ASSERT_EXPR_VAR (expr);
692 tree cond = ASSERT_EXPR_COND (expr);
693 tree limit, op;
694 enum tree_code cond_code;
695 gcc_assert (COMPARISON_CLASS_P (cond));
697 /* Find VAR in the ASSERT_EXPR conditional. */
698 if (var == TREE_OPERAND (cond, 0)
699 || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
700 || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
702 /* If the predicate is of the form VAR COMP LIMIT, then we just
703 take LIMIT from the RHS and use the same comparison code. */
704 cond_code = TREE_CODE (cond);
705 limit = TREE_OPERAND (cond, 1);
706 op = TREE_OPERAND (cond, 0);
708 else
710 /* If the predicate is of the form LIMIT COMP VAR, then we need
711 to flip around the comparison code to create the proper range
712 for VAR. */
713 cond_code = swap_tree_comparison (TREE_CODE (cond));
714 limit = TREE_OPERAND (cond, 0);
715 op = TREE_OPERAND (cond, 1);
717 extract_range_for_var_from_comparison_expr (var, cond_code, op,
718 limit, vr_p);
721 /* Extract range information from SSA name VAR and store it in VR. If
722 VAR has an interesting range, use it. Otherwise, create the
723 range [VAR, VAR] and return it. This is useful in situations where
724 we may have conditionals testing values of VARYING names. For
725 instance,
727 x_3 = y_5;
728 if (x_3 > y_5)
731 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
732 always false. */
734 void
735 vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
737 value_range *var_vr = get_value_range (var);
739 if (var_vr->type != VR_VARYING)
740 copy_value_range (vr, var_vr);
741 else
742 set_value_range (vr, VR_RANGE, var, var, NULL);
744 add_equivalence (&vr->equiv, var);
747 /* Extract range information from a binary expression OP0 CODE OP1 based on
748 the ranges of each of its operands with resulting type EXPR_TYPE.
749 The resulting range is stored in *VR. */
751 void
752 vr_values::extract_range_from_binary_expr (value_range *vr,
753 enum tree_code code,
754 tree expr_type, tree op0, tree op1)
756 value_range vr0 = VR_INITIALIZER;
757 value_range vr1 = VR_INITIALIZER;
759 /* Get value ranges for each operand. For constant operands, create
760 a new value range with the operand to simplify processing. */
761 if (TREE_CODE (op0) == SSA_NAME)
762 vr0 = *(get_value_range (op0));
763 else if (is_gimple_min_invariant (op0))
764 set_value_range_to_value (&vr0, op0, NULL);
765 else
766 set_value_range_to_varying (&vr0);
768 if (TREE_CODE (op1) == SSA_NAME)
769 vr1 = *(get_value_range (op1));
770 else if (is_gimple_min_invariant (op1))
771 set_value_range_to_value (&vr1, op1, NULL);
772 else
773 set_value_range_to_varying (&vr1);
775 /* If one argument is varying, we can sometimes still deduce a
776 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
777 if (INTEGRAL_TYPE_P (TREE_TYPE (op0))
778 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
780 if (vr0.type == VR_VARYING && vr1.type != VR_VARYING)
782 vr0.type = VR_RANGE;
783 vr0.min = vrp_val_min (expr_type);
784 vr0.max = vrp_val_max (expr_type);
786 else if (vr1.type == VR_VARYING && vr0.type != VR_VARYING)
788 vr1.type = VR_RANGE;
789 vr1.min = vrp_val_min (expr_type);
790 vr1.max = vrp_val_max (expr_type);
794 extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
796 /* Set value_range for n in following sequence:
797 def = __builtin_memchr (arg, 0, sz)
798 n = def - arg
799 Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
801 if (vr->type == VR_VARYING
802 && code == POINTER_DIFF_EXPR
803 && TREE_CODE (op0) == SSA_NAME
804 && TREE_CODE (op1) == SSA_NAME)
806 tree op0_ptype = TREE_TYPE (TREE_TYPE (op0));
807 tree op1_ptype = TREE_TYPE (TREE_TYPE (op1));
808 gcall *call_stmt = NULL;
810 if (TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node)
811 && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node)
812 && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node)
813 && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node)
814 && (call_stmt = dyn_cast<gcall *>(SSA_NAME_DEF_STMT (op0)))
815 && gimple_call_builtin_p (call_stmt, BUILT_IN_MEMCHR)
816 && operand_equal_p (op0, gimple_call_lhs (call_stmt), 0)
817 && operand_equal_p (op1, gimple_call_arg (call_stmt, 0), 0)
818 && integer_zerop (gimple_call_arg (call_stmt, 1)))
820 tree max = vrp_val_max (ptrdiff_type_node);
821 wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
822 tree range_min = build_zero_cst (expr_type);
823 tree range_max = wide_int_to_tree (expr_type, wmax - 1);
824 set_value_range (vr, VR_RANGE, range_min, range_max, NULL);
825 return;
829 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
830 and based on the other operand, for example if it was deduced from a
831 symbolic comparison. When a bound of the range of the first operand
832 is invariant, we set the corresponding bound of the new range to INF
833 in order to avoid recursing on the range of the second operand. */
834 if (vr->type == VR_VARYING
835 && (code == PLUS_EXPR || code == MINUS_EXPR)
836 && TREE_CODE (op1) == SSA_NAME
837 && vr0.type == VR_RANGE
838 && symbolic_range_based_on_p (&vr0, op1))
840 const bool minus_p = (code == MINUS_EXPR);
841 value_range n_vr1 = VR_INITIALIZER;
843 /* Try with VR0 and [-INF, OP1]. */
844 if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min))
845 set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL);
847 /* Try with VR0 and [OP1, +INF]. */
848 else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max))
849 set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL);
851 /* Try with VR0 and [OP1, OP1]. */
852 else
853 set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL);
855 extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1);
858 if (vr->type == VR_VARYING
859 && (code == PLUS_EXPR || code == MINUS_EXPR)
860 && TREE_CODE (op0) == SSA_NAME
861 && vr1.type == VR_RANGE
862 && symbolic_range_based_on_p (&vr1, op0))
864 const bool minus_p = (code == MINUS_EXPR);
865 value_range n_vr0 = VR_INITIALIZER;
867 /* Try with [-INF, OP0] and VR1. */
868 if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min))
869 set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL);
871 /* Try with [OP0, +INF] and VR1. */
872 else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max))
873 set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL);
875 /* Try with [OP0, OP0] and VR1. */
876 else
877 set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL);
879 extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
882 /* If we didn't derive a range for MINUS_EXPR, and
883 op1's range is ~[op0,op0] or vice-versa, then we
884 can derive a non-null range. This happens often for
885 pointer subtraction. */
886 if (vr->type == VR_VARYING
887 && (code == MINUS_EXPR || code == POINTER_DIFF_EXPR)
888 && TREE_CODE (op0) == SSA_NAME
889 && ((vr0.type == VR_ANTI_RANGE
890 && vr0.min == op1
891 && vr0.min == vr0.max)
892 || (vr1.type == VR_ANTI_RANGE
893 && vr1.min == op0
894 && vr1.min == vr1.max)))
895 set_value_range_to_nonnull (vr, expr_type);
898 /* Extract range information from a unary expression CODE OP0 based on
899 the range of its operand with resulting type TYPE.
900 The resulting range is stored in *VR. */
902 void
903 vr_values::extract_range_from_unary_expr (value_range *vr, enum tree_code code,
904 tree type, tree op0)
906 value_range vr0 = VR_INITIALIZER;
908 /* Get value ranges for the operand. For constant operands, create
909 a new value range with the operand to simplify processing. */
910 if (TREE_CODE (op0) == SSA_NAME)
911 vr0 = *(get_value_range (op0));
912 else if (is_gimple_min_invariant (op0))
913 set_value_range_to_value (&vr0, op0, NULL);
914 else
915 set_value_range_to_varying (&vr0);
917 ::extract_range_from_unary_expr (vr, code, type, &vr0, TREE_TYPE (op0));
921 /* Extract range information from a conditional expression STMT based on
922 the ranges of each of its operands and the expression code. */
924 void
925 vr_values::extract_range_from_cond_expr (value_range *vr, gassign *stmt)
927 tree op0, op1;
928 value_range vr0 = VR_INITIALIZER;
929 value_range vr1 = VR_INITIALIZER;
931 /* Get value ranges for each operand. For constant operands, create
932 a new value range with the operand to simplify processing. */
933 op0 = gimple_assign_rhs2 (stmt);
934 if (TREE_CODE (op0) == SSA_NAME)
935 vr0 = *(get_value_range (op0));
936 else if (is_gimple_min_invariant (op0))
937 set_value_range_to_value (&vr0, op0, NULL);
938 else
939 set_value_range_to_varying (&vr0);
941 op1 = gimple_assign_rhs3 (stmt);
942 if (TREE_CODE (op1) == SSA_NAME)
943 vr1 = *(get_value_range (op1));
944 else if (is_gimple_min_invariant (op1))
945 set_value_range_to_value (&vr1, op1, NULL);
946 else
947 set_value_range_to_varying (&vr1);
949 /* The resulting value range is the union of the operand ranges */
950 copy_value_range (vr, &vr0);
951 vrp_meet (vr, &vr1);
955 /* Extract range information from a comparison expression EXPR based
956 on the range of its operand and the expression code. */
958 void
959 vr_values::extract_range_from_comparison (value_range *vr, enum tree_code code,
960 tree type, tree op0, tree op1)
962 bool sop;
963 tree val;
965 val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
966 NULL);
967 if (val)
969 /* Since this expression was found on the RHS of an assignment,
970 its type may be different from _Bool. Convert VAL to EXPR's
971 type. */
972 val = fold_convert (type, val);
973 if (is_gimple_min_invariant (val))
974 set_value_range_to_value (vr, val, vr->equiv);
975 else
976 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
978 else
979 /* The result of a comparison is always true or false. */
980 set_value_range_to_truthvalue (vr, type);
983 /* Helper function for simplify_internal_call_using_ranges and
984 extract_range_basic. Return true if OP0 SUBCODE OP1 for
985 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
986 always overflow. Set *OVF to true if it is known to always
987 overflow. */
989 bool
990 vr_values::check_for_binary_op_overflow (enum tree_code subcode, tree type,
991 tree op0, tree op1, bool *ovf)
993 value_range vr0 = VR_INITIALIZER;
994 value_range vr1 = VR_INITIALIZER;
995 if (TREE_CODE (op0) == SSA_NAME)
996 vr0 = *get_value_range (op0);
997 else if (TREE_CODE (op0) == INTEGER_CST)
998 set_value_range_to_value (&vr0, op0, NULL);
999 else
1000 set_value_range_to_varying (&vr0);
1002 if (TREE_CODE (op1) == SSA_NAME)
1003 vr1 = *get_value_range (op1);
1004 else if (TREE_CODE (op1) == INTEGER_CST)
1005 set_value_range_to_value (&vr1, op1, NULL);
1006 else
1007 set_value_range_to_varying (&vr1);
1009 if (!range_int_cst_p (&vr0)
1010 || TREE_OVERFLOW (vr0.min)
1011 || TREE_OVERFLOW (vr0.max))
1013 vr0.min = vrp_val_min (TREE_TYPE (op0));
1014 vr0.max = vrp_val_max (TREE_TYPE (op0));
1016 if (!range_int_cst_p (&vr1)
1017 || TREE_OVERFLOW (vr1.min)
1018 || TREE_OVERFLOW (vr1.max))
1020 vr1.min = vrp_val_min (TREE_TYPE (op1));
1021 vr1.max = vrp_val_max (TREE_TYPE (op1));
1023 *ovf = arith_overflowed_p (subcode, type, vr0.min,
1024 subcode == MINUS_EXPR ? vr1.max : vr1.min);
1025 if (arith_overflowed_p (subcode, type, vr0.max,
1026 subcode == MINUS_EXPR ? vr1.min : vr1.max) != *ovf)
1027 return false;
1028 if (subcode == MULT_EXPR)
1030 if (arith_overflowed_p (subcode, type, vr0.min, vr1.max) != *ovf
1031 || arith_overflowed_p (subcode, type, vr0.max, vr1.min) != *ovf)
1032 return false;
1034 if (*ovf)
1036 /* So far we found that there is an overflow on the boundaries.
1037 That doesn't prove that there is an overflow even for all values
1038 in between the boundaries. For that compute widest_int range
1039 of the result and see if it doesn't overlap the range of
1040 type. */
1041 widest_int wmin, wmax;
1042 widest_int w[4];
1043 int i;
1044 w[0] = wi::to_widest (vr0.min);
1045 w[1] = wi::to_widest (vr0.max);
1046 w[2] = wi::to_widest (vr1.min);
1047 w[3] = wi::to_widest (vr1.max);
1048 for (i = 0; i < 4; i++)
1050 widest_int wt;
1051 switch (subcode)
1053 case PLUS_EXPR:
1054 wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]);
1055 break;
1056 case MINUS_EXPR:
1057 wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]);
1058 break;
1059 case MULT_EXPR:
1060 wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]);
1061 break;
1062 default:
1063 gcc_unreachable ();
1065 if (i == 0)
1067 wmin = wt;
1068 wmax = wt;
1070 else
1072 wmin = wi::smin (wmin, wt);
1073 wmax = wi::smax (wmax, wt);
1076 /* The result of op0 CODE op1 is known to be in range
1077 [wmin, wmax]. */
1078 widest_int wtmin = wi::to_widest (vrp_val_min (type));
1079 widest_int wtmax = wi::to_widest (vrp_val_max (type));
1080 /* If all values in [wmin, wmax] are smaller than
1081 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1082 the arithmetic operation will always overflow. */
1083 if (wmax < wtmin || wmin > wtmax)
1084 return true;
1085 return false;
1087 return true;
1090 /* Try to derive a nonnegative or nonzero range out of STMT relying
1091 primarily on generic routines in fold in conjunction with range data.
1092 Store the result in *VR */
1094 void
1095 vr_values::extract_range_basic (value_range *vr, gimple *stmt)
1097 bool sop;
1098 tree type = gimple_expr_type (stmt);
1100 if (is_gimple_call (stmt))
1102 tree arg;
1103 int mini, maxi, zerov = 0, prec;
1104 enum tree_code subcode = ERROR_MARK;
1105 combined_fn cfn = gimple_call_combined_fn (stmt);
1106 scalar_int_mode mode;
1108 switch (cfn)
1110 case CFN_BUILT_IN_CONSTANT_P:
1111 /* If the call is __builtin_constant_p and the argument is a
1112 function parameter resolve it to false. This avoids bogus
1113 array bound warnings.
1114 ??? We could do this as early as inlining is finished. */
1115 arg = gimple_call_arg (stmt, 0);
1116 if (TREE_CODE (arg) == SSA_NAME
1117 && SSA_NAME_IS_DEFAULT_DEF (arg)
1118 && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL
1119 && cfun->after_inlining)
1121 set_value_range_to_null (vr, type);
1122 return;
1124 break;
1125 /* Both __builtin_ffs* and __builtin_popcount return
1126 [0, prec]. */
1127 CASE_CFN_FFS:
1128 CASE_CFN_POPCOUNT:
1129 arg = gimple_call_arg (stmt, 0);
1130 prec = TYPE_PRECISION (TREE_TYPE (arg));
1131 mini = 0;
1132 maxi = prec;
1133 if (TREE_CODE (arg) == SSA_NAME)
1135 value_range *vr0 = get_value_range (arg);
1136 /* If arg is non-zero, then ffs or popcount
1137 are non-zero. */
1138 if ((vr0->type == VR_RANGE
1139 && range_includes_zero_p (vr0->min, vr0->max) == 0)
1140 || (vr0->type == VR_ANTI_RANGE
1141 && range_includes_zero_p (vr0->min, vr0->max) == 1))
1142 mini = 1;
1143 /* If some high bits are known to be zero,
1144 we can decrease the maximum. */
1145 if (vr0->type == VR_RANGE
1146 && TREE_CODE (vr0->max) == INTEGER_CST
1147 && !operand_less_p (vr0->min,
1148 build_zero_cst (TREE_TYPE (vr0->min))))
1149 maxi = tree_floor_log2 (vr0->max) + 1;
1151 goto bitop_builtin;
1152 /* __builtin_parity* returns [0, 1]. */
1153 CASE_CFN_PARITY:
1154 mini = 0;
1155 maxi = 1;
1156 goto bitop_builtin;
1157 /* __builtin_c[lt]z* return [0, prec-1], except for
1158 when the argument is 0, but that is undefined behavior.
1159 On many targets where the CLZ RTL or optab value is defined
1160 for 0 the value is prec, so include that in the range
1161 by default. */
1162 CASE_CFN_CLZ:
1163 arg = gimple_call_arg (stmt, 0);
1164 prec = TYPE_PRECISION (TREE_TYPE (arg));
1165 mini = 0;
1166 maxi = prec;
1167 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
1168 if (optab_handler (clz_optab, mode) != CODE_FOR_nothing
1169 && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov)
1170 /* Handle only the single common value. */
1171 && zerov != prec)
1172 /* Magic value to give up, unless vr0 proves
1173 arg is non-zero. */
1174 mini = -2;
1175 if (TREE_CODE (arg) == SSA_NAME)
1177 value_range *vr0 = get_value_range (arg);
1178 /* From clz of VR_RANGE minimum we can compute
1179 result maximum. */
1180 if (vr0->type == VR_RANGE
1181 && TREE_CODE (vr0->min) == INTEGER_CST)
1183 maxi = prec - 1 - tree_floor_log2 (vr0->min);
1184 if (maxi != prec)
1185 mini = 0;
1187 else if (vr0->type == VR_ANTI_RANGE
1188 && integer_zerop (vr0->min))
1190 maxi = prec - 1;
1191 mini = 0;
1193 if (mini == -2)
1194 break;
1195 /* From clz of VR_RANGE maximum we can compute
1196 result minimum. */
1197 if (vr0->type == VR_RANGE
1198 && TREE_CODE (vr0->max) == INTEGER_CST)
1200 mini = prec - 1 - tree_floor_log2 (vr0->max);
1201 if (mini == prec)
1202 break;
1205 if (mini == -2)
1206 break;
1207 goto bitop_builtin;
1208 /* __builtin_ctz* return [0, prec-1], except for
1209 when the argument is 0, but that is undefined behavior.
1210 If there is a ctz optab for this mode and
1211 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1212 otherwise just assume 0 won't be seen. */
1213 CASE_CFN_CTZ:
1214 arg = gimple_call_arg (stmt, 0);
1215 prec = TYPE_PRECISION (TREE_TYPE (arg));
1216 mini = 0;
1217 maxi = prec - 1;
1218 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
1219 if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing
1220 && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov))
1222 /* Handle only the two common values. */
1223 if (zerov == -1)
1224 mini = -1;
1225 else if (zerov == prec)
1226 maxi = prec;
1227 else
1228 /* Magic value to give up, unless vr0 proves
1229 arg is non-zero. */
1230 mini = -2;
1232 if (TREE_CODE (arg) == SSA_NAME)
1234 value_range *vr0 = get_value_range (arg);
1235 /* If arg is non-zero, then use [0, prec - 1]. */
1236 if ((vr0->type == VR_RANGE
1237 && integer_nonzerop (vr0->min))
1238 || (vr0->type == VR_ANTI_RANGE
1239 && integer_zerop (vr0->min)))
1241 mini = 0;
1242 maxi = prec - 1;
1244 /* If some high bits are known to be zero,
1245 we can decrease the result maximum. */
1246 if (vr0->type == VR_RANGE
1247 && TREE_CODE (vr0->max) == INTEGER_CST)
1249 maxi = tree_floor_log2 (vr0->max);
1250 /* For vr0 [0, 0] give up. */
1251 if (maxi == -1)
1252 break;
1255 if (mini == -2)
1256 break;
1257 goto bitop_builtin;
1258 /* __builtin_clrsb* returns [0, prec-1]. */
1259 CASE_CFN_CLRSB:
1260 arg = gimple_call_arg (stmt, 0);
1261 prec = TYPE_PRECISION (TREE_TYPE (arg));
1262 mini = 0;
1263 maxi = prec - 1;
1264 goto bitop_builtin;
1265 bitop_builtin:
1266 set_value_range (vr, VR_RANGE, build_int_cst (type, mini),
1267 build_int_cst (type, maxi), NULL);
1268 return;
1269 case CFN_UBSAN_CHECK_ADD:
1270 subcode = PLUS_EXPR;
1271 break;
1272 case CFN_UBSAN_CHECK_SUB:
1273 subcode = MINUS_EXPR;
1274 break;
1275 case CFN_UBSAN_CHECK_MUL:
1276 subcode = MULT_EXPR;
1277 break;
1278 case CFN_GOACC_DIM_SIZE:
1279 case CFN_GOACC_DIM_POS:
1280 /* Optimizing these two internal functions helps the loop
1281 optimizer eliminate outer comparisons. Size is [1,N]
1282 and pos is [0,N-1]. */
1284 bool is_pos = cfn == CFN_GOACC_DIM_POS;
1285 int axis = oacc_get_ifn_dim_arg (stmt);
1286 int size = oacc_get_fn_dim_size (current_function_decl, axis);
1288 if (!size)
1289 /* If it's dynamic, the backend might know a hardware
1290 limitation. */
1291 size = targetm.goacc.dim_limit (axis);
1293 tree type = TREE_TYPE (gimple_call_lhs (stmt));
1294 set_value_range (vr, VR_RANGE,
1295 build_int_cst (type, is_pos ? 0 : 1),
1296 size ? build_int_cst (type, size - is_pos)
1297 : vrp_val_max (type), NULL);
1299 return;
1300 case CFN_BUILT_IN_STRLEN:
1301 if (tree lhs = gimple_call_lhs (stmt))
1302 if (ptrdiff_type_node
1303 && (TYPE_PRECISION (ptrdiff_type_node)
1304 == TYPE_PRECISION (TREE_TYPE (lhs))))
1306 tree type = TREE_TYPE (lhs);
1307 tree max = vrp_val_max (ptrdiff_type_node);
1308 wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
1309 tree range_min = build_zero_cst (type);
1310 tree range_max = wide_int_to_tree (type, wmax - 1);
1311 set_value_range (vr, VR_RANGE, range_min, range_max, NULL);
1312 return;
1314 break;
1315 default:
1316 break;
1318 if (subcode != ERROR_MARK)
1320 bool saved_flag_wrapv = flag_wrapv;
1321 /* Pretend the arithmetics is wrapping. If there is
1322 any overflow, we'll complain, but will actually do
1323 wrapping operation. */
1324 flag_wrapv = 1;
1325 extract_range_from_binary_expr (vr, subcode, type,
1326 gimple_call_arg (stmt, 0),
1327 gimple_call_arg (stmt, 1));
1328 flag_wrapv = saved_flag_wrapv;
1330 /* If for both arguments vrp_valueize returned non-NULL,
1331 this should have been already folded and if not, it
1332 wasn't folded because of overflow. Avoid removing the
1333 UBSAN_CHECK_* calls in that case. */
1334 if (vr->type == VR_RANGE
1335 && (vr->min == vr->max
1336 || operand_equal_p (vr->min, vr->max, 0)))
1337 set_value_range_to_varying (vr);
1338 return;
1341 /* Handle extraction of the two results (result of arithmetics and
1342 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1343 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1344 else if (is_gimple_assign (stmt)
1345 && (gimple_assign_rhs_code (stmt) == REALPART_EXPR
1346 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR)
1347 && INTEGRAL_TYPE_P (type))
1349 enum tree_code code = gimple_assign_rhs_code (stmt);
1350 tree op = gimple_assign_rhs1 (stmt);
1351 if (TREE_CODE (op) == code && TREE_CODE (TREE_OPERAND (op, 0)) == SSA_NAME)
1353 gimple *g = SSA_NAME_DEF_STMT (TREE_OPERAND (op, 0));
1354 if (is_gimple_call (g) && gimple_call_internal_p (g))
1356 enum tree_code subcode = ERROR_MARK;
1357 switch (gimple_call_internal_fn (g))
1359 case IFN_ADD_OVERFLOW:
1360 subcode = PLUS_EXPR;
1361 break;
1362 case IFN_SUB_OVERFLOW:
1363 subcode = MINUS_EXPR;
1364 break;
1365 case IFN_MUL_OVERFLOW:
1366 subcode = MULT_EXPR;
1367 break;
1368 case IFN_ATOMIC_COMPARE_EXCHANGE:
1369 if (code == IMAGPART_EXPR)
1371 /* This is the boolean return value whether compare and
1372 exchange changed anything or not. */
1373 set_value_range (vr, VR_RANGE, build_int_cst (type, 0),
1374 build_int_cst (type, 1), NULL);
1375 return;
1377 break;
1378 default:
1379 break;
1381 if (subcode != ERROR_MARK)
1383 tree op0 = gimple_call_arg (g, 0);
1384 tree op1 = gimple_call_arg (g, 1);
1385 if (code == IMAGPART_EXPR)
1387 bool ovf = false;
1388 if (check_for_binary_op_overflow (subcode, type,
1389 op0, op1, &ovf))
1390 set_value_range_to_value (vr,
1391 build_int_cst (type, ovf),
1392 NULL);
1393 else if (TYPE_PRECISION (type) == 1
1394 && !TYPE_UNSIGNED (type))
1395 set_value_range_to_varying (vr);
1396 else
1397 set_value_range (vr, VR_RANGE, build_int_cst (type, 0),
1398 build_int_cst (type, 1), NULL);
1400 else if (types_compatible_p (type, TREE_TYPE (op0))
1401 && types_compatible_p (type, TREE_TYPE (op1)))
1403 bool saved_flag_wrapv = flag_wrapv;
1404 /* Pretend the arithmetics is wrapping. If there is
1405 any overflow, IMAGPART_EXPR will be set. */
1406 flag_wrapv = 1;
1407 extract_range_from_binary_expr (vr, subcode, type,
1408 op0, op1);
1409 flag_wrapv = saved_flag_wrapv;
1411 else
1413 value_range vr0 = VR_INITIALIZER;
1414 value_range vr1 = VR_INITIALIZER;
1415 bool saved_flag_wrapv = flag_wrapv;
1416 /* Pretend the arithmetics is wrapping. If there is
1417 any overflow, IMAGPART_EXPR will be set. */
1418 flag_wrapv = 1;
1419 extract_range_from_unary_expr (&vr0, NOP_EXPR,
1420 type, op0);
1421 extract_range_from_unary_expr (&vr1, NOP_EXPR,
1422 type, op1);
1423 extract_range_from_binary_expr_1 (vr, subcode, type,
1424 &vr0, &vr1);
1425 flag_wrapv = saved_flag_wrapv;
1427 return;
1432 if (INTEGRAL_TYPE_P (type)
1433 && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
1434 set_value_range_to_nonnegative (vr, type);
1435 else if (vrp_stmt_computes_nonzero (stmt))
1436 set_value_range_to_nonnull (vr, type);
1437 else
1438 set_value_range_to_varying (vr);
1442 /* Try to compute a useful range out of assignment STMT and store it
1443 in *VR. */
1445 void
1446 vr_values::extract_range_from_assignment (value_range *vr, gassign *stmt)
1448 enum tree_code code = gimple_assign_rhs_code (stmt);
1450 if (code == ASSERT_EXPR)
1451 extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
1452 else if (code == SSA_NAME)
1453 extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
1454 else if (TREE_CODE_CLASS (code) == tcc_binary)
1455 extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
1456 gimple_expr_type (stmt),
1457 gimple_assign_rhs1 (stmt),
1458 gimple_assign_rhs2 (stmt));
1459 else if (TREE_CODE_CLASS (code) == tcc_unary)
1460 extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
1461 gimple_expr_type (stmt),
1462 gimple_assign_rhs1 (stmt));
1463 else if (code == COND_EXPR)
1464 extract_range_from_cond_expr (vr, stmt);
1465 else if (TREE_CODE_CLASS (code) == tcc_comparison)
1466 extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
1467 gimple_expr_type (stmt),
1468 gimple_assign_rhs1 (stmt),
1469 gimple_assign_rhs2 (stmt));
1470 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
1471 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1472 set_value_range_to_value (vr, gimple_assign_rhs1 (stmt), NULL);
1473 else
1474 set_value_range_to_varying (vr);
1476 if (vr->type == VR_VARYING)
1477 extract_range_basic (vr, stmt);
1480 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1482 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1483 all the values in the ranges.
1485 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1487 - Return NULL_TREE if it is not always possible to determine the
1488 value of the comparison.
1490 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1491 assumed signed overflow is undefined. */
1494 static tree
1495 compare_ranges (enum tree_code comp, value_range *vr0, value_range *vr1,
1496 bool *strict_overflow_p)
1498 /* VARYING or UNDEFINED ranges cannot be compared. */
1499 if (vr0->type == VR_VARYING
1500 || vr0->type == VR_UNDEFINED
1501 || vr1->type == VR_VARYING
1502 || vr1->type == VR_UNDEFINED)
1503 return NULL_TREE;
1505 /* Anti-ranges need to be handled separately. */
1506 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
1508 /* If both are anti-ranges, then we cannot compute any
1509 comparison. */
1510 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
1511 return NULL_TREE;
1513 /* These comparisons are never statically computable. */
1514 if (comp == GT_EXPR
1515 || comp == GE_EXPR
1516 || comp == LT_EXPR
1517 || comp == LE_EXPR)
1518 return NULL_TREE;
1520 /* Equality can be computed only between a range and an
1521 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1522 if (vr0->type == VR_RANGE)
1524 /* To simplify processing, make VR0 the anti-range. */
1525 value_range *tmp = vr0;
1526 vr0 = vr1;
1527 vr1 = tmp;
1530 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
1532 if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
1533 && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
1534 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1536 return NULL_TREE;
1539 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1540 operands around and change the comparison code. */
1541 if (comp == GT_EXPR || comp == GE_EXPR)
1543 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
1544 std::swap (vr0, vr1);
1547 if (comp == EQ_EXPR)
1549 /* Equality may only be computed if both ranges represent
1550 exactly one value. */
1551 if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
1552 && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
1554 int cmp_min = compare_values_warnv (vr0->min, vr1->min,
1555 strict_overflow_p);
1556 int cmp_max = compare_values_warnv (vr0->max, vr1->max,
1557 strict_overflow_p);
1558 if (cmp_min == 0 && cmp_max == 0)
1559 return boolean_true_node;
1560 else if (cmp_min != -2 && cmp_max != -2)
1561 return boolean_false_node;
1563 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1564 else if (compare_values_warnv (vr0->min, vr1->max,
1565 strict_overflow_p) == 1
1566 || compare_values_warnv (vr1->min, vr0->max,
1567 strict_overflow_p) == 1)
1568 return boolean_false_node;
1570 return NULL_TREE;
1572 else if (comp == NE_EXPR)
1574 int cmp1, cmp2;
1576 /* If VR0 is completely to the left or completely to the right
1577 of VR1, they are always different. Notice that we need to
1578 make sure that both comparisons yield similar results to
1579 avoid comparing values that cannot be compared at
1580 compile-time. */
1581 cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
1582 cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
1583 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1584 return boolean_true_node;
1586 /* If VR0 and VR1 represent a single value and are identical,
1587 return false. */
1588 else if (compare_values_warnv (vr0->min, vr0->max,
1589 strict_overflow_p) == 0
1590 && compare_values_warnv (vr1->min, vr1->max,
1591 strict_overflow_p) == 0
1592 && compare_values_warnv (vr0->min, vr1->min,
1593 strict_overflow_p) == 0
1594 && compare_values_warnv (vr0->max, vr1->max,
1595 strict_overflow_p) == 0)
1596 return boolean_false_node;
1598 /* Otherwise, they may or may not be different. */
1599 else
1600 return NULL_TREE;
1602 else if (comp == LT_EXPR || comp == LE_EXPR)
1604 int tst;
1606 /* If VR0 is to the left of VR1, return true. */
1607 tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
1608 if ((comp == LT_EXPR && tst == -1)
1609 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1610 return boolean_true_node;
1612 /* If VR0 is to the right of VR1, return false. */
1613 tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
1614 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1615 || (comp == LE_EXPR && tst == 1))
1616 return boolean_false_node;
1618 /* Otherwise, we don't know. */
1619 return NULL_TREE;
1622 gcc_unreachable ();
1625 /* Given a value range VR, a value VAL and a comparison code COMP, return
1626 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1627 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1628 always returns false. Return NULL_TREE if it is not always
1629 possible to determine the value of the comparison. Also set
1630 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1631 assumed signed overflow is undefined. */
1633 static tree
1634 compare_range_with_value (enum tree_code comp, value_range *vr, tree val,
1635 bool *strict_overflow_p)
1637 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1638 return NULL_TREE;
1640 /* Anti-ranges need to be handled separately. */
1641 if (vr->type == VR_ANTI_RANGE)
1643 /* For anti-ranges, the only predicates that we can compute at
1644 compile time are equality and inequality. */
1645 if (comp == GT_EXPR
1646 || comp == GE_EXPR
1647 || comp == LT_EXPR
1648 || comp == LE_EXPR)
1649 return NULL_TREE;
1651 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1652 if (value_inside_range (val, vr->min, vr->max) == 1)
1653 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1655 return NULL_TREE;
1658 if (comp == EQ_EXPR)
1660 /* EQ_EXPR may only be computed if VR represents exactly
1661 one value. */
1662 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0)
1664 int cmp = compare_values_warnv (vr->min, val, strict_overflow_p);
1665 if (cmp == 0)
1666 return boolean_true_node;
1667 else if (cmp == -1 || cmp == 1 || cmp == 2)
1668 return boolean_false_node;
1670 else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1
1671 || compare_values_warnv (vr->max, val, strict_overflow_p) == -1)
1672 return boolean_false_node;
1674 return NULL_TREE;
1676 else if (comp == NE_EXPR)
1678 /* If VAL is not inside VR, then they are always different. */
1679 if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1
1680 || compare_values_warnv (vr->min, val, strict_overflow_p) == 1)
1681 return boolean_true_node;
1683 /* If VR represents exactly one value equal to VAL, then return
1684 false. */
1685 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0
1686 && compare_values_warnv (vr->min, val, strict_overflow_p) == 0)
1687 return boolean_false_node;
1689 /* Otherwise, they may or may not be different. */
1690 return NULL_TREE;
1692 else if (comp == LT_EXPR || comp == LE_EXPR)
1694 int tst;
1696 /* If VR is to the left of VAL, return true. */
1697 tst = compare_values_warnv (vr->max, val, strict_overflow_p);
1698 if ((comp == LT_EXPR && tst == -1)
1699 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1700 return boolean_true_node;
1702 /* If VR is to the right of VAL, return false. */
1703 tst = compare_values_warnv (vr->min, val, strict_overflow_p);
1704 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1705 || (comp == LE_EXPR && tst == 1))
1706 return boolean_false_node;
1708 /* Otherwise, we don't know. */
1709 return NULL_TREE;
1711 else if (comp == GT_EXPR || comp == GE_EXPR)
1713 int tst;
1715 /* If VR is to the right of VAL, return true. */
1716 tst = compare_values_warnv (vr->min, val, strict_overflow_p);
1717 if ((comp == GT_EXPR && tst == 1)
1718 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1719 return boolean_true_node;
1721 /* If VR is to the left of VAL, return false. */
1722 tst = compare_values_warnv (vr->max, val, strict_overflow_p);
1723 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1724 || (comp == GE_EXPR && tst == -1))
1725 return boolean_false_node;
1727 /* Otherwise, we don't know. */
1728 return NULL_TREE;
1731 gcc_unreachable ();
1733 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1734 would be profitable to adjust VR using scalar evolution information
1735 for VAR. If so, update VR with the new limits. */
1737 void
1738 vr_values::adjust_range_with_scev (value_range *vr, struct loop *loop,
1739 gimple *stmt, tree var)
1741 tree init, step, chrec, tmin, tmax, min, max, type, tem;
1742 enum ev_direction dir;
1744 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1745 better opportunities than a regular range, but I'm not sure. */
1746 if (vr->type == VR_ANTI_RANGE)
1747 return;
1749 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
1751 /* Like in PR19590, scev can return a constant function. */
1752 if (is_gimple_min_invariant (chrec))
1754 set_value_range_to_value (vr, chrec, vr->equiv);
1755 return;
1758 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1759 return;
1761 init = initial_condition_in_loop_num (chrec, loop->num);
1762 tem = op_with_constant_singleton_value_range (init);
1763 if (tem)
1764 init = tem;
1765 step = evolution_part_in_loop_num (chrec, loop->num);
1766 tem = op_with_constant_singleton_value_range (step);
1767 if (tem)
1768 step = tem;
1770 /* If STEP is symbolic, we can't know whether INIT will be the
1771 minimum or maximum value in the range. Also, unless INIT is
1772 a simple expression, compare_values and possibly other functions
1773 in tree-vrp won't be able to handle it. */
1774 if (step == NULL_TREE
1775 || !is_gimple_min_invariant (step)
1776 || !valid_value_p (init))
1777 return;
1779 dir = scev_direction (chrec);
1780 if (/* Do not adjust ranges if we do not know whether the iv increases
1781 or decreases, ... */
1782 dir == EV_DIR_UNKNOWN
1783 /* ... or if it may wrap. */
1784 || scev_probably_wraps_p (NULL_TREE, init, step, stmt,
1785 get_chrec_loop (chrec), true))
1786 return;
1788 type = TREE_TYPE (var);
1789 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1790 tmin = lower_bound_in_type (type, type);
1791 else
1792 tmin = TYPE_MIN_VALUE (type);
1793 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1794 tmax = upper_bound_in_type (type, type);
1795 else
1796 tmax = TYPE_MAX_VALUE (type);
1798 /* Try to use estimated number of iterations for the loop to constrain the
1799 final value in the evolution. */
1800 if (TREE_CODE (step) == INTEGER_CST
1801 && is_gimple_val (init)
1802 && (TREE_CODE (init) != SSA_NAME
1803 || get_value_range (init)->type == VR_RANGE))
1805 widest_int nit;
1807 /* We are only entering here for loop header PHI nodes, so using
1808 the number of latch executions is the correct thing to use. */
1809 if (max_loop_iterations (loop, &nit))
1811 value_range maxvr = VR_INITIALIZER;
1812 signop sgn = TYPE_SIGN (TREE_TYPE (step));
1813 bool overflow;
1815 widest_int wtmp = wi::mul (wi::to_widest (step), nit, sgn,
1816 &overflow);
1817 /* If the multiplication overflowed we can't do a meaningful
1818 adjustment. Likewise if the result doesn't fit in the type
1819 of the induction variable. For a signed type we have to
1820 check whether the result has the expected signedness which
1821 is that of the step as number of iterations is unsigned. */
1822 if (!overflow
1823 && wi::fits_to_tree_p (wtmp, TREE_TYPE (init))
1824 && (sgn == UNSIGNED
1825 || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0)))
1827 tem = wide_int_to_tree (TREE_TYPE (init), wtmp);
1828 extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
1829 TREE_TYPE (init), init, tem);
1830 /* Likewise if the addition did. */
1831 if (maxvr.type == VR_RANGE)
1833 value_range initvr = VR_INITIALIZER;
1835 if (TREE_CODE (init) == SSA_NAME)
1836 initvr = *(get_value_range (init));
1837 else if (is_gimple_min_invariant (init))
1838 set_value_range_to_value (&initvr, init, NULL);
1839 else
1840 return;
1842 /* Check if init + nit * step overflows. Though we checked
1843 scev {init, step}_loop doesn't wrap, it is not enough
1844 because the loop may exit immediately. Overflow could
1845 happen in the plus expression in this case. */
1846 if ((dir == EV_DIR_DECREASES
1847 && compare_values (maxvr.min, initvr.min) != -1)
1848 || (dir == EV_DIR_GROWS
1849 && compare_values (maxvr.max, initvr.max) != 1))
1850 return;
1852 tmin = maxvr.min;
1853 tmax = maxvr.max;
1859 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1861 min = tmin;
1862 max = tmax;
1864 /* For VARYING or UNDEFINED ranges, just about anything we get
1865 from scalar evolutions should be better. */
1867 if (dir == EV_DIR_DECREASES)
1868 max = init;
1869 else
1870 min = init;
1872 else if (vr->type == VR_RANGE)
1874 min = vr->min;
1875 max = vr->max;
1877 if (dir == EV_DIR_DECREASES)
1879 /* INIT is the maximum value. If INIT is lower than VR->MAX
1880 but no smaller than VR->MIN, set VR->MAX to INIT. */
1881 if (compare_values (init, max) == -1)
1882 max = init;
1884 /* According to the loop information, the variable does not
1885 overflow. */
1886 if (compare_values (min, tmin) == -1)
1887 min = tmin;
1890 else
1892 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1893 if (compare_values (init, min) == 1)
1894 min = init;
1896 if (compare_values (tmax, max) == -1)
1897 max = tmax;
1900 else
1901 return;
1903 /* If we just created an invalid range with the minimum
1904 greater than the maximum, we fail conservatively.
1905 This should happen only in unreachable
1906 parts of code, or for invalid programs. */
1907 if (compare_values (min, max) == 1)
1908 return;
1910 /* Even for valid range info, sometimes overflow flag will leak in.
1911 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1912 drop them. */
1913 if (TREE_OVERFLOW_P (min))
1914 min = drop_tree_overflow (min);
1915 if (TREE_OVERFLOW_P (max))
1916 max = drop_tree_overflow (max);
1918 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1921 /* Dump value ranges of all SSA_NAMEs to FILE. */
1923 void
1924 vr_values::dump_all_value_ranges (FILE *file)
1926 size_t i;
1928 for (i = 0; i < num_vr_values; i++)
1930 if (vr_value[i])
1932 print_generic_expr (file, ssa_name (i));
1933 fprintf (file, ": ");
1934 dump_value_range (file, vr_value[i]);
1935 fprintf (file, "\n");
1939 fprintf (file, "\n");
1942 /* Initialize VRP lattice. */
1944 vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
1946 values_propagated = false;
1947 num_vr_values = num_ssa_names;
1948 vr_value = XCNEWVEC (value_range *, num_vr_values);
1949 vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
1950 bitmap_obstack_initialize (&vrp_equiv_obstack);
1953 /* Free VRP lattice. */
1955 vr_values::~vr_values ()
1957 /* Free allocated memory. */
1958 free (vr_value);
1959 free (vr_phi_edge_counts);
1960 bitmap_obstack_release (&vrp_equiv_obstack);
1961 vrp_value_range_pool.release ();
1963 /* So that we can distinguish between VRP data being available
1964 and not available. */
1965 vr_value = NULL;
1966 vr_phi_edge_counts = NULL;
1970 /* A hack. */
1971 static class vr_values *x_vr_values;
1973 /* Return the singleton value-range for NAME or NAME. */
1975 static inline tree
1976 vrp_valueize (tree name)
1978 if (TREE_CODE (name) == SSA_NAME)
1980 value_range *vr = x_vr_values->get_value_range (name);
1981 if (vr->type == VR_RANGE
1982 && (TREE_CODE (vr->min) == SSA_NAME
1983 || is_gimple_min_invariant (vr->min))
1984 && vrp_operand_equal_p (vr->min, vr->max))
1985 return vr->min;
1987 return name;
1990 /* Return the singleton value-range for NAME if that is a constant
1991 but signal to not follow SSA edges. */
1993 static inline tree
1994 vrp_valueize_1 (tree name)
1996 if (TREE_CODE (name) == SSA_NAME)
1998 /* If the definition may be simulated again we cannot follow
1999 this SSA edge as the SSA propagator does not necessarily
2000 re-visit the use. */
2001 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
2002 if (!gimple_nop_p (def_stmt)
2003 && prop_simulate_again_p (def_stmt))
2004 return NULL_TREE;
2005 value_range *vr = x_vr_values->get_value_range (name);
2006 if (range_int_cst_singleton_p (vr))
2007 return vr->min;
2009 return name;
2012 /* Given STMT, an assignment or call, return its LHS if the type
2013 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
2015 tree
2016 get_output_for_vrp (gimple *stmt)
2018 if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
2019 return NULL_TREE;
2021 /* We only keep track of ranges in integral and pointer types. */
2022 tree lhs = gimple_get_lhs (stmt);
2023 if (TREE_CODE (lhs) == SSA_NAME
2024 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2025 /* It is valid to have NULL MIN/MAX values on a type. See
2026 build_range_type. */
2027 && TYPE_MIN_VALUE (TREE_TYPE (lhs))
2028 && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
2029 || POINTER_TYPE_P (TREE_TYPE (lhs))))
2030 return lhs;
2032 return NULL_TREE;
2035 /* Visit assignment STMT. If it produces an interesting range, record
2036 the range in VR and set LHS to OUTPUT_P. */
2038 void
2039 vr_values::vrp_visit_assignment_or_call (gimple *stmt, tree *output_p,
2040 value_range *vr)
2042 tree lhs = get_output_for_vrp (stmt);
2043 *output_p = lhs;
2045 /* We only keep track of ranges in integral and pointer types. */
2046 if (lhs)
2048 enum gimple_code code = gimple_code (stmt);
2050 /* Try folding the statement to a constant first. */
2051 x_vr_values = this;
2052 tree tem = gimple_fold_stmt_to_constant_1 (stmt, vrp_valueize,
2053 vrp_valueize_1);
2054 x_vr_values = NULL;
2055 if (tem)
2057 if (TREE_CODE (tem) == SSA_NAME
2058 && (SSA_NAME_IS_DEFAULT_DEF (tem)
2059 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem))))
2061 extract_range_from_ssa_name (vr, tem);
2062 return;
2064 else if (is_gimple_min_invariant (tem))
2066 set_value_range_to_value (vr, tem, NULL);
2067 return;
2070 /* Then dispatch to value-range extracting functions. */
2071 if (code == GIMPLE_CALL)
2072 extract_range_basic (vr, stmt);
2073 else
2074 extract_range_from_assignment (vr, as_a <gassign *> (stmt));
2078 /* Helper that gets the value range of the SSA_NAME with version I
2079 or a symbolic range containing the SSA_NAME only if the value range
2080 is varying or undefined. */
2082 value_range
2083 vr_values::get_vr_for_comparison (int i)
2085 value_range vr = *get_value_range (ssa_name (i));
2087 /* If name N_i does not have a valid range, use N_i as its own
2088 range. This allows us to compare against names that may
2089 have N_i in their ranges. */
2090 if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
2092 vr.type = VR_RANGE;
2093 vr.min = ssa_name (i);
2094 vr.max = ssa_name (i);
2097 return vr;
2100 /* Compare all the value ranges for names equivalent to VAR with VAL
2101 using comparison code COMP. Return the same value returned by
2102 compare_range_with_value, including the setting of
2103 *STRICT_OVERFLOW_P. */
2105 tree
2106 vr_values::compare_name_with_value (enum tree_code comp, tree var, tree val,
2107 bool *strict_overflow_p, bool use_equiv_p)
2109 bitmap_iterator bi;
2110 unsigned i;
2111 bitmap e;
2112 tree retval, t;
2113 int used_strict_overflow;
2114 bool sop;
2115 value_range equiv_vr;
2117 /* Get the set of equivalences for VAR. */
2118 e = get_value_range (var)->equiv;
2120 /* Start at -1. Set it to 0 if we do a comparison without relying
2121 on overflow, or 1 if all comparisons rely on overflow. */
2122 used_strict_overflow = -1;
2124 /* Compare vars' value range with val. */
2125 equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
2126 sop = false;
2127 retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
2128 if (retval)
2129 used_strict_overflow = sop ? 1 : 0;
2131 /* If the equiv set is empty we have done all work we need to do. */
2132 if (e == NULL)
2134 if (retval
2135 && used_strict_overflow > 0)
2136 *strict_overflow_p = true;
2137 return retval;
2140 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
2142 tree name = ssa_name (i);
2143 if (! name)
2144 continue;
2146 if (! use_equiv_p
2147 && ! SSA_NAME_IS_DEFAULT_DEF (name)
2148 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name)))
2149 continue;
2151 equiv_vr = get_vr_for_comparison (i);
2152 sop = false;
2153 t = compare_range_with_value (comp, &equiv_vr, val, &sop);
2154 if (t)
2156 /* If we get different answers from different members
2157 of the equivalence set this check must be in a dead
2158 code region. Folding it to a trap representation
2159 would be correct here. For now just return don't-know. */
2160 if (retval != NULL
2161 && t != retval)
2163 retval = NULL_TREE;
2164 break;
2166 retval = t;
2168 if (!sop)
2169 used_strict_overflow = 0;
2170 else if (used_strict_overflow < 0)
2171 used_strict_overflow = 1;
2175 if (retval
2176 && used_strict_overflow > 0)
2177 *strict_overflow_p = true;
2179 return retval;
2183 /* Given a comparison code COMP and names N1 and N2, compare all the
2184 ranges equivalent to N1 against all the ranges equivalent to N2
2185 to determine the value of N1 COMP N2. Return the same value
2186 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2187 whether we relied on undefined signed overflow in the comparison. */
2190 tree
2191 vr_values::compare_names (enum tree_code comp, tree n1, tree n2,
2192 bool *strict_overflow_p)
2194 tree t, retval;
2195 bitmap e1, e2;
2196 bitmap_iterator bi1, bi2;
2197 unsigned i1, i2;
2198 int used_strict_overflow;
2199 static bitmap_obstack *s_obstack = NULL;
2200 static bitmap s_e1 = NULL, s_e2 = NULL;
2202 /* Compare the ranges of every name equivalent to N1 against the
2203 ranges of every name equivalent to N2. */
2204 e1 = get_value_range (n1)->equiv;
2205 e2 = get_value_range (n2)->equiv;
2207 /* Use the fake bitmaps if e1 or e2 are not available. */
2208 if (s_obstack == NULL)
2210 s_obstack = XNEW (bitmap_obstack);
2211 bitmap_obstack_initialize (s_obstack);
2212 s_e1 = BITMAP_ALLOC (s_obstack);
2213 s_e2 = BITMAP_ALLOC (s_obstack);
2215 if (e1 == NULL)
2216 e1 = s_e1;
2217 if (e2 == NULL)
2218 e2 = s_e2;
2220 /* Add N1 and N2 to their own set of equivalences to avoid
2221 duplicating the body of the loop just to check N1 and N2
2222 ranges. */
2223 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
2224 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
2226 /* If the equivalence sets have a common intersection, then the two
2227 names can be compared without checking their ranges. */
2228 if (bitmap_intersect_p (e1, e2))
2230 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2231 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2233 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
2234 ? boolean_true_node
2235 : boolean_false_node;
2238 /* Start at -1. Set it to 0 if we do a comparison without relying
2239 on overflow, or 1 if all comparisons rely on overflow. */
2240 used_strict_overflow = -1;
2242 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2243 N2 to their own set of equivalences to avoid duplicating the body
2244 of the loop just to check N1 and N2 ranges. */
2245 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
2247 if (! ssa_name (i1))
2248 continue;
2250 value_range vr1 = get_vr_for_comparison (i1);
2252 t = retval = NULL_TREE;
2253 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
2255 if (! ssa_name (i2))
2256 continue;
2258 bool sop = false;
2260 value_range vr2 = get_vr_for_comparison (i2);
2262 t = compare_ranges (comp, &vr1, &vr2, &sop);
2263 if (t)
2265 /* If we get different answers from different members
2266 of the equivalence set this check must be in a dead
2267 code region. Folding it to a trap representation
2268 would be correct here. For now just return don't-know. */
2269 if (retval != NULL
2270 && t != retval)
2272 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2273 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2274 return NULL_TREE;
2276 retval = t;
2278 if (!sop)
2279 used_strict_overflow = 0;
2280 else if (used_strict_overflow < 0)
2281 used_strict_overflow = 1;
2285 if (retval)
2287 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2288 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2289 if (used_strict_overflow > 0)
2290 *strict_overflow_p = true;
2291 return retval;
2295 /* None of the equivalent ranges are useful in computing this
2296 comparison. */
2297 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2298 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2299 return NULL_TREE;
2302 /* Helper function for vrp_evaluate_conditional_warnv & other
2303 optimizers. */
2305 tree
2306 vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2307 (enum tree_code code, tree op0, tree op1, bool * strict_overflow_p)
2309 value_range *vr0, *vr1;
2311 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
2312 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
2314 tree res = NULL_TREE;
2315 if (vr0 && vr1)
2316 res = compare_ranges (code, vr0, vr1, strict_overflow_p);
2317 if (!res && vr0)
2318 res = compare_range_with_value (code, vr0, op1, strict_overflow_p);
2319 if (!res && vr1)
2320 res = (compare_range_with_value
2321 (swap_tree_comparison (code), vr1, op0, strict_overflow_p));
2322 return res;
2325 /* Helper function for vrp_evaluate_conditional_warnv. */
2327 tree
2328 vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
2329 tree op0, tree op1,
2330 bool use_equiv_p,
2331 bool *strict_overflow_p,
2332 bool *only_ranges)
2334 tree ret;
2335 if (only_ranges)
2336 *only_ranges = true;
2338 /* We only deal with integral and pointer types. */
2339 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2340 && !POINTER_TYPE_P (TREE_TYPE (op0)))
2341 return NULL_TREE;
2343 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2344 as a simple equality test, then prefer that over its current form
2345 for evaluation.
2347 An overflow test which collapses to an equality test can always be
2348 expressed as a comparison of one argument against zero. Overflow
2349 occurs when the chosen argument is zero and does not occur if the
2350 chosen argument is not zero. */
2351 tree x;
2352 if (overflow_comparison_p (code, op0, op1, use_equiv_p, &x))
2354 wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
2355 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2356 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2357 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2358 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2359 if (integer_zerop (x))
2361 op1 = x;
2362 code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
2364 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2365 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2366 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2367 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2368 else if (wi::to_wide (x) == max - 1)
2370 op0 = op1;
2371 op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
2372 code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
2376 if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
2377 (code, op0, op1, strict_overflow_p)))
2378 return ret;
2379 if (only_ranges)
2380 *only_ranges = false;
2381 /* Do not use compare_names during propagation, it's quadratic. */
2382 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME
2383 && use_equiv_p)
2384 return compare_names (code, op0, op1, strict_overflow_p);
2385 else if (TREE_CODE (op0) == SSA_NAME)
2386 return compare_name_with_value (code, op0, op1,
2387 strict_overflow_p, use_equiv_p);
2388 else if (TREE_CODE (op1) == SSA_NAME)
2389 return compare_name_with_value (swap_tree_comparison (code), op1, op0,
2390 strict_overflow_p, use_equiv_p);
2391 return NULL_TREE;
2394 /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2395 information. Return NULL if the conditional can not be evaluated.
2396 The ranges of all the names equivalent with the operands in COND
2397 will be used when trying to compute the value. If the result is
2398 based on undefined signed overflow, issue a warning if
2399 appropriate. */
2401 tree
2402 vr_values::vrp_evaluate_conditional (tree_code code, tree op0,
2403 tree op1, gimple *stmt)
2405 bool sop;
2406 tree ret;
2407 bool only_ranges;
2409 /* Some passes and foldings leak constants with overflow flag set
2410 into the IL. Avoid doing wrong things with these and bail out. */
2411 if ((TREE_CODE (op0) == INTEGER_CST
2412 && TREE_OVERFLOW (op0))
2413 || (TREE_CODE (op1) == INTEGER_CST
2414 && TREE_OVERFLOW (op1)))
2415 return NULL_TREE;
2417 sop = false;
2418 ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop,
2419 &only_ranges);
2421 if (ret && sop)
2423 enum warn_strict_overflow_code wc;
2424 const char* warnmsg;
2426 if (is_gimple_min_invariant (ret))
2428 wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
2429 warnmsg = G_("assuming signed overflow does not occur when "
2430 "simplifying conditional to constant");
2432 else
2434 wc = WARN_STRICT_OVERFLOW_COMPARISON;
2435 warnmsg = G_("assuming signed overflow does not occur when "
2436 "simplifying conditional");
2439 if (issue_strict_overflow_warning (wc))
2441 location_t location;
2443 if (!gimple_has_location (stmt))
2444 location = input_location;
2445 else
2446 location = gimple_location (stmt);
2447 warning_at (location, OPT_Wstrict_overflow, "%s", warnmsg);
2451 if (warn_type_limits
2452 && ret && only_ranges
2453 && TREE_CODE_CLASS (code) == tcc_comparison
2454 && TREE_CODE (op0) == SSA_NAME)
2456 /* If the comparison is being folded and the operand on the LHS
2457 is being compared against a constant value that is outside of
2458 the natural range of OP0's type, then the predicate will
2459 always fold regardless of the value of OP0. If -Wtype-limits
2460 was specified, emit a warning. */
2461 tree type = TREE_TYPE (op0);
2462 value_range *vr0 = get_value_range (op0);
2464 if (vr0->type == VR_RANGE
2465 && INTEGRAL_TYPE_P (type)
2466 && vrp_val_is_min (vr0->min)
2467 && vrp_val_is_max (vr0->max)
2468 && is_gimple_min_invariant (op1))
2470 location_t location;
2472 if (!gimple_has_location (stmt))
2473 location = input_location;
2474 else
2475 location = gimple_location (stmt);
2477 warning_at (location, OPT_Wtype_limits,
2478 integer_zerop (ret)
2479 ? G_("comparison always false "
2480 "due to limited range of data type")
2481 : G_("comparison always true "
2482 "due to limited range of data type"));
2486 return ret;
2490 /* Visit conditional statement STMT. If we can determine which edge
2491 will be taken out of STMT's basic block, record it in
2492 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2494 void
2495 vr_values::vrp_visit_cond_stmt (gcond *stmt, edge *taken_edge_p)
2497 tree val;
2499 *taken_edge_p = NULL;
2501 if (dump_file && (dump_flags & TDF_DETAILS))
2503 tree use;
2504 ssa_op_iter i;
2506 fprintf (dump_file, "\nVisiting conditional with predicate: ");
2507 print_gimple_stmt (dump_file, stmt, 0);
2508 fprintf (dump_file, "\nWith known ranges\n");
2510 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
2512 fprintf (dump_file, "\t");
2513 print_generic_expr (dump_file, use);
2514 fprintf (dump_file, ": ");
2515 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
2518 fprintf (dump_file, "\n");
2521 /* Compute the value of the predicate COND by checking the known
2522 ranges of each of its operands.
2524 Note that we cannot evaluate all the equivalent ranges here
2525 because those ranges may not yet be final and with the current
2526 propagation strategy, we cannot determine when the value ranges
2527 of the names in the equivalence set have changed.
2529 For instance, given the following code fragment
2531 i_5 = PHI <8, i_13>
2533 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2534 if (i_14 == 1)
2537 Assume that on the first visit to i_14, i_5 has the temporary
2538 range [8, 8] because the second argument to the PHI function is
2539 not yet executable. We derive the range ~[0, 0] for i_14 and the
2540 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2541 the first time, since i_14 is equivalent to the range [8, 8], we
2542 determine that the predicate is always false.
2544 On the next round of propagation, i_13 is determined to be
2545 VARYING, which causes i_5 to drop down to VARYING. So, another
2546 visit to i_14 is scheduled. In this second visit, we compute the
2547 exact same range and equivalence set for i_14, namely ~[0, 0] and
2548 { i_5 }. But we did not have the previous range for i_5
2549 registered, so vrp_visit_assignment thinks that the range for
2550 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2551 is not visited again, which stops propagation from visiting
2552 statements in the THEN clause of that if().
2554 To properly fix this we would need to keep the previous range
2555 value for the names in the equivalence set. This way we would've
2556 discovered that from one visit to the other i_5 changed from
2557 range [8, 8] to VR_VARYING.
2559 However, fixing this apparent limitation may not be worth the
2560 additional checking. Testing on several code bases (GCC, DLV,
2561 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2562 4 more predicates folded in SPEC. */
2564 bool sop;
2565 val = vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt),
2566 gimple_cond_lhs (stmt),
2567 gimple_cond_rhs (stmt),
2568 false, &sop, NULL);
2569 if (val)
2570 *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
2572 if (dump_file && (dump_flags & TDF_DETAILS))
2574 fprintf (dump_file, "\nPredicate evaluates to: ");
2575 if (val == NULL_TREE)
2576 fprintf (dump_file, "DON'T KNOW\n");
2577 else
2578 print_generic_stmt (dump_file, val);
2582 /* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2583 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2584 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2585 Returns true if the default label is not needed. */
2587 static bool
2588 find_case_label_ranges (gswitch *stmt, value_range *vr, size_t *min_idx1,
2589 size_t *max_idx1, size_t *min_idx2,
2590 size_t *max_idx2)
2592 size_t i, j, k, l;
2593 unsigned int n = gimple_switch_num_labels (stmt);
2594 bool take_default;
2595 tree case_low, case_high;
2596 tree min = vr->min, max = vr->max;
2598 gcc_checking_assert (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE);
2600 take_default = !find_case_label_range (stmt, min, max, &i, &j);
2602 /* Set second range to emtpy. */
2603 *min_idx2 = 1;
2604 *max_idx2 = 0;
2606 if (vr->type == VR_RANGE)
2608 *min_idx1 = i;
2609 *max_idx1 = j;
2610 return !take_default;
2613 /* Set first range to all case labels. */
2614 *min_idx1 = 1;
2615 *max_idx1 = n - 1;
2617 if (i > j)
2618 return false;
2620 /* Make sure all the values of case labels [i , j] are contained in
2621 range [MIN, MAX]. */
2622 case_low = CASE_LOW (gimple_switch_label (stmt, i));
2623 case_high = CASE_HIGH (gimple_switch_label (stmt, j));
2624 if (tree_int_cst_compare (case_low, min) < 0)
2625 i += 1;
2626 if (case_high != NULL_TREE
2627 && tree_int_cst_compare (max, case_high) < 0)
2628 j -= 1;
2630 if (i > j)
2631 return false;
2633 /* If the range spans case labels [i, j], the corresponding anti-range spans
2634 the labels [1, i - 1] and [j + 1, n - 1]. */
2635 k = j + 1;
2636 l = n - 1;
2637 if (k > l)
2639 k = 1;
2640 l = 0;
2643 j = i - 1;
2644 i = 1;
2645 if (i > j)
2647 i = k;
2648 j = l;
2649 k = 1;
2650 l = 0;
2653 *min_idx1 = i;
2654 *max_idx1 = j;
2655 *min_idx2 = k;
2656 *max_idx2 = l;
2657 return false;
2660 /* Visit switch statement STMT. If we can determine which edge
2661 will be taken out of STMT's basic block, record it in
2662 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2664 void
2665 vr_values::vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p)
2667 tree op, val;
2668 value_range *vr;
2669 size_t i = 0, j = 0, k, l;
2670 bool take_default;
2672 *taken_edge_p = NULL;
2673 op = gimple_switch_index (stmt);
2674 if (TREE_CODE (op) != SSA_NAME)
2675 return;
2677 vr = get_value_range (op);
2678 if (dump_file && (dump_flags & TDF_DETAILS))
2680 fprintf (dump_file, "\nVisiting switch expression with operand ");
2681 print_generic_expr (dump_file, op);
2682 fprintf (dump_file, " with known range ");
2683 dump_value_range (dump_file, vr);
2684 fprintf (dump_file, "\n");
2687 if ((vr->type != VR_RANGE
2688 && vr->type != VR_ANTI_RANGE)
2689 || symbolic_range_p (vr))
2690 return;
2692 /* Find the single edge that is taken from the switch expression. */
2693 take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
2695 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2696 label */
2697 if (j < i)
2699 gcc_assert (take_default);
2700 val = gimple_switch_default_label (stmt);
2702 else
2704 /* Check if labels with index i to j and maybe the default label
2705 are all reaching the same label. */
2707 val = gimple_switch_label (stmt, i);
2708 if (take_default
2709 && CASE_LABEL (gimple_switch_default_label (stmt))
2710 != CASE_LABEL (val))
2712 if (dump_file && (dump_flags & TDF_DETAILS))
2713 fprintf (dump_file, " not a single destination for this "
2714 "range\n");
2715 return;
2717 for (++i; i <= j; ++i)
2719 if (CASE_LABEL (gimple_switch_label (stmt, i)) != CASE_LABEL (val))
2721 if (dump_file && (dump_flags & TDF_DETAILS))
2722 fprintf (dump_file, " not a single destination for this "
2723 "range\n");
2724 return;
2727 for (; k <= l; ++k)
2729 if (CASE_LABEL (gimple_switch_label (stmt, k)) != CASE_LABEL (val))
2731 if (dump_file && (dump_flags & TDF_DETAILS))
2732 fprintf (dump_file, " not a single destination for this "
2733 "range\n");
2734 return;
2739 *taken_edge_p = find_edge (gimple_bb (stmt),
2740 label_to_block (CASE_LABEL (val)));
2742 if (dump_file && (dump_flags & TDF_DETAILS))
2744 fprintf (dump_file, " will take edge to ");
2745 print_generic_stmt (dump_file, CASE_LABEL (val));
2750 /* Evaluate statement STMT. If the statement produces a useful range,
2751 set VR and corepsponding OUTPUT_P.
2753 If STMT is a conditional branch and we can determine its truth
2754 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2756 void
2757 vr_values::extract_range_from_stmt (gimple *stmt, edge *taken_edge_p,
2758 tree *output_p, value_range *vr)
2761 if (dump_file && (dump_flags & TDF_DETAILS))
2763 fprintf (dump_file, "\nVisiting statement:\n");
2764 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2767 if (!stmt_interesting_for_vrp (stmt))
2768 gcc_assert (stmt_ends_bb_p (stmt));
2769 else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
2770 vrp_visit_assignment_or_call (stmt, output_p, vr);
2771 else if (gimple_code (stmt) == GIMPLE_COND)
2772 vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p);
2773 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2774 vrp_visit_switch_stmt (as_a <gswitch *> (stmt), taken_edge_p);
2777 /* Visit all arguments for PHI node PHI that flow through executable
2778 edges. If a valid value range can be derived from all the incoming
2779 value ranges, set a new range in VR_RESULT. */
2781 void
2782 vr_values::extract_range_from_phi_node (gphi *phi, value_range *vr_result)
2784 size_t i;
2785 tree lhs = PHI_RESULT (phi);
2786 value_range *lhs_vr = get_value_range (lhs);
2787 bool first = true;
2788 int edges, old_edges;
2789 struct loop *l;
2791 if (dump_file && (dump_flags & TDF_DETAILS))
2793 fprintf (dump_file, "\nVisiting PHI node: ");
2794 print_gimple_stmt (dump_file, phi, 0, dump_flags);
2797 bool may_simulate_backedge_again = false;
2798 edges = 0;
2799 for (i = 0; i < gimple_phi_num_args (phi); i++)
2801 edge e = gimple_phi_arg_edge (phi, i);
2803 if (dump_file && (dump_flags & TDF_DETAILS))
2805 fprintf (dump_file,
2806 " Argument #%d (%d -> %d %sexecutable)\n",
2807 (int) i, e->src->index, e->dest->index,
2808 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2811 if (e->flags & EDGE_EXECUTABLE)
2813 tree arg = PHI_ARG_DEF (phi, i);
2814 value_range vr_arg;
2816 ++edges;
2818 if (TREE_CODE (arg) == SSA_NAME)
2820 /* See if we are eventually going to change one of the args. */
2821 gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
2822 if (! gimple_nop_p (def_stmt)
2823 && prop_simulate_again_p (def_stmt)
2824 && e->flags & EDGE_DFS_BACK)
2825 may_simulate_backedge_again = true;
2827 vr_arg = *(get_value_range (arg));
2828 /* Do not allow equivalences or symbolic ranges to leak in from
2829 backedges. That creates invalid equivalencies.
2830 See PR53465 and PR54767. */
2831 if (e->flags & EDGE_DFS_BACK)
2833 if (vr_arg.type == VR_RANGE
2834 || vr_arg.type == VR_ANTI_RANGE)
2836 vr_arg.equiv = NULL;
2837 if (symbolic_range_p (&vr_arg))
2839 vr_arg.type = VR_VARYING;
2840 vr_arg.min = NULL_TREE;
2841 vr_arg.max = NULL_TREE;
2845 else
2847 /* If the non-backedge arguments range is VR_VARYING then
2848 we can still try recording a simple equivalence. */
2849 if (vr_arg.type == VR_VARYING)
2851 vr_arg.type = VR_RANGE;
2852 vr_arg.min = arg;
2853 vr_arg.max = arg;
2854 vr_arg.equiv = NULL;
2858 else
2860 if (TREE_OVERFLOW_P (arg))
2861 arg = drop_tree_overflow (arg);
2863 vr_arg.type = VR_RANGE;
2864 vr_arg.min = arg;
2865 vr_arg.max = arg;
2866 vr_arg.equiv = NULL;
2869 if (dump_file && (dump_flags & TDF_DETAILS))
2871 fprintf (dump_file, "\t");
2872 print_generic_expr (dump_file, arg, dump_flags);
2873 fprintf (dump_file, ": ");
2874 dump_value_range (dump_file, &vr_arg);
2875 fprintf (dump_file, "\n");
2878 if (first)
2879 copy_value_range (vr_result, &vr_arg);
2880 else
2881 vrp_meet (vr_result, &vr_arg);
2882 first = false;
2884 if (vr_result->type == VR_VARYING)
2885 break;
2889 if (vr_result->type == VR_VARYING)
2890 goto varying;
2891 else if (vr_result->type == VR_UNDEFINED)
2892 goto update_range;
2894 old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
2895 vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
2897 /* To prevent infinite iterations in the algorithm, derive ranges
2898 when the new value is slightly bigger or smaller than the
2899 previous one. We don't do this if we have seen a new executable
2900 edge; this helps us avoid an infinity for conditionals
2901 which are not in a loop. If the old value-range was VR_UNDEFINED
2902 use the updated range and iterate one more time. If we will not
2903 simulate this PHI again via the backedge allow us to iterate. */
2904 if (edges > 0
2905 && gimple_phi_num_args (phi) > 1
2906 && edges == old_edges
2907 && lhs_vr->type != VR_UNDEFINED
2908 && may_simulate_backedge_again)
2910 /* Compare old and new ranges, fall back to varying if the
2911 values are not comparable. */
2912 int cmp_min = compare_values (lhs_vr->min, vr_result->min);
2913 if (cmp_min == -2)
2914 goto varying;
2915 int cmp_max = compare_values (lhs_vr->max, vr_result->max);
2916 if (cmp_max == -2)
2917 goto varying;
2919 /* For non VR_RANGE or for pointers fall back to varying if
2920 the range changed. */
2921 if ((lhs_vr->type != VR_RANGE || vr_result->type != VR_RANGE
2922 || POINTER_TYPE_P (TREE_TYPE (lhs)))
2923 && (cmp_min != 0 || cmp_max != 0))
2924 goto varying;
2926 /* If the new minimum is larger than the previous one
2927 retain the old value. If the new minimum value is smaller
2928 than the previous one and not -INF go all the way to -INF + 1.
2929 In the first case, to avoid infinite bouncing between different
2930 minimums, and in the other case to avoid iterating millions of
2931 times to reach -INF. Going to -INF + 1 also lets the following
2932 iteration compute whether there will be any overflow, at the
2933 expense of one additional iteration. */
2934 if (cmp_min < 0)
2935 vr_result->min = lhs_vr->min;
2936 else if (cmp_min > 0
2937 && !vrp_val_is_min (vr_result->min))
2938 vr_result->min
2939 = int_const_binop (PLUS_EXPR,
2940 vrp_val_min (TREE_TYPE (vr_result->min)),
2941 build_int_cst (TREE_TYPE (vr_result->min), 1));
2943 /* Similarly for the maximum value. */
2944 if (cmp_max > 0)
2945 vr_result->max = lhs_vr->max;
2946 else if (cmp_max < 0
2947 && !vrp_val_is_max (vr_result->max))
2948 vr_result->max
2949 = int_const_binop (MINUS_EXPR,
2950 vrp_val_max (TREE_TYPE (vr_result->min)),
2951 build_int_cst (TREE_TYPE (vr_result->min), 1));
2953 /* If we dropped either bound to +-INF then if this is a loop
2954 PHI node SCEV may known more about its value-range. */
2955 if (cmp_min > 0 || cmp_min < 0
2956 || cmp_max < 0 || cmp_max > 0)
2957 goto scev_check;
2959 goto infinite_check;
2962 goto update_range;
2964 varying:
2965 set_value_range_to_varying (vr_result);
2967 scev_check:
2968 /* If this is a loop PHI node SCEV may known more about its value-range.
2969 scev_check can be reached from two paths, one is a fall through from above
2970 "varying" label, the other is direct goto from code block which tries to
2971 avoid infinite simulation. */
2972 if (scev_initialized_p ()
2973 && (l = loop_containing_stmt (phi))
2974 && l->header == gimple_bb (phi))
2975 adjust_range_with_scev (vr_result, l, phi, lhs);
2977 infinite_check:
2978 /* If we will end up with a (-INF, +INF) range, set it to
2979 VARYING. Same if the previous max value was invalid for
2980 the type and we end up with vr_result.min > vr_result.max. */
2981 if ((vr_result->type == VR_RANGE || vr_result->type == VR_ANTI_RANGE)
2982 && !((vrp_val_is_max (vr_result->max) && vrp_val_is_min (vr_result->min))
2983 || compare_values (vr_result->min, vr_result->max) > 0))
2985 else
2986 set_value_range_to_varying (vr_result);
2988 /* If the new range is different than the previous value, keep
2989 iterating. */
2990 update_range:
2991 return;
2994 /* Simplify boolean operations if the source is known
2995 to be already a boolean. */
2996 bool
2997 vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi,
2998 gimple *stmt)
3000 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3001 tree lhs, op0, op1;
3002 bool need_conversion;
3004 /* We handle only !=/== case here. */
3005 gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
3007 op0 = gimple_assign_rhs1 (stmt);
3008 if (!op_with_boolean_value_range_p (op0))
3009 return false;
3011 op1 = gimple_assign_rhs2 (stmt);
3012 if (!op_with_boolean_value_range_p (op1))
3013 return false;
3015 /* Reduce number of cases to handle to NE_EXPR. As there is no
3016 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
3017 if (rhs_code == EQ_EXPR)
3019 if (TREE_CODE (op1) == INTEGER_CST)
3020 op1 = int_const_binop (BIT_XOR_EXPR, op1,
3021 build_int_cst (TREE_TYPE (op1), 1));
3022 else
3023 return false;
3026 lhs = gimple_assign_lhs (stmt);
3027 need_conversion
3028 = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0));
3030 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
3031 if (need_conversion
3032 && !TYPE_UNSIGNED (TREE_TYPE (op0))
3033 && TYPE_PRECISION (TREE_TYPE (op0)) == 1
3034 && TYPE_PRECISION (TREE_TYPE (lhs)) > 1)
3035 return false;
3037 /* For A != 0 we can substitute A itself. */
3038 if (integer_zerop (op1))
3039 gimple_assign_set_rhs_with_ops (gsi,
3040 need_conversion
3041 ? NOP_EXPR : TREE_CODE (op0), op0);
3042 /* For A != B we substitute A ^ B. Either with conversion. */
3043 else if (need_conversion)
3045 tree tem = make_ssa_name (TREE_TYPE (op0));
3046 gassign *newop
3047 = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1);
3048 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
3049 if (INTEGRAL_TYPE_P (TREE_TYPE (tem))
3050 && TYPE_PRECISION (TREE_TYPE (tem)) > 1)
3051 set_range_info (tem, VR_RANGE,
3052 wi::zero (TYPE_PRECISION (TREE_TYPE (tem))),
3053 wi::one (TYPE_PRECISION (TREE_TYPE (tem))));
3054 gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem);
3056 /* Or without. */
3057 else
3058 gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1);
3059 update_stmt (gsi_stmt (*gsi));
3060 fold_stmt (gsi, follow_single_use_edges);
3062 return true;
3065 /* Simplify a division or modulo operator to a right shift or bitwise and
3066 if the first operand is unsigned or is greater than zero and the second
3067 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
3068 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
3069 optimize it into just op0 if op0's range is known to be a subset of
3070 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3071 modulo. */
3073 bool
3074 vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator *gsi,
3075 gimple *stmt)
3077 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3078 tree val = NULL;
3079 tree op0 = gimple_assign_rhs1 (stmt);
3080 tree op1 = gimple_assign_rhs2 (stmt);
3081 tree op0min = NULL_TREE, op0max = NULL_TREE;
3082 tree op1min = op1;
3083 value_range *vr = NULL;
3085 if (TREE_CODE (op0) == INTEGER_CST)
3087 op0min = op0;
3088 op0max = op0;
3090 else
3092 vr = get_value_range (op0);
3093 if (range_int_cst_p (vr))
3095 op0min = vr->min;
3096 op0max = vr->max;
3100 if (rhs_code == TRUNC_MOD_EXPR
3101 && TREE_CODE (op1) == SSA_NAME)
3103 value_range *vr1 = get_value_range (op1);
3104 if (range_int_cst_p (vr1))
3105 op1min = vr1->min;
3107 if (rhs_code == TRUNC_MOD_EXPR
3108 && TREE_CODE (op1min) == INTEGER_CST
3109 && tree_int_cst_sgn (op1min) == 1
3110 && op0max
3111 && tree_int_cst_lt (op0max, op1min))
3113 if (TYPE_UNSIGNED (TREE_TYPE (op0))
3114 || tree_int_cst_sgn (op0min) >= 0
3115 || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min),
3116 op0min))
3118 /* If op0 already has the range op0 % op1 has,
3119 then TRUNC_MOD_EXPR won't change anything. */
3120 gimple_assign_set_rhs_from_tree (gsi, op0);
3121 return true;
3125 if (TREE_CODE (op0) != SSA_NAME)
3126 return false;
3128 if (!integer_pow2p (op1))
3130 /* X % -Y can be only optimized into X % Y either if
3131 X is not INT_MIN, or Y is not -1. Fold it now, as after
3132 remove_range_assertions the range info might be not available
3133 anymore. */
3134 if (rhs_code == TRUNC_MOD_EXPR
3135 && fold_stmt (gsi, follow_single_use_edges))
3136 return true;
3137 return false;
3140 if (TYPE_UNSIGNED (TREE_TYPE (op0)))
3141 val = integer_one_node;
3142 else
3144 bool sop = false;
3146 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
3148 if (val
3149 && sop
3150 && integer_onep (val)
3151 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3153 location_t location;
3155 if (!gimple_has_location (stmt))
3156 location = input_location;
3157 else
3158 location = gimple_location (stmt);
3159 warning_at (location, OPT_Wstrict_overflow,
3160 "assuming signed overflow does not occur when "
3161 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3165 if (val && integer_onep (val))
3167 tree t;
3169 if (rhs_code == TRUNC_DIV_EXPR)
3171 t = build_int_cst (integer_type_node, tree_log2 (op1));
3172 gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
3173 gimple_assign_set_rhs1 (stmt, op0);
3174 gimple_assign_set_rhs2 (stmt, t);
3176 else
3178 t = build_int_cst (TREE_TYPE (op1), 1);
3179 t = int_const_binop (MINUS_EXPR, op1, t);
3180 t = fold_convert (TREE_TYPE (op0), t);
3182 gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
3183 gimple_assign_set_rhs1 (stmt, op0);
3184 gimple_assign_set_rhs2 (stmt, t);
3187 update_stmt (stmt);
3188 fold_stmt (gsi, follow_single_use_edges);
3189 return true;
3192 return false;
3195 /* Simplify a min or max if the ranges of the two operands are
3196 disjoint. Return true if we do simplify. */
3198 bool
3199 vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator *gsi,
3200 gimple *stmt)
3202 tree op0 = gimple_assign_rhs1 (stmt);
3203 tree op1 = gimple_assign_rhs2 (stmt);
3204 bool sop = false;
3205 tree val;
3207 val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3208 (LE_EXPR, op0, op1, &sop));
3209 if (!val)
3211 sop = false;
3212 val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3213 (LT_EXPR, op0, op1, &sop));
3216 if (val)
3218 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3220 location_t location;
3222 if (!gimple_has_location (stmt))
3223 location = input_location;
3224 else
3225 location = gimple_location (stmt);
3226 warning_at (location, OPT_Wstrict_overflow,
3227 "assuming signed overflow does not occur when "
3228 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3231 /* VAL == TRUE -> OP0 < or <= op1
3232 VAL == FALSE -> OP0 > or >= op1. */
3233 tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
3234 == integer_zerop (val)) ? op0 : op1;
3235 gimple_assign_set_rhs_from_tree (gsi, res);
3236 return true;
3239 return false;
3242 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3243 ABS_EXPR. If the operand is <= 0, then simplify the
3244 ABS_EXPR into a NEGATE_EXPR. */
3246 bool
3247 vr_values::simplify_abs_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
3249 tree op = gimple_assign_rhs1 (stmt);
3250 value_range *vr = get_value_range (op);
3252 if (vr)
3254 tree val = NULL;
3255 bool sop = false;
3257 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop);
3258 if (!val)
3260 /* The range is neither <= 0 nor > 0. Now see if it is
3261 either < 0 or >= 0. */
3262 sop = false;
3263 val = compare_range_with_value (LT_EXPR, vr, integer_zero_node,
3264 &sop);
3267 if (val)
3269 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3271 location_t location;
3273 if (!gimple_has_location (stmt))
3274 location = input_location;
3275 else
3276 location = gimple_location (stmt);
3277 warning_at (location, OPT_Wstrict_overflow,
3278 "assuming signed overflow does not occur when "
3279 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3282 gimple_assign_set_rhs1 (stmt, op);
3283 if (integer_zerop (val))
3284 gimple_assign_set_rhs_code (stmt, SSA_NAME);
3285 else
3286 gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
3287 update_stmt (stmt);
3288 fold_stmt (gsi, follow_single_use_edges);
3289 return true;
3293 return false;
3296 /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3297 If all the bits that are being cleared by & are already
3298 known to be zero from VR, or all the bits that are being
3299 set by | are already known to be one from VR, the bit
3300 operation is redundant. */
3302 bool
3303 vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi,
3304 gimple *stmt)
3306 tree op0 = gimple_assign_rhs1 (stmt);
3307 tree op1 = gimple_assign_rhs2 (stmt);
3308 tree op = NULL_TREE;
3309 value_range vr0 = VR_INITIALIZER;
3310 value_range vr1 = VR_INITIALIZER;
3311 wide_int may_be_nonzero0, may_be_nonzero1;
3312 wide_int must_be_nonzero0, must_be_nonzero1;
3313 wide_int mask;
3315 if (TREE_CODE (op0) == SSA_NAME)
3316 vr0 = *(get_value_range (op0));
3317 else if (is_gimple_min_invariant (op0))
3318 set_value_range_to_value (&vr0, op0, NULL);
3319 else
3320 return false;
3322 if (TREE_CODE (op1) == SSA_NAME)
3323 vr1 = *(get_value_range (op1));
3324 else if (is_gimple_min_invariant (op1))
3325 set_value_range_to_value (&vr1, op1, NULL);
3326 else
3327 return false;
3329 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op0), &vr0, &may_be_nonzero0,
3330 &must_be_nonzero0))
3331 return false;
3332 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op1), &vr1, &may_be_nonzero1,
3333 &must_be_nonzero1))
3334 return false;
3336 switch (gimple_assign_rhs_code (stmt))
3338 case BIT_AND_EXPR:
3339 mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
3340 if (mask == 0)
3342 op = op0;
3343 break;
3345 mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
3346 if (mask == 0)
3348 op = op1;
3349 break;
3351 break;
3352 case BIT_IOR_EXPR:
3353 mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
3354 if (mask == 0)
3356 op = op1;
3357 break;
3359 mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
3360 if (mask == 0)
3362 op = op0;
3363 break;
3365 break;
3366 default:
3367 gcc_unreachable ();
3370 if (op == NULL_TREE)
3371 return false;
3373 gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op);
3374 update_stmt (gsi_stmt (*gsi));
3375 return true;
3378 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3379 a known value range VR.
3381 If there is one and only one value which will satisfy the
3382 conditional, then return that value. Else return NULL.
3384 If signed overflow must be undefined for the value to satisfy
3385 the conditional, then set *STRICT_OVERFLOW_P to true. */
3387 static tree
3388 test_for_singularity (enum tree_code cond_code, tree op0,
3389 tree op1, value_range *vr)
3391 tree min = NULL;
3392 tree max = NULL;
3394 /* Extract minimum/maximum values which satisfy the conditional as it was
3395 written. */
3396 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
3398 min = TYPE_MIN_VALUE (TREE_TYPE (op0));
3400 max = op1;
3401 if (cond_code == LT_EXPR)
3403 tree one = build_int_cst (TREE_TYPE (op0), 1);
3404 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
3405 /* Signal to compare_values_warnv this expr doesn't overflow. */
3406 if (EXPR_P (max))
3407 TREE_NO_WARNING (max) = 1;
3410 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
3412 max = TYPE_MAX_VALUE (TREE_TYPE (op0));
3414 min = op1;
3415 if (cond_code == GT_EXPR)
3417 tree one = build_int_cst (TREE_TYPE (op0), 1);
3418 min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
3419 /* Signal to compare_values_warnv this expr doesn't overflow. */
3420 if (EXPR_P (min))
3421 TREE_NO_WARNING (min) = 1;
3425 /* Now refine the minimum and maximum values using any
3426 value range information we have for op0. */
3427 if (min && max)
3429 if (compare_values (vr->min, min) == 1)
3430 min = vr->min;
3431 if (compare_values (vr->max, max) == -1)
3432 max = vr->max;
3434 /* If the new min/max values have converged to a single value,
3435 then there is only one value which can satisfy the condition,
3436 return that value. */
3437 if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
3438 return min;
3440 return NULL;
3443 /* Return whether the value range *VR fits in an integer type specified
3444 by PRECISION and UNSIGNED_P. */
3446 static bool
3447 range_fits_type_p (value_range *vr, unsigned dest_precision, signop dest_sgn)
3449 tree src_type;
3450 unsigned src_precision;
3451 widest_int tem;
3452 signop src_sgn;
3454 /* We can only handle integral and pointer types. */
3455 src_type = TREE_TYPE (vr->min);
3456 if (!INTEGRAL_TYPE_P (src_type)
3457 && !POINTER_TYPE_P (src_type))
3458 return false;
3460 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3461 and so is an identity transform. */
3462 src_precision = TYPE_PRECISION (TREE_TYPE (vr->min));
3463 src_sgn = TYPE_SIGN (src_type);
3464 if ((src_precision < dest_precision
3465 && !(dest_sgn == UNSIGNED && src_sgn == SIGNED))
3466 || (src_precision == dest_precision && src_sgn == dest_sgn))
3467 return true;
3469 /* Now we can only handle ranges with constant bounds. */
3470 if (vr->type != VR_RANGE
3471 || TREE_CODE (vr->min) != INTEGER_CST
3472 || TREE_CODE (vr->max) != INTEGER_CST)
3473 return false;
3475 /* For sign changes, the MSB of the wide_int has to be clear.
3476 An unsigned value with its MSB set cannot be represented by
3477 a signed wide_int, while a negative value cannot be represented
3478 by an unsigned wide_int. */
3479 if (src_sgn != dest_sgn
3480 && (wi::lts_p (wi::to_wide (vr->min), 0)
3481 || wi::lts_p (wi::to_wide (vr->max), 0)))
3482 return false;
3484 /* Then we can perform the conversion on both ends and compare
3485 the result for equality. */
3486 tem = wi::ext (wi::to_widest (vr->min), dest_precision, dest_sgn);
3487 if (tem != wi::to_widest (vr->min))
3488 return false;
3489 tem = wi::ext (wi::to_widest (vr->max), dest_precision, dest_sgn);
3490 if (tem != wi::to_widest (vr->max))
3491 return false;
3493 return true;
3496 /* Simplify a conditional using a relational operator to an equality
3497 test if the range information indicates only one value can satisfy
3498 the original conditional. */
3500 bool
3501 vr_values::simplify_cond_using_ranges_1 (gcond *stmt)
3503 tree op0 = gimple_cond_lhs (stmt);
3504 tree op1 = gimple_cond_rhs (stmt);
3505 enum tree_code cond_code = gimple_cond_code (stmt);
3507 if (cond_code != NE_EXPR
3508 && cond_code != EQ_EXPR
3509 && TREE_CODE (op0) == SSA_NAME
3510 && INTEGRAL_TYPE_P (TREE_TYPE (op0))
3511 && is_gimple_min_invariant (op1))
3513 value_range *vr = get_value_range (op0);
3515 /* If we have range information for OP0, then we might be
3516 able to simplify this conditional. */
3517 if (vr->type == VR_RANGE)
3519 tree new_tree = test_for_singularity (cond_code, op0, op1, vr);
3520 if (new_tree)
3522 if (dump_file)
3524 fprintf (dump_file, "Simplified relational ");
3525 print_gimple_stmt (dump_file, stmt, 0);
3526 fprintf (dump_file, " into ");
3529 gimple_cond_set_code (stmt, EQ_EXPR);
3530 gimple_cond_set_lhs (stmt, op0);
3531 gimple_cond_set_rhs (stmt, new_tree);
3533 update_stmt (stmt);
3535 if (dump_file)
3537 print_gimple_stmt (dump_file, stmt, 0);
3538 fprintf (dump_file, "\n");
3541 return true;
3544 /* Try again after inverting the condition. We only deal
3545 with integral types here, so no need to worry about
3546 issues with inverting FP comparisons. */
3547 new_tree = test_for_singularity
3548 (invert_tree_comparison (cond_code, false),
3549 op0, op1, vr);
3550 if (new_tree)
3552 if (dump_file)
3554 fprintf (dump_file, "Simplified relational ");
3555 print_gimple_stmt (dump_file, stmt, 0);
3556 fprintf (dump_file, " into ");
3559 gimple_cond_set_code (stmt, NE_EXPR);
3560 gimple_cond_set_lhs (stmt, op0);
3561 gimple_cond_set_rhs (stmt, new_tree);
3563 update_stmt (stmt);
3565 if (dump_file)
3567 print_gimple_stmt (dump_file, stmt, 0);
3568 fprintf (dump_file, "\n");
3571 return true;
3575 return false;
3578 /* STMT is a conditional at the end of a basic block.
3580 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3581 was set via a type conversion, try to replace the SSA_NAME with the RHS
3582 of the type conversion. Doing so makes the conversion dead which helps
3583 subsequent passes. */
3585 void
3586 vr_values::simplify_cond_using_ranges_2 (gcond *stmt)
3588 tree op0 = gimple_cond_lhs (stmt);
3589 tree op1 = gimple_cond_rhs (stmt);
3591 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3592 see if OP0 was set by a type conversion where the source of
3593 the conversion is another SSA_NAME with a range that fits
3594 into the range of OP0's type.
3596 If so, the conversion is redundant as the earlier SSA_NAME can be
3597 used for the comparison directly if we just massage the constant in the
3598 comparison. */
3599 if (TREE_CODE (op0) == SSA_NAME
3600 && TREE_CODE (op1) == INTEGER_CST)
3602 gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
3603 tree innerop;
3605 if (!is_gimple_assign (def_stmt)
3606 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
3607 return;
3609 innerop = gimple_assign_rhs1 (def_stmt);
3611 if (TREE_CODE (innerop) == SSA_NAME
3612 && !POINTER_TYPE_P (TREE_TYPE (innerop))
3613 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
3614 && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
3616 value_range *vr = get_value_range (innerop);
3618 if (range_int_cst_p (vr)
3619 && range_fits_type_p (vr,
3620 TYPE_PRECISION (TREE_TYPE (op0)),
3621 TYPE_SIGN (TREE_TYPE (op0)))
3622 && int_fits_type_p (op1, TREE_TYPE (innerop)))
3624 tree newconst = fold_convert (TREE_TYPE (innerop), op1);
3625 gimple_cond_set_lhs (stmt, innerop);
3626 gimple_cond_set_rhs (stmt, newconst);
3627 update_stmt (stmt);
3628 if (dump_file && (dump_flags & TDF_DETAILS))
3630 fprintf (dump_file, "Folded into: ");
3631 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3632 fprintf (dump_file, "\n");
3639 /* Simplify a switch statement using the value range of the switch
3640 argument. */
3642 bool
3643 vr_values::simplify_switch_using_ranges (gswitch *stmt)
3645 tree op = gimple_switch_index (stmt);
3646 value_range *vr = NULL;
3647 bool take_default;
3648 edge e;
3649 edge_iterator ei;
3650 size_t i = 0, j = 0, n, n2;
3651 tree vec2;
3652 switch_update su;
3653 size_t k = 1, l = 0;
3655 if (TREE_CODE (op) == SSA_NAME)
3657 vr = get_value_range (op);
3659 /* We can only handle integer ranges. */
3660 if ((vr->type != VR_RANGE
3661 && vr->type != VR_ANTI_RANGE)
3662 || symbolic_range_p (vr))
3663 return false;
3665 /* Find case label for min/max of the value range. */
3666 take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
3668 else if (TREE_CODE (op) == INTEGER_CST)
3670 take_default = !find_case_label_index (stmt, 1, op, &i);
3671 if (take_default)
3673 i = 1;
3674 j = 0;
3676 else
3678 j = i;
3681 else
3682 return false;
3684 n = gimple_switch_num_labels (stmt);
3686 /* We can truncate the case label ranges that partially overlap with OP's
3687 value range. */
3688 size_t min_idx = 1, max_idx = 0;
3689 if (vr != NULL)
3690 find_case_label_range (stmt, vr->min, vr->max, &min_idx, &max_idx);
3691 if (min_idx <= max_idx)
3693 tree min_label = gimple_switch_label (stmt, min_idx);
3694 tree max_label = gimple_switch_label (stmt, max_idx);
3696 /* Avoid changing the type of the case labels when truncating. */
3697 tree case_label_type = TREE_TYPE (CASE_LOW (min_label));
3698 tree vr_min = fold_convert (case_label_type, vr->min);
3699 tree vr_max = fold_convert (case_label_type, vr->max);
3701 if (vr->type == VR_RANGE)
3703 /* If OP's value range is [2,8] and the low label range is
3704 0 ... 3, truncate the label's range to 2 .. 3. */
3705 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3706 && CASE_HIGH (min_label) != NULL_TREE
3707 && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
3708 CASE_LOW (min_label) = vr_min;
3710 /* If OP's value range is [2,8] and the high label range is
3711 7 ... 10, truncate the label's range to 7 .. 8. */
3712 if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
3713 && CASE_HIGH (max_label) != NULL_TREE
3714 && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
3715 CASE_HIGH (max_label) = vr_max;
3717 else if (vr->type == VR_ANTI_RANGE)
3719 tree one_cst = build_one_cst (case_label_type);
3721 if (min_label == max_label)
3723 /* If OP's value range is ~[7,8] and the label's range is
3724 7 ... 10, truncate the label's range to 9 ... 10. */
3725 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) == 0
3726 && CASE_HIGH (min_label) != NULL_TREE
3727 && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) > 0)
3728 CASE_LOW (min_label)
3729 = int_const_binop (PLUS_EXPR, vr_max, one_cst);
3731 /* If OP's value range is ~[7,8] and the label's range is
3732 5 ... 8, truncate the label's range to 5 ... 6. */
3733 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3734 && CASE_HIGH (min_label) != NULL_TREE
3735 && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) == 0)
3736 CASE_HIGH (min_label)
3737 = int_const_binop (MINUS_EXPR, vr_min, one_cst);
3739 else
3741 /* If OP's value range is ~[2,8] and the low label range is
3742 0 ... 3, truncate the label's range to 0 ... 1. */
3743 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3744 && CASE_HIGH (min_label) != NULL_TREE
3745 && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
3746 CASE_HIGH (min_label)
3747 = int_const_binop (MINUS_EXPR, vr_min, one_cst);
3749 /* If OP's value range is ~[2,8] and the high label range is
3750 7 ... 10, truncate the label's range to 9 ... 10. */
3751 if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
3752 && CASE_HIGH (max_label) != NULL_TREE
3753 && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
3754 CASE_LOW (max_label)
3755 = int_const_binop (PLUS_EXPR, vr_max, one_cst);
3759 /* Canonicalize singleton case ranges. */
3760 if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label)))
3761 CASE_HIGH (min_label) = NULL_TREE;
3762 if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label)))
3763 CASE_HIGH (max_label) = NULL_TREE;
3766 /* We can also eliminate case labels that lie completely outside OP's value
3767 range. */
3769 /* Bail out if this is just all edges taken. */
3770 if (i == 1
3771 && j == n - 1
3772 && take_default)
3773 return false;
3775 /* Build a new vector of taken case labels. */
3776 vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default);
3777 n2 = 0;
3779 /* Add the default edge, if necessary. */
3780 if (take_default)
3781 TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt);
3783 for (; i <= j; ++i, ++n2)
3784 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i);
3786 for (; k <= l; ++k, ++n2)
3787 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k);
3789 /* Mark needed edges. */
3790 for (i = 0; i < n2; ++i)
3792 e = find_edge (gimple_bb (stmt),
3793 label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
3794 e->aux = (void *)-1;
3797 /* Queue not needed edges for later removal. */
3798 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
3800 if (e->aux == (void *)-1)
3802 e->aux = NULL;
3803 continue;
3806 if (dump_file && (dump_flags & TDF_DETAILS))
3808 fprintf (dump_file, "removing unreachable case label\n");
3810 to_remove_edges.safe_push (e);
3811 e->flags &= ~EDGE_EXECUTABLE;
3814 /* And queue an update for the stmt. */
3815 su.stmt = stmt;
3816 su.vec = vec2;
3817 to_update_switch_stmts.safe_push (su);
3818 return false;
3821 /* Simplify an integral conversion from an SSA name in STMT. */
3823 static bool
3824 simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
3826 tree innerop, middleop, finaltype;
3827 gimple *def_stmt;
3828 signop inner_sgn, middle_sgn, final_sgn;
3829 unsigned inner_prec, middle_prec, final_prec;
3830 widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
3832 finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
3833 if (!INTEGRAL_TYPE_P (finaltype))
3834 return false;
3835 middleop = gimple_assign_rhs1 (stmt);
3836 def_stmt = SSA_NAME_DEF_STMT (middleop);
3837 if (!is_gimple_assign (def_stmt)
3838 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
3839 return false;
3840 innerop = gimple_assign_rhs1 (def_stmt);
3841 if (TREE_CODE (innerop) != SSA_NAME
3842 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
3843 return false;
3845 /* Get the value-range of the inner operand. Use get_range_info in
3846 case innerop was created during substitute-and-fold. */
3847 wide_int imin, imax;
3848 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop))
3849 || get_range_info (innerop, &imin, &imax) != VR_RANGE)
3850 return false;
3851 innermin = widest_int::from (imin, TYPE_SIGN (TREE_TYPE (innerop)));
3852 innermax = widest_int::from (imax, TYPE_SIGN (TREE_TYPE (innerop)));
3854 /* Simulate the conversion chain to check if the result is equal if
3855 the middle conversion is removed. */
3856 inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
3857 middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
3858 final_prec = TYPE_PRECISION (finaltype);
3860 /* If the first conversion is not injective, the second must not
3861 be widening. */
3862 if (wi::gtu_p (innermax - innermin,
3863 wi::mask <widest_int> (middle_prec, false))
3864 && middle_prec < final_prec)
3865 return false;
3866 /* We also want a medium value so that we can track the effect that
3867 narrowing conversions with sign change have. */
3868 inner_sgn = TYPE_SIGN (TREE_TYPE (innerop));
3869 if (inner_sgn == UNSIGNED)
3870 innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false);
3871 else
3872 innermed = 0;
3873 if (wi::cmp (innermin, innermed, inner_sgn) >= 0
3874 || wi::cmp (innermed, innermax, inner_sgn) >= 0)
3875 innermed = innermin;
3877 middle_sgn = TYPE_SIGN (TREE_TYPE (middleop));
3878 middlemin = wi::ext (innermin, middle_prec, middle_sgn);
3879 middlemed = wi::ext (innermed, middle_prec, middle_sgn);
3880 middlemax = wi::ext (innermax, middle_prec, middle_sgn);
3882 /* Require that the final conversion applied to both the original
3883 and the intermediate range produces the same result. */
3884 final_sgn = TYPE_SIGN (finaltype);
3885 if (wi::ext (middlemin, final_prec, final_sgn)
3886 != wi::ext (innermin, final_prec, final_sgn)
3887 || wi::ext (middlemed, final_prec, final_sgn)
3888 != wi::ext (innermed, final_prec, final_sgn)
3889 || wi::ext (middlemax, final_prec, final_sgn)
3890 != wi::ext (innermax, final_prec, final_sgn))
3891 return false;
3893 gimple_assign_set_rhs1 (stmt, innerop);
3894 fold_stmt (gsi, follow_single_use_edges);
3895 return true;
3898 /* Simplify a conversion from integral SSA name to float in STMT. */
3900 bool
3901 vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi,
3902 gimple *stmt)
3904 tree rhs1 = gimple_assign_rhs1 (stmt);
3905 value_range *vr = get_value_range (rhs1);
3906 scalar_float_mode fltmode
3907 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
3908 scalar_int_mode mode;
3909 tree tem;
3910 gassign *conv;
3912 /* We can only handle constant ranges. */
3913 if (vr->type != VR_RANGE
3914 || TREE_CODE (vr->min) != INTEGER_CST
3915 || TREE_CODE (vr->max) != INTEGER_CST)
3916 return false;
3918 /* First check if we can use a signed type in place of an unsigned. */
3919 scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1));
3920 if (TYPE_UNSIGNED (TREE_TYPE (rhs1))
3921 && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing
3922 && range_fits_type_p (vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED))
3923 mode = rhs_mode;
3924 /* If we can do the conversion in the current input mode do nothing. */
3925 else if (can_float_p (fltmode, rhs_mode,
3926 TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing)
3927 return false;
3928 /* Otherwise search for a mode we can use, starting from the narrowest
3929 integer mode available. */
3930 else
3932 mode = NARROWEST_INT_MODE;
3933 for (;;)
3935 /* If we cannot do a signed conversion to float from mode
3936 or if the value-range does not fit in the signed type
3937 try with a wider mode. */
3938 if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing
3939 && range_fits_type_p (vr, GET_MODE_PRECISION (mode), SIGNED))
3940 break;
3942 /* But do not widen the input. Instead leave that to the
3943 optabs expansion code. */
3944 if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
3945 || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1)))
3946 return false;
3950 /* It works, insert a truncation or sign-change before the
3951 float conversion. */
3952 tem = make_ssa_name (build_nonstandard_integer_type
3953 (GET_MODE_PRECISION (mode), 0));
3954 conv = gimple_build_assign (tem, NOP_EXPR, rhs1);
3955 gsi_insert_before (gsi, conv, GSI_SAME_STMT);
3956 gimple_assign_set_rhs1 (stmt, tem);
3957 fold_stmt (gsi, follow_single_use_edges);
3959 return true;
3962 /* Simplify an internal fn call using ranges if possible. */
3964 bool
3965 vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi,
3966 gimple *stmt)
3968 enum tree_code subcode;
3969 bool is_ubsan = false;
3970 bool ovf = false;
3971 switch (gimple_call_internal_fn (stmt))
3973 case IFN_UBSAN_CHECK_ADD:
3974 subcode = PLUS_EXPR;
3975 is_ubsan = true;
3976 break;
3977 case IFN_UBSAN_CHECK_SUB:
3978 subcode = MINUS_EXPR;
3979 is_ubsan = true;
3980 break;
3981 case IFN_UBSAN_CHECK_MUL:
3982 subcode = MULT_EXPR;
3983 is_ubsan = true;
3984 break;
3985 case IFN_ADD_OVERFLOW:
3986 subcode = PLUS_EXPR;
3987 break;
3988 case IFN_SUB_OVERFLOW:
3989 subcode = MINUS_EXPR;
3990 break;
3991 case IFN_MUL_OVERFLOW:
3992 subcode = MULT_EXPR;
3993 break;
3994 default:
3995 return false;
3998 tree op0 = gimple_call_arg (stmt, 0);
3999 tree op1 = gimple_call_arg (stmt, 1);
4000 tree type;
4001 if (is_ubsan)
4003 type = TREE_TYPE (op0);
4004 if (VECTOR_TYPE_P (type))
4005 return false;
4007 else if (gimple_call_lhs (stmt) == NULL_TREE)
4008 return false;
4009 else
4010 type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt)));
4011 if (!check_for_binary_op_overflow (subcode, type, op0, op1, &ovf)
4012 || (is_ubsan && ovf))
4013 return false;
4015 gimple *g;
4016 location_t loc = gimple_location (stmt);
4017 if (is_ubsan)
4018 g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1);
4019 else
4021 int prec = TYPE_PRECISION (type);
4022 tree utype = type;
4023 if (ovf
4024 || !useless_type_conversion_p (type, TREE_TYPE (op0))
4025 || !useless_type_conversion_p (type, TREE_TYPE (op1)))
4026 utype = build_nonstandard_integer_type (prec, 1);
4027 if (TREE_CODE (op0) == INTEGER_CST)
4028 op0 = fold_convert (utype, op0);
4029 else if (!useless_type_conversion_p (utype, TREE_TYPE (op0)))
4031 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0);
4032 gimple_set_location (g, loc);
4033 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4034 op0 = gimple_assign_lhs (g);
4036 if (TREE_CODE (op1) == INTEGER_CST)
4037 op1 = fold_convert (utype, op1);
4038 else if (!useless_type_conversion_p (utype, TREE_TYPE (op1)))
4040 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1);
4041 gimple_set_location (g, loc);
4042 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4043 op1 = gimple_assign_lhs (g);
4045 g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1);
4046 gimple_set_location (g, loc);
4047 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4048 if (utype != type)
4050 g = gimple_build_assign (make_ssa_name (type), NOP_EXPR,
4051 gimple_assign_lhs (g));
4052 gimple_set_location (g, loc);
4053 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4055 g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR,
4056 gimple_assign_lhs (g),
4057 build_int_cst (type, ovf));
4059 gimple_set_location (g, loc);
4060 gsi_replace (gsi, g, false);
4061 return true;
4064 /* Return true if VAR is a two-valued variable. Set a and b with the
4065 two-values when it is true. Return false otherwise. */
4067 bool
4068 vr_values::two_valued_val_range_p (tree var, tree *a, tree *b)
4070 value_range *vr = get_value_range (var);
4071 if ((vr->type != VR_RANGE
4072 && vr->type != VR_ANTI_RANGE)
4073 || TREE_CODE (vr->min) != INTEGER_CST
4074 || TREE_CODE (vr->max) != INTEGER_CST)
4075 return false;
4077 if (vr->type == VR_RANGE
4078 && wi::to_wide (vr->max) - wi::to_wide (vr->min) == 1)
4080 *a = vr->min;
4081 *b = vr->max;
4082 return true;
4085 /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
4086 if (vr->type == VR_ANTI_RANGE
4087 && (wi::to_wide (vr->min)
4088 - wi::to_wide (vrp_val_min (TREE_TYPE (var)))) == 1
4089 && (wi::to_wide (vrp_val_max (TREE_TYPE (var)))
4090 - wi::to_wide (vr->max)) == 1)
4092 *a = vrp_val_min (TREE_TYPE (var));
4093 *b = vrp_val_max (TREE_TYPE (var));
4094 return true;
4097 return false;
4100 /* Simplify STMT using ranges if possible. */
4102 bool
4103 vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
4105 gimple *stmt = gsi_stmt (*gsi);
4106 if (is_gimple_assign (stmt))
4108 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
4109 tree rhs1 = gimple_assign_rhs1 (stmt);
4110 tree rhs2 = gimple_assign_rhs2 (stmt);
4111 tree lhs = gimple_assign_lhs (stmt);
4112 tree val1 = NULL_TREE, val2 = NULL_TREE;
4113 use_operand_p use_p;
4114 gimple *use_stmt;
4116 /* Convert:
4117 LHS = CST BINOP VAR
4118 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4120 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4122 Also handles:
4123 LHS = VAR BINOP CST
4124 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4126 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4128 if (TREE_CODE_CLASS (rhs_code) == tcc_binary
4129 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
4130 && ((TREE_CODE (rhs1) == INTEGER_CST
4131 && TREE_CODE (rhs2) == SSA_NAME)
4132 || (TREE_CODE (rhs2) == INTEGER_CST
4133 && TREE_CODE (rhs1) == SSA_NAME))
4134 && single_imm_use (lhs, &use_p, &use_stmt)
4135 && gimple_code (use_stmt) == GIMPLE_COND)
4138 tree new_rhs1 = NULL_TREE;
4139 tree new_rhs2 = NULL_TREE;
4140 tree cmp_var = NULL_TREE;
4142 if (TREE_CODE (rhs2) == SSA_NAME
4143 && two_valued_val_range_p (rhs2, &val1, &val2))
4145 /* Optimize RHS1 OP [VAL1, VAL2]. */
4146 new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
4147 new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
4148 cmp_var = rhs2;
4150 else if (TREE_CODE (rhs1) == SSA_NAME
4151 && two_valued_val_range_p (rhs1, &val1, &val2))
4153 /* Optimize [VAL1, VAL2] OP RHS2. */
4154 new_rhs1 = int_const_binop (rhs_code, val1, rhs2);
4155 new_rhs2 = int_const_binop (rhs_code, val2, rhs2);
4156 cmp_var = rhs1;
4159 /* If we could not find two-vals or the optimzation is invalid as
4160 in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
4161 if (new_rhs1 && new_rhs2)
4163 tree cond = build2 (EQ_EXPR, boolean_type_node, cmp_var, val1);
4164 gimple_assign_set_rhs_with_ops (gsi,
4165 COND_EXPR, cond,
4166 new_rhs1,
4167 new_rhs2);
4168 update_stmt (gsi_stmt (*gsi));
4169 fold_stmt (gsi, follow_single_use_edges);
4170 return true;
4174 switch (rhs_code)
4176 case EQ_EXPR:
4177 case NE_EXPR:
4178 /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
4179 if the RHS is zero or one, and the LHS are known to be boolean
4180 values. */
4181 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4182 return simplify_truth_ops_using_ranges (gsi, stmt);
4183 break;
4185 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4186 and BIT_AND_EXPR respectively if the first operand is greater
4187 than zero and the second operand is an exact power of two.
4188 Also optimize TRUNC_MOD_EXPR away if the second operand is
4189 constant and the first operand already has the right value
4190 range. */
4191 case TRUNC_DIV_EXPR:
4192 case TRUNC_MOD_EXPR:
4193 if ((TREE_CODE (rhs1) == SSA_NAME
4194 || TREE_CODE (rhs1) == INTEGER_CST)
4195 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4196 return simplify_div_or_mod_using_ranges (gsi, stmt);
4197 break;
4199 /* Transform ABS (X) into X or -X as appropriate. */
4200 case ABS_EXPR:
4201 if (TREE_CODE (rhs1) == SSA_NAME
4202 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4203 return simplify_abs_using_ranges (gsi, stmt);
4204 break;
4206 case BIT_AND_EXPR:
4207 case BIT_IOR_EXPR:
4208 /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
4209 if all the bits being cleared are already cleared or
4210 all the bits being set are already set. */
4211 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4212 return simplify_bit_ops_using_ranges (gsi, stmt);
4213 break;
4215 CASE_CONVERT:
4216 if (TREE_CODE (rhs1) == SSA_NAME
4217 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4218 return simplify_conversion_using_ranges (gsi, stmt);
4219 break;
4221 case FLOAT_EXPR:
4222 if (TREE_CODE (rhs1) == SSA_NAME
4223 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
4224 return simplify_float_conversion_using_ranges (gsi, stmt);
4225 break;
4227 case MIN_EXPR:
4228 case MAX_EXPR:
4229 return simplify_min_or_max_using_ranges (gsi, stmt);
4231 default:
4232 break;
4235 else if (gimple_code (stmt) == GIMPLE_COND)
4236 return simplify_cond_using_ranges_1 (as_a <gcond *> (stmt));
4237 else if (gimple_code (stmt) == GIMPLE_SWITCH)
4238 return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
4239 else if (is_gimple_call (stmt)
4240 && gimple_call_internal_p (stmt))
4241 return simplify_internal_call_using_ranges (gsi, stmt);
4243 return false;
4246 void
4247 vr_values::set_vr_value (tree var, value_range *vr)
4249 if (SSA_NAME_VERSION (var) >= num_vr_values)
4250 return;
4251 vr_value[SSA_NAME_VERSION (var)] = vr;