Mercurial > hg > truffle

changeset 19638:96cf6f7678d2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add test case and support for nested loops for Truffle bytecode interpreters.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Sat, 28 Feb 2015 14:54:59 +0100
parents 86909168a529
children 78f7c16c9bee
files graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java
diffstat 2 files changed, 55 insertions(+), 34 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Sat Feb 28 14:54:29 2015 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Sat Feb 28 14:54:59 2015 +0100
@@ -331,6 +331,7 @@
                     }
 
                     if (this.mergeExplosions) {
+                        Debug.dump(currentGraph, "Before loop detection");
                         detectLoops(startInstruction);
                     }
 
@@ -373,7 +374,6 @@
                                 LoopBeginNode loopBegin = (LoopBeginNode) ((EndNode) merge.next()).merge();
                                 LoopEndNode loopEnd = currentGraph.add(new LoopEndNode(loopBegin));
                                 endNode.replaceAndDelete(loopEnd);
-                                System.out.println("Cycle detected! root node: " + n);
                             } else if (visited.contains(n)) {
                                 // Normal merge into a branch we are already exploring.
                             } else {
@@ -384,6 +384,7 @@
                     }
                 }
 
+                Debug.dump(currentGraph, "After loops detected");
                 insertLoopEnds(startInstruction);
             }
 
@@ -413,6 +414,17 @@
                 for (int i = loopBegins.size() - 1; i >= 0; --i) {
                     LoopBeginNode loopBegin = loopBegins.get(i);
                     insertLoopExits(loopBegin, innerLoopsMap);
+                    if (GraalOptions.DumpDuringGraphBuilding.getValue()) {
+                        Debug.dump(currentGraph, "After building loop exits for %s.", loopBegin);
+                    }
+                }
+
+                // Remove degenerated merges with only one predecessor.
+                for (LoopBeginNode loopBegin : loopBegins) {
+                    Node pred = loopBegin.forwardEnd().predecessor();
+                    if (pred instanceof MergeNode) {
+                        MergeNode.removeMergeIfDegenerated((MergeNode) pred);
+                    }
                 }
             }
 
