Currently a load from a constant table gets the range of the whole
table, no matter what is known of its index. For example, with
static const int tbl[4] = { 0, 5, 6, 7 };
and i in [0, 1], tbl[i] is currently [0, 0][5, 7]. With this patch we
get [0, 0][5, 5].
This work comes from my DOM parity obsession, but goes beyond what DOM
gets here. DOM folds a load from a constant table only when the index
can be determined to be a constant, as on the path through i = 1 in:
if (c)
i = 1;
if (tbl[i] == 5)
With this patch we also narrow a load whose index is in a range:
if (i < 2 && tbl[i] > 5)
tbl[i] is [0, 0][5, 5], and we can fold the comparison away.
This implements the following TODO in the code:
/* TODO: If the array index in the expr is an SSA_NAME with a known
range, we could use just values loaded from the corresponding array
elements. */
Oh, and we no longer have to special case INTEGER_CSTs, as ranger
happily handles those.
I've also added a testcase for r17-4029-g7dab38c9d7104e, a phiopt
tweak which couldn't be properly tested until now.
Tested on ppc64le Linux.
Pushed.
gcc/ChangeLog:
* gimple-range-fold.cc (intersects_p): New.
(class ctor_ref_range): Add SRC.
(ctor_ref_range::accumulate_range_from_array_ref): Load only from
the elements the range of the index reaches, a constant index
included.
(fold_using_range::fold_stmt): Pass the source to
range_from_readonly_var.
(fold_using_range::range_from_readonly_var): Add SRC.
* gimple-range-fold.h (fold_using_range::range_from_readonly_var):
Adjust.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/phi-opt-52.c: New test.
* gcc.dg/tree-ssa/vrp-from-cst-agg-10.c: New test.
* gcc.dg/tree-ssa/vrp-from-cst-agg-11.c: New test.
* gcc.dg/tree-ssa/vrp-from-cst-agg-13.c: New test.
---
gcc/gimple-range-fold.cc | 61 ++++++++++---------
gcc/gimple-range-fold.h | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c | 38 ++++++++++++
.../gcc.dg/tree-ssa/vrp-from-cst-agg-10.c | 46 ++++++++++++++
.../gcc.dg/tree-ssa/vrp-from-cst-agg-11.c | 27 ++++++++
.../gcc.dg/tree-ssa/vrp-from-cst-agg-13.c | 19 ++++++
6 files changed, 163 insertions(+), 30 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-10.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-11.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-13.c
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 554bb4e122c..9ac5a94341c 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -687,7 +687,7 @@ fold_using_range::fold_stmt (vrange &r, gimple *s,
fur_source &src, tree name)
name = gimple_get_lhs (s);
// Process addresses and loads from static constructors.
- if (gimple_code (s) == GIMPLE_ASSIGN && range_from_readonly_var (r, s))
+ if (gimple_code (s) == GIMPLE_ASSIGN && range_from_readonly_var (r, s, src))
return true;
// Save the current range query and restore it before returning.
@@ -992,6 +992,16 @@ fold_using_range::range_of_address (prange &r, gimple
*stmt, fur_source &src)
return true;
}
+// Does R contain anything in [LO, HI]?
+
+static bool
+intersects_p (const irange &r, const wide_int &lo, const wide_int &hi)
+{
+ int_range_max tmp (r);
+ tmp.intersect (int_range<1> (r.type (), lo, hi));
+ return !tmp.undefined_p ();
+}
+
// The range of a load from a read-only aggregate: walk its initializer along
// the component path of the reference, COMPONENT_PATH, from the aggregate out,
// unioning into R the constants the load can reach. For example:
@@ -1006,8 +1016,10 @@ fold_using_range::range_of_address (prange &r, gimple
*stmt, fur_source &src)
class ctor_ref_range
{
public:
- ctor_ref_range (vrange &r, tree type, const vec<tree> &component_path)
- : m_r (r), m_type (type), m_component_path (component_path) { }
+ ctor_ref_range (vrange &r, tree type, const vec<tree> &component_path,
+ fur_source &src)
+ : m_r (r), m_type (type), m_component_path (component_path),
+ m_src (src) { }
bool accumulate_range (tree init, unsigned i);
private:
bool accumulate_range_from_scalar (tree init);
@@ -1018,6 +1030,7 @@ private:
vrange &m_r;
tree m_type;
const vec<tree> &m_component_path;
+ fur_source &m_src;
};
// Accumulate the range of the load from INIT, the initializer reached after
@@ -1132,24 +1145,6 @@ bool
ctor_ref_range::accumulate_range_from_array_ref (tree init, unsigned i,
tree idx)
{
- if (TREE_CODE (idx) == INTEGER_CST)
- {
- unsigned ctor_idx;
- tree val = get_array_ctor_element_at_index (init, wi::to_offset (idx),
- &ctor_idx);
- if (!val)
- {
- // An index the initializer skips over, like t[1] of
- // static const int t[4] = { [2] = 5 };
- // is not read as zero, unlike one past its end.
- if (ctor_idx < CONSTRUCTOR_NELTS (init))
- return false;
- accumulate_range_from_missing_constructor_elt ();
- return true;
- }
- return accumulate_range (val, i);
- }
-
tree domain = TYPE_DOMAIN (TREE_TYPE (init));
if (!TYPE_MIN_VALUE (domain)
|| !TYPE_MAX_VALUE (domain)
@@ -1172,8 +1167,18 @@ ctor_ref_range::accumulate_range_from_array_ref (tree
init, unsigned i,
return true;
unsigned prec = TYPE_PRECISION (type);
- int_range_max missing (type, min, max);
- wide_int next = missing.lower_bound ();
+ int_range<1> domain_r (type, min, max);
+
+ // Narrow IDX to the ranges it can actually take.
+ int_range_max idx_r;
+ m_src.get_operand (idx_r, idx);
+ range_cast (idx_r, type);
+ idx_r.intersect (domain_r);
+ if (idx_r.undefined_p ())
+ return false;
+
+ int_range_max missing (idx_r);
+ wide_int next = domain_r.lower_bound ();
unsigned ix;
tree index, val;
@@ -1203,10 +1208,7 @@ ctor_ref_range::accumulate_range_from_array_ref (tree
init, unsigned i,
missing.intersect (int_range<2> (type, lo, hi, VR_ANTI_RANGE));
next = wi::add (hi, 1);
- /* TODO: If the array index in the expr is an SSA_NAME with a known
- range, we could use just values loaded from the corresponding array
- elements. */
- if (!accumulate_range (val, i))
+ if (intersects_p (idx_r, lo, hi) && !accumulate_range (val, i))
return false;
}
@@ -1234,7 +1236,8 @@
ctor_ref_range::accumulate_range_from_missing_constructor_elt ()
// false and leave R untouched.
bool
-fold_using_range::range_from_readonly_var (vrange &r, gimple *stmt)
+fold_using_range::range_from_readonly_var (vrange &r, gimple *stmt,
+ fur_source &src)
{
gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
tree type = TREE_TYPE (gimple_assign_lhs (stmt));
@@ -1279,7 +1282,7 @@ fold_using_range::range_from_readonly_var (vrange &r,
gimple *stmt)
return false;
value_range tmp (type);
- ctor_ref_range load (tmp, type, component_path);
+ ctor_ref_range load (tmp, type, component_path, src);
bool res = load.accumulate_range (ctor, 0) && !tmp.varying_p ();
if (res)
r = tmp;
diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h
index bf4310847e4..0cf14cf90dd 100644
--- a/gcc/gimple-range-fold.h
+++ b/gcc/gimple-range-fold.h
@@ -181,7 +181,7 @@ protected:
bool range_of_call (vrange &r, gcall *call, fur_source &src);
bool range_of_cond_expr (vrange &r, gassign* cond, fur_source &src);
bool range_of_address (prange &r, gimple *s, fur_source &src);
- bool range_from_readonly_var (vrange &r, gimple *stmt);
+ bool range_from_readonly_var (vrange &r, gimple *stmt, fur_source &src);
bool range_of_phi (vrange &r, gphi *phi, fur_source &src);
void range_of_ssa_name_with_loop_info (vrange &, tree, class loop *, gphi *,
fur_source &src);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c
new file mode 100644
index 00000000000..583b32ba72c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c
@@ -0,0 +1,38 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+/* The range of the load of sa[i].a under i < 2 is [1, 3]. Once it is
+ hoisted above the condition, that range must not fold the later
+ sa[i].a > 3.
+
+ This is the testcase for r17-4029-g7dab38c9d7104e ("phiopt: clear the
+ range info of hoisted adjacent loads"), which could not be exercised
+ until now. */
+
+struct S { int a, b; };
+static const struct S sa[4] = { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };
+volatile int vol;
+
+__attribute__((noipa)) int
+f (int i)
+{
+ int r;
+ if (i < 2)
+ r = sa[i].a;
+ else
+ r = sa[i].b;
+ /* Enough statements that the merge block is not worth threading. */
+ vol; vol; vol; vol; vol; vol; vol; vol;
+ vol; vol; vol; vol; vol; vol; vol; vol;
+ if (sa[i].a > 3)
+ return 100 + r;
+ return r;
+}
+
+int
+main ()
+{
+ if (f (0) != 1 || f (1) != 3 || f (2) != 106 || f (3) != 108)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-10.c
b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-10.c
new file mode 100644
index 00000000000..e329f59259f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-10.c
@@ -0,0 +1,46 @@
+/* { dg-do link } */
+/* { dg-options "-O2 -fgimple" } */
+
+/* This is:
+
+ if (i < 2 && tbl[i] > 5)
+ link_error ();
+
+ The index is [0, 1] so the range for v_3 should be [0, 0][5, 5]. */
+
+static const int tbl[4] = { 0, 5, 6, 7 };
+
+void link_error (void);
+
+[[gnu::noipa]] void __GIMPLE (ssa,startwith("evrp"))
+foo (unsigned int i)
+{
+ int v;
+
+ __BB(2):
+ if (i_2(D) < 2u)
+ goto __BB3;
+ else
+ goto __BB5;
+
+ __BB(3):
+ v_3 = tbl[i_2(D)];
+ if (v_3 > 5)
+ goto __BB4;
+ else
+ goto __BB5;
+
+ __BB(4):
+ link_error ();
+ goto __BB5;
+
+ __BB(5):
+ return;
+}
+
+int
+main (void)
+{
+ foo (0);
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-11.c
b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-11.c
new file mode 100644
index 00000000000..425981f1f21
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-11.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgimple -fdump-tree-evrp" } */
+
+/* The index is [0, 2] so the range for v_3 should be [0, 0][5, 5]. */
+
+static const int tbl[8] = { [2] = 5, [5] = 9 };
+
+int __GIMPLE (ssa,startwith("evrp"))
+foo (unsigned int i)
+{
+ int v;
+
+ __BB(2):
+ if (i_2(D) > 2u)
+ goto __BB4;
+ else
+ goto __BB3;
+
+ __BB(3):
+ v_3 = tbl[i_2(D)];
+ return v_3;
+
+ __BB(4):
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "v_3 = .irange. int .0, 0..5, 5.\n" "evrp" } }
*/
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-13.c
b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-13.c
new file mode 100644
index 00000000000..2ead51b33ec
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-13.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgimple -fdump-tree-evrp" } */
+
+/* The index is unknown so the range for v_3 should be [0, 0][7, 7]. */
+
+static const struct { int a; int b[4]; } tbl[2]
+ = { { 1, { [3] = 5 } }, { 2, { 6, 7, 8, 9 } } };
+
+int __GIMPLE (ssa,startwith("evrp"))
+foo (int i)
+{
+ int v;
+
+ __BB(2):
+ v_3 = tbl[i_2(D)].b[1];
+ return v_3;
+}
+
+/* { dg-final { scan-tree-dump "v_3 = .irange. int .0, 0..7, 7.\n" "evrp" } }
*/
--
2.53.0
