Error in array-bound-check in the Dalvik JIT compiler?

[Javed Absar]

Hi 

Either I have misunderstood some-part or I think there is an error with the logic in 

dalvik/vm/compiler/Loop.c ... line 434-436. 

(First some context settting... 

DVM consider for array-bound-check (ABC) only those loops that :

1. have one basic induction variable ... lets say iterator 'i'

2. the branch condition compares i with a loop-independent-variable (lets say N) .... unless condition is LTZ or LEZ

3. If its a countup loop, then branch can be only GT or GTE. 

4. If its a count-down loop, then the branch can only be LT, LTE, LTZ or LEZ. 

5. array index expression can be of the type a[i+konstant]

6. minC, maxC are aggregated konstants for all references to the same array. Lets just assume there is only one ref for the point below

So, in the case of countup loop its like (e.g. i++)

OP_IF_GT vA<-i, vB<-N exit_the_loop_address                                .... (i.e. i > N exit the loop)

in the case of countdown loop (e.g. i--)

OP_IF_LT vA<-i, vB<-N exit_the_loop address                                  ... (i.e. i < N exit the loop)        

I am going to skip some parts now.... those who know the JIT code well.. will be able to follow easily.

Those who dont know the code cannot comment intelligently, anyways :)

For ABC, in the case of countup up (Loop.c 415-421) the lower bound check is done by 

comparing                " i0 + globalMinC >= 0 ". If false punt.        (globalMinc is a -ve value or 0)

i0 is the initial iterator value. 

This is fine. 

For ABC, in the case of CountDown (Loop.c 422-...) 

the CODE says, "in the case of OP_IF_LT do .vB++

What this means is - (below i have illustrated a countdown loop taking N=5)

Lets say 

i    Comparison            N                    Decision

10        <                      5       ?           no , please continue looping    

 9         <                      5       ?           no , please continue looping 

...

 6         <                      5       ?           no , please continue looping

 5         <                      5       ?           no , please continue looping

 4         <                      5       ?           yes, please exit loop.

So, the last valid value of i is N. But the code seems to say, its N+1

Now lets see for case of OP_IF_LTE 

10        <=                     5       ?           no , please continue looping    

 9         <=                     5       ?           no , please continue looping 

...

 6         <=                     5       ?           no , please continue looping

 5         <=                     5       ?           yes, please exit loop.

So, the last valid value of i is N+1. 

Basically, I think the LT and LTE case has been mixed up 

It should be N+1 for LTE (as shown above). The code instead does N+1 for the LT case.

Please comment

Bes Regards

Javed Absar 

--
my homepage: http://www.javedabsar.com

[Ben Cheng]

Thanks for reporting and your proposed fix is correct.

-Ben

--
You received this message because you are subscribed to the Google Groups "android-platform" group.
To post to this group, send email to android-...@googlegroups.com.
To unsubscribe from this group, send email to android-platfo...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/android-platform?hl=en.