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