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

[Jeff Law <law at redhat dot com>]

On 06/03/2013 02:24 AM, Richard Biener wrote:
> 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.
Sigh.  Yes.

> 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.
The gimple optimizers should be looking to simplify things to the 
fullest extent possible at the gimple level and let the backend make the 
determination to use and-not if such an insn is available.

The counter to that argument of leaving it to the backend to recover the 
and-not for is that the backend doesn't typically see these as single 
bit operations which makes turning the relational back into an and-not 
sequence considerably more difficult.

Do we consider this enough of an issue to want to avoid going down this 
path? (in which case we'll file the example code as a missed-opt PR and 
attach the code and pointer to this thread for future reference)

> > +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?
Yes.  Booleans are integral types with a single bit of precision, right? 
 So this check should allow boolean types.  What am I missing?

> > +    {
> > +      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.
I'd have to check on that; I think this was cribbed from another 
transformation in tree-ssa-reassoc.