[PATCH] IFCOMBINE: Remove outer condition for two same conditionals

[PATCH] IFCOMBINE: Remove outer condition for two same conditionals

[Andrew Pinski]

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;
+
+  /* All 3 basic blocks need to have a GIMPLE_COND as the last statement. */
+  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;
+
+  /* Both inner bbs need not to have phi nodes.  */
+  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);
+  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;
+
       if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
 				   then_bb, else_bb, inner_cond_bb))
 	return true;
-- 
2.31.1

Re: [PATCH] IFCOMBINE: Remove outer condition for two same conditionals

[Richard Biener]

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
>