8193935: RFR(S): Illegal countedLoops transformation

[Nils Eliasson]

I decided to make it a little more safe. Since this only happens when 
there is truncation, I guard the new check so it is only applied when 
there is truncation.

Also added some comments.

http://cr.openjdk.java.net/~neliasso/8193935/webrev.03

I will be running this patch together with the 8192992 fix through some 
extensive testing.

Regards,
Nils

On 2018-03-21 01:30, Vladimir Kozlov wrote:
> Okay. My mistake was that I thought incr_t is type of 'stride' (in 
> example it is '1'). Change seems good then.
>
> Can you submit performance testing to make sure we did not miss 
> something? This is very performance sensitive code.
>
> Thanks,
> Vladimir
>
> On 3/20/18 4:49 AM, Nils Eliasson wrote:
>> Hi Vladimir,
>>
>>
>> On 2018-03-19 22:31, Vladimir Kozlov wrote:
>>> Hi Nils,
>>>
>>> Do I miss something in explanation? The check you added should be 
>>> true for all normal loops:
>>
>> Yes, I need to add some proper documentation for this.
>>
>>>
>>> if (limit_t->_hi > incr_t->_hi) {
>>>   return false; // limit might be a value that incr never can reach
>>>
>>> Fro example:
>>>
>>> for (int i = 0; i < 10; i++) {}
>>
>> This would be:
>>
>> i1 <- 0;
>> loop:
>> i2 <- phi(0 , i3)
>> i3 <- add(i2, 1)
>> cmp (i3, 10)
>> jlt loop
>>
>> inct_t is the type for i3 - IntType[0, 10]
>> limit_t is IntType[10, 10]
>>
>> My case is something like:
>>
>> void testMethod(int[] array){
>>     int i = 0;
>>    while (true)
>>        sum + = array[i];
>>        i++;
>>        i = i && 0x7fff;
>>    }
>> }
>>
>> In this case incr_t is the type of i at the end of the loop (or 
>> before the loop-phi at the start)- which is IntType[0,0x7fff]
>>
>> If array is longer than 0x8000 this code should never terminate. If 
>> array is shorter, it will get an AIOOB.
>>
>> Counted loops transform this into:
>>
>>     int j = 0;
>>    while (true) {
>>        sum += array[j];
>>        j++;
>>    }
>>
>> Best  regards,
>> Nils
>>
>>>
>>> 10 > 1 and you will not convert this loop into counted.
>>>
>>> Thanks,
>>> Vladimir
>>>
>>> On 3/19/18 2:17 AM, Nils Eliasson wrote:
>>>> Hi,
>>>>
>>>> This bug was found in mpegaudio hiding behind the loop predication. 
>>>> The Counted loop transformation may loose a significant truncation 
>>>> which changes the behaviour of the program.
>>>>
>>>> CountedLoopNode::match_incr_with_optional_truncation finds the 
>>>> truncation Op_AndI(0x7fff) and sets trunc_t = TypeInt::CHAR. 
>>>> However the program does not use it for a char truncation, but a 
>>>> accessing an array as a circular buffer. (Any other mask would have 
>>>> hidden this problem since char truncation is the only one matched).
>>>>
>>>> A loop is succesfully matched as a countedloop, and when the trip 
>>>> counter is cloned it drops the truncation. In the intended 
>>>> char-case that is ok. In this case the truncation prevents the 
>>>> program from hitting an AIOOB.
>>>>
>>>> In the general case, if a truncated loop counter is compared to an 
>>>> array length (or any variable) it must be provable that the array 
>>>> length is less than the truncation, and then the truncation can be 
>>>> omitted. If the array length can be longer, the exit may never be 
>>>> taken - the loop may never terminate, and a counted loop transform 
>>>> can not be performed.
>>>>
>>>> One additional topic of discussion is if we really want to do 
>>>> counted loop transformations with a RangeCheck as exit point. 
>>>> Especially if the profiling shows that the RangeCheck never fails. 
>>>> In the loop that fails there are multiple exits, many which are 
>>>> RangeChecks.
>>>>
>>>> For additional optimization opportunities we could consider 
>>>> rotating the loop until a normal compare is the loop exit condition.
>>>>
>>>>
>>>> Image of significant parts of node graph (the entire loop with its 
>>>> multiple exits, is omitted): 
>>>> http://cr.openjdk.java.net/~neliasso/8193935/mpegaudio.png
>>>>
>>>> bug: https://bugs.openjdk.java.net/browse/JDK-8193935
>>>>
>>>> webrev: http://cr.openjdk.java.net/~neliasso/8193935/webrev.01
>>>>
>>>>
>>>> Please review,
>>>>
>>>> Nils Eliasson
>>>>
>>