[RFA] Minor optimization of variable bit testing

[Jeff Law]

On 11/3/2021 2:15 AM, Richard Biener via Gcc-patches wrote:
> On Tue, Nov 2, 2021 at 4:53 PM Jeff Law <jlaw@tachyum.com> wrote:
>>
>> I was wandering spec chasing down instances where we should be
>> generating bit-test, bit-set and bit-clear types of instructions for our
>> target when I ran across a generic missed optimization in this space.
>>
>>
>> (((1 << N) & C) != 0)  -> (N == C')
>> (((1 << N) & C) == 0)  -> (N != C')
>>
>> Where C is a constant power of 2 and C' is log2 (C).
>>
>>
>>
>> That obviously avoids the shift by a variable amount and the bit masking
>> which is the primary effect.  I did see cases where we were able to
>> constant propagate into uses of N, but those were only in PHI nodes and
>> never triggered any real secondary effects in the cases I looked at.
>>
>>
>> Anyway, it's a fairly minor optimization, but with the analysis done and
>> patch in hand, it's silly not to take the easy win.
>>
>>
>> Bootstrapped and regression tested on x86_64 and verified that the
>> affected spec benchmark (gcc itself) still passes on our target.
>>
>> OK for the trunk?  Note I added the patterns at the end of match.pd.
>> Certainly open to moving them elsewhere.
> There are related patterns like
>
> /* (CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1)
>     (CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1)
>
> please move the new patterns next to those.
Will do.   FWIW, it feels like match.pd is getting a bit unwieldy in 
terms of being able to find things.  I wonder if we should be looking to 
break it up into multiple files.  Not critical of course, but it's grown 
to ~6k lines at this point.


>
> +/* ((1 << n) & M) != 0  -> n == log2 (M) */
> +(simplify
> + (ne
> +  (bit_and
> +   (nop_convert? (lshift integer_onep@0 @1)) integer_pow2p@2) integer_zerop@3)
> + (eq @1 { build_int_cst (integer_type_node,
> +                         wi::exact_log2 (wi::to_wide (@2))); }))
> +
> +/* ((1 << n) & M) == 0  -> n != log2 (M) */
> +(simplify
> + (eq
> +  (bit_and
> +   (nop_convert? (lshift integer_onep@0 @1)) integer_pow2p@2) integer_zerop@3)
> + (ne @1 { build_int_cst (integer_type_node,
> +                         wi::exact_log2 (wi::to_wide (@2))); }))
>
> you don't need @3 or @0 so no need to specify them.
Ah, I didn't know the language allowed us to do that.  Will do and 
adjust operand #s.



>   You can merge the
> patterns with
>
> (for cmp (ne eq)
>         icmp (eq ne)
Thanks.  I was pretty sure we we had this kind of mapping capability, 
now that I know what to look for, it's easy to find.


>    (simplify
>      (cmp
> +  (bit_and
>        (nop_convert? (lshift integer_onep @1)) integer_pow2p@2) integer_zerop)
>      (icmp @1 { wide_int_to_tree (TREE_TYPE (@1),
> +                         wi::exact_log2 (wi::to_wide (@2))); }))
>
> I belive the integer constant you build should be of the type of @1 (I
> fixed that above,
> also using wide_int_to_tree.  The pattern is written in a way that _could_ match
> vector operations and a vector by vector shift in which case the
> wi::to_wide would
> ICE - integer_pow2p currently does not match vector constants.  But maybe be
> defensive and add
>
>    (if (INTEGRAL_TYPE_P (TREE_TYPE (@1)))
>
> I think the patch is OK with those changes.
I'll add that test as well and retest.

Thanks,
jeff