Endless loops in computation code (1.6.0_22).

Dawid Weiss dawid.weiss at gmail.com
Fri Mar 25 01:01:55 PDT 2011

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 :) Is the full test showing this somewhere in OpenJDK
codebase?

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.

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
> >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20110325/bc4c9e7a/attachment-0001.html