[Richi, per your suggestion...is this what you had in mind?]
DOM's jump threader duplicates a join block that merges comparisons
into a boolean that is immediately tested:
<bb 3>:
t_9 = a < b;
goto <bb 5>;
<bb 4>:
t_6 = c < d;
goto <bb 5>;
<bb 5>:
# t_1 = PHI <t_9(3), t_6(4)>
if (t_1 != 0)
Implement this optimization in the phiopt pass, without using the jump
threading machinery DOM's version uses. This was an optimization we
lost with the jump threader rewrite, which DOM ended up picking up.
Measured over GCC's own sources plus LAPACK, the phiopt version takes
over ~94% of the joins DOM's special case caught: DOM registrations
for this optimization drop from 3536 to 196, with 1325 phiopt
replications; the remainder are cases that show up between phiopt and
DOM. Optimizations at loop boundaries (approx 700) are deliberately
left to the DOM threader, as replicating those would change loop
structure. I could loosen this restriction, but I've learned to fear
all things loop ;-).
I've left DOM's version in place, just in case we still want to allow
it for loop things, but I can just as easily drop it in a follow-up
patch.
Tested on ppc64le Linux.
OK?
PR tree-optimization/126896
gcc/ChangeLog:
* tree-ssa-phiopt.cc: Include tree-ssa-threadedge.h.
(preserves_loop_structure_p): New.
(replicate_cond_into_pred): New.
(replicate_conds_over_phis): New.
(pass_phiopt::execute): Call replicate_conds_over_phis.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/phi_on_compare-1.c: Scan the phiopt2 dump.
* gcc.dg/tree-ssa/phi_on_compare-2.c: Scan the optimized dump.
* gcc.dg/tree-ssa/phi_on_compare-3.c: Likewise.
* gcc.dg/tree-ssa/dom-jump-threading-1.c: Disable phiopt.
* gcc.dg/tree-ssa/dom-jump-threading-2.c: Likewise.
* gcc.dg/tree-ssa/phi_on_compare-5.c: New test.
---
.../gcc.dg/tree-ssa/dom-jump-threading-1.c | 2 +-
.../gcc.dg/tree-ssa/dom-jump-threading-2.c | 2 +-
.../gcc.dg/tree-ssa/phi_on_compare-1.c | 9 +-
.../gcc.dg/tree-ssa/phi_on_compare-2.c | 4 +-
.../gcc.dg/tree-ssa/phi_on_compare-3.c | 4 +-
.../gcc.dg/tree-ssa/phi_on_compare-5.c | 22 ++++
gcc/tree-ssa-phiopt.cc | 118 ++++++++++++++++++
7 files changed, 148 insertions(+), 13 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-5.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/dom-jump-threading-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/dom-jump-threading-1.c
index a0d0809b176..021401ff151 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/dom-jump-threading-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/dom-jump-threading-1.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 --param=dom-jump-threading=0 -fdump-tree-dom2-details
-fdump-tree-optimized" } */
+/* { dg-options "-O2 --param=dom-jump-threading=0 -fdisable-tree-phiopt2
-fdisable-tree-phiopt3 -fdisable-tree-phiopt4 -fdump-tree-dom2-details
-fdump-tree-optimized" } */
/* Verify that --param=dom-jump-threading=0 keeps DOM from threading
jumps. Only DOM can thread a PHI of compares (the backward
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/dom-jump-threading-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/dom-jump-threading-2.c
index fb6b8a12732..688d3ccbe5d 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/dom-jump-threading-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/dom-jump-threading-2.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-dom2-details" } */
+/* { dg-options "-O2 -fdisable-tree-phiopt2 -fdisable-tree-phiopt3
-fdisable-tree-phiopt4 -fdump-tree-dom2-details" } */
/* Same test as dom-jump-threading-1.c but with DOM jump threading at
its default (enabled): DOM must thread the PHI of compares, which
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c
index 923497f7896..baf020c2c56 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-Ofast -fdump-tree-dom2 -fdump-tree-optimized-details-blocks"
} */
+/* { dg-options "-Ofast -fdump-tree-phiopt2-details
-fdump-tree-optimized-details-blocks" } */
void g (int);
void g1 (int);
@@ -27,10 +27,5 @@ f (long a, long b, long c, long d, long x)
g (a);
}
-/* This is actually a regression. The backward threader cannot thread
- the above scenario, but it is being caught by the DOM threader
- which still uses the forward threader. We should implement this
- optimization in the backward threader before killing the forward
- threader. Similarly for the other phi_on_compare-*.c tests. */
-/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "dom2" } } */
+/* { dg-final { scan-tree-dump-times "replicating conditional" 2 "phiopt2" } }
*/
/* { dg-final { scan-tree-dump-not "Invalid sum" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c
index b1865701ad8..9b8daa856ab 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-Ofast -fdump-tree-dom2" } */
+/* { dg-options "-Ofast -fdump-tree-optimized" } */
void g (void);
void g1 (void);
@@ -20,4 +20,4 @@ f (long a, long b, long c, long d, int x)
}
}
-/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "dom2" } } */
+/* { dg-final { scan-tree-dump-not "PHI <" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c
index b48ecbf6e61..32af6a3e1f7 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-Ofast -fdump-tree-dom2" } */
+/* { dg-options "-Ofast -fdump-tree-optimized" } */
void g (void);
void g1 (void);
@@ -22,4 +22,4 @@ f (long a, long b, long c, long d, int x)
}
}
-/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "dom2" } } */
+/* { dg-final { scan-tree-dump-not "PHI <" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-5.c
b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-5.c
new file mode 100644
index 00000000000..3ed0e9736e5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-5.c
@@ -0,0 +1,22 @@
+/* PR tree-optimization/126896 */
+/* { dg-do compile } */
+/* { dg-options "-O2 --param=dom-jump-threading=0 -fdump-tree-optimized" } */
+
+/* Even with DOM jump threading disabled, phiopt replicates the
+ conditional into both predecessors and the boolean PHI dies. */
+
+void g (void);
+
+void
+f (int x, int a, int b, int c, int d)
+{
+ _Bool t;
+ if (x)
+ t = a < b;
+ else
+ t = c < d;
+ if (t)
+ g ();
+}
+
+/* { dg-final { scan-tree-dump-not "PHI" "optimized" } } */
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index 784221c83b3..f8dbd26abc1 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -55,6 +55,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-ssa-loop-niter.h"
#include "gimple-predict.h"
#include "alias.h"
+#include "tree-ssa-threadedge.h"
/* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
@@ -4871,6 +4872,117 @@ execute_over_cond_phis (func_type func)
where left and right are typically adjacent pointers in a tree structure.
*/
+/* Return TRUE if duplicating E's destination with E redirected to
+ the copy leaves the loop structure unchanged. Requires
+ EDGE_DFS_BACK to be current. */
+
+static bool
+preserves_loop_structure_p (edge e)
+{
+ basic_block bb = e->dest;
+
+ if ((e->flags & EDGE_DFS_BACK)
+ || e->src->loop_father != bb->loop_father)
+ return false;
+
+ edge s;
+ edge_iterator ei;
+ FOR_EACH_EDGE (s, ei, bb->succs)
+ if ((s->flags & EDGE_DFS_BACK)
+ || s->dest->loop_father != bb->loop_father)
+ return false;
+
+ return true;
+}
+
+/* Replicate the join block at E's destination into E's source. The copy's
+ PHIs degenerate to their argument on E, so the copied conditional tests the
+ predecessor's own value. The net effect after cleanups, for edge (3, 5)
+ would be:
+
+ <bb 3>: <bb 3>:
+ t_9 = a < b; t_9 = a < b;
+ goto <bb 5>; if (t_9 != 0)
+
+ <bb 4>: -> <bb 4>:
+ t_6 = c < d; t_6 = c < d;
+ goto <bb 5>; goto <bb 5>;
+
+ <bb 5>: <bb 5>:
+ # t_1 = PHI <t_9(3), t_6(4)> # t_1 = PHI <t_6(4)>
+ if (t_1 != 0) if (t_1 != 0)
+
+ Return TRUE if the replication was performed. */
+
+static bool
+replicate_cond_into_pred (edge e)
+{
+ basic_block bb = e->dest;
+
+ if (!can_duplicate_block_on_edge_p (e)
+ || !preserves_loop_structure_p (e))
+ return false;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "replicating conditional in bb%d into predecessor bb%d\n",
+ bb->index, e->src->index);
+
+ basic_block copy = duplicate_block (bb, e, e->src);
+ flush_pending_stmts (e);
+ add_phi_args_after_copy (©, 1, NULL);
+ return true;
+}
+
+/* Replicate conditionals over a PHI of comparisons into the
+ qualifying predecessors of every join block in the function, so
+ each arm branches directly on its own comparison instead of merging
+ into a boolean that is tested again:
+
+ <bb 3>: <bb 3>:
+ t_9 = a < b; t_9 = a < b;
+ goto <bb 5>; if (t_9 != 0)
+
+ <bb 4>: -> <bb 4>:
+ t_6 = c < d; t_6 = c < d;
+ goto <bb 5>; if (t_6 != 0)
+
+ <bb 5>:
+ # t_1 = PHI <t_9(3), t_6(4)>
+ if (t_1 != 0)
+*/
+
+static bool
+replicate_conds_over_phis (void)
+{
+ bool cfgchanged = false;
+ basic_block bb;
+
+ mark_dfs_back_edges ();
+ initialize_original_copy_tables ();
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ gcond *cond;
+ gphi *phi;
+ if (EDGE_COUNT (bb->preds) < 2
+ || !cond_on_phi_p (bb, &cond, &phi))
+ continue;
+
+ edge e;
+ edge_iterator ei = ei_start (bb->preds);
+ while ((e = ei_safe_edge (ei)))
+ {
+ if (phi_arg_from_cmp_p (phi, e)
+ && replicate_cond_into_pred (e))
+ cfgchanged = true;
+ else
+ ei_next (&ei);
+ }
+ }
+ free_original_copy_tables ();
+ return cfgchanged;
+}
+
namespace {
const pass_data pass_data_phiopt =
@@ -5010,6 +5122,12 @@ pass_phiopt::execute (function *)
execute_over_cond_phis (phiopt_exec);
+ if (!early_p && replicate_conds_over_phis ())
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ return TODO_cleanup_cfg | TODO_update_ssa;
+ }
+
if (cfgchanged)
return TODO_cleanup_cfg;
return 0;
--
2.47.3
