--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GraphDecoder.java	Mon Jan 11 22:50:34 2016 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GraphDecoder.java	Mon Jan 11 16:47:22 2016 -0800
@@ -1137,7 +1137,11 @@
             visited.mark(loopEnd);
         }
 
-        List<ControlSplitNode> controlSplits = new ArrayList<>();
+        /*
+         * All nodes that get added to that list, and that do not get marked as being in our loop,
+         * need to be preceded by a LoopExitNode.
+         */
+        List<Node> possibleExitSuccessors = new ArrayList<>();
 
         while (!stack.isEmpty()) {
             Node current = stack.pop();
@@ -1154,11 +1158,27 @@
                         if (!visited.isMarked(innerLoopBegin)) {
                             stack.push(innerLoopBegin);
                             visited.mark(innerLoopBegin);
+
+                            /*
+                             * All loop exits of the inner loop possibly need a LoopExit of our
+                             * loop. Because we are processing inner loops first, we are guaranteed
+                             * to already have all exits of the inner loop.
+                             */
+                            for (LoopExitNode exit : innerLoopBegin.loopExits()) {
+                                if (!visited.isMarked(exit)) {
+                                    possibleExitSuccessors.add(exit);
+                                }
+                            }
                         }
+
                     } else {
                         if (pred instanceof ControlSplitNode) {
                             ControlSplitNode controlSplitNode = (ControlSplitNode) pred;
-                            controlSplits.add(controlSplitNode);
+                            for (Node succ : controlSplitNode.cfgSuccessors()) {
+                                if (!visited.isMarked(succ)) {
+                                    possibleExitSuccessors.add(succ);
+                                }
+                            }
                         }
                         stack.push(pred);
                     }
@@ -1166,14 +1186,16 @@
             }
         }
 
-        for (ControlSplitNode controlSplit : controlSplits) {
-            for (Node succ : controlSplit.cfgSuccessors()) {
-                if (!visited.isMarked(succ)) {
-                    LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin));
-                    FixedNode next = ((FixedWithNextNode) succ).next();
-                    next.replaceAtPredecessor(loopExit);
-                    loopExit.setNext(next);
-                }
+        for (Node succ : possibleExitSuccessors) {
+            /*
+             * Now we have the definitive isMarked information. A node can get marked after the
+             * initial check for isMarked when we added a node to the list.
+             */
+            if (!visited.isMarked(succ)) {
+                LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin));
+                FixedNode next = ((FixedWithNextNode) succ).next();
+                next.replaceAtPredecessor(loopExit);
+                loopExit.setNext(next);
             }
         }
     }

--- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java	Mon Jan 11 22:50:34 2016 +0100
+++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java	Mon Jan 11 16:47:22 2016 -0800
@@ -334,6 +334,46 @@
         assertPartialEvalEqualsAndRunsCorrect(new Program("nestedLoopsProgram", bytecodes, 0, 6));
     }
 
+    @Test
+    public void nestedLoopsProgram2() {
+        byte[] bytecodes = new byte[]{
+        /* 0: */Bytecode.CONST,
+        /* 1: */42,
+        /* 2: */Bytecode.CONST,
+        /* 3: */-2,
+        /* 4: */Bytecode.CONST,
+        /* 5: */1,
+        /* 6: */Bytecode.ADD,
+        /* 7: */Bytecode.DUP,
+        /* 8: */Bytecode.CONST,
+        /* 9: */-2,
+
+        /* 10: */Bytecode.CONST,
+        /* 11: */0,
+        /* 12: */Bytecode.IFZERO,
+        /* 13: */17,
+        /* 14: */Bytecode.POP,
+        /* 15: */Bytecode.JMP,
+        /* 16: */30,
+
+        /* 17: */Bytecode.CONST,
+        /* 18: */1,
+        /* 19: */Bytecode.ADD,
+        /* 10: */Bytecode.DUP,
+        /* 21: */Bytecode.IFZERO,
+        /* 22: */25,
+        /* 23: */Bytecode.JMP,
+        /* 24: */10,
+        /* 25: */Bytecode.POP,
+        /* 26: */Bytecode.IFZERO,
+        /* 27: */30,
+        /* 28: */Bytecode.JMP,
+        /* 29: */4,
+        /* 30: */Bytecode.POP,
+        /* 31: */Bytecode.RETURN};
+        assertPartialEvalEqualsAndRunsCorrect(new Program("nestedLoopsProgram2", bytecodes, 0, 6));
+    }
+
     @Test(timeout = 2000)
     public void manyIfsProgram() {
         byte[] bytecodes = new byte[]{