GCC Bugzilla Bug 24980

GIJ segfaults on
java-puzzlers/5-exceptional-puzzlers/puzzle-45/Workout.java from Bloch
and Gafter's latest book.  (This "puzzle" is due to Jim Hugunin of
Jython and IronPython fame.)

| $ curl -O http://www.javapuzzlers.com/java-puzzlers.zip
|   % Total    % Received % Xferd  Average Speed   Time    Time     Time 
Current
|                                  Dload  Upload   Total   Spent    Left  Speed
| 100 61564  100 61564    0     0  37113      0  0:00:01  0:00:01 --:--:--
43957
| $ unzip -q java-puzzlers.zip 
| $ gcj -C java-puzzlers/5-exceptional-puzzlers/puzzle-45/Workout.java
| $ gij -classpath java-puzzlers/5-exceptional-puzzlers/puzzle-45 Workout
| Segmentation fault
| $ gcj --main=Workout
java-puzzlers/5-exceptional-puzzlers/puzzle-45/Workout.java
| $ ./a.out 
| Segmentation fault

The above is under the following version of GCJ:

| $ gcj --version
| gcj (GCC) 4.0.1 20050727 (Red Hat 4.0.1-5)
| Copyright (C) 2005 Free Software Foundation, Inc.
| This is free software; see the source for copying conditions.  There is NO
| warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

I also tried running this under three other 32-bit VMs: Sun 1.4.2_08,
BEA (build 1.4.2_05-b04), and IBM 1.4.2 (build cxia32142-20050609).

The only one that seems to run this program correctly is Sun's JVM.
(Given a limited maximum stack depth, the correct behavior for this
program is to run a few gazillion years and terminate successfully.
In Sun's case, the maximum stack depth is 1024 and the program can be
expected to run for about 10^300 years, give or take a few orders of
magnitude.)

IBM's 32-bit Linux JDK starts spewing out the following diagnostic:

| Stack overflow occurred outside JITted code or Interpreter.
| Searching for valid stack frames.
| Stack trace information below may not be accurate or complete.
|  It is provided for diagnostic purposes.
| Stack overflow occurred outside JITted code or Interpreter.
| Searching for valid stack frames.
| Stack trace information below may not be accurate or complete.
|  It is provided for diagnostic purposes.
|        at Workout.workHard
| Stack overflow occurred outside JITted code or Interpreter.
| Searching for valid stack frames.
| Stack trace information below may not be accurate or complete.
|  It is provided for diagnostic purposes.
|        at Workout.workHard

I had to Ctrl-C out of it after it generated 100,000+ lines of the
above.

BEA's JDK seems to do the right thing: run till the end of times.  On
closer inspection, it turns out to get a little hosed: it stops
responding to SIGTERM and SIGQUIT.

Bryce pointed out to me that Sun's behavior is not the only correct
interpretation of the above program's semantics.  If the runtime (or
the native ahead-of-time compiler) performs tail-call optimization,
then the program may loop forever without ever terminating.  After
thinking about this over the weekend, I came to realize that this is
wrong.  There seems to be no room for TCO in this particular case:

    private static void workHard() {
        try {
            workHard();
        } finally {
            workHard();
        }
    }

Note that while the recursive call in the "finally" block *is* in the
tail position, the call in the "try" block is not.  Therefore, the
recursion cannot be transformed into a loop.

I think this is a dup of bug 1373.

You should try  with optimizations turned on.

Created an attachment (id=10315) [edit]
BinaryCallTree.java

For my own education, I wrote a variation of Workout.java that prints
out the call tree in the Graphviz dot format.

Yeah, this may be a dup.

Bryce did mention that native-compiling this program with -O2 should
turn on the TCO.  There are two problems with this theory.  Number
one, it still segfaults for me:

| $ gcj -O2 --main=Workout Workout.java 
| $ ./a.out 
| Segmentation fault

This may be ok, because I'm using a rather old GCJ build.

Number two, the TCO cannot possibly be applied in this case.  (I can't
see how at the moment, but I'm willing to be convinced otherwise.)

Bryce ran the program under a newer version of GCJ and got some
equally bizarre results:

    public static void main(String[] args) {
        workHard();
        System.out.println("It's nap time.");
    }

In his case, it printed out "It's nap time."  This is incorrect,
because the program should either run out of stack and throw a
StackOverflowError, or it should it should run out of memory if stack
frames are allocated on the heap.  Under no circumstances can the
method return normally.  (I misspoke in my original post where I said
the program should, in theory, terminate successfully.)

So, yeah, if this is a dup, close it.  Note though this program
generates a much more interesting stress pattern than the one that aph
posted in bug 1373.

Created an attachment (id=10316) [edit]
call-tree-of-depth-4.png

So, speaking of stress patterns, this is what the call tree looks like
if you run attachment 10315 [edit] with the stack depth of 4.  In Sun's case,
it's a complete binary tree of depth 1024.

Blue arrows are calls made from within the "try" block.  Red arrows
are calls made from within the "finally" block.  Gray nodes are stack
overflow exceptions.

(In reply to comment #3)
> Number two, the TCO cannot possibly be applied in this case.  (I can't
> see how at the moment, but I'm willing to be convinced otherwise.)

Actually TCO cannot because you still need to unwind the stack but it would
always be calling the first workHard, even before the finnally one is called..

>Bryce ran the program under a newer version of GCJ and got some
>equally bizarre results:

It is not that bizarre as what is happening is that the function is being
marked as a "pure" function so it does nothing useful, so we remove it. 

Anyways I am marking this as a dup of bug 1373.  This comes down to the halting
problem.


*** This bug has been marked as a duplicate of 1373 ***

*** This bug has been marked as a duplicate of 1373 ***

(In reply to comment #5)
> It is not that bizarre as what is happening is that the function is
> being marked as a "pure" function so it does nothing useful, so we
> remove it.

Except that under Bryce's GCJ, the function terminates successfully
even if you throw in System.out.println's into it, thus tainting its
"purity".

> Except that under Bryce's GCJ, the function terminates successfully
> even if you throw in System.out.println's into it, thus tainting its
> "purity".

No, when I add a System.out.println("hi"), and compile with a trunk gcj, the
example behaves as expected - "hi" is printed many times until a stack overflow
eventually occurs, resulting in a segfault. Removing the try/finally, the
example runs forever thanks to tail-call optimization.