@@ -429,23 +441,28 @@
 
                 while (!stack.isEmpty()) {
                     Node current = stack.pop();
+                    if (current == loopBegin) {
+                        continue;
+                    }
                     for (Node pred : current.cfgPredecessors()) {
-                        if (pred instanceof LoopExitNode) {
-                            // Inner loop
-                            LoopExitNode loopExitNode = (LoopExitNode) pred;
-                            LoopBeginNode innerLoopBegin = loopExitNode.loopBegin();
-                            if (!visited.isMarked(innerLoopBegin)) {
-                                stack.push(innerLoopBegin);
-                                visited.mark(innerLoopBegin);
-                                innerLoopBegins.add(innerLoopBegin);
+                        if (!visited.isMarked(pred)) {
+                            visited.mark(pred);
+                            if (pred instanceof LoopExitNode) {
+                                // Inner loop
+                                LoopExitNode loopExitNode = (LoopExitNode) pred;
+                                LoopBeginNode innerLoopBegin = loopExitNode.loopBegin();
+                                if (!visited.isMarked(innerLoopBegin)) {
+                                    stack.push(innerLoopBegin);
+                                    visited.mark(innerLoopBegin);
+                                    innerLoopBegins.add(innerLoopBegin);
+                                }
+                            } else {
+                                if (pred instanceof ControlSplitNode) {
+                                    ControlSplitNode controlSplitNode = (ControlSplitNode) pred;
+                                    controlSplits.add(controlSplitNode);
+                                }
+                                stack.push(pred);
                             }
-                        } else if (!visited.isMarked(pred)) {
-                            if (pred instanceof ControlSplitNode) {
-                                ControlSplitNode controlSplitNode = (ControlSplitNode) pred;
-                                controlSplits.add(controlSplitNode);
-                            }
-                            stack.push(pred);
-                            visited.mark(pred);
                         }
                     }
                 }
@@ -463,6 +480,9 @@
 
                 for (LoopBeginNode inner : innerLoopBegins) {
                     addLoopExits(loopBegin, inner, innerLoopsMap, visited);
+                    if (GraalOptions.DumpDuringGraphBuilding.getValue()) {
+                        Debug.dump(currentGraph, "After adding loop exits for %s.", inner);
+                    }
                 }
 
                 innerLoopsMap.put(loopBegin, innerLoopBegins);
@@ -1648,7 +1668,7 @@
                         // time mark the context loop begin as hit during the current
                         // iteration.
                         if (this.mergeExplosions) {
-                            this.addToMergeCache(state.copy(), nextPeelIteration);
+                            this.addToMergeCache(state, nextPeelIteration);
                         }
                         context.targetPeelIteration[context.targetPeelIteration.length - 1] = nextPeelIteration++;
                         if (nextPeelIteration > MaximumLoopExplosionCount.getValue()) {
@@ -1879,6 +1899,8 @@
                     setEntryState(block, this.getCurrentDimension(), frameState.copy());
 
                     Debug.log("  created loop header %s", loopBegin);
+                } else if (block.isLoopHeader && explodeLoops && this.mergeExplosions) {
+                    frameState = frameState.copy();
                 }
                 assert lastInstr.next() == null : "instructions already appended at block " + block;
                 Debug.log("  frameState: %s", frameState);
--- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java	Sat Feb 28 14:54:29 2015 +0100
+++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java	Sat Feb 28 14:54:59 2015 +0100
@@ -100,19 +100,19 @@
                 switch (bc) {
                     case Bytecode.CONST:
                         value = bytecodes[bci + 1];
-                        trace("%d: CONST %s", bci, value);
+                        trace("%d (%d): CONST %s", bci, topOfStack, value);
                         setInt(frame, ++topOfStack, value);
                         bci = bci + 2;
                         continue;
 
                     case Bytecode.RETURN:
-                        trace("%d: RETURN", bci);
+                        trace("%d (%d): RETURN", bci, topOfStack);
                         return getInt(frame, topOfStack);
 
                     case Bytecode.ADD: {
                         int left = getInt(frame, topOfStack);
                         int right = getInt(frame, topOfStack - 1);
-                        trace("%d: ADD %d %d", bci, left, right);
+                        trace("%d (%d): ADD %d %d", bci, topOfStack, left, right);
                         setInt(frame, topOfStack - 1, left + right);
                         topOfStack--;
                         bci = bci + 1;
@@ -120,7 +120,7 @@
                     }
 
                     case Bytecode.IFZERO:
-                        trace("%d: IFZERO", bci);
+                        trace("%d (%d): IFZERO", bci, topOfStack);
                         if (getInt(frame, topOfStack--) == 0) {
                             bci = bytecodes[bci + 1];
                             continue;
@@ -130,18 +130,18 @@
                         }
 
                     case Bytecode.POP:
-                        trace("%d: POP", bci);
+                        trace("%d (%d): POP", bci, topOfStack);
                         topOfStack--;
                         bci++;
                         continue;
 
                     case Bytecode.JMP:
-                        trace("%d: JMP", bci);
+                        trace("%d (%d): JMP", bci, topOfStack);
                         bci = bytecodes[bci + 1];
                         continue;
 
                     case Bytecode.DUP:
-                        trace("%d: DUP", bci);
+                        trace("%d (%d): DUP", bci, topOfStack);
                         setInt(frame, topOfStack + 1, getInt(frame, topOfStack));
                         topOfStack++;
                         bci++;
@@ -236,20 +236,19 @@
         assertPartialEvalEqualsAndRunsCorrect(new Program("simpleLoopProgram", bytecodes, 0, 3));
     }
 
-    @Ignore
     @Test
     public void nestedLoopsProgram() {
         byte[] bytecodes = new byte[]{
         /* 0: */Bytecode.CONST,
         /* 1: */42,
         /* 2: */Bytecode.CONST,
-        /* 3: */-12,
+        /* 3: */-2,
         /* 4: */Bytecode.CONST,
         /* 5: */1,
         /* 6: */Bytecode.ADD,
         /* 7: */Bytecode.DUP,
         /* 8: */Bytecode.CONST,
-        /* 9: */-12,
+        /* 9: */-2,
         /* 10: */Bytecode.CONST,
         /* 11: */1,
         /* 12: */Bytecode.ADD,
@@ -258,13 +257,13 @@
         /* 15: */18,
         /* 16: */Bytecode.JMP,
         /* 17: */10,
-        /* 18: */Bytecode.IFZERO,
-        /* 19: */22,
-        /* 20: */Bytecode.JMP,
-        /* 21: */4,
-        /* 22: */Bytecode.POP,
-        /* 22: */Bytecode.POP,
-        /* 23: */Bytecode.RETURN};
+        /* 18: */Bytecode.POP,
+        /* 19: */Bytecode.IFZERO,
+        /* 20: */23,
+        /* 21: */Bytecode.JMP,
+        /* 22: */4,
+        /* 23: */Bytecode.POP,
+        /* 24: */Bytecode.RETURN};
         assertPartialEvalEqualsAndRunsCorrect(new Program("nestedLoopsProgram", bytecodes, 0, 6));
     }