Patchwork [tree-optimization] : Improve handling of conditional-branches on targets with high branch costs

login
register
mail settings
Submitter Kai Tietz
Date Oct. 6, 2011, 2:25 p.m.
Message ID <14d7ea4a-5238-423e-8341-30e8a8db52dd@zmail06.collab.prod.int.phx2.redhat.com>
Download mbox | patch
Permalink /patch/118102/
State New
Headers show

Comments

Kai Tietz - Oct. 6, 2011, 2:25 p.m.
Hi,

I modified the patch so, that it always just converts two leafs of a TRUTH(AND|OR)IF chain into a TRUTH_(AND|OR) expression, if branch costs are high and leafs are simple without side-effects.

Additionally I added some testcases for it.

2011-10-06  Kai Tietz  <ktietz@redhat.com>

	* fold-const.c (fold_truth_andor): Convert TRUTH_(AND|OR)IF_EXPR
	to TRUTH_OR_EXPR, if suitable.

2011-10-06  Kai Tietz  <ktietz@redhat.com>

	* gcc.dg/tree-ssa/ssa-ifbranch-1.c: New test.
	* gcc.dg/tree-ssa/ssa-ifbranch-2.c: New test.
	* gcc.dg/tree-ssa/ssa-ifbranch-3.c: New test.
	* gcc.dg/tree-ssa/ssa-ifbranch-4.c: New test.

Bootstrapped and tested for all languages (including Ada and Obj-C++) on host x86_64-unknown-linux-gnu.  Ok for apply?

Regards,
Kai
Richard Guenther - Oct. 7, 2011, 2:47 p.m.
On Thu, Oct 6, 2011 at 4:25 PM, Kai Tietz <ktietz@redhat.com> wrote:
> Hi,
>
> I modified the patch so, that it always just converts two leafs of a TRUTH(AND|OR)IF chain into a TRUTH_(AND|OR) expression, if branch costs are high and leafs are simple without side-effects.
>
> Additionally I added some testcases for it.
>
> 2011-10-06  Kai Tietz  <ktietz@redhat.com>
>
>        * fold-const.c (fold_truth_andor): Convert TRUTH_(AND|OR)IF_EXPR
>        to TRUTH_OR_EXPR, if suitable.
>
> 2011-10-06  Kai Tietz  <ktietz@redhat.com>
>
>        * gcc.dg/tree-ssa/ssa-ifbranch-1.c: New test.
>        * gcc.dg/tree-ssa/ssa-ifbranch-2.c: New test.
>        * gcc.dg/tree-ssa/ssa-ifbranch-3.c: New test.
>        * gcc.dg/tree-ssa/ssa-ifbranch-4.c: New test.
>
> Bootstrapped and tested for all languages (including Ada and Obj-C++) on host x86_64-unknown-linux-gnu.  Ok for apply?
>
> Regards,
> Kai
>
> Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-1.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-1.c
> @@ -0,0 +1,18 @@
> +/* Skip on MIPS, S/390, and AVR due LOGICAL_OP_NON_SHORT_CIRCUIT, and
> +   lower values in BRANCH_COST.  */
> +/* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-* mn10300-*-*" } } } */
> +/* { dg-options "-O2 -fdump-tree-gimple" } */
> +/* { dg-options "-O2 -fdump-tree-gimple -march=i586" { target { i?86-*-* && ilp32 } } } */
> +
> +extern int doo1 (void);
> +extern int doo2 (void);
> +
> +int bar (int a, int b, int c)
> +{
> +  if (a && b && c)
> +    return doo1 ();
> +  return doo2 ();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "if " 2 "gimple" } } */
> +/* { dg-final { cleanup-tree-dump "gimple" } } */
> Index: gcc-head/gcc/fold-const.c
> ===================================================================
> --- gcc-head.orig/gcc/fold-const.c
> +++ gcc-head/gcc/fold-const.c
> @@ -8387,6 +8387,45 @@ fold_truth_andor (location_t loc, enum t
>   if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
>     return tem;
>
> +  if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
> +      && !TREE_SIDE_EFFECTS (arg1)
> +      && LOGICAL_OP_NON_SHORT_CIRCUIT
> +      /* floats might trap.  */
> +      && !FLOAT_TYPE_P (TREE_TYPE (arg1))

Floats don't "trap" on their own.  If possibly trapping trees don't have
TREE_SIDE_EFFECTS set then you want

&& !tree_could_trap_p (arg1)

here.

> +      && ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison
> +           && TREE_CODE (arg1) != TRUTH_NOT_EXPR
> +           && simple_operand_p (arg1))

