Re: RFC: Two minor optimization patterns

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

On Wed, Jan 14, 2015 at 1:23 PM, Rasmus Villemoes <rv@rasmusvillemoes.dk> wrote:
> On Wed, Jan 14 2015, Richard Biener <richard.guenther@gmail.com> wrote:
>
>> On Tue, Jan 13, 2015 at 11:47 PM, Andrew Pinski <pinskia@gmail.com> wrote:
>>> On Tue, Jan 13, 2015 at 2:41 PM, Rasmus Villemoes <rv@rasmusvillemoes.dk> wrote:
>>>> [My first attempt at submitting a patch for gcc, so please forgive me
>>>> if I'm not following the right protocol.]
>>>
>>> There are a few things missing.  For one, a testcase or two for the
>>> added optimizations.
>
> I'll see what I can come up with. Thanks for the pointers.
>
>>>> Sometimes rounding a variable to the next even integer is written x += x
>>>> & 1. This usually means using an extra register (and hence at least an
>>>> extra mov instruction) compared to the equivalent x = (x + 1) & ~1. The
>>>> first pattern below tries to do this transformation.
>>>>
>>>> While playing with various ways of rounding down, I noticed that gcc
>>>> already optimizes all of x-(x&3), x^(x&3) and x&~(x&3) to simply
>>>> x&~3.
>>
>> Does it also handle x+(x&3)?
>
> I'm not sure what 'it' refers to, and I'm also not sure how you think
> x+(x&3) could be rewritten.

I was just guessing.

>> Where does it handle x - (x&3)?
>
> If by 'it' you mean gcc, I tried looking for a pattern matching this,
> but couldn't find it, so I don't know where it is handled. I can just
> see by running gcc-5.0 -fdump-tree-original -O2 -c opt.c that "x - (x &
> 3)" is rewritten as x & -4 (which is of course the same as x & ~3).

That's done in fold-const.c:fold_binary_loc here:

          /* Fold A - (A & B) into ~B & A.  */
          if (!TREE_SIDE_EFFECTS (arg0)
              && TREE_CODE (arg1) == BIT_AND_EXPR)
            {
...

(note that patterns are not fully moved to match.pd yet)

> Btw,
> I now see that neither x&~(x&3) or x&~(x&y) are rewritten that early,
> but objdump -d shows that the end result is the same.
>
>> That is, doesn't the pattern also work for constants other than 1?
>
> Here I assume that 'the pattern' refers to the first pattern, and the
> answer is 'not immediately'. To round up a number to the next multiple
> of 2^k we need to add the negative of that number modulo 2^k. It just so
> happens that for k=1 we have x==-x for both possible values of x. So
> with a little tweak, this does in fact lead to an optimization
> opportunity, namely x + ((-x) & m) -> (x + m) & ~m whenever m is one
> less than a power of 2. I don't know how to check for m satisfying this
> in the match.pd language.

you'd need to write some C code involving trees in a if/with.  We do
have a integer_pow2p predicate but not a integer_one_less_than_pow2p
one.

>
>> Please put it before the abs simplifications after the last one handing
>> bit_and/bit_ior.
>
> OK, will do.

Thanks,
Richard.

> Rasmus