After tail merging combines duplicate blocks, their predecessors branch
to the same successor. Combine the sequential conditions leading to the
merged block using the ifcombine infrastructure; on targets with
conditional compares this lets the backend emit ccmp. Whether combining
is profitable is left to ifcombine's own cost model.
The candidate selection identifies predecessor blocks of the merged block
that have conditional branches, excluding the immediate dominator. After
the tail-merge loop completes, dominance info is (re)computed, SSA names
that may be undefined are marked, and tree_ssa_ifcombine_bb is called for
each candidate.
Combining the scalar conditions that guard a loop would turn the loop's
analyzable entry test into a boolean one, defeating the number-of-iterations
analysis (and thus passes such as ivopts); extend ifcombine's existing
niter-safety check to leave loop guards alone too.
gcc/ChangeLog:
PR tree-optimization/102793
* tree-ssa-ifcombine.cc (bb_guards_loop_p): New function.
(ifcombine_ifandif): Use it to avoid combining the conditions
guarding a loop.
* tree-ssa-tail-merge.cc: Include tree-ssa-ifcombine.h and
tree-ssa.h.
(ifcombine_candidate_bbs): New static bitmap.
(apply_clusters): Collect the merged block's predecessors as
ifcombine candidates.
(tail_merge_optimize): Run tree_ssa_ifcombine_bb on the candidates;
return TODO_cleanup_cfg when it changed the CFG.
gcc/testsuite/ChangeLog:
PR tree-optimization/102793
* g++.dg/tree-ssa/pr117123.C: Use --param
logical-op-non-short-circuit=0.
* gcc.dg/tree-ssa/pr102793-1.c: New test.
* gcc.dg/tree-ssa/pr102793-2.c: New test.
* gcc.dg/uninit-pred-13.c: New test.
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
Changes in v3:
- Drop the targetm.have_ccmp () gate; the post-tail-merge ifcombine now runs on
all targets, leaving profitability to ifcombine's own cost model.
- Replace the maybe_undef_at_dom_frontier_p work-around with a fix in the uninit
predicate analysis (relax the definition predicate by the maybe-undef
operands' incoming-edge conditions).
- apply_clusters: hoist the immediate-dominator check ahead of
recognize_if_then_else and assert the gcond.
- Add gcc.dg/uninit-pred-13.c covering the uninit interaction.
- Make the pr102793 tests target-independent (force the combine with
--param logical-op-non-short-circuit=1, drop the ccmp dg-skip-if) and use
__UINT64_TYPE__.
- ifcombine: do not combine the conditions guarding a loop. Extend the
existing niter-safety check (which already leaves integer/pointer loop exit
conditions alone) to loop guards too, so the post-tail-merge combine no
longer makes a guarded loop's number-of-iterations unanalyzable; this
restores the IV elimination in gcc.dg/tree-ssa/ivopt_mult_1.c and
ivopt_mult_2.c.
- pr117123.C: force --param logical-op-non-short-circuit=0 so this
value-numbering test keeps its short-circuit form (3 ifs) on all targets,
rather than being combined to 2 where the target defaults to
non-short-circuit (e.g. x86).
gcc/testsuite/g++.dg/tree-ssa/pr117123.C | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/pr102793-1.c | 49 ++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr102793-2.c | 50 ++++++++++++++++++
gcc/testsuite/gcc.dg/uninit-pred-13.c | 60 ++++++++++++++++++++++
gcc/tree-ssa-ifcombine.cc | 34 ++++++++++--
gcc/tree-ssa-tail-merge.cc | 60 ++++++++++++++++++++--
6 files changed, 246 insertions(+), 9 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr102793-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr102793-2.c
create mode 100644 gcc/testsuite/gcc.dg/uninit-pred-13.c
diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr117123.C
b/gcc/testsuite/g++.dg/tree-ssa/pr117123.C
index 2aa2810de952..3b0e8817e0b0 100644
--- a/gcc/testsuite/g++.dg/tree-ssa/pr117123.C
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr117123.C
@@ -1,5 +1,5 @@
// { dg-do compile }
-// { dg-options "-Os -fdump-tree-optimized" }
+// { dg-options "-Os -fdump-tree-optimized --param
logical-op-non-short-circuit=0" }
struct Potato {
int size;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr102793-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr102793-1.c
new file mode 100644
index 000000000000..436b4e4bf058
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr102793-1.c
@@ -0,0 +1,49 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-pre --param logical-op-non-short-circuit=1" }
*/
+
+typedef __UINT64_TYPE__ uint64_t;
+
+int foo(void);
+
+int ccmp(uint64_t* s1, uint64_t* s2)
+{
+ uint64_t d1, d2, bar;
+ d1 = *s1++;
+ d2 = *s2++;
+ bar = (d1 ^ d2) & 0xabcd;
+ if (bar == 0 || d1 != d2)
+ return foo();
+ return 0;
+}
+
+int noccmp0(uint64_t* s1, uint64_t* s2)
+{
+ uint64_t d1, d2, bar;
+
+ d1 = *s1++;
+ d2 = *s2++;
+ bar = (d1 ^ d2) & 0xabcd;
+ if (bar == 0)
+ return foo();
+ if (d1 != d2)
+ return foo();
+ return 0;
+}
+
+int noccmp1(uint64_t* s1, uint64_t* s2)
+{
+ uint64_t d1, d2, d3, d4, bar;
+ d1 = *s1++;
+ d2 = *s2++;
+ d3 = *s1++;
+ d4 = *s2++;
+ bar = (d1 ^ d2) & 0xabcd;
+ if (bar == 0)
+ return foo();
+ if (d3 != d4)
+ return foo();
+ return 0;
+}
+
+/* Check for condition assignments for noccmp0 and noccmp1. */
+/* { dg-final { scan-tree-dump-times {_\d+ = d\d+_\d+ != d\d+_\d+;\n _\d+ =
bar_\d+ == 0;} 2 "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr102793-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr102793-2.c
new file mode 100644
index 000000000000..40e03365adbd
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr102793-2.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-pre --param logical-op-non-short-circuit=1" }
*/
+
+typedef __UINT64_TYPE__ uint64_t;
+
+int foo(void);
+
+uint64_t noccmp0(uint64_t* s1, uint64_t* s2)
+{
+ uint64_t d1, d2, d3, d4, bar;
+ d1 = *s1++;
+ d2 = *s2++;
+ d3 = *s1++;
+ d4 = *s2++;
+ bar = (d1 ^ d2) & 0xabcd;
+ if (bar == 0)
+ return foo();
+ if (d3 != d4)
+ d3++;
+ else
+ return foo();
+ return d3;
+}
+
+uint64_t noccmp1(uint64_t* s1, uint64_t* s2)
+{
+ uint64_t d1, d2, d3, d4, bar;
+ d1 = *s1++;
+ d2 = *s2++;
+ d3 = *s1++;
+ d4 = *s2++;
+ bar = (d1 ^ d2) & 0xabcd;
+ if (bar == 0)
+ d3++;
+ else
+ return foo();
+ if (d3 > d4)
+ d3++;
+ else if (d1 != d2)
+ return foo ();
+ d3 = d3 + d4 + 1;
+ return d3;
+}
+
+/* Check for condition assignments in the case that the transformation
+ is applied.
+ The transformation should not be applied on noccmp1, where the foo call is
+ on the false branch of the first condition. */
+/* { dg-final { scan-tree-dump-times {_\d+ = d\d+_\d+ != d\d+_\d+;\n _\d+ =
bar_\d+ != 0;} 1 "pre" } } */
+/* { dg-final { scan-tree-dump-times {if \(bar_\d+ == 0\)} 1 "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/uninit-pred-13.c
b/gcc/testsuite/gcc.dg/uninit-pred-13.c
new file mode 100644
index 000000000000..a7192d716712
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-pred-13.c
@@ -0,0 +1,60 @@
+/* { dg-do compile } */
+/* { dg-options "-Wuninitialized -O2" } */
+/* { dg-skip-if "tail-merge ifcombine fires on ccmp targets" { ! {
aarch64*-*-* || apxf } } } */
+
+/* Tail-merge runs ifcombine to combine the conditions guarding V's definition.
+ Check that uninit still proves the guarded uses safe and still warns when V
+ can be used uninitialized. */
+
+int g;
+void bar (void);
+void blah (int);
+
+/* V is defined only under (n > 10) && l. The second use is guarded by
+ l && n > 12, which implies the definition guard, so no warning must be
+ emitted even after the conditions are combined. */
+int
+guarded (int n, int l, int m, int r)
+{
+ int v;
+
+ if (n > 10)
+ if (l)
+ v = r;
+
+ if (m) g++; else bar ();
+
+ if ((n > 10) && l)
+ blah (v); /* { dg-bogus "uninitialized" } */
+
+ if (l)
+ if (n > 12)
+ blah (v); /* { dg-bogus "uninitialized" } */
+
+ return 0;
+}
+
+/* Same shape and the same tail-merge + ifcombine combination, but the second
+ use's guard l && n > 8 does not imply the definition guard (n > 10) && l:
+ V is uninitialized for n in { 9, 10 }, so it must still warn -- the
+ relaxation must not over-suppress. */
+int
+unguarded (int n, int l, int m, int r)
+{
+ int v;
+
+ if (n > 10)
+ if (l)
+ v = r;
+
+ if (m) g++; else bar ();
+
+ if ((n > 10) && l)
+ blah (v); /* { dg-bogus "uninitialized" } */
+
+ if (l)
+ if (n > 8)
+ blah (v); /* { dg-warning "uninitialized" } */
+
+ return 0;
+}
diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
index 048ed30d7631..d57029da020f 100644
--- a/gcc/tree-ssa-ifcombine.cc
+++ b/gcc/tree-ssa-ifcombine.cc
@@ -800,6 +800,28 @@ can_combine_bbs_with_short_circuit (basic_block
inner_cond_bb, tree lhs, tree rh
return false;
}
+/* Return true if BB guards entry to a loop: a successor edge reaches a loop
+ header BB does not belong to, directly or through a single-successor
+ preheader. Combining the scalar conditions guarding a loop into a single
+ boolean leaves the number-of-iterations analysis unable to prove the loop
+ runs at least once, pessimizing later loop passes such as ivopts. */
+
+static bool
+bb_guards_loop_p (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ basic_block h = e->dest;
+ if (single_succ_p (h) && !bb_loop_header_p (h))
+ h = single_succ (h);
+ if (bb_loop_header_p (h) && !dominated_by_p (CDI_DOMINATORS, bb, h))
+ return true;
+ }
+ return false;
+}
+
/* If-convert on a and pattern with a common else block. The inner
if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
inner_inv, outer_inv indicate whether the conditions are inverted.
@@ -820,11 +842,13 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool
inner_inv,
if (!outer_cond)
return false;
- /* niter analysis does not cope with boolean typed loop exit conditions.
- Avoid turning an analyzable exit into an unanalyzable one. */
- if (inner_cond_bb->loop_father == outer_cond_bb->loop_father
- && loop_exits_from_bb_p (inner_cond_bb->loop_father, inner_cond_bb)
- && loop_exits_from_bb_p (outer_cond_bb->loop_father, outer_cond_bb))
+ /* niter analysis does not cope with boolean typed loop exit conditions, nor
+ with boolean loop guards. Avoid turning an analyzable loop exit or guard
+ into an unanalyzable one. */
+ if ((inner_cond_bb->loop_father == outer_cond_bb->loop_father
+ && loop_exits_from_bb_p (inner_cond_bb->loop_father, inner_cond_bb)
+ && loop_exits_from_bb_p (outer_cond_bb->loop_father, outer_cond_bb))
+ || bb_guards_loop_p (inner_cond_bb))
{
tree outer_type = TREE_TYPE (gimple_cond_lhs (outer_cond));
tree inner_type = TREE_TYPE (gimple_cond_lhs (inner_cond));
diff --git a/gcc/tree-ssa-tail-merge.cc b/gcc/tree-ssa-tail-merge.cc
index 4b9dbd886b6a..323d71f132cd 100644
--- a/gcc/tree-ssa-tail-merge.cc
+++ b/gcc/tree-ssa-tail-merge.cc
@@ -202,9 +202,11 @@ along with GCC; see the file COPYING3. If not see
#include "tree-cfg.h"
#include "tree-into-ssa.h"
#include "tree-ssa-sccvn.h"
+#include "tree-ssa-ifcombine.h"
#include "cfgloop.h"
#include "tree-eh.h"
#include "tree-cfgcleanup.h"
+#include "tree-ssa.h"
const int ignore_edge_flags = EDGE_DFS_BACK | EDGE_EXECUTABLE;
@@ -1707,6 +1709,8 @@ replace_block_by (basic_block bb1, basic_block bb2)
static bitmap update_bbs;
+static bitmap ifcombine_candidate_bbs;
+
/* For each cluster in all_clusters, merge all cluster->bbs. Returns
number of bbs removed. */
@@ -1735,6 +1739,31 @@ apply_clusters (void)
bitmap_clear_bit (update_bbs, bb1->index);
replace_block_by (bb1, bb2);
+
+ basic_block imm_dominator
+ = get_immediate_dominator (CDI_DOMINATORS, bb2);
+
+ /* Find conditions in if-statements that lead to bb2. */
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb2->preds)
+ {
+ /* The immediate dominator's condition cannot be combined; skip it
+ before the more expensive recognize_if_then_else check. */
+ if (e->src == imm_dominator)
+ continue;
+
+ basic_block then_tmp = NULL;
+ basic_block else_tmp = NULL;
+ if (recognize_if_then_else (e->src, &bb2, &else_tmp)
+ || recognize_if_then_else (e->src, &then_tmp, &bb2))
+ {
+ /* A recognized if-then-else always ends in a gcond. */
+ gcc_assert (safe_dyn_cast <gcond *> (*gsi_last_bb (e->src)));
+ bitmap_set_bit (ifcombine_candidate_bbs, e->src->index);
+ }
+ }
+
nr_bbs_removed++;
}
}
@@ -1807,6 +1836,7 @@ tail_merge_optimize (bool need_crit_edge_split)
bool loop_entered = false;
int iteration_nr = 0;
int max_iterations = param_max_tail_merge_iterations;
+ unsigned int todo = 0;
if (!flag_tree_tail_merge
|| max_iterations == 0)
@@ -1833,6 +1863,7 @@ tail_merge_optimize (bool need_crit_edge_split)
loop_entered = true;
alloc_cluster_vectors ();
update_bbs = BITMAP_ALLOC (NULL);
+ ifcombine_candidate_bbs = BITMAP_ALLOC (NULL);
}
else
reset_cluster_vectors ();
@@ -1866,10 +1897,30 @@ tail_merge_optimize (bool need_crit_edge_split)
if (nr_bbs_removed_total > 0)
{
+ bool need_dominance
+ = MAY_HAVE_DEBUG_BIND_STMTS
+ || !bitmap_empty_p (ifcombine_candidate_bbs);
+
+ if (need_dominance)
+ calculate_dominance_info (CDI_DOMINATORS);
+
if (MAY_HAVE_DEBUG_BIND_STMTS)
+ update_debug_stmts ();
+
+ unsigned int i;
+ bitmap_iterator bi;
+ bool cfg_changed = false;
+ /* Try to combine conditions of blocks that were made to branch to the
+ same successor by tail merging. */
+ if (!bitmap_empty_p (ifcombine_candidate_bbs))
{
- calculate_dominance_info (CDI_DOMINATORS);
- update_debug_stmts ();
+ mark_ssa_maybe_undefs ();
+ EXECUTE_IF_SET_IN_BITMAP (ifcombine_candidate_bbs, 0, i, bi)
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
+ if (bb)
+ cfg_changed |= tree_ssa_ifcombine_bb (bb);
+ }
}
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1879,6 +1930,8 @@ tail_merge_optimize (bool need_crit_edge_split)
}
mark_virtual_operands_for_renaming (cfun);
+
+ todo |= cfg_changed ? TODO_cleanup_cfg : 0;
}
delete_worklist ();
@@ -1886,9 +1939,10 @@ tail_merge_optimize (bool need_crit_edge_split)
{
delete_cluster_vectors ();
BITMAP_FREE (update_bbs);
+ BITMAP_FREE (ifcombine_candidate_bbs);
}
timevar_pop (TV_TREE_TAIL_MERGE);
- return 0;
+ return todo;
}
--
2.52.0
