tree-optimization/106922 - missed FRE/PRE

The following enhances the store-with-same-value trick in
vn_reference_lookup_3 by not only looking for

  a = val;
  *ptr = val;
  .. = a;

but also

  *ptr = val;
  other = x;
  .. = a;

where the earlier store is more than one hop away.  It does this
by queueing the actual value to compare until after the walk but
as disadvantage only allows a single such skipped store from a
constant value.

Unfortunately we cannot handle defs from non-constants this way
since we're prone to pick up values from the past loop iteration
this way and we have no good way to identify values that are
invariant in the currently iterated cycle.  That's why we keep
the single-hop lookup for those cases.  gcc.dg/tree-ssa/pr87126.c
would be a testcase that's un-XFAILed when we'd handle those
as well.

	PR tree-optimization/106922
	* tree-ssa-sccvn.cc (vn_walk_cb_data::same_val): New member.
	(vn_walk_cb_data::finish): Perform delayed verification of
	a skipped may-alias.
	(vn_reference_lookup_pieces): Likewise.
	(vn_reference_lookup): Likewise.
	(vn_reference_lookup_3): When skipping stores of the same
	value also handle constant stores that are more than a
	single VDEF away by delaying the verification.

	* gcc.dg/tree-ssa/ssa-fre-100.c: New testcase.
	* g++.dg/tree-ssa/pr106922.C: Adjust.

2 files changed, 26 insertions, 2 deletions

diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr106922.C b/gcc/testsuite/g++.dg/tree-ssa/pr106922.C
index faf379b..14fa061 100644
--- a/gcc/testsuite/g++.dg/tree-ssa/pr106922.C
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr106922.C
@@ -87,5 +87,4 @@ void testfunctionfoo() {
   }
 }
 
-// { dg-final { scan-tree-dump-times "Found fully redundant value" 4 "pre" { xfail { ! lp64 } } } }
-// { dg-final { scan-tree-dump-not "m_initialized" "cddce3" { xfail { ! lp64 } } } }
+// { dg-final { scan-tree-dump-not "m_initialized" "dce3" } }
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-100.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-100.c
new file mode 100644
index 0000000..ead7654
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-100.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+float bar, baz;
+void foo (int *p, int n)
+{
+  *p = 0;
+  do
+    {
+      bar = 1.;
+      /* When iterating we should have optimistically value-numbered
+	 *p to zero, on the second iteration we have to prove the
+	 store below does not affect the value of this load though.
+	 We can compare the stored value against the value from the
+	 previous iteration instead relying on a non-walking lookup.  */
+      if (*p)
+        {
+          baz = 2.;
+          *p = 0;
+        }
+    }
+  while (--n);
+}
+
+/* { dg-final { scan-tree-dump-not "baz" "fre1" } } */