[prev in list] [next in list] [prev in thread] [next in thread]
List: gcc-patches
Subject: [patch] multi-range implementation for value_range (irange)
From: Aldy Hernandez via Gcc-patches <gcc-patches () gcc ! gnu ! org>
Date: 2020-07-31 21:44:38
Message-ID: c277363e-3df6-b322-5a82-366d3c8bbddf () redhat ! com
[Download RAW message or body]
INTRO
=====
The following is the implementation of irange, our multi-range class
that is API compatible with value_range. It is meant to be a drop-in
replacement for value_range that provides multi-ranges while peacefully
coexisting with the existing implementation.
As Andrew previously mentioned, we have moved the representation of our
multi-range class from wide-int to trees, and merged it with the
value_range class. There is now a base class which "recognizes" a 1
sub-range case as a special legacy mode which supports ANTI_RANGE and
incorporates the original value_range code. Multi-range is fully
interoperable with value_range code now and all existing code which uses
value_range still operates exactly the same as it did. It's just
slightly different under the covers.
range-ops has been returned to working in multi-range mode now that it's
compatible with value_range. Any consumer working with ranges can
switch to multi-range by switching to the multi-range API. Basically if
you pass a value_range to any of the existing range-ops folders, you get
a low-precision result back, but if you pass a wider irange, you will
get almost infinite precision back from the range-ops code, as well as
the union and intersect, etc code. More details below.
TESTING
=======
The code has been regression tested on x86-64, x86-32, aarch64, ppc64
and ppc64le. It has also gone through a complete fedora build (over
9000 packages on x86_64).
We have also tested this patch on the ranger staging branch with the
ranger, which makes full use of multi-ranges, as opposed to evrp/vrp
which use value_ranges.
PERFORMANCE
===========
We benchmarked the code with 240 .ii files gathered from a GCC
bootstrap. The tests were run 3 times a piece and times were averaged
in. We measured performance with two approaches: one was user-time as
reported by -ftime-report-details, and the other one was done with
./cc1plus running under callgrind emulation. We decided on callgrind,
as the numbers are so small on evrp/vrp that the smallest difference in
environment throws off the numbers. Callgrind proved immensely useful
in pin-pointing those last few percentage points.
For user-time, our difference was:
* evrp with irange is 2.04% slower than mainline. In practice, this is
a combined difference of 1.0425 seconds versus 1.0637 seconds (delta of
0.0212 secs) over the 200+ files compiled.
* vrp with irange is 3.68% *FASTER* than mainline. In practice, this is
a difference of 5.5075 seconds versus 5.3050 seconds (delta of 0.2025 secs).
For callgrind, our difference was:
* evrp with irange is 5.76% slower than mainline.
* vrp with irange is 3.68% slower than mainline.
Reasons for the slowdown:
* A trivial amount of slowdown is expected by the additional ranges.
* Extra indirection in the base class (discussed below).
* Coexistence with legacy value_range's and their anti-ranges. Copying
between value_range and wider irange's involves a time and memory penalty.
Conclusion: We expect these differences to pretty much disappear as all
users of value_range are converted to multi-ranges.
But seriously folks, it's a 0.02 second slowdown over 240 files on a
uni-processor build. Plus, we more than made up for that by making VRP
0.2 seconds faster :-).
MEMORY LAYOUT
=============
irange is the base class, which contains no storage, but a pointer to
the storage when it becomes available:
class irange
{
unsigned char m_num_ranges;
unsigned char m_max_ranges;
ENUM_BITFIELD(value_range_kind) m_kind : 8;
tree *m_base;
};
Irange is meant to be an abstract class that is only instantiated by the
class with the actual storage (int_range<>):
template<unsigned N>
class int_range : public irange
{
tree m_ranges[N*2];
};
In this world, value_range which is int_range<1>, is only one word
larger than the original value_range structure (24 versus 32 bytes on
x86-64).
USAGE
=====
Multi-ranges can be declared in three ways:
* int_range<N> where N is the number of sub-ranges.
* widest_irange. This is a convenience typedef for int_range<255>, and
is used throughout to hold temporaries to make sure things don't get
squished down into a lower-precision while calculating intermediate
results. Originally we had infinite precision that grew like auto_vec<>
but decided against it for performance reasons. We also didn't see the
need for sub-ranges larger than a couple dozen. Simple tests showed
that they mostly went unused. I could dig up our original research on
this, if folks are interested in what the ideal N is. As it is, a
widest_irange is about 4k on x86-64.
* value_range. This is a convenience typedef for int_range<1> and is
special in that it is implemented under the covers with all the
VR_ANTI_RANGE nonsense. It's legacy. It's meant to go away. Or
rather, int_range<1> will eventually become just that... a bare range
with two end-points, no anti-range business.
Note: Assignment between any combination works as expected. You can
copy a value_range into a multi-range, and vice-versa. Obviously,
copying a higher precision multi-range down to a value_range will
frequently result in squishing of ranges and precision loss.
Note: range-ops (and the ranger) use the base class irange and are meant
to work with anything you throw at it.
API
===
Nothing changes in the public API.
However, we have marked all the API methods that are slated to be
deprecated by DEPRECATED in the header file. Examples of these are
kind(), min(), max(), symbolic_p(), etc. We hope this makes it easier
for contributors and reviewers to notice when deprecated API calls are
slipping into the code base.
We encourage passes that use value_range to, at the very least, be
converted away from these deprecated methods. i.e. Don't depend on
kind() and VR_ANTI_RANGE. Instead re-frame your questions with
intersect(), union(), contains_p(), and all the fancy clean API methods.
NOTES ON THE PATCH ITSELF
=========================
* Internally, a value_range is distinguished from a multi-range with the
protected method legacy_mode_p(). If/when we get rid of value_range,
all we have to do is search for this idiom and kill the legacy_mode_p
code path.
* A good portion of the changes are in range-ops, primarily in the form
of adjustments to make range-ops range agnostic (using the abstract
irange, instead of value_range), as well as performance tweaks so we
don't slow down unnecessarily. However, there are a bunch of
::op1_range and ::op2_range implementations for opcodes that were
previously unimplemented. The reviewer can safely ignore these, as the
only consumer of these are in the ranger. We're providing them (as we
did in the original range-ops submission), as the range_operator classes
are a package onto themselves.
* ipa-cp changes from vec<value_range> to std::vec<value_range>.
We are using std::vec to ensure constructors are run, which they aren't
in our internal vec<> implementation. Although we usually steer away
from using std::vec because of interactions with our GC system,
ipcp_param_lattices is only live within the pass and allocated with calloc.
* There is a one-line change to the gengtype lexer so it can handle the
<N> in the int_range template.
* We found that caching of 0, 1, and MAX for pointers significantly
speeds things up (vrp_val_max, ~[0,0] comparisons, etc). This caching
was added to the already present cache for common wide_ints in
wide_int_to_tree_1.
Jeff approved this patch off-list. I will re-run tests once again and
commit by Monday.
Aldy and Andrew
["irange.patch" (text/x-patch)]
commit f6ec639a86fbf98055f3506cf16286d616dc18ce
Author: Aldy Hernandez <aldyh@redhat.com>
Date: Thu Jul 30 11:30:18 2020 +0200
Multi-range implementation for value_range (irange).
Implement class irange, a generic multi-range implementation for
value ranges. This class is API compatible with value_range, and is meant
to seamlessly coexist with it.
gcc/ChangeLog:
* Makefile.in (GTFILES): Move value-range.h up.
* gengtype-lex.l: Set yylval to handle GTY markers on templates.
* ipa-cp.c (initialize_node_lattices): Call value_range
constructor.
(ipcp_propagate_stage): Use in-place new so value_range construct
is called.
* ipa-fnsummary.c (evaluate_conditions_for_known_args): Use std
vec instead of GCC's vec<>.
(evaluate_properties_for_edge): Adjust for std vec.
(ipa_fn_summary_t::duplicate): Same.
(estimate_ipcp_clone_size_and_time): Same.
* ipa-prop.c (ipa_get_value_range): Use in-place new for
value_range.
* ipa-prop.h (struct GTY): Remove class keyword for m_vr.
* range-op.cc (empty_range_check): Rename to...
(empty_range_varying): ...this and adjust for varying.
(undefined_shift_range_check): Adjust for irange.
(range_operator::wi_fold): Same.
(range_operator::fold_range): Adjust for irange. Special case
single pairs for performance.
(range_operator::op1_range): Adjust for irange.
(range_operator::op2_range): Same.
(value_range_from_overflowed_bounds): Same.
(value_range_with_overflow): Same.
(create_possibly_reversed_range): Same.
(range_true): Same.
(range_false): Same.
(range_true_and_false): Same.
(get_bool_state): Adjust for irange and tweak for performance.
(operator_equal::fold_range): Adjust for irange.
(operator_equal::op1_range): Same.
(operator_equal::op2_range): Same.
(operator_not_equal::fold_range): Same.
(operator_not_equal::op1_range): Same.
(operator_not_equal::op2_range): Same.
(build_lt): Same.
(build_le): Same.
(build_gt): Same.
(build_ge): Same.
(operator_lt::fold_range): Same.
(operator_lt::op1_range): Same.
(operator_lt::op2_range): Same.
(operator_le::fold_range): Same.
(operator_le::op1_range): Same.
(operator_le::op2_range): Same.
(operator_gt::fold_range): Same.
(operator_gt::op1_range): Same.
(operator_gt::op2_range): Same.
(operator_ge::fold_range): Same.
(operator_ge::op1_range): Same.
(operator_ge::op2_range): Same.
(operator_plus::wi_fold): Same.
(operator_plus::op1_range): Same.
(operator_plus::op2_range): Same.
(operator_minus::wi_fold): Same.
(operator_minus::op1_range): Same.
(operator_minus::op2_range): Same.
(operator_min::wi_fold): Same.
(operator_max::wi_fold): Same.
(cross_product_operator::wi_cross_product): Same.
(operator_mult::op1_range): New.
(operator_mult::op2_range): New.
(operator_mult::wi_fold): Adjust for irange.
(operator_div::wi_fold): Same.
(operator_exact_divide::op1_range): Same.
(operator_lshift::fold_range): Same.
(operator_lshift::wi_fold): Same.
(operator_lshift::op1_range): New.
(operator_rshift::op1_range): New.
(operator_rshift::fold_range): Adjust for irange.
(operator_rshift::wi_fold): Same.
(operator_cast::truncating_cast_p): Abstract out from
operator_cast::fold_range.
(operator_cast::fold_range): Adjust for irange and tweak for
performance.
(operator_cast::inside_domain_p): Abstract out from fold_range.
(operator_cast::fold_pair): Same.
(operator_cast::op1_range): Use abstracted methods above. Adjust
for irange and tweak for performance.
(operator_logical_and::fold_range): Adjust for irange.
(operator_logical_and::op1_range): Same.
(operator_logical_and::op2_range): Same.
(unsigned_singleton_p): New.
(operator_bitwise_and::remove_impossible_ranges): New.
(operator_bitwise_and::fold_range): New.
(wi_optimize_and_or): Adjust for irange.
(operator_bitwise_and::wi_fold): Same.
(set_nonzero_range_from_mask): New.
(operator_bitwise_and::simple_op1_range_solver): New.
(operator_bitwise_and::op1_range): Adjust for irange.
(operator_bitwise_and::op2_range): Same.
(operator_logical_or::fold_range): Same.
(operator_logical_or::op1_range): Same.
(operator_logical_or::op2_range): Same.
(operator_bitwise_or::wi_fold): Same.
(operator_bitwise_or::op1_range): Same.
(operator_bitwise_or::op2_range): Same.
(operator_bitwise_xor::wi_fold): Same.
(operator_bitwise_xor::op1_range): New.
(operator_bitwise_xor::op2_range): New.
(operator_trunc_mod::wi_fold): Adjust for irange.
(operator_logical_not::fold_range): Same.
(operator_logical_not::op1_range): Same.
(operator_bitwise_not::fold_range): Same.
(operator_bitwise_not::op1_range): Same.
(operator_cst::fold_range): Same.
(operator_identity::fold_range): Same.
(operator_identity::op1_range): Same.
(class operator_unknown): New.
(operator_unknown::fold_range): New.
(class operator_abs): Adjust for irange.
(operator_abs::wi_fold): Same.
(operator_abs::op1_range): Same.
(operator_absu::wi_fold): Same.
(class operator_negate): Same.
(operator_negate::fold_range): Same.
(operator_negate::op1_range): Same.
(operator_addr_expr::fold_range): Same.
(operator_addr_expr::op1_range): Same.
(pointer_plus_operator::wi_fold): Same.
(pointer_min_max_operator::wi_fold): Same.
(pointer_and_operator::wi_fold): Same.
(pointer_or_operator::op1_range): New.
(pointer_or_operator::op2_range): New.
(pointer_or_operator::wi_fold): Adjust for irange.
(integral_table::integral_table): Add entries for IMAGPART_EXPR
and POINTER_DIFF_EXPR.
(range_cast): Adjust for irange.
(build_range3): New.
(range3_tests): New.
(widest_irange_tests): New.
(multi_precision_range_tests): New.
(operator_tests): New.
(range_tests): New.
* range-op.h (class range_operator): Adjust for irange.
(range_cast): Same.
* tree-vrp.c (range_fold_binary_symbolics_p): Adjust for irange and
tweak for performance.
(range_fold_binary_expr): Same.
(masked_increment): Change to extern.
* tree-vrp.h (masked_increment): New.
* tree.c (cache_wide_int_in_type_cache): New function abstracted
out from wide_int_to_tree_1.
(wide_int_to_tree_1): Cache 0, 1, and MAX for pointers.
* value-range-equiv.cc (value_range_equiv::deep_copy): Use kind
method.
(value_range_equiv::move): Same.
(value_range_equiv::check): Adjust for irange.
(value_range_equiv::intersect): Same.
(value_range_equiv::union_): Same.
(value_range_equiv::dump): Same.
* value-range.cc (irange::operator=): Same.
(irange::maybe_anti_range): New.
(irange::copy_legacy_range): New.
(irange::set_undefined): Adjust for irange.
(irange::swap_out_of_order_endpoints): Abstract out from set().
(irange::set_varying): Adjust for irange.
(irange::irange_set): New.
(irange::irange_set_anti_range): New.
(irange::set): Adjust for irange.
(value_range::set_nonzero): Move to header file.
(value_range::set_zero): Move to header file.
(value_range::check): Rename to...
(irange::verify_range): ...this.
(value_range::num_pairs): Rename to...
(irange::legacy_num_pairs): ...this, and adjust for irange.
(value_range::lower_bound): Rename to...
(irange::legacy_lower_bound): ...this, and adjust for irange.
(value_range::upper_bound): Rename to...
(irange::legacy_upper_bound): ...this, and adjust for irange.
(value_range::equal_p): Rename to...
(irange::legacy_equal_p): ...this.
(value_range::operator==): Move to header file.
(irange::equal_p): New.
(irange::symbolic_p): Adjust for irange.
(irange::constant_p): Same.
(irange::singleton_p): Same.
(irange::value_inside_range): Same.
(irange::may_contain_p): Same.
(irange::contains_p): Same.
(irange::normalize_addresses): Same.
(irange::normalize_symbolics): Same.
(irange::legacy_intersect): Same.
(irange::legacy_union): Same.
(irange::union_): Same.
(irange::intersect): Same.
(irange::irange_union): New.
(irange::irange_intersect): New.
(subtract_one): New.
(irange::invert): Adjust for irange.
(dump_bound_with_infinite_markers): New.
(irange::dump): Adjust for irange.
(debug): Add irange versions.
(range_has_numeric_bounds_p): Adjust for irange.
(vrp_val_max): Move to header file.
(vrp_val_min): Move to header file.
(DEFINE_INT_RANGE_GC_STUBS): New.
(DEFINE_INT_RANGE_INSTANCE): New.
* value-range.h (class irange): New.
(class int_range): New.
(class value_range): Rename to a instantiation of int_range.
(irange::legacy_mode_p): New.
(value_range::value_range): Remove.
(irange::kind): New.
(irange::num_pairs): Adjust for irange.
(irange::type): Adjust for irange.
(irange::tree_lower_bound): New.
(irange::tree_upper_bound): New.
(irange::type): Adjust for irange.
(irange::min): Same.
(irange::max): Same.
(irange::varying_p): Same.
(irange::undefined_p): Same.
(irange::zero_p): Same.
(irange::nonzero_p): Same.
(irange::supports_type_p): Same.
(range_includes_zero_p): Same.
(gt_ggc_mx): New.
(gt_pch_nx): New.
(irange::irange): New.
(int_range::int_range): New.
(int_range::operator=): New.
(irange::set): Moved from value-range.cc and adjusted for irange.
(irange::set_undefined): Same.
(irange::set_varying): Same.
(irange::operator==): Same.
(irange::lower_bound): Same.
(irange::upper_bound): Same.
(irange::union_): Same.
(irange::intersect): Same.
(irange::set_nonzero): Same.
(irange::set_zero): Same.
(irange::normalize_min_max): New.
(vrp_val_max): Move from value-range.cc.
(vrp_val_min): Same.
* vr-values.c (vr_values::get_lattice_entry): Call value_range
constructor.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 4208c6285b6..7251c007907 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2628,13 +2628,13 @@ GTFILES = $(CPPLIB_H) $(srcdir)/input.h $(srcdir)/coretypes.h \
$(srcdir)/tree-ssa-alias.h \
$(srcdir)/tree-ssanames.h \
$(srcdir)/tree-vrp.h \
+ $(srcdir)/value-range.h \
$(srcdir)/ipa-prop.h \
$(srcdir)/trans-mem.c \
$(srcdir)/lto-streamer.h \
$(srcdir)/target-globals.h \
$(srcdir)/ipa-predicate.h \
$(srcdir)/ipa-fnsummary.h \
- $(srcdir)/value-range.h \
$(srcdir)/vtable-verify.c \
$(srcdir)/asan.c \
$(srcdir)/ubsan.c \
diff --git a/gcc/gengtype-lex.l b/gcc/gengtype-lex.l
index a5e9d2b1de6..9bf6ffa73c4 100644
--- a/gcc/gengtype-lex.l
+++ b/gcc/gengtype-lex.l
@@ -125,7 +125,10 @@ CXX_KEYWORD inline|public:|private:|protected:|template|operator|friend|static|m
"ptr_alias"/{EOID} { return PTR_ALIAS; }
"nested_ptr"/{EOID} { return NESTED_PTR; }
"user"/{EOID} { return USER_GTY; }
-[0-9]+ { return NUM; }
+[0-9]+ {
+ *yylval = XDUPVAR (const char, yytext, yyleng, yyleng+1);
+ return NUM;
+}
{IWORD}({WS}{IWORD})*/{EOID} |
"ENUM_BITFIELD"{WS}?"("{WS}?{ID}{WS}?")" {
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index fe010ff457c..10cc59509d5 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -1270,6 +1270,7 @@ initialize_node_lattices (struct cgraph_node *node)
plats->ctxlat.set_to_bottom ();
set_agg_lats_to_bottom (plats);
plats->bits_lattice.set_to_bottom ();
+ plats->m_value_range.m_vr = value_range ();
plats->m_value_range.set_to_bottom ();
}
else
@@ -3898,8 +3899,10 @@ ipcp_propagate_stage (class ipa_topo_info *topo)
{
class ipa_node_params *info = IPA_NODE_REF (node);
determine_versionability (node, info);
- info->lattices = XCNEWVEC (class ipcp_param_lattices,
- ipa_get_param_count (info));
+
+ unsigned nlattices = ipa_get_param_count (info);
+ void *chunk = XCNEWVEC (class ipcp_param_lattices, nlattices);
+ info->lattices = new (chunk) ipcp_param_lattices[nlattices];
initialize_node_lattices (node);
}
ipa_size_summary *s = ipa_size_summaries->get (node);
diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index 55a0b272a96..49bab04524b 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -82,6 +82,7 @@ along with GCC; see the file COPYING3. If not see
#include "gimplify.h"
#include "stringpool.h"
#include "attribs.h"
+#include <vector>
#include "tree-into-ssa.h"
/* Summaries. */
@@ -330,7 +331,7 @@ static void
evaluate_conditions_for_known_args (struct cgraph_node *node,
bool inline_p,
vec<tree> known_vals,
- vec<value_range> known_value_ranges,
+ const std::vector<value_range> &known_value_ranges,
vec<ipa_agg_value_set> known_aggs,
clause_t *ret_clause,
clause_t *ret_nonspec_clause)
@@ -445,7 +446,7 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
continue;
}
}
- if (c->operand_num < (int) known_value_ranges.length ()
+ if (c->operand_num < (int) known_value_ranges.size ()
&& !c->agg_contents
&& !known_value_ranges[c->operand_num].undefined_p ()
&& !known_value_ranges[c->operand_num].varying_p ()
@@ -554,7 +555,7 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
{
struct cgraph_node *callee = e->callee->ultimate_alias_target ();
class ipa_fn_summary *info = ipa_fn_summaries->get (callee);
- auto_vec<value_range, 32> known_value_ranges;
+ std::vector<value_range> known_value_ranges (32);
class ipa_edge_args *args;
if (clause_ptr)
@@ -629,8 +630,12 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
i));
if (!vr.undefined_p () && !vr.varying_p ())
{
- if (!known_value_ranges.length ())
- known_value_ranges.safe_grow_cleared (count);
+ if (!known_value_ranges.size ())
+ {
+ known_value_ranges.resize (count);
+ for (int i = 0; i < count; ++i)
+ known_value_ranges[i].set_undefined ();
+ }
known_value_ranges[i] = vr;
}
}
@@ -803,7 +808,7 @@ ipa_fn_summary_t::duplicate (cgraph_node *src,
}
evaluate_conditions_for_known_args (dst, false,
known_vals,
- vNULL,
+ std::vector<value_range> (),
vNULL,
&possible_truths,
/* We are going to specialize,
@@ -3687,7 +3692,8 @@ estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
clause_t clause, nonspec_clause;
/* TODO: Also pass known value ranges. */
- evaluate_conditions_for_known_args (node, false, known_vals, vNULL,
+ evaluate_conditions_for_known_args (node, false, known_vals,
+ std::vector<value_range> (),
known_aggs, &clause, &nonspec_clause);
ipa_call_context ctx (node, clause, nonspec_clause,
known_vals, known_contexts,
diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
index 71ac0e104d2..da50f0837fd 100644
--- a/gcc/ipa-prop.c
+++ b/gcc/ipa-prop.c
@@ -2059,7 +2059,7 @@ ipa_get_value_range (value_range *tmp)
if (*slot)
return *slot;
- value_range *vr = ggc_alloc<value_range> ();
+ value_range *vr = new (ggc_alloc<value_range> ()) value_range;
*vr = *tmp;
*slot = vr;
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index 168c4c26443..23fcf905ef3 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -318,7 +318,7 @@ struct GTY (()) ipa_jump_func
/* Information about value range, containing valid data only when vr_known is
true. The pointed to structure is shared betweed different jump
functions. Use ipa_set_jfunc_vr to set this field. */
- class value_range *m_vr;
+ value_range *m_vr;
enum jump_func_type type;
/* Represents a value of a jump function. pass_through is used only in jump
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 5df075b15b5..c62e3977ce5 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -63,15 +63,17 @@ min_limit (const_tree type)
}
// If the range of either op1 or op2 is undefined, set the result to
-// undefined and return TRUE.
+// varying and return TRUE. If the caller truely cares about a result,
+// they should pass in a varying if it has an undefined that it wants
+// treated as a varying.
inline bool
-empty_range_check (value_range &r,
- const value_range &op1, const value_range & op2)
+empty_range_varying (irange &r, tree type,
+ const irange &op1, const irange & op2)
{
if (op1.undefined_p () || op2.undefined_p ())
{
- r.set_undefined ();
+ r.set_varying (type);
return true;
}
else
@@ -82,11 +84,11 @@ empty_range_check (value_range &r,
// the appropriate range.
static inline bool
-undefined_shift_range_check (value_range &r, tree type, const value_range op)
+undefined_shift_range_check (irange &r, tree type, const irange &op)
{
if (op.undefined_p ())
{
- r = value_range ();
+ r.set_undefined ();
return true;
}
@@ -98,7 +100,7 @@ undefined_shift_range_check (value_range &r, tree type, const value_range op)
|| wi::ge_p (op.upper_bound (),
TYPE_PRECISION (type), TYPE_SIGN (op.type ())))
{
- r = value_range (type);
+ r.set_varying (type);
return true;
}
return false;
@@ -125,32 +127,43 @@ wi_zero_p (tree type, const wide_int &wmin, const wide_int &wmax)
// Default wide_int fold operation returns [MIN, MAX].
void
-range_operator::wi_fold (value_range &r, tree type,
+range_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb ATTRIBUTE_UNUSED,
const wide_int &lh_ub ATTRIBUTE_UNUSED,
const wide_int &rh_lb ATTRIBUTE_UNUSED,
const wide_int &rh_ub ATTRIBUTE_UNUSED) const
{
- gcc_checking_assert (value_range::supports_type_p (type));
- r = value_range (type);
+ gcc_checking_assert (irange::supports_type_p (type));
+ r.set_varying (type);
}
// The default for fold is to break all ranges into sub-ranges and
// invoke the wi_fold method on each sub-range pair.
bool
-range_operator::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+range_operator::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- gcc_checking_assert (value_range::supports_type_p (type));
- if (empty_range_check (r, lh, rh))
+ gcc_checking_assert (irange::supports_type_p (type));
+ if (empty_range_varying (r, type, lh, rh))
return true;
- value_range tmp;
+ unsigned num_lh = lh.num_pairs ();
+ unsigned num_rh = rh.num_pairs ();
+
+ // If both ranges are single pairs, fold directly into the result range.
+ if (num_lh == 1 && num_rh == 1)
+ {
+ wi_fold (r, type, lh.lower_bound (0), lh.upper_bound (0),
+ rh.lower_bound (0), rh.upper_bound (0));
+ return true;
+ }
+
+ widest_irange tmp;
r.set_undefined ();
- for (unsigned x = 0; x < lh.num_pairs (); ++x)
- for (unsigned y = 0; y < rh.num_pairs (); ++y)
+ for (unsigned x = 0; x < num_lh; ++x)
+ for (unsigned y = 0; y < num_rh; ++y)
{
wide_int lh_lb = lh.lower_bound (x);
wide_int lh_ub = lh.upper_bound (x);
@@ -167,10 +180,10 @@ range_operator::fold_range (value_range &r, tree type,
// The default for op1_range is to return false.
bool
-range_operator::op1_range (value_range &r ATTRIBUTE_UNUSED,
+range_operator::op1_range (irange &r ATTRIBUTE_UNUSED,
tree type ATTRIBUTE_UNUSED,
- const value_range &lhs ATTRIBUTE_UNUSED,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+ const irange &lhs ATTRIBUTE_UNUSED,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
return false;
}
@@ -178,10 +191,10 @@ range_operator::op1_range (value_range &r ATTRIBUTE_UNUSED,
// The default for op2_range is to return false.
bool
-range_operator::op2_range (value_range &r ATTRIBUTE_UNUSED,
+range_operator::op2_range (irange &r ATTRIBUTE_UNUSED,
tree type ATTRIBUTE_UNUSED,
- const value_range &lhs ATTRIBUTE_UNUSED,
- const value_range &op1 ATTRIBUTE_UNUSED) const
+ const irange &lhs ATTRIBUTE_UNUSED,
+ const irange &op1 ATTRIBUTE_UNUSED) const
{
return false;
}
@@ -191,7 +204,7 @@ range_operator::op2_range (value_range &r ATTRIBUTE_UNUSED,
// to have overflowed (or underflowed).
static void
-value_range_from_overflowed_bounds (value_range &r, tree type,
+value_range_from_overflowed_bounds (irange &r, tree type,
const wide_int &wmin,
const wide_int &wmax)
{
@@ -214,9 +227,13 @@ value_range_from_overflowed_bounds (value_range &r, tree type,
// Likewise if the anti-range bounds are outside of the types
// values.
if (covers || wi::cmp (tmin, tmax, sgn) > 0)
- r = value_range (type);
+ r.set_varying (type);
else
- r = value_range (type, tmin, tmax, VR_ANTI_RANGE);
+ {
+ tree tree_min = wide_int_to_tree (type, tmin);
+ tree tree_max = wide_int_to_tree (type, tmax);
+ r.set (tree_min, tree_max, VR_ANTI_RANGE);
+ }
}
// Create and return a range from a pair of wide-ints. MIN_OVF and
@@ -224,7 +241,7 @@ value_range_from_overflowed_bounds (value_range &r, tree type,
// calculating WMIN and WMAX respectively.
static void
-value_range_with_overflow (value_range &r, tree type,
+value_range_with_overflow (irange &r, tree type,
const wide_int &wmin, const wide_int &wmax,
wi::overflow_type min_ovf = wi::OVF_NONE,
wi::overflow_type max_ovf = wi::OVF_NONE)
@@ -237,7 +254,7 @@ value_range_with_overflow (value_range &r, tree type,
// values.
if (prec == 1 && wi::ne_p (wmax, wmin))
{
- r = value_range (type);
+ r.set_varying (type);
return;
}
@@ -252,11 +269,12 @@ value_range_with_overflow (value_range &r, tree type,
// If the limits are swapped, we wrapped around and cover
// the entire range.
if (wi::gt_p (tmin, tmax, sgn))
- r = value_range (type);
+ r.set_varying (type);
else
// No overflow or both overflow or underflow. The range
// kind stays normal.
- r = value_range (type, tmin, tmax);
+ r.set (wide_int_to_tree (type, tmin),
+ wide_int_to_tree (type, tmax));
return;
}
@@ -265,7 +283,7 @@ value_range_with_overflow (value_range &r, tree type,
value_range_from_overflowed_bounds (r, type, wmin, wmax);
else
// Other underflow and/or overflow, drop to VR_VARYING.
- r = value_range (type);
+ r.set_varying (type);
}
else
{
@@ -285,7 +303,8 @@ value_range_with_overflow (value_range &r, tree type,
else
new_ub = wmax;
- r = value_range (type, new_lb, new_ub);
+ r.set (wide_int_to_tree (type, new_lb),
+ wide_int_to_tree (type, new_ub));
}
}
@@ -294,7 +313,7 @@ value_range_with_overflow (value_range &r, tree type,
// [10,5] into [MIN,5][10,MAX].
static inline void
-create_possibly_reversed_range (value_range &r, tree type,
+create_possibly_reversed_range (irange &r, tree type,
const wide_int &new_lb, const wide_int &new_ub)
{
signop s = TYPE_SIGN (type);
@@ -302,35 +321,35 @@ create_possibly_reversed_range (value_range &r, tree type,
if (wi::gt_p (new_lb, new_ub, s))
value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
else
- // Otherwise its just a normal range.
- r = value_range (type, new_lb, new_ub);
+ // Otherwise it's just a normal range.
+ r.set (wide_int_to_tree (type, new_lb), wide_int_to_tree (type, new_ub));
}
-// Return a value_range instance that is a boolean TRUE.
+// Return an irange instance that is a boolean TRUE.
-static inline value_range
+static inline int_range<1>
range_true (tree type)
{
unsigned prec = TYPE_PRECISION (type);
- return value_range (type, wi::one (prec), wi::one (prec));
+ return int_range<1> (type, wi::one (prec), wi::one (prec));
}
-// Return a value_range instance that is a boolean FALSE.
+// Return an irange instance that is a boolean FALSE.
-static inline value_range
+static inline int_range<1>
range_false (tree type)
{
unsigned prec = TYPE_PRECISION (type);
- return value_range (type, wi::zero (prec), wi::zero (prec));
+ return int_range<1> (type, wi::zero (prec), wi::zero (prec));
}
-// Return a value_range that covers both true and false.
+// Return an irange that covers both true and false.
-static inline value_range
+static inline int_range<1>
range_true_and_false (tree type)
{
unsigned prec = TYPE_PRECISION (type);
- return value_range (type, wi::zero (prec), wi::one (prec));
+ return int_range<1> (type, wi::zero (prec), wi::one (prec));
}
enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL };
@@ -341,7 +360,7 @@ enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL };
// the bool range.
static bool_range_state
-get_bool_state (value_range &r, const value_range &lhs, tree val_type)
+get_bool_state (irange &r, const irange &lhs, tree val_type)
{
// If there is no result, then this is unexecutable.
if (lhs.undefined_p ())
@@ -350,16 +369,16 @@ get_bool_state (value_range &r, const value_range &lhs, tree val_type)
return BRS_EMPTY;
}
- // If the bounds aren't the same, then it's not a constant.
- if (!wi::eq_p (lhs.upper_bound (), lhs.lower_bound ()))
+ if (lhs.zero_p ())
+ return BRS_FALSE;
+
+ // For TRUE, we can't just test for [1,1] because Ada can have
+ // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
+ if (lhs.contains_p (build_zero_cst (lhs.type ())))
{
r.set_varying (val_type);
return BRS_FULL;
}
-
- if (lhs.zero_p ())
- return BRS_FALSE;
-
return BRS_TRUE;
}
@@ -367,23 +386,23 @@ get_bool_state (value_range &r, const value_range &lhs, tree val_type)
class operator_equal : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &val) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &val) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &val) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &val) const;
} op_equal;
bool
-operator_equal::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_equal::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
// We can be sure the values are always equal or not if both ranges
@@ -411,9 +430,9 @@ operator_equal::fold_range (value_range &r, tree type,
}
bool
-operator_equal::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_equal::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -441,9 +460,9 @@ operator_equal::op1_range (value_range &r, tree type,
}
bool
-operator_equal::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_equal::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_equal::op1_range (r, type, lhs, op1);
}
@@ -452,23 +471,23 @@ operator_equal::op2_range (value_range &r, tree type,
class operator_not_equal : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_not_equal;
bool
-operator_not_equal::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_not_equal::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
// We can be sure the values are always equal or not if both ranges
@@ -496,9 +515,9 @@ operator_not_equal::fold_range (value_range &r, tree type,
}
bool
-operator_not_equal::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_not_equal::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -527,9 +546,9 @@ operator_not_equal::op1_range (value_range &r, tree type,
bool
-operator_not_equal::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_not_equal::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_not_equal::op1_range (r, type, lhs, op1);
}
@@ -537,7 +556,7 @@ operator_not_equal::op2_range (value_range &r, tree type,
// (X < VAL) produces the range of [MIN, VAL - 1].
static void
-build_lt (value_range &r, tree type, const wide_int &val)
+build_lt (irange &r, tree type, const wide_int &val)
{
wi::overflow_type ov;
wide_int lim = wi::sub (val, 1, TYPE_SIGN (type), &ov);
@@ -546,21 +565,21 @@ build_lt (value_range &r, tree type, const wide_int &val)
if (ov)
r.set_undefined ();
else
- r = value_range (type, min_limit (type), lim);
+ r = int_range<1> (type, min_limit (type), lim);
}
// (X <= VAL) produces the range of [MIN, VAL].
static void
-build_le (value_range &r, tree type, const wide_int &val)
+build_le (irange &r, tree type, const wide_int &val)
{
- r = value_range (type, min_limit (type), val);
+ r = int_range<1> (type, min_limit (type), val);
}
// (X > VAL) produces the range of [VAL + 1, MAX].
static void
-build_gt (value_range &r, tree type, const wide_int &val)
+build_gt (irange &r, tree type, const wide_int &val)
{
wi::overflow_type ov;
wide_int lim = wi::add (val, 1, TYPE_SIGN (type), &ov);
@@ -568,38 +587,38 @@ build_gt (value_range &r, tree type, const wide_int &val)
if (ov)
r.set_undefined ();
else
- r = value_range (type, lim, max_limit (type));
+ r = int_range<1> (type, lim, max_limit (type));
}
// (X >= val) produces the range of [VAL, MAX].
static void
-build_ge (value_range &r, tree type, const wide_int &val)
+build_ge (irange &r, tree type, const wide_int &val)
{
- r = value_range (type, val, max_limit (type));
+ r = int_range<1> (type, val, max_limit (type));
}
class operator_lt : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_lt;
bool
-operator_lt::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_lt::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
signop sign = TYPE_SIGN (op1.type ());
@@ -615,9 +634,9 @@ operator_lt::fold_range (value_range &r, tree type,
}
bool
-operator_lt::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_lt::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -636,9 +655,9 @@ operator_lt::op1_range (value_range &r, tree type,
}
bool
-operator_lt::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_lt::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -660,23 +679,23 @@ operator_lt::op2_range (value_range &r, tree type,
class operator_le : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_le;
bool
-operator_le::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_le::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
signop sign = TYPE_SIGN (op1.type ());
@@ -692,9 +711,9 @@ operator_le::fold_range (value_range &r, tree type,
}
bool
-operator_le::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_le::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -713,9 +732,9 @@ operator_le::op1_range (value_range &r, tree type,
}
bool
-operator_le::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_le::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -737,22 +756,22 @@ operator_le::op2_range (value_range &r, tree type,
class operator_gt : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_gt;
bool
-operator_gt::fold_range (value_range &r, tree type,
- const value_range &op1, const value_range &op2) const
+operator_gt::fold_range (irange &r, tree type,
+ const irange &op1, const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
signop sign = TYPE_SIGN (op1.type ());
@@ -768,8 +787,8 @@ operator_gt::fold_range (value_range &r, tree type,
}
bool
-operator_gt::op1_range (value_range &r, tree type,
- const value_range &lhs, const value_range &op2) const
+operator_gt::op1_range (irange &r, tree type,
+ const irange &lhs, const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -788,9 +807,9 @@ operator_gt::op1_range (value_range &r, tree type,
}
bool
-operator_gt::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_gt::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -812,23 +831,23 @@ operator_gt::op2_range (value_range &r, tree type,
class operator_ge : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_ge;
bool
-operator_ge::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_ge::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
signop sign = TYPE_SIGN (op1.type ());
@@ -844,9 +863,9 @@ operator_ge::fold_range (value_range &r, tree type,
}
bool
-operator_ge::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_ge::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -865,9 +884,9 @@ operator_ge::op1_range (value_range &r, tree type,
}
bool
-operator_ge::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_ge::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -889,13 +908,13 @@ operator_ge::op2_range (value_range &r, tree type,
class operator_plus : public range_operator
{
public:
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -903,7 +922,7 @@ public:
} op_plus;
void
-operator_plus::wi_fold (value_range &r, tree type,
+operator_plus::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
@@ -915,17 +934,17 @@ operator_plus::wi_fold (value_range &r, tree type,
}
bool
-operator_plus::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_plus::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op2);
}
bool
-operator_plus::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_plus::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op1);
}
@@ -934,13 +953,13 @@ operator_plus::op2_range (value_range &r, tree type,
class operator_minus : public range_operator
{
public:
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -948,7 +967,7 @@ public:
} op_minus;
void
-operator_minus::wi_fold (value_range &r, tree type,
+operator_minus::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
@@ -960,17 +979,17 @@ operator_minus::wi_fold (value_range &r, tree type,
}
bool
-operator_minus::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_minus::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
return range_op_handler (PLUS_EXPR, type)->fold_range (r, type, lhs, op2);
}
bool
-operator_minus::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_minus::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return fold_range (r, type, op1, lhs);
}
@@ -979,7 +998,7 @@ operator_minus::op2_range (value_range &r, tree type,
class operator_min : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -987,7 +1006,7 @@ public:
} op_min;
void
-operator_min::wi_fold (value_range &r, tree type,
+operator_min::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
@@ -1001,7 +1020,7 @@ operator_min::wi_fold (value_range &r, tree type,
class operator_max : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -1009,7 +1028,7 @@ public:
} op_max;
void
-operator_max::wi_fold (value_range &r, tree type,
+operator_max::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
@@ -1031,7 +1050,7 @@ public:
const wide_int &) const = 0;
// Calculate the cross product of two sets of sub-ranges and return it.
- void wi_cross_product (value_range &r, tree type,
+ void wi_cross_product (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -1052,7 +1071,7 @@ public:
// figure the smallest and largest values to form the new range.
void
-cross_product_operator::wi_cross_product (value_range &r, tree type,
+cross_product_operator::wi_cross_product (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -1060,7 +1079,7 @@ cross_product_operator::wi_cross_product (value_range &r, tree type,
{
wide_int cp1, cp2, cp3, cp4;
// Default to varying.
- r = value_range (type);
+ r.set_varying (type);
// Compute the 4 cross operations, bailing if we get an overflow we
// can't handle.
@@ -1096,15 +1115,46 @@ cross_product_operator::wi_cross_product (value_range &r, tree type,
class operator_mult : public cross_product_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
virtual bool wi_op_overflows (wide_int &res, tree type,
const wide_int &w0, const wide_int &w1) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_mult;
+bool
+operator_mult::op1_range (irange &r, tree type,
+ const irange &lhs, const irange &op2) const
+{
+ tree offset;
+
+ // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
+ // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
+ // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
+ if (TYPE_OVERFLOW_WRAPS (type))
+ return false;
+
+ if (op2.singleton_p (&offset) && !integer_zerop (offset))
+ return range_op_handler (TRUNC_DIV_EXPR, type)->fold_range (r, type,
+ lhs, op2);
+ return false;
+}
+
+bool
+operator_mult::op2_range (irange &r, tree type,
+ const irange &lhs, const irange &op1) const
+{
+ return operator_mult::op1_range (r, type, lhs, op1);
+}
+
bool
operator_mult::wi_op_overflows (wide_int &res, tree type,
const wide_int &w0, const wide_int &w1) const
@@ -1126,7 +1176,7 @@ operator_mult::wi_op_overflows (wide_int &res, tree type,
}
void
-operator_mult::wi_fold (value_range &r, tree type,
+operator_mult::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
@@ -1195,7 +1245,7 @@ operator_mult::wi_fold (value_range &r, tree type,
prod2 = prod3 - prod0;
if (wi::geu_p (prod2, sizem1))
// The range covers all values.
- r = value_range (type);
+ r.set_varying (type);
else
{
wide_int new_lb = wide_int::from (prod0, prec, sign);
@@ -1209,7 +1259,7 @@ class operator_div : public cross_product_operator
{
public:
operator_div (enum tree_code c) { code = c; }
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -1263,14 +1313,14 @@ operator_div::wi_op_overflows (wide_int &res, tree type,
}
void
-operator_div::wi_fold (value_range &r, tree type,
+operator_div::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
// If we know we will divide by zero, return undefined.
if (rh_lb == 0 && rh_ub == 0)
{
- r = value_range ();
+ r.set_undefined ();
return;
}
@@ -1293,14 +1343,14 @@ operator_div::wi_fold (value_range &r, tree type,
// If flag_non_call_exceptions, we must not eliminate a division by zero.
if (cfun->can_throw_non_call_exceptions)
{
- r = value_range (type);
+ r.set_varying (type);
return;
}
// If we're definitely dividing by zero, there's nothing to do.
if (wi_zero_p (type, divisor_min, divisor_max))
{
- r = value_range ();
+ r.set_undefined ();
return;
}
@@ -1312,12 +1362,12 @@ operator_div::wi_fold (value_range &r, tree type,
wi_cross_product (r, type, dividend_min, dividend_max,
divisor_min, wi::minus_one (prec));
else
- r = value_range ();
+ r.set_undefined ();
// Then divide by the non-zero positive numbers, if any.
if (wi::gt_p (divisor_max, wi::zero (prec), sign))
{
- value_range tmp;
+ widest_irange tmp;
wi_cross_product (tmp, type, dividend_min, dividend_max,
wi::one (prec), divisor_max);
r.union_ (tmp);
@@ -1336,16 +1386,16 @@ class operator_exact_divide : public operator_div
{
public:
operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { }
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_exact_div;
bool
-operator_exact_divide::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_exact_divide::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
tree offset;
// [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
@@ -1364,11 +1414,14 @@ operator_exact_divide::op1_range (value_range &r, tree type,
class operator_lshift : public cross_product_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
-
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
virtual bool wi_op_overflows (wide_int &res,
@@ -1378,9 +1431,9 @@ public:
} op_lshift;
bool
-operator_lshift::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_lshift::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
if (undefined_shift_range_check (r, type, op2))
return true;
@@ -1390,15 +1443,14 @@ operator_lshift::fold_range (value_range &r, tree type,
{
unsigned shift = op2.lower_bound ().to_uhwi ();
wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
- value_range mult (type, tmp, tmp);
+ int_range<1> mult (type, tmp, tmp);
// Force wrapping multiplication.
bool saved_flag_wrapv = flag_wrapv;
bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
flag_wrapv = 1;
flag_wrapv_pointer = 1;
- bool b = range_op_handler (MULT_EXPR, type)->fold_range (r, type, op1,
- mult);
+ bool b = op_mult.fold_range (r, type, op1, mult);
flag_wrapv = saved_flag_wrapv;
flag_wrapv_pointer = saved_flag_wrapv_pointer;
return b;
@@ -1409,7 +1461,7 @@ operator_lshift::fold_range (value_range &r, tree type,
}
void
-operator_lshift::wi_fold (value_range &r, tree type,
+operator_lshift::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
@@ -1465,7 +1517,7 @@ operator_lshift::wi_fold (value_range &r, tree type,
if (in_bounds)
wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
else
- r = value_range (type);
+ r.set_varying (type);
}
bool
@@ -1485,14 +1537,56 @@ operator_lshift::wi_op_overflows (wide_int &res, tree type,
return false;
}
+bool
+operator_lshift::op1_range (irange &r,
+ tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ tree shift_amount;
+ if (op2.singleton_p (&shift_amount))
+ {
+ int_range<1> shifted (shift_amount, shift_amount), ub, lb;
+ const range_operator *rshift_op = range_op_handler (RSHIFT_EXPR, type);
+ rshift_op->fold_range (ub, type, lhs, shifted);
+ if (TYPE_UNSIGNED (type))
+ {
+ r = ub;
+ return true;
+ }
+ // For signed types, we can't just do an arithmetic rshift,
+ // because that will propagate the sign bit.
+ //
+ // LHS
+ // 1110 = OP1 << 1
+ //
+ // Assuming a 4-bit signed integer, a right shift will result in
+ // OP1=1111, but OP1 could have also been 0111. What we want is
+ // a range from 0111 to 1111. That is, a range from the logical
+ // rshift (0111) to the arithmetic rshift (1111).
+ //
+ // Perform a logical rshift by doing the rshift as unsigned.
+ tree unsigned_type = unsigned_type_for (type);
+ widest_irange unsigned_lhs = lhs;
+ range_cast (unsigned_lhs, unsigned_type);
+ rshift_op = range_op_handler (RSHIFT_EXPR, unsigned_type);
+ rshift_op->fold_range (lb, unsigned_type, unsigned_lhs, shifted);
+ range_cast (lb, type);
+ r = lb;
+ r.union_ (ub);
+ return true;
+ }
+ return false;
+}
+
class operator_rshift : public cross_product_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -1501,8 +1595,57 @@ public:
tree type,
const wide_int &w0,
const wide_int &w1) const;
+ virtual bool op1_range (irange &, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_rshift;
+bool
+operator_rshift::op1_range (irange &r,
+ tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ tree shift;
+ if (op2.singleton_p (&shift))
+ {
+ // Folding the original operation may discard some impossible
+ // ranges from the LHS.
+ widest_irange lhs_refined;
+ op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
+ lhs_refined.intersect (lhs);
+ if (lhs_refined.undefined_p ())
+ {
+ r.set_undefined ();
+ return true;
+ }
+ widest_irange shift_range (shift, shift);
+ widest_irange lb, ub;
+ op_lshift.fold_range (lb, type, lhs_refined, shift_range);
+ // LHS
+ // 0000 0111 = OP1 >> 3
+ //
+ // OP1 is anything from 0011 1000 to 0011 1111. That is, a
+ // range from LHS<<3 plus a mask of the 3 bits we shifted on the
+ // right hand side (0x07).
+ tree mask = fold_build1 (BIT_NOT_EXPR, type,
+ fold_build2 (LSHIFT_EXPR, type,
+ build_minus_one_cst (type),
+ shift));
+ widest_irange mask_range (build_zero_cst (type), mask);
+ op_plus.fold_range (ub, type, lb, mask_range);
+ r = lb;
+ r.union_ (ub);
+ if (!lhs_refined.contains_p (build_zero_cst (type)))
+ {
+ mask_range.invert ();
+ r.intersect (mask_range);
+ }
+ return true;
+ }
+ return false;
+}
+
bool
operator_rshift::wi_op_overflows (wide_int &res,
tree type,
@@ -1523,9 +1666,9 @@ operator_rshift::wi_op_overflows (wide_int &res,
}
bool
-operator_rshift::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_rshift::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
// Invoke the generic fold routine if not undefined..
if (undefined_shift_range_check (r, type, op2))
@@ -1535,7 +1678,7 @@ operator_rshift::fold_range (value_range &r, tree type,
}
void
-operator_rshift::wi_fold (value_range &r, tree type,
+operator_rshift::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
@@ -1546,139 +1689,180 @@ operator_rshift::wi_fold (value_range &r, tree type,
class operator_cast: public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
-
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+private:
+ bool truncating_cast_p (const irange &inner, const irange &outer) const;
+ bool inside_domain_p (const wide_int &min, const wide_int &max,
+ const irange &outer) const;
+ void fold_pair (irange &r, unsigned index, const irange &inner,
+ const irange &outer) const;
} op_convert;
+// Return TRUE if casting from INNER to OUTER is a truncating cast.
+
+inline bool
+operator_cast::truncating_cast_p (const irange &inner,
+ const irange &outer) const
+{
+ return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
+}
+
+// Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
+
bool
-operator_cast::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lh,
- const value_range &rh) const
+operator_cast::inside_domain_p (const wide_int &min,
+ const wide_int &max,
+ const irange &range) const
{
- if (empty_range_check (r, lh, rh))
- return true;
-
- tree inner = lh.type ();
- tree outer = rh.type ();
- gcc_checking_assert (rh.varying_p ());
- gcc_checking_assert (types_compatible_p (outer, type));
- signop inner_sign = TYPE_SIGN (inner);
- signop outer_sign = TYPE_SIGN (outer);
- unsigned inner_prec = TYPE_PRECISION (inner);
- unsigned outer_prec = TYPE_PRECISION (outer);
-
- // Start with an empty range and add subranges.
- r = value_range ();
- for (unsigned x = 0; x < lh.num_pairs (); ++x)
- {
- wide_int lh_lb = lh.lower_bound (x);
- wide_int lh_ub = lh.upper_bound (x);
-
- // If the conversion is not truncating we can convert the min
- // and max values and canonicalize the resulting range.
- // Otherwise, we can do the conversion if the size of the range
- // is less than what the precision of the target type can
- // represent.
- if (outer_prec >= inner_prec
- || wi::rshift (wi::sub (lh_ub, lh_lb),
- wi::uhwi (outer_prec, inner_prec),
- inner_sign) == 0)
+ wide_int domain_min = wi::to_wide (vrp_val_min (range.type ()));
+ wide_int domain_max = wi::to_wide (vrp_val_max (range.type ()));
+ signop domain_sign = TYPE_SIGN (range.type ());
+ return (wi::le_p (min, domain_max, domain_sign)
+ && wi::le_p (max, domain_max, domain_sign)
+ && wi::ge_p (min, domain_min, domain_sign)
+ && wi::ge_p (max, domain_min, domain_sign));
+}
+
+
+// Helper for fold_range which work on a pair at a time.
+
+void
+operator_cast::fold_pair (irange &r, unsigned index,
+ const irange &inner,
+ const irange &outer) const
+{
+ tree inner_type = inner.type ();
+ tree outer_type = outer.type ();
+ signop inner_sign = TYPE_SIGN (inner_type);
+ unsigned outer_prec = TYPE_PRECISION (outer_type);
+
+ // check to see if casting from INNER to OUTER is a conversion that
+ // fits in the resulting OUTER type.
+ wide_int inner_lb = inner.lower_bound (index);
+ wide_int inner_ub = inner.upper_bound (index);
+ if (truncating_cast_p (inner, outer))
+ {
+ // We may be able to accomodate a truncating cast if the
+ // resulting range can be represented in the target type...
+ if (wi::rshift (wi::sub (inner_ub, inner_lb),
+ wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
+ inner_sign) != 0)
{
- wide_int min = wide_int::from (lh_lb, outer_prec, inner_sign);
- wide_int max = wide_int::from (lh_ub, outer_prec, inner_sign);
- if (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign))
- || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign)))
- {
- value_range tmp;
- create_possibly_reversed_range (tmp, type, min, max);
- r.union_ (tmp);
- continue;
- }
+ r.set_varying (outer_type);
+ return;
}
- r = value_range (type);
- break;
+ }
+ // ...but we must still verify that the final range fits in the
+ // domain. This catches -fstrict-enum restrictions where the domain
+ // range is smaller than what fits in the underlying type.
+ wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
+ wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
+ if (inside_domain_p (min, max, outer))
+ create_possibly_reversed_range (r, outer_type, min, max);
+ else
+ r.set_varying (outer_type);
+}
+
+
+bool
+operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &inner,
+ const irange &outer) const
+{
+ if (empty_range_varying (r, type, inner, outer))
+ return true;
+
+ gcc_checking_assert (outer.varying_p ());
+ gcc_checking_assert (inner.num_pairs () > 0);
+
+ // Avoid a temporary by folding the first pair directly into the result.
+ fold_pair (r, 0, inner, outer);
+
+ // Then process any additonal pairs by unioning with their results.
+ for (unsigned x = 1; x < inner.num_pairs (); ++x)
+ {
+ widest_irange tmp;
+ fold_pair (tmp, x, inner, outer);
+ r.union_ (tmp);
+ if (r.varying_p ())
+ return true;
}
return true;
}
bool
-operator_cast::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_cast::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
tree lhs_type = lhs.type ();
- value_range tmp;
gcc_checking_assert (types_compatible_p (op2.type(), type));
- // If the precision of the LHS is smaller than the precision of the
- // RHS, then there would be truncation of the value on the RHS, and
- // so we can tell nothing about it.
- if (TYPE_PRECISION (lhs_type) < TYPE_PRECISION (type))
- {
- // If we've been passed an actual value for the RHS rather than
- // the type, see if it fits the LHS, and if so, then we can allow
- // it.
- fold_range (r, lhs_type, op2, value_range (lhs_type));
- fold_range (tmp, type, r, value_range (type));
- if (tmp == op2)
+ if (truncating_cast_p (op2, lhs))
+ {
+ if (lhs.varying_p ())
+ r.set_varying (type);
+ else
{
- // We know the value of the RHS fits in the LHS type, so
- // convert the LHS and remove any values that arent in OP2.
- fold_range (r, type, lhs, value_range (type));
- r.intersect (op2);
- return true;
- }
- // Special case if the LHS is a boolean. A 0 means the RHS is
- // zero, and a 1 means the RHS is non-zero.
- if (TREE_CODE (lhs_type) == BOOLEAN_TYPE)
- {
- // If the LHS is unknown, the result is whatever op2 already is.
- if (!lhs.singleton_p ())
- {
- r = op2;
- return true;
- }
- // Boolean casts are weird in GCC. It's actually an implied
- // mask with 0x01, so all that is known is whether the
- // rightmost bit is 0 or 1, which implies the only value
- // *not* in the RHS is 0 or -1.
- unsigned prec = TYPE_PRECISION (type);
- if (lhs.zero_p ())
- r = value_range (type, wi::minus_one (prec), wi::minus_one (prec),
- VR_ANTI_RANGE);
- else
- r = value_range (type, wi::zero (prec), wi::zero (prec),
- VR_ANTI_RANGE);
- // And intersect it with what we know about op2.
- r.intersect (op2);
+ // We want to insert the LHS as an unsigned value since it
+ // would not trigger the signed bit of the larger type.
+ widest_irange converted_lhs = lhs;
+ range_cast (converted_lhs, unsigned_type_for (lhs_type));
+ range_cast (converted_lhs, type);
+ // Start by building the positive signed outer range for the type.
+ wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
+ TYPE_PRECISION (type));
+ r = int_range<1> (type, lim, wi::max_value (TYPE_PRECISION (type),
+ SIGNED));
+ // For the signed part, we need to simply union the 2 ranges now.
+ r.union_ (converted_lhs);
+
+ // Create maximal negative number outside of LHS bits.
+ lim = wi::mask (TYPE_PRECISION (lhs_type), true,
+ TYPE_PRECISION (type));
+ // Add this to the unsigned LHS range(s).
+ widest_irange lim_range (type, lim, lim);
+ widest_irange lhs_neg;
+ range_op_handler (PLUS_EXPR, type)->fold_range (lhs_neg,
+ type,
+ converted_lhs,
+ lim_range);
+ // And union this with the entire outer types negative range.
+ widest_irange neg (type,
+ wi::min_value (TYPE_PRECISION (type),
+ SIGNED),
+ lim - 1);
+ neg.union_ (lhs_neg);
+ // And finally, munge the signed and unsigned portions.
+ r.union_ (neg);
}
- else
- // Otherwise we'll have to assume it's whatever we know about op2.
- r = op2;
+ // And intersect with any known value passed in the extra operand.
+ r.intersect (op2);
return true;
}
- // If the LHS precision is greater than the rhs precision, the LHS
- // range is restricted to the range of the RHS by this
- // assignment.
- if (TYPE_PRECISION (lhs_type) > TYPE_PRECISION (type))
+ widest_irange tmp;
+ if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
+ tmp = lhs;
+ else
{
+ // The cast is not truncating, and the range is restricted to
+ // the range of the RHS by this assignment.
+ //
// Cast the range of the RHS to the type of the LHS.
- fold_range (tmp, lhs_type, value_range (type), value_range (lhs_type));
- // Intersect this with the LHS range will produce the range, which
- // will be cast to the RHS type before returning.
+ fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
+ // Intersect this with the LHS range will produce the range,
+ // which will be cast to the RHS type before returning.
tmp.intersect (lhs);
}
- else
- tmp = lhs;
// Cast the calculated range to the type of the RHS.
- fold_range (r, type, tmp, value_range (type));
+ fold_range (r, type, tmp, int_range<1> (type));
return true;
}
@@ -1686,24 +1870,24 @@ operator_cast::op1_range (value_range &r, tree type,
class operator_logical_and : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_logical_and;
bool
-operator_logical_and::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+operator_logical_and::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
// 0 && anything is 0.
@@ -1721,9 +1905,9 @@ operator_logical_and::fold_range (value_range &r, tree type,
}
bool
-operator_logical_and::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+operator_logical_and::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -1742,9 +1926,9 @@ operator_logical_and::op1_range (value_range &r, tree type,
}
bool
-operator_logical_and::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_logical_and::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_logical_and::op1_range (r, type, lhs, op1);
}
@@ -1753,19 +1937,106 @@ operator_logical_and::op2_range (value_range &r, tree type,
class operator_bitwise_and : public range_operator
{
public:
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
+private:
+ void simple_op1_range_solver (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ void remove_impossible_ranges (irange &r, const irange &rh) const;
} op_bitwise_and;
+static bool
+unsigned_singleton_p (const irange &op)
+{
+ tree mask;
+ if (op.singleton_p (&mask))
+ {
+ wide_int x = wi::to_wide (mask);
+ return wi::ge_p (x, 0, TYPE_SIGN (op.type ()));
+ }
+ return false;
+}
+
+// Remove any ranges from R that are known to be impossible when an
+// range is ANDed with MASK.
+
+void
+operator_bitwise_and::remove_impossible_ranges (irange &r,
+ const irange &rmask) const
+{
+ if (r.undefined_p () || !unsigned_singleton_p (rmask))
+ return;
+
+ wide_int mask = rmask.lower_bound ();
+ tree type = r.type ();
+ int prec = TYPE_PRECISION (type);
+ int leading_zeros = wi::clz (mask);
+ widest_irange impossible_ranges;
+
+ /* We know that starting at the most significant bit, any 0 in the
+ mask means the resulting range cannot contain a 1 in that same
+ position. This means the following ranges are impossible:
+
+ x & 0b1001 1010
+ IMPOSSIBLE RANGES
+ 01xx xxxx [0100 0000, 0111 1111]
+ 001x xxxx [0010 0000, 0011 1111]
+ 0000 01xx [0000 0100, 0000 0111]
+ 0000 0001 [0000 0001, 0000 0001]
+ */
+ wide_int one = wi::one (prec);
+ for (int i = 0; i < prec - leading_zeros - 1; ++i)
+ if (wi::bit_and (mask, wi::lshift (one, wi::uhwi (i, prec))) == 0)
+ {
+ tree lb = fold_build2 (LSHIFT_EXPR, type,
+ build_one_cst (type),
+ build_int_cst (type, i));
+ tree ub_left = fold_build1 (BIT_NOT_EXPR, type,
+ fold_build2 (LSHIFT_EXPR, type,
+ build_minus_one_cst (type),
+ build_int_cst (type, i)));
+ tree ub_right = fold_build2 (LSHIFT_EXPR, type,
+ build_one_cst (type),
+ build_int_cst (type, i));
+ tree ub = fold_build2 (BIT_IOR_EXPR, type, ub_left, ub_right);
+ impossible_ranges.union_ (int_range<1> (lb, ub));
+ }
+ if (!impossible_ranges.undefined_p ())
+ {
+ impossible_ranges.invert ();
+ r.intersect (impossible_ranges);
+ }
+}
+
+bool
+operator_bitwise_and::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
+{
+ if (range_operator::fold_range (r, type, lh, rh))
+ {
+ // FIXME: This is temporarily disabled because, though it
+ // generates better ranges, it's noticeably slower for evrp.
+ // remove_impossible_ranges (r, rh);
+ return true;
+ }
+ return false;
+}
+
+
// Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
// possible. Basically, see if we can optimize:
//
@@ -1777,7 +2048,7 @@ public:
// return TRUE.
static bool
-wi_optimize_and_or (value_range &r,
+wi_optimize_and_or (irange &r,
enum tree_code code,
tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
@@ -1886,7 +2157,7 @@ wi_set_zero_nonzero_bits (tree type,
}
void
-operator_bitwise_and::wi_fold (value_range &r, tree type,
+operator_bitwise_and::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -1938,29 +2209,128 @@ operator_bitwise_and::wi_fold (value_range &r, tree type,
}
// If the limits got swapped around, return varying.
if (wi::gt_p (new_lb, new_ub,sign))
- r = value_range (type);
+ r.set_varying (type);
else
value_range_with_overflow (r, type, new_lb, new_ub);
}
+static void
+set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
+{
+ if (!lhs.contains_p (build_zero_cst (type)))
+ r = range_nonzero (type);
+ else
+ r.set_varying (type);
+}
+
+// This was shamelessly stolen from register_edge_assert_for_2 and
+// adjusted to work with iranges.
+
+void
+operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ if (!op2.singleton_p ())
+ {
+ set_nonzero_range_from_mask (r, type, lhs);
+ return;
+ }
+ unsigned int nprec = TYPE_PRECISION (type);
+ wide_int cst2v = op2.lower_bound ();
+ bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
+ wide_int sgnbit;
+ if (cst2n)
+ sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
+ else
+ sgnbit = wi::zero (nprec);
+
+ // Solve [lhs.lower_bound (), +INF] = x & MASK.
+ //
+ // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
+ // maximum unsigned value is ~0. For signed comparison, if CST2
+ // doesn't have the most significant bit set, handle it similarly. If
+ // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
+ wide_int valv = lhs.lower_bound ();
+ wide_int minv = valv & cst2v, maxv;
+ bool we_know_nothing = false;
+ if (minv != valv)
+ {
+ // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
+ minv = masked_increment (valv, cst2v, sgnbit, nprec);
+ if (minv == valv)
+ {
+ // If we can't determine anything on this bound, fall
+ // through and conservatively solve for the other end point.
+ we_know_nothing = true;
+ }
+ }
+ maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
+ if (we_know_nothing)
+ r.set_varying (type);
+ else
+ r = int_range<1> (type, minv, maxv);
+
+ // Solve [-INF, lhs.upper_bound ()] = x & MASK.
+ //
+ // Minimum unsigned value for <= is 0 and maximum unsigned value is
+ // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
+ // VAL2 where
+ // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
+ // as maximum.
+ // For signed comparison, if CST2 doesn't have most significant bit
+ // set, handle it similarly. If CST2 has MSB set, the maximum is
+ // the same and minimum is INT_MIN.
+ valv = lhs.upper_bound ();
+ minv = valv & cst2v;
+ if (minv == valv)
+ maxv = valv;
+ else
+ {
+ maxv = masked_increment (valv, cst2v, sgnbit, nprec);
+ if (maxv == valv)
+ {
+ // If we couldn't determine anything on either bound, return
+ // undefined.
+ if (we_know_nothing)
+ r.set_undefined ();
+ return;
+ }
+ maxv -= 1;
+ }
+ maxv |= ~cst2v;
+ minv = sgnbit;
+ int_range<1> upper_bits (type, minv, maxv);
+ r.intersect (upper_bits);
+}
+
bool
-operator_bitwise_and::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_bitwise_and::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
- // If this is really a logical wi_fold, call that.
if (types_compatible_p (type, boolean_type_node))
return op_logical_and.op1_range (r, type, lhs, op2);
- // For now do nothing with bitwise AND of value_range's.
- r.set_varying (type);
+ r.set_undefined ();
+ for (unsigned i = 0; i < lhs.num_pairs (); ++i)
+ {
+ widest_irange chunk (lhs.type (),
+ lhs.lower_bound (i),
+ lhs.upper_bound (i));
+ widest_irange res;
+ simple_op1_range_solver (res, type, chunk, op2);
+ r.union_ (res);
+ }
+ if (r.undefined_p ())
+ set_nonzero_range_from_mask (r, type, lhs);
return true;
}
bool
-operator_bitwise_and::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_bitwise_and::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_bitwise_and::op1_range (r, type, lhs, op1);
}
@@ -1969,23 +2339,23 @@ operator_bitwise_and::op2_range (value_range &r, tree type,
class operator_logical_or : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_logical_or;
bool
-operator_logical_or::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lh,
- const value_range &rh) const
+operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
r = lh;
@@ -1994,9 +2364,9 @@ operator_logical_or::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
}
bool
-operator_logical_or::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+operator_logical_or::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
switch (get_bool_state (r, lhs, type))
{
@@ -2015,9 +2385,9 @@ operator_logical_or::op1_range (value_range &r, tree type,
}
bool
-operator_logical_or::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_logical_or::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_logical_or::op1_range (r, type, lhs, op1);
}
@@ -2026,13 +2396,13 @@ operator_logical_or::op2_range (value_range &r, tree type,
class operator_bitwise_or : public range_operator
{
public:
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2040,7 +2410,7 @@ public:
} op_bitwise_or;
void
-operator_bitwise_or::wi_fold (value_range &r, tree type,
+operator_bitwise_or::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2076,29 +2446,34 @@ operator_bitwise_or::wi_fold (value_range &r, tree type,
new_lb = wi::max (new_lb, rh_lb, sign);
// If the limits got swapped around, return varying.
if (wi::gt_p (new_lb, new_ub,sign))
- r = value_range (type);
+ r.set_varying (type);
else
value_range_with_overflow (r, type, new_lb, new_ub);
}
bool
-operator_bitwise_or::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_bitwise_or::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
// If this is really a logical wi_fold, call that.
if (types_compatible_p (type, boolean_type_node))
return op_logical_or.op1_range (r, type, lhs, op2);
- // For now do nothing with bitwise OR of value_range's.
+ if (lhs.zero_p ())
+ {
+ tree zero = build_zero_cst (type);
+ r = int_range<1> (zero, zero);
+ return true;
+ }
r.set_varying (type);
return true;
}
bool
-operator_bitwise_or::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_bitwise_or::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_bitwise_or::op1_range (r, type, lhs, op1);
}
@@ -2107,15 +2482,21 @@ operator_bitwise_or::op2_range (value_range &r, tree type,
class operator_bitwise_xor : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_bitwise_xor;
void
-operator_bitwise_xor::wi_fold (value_range &r, tree type,
+operator_bitwise_xor::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2142,14 +2523,55 @@ operator_bitwise_xor::wi_fold (value_range &r, tree type,
if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
value_range_with_overflow (r, type, new_lb, new_ub);
else
- r = value_range (type);
+ r.set_varying (type);
+}
+
+bool
+operator_bitwise_xor::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ if (lhs.undefined_p () || lhs.varying_p ())
+ {
+ r = lhs;
+ return true;
+ }
+ if (types_compatible_p (type, boolean_type_node))
+ {
+ switch (get_bool_state (r, lhs, type))
+ {
+ case BRS_TRUE:
+ if (op2.varying_p ())
+ r.set_varying (type);
+ else if (op2.zero_p ())
+ r = range_true (type);
+ else
+ r = range_false (type);
+ break;
+ case BRS_FALSE:
+ r = op2;
+ break;
+ default:
+ gcc_unreachable ();
+ }
+ return true;
+ }
+ r.set_varying (type);
+ return true;
}
+bool
+operator_bitwise_xor::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
+{
+ return operator_bitwise_xor::op1_range (r, type, lhs, op1);
+}
class operator_trunc_mod : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2157,7 +2579,7 @@ public:
} op_trunc_mod;
void
-operator_trunc_mod::wi_fold (value_range &r, tree type,
+operator_trunc_mod::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2170,7 +2592,7 @@ operator_trunc_mod::wi_fold (value_range &r, tree type,
// Mod 0 is undefined. Return undefined.
if (wi_zero_p (type, rh_lb, rh_ub))
{
- r = value_range ();
+ r.set_undefined ();
return;
}
@@ -2204,12 +2626,12 @@ operator_trunc_mod::wi_fold (value_range &r, tree type,
class operator_logical_not : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_logical_not;
// Folding a logical NOT, oddly enough, involves doing nothing on the
@@ -2227,11 +2649,11 @@ public:
// which is the result we are looking for.. so.. pass it through.
bool
-operator_logical_not::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh ATTRIBUTE_UNUSED) const
+operator_logical_not::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh ATTRIBUTE_UNUSED) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
if (lh.varying_p () || lh.undefined_p ())
@@ -2246,10 +2668,10 @@ operator_logical_not::fold_range (value_range &r, tree type,
}
bool
-operator_logical_not::op1_range (value_range &r,
+operator_logical_not::op1_range (irange &r,
tree type ATTRIBUTE_UNUSED,
- const value_range &lhs,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
r = lhs;
if (!lhs.varying_p () && !lhs.undefined_p ())
@@ -2261,33 +2683,33 @@ operator_logical_not::op1_range (value_range &r,
class operator_bitwise_not : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_bitwise_not;
bool
-operator_bitwise_not::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+operator_bitwise_not::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
// ~X is simply -1 - X.
- value_range minusone (type, wi::minus_one (TYPE_PRECISION (type)),
- wi::minus_one (TYPE_PRECISION (type)));
+ int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
+ wi::minus_one (TYPE_PRECISION (type)));
return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, minusone,
lh);
}
bool
-operator_bitwise_not::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_bitwise_not::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
// ~X is -1 - X and since bitwise NOT is involutary...do it again.
return fold_range (r, type, lhs, op2);
@@ -2297,15 +2719,15 @@ operator_bitwise_not::op1_range (value_range &r, tree type,
class operator_cst : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
} op_integer_cst;
bool
-operator_cst::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lh,
- const value_range &rh ATTRIBUTE_UNUSED) const
+operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &lh,
+ const irange &rh ATTRIBUTE_UNUSED) const
{
r = lh;
return true;
@@ -2315,48 +2737,66 @@ operator_cst::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
class operator_identity : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_identity;
bool
-operator_identity::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lh,
- const value_range &rh ATTRIBUTE_UNUSED) const
+operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &lh,
+ const irange &rh ATTRIBUTE_UNUSED) const
{
r = lh;
return true;
}
bool
-operator_identity::op1_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lhs,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
r = lhs;
return true;
}
+class operator_unknown : public range_operator
+{
+public:
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+} op_unknown;
+
+bool
+operator_unknown::fold_range (irange &r, tree type,
+ const irange &lh ATTRIBUTE_UNUSED,
+ const irange &rh ATTRIBUTE_UNUSED) const
+{
+ r.set_varying (type);
+ return true;
+}
+
+
class operator_abs : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_abs;
void
-operator_abs::wi_fold (value_range &r, tree type,
+operator_abs::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb ATTRIBUTE_UNUSED,
const wide_int &rh_ub ATTRIBUTE_UNUSED) const
@@ -2368,7 +2808,7 @@ operator_abs::wi_fold (value_range &r, tree type,
// Pass through LH for the easy cases.
if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
{
- r = value_range (type, lh_lb, lh_ub);
+ r = int_range<1> (type, lh_lb, lh_ub);
return;
}
@@ -2378,7 +2818,7 @@ operator_abs::wi_fold (value_range &r, tree type,
wide_int max_value = wi::max_value (prec, sign);
if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
{
- r = value_range (type);
+ r.set_varying (type);
return;
}
@@ -2416,15 +2856,15 @@ operator_abs::wi_fold (value_range &r, tree type,
min = wi::zero (prec);
max = max_value;
}
- r = value_range (type, min, max);
+ r = int_range<1> (type, min, max);
}
bool
-operator_abs::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_abs::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
- if (empty_range_check (r, lhs, op2))
+ if (empty_range_varying (r, type, lhs, op2))
return true;
if (TYPE_UNSIGNED (type))
{
@@ -2432,15 +2872,15 @@ operator_abs::op1_range (value_range &r, tree type,
return true;
}
// Start with the positives because negatives are an impossible result.
- value_range positives = range_positives (type);
+ widest_irange positives = range_positives (type);
positives.intersect (lhs);
r = positives;
// Then add the negative of each pair:
// ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
for (unsigned i = 0; i < positives.num_pairs (); ++i)
- r.union_ (value_range (type,
- -positives.upper_bound (i),
- -positives.lower_bound (i)));
+ r.union_ (int_range<1> (type,
+ -positives.upper_bound (i),
+ -positives.lower_bound (i)));
return true;
}
@@ -2448,13 +2888,13 @@ operator_abs::op1_range (value_range &r, tree type,
class operator_absu : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_absu;
void
-operator_absu::wi_fold (value_range &r, tree type,
+operator_absu::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb ATTRIBUTE_UNUSED,
const wide_int &rh_ub ATTRIBUTE_UNUSED) const
@@ -2485,27 +2925,27 @@ operator_absu::wi_fold (value_range &r, tree type,
}
gcc_checking_assert (TYPE_UNSIGNED (type));
- r = value_range (type, new_lb, new_ub);
+ r = int_range<1> (type, new_lb, new_ub);
}
class operator_negate : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_negate;
bool
-operator_negate::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+operator_negate::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
// -X is simply 0 - X.
return range_op_handler (MINUS_EXPR, type)->fold_range (r, type,
@@ -2514,9 +2954,9 @@ operator_negate::fold_range (value_range &r, tree type,
}
bool
-operator_negate::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_negate::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
// NEGATE is involutory.
return fold_range (r, type, lhs, op2);
@@ -2526,20 +2966,20 @@ operator_negate::op1_range (value_range &r, tree type,
class operator_addr_expr : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_addr;
bool
-operator_addr_expr::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+operator_addr_expr::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
// Return a non-null pointer of the LHS type (passed in op2).
@@ -2548,14 +2988,14 @@ operator_addr_expr::fold_range (value_range &r, tree type,
else if (!lh.contains_p (build_zero_cst (lh.type ())))
r = range_nonzero (type);
else
- r = value_range (type);
+ r.set_varying (type);
return true;
}
bool
-operator_addr_expr::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_addr_expr::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
return operator_addr_expr::fold_range (r, type, lhs, op2);
}
@@ -2564,7 +3004,7 @@ operator_addr_expr::op1_range (value_range &r, tree type,
class pointer_plus_operator : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2572,7 +3012,7 @@ public:
} op_pointer_plus;
void
-pointer_plus_operator::wi_fold (value_range &r, tree type,
+pointer_plus_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2604,20 +3044,20 @@ pointer_plus_operator::wi_fold (value_range &r, tree type,
&& rh_lb == rh_ub && rh_lb == 0)
r = range_zero (type);
else
- r = value_range (type);
+ r.set_varying (type);
}
class pointer_min_max_operator : public range_operator
{
public:
- virtual void wi_fold (value_range & r, tree type,
+ virtual void wi_fold (irange & r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_ptr_min_max;
void
-pointer_min_max_operator::wi_fold (value_range &r, tree type,
+pointer_min_max_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2633,20 +3073,20 @@ pointer_min_max_operator::wi_fold (value_range &r, tree type,
else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
r = range_zero (type);
else
- r = value_range (type);
+ r.set_varying (type);
}
class pointer_and_operator : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_pointer_and;
void
-pointer_and_operator::wi_fold (value_range &r, tree type,
+pointer_and_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb ATTRIBUTE_UNUSED,
@@ -2657,20 +3097,49 @@ pointer_and_operator::wi_fold (value_range &r, tree type,
if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub))
r = range_zero (type);
else
- r = value_range (type);
+ r.set_varying (type);
}
class pointer_or_operator : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_pointer_or;
+bool
+pointer_or_operator::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
+{
+ if (lhs.zero_p ())
+ {
+ tree zero = build_zero_cst (type);
+ r = int_range<1> (zero, zero);
+ return true;
+ }
+ r.set_varying (type);
+ return true;
+}
+
+bool
+pointer_or_operator::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
+{
+ return pointer_or_operator::op1_range (r, type, lhs, op1);
+}
+
void
-pointer_or_operator::wi_fold (value_range &r, tree type,
+pointer_or_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -2684,7 +3153,7 @@ pointer_or_operator::wi_fold (value_range &r, tree type,
else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
r = range_zero (type);
else
- r = value_range (type);
+ r.set_varying (type);
}
// This implements the range operator tables as local objects in this file.
@@ -2760,6 +3229,8 @@ integral_table::integral_table ()
set (SSA_NAME, op_identity);
set (PAREN_EXPR, op_identity);
set (OBJ_TYPE_REF, op_identity);
+ set (IMAGPART_EXPR, op_unknown);
+ set (POINTER_DIFF_EXPR, op_unknown);
set (ABS_EXPR, op_abs);
set (ABSU_EXPR, op_absu);
set (NEGATE_EXPR, op_negate);
@@ -2811,13 +3282,13 @@ range_op_handler (enum tree_code code, tree type)
// Cast the range in R to TYPE.
void
-range_cast (value_range &r, tree type)
+range_cast (irange &r, tree type)
{
- value_range tmp = r;
+ widest_irange tmp = r;
range_operator *op = range_op_handler (CONVERT_EXPR, type);
// Call op_convert, if it fails, the result is varying.
- if (!op->fold_range (r, type, tmp, value_range (type)))
- r = value_range (type);
+ if (!op->fold_range (r, type, tmp, int_range<1> (type)))
+ r.set_varying (type);
}
#if CHECKING_P
@@ -2836,37 +3307,280 @@ namespace selftest
#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
#define SCHAR(N) build_int_cst (signed_char_type_node, (N))
+static int_range<3>
+build_range3 (int a, int b, int c, int d, int e, int f)
+{
+ int_range<3> i1 (INT (a), INT (b));
+ int_range<3> i2 (INT (c), INT (d));
+ int_range<3> i3 (INT (e), INT (f));
+ i1.union_ (i2);
+ i1.union_ (i3);
+ return i1;
+}
+
+static void
+range3_tests ()
+{
+ typedef int_range<3> irange3;
+ irange3 r0, r1, r2;
+ irange3 i1, i2, i3;
+
+ // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
+ r0 = irange3 (INT (10), INT (20));
+ r1 = irange3 (INT (5), INT (8));
+ r0.union_ (r1);
+ r1 = irange3 (INT (1), INT (3));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
+
+ // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
+ r1 = irange3 (INT (-5), INT (0));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
+
+ // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
+ r1 = irange3 (INT (50), INT (60));
+ r0 = irange3 (INT (10), INT (20));
+ r0.union_ (irange3 (INT (30), INT (40)));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
+ // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
+ r1 = irange3 (INT (70), INT (80));
+ r0.union_ (r1);
+
+ r2 = build_range3 (10, 20, 30, 40, 50, 60);
+ r2.union_ (irange3 (INT (70), INT (80)));
+ ASSERT_TRUE (r0 == r2);
+
+ // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (6), INT (35));
+ r0.union_ (r1);
+ r1 = irange3 (INT (6), INT (40));
+ r1.union_ (irange3 (INT (50), INT (60)));
+ ASSERT_TRUE (r0 == r1);
+
+ // [10,20][30,40][50,60] U [6,60] => [6,60].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (6), INT (60));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange3 (INT (6), INT (60)));
+
+ // [10,20][30,40][50,60] U [6,70] => [6,70].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (6), INT (70));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange3 (INT (6), INT (70)));
+
+ // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (35), INT (70));
+ r0.union_ (r1);
+ r1 = irange3 (INT (10), INT (20));
+ r1.union_ (irange3 (INT (30), INT (70)));
+ ASSERT_TRUE (r0 == r1);
+
+ // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (15), INT (35));
+ r0.union_ (r1);
+ r1 = irange3 (INT (10), INT (40));
+ r1.union_ (irange3 (INT (50), INT (60)));
+ ASSERT_TRUE (r0 == r1);
+
+ // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (35), INT (35));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
+}
+
+static void
+widest_irange_tests ()
+{
+ widest_irange big;
+ unsigned int nrange;
+
+ // Build a huge multi-range range.
+ for (nrange = 0; nrange < 50; ++nrange)
+ {
+ int_range<1> tmp (INT (nrange*10), INT (nrange*10 + 5));
+ big.union_ (tmp);
+ }
+ ASSERT_TRUE (big.num_pairs () == nrange);
+
+ // Verify that we can copy it without loosing precision.
+ widest_irange copy (big);
+ ASSERT_TRUE (copy.num_pairs () == nrange);
+
+ // Inverting it should produce one more sub-range.
+ big.invert ();
+ ASSERT_TRUE (big.num_pairs () == nrange + 1);
+
+ int_range<1> tmp (INT (5), INT (37));
+ big.intersect (tmp);
+ ASSERT_TRUE (big.num_pairs () == 4);
+
+ // Test that [10,10][20,20] does NOT contain 15.
+ {
+ widest_irange i1 (build_int_cst (integer_type_node, 10),
+ build_int_cst (integer_type_node, 10));
+ widest_irange i2 (build_int_cst (integer_type_node, 20),
+ build_int_cst (integer_type_node, 20));
+ i1.union_ (i2);
+ ASSERT_FALSE (i1.contains_p (build_int_cst (integer_type_node, 15)));
+ }
+
+}
+
+static void
+multi_precision_range_tests ()
+{
+ // Test truncating copy to int_range<1>.
+ int_range<3> big = build_range3 (10, 20, 30, 40, 50, 60);
+ int_range<1> small = big;
+ ASSERT_TRUE (small == int_range<1> (INT (10), INT (60)));
+
+ // Test truncating copy to int_range<2>.
+ int_range<2> medium = big;
+ ASSERT_TRUE (!medium.undefined_p ());
+
+ // Test that a truncating copy of [MIN,20][22,40][80,MAX]
+ // ends up as a conservative anti-range of ~[21,21].
+ big = int_range<3> (vrp_val_min (integer_type_node), INT (20));
+ big.union_ (int_range<1> (INT (22), INT (40)));
+ big.union_ (int_range<1> (INT (80), vrp_val_max (integer_type_node)));
+ small = big;
+ ASSERT_TRUE (small == int_range<1> (INT (21), INT (21), VR_ANTI_RANGE));
+
+ range3_tests ();
+}
+
+static void
+operator_tests ()
+{
+ tree min = vrp_val_min (integer_type_node);
+ tree max = vrp_val_max (integer_type_node);
+ tree tiny = fold_build2 (PLUS_EXPR, integer_type_node, min,
+ build_one_cst (integer_type_node));
+ widest_irange res;
+ widest_irange i1 (tiny, max);
+ widest_irange i2 (build_int_cst (integer_type_node, 255),
+ build_int_cst (integer_type_node, 255));
+
+ // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
+ op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
+ ASSERT_TRUE (res == int_range<1> (integer_type_node));
+
+ // VARYING = OP1 & 255: OP1 is VARYING
+ i1 = int_range<1> (integer_type_node);
+ op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
+ ASSERT_TRUE (res == int_range<1> (integer_type_node));
+
+ // Test that 0x808.... & 0x8.... still contains 0x8....
+ // for a large set of numbers.
+ {
+ tree big_type = long_long_unsigned_type_node;
+ // big_num = 0x808,0000,0000,0000
+ tree big_num = fold_build2 (LSHIFT_EXPR, big_type,
+ build_int_cst (big_type, 0x808),
+ build_int_cst (big_type, 48));
+ op_bitwise_and.fold_range (res, big_type,
+ int_range <1> (big_type),
+ int_range <1> (big_num, big_num));
+ // val = 0x8,0000,0000,0000
+ tree val = fold_build2 (LSHIFT_EXPR, big_type,
+ build_int_cst (big_type, 0x8),
+ build_int_cst (big_type, 48));
+ ASSERT_TRUE (res.contains_p (val));
+ }
+
+ // unsigned: [3, MAX] = OP1 >> 1
+ {
+ widest_irange lhs (build_int_cst (unsigned_type_node, 3),
+ TYPE_MAX_VALUE (unsigned_type_node));
+ widest_irange one (build_one_cst (unsigned_type_node),
+ build_one_cst (unsigned_type_node));
+ widest_irange op1;
+ op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
+ ASSERT_FALSE (op1.contains_p (UINT (3)));
+ }
+
+ // signed: [3, MAX] = OP1 >> 1
+ {
+ widest_irange lhs (INT (3), TYPE_MAX_VALUE (integer_type_node));
+ widest_irange one (INT (1), INT (1));
+ widest_irange op1;
+ op_rshift.op1_range (op1, integer_type_node, lhs, one);
+ ASSERT_FALSE (op1.contains_p (INT (-2)));
+ }
+
+ // This is impossible, so OP1 should be [].
+ // signed: [MIN, MIN] = OP1 >> 1
+ {
+ widest_irange lhs (TYPE_MIN_VALUE (integer_type_node),
+ TYPE_MIN_VALUE (integer_type_node));
+ widest_irange one (INT (1), INT (1));
+ widest_irange op1;
+ op_rshift.op1_range (op1, integer_type_node, lhs, one);
+ ASSERT_TRUE (op1.undefined_p ());
+ }
+
+ // signed: ~[-1] = OP1 >> 31
+ {
+ widest_irange lhs (INT (-1), INT (-1), VR_ANTI_RANGE);
+ widest_irange shift (INT (31), INT (31));
+ widest_irange op1;
+ op_rshift.op1_range (op1, integer_type_node, lhs, shift);
+ widest_irange negatives = range_negatives (integer_type_node);
+ negatives.intersect (op1);
+ ASSERT_TRUE (negatives.undefined_p ());
+ }
+}
+
// Run all of the selftests within this file.
void
range_tests ()
{
tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
- value_range i1, i2, i3;
- value_range r0, r1, rold;
+ int_range<1> i1, i2, i3;
+ int_range<1> r0, r1, rold;
+
+ // Test 1-bit signed integer union.
+ // [-1,-1] U [0,0] = VARYING.
+ tree one_bit_type = build_nonstandard_integer_type (1, 0);
+ {
+ tree one_bit_min = vrp_val_min (one_bit_type);
+ tree one_bit_max = vrp_val_max (one_bit_type);
+ int_range<2> min (one_bit_min, one_bit_min);
+ int_range<2> max (one_bit_max, one_bit_max);
+ max.union_ (min);
+ ASSERT_TRUE (max.varying_p ());
+ }
// Test that NOT(255) is [0..254] in 8-bit land.
- value_range not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE);
- ASSERT_TRUE (not_255 == value_range (UCHAR (0), UCHAR (254)));
+ int_range<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE);
+ ASSERT_TRUE (not_255 == int_range<1> (UCHAR (0), UCHAR (254)));
// Test that NOT(0) is [1..255] in 8-bit land.
- value_range not_zero = range_nonzero (unsigned_char_type_node);
- ASSERT_TRUE (not_zero == value_range (UCHAR (1), UCHAR (255)));
+ int_range<1> not_zero = range_nonzero (unsigned_char_type_node);
+ ASSERT_TRUE (not_zero == int_range<1> (UCHAR (1), UCHAR (255)));
// Check that [0,127][0x..ffffff80,0x..ffffff]
// => ~[128, 0x..ffffff7f].
- r0 = value_range (UINT128 (0), UINT128 (127));
+ r0 = int_range<1> (UINT128 (0), UINT128 (127));
tree high = build_minus_one_cst (u128_type);
// low = -1 - 127 => 0x..ffffff80.
tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127));
- r1 = value_range (low, high); // [0x..ffffff80, 0x..ffffffff]
+ r1 = int_range<1> (low, high); // [0x..ffffff80, 0x..ffffffff]
// r0 = [0,127][0x..ffffff80,0x..fffffff].
r0.union_ (r1);
// r1 = [128, 0x..ffffff7f].
- r1 = value_range (UINT128(128),
- fold_build2 (MINUS_EXPR, u128_type,
- build_minus_one_cst (u128_type),
- UINT128(128)));
+ r1 = int_range<1> (UINT128(128),
+ fold_build2 (MINUS_EXPR, u128_type,
+ build_minus_one_cst (u128_type),
+ UINT128(128)));
r0.invert ();
ASSERT_TRUE (r0 == r1);
@@ -2882,38 +3596,38 @@ range_tests ()
tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ());
// Check that ~[0,5] => [6,MAX] for unsigned int.
- r0 = value_range (UINT (0), UINT (5));
+ r0 = int_range<1> (UINT (0), UINT (5));
r0.invert ();
- ASSERT_TRUE (r0 == value_range (UINT(6), maxuint));
+ ASSERT_TRUE (r0 == int_range<1> (UINT(6), maxuint));
// Check that ~[10,MAX] => [0,9] for unsigned int.
- r0 = value_range (UINT(10), maxuint);
+ r0 = int_range<1> (UINT(10), maxuint);
r0.invert ();
- ASSERT_TRUE (r0 == value_range (UINT (0), UINT (9)));
+ ASSERT_TRUE (r0 == int_range<1> (UINT (0), UINT (9)));
// Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
- r0 = value_range (UINT128 (0), UINT128 (5), VR_ANTI_RANGE);
- r1 = value_range (UINT128(6), build_minus_one_cst (u128_type));
+ r0 = int_range<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE);
+ r1 = int_range<1> (UINT128(6), build_minus_one_cst (u128_type));
ASSERT_TRUE (r0 == r1);
// Check that [~5] is really [-MIN,4][6,MAX].
- r0 = value_range (INT (5), INT (5), VR_ANTI_RANGE);
- r1 = value_range (minint, INT (4));
- r1.union_ (value_range (INT (6), maxint));
+ r0 = int_range<1> (INT (5), INT (5), VR_ANTI_RANGE);
+ r1 = int_range<1> (minint, INT (4));
+ r1.union_ (int_range<1> (INT (6), maxint));
ASSERT_FALSE (r1.undefined_p ());
ASSERT_TRUE (r0 == r1);
- r1 = value_range (INT (5), INT (5));
- value_range r2 (r1);
+ r1 = int_range<1> (INT (5), INT (5));
+ int_range<1> r2 (r1);
ASSERT_TRUE (r1 == r2);
- r1 = value_range (INT (5), INT (10));
+ r1 = int_range<1> (INT (5), INT (10));
- r1 = value_range (integer_type_node,
- wi::to_wide (INT (5)), wi::to_wide (INT (10)));
+ r1 = int_range<1> (integer_type_node,
+ wi::to_wide (INT (5)), wi::to_wide (INT (10)));
ASSERT_TRUE (r1.contains_p (INT (7)));
- r1 = value_range (SCHAR (0), SCHAR (20));
+ r1 = int_range<1> (SCHAR (0), SCHAR (20));
ASSERT_TRUE (r1.contains_p (SCHAR(15)));
ASSERT_FALSE (r1.contains_p (SCHAR(300)));
@@ -2922,96 +3636,96 @@ range_tests ()
if (TYPE_PRECISION (TREE_TYPE (maxint))
> TYPE_PRECISION (short_integer_type_node))
{
- r1 = value_range (integer_zero_node, maxint);
+ r1 = int_range<1> (integer_zero_node, maxint);
range_cast (r1, short_integer_type_node);
ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort)
&& r1.upper_bound() == wi::to_wide (maxshort));
}
// (unsigned char)[-5,-1] => [251,255].
- r0 = rold = value_range (SCHAR (-5), SCHAR (-1));
+ r0 = rold = int_range<1> (SCHAR (-5), SCHAR (-1));
range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == value_range (UCHAR (251), UCHAR (255)));
+ ASSERT_TRUE (r0 == int_range<1> (UCHAR (251), UCHAR (255)));
range_cast (r0, signed_char_type_node);
ASSERT_TRUE (r0 == rold);
// (signed char)[15, 150] => [-128,-106][15,127].
- r0 = rold = value_range (UCHAR (15), UCHAR (150));
+ r0 = rold = int_range<1> (UCHAR (15), UCHAR (150));
range_cast (r0, signed_char_type_node);
- r1 = value_range (SCHAR (15), SCHAR (127));
- r2 = value_range (SCHAR (-128), SCHAR (-106));
+ r1 = int_range<1> (SCHAR (15), SCHAR (127));
+ r2 = int_range<1> (SCHAR (-128), SCHAR (-106));
r1.union_ (r2);
ASSERT_TRUE (r1 == r0);
range_cast (r0, unsigned_char_type_node);
ASSERT_TRUE (r0 == rold);
// (unsigned char)[-5, 5] => [0,5][251,255].
- r0 = rold = value_range (SCHAR (-5), SCHAR (5));
+ r0 = rold = int_range<1> (SCHAR (-5), SCHAR (5));
range_cast (r0, unsigned_char_type_node);
- r1 = value_range (UCHAR (251), UCHAR (255));
- r2 = value_range (UCHAR (0), UCHAR (5));
+ r1 = int_range<1> (UCHAR (251), UCHAR (255));
+ r2 = int_range<1> (UCHAR (0), UCHAR (5));
r1.union_ (r2);
ASSERT_TRUE (r0 == r1);
range_cast (r0, signed_char_type_node);
ASSERT_TRUE (r0 == rold);
// (unsigned char)[-5,5] => [0,5][251,255].
- r0 = value_range (INT (-5), INT (5));
+ r0 = int_range<1> (INT (-5), INT (5));
range_cast (r0, unsigned_char_type_node);
- r1 = value_range (UCHAR (0), UCHAR (5));
- r1.union_ (value_range (UCHAR (251), UCHAR (255)));
+ r1 = int_range<1> (UCHAR (0), UCHAR (5));
+ r1.union_ (int_range<1> (UCHAR (251), UCHAR (255)));
ASSERT_TRUE (r0 == r1);
// (unsigned char)[5U,1974U] => [0,255].
- r0 = value_range (UINT (5), UINT (1974));
+ r0 = int_range<1> (UINT (5), UINT (1974));
range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == value_range (UCHAR (0), UCHAR (255)));
+ ASSERT_TRUE (r0 == int_range<1> (UCHAR (0), UCHAR (255)));
range_cast (r0, integer_type_node);
// Going to a wider range should not sign extend.
- ASSERT_TRUE (r0 == value_range (INT (0), INT (255)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (0), INT (255)));
// (unsigned char)[-350,15] => [0,255].
- r0 = value_range (INT (-350), INT (15));
+ r0 = int_range<1> (INT (-350), INT (15));
range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == (value_range
+ ASSERT_TRUE (r0 == (int_range<1>
(TYPE_MIN_VALUE (unsigned_char_type_node),
TYPE_MAX_VALUE (unsigned_char_type_node))));
// Casting [-120,20] from signed char to unsigned short.
// => [0, 20][0xff88, 0xffff].
- r0 = value_range (SCHAR (-120), SCHAR (20));
+ r0 = int_range<1> (SCHAR (-120), SCHAR (20));
range_cast (r0, short_unsigned_type_node);
- r1 = value_range (UINT16 (0), UINT16 (20));
- r2 = value_range (UINT16 (0xff88), UINT16 (0xffff));
+ r1 = int_range<1> (UINT16 (0), UINT16 (20));
+ r2 = int_range<1> (UINT16 (0xff88), UINT16 (0xffff));
r1.union_ (r2);
ASSERT_TRUE (r0 == r1);
// A truncating cast back to signed char will work because [-120, 20]
// is representable in signed char.
range_cast (r0, signed_char_type_node);
- ASSERT_TRUE (r0 == value_range (SCHAR (-120), SCHAR (20)));
+ ASSERT_TRUE (r0 == int_range<1> (SCHAR (-120), SCHAR (20)));
// unsigned char -> signed short
// (signed short)[(unsigned char)25, (unsigned char)250]
// => [(signed short)25, (signed short)250]
- r0 = rold = value_range (UCHAR (25), UCHAR (250));
+ r0 = rold = int_range<1> (UCHAR (25), UCHAR (250));
range_cast (r0, short_integer_type_node);
- r1 = value_range (INT16 (25), INT16 (250));
+ r1 = int_range<1> (INT16 (25), INT16 (250));
ASSERT_TRUE (r0 == r1);
range_cast (r0, unsigned_char_type_node);
ASSERT_TRUE (r0 == rold);
// Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
- r0 = value_range (TYPE_MIN_VALUE (long_long_integer_type_node),
+ r0 = int_range<1> (TYPE_MIN_VALUE (long_long_integer_type_node),
TYPE_MAX_VALUE (long_long_integer_type_node));
range_cast (r0, short_unsigned_type_node);
- r1 = value_range (TYPE_MIN_VALUE (short_unsigned_type_node),
+ r1 = int_range<1> (TYPE_MIN_VALUE (short_unsigned_type_node),
TYPE_MAX_VALUE (short_unsigned_type_node));
ASSERT_TRUE (r0 == r1);
// NOT([10,20]) ==> [-MIN,9][21,MAX].
- r0 = r1 = value_range (INT (10), INT (20));
- r2 = value_range (minint, INT(9));
- r2.union_ (value_range (INT(21), maxint));
+ r0 = r1 = int_range<1> (INT (10), INT (20));
+ r2 = int_range<1> (minint, INT(9));
+ r2.union_ (int_range<1> (INT(21), maxint));
ASSERT_FALSE (r2.undefined_p ());
r1.invert ();
ASSERT_TRUE (r1 == r2);
@@ -3021,11 +3735,11 @@ range_tests ()
// Test that booleans and their inverse work as expected.
r0 = range_zero (boolean_type_node);
- ASSERT_TRUE (r0 == value_range (build_zero_cst (boolean_type_node),
- build_zero_cst (boolean_type_node)));
+ ASSERT_TRUE (r0 == int_range<1> (build_zero_cst (boolean_type_node),
+ build_zero_cst (boolean_type_node)));
r0.invert ();
- ASSERT_TRUE (r0 == value_range (build_one_cst (boolean_type_node),
- build_one_cst (boolean_type_node)));
+ ASSERT_TRUE (r0 == int_range<1> (build_one_cst (boolean_type_node),
+ build_one_cst (boolean_type_node)));
// Casting NONZERO to a narrower type will wrap/overflow so
// it's just the entire range for the narrower type.
@@ -3038,8 +3752,8 @@ range_tests ()
{
r0 = range_nonzero (integer_type_node);
range_cast (r0, short_integer_type_node);
- r1 = value_range (TYPE_MIN_VALUE (short_integer_type_node),
- TYPE_MAX_VALUE (short_integer_type_node));
+ r1 = int_range<1> (TYPE_MIN_VALUE (short_integer_type_node),
+ TYPE_MAX_VALUE (short_integer_type_node));
ASSERT_TRUE (r0 == r1);
}
@@ -3049,8 +3763,8 @@ range_tests ()
// Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
r0 = range_nonzero (short_integer_type_node);
range_cast (r0, integer_type_node);
- r1 = value_range (INT (-32768), INT (-1));
- r2 = value_range (INT (1), INT (32767));
+ r1 = int_range<1> (INT (-32768), INT (-1));
+ r2 = int_range<1> (INT (1), INT (32767));
r1.union_ (r2);
ASSERT_TRUE (r0 == r1);
@@ -3064,34 +3778,34 @@ range_tests ()
ASSERT_TRUE (r0 == r1);
// [10,20] U [15, 30] => [10, 30].
- r0 = value_range (INT (10), INT (20));
- r1 = value_range (INT (15), INT (30));
+ r0 = int_range<1> (INT (10), INT (20));
+ r1 = int_range<1> (INT (15), INT (30));
r0.union_ (r1);
- ASSERT_TRUE (r0 == value_range (INT (10), INT (30)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (30)));
// [15,40] U [] => [15,40].
- r0 = value_range (INT (15), INT (40));
+ r0 = int_range<1> (INT (15), INT (40));
r1.set_undefined ();
r0.union_ (r1);
- ASSERT_TRUE (r0 == value_range (INT (15), INT (40)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (40)));
// [10,20] U [10,10] => [10,20].
- r0 = value_range (INT (10), INT (20));
- r1 = value_range (INT (10), INT (10));
+ r0 = int_range<1> (INT (10), INT (20));
+ r1 = int_range<1> (INT (10), INT (10));
r0.union_ (r1);
- ASSERT_TRUE (r0 == value_range (INT (10), INT (20)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (20)));
// [10,20] U [9,9] => [9,20].
- r0 = value_range (INT (10), INT (20));
- r1 = value_range (INT (9), INT (9));
+ r0 = int_range<1> (INT (10), INT (20));
+ r1 = int_range<1> (INT (9), INT (9));
r0.union_ (r1);
- ASSERT_TRUE (r0 == value_range (INT (9), INT (20)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (9), INT (20)));
// [10,20] ^ [15,30] => [15,20].
- r0 = value_range (INT (10), INT (20));
- r1 = value_range (INT (15), INT (30));
+ r0 = int_range<1> (INT (10), INT (20));
+ r1 = int_range<1> (INT (15), INT (30));
r0.intersect (r1);
- ASSERT_TRUE (r0 == value_range (INT (15), INT (20)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (20)));
// Test the internal sanity of wide_int's wrt HWIs.
ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
@@ -3099,13 +3813,17 @@ range_tests ()
== wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
// Test zero_p().
- r0 = value_range (INT (0), INT (0));
+ r0 = int_range<1> (INT (0), INT (0));
ASSERT_TRUE (r0.zero_p ());
// Test nonzero_p().
- r0 = value_range (INT (0), INT (0));
+ r0 = int_range<1> (INT (0), INT (0));
r0.invert ();
ASSERT_TRUE (r0.nonzero_p ());
+
+ multi_precision_range_tests ();
+ widest_irange_tests ();
+ operator_tests ();
}
} // namespace selftest
diff --git a/gcc/range-op.h b/gcc/range-op.h
index 1311965f4f5..08f6bf9f73f 100644
--- a/gcc/range-op.h
+++ b/gcc/range-op.h
@@ -50,9 +50,9 @@ class range_operator
{
public:
// Perform an operation between 2 ranges and return it.
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
// Return the range for op[12] in the general case. LHS is the range for
// the LHS of the expression, OP[12]is the range for the other
@@ -65,16 +65,16 @@ public:
//
// i.e. [LHS] = ??? + OP2
// is re-formed as R = [LHS] - OP2.
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
protected:
// Perform an integral operation between 2 sub-ranges and return it.
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
@@ -82,7 +82,7 @@ protected:
};
extern range_operator *range_op_handler (enum tree_code code, tree type);
-extern void range_cast (value_range &, tree type);
+extern void range_cast (irange &, tree type);
extern void wi_set_zero_nonzero_bits (tree type,
const wide_int &, const wide_int &,
wide_int &maybe_nonzero,
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 7193ca4ad5e..de84c1d505d 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1151,25 +1151,29 @@ static bool
range_fold_binary_symbolics_p (value_range *vr,
tree_code code,
tree expr_type,
- const value_range *vr0, const value_range *vr1)
+ const value_range *vr0_,
+ const value_range *vr1_)
{
- if (vr0->symbolic_p () || vr1->symbolic_p ())
+ if (vr0_->symbolic_p () || vr1_->symbolic_p ())
{
+ value_range vr0 = drop_undefines_to_varying (vr0_, expr_type);
+ value_range vr1 = drop_undefines_to_varying (vr1_, expr_type);
if ((code == PLUS_EXPR || code == MINUS_EXPR))
{
- extract_range_from_plus_minus_expr (vr, code, expr_type, vr0, vr1);
+ extract_range_from_plus_minus_expr (vr, code, expr_type,
+ &vr0, &vr1);
return true;
}
if (POINTER_TYPE_P (expr_type) && code == POINTER_PLUS_EXPR)
{
- extract_range_from_pointer_plus_expr (vr, code, expr_type, vr0, vr1);
+ extract_range_from_pointer_plus_expr (vr, code, expr_type,
+ &vr0, &vr1);
return true;
}
const range_operator *op = get_range_op_handler (vr, code, expr_type);
- value_range vr0_cst (*vr0), vr1_cst (*vr1);
- vr0_cst.normalize_symbolics ();
- vr1_cst.normalize_symbolics ();
- return op->fold_range (*vr, expr_type, vr0_cst, vr1_cst);
+ vr0.normalize_symbolics ();
+ vr1.normalize_symbolics ();
+ return op->fold_range (*vr, expr_type, vr0, vr1);
}
return false;
}
@@ -1225,11 +1229,15 @@ range_fold_binary_expr (value_range *vr,
if (!op)
return;
- value_range vr0 = drop_undefines_to_varying (vr0_, expr_type);
- value_range vr1 = drop_undefines_to_varying (vr1_, expr_type);
- if (range_fold_binary_symbolics_p (vr, code, expr_type, &vr0, &vr1))
+ if (range_fold_binary_symbolics_p (vr, code, expr_type, vr0_, vr1_))
return;
+ value_range vr0 (*vr0_);
+ value_range vr1 (*vr1_);
+ if (vr0.undefined_p ())
+ vr0.set_varying (expr_type);
+ if (vr1.undefined_p ())
+ vr1.set_varying (expr_type);
vr0.normalize_addresses ();
vr1.normalize_addresses ();
op->fold_range (*vr, expr_type, vr0, vr1);
@@ -1637,7 +1645,7 @@ extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
(to transform signed values into unsigned) and at the end xor
SGNBIT back. */
-static wide_int
+wide_int
masked_increment (const wide_int &val_in, const wide_int &mask,
const wide_int &sgnbit, unsigned int prec)
{
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index b3d187ffdf1..371e58aa0ea 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -62,5 +62,7 @@ extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *);
extern tree get_single_symbol (tree, bool *, tree *);
extern void maybe_set_nonzero_bits (edge, tree);
extern value_range_kind determine_value_range (tree, wide_int *, wide_int *);
+extern wide_int masked_increment (const wide_int &val_in, const wide_int &mask,
+ const wide_int &sgnbit, unsigned int prec);
#endif /* GCC_TREE_VRP_H */
diff --git a/gcc/tree.c b/gcc/tree.c
index 6522a089ddf..01a342c5b92 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -1483,6 +1483,31 @@ int_cst_hasher::equal (tree x, tree y)
return true;
}
+/* Cache wide_int CST into the TYPE_CACHED_VALUES cache for TYPE.
+ SLOT is the slot entry to store it in, and MAX_SLOTS is the maximum
+ number of slots that can be cached for the type. */
+
+static inline tree
+cache_wide_int_in_type_cache (tree type, const wide_int &cst,
+ int slot, int max_slots)
+{
+ gcc_checking_assert (slot >= 0);
+ /* Initialize cache. */
+ if (!TYPE_CACHED_VALUES_P (type))
+ {
+ TYPE_CACHED_VALUES_P (type) = 1;
+ TYPE_CACHED_VALUES (type) = make_tree_vec (max_slots);
+ }
+ tree t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), slot);
+ if (!t)
+ {
+ /* Create a new shared int. */
+ t = build_new_int_cst (type, cst);
+ TREE_VEC_ELT (TYPE_CACHED_VALUES (type), slot) = t;
+ }
+ return t;
+}
+
/* Create an INT_CST node of TYPE and value CST.
The returned node is always shared. For small integers we use a
per-type vector cache, for larger ones we use a single hash table.
@@ -1515,6 +1540,28 @@ wide_int_to_tree_1 (tree type, const wide_int_ref &pcst)
wide_int cst = wide_int::from (pcst, prec, sgn);
unsigned int ext_len = get_int_cst_ext_nunits (type, cst);
+ enum tree_code code = TREE_CODE (type);
+ if (code == POINTER_TYPE || code == REFERENCE_TYPE)
+ {
+ /* Cache NULL pointer and zero bounds. */
+ if (cst == 0)
+ ix = 0;
+ /* Cache upper bounds of pointers. */
+ else if (cst == wi::max_value (prec, sgn))
+ ix = 1;
+ /* Cache 1 which is used for a non-zero range. */
+ else if (cst == 1)
+ ix = 2;
+
+ if (ix >= 0)
+ {
+ t = cache_wide_int_in_type_cache (type, cst, ix, 3);
+ /* Make sure no one is clobbering the shared constant. */
+ gcc_checking_assert (TREE_TYPE (t) == type
+ && cst == wi::to_wide (t));
+ return t;
+ }
+ }
if (ext_len == 1)
{
/* We just need to store a single HOST_WIDE_INT. */
@@ -1524,7 +1571,7 @@ wide_int_to_tree_1 (tree type, const wide_int_ref &pcst)
else
hwi = cst.to_shwi ();
- switch (TREE_CODE (type))
+ switch (code)
{
case NULLPTR_TYPE:
gcc_assert (hwi == 0);
@@ -1532,12 +1579,7 @@ wide_int_to_tree_1 (tree type, const wide_int_ref &pcst)
case POINTER_TYPE:
case REFERENCE_TYPE:
- /* Cache NULL pointer and zero bounds. */
- if (hwi == 0)
- {
- limit = 1;
- ix = 0;
- }
+ /* Ignore pointers, as they were already handled above. */
break;
case BOOLEAN_TYPE:
@@ -1574,27 +1616,14 @@ wide_int_to_tree_1 (tree type, const wide_int_ref &pcst)
if (ix >= 0)
{
- /* Look for it in the type's vector of small shared ints. */
- if (!TYPE_CACHED_VALUES_P (type))
- {
- TYPE_CACHED_VALUES_P (type) = 1;
- TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
- }
-
- t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
- if (t)
- /* Make sure no one is clobbering the shared constant. */
- gcc_checking_assert (TREE_TYPE (t) == type
- && TREE_INT_CST_NUNITS (t) == 1
- && TREE_INT_CST_OFFSET_NUNITS (t) == 1
- && TREE_INT_CST_EXT_NUNITS (t) == 1
- && TREE_INT_CST_ELT (t, 0) == hwi);
- else
- {
- /* Create a new shared int. */
- t = build_new_int_cst (type, cst);
- TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
- }
+ t = cache_wide_int_in_type_cache (type, cst, ix, limit);
+ /* Make sure no one is clobbering the shared constant. */
+ gcc_checking_assert (TREE_TYPE (t) == type
+ && TREE_INT_CST_NUNITS (t) == 1
+ && TREE_INT_CST_OFFSET_NUNITS (t) == 1
+ && TREE_INT_CST_EXT_NUNITS (t) == 1
+ && TREE_INT_CST_ELT (t, 0) == hwi);
+ return t;
}
else
{
diff --git a/gcc/value-range-equiv.cc b/gcc/value-range-equiv.cc
index 24132e3546e..7dc10b876e0 100644
--- a/gcc/value-range-equiv.cc
+++ b/gcc/value-range-equiv.cc
@@ -90,13 +90,13 @@ value_range_equiv::update (tree min, tree max, value_range_kind kind)
void
value_range_equiv::deep_copy (const value_range_equiv *from)
{
- set (from->min (), from->max (), from->m_equiv, from->m_kind);
+ set (from->min (), from->max (), from->m_equiv, from->kind ());
}
void
value_range_equiv::move (value_range_equiv *from)
{
- set (from->min (), from->max (), NULL, from->m_kind);
+ set (from->min (), from->max (), NULL, from->kind ());
m_equiv = from->m_equiv;
from->m_equiv = NULL;
}
@@ -127,8 +127,8 @@ value_range_equiv::set_equiv (bitmap equiv)
void
value_range_equiv::check ()
{
- value_range::check ();
- switch (m_kind)
+ value_range::verify_range ();
+ switch (kind ())
{
case VR_UNDEFINED:
case VR_VARYING:
@@ -206,8 +206,9 @@ value_range_equiv::intersect (const value_range_equiv *other)
this->deep_copy (other);
else
{
- value_range tem = intersect_helper (this, other);
- this->update (tem.min (), tem.max (), tem.kind ());
+ legacy_intersect (this, other);
+ if (varying_p () || undefined_p ())
+ equiv_clear ();
/* If the result is VR_UNDEFINED there is no need to mess with
equivalencies. */
@@ -254,8 +255,9 @@ value_range_equiv::union_ (const value_range_equiv *other)
this->deep_copy (other);
else
{
- value_range tem = union_helper (this, other);
- this->update (tem.min (), tem.max (), tem.kind ());
+ legacy_union (this, other);
+ if (varying_p () || undefined_p ())
+ equiv_clear ();
/* The resulting set of equivalences is always the intersection of
the two sets. */
@@ -277,7 +279,7 @@ void
value_range_equiv::dump (FILE *file) const
{
value_range::dump (file);
- if ((m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
+ if ((kind () == VR_RANGE || kind () == VR_ANTI_RANGE)
&& m_equiv)
{
bitmap_iterator bi;
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index bc4b061da57..93164b7e2e2 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1,5 +1,7 @@
/* Support routines for value ranges.
Copyright (C) 2019-2020 Free Software Foundation, Inc.
+ Major hacks by Aldy Hernandez <aldyh@redhat.com> and
+ Andrew MacLeod <amacleod@redhat.com>.
This file is part of GCC.
@@ -27,45 +29,168 @@ along with GCC; see the file COPYING3. If not see
#include "tree-pretty-print.h"
#include "fold-const.h"
-value_range::value_range (tree min, tree max, value_range_kind kind)
+// Here we copy between any two irange's. The ranges can be legacy or
+// multi-ranges, and copying between any combination works correctly.
+
+irange &
+irange::operator= (const irange &src)
+{
+ if (legacy_mode_p () != src.legacy_mode_p ())
+ {
+ copy_legacy_range (src);
+ return *this;
+ }
+ if (legacy_mode_p ())
+ {
+ gcc_checking_assert (src.legacy_mode_p ());
+ m_num_ranges = src.m_num_ranges;
+ m_base[0] = src.m_base[0];
+ m_base[1] = src.m_base[1];
+ m_kind = src.m_kind;
+ return *this;
+ }
+
+ unsigned x;
+ unsigned lim = src.m_num_ranges;
+ if (lim > m_max_ranges)
+ lim = m_max_ranges;
+
+ for (x = 0; x < lim * 2; ++x)
+ m_base[x] = src.m_base[x];
+
+ // If the range didn't fit, the last range should cover the rest.
+ if (lim != src.m_num_ranges)
+ m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
+
+ m_num_ranges = lim;
+ return *this;
+}
+
+// Return TRUE if range is a multi-range that can be represented as a
+// VR_ANTI_RANGE.
+
+bool
+irange::maybe_anti_range () const
{
- set (min, max, kind);
+ tree ttype = type ();
+ unsigned int precision = TYPE_PRECISION (ttype);
+ signop sign = TYPE_SIGN (ttype);
+ return (num_pairs () > 1
+ && precision > 1
+ && lower_bound () == wi::min_value (precision, sign)
+ && upper_bound () == wi::max_value (precision, sign));
}
-value_range::value_range (tree type)
+// Copy between a legacy and a multi-range, or vice-versa.
+
+void
+irange::copy_legacy_range (const irange &src)
{
- set_varying (type);
+ gcc_checking_assert (src.legacy_mode_p () != legacy_mode_p ());
+ if (src.undefined_p ())
+ set_undefined ();
+ else if (src.varying_p ())
+ set_varying (src.type ());
+ else if (src.kind () == VR_ANTI_RANGE)
+ set (src.min (), src.max (), VR_ANTI_RANGE);
+ else if (legacy_mode_p () && src.maybe_anti_range ())
+ {
+ int_range<3> tmp (src);
+ tmp.invert ();
+ set (tmp.min (), wide_int_to_tree (src.type (), tmp.upper_bound (0)),
+ VR_ANTI_RANGE);
+ }
+ else
+ set (src.min (), src.max (), VR_RANGE);
}
-value_range::value_range (tree type,
- const wide_int &wmin, const wide_int &wmax,
- enum value_range_kind kind)
+// Swap min/max if they are out of order. Return TRUE if further
+// processing of the range is necessary, FALSE otherwise.
+
+bool
+irange::swap_out_of_order_endpoints (tree &min, tree &max,
+ value_range_kind &kind)
{
- tree min = wide_int_to_tree (type, wmin);
- tree max = wide_int_to_tree (type, wmax);
- gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
- set (min, max, kind);
+ /* Wrong order for min and max, to swap them and the VR type we need
+ to adjust them. */
+ if (tree_int_cst_lt (max, min))
+ {
+ tree one, tmp;
+
+ /* For one bit precision if max < min, then the swapped
+ range covers all values, so for VR_RANGE it is varying and
+ for VR_ANTI_RANGE empty range, so drop to varying as well. */
+ if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
+ {
+ set_varying (TREE_TYPE (min));
+ return false;
+ }
+
+ one = build_int_cst (TREE_TYPE (min), 1);
+ tmp = int_const_binop (PLUS_EXPR, max, one);
+ max = int_const_binop (MINUS_EXPR, min, one);
+ min = tmp;
+
+ /* There's one corner case, if we had [C+1, C] before we now have
+ that again. But this represents an empty value range, so drop
+ to varying in this case. */
+ if (tree_int_cst_lt (max, min))
+ {
+ set_varying (TREE_TYPE (min));
+ return false;
+ }
+ kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
+ }
+ return true;
}
void
-value_range::set_undefined ()
+irange::irange_set (tree min, tree max)
{
- m_kind = VR_UNDEFINED;
- m_min = m_max = NULL;
+ gcc_checking_assert (!POLY_INT_CST_P (min));
+ gcc_checking_assert (!POLY_INT_CST_P (max));
+
+ m_base[0] = min;
+ m_base[1] = max;
+ m_num_ranges = 1;
+ if (flag_checking)
+ verify_range ();
}
void
-value_range::set_varying (tree type)
+irange::irange_set_anti_range (tree min, tree max)
{
- m_kind = VR_VARYING;
- if (supports_type_p (type))
+ gcc_checking_assert (!POLY_INT_CST_P (min));
+ gcc_checking_assert (!POLY_INT_CST_P (max));
+
+ // set an anti-range
+ tree type = TREE_TYPE (min);
+ signop sign = TYPE_SIGN (type);
+ int_range<2> type_range (type);
+ // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
+ m_num_ranges = 0;
+ wi::overflow_type ovf;
+
+ wide_int w_min = wi::to_wide (min);
+ if (wi::ne_p (w_min, type_range.lower_bound ()))
{
- m_min = vrp_val_min (type);
- m_max = vrp_val_max (type);
+ wide_int lim1 = wi::sub (w_min, 1, sign, &ovf);
+ gcc_checking_assert (ovf != wi::OVF_OVERFLOW);
+ m_base[0] = type_range.tree_lower_bound (0);
+ m_base[1] = wide_int_to_tree (type, lim1);
+ m_num_ranges = 1;
}
- else
- /* We can't do anything range-wise with these types. */
- m_min = m_max = error_mark_node;
+ wide_int w_max = wi::to_wide (max);
+ if (wi::ne_p (w_max, type_range.upper_bound ()))
+ {
+ wide_int lim2 = wi::add (w_max, 1, sign, &ovf);
+ gcc_checking_assert (ovf != wi::OVF_OVERFLOW);
+ m_base[m_num_ranges * 2] = wide_int_to_tree (type, lim2);
+ m_base[m_num_ranges * 2 + 1] = type_range.tree_upper_bound (0);
+ ++m_num_ranges;
+ }
+ if (flag_checking)
+ verify_range ();
}
/* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
@@ -78,15 +203,24 @@ value_range::set_varying (tree type)
extract ranges from var + CST op limit. */
void
-value_range::set (tree min, tree max, value_range_kind kind)
+irange::set (tree min, tree max, value_range_kind kind)
{
- /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
+ if (!legacy_mode_p ())
+ {
+ if (kind == VR_RANGE)
+ irange_set (min, max);
+ else
+ {
+ gcc_checking_assert (kind == VR_ANTI_RANGE);
+ irange_set_anti_range (min, max);
+ }
+ return;
+ }
if (kind == VR_UNDEFINED)
{
set_undefined ();
return;
}
-
if (kind == VR_RANGE)
{
/* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */
@@ -109,68 +243,30 @@ value_range::set (tree min, tree max, value_range_kind kind)
}
else if (kind != VR_VARYING)
{
- if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
- kind = VR_VARYING;
+ if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
+ kind = VR_VARYING;
}
-
if (kind == VR_VARYING)
{
- gcc_assert (TREE_TYPE (min) == TREE_TYPE (max));
- tree typ = TREE_TYPE (min);
- if (supports_type_p (typ))
- {
- gcc_assert (vrp_val_min (typ));
- gcc_assert (vrp_val_max (typ));
- }
- set_varying (typ);
+ set_varying (TREE_TYPE (min));
return;
}
- /* Nothing to canonicalize for symbolic ranges. */
+ tree type = TREE_TYPE (min);
+ // Nothing to canonicalize for symbolic ranges.
if (TREE_CODE (min) != INTEGER_CST
|| TREE_CODE (max) != INTEGER_CST)
{
m_kind = kind;
- m_min = min;
- m_max = max;
+ m_base[0] = min;
+ m_base[1] = max;
+ m_num_ranges = 1;
return;
}
+ if (!swap_out_of_order_endpoints (min, max, kind))
+ goto cleanup_set;
- /* Wrong order for min and max, to swap them and the VR type we need
- to adjust them. */
- if (tree_int_cst_lt (max, min))
- {
- tree one, tmp;
-
- /* For one bit precision if max < min, then the swapped
- range covers all values, so for VR_RANGE it is varying and
- for VR_ANTI_RANGE empty range, so drop to varying as well. */
- if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
- {
- set_varying (TREE_TYPE (min));
- return;
- }
-
- one = build_int_cst (TREE_TYPE (min), 1);
- tmp = int_const_binop (PLUS_EXPR, max, one);
- max = int_const_binop (MINUS_EXPR, min, one);
- min = tmp;
-
- /* There's one corner case, if we had [C+1, C] before we now have
- that again. But this represents an empty value range, so drop
- to varying in this case. */
- if (tree_int_cst_lt (max, min))
- {
- set_varying (TREE_TYPE (min));
- return;
- }
-
- kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
- }
-
- tree type = TREE_TYPE (min);
-
- /* Anti-ranges that can be represented as ranges should be so. */
+ // Anti-ranges that can be represented as ranges should be so.
if (kind == VR_ANTI_RANGE)
{
/* For -fstrict-enums we may receive out-of-range ranges so consider
@@ -211,109 +307,90 @@ value_range::set (tree min, tree max, value_range_kind kind)
kind = VR_RANGE;
}
}
+ else if (!swap_out_of_order_endpoints (min, max, kind))
+ goto cleanup_set;
- /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+ /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
+ to make sure VRP iteration terminates, otherwise we can get into
+ oscillations. */
+ if (!normalize_min_max (type, min, max, kind))
+ {
+ m_kind = kind;
+ m_base[0] = min;
+ m_base[1] = max;
+ m_num_ranges = 1;
+ if (flag_checking)
+ verify_range ();
+ }
- Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
- restrict those to a subset of what actually fits in the type.
- Instead use the extremes of the type precision which will allow
- compare_range_with_value() to check if a value is inside a range,
- whereas if we used TYPE_*_VAL, said function would just punt
- upon seeing a VARYING. */
+ cleanup_set:
+ // Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
+ // restrict those to a subset of what actually fits in the type.
+ // Instead use the extremes of the type precision
unsigned prec = TYPE_PRECISION (type);
signop sign = TYPE_SIGN (type);
if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
&& wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
- {
- if (kind == VR_RANGE)
- set_varying (type);
- else if (kind == VR_ANTI_RANGE)
- set_undefined ();
- else
- gcc_unreachable ();
- return;
- }
-
- /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
- to make sure VRP iteration terminates, otherwise we can get into
- oscillations. */
-
- m_kind = kind;
- m_min = min;
- m_max = max;
+ m_kind = VR_VARYING;
+ else if (undefined_p ())
+ m_kind = VR_UNDEFINED;
if (flag_checking)
- check ();
-}
-
-void
-value_range::set (tree val)
-{
- gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
- if (TREE_OVERFLOW_P (val))
- val = drop_tree_overflow (val);
- set (val, val);
-}
-
-/* Set value range VR to a nonzero range of type TYPE. */
-
-void
-value_range::set_nonzero (tree type)
-{
- tree zero = build_int_cst (type, 0);
- set (zero, zero, VR_ANTI_RANGE);
-}
-
-/* Set value range VR to a ZERO range of type TYPE. */
-
-void
-value_range::set_zero (tree type)
-{
- set (build_int_cst (type, 0));
+ verify_range ();
}
/* Check the validity of the range. */
void
-value_range::check ()
+irange::verify_range ()
{
- switch (m_kind)
+ if (!legacy_mode_p ())
{
- case VR_RANGE:
- case VR_ANTI_RANGE:
- {
- gcc_assert (m_min && m_max);
- gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max));
-
- /* Creating ~[-MIN, +MAX] is stupid because that would be
- the empty set. */
- if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE)
- gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max));
+ gcc_checking_assert (m_kind == VR_RANGE);
+ for (unsigned i = 0; i < m_num_ranges; ++i)
+ {
+ tree lb = tree_lower_bound (i);
+ tree ub = tree_upper_bound (i);
+ int c = compare_values (lb, ub);
+ gcc_assert (c == 0 || c == -1);
+ }
+ return;
+ }
- int cmp = compare_values (m_min, m_max);
- gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
- break;
- }
+ switch (m_kind)
+ {
case VR_UNDEFINED:
- gcc_assert (!min () && !max ());
+ gcc_assert (m_num_ranges == 0);
break;
+
case VR_VARYING:
- gcc_assert (m_min && m_max);
+ gcc_assert (m_num_ranges == 1);
break;
+
+ case VR_ANTI_RANGE:
+ case VR_RANGE:
+ {
+ gcc_assert (m_num_ranges == 1);
+ int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0));
+ gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
+ return;
+ }
+
default:
gcc_unreachable ();
}
}
-/* Return the number of sub-ranges in a range. */
-
unsigned
-value_range::num_pairs () const
+irange::legacy_num_pairs () const
{
+ gcc_checking_assert (legacy_mode_p ());
+
if (undefined_p ())
return 0;
if (varying_p ())
return 1;
- if (symbolic_p ())
+ // Inlined symbolic_p for performance:
+ if (!is_gimple_min_invariant (min ()) || !is_gimple_min_invariant (max ()))
{
value_range numeric_range (*this);
numeric_range.normalize_symbolics ();
@@ -323,111 +400,124 @@ value_range::num_pairs () const
{
// ~[MIN, X] has one sub-range of [X+1, MAX], and
// ~[X, MAX] has one sub-range of [MIN, X-1].
- if (vrp_val_is_min (m_min) || vrp_val_is_max (m_max))
+ if (vrp_val_is_min (min ()) || vrp_val_is_max (max ()))
return 1;
return 2;
}
+ gcc_checking_assert (m_num_ranges == 1);
return 1;
}
-/* Return the lower bound for a sub-range. PAIR is the sub-range in
- question. */
+// Return the lower bound for a sub-range. PAIR is the sub-range in
+// question.
wide_int
-value_range::lower_bound (unsigned pair) const
+irange::legacy_lower_bound (unsigned pair) const
{
+ gcc_checking_assert (legacy_mode_p ());
if (symbolic_p ())
{
value_range numeric_range (*this);
numeric_range.normalize_symbolics ();
- return numeric_range.lower_bound (pair);
+ return numeric_range.legacy_lower_bound (pair);
}
-
gcc_checking_assert (!undefined_p ());
gcc_checking_assert (pair + 1 <= num_pairs ());
- tree t = NULL;
if (m_kind == VR_ANTI_RANGE)
{
- tree typ = type ();
- if (pair == 1 || vrp_val_is_min (m_min))
- t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1);
+ tree typ = type (), t;
+ if (pair == 1 || vrp_val_is_min (min ()))
+ t = wide_int_to_tree (typ, wi::to_wide (max ()) + 1);
else
t = vrp_val_min (typ);
+ return wi::to_wide (t);
}
- else
- t = m_min;
- return wi::to_wide (t);
+ return wi::to_wide (tree_lower_bound (pair));
}
-/* Return the upper bound for a sub-range. PAIR is the sub-range in
- question. */
+// Return the upper bound for a sub-range. PAIR is the sub-range in
+// question.
wide_int
-value_range::upper_bound (unsigned pair) const
+irange::legacy_upper_bound (unsigned pair) const
{
+ gcc_checking_assert (legacy_mode_p ());
if (symbolic_p ())
{
value_range numeric_range (*this);
numeric_range.normalize_symbolics ();
- return numeric_range.upper_bound (pair);
+ return numeric_range.legacy_upper_bound (pair);
}
-
gcc_checking_assert (!undefined_p ());
gcc_checking_assert (pair + 1 <= num_pairs ());
- tree t = NULL;
if (m_kind == VR_ANTI_RANGE)
{
- tree typ = type ();
- if (pair == 1 || vrp_val_is_min (m_min))
+ tree typ = type (), t;
+ if (pair == 1 || vrp_val_is_min (min ()))
t = vrp_val_max (typ);
else
- t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1);
+ t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1);
+ return wi::to_wide (t);
}
- else
- t = m_max;
- return wi::to_wide (t);
-}
-
-/* Return the highest bound in a range. */
-
-wide_int
-value_range::upper_bound () const
-{
- unsigned pairs = num_pairs ();
- gcc_checking_assert (pairs > 0);
- return upper_bound (pairs - 1);
+ return wi::to_wide (tree_upper_bound (pair));
}
bool
-value_range::equal_p (const value_range &other) const
+irange::legacy_equal_p (const irange &other) const
{
- /* Ignore types for undefined. All undefines are equal. */
- if (undefined_p ())
- return m_kind == other.m_kind;
+ gcc_checking_assert (legacy_mode_p () && other.legacy_mode_p ());
- return (m_kind == other.m_kind
- && vrp_operand_equal_p (m_min, other.m_min)
- && vrp_operand_equal_p (m_max, other.m_max));
+ if (m_kind != other.m_kind)
+ return false;
+ if (m_kind == VR_UNDEFINED || m_kind == VR_VARYING)
+ return true;
+ return (vrp_operand_equal_p (tree_lower_bound (0),
+ other.tree_lower_bound (0))
+ && vrp_operand_equal_p (tree_upper_bound (0),
+ other.tree_upper_bound (0)));
}
bool
-value_range::operator== (const value_range &r) const
+irange::equal_p (const irange &other) const
{
- return equal_p (r);
+ if (legacy_mode_p ())
+ {
+ if (other.legacy_mode_p ())
+ return legacy_equal_p (other);
+ value_range tmp (other);
+ return legacy_equal_p (tmp);
+ }
+ if (other.legacy_mode_p ())
+ {
+ value_range tmp2 (*this);
+ return tmp2.legacy_equal_p (other);
+ }
+
+ if (m_num_ranges != other.m_num_ranges)
+ return false;
+
+ for (unsigned i = 0; i < m_num_ranges; ++i)
+ {
+ tree lb = tree_lower_bound (i);
+ tree ub = tree_upper_bound (i);
+ tree lb_other = other.tree_lower_bound (i);
+ tree ub_other = other.tree_upper_bound (i);
+ if (!operand_equal_p (lb, lb_other, 0)
+ || !operand_equal_p (ub, ub_other, 0))
+ return false;
+ }
+ return true;
}
-/* If range is a singleton, place it in RESULT and return TRUE.
- Note: A singleton can be any gimple invariant, not just constants.
- So, [&x, &x] counts as a singleton. */
/* Return TRUE if this is a symbolic range. */
bool
-value_range::symbolic_p () const
+irange::symbolic_p () const
{
return (!varying_p ()
&& !undefined_p ()
- && (!is_gimple_min_invariant (m_min)
- || !is_gimple_min_invariant (m_max)));
+ && (!is_gimple_min_invariant (min ())
+ || !is_gimple_min_invariant (max ())));
}
/* NOTE: This is not the inverse of symbolic_p because the range
@@ -436,17 +526,32 @@ value_range::symbolic_p () const
constants would be represented as [-MIN, +MAX]. */
bool
-value_range::constant_p () const
+irange::constant_p () const
{
return (!varying_p ()
&& !undefined_p ()
- && TREE_CODE (m_min) == INTEGER_CST
- && TREE_CODE (m_max) == INTEGER_CST);
+ && TREE_CODE (min ()) == INTEGER_CST
+ && TREE_CODE (max ()) == INTEGER_CST);
}
+/* If range is a singleton, place it in RESULT and return TRUE.
+ Note: A singleton can be any gimple invariant, not just constants.
+ So, [&x, &x] counts as a singleton. */
+
bool
-value_range::singleton_p (tree *result) const
+irange::singleton_p (tree *result) const
{
+ if (!legacy_mode_p ())
+ {
+ if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
+ == wi::to_wide (tree_upper_bound ())))
+ {
+ if (result)
+ *result = tree_lower_bound ();
+ return true;
+ }
+ return false;
+ }
if (m_kind == VR_ANTI_RANGE)
{
if (nonzero_p ())
@@ -454,7 +559,7 @@ value_range::singleton_p (tree *result) const
if (TYPE_PRECISION (type ()) == 1)
{
if (result)
- *result = m_max;
+ *result = max ();
return true;
}
return false;
@@ -462,10 +567,11 @@ value_range::singleton_p (tree *result) const
if (num_pairs () == 1)
{
value_range vr0, vr1;
- ranges_from_anti_range (this, &vr0, &vr1);
+ ranges_from_anti_range ((const value_range *) this, &vr0, &vr1);
return vr0.singleton_p (result);
}
}
+ // Catches non-numeric extremes as well.
if (m_kind == VR_RANGE
&& vrp_operand_equal_p (min (), max ())
&& is_gimple_min_invariant (min ()))
@@ -478,30 +584,31 @@ value_range::singleton_p (tree *result) const
}
/* Return 1 if VAL is inside value range.
- 0 if VAL is not inside value range.
+ 0 if VAL is not inside value range.
-2 if we cannot tell either way.
Benchmark compile/20001226-1.c compilation time after changing this
function. */
int
-value_range::value_inside_range (tree val) const
+irange::value_inside_range (tree val) const
{
- int cmp1, cmp2;
-
if (varying_p ())
return 1;
if (undefined_p ())
return 0;
- cmp1 = operand_less_p (val, m_min);
+ if (!legacy_mode_p () && TREE_CODE (val) == INTEGER_CST)
+ return contains_p (val);
+
+ int cmp1 = operand_less_p (val, min ());
if (cmp1 == -2)
return -2;
if (cmp1 == 1)
return m_kind != VR_RANGE;
- cmp2 = operand_less_p (m_max, val);
+ int cmp2 = operand_less_p (max (), val);
if (cmp2 == -2)
return -2;
@@ -514,30 +621,56 @@ value_range::value_inside_range (tree val) const
/* Return TRUE if it is possible that range contains VAL. */
bool
-value_range::may_contain_p (tree val) const
+irange::may_contain_p (tree val) const
{
return value_inside_range (val) != 0;
}
/* Return TRUE if range contains INTEGER_CST. */
+/* Return 1 if VAL is inside value range.
+ 0 if VAL is not inside value range.
+
+ Benchmark compile/20001226-1.c compilation time after changing this
+ function. */
+
bool
-value_range::contains_p (tree cst) const
+irange::contains_p (tree cst) const
{
+ if (undefined_p ())
+ return false;
+
+ if (legacy_mode_p ())
+ {
+ gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
+ if (symbolic_p ())
+ {
+ value_range numeric_range (*this);
+ numeric_range.normalize_symbolics ();
+ return numeric_range.contains_p (cst);
+ }
+ return value_inside_range (cst) == 1;
+ }
+
gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
- if (symbolic_p ())
+ signop sign = TYPE_SIGN (TREE_TYPE (cst));
+ wide_int v = wi::to_wide (cst);
+ for (unsigned r = 0; r < m_num_ranges; ++r)
{
- value_range numeric_range (*this);
- numeric_range.normalize_symbolics ();
- return numeric_range.contains_p (cst);
+ if (wi::lt_p (v, lower_bound (r), sign))
+ return false;
+ if (wi::le_p (v, upper_bound (r), sign))
+ return true;
}
- return value_inside_range (cst) == 1;
+
+ return false;
}
+
/* Normalize addresses into constants. */
void
-value_range::normalize_addresses ()
+irange::normalize_addresses ()
{
if (undefined_p ())
return;
@@ -547,8 +680,8 @@ value_range::normalize_addresses ()
if (!range_includes_zero_p (this))
{
- gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
- || TREE_CODE (m_max) == ADDR_EXPR);
+ gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
+ || TREE_CODE (max ()) == ADDR_EXPR);
set_nonzero (type ());
return;
}
@@ -558,7 +691,7 @@ value_range::normalize_addresses ()
/* Normalize symbolics and addresses into constants. */
void
-value_range::normalize_symbolics ()
+irange::normalize_symbolics ()
{
if (varying_p () || undefined_p ())
return;
@@ -939,45 +1072,64 @@ intersect_ranges (enum value_range_kind *vr0type,
}
/* Helper for the intersection operation for value ranges. Given two
- value ranges VR0 and VR1, return the intersection of the two
- ranges. This may not be the smallest possible such range. */
+ ranges VR0 and VR1, set VR0 to the intersection of both ranges.
+ This may not be the smallest possible such range. */
-value_range
-value_range::intersect_helper (const value_range *vr0, const value_range *vr1)
+void
+irange::legacy_intersect (irange *vr0, const irange *vr1)
{
/* If either range is VR_VARYING the other one wins. */
if (vr1->varying_p ())
- return *vr0;
+ return;
if (vr0->varying_p ())
- return *vr1;
+ {
+ /* Avoid the full copy if we already know both sides are simple
+ and can be trivially copied. */
+ if (vr1->legacy_mode_p ())
+ {
+ vr0->set (vr1->min (), vr1->max (), vr1->kind ());
+ return;
+ }
+ *vr0 = *vr1;
+ return;
+ }
/* When either range is VR_UNDEFINED the resulting range is
VR_UNDEFINED, too. */
if (vr0->undefined_p ())
- return *vr0;
+ return;
if (vr1->undefined_p ())
- return *vr1;
+ {
+ vr0->set_undefined ();
+ return;
+ }
value_range_kind vr0kind = vr0->kind ();
tree vr0min = vr0->min ();
tree vr0max = vr0->max ();
- intersect_ranges (&vr0kind, &vr0min, &vr0max,
- vr1->kind (), vr1->min (), vr1->max ());
+ /* Handle multi-ranges that can be represented as anti-ranges. */
+ if (!vr1->legacy_mode_p () && vr1->maybe_anti_range ())
+ {
+ int_range<3> tmp (*vr1);
+ tmp.invert ();
+ intersect_ranges (&vr0kind, &vr0min, &vr0max,
+ VR_ANTI_RANGE, tmp.min (), tmp.max ());
+ }
+ else
+ intersect_ranges (&vr0kind, &vr0min, &vr0max,
+ vr1->kind (), vr1->min (), vr1->max ());
+
/* Make sure to canonicalize the result though as the inversion of a
- VR_RANGE can still be a VR_RANGE. Work on a temporary so we can
- fall back to vr0 when this turns things to varying. */
- value_range tem;
+ VR_RANGE can still be a VR_RANGE. */
if (vr0kind == VR_UNDEFINED)
- tem.set_undefined ();
+ vr0->set_undefined ();
else if (vr0kind == VR_VARYING)
- tem.set_varying (vr0->type ());
+ {
+ /* If we failed, use the original VR0. */
+ return;
+ }
else
- tem.set (vr0min, vr0max, vr0kind);
- /* If that failed, use the saved original VR0. */
- if (tem.varying_p ())
- return *vr0;
-
- return tem;
+ vr0->set (vr0min, vr0max, vr0kind);
}
/* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
@@ -1253,50 +1405,67 @@ give_up:
*vr0max = NULL_TREE;
}
-/* Helper for meet operation for value ranges. Given two value ranges VR0 and
- VR1, return a range that contains both VR0 and VR1. This may not be the
+/* Helper for meet operation for value ranges. Given two ranges VR0
+ and VR1, set VR0 to the union of both ranges. This may not be the
smallest possible such range. */
-value_range
-value_range::union_helper (const value_range *vr0, const value_range *vr1)
+void
+irange::legacy_union (irange *vr0, const irange *vr1)
{
/* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
if (vr1->undefined_p ()
|| vr0->varying_p ())
- return *vr0;
+ return;
/* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
- if (vr0->undefined_p ()
- || vr1->varying_p ())
- return *vr1;
+ if (vr0->undefined_p ())
+ {
+ /* Avoid the full copy if we already know both sides are simple
+ and can be trivially copied. */
+ if (vr1->legacy_mode_p ())
+ {
+ vr0->set (vr1->min (), vr1->max (), vr1->kind ());
+ return;
+ }
+ *vr0 = *vr1;
+ return;
+ }
+ if (vr1->varying_p ())
+ {
+ vr0->set_varying (vr1->type ());
+ return;
+ }
value_range_kind vr0kind = vr0->kind ();
tree vr0min = vr0->min ();
tree vr0max = vr0->max ();
- union_ranges (&vr0kind, &vr0min, &vr0max,
- vr1->kind (), vr1->min (), vr1->max ());
+ /* Handle multi-ranges that can be represented as anti-ranges. */
+ if (!vr1->legacy_mode_p () && vr1->maybe_anti_range ())
+ {
+ int_range<3> tmp (*vr1);
+ tmp.invert ();
+ union_ranges (&vr0kind, &vr0min, &vr0max,
+ VR_ANTI_RANGE, tmp.min (), tmp.max ());
+ }
+ else
+ union_ranges (&vr0kind, &vr0min, &vr0max,
+ vr1->kind (), vr1->min (), vr1->max ());
- /* Work on a temporary so we can still use vr0 when union returns varying. */
- value_range tem;
if (vr0kind == VR_UNDEFINED)
- tem.set_undefined ();
+ vr0->set_undefined ();
else if (vr0kind == VR_VARYING)
- tem.set_varying (vr0->type ());
- else
- tem.set (vr0min, vr0max, vr0kind);
-
- /* Failed to find an efficient meet. Before giving up and setting
- the result to VARYING, see if we can at least derive a useful
- anti-range. */
- if (tem.varying_p ()
- && range_includes_zero_p (vr0) == 0
- && range_includes_zero_p (vr1) == 0)
{
- tem.set_nonzero (vr0->type ());
- return tem;
+ /* Failed to find an efficient meet. Before giving up and
+ setting the result to VARYING, see if we can at least derive
+ a non-zero range. */
+ if (range_includes_zero_p (vr0) == 0
+ && range_includes_zero_p (vr1) == 0)
+ vr0->set_nonzero (vr0->type ());
+ else
+ vr0->set_varying (vr0->type ());
}
-
- return tem;
+ else
+ vr0->set (vr0min, vr0max, vr0kind);
}
/* Meet operation for value ranges. Given two value ranges VR0 and
@@ -1304,161 +1473,495 @@ value_range::union_helper (const value_range *vr0, const value_range *vr1)
may not be the smallest possible such range. */
void
-value_range::union_ (const value_range *other)
+irange::union_ (const irange *other)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (legacy_mode_p ())
{
- fprintf (dump_file, "Meeting\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\nand\n ");
- dump_value_range (dump_file, other);
- fprintf (dump_file, "\n");
- }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Meeting\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, other);
+ fprintf (dump_file, "\n");
+ }
- *this = union_helper (this, other);
+ legacy_union (this, other);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
+ }
+ return;
+ }
+
+ if (other->legacy_mode_p ())
{
- fprintf (dump_file, "to\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\n");
+ int_range<2> wider;
+ wider = *other;
+ irange_union (wider);
}
+ else
+ irange_union (*other);
}
-/* Range union, but for references. */
-
void
-value_range::union_ (const value_range &r)
+irange::intersect (const irange *other)
{
- /* Disable details for now, because it makes the ranger dump
- unnecessarily verbose. */
- bool details = dump_flags & TDF_DETAILS;
- if (details)
- dump_flags &= ~TDF_DETAILS;
- union_ (&r);
- if (details)
- dump_flags |= TDF_DETAILS;
+ if (legacy_mode_p ())
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Intersecting\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, other);
+ fprintf (dump_file, "\n");
+ }
+
+ legacy_intersect (this, other);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
+ }
+ return;
+ }
+
+ if (other->legacy_mode_p ())
+ {
+ int_range<2> wider;
+ wider = *other;
+ irange_intersect (wider);
+ }
+ else
+ irange_intersect (*other);
}
+// union_ for multi-ranges.
+
void
-value_range::intersect (const value_range *other)
+irange::irange_union (const irange &r)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
+ gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
+
+ if (r.undefined_p () || varying_p ())
+ return;
+
+ if (undefined_p () || r.varying_p ())
{
- fprintf (dump_file, "Intersecting\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\nand\n ");
- dump_value_range (dump_file, other);
- fprintf (dump_file, "\n");
+ operator= (r);
+ return;
}
- *this = intersect_helper (this, other);
+ // Do not worry about merging and such by reserving twice as many
+ // pairs as needed, and then simply sort the 2 ranges into this
+ // intermediate form.
+ //
+ // The intermediate result will have the property that the beginning
+ // of each range is <= the beginning of the next range. There may
+ // be overlapping ranges at this point. I.e. this would be valid
+ // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
+ // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
+ // the merge is performed.
+ //
+ // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
+ tree ttype = r.type ();
+ signop sign = TYPE_SIGN (ttype);
+
+ auto_vec<tree, 20> res;
+ wide_int u1 ;
+ wi::overflow_type ovf;
+ unsigned i = 0, j = 0, k = 0;
+
+ while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
+ {
+ // lower of Xi and Xj is the lowest point.
+ if (wi::le_p (wi::to_wide (m_base[i]), wi::to_wide (r.m_base[j]), sign))
+ {
+ res.safe_push (m_base[i]);
+ res.safe_push (m_base[i + 1]);
+ k += 2;
+ i += 2;
+ }
+ else
+ {
+ res.safe_push (r.m_base[j]);
+ res.safe_push (r.m_base[j + 1]);
+ k += 2;
+ j += 2;
+ }
+ }
+ for ( ; i < m_num_ranges * 2; i += 2)
+ {
+ res.safe_push (m_base[i]);
+ res.safe_push (m_base[i + 1]);
+ k += 2;
+ }
+ for ( ; j < r.m_num_ranges * 2; j += 2)
+ {
+ res.safe_push (r.m_base[j]);
+ res.safe_push (r.m_base[j + 1]);
+ k += 2;
+ }
- if (dump_file && (dump_flags & TDF_DETAILS))
+ // Now normalize the vector removing any overlaps.
+ i = 2;
+ int prec = TYPE_PRECISION (ttype);
+ wide_int max_val = wi::max_value (prec, sign);
+ for (j = 2; j < k ; j += 2)
{
- fprintf (dump_file, "to\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\n");
+ wide_int val_im1 = wi::to_wide (res[i - 1]);
+ if (val_im1 == max_val)
+ break;
+ u1 = wi::add (val_im1, 1, sign, &ovf);
+
+ // Overflow indicates we are at MAX already.
+ // A wide int bug requires the previous max_val check
+ // trigger: gcc.c-torture/compile/pr80443.c with -O3
+ if (ovf == wi::OVF_OVERFLOW)
+ break;
+
+ wide_int val_j = wi::to_wide (res[j]);
+ wide_int val_jp1 = wi::to_wide (res[j+1]);
+ // Current upper+1 is >= lower bound next pair, then we merge ranges.
+ if (wi::ge_p (u1, val_j, sign))
+ {
+ // New upper bounds is greater of current or the next one.
+ if (wi::gt_p (val_jp1, val_im1, sign))
+ res [i - 1] = res[j + 1];
+ }
+ else
+ {
+ // This is a new distinct range, but no point in copying it
+ // if it is already in the right place.
+ if (i != j)
+ {
+ res[i++] = res[j];
+ res[i++] = res[j + 1];
+ }
+ else
+ i += 2;
+ }
}
+
+ // At this point, the vector should have i ranges, none overlapping.
+ // Now it simply needs to be copied, and if there are too many
+ // ranges, merge some. We wont do any analysis as to what the
+ // "best" merges are, simply combine the final ranges into one.
+ if (i > m_max_ranges * 2)
+ {
+ res[m_max_ranges * 2 - 1] = res[i - 1];
+ i = m_max_ranges * 2;
+ }
+
+ for (j = 0; j < i ; j++)
+ m_base[j] = res [j];
+ m_num_ranges = i / 2;
+
+ if (flag_checking)
+ verify_range ();
}
-/* Range intersect, but for references. */
+// intersect for multi-ranges.
void
-value_range::intersect (const value_range &r)
+irange::irange_intersect (const irange &r)
+{
+ gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
+
+ if (undefined_p () || r.varying_p ())
+ return;
+ if (r.undefined_p ())
+ {
+ set_undefined ();
+ return;
+ }
+ if (varying_p ())
+ {
+ operator= (r);
+ return;
+ }
+
+ signop sign = TYPE_SIGN (TREE_TYPE(m_base[0]));
+ unsigned bld_pair = 0;
+ unsigned bld_lim = m_max_ranges;
+ widest_irange r2 (*this);
+ unsigned r2_lim = r2.num_pairs ();
+ unsigned i2 = 0;
+ for (unsigned i = 0; i < r.num_pairs (); )
+ {
+ // If r1's upper is < r2's lower, we can skip r1's pair.
+ tree ru = r.m_base[i * 2 + 1];
+ tree r2l = r2.m_base[i2 * 2];
+ if (wi::lt_p (wi::to_wide (ru), wi::to_wide (r2l), sign))
+ {
+ i++;
+ continue;
+ }
+ // Likewise, skip r2's pair if its excluded.
+ tree r2u = r2.m_base[i2 * 2 + 1];
+ tree rl = r.m_base[i * 2];
+ if (wi::lt_p (wi::to_wide (r2u), wi::to_wide (rl), sign))
+ {
+ i2++;
+ if (i2 < r2_lim)
+ continue;
+ // No more r2, break.
+ break;
+ }
+
+ // Must be some overlap. Find the highest of the lower bounds,
+ // and set it, unless the build limits lower bounds is already
+ // set.
+ if (bld_pair < bld_lim)
+ {
+ if (wi::ge_p (wi::to_wide (rl), wi::to_wide (r2l), sign))
+ m_base[bld_pair * 2] = rl;
+ else
+ m_base[bld_pair * 2] = r2l;
+ }
+ else
+ // Decrease and set a new upper.
+ bld_pair--;
+
+ // ...and choose the lower of the upper bounds.
+ if (wi::le_p (wi::to_wide (ru), wi::to_wide (r2u), sign))
+ {
+ m_base[bld_pair * 2 + 1] = ru;
+ bld_pair++;
+ // Move past the r1 pair and keep trying.
+ i++;
+ continue;
+ }
+ else
+ {
+ m_base[bld_pair * 2 + 1] = r2u;
+ bld_pair++;
+ i2++;
+ if (i2 < r2_lim)
+ continue;
+ // No more r2, break.
+ break;
+ }
+ // r2 has the higher lower bound.
+ }
+
+ // At the exit of this loop, it is one of 2 things:
+ // ran out of r1, or r2, but either means we are done.
+ m_num_ranges = bld_pair;
+ if (flag_checking)
+ verify_range ();
+}
+
+static wide_int inline
+subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
{
- /* Disable details for now, because it makes the ranger dump
- unnecessarily verbose. */
- bool details = dump_flags & TDF_DETAILS;
- if (details)
- dump_flags &= ~TDF_DETAILS;
- intersect (&r);
- if (details)
- dump_flags |= TDF_DETAILS;
+ // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1
+ // overflows, since +1 is unrepresentable. This is why we have an
+ // addition of -1 here.
+ if (TYPE_SIGN (type) == SIGNED)
+ return wi::add (x, -1 , SIGNED, &overflow);
+ else
+ return wi::sub (x, 1, UNSIGNED, &overflow);
}
/* Return the inverse of a range. */
void
-value_range::invert ()
+irange::invert ()
{
- /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
- create non-canonical ranges. Use the constructors instead. */
- if (m_kind == VR_RANGE)
- *this = value_range (m_min, m_max, VR_ANTI_RANGE);
- else if (m_kind == VR_ANTI_RANGE)
- *this = value_range (m_min, m_max);
+ if (legacy_mode_p ())
+ {
+ // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
+ // create non-canonical ranges. Use the constructors instead.
+ if (m_kind == VR_RANGE)
+ *this = value_range (min (), max (), VR_ANTI_RANGE);
+ else if (m_kind == VR_ANTI_RANGE)
+ *this = value_range (min (), max ());
+ else
+ gcc_unreachable ();
+ return;
+ }
+
+ gcc_assert (!undefined_p () && !varying_p ());
+
+ // We always need one more set of bounds to represent an inverse, so
+ // if we're at the limit, we can't properly represent things.
+ //
+ // For instance, to represent the inverse of a 2 sub-range set
+ // [5, 10][20, 30], we would need a 3 sub-range set
+ // [-MIN, 4][11, 19][31, MAX].
+ //
+ // In this case, return the most conservative thing.
+ //
+ // However, if any of the extremes of the range are -MIN/+MAX, we
+ // know we will not need an extra bound. For example:
+ //
+ // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
+ // INVERT([-MIN,20][30,MAX]) => [21,29]
+ tree ttype = type ();
+ unsigned prec = TYPE_PRECISION (ttype);
+ signop sign = TYPE_SIGN (ttype);
+ wide_int type_min = wi::min_value (prec, sign);
+ wide_int type_max = wi::max_value (prec, sign);
+ if (m_num_ranges == m_max_ranges
+ && lower_bound () != type_min
+ && upper_bound () != type_max)
+ {
+ m_base[1] = wide_int_to_tree (ttype, type_max);
+ m_num_ranges = 1;
+ return;
+ }
+ // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
+ // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
+ //
+ // If there is an over/underflow in the calculation for any
+ // sub-range, we eliminate that subrange. This allows us to easily
+ // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
+ // we eliminate the underflow, only [6, MAX] remains.
+ unsigned i = 0;
+ wi::overflow_type ovf;
+ // Construct leftmost range.
+ widest_irange orig_range (*this);
+ unsigned nitems = 0;
+ wide_int tmp;
+ // If this is going to underflow on the MINUS 1, don't even bother
+ // checking. This also handles subtracting one from an unsigned 0,
+ // which doesn't set the underflow bit.
+ if (type_min != orig_range.lower_bound ())
+ {
+ m_base[nitems++] = wide_int_to_tree (ttype, type_min);
+ tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
+ m_base[nitems++] = wide_int_to_tree (ttype, tmp);
+ if (ovf)
+ nitems = 0;
+ }
+ i++;
+ // Construct middle ranges if applicable.
+ if (orig_range.num_pairs () > 1)
+ {
+ unsigned j = i;
+ for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
+ {
+ // The middle ranges cannot have MAX/MIN, so there's no need
+ // to check for unsigned overflow on the +1 and -1 here.
+ tmp = wi::add (wi::to_wide (orig_range.m_base[j]), 1, sign, &ovf);
+ m_base[nitems++] = wide_int_to_tree (ttype, tmp);
+ tmp = subtract_one (wi::to_wide (orig_range.m_base[j + 1]),
+ ttype, ovf);
+ m_base[nitems++] = wide_int_to_tree (ttype, tmp);
+ if (ovf)
+ nitems -= 2;
+ }
+ i = j;
+ }
+ // Construct rightmost range.
+ //
+ // However, if this will overflow on the PLUS 1, don't even bother.
+ // This also handles adding one to an unsigned MAX, which doesn't
+ // set the overflow bit.
+ if (type_max != wi::to_wide (orig_range.m_base[i]))
+ {
+ tmp = wi::add (wi::to_wide (orig_range.m_base[i]), 1, sign, &ovf);
+ m_base[nitems++] = wide_int_to_tree (ttype, tmp);
+ m_base[nitems++] = wide_int_to_tree (ttype, type_max);
+ if (ovf)
+ nitems -= 2;
+ }
+ m_num_ranges = nitems / 2;
+
+ if (flag_checking)
+ verify_range ();
+}
+
+static void
+dump_bound_with_infinite_markers (FILE *file, tree bound)
+{
+ tree type = TREE_TYPE (bound);
+ if (INTEGRAL_TYPE_P (type)
+ && !TYPE_UNSIGNED (type)
+ && vrp_val_is_min (bound)
+ && TYPE_PRECISION (type) != 1)
+ fprintf (file, "-INF");
+ else if (vrp_val_is_max (bound)
+ && TYPE_PRECISION (type) != 1)
+ fprintf (file, "+INF");
else
- gcc_unreachable ();
+ print_generic_expr (file, bound);
}
void
-value_range::dump (FILE *file) const
+irange::dump (FILE *file) const
{
if (undefined_p ())
- fprintf (file, "UNDEFINED");
- else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
{
- tree ttype = type ();
-
- print_generic_expr (file, ttype);
- fprintf (file, " ");
-
+ fprintf (file, "UNDEFINED");
+ return;
+ }
+ print_generic_expr (file, type ());
+ fprintf (file, " ");
+ if (varying_p ())
+ {
+ fprintf (file, "VARYING");
+ return;
+ }
+ if (legacy_mode_p ())
+ {
fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : "");
-
- if (INTEGRAL_TYPE_P (ttype)
- && !TYPE_UNSIGNED (ttype)
- && vrp_val_is_min (min ())
- && TYPE_PRECISION (ttype) != 1)
- fprintf (file, "-INF");
- else
- print_generic_expr (file, min ());
-
+ dump_bound_with_infinite_markers (file, min ());
fprintf (file, ", ");
-
- if (supports_type_p (ttype)
- && vrp_val_is_max (max ())
- && TYPE_PRECISION (ttype) != 1)
- fprintf (file, "+INF");
- else
- print_generic_expr (file, max ());
-
+ dump_bound_with_infinite_markers (file, max ());
fprintf (file, "]");
+ return;
}
- else if (varying_p ())
+ for (unsigned i = 0; i < m_num_ranges; ++i)
{
- print_generic_expr (file, type ());
- fprintf (file, " VARYING");
+ tree lb = m_base[i * 2];
+ tree ub = m_base[i * 2 + 1];
+ fprintf (file, "[");
+ dump_bound_with_infinite_markers (file, lb);
+ fprintf (file, ", ");
+ dump_bound_with_infinite_markers (file, ub);
+ fprintf (file, "]");
}
- else
- gcc_unreachable ();
}
void
-value_range::dump () const
+dump_value_range (FILE *file, const irange *vr)
{
- dump (stderr);
+ vr->dump (file);
}
-void
-dump_value_range (FILE *file, const value_range *vr)
+DEBUG_FUNCTION void
+debug (const irange *vr)
{
- if (!vr)
- fprintf (file, "[]");
- else
- vr->dump (file);
+ dump_value_range (stderr, vr);
+ fprintf (stderr, "\n");
+}
+
+DEBUG_FUNCTION void
+debug (const irange &vr)
+{
+ debug (&vr);
}
DEBUG_FUNCTION void
debug (const value_range *vr)
{
dump_value_range (stderr, vr);
+ fprintf (stderr, "\n");
}
DEBUG_FUNCTION void
debug (const value_range &vr)
{
dump_value_range (stderr, &vr);
+ fprintf (stderr, "\n");
}
/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
@@ -1501,40 +2004,13 @@ ranges_from_anti_range (const value_range *ar,
}
bool
-range_has_numeric_bounds_p (const value_range *vr)
+range_has_numeric_bounds_p (const irange *vr)
{
- return (vr->min ()
+ return (!vr->undefined_p ()
&& TREE_CODE (vr->min ()) == INTEGER_CST
&& TREE_CODE (vr->max ()) == INTEGER_CST);
}
-/* Return the maximum value for TYPE. */
-
-tree
-vrp_val_max (const_tree type)
-{
- if (INTEGRAL_TYPE_P (type))
- return TYPE_MAX_VALUE (type);
- if (POINTER_TYPE_P (type))
- {
- wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
- return wide_int_to_tree (const_cast<tree> (type), max);
- }
- return NULL_TREE;
-}
-
-/* Return the minimum value for TYPE. */
-
-tree
-vrp_val_min (const_tree type)
-{
- if (INTEGRAL_TYPE_P (type))
- return TYPE_MIN_VALUE (type);
- if (POINTER_TYPE_P (type))
- return build_zero_cst (const_cast<tree> (type));
- return NULL_TREE;
-}
-
/* Return whether VAL is equal to the maximum value of its type.
We can't do a simple equality comparison with TYPE_MAX_VALUE because
C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
@@ -1571,3 +2047,41 @@ vrp_operand_equal_p (const_tree val1, const_tree val2)
return false;
return true;
}
+
+#define DEFINE_INT_RANGE_GC_STUBS(N) \
+ void \
+ gt_pch_nx (int_range<N> *&x) \
+ { \
+ for (unsigned i = 0; i < N; ++i) \
+ { \
+ gt_pch_nx (x->m_ranges[i * 2]); \
+ gt_pch_nx (x->m_ranges[i * 2 + 1]); \
+ } \
+ } \
+ \
+ void \
+ gt_ggc_mx (int_range<N> *&x) \
+ { \
+ for (unsigned i = 0; i < N; ++i) \
+ { \
+ gt_ggc_mx (x->m_ranges[i * 2]); \
+ gt_ggc_mx (x->m_ranges[i * 2 + 1]); \
+ } \
+ }
+
+#define DEFINE_INT_RANGE_INSTANCE(N) \
+ template int_range<N>::int_range(tree, tree, value_range_kind); \
+ template int_range<N>::int_range(tree_node *, \
+ const wide_int &, \
+ const wide_int &, \
+ value_range_kind); \
+ template int_range<N>::int_range(tree); \
+ template int_range<N>::int_range(const irange &); \
+ template int_range<N>::int_range(const int_range &); \
+ template int_range<N>& int_range<N>::operator= (const int_range &);
+
+DEFINE_INT_RANGE_INSTANCE(1)
+DEFINE_INT_RANGE_INSTANCE(2)
+DEFINE_INT_RANGE_INSTANCE(3)
+DEFINE_INT_RANGE_INSTANCE(255)
+DEFINE_INT_RANGE_GC_STUBS(1)
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 0a9dc6f151f..e3282c4ad03 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -1,5 +1,7 @@
/* Support routines for value ranges.
Copyright (C) 2019-2020 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <aldyh@redhat.com> and
+ Andrew Macleod <amacleod@redhat.com>.
This file is part of GCC.
@@ -20,7 +22,7 @@ along with GCC; see the file COPYING3. If not see
#ifndef GCC_VALUE_RANGE_H
#define GCC_VALUE_RANGE_H
-/* Types of value ranges. */
+// Types of value ranges.
enum value_range_kind
{
/* Empty range. */
@@ -36,164 +38,292 @@ enum value_range_kind
};
// Range of values that can be associated with an SSA_NAME.
+//
+// This is the base class without any storage.
-class GTY((for_user)) value_range
+class irange
{
public:
- value_range ();
- value_range (tree, tree, value_range_kind = VR_RANGE);
- value_range (tree type, const wide_int &, const wide_int &,
- value_range_kind = VR_RANGE);
- value_range (tree type);
-
+ // In-place setters.
void set (tree, tree, value_range_kind = VR_RANGE);
- void set (tree);
void set_nonzero (tree);
void set_zero (tree);
-
- enum value_range_kind kind () const;
- tree min () const;
- tree max () const;
-
- /* Types of value ranges. */
- bool symbolic_p () const;
- bool constant_p () const;
- bool undefined_p () const;
- bool varying_p () const;
void set_varying (tree type);
void set_undefined ();
- void union_ (const value_range *);
- void intersect (const value_range *);
- void union_ (const value_range &);
- void intersect (const value_range &);
-
- bool operator== (const value_range &) const;
- bool operator!= (const value_range &) const /* = delete */;
- bool equal_p (const value_range &) const;
-
- /* Misc methods. */
- tree type () const;
- bool may_contain_p (tree) const;
- bool zero_p () const;
- bool nonzero_p () const;
- bool singleton_p (tree *result = NULL) const;
- void dump (FILE *) const;
- void dump () const;
-
+ // Range types.
static bool supports_type_p (tree);
- void normalize_symbolics ();
- void normalize_addresses ();
+ tree type () const;
- static const unsigned int m_max_pairs = 2;
- bool contains_p (tree) const;
+ // Iteration over sub-ranges.
unsigned num_pairs () const;
wide_int lower_bound (unsigned = 0) const;
wide_int upper_bound (unsigned) const;
wide_int upper_bound () const;
+
+ // Predicates.
+ bool zero_p () const;
+ bool nonzero_p () const;
+ bool undefined_p () const;
+ bool varying_p () const;
+ bool singleton_p (tree *result = NULL) const;
+ bool contains_p (tree) const;
+
+ // In-place operators.
+ void union_ (const irange &);
+ void intersect (const irange &);
void invert ();
+ // Operator overloads.
+ irange& operator= (const irange &);
+ bool operator== (const irange &) const;
+ bool operator!= (const irange &r) const { return !(*this == r); }
+
+ // Misc methods.
+ void dump (FILE * = stderr) const;
+
+ // Deprecated legacy public methods.
+ enum value_range_kind kind () const; // DEPRECATED
+ tree min () const; // DEPRECATED
+ tree max () const; // DEPRECATED
+ bool symbolic_p () const; // DEPRECATED
+ bool constant_p () const; // DEPRECATED
+ void normalize_symbolics (); // DEPRECATED
+ void normalize_addresses (); // DEPRECATED
+ bool may_contain_p (tree) const; // DEPRECATED
+ void set (tree); // DEPRECATED
+ bool equal_p (const irange &) const; // DEPRECATED
+ void union_ (const class irange *); // DEPRECATED
+ void intersect (const irange *); // DEPRECATED
+
protected:
- void check ();
- static value_range union_helper (const value_range *, const value_range *);
- static value_range intersect_helper (const value_range *,
- const value_range *);
-
- friend void gt_ggc_mx_value_range (void *);
- friend void gt_pch_p_11value_range (void *, void *,
- gt_pointer_operator, void *);
- friend void gt_pch_nx_value_range (void *);
- friend void gt_ggc_mx (value_range &);
- friend void gt_ggc_mx (value_range *&);
- friend void gt_pch_nx (value_range &);
- friend void gt_pch_nx (value_range *, gt_pointer_operator, void *);
-
- enum value_range_kind m_kind;
- tree m_min;
- tree m_max;
+ irange (tree *, unsigned);
+ // potential promotion to public?
+ tree tree_lower_bound (unsigned = 0) const;
+ tree tree_upper_bound (unsigned) const;
+ tree tree_upper_bound () const;
+
+ // In-place operators.
+ void irange_union (const irange &);
+ void irange_intersect (const irange &);
+ void irange_set (tree, tree);
+ void irange_set_anti_range (tree, tree);
+
+ bool swap_out_of_order_endpoints (tree &min, tree &max, value_range_kind &);
+ bool normalize_min_max (tree type, tree min, tree max, value_range_kind);
+
+ bool legacy_mode_p () const;
+ bool legacy_equal_p (const irange &) const;
+ void legacy_union (irange *, const irange *);
+ void legacy_intersect (irange *, const irange *);
+ void verify_range ();
+ unsigned legacy_num_pairs () const;
+ wide_int legacy_lower_bound (unsigned = 0) const;
+ wide_int legacy_upper_bound (unsigned) const;
+ int value_inside_range (tree) const;
+ bool maybe_anti_range () const;
+ void copy_legacy_range (const irange &);
private:
- int value_inside_range (tree) const;
+ unsigned char m_num_ranges;
+ unsigned char m_max_ranges;
+ ENUM_BITFIELD(value_range_kind) m_kind : 8;
+ tree *m_base;
};
-extern bool range_has_numeric_bounds_p (const value_range *);
+// Here we describe an irange with N pairs of ranges. The storage for
+// the pairs is embedded in the class as an array.
+
+template<unsigned N>
+class GTY((user)) int_range : public irange
+{
+public:
+ int_range ();
+ int_range (tree, tree, value_range_kind = VR_RANGE);
+ int_range (tree type, const wide_int &, const wide_int &,
+ value_range_kind = VR_RANGE);
+ int_range (tree type);
+ int_range (const int_range &);
+ int_range (const irange &);
+ int_range& operator= (const int_range &);
+private:
+ template <unsigned X> friend void gt_ggc_mx (int_range<X> *);
+ template <unsigned X> friend void gt_pch_nx (int_range<X> *);
+ template <unsigned X> friend void gt_pch_nx (int_range<X> *,
+ gt_pointer_operator, void *);
+ // ?? hash-traits.h has its own extern for these, which is causing
+ // them to never be picked up by the templates. For now, define
+ // elsewhere.
+ //template<unsigned X> friend void gt_ggc_mx (int_range<X> *&);
+ //template<unsigned X> friend void gt_pch_nx (int_range<X> *&);
+ friend void gt_ggc_mx (int_range<1> *&);
+ friend void gt_pch_nx (int_range<1> *&);
+
+ tree m_ranges[N*2];
+};
+
+// This is a special int_range<1> with only one pair, plus
+// VR_ANTI_RANGE magic to describe slightly more than can be described
+// in one pair. It is described in the code as a "legacy range" (as
+// opposed to multi-ranges which have multiple sub-ranges). It is
+// provided for backward compatibility with code that has not been
+// converted to multi-range irange's.
+//
+// There are copy operators to seamlessly copy to/fro multi-ranges.
+typedef int_range<1> value_range;
+
+// This is an "infinite" precision irange for use in temporary
+// calculations.
+typedef int_range<255> widest_irange;
+
+// Returns true for an old-school value_range as described above.
+inline bool
+irange::legacy_mode_p () const
+{
+ return m_max_ranges == 1;
+}
+
+extern bool range_has_numeric_bounds_p (const irange *);
extern bool ranges_from_anti_range (const value_range *,
value_range *, value_range *);
-extern void dump_value_range (FILE *, const value_range *);
+extern void dump_value_range (FILE *, const irange *);
extern bool vrp_val_is_min (const_tree);
extern bool vrp_val_is_max (const_tree);
-extern tree vrp_val_min (const_tree);
-extern tree vrp_val_max (const_tree);
extern bool vrp_operand_equal_p (const_tree, const_tree);
-inline
-value_range::value_range ()
+inline value_range_kind
+irange::kind () const
+{
+ if (legacy_mode_p ())
+ return m_kind;
+
+ if (undefined_p ())
+ return VR_UNDEFINED;
+
+ if (varying_p ())
+ return VR_VARYING;
+
+ return VR_RANGE;
+}
+
+// Number of sub-ranges in a range.
+
+inline unsigned
+irange::num_pairs () const
{
- m_kind = VR_UNDEFINED;
- m_min = m_max = NULL;
+ if (!legacy_mode_p ())
+ return m_num_ranges;
+ else
+ return legacy_num_pairs ();
}
-inline value_range_kind
-value_range::kind () const
+inline tree
+irange::type () const
+{
+ gcc_checking_assert (!undefined_p ());
+ return TREE_TYPE (m_base[0]);
+}
+
+// Return the lower bound of a sub-range expressed as a tree. PAIR is
+// the sub-range in question.
+
+inline tree
+irange::tree_lower_bound (unsigned pair) const
+{
+ return m_base[pair * 2];
+}
+
+// Return the upper bound of a sub-range expressed as a tree. PAIR is
+// the sub-range in question.
+
+inline tree
+irange::tree_upper_bound (unsigned pair) const
{
- return m_kind;
+ return m_base[pair * 2 + 1];
}
+// Return the highest bound of a range expressed as a tree.
+
inline tree
-value_range::type () const
+irange::tree_upper_bound () const
{
- return TREE_TYPE (min ());
+ gcc_checking_assert (m_num_ranges);
+ return tree_upper_bound (m_num_ranges - 1);
}
inline tree
-value_range::min () const
+irange::min () const
{
- return m_min;
+ return tree_lower_bound (0);
}
inline tree
-value_range::max () const
+irange::max () const
{
- return m_max;
+ if (m_num_ranges)
+ return tree_upper_bound ();
+ else
+ return NULL;
}
inline bool
-value_range::varying_p () const
+irange::varying_p () const
{
- return m_kind == VR_VARYING;
+ if (legacy_mode_p ())
+ return m_kind == VR_VARYING;
+
+ if (m_num_ranges != 1)
+ return false;
+
+ tree l = m_base[0];
+ tree u = m_base[1];
+ tree t = TREE_TYPE (l);
+ if (INTEGRAL_TYPE_P (t))
+ return l == TYPE_MIN_VALUE (t) && u == TYPE_MAX_VALUE (t);
+ if (POINTER_TYPE_P (t))
+ return wi::to_wide (l) == 0
+ && wi::to_wide (u) == wi::max_value (TYPE_PRECISION (t),
+ TYPE_SIGN (t));
+ return true;
+
}
inline bool
-value_range::undefined_p () const
+irange::undefined_p () const
{
+ if (!legacy_mode_p ())
+ return m_num_ranges == 0;
+
+ if (CHECKING_P && legacy_mode_p ())
+ {
+ if (m_kind == VR_UNDEFINED)
+ gcc_checking_assert (m_num_ranges == 0);
+ else
+ gcc_checking_assert (m_num_ranges != 0);
+ }
return m_kind == VR_UNDEFINED;
}
inline bool
-value_range::zero_p () const
+irange::zero_p () const
{
- return (m_kind == VR_RANGE
- && integer_zerop (m_min)
- && integer_zerop (m_max));
+ return (m_kind == VR_RANGE && m_num_ranges == 1
+ && integer_zerop (tree_lower_bound (0))
+ && integer_zerop (tree_upper_bound (0)));
}
inline bool
-value_range::nonzero_p () const
+irange::nonzero_p () const
{
- if (m_kind == VR_ANTI_RANGE
- && !TYPE_UNSIGNED (type ())
- && integer_zerop (m_min)
- && integer_zerop (m_max))
- return true;
+ if (undefined_p ())
+ return false;
- return (m_kind == VR_RANGE
- && TYPE_UNSIGNED (type ())
- && integer_onep (m_min)
- && vrp_val_is_max (m_max));
+ tree zero = build_zero_cst (type ());
+ return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
}
inline bool
-value_range::supports_type_p (tree type)
+irange::supports_type_p (tree type)
{
if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
return type;
@@ -201,7 +331,7 @@ value_range::supports_type_p (tree type)
}
inline bool
-range_includes_zero_p (const value_range *vr)
+range_includes_zero_p (const irange *vr)
{
if (vr->undefined_p ())
return false;
@@ -212,4 +342,281 @@ range_includes_zero_p (const value_range *vr)
return vr->may_contain_p (build_zero_cst (vr->type ()));
}
+template<unsigned N>
+static inline void
+gt_ggc_mx (int_range<N> *x)
+{
+ for (unsigned i = 0; i < N; ++i)
+ {
+ gt_ggc_mx (x->m_ranges[i * 2]);
+ gt_ggc_mx (x->m_ranges[i * 2 + 1]);
+ }
+}
+
+template<unsigned N>
+static inline void
+gt_pch_nx (int_range<N> *x)
+{
+ for (unsigned i = 0; i < N; ++i)
+ {
+ gt_pch_nx (x->m_ranges[i * 2]);
+ gt_pch_nx (x->m_ranges[i * 2 + 1]);
+ }
+}
+
+template<unsigned N>
+static inline void
+gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
+{
+ for (unsigned i = 0; i < N; ++i)
+ {
+ op (&x->m_ranges[i * 2], cookie);
+ op (&x->m_ranges[i * 2 + 1], cookie);
+ }
+}
+
+// Constructors for irange
+
+inline
+irange::irange (tree *base, unsigned nranges)
+{
+ m_base = base;
+ m_num_ranges = 0;
+ m_max_ranges = nranges;
+ if (legacy_mode_p ())
+ m_kind = VR_UNDEFINED;
+ else
+ m_kind = VR_RANGE;
+}
+
+// Constructors for int_range<>.
+
+template<unsigned N>
+inline
+int_range<N>::int_range ()
+ : irange (m_ranges, N)
+{
+}
+
+template<unsigned N>
+int_range<N>::int_range (const int_range &other)
+ : irange (m_ranges, N)
+{
+ irange::operator= (other);
+}
+
+template<unsigned N>
+int_range<N>::int_range (tree min, tree max, value_range_kind kind)
+ : irange (m_ranges, N)
+{
+ irange::set (min, max, kind);
+}
+
+template<unsigned N>
+int_range<N>::int_range (tree type)
+ : irange (m_ranges, N)
+{
+ set_varying (type);
+}
+
+template<unsigned N>
+int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
+ value_range_kind kind)
+ : irange (m_ranges, N)
+{
+ tree min = wide_int_to_tree (type, wmin);
+ tree max = wide_int_to_tree (type, wmax);
+ set (min, max, kind);
+}
+
+template<unsigned N>
+int_range<N>::int_range (const irange &other)
+ : irange (m_ranges, N)
+{
+ irange::operator= (other);
+}
+
+template<unsigned N>
+int_range<N>&
+int_range<N>::operator= (const int_range &src)
+{
+ irange::operator= (src);
+ return *this;
+}
+
+inline void
+irange::set (tree val)
+{
+ set (val, val);
+}
+
+inline void
+irange::set_undefined ()
+{
+ m_num_ranges = 0;
+ if (legacy_mode_p ())
+ m_kind = VR_UNDEFINED;
+}
+
+inline void
+irange::set_varying (tree type)
+{
+ if (legacy_mode_p ())
+ m_kind = VR_VARYING;
+
+ m_num_ranges = 1;
+ if (INTEGRAL_TYPE_P (type))
+ {
+ m_base[0] = TYPE_MIN_VALUE (type);
+ m_base[1] = TYPE_MAX_VALUE (type);
+ }
+ else if (POINTER_TYPE_P (type))
+ {
+ m_base[0] = build_int_cst (type, 0);
+ m_base[1] = build_int_cst (type, -1);
+ }
+ else
+ m_base[0] = m_base[1] = error_mark_node;
+}
+
+inline bool
+irange::operator== (const irange &r) const
+{
+ return equal_p (r);
+}
+
+// Return the lower bound of a sub-range. PAIR is the sub-range in
+// question.
+
+inline wide_int
+irange::lower_bound (unsigned pair) const
+{
+ if (legacy_mode_p ())
+ return legacy_lower_bound (pair);
+ gcc_checking_assert (!undefined_p ());
+ gcc_checking_assert (pair + 1 <= num_pairs ());
+ return wi::to_wide (tree_lower_bound (pair));
+}
+
+// Return the upper bound of a sub-range. PAIR is the sub-range in
+// question.
+
+inline wide_int
+irange::upper_bound (unsigned pair) const
+{
+ if (legacy_mode_p ())
+ return legacy_upper_bound (pair);
+ gcc_checking_assert (!undefined_p ());
+ gcc_checking_assert (pair + 1 <= num_pairs ());
+ return wi::to_wide (tree_upper_bound (pair));
+}
+
+// Return the highest bound of a range.
+
+inline wide_int
+irange::upper_bound () const
+{
+ unsigned pairs = num_pairs ();
+ gcc_checking_assert (pairs > 0);
+ return upper_bound (pairs - 1);
+}
+
+inline void
+irange::union_ (const irange &r)
+{
+ dump_flags_t m_flags = dump_flags;
+ dump_flags &= ~TDF_DETAILS;
+ irange::union_ (&r);
+ dump_flags = m_flags;
+}
+
+inline void
+irange::intersect (const irange &r)
+{
+ dump_flags_t m_flags = dump_flags;
+ dump_flags &= ~TDF_DETAILS;
+ irange::intersect (&r);
+ dump_flags = m_flags;
+}
+
+// Set value range VR to a nonzero range of type TYPE.
+
+inline void
+irange::set_nonzero (tree type)
+{
+ tree zero = build_int_cst (type, 0);
+ if (legacy_mode_p ())
+ set (zero, zero, VR_ANTI_RANGE);
+ else
+ irange_set_anti_range (zero, zero);
+}
+
+// Set value range VR to a ZERO range of type TYPE.
+
+inline void
+irange::set_zero (tree type)
+{
+ tree z = build_int_cst (type, 0);
+ if (legacy_mode_p ())
+ set (z);
+ else
+ irange_set (z, z);
+}
+
+// Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+//
+// Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
+// restrict those to a subset of what actually fits in the type.
+// Instead use the extremes of the type precision which will allow
+// compare_range_with_value() to check if a value is inside a range,
+// whereas if we used TYPE_*_VAL, said function would just punt upon
+// seeing a VARYING.
+
+inline bool
+irange::normalize_min_max (tree type, tree min, tree max,
+ value_range_kind kind)
+{
+ unsigned prec = TYPE_PRECISION (type);
+ signop sign = TYPE_SIGN (type);
+ if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
+ && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
+ {
+ if (kind == VR_RANGE)
+ set_varying (type);
+ else if (kind == VR_ANTI_RANGE)
+ set_undefined ();
+ else
+ gcc_unreachable ();
+ return true;
+ }
+ return false;
+}
+
+// Return the maximum value for TYPE.
+
+inline tree
+vrp_val_max (const_tree type)
+{
+ if (INTEGRAL_TYPE_P (type))
+ return TYPE_MAX_VALUE (type);
+ if (POINTER_TYPE_P (type))
+ {
+ wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+ return wide_int_to_tree (const_cast<tree> (type), max);
+ }
+ return NULL_TREE;
+}
+
+// Return the minimum value for TYPE.
+
+inline tree
+vrp_val_min (const_tree type)
+{
+ if (INTEGRAL_TYPE_P (type))
+ return TYPE_MIN_VALUE (type);
+ if (POINTER_TYPE_P (type))
+ return build_zero_cst (const_cast<tree> (type));
+ return NULL_TREE;
+}
+
#endif // GCC_VALUE_RANGE_H
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index d0303599002..609375c072e 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -92,7 +92,8 @@ vr_values::get_lattice_entry (const_tree var)
return vr;
/* Create a default value range. */
- vr_value[ver] = vr = vrp_value_range_pool.allocate ();
+ vr = new (vrp_value_range_pool.allocate ()) value_range_equiv;
+ vr_value[ver] = vr;
/* After propagation finished return varying. */
if (values_propagated)
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic