1 /* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2023 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"
47 // Construct a fur_source, and set the m_query field.
49 fur_source::fur_source (range_query
*q
)
54 m_query
= get_range_query (cfun
);
56 m_query
= get_global_range_query ();
60 // Invoke range_of_expr on EXPR.
63 fur_source::get_operand (vrange
&r
, tree expr
)
65 return m_query
->range_of_expr (r
, expr
);
68 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
69 // range_query to get the range on the edge.
72 fur_source::get_phi_operand (vrange
&r
, tree expr
, edge e
)
74 return m_query
->range_on_edge (r
, e
, expr
);
77 // Default is no relation.
80 fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED
,
81 tree op2 ATTRIBUTE_UNUSED
)
86 // Default registers nothing.
89 fur_source::register_relation (gimple
*s ATTRIBUTE_UNUSED
,
90 relation_kind k ATTRIBUTE_UNUSED
,
91 tree op1 ATTRIBUTE_UNUSED
,
92 tree op2 ATTRIBUTE_UNUSED
)
96 // Default registers nothing.
99 fur_source::register_relation (edge e ATTRIBUTE_UNUSED
,
100 relation_kind k ATTRIBUTE_UNUSED
,
101 tree op1 ATTRIBUTE_UNUSED
,
102 tree op2 ATTRIBUTE_UNUSED
)
106 // This version of fur_source will pick a range up off an edge.
108 class fur_edge
: public fur_source
111 fur_edge (edge e
, range_query
*q
= NULL
);
112 virtual bool get_operand (vrange
&r
, tree expr
) override
;
113 virtual bool get_phi_operand (vrange
&r
, tree expr
, edge e
) override
;
118 // Instantiate an edge based fur_source.
121 fur_edge::fur_edge (edge e
, range_query
*q
) : fur_source (q
)
126 // Get the value of EXPR on edge m_edge.
129 fur_edge::get_operand (vrange
&r
, tree expr
)
131 return m_query
->range_on_edge (r
, m_edge
, expr
);
134 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
135 // range_query to get the range on the edge.
138 fur_edge::get_phi_operand (vrange
&r
, tree expr
, edge e
)
140 // Edge to edge recalculations not supported yet, until we sort it out.
141 gcc_checking_assert (e
== m_edge
);
142 return m_query
->range_on_edge (r
, e
, expr
);
145 // Instantiate a stmt based fur_source.
147 fur_stmt::fur_stmt (gimple
*s
, range_query
*q
) : fur_source (q
)
152 // Retrieve range of EXPR as it occurs as a use on stmt M_STMT.
155 fur_stmt::get_operand (vrange
&r
, tree expr
)
157 return m_query
->range_of_expr (r
, expr
, m_stmt
);
160 // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
161 // range_query to get the range on the edge.
164 fur_stmt::get_phi_operand (vrange
&r
, tree expr
, edge e
)
166 // Pick up the range of expr from edge E.
167 fur_edge
e_src (e
, m_query
);
168 return e_src
.get_operand (r
, expr
);
171 // Return relation based from m_stmt.
174 fur_stmt::query_relation (tree op1
, tree op2
)
176 return m_query
->query_relation (m_stmt
, op1
, op2
);
179 // Instantiate a stmt based fur_source with a GORI object.
182 fur_depend::fur_depend (gimple
*s
, gori_compute
*gori
, range_query
*q
)
185 gcc_checking_assert (gori
);
187 // Set relations if there is an oracle in the range_query.
188 // This will enable registering of relationships as they are discovered.
189 m_oracle
= q
->oracle ();
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
)
199 m_oracle
->register_stmt (s
, k
, op1
, op2
);
202 // Register a relation on an edge if there is an oracle.
205 fur_depend::register_relation (edge e
, relation_kind k
, tree op1
, tree op2
)
208 m_oracle
->register_edge (e
, k
, op1
, op2
);
211 // This version of fur_source will pick a range up from a list of ranges
212 // supplied by the caller.
214 class fur_list
: public fur_source
217 fur_list (vrange
&r1
);
218 fur_list (vrange
&r1
, vrange
&r2
);
219 fur_list (unsigned num
, vrange
**list
);
220 virtual bool get_operand (vrange
&r
, tree expr
) override
;
221 virtual bool get_phi_operand (vrange
&r
, tree expr
, edge e
) override
;
229 // One range supplied for unary operations.
231 fur_list::fur_list (vrange
&r1
) : fur_source (NULL
)
239 // Two ranges supplied for binary operations.
241 fur_list::fur_list (vrange
&r1
, vrange
&r2
) : fur_source (NULL
)
250 // Arbitrary number of ranges in a vector.
252 fur_list::fur_list (unsigned num
, vrange
**list
) : fur_source (NULL
)
259 // Get the next operand from the vector, ensure types are compatible.
262 fur_list::get_operand (vrange
&r
, tree expr
)
264 if (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
)
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
)
294 fur_list
src (r1
, r2
);
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
)
305 fur_list
src (num_elements
, vector
);
306 return f
.fold_stmt (r
, s
, src
);
309 // Fold stmt S into range R using range query Q.
312 fold_range (vrange
&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 (vrange
&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 wide_int maxm1
= irange_val_max (ptrdiff_type_node
) - 1;
364 res
.intersect (int_range
<2> (ptrdiff_type_node
,
365 wi::zero (TYPE_PRECISION (ptrdiff_type_node
)),
370 // Adjust the range for an IMAGPART_EXPR.
373 adjust_imagpart_expr (vrange
&res
, const gimple
*stmt
)
375 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
377 if (TREE_CODE (name
) != SSA_NAME
|| !SSA_NAME_DEF_STMT (name
))
380 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
381 if (is_gimple_call (def_stmt
) && gimple_call_internal_p (def_stmt
))
383 switch (gimple_call_internal_fn (def_stmt
))
385 case IFN_ADD_OVERFLOW
:
386 case IFN_SUB_OVERFLOW
:
387 case IFN_MUL_OVERFLOW
:
388 case IFN_ATOMIC_COMPARE_EXCHANGE
:
391 r
.set_varying (boolean_type_node
);
392 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
393 range_cast (r
, type
);
401 if (is_gimple_assign (def_stmt
)
402 && gimple_assign_rhs_code (def_stmt
) == COMPLEX_CST
)
404 tree cst
= gimple_assign_rhs1 (def_stmt
);
405 if (TREE_CODE (cst
) == COMPLEX_CST
)
407 wide_int w
= wi::to_wide (TREE_IMAGPART (cst
));
408 int_range
<1> imag (TREE_TYPE (TREE_IMAGPART (cst
)), w
, w
);
409 res
.intersect (imag
);
414 // Adjust the range for a REALPART_EXPR.
417 adjust_realpart_expr (vrange
&res
, const gimple
*stmt
)
419 tree name
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
421 if (TREE_CODE (name
) != SSA_NAME
)
424 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
425 if (!SSA_NAME_DEF_STMT (name
))
428 if (is_gimple_assign (def_stmt
)
429 && gimple_assign_rhs_code (def_stmt
) == COMPLEX_CST
)
431 tree cst
= gimple_assign_rhs1 (def_stmt
);
432 if (TREE_CODE (cst
) == COMPLEX_CST
)
434 wide_int imag
= wi::to_wide (TREE_REALPART (cst
));
435 int_range
<2> tmp (TREE_TYPE (TREE_REALPART (cst
)), imag
, imag
);
441 // This function looks for situations when walking the use/def chains
442 // may provide additional contextual range information not exposed on
446 gimple_range_adjustment (vrange
&res
, const gimple
*stmt
)
448 switch (gimple_expr_code (stmt
))
450 case POINTER_DIFF_EXPR
:
451 adjust_pointer_diff_expr (as_a
<irange
> (res
), stmt
);
455 adjust_imagpart_expr (res
, stmt
);
459 adjust_realpart_expr (res
, stmt
);
467 // Calculate a range for statement S and return it in R. If NAME is provided it
468 // represents the SSA_NAME on the LHS of the statement. It is only required
469 // if there is more than one lhs/output. If a range cannot
470 // be calculated, return false.
473 fold_using_range::fold_stmt (vrange
&r
, gimple
*s
, fur_source
&src
, tree name
)
476 // If name and S are specified, make sure it is an LHS of S.
477 gcc_checking_assert (!name
|| !gimple_get_lhs (s
) ||
478 name
== gimple_get_lhs (s
));
481 name
= gimple_get_lhs (s
);
483 // Process addresses.
484 if (gimple_code (s
) == GIMPLE_ASSIGN
485 && gimple_assign_rhs_code (s
) == ADDR_EXPR
)
486 return range_of_address (as_a
<irange
> (r
), s
, src
);
488 gimple_range_op_handler
handler (s
);
490 res
= range_of_range_op (r
, handler
, src
);
491 else if (is_a
<gphi
*>(s
))
492 res
= range_of_phi (r
, as_a
<gphi
*> (s
), src
);
493 else if (is_a
<gcall
*>(s
))
494 res
= range_of_call (r
, as_a
<gcall
*> (s
), src
);
495 else if (is_a
<gassign
*> (s
) && gimple_assign_rhs_code (s
) == COND_EXPR
)
496 res
= range_of_cond_expr (r
, as_a
<gassign
*> (s
), src
);
498 // If the result is varying, check for basic nonnegativeness.
499 // Specifically this helps for now with strict enum in cases like
500 // g++.dg/warn/pr33738.C.
502 if (res
&& r
.varying_p () && INTEGRAL_TYPE_P (r
.type ())
503 && gimple_stmt_nonnegative_warnv_p (s
, &so_p
))
504 r
.set_nonnegative (r
.type ());
508 // If no name specified or range is unsupported, bail.
509 if (!name
|| !gimple_range_ssa_p (name
))
511 // We don't understand the stmt, so return the global range.
512 gimple_range_global (r
, name
);
516 if (r
.undefined_p ())
519 // We sometimes get compatible types copied from operands, make sure
520 // the correct type is being returned.
521 if (name
&& TREE_TYPE (name
) != r
.type ())
523 gcc_checking_assert (range_compatible_p (r
.type (), TREE_TYPE (name
)));
524 range_cast (r
, TREE_TYPE (name
));
529 // Calculate a range for range_op statement S and return it in R. If any
530 // If a range cannot be calculated, return false.
533 fold_using_range::range_of_range_op (vrange
&r
,
534 gimple_range_op_handler
&handler
,
537 gcc_checking_assert (handler
);
538 gimple
*s
= handler
.stmt ();
539 tree type
= gimple_range_type (s
);
543 tree lhs
= handler
.lhs ();
544 tree op1
= handler
.operand1 ();
545 tree op2
= handler
.operand2 ();
547 // Certain types of builtin functions may have no arguments.
550 Value_Range
r1 (type
);
551 if (!handler
.fold_range (r
, type
, r1
, r1
))
552 r
.set_varying (type
);
556 Value_Range
range1 (TREE_TYPE (op1
));
557 Value_Range
range2 (op2
? TREE_TYPE (op2
) : TREE_TYPE (op1
));
559 if (src
.get_operand (range1
, op1
))
563 // Fold range, and register any dependency if available.
564 Value_Range
r2 (type
);
565 r2
.set_varying (type
);
566 if (!handler
.fold_range (r
, type
, range1
, r2
))
567 r
.set_varying (type
);
568 if (lhs
&& gimple_range_ssa_p (op1
))
571 src
.gori ()->register_dependency (lhs
, op1
);
573 rel
= handler
.lhs_op1_relation (r
, range1
, range1
);
574 if (rel
!= VREL_VARYING
)
575 src
.register_relation (s
, rel
, lhs
, op1
);
578 else if (src
.get_operand (range2
, op2
))
580 relation_kind rel
= src
.query_relation (op1
, op2
);
581 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && rel
!= VREL_VARYING
)
583 fprintf (dump_file
, " folding with relation ");
584 print_generic_expr (dump_file
, op1
, TDF_SLIM
);
585 print_relation (dump_file
, rel
);
586 print_generic_expr (dump_file
, op2
, TDF_SLIM
);
587 fputc ('\n', dump_file
);
589 // Fold range, and register any dependency if available.
590 if (!handler
.fold_range (r
, type
, range1
, range2
,
591 relation_trio::op1_op2 (rel
)))
592 r
.set_varying (type
);
593 if (irange::supports_p (type
))
594 relation_fold_and_or (as_a
<irange
> (r
), s
, src
);
599 src
.gori ()->register_dependency (lhs
, op1
);
600 src
.gori ()->register_dependency (lhs
, op2
);
602 if (gimple_range_ssa_p (op1
))
604 rel
= handler
.lhs_op1_relation (r
, range1
, range2
, rel
);
605 if (rel
!= VREL_VARYING
)
606 src
.register_relation (s
, rel
, lhs
, op1
);
608 if (gimple_range_ssa_p (op2
))
610 rel
= handler
.lhs_op2_relation (r
, range1
, range2
, rel
);
611 if (rel
!= VREL_VARYING
)
612 src
.register_relation (s
, rel
, lhs
, op2
);
615 // Check for an existing BB, as we maybe asked to fold an
616 // artificial statement not in the CFG.
617 else if (is_a
<gcond
*> (s
) && gimple_bb (s
))
619 basic_block bb
= gimple_bb (s
);
620 edge e0
= EDGE_SUCC (bb
, 0);
621 edge e1
= EDGE_SUCC (bb
, 1);
623 if (!single_pred_p (e0
->dest
))
625 if (!single_pred_p (e1
->dest
))
627 src
.register_outgoing_edges (as_a
<gcond
*> (s
),
628 as_a
<irange
> (r
), e0
, e1
);
632 r
.set_varying (type
);
635 r
.set_varying (type
);
636 // Make certain range-op adjustments that aren't handled any other way.
637 gimple_range_adjustment (r
, s
);
641 // Calculate the range of an assignment containing an ADDR_EXPR.
642 // Return the range in R.
643 // If a range cannot be calculated, set it to VARYING and return true.
646 fold_using_range::range_of_address (irange
&r
, gimple
*stmt
, fur_source
&src
)
648 gcc_checking_assert (gimple_code (stmt
) == GIMPLE_ASSIGN
);
649 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == ADDR_EXPR
);
651 bool strict_overflow_p
;
652 tree expr
= gimple_assign_rhs1 (stmt
);
653 poly_int64 bitsize
, bitpos
;
656 int unsignedp
, reversep
, volatilep
;
657 tree base
= get_inner_reference (TREE_OPERAND (expr
, 0), &bitsize
,
658 &bitpos
, &offset
, &mode
, &unsignedp
,
659 &reversep
, &volatilep
);
662 if (base
!= NULL_TREE
663 && TREE_CODE (base
) == MEM_REF
664 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
666 tree ssa
= TREE_OPERAND (base
, 0);
667 tree lhs
= gimple_get_lhs (stmt
);
668 if (lhs
&& gimple_range_ssa_p (ssa
) && src
.gori ())
669 src
.gori ()->register_dependency (lhs
, ssa
);
670 src
.get_operand (r
, ssa
);
671 range_cast (r
, TREE_TYPE (gimple_assign_rhs1 (stmt
)));
673 poly_offset_int off
= 0;
674 bool off_cst
= false;
675 if (offset
== NULL_TREE
|| TREE_CODE (offset
) == INTEGER_CST
)
677 off
= mem_ref_offset (base
);
679 off
+= poly_offset_int::from (wi::to_poly_wide (offset
),
681 off
<<= LOG2_BITS_PER_UNIT
;
685 /* If &X->a is equal to X, the range of X is the result. */
686 if (off_cst
&& known_eq (off
, 0))
688 else if (flag_delete_null_pointer_checks
689 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
)))
691 /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
692 allow going from non-NULL pointer to NULL. */
694 || !r
.contains_p (wi::zero (TYPE_PRECISION (TREE_TYPE (expr
)))))
696 /* We could here instead adjust r by off >> LOG2_BITS_PER_UNIT
697 using POINTER_PLUS_EXPR if off_cst and just fall back to
699 r
.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
703 /* If MEM_REF has a "positive" offset, consider it non-NULL
704 always, for -fdelete-null-pointer-checks also "negative"
705 ones. Punt for unknown offsets (e.g. variable ones). */
706 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr
))
709 && (flag_delete_null_pointer_checks
|| known_gt (off
, 0)))
711 r
.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
714 r
.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
719 if (tree_single_nonzero_warnv_p (expr
, &strict_overflow_p
))
721 r
.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
725 // Otherwise return varying.
726 r
.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt
)));
730 // Calculate a range for phi statement S and return it in R.
731 // If a range cannot be calculated, return false.
734 fold_using_range::range_of_phi (vrange
&r
, gphi
*phi
, fur_source
&src
)
736 tree phi_def
= gimple_phi_result (phi
);
737 tree type
= gimple_range_type (phi
);
738 Value_Range
arg_range (type
);
739 Value_Range
equiv_range (type
);
745 // Track if all executable arguments are the same.
746 tree single_arg
= NULL_TREE
;
747 bool seen_arg
= false;
749 // Start with an empty range, unioning in each argument's range.
751 for (x
= 0; x
< gimple_phi_num_args (phi
); x
++)
753 tree arg
= gimple_phi_arg_def (phi
, x
);
754 // An argument that is the same as the def provides no new range.
758 edge e
= gimple_phi_arg_edge (phi
, x
);
760 // Get the range of the argument on its edge.
761 src
.get_phi_operand (arg_range
, arg
, e
);
763 if (!arg_range
.undefined_p ())
765 // Register potential dependencies for stale value tracking.
766 // Likewise, if the incoming PHI argument is equivalent to this
767 // PHI definition, it provides no new info. Accumulate these ranges
768 // in case all arguments are equivalences.
769 if (src
.query ()->query_relation (e
, arg
, phi_def
, false) == VREL_EQ
)
770 equiv_range
.union_(arg_range
);
772 r
.union_ (arg_range
);
774 if (gimple_range_ssa_p (arg
) && src
.gori ())
775 src
.gori ()->register_dependency (phi_def
, arg
);
778 // Track if all arguments are the same.
784 else if (single_arg
!= arg
)
785 single_arg
= NULL_TREE
;
787 // Once the value reaches varying, stop looking.
788 if (r
.varying_p () && single_arg
== NULL_TREE
)
792 // If all arguments were equivalences, use the equivalence ranges as no
793 // arguments were processed.
794 if (r
.undefined_p () && !equiv_range
.undefined_p ())
797 // If the PHI boils down to a single effective argument, look at it.
800 // Symbolic arguments can be equivalences.
801 if (gimple_range_ssa_p (single_arg
))
803 // Only allow the equivalence if the PHI definition does not
804 // dominate any incoming edge for SINGLE_ARG.
805 // See PR 108139 and 109462.
806 basic_block bb
= gimple_bb (phi
);
807 if (!dom_info_available_p (CDI_DOMINATORS
))
810 for (x
= 0; x
< gimple_phi_num_args (phi
); x
++)
811 if (gimple_phi_arg_def (phi
, x
) == single_arg
812 && dominated_by_p (CDI_DOMINATORS
,
813 gimple_phi_arg_edge (phi
, x
)->src
,
820 src
.register_relation (phi
, VREL_EQ
, phi_def
, single_arg
);
822 else if (src
.get_operand (arg_range
, single_arg
)
823 && arg_range
.singleton_p ())
825 // Numerical arguments that are a constant can be returned as
826 // the constant. This can help fold later cases where even this
827 // constant might have been UNDEFINED via an unreachable edge.
833 // If SCEV is available, query if this PHI has any known values.
834 if (scev_initialized_p ()
835 && !POINTER_TYPE_P (TREE_TYPE (phi_def
)))
837 class loop
*l
= loop_containing_stmt (phi
);
838 if (l
&& loop_outer (l
))
840 Value_Range
loop_range (type
);
841 range_of_ssa_name_with_loop_info (loop_range
, phi_def
, l
, phi
, src
);
842 if (!loop_range
.varying_p ())
844 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
846 fprintf (dump_file
, " Loops range found for ");
847 print_generic_expr (dump_file
, phi_def
, TDF_SLIM
);
848 fprintf (dump_file
, ": ");
849 loop_range
.dump (dump_file
);
850 fprintf (dump_file
, " and calculated range :");
852 fprintf (dump_file
, "\n");
854 r
.intersect (loop_range
);
862 // Calculate a range for call statement S and return it in R.
863 // If a range cannot be calculated, return false.
866 fold_using_range::range_of_call (vrange
&r
, gcall
*call
, fur_source
&)
868 tree type
= gimple_range_type (call
);
872 tree lhs
= gimple_call_lhs (call
);
873 bool strict_overflow_p
;
875 if (gimple_stmt_nonnegative_warnv_p (call
, &strict_overflow_p
))
876 r
.set_nonnegative (type
);
877 else if (gimple_call_nonnull_result_p (call
)
878 || gimple_call_nonnull_arg (call
))
879 r
.set_nonzero (type
);
881 r
.set_varying (type
);
883 // If there is an LHS, intersect that with what is known.
886 Value_Range
def (TREE_TYPE (lhs
));
887 gimple_range_global (def
, lhs
);
893 // Calculate a range for COND_EXPR statement S and return it in R.
894 // If a range cannot be calculated, return false.
897 fold_using_range::range_of_cond_expr (vrange
&r
, gassign
*s
, fur_source
&src
)
899 tree cond
= gimple_assign_rhs1 (s
);
900 tree op1
= gimple_assign_rhs2 (s
);
901 tree op2
= gimple_assign_rhs3 (s
);
903 tree type
= gimple_range_type (s
);
907 Value_Range
range1 (TREE_TYPE (op1
));
908 Value_Range
range2 (TREE_TYPE (op2
));
909 Value_Range
cond_range (TREE_TYPE (cond
));
910 gcc_checking_assert (gimple_assign_rhs_code (s
) == COND_EXPR
);
911 gcc_checking_assert (range_compatible_p (TREE_TYPE (op1
), TREE_TYPE (op2
)));
912 src
.get_operand (cond_range
, cond
);
913 src
.get_operand (range1
, op1
);
914 src
.get_operand (range2
, op2
);
916 // Try to see if there is a dependence between the COND and either operand
918 if (src
.gori ()->condexpr_adjust (range1
, range2
, s
, cond
, op1
, op2
, src
))
919 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
921 fprintf (dump_file
, "Possible COND_EXPR adjustment. Range op1 : ");
922 range1
.dump(dump_file
);
923 fprintf (dump_file
, " and Range op2: ");
924 range2
.dump(dump_file
);
925 fprintf (dump_file
, "\n");
928 // If the condition is known, choose the appropriate expression.
929 if (cond_range
.singleton_p ())
931 // False, pick second operand.
932 if (cond_range
.zero_p ())
942 gcc_checking_assert (r
.undefined_p ()
943 || range_compatible_p (r
.type (), type
));
947 // Return the lower bound of R as a tree.
950 tree_lower_bound (const vrange
&r
, tree type
)
952 if (is_a
<irange
> (r
))
953 return wide_int_to_tree (type
, as_a
<irange
> (r
).lower_bound ());
954 // ?? Handle floats when they contain endpoints.
958 // Return the upper bound of R as a tree.
961 tree_upper_bound (const vrange
&r
, tree type
)
963 if (is_a
<irange
> (r
))
964 return wide_int_to_tree (type
, as_a
<irange
> (r
).upper_bound ());
965 // ?? Handle floats when they contain endpoints.
969 // Return the maximum value for TYPE.
972 vrp_val_max (const_tree type
)
974 if (INTEGRAL_TYPE_P (type
)
975 || POINTER_TYPE_P (type
))
976 return wide_int_to_tree (const_cast <tree
> (type
), irange_val_max (type
));
977 if (frange::supports_p (type
))
979 REAL_VALUE_TYPE r
= frange_val_max (type
);
980 return build_real (const_cast <tree
> (type
), r
);
985 // Return the minimum value for TYPE.
988 vrp_val_min (const_tree type
)
990 if (INTEGRAL_TYPE_P (type
)
991 || POINTER_TYPE_P (type
))
992 return wide_int_to_tree (const_cast <tree
> (type
), irange_val_min (type
));
993 if (frange::supports_p (type
))
995 REAL_VALUE_TYPE r
= frange_val_min (type
);
996 return build_real (const_cast <tree
> (type
), r
);
1001 // If SCEV has any information about phi node NAME, return it as a range in R.
1004 fold_using_range::range_of_ssa_name_with_loop_info (vrange
&r
, tree name
,
1005 class loop
*l
, gphi
*phi
,
1008 gcc_checking_assert (TREE_CODE (name
) == SSA_NAME
);
1009 tree min
, max
, type
= TREE_TYPE (name
);
1010 if (bounds_of_var_in_loop (&min
, &max
, src
.query (), l
, phi
, name
))
1012 if (!is_gimple_constant (min
))
1014 if (src
.query ()->range_of_expr (r
, min
, phi
) && !r
.undefined_p ())
1015 min
= tree_lower_bound (r
, type
);
1017 min
= vrp_val_min (type
);
1019 if (!is_gimple_constant (max
))
1021 if (src
.query ()->range_of_expr (r
, max
, phi
) && !r
.undefined_p ())
1022 max
= tree_upper_bound (r
, type
);
1024 max
= vrp_val_max (type
);
1032 r
.set_varying (type
);
1035 // -----------------------------------------------------------------------
1037 // Check if an && or || expression can be folded based on relations. ie
1041 // c_2 and c_3 can never be true at the same time,
1042 // Therefore c_4 can always resolve to false based purely on the relations.
1045 fold_using_range::relation_fold_and_or (irange
& lhs_range
, gimple
*s
,
1048 // No queries or already folded.
1049 if (!src
.gori () || !src
.query ()->oracle () || lhs_range
.singleton_p ())
1052 // Only care about AND and OR expressions.
1053 enum tree_code code
= gimple_expr_code (s
);
1054 bool is_and
= false;
1055 if (code
== BIT_AND_EXPR
|| code
== TRUTH_AND_EXPR
)
1057 else if (code
!= BIT_IOR_EXPR
&& code
!= TRUTH_OR_EXPR
)
1060 gimple_range_op_handler
handler (s
);
1061 tree lhs
= handler
.lhs ();
1062 tree ssa1
= gimple_range_ssa_p (handler
.operand1 ());
1063 tree ssa2
= gimple_range_ssa_p (handler
.operand2 ());
1065 // Deal with || and && only when there is a full set of symbolics.
1066 if (!lhs
|| !ssa1
|| !ssa2
1067 || (TREE_CODE (TREE_TYPE (lhs
)) != BOOLEAN_TYPE
)
1068 || (TREE_CODE (TREE_TYPE (ssa1
)) != BOOLEAN_TYPE
)
1069 || (TREE_CODE (TREE_TYPE (ssa2
)) != BOOLEAN_TYPE
))
1072 // Now we know its a boolean AND or OR expression with boolean operands.
1073 // Ideally we search dependencies for common names, and see what pops out.
1074 // until then, simply try to resolve direct dependencies.
1076 gimple
*ssa1_stmt
= SSA_NAME_DEF_STMT (ssa1
);
1077 gimple
*ssa2_stmt
= SSA_NAME_DEF_STMT (ssa2
);
1079 gimple_range_op_handler
handler1 (ssa1_stmt
);
1080 gimple_range_op_handler
handler2 (ssa2_stmt
);
1082 // If either handler is not present, no relation can be found.
1083 if (!handler1
|| !handler2
)
1086 // Both stmts will need to have 2 ssa names in the stmt.
1087 tree ssa1_dep1
= gimple_range_ssa_p (handler1
.operand1 ());
1088 tree ssa1_dep2
= gimple_range_ssa_p (handler1
.operand2 ());
1089 tree ssa2_dep1
= gimple_range_ssa_p (handler2
.operand1 ());
1090 tree ssa2_dep2
= gimple_range_ssa_p (handler2
.operand2 ());
1092 if (!ssa1_dep1
|| !ssa1_dep2
|| !ssa2_dep1
|| !ssa2_dep2
)
1095 if (HONOR_NANS (TREE_TYPE (ssa1_dep1
)))
1098 // Make sure they are the same dependencies, and detect the order of the
1100 bool reverse_op2
= true;
1101 if (ssa1_dep1
== ssa2_dep1
&& ssa1_dep2
== ssa2_dep2
)
1102 reverse_op2
= false;
1103 else if (ssa1_dep1
!= ssa2_dep2
|| ssa1_dep2
!= ssa2_dep1
)
1106 int_range
<2> bool_one
= range_true ();
1108 relation_kind relation1
= handler1
.op1_op2_relation (bool_one
);
1109 relation_kind relation2
= handler2
.op1_op2_relation (bool_one
);
1110 if (relation1
== VREL_VARYING
|| relation2
== VREL_VARYING
)
1114 relation2
= relation_negate (relation2
);
1116 // x && y is false if the relation intersection of the true cases is NULL.
1117 if (is_and
&& relation_intersect (relation1
, relation2
) == VREL_UNDEFINED
)
1118 lhs_range
= range_false (boolean_type_node
);
1119 // x || y is true if the union of the true cases is NO-RELATION..
1120 // ie, one or the other being true covers the full range of possibilities.
1121 else if (!is_and
&& relation_union (relation1
, relation2
) == VREL_VARYING
)
1122 lhs_range
= bool_one
;
1126 range_cast (lhs_range
, TREE_TYPE (lhs
));
1127 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1129 fprintf (dump_file
, " Relation adjustment: ");
1130 print_generic_expr (dump_file
, ssa1
, TDF_SLIM
);
1131 fprintf (dump_file
, " and ");
1132 print_generic_expr (dump_file
, ssa2
, TDF_SLIM
);
1133 fprintf (dump_file
, " combine to produce ");
1134 lhs_range
.dump (dump_file
);
1135 fputc ('\n', dump_file
);
1141 // Register any outgoing edge relations from a conditional branch.
1144 fur_source::register_outgoing_edges (gcond
*s
, irange
&lhs_range
, edge e0
, edge e1
)
1146 int_range
<2> e0_range
, e1_range
;
1148 basic_block bb
= gimple_bb (s
);
1150 gimple_range_op_handler
handler (s
);
1156 // If this edge is never taken, ignore it.
1157 gcond_edge_range (e0_range
, e0
);
1158 e0_range
.intersect (lhs_range
);
1159 if (e0_range
.undefined_p ())
1165 // If this edge is never taken, ignore it.
1166 gcond_edge_range (e1_range
, e1
);
1167 e1_range
.intersect (lhs_range
);
1168 if (e1_range
.undefined_p ())
1175 // First, register the gcond itself. This will catch statements like
1177 tree ssa1
= gimple_range_ssa_p (handler
.operand1 ());
1178 tree ssa2
= gimple_range_ssa_p (handler
.operand2 ());
1183 relation_kind relation
= handler
.op1_op2_relation (e0_range
);
1184 if (relation
!= VREL_VARYING
)
1185 register_relation (e0
, relation
, ssa1
, ssa2
);
1189 relation_kind relation
= handler
.op1_op2_relation (e1_range
);
1190 if (relation
!= VREL_VARYING
)
1191 register_relation (e1
, relation
, ssa1
, ssa2
);
1195 // Outgoing relations of GORI exports require a gori engine.
1199 // Now look for other relations in the exports. This will find stmts
1200 // leading to the condition such as:
1203 FOR_EACH_GORI_EXPORT_NAME (*(gori ()), bb
, name
)
1205 if (TREE_CODE (TREE_TYPE (name
)) != BOOLEAN_TYPE
)
1207 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
1208 gimple_range_op_handler
handler (stmt
);
1211 tree ssa1
= gimple_range_ssa_p (handler
.operand1 ());
1212 tree ssa2
= gimple_range_ssa_p (handler
.operand2 ());
1213 Value_Range
r (TREE_TYPE (name
));
1216 if (e0
&& gori ()->outgoing_edge_range_p (r
, e0
, name
, *m_query
)
1217 && r
.singleton_p ())
1219 relation_kind relation
= handler
.op1_op2_relation (r
);
1220 if (relation
!= VREL_VARYING
)
1221 register_relation (e0
, relation
, ssa1
, ssa2
);
1223 if (e1
&& gori ()->outgoing_edge_range_p (r
, e1
, name
, *m_query
)
1224 && r
.singleton_p ())
1226 relation_kind relation
= handler
.op1_op2_relation (r
);
1227 if (relation
!= VREL_VARYING
)
1228 register_relation (e1
, relation
, ssa1
, ssa2
);