1/* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
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"
50
51/* Set value range VR to a non-negative range of type TYPE. */
52
53static inline void
54set_value_range_to_nonnegative (value_range *vr, tree type)
55{
56 tree zero = build_int_cst (type, 0);
57 set_value_range (vr, VR_RANGE, zero, vrp_val_max (type), vr->equiv);
58}
59
60/* Set value range VR to a range of a truthvalue of type TYPE. */
61
62static inline void
63set_value_range_to_truthvalue (value_range *vr, tree type)
64{
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);
71}
72
73
74/* Return value range information for VAR.
75
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. */
78
79value_range *
80vr_values::get_value_range (const_tree var)
81{
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);
87
88 /* If we have no recorded ranges, then return NULL. */
89 if (! vr_value)
90 return NULL;
91
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);
97
98 vr = vr_value[ver];
99 if (vr)
100 return vr;
101
102 /* After propagation finished do not allocate new value-ranges. */
103 if (values_propagated)
104 return CONST_CAST (value_range *, &vr_const_varying);
105
106 /* Create a default value range. */
107 vr_value[ver] = vr = vrp_value_range_pool.allocate ();
108 memset (vr, 0, sizeof (*vr));
109
110 /* Defer allocating the equivalence set. */
111 vr->equiv = NULL;
112
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))
116 {
117 sym = SSA_NAME_VAR (var);
118 if (TREE_CODE (sym) == PARM_DECL)
119 {
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)))
128 {
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);
138 }
139 else
140 set_value_range_to_varying (vr);
141 }
142 else if (TREE_CODE (sym) == RESULT_DECL
143 && DECL_BY_REFERENCE (sym))
144 set_value_range_to_nonnull (vr, TREE_TYPE (sym));
145 }
146
147 return vr;
148}
149
150/* Set value-ranges of all SSA names defined by STMT to varying. */
151
152void
153vr_values::set_defs_to_varying (gimple *stmt)
154{
155 ssa_op_iter i;
156 tree def;
157 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
158 {
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);
163 }
164}
165
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.
169
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. */
175
176bool
177vr_values::update_value_range (const_tree var, value_range *new_vr)
178{
179 value_range *old_vr;
180 bool is_new;
181
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)))
185 {
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)
189 {
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);
196 }
197 }
198
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);
205
206 if (is_new)
207 {
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)
215 {
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;
220 }
221 else
222 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
223 new_vr->equiv);
224 }
225
226 BITMAP_FREE (new_vr->equiv);
227
228 return is_new;
229}
230
231
232/* Add VAR and VAR's equivalence set to EQUIV. This is the central
233 point where equivalence processing can be turned on/off. */
234
235void
236vr_values::add_equivalence (bitmap *equiv, const_tree var)
237{
238 unsigned ver = SSA_NAME_VERSION (var);
239 value_range *vr = get_value_range (var);
240
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);
246}
247
248/* Return true if value range VR involves exactly one symbol SYM. */
249
250static bool
251symbolic_range_based_on_p (value_range *vr, const_tree sym)
252{
253 bool neg, min_has_symbol, max_has_symbol;
254 tree inv;
255
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;
262
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;
269
270 return (min_has_symbol || max_has_symbol);
271}
272
273/* Return true if the result of assignment STMT is know to be non-zero. */
274
275static bool
276gimple_assign_nonzero_p (gimple *stmt)
277{
278 enum tree_code code = gimple_assign_rhs_code (stmt);
279 bool strict_overflow_p;
280 switch (get_gimple_rhs_class (code))
281 {
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 ();
302 }
303}
304
305/* Return true if STMT is known to compute a non-zero value. */
306
307static bool
308gimple_stmt_nonzero_p (gimple *stmt)
309{
310 switch (gimple_code (stmt))
311 {
312 case GIMPLE_ASSIGN:
313 return gimple_assign_nonzero_p (stmt);
314 case GIMPLE_CALL:
315 {
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;
330
331 gcall *call_stmt = as_a<gcall *> (stmt);
332 unsigned rf = gimple_call_return_flags (call_stmt);
333 if (rf & ERF_RETURNS_ARG)
334 {
335 unsigned argnum = rf & ERF_RETURN_ARG_MASK;
336 if (argnum < gimple_call_num_args (call_stmt))
337 {
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;
342 }
343 }
344 return gimple_alloca_call_p (stmt);
345 }
346 default:
347 gcc_unreachable ();
348 }
349}
350/* Like tree_expr_nonzero_p, but this function uses value ranges
351 obtained so far. */
352
353bool
354vr_values::vrp_stmt_computes_nonzero (gimple *stmt)
355{
356 if (gimple_stmt_nonzero_p (stmt))
357 return true;
358
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)
363 {
364 tree expr = gimple_assign_rhs1 (stmt);
365 tree base = get_base_address (TREE_OPERAND (expr, 0));
366
367 if (base != NULL_TREE
368 && TREE_CODE (base) == MEM_REF
369 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
370 {
371 value_range *vr = get_value_range (TREE_OPERAND (base, 0));
372 if (range_is_nonnull (vr))
373 return true;
374 }
375 }
376
377 return false;
378}
379
380/* Returns true if EXPR is a valid value (as expected by compare_values) --
381 a gimple invariant, or SSA_NAME +- CST. */
382
383static bool
384valid_value_p (tree expr)
385{
386 if (TREE_CODE (expr) == SSA_NAME)
387 return true;
388
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);
393
394 return is_gimple_min_invariant (expr);
395}
396
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. */
400
401tree
402vr_values::op_with_constant_singleton_value_range (tree op)
403{
404 if (is_gimple_min_invariant (op))
405 return op;
406
407 if (TREE_CODE (op) != SSA_NAME)
408 return NULL_TREE;
409
410 return value_range_constant_singleton (get_value_range (op));
411}
412
413/* Return true if op is in a boolean [0, 1] value-range. */
414
415bool
416vr_values::op_with_boolean_value_range_p (tree op)
417{
418 value_range *vr;
419
420 if (TYPE_PRECISION (TREE_TYPE (op)) == 1)
421 return true;
422
423 if (integer_zerop (op)
424 || integer_onep (op))
425 return true;
426
427 if (TREE_CODE (op) != SSA_NAME)
428 return false;
429
430 vr = get_value_range (op);
431 return (vr->type == VR_RANGE
432 && integer_zerop (vr->min)
433 && integer_onep (vr->max));
434}
435
436/* Extract value range information for VAR when (OP COND_CODE LIMIT) is
437 true and store it in *VR_P. */
438
439void
440vr_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)
444{
445 tree min, max, type;
446 value_range *limit_vr;
447 type = TREE_TYPE (var);
448 gcc_assert (limit != var);
449
450 /* For pointer arithmetic, we only keep track of pointer equality
451 and inequality. */
452 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
453 {
454 set_value_range_to_varying (vr_p);
455 return;
456 }
457
458 /* If LIMIT is another SSA name and LIMIT has a range of its own,
459 try to use LIMIT's range to avoid creating symbolic ranges
460 unnecessarily. */
461 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
462
463 /* LIMIT's range is only interesting if it has any useful information. */
464 if (! limit_vr
465 || limit_vr->type == VR_UNDEFINED
466 || limit_vr->type == VR_VARYING
467 || (symbolic_range_p (limit_vr)
468 && ! (limit_vr->type == VR_RANGE
469 && (limit_vr->min == limit_vr->max
470 || operand_equal_p (limit_vr->min, limit_vr->max, 0)))))
471 limit_vr = NULL;
472
473 /* Initially, the new range has the same set of equivalences of
474 VAR's range. This will be revised before returning the final
475 value. Since assertions may be chained via mutually exclusive
476 predicates, we will need to trim the set of equivalences before
477 we are done. */
478 gcc_assert (vr_p->equiv == NULL);
479 add_equivalence (&vr_p->equiv, var);
480
481 /* Extract a new range based on the asserted comparison for VAR and
482 LIMIT's value range. Notice that if LIMIT has an anti-range, we
483 will only use it for equality comparisons (EQ_EXPR). For any
484 other kind of assertion, we cannot derive a range from LIMIT's
485 anti-range that can be used to describe the new range. For
486 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
487 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
488 no single range for x_2 that could describe LE_EXPR, so we might
489 as well build the range [b_4, +INF] for it.
490 One special case we handle is extracting a range from a
491 range test encoded as (unsigned)var + CST <= limit. */
492 if (TREE_CODE (op) == NOP_EXPR
493 || TREE_CODE (op) == PLUS_EXPR)
494 {
495 if (TREE_CODE (op) == PLUS_EXPR)
496 {
497 min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)),
498 TREE_OPERAND (op, 1));
499 max = int_const_binop (PLUS_EXPR, limit, min);
500 op = TREE_OPERAND (op, 0);
501 }
502 else
503 {
504 min = build_int_cst (TREE_TYPE (var), 0);
505 max = limit;
506 }
507
508 /* Make sure to not set TREE_OVERFLOW on the final type
509 conversion. We are willingly interpreting large positive
510 unsigned values as negative signed values here. */
511 min = force_fit_type (TREE_TYPE (var), wi::to_widest (min), 0, false);
512 max = force_fit_type (TREE_TYPE (var), wi::to_widest (max), 0, false);
513
514 /* We can transform a max, min range to an anti-range or
515 vice-versa. Use set_and_canonicalize_value_range which does
516 this for us. */
517 if (cond_code == LE_EXPR)
518 set_and_canonicalize_value_range (vr_p, VR_RANGE,
519 min, max, vr_p->equiv);
520 else if (cond_code == GT_EXPR)
521 set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
522 min, max, vr_p->equiv);
523 else
524 gcc_unreachable ();
525 }
526 else if (cond_code == EQ_EXPR)
527 {
528 enum value_range_type range_type;
529
530 if (limit_vr)
531 {
532 range_type = limit_vr->type;
533 min = limit_vr->min;
534 max = limit_vr->max;
535 }
536 else
537 {
538 range_type = VR_RANGE;
539 min = limit;
540 max = limit;
541 }
542
543 set_value_range (vr_p, range_type, min, max, vr_p->equiv);
544
545 /* When asserting the equality VAR == LIMIT and LIMIT is another
546 SSA name, the new range will also inherit the equivalence set
547 from LIMIT. */
548 if (TREE_CODE (limit) == SSA_NAME)
549 add_equivalence (&vr_p->equiv, limit);
550 }
551 else if (cond_code == NE_EXPR)
552 {
553 /* As described above, when LIMIT's range is an anti-range and
554 this assertion is an inequality (NE_EXPR), then we cannot
555 derive anything from the anti-range. For instance, if
556 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
557 not imply that VAR's range is [0, 0]. So, in the case of
558 anti-ranges, we just assert the inequality using LIMIT and
559 not its anti-range.
560
561 If LIMIT_VR is a range, we can only use it to build a new
562 anti-range if LIMIT_VR is a single-valued range. For
563 instance, if LIMIT_VR is [0, 1], the predicate
564 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
565 Rather, it means that for value 0 VAR should be ~[0, 0]
566 and for value 1, VAR should be ~[1, 1]. We cannot
567 represent these ranges.
568
569 The only situation in which we can build a valid
570 anti-range is when LIMIT_VR is a single-valued range
571 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
572 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
573 if (limit_vr
574 && limit_vr->type == VR_RANGE
575 && compare_values (limit_vr->min, limit_vr->max) == 0)
576 {
577 min = limit_vr->min;
578 max = limit_vr->max;
579 }
580 else
581 {
582 /* In any other case, we cannot use LIMIT's range to build a
583 valid anti-range. */
584 min = max = limit;
585 }
586
587 /* If MIN and MAX cover the whole range for their type, then
588 just use the original LIMIT. */
589 if (INTEGRAL_TYPE_P (type)
590 && vrp_val_is_min (min)
591 && vrp_val_is_max (max))
592 min = max = limit;
593
594 set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
595 min, max, vr_p->equiv);
596 }
597 else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
598 {
599 min = TYPE_MIN_VALUE (type);
600
601 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
602 max = limit;
603 else
604 {
605 /* If LIMIT_VR is of the form [N1, N2], we need to build the
606 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
607 LT_EXPR. */
608 max = limit_vr->max;
609 }
610
611 /* If the maximum value forces us to be out of bounds, simply punt.
612 It would be pointless to try and do anything more since this
613 all should be optimized away above us. */
614 if (cond_code == LT_EXPR
615 && compare_values (max, min) == 0)
616 set_value_range_to_varying (vr_p);
617 else
618 {
619 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
620 if (cond_code == LT_EXPR)
621 {
622 if (TYPE_PRECISION (TREE_TYPE (max)) == 1
623 && !TYPE_UNSIGNED (TREE_TYPE (max)))
624 max = fold_build2 (PLUS_EXPR, TREE_TYPE (max), max,
625 build_int_cst (TREE_TYPE (max), -1));
626 else
627 max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max,
628 build_int_cst (TREE_TYPE (max), 1));
629 /* Signal to compare_values_warnv this expr doesn't overflow. */
630 if (EXPR_P (max))
631 TREE_NO_WARNING (max) = 1;
632 }
633
634 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
635 }
636 }
637 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
638 {
639 max = TYPE_MAX_VALUE (type);
640
641 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
642 min = limit;
643 else
644 {
645 /* If LIMIT_VR is of the form [N1, N2], we need to build the
646 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
647 GT_EXPR. */
648 min = limit_vr->min;
649 }
650
651 /* If the minimum value forces us to be out of bounds, simply punt.
652 It would be pointless to try and do anything more since this
653 all should be optimized away above us. */
654 if (cond_code == GT_EXPR
655 && compare_values (min, max) == 0)
656 set_value_range_to_varying (vr_p);
657 else
658 {
659 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
660 if (cond_code == GT_EXPR)
661 {
662 if (TYPE_PRECISION (TREE_TYPE (min)) == 1
663 && !TYPE_UNSIGNED (TREE_TYPE (min)))
664 min = fold_build2 (MINUS_EXPR, TREE_TYPE (min), min,
665 build_int_cst (TREE_TYPE (min), -1));
666 else
667 min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min,
668 build_int_cst (TREE_TYPE (min), 1));
669 /* Signal to compare_values_warnv this expr doesn't overflow. */
670 if (EXPR_P (min))
671 TREE_NO_WARNING (min) = 1;
672 }
673
674 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
675 }
676 }
677 else
678 gcc_unreachable ();
679
680 /* Finally intersect the new range with what we already know about var. */
681 vrp_intersect_ranges (vr_p, get_value_range (var));
682}
683
684/* Extract value range information from an ASSERT_EXPR EXPR and store
685 it in *VR_P. */
686
687void
688vr_values::extract_range_from_assert (value_range *vr_p, tree expr)
689{
690 tree var = ASSERT_EXPR_VAR (expr);
691 tree cond = ASSERT_EXPR_COND (expr);
692 tree limit, op;
693 enum tree_code cond_code;
694 gcc_assert (COMPARISON_CLASS_P (cond));
695
696 /* Find VAR in the ASSERT_EXPR conditional. */
697 if (var == TREE_OPERAND (cond, 0)
698 || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
699 || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
700 {
701 /* If the predicate is of the form VAR COMP LIMIT, then we just
702 take LIMIT from the RHS and use the same comparison code. */
703 cond_code = TREE_CODE (cond);
704 limit = TREE_OPERAND (cond, 1);
705 op = TREE_OPERAND (cond, 0);
706 }
707 else
708 {
709 /* If the predicate is of the form LIMIT COMP VAR, then we need
710 to flip around the comparison code to create the proper range
711 for VAR. */
712 cond_code = swap_tree_comparison (TREE_CODE (cond));
713 limit = TREE_OPERAND (cond, 0);
714 op = TREE_OPERAND (cond, 1);
715 }
716 extract_range_for_var_from_comparison_expr (var, cond_code, op,
717 limit, vr_p);
718}
719
720/* Extract range information from SSA name VAR and store it in VR. If
721 VAR has an interesting range, use it. Otherwise, create the
722 range [VAR, VAR] and return it. This is useful in situations where
723 we may have conditionals testing values of VARYING names. For
724 instance,
725
726 x_3 = y_5;
727 if (x_3 > y_5)
728 ...
729
730 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
731 always false. */
732
733void
734vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
735{
736 value_range *var_vr = get_value_range (var);
737
738 if (var_vr->type != VR_VARYING)
739 copy_value_range (vr, var_vr);
740 else
741 set_value_range (vr, VR_RANGE, var, var, NULL);
742
743 add_equivalence (&vr->equiv, var);
744}
745
746/* Extract range information from a binary expression OP0 CODE OP1 based on
747 the ranges of each of its operands with resulting type EXPR_TYPE.
748 The resulting range is stored in *VR. */
749
750void
751vr_values::extract_range_from_binary_expr (value_range *vr,
752 enum tree_code code,
753 tree expr_type, tree op0, tree op1)
754{
755 value_range vr0 = VR_INITIALIZER;
756 value_range vr1 = VR_INITIALIZER;
757
758 /* Get value ranges for each operand. For constant operands, create
759 a new value range with the operand to simplify processing. */
760 if (TREE_CODE (op0) == SSA_NAME)
761 vr0 = *(get_value_range (op0));
762 else if (is_gimple_min_invariant (op0))
763 set_value_range_to_value (&vr0, op0, NULL);
764 else
765 set_value_range_to_varying (&vr0);
766
767 if (TREE_CODE (op1) == SSA_NAME)
768 vr1 = *(get_value_range (op1));
769 else if (is_gimple_min_invariant (op1))
770 set_value_range_to_value (&vr1, op1, NULL);
771 else
772 set_value_range_to_varying (&vr1);
773
774 /* If one argument is varying, we can sometimes still deduce a
775 range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
776 if (INTEGRAL_TYPE_P (TREE_TYPE (op0))
777 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
778 {
779 if (vr0.type == VR_VARYING && vr1.type != VR_VARYING)
780 {
781 vr0.type = VR_RANGE;
782 vr0.min = vrp_val_min (expr_type);
783 vr0.max = vrp_val_max (expr_type);
784 }
785 else if (vr1.type == VR_VARYING && vr0.type != VR_VARYING)
786 {
787 vr1.type = VR_RANGE;
788 vr1.min = vrp_val_min (expr_type);
789 vr1.max = vrp_val_max (expr_type);
790 }
791 }
792
793 extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
794
795 /* Try harder for PLUS and MINUS if the range of one operand is symbolic
796 and based on the other operand, for example if it was deduced from a
797 symbolic comparison. When a bound of the range of the first operand
798 is invariant, we set the corresponding bound of the new range to INF
799 in order to avoid recursing on the range of the second operand. */
800 if (vr->type == VR_VARYING
801 && (code == PLUS_EXPR || code == MINUS_EXPR)
802 && TREE_CODE (op1) == SSA_NAME
803 && vr0.type == VR_RANGE
804 && symbolic_range_based_on_p (&vr0, op1))
805 {
806 const bool minus_p = (code == MINUS_EXPR);
807 value_range n_vr1 = VR_INITIALIZER;
808
809 /* Try with VR0 and [-INF, OP1]. */
810 if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min))
811 set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL);
812
813 /* Try with VR0 and [OP1, +INF]. */
814 else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max))
815 set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL);
816
817 /* Try with VR0 and [OP1, OP1]. */
818 else
819 set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL);
820
821 extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1);
822 }
823
824 if (vr->type == VR_VARYING
825 && (code == PLUS_EXPR || code == MINUS_EXPR)
826 && TREE_CODE (op0) == SSA_NAME
827 && vr1.type == VR_RANGE
828 && symbolic_range_based_on_p (&vr1, op0))
829 {
830 const bool minus_p = (code == MINUS_EXPR);
831 value_range n_vr0 = VR_INITIALIZER;
832
833 /* Try with [-INF, OP0] and VR1. */
834 if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min))
835 set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL);
836
837 /* Try with [OP0, +INF] and VR1. */
838 else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max))
839 set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL);
840
841 /* Try with [OP0, OP0] and VR1. */
842 else
843 set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL);
844
845 extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
846 }
847
848 /* If we didn't derive a range for MINUS_EXPR, and
849 op1's range is ~[op0,op0] or vice-versa, then we
850 can derive a non-null range. This happens often for
851 pointer subtraction. */
852 if (vr->type == VR_VARYING
853 && (code == MINUS_EXPR || code == POINTER_DIFF_EXPR)
854 && TREE_CODE (op0) == SSA_NAME
855 && ((vr0.type == VR_ANTI_RANGE
856 && vr0.min == op1
857 && vr0.min == vr0.max)
858 || (vr1.type == VR_ANTI_RANGE
859 && vr1.min == op0
860 && vr1.min == vr1.max)))
861 set_value_range_to_nonnull (vr, expr_type);
862}
863
864/* Extract range information from a unary expression CODE OP0 based on
865 the range of its operand with resulting type TYPE.
866 The resulting range is stored in *VR. */
867
868void
869vr_values::extract_range_from_unary_expr (value_range *vr, enum tree_code code,
870 tree type, tree op0)
871{
872 value_range vr0 = VR_INITIALIZER;
873
874 /* Get value ranges for the operand. For constant operands, create
875 a new value range with the operand to simplify processing. */
876 if (TREE_CODE (op0) == SSA_NAME)
877 vr0 = *(get_value_range (op0));
878 else if (is_gimple_min_invariant (op0))
879 set_value_range_to_value (&vr0, op0, NULL);
880 else
881 set_value_range_to_varying (&vr0);
882
883 ::extract_range_from_unary_expr (vr, code, type, &vr0, TREE_TYPE (op0));
884}
885
886
887/* Extract range information from a conditional expression STMT based on
888 the ranges of each of its operands and the expression code. */
889
890void
891vr_values::extract_range_from_cond_expr (value_range *vr, gassign *stmt)
892{
893 tree op0, op1;
894 value_range vr0 = VR_INITIALIZER;
895 value_range vr1 = VR_INITIALIZER;
896
897 /* Get value ranges for each operand. For constant operands, create
898 a new value range with the operand to simplify processing. */
899 op0 = gimple_assign_rhs2 (stmt);
900 if (TREE_CODE (op0) == SSA_NAME)
901 vr0 = *(get_value_range (op0));
902 else if (is_gimple_min_invariant (op0))
903 set_value_range_to_value (&vr0, op0, NULL);
904 else
905 set_value_range_to_varying (&vr0);
906
907 op1 = gimple_assign_rhs3 (stmt);
908 if (TREE_CODE (op1) == SSA_NAME)
909 vr1 = *(get_value_range (op1));
910 else if (is_gimple_min_invariant (op1))
911 set_value_range_to_value (&vr1, op1, NULL);
912 else
913 set_value_range_to_varying (&vr1);
914
915 /* The resulting value range is the union of the operand ranges */
916 copy_value_range (vr, &vr0);
917 vrp_meet (vr, &vr1);
918}
919
920
921/* Extract range information from a comparison expression EXPR based
922 on the range of its operand and the expression code. */
923
924void
925vr_values::extract_range_from_comparison (value_range *vr, enum tree_code code,
926 tree type, tree op0, tree op1)
927{
928 bool sop;
929 tree val;
930
931 val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
932 NULL);
933 if (val)
934 {
935 /* Since this expression was found on the RHS of an assignment,
936 its type may be different from _Bool. Convert VAL to EXPR's
937 type. */
938 val = fold_convert (type, val);
939 if (is_gimple_min_invariant (val))
940 set_value_range_to_value (vr, val, vr->equiv);
941 else
942 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
943 }
944 else
945 /* The result of a comparison is always true or false. */
946 set_value_range_to_truthvalue (vr, type);
947}
948
949/* Helper function for simplify_internal_call_using_ranges and
950 extract_range_basic. Return true if OP0 SUBCODE OP1 for
951 SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
952 always overflow. Set *OVF to true if it is known to always
953 overflow. */
954
955bool
956vr_values::check_for_binary_op_overflow (enum tree_code subcode, tree type,
957 tree op0, tree op1, bool *ovf)
958{
959 value_range vr0 = VR_INITIALIZER;
960 value_range vr1 = VR_INITIALIZER;
961 if (TREE_CODE (op0) == SSA_NAME)
962 vr0 = *get_value_range (op0);
963 else if (TREE_CODE (op0) == INTEGER_CST)
964 set_value_range_to_value (&vr0, op0, NULL);
965 else
966 set_value_range_to_varying (&vr0);
967
968 if (TREE_CODE (op1) == SSA_NAME)
969 vr1 = *get_value_range (op1);
970 else if (TREE_CODE (op1) == INTEGER_CST)
971 set_value_range_to_value (&vr1, op1, NULL);
972 else
973 set_value_range_to_varying (&vr1);
974
975 if (!range_int_cst_p (&vr0)
976 || TREE_OVERFLOW (vr0.min)
977 || TREE_OVERFLOW (vr0.max))
978 {
979 vr0.min = vrp_val_min (TREE_TYPE (op0));
980 vr0.max = vrp_val_max (TREE_TYPE (op0));
981 }
982 if (!range_int_cst_p (&vr1)
983 || TREE_OVERFLOW (vr1.min)
984 || TREE_OVERFLOW (vr1.max))
985 {
986 vr1.min = vrp_val_min (TREE_TYPE (op1));
987 vr1.max = vrp_val_max (TREE_TYPE (op1));
988 }
989 *ovf = arith_overflowed_p (subcode, type, vr0.min,
990 subcode == MINUS_EXPR ? vr1.max : vr1.min);
991 if (arith_overflowed_p (subcode, type, vr0.max,
992 subcode == MINUS_EXPR ? vr1.min : vr1.max) != *ovf)
993 return false;
994 if (subcode == MULT_EXPR)
995 {
996 if (arith_overflowed_p (subcode, type, vr0.min, vr1.max) != *ovf
997 || arith_overflowed_p (subcode, type, vr0.max, vr1.min) != *ovf)
998 return false;
999 }
1000 if (*ovf)
1001 {
1002 /* So far we found that there is an overflow on the boundaries.
1003 That doesn't prove that there is an overflow even for all values
1004 in between the boundaries. For that compute widest_int range
1005 of the result and see if it doesn't overlap the range of
1006 type. */
1007 widest_int wmin, wmax;
1008 widest_int w[4];
1009 int i;
1010 w[0] = wi::to_widest (vr0.min);
1011 w[1] = wi::to_widest (vr0.max);
1012 w[2] = wi::to_widest (vr1.min);
1013 w[3] = wi::to_widest (vr1.max);
1014 for (i = 0; i < 4; i++)
1015 {
1016 widest_int wt;
1017 switch (subcode)
1018 {
1019 case PLUS_EXPR:
1020 wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]);
1021 break;
1022 case MINUS_EXPR:
1023 wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]);
1024 break;
1025 case MULT_EXPR:
1026 wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]);
1027 break;
1028 default:
1029 gcc_unreachable ();
1030 }
1031 if (i == 0)
1032 {
1033 wmin = wt;
1034 wmax = wt;
1035 }
1036 else
1037 {
1038 wmin = wi::smin (wmin, wt);
1039 wmax = wi::smax (wmax, wt);
1040 }
1041 }
1042 /* The result of op0 CODE op1 is known to be in range
1043 [wmin, wmax]. */
1044 widest_int wtmin = wi::to_widest (vrp_val_min (type));
1045 widest_int wtmax = wi::to_widest (vrp_val_max (type));
1046 /* If all values in [wmin, wmax] are smaller than
1047 [wtmin, wtmax] or all are larger than [wtmin, wtmax],
1048 the arithmetic operation will always overflow. */
1049 if (wmax < wtmin || wmin > wtmax)
1050 return true;
1051 return false;
1052 }
1053 return true;
1054}
1055
1056/* Try to derive a nonnegative or nonzero range out of STMT relying
1057 primarily on generic routines in fold in conjunction with range data.
1058 Store the result in *VR */
1059
1060void
1061vr_values::extract_range_basic (value_range *vr, gimple *stmt)
1062{
1063 bool sop;
1064 tree type = gimple_expr_type (stmt);
1065
1066 if (is_gimple_call (stmt))
1067 {
1068 tree arg;
1069 int mini, maxi, zerov = 0, prec;
1070 enum tree_code subcode = ERROR_MARK;
1071 combined_fn cfn = gimple_call_combined_fn (stmt);
1072 scalar_int_mode mode;
1073
1074 switch (cfn)
1075 {
1076 case CFN_BUILT_IN_CONSTANT_P:
1077 /* If the call is __builtin_constant_p and the argument is a
1078 function parameter resolve it to false. This avoids bogus
1079 array bound warnings.
1080 ??? We could do this as early as inlining is finished. */
1081 arg = gimple_call_arg (stmt, 0);
1082 if (TREE_CODE (arg) == SSA_NAME
1083 && SSA_NAME_IS_DEFAULT_DEF (arg)
1084 && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL
1085 && cfun->after_inlining)
1086 {
1087 set_value_range_to_null (vr, type);
1088 return;
1089 }
1090 break;
1091 /* Both __builtin_ffs* and __builtin_popcount return
1092 [0, prec]. */
1093 CASE_CFN_FFS:
1094 CASE_CFN_POPCOUNT:
1095 arg = gimple_call_arg (stmt, 0);
1096 prec = TYPE_PRECISION (TREE_TYPE (arg));
1097 mini = 0;
1098 maxi = prec;
1099 if (TREE_CODE (arg) == SSA_NAME)
1100 {
1101 value_range *vr0 = get_value_range (arg);
1102 /* If arg is non-zero, then ffs or popcount
1103 are non-zero. */
1104 if ((vr0->type == VR_RANGE
1105 && range_includes_zero_p (vr0->min, vr0->max) == 0)
1106 || (vr0->type == VR_ANTI_RANGE
1107 && range_includes_zero_p (vr0->min, vr0->max) == 1))
1108 mini = 1;
1109 /* If some high bits are known to be zero,
1110 we can decrease the maximum. */
1111 if (vr0->type == VR_RANGE
1112 && TREE_CODE (vr0->max) == INTEGER_CST
1113 && !operand_less_p (vr0->min,
1114 build_zero_cst (TREE_TYPE (vr0->min))))
1115 maxi = tree_floor_log2 (vr0->max) + 1;
1116 }
1117 goto bitop_builtin;
1118 /* __builtin_parity* returns [0, 1]. */
1119 CASE_CFN_PARITY:
1120 mini = 0;
1121 maxi = 1;
1122 goto bitop_builtin;
1123 /* __builtin_c[lt]z* return [0, prec-1], except for
1124 when the argument is 0, but that is undefined behavior.
1125 On many targets where the CLZ RTL or optab value is defined
1126 for 0 the value is prec, so include that in the range
1127 by default. */
1128 CASE_CFN_CLZ:
1129 arg = gimple_call_arg (stmt, 0);
1130 prec = TYPE_PRECISION (TREE_TYPE (arg));
1131 mini = 0;
1132 maxi = prec;
1133 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
1134 if (optab_handler (clz_optab, mode) != CODE_FOR_nothing
1135 && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov)
1136 /* Handle only the single common value. */
1137 && zerov != prec)
1138 /* Magic value to give up, unless vr0 proves
1139 arg is non-zero. */
1140 mini = -2;
1141 if (TREE_CODE (arg) == SSA_NAME)
1142 {
1143 value_range *vr0 = get_value_range (arg);
1144 /* From clz of VR_RANGE minimum we can compute
1145 result maximum. */
1146 if (vr0->type == VR_RANGE
1147 && TREE_CODE (vr0->min) == INTEGER_CST)
1148 {
1149 maxi = prec - 1 - tree_floor_log2 (vr0->min);
1150 if (maxi != prec)
1151 mini = 0;
1152 }
1153 else if (vr0->type == VR_ANTI_RANGE
1154 && integer_zerop (vr0->min))
1155 {
1156 maxi = prec - 1;
1157 mini = 0;
1158 }
1159 if (mini == -2)
1160 break;
1161 /* From clz of VR_RANGE maximum we can compute
1162 result minimum. */
1163 if (vr0->type == VR_RANGE
1164 && TREE_CODE (vr0->max) == INTEGER_CST)
1165 {
1166 mini = prec - 1 - tree_floor_log2 (vr0->max);
1167 if (mini == prec)
1168 break;
1169 }
1170 }
1171 if (mini == -2)
1172 break;
1173 goto bitop_builtin;
1174 /* __builtin_ctz* return [0, prec-1], except for
1175 when the argument is 0, but that is undefined behavior.
1176 If there is a ctz optab for this mode and
1177 CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
1178 otherwise just assume 0 won't be seen. */
1179 CASE_CFN_CTZ:
1180 arg = gimple_call_arg (stmt, 0);
1181 prec = TYPE_PRECISION (TREE_TYPE (arg));
1182 mini = 0;
1183 maxi = prec - 1;
1184 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
1185 if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing
1186 && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov))
1187 {
1188 /* Handle only the two common values. */
1189 if (zerov == -1)
1190 mini = -1;
1191 else if (zerov == prec)
1192 maxi = prec;
1193 else
1194 /* Magic value to give up, unless vr0 proves
1195 arg is non-zero. */
1196 mini = -2;
1197 }
1198 if (TREE_CODE (arg) == SSA_NAME)
1199 {
1200 value_range *vr0 = get_value_range (arg);
1201 /* If arg is non-zero, then use [0, prec - 1]. */
1202 if ((vr0->type == VR_RANGE
1203 && integer_nonzerop (vr0->min))
1204 || (vr0->type == VR_ANTI_RANGE
1205 && integer_zerop (vr0->min)))
1206 {
1207 mini = 0;
1208 maxi = prec - 1;
1209 }
1210 /* If some high bits are known to be zero,
1211 we can decrease the result maximum. */
1212 if (vr0->type == VR_RANGE
1213 && TREE_CODE (vr0->max) == INTEGER_CST)
1214 {
1215 maxi = tree_floor_log2 (vr0->max);
1216 /* For vr0 [0, 0] give up. */
1217 if (maxi == -1)
1218 break;
1219 }
1220 }
1221 if (mini == -2)
1222 break;
1223 goto bitop_builtin;
1224 /* __builtin_clrsb* returns [0, prec-1]. */
1225 CASE_CFN_CLRSB:
1226 arg = gimple_call_arg (stmt, 0);
1227 prec = TYPE_PRECISION (TREE_TYPE (arg));
1228 mini = 0;
1229 maxi = prec - 1;
1230 goto bitop_builtin;
1231 bitop_builtin:
1232 set_value_range (vr, VR_RANGE, build_int_cst (type, mini),
1233 build_int_cst (type, maxi), NULL);
1234 return;
1235 case CFN_UBSAN_CHECK_ADD:
1236 subcode = PLUS_EXPR;
1237 break;
1238 case CFN_UBSAN_CHECK_SUB:
1239 subcode = MINUS_EXPR;
1240 break;
1241 case CFN_UBSAN_CHECK_MUL:
1242 subcode = MULT_EXPR;
1243 break;
1244 case CFN_GOACC_DIM_SIZE:
1245 case CFN_GOACC_DIM_POS:
1246 /* Optimizing these two internal functions helps the loop
1247 optimizer eliminate outer comparisons. Size is [1,N]
1248 and pos is [0,N-1]. */
1249 {
1250 bool is_pos = cfn == CFN_GOACC_DIM_POS;
1251 int axis = oacc_get_ifn_dim_arg (stmt);
1252 int size = oacc_get_fn_dim_size (current_function_decl, axis);
1253
1254 if (!size)
1255 /* If it's dynamic, the backend might know a hardware
1256 limitation. */
1257 size = targetm.goacc.dim_limit (axis);
1258
1259 tree type = TREE_TYPE (gimple_call_lhs (stmt));
1260 set_value_range (vr, VR_RANGE,
1261 build_int_cst (type, is_pos ? 0 : 1),
1262 size ? build_int_cst (type, size - is_pos)
1263 : vrp_val_max (type), NULL);
1264 }
1265 return;
1266 case CFN_BUILT_IN_STRLEN:
1267 if (tree lhs = gimple_call_lhs (stmt))
1268 if (ptrdiff_type_node
1269 && (TYPE_PRECISION (ptrdiff_type_node)
1270 == TYPE_PRECISION (TREE_TYPE (lhs))))
1271 {
1272 tree type = TREE_TYPE (lhs);
1273 tree max = vrp_val_max (ptrdiff_type_node);
1274 wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
1275 tree range_min = build_zero_cst (type);
1276 tree range_max = wide_int_to_tree (type, wmax - 1);
1277 set_value_range (vr, VR_RANGE, range_min, range_max, NULL);
1278 return;
1279 }
1280 break;
1281 default:
1282 break;
1283 }
1284 if (subcode != ERROR_MARK)
1285 {
1286 bool saved_flag_wrapv = flag_wrapv;
1287 /* Pretend the arithmetics is wrapping. If there is
1288 any overflow, we'll complain, but will actually do
1289 wrapping operation. */
1290 flag_wrapv = 1;
1291 extract_range_from_binary_expr (vr, subcode, type,
1292 gimple_call_arg (stmt, 0),
1293 gimple_call_arg (stmt, 1));
1294 flag_wrapv = saved_flag_wrapv;
1295
1296 /* If for both arguments vrp_valueize returned non-NULL,
1297 this should have been already folded and if not, it
1298 wasn't folded because of overflow. Avoid removing the
1299 UBSAN_CHECK_* calls in that case. */
1300 if (vr->type == VR_RANGE
1301 && (vr->min == vr->max
1302 || operand_equal_p (vr->min, vr->max, 0)))
1303 set_value_range_to_varying (vr);
1304 return;
1305 }
1306 }
1307 /* Handle extraction of the two results (result of arithmetics and
1308 a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW
1309 internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */
1310 else if (is_gimple_assign (stmt)
1311 && (gimple_assign_rhs_code (stmt) == REALPART_EXPR
1312 || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR)
1313 && INTEGRAL_TYPE_P (type))
1314 {
1315 enum tree_code code = gimple_assign_rhs_code (stmt);
1316 tree op = gimple_assign_rhs1 (stmt);
1317 if (TREE_CODE (op) == code && TREE_CODE (TREE_OPERAND (op, 0)) == SSA_NAME)
1318 {
1319 gimple *g = SSA_NAME_DEF_STMT (TREE_OPERAND (op, 0));
1320 if (is_gimple_call (g) && gimple_call_internal_p (g))
1321 {
1322 enum tree_code subcode = ERROR_MARK;
1323 switch (gimple_call_internal_fn (g))
1324 {
1325 case IFN_ADD_OVERFLOW:
1326 subcode = PLUS_EXPR;
1327 break;
1328 case IFN_SUB_OVERFLOW:
1329 subcode = MINUS_EXPR;
1330 break;
1331 case IFN_MUL_OVERFLOW:
1332 subcode = MULT_EXPR;
1333 break;
1334 case IFN_ATOMIC_COMPARE_EXCHANGE:
1335 if (code == IMAGPART_EXPR)
1336 {
1337 /* This is the boolean return value whether compare and
1338 exchange changed anything or not. */
1339 set_value_range (vr, VR_RANGE, build_int_cst (type, 0),
1340 build_int_cst (type, 1), NULL);
1341 return;
1342 }
1343 break;
1344 default:
1345 break;
1346 }
1347 if (subcode != ERROR_MARK)
1348 {
1349 tree op0 = gimple_call_arg (g, 0);
1350 tree op1 = gimple_call_arg (g, 1);
1351 if (code == IMAGPART_EXPR)
1352 {
1353 bool ovf = false;
1354 if (check_for_binary_op_overflow (subcode, type,
1355 op0, op1, &ovf))
1356 set_value_range_to_value (vr,
1357 build_int_cst (type, ovf),
1358 NULL);
1359 else if (TYPE_PRECISION (type) == 1
1360 && !TYPE_UNSIGNED (type))
1361 set_value_range_to_varying (vr);
1362 else
1363 set_value_range (vr, VR_RANGE, build_int_cst (type, 0),
1364 build_int_cst (type, 1), NULL);
1365 }
1366 else if (types_compatible_p (type, TREE_TYPE (op0))
1367 && types_compatible_p (type, TREE_TYPE (op1)))
1368 {
1369 bool saved_flag_wrapv = flag_wrapv;
1370 /* Pretend the arithmetics is wrapping. If there is
1371 any overflow, IMAGPART_EXPR will be set. */
1372 flag_wrapv = 1;
1373 extract_range_from_binary_expr (vr, subcode, type,
1374 op0, op1);
1375 flag_wrapv = saved_flag_wrapv;
1376 }
1377 else
1378 {
1379 value_range vr0 = VR_INITIALIZER;
1380 value_range vr1 = VR_INITIALIZER;
1381 bool saved_flag_wrapv = flag_wrapv;
1382 /* Pretend the arithmetics is wrapping. If there is
1383 any overflow, IMAGPART_EXPR will be set. */
1384 flag_wrapv = 1;
1385 extract_range_from_unary_expr (&vr0, NOP_EXPR,
1386 type, op0);
1387 extract_range_from_unary_expr (&vr1, NOP_EXPR,
1388 type, op1);
1389 extract_range_from_binary_expr_1 (vr, subcode, type,
1390 &vr0, &vr1);
1391 flag_wrapv = saved_flag_wrapv;
1392 }
1393 return;
1394 }
1395 }
1396 }
1397 }
1398 if (INTEGRAL_TYPE_P (type)
1399 && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
1400 set_value_range_to_nonnegative (vr, type);
1401 else if (vrp_stmt_computes_nonzero (stmt))
1402 set_value_range_to_nonnull (vr, type);
1403 else
1404 set_value_range_to_varying (vr);
1405}
1406
1407
1408/* Try to compute a useful range out of assignment STMT and store it
1409 in *VR. */
1410
1411void
1412vr_values::extract_range_from_assignment (value_range *vr, gassign *stmt)
1413{
1414 enum tree_code code = gimple_assign_rhs_code (stmt);
1415
1416 if (code == ASSERT_EXPR)
1417 extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
1418 else if (code == SSA_NAME)
1419 extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
1420 else if (TREE_CODE_CLASS (code) == tcc_binary)
1421 extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
1422 gimple_expr_type (stmt),
1423 gimple_assign_rhs1 (stmt),
1424 gimple_assign_rhs2 (stmt));
1425 else if (TREE_CODE_CLASS (code) == tcc_unary)
1426 extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
1427 gimple_expr_type (stmt),
1428 gimple_assign_rhs1 (stmt));
1429 else if (code == COND_EXPR)
1430 extract_range_from_cond_expr (vr, stmt);
1431 else if (TREE_CODE_CLASS (code) == tcc_comparison)
1432 extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
1433 gimple_expr_type (stmt),
1434 gimple_assign_rhs1 (stmt),
1435 gimple_assign_rhs2 (stmt));
1436 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
1437 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1438 set_value_range_to_value (vr, gimple_assign_rhs1 (stmt), NULL);
1439 else
1440 set_value_range_to_varying (vr);
1441
1442 if (vr->type == VR_VARYING)
1443 extract_range_basic (vr, stmt);
1444}
1445
1446/* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1447
1448 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1449 all the values in the ranges.
1450
1451 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1452
1453 - Return NULL_TREE if it is not always possible to determine the
1454 value of the comparison.
1455
1456 Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1457 assumed signed overflow is undefined. */
1458
1459
1460static tree
1461compare_ranges (enum tree_code comp, value_range *vr0, value_range *vr1,
1462 bool *strict_overflow_p)
1463{
1464 /* VARYING or UNDEFINED ranges cannot be compared. */
1465 if (vr0->type == VR_VARYING
1466 || vr0->type == VR_UNDEFINED
1467 || vr1->type == VR_VARYING
1468 || vr1->type == VR_UNDEFINED)
1469 return NULL_TREE;
1470
1471 /* Anti-ranges need to be handled separately. */
1472 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
1473 {
1474 /* If both are anti-ranges, then we cannot compute any
1475 comparison. */
1476 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
1477 return NULL_TREE;
1478
1479 /* These comparisons are never statically computable. */
1480 if (comp == GT_EXPR
1481 || comp == GE_EXPR
1482 || comp == LT_EXPR
1483 || comp == LE_EXPR)
1484 return NULL_TREE;
1485
1486 /* Equality can be computed only between a range and an
1487 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1488 if (vr0->type == VR_RANGE)
1489 {
1490 /* To simplify processing, make VR0 the anti-range. */
1491 value_range *tmp = vr0;
1492 vr0 = vr1;
1493 vr1 = tmp;
1494 }
1495
1496 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
1497
1498 if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
1499 && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
1500 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1501
1502 return NULL_TREE;
1503 }
1504
1505 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1506 operands around and change the comparison code. */
1507 if (comp == GT_EXPR || comp == GE_EXPR)
1508 {
1509 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
1510 std::swap (vr0, vr1);
1511 }
1512
1513 if (comp == EQ_EXPR)
1514 {
1515 /* Equality may only be computed if both ranges represent
1516 exactly one value. */
1517 if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
1518 && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
1519 {
1520 int cmp_min = compare_values_warnv (vr0->min, vr1->min,
1521 strict_overflow_p);
1522 int cmp_max = compare_values_warnv (vr0->max, vr1->max,
1523 strict_overflow_p);
1524 if (cmp_min == 0 && cmp_max == 0)
1525 return boolean_true_node;
1526 else if (cmp_min != -2 && cmp_max != -2)
1527 return boolean_false_node;
1528 }
1529 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
1530 else if (compare_values_warnv (vr0->min, vr1->max,
1531 strict_overflow_p) == 1
1532 || compare_values_warnv (vr1->min, vr0->max,
1533 strict_overflow_p) == 1)
1534 return boolean_false_node;
1535
1536 return NULL_TREE;
1537 }
1538 else if (comp == NE_EXPR)
1539 {
1540 int cmp1, cmp2;
1541
1542 /* If VR0 is completely to the left or completely to the right
1543 of VR1, they are always different. Notice that we need to
1544 make sure that both comparisons yield similar results to
1545 avoid comparing values that cannot be compared at
1546 compile-time. */
1547 cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
1548 cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
1549 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1550 return boolean_true_node;
1551
1552 /* If VR0 and VR1 represent a single value and are identical,
1553 return false. */
1554 else if (compare_values_warnv (vr0->min, vr0->max,
1555 strict_overflow_p) == 0
1556 && compare_values_warnv (vr1->min, vr1->max,
1557 strict_overflow_p) == 0
1558 && compare_values_warnv (vr0->min, vr1->min,
1559 strict_overflow_p) == 0
1560 && compare_values_warnv (vr0->max, vr1->max,
1561 strict_overflow_p) == 0)
1562 return boolean_false_node;
1563
1564 /* Otherwise, they may or may not be different. */
1565 else
1566 return NULL_TREE;
1567 }
1568 else if (comp == LT_EXPR || comp == LE_EXPR)
1569 {
1570 int tst;
1571
1572 /* If VR0 is to the left of VR1, return true. */
1573 tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
1574 if ((comp == LT_EXPR && tst == -1)
1575 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1576 return boolean_true_node;
1577
1578 /* If VR0 is to the right of VR1, return false. */
1579 tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
1580 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1581 || (comp == LE_EXPR && tst == 1))
1582 return boolean_false_node;
1583
1584 /* Otherwise, we don't know. */
1585 return NULL_TREE;
1586 }
1587
1588 gcc_unreachable ();
1589}
1590
1591/* Given a value range VR, a value VAL and a comparison code COMP, return
1592 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1593 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1594 always returns false. Return NULL_TREE if it is not always
1595 possible to determine the value of the comparison. Also set
1596 *STRICT_OVERFLOW_P to indicate whether comparision evaluation
1597 assumed signed overflow is undefined. */
1598
1599static tree
1600compare_range_with_value (enum tree_code comp, value_range *vr, tree val,
1601 bool *strict_overflow_p)
1602{
1603 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1604 return NULL_TREE;
1605
1606 /* Anti-ranges need to be handled separately. */
1607 if (vr->type == VR_ANTI_RANGE)
1608 {
1609 /* For anti-ranges, the only predicates that we can compute at
1610 compile time are equality and inequality. */
1611 if (comp == GT_EXPR
1612 || comp == GE_EXPR
1613 || comp == LT_EXPR
1614 || comp == LE_EXPR)
1615 return NULL_TREE;
1616
1617 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
1618 if (value_inside_range (val, vr->min, vr->max) == 1)
1619 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1620
1621 return NULL_TREE;
1622 }
1623
1624 if (comp == EQ_EXPR)
1625 {
1626 /* EQ_EXPR may only be computed if VR represents exactly
1627 one value. */
1628 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0)
1629 {
1630 int cmp = compare_values_warnv (vr->min, val, strict_overflow_p);
1631 if (cmp == 0)
1632 return boolean_true_node;
1633 else if (cmp == -1 || cmp == 1 || cmp == 2)
1634 return boolean_false_node;
1635 }
1636 else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1
1637 || compare_values_warnv (vr->max, val, strict_overflow_p) == -1)
1638 return boolean_false_node;
1639
1640 return NULL_TREE;
1641 }
1642 else if (comp == NE_EXPR)
1643 {
1644 /* If VAL is not inside VR, then they are always different. */
1645 if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1
1646 || compare_values_warnv (vr->min, val, strict_overflow_p) == 1)
1647 return boolean_true_node;
1648
1649 /* If VR represents exactly one value equal to VAL, then return
1650 false. */
1651 if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0
1652 && compare_values_warnv (vr->min, val, strict_overflow_p) == 0)
1653 return boolean_false_node;
1654
1655 /* Otherwise, they may or may not be different. */
1656 return NULL_TREE;
1657 }
1658 else if (comp == LT_EXPR || comp == LE_EXPR)
1659 {
1660 int tst;
1661
1662 /* If VR is to the left of VAL, return true. */
1663 tst = compare_values_warnv (vr->max, val, strict_overflow_p);
1664 if ((comp == LT_EXPR && tst == -1)
1665 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1666 return boolean_true_node;
1667
1668 /* If VR is to the right of VAL, return false. */
1669 tst = compare_values_warnv (vr->min, val, strict_overflow_p);
1670 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1671 || (comp == LE_EXPR && tst == 1))
1672 return boolean_false_node;
1673
1674 /* Otherwise, we don't know. */
1675 return NULL_TREE;
1676 }
1677 else if (comp == GT_EXPR || comp == GE_EXPR)
1678 {
1679 int tst;
1680
1681 /* If VR is to the right of VAL, return true. */
1682 tst = compare_values_warnv (vr->min, val, strict_overflow_p);
1683 if ((comp == GT_EXPR && tst == 1)
1684 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1685 return boolean_true_node;
1686
1687 /* If VR is to the left of VAL, return false. */
1688 tst = compare_values_warnv (vr->max, val, strict_overflow_p);
1689 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1690 || (comp == GE_EXPR && tst == -1))
1691 return boolean_false_node;
1692
1693 /* Otherwise, we don't know. */
1694 return NULL_TREE;
1695 }
1696
1697 gcc_unreachable ();
1698}
1699/* Given a range VR, a LOOP and a variable VAR, determine whether it
1700 would be profitable to adjust VR using scalar evolution information
1701 for VAR. If so, update VR with the new limits. */
1702
1703void
1704vr_values::adjust_range_with_scev (value_range *vr, struct loop *loop,
1705 gimple *stmt, tree var)
1706{
1707 tree init, step, chrec, tmin, tmax, min, max, type, tem;
1708 enum ev_direction dir;
1709
1710 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1711 better opportunities than a regular range, but I'm not sure. */
1712 if (vr->type == VR_ANTI_RANGE)
1713 return;
1714
1715 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
1716
1717 /* Like in PR19590, scev can return a constant function. */
1718 if (is_gimple_min_invariant (chrec))
1719 {
1720 set_value_range_to_value (vr, chrec, vr->equiv);
1721 return;
1722 }
1723
1724 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1725 return;
1726
1727 init = initial_condition_in_loop_num (chrec, loop->num);
1728 tem = op_with_constant_singleton_value_range (init);
1729 if (tem)
1730 init = tem;
1731 step = evolution_part_in_loop_num (chrec, loop->num);
1732 tem = op_with_constant_singleton_value_range (step);
1733 if (tem)
1734 step = tem;
1735
1736 /* If STEP is symbolic, we can't know whether INIT will be the
1737 minimum or maximum value in the range. Also, unless INIT is
1738 a simple expression, compare_values and possibly other functions
1739 in tree-vrp won't be able to handle it. */
1740 if (step == NULL_TREE
1741 || !is_gimple_min_invariant (step)
1742 || !valid_value_p (init))
1743 return;
1744
1745 dir = scev_direction (chrec);
1746 if (/* Do not adjust ranges if we do not know whether the iv increases
1747 or decreases, ... */
1748 dir == EV_DIR_UNKNOWN
1749 /* ... or if it may wrap. */
1750 || scev_probably_wraps_p (NULL_TREE, init, step, stmt,
1751 get_chrec_loop (chrec), true))
1752 return;
1753
1754 type = TREE_TYPE (var);
1755 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1756 tmin = lower_bound_in_type (type, type);
1757 else
1758 tmin = TYPE_MIN_VALUE (type);
1759 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1760 tmax = upper_bound_in_type (type, type);
1761 else
1762 tmax = TYPE_MAX_VALUE (type);
1763
1764 /* Try to use estimated number of iterations for the loop to constrain the
1765 final value in the evolution. */
1766 if (TREE_CODE (step) == INTEGER_CST
1767 && is_gimple_val (init)
1768 && (TREE_CODE (init) != SSA_NAME
1769 || get_value_range (init)->type == VR_RANGE))
1770 {
1771 widest_int nit;
1772
1773 /* We are only entering here for loop header PHI nodes, so using
1774 the number of latch executions is the correct thing to use. */
1775 if (max_loop_iterations (loop, &nit))
1776 {
1777 value_range maxvr = VR_INITIALIZER;
1778 signop sgn = TYPE_SIGN (TREE_TYPE (step));
1779 bool overflow;
1780
1781 widest_int wtmp = wi::mul (wi::to_widest (step), nit, sgn,
1782 &overflow);
1783 /* If the multiplication overflowed we can't do a meaningful
1784 adjustment. Likewise if the result doesn't fit in the type
1785 of the induction variable. For a signed type we have to
1786 check whether the result has the expected signedness which
1787 is that of the step as number of iterations is unsigned. */
1788 if (!overflow
1789 && wi::fits_to_tree_p (wtmp, TREE_TYPE (init))
1790 && (sgn == UNSIGNED
1791 || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0)))
1792 {
1793 tem = wide_int_to_tree (TREE_TYPE (init), wtmp);
1794 extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
1795 TREE_TYPE (init), init, tem);
1796 /* Likewise if the addition did. */
1797 if (maxvr.type == VR_RANGE)
1798 {
1799 value_range initvr = VR_INITIALIZER;
1800
1801 if (TREE_CODE (init) == SSA_NAME)
1802 initvr = *(get_value_range (init));
1803 else if (is_gimple_min_invariant (init))
1804 set_value_range_to_value (&initvr, init, NULL);
1805 else
1806 return;
1807
1808 /* Check if init + nit * step overflows. Though we checked
1809 scev {init, step}_loop doesn't wrap, it is not enough
1810 because the loop may exit immediately. Overflow could
1811 happen in the plus expression in this case. */
1812 if ((dir == EV_DIR_DECREASES
1813 && compare_values (maxvr.min, initvr.min) != -1)
1814 || (dir == EV_DIR_GROWS
1815 && compare_values (maxvr.max, initvr.max) != 1))
1816 return;
1817
1818 tmin = maxvr.min;
1819 tmax = maxvr.max;
1820 }
1821 }
1822 }
1823 }
1824
1825 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1826 {
1827 min = tmin;
1828 max = tmax;
1829
1830 /* For VARYING or UNDEFINED ranges, just about anything we get
1831 from scalar evolutions should be better. */
1832
1833 if (dir == EV_DIR_DECREASES)
1834 max = init;
1835 else
1836 min = init;
1837 }
1838 else if (vr->type == VR_RANGE)
1839 {
1840 min = vr->min;
1841 max = vr->max;
1842
1843 if (dir == EV_DIR_DECREASES)
1844 {
1845 /* INIT is the maximum value. If INIT is lower than VR->MAX
1846 but no smaller than VR->MIN, set VR->MAX to INIT. */
1847 if (compare_values (init, max) == -1)
1848 max = init;
1849
1850 /* According to the loop information, the variable does not
1851 overflow. */
1852 if (compare_values (min, tmin) == -1)
1853 min = tmin;
1854
1855 }
1856 else
1857 {
1858 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1859 if (compare_values (init, min) == 1)
1860 min = init;
1861
1862 if (compare_values (tmax, max) == -1)
1863 max = tmax;
1864 }
1865 }
1866 else
1867 return;
1868
1869 /* If we just created an invalid range with the minimum
1870 greater than the maximum, we fail conservatively.
1871 This should happen only in unreachable
1872 parts of code, or for invalid programs. */
1873 if (compare_values (min, max) == 1)
1874 return;
1875
1876 /* Even for valid range info, sometimes overflow flag will leak in.
1877 As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
1878 drop them. */
1879 if (TREE_OVERFLOW_P (min))
1880 min = drop_tree_overflow (min);
1881 if (TREE_OVERFLOW_P (max))
1882 max = drop_tree_overflow (max);
1883
1884 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1885}
1886
1887/* Dump value ranges of all SSA_NAMEs to FILE. */
1888
1889void
1890vr_values::dump_all_value_ranges (FILE *file)
1891{
1892 size_t i;
1893
1894 for (i = 0; i < num_vr_values; i++)
1895 {
1896 if (vr_value[i])
1897 {
1898 print_generic_expr (file, ssa_name (i));
1899 fprintf (file, ": ");
1900 dump_value_range (file, vr_value[i]);
1901 fprintf (file, "\n");
1902 }
1903 }
1904
1905 fprintf (file, "\n");
1906}
1907
1908/* Initialize VRP lattice. */
1909
1910vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
1911{
1912 values_propagated = false;
1913 num_vr_values = num_ssa_names;
1914 vr_value = XCNEWVEC (value_range *, num_vr_values);
1915 vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
1916 bitmap_obstack_initialize (&vrp_equiv_obstack);
1917}
1918
1919/* Free VRP lattice. */
1920
1921vr_values::~vr_values ()
1922{
1923 /* Free allocated memory. */
1924 free (vr_value);
1925 free (vr_phi_edge_counts);
1926 bitmap_obstack_release (&vrp_equiv_obstack);
1927 vrp_value_range_pool.release ();
1928
1929 /* So that we can distinguish between VRP data being available
1930 and not available. */
1931 vr_value = NULL;
1932 vr_phi_edge_counts = NULL;
1933}
1934
1935
1936/* A hack. */
1937static class vr_values *x_vr_values;
1938
1939/* Return the singleton value-range for NAME or NAME. */
1940
1941static inline tree
1942vrp_valueize (tree name)
1943{
1944 if (TREE_CODE (name) == SSA_NAME)
1945 {
1946 value_range *vr = x_vr_values->get_value_range (name);
1947 if (vr->type == VR_RANGE
1948 && (TREE_CODE (vr->min) == SSA_NAME
1949 || is_gimple_min_invariant (vr->min))
1950 && vrp_operand_equal_p (vr->min, vr->max))
1951 return vr->min;
1952 }
1953 return name;
1954}
1955
1956/* Return the singleton value-range for NAME if that is a constant
1957 but signal to not follow SSA edges. */
1958
1959static inline tree
1960vrp_valueize_1 (tree name)
1961{
1962 if (TREE_CODE (name) == SSA_NAME)
1963 {
1964 /* If the definition may be simulated again we cannot follow
1965 this SSA edge as the SSA propagator does not necessarily
1966 re-visit the use. */
1967 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1968 if (!gimple_nop_p (def_stmt)
1969 && prop_simulate_again_p (def_stmt))
1970 return NULL_TREE;
1971 value_range *vr = x_vr_values->get_value_range (name);
1972 if (range_int_cst_singleton_p (vr))
1973 return vr->min;
1974 }
1975 return name;
1976}
1977
1978/* Given STMT, an assignment or call, return its LHS if the type
1979 of the LHS is suitable for VRP analysis, else return NULL_TREE. */
1980
1981tree
1982get_output_for_vrp (gimple *stmt)
1983{
1984 if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
1985 return NULL_TREE;
1986
1987 /* We only keep track of ranges in integral and pointer types. */
1988 tree lhs = gimple_get_lhs (stmt);
1989 if (TREE_CODE (lhs) == SSA_NAME
1990 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1991 /* It is valid to have NULL MIN/MAX values on a type. See
1992 build_range_type. */
1993 && TYPE_MIN_VALUE (TREE_TYPE (lhs))
1994 && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
1995 || POINTER_TYPE_P (TREE_TYPE (lhs))))
1996 return lhs;
1997
1998 return NULL_TREE;
1999}
2000
2001/* Visit assignment STMT. If it produces an interesting range, record
2002 the range in VR and set LHS to OUTPUT_P. */
2003
2004void
2005vr_values::vrp_visit_assignment_or_call (gimple *stmt, tree *output_p,
2006 value_range *vr)
2007{
2008 tree lhs = get_output_for_vrp (stmt);
2009 *output_p = lhs;
2010
2011 /* We only keep track of ranges in integral and pointer types. */
2012 if (lhs)
2013 {
2014 enum gimple_code code = gimple_code (stmt);
2015
2016 /* Try folding the statement to a constant first. */
2017 x_vr_values = this;
2018 tree tem = gimple_fold_stmt_to_constant_1 (stmt, vrp_valueize,
2019 vrp_valueize_1);
2020 x_vr_values = NULL;
2021 if (tem)
2022 {
2023 if (TREE_CODE (tem) == SSA_NAME
2024 && (SSA_NAME_IS_DEFAULT_DEF (tem)
2025 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem))))
2026 {
2027 extract_range_from_ssa_name (vr, tem);
2028 return;
2029 }
2030 else if (is_gimple_min_invariant (tem))
2031 {
2032 set_value_range_to_value (vr, tem, NULL);
2033 return;
2034 }
2035 }
2036 /* Then dispatch to value-range extracting functions. */
2037 if (code == GIMPLE_CALL)
2038 extract_range_basic (vr, stmt);
2039 else
2040 extract_range_from_assignment (vr, as_a <gassign *> (stmt));
2041 }
2042}
2043
2044/* Helper that gets the value range of the SSA_NAME with version I
2045 or a symbolic range containing the SSA_NAME only if the value range
2046 is varying or undefined. */
2047
2048value_range
2049vr_values::get_vr_for_comparison (int i)
2050{
2051 value_range vr = *get_value_range (ssa_name (i));
2052
2053 /* If name N_i does not have a valid range, use N_i as its own
2054 range. This allows us to compare against names that may
2055 have N_i in their ranges. */
2056 if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
2057 {
2058 vr.type = VR_RANGE;
2059 vr.min = ssa_name (i);
2060 vr.max = ssa_name (i);
2061 }
2062
2063 return vr;
2064}
2065
2066/* Compare all the value ranges for names equivalent to VAR with VAL
2067 using comparison code COMP. Return the same value returned by
2068 compare_range_with_value, including the setting of
2069 *STRICT_OVERFLOW_P. */
2070
2071tree
2072vr_values::compare_name_with_value (enum tree_code comp, tree var, tree val,
2073 bool *strict_overflow_p, bool use_equiv_p)
2074{
2075 bitmap_iterator bi;
2076 unsigned i;
2077 bitmap e;
2078 tree retval, t;
2079 int used_strict_overflow;
2080 bool sop;
2081 value_range equiv_vr;
2082
2083 /* Get the set of equivalences for VAR. */
2084 e = get_value_range (var)->equiv;
2085
2086 /* Start at -1. Set it to 0 if we do a comparison without relying
2087 on overflow, or 1 if all comparisons rely on overflow. */
2088 used_strict_overflow = -1;
2089
2090 /* Compare vars' value range with val. */
2091 equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
2092 sop = false;
2093 retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
2094 if (retval)
2095 used_strict_overflow = sop ? 1 : 0;
2096
2097 /* If the equiv set is empty we have done all work we need to do. */
2098 if (e == NULL)
2099 {
2100 if (retval
2101 && used_strict_overflow > 0)
2102 *strict_overflow_p = true;
2103 return retval;
2104 }
2105
2106 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
2107 {
2108 tree name = ssa_name (i);
2109 if (! name)
2110 continue;
2111
2112 if (! use_equiv_p
2113 && ! SSA_NAME_IS_DEFAULT_DEF (name)
2114 && prop_simulate_again_p (SSA_NAME_DEF_STMT (name)))
2115 continue;
2116
2117 equiv_vr = get_vr_for_comparison (i);
2118 sop = false;
2119 t = compare_range_with_value (comp, &equiv_vr, val, &sop);
2120 if (t)
2121 {
2122 /* If we get different answers from different members
2123 of the equivalence set this check must be in a dead
2124 code region. Folding it to a trap representation
2125 would be correct here. For now just return don't-know. */
2126 if (retval != NULL
2127 && t != retval)
2128 {
2129 retval = NULL_TREE;
2130 break;
2131 }
2132 retval = t;
2133
2134 if (!sop)
2135 used_strict_overflow = 0;
2136 else if (used_strict_overflow < 0)
2137 used_strict_overflow = 1;
2138 }
2139 }
2140
2141 if (retval
2142 && used_strict_overflow > 0)
2143 *strict_overflow_p = true;
2144
2145 return retval;
2146}
2147
2148
2149/* Given a comparison code COMP and names N1 and N2, compare all the
2150 ranges equivalent to N1 against all the ranges equivalent to N2
2151 to determine the value of N1 COMP N2. Return the same value
2152 returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate
2153 whether we relied on undefined signed overflow in the comparison. */
2154
2155
2156tree
2157vr_values::compare_names (enum tree_code comp, tree n1, tree n2,
2158 bool *strict_overflow_p)
2159{
2160 tree t, retval;
2161 bitmap e1, e2;
2162 bitmap_iterator bi1, bi2;
2163 unsigned i1, i2;
2164 int used_strict_overflow;
2165 static bitmap_obstack *s_obstack = NULL;
2166 static bitmap s_e1 = NULL, s_e2 = NULL;
2167
2168 /* Compare the ranges of every name equivalent to N1 against the
2169 ranges of every name equivalent to N2. */
2170 e1 = get_value_range (n1)->equiv;
2171 e2 = get_value_range (n2)->equiv;
2172
2173 /* Use the fake bitmaps if e1 or e2 are not available. */
2174 if (s_obstack == NULL)
2175 {
2176 s_obstack = XNEW (bitmap_obstack);
2177 bitmap_obstack_initialize (s_obstack);
2178 s_e1 = BITMAP_ALLOC (s_obstack);
2179 s_e2 = BITMAP_ALLOC (s_obstack);
2180 }
2181 if (e1 == NULL)
2182 e1 = s_e1;
2183 if (e2 == NULL)
2184 e2 = s_e2;
2185
2186 /* Add N1 and N2 to their own set of equivalences to avoid
2187 duplicating the body of the loop just to check N1 and N2
2188 ranges. */
2189 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
2190 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
2191
2192 /* If the equivalence sets have a common intersection, then the two
2193 names can be compared without checking their ranges. */
2194 if (bitmap_intersect_p (e1, e2))
2195 {
2196 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2197 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2198
2199 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
2200 ? boolean_true_node
2201 : boolean_false_node;
2202 }
2203
2204 /* Start at -1. Set it to 0 if we do a comparison without relying
2205 on overflow, or 1 if all comparisons rely on overflow. */
2206 used_strict_overflow = -1;
2207
2208 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2209 N2 to their own set of equivalences to avoid duplicating the body
2210 of the loop just to check N1 and N2 ranges. */
2211 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
2212 {
2213 if (! ssa_name (i1))
2214 continue;
2215
2216 value_range vr1 = get_vr_for_comparison (i1);
2217
2218 t = retval = NULL_TREE;
2219 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
2220 {
2221 if (! ssa_name (i2))
2222 continue;
2223
2224 bool sop = false;
2225
2226 value_range vr2 = get_vr_for_comparison (i2);
2227
2228 t = compare_ranges (comp, &vr1, &vr2, &sop);
2229 if (t)
2230 {
2231 /* If we get different answers from different members
2232 of the equivalence set this check must be in a dead
2233 code region. Folding it to a trap representation
2234 would be correct here. For now just return don't-know. */
2235 if (retval != NULL
2236 && t != retval)
2237 {
2238 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2239 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2240 return NULL_TREE;
2241 }
2242 retval = t;
2243
2244 if (!sop)
2245 used_strict_overflow = 0;
2246 else if (used_strict_overflow < 0)
2247 used_strict_overflow = 1;
2248 }
2249 }
2250
2251 if (retval)
2252 {
2253 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2254 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2255 if (used_strict_overflow > 0)
2256 *strict_overflow_p = true;
2257 return retval;
2258 }
2259 }
2260
2261 /* None of the equivalent ranges are useful in computing this
2262 comparison. */
2263 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2264 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2265 return NULL_TREE;
2266}
2267
2268/* Helper function for vrp_evaluate_conditional_warnv & other
2269 optimizers. */
2270
2271tree
2272vr_values::vrp_evaluate_conditional_warnv_with_ops_using_ranges
2273 (enum tree_code code, tree op0, tree op1, bool * strict_overflow_p)
2274{
2275 value_range *vr0, *vr1;
2276
2277 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
2278 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
2279
2280 tree res = NULL_TREE;
2281 if (vr0 && vr1)
2282 res = compare_ranges (code, vr0, vr1, strict_overflow_p);
2283 if (!res && vr0)
2284 res = compare_range_with_value (code, vr0, op1, strict_overflow_p);
2285 if (!res && vr1)
2286 res = (compare_range_with_value
2287 (swap_tree_comparison (code), vr1, op0, strict_overflow_p));
2288 return res;
2289}
2290
2291/* Helper function for vrp_evaluate_conditional_warnv. */
2292
2293tree
2294vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
2295 tree op0, tree op1,
2296 bool use_equiv_p,
2297 bool *strict_overflow_p,
2298 bool *only_ranges)
2299{
2300 tree ret;
2301 if (only_ranges)
2302 *only_ranges = true;
2303
2304 /* We only deal with integral and pointer types. */
2305 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2306 && !POINTER_TYPE_P (TREE_TYPE (op0)))
2307 return NULL_TREE;
2308
2309 /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
2310 as a simple equality test, then prefer that over its current form
2311 for evaluation.
2312
2313 An overflow test which collapses to an equality test can always be
2314 expressed as a comparison of one argument against zero. Overflow
2315 occurs when the chosen argument is zero and does not occur if the
2316 chosen argument is not zero. */
2317 tree x;
2318 if (overflow_comparison_p (code, op0, op1, use_equiv_p, &x))
2319 {
2320 wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
2321 /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
2322 B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
2323 B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
2324 B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
2325 if (integer_zerop (x))
2326 {
2327 op1 = x;
2328 code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
2329 }
2330 /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
2331 B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
2332 B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
2333 B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
2334 else if (wi::to_wide (x) == max - 1)
2335 {
2336 op0 = op1;
2337 op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
2338 code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
2339 }
2340 }
2341
2342 if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
2343 (code, op0, op1, strict_overflow_p)))
2344 return ret;
2345 if (only_ranges)
2346 *only_ranges = false;
2347 /* Do not use compare_names during propagation, it's quadratic. */
2348 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME
2349 && use_equiv_p)
2350 return compare_names (code, op0, op1, strict_overflow_p);
2351 else if (TREE_CODE (op0) == SSA_NAME)
2352 return compare_name_with_value (code, op0, op1,
2353 strict_overflow_p, use_equiv_p);
2354 else if (TREE_CODE (op1) == SSA_NAME)
2355 return compare_name_with_value (swap_tree_comparison (code), op1, op0,
2356 strict_overflow_p, use_equiv_p);
2357 return NULL_TREE;
2358}
2359
2360/* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
2361 information. Return NULL if the conditional can not be evaluated.
2362 The ranges of all the names equivalent with the operands in COND
2363 will be used when trying to compute the value. If the result is
2364 based on undefined signed overflow, issue a warning if
2365 appropriate. */
2366
2367tree
2368vr_values::vrp_evaluate_conditional (tree_code code, tree op0,
2369 tree op1, gimple *stmt)
2370{
2371 bool sop;
2372 tree ret;
2373 bool only_ranges;
2374
2375 /* Some passes and foldings leak constants with overflow flag set
2376 into the IL. Avoid doing wrong things with these and bail out. */
2377 if ((TREE_CODE (op0) == INTEGER_CST
2378 && TREE_OVERFLOW (op0))
2379 || (TREE_CODE (op1) == INTEGER_CST
2380 && TREE_OVERFLOW (op1)))
2381 return NULL_TREE;
2382
2383 sop = false;
2384 ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop,
2385 &only_ranges);
2386
2387 if (ret && sop)
2388 {
2389 enum warn_strict_overflow_code wc;
2390 const char* warnmsg;
2391
2392 if (is_gimple_min_invariant (ret))
2393 {
2394 wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
2395 warnmsg = G_("assuming signed overflow does not occur when "
2396 "simplifying conditional to constant");
2397 }
2398 else
2399 {
2400 wc = WARN_STRICT_OVERFLOW_COMPARISON;
2401 warnmsg = G_("assuming signed overflow does not occur when "
2402 "simplifying conditional");
2403 }
2404
2405 if (issue_strict_overflow_warning (wc))
2406 {
2407 location_t location;
2408
2409 if (!gimple_has_location (stmt))
2410 location = input_location;
2411 else
2412 location = gimple_location (stmt);
2413 warning_at (location, OPT_Wstrict_overflow, "%s", warnmsg);
2414 }
2415 }
2416
2417 if (warn_type_limits
2418 && ret && only_ranges
2419 && TREE_CODE_CLASS (code) == tcc_comparison
2420 && TREE_CODE (op0) == SSA_NAME)
2421 {
2422 /* If the comparison is being folded and the operand on the LHS
2423 is being compared against a constant value that is outside of
2424 the natural range of OP0's type, then the predicate will
2425 always fold regardless of the value of OP0. If -Wtype-limits
2426 was specified, emit a warning. */
2427 tree type = TREE_TYPE (op0);
2428 value_range *vr0 = get_value_range (op0);
2429
2430 if (vr0->type == VR_RANGE
2431 && INTEGRAL_TYPE_P (type)
2432 && vrp_val_is_min (vr0->min)
2433 && vrp_val_is_max (vr0->max)
2434 && is_gimple_min_invariant (op1))
2435 {
2436 location_t location;
2437
2438 if (!gimple_has_location (stmt))
2439 location = input_location;
2440 else
2441 location = gimple_location (stmt);
2442
2443 warning_at (location, OPT_Wtype_limits,
2444 integer_zerop (ret)
2445 ? G_("comparison always false "
2446 "due to limited range of data type")
2447 : G_("comparison always true "
2448 "due to limited range of data type"));
2449 }
2450 }
2451
2452 return ret;
2453}
2454
2455
2456/* Visit conditional statement STMT. If we can determine which edge
2457 will be taken out of STMT's basic block, record it in
2458 *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
2459
2460void
2461vr_values::vrp_visit_cond_stmt (gcond *stmt, edge *taken_edge_p)
2462{
2463 tree val;
2464
2465 *taken_edge_p = NULL;
2466
2467 if (dump_file && (dump_flags & TDF_DETAILS))
2468 {
2469 tree use;
2470 ssa_op_iter i;
2471
2472 fprintf (dump_file, "\nVisiting conditional with predicate: ");
2473 print_gimple_stmt (dump_file, stmt, 0);
2474 fprintf (dump_file, "\nWith known ranges\n");
2475
2476 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
2477 {
2478 fprintf (dump_file, "\t");
2479 print_generic_expr (dump_file, use);
2480 fprintf (dump_file, ": ");
2481 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
2482 }
2483
2484 fprintf (dump_file, "\n");
2485 }
2486
2487 /* Compute the value of the predicate COND by checking the known
2488 ranges of each of its operands.
2489
2490 Note that we cannot evaluate all the equivalent ranges here
2491 because those ranges may not yet be final and with the current
2492 propagation strategy, we cannot determine when the value ranges
2493 of the names in the equivalence set have changed.
2494
2495 For instance, given the following code fragment
2496
2497 i_5 = PHI <8, i_13>
2498 ...
2499 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
2500 if (i_14 == 1)
2501 ...
2502
2503 Assume that on the first visit to i_14, i_5 has the temporary
2504 range [8, 8] because the second argument to the PHI function is
2505 not yet executable. We derive the range ~[0, 0] for i_14 and the
2506 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
2507 the first time, since i_14 is equivalent to the range [8, 8], we
2508 determine that the predicate is always false.
2509
2510 On the next round of propagation, i_13 is determined to be
2511 VARYING, which causes i_5 to drop down to VARYING. So, another
2512 visit to i_14 is scheduled. In this second visit, we compute the
2513 exact same range and equivalence set for i_14, namely ~[0, 0] and
2514 { i_5 }. But we did not have the previous range for i_5
2515 registered, so vrp_visit_assignment thinks that the range for
2516 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
2517 is not visited again, which stops propagation from visiting
2518 statements in the THEN clause of that if().
2519
2520 To properly fix this we would need to keep the previous range
2521 value for the names in the equivalence set. This way we would've
2522 discovered that from one visit to the other i_5 changed from
2523 range [8, 8] to VR_VARYING.
2524
2525 However, fixing this apparent limitation may not be worth the
2526 additional checking. Testing on several code bases (GCC, DLV,
2527 MICO, TRAMP3D and SPEC2000) showed that doing this results in
2528 4 more predicates folded in SPEC. */
2529
2530 bool sop;
2531 val = vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt),
2532 gimple_cond_lhs (stmt),
2533 gimple_cond_rhs (stmt),
2534 false, &sop, NULL);
2535 if (val)
2536 *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
2537
2538 if (dump_file && (dump_flags & TDF_DETAILS))
2539 {
2540 fprintf (dump_file, "\nPredicate evaluates to: ");
2541 if (val == NULL_TREE)
2542 fprintf (dump_file, "DON'T KNOW\n");
2543 else
2544 print_generic_stmt (dump_file, val);
2545 }
2546}
2547
2548/* Searches the case label vector VEC for the ranges of CASE_LABELs that are
2549 used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
2550 MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
2551 Returns true if the default label is not needed. */
2552
2553static bool
2554find_case_label_ranges (gswitch *stmt, value_range *vr, size_t *min_idx1,
2555 size_t *max_idx1, size_t *min_idx2,
2556 size_t *max_idx2)
2557{
2558 size_t i, j, k, l;
2559 unsigned int n = gimple_switch_num_labels (stmt);
2560 bool take_default;
2561 tree case_low, case_high;
2562 tree min = vr->min, max = vr->max;
2563
2564 gcc_checking_assert (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE);
2565
2566 take_default = !find_case_label_range (stmt, min, max, &i, &j);
2567
2568 /* Set second range to emtpy. */
2569 *min_idx2 = 1;
2570 *max_idx2 = 0;
2571
2572 if (vr->type == VR_RANGE)
2573 {
2574 *min_idx1 = i;
2575 *max_idx1 = j;
2576 return !take_default;
2577 }
2578
2579 /* Set first range to all case labels. */
2580 *min_idx1 = 1;
2581 *max_idx1 = n - 1;
2582
2583 if (i > j)
2584 return false;
2585
2586 /* Make sure all the values of case labels [i , j] are contained in
2587 range [MIN, MAX]. */
2588 case_low = CASE_LOW (gimple_switch_label (stmt, i));
2589 case_high = CASE_HIGH (gimple_switch_label (stmt, j));
2590 if (tree_int_cst_compare (case_low, min) < 0)
2591 i += 1;
2592 if (case_high != NULL_TREE
2593 && tree_int_cst_compare (max, case_high) < 0)
2594 j -= 1;
2595
2596 if (i > j)
2597 return false;
2598
2599 /* If the range spans case labels [i, j], the corresponding anti-range spans
2600 the labels [1, i - 1] and [j + 1, n - 1]. */
2601 k = j + 1;
2602 l = n - 1;
2603 if (k > l)
2604 {
2605 k = 1;
2606 l = 0;
2607 }
2608
2609 j = i - 1;
2610 i = 1;
2611 if (i > j)
2612 {
2613 i = k;
2614 j = l;
2615 k = 1;
2616 l = 0;
2617 }
2618
2619 *min_idx1 = i;
2620 *max_idx1 = j;
2621 *min_idx2 = k;
2622 *max_idx2 = l;
2623 return false;
2624}
2625
2626/* Visit switch statement STMT. If we can determine which edge
2627 will be taken out of STMT's basic block, record it in
2628 *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */
2629
2630void
2631vr_values::vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p)
2632{
2633 tree op, val;
2634 value_range *vr;
2635 size_t i = 0, j = 0, k, l;
2636 bool take_default;
2637
2638 *taken_edge_p = NULL;
2639 op = gimple_switch_index (stmt);
2640 if (TREE_CODE (op) != SSA_NAME)
2641 return;
2642
2643 vr = get_value_range (op);
2644 if (dump_file && (dump_flags & TDF_DETAILS))
2645 {
2646 fprintf (dump_file, "\nVisiting switch expression with operand ");
2647 print_generic_expr (dump_file, op);
2648 fprintf (dump_file, " with known range ");
2649 dump_value_range (dump_file, vr);
2650 fprintf (dump_file, "\n");
2651 }
2652
2653 if ((vr->type != VR_RANGE
2654 && vr->type != VR_ANTI_RANGE)
2655 || symbolic_range_p (vr))
2656 return;
2657
2658 /* Find the single edge that is taken from the switch expression. */
2659 take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
2660
2661 /* Check if the range spans no CASE_LABEL. If so, we only reach the default
2662 label */
2663 if (j < i)
2664 {
2665 gcc_assert (take_default);
2666 val = gimple_switch_default_label (stmt);
2667 }
2668 else
2669 {
2670 /* Check if labels with index i to j and maybe the default label
2671 are all reaching the same label. */
2672
2673 val = gimple_switch_label (stmt, i);
2674 if (take_default
2675 && CASE_LABEL (gimple_switch_default_label (stmt))
2676 != CASE_LABEL (val))
2677 {
2678 if (dump_file && (dump_flags & TDF_DETAILS))
2679 fprintf (dump_file, " not a single destination for this "
2680 "range\n");
2681 return;
2682 }
2683 for (++i; i <= j; ++i)
2684 {
2685 if (CASE_LABEL (gimple_switch_label (stmt, i)) != CASE_LABEL (val))
2686 {
2687 if (dump_file && (dump_flags & TDF_DETAILS))
2688 fprintf (dump_file, " not a single destination for this "
2689 "range\n");
2690 return;
2691 }
2692 }
2693 for (; k <= l; ++k)
2694 {
2695 if (CASE_LABEL (gimple_switch_label (stmt, k)) != CASE_LABEL (val))
2696 {
2697 if (dump_file && (dump_flags & TDF_DETAILS))
2698 fprintf (dump_file, " not a single destination for this "
2699 "range\n");
2700 return;
2701 }
2702 }
2703 }
2704
2705 *taken_edge_p = find_edge (gimple_bb (stmt),
2706 label_to_block (CASE_LABEL (val)));
2707
2708 if (dump_file && (dump_flags & TDF_DETAILS))
2709 {
2710 fprintf (dump_file, " will take edge to ");
2711 print_generic_stmt (dump_file, CASE_LABEL (val));
2712 }
2713}
2714
2715
2716/* Evaluate statement STMT. If the statement produces a useful range,
2717 set VR and corepsponding OUTPUT_P.
2718
2719 If STMT is a conditional branch and we can determine its truth
2720 value, the taken edge is recorded in *TAKEN_EDGE_P. */
2721
2722void
2723vr_values::extract_range_from_stmt (gimple *stmt, edge *taken_edge_p,
2724 tree *output_p, value_range *vr)
2725{
2726
2727 if (dump_file && (dump_flags & TDF_DETAILS))
2728 {
2729 fprintf (dump_file, "\nVisiting statement:\n");
2730 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2731 }
2732
2733 if (!stmt_interesting_for_vrp (stmt))
2734 gcc_assert (stmt_ends_bb_p (stmt));
2735 else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
2736 vrp_visit_assignment_or_call (stmt, output_p, vr);
2737 else if (gimple_code (stmt) == GIMPLE_COND)
2738 vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p);
2739 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2740 vrp_visit_switch_stmt (as_a <gswitch *> (stmt), taken_edge_p);
2741}
2742
2743/* Visit all arguments for PHI node PHI that flow through executable
2744 edges. If a valid value range can be derived from all the incoming
2745 value ranges, set a new range in VR_RESULT. */
2746
2747void
2748vr_values::extract_range_from_phi_node (gphi *phi, value_range *vr_result)
2749{
2750 size_t i;
2751 tree lhs = PHI_RESULT (phi);
2752 value_range *lhs_vr = get_value_range (lhs);
2753 bool first = true;
2754 int edges, old_edges;
2755 struct loop *l;
2756
2757 if (dump_file && (dump_flags & TDF_DETAILS))
2758 {
2759 fprintf (dump_file, "\nVisiting PHI node: ");
2760 print_gimple_stmt (dump_file, phi, 0, dump_flags);
2761 }
2762
2763 bool may_simulate_backedge_again = false;
2764 edges = 0;
2765 for (i = 0; i < gimple_phi_num_args (phi); i++)
2766 {
2767 edge e = gimple_phi_arg_edge (phi, i);
2768
2769 if (dump_file && (dump_flags & TDF_DETAILS))
2770 {
2771 fprintf (dump_file,
2772 " Argument #%d (%d -> %d %sexecutable)\n",
2773 (int) i, e->src->index, e->dest->index,
2774 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2775 }
2776
2777 if (e->flags & EDGE_EXECUTABLE)
2778 {
2779 tree arg = PHI_ARG_DEF (phi, i);
2780 value_range vr_arg;
2781
2782 ++edges;
2783
2784 if (TREE_CODE (arg) == SSA_NAME)
2785 {
2786 /* See if we are eventually going to change one of the args. */
2787 gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
2788 if (! gimple_nop_p (def_stmt)
2789 && prop_simulate_again_p (def_stmt)
2790 && e->flags & EDGE_DFS_BACK)
2791 may_simulate_backedge_again = true;
2792
2793 vr_arg = *(get_value_range (arg));
2794 /* Do not allow equivalences or symbolic ranges to leak in from
2795 backedges. That creates invalid equivalencies.
2796 See PR53465 and PR54767. */
2797 if (e->flags & EDGE_DFS_BACK)
2798 {
2799 if (vr_arg.type == VR_RANGE
2800 || vr_arg.type == VR_ANTI_RANGE)
2801 {
2802 vr_arg.equiv = NULL;
2803 if (symbolic_range_p (&vr_arg))
2804 {
2805 vr_arg.type = VR_VARYING;
2806 vr_arg.min = NULL_TREE;
2807 vr_arg.max = NULL_TREE;
2808 }
2809 }
2810 }
2811 else
2812 {
2813 /* If the non-backedge arguments range is VR_VARYING then
2814 we can still try recording a simple equivalence. */
2815 if (vr_arg.type == VR_VARYING)
2816 {
2817 vr_arg.type = VR_RANGE;
2818 vr_arg.min = arg;
2819 vr_arg.max = arg;
2820 vr_arg.equiv = NULL;
2821 }
2822 }
2823 }
2824 else
2825 {
2826 if (TREE_OVERFLOW_P (arg))
2827 arg = drop_tree_overflow (arg);
2828
2829 vr_arg.type = VR_RANGE;
2830 vr_arg.min = arg;
2831 vr_arg.max = arg;
2832 vr_arg.equiv = NULL;
2833 }
2834
2835 if (dump_file && (dump_flags & TDF_DETAILS))
2836 {
2837 fprintf (dump_file, "\t");
2838 print_generic_expr (dump_file, arg, dump_flags);
2839 fprintf (dump_file, ": ");
2840 dump_value_range (dump_file, &vr_arg);
2841 fprintf (dump_file, "\n");
2842 }
2843
2844 if (first)
2845 copy_value_range (vr_result, &vr_arg);
2846 else
2847 vrp_meet (vr_result, &vr_arg);
2848 first = false;
2849
2850 if (vr_result->type == VR_VARYING)
2851 break;
2852 }
2853 }
2854
2855 if (vr_result->type == VR_VARYING)
2856 goto varying;
2857 else if (vr_result->type == VR_UNDEFINED)
2858 goto update_range;
2859
2860 old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
2861 vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
2862
2863 /* To prevent infinite iterations in the algorithm, derive ranges
2864 when the new value is slightly bigger or smaller than the
2865 previous one. We don't do this if we have seen a new executable
2866 edge; this helps us avoid an infinity for conditionals
2867 which are not in a loop. If the old value-range was VR_UNDEFINED
2868 use the updated range and iterate one more time. If we will not
2869 simulate this PHI again via the backedge allow us to iterate. */
2870 if (edges > 0
2871 && gimple_phi_num_args (phi) > 1
2872 && edges == old_edges
2873 && lhs_vr->type != VR_UNDEFINED
2874 && may_simulate_backedge_again)
2875 {
2876 /* Compare old and new ranges, fall back to varying if the
2877 values are not comparable. */
2878 int cmp_min = compare_values (lhs_vr->min, vr_result->min);
2879 if (cmp_min == -2)
2880 goto varying;
2881 int cmp_max = compare_values (lhs_vr->max, vr_result->max);
2882 if (cmp_max == -2)
2883 goto varying;
2884
2885 /* For non VR_RANGE or for pointers fall back to varying if
2886 the range changed. */
2887 if ((lhs_vr->type != VR_RANGE || vr_result->type != VR_RANGE
2888 || POINTER_TYPE_P (TREE_TYPE (lhs)))
2889 && (cmp_min != 0 || cmp_max != 0))
2890 goto varying;
2891
2892 /* If the new minimum is larger than the previous one
2893 retain the old value. If the new minimum value is smaller
2894 than the previous one and not -INF go all the way to -INF + 1.
2895 In the first case, to avoid infinite bouncing between different
2896 minimums, and in the other case to avoid iterating millions of
2897 times to reach -INF. Going to -INF + 1 also lets the following
2898 iteration compute whether there will be any overflow, at the
2899 expense of one additional iteration. */
2900 if (cmp_min < 0)
2901 vr_result->min = lhs_vr->min;
2902 else if (cmp_min > 0
2903 && !vrp_val_is_min (vr_result->min))
2904 vr_result->min
2905 = int_const_binop (PLUS_EXPR,
2906 vrp_val_min (TREE_TYPE (vr_result->min)),
2907 build_int_cst (TREE_TYPE (vr_result->min), 1));
2908
2909 /* Similarly for the maximum value. */
2910 if (cmp_max > 0)
2911 vr_result->max = lhs_vr->max;
2912 else if (cmp_max < 0
2913 && !vrp_val_is_max (vr_result->max))
2914 vr_result->max
2915 = int_const_binop (MINUS_EXPR,
2916 vrp_val_max (TREE_TYPE (vr_result->min)),
2917 build_int_cst (TREE_TYPE (vr_result->min), 1));
2918
2919 /* If we dropped either bound to +-INF then if this is a loop
2920 PHI node SCEV may known more about its value-range. */
2921 if (cmp_min > 0 || cmp_min < 0
2922 || cmp_max < 0 || cmp_max > 0)
2923 goto scev_check;
2924
2925 goto infinite_check;
2926 }
2927
2928 goto update_range;
2929
2930varying:
2931 set_value_range_to_varying (vr_result);
2932
2933scev_check:
2934 /* If this is a loop PHI node SCEV may known more about its value-range.
2935 scev_check can be reached from two paths, one is a fall through from above
2936 "varying" label, the other is direct goto from code block which tries to
2937 avoid infinite simulation. */
2938 if (scev_initialized_p ()
2939 && (l = loop_containing_stmt (phi))
2940 && l->header == gimple_bb (phi))
2941 adjust_range_with_scev (vr_result, l, phi, lhs);
2942
2943infinite_check:
2944 /* If we will end up with a (-INF, +INF) range, set it to
2945 VARYING. Same if the previous max value was invalid for
2946 the type and we end up with vr_result.min > vr_result.max. */
2947 if ((vr_result->type == VR_RANGE || vr_result->type == VR_ANTI_RANGE)
2948 && !((vrp_val_is_max (vr_result->max) && vrp_val_is_min (vr_result->min))
2949 || compare_values (vr_result->min, vr_result->max) > 0))
2950 ;
2951 else
2952 set_value_range_to_varying (vr_result);
2953
2954 /* If the new range is different than the previous value, keep
2955 iterating. */
2956update_range:
2957 return;
2958}
2959
2960/* Simplify boolean operations if the source is known
2961 to be already a boolean. */
2962bool
2963vr_values::simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi,
2964 gimple *stmt)
2965{
2966 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
2967 tree lhs, op0, op1;
2968 bool need_conversion;
2969
2970 /* We handle only !=/== case here. */
2971 gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
2972
2973 op0 = gimple_assign_rhs1 (stmt);
2974 if (!op_with_boolean_value_range_p (op0))
2975 return false;
2976
2977 op1 = gimple_assign_rhs2 (stmt);
2978 if (!op_with_boolean_value_range_p (op1))
2979 return false;
2980
2981 /* Reduce number of cases to handle to NE_EXPR. As there is no
2982 BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
2983 if (rhs_code == EQ_EXPR)
2984 {
2985 if (TREE_CODE (op1) == INTEGER_CST)
2986 op1 = int_const_binop (BIT_XOR_EXPR, op1,
2987 build_int_cst (TREE_TYPE (op1), 1));
2988 else
2989 return false;
2990 }
2991
2992 lhs = gimple_assign_lhs (stmt);
2993 need_conversion
2994 = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0));
2995
2996 /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
2997 if (need_conversion
2998 && !TYPE_UNSIGNED (TREE_TYPE (op0))
2999 && TYPE_PRECISION (TREE_TYPE (op0)) == 1
3000 && TYPE_PRECISION (TREE_TYPE (lhs)) > 1)
3001 return false;
3002
3003 /* For A != 0 we can substitute A itself. */
3004 if (integer_zerop (op1))
3005 gimple_assign_set_rhs_with_ops (gsi,
3006 need_conversion
3007 ? NOP_EXPR : TREE_CODE (op0), op0);
3008 /* For A != B we substitute A ^ B. Either with conversion. */
3009 else if (need_conversion)
3010 {
3011 tree tem = make_ssa_name (TREE_TYPE (op0));
3012 gassign *newop
3013 = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1);
3014 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
3015 if (INTEGRAL_TYPE_P (TREE_TYPE (tem))
3016 && TYPE_PRECISION (TREE_TYPE (tem)) > 1)
3017 set_range_info (tem, VR_RANGE,
3018 wi::zero (TYPE_PRECISION (TREE_TYPE (tem))),
3019 wi::one (TYPE_PRECISION (TREE_TYPE (tem))));
3020 gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem);
3021 }
3022 /* Or without. */
3023 else
3024 gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1);
3025 update_stmt (gsi_stmt (*gsi));
3026 fold_stmt (gsi, follow_single_use_edges);
3027
3028 return true;
3029}
3030
3031/* Simplify a division or modulo operator to a right shift or bitwise and
3032 if the first operand is unsigned or is greater than zero and the second
3033 operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
3034 constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
3035 optimize it into just op0 if op0's range is known to be a subset of
3036 [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
3037 modulo. */
3038
3039bool
3040vr_values::simplify_div_or_mod_using_ranges (gimple_stmt_iterator *gsi,
3041 gimple *stmt)
3042{
3043 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3044 tree val = NULL;
3045 tree op0 = gimple_assign_rhs1 (stmt);
3046 tree op1 = gimple_assign_rhs2 (stmt);
3047 tree op0min = NULL_TREE, op0max = NULL_TREE;
3048 tree op1min = op1;
3049 value_range *vr = NULL;
3050
3051 if (TREE_CODE (op0) == INTEGER_CST)
3052 {
3053 op0min = op0;
3054 op0max = op0;
3055 }
3056 else
3057 {
3058 vr = get_value_range (op0);
3059 if (range_int_cst_p (vr))
3060 {
3061 op0min = vr->min;
3062 op0max = vr->max;
3063 }
3064 }
3065
3066 if (rhs_code == TRUNC_MOD_EXPR
3067 && TREE_CODE (op1) == SSA_NAME)
3068 {
3069 value_range *vr1 = get_value_range (op1);
3070 if (range_int_cst_p (vr1))
3071 op1min = vr1->min;
3072 }
3073 if (rhs_code == TRUNC_MOD_EXPR
3074 && TREE_CODE (op1min) == INTEGER_CST
3075 && tree_int_cst_sgn (op1min) == 1
3076 && op0max
3077 && tree_int_cst_lt (op0max, op1min))
3078 {
3079 if (TYPE_UNSIGNED (TREE_TYPE (op0))
3080 || tree_int_cst_sgn (op0min) >= 0
3081 || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min),
3082 op0min))
3083 {
3084 /* If op0 already has the range op0 % op1 has,
3085 then TRUNC_MOD_EXPR won't change anything. */
3086 gimple_assign_set_rhs_from_tree (gsi, op0);
3087 return true;
3088 }
3089 }
3090
3091 if (TREE_CODE (op0) != SSA_NAME)
3092 return false;
3093
3094 if (!integer_pow2p (op1))
3095 {
3096 /* X % -Y can be only optimized into X % Y either if
3097 X is not INT_MIN, or Y is not -1. Fold it now, as after
3098 remove_range_assertions the range info might be not available
3099 anymore. */
3100 if (rhs_code == TRUNC_MOD_EXPR
3101 && fold_stmt (gsi, follow_single_use_edges))
3102 return true;
3103 return false;
3104 }
3105
3106 if (TYPE_UNSIGNED (TREE_TYPE (op0)))
3107 val = integer_one_node;
3108 else
3109 {
3110 bool sop = false;
3111
3112 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
3113
3114 if (val
3115 && sop
3116 && integer_onep (val)
3117 && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3118 {
3119 location_t location;
3120
3121 if (!gimple_has_location (stmt))
3122 location = input_location;
3123 else
3124 location = gimple_location (stmt);
3125 warning_at (location, OPT_Wstrict_overflow,
3126 "assuming signed overflow does not occur when "
3127 "simplifying %</%> or %<%%%> to %<>>%> or %<&%>");
3128 }
3129 }
3130
3131 if (val && integer_onep (val))
3132 {
3133 tree t;
3134
3135 if (rhs_code == TRUNC_DIV_EXPR)
3136 {
3137 t = build_int_cst (integer_type_node, tree_log2 (op1));
3138 gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
3139 gimple_assign_set_rhs1 (stmt, op0);
3140 gimple_assign_set_rhs2 (stmt, t);
3141 }
3142 else
3143 {
3144 t = build_int_cst (TREE_TYPE (op1), 1);
3145 t = int_const_binop (MINUS_EXPR, op1, t);
3146 t = fold_convert (TREE_TYPE (op0), t);
3147
3148 gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
3149 gimple_assign_set_rhs1 (stmt, op0);
3150 gimple_assign_set_rhs2 (stmt, t);
3151 }
3152
3153 update_stmt (stmt);
3154 fold_stmt (gsi, follow_single_use_edges);
3155 return true;
3156 }
3157
3158 return false;
3159}
3160
3161/* Simplify a min or max if the ranges of the two operands are
3162 disjoint. Return true if we do simplify. */
3163
3164bool
3165vr_values::simplify_min_or_max_using_ranges (gimple_stmt_iterator *gsi,
3166 gimple *stmt)
3167{
3168 tree op0 = gimple_assign_rhs1 (stmt);
3169 tree op1 = gimple_assign_rhs2 (stmt);
3170 bool sop = false;
3171 tree val;
3172
3173 val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3174 (LE_EXPR, op0, op1, &sop));
3175 if (!val)
3176 {
3177 sop = false;
3178 val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges
3179 (LT_EXPR, op0, op1, &sop));
3180 }
3181
3182 if (val)
3183 {
3184 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3185 {
3186 location_t location;
3187
3188 if (!gimple_has_location (stmt))
3189 location = input_location;
3190 else
3191 location = gimple_location (stmt);
3192 warning_at (location, OPT_Wstrict_overflow,
3193 "assuming signed overflow does not occur when "
3194 "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>");
3195 }
3196
3197 /* VAL == TRUE -> OP0 < or <= op1
3198 VAL == FALSE -> OP0 > or >= op1. */
3199 tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
3200 == integer_zerop (val)) ? op0 : op1;
3201 gimple_assign_set_rhs_from_tree (gsi, res);
3202 return true;
3203 }
3204
3205 return false;
3206}
3207
3208/* If the operand to an ABS_EXPR is >= 0, then eliminate the
3209 ABS_EXPR. If the operand is <= 0, then simplify the
3210 ABS_EXPR into a NEGATE_EXPR. */
3211
3212bool
3213vr_values::simplify_abs_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
3214{
3215 tree op = gimple_assign_rhs1 (stmt);
3216 value_range *vr = get_value_range (op);
3217
3218 if (vr)
3219 {
3220 tree val = NULL;
3221 bool sop = false;
3222
3223 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop);
3224 if (!val)
3225 {
3226 /* The range is neither <= 0 nor > 0. Now see if it is
3227 either < 0 or >= 0. */
3228 sop = false;
3229 val = compare_range_with_value (LT_EXPR, vr, integer_zero_node,
3230 &sop);
3231 }
3232
3233 if (val)
3234 {
3235 if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
3236 {
3237 location_t location;
3238
3239 if (!gimple_has_location (stmt))
3240 location = input_location;
3241 else
3242 location = gimple_location (stmt);
3243 warning_at (location, OPT_Wstrict_overflow,
3244 "assuming signed overflow does not occur when "
3245 "simplifying %<abs (X)%> to %<X%> or %<-X%>");
3246 }
3247
3248 gimple_assign_set_rhs1 (stmt, op);
3249 if (integer_zerop (val))
3250 gimple_assign_set_rhs_code (stmt, SSA_NAME);
3251 else
3252 gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
3253 update_stmt (stmt);
3254 fold_stmt (gsi, follow_single_use_edges);
3255 return true;
3256 }
3257 }
3258
3259 return false;
3260}
3261
3262/* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
3263 If all the bits that are being cleared by & are already
3264 known to be zero from VR, or all the bits that are being
3265 set by | are already known to be one from VR, the bit
3266 operation is redundant. */
3267
3268bool
3269vr_values::simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi,
3270 gimple *stmt)
3271{
3272 tree op0 = gimple_assign_rhs1 (stmt);
3273 tree op1 = gimple_assign_rhs2 (stmt);
3274 tree op = NULL_TREE;
3275 value_range vr0 = VR_INITIALIZER;
3276 value_range vr1 = VR_INITIALIZER;
3277 wide_int may_be_nonzero0, may_be_nonzero1;
3278 wide_int must_be_nonzero0, must_be_nonzero1;
3279 wide_int mask;
3280
3281 if (TREE_CODE (op0) == SSA_NAME)
3282 vr0 = *(get_value_range (op0));
3283 else if (is_gimple_min_invariant (op0))
3284 set_value_range_to_value (&vr0, op0, NULL);
3285 else
3286 return false;
3287
3288 if (TREE_CODE (op1) == SSA_NAME)
3289 vr1 = *(get_value_range (op1));
3290 else if (is_gimple_min_invariant (op1))
3291 set_value_range_to_value (&vr1, op1, NULL);
3292 else
3293 return false;
3294
3295 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op0), &vr0, &may_be_nonzero0,
3296 &must_be_nonzero0))
3297 return false;
3298 if (!zero_nonzero_bits_from_vr (TREE_TYPE (op1), &vr1, &may_be_nonzero1,
3299 &must_be_nonzero1))
3300 return false;
3301
3302 switch (gimple_assign_rhs_code (stmt))
3303 {
3304 case BIT_AND_EXPR:
3305 mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
3306 if (mask == 0)
3307 {
3308 op = op0;
3309 break;
3310 }
3311 mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
3312 if (mask == 0)
3313 {
3314 op = op1;
3315 break;
3316 }
3317 break;
3318 case BIT_IOR_EXPR:
3319 mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
3320 if (mask == 0)
3321 {
3322 op = op1;
3323 break;
3324 }
3325 mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
3326 if (mask == 0)
3327 {
3328 op = op0;
3329 break;
3330 }
3331 break;
3332 default:
3333 gcc_unreachable ();
3334 }
3335
3336 if (op == NULL_TREE)
3337 return false;
3338
3339 gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op);
3340 update_stmt (gsi_stmt (*gsi));
3341 return true;
3342}
3343
3344/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
3345 a known value range VR.
3346
3347 If there is one and only one value which will satisfy the
3348 conditional, then return that value. Else return NULL.
3349
3350 If signed overflow must be undefined for the value to satisfy
3351 the conditional, then set *STRICT_OVERFLOW_P to true. */
3352
3353static tree
3354test_for_singularity (enum tree_code cond_code, tree op0,
3355 tree op1, value_range *vr)
3356{
3357 tree min = NULL;
3358 tree max = NULL;
3359
3360 /* Extract minimum/maximum values which satisfy the conditional as it was
3361 written. */
3362 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
3363 {
3364 min = TYPE_MIN_VALUE (TREE_TYPE (op0));
3365
3366 max = op1;
3367 if (cond_code == LT_EXPR)
3368 {
3369 tree one = build_int_cst (TREE_TYPE (op0), 1);
3370 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
3371 /* Signal to compare_values_warnv this expr doesn't overflow. */
3372 if (EXPR_P (max))
3373 TREE_NO_WARNING (max) = 1;
3374 }
3375 }
3376 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
3377 {
3378 max = TYPE_MAX_VALUE (TREE_TYPE (op0));
3379
3380 min = op1;
3381 if (cond_code == GT_EXPR)
3382 {
3383 tree one = build_int_cst (TREE_TYPE (op0), 1);
3384 min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
3385 /* Signal to compare_values_warnv this expr doesn't overflow. */
3386 if (EXPR_P (min))
3387 TREE_NO_WARNING (min) = 1;
3388 }
3389 }
3390
3391 /* Now refine the minimum and maximum values using any
3392 value range information we have for op0. */
3393 if (min && max)
3394 {
3395 if (compare_values (vr->min, min) == 1)
3396 min = vr->min;
3397 if (compare_values (vr->max, max) == -1)
3398 max = vr->max;
3399
3400 /* If the new min/max values have converged to a single value,
3401 then there is only one value which can satisfy the condition,
3402 return that value. */
3403 if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
3404 return min;
3405 }
3406 return NULL;
3407}
3408
3409/* Return whether the value range *VR fits in an integer type specified
3410 by PRECISION and UNSIGNED_P. */
3411
3412static bool
3413range_fits_type_p (value_range *vr, unsigned dest_precision, signop dest_sgn)
3414{
3415 tree src_type;
3416 unsigned src_precision;
3417 widest_int tem;
3418 signop src_sgn;
3419
3420 /* We can only handle integral and pointer types. */
3421 src_type = TREE_TYPE (vr->min);
3422 if (!INTEGRAL_TYPE_P (src_type)
3423 && !POINTER_TYPE_P (src_type))
3424 return false;
3425
3426 /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
3427 and so is an identity transform. */
3428 src_precision = TYPE_PRECISION (TREE_TYPE (vr->min));
3429 src_sgn = TYPE_SIGN (src_type);
3430 if ((src_precision < dest_precision
3431 && !(dest_sgn == UNSIGNED && src_sgn == SIGNED))
3432 || (src_precision == dest_precision && src_sgn == dest_sgn))
3433 return true;
3434
3435 /* Now we can only handle ranges with constant bounds. */
3436 if (vr->type != VR_RANGE
3437 || TREE_CODE (vr->min) != INTEGER_CST
3438 || TREE_CODE (vr->max) != INTEGER_CST)
3439 return false;
3440
3441 /* For sign changes, the MSB of the wide_int has to be clear.
3442 An unsigned value with its MSB set cannot be represented by
3443 a signed wide_int, while a negative value cannot be represented
3444 by an unsigned wide_int. */
3445 if (src_sgn != dest_sgn
3446 && (wi::lts_p (wi::to_wide (vr->min), 0)
3447 || wi::lts_p (wi::to_wide (vr->max), 0)))
3448 return false;
3449
3450 /* Then we can perform the conversion on both ends and compare
3451 the result for equality. */
3452 tem = wi::ext (wi::to_widest (vr->min), dest_precision, dest_sgn);
3453 if (tem != wi::to_widest (vr->min))
3454 return false;
3455 tem = wi::ext (wi::to_widest (vr->max), dest_precision, dest_sgn);
3456 if (tem != wi::to_widest (vr->max))
3457 return false;
3458
3459 return true;
3460}
3461
3462/* Simplify a conditional using a relational operator to an equality
3463 test if the range information indicates only one value can satisfy
3464 the original conditional. */
3465
3466bool
3467vr_values::simplify_cond_using_ranges_1 (gcond *stmt)
3468{
3469 tree op0 = gimple_cond_lhs (stmt);
3470 tree op1 = gimple_cond_rhs (stmt);
3471 enum tree_code cond_code = gimple_cond_code (stmt);
3472
3473 if (cond_code != NE_EXPR
3474 && cond_code != EQ_EXPR
3475 && TREE_CODE (op0) == SSA_NAME
3476 && INTEGRAL_TYPE_P (TREE_TYPE (op0))
3477 && is_gimple_min_invariant (op1))
3478 {
3479 value_range *vr = get_value_range (op0);
3480
3481 /* If we have range information for OP0, then we might be
3482 able to simplify this conditional. */
3483 if (vr->type == VR_RANGE)
3484 {
3485 tree new_tree = test_for_singularity (cond_code, op0, op1, vr);
3486 if (new_tree)
3487 {
3488 if (dump_file)
3489 {
3490 fprintf (dump_file, "Simplified relational ");
3491 print_gimple_stmt (dump_file, stmt, 0);
3492 fprintf (dump_file, " into ");
3493 }
3494
3495 gimple_cond_set_code (stmt, EQ_EXPR);
3496 gimple_cond_set_lhs (stmt, op0);
3497 gimple_cond_set_rhs (stmt, new_tree);
3498
3499 update_stmt (stmt);
3500
3501 if (dump_file)
3502 {
3503 print_gimple_stmt (dump_file, stmt, 0);
3504 fprintf (dump_file, "\n");
3505 }
3506
3507 return true;
3508 }
3509
3510 /* Try again after inverting the condition. We only deal
3511 with integral types here, so no need to worry about
3512 issues with inverting FP comparisons. */
3513 new_tree = test_for_singularity
3514 (invert_tree_comparison (cond_code, false),
3515 op0, op1, vr);
3516 if (new_tree)
3517 {
3518 if (dump_file)
3519 {
3520 fprintf (dump_file, "Simplified relational ");
3521 print_gimple_stmt (dump_file, stmt, 0);
3522 fprintf (dump_file, " into ");
3523 }
3524
3525 gimple_cond_set_code (stmt, NE_EXPR);
3526 gimple_cond_set_lhs (stmt, op0);
3527 gimple_cond_set_rhs (stmt, new_tree);
3528
3529 update_stmt (stmt);
3530
3531 if (dump_file)
3532 {
3533 print_gimple_stmt (dump_file, stmt, 0);
3534 fprintf (dump_file, "\n");
3535 }
3536
3537 return true;
3538 }
3539 }
3540 }
3541 return false;
3542}
3543
3544/* STMT is a conditional at the end of a basic block.
3545
3546 If the conditional is of the form SSA_NAME op constant and the SSA_NAME
3547 was set via a type conversion, try to replace the SSA_NAME with the RHS
3548 of the type conversion. Doing so makes the conversion dead which helps
3549 subsequent passes. */
3550
3551void
3552vr_values::simplify_cond_using_ranges_2 (gcond *stmt)
3553{
3554 tree op0 = gimple_cond_lhs (stmt);
3555 tree op1 = gimple_cond_rhs (stmt);
3556
3557 /* If we have a comparison of an SSA_NAME (OP0) against a constant,
3558 see if OP0 was set by a type conversion where the source of
3559 the conversion is another SSA_NAME with a range that fits
3560 into the range of OP0's type.
3561
3562 If so, the conversion is redundant as the earlier SSA_NAME can be
3563 used for the comparison directly if we just massage the constant in the
3564 comparison. */
3565 if (TREE_CODE (op0) == SSA_NAME
3566 && TREE_CODE (op1) == INTEGER_CST)
3567 {
3568 gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
3569 tree innerop;
3570
3571 if (!is_gimple_assign (def_stmt)
3572 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
3573 return;
3574
3575 innerop = gimple_assign_rhs1 (def_stmt);
3576
3577 if (TREE_CODE (innerop) == SSA_NAME
3578 && !POINTER_TYPE_P (TREE_TYPE (innerop))
3579 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
3580 && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
3581 {
3582 value_range *vr = get_value_range (innerop);
3583
3584 if (range_int_cst_p (vr)
3585 && range_fits_type_p (vr,
3586 TYPE_PRECISION (TREE_TYPE (op0)),
3587 TYPE_SIGN (TREE_TYPE (op0)))
3588 && int_fits_type_p (op1, TREE_TYPE (innerop)))
3589 {
3590 tree newconst = fold_convert (TREE_TYPE (innerop), op1);
3591 gimple_cond_set_lhs (stmt, innerop);
3592 gimple_cond_set_rhs (stmt, newconst);
3593 update_stmt (stmt);
3594 if (dump_file && (dump_flags & TDF_DETAILS))
3595 {
3596 fprintf (dump_file, "Folded into: ");
3597 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3598 fprintf (dump_file, "\n");
3599 }
3600 }
3601 }
3602 }
3603}
3604
3605/* Simplify a switch statement using the value range of the switch
3606 argument. */
3607
3608bool
3609vr_values::simplify_switch_using_ranges (gswitch *stmt)
3610{
3611 tree op = gimple_switch_index (stmt);
3612 value_range *vr = NULL;
3613 bool take_default;
3614 edge e;
3615 edge_iterator ei;
3616 size_t i = 0, j = 0, n, n2;
3617 tree vec2;
3618 switch_update su;
3619 size_t k = 1, l = 0;
3620
3621 if (TREE_CODE (op) == SSA_NAME)
3622 {
3623 vr = get_value_range (op);
3624
3625 /* We can only handle integer ranges. */
3626 if ((vr->type != VR_RANGE
3627 && vr->type != VR_ANTI_RANGE)
3628 || symbolic_range_p (vr))
3629 return false;
3630
3631 /* Find case label for min/max of the value range. */
3632 take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
3633 }
3634 else if (TREE_CODE (op) == INTEGER_CST)
3635 {
3636 take_default = !find_case_label_index (stmt, 1, op, &i);
3637 if (take_default)
3638 {
3639 i = 1;
3640 j = 0;
3641 }
3642 else
3643 {
3644 j = i;
3645 }
3646 }
3647 else
3648 return false;
3649
3650 n = gimple_switch_num_labels (stmt);
3651
3652 /* We can truncate the case label ranges that partially overlap with OP's
3653 value range. */
3654 size_t min_idx = 1, max_idx = 0;
3655 if (vr != NULL)
3656 find_case_label_range (stmt, vr->min, vr->max, &min_idx, &max_idx);
3657 if (min_idx <= max_idx)
3658 {
3659 tree min_label = gimple_switch_label (stmt, min_idx);
3660 tree max_label = gimple_switch_label (stmt, max_idx);
3661
3662 /* Avoid changing the type of the case labels when truncating. */
3663 tree case_label_type = TREE_TYPE (CASE_LOW (min_label));
3664 tree vr_min = fold_convert (case_label_type, vr->min);
3665 tree vr_max = fold_convert (case_label_type, vr->max);
3666
3667 if (vr->type == VR_RANGE)
3668 {
3669 /* If OP's value range is [2,8] and the low label range is
3670 0 ... 3, truncate the label's range to 2 .. 3. */
3671 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3672 && CASE_HIGH (min_label) != NULL_TREE
3673 && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
3674 CASE_LOW (min_label) = vr_min;
3675
3676 /* If OP's value range is [2,8] and the high label range is
3677 7 ... 10, truncate the label's range to 7 .. 8. */
3678 if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
3679 && CASE_HIGH (max_label) != NULL_TREE
3680 && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
3681 CASE_HIGH (max_label) = vr_max;
3682 }
3683 else if (vr->type == VR_ANTI_RANGE)
3684 {
3685 tree one_cst = build_one_cst (case_label_type);
3686
3687 if (min_label == max_label)
3688 {
3689 /* If OP's value range is ~[7,8] and the label's range is
3690 7 ... 10, truncate the label's range to 9 ... 10. */
3691 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) == 0
3692 && CASE_HIGH (min_label) != NULL_TREE
3693 && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) > 0)
3694 CASE_LOW (min_label)
3695 = int_const_binop (PLUS_EXPR, vr_max, one_cst);
3696
3697 /* If OP's value range is ~[7,8] and the label's range is
3698 5 ... 8, truncate the label's range to 5 ... 6. */
3699 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3700 && CASE_HIGH (min_label) != NULL_TREE
3701 && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) == 0)
3702 CASE_HIGH (min_label)
3703 = int_const_binop (MINUS_EXPR, vr_min, one_cst);
3704 }
3705 else
3706 {
3707 /* If OP's value range is ~[2,8] and the low label range is
3708 0 ... 3, truncate the label's range to 0 ... 1. */
3709 if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0
3710 && CASE_HIGH (min_label) != NULL_TREE
3711 && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0)
3712 CASE_HIGH (min_label)
3713 = int_const_binop (MINUS_EXPR, vr_min, one_cst);
3714
3715 /* If OP's value range is ~[2,8] and the high label range is
3716 7 ... 10, truncate the label's range to 9 ... 10. */
3717 if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0
3718 && CASE_HIGH (max_label) != NULL_TREE
3719 && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0)
3720 CASE_LOW (max_label)
3721 = int_const_binop (PLUS_EXPR, vr_max, one_cst);
3722 }
3723 }
3724
3725 /* Canonicalize singleton case ranges. */
3726 if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label)))
3727 CASE_HIGH (min_label) = NULL_TREE;
3728 if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label)))
3729 CASE_HIGH (max_label) = NULL_TREE;
3730 }
3731
3732 /* We can also eliminate case labels that lie completely outside OP's value
3733 range. */
3734
3735 /* Bail out if this is just all edges taken. */
3736 if (i == 1
3737 && j == n - 1
3738 && take_default)
3739 return false;
3740
3741 /* Build a new vector of taken case labels. */
3742 vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default);
3743 n2 = 0;
3744
3745 /* Add the default edge, if necessary. */
3746 if (take_default)
3747 TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt);
3748
3749 for (; i <= j; ++i, ++n2)
3750 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i);
3751
3752 for (; k <= l; ++k, ++n2)
3753 TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k);
3754
3755 /* Mark needed edges. */
3756 for (i = 0; i < n2; ++i)
3757 {
3758 e = find_edge (gimple_bb (stmt),
3759 label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
3760 e->aux = (void *)-1;
3761 }
3762
3763 /* Queue not needed edges for later removal. */
3764 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
3765 {
3766 if (e->aux == (void *)-1)
3767 {
3768 e->aux = NULL;
3769 continue;
3770 }
3771
3772 if (dump_file && (dump_flags & TDF_DETAILS))
3773 {
3774 fprintf (dump_file, "removing unreachable case label\n");
3775 }
3776 to_remove_edges.safe_push (e);
3777 e->flags &= ~EDGE_EXECUTABLE;
3778 }
3779
3780 /* And queue an update for the stmt. */
3781 su.stmt = stmt;
3782 su.vec = vec2;
3783 to_update_switch_stmts.safe_push (su);
3784 return false;
3785}
3786
3787/* Simplify an integral conversion from an SSA name in STMT. */
3788
3789static bool
3790simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
3791{
3792 tree innerop, middleop, finaltype;
3793 gimple *def_stmt;
3794 signop inner_sgn, middle_sgn, final_sgn;
3795 unsigned inner_prec, middle_prec, final_prec;
3796 widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
3797
3798 finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
3799 if (!INTEGRAL_TYPE_P (finaltype))
3800 return false;
3801 middleop = gimple_assign_rhs1 (stmt);
3802 def_stmt = SSA_NAME_DEF_STMT (middleop);
3803 if (!is_gimple_assign (def_stmt)
3804 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
3805 return false;
3806 innerop = gimple_assign_rhs1 (def_stmt);
3807 if (TREE_CODE (innerop) != SSA_NAME
3808 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
3809 return false;
3810
3811 /* Get the value-range of the inner operand. Use get_range_info in
3812 case innerop was created during substitute-and-fold. */
3813 wide_int imin, imax;
3814 if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop))
3815 || get_range_info (innerop, &imin, &imax) != VR_RANGE)
3816 return false;
3817 innermin = widest_int::from (imin, TYPE_SIGN (TREE_TYPE (innerop)));
3818 innermax = widest_int::from (imax, TYPE_SIGN (TREE_TYPE (innerop)));
3819
3820 /* Simulate the conversion chain to check if the result is equal if
3821 the middle conversion is removed. */
3822 inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
3823 middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
3824 final_prec = TYPE_PRECISION (finaltype);
3825
3826 /* If the first conversion is not injective, the second must not
3827 be widening. */
3828 if (wi::gtu_p (innermax - innermin,
3829 wi::mask <widest_int> (middle_prec, false))
3830 && middle_prec < final_prec)
3831 return false;
3832 /* We also want a medium value so that we can track the effect that
3833 narrowing conversions with sign change have. */
3834 inner_sgn = TYPE_SIGN (TREE_TYPE (innerop));
3835 if (inner_sgn == UNSIGNED)
3836 innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false);
3837 else
3838 innermed = 0;
3839 if (wi::cmp (innermin, innermed, inner_sgn) >= 0
3840 || wi::cmp (innermed, innermax, inner_sgn) >= 0)
3841 innermed = innermin;
3842
3843 middle_sgn = TYPE_SIGN (TREE_TYPE (middleop));
3844 middlemin = wi::ext (innermin, middle_prec, middle_sgn);
3845 middlemed = wi::ext (innermed, middle_prec, middle_sgn);
3846 middlemax = wi::ext (innermax, middle_prec, middle_sgn);
3847
3848 /* Require that the final conversion applied to both the original
3849 and the intermediate range produces the same result. */
3850 final_sgn = TYPE_SIGN (finaltype);
3851 if (wi::ext (middlemin, final_prec, final_sgn)
3852 != wi::ext (innermin, final_prec, final_sgn)
3853 || wi::ext (middlemed, final_prec, final_sgn)
3854 != wi::ext (innermed, final_prec, final_sgn)
3855 || wi::ext (middlemax, final_prec, final_sgn)
3856 != wi::ext (innermax, final_prec, final_sgn))
3857 return false;
3858
3859 gimple_assign_set_rhs1 (stmt, innerop);
3860 fold_stmt (gsi, follow_single_use_edges);
3861 return true;
3862}
3863
3864/* Simplify a conversion from integral SSA name to float in STMT. */
3865
3866bool
3867vr_values::simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi,
3868 gimple *stmt)
3869{
3870 tree rhs1 = gimple_assign_rhs1 (stmt);
3871 value_range *vr = get_value_range (rhs1);
3872 scalar_float_mode fltmode
3873 = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
3874 scalar_int_mode mode;
3875 tree tem;
3876 gassign *conv;
3877
3878 /* We can only handle constant ranges. */
3879 if (vr->type != VR_RANGE
3880 || TREE_CODE (vr->min) != INTEGER_CST
3881 || TREE_CODE (vr->max) != INTEGER_CST)
3882 return false;
3883
3884 /* First check if we can use a signed type in place of an unsigned. */
3885 scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1));
3886 if (TYPE_UNSIGNED (TREE_TYPE (rhs1))
3887 && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing
3888 && range_fits_type_p (vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED))
3889 mode = rhs_mode;
3890 /* If we can do the conversion in the current input mode do nothing. */
3891 else if (can_float_p (fltmode, rhs_mode,
3892 TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing)
3893 return false;
3894 /* Otherwise search for a mode we can use, starting from the narrowest
3895 integer mode available. */
3896 else
3897 {
3898 mode = NARROWEST_INT_MODE;
3899 for (;;)
3900 {
3901 /* If we cannot do a signed conversion to float from mode
3902 or if the value-range does not fit in the signed type
3903 try with a wider mode. */
3904 if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing
3905 && range_fits_type_p (vr, GET_MODE_PRECISION (mode), SIGNED))
3906 break;
3907
3908 /* But do not widen the input. Instead leave that to the
3909 optabs expansion code. */
3910 if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
3911 || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1)))
3912 return false;
3913 }
3914 }
3915
3916 /* It works, insert a truncation or sign-change before the
3917 float conversion. */
3918 tem = make_ssa_name (build_nonstandard_integer_type
3919 (GET_MODE_PRECISION (mode), 0));
3920 conv = gimple_build_assign (tem, NOP_EXPR, rhs1);
3921 gsi_insert_before (gsi, conv, GSI_SAME_STMT);
3922 gimple_assign_set_rhs1 (stmt, tem);
3923 fold_stmt (gsi, follow_single_use_edges);
3924
3925 return true;
3926}
3927
3928/* Simplify an internal fn call using ranges if possible. */
3929
3930bool
3931vr_values::simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi,
3932 gimple *stmt)
3933{
3934 enum tree_code subcode;
3935 bool is_ubsan = false;
3936 bool ovf = false;
3937 switch (gimple_call_internal_fn (stmt))
3938 {
3939 case IFN_UBSAN_CHECK_ADD:
3940 subcode = PLUS_EXPR;
3941 is_ubsan = true;
3942 break;
3943 case IFN_UBSAN_CHECK_SUB:
3944 subcode = MINUS_EXPR;
3945 is_ubsan = true;
3946 break;
3947 case IFN_UBSAN_CHECK_MUL:
3948 subcode = MULT_EXPR;
3949 is_ubsan = true;
3950 break;
3951 case IFN_ADD_OVERFLOW:
3952 subcode = PLUS_EXPR;
3953 break;
3954 case IFN_SUB_OVERFLOW:
3955 subcode = MINUS_EXPR;
3956 break;
3957 case IFN_MUL_OVERFLOW:
3958 subcode = MULT_EXPR;
3959 break;
3960 default:
3961 return false;
3962 }
3963
3964 tree op0 = gimple_call_arg (stmt, 0);
3965 tree op1 = gimple_call_arg (stmt, 1);
3966 tree type;
3967 if (is_ubsan)
3968 {
3969 type = TREE_TYPE (op0);
3970 if (VECTOR_TYPE_P (type))
3971 return false;
3972 }
3973 else if (gimple_call_lhs (stmt) == NULL_TREE)
3974 return false;
3975 else
3976 type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt)));
3977 if (!check_for_binary_op_overflow (subcode, type, op0, op1, &ovf)
3978 || (is_ubsan && ovf))
3979 return false;
3980
3981 gimple *g;
3982 location_t loc = gimple_location (stmt);
3983 if (is_ubsan)
3984 g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1);
3985 else
3986 {
3987 int prec = TYPE_PRECISION (type);
3988 tree utype = type;
3989 if (ovf
3990 || !useless_type_conversion_p (type, TREE_TYPE (op0))
3991 || !useless_type_conversion_p (type, TREE_TYPE (op1)))
3992 utype = build_nonstandard_integer_type (prec, 1);
3993 if (TREE_CODE (op0) == INTEGER_CST)
3994 op0 = fold_convert (utype, op0);
3995 else if (!useless_type_conversion_p (utype, TREE_TYPE (op0)))
3996 {
3997 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0);
3998 gimple_set_location (g, loc);
3999 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4000 op0 = gimple_assign_lhs (g);
4001 }
4002 if (TREE_CODE (op1) == INTEGER_CST)
4003 op1 = fold_convert (utype, op1);
4004 else if (!useless_type_conversion_p (utype, TREE_TYPE (op1)))
4005 {
4006 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1);
4007 gimple_set_location (g, loc);
4008 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4009 op1 = gimple_assign_lhs (g);
4010 }
4011 g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1);
4012 gimple_set_location (g, loc);
4013 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4014 if (utype != type)
4015 {
4016 g = gimple_build_assign (make_ssa_name (type), NOP_EXPR,
4017 gimple_assign_lhs (g));
4018 gimple_set_location (g, loc);
4019 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4020 }
4021 g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR,
4022 gimple_assign_lhs (g),
4023 build_int_cst (type, ovf));
4024 }
4025 gimple_set_location (g, loc);
4026 gsi_replace (gsi, g, false);
4027 return true;
4028}
4029
4030/* Return true if VAR is a two-valued variable. Set a and b with the
4031 two-values when it is true. Return false otherwise. */
4032
4033bool
4034vr_values::two_valued_val_range_p (tree var, tree *a, tree *b)
4035{
4036 value_range *vr = get_value_range (var);
4037 if ((vr->type != VR_RANGE
4038 && vr->type != VR_ANTI_RANGE)
4039 || TREE_CODE (vr->min) != INTEGER_CST
4040 || TREE_CODE (vr->max) != INTEGER_CST)
4041 return false;
4042
4043 if (vr->type == VR_RANGE
4044 && wi::to_wide (vr->max) - wi::to_wide (vr->min) == 1)
4045 {
4046 *a = vr->min;
4047 *b = vr->max;
4048 return true;
4049 }
4050
4051 /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
4052 if (vr->type == VR_ANTI_RANGE
4053 && (wi::to_wide (vr->min)
4054 - wi::to_wide (vrp_val_min (TREE_TYPE (var)))) == 1
4055 && (wi::to_wide (vrp_val_max (TREE_TYPE (var)))
4056 - wi::to_wide (vr->max)) == 1)
4057 {
4058 *a = vrp_val_min (TREE_TYPE (var));
4059 *b = vrp_val_max (TREE_TYPE (var));
4060 return true;
4061 }
4062
4063 return false;
4064}
4065
4066/* Simplify STMT using ranges if possible. */
4067
4068bool
4069vr_values::simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
4070{
4071 gimple *stmt = gsi_stmt (*gsi);
4072 if (is_gimple_assign (stmt))
4073 {
4074 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
4075 tree rhs1 = gimple_assign_rhs1 (stmt);
4076 tree rhs2 = gimple_assign_rhs2 (stmt);
4077 tree lhs = gimple_assign_lhs (stmt);
4078 tree val1 = NULL_TREE, val2 = NULL_TREE;
4079 use_operand_p use_p;
4080 gimple *use_stmt;
4081
4082 /* Convert:
4083 LHS = CST BINOP VAR
4084 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4085 To:
4086 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
4087
4088 Also handles:
4089 LHS = VAR BINOP CST
4090 Where VAR is two-valued and LHS is used in GIMPLE_COND only
4091 To:
4092 LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
4093
4094 if (TREE_CODE_CLASS (rhs_code) == tcc_binary
4095 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
4096 && ((TREE_CODE (rhs1) == INTEGER_CST
4097 && TREE_CODE (rhs2) == SSA_NAME)
4098 || (TREE_CODE (rhs2) == INTEGER_CST
4099 && TREE_CODE (rhs1) == SSA_NAME))
4100 && single_imm_use (lhs, &use_p, &use_stmt)
4101 && gimple_code (use_stmt) == GIMPLE_COND)
4102
4103 {
4104 tree new_rhs1 = NULL_TREE;
4105 tree new_rhs2 = NULL_TREE;
4106 tree cmp_var = NULL_TREE;
4107
4108 if (TREE_CODE (rhs2) == SSA_NAME
4109 && two_valued_val_range_p (rhs2, &val1, &val2))
4110 {
4111 /* Optimize RHS1 OP [VAL1, VAL2]. */
4112 new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
4113 new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
4114 cmp_var = rhs2;
4115 }
4116 else if (TREE_CODE (rhs1) == SSA_NAME
4117 && two_valued_val_range_p (rhs1, &val1, &val2))
4118