As I said previously simple_operand_p already rejects covers
comparisons and TRUTH_NOT_EXPR.  Also arg1 had better
TREE_SIDE_EFFECTS set if the comparison might trap, as
it might just be hidden in something more complicated - so
the simple check isn't enough anyway (and if simple_operand_p
would cover it, the check would be better placed there).

> +          || ((TREE_CODE_CLASS (TREE_CODE (arg1)) == tcc_comparison
> +               || TREE_CODE (arg1) == TRUTH_NOT_EXPR)
> +             /* Float comparison might trap.  */
> +              && !FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg1, 0)))
> +              && simple_operand_p (TREE_OPERAND (arg1, 0)))))
> +    {
> +      /* We want to combine truth-comparison for
> +        ((W TRUTH-ANDOR X) TRUTH-ANDORIF Y) TRUTH-ANDORIF Z,
> +        if Y and Z are simple operands and have no side-effect to
> +        ((W TRUTH-ANDOR X) TRUTH-IF (Y TRUTH-ANDOR Z).  */

No we don't.  See down-thread.

> +      if (TREE_CODE (arg0) == code
> +          && !TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1))
> +          && simple_operand_p (TREE_OPERAND (arg0, 1)))
> +       {
> +         tem = build2_loc (loc,
> +                           (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
> +                                                     : TRUTH_OR_EXPR),
> +                           type, TREE_OPERAND (arg0, 1), arg1);
> +         return build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
> +                            tem);

All trees should be folded, don't use plain build without a good reason.

> +       }
> +      /* Convert X TRUTH-ANDORIF Y to X TRUTH-ANDOR Y, if X and Y
> +        are simple operands and have no side-effects.  */
> +      if (simple_operand_p (arg0)
> +          && !TREE_SIDE_EFFECTS (arg0))

Again, the checks you do for arg0 do not match those for arg1.  OTOH
it doesn't matter whether arg0 is simple or not or has side-effects or
not for this transformation, so why check it at all?

