# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1365441272 -7200
# Node ID fc972f34c1d5b8ca37c33b2fdd436d3ebafcfab2
# Parent  a8260ba9c7624a7c58959645248b7c5574ad6e69
PEA: unify merge and loop logic, implement handling of identity-less virtual objects

diff -r a8260ba9c762 -r fc972f34c1d5 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectNode.java	Mon Apr 08 19:12:19 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectNode.java	Mon Apr 08 19:14:32 2013 +0200
@@ -55,4 +55,8 @@
     public abstract Kind entryKind(int index);
 
     public abstract VirtualObjectNode duplicate();
+
+    public boolean hasIdentity() {
+        return true;
+    }
 }
diff -r a8260ba9c762 -r fc972f34c1d5 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Mon Apr 08 19:12:19 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Mon Apr 08 19:14:32 2013 +0200
@@ -40,7 +40,7 @@
     private final IdentityHashMap<VirtualObjectNode, ObjectState> objectStates = new IdentityHashMap<>();
     private final IdentityHashMap<ValueNode, VirtualObjectNode> objectAliases;
     private final IdentityHashMap<ValueNode, ValueNode> scalarAliases;
-    private final HashMap<ReadCacheEntry, ValueNode> readCache;
+    final HashMap<ReadCacheEntry, ValueNode> readCache;
 
     static class ReadCacheEntry {
 
@@ -167,8 +167,6 @@
 
         ValueNode[] fieldState = obj.getEntries();
 
-        // some entries are not default constants - do the materialization
-        virtual.materializeAt(fixed);
         MaterializeObjectNode materialize = new MaterializeObjectNode(virtual, obj.getLockCount());
         ValueNode[] values = new ValueNode[obj.getEntries().length];
         materialize.setProbability(fixed.probability());
@@ -249,70 +247,13 @@
         return objectStates.values();
     }
 
-    public Iterable<VirtualObjectNode> getVirtualObjects() {
+    public Collection<VirtualObjectNode> getVirtualObjects() {
         return objectAliases.values();
     }
 
     @Override
     public String toString() {
-        return objectStates.toString();
-    }
-
-    public void mergeReadCache(List<BlockState> states, MergeNode merge, GraphEffectList effects) {
-        for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
-            ReadCacheEntry key = entry.getKey();
-            ValueNode value = entry.getValue();
-            boolean phi = false;
-            for (int i = 1; i < states.size(); i++) {
-                ValueNode otherValue = states.get(i).readCache.get(key);
-                if (otherValue == null) {
-                    value = null;
-                    phi = false;
-                    break;
-                }
-                if (!phi && otherValue != value) {
-                    phi = true;
-                }
-            }
-            if (phi) {
-                PhiNode phiNode = new PhiNode(value.kind(), merge);
-                effects.addFloatingNode(phiNode);
-                for (int i = 0; i < states.size(); i++) {
-                    effects.addPhiInput(phiNode, states.get(i).getReadCache(key.object, key.identity));
-                }
-                readCache.put(key, phiNode);
-            } else if (value != null) {
-                readCache.put(key, value);
-            }
-        }
-        for (PhiNode phi : merge.phis()) {
-            if (phi.kind() == Kind.Object) {
-                for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
-                    if (entry.getKey().object == phi.valueAt(0)) {
-                        mergeReadCachePhi(phi, entry.getKey().identity, states, merge, effects);
-                    }
-                }
-
-            }
-        }
-    }
-
-    private void mergeReadCachePhi(PhiNode phi, Object identity, List<BlockState> states, MergeNode merge, GraphEffectList effects) {
-        ValueNode[] values = new ValueNode[phi.valueCount()];
-        for (int i = 0; i < phi.valueCount(); i++) {
-            ValueNode value = states.get(i).getReadCache(phi.valueAt(i), identity);
-            if (value == null) {
-                return;
-            }
-            values[i] = value;
-        }
-
-        PhiNode phiNode = new PhiNode(values[0].kind(), merge);
-        effects.addFloatingNode(phiNode);
-        for (int i = 0; i < values.length; i++) {
-            effects.addPhiInput(phiNode, values[i]);
-        }
-        readCache.put(new ReadCacheEntry(identity, phi), phiNode);
+        return objectStates + " " + readCache;
     }
 
     public static BlockState meetAliases(List<BlockState> states) {
@@ -349,4 +290,38 @@
         return readCache;
     }
 
+    public boolean equivalentTo(BlockState other) {
+        if (this == other) {
+            return true;
+        }
+        boolean objectAliasesEqual = compareMaps(objectAliases, other.objectAliases);
+        boolean objectStatesEqual = compareMaps(objectStates, other.objectStates);
+        boolean readCacheEqual = compareMapsNoSize(readCache, other.readCache);
+        boolean scalarAliasesEqual = scalarAliases.equals(other.scalarAliases);
+        return objectAliasesEqual && objectStatesEqual && readCacheEqual && scalarAliasesEqual;
+    }
+
+    private static <K, V> boolean compareMaps(Map<K, V> left, Map<K, V> right) {
+        if (left.size() != right.size()) {
+            return false;
+        }
+        return compareMapsNoSize(left, right);
+    }
+
+    private static <K, V> boolean compareMapsNoSize(Map<K, V> left, Map<K, V> right) {
+        if (left == right) {
+            return true;
+        }
+        for (Map.Entry<K, V> entry : right.entrySet()) {
+            K key = entry.getKey();
+            V value = entry.getValue();
+            assert value != null;
+            V otherValue = left.get(key);
+            if (otherValue != value && !value.equals(otherValue)) {
+                return false;
+            }
+        }
+        return true;
+    }
+
 }
diff -r a8260ba9c762 -r fc972f34c1d5 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	Mon Apr 08 19:12:19 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Mon Apr 08 19:14:32 2013 +0200
@@ -104,17 +104,17 @@
      * 
      * @param node The floating node to be added.
      */
-    public void addFloatingNode(final ValueNode node) {
+    public void addFloatingNode(final ValueNode node, final String cause) {
         add(new Effect() {
 
             @Override
             public String name() {
-                return "addFloatingNode";
+                return "addFloatingNode " + cause;
             }
 
             @Override
             public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
-                assert !node.isAlive() && !node.isDeleted();
+                assert !node.isAlive() && !node.isDeleted() : node + " " + cause;
                 graph.add(node);
             }
         });
@@ -164,7 +164,7 @@
 
             @Override
             public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
-                assert node.isAlive() && value.isAlive();
+                assert node.isAlive() && value.isAlive() : node + " " + value;
                 node.addInput(value);
             }
         });
