This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Improve folding of bitwise ops on booleans


On Fri, May 31, 2013 at 10:18 PM, Jeff Law <law@redhat.com> wrote:
>
> This is an implementation to fix a missed optimization pointed out to me by
> Kai.
>
> In all these examples, assume a & b are single bit types.
>
> ~a && b --> a < b

For a signed 1-bit type you'll have values -1, 0 and clearly

  0 < -1

is false while ~0 & -1 is non-zero.

So I believe you have to restrict these transforms to signed 1-bit values
or adjust the folding appropriately.  Besides that, ...

> a && ~b --> b < a
> ~a || b --> a <= b
> a && ~b --> b <= a

I wonder if these are really a simplification if the result is not used
exclusively in a conditional jump.  Because for setting a register
to a < b you'll likely get worse code than using ~a & b (given that
many ISAs have a and-not instruction).  Of course you may argue
that's a bug in the RTL / target piece (getting different code for
a < b vs. ~a & b) and a < b is shorter on the tree level.

More comments in-line.

> This happens with some regularity in GCC itself, though it's not as
> pervasive as some of the other missed optimizations I've run into.
>
> This could have gone into fold-const.c or tree-forwprop.   fold-const.c
> isn't as useful as would need to see the entire expression as a single tree
> node.  tree-forwprop.c can follow the use-def links and discover more
> opportunities even when the expressions span two source statements or are
> exposed by other optimizations.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu.
>
> OK for the trunk?
>
>
> commit 2b61de6f70576105fe6ada31618db23857f9c902
> Author: Jeff Law <law@redhat.com>
> Date:   Fri May 31 14:16:27 2013 -0600
>
>             * tree-ssa-forwprop.c (simplify_bitwise_binary_boolean): New
>             * function.
>             (simplify_bitwise_binary): Use it to simpify certain binary ops
> on
>             booleans.
>
>             * gcc.dg/tree-ssa/forwprop-27.c: New test.
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 396111e..7f027b0 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2013-05-31  Jeff Law  <law@redhat.com>
> +
> +       * tree-ssa-forwprop.c (simplify_bitwise_binary_boolean): New
> function.
> +       (simplify_bitwise_binary): Use it to simpify certain binary ops on
> +       booleans.
> +
>  2013-05-28  Steve Ellcey  <sellcey@mips.com>
>
>         * config/mips/mips-cpus.def (mips32r2): Change processor type.
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 869371a..6f80afb 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,7 @@
> +2013-05-31  Jeff Law  <law@redhat.com>
> +
> +       * gcc.dg/tree-ssa/forwprop-27.c: New test.
> +
>  2013-05-28  Balaji V. Iyer  <balaji.v.iyer@intel.com>
>
>         * c-c++-common/cilk-plus/AN/array_test1.c: New test.
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-27.c
> b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-27.c
> new file mode 100644
> index 0000000..75e935d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-27.c
> @@ -0,0 +1,78 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-forwprop1" } */
> +
> +extern char * frob (void);
> +extern _Bool testit(void);
> +
> +test (int code)
> +{
> +  char * temp = frob();;
> +  int rotate = (code == 22);
> +  if (temp == 0 && !rotate)
> +      oof();
> +}
> +
> +test_2 (int code)
> +{
> +  char * temp = frob();
> +  int rotate = (code == 22);
> +  if (!rotate && temp == 0)
> +      oof();
> +}
> +
> +
> +test_3 (int code)
> +{
> +  char * temp = frob();
> +  int rotate = (code == 22);
> +  if (!rotate || temp == 0)
> +      oof();
> +}
> +
> +
> +test_4 (int code)
> +{
> +  char * temp = frob();
> +  int rotate = (code == 22);
> +  if (temp == 0 || !rotate)
> +      oof();
> +}
> +
> +
> +test_5 (int code)
> +{
> +  _Bool temp = testit();;
> +  _Bool rotate = (code == 22);
> +  if (temp == 0 && !rotate)
> +      oof();
> +}
> +
> +test_6 (int code)
> +{
> +  _Bool temp = testit();
> +  _Bool rotate = (code == 22);
> +  if (!rotate && temp == 0)
> +      oof();
> +}
> +
> +
> +test_7 (int code)
> +{
> +  _Bool temp = testit();
> +  _Bool rotate = (code == 22);
> +  if (!rotate || temp == 0)
> +      oof();
> +}
> +
> +
> +test_8 (int code)
> +{
> +  _Bool temp = testit();
> +  _Bool rotate = (code == 22);
> +  if (temp == 0 || !rotate)
> +      oof();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Replaced" 8 "forwprop1"} } */
> +
> +
> diff --git a/gcc/tree-ssa-forwprop.c b/gcc/tree-ssa-forwprop.c
> index 6043d31..8c3f08b 100644
> --- a/gcc/tree-ssa-forwprop.c
> +++ b/gcc/tree-ssa-forwprop.c
> @@ -1870,6 +1870,45 @@ hoist_conversion_for_bitop_p (tree to, tree from)
>    return false;
>  }
>
> +/* GSI points to a statement of the form
> +
> +   result = OP0 CODE OP1
> +
> +   Where OP0 and OP1 are single bit SSA_NAMEs and CODE is either
> +   BIT_AND_EXPR or BIT_IOR_EXPR.
> +
> +   If OP0 is fed by a bitwise negation of another single bit SSA_NAME,
> +   then we can simplify the two statements into a single LT_EXPR or LE_EXPR
> +   when code is BIT_AND_EXPR and BIT_IOR_EXPR respectively.
> +
> +   If a simplification is mode, return TRUE, else return FALSE.  */
> +static bool
> +simplify_bitwise_binary_boolean (gimple_stmt_iterator *gsi,
> +                                enum tree_code code,
> +                                tree op0, tree op1)
> +{
> +  gimple op0_def_stmt = SSA_NAME_DEF_STMT (op0);
> +
> +  if (!is_gimple_assign (op0_def_stmt)
> +      || (gimple_assign_rhs_code (op0_def_stmt) != BIT_NOT_EXPR))
> +    return false;
> +
> +  tree x = gimple_assign_rhs1 (op0_def_stmt);
> +  if (TREE_CODE (x) == SSA_NAME
> +      && INTEGRAL_TYPE_P (TREE_TYPE (x))
> +      && TYPE_PRECISION (TREE_TYPE (x)) == 1)

Do these transforms not work for BOOLEAN_TYPE as well?

> +    {
> +      gimple stmt = gsi_stmt (*gsi);
> +      gimple_assign_set_rhs1 (stmt, x);
> +      gimple_assign_set_rhs2 (stmt, op1);
> +      gimple_assign_set_rhs_code (stmt, code == BIT_AND_EXPR ? LT_EXPR :
> LE_EXPR);
> +      update_stmt (gsi_stmt (*gsi));

No need to query gsi_stmt again, it cannot change.

> +      return true;
> +    }
> +  return false;
> +
> +}
> +
>  /* Simplify bitwise binary operations.
>     Return true if a transformation applied, otherwise return false.  */
>
> @@ -2118,8 +2157,26 @@ simplify_bitwise_binary (gimple_stmt_iterator *gsi)
>               return true;
>             }
>         }
> -    }
>
> +      /* If arg1 and arg2 are booleans (or any single bit type)
> +         then try to simplify:
> +
> +        (~X & Y) -> X < Y
> +        (X & ~Y) -> Y < X
> +         (~X | Y) -> X <= Y
> +         (X | ~Y) -> Y <= X  */
> +      if (TREE_CODE (arg1) == SSA_NAME
> +         && TREE_CODE (arg2) == SSA_NAME
> +         && INTEGRAL_TYPE_P (TREE_TYPE (arg1))
> +         && TYPE_PRECISION (TREE_TYPE (arg1)) == 1
> +         && TYPE_PRECISION (TREE_TYPE (arg2)) == 1)
> +       {
> +         if (simplify_bitwise_binary_boolean (gsi, code, arg1, arg2))
> +           return true;
> +         if (simplify_bitwise_binary_boolean (gsi, code, arg2, arg1))
> +           return true;
> +       }
> +    }
>    return false;
>  }
>
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]