In fold_truthop we still have the same (albeit more restricted transform),
but guarded with

 if (BRANCH_COST (optimize_function_for_speed_p (cfun),
                   false) >= 2

too.  Why not here?  Please delete redundant code in fold_truthop.

It's also odd that this is only called from fold_truth_andor but has
a more generic name, so maybe rename it to fold_truth_andor_1 on the way.

Richard.

> +       return build2_loc (loc,
> +                          (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
> +                                                    : TRUTH_OR_EXPR),
> +                          type, arg0, arg1);
> +    }
> +
>   return NULL_TREE;
>  }
>
> Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-2.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-2.c
> @@ -0,0 +1,18 @@
> +/* Skip on MIPS, S/390, and AVR due LOGICAL_OP_NON_SHORT_CIRCUIT, and
> +   lower values in BRANCH_COST.  */
> +/* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-* mn10300-*-*" } } } */
> +/* { dg-options "-O2 -fdump-tree-gimple" } */
> +/* { dg-options "-O2 -fdump-tree-gimple -march=i586" { target { i?86-*-* && ilp32 } } } */
> +
> +extern int doo1 (void);
> +extern int doo2 (void);
> +
> +int bar (int a, int b, int c, int d)
> +{
> +  if (a && b && c && d)
> +    return doo1 ();
> +  return doo2 ();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "if " 2 "gimple" } } */
> +/* { dg-final { cleanup-tree-dump "gimple" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-3.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-3.c
> @@ -0,0 +1,18 @@
> +/* Skip on MIPS, S/390, and AVR due LOGICAL_OP_NON_SHORT_CIRCUIT, and
> +   lower values in BRANCH_COST.  */
> +/* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-* mn10300-*-*" } } } */
> +/* { dg-options "-O2 -fdump-tree-gimple" } */
> +/* { dg-options "-O2 -fdump-tree-gimple -march=i586" { target { i?86-*-* && ilp32 } } } */
> +
> +extern int doo1 (void);
> +extern int doo2 (void);
> +
> +int bar (int a, int c)
> +{
> +  if (a &&  c)
> +    return doo1 ();
> +  return doo2 ();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "if " 1 "gimple" } } */
> +/* { dg-final { cleanup-tree-dump "gimple" } } */
> Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-4.c
> ===================================================================
> --- /dev/null
> +++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-4.c
> @@ -0,0 +1,18 @@
> +/* Skip on MIPS, S/390, and AVR due LOGICAL_OP_NON_SHORT_CIRCUIT, and
> +   lower values in BRANCH_COST.  */
> +/* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-* mn10300-*-*" } } } */
> +/* { dg-options "-O2 -fdump-tree-gimple" } */
> +/* { dg-options "-O2 -fdump-tree-gimple -march=i586" { target { i?86-*-* && ilp32 } } } */
> +
> +extern int doo1 (void);
> +extern int doo2 (void);
> +
> +int bar (int a, int b, int c, int d)
> +{
> +  if ((a && b) && (c && d))
> +    return doo1 ();
> +  return doo2 ();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "if " 2 "gimple" } } */
> +/* { dg-final { cleanup-tree-dump "gimple" } } */
>

Patch

Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-1.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-1.c
@@ -0,0 +1,18 @@ 
+/* Skip on MIPS, S/390, and AVR due LOGICAL_OP_NON_SHORT_CIRCUIT, and
+   lower values in BRANCH_COST.  */
+/* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-* mn10300-*-*" } } } */
+/* { dg-options "-O2 -fdump-tree-gimple" } */
+/* { dg-options "-O2 -fdump-tree-gimple -march=i586" { target { i?86-*-* && ilp32 } } } */
+
+extern int doo1 (void);
+extern int doo2 (void);
+
+int bar (int a, int b, int c)
+{
+  if (a && b && c)
+    return doo1 ();
+  return doo2 ();
+}
+
+/* { dg-final { scan-tree-dump-times "if " 2 "gimple" } } */
+/* { dg-final { cleanup-tree-dump "gimple" } } */
Index: gcc-head/gcc/fold-const.c
===================================================================
--- gcc-head.orig/gcc/fold-const.c
+++ gcc-head/gcc/fold-const.c
@@ -8387,6 +8387,45 @@  fold_truth_andor (location_t loc, enum t
   if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0)
     return tem;
 
