hotspot: problem with bitwise rotation on PowerLE

[Volker Simonis]

On Tue, May 12, 2015 at 10:53 PM, Alexander Smundak <asmundak at google.com> wrote:
> I can confirm that the patch works. I tried to write the test that covers both
> 'rotlI_reg_immi8' and ' rotrI_reg_immi8' patterns but I didn't manage
> to match the latter,
> somehow all of the following methods inline to ROTLWI:
>
>   static int rotateRight1(int i, int distance) { return (i >>>
> distance) | (i << -distance); }
>   static int rotateRight2(int i, int distance) { return (i <<
> -distance) | (i >>> distance); }
>
> These two inline to
>     rotlwi Rx, Ry, (32-distance)
>
>   static int rotateLeft1(int i, int distance) { return (i << distance)
> | (i >>> -distance); }
>   static int rotateLeft2(int i, int distance) { return (i >>>
> -distance) | (i << distance); }
> And these to inline to
>     rotlwi Rx, Ry, distance
>

That's because ADLC is 'smart'. For the instruction 'rotlI_reg_immi8'
it generates two nodes, one with the verbatim match rule:

match(Set dst (OrI (LShiftI src lshift) (URShiftI src rshift)))

and another one with the rule:

match(Set dst (OrI (URShiftI src rshift) (LShiftI src lshift)))

This is because ADLC knows that "or" is commutative and automatically
generates nodes for both variants of the "or" clause to save us from
having to provide both versions manually. But in this case it happens
that the second version is equal to the matching pattern of
'rotrI_reg_immi8', so that one will never match.

> How can such a bug escape the hotspot test? I don't have access to
> JCK, but isn't it supposed to cover this?
>

It's a common misunderstanding that passing the JCK is a quality
statement. The JCK is merely a conformance test suite - it doesn't
check the performance, robustness or general stability of the VM under
test. There is for sure a test for Integer.rotateLeft() in the test
suite, but remember that for this error to occur, Integer.rotateLeft()
has to be called with immediates and it has to be called often enough
such that it gets compiled on C2 level.

> On Tue, May 12, 2015 at 11:31 AM, Volker Simonis
> <volker.simonis at gmail.com> wrote:
>> Hi,
>>
>> I think I've finally understood and fixed this issue.
>>
>> The problem was that we initially took the "rotate left/right by 8-bit
>> immediate" instructions from x86_64. But on x86_64 the rotate
>> instructions for 32-bit integers do in fact really take 8-bit
>> immediates (seems like the Intel guys had to many spare bits when they
>> designed their instruction set :) On the other hand, the rotate
>> instructions on Power only use 5 bit to encode the rotation distance.
>>
>> We do check for this limit, but only in the debug build. That's why
>> you saw the assertion in the fastdebug build.
>>
>> I think the right solution for this problem is to simply mask the
>> rotation distance with 0x1f  (which is equivalent to taking the
>> distance modulo 32).
>>
>> Can you please verify that the proposed fix also works for you on LE?
>>
>> https://bugs.openjdk.java.net/browse/JDK-8080190
>> http://cr.openjdk.java.net/~simonis/webrevs/2015/8080190/
>>
>> If yes I can send it out for review and push it to our jdk9 and jdk8u
>> repositories.
>>
>> @Jan: have you signed the Oracle Contributor Agreement or are you
>> covered by the company-wide IBM OCA? I'd like to take your test as a
>> regresstion test into the OpenJDK HotSpot repository, but this is only
>> possible if you're a Contributor[2].
>>
>> Thank you and best regards,
>> Volker
>>
>> PS: the issue didn't appear in our internal SAP JVM version because we
>> already mask the inputs of the corresponding shift nodes in the ideal
>> graph but for some unknown reasons this shared changes haven’t been
>> contributed along with our ppc port so far.
>>
>> [1] http://www.oracle.com/technetwork/community/oca-486395.html
>> [2] http://openjdk.java.net/bylaws#contributor
>>
>>
>> On Tue, May 12, 2015 at 2:38 PM, Volker Simonis
>> <volker.simonis at gmail.com> wrote:
>>> Hi,
>>>
>>> this problem is not LE-related. I could reproduce it on BE as well. I
>>> also don't think that the fix proposed by Jan is completely right. I
>>> think it only helps because it leads to another instruction being
>>> matched. The problem is that the URshift has a negative input which
>>> should not be. It should have been converted to it's positive
>>> equivalent modulo 32 (as described in the  JLS 15.19 -
>>> https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.19).
>>>
>>> Strange enough, in our internal version, the error doesn't occur so I
>>> should actually easy find the difference. Unfortunately, I didn't saw
>>> it until now :(
>>> I'll keep you posted once I found out more...
>>>
>>> Regards,
>>> Volker
>>>
>>> On Tue, May 12, 2015 at 6:06 AM, Alexander Smundak <asmundak at google.com> wrote:
>>>> Looking into this. Sorry for the late response, we were moved into a
>>>> different office over the weekend.
>>>>
>>>> On Fri, May 8, 2015 at 1:01 PM, Jan S Rellermeyer
>>>> <rellermeyer at us.ibm.com> wrote:
>>>>> I am helping people in IBM who have encountered a hotspot bug that surfaces
>>>>> when using bitwise rotations (such as through Integer.rotateRight). I have
>>>>> attached a small test program that illustrates the problem. When running
>>>>> this on Power LE (I don't think that anybody tried on BE, though) the
>>>>> results of the hash function are incorrect.
>>>>>
>>>>> The bug goes away when disabling inlining. After digging through the
>>>>> generated code I found out that it contained some suspicious fnmadd
>>>>> instructions where you would rather expect some kind of left rotate. I could
>>>>> track down that the bug was caused by the immediate value for the right
>>>>> shift constant of what should be a rlwinm node to be negative and thereby
>>>>> bleeding into the opcode (which unfortunately still created a valid Power
>>>>> instruction, namely the fnmadd). Running with a fastdebug build causes an
>>>>> assertion to fail.
>>>>>
>>>>> The attached patch does fix the problem and so does an alternative patch
>>>>> that replaces the URshift with a UShift but I am not entirely sure if this
>>>>> really fixes the root cause or rather just prevents the rotlI instruction
>>>>> from being matched by the ReduceInst.
>>>>>
>>>>> --Jan.
>>>>>
>>>>>
>>>>> Dr. Jan S. Rellermeyer
>>>>> IBM Research
>>>>> RSM - Austin Research Lab
>>>>> rellermeyer_at_us.ibm.com
>>>>> The University of Texas at Austin
>>>>> Adjunct Assistant Professor
>>>>> jrellerm_at_cs.utexas.edu
>>>>>
>>>>> (See attached file: hash.java)(See attached file: rotl.patch)