[4.2 regression]: Fix symptoms for PR 32327

[Diego Novillo <dnovillo at google dot com>]

This bug exposes a bad interaction between code motion passes (in this
case store sinking) and stack slot sharing.  When we assign locals to
stack slots, we do not consider variables in different lexical scopes to
conflict.  However, in GIMPLE there are no lexical scopes, so code
motion may move variables out of their original lexical scope.

This is what is happening in this case, a store to a stack variable
(dest) is moved out of its original lexical scope and stack slot sharing
makes it share the same stack slot with another stack variable (norder):

  norder = __r.__ll;		<--	In stack slot #8
  norder.13 = (char *) &norder;
  dest = n.100;			<--	In stack slot #8
  foo (norder.13);
  return;

The assignment to 'dest' kills the value we had computed for 'norder',
causing the test to fail.  In this particular case, there was a
secondary problem: variable 'dest' does not really need to live on the
stack.  It is not addressable, but we never notice that.  So, I was able
to mask the problem by fixing this alias inefficiency.

What is happening is that we fold memcpy() to a straight assignment, but
we fail to promote the addressable variables to registers.
Later on, store sinking comes along and sinks the store 'dest = n.100'
to the very unfortunate place where we store the result from bswap,
causing grief.

I am of two minds wrt the real fix,  These are the two alternatives that
I am considering.

1- Stack slot sharing ought to be taking lifetime into consideration.
It only assumes that two symbols in different lexical scopes cannot be
live at the same time, so it happily puts them in the same place.

Given that GIMPLE only has a single lexical scope, this is a dangerous
view.  However, it is certainly reasonable from the point of view of the
original program.  A symbol shouldn't really be live outside of its
lexical scope.


2- Store sinking ought to limit itself to not moving stores out of their
original lexical scope.  We have shied away from limiting passes this
way.  One could argue that this would limit stack slot pressure (which
is in some cases a big problem), but we would then be (a) tying our
language-independent framework to the vagaries of the input language,
and (b) the burden of dealing with lexical scopes inside code motion can
be quite extensive.

I am leaning heavily towards #1.  I do not think #2 is going to be
feasible nor easy to maintain.

In the meantime, the attached patch masks the problem.  This is
obviously not a huge problem for now, but as more code motion passes
come along, it will get worse.  As a minor side-effect,
this patch should promote more memory symbols to registers, which is
always a good thing.  I will not close the PR just yet, the real fix for
it is option #1, I think.

Andrew, any thoughts on how we could use the live-range information you
collect during out-of-ssa to help the stack sharing code?  We do
stack-sharing during expansion (cfgexpand.c:expand_used_vars).  We'd
want to export enough live-range information so that the expander didn't
have to rely on lexical blocks to do its own partitioning.

This patch is still undergoing testing.  I will commit to 4.2 after
testing has finished.


Thanks.

2007-06-15  Diego Novillo  <dnovillo@google.com>

	PR 32327
	* tree-ssa-operands.c (build_ssa_operands): Initially assume
	that the statement does not take any addresses.
 

testsuite/ChangeLog

	PR 32327
	* g++.dg/tree-ssa/pr32327-1.C: New test.
	* g++.dg/tree-ssa/pr32327.C: New test.

