1 /* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2021 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "insn-codes.h"
31 #include "gimple-pretty-print.h"
32 #include "gimple-iterator.h"
33 #include "optabs-tree.h"
34 #include "gimple-fold.h"
36 #include "fold-const.h"
39 #include "fold-const.h"
40 #include "case-cfn-macros.h"
41 #include "omp-general.h"
43 #include "tree-ssa-loop.h"
44 #include "tree-scalar-evolution.h"
46 #include "alloc-pool.h"
47 #include "vr-values.h"
48 #include "gimple-range.h"
51 // Adjust the range for a pointer difference where the operands came
54 // This notices the following sequence:
56 // def = __builtin_memchr (arg, 0, sz)
59 // The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
62 adjust_pointer_diff_expr (irange
&res
, const gimple
*diff_stmt
)
64 tree op0
= gimple_assign_rhs1 (diff_stmt
);
65 tree op1
= gimple_assign_rhs2 (diff_stmt
);
66 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
67 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
70 if (TREE_CODE (op0
) == SSA_NAME
71 && TREE_CODE (op1
) == SSA_NAME
72 && (call
= SSA_NAME_DEF_STMT (op0
))
73 && is_gimple_call (call
)
74 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
75 && TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
76 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
77 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
78 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
79 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
80 && vrp_operand_equal_p (op1
, gimple_call_arg (call
, 0))
81 && integer_zerop (gimple_call_arg (call
, 1)))
83 tree max
= vrp_val_max (ptrdiff_type_node
);
84 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
85 tree expr_type
= gimple_expr_type (diff_stmt
);
86 tree range_min
= build_zero_cst (expr_type
);
87 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
88 int_range
<2> r (range_min
, range_max
);
93 // This function looks for situations when walking the use/def chains
94 // may provide additonal contextual range information not exposed on
95 // this statement. Like knowing the IMAGPART return value from a
96 // builtin function is a boolean result.
98 // We should rework how we're called, as we have an op_unknown entry
99 // for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this
100 // function gets called.
103 gimple_range_adjustment (irange
&res
, const gimple
*stmt
)
105 switch (gimple_expr_code (stmt
))
107 case POINTER_DIFF_EXPR
:
108 adjust_pointer_diff_expr (res
, stmt
);
113 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
114 if (TREE_CODE (name
) == SSA_NAME
)
116 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
117 if (def_stmt
&& is_gimple_call (def_stmt
)
118 && gimple_call_internal_p (def_stmt
))
120 switch (gimple_call_internal_fn (def_stmt
))
122 case IFN_ADD_OVERFLOW
:
123 case IFN_SUB_OVERFLOW
:
124 case IFN_MUL_OVERFLOW
:
125 case IFN_ATOMIC_COMPARE_EXCHANGE
:
128 r
.set_varying (boolean_type_node
);
129 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
130 range_cast (r
, type
);
146 // Return a range in R for the tree EXPR. Return true if a range is
147 // representable, and UNDEFINED/false if not.
150 get_tree_range (irange
&r
, tree expr
)
156 type
= TREE_TYPE (expr
);
158 // Return false if the type isn't suported.
159 if (!irange::supports_type_p (type
))
165 switch (TREE_CODE (expr
))
168 if (TREE_OVERFLOW_P (expr
))
169 expr
= drop_tree_overflow (expr
);
174 r
= gimple_range_global (expr
);
179 // Handle &var which can show up in phi arguments.
181 if (tree_single_nonzero_warnv_p (expr
, &ov
))
183 r
= range_nonzero (type
);
192 r
.set_varying (type
);
196 // Fold this unary statement using R1 as operand1's range, returning
197 // the result in RES. Return false if the operation fails.
200 gimple_range_fold (irange
&res
, const gimple
*stmt
, const irange
&r1
)
202 gcc_checking_assert (gimple_range_handler (stmt
));
204 tree type
= gimple_expr_type (stmt
);
205 // Unary SSA operations require the LHS type as the second range.
206 int_range
<2> r2 (type
);
208 return gimple_range_fold (res
, stmt
, r1
, r2
);
211 // Fold this binary statement using R1 and R2 as the operands ranges,
212 // returning the result in RES. Return false if the operation fails.
215 gimple_range_fold (irange
&res
, const gimple
*stmt
,
216 const irange
&r1
, const irange
&r2
)
218 gcc_checking_assert (gimple_range_handler (stmt
));
220 gimple_range_handler (stmt
)->fold_range (res
, gimple_expr_type (stmt
),
223 // If there are any gimple lookups, do those now.
224 gimple_range_adjustment (res
, stmt
);
228 // Return the base of the RHS of an assignment.
231 gimple_range_base_of_assignment (const gimple
*stmt
)
233 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
234 tree op1
= gimple_assign_rhs1 (stmt
);
235 if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
236 return get_base_address (TREE_OPERAND (op1
, 0));
240 // Return the first operand of this statement if it is a valid operand
241 // supported by ranges, otherwise return NULL_TREE. Special case is
242 // &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr.
245 gimple_range_operand1 (const gimple
*stmt
)
247 gcc_checking_assert (gimple_range_handler (stmt
));
249 switch (gimple_code (stmt
))
252 return gimple_cond_lhs (stmt
);
255 tree base
= gimple_range_base_of_assignment (stmt
);
256 if (base
&& TREE_CODE (base
) == MEM_REF
)
258 // If the base address is an SSA_NAME, we return it
259 // here. This allows processing of the range of that
260 // name, while the rest of the expression is simply
261 // ignored. The code in range_ops will see the
262 // ADDR_EXPR and do the right thing.
263 tree ssa
= TREE_OPERAND (base
, 0);
264 if (TREE_CODE (ssa
) == SSA_NAME
)
275 // Return the second operand of statement STMT, otherwise return NULL_TREE.
278 gimple_range_operand2 (const gimple
*stmt
)
280 gcc_checking_assert (gimple_range_handler (stmt
));
282 switch (gimple_code (stmt
))
285 return gimple_cond_rhs (stmt
);
287 if (gimple_num_ops (stmt
) >= 3)
288 return gimple_assign_rhs2 (stmt
);
295 // Calculate what we can determine of the range of this unary
296 // statement's operand if the lhs of the expression has the range
297 // LHS_RANGE. Return false if nothing can be determined.
300 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
, const irange
&lhs_range
)
302 gcc_checking_assert (gimple_num_ops (stmt
) < 3);
304 // An empty range is viral.
305 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
306 if (lhs_range
.undefined_p ())
311 // Unary operations require the type of the first operand in the
312 // second range position.
313 int_range
<2> type_range (type
);
314 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
318 // Calculate what we can determine of the range of this statement's
319 // first operand if the lhs of the expression has the range LHS_RANGE
320 // and the second operand has the range OP2_RANGE. Return false if
321 // nothing can be determined.
324 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
,
325 const irange
&lhs_range
, const irange
&op2_range
)
327 // Unary operation are allowed to pass a range in for second operand
328 // as there are often additional restrictions beyond the type which
329 // can be imposed. See operator_cast::op1_range().
330 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
331 // An empty range is viral.
332 if (op2_range
.undefined_p () || lhs_range
.undefined_p ())
337 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
341 // Calculate what we can determine of the range of this statement's
342 // second operand if the lhs of the expression has the range LHS_RANGE
343 // and the first operand has the range OP1_RANGE. Return false if
344 // nothing can be determined.
347 gimple_range_calc_op2 (irange
&r
, const gimple
*stmt
,
348 const irange
&lhs_range
, const irange
&op1_range
)
350 tree type
= TREE_TYPE (gimple_range_operand2 (stmt
));
351 // An empty range is viral.
352 if (op1_range
.undefined_p () || lhs_range
.undefined_p ())
357 return gimple_range_handler (stmt
)->op2_range (r
, type
, lhs_range
,
361 // Calculate a range for statement S and return it in R. If NAME is provided it
362 // represents the SSA_NAME on the LHS of the statement. It is only required
363 // if there is more than one lhs/output. If a range cannot
364 // be calculated, return false.
367 gimple_ranger::calc_stmt (irange
&r
, gimple
*s
, tree name
)
370 // If name is specified, make sure it is an LHS of S.
371 gcc_checking_assert (name
? SSA_NAME_DEF_STMT (name
) == s
: true);
373 if (gimple_range_handler (s
))
374 res
= range_of_range_op (r
, s
);
375 else if (is_a
<gphi
*>(s
))
376 res
= range_of_phi (r
, as_a
<gphi
*> (s
));
377 else if (is_a
<gcall
*>(s
))
378 res
= range_of_call (r
, as_a
<gcall
*> (s
));
379 else if (is_a
<gassign
*> (s
) && gimple_assign_rhs_code (s
) == COND_EXPR
)
380 res
= range_of_cond_expr (r
, as_a
<gassign
*> (s
));
384 // If no name is specified, try the expression kind.
387 tree t
= gimple_expr_type (s
);
388 if (!irange::supports_type_p (t
))
393 if (!gimple_range_ssa_p (name
))
395 // We don't understand the stmt, so return the global range.
396 r
= gimple_range_global (name
);
400 if (r
.undefined_p ())
403 // We sometimes get compatible types copied from operands, make sure
404 // the correct type is being returned.
405 if (name
&& TREE_TYPE (name
) != r
.type ())
407 gcc_checking_assert (range_compatible_p (r
.type (), TREE_TYPE (name
)));
408 range_cast (r
, TREE_TYPE (name
));
413 // Calculate a range for range_op statement S and return it in R. If any
414 // If a range cannot be calculated, return false.
417 gimple_ranger::range_of_range_op (irange
&r
, gimple
*s
)
419 int_range_max range1
, range2
;
420 tree lhs
= gimple_get_lhs (s
);
421 tree type
= gimple_expr_type (s
);
422 gcc_checking_assert (irange::supports_type_p (type
));
424 tree op1
= gimple_range_operand1 (s
);
425 tree op2
= gimple_range_operand2 (s
);
429 // Register potential dependencies for stale value tracking.
430 m_cache
.register_dependency (lhs
, op1
);
431 m_cache
.register_dependency (lhs
, op2
);
434 if (gimple_code (s
) == GIMPLE_ASSIGN
435 && gimple_assign_rhs_code (s
) == ADDR_EXPR
)
436 return range_of_address (r
, s
);
438 if (range_of_expr (range1
, op1
, s
))
441 return gimple_range_fold (r
, s
, range1
);
443 if (range_of_expr (range2
, op2
, s
))
444 return gimple_range_fold (r
, s
, range1
, range2
);
446 r
.set_varying (type
);
450 // Calculate the range of an assignment containing an ADDR_EXPR.
451 // Return the range in R.
452 // If a range cannot be calculated, set it to VARYING and return true.
455 gimple_ranger::range_of_address (irange
&r
, gimple
*stmt
)
457 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
458 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
);
460 bool strict_overflow_p
;
461 tree expr
= gimple_assign_rhs1 (stmt
);
462 poly_int64 bitsize
, bitpos
;
465 int unsignedp
, reversep
, volatilep
;
466 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
467 &bitpos
, &offset
, &mode
, &unsignedp
,
468 &reversep
, &volatilep
);
471 if (base
!= NULL_TREE
472 && TREE_CODE (base
) == MEM_REF
473 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
475 tree ssa
= TREE_OPERAND (base
, 0);
476 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (ssa
)));
477 range_of_expr (r
, ssa
, stmt
);
478 range_cast (r
, TREE_TYPE (gimple_assign_rhs1 (stmt
)));
480 poly_offset_int off
= 0;
481 bool off_cst
= false;
482 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
484 off
= mem_ref_offset (base
);
486 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
488 off
<<= LOG2_BITS_PER_UNIT
;
492 /* If &X->a is equal to X, the range of X is the result. */
493 if (off_cst
&& known_eq (off
, 0))
495 else if (flag_delete_null_pointer_checks
496 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
)))
498 /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
499 allow going from non-NULL pointer to NULL. */
500 if(!range_includes_zero_p (&r
))
503 /* If MEM_REF has a "positive" offset, consider it non-NULL
504 always, for -fdelete-null-pointer-checks also "negative"
505 ones. Punt for unknown offsets (e.g. variable ones). */
506 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
509 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
511 r
= range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
514 r
= int_range
<2> (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
519 if (tree_single_nonzero_warnv_p (expr
, &strict_overflow_p
))
521 r
= range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
525 // Otherwise return varying.
526 r
= int_range
<2> (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
530 // Calculate a range for phi statement S and return it in R.
531 // If a range cannot be calculated, return false.
534 gimple_ranger::range_of_phi (irange
&r
, gphi
*phi
)
536 tree phi_def
= gimple_phi_result (phi
);
537 tree type
= TREE_TYPE (phi_def
);
538 int_range_max arg_range
;
541 if (!irange::supports_type_p (type
))
544 // Start with an empty range, unioning in each argument's range.
546 for (x
= 0; x
< gimple_phi_num_args (phi
); x
++)
548 tree arg
= gimple_phi_arg_def (phi
, x
);
549 edge e
= gimple_phi_arg_edge (phi
, x
);
551 // Register potential dependencies for stale value tracking.
552 m_cache
.register_dependency (phi_def
, arg
);
554 range_on_edge (arg_range
, e
, arg
);
555 r
.union_ (arg_range
);
556 // Once the value reaches varying, stop looking.
561 // If SCEV is available, query if this PHI has any knonwn values.
562 if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def
)))
564 value_range loop_range
;
565 class loop
*l
= loop_containing_stmt (phi
);
566 if (l
&& loop_outer (l
))
568 range_of_ssa_name_with_loop_info (loop_range
, phi_def
, l
, phi
);
569 if (!loop_range
.varying_p ())
571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
573 fprintf (dump_file
, " Loops range found for ");
574 print_generic_expr (dump_file
, phi_def
, TDF_SLIM
);
575 fprintf (dump_file
, ": ");
576 loop_range
.dump (dump_file
);
577 fprintf (dump_file
, " and calculated range :");
579 fprintf (dump_file
, "\n");
581 r
.intersect (loop_range
);
589 // Calculate a range for call statement S and return it in R.
590 // If a range cannot be calculated, return false.
593 gimple_ranger::range_of_call (irange
&r
, gcall
*call
)
595 tree type
= gimple_call_return_type (call
);
596 tree lhs
= gimple_call_lhs (call
);
597 bool strict_overflow_p
;
599 if (!irange::supports_type_p (type
))
602 if (range_of_builtin_call (r
, call
))
604 else if (gimple_stmt_nonnegative_warnv_p (call
, &strict_overflow_p
))
605 r
.set (build_int_cst (type
, 0), TYPE_MAX_VALUE (type
));
606 else if (gimple_call_nonnull_result_p (call
)
607 || gimple_call_nonnull_arg (call
))
608 r
= range_nonzero (type
);
610 r
.set_varying (type
);
612 // If there is an LHS, intersect that with what is known.
616 def
= gimple_range_global (lhs
);
622 // Return the range of a __builtin_ubsan* in CALL and set it in R.
623 // CODE is the type of ubsan call (PLUS_EXPR, MINUS_EXPR or
627 range_of_builtin_ubsan_call (range_query
&query
, irange
&r
, gcall
*call
,
630 gcc_checking_assert (code
== PLUS_EXPR
|| code
== MINUS_EXPR
631 || code
== MULT_EXPR
);
632 tree type
= gimple_call_return_type (call
);
633 range_operator
*op
= range_op_handler (code
, type
);
634 gcc_checking_assert (op
);
635 int_range_max ir0
, ir1
;
636 tree arg0
= gimple_call_arg (call
, 0);
637 tree arg1
= gimple_call_arg (call
, 1);
638 query
.range_of_expr (ir0
, arg0
, call
);
639 query
.range_of_expr (ir1
, arg1
, call
);
641 bool saved_flag_wrapv
= flag_wrapv
;
642 // Pretend the arithmetic is wrapping. If there is any overflow,
643 // we'll complain, but will actually do wrapping operation.
645 op
->fold_range (r
, type
, ir0
, ir1
);
646 flag_wrapv
= saved_flag_wrapv
;
648 // If for both arguments vrp_valueize returned non-NULL, this should
649 // have been already folded and if not, it wasn't folded because of
650 // overflow. Avoid removing the UBSAN_CHECK_* calls in that case.
651 if (r
.singleton_p ())
652 r
.set_varying (type
);
655 // For a builtin in CALL, return a range in R if known and return
656 // TRUE. Otherwise return FALSE.
659 range_of_builtin_call (range_query
&query
, irange
&r
, gcall
*call
)
661 combined_fn func
= gimple_call_combined_fn (call
);
662 if (func
== CFN_LAST
)
665 tree type
= gimple_call_return_type (call
);
667 int mini
, maxi
, zerov
= 0, prec
;
668 scalar_int_mode mode
;
672 case CFN_BUILT_IN_CONSTANT_P
:
673 if (cfun
->after_inlining
)
679 arg
= gimple_call_arg (call
, 0);
680 if (query
.range_of_expr (r
, arg
, call
) && r
.singleton_p ())
682 r
.set (build_one_cst (type
), build_one_cst (type
));
689 // __builtin_ffs* and __builtin_popcount* return [0, prec].
690 arg
= gimple_call_arg (call
, 0);
691 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
694 query
.range_of_expr (r
, arg
, call
);
695 // If arg is non-zero, then ffs or popcount are non-zero.
696 if (!range_includes_zero_p (&r
))
698 // If some high bits are known to be zero, decrease the maximum.
699 if (!r
.undefined_p ())
701 if (TYPE_SIGN (r
.type ()) == SIGNED
)
702 range_cast (r
, unsigned_type_for (r
.type ()));
703 wide_int max
= r
.upper_bound ();
704 maxi
= wi::floor_log2 (max
) + 1;
706 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
710 r
.set (build_zero_cst (type
), build_one_cst (type
));
714 // __builtin_c[lt]z* return [0, prec-1], except when the
715 // argument is 0, but that is undefined behavior.
717 // For __builtin_c[lt]z* consider argument of 0 always undefined
718 // behavior, for internal fns depending on C?Z_DEFINED_VALUE_AT_ZERO.
719 arg
= gimple_call_arg (call
, 0);
720 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
723 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
724 if (gimple_call_internal_p (call
))
726 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
727 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
729 // Only handle the single common value.
733 // Magic value to give up, unless we can prove arg is non-zero.
738 query
.range_of_expr (r
, arg
, call
);
739 // From clz of minimum we can compute result maximum.
742 int newmaxi
= prec
- 1 - wi::floor_log2 (r
.lower_bound ());
743 // Argument is unsigned, so do nothing if it is [0, ...] range.
750 else if (!range_includes_zero_p (&r
))
757 // From clz of maximum we can compute result minimum.
760 int newmini
= prec
- 1 - wi::floor_log2 (r
.upper_bound ());
763 // Argument range is [0, 0]. If CLZ_DEFINED_VALUE_AT_ZERO
764 // is 2 with VALUE of prec, return [prec, prec], otherwise
774 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
778 // __builtin_ctz* return [0, prec-1], except for when the
779 // argument is 0, but that is undefined behavior.
781 // For __builtin_ctz* consider argument of 0 always undefined
782 // behavior, for internal fns depending on CTZ_DEFINED_VALUE_AT_ZERO.
783 arg
= gimple_call_arg (call
, 0);
784 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
787 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
788 if (gimple_call_internal_p (call
))
790 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
791 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
793 // Handle only the two common values.
796 else if (zerov
== prec
)
799 // Magic value to give up, unless we can prove arg is non-zero.
803 query
.range_of_expr (r
, arg
, call
);
804 if (!r
.undefined_p ())
806 if (r
.lower_bound () != 0)
811 // If some high bits are known to be zero, we can decrease
813 wide_int max
= r
.upper_bound ();
816 // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO
817 // is 2 with value -1 or prec, return [-1, -1] or [prec, prec].
818 // Otherwise ignore the range.
821 else if (maxi
== prec
)
824 // If value at zero is prec and 0 is in the range, we can't lower
825 // the upper bound. We could create two separate ranges though,
826 // [0,floor_log2(max)][prec,prec] though.
827 else if (maxi
!= prec
)
828 maxi
= wi::floor_log2 (max
);
832 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
836 arg
= gimple_call_arg (call
, 0);
837 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
838 r
.set (build_int_cst (type
, 0), build_int_cst (type
, prec
- 1));
840 case CFN_UBSAN_CHECK_ADD
:
841 range_of_builtin_ubsan_call (query
, r
, call
, PLUS_EXPR
);
843 case CFN_UBSAN_CHECK_SUB
:
844 range_of_builtin_ubsan_call (query
, r
, call
, MINUS_EXPR
);
846 case CFN_UBSAN_CHECK_MUL
:
847 range_of_builtin_ubsan_call (query
, r
, call
, MULT_EXPR
);
850 case CFN_GOACC_DIM_SIZE
:
851 case CFN_GOACC_DIM_POS
:
852 // Optimizing these two internal functions helps the loop
853 // optimizer eliminate outer comparisons. Size is [1,N]
854 // and pos is [0,N-1].
856 bool is_pos
= func
== CFN_GOACC_DIM_POS
;
857 int axis
= oacc_get_ifn_dim_arg (call
);
858 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
860 // If it's dynamic, the backend might know a hardware limitation.
861 size
= targetm
.goacc
.dim_limit (axis
);
863 r
.set (build_int_cst (type
, is_pos
? 0 : 1),
865 ? build_int_cst (type
, size
- is_pos
) : vrp_val_max (type
));
869 case CFN_BUILT_IN_STRLEN
:
870 if (tree lhs
= gimple_call_lhs (call
))
871 if (ptrdiff_type_node
872 && (TYPE_PRECISION (ptrdiff_type_node
)
873 == TYPE_PRECISION (TREE_TYPE (lhs
))))
875 tree type
= TREE_TYPE (lhs
);
876 tree max
= vrp_val_max (ptrdiff_type_node
);
878 = wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
879 tree range_min
= build_zero_cst (type
);
880 // To account for the terminating NULL, the maximum length
881 // is one less than the maximum array size, which in turn
882 // is one less than PTRDIFF_MAX (or SIZE_MAX where it's
883 // smaller than the former type).
884 // FIXME: Use max_object_size() - 1 here.
885 tree range_max
= wide_int_to_tree (type
, wmax
- 2);
886 r
.set (range_min
, range_max
);
898 gimple_ranger::range_of_builtin_call (irange
&r
, gcall
*call
)
900 return ::range_of_builtin_call (*this, r
, call
);
903 // Calculate a range for COND_EXPR statement S and return it in R.
904 // If a range cannot be calculated, return false.
907 gimple_ranger::range_of_cond_expr (irange
&r
, gassign
*s
)
909 int_range_max cond_range
, range1
, range2
;
910 tree cond
= gimple_assign_rhs1 (s
);
911 tree op1
= gimple_assign_rhs2 (s
);
912 tree op2
= gimple_assign_rhs3 (s
);
914 gcc_checking_assert (gimple_assign_rhs_code (s
) == COND_EXPR
);
915 gcc_checking_assert (useless_type_conversion_p (TREE_TYPE (op1
),
917 if (!irange::supports_type_p (TREE_TYPE (op1
)))
920 range_of_expr (cond_range
, cond
, s
);
921 range_of_expr (range1
, op1
, s
);
922 range_of_expr (range2
, op2
, s
);
924 // If the condition is known, choose the appropriate expression.
925 if (cond_range
.singleton_p ())
927 // False, pick second operand.
928 if (cond_range
.zero_p ())
942 gimple_ranger::range_of_expr (irange
&r
, tree expr
, gimple
*stmt
)
944 if (!gimple_range_ssa_p (expr
))
945 return get_tree_range (r
, expr
);
947 // If there is no statement, just get the global value.
950 if (!m_cache
.get_global_range (r
, expr
))
951 r
= gimple_range_global (expr
);
955 basic_block bb
= gimple_bb (stmt
);
956 gimple
*def_stmt
= SSA_NAME_DEF_STMT (expr
);
958 // If name is defined in this block, try to get an range from S.
959 if (def_stmt
&& gimple_bb (def_stmt
) == bb
)
960 range_of_stmt (r
, def_stmt
, expr
);
962 // Otherwise OP comes from outside this block, use range on entry.
963 range_on_entry (r
, bb
, expr
);
965 // No range yet, see if there is a dereference in the block.
966 // We don't care if it's between the def and a use within a block
967 // because the entire block must be executed anyway.
968 // FIXME:?? For non-call exceptions we could have a statement throw
969 // which causes an early block exit.
970 // in which case we may need to walk from S back to the def/top of block
971 // to make sure the deref happens between S and there before claiming
972 // there is a deref. Punt for now.
973 if (!cfun
->can_throw_non_call_exceptions
&& r
.varying_p () &&
974 m_cache
.m_non_null
.non_null_deref_p (expr
, bb
))
975 r
= range_nonzero (TREE_TYPE (expr
));
980 // Return the range of NAME on entry to block BB in R.
983 gimple_ranger::range_on_entry (irange
&r
, basic_block bb
, tree name
)
985 int_range_max entry_range
;
986 gcc_checking_assert (gimple_range_ssa_p (name
));
988 // Start with any known range
989 range_of_stmt (r
, SSA_NAME_DEF_STMT (name
), name
);
991 // Now see if there is any on_entry value which may refine it.
992 if (m_cache
.block_range (entry_range
, bb
, name
))
993 r
.intersect (entry_range
);
996 // Calculate the range for NAME at the end of block BB and return it in R.
997 // Return false if no range can be calculated.
1000 gimple_ranger::range_on_exit (irange
&r
, basic_block bb
, tree name
)
1002 // on-exit from the exit block?
1003 gcc_checking_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1004 gcc_checking_assert (gimple_range_ssa_p (name
));
1006 gimple
*s
= last_stmt (bb
);
1007 // If there is no statement in the block and this isn't the entry
1008 // block, go get the range_on_entry for this block. For the entry
1009 // block, a NULL stmt will return the global value for NAME.
1010 if (!s
&& bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1011 range_on_entry (r
, bb
, name
);
1013 range_of_expr (r
, name
, s
);
1014 gcc_checking_assert (r
.undefined_p ()
1015 || range_compatible_p (r
.type (), TREE_TYPE (name
)));
1018 // Calculate a range for NAME on edge E and return it in R.
1021 gimple_ranger::range_on_edge (irange
&r
, edge e
, tree name
)
1023 int_range_max edge_range
;
1024 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name
)));
1026 // PHI arguments can be constants, catch these here.
1027 if (!gimple_range_ssa_p (name
))
1028 return range_of_expr (r
, name
);
1030 range_on_exit (r
, e
->src
, name
);
1031 gcc_checking_assert (r
.undefined_p ()
1032 || range_compatible_p (r
.type(), TREE_TYPE (name
)));
1034 // Check to see if NAME is defined on edge e.
1035 if (m_cache
.outgoing_edge_range_p (edge_range
, e
, name
))
1036 r
.intersect (edge_range
);
1041 // Calculate a range for statement S and return it in R. If NAME is
1042 // provided it represents the SSA_NAME on the LHS of the statement.
1043 // It is only required if there is more than one lhs/output. Check
1044 // the global cache for NAME first to see if the evaluation can be
1045 // avoided. If a range cannot be calculated, return false and UNDEFINED.
1048 gimple_ranger::range_of_stmt (irange
&r
, gimple
*s
, tree name
)
1053 name
= gimple_get_lhs (s
);
1055 // If no name, simply call the base routine.
1057 return calc_stmt (r
, s
, NULL_TREE
);
1059 if (!gimple_range_ssa_p (name
))
1062 // Check if the stmt has already been processed, and is not stale.
1063 if (m_cache
.get_non_stale_global_range (r
, name
))
1066 // Otherwise calculate a new value.
1068 calc_stmt (tmp
, s
, name
);
1070 // Combine the new value with the old value. This is required because
1071 // the way value propagation works, when the IL changes on the fly we
1072 // can sometimes get different results. See PR 97741.
1074 m_cache
.set_global_range (name
, r
);
1078 // This routine will export whatever global ranges are known to GCC
1079 // SSA_RANGE_NAME_INFO fields.
1082 gimple_ranger::export_global_ranges ()
1088 fprintf (dump_file
, "Exported global range table\n");
1089 fprintf (dump_file
, "===========================\n");
1092 for ( x
= 1; x
< num_ssa_names
; x
++)
1094 tree name
= ssa_name (x
);
1095 if (name
&& !SSA_NAME_IN_FREE_LIST (name
)
1096 && gimple_range_ssa_p (name
)
1097 && m_cache
.get_global_range (r
, name
)
1100 // Make sure the new range is a subset of the old range.
1101 int_range_max old_range
;
1102 old_range
= gimple_range_global (name
);
1103 old_range
.intersect (r
);
1104 /* Disable this while we fix tree-ssa/pr61743-2.c. */
1105 //gcc_checking_assert (old_range == r);
1107 // WTF? Can't write non-null pointer ranges?? stupid set_range_info!
1108 if (!POINTER_TYPE_P (TREE_TYPE (name
)) && !r
.undefined_p ())
1111 set_range_info (name
, vr
);
1114 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1115 fprintf (dump_file
, " --> ");
1116 vr
.dump (dump_file
);
1117 fprintf (dump_file
, "\n");
1118 fprintf (dump_file
, " irange : ");
1120 fprintf (dump_file
, "\n");
1127 // Print the known table values to file F.
1130 gimple_ranger::dump (FILE *f
)
1134 FOR_EACH_BB_FN (bb
, cfun
)
1139 int_range_max range
;
1140 fprintf (f
, "\n=========== BB %d ============\n", bb
->index
);
1141 m_cache
.dump (f
, bb
);
1143 dump_bb (f
, bb
, 4, TDF_NONE
);
1145 // Now find any globals defined in this block.
1146 for (x
= 1; x
< num_ssa_names
; x
++)
1148 tree name
= ssa_name (x
);
1149 if (gimple_range_ssa_p (name
) && SSA_NAME_DEF_STMT (name
) &&
1150 gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
&&
1151 m_cache
.get_global_range (range
, name
))
1153 if (!range
.varying_p ())
1155 print_generic_expr (f
, name
, TDF_SLIM
);
1164 // And now outgoing edges, if they define anything.
1165 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1167 for (x
= 1; x
< num_ssa_names
; x
++)
1169 tree name
= gimple_range_ssa_p (ssa_name (x
));
1170 if (name
&& m_cache
.outgoing_edge_range_p (range
, e
, name
))
1172 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1173 // Only print the range if this is the def block, or
1174 // the on entry cache for either end of the edge is
1176 if ((s
&& bb
== gimple_bb (s
)) ||
1177 m_cache
.block_range (range
, bb
, name
, false) ||
1178 m_cache
.block_range (range
, e
->dest
, name
, false))
1180 range_on_edge (range
, e
, name
);
1181 if (!range
.varying_p ())
1183 fprintf (f
, "%d->%d ", e
->src
->index
,
1186 if (e
->flags
& EDGE_TRUE_VALUE
)
1187 fprintf (f
, " (T)%c", c
);
1188 else if (e
->flags
& EDGE_FALSE_VALUE
)
1189 fprintf (f
, " (F)%c", c
);
1192 print_generic_expr (f
, name
, TDF_SLIM
);
1193 fprintf(f
, " : \t");
1203 m_cache
.dump (dump_file
, (dump_flags
& TDF_DETAILS
) != 0);
1206 // If SCEV has any information about phi node NAME, return it as a range in R.
1209 gimple_ranger::range_of_ssa_name_with_loop_info (irange
&r
, tree name
,
1210 class loop
*l
, gphi
*phi
)
1212 gcc_checking_assert (TREE_CODE (name
) == SSA_NAME
);
1213 tree min
, max
, type
= TREE_TYPE (name
);
1214 if (bounds_of_var_in_loop (&min
, &max
, this, l
, phi
, name
))
1216 // ?? We could do better here. Since MIN/MAX can only be an
1217 // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call
1218 // the ranger and solve anything not an integer.
1219 if (TREE_CODE (min
) != INTEGER_CST
)
1220 min
= vrp_val_min (type
);
1221 if (TREE_CODE (max
) != INTEGER_CST
)
1222 max
= vrp_val_max (type
);
1226 r
.set_varying (type
);
1229 // --------------------------------------------------------------------------
1230 // trace_ranger implementation.
1233 trace_ranger::trace_ranger ()
1239 // If dumping, return true and print the prefix for the next output line.
1242 trace_ranger::dumping (unsigned counter
, bool trailing
)
1244 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1246 // Print counter index as well as INDENT spaces.
1248 fprintf (dump_file
, " %-7u ", counter
);
1250 fprintf (dump_file
, " ");
1252 for (x
= 0; x
< indent
; x
++)
1253 fputc (' ', dump_file
);
1259 // After calling a routine, if dumping, print the CALLER, NAME, and RESULT,
1260 // returning RESULT.
1263 trace_ranger::trailer (unsigned counter
, const char *caller
, bool result
,
1264 tree name
, const irange
&r
)
1266 if (dumping (counter
, true))
1269 fputs(result
? "TRUE : " : "FALSE : ", dump_file
);
1270 fprintf (dump_file
, "(%u) ", counter
);
1271 fputs (caller
, dump_file
);
1272 fputs (" (",dump_file
);
1274 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1275 fputs (") ",dump_file
);
1279 fputc('\n', dump_file
);
1282 fputc('\n', dump_file
);
1283 // Marks the end of a request.
1285 fputc('\n', dump_file
);
1290 // Tracing version of range_on_edge. Call it with printing wrappers.
1293 trace_ranger::range_on_edge (irange
&r
, edge e
, tree name
)
1295 unsigned idx
= ++trace_count
;
1298 fprintf (dump_file
, "range_on_edge (");
1299 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1300 fprintf (dump_file
, ") on edge %d->%d\n", e
->src
->index
, e
->dest
->index
);
1304 bool res
= gimple_ranger::range_on_edge (r
, e
, name
);
1305 trailer (idx
, "range_on_edge", true, name
, r
);
1309 // Tracing version of range_on_entry. Call it with printing wrappers.
1312 trace_ranger::range_on_entry (irange
&r
, basic_block bb
, tree name
)
1314 unsigned idx
= ++trace_count
;
1317 fprintf (dump_file
, "range_on_entry (");
1318 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1319 fprintf (dump_file
, ") to BB %d\n", bb
->index
);
1323 gimple_ranger::range_on_entry (r
, bb
, name
);
1325 trailer (idx
, "range_on_entry", true, name
, r
);
1328 // Tracing version of range_on_exit. Call it with printing wrappers.
1331 trace_ranger::range_on_exit (irange
&r
, basic_block bb
, tree name
)
1333 unsigned idx
= ++trace_count
;
1336 fprintf (dump_file
, "range_on_exit (");
1337 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1338 fprintf (dump_file
, ") from BB %d\n", bb
->index
);
1342 gimple_ranger::range_on_exit (r
, bb
, name
);
1344 trailer (idx
, "range_on_exit", true, name
, r
);
1347 // Tracing version of range_of_stmt. Call it with printing wrappers.
1350 trace_ranger::range_of_stmt (irange
&r
, gimple
*s
, tree name
)
1353 unsigned idx
= ++trace_count
;
1356 fprintf (dump_file
, "range_of_stmt (");
1358 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1359 fputs (") at stmt ", dump_file
);
1360 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
1364 res
= gimple_ranger::range_of_stmt (r
, s
, name
);
1366 return trailer (idx
, "range_of_stmt", res
, name
, r
);
1369 // Tracing version of range_of_expr. Call it with printing wrappers.
1372 trace_ranger::range_of_expr (irange
&r
, tree name
, gimple
*s
)
1375 unsigned idx
= ++trace_count
;
1378 fprintf (dump_file
, "range_of_expr(");
1379 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1380 fputs (")", dump_file
);
1383 fputs (" at stmt ", dump_file
);
1384 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
1387 fputs ("\n", dump_file
);
1391 res
= gimple_ranger::range_of_expr (r
, name
, s
);
1393 return trailer (idx
, "range_of_expr", res
, name
, r
);