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 calculated, return FALSE.
55 fur_source::get_operand (irange
&r
, tree expr
)
57 return get_range_query (cfun
)->range_of_expr (r
, expr
);
60 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
61 // range_query to get the range on the edge.
64 fur_source::get_phi_operand (irange
&r
, tree expr
, edge e
)
66 return get_range_query (cfun
)->range_on_edge (r
, e
, expr
);
69 // Default is to not register any dependencies from fold_using_range.
72 fur_source::register_dependency (tree lhs ATTRIBUTE_UNUSED
,
73 tree rhs ATTRIBUTE_UNUSED
)
77 // Default object is the current range query.
82 return get_range_query (cfun
);
85 // This version of fur_source will pick a range up off an edge.
87 class fur_edge
: public fur_source
90 fur_edge (edge e
, range_query
*q
= NULL
);
91 virtual bool get_operand (irange
&r
, tree expr
) OVERRIDE
;
92 virtual bool get_phi_operand (irange
&r
, tree expr
, edge e
) OVERRIDE
;
93 virtual range_query
*query () OVERRIDE
;
99 // Instantiate an edge based fur_source.
102 fur_edge::fur_edge (edge e
, range_query
*q
)
108 m_query
= get_range_query (cfun
);
111 // Get the value of EXPR on edge m_edge.
114 fur_edge::get_operand (irange
&r
, tree expr
)
116 return m_query
->range_on_edge (r
, m_edge
, expr
);
119 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
120 // range_query to get the range on the edge.
123 fur_edge::get_phi_operand (irange
&r
, tree expr
, edge e
)
125 // edge to edge recalculations not supoprted yet, until we sort it out.
126 gcc_checking_assert (e
== m_edge
);
127 return m_query
->range_on_edge (r
, e
, expr
);
130 // Return the current range_query object.
139 // Instantiate a stmt based fur_source.
142 fur_stmt::fur_stmt (gimple
*s
, range_query
*q
)
148 m_query
= get_global_range_query ();
151 // Retirenve range of EXPR as it occurs as a use on stmt M_STMT.
154 fur_stmt::get_operand (irange
&r
, tree expr
)
156 return m_query
->range_of_expr (r
, expr
, m_stmt
);
159 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
160 // range_query to get the range on the edge.
163 fur_stmt::get_phi_operand (irange
&r
, tree expr
, edge e
)
165 // Pick up the range of expr from edge E.
166 fur_edge
e_src (e
, m_query
);
167 return e_src
.get_operand (r
, expr
);
170 // Return the current range_query object.
178 // This version of fur_source will pick a range from a stmt, and register
179 // also dependencies via a gori_compute object. This is mostly an internal API.
181 class fur_depend
: public fur_stmt
184 fur_depend (gimple
*s
, gori_compute
*gori
, range_query
*q
= NULL
);
185 virtual void register_dependency (tree lhs
, tree rhs
) OVERRIDE
;
187 gori_compute
*m_gori
;
190 // Instantiate a stmt based fur_source witrh a GORI object
192 fur_depend::fur_depend (gimple
*s
, gori_compute
*gori
, range_query
*q
)
195 gcc_checking_assert (gori
);
200 // find and add any dependnecy between LHS and RHS
203 fur_depend::register_dependency (tree lhs
, tree rhs
)
205 m_gori
->register_dependency (lhs
, rhs
);
209 // This version of fur_source will pick a range up from a list of ranges
210 // supplied by the caller.
212 class fur_list
: public fur_source
215 fur_list (irange
&r1
);
216 fur_list (irange
&r1
, irange
&r2
);
217 fur_list (unsigned num
, irange
*list
);
218 virtual bool get_operand (irange
&r
, tree expr
) OVERRIDE
;
219 virtual bool get_phi_operand (irange
&r
, tree expr
, edge e
) OVERRIDE
;
221 int_range_max m_local
[2];
227 // One range supplied for unary operations.
229 fur_list::fur_list (irange
&r1
)
237 // Two ranges supplied for binary operations.
239 fur_list::fur_list (irange
&r1
, irange
&r2
)
248 // Arbitrary number of ranges in a vector.
250 fur_list::fur_list (unsigned num
, irange
*list
)
257 // Get the next operand from the vector, ensure types are compatible,
260 fur_list::get_operand (irange
&r
, tree expr
)
262 if (m_index
>= m_limit
)
263 return get_range_query (cfun
)->range_of_expr (r
, expr
);
264 r
= m_list
[m_index
++];
265 gcc_checking_assert (range_compatible_p (TREE_TYPE (expr
), r
.type ()));
269 // This will simply pick the next operand from the vector.
271 fur_list::get_phi_operand (irange
&r
, tree expr
, edge e ATTRIBUTE_UNUSED
)
273 return get_operand (r
, expr
);
276 // Fold stmt S into range R using R1 as the first operand.
279 fold_range (irange
&r
, gimple
*s
, irange
&r1
)
283 return f
.fold_stmt (r
, s
, src
);
286 // Fold stmt S into range R using R1 and R2 as the first two operands.
289 fold_range (irange
&r
, gimple
*s
, irange
&r1
, irange
&r2
)
292 fur_list
src (r1
, r2
);
293 return f
.fold_stmt (r
, s
, src
);
297 // Fold stmt S into range R using NUM_ELEMENTS from VECTOR as the initial
298 // operands encountered.
301 fold_range (irange
&r
, gimple
*s
, unsigned num_elements
, irange
*vector
)
304 fur_list
src (num_elements
, vector
);
305 return f
.fold_stmt (r
, s
, src
);
309 // Fold stmt S into range R using range query Q.
312 fold_range (irange
&r
, gimple
*s
, range_query
*q
)
316 return f
.fold_stmt (r
, s
, src
);
319 // Recalculate stmt S into R using range query Q as if it were on edge ON_EDGE.
322 fold_range (irange
&r
, gimple
*s
, edge on_edge
, range_query
*q
)
325 fur_edge
src (on_edge
, q
);
326 return f
.fold_stmt (r
, s
, src
);
329 // -------------------------------------------------------------------------
331 // Adjust the range for a pointer difference where the operands came
334 // This notices the following sequence:
336 // def = __builtin_memchr (arg, 0, sz)
339 // The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
342 adjust_pointer_diff_expr (irange
&res
, const gimple
*diff_stmt
)
344 tree op0
= gimple_assign_rhs1 (diff_stmt
);
345 tree op1
= gimple_assign_rhs2 (diff_stmt
);
346 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
347 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
350 if (TREE_CODE (op0
) == SSA_NAME
351 && TREE_CODE (op1
) == SSA_NAME
352 && (call
= SSA_NAME_DEF_STMT (op0
))
353 && is_gimple_call (call
)
354 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
355 && TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
356 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
357 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
358 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
359 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
360 && vrp_operand_equal_p (op1
, gimple_call_arg (call
, 0))
361 && integer_zerop (gimple_call_arg (call
, 1)))
363 tree max
= vrp_val_max (ptrdiff_type_node
);
364 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
365 tree expr_type
= gimple_expr_type (diff_stmt
);
366 tree range_min
= build_zero_cst (expr_type
);
367 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
368 int_range
<2> r (range_min
, range_max
);
373 // This function looks for situations when walking the use/def chains
374 // may provide additonal contextual range information not exposed on
375 // this statement. Like knowing the IMAGPART return value from a
376 // builtin function is a boolean result.
378 // We should rework how we're called, as we have an op_unknown entry
379 // for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this
380 // function gets called.
383 gimple_range_adjustment (irange
&res
, const gimple
*stmt
)
385 switch (gimple_expr_code (stmt
))
387 case POINTER_DIFF_EXPR
:
388 adjust_pointer_diff_expr (res
, stmt
);
393 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
394 if (TREE_CODE (name
) == SSA_NAME
)
396 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
397 if (def_stmt
&& is_gimple_call (def_stmt
)
398 && gimple_call_internal_p (def_stmt
))
400 switch (gimple_call_internal_fn (def_stmt
))
402 case IFN_ADD_OVERFLOW
:
403 case IFN_SUB_OVERFLOW
:
404 case IFN_MUL_OVERFLOW
:
405 case IFN_ATOMIC_COMPARE_EXCHANGE
:
408 r
.set_varying (boolean_type_node
);
409 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
410 range_cast (r
, type
);
426 // Return the base of the RHS of an assignment.
429 gimple_range_base_of_assignment (const gimple
*stmt
)
431 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
432 tree op1
= gimple_assign_rhs1 (stmt
);
433 if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
434 return get_base_address (TREE_OPERAND (op1
, 0));
438 // Return the first operand of this statement if it is a valid operand
439 // supported by ranges, otherwise return NULL_TREE. Special case is
440 // &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr.
443 gimple_range_operand1 (const gimple
*stmt
)
445 gcc_checking_assert (gimple_range_handler (stmt
));
447 switch (gimple_code (stmt
))
450 return gimple_cond_lhs (stmt
);
453 tree base
= gimple_range_base_of_assignment (stmt
);
454 if (base
&& TREE_CODE (base
) == MEM_REF
)
456 // If the base address is an SSA_NAME, we return it
457 // here. This allows processing of the range of that
458 // name, while the rest of the expression is simply
459 // ignored. The code in range_ops will see the
460 // ADDR_EXPR and do the right thing.
461 tree ssa
= TREE_OPERAND (base
, 0);
462 if (TREE_CODE (ssa
) == SSA_NAME
)
473 // Return the second operand of statement STMT, otherwise return NULL_TREE.
476 gimple_range_operand2 (const gimple
*stmt
)
478 gcc_checking_assert (gimple_range_handler (stmt
));
480 switch (gimple_code (stmt
))
483 return gimple_cond_rhs (stmt
);
485 if (gimple_num_ops (stmt
) >= 3)
486 return gimple_assign_rhs2 (stmt
);
493 // Calculate what we can determine of the range of this unary
494 // statement's operand if the lhs of the expression has the range
495 // LHS_RANGE. Return false if nothing can be determined.
498 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
, const irange
&lhs_range
)
500 gcc_checking_assert (gimple_num_ops (stmt
) < 3);
502 // An empty range is viral.
503 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
504 if (lhs_range
.undefined_p ())
509 // Unary operations require the type of the first operand in the
510 // second range position.
511 int_range
<2> type_range (type
);
512 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
516 // Calculate what we can determine of the range of this statement's
517 // first operand if the lhs of the expression has the range LHS_RANGE
518 // and the second operand has the range OP2_RANGE. Return false if
519 // nothing can be determined.
522 gimple_range_calc_op1 (irange
&r
, const gimple
*stmt
,
523 const irange
&lhs_range
, const irange
&op2_range
)
525 // Unary operation are allowed to pass a range in for second operand
526 // as there are often additional restrictions beyond the type which
527 // can be imposed. See operator_cast::op1_range().
528 tree type
= TREE_TYPE (gimple_range_operand1 (stmt
));
529 // An empty range is viral.
530 if (op2_range
.undefined_p () || lhs_range
.undefined_p ())
535 return gimple_range_handler (stmt
)->op1_range (r
, type
, lhs_range
,
539 // Calculate what we can determine of the range of this statement's
540 // second operand if the lhs of the expression has the range LHS_RANGE
541 // and the first operand has the range OP1_RANGE. Return false if
542 // nothing can be determined.
545 gimple_range_calc_op2 (irange
&r
, const gimple
*stmt
,
546 const irange
&lhs_range
, const irange
&op1_range
)
548 tree type
= TREE_TYPE (gimple_range_operand2 (stmt
));
549 // An empty range is viral.
550 if (op1_range
.undefined_p () || lhs_range
.undefined_p ())
555 return gimple_range_handler (stmt
)->op2_range (r
, type
, lhs_range
,
559 // Calculate a range for statement S and return it in R. If NAME is provided it
560 // represents the SSA_NAME on the LHS of the statement. It is only required
561 // if there is more than one lhs/output. If a range cannot
562 // be calculated, return false.
565 fold_using_range::fold_stmt (irange
&r
, gimple
*s
, fur_source
&src
, tree name
)
568 // If name and S are specified, make sure it is an LHS of S.
569 gcc_checking_assert (!name
|| !gimple_get_lhs (s
) ||
570 name
== gimple_get_lhs (s
));
573 name
= gimple_get_lhs (s
);
575 // Process addresses.
576 if (gimple_code (s
) == GIMPLE_ASSIGN
577 && gimple_assign_rhs_code (s
) == ADDR_EXPR
)
578 return range_of_address (r
, s
, src
);
580 if (gimple_range_handler (s
))
581 res
= range_of_range_op (r
, s
, src
);
582 else if (is_a
<gphi
*>(s
))
583 res
= range_of_phi (r
, as_a
<gphi
*> (s
), src
);
584 else if (is_a
<gcall
*>(s
))
585 res
= range_of_call (r
, as_a
<gcall
*> (s
), src
);
586 else if (is_a
<gassign
*> (s
) && gimple_assign_rhs_code (s
) == COND_EXPR
)
587 res
= range_of_cond_expr (r
, as_a
<gassign
*> (s
), src
);
591 // If no name is specified, try the expression kind.
594 tree t
= gimple_expr_type (s
);
595 if (!irange::supports_type_p (t
))
600 if (!gimple_range_ssa_p (name
))
602 // We don't understand the stmt, so return the global range.
603 r
= gimple_range_global (name
);
607 if (r
.undefined_p ())
610 // We sometimes get compatible types copied from operands, make sure
611 // the correct type is being returned.
612 if (name
&& TREE_TYPE (name
) != r
.type ())
614 gcc_checking_assert (range_compatible_p (r
.type (), TREE_TYPE (name
)));
615 range_cast (r
, TREE_TYPE (name
));
620 // Calculate a range for range_op statement S and return it in R. If any
621 // If a range cannot be calculated, return false.
624 fold_using_range::range_of_range_op (irange
&r
, gimple
*s
, fur_source
&src
)
626 int_range_max range1
, range2
;
627 tree type
= gimple_expr_type (s
);
628 range_operator
*handler
= gimple_range_handler (s
);
629 gcc_checking_assert (handler
);
630 gcc_checking_assert (irange::supports_type_p (type
));
632 tree lhs
= gimple_get_lhs (s
);
633 tree op1
= gimple_range_operand1 (s
);
634 tree op2
= gimple_range_operand2 (s
);
636 if (src
.get_operand (range1
, op1
))
640 // Fold range, and register any dependency if available.
641 int_range
<2> r2 (type
);
642 handler
->fold_range (r
, type
, range1
, r2
);
644 src
.register_dependency (lhs
, op1
);
646 else if (src
.get_operand (range2
, op2
))
648 // Fold range, and register any dependency if available.
649 handler
->fold_range (r
, type
, range1
, range2
);
652 src
.register_dependency (lhs
, op1
);
653 src
.register_dependency (lhs
, op2
);
657 r
.set_varying (type
);
660 r
.set_varying (type
);
661 // Make certain range-op adjustments that aren't handled any other way.
662 gimple_range_adjustment (r
, s
);
666 // Calculate the range of an assignment containing an ADDR_EXPR.
667 // Return the range in R.
668 // If a range cannot be calculated, set it to VARYING and return true.
671 fold_using_range::range_of_address (irange
&r
, gimple
*stmt
, fur_source
&src
)
673 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
674 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
);
676 bool strict_overflow_p
;
677 tree expr
= gimple_assign_rhs1 (stmt
);
678 poly_int64 bitsize
, bitpos
;
681 int unsignedp
, reversep
, volatilep
;
682 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
683 &bitpos
, &offset
, &mode
, &unsignedp
,
684 &reversep
, &volatilep
);
687 if (base
!= NULL_TREE
688 && TREE_CODE (base
) == MEM_REF
689 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
691 tree ssa
= TREE_OPERAND (base
, 0);
692 tree lhs
= gimple_get_lhs (stmt
);
693 if (lhs
&& gimple_range_ssa_p (ssa
))
694 src
.register_dependency (lhs
, ssa
);
695 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (ssa
)));
696 src
.get_operand (r
, ssa
);
697 range_cast (r
, TREE_TYPE (gimple_assign_rhs1 (stmt
)));
699 poly_offset_int off
= 0;
700 bool off_cst
= false;
701 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
703 off
= mem_ref_offset (base
);
705 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
707 off
<<= LOG2_BITS_PER_UNIT
;
711 /* If &X->a is equal to X, the range of X is the result. */
712 if (off_cst
&& known_eq (off
, 0))
714 else if (flag_delete_null_pointer_checks
715 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
)))
717 /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
718 allow going from non-NULL pointer to NULL. */
719 if(!range_includes_zero_p (&r
))
722 /* If MEM_REF has a "positive" offset, consider it non-NULL
723 always, for -fdelete-null-pointer-checks also "negative"
724 ones. Punt for unknown offsets (e.g. variable ones). */
725 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
728 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
730 r
= range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
733 r
= int_range
<2> (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
738 if (tree_single_nonzero_warnv_p (expr
, &strict_overflow_p
))
740 r
= range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
744 // Otherwise return varying.
745 r
= int_range
<2> (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
749 // Calculate a range for phi statement S and return it in R.
750 // If a range cannot be calculated, return false.
753 fold_using_range::range_of_phi (irange
&r
, gphi
*phi
, fur_source
&src
)
755 tree phi_def
= gimple_phi_result (phi
);
756 tree type
= TREE_TYPE (phi_def
);
757 int_range_max arg_range
;
760 if (!irange::supports_type_p (type
))
763 // Start with an empty range, unioning in each argument's range.
765 for (x
= 0; x
< gimple_phi_num_args (phi
); x
++)
767 tree arg
= gimple_phi_arg_def (phi
, x
);
768 edge e
= gimple_phi_arg_edge (phi
, x
);
770 // Register potential dependencies for stale value tracking.
771 if (gimple_range_ssa_p (arg
))
772 src
.register_dependency (phi_def
, arg
);
774 // Get the range of the argument on its edge.
775 src
.get_phi_operand (arg_range
, arg
, e
);
776 // If we're recomputing the argument elsewhere, try to refine it.
777 r
.union_ (arg_range
);
778 // Once the value reaches varying, stop looking.
783 // If SCEV is available, query if this PHI has any knonwn values.
784 if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def
)))
786 value_range loop_range
;
787 class loop
*l
= loop_containing_stmt (phi
);
788 if (l
&& loop_outer (l
))
790 range_of_ssa_name_with_loop_info (loop_range
, phi_def
, l
, phi
, src
);
791 if (!loop_range
.varying_p ())
793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
795 fprintf (dump_file
, " Loops range found for ");
796 print_generic_expr (dump_file
, phi_def
, TDF_SLIM
);
797 fprintf (dump_file
, ": ");
798 loop_range
.dump (dump_file
);
799 fprintf (dump_file
, " and calculated range :");
801 fprintf (dump_file
, "\n");
803 r
.intersect (loop_range
);
811 // Calculate a range for call statement S and return it in R.
812 // If a range cannot be calculated, return false.
815 fold_using_range::range_of_call (irange
&r
, gcall
*call
, fur_source
&src
)
817 tree type
= gimple_call_return_type (call
);
818 tree lhs
= gimple_call_lhs (call
);
819 bool strict_overflow_p
;
821 if (!irange::supports_type_p (type
))
824 if (range_of_builtin_call (r
, call
, src
))
826 else if (gimple_stmt_nonnegative_warnv_p (call
, &strict_overflow_p
))
827 r
.set (build_int_cst (type
, 0), TYPE_MAX_VALUE (type
));
828 else if (gimple_call_nonnull_result_p (call
)
829 || gimple_call_nonnull_arg (call
))
830 r
= range_nonzero (type
);
832 r
.set_varying (type
);
834 // If there is an LHS, intersect that with what is known.
838 def
= gimple_range_global (lhs
);
844 // Return the range of a __builtin_ubsan* in CALL and set it in R.
845 // CODE is the type of ubsan call (PLUS_EXPR, MINUS_EXPR or
849 fold_using_range::range_of_builtin_ubsan_call (irange
&r
, gcall
*call
,
850 tree_code code
, fur_source
&src
)
852 gcc_checking_assert (code
== PLUS_EXPR
|| code
== MINUS_EXPR
853 || code
== MULT_EXPR
);
854 tree type
= gimple_call_return_type (call
);
855 range_operator
*op
= range_op_handler (code
, type
);
856 gcc_checking_assert (op
);
857 int_range_max ir0
, ir1
;
858 tree arg0
= gimple_call_arg (call
, 0);
859 tree arg1
= gimple_call_arg (call
, 1);
860 src
.get_operand (ir0
, arg0
);
861 src
.get_operand (ir1
, arg1
);
863 bool saved_flag_wrapv
= flag_wrapv
;
864 // Pretend the arithmetic is wrapping. If there is any overflow,
865 // we'll complain, but will actually do wrapping operation.
867 op
->fold_range (r
, type
, ir0
, ir1
);
868 flag_wrapv
= saved_flag_wrapv
;
870 // If for both arguments vrp_valueize returned non-NULL, this should
871 // have been already folded and if not, it wasn't folded because of
872 // overflow. Avoid removing the UBSAN_CHECK_* calls in that case.
873 if (r
.singleton_p ())
874 r
.set_varying (type
);
877 // For a builtin in CALL, return a range in R if known and return
878 // TRUE. Otherwise return FALSE.
881 fold_using_range::range_of_builtin_call (irange
&r
, gcall
*call
,
884 combined_fn func
= gimple_call_combined_fn (call
);
885 if (func
== CFN_LAST
)
888 tree type
= gimple_call_return_type (call
);
890 int mini
, maxi
, zerov
= 0, prec
;
891 scalar_int_mode mode
;
895 case CFN_BUILT_IN_CONSTANT_P
:
896 if (cfun
->after_inlining
)
902 arg
= gimple_call_arg (call
, 0);
903 if (src
.get_operand (r
, arg
) && r
.singleton_p ())
905 r
.set (build_one_cst (type
), build_one_cst (type
));
912 // __builtin_ffs* and __builtin_popcount* return [0, prec].
913 arg
= gimple_call_arg (call
, 0);
914 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
917 src
.get_operand (r
, arg
);
918 // If arg is non-zero, then ffs or popcount are non-zero.
919 if (!range_includes_zero_p (&r
))
921 // If some high bits are known to be zero, decrease the maximum.
922 if (!r
.undefined_p ())
924 if (TYPE_SIGN (r
.type ()) == SIGNED
)
925 range_cast (r
, unsigned_type_for (r
.type ()));
926 wide_int max
= r
.upper_bound ();
927 maxi
= wi::floor_log2 (max
) + 1;
929 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
933 r
.set (build_zero_cst (type
), build_one_cst (type
));
937 // __builtin_c[lt]z* return [0, prec-1], except when the
938 // argument is 0, but that is undefined behavior.
940 // For __builtin_c[lt]z* consider argument of 0 always undefined
941 // behavior, for internal fns depending on C?Z_DEFINED_VALUE_AT_ZERO.
942 arg
= gimple_call_arg (call
, 0);
943 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
946 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
947 if (gimple_call_internal_p (call
))
949 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
950 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
952 // Only handle the single common value.
956 // Magic value to give up, unless we can prove arg is non-zero.
961 src
.get_operand (r
, arg
);
962 // From clz of minimum we can compute result maximum.
963 if (r
.constant_p () && !r
.varying_p ())
965 int newmaxi
= prec
- 1 - wi::floor_log2 (r
.lower_bound ());
966 // Argument is unsigned, so do nothing if it is [0, ...] range.
973 else if (!range_includes_zero_p (&r
))
980 // From clz of maximum we can compute result minimum.
983 int newmini
= prec
- 1 - wi::floor_log2 (r
.upper_bound ());
986 // Argument range is [0, 0]. If CLZ_DEFINED_VALUE_AT_ZERO
987 // is 2 with VALUE of prec, return [prec, prec], otherwise
997 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
1001 // __builtin_ctz* return [0, prec-1], except for when the
1002 // argument is 0, but that is undefined behavior.
1004 // For __builtin_ctz* consider argument of 0 always undefined
1005 // behavior, for internal fns depending on CTZ_DEFINED_VALUE_AT_ZERO.
1006 arg
= gimple_call_arg (call
, 0);
1007 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1010 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1011 if (gimple_call_internal_p (call
))
1013 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1014 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
1016 // Handle only the two common values.
1019 else if (zerov
== prec
)
1022 // Magic value to give up, unless we can prove arg is non-zero.
1026 src
.get_operand (r
, arg
);
1027 if (!r
.undefined_p ())
1029 if (r
.lower_bound () != 0)
1034 // If some high bits are known to be zero, we can decrease
1036 wide_int max
= r
.upper_bound ();
1039 // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO
1040 // is 2 with value -1 or prec, return [-1, -1] or [prec, prec].
1041 // Otherwise ignore the range.
1044 else if (maxi
== prec
)
1047 // If value at zero is prec and 0 is in the range, we can't lower
1048 // the upper bound. We could create two separate ranges though,
1049 // [0,floor_log2(max)][prec,prec] though.
1050 else if (maxi
!= prec
)
1051 maxi
= wi::floor_log2 (max
);
1055 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
1059 arg
= gimple_call_arg (call
, 0);
1060 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1061 r
.set (build_int_cst (type
, 0), build_int_cst (type
, prec
- 1));
1063 case CFN_UBSAN_CHECK_ADD
:
1064 range_of_builtin_ubsan_call (r
, call
, PLUS_EXPR
, src
);
1066 case CFN_UBSAN_CHECK_SUB
:
1067 range_of_builtin_ubsan_call (r
, call
, MINUS_EXPR
, src
);
1069 case CFN_UBSAN_CHECK_MUL
:
1070 range_of_builtin_ubsan_call (r
, call
, MULT_EXPR
, src
);
1073 case CFN_GOACC_DIM_SIZE
:
1074 case CFN_GOACC_DIM_POS
:
1075 // Optimizing these two internal functions helps the loop
1076 // optimizer eliminate outer comparisons. Size is [1,N]
1077 // and pos is [0,N-1].
1079 bool is_pos
= func
== CFN_GOACC_DIM_POS
;
1080 int axis
= oacc_get_ifn_dim_arg (call
);
1081 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1083 // If it's dynamic, the backend might know a hardware limitation.
1084 size
= targetm
.goacc
.dim_limit (axis
);
1086 r
.set (build_int_cst (type
, is_pos
? 0 : 1),
1088 ? build_int_cst (type
, size
- is_pos
) : vrp_val_max (type
));
1092 case CFN_BUILT_IN_STRLEN
:
1093 if (tree lhs
= gimple_call_lhs (call
))
1094 if (ptrdiff_type_node
1095 && (TYPE_PRECISION (ptrdiff_type_node
)
1096 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1098 tree type
= TREE_TYPE (lhs
);
1099 tree max
= vrp_val_max (ptrdiff_type_node
);
1101 = wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1102 tree range_min
= build_zero_cst (type
);
1103 // To account for the terminating NULL, the maximum length
1104 // is one less than the maximum array size, which in turn
1105 // is one less than PTRDIFF_MAX (or SIZE_MAX where it's
1106 // smaller than the former type).
1107 // FIXME: Use max_object_size() - 1 here.
1108 tree range_max
= wide_int_to_tree (type
, wmax
- 2);
1109 r
.set (range_min
, range_max
);
1120 // Calculate a range for COND_EXPR statement S and return it in R.
1121 // If a range cannot be calculated, return false.
1124 fold_using_range::range_of_cond_expr (irange
&r
, gassign
*s
, fur_source
&src
)
1126 int_range_max cond_range
, range1
, range2
;
1127 tree cond
= gimple_assign_rhs1 (s
);
1128 tree op1
= gimple_assign_rhs2 (s
);
1129 tree op2
= gimple_assign_rhs3 (s
);
1131 gcc_checking_assert (gimple_assign_rhs_code (s
) == COND_EXPR
);
1132 gcc_checking_assert (useless_type_conversion_p (TREE_TYPE (op1
),
1134 if (!irange::supports_type_p (TREE_TYPE (op1
)))
1137 src
.get_operand (cond_range
, cond
);
1138 src
.get_operand (range1
, op1
);
1139 src
.get_operand (range2
, op2
);
1141 // If the condition is known, choose the appropriate expression.
1142 if (cond_range
.singleton_p ())
1144 // False, pick second operand.
1145 if (cond_range
.zero_p ())
1159 gimple_ranger::range_of_expr (irange
&r
, tree expr
, gimple
*stmt
)
1161 if (!gimple_range_ssa_p (expr
))
1162 return get_tree_range (r
, expr
, stmt
);
1164 // If there is no statement, just get the global value.
1167 if (!m_cache
.get_global_range (r
, expr
))
1168 r
= gimple_range_global (expr
);
1172 // For a debug stmt, pick the best value currently available, do not
1173 // trigger new value calculations. PR 100781.
1174 if (is_gimple_debug (stmt
))
1176 bool state
= m_cache
.enable_new_values (false);
1177 m_cache
.range_of_expr (r
, expr
, stmt
);
1178 m_cache
.enable_new_values (state
);
1181 basic_block bb
= gimple_bb (stmt
);
1182 gimple
*def_stmt
= SSA_NAME_DEF_STMT (expr
);
1184 // If name is defined in this block, try to get an range from S.
1185 if (def_stmt
&& gimple_bb (def_stmt
) == bb
)
1187 range_of_stmt (r
, def_stmt
, expr
);
1188 if (!cfun
->can_throw_non_call_exceptions
&& r
.varying_p () &&
1189 m_cache
.m_non_null
.non_null_deref_p (expr
, bb
))
1190 r
= range_nonzero (TREE_TYPE (expr
));
1193 // Otherwise OP comes from outside this block, use range on entry.
1194 range_on_entry (r
, bb
, expr
);
1199 // Return the range of NAME on entry to block BB in R.
1202 gimple_ranger::range_on_entry (irange
&r
, basic_block bb
, tree name
)
1204 int_range_max entry_range
;
1205 gcc_checking_assert (gimple_range_ssa_p (name
));
1207 // Start with any known range
1208 range_of_stmt (r
, SSA_NAME_DEF_STMT (name
), name
);
1210 // Now see if there is any on_entry value which may refine it.
1211 if (m_cache
.block_range (entry_range
, bb
, name
))
1212 r
.intersect (entry_range
);
1214 if (!cfun
->can_throw_non_call_exceptions
&& r
.varying_p () &&
1215 m_cache
.m_non_null
.non_null_deref_p (name
, bb
))
1216 r
= range_nonzero (TREE_TYPE (name
));
1219 // Calculate the range for NAME at the end of block BB and return it in R.
1220 // Return false if no range can be calculated.
1223 gimple_ranger::range_on_exit (irange
&r
, basic_block bb
, tree name
)
1225 // on-exit from the exit block?
1226 gcc_checking_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1227 gcc_checking_assert (gimple_range_ssa_p (name
));
1229 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1230 basic_block def_bb
= gimple_bb (s
);
1231 // If this is not the definition block, get the range on the last stmt in
1232 // the block... if there is one.
1235 // If there is no statement provided, get the range_on_entry for this block.
1237 range_of_expr (r
, name
, s
);
1239 range_on_entry (r
, bb
, name
);
1240 gcc_checking_assert (r
.undefined_p ()
1241 || range_compatible_p (r
.type (), TREE_TYPE (name
)));
1244 // Calculate a range for NAME on edge E and return it in R.
1247 gimple_ranger::range_on_edge (irange
&r
, edge e
, tree name
)
1249 int_range_max edge_range
;
1250 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name
)));
1252 // PHI arguments can be constants, catch these here.
1253 if (!gimple_range_ssa_p (name
))
1254 return range_of_expr (r
, name
);
1256 range_on_exit (r
, e
->src
, name
);
1257 gcc_checking_assert (r
.undefined_p ()
1258 || range_compatible_p (r
.type(), TREE_TYPE (name
)));
1260 // Check to see if NAME is defined on edge e.
1261 if (m_cache
.range_on_edge (edge_range
, e
, name
))
1262 r
.intersect (edge_range
);
1267 // fold_range wrapper for range_of_stmt to use as an internal client.
1270 gimple_ranger::fold_range_internal (irange
&r
, gimple
*s
, tree name
)
1273 fur_depend
src (s
, &(gori ()), this);
1274 return f
.fold_stmt (r
, s
, src
, name
);
1277 // Calculate a range for statement S and return it in R. If NAME is
1278 // provided it represents the SSA_NAME on the LHS of the statement.
1279 // It is only required if there is more than one lhs/output. Check
1280 // the global cache for NAME first to see if the evaluation can be
1281 // avoided. If a range cannot be calculated, return false and UNDEFINED.
1284 gimple_ranger::range_of_stmt (irange
&r
, gimple
*s
, tree name
)
1289 name
= gimple_get_lhs (s
);
1291 // If no name, simply call the base routine.
1293 return fold_range_internal (r
, s
, NULL_TREE
);
1295 if (!gimple_range_ssa_p (name
))
1298 // Check if the stmt has already been processed, and is not stale.
1299 if (m_cache
.get_non_stale_global_range (r
, name
))
1302 // Otherwise calculate a new value.
1304 fold_range_internal (tmp
, s
, name
);
1306 // Combine the new value with the old value. This is required because
1307 // the way value propagation works, when the IL changes on the fly we
1308 // can sometimes get different results. See PR 97741.
1310 m_cache
.set_global_range (name
, r
);
1315 // This routine will export whatever global ranges are known to GCC
1316 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
1319 gimple_ranger::export_global_ranges ()
1325 fprintf (dump_file
, "Exported global range table\n");
1326 fprintf (dump_file
, "===========================\n");
1329 for ( x
= 1; x
< num_ssa_names
; x
++)
1331 tree name
= ssa_name (x
);
1332 if (name
&& !SSA_NAME_IN_FREE_LIST (name
)
1333 && gimple_range_ssa_p (name
)
1334 && m_cache
.get_global_range (r
, name
)
1337 bool updated
= update_global_range (r
, name
);
1339 if (updated
&& dump_file
)
1342 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1343 fprintf (dump_file
, " --> ");
1344 vr
.dump (dump_file
);
1345 fprintf (dump_file
, "\n");
1346 int_range_max same
= vr
;
1349 fprintf (dump_file
, " irange : ");
1351 fprintf (dump_file
, "\n");
1358 // Print the known table values to file F.
1361 gimple_ranger::dump_bb (FILE *f
, basic_block bb
)
1366 int_range_max range
;
1367 fprintf (f
, "\n=========== BB %d ============\n", bb
->index
);
1368 m_cache
.dump_bb (f
, bb
);
1370 ::dump_bb (f
, bb
, 4, TDF_NONE
);
1372 // Now find any globals defined in this block.
1373 for (x
= 1; x
< num_ssa_names
; x
++)
1375 tree name
= ssa_name (x
);
1376 if (gimple_range_ssa_p (name
) && SSA_NAME_DEF_STMT (name
) &&
1377 gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
&&
1378 m_cache
.get_global_range (range
, name
))
1380 if (!range
.varying_p ())
1382 print_generic_expr (f
, name
, TDF_SLIM
);
1391 // And now outgoing edges, if they define anything.
1392 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1394 for (x
= 1; x
< num_ssa_names
; x
++)
1396 tree name
= gimple_range_ssa_p (ssa_name (x
));
1397 if (name
&& gori ().has_edge_range_p (name
, e
)
1398 && m_cache
.range_on_edge (range
, e
, name
))
1400 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1401 // Only print the range if this is the def block, or
1402 // the on entry cache for either end of the edge is
1404 if ((s
&& bb
== gimple_bb (s
)) ||
1405 m_cache
.block_range (range
, bb
, name
, false) ||
1406 m_cache
.block_range (range
, e
->dest
, name
, false))
1408 range_on_edge (range
, e
, name
);
1409 if (!range
.varying_p ())
1411 fprintf (f
, "%d->%d ", e
->src
->index
,
1414 if (e
->flags
& EDGE_TRUE_VALUE
)
1415 fprintf (f
, " (T)%c", c
);
1416 else if (e
->flags
& EDGE_FALSE_VALUE
)
1417 fprintf (f
, " (F)%c", c
);
1420 print_generic_expr (f
, name
, TDF_SLIM
);
1421 fprintf(f
, " : \t");
1431 // Print the known table values to file F.
1434 gimple_ranger::dump (FILE *f
)
1438 FOR_EACH_BB_FN (bb
, cfun
)
1444 // If SCEV has any information about phi node NAME, return it as a range in R.
1447 fold_using_range::range_of_ssa_name_with_loop_info (irange
&r
, tree name
,
1448 class loop
*l
, gphi
*phi
,
1451 gcc_checking_assert (TREE_CODE (name
) == SSA_NAME
);
1452 tree min
, max
, type
= TREE_TYPE (name
);
1453 if (bounds_of_var_in_loop (&min
, &max
, src
.query (), l
, phi
, name
))
1455 if (TREE_CODE (min
) != INTEGER_CST
)
1457 if (src
.query ()->range_of_expr (r
, min
, phi
) && !r
.undefined_p ())
1458 min
= wide_int_to_tree (type
, r
.lower_bound ());
1460 min
= vrp_val_min (type
);
1462 if (TREE_CODE (max
) != INTEGER_CST
)
1464 if (src
.query ()->range_of_expr (r
, max
, phi
) && !r
.undefined_p ())
1465 max
= wide_int_to_tree (type
, r
.upper_bound ());
1467 max
= vrp_val_max (type
);
1472 r
.set_varying (type
);
1475 // --------------------------------------------------------------------------
1476 // trace_ranger implementation.
1479 trace_ranger::trace_ranger ()
1485 // If dumping, return true and print the prefix for the next output line.
1488 trace_ranger::dumping (unsigned counter
, bool trailing
)
1490 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1492 // Print counter index as well as INDENT spaces.
1494 fprintf (dump_file
, " %-7u ", counter
);
1496 fprintf (dump_file
, " ");
1498 for (x
= 0; x
< indent
; x
++)
1499 fputc (' ', dump_file
);
1505 // After calling a routine, if dumping, print the CALLER, NAME, and RESULT,
1506 // returning RESULT.
1509 trace_ranger::trailer (unsigned counter
, const char *caller
, bool result
,
1510 tree name
, const irange
&r
)
1512 if (dumping (counter
, true))
1515 fputs(result
? "TRUE : " : "FALSE : ", dump_file
);
1516 fprintf (dump_file
, "(%u) ", counter
);
1517 fputs (caller
, dump_file
);
1518 fputs (" (",dump_file
);
1520 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1521 fputs (") ",dump_file
);
1525 fputc('\n', dump_file
);
1528 fputc('\n', dump_file
);
1529 // Marks the end of a request.
1531 fputc('\n', dump_file
);
1536 // Tracing version of range_on_edge. Call it with printing wrappers.
1539 trace_ranger::range_on_edge (irange
&r
, edge e
, tree name
)
1541 unsigned idx
= ++trace_count
;
1544 fprintf (dump_file
, "range_on_edge (");
1545 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1546 fprintf (dump_file
, ") on edge %d->%d\n", e
->src
->index
, e
->dest
->index
);
1550 bool res
= gimple_ranger::range_on_edge (r
, e
, name
);
1551 trailer (idx
, "range_on_edge", true, name
, r
);
1555 // Tracing version of range_on_entry. Call it with printing wrappers.
1558 trace_ranger::range_on_entry (irange
&r
, basic_block bb
, tree name
)
1560 unsigned idx
= ++trace_count
;
1563 fprintf (dump_file
, "range_on_entry (");
1564 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1565 fprintf (dump_file
, ") to BB %d\n", bb
->index
);
1569 gimple_ranger::range_on_entry (r
, bb
, name
);
1571 trailer (idx
, "range_on_entry", true, name
, r
);
1574 // Tracing version of range_on_exit. Call it with printing wrappers.
1577 trace_ranger::range_on_exit (irange
&r
, basic_block bb
, tree name
)
1579 unsigned idx
= ++trace_count
;
1582 fprintf (dump_file
, "range_on_exit (");
1583 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1584 fprintf (dump_file
, ") from BB %d\n", bb
->index
);
1588 gimple_ranger::range_on_exit (r
, bb
, name
);
1590 trailer (idx
, "range_on_exit", true, name
, r
);
1593 // Tracing version of range_of_stmt. Call it with printing wrappers.
1596 trace_ranger::range_of_stmt (irange
&r
, gimple
*s
, tree name
)
1599 unsigned idx
= ++trace_count
;
1602 fprintf (dump_file
, "range_of_stmt (");
1604 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1605 fputs (") at stmt ", dump_file
);
1606 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
1610 res
= gimple_ranger::range_of_stmt (r
, s
, name
);
1612 return trailer (idx
, "range_of_stmt", res
, name
, r
);
1615 // Tracing version of range_of_expr. Call it with printing wrappers.
1618 trace_ranger::range_of_expr (irange
&r
, tree name
, gimple
*s
)
1621 unsigned idx
= ++trace_count
;
1624 fprintf (dump_file
, "range_of_expr(");
1625 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1626 fputs (")", dump_file
);
1629 fputs (" at stmt ", dump_file
);
1630 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
1633 fputs ("\n", dump_file
);
1637 res
= gimple_ranger::range_of_expr (r
, name
, s
);
1639 return trailer (idx
, "range_of_expr", res
, name
, r
);
1643 enable_ranger (struct function
*fun
)
1647 if (param_evrp_mode
& EVRP_MODE_TRACE
)
1648 r
= new trace_ranger
;
1650 r
= new gimple_ranger
;
1652 fun
->x_range_query
= r
;
1658 disable_ranger (struct function
*fun
)
1660 delete fun
->x_range_query
;
1662 fun
->x_range_query
= &global_ranges
;
1665 #include "gimple-range-tests.cc"