Wrong call-tree output when using -H:+PrintAnalysisCallTree

[zakkak]

Describe the issue
Using -H:+PrintAnalysisCallTree on the following java example:

public class CallTree {
    private static void callA() {
        callB(true);
        callB(false);
    }

    private static void callB(boolean cond) {
        if (cond) {
            callD(true);
        }
    }

    private static void callD(boolean cond) {
        if (cond) {
            callC();
        } else {
            System.out.println("Hello D");
        }
    }

    private static void callC() {
        System.out.println("Hello C");
    }

    private static void callW() {
        callD(false);
    }

    private static void callX() {
        callD(false);
    }

    private static void callZ() {
        callD(false);
    }

    public static void main(String[] args) {
        callA();
        callW();
        callX();
        callZ();
    }
}

results in the following call tree:

├── entry com.oracle.svm.core.code.IsolateEnterStub.JavaMainWrapper_run_5087f5482cc9a6abc971913ece43acb471d2631b(int, org.graalvm.nativeimage.c.type.CCharPointerPointer):int id=85 
│   └── directly calls com.oracle.svm.core.JavaMainWrapper.run(int, org.graalvm.nativeimage.c.type.CCharPointerPointer):int id=693 @bci=2 
│       └── directly calls com.oracle.svm.core.JavaMainWrapper.runCore():int id=1029 @bci=0 
│           ├── directly calls CallTree.main(java.lang.String[]):void id=1402 @bci=66 
│           │   ├── directly calls CallTree.callA():void id=1973 @bci=0 
│           │   │   ├── directly calls CallTree.callB(boolean):void id=2939 @bci=1 
│           │   │   │   └── directly calls CallTree.callD(boolean):void id-ref=2940 @bci=5 
│           │   │   └── directly calls CallTree.callB(boolean):void id-ref=2939 @bci=5 
│           │   ├── directly calls CallTree.callW():void id=1974 @bci=3 
│           │   │   └── directly calls CallTree.callD(boolean):void id=2940 @bci=1 
│           │   │       ├── directly calls CallTree.callC():void id=3797 @bci=4 
│           │   │       │   └── virtually calls java.io.PrintStream.println(java.lang.String):void @bci=5
│           │   │       │       └── is overridden by java.io.PrintStream.println(java.lang.String):void id-ref=938 
│           │   │       └── virtually calls java.io.PrintStream.println(java.lang.String):void @bci=15
│           │   │           └── is overridden by java.io.PrintStream.println(java.lang.String):void id-ref=938 
│           │   ├── directly calls CallTree.callX():void id=1975 @bci=6 
│           │   │   └── directly calls CallTree.callD(boolean):void id-ref=2940 @bci=1 
│           │   └── directly calls CallTree.callZ():void id=1976 @bci=9 
│           │       └── directly calls CallTree.callD(boolean):void id-ref=2940 @bci=

while I would expect something like the following:

├── entry com.oracle.svm.core.code.IsolateEnterStub.JavaMainWrapper_run_5087f5482cc9a6abc971913ece43acb471d2631b(int, org.graalvm.nativeimage.c.type.CCharPointerPointer):int id=85 
│   └── directly calls com.oracle.svm.core.JavaMainWrapper.run(int, org.graalvm.nativeimage.c.type.CCharPointerPointer):int id=693 @bci=2 
│       └── directly calls com.oracle.svm.core.JavaMainWrapper.runCore():int id=1029 @bci=0 
│           ├── directly calls CallTree.main(java.lang.String[]):void id=1402 @bci=66 
│           │   ├── directly calls CallTree.callA():void id=1973 @bci=0 
│           │   │   ├── directly calls CallTree.callB(boolean):void id=2939 @bci=1 
│           │   │   │   └── directly calls CallTree.callD(boolean):void id-ref=2940 @bci=5 
│           │   │   │         └── directly calls CallTree.callC():void id=3797 @bci=4 
│           │   │   │             └── virtually calls java.io.PrintStream.println(java.lang.String):void @bci=5
│           │   │   │                 └── is overridden by java.io.PrintStream.println(java.lang.String):void id-ref=938 
│           │   │   └── directly calls CallTree.callB(boolean):void id-ref=2939 @bci=5 
│           │   ├── directly calls CallTree.callW():void id=1974 @bci=3 
│           │   │   └── directly calls CallTree.callD(boolean):void id=2940 @bci=1 
│           │   │       └── virtually calls java.io.PrintStream.println(java.lang.String):void @bci=15
│           │   │           └── is overridden by java.io.PrintStream.println(java.lang.String):void id-ref=938 
│           │   ├── directly calls CallTree.callX():void id=1975 @bci=6 
│           │   │   └── directly calls CallTree.callD(boolean):void id-ref=2940 @bci=1 
│           │   │       └── virtually calls java.io.PrintStream.println(java.lang.String):void @bci=15
│           │   │           └── is overridden by java.io.PrintStream.println(java.lang.String):void id-ref=938 
│           │   └── directly calls CallTree.callZ():void id=1976 @bci=9 
│           │       └── directly calls CallTree.callD(boolean):void id-ref=2940 @bci=
│           │           └── virtually calls java.io.PrintStream.println(java.lang.String):void @bci=15
│           │               └── is overridden by java.io.PrintStream.println(java.lang.String):void id-ref=938 

Steps to reproduce the issue
Please include both build steps as well as run steps

1. Copy the above Java example to CallTree.java
2. javac CallTree.java
3. native-image -H:+PrintAnalysisCallTree CallTree
4. grep -C10 CallTree reports/call_tree_calltree_*.txt

Describe GraalVM and your environment:

• GraalVM version: CE 21.0.0
• JDK major version: 11
• OS: Fedora 33
• Architecture: AMD64

[christianwimmer]

So when I look at the diff between the actual out and what you expect, then

1. you expect callC to be printed at a higher depth, and
2. callees of callD printed multiple times, for every occurrence of callD.

But we want to have methods at the lowest depth possible and without repetition. Why would you want to change that?

[zakkak]

1. you expect `callC` to be printed at a higher depth, and

If I am not mistaken, callC is only reachable though main -> callA -> callB -> callD, there is no way for it to be reached through main -> callW -> callD.

2. callees of `callD` printed multiple times, for every occurrence of `callD`.

If not printed multiple times how can we know that callD is reachable from multiple methods?
(I might be misusing this output to figure out all the possible call chains that lead to a method being run)

[christianwimmer]

ad 1) Our static analysis (like about every other static analysis) does not look at primitive values. So even if for you it is obvious that a constant parameter false passed in to a method makes some branch in that method unreachable, the static analysis looks at each method independently.

ad 2) Note that callD shows up multiple times in the tree. Once with all its children and the marker id=2940. The other times without children and the marker id-ref=2940. So you can manually search for these strings in the tree. In a textual representation of a graph as a tree, there is no other option.

[zakkak]

Interesting, thanks for the explanation Christian!

[christianwimmer]

And for the record: We have started working on method inlining before static analysis, and will expand that work in the future. That means for really small methods (which in your example is the case), method inlining before static analysis will at some point in the future be able to inline all your call* methods into main and as part of that method inlining perform constant folding. That means in your example the static analysis will actually analyze method main that invokes System.out.println a few times.

No idea yet how that will show up in the text format of the call tree printing, maybe something like directly calls println via inlined callA -> callW -> CallD -> callC