[PATCH, GCC] PR middle-end/55299, fold bitnot through ASR and rotates

[Marc Glisse]

On Tue, 17 May 2016, Richard Biener wrote:

> On Fri, May 13, 2016 at 3:36 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> On Fri, 13 May 2016, Mikhail Maltsev wrote:
>>
>>>> I don't know if we might want some :c / single_use restrictions, maybe on
>>>> the
>>>> outer convert and the rshift/rotate.
>>>>
>>> I don't think :c can be used here.
>>
>>
>> Oups, typo for :s.
>>
>>> As for :s, I added it, as you suggested.
>>
>>
>> :s will be ignored when there is no conversion, but I think that's good
>> enough for now.
>
> Yeah.  Doing :s twice as done in the patch works though.

I meant that the output will be a single instruction, and thus any :s will 
be ignored (I think).

>>> Also, I tried to add some more test cases for rotate with conversions, but
>>> unfortunately GCC does not recognize rotate pattern, when narrowing
>>> conversions
>>> are present.
>>
>>
>> It is usually easier to split your expression into several assignments.
>> Untested:
>>
>> int f(long long a, unsigned long n){
>>   long long b = ~a;
>>   unsigned long c = b;
>>   unsigned long d = ROLL (c, n);
>>   int e = d;
>>   return ~e;
>> }
>>
>> this way the rotate pattern is detected early (generic) with no extra
>> operations to confuse the compiler, while your new transformation will
>> happen in gimple (most likely the first forwprop pass).
>>
>> The patch looks good to me, now wait for Richard's comments.
>
> Are you sure narrowing conversions are valid for rotates?

My reasoning is that narrowing conversions and bit_not commute (sign 
extensions should be fine as well IIRC). So you can essentially pull 
convert1 out and push convert2 down to @1 (notice how the the result 
converts the input and the output), and simplify the middle (rotate and 
bit_not commute) without any conversion.

Note that an alternative way to handle the transformation would be to fix 
a canonical order for some things that commute. Turn non-extending convert 
of bit_not into bit_not of convert, turn rotate of bit_not to bit_not of 
rotate (or the reverse, whatever), etc. If we are lucky, this might move 
the 2 bit_not next to each other, where they can cancel out. But that's 
more ambitious.

I heard that llvm and visual studio were using a prover for such 
transforms. Without going that far, it might be good to use some 
automation to check that a transform works say for all values of all types 
of precision at most 4 or something, if someone is motivated...

> (char)short_var <<r 8 == (char)short_var but short_var << r8 is its upper byte.
>
> so at least for the conversion inside the rotate (and shift as well)
> only nop-conversions look valid to me.

Notice that the rotation is done in the type of @0 both before and after.

-- 
Marc Glisse