From: Kyrylo Tkachov <[email protected]>
If-conversion can expose separate comparisons for a predicate and its
inverse. Value number selects using an available inverse comparison
with exchanged arms. This also exposes equivalent scalar selects to
CSE and lets their users simplify in the same VN pass.
For example, with finite-math assumptions:
p = x < y;
a = p ? v1 : v2;
q = x >= y;
b = q ? v2 : v1;
r = a ^ b;
becomes:
r = 0;
Look up the exchanged COND_EXPR in visit_nary_op. If no equivalent
select exists, use an available same-block inverse to build its value
number. Prefer the lower comparison code for this new expression,
including after VN operand canonicalization, to keep the choice stable.
Extend the existing insertion code to materialize COND_EXPR after
checking availability of all three operands.
Use invert_tree_comparison for NaN semantics. Keep a nontrapping guard
because EQ/NE inversion can be valid even when signaling NaNs can trap.
Reusing a later comparison must not move an earlier trap past a side effect.
This removes one comparison and one mask copy from each hot vector loop
in miniBUDE 20210901 on Neoverse V2 and Olympus.
Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill
gcc/ChangeLog:
* tree-ssa-sccvn.cc (visit_nary_op): Value number selects using
inverse comparisons and exchanged arms.
(eliminate_dom_walker::eliminate_insert): Handle COND_EXPR.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/fre-inverse-compare-1.c: New test.
* gcc.dg/tree-ssa/fre-inverse-compare-2.c: Likewise.
* gcc.dg/tree-ssa/fre-inverse-compare-3.c: Likewise.
* gcc.dg/tree-ssa/ifc-cmp-inverse-1.c: Likewise.
* gcc.dg/tree-ssa/ifc-cmp-inverse-2.c: Likewise.
* gcc.dg/tree-ssa/ifc-cmp-inverse-3.c: Likewise.
* gcc.dg/tree-ssa/ifc-cmp-inverse-4.c: Likewise.
* gcc.dg/tree-ssa/ifc-cmp-inverse-5.c: Likewise.
* gcc.dg/tree-ssa/ifc-cmp-inverse-6.c: Likewise.
* gcc.dg/tree-ssa/ifc-cmp-inverse-7.c: Likewise.
* gcc.dg/tree-ssa/ifc-cmp-inverse-8.c: Likewise.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
.../gcc.dg/tree-ssa/fre-inverse-compare-1.c | 46 ++++++++++
.../gcc.dg/tree-ssa/fre-inverse-compare-2.c | 26 ++++++
.../gcc.dg/tree-ssa/fre-inverse-compare-3.c | 65 ++++++++++++++
.../gcc.dg/tree-ssa/ifc-cmp-inverse-1.c | 35 ++++++++
.../gcc.dg/tree-ssa/ifc-cmp-inverse-2.c | 33 +++++++
.../gcc.dg/tree-ssa/ifc-cmp-inverse-3.c | 34 ++++++++
.../gcc.dg/tree-ssa/ifc-cmp-inverse-4.c | 83 ++++++++++++++++++
.../gcc.dg/tree-ssa/ifc-cmp-inverse-5.c | 60 +++++++++++++
.../gcc.dg/tree-ssa/ifc-cmp-inverse-6.c | 69 +++++++++++++++
.../gcc.dg/tree-ssa/ifc-cmp-inverse-7.c | 57 ++++++++++++
.../gcc.dg/tree-ssa/ifc-cmp-inverse-8.c | 62 +++++++++++++
gcc/tree-ssa-sccvn.cc | 87 +++++++++++++++++++
12 files changed, 657 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-4.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-5.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-6.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-7.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-8.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-1.c
new file mode 100644
index 00000000000..e986bc350f7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-1.c
@@ -0,0 +1,46 @@
+/* { dg-do compile } */
+/* { dg-options "-fgimple -O2 -ffinite-math-only -fno-trapping-math
-fdump-tree-fre1 -fdump-tree-optimized" } */
+
+/* Reuse the available inverse comparison and swap the select arms. */
+
+int __GIMPLE (ssa,startwith("fre1"))
+scalar_select (float x, float y, int a, int b, int c, int d)
+{
+ _Bool p;
+ _Bool q;
+ int t;
+ int u;
+ int r;
+
+ __BB(2):
+ p_7 = x_1(D) < y_2(D);
+ t_8 = p_7 ? a_3(D) : b_4(D);
+ q_9 = x_1(D) >= y_2(D);
+ u_10 = q_9 ? c_5(D) : d_6(D);
+ r_11 = t_8 + u_10;
+ return r_11;
+}
+
+/* Operand canonicalization must not make each select prefer the other's
+ comparison. Keep the available comparison with reversed operands. */
+
+int __GIMPLE (ssa,startwith("fre1"))
+reversed_select (float x, float y, int a, int b, int c, int d)
+{
+ _Bool p;
+ _Bool q;
+ int t;
+ int u;
+ int r;
+
+ __BB(2):
+ q_7 = y_2(D) > x_1(D);
+ t_8 = q_7 ? a_3(D) : b_4(D);
+ p_9 = x_1(D) >= y_2(D);
+ u_10 = p_9 ? c_5(D) : d_6(D);
+ r_11 = t_8 + u_10;
+ return r_11;
+}
+
+/* { dg-final { scan-tree-dump-times {= [pq]_7 \? d_6\(D\) : c_5\(D\);} 2
"fre1" } } */
+/* { dg-final { scan-tree-dump-not { >= } "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-2.c
new file mode 100644
index 00000000000..7b72aa3b126
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-2.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-fgimple -O2 -ftrapping-math -fsignaling-nans
-fdump-tree-fre1" } */
+
+volatile int marker;
+
+int __GIMPLE (ssa,startwith("fre1"))
+compare (float x, float y, int a, int b, int c, int d)
+{
+ _Bool p;
+ _Bool q;
+ int t;
+ int u;
+ int r;
+
+ __BB(2):
+ p_7 = x_1(D) != y_2(D);
+ marker = 1;
+ q_8 = x_1(D) == y_2(D);
+ t_9 = q_8 ? a_3(D) : b_4(D);
+ u_10 = p_7 ? c_5(D) : d_6(D);
+ r_11 = t_9 + u_10;
+ return r_11;
+}
+
+/* The earlier comparison must remain a condition of its select. */
+/* { dg-final { scan-tree-dump {u_10 = p_7 \? c_5\(D\) : d_6\(D\);} "fre1" } }
*/
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-3.c
new file mode 100644
index 00000000000..0c6a1a068d8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/fre-inverse-compare-3.c
@@ -0,0 +1,65 @@
+/* { dg-do compile } */
+/* { dg-options "-fgimple -O2 -ffinite-math-only -fno-trapping-math
-fdump-tree-fre1" } */
+
+/* Equivalent selects must have the same value number, so their users
+ can also be simplified during the same FRE pass. */
+
+int __GIMPLE (ssa,startwith("fre1"))
+equivalent_selects (float x, float y, int a, int b)
+{
+ _Bool p;
+ _Bool q;
+ int t;
+ int u;
+ int r;
+
+ __BB(2):
+ p_5 = x_1(D) < y_2(D);
+ t_6 = p_5 ? a_3(D) : b_4(D);
+ q_7 = x_1(D) >= y_2(D);
+ u_8 = q_7 ? b_4(D) : a_3(D);
+ r_9 = t_6 ^ u_8;
+ return r_9;
+}
+
+/* The inverse lookup must also accept reversed comparison operands. */
+
+int __GIMPLE (ssa,startwith("fre1"))
+reversed_operands (float x, float y, int a, int b)
+{
+ _Bool p;
+ _Bool q;
+ int t;
+ int u;
+ int r;
+
+ __BB(2):
+ p_5 = y_2(D) > x_1(D);
+ t_6 = p_5 ? a_3(D) : b_4(D);
+ q_7 = x_1(D) >= y_2(D);
+ u_8 = q_7 ? b_4(D) : a_3(D);
+ r_9 = t_6 ^ u_8;
+ return r_9;
+}
+
+/* Find the same redundancy when the opposite select occurs first. */
+
+int __GIMPLE (ssa,startwith("fre1"))
+reversed_order (float x, float y, int a, int b)
+{
+ _Bool p;
+ _Bool q;
+ int t;
+ int u;
+ int r;
+
+ __BB(2):
+ q_5 = x_1(D) >= y_2(D);
+ t_6 = q_5 ? b_4(D) : a_3(D);
+ p_7 = y_2(D) > x_1(D);
+ u_8 = p_7 ? a_3(D) : b_4(D);
+ r_9 = t_6 ^ u_8;
+ return r_9;
+}
+
+/* { dg-final { scan-tree-dump-times {return 0;} 3 "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-1.c
new file mode 100644
index 00000000000..8d291d0b789
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-1.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-Ofast -fdump-tree-ifcvt" } */
+
+/* The two merge points are predicated on DISTBB < 0 and on DISTBB >= 0.
+ With NaNs out of the way the second predicate is the inverse of the
+ first, so if-conversion has to reuse it with the arms of the select
+ swapped instead of emitting a second comparison. */
+
+void
+f (float *restrict etot, const float *restrict lx, float radij, float r_radij,
+ float elcdst, float elcdst1, float distdslv, float r_distdslv,
+ float chrg_init, float dslv_init, int n)
+{
+ for (int l = 0; l < n; l++)
+ {
+ float distij = lx[l];
+ float distbb = distij - radij;
+ int zone1 = distbb < 0.f;
+
+ etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
+
+ float chrg_e = chrg_init
+ * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
+ * (distbb < elcdst ? 1.f : 0.f));
+ etot[l] += chrg_e * 45.f;
+
+ float coeff = 1.f - distbb * r_distdslv;
+ float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
+ dslv_e *= distbb >= 0.f ? coeff : 1.f;
+ etot[l] += dslv_e;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times {= \S+ < 0\.0;} 1 "ifcvt" } } */
+/* { dg-final { scan-tree-dump-not {= \S+ >= 0\.0;} "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-2.c
new file mode 100644
index 00000000000..76eef5bf586
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-2.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-Ofast -fno-finite-math-only -fdump-tree-ifcvt" } */
+
+/* Same kernel as ifc-cmp-inverse-1.c. With NaNs honoured DISTBB >= 0 is
+ not the inverse of DISTBB < 0, so both comparisons have to stay. */
+
+void
+f (float *restrict etot, const float *restrict lx, float radij, float r_radij,
+ float elcdst, float elcdst1, float distdslv, float r_distdslv,
+ float chrg_init, float dslv_init, int n)
+{
+ for (int l = 0; l < n; l++)
+ {
+ float distij = lx[l];
+ float distbb = distij - radij;
+ int zone1 = distbb < 0.f;
+
+ etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
+
+ float chrg_e = chrg_init
+ * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
+ * (distbb < elcdst ? 1.f : 0.f));
+ etot[l] += chrg_e * 45.f;
+
+ float coeff = 1.f - distbb * r_distdslv;
+ float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
+ dslv_e *= distbb >= 0.f ? coeff : 1.f;
+ etot[l] += dslv_e;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times {= \S+ < 0\.0;} 1 "ifcvt" } } */
+/* { dg-final { scan-tree-dump-times {= \S+ >= 0\.0;} 1 "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-3.c
new file mode 100644
index 00000000000..022aa52fd26
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-3.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-Ofast -fno-finite-math-only -fdump-tree-ifcvt" } */
+
+/* When the source spells the second test as the arms of a select, GCC
+ builds the else predicate as DISTBB u>= 0, which is the inverse of
+ DISTBB < 0 even with NaNs honoured, so one comparison is enough. */
+
+void
+f (float *restrict etot, const float *restrict lx, float radij, float r_radij,
+ float elcdst, float elcdst1, float distdslv, float r_distdslv,
+ float chrg_init, float dslv_init, int n)
+{
+ for (int l = 0; l < n; l++)
+ {
+ float distij = lx[l];
+ float distbb = distij - radij;
+ int zone1 = distbb < 0.f;
+
+ etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
+
+ float chrg_e = chrg_init
+ * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
+ * (distbb < elcdst ? 1.f : 0.f));
+ etot[l] += chrg_e * 45.f;
+
+ float coeff = 1.f - distbb * r_distdslv;
+ float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
+ dslv_e *= zone1 ? 1.f : coeff;
+ etot[l] += dslv_e;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times {= \S+ < 0\.0;} 1 "ifcvt" } } */
+/* { dg-final { scan-tree-dump-not {= \S+ u>= 0\.0;} "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-4.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-4.c
new file mode 100644
index 00000000000..867a7381a96
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-4.c
@@ -0,0 +1,83 @@
+/* { dg-do run } */
+/* { dg-options "-Ofast" } */
+
+/* Swapping the arms of a select and testing the inverse predicate has to
+ pick the same value. Every input and every intermediate value here is a
+ small integer, so the result does not depend on the order in which the
+ fast-math flags let the compiler evaluate the expression. */
+
+#define N 41
+
+static float lx[N], etot[N], ref[N];
+
+__attribute__ ((noipa))
+static void
+kernel (float *restrict etot, const float *restrict lx, float radij,
+ float r_radij, float elcdst, float elcdst1, float distdslv,
+ float r_distdslv, float chrg_init, float dslv_init, int n)
+{
+ for (int l = 0; l < n; l++)
+ {
+ float distij = lx[l];
+ float distbb = distij - radij;
+ int zone1 = distbb < 0.f;
+
+ etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
+
+ float chrg_e = chrg_init
+ * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
+ * (distbb < elcdst ? 1.f : 0.f));
+ etot[l] += chrg_e * 45.f;
+
+ float coeff = 1.f - distbb * r_distdslv;
+ float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
+ dslv_e *= distbb >= 0.f ? coeff : 1.f;
+ etot[l] += dslv_e;
+ }
+}
+
+__attribute__ ((noipa, optimize ("O0")))
+static void
+reference (float *restrict etot, const float *restrict lx, float radij,
+ float r_radij, float elcdst, float elcdst1, float distdslv,
+ float r_distdslv, float chrg_init, float dslv_init, int n)
+{
+ for (int l = 0; l < n; l++)
+ {
+ float distij = lx[l];
+ float distbb = distij - radij;
+ int zone1 = distbb < 0.f;
+
+ etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
+
+ float chrg_e = chrg_init
+ * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
+ * (distbb < elcdst ? 1.f : 0.f));
+ etot[l] += chrg_e * 45.f;
+
+ float coeff = 1.f - distbb * r_distdslv;
+ float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
+ dslv_e *= distbb >= 0.f ? coeff : 1.f;
+ etot[l] += dslv_e;
+ }
+}
+
+int
+main (void)
+{
+ for (int i = 0; i < N; i++)
+ {
+ lx[i] = i - N / 2;
+ etot[i] = i & 3;
+ ref[i] = etot[i];
+ }
+
+ kernel (etot, lx, 3.f, 2.f, 5.f, 1.f, 4.f, 2.f, 3.f, 2.f, N);
+ reference (ref, lx, 3.f, 2.f, 5.f, 1.f, 4.f, 2.f, 3.f, 2.f, N);
+
+ for (int i = 0; i < N; i++)
+ if (etot[i] != ref[i])
+ __builtin_abort ();
+
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-5.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-5.c
new file mode 100644
index 00000000000..2b624516c0f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-5.c
@@ -0,0 +1,60 @@
+/* { dg-do run } */
+/* { dg-options "-O3 -ffast-math -fno-ssa-phiopt" } */
+
+/* Factoring the first select removes a comparison that can be an inverse
+ predicate for the second select. */
+
+__attribute__ ((noipa))
+static void
+kernel (float *restrict out, const float *restrict in, float z, int n)
+{
+ for (int i = 0; i < n; ++i)
+ {
+ float x = in[i * 3];
+ float y = in[i * 3 + 1];
+ float w = in[i * 3 + 2];
+ int p;
+ if (x < 0)
+ p = y < z;
+ else
+ p = w < z;
+ out[i * 2] = p;
+ float q;
+ if (y >= z)
+ q = x * 3 + 1;
+ else
+ q = x * 2 - 1;
+ out[i * 2 + 1] = q;
+ }
+}
+
+__attribute__ ((noipa, optimize ("O0")))
+static void
+check (const float *out, const float *in, float z, int n)
+{
+ for (int i = 0; i < n; ++i)
+ {
+ float x = in[i * 3];
+ float y = in[i * 3 + 1];
+ float w = in[i * 3 + 2];
+ float p = x < 0 ? y < z : w < z;
+ float q = y >= z ? x * 3 + 1 : x * 2 - 1;
+ if (out[i * 2] != p || out[i * 2 + 1] != q)
+ __builtin_abort ();
+ }
+}
+
+int
+main (void)
+{
+ float in[3 * 257], out[2 * 257];
+ for (int i = 0; i < 3 * 257; ++i)
+ in[i] = (i * 13 % 41) - 20;
+ for (int n = 0; n <= 257; ++n)
+ for (int z = -2; z <= 2; ++z)
+ {
+ kernel (out, in, z, n);
+ check (out, in, z, n);
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-6.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-6.c
new file mode 100644
index 00000000000..f1431e88d2d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-6.c
@@ -0,0 +1,69 @@
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-trapping-math -fno-ssa-phiopt" } */
+/* { dg-require-effective-target flt_dbl_ldbl_inf_nan } */
+
+/* Ordered comparisons are not complementary for unordered operands.
+ Check inverse and reversed comparisons in nested loop predicates. */
+
+#define N 81
+static float a[N], b[N];
+static int out[N * 4];
+
+__attribute__ ((noipa))
+static void
+kernel (int *restrict out, const float *restrict a,
+ const float *restrict b, int n)
+{
+ for (int i = 0; i < n; ++i)
+ {
+ float x = a[i], y = b[i];
+ out[4 * i] = x < y ? 11 : 29;
+ out[4 * i + 1] = x >= y ? 31 : 47;
+ out[4 * i + 2] = !(x < y) ? 53 : 71;
+ int r;
+ if (y <= x)
+ r = x == y ? 73 : 89;
+ else
+ r = x != y ? 97 : 101;
+ out[4 * i + 3] = r;
+ }
+}
+
+int
+main (void)
+{
+ float values[9] = { -__builtin_inff (), -2.0f, -0.0f, 0.0f, 2.0f,
+ __builtin_inff (), __builtin_nanf (""),
+ -__builtin_nanf (""), 1.0f };
+ /* Equal ranks denote equal values. Rank 4 denotes unordered values. */
+ int rank[9] = { -3, -2, 0, 0, 2, 3, 4, 4, 1 };
+ for (int i = 0; i < N; ++i)
+ {
+ a[i] = values[i / 9];
+ b[i] = values[i % 9];
+ }
+ for (int n = 0; n <= N; ++n)
+ {
+ for (int i = 0; i < N * 4; ++i)
+ out[i] = -1;
+ kernel (out, a, b, n);
+ for (int i = 0; i < n; ++i)
+ {
+ int x = rank[i / 9], y = rank[i % 9];
+ int ordered = x != 4 && y != 4;
+ int lt = ordered && x < y;
+ int ge = ordered && x >= y;
+ int eq = ordered && x == y;
+ if (out[4 * i] != (lt ? 11 : 29)
+ || out[4 * i + 1] != (ge ? 31 : 47)
+ || out[4 * i + 2] != (lt ? 71 : 53)
+ || out[4 * i + 3] != (ge ? (eq ? 73 : 89)
+ : (eq ? 101 : 97)))
+ __builtin_abort ();
+ }
+ for (int i = n * 4; i < N * 4; ++i)
+ if (out[i] != -1)
+ __builtin_abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-7.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-7.c
new file mode 100644
index 00000000000..7b0b17028f6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-7.c
@@ -0,0 +1,57 @@
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-ssa-phiopt" } */
+
+/* Check reversed integer comparisons and nested predicates at the type
+ limits. Each result identifies one path through the conditions. */
+
+#define N 25
+static int a[N], b[N], out[N * 3];
+
+__attribute__ ((noipa))
+static void
+kernel (int *restrict out, const int *restrict a,
+ const int *restrict b, int n)
+{
+ for (int i = 0; i < n; ++i)
+ {
+ int x = a[i], y = b[i];
+ out[3 * i] = x < y ? 11 : 29;
+ out[3 * i + 1] = y <= x ? 31 : 47;
+ int r;
+ if (x >= y)
+ r = y == x ? 53 : 71;
+ else
+ r = y > 0 ? 73 : 89;
+ out[3 * i + 2] = r;
+ }
+}
+
+int
+main (void)
+{
+ int values[5] = { -__INT_MAX__ - 1, -1, 0, 1, __INT_MAX__ };
+ for (int i = 0; i < N; ++i)
+ {
+ a[i] = values[i / 5];
+ b[i] = values[i % 5];
+ }
+ for (int n = 0; n <= N; ++n)
+ {
+ for (int i = 0; i < N * 3; ++i)
+ out[i] = -1;
+ kernel (out, a, b, n);
+ for (int i = 0; i < n; ++i)
+ {
+ int x = i / 5, y = i % 5;
+ if (out[3 * i] != (x < y ? 11 : 29)
+ || out[3 * i + 1] != (x < y ? 47 : 31)
+ || out[3 * i + 2] != (x >= y ? (x == y ? 53 : 71)
+ : (y > 2 ? 73 : 89)))
+ __builtin_abort ();
+ }
+ for (int i = n * 3; i < N * 3; ++i)
+ if (out[i] != -1)
+ __builtin_abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-8.c
b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-8.c
new file mode 100644
index 00000000000..cbf12764479
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-8.c
@@ -0,0 +1,62 @@
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-ssa-phiopt" } */
+
+/* Check inverse predicates on conditional stores and reductions.
+ Unsigned arithmetic permits the reductions to wrap. */
+
+#define N 25
+static unsigned int a[N], b[N], out[N];
+
+__attribute__ ((noipa))
+static unsigned int
+kernel (unsigned int *restrict out, const unsigned int *restrict a,
+ const unsigned int *restrict b, int n)
+{
+ unsigned int sum = 1;
+ for (int i = 0; i < n; ++i)
+ {
+ unsigned int x = a[i], y = b[i];
+ if (x < y)
+ sum += y;
+ if (y <= x)
+ {
+ out[i] = x;
+ sum -= x;
+ }
+ }
+ return sum;
+}
+
+int
+main (void)
+{
+ unsigned int values[5] = { 0, 1, __INT_MAX__, __INT_MAX__ + 1U, ~0U };
+ for (int i = 0; i < N; ++i)
+ {
+ a[i] = values[i / 5];
+ b[i] = values[i % 5];
+ }
+ for (int n = 0; n <= N; ++n)
+ {
+ for (int i = 0; i < N; ++i)
+ out[i] = 42;
+ unsigned int sum = kernel (out, a, b, n);
+ unsigned int expected = 1;
+ for (int i = 0; i < n; ++i)
+ {
+ int x = i / 5, y = i % 5;
+ if (x < y)
+ expected += values[y];
+ else
+ expected -= values[x];
+ if (out[i] != (x < y ? 42 : values[x]))
+ __builtin_abort ();
+ }
+ if (sum != expected)
+ __builtin_abort ();
+ for (int i = n; i < N; ++i)
+ if (out[i] != 42)
+ __builtin_abort ();
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
index c496ff93d11..d9ac15708b2 100644
--- a/gcc/tree-ssa-sccvn.cc
+++ b/gcc/tree-ssa-sccvn.cc
@@ -5709,6 +5709,79 @@ visit_nary_op (tree lhs, gassign *stmt)
tree rhs1 = gimple_assign_rhs1 (stmt);
switch (code)
{
+ case COND_EXPR:
+ {
+ /* Valueization can return a constant even for an SSA selector. */
+ tree cond = vn_valueize (rhs1);
+ gassign *cmp = NULL;
+ if (TREE_CODE (cond) == SSA_NAME)
+ cmp = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (cond));
+ if (!cmp
+ || TREE_CODE_CLASS (gimple_assign_rhs_code (cmp)) != tcc_comparison
+ /* invert_tree_comparison allows EQ/NE inversion even when signaling
+ NaNs can trap. It preserves the trap at the comparison, but
+ reusing a later comparison must not move an earlier trap past
+ a side effect. */
+ || gimple_could_trap_p (cmp))
+ break;
+ tree_code cmp_code = gimple_assign_rhs_code (cmp);
+ tree ops[2] = { gimple_assign_rhs1 (cmp), gimple_assign_rhs2 (cmp) };
+ tree_code inverse_code
+ = invert_tree_comparison (cmp_code, HONOR_NANS (ops[0]));
+ if (inverse_code == ERROR_MARK)
+ break;
+ tree inverse = vn_nary_op_lookup_pieces (2, inverse_code,
+ TREE_TYPE (cond), ops, NULL);
+ if (!inverse)
+ break;
+ tree select_ops[3] = { inverse, gimple_assign_rhs3 (stmt),
+ gimple_assign_rhs2 (stmt) };
+ /* Equivalent selects can be found in either direction. */
+ result = vn_nary_op_lookup_pieces (3, COND_EXPR, type,
+ select_ops, NULL);
+ /* Create new selects in only one direction, using the lower comparison
+ code. A mere inequality would let each polarity replace the other.
+ The inverse lookup can return a constant, not just an SSA name. */
+ if (!result && inverse_code < cmp_code
+ && TREE_CODE (inverse) == SSA_NAME)
+ {
+ /* An SSA name can have a constant value number or VN_TOP. */
+ tree value = SSA_VAL (inverse);
+ vn_avail *av = (TREE_CODE (value) == SSA_NAME
+ ? VN_INFO (value)->avail : NULL);
+ /* Require an inverse available in this block. Checking the latest
+ availability record keeps eliminate_avail on its same-block
+ fast path, without walking the availability chain. */
+ tree leader = NULL_TREE;
+ if (rpo_avail && av && av->location == gimple_bb (stmt)->index)
+ leader = rpo_avail->eliminate_avail (gimple_bb (stmt), inverse);
+ gassign *def = NULL;
+ if (leader && TREE_CODE (leader) == SSA_NAME)
+ def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (leader));
+ /* The available leader need not be the comparison returned by the
+ lookup. Require a comparison in this block and check its code
+ too: VN can swap operands and thus change the comparison code.
+ The strict ordering must also hold for this actual leader. */
+ if (def && gimple_bb (def) == gimple_bb (stmt)
+ && TREE_CODE_CLASS (gimple_assign_rhs_code (def))
+ == tcc_comparison
+ && gimple_assign_rhs_code (def) < cmp_code)
+ {
+ gimple_match_op match_op (gimple_match_cond::UNCOND,
+ COND_EXPR, type, leader,
+ select_ops[1], select_ops[2]);
+ result = vn_nary_build_or_lookup (&match_op);
+ }
+ }
+ if (result)
+ {
+ bool changed = set_ssa_val_to (lhs, result);
+ if (TREE_CODE (result) == SSA_NAME)
+ vn_nary_op_insert_stmt (stmt, result);
+ return changed;
+ }
+ }
+ break;
CASE_CONVERT:
/* Match arithmetic done in a different type where we can easily
substitute the result from some earlier sign-changed or widened
@@ -7203,6 +7276,7 @@ eliminate_dom_walker::eliminate_insert (basic_block bb,
|| (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
&& gimple_assign_rhs_code (stmt) != VIEW_CONVERT_EXPR
&& gimple_assign_rhs_code (stmt) != NEGATE_EXPR
+ && gimple_assign_rhs_code (stmt) != COND_EXPR
&& gimple_assign_rhs_code (stmt) != BIT_FIELD_REF
&& (gimple_assign_rhs_code (stmt) != BIT_AND_EXPR
|| TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)))
@@ -7226,6 +7300,19 @@ eliminate_dom_walker::eliminate_insert (basic_block bb,
else if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR)
res = gimple_build (&stmts, BIT_AND_EXPR,
TREE_TYPE (val), leader, gimple_assign_rhs2 (stmt));
+ else if (gimple_assign_rhs_code (stmt) == COND_EXPR)
+ {
+ tree arg1 = gimple_assign_rhs2 (stmt);
+ tree arg2 = gimple_assign_rhs3 (stmt);
+ if (TREE_CODE (arg1) == SSA_NAME)
+ arg1 = eliminate_avail (bb, arg1);
+ if (TREE_CODE (arg2) == SSA_NAME)
+ arg2 = eliminate_avail (bb, arg2);
+ if (!arg1 || !arg2)
+ return NULL_TREE;
+ res = gimple_build (&stmts, COND_EXPR, TREE_TYPE (val),
+ leader, arg1, arg2);
+ }
else
res = gimple_build (&stmts, gimple_assign_rhs_code (stmt),
TREE_TYPE (val), leader);
--
2.50.1 (Apple Git-155)
