8193935: RFR(S): Illegal countedLoops transformation

[Nils Eliasson]

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