Endless loops in computation code (1.6.0_22).

[Tom Rodriguez]

On Mar 25, 2011, at 1:01 AM, Dawid Weiss wrote:

> 
> Thanks Tom (and Vladimir). Although I must say even though the explanation seems to be in plain English I will need to digest it a little bit to understand it :)

Yes it looks like English but it's really jargon.  The optimizer often wants loops that are shaped like:

if (guard) {
  do {
  } while (test);

The guard piece is a zero trip test since it skips over the loop if it won't execute at all.  The space between the if and the do is a useful place to put things that are loop invariant but only need to be computed if you actually enter the loop which is why we like this structure.  The remove empty loop code was replacing the loop with the result it produced but that's only valid if it already has a zero trip guard.  Pretty much all the time it does but in this case it didn't.

Note that neither your original program nor the test case have an obvious empty loop.  In both cases it results from optimizations on the original loop

> Is the full test showing this somewhere in OpenJDK codebase?

It's in the bug report and I made a regression test for it which I included in my fix.  http://cr.openjdk.java.net/~never/7024475/raw_files/new/test/compiler/7024475/Test7024475.java

> 
> As for a workaround to the original code: this is not anything critical (just a toy algorithmic project), so you don't need to bother thinking of a workaround. If it was something that we could trivially fix, fine, but if not -- so be it, no problem.

Ok.

tom

> 
> Dawid
> 
> 2011/3/24 Tom Rodriguez <tom.rodriguez at oracle.com>
> I finally tracked down this bug and it's an new issue.  There's an optimization that replaces empty loops with the final index they compute and it assumes that the loop already has a zero trip guard so that if we enter the loop we will go around the loop at least once.  For your complex loop combined with an OSR compile we get the right set of conditions for this.  This causes the loop to produce an incorrect value and resets the bounds of the iteration.
> 
> I simplified your original loop quite a bit and then Vladimir was able to build a really simple version of it.  I modified those bytecodes to be OSR like, taking all locals as incoming arguments and jumping to the OSR bci, and then used jode to produce source from those bytecodes.  That gave me this loop:
> 
>    static void test(Test test, int i, int c0, int j, int c1) {
>        for (;;) {
>            if (c1 > c0) {
>                if (c0 > 253) {
>                    throw new InternalError("c0 = " + c0);
>                }
>                int index = c0 * 256 + c1;
>                if (index == -1) return;
>                i = bucket_B[index];
>                if (1 < j - i && test != null)
>                    x1 = 0;
>                j = i;
>                c1--;
>            } else {
>                c0--;
>                if (j <= 0)
>                    break;
>                c1 = 255;
>            }
>        }
>    }
> 
> which shows the bug in every 1.6.0 release in both OSR and non-OSR compiles.  The bug report has the full test in it.  The fix is simply to ensure that this code has a zero trip guard, probably by reusing do_peeling to build one.  That produces a redundant test in the common case where there's already a guard though I suspect we can optimize that away.
> 
> As far as a workaround for your code, I'm not sure what to suggest.  I'll see if I can come up with something.
> 
> tom
> 
> On Mar 3, 2011, at 11:44 PM, Dawid Weiss wrote:
> 
> >
> > After watching maven download jars for 10 minutes, it actually ran the test and reproduced it.
> >
> > Ehm, I'm not a big fan of Maven myself, but trying to get used to what people use (and many people do use maven -- perhaps they need those 10 minutes to grab a coffee in the morning, don't know).
> >
> >  I put together a little main to run the test manually and just reproduced it with -XX:+PrintCompilation.  It hung right after it printed this:
> >
> >  3%      org.jsuffixarrays.DivSufSort::sortTypeBstar @ 979 (1125 bytes)
> >
> > Ok, so it must be Maven's test plugin messing with the stdout/stderr log order then. I'm glad you could reproduce it.
> >
> > so it's possible it's a bug with with on stack replacement.  I've reproduced it with the latest 1.7 as well so it's something we haven't seen before.  I filed 7024475 for this and put you on the interest list.  I can't reproduce it in 6u12 but I can in 6u14 so I think it appeared there.
> >
> > Great, thanks. I fiddled with that code a little bit moving loop counter increments here and there, but it seems to be fairly resilient to where they are (as long as the logic doesn't change). Interestingly, moving the sysout does seem to fix things (if you move it after the if in the inside loop).
> >
> > I appreciate your help, Tom. This is truly fascinating stuff.
> > Dawid
> >
> >
> 
>