--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/ExceptionObjectNode.java	Wed Jun 19 16:46:41 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/ExceptionObjectNode.java	Wed Jun 19 21:49:09 2013 +0200
@@ -69,7 +69,6 @@
         loadException.setStateAfter(stateAfter());
         replaceAtUsages(loadException);
         graph().addAfterFixed(this, loadException);
-        tool.setLastFixedNode(loadException);
         setStateAfter(null);
         setStamp(StampFactory.forVoid());
     }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/LoweringTool.java	Wed Jun 19 16:46:41 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/LoweringTool.java	Wed Jun 19 21:49:09 2013 +0200
@@ -52,9 +52,4 @@
      * Gets the closest fixed node preceding the node currently being lowered.
      */
     FixedWithNextNode lastFixedNode();
-
-    /**
-     * Sets the closest fixed node preceding the next node to be lowered.
-     */
-    void setLastFixedNode(FixedWithNextNode n);
 }

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Wed Jun 19 16:46:41 2013 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Wed Jun 19 21:49:09 2013 +0200
@@ -126,7 +126,7 @@
             return lastFixedNode;
         }
 
-        public void setLastFixedNode(FixedWithNextNode n) {
+        private void setLastFixedNode(FixedWithNextNode n) {
             assert n == null || n.isAlive() : n;
             lastFixedNode = n;
         }
@@ -150,35 +150,30 @@
     @Override
     protected void run(final StructuredGraph graph, PhaseContext context) {
         int i = 0;
-        NodeBitMap processed = graph.createNodeBitMap();
         while (true) {
-            Round round = new Round(i++, context, processed);
+            Round round = new Round(i++, context);
             int mark = graph.getMark();
 
             IncrementalCanonicalizerPhase<PhaseContext> canonicalizer = new IncrementalCanonicalizerPhase<>();
             canonicalizer.appendPhase(round);
             canonicalizer.apply(graph, context);
 
-            if (!round.deferred && !containsLowerable(graph.getNewNodes(mark))) {
+            if (!containsLowerable(graph.getNewNodes(mark))) {
                 // No new lowerable nodes - done!
                 break;
             }
             assert graph.verify();
-            processed.grow();
         }
     }
 
     private final class Round extends Phase {
 
         private final PhaseContext context;
-        private final NodeBitMap processed;
         private final SchedulePhase schedule;
-        private boolean deferred = false;
 
-        private Round(int iteration, PhaseContext context, NodeBitMap processed) {
+        private Round(int iteration, PhaseContext context) {
             super(String.format("Lowering iteration %d", iteration));
             this.context = context;
-            this.processed = processed;
             this.schedule = new SchedulePhase();
         }
 
@@ -223,45 +218,45 @@
 
             // Lower the instructions of this block.
             List<ScheduledNode> nodes = schedule.nodesFor(b);
-
+            loweringTool.setLastFixedNode(null);
             for (Node node : nodes) {
-                FixedNode nextFixedNode = null;
-                if (node instanceof FixedWithNextNode && node.isAlive()) {
-                    FixedWithNextNode fixed = (FixedWithNextNode) node;
-                    nextFixedNode = fixed.next();
-                    loweringTool.setLastFixedNode(fixed);
+
+                if (node.isDeleted()) {
+                    // This case can happen when previous lowerings deleted nodes.
+                    continue;
                 }
 
-                if (node.isAlive() && !processed.isMarked(node) && node instanceof Lowerable) {
-                    if (loweringTool.lastFixedNode() == null) {
-                        /*
-                         * We cannot lower the node now because we don't have a fixed node to anchor
-                         * the replacements. This can happen when previous lowerings in this
-                         * lowering iteration deleted the BeginNode of this block. In the next
-                         * iteration, we will have the new BeginNode available, and we can lower
-                         * this node.
-                         */
-                        deferred = true;
+                if (loweringTool.lastFixedNode() == null) {
+                    AbstractBeginNode beginNode = b.getBeginNode();
+                    if (node instanceof Lowerable) {
+                        // Handles cases where there is a lowerable nodes scheduled before the begin
+                        // node.
+                        BeginNode newBegin = node.graph().add(new BeginNode());
+                        beginNode.replaceAtPredecessor(newBegin);
+                        newBegin.setNext(beginNode);
+                        loweringTool.setLastFixedNode(newBegin);
+                    } else if (node == beginNode) {
+                        loweringTool.setLastFixedNode(beginNode);
                     } else {
-                        processed.mark(node);
-                        ((Lowerable) node).lower(loweringTool, loweringType);
+                        continue;
                     }
                 }
 
-                if (loweringTool.lastFixedNode() == node && !node.isAlive()) {
-                    if (nextFixedNode == null || !nextFixedNode.isAlive()) {
-                        loweringTool.setLastFixedNode(null);
-                    } else {
-                        Node prev = nextFixedNode.predecessor();
-                        if (prev != node && prev instanceof FixedWithNextNode) {
-                            loweringTool.setLastFixedNode((FixedWithNextNode) prev);
-                        } else if (nextFixedNode instanceof FixedWithNextNode) {
-                            loweringTool.setLastFixedNode((FixedWithNextNode) nextFixedNode);
-                        } else {
-                            loweringTool.setLastFixedNode(null);
-                        }
-                    }
+                // Cache the next node to be able to reconstruct the previous of the next node
+                // after lowering.
+                FixedNode nextNode = null;
+                if (node instanceof FixedWithNextNode) {
+                    FixedWithNextNode fixed = (FixedWithNextNode) node;
+                    nextNode = fixed.next();
+                } else {
+                    nextNode = loweringTool.lastFixedNode().next();
                 }
+
+                if (node instanceof Lowerable) {
+                    ((Lowerable) node).lower(loweringTool, loweringType);
+                }
+
+                loweringTool.setLastFixedNode((FixedWithNextNode) nextNode.predecessor());
             }
         }
     }

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java	Wed Jun 19 16:46:41 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java	Wed Jun 19 21:49:09 2013 +0200
@@ -807,7 +807,7 @@
         Debug.dump(replaceeGraph, "After inlining snippet %s", snippetCopy.method());
 
         FixedWithNextNode lastFixedNode = tool.lastFixedNode();
-        assert lastFixedNode != null && lastFixedNode.isAlive() : replaceeGraph;
+        assert lastFixedNode != null && lastFixedNode.isAlive() : replaceeGraph + " lastFixed=" + lastFixedNode;
         FixedNode next = lastFixedNode.next();
         lastFixedNode.setNext(null);
         FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
@@ -836,14 +836,10 @@
         assert returnValue != null || replacee.usages().isEmpty();
         replacer.replace(replacee, returnValue);
 
-        tool.setLastFixedNode(null);
         Node returnDuplicate = duplicates.get(returnNode);
         if (returnDuplicate.isAlive()) {
             returnDuplicate.clearInputs();
             returnDuplicate.replaceAndDelete(next);
-            if (next != null && next.predecessor() instanceof FixedWithNextNode) {
-                tool.setLastFixedNode((FixedWithNextNode) next.predecessor());
-            }
         }
 
         Debug.dump(replaceeGraph, "After lowering %s with %s", replacee, this);