Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8345262

Loop peeling helps escape analysis

XMLWordPrintable

      Consider the following program (see also attached):

          public static void payload() {
              var list = new MyList();
              list.addNode();
              list.addNode();

              // ...

              list.cleanup();
          }

          static class MyList {
              Node first;

              public void addNode() {
                  Node newNode = new Node();
                  newNode.next = first;
                  first = newNode;
              }

              public void cleanup() {
                  Node current = first;
                  // uncomment to help EA
                  // if (current != null) {
                  // current.cleanup();
                  // current = current.next;
                  // }
                  while (current != null) {
                      current.cleanup();
                      current = current.next;
                  }
              }

              
              private static class Node {
                  Node next;

                  public void cleanup() {
                      // ...
                  }
              }

      TraceEscapeAnalysis reports several objects that are marked not scalar replaceable:

          JavaObject(1) NoEscape(NoEscape) NSR [ [ ]] 171 ConP === 0 [[ 418 105 ]] #null

          JavaObject(5) NoEscape(NoEscape) [ [ 117 ]] 105 Allocate === 5 6 7 8 1 (22 103 21 1 1 448 448 1 171 ) [[ 106 107 108 115 116 117 ]] rawptr:NotNull ( int:>=0, java/lang/Object:NotNull *, bool, top, bool ) LoopPeelingEA$MyList::addNode @ bci:0 (line 23) LoopPeelingEA::payload @ bci:9 (line 11) !jvms: LoopPeelingEA$MyList::addNode @ bci:0 (line 23) LoopPeelingEA::payload @ bci:9 (line 11)

          JavaObject(6) NoEscape(NoEscape) [ [ 225 ]] 213 Allocate === 119 116 210 8 1 (22 103 21 1 1 450 450 1 122 ) [[ 214 215 216 223 224 225 ]] rawptr:NotNull ( int:>=0, java/lang/Object:NotNull *, bool, top, bool ) LoopPeelingEA$MyList::addNode @ bci:0 (line 23) LoopPeelingEA::payload @ bci:13 (line 12) !jvms: LoopPeelingEA$MyList::addNode @ bci:0 (line 23) LoopPeelingEA::payload @ bci:13 (line 12)
      ...
          JavaObject(5) NoEscape(NoEscape) is NSR. is merged with other object: JavaObject(1) NoEscape(NoEscape) NSR , by node: Field(8) oop +12 ( 225 213P )[ 179 105P 171P [ ]] 280 AddP === _ 1 225 166 [[ 279 ]] !jvms: LoopPeelingEA$MyList::addNode @ bci:13 (line 24) LoopPeelingEA::payload @ bci:13 (line 12)

          JavaObject(1) NoEscape(NoEscape) NSR is NSR. is merged with other object: JavaObject(5) NoEscape(NoEscape) NSR , by node: Field(8) oop +12 ( 225 213P )[ 179 105P 171P [ ]] 280 AddP === _ 1 225 166 [[ 279 ]] !jvms: LoopPeelingEA$MyList::addNode @ bci:13 (line 24) LoopPeelingEA::payload @ bci:13 (line 12)

          JavaObject(6) NoEscape(NoEscape) is NSR. is merged with other object: JavaObject(5) NoEscape(NoEscape) NSR , by node: LocalVar(20) [ 230 426 213P 105P 171P [ 409b ]] 369 Phi === 443 230 426 [[ 409 409 ]] #LoopPeelingEA$MyList$Node:NotNull * Oop:LoopPeelingEA$MyList$Node:NotNull * !orig=[372],[386] !jvms: LoopPeelingEA$MyList::cleanup @ bci:9 (line 35) LoopPeelingEA::payload @ bci:17 (line 16)

          JavaObject(5) NoEscape(NoEscape) NSR is NSR. is merged with other object: JavaObject(6) NoEscape(NoEscape) NSR , by node: LocalVar(20) [ 230 426 213P 105P 171P [ 409b ]] 369 Phi === 443 230 426 [[ 409 409 ]] #LoopPeelingEA$MyList$Node:NotNull * Oop:LoopPeelingEA$MyList$Node:NotNull * !orig=[372],[386] !jvms: LoopPeelingEA$MyList::cleanup @ bci:9 (line 35) LoopPeelingEA::payload @ bci:17 (line 16)

          JavaObject(6) NoEscape(NoEscape) NSR is NSR. is merged with other object: JavaObject(1) NoEscape(NoEscape) NSR , by node: LocalVar(20) [ 230 426 213P 105P 171P [ 409b ]] 369 Phi === 443 230 426 [[ 409 409 ]] #LoopPeelingEA$MyList$Node:NotNull * Oop:LoopPeelingEA$MyList$Node:NotNull * !orig=[372],[386] !jvms: LoopPeelingEA$MyList::cleanup @ bci:9 (line 35) LoopPeelingEA::payload @ bci:17 (line 16)

          JavaObject(1) NoEscape(NoEscape) NSR is NSR. is merged with other object: JavaObject(6) NoEscape(NoEscape) NSR , by node: LocalVar(20) [ 230 426 213P 105P 171P [ 409b ]] 369 Phi === 443 230 426 [[ 409 409 ]] #LoopPeelingEA$MyList$Node:NotNull * Oop:LoopPeelingEA$MyList$Node:NotNull * !orig=[372],[386] !jvms: LoopPeelingEA$MyList::cleanup @ bci:9 (line 35) LoopPeelingEA::payload @ bci:17 (line 16)

      (Note that I've slightly modified the code to also print out the use node. See the attached IGV graph as well).

      The main culprit of the merges is the Phi node generated as a result of the while loop, merging current and null. If we manually peel a single loop iteration (un-comment the code in MyList::cleanup), the allocations go away/can be scalar replaced.

      It would be nice if C2 could do this peeling to help EA automatically, so that 1) user code does not have to change and 2) inlining is not affected by the extra peeled iteration being present in the bytecode (we've seen this being in issue in a real world use case).

            Unassigned Unassigned
            jvernee Jorn Vernee
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated: