8193935: RFR(S): Illegal countedLoops transformation

[Vladimir Kozlov]

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
>>>
>