diff -r a8260ba9c762 -r fc972f34c1d5 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java	Mon Apr 08 19:12:19 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java	Mon Apr 08 19:14:32 2013 +0200
@@ -22,6 +22,8 @@
  */
 package com.oracle.graal.virtual.phases.ea;
 
+import java.util.*;
+
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.spi.Virtualizable.EscapeState;
@@ -144,4 +146,48 @@
 
         return str.append('}').toString();
     }
+
+    @Override
+    public int hashCode() {
+        final int prime = 31;
+        int result = 1;
+        result = prime * result + Arrays.hashCode(entries);
+        result = prime * result + lockCount;
+        result = prime * result + ((materializedValue == null) ? 0 : materializedValue.hashCode());
+        result = prime * result + ((state == null) ? 0 : state.hashCode());
+        result = prime * result + ((virtual == null) ? 0 : virtual.hashCode());
+        return result;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if (obj == null || getClass() != obj.getClass()) {
+            return false;
+        }
+        ObjectState other = (ObjectState) obj;
+        if (!Arrays.equals(entries, other.entries)) {
+            return false;
+        }
+        if (lockCount != other.lockCount) {
+            return false;
+        }
+        if (materializedValue == null) {
+            if (other.materializedValue != null) {
+                return false;
+            }
+        } else if (!materializedValue.equals(other.materializedValue)) {
+            return false;
+        }
+        if (state != other.state) {
+            return false;
+        }
+        assert virtual != null && other.virtual != null;
+        if (!virtual.equals(other.virtual)) {
+            return false;
+        }
+        return true;
+    }
 }
diff -r a8260ba9c762 -r fc972f34c1d5 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Mon Apr 08 19:12:19 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Mon Apr 08 19:14:32 2013 +0200
@@ -39,7 +39,6 @@
 import com.oracle.graal.phases.graph.*;
 import com.oracle.graal.phases.schedule.*;
 import com.oracle.graal.virtual.nodes.*;
-import com.oracle.graal.virtual.phases.ea.EffectList.Effect;
 
 public class PartialEscapeAnalysisPhase extends Phase {
 
@@ -109,11 +108,7 @@
                     changed = true;
 
                     // apply the effects collected during the escape analysis iteration
-                    ArrayList<Node> obsoleteNodes = new ArrayList<>();
-                    for (Effect effect : closure.getEffects()) {
-                        effect.apply(graph, obsoleteNodes);
-                    }
-                    trace("%s\n", closure.getEffects());
+                    List<Node> obsoleteNodes = closure.applyEffects(graph);
 
                     Debug.dump(graph, "after PartialEscapeAnalysis iteration");
                     assert noObsoleteNodes(graph, obsoleteNodes);
@@ -146,7 +141,7 @@
         return true;
     }
 
-    static boolean noObsoleteNodes(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
+    static boolean noObsoleteNodes(StructuredGraph graph, List<Node> obsoleteNodes) {
         // helper code that determines the paths that keep obsolete nodes alive:
 
         NodeFlood flood = graph.createNodeFlood();
diff -r a8260ba9c762 -r fc972f34c1d5 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	Mon Apr 08 19:12:19 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Mon Apr 08 19:14:32 2013 +0200
@@ -24,6 +24,7 @@
 
 import static com.oracle.graal.virtual.phases.ea.PartialEscapeAnalysisPhase.*;
 
+import java.io.*;
 import java.util.*;
 
 import com.oracle.graal.api.code.*;
@@ -46,6 +47,7 @@
 import com.oracle.graal.phases.schedule.*;
 import com.oracle.graal.virtual.nodes.*;
 import com.oracle.graal.virtual.phases.ea.BlockState.ReadCacheEntry;
+import com.oracle.graal.virtual.phases.ea.EffectList.*;
 
 class PartialEscapeClosure extends BlockIteratorClosure<BlockState> {
 
@@ -65,7 +67,8 @@
     private final NodeBitMap usages;
     private final SchedulePhase schedule;
 
-    private final GraphEffectList effects = new GraphEffectList();
+    private final BlockMap<GraphEffectList> blockEffects;
+    private final IdentityHashMap<Loop, GraphEffectList> loopMergeEffects = new IdentityHashMap<>();
 
     private final VirtualizerToolImpl tool;
 
@@ -76,19 +79,61 @@
     public PartialEscapeClosure(NodeBitMap usages, SchedulePhase schedule, MetaAccessProvider metaAccess, Assumptions assumptions) {
         this.usages = usages;
         this.schedule = schedule;
-        tool = new VirtualizerToolImpl(effects, usages, metaAccess, assumptions);
+        this.tool = new VirtualizerToolImpl(usages, metaAccess, assumptions);
+        this.blockEffects = new BlockMap<>(schedule.getCFG());
+        for (Block block : schedule.getCFG().getBlocks()) {
+            blockEffects.put(block, new GraphEffectList());
+        }
     }
 
     public boolean hasChanged() {
         return changed;
     }
 
-    public GraphEffectList getEffects() {
-        return effects;
+    private static void trace2(String format, Object... args) {
+        Debug.log(format, args);
     }
 
-    public int getNewVirtualObjectCount() {
-        return tool.getNewVirtualObjectCount();
+    public List<Node> applyEffects(final StructuredGraph graph) {
+        final ArrayList<Node> obsoleteNodes = new ArrayList<>();
+        BlockIteratorClosure<Object> closure = new BlockIteratorClosure<Object>() {
+
+            private void apply(GraphEffectList effects, Object context) {
+                if (!effects.isEmpty()) {
+                    trace2(" ==== effects for %s", context);
+                    for (Effect effect : effects) {
+                        effect.apply(graph, obsoleteNodes);
+                        if (effect.isVisible()) {
+                            trace2("    %s", effect);
+                        }
+                    }
+                }
+            }
+
+            @Override
+            protected void processBlock(Block block, Object currentState) {
+                apply(blockEffects.get(block), block);
+            }
+
+            @Override
+            protected Object merge(Block merge, List<Object> states) {
+                return new Object();
+            }
+
+            @Override
+            protected Object cloneState(Object oldState) {
+                return oldState;
+            }
+
+            @Override
+            protected List<Object> processLoop(Loop loop, Object initialState) {
+                LoopInfo<Object> info = ReentrantBlockIterator.processLoop(this, loop, initialState);
+                apply(loopMergeEffects.get(loop), loop);
+                return info.exitStates;
+            }
+        };
+        ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new Object(), null);
+        return obsoleteNodes;
     }
 
     public Map<Invoke, Double> getHints() {
@@ -97,6 +142,9 @@
 
     @Override
     protected void processBlock(Block block, BlockState state) {
+        GraphEffectList effects = blockEffects.get(block);
+        tool.setEffects(effects);
+
         trace("\nBlock: %s (", block);
         List<ScheduledNode> nodeList = schedule.getBlockToNodesMap().get(block);
 
@@ -105,7 +153,7 @@
             boolean deleted;
             if (usages.isMarked(node) || node instanceof VirtualizableAllocation) {
                 trace("[[%s]] ", node);
-                deleted = processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state);
+                deleted = processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state, effects);
             } else {
                 trace("%s ", node);
                 deleted = false;
@@ -154,7 +202,7 @@
         trace(")\n    end state: %s\n", state);
     }
 
-    private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) {
+    private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockState state, final GraphEffectList effects) {
         tool.reset(state, node);
         if (node instanceof Virtualizable) {
             ((Virtualizable) node).virtualize(tool);
@@ -250,13 +298,13 @@
                     hints.put(invoke, 5d);
                 }
                 trace("replacing input %s at %s: %s", input, node, obj);
-                replaceWithMaterialized(input, node, insertBefore, state, obj, METRIC_MATERIALIZATIONS_UNHANDLED);
+                replaceWithMaterialized(input, node, insertBefore, state, obj, effects, METRIC_MATERIALIZATIONS_UNHANDLED);
             }
         }
         return false;
     }
 
-    private void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore, DebugMetric metric) {
+    private static void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore, GraphEffectList effects, DebugMetric metric) {
         assert obj != null;
         if (obj.getState() == EscapeState.Virtual) {
             metric.increment();
@@ -267,178 +315,23 @@
         assert !obj.isVirtual();
     }
 
-    private void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj, DebugMetric metric) {
-        ensureMaterialized(state, obj, materializeBefore, metric);
+    private static void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj, GraphEffectList effects, DebugMetric metric) {
+        ensureMaterialized(state, obj, materializeBefore, effects, metric);
         effects.replaceFirstInput(usage, value, obj.getMaterializedValue());
     }
 
     @Override
