--- a/graal/com.oracle.graal.api.replacements/src/com/oracle/graal/api/replacements/MethodSubstitution.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.api.replacements/src/com/oracle/graal/api/replacements/MethodSubstitution.java	Tue Apr 09 10:48:14 2013 +0200
@@ -56,6 +56,12 @@
     String signature() default "";
 
     /**
+     * Determines if this method should be substituted in all cases, even if inlining thinks it is
+     * not important.
+     */
+    boolean isForcedInlining() default false;
+
+    /**
      * Determines if the substitution is for a method that may not be part of the runtime. For
      * example, a method introduced in a later JDK version. Substitutions for such methods are
      * omitted if the original method cannot be found.

--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/BoxingEliminationTest.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/BoxingEliminationTest.java	Tue Apr 09 10:48:14 2013 +0200
@@ -22,17 +22,16 @@
  */
 package com.oracle.graal.compiler.test;
 
-import java.util.*;
-
 import org.junit.*;
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.debug.*;
+import com.oracle.graal.loop.phases.*;
 import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.phases.*;
-import com.oracle.graal.phases.PhasePlan.*;
 import com.oracle.graal.phases.common.*;
+import com.oracle.graal.virtual.nodes.*;
+import com.oracle.graal.virtual.phases.ea.*;
 
 /**
  * In the following tests, the usages of local variable "a" are replaced with the integer constant
@@ -57,17 +56,25 @@
         return 1;
     }
 
-    public static Object boxedObject() {
+    public static Object boxedObjectShort() {
         return (short) 1;
     }
 
+    public static Object boxedObjectInteger() {
+        return (int) 1;
+    }
+
+    public static Integer boxedInteger() {
+        return 2;
+    }
+
     public static Short constantBoxedShort() {
         return s;
     }
 
     @Test
     public void test1() {
-        test("test1Snippet", "referenceSnippet1");
+        compareGraphs("test1Snippet", "referenceSnippet1");
     }
 
     @SuppressWarnings("all")
@@ -77,17 +84,17 @@
 
     @Test
     public void test2() {
-        test("test2Snippet", "referenceSnippet1");
+        compareGraphs("test2Snippet", "referenceSnippet1");
     }
 
     @SuppressWarnings("all")
     public static short test2Snippet() {
-        return (Short) boxedObject();
+        return (Short) boxedObjectShort();
     }
 
     @Test
     public void test3() {
-        test("test3Snippet", "referenceSnippet1");
+        compareGraphs("test3Snippet", "referenceSnippet1");
     }
 
     @SuppressWarnings("all")
@@ -101,7 +108,7 @@
 
     @Test
     public void test4() {
-        test("test4Snippet", "referenceSnippet2");
+        compareGraphs("test4Snippet", "referenceSnippet2");
     }
 
     @SuppressWarnings("all")
@@ -109,33 +116,200 @@
         return constantBoxedShort();
     }
 
-    private void test(final String snippet, final String referenceSnippet) {
-        Debug.scope("BoxingEliminationTest", new DebugDumpScope(snippet), new Runnable() {
+    @Test
+    public void testLoop() {
+        compareGraphs("testLoopSnippet", "referenceLoopSnippet", false, true);
+    }
+
+    public static int testLoopSnippet(int n, int a) {
+        Integer sum = a;
+        for (Integer i = 0; i < n; i++) {
+            sum += i;
+        }
+        return sum;
+    }
+
+    public static int referenceLoopSnippet(int n, int a) {
+        int sum = a;
+        for (int i = 0; i < n; i++) {
+            sum += i;
+        }
+        return sum;
+    }
+
+    @Test
+    public void testLoop2() {
+        compareGraphs("testLoop2Snippet", "referenceLoop2Snippet", true, true);
+    }
+
+    public static int testLoop2Snippet(int n, Integer a) {
+        Integer sum = a;
+        for (Integer i = 0; i < n; i++) {
+            sum += i;
+        }
+        return sum;
+    }
+
+    public static int referenceLoop2Snippet(int n, Integer a) {
+        Integer sum0;
+        if (n <= 0) {
+            sum0 = a;
+        } else {
+            int sum = a;
+            for (int i = 0; i < n; i++) {
+                sum += i;
+            }
+            sum0 = sum;
+        }
+        return sum0;
+    }
+
+    public static int referenceIfSnippet(int a) {
+        int result;
+        if (a < 0) {
+            result = 2;
+        } else {
+            result = 1;
+        }
+        return result;
+    }
+
+    @Test
+    public void testIf() {
+        compareGraphs("testIfSnippet", "referenceIfSnippet");
+    }
+
+    public static int testIfSnippet(int a) {
+        Integer result;
+        if (a < 0) {
+            result = boxedInteger();
+        } else {
+            result = (Integer) boxedObjectInteger();
+        }
+        return result;
+    }
+
+    private StructuredGraph graph;
+
+    public static Integer materializeReferenceSnippet(int a) {
+        return Integer.valueOf(a);
+    }
+
+    public static Integer materializeTest1Snippet(int a) {
+        Integer v = a;
+
+        if (v == a) {
+            return v;
+        } else {
+            return null;
+        }
+    }
+
+    @Test
+    public void materializeTest1() {
+        test("materializeTest1Snippet", 1);
+    }
+
+    public static int intTest1Snippet() {
+        return Integer.valueOf(1);
+    }
+
+    @Test
+    public void intTest1() {
+        ValueNode result = getResult("intTest1Snippet");
+        Assert.assertTrue(result.isConstant());
+        Assert.assertEquals(1, result.asConstant().asInt());
+    }
+
+    public static int mergeTest1Snippet(boolean d, int a, int b) {
+        Integer v;
+        if (d) {
+            v = a;
+        } else {
+            v = b;
+        }
+        return v;
+    }
+
+    @Test
+    public void mergeTest1() {
+        processMethod("mergeTest1Snippet");
+    }
+
+    public static boolean equalsTest1Snippet(int x, int y) {
+        Integer a = x;
+        Integer b = y;
+        return a == b;
+    }
+
+    @Test
+    public void equalsTest1() {
+        processMethod("equalsTest1Snippet");
+    }
+
+    public static int loopTest1Snippet(int n, int v) {
+        Integer sum = 0;
+        for (int i = 0; i < n; i++) {
+            sum += v;
+        }
+        return sum;
+    }
+
+    @Test
+    public void loopTest1() {
+        processMethod("loopTest1Snippet");
+
+    }
+
+    final ValueNode getResult(String snippet) {
+        processMethod(snippet);
+        assertEquals(1, graph.getNodes(ReturnNode.class).count());
+        return graph.getNodes(ReturnNode.class).first().result();
+    }
+
+    private void processMethod(final String snippet) {
+        graph = parse(snippet);
+        new ComputeProbabilityPhase().apply(graph);
+        Assumptions assumptions = new Assumptions(false);
+        new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
+        new PartialEscapeAnalysisPhase(runtime(), assumptions, false, false).apply(graph);
+        new CullFrameStatesPhase().apply(graph);
+    }
+
+    private void compareGraphs(final String snippet, final String referenceSnippet) {
+        compareGraphs(snippet, referenceSnippet, false, false);
+    }
+
+    private void compareGraphs(final String snippet, final String referenceSnippet, final boolean loopPeeling, final boolean excludeVirtual) {
+        Debug.scope("BoxingEliminationTest " + snippet, new DebugDumpScope(snippet), new Runnable() {
 
             @Override
             public void run() {
-                StructuredGraph graph = parse(snippet);
-                BoxingMethodPool pool = new BoxingMethodPool(runtime());
-                IdentifyBoxingPhase identifyBoxingPhase = new IdentifyBoxingPhase(pool);
-                PhasePlan phasePlan = getDefaultPhasePlan();
-                phasePlan.addPhase(PhasePosition.AFTER_PARSING, identifyBoxingPhase);
-                identifyBoxingPhase.apply(graph);
-                Map<Invoke, Double> hints = new HashMap<>();
-                for (Invoke invoke : graph.getInvokes()) {
-                    hints.put(invoke, 1000d);
+                graph = parse(snippet);
+
+                new ComputeProbabilityPhase().apply(graph);
+                Assumptions assumptions = new Assumptions(false);
+                new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
+                if (loopPeeling) {
+                    new LoopTransformHighPhase().apply(graph);
+                }
+                new DeadCodeEliminationPhase().apply(graph);
+                new CanonicalizerPhase(runtime(), assumptions).apply(graph);
+                new PartialEscapeAnalysisPhase(runtime(), assumptions, false, false).apply(graph);
+
+                for (MaterializeObjectNode materialize : graph.getNodes(MaterializeObjectNode.class)) {
+                    materialize.getVirtualObject().materializeAt(materialize, materialize.getValues(), false, materialize.getLockCount());
                 }
 
-                Assumptions assumptions = new Assumptions(false);
-                new InliningPhase(runtime(), hints, replacements, assumptions, null, phasePlan, OptimisticOptimizations.ALL).apply(graph);
+                new CullFrameStatesPhase().apply(graph);
+                new DeadCodeEliminationPhase().apply(graph);
                 new CanonicalizerPhase(runtime(), assumptions).apply(graph);
-                Debug.dump(graph, "Graph");
-                new BoxingEliminationPhase(runtime()).apply(graph);
-                Debug.dump(graph, "Graph");
-                new ExpandBoxingNodesPhase(pool).apply(graph);
-                new CanonicalizerPhase(runtime(), assumptions).apply(graph);
-                new DeadCodeEliminationPhase().apply(graph);
+
                 StructuredGraph referenceGraph = parse(referenceSnippet);
-                assertEquals(referenceGraph, graph);
+                new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(referenceGraph);
+                new DeadCodeEliminationPhase().apply(referenceGraph);
+                new CanonicalizerPhase(runtime(), assumptions).apply(referenceGraph);
+                assertEquals(referenceGraph, graph, excludeVirtual);
             }
         });
     }

--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Tue Apr 09 10:48:14 2013 +0200
@@ -40,6 +40,7 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.virtual.*;
 import com.oracle.graal.phases.*;
 import com.oracle.graal.phases.PhasePlan.PhasePosition;
 import com.oracle.graal.phases.schedule.*;
@@ -83,11 +84,15 @@
     }
 
     protected void assertEquals(StructuredGraph expected, StructuredGraph graph) {
-        String expectedString = getCanonicalGraphString(expected);
-        String actualString = getCanonicalGraphString(graph);
+        assertEquals(expected, graph, false);
+    }
+
+    protected void assertEquals(StructuredGraph expected, StructuredGraph graph, boolean excludeVirtual) {
+        String expectedString = getCanonicalGraphString(expected, excludeVirtual);
+        String actualString = getCanonicalGraphString(graph, excludeVirtual);
         String mismatchString = "mismatch in graphs:\n========= expected =========\n" + expectedString + "\n\n========= actual =========\n" + actualString;
 
-        if (expected.getNodeCount() != graph.getNodeCount()) {
+        if (!excludeVirtual && expected.getNodeCount() != graph.getNodeCount()) {
             Debug.dump(expected, "Node count not matching - expected");
             Debug.dump(graph, "Node count not matching - actual");
             Assert.fail("Graphs do not have the same number of nodes: " + expected.getNodeCount() + " vs. " + graph.getNodeCount() + "\n" + mismatchString);
@@ -100,7 +105,7 @@
     }
 
     protected void assertConstantReturn(StructuredGraph graph, int value) {
-        String graphString = getCanonicalGraphString(graph);
+        String graphString = getCanonicalGraphString(graph, false);
         Assert.assertEquals("unexpected number of ReturnNodes: " + graphString, graph.getNodes(ReturnNode.class).count(), 1);
         ValueNode result = graph.getNodes(ReturnNode.class).first().result();
         Assert.assertTrue("unexpected ReturnNode result node: " + graphString, result.isConstant());
@@ -108,7 +113,7 @@
         Assert.assertEquals("unexpected ReturnNode result: " + graphString, result.asConstant().asInt(), value);
     }
 
-    protected static String getCanonicalGraphString(StructuredGraph graph) {
+    protected static String getCanonicalGraphString(StructuredGraph graph, boolean excludeVirtual) {
         SchedulePhase schedule = new SchedulePhase();
         schedule.apply(graph);
 
@@ -127,15 +132,17 @@
             }
             result.append("\n");
             for (Node node : schedule.getBlockToNodesMap().get(block)) {
-                int id;
-                if (canonicalId.get(node) != null) {
-                    id = canonicalId.get(node);
-                } else {
-                    id = nextId++;
-                    canonicalId.set(node, id);
+                if (!excludeVirtual || !(node instanceof VirtualObjectNode || node instanceof ProxyNode)) {
+                    int id;
+                    if (canonicalId.get(node) != null) {
+                        id = canonicalId.get(node);
+                    } else {
+                        id = nextId++;
+                        canonicalId.set(node, id);
+                    }
+                    String name = node instanceof ConstantNode ? node.toString(Verbosity.Name) : node.getClass().getSimpleName();
+                    result.append("  " + id + "|" + name + (excludeVirtual ? "\n" : "    (" + node.usages().count() + ")\n"));
                 }
-                String name = node instanceof ConstantNode ? node.toString(Verbosity.Name) : node.getClass().getSimpleName();
-                result.append("  " + id + "|" + name + "    (" + node.usages().count() + ")\n");
             }
         }
         return result.toString();
@@ -400,7 +407,8 @@
                 GraphBuilderPhase graphBuilderPhase = new GraphBuilderPhase(runtime, GraphBuilderConfiguration.getDefault(), OptimisticOptimizations.ALL);
                 phasePlan.addPhase(PhasePosition.AFTER_PARSING, graphBuilderPhase);
                 editPhasePlan(method, graph, phasePlan);
-                CompilationResult compResult = GraalCompiler.compileMethod(runtime(), replacements, backend, runtime().getTarget(), method, graph, null, phasePlan, OptimisticOptimizations.ALL, new SpeculationLog());
+                CompilationResult compResult = GraalCompiler.compileMethod(runtime(), replacements, backend, runtime().getTarget(), method, graph, null, phasePlan, OptimisticOptimizations.ALL,
+                                new SpeculationLog());
                 if (printCompilation) {
                     TTY.println(String.format("@%-6d Graal %-70s %-45s %-50s | %4dms %5dB", id, "", "", "", System.currentTimeMillis() - start, compResult.getTargetCodeSize()));
                 }

--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/IfBoxingEliminationTest.java	Tue Apr 09 10:11:52 2013 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,111 +0,0 @@
-/*
- * 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.compiler.test;
-
-import java.util.*;
-
-import org.junit.*;
-
-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.phases.*;
-import com.oracle.graal.phases.PhasePlan.PhasePosition;
-import com.oracle.graal.phases.common.*;
-
-public class IfBoxingEliminationTest extends GraalCompilerTest {
-
-    private static final String REFERENCE_SNIPPET = "referenceSnippet";
-
-    public static int referenceSnippet(int a) {
-        int result;
-        if (a < 0) {
-            result = 1;
-        } else {
-            result = 2;
-        }
-        return result;
-    }
-
-    public static Integer boxedInteger() {
-        return 1;
-    }
-
-    public static Object boxedObject() {
-        return 2;
-    }
-
-    @Test
-    public void test1() {
-        test("test1Snippet");
-    }
-
-    public static int test1Snippet(int a) {
-        Integer result;
-        if (a < 0) {
-            result = boxedInteger();
-        } else {
-            result = (Integer) boxedObject();
-        }
-        return result;
-    }
-
-    private void test(final String snippet) {
-        Debug.scope("IfBoxingEliminationTest", new DebugDumpScope(snippet), new Runnable() {
-
-            @Override
-            public void run() {
-                StructuredGraph graph = parse(snippet);
-                BoxingMethodPool pool = new BoxingMethodPool(runtime());
-                IdentifyBoxingPhase identifyBoxingPhase = new IdentifyBoxingPhase(pool);
-                PhasePlan phasePlan = getDefaultPhasePlan();
-                phasePlan.addPhase(PhasePosition.AFTER_PARSING, identifyBoxingPhase);
-                phasePlan.addPhase(PhasePosition.AFTER_PARSING, new PhiStampPhase());
-                identifyBoxingPhase.apply(graph);
-                Map<Invoke, Double> hints = new HashMap<>();
-                for (Invoke invoke : graph.getInvokes()) {
-                    hints.put(invoke, 1000d);
-                }
-
-                Assumptions assumptions = new Assumptions(false);
-                new InliningPhase(runtime(), hints, replacements, assumptions, null, phasePlan, OptimisticOptimizations.ALL).apply(graph);
-                new CanonicalizerPhase(runtime(), assumptions).apply(graph);
-                new PhiStampPhase().apply(graph);
-                new CanonicalizerPhase(runtime(), assumptions).apply(graph);
-                Debug.dump(graph, "Graph");
-                new BoxingEliminationPhase(runtime()).apply(graph);
-                Debug.dump(graph, "Graph");
-                new ExpandBoxingNodesPhase(pool).apply(graph);
-                new CanonicalizerPhase(runtime(), assumptions).apply(graph);
-                new CanonicalizerPhase(runtime(), assumptions).apply(graph);
-                new DeadCodeEliminationPhase().apply(graph);
-                StructuredGraph referenceGraph = parse(REFERENCE_SNIPPET);
-                new CanonicalizerPhase(runtime(), assumptions).apply(referenceGraph);
-                new DeadCodeEliminationPhase().apply(referenceGraph);
-
-                assertEquals(referenceGraph, graph);
-            }
-        });
-    }
-}

--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java	Tue Apr 09 10:48:14 2013 +0200
@@ -22,7 +22,8 @@
  */
 package com.oracle.graal.compiler.test.ea;
 
