# HG changeset patch
# User Lukas Stadler <lukas.stadler@oracle.com>
# Date 1427979350 -7200
# Node ID 8ff9e165002b1119d8b84cfa42096c32e73c5eee
# Parent  33be8eb8cbd53a2d360434a49e02638559113b56
canonicalize during PEA

diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Thu Apr 02 14:55:50 2015 +0200
@@ -297,7 +297,20 @@
         return add(node);
     }
 
+    public <T extends Node> void addWithoutUniqueWithInputs(T node) {
+        addInputs(node);
+        addHelper(node);
+    }
+
     public <T extends Node> T addOrUniqueWithInputs(T node) {
+        addInputs(node);
+        if (node.getNodeClass().valueNumberable()) {
+            return uniqueHelper(node, true);
+        }
+        return add(node);
+    }
+
+    private <T extends Node> void addInputs(T node) {
         NodePosIterator iterator = node.inputs().iterator();
         while (iterator.hasNext()) {
             Position pos = iterator.nextPosition();
@@ -307,10 +320,6 @@
                 pos.initialize(node, addOrUniqueWithInputs(input));
             }
         }
-        if (node.getNodeClass().valueNumberable()) {
-            return uniqueHelper(node, true);
-        }
-        return add(node);
     }
 
     private <T extends Node> T addHelper(T node) {
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java	Thu Apr 02 14:55:50 2015 +0200
@@ -41,6 +41,10 @@
             return true;
         }
 
+        default boolean isCfgKill() {
+            return false;
+        }
+
         void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes);
     }
 
@@ -158,20 +162,22 @@
         return size == 0;
     }
 
