If-conversion optimization

Extends the instruction selection pass with an if-conversion optimization:
some if/then/else statements are converted into "select" operations,
which in turn can be compiled down to branchless instruction sequences
if the target architecture supports them.

The statements that are converted are of the form

        if (cond) { x = a1; } else { x = a2; }
        if (cond) { x = a1; }
        if (cond) { /*skip*/; } else { x = a2; }

where a1, a2 are "safe" expressions, containing no operations that can
fail at run-time, such as memory loads or integer divisions.

A heuristic in backend/Selectionaux.ml controls when the optimization occurs,
depending on command-line flags and the complexity of the "then" and "else"
branches.

3 files changed, 156 insertions, 1 deletions

diff --git a/test/regression/Makefile b/test/regression/Makefile
index 760ee570..e5b0655e 100644
--- a/test/regression/Makefile
+++ b/test/regression/Makefile
@@ -16,7 +16,7 @@ TESTS=int32 int64 floats floats-basics \
   funct3 expr5 struct7 struct8 struct11 struct12 casts1 casts2 char1 \
   sizeof1 sizeof2 binops bool for1 for2 switch switch2 compound \
   decl1 interop1 bitfields9 ptrs3 \
-  parsing krfun
+  parsing krfun ifconv
 
 # Can run, but only in compiled mode, and have reference output in Results
 
diff --git a/test/regression/Results/ifconv b/test/regression/Results/ifconv
new file mode 100644
index 00000000..38019fe6
--- /dev/null
+++ b/test/regression/Results/ifconv
@@ -0,0 +1,26 @@
+test1(0,1,12,34) = 12
+test1(1,0,45,67) = 67
+test2(0,1,12,34) = 12
+test2(1,0,45,67) = 67
+test3(0,1,12,34) = 12
+test3(1,0,45,67) = 67
+test4(0,1,12,34) = 12
+test4(1,0,45,67) = 67
+test5(0,1,12) = 13
+test5(1,0,45) = 44
+test6(NULL) = 0
+test6(&i) = 1244
+test7(1,0) = -1
+test7(-100,4) = -25
+test8(0) = 0
+test8(1) = -72
+ltest1(-1, 0, 123LL, 456LL) = 124
+ltest1(1, 0, 123LL, 456LL) = 114
+dmax(0.0, 3.14) = 3.140000
+dmax(1.0, -2.718) = 1.000000
+dabs(1.0) = 1.000000
+dabs(-2.718) = 2.718000
+smin(0.0, 3.14) = 0.000000
+smin(1.0, -2.718) = -2.718000
+sdoz(1.0, 0.5) = 0.500000
+sdoz(0.0, 3.14) = 0.000000
diff --git a/test/regression/ifconv.c b/test/regression/ifconv.c
new file mode 100644
index 00000000..dcbf43e5
--- /dev/null
+++ b/test/regression/ifconv.c
@@ -0,0 +1,129 @@
+#include <stdio.h>
+
+/* Several equivalent forms that should be turned into cmov */
+
+int test1(int x, int y, int a, int b)
+{
+  return x < y ? a : b;
+}
+
+int test2(int x, int y, int a, int b)
+{
+  int r;
+  if (x < y) { r = a; } else { r = b; }
+  return r;
+}
+
+int test3(int x, int y, int a, int b)
+{
+  int r = b;
+  if (x < y) { r = a; }
+  return r;
+}
+
+int test4(int x, int y, int a, int b)
+{
+  int r = a;
+  if (x < y) { /*skip*/; } else { r = b; }
+  return r;
+}
+
+/* A more advanced example */
+
+int test5(int x, int y, int a)
+{
+  return x < y ? a + 1 : a - 1;
+}
+
+/* Unsafe operations should not be turned into cmov */
+
+int test6(int * p)
+{
+  return p == NULL ? 0 : *p + 10;
+}
+
+int test7(int a, int b)
+{
+  return b == 0 ? -1 : a / b;
+}
+
+/* Very large operations should not be turned into cmov */
+
+int test8(int a)
+{
+  return a == 0 ? 0 : a*a*a*a - 2*a*a*a + 10*a*a + 42*a - 123;
+}
+
+/* Some examples with 64-bit integers */
+
+long long ltest1(int x, int y, long long a, long long b)
+{
+  return x < y ? a + 1 : b >> 2;
+}
+
+/* Some examples with floating-point */
+
+double dmax(double x, double y)
+{
+  return x >= y ? x : y;
+}
+
+double dabs(double x)
+{
+  return x < 0.0 ? -x : x;
+}
+
+float smin(float x, float y)
+{
+  return x <= y ? x : y;
+}
+
+float sdoz(float x, float y)
+{
+  return x >= y ? x - y : 0.0f;
+}
+
+/* Test harness */
+
+#define TESTI(call) printf(#call " = %d\n", call)
+#define TESTL(call) printf(#call " = %lld\n", call)
+#define TESTF(call) printf(#call " = %f\n", call)
+
+
+int main()
+{
+  int i = 1234;
+  TESTI(test1(0,1,12,34));
+  TESTI(test1(1,0,45,67));
+  TESTI(test2(0,1,12,34));
+  TESTI(test2(1,0,45,67));
+  TESTI(test3(0,1,12,34));
+  TESTI(test3(1,0,45,67));
+  TESTI(test4(0,1,12,34));
+  TESTI(test4(1,0,45,67));
+  TESTI(test5(0,1,12));
+  TESTI(test5(1,0,45));
+  TESTI(test6(NULL));
+  TESTI(test6(&i));
+  TESTI(test7(1,0));
+  TESTI(test7(-100,4));
+  TESTI(test8(0));
+  TESTI(test8(1));
+
+  TESTL(ltest1(-1, 0, 123LL, 456LL));
+  TESTL(ltest1(1, 0, 123LL, 456LL));
+
+  TESTF(dmax(0.0, 3.14));
+  TESTF(dmax(1.0, -2.718));
+
+  TESTF(dabs(1.0));
+  TESTF(dabs(-2.718));
+
+  TESTF(smin(0.0, 3.14));
+  TESTF(smin(1.0, -2.718));
+
+  TESTF(sdoz(1.0, 0.5));
+  TESTF(sdoz(0.0, 3.14));
+
+  return 0;
+}