--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java	Mon Nov 04 17:17:08 2013 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java	Mon Nov 04 17:18:28 2013 +0100
@@ -60,7 +60,7 @@
 
     public void addAll(Iterable<? extends Node> nodes) {
         for (Node node : nodes) {
-            if (node.isAlive() && !node.isExternal()) {
+            if (node.isAlive()) {
                 this.add(node);
             }
         }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ConstantNode.java	Mon Nov 04 17:17:08 2013 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ConstantNode.java	Mon Nov 04 17:18:28 2013 +0100
@@ -78,6 +78,11 @@
     }
 
     @Override
+    public boolean isDeleted() {
+        return false;
+    }
+
+    @Override
     public boolean isAlive() {
         return true;
     }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java	Mon Nov 04 17:17:08 2013 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java	Mon Nov 04 17:18:28 2013 +0100
@@ -314,26 +314,67 @@
             }
         } while (v != null);
 
-        // if the simple check fails (this can happen for complicated phi/proxy/phi constructs), we
-        // do an exhaustive search
         if (v == null) {
+            v = new OriginalValueSearch(proxy).result;
+        }
+        return v;
+    }
+
+    /**
+     * Exhaustive search for {@link GraphUtil#originalValue(ValueNode)} when a simple search fails.
+     * This can happen in the presence of complicated phi/proxy/phi constructs.
+     */
+    static class OriginalValueSearch {
+        ValueNode result;
+
+        public OriginalValueSearch(ValueNode proxy) {
             NodeWorkList worklist = proxy.graph().createNodeWorkList();
             worklist.add(proxy);
             for (Node node : worklist) {
                 if (node instanceof ValueProxy) {
-                    worklist.add(((ValueProxy) node).getOriginalValue());
+                    ValueNode originalValue = ((ValueProxy) node).getOriginalValue();
+                    if (!process(originalValue, worklist)) {
+                        return;
+                    }
                 } else if (node instanceof PhiNode) {
-                    worklist.addAll(((PhiNode) node).values());
+                    for (Node value : ((PhiNode) node).values()) {
+                        if (!process((ValueNode) value, worklist)) {
+                            return;
+                        }
+                    }
                 } else {
-                    if (v == null) {
-                        v = (ValueNode) node;
-                    } else {
-                        return null;
+                    if (!process((ValueNode) node, null)) {
+                        return;
                     }
                 }
             }
         }
-        return v;
+
+        /**
+         * Process a node as part of this search.
+         * 
+         * @param node the next node encountered in the search
+         * @param worklist if non-null and {@code node} is not external, {@code node} will be added
+         *            to this list. Otherwise, {@code node} is treated as a candidate result.
+         * @return true if the search should continue, false if a definitive {@link #result} has
+         *         been found
+         */
+        private boolean process(ValueNode node, NodeWorkList worklist) {
+            if (node.isAlive()) {
+                if (node.isExternal() || worklist == null) {
+                    if (result == null) {
+                        // Initial candidate result: continue search
+                        result = node;
+                    } else if (result != node) {
+                        // Conflicts with existing candidate: stop search with null result
+                        result = null;
+                        return false;
+                    }
+                } else {
+                    worklist.add(node);
+                }
+            }
+            return true;
+        }
     }
-
 }