Subzero: Strength-reduce mul by certain constants.
These all appear to some degree in spec2k.
This is implemented for i8/i16/i32 types. It is done as part of core lowering, so in theory all optimization levels could benefit, but it is explicitly disabled for Om1/O0 to keep things simple there.
While clang appears to strength-reduce udiv/urem by a constant power of 2, for some reason it does not always strength-reduce multiplies (given that they appear in the spec2k bitcode).
For multiplies by 3, 5, or 9, we can make use of the lea instruction. We can do combinations of shift and lea to multiply by other constants, e.g. 100=5*5*4. If too many operations would be required, just give up and use the mul instruction.
BUG= https://code.google.com/p/nativeclient/issues/detail?id=4095
R=jpp@chromium.org, jvoung@chromium.org
Review URL: https://codereview.chromium.org/1146803002
diff --git a/crosstest/crosstest.cfg b/crosstest/crosstest.cfg
index 2222b90..620edb6 100644
--- a/crosstest/crosstest.cfg
+++ b/crosstest/crosstest.cfg
@@ -42,6 +42,13 @@
driver: test_stacksave_main.c
test: test_stacksave.c
+[test_strengthreduce]
+driver: test_strengthreduce_main.cpp
+test: test_strengthreduce.cpp
+# Disable clang-side optimizations so that pnacl-sz sees suitable
+# bitcode patterns.
+flags: --clang-opt=0
+
[test_sync_atomic]
driver: test_sync_atomic_main.cpp
# Compile the non-Subzero object files straight from source since the native
diff --git a/crosstest/test_strengthreduce.cpp b/crosstest/test_strengthreduce.cpp
new file mode 100644
index 0000000..b6be659
--- /dev/null
+++ b/crosstest/test_strengthreduce.cpp
@@ -0,0 +1,30 @@
+//===- subzero/crosstest/test_strengthreduce.cpp - Strength reduction -----===//
+//
+// The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation for crosstesting strength reduction.
+//
+//===----------------------------------------------------------------------===//
+
+#include "test_strengthreduce.h"
+
+// TODO(stichnot): Extend to i16 and i8 types, and also test the
+// commutativity transformations. This may require hand-generating
+// .ll files, because of C/C++ integer promotion rules for arithmetic,
+// and because clang prefers to do its own commutativity
+// transformation.
+
+#define X(constant, suffix) \
+ uint32_t multiplyByConst##suffix(uint32_t Val) { \
+ return Val * (uint32_t)constant; \
+ } \
+ int32_t multiplyByConst##suffix(int32_t Val) { \
+ return Val * (int32_t)constant; \
+ }
+CONST_TABLE
+#undef X
diff --git a/crosstest/test_strengthreduce.def b/crosstest/test_strengthreduce.def
new file mode 100644
index 0000000..a65437c
--- /dev/null
+++ b/crosstest/test_strengthreduce.def
@@ -0,0 +1,38 @@
+//===- subzero/crosstest/test_strengthreduce.def - macros -----*- C++ -*---===//
+//
+// The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines macros for crosstesting strength reduction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef TEST_STRENGTHREDUCE_DEF
+#define TEST_STRENGTHREDUCE_DEF
+
+#define XSTR(s) STR(s)
+#define STR(s) #s
+
+#define CONST_TABLE \
+ X( -10, _10) \
+ X( -7, _7) \
+ X( -2, _2) \
+ X( -1, _1) \
+ X( 0, 0) \
+ X( 1, 1) \
+ X( 2, 2) \
+ X( 3, 3) \
+ X( 4, 4) \
+ X( 5, 5) \
+ X( 7, 7) \
+ X( 9, 9) \
+ X( 10, 10) \
+ X( 100, 100) \
+ X(100000, 100000) \
+//#define X(constant, suffix)
+
+#endif // !TEST_STRENGTHREDUCE_DEF
diff --git a/crosstest/test_strengthreduce.h b/crosstest/test_strengthreduce.h
new file mode 100644
index 0000000..309eef9
--- /dev/null
+++ b/crosstest/test_strengthreduce.h
@@ -0,0 +1,23 @@
+//===- subzero/crosstest/test_strengthreduce.h - Prototypes ---*- C++ -*---===//
+//
+// The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares the function prototypes used for crosstesting strength
+// reduction.
+//
+//===----------------------------------------------------------------------===//
+
+#include <stdint.h>
+
+#include "test_strengthreduce.def"
+
+#define X(constant, suffix) \
+ uint32_t multiplyByConst##suffix(uint32_t val); \
+ int32_t multiplyByConst##suffix(int32_t val);
+CONST_TABLE
+#undef X
diff --git a/crosstest/test_strengthreduce_main.cpp b/crosstest/test_strengthreduce_main.cpp
new file mode 100644
index 0000000..2c2aa98
--- /dev/null
+++ b/crosstest/test_strengthreduce_main.cpp
@@ -0,0 +1,65 @@
+//===- subzero/crosstest/test_strengthreduce_main.cpp - Driver for tests --===//
+//
+// The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Driver for crosstesting arithmetic strength-reducing optimizations.
+//
+//===----------------------------------------------------------------------===//
+
+/* crosstest.py --test=test_strengthreduce.cpp \
+ --driver=test_strengthreduce_main.cpp \
+ --prefix=Subzero_ --clang-opt=0 --output=test_strengthreduce */
+
+#include <iostream>
+
+// Include test_strengthreduce.h twice - once normally, and once
+// within the Subzero_ namespace, corresponding to the llc and Subzero
+// translated object files, respectively.
+#include "test_strengthreduce.h"
+namespace Subzero_ {
+#include "test_strengthreduce.h"
+}
+
+int main(int argc, char **argv) {
+ size_t TotalTests = 0;
+ size_t Passes = 0;
+ size_t Failures = 0;
+ static int32_t Values[] = {-100, -50, 0, 1, 8, 123, 0x33333333, 0x77777777};
+ for (size_t i = 0; i < sizeof(Values) / sizeof(*Values); ++i) {
+ int32_t SVal = Values[i];
+ int32_t ResultLlcS, ResultSzS;
+ uint32_t UVal = (uint32_t)Values[i];
+ int32_t ResultLlcU, ResultSzU;
+
+#define X(constant, suffix) \
+ ResultLlcS = multiplyByConst##suffix(UVal); \
+ ResultSzS = Subzero_::multiplyByConst##suffix(UVal); \
+ if (ResultLlcS == ResultSzS) { \
+ ++Passes; \
+ } else { \
+ ++Failures; \
+ std::cout << "multiplyByConstS" STR(suffix) "(" << SVal \
+ << "): sz=" << ResultSzS << " llc=" << ResultLlcS << "\n"; \
+ } \
+ ResultLlcU = multiplyByConst##suffix(UVal); \
+ ResultSzU = Subzero_::multiplyByConst##suffix(UVal); \
+ if (ResultLlcU == ResultSzU) { \
+ ++Passes; \
+ } else { \
+ ++Failures; \
+ std::cout << "multiplyByConstU" STR(suffix) "(" << UVal \
+ << "): sz=" << ResultSzU << " llc=" << ResultLlcU << "\n"; \
+ }
+ CONST_TABLE
+#undef X
+ }
+
+ std::cout << "TotalTests=" << TotalTests << " Passes=" << Passes
+ << " Failures=" << Failures << "\n";
+ return Failures;
+}
