Lower stacksave and restore intrinsics.

crosstest/test_stacksave.c

Index: crosstest/test_stacksave.c
diff --git a/crosstest/test_stacksave.c b/crosstest/test_stacksave.c
new file mode 100644
index 0000000000000000000000000000000000000000..343ab8195a3ffddb1cfcb97e39af47ccd6b6e8ce
--- /dev/null
+++ b/crosstest/test_stacksave.c
@@ -0,0 +1,86 @@
+//===- subzero/crosstest/test_stacksave.c - Implementation for tests ------===//
+//
+//                        The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This aims to test that C99's VLAs (which use stacksave/stackrestore
+// intrinsics) work fine.
+//
+//===----------------------------------------------------------------------===//
+
+#include <stdint.h>
+
+#include "test_stacksave.h"
+DECLARE_TESTS()
+
+/* NOTE: This has 0 stacksaves, because the vla isn't in a loop,
+ * so the vla can just be freed by the epilogue.
+ */
+uint32_t test_basic_vla(uint32_t size, uint32_t start, uint32_t inc) {
+  uint32_t vla[size];
+  uint32_t mid = start + ((size - start) / 2);
+  for (uint32_t i = start; i < size; ++i) {
+    vla[i] = i + inc;
+  }
+  return (vla[start] << 2) + (vla[mid] << 1) + vla[size - 1];
+}
+
+/* NOTE: This has 1 stacksaves, because the vla is in a loop and should

[Jim Stichnoth, 2014/07/17 16:47:25]

stacksave :)

[jvoung (off chromium), 2014/07/17 20:34:51]

Done.

+ * be freed before the next iteration.
+ */
+uint32_t test_vla_in_loop(uint32_t size, uint32_t start, uint32_t inc) {
+  uint32_t saved_start = 0;
+  uint32_t saved_mid = 0;
+  uint32_t saved_last = 0;
+  uint32_t mid = start + ((size - start) / 2);
+  for (uint32_t i = start; i < size; ++i) {
+    uint32_t vla[size];

[Jim Stichnoth, 2014/07/17 16:47:25]

It seems to me that a smart compiler could optimize vla[] out entirely.

Also, it seems like the vla[] definition could legitimately be hoisted out of
the loop and you'd be back to the basic vla.

If the vla size were a function of the loop iteration variable, it would be much
harder to hoist.

[jvoung (off chromium), 2014/07/17 20:34:51]

Done.

The compiler did some optimization indeed. It didn't hoist it out, so still had
the stacksave/restore.  However, the compiler noticed the sampling of array
indices and it did optimized out the alloca and computed 3 numbers instead.

Made it touch every entry instead, and made the number sequence a bit more
complicated. I've certainly seen LLVM collapse two nested loops into constant
time operation.

The later function was a bit less optimized, but it also optimized out vla1's
alloca. Adjusted that too.

+    vla[i] = i + inc;
+    if (i == start)
+      saved_start = vla[i];
+    if (i == mid)
+      saved_mid = vla[i];
+    if (i == size - 1)
+      saved_last = vla[i];
+  }
+  return (saved_start << 2) + (saved_mid << 1) + saved_last;
+}
+
+static uint32_t __attribute__((noinline)) foo(uint32_t x) {
+  return x * x;
+}
+
+uint32_t test_two_vlas_in_loops(uint32_t size, uint32_t start, uint32_t inc) {
+  uint32_t saved_start = 0;
+  uint32_t saved_mid = 0;
+  uint32_t saved_last = 0;
+  uint32_t mid = start + ((size - start) / 2);
+  for (uint32_t i = start; i < size; ++i) {
+    uint32_t vla1[size];
+    uint32_t x = 0;
+    for (uint32_t j = i; j < size; j++) {
+      uint32_t size2 = size - j;
+      uint32_t start2 = 0;
+      uint32_t mid2 = size2 / 2;
+      uint32_t vla2[size2];
+      for (uint32_t k = start2; k < size2; k++) {
+        /* Adjust stack again with a function call. */
+        uint32_t x = foo(inc);
+        vla2[k] = k + x;
+      }
+      x = (vla2[start2] << 2) + (vla2[mid2] << 1) + vla2[size2 - 1];
+    }
+    vla1[i] = x;
+    if (i == start)
+      saved_start = vla1[i];
+    if (i == mid)
+      saved_mid = vla1[i];
+    if (i == size - 1)
+      saved_last = vla1[i];
+  }
+  return (saved_start << 2) + (saved_mid << 1) + saved_last;
+}