--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Thu Jan 23 15:21:14 2014 -0800
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Thu Jan 23 16:15:04 2014 -0800
@@ -138,6 +138,7 @@
     public static <T extends CompilationResult> T compileGraph(StructuredGraph graph, CallingConvention cc, ResolvedJavaMethod installedCodeOwner, Providers providers, Backend backend,
                     TargetDescription target, GraphCache cache, PhaseSuite<HighTierContext> graphBuilderSuite, OptimisticOptimizations optimisticOpts, ProfilingInfo profilingInfo,
                     SpeculationLog speculationLog, Suites suites, boolean withScope, T compilationResult, CompilationResultBuilderFactory factory) {
+        assert !graph.isFrozen();
         try (Scope s0 = withScope ? Debug.scope("GraalCompiler", graph, providers.getCodeCache()) : null) {
             Assumptions assumptions = new Assumptions(OptAssumptions.getValue());
             LIR lir = null;

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Thu Jan 23 15:21:14 2014 -0800
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Thu Jan 23 16:15:04 2014 -0800
@@ -75,6 +75,12 @@
     NodeChangedListener usagesDroppedToZeroListener;
     private final HashMap<CacheEntry, Node> cachedNodes = new HashMap<>();
 
+    /*
+     * Indicates that the graph should no longer be modified. Frozen graphs can be used my multiple
+     * threads so it's only safe to read them.
+     */
+    private boolean isFrozen = false;
+
     private static final class CacheEntry {
 
         private final Node node;
@@ -761,6 +767,7 @@
     }
 
     void register(Node node) {
+        assert !isFrozen();
         assert node.id() == Node.INITIAL_ID;
         if (nodes.length == nodesSize) {
             nodes = Arrays.copyOf(nodes, (nodesSize * 2) + 1);
@@ -812,6 +819,7 @@
     }
 
     void unregister(Node node) {
+        assert !isFrozen();
         assert !node.isDeleted() : "cannot delete a node twice! node=" + node;
         logNodeDeleted(node);
         nodes[node.id] = null;
@@ -896,4 +904,12 @@
     public Map<Node, Node> addDuplicates(Iterable<Node> newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) {
         return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements);
     }
+
+    public boolean isFrozen() {
+        return isFrozen;
+    }
+
+    public void freeze() {
+        this.isFrozen = true;
+    }
 }

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Thu Jan 23 15:21:14 2014 -0800
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Thu Jan 23 16:15:04 2014 -0800
@@ -488,6 +488,7 @@
      * this node to newSuccessor's predecessors.
      */
     protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) {
+        assert graph == null || !graph.isFrozen();
         if (oldSuccessor != newSuccessor) {
             if (oldSuccessor != null) {
                 assert assertTrue(oldSuccessor.predecessor == this, "wrong predecessor in old successor (%s): %s", oldSuccessor, oldSuccessor.predecessor);
@@ -517,6 +518,7 @@
     }
 
     private boolean checkReplaceWith(Node other) {
+        assert assertTrue(graph == null || !graph.isFrozen(), "cannot modify frozen graph");
         assert assertFalse(other == this, "cannot replace a node with itself");
         assert assertFalse(isDeleted(), "cannot replace deleted node");
         assert assertTrue(other == null || !other.isDeleted(), "cannot replace with deleted node %s", other);
@@ -574,6 +576,7 @@
 
     public void clearInputs() {
         assert assertFalse(isDeleted(), "cannot clear inputs of deleted node");
+        assert graph == null || !graph.isFrozen();
 
         for (Node input : inputs()) {
             if (input.recordsUsages()) {

--- a/graal/com.oracle.graal.hotspot.test/src/com/oracle/graal/hotspot/test/HotSpotCryptoSubstitutionTest.java	Thu Jan 23 15:21:14 2014 -0800
+++ b/graal/com.oracle.graal.hotspot.test/src/com/oracle/graal/hotspot/test/HotSpotCryptoSubstitutionTest.java	Thu Jan 23 16:15:04 2014 -0800
@@ -115,6 +115,7 @@
                 ResolvedJavaMethod installedCodeOwner = getMetaAccess().lookupJavaMethod(method);
                 StructuredGraph graph = getReplacements().getMethodSubstitution(installedCodeOwner);
                 if (graph != null) {
+                    graph = graph.copy();
                     Assert.assertNotNull(getCode(installedCodeOwner, graph, true));
                     atLeastOneCompiled = true;
                 } else {

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsImpl.java	Thu Jan 23 15:21:14 2014 -0800
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsImpl.java	Thu Jan 23 16:15:04 2014 -0800
@@ -135,7 +135,9 @@
         if (graph == null) {
             graphs.putIfAbsent(substitute, makeGraph(substitute, original, substitute, inliningPolicy(substitute), FrameStateProcessing.None));
             graph = graphs.get(substitute);
+            graph.freeze();
         }
+        assert graph.isFrozen();
         return graph;
 
     }