# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1352738946 -3600
# Node ID 6db6881c1270c422508d22152064789108b86313
# Parent  55afed7bc2091a5b6dbb08f3bdaac312a276a642
add Virtualizable and VirtualizerTool, refactor PEA to use it

diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PiNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PiNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PiNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -25,13 +25,14 @@
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * A node that changes the type of its input, usually narrowing it.
  * For example, a PI node refines the type of a receiver during
  * type-guarded inlining to be the type tested by the guard.
  */
-public class PiNode extends FloatingNode implements LIRLowerable {
+public class PiNode extends FloatingNode implements LIRLowerable, Virtualizable {
 
     @Input private ValueNode object;
     @Input(notDataflow = true) private final FixedNode anchor;
@@ -64,4 +65,12 @@
         }
         return updateStamp(stamp().join(object().stamp()));
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(object());
+        if (virtual != null) {
+            tool.replaceWithVirtual(virtual);
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueProxyNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueProxyNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueProxyNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -26,14 +26,16 @@
 import com.oracle.graal.graph.Node.ValueNumberable;
 import com.oracle.graal.nodes.PhiNode.PhiType;
 import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * A value proxy that is inserted in the frame state of a loop exit for any value that is
  * created inside the loop (i.e. was not live on entry to the loop) and is (potentially)
  * used after the loop.
  */
-public class ValueProxyNode extends FloatingNode implements Node.IterableNodeType, ValueNumberable {
+public class ValueProxyNode extends FloatingNode implements Node.IterableNodeType, ValueNumberable, Canonicalizable, Virtualizable {
     @Input(notDataflow = true) private BeginNode proxyPoint;
     @Input private ValueNode value;
     private final PhiType type;
@@ -74,4 +76,20 @@
         assert proxyPoint != null;
         return super.verify();
     }
+
+    @Override
+    public ValueNode canonical(CanonicalizerTool tool) {
+        if (value.isConstant()) {
+            return value;
+        }
+        return this;
+    }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(value());
+        if (virtual != null) {
+            tool.replaceWithVirtual(virtual);
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IsNullNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IsNullNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IsNullNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -30,7 +30,7 @@
 /**
  * An IsNullNode will be true if the supplied value is null, and false if it is non-null.
  */
-public final class IsNullNode extends BooleanNode implements Canonicalizable, LIRLowerable {
+public final class IsNullNode extends BooleanNode implements Canonicalizable, LIRLowerable, Virtualizable {
 
     @Input private ValueNode object;
 
@@ -73,4 +73,11 @@
         }
         return this;
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        if (tool.getVirtualState(object()) != null || tool.getMaterializedValue(object()) != null) {
+            tool.replaceWithValue(ConstantNode.forBoolean(false, graph()));
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ObjectEqualsNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ObjectEqualsNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ObjectEqualsNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -26,9 +26,10 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.virtual.*;
 
 @NodeInfo(shortName = "==")
-public final class ObjectEqualsNode extends CompareNode {
+public final class ObjectEqualsNode extends CompareNode implements Virtualizable {
 
     /**
      * Constructs a new object equality comparison node.
@@ -69,4 +70,20 @@
 
         return super.canonical(tool);
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtualX = tool.getVirtualState(x());
+        VirtualObjectNode virtualY = tool.getVirtualState(y());
+        boolean xVirtual = virtualX != null;
+        boolean yVirtual = virtualY != null;
+
+        if (xVirtual ^ yVirtual) {
+            // one of them is virtual: they can never be the same objects
+            tool.replaceWithValue(ConstantNode.forBoolean(false, graph()));
+        } else if (xVirtual && yVirtual) {
+            // both are virtual: check if they refer to the same object
+            tool.replaceWithValue(ConstantNode.forBoolean(virtualX == virtualY, graph()));
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/LoadHubNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/LoadHubNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/LoadHubNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -27,11 +27,12 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * Loads an object's {@linkplain Representation#ObjectHub hub}, null-checking the object first.
  */
-public final class LoadHubNode extends FixedWithNextNode implements Lowerable, Canonicalizable {
+public final class LoadHubNode extends FixedWithNextNode implements Lowerable, Canonicalizable, Virtualizable {
     @Input private ValueNode object;
 
     public ValueNode object() {
@@ -75,4 +76,12 @@
 
     @NodeIntrinsic
     public static native Object loadHub(Object object);
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(object());
+        if (virtual != null) {
+            tool.replaceWithValue(ConstantNode.forConstant(virtual.type().getEncoding(Representation.ObjectHub), tool.getMetaAccessProvider(), graph()));
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ValueAnchorNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ValueAnchorNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ValueAnchorNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -28,13 +28,14 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
 
 /**
  * The ValueAnchor instruction keeps non-CFG (floating) nodes above a certain point in the graph.
  */
-public final class ValueAnchorNode extends FixedWithNextNode implements Canonicalizable, LIRLowerable, Node.IterableNodeType {
+public final class ValueAnchorNode extends FixedWithNextNode implements Canonicalizable, LIRLowerable, Node.IterableNodeType, Virtualizable {
 
     public ValueAnchorNode(ValueNode... values) {
         super(StampFactory.dependency(), values);
@@ -84,4 +85,21 @@
         }
         return this;
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        // don't process this node if it is anchoring the return value
+        if (next() instanceof MonitorExitNode) {
+            MonitorExitNode monitorExit = (MonitorExitNode) next();
+            if (monitorExit.stateAfter() != null && monitorExit.stateAfter().bci == FrameState.AFTER_BCI && monitorExit.next() instanceof ReturnNode) {
+                return;
+            }
+        }
+        for (ValueNode node : dependencies().nonNull().and(isNotA(BeginNode.class))) {
+            if (tool.getVirtualState(node) == null) {
+                return;
+            }
+        }
+        tool.delete();
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessMonitorNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessMonitorNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessMonitorNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -23,9 +23,12 @@
 package com.oracle.graal.nodes.java;
 
 import com.oracle.graal.api.code.*;
+import com.oracle.graal.debug.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.extended.*;
+import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * The {@code AccessMonitorNode} is the base class of both monitor acquisition and release.
@@ -38,12 +41,9 @@
  * locking hierarchy.
  * <br>
  * The Java bytecode specification allows non-balanced locking. Graal does not handle such cases and throws a
- * {@link BailoutException} instead. Detecting non-balanced monitors during bytecode parsing is difficult, since the
- * node flowing into the {@link MonitorExitNode} can be a phi function hiding the node that was flowing into the
- * {@link MonitorEnterNode}. Optimization phases are free to throw {@link BailoutException} if they detect such cases.
- * Otherwise, they are detected during LIR construction.
+ * {@link BailoutException} instead during graph building.
  */
-public abstract class AccessMonitorNode extends AbstractStateSplit implements StateSplit, MemoryCheckpoint {
+public abstract class AccessMonitorNode extends AbstractStateSplit implements StateSplit, MemoryCheckpoint, Virtualizable {
 
     @Input private ValueNode object;
     private boolean eliminated;
@@ -69,4 +69,21 @@
         super(StampFactory.forVoid());
         this.object = object;
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(object());
+        if (virtual != null) {
+            Debug.log("monitor operation %s on %s\n", this, virtual);
+            int newLockCount = tool.getVirtualLockCount(virtual) + (this instanceof MonitorEnterNode ? 1 : -1);
+            tool.setVirtualLockCount(virtual,  newLockCount);
+            tool.replaceFirstInput(object(), virtual);
+            tool.customAction(new Runnable() {
+                @Override
+                public void run() {
+                    eliminate();
+                }
+            });
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/ArrayLengthNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/ArrayLengthNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/ArrayLengthNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -26,11 +26,12 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * The {@code ArrayLength} instruction gets the length of an array.
  */
-public final class ArrayLengthNode extends FixedWithNextNode implements Canonicalizable, Lowerable {
+public final class ArrayLengthNode extends FixedWithNextNode implements Canonicalizable, Lowerable, Virtualizable {
 
     @Input private ValueNode array;
 
@@ -67,4 +68,13 @@
 
     @NodeIntrinsic
     public static native int arrayLength(Object array);
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(array());
+        if (virtual != null) {
+            assert virtual instanceof VirtualArrayNode : virtual;
+            tool.replaceWithValue(ConstantNode.forInt(virtual.entryCount(), graph()));
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -27,11 +27,12 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * Implements a type check against a compile-time known type.
  */
-public final class CheckCastNode extends FixedWithNextNode implements Canonicalizable, Lowerable, Node.IterableNodeType {
+public final class CheckCastNode extends FixedWithNextNode implements Canonicalizable, Lowerable, Node.IterableNodeType, Virtualizable {
 
     @Input private ValueNode object;
     private final ResolvedJavaType type;
@@ -97,4 +98,12 @@
     public JavaTypeProfile profile() {
         return profile;
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(object());
+        if (virtual != null && virtual.type().isSubtypeOf(type())) {
+            tool.replaceWithVirtual(virtual);
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/LoadFieldNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/LoadFieldNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/LoadFieldNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -27,12 +27,13 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * The {@code LoadFieldNode} represents a read of a static or instance field.
  */
 @NodeInfo(nameTemplate = "LoadField#{p#field/s}")
-public final class LoadFieldNode extends AccessFieldNode implements Canonicalizable, Node.IterableNodeType {
+public final class LoadFieldNode extends AccessFieldNode implements Canonicalizable, Node.IterableNodeType, Virtualizable {
 
     /**
      * Creates a new LoadFieldNode instance.
@@ -69,4 +70,21 @@
         }
         return this;
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(object());
+        if (virtual != null) {
+            int fieldIndex = ((VirtualInstanceNode) virtual).fieldIndex(field());
+            if (fieldIndex != -1) {
+                ValueNode result = tool.getVirtualEntry(virtual, fieldIndex);
+                VirtualObjectNode virtualResult = tool.getVirtualState(result);
+                if (virtualResult != null) {
+                    tool.replaceWithVirtual(virtualResult);
+                } else {
+                    tool.replaceWithValue(result);
+                }
+            }
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/LoadIndexedNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/LoadIndexedNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/LoadIndexedNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -29,11 +29,12 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * The {@code LoadIndexedNode} represents a read from an element of an array.
  */
-public final class LoadIndexedNode extends AccessIndexedNode implements Canonicalizable, Node.IterableNodeType {
+public final class LoadIndexedNode extends AccessIndexedNode implements Canonicalizable, Node.IterableNodeType, Virtualizable {
 
     /**
      * Creates a new LoadIndexedNode.
@@ -70,4 +71,22 @@
         }
         return this;
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtualArray = tool.getVirtualState(array());
+        if (virtualArray != null) {
+            ValueNode indexValue = tool.getReplacedValue(index());
+            int index = indexValue.isConstant() ? indexValue.asConstant().asInt() : -1;
+            if (index >= 0 && index < virtualArray.entryCount()) {
+                ValueNode result = tool.getVirtualEntry(virtualArray, index);
+                VirtualObjectNode virtualResult = tool.getVirtualState(result);
+                if (virtualResult != null) {
+                    tool.replaceWithVirtual(virtualResult);
+                } else {
+                    tool.replaceWithValue(result);
+                }
+            }
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/StoreFieldNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/StoreFieldNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/StoreFieldNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -25,13 +25,15 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * The {@code StoreFieldNode} represents a write to a static or instance field.
  */
 @NodeInfo(nameTemplate = "StoreField#{p#field/s}")
-public final class StoreFieldNode extends AccessFieldNode implements StateSplit {
+public final class StoreFieldNode extends AccessFieldNode implements StateSplit, Virtualizable {
 
     @Input private ValueNode value;
     @Input(notDataflow = true) private FrameState stateAfter;
@@ -64,4 +66,16 @@
         super(StampFactory.forVoid(), object, field, leafGraphId);
         this.value = value;
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(object());
+        if (virtual != null) {
+            int fieldIndex = ((VirtualInstanceNode) virtual).fieldIndex(field());
+            if (fieldIndex != -1) {
+                tool.setVirtualEntry(virtual, fieldIndex, value());
+                tool.delete();
+            }
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/StoreIndexedNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/StoreIndexedNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/StoreIndexedNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -26,11 +26,12 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * The {@code StoreIndexedNode} represents a write to an array element.
  */
-public final class StoreIndexedNode extends AccessIndexedNode implements StateSplit, Lowerable {
+public final class StoreIndexedNode extends AccessIndexedNode implements StateSplit, Lowerable, Virtualizable {
 
     @Input private ValueNode value;
     @Input(notDataflow = true) private FrameState stateAfter;
@@ -64,4 +65,17 @@
         super(StampFactory.forVoid(), array, index, elementKind, leafGraphId);
         this.value = value;
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtualArray = tool.getVirtualState(array());
+        if (virtualArray != null) {
+            ValueNode indexValue = tool.getReplacedValue(index());
+            int index = indexValue.isConstant() ? indexValue.asConstant().asInt() : -1;
+            if (index >= 0 && index < virtualArray.entryCount()) {
+                tool.setVirtualEntry(virtualArray, index, value());
+                tool.delete();
+            }
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/Virtualizable.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/Virtualizable.java	Mon Nov 12 17:49:06 2012 +0100
@@ -0,0 +1,40 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.nodes.spi;
+
+/**
+ * This interface allows a node to convey information about what its effect would be if some of its inputs were
+ * virtualized.
+ */
+public interface Virtualizable {
+
+    /**
+     * A node class can implement this method to convey information about what its effect would be if some of its inputs
+     * were virtualized. All modifications must be made through the supplied tool, and not directly on the node, because
+     * by the time this method is called the virtualized/non-virtualized state is still speculative and might not hold
+     * because of loops, etc.
+     *
+     * @param tool the tool used to describe the effects of this node
+     */
+    void virtualize(VirtualizerTool tool);
+}
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/VirtualizerTool.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/VirtualizerTool.java	Mon Nov 12 17:49:06 2012 +0100
@@ -0,0 +1,145 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.nodes.spi;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.virtual.*;
+
+/**
+ * This tool can be used to query the current state (normal/virtualized/re-materialized) of values and to describe the
+ * actions that would be taken for this state.
+ *
+ * See also {@link Virtualizable}.
+ */
+public interface VirtualizerTool {
+
+    /**
+     * @return the {@link MetaAccessProvider} associated with the current compilation, which might be required for
+     *         creating constants, etc.
+     */
+    MetaAccessProvider getMetaAccessProvider();
+
+    // methods working on virtualized/materialized objects
+
+    /**
+     * Queries the current state of the given value: if it is virtualized (thread-local and the compiler knows all
+     * entries) or not.
+     *
+     * @param value the value whose state should be queried.
+     * @return the {@link VirtualObjectNode} representing the value if it is virtualized, null otherwise.
+     */
+    VirtualObjectNode getVirtualState(ValueNode value);
+
+    /**
+     * Retrieves the entry (field or array element) with the given index in the virtualized object.
+     *
+     * @param virtual the virtualized object
+     * @param index the index to be queried.
+     * @return the entry at the given index.
+     */
+    ValueNode getVirtualEntry(VirtualObjectNode virtual, int index);
+
+    /**
+     * Sets the entry (field or array element) with the given index in the virtualized object.
+     *
+     * @param virtual the virtualized object.
+     * @param index the index to be set.
+     * @param value the new value for the given index.
+     */
+    void setVirtualEntry(VirtualObjectNode virtual, int index, ValueNode value);
+
+    /**
+     * Retrieves the lock count of the given virtualized object.
+     *
+     * @param virtual the virtualized object.
+     * @return the number of locks.
+     */
+    int getVirtualLockCount(VirtualObjectNode virtual);
+
+    /**
+     * Sets the lock count of the given virtualized object.
+     *
+     * @param virtual the virtualized object.
+     * @param lockCount the new lock count.
+     */
+    void setVirtualLockCount(VirtualObjectNode virtual, int lockCount);
+
+    /**
+     * Queries the current state of the given value: if it was materialized or not.
+     *
+     * @param value the value whose state should be queried.
+     * @return the materialized value (usually a MaterializeObjectNode or a {@link PhiNode}) if it was materialized,
+     *         null otherwise.
+     */
+    ValueNode getMaterializedValue(ValueNode value);
+
+    // scalar replacement
+
+    /**
+     * Replacements via {@link #replaceWithValue(ValueNode)} are not immediately committed. This method can be used to
+     * determine if a value was replaced by another one (e.g., a load field by the loaded value).
+     *
+     * @param original the original input value.
+     * @return the replacement value, or the original value if there is no replacement.
+     */
+    ValueNode getReplacedValue(ValueNode original);
+
+    // operations on the current node
+
+    /**
+     * Deletes the current node and replaces it with the given virtualized object.
+     *
+     * @param virtual the virtualized object that should replace the current node.
+     */
+    void replaceWithVirtual(VirtualObjectNode virtual);
+
+    /**
+     * Deletes the current node and replaces it with the given value.
+     *
+     * @param replacement the value that should replace the current node.
+     */
+    void replaceWithValue(ValueNode replacement);
+
+    /**
+     * Deletes the current node.
+     */
+    void delete();
+
+    /**
+     * Replaces an input of the current node.
+     *
+     * @param oldInput the old input value.
+     * @param replacement the new input value.
+     */
+    void replaceFirstInput(Node oldInput, Node replacement);
+
+    /**
+     * Performs a custom action on the current node. This action will only be performed when, and if, the changes are
+     * committed. Custom actions must not modify inputs of nodes.
+     *
+     * @param action the custom action.
+     */
+    void customAction(Runnable action);
+}
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Mon Nov 12 17:49:06 2012 +0100
@@ -68,6 +68,7 @@
 
     // escape analysis settings
     public static boolean PartialEscapeAnalysis              = true;
+    public static boolean EscapeAnalysisHistogram            = ____;
     public static int     EscapeAnalysisIterations           = 2;
     public static String  EscapeAnalyzeOnly                  = null;
 
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/CyclicMaterializeStoreNode.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/CyclicMaterializeStoreNode.java	Mon Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/CyclicMaterializeStoreNode.java	Mon Nov 12 17:49:06 2012 +0100
@@ -28,12 +28,13 @@
 import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.virtual.*;
 
 /**
  * The {@code StoreFieldNode} represents a write to a static or instance field.
  */
 @NodeInfo(nameTemplate = "MaterializeStore#{p#target/s}")
-public final class CyclicMaterializeStoreNode extends FixedWithNextNode implements Lowerable {
+public final class CyclicMaterializeStoreNode extends FixedWithNextNode implements Lowerable, Virtualizable {
 
     @Input private ValueNode object;
     @Input private ValueNode value;
@@ -82,4 +83,17 @@
         }
         graph.replaceFixedWithFixed(this, store);
     }
+
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        VirtualObjectNode virtual = tool.getVirtualState(object());
+        if (virtual != null) {
+            if (virtual instanceof VirtualArrayNode) {
+                tool.setVirtualEntry(virtual, targetIndex(), value());
+            } else {
+                tool.setVirtualEntry(virtual, ((VirtualInstanceNode) virtual).fieldIndex(targetField()), value());
+            }
+            tool.delete();
+        }
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 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 Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Mon Nov 12 17:49:06 2012 +0100
@@ -30,6 +30,7 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.virtual.*;
 import com.oracle.graal.phases.graph.ReentrantBlockIterator.MergeableBlockState;
 import com.oracle.graal.virtual.nodes.*;
@@ -88,41 +89,71 @@
             throw new BailoutException("array materialized with lock");
         }
 
-        MaterializeObjectNode materialize = new MaterializeObjectNode(virtual, obj.getLockCount());
-        ValueNode[] values = new ValueNode[obj.getEntries().length];
-        materialize.setProbability(fixed.probability());
         ValueNode[] fieldState = obj.getEntries();
-        obj.setMaterializedValue(materialize);
-        deferred.add(virtual);
+
+        // determine if all entries are default constants
+        boolean allDefault = true;
         for (int i = 0; i < fieldState.length; i++) {
-            ObjectState valueObj = getObjectState(fieldState[i]);
-            if (valueObj != null) {
-                if (valueObj.isVirtual()) {
-                    materializeChangedBefore(fixed, valueObj.virtual, deferred, deferredStores, materializeEffects);
-                }
-                if (deferred.contains(valueObj.virtual)) {
-                    Kind fieldKind;
-                    CyclicMaterializeStoreNode store;
-                    if (virtual instanceof VirtualArrayNode) {
-                        store = new CyclicMaterializeStoreNode(materialize, valueObj.getMaterializedValue(), i);
-                        fieldKind = ((VirtualArrayNode) virtual).componentType().getKind();
-                    } else {
-                        VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual;
-                        store = new CyclicMaterializeStoreNode(materialize, valueObj.getMaterializedValue(), instanceObject.field(i));
-                        fieldKind = instanceObject.field(i).getType().getKind();
-                    }
-                    deferredStores.addFixedNodeBefore(store, fixed);
-                    values[i] = ConstantNode.defaultForKind(fieldKind, fixed.graph());
-                } else {
-                    values[i] = valueObj.getMaterializedValue();
-                }
-            } else {
-                values[i] = fieldState[i];
+            if (!fieldState[i].isConstant() || !fieldState[i].asConstant().isDefaultForKind()) {
+                allDefault = false;
+                break;
             }
         }
-        deferred.remove(virtual);
 
-        materializeEffects.addMaterialization(materialize, fixed, values);
+        if (allDefault && obj.getLockCount() == 0) {
+            // create an ordinary NewInstance/NewArray node if all entries are default constants
+            FixedWithNextNode newObject;
+            if (virtual instanceof VirtualInstanceNode) {
+                newObject = new NewInstanceNode(virtual.type(), true, false);
+            } else {
+                assert virtual instanceof VirtualArrayNode;
+                ResolvedJavaType element = ((VirtualArrayNode) virtual).componentType();
+                if (element.getKind() == Kind.Object) {
+                    newObject = new NewObjectArrayNode(element, ConstantNode.forInt(virtual.entryCount(), fixed.graph()), true, false);
+                } else {
+                    newObject = new NewPrimitiveArrayNode(element, ConstantNode.forInt(virtual.entryCount(), fixed.graph()), true, false);
+                }
+            }
+            newObject.setProbability(fixed.probability());
+            obj.setMaterializedValue(newObject);
+            materializeEffects.addFixedNodeBefore(newObject, fixed);
+        } else {
+            // some entries are not default constants - do the materialization
+            MaterializeObjectNode materialize = new MaterializeObjectNode(virtual, obj.getLockCount());
+            ValueNode[] values = new ValueNode[obj.getEntries().length];
+            materialize.setProbability(fixed.probability());
+            obj.setMaterializedValue(materialize);
+            deferred.add(virtual);
+            for (int i = 0; i < fieldState.length; i++) {
+                ObjectState valueObj = getObjectState(fieldState[i]);
+                if (valueObj != null) {
+                    if (valueObj.isVirtual()) {
+                        materializeChangedBefore(fixed, valueObj.virtual, deferred, deferredStores, materializeEffects);
+                    }
+                    if (deferred.contains(valueObj.virtual)) {
+                        Kind fieldKind;
+                        CyclicMaterializeStoreNode store;
+                        if (virtual instanceof VirtualArrayNode) {
+                            store = new CyclicMaterializeStoreNode(materialize, valueObj.getMaterializedValue(), i);
+                            fieldKind = ((VirtualArrayNode) virtual).componentType().getKind();
+                        } else {
+                            VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual;
+                            store = new CyclicMaterializeStoreNode(materialize, valueObj.getMaterializedValue(), instanceObject.field(i));
+                            fieldKind = instanceObject.field(i).getType().getKind();
+                        }
+                        deferredStores.addFixedNodeBefore(store, fixed);
+                        values[i] = ConstantNode.defaultForKind(fieldKind, fixed.graph());
+                    } else {
+                        values[i] = valueObj.getMaterializedValue();
+                    }
+                } else {
+                    values[i] = fieldState[i];
+                }
+            }
+            deferred.remove(virtual);
+
+            materializeEffects.addMaterialization(materialize, fixed, values);
+        }
     }
 
     void addAndMarkAlias(VirtualObjectNode virtual, ValueNode node, NodeBitMap usages) {
diff -r 55afed7bc209 -r 6db6881c1270 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 Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Mon Nov 12 17:49:06 2012 +0100
@@ -27,8 +27,8 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
-import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.virtual.*;
+import com.oracle.graal.phases.common.*;
 import com.oracle.graal.virtual.nodes.*;
 
 public class GraphEffectList extends EffectList {
@@ -214,31 +214,13 @@
     }
 
     /**
-     * Virtualizes a monitor access by calling its {@link AccessMonitorNode#eliminate()} method.
-     *
-     * @param node The monitor access that should be virtualized.
-     */
-    public void eliminateMonitor(final AccessMonitorNode node) {
-        add(new Effect() {
-
-            @Override
-            public String name() {
-                return "eliminateMonitor";
-            }
-
-            @Override
-            public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
-                assert node.isAlive() && node.object().isAlive() && (node.object() instanceof VirtualObjectNode);
-                node.eliminate();
-            }
-        });
-    }
-
-    /**
-     * Replaces the given node at its usages without deleting it.
+     * 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 subsequent {@link DeadCodeEliminationPhase}
      *
      * @param node The node to be replaced.
-     * @param replacement The node that should replace the original value.
+     * @param replacement The node that should replace the original value. If the replacement is a non-connected
+     *            {@link FixedWithNextNode} it will be added to the control flow.
+     *
      */
     public void replaceAtUsages(final ValueNode node, final ValueNode replacement) {
         add(new Effect() {
@@ -251,7 +233,17 @@
             @Override
             public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
                 assert node.isAlive() && replacement.isAlive();
+                if (replacement instanceof FixedWithNextNode && ((FixedWithNextNode) replacement).next() == null) {
+                    assert node instanceof FixedNode;
+                    graph.addBeforeFixed((FixedNode) node, (FixedWithNextNode) replacement);
+                }
                 node.replaceAtUsages(replacement);
+                if (node instanceof FixedWithNextNode) {
+                    FixedNode next = ((FixedWithNextNode) node).next();
+                    ((FixedWithNextNode) node).setNext(null);
+                    node.replaceAtPredecessor(next);
+                    obsoleteNodes.add(node);
+                }
             }
         });
     }
@@ -263,7 +255,7 @@
      * @param oldInput The value to look for.
      * @param newInput The value to replace with.
      */
-    public void replaceFirstInput(final Node node, final ValueNode oldInput, final ValueNode newInput) {
+    public void replaceFirstInput(final Node node, final Node oldInput, final Node newInput) {
         add(new Effect() {
 
             @Override
@@ -283,4 +275,24 @@
             }
         });
     }
+
+    /**
+     * Performs a custom action.
+     *
+     * @param action The action that should be performed when the effects are applied.
+     */
+    public void customAction(final Runnable action) {
+        add(new Effect() {
+
+            @Override
+            public String name() {
+                return "customAction";
+            }
+
+            @Override
+            public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
+                action.run();
+            }
+        });
+    }
 }
diff -r 55afed7bc209 -r 6db6881c1270 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 Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java	Mon Nov 12 17:49:06 2012 +0100
@@ -100,12 +100,8 @@
         return lockCount;
     }
 
-    public void incLockCount() {
-        lockCount++;
-    }
-
-    public void decLockCount() {
-        lockCount--;
+    public void setLockCount(int lockCount) {
+        this.lockCount = lockCount;
     }
 
     @Override
diff -r 55afed7bc209 -r 6db6881c1270 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 Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Mon Nov 12 17:49:06 2012 +0100
@@ -157,10 +157,10 @@
         boolean success = true;
         for (Node node : obsoleteNodes) {
             if (flood.isMarked(node)) {
-                trace("offending node path:");
+                error("offending node path:");
                 Node current = node;
                 while (current != null) {
-                    trace(current.toString());
+                    error(current.toString());
                     current = path.get(current);
                     if (current != null && current instanceof FixedNode && !obsoleteNodes.contains(current)) {
                         break;
diff -r 55afed7bc209 -r 6db6881c1270 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 Nov 12 17:48:51 2012 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Mon Nov 12 17:49:06 2012 +0100
@@ -25,20 +25,19 @@
 import static com.oracle.graal.virtual.phases.ea.PartialEscapeAnalysisPhase.*;
 
 import java.util.*;
+import java.util.concurrent.*;
+import java.util.concurrent.atomic.*;
 
 import com.oracle.graal.api.meta.*;
-import com.oracle.graal.api.meta.ResolvedJavaType.Representation;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.PhiNode.PhiType;
 import com.oracle.graal.nodes.VirtualState.NodeClosure;
-import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.cfg.*;
-import com.oracle.graal.nodes.extended.*;
-import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.virtual.*;
+import com.oracle.graal.phases.*;
 import com.oracle.graal.phases.graph.*;
 import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
 import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo;
@@ -47,21 +46,36 @@
 
 class PartialEscapeClosure extends BlockIteratorClosure<BlockState> {
 
+    public static final ConcurrentHashMap<Class<? extends Node>, AtomicLong> materializeReasons = new ConcurrentHashMap<>();
+
+    static {
+        if (GraalOptions.EscapeAnalysisHistogram) {
+            Runtime.getRuntime().addShutdownHook(new Thread() {
+                @Override
+                public void run() {
+                    for (Map.Entry<Class<? extends Node>, AtomicLong> entry : materializeReasons.entrySet()) {
+                        System.out.println(entry.getKey() + ": " + entry.getValue());
+                    }
+                }
+            });
+        }
+    }
 
     private static final DebugMetric metricAllocationRemoved = Debug.metric("AllocationRemoved ");
 
+    private final NodeBitMap usages;
+    private final SchedulePhase schedule;
+
     private final GraphEffectList effects = new GraphEffectList();
     private final HashSet<VirtualObjectNode> reusedVirtualObjects = new HashSet<>();
     private int virtualIds = 0;
 
-    private final NodeBitMap usages;
-    private final SchedulePhase schedule;
-    private final MetaAccessProvider runtime;
+    private final VirtualizerToolImpl tool;
 
-    public PartialEscapeClosure(NodeBitMap usages, SchedulePhase schedule, MetaAccessProvider runtime) {
+    public PartialEscapeClosure(NodeBitMap usages, SchedulePhase schedule, MetaAccessProvider metaAccess) {
         this.usages = usages;
         this.schedule = schedule;
-        this.runtime = runtime;
+        tool = new VirtualizerToolImpl(effects, usages, metaAccess);
     }
 
     public GraphEffectList getEffects() {
@@ -118,265 +132,16 @@
         trace(")\n    end state: %s\n", state);
     }
 
+
     private void processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) {
-        boolean usageFound = false;
-        if (node instanceof PiNode || node instanceof ValueProxyNode) {
-            ValueNode value = node instanceof PiNode ? ((PiNode) node).object() : ((ValueProxyNode) node).value();
-            ObjectState obj = state.getObjectState(value);
-            if (obj != null) {
-                if (obj.isVirtual()) {
-                    state.addAndMarkAlias(obj.virtual, node, usages);
-                } else {
-                    effects.replaceFirstInput(node, value, obj.getMaterializedValue());
-                }
-                usageFound = true;
-            }
-        } else if (node instanceof CheckCastNode) {
-            CheckCastNode x = (CheckCastNode) node;
-            ObjectState obj = state.getObjectState(x.object());
-            if (obj != null) {
-                if (obj.isVirtual()) {
-                    if (obj.virtual.type().isSubtypeOf(x.type())) {
-                        state.addAndMarkAlias(obj.virtual, x, usages);
-                        effects.deleteFixedNode(x);
-                    } else {
-                        replaceWithMaterialized(x.object(), x, state, obj);
-                    }
-                } else {
-                    effects.replaceFirstInput(x, x.object(), obj.getMaterializedValue());
-                }
-                usageFound = true;
-            }
-        } else if (node instanceof IsNullNode) {
-            IsNullNode x = (IsNullNode) node;
-            if (state.getObjectState(x.object()) != null) {
-                replaceAtUsages(state, x, ConstantNode.forBoolean(false, node.graph()));
-                usageFound = true;
-            }
-        } else if (node instanceof AccessMonitorNode) {
-            AccessMonitorNode x = (AccessMonitorNode) node;
-            ObjectState obj = state.getObjectState(x.object());
-            if (obj != null) {
-                Debug.log("monitor operation %s on %s\n", x, obj.virtual);
-                if (node instanceof MonitorEnterNode) {
-                    obj.incLockCount();
-                } else {
-                    assert node instanceof MonitorExitNode;
-                    obj.decLockCount();
-                }
-                if (obj.isVirtual()) {
-                    effects.replaceFirstInput(node, x.object(), obj.virtual);
-                    effects.eliminateMonitor(x);
-                } else {
-                    effects.replaceFirstInput(node, x.object(), obj.getMaterializedValue());
-                }
-                usageFound = true;
-            }
-        } else if (node instanceof CyclicMaterializeStoreNode) {
-            CyclicMaterializeStoreNode x = (CyclicMaterializeStoreNode) node;
-            ObjectState obj = state.getObjectState(x.object());
-            if (obj != null) {
-                if (obj.virtual instanceof VirtualArrayNode) {
-                    obj.setEntry(x.targetIndex(), x.value());
-                } else {
-                    VirtualInstanceNode instance = (VirtualInstanceNode) obj.virtual;
-                    obj.setEntry(instance.fieldIndex(x.targetField()), x.value());
-                }
-                effects.deleteFixedNode(x);
-                usageFound = true;
-            }
-        } else if (node instanceof LoadFieldNode) {
-            LoadFieldNode x = (LoadFieldNode) node;
-            ObjectState obj = state.getObjectState(x.object());
-            if (obj != null) {
-                VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual;
-                int fieldIndex = virtual.fieldIndex(x.field());
-                if (fieldIndex == -1) {
-                    // the field does not exist in the virtual object
-                    ensureMaterialized(state, obj, x);
-                }
-                if (obj.isVirtual()) {
-                    ValueNode result = obj.getEntry(fieldIndex);
-                    ObjectState resultObj = state.getObjectState(result);
-                    if (resultObj != null) {
-                        state.addAndMarkAlias(resultObj.virtual, x, usages);
-                    } else {
-                        replaceAtUsages(state, x, result);
-                    }
-                    effects.deleteFixedNode(x);
-                } else {
-                    effects.replaceFirstInput(x, x.object(), obj.getMaterializedValue());
-                }
-                usageFound = true;
-            }
-        } else if (node instanceof StoreFieldNode) {
-            StoreFieldNode x = (StoreFieldNode) node;
-            ValueNode object = x.object();
-            ValueNode value = x.value();
-            ObjectState obj = state.getObjectState(object);
-            if (obj != null) {
-                VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual;
-                int fieldIndex = virtual.fieldIndex(x.field());
-                if (fieldIndex == -1) {
-                    // the field does not exist in the virtual object
-                    ensureMaterialized(state, obj, x);
-                }
-                if (obj.isVirtual()) {
-                    obj.setEntry(fieldIndex, state.getScalarAlias(value));
-                    effects.deleteFixedNode(x);
-                } else {
-                    effects.replaceFirstInput(x, object, obj.getMaterializedValue());
-                    ObjectState valueObj = state.getObjectState(value);
-                    if (valueObj != null) {
-                        replaceWithMaterialized(value, x, state, valueObj);
-                    }
-                }
-                usageFound = true;
-            } else {
-                ObjectState valueObj = state.getObjectState(value);
-                if (valueObj != null) {
-                    replaceWithMaterialized(value, x, state, valueObj);
-                    usageFound = true;
-                }
-            }
-        } else if (node instanceof LoadIndexedNode) {
-            LoadIndexedNode x = (LoadIndexedNode) node;
-            ValueNode array = x.array();
-            ObjectState arrayObj = state.getObjectState(array);
-            if (arrayObj != null) {
-                if (arrayObj.isVirtual()) {
-                    ValueNode indexValue = state.getScalarAlias(x.index());
-                    int index = indexValue.isConstant() ? indexValue.asConstant().asInt() : -1;
-                    if (index < 0 || index >= arrayObj.getEntries().length) {
-                        // out of bounds or not constant
-                        replaceWithMaterialized(array, x, state, arrayObj);
-                    } else {
-                        ValueNode result = arrayObj.getEntry(index);
-                        ObjectState resultObj = state.getObjectState(result);
-                        if (resultObj != null) {
-                            state.addAndMarkAlias(resultObj.virtual, x, usages);
-                        } else {
-                            replaceAtUsages(state, x, result);
-                        }
-                        effects.deleteFixedNode(x);
-                    }
-                } else {
-                    effects.replaceFirstInput(x, array, arrayObj.getMaterializedValue());
-                }
-                usageFound = true;
-            }
-        } else if (node instanceof StoreIndexedNode) {
-            StoreIndexedNode x = (StoreIndexedNode) node;
-            ValueNode array = x.array();
-            ValueNode value = x.value();
-            ObjectState arrayObj = state.getObjectState(array);
-            ObjectState valueObj = state.getObjectState(value);
-
-            if (arrayObj != null) {
-                if (arrayObj.isVirtual()) {
-                    ValueNode indexValue = state.getScalarAlias(x.index());
-                    int index = indexValue.isConstant() ? indexValue.asConstant().asInt() : -1;
-                    if (index < 0 || index >= arrayObj.getEntries().length) {
-                        // out of bounds or not constant
-                        replaceWithMaterialized(array, x, state, arrayObj);
-                        if (valueObj != null) {
-                            replaceWithMaterialized(value, x, state, valueObj);
-                        }
-                    } else {
-                        arrayObj.setEntry(index, state.getScalarAlias(value));
-                        effects.deleteFixedNode(x);
-                    }
-                } else {
-                    effects.replaceFirstInput(x, array, arrayObj.getMaterializedValue());
-                    if (valueObj != null) {
-                        replaceWithMaterialized(value, x, state, valueObj);
-                    }
-                }
-                usageFound = true;
-            } else {
-                if (valueObj != null) {
-                    replaceWithMaterialized(value, x, state, valueObj);
-                    usageFound = true;
-                }
-            }
-        } else if (node instanceof RegisterFinalizerNode) {
-            RegisterFinalizerNode x = (RegisterFinalizerNode) node;
-            ObjectState obj = state.getObjectState(x.object());
-            if (obj != null) {
-                replaceWithMaterialized(x.object(), x, state, obj);
-                usageFound = true;
-            }
-        } else if (node instanceof ArrayLengthNode) {
-            ArrayLengthNode x = (ArrayLengthNode) node;
-            ObjectState obj = state.getObjectState(x.array());
-            if (obj != null) {
-                replaceAtUsages(state, x, ConstantNode.forInt(((VirtualArrayNode) obj.virtual).entryCount(), node.graph()));
-                effects.deleteFixedNode(x);
-                usageFound = true;
-            }
-        } else if (node instanceof LoadHubNode) {
-            LoadHubNode x = (LoadHubNode) node;
-            ObjectState obj = state.getObjectState(x.object());
-            if (obj != null) {
-                replaceAtUsages(state, x, ConstantNode.forConstant(obj.virtual.type().getEncoding(Representation.ObjectHub), runtime, node.graph()));
-                effects.deleteFixedNode(x);
-                usageFound = true;
-            }
-        } else if (node instanceof ReturnNode) {
-            ReturnNode x = (ReturnNode) node;
-            ObjectState obj = state.getObjectState(x.result());
-            if (obj != null) {
-                replaceWithMaterialized(x.result(), x, state, obj);
-                usageFound = true;
-            }
-        } else if (node instanceof MethodCallTargetNode) {
-            for (ValueNode argument : ((MethodCallTargetNode) node).arguments()) {
-                ObjectState obj = state.getObjectState(argument);
-                if (obj != null) {
-                    replaceWithMaterialized(argument, node, insertBefore, state, obj);
-                    usageFound = true;
-                }
-            }
-        } else if (node instanceof ObjectEqualsNode) {
-            ObjectEqualsNode x = (ObjectEqualsNode) node;
-            ObjectState xObj = state.getObjectState(x.x());
-            ObjectState yObj = state.getObjectState(x.y());
-            boolean xVirtual = xObj != null && xObj.isVirtual();
-            boolean yVirtual = yObj != null && yObj.isVirtual();
-
-            if (xVirtual ^ yVirtual) {
-                // one of them is virtual: they can never be the same objects
-                replaceAtUsages(state, x, ConstantNode.forBoolean(false, node.graph()));
-                usageFound = true;
-            } else if (xVirtual && yVirtual) {
-                // both are virtual: check if they refer to the same object
-                replaceAtUsages(state, x, ConstantNode.forBoolean(xObj == yObj, node.graph()));
-                usageFound = true;
-            } else {
-                if (xObj != null || yObj != null) {
-                    if (xObj != null) {
-                        assert !xObj.isVirtual();
-                        effects.replaceFirstInput(x, x.x(), xObj.getMaterializedValue());
-                    }
-                    if (yObj != null) {
-                        assert !yObj.isVirtual();
-                        effects.replaceFirstInput(x, x.y(), yObj.getMaterializedValue());
-                    }
-                    usageFound = true;
-                }
-            }
-        } else if (node instanceof MergeNode) {
-            usageFound = true;
-        } else if (node instanceof UnsafeLoadNode || node instanceof UnsafeStoreNode || node instanceof CompareAndSwapNode || node instanceof SafeReadNode) {
-            for (ValueNode input : node.inputs().filter(ValueNode.class)) {
-                ObjectState obj = state.getObjectState(input);
-                if (obj != null) {
-                    replaceWithMaterialized(input, node, insertBefore, state, obj);
-                    usageFound = true;
-                }
-            }
+        tool.reset(state, node);
+        if (node instanceof Virtualizable) {
+            ((Virtualizable) node).virtualize(tool);
         }
-        if (node.isAlive() && node instanceof StateSplit) {
+        if (tool.isDeleted()) {
+            return;
+        }
+        if (node instanceof StateSplit) {
             StateSplit split = (StateSplit) node;
             FrameState stateAfter = split.stateAfter();
             if (stateAfter != null) {
@@ -449,25 +214,27 @@
                     effects.addVirtualMapping(stateAfter, v, reusedVirtualObjects);
                 }
             }
-            usageFound = true;
+        }
+        if (tool.isCustomAction()) {
+            return;
         }
-        if (!usageFound) {
-            for (ValueNode input : node.inputs().filter(ValueNode.class)) {
-                ObjectState obj = state.getObjectState(input);
-                if (obj != null) {
-                    replaceWithMaterialized(input, node, insertBefore, state, obj);
-                    usageFound = true;
+        for (ValueNode input : node.inputs().filter(ValueNode.class)) {
+            ObjectState obj = state.getObjectState(input);
+            if (obj != null) {
+                trace("replacing input %s at %s: %s", input, node, obj);
+                if (GraalOptions.EscapeAnalysisHistogram && obj.isVirtual()) {
+                    AtomicLong counter = materializeReasons.get(node.getClass());
+                    if (counter == null) {
+                        counter = new AtomicLong();
+                        materializeReasons.put(node.getClass(), counter);
+                    }
+                    counter.incrementAndGet();
                 }
+                replaceWithMaterialized(input, node, insertBefore, state, obj);
             }
-            Debug.log("unexpected usage of %s: %s\n", node, node.inputs().snapshot());
         }
     }
 
-    private void replaceAtUsages(final BlockState state, ValueNode x, ValueNode value) {
-        effects.replaceAtUsages(x, value);
-        state.addScalarAlias(x, value);
-    }
-
     private void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore) {
         assert obj != null;
         if (obj.isVirtual()) {
@@ -476,11 +243,6 @@
         assert !obj.isVirtual();
     }
 
-    private void replaceWithMaterialized(ValueNode value, FixedNode usage, BlockState state, ObjectState obj) {
-        ensureMaterialized(state, obj, usage);
-        effects.replaceFirstInput(usage, value, obj.getMaterializedValue());
-    }
-
     private void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj) {
         ensureMaterialized(state, obj, materializeBefore);
         effects.replaceFirstInput(usage, value, obj.getMaterializedValue());
diff -r 55afed7bc209 -r 6db6881c1270 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java	Mon Nov 12 17:49:06 2012 +0100
@@ -0,0 +1,157 @@
+/*
+ * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.virtual.phases.ea;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.virtual.*;
+
+class VirtualizerToolImpl implements VirtualizerTool {
+
+    private final GraphEffectList effects;
+    private final NodeBitMap usages;
+    private final MetaAccessProvider metaAccess;
+
+    VirtualizerToolImpl(GraphEffectList effects, NodeBitMap usages, MetaAccessProvider metaAccess) {
+        this.effects = effects;
+        this.usages = usages;
+        this.metaAccess = metaAccess;
+    }
+
+    private boolean deleted;
+    private boolean customAction;
+    private BlockState state;
+    private ValueNode current;
+
+    @Override
+    public MetaAccessProvider getMetaAccessProvider() {
+        return metaAccess;
+    }
+
+    public void reset(BlockState newState, ValueNode newCurrent) {
+        deleted = false;
+        customAction = false;
+        this.state = newState;
+        this.current = newCurrent;
+    }
+
+    public boolean isDeleted() {
+        return deleted;
+    }
+
+    public boolean isCustomAction() {
+        return customAction;
+    }
+
+    @Override
+    public VirtualObjectNode getVirtualState(ValueNode value) {
+        ObjectState obj = state.getObjectState(value);
+        return obj != null && obj.isVirtual() ? obj.virtual : null;
+    }
+
+    @Override
+    public ValueNode getVirtualEntry(VirtualObjectNode virtual, int index) {
+        ObjectState obj = state.getObjectState(virtual);
+        assert obj != null && obj.isVirtual() : "not virtual: " + obj;
+        ValueNode result = obj.getEntry(index);
+        ValueNode materialized = getMaterializedValue(result);
+        return materialized != null ? materialized : result;
+    }
+
+    @Override
+    public void setVirtualEntry(VirtualObjectNode virtual, int index, ValueNode value) {
+        ObjectState obj = state.getObjectState(virtual);
+        assert obj != null && obj.isVirtual() : "not virtual: " + obj;
+        if (getVirtualState(value) == null) {
+            ValueNode materialized = getMaterializedValue(value);
+            if (materialized != null) {
+                obj.setEntry(index, materialized);
+            } else {
+                obj.setEntry(index, getReplacedValue(value));
+            }
+        } else {
+            obj.setEntry(index, value);
+        }
+    }
+
+    @Override
+    public int getVirtualLockCount(VirtualObjectNode virtual) {
+        ObjectState obj = state.getObjectState(virtual);
+        assert obj != null && obj.isVirtual() : "not virtual: " + obj;
+        return obj.getLockCount();
+    }
+
+    @Override
+    public void setVirtualLockCount(VirtualObjectNode virtual, int lockCount) {
+        ObjectState obj = state.getObjectState(virtual);
+        assert obj != null && obj.isVirtual() : "not virtual: " + obj;
+        obj.setLockCount(lockCount);
+    }
+
+    @Override
+    public ValueNode getMaterializedValue(ValueNode value) {
+        ObjectState obj = state.getObjectState(value);
+        return obj != null && !obj.isVirtual() ? obj.getMaterializedValue() : null;
+    }
+
+    @Override
+    public ValueNode getReplacedValue(ValueNode original) {
+        return state.getScalarAlias(original);
+    }
+
+    @Override
+    public void replaceWithVirtual(VirtualObjectNode virtual) {
+        state.addAndMarkAlias(virtual, current, usages);
+        if (current instanceof FixedWithNextNode) {
+            effects.deleteFixedNode((FixedWithNextNode) current);
+        }
+        deleted = true;
+    }
+
+    @Override
+    public void replaceWithValue(ValueNode replacement) {
+        effects.replaceAtUsages(current, state.getScalarAlias(replacement));
+        state.addScalarAlias(current, replacement);
+        deleted = true;
+    }
+
+    @Override
+    public void delete() {
+        assert current instanceof FixedWithNextNode;
+        effects.deleteFixedNode((FixedWithNextNode) current);
+        deleted = true;
+    }
+
+    @Override
+    public void replaceFirstInput(Node oldInput, Node replacement) {
+        effects.replaceFirstInput(current, oldInput, replacement);
+    }
+
+    @Override
+    public void customAction(Runnable action) {
+        effects.customAction(action);
+        customAction = true;
+    }
+}