-import junit.framework.*;
+import java.util.concurrent.*;
+
 import junit.framework.Assert;
 
 import org.junit.Test;
@@ -30,6 +31,8 @@
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.test.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.java.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.phases.*;
@@ -83,8 +86,8 @@
 
     public static int testMonitorSnippet() {
         Integer x = new Integer(0);
-        Integer[] y = new Integer[0];
-        Integer[] z = new Integer[1];
+        Double y = new Double(0);
+        Object z = new Object();
         synchronized (x) {
             synchronized (y) {
                 synchronized (z) {
@@ -106,8 +109,8 @@
      */
     public static int testMonitor2Snippet() {
         Integer x = new Integer(0);
-        Integer[] y = new Integer[0];
-        Integer[] z = new Integer[1];
+        Double y = new Double(0);
+        Object z = new Object();
         synchronized (x) {
             synchronized (y) {
                 synchronized (z) {
@@ -161,6 +164,20 @@
         return obj.x;
     }
 
+    @Test
+    public void testModifyingLoop() {
+        testEscapeAnalysis("testModifyingLoopSnippet", Constant.forInt(1), false);
+    }
+
+    public int testModifyingLoopSnippet(int a) {
+        TestObject obj = new TestObject(1, 2);
+        for (int i = 0; i < a; i++) {
+            obj.x = 3;
+            notInlineable();
+        }
+        return obj.x <= 3 ? 1 : 0;
+    }
+
     public static class TestObject2 {
 
         Object o;
@@ -192,28 +209,32 @@
         return obj2.o instanceof TestObject2;
     }
 
-    private ReturnNode testEscapeAnalysis(String snippet, Constant expectedConstantResult, boolean iterativeEscapeAnalysis) {
-        StructuredGraph graph = parse(snippet);
-        try {
-            for (Invoke n : graph.getInvokes()) {
-                n.setInliningRelevance(1);
-            }
+    private ReturnNode testEscapeAnalysis(String snippet, final Constant expectedConstantResult, final boolean iterativeEscapeAnalysis) {
+        ResolvedJavaMethod method = runtime.lookupJavaMethod(getMethod(snippet));
+        final StructuredGraph graph = new StructuredGraph(method);
+
+        return Debug.scope("GraalCompiler", new Object[]{graph, method, runtime}, new Callable<ReturnNode>() {
+
+            public ReturnNode call() {
+                new GraphBuilderPhase(runtime, GraphBuilderConfiguration.getEagerDefault(), OptimisticOptimizations.ALL).apply(graph);
+                for (Invoke n : graph.getInvokes()) {
+                    n.setInliningRelevance(1);
+                }
 
-            Assumptions assumptions = new Assumptions(false);
-            new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
-            new DeadCodeEliminationPhase().apply(graph);
-            new PartialEscapeAnalysisPhase(runtime(), assumptions, iterativeEscapeAnalysis, false).apply(graph);
-            Assert.assertEquals(1, graph.getNodes(ReturnNode.class).count());
-            ReturnNode returnNode = graph.getNodes(ReturnNode.class).first();
-            if (expectedConstantResult != null) {
-                Assert.assertTrue(returnNode.result().toString(), returnNode.result().isConstant());
-                Assert.assertEquals(expectedConstantResult, returnNode.result().asConstant());
+                Assumptions assumptions = new Assumptions(false);
+                new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
+                new DeadCodeEliminationPhase().apply(graph);
+                new PartialEscapeAnalysisPhase(runtime(), assumptions, iterativeEscapeAnalysis, false).apply(graph);
+                Assert.assertEquals(1, graph.getNodes(ReturnNode.class).count());
+                ReturnNode returnNode = graph.getNodes(ReturnNode.class).first();
+                if (expectedConstantResult != null) {
+                    Assert.assertTrue(returnNode.result().toString(), returnNode.result().isConstant());
+                    Assert.assertEquals(expectedConstantResult, returnNode.result().asConstant());
+                }
+                int newInstanceCount = graph.getNodes(NewInstanceNode.class).count() + graph.getNodes(NewArrayNode.class).count() + graph.getNodes(MaterializeObjectNode.class).count();
+                Assert.assertEquals(0, newInstanceCount);
+                return returnNode;
             }
-            int newInstanceCount = graph.getNodes(NewInstanceNode.class).count() + graph.getNodes(NewArrayNode.class).count() + graph.getNodes(MaterializeObjectNode.class).count();
-            Assert.assertEquals(0, newInstanceCount);
-            return returnNode;
-        } catch (AssertionFailedError t) {
-            throw new RuntimeException(t.getMessage() + "\n" + getCanonicalGraphString(graph), t);
-        }
+        });
     }
 }

--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java	Tue Apr 09 10:48:14 2013 +0200
@@ -143,10 +143,11 @@
     }
 
     @SuppressWarnings("all")
-    public static int testBadLoopSnippet(TestObject obj, int a, int b) {
+    public static int testBadLoopSnippet(TestObject obj, TestObject obj2, int a, int b) {
         obj.x = a;
         for (int i = 0; i < 10; i++) {
             staticField = obj;
+            obj2.x = 10;
             obj.x = 0;
         }
         return obj.x;
@@ -155,6 +156,24 @@
     @Test
     public void testBadLoop() {
         ValueNode result = getReturn("testBadLoopSnippet").result();
+        assertEquals(0, graph.getNodes(LoadFieldNode.class).count());
+        assertTrue(result instanceof ProxyNode);
+        assertTrue(((ProxyNode) result).value() instanceof PhiNode);
+    }
+
+    @SuppressWarnings("all")
+    public static int testBadLoop2Snippet(TestObject obj, TestObject obj2, int a, int b) {
+        obj.x = a;
+        for (int i = 0; i < 10; i++) {
+            obj.x = 0;
+            obj2.x = 10;
+        }
+        return obj.x;
+    }
+
+    @Test
+    public void testBadLoop2() {
+        ValueNode result = getReturn("testBadLoop2Snippet").result();
         assertEquals(1, graph.getNodes(LoadFieldNode.class).count());
         assertTrue(result instanceof LoadFieldNode);
     }

--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java	Tue Apr 09 10:48:14 2013 +0200
@@ -22,13 +22,15 @@
  */
 package com.oracle.graal.compiler.test.ea;
 
+import java.util.concurrent.*;
+
 import junit.framework.*;
-import junit.framework.Assert;
 
 import org.junit.Test;
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.compiler.test.*;
+import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.java.*;
@@ -72,8 +74,8 @@
     }
 
     @SuppressWarnings("all")
-    public static Object test1Snippet(int a, int b) {
-        TestObject obj = new TestObject(1, 2);
+    public static Object test1Snippet(int a, int b, Object x, Object y) {
+        TestObject2 obj = new TestObject2(x, y);
         if (a < 0) {
             if (b < 0) {
                 return obj;
@@ -90,9 +92,9 @@
         testMaterialize("test2Snippet", 1.5, 3, LoadIndexedNode.class);
     }
 
-    public static Object test2Snippet(int a) {
-        TestObject2 obj = new TestObject2(1, 2);
-        obj.x = new TestObject2(obj, 3);
+    public static Object test2Snippet(int a, Object x, Object y, Object z) {
+        TestObject2 obj = new TestObject2(x, y);
+        obj.x = new TestObject2(obj, z);
         if (a < 0) {
             ((TestObject2) obj.x).y = null;
             obj.y = null;
@@ -125,42 +127,49 @@
     @SafeVarargs
     final void testMaterialize(final String snippet, double expectedProbability, int expectedCount, Class<? extends Node>... invalidNodeClasses) {
         StructuredGraph result = processMethod(snippet);
-        Assert.assertTrue("partial escape analysis should have removed all NewInstanceNode allocations", result.getNodes(NewInstanceNode.class).isEmpty());
-        Assert.assertTrue("partial escape analysis should have removed all NewArrayNode allocations", result.getNodes(NewArrayNode.class).isEmpty());
-        double probabilitySum = 0;
-        int materializeCount = 0;
-        for (MaterializeObjectNode materialize : result.getNodes(MaterializeObjectNode.class)) {
-            probabilitySum += materialize.probability();
-            materializeCount++;
-        }
-        Assert.assertEquals("unexpected number of MaterializeObjectNodes", expectedCount, materializeCount);
-        Assert.assertEquals("unexpected probability of MaterializeObjectNodes", expectedProbability, probabilitySum, 0.01);
-        for (Node node : result.getNodes()) {
-            for (Class<? extends Node> clazz : invalidNodeClasses) {
-                Assert.assertFalse("instance of invalid class: " + clazz.getSimpleName(), clazz.isInstance(node) && node.usages().isNotEmpty());
+        try {
+            Assert.assertTrue("partial escape analysis should have removed all NewInstanceNode allocations", result.getNodes(NewInstanceNode.class).isEmpty());
+            Assert.assertTrue("partial escape analysis should have removed all NewArrayNode allocations", result.getNodes(NewArrayNode.class).isEmpty());
+            double probabilitySum = 0;
+            int materializeCount = 0;
+            for (MaterializeObjectNode materialize : result.getNodes(MaterializeObjectNode.class)) {
+                probabilitySum += materialize.probability();
+                materializeCount++;
             }
+            Assert.assertEquals("unexpected number of MaterializeObjectNodes", expectedCount, materializeCount);
+            Assert.assertEquals("unexpected probability of MaterializeObjectNodes", expectedProbability, probabilitySum, 0.01);
+            for (Node node : result.getNodes()) {
+                for (Class<? extends Node> clazz : invalidNodeClasses) {
+                    Assert.assertFalse("instance of invalid class: " + clazz.getSimpleName(), clazz.isInstance(node) && node.usages().isNotEmpty());
+                }
+            }
+        } catch (AssertionError e) {
+            TypeSystemTest.outputGraph(result, snippet + ": " + e.getMessage());
+            throw e;
         }
     }
 
     private StructuredGraph processMethod(final String snippet) {
-        StructuredGraph graph = parse(snippet);
-        try {
-            new ComputeProbabilityPhase().apply(graph);
-            for (Invoke n : graph.getInvokes()) {
-                n.node().setProbability(100000);
+        return Debug.scope("PartialEscapeAnalysisTest " + snippet, new DebugDumpScope(snippet), new Callable<StructuredGraph>() {
+
+            @Override
+            public StructuredGraph call() {
+                StructuredGraph graph = parse(snippet);
+                new ComputeProbabilityPhase().apply(graph);
+                for (Invoke n : graph.getInvokes()) {
+                    n.node().setProbability(100000);
+                }
+                Assumptions assumptions = new Assumptions(false);
+                new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
+                new DeadCodeEliminationPhase().apply(graph);
+                new CanonicalizerPhase(runtime(), assumptions).apply(graph);
+                new PartialEscapeAnalysisPhase(runtime(), assumptions, false, false).apply(graph);
+
+                new CullFrameStatesPhase().apply(graph);
+                new DeadCodeEliminationPhase().apply(graph);
+                new CanonicalizerPhase(runtime(), assumptions).apply(graph);
+                return graph;
             }
-            Assumptions assumptions = new Assumptions(false);
-            new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
-            new DeadCodeEliminationPhase().apply(graph);
-            new CanonicalizerPhase(runtime(), assumptions).apply(graph);
-            new PartialEscapeAnalysisPhase(runtime(), assumptions, false, false).apply(graph);
-
-            new CullFrameStatesPhase().apply(graph);
-            new DeadCodeEliminationPhase().apply(graph);
-            new CanonicalizerPhase(runtime(), assumptions).apply(graph);
-            return graph;
-        } catch (AssertionFailedError t) {
-            throw new RuntimeException(t.getMessage() + "\n" + getCanonicalGraphString(graph), t);
-        }
+        });
     }
 }

--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java	Tue Apr 09 10:48:14 2013 +0200
@@ -82,21 +82,16 @@
                 for (Entry<VirtualObjectNode, VirtualObject> entry : virtualObjectsCopy.entrySet()) {
                     if (entry.getValue().getValues() == null) {
                         VirtualObjectNode vobj = entry.getKey();
-                        if (vobj instanceof BoxedVirtualObjectNode) {
-                            BoxedVirtualObjectNode boxedVirtualObjectNode = (BoxedVirtualObjectNode) vobj;
-                            entry.getValue().setValues(new Value[]{toValue(boxedVirtualObjectNode.getUnboxedValue())});
-                        } else {
-                            Value[] values = new Value[vobj.entryCount()];
-                            if (values.length > 0) {
-                                changed = true;
-                                VirtualObjectState currentField = (VirtualObjectState) objectStates.get(vobj);
-                                assert currentField != null;
-                                for (int i = 0; i < vobj.entryCount(); i++) {
-                                    values[i] = toValue(currentField.fieldValues().get(i));
-                                }
+                        Value[] values = new Value[vobj.entryCount()];
+                        if (values.length > 0) {
+                            changed = true;
+                            VirtualObjectState currentField = (VirtualObjectState) objectStates.get(vobj);
+                            assert currentField != null;
+                            for (int i = 0; i < vobj.entryCount(); i++) {
+                                values[i] = toValue(currentField.fieldValues().get(i));
                             }
-                            entry.getValue().setValues(values);
                         }
+                        entry.getValue().setValues(values);
                     }
                 }
             } while (changed);
@@ -165,7 +160,7 @@
         if (value instanceof VirtualObjectNode) {
             VirtualObjectNode obj = (VirtualObjectNode) value;
             EscapeObjectState state = objectStates.get(obj);
-            if (state == null && obj.entryCount() > 0 && !(obj instanceof BoxedVirtualObjectNode)) {
+            if (state == null && obj.entryCount() > 0) {
                 // null states occur for objects with 0 fields
                 throw new GraalInternalError("no mapping found for virtual object %s", obj);
             }
@@ -173,7 +168,7 @@
                 assert !(((MaterializedObjectState) state).materializedValue() instanceof VirtualObjectNode);
                 return toValue(((MaterializedObjectState) state).materializedValue());
             } else {
-                assert obj.entryCount() == 0 || state instanceof VirtualObjectState || obj instanceof BoxedVirtualObjectNode;
+                assert obj.entryCount() == 0 || state instanceof VirtualObjectState;
                 VirtualObject vobject = virtualObjects.get(value);
                 if (vobject == null) {
                     vobject = VirtualObject.get(obj.type(), null, virtualObjects.size());

--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotReplacementsImpl.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotReplacementsImpl.java	Tue Apr 09 10:48:14 2013 +0200
@@ -25,12 +25,14 @@
 import java.lang.reflect.*;
 
 import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
 import com.oracle.graal.hotspot.meta.*;
 import com.oracle.graal.hotspot.replacements.*;
 import com.oracle.graal.replacements.*;
 
 /**
- * Filters certain method substitutions based on whether there is underlying hardware support for them.
+ * Filters certain method substitutions based on whether there is underlying hardware support for
+ * them.
  */
 public class HotSpotReplacementsImpl extends ReplacementsImpl {
 
@@ -42,22 +44,22 @@
     }
 
     @Override
-    protected void registerMethodSubstitution(Member originalMethod, Method substituteMethod) {
+    protected ResolvedJavaMethod registerMethodSubstitution(Member originalMethod, Method substituteMethod) {
         if (substituteMethod.getDeclaringClass() == IntegerSubstitutions.class || substituteMethod.getDeclaringClass() == LongSubstitutions.class) {
             if (substituteMethod.getName().equals("bitCount")) {
                 if (!config.usePopCountInstruction) {
-                    return;
+                    return null;
                 }
             }
         } else if (substituteMethod.getDeclaringClass() == AESCryptSubstitutions.class || substituteMethod.getDeclaringClass() == CipherBlockChainingSubstitutions.class) {
             if (!config.useAESIntrinsics) {
-                return;
+                return null;
             }
             assert config.aescryptEncryptBlockStub != 0L;
             assert config.aescryptDecryptBlockStub != 0L;
             assert config.cipherBlockChainingEncryptAESCryptStub != 0L;
             assert config.cipherBlockChainingDecryptAESCryptStub != 0L;
         }
-        super.registerMethodSubstitution(originalMethod, substituteMethod);
+        return super.registerMethodSubstitution(originalMethod, substituteMethod);
     }
 }

--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/bridge/VMToCompilerImpl.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/bridge/VMToCompilerImpl.java	Tue Apr 09 10:48:14 2013 +0200
@@ -156,6 +156,13 @@
                         provider.registerReplacements(replacements);
                     }
                     runtime.registerReplacements(replacements);
+                    if (GraalOptions.BootstrapReplacements) {
+                        for (ResolvedJavaMethod method : replacements.getAllReplacements()) {
+                            replacements.getMacroSubstitution(method);
+                            replacements.getMethodSubstitution(method);
+                            replacements.getSnippet(method);
+                        }
+                    }
                 }
             });
 

--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java	Tue Apr 09 10:48:14 2013 +0200
@@ -89,6 +89,7 @@
     private NewObjectSnippets.Templates newObjectSnippets;
     private MonitorSnippets.Templates monitorSnippets;
     private WriteBarrierSnippets.Templates writeBarrierSnippets;
+    private BoxingSnippets.Templates boxingSnippets;
     private LoadExceptionObjectSnippets.Templates exceptionObjectSnippets;
 
     private final Map<Descriptor, HotSpotRuntimeCallTarget> runtimeCalls = new HashMap<>();
@@ -332,11 +333,17 @@
             replacements.registerSnippets(ObjectCloneSnippets.class);
         }
 
+        replacements.registerSnippets(BoxingSnippets.class);
+        for (Class<?> clazz : BoxingSubstitutions.getClasses()) {
+            replacements.registerSubstitutions(clazz);
+        }
+
         checkcastSnippets = new CheckCastSnippets.Templates(this, replacements, graalRuntime.getTarget());
         instanceofSnippets = new InstanceOfSnippets.Templates(this, replacements, graalRuntime.getTarget());
         newObjectSnippets = new NewObjectSnippets.Templates(this, replacements, graalRuntime.getTarget(), config.useTLAB);
         monitorSnippets = new MonitorSnippets.Templates(this, replacements, graalRuntime.getTarget(), config.useFastLocking);
         writeBarrierSnippets = new WriteBarrierSnippets.Templates(this, replacements, graalRuntime.getTarget());
+        boxingSnippets = new BoxingSnippets.Templates(this, replacements, graalRuntime.getTarget());
         exceptionObjectSnippets = new LoadExceptionObjectSnippets.Templates(this, replacements, graalRuntime.getTarget());
 
         registerStub(new NewInstanceStub(this, replacements, graalRuntime.getTarget(), runtimeCalls.get(NEW_INSTANCE)));
@@ -715,6 +722,10 @@
             // zero and the MIN_VALUE / -1 cases.
         } else if (n instanceof UnwindNode) {
             // Nothing to do, using direct LIR lowering for these nodes.
+        } else if (n instanceof BoxNode) {
+            boxingSnippets.lower((BoxNode) n);
+        } else if (n instanceof UnboxNode) {
+            boxingSnippets.lower((UnboxNode) n);
         } else {
             assert false : "Node implementing Lowerable not handled: " + n;
             throw GraalInternalError.shouldNotReachHere();

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/BoxingSnippets.java	Tue Apr 09 10:48:14 2013 +0200
@@ -0,0 +1,252 @@
+/*
+ * Copyright (c) 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.hotspot.replacements;
+
+import static com.oracle.graal.replacements.SnippetTemplate.*;
+
+import java.lang.reflect.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.graph.Node.NodeIntrinsic;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.nodes.extended.*;
+import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.phases.*;
+import com.oracle.graal.replacements.*;
+import com.oracle.graal.replacements.Snippet.Fold;
+import com.oracle.graal.replacements.Snippet.Parameter;
+import com.oracle.graal.replacements.Snippet.SnippetInliningPolicy;
+import com.oracle.graal.replacements.SnippetTemplate.AbstractTemplates;
+import com.oracle.graal.replacements.SnippetTemplate.Arguments;
+import com.oracle.graal.replacements.SnippetTemplate.Key;
+import com.oracle.graal.word.*;
+
+public class BoxingSnippets implements Snippets {
+
+    /**
+     * This snippet inlining policy differs from the default one in that it does normal inlining of
+     * boxing methods like {@link Integer#valueOf(int)} (as opposed to method substitution).
+     */
+    public static class BoxingSnippetInliningPolicy implements SnippetInliningPolicy {
+
+        @Override
+        public boolean shouldInline(ResolvedJavaMethod method, ResolvedJavaMethod caller) {
+            if (Modifier.isNative(method.getModifiers())) {
+                return false;
+            }
+            if (method.getAnnotation(Fold.class) != null) {
+                return false;
+            }
+            if (method.getAnnotation(NodeIntrinsic.class) != null) {
+                return false;
+            }
+            if (method.getAnnotation(Word.Operation.class) != null) {
+                return false;
+            }
+            return true;
+        }
+
+        @Override
+        public boolean shouldUseReplacement(ResolvedJavaMethod callee, ResolvedJavaMethod methodToParse) {
+            return false;
+        }
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static Boolean valueOf(@Parameter("value") boolean value) {
+        valueOfCounter.inc();
+        return UnsafeCastNode.unsafeCast(Boolean.valueOf(value), StampFactory.forNodeIntrinsic());
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static Byte valueOf(@Parameter("value") byte value) {
+        valueOfCounter.inc();
+        return UnsafeCastNode.unsafeCast(Byte.valueOf(value), StampFactory.forNodeIntrinsic());
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static Character valueOf(@Parameter("value") char value) {
+        valueOfCounter.inc();
+        return UnsafeCastNode.unsafeCast(Character.valueOf(value), StampFactory.forNodeIntrinsic());
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static Double valueOf(@Parameter("value") double value) {
+        valueOfCounter.inc();
+        return UnsafeCastNode.unsafeCast(Double.valueOf(value), StampFactory.forNodeIntrinsic());
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static Float valueOf(@Parameter("value") float value) {
+        valueOfCounter.inc();
+        return UnsafeCastNode.unsafeCast(Float.valueOf(value), StampFactory.forNodeIntrinsic());
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static Integer valueOf(@Parameter("value") int value) {
+        valueOfCounter.inc();
+        return UnsafeCastNode.unsafeCast(Integer.valueOf(value), StampFactory.forNodeIntrinsic());
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static Long valueOf(@Parameter("value") long value) {
+        valueOfCounter.inc();
+        return UnsafeCastNode.unsafeCast(Long.valueOf(value), StampFactory.forNodeIntrinsic());
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static Short valueOf(@Parameter("value") short value) {
+        valueOfCounter.inc();
+        return UnsafeCastNode.unsafeCast(Short.valueOf(value), StampFactory.forNodeIntrinsic());
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static boolean booleanValue(@Parameter("value") Boolean value) {
+        valueOfCounter.inc();
+        return value.booleanValue();
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static byte byteValue(@Parameter("value") Byte value) {
+        valueOfCounter.inc();
+        return value.byteValue();
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static char charValue(@Parameter("value") Character value) {
+        valueOfCounter.inc();
+        return value.charValue();
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static double doubleValue(@Parameter("value") Double value) {
+        valueOfCounter.inc();
+        return value.doubleValue();
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static float floatValue(@Parameter("value") Float value) {
+        valueOfCounter.inc();
+        return value.floatValue();
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static int intValue(@Parameter("value") Integer value) {
+        valueOfCounter.inc();
+        return value.intValue();
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static long longValue(@Parameter("value") Long value) {
+        valueOfCounter.inc();
+        return value.longValue();
+    }
+
+    @Snippet(inlining = BoxingSnippetInliningPolicy.class)
+    public static short shortValue(@Parameter("value") Short value) {
+        valueOfCounter.inc();
+        return value.shortValue();
+    }
+
+    public static FloatingNode canonicalizeBoxing(BoxNode box, MetaAccessProvider runtime) {
+        ValueNode value = box.getValue();
+        if (value.isConstant()) {
+            Constant sourceConstant = value.asConstant();
+            switch (box.getBoxingKind()) {
+                case Boolean:
+                    return ConstantNode.forObject(Boolean.valueOf(sourceConstant.asInt() != 0), runtime, box.graph());
+                case Byte:
+                    return ConstantNode.forObject(Byte.valueOf((byte) sourceConstant.asInt()), runtime, box.graph());
+                case Char:
+                    return ConstantNode.forObject(Character.valueOf((char) sourceConstant.asInt()), runtime, box.graph());
+                case Short:
+                    return ConstantNode.forObject(Short.valueOf((short) sourceConstant.asInt()), runtime, box.graph());
+                case Int:
+                    return ConstantNode.forObject(Integer.valueOf(sourceConstant.asInt()), runtime, box.graph());
+                case Long:
+                    return ConstantNode.forObject(Long.valueOf(sourceConstant.asLong()), runtime, box.graph());
+                case Float:
+                    return ConstantNode.forObject(Float.valueOf(sourceConstant.asFloat()), runtime, box.graph());
+                case Double:
+                    return ConstantNode.forObject(Double.valueOf(sourceConstant.asDouble()), runtime, box.graph());
+                default:
+                    assert false : "Unexpected source kind for boxing";
+                    break;
+            }
+        }
+        return null;
+    }
+
+    public static class Templates extends AbstractTemplates<BoxingSnippets> {
+
+        private final ResolvedJavaMethod[] valueOfMethods = new ResolvedJavaMethod[Kind.values().length];
+        private final ResolvedJavaMethod[] unboxMethods = new ResolvedJavaMethod[Kind.values().length];
+
+        public Templates(CodeCacheProvider runtime, Replacements replacements, TargetDescription target) {
+            super(runtime, replacements, target, BoxingSnippets.class);
+            for (Kind kind : new Kind[]{Kind.Boolean, Kind.Byte, Kind.Char, Kind.Double, Kind.Float, Kind.Int, Kind.Long, Kind.Short}) {
+                valueOfMethods[kind.ordinal()] = snippet("valueOf", kind.toJavaClass());
+                unboxMethods[kind.ordinal()] = snippet(kind.getJavaName() + "Value", kind.toBoxedJavaClass());
+            }
+        }
+
+        private ResolvedJavaMethod getValueOf(Kind kind) {
+            assert valueOfMethods[kind.ordinal()] != null;
+            return valueOfMethods[kind.ordinal()];
+        }
+
+        private ResolvedJavaMethod getUnbox(Kind kind) {
+            assert unboxMethods[kind.ordinal()] != null;
+            return unboxMethods[kind.ordinal()];
+        }
+
+        public void lower(BoxNode box) {
+            FloatingNode canonical = canonicalizeBoxing(box, runtime);
+            if (canonical != null) {
+                ((StructuredGraph) box.graph()).replaceFixedWithFloating(box, canonical);
+            } else {
+                Key key = new Key(getValueOf(box.getBoxingKind()));
+                Arguments arguments = new Arguments().add("value", box.getValue());
+                SnippetTemplate template = cache.get(key);
+                Debug.log("Lowering integerValueOf in %s: node=%s, template=%s, arguments=%s", box.graph(), box, template, arguments);
+                template.instantiate(runtime, box, DEFAULT_REPLACER, arguments);
+            }
+        }
+
+        public void lower(UnboxNode unbox) {
+            Key key = new Key(getUnbox(unbox.getBoxingKind()));
+            Arguments arguments = new Arguments().add("value", unbox.getValue());
+            SnippetTemplate template = cache.get(key);
+            Debug.log("Lowering integerValueOf in %s: node=%s, template=%s, arguments=%s", unbox.graph(), unbox, template, arguments);
+            template.instantiate(runtime, unbox, DEFAULT_REPLACER, arguments);
+        }
+    }
+
+    private static final SnippetCounter.Group integerCounters = GraalOptions.SnippetCounters ? new SnippetCounter.Group("Integer intrinsifications") : null;
+    private static final SnippetCounter valueOfCounter = new SnippetCounter(integerCounters, "valueOf", "valueOf intrinsification");
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/BoxingSubstitutions.java	Tue Apr 09 10:48:14 2013 +0200
@@ -0,0 +1,147 @@
+/*
+ * Copyright (c) 2012, 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.hotspot.replacements;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
+import com.oracle.graal.nodes.extended.*;
+
+public class BoxingSubstitutions {
+
+    @ClassSubstitution(Boolean.class)
+    private static class BooleanSubstitutions {
+
+        @MethodSubstitution(isForcedInlining = true)
+        public static Boolean valueOf(boolean value) {
+            return BoxNode.box(value, Boolean.class, Kind.Boolean);
+        }
+
+        @MethodSubstitution(isStatic = false, isForcedInlining = true)
+        public static boolean booleanValue(Boolean value) {
+            return UnboxNode.unbox(value, Kind.Boolean);
+        }
+    }
+
+    @ClassSubstitution(Byte.class)
+    private static class ByteSubstitutions {
+
+        @MethodSubstitution(isForcedInlining = true)
+        public static Byte valueOf(byte value) {
+            return BoxNode.box(value, Byte.class, Kind.Byte);
+        }
+
+        @MethodSubstitution(isStatic = false, isForcedInlining = true)
+        public static byte byteValue(Byte value) {
+            return UnboxNode.unbox(value, Kind.Byte);
+        }
+    }
+
+    @ClassSubstitution(Character.class)
+    private static class CharacterSubstitutions {
+
+        @MethodSubstitution(isForcedInlining = true)
+        public static Character valueOf(char value) {
+            return BoxNode.box(value, Character.class, Kind.Char);
+        }
+
+        @MethodSubstitution(isStatic = false, isForcedInlining = true)
+        public static char charValue(Character value) {
+            return UnboxNode.unbox(value, Kind.Char);
+        }
+    }
+
+    @ClassSubstitution(Double.class)
+    private static class DoubleSubstitutions {
+
+        @MethodSubstitution(isForcedInlining = true)
+        public static Double valueOf(double value) {
+            return BoxNode.box(value, Double.class, Kind.Double);
+        }
+
+        @MethodSubstitution(isStatic = false, isForcedInlining = true)
+        public static double doubleValue(Double value) {
+            return UnboxNode.unbox(value, Kind.Double);
+        }
+    }
+
+    @ClassSubstitution(Float.class)
+    private static class FloatSubstitutions {
+
+        @MethodSubstitution(isForcedInlining = true)
+        public static Float valueOf(float value) {
+            return BoxNode.box(value, Float.class, Kind.Float);
+        }
+
+        @MethodSubstitution(isStatic = false, isForcedInlining = true)
+        public static float floatValue(Float value) {
+            return UnboxNode.unbox(value, Kind.Float);
+        }
+    }
+
+    @ClassSubstitution(Integer.class)
+    private static class IntegerSubstitutions {
+
+        @MethodSubstitution(isForcedInlining = true)
+        public static Integer valueOf(int value) {
+            return BoxNode.box(value, Integer.class, Kind.Int);
+        }
+
+        @MethodSubstitution(isStatic = false, isForcedInlining = true)
+        public static int intValue(Integer value) {
+            return UnboxNode.unbox(value, Kind.Int);
+        }
+    }
+
+    @ClassSubstitution(Long.class)
+    private static class LongSubstitutions {
+
+        @MethodSubstitution(isForcedInlining = true)
+        public static Long valueOf(long value) {
+            return BoxNode.box(value, Long.class, Kind.Long);
+        }
+
+        @MethodSubstitution(isStatic = false, isForcedInlining = true)
+        public static long longValue(Long value) {
+            return UnboxNode.unbox(value, Kind.Long);
+        }
+    }
+
+    @ClassSubstitution(Short.class)
+    private static class ShortSubstitutions {
+
+        @MethodSubstitution(isForcedInlining = true)
+        public static Short valueOf(short value) {
+            return BoxNode.box(value, Short.class, Kind.Short);
+        }
+
+        @MethodSubstitution(isStatic = false, isForcedInlining = true)
+        public static short shortValue(Short value) {
+            return UnboxNode.unbox(value, Kind.Short);
+        }
+    }
+
+    public static Class<?>[] getClasses() {
+        return new Class<?>[]{BooleanSubstitutions.class, ByteSubstitutions.class, CharacterSubstitutions.class, DoubleSubstitutions.class, FloatSubstitutions.class, IntegerSubstitutions.class,
+                        LongSubstitutions.class, ShortSubstitutions.class};
+    }
+}

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -186,5 +186,5 @@
     }
 
     @NodeIntrinsic
-    public static native <T> T anchor(@ConstantNodeParameter Stamp stamp);
+    public static native BeginNode anchor(@ConstantNodeParameter Stamp stamp);
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java	Tue Apr 09 10:48:14 2013 +0200
@@ -239,7 +239,7 @@
                 copy.remove(copy.size() - 1);
             }
             ValueNode lastSlot = copy.get(copy.size() - 1);
-            assert lastSlot.kind().getStackKind() == popKind.getStackKind() || (lastSlot instanceof BoxedVirtualObjectNode && popKind == Kind.Object);
+            assert lastSlot.kind().getStackKind() == popKind.getStackKind();
             copy.remove(copy.size() - 1);
         }
         Collections.addAll(copy, pushedValues);

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConvertNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConvertNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -172,5 +172,15 @@
     }
 
     @NodeIntrinsic
-    public static native <S, T> S convert(@ConstantNodeParameter Op op, T value);
+    public static native float convert(@ConstantNodeParameter Op op, int value);
+
+    @NodeIntrinsic
+    public static native int convert(@ConstantNodeParameter Op op, float value);
+
+    @NodeIntrinsic
+    public static native double convert(@ConstantNodeParameter Op op, long value);
+
+    @NodeIntrinsic
+    public static native long convert(@ConstantNodeParameter Op op, double value);
+
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ObjectEqualsNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ObjectEqualsNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -81,8 +81,28 @@
             // one of them is virtual: they can never be the same objects
             tool.replaceWithValue(LogicConstantNode.contradiction(graph()));
         } else if (xVirtual && yVirtual) {
-            // both are virtual: check if they refer to the same object
-            tool.replaceWithValue(LogicConstantNode.forBoolean(stateX == stateY, graph()));
+            boolean xIdentity = stateX.getVirtualObject().hasIdentity();
+            boolean yIdentity = stateY.getVirtualObject().hasIdentity();
+            if (xIdentity ^ yIdentity) {
+                tool.replaceWithValue(LogicConstantNode.contradiction(graph()));
+            } else if (!xIdentity && !yIdentity) {
+                // both are virtual without identity: check contents
+                assert stateX.getVirtualObject().entryCount() == 1 && stateY.getVirtualObject().entryCount() == 1;
+                assert stateX.getVirtualObject().type() == stateY.getVirtualObject().type();
+                assert stateX.getVirtualObject().entryKind(0) == Kind.Int || stateX.getVirtualObject().entryKind(0) == Kind.Long;
+                final IntegerEqualsNode equals = new IntegerEqualsNode(stateX.getEntry(0), stateY.getEntry(0));
+                tool.customAction(new Runnable() {
+
+                    @Override
+                    public void run() {
+                        graph().add(equals);
+                    }
+                });
+                tool.replaceWithValue(equals);
+            } else {
+                // both are virtual with identity: check if they refer to the same object
+                tool.replaceWithValue(LogicConstantNode.forBoolean(stateX == stateY, graph()));
+            }
         }
     }
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/BoxNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/BoxNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2013, 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
@@ -23,80 +23,84 @@
 package com.oracle.graal.nodes.extended;
 
 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.java.MethodCallTargetNode.InvokeKind;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
-
-public final class BoxNode extends AbstractStateSplit implements StateSplit, Node.IterableNodeType, Canonicalizable {
+import com.oracle.graal.nodes.virtual.*;
 
-    @Input private ValueNode source;
-    private final int bci;
-    private final Kind sourceKind;
+public class BoxNode extends FixedWithNextNode implements VirtualizableAllocation, Lowerable, Canonicalizable {
 
-    public BoxNode(ValueNode value, ResolvedJavaType type, Kind sourceKind, int bci) {
-        super(StampFactory.exactNonNull(type));
-        this.source = value;
-        this.bci = bci;
-        this.sourceKind = sourceKind;
-        assert value.kind() != Kind.Object : "can only box from primitive type";
+    @Input private ValueNode value;
+    private final Kind boxingKind;
+
+    public BoxNode(Invoke invoke) {
+        this(invoke.methodCallTarget().arguments().get(0), invoke.node().objectStamp().type(), invoke.methodCallTarget().targetMethod().getSignature().getParameterKind(0));
     }
 
-    public ValueNode source() {
-        return source;
-    }
-
-    public Kind getSourceKind() {
-        return sourceKind;
+    public BoxNode(ValueNode value, ResolvedJavaType resultType, Kind boxingKind) {
+        super(StampFactory.exactNonNull(resultType));
+        this.value = value;
+        this.boxingKind = boxingKind;
     }
 
-    public void expand(BoxingMethodPool pool) {
-        ResolvedJavaMethod boxingMethod = pool.getBoxingMethod(sourceKind);
-        MethodCallTargetNode callTarget = graph().add(
-                        new MethodCallTargetNode(InvokeKind.Static, boxingMethod, new ValueNode[]{source}, boxingMethod.getSignature().getReturnType(boxingMethod.getDeclaringClass())));
-        InvokeNode invokeNode = graph().add(new InvokeNode(callTarget, bci));
-        invokeNode.setProbability(this.probability());
-        invokeNode.setStateAfter(stateAfter());
-        ((StructuredGraph) graph()).replaceFixedWithFixed(this, invokeNode);
+    public Kind getBoxingKind() {
+        return boxingKind;
+    }
+
+    public ValueNode getValue() {
+        return value;
+    }
+
+    @Override
+    public void lower(LoweringTool tool) {
+        tool.getRuntime().lower(this, tool);
     }
 
     @Override
     public ValueNode canonical(CanonicalizerTool tool) {
+        /*
+         * Constant values are not canonicalized into their constant boxing objects because this
+         * would mean that the information that they came from a valueOf is lost.
+         */
+        if (usages().isEmpty()) {
+            return null;
+        }
+        return this;
+    }
 
-        if (source.isConstant()) {
-            Constant sourceConstant = source.asConstant();
-            switch (sourceKind) {
-                case Boolean:
-                    return ConstantNode.forObject(Boolean.valueOf(sourceConstant.asBoolean()), tool.runtime(), graph());
-                case Byte:
-                    return ConstantNode.forObject(Byte.valueOf((byte) sourceConstant.asInt()), tool.runtime(), graph());
-                case Char:
-                    return ConstantNode.forObject(Character.valueOf((char) sourceConstant.asInt()), tool.runtime(), graph());
-                case Short:
-                    return ConstantNode.forObject(Short.valueOf((short) sourceConstant.asInt()), tool.runtime(), graph());
-                case Int:
-                    return ConstantNode.forObject(Integer.valueOf(sourceConstant.asInt()), tool.runtime(), graph());
-                case Long:
-                    return ConstantNode.forObject(Long.valueOf(sourceConstant.asLong()), tool.runtime(), graph());
-                case Float:
-                    return ConstantNode.forObject(Float.valueOf(sourceConstant.asFloat()), tool.runtime(), graph());
-                case Double:
-                    return ConstantNode.forObject(Double.valueOf(sourceConstant.asDouble()), tool.runtime(), graph());
-                default:
-                    assert false : "Unexpected source kind for boxing";
-                    break;
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        ValueNode v = tool.getReplacedValue(getValue());
+        ResolvedJavaType type = objectStamp().type();
+
+        VirtualBoxingNode newVirtual = new VirtualBoxingNode(type, boxingKind);
+        assert newVirtual.getFields().length == 1;
+
+        tool.createVirtualObject(newVirtual, new ValueNode[]{v}, 0);
+        tool.replaceWithVirtual(newVirtual);
+    }
+
+    @NodeIntrinsic
+    public static native Boolean box(boolean value, @ConstantNodeParameter Class<?> clazz, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native Byte box(byte value, @ConstantNodeParameter Class<?> clazz, @ConstantNodeParameter Kind kind);
 
-            }
-        }
+    @NodeIntrinsic
+    public static native Character box(char value, @ConstantNodeParameter Class<?> clazz, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native Double box(double value, @ConstantNodeParameter Class<?> clazz, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native Float box(float value, @ConstantNodeParameter Class<?> clazz, @ConstantNodeParameter Kind kind);
 
-        for (Node usage : usages()) {
-            if (usage != stateAfter()) {
-                return this;
-            }
-        }
-        replaceAtUsages(null);
-        return null;
-    }
+    @NodeIntrinsic
+    public static native Integer box(int value, @ConstantNodeParameter Class<?> clazz, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native Long box(long value, @ConstantNodeParameter Class<?> clazz, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native Short box(short value, @ConstantNodeParameter Class<?> clazz, @ConstantNodeParameter Kind kind);
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/BoxingMethodPool.java	Tue Apr 09 10:11:52 2013 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,95 +0,0 @@
-/*
- * 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.extended;
-
-import java.util.*;
-
-import com.oracle.graal.api.meta.*;
-
-public class BoxingMethodPool {
-
-    private final Set<JavaMethod> specialMethods = new HashSet<>();
-    private final MetaAccessProvider runtime;
-    private final ResolvedJavaMethod[] boxingMethods = new ResolvedJavaMethod[Kind.values().length];
-    private final ResolvedJavaMethod[] unboxingMethods = new ResolvedJavaMethod[Kind.values().length];
-    private final ResolvedJavaField[] boxFields = new ResolvedJavaField[Kind.values().length];
-
-    public BoxingMethodPool(MetaAccessProvider runtime) {
-        this.runtime = runtime;
-
-        try {
-            initialize(Kind.Boolean, Boolean.class, "booleanValue");
-            initialize(Kind.Byte, Byte.class, "byteValue");
-            initialize(Kind.Char, Character.class, "charValue");
-            initialize(Kind.Short, Short.class, "shortValue");
-            initialize(Kind.Int, Integer.class, "intValue");
-            initialize(Kind.Long, Long.class, "longValue");
-            initialize(Kind.Float, Float.class, "floatValue");
-            initialize(Kind.Double, Double.class, "doubleValue");
-        } catch (SecurityException | NoSuchMethodException e) {
-            throw new RuntimeException(e);
-        }
-    }
-
-    private void initialize(Kind kind, Class<?> type, String unboxMethod) throws SecurityException, NoSuchMethodException {
-        // Get boxing method from runtime.
-        ResolvedJavaMethod boxingMethod = runtime.lookupJavaMethod(type.getDeclaredMethod("valueOf", kind.toJavaClass()));
-        specialMethods.add(boxingMethod);
-        boxingMethods[kind.ordinal()] = boxingMethod;
-
-        // Get unboxing method from runtime.
-        ResolvedJavaMethod unboxingMethod = runtime.lookupJavaMethod(type.getDeclaredMethod(unboxMethod));
-        unboxingMethods[kind.ordinal()] = unboxingMethod;
-        specialMethods.add(unboxingMethod);
-
-        // Get the field that contains the boxed value.
-        ResolvedJavaField[] fields = runtime.lookupJavaType(type).getInstanceFields(false);
-        ResolvedJavaField boxField = fields[0];
-        assert fields.length == 1 && boxField.getKind() == kind;
-        boxFields[kind.ordinal()] = boxField;
-    }
-
-    public boolean isSpecialMethod(ResolvedJavaMethod method) {
-        return specialMethods.contains(method);
-    }
-
-    public boolean isBoxingMethod(ResolvedJavaMethod method) {
-        return isSpecialMethod(method) && method.getSignature().getReturnKind() == Kind.Object;
-    }
-
-    public boolean isUnboxingMethod(ResolvedJavaMethod method) {
-        return isSpecialMethod(method) && method.getSignature().getReturnKind() != Kind.Object;
-    }
-
-    public ResolvedJavaMethod getBoxingMethod(Kind kind) {
-        return boxingMethods[kind.ordinal()];
-    }
-
-    public ResolvedJavaMethod getUnboxingMethod(Kind kind) {
-        return unboxingMethods[kind.ordinal()];
-    }
-
-    public ResolvedJavaField getBoxField(Kind kind) {
-        return boxFields[kind.ordinal()];
-    }
-}

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/UnboxNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/UnboxNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2013, 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
@@ -23,47 +23,49 @@
 package com.oracle.graal.nodes.extended;
 
 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.spi.*;
 import com.oracle.graal.nodes.type.*;
 
-public final class UnboxNode extends FixedWithNextNode implements Node.IterableNodeType, Canonicalizable {
+public class UnboxNode extends FixedWithNextNode implements Virtualizable, Lowerable, Canonicalizable {
 
-    @Input private ValueNode source;
-    private Kind destinationKind;
+    @Input private ValueNode value;
+    private final Kind boxingKind;
 
-    public UnboxNode(Kind kind, ValueNode source) {
-        super(StampFactory.forKind(kind));
-        this.source = source;
-        this.destinationKind = kind;
-        assert kind != Kind.Object : "can only unbox to primitive";
-        assert source.kind() == Kind.Object : "can only unbox objects";
+    public UnboxNode(ValueNode value, Kind boxingKind) {
+        super(StampFactory.forKind(boxingKind.getStackKind()));
+        this.value = value;
+        this.boxingKind = boxingKind;
+    }
+
+    public Kind getBoxingKind() {
+        return boxingKind;
     }
 
-    public ValueNode source() {
-        return source;
+    public ValueNode getValue() {
+        return value;
     }
 
-    public Kind destinationKind() {
-        return destinationKind;
+    @Override
+    public void lower(LoweringTool tool) {
+        tool.getRuntime().lower(this, tool);
     }
 
-    public void expand(BoxingMethodPool pool) {
-        ResolvedJavaField field = pool.getBoxField(kind());
-        LoadFieldNode loadField = graph().add(new LoadFieldNode(source, field));
-        loadField.setProbability(probability());
-        ((StructuredGraph) graph()).replaceFixedWithFixed(this, loadField);
+    @Override
+    public void virtualize(VirtualizerTool tool) {
+        State state = tool.getObjectState(value);
+        if (state != null && state.getState() == EscapeState.Virtual) {
+            tool.replaceWithValue(state.getEntry(0));
+        }
     }
 
     @Override
     public ValueNode canonical(CanonicalizerTool tool) {
-        if (source.isConstant()) {
-            Constant constant = source.asConstant();
+        if (value.isConstant()) {
+            Constant constant = value.asConstant();
             Object o = constant.asObject();
             if (o != null) {
-                switch (destinationKind) {
+                switch (boxingKind) {
                     case Boolean:
                         return ConstantNode.forBoolean((Boolean) o, graph());
                     case Byte:
@@ -84,7 +86,42 @@
                         ValueNodeUtil.shouldNotReachHere();
                 }
             }
+        } else if (value instanceof BoxNode) {
+            return ((BoxNode) value).getValue();
+        }
+        if (usages().isEmpty()) {
+            return null;
         }
         return this;
     }
+
+    /*
+     * Normally, all these variants wouldn't be needed because this can be accomplished by using a
+     * generic method with automatic unboxing. These intrinsics, however, are themselves used for
+     * recognizing boxings, which means that there would be a circularity issue.
+     */
+
+    @NodeIntrinsic
+    public static native boolean unbox(Boolean value, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native byte unbox(Byte value, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native char unbox(Character value, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native double unbox(Double value, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native float unbox(Float value, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native int unbox(Integer value, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native long unbox(Long value, @ConstantNodeParameter Kind kind);
+
+    @NodeIntrinsic
+    public static native short unbox(Short value, @ConstantNodeParameter Kind kind);
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessMonitorNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessMonitorNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -28,6 +28,7 @@
 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.
@@ -72,7 +73,7 @@
     @Override
     public void virtualize(VirtualizerTool tool) {
         State state = tool.getObjectState(object);
-        if (state != null && state.getState() == EscapeState.Virtual) {
+        if (state != null && state.getState() == EscapeState.Virtual && state.getVirtualObject().getClass() == VirtualInstanceNode.class) {
             Debug.log("monitor operation %s on %s\n", this, state);
             int newLockCount = state.getLockCount() + (this instanceof MonitorEnterNode ? 1 : -1);
             state.setLockCount(newLockCount);

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/MacroSubstitution.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/MacroSubstitution.java	Tue Apr 09 10:48:14 2013 +0200
@@ -73,4 +73,10 @@
      * an {@link InvokeNode} as a parameter.
      */
     Class<? extends FixedWithNextNode> macro();
+
+    /**
+     * Determines if this method should be substituted in all cases, even if inlining thinks it is
+     * not important.
+     */
+    boolean isForcedInlining() default false;
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/Replacements.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/Replacements.java	Tue Apr 09 10:48:14 2013 +0200
@@ -22,6 +22,8 @@
  */
 package com.oracle.graal.nodes.spi;
 
+import java.util.*;
+
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.api.replacements.*;
@@ -70,4 +72,15 @@
      * macro} substitutions defined by a given class.
      */
     void registerSubstitutions(Class<?> substitutions);
+
+    /**
+     * Returns all methods that are currently registered as method/macro substitution or as a
+     * snippet.
+     */
+    Collection<ResolvedJavaMethod> getAllReplacements();
+
+    /**
+     * Determines whether the replacement of this method is flagged as being inlined always.
+     */
+    boolean isForcedSubstitution(ResolvedJavaMethod methodAt);
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java	Tue Apr 09 10:48:14 2013 +0200
@@ -23,12 +23,15 @@
 package com.oracle.graal.nodes.type;
 
 import com.oracle.graal.api.code.*;
+
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.type.GenericStamp.GenericStampType;
 
 public class StampFactory {
 
+    // JaCoCo Exclude
+
     private static final Stamp[] stampCache = new Stamp[Kind.values().length];
     private static final Stamp objectStamp = new ObjectStamp(null, false, false, false);
     private static final Stamp objectNonNullStamp = new ObjectStamp(null, false, true, false);

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/BoxedVirtualObjectNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,78 +0,0 @@
-/*
- * 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.nodes.virtual;
-
-import com.oracle.graal.api.meta.*;
-import com.oracle.graal.graph.*;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.spi.*;
-
-public class BoxedVirtualObjectNode extends VirtualObjectNode implements LIRLowerable, Node.ValueNumberable {
-
-    @Input ValueNode unboxedValue;
-    private final ResolvedJavaType type;
-    private final Kind kind;
-
-    public BoxedVirtualObjectNode(ResolvedJavaType type, Kind kind, ValueNode unboxedValue) {
-        this.type = type;
-        this.kind = kind;
-        this.unboxedValue = unboxedValue;
-    }
-
-    public ValueNode getUnboxedValue() {
-        return unboxedValue;
-    }
-
-    @Override
-    public ResolvedJavaType type() {
-        return type;
-    }
-
-    @Override
-    public int entryCount() {
-        return 1;
-    }
-
-    @Override
-    public String fieldName(int index) {
-        assert index == 0;
-        return "value";
-    }
-
-    @Override
-    public int entryIndexForOffset(long constantOffset) {
-        // (lstadler) unsafe access to a newly created boxing object should only ever touch the
-        // value field
-        return 0;
-    }
-
-    @Override
-    public Kind entryKind(int index) {
-        return kind;
-    }
-
-    @Override
-    public BoxedVirtualObjectNode duplicate() {
-        return new BoxedVirtualObjectNode(type, kind, unboxedValue);
-    }
-}

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualArrayNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualArrayNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -22,10 +22,14 @@
  */
 package com.oracle.graal.nodes.virtual;
 
+import java.util.*;
+
 import sun.misc.*;
 
 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.spi.*;
 
 @NodeInfo(nameTemplate = "VirtualArray {p#componentType/s}[{p#length}]")
@@ -137,4 +141,19 @@
     public VirtualArrayNode duplicate() {
         return new VirtualArrayNode(componentType, length);
     }
+
+    @Override
+    public void materializeAt(FixedWithNextNode materializeNode, List<ValueNode> values, boolean defaultValuesOnly, int lockCount) {
+        StructuredGraph graph = (StructuredGraph) graph();
+        ResolvedJavaType element = componentType();
+        NewArrayNode newArray = graph.add(new NewArrayNode(element, ConstantNode.forInt(entryCount(), graph), defaultValuesOnly, lockCount > 0));
+        materializeNode.replaceAtUsages(newArray);
+        graph.addBeforeFixed(materializeNode, newArray);
+        if (!defaultValuesOnly) {
+            for (int i = 0; i < entryCount(); i++) {
+                graph.addBeforeFixed(materializeNode, graph.add(new StoreIndexedNode(newArray, ConstantNode.forInt(i, graph), element.getKind(), values.get(i))));
+            }
+        }
+        graph.removeFixed(materializeNode);
+    }
 }

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualBoxingNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -0,0 +1,58 @@
+/*
+ * Copyright (c) 2013, 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.virtual;
+
+import java.util.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.extended.*;
+
+public class VirtualBoxingNode extends VirtualInstanceNode {
+
+    private final Kind boxingKind;
+
+    public VirtualBoxingNode(ResolvedJavaType type, Kind boxingKind) {
+        super(type);
+        this.boxingKind = boxingKind;
+    }
+
+    @Override
+    public VirtualBoxingNode duplicate() {
+        return new VirtualBoxingNode(type(), boxingKind);
+    }
+
+    @Override
+    public boolean hasIdentity() {
+        return false;
+    }
+
+    @Override
+    public void materializeAt(FixedWithNextNode materializeNode, List<ValueNode> values, boolean defaultValuesOnly, int lockCount) {
+        assert values.size() == 1;
+        assert lockCount == 0;
+        StructuredGraph graph = (StructuredGraph) graph();
+        BoxNode valueOf = graph.add(new BoxNode(values.get(0), type(), boxingKind));
+        graph.replaceFixedWithFixed(materializeNode, valueOf);
+    }
+}

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualInstanceNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualInstanceNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -22,8 +22,12 @@
  */
 package com.oracle.graal.nodes.virtual;
 
+import java.util.*;
+
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.java.*;
 
 @NodeInfo(nameTemplate = "VirtualInstance {p#type}")
 public class VirtualInstanceNode extends VirtualObjectNode {
@@ -93,4 +97,18 @@
     public VirtualInstanceNode duplicate() {
         return new VirtualInstanceNode(type);
     }
+
+    @Override
+    public void materializeAt(FixedWithNextNode materializeNode, List<ValueNode> values, boolean defaultValuesOnly, int lockCount) {
+        StructuredGraph graph = (StructuredGraph) graph();
+        NewInstanceNode newInstance = graph.add(new NewInstanceNode(type(), defaultValuesOnly, lockCount > 0));
+        materializeNode.replaceAtUsages(newInstance);
+        graph.addBeforeFixed(materializeNode, newInstance);
+        if (!defaultValuesOnly) {
+            for (int i = 0; i < entryCount(); i++) {
+                graph.addBeforeFixed(materializeNode, graph.add(new StoreFieldNode(newInstance, field(i), values.get(i))));
+            }
+        }
+        graph.removeFixed(materializeNode);
+    }
 }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -22,6 +22,8 @@
  */
 package com.oracle.graal.nodes.virtual;
 
+import java.util.*;
+
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
@@ -46,13 +48,15 @@
 
     public abstract String fieldName(int i);
 
-    public void materializeAt(@SuppressWarnings("unused") FixedNode fixed) {
-        // nothing to do in here - this method allows subclasses to respond to materialization
-    }
+    public abstract void materializeAt(FixedWithNextNode materializeNode, List<ValueNode> values, boolean defaultValuesOnly, int lockCount);
 
     public abstract int entryIndexForOffset(long constantOffset);
 
     public abstract Kind entryKind(int index);
 
     public abstract VirtualObjectNode duplicate();
+
+    public boolean hasIdentity() {
+        return true;
+    }
 }

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/BoxingEliminationPhase.java	Tue Apr 09 10:11:52 2013 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,142 +0,0 @@
-/*
- * 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.phases.common;
-
-import static com.oracle.graal.graph.iterators.NodePredicates.*;
-
-import java.util.*;
-
-import com.oracle.graal.api.meta.*;
-import com.oracle.graal.graph.*;
-import com.oracle.graal.graph.iterators.*;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.extended.*;
-import com.oracle.graal.nodes.type.*;
-import com.oracle.graal.nodes.virtual.*;
-import com.oracle.graal.phases.*;
-
-public class BoxingEliminationPhase extends Phase {
-
-    private final MetaAccessProvider metaAccess;
-
-    public BoxingEliminationPhase(MetaAccessProvider metaAccess) {
-        this.metaAccess = metaAccess;
-    }
-
-    @Override
-    protected void run(StructuredGraph graph) {
-        if (graph.getNodes(UnboxNode.class).isNotEmpty()) {
-
-            Map<PhiNode, PhiNode> phiReplacements = new HashMap<>();
-            for (UnboxNode unboxNode : graph.getNodes(UnboxNode.class)) {
-                tryEliminate(graph, unboxNode, phiReplacements);
-            }
-
-            new DeadCodeEliminationPhase().apply(graph);
-
-            for (BoxNode boxNode : graph.getNodes(BoxNode.class)) {
-                tryEliminate(boxNode);
-            }
-        }
-    }
-
-    private void tryEliminate(StructuredGraph graph, UnboxNode unboxNode, Map<PhiNode, PhiNode> phiReplacements) {
-        ValueNode unboxedValue = unboxedValue(unboxNode.source(), unboxNode.destinationKind(), phiReplacements);
-        if (unboxedValue != null) {
-            assert unboxedValue.kind() == unboxNode.kind();
-            unboxNode.replaceAtUsages(unboxedValue);
-            graph.removeFixed(unboxNode);
-        }
-    }
-
-    private PhiNode getReplacementPhi(PhiNode phiNode, Kind kind, Map<PhiNode, PhiNode> phiReplacements) {
-        if (!phiReplacements.containsKey(phiNode)) {
-            PhiNode result = null;
-            ObjectStamp stamp = phiNode.objectStamp();
-            if (stamp.nonNull() && stamp.isExactType()) {
-                ResolvedJavaType type = stamp.type();
-                if (type != null && type.equals(metaAccess.lookupJavaType(kind.toBoxedJavaClass()))) {
-                    StructuredGraph graph = (StructuredGraph) phiNode.graph();
-                    result = graph.add(new PhiNode(kind, phiNode.merge()));
-                    phiReplacements.put(phiNode, result);
-                    virtualizeUsages(phiNode, result, type, kind);
-                    int i = 0;
-                    for (ValueNode n : phiNode.values()) {
-                        ValueNode unboxedValue = unboxedValue(n, kind, phiReplacements);
-                        if (unboxedValue != null) {
-                            assert unboxedValue.kind() == kind;
-                            result.addInput(unboxedValue);
-                        } else {
-                            UnboxNode unboxNode = graph.add(new UnboxNode(kind, n));
-                            FixedNode pred = phiNode.merge().phiPredecessorAt(i);
-                            graph.addBeforeFixed(pred, unboxNode);
-                            result.addInput(unboxNode);
-                        }
-                        ++i;
-                    }
-                }
-            }
-        }
-        return phiReplacements.get(phiNode);
-    }
-
-    private ValueNode unboxedValue(ValueNode n, Kind kind, Map<PhiNode, PhiNode> phiReplacements) {
-        if (n instanceof BoxNode) {
-            BoxNode boxNode = (BoxNode) n;
-            return boxNode.source();
-        } else if (n instanceof PhiNode) {
-            PhiNode phiNode = (PhiNode) n;
-            return getReplacementPhi(phiNode, kind, phiReplacements);
-        } else {
-            return null;
-        }
-    }
-
-    private static void tryEliminate(BoxNode boxNode) {
-
-        assert boxNode.objectStamp().isExactType();
-        virtualizeUsages(boxNode, boxNode.source(), boxNode.objectStamp().type(), boxNode.getSourceKind());
-
-        if (boxNode.usages().filter(isNotA(VirtualState.class)).isNotEmpty()) {
-            // Elimination failed, because boxing object escapes.
-            return;
-        }
-
-        FrameState stateAfter = boxNode.stateAfter();
-        boxNode.setStateAfter(null);
-        stateAfter.safeDelete();
-
-        ((StructuredGraph) boxNode.graph()).removeFixed(boxNode);
-    }
-
-    private static void virtualizeUsages(ValueNode boxNode, ValueNode replacement, ResolvedJavaType exactType, Kind sourceKind) {
-        ValueNode virtualValueNode = null;
-        VirtualObjectNode virtualObjectNode = null;
-        for (Node n : boxNode.usages().filter(NodePredicates.isA(VirtualState.class)).snapshot()) {
-            if (virtualValueNode == null) {
-                virtualObjectNode = n.graph().unique(new BoxedVirtualObjectNode(exactType, sourceKind, replacement));
-            }
-            n.replaceFirstInput(boxNode, virtualObjectNode);
-        }
-    }
-}

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ExpandBoxingNodesPhase.java	Tue Apr 09 10:11:52 2013 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,47 +0,0 @@
-/*
- * 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.phases.common;
-
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.extended.*;
-import com.oracle.graal.phases.*;
-
-public class ExpandBoxingNodesPhase extends Phase {
-
-    private final BoxingMethodPool pool;
-
-    public ExpandBoxingNodesPhase(BoxingMethodPool pool) {
-        this.pool = pool;
-    }
-
-    @Override
-    protected void run(StructuredGraph graph) {
-        for (BoxNode boxNode : graph.getNodes(BoxNode.class)) {
-            boxNode.expand(pool);
-        }
-
-        for (UnboxNode unboxNode : graph.getNodes(UnboxNode.class)) {
-            unboxNode.expand(pool);
-        }
-    }
-}

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/IdentifyBoxingPhase.java	Tue Apr 09 10:11:52 2013 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,77 +0,0 @@
-/*
- * 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.phases.common;
-
-import java.lang.reflect.*;
-
-import com.oracle.graal.api.meta.*;
-import com.oracle.graal.graph.*;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.extended.*;
-import com.oracle.graal.nodes.java.*;
-import com.oracle.graal.phases.*;
-
-public class IdentifyBoxingPhase extends Phase {
-
-    private final BoxingMethodPool pool;
-
-    public IdentifyBoxingPhase(BoxingMethodPool pool) {
-        this.pool = pool;
-    }
-
-    @Override
-    protected void run(StructuredGraph graph) {
-        for (Invoke invoke : graph.getInvokes()) {
-            tryIntrinsify(invoke);
-        }
-    }
-
-    public void tryIntrinsify(Invoke invoke) {
-        if (!(invoke.callTarget() instanceof MethodCallTargetNode)) {
-            return;
-        }
-        MethodCallTargetNode callTarget = invoke.methodCallTarget();
-        ResolvedJavaMethod targetMethod = callTarget.targetMethod();
-        if (pool.isSpecialMethod(targetMethod)) {
-            assert callTarget.arguments().size() == 1 : "boxing/unboxing method must have exactly one argument";
-            Kind returnKind = callTarget.returnKind();
-            ValueNode sourceValue = callTarget.arguments().get(0);
-
-            // Check whether this is a boxing or an unboxing.
-            Node newNode = null;
-            if (returnKind == Kind.Object) {
-                // We have a boxing method here.
-                assert Modifier.isStatic(targetMethod.getModifiers()) : "boxing method must be static";
-                Kind sourceKind = targetMethod.getSignature().getParameterKind(0);
-                newNode = invoke.graph().add(new BoxNode(sourceValue, targetMethod.getDeclaringClass(), sourceKind, invoke.bci()));
-            } else {
-                // We have an unboxing method here.
-                assert !Modifier.isStatic(targetMethod.getModifiers()) : "unboxing method must be an instance method";
-                newNode = invoke.graph().add(new UnboxNode(returnKind, sourceValue));
-            }
-
-            // Intrinsify the invoke to the special node.
-            invoke.intrinsify(newNode);
-        }
-    }
-}

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java	Tue Apr 09 10:48:14 2013 +0200
@@ -68,7 +68,8 @@
     private static final DebugMetric metricInliningStoppedByMaxDesiredSize = Debug.metric("InliningStoppedByMaxDesiredSize");
     private static final DebugMetric metricInliningRuns = Debug.metric("Runs");
 
-    public InliningPhase(MetaAccessProvider runtime, Map<Invoke, Double> hints, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) {
+    public InliningPhase(MetaAccessProvider runtime, Map<Invoke, Double> hints, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan,
+                    OptimisticOptimizations optimisticOpts) {
         this(runtime, replacements, assumptions, cache, plan, createInliningPolicy(runtime, replacements, assumptions, optimisticOpts, hints), optimisticOpts);
     }
 
@@ -200,8 +201,14 @@
              * also getting queued in the compilation queue concurrently)
              */
 
-            if (GraalOptions.AlwaysInlineIntrinsics && onlyIntrinsics(replacements, info)) {
-                return InliningUtil.logInlinedMethod(info, "intrinsic");
+            if (GraalOptions.AlwaysInlineIntrinsics) {
+                if (onlyIntrinsics(replacements, info)) {
+                    return InliningUtil.logInlinedMethod(info, "intrinsic");
+                }
+            } else {
+                if (onlyForcedIntrinsics(replacements, info)) {
+                    return InliningUtil.logInlinedMethod(info, "intrinsic");
+                }
             }
 
             double bonus = 1;
@@ -347,6 +354,18 @@
             }
             return true;
         }
+
+        private static boolean onlyForcedIntrinsics(Replacements replacements, InlineInfo info) {
+            for (int i = 0; i < info.numberOfMethods(); i++) {
+                if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) {
+                    return false;
+                }
+                if (!replacements.isForcedSubstitution(info.methodAt(i))) {
+                    return false;
+                }
+            }
+            return true;
+        }
     }
 
     private static class CFInliningPolicy implements InliningPolicy {

--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Tue Apr 09 10:48:14 2013 +0200
@@ -116,6 +116,7 @@
     // Debug settings:
     public static boolean Debug                              = true;
     public static boolean DebugReplacements                  = ____;
+    public static boolean BootstrapReplacements              = ____;
     public static boolean PerThreadDebugValues               = ____;
     public static boolean SummarizeDebugValues               = ____;
     public static boolean SummarizePerPhase                  = ____;

--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java	Tue Apr 09 10:48:14 2013 +0200
@@ -39,7 +39,7 @@
 
         protected abstract void processBlock(Block block, StateT currentState);
 
-        protected abstract StateT merge(MergeNode merge, List<StateT> states);
+        protected abstract StateT merge(Block merge, List<StateT> states);
 
         protected abstract StateT cloneState(StateT oldState);
 
@@ -161,12 +161,11 @@
                     assert current.getPredecessors().size() > 1;
                     MergeNode merge = (MergeNode) current.getBeginNode();
                     ArrayList<StateT> mergedStates = new ArrayList<>(merge.forwardEndCount());
-                    for (int i = 0; i < merge.forwardEndCount(); i++) {
-                        StateT other = states.get(merge.forwardEndAt(i));
-                        assert other != null;
-                        mergedStates.add(other);
+                    for (Block predecessor : current.getPredecessors()) {
+                        EndNode end = (EndNode) predecessor.getEndNode();
+                        mergedStates.add(states.get(end));
                     }
-                    state = closure.merge(merge, mergedStates);
+                    state = closure.merge(current, mergedStates);
                 }
                 assert state != null;
             }

--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Tue Apr 09 10:48:14 2013 +0200
@@ -91,7 +91,7 @@
         }
 
         @Override
-        protected HashSet<FloatingReadNode> merge(MergeNode merge, List<HashSet<FloatingReadNode>> states) {
+        protected HashSet<FloatingReadNode> merge(Block merge, List<HashSet<FloatingReadNode>> states) {
             HashSet<FloatingReadNode> state = new HashSet<>(states.get(0));
             for (int i = 1; i < states.size(); i++) {
                 state.retainAll(states.get(i));

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/NodeIntrinsificationPhase.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/NodeIntrinsificationPhase.java	Tue Apr 09 10:48:14 2013 +0200
@@ -28,16 +28,18 @@
 import java.util.*;
 
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.Node.ConstantNodeParameter;
 import com.oracle.graal.graph.Node.NodeIntrinsic;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.nodes.util.*;
 import com.oracle.graal.phases.*;
-import com.oracle.graal.replacements.Snippet.*;
+import com.oracle.graal.replacements.Snippet.Fold;
 
 /**
  * Replaces calls to {@link NodeIntrinsic}s with nodes and calls to methods annotated with
@@ -46,20 +48,23 @@
 public class NodeIntrinsificationPhase extends Phase {
 
     private final MetaAccessProvider runtime;
-    private final BoxingMethodPool pool;
 
-    public NodeIntrinsificationPhase(MetaAccessProvider runtime, BoxingMethodPool pool) {
+    public NodeIntrinsificationPhase(MetaAccessProvider runtime) {
         this.runtime = runtime;
-        this.pool = pool;
     }
 
     @Override
     protected void run(StructuredGraph graph) {
+        ArrayList<Node> cleanUpReturnList = new ArrayList<>();
         for (Invoke i : graph.getInvokes()) {
             if (i.callTarget() instanceof MethodCallTargetNode) {
-                tryIntrinsify(i);
+                tryIntrinsify(i, cleanUpReturnList);
             }
         }
+
+        for (Node node : cleanUpReturnList) {
+            cleanUpReturnCheckCast(node);
+        }
     }
 
     public static Class<?>[] signatureToTypes(Signature signature, JavaType receiverType, ResolvedJavaType accessingClass) {
@@ -76,7 +81,7 @@
         return result;
     }
 
-    private boolean tryIntrinsify(Invoke invoke) {
+    private boolean tryIntrinsify(Invoke invoke, List<Node> cleanUpReturnList) {
         ResolvedJavaMethod target = invoke.methodCallTarget().targetMethod();
         NodeIntrinsic intrinsic = target.getAnnotation(Node.NodeIntrinsic.class);
         ResolvedJavaType declaringClass = target.getDeclaringClass();
@@ -103,7 +108,7 @@
             invoke.intrinsify(newInstance);
 
             // Clean up checkcast instructions inserted by javac if the return type is generic.
-            cleanUpReturnCheckCast(newInstance);
+            cleanUpReturnList.add(newInstance);
         } else if (target.getAnnotation(Fold.class) != null) {
             Class<?>[] parameterTypes = signatureToTypes(target.getSignature(), receiverType, declaringClass);
 
@@ -129,7 +134,7 @@
                 invoke.intrinsify(node);
 
                 // Clean up checkcast instructions inserted by javac if the return type is generic.
-                cleanUpReturnCheckCast(node);
+                cleanUpReturnList.add(node);
             } else {
                 // Remove the invoke
                 invoke.intrinsify(null);
@@ -154,7 +159,7 @@
             if (!invoke.methodCallTarget().isStatic()) {
                 parameterIndex--;
             }
-            ValueNode argument = tryBoxingElimination(parameterIndex, target, arguments.get(i));
+            ValueNode argument = arguments.get(i);
             if (folding || MetaUtil.getParameterAnnotation(ConstantNodeParameter.class, parameterIndex, target) != null) {
                 if (!(argument instanceof ConstantNode)) {
                     return null;
@@ -195,47 +200,6 @@
         return result;
     }
 
-    private ValueNode tryBoxingElimination(int parameterIndex, ResolvedJavaMethod target, ValueNode node) {
-        if (parameterIndex >= 0) {
-            Type type = target.getGenericParameterTypes()[parameterIndex];
-            if (type instanceof TypeVariable) {
-                TypeVariable typeVariable = (TypeVariable) type;
-                if (typeVariable.getBounds().length == 1) {
-                    Type boundType = typeVariable.getBounds()[0];
-                    if (boundType instanceof Class && ((Class) boundType).getSuperclass() == null) {
-                        // Unbound generic => try boxing elimination
-                        if (node.usages().count() == 2) {
-                            if (node instanceof Invoke) {
-                                Invoke invokeNode = (Invoke) node;
-                                MethodCallTargetNode callTarget = invokeNode.methodCallTarget();
-                                if (pool.isBoxingMethod(callTarget.targetMethod())) {
-                                    FrameState stateAfter = invokeNode.stateAfter();
-                                    assert stateAfter.usages().count() == 1;
-                                    invokeNode.node().replaceAtUsages(null);
-                                    ValueNode result = callTarget.arguments().get(0);
-                                    StructuredGraph graph = (StructuredGraph) node.graph();
-                                    if (invokeNode instanceof InvokeWithExceptionNode) {
-                                        // Destroy exception edge & clear stateAfter.
-                                        InvokeWithExceptionNode invokeWithExceptionNode = (InvokeWithExceptionNode) invokeNode;
-
-                                        invokeWithExceptionNode.killExceptionEdge();
-                                        graph.removeSplit(invokeWithExceptionNode, invokeWithExceptionNode.next());
-                                    } else {
-                                        graph.removeFixed((InvokeNode) invokeNode);
-                                    }
-                                    stateAfter.safeDelete();
-                                    GraphUtil.propagateKill(callTarget);
-                                    return result;
-                                }
-                            }
-                        }
-                    }
-                }
-            }
-        }
-        return node;
-    }
-
     private static Class asBoxedType(Class type) {
         if (!type.isPrimitive()) {
             return type;
@@ -379,32 +343,25 @@
                     if (checkCastUsage instanceof ValueAnchorNode) {
                         ValueAnchorNode valueAnchorNode = (ValueAnchorNode) checkCastUsage;
                         graph.removeFixed(valueAnchorNode);
+                    } else if (checkCastUsage instanceof UnboxNode) {
+                        UnboxNode unbox = (UnboxNode) checkCastUsage;
+                        unbox.replaceAtUsages(newInstance);
+                        graph.removeFixed(unbox);
                     } else if (checkCastUsage instanceof MethodCallTargetNode) {
                         MethodCallTargetNode checkCastCallTarget = (MethodCallTargetNode) checkCastUsage;
-                        if (pool.isUnboxingMethod(checkCastCallTarget.targetMethod())) {
-                            Invoke invokeNode = checkCastCallTarget.invoke();
-                            invokeNode.node().replaceAtUsages(newInstance);
-                            if (invokeNode instanceof InvokeWithExceptionNode) {
-                                // Destroy exception edge & clear stateAfter.
-                                InvokeWithExceptionNode invokeWithExceptionNode = (InvokeWithExceptionNode) invokeNode;
-
-                                invokeWithExceptionNode.killExceptionEdge();
-                                graph.removeSplit(invokeWithExceptionNode, invokeWithExceptionNode.next());
-                            } else {
-                                graph.removeFixed((InvokeNode) invokeNode);
-                            }
-                            checkCastCallTarget.safeDelete();
-                        } else {
-                            assert checkCastCallTarget.targetMethod().getAnnotation(NodeIntrinsic.class) != null : "checkcast at " + sourceLocation(checkCastNode) +
-                                            " not used by an unboxing method or node intrinsic, but by a call at " + sourceLocation(checkCastCallTarget.usages().first()) + " to " +
-                                            checkCastCallTarget.targetMethod();
-                            checkCastUsage.replaceFirstInput(checkCastNode, checkCastNode.object());
-                        }
+                        assert checkCastCallTarget.targetMethod().getAnnotation(NodeIntrinsic.class) != null : "checkcast at " + sourceLocation(checkCastNode) +
+                                        " not used by an unboxing method or node intrinsic, but by a call at " + sourceLocation(checkCastCallTarget.usages().first()) + " to " +
+                                        checkCastCallTarget.targetMethod();
+                        checkCastUsage.replaceFirstInput(checkCastNode, checkCastNode.object());
                     } else if (checkCastUsage instanceof FrameState) {
                         checkCastUsage.replaceFirstInput(checkCastNode, null);
                     } else if (checkCastUsage instanceof ReturnNode && checkCastNode.object().stamp() == StampFactory.forNodeIntrinsic()) {
                         checkCastUsage.replaceFirstInput(checkCastNode, checkCastNode.object());
+                    } else if (checkCastUsage instanceof IsNullNode) {
+                        assert checkCastUsage.usages().count() == 1 && checkCastUsage.usages().first().predecessor() == checkCastNode;
+                        graph.replaceFloating((FloatingNode) checkCastUsage, LogicConstantNode.contradiction(graph));
                     } else {
+                        Debug.dump(graph, "exception");
                         assert false : sourceLocation(checkCastUsage) + " has unexpected usage " + checkCastUsage + " of checkcast at " + sourceLocation(checkCastNode);
                     }
                 }

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsImpl.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsImpl.java	Tue Apr 09 10:48:14 2013 +0200
@@ -37,7 +37,6 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.java.*;
 import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.java.MethodCallTargetNode.InvokeKind;
 import com.oracle.graal.nodes.spi.*;
@@ -53,8 +52,6 @@
     protected final TargetDescription target;
     protected final Assumptions assumptions;
 
-    private BoxingMethodPool pool;
-
     /**
      * The preprocessed replacement graphs.
      */
@@ -65,6 +62,7 @@
     private final Map<ResolvedJavaMethod, ResolvedJavaMethod> registeredMethodSubstitutions;
     private final Set<ResolvedJavaMethod> registeredSnippets;
     private final Map<ResolvedJavaMethod, Class<? extends FixedWithNextNode>> registerMacroSubstitutions;
+    private final Set<ResolvedJavaMethod> forcedSubstitutions;
 
     public ReplacementsImpl(MetaAccessProvider runtime, Assumptions assumptions, TargetDescription target) {
         this.runtime = runtime;
@@ -74,6 +72,7 @@
         this.registeredMethodSubstitutions = new HashMap<>();
         this.registeredSnippets = new HashSet<>();
         this.registerMacroSubstitutions = new HashMap<>();
+        this.forcedSubstitutions = new HashSet<>();
     }
 
     public void registerSnippets(Class<?> snippets) {
@@ -149,7 +148,10 @@
                 Class[] originalParameters = originalParameters(substituteMethod, methodSubstitution.signature(), methodSubstitution.isStatic());
                 Member originalMethod = originalMethod(classSubstitution, methodSubstitution.optional(), originalName, originalParameters);
                 if (originalMethod != null) {
-                    registerMethodSubstitution(originalMethod, substituteMethod);
+                    ResolvedJavaMethod original = registerMethodSubstitution(originalMethod, substituteMethod);
+                    if (original != null && methodSubstitution.isForcedInlining()) {
+                        forcedSubstitutions.add(original);
+                    }
                 }
             }
             if (macroSubstitution != null) {
@@ -157,7 +159,10 @@
                 Class[] originalParameters = originalParameters(substituteMethod, macroSubstitution.signature(), macroSubstitution.isStatic());
                 Member originalMethod = originalMethod(classSubstitution, macroSubstitution.optional(), originalName, originalParameters);
                 if (originalMethod != null) {
-                    registerMacroSubstitution(originalMethod, macroSubstitution.macro());
+                    ResolvedJavaMethod original = registerMacroSubstitution(originalMethod, macroSubstitution.macro());
+                    if (original != null && macroSubstitution.isForcedInlining()) {
+                        forcedSubstitutions.add(original);
+                    }
                 }
             }
         }
@@ -168,8 +173,9 @@
      * 
      * @param originalMember a method or constructor being substituted
      * @param substituteMethod the substitute method
+     * @return the original method
      */
-    protected void registerMethodSubstitution(Member originalMember, Method substituteMethod) {
+    protected ResolvedJavaMethod registerMethodSubstitution(Member originalMember, Method substituteMethod) {
         ResolvedJavaMethod substitute = runtime.lookupJavaMethod(substituteMethod);
         ResolvedJavaMethod original;
         if (originalMember instanceof Method) {
@@ -180,6 +186,7 @@
         Debug.log("substitution: " + MetaUtil.format("%H.%n(%p)", original) + " --> " + MetaUtil.format("%H.%n(%p)", substitute));
 
         registeredMethodSubstitutions.put(original, substitute);
+        return original;
     }
 
     /**
@@ -187,8 +194,9 @@
      * 
      * @param originalMethod a method or constructor being substituted
      * @param macro the substitute macro node class
+     * @return the original method
      */
-    protected void registerMacroSubstitution(Member originalMethod, Class<? extends FixedWithNextNode> macro) {
+    protected ResolvedJavaMethod registerMacroSubstitution(Member originalMethod, Class<? extends FixedWithNextNode> macro) {
         ResolvedJavaMethod originalJavaMethod;
         if (originalMethod instanceof Method) {
             originalJavaMethod = runtime.lookupJavaMethod((Method) originalMethod);
@@ -196,6 +204,7 @@
             originalJavaMethod = runtime.lookupJavaConstructor((Constructor) originalMethod);
         }
         registerMacroSubstitutions.put(originalJavaMethod, macro);
+        return originalJavaMethod;
     }
 
     private SnippetInliningPolicy inliningPolicy(ResolvedJavaMethod method) {
@@ -205,7 +214,7 @@
             policyClass = snippet.inlining();
         }
         if (policyClass == SnippetInliningPolicy.class) {
-            return new DefaultSnippetInliningPolicy(runtime, pool());
+            return new DefaultSnippetInliningPolicy(runtime);
         }
         try {
             return policyClass.getConstructor().newInstance();
@@ -284,7 +293,7 @@
          * Does final processing of a snippet graph.
          */
         protected void finalizeGraph(StructuredGraph graph) {
-            new NodeIntrinsificationPhase(runtime, pool()).apply(graph);
+            new NodeIntrinsificationPhase(runtime).apply(graph);
             assert SnippetTemplate.hasConstantParameter(method) || NodeIntrinsificationVerificationPhase.verify(graph);
 
             if (original == null) {
@@ -318,7 +327,6 @@
             Debug.dump(graph, "%s: %s", methodToParse.getName(), GraphBuilderPhase.class.getSimpleName());
 
             new WordTypeVerificationPhase(runtime, target.wordKind).apply(graph);
-            new NodeIntrinsificationPhase(runtime, pool()).apply(graph);
 
             return graph;
         }
@@ -340,7 +348,7 @@
          * Called after all inlining for a given graph is complete.
          */
         protected void afterInlining(StructuredGraph graph) {
-            new NodeIntrinsificationPhase(runtime, pool()).apply(graph);
+            new NodeIntrinsificationPhase(runtime).apply(graph);
 
             new WordTypeRewriterPhase(runtime, target.wordKind).apply(graph);
 
@@ -367,7 +375,13 @@
                     substituteCallsOriginal = true;
                 } else {
                     if ((callTarget.invokeKind() == InvokeKind.Static || callTarget.invokeKind() == InvokeKind.Special) && policy.shouldInline(callee, methodToParse)) {
-                        StructuredGraph targetGraph = parseGraph(callee, policy);
+                        StructuredGraph targetGraph;
+                        StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(ReplacementsImpl.this, callee);
+                        if (intrinsicGraph != null && policy.shouldUseReplacement(callee, methodToParse)) {
+                            targetGraph = intrinsicGraph;
+                        } else {
+                            targetGraph = parseGraph(callee, policy);
+                        }
                         InliningUtil.inline(invoke, targetGraph, true);
                         Debug.dump(graph, "after inlining %s", callee);
                         afterInline(graph, targetGraph);
@@ -471,11 +485,17 @@
         }
     }
 
-    protected BoxingMethodPool pool() {
-        if (pool == null) {
-            // A race to create the pool is ok
-            pool = new BoxingMethodPool(runtime);
-        }
-        return pool;
+    @Override
+    public Collection<ResolvedJavaMethod> getAllReplacements() {
+        HashSet<ResolvedJavaMethod> result = new HashSet<>();
+        result.addAll(registeredSnippets);
+        result.addAll(registeredMethodSubstitutions.keySet());
+        result.addAll(registerMacroSubstitutions.keySet());
+        return result;
+    }
+
+    @Override
+    public boolean isForcedSubstitution(ResolvedJavaMethod method) {
+        return forcedSubstitutions.contains(method);
     }
 }

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/Snippet.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/Snippet.java	Tue Apr 09 10:48:14 2013 +0200
@@ -27,7 +27,6 @@
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.Node.NodeIntrinsic;
-import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.replacements.nodes.*;
 import com.oracle.graal.word.*;
@@ -55,6 +54,13 @@
          * Determines if {@code method} should be inlined into {@code caller}.
          */
         boolean shouldInline(ResolvedJavaMethod method, ResolvedJavaMethod caller);
+
+        /**
+         * Determines if {@code method} should be inlined using its replacement graph.
+         * 
+         * @return true if the replacement graph should be used, false for normal inlining.
+         */
+        boolean shouldUseReplacement(ResolvedJavaMethod callee, ResolvedJavaMethod methodToParse);
     }
 
     /**
@@ -70,11 +76,9 @@
     public static class DefaultSnippetInliningPolicy implements SnippetInliningPolicy {
 
         private final MetaAccessProvider metaAccess;
-        private final BoxingMethodPool pool;
 
-        public DefaultSnippetInliningPolicy(MetaAccessProvider metaAccess, BoxingMethodPool pool) {
+        public DefaultSnippetInliningPolicy(MetaAccessProvider metaAccess) {
             this.metaAccess = metaAccess;
-            this.pool = pool;
         }
 
         @Override
@@ -89,16 +93,18 @@
                 return false;
             }
             if (metaAccess.lookupJavaType(Throwable.class).isAssignableFrom(method.getDeclaringClass())) {
-                if (method.getName().equals("<init>")) {
+                if (method.isConstructor()) {
                     return false;
                 }
             }
             if (method.getAnnotation(Word.Operation.class) != null) {
                 return false;
             }
-            if (pool.isSpecialMethod(method)) {
-                return false;
-            }
+            return true;
+        }
+
+        @Override
+        public boolean shouldUseReplacement(ResolvedJavaMethod callee, ResolvedJavaMethod methodToParse) {
             return true;
         }
     }

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java	Tue Apr 09 10:48:14 2013 +0200
@@ -36,7 +36,6 @@
 import com.oracle.graal.loop.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
-import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
@@ -291,7 +290,7 @@
         Debug.dump(snippetCopy, "Before specialization");
         if (!nodeReplacements.isEmpty()) {
             // Do deferred intrinsification of node intrinsics
-            new NodeIntrinsificationPhase(runtime, new BoxingMethodPool(runtime)).apply(snippetCopy);
+            new NodeIntrinsificationPhase(runtime).apply(snippetCopy);
             new WordTypeRewriterPhase(runtime, target.wordKind).apply(snippetCopy);
 
             new CanonicalizerPhase(runtime, replacements.getAssumptions(), 0, null).apply(snippetCopy);

--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/MaterializeObjectNode.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/MaterializeObjectNode.java	Tue Apr 09 10:48:14 2013 +0200
@@ -25,7 +25,6 @@
 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.spi.*;
 import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.nodes.virtual.*;
@@ -44,10 +43,18 @@
         this.values = new NodeInputList<>(this, virtualObject.entryCount());
     }
 
-    public NodeInputList<ValueNode> values() {
+    public NodeInputList<ValueNode> getValues() {
         return values;
     }
 
+    public VirtualObjectNode getVirtualObject() {
+        return virtualObject;
+    }
+
+    public int getLockCount() {
+        return lockCount;
+    }
+
     @Override
     public ValueNode length() {
         assert virtualObject.type().isArray();
@@ -73,38 +80,7 @@
 
     @Override
     public void lower(LoweringTool tool) {
-        StructuredGraph graph = (StructuredGraph) graph();
-
-        boolean defaultValuesOnly = isDefault();
-
-        if (virtualObject instanceof VirtualInstanceNode) {
-            VirtualInstanceNode virtual = (VirtualInstanceNode) virtualObject;
-
-            NewInstanceNode newInstance = graph.add(new NewInstanceNode(virtual.type(), defaultValuesOnly, lockCount > 0));
-            this.replaceAtUsages(newInstance);
-            graph.addBeforeFixed(this, newInstance);
-
-            if (!defaultValuesOnly) {
-                for (int i = 0; i < virtual.entryCount(); i++) {
-                    graph.addBeforeFixed(this, graph.add(new StoreFieldNode(newInstance, virtual.field(i), values.get(i))));
-                }
-            }
-        } else {
-            assert virtualObject instanceof VirtualArrayNode;
-            VirtualArrayNode virtual = (VirtualArrayNode) virtualObject;
-
-            ResolvedJavaType element = virtual.componentType();
-            NewArrayNode newArray = graph.add(new NewArrayNode(element, ConstantNode.forInt(virtual.entryCount(), graph), defaultValuesOnly, lockCount > 0));
-            this.replaceAtUsages(newArray);
-            graph.addBeforeFixed(this, newArray);
-
-            if (!defaultValuesOnly) {
-                for (int i = 0; i < virtual.entryCount(); i++) {
-                    graph.addBeforeFixed(this, graph.add(new StoreIndexedNode(newArray, ConstantNode.forInt(i, graph), element.getKind(), values.get(i))));
-                }
-            }
-        }
-        graph.removeFixed(this);
+        virtualObject.materializeAt(this, values, isDefault(), lockCount);
     }
 
     @Override

--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Tue Apr 09 10:48:14 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;
+    }
+
 }

--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java	Tue Apr 09 10:48:14 2013 +0200
@@ -73,48 +73,47 @@
         public abstract void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes);
     }
 
-    private Effect[] effects = new Effect[16];
-    private int[] level = new int[16];
+    private static final Effect[] EMPTY_ARRAY = new Effect[0];
+
+    private Effect[] effects = EMPTY_ARRAY;
     private int size;
-    private int currentLevel;
+
+    private void enlarge(int elements) {
+        int length = effects.length;
+        if (size + elements > length) {
+            while (size + elements > length) {
+                length = Math.max(length * 2, 4);
+            }
+            effects = Arrays.copyOf(effects, length);
+        }
+    }
 
     public void add(Effect effect) {
-        if (effects.length == size) {
-            effects = Arrays.copyOf(effects, effects.length * 2);
-            level = Arrays.copyOf(level, effects.length);
-        }
-        level[size] = currentLevel;
+        assert effect != null;
+        enlarge(1);
         effects[size++] = effect;
     }
 
     public void addAll(Collection<? extends Effect> list) {
-        int length = effects.length;
-        if (size + list.size() > length) {
-            while (size + list.size() > length) {
-                length *= 2;
-            }
-            effects = Arrays.copyOf(effects, length);
-            level = Arrays.copyOf(level, effects.length);
-        }
+        enlarge(list.size());
         for (Effect effect : list) {
-            level[size] = currentLevel;
+            assert effect != null;
             effects[size++] = effect;
         }
     }
 
     public void addAll(EffectList list) {
-        int length = effects.length;
-        if (size + list.size > length) {
-            while (size + list.size > length) {
-                length *= 2;
-            }
-            effects = Arrays.copyOf(effects, length);
-            level = Arrays.copyOf(level, effects.length);
-        }
-        for (Effect effect : list) {
-            level[size] = currentLevel;
-            effects[size++] = effect;
-        }
+        enlarge(list.size);
+        System.arraycopy(list.effects, 0, effects, size, list.size);
+        size += list.size;
+    }
+
+    public void insertAll(EffectList list, int position) {
+        assert position >= 0 && position <= size;
+        enlarge(list.size);
+        System.arraycopy(effects, position, effects, position + list.size, size - position);
+        System.arraycopy(list.effects, 0, effects, position, list.size);
+        size += list.size;
     }
 
     public int checkpoint() {
@@ -154,14 +153,6 @@
         };
     }
 
-    public void incLevel() {
-        currentLevel++;
-    }
-
-    public void decLevel() {
-        currentLevel--;
-    }
-
     public Effect get(int index) {
         if (index >= size) {
             throw new IndexOutOfBoundsException();
@@ -169,13 +160,6 @@
         return effects[index];
     }
 
-    public int levelAt(int index) {
-        if (index >= size) {
-            throw new IndexOutOfBoundsException();
-        }
-        return level[index];
-    }
-
     public void clear() {
         size = 0;
     }
@@ -190,9 +174,6 @@
         for (int i = 0; i < size(); i++) {
             Effect effect = get(i);
             if (effect.isVisible()) {
-                for (int i2 = 0; i2 < levelAt(i); i2++) {
-                    str.append("    ");
-                }
                 str.append(effect).append('\n');
             }
         }

--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Tue Apr 09 10:48:14 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);
             }
         });
@@ -142,7 +142,7 @@
                 graph.addBeforeFixed(position, graph.add(node));
                 node.setProbability(position.probability());
                 for (int i = 0; i < values.length; i++) {
-                    node.values().set(i, values[i]);
+                    node.getValues().set(i, values[i]);
                 }
             }
         });
@@ -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);
             }
         });

--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java	Tue Apr 09 10:48:14 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;
+    }
 }

--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Tue Apr 09 10:48:14 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();

--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Tue Apr 09 10:11:52 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Tue Apr 09 10:48:14 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,89 +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);
 
-            List<BlockState> loopEndStates = info.endStates;
-            List<Block> predecessors = loop.header.getPredecessors();
-            HashSet<VirtualObjectNode> additionalMaterializations = new HashSet<>();
-            HashSet<ReadCacheEntry> additionalKilledReads = new HashSet<>();
-            int oldPhiCount = phis.size();
-            for (int i = 1; i < predecessors.size(); i++) {
-                processLoopEnd(loop.loopBegin(), (LoopEndNode) predecessors.get(i).getEndNode(), state, loopEndStates.get(i - 1), 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()) {
@@ -548,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");
                         }
                     }
                 }
@@ -557,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;
                 }
             }
         }
@@ -573,181 +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);
+
+            /*
+             * 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.
+             */
 
-    private void processLoopEnd(LoopBeginNode loopBegin, LoopEndNode loopEnd, BlockState initialState, BlockState loopEndState, GraphEffectList successEffects,
-                    Set<VirtualObjectNode> additionalMaterializations, HashSet<ReadCacheEntry> additionalKilledReads, HashSet<PhiDesc> phis) {
-        assert loopEnd.loopBegin() == loopBegin;
-        boolean materialized;
-        do {
-            materialized = false;
-            for (ObjectState state : initialState.getStates()) {
-                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();
-                                            loopEndState.materializeBefore(loopEnd, 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 {
+                            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 {
-                        additionalMaterializations.add(state.virtual);
+                        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);
 
-                    ObjectState loopEndObj = loopEndState.getObjectState(phi.valueAt(loopEnd));
-                    if (loopEndObj == null || !loopEndObj.isVirtual()) {
-                        if (loopEndObj != null) {
-                            successEffects.setPhiInput(phi, loopBegin.phiPredecessorIndex(loopEnd), loopEndObj.getMaterializedValue());
-                        }
-                        if (!initialMaterialized) {
-                            additionalMaterializations.add(initialObj.virtual);
-                        }
-                    } else {
-                        if (initialMaterialized) {
-                            loopEndState.materializeBefore(loopEnd, loopEndObj.virtual, EscapeState.Global, successEffects);
-                            materialized = true;
-                        } else {
-                            if (loopEndObj.virtual != initialObj.virtual) {
-                                additionalMaterializations.add(initialObj.virtual);
+                        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);
+                            }
+                            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()) {
-            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));
-                            }
+        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;
+                    }
+                }
+                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);
                         }
                     }
-                } else {
-                    // endState.materializedValue != null
-                    assert !additionalMaterializations.isEmpty();
-                }
-            } 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);
-                    }
+
                 }
             }
         }
 
-        for (Map.Entry<ReadCacheEntry, ValueNode> entry : initialState.getReadCache().entrySet()) {
-            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);
         }
     }
 }