Index: testsuite/g++.dg/tree-ssa/pr32327-1.C
===================================================================
--- testsuite/g++.dg/tree-ssa/pr32327-1.C	(revision 0)
+++ testsuite/g++.dg/tree-ssa/pr32327-1.C	(revision 0)
@@ -0,0 +1,70 @@
+// { dg-do run { target { { i?86-*-* x86_64-*-* } && ilp32 } } }
+// { dg-options "-O2" }
+
+// Endian sensitive.  This is a little-endian redux.
+
+typedef long long int64;
+typedef unsigned long long uint64;
+typedef __SIZE_TYPE__ size_t;
+
+extern "C" {
+extern void *memcpy (void *__restrict __dest,
+      __const void *__restrict __src, size_t __n) /*throw ()*/;
+extern void abort (void);
+}
+
+inline uint64 Swap64(uint64 ull) {
+ uint64 b0 = (ull >>  0) & 0xff;
+ uint64 b1 = (ull >>  8) & 0xff;
+ uint64 b2 = (ull >> 16) & 0xff;
+ uint64 b3 = (ull >> 24) & 0xff;
+ uint64 b4 = (ull >> 32) & 0xff;
+ uint64 b5 = (ull >> 40) & 0xff;
+ uint64 b6 = (ull >> 48) & 0xff;
+ uint64 b7 = (ull >> 56) & 0xff;
+ return (b0 << 56) | (b1 << 48) | (b2 << 40) | (b3 << 32) |
+        (b4 << 24) | (b5 << 16) | (b6 <<  8) | (b7 <<  0);
+}
+
+inline void KeyFromUint64(uint64 ull, unsigned char* key) {
+ uint64 ull_swap = Swap64(ull);
+ memcpy(key, &ull_swap, sizeof(uint64));
+}
+
+inline int64 int64_from_double(const double& source) {
+ int64 dest;
+ memcpy(&dest, &source, sizeof(dest));
+ return dest;
+}
+
+void KeyFromDouble(double x, unsigned char* key) __attribute__ ((noinline));
+void KeyFromDouble(double x, unsigned char* key) {
+ int64 n = int64_from_double(x);
+ if (n >= 0) {
+   n += 1ull << 63;
+ } else {
+   n = -n;
+ }
+ KeyFromUint64(n, key);
+}
+
+
+void TestKeyFromDouble(uint64 ull) {
+ double d;
+ memcpy(&d, &ull, sizeof(d));
+
+ unsigned char key[sizeof(uint64)];
+ unsigned char expected_key[sizeof(uint64)] = { 0x81, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef };
+
+ KeyFromDouble(d, key);
+
+ for (size_t i = 0; i < sizeof(key); ++i) {
+   if ((key[i] & 0xff) != expected_key[i])
+     abort ();
+ }
+}
+
+int main() {
+ TestKeyFromDouble(0x0123456789abcdefull);
+ return 0;
+}
Index: testsuite/g++.dg/tree-ssa/pr32327.C
===================================================================
--- testsuite/g++.dg/tree-ssa/pr32327.C	(revision 0)
+++ testsuite/g++.dg/tree-ssa/pr32327.C	(revision 0)
@@ -0,0 +1,84 @@
+// { dg-do run { target { { i?86-*-* x86_64-*-* } && ilp32 } } }
+// { dg-options "-O2" }
+
+typedef unsigned long long uint64;
+typedef __SIZE_TYPE__ size_t;
+
+extern "C" {
+extern void *memcpy (void *__restrict __dest,
+      __const void *__restrict __src, size_t __n) /*throw ()*/;
+extern void abort (void);
+}
+
+extern void foo (void* p);
+
+inline uint64
+ghtonll(uint64 x)
+{
+ // __r is allocated the same stack slot as dest below
+ union { unsigned long long int __ll;
+         unsigned long int __l[2]; } __w, __r;
+ __w.__ll = x;
+ __r.__l[0] = (
+   {
+     register unsigned int __v;
+     __asm__ __volatile__ ("bswap %0" : "=r" (__v) :
+                           "0" ((unsigned int) (__w.__l[1])));
+     __v; });
+
+ __r.__l[1] = (
+   {
+     register unsigned int __v;
+     __asm__ __volatile__ ("bswap %0" : "=r" (__v) :
+                           "0" ((unsigned int) (__w.__l[0])));
+     __v; });
+
+ return __r.__ll;
+}
+
+inline uint64
+double_2_uint64 (const double *source)
+{
+ uint64 dest;  // allocated the same stack slot as __r above
+ memcpy(&dest, source, sizeof(dest));
+ return dest;
+}
+
+inline void
+KeyFromUint64(uint64 fp) {
+ uint64 norder;
+ norder = ghtonll (fp);
+ foo((char*)(&norder));
+}
+
+void
+KeyFromDouble(double x) {
+ uint64 n = double_2_uint64 (&x);
+ if (n >= 42) {
+   n += 1;
+ }
+
+ KeyFromUint64(n);
+}
+
+#define NUM		0x0123456789abcdefll
+#define EXPECTED	0xe0bc9a7856347243ll
+
+void foo (void *x)
+{
+  if (*((uint64 *)x) != (uint64) EXPECTED)
+    abort ();
+}
+
+int main ()
+{
+  if (sizeof (double) != sizeof (uint64))
+    return 0;
+
+  if (sizeof (uint64) == sizeof (unsigned long int))
+    return 0;
+
+  KeyFromDouble ((double)NUM);
+
+  return 0;
+}
Index: tree-ssa-operands.c
===================================================================
--- tree-ssa-operands.c	(revision 125683)
+++ tree-ssa-operands.c	(working copy)
@@ -2162,9 +2162,14 @@ build_ssa_operands (tree stmt)
 {
   stmt_ann_t ann = get_stmt_ann (stmt);
   
-  /* Initially assume that the statement has no volatile operands.  */
+  /* Initially assume that the statement has no volatile operands and
+     does not take the address of any symbols.  */
   if (ann)
-    ann->has_volatile_ops = false;
+    {
+      ann->has_volatile_ops = false;
+      if (ann->addresses_taken)
+	ann->addresses_taken = NULL;
+    }
 
   start_ssa_stmt_operands ();