A load from a constant array at an unknown index unions every element
of its initializer, and adds zero if the initializer has fewer
elements than the array. We currently do this by counting, ignoring
position. My next patch will need to know where the missing elements
are, so this patch changes the approach to a walk instead of a count.
We cap initializers at 32 elements by default (--param
vrp-cstload-limit), so there's no penalty for doing the walk. For
that matter, the whole patch series is a wash in compile time
performance.
Tested on ppc64le Linux, including Ada for the swapped ranges test.
No assembly changes over a corpus of .ii files from a stage1
bootstrap.
Pushed.
gcc/ChangeLog:
* gimple-range-fold.cc
(ctor_ref_range::accumulate_range_from_array_ref): Walk the
initializer by index to find the elements it leaves out.
gcc/testsuite/ChangeLog:
* g++.dg/tree-ssa/vrp-from-cst-agg-1.C: New test.
* gcc.dg/tree-ssa/vrp-from-cst-agg-9.c: New test.
* gnat.dg/opt111.adb: New test.
---
gcc/gimple-range-fold.cc | 57 ++++++++++++++++---
.../g++.dg/tree-ssa/vrp-from-cst-agg-1.C | 22 +++++++
.../gcc.dg/tree-ssa/vrp-from-cst-agg-9.c | 27 +++++++++
gcc/testsuite/gnat.dg/opt111.adb | 28 +++++++++
4 files changed, 126 insertions(+), 8 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/tree-ssa/vrp-from-cst-agg-1.C
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-9.c
create mode 100644 gcc/testsuite/gnat.dg/opt111.adb
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index f567df891c8..554bb4e122c 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -1124,7 +1124,9 @@ ctor_ref_range::accumulate_range_from_component_ref (tree
init, unsigned i,
// static const int t[2] = { 4, 5 };
//
// INIT is { 4, 5 } and I is 1, the end of the path. For t[1] the range is
-// [5, 5] and for t[n] it is [4, 5].
+// [5, 5] and for t[n] it is [4, 5]. When every element is loaded, whatever
+// the initializer leaves out reads as zero: take each element's indices out
+// of the domain to see if anything is left.
bool
ctor_ref_range::accumulate_range_from_array_ref (tree init, unsigned i,
@@ -1154,16 +1156,53 @@ ctor_ref_range::accumulate_range_from_array_ref (tree
init, unsigned i,
|| !tree_fits_uhwi_p (TYPE_MIN_VALUE (domain))
|| !tree_fits_uhwi_p (TYPE_MAX_VALUE (domain)))
return false;
- unsigned HOST_WIDE_INT needed_count
- = (tree_to_uhwi (TYPE_MAX_VALUE (domain))
- - tree_to_uhwi (TYPE_MIN_VALUE (domain)) + 1);
- if (CONSTRUCTOR_NELTS (init) < needed_count)
- accumulate_range_from_missing_constructor_elt ();
+ // Unsigned bounds that look reversed are signed, as they are for
+ // get_array_ctor_element_at_index: Ada's -1 .. 5 has a lower bound of
+ // SIZE_MAX.
+ tree type = TREE_TYPE (TYPE_MIN_VALUE (domain));
+ if (TYPE_UNSIGNED (type)
+ && tree_int_cst_lt (TYPE_MAX_VALUE (domain), TYPE_MIN_VALUE (domain)))
+ type = signed_type_for (type);
+ wide_int min = wi::to_wide (TYPE_MIN_VALUE (domain));
+ wide_int max = wi::to_wide (TYPE_MAX_VALUE (domain));
+
+ // Ada represents an empty array with reversed bounds.
+ if (wi::gt_p (min, max, TYPE_SIGN (type)))
+ return true;
+
+ unsigned prec = TYPE_PRECISION (type);
+ int_range_max missing (type, min, max);
+ wide_int next = missing.lower_bound ();
unsigned ix;
- tree val;
- FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), ix, val)
+ tree index, val;
+
+ // Build a range with the entire domain, and take out any elements which are
+ // initialized. If there's anything left in that range, it means there are
+ // missing elements and we should add a [0, 0] to the final range.
+ FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), ix, index, val)
{
+ wide_int lo, hi;
+
+ // A null index means the element follows the previous one.
+ if (!index)
+ lo = hi = next;
+ else if (TREE_CODE (index) == RANGE_EXPR)
+ {
+ lo = wi::to_wide (TREE_OPERAND (index, 0), prec);
+ hi = wi::to_wide (TREE_OPERAND (index, 1), prec);
+ }
+ else
+ {
+ gcc_checking_assert (TREE_CODE (index) == INTEGER_CST);
+ lo = hi = wi::to_wide (index, prec);
+ }
+ // A RAW_DATA_CST holds one element per byte.
+ if (TREE_CODE (val) == RAW_DATA_CST)
+ hi = wi::add (hi, RAW_DATA_LENGTH (val) - 1);
+ 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. */
@@ -1171,6 +1210,8 @@ ctor_ref_range::accumulate_range_from_array_ref (tree
init, unsigned i,
return false;
}
+ if (!missing.undefined_p ())
+ accumulate_range_from_missing_constructor_elt ();
return true;
}
diff --git a/gcc/testsuite/g++.dg/tree-ssa/vrp-from-cst-agg-1.C
b/gcc/testsuite/g++.dg/tree-ssa/vrp-from-cst-agg-1.C
new file mode 100644
index 00000000000..07d2618871d
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/vrp-from-cst-agg-1.C
@@ -0,0 +1,22 @@
+// { dg-do compile { target c++14 } }
+// { dg-options "-O2 -fdump-tree-optimized" }
+
+// The elements of t after the first share one initializer, { 0, 3 }, under
+// a RANGE_EXPR: the two elements of its constructor cover all eight of the
+// array, so no load reads a zero from an element left out.
+
+struct S { int a; int b = 3; };
+static const S t[8] = { { 1, 2 } };
+
+void link_error ();
+
+int
+foo (unsigned i)
+{
+ int v = t[i].b;
+ if (v != 2 && v != 3)
+ link_error ();
+ return v;
+}
+
+// { dg-final { scan-tree-dump-not "link_error" "optimized" } }
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-9.c
b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-9.c
new file mode 100644
index 00000000000..c06a12a80f3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-9.c
@@ -0,0 +1,27 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+/* The initializer leaves out the elements at 0, 1, 3 and 4, and those
+ from 6 on: all read as zero, so whatever the index the load is 0, 5
+ or 9. */
+
+void link_error (void);
+
+static const int tbl[8] = { [2] = 5, [5] = 9 };
+
+[[gnu::noipa]] int
+foo (int i)
+{
+ int v = tbl[i];
+ if (v != 0 && v != 5 && v != 9)
+ link_error ();
+ return v == 0;
+}
+
+int
+main (void)
+{
+ if (!foo (0) || foo (2) || foo (5) || !foo (7))
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gnat.dg/opt111.adb b/gcc/testsuite/gnat.dg/opt111.adb
new file mode 100644
index 00000000000..8a4da47fd4d
--- /dev/null
+++ b/gcc/testsuite/gnat.dg/opt111.adb
@@ -0,0 +1,28 @@
+-- { dg-do run }
+-- { dg-options "-O2" }
+
+-- The domain of an array with a negative lower bound has unsigned bounds
+-- that look reversed. Loads from it are not loads from an empty array.
+
+procedure Opt111 is
+
+ type Arr is array (-1 .. 5) of Integer;
+ T : constant Arr := (11, 12, 13, 14, 15, 16, 17);
+
+ function G (I : Integer; C : Boolean) return Integer;
+ pragma No_Inline (G);
+
+ function G (I : Integer; C : Boolean) return Integer is
+ R : Integer := 0;
+ begin
+ if C then
+ R := T (I);
+ end if;
+ return R;
+ end;
+
+begin
+ if G (-1, True) /= 11 or else G (5, True) /= 17 then
+ raise Program_Error;
+ end if;
+end;
--
2.53.0