+  if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR)
+      && !TREE_SIDE_EFFECTS (arg1)
+      && LOGICAL_OP_NON_SHORT_CIRCUIT
+      /* floats might trap.  */
+      && !FLOAT_TYPE_P (TREE_TYPE (arg1))
+      && ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison
+           && TREE_CODE (arg1) != TRUTH_NOT_EXPR
+           && simple_operand_p (arg1))
+          || ((TREE_CODE_CLASS (TREE_CODE (arg1)) == tcc_comparison
+               || TREE_CODE (arg1) == TRUTH_NOT_EXPR)
+	      /* Float comparison might trap.  */
+              && !FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg1, 0)))
+              && simple_operand_p (TREE_OPERAND (arg1, 0)))))
+    {
+      /* We want to combine truth-comparison for
+	 ((W TRUTH-ANDOR X) TRUTH-ANDORIF Y) TRUTH-ANDORIF Z,
+	 if Y and Z are simple operands and have no side-effect to
+	 ((W TRUTH-ANDOR X) TRUTH-IF (Y TRUTH-ANDOR Z).  */
+      if (TREE_CODE (arg0) == code
+          && !TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1))
+          && simple_operand_p (TREE_OPERAND (arg0, 1)))
+	{
+	  tem = build2_loc (loc,
+			    (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
+						      : TRUTH_OR_EXPR),
+			    type, TREE_OPERAND (arg0, 1), arg1);
+	  return build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
+			     tem);
+	}
+      /* Convert X TRUTH-ANDORIF Y to X TRUTH-ANDOR Y, if X and Y
+	 are simple operands and have no side-effects.  */
+      if (simple_operand_p (arg0)
+          && !TREE_SIDE_EFFECTS (arg0))
+	return build2_loc (loc,
+			   (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
+						     : TRUTH_OR_EXPR),
+			   type, arg0, arg1);
+    }
+
   return NULL_TREE;
 }
 
Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-2.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-2.c
@@ -0,0 +1,18 @@ 
+/* Skip on MIPS, S/390, and AVR due LOGICAL_OP_NON_SHORT_CIRCUIT, and
+   lower values in BRANCH_COST.  */
+/* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-* mn10300-*-*" } } } */
+/* { dg-options "-O2 -fdump-tree-gimple" } */
+/* { dg-options "-O2 -fdump-tree-gimple -march=i586" { target { i?86-*-* && ilp32 } } } */
+
+extern int doo1 (void);
+extern int doo2 (void);
+
+int bar (int a, int b, int c, int d)
+{
+  if (a && b && c && d)
+    return doo1 ();
+  return doo2 ();
+}
+
+/* { dg-final { scan-tree-dump-times "if " 2 "gimple" } } */
+/* { dg-final { cleanup-tree-dump "gimple" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-3.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-3.c
@@ -0,0 +1,18 @@ 
+/* Skip on MIPS, S/390, and AVR due LOGICAL_OP_NON_SHORT_CIRCUIT, and
+   lower values in BRANCH_COST.  */
+/* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-* mn10300-*-*" } } } */
+/* { dg-options "-O2 -fdump-tree-gimple" } */
+/* { dg-options "-O2 -fdump-tree-gimple -march=i586" { target { i?86-*-* && ilp32 } } } */
+
+extern int doo1 (void);
+extern int doo2 (void);
+
+int bar (int a, int c)
+{
+  if (a &&  c)
+    return doo1 ();
+  return doo2 ();
+}
+
+/* { dg-final { scan-tree-dump-times "if " 1 "gimple" } } */
+/* { dg-final { cleanup-tree-dump "gimple" } } */
Index: gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-4.c
===================================================================
--- /dev/null
+++ gcc-head/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifbranch-4.c
@@ -0,0 +1,18 @@ 
+/* Skip on MIPS, S/390, and AVR due LOGICAL_OP_NON_SHORT_CIRCUIT, and
+   lower values in BRANCH_COST.  */
+/* { dg-do compile { target { ! "mips*-*-* s390*-*-*  avr-*-* mn10300-*-*" } } } */
+/* { dg-options "-O2 -fdump-tree-gimple" } */
+/* { dg-options "-O2 -fdump-tree-gimple -march=i586" { target { i?86-*-* && ilp32 } } } */
+
+extern int doo1 (void);
+extern int doo2 (void);
+
+int bar (int a, int b, int c, int d)
+{
+  if ((a && b) && (c && d))
+    return doo1 ();
+  return doo2 ();
+}
+
+/* { dg-final { scan-tree-dump-times "if " 2 "gimple" } } */
+/* { dg-final { cleanup-tree-dump "gimple" } } */