-    public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
+    public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes, boolean cfgKills) {
         for (int i = 0; i < size(); i++) {
             Effect effect = effects[i];
-            try {
-                effect.apply(graph, obsoleteNodes);
-            } catch (Throwable t) {
-                StringBuilder str = new StringBuilder();
-                toString(str, i);
-                throw new GraalInternalError(t).addContext("effect", str);
-            }
-            if (effect.isVisible() && Debug.isLogEnabled()) {
-                StringBuilder str = new StringBuilder();
-                toString(str, i);
-                Debug.log("    %s", str);
+            if (effect.isCfgKill() == cfgKills) {
+                try {
+                    effect.apply(graph, obsoleteNodes);
+                } catch (Throwable t) {
+                    StringBuilder str = new StringBuilder();
+                    toString(str, i);
+                    throw new GraalInternalError(t).addContext("effect", str);
+                }
+                if (effect.isVisible() && Debug.isLogEnabled()) {
+                    StringBuilder str = new StringBuilder();
+                    toString(str, i);
+                    Debug.log("    %s", str);
+                }
             }
         }
     }
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsBlockState.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsBlockState.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsBlockState.java	Thu Apr 02 14:55:50 2015 +0200
@@ -26,6 +26,19 @@
 
 public abstract class EffectsBlockState<T extends EffectsBlockState<T>> {
 
+    /*
+     * This flag specifies whether this path that leads to this block is unreachable.
+     */
+    private boolean dead;
+
+    public EffectsBlockState() {
+        // emtpy
+    }
+
+    public EffectsBlockState(EffectsBlockState<T> other) {
+        this.dead = other.dead;
+    }
+
     @Override
     public String toString() {
         return "";
@@ -33,6 +46,14 @@
 
     protected abstract boolean equivalentTo(T other);
 
+    public boolean isDead() {
+        return dead;
+    }
+
+    public void markAsDead() {
+        this.dead = true;
+    }
+
     protected static <K, V> boolean compareMaps(Map<K, V> left, Map<K, V> right) {
         if (left.size() != right.size()) {
             return false;
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsClosure.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsClosure.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsClosure.java	Thu Apr 02 14:55:50 2015 +0200
@@ -22,14 +22,14 @@
  */
 package com.oracle.graal.virtual.phases.ea;
 
-import static com.oracle.graal.compiler.common.GraalOptions.*;
-
 import java.util.*;
 
 import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.compiler.common.type.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.util.*;
@@ -48,6 +48,7 @@
     protected final BlockMap<GraphEffectList> blockEffects;
     private final Map<Loop<Block>, GraphEffectList> loopMergeEffects = CollectionsFactory.newIdentityMap();
     private final Map<LoopBeginNode, BlockT> loopEntryStates = Node.newIdentityMap();
+    private final NodeBitMap hasScalarReplacedInputs;
 
     protected boolean changed;
 
@@ -55,6 +56,7 @@
         this.schedule = schedule;
         this.cfg = cfg;
         this.aliases = cfg.graph.createNodeMap();
+        this.hasScalarReplacedInputs = cfg.graph.createNodeBitMap();
         this.blockEffects = new BlockMap<>(cfg);
         for (Block block : cfg.getBlocks()) {
             blockEffects.put(block, new GraphEffectList());
@@ -67,9 +69,10 @@
     }
 
     @Override
-    public void applyEffects() {
+    public final void applyEffects() {
         final StructuredGraph graph = cfg.graph;
         final ArrayList<Node> obsoleteNodes = new ArrayList<>(0);
+        final ArrayList<GraphEffectList> effectList = new ArrayList<>();
         BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() {
 
             @Override
@@ -77,19 +80,15 @@
                 return null;
             }
 
-            private void apply(GraphEffectList effects, Object context) {
-                if (!effects.isEmpty()) {
-                    Debug.log(" ==== effects for %s", context);
-                    effects.apply(graph, obsoleteNodes);
-                    if (TraceEscapeAnalysis.getValue()) {
-                        Debug.dump(5, graph, "After processing EffectsList for %s", context);
-                    }
+            private void apply(GraphEffectList effects) {
+                if (effects != null && !effects.isEmpty()) {
+                    effectList.add(effects);
                 }
             }
 
             @Override
             protected Void processBlock(Block block, Void currentState) {
-                apply(blockEffects.get(block), block);
+                apply(blockEffects.get(block));
                 return currentState;
             }
 
@@ -106,11 +105,20 @@
             @Override
             protected List<Void> processLoop(Loop<Block> loop, Void initialState) {
                 LoopInfo<Void> info = ReentrantBlockIterator.processLoop(this, loop, initialState);
-                apply(loopMergeEffects.get(loop), loop);
+                apply(loopMergeEffects.get(loop));
                 return info.exitStates;
             }
         };
         ReentrantBlockIterator.apply(closure, cfg.getStartBlock());
+        for (GraphEffectList effects : effectList) {
+            Debug.log(" ==== effects");
+            effects.apply(graph, obsoleteNodes, false);
+        }
+        for (GraphEffectList effects : effectList) {
+            Debug.log(" ==== cfg kill effects");
+            effects.apply(graph, obsoleteNodes, true);
+        }
+        Debug.dump(4, graph, "After applying effects");
         assert VirtualUtil.assertNonReachable(graph, obsoleteNodes);
         for (Node node : obsoleteNodes) {
             if (node.isAlive()) {
@@ -122,26 +130,45 @@
 
     @Override
     protected BlockT processBlock(Block block, BlockT state) {
-        VirtualUtil.trace("\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors());
+        if (!state.isDead()) {
+            GraphEffectList effects = blockEffects.get(block);
+
+            if (block.getBeginNode().predecessor() instanceof IfNode) {
+                IfNode ifNode = (IfNode) block.getBeginNode().predecessor();
+                LogicNode condition = ifNode.condition();
+                Node alias = getScalarAlias(condition);
+                if (alias instanceof LogicConstantNode) {
+                    LogicConstantNode constant = (LogicConstantNode) alias;
+                    boolean deadBranch = constant.getValue() != (block.getBeginNode() == ifNode.trueSuccessor());
+
+                    if (deadBranch) {
+                        state.markAsDead();
+                        effects.killIfBranch(ifNode, constant.getValue());
+                        return state;
+                    }
+                }
+            }
 
-        GraphEffectList effects = blockEffects.get(block);
-        FixedWithNextNode lastFixedNode = block.getBeginNode().predecessor() instanceof FixedWithNextNode ? (FixedWithNextNode) block.getBeginNode().predecessor() : null;
-        Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes();
-        for (Node node : nodes) {
-            aliases.set(node, null);
-            if (node instanceof LoopExitNode) {
-                LoopExitNode loopExit = (LoopExitNode) node;
-                for (ProxyNode proxy : loopExit.proxies()) {
-                    changed |= processNode(proxy, state, effects, lastFixedNode);
+            VirtualUtil.trace("\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors());
+
+            FixedWithNextNode lastFixedNode = block.getBeginNode().predecessor() instanceof FixedWithNextNode ? (FixedWithNextNode) block.getBeginNode().predecessor() : null;
+            Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes();
+            for (Node node : nodes) {
+                aliases.set(node, null);
+                if (node instanceof LoopExitNode) {
+                    LoopExitNode loopExit = (LoopExitNode) node;
+                    for (ProxyNode proxy : loopExit.proxies()) {
+                        changed |= processNode(proxy, state, effects, lastFixedNode);
+                    }
+                    processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block));
                 }
-                processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block));
+                changed |= processNode(node, state, effects, lastFixedNode);
+                if (node instanceof FixedWithNextNode) {
+                    lastFixedNode = (FixedWithNextNode) node;
+                }
             }
-            changed |= processNode(node, state, effects, lastFixedNode);
-            if (node instanceof FixedWithNextNode) {
-                lastFixedNode = (FixedWithNextNode) node;
-            }
+            VirtualUtil.trace(")\n    end state: %s\n", state);
         }
-        VirtualUtil.trace(")\n    end state: %s\n", state);
         return state;
     }
 
@@ -151,7 +178,7 @@
     protected BlockT merge(Block merge, List<BlockT> states) {
         assert blockEffects.get(merge).isEmpty();
         MergeProcessor processor = createMergeProcessor(merge);
-        processor.merge(states);
+        doMergeWithoutDead(processor, states);
         processor.commitEnds(states);
         blockEffects.get(merge).addAll(processor.mergeEffects);
         blockEffects.get(merge).addAll(processor.afterMergeEffects);
@@ -160,6 +187,14 @@
 
     @Override
     protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) {
+        if (initialState.isDead()) {
+            ArrayList<BlockT> states = new ArrayList<>();
+            for (int i = 0; i < loop.getExits().size(); i++) {
+                states.add(initialState);
+            }
+            return states;
+        }
+
         BlockT loopEntryState = initialState;
         BlockT lastMergedState = cloneState(initialState);
         MergeProcessor mergeProcessor = createMergeProcessor(loop.getHeader());
@@ -169,7 +204,7 @@
             List<BlockT> states = new ArrayList<>();
             states.add(initialState);
             states.addAll(info.endStates);
-            mergeProcessor.merge(states);
+            doMergeWithoutDead(mergeProcessor, states);
 
             Debug.log("================== %s", loop.getHeader());
             Debug.log("%s", mergeProcessor.newState);
@@ -197,6 +232,36 @@
         throw new GraalInternalError("too many iterations at %s", loop);
     }
 
+    private void doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states) {
+        int alive = 0;
+        for (BlockT state : states) {
+            if (!state.isDead()) {
+                alive++;
+            }
+        }
+        if (alive == 0) {
+            mergeProcessor.setNewState(states.get(0));
+        } else if (alive == states.size()) {
+            int[] stateIndexes = new int[states.size()];
+            for (int i = 0; i < stateIndexes.length; i++) {
+                stateIndexes[i] = i;
+            }
+            mergeProcessor.setStateIndexes(stateIndexes);
+            mergeProcessor.merge(states);
+        } else {
+            ArrayList<BlockT> aliveStates = new ArrayList<>(alive);
+            int[] stateIndexes = new int[alive];
+            for (int i = 0; i < states.size(); i++) {
+                if (!states.get(i).isDead()) {
+                    stateIndexes[aliveStates.size()] = i;
+                    aliveStates.add(states.get(i));
+                }
+            }
+            mergeProcessor.setStateIndexes(stateIndexes);
+            mergeProcessor.merge(aliveStates);
+        }
+    }
+
     private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) {
         for (int i = 0; i < loop.getExits().size(); i++) {
             assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getExits().get(i) + " / " + loop.getHeader();
@@ -210,11 +275,13 @@
 
     protected class MergeProcessor {
 
-        protected final Block mergeBlock;
-        protected final AbstractMergeNode merge;
+        private final Block mergeBlock;
+        private final AbstractMergeNode merge;
 
         protected final GraphEffectList mergeEffects;
         protected final GraphEffectList afterMergeEffects;
+
+        private int[] stateIndexes;
         protected BlockT newState;
 
         public MergeProcessor(Block mergeBlock) {
@@ -228,15 +295,51 @@
          * @param states the states that should be merged.
          */
         protected void merge(List<BlockT> states) {
-            newState = getInitialState();
+            setNewState(getInitialState());
+        }
+
+        private void setNewState(BlockT state) {
+            newState = state;
             mergeEffects.clear();
             afterMergeEffects.clear();
         }
 
+        private void setStateIndexes(int[] stateIndexes) {
+            this.stateIndexes = stateIndexes;
+        }
+
         @SuppressWarnings("unused")
         protected void commitEnds(List<BlockT> states) {
         }
 
+        protected final Block getPredecessor(int index) {
+            return mergeBlock.getPredecessors().get(stateIndexes[index]);
+        }
+
+        protected final NodeIterable<PhiNode> getPhis() {
+            return merge.phis();
+        }
+
+        protected final ValueNode getPhiValueAt(PhiNode phi, int index) {
+            return phi.valueAt(stateIndexes[index]);
+        }
+
+        protected final ValuePhiNode createValuePhi(Stamp stamp) {
+            return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]);
+        }
+
+        protected final void setPhiInput(PhiNode phi, int index, ValueNode value) {
+            afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value);
+        }
+
+        protected final int getStateIndex(int i) {
+            return stateIndexes[i];
+        }
+
+        protected final StructuredGraph graph() {
+            return merge.graph();
+        }
+
         @Override
         public String toString() {
             return "MergeProcessor@" + merge;
@@ -246,6 +349,15 @@
     public void addScalarAlias(ValueNode node, ValueNode alias) {
         assert !(alias instanceof VirtualObjectNode);
         aliases.set(node, alias);
+        for (Node usage : node.usages()) {
+            if (!hasScalarReplacedInputs.isNew(usage)) {
+                hasScalarReplacedInputs.mark(usage);
+            }
+        }
+    }
+
+    protected final boolean hasScalarReplacedInputs(Node node) {
+        return hasScalarReplacedInputs.isMarked(node);
     }
 
     public ValueNode getScalarAlias(ValueNode node) {
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Thu Apr 02 14:55:50 2015 +0200
@@ -33,16 +33,16 @@
 
 public class GraphEffectList extends EffectList {
 
-    public void addCounterBefore(final String group, final String name, final int increment, final boolean addContext, final FixedNode position) {
+    public void addCounterBefore(String group, String name, int increment, boolean addContext, FixedNode position) {
         add("add counter", graph -> DynamicCounterNode.addCounterBefore(group, name, increment, addContext, position));
     }
 
-    public void addCounterAfter(final String group, final String name, final int increment, final boolean addContext, final FixedWithNextNode position) {
+    public void addCounterAfter(String group, String name, int increment, boolean addContext, FixedWithNextNode position) {
         FixedNode nextPosition = position.next();
         add("add counter after", graph -> DynamicCounterNode.addCounterBefore(group, name, increment, addContext, nextPosition));
     }
 
-    public void addWeakCounterCounterBefore(final String group, final String name, final int increment, final boolean addContext, final ValueNode checkedValue, final FixedNode position) {
+    public void addWeakCounterCounterBefore(String group, String name, int increment, boolean addContext, ValueNode checkedValue, FixedNode position) {
         add("add weak counter", graph -> WeakCounterNode.addCounterBefore(group, name, increment, addContext, checkedValue, position));
     }
 
@@ -53,36 +53,35 @@
      * @param node The fixed node to be added to the graph.
      * @param position The fixed node before which the node should be added.
      */
-    public void addFixedNodeBefore(final FixedWithNextNode node, final FixedNode position) {
+    public void addFixedNodeBefore(FixedWithNextNode node, FixedNode position) {
         add("add fixed node", graph -> {
             assert !node.isAlive() && !node.isDeleted() && position.isAlive();
             graph.addBeforeFixed(position, graph.add(node));
         });
     }
 
+    public void ensureAdded(ValueNode node, FixedNode position) {
+        add("ensure added", graph -> {
+            assert position.isAlive();
+            if (!node.isAlive()) {
+                graph.addWithoutUniqueWithInputs(node);
+                if (node instanceof FixedNode) {
+                    graph.addBeforeFixed(position, (FixedWithNextNode) node);
+                }
+            }
+        });
+    }
+
     /**
      * Add the given floating node to the graph.
      *
      * @param node The floating node to be added.
      */
-    public void addFloatingNode(final ValueNode node, @SuppressWarnings("unused") final String cause) {
+    public void addFloatingNode(ValueNode node, @SuppressWarnings("unused") String cause) {
         add("add floating node", graph -> graph.addWithoutUnique(node));
     }
 
     /**
-     * Adds an value to the given phi node.
-     *
-     * @param node The phi node to which the value should be added.
-     * @param value The value that will be added to the phi node.
-     */
-    public void addPhiInput(final PhiNode node, final ValueNode value) {
-        add("add phi input", graph -> {
-            assert node.isAlive() && value.isAlive() : node + " " + value;
-            node.addInput(value);
-        });
-    }
-
-    /**
      * Sets the phi node's input at the given index to the given value, adding new phi inputs as
      * needed.
      *
@@ -90,7 +89,7 @@
      * @param index The index of the phi input to be changed.
      * @param value The new value for the phi input.
      */
-    public void initializePhiInput(final PhiNode node, final int index, final ValueNode value) {
+    public void initializePhiInput(PhiNode node, int index, ValueNode value) {
         add("set phi input", (graph, obsoleteNodes) -> {
             assert node.isAlive() && value.isAlive() && index >= 0;
             node.initializeValueAt(index, value);
@@ -104,18 +103,20 @@
      * @param node The frame state to which the state should be added.
      * @param state The virtual object state to add.
      */
-    public void addVirtualMapping(final FrameState node, final EscapeObjectState state) {
+    public void addVirtualMapping(FrameState node, EscapeObjectState state) {
         add("add virtual mapping", new Effect() {
             @Override
             public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
-                assert node.isAlive() && !state.isDeleted();
-                FrameState stateAfter = node;
-                for (int i = 0; i < stateAfter.virtualObjectMappingCount(); i++) {
-                    if (stateAfter.virtualObjectMappingAt(i).object() == state.object()) {
-                        stateAfter.virtualObjectMappings().remove(i);
+                if (node.isAlive()) {
+                    assert !state.isDeleted();
+                    FrameState stateAfter = node;
+                    for (int i = 0; i < stateAfter.virtualObjectMappingCount(); i++) {
+                        if (stateAfter.virtualObjectMappingAt(i).object() == state.object()) {
+                            stateAfter.virtualObjectMappings().remove(i);
+                        }
                     }
+                    stateAfter.addVirtualObjectMapping(state.isAlive() ? state : graph.unique(state));
                 }
-                stateAfter.addVirtualObjectMapping(state.isAlive() ? state : graph.unique(state));
             }
 
             @Override
@@ -130,7 +131,7 @@
      *
      * @param node The fixed node that should be deleted.
      */
-    public void deleteNode(final Node node) {
+    public void deleteNode(Node node) {
         add("delete fixed node", (graph, obsoleteNodes) -> {
             if (node instanceof FixedWithNextNode) {
                 GraphUtil.unlinkFixedNode((FixedWithNextNode) node);
@@ -139,6 +140,18 @@
         });
     }
 
+    public void killIfBranch(IfNode ifNode, boolean constantCondition) {
+        add("kill if branch", new Effect() {
+            public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
+                graph.removeSplitPropagate(ifNode, ifNode.getSuccessor(constantCondition));
+            }
+
+            public boolean isCfgKill() {
+                return true;
+            }
+        });
+    }
+
     /**
      * Replaces the given node at its usages without deleting it. If the current node is a fixed
      * node it will be disconnected from the control flow, so that it will be deleted by a
@@ -149,7 +162,7 @@
      *            non-connected {@link FixedWithNextNode} it will be added to the control flow.
      *
      */
-    public void replaceAtUsages(final ValueNode node, final ValueNode replacement) {
+    public void replaceAtUsages(ValueNode node, ValueNode replacement) {
         add("replace at usages", (graph, obsoleteNodes) -> {
             assert node.isAlive() && replacement.isAlive();
             if (replacement instanceof FixedWithNextNode && ((FixedWithNextNode) replacement).next() == null) {
@@ -171,13 +184,15 @@
      * @param oldInput The value to look for.
      * @param newInput The value to replace with.
      */
-    public void replaceFirstInput(final Node node, final Node oldInput, final Node newInput) {
+    public void replaceFirstInput(Node node, Node oldInput, Node newInput) {
         assert node.isAlive() && oldInput.isAlive() && !newInput.isDeleted();
         add("replace first input", new Effect() {
             @Override
             public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
-                assert node.isAlive() && oldInput.isAlive() && newInput.isAlive();
-                node.replaceFirstInput(oldInput, newInput);
+                if (node.isAlive()) {
+                    assert oldInput.isAlive() && newInput.isAlive();
+                    node.replaceFirstInput(oldInput, newInput);
+                }
             }
 
             @Override
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PEReadEliminationClosure.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PEReadEliminationClosure.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PEReadEliminationClosure.java	Thu Apr 02 14:55:50 2015 +0200
@@ -272,29 +272,28 @@
                     PhiNode phiNode = getPhi(entry, value.stamp().unrestricted());
                     mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
                     for (int i = 0; i < states.size(); i++) {
-                        afterMergeEffects.addPhiInput(phiNode, states.get(i).getReadCache(key.object, key.identity, key.index, PEReadEliminationClosure.this));
+                        setPhiInput(phiNode, i, states.get(i).getReadCache(key.object, key.identity, key.index, PEReadEliminationClosure.this));
                     }
                     newState.readCache.put(key, phiNode);
                 } else if (value != null) {
                     newState.readCache.put(key, value);
                 }
             }
-            for (PhiNode phi : merge.phis()) {
+            for (PhiNode phi : getPhis()) {
                 if (phi.getKind() == Kind.Object) {
                     for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
-                        if (entry.getKey().object == phi.valueAt(0)) {
+                        if (entry.getKey().object == getPhiValueAt(phi, 0)) {
                             mergeReadCachePhi(phi, entry.getKey().identity, entry.getKey().index, states);
                         }
                     }
-
                 }
             }
         }
 
         private void mergeReadCachePhi(PhiNode phi, LocationIdentity identity, int index, List<PEReadEliminationBlockState> states) {
-            ValueNode[] values = new ValueNode[phi.valueCount()];
-            for (int i = 0; i < phi.valueCount(); i++) {
-                ValueNode value = states.get(i).getReadCache(phi.valueAt(i), identity, index, PEReadEliminationClosure.this);
+            ValueNode[] values = new ValueNode[states.size()];
+            for (int i = 0; i < states.size(); i++) {
+                ValueNode value = states.get(i).getReadCache(getPhiValueAt(phi, i), identity, index, PEReadEliminationClosure.this);
                 if (value == null) {
                     return;
                 }
@@ -304,7 +303,7 @@
             PhiNode phiNode = getPhi(new ReadCacheEntry(identity, phi, index), values[0].stamp().unrestricted());
             mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
             for (int i = 0; i < values.length; i++) {
-                afterMergeEffects.addPhiInput(phiNode, values[i]);
+                setPhiInput(phiNode, i, values[i]);
             }
             newState.readCache.put(new ReadCacheEntry(identity, phi, index), phiNode);
         }
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeBlockState.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeBlockState.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeBlockState.java	Thu Apr 02 14:55:50 2015 +0200
@@ -53,6 +53,7 @@
     }
 
     protected PartialEscapeBlockState(PartialEscapeBlockState<T> other) {
+        super(other);
         for (Map.Entry<VirtualObjectNode, ObjectState> entry : other.objectStates.entrySet()) {
             objectStates.put(entry.getKey(), entry.getValue().cloneState());
         }
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Thu Apr 02 14:55:50 2015 +0200
@@ -30,6 +30,7 @@
 import com.oracle.graal.compiler.common.util.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.VirtualState.NodeClosure;
 import com.oracle.graal.nodes.cfg.*;
@@ -51,7 +52,7 @@
 
     public static final DebugMetric METRIC_MEMORYCHECKPOINT = Debug.metric("MemoryCheckpoint");
 
-    private final NodeBitMap usages;
+    private final NodeBitMap hasVirtualInputs;
     private final VirtualizerToolImpl tool;
 
     private final class CollectVirtualObjectsClosure extends NodeClosure<ValueNode> {
@@ -109,7 +110,7 @@
 
     public PartialEscapeClosure(SchedulePhase schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection) {
         super(schedule, schedule.getCFG());
-        this.usages = schedule.getCFG().graph.createNodeBitMap();
+        this.hasVirtualInputs = schedule.getCFG().graph.createNodeBitMap();
         this.tool = new VirtualizerToolImpl(metaAccess, constantReflection, this);
     }
 
@@ -118,43 +119,157 @@
      */
     @Override
     protected boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
-        boolean isMarked = usages.isMarked(node);
-        if ((isMarked && node instanceof ValueNode) || node instanceof VirtualizableAllocation) {
-            VirtualUtil.trace("[[%s]] ", node);
-            FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next();
-            return processNode((ValueNode) node, nextFixedNode, state, effects, isMarked);
-        } else {
-            VirtualUtil.trace("%s ", node);
+        /*
+         * These checks make up for the fact that an earliest schedule moves CallTargetNodes upwards
+         * and thus materializes virtual objects needlessly. Also, FrameStates and ConstantNodes are
+         * scheduled, but can safely be ignored.
+         */
+        if (node instanceof CallTargetNode || node instanceof FrameState || node instanceof ConstantNode) {
             return false;
+        } else if (node instanceof Invoke) {
+            processNodeInternal(((Invoke) node).callTarget(), state, effects, lastFixedNode);
         }
+        return processNodeInternal(node, state, effects, lastFixedNode);
+    }
+
+    private boolean processNodeInternal(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
+        FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next();
+        boolean significantChange = false;
+        VirtualUtil.trace("%s", node);
+
+        if (node instanceof VirtualizableAllocation) {
+            significantChange |= processVirtualizable((ValueNode) node, nextFixedNode, state, effects);
+            if (tool.isDeleted()) {
+                VirtualUtil.trace("deleted virtualizable allocation %s", node);
+                return significantChange;
+            }
+        }
+
+        if (hasVirtualInputs.isMarked(node) && node instanceof ValueNode) {
+            if (node instanceof Virtualizable) {
+                significantChange |= processVirtualizable((ValueNode) node, nextFixedNode, state, effects);
+                if (tool.isDeleted()) {
+                    VirtualUtil.trace("deleted virtualizable node %s", node);
+                    return significantChange;
+                }
+            }
+            processNodeInputs((ValueNode) node, nextFixedNode, state, effects);
+        }
+
+        if (hasScalarReplacedInputs(node) && node instanceof ValueNode) {
+            significantChange |= processNodeWithScalarReplacedInputs((ValueNode) node, nextFixedNode, state, effects);
+        }
+        return significantChange;
     }
 
-    private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockT state, final GraphEffectList effects, boolean isMarked) {
-        tool.reset(state, node, insertBefore, effects);
-        if (node instanceof Virtualizable) {
-            ((Virtualizable) node).virtualize(tool);
-        }
-        if (tool.isDeleted()) {
-            return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode);
+    private boolean processNodeWithScalarReplacedInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
+        ValueNode canonicalizedValue = node;
+        if (node instanceof Canonicalizable.Unary<?>) {
+            @SuppressWarnings("unchecked")
+            Canonicalizable.Unary<ValueNode> canonicalizable = (Canonicalizable.Unary<ValueNode>) node;
+            ObjectState valueObj = getObjectState(state, canonicalizable.getValue());
+            ValueNode valueAlias = valueObj != null ? valueObj.getMaterializedValue() : getScalarAlias(canonicalizable.getValue());
+            if (valueAlias != canonicalizable.getValue()) {
+                canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, valueAlias);
+            }
+        } else if (node instanceof Canonicalizable.Binary<?>) {
+            @SuppressWarnings("unchecked")
+            Canonicalizable.Binary<ValueNode> canonicalizable = (Canonicalizable.Binary<ValueNode>) node;
+            ObjectState xObj = getObjectState(state, canonicalizable.getX());
+            ValueNode xAlias = xObj != null ? xObj.getMaterializedValue() : getScalarAlias(canonicalizable.getX());
+            ObjectState yObj = getObjectState(state, canonicalizable.getY());
+            ValueNode yAlias = yObj != null ? yObj.getMaterializedValue() : getScalarAlias(canonicalizable.getY());
+            if (xAlias != canonicalizable.getX() || yAlias != canonicalizable.getY()) {
+                canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, xAlias, yAlias);
+            }
+        } else {
+            return false;
         }
-        if (isMarked) {
-            for (Node input : node.inputs()) {
-                if (input instanceof ValueNode) {
-                    ObjectState obj = getObjectState(state, (ValueNode) input);
-                    if (obj != null) {
-                        VirtualUtil.trace("replacing input %s at %s: %s", input, node, obj);
-                        replaceWithMaterialized(input, node, insertBefore, state, obj, effects, METRIC_MATERIALIZATIONS_UNHANDLED);
+        if (canonicalizedValue != node && canonicalizedValue != null) {
+            if (canonicalizedValue.isAlive()) {
+                ObjectState obj = getObjectState(state, canonicalizedValue);
+                if (obj != null) {
+                    if (obj.getState() == EscapeState.Virtual) {
+                        addAndMarkAlias(obj.virtual, node);
+                        effects.deleteNode(node);
+                    } else {
+                        effects.replaceAtUsages(node, obj.getMaterializedValue());
+                        addScalarAlias(node, obj.getMaterializedValue());
                     }
+                } else {
+                    ValueNode alias = getScalarAlias(canonicalizedValue);
+                    effects.replaceAtUsages(node, alias);
+                    addScalarAlias(node, alias);
                 }
+            } else {
+                if (!prepareCanonicalNode(canonicalizedValue, state, effects)) {
+                    VirtualUtil.trace("replacement via canonicalization too complex: %s -> %s", node, canonicalizedValue);
+                    return false;
+                }
+                effects.ensureAdded(canonicalizedValue, insertBefore);
+                effects.replaceAtUsages(node, canonicalizedValue);
+                addScalarAlias(node, canonicalizedValue);
             }
-            if (node instanceof NodeWithState) {
-                processNodeWithState((NodeWithState) node, state, effects);
-            }
+            VirtualUtil.trace("replaced via canonicalization: %s -> %s", node, canonicalizedValue);
+            return true;
         }
         return false;
     }
 
-    private void processNodeWithState(NodeWithState nodeWithState, final BlockT state, final GraphEffectList effects) {
+    private boolean prepareCanonicalNode(ValueNode node, BlockT state, GraphEffectList effects) {
+        assert !node.isAlive();
+        NodePosIterator iter = node.inputs().iterator();
+        while (iter.hasNext()) {
+            Position pos = iter.nextPosition();
+            Node input = pos.get(node);
+            if (input instanceof ValueNode) {
+                if (input.isAlive()) {
+                    ObjectState obj = getObjectState(state, (ValueNode) input);
+                    if (obj != null) {
+                        if (obj.getState() == EscapeState.Virtual) {
+                            return false;
+                        } else {
+                            pos.initialize(node, obj.getMaterializedValue());
+                        }
+                    } else {
+                        pos.initialize(node, getScalarAlias((ValueNode) input));
+                    }
+                } else {
+                    if (!prepareCanonicalNode((ValueNode) input, state, effects)) {
+                        return false;
+                    }
+                }
+            }
+        }
+        return true;
+    }
+
+    private void processNodeInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
+        VirtualUtil.trace("processing nodewithstate: %s", node);
+        for (Node input : node.inputs()) {
+            if (input instanceof ValueNode) {
+                ObjectState obj = getObjectState(state, (ValueNode) input);
+                if (obj != null) {
+                    VirtualUtil.trace("replacing input %s at %s: %s", input, node, obj);
+                    replaceWithMaterialized(input, node, insertBefore, state, obj, effects, METRIC_MATERIALIZATIONS_UNHANDLED);
+                }
+            }
+        }
+        if (node instanceof NodeWithState) {
+            processNodeWithState((NodeWithState) node, state, effects);
+        }
+    }
+
+    private boolean processVirtualizable(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
+        tool.reset(state, node, insertBefore, effects);
+        ((Virtualizable) node).virtualize(tool);
+        if (tool.isDeleted()) {
+            return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode);
+        }
+        return false;
+    }
+
+    private void processNodeWithState(NodeWithState nodeWithState, BlockT state, GraphEffectList effects) {
         for (FrameState fs : nodeWithState.states()) {
             FrameState frameState = getUniqueFramestate(nodeWithState, fs);
             Set<ObjectState> virtual = new ArraySet<>();
@@ -317,7 +432,7 @@
             if (needsCaching) {
                 return getPhiCached(virtual, stamp);
             } else {
-                return new ValuePhiNode(stamp, merge);
+                return createValuePhi(stamp);
             }
         }
 
@@ -327,7 +442,7 @@
             }
             ValuePhiNode result = materializedPhis.get(virtual);
             if (result == null) {
-                result = new ValuePhiNode(stamp, merge);
+                result = createValuePhi(stamp);
                 materializedPhis.put(virtual, result);
             }
             return result;
@@ -425,18 +540,18 @@
                             for (int i = 0; i < objStates.length; i++) {
                                 ObjectState obj = objStates[i];
                                 if (obj.isVirtual()) {
-                                    Block predecessor = mergeBlock.getPredecessors().get(i);
+                                    Block predecessor = getPredecessor(i);
                                     materialized |= ensureMaterialized(states.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE);
                                 }
-                                afterMergeEffects.addPhiInput(materializedValuePhi, obj.getMaterializedValue());
+                                setPhiInput(materializedValuePhi, i, obj.getMaterializedValue());
                             }
                             newState.addObject(object, new ObjectState(object, materializedValuePhi, EscapeState.Materialized, null));
                         }
                     }
                 }
 
-                for (PhiNode phi : merge.phis()) {
-                    if (usages.isMarked(phi) && phi instanceof ValuePhiNode) {
+                for (PhiNode phi : getPhis()) {
+                    if (hasVirtualInputs.isMarked(phi) && phi instanceof ValuePhiNode) {
                         materialized |= processPhi((ValuePhiNode) phi, states, virtualObjTemp);
                     }
                 }
@@ -511,8 +626,8 @@
                                 ValueNode nextValue = objStates[i].getEntry(valueIndex + 1);
                                 if (value.isConstant() && value.asConstant().equals(JavaConstant.INT_0) && nextValue.isConstant() && nextValue.asConstant().equals(JavaConstant.INT_0)) {
                                     // rewrite to a zero constant of the larger kind
-                                    objStates[i].setEntry(valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], merge.graph()));
-                                    objStates[i].setEntry(valueIndex + 1, ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), merge.graph()));
+                                    objStates[i].setEntry(valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], graph()));
+                                    objStates[i].setEntry(valueIndex + 1, ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), graph()));
                                 } else {
                                     compatible = false;
                                     break outer;
@@ -529,19 +644,21 @@
                 int valueIndex = 0;
                 while (valueIndex < values.length) {
                     for (int i = 1; i < objStates.length; i++) {
-                        ValueNode field = objStates[i].getEntry(valueIndex);
-                        if (phis[valueIndex] == null && values[valueIndex] != field) {
-                            phis[valueIndex] = new ValuePhiNode(values[valueIndex].stamp().unrestricted(), merge);
+                        if (phis[valueIndex] == null) {
+                            ValueNode field = objStates[i].getEntry(valueIndex);
+                            if (values[valueIndex] != field) {
+                                phis[valueIndex] = createValuePhi(values[valueIndex].stamp().unrestricted());
+                            }
                         }
                     }
                     if (phis[valueIndex] != null && !phis[valueIndex].stamp().isCompatible(values[valueIndex].stamp())) {
-                        phis[valueIndex] = new ValuePhiNode(values[valueIndex].stamp().unrestricted(), merge);
+                        phis[valueIndex] = createValuePhi(values[valueIndex].stamp().unrestricted());
                     }
                     if (twoSlotKinds != null && twoSlotKinds[valueIndex] != null) {
                         // skip an entry after a long/double value that occupies two int slots
                         valueIndex++;
                         phis[valueIndex] = null;
-                        values[valueIndex] = ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), merge.graph());
+                        values[valueIndex] = ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), graph());
                     }
                     valueIndex++;
                 }
@@ -566,9 +683,9 @@
                 PhiNode materializedValuePhi = getPhi(object, StampFactory.forKind(Kind.Object));
                 for (int i = 0; i < blockStates.size(); i++) {
                     ObjectState obj = objStates[i];
-                    Block predecessor = mergeBlock.getPredecessors().get(i);
+                    Block predecessor = getPredecessor(i);
                     ensureMaterialized(blockStates.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE);
-                    afterMergeEffects.addPhiInput(materializedValuePhi, obj.getMaterializedValue());
+                    setPhiInput(materializedValuePhi, i, obj.getMaterializedValue());
                 }
                 newState.addObject(object, new ObjectState(object, materializedValuePhi, EscapeState.Materialized, null));
                 return true;
@@ -590,13 +707,13 @@
                 ValueNode entry = objStates[i].getEntry(entryIndex);
                 if (entry instanceof VirtualObjectNode) {
                     ObjectState obj = blockStates.get(i).getObjectState((VirtualObjectNode) entry);
-                    Block predecessor = mergeBlock.getPredecessors().get(i);
+                    Block predecessor = getPredecessor(i);
                     materialized |= ensureMaterialized(blockStates.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE);
                     if (objStates[i].isVirtual()) {
                         objStates[i].setEntry(entryIndex, entry = obj.getMaterializedValue());
                     }
                 }
-                afterMergeEffects.addPhiInput(phi, entry);
+                setPhiInput(phi, i, entry);
             }
             return materialized;
         }
@@ -606,11 +723,12 @@
          * object.
          */
         private void mergePrimitiveEntry(ObjectState[] objStates, PhiNode phi, int entryIndex) {
-            for (ObjectState state : objStates) {
+            for (int i = 0; i < objStates.length; i++) {
+                ObjectState state = objStates[i];
                 if (!state.isVirtual()) {
                     break;
                 }
-                afterMergeEffects.addPhiInput(phi, state.getEntry(entryIndex));
+                setPhiInput(phi, i, state.getEntry(entryIndex));
             }
         }
 
@@ -628,14 +746,13 @@
          */
         private boolean processPhi(ValuePhiNode phi, List<BlockT> states, Set<VirtualObjectNode> mergedVirtualObjects) {
             aliases.set(phi, null);
-            assert states.size() == phi.valueCount();
 
             // determine how many inputs are virtual and if they're all the same virtual object
             int virtualInputs = 0;
             ObjectState[] objStates = new ObjectState[states.size()];
             boolean uniqueVirtualObject = true;
             for (int i = 0; i < objStates.length; i++) {
-                ObjectState obj = objStates[i] = getObjectState(states.get(i), phi.valueAt(i));
+                ObjectState obj = objStates[i] = getObjectState(states.get(i), getPhiValueAt(phi, i));
                 if (obj != null) {
                     if (obj.isVirtual()) {
                         if (objStates[0] == null || objStates[0].virtual != obj.virtual) {
@@ -667,9 +784,9 @@
                     }
                     if (compatible && hasIdentity) {
                         // we still need to check whether this value is referenced by any other phi
-                        outer: for (PhiNode otherPhi : merge.phis().filter(otherPhi -> otherPhi != phi)) {
+                        outer: for (PhiNode otherPhi : getPhis().filter(otherPhi -> otherPhi != phi)) {
                             for (int i = 0; i < objStates.length; i++) {
-                                ObjectState otherPhiValueState = getObjectState(states.get(i), otherPhi.valueAt(i));
+                                ObjectState otherPhiValueState = getObjectState(states.get(i), getPhiValueAt(otherPhi, i));
                                 if (Arrays.asList(objStates).contains(otherPhiValueState)) {
                                     compatible = false;
                                     break outer;
@@ -679,7 +796,7 @@
                     }
 
                     if (compatible) {
-                        VirtualObjectNode virtual = getValueObjectVirtual(phi, getObjectState(states.get(0), phi.valueAt(0)).virtual);
+                        VirtualObjectNode virtual = getValueObjectVirtual(phi, getObjectState(states.get(0), getPhiValueAt(phi, 0)).virtual);
                         mergeEffects.addFloatingNode(virtual, "valueObjectNode");
                         mergeEffects.deleteNode(phi);
 
@@ -696,9 +813,9 @@
             for (int i = 0; i < objStates.length; i++) {
                 ObjectState obj = objStates[i];
                 if (obj != null) {
-                    Block predecessor = mergeBlock.getPredecessors().get(i);
+                    Block predecessor = getPredecessor(i);
                     materialized |= ensureMaterialized(states.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_PHI);
-                    afterMergeEffects.initializePhiInput(phi, i, obj.getMaterializedValue());
+                    setPhiInput(phi, i, obj.getMaterializedValue());
                 }
             }
             return materialized;
@@ -730,12 +847,12 @@
     }
 
     private void markVirtualUsages(Node node) {
-        if (!usages.isNew(node)) {
-            usages.mark(node);
-        }
-        if (node instanceof VirtualState) {
-            for (Node usage : node.usages()) {
-                markVirtualUsages(usage);
+        if (!hasVirtualInputs.isNew(node) && !hasVirtualInputs.isMarked(node)) {
+            hasVirtualInputs.mark(node);
+            if (node instanceof VirtualState) {
+                for (Node usage : node.usages()) {
+                    markVirtualUsages(usage);
+                }
             }
         }
     }
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationClosure.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationClosure.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationClosure.java	Thu Apr 02 14:55:50 2015 +0200
@@ -203,7 +203,7 @@
         protected <T> PhiNode getCachedPhi(T virtual, Stamp stamp) {
             ValuePhiNode result = materializedPhis.get(virtual);
             if (result == null) {
-                result = new ValuePhiNode(stamp, merge);
+                result = createValuePhi(stamp);
                 materializedPhis.put(virtual, result);
             }
             return result;
@@ -236,17 +236,17 @@
                     PhiNode phiNode = getCachedPhi(entry, value.stamp().unrestricted());
                     mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
                     for (int i = 0; i < states.size(); i++) {
-                        afterMergeEffects.addPhiInput(phiNode, states.get(i).getCacheEntry(key));
+                        setPhiInput(phiNode, i, states.get(i).getCacheEntry(key));
                     }
                     newState.addCacheEntry(key, phiNode);
                 } else if (value != null) {
                     newState.addCacheEntry(key, value);
                 }
             }
-            for (PhiNode phi : merge.phis()) {
+            for (PhiNode phi : getPhis()) {
                 if (phi.getKind() == Kind.Object) {
                     for (Map.Entry<CacheEntry<?>, ValueNode> entry : states.get(0).readCache.entrySet()) {
-                        if (entry.getKey().object == phi.valueAt(0)) {
+                        if (entry.getKey().object == getPhiValueAt(phi, 0)) {
                             mergeReadCachePhi(phi, entry.getKey(), states);
                         }
                     }
@@ -256,9 +256,9 @@
         }
 
         private void mergeReadCachePhi(PhiNode phi, CacheEntry<?> identifier, List<ReadEliminationBlockState> states) {
-            ValueNode[] values = new ValueNode[phi.valueCount()];
-            for (int i = 0; i < phi.valueCount(); i++) {
-                ValueNode value = states.get(i).getCacheEntry(identifier.duplicateWithObject(phi.valueAt(i)));
+            ValueNode[] values = new ValueNode[states.size()];
+            for (int i = 0; i < states.size(); i++) {
+                ValueNode value = states.get(i).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, i)));
                 if (value == null) {
                     return;
                 }
@@ -269,7 +269,7 @@
             PhiNode phiNode = getCachedPhi(newIdentifier, values[0].stamp().unrestricted());
             mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
             for (int i = 0; i < values.length; i++) {
-                afterMergeEffects.addPhiInput(phiNode, values[i]);
+                setPhiInput(phiNode, i, values[i]);
             }
             newState.addCacheEntry(newIdentifier, phiNode);
         }
diff -r 33be8eb8cbd5 -r 8ff9e165002b graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java	Thu Apr 02 14:50:16 2015 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java	Thu Apr 02 14:55:50 2015 +0200
@@ -28,6 +28,7 @@
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.java.*;
@@ -36,7 +37,7 @@
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.virtual.*;
 
-class VirtualizerToolImpl implements VirtualizerTool {
+class VirtualizerToolImpl implements VirtualizerTool, CanonicalizerTool {
 
     private final MetaAccessProvider metaAccess;
     private final ConstantReflectionProvider constantReflection;
@@ -187,4 +188,16 @@
             }
         }
     }
+
+    public MetaAccessProvider getMetaAccess() {
+        return metaAccess;
+    }
+
+    public ConstantReflectionProvider getConstantReflection() {
+        return constantReflection;
+    }
+
+    public boolean canonicalizeReads() {
+        return false;
+    }
 }