# HG changeset patch
# User Gilles Duboscq <duboscq@ssw.jku.at>
# Date 1329389858 -3600
# Node ID a3882fd1ae61e3a5c552f8a2ca6ccf1d1a5d4c17
# Parent  09402dddc51ee795c624adeefd8cde389b7f557c
Make it possible to have multiple LoopEnds per LoopBegin
Factor out the 2 versions of KillCFG (GraphUitl/Canonicalizer)
Remove unused loop detection code from FloatingReadPhase
Made InvokeNode's toString/getDebugProperties more robust

diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/ComputeLinearScanOrder.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/ComputeLinearScanOrder.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/ComputeLinearScanOrder.java	Thu Feb 16 11:57:38 2012 +0100
@@ -29,6 +29,7 @@
 import com.oracle.max.graal.compiler.*;
 import com.oracle.max.graal.graph.*;
 import com.oracle.max.graal.lir.cfg.*;
+import com.oracle.max.graal.nodes.*;
 
 public final class ComputeLinearScanOrder {
 
@@ -261,18 +262,19 @@
         if (cur.isLoopEnd() && cur.isLoopHeader()) {
             codeEmittingOrder.add(cur);
         } else {
-            if (!cur.isLoopHeader() || !GraalOptions.OptReorderLoops) {
+            if (!cur.isLoopHeader() || ((LoopBeginNode) cur.getBeginNode()).loopEnds().count() > 1 || !GraalOptions.OptReorderLoops) {
                 codeEmittingOrder.add(cur);
 
                 if (cur.isLoopEnd() && GraalOptions.OptReorderLoops) {
                     Block loopHeader = loopHeaders[cur.getLoop().index];
-                    assert loopHeader != null;
-                    codeEmittingOrder.add(loopHeader);
+                    if (loopHeader != null) {
+                        codeEmittingOrder.add(loopHeader);
 
-                    for (int i = 0; i < loopHeader.numberOfSux(); i++) {
-                        Block succ = loopHeader.suxAt(i);
-                        if (succ.getLoopDepth() == loopHeader.getLoopDepth()) {
-                            succ.align = true;
+                        for (int i = 0; i < loopHeader.numberOfSux(); i++) {
+                            Block succ = loopHeader.suxAt(i);
+                            if (succ.getLoopDepth() == loopHeader.getLoopDepth()) {
+                                succ.align = true;
+                            }
                         }
                     }
                 }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Thu Feb 16 11:57:38 2012 +0100
@@ -682,12 +682,11 @@
         if (GraalOptions.GenLoopSafepoints && x.hasSafepointPolling()) {
             emitSafepointPoll(x);
         }
-        moveToPhi(x.loopBegin(), x);
     }
 
     private ArrayList<CiValue> phiValues = new ArrayList<>();
 
-    private void moveToPhi(MergeNode merge, FixedNode pred) {
+    private void moveToPhi(MergeNode merge, EndNode pred) {
         if (GraalOptions.AllocSSA) {
             assert phiValues.isEmpty();
             for (PhiNode phi : merge.phis()) {
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/MergeableState.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/MergeableState.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/MergeableState.java	Thu Feb 16 11:57:38 2012 +0100
@@ -30,6 +30,6 @@
     T clone();
     boolean merge(MergeNode merge, Collection<T> withStates);
     void loopBegin(LoopBeginNode loopBegin);
-    void loopEnd(LoopEndNode loopEnd, T loopEndState);
+    void loopEnds(LoopBeginNode loopBegin, Collection<T> loopEndStates);
     void afterSplit(FixedNode node);
 }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/PostOrderNodeIterator.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/PostOrderNodeIterator.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/PostOrderNodeIterator.java	Thu Feb 16 11:57:38 2012 +0100
@@ -60,11 +60,8 @@
                 current = ((LoopBeginNode) current).next();
                 assert current != null;
             } else if (current instanceof LoopEndNode) {
-                T loopBeginState = nodeStates.get(((LoopEndNode) current).loopBegin());
-                if (loopBeginState != null) {
-                    loopBeginState.loopEnd((LoopEndNode) current, state);
-                }
                 loopEnd((LoopEndNode) current);
+                finishLoopEnds((LoopEndNode) current);
                 current = nextQueuedNode();
             } else if (current instanceof MergeNode) {
                 merge((MergeNode) current);
@@ -122,10 +119,10 @@
             FixedNode node = nodeQueue.removeFirst();
             if (node instanceof MergeNode) {
                 MergeNode merge = (MergeNode) node;
-                state = nodeStates.get(merge.endAt(0)).clone();
-                ArrayList<T> states = new ArrayList<>(merge.endCount() - 1);
-                for (int i = 1; i < merge.endCount(); i++) {
-                    T other = nodeStates.get(merge.endAt(i));
+                state = nodeStates.get(merge.forwardEndAt(0)).clone();
+                ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1);
+                for (int i = 1; i < merge.forwardEndCount(); i++) {
+                    T other = nodeStates.get(merge.forwardEndAt(i));
                     assert other != null;
                     states.add(other);
                 }
@@ -145,6 +142,31 @@
         return null;
     }
 
+    private void finishLoopEnds(LoopEndNode end) {
+        assert !visitedEnds.isMarked(end);
+        assert !nodeStates.containsKey(end);
+        nodeStates.put(end, state);
+        visitedEnds.mark(end);
+        LoopBeginNode begin = end.loopBegin();
+        boolean endsVisited = true;
+        for (LoopEndNode le : begin.loopEnds()) {
+            if (!visitedEnds.isMarked(le)) {
+                endsVisited = false;
+                break;
+            }
+        }
+        if (endsVisited) {
+            ArrayList<T> states = new ArrayList<>(begin.loopEnds().count());
+            for (LoopEndNode le : begin.orderedLoopEnds()) {
+                states.add(nodeStates.get(le));
+            }
+            T loopBeginState = nodeStates.get(begin);
+            if (loopBeginState != null) {
+                loopBeginState.loopEnds(begin, states);
+            }
+        }
+    }
+
     private void queueMerge(EndNode end) {
         assert !visitedEnds.isMarked(end);
         assert !nodeStates.containsKey(end);
@@ -152,8 +174,8 @@
         visitedEnds.mark(end);
         MergeNode merge = end.merge();
         boolean endsVisited = true;
-        for (int i = 0; i < merge.endCount(); i++) {
-            if (!visitedEnds.isMarked(merge.endAt(i))) {
+        for (int i = 0; i < merge.forwardEndCount(); i++) {
+            if (!visitedEnds.isMarked(merge.forwardEndAt(i))) {
                 endsVisited = false;
                 break;
             }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java	Thu Feb 16 11:57:38 2012 +0100
@@ -22,8 +22,6 @@
  */
 package com.oracle.max.graal.compiler.phases;
 
-import static com.oracle.max.graal.graph.iterators.NodePredicates.*;
-
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
 import com.oracle.max.graal.debug.*;
@@ -31,6 +29,7 @@
 import com.oracle.max.graal.nodes.*;
 import com.oracle.max.graal.nodes.calc.*;
 import com.oracle.max.graal.nodes.spi.*;
+import com.oracle.max.graal.nodes.util.*;
 
 public class CanonicalizerPhase extends Phase {
     private static final int MAX_ITERATION_PER_NODE = 10;
@@ -62,6 +61,7 @@
     }
 
     public static void canonicalize(StructuredGraph graph, NodeWorkList nodeWorkList, RiRuntime runtime, CiTarget target, CiAssumptions assumptions) {
+        graph.trackInputChange(nodeWorkList);
         Tool tool = new Tool(nodeWorkList, runtime, target, assumptions);
         for (Node node : nodeWorkList) {
             if (node instanceof Canonicalizable) {
@@ -113,36 +113,23 @@
                             }
                         }
                     }
-
-                    for (Node newNode : graph.getNewNodes()) {
-                        nodeWorkList.add(newNode);
-                    }
-                    if (canonical != null) {
-                        nodeWorkList.replaced(canonical, node, false);
-                    }
+                    nodeWorkList.addAll(graph.getNewNodes());
                 }
             } else if (node instanceof Simplifiable) {
                 ((Simplifiable) node).simplify(tool);
             }
         }
-
+        graph.stopTrackingInputChange();
         while (graph.getUsagesDroppedNodesCount() > 0) {
             for (Node n : graph.getAndCleanUsagesDroppedNodes()) {
                 if (!n.isDeleted() && n.usages().size() == 0 && n instanceof FloatingNode) {
-                    killFloating((FloatingNode) n);
+                    n.clearInputs();
+                    n.safeDelete();
                 }
             }
         }
     }
 
-
-    private static void killFloating(FloatingNode node) {
-        if (node.usages().size() == 0) {
-            node.clearInputs();
-            node.safeDelete();
-        }
-    }
-
     private static final class Tool implements SimplifierTool {
 
         private final NodeWorkList nodeWorkList;
@@ -160,89 +147,7 @@
         @Override
         public void deleteBranch(FixedNode branch) {
             branch.predecessor().replaceFirstSuccessor(branch, null);
-            killCFG(branch);
-        }
-
-        public void killCFG(FixedNode node) {
-            for (Node successor : node.successors()) {
-                if (successor != null) {
-                    node.replaceFirstSuccessor(successor, null);
-                    assert !node.isDeleted();
-                    killCFG((FixedNode) successor);
-                }
-            }
-            if (node instanceof LoopEndNode) {
-                LoopEndNode loopEnd = (LoopEndNode) node;
-                LoopBeginNode loopBegin = loopEnd.loopBegin();
-                if (loopBegin != null) {
-                    assert loopBegin.isAlive();
-                    assert loopBegin.endCount() == 1;
-                    EndNode predEnd = loopBegin.endAt(0);
-
-                    for (PhiNode phi : loopBegin.phis().snapshot()) {
-                        ValueNode value = phi.valueAt(0);
-                        phi.replaceAndDelete(value);
-                        nodeWorkList.replaced(value, phi, false);
-                    }
-                    FixedNode next = loopBegin.next();
-                    loopEnd.setLoopBegin(null);
-                    loopBegin.safeDelete();
-
-                    predEnd.replaceAndDelete(next);
-                }
-            } else if (node instanceof EndNode) {
-                EndNode end = (EndNode) node;
-                MergeNode merge = end.merge();
-                if (merge instanceof LoopBeginNode) {
-                    for (PhiNode phi : merge.phis().snapshot()) {
-                        ValueNode value = phi.valueAt(0);
-                        phi.replaceAndDelete(value);
-                        nodeWorkList.replaced(value, phi, false);
-                    }
-                    if (((LoopBeginNode) merge).loopEnd() != null) {
-                        ((LoopBeginNode) merge).loopEnd().setLoopBegin(null);
-                    }
-                    killCFG(merge);
-                } else {
-                    merge.removeEnd(end);
-                    if (merge.phiPredecessorCount() == 1) {
-                        for (PhiNode phi : merge.phis().snapshot()) {
-                            ValueNode value = phi.valueAt(0);
-                            phi.replaceAndDelete(value);
-                            nodeWorkList.replaced(value, phi, false);
-                        }
-                        Node replacedSux = merge.phiPredecessorAt(0);
-                        Node pred = replacedSux.predecessor();
-                        assert replacedSux instanceof EndNode;
-                        FixedNode next = merge.next();
-                        merge.setNext(null);
-                        pred.replaceFirstSuccessor(replacedSux, next);
-                        FrameState stateAfter = merge.stateAfter();
-                        merge.setStateAfter(null);
-                        if (stateAfter != null && stateAfter.usages().isEmpty()) {
-                            stateAfter.safeDelete();
-                        }
-                        merge.safeDelete();
-                        replacedSux.safeDelete();
-                    }
-                }
-            }
-            killNonCFG(node, null);
-        }
-
-        public void killNonCFG(Node node, Node input) {
-            if (node instanceof PhiNode) {
-                node.replaceFirstInput(input, null);
-            } else {
-                for (Node usage : node.usages().filter(isA(FloatingNode.class).or(CallTargetNode.class)).snapshot()) {
-                    if (!usage.isDeleted()) {
-                        killNonCFG(usage, node);
-                    }
-                }
-                // null out remaining usages
-                node.replaceAtUsages(null);
-                node.safeDelete();
-            }
+            GraphUtil.killCFG(branch);
         }
 
         /**
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java	Thu Feb 16 11:57:38 2012 +0100
@@ -73,26 +73,32 @@
     public static class LoopInfo {
         public final LoopBeginNode loopBegin;
 
-        public final Set<LoopInfo> requires = new HashSet<>(4);
+        public final NodeMap<Set<LoopInfo>> requires;
 
         private double loopFrequency = -1;
         public boolean ended = false;
 
         public LoopInfo(LoopBeginNode loopBegin) {
             this.loopBegin = loopBegin;
+            this.requires = loopBegin.graph().createNodeMap();
         }
 
         public double loopFrequency() {
             if (loopFrequency == -1 && ended) {
-                double factor = 1;
-                for (LoopInfo required : requires) {
-                    double t = required.loopFrequency();
-                    if (t == -1) {
-                        return -1;
+                double backEdgeProb = 0.0;
+                for (LoopEndNode le : loopBegin.loopEnds()) {
+                    double factor = 1;
+                    Set<LoopInfo> requireds = requires.get(le);
+                    for (LoopInfo required : requireds) {
+                        double t = required.loopFrequency();
+                        if (t == -1) {
+                            return -1;
+                        }
+                        factor *= t;
                     }
-                    factor *= t;
+                    backEdgeProb += le.probability() * factor;
                 }
-                double d = loopBegin.loopEnd().probability() * factor;
+                double d = backEdgeProb;
                 if (d < EPSILON) {
                     d = EPSILON;
                 } else if (d > loopBegin.probability() - EPSILON) {
@@ -128,7 +134,7 @@
 
         @Override
         public boolean merge(MergeNode merge, Collection<Probability> withStates) {
-            if (merge.endCount() > 1) {
+            if (merge.forwardEndCount() > 1) {
                 HashSet<LoopInfo> intersection = new HashSet<>(loops);
                 for (Probability other : withStates) {
                     intersection.retainAll(other.loops);
@@ -170,11 +176,21 @@
         }
 
         @Override
-        public void loopEnd(LoopEndNode loopEnd, Probability loopEndState) {
+        public void loopEnds(LoopBeginNode loopBegin, Collection<Probability> loopEndStates) {
             assert loopInfo != null;
-            for (LoopInfo innerLoop : loopEndState.loops) {
-                if (innerLoop != loopInfo && !loops.contains(innerLoop)) {
-                    loopInfo.requires.add(innerLoop);
+            List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds();
+            int i = 0;
+            for (Probability proba : loopEndStates) {
+                LoopEndNode loopEnd = loopEnds.get(i++);
+                Set<LoopInfo> requires = loopInfo.requires.get(loopEnd);
+                if (requires == null) {
+                    requires = new HashSet<>();
+                    loopInfo.requires.set(loopEnd, requires);
+                }
+                for (LoopInfo innerLoop : proba.loops) {
+                    if (innerLoop != loopInfo && !this.loops.contains(innerLoop)) {
+                        requires.add(innerLoop);
+                    }
                 }
             }
             loopInfo.ended = true;
@@ -229,8 +245,8 @@
 
         @Override
         public boolean merge(MergeNode merge, Collection<LoopCount> withStates) {
-            assert merge.endCount() == withStates.size() + 1;
-            if (merge.endCount() > 1) {
+            assert merge.forwardEndCount() == withStates.size() + 1;
+            if (merge.forwardEndCount() > 1) {
                 Set<LoopInfo> loops = mergeLoops.get(merge);
                 assert loops != null;
                 double countProd = 1;
@@ -248,7 +264,7 @@
         }
 
         @Override
-        public void loopEnd(LoopEndNode loopEnd, LoopCount loopEndState) {
+        public void loopEnds(LoopBeginNode loopBegin, Collection<LoopCount> loopEndStates) {
             // nothing to do...
         }
 
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java	Thu Feb 16 11:57:38 2012 +0100
@@ -43,9 +43,9 @@
 
         // remove chained Merges
         for (MergeNode merge : graph.getNodes(MergeNode.class)) {
-            if (merge.endCount() == 1 && !(merge instanceof LoopBeginNode)) {
+            if (merge.forwardEndCount() == 1 && !(merge instanceof LoopBeginNode)) {
                 replacePhis(merge);
-                EndNode endNode = merge.endAt(0);
+                EndNode endNode = merge.forwardEndAt(0);
                 FixedNode next = merge.next();
                 merge.safeDelete();
                 endNode.replaceAndDelete(next);
@@ -76,21 +76,21 @@
                 }
             }
         }
-        for (LoopEndNode node : graph.getNodes(LoopEndNode.class)) {
-            if (!flood.isMarked(node)) {
-                LoopBeginNode loop = node.loopBegin();
-                if (flood.isMarked(loop)) {
+        for (LoopBeginNode loop : graph.getNodes(LoopBeginNode.class)) {
+            if (flood.isMarked(loop)) {
+                boolean reachable = false;
+                for (LoopEndNode end : loop.loopEnds()) {
+                    if (flood.isMarked(end)) {
+                        reachable = true;
+                        break;
+                    }
+                }
+                if (!reachable) {
                     Debug.log("Removing loop with unreachable end: %s", loop);
-                    node.setLoopBegin(null);
-                    EndNode endNode = loop.endAt(0);
-                    assert endNode.predecessor() != null;
-                    replacePhis(loop);
-                    loop.removeEnd(endNode);
-
-                    FixedNode next = loop.next();
-                    loop.setNext(null);
-                    endNode.replaceAndDelete(next);
-                    loop.safeDelete();
+                    for (LoopEndNode end : loop.loopEnds().snapshot()) {
+                        loop.removeEnd(end);
+                    }
+                    graph.reduceDegenerateLoopBegin(loop);
                 }
             }
         }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java	Thu Feb 16 11:57:38 2012 +0100
@@ -189,15 +189,15 @@
         }
 
         @Override
-        public void loopEnd(LoopEndNode x, BlockExitState loopEndState) {
+        public void loopEnds(LoopBeginNode loopBegin, Collection<BlockExitState> loopEndStates) {
             while (!(virtualObjectField instanceof PhiNode)) {
                 virtualObjectField = ((VirtualObjectFieldNode) virtualObjectField).lastState();
             }
-            ((PhiNode) virtualObjectField).addInput(loopEndState.virtualObjectField);
-            assert ((PhiNode) virtualObjectField).valueCount() == 2;
-            for (int i2 = 0; i2 < fieldState.length; i2++) {
-                ((PhiNode) fieldState[i2]).addInput(loopEndState.fieldState[i2]);
-                assert ((PhiNode) fieldState[i2]).valueCount() == 2;
+            for (BlockExitState loopEndState : loopEndStates) {
+                ((PhiNode) virtualObjectField).addInput(loopEndState.virtualObjectField);
+                for (int i2 = 0; i2 < fieldState.length; i2++) {
+                    ((PhiNode) fieldState[i2]).addInput(loopEndState.fieldState[i2]);
+                }
             }
         }
 
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/FloatingReadPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/FloatingReadPhase.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/FloatingReadPhase.java	Thu Feb 16 11:57:38 2012 +0100
@@ -57,10 +57,8 @@
 
             for (Map.Entry<Object, Node> entry : loopEntryMap.entrySet()) {
                 PhiNode phiNode = (PhiNode) entry.getValue();
-                assert phiNode.valueCount() == 1;
-
+                Object key = entry.getKey();
                 Node other;
-                Object key = entry.getKey();
                 if (otherMemoryMap.map.containsKey(key)) {
                     other = otherMemoryMap.map.get(key);
                 } else {
@@ -113,7 +111,7 @@
                 PhiNode phi = (PhiNode) original;
                 phi.addInput((ValueNode) newValue);
                 Debug.log("Add new input to %s: %s.", original, newValue);
-                assert phi.valueCount() <= phi.merge().endCount() : phi.merge();
+                assert phi.valueCount() <= phi.merge().forwardEndCount() : phi.merge();
             } else {
                 PhiNode phi = m.graph().unique(new PhiNode(CiKind.Illegal, m, PhiType.Memory));
                 for (int i = 0; i < mergeOperationCount + 1; ++i) {
@@ -121,7 +119,7 @@
                 }
                 phi.addInput((ValueNode) newValue);
                 Debug.log("Creating new %s merge=%s newValue=%s location=%s.", phi, phi.merge(), newValue, location);
-                assert phi.valueCount() <= phi.merge().endCount() + ((phi.merge() instanceof LoopBeginNode) ? 1 : 0) : phi.merge() + "/" + phi.valueCount() + "/" + phi.merge().endCount() + "/" + mergeOperationCount;
+                assert phi.valueCount() <= phi.merge().forwardEndCount() + ((phi.merge() instanceof LoopBeginNode) ? 1 : 0) : phi.merge() + "/" + phi.valueCount() + "/" + phi.merge().forwardEndCount() + "/" + mergeOperationCount;
                 assert m.usages().contains(phi);
                 assert phi.merge().usages().contains(phi);
                 for (Node input : phi.inputs()) {
@@ -263,10 +261,10 @@
             if (b.isLoopHeader()) {
                 Loop loop = b.getLoop();
                 map.createLoopEntryMemoryMap(modifiedValues.get(loop), loop);
-            } else {
-                for (int i = 1; i < b.getPredecessors().size(); ++i) {
-                    assert b.getBeginNode() instanceof MergeNode : b.getBeginNode();
-                    Block block = b.getPredecessors().get(i);
+            }
+            for (int i = 1; i < b.getPredecessors().size(); ++i) {
+                Block block = b.getPredecessors().get(i);
+                if (!block.isLoopEnd()) {
                     map.mergeWith(memoryMaps[block.getId()], b);
                 }
             }
@@ -313,40 +311,4 @@
     private static void traceWrite(Loop loop, Object locationIdentity, HashMap<Loop, Set<Object>> modifiedValues) {
         modifiedValues.get(loop).add(locationIdentity);
     }
-
-    private void mark(LoopBeginNode begin, LoopBeginNode outer, NodeMap<LoopBeginNode> nodeToLoop) {
-
-        if (nodeToLoop.get(begin) != null) {
-            // Loop already processed.
-            return;
-        }
-        nodeToLoop.set(begin, begin);
-
-        NodeFlood workCFG = begin.graph().createNodeFlood();
-        workCFG.add(begin.loopEnd());
-        for (Node n : workCFG) {
-            if (n == begin) {
-                // Stop at loop begin.
-                continue;
-            }
-            markNode(n, begin, outer, nodeToLoop);
-
-            for (Node pred : n.cfgPredecessors()) {
-                workCFG.add(pred);
-            }
-        }
-    }
-
-    private void markNode(Node n, LoopBeginNode begin, LoopBeginNode outer, NodeMap<LoopBeginNode> nodeToLoop) {
-        LoopBeginNode oldMark = nodeToLoop.get(n);
-        if (oldMark == null || oldMark == outer) {
-
-            // We have an inner loop, start marking it.
-            if (n instanceof LoopBeginNode) {
-                mark((LoopBeginNode) n, begin, nodeToLoop);
-            }
-
-            nodeToLoop.set(n, begin);
-        }
-    }
 }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java	Thu Feb 16 11:57:38 2012 +0100
@@ -204,10 +204,11 @@
                         TTY.println(merge.toString());
                         TTY.println(phi.toString());
                         TTY.println(merge.cfgPredecessors().toString());
+                        TTY.println(mergeBlock.getPredecessors().toString());
                         TTY.println(phi.inputs().toString());
                         TTY.println("value count: " + phi.valueCount());
                     }
-                closure.apply(mergeBlock.getPredecessors().get(i));
+                    closure.apply(mergeBlock.getPredecessors().get(i));
                 }
             }
         } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/InliningUtil.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/InliningUtil.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/InliningUtil.java	Thu Feb 16 11:57:38 2012 +0100
@@ -358,7 +358,7 @@
             if (tsux instanceof MergeNode) {
                 EndNode endNode = graph.add(new EndNode());
                 result = graph.add(new IfNode(isTypeNode, endNode, nextNode, tsuxProbability));
-                ((MergeNode) tsux).addEnd(endNode);
+                ((MergeNode) tsux).addForwardEnd(endNode);
             } else {
                 result = graph.add(new IfNode(isTypeNode, tsux, nextNode, tsuxProbability));
             }
@@ -389,7 +389,7 @@
             EndNode endNode = graph.add(new EndNode());
             // TODO (ch) set probability
             duplicatedInvoke.setNext(endNode);
-            returnMerge.addEnd(endNode);
+            returnMerge.addForwardEnd(endNode);
             if (returnValuePhi != null) {
                 returnValuePhi.addInput(duplicatedInvoke.node());
             }
@@ -424,7 +424,7 @@
 
                 EndNode endNode = graph.add(new EndNode());
                 newExceptionObject.setNext(endNode);
-                exceptionMerge.addEnd(endNode);
+                exceptionMerge.addForwardEnd(endNode);
                 exceptionObjectPhi.addInput(newExceptionObject);
 
                 ((InvokeWithExceptionNode) result).setExceptionEdge(newExceptionEdge);
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java	Thu Feb 16 11:57:38 2012 +0100
@@ -49,6 +49,7 @@
     private GraphEventLog eventLog;
 
     ArrayList<Node> usagesDropped = new ArrayList<>();
+    NodeWorkList inputChanged;
     private final HashMap<CacheEntry, Node> cachedNodes = new HashMap<>();
 
     private static final class CacheEntry {
@@ -159,6 +160,14 @@
         return result;
     }
 
+    public void trackInputChange(NodeWorkList worklist) {
+        this.inputChanged = worklist;
+    }
+
+    public void stopTrackingInputChange() {
+        inputChanged = null;
+    }
+
     /**
      * Adds a new node to the graph, if a <i>similar</i> node already exists in the graph, the provided node will not be added to the graph but the <i>similar</i> node will be returned instead.
      * @param node
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java	Thu Feb 16 11:57:38 2012 +0100
@@ -180,6 +180,10 @@
                 assert assertTrue(result, "not found in usages, old input: %s", oldInput);
             }
             if (newInput != null) {
+                NodeWorkList inputChanged = graph.inputChanged;
+                if (inputChanged != null) {
+                    inputChanged.addAgain(this);
+                }
                 newInput.usages.add(this);
             }
         }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/BciBlockMapping.java
--- a/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/BciBlockMapping.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/BciBlockMapping.java	Thu Feb 16 11:57:38 2012 +0100
@@ -145,6 +145,23 @@
                 throw new RuntimeException(e);
             }
         }
+
+        @Override
+        public String toString() {
+            StringBuilder sb = new StringBuilder("B").append(blockID);
+            sb.append('[').append(startBci).append("->").append(endBci);
+            if (isLoopHeader || isExceptionEntry) {
+                sb.append(' ');
+                if (isLoopHeader) {
+                    sb.append('L');
+                }
+                if (isExceptionEntry) {
+                    sb.append('!');
+                }
+            }
+            sb.append(']');
+            return sb.toString();
+        }
     }
 
     public static class ExceptionBlock extends Block {
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java
--- a/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java	Thu Feb 16 11:57:38 2012 +0100
@@ -243,12 +243,7 @@
         return blocksVisited.contains(block);
     }
 
-    public void mergeOrClone(Block target, FrameStateAccess newState) {
-        AbstractStateSplit first = (AbstractStateSplit) target.firstInstruction;
-
-        if (target.isLoopHeader && isVisited(target)) {
-            first = (AbstractStateSplit) loopBegin(target).loopEnd().predecessor();
-        }
+    public void mergeOrClone(Block target, FrameStateAccess newState, StateSplit first) {
 
         int bci = target.startBci;
         if (target instanceof ExceptionBlock) {
@@ -256,10 +251,11 @@
         }
 
         FrameState existingState = first.stateAfter();
-
         if (existingState == null) {
+            // There was no state : new target
             // copy state because it is modified
             first.setStateAfter(newState.duplicate(bci));
+            return;
         } else {
             if (!GraalOptions.AssumeVerifiedBytecode && !existingState.isCompatibleWith(newState)) {
                 // stacks or locks do not match--bytecodes would not verify
@@ -271,27 +267,31 @@
             assert existingState.stackSize() == newState.stackSize();
 
             if (first instanceof PlaceholderNode) {
+                // there is no merge yet here
                 PlaceholderNode p = (PlaceholderNode) first;
                 if (p.predecessor() == null) {
+                    //nothing seems to come here, yet there's a state?
+                    Debug.log("Funky control flow going to @bci %d : we already have a state but no predecessor", bci);
                     p.setStateAfter(newState.duplicate(bci));
                     return;
                 } else {
+                    //create a merge
                     MergeNode merge = currentGraph.add(new MergeNode());
                     FixedNode next = p.next();
-                    EndNode end = currentGraph.add(new EndNode());
-                    p.setNext(end);
+                    if (p.predecessor() != null) {
+                        EndNode end = currentGraph.add(new EndNode());
+                        p.setNext(end);
+                        merge.addForwardEnd(end);
+                    }
                     merge.setNext(next);
-                    merge.addEnd(end);
-                    merge.setStateAfter(existingState);
-                    p.setStateAfter(existingState.duplicate(bci));
-                    if (!(next instanceof LoopEndNode)) {
-                        target.firstInstruction = merge;
-                    }
-                    first = merge;
+                    FrameState mergeState = existingState.duplicate(bci);
+                    merge.setStateAfter(mergeState);
+                    mergeState.merge(merge, newState);
+                    target.firstInstruction = merge;
                 }
+            } else {
+                existingState.merge((MergeNode) first, newState);
             }
-
-            existingState.merge((MergeNode) first, newState);
         }
     }
 
@@ -921,7 +921,7 @@
                 for (ExceptionInfo info : exceptions) {
                     EndNode end = currentGraph.add(new EndNode());
                     info.exceptionEdge.setNext(end);
-                    merge.addEnd(end);
+                    merge.addForwardEnd(end);
                     phi.addInput(info.exception);
                 }
                 merge.setStateAfter(frameState.duplicate(bci()));
@@ -1264,48 +1264,42 @@
 
         if (block.firstInstruction == null) {
             if (block.isLoopHeader) {
-                LoopBeginNode loopBegin = currentGraph.add(new LoopBeginNode());
-                loopBegin.addEnd(currentGraph.add(new EndNode()));
-                LoopEndNode loopEnd = currentGraph.add(new LoopEndNode());
-                loopEnd.setLoopBegin(loopBegin);
-                PlaceholderNode pBegin = currentGraph.add(new PlaceholderNode());
-                pBegin.setNext(loopBegin.forwardEdge());
-                PlaceholderNode pEnd = currentGraph.add(new PlaceholderNode());
-                pEnd.setNext(loopEnd);
-                loopBegin.setStateAfter(stateAfter.duplicate(block.startBci));
-                block.firstInstruction = pBegin;
+                LoopBeginNode loop = currentGraph.add(new LoopBeginNode());
+                EndNode end = currentGraph.add(new EndNode());
+                loop.addForwardEnd(end);
+                PlaceholderNode p = currentGraph.add(new PlaceholderNode());
+                p.setNext(end);
+                block.firstInstruction = p;
             } else {
                 block.firstInstruction = currentGraph.add(new PlaceholderNode());
             }
         }
-        mergeOrClone(block, stateAfter);
+        LoopEndNode loopend = null;
+        StateSplit mergeAt = null;
+        if (block.isLoopHeader && isVisited(block)) { // backedge
+            loopend = currentGraph.add(new LoopEndNode(loopBegin(block)));
+            mergeAt = loopBegin(block);
+        } else {
+            mergeAt = (StateSplit) block.firstInstruction;
+        }
+
+        mergeOrClone(block, stateAfter, mergeAt);
         addToWorkList(block);
 
         FixedNode result = null;
-        if (block.isLoopHeader && isVisited(block)) {
-            result = (FixedNode) loopBegin(block).loopEnd().predecessor();
+        if (loopend != null) {
+            result = loopend;
         } else {
             result = block.firstInstruction;
         }
 
-        assert result instanceof MergeNode || result instanceof PlaceholderNode : result;
         if (result instanceof MergeNode) {
-            if (result instanceof LoopBeginNode) {
-                result = ((LoopBeginNode) result).forwardEdge();
-            } else {
-                EndNode end = currentGraph.add(new EndNode());
-                ((MergeNode) result).addEnd(end);
-                PlaceholderNode p = currentGraph.add(new PlaceholderNode());
-                int bci = block.startBci;
-                if (block instanceof ExceptionBlock) {
-                    bci = ((ExceptionBlock) block).deoptBci;
-                }
-                p.setStateAfter(stateAfter.duplicate(bci));
-                p.setNext(end);
-                result = p;
-            }
+            EndNode end = currentGraph.add(new EndNode());
+            ((MergeNode) result).addForwardEnd(end);
+            result = end;
         }
-        assert !(result instanceof LoopBeginNode || result instanceof MergeNode);
+        assert !(result instanceof MergeNode);
+        Debug.log("createTarget(%s, state) = %s", block, result);
         return result;
     }
 
@@ -1332,10 +1326,9 @@
                 if (block.isLoopHeader) {
                     LoopBeginNode begin = loopBegin(block);
                     FrameState preLoopState = ((StateSplit) block.firstInstruction).stateAfter();
-                    assert preLoopState != null;
-                    FrameState duplicate = preLoopState.duplicate(preLoopState.bci);
-                    begin.setStateAfter(duplicate);
-                    duplicate.insertLoopPhis(begin);
+                    FrameState loopState = preLoopState.duplicate(preLoopState.bci);
+                    begin.setStateAfter(loopState);
+                    loopState.insertLoopPhis(begin);
                     lastInstr = begin;
                 } else {
                     lastInstr = block.firstInstruction;
@@ -1361,11 +1354,7 @@
 
     private void connectLoopEndToBegin() {
         for (LoopBeginNode begin : currentGraph.getNodes(LoopBeginNode.class)) {
-            LoopEndNode loopEnd = begin.loopEnd();
-            AbstractStateSplit loopEndStateSplit = (AbstractStateSplit) loopEnd.predecessor();
-            if (loopEndStateSplit.stateAfter() != null) {
-                begin.stateAfter().mergeLoop(begin, loopEndStateSplit.stateAfter());
-            } else {
+            if (begin.loopEnds().isEmpty()) {
 //              This can happen with degenerated loops like this one:
 //              for (;;) {
 //                  try {
@@ -1373,30 +1362,18 @@
 //                  } catch (UnresolvedException iioe) {
 //                  }
 //              }
-                // Delete the phis (all of them must have exactly one input).
-                for (PhiNode phi : begin.phis().snapshot()) {
-                    assert phi.valueCount() == 1;
-                    begin.stateAfter().deleteRedundantPhi(phi, phi.firstValue());
-                }
 
-                // Delete the loop end.
-                loopEndStateSplit.safeDelete();
-                loopEnd.safeDelete();
-
-                // Remove the loop begin.
-                EndNode loopEntryEnd = begin.forwardEdge();
-                FixedNode beginSucc = begin.next();
-                FrameState stateAfter = begin.stateAfter();
-                begin.safeDelete();
-                stateAfter.safeDelete();
-                loopEntryEnd.replaceAndDelete(beginSucc);
+                // Remove the loop begin or transform it into a merge.
+                assert begin.forwardEndCount() > 0;
+                currentGraph.reduceDegenerateLoopBegin(begin);
+            } else {
+                begin.stateAfter().simplifyLoopState();
             }
         }
     }
 
     private static LoopBeginNode loopBegin(Block block) {
-        EndNode endNode = (EndNode) block.firstInstruction.next();
-        LoopBeginNode loopBegin = (LoopBeginNode) endNode.merge();
+        LoopBeginNode loopBegin = (LoopBeginNode) ((EndNode) block.firstInstruction.next()).merge();
         return loopBegin;
     }
 
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.lir/src/com/oracle/max/graal/lir/cfg/ControlFlowGraph.java
--- a/graal/com.oracle.max.graal.lir/src/com/oracle/max/graal/lir/cfg/ControlFlowGraph.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.lir/src/com/oracle/max/graal/lir/cfg/ControlFlowGraph.java	Thu Feb 16 11:57:38 2012 +0100
@@ -136,7 +136,7 @@
                 // First time we see this block: push all successors.
                 for (Node suxNode : block.getEndNode().cfgSuccessors()) {
                     Block suxBlock = blockFor(suxNode);
-                    assert suxBlock.id != BLOCK_ID_VISITED;
+                    assert suxBlock.id != BLOCK_ID_VISITED : "Sux already visited?? from " + block.getEndNode() + " to " + suxNode;
                     if (suxBlock.id == BLOCK_ID_INITIAL) {
                         stack.add(suxBlock);
                     }
@@ -163,7 +163,9 @@
                 predecessors.add(nodeToBlock.get(predNode));
             }
             if (block.getBeginNode() instanceof LoopBeginNode) {
-                predecessors.add(nodeToBlock.get(((LoopBeginNode) block.getBeginNode()).loopEnd()));
+                for (LoopEndNode predNode : ((LoopBeginNode) block.getBeginNode()).orderedLoopEnds()) {
+                    predecessors.add(nodeToBlock.get(predNode));
+                }
             }
             block.predecessors = predecessors;
 
@@ -186,9 +188,10 @@
                 Loop loop = new Loop(block.getLoop(), loopsList.size(), block);
                 loopsList.add(loop);
 
-                LoopEndNode end = ((LoopBeginNode) beginNode).loopEnd();
-                Block endBlock = nodeToBlock.get(end);
-                computeLoopBlocks(endBlock, loop);
+                for (LoopEndNode end : ((LoopBeginNode) beginNode).loopEnds()) {
+                    Block endBlock = nodeToBlock.get(end);
+                    computeLoopBlocks(endBlock, loop);
+                }
             }
         }
         loops = loopsList.toArray(new Loop[loopsList.size()]);
@@ -228,16 +231,12 @@
             List<Block> predecessors = block.getPredecessors();
             assert predecessors.size() > 0;
 
-            if (block.isLoopHeader()) {
-                // Loop headers have exactly one non-loop predecessor, and that is the dominator.
-                setDominator(block, predecessors.get(0));
-                continue;
-            }
-
             Block dominator = predecessors.get(0);
             for (int j = 1; j < predecessors.size(); j++) {
                 Block pred = predecessors.get(j);
-                dominator = commonDominator(dominator, pred);
+                if (!pred.isLoopEnd()) {
+                    dominator = commonDominator(dominator, pred);
+                }
             }
             setDominator(block, dominator);
         }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/EndNode.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/EndNode.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/EndNode.java	Thu Feb 16 11:57:38 2012 +0100
@@ -28,7 +28,7 @@
 import com.oracle.max.graal.nodes.spi.*;
 import com.oracle.max.graal.nodes.type.*;
 
-public final class EndNode extends FixedNode implements Node.IterableNodeType, LIRLowerable {
+public class EndNode extends FixedNode implements Node.IterableNodeType, LIRLowerable {
 
     public EndNode() {
         super(StampFactory.illegal());
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FrameState.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FrameState.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FrameState.java	Thu Feb 16 11:57:38 2012 +0100
@@ -329,7 +329,7 @@
      * @param block the block begin for which we are creating the phi
      * @param i the index into the stack for which to create a phi
      */
-    public PhiNode setupPhiForStack(MergeNode block, int i) {
+    public PhiNode setupLoopPhiForStack(MergeNode block, int i) {
         ValueNode p = stackAt(i);
         if (p != null) {
             if (p instanceof PhiNode) {
@@ -339,6 +339,7 @@
                 }
             }
             PhiNode phi = graph().unique(new PhiNode(p.kind(), block, PhiType.Value));
+            phi.addInput(p);
             setValueAt(localsSize + i, phi);
             return phi;
         }
@@ -350,7 +351,7 @@
      * @param block the block begin for which we are creating the phi
      * @param i the index of the local variable for which to create the phi
      */
-    public PhiNode setupPhiForLocal(MergeNode block, int i) {
+    public PhiNode setupLoopPhiForLocal(MergeNode block, int i) {
         ValueNode p = localAt(i);
         if (p instanceof PhiNode) {
             PhiNode phi = (PhiNode) p;
@@ -359,6 +360,7 @@
             }
         }
         PhiNode phi = graph().unique(new PhiNode(p.kind(), block, PhiType.Value));
+        phi.addInput(p);
         storeLocal(i, phi);
         return phi;
     }
@@ -401,9 +403,9 @@
         for (int i = 0; i < valuesSize(); i++) {
             ValueNode currentValue = valueAt(i);
             ValueNode otherValue = other.valueAt(i);
-            if (currentValue != otherValue) {
+            if (currentValue != otherValue || block instanceof LoopBeginNode) {
                 if (block.isPhiAtMerge(currentValue)) {
-                    addToPhi((PhiNode) currentValue, otherValue);
+                    addToPhi((PhiNode) currentValue, otherValue, block instanceof LoopBeginNode);
                 } else {
                     setValueAt(i, combineValues(currentValue, otherValue, block));
                 }
@@ -411,12 +413,18 @@
         }
     }
 
-    private ValueNode combineValues(ValueNode currentValue, ValueNode otherValue, MergeNode block) {
+    public void simplifyLoopState() {
+        for (PhiNode phi : values.filter(PhiNode.class).snapshot()) {
+            checkRedundantPhi(phi);
+        }
+    }
+
+    private static ValueNode combineValues(ValueNode currentValue, ValueNode otherValue, MergeNode block) {
         if (currentValue == null || otherValue == null || currentValue.kind() != otherValue.kind()) {
             return null;
         }
 
-        PhiNode phi = graph().unique(new PhiNode(currentValue.kind(), block, PhiType.Value));
+        PhiNode phi = currentValue.graph().add(new PhiNode(currentValue.kind(), block, PhiType.Value));
         for (int j = 0; j < block.phiPredecessorCount(); ++j) {
             phi.addInput(currentValue);
         }
@@ -425,43 +433,28 @@
         return phi;
     }
 
-    private static void addToPhi(PhiNode phiNode, ValueNode otherValue) {
+    private static void addToPhi(PhiNode phiNode, ValueNode otherValue, boolean recursiveInvalidCheck) {
         if (otherValue == null || otherValue.kind() != phiNode.kind()) {
-            phiNode.replaceAtUsages(null);
-            phiNode.safeDelete();
+            if (recursiveInvalidCheck) {
+                deleteInvalidPhi(phiNode);
+            } else {
+                phiNode.replaceAtUsages(null);
+                phiNode.safeDelete();
+            }
         } else {
             phiNode.addInput(otherValue);
         }
     }
 
-    public void mergeLoop(LoopBeginNode block, FrameStateAccess other) {
-        assert checkSize(other);
-        for (int i = 0; i < valuesSize(); i++) {
-            PhiNode currentValue = (PhiNode) valueAt(i);
-            if (currentValue != null) {
-                assert currentValue.merge() == block;
-                assert currentValue.valueCount() == 1;
-                ValueNode otherValue = other.valueAt(i);
-                if (otherValue == currentValue) {
-                    deleteRedundantPhi(currentValue, currentValue.firstValue());
-                } else if (otherValue == null || otherValue.kind() != currentValue.kind()) {
-                    deleteInvalidPhi(currentValue);
-                } else {
-                    currentValue.addInput(otherValue);
-                }
-            }
-        }
-    }
-
-    public void deleteRedundantPhi(PhiNode redundantPhi, ValueNode phiValue) {
+    public static void deleteRedundantPhi(PhiNode redundantPhi, ValueNode phiValue) {
         Collection<PhiNode> phiUsages = redundantPhi.usages().filter(PhiNode.class).snapshot();
-        ((StructuredGraph) graph()).replaceFloating(redundantPhi, phiValue);
+        ((StructuredGraph) redundantPhi.graph()).replaceFloating(redundantPhi, phiValue);
         for (PhiNode phi : phiUsages) {
             checkRedundantPhi(phi);
         }
     }
 
-    private void checkRedundantPhi(PhiNode phiNode) {
+    private static void checkRedundantPhi(PhiNode phiNode) {
         if (phiNode.isDeleted() || phiNode.valueCount() == 1) {
             return;
         }
@@ -472,7 +465,7 @@
         }
     }
 
-    private void deleteInvalidPhi(PhiNode phiNode) {
+    private static void deleteInvalidPhi(PhiNode phiNode) {
         if (!phiNode.isDeleted()) {
             Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot();
             phiNode.replaceAtUsages(null);
@@ -575,13 +568,13 @@
             // always insert phis for the stack
             ValueNode x = stackAt(i);
             if (x != null) {
-                setupPhiForStack(loopBegin, i).addInput(x);
+                setupLoopPhiForStack(loopBegin, i);
             }
         }
         for (int i = 0; i < localsSize(); i++) {
             ValueNode x = localAt(i);
             if (x != null) {
-                setupPhiForLocal(loopBegin, i).addInput(x);
+                setupLoopPhiForLocal(loopBegin, i);
             }
         }
     }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/IfNode.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/IfNode.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/IfNode.java	Thu Feb 16 11:57:38 2012 +0100
@@ -121,7 +121,7 @@
                 EndNode trueEnd = (EndNode) trueSuccessor().next();
                 EndNode falseEnd = (EndNode) falseSuccessor().next();
                 MergeNode merge = trueEnd.merge();
-                if (merge == falseEnd.merge() && merge.endCount() == 2) {
+                if (merge == falseEnd.merge() && merge.forwardEndCount() == 2) {
                     Iterator<PhiNode> phis = merge.phis().iterator();
                     if (!phis.hasNext()) {
                         // empty if construct with no phis: remove it
@@ -130,7 +130,7 @@
                         PhiNode singlePhi = phis.next();
                         if (!phis.hasNext()) {
                             // one phi at the merge of an otherwise empty if construct: try to convert into a MaterializeNode
-                            boolean inverted = trueEnd == merge.endAt(FALSE_EDGE);
+                            boolean inverted = trueEnd == merge.forwardEndAt(FALSE_EDGE);
                             ValueNode trueValue = singlePhi.valueAt(inverted ? 1 : 0);
                             ValueNode falseValue = singlePhi.valueAt(inverted ? 0 : 1);
                             if (trueValue.kind() != falseValue.kind()) {
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/InvokeNode.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/InvokeNode.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/InvokeNode.java	Thu Feb 16 11:57:38 2012 +0100
@@ -71,7 +71,9 @@
     @Override
     public Map<Object, Object> getDebugProperties() {
         Map<Object, Object> debugProperties = super.getDebugProperties();
-        debugProperties.put("targetMethod", CiUtil.format("%h.%n(%p)", callTarget.targetMethod()));
+        if (callTarget != null && callTarget.targetMethod() != null) {
+            debugProperties.put("targetMethod", CiUtil.format("%h.%n(%p)", callTarget.targetMethod()));
+        }
         return debugProperties;
     }
 
@@ -85,6 +87,9 @@
         if (verbosity == Verbosity.Long) {
             return super.toString(Verbosity.Short) + "(bci=" + bci() + ")";
         } else if (verbosity == Verbosity.Name) {
+            if (callTarget == null || callTarget.targetMethod() == null) {
+                return "Invoke#??Invalid!";
+            }
             return "Invoke#" + callTarget.targetMethod().name();
         } else {
             return super.toString(verbosity);
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopBeginNode.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopBeginNode.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopBeginNode.java	Thu Feb 16 11:57:38 2012 +0100
@@ -25,12 +25,13 @@
 import java.util.*;
 
 import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.graph.iterators.*;
 import com.oracle.max.graal.nodes.spi.*;
 
 
 public class LoopBeginNode extends MergeNode implements Node.IterableNodeType, LIRLowerable {
-
     private double loopFrequency;
+    private int nextEndIndex;
 
     public LoopBeginNode() {
         loopFrequency = 1;
@@ -44,8 +45,24 @@
         this.loopFrequency = loopFrequency;
     }
 
-    public LoopEndNode loopEnd() {
-        return usages().filter(LoopEndNode.class).first();
+    public NodeIterable<LoopEndNode> loopEnds() {
+        return usages().filter(LoopEndNode.class);
+    }
+
+    public List<LoopEndNode> orderedLoopEnds() {
+        List<LoopEndNode> snapshot = usages().filter(LoopEndNode.class).snapshot();
+        Collections.sort(snapshot, new Comparator<LoopEndNode>() {
+            @Override
+            public int compare(LoopEndNode o1, LoopEndNode o2) {
+                return o1.endIndex() - o2.endIndex();
+            }
+        });
+        return snapshot;
+    }
+
+    public EndNode forwardEnd() {
+        assert forwardEndCount() == 1;
+        return forwardEndAt(0);
     }
 
     @Override
@@ -54,39 +71,61 @@
     }
 
     @Override
+    protected void deleteEnd(EndNode end) {
+        if (end instanceof LoopEndNode) {
+            LoopEndNode loopEnd = (LoopEndNode) end;
+            loopEnd.setLoopBegin(null);
+            int idx = loopEnd.endIndex();
+            for (LoopEndNode le : loopEnds()) {
+                int leIdx = le.endIndex();
+                assert leIdx != idx;
+                if (leIdx > idx) {
+                    le.setEndIndex(leIdx - 1);
+                }
+            }
+        } else {
+            super.deleteEnd(end);
+        }
+    }
+
+    @Override
     public int phiPredecessorCount() {
-        return endCount() + 1;
+        return forwardEndCount() + loopEnds().count();
     }
 
     @Override
-    public int phiPredecessorIndex(FixedNode pred) {
-        if (pred == forwardEdge()) {
-            return 0;
-        } else if (pred == this.loopEnd()) {
-            return 1;
+    public int phiPredecessorIndex(EndNode pred) {
+        if (pred instanceof LoopEndNode) {
+            LoopEndNode loopEnd = (LoopEndNode) pred;
+            if (loopEnd.loopBegin() == this) {
+                assert loopEnd.endIndex() < loopEnds().count();
+                return loopEnd.endIndex() + forwardEndCount();
+            }
+        } else {
+            return super.forwardEndIndex(pred);
         }
-        throw ValueUtil.shouldNotReachHere("unknown pred : " + pred + "(sp=" + forwardEdge() + ", le=" + this.loopEnd() + ")");
+        throw ValueUtil.shouldNotReachHere("unknown pred : " + pred);
     }
 
     @Override
-    public FixedNode phiPredecessorAt(int index) {
-        if (index == 0) {
-            return forwardEdge();
-        } else if (index == 1) {
-            return loopEnd();
+    public EndNode phiPredecessorAt(int index) {
+        if (index < forwardEndCount()) {
+            return forwardEndAt(index);
+        }
+        for (LoopEndNode end : loopEnds()) {
+            int idx = index - forwardEndCount();
+            assert idx >= 0;
+            if (end.endIndex() == idx) {
+                return end;
+            }
         }
         throw ValueUtil.shouldNotReachHere();
     }
 
-    public EndNode forwardEdge() {
-        return this.endAt(0);
-    }
-
     @Override
     public boolean verify() {
-        assertTrue(loopEnd() != null, "missing loopEnd");
-        assertTrue(forwardEdge() != null, "missing forwardEdge");
-        assertTrue(usages().filter(LoopEndNode.class).count() == 1, "multiple loop ends");
+        assertTrue(loopEnds().count() > 0, "missing loopEnd");
+        assertTrue(forwardEndCount() == 1, "LoopBegin should only have one forward edge");
         return super.verify();
     }
 
@@ -96,4 +135,8 @@
         properties.put("loopFrequency", String.format("%7.1f", loopFrequency));
         return properties;
     }
+
+    public int nextEndIndex() {
+        return nextEndIndex++;
+    }
 }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopEndNode.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopEndNode.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopEndNode.java	Thu Feb 16 11:57:38 2012 +0100
@@ -22,19 +22,29 @@
  */
 package com.oracle.max.graal.nodes;
 
+import java.util.*;
+
 import com.oracle.max.graal.graph.*;
 import com.oracle.max.graal.nodes.spi.*;
-import com.oracle.max.graal.nodes.type.*;
 
 
-public class LoopEndNode extends FixedNode implements Node.IterableNodeType, LIRLowerable {
+public final class LoopEndNode extends EndNode {
 
     @Input(notDataflow = true) private LoopBeginNode loopBegin;
     @Data private boolean safepointPolling;
+    @Data private int endIndex;
 
-    public LoopEndNode() {
-        super(StampFactory.illegal());
+    public LoopEndNode(LoopBeginNode begin) {
+        int idx = begin.nextEndIndex();
+        assert idx >= 0;
         this.safepointPolling = true;
+        this.endIndex = idx;
+        this.loopBegin = begin;
+    }
+
+    @Override
+    public MergeNode merge() {
+        return loopBegin();
     }
 
     public LoopBeginNode loopBegin() {
@@ -58,11 +68,26 @@
     @Override
     public void generate(LIRGeneratorTool gen) {
         gen.visitLoopEnd(this);
+        super.generate(gen);
     }
 
     @Override
     public boolean verify() {
         assertTrue(loopBegin != null, "must have a loop begin");
+        assertTrue(usages().count() == 0, "LoopEnds can not be used");
         return super.verify();
     }
+
+    public int endIndex() {
+        return endIndex;
+    }
+
+    public void setEndIndex(int idx) {
+        this.endIndex = idx;
+    }
+
+    @Override
+    public Iterable< ? extends Node> cfgSuccessors() {
+        return Collections.emptyList();
+    }
 }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/MergeNode.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/MergeNode.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/MergeNode.java	Thu Feb 16 11:57:38 2012 +0100
@@ -43,19 +43,19 @@
         gen.visitMerge(this);
     }
 
-    public int endIndex(EndNode end) {
+    public int forwardEndIndex(EndNode end) {
         return ends.indexOf(end);
     }
 
-    public void addEnd(EndNode end) {
+    public void addForwardEnd(EndNode end) {
         ends.add(end);
     }
 
-    public int endCount() {
+    public int forwardEndCount() {
         return ends.size();
     }
 
-    public EndNode endAt(int index) {
+    public EndNode forwardEndAt(int index) {
         return ends.get(index);
     }
 
@@ -74,67 +74,41 @@
         return value instanceof PhiNode && ((PhiNode) value).merge() == this;
     }
 
-
-    /**
-     * Formats a given instruction as a value in a {@linkplain FrameState frame state}. If the instruction is a phi defined at a given
-     * block, its {@linkplain PhiNode#valueCount() inputs} are appended to the returned string.
-     *
-     * @param index the index of the value in the frame state
-     * @param value the frame state value
-     * @return the instruction representation as a string
-     */
-    public String stateString(int index, ValueNode value) {
-        StringBuilder sb = new StringBuilder(30);
-        sb.append(String.format("%2d  %s", index, ValueUtil.valueString(value)));
-        if (value instanceof PhiNode) {
-            PhiNode phi = (PhiNode) value;
-            // print phi operands
-            if (phi.merge() == this) {
-                sb.append(" [");
-                for (int j = 0; j < phi.valueCount(); j++) {
-                    sb.append(' ');
-                    ValueNode operand = phi.valueAt(j);
-                    if (operand != null) {
-                        sb.append(ValueUtil.valueString(operand));
-                    } else {
-                        sb.append("NULL");
-                    }
-                }
-                sb.append("] ");
-            }
-        }
-        return sb.toString();
-    }
-
     /**
      * Removes the given end from the merge, along with the entries corresponding to this end in the phis connected to the merge.
      * @param pred the end to remove
      */
     public void removeEnd(EndNode pred) {
-        int predIndex = ends.indexOf(pred);
+        int predIndex = phiPredecessorIndex(pred);
         assert predIndex != -1;
-        ends.remove(predIndex);
-
+        deleteEnd(pred);
         for (PhiNode phi : phis()) {
             phi.removeInput(predIndex);
         }
     }
 
+    protected void deleteEnd(EndNode end) {
+        ends.remove(end);
+    }
+
     public void clearEnds() {
         ends.clear();
     }
 
-    public int phiPredecessorCount() {
-        return endCount();
+    public NodeIterable<EndNode> forwardEnds() {
+        return ends;
     }
 
-    public int phiPredecessorIndex(FixedNode pred) {
-        EndNode end = (EndNode) pred;
-        return endIndex(end);
+    public int phiPredecessorCount() {
+        return forwardEndCount();
     }
 
-    public FixedNode phiPredecessorAt(int index) {
-        return endAt(index);
+    public int phiPredecessorIndex(EndNode pred) {
+        return forwardEndIndex(pred);
+    }
+
+    public EndNode phiPredecessorAt(int index) {
+        return forwardEndAt(index);
     }
 
     public NodeIterable<PhiNode> phis() {
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PhiNode.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PhiNode.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PhiNode.java	Thu Feb 16 11:57:38 2012 +0100
@@ -100,7 +100,7 @@
         values.set(i, x);
     }
 
-    public ValueNode valueAt(FixedNode pred) {
+    public ValueNode valueAt(EndNode pred) {
         return valueAt(merge().phiPredecessorIndex(pred));
     }
 
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/StructuredGraph.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/StructuredGraph.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/StructuredGraph.java	Thu Feb 16 11:57:38 2012 +0100
@@ -285,4 +285,37 @@
         newNode.setNext(node);
     }
 
+    public void reduceDegenerateLoopBegin(LoopBeginNode begin) {
+        assert begin.loopEnds().count() == 0 : "Loop begin still has backedges";
+        if (begin.forwardEndCount() == 1) { // bypass merge and remove
+            reduceTrivialMerge(begin);
+        } else { // convert to merge
+            MergeNode merge = this.add(new MergeNode());
+            this.replaceFixedWithFixed(begin, merge);
+        }
+    }
+
+    public void reduceTrivialMerge(MergeNode merge) {
+        assert merge.forwardEndCount() == 1;
+        assert !(merge instanceof LoopBeginNode) || ((LoopBeginNode) merge).loopEnds().count() == 0;
+        for (PhiNode phi : merge.phis().snapshot()) {
+            assert phi.valueCount() == 1;
+            ValueNode singleValue = phi.valueAt(0);
+            phi.replaceAtUsages(singleValue);
+            phi.safeDelete();
+        }
+        EndNode singleEnd = merge.forwardEndAt(0);
+        FixedNode sux = merge.next();
+        FrameState stateAfter = merge.stateAfter();
+        merge.safeDelete();
+        if (stateAfter != null && stateAfter.usages().count() == 0) {
+            stateAfter.safeDelete();
+        }
+        if (sux == null) {
+            singleEnd.replaceAtPredecessors(null);
+            singleEnd.safeDelete();
+        } else {
+            singleEnd.replaceAndDelete(sux);
+        }
+    }
 }
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/calc/ConditionalNode.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/calc/ConditionalNode.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/calc/ConditionalNode.java	Thu Feb 16 11:57:38 2012 +0100
@@ -81,8 +81,8 @@
         ifNode.setTrueSuccessor(BeginNode.begin(trueEnd));
         ifNode.setFalseSuccessor(BeginNode.begin(falseEnd));
         MergeNode merge = graph.add(new MergeNode());
-        merge.addEnd(trueEnd);
-        merge.addEnd(falseEnd);
+        merge.addForwardEnd(trueEnd);
+        merge.addForwardEnd(falseEnd);
         PhiNode phi = graph.unique(new PhiNode(kind, merge, PhiType.Value));
         phi.addInput(trueValue);
         phi.addInput(falseValue);
diff -r 09402dddc51e -r a3882fd1ae61 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/util/GraphUtil.java
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/util/GraphUtil.java	Wed Feb 15 20:09:25 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/util/GraphUtil.java	Thu Feb 16 11:57:38 2012 +0100
@@ -22,10 +22,13 @@
  */
 package com.oracle.max.graal.nodes.util;
 
+import static com.oracle.max.graal.graph.iterators.NodePredicates.*;
+
 import java.util.*;
 
 import com.oracle.max.graal.graph.*;
 import com.oracle.max.graal.nodes.*;
+import com.oracle.max.graal.nodes.calc.*;
 
 public class GraphUtil {
 
@@ -35,9 +38,6 @@
             // We reached a control flow end.
             EndNode end = (EndNode) node;
             killEnd(end);
-        } else if (node instanceof LoopEndNode) {
-            // We reached a loop end.
-            killLoopEnd(node);
         } else {
             // Normal control flow node.
             for (Node successor : node.successors().snapshot()) {
@@ -47,59 +47,33 @@
         propagateKill(node);
     }
 
-    private static void killLoopEnd(FixedNode node) {
-        LoopEndNode loopEndNode = (LoopEndNode) node;
-        LoopBeginNode loop = loopEndNode.loopBegin();
-        loopEndNode.setLoopBegin(null);
-        EndNode endNode = loop.endAt(0);
-        assert endNode.predecessor() != null;
-        replaceLoopPhis(loop);
-        loop.removeEnd(endNode);
-
-        FixedNode next = loop.next();
-        loop.setNext(null);
-        endNode.replaceAndDelete(next);
-        loop.safeDelete();
-    }
-
-    private static void replaceLoopPhis(MergeNode merge) {
-        for (Node usage : merge.usages().snapshot()) {
-            assert usage instanceof PhiNode;
-            ((StructuredGraph) merge.graph()).replaceFloating((PhiNode) usage, ((PhiNode) usage).valueAt(0));
-        }
-    }
-
     private static void killEnd(EndNode end) {
         MergeNode merge = end.merge();
-        if (merge instanceof LoopBeginNode) {
+        merge.removeEnd(end);
+        if (merge instanceof LoopBeginNode && merge.forwardEndCount() == 0) { //dead loop
             for (PhiNode phi : merge.phis().snapshot()) {
-                ValueNode value = phi.valueAt(0);
-                phi.replaceAndDelete(value);
+                propagateKill(phi);
             }
-            killCFG(merge);
-        } else {
-            merge.removeEnd(end);
-            if (merge.phiPredecessorCount() == 1) {
-                for (PhiNode phi : merge.phis().snapshot()) {
-                    ValueNode value = phi.valueAt(0);
-                    phi.replaceAndDelete(value);
-                }
-                Node replacedSux = merge.phiPredecessorAt(0);
-                Node pred = replacedSux.predecessor();
-                assert replacedSux instanceof EndNode;
-                FixedNode next = merge.next();
-                merge.setNext(null);
-                pred.replaceFirstSuccessor(replacedSux, next);
-                merge.safeDelete();
-                replacedSux.safeDelete();
+            LoopBeginNode begin = (LoopBeginNode) merge;
+            // disconnect and delete loop ends
+            for (LoopEndNode loopend : begin.loopEnds().snapshot()) {
+                loopend.predecessor().replaceFirstSuccessor(loopend, null);
+                loopend.safeDelete();
             }
+            FixedNode next = begin.next();
+            begin.safeDelete();
+            killCFG(next);
+        } else if (merge instanceof LoopBeginNode && ((LoopBeginNode) merge).loopEnds().count() == 0) { // not a loop anymore
+            ((StructuredGraph) end.graph()).reduceDegenerateLoopBegin((LoopBeginNode) merge);
+        } else if (merge.phiPredecessorCount() == 1) { // not a merge anymore
+            ((StructuredGraph) end.graph()).reduceTrivialMerge(merge);
         }
     }
 
     // TODO(tw): Factor this code with other branch deletion code.
     public static void propagateKill(Node node) {
         if (node != null && node.isAlive()) {
-            List<Node> usagesSnapshot = node.usages().snapshot();
+            List<Node> usagesSnapshot = node.usages().filter(isA(FloatingNode.class).or(CallTargetNode.class)).snapshot();
 
             // null out remaining usages
             node.replaceAtUsages(null);
@@ -108,7 +82,11 @@
 
             for (Node usage : usagesSnapshot) {
                 if (!usage.isDeleted()) {
-                    propagateKill(usage);
+                    if (usage instanceof PhiNode) {
+                        usage.replaceFirstInput(node, null);
+                    } else {
+                        propagateKill(usage);
+                    }
                 }
             }
         }