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"
30 #include "gimple-pretty-print.h"
31 #include "optabs-tree.h"
32 #include "gimple-fold.h"
34 #include "fold-const.h"
35 #include "case-cfn-macros.h"
36 #include "omp-general.h"
38 #include "tree-ssa-loop.h"
39 #include "tree-scalar-evolution.h"
40 #include "langhooks.h"
41 #include "vr-values.h"
43 #include "value-query.h"
45 #include "gimple-range.h"
46 // Construct a fur_source, and set the m_query field.
48 fur_source::fur_source (range_query
*q
)
53 m_query
= get_range_query (cfun
);
55 m_query
= get_global_range_query ();
59 // Invoke range_of_expr on EXPR.
62 fur_source::get_operand (irange
&r
, tree expr
)
64 return m_query
->range_of_expr (r
, expr
);
67 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
68 // range_query to get the range on the edge.
71 fur_source::get_phi_operand (irange
&r
, tree expr
, edge e
)
73 return m_query
->range_on_edge (r
, e
, expr
);
76 // Default is no relation.
79 fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED
,
80 tree op2 ATTRIBUTE_UNUSED
)
85 // Default registers nothing.
88 fur_source::register_relation (gimple
*s ATTRIBUTE_UNUSED
,
89 relation_kind k ATTRIBUTE_UNUSED
,
90 tree op1 ATTRIBUTE_UNUSED
,
91 tree op2 ATTRIBUTE_UNUSED
)
95 // Default registers nothing.
98 fur_source::register_relation (edge e ATTRIBUTE_UNUSED
,
99 relation_kind k ATTRIBUTE_UNUSED
,
100 tree op1 ATTRIBUTE_UNUSED
,
101 tree op2 ATTRIBUTE_UNUSED
)
105 // This version of fur_source will pick a range up off an edge.
107 class fur_edge
: public fur_source
110 fur_edge (edge e
, range_query
*q
= NULL
);
111 virtual bool get_operand (irange
&r
, tree expr
) OVERRIDE
;
112 virtual bool get_phi_operand (irange
&r
, tree expr
, edge e
) OVERRIDE
;
117 // Instantiate an edge based fur_source.
120 fur_edge::fur_edge (edge e
, range_query
*q
) : fur_source (q
)
125 // Get the value of EXPR on edge m_edge.
128 fur_edge::get_operand (irange
&r
, tree expr
)
130 return m_query
->range_on_edge (r
, m_edge
, expr
);
133 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
134 // range_query to get the range on the edge.
137 fur_edge::get_phi_operand (irange
&r
, tree expr
, edge e
)
139 // Edge to edge recalculations not supoprted yet, until we sort it out.
140 gcc_checking_assert (e
== m_edge
);
141 return m_query
->range_on_edge (r
, e
, expr
);
144 // Instantiate a stmt based fur_source.
146 fur_stmt::fur_stmt (gimple
*s
, range_query
*q
) : fur_source (q
)
151 // Retreive 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 relation based from m_stmt.
173 fur_stmt::query_relation (tree op1
, tree op2
)
175 return m_query
->query_relation (m_stmt
, op1
, op2
);
178 // Instantiate a stmt based fur_source with a GORI object.
181 fur_depend::fur_depend (gimple
*s
, gori_compute
*gori
, range_query
*q
)
184 gcc_checking_assert (gori
);
186 // Set relations if there is an oracle in the range_query.
187 // This will enable registering of relationships as they are discovered.
188 m_oracle
= q
->oracle ();
192 // Register a relation on a stmt if there is an oracle.
195 fur_depend::register_relation (gimple
*s
, relation_kind k
, tree op1
, tree op2
)
198 m_oracle
->register_relation (s
, k
, op1
, op2
);
201 // Register a relation on an edge if there is an oracle.
204 fur_depend::register_relation (edge e
, relation_kind k
, tree op1
, tree op2
)
207 m_oracle
->register_relation (e
, k
, op1
, op2
);
210 // This version of fur_source will pick a range up from a list of ranges
211 // supplied by the caller.
213 class fur_list
: public fur_source
216 fur_list (irange
&r1
);
217 fur_list (irange
&r1
, irange
&r2
);
218 fur_list (unsigned num
, irange
*list
);
219 virtual bool get_operand (irange
&r
, tree expr
) OVERRIDE
;
220 virtual bool get_phi_operand (irange
&r
, tree expr
, edge e
) OVERRIDE
;
222 int_range_max m_local
[2];
228 // One range supplied for unary operations.
230 fur_list::fur_list (irange
&r1
) : fur_source (NULL
)
238 // Two ranges supplied for binary operations.
240 fur_list::fur_list (irange
&r1
, irange
&r2
) : fur_source (NULL
)
249 // Arbitrary number of ranges in a vector.
251 fur_list::fur_list (unsigned num
, irange
*list
) : fur_source (NULL
)
258 // Get the next operand from the vector, ensure types are compatible.
261 fur_list::get_operand (irange
&r
, tree expr
)
263 if (m_index
>= m_limit
)
264 return m_query
->range_of_expr (r
, expr
);
265 r
= m_list
[m_index
++];
266 gcc_checking_assert (range_compatible_p (TREE_TYPE (expr
), r
.type ()));
270 // This will simply pick the next operand from the vector.
272 fur_list::get_phi_operand (irange
&r
, tree expr
, edge e ATTRIBUTE_UNUSED
)
274 return get_operand (r
, expr
);
277 // Fold stmt S into range R using R1 as the first operand.
280 fold_range (irange
&r
, gimple
*s
, irange
&r1
)
284 return f
.fold_stmt (r
, s
, src
);
287 // Fold stmt S into range R using R1 and R2 as the first two operands.
290 fold_range (irange
&r
, gimple
*s
, irange
&r1
, irange
&r2
)
293 fur_list
src (r1
, r2
);
294 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
);
308 // Fold stmt S into range R using range query Q.
311 fold_range (irange
&r
, gimple
*s
, range_query
*q
)
315 return f
.fold_stmt (r
, s
, src
);
318 // Recalculate stmt S into R using range query Q as if it were on edge ON_EDGE.
321 fold_range (irange
&r
, gimple
*s
, edge on_edge
, range_query
*q
)
324 fur_edge
src (on_edge
, q
);
325 return f
.fold_stmt (r
, s
, src
);
328 // -------------------------------------------------------------------------
330 // Adjust the range for a pointer difference where the operands came
333 // This notices the following sequence:
335 // def = __builtin_memchr (arg, 0, sz)
338 // The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
341 adjust_pointer_diff_expr (irange
&res
, const gimple
*diff_stmt
)
343 tree op0
= gimple_assign_rhs1 (diff_stmt
);
344 tree op1
= gimple_assign_rhs2 (diff_stmt
);
345 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
346 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
349 if (TREE_CODE (op0
) == SSA_NAME
350 && TREE_CODE (op1
) == SSA_NAME
351 && (call
= SSA_NAME_DEF_STMT (op0
))
352 && is_gimple_call (call
)
353 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
354 && TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
355 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
356 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
357 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
358 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
359 && vrp_operand_equal_p (op1
, gimple_call_arg (call
, 0))
360 && integer_zerop (gimple_call_arg (call
, 1)))
362 tree max
= vrp_val_max (ptrdiff_type_node
);
363 wide_int wmax
= wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
364 tree expr_type
= gimple_range_type (diff_stmt
);
365 tree range_min
= build_zero_cst (expr_type
);
366 tree range_max
= wide_int_to_tree (expr_type
, wmax
- 1);
367 int_range
<2> r (range_min
, range_max
);
372 // Adjust the range for an IMAGPART_EXPR.
375 adjust_imagpart_expr (irange
&res
, const gimple
*stmt
)
377 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
379 if (TREE_CODE (name
) != SSA_NAME
|| !SSA_NAME_DEF_STMT (name
))
382 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
383 if (is_gimple_call (def_stmt
) && gimple_call_internal_p (def_stmt
))
385 switch (gimple_call_internal_fn (def_stmt
))
387 case IFN_ADD_OVERFLOW
:
388 case IFN_SUB_OVERFLOW
:
389 case IFN_MUL_OVERFLOW
:
390 case IFN_ATOMIC_COMPARE_EXCHANGE
:
393 r
.set_varying (boolean_type_node
);
394 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
395 range_cast (r
, type
);
403 if (is_gimple_assign (def_stmt
))
405 tree cst
= gimple_assign_rhs1 (def_stmt
);
406 if (TREE_CODE (cst
) == COMPLEX_CST
)
408 tree imag
= TREE_IMAGPART (cst
);
409 int_range
<2> tmp (imag
, imag
);
415 // Adjust the range for a REALPART_EXPR.
418 adjust_realpart_expr (irange
&res
, const gimple
*stmt
)
420 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
422 if (TREE_CODE (name
) != SSA_NAME
)
425 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
426 if (!SSA_NAME_DEF_STMT (name
))
429 if (is_gimple_assign (def_stmt
))
431 tree cst
= gimple_assign_rhs1 (def_stmt
);
432 if (TREE_CODE (cst
) == COMPLEX_CST
)
434 tree imag
= TREE_REALPART (cst
);
435 int_range
<2> tmp (imag
, imag
);
441 // This function looks for situations when walking the use/def chains
442 // may provide additonal contextual range information not exposed on
446 gimple_range_adjustment (irange
&res
, const gimple
*stmt
)
448 switch (gimple_expr_code (stmt
))
450 case POINTER_DIFF_EXPR
:
451 adjust_pointer_diff_expr (res
, stmt
);
455 adjust_imagpart_expr (res
, stmt
);
459 adjust_realpart_expr (res
, stmt
);
467 // Return the base of the RHS of an assignment.
470 gimple_range_base_of_assignment (const gimple
*stmt
)
472 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
473 tree op1
= gimple_assign_rhs1 (stmt
);
474 if (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
)
475 return get_base_address (TREE_OPERAND (op1
, 0));
479 // Return the first operand of this statement if it is a valid operand
480 // supported by ranges, otherwise return NULL_TREE. Special case is
481 // &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr.
484 gimple_range_operand1 (const gimple
*stmt
)
486 gcc_checking_assert (gimple_range_handler (stmt
));
488 switch (gimple_code (stmt
))
491 return gimple_cond_lhs (stmt
);
494 tree base
= gimple_range_base_of_assignment (stmt
);
495 if (base
&& TREE_CODE (base
) == MEM_REF
)
497 // If the base address is an SSA_NAME, we return it
498 // here. This allows processing of the range of that
499 // name, while the rest of the expression is simply
500 // ignored. The code in range_ops will see the
501 // ADDR_EXPR and do the right thing.
502 tree ssa
= TREE_OPERAND (base
, 0);
503 if (TREE_CODE (ssa
) == SSA_NAME
)
514 // Return the second operand of statement STMT, otherwise return NULL_TREE.
517 gimple_range_operand2 (const gimple
*stmt
)
519 gcc_checking_assert (gimple_range_handler (stmt
));
521 switch (gimple_code (stmt
))
524 return gimple_cond_rhs (stmt
);
526 if (gimple_num_ops (stmt
) >= 3)
527 return gimple_assign_rhs2 (stmt
);
534 // Calculate a range for statement S and return it in R. If NAME is provided it
535 // represents the SSA_NAME on the LHS of the statement. It is only required
536 // if there is more than one lhs/output. If a range cannot
537 // be calculated, return false.
540 fold_using_range::fold_stmt (irange
&r
, gimple
*s
, fur_source
&src
, tree name
)
543 // If name and S are specified, make sure it is an LHS of S.
544 gcc_checking_assert (!name
|| !gimple_get_lhs (s
) ||
545 name
== gimple_get_lhs (s
));
548 name
= gimple_get_lhs (s
);
550 // Process addresses.
551 if (gimple_code (s
) == GIMPLE_ASSIGN
552 && gimple_assign_rhs_code (s
) == ADDR_EXPR
)
553 return range_of_address (r
, s
, src
);
555 if (gimple_range_handler (s
))
556 res
= range_of_range_op (r
, s
, src
);
557 else if (is_a
<gphi
*>(s
))
558 res
= range_of_phi (r
, as_a
<gphi
*> (s
), src
);
559 else if (is_a
<gcall
*>(s
))
560 res
= range_of_call (r
, as_a
<gcall
*> (s
), src
);
561 else if (is_a
<gassign
*> (s
) && gimple_assign_rhs_code (s
) == COND_EXPR
)
562 res
= range_of_cond_expr (r
, as_a
<gassign
*> (s
), src
);
566 // If no name specified or range is unsupported, bail.
567 if (!name
|| !gimple_range_ssa_p (name
))
569 // We don't understand the stmt, so return the global range.
570 r
= gimple_range_global (name
);
574 if (r
.undefined_p ())
577 // We sometimes get compatible types copied from operands, make sure
578 // the correct type is being returned.
579 if (name
&& TREE_TYPE (name
) != r
.type ())
581 gcc_checking_assert (range_compatible_p (r
.type (), TREE_TYPE (name
)));
582 range_cast (r
, TREE_TYPE (name
));
587 // Calculate a range for range_op statement S and return it in R. If any
588 // If a range cannot be calculated, return false.
591 fold_using_range::range_of_range_op (irange
&r
, gimple
*s
, fur_source
&src
)
593 int_range_max range1
, range2
;
594 tree type
= gimple_range_type (s
);
597 range_operator
*handler
= gimple_range_handler (s
);
598 gcc_checking_assert (handler
);
600 tree lhs
= gimple_get_lhs (s
);
601 tree op1
= gimple_range_operand1 (s
);
602 tree op2
= gimple_range_operand2 (s
);
604 if (src
.get_operand (range1
, op1
))
608 // Fold range, and register any dependency if available.
609 int_range
<2> r2 (type
);
610 handler
->fold_range (r
, type
, range1
, r2
);
611 if (lhs
&& gimple_range_ssa_p (op1
))
614 src
.gori ()->register_dependency (lhs
, op1
);
616 rel
= handler
->lhs_op1_relation (r
, range1
, range1
);
617 if (rel
!= VREL_NONE
)
618 src
.register_relation (s
, rel
, lhs
, op1
);
621 else if (src
.get_operand (range2
, op2
))
623 relation_kind rel
= src
.query_relation (op1
, op2
);
624 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && rel
!= VREL_NONE
)
626 fprintf (dump_file
, " folding with relation ");
627 print_relation (dump_file
, rel
);
628 fputc ('\n', dump_file
);
630 // Fold range, and register any dependency if available.
631 handler
->fold_range (r
, type
, range1
, range2
, rel
);
632 relation_fold_and_or (r
, s
, src
);
637 src
.gori ()->register_dependency (lhs
, op1
);
638 src
.gori ()->register_dependency (lhs
, op2
);
640 if (gimple_range_ssa_p (op1
))
642 rel
= handler
->lhs_op1_relation (r
, range1
, range2
);
643 if (rel
!= VREL_NONE
)
644 src
.register_relation (s
, rel
, lhs
, op1
);
646 if (gimple_range_ssa_p (op2
))
648 rel
= handler
->lhs_op2_relation (r
, range1
, range2
);
649 if (rel
!= VREL_NONE
)
650 src
.register_relation (s
, rel
, lhs
, op2
);
653 else if (is_a
<gcond
*> (s
))
654 postfold_gcond_edges (as_a
<gcond
*> (s
), r
, src
);
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
) && src
.gori ())
694 src
.gori ()->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
= gimple_range_type (phi
);
757 int_range_max arg_range
;
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
) && src
.gori ())
772 src
.gori ()->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_range_type (call
);
821 tree lhs
= gimple_call_lhs (call
);
822 bool strict_overflow_p
;
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_range_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
);
862 // Check for any relation between arg0 and arg1.
863 relation_kind relation
= src
.query_relation (arg0
, arg1
);
865 bool saved_flag_wrapv
= flag_wrapv
;
866 // Pretend the arithmetic is wrapping. If there is any overflow,
867 // we'll complain, but will actually do wrapping operation.
869 op
->fold_range (r
, type
, ir0
, ir1
, relation
);
870 flag_wrapv
= saved_flag_wrapv
;
872 // If for both arguments vrp_valueize returned non-NULL, this should
873 // have been already folded and if not, it wasn't folded because of
874 // overflow. Avoid removing the UBSAN_CHECK_* calls in that case.
875 if (r
.singleton_p ())
876 r
.set_varying (type
);
879 // Return TRUE if we recognize the target character set and return the
880 // range for lower case and upper case letters.
883 get_letter_range (tree type
, irange
&lowers
, irange
&uppers
)
886 int a
= lang_hooks
.to_target_charset ('a');
887 int z
= lang_hooks
.to_target_charset ('z');
888 int A
= lang_hooks
.to_target_charset ('A');
889 int Z
= lang_hooks
.to_target_charset ('Z');
891 if ((z
- a
== 25) && (Z
- A
== 25))
893 lowers
= int_range
<2> (build_int_cst (type
, a
), build_int_cst (type
, z
));
894 uppers
= int_range
<2> (build_int_cst (type
, A
), build_int_cst (type
, Z
));
897 // Unknown character set.
901 // For a builtin in CALL, return a range in R if known and return
902 // TRUE. Otherwise return FALSE.
905 fold_using_range::range_of_builtin_call (irange
&r
, gcall
*call
,
908 combined_fn func
= gimple_call_combined_fn (call
);
909 if (func
== CFN_LAST
)
912 tree type
= gimple_range_type (call
);
914 int mini
, maxi
, zerov
= 0, prec
;
915 scalar_int_mode mode
;
919 case CFN_BUILT_IN_CONSTANT_P
:
920 if (cfun
->after_inlining
)
926 arg
= gimple_call_arg (call
, 0);
927 if (src
.get_operand (r
, arg
) && r
.singleton_p ())
929 r
.set (build_one_cst (type
), build_one_cst (type
));
934 case CFN_BUILT_IN_TOUPPER
:
936 arg
= gimple_call_arg (call
, 0);
937 // If the argument isn't compatible with the LHS, do nothing.
938 if (!range_compatible_p (type
, TREE_TYPE (arg
)))
940 if (!src
.get_operand (r
, arg
))
945 if (!get_letter_range (type
, lowers
, uppers
))
948 // Return the range passed in without any lower case characters,
949 // but including all the upper case ones.
951 r
.intersect (lowers
);
956 case CFN_BUILT_IN_TOLOWER
:
958 arg
= gimple_call_arg (call
, 0);
959 // If the argument isn't compatible with the LHS, do nothing.
960 if (!range_compatible_p (type
, TREE_TYPE (arg
)))
962 if (!src
.get_operand (r
, arg
))
967 if (!get_letter_range (type
, lowers
, uppers
))
970 // Return the range passed in without any upper case characters,
971 // but including all the lower case ones.
973 r
.intersect (uppers
);
980 // __builtin_ffs* and __builtin_popcount* return [0, prec].
981 arg
= gimple_call_arg (call
, 0);
982 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
985 src
.get_operand (r
, arg
);
986 // If arg is non-zero, then ffs or popcount are non-zero.
987 if (!range_includes_zero_p (&r
))
989 // If some high bits are known to be zero, decrease the maximum.
990 if (!r
.undefined_p ())
992 if (TYPE_SIGN (r
.type ()) == SIGNED
)
993 range_cast (r
, unsigned_type_for (r
.type ()));
994 wide_int max
= r
.upper_bound ();
995 maxi
= wi::floor_log2 (max
) + 1;
997 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
1001 r
.set (build_zero_cst (type
), build_one_cst (type
));
1005 // __builtin_c[lt]z* return [0, prec-1], except when the
1006 // argument is 0, but that is undefined behavior.
1008 // For __builtin_c[lt]z* consider argument of 0 always undefined
1009 // behavior, for internal fns depending on C?Z_DEFINED_VALUE_AT_ZERO.
1010 arg
= gimple_call_arg (call
, 0);
1011 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1014 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1015 if (gimple_call_internal_p (call
))
1017 if (optab_handler (clz_optab
, mode
) != CODE_FOR_nothing
1018 && CLZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
1020 // Only handle the single common value.
1024 // Magic value to give up, unless we can prove arg is non-zero.
1029 src
.get_operand (r
, arg
);
1030 // From clz of minimum we can compute result maximum.
1031 if (!r
.undefined_p ())
1033 // From clz of minimum we can compute result maximum.
1034 if (wi::gt_p (r
.lower_bound (), 0, TYPE_SIGN (r
.type ())))
1036 maxi
= prec
- 1 - wi::floor_log2 (r
.lower_bound ());
1040 else if (!range_includes_zero_p (&r
))
1047 // From clz of maximum we can compute result minimum.
1048 wide_int max
= r
.upper_bound ();
1049 int newmini
= prec
- 1 - wi::floor_log2 (max
);
1052 // If CLZ_DEFINED_VALUE_AT_ZERO is 2 with VALUE of prec,
1053 // return [prec, prec], otherwise ignore the range.
1062 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
1066 // __builtin_ctz* return [0, prec-1], except for when the
1067 // argument is 0, but that is undefined behavior.
1069 // For __builtin_ctz* consider argument of 0 always undefined
1070 // behavior, for internal fns depending on CTZ_DEFINED_VALUE_AT_ZERO.
1071 arg
= gimple_call_arg (call
, 0);
1072 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1075 mode
= SCALAR_INT_TYPE_MODE (TREE_TYPE (arg
));
1076 if (gimple_call_internal_p (call
))
1078 if (optab_handler (ctz_optab
, mode
) != CODE_FOR_nothing
1079 && CTZ_DEFINED_VALUE_AT_ZERO (mode
, zerov
) == 2)
1081 // Handle only the two common values.
1084 else if (zerov
== prec
)
1087 // Magic value to give up, unless we can prove arg is non-zero.
1091 src
.get_operand (r
, arg
);
1092 if (!r
.undefined_p ())
1094 // If arg is non-zero, then use [0, prec - 1].
1095 if (!range_includes_zero_p (&r
))
1100 // If some high bits are known to be zero, we can decrease
1102 wide_int max
= r
.upper_bound ();
1105 // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO
1106 // is 2 with value -1 or prec, return [-1, -1] or [prec, prec].
1107 // Otherwise ignore the range.
1110 else if (maxi
== prec
)
1113 // If value at zero is prec and 0 is in the range, we can't lower
1114 // the upper bound. We could create two separate ranges though,
1115 // [0,floor_log2(max)][prec,prec] though.
1116 else if (maxi
!= prec
)
1117 maxi
= wi::floor_log2 (max
);
1121 r
.set (build_int_cst (type
, mini
), build_int_cst (type
, maxi
));
1125 arg
= gimple_call_arg (call
, 0);
1126 prec
= TYPE_PRECISION (TREE_TYPE (arg
));
1127 r
.set (build_int_cst (type
, 0), build_int_cst (type
, prec
- 1));
1129 case CFN_UBSAN_CHECK_ADD
:
1130 range_of_builtin_ubsan_call (r
, call
, PLUS_EXPR
, src
);
1132 case CFN_UBSAN_CHECK_SUB
:
1133 range_of_builtin_ubsan_call (r
, call
, MINUS_EXPR
, src
);
1135 case CFN_UBSAN_CHECK_MUL
:
1136 range_of_builtin_ubsan_call (r
, call
, MULT_EXPR
, src
);
1139 case CFN_GOACC_DIM_SIZE
:
1140 case CFN_GOACC_DIM_POS
:
1141 // Optimizing these two internal functions helps the loop
1142 // optimizer eliminate outer comparisons. Size is [1,N]
1143 // and pos is [0,N-1].
1145 bool is_pos
= func
== CFN_GOACC_DIM_POS
;
1146 int axis
= oacc_get_ifn_dim_arg (call
);
1147 int size
= oacc_get_fn_dim_size (current_function_decl
, axis
);
1149 // If it's dynamic, the backend might know a hardware limitation.
1150 size
= targetm
.goacc
.dim_limit (axis
);
1152 r
.set (build_int_cst (type
, is_pos
? 0 : 1),
1154 ? build_int_cst (type
, size
- is_pos
) : vrp_val_max (type
));
1158 case CFN_BUILT_IN_STRLEN
:
1159 if (tree lhs
= gimple_call_lhs (call
))
1160 if (ptrdiff_type_node
1161 && (TYPE_PRECISION (ptrdiff_type_node
)
1162 == TYPE_PRECISION (TREE_TYPE (lhs
))))
1164 tree type
= TREE_TYPE (lhs
);
1165 tree max
= vrp_val_max (ptrdiff_type_node
);
1167 = wi::to_wide (max
, TYPE_PRECISION (TREE_TYPE (max
)));
1168 tree range_min
= build_zero_cst (type
);
1169 // To account for the terminating NULL, the maximum length
1170 // is one less than the maximum array size, which in turn
1171 // is one less than PTRDIFF_MAX (or SIZE_MAX where it's
1172 // smaller than the former type).
1173 // FIXME: Use max_object_size() - 1 here.
1174 tree range_max
= wide_int_to_tree (type
, wmax
- 2);
1175 r
.set (range_min
, range_max
);
1186 // Calculate a range for COND_EXPR statement S and return it in R.
1187 // If a range cannot be calculated, return false.
1190 fold_using_range::range_of_cond_expr (irange
&r
, gassign
*s
, fur_source
&src
)
1192 int_range_max cond_range
, range1
, range2
;
1193 tree cond
= gimple_assign_rhs1 (s
);
1194 tree op1
= gimple_assign_rhs2 (s
);
1195 tree op2
= gimple_assign_rhs3 (s
);
1197 tree type
= gimple_range_type (s
);
1201 gcc_checking_assert (gimple_assign_rhs_code (s
) == COND_EXPR
);
1202 gcc_checking_assert (range_compatible_p (TREE_TYPE (op1
), TREE_TYPE (op2
)));
1203 src
.get_operand (cond_range
, cond
);
1204 src
.get_operand (range1
, op1
);
1205 src
.get_operand (range2
, op2
);
1207 // If the condition is known, choose the appropriate expression.
1208 if (cond_range
.singleton_p ())
1210 // False, pick second operand.
1211 if (cond_range
.zero_p ())
1221 gcc_checking_assert (r
.undefined_p ()
1222 || range_compatible_p (r
.type (), type
));
1226 // If SCEV has any information about phi node NAME, return it as a range in R.
1229 fold_using_range::range_of_ssa_name_with_loop_info (irange
&r
, tree name
,
1230 class loop
*l
, gphi
*phi
,
1233 gcc_checking_assert (TREE_CODE (name
) == SSA_NAME
);
1234 tree min
, max
, type
= TREE_TYPE (name
);
1235 if (bounds_of_var_in_loop (&min
, &max
, src
.query (), l
, phi
, name
))
1237 if (TREE_CODE (min
) != INTEGER_CST
)
1239 if (src
.query ()->range_of_expr (r
, min
, phi
) && !r
.undefined_p ())
1240 min
= wide_int_to_tree (type
, r
.lower_bound ());
1242 min
= vrp_val_min (type
);
1244 if (TREE_CODE (max
) != INTEGER_CST
)
1246 if (src
.query ()->range_of_expr (r
, max
, phi
) && !r
.undefined_p ())
1247 max
= wide_int_to_tree (type
, r
.upper_bound ());
1249 max
= vrp_val_max (type
);
1254 r
.set_varying (type
);
1257 // -----------------------------------------------------------------------
1259 // Check if an && or || expression can be folded based on relations. ie
1263 // c_2 and c_3 can never be true at the same time,
1264 // Therefore c_4 can always resolve to false based purely on the relations.
1267 fold_using_range::relation_fold_and_or (irange
& lhs_range
, gimple
*s
,
1270 // No queries or already folded.
1271 if (!src
.gori () || !src
.query ()->oracle () || lhs_range
.singleton_p ())
1274 // Only care about AND and OR expressions.
1275 enum tree_code code
= gimple_expr_code (s
);
1276 bool is_and
= false;
1277 if (code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
)
1279 else if (code
!= BIT_IOR_EXPR
&& code
!= TRUTH_OR_EXPR
)
1282 tree lhs
= gimple_get_lhs (s
);
1283 tree ssa1
= gimple_range_ssa_p (gimple_range_operand1 (s
));
1284 tree ssa2
= gimple_range_ssa_p (gimple_range_operand2 (s
));
1286 // Deal with || and && only when there is a full set of symbolics.
1287 if (!lhs
|| !ssa1
|| !ssa2
1288 || (TREE_CODE (TREE_TYPE (lhs
)) != BOOLEAN_TYPE
)
1289 || (TREE_CODE (TREE_TYPE (ssa1
)) != BOOLEAN_TYPE
)
1290 || (TREE_CODE (TREE_TYPE (ssa2
)) != BOOLEAN_TYPE
))
1293 // Now we know its a boolean AND or OR expression with boolean operands.
1294 // Ideally we search dependencies for common names, and see what pops out.
1295 // until then, simply try to resolve direct dependencies.
1297 // Both names will need to have 2 direct dependencies.
1298 tree ssa1_dep2
= src
.gori ()->depend2 (ssa1
);
1299 tree ssa2_dep2
= src
.gori ()->depend2 (ssa2
);
1300 if (!ssa1_dep2
|| !ssa2_dep2
)
1303 tree ssa1_dep1
= src
.gori ()->depend1 (ssa1
);
1304 tree ssa2_dep1
= src
.gori ()->depend1 (ssa2
);
1305 // Make sure they are the same dependencies, and detect the order of the
1307 bool reverse_op2
= true;
1308 if (ssa1_dep1
== ssa2_dep1
&& ssa1_dep2
== ssa2_dep2
)
1309 reverse_op2
= false;
1310 else if (ssa1_dep1
!= ssa2_dep2
|| ssa1_dep2
!= ssa2_dep1
)
1313 range_operator
*handler1
= gimple_range_handler (SSA_NAME_DEF_STMT (ssa1
));
1314 range_operator
*handler2
= gimple_range_handler (SSA_NAME_DEF_STMT (ssa2
));
1316 int_range
<2> bool_one (boolean_true_node
, boolean_true_node
);
1318 relation_kind relation1
= handler1
->op1_op2_relation (bool_one
);
1319 relation_kind relation2
= handler2
->op1_op2_relation (bool_one
);
1320 if (relation1
== VREL_NONE
|| relation2
== VREL_NONE
)
1324 relation2
= relation_negate (relation2
);
1326 // x && y is false if the relation intersection of the true cases is NULL.
1327 if (is_and
&& relation_intersect (relation1
, relation2
) == VREL_EMPTY
)
1328 lhs_range
= int_range
<2> (boolean_false_node
, boolean_false_node
);
1329 // x || y is true if the union of the true cases is NO-RELATION..
1330 // ie, one or the other being true covers the full range of possibilties.
1331 else if (!is_and
&& relation_union (relation1
, relation2
) == VREL_NONE
)
1332 lhs_range
= bool_one
;
1336 range_cast (lhs_range
, TREE_TYPE (lhs
));
1337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1339 fprintf (dump_file
, " Relation adjustment: ");
1340 print_generic_expr (dump_file
, ssa1
, TDF_SLIM
);
1341 fprintf (dump_file
, " and ");
1342 print_generic_expr (dump_file
, ssa2
, TDF_SLIM
);
1343 fprintf (dump_file
, " combine to produce ");
1344 lhs_range
.dump (dump_file
);
1345 fputc ('\n', dump_file
);
1351 // Register any outgoing edge relations from a conditional branch.
1354 fold_using_range::postfold_gcond_edges (gcond
*s
, irange
& lhs_range
,
1358 int_range
<2> e0_range
, e1_range
;
1360 range_operator
*handler
;
1361 basic_block bb
= gimple_bb (s
);
1363 edge e0
= EDGE_SUCC (bb
, 0);
1364 if (!single_pred_p (e0
->dest
))
1368 // If this edge is never taken, ignore it.
1369 gcond_edge_range (e0_range
, e0
);
1370 e0_range
.intersect (lhs_range
);
1371 if (e0_range
.undefined_p ())
1376 edge e1
= EDGE_SUCC (bb
, 1);
1377 if (!single_pred_p (e1
->dest
))
1381 // If this edge is never taken, ignore it.
1382 gcond_edge_range (e1_range
, e1
);
1383 e1_range
.intersect (lhs_range
);
1384 if (e1_range
.undefined_p ())
1388 // At least one edge needs to be single pred.
1392 // First, register the gcond itself. This will catch statements like
1394 tree ssa1
= gimple_range_ssa_p (gimple_range_operand1 (s
));
1395 tree ssa2
= gimple_range_ssa_p (gimple_range_operand2 (s
));
1398 handler
= gimple_range_handler (s
);
1399 gcc_checking_assert (handler
);
1402 relation_kind relation
= handler
->op1_op2_relation (e0_range
);
1403 if (relation
!= VREL_NONE
)
1404 src
.register_relation (e0
, relation
, ssa1
, ssa2
);
1408 relation_kind relation
= handler
->op1_op2_relation (e1_range
);
1409 if (relation
!= VREL_NONE
)
1410 src
.register_relation (e1
, relation
, ssa1
, ssa2
);
1414 // Outgoing relations of GORI exports require a gori engine.
1418 range_query
*q
= src
.query ();
1419 // Now look for other relations in the exports. This will find stmts
1420 // leading to the condition such as:
1424 FOR_EACH_GORI_EXPORT_NAME (*(src
.gori ()), bb
, name
)
1426 if (TREE_CODE (TREE_TYPE (name
)) != BOOLEAN_TYPE
)
1428 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
1429 handler
= gimple_range_handler (stmt
);
1432 tree ssa1
= gimple_range_ssa_p (gimple_range_operand1 (stmt
));
1433 tree ssa2
= gimple_range_ssa_p (gimple_range_operand2 (stmt
));
1436 if (e0
&& src
.gori ()->outgoing_edge_range_p (r
, e0
, name
, *q
)
1437 && r
.singleton_p ())
1439 relation_kind relation
= handler
->op1_op2_relation (r
);
1440 if (relation
!= VREL_NONE
)
1441 src
.register_relation (e0
, relation
, ssa1
, ssa2
);
1443 if (e1
&& src
.gori ()->outgoing_edge_range_p (r
, e1
, name
, *q
)
1444 && r
.singleton_p ())
1446 relation_kind relation
= handler
->op1_op2_relation (r
);
1447 if (relation
!= VREL_NONE
)
1448 src
.register_relation (e1
, relation
, ssa1
, ssa2
);