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

[Richard Guenther <richard dot guenther at gmail dot com>]

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" } } */
>