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