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"
50 // Evaluate expression EXPR using the source information the class was
51 // instantiated with. Place the result in R, and return TRUE. If a range
52 // cannot be calcluated, return FALSE.
55 fur_source::get_operand (irange
&r
, tree expr
)
57 if (!gimple_range_ssa_p (expr
))
58 return get_tree_range (r
, expr
);
60 // If no query engine is present, simply get the global value.
63 r
= gimple_range_global (expr
);
67 // First look for a stmt.
69 return m_query
->range_of_expr (r
, expr
, m_stmt
);
71 // Finally must be on an edge.
72 return m_query
->range_on_edge (r
, m_edge
, expr
);
76 // Adjust the range for a pointer difference where the operands came
79 // This notices the following sequence:
81 // def = __builtin_memchr (arg, 0, sz)
84 // The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
87 adjust_pointer_diff_expr (irange
&res
, const gimple
*diff_stmt
)
89 tree op0
= gimple_assign_rhs1 (diff_stmt
);
90 tree op1
= gimple_assign_rhs2 (diff_stmt
);
91 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
92 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
95 if (TREE_CODE (op0
) == SSA_NAME
96 && TREE_CODE (op1
) == SSA_NAME
97 && (call
= SSA_NAME_DEF_STMT (op0
))
98 && is_gimple_call (call
)
99 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
100 && TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
101 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
102 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
103 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
104 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
105 && vrp_operand_equal_p (op1
, gimple_call_arg (call
, 0))
106 && integer_zerop (gimple_call_arg (call
, 1)))
108 tree max
= vrp_val_max (ptrdiff_type_node
);
109 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
110 tree expr_type
= gimple_expr_type (diff_stmt
);
111 tree range_min
= build_zero_cst (expr_type
);
112 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
113 int_range
<2> r (range_min
, range_max
);
118 // This function looks for situations when walking the use/def chains
119 // may provide additonal contextual range information not exposed on
120 // this statement. Like knowing the IMAGPART return value from a
121 // builtin function is a boolean result.
123 // We should rework how we're called, as we have an op_unknown entry
124 // for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this
125 // function gets called.
128 gimple_range_adjustment (irange
&res
, const gimple
*stmt
)
130 switch (gimple_expr_code (stmt
))
132 case POINTER_DIFF_EXPR
:
133 adjust_pointer_diff_expr (res
, stmt
);
138 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
139 if (TREE_CODE (name
) == SSA_NAME
)
141 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
142 if (def_stmt
&& is_gimple_call (def_stmt
)
143 && gimple_call_internal_p (def_stmt
))
145 switch (gimple_call_internal_fn (def_stmt
))
147 case IFN_ADD_OVERFLOW
:
148 case IFN_SUB_OVERFLOW
:
149 case IFN_MUL_OVERFLOW
:
150 case IFN_ATOMIC_COMPARE_EXCHANGE
:
153 r
.set_varying (boolean_type_node
);
154 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
155 range_cast (r
, type
);
171 // Return a range in R for the tree EXPR. Return true if a range is
172 // representable, and UNDEFINED/false if not.
175 get_tree_range (irange
&r
, tree expr
)
181 type
= TREE_TYPE (expr
);
183 // Return false if the type isn't suported.
184 if (!irange::supports_type_p (type
))
190 switch (TREE_CODE (expr
))
193 if (TREE_OVERFLOW_P (expr
))
194 expr
= drop_tree_overflow (expr
);
199 r
= gimple_range_global (expr
);
204 // Handle &var which can show up in phi arguments.
206 if (tree_single_nonzero_warnv_p (expr
, &ov
))
208 r
= range_nonzero (type
);
217 r
.set_varying (type
);
221 // Return the base of the RHS of an assignment.
224 gimple_range_base_of_assignment (const gimple
*stmt
)
226 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
227 tree op1
= gimple_assign_rhs1 (stmt
);
228 if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
229 return get_base_address (TREE_OPERAND (op1
, 0));
233 // Return the first operand of this statement if it is a valid operand
234 // supported by ranges, otherwise return NULL_TREE. Special case is
235 // &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr.
238 gimple_range_operand1 (const gimple
*stmt
)
240 gcc_checking_assert (gimple_range_handler (stmt
));
242 switch (gimple_code (stmt
))
245 return gimple_cond_lhs (stmt
);
248 tree base
= gimple_range_base_of_assignment (stmt
);
249 if (base
&& TREE_CODE (base
) == MEM_REF
)
251 // If the base address is an SSA_NAME, we return it
252 // here. This allows processing of the range of that
253 // name, while the rest of the expression is simply
254 // ignored. The code in range_ops will see the
255 // ADDR_EXPR and do the right thing.
256 tree ssa
= TREE_OPERAND (base
, 0);
257 if (TREE_CODE (ssa
) == SSA_NAME
)
268 // Return the second operand of statement STMT, otherwise return NULL_TREE.
271 gimple_range_operand2 (const gimple
*stmt
)
273 gcc_checking_assert (gimple_range_handler (stmt
));
275 switch (gimple_code (stmt
))
278 return gimple_cond_rhs (stmt
);
280 if (gimple_num_ops (stmt
) >= 3)
281 return gimple_assign_rhs2 (stmt
);
288 // Calculate what we can determine of the range of this unary
289 // statement's operand if the lhs of the expression has the range
290 // LHS_RANGE. Return false if nothing can be determined.
293 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
, const irange
&lhs_range
)
295 gcc_checking_assert (gimple_num_ops (stmt
) < 3);
297 // An empty range is viral.
298 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
299 if (lhs_range
.undefined_p ())
304 // Unary operations require the type of the first operand in the
305 // second range position.
306 int_range
<2> type_range (type
);
307 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
311 // Calculate what we can determine of the range of this statement's
312 // first operand if the lhs of the expression has the range LHS_RANGE
313 // and the second operand has the range OP2_RANGE. Return false if
314 // nothing can be determined.
317 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
,
318 const irange
&lhs_range
, const irange
&op2_range
)
320 // Unary operation are allowed to pass a range in for second operand
321 // as there are often additional restrictions beyond the type which
322 // can be imposed. See operator_cast::op1_range().
323 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
324 // An empty range is viral.
325 if (op2_range
.undefined_p () || lhs_range
.undefined_p ())
330 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
334 // Calculate what we can determine of the range of this statement's
335 // second operand if the lhs of the expression has the range LHS_RANGE
336 // and the first operand has the range OP1_RANGE. Return false if
337 // nothing can be determined.
340 gimple_range_calc_op2 (irange
&r
, const gimple
*stmt
,
341 const irange
&lhs_range
, const irange
&op1_range
)
343 tree type
= TREE_TYPE (gimple_range_operand2 (stmt
));
344 // An empty range is viral.
345 if (op1_range
.undefined_p () || lhs_range
.undefined_p ())
350 return gimple_range_handler (stmt
)->op2_range (r
, type
, lhs_range
,
354 // Calculate a range for statement S and return it in R. If NAME is provided it
355 // represents the SSA_NAME on the LHS of the statement. It is only required
356 // if there is more than one lhs/output. If a range cannot
357 // be calculated, return false.
360 fold_using_range::fold_stmt (irange
&r
, gimple
*s
, fur_source
&src
, tree name
)
363 // If name and S are specified, make sure it is an LHS of S.
364 gcc_checking_assert (!name
|| !gimple_get_lhs (s
) ||
365 name
== gimple_get_lhs (s
));
368 name
= gimple_get_lhs (s
);
370 // Process addresses.
371 if (gimple_code (s
) == GIMPLE_ASSIGN
372 && gimple_assign_rhs_code (s
) == ADDR_EXPR
)
373 return range_of_address (r
, s
, src
);
375 if (gimple_range_handler (s
))
376 res
= range_of_range_op (r
, s
, src
);
377 else if (is_a
<gphi
*>(s
))
378 res
= range_of_phi (r
, as_a
<gphi
*> (s
), src
);
379 else if (is_a
<gcall
*>(s
))
380 res
= range_of_call (r
, as_a
<gcall
*> (s
), src
);
381 else if (is_a
<gassign
*> (s
) && gimple_assign_rhs_code (s
) == COND_EXPR
)
382 res
= range_of_cond_expr (r
, as_a
<gassign
*> (s
), src
);
386 // If no name is specified, try the expression kind.
389 tree t
= gimple_expr_type (s
);
390 if (!irange::supports_type_p (t
))
395 if (!gimple_range_ssa_p (name
))
397 // We don't understand the stmt, so return the global range.
398 r
= gimple_range_global (name
);
402 if (r
.undefined_p ())
405 // We sometimes get compatible types copied from operands, make sure
406 // the correct type is being returned.
407 if (name
&& TREE_TYPE (name
) != r
.type ())
409 gcc_checking_assert (range_compatible_p (r
.type (), TREE_TYPE (name
)));
410 range_cast (r
, TREE_TYPE (name
));
415 // Calculate a range for range_op statement S and return it in R. If any
416 // If a range cannot be calculated, return false.
419 fold_using_range::range_of_range_op (irange
&r
, gimple
*s
, fur_source
&src
)
421 int_range_max range1
, range2
;
422 tree type
= gimple_expr_type (s
);
423 range_operator
*handler
= gimple_range_handler (s
);
424 gcc_checking_assert (handler
);
425 gcc_checking_assert (irange::supports_type_p (type
));
427 tree lhs
= gimple_get_lhs (s
);
428 tree op1
= gimple_range_operand1 (s
);
429 tree op2
= gimple_range_operand2 (s
);
431 if (src
.get_operand (range1
, op1
))
435 // Fold range, and register any dependency if available.
436 int_range
<2> r2 (type
);
437 handler
->fold_range (r
, type
, range1
, r2
);
438 if (lhs
&& src
.m_cache
)
439 src
.m_cache
->register_dependency (lhs
, op1
);
441 else if (src
.get_operand (range2
, op2
))
443 // Fold range, and register any dependency if available.
444 handler
->fold_range (r
, type
, range1
, range2
);
445 if (lhs
&& src
.m_cache
)
447 src
.m_cache
->register_dependency (lhs
, op1
);
448 src
.m_cache
->register_dependency (lhs
, op2
);
452 r
.set_varying (type
);
455 r
.set_varying (type
);
456 // Make certain range-op adjustments that aren't handled any other way.
457 gimple_range_adjustment (r
, s
);
461 // Calculate the range of an assignment containing an ADDR_EXPR.
462 // Return the range in R.
463 // If a range cannot be calculated, set it to VARYING and return true.
466 fold_using_range::range_of_address (irange
&r
, gimple
*stmt
, fur_source
&src
)
468 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
469 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
);
471 bool strict_overflow_p
;
472 tree expr
= gimple_assign_rhs1 (stmt
);
473 poly_int64 bitsize
, bitpos
;
476 int unsignedp
, reversep
, volatilep
;
477 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
478 &bitpos
, &offset
, &mode
, &unsignedp
,
479 &reversep
, &volatilep
);
482 if (base
!= NULL_TREE
483 && TREE_CODE (base
) == MEM_REF
484 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
486 tree ssa
= TREE_OPERAND (base
, 0);
487 tree lhs
= gimple_get_lhs (stmt
);
488 if (src
.m_cache
&& lhs
&& gimple_range_ssa_p (ssa
))
489 src
.m_cache
->register_dependency (lhs
, ssa
);
490 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (ssa
)));
491 src
.get_operand (r
, ssa
);
492 range_cast (r
, TREE_TYPE (gimple_assign_rhs1 (stmt
)));
494 poly_offset_int off
= 0;
495 bool off_cst
= false;
496 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
498 off
= mem_ref_offset (base
);
500 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
502 off
<<= LOG2_BITS_PER_UNIT
;
506 /* If &X->a is equal to X, the range of X is the result. */
507 if (off_cst
&& known_eq (off
, 0))
509 else if (flag_delete_null_pointer_checks
510 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
)))
512 /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
513 allow going from non-NULL pointer to NULL. */
514 if(!range_includes_zero_p (&r
))
517 /* If MEM_REF has a "positive" offset, consider it non-NULL
518 always, for -fdelete-null-pointer-checks also "negative"
519 ones. Punt for unknown offsets (e.g. variable ones). */
520 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
523 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
525 r
= range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
528 r
= int_range
<2> (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
533 if (tree_single_nonzero_warnv_p (expr
, &strict_overflow_p
))
535 r
= range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
539 // Otherwise return varying.
540 r
= int_range
<2> (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
544 // Calculate a range for phi statement S and return it in R.
545 // If a range cannot be calculated, return false.
548 fold_using_range::range_of_phi (irange
&r
, gphi
*phi
, fur_source
&src
)
550 tree phi_def
= gimple_phi_result (phi
);
551 tree type
= TREE_TYPE (phi_def
);
552 int_range_max arg_range
;
555 if (!irange::supports_type_p (type
))
558 // Start with an empty range, unioning in each argument's range.
560 for (x
= 0; x
< gimple_phi_num_args (phi
); x
++)
562 tree arg
= gimple_phi_arg_def (phi
, x
);
563 edge e
= gimple_phi_arg_edge (phi
, x
);
565 // Register potential dependencies for stale value tracking.
566 if (src
.m_cache
&& gimple_range_ssa_p (arg
))
567 src
.m_cache
->register_dependency (phi_def
, arg
);
569 // Get the range of the argument on its edge.
570 fur_source
e_src (src
.m_query
, e
);
571 e_src
.get_operand (arg_range
, arg
);
572 // If we're recomputing the argument elsewhere, try to refine it.
573 if (src
.m_stmt
!= phi
)
576 e_src
.get_operand (tmp
, arg
);
577 arg_range
.intersect (tmp
);
579 r
.union_ (arg_range
);
580 // Once the value reaches varying, stop looking.
585 // If SCEV is available, query if this PHI has any knonwn values.
586 if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def
)))
588 value_range loop_range
;
589 class loop
*l
= loop_containing_stmt (phi
);
590 if (l
&& loop_outer (l
))
592 range_of_ssa_name_with_loop_info (loop_range
, phi_def
, l
, phi
, src
);
593 if (!loop_range
.varying_p ())
595 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
597 fprintf (dump_file
, " Loops range found for ");
598 print_generic_expr (dump_file
, phi_def
, TDF_SLIM
);
599 fprintf (dump_file
, ": ");
600 loop_range
.dump (dump_file
);
601 fprintf (dump_file
, " and calculated range :");
603 fprintf (dump_file
, "\n");
605 r
.intersect (loop_range
);
613 // Calculate a range for call statement S and return it in R.
614 // If a range cannot be calculated, return false.
617 fold_using_range::range_of_call (irange
&r
, gcall
*call
, fur_source
&src
)
619 tree type
= gimple_call_return_type (call
);
620 tree lhs
= gimple_call_lhs (call
);
621 bool strict_overflow_p
;
623 if (!irange::supports_type_p (type
))
626 if (range_of_builtin_call (r
, call
, src
))
628 else if (gimple_stmt_nonnegative_warnv_p (call
, &strict_overflow_p
))
629 r
.set (build_int_cst (type
, 0), TYPE_MAX_VALUE (type
));
630 else if (gimple_call_nonnull_result_p (call
)
631 || gimple_call_nonnull_arg (call
))
632 r
= range_nonzero (type
);
634 r
.set_varying (type
);
636 // If there is an LHS, intersect that with what is known.
640 def
= gimple_range_global (lhs
);
646 // Return the range of a __builtin_ubsan* in CALL and set it in R.
647 // CODE is the type of ubsan call (PLUS_EXPR, MINUS_EXPR or
651 fold_using_range::range_of_builtin_ubsan_call (irange
&r
, gcall
*call
,
652 tree_code code
, fur_source
&src
)
654 gcc_checking_assert (code
== PLUS_EXPR
|| code
== MINUS_EXPR
655 || code
== MULT_EXPR
);
656 tree type
= gimple_call_return_type (call
);
657 range_operator
*op
= range_op_handler (code
, type
);
658 gcc_checking_assert (op
);
659 int_range_max ir0
, ir1
;
660 tree arg0
= gimple_call_arg (call
, 0);
661 tree arg1
= gimple_call_arg (call
, 1);
662 src
.get_operand (ir0
, arg0
);
663 src
.get_operand (ir1
, arg1
);
665 bool saved_flag_wrapv
= flag_wrapv
;
666 // Pretend the arithmetic is wrapping. If there is any overflow,
667 // we'll complain, but will actually do wrapping operation.
669 op
->fold_range (r
, type
, ir0
, ir1
);
670 flag_wrapv
= saved_flag_wrapv
;
672 // If for both arguments vrp_valueize returned non-NULL, this should
673 // have been already folded and if not, it wasn't folded because of
674 // overflow. Avoid removing the UBSAN_CHECK_* calls in that case.
675 if (r
.singleton_p ())
676 r
.set_varying (type
);
679 // For a builtin in CALL, return a range in R if known and return
680 // TRUE. Otherwise return FALSE.
683 fold_using_range::range_of_builtin_call (irange
&r
, gcall
*call
,
686 combined_fn func
= gimple_call_combined_fn (call
);
687 if (func
== CFN_LAST
)
690 tree type
= gimple_call_return_type (call
);
692 int mini
, maxi
, zerov
= 0, prec
;
693 scalar_int_mode mode
;
697 case CFN_BUILT_IN_CONSTANT_P
:
698 if (cfun
->after_inlining
)
704 arg
= gimple_call_arg (call
, 0);
705 if (src
.get_operand (r
, arg
) && r
.singleton_p ())
707 r
.set (build_one_cst (type
), build_one_cst (type
));
714 // __builtin_ffs* and __builtin_popcount* return [0, prec].
715 arg
= gimple_call_arg (call
, 0);
716 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
719 src
.get_operand (r
, arg
);
720 // If arg is non-zero, then ffs or popcount are non-zero.
721 if (!range_includes_zero_p (&r
))
723 // If some high bits are known to be zero, decrease the maximum.
724 if (!r
.undefined_p ())
726 if (TYPE_SIGN (r
.type ()) == SIGNED
)
727 range_cast (r
, unsigned_type_for (r
.type ()));
728 wide_int max
= r
.upper_bound ();
729 maxi
= wi::floor_log2 (max
) + 1;
731 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
735 r
.set (build_zero_cst (type
), build_one_cst (type
));
739 // __builtin_c[lt]z* return [0, prec-1], except when the
740 // argument is 0, but that is undefined behavior.
742 // For __builtin_c[lt]z* consider argument of 0 always undefined
743 // behavior, for internal fns depending on C?Z_DEFINED_VALUE_AT_ZERO.
744 arg
= gimple_call_arg (call
, 0);
745 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
748 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
749 if (gimple_call_internal_p (call
))
751 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
752 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
754 // Only handle the single common value.
758 // Magic value to give up, unless we can prove arg is non-zero.
763 src
.get_operand (r
, arg
);
764 // From clz of minimum we can compute result maximum.
765 if (r
.constant_p () && !r
.varying_p ())
767 int newmaxi
= prec
- 1 - wi::floor_log2 (r
.lower_bound ());
768 // Argument is unsigned, so do nothing if it is [0, ...] range.
775 else if (!range_includes_zero_p (&r
))
782 // From clz of maximum we can compute result minimum.
785 int newmini
= prec
- 1 - wi::floor_log2 (r
.upper_bound ());
788 // Argument range is [0, 0]. If CLZ_DEFINED_VALUE_AT_ZERO
789 // is 2 with VALUE of prec, return [prec, prec], otherwise
799 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
803 // __builtin_ctz* return [0, prec-1], except for when the
804 // argument is 0, but that is undefined behavior.
806 // For __builtin_ctz* consider argument of 0 always undefined
807 // behavior, for internal fns depending on CTZ_DEFINED_VALUE_AT_ZERO.
808 arg
= gimple_call_arg (call
, 0);
809 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
812 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
813 if (gimple_call_internal_p (call
))
815 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
816 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
818 // Handle only the two common values.
821 else if (zerov
== prec
)
824 // Magic value to give up, unless we can prove arg is non-zero.
828 src
.get_operand (r
, arg
);
829 if (!r
.undefined_p ())
831 if (r
.lower_bound () != 0)
836 // If some high bits are known to be zero, we can decrease
838 wide_int max
= r
.upper_bound ();
841 // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO
842 // is 2 with value -1 or prec, return [-1, -1] or [prec, prec].
843 // Otherwise ignore the range.
846 else if (maxi
== prec
)
849 // If value at zero is prec and 0 is in the range, we can't lower
850 // the upper bound. We could create two separate ranges though,
851 // [0,floor_log2(max)][prec,prec] though.
852 else if (maxi
!= prec
)
853 maxi
= wi::floor_log2 (max
);
857 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
861 arg
= gimple_call_arg (call
, 0);
862 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
863 r
.set (build_int_cst (type
, 0), build_int_cst (type
, prec
- 1));
865 case CFN_UBSAN_CHECK_ADD
:
866 range_of_builtin_ubsan_call (r
, call
, PLUS_EXPR
, src
);
868 case CFN_UBSAN_CHECK_SUB
:
869 range_of_builtin_ubsan_call (r
, call
, MINUS_EXPR
, src
);
871 case CFN_UBSAN_CHECK_MUL
:
872 range_of_builtin_ubsan_call (r
, call
, MULT_EXPR
, src
);
875 case CFN_GOACC_DIM_SIZE
:
876 case CFN_GOACC_DIM_POS
:
877 // Optimizing these two internal functions helps the loop
878 // optimizer eliminate outer comparisons. Size is [1,N]
879 // and pos is [0,N-1].
881 bool is_pos
= func
== CFN_GOACC_DIM_POS
;
882 int axis
= oacc_get_ifn_dim_arg (call
);
883 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
885 // If it's dynamic, the backend might know a hardware limitation.
886 size
= targetm
.goacc
.dim_limit (axis
);
888 r
.set (build_int_cst (type
, is_pos
? 0 : 1),
890 ? build_int_cst (type
, size
- is_pos
) : vrp_val_max (type
));
894 case CFN_BUILT_IN_STRLEN
:
895 if (tree lhs
= gimple_call_lhs (call
))
896 if (ptrdiff_type_node
897 && (TYPE_PRECISION (ptrdiff_type_node
)
898 == TYPE_PRECISION (TREE_TYPE (lhs
))))
900 tree type
= TREE_TYPE (lhs
);
901 tree max
= vrp_val_max (ptrdiff_type_node
);
903 = wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
904 tree range_min
= build_zero_cst (type
);
905 // To account for the terminating NULL, the maximum length
906 // is one less than the maximum array size, which in turn
907 // is one less than PTRDIFF_MAX (or SIZE_MAX where it's
908 // smaller than the former type).
909 // FIXME: Use max_object_size() - 1 here.
910 tree range_max
= wide_int_to_tree (type
, wmax
- 2);
911 r
.set (range_min
, range_max
);
922 // Calculate a range for COND_EXPR statement S and return it in R.
923 // If a range cannot be calculated, return false.
926 fold_using_range::range_of_cond_expr (irange
&r
, gassign
*s
, fur_source
&src
)
928 int_range_max cond_range
, range1
, range2
;
929 tree cond
= gimple_assign_rhs1 (s
);
930 tree op1
= gimple_assign_rhs2 (s
);
931 tree op2
= gimple_assign_rhs3 (s
);
933 gcc_checking_assert (gimple_assign_rhs_code (s
) == COND_EXPR
);
934 gcc_checking_assert (useless_type_conversion_p (TREE_TYPE (op1
),
936 if (!irange::supports_type_p (TREE_TYPE (op1
)))
939 src
.get_operand (cond_range
, cond
);
940 src
.get_operand (range1
, op1
);
941 src
.get_operand (range2
, op2
);
943 // If the condition is known, choose the appropriate expression.
944 if (cond_range
.singleton_p ())
946 // False, pick second operand.
947 if (cond_range
.zero_p ())
961 gimple_ranger::range_of_expr (irange
&r
, tree expr
, gimple
*stmt
)
963 if (!gimple_range_ssa_p (expr
))
964 return get_tree_range (r
, expr
);
966 // If there is no statement, just get the global value.
969 if (!m_cache
.get_global_range (r
, expr
))
970 r
= gimple_range_global (expr
);
974 basic_block bb
= gimple_bb (stmt
);
975 gimple
*def_stmt
= SSA_NAME_DEF_STMT (expr
);
977 // If name is defined in this block, try to get an range from S.
978 if (def_stmt
&& gimple_bb (def_stmt
) == bb
)
979 range_of_stmt (r
, def_stmt
, expr
);
981 // Otherwise OP comes from outside this block, use range on entry.
982 range_on_entry (r
, bb
, expr
);
984 // No range yet, see if there is a dereference in the block.
985 // We don't care if it's between the def and a use within a block
986 // because the entire block must be executed anyway.
987 // FIXME:?? For non-call exceptions we could have a statement throw
988 // which causes an early block exit.
989 // in which case we may need to walk from S back to the def/top of block
990 // to make sure the deref happens between S and there before claiming
991 // there is a deref. Punt for now.
992 if (!cfun
->can_throw_non_call_exceptions
&& r
.varying_p () &&
993 m_cache
.m_non_null
.non_null_deref_p (expr
, bb
))
994 r
= range_nonzero (TREE_TYPE (expr
));
999 // Return the range of NAME on entry to block BB in R.
1002 gimple_ranger::range_on_entry (irange
&r
, basic_block bb
, tree name
)
1004 int_range_max entry_range
;
1005 gcc_checking_assert (gimple_range_ssa_p (name
));
1007 // Start with any known range
1008 range_of_stmt (r
, SSA_NAME_DEF_STMT (name
), name
);
1010 // Now see if there is any on_entry value which may refine it.
1011 if (m_cache
.block_range (entry_range
, bb
, name
))
1012 r
.intersect (entry_range
);
1015 // Calculate the range for NAME at the end of block BB and return it in R.
1016 // Return false if no range can be calculated.
1019 gimple_ranger::range_on_exit (irange
&r
, basic_block bb
, tree name
)
1021 // on-exit from the exit block?
1022 gcc_checking_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1023 gcc_checking_assert (gimple_range_ssa_p (name
));
1025 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1026 basic_block def_bb
= gimple_bb (s
);
1027 // If this is not the definition block, get the range on the last stmt in
1028 // the block... if there is one.
1031 // If there is no statement provided, get the range_on_entry for this block.
1033 range_of_expr (r
, name
, s
);
1036 range_on_entry (r
, bb
, name
);
1037 // See if there was a deref in this block, if applicable
1038 if (!cfun
->can_throw_non_call_exceptions
&& r
.varying_p () &&
1039 m_cache
.m_non_null
.non_null_deref_p (name
, bb
))
1040 r
= range_nonzero (TREE_TYPE (name
));
1042 gcc_checking_assert (r
.undefined_p ()
1043 || range_compatible_p (r
.type (), TREE_TYPE (name
)));
1046 // Calculate a range for NAME on edge E and return it in R.
1049 gimple_ranger::range_on_edge (irange
&r
, edge e
, tree name
)
1051 int_range_max edge_range
;
1052 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name
)));
1054 // PHI arguments can be constants, catch these here.
1055 if (!gimple_range_ssa_p (name
))
1056 return range_of_expr (r
, name
);
1058 range_on_exit (r
, e
->src
, name
);
1059 gcc_checking_assert (r
.undefined_p ()
1060 || range_compatible_p (r
.type(), TREE_TYPE (name
)));
1062 // Check to see if NAME is defined on edge e.
1063 if (m_cache
.outgoing_edge_range_p (edge_range
, e
, name
))
1064 r
.intersect (edge_range
);
1069 // fold_range wrapper for range_of_stmt to use as an internal client.
1072 gimple_ranger::fold_range_internal (irange
&r
, gimple
*s
, tree name
)
1075 fur_source
src (this, &m_cache
, NULL
, s
);
1076 return f
.fold_stmt (r
, s
, src
, name
);
1079 // Calculate a range for statement S and return it in R. If NAME is
1080 // provided it represents the SSA_NAME on the LHS of the statement.
1081 // It is only required if there is more than one lhs/output. Check
1082 // the global cache for NAME first to see if the evaluation can be
1083 // avoided. If a range cannot be calculated, return false and UNDEFINED.
1086 gimple_ranger::range_of_stmt (irange
&r
, gimple
*s
, tree name
)
1091 name
= gimple_get_lhs (s
);
1093 // If no name, simply call the base routine.
1095 return fold_range_internal (r
, s
, NULL_TREE
);
1097 if (!gimple_range_ssa_p (name
))
1100 // Check if the stmt has already been processed, and is not stale.
1101 if (m_cache
.get_non_stale_global_range (r
, name
))
1104 // Otherwise calculate a new value.
1106 fold_range_internal (tmp
, s
, name
);
1108 // Combine the new value with the old value. This is required because
1109 // the way value propagation works, when the IL changes on the fly we
1110 // can sometimes get different results. See PR 97741.
1112 m_cache
.set_global_range (name
, r
);
1117 // This routine will export whatever global ranges are known to GCC
1118 // SSA_RANGE_NAME_INFO fields.
1121 gimple_ranger::export_global_ranges ()
1127 fprintf (dump_file
, "Exported global range table\n");
1128 fprintf (dump_file
, "===========================\n");
1131 for ( x
= 1; x
< num_ssa_names
; x
++)
1133 tree name
= ssa_name (x
);
1134 if (name
&& !SSA_NAME_IN_FREE_LIST (name
)
1135 && gimple_range_ssa_p (name
)
1136 && m_cache
.get_global_range (r
, name
)
1139 // Make sure the new range is a subset of the old range.
1140 int_range_max old_range
;
1141 old_range
= gimple_range_global (name
);
1142 old_range
.intersect (r
);
1143 /* Disable this while we fix tree-ssa/pr61743-2.c. */
1144 //gcc_checking_assert (old_range == r);
1146 // WTF? Can't write non-null pointer ranges?? stupid set_range_info!
1147 if (!POINTER_TYPE_P (TREE_TYPE (name
)) && !r
.undefined_p ())
1150 set_range_info (name
, vr
);
1153 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1154 fprintf (dump_file
, " --> ");
1155 vr
.dump (dump_file
);
1156 fprintf (dump_file
, "\n");
1157 fprintf (dump_file
, " irange : ");
1159 fprintf (dump_file
, "\n");
1166 // Print the known table values to file F.
1169 gimple_ranger::dump (FILE *f
)
1173 FOR_EACH_BB_FN (bb
, cfun
)
1178 int_range_max range
;
1179 fprintf (f
, "\n=========== BB %d ============\n", bb
->index
);
1180 m_cache
.dump (f
, bb
);
1182 dump_bb (f
, bb
, 4, TDF_NONE
);
1184 // Now find any globals defined in this block.
1185 for (x
= 1; x
< num_ssa_names
; x
++)
1187 tree name
= ssa_name (x
);
1188 if (gimple_range_ssa_p (name
) && SSA_NAME_DEF_STMT (name
) &&
1189 gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
&&
1190 m_cache
.get_global_range (range
, name
))
1192 if (!range
.varying_p ())
1194 print_generic_expr (f
, name
, TDF_SLIM
);
1203 // And now outgoing edges, if they define anything.
1204 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1206 for (x
= 1; x
< num_ssa_names
; x
++)
1208 tree name
= gimple_range_ssa_p (ssa_name (x
));
1209 if (name
&& m_cache
.outgoing_edge_range_p (range
, e
, name
))
1211 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1212 // Only print the range if this is the def block, or
1213 // the on entry cache for either end of the edge is
1215 if ((s
&& bb
== gimple_bb (s
)) ||
1216 m_cache
.block_range (range
, bb
, name
, false) ||
1217 m_cache
.block_range (range
, e
->dest
, name
, false))
1219 range_on_edge (range
, e
, name
);
1220 if (!range
.varying_p ())
1222 fprintf (f
, "%d->%d ", e
->src
->index
,
1225 if (e
->flags
& EDGE_TRUE_VALUE
)
1226 fprintf (f
, " (T)%c", c
);
1227 else if (e
->flags
& EDGE_FALSE_VALUE
)
1228 fprintf (f
, " (F)%c", c
);
1231 print_generic_expr (f
, name
, TDF_SLIM
);
1232 fprintf(f
, " : \t");
1242 m_cache
.dump (dump_file
, (dump_flags
& TDF_DETAILS
) != 0);
1245 // If SCEV has any information about phi node NAME, return it as a range in R.
1248 fold_using_range::range_of_ssa_name_with_loop_info (irange
&r
, tree name
,
1249 class loop
*l
, gphi
*phi
,
1252 gcc_checking_assert (TREE_CODE (name
) == SSA_NAME
);
1253 tree min
, max
, type
= TREE_TYPE (name
);
1254 if (bounds_of_var_in_loop (&min
, &max
, src
.m_query
, l
, phi
, name
))
1256 if (TREE_CODE (min
) != INTEGER_CST
)
1259 && src
.m_query
->range_of_expr (r
, min
, phi
)
1260 && !r
.undefined_p ())
1261 min
= wide_int_to_tree (type
, r
.lower_bound ());
1263 min
= vrp_val_min (type
);
1265 if (TREE_CODE (max
) != INTEGER_CST
)
1268 && src
.m_query
->range_of_expr (r
, max
, phi
)
1269 && !r
.undefined_p ())
1270 max
= wide_int_to_tree (type
, r
.upper_bound ());
1272 max
= vrp_val_max (type
);
1277 r
.set_varying (type
);
1280 // --------------------------------------------------------------------------
1281 // trace_ranger implementation.
1284 trace_ranger::trace_ranger ()
1290 // If dumping, return true and print the prefix for the next output line.
1293 trace_ranger::dumping (unsigned counter
, bool trailing
)
1295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1297 // Print counter index as well as INDENT spaces.
1299 fprintf (dump_file
, " %-7u ", counter
);
1301 fprintf (dump_file
, " ");
1303 for (x
= 0; x
< indent
; x
++)
1304 fputc (' ', dump_file
);
1310 // After calling a routine, if dumping, print the CALLER, NAME, and RESULT,
1311 // returning RESULT.
1314 trace_ranger::trailer (unsigned counter
, const char *caller
, bool result
,
1315 tree name
, const irange
&r
)
1317 if (dumping (counter
, true))
1320 fputs(result
? "TRUE : " : "FALSE : ", dump_file
);
1321 fprintf (dump_file
, "(%u) ", counter
);
1322 fputs (caller
, dump_file
);
1323 fputs (" (",dump_file
);
1325 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1326 fputs (") ",dump_file
);
1330 fputc('\n', dump_file
);
1333 fputc('\n', dump_file
);
1334 // Marks the end of a request.
1336 fputc('\n', dump_file
);
1341 // Tracing version of range_on_edge. Call it with printing wrappers.
1344 trace_ranger::range_on_edge (irange
&r
, edge e
, tree name
)
1346 unsigned idx
= ++trace_count
;
1349 fprintf (dump_file
, "range_on_edge (");
1350 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1351 fprintf (dump_file
, ") on edge %d->%d\n", e
->src
->index
, e
->dest
->index
);
1355 bool res
= gimple_ranger::range_on_edge (r
, e
, name
);
1356 trailer (idx
, "range_on_edge", true, name
, r
);
1360 // Tracing version of range_on_entry. Call it with printing wrappers.
1363 trace_ranger::range_on_entry (irange
&r
, basic_block bb
, tree name
)
1365 unsigned idx
= ++trace_count
;
1368 fprintf (dump_file
, "range_on_entry (");
1369 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1370 fprintf (dump_file
, ") to BB %d\n", bb
->index
);
1374 gimple_ranger::range_on_entry (r
, bb
, name
);
1376 trailer (idx
, "range_on_entry", true, name
, r
);
1379 // Tracing version of range_on_exit. Call it with printing wrappers.
1382 trace_ranger::range_on_exit (irange
&r
, basic_block bb
, tree name
)
1384 unsigned idx
= ++trace_count
;
1387 fprintf (dump_file
, "range_on_exit (");
1388 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1389 fprintf (dump_file
, ") from BB %d\n", bb
->index
);
1393 gimple_ranger::range_on_exit (r
, bb
, name
);
1395 trailer (idx
, "range_on_exit", true, name
, r
);
1398 // Tracing version of range_of_stmt. Call it with printing wrappers.
1401 trace_ranger::range_of_stmt (irange
&r
, gimple
*s
, tree name
)
1404 unsigned idx
= ++trace_count
;
1407 fprintf (dump_file
, "range_of_stmt (");
1409 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1410 fputs (") at stmt ", dump_file
);
1411 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
1415 res
= gimple_ranger::range_of_stmt (r
, s
, name
);
1417 return trailer (idx
, "range_of_stmt", res
, name
, r
);
1420 // Tracing version of range_of_expr. Call it with printing wrappers.
1423 trace_ranger::range_of_expr (irange
&r
, tree name
, gimple
*s
)
1426 unsigned idx
= ++trace_count
;
1429 fprintf (dump_file
, "range_of_expr(");
1430 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1431 fputs (")", dump_file
);
1434 fputs (" at stmt ", dump_file
);
1435 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
1438 fputs ("\n", dump_file
);
1442 res
= gimple_ranger::range_of_expr (r
, name
, s
);
1444 return trailer (idx
, "range_of_expr", res
, name
, r
);