-    protected BlockState merge(MergeNode merge, List<BlockState> states) {
-        BlockState newState = BlockState.meetAliases(states);
-
-        // Iterative processing:
-        // Merging the materialized/virtual state of virtual objects can lead to new
-        // materializations, which can
-        // lead to new materializations because of phis, and so on.
-
-        boolean materialized;
-        do {
-            materialized = false;
-            // use a hash set to make the values distinct...
-            for (VirtualObjectNode object : newState.getVirtualObjects()) {
-                ObjectState resultState = newState.getObjectStateOptional(object);
-                if (resultState == null || resultState.isVirtual()) {
-                    int virtual = 0;
-                    ObjectState startObj = states.get(0).getObjectState(object);
-                    int lockCount = startObj.getLockCount();
-                    boolean locksMatch = true;
-                    ValueNode singleValue = startObj.isVirtual() ? null : startObj.getMaterializedValue();
-                    for (BlockState state : states) {
-                        ObjectState obj = state.getObjectState(object);
-                        if (obj.isVirtual()) {
-                            virtual++;
-                            singleValue = null;
-                        } else {
-                            if (obj.getMaterializedValue() != singleValue) {
-                                singleValue = null;
-                            }
-                        }
-                        locksMatch &= obj.getLockCount() == lockCount;
-                    }
-
-                    assert virtual < states.size() || locksMatch : "mismatching lock counts at " + merge;
+    protected BlockState merge(Block merge, List<BlockState> states) {
+        assert blockEffects.get(merge).isEmpty();
+        MergeProcessor processor = new MergeProcessor(merge, usages, blockEffects);
+        processor.merge(states);
+        blockEffects.get(merge).addAll(processor.mergeEffects);
+        blockEffects.get(merge).addAll(processor.afterMergeEffects);
+        return processor.newState;
 
-                    if (virtual < states.size()) {
-                        if (singleValue == null) {
-                            PhiNode materializedValuePhi = new PhiNode(Kind.Object, merge);
-                            effects.addFloatingNode(materializedValuePhi);
-                            for (int i = 0; i < states.size(); i++) {
-                                BlockState state = states.get(i);
-                                ObjectState obj = state.getObjectState(object);
-                                materialized |= obj.isVirtual();
-                                ensureMaterialized(state, obj, merge.forwardEndAt(i), METRIC_MATERIALIZATIONS_MERGE);
-                                effects.addPhiInput(materializedValuePhi, obj.getMaterializedValue());
-                            }
-                            newState.addObject(object, new ObjectState(object, materializedValuePhi, EscapeState.Global, lockCount));
-                        } else {
-                            newState.addObject(object, new ObjectState(object, singleValue, EscapeState.Global, lockCount));
-                        }
-                    } else {
-                        assert virtual == states.size();
-                        ValueNode[] values = startObj.getEntries().clone();
-                        PhiNode[] phis = new PhiNode[values.length];
-                        int mismatch = 0;
-                        for (int i = 1; i < states.size(); i++) {
-                            BlockState state = states.get(i);
-                            ValueNode[] fields = state.getObjectState(object).getEntries();
-                            for (int index = 0; index < values.length; index++) {
-                                if (phis[index] == null && values[index] != fields[index]) {
-                                    mismatch++;
-                                    phis[index] = new PhiNode(values[index].kind(), merge);
-                                    effects.addFloatingNode(phis[index]);
-                                }
-                            }
-                        }
-                        if (mismatch > 0) {
-                            for (int i = 0; i < states.size(); i++) {
-                                BlockState state = states.get(i);
-                                ValueNode[] fields = state.getObjectState(object).getEntries();
-                                for (int index = 0; index < values.length; index++) {
-                                    if (phis[index] != null) {
-                                        ObjectState obj = state.getObjectState(fields[index]);
-                                        if (obj != null) {
-                                            materialized |= obj.isVirtual();
-                                            ensureMaterialized(state, obj, merge.forwardEndAt(i), METRIC_MATERIALIZATIONS_MERGE);
-                                            fields[index] = obj.getMaterializedValue();
-                                        }
-                                        effects.addPhiInput(phis[index], fields[index]);
-                                    }
-                                }
-                            }
-                            for (int index = 0; index < values.length; index++) {
-                                if (phis[index] != null) {
-                                    values[index] = phis[index];
-                                }
-                            }
-                        }
-                        newState.addObject(object, new ObjectState(object, values, EscapeState.Virtual, lockCount));
-                    }
-                }
-            }
-
-            for (PhiNode phi : merge.phis()) {
-                if (usages.isMarked(phi) && phi.type() == PhiType.Value) {
-                    materialized |= processPhi(newState, merge, phi, states);
-                }
-            }
-        } while (materialized);
-
-        newState.mergeReadCache(states, merge, effects);
-
-        return newState;
     }
 
-    private boolean processPhi(BlockState newState, MergeNode merge, PhiNode phi, List<BlockState> states) {
-        assert states.size() == phi.valueCount();
-        int virtualInputs = 0;
-        boolean materialized = false;
-        VirtualObjectNode sameObject = null;
-        ResolvedJavaType sameType = null;
-        int sameEntryCount = -1;
-        for (int i = 0; i < phi.valueCount(); i++) {
-            ValueNode value = phi.valueAt(i);
-            ObjectState obj = states.get(i).getObjectState(value);
-            if (obj != null) {
-                if (obj.isVirtual()) {
-                    virtualInputs++;
-                    if (i == 0) {
-                        sameObject = obj.virtual;
-                        sameType = obj.virtual.type();
-                        sameEntryCount = obj.virtual.entryCount();
-                    } else {
-                        if (sameObject != obj.virtual) {
-                            sameObject = null;
-                        }
-                        if (sameType != obj.virtual.type()) {
-                            sameType = null;
-                        }
-                        if (sameEntryCount != obj.virtual.entryCount()) {
-                            sameEntryCount = -1;
-                        }
-                    }
-                } else {
-                    effects.setPhiInput(phi, i, obj.getMaterializedValue());
-                }
-            }
-        }
-        boolean materialize = false;
-        if (virtualInputs == 0) {
-            // nothing to do...
-        } else if (virtualInputs == phi.valueCount()) {
-            if (sameObject != null) {
-                newState.addAndMarkAlias(sameObject, phi, usages);
-            } else if (sameType != null && sameEntryCount != -1) {
-                materialize = true;
-                // throw new GraalInternalError("merge required for %s", sameType);
-            } else {
-                materialize = true;
-            }
-        } else {
-            materialize = true;
-        }
-
-        if (materialize) {
-            for (int i = 0; i < phi.valueCount(); i++) {
-                ValueNode value = phi.valueAt(i);
-                ObjectState obj = states.get(i).getObjectState(value);
-                if (obj != null) {
-                    materialized |= obj.isVirtual();
-                    replaceWithMaterialized(value, phi, merge.forwardEndAt(i), states.get(i), obj, METRIC_MATERIALIZATIONS_PHI);
-                }
-            }
-        }
-        return materialized;
-    }
+    static PrintStream out = System.out;
 
     @Override
     protected BlockState cloneState(BlockState oldState) {
@@ -447,84 +340,45 @@
 
     @Override
     protected List<BlockState> processLoop(Loop loop, BlockState initialState) {
-        GraphEffectList successEffects = new GraphEffectList();
-        HashSet<PhiDesc> phis = new HashSet<>();
+        BlockState loopEntryState = initialState;
+        BlockState lastMergedState = initialState;
+        MergeProcessor mergeProcessor = new MergeProcessor(loop.header, usages, blockEffects);
         for (int iteration = 0; iteration < 10; iteration++) {
-            BlockState state = initialState.cloneState();
-            int checkpoint = effects.checkpoint();
-
-            for (PhiDesc desc : phis) {
-                ObjectState obj = state.getObjectState(desc.virtualObject);
-                if (obj.isVirtual()) {
-                    ValueNode value = obj.getEntry(desc.fieldIndex);
-                    ObjectState valueObj = state.getObjectState(value);
-                    if (valueObj != null) {
-                        assert !valueObj.isVirtual();
-                        value = valueObj.getMaterializedValue();
-                    }
-
-                    PhiNode phiNode = new PhiNode(value.kind(), loop.loopBegin());
-                    effects.addFloatingNode(phiNode);
-                    effects.addPhiInput(phiNode, value);
-                    obj.setEntry(desc.fieldIndex, phiNode);
-                }
-            }
+            LoopInfo<BlockState> info = ReentrantBlockIterator.processLoop(this, loop, lastMergedState.cloneState());
 
-            for (PhiNode phi : loop.loopBegin().phis()) {
-                if (usages.isMarked(phi) && phi.type() == PhiType.Value) {
-                    ObjectState initialObj = initialState.getObjectState(phi.valueAt(0));
-                    if (initialObj != null) {
-                        if (initialObj.isVirtual()) {
-                            state.addAndMarkAlias(initialObj.virtual, phi, usages);
-                        } else {
-                            successEffects.setPhiInput(phi, 0, initialObj.getMaterializedValue());
-                        }
-                    }
-                }
-            }
+            List<BlockState> states = new ArrayList<>();
+            states.add(initialState);
+            states.addAll(info.endStates);
+            mergeProcessor.merge(states);
 
-            effects.incLevel();
-            LoopInfo<BlockState> info = ReentrantBlockIterator.processLoop(this, loop, state.cloneState());
+            Debug.log("================== %s", loop.header);
+            Debug.log("%s", mergeProcessor.newState);
+            Debug.log("===== vs.");
+            Debug.log("%s", lastMergedState);
 
-            HashSet<VirtualObjectNode> additionalMaterializations = new HashSet<>();
-            HashSet<ReadCacheEntry> additionalKilledReads = new HashSet<>();
-            int oldPhiCount = phis.size();
-            processLoopEnds(loop, state, info.endStates, successEffects, additionalMaterializations, additionalKilledReads, phis);
-            if (additionalMaterializations.isEmpty() && additionalKilledReads.isEmpty() && oldPhiCount == phis.size()) {
-                effects.addAll(successEffects);
+            if (mergeProcessor.newState.equivalentTo(lastMergedState)) {
+                blockEffects.get(loop.header).insertAll(mergeProcessor.mergeEffects, 0);
+                loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects);
 
                 assert info.exitStates.size() == loop.exits.size();
                 for (int i = 0; i < loop.exits.size(); i++) {
                     BlockState exitState = info.exitStates.get(i);
                     assert exitState != null : "no loop exit state at " + loop.exits.get(i) + " / " + loop.header;
-                    processLoopExit((LoopExitNode) loop.exits.get(i).getBeginNode(), state, exitState);
+                    processLoopExit((LoopExitNode) loop.exits.get(i).getBeginNode(), loopEntryState, exitState, blockEffects.get(loop.exits.get(i)));
                 }
 
-                effects.decLevel();
                 return info.exitStates;
             } else {
-                successEffects.clear();
-                effects.backtrack(checkpoint);
-                effects.decLevel();
-                for (VirtualObjectNode virtualObject : additionalMaterializations) {
-                    ObjectState obj = initialState.getObjectState(virtualObject);
-                    if (obj.isVirtual()) {
-                        METRIC_MATERIALIZATIONS_LOOP_REITERATION.increment();
-                        initialState.materializeBefore(loop.loopBegin().forwardEnd(), virtualObject, EscapeState.Global, effects);
-                    } else {
-                        assert obj.getState() == EscapeState.Global;
-                    }
-                }
-                for (ReadCacheEntry entry : additionalKilledReads) {
-                    initialState.getReadCache().remove(entry);
+                lastMergedState = mergeProcessor.newState;
+                for (Block block : loop.blocks) {
+                    blockEffects.get(block).clear();
                 }
             }
         }
-
         throw new GraalInternalError("too many iterations at %s", loop);
     }
 
-    private void processLoopExit(LoopExitNode exitNode, BlockState initialState, BlockState exitState) {
+    private static void processLoopExit(LoopExitNode exitNode, BlockState initialState, BlockState exitState, GraphEffectList effects) {
         HashMap<VirtualObjectNode, ProxyNode> proxies = new HashMap<>();
 
         for (ProxyNode proxy : exitNode.proxies()) {
@@ -543,7 +397,7 @@
                         if ((value instanceof PhiNode && ((PhiNode) value).merge() == exitNode.loopBegin()) || initialObj == null || !initialObj.isVirtual() || initialObj.getEntry(i) != value) {
                             ProxyNode proxy = new ProxyNode(value, exitNode, PhiType.Value, null);
                             obj.setEntry(i, proxy);
-                            effects.addFloatingNode(proxy);
+                            effects.addFloatingNode(proxy, "virtualProxy");
                         }
                     }
                 }
@@ -552,15 +406,18 @@
                     ProxyNode proxy = proxies.get(obj.virtual);
                     if (proxy == null) {
                         proxy = new ProxyNode(obj.getMaterializedValue(), exitNode, PhiType.Value, null);
-                        effects.addFloatingNode(proxy);
+                        effects.addFloatingNode(proxy, "proxy");
                     } else {
                         effects.replaceFirstInput(proxy, proxy.value(), obj.getMaterializedValue());
                         // nothing to do - will be handled in processNode
                     }
                     obj.updateMaterializedValue(proxy);
                 } else {
-                    assert initialObj.getMaterializedValue() == obj.getMaterializedValue() : "materialized value is not allowed to change within loops: " + initialObj.getMaterializedValue() +
-                                    " vs. " + obj.getMaterializedValue() + " at " + exitNode;
+                    // assert initialObj.getMaterializedValue() == obj.getMaterializedValue() :
+                    // "materialized value is not allowed to change within loops: " +
+// initialObj.getMaterializedValue()
+                    // +
+                    // " vs. " + obj.getMaterializedValue() + " at " + exitNode;
                 }
             }
         }
@@ -568,207 +425,312 @@
         for (Map.Entry<ReadCacheEntry, ValueNode> entry : exitState.getReadCache().entrySet()) {
             if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
                 ProxyNode proxy = new ProxyNode(exitState.getReadCache(entry.getKey().object, entry.getKey().identity), exitNode, PhiType.Value, null);
-                effects.addFloatingNode(proxy);
+                effects.addFloatingNode(proxy, "readCacheProxy");
                 entry.setValue(proxy);
             }
         }
     }
 
