1 /* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2024 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-iterator.h"
33 #include "gimple-fold.h"
35 #include "fold-const.h"
36 #include "case-cfn-macros.h"
37 #include "omp-general.h"
39 #include "tree-ssa-loop.h"
40 #include "tree-scalar-evolution.h"
41 #include "langhooks.h"
42 #include "vr-values.h"
44 #include "value-query.h"
45 #include "gimple-range-op.h"
46 #include "gimple-range.h"
48 #include "alloc-pool.h"
49 #include "symbol-summary.h"
50 #include "ipa-utils.h"
54 // Construct a fur_source, and set the m_query field.
56 fur_source::fur_source (range_query
*q
)
61 m_query
= get_range_query (cfun
);
65 // Invoke range_of_expr on EXPR.
68 fur_source::get_operand (vrange
&r
, tree expr
)
70 return m_query
->range_of_expr (r
, expr
);
73 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
74 // range_query to get the range on the edge.
77 fur_source::get_phi_operand (vrange
&r
, tree expr
, edge e
)
79 return m_query
->range_on_edge (r
, e
, expr
);
82 // Default is no relation.
85 fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED
,
86 tree op2 ATTRIBUTE_UNUSED
)
91 // Default registers nothing.
94 fur_source::register_relation (gimple
*s ATTRIBUTE_UNUSED
,
95 relation_kind k ATTRIBUTE_UNUSED
,
96 tree op1 ATTRIBUTE_UNUSED
,
97 tree op2 ATTRIBUTE_UNUSED
)
101 // Default registers nothing.
104 fur_source::register_relation (edge e ATTRIBUTE_UNUSED
,
105 relation_kind k ATTRIBUTE_UNUSED
,
106 tree op1 ATTRIBUTE_UNUSED
,
107 tree op2 ATTRIBUTE_UNUSED
)
111 // This version of fur_source will pick a range up off an edge.
113 class fur_edge
: public fur_source
116 fur_edge (edge e
, range_query
*q
= NULL
);
117 virtual bool get_operand (vrange
&r
, tree expr
) override
;
118 virtual bool get_phi_operand (vrange
&r
, tree expr
, edge e
) override
;
123 // Instantiate an edge based fur_source.
126 fur_edge::fur_edge (edge e
, range_query
*q
) : fur_source (q
)
131 // Get the value of EXPR on edge m_edge.
134 fur_edge::get_operand (vrange
&r
, tree expr
)
136 return m_query
->range_on_edge (r
, m_edge
, expr
);
139 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
140 // range_query to get the range on the edge.
143 fur_edge::get_phi_operand (vrange
&r
, tree expr
, edge e
)
145 // Edge to edge recalculations not supported yet, until we sort it out.
146 gcc_checking_assert (e
== m_edge
);
147 return m_query
->range_on_edge (r
, e
, expr
);
150 // Instantiate a stmt based fur_source.
152 fur_stmt::fur_stmt (gimple
*s
, range_query
*q
) : fur_source (q
)
157 // Retrieve range of EXPR as it occurs as a use on stmt M_STMT.
160 fur_stmt::get_operand (vrange
&r
, tree expr
)
162 return m_query
->range_of_expr (r
, expr
, m_stmt
);
165 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
166 // range_query to get the range on the edge.
169 fur_stmt::get_phi_operand (vrange
&r
, tree expr
, edge e
)
171 // Pick up the range of expr from edge E.
172 fur_edge
e_src (e
, m_query
);
173 return e_src
.get_operand (r
, expr
);
176 // Return relation based from m_stmt.
179 fur_stmt::query_relation (tree op1
, tree op2
)
181 return m_query
->relation ().query (m_stmt
, op1
, op2
);
184 // Instantiate a stmt based fur_source with a GORI object.
187 fur_depend::fur_depend (gimple
*s
, range_query
*q
)
193 // Register a relation on a stmt if there is an oracle.
196 fur_depend::register_relation (gimple
*s
, relation_kind k
, tree op1
, tree op2
)
198 m_query
->relation ().record (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
)
206 m_query
->relation ().record (e
, k
, op1
, op2
);
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 (vrange
&r1
, range_query
*q
= NULL
);
216 fur_list (vrange
&r1
, vrange
&r2
, range_query
*q
= NULL
);
217 fur_list (unsigned num
, vrange
**list
, range_query
*q
= NULL
);
218 virtual bool get_operand (vrange
&r
, tree expr
) override
;
219 virtual bool get_phi_operand (vrange
&r
, tree expr
, edge e
) override
;
227 // One range supplied for unary operations.
229 fur_list::fur_list (vrange
&r1
, range_query
*q
) : fur_source (q
)
237 // Two ranges supplied for binary operations.
239 fur_list::fur_list (vrange
&r1
, vrange
&r2
, range_query
*q
) : fur_source (q
)
248 // Arbitrary number of ranges in a vector.
250 fur_list::fur_list (unsigned num
, vrange
**list
, range_query
*q
)
258 // Get the next operand from the vector, ensure types are compatible.
261 fur_list::get_operand (vrange
&r
, tree expr
)
263 // Do not use the vector for non-ssa-names, or if it has been emptied.
264 if (TREE_CODE (expr
) != SSA_NAME
|| m_index
>= m_limit
)
265 return m_query
->range_of_expr (r
, expr
);
266 r
= *m_list
[m_index
++];
267 gcc_checking_assert (range_compatible_p (TREE_TYPE (expr
), r
.type ()));
271 // This will simply pick the next operand from the vector.
273 fur_list::get_phi_operand (vrange
&r
, tree expr
, edge e ATTRIBUTE_UNUSED
)
275 return get_operand (r
, expr
);
278 // Fold stmt S into range R using R1 as the first operand.
281 fold_range (vrange
&r
, gimple
*s
, vrange
&r1
, range_query
*q
)
284 fur_list
src (r1
, q
);
285 return f
.fold_stmt (r
, s
, src
);
288 // Fold stmt S into range R using R1 and R2 as the first two operands.
291 fold_range (vrange
&r
, gimple
*s
, vrange
&r1
, vrange
&r2
, range_query
*q
)
294 fur_list
src (r1
, r2
, q
);
295 return f
.fold_stmt (r
, s
, src
);
298 // Fold stmt S into range R using NUM_ELEMENTS from VECTOR as the initial
299 // operands encountered.
302 fold_range (vrange
&r
, gimple
*s
, unsigned num_elements
, vrange
**vector
,
306 fur_list
src (num_elements
, vector
, q
);
307 return f
.fold_stmt (r
, s
, src
);
310 // Fold stmt S into range R using range query Q.
313 fold_range (vrange
&r
, gimple
*s
, range_query
*q
)
317 return f
.fold_stmt (r
, s
, src
);
320 // Recalculate stmt S into R using range query Q as if it were on edge ON_EDGE.
323 fold_range (vrange
&r
, gimple
*s
, edge on_edge
, range_query
*q
)
326 fur_edge
src (on_edge
, q
);
327 return f
.fold_stmt (r
, s
, src
);
330 // Calculate op1 on statetemt S with LHS into range R using range query Q
331 // to resolve any other operands.
334 op1_range (vrange
&r
, gimple
*s
, const vrange
&lhs
, range_query
*q
)
336 gimple_range_op_handler
handler (s
);
342 tree op2_expr
= handler
.operand2 ();
344 return handler
.calc_op1 (r
, lhs
);
346 value_range
op2 (TREE_TYPE (op2_expr
));
347 if (!src
.get_operand (op2
, op2_expr
))
350 return handler
.calc_op1 (r
, lhs
, op2
);
353 // Calculate op1 on statetemt S into range R using range query Q.
354 // LHS is set to VARYING in this case.
357 op1_range (vrange
&r
, gimple
*s
, range_query
*q
)
359 tree lhs_type
= gimple_range_type (s
);
362 value_range lhs_range
;
363 lhs_range
.set_varying (lhs_type
);
364 return op1_range (r
, s
, lhs_range
, q
);
367 // Calculate op2 on statetemt S with LHS into range R using range query Q
368 // to resolve any other operands.
371 op2_range (vrange
&r
, gimple
*s
, const vrange
&lhs
, range_query
*q
)
374 gimple_range_op_handler
handler (s
);
380 value_range
op1 (TREE_TYPE (handler
.operand1 ()));
381 if (!src
.get_operand (op1
, handler
.operand1 ()))
384 return handler
.calc_op2 (r
, lhs
, op1
);
387 // Calculate op2 on statetemt S into range R using range query Q.
388 // LHS is set to VARYING in this case.
391 op2_range (vrange
&r
, gimple
*s
, range_query
*q
)
393 tree lhs_type
= gimple_range_type (s
);
396 value_range lhs_range
;
397 lhs_range
.set_varying (lhs_type
);
398 return op2_range (r
, s
, lhs_range
, q
);
401 // Provide a fur_source which can be used to determine any relations on
402 // a statement. It manages the callback from fold_using_ranges to determine
403 // a relation_trio for a statement.
405 class fur_relation
: public fur_stmt
408 fur_relation (gimple
*s
, range_query
*q
= NULL
);
409 virtual void register_relation (gimple
*stmt
, relation_kind k
, tree op1
,
411 virtual void register_relation (edge e
, relation_kind k
, tree op1
,
413 relation_trio
trio() const;
415 relation_kind def_op1
, def_op2
, op1_op2
;
418 fur_relation::fur_relation (gimple
*s
, range_query
*q
) : fur_stmt (s
, q
)
420 def_op1
= def_op2
= op1_op2
= VREL_VARYING
;
423 // Construct a trio from what is known.
426 fur_relation::trio () const
428 return relation_trio (def_op1
, def_op2
, op1_op2
);
431 // Don't support edges, but avoid a compiler warning by providing the routine.
434 fur_relation::register_relation (edge
, relation_kind
, tree
, tree
)
438 // Register relation K between OP1 and OP2 on STMT.
441 fur_relation::register_relation (gimple
*stmt
, relation_kind k
, tree op1
,
444 tree lhs
= gimple_get_lhs (stmt
);
447 switch (gimple_code (stmt
))
450 a1
= gimple_cond_lhs (stmt
);
451 a2
= gimple_cond_rhs (stmt
);
454 a1
= gimple_assign_rhs1 (stmt
);
455 if (gimple_num_ops (stmt
) >= 3)
456 a2
= gimple_assign_rhs2 (stmt
);
461 // STMT is of the form LHS = A1 op A2, now map the relation to these
462 // operands, if possible.
473 def_op1
= relation_swap (k
);
475 def_op2
= relation_swap (k
);
479 if (op1
== a1
&& op2
== a2
)
481 else if (op2
== a1
&& op1
== a2
)
482 op1_op2
= relation_swap (k
);
486 // Return the relation trio for stmt S using query Q.
489 fold_relations (gimple
*s
, range_query
*q
)
492 fur_relation
src (s
, q
);
493 tree lhs
= gimple_range_ssa_p (gimple_get_lhs (s
));
496 value_range
vr(TREE_TYPE (lhs
));
497 if (f
.fold_stmt (vr
, s
, src
))
503 // -------------------------------------------------------------------------
505 // Adjust the range for a pointer difference where the operands came
508 // This notices the following sequence:
510 // def = __builtin_memchr (arg, 0, sz)
513 // The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
516 adjust_pointer_diff_expr (irange
&res
, const gimple
*diff_stmt
)
518 tree op0
= gimple_assign_rhs1 (diff_stmt
);
519 tree op1
= gimple_assign_rhs2 (diff_stmt
);
520 tree op0_ptype
= TREE_TYPE (TREE_TYPE (op0
));
521 tree op1_ptype
= TREE_TYPE (TREE_TYPE (op1
));
524 if (TREE_CODE (op0
) == SSA_NAME
525 && TREE_CODE (op1
) == SSA_NAME
526 && (call
= SSA_NAME_DEF_STMT (op0
))
527 && is_gimple_call (call
)
528 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
529 && TYPE_MODE (op0_ptype
) == TYPE_MODE (char_type_node
)
530 && TYPE_PRECISION (op0_ptype
) == TYPE_PRECISION (char_type_node
)
531 && TYPE_MODE (op1_ptype
) == TYPE_MODE (char_type_node
)
532 && TYPE_PRECISION (op1_ptype
) == TYPE_PRECISION (char_type_node
)
533 && gimple_call_builtin_p (call
, BUILT_IN_MEMCHR
)
534 && vrp_operand_equal_p (op1
, gimple_call_arg (call
, 0))
535 && integer_zerop (gimple_call_arg (call
, 1)))
537 wide_int maxm1
= irange_val_max (ptrdiff_type_node
) - 1;
538 res
.intersect (int_range
<2> (ptrdiff_type_node
,
539 wi::zero (TYPE_PRECISION (ptrdiff_type_node
)),
544 // Adjust the range for an IMAGPART_EXPR.
547 adjust_imagpart_expr (vrange
&res
, const gimple
*stmt
)
549 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
551 if (TREE_CODE (name
) != SSA_NAME
|| !SSA_NAME_DEF_STMT (name
))
554 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
555 if (is_gimple_call (def_stmt
) && gimple_call_internal_p (def_stmt
))
557 switch (gimple_call_internal_fn (def_stmt
))
559 case IFN_ADD_OVERFLOW
:
560 case IFN_SUB_OVERFLOW
:
561 case IFN_MUL_OVERFLOW
:
564 case IFN_ATOMIC_COMPARE_EXCHANGE
:
567 r
.set_varying (boolean_type_node
);
568 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
569 range_cast (r
, type
);
577 if (is_gimple_assign (def_stmt
)
578 && gimple_assign_rhs_code (def_stmt
) == COMPLEX_CST
)
580 tree cst
= gimple_assign_rhs1 (def_stmt
);
581 if (TREE_CODE (cst
) == COMPLEX_CST
582 && TREE_CODE (TREE_TYPE (TREE_TYPE (cst
))) == INTEGER_TYPE
)
584 wide_int w
= wi::to_wide (TREE_IMAGPART (cst
));
585 int_range
<1> imag (TREE_TYPE (TREE_IMAGPART (cst
)), w
, w
);
586 res
.intersect (imag
);
591 // Adjust the range for a REALPART_EXPR.
594 adjust_realpart_expr (vrange
&res
, const gimple
*stmt
)
596 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
598 if (TREE_CODE (name
) != SSA_NAME
)
601 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
602 if (!SSA_NAME_DEF_STMT (name
))
605 if (is_gimple_assign (def_stmt
)
606 && gimple_assign_rhs_code (def_stmt
) == COMPLEX_CST
)
608 tree cst
= gimple_assign_rhs1 (def_stmt
);
609 if (TREE_CODE (cst
) == COMPLEX_CST
610 && TREE_CODE (TREE_TYPE (TREE_TYPE (cst
))) == INTEGER_TYPE
)
612 wide_int imag
= wi::to_wide (TREE_REALPART (cst
));
613 int_range
<2> tmp (TREE_TYPE (TREE_REALPART (cst
)), imag
, imag
);
619 // This function looks for situations when walking the use/def chains
620 // may provide additional contextual range information not exposed on
624 gimple_range_adjustment (vrange
&res
, const gimple
*stmt
)
626 switch (gimple_expr_code (stmt
))
628 case POINTER_DIFF_EXPR
:
629 adjust_pointer_diff_expr (as_a
<irange
> (res
), stmt
);
633 adjust_imagpart_expr (res
, stmt
);
637 adjust_realpart_expr (res
, stmt
);
645 // Calculate a range for statement S and return it in R. If NAME is provided it
646 // represents the SSA_NAME on the LHS of the statement. It is only required
647 // if there is more than one lhs/output. If a range cannot
648 // be calculated, return false.
651 fold_using_range::fold_stmt (vrange
&r
, gimple
*s
, fur_source
&src
, tree name
)
654 // If name and S are specified, make sure it is an LHS of S.
655 gcc_checking_assert (!name
|| !gimple_get_lhs (s
) ||
656 name
== gimple_get_lhs (s
));
659 name
= gimple_get_lhs (s
);
661 // Process addresses.
662 if (gimple_code (s
) == GIMPLE_ASSIGN
663 && gimple_assign_rhs_code (s
) == ADDR_EXPR
)
664 return range_of_address (as_a
<prange
> (r
), s
, src
);
666 gimple_range_op_handler
handler (s
);
668 res
= range_of_range_op (r
, handler
, src
);
669 else if (is_a
<gphi
*>(s
))
670 res
= range_of_phi (r
, as_a
<gphi
*> (s
), src
);
671 else if (is_a
<gcall
*>(s
))
672 res
= range_of_call (r
, as_a
<gcall
*> (s
), src
);
673 else if (is_a
<gassign
*> (s
) && gimple_assign_rhs_code (s
) == COND_EXPR
)
674 res
= range_of_cond_expr (r
, as_a
<gassign
*> (s
), src
);
676 // If the result is varying, check for basic nonnegativeness.
677 // Specifically this helps for now with strict enum in cases like
678 // g++.dg/warn/pr33738.C.
680 if (res
&& r
.varying_p () && INTEGRAL_TYPE_P (r
.type ())
681 && gimple_stmt_nonnegative_warnv_p (s
, &so_p
))
682 r
.set_nonnegative (r
.type ());
686 // If no name specified or range is unsupported, bail.
687 if (!name
|| !gimple_range_ssa_p (name
))
689 // We don't understand the stmt, so return the global range.
690 gimple_range_global (r
, name
);
694 if (r
.undefined_p ())
697 // We sometimes get compatible types copied from operands, make sure
698 // the correct type is being returned.
699 if (name
&& TREE_TYPE (name
) != r
.type ())
701 gcc_checking_assert (range_compatible_p (r
.type (), TREE_TYPE (name
)));
702 range_cast (r
, TREE_TYPE (name
));
707 // Calculate a range for range_op statement S and return it in R. If any
708 // If a range cannot be calculated, return false.
711 fold_using_range::range_of_range_op (vrange
&r
,
712 gimple_range_op_handler
&handler
,
715 gcc_checking_assert (handler
);
716 gimple
*s
= handler
.stmt ();
717 tree type
= gimple_range_type (s
);
721 tree lhs
= handler
.lhs ();
722 tree op1
= handler
.operand1 ();
723 tree op2
= handler
.operand2 ();
725 // Certain types of builtin functions may have no arguments.
728 value_range
r1 (type
);
729 if (!handler
.fold_range (r
, type
, r1
, r1
))
730 r
.set_varying (type
);
734 value_range
range1 (TREE_TYPE (op1
));
735 value_range
range2 (op2
? TREE_TYPE (op2
) : TREE_TYPE (op1
));
737 if (src
.get_operand (range1
, op1
))
741 // Fold range, and register any dependency if available.
742 value_range
r2 (type
);
743 r2
.set_varying (type
);
744 if (!handler
.fold_range (r
, type
, range1
, r2
))
745 r
.set_varying (type
);
746 if (lhs
&& gimple_range_ssa_p (op1
))
749 src
.gori_ssa ()->register_dependency (lhs
, op1
);
751 rel
= handler
.lhs_op1_relation (r
, range1
, range1
);
752 if (rel
!= VREL_VARYING
)
753 src
.register_relation (s
, rel
, lhs
, op1
);
756 else if (src
.get_operand (range2
, op2
))
758 relation_kind rel
= src
.query_relation (op1
, op2
);
759 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && rel
!= VREL_VARYING
)
761 fprintf (dump_file
, " folding with relation ");
762 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
763 print_relation (dump_file
, rel
);
764 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
765 fputc ('\n', dump_file
);
767 // Fold range, and register any dependency if available.
768 if (!handler
.fold_range (r
, type
, range1
, range2
,
769 relation_trio::op1_op2 (rel
)))
770 r
.set_varying (type
);
771 if (irange::supports_p (type
))
772 relation_fold_and_or (as_a
<irange
> (r
), s
, src
, range1
, range2
);
777 src
.gori_ssa ()->register_dependency (lhs
, op1
);
778 src
.gori_ssa ()->register_dependency (lhs
, op2
);
780 if (gimple_range_ssa_p (op1
))
782 rel
= handler
.lhs_op1_relation (r
, range1
, range2
, rel
);
783 if (rel
!= VREL_VARYING
)
784 src
.register_relation (s
, rel
, lhs
, op1
);
786 if (gimple_range_ssa_p (op2
))
788 rel
= handler
.lhs_op2_relation (r
, range1
, range2
, rel
);
789 if (rel
!= VREL_VARYING
)
790 src
.register_relation (s
, rel
, lhs
, op2
);
793 // Check for an existing BB, as we maybe asked to fold an
794 // artificial statement not in the CFG.
795 else if (is_a
<gcond
*> (s
) && gimple_bb (s
))
797 basic_block bb
= gimple_bb (s
);
798 edge e0
= EDGE_SUCC (bb
, 0);
799 edge e1
= EDGE_SUCC (bb
, 1);
801 if (!single_pred_p (e0
->dest
))
803 if (!single_pred_p (e1
->dest
))
805 src
.register_outgoing_edges (as_a
<gcond
*> (s
),
806 as_a
<irange
> (r
), e0
, e1
);
810 r
.set_varying (type
);
813 r
.set_varying (type
);
814 // Make certain range-op adjustments that aren't handled any other way.
815 gimple_range_adjustment (r
, s
);
819 // Calculate the range of an assignment containing an ADDR_EXPR.
820 // Return the range in R.
821 // If a range cannot be calculated, set it to VARYING and return true.
824 fold_using_range::range_of_address (prange
&r
, gimple
*stmt
, fur_source
&src
)
826 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
827 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
);
829 bool strict_overflow_p
;
830 tree expr
= gimple_assign_rhs1 (stmt
);
831 poly_int64 bitsize
, bitpos
;
834 int unsignedp
, reversep
, volatilep
;
835 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
836 &bitpos
, &offset
, &mode
, &unsignedp
,
837 &reversep
, &volatilep
);
840 if (base
!= NULL_TREE
841 && TREE_CODE (base
) == MEM_REF
842 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
844 tree ssa
= TREE_OPERAND (base
, 0);
845 tree lhs
= gimple_get_lhs (stmt
);
846 if (lhs
&& gimple_range_ssa_p (ssa
) && src
.gori_ssa ())
847 src
.gori_ssa ()->register_dependency (lhs
, ssa
);
848 src
.get_operand (r
, ssa
);
849 range_cast (r
, TREE_TYPE (gimple_assign_rhs1 (stmt
)));
851 poly_offset_int off
= 0;
852 bool off_cst
= false;
853 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
855 off
= mem_ref_offset (base
);
857 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
859 off
<<= LOG2_BITS_PER_UNIT
;
863 /* If &X->a is equal to X, the range of X is the result. */
864 if (off_cst
&& known_eq (off
, 0))
866 else if (flag_delete_null_pointer_checks
867 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
)))
869 /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
870 allow going from non-NULL pointer to NULL. */
872 || !r
.contains_p (wi::zero (TYPE_PRECISION (TREE_TYPE (expr
)))))
874 /* We could here instead adjust r by off >> LOG2_BITS_PER_UNIT
875 using POINTER_PLUS_EXPR if off_cst and just fall back to
877 r
.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
881 /* If MEM_REF has a "positive" offset, consider it non-NULL
882 always, for -fdelete-null-pointer-checks also "negative"
883 ones. Punt for unknown offsets (e.g. variable ones). */
884 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
887 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
889 r
.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
892 r
.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
897 if (tree_single_nonzero_warnv_p (expr
, &strict_overflow_p
))
899 r
.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
903 // Otherwise return varying.
904 r
.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
908 // Calculate a range for phi statement S and return it in R.
909 // If a range cannot be calculated, return false.
912 fold_using_range::range_of_phi (vrange
&r
, gphi
*phi
, fur_source
&src
)
914 tree phi_def
= gimple_phi_result (phi
);
915 tree type
= gimple_range_type (phi
);
916 value_range
arg_range (type
);
917 value_range
equiv_range (type
);
923 // Track if all executable arguments are the same.
924 tree single_arg
= NULL_TREE
;
925 bool seen_arg
= false;
927 relation_oracle
*oracle
= &(src
.query()->relation ());
928 // Start with an empty range, unioning in each argument's range.
930 for (x
= 0; x
< gimple_phi_num_args (phi
); x
++)
932 tree arg
= gimple_phi_arg_def (phi
, x
);
933 // An argument that is the same as the def provides no new range.
937 edge e
= gimple_phi_arg_edge (phi
, x
);
939 // Get the range of the argument on its edge.
940 src
.get_phi_operand (arg_range
, arg
, e
);
942 if (!arg_range
.undefined_p ())
944 // Register potential dependencies for stale value tracking.
945 // Likewise, if the incoming PHI argument is equivalent to this
946 // PHI definition, it provides no new info. Accumulate these ranges
947 // in case all arguments are equivalences.
948 if (oracle
->query (e
, arg
, phi_def
) == VREL_EQ
)
949 equiv_range
.union_(arg_range
);
951 r
.union_ (arg_range
);
953 if (gimple_range_ssa_p (arg
) && src
.gori_ssa ())
954 src
.gori_ssa ()->register_dependency (phi_def
, arg
);
957 // Track if all arguments are the same.
963 else if (single_arg
!= arg
)
964 single_arg
= NULL_TREE
;
966 // Once the value reaches varying, stop looking.
967 if (r
.varying_p () && single_arg
== NULL_TREE
)
971 // If all arguments were equivalences, use the equivalence ranges as no
972 // arguments were processed.
973 if (r
.undefined_p () && !equiv_range
.undefined_p ())
976 // If the PHI boils down to a single effective argument, look at it.
979 // Symbolic arguments can be equivalences.
980 if (gimple_range_ssa_p (single_arg
))
982 // Only allow the equivalence if the PHI definition does not
983 // dominate any incoming edge for SINGLE_ARG.
984 // See PR 108139 and 109462.
985 basic_block bb
= gimple_bb (phi
);
986 if (!dom_info_available_p (CDI_DOMINATORS
))
989 for (x
= 0; x
< gimple_phi_num_args (phi
); x
++)
990 if (gimple_phi_arg_def (phi
, x
) == single_arg
991 && dominated_by_p (CDI_DOMINATORS
,
992 gimple_phi_arg_edge (phi
, x
)->src
,
999 src
.register_relation (phi
, VREL_EQ
, phi_def
, single_arg
);
1001 else if (src
.get_operand (arg_range
, single_arg
)
1002 && arg_range
.singleton_p ())
1004 // Numerical arguments that are a constant can be returned as
1005 // the constant. This can help fold later cases where even this
1006 // constant might have been UNDEFINED via an unreachable edge.
1012 // If PHI analysis is available, see if there is an iniital range.
1013 if (phi_analysis_available_p ()
1014 && irange::supports_p (TREE_TYPE (phi_def
)))
1016 phi_group
*g
= (phi_analysis())[phi_def
];
1017 if (g
&& !(g
->range ().varying_p ()))
1019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1021 fprintf (dump_file
, "PHI GROUP query for ");
1022 print_generic_expr (dump_file
, phi_def
, TDF_SLIM
);
1023 fprintf (dump_file
, " found : ");
1024 g
->range ().dump (dump_file
);
1025 fprintf (dump_file
, " and adjusted original range from :");
1028 r
.intersect (g
->range ());
1029 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1031 fprintf (dump_file
, " to :");
1033 fprintf (dump_file
, "\n");
1038 // If SCEV is available, query if this PHI has any known values.
1039 if (scev_initialized_p ()
1040 && !POINTER_TYPE_P (TREE_TYPE (phi_def
)))
1042 class loop
*l
= loop_containing_stmt (phi
);
1043 if (l
&& loop_outer (l
))
1045 value_range
loop_range (type
);
1046 range_of_ssa_name_with_loop_info (loop_range
, phi_def
, l
, phi
, src
);
1047 if (!loop_range
.varying_p ())
1049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1051 fprintf (dump_file
, "Loops range found for ");
1052 print_generic_expr (dump_file
, phi_def
, TDF_SLIM
);
1053 fprintf (dump_file
, ": ");
1054 loop_range
.dump (dump_file
);
1055 fprintf (dump_file
, " and calculated range :");
1057 fprintf (dump_file
, "\n");
1059 r
.intersect (loop_range
);
1067 // Calculate a range for call statement S and return it in R.
1068 // If a range cannot be calculated, return false.
1071 fold_using_range::range_of_call (vrange
&r
, gcall
*call
, fur_source
&)
1073 tree type
= gimple_range_type (call
);
1077 tree lhs
= gimple_call_lhs (call
);
1078 bool strict_overflow_p
;
1080 if (gimple_stmt_nonnegative_warnv_p (call
, &strict_overflow_p
))
1081 r
.set_nonnegative (type
);
1082 else if (gimple_call_nonnull_result_p (call
)
1083 || gimple_call_nonnull_arg (call
))
1084 r
.set_nonzero (type
);
1086 r
.set_varying (type
);
1088 tree callee
= gimple_call_fndecl (call
);
1090 && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee
)), type
))
1093 if (ipa_return_value_range (val
, callee
))
1096 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1098 fprintf (dump_file
, "Using return value range of ");
1099 print_generic_expr (dump_file
, callee
, TDF_SLIM
);
1100 fprintf (dump_file
, ": ");
1101 val
.dump (dump_file
);
1102 fprintf (dump_file
, "\n");
1107 // If there is an LHS, intersect that with what is known.
1108 if (gimple_range_ssa_p (lhs
))
1110 value_range
def (TREE_TYPE (lhs
));
1111 gimple_range_global (def
, lhs
);
1117 // Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori
1118 // to further resolve R1 and R2 if there are any dependencies between
1119 // OP1 and COND or OP2 and COND. All values can are to be calculated using SRC
1120 // as the origination source location for operands..
1121 // Effectively, use COND an the edge condition and solve for OP1 on the true
1122 // edge and OP2 on the false edge.
1125 fold_using_range::condexpr_adjust (vrange
&r1
, vrange
&r2
, gimple
*, tree cond
,
1126 tree op1
, tree op2
, fur_source
&src
)
1128 if (!src
.gori () || !src
.gori_ssa ())
1131 tree ssa1
= gimple_range_ssa_p (op1
);
1132 tree ssa2
= gimple_range_ssa_p (op2
);
1135 if (TREE_CODE (cond
) != SSA_NAME
)
1137 gassign
*cond_def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (cond
));
1139 || TREE_CODE_CLASS (gimple_assign_rhs_code (cond_def
)) != tcc_comparison
)
1141 tree type
= TREE_TYPE (gimple_assign_rhs1 (cond_def
));
1142 if (!range_compatible_p (type
, TREE_TYPE (gimple_assign_rhs2 (cond_def
))))
1144 range_op_handler
hand (gimple_assign_rhs_code (cond_def
));
1148 tree c1
= gimple_range_ssa_p (gimple_assign_rhs1 (cond_def
));
1149 tree c2
= gimple_range_ssa_p (gimple_assign_rhs2 (cond_def
));
1151 // Only solve if there is one SSA name in the condition.
1152 if ((!c1
&& !c2
) || (c1
&& c2
))
1155 // Pick up the current values of each part of the condition.
1156 tree rhs1
= gimple_assign_rhs1 (cond_def
);
1157 tree rhs2
= gimple_assign_rhs2 (cond_def
);
1158 value_range
cl (TREE_TYPE (rhs1
));
1159 value_range
cr (TREE_TYPE (rhs2
));
1160 src
.get_operand (cl
, rhs1
);
1161 src
.get_operand (cr
, rhs2
);
1163 tree cond_name
= c1
? c1
: c2
;
1164 gimple
*def_stmt
= SSA_NAME_DEF_STMT (cond_name
);
1166 // Evaluate the value of COND_NAME on the true and false edges, using either
1167 // the op1 or op2 routines based on its location.
1168 value_range
cond_true (type
), cond_false (type
);
1171 if (!hand
.op1_range (cond_false
, type
, range_false (), cr
))
1173 if (!hand
.op1_range (cond_true
, type
, range_true (), cr
))
1175 cond_false
.intersect (cl
);
1176 cond_true
.intersect (cl
);
1180 if (!hand
.op2_range (cond_false
, type
, range_false (), cl
))
1182 if (!hand
.op2_range (cond_true
, type
, range_true (), cl
))
1184 cond_false
.intersect (cr
);
1185 cond_true
.intersect (cr
);
1188 // Now solve for SSA1 or SSA2 if they are in the dependency chain.
1189 if (ssa1
&& src
.gori_ssa()->in_chain_p (ssa1
, cond_name
))
1191 value_range
tmp1 (TREE_TYPE (ssa1
));
1192 if (src
.gori ()->compute_operand_range (tmp1
, def_stmt
, cond_true
,
1194 r1
.intersect (tmp1
);
1196 if (ssa2
&& src
.gori_ssa ()->in_chain_p (ssa2
, cond_name
))
1198 value_range
tmp2 (TREE_TYPE (ssa2
));
1199 if (src
.gori ()->compute_operand_range (tmp2
, def_stmt
, cond_false
,
1201 r2
.intersect (tmp2
);
1206 // Calculate a range for COND_EXPR statement S and return it in R.
1207 // If a range cannot be calculated, return false.
1210 fold_using_range::range_of_cond_expr (vrange
&r
, gassign
*s
, fur_source
&src
)
1212 tree cond
= gimple_assign_rhs1 (s
);
1213 tree op1
= gimple_assign_rhs2 (s
);
1214 tree op2
= gimple_assign_rhs3 (s
);
1216 tree type
= gimple_range_type (s
);
1220 value_range
range1 (TREE_TYPE (op1
));
1221 value_range
range2 (TREE_TYPE (op2
));
1222 value_range
cond_range (TREE_TYPE (cond
));
1223 gcc_checking_assert (gimple_assign_rhs_code (s
) == COND_EXPR
);
1224 gcc_checking_assert (range_compatible_p (TREE_TYPE (op1
), TREE_TYPE (op2
)));
1225 src
.get_operand (cond_range
, cond
);
1226 src
.get_operand (range1
, op1
);
1227 src
.get_operand (range2
, op2
);
1229 // Try to see if there is a dependence between the COND and either operand
1230 if (condexpr_adjust (range1
, range2
, s
, cond
, op1
, op2
, src
))
1231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1233 fprintf (dump_file
, "Possible COND_EXPR adjustment. Range op1 : ");
1234 range1
.dump(dump_file
);
1235 fprintf (dump_file
, " and Range op2: ");
1236 range2
.dump(dump_file
);
1237 fprintf (dump_file
, "\n");
1240 // If the condition is known, choose the appropriate expression.
1241 if (cond_range
.singleton_p ())
1243 // False, pick second operand.
1244 if (cond_range
.zero_p ())
1254 gcc_checking_assert (r
.undefined_p ()
1255 || range_compatible_p (r
.type (), type
));
1259 // If SCEV has any information about phi node NAME, return it as a range in R.
1262 fold_using_range::range_of_ssa_name_with_loop_info (vrange
&r
, tree name
,
1263 class loop
*l
, gphi
*phi
,
1266 gcc_checking_assert (TREE_CODE (name
) == SSA_NAME
);
1267 // SCEV currently invokes get_range_query () for values. If the query
1268 // being passed in is not the same SCEV will use, do not invoke SCEV.
1269 // This can be remove if/when SCEV uses a passed in range-query.
1270 if (src
.query () != get_range_query (cfun
))
1272 r
.set_varying (TREE_TYPE (name
));
1273 // Report the msmatch if SRC is not the global query. The cache
1274 // uses a global query and would provide numerous false positives.
1275 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1276 && src
.query () != get_global_range_query ())
1278 "fold_using-range:: SCEV not invoked due to mismatched queries\n");
1280 else if (!range_of_var_in_loop (r
, name
, l
, phi
, src
.query ()))
1281 r
.set_varying (TREE_TYPE (name
));
1284 // -----------------------------------------------------------------------
1286 // Check if an && or || expression can be folded based on relations. ie
1290 // c_2 and c_3 can never be true at the same time,
1291 // Therefore c_4 can always resolve to false based purely on the relations.
1294 fold_using_range::relation_fold_and_or (irange
& lhs_range
, gimple
*s
,
1295 fur_source
&src
, vrange
&op1
,
1298 // No queries or already folded.
1299 if (!src
.gori () || lhs_range
.singleton_p ())
1302 // Only care about AND and OR expressions.
1303 enum tree_code code
= gimple_expr_code (s
);
1304 bool is_and
= false;
1305 if (code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
)
1307 else if (code
!= BIT_IOR_EXPR
&& code
!= TRUTH_OR_EXPR
)
1310 gimple_range_op_handler
handler (s
);
1311 tree lhs
= handler
.lhs ();
1312 tree ssa1
= gimple_range_ssa_p (handler
.operand1 ());
1313 tree ssa2
= gimple_range_ssa_p (handler
.operand2 ());
1315 // Deal with || and && only when there is a full set of symbolics.
1316 if (!lhs
|| !ssa1
|| !ssa2
1317 || (TREE_CODE (TREE_TYPE (lhs
)) != BOOLEAN_TYPE
)
1318 || (TREE_CODE (TREE_TYPE (ssa1
)) != BOOLEAN_TYPE
)
1319 || (TREE_CODE (TREE_TYPE (ssa2
)) != BOOLEAN_TYPE
))
1322 // Now we know its a boolean AND or OR expression with boolean operands.
1323 // Ideally we search dependencies for common names, and see what pops out.
1324 // until then, simply try to resolve direct dependencies.
1326 gimple
*ssa1_stmt
= SSA_NAME_DEF_STMT (ssa1
);
1327 gimple
*ssa2_stmt
= SSA_NAME_DEF_STMT (ssa2
);
1329 gimple_range_op_handler
handler1 (ssa1_stmt
);
1330 gimple_range_op_handler
handler2 (ssa2_stmt
);
1332 // If either handler is not present, no relation can be found.
1333 if (!handler1
|| !handler2
)
1336 // Both stmts will need to have 2 ssa names in the stmt.
1337 tree ssa1_dep1
= gimple_range_ssa_p (handler1
.operand1 ());
1338 tree ssa1_dep2
= gimple_range_ssa_p (handler1
.operand2 ());
1339 tree ssa2_dep1
= gimple_range_ssa_p (handler2
.operand1 ());
1340 tree ssa2_dep2
= gimple_range_ssa_p (handler2
.operand2 ());
1342 if (!ssa1_dep1
|| !ssa1_dep2
|| !ssa2_dep1
|| !ssa2_dep2
)
1345 if (HONOR_NANS (TREE_TYPE (ssa1_dep1
)))
1348 // Make sure they are the same dependencies, and detect the order of the
1350 bool reverse_op2
= true;
1351 if (ssa1_dep1
== ssa2_dep1
&& ssa1_dep2
== ssa2_dep2
)
1352 reverse_op2
= false;
1353 else if (ssa1_dep1
!= ssa2_dep2
|| ssa1_dep2
!= ssa2_dep1
)
1356 int_range
<2> bool_one
= range_true ();
1357 relation_kind relation1
= handler1
.op1_op2_relation (bool_one
, op1
, op2
);
1358 relation_kind relation2
= handler2
.op1_op2_relation (bool_one
, op1
, op2
);
1359 if (relation1
== VREL_VARYING
|| relation2
== VREL_VARYING
)
1363 relation2
= relation_negate (relation2
);
1365 // x && y is false if the relation intersection of the true cases is NULL.
1366 if (is_and
&& relation_intersect (relation1
, relation2
) == VREL_UNDEFINED
)
1367 lhs_range
= range_false (boolean_type_node
);
1368 // x || y is true if the union of the true cases is NO-RELATION..
1369 // ie, one or the other being true covers the full range of possibilities.
1370 else if (!is_and
&& relation_union (relation1
, relation2
) == VREL_VARYING
)
1371 lhs_range
= bool_one
;
1375 range_cast (lhs_range
, TREE_TYPE (lhs
));
1376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1378 fprintf (dump_file
, " Relation adjustment: ");
1379 print_generic_expr (dump_file
, ssa1
, TDF_SLIM
);
1380 fprintf (dump_file
, " and ");
1381 print_generic_expr (dump_file
, ssa2
, TDF_SLIM
);
1382 fprintf (dump_file
, " combine to produce ");
1383 lhs_range
.dump (dump_file
);
1384 fputc ('\n', dump_file
);
1390 // Register any outgoing edge relations from a conditional branch.
1393 fur_source::register_outgoing_edges (gcond
*s
, irange
&lhs_range
,
1396 int_range
<2> e0_range
, e1_range
;
1398 basic_block bb
= gimple_bb (s
);
1400 gimple_range_op_handler
handler (s
);
1406 // If this edge is never taken, ignore it.
1407 gcond_edge_range (e0_range
, e0
);
1408 e0_range
.intersect (lhs_range
);
1409 if (e0_range
.undefined_p ())
1415 // If this edge is never taken, ignore it.
1416 gcond_edge_range (e1_range
, e1
);
1417 e1_range
.intersect (lhs_range
);
1418 if (e1_range
.undefined_p ())
1425 // First, register the gcond itself. This will catch statements like
1427 tree ssa1
= gimple_range_ssa_p (handler
.operand1 ());
1428 tree ssa2
= gimple_range_ssa_p (handler
.operand2 ());
1432 r1
.set_varying (TREE_TYPE (ssa1
));
1433 r2
.set_varying (TREE_TYPE (ssa2
));
1436 relation_kind relation
= handler
.op1_op2_relation (e0_range
, r1
, r2
);
1437 if (relation
!= VREL_VARYING
)
1438 register_relation (e0
, relation
, ssa1
, ssa2
);
1442 relation_kind relation
= handler
.op1_op2_relation (e1_range
, r1
, r2
);
1443 if (relation
!= VREL_VARYING
)
1444 register_relation (e1
, relation
, ssa1
, ssa2
);
1448 // Outgoing relations of GORI exports require a gori engine.
1452 // Now look for other relations in the exports. This will find stmts
1453 // leading to the condition such as:
1456 FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb
, name
)
1458 if (TREE_CODE (TREE_TYPE (name
)) != BOOLEAN_TYPE
)
1460 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
1461 gimple_range_op_handler
handler (stmt
);
1464 tree ssa1
= gimple_range_ssa_p (handler
.operand1 ());
1465 tree ssa2
= gimple_range_ssa_p (handler
.operand2 ());
1466 value_range
r (TREE_TYPE (name
));
1469 r1
.set_varying (TREE_TYPE (ssa1
));
1470 r2
.set_varying (TREE_TYPE (ssa2
));
1471 if (e0
&& gori ()->edge_range_p (r
, e0
, name
, *m_query
)
1472 && r
.singleton_p ())
1474 relation_kind relation
= handler
.op1_op2_relation (r
, r1
, r2
);
1475 if (relation
!= VREL_VARYING
)
1476 register_relation (e0
, relation
, ssa1
, ssa2
);
1478 if (e1
&& gori ()->edge_range_p (r
, e1
, name
, *m_query
)
1479 && r
.singleton_p ())
1481 relation_kind relation
= handler
.op1_op2_relation (r
, r1
, r2
);
1482 if (relation
!= VREL_VARYING
)
1483 register_relation (e1
, relation
, ssa1
, ssa2
);