On Mon, Aug 28, 2023 at 12:58 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This adds a simple case to remove an outer condition if the two inner
> condtionals are the same and lead the same location.
> This can show up due to jump threading or inlining or someone wrote code
> like this.
>
> ifcombine-1.c shows the simple case where this is supposed to solve.
> Even though PRE can handle some cases, ifcombine is earlier and even runs
> at -O1.
>
> Note in the case of the PR here, it comes from jump threading.
>
> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>
> gcc/ChangeLog:
>
> PR tree-optimization/110891
> * tree-ssa-ifcombine.cc (ifcombine_bb_same): New function.
> (tree_ssa_ifcombine_bb): Call ifcombine_bb_same.
>
> gcc/testsuite/ChangeLog:
>
> PR tree-optimization/110891
> * gcc.dg/tree-ssa/ifcombine-1.c: New test.
> * gcc.dg/tree-ssa/pr110891-1.c: New test.
> ---
> gcc/testsuite/gcc.dg/tree-ssa/ifcombine-1.c | 27 ++++++
> gcc/testsuite/gcc.dg/tree-ssa/pr110891-1.c | 53 +++++++++++
> gcc/tree-ssa-ifcombine.cc | 100 ++++++++++++++++++++
> 3 files changed, 180 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifcombine-1.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr110891-1.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifcombine-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ifcombine-1.c
> new file mode 100644
> index 00000000000..02d08efef87
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifcombine-1.c
> @@ -0,0 +1,27 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-optimized -fdump-tree-ifcombine" } */
> +
> +int g();
> +int h();
> +
> +int j, l;
> +
> +int f(int a, int *b)
> +{
> + if (a == 0)
> + {
> + if (b == &j) goto L9; else goto L7;
> + }
> + else
> + {
> + if (b == &j) goto L9; else goto L7;
> + }
> +L7: return g();
> +L9: return h();
> +}
> +
> +/* ifcombine can optimize away the outer most if here. */
> +/* { dg-final { scan-tree-dump-times "optimized away the test from bb " 1
> "ifcombine" } } */
> +/* We should have remove the outer if and one of the inner ifs; leaving us
> with one if. */
> +/* { dg-final { scan-tree-dump-times "if " 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "goto " 3 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr110891-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/pr110891-1.c
> new file mode 100644
> index 00000000000..320d8823077
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr110891-1.c
> @@ -0,0 +1,53 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +void foo(void);
> +static int a, c = 7, d, o, q;
> +static int *b = &a, *f, *j = &d, *n = &c, *ae;
> +static short e, m;
> +static short *i = &e;
> +static char r;
> +void __assert_fail(char *, char *, int, const char *)
> __attribute__((__noreturn__));
> +static const short g();
> +static void h();
> +static int *k(int) {
> + (*i)++;
> + *j ^= *b;
> + return &a;
> +}
> +static void l(unsigned p) {
> + int *aa = &o;
> + h();
> + o = 5 ^ g() && p;
> + if (f == &d || f == &c || f == &a)
> + ;
> + else {
> + foo();
> + __assert_fail("", "", 3, __PRETTY_FUNCTION__);
> + }
> + *aa ^= *n;
> + if (*aa)
> + if (!(((p) >= 0) && ((p) <= 0))) {
> + __builtin_unreachable();
> + }
> + k(p);
> +}
> +static const short g() { return q; }
> +static void h() {
> + unsigned ag = c;
> + d = ag > r ? ag : 0;
> + ae = k(c);
> + f = ae;
> + if (ae == &d || ae == &c || ae == &a)
> + ;
> + else
> + __assert_fail("", "", 4, __PRETTY_FUNCTION__);
> +}
> +int main() {
> + l(a);
> + m || (*b |= 64);
> + *b &= 5;
> +}
> +
> +/* We should be able to optimize away foo. */
> +/* { dg-final { scan-tree-dump-not "foo " "optimized" } } */
> diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
> index 46b076804f4..f79545b9a0b 100644
> --- a/gcc/tree-ssa-ifcombine.cc
> +++ b/gcc/tree-ssa-ifcombine.cc
> @@ -666,6 +666,103 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool
> inner_inv,
> return false;
> }
>
> +/* Function to remove an outer condition if two inner basic blocks have the
> same condition and both empty otherwise. */
> +
> +static bool
> +ifcombine_bb_same (basic_block cond_bb, basic_block outer_cond_bb,
> + basic_block then_bb, basic_block else_bb)
> +{
> + basic_block inner_cond_bbt = nullptr, inner_cond_bbf = nullptr;
> +
> + /* See if the the outer condition is a condition. */
> + if (!recognize_if_then_else (outer_cond_bb, &inner_cond_bbt,
> &inner_cond_bbf))
> + return false;
> + basic_block other_cond_bb;
> + if (cond_bb == inner_cond_bbt)
> + other_cond_bb = inner_cond_bbf;
> + else
> + other_cond_bb = inner_cond_bbt;
> +
> + /* The other bb has to have a single predecessor too. */
> + if (!single_pred_p (other_cond_bb))
> + return false;
> +
> + /* Other inner conditional bb needs to go to the same then and else
> blocks. */
> + if (!recognize_if_then_else (other_cond_bb, &then_bb, &else_bb))
> + return false;
> +
> + /* Both edges of both inner basic blocks need to have the same values for
> the incoming phi for both then and else basic blocks. */
> + if (!same_phi_args_p (cond_bb, other_cond_bb, else_bb))
> + return false;
> +
> + if (!same_phi_args_p (cond_bb, other_cond_bb, then_bb))
> + return false;
> +
> + /* Both inner bbs need to be empty (besides the condition). */
> + if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (cond_bb)))
> + return false;
> + if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb
> (other_cond_bb)))
> + return false;
Possibly too restrictive (see empty_block_p), maybe worth a comment. Maybe
it's possible to leverage ICF BB comparison.
> + /* All 3 basic blocks need to have a GIMPLE_COND as the last statement. */
I think recognize_if_then_else pretty much guarantees this, though not
explicitly.
> + gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
> + if (!cond)
> + return false;
> +
> + gcond *other_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (other_cond_bb));
> + if (!other_cond)
> + return false;
> +
> + gcond *outer_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (outer_cond_bb));
> + if (!outer_cond)
> + return false;
> +
> + /* If already done the transformation, don't need to do it again. */
> + if (gimple_cond_true_p (outer_cond))
> + return false;
> + if (gimple_cond_false_p (outer_cond))
> + return false;
> +
> + /* Both inner bb have to have the same condition. */
> + if (gimple_cond_code (cond) != gimple_cond_code (other_cond)
> + || !operand_equal_p (gimple_cond_lhs (cond), gimple_cond_lhs
> (other_cond))
> + || !operand_equal_p (gimple_cond_rhs (cond), gimple_cond_rhs
> (other_cond)))
> + return false;
I can see one might be the inverted condition of the other (and thus
swapped then/else). Possibly for a followup?
> +
> + /* Both inner bbs need not to have phi nodes. */
I _think_ that's guaranteed by means of the merge PHI comparison, leaving
dead PHIs case which should be OK.
> + if (!gimple_seq_empty_p (phi_nodes (cond_bb)))
> + return false;
> +
> + if (!gimple_seq_empty_p (phi_nodes (other_cond_bb)))
> + return false;
> +
> + if (dump_file)
> + {
> + fprintf (dump_file, "optimized away the test from bb #%d.\n",
> outer_cond_bb->index);
> + }
> +
> + /* It does not matter which basic block we use here as both
> + are the same. Remove the one which we are processing now as
> + the other one will be processed afterwards and maybe merged in. */
> + bool remove_true_cond = inner_cond_bbt == cond_bb;
> +
> + /* Remove the bb which is not reachable any more
> + so the other one could be merged. */
> + edge remove_edge = find_edge (outer_cond_bb, remove_true_cond ?
> inner_cond_bbt : inner_cond_bbf);
> + edge keep_edge = find_edge (outer_cond_bb, remove_true_cond ?
> inner_cond_bbf : inner_cond_bbt);
I think we prefer to change the outer if to unconditonal if (true) or
if (false), leaving
the CFG manipulation to CFG cleanup.
> + keep_edge->flags |= EDGE_FALLTHRU;
> + keep_edge->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
> + keep_edge->probability = profile_probability::always ();
> + delete_basic_block (remove_edge->dest);
> +
> + /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
> + gimple_stmt_iterator gsi = gsi_last_bb (outer_cond_bb);
> + gsi_remove (&gsi, true);
> + /* Now merge the outer conditional block with the (old exectued) inner
> one. */
> + merge_blocks (outer_cond_bb, remove_true_cond ? inner_cond_bbf :
> inner_cond_bbt);
> + return true;
> +}
> +
> /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
> dispatch to the appropriate if-conversion helper for a particular
> set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
> @@ -780,6 +877,9 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
> {
> basic_block outer_cond_bb = single_pred (inner_cond_bb);
>
> + if (ifcombine_bb_same (inner_cond_bb, outer_cond_bb, then_bb, else_bb))
> + return true;
Otherwise looks OK.
Thanks,
Richard.
> +
> if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
> then_bb, else_bb, inner_cond_bb))
> return true;
> --
> 2.31.1
>