-    private final class PhiDesc {
+    private static class MergeProcessor {
+
+        private final Block mergeBlock;
+        private final MergeNode merge;
+        private final NodeBitMap usages;
+        private final BlockMap<GraphEffectList> blockEffects;
+        private final GraphEffectList mergeEffects;
+        private final GraphEffectList afterMergeEffects;
 
-        public final VirtualObjectNode virtualObject;
-        public final int fieldIndex;
+        private final HashMap<Object, PhiNode> materializedPhis = new HashMap<>();
+        private final IdentityHashMap<VirtualObjectNode, PhiNode[]> valuePhis = new IdentityHashMap<>();
+        private final IdentityHashMap<PhiNode, PhiNode[]> valueObjectMergePhis = new IdentityHashMap<>();
+        private final IdentityHashMap<PhiNode, VirtualObjectNode> valueObjectVirtuals = new IdentityHashMap<>();
+        private BlockState newState;
 
-        public PhiDesc(VirtualObjectNode virtualObject, int fieldIndex) {
-            this.virtualObject = virtualObject;
-            this.fieldIndex = fieldIndex;
+        public MergeProcessor(Block mergeBlock, NodeBitMap usages, BlockMap<GraphEffectList> blockEffects) {
+            this.usages = usages;
+            this.mergeBlock = mergeBlock;
+            this.blockEffects = blockEffects;
+            this.merge = (MergeNode) mergeBlock.getBeginNode();
+            this.mergeEffects = new GraphEffectList();
+            this.afterMergeEffects = new GraphEffectList();
         }
 
-        @Override
-        public int hashCode() {
-            final int prime = 31;
-            int result = fieldIndex;
-            result = prime * result + ((virtualObject == null) ? 0 : virtualObject.hashCode());
+        private <T> PhiNode getCachedPhi(T virtual, Kind kind) {
+            PhiNode result = materializedPhis.get(virtual);
+            if (result == null) {
+                result = new PhiNode(kind, merge);
+                materializedPhis.put(virtual, result);
+            }
+            return result;
+        }
+
+        private PhiNode[] getValuePhis(VirtualObjectNode virtual) {
+            PhiNode[] result = valuePhis.get(virtual);
+            if (result == null) {
+                result = new PhiNode[virtual.entryCount()];
+                valuePhis.put(virtual, result);
+            }
+            return result;
+        }
+
+        private PhiNode[] getValueObjectMergePhis(PhiNode phi, int entryCount) {
+            PhiNode[] result = valueObjectMergePhis.get(phi);
+            if (result == null) {
+                result = new PhiNode[entryCount];
+                valueObjectMergePhis.put(phi, result);
+            }
+            return result;
+        }
+
+        private VirtualObjectNode getValueObjectVirtual(PhiNode phi, VirtualObjectNode virtual) {
+            VirtualObjectNode result = valueObjectVirtuals.get(phi);
+            if (result == null) {
+                result = virtual.duplicate();
+                valueObjectVirtuals.put(phi, result);
+            }
             return result;
         }
 
-        @Override
-        public boolean equals(Object obj) {
-            if (this == obj) {
-                return true;
-            }
-            if (obj == null || getClass() != obj.getClass()) {
-                return false;
-            }
-            PhiDesc other = (PhiDesc) obj;
-            return virtualObject == other.virtualObject && fieldIndex == other.fieldIndex;
-        }
-    }
+        private void merge(List<BlockState> states) {
+            newState = BlockState.meetAliases(states);
 
-    private void processLoopEnds(Loop loop, BlockState initialState, List<BlockState> loopEndStates, GraphEffectList successEffects, Set<VirtualObjectNode> additionalMaterializations,
-                    HashSet<ReadCacheEntry> additionalKilledReads, HashSet<PhiDesc> phis) {
-        LoopBeginNode loopBegin = loop.loopBegin();
-        int loopEndCount = loop.header.getPredecessorCount() - 1;
-
-        boolean materialized;
-        do {
-            materialized = false;
-            for (ObjectState state : initialState.getStates()) {
-                for (int loopEndIndex = 0; loopEndIndex < loopEndCount; loopEndIndex++) {
-                    BlockState loopEndState = loopEndStates.get(loopEndIndex);
+            /*
+             * Iterative processing: Merging the materialized/virtual state of virtual objects can
+             * lead to new materializations, which can lead to new materializations because of phis,
+             * and so on.
+             */
 
-                    ObjectState endState = loopEndState.getObjectState(state.virtual);
-                    if (state.isVirtual()) {
-                        if (endState.isVirtual()) {
-                            assert state.getEntries().length == endState.getEntries().length;
-                            for (int i = 0; endState.isVirtual() && i < state.getEntries().length; i++) {
-                                ValueNode value = state.getEntry(i);
-                                ValueNode endValue = endState.getEntry(i);
-                                ObjectState valueObj = initialState.getObjectState(value);
-                                ObjectState endValueObj = loopEndState.getObjectState(endValue);
+            HashSet<VirtualObjectNode> virtualObjects = new HashSet<>(newState.getVirtualObjects());
+            boolean materialized;
+            do {
+                mergeEffects.clear();
+                afterMergeEffects.clear();
+                materialized = false;
+                for (VirtualObjectNode object : virtualObjects) {
+                    ObjectState[] objStates = new ObjectState[states.size()];
+                    for (int i = 0; i < states.size(); i++) {
+                        objStates[i] = states.get(i).getObjectState(object);
+                    }
+                    int virtual = 0;
+                    ObjectState startObj = objStates[0];
+                    int lockCount = startObj.getLockCount();
+                    boolean locksMatch = true;
+                    ValueNode singleValue = startObj.isVirtual() ? null : startObj.getMaterializedValue();
+                    for (ObjectState obj : objStates) {
+                        if (obj.isVirtual()) {
+                            virtual++;
+                            singleValue = null;
+                        } else {
+                            if (obj.getMaterializedValue() != singleValue) {
+                                singleValue = null;
+                            }
+                        }
+                        locksMatch &= obj.getLockCount() == lockCount;
+                    }
 
-                                if (valueObj != null) {
-                                    if (valueObj.isVirtual()) {
-                                        if (endValueObj == null || !endValueObj.isVirtual() || valueObj.virtual != endValueObj.virtual) {
-                                            additionalMaterializations.add(valueObj.virtual);
-                                        } else {
-                                            /*
-                                             * endValue is also virtual and refers to the same
-                                             * virtual object, so we're good.
-                                             */
-                                        }
-                                    }
-                                } else {
-                                    if (value instanceof PhiNode && ((PhiNode) value).merge() == loopBegin) {
-                                        if (endValueObj != null) {
-                                            if (endValueObj.isVirtual()) {
-                                                METRIC_MATERIALIZATIONS_LOOP_END.increment();
-                                                FixedNode endNode = loop.header.getPredecessors().get(loopEndIndex + 1).getEndNode();
-                                                loopEndState.materializeBefore(endNode, endValueObj.virtual, EscapeState.Global, successEffects);
-                                                materialized = true;
-                                            }
-                                        }
-                                    }
+                    assert virtual < states.size() || locksMatch : "mismatching lock counts at " + merge;
+
+                    if (virtual < states.size()) {
+                        if (singleValue == null) {
+                            PhiNode materializedValuePhi = getCachedPhi(object, Kind.Object);
+                            mergeEffects.addFloatingNode(materializedValuePhi, "materializedPhi");
+                            for (int i = 0; i < states.size(); i++) {
+                                BlockState state = states.get(i);
+                                ObjectState obj = objStates[i];
+                                materialized |= obj.isVirtual();
+                                Block predecessor = mergeBlock.getPredecessors().get(i);
+                                ensureMaterialized(state, obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE);
+                                afterMergeEffects.addPhiInput(materializedValuePhi, obj.getMaterializedValue());
+                            }
+                            newState.addObject(object, new ObjectState(object, materializedValuePhi, EscapeState.Global, lockCount));
+                        } else {
+                            newState.addObject(object, new ObjectState(object, singleValue, EscapeState.Global, lockCount));
+                        }
+                    } else {
+                        assert virtual == states.size();
+                        ValueNode[] values = startObj.getEntries().clone();
+                        PhiNode[] phis = getValuePhis(object);
+                        for (int index = 0; index < values.length; index++) {
+                            for (int i = 1; i < states.size(); i++) {
+                                ValueNode[] fields = objStates[i].getEntries();
+                                if (phis[index] == null && values[index] != fields[index]) {
+                                    phis[index] = new PhiNode(values[index].kind(), merge);
                                 }
                             }
+                        }
+                        outer: for (int index = 0; index < values.length; index++) {
+                            if (phis[index] != null) {
+                                mergeEffects.addFloatingNode(phis[index], "virtualMergePhi");
+                                for (int i = 0; i < states.size(); i++) {
+                                    if (!objStates[i].isVirtual()) {
+                                        break outer;
+                                    }
+                                    ValueNode[] fields = objStates[i].getEntries();
+                                    ObjectState obj = states.get(i).getObjectState(fields[index]);
+                                    if (obj != null) {
+                                        materialized |= obj.isVirtual();
+                                        Block predecessor = mergeBlock.getPredecessors().get(i);
+                                        ensureMaterialized(states.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE);
+                                        fields[index] = obj.getMaterializedValue();
+                                    }
+                                    afterMergeEffects.addPhiInput(phis[index], fields[index]);
+                                }
+                                values[index] = phis[index];
+                            }
+                        }
+                        newState.addObject(object, new ObjectState(object, values, EscapeState.Virtual, lockCount));
+                    }
+                }
+
+                for (PhiNode phi : merge.phis()) {
+                    if (usages.isMarked(phi) && phi.type() == PhiType.Value) {
+                        materialized |= processPhi(phi, states);
+                    }
+                }
+            } while (materialized);
+
+            mergeReadCache(states);
+        }
+
+        private boolean processPhi(PhiNode phi, List<BlockState> states) {
+            assert states.size() == phi.valueCount();
+            int virtualInputs = 0;
+            boolean materialized = false;
+            VirtualObjectNode sameObject = null;
+            ResolvedJavaType sameType = null;
+            int sameEntryCount = -1;
+            boolean hasIdentity = false;
+            for (int i = 0; i < phi.valueCount(); i++) {
+                ValueNode value = phi.valueAt(i);
+                ObjectState obj = states.get(i).getObjectState(value);
+                if (obj != null) {
+                    if (obj.isVirtual()) {
+                        virtualInputs++;
+                        if (i == 0) {
+                            sameObject = obj.virtual;
+                            sameType = obj.virtual.type();
+                            sameEntryCount = obj.virtual.entryCount();
                         } else {
-                            additionalMaterializations.add(state.virtual);
+                            if (sameObject != obj.virtual) {
+                                sameObject = null;
+                            }
+                            if (sameType != obj.virtual.type()) {
+                                sameType = null;
+                            }
+                            if (sameEntryCount != obj.virtual.entryCount()) {
+                                sameEntryCount = -1;
+                            }
+                            hasIdentity |= obj.virtual.hasIdentity();
                         }
+                    } else {
+                        afterMergeEffects.setPhiInput(phi, i, obj.getMaterializedValue());
                     }
                 }
             }
-
-            for (PhiNode phi : loopBegin.phis()) {
-                if (usages.isMarked(phi) && phi.type() == PhiType.Value) {
-                    ObjectState initialObj = initialState.getObjectState(phi.valueAt(0));
-                    boolean initialMaterialized = initialObj == null || !initialObj.isVirtual();
+            boolean materialize = false;
+            if (virtualInputs == 0) {
+                // nothing to do...
+            } else if (virtualInputs == phi.valueCount()) {
+                if (sameObject != null) {
+                    newState.addAndMarkAlias(sameObject, phi, usages);
+                } else if (sameType != null && sameEntryCount != -1) {
+                    if (!hasIdentity) {
+                        VirtualObjectNode virtual = getValueObjectVirtual(phi, states.get(0).getObjectState(phi.valueAt(0)).virtual);
 
-                    for (int loopEndIndex = 0; loopEndIndex < loopEndCount; loopEndIndex++) {
-                        BlockState loopEndState = loopEndStates.get(loopEndIndex);
-                        LoopEndNode endNode = (LoopEndNode) loop.header.getPredecessors().get(loopEndIndex + 1).getEndNode();
-                        ObjectState loopEndObj = loopEndState.getObjectState(phi.valueAt(endNode));
-                        if (loopEndObj == null || !loopEndObj.isVirtual()) {
-                            if (loopEndObj != null) {
-                                successEffects.setPhiInput(phi, loopBegin.phiPredecessorIndex(endNode), loopEndObj.getMaterializedValue());
+                        PhiNode[] phis = getValueObjectMergePhis(phi, virtual.entryCount());
+                        for (int i = 0; i < virtual.entryCount(); i++) {
+                            assert virtual.entryKind(i) != Kind.Object;
+                            if (phis[i] == null) {
+                                phis[i] = new PhiNode(virtual.entryKind(i), merge);
                             }
-                            if (!initialMaterialized) {
-                                additionalMaterializations.add(initialObj.virtual);
-                            }
-                        } else {
-                            if (initialMaterialized) {
-                                loopEndState.materializeBefore(endNode, loopEndObj.virtual, EscapeState.Global, successEffects);
-                                materialized = true;
-                            } else {
-                                if (loopEndObj.virtual != initialObj.virtual) {
-                                    additionalMaterializations.add(initialObj.virtual);
-                                }
+                            mergeEffects.addFloatingNode(phis[i], "valueObjectPhi");
+                            for (int i2 = 0; i2 < phi.valueCount(); i2++) {
+                                afterMergeEffects.addPhiInput(phis[i], states.get(i2).getObjectState(phi.valueAt(i2)).getEntry(i));
                             }
                         }
+                        mergeEffects.addFloatingNode(virtual, "valueObjectNode");
+                        newState.addObject(virtual, new ObjectState(virtual, Arrays.copyOf(phis, phis.length, ValueNode[].class), EscapeState.Virtual, 0));
+                        newState.addAndMarkAlias(virtual, virtual, usages);
+                        newState.addAndMarkAlias(virtual, phi, usages);
+                    } else {
+                        materialize = true;
+                    }
+                } else {
+                    materialize = true;
+                }
+            } else {
+                materialize = true;
+            }
+
+            if (materialize) {
+                for (int i = 0; i < phi.valueCount(); i++) {
+                    ValueNode value = phi.valueAt(i);
+                    ObjectState obj = states.get(i).getObjectState(value);
+                    if (obj != null) {
+                        materialized |= obj.isVirtual();
+                        Block predecessor = mergeBlock.getPredecessors().get(i);
+                        replaceWithMaterialized(value, phi, predecessor.getEndNode(), states.get(i), obj, blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_PHI);
                     }
                 }
             }
-
-        } while (materialized);
-
-        for (ObjectState state : initialState.getStates()) {
-            for (BlockState loopEndState : loopEndStates) {
-                ObjectState endState = loopEndState.getObjectState(state.virtual);
-                if (state.isVirtual()) {
-                    if (endState.isVirtual()) {
-                        assert state.getEntries().length == endState.getEntries().length;
-                        for (int i = 0; i < state.getEntries().length; i++) {
-                            ValueNode value = state.getEntry(i);
-                            ValueNode endValue = endState.getEntry(i);
-                            ObjectState valueObj = initialState.getObjectState(value);
-                            ObjectState endValueObj = loopEndState.getObjectState(endValue);
+            return materialized;
+        }
 
-                            if (valueObj != null) {
-                                if (valueObj.isVirtual()) {
-                                    if (endValueObj == null || !endValueObj.isVirtual() || valueObj.virtual != endValueObj.virtual) {
-                                        assert !additionalMaterializations.isEmpty();
-                                    } else {
-                                        /*
-                                         * endValue is also virtual and refers to the same virtual
-                                         * object, so we're good.
-                                         */
-                                    }
-                                } else {
-                                    if ((endValueObj != null && endValueObj.getMaterializedValue() != valueObj.getMaterializedValue()) ||
-                                                    (endValueObj == null && valueObj.getMaterializedValue() != endValue)) {
-                                        phis.add(new PhiDesc(state.virtual, i));
-                                    } else {
-                                        /*
-                                         * either endValue has the same materialized value as value
-                                         * or endValue is the same as the materialized value, so
-                                         * we're good.
-                                         */
-                                    }
-                                }
-                            } else {
-                                if (value instanceof PhiNode && ((PhiNode) value).merge() == loopBegin) {
-                                    if (endValueObj != null) {
-                                        if (endValueObj.isVirtual()) {
-                                            assert !additionalMaterializations.isEmpty();
-                                        }
-                                        successEffects.addPhiInput((PhiNode) value, endValueObj.getMaterializedValue());
-                                    } else {
-                                        successEffects.addPhiInput((PhiNode) value, endValue);
-                                    }
-                                } else if (value != endValue) {
-                                    phis.add(new PhiDesc(state.virtual, i));
-                                }
-                            }
-                        }
-                    } else {
-                        // endState.materializedValue != null
-                        assert !additionalMaterializations.isEmpty();
+        private void mergeReadCache(List<BlockState> states) {
+            for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
+                ReadCacheEntry key = entry.getKey();
+                ValueNode value = entry.getValue();
+                boolean phi = false;
+                for (int i = 1; i < states.size(); i++) {
+                    ValueNode otherValue = states.get(i).readCache.get(key);
+                    if (otherValue == null) {
+                        value = null;
+                        phi = false;
+                        break;
+                    }
+                    if (!phi && otherValue != value) {
+                        phi = true;
                     }
-                } else {
-                    // state.materializedValue != null
-                    if (endState.isVirtual()) {
-                        /*
-                         * throw new GraalInternalError("un-materialized object state at %s",
-                         * loopEnd);
-                         */
-                    } else {
-                        if (state.getMaterializedValue() != endState.getMaterializedValue()) {
-                            /*
-                             * throw new
-                             * GraalInternalError("changed materialized value during loop: %s vs %s"
-                             * , state.materializedValue, endState.materializedValue);
-                             */
+                }
+                if (phi) {
+                    PhiNode phiNode = getCachedPhi(entry, value.kind());
+                    mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
+                    for (int i = 0; i < states.size(); i++) {
+                        afterMergeEffects.addPhiInput(phiNode, states.get(i).getReadCache(key.object, key.identity));
+                    }
+                    newState.readCache.put(key, phiNode);
+                } else if (value != null) {
+                    newState.readCache.put(key, value);
+                }
+            }
+            for (PhiNode phi : merge.phis()) {
+                if (phi.kind() == Kind.Object) {
+                    for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
+                        if (entry.getKey().object == phi.valueAt(0)) {
+                            mergeReadCachePhi(phi, entry.getKey().identity, states);
                         }
                     }
+
                 }
             }
         }
 
-        for (Map.Entry<ReadCacheEntry, ValueNode> entry : initialState.getReadCache().entrySet()) {
-            for (BlockState loopEndState : loopEndStates) {
-                if (loopEndState.getReadCache().get(entry.getKey()) != entry.getValue()) {
-                    additionalKilledReads.add(entry.getKey());
+        private void mergeReadCachePhi(PhiNode phi, Object identity, List<BlockState> 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);
+                if (value == null) {
+                    return;
                 }
+                values[i] = value;
             }
+
+            PhiNode phiNode = getCachedPhi(new ReadCacheEntry(identity, phi), values[0].kind());
+            mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
+            for (int i = 0; i < values.length; i++) {
+                afterMergeEffects.addPhiInput(phiNode, values[i]);
+            }
+            newState.readCache.put(new ReadCacheEntry(identity, phi), phiNode);
         }
     }
 }
diff -r a8260ba9c762 -r fc972f34c1d5 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	Mon Apr 08 19:12:19 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java	Mon Apr 08 19:14:32 2013 +0200
@@ -36,13 +36,12 @@
 
 class VirtualizerToolImpl implements VirtualizerTool {
 
-    private final GraphEffectList effects;
     private final NodeBitMap usages;
     private final MetaAccessProvider metaAccess;
     private final Assumptions assumptions;
+    private GraphEffectList effects;
 
-    VirtualizerToolImpl(GraphEffectList effects, NodeBitMap usages, MetaAccessProvider metaAccess, Assumptions assumptions) {
-        this.effects = effects;
+    VirtualizerToolImpl(NodeBitMap usages, MetaAccessProvider metaAccess, Assumptions assumptions) {
         this.usages = usages;
         this.metaAccess = metaAccess;
         this.assumptions = assumptions;
@@ -52,7 +51,6 @@
     private boolean customAction;
     private BlockState state;
     private ValueNode current;
-    private int newVirtualObjectCount = 0;
 
     @Override
     public MetaAccessProvider getMetaAccessProvider() {
@@ -64,6 +62,10 @@
         return assumptions;
     }
 
+    public void setEffects(GraphEffectList effects) {
+        this.effects = effects;
+    }
+
     public void reset(BlockState newState, ValueNode newCurrent) {
         deleted = false;
         customAction = false;
@@ -79,10 +81,6 @@
         return customAction;
     }
 
-    public int getNewVirtualObjectCount() {
-        return newVirtualObjectCount;
-    }
-
     @Override
     public State getObjectState(ValueNode value) {
         return state.getObjectState(value);
@@ -155,7 +153,7 @@
         if (virtualObject.isAlive()) {
             state.addAndMarkAlias(virtualObject, virtualObject, usages);
         } else {
-            effects.addFloatingNode(virtualObject);
+            effects.addFloatingNode(virtualObject, "newVirtualObject");
         }
         for (int i = 0; i < entryState.length; i++) {
             entryState[i] = state.getScalarAlias(entryState[i]);
@@ -163,7 +161,6 @@
         state.addObject(virtualObject, new ObjectState(virtualObject, entryState, EscapeState.Virtual, lockCount));
         state.addAndMarkAlias(virtualObject, virtualObject, usages);
         PartialEscapeClosure.METRIC_ALLOCATION_REMOVED.increment();
-        newVirtualObjectCount++;
     }
 
     @Override