changeset 8627:75db7afee829

implemented lazy installation of replacements (GRAAL-137)
author Doug Simon <doug.simon@oracle.com>
date Wed, 03 Apr 2013 21:51:44 +0200
parents c1c0ca020d98
children 77de2f3df379
files graal/com.oracle.graal.api.replacements/src/com/oracle/graal/api/replacements/MacroSubstitution.java graal/com.oracle.graal.api.replacements/src/com/oracle/graal/api/replacements/Replacements.java graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotRuntime.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/CompilationTask.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotGraalRuntime.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotRuntimeCallTarget.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/bridge/VMToCompilerImpl.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ArrayCopyNode.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/CheckCastSnippets.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/HotSpotInstalledCodeIntrinsics.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/InstanceOfSnippets.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/MonitorSnippets.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/NewObjectSnippets.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ObjectCloneNode.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/WriteBarrierSnippets.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/NewArrayStub.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/NewInstanceStub.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/Stub.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java graal/com.oracle.graal.replacements.amd64/src/com/oracle/graal/replacements/amd64/AMD64ConvertSnippets.java graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/GraalMethodSubstitutions.java graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/InstanceOfSnippetsTemplates.java graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/MacroSubstitution.java graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsInstaller.java graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsProvider.java graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java make/build-graal.xml mx/projects
diffstat 29 files changed, 563 insertions(+), 436 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.api.replacements/src/com/oracle/graal/api/replacements/MacroSubstitution.java	Wed Apr 03 21:51:44 2013 +0200
@@ -0,0 +1,69 @@
+/*
+ * 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.api.replacements;
+
+import java.lang.annotation.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.nodes.*;
+
+/**
+ * Denotes a macro substitute method. This replaces a method invocation with an instance of the
+ * specified node class.
+ * 
+ * A macro substitution can be combined with a normal substitution, so that the macro node can be
+ * replaced with the actual substitution code during lowering.
+ */
+@Retention(RetentionPolicy.RUNTIME)
+@Target(ElementType.METHOD)
+public @interface MacroSubstitution {
+
+    /**
+     * Gets the name of the substituted method.
+     * <p>
+     * If the default value is specified for this element, then the name of the substituted method
+     * is same as the substitute method.
+     */
+    String value() default "";
+
+    /**
+     * Determines if the substituted method is static.
+     */
+    boolean isStatic() default true;
+
+    /**
+     * Gets the {@linkplain MetaUtil#signatureToMethodDescriptor signature} of the substituted
+     * method.
+     * <p>
+     * If the default value is specified for this element, then the signature of the substituted
+     * method is the same as the substitute method.
+     */
+    String signature() default "";
+
+    /**
+     * The node class with which the method invocation should be replaced. It needs to be a subclass
+     * of {@link FixedWithNextNode}, and it is expected to provide a public constructor that takes
+     * an {@link InvokeNode} as a parameter.
+     */
+    Class<? extends FixedWithNextNode> macro();
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.api.replacements/src/com/oracle/graal/api/replacements/Replacements.java	Wed Apr 03 21:51:44 2013 +0200
@@ -0,0 +1,72 @@
+/*
+ * 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.api.replacements;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.nodes.*;
+
+/**
+ * Interface for managing replacements.
+ */
+public interface Replacements {
+
+    /**
+     * Gets the snippet graph derived from a given method.
+     * 
+     * @return the snippet graph, if any, that is derived from {@code method}
+     */
+    StructuredGraph getSnippet(ResolvedJavaMethod method);
+
+    /**
+     * Gets the graph that is a substitution for a given method.
+     * 
+     * @return the graph, if any, that is a substitution for {@code method}
+     */
+    StructuredGraph getMethodSubstitution(ResolvedJavaMethod method);
+
+    /**
+     * Gets the node class with which a method invocation should be replaced.
+     * 
+     * @param method target of an invocation
+     * @return the {@linkplain MacroSubstitution#macro() macro node class} associated with
+     *         {@code method} or null if there is no such association
+     */
+    Class<? extends FixedWithNextNode> getMacroSubstitution(ResolvedJavaMethod method);
+
+    /**
+     * Gets the assumptions with which replacement graphs are preprocessed.
+     */
+    Assumptions getAssumptions();
+
+    /**
+     * Registers all the snippet methods defined by a given class.
+     */
+    void registerSnippets(Class<?> snippets);
+
+    /**
+     * Registers all the {@linkplain MethodSubstitution method} and {@linkplain MacroSubstitution
+     * macro} substitutions defined by a given class.
+     */
+    void registerSubstitutions(Class<?> substitutions);
+}
--- a/graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotRuntime.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotRuntime.java	Wed Apr 03 21:51:44 2013 +0200
@@ -37,23 +37,22 @@
 import static com.oracle.graal.hotspot.nodes.ThreadIsInterruptedStubCall.*;
 import static com.oracle.graal.hotspot.nodes.VMErrorNode.*;
 import static com.oracle.graal.hotspot.nodes.VerifyOopStubCall.*;
+import static com.oracle.graal.hotspot.nodes.WriteBarrierPostStubCall.*;
+import static com.oracle.graal.hotspot.nodes.WriteBarrierPreStubCall.*;
 import static com.oracle.graal.hotspot.replacements.AESCryptSubstitutions.DecryptBlockStubCall.*;
 import static com.oracle.graal.hotspot.replacements.AESCryptSubstitutions.EncryptBlockStubCall.*;
 import static com.oracle.graal.hotspot.replacements.CipherBlockChainingSubstitutions.DecryptAESCryptStubCall.*;
 import static com.oracle.graal.hotspot.replacements.CipherBlockChainingSubstitutions.EncryptAESCryptStubCall.*;
-import static com.oracle.graal.hotspot.nodes.WriteBarrierPostStubCall.*;
-import static com.oracle.graal.hotspot.nodes.WriteBarrierPreStubCall.*;
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
-import com.oracle.graal.compiler.target.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.hotspot.*;
 import com.oracle.graal.hotspot.meta.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.replacements.amd64.*;
-import com.oracle.graal.replacements.*;
 
 public class AMD64HotSpotRuntime extends HotSpotRuntime {
 
@@ -208,10 +207,10 @@
     private AMD64ConvertSnippets.Templates convertSnippets;
 
     @Override
-    public void installReplacements(Backend backend, ReplacementsInstaller installer, Assumptions assumptions) {
-        installer.installSnippets(AMD64ConvertSnippets.class);
-        convertSnippets = new AMD64ConvertSnippets.Templates(this, assumptions, graalRuntime.getTarget());
-        super.installReplacements(backend, installer, assumptions);
+    public void registerReplacements(Replacements replacements) {
+        replacements.registerSnippets(AMD64ConvertSnippets.class);
+        convertSnippets = new AMD64ConvertSnippets.Templates(this, replacements, graalRuntime.getTarget());
+        super.registerReplacements(replacements);
     }
 
     @Override
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/CompilationTask.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/CompilationTask.java	Wed Apr 03 21:51:44 2013 +0200
@@ -29,6 +29,7 @@
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.api.replacements.*;
+import com.oracle.graal.api.runtime.*;
 import com.oracle.graal.compiler.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.debug.internal.*;
@@ -143,7 +144,8 @@
                     @Override
                     public CompilationResult call() throws Exception {
                         graalRuntime.evictDeoptedGraphs();
-                        StructuredGraph graph = (StructuredGraph) method.getCompilerStorage().get(MethodSubstitution.class);
+                        Replacements replacements = Graal.getRequiredCapability(Replacements.class);
+                        StructuredGraph graph = replacements.getMethodSubstitution(method);
                         if (graph == null || entryBCI != INVOCATION_ENTRY_BCI) {
                             graph = new StructuredGraph(method, entryBCI);
                         } else {
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotGraalRuntime.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotGraalRuntime.java	Wed Apr 03 21:51:44 2013 +0200
@@ -29,6 +29,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.api.runtime.*;
 import com.oracle.graal.compiler.target.*;
 import com.oracle.graal.hotspot.bridge.*;
@@ -119,6 +120,7 @@
 
     protected final HotSpotRuntime runtime;
     protected final TargetDescription target;
+    protected final Replacements replacements;
 
     private HotSpotRuntimeInterpreterInterface runtimeInterpreterInterface;
     private volatile HotSpotGraphCache cache;
@@ -148,6 +150,11 @@
 
         runtime = createRuntime();
 
+        // Replacements cannot have speculative optimizations since they have
+        // to be valid for the entire run of the VM.
+        Assumptions assumptions = new Assumptions(false);
+        replacements = new HotSpotReplacementsInstaller(runtime, assumptions, runtime.getGraalRuntime().getTarget());
+
         backend = createBackend();
         GraalOptions.StackShadowPages = config.stackShadowPages;
         if (GraalOptions.CacheGraphs) {
@@ -269,6 +276,9 @@
         if (clazz == HotSpotRuntime.class) {
             return (T) runtime;
         }
+        if (clazz == Replacements.class) {
+            return (T) replacements;
+        }
         if (clazz == Backend.class) {
             return (T) getBackend();
         }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotRuntimeCallTarget.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotRuntimeCallTarget.java	Wed Apr 03 21:51:44 2013 +0200
@@ -24,6 +24,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.compiler.target.*;
 import com.oracle.graal.hotspot.bridge.*;
 import com.oracle.graal.hotspot.stubs.*;
 
@@ -79,17 +80,14 @@
     }
 
     public void setStub(Stub stub) {
-        assert address == 0L : "cannot stub for linkage that already has an address: " + this;
+        assert address == 0L : "cannot set stub for linkage that already has an address: " + this;
         this.stub = stub;
     }
 
-    public void setAddress(long address) {
-        assert this.address == 0L : "cannot re-initialize address of " + this;
-        this.address = address;
-    }
-
-    public long getAddress() {
-        assert address != 0L : "address not yet initialized for " + this;
-        return address;
+    public void finalizeAddress(Backend backend) {
+        if (address == 0) {
+            assert stub != null : "linkage without an address must be a stub";
+            address = stub.getAddress(backend);
+        }
     }
 }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/bridge/VMToCompilerImpl.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/bridge/VMToCompilerImpl.java	Wed Apr 03 21:51:44 2013 +0200
@@ -34,8 +34,8 @@
 import java.util.concurrent.*;
 import java.util.concurrent.atomic.*;
 
-import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.debug.internal.*;
 import com.oracle.graal.hotspot.*;
@@ -146,19 +146,16 @@
 
         // Install intrinsics.
         final HotSpotRuntime runtime = graalRuntime.getCapability(HotSpotRuntime.class);
+        final Replacements replacements = graalRuntime.getCapability(Replacements.class);
         if (GraalOptions.Intrinsify) {
-            Debug.scope("InstallReplacements", new Object[]{new DebugDumpScope("InstallReplacements")}, new Runnable() {
+            Debug.scope("RegisterReplacements", new Object[]{new DebugDumpScope("RegisterReplacements")}, new Runnable() {
 
                 @Override
                 public void run() {
-                    // Replacements cannot have speculative optimizations since they have
-                    // to be valid for the entire run of the VM.
-                    Assumptions assumptions = new Assumptions(false);
-                    ReplacementsInstaller installer = new HotSpotReplacementsInstaller(runtime, assumptions, runtime.getGraalRuntime().getTarget());
                     for (ReplacementsProvider provider : ServiceLoader.loadInstalled(ReplacementsProvider.class)) {
-                        provider.installReplacements(installer);
+                        provider.registerReplacements(replacements);
                     }
-                    runtime.installReplacements(graalRuntime.getBackend(), installer, assumptions);
+                    runtime.registerReplacements(replacements);
                 }
             });
 
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java	Wed Apr 03 21:51:44 2013 +0200
@@ -30,12 +30,14 @@
 import static com.oracle.graal.api.meta.Value.*;
 import static com.oracle.graal.graph.UnsafeAccess.*;
 import static com.oracle.graal.hotspot.HotSpotGraalRuntime.*;
+import static com.oracle.graal.hotspot.nodes.NewArrayStubCall.*;
+import static com.oracle.graal.hotspot.nodes.NewInstanceStubCall.*;
 import static com.oracle.graal.hotspot.replacements.SystemSubstitutions.*;
 import static com.oracle.graal.java.GraphBuilderPhase.RuntimeCalls.*;
 import static com.oracle.graal.nodes.java.RegisterFinalizerNode.*;
 import static com.oracle.graal.replacements.Log.*;
 import static com.oracle.graal.replacements.MathSubstitutionsX86.*;
-import com.oracle.graal.replacements.*;
+
 import java.lang.reflect.*;
 import java.util.*;
 
@@ -50,7 +52,7 @@
 import com.oracle.graal.api.code.Register.RegisterFlag;
 import com.oracle.graal.api.code.RuntimeCallTarget.Descriptor;
 import com.oracle.graal.api.meta.*;
-import com.oracle.graal.compiler.target.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.hotspot.*;
 import com.oracle.graal.hotspot.bridge.*;
@@ -69,6 +71,7 @@
 import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.phases.*;
 import com.oracle.graal.printer.*;
+import com.oracle.graal.replacements.*;
 import com.oracle.graal.word.*;
 
 /**
@@ -88,9 +91,6 @@
     private MonitorSnippets.Templates monitorSnippets;
     private WriteBarrierSnippets.Templates writeBarrierSnippets;
 
-    private NewInstanceStub newInstanceStub;
-    private NewArrayStub newArrayStub;
-
     private final Map<Descriptor, HotSpotRuntimeCallTarget> runtimeCalls = new HashMap<>();
     private final Map<ResolvedJavaMethod, Stub> stubs = new HashMap<>();
 
@@ -303,67 +303,57 @@
         return kind == Kind.fromJavaClass(spec);
     }
 
-    /**
-     * Binds a snippet-base {@link Stub} to a runtime call descriptor.
-     * 
-     * @return the linkage information for a call to the stub
-     */
-    public HotSpotRuntimeCallTarget registerStub(Descriptor descriptor, Stub stub) {
-        HotSpotRuntimeCallTarget linkage = runtimeCalls.get(descriptor);
-        assert linkage != null;
-        linkage.setStub(stub);
-        stubs.put(stub.getMethod(), stub);
-        return linkage;
+    protected abstract RegisterConfig createRegisterConfig(boolean globalStubConfig);
+
+    public void registerReplacements(Replacements replacements) {
+        if (GraalOptions.IntrinsifyObjectMethods) {
+            replacements.registerSubstitutions(ObjectSubstitutions.class);
+        }
+        if (GraalOptions.IntrinsifySystemMethods) {
+            replacements.registerSubstitutions(SystemSubstitutions.class);
+        }
+        if (GraalOptions.IntrinsifyThreadMethods) {
+            replacements.registerSubstitutions(ThreadSubstitutions.class);
+        }
+        if (GraalOptions.IntrinsifyUnsafeMethods) {
+            replacements.registerSubstitutions(UnsafeSubstitutions.class);
+        }
+        if (GraalOptions.IntrinsifyClassMethods) {
+            replacements.registerSubstitutions(ClassSubstitutions.class);
+        }
+        if (GraalOptions.IntrinsifyAESMethods) {
+            replacements.registerSubstitutions(AESCryptSubstitutions.class);
+            replacements.registerSubstitutions(CipherBlockChainingSubstitutions.class);
+        }
+        if (GraalOptions.IntrinsifyArrayCopy) {
+            replacements.registerSnippets(ArrayCopySnippets.class);
+        }
+        if (GraalOptions.IntrinsifyObjectClone) {
+            replacements.registerSnippets(ObjectCloneSnippets.class);
+        }
+
+        replacements.registerSnippets(CheckCastSnippets.class);
+        replacements.registerSnippets(InstanceOfSnippets.class);
+        replacements.registerSnippets(NewObjectSnippets.class);
+        replacements.registerSnippets(MonitorSnippets.class);
+
+        replacements.registerSnippets(NewInstanceStub.class);
+        replacements.registerSnippets(NewArrayStub.class);
+        replacements.registerSnippets(WriteBarrierSnippets.class);
+
+        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());
+
+        registerStub(new NewInstanceStub(this, replacements, graalRuntime.getTarget(), runtimeCalls.get(NEW_INSTANCE)));
+        registerStub(new NewArrayStub(this, replacements, graalRuntime.getTarget(), runtimeCalls.get(NEW_ARRAY)));
     }
 
-    protected abstract RegisterConfig createRegisterConfig(boolean globalStubConfig);
-
-    public void installReplacements(Backend backend, ReplacementsInstaller installer, Assumptions assumptions) {
-        if (GraalOptions.IntrinsifyObjectMethods) {
-            installer.installSubstitutions(ObjectSubstitutions.class);
-        }
-        if (GraalOptions.IntrinsifySystemMethods) {
-            installer.installSubstitutions(SystemSubstitutions.class);
-        }
-        if (GraalOptions.IntrinsifyThreadMethods) {
-            installer.installSubstitutions(ThreadSubstitutions.class);
-        }
-        if (GraalOptions.IntrinsifyUnsafeMethods) {
-            installer.installSubstitutions(UnsafeSubstitutions.class);
-        }
-        if (GraalOptions.IntrinsifyClassMethods) {
-            installer.installSubstitutions(ClassSubstitutions.class);
-        }
-        if (GraalOptions.IntrinsifyAESMethods) {
-            installer.installSubstitutions(AESCryptSubstitutions.class);
-            installer.installSubstitutions(CipherBlockChainingSubstitutions.class);
-        }
-        if (GraalOptions.IntrinsifyArrayCopy) {
-            installer.installSnippets(ArrayCopySnippets.class);
-        }
-        if (GraalOptions.IntrinsifyObjectClone) {
-            installer.installSnippets(ObjectCloneSnippets.class);
-        }
-
-        installer.installSnippets(CheckCastSnippets.class);
-        installer.installSnippets(InstanceOfSnippets.class);
-        installer.installSnippets(NewObjectSnippets.class);
-        installer.installSnippets(MonitorSnippets.class);
-
-        installer.installSnippets(NewInstanceStub.class);
-        installer.installSnippets(NewArrayStub.class);
-        installer.installSnippets(WriteBarrierSnippets.class);
-
-        checkcastSnippets = new CheckCastSnippets.Templates(this, assumptions, graalRuntime.getTarget());
-        instanceofSnippets = new InstanceOfSnippets.Templates(this, assumptions, graalRuntime.getTarget());
-        newObjectSnippets = new NewObjectSnippets.Templates(this, assumptions, graalRuntime.getTarget(), config.useTLAB);
-        monitorSnippets = new MonitorSnippets.Templates(this, assumptions, graalRuntime.getTarget(), config.useFastLocking);
-        writeBarrierSnippets = new WriteBarrierSnippets.Templates(this, assumptions, graalRuntime.getTarget());
-
-        newInstanceStub = new NewInstanceStub(this, assumptions, graalRuntime.getTarget());
-        newArrayStub = new NewArrayStub(this, assumptions, graalRuntime.getTarget());
-        newInstanceStub.install(backend);
-        newArrayStub.install(backend);
+    private void registerStub(Stub stub) {
+        stub.getLinkage().setStub(stub);
+        stubs.put(stub.getMethod(), stub);
     }
 
     public HotSpotGraalRuntime getGraalRuntime() {
@@ -827,8 +817,10 @@
     }
 
     public HotSpotRuntimeCallTarget lookupRuntimeCall(Descriptor descriptor) {
-        assert runtimeCalls.containsKey(descriptor) : descriptor;
-        return runtimeCalls.get(descriptor);
+        HotSpotRuntimeCallTarget callTarget = runtimeCalls.get(descriptor);
+        assert runtimeCalls != null : descriptor;
+        callTarget.finalizeAddress(graalRuntime.getBackend());
+        return callTarget;
     }
 
     public ResolvedJavaMethod lookupJavaMethod(Method reflectionMethod) {
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ArrayCopyNode.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ArrayCopyNode.java	Wed Apr 03 21:51:44 2013 +0200
@@ -23,6 +23,8 @@
 package com.oracle.graal.hotspot.replacements;
 
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
+import com.oracle.graal.api.runtime.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.Node.IterableNodeType;
 import com.oracle.graal.loop.phases.*;
@@ -31,7 +33,6 @@
 import com.oracle.graal.nodes.virtual.*;
 import com.oracle.graal.phases.*;
 import com.oracle.graal.phases.common.*;
-import com.oracle.graal.replacements.*;
 import com.oracle.graal.replacements.nodes.*;
 
 public class ArrayCopyNode extends MacroNode implements Virtualizable, IterableNodeType, Lowerable {
@@ -60,7 +61,7 @@
         return arguments.get(4);
     }
 
-    private StructuredGraph selectSnippet(LoweringTool tool) {
+    private StructuredGraph selectSnippet(LoweringTool tool, Replacements replacements) {
         ResolvedJavaType srcType = getSource().objectStamp().type();
         ResolvedJavaType destType = getDestination().objectStamp().type();
 
@@ -72,7 +73,7 @@
         }
         Kind componentKind = srcType.getComponentType().getKind();
         ResolvedJavaMethod snippetMethod = tool.getRuntime().lookupJavaMethod(ArrayCopySnippets.getSnippetForKind(componentKind));
-        return (StructuredGraph) snippetMethod.getCompilerStorage().get(Snippet.class);
+        return replacements.getSnippet(snippetMethod);
     }
 
     private static void unrollFixedLengthLoop(StructuredGraph snippetGraph, int length, LoweringTool tool) {
@@ -93,12 +94,11 @@
             return null;
         }
 
-        StructuredGraph snippetGraph = selectSnippet(tool);
+        Replacements replacements = Graal.getRequiredCapability(Replacements.class);
+        StructuredGraph snippetGraph = selectSnippet(tool, replacements);
         if (snippetGraph == null) {
             ResolvedJavaMethod snippetMethod = tool.getRuntime().lookupJavaMethod(ArrayCopySnippets.genericArraycopySnippet);
-            snippetGraph = ((StructuredGraph) snippetMethod.getCompilerStorage().get(Snippet.class)).copy();
-            assert snippetGraph != null : "ArrayCopySnippets should be installed";
-
+            snippetGraph = replacements.getSnippet(snippetMethod).copy();
             replaceSnippetInvokes(snippetGraph);
         } else {
             assert snippetGraph != null : "ArrayCopySnippets should be installed";
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/CheckCastSnippets.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/CheckCastSnippets.java	Wed Apr 03 21:51:44 2013 +0200
@@ -33,6 +33,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.Node.NodeIntrinsic;
 import com.oracle.graal.hotspot.meta.*;
@@ -179,8 +180,8 @@
         private final ResolvedJavaMethod secondary;
         private final ResolvedJavaMethod dynamic;
 
-        public Templates(CodeCacheProvider runtime, Assumptions assumptions, TargetDescription target) {
-            super(runtime, assumptions, target, CheckCastSnippets.class);
+        public Templates(CodeCacheProvider runtime, Replacements replacements, TargetDescription target) {
+            super(runtime, replacements, target, CheckCastSnippets.class);
             exact = snippet("checkcastExact", Object.class, Word.class, boolean.class);
             primary = snippet("checkcastPrimary", Word.class, Object.class, boolean.class, int.class);
             secondary = snippet("checkcastSecondary", Word.class, Object.class, Word[].class, boolean.class);
@@ -215,7 +216,7 @@
                 arguments = arguments("hub", hub).add("object", object).add("hints", hints);
             }
 
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             Debug.log("Lowering checkcast in %s: node=%s, template=%s, arguments=%s", graph, checkcast, template, arguments);
             template.instantiate(runtime, checkcast, DEFAULT_REPLACER, arguments);
         }
@@ -232,7 +233,7 @@
             Key key = new Key(dynamic).add("checkNull", checkNull);
             Arguments arguments = arguments("hub", hub).add("object", object);
 
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             Debug.log("Lowering dynamic checkcast in %s: node=%s, template=%s, arguments=%s", graph, checkcast, template, arguments);
             template.instantiate(runtime, checkcast, DEFAULT_REPLACER, arguments);
         }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/HotSpotInstalledCodeIntrinsics.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/HotSpotInstalledCodeIntrinsics.java	Wed Apr 03 21:51:44 2013 +0200
@@ -22,6 +22,7 @@
  */
 package com.oracle.graal.hotspot.replacements;
 
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.api.runtime.*;
 import com.oracle.graal.phases.*;
 import com.oracle.graal.replacements.*;
@@ -30,9 +31,9 @@
 public class HotSpotInstalledCodeIntrinsics implements ReplacementsProvider {
 
     @Override
-    public void installReplacements(ReplacementsInstaller installer) {
+    public void registerReplacements(Replacements replacements) {
         if (GraalOptions.IntrinsifyInstalledCodeMethods) {
-            installer.installSubstitutions(HotSpotInstalledCodeSubstitutions.class);
+            replacements.registerSubstitutions(HotSpotInstalledCodeSubstitutions.class);
         }
     }
 }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/InstanceOfSnippets.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/InstanceOfSnippets.java	Wed Apr 03 21:51:44 2013 +0200
@@ -29,6 +29,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.hotspot.meta.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.java.*;
@@ -170,8 +171,8 @@
         private final ResolvedJavaMethod instanceofSecondary;
         private final ResolvedJavaMethod instanceofDynamic;
 
-        public Templates(CodeCacheProvider runtime, Assumptions assumptions, TargetDescription target) {
-            super(runtime, assumptions, target, InstanceOfSnippets.class);
+        public Templates(CodeCacheProvider runtime, Replacements replacements, TargetDescription target) {
+            super(runtime, replacements, target, InstanceOfSnippets.class);
             instanceofExact = snippet("instanceofExact", Object.class, Word.class, Object.class, Object.class, boolean.class);
             instanceofPrimary = snippet("instanceofPrimary", Word.class, Object.class, Object.class, Object.class, boolean.class, int.class);
             instanceofSecondary = snippet("instanceofSecondary", Word.class, Object.class, Object.class, Object.class, Word[].class, boolean.class);
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/MonitorSnippets.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/MonitorSnippets.java	Wed Apr 03 21:51:44 2013 +0200
@@ -34,6 +34,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.Node.NodeIntrinsic;
 import com.oracle.graal.graph.iterators.*;
@@ -410,8 +411,8 @@
         private final ResolvedJavaMethod checkCounter;
         private final boolean useFastLocking;
 
-        public Templates(CodeCacheProvider runtime, Assumptions assumptions, TargetDescription target, boolean useFastLocking) {
-            super(runtime, assumptions, target, MonitorSnippets.class);
+        public Templates(CodeCacheProvider runtime, Replacements replacements, TargetDescription target, boolean useFastLocking) {
+            super(runtime, replacements, target, MonitorSnippets.class);
             monitorenter = snippet("monitorenter", Object.class, boolean.class, boolean.class);
             monitorexit = snippet("monitorexit", Object.class, boolean.class);
             monitorenterStub = snippet("monitorenterStub", Object.class, boolean.class, boolean.class);
@@ -444,7 +445,7 @@
             if (!eliminated) {
                 arguments.add("object", monitorenterNode.object());
             }
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             Map<Node, Node> nodes = template.instantiate(runtime, monitorenterNode, DEFAULT_REPLACER, arguments);
             for (Node n : nodes.values()) {
                 if (n instanceof BeginLockScopeNode) {
@@ -470,7 +471,7 @@
             if (!eliminated) {
                 arguments.add("object", monitorexitNode.object());
             }
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             Map<Node, Node> nodes = template.instantiate(runtime, monitorexitNode, DEFAULT_REPLACER, arguments);
             for (Node n : nodes.values()) {
                 if (n instanceof EndLockScopeNode) {
@@ -526,7 +527,8 @@
                     InvokeNode invoke = graph.add(new InvokeNode(callTarget, 0));
                     invoke.setStateAfter(graph.start().stateAfter());
                     graph.addAfterFixed(graph.start(), invoke);
-                    StructuredGraph inlineeGraph = (StructuredGraph) initCounter.getCompilerStorage().get(Snippet.class);
+
+                    StructuredGraph inlineeGraph = replacements.getSnippet(initCounter);
                     InliningUtil.inline(invoke, inlineeGraph, false);
 
                     List<ReturnNode> rets = graph.getNodes().filter(ReturnNode.class).snapshot();
@@ -540,7 +542,7 @@
                         FrameState stateAfter = new FrameState(graph.method(), FrameState.AFTER_BCI, new ValueNode[0], stack, new ValueNode[0], false, false);
                         invoke.setStateAfter(graph.add(stateAfter));
                         graph.addBeforeFixed(ret, invoke);
-                        inlineeGraph = (StructuredGraph) checkCounter.getCompilerStorage().get(Snippet.class);
+                        inlineeGraph = replacements.getSnippet(checkCounter);
                         InliningUtil.inline(invoke, inlineeGraph, false);
                     }
                 }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/NewObjectSnippets.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/NewObjectSnippets.java	Wed Apr 03 21:51:44 2013 +0200
@@ -34,6 +34,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.hotspot.meta.*;
 import com.oracle.graal.hotspot.nodes.*;
@@ -234,8 +235,8 @@
         private final TargetDescription target;
         private final boolean useTLAB;
 
-        public Templates(CodeCacheProvider runtime, Assumptions assumptions, TargetDescription target, boolean useTLAB) {
-            super(runtime, assumptions, target, NewObjectSnippets.class);
+        public Templates(CodeCacheProvider runtime, Replacements replacements, TargetDescription target, boolean useTLAB) {
+            super(runtime, replacements, target, NewObjectSnippets.class);
             this.target = target;
             this.useTLAB = useTLAB;
             allocate = snippet("allocate", int.class);
@@ -303,7 +304,7 @@
                 Key key = new Key(allocateArrayAndInitialize).add("alignment", alignment).add("headerSize", headerSize).add("log2ElementSize", log2ElementSize).add("fillContents",
                                 newArrayNode.fillContents()).add("type", arrayType);
                 Arguments arguments = new Arguments().add("length", lengthNode);
-                SnippetTemplate template = cache.get(key, assumptions);
+                SnippetTemplate template = cache.get(key);
                 Debug.log("Lowering allocateArrayAndInitialize in %s: node=%s, template=%s, arguments=%s", graph, newArrayNode, template, arguments);
                 template.instantiate(runtime, newArrayNode, DEFAULT_REPLACER, arguments);
             }
@@ -315,7 +316,7 @@
             ValueNode size = tlabAllocateNode.size();
             Key key = new Key(allocate);
             Arguments arguments = arguments("size", size);
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             Debug.log("Lowering fastAllocate in %s: node=%s, template=%s, arguments=%s", graph, tlabAllocateNode, template, arguments);
             template.instantiate(runtime, tlabAllocateNode, DEFAULT_REPLACER, arguments);
         }
@@ -330,7 +331,7 @@
             Key key = new Key(initializeObject).add("size", size).add("fillContents", initializeNode.fillContents()).add("locked", initializeNode.locked());
             ValueNode memory = initializeNode.memory();
             Arguments arguments = arguments("memory", memory).add("hub", hub).add("prototypeMarkWord", type.prototypeMarkWord());
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             Debug.log("Lowering initializeObject in %s: node=%s, template=%s, arguments=%s", graph, initializeNode, template, arguments);
             template.instantiate(runtime, initializeNode, DEFAULT_REPLACER, arguments);
         }
@@ -348,7 +349,7 @@
             ValueNode memory = initializeNode.memory();
             Arguments arguments = arguments("memory", memory).add("hub", hub).add("prototypeMarkWord", type.prototypeMarkWord()).add("allocationSize", initializeNode.allocationSize()).add("length",
                             initializeNode.length());
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             Debug.log("Lowering initializeArray in %s: node=%s, template=%s, arguments=%s", graph, initializeNode, template, arguments);
             template.instantiate(runtime, initializeNode, DEFAULT_REPLACER, arguments);
         }
@@ -365,7 +366,7 @@
             ConstantNode hub = ConstantNode.forConstant(type.klass(), runtime, graph);
             Key key = new Key(newmultiarray).add("dimensions", vargargs(new int[rank], StampFactory.forKind(Kind.Int))).add("rank", rank);
             Arguments arguments = arguments("dimensions", dims).add("hub", hub);
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             template.instantiate(runtime, newmultiarrayNode, DEFAULT_REPLACER, arguments);
         }
 
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ObjectCloneNode.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ObjectCloneNode.java	Wed Apr 03 21:51:44 2013 +0200
@@ -26,13 +26,14 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
+import com.oracle.graal.api.runtime.*;
 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.*;
 import com.oracle.graal.phases.*;
-import com.oracle.graal.replacements.*;
 import com.oracle.graal.replacements.nodes.*;
 
 public class ObjectCloneNode extends MacroNode implements VirtualizableAllocation, ArrayLengthProvider {
@@ -70,7 +71,8 @@
             method = ObjectCloneSnippets.instanceCloneMethod;
         }
         ResolvedJavaMethod snippetMethod = tool.getRuntime().lookupJavaMethod(method);
-        StructuredGraph snippetGraph = (StructuredGraph) snippetMethod.getCompilerStorage().get(Snippet.class);
+        Replacements replacements = Graal.getRequiredCapability(Replacements.class);
+        StructuredGraph snippetGraph = replacements.getSnippet(snippetMethod);
 
         assert snippetGraph != null : "ObjectCloneSnippets should be installed";
         return snippetGraph;
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/WriteBarrierSnippets.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/WriteBarrierSnippets.java	Wed Apr 03 21:51:44 2013 +0200
@@ -27,6 +27,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.hotspot.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.replacements.*;
@@ -155,8 +156,8 @@
         private final ResolvedJavaMethod g1PreWriteBarrier;
         private final ResolvedJavaMethod g1PostWriteBarrier;
 
-        public Templates(CodeCacheProvider runtime, Assumptions assumptions, TargetDescription target) {
-            super(runtime, assumptions, target, WriteBarrierSnippets.class);
+        public Templates(CodeCacheProvider runtime, Replacements replacements, TargetDescription target) {
+            super(runtime, replacements, target, WriteBarrierSnippets.class);
             serialFieldWriteBarrier = snippet("serialFieldWriteBarrier", Object.class);
             serialArrayWriteBarrier = snippet("serialArrayWriteBarrier", Object.class, Object.class);
             g1PreWriteBarrier = snippet("g1PreWriteBarrier", Object.class, Object.class, Object.class, boolean.class);
@@ -169,7 +170,7 @@
             Arguments arguments = new Arguments();
             arguments.add("object", arrayWriteBarrier.getObject());
             arguments.add("location", arrayWriteBarrier.getLocation());
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             template.instantiate(runtime, arrayWriteBarrier, DEFAULT_REPLACER, arguments);
         }
 
@@ -178,7 +179,7 @@
             Key key = new Key(method);
             Arguments arguments = new Arguments();
             arguments.add("object", fieldWriteBarrier.getObject());
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             template.instantiate(runtime, fieldWriteBarrier, DEFAULT_REPLACER, arguments);
         }
 
@@ -190,7 +191,7 @@
             arguments.add("object", writeBarrierPre.getObject());
             arguments.add("expectedObject", writeBarrierPre.getExpectedObject());
             arguments.add("location", writeBarrierPre.getLocation());
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             template.instantiate(runtime, writeBarrierPre, DEFAULT_REPLACER, arguments);
         }
 
@@ -202,7 +203,7 @@
             arguments.add("object", writeBarrierPost.getObject());
             arguments.add("location", writeBarrierPost.getLocation());
             arguments.add("value", writeBarrierPost.getValue());
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             template.instantiate(runtime, writeBarrierPost, DEFAULT_REPLACER, arguments);
         }
 
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/NewArrayStub.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/NewArrayStub.java	Wed Apr 03 21:51:44 2013 +0200
@@ -28,6 +28,8 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
+import com.oracle.graal.hotspot.*;
 import com.oracle.graal.hotspot.meta.*;
 import com.oracle.graal.hotspot.nodes.*;
 import com.oracle.graal.hotspot.replacements.*;
@@ -44,8 +46,8 @@
  */
 public class NewArrayStub extends Stub {
 
-    public NewArrayStub(final HotSpotRuntime runtime, Assumptions assumptions, TargetDescription target) {
-        super(runtime, assumptions, target, NewArrayStubCall.NEW_ARRAY);
+    public NewArrayStub(final HotSpotRuntime runtime, Replacements replacements, TargetDescription target, HotSpotRuntimeCallTarget linkage) {
+        super(runtime, replacements, target, linkage);
     }
 
     @Override
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/NewInstanceStub.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/NewInstanceStub.java	Wed Apr 03 21:51:44 2013 +0200
@@ -23,18 +23,21 @@
 package com.oracle.graal.hotspot.stubs;
 
 import static com.oracle.graal.hotspot.nodes.DirectCompareAndSwapNode.*;
-import static com.oracle.graal.hotspot.nodes.NewInstanceStubCall.*;
 import static com.oracle.graal.hotspot.replacements.HotSpotSnippetUtils.*;
 import static com.oracle.graal.hotspot.replacements.NewObjectSnippets.*;
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
+import com.oracle.graal.hotspot.*;
 import com.oracle.graal.hotspot.meta.*;
 import com.oracle.graal.hotspot.nodes.*;
 import com.oracle.graal.hotspot.replacements.*;
 import com.oracle.graal.replacements.*;
-import com.oracle.graal.replacements.Snippet.*;
-import com.oracle.graal.replacements.SnippetTemplate.*;
+import com.oracle.graal.replacements.Snippet.ConstantParameter;
+import com.oracle.graal.replacements.Snippet.Fold;
+import com.oracle.graal.replacements.Snippet.Parameter;
+import com.oracle.graal.replacements.SnippetTemplate.Key;
 import com.oracle.graal.word.*;
 
 /**
@@ -45,8 +48,8 @@
  */
 public class NewInstanceStub extends Stub {
 
-    public NewInstanceStub(final HotSpotRuntime runtime, Assumptions assumptions, TargetDescription target) {
-        super(runtime, assumptions, target, NEW_INSTANCE);
+    public NewInstanceStub(final HotSpotRuntime runtime, Replacements replacements, TargetDescription target, HotSpotRuntimeCallTarget linkage) {
+        super(runtime, replacements, target, linkage);
     }
 
     @Override
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/Stub.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/Stub.java	Wed Apr 03 21:51:44 2013 +0200
@@ -28,8 +28,8 @@
 import java.util.concurrent.*;
 
 import com.oracle.graal.api.code.*;
-import com.oracle.graal.api.code.RuntimeCallTarget.Descriptor;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.compiler.*;
 import com.oracle.graal.compiler.target.*;
 import com.oracle.graal.debug.*;
@@ -69,17 +69,17 @@
     protected InstalledCode stubCode;
 
     /**
-     * Creates a new stub container. The new stub still needs to be {@linkplain #install(Backend)
+     * Creates a new stub container. The new stub still needs to be {@linkplain #getAddress(Backend)
      * installed}.
      * 
-     * @param descriptor linkage details for a call to the stub
+     * @param linkage linkage details for a call to the stub
      */
     @SuppressWarnings("unchecked")
-    public Stub(HotSpotRuntime runtime, Assumptions assumptions, TargetDescription target, Descriptor descriptor) {
-        super(runtime, assumptions, target, null);
+    public Stub(HotSpotRuntime runtime, Replacements replacements, TargetDescription target, HotSpotRuntimeCallTarget linkage) {
+        super(runtime, replacements, target, null);
         stubMethod = findStubMethod(runtime, getClass());
-        linkage = runtime.registerStub(descriptor, this);
-        assert linkage != null;
+        this.linkage = linkage;
+
     }
 
     /**
@@ -103,38 +103,41 @@
     }
 
     /**
-     * Compiles the code for this stub, installs it and initializes the address used for calls to
-     * it.
+     * Ensures the code for this stub is installed.
+     * 
+     * @return the entry point address for calls to this stub
      */
-    public void install(Backend backend) {
-        StructuredGraph graph = (StructuredGraph) stubMethod.getCompilerStorage().get(Snippet.class);
+    public synchronized long getAddress(Backend backend) {
+        if (stubCode == null) {
+            StructuredGraph graph = replacements.getSnippet(stubMethod);
 
-        Key key = new Key(stubMethod);
-        populateKey(key);
-        SnippetTemplate template = cache.get(key, assumptions);
-        graph = template.copySpecializedGraph();
+            Key key = new Key(stubMethod);
+            populateKey(key);
+            SnippetTemplate template = cache.get(key);
+            graph = template.copySpecializedGraph();
 
-        PhasePlan phasePlan = new PhasePlan();
-        GraphBuilderPhase graphBuilderPhase = new GraphBuilderPhase(runtime, GraphBuilderConfiguration.getDefault(), OptimisticOptimizations.ALL);
-        phasePlan.addPhase(PhasePosition.AFTER_PARSING, graphBuilderPhase);
-        final CompilationResult compResult = GraalCompiler.compileMethod(runtime(), backend, runtime().getTarget(), stubMethod, graph, null, phasePlan, OptimisticOptimizations.ALL,
-                        new SpeculationLog());
+            PhasePlan phasePlan = new PhasePlan();
+            GraphBuilderPhase graphBuilderPhase = new GraphBuilderPhase(runtime, GraphBuilderConfiguration.getDefault(), OptimisticOptimizations.ALL);
+            phasePlan.addPhase(PhasePosition.AFTER_PARSING, graphBuilderPhase);
+            final CompilationResult compResult = GraalCompiler.compileMethod(runtime(), backend, runtime().getTarget(), stubMethod, graph, null, phasePlan, OptimisticOptimizations.ALL,
+                            new SpeculationLog());
 
-        stubCode = Debug.scope("CodeInstall", new Object[]{runtime(), stubMethod}, new Callable<InstalledCode>() {
+            stubCode = Debug.scope("CodeInstall", new Object[]{runtime(), stubMethod}, new Callable<InstalledCode>() {
 
-            @Override
-            public InstalledCode call() {
-                InstalledCode installedCode = runtime().addMethod(stubMethod, compResult);
-                assert installedCode != null : "error installing stub " + stubMethod;
-                if (Debug.isDumpEnabled()) {
-                    Debug.dump(new Object[]{compResult, installedCode}, "After code installation");
+                @Override
+                public InstalledCode call() {
+                    InstalledCode installedCode = runtime().addMethod(stubMethod, compResult);
+                    assert installedCode != null : "error installing stub " + stubMethod;
+                    if (Debug.isDumpEnabled()) {
+                        Debug.dump(new Object[]{compResult, installedCode}, "After code installation");
+                    }
+                    return installedCode;
                 }
-                return installedCode;
-            }
-        });
+            });
 
-        assert stubCode != null : "error installing stub " + stubMethod;
-        linkage.setAddress(stubCode.getStart());
+            assert stubCode != null : "error installing stub " + stubMethod;
+        }
+        return stubCode.getStart();
     }
 
     /**
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java	Wed Apr 03 21:51:44 2013 +0200
@@ -32,6 +32,7 @@
 import com.oracle.graal.api.meta.JavaTypeProfile.ProfiledType;
 import com.oracle.graal.api.meta.ResolvedJavaType.Representation;
 import com.oracle.graal.api.replacements.*;
+import com.oracle.graal.api.runtime.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
@@ -1181,11 +1182,12 @@
     }
 
     public static StructuredGraph getIntrinsicGraph(ResolvedJavaMethod target) {
-        return (StructuredGraph) target.getCompilerStorage().get(MethodSubstitution.class);
+        Replacements replacements = Graal.getRequiredCapability(Replacements.class);
+        return replacements.getMethodSubstitution(target);
     }
 
     public static Class<? extends FixedWithNextNode> getMacroNodeClass(ResolvedJavaMethod target) {
-        Object result = target.getCompilerStorage().get(Node.class);
-        return result == null ? null : ((Class<?>) result).asSubclass(FixedWithNextNode.class);
+        Replacements replacements = Graal.getRequiredCapability(Replacements.class);
+        return replacements.getMacroSubstitution(target);
     }
 }
--- a/graal/com.oracle.graal.replacements.amd64/src/com/oracle/graal/replacements/amd64/AMD64ConvertSnippets.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.replacements.amd64/src/com/oracle/graal/replacements/amd64/AMD64ConvertSnippets.java	Wed Apr 03 21:51:44 2013 +0200
@@ -28,6 +28,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
@@ -153,8 +154,8 @@
         private final ResolvedJavaMethod d2i;
         private final ResolvedJavaMethod d2l;
 
-        public Templates(CodeCacheProvider runtime, Assumptions assumptions, TargetDescription target) {
-            super(runtime, assumptions, target, AMD64ConvertSnippets.class);
+        public Templates(CodeCacheProvider runtime, Replacements replacements, TargetDescription target) {
+            super(runtime, replacements, target, AMD64ConvertSnippets.class);
             f2i = snippet("f2i", float.class, int.class);
             f2l = snippet("f2l", float.class, long.class);
             d2i = snippet("d2i", double.class, int.class);
@@ -185,7 +186,7 @@
             convert.replaceAtUsages(replacee);
             Key key = new Key(snippet);
             Arguments arguments = arguments("input", convert.value()).add("result", convert);
-            SnippetTemplate template = cache.get(key, assumptions);
+            SnippetTemplate template = cache.get(key);
             Debug.log("Lowering %s in %s: node=%s, template=%s, arguments=%s", convert.opcode, graph, convert, template, arguments);
             template.instantiate(runtime, replacee, DEFAULT_REPLACER, tool, arguments);
         }
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/GraalMethodSubstitutions.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/GraalMethodSubstitutions.java	Wed Apr 03 21:51:44 2013 +0200
@@ -22,6 +22,7 @@
  */
 package com.oracle.graal.replacements;
 
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.api.runtime.*;
 import com.oracle.graal.phases.*;
 
@@ -31,15 +32,15 @@
 @ServiceProvider(ReplacementsProvider.class)
 public class GraalMethodSubstitutions implements ReplacementsProvider {
 
-    public void installReplacements(ReplacementsInstaller installer) {
+    public void registerReplacements(Replacements replacements) {
         if (GraalOptions.Intrinsify) {
-            installer.installSubstitutions(MathSubstitutionsX86.class);
-            installer.installSubstitutions(DoubleSubstitutions.class);
-            installer.installSubstitutions(FloatSubstitutions.class);
-            installer.installSubstitutions(NodeClassSubstitutions.class);
-            installer.installSubstitutions(LongSubstitutions.class);
-            installer.installSubstitutions(IntegerSubstitutions.class);
-            installer.installSubstitutions(UnsignedMathSubstitutions.class);
+            replacements.registerSubstitutions(MathSubstitutionsX86.class);
+            replacements.registerSubstitutions(DoubleSubstitutions.class);
+            replacements.registerSubstitutions(FloatSubstitutions.class);
+            replacements.registerSubstitutions(NodeClassSubstitutions.class);
+            replacements.registerSubstitutions(LongSubstitutions.class);
+            replacements.registerSubstitutions(IntegerSubstitutions.class);
+            replacements.registerSubstitutions(UnsignedMathSubstitutions.class);
         }
     }
 }
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/InstanceOfSnippetsTemplates.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/InstanceOfSnippetsTemplates.java	Wed Apr 03 21:51:44 2013 +0200
@@ -28,6 +28,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
@@ -51,8 +52,8 @@
  */
 public abstract class InstanceOfSnippetsTemplates<T extends Snippets> extends AbstractTemplates<T> {
 
-    public InstanceOfSnippetsTemplates(MetaAccessProvider runtime, Assumptions assumptions, TargetDescription target, Class<T> snippetsClass) {
-        super(runtime, assumptions, target, snippetsClass);
+    public InstanceOfSnippetsTemplates(MetaAccessProvider runtime, Replacements replacements, TargetDescription target, Class<T> snippetsClass) {
+        super(runtime, replacements, target, snippetsClass);
     }
 
     /**
@@ -91,7 +92,7 @@
                 replacer.replaceUsingInstantiation();
             } else {
                 KeyAndArguments keyAndArguments = getKeyAndArguments(replacer, tool);
-                SnippetTemplate template = cache.get(keyAndArguments.key, assumptions);
+                SnippetTemplate template = cache.get(keyAndArguments.key);
                 template.instantiate(runtime, instanceOf, replacer, tool, keyAndArguments.arguments);
             }
         }
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/MacroSubstitution.java	Wed Apr 03 16:56:43 2013 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,71 +0,0 @@
-/*
- * 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.replacements;
-
-import java.lang.annotation.*;
-
-import com.oracle.graal.api.meta.*;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.replacements.nodes.*;
-
-/**
- * Denotes a macro substitute method. This replaces a method invocation with an instance of the
- * specified node class.
- * 
- * A macro substitution can be combined with a normal substitution, so that the macro node can be
- * replaced with the actual substitution code during lowering.
- */
-@Retention(RetentionPolicy.RUNTIME)
-@Target(ElementType.METHOD)
-public @interface MacroSubstitution {
-
-    /**
-     * Gets the name of the substituted method.
-     * <p>
-     * If the default value is specified for this element, then the name of the substituted method
-     * is same as the substitute method.
-     */
-    String value() default "";
-
-    /**
-     * Determines if the substituted method is static.
-     */
-    boolean isStatic() default true;
-
-    /**
-     * Gets the {@linkplain MetaUtil#signatureToMethodDescriptor signature} of the substituted
-     * method.
-     * <p>
-     * If the default value is specified for this element, then the signature of the substituted
-     * method is the same as the substitute method.
-     */
-    String signature() default "";
-
-    /**
-     * The node class with which the method invocation should be replaced. It needs to be a subclass
-     * of {@link FixedWithNextNode}, and it is expected to provide a public constructor that takes
-     * an InvokeNode as a parameter. For most cases this class should subclass {@link MacroNode} and
-     * use its constructor.
-     */
-    Class<? extends FixedWithNextNode> macro();
-}
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsInstaller.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsInstaller.java	Wed Apr 03 21:51:44 2013 +0200
@@ -46,41 +46,36 @@
 import com.oracle.graal.replacements.Snippet.SnippetInliningPolicy;
 import com.oracle.graal.word.phases.*;
 
-/**
- * Utility for managing the pre-processing and installation of replacements. Replacements are either
- * {@linkplain Snippets snippets}, {@linkplain MethodSubstitution method substitutions} or
- * {@link MacroSubstitution macro substitutions}.
- */
-public class ReplacementsInstaller {
+public class ReplacementsInstaller implements Replacements {
 
     protected final MetaAccessProvider runtime;
     protected final TargetDescription target;
     protected final Assumptions assumptions;
-    protected final BoxingMethodPool pool;
-    private final Thread owner;
+
+    private BoxingMethodPool pool;
 
     /**
      * A graph cache used by this installer to avoid using the compiler storage for each method
      * processed during snippet installation. Without this, all processed methods are to be
      * determined as {@linkplain InliningUtil#canIntrinsify intrinsifiable}.
      */
-    private final Map<ResolvedJavaMethod, StructuredGraph> graphCache;
+    private final ConcurrentMap<ResolvedJavaMethod, StructuredGraph> graphCache;
+
+    private final ConcurrentMap<ResolvedJavaMethod, ResolvedJavaMethod> originalToSubstitute;
+
+    private final ConcurrentMap<ResolvedJavaMethod, Class<? extends FixedWithNextNode>> macroNodeClasses;
 
     public ReplacementsInstaller(MetaAccessProvider runtime, Assumptions assumptions, TargetDescription target) {
         this.runtime = runtime;
         this.target = target;
         this.assumptions = assumptions;
-        this.pool = new BoxingMethodPool(runtime);
-        this.graphCache = new HashMap<>();
-        this.owner = Thread.currentThread();
+        this.graphCache = new ConcurrentHashMap<>();
+        this.originalToSubstitute = new ConcurrentHashMap<>();
+        this.macroNodeClasses = new ConcurrentHashMap<>();
     }
 
-    /**
-     * Finds all the snippet methods in a given class, builds a graph for them and installs the
-     * graph with the key value of {@code Snippet.class} in the
-     * {@linkplain ResolvedJavaMethod#getCompilerStorage() compiler storage} of each method.
-     */
-    public void installSnippets(Class<? extends Snippets> snippets) {
+    public void registerSnippets(Class<?> snippets) {
+        assert Snippets.class.isAssignableFrom(snippets);
         for (Method method : snippets.getDeclaredMethods()) {
             if (method.getAnnotation(Snippet.class) != null) {
                 int modifiers = method.getModifiers();
@@ -88,24 +83,43 @@
                     throw new RuntimeException("Snippet must not be abstract or native");
                 }
                 ResolvedJavaMethod snippet = runtime.lookupJavaMethod(method);
-                assert snippet.getCompilerStorage().get(Snippet.class) == null : method;
-                StructuredGraph graph = makeGraph(snippet, inliningPolicy(snippet));
-                // System.out.println("snippet: " + graph);
-                snippet.getCompilerStorage().put(Snippet.class, graph);
+                graphCache.putIfAbsent(snippet, placeholder);
             }
         }
     }
 
-    /**
-     * Finds all the methods in a given class annotated with {@link MethodSubstitution} or
-     * {@link MacroSubstitution}. It builds graphs for the former and installs them in the
-     * {@linkplain ResolvedJavaMethod#getCompilerStorage() compiler storage} of the original (i.e.,
-     * substituted) method with a key of {@code MethodSubstitution.class}. For the latter, the
-     * denoted {@linkplain MacroSubstitution#macro() macro} node type is install in the compiler
-     * storage with a key of {@code Node.class}.
-     */
-    public void installSubstitutions(Class<?> substitutions) {
-        assert owner == Thread.currentThread() : "substitution installation must be single threaded";
+    private final StructuredGraph placeholder = new StructuredGraph();
+
+    public StructuredGraph getSnippet(ResolvedJavaMethod method) {
+        StructuredGraph graph = graphCache.get(method);
+        if (graph == placeholder) {
+            graph = createGraphMaker(null, null).makeGraph(method, inliningPolicy(method));
+            assert graph == graphCache.get(method);
+        }
+        return graph;
+    }
+
+    public StructuredGraph getMethodSubstitution(ResolvedJavaMethod original) {
+        StructuredGraph graph = graphCache.get(original);
+        if (graph == placeholder) {
+            ResolvedJavaMethod substitute = originalToSubstitute.get(original);
+            if (substitute != null) {
+                graph = createGraphMaker(substitute, original).makeGraph(substitute, inliningPolicy(substitute));
+                assert graph == graphCache.get(substitute);
+            }
+        }
+        return graph;
+    }
+
+    public Class<? extends FixedWithNextNode> getMacroSubstitution(ResolvedJavaMethod method) {
+        return macroNodeClasses.get(method);
+    }
+
+    public Assumptions getAssumptions() {
+        return assumptions;
+    }
+
+    public void registerSubstitutions(Class<?> substitutions) {
         ClassSubstitution classSubstitution = substitutions.getAnnotation(ClassSubstitution.class);
         assert classSubstitution != null;
         assert !Snippets.class.isAssignableFrom(substitutions);
@@ -143,11 +157,6 @@
         }
     }
 
-    // These fields are used to detect calls from the substitute method to the original method.
-    ResolvedJavaMethod substitute;
-    ResolvedJavaMethod original;
-    boolean substituteCallsOriginal;
-
     /**
      * Installs a method substitution.
      * 
@@ -155,22 +164,17 @@
      * @param substituteMethod the substitute method
      */
     protected void installMethodSubstitution(Member originalMember, Method substituteMethod) {
-        substitute = runtime.lookupJavaMethod(substituteMethod);
+        ResolvedJavaMethod substitute = runtime.lookupJavaMethod(substituteMethod);
+        ResolvedJavaMethod original;
         if (originalMember instanceof Method) {
             original = runtime.lookupJavaMethod((Method) originalMember);
         } else {
             original = runtime.lookupJavaConstructor((Constructor) originalMember);
         }
-        try {
-            Debug.log("substitution: " + MetaUtil.format("%H.%n(%p)", original) + " --> " + MetaUtil.format("%H.%n(%p)", substitute));
-            StructuredGraph graph = makeGraph(substitute, inliningPolicy(substitute));
-            Object oldValue = original.getCompilerStorage().put(MethodSubstitution.class, graph);
-            assert oldValue == null;
-        } finally {
-            substitute = null;
-            original = null;
-            substituteCallsOriginal = false;
-        }
+        Debug.log("substitution: " + MetaUtil.format("%H.%n(%p)", original) + " --> " + MetaUtil.format("%H.%n(%p)", substitute));
+
+        graphCache.putIfAbsent(original, placeholder);
+        originalToSubstitute.put(original, substitute);
     }
 
     /**
@@ -186,8 +190,7 @@
         } else {
             originalJavaMethod = runtime.lookupJavaConstructor((Constructor) originalMethod);
         }
-        Object oldValue = originalJavaMethod.getCompilerStorage().put(Node.class, macro);
-        assert oldValue == null;
+        macroNodeClasses.put(originalJavaMethod, macro);
     }
 
     private SnippetInliningPolicy inliningPolicy(ResolvedJavaMethod method) {
@@ -197,7 +200,7 @@
             policyClass = snippet.inlining();
         }
         if (policyClass == SnippetInliningPolicy.class) {
-            return new DefaultSnippetInliningPolicy(runtime, pool);
+            return new DefaultSnippetInliningPolicy(runtime, pool());
         }
         try {
             return policyClass.getConstructor().newInstance();
@@ -206,127 +209,149 @@
         }
     }
 
-    /**
-     * Does final processing of a snippet graph.
-     */
-    protected void finalizeGraph(ResolvedJavaMethod method, StructuredGraph graph) {
-        new NodeIntrinsificationPhase(runtime, pool).apply(graph);
-        assert SnippetTemplate.hasConstantParameter(method) || NodeIntrinsificationVerificationPhase.verify(graph);
-
-        if (substitute == null) {
-            new SnippetFrameStateCleanupPhase().apply(graph);
-            new DeadCodeEliminationPhase().apply(graph);
-            new InsertStateAfterPlaceholderPhase().apply(graph);
-        } else {
-            new DeadCodeEliminationPhase().apply(graph);
-        }
+    public StructuredGraph makeGraph(ResolvedJavaMethod method, SnippetInliningPolicy policy) {
+        return createGraphMaker(null, null).makeGraph(method, policy);
     }
 
-    public StructuredGraph makeGraph(final ResolvedJavaMethod method, final SnippetInliningPolicy policy) {
-        return Debug.scope("BuildSnippetGraph", new Object[]{method}, new Callable<StructuredGraph>() {
-
-            @Override
-            public StructuredGraph call() throws Exception {
-                StructuredGraph graph = parseGraph(method, policy);
-
-                finalizeGraph(method, graph);
-
-                Debug.dump(graph, "%s: Final", method.getName());
-
-                return graph;
-            }
-        });
+    protected GraphMaker createGraphMaker(ResolvedJavaMethod substitute, ResolvedJavaMethod original) {
+        return new GraphMaker(substitute, original);
     }
 
-    private StructuredGraph parseGraph(final ResolvedJavaMethod method, final SnippetInliningPolicy policy) {
-        StructuredGraph graph = graphCache.get(method);
-        if (graph == null) {
-            graph = buildGraph(method, policy == null ? inliningPolicy(method) : policy);
-            graphCache.put(method, graph);
+    protected class GraphMaker {
+
+        // These fields are used to detect calls from the substitute method to the original method.
+        protected final ResolvedJavaMethod substitute;
+        protected final ResolvedJavaMethod original;
+
+        boolean substituteCallsOriginal;
+
+        protected GraphMaker(ResolvedJavaMethod substitute, ResolvedJavaMethod original) {
+            this.substitute = substitute;
+            this.original = original;
         }
-        return graph;
-    }
 
-    /**
-     * Builds the initial graph for a snippet.
-     */
-    protected StructuredGraph buildInitialGraph(final ResolvedJavaMethod method) {
-        final StructuredGraph graph = new StructuredGraph(method);
-        GraphBuilderConfiguration config = GraphBuilderConfiguration.getSnippetDefault();
-        GraphBuilderPhase graphBuilder = new GraphBuilderPhase(runtime, config, OptimisticOptimizations.NONE);
-        graphBuilder.apply(graph);
+        /**
+         * Does final processing of a snippet graph.
+         */
+        protected void finalizeGraph(ResolvedJavaMethod method, StructuredGraph graph) {
+            new NodeIntrinsificationPhase(runtime, pool()).apply(graph);
+            assert SnippetTemplate.hasConstantParameter(method) || NodeIntrinsificationVerificationPhase.verify(graph);
 
-        Debug.dump(graph, "%s: %s", method.getName(), GraphBuilderPhase.class.getSimpleName());
-
-        new WordTypeVerificationPhase(runtime, target.wordKind).apply(graph);
-        new NodeIntrinsificationPhase(runtime, pool).apply(graph);
-
-        return graph;
-    }
-
-    /**
-     * Called after a graph is inlined.
-     * 
-     * @param caller the graph into which {@code callee} was inlined
-     * @param callee the graph that was inlined into {@code caller}
-     */
-    protected void afterInline(StructuredGraph caller, StructuredGraph callee) {
-        if (GraalOptions.OptCanonicalizer) {
-            new WordTypeRewriterPhase(runtime, target.wordKind).apply(caller);
-            new CanonicalizerPhase(runtime, assumptions).apply(caller);
-        }
-    }
-
-    /**
-     * Called after all inlining for a given graph is complete.
-     */
-    protected void afterInlining(StructuredGraph graph) {
-        new NodeIntrinsificationPhase(runtime, pool).apply(graph);
-
-        new WordTypeRewriterPhase(runtime, target.wordKind).apply(graph);
-
-        new DeadCodeEliminationPhase().apply(graph);
-        if (GraalOptions.OptCanonicalizer) {
-            new CanonicalizerPhase(runtime, assumptions).apply(graph);
-        }
-    }
-
-    private StructuredGraph buildGraph(final ResolvedJavaMethod method, final SnippetInliningPolicy policy) {
-        assert !Modifier.isAbstract(method.getModifiers()) && !Modifier.isNative(method.getModifiers()) : method;
-        final StructuredGraph graph = buildInitialGraph(method);
-
-        for (Invoke invoke : graph.getInvokes()) {
-            MethodCallTargetNode callTarget = invoke.methodCallTarget();
-            ResolvedJavaMethod callee = callTarget.targetMethod();
-            if (callee == substitute) {
-                final StructuredGraph originalGraph = new StructuredGraph(original);
-                new GraphBuilderPhase(runtime, GraphBuilderConfiguration.getSnippetDefault(), OptimisticOptimizations.NONE).apply(originalGraph);
-                InliningUtil.inline(invoke, originalGraph, true);
-
-                Debug.dump(graph, "after inlining %s", callee);
-                afterInline(graph, originalGraph);
-                substituteCallsOriginal = true;
+            if (substitute == null) {
+                new SnippetFrameStateCleanupPhase().apply(graph);
+                new DeadCodeEliminationPhase().apply(graph);
+                new InsertStateAfterPlaceholderPhase().apply(graph);
             } else {
-                if ((callTarget.invokeKind() == InvokeKind.Static || callTarget.invokeKind() == InvokeKind.Special) && policy.shouldInline(callee, method)) {
-                    StructuredGraph targetGraph = parseGraph(callee, policy);
-                    InliningUtil.inline(invoke, targetGraph, true);
-                    Debug.dump(graph, "after inlining %s", callee);
-                    afterInline(graph, targetGraph);
-                }
+                new DeadCodeEliminationPhase().apply(graph);
             }
         }
 
-        afterInlining(graph);
+        public StructuredGraph makeGraph(final ResolvedJavaMethod method, final SnippetInliningPolicy policy) {
+            return Debug.scope("BuildSnippetGraph", new Object[]{method}, new Callable<StructuredGraph>() {
 
-        for (LoopEndNode end : graph.getNodes(LoopEndNode.class)) {
-            end.disableSafepoint();
+                @Override
+                public StructuredGraph call() throws Exception {
+                    StructuredGraph graph = parseGraph(method, policy);
+
+                    finalizeGraph(method, graph);
+
+                    Debug.dump(graph, "%s: Final", method.getName());
+
+                    return graph;
+                }
+            });
         }
 
-        if (GraalOptions.ProbabilityAnalysis) {
+        private StructuredGraph parseGraph(final ResolvedJavaMethod method, final SnippetInliningPolicy policy) {
+            StructuredGraph graph = graphCache.get(method);
+            if (graph == null || graph == placeholder) {
+                graph = buildGraph(method, policy == null ? inliningPolicy(method) : policy);
+                graphCache.put(method, graph);
+            }
+            return graph;
+        }
+
+        /**
+         * Builds the initial graph for a snippet.
+         */
+        protected StructuredGraph buildInitialGraph(final ResolvedJavaMethod method) {
+            final StructuredGraph graph = new StructuredGraph(method);
+            GraphBuilderConfiguration config = GraphBuilderConfiguration.getSnippetDefault();
+            GraphBuilderPhase graphBuilder = new GraphBuilderPhase(runtime, config, OptimisticOptimizations.NONE);
+            graphBuilder.apply(graph);
+
+            Debug.dump(graph, "%s: %s", method.getName(), GraphBuilderPhase.class.getSimpleName());
+
+            new WordTypeVerificationPhase(runtime, target.wordKind).apply(graph);
+            new NodeIntrinsificationPhase(runtime, pool()).apply(graph);
+
+            return graph;
+        }
+
+        /**
+         * Called after a graph is inlined.
+         * 
+         * @param caller the graph into which {@code callee} was inlined
+         * @param callee the graph that was inlined into {@code caller}
+         */
+        protected void afterInline(StructuredGraph caller, StructuredGraph callee) {
+            if (GraalOptions.OptCanonicalizer) {
+                new WordTypeRewriterPhase(runtime, target.wordKind).apply(caller);
+                new CanonicalizerPhase(runtime, assumptions).apply(caller);
+            }
+        }
+
+        /**
+         * Called after all inlining for a given graph is complete.
+         */
+        protected void afterInlining(StructuredGraph graph) {
+            new NodeIntrinsificationPhase(runtime, pool()).apply(graph);
+
+            new WordTypeRewriterPhase(runtime, target.wordKind).apply(graph);
+
             new DeadCodeEliminationPhase().apply(graph);
-            new ComputeProbabilityPhase().apply(graph);
+            if (GraalOptions.OptCanonicalizer) {
+                new CanonicalizerPhase(runtime, assumptions).apply(graph);
+            }
         }
-        return graph;
+
+        private StructuredGraph buildGraph(final ResolvedJavaMethod method, final SnippetInliningPolicy policy) {
+            assert !Modifier.isAbstract(method.getModifiers()) && !Modifier.isNative(method.getModifiers()) : method;
+            final StructuredGraph graph = buildInitialGraph(method);
+
+            for (Invoke invoke : graph.getInvokes()) {
+                MethodCallTargetNode callTarget = invoke.methodCallTarget();
+                ResolvedJavaMethod callee = callTarget.targetMethod();
+                if (callee == substitute) {
+                    final StructuredGraph originalGraph = new StructuredGraph(original);
+                    new GraphBuilderPhase(runtime, GraphBuilderConfiguration.getSnippetDefault(), OptimisticOptimizations.NONE).apply(originalGraph);
+                    InliningUtil.inline(invoke, originalGraph, true);
+
+                    Debug.dump(graph, "after inlining %s", callee);
+                    afterInline(graph, originalGraph);
+                    substituteCallsOriginal = true;
+                } else {
+                    if ((callTarget.invokeKind() == InvokeKind.Static || callTarget.invokeKind() == InvokeKind.Special) && policy.shouldInline(callee, method)) {
+                        StructuredGraph targetGraph = parseGraph(callee, policy);
+                        InliningUtil.inline(invoke, targetGraph, true);
+                        Debug.dump(graph, "after inlining %s", callee);
+                        afterInline(graph, targetGraph);
+                    }
+                }
+            }
+
+            afterInlining(graph);
+
+            for (LoopEndNode end : graph.getNodes(LoopEndNode.class)) {
+                end.disableSafepoint();
+            }
+
+            if (GraalOptions.ProbabilityAnalysis) {
+                new DeadCodeEliminationPhase().apply(graph);
+                new ComputeProbabilityPhase().apply(graph);
+            }
+            return graph;
+        }
     }
 
     private static String originalName(Method substituteMethod, String methodSubstitution) {
@@ -407,4 +432,12 @@
             throw new GraalInternalError(e);
         }
     }
+
+    protected BoxingMethodPool pool() {
+        if (pool == null) {
+            // A race to create the pool is ok
+            pool = new BoxingMethodPool(runtime);
+        }
+        return pool;
+    }
 }
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsProvider.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsProvider.java	Wed Apr 03 21:51:44 2013 +0200
@@ -22,10 +22,12 @@
  */
 package com.oracle.graal.replacements;
 
+import com.oracle.graal.api.replacements.*;
+
 /**
- * Interface for service providers that install replacements into the compiler.
+ * Interface for service providers that register replacements with the compiler.
  */
 public interface ReplacementsProvider {
 
-    void installReplacements(ReplacementsInstaller installer);
+    void registerReplacements(Replacements replacements);
 }
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java	Wed Apr 03 16:56:43 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java	Wed Apr 03 21:51:44 2013 +0200
@@ -29,6 +29,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.api.replacements.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.loop.*;
@@ -41,7 +42,6 @@
 import com.oracle.graal.nodes.util.*;
 import com.oracle.graal.phases.common.*;
 import com.oracle.graal.replacements.Snippet.*;
-import com.oracle.graal.replacements.Snippet.Parameter;
 import com.oracle.graal.replacements.nodes.*;
 import com.oracle.graal.word.*;
 import com.oracle.graal.word.phases.*;
@@ -158,23 +158,25 @@
         private final ConcurrentHashMap<SnippetTemplate.Key, SnippetTemplate> templates = new ConcurrentHashMap<>();
         private final MetaAccessProvider runtime;
         private final TargetDescription target;
+        private final Replacements replacements;
 
-        public Cache(MetaAccessProvider runtime, TargetDescription target) {
+        public Cache(MetaAccessProvider runtime, Replacements replacements, TargetDescription target) {
             this.runtime = runtime;
+            this.replacements = replacements;
             this.target = target;
         }
 
         /**
          * Gets a template for a given key, creating it first if necessary.
          */
-        public SnippetTemplate get(final SnippetTemplate.Key key, final Assumptions assumptions) {
+        public SnippetTemplate get(final SnippetTemplate.Key key) {
             SnippetTemplate template = templates.get(key);
             if (template == null) {
                 template = Debug.scope("SnippetSpecialization", key.method, new Callable<SnippetTemplate>() {
 
                     @Override
                     public SnippetTemplate call() throws Exception {
-                        return new SnippetTemplate(runtime, assumptions, target, key);
+                        return new SnippetTemplate(runtime, replacements, target, key);
                     }
                 });
                 // System.out.println(key + " -> " + template);
@@ -188,19 +190,19 @@
 
         protected final Cache cache;
         protected final MetaAccessProvider runtime;
-        protected final Assumptions assumptions;
+        protected final Replacements replacements;
         protected Class<?> snippetsClass;
 
-        public AbstractTemplates(MetaAccessProvider runtime, Assumptions assumptions, TargetDescription target, Class<T> snippetsClass) {
+        public AbstractTemplates(MetaAccessProvider runtime, Replacements replacements, TargetDescription target, Class<T> snippetsClass) {
             this.runtime = runtime;
-            this.assumptions = assumptions;
+            this.replacements = replacements;
             if (snippetsClass == null) {
                 assert this instanceof Snippets;
                 this.snippetsClass = getClass();
             } else {
                 this.snippetsClass = snippetsClass;
             }
-            this.cache = new Cache(runtime, target);
+            this.cache = new Cache(runtime, replacements, target);
         }
 
         protected ResolvedJavaMethod snippet(String name, Class<?>... parameterTypes) {
@@ -231,16 +233,16 @@
     /**
      * Creates a snippet template.
      */
-    public SnippetTemplate(MetaAccessProvider runtime, Assumptions assumptions, TargetDescription target, SnippetTemplate.Key key) {
+    public SnippetTemplate(MetaAccessProvider runtime, Replacements replacements, TargetDescription target, SnippetTemplate.Key key) {
         ResolvedJavaMethod method = key.method;
         assert Modifier.isStatic(method.getModifiers()) : "snippet method must be static: " + method;
         Signature signature = method.getSignature();
 
         // Copy snippet graph, replacing constant parameters with given arguments
-        StructuredGraph snippetGraph = (StructuredGraph) method.getCompilerStorage().get(Snippet.class);
+        StructuredGraph snippetGraph = replacements.getSnippet(method);
         StructuredGraph snippetCopy = new StructuredGraph(snippetGraph.name, snippetGraph.method());
-        IdentityHashMap<Node, Node> replacements = new IdentityHashMap<>();
-        replacements.put(snippetGraph.start(), snippetCopy.start());
+        IdentityHashMap<Node, Node> nodeReplacements = new IdentityHashMap<>();
+        nodeReplacements.put(snippetGraph.start(), snippetCopy.start());
 
         int parameterCount = signature.getParameterCount(false);
         assert checkTemplate(runtime, key, parameterCount, method, signature);
@@ -260,7 +262,7 @@
                 } else {
                     constantArg = Constant.forBoxed(kind, arg);
                 }
-                replacements.put(snippetGraph.getLocal(i), ConstantNode.forConstant(constantArg, runtime, snippetCopy));
+                nodeReplacements.put(snippetGraph.getLocal(i), ConstantNode.forConstant(constantArg, runtime, snippetCopy));
             } else {
                 VarargsParameter vp = MetaUtil.getParameterAnnotation(VarargsParameter.class, i, method);
                 if (vp != null) {
@@ -268,7 +270,7 @@
                     Varargs varargs = (Varargs) key.get(name);
                     Object array = varargs.getArray();
                     ConstantNode placeholder = ConstantNode.forObject(array, runtime, snippetCopy);
-                    replacements.put(snippetGraph.getLocal(i), placeholder);
+                    nodeReplacements.put(snippetGraph.getLocal(i), placeholder);
                     placeholders[i] = placeholder;
                     varargsParameterAnnotations[i] = vp;
                 } else {
@@ -276,15 +278,15 @@
                 }
             }
         }
-        snippetCopy.addDuplicates(snippetGraph.getNodes(), replacements);
+        snippetCopy.addDuplicates(snippetGraph.getNodes(), nodeReplacements);
 
         Debug.dump(snippetCopy, "Before specialization");
-        if (!replacements.isEmpty()) {
+        if (!nodeReplacements.isEmpty()) {
             // Do deferred intrinsification of node intrinsics
             new NodeIntrinsificationPhase(runtime, new BoxingMethodPool(runtime)).apply(snippetCopy);
             new WordTypeRewriterPhase(runtime, target.wordKind).apply(snippetCopy);
 
-            new CanonicalizerPhase(runtime, assumptions, 0, null).apply(snippetCopy);
+            new CanonicalizerPhase(runtime, replacements.getAssumptions(), 0, null).apply(snippetCopy);
         }
         assert NodeIntrinsificationVerificationPhase.verify(snippetCopy);
 
@@ -344,7 +346,7 @@
                     LoopEx loop = new LoopsData(snippetCopy).loop(loopBegin);
                     int mark = snippetCopy.getMark();
                     LoopTransformations.fullUnroll(loop, runtime, null);
-                    new CanonicalizerPhase(runtime, assumptions, mark, null).apply(snippetCopy);
+                    new CanonicalizerPhase(runtime, replacements.getAssumptions(), mark, null).apply(snippetCopy);
                 }
                 FixedNode explodeLoopNext = explodeLoop.next();
                 explodeLoop.clearSuccessors();
--- a/make/build-graal.xml	Wed Apr 03 16:56:43 2013 +0200
+++ b/make/build-graal.xml	Wed Apr 03 21:51:44 2013 +0200
@@ -39,6 +39,7 @@
       <src path="${src.dir}/com.oracle.graal.nodes"/>
       <src path="${src.dir}/com.oracle.graal.phases"/>
       <src path="${src.dir}/com.oracle.graal.api.replacements"/>
+      <src path="${src.dir}/com.oracle.graal.api.runtime"/>
       <src path="${src.dir}/com.oracle.graal.phases.common"/>
       <src path="${src.dir}/com.oracle.graal.virtual"/>
       <src path="${src.dir}/com.oracle.graal.loop"/>
@@ -49,7 +50,6 @@
       <src path="${src.dir}/com.oracle.graal.bytecode"/>
       <src path="${src.dir}/com.oracle.graal.java"/>
       <src path="${src.dir}/com.oracle.graal.word"/>
-      <src path="${src.dir}/com.oracle.graal.api.runtime"/>
       <src path="${src.dir}/com.oracle.graal.replacements"/>
       <src path="${src.dir}/com.oracle.graal.printer"/>
       <src path="${src.dir}/com.oracle.graal.hotspot"/>
--- a/mx/projects	Wed Apr 03 16:56:43 2013 +0200
+++ b/mx/projects	Wed Apr 03 21:51:44 2013 +0200
@@ -61,7 +61,7 @@
 # graal.api.replacements
 project@com.oracle.graal.api.replacements@subDir=graal
 project@com.oracle.graal.api.replacements@sourceDirs=src
-project@com.oracle.graal.api.replacements@dependencies=com.oracle.graal.api.meta
+project@com.oracle.graal.api.replacements@dependencies=com.oracle.graal.nodes
 project@com.oracle.graal.api.replacements@checkstyle=com.oracle.graal.graph
 project@com.oracle.graal.api.replacements@javaCompliance=1.7
 
@@ -200,7 +200,7 @@
 # graal.replacements
 project@com.oracle.graal.replacements@subDir=graal
 project@com.oracle.graal.replacements@sourceDirs=src
-project@com.oracle.graal.replacements@dependencies=com.oracle.graal.compiler,com.oracle.graal.java,com.oracle.graal.word,com.oracle.graal.api.runtime
+project@com.oracle.graal.replacements@dependencies=com.oracle.graal.compiler,com.oracle.graal.java,com.oracle.graal.word
 project@com.oracle.graal.replacements@checkstyle=com.oracle.graal.graph
 project@com.oracle.graal.replacements@javaCompliance=1.7
 project@com.oracle.graal.replacements@annotationProcessors=com.oracle.graal.replacements.verifier,com.oracle.graal.service.processor
@@ -243,7 +243,7 @@
 # graal.phases.common
 project@com.oracle.graal.phases.common@subDir=graal
 project@com.oracle.graal.phases.common@sourceDirs=src
-project@com.oracle.graal.phases.common@dependencies=com.oracle.graal.phases,com.oracle.graal.api.replacements
+project@com.oracle.graal.phases.common@dependencies=com.oracle.graal.phases,com.oracle.graal.api.replacements,com.oracle.graal.api.runtime
 project@com.oracle.graal.phases.common@checkstyle=com.oracle.graal.graph
 project@com.oracle.graal.phases.common@javaCompliance=1.7
 
@@ -333,7 +333,7 @@
 # graal.compiler.test
 project@com.oracle.graal.compiler.test@subDir=graal
 project@com.oracle.graal.compiler.test@sourceDirs=src
-project@com.oracle.graal.compiler.test@dependencies=com.oracle.graal.api.runtime,com.oracle.graal.printer,com.oracle.graal.test
+project@com.oracle.graal.compiler.test@dependencies=com.oracle.graal.printer,com.oracle.graal.test
 project@com.oracle.graal.compiler.test@checkstyle=com.oracle.graal.graph
 project@com.oracle.graal.compiler.test@javaCompliance=1.7