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

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

On Mon, Jun 3, 2013 at 6:05 PM, Jeff Law <law@redhat.com> wrote:
> 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)

I agree that gimple optimizers should simplify things as much as possible.
Still we try to not generate regressions on the way.  So as an intermediate
guard I'd make sure the result of the bitwise op is only used in a GIMPLE_COND
(which means we can forward the resulting compare directly into the
GIMPLE_COND).
A comment should explain why we restrict the transform.

>
>>> +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?

We have BOOLEAN_TYPEs that do not have a TYPE_PRECISION of one
(but still are two-valued, and we assume those values are 0 and != 0 (eh)).
So there is code that treats BOOLEAN_TYPEs the same as TYPE_PRECISION
one types and there is code that does not (for example bitwise not is not
equal to truth not on such types).

Richard.

>>
>>> +    {
>>> +      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.
>
>