--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/remote/LinkedIdentityHashMap.java	Sat Nov 15 16:39:23 2014 +0100
@@ -0,0 +1,251 @@
+/*
+ * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.common.remote;
+
+import java.util.*;
+import java.util.function.*;
+
+import com.oracle.graal.compiler.common.remote.Context.Mode;
+
+/**
+ * A map that combines {@link IdentityHashMap} with {@link LinkedHashMap} for the purpose of
+ * ensuring a deterministic execution order during {@link Mode#Capturing}.
+ */
+final class LinkedIdentityHashMap<K, V> implements Map<K, V> {
+
+    private final LinkedHashMap<Id<K>, V> map;
+
+    public LinkedIdentityHashMap() {
+        map = new LinkedHashMap<>();
+    }
+
+    public LinkedIdentityHashMap(Map<K, V> m) {
+        map = new LinkedHashMap<>(m.size());
+        putAll(m);
+    }
+
+    public LinkedIdentityHashMap(int expectedMaxSize) {
+        map = new LinkedHashMap<>(expectedMaxSize);
+    }
+
+    /**
+     * Wrapper for an object that gives uses the object's identity for the purpose of equality
+     * comparisons and computing a hash code.
+     */
+    public static class Id<T> {
+        final T object;
+
+        public Id(T object) {
+            assert object != null;
+            this.object = object;
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public boolean equals(Object obj) {
+            return ((Id<T>) obj).object == object;
+        }
+
+        @Override
+        public int hashCode() {
+            return System.identityHashCode(object);
+        }
+    }
+
+    public int size() {
+        return map.size();
+    }
+
+    public boolean isEmpty() {
+        return map.isEmpty();
+    }
+
+    public boolean containsKey(Object key) {
+        return map.containsKey(id(key));
+    }
+
+    @SuppressWarnings("unchecked")
+    private Id<K> id(Object key) {
+        if (key == null) {
+            return null;
+        }
+        return new Id<>((K) key);
+    }
+
+    public boolean containsValue(Object value) {
+        return map.containsValue(value);
+    }
+
+    public V get(Object key) {
+        return map.get(id(key));
+    }
+
+    public V put(K key, V value) {
+        return map.put(id(key), value);
+    }
+
+    public V remove(Object key) {
+        return map.remove(id(key));
+    }
+
+    @SuppressWarnings("unchecked")
+    public void putAll(Map<? extends K, ? extends V> m) {
+        if (m != null && m.getClass() == getClass()) {
+            LinkedIdentityHashMap<K, V> that = (LinkedIdentityHashMap<K, V>) m;
+            map.putAll(that.map);
+
+        } else {
+            for (K key : m.keySet()) {
+                map.put(id(key), m.get(key));
+            }
+        }
+    }
+
+    public void clear() {
+        map.clear();
+    }
+
+    final class KeySet extends AbstractSet<K> {
+        @Override
+        public int size() {
+            return map.size();
+        }
+
+        @Override
+        public void clear() {
+            map.clear();
+        }
+
+        @Override
+        public Iterator<K> iterator() {
+            return new Iterator<K>() {
+                final Iterator<Id<K>> i = map.keySet().iterator();
+
+                public boolean hasNext() {
+                    return i.hasNext();
+                }
+
+                public K next() {
+                    return i.next().object;
+                }
+
+                public void remove() {
+                    i.remove();
+                }
+            };
+        }
+
+        @Override
+        public boolean contains(Object o) {
+            return containsKey(o);
+        }
+
+        @Override
+        public boolean remove(Object o) {
+            return LinkedIdentityHashMap.this.remove(o) != null;
+        }
+
+        public Spliterator<K> spliterator() {
+            return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT);
+        }
+
+        public void forEach(Consumer<? super K> action) {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    public Set<K> keySet() {
+        return new KeySet();
+    }
+
+    public Collection<V> values() {
+        return map.values();
+    }
+
+    final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
+        @Override
+        public int size() {
+            return map.size();
+        }
+
+        @Override
+        public void clear() {
+            map.clear();
+        }
+
+        @Override
+        public Iterator<Map.Entry<K, V>> iterator() {
+            return new Iterator<Map.Entry<K, V>>() {
+                final Iterator<Map.Entry<Id<K>, V>> i = map.entrySet().iterator();
+
+                public boolean hasNext() {
+                    return i.hasNext();
+                }
+
+                public Map.Entry<K, V> next() {
+                    Map.Entry<Id<K>, V> e = i.next();
+                    return new Map.Entry<K, V>() {
+
+                        public K getKey() {
+                            return e.getKey().object;
+                        }
+
+                        public V getValue() {
+                            return e.getValue();
+                        }
+
+                        public V setValue(V value) {
+                            return e.setValue(value);
+                        }
+                    };
+                }
+
+                public void remove() {
+                    i.remove();
+                }
+            };
+        }
+
+        @Override
+        public boolean contains(Object o) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean remove(Object o) {
+            throw new UnsupportedOperationException();
+        }
+
+        public Spliterator<Map.Entry<K, V>> spliterator() {
+            throw new UnsupportedOperationException();
+        }
+
+        public void forEach(Consumer<? super Map.Entry<K, V>> action) {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    public Set<Map.Entry<K, V>> entrySet() {
+        return new EntrySet();
+    }
+}

--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Fri Nov 14 09:32:59 2014 -0800
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Sat Nov 15 16:39:23 2014 +0100
@@ -702,8 +702,8 @@
         return OUTPUT_DIR;
     }
 
-    protected String dissasembleToFile(CompilationResult original, ResolvedJavaMethod installedCodeOwner, String fileSuffix) {
-        String dis = getCodeCache().disassemble(original, null);
+    protected String dissasembleToFile(CompilationResult result, ResolvedJavaMethod installedCodeOwner, String fileSuffix) {
+        String dis = getCodeCache().disassemble(result, null);
         File disFile = new File(getOutputDir(), installedCodeOwner.format("%H.%n_%p").replace(", ", "__") + "." + fileSuffix);
         try (PrintStream ps = new PrintStream(new FileOutputStream(disFile))) {
             ps.println(dis);
@@ -713,18 +713,18 @@
         }
     }
 
-    protected void checkCompilationResultsEqual(Context c, String prefix, CompilationResult original, CompilationResult derived, ResolvedJavaMethod installedCodeOwner) {
-        if (!derived.equals(original)) {
+    protected void checkCompilationResultsEqual(Context c, String prefix, CompilationResult expected, CompilationResult actual, ResolvedJavaMethod installedCodeOwner) {
+        if (!actual.equals(expected)) {
             Mode mode = c.getMode();
             // Temporarily force capturing mode as dumping/printing/disassembling
             // may need to execute proxy methods that have not yet been executed
             c.setMode(Mode.Capturing);
             try {
-                String originalDisFile = dissasembleToFile(original, installedCodeOwner, "original");
-                String derivedDisFile = dissasembleToFile(derived, installedCodeOwner, "derived");
-                String message = String.format("%s compilation result differs from original compilation result", prefix);
-                if (originalDisFile != null && derivedDisFile != null) {
-                    message += String.format(" [diff %s %s]", originalDisFile, derivedDisFile);
+                String expectedDisFile = dissasembleToFile(expected, installedCodeOwner, "expected");
+                String actualDisFile = dissasembleToFile(actual, installedCodeOwner, "actual");
+                String message = String.format("%s compilation result differs from expected compilation result", prefix);
+                if (expectedDisFile != null && actualDisFile != null) {
+                    message += String.format(" [diff %s %s]", expectedDisFile, actualDisFile);
                 }
                 if (TEST_REPLAY_MISMATCH_IS_FAILURE) {
                     Assert.fail(message);
@@ -737,50 +737,35 @@
         }
     }
 
-    protected void testRecompile(Context c, Mode mode, CompilationResult originalResultInContext, ResolvedJavaMethod installedCodeOwner) {
+    protected CompilationResult testRecompile(Context c, Mode mode, CompilationResult expectedResult, ResolvedJavaMethod installedCodeOwner) {
         try (Debug.Scope s = Debug.scope(mode.name(), new DebugDumpScope(mode.name(), true))) {
 
             StructuredGraph graphToCompile = parseForCompile(installedCodeOwner);
+
             lastCompiledGraph = graphToCompile;
 
             CallingConvention cc = getCallingConvention(getCodeCache(), Type.JavaCallee, graphToCompile.method(), false);
             Request<CompilationResult> request = c.get(new GraalCompiler.Request<>(graphToCompile, null, cc, installedCodeOwner, getProviders(), getBackend(), getCodeCache().getTarget(), null,
                             getDefaultGraphBuilderSuite(), OptimisticOptimizations.ALL, getProfilingInfo(graphToCompile), getSpeculationLog(), getSuites(), new CompilationResult(),
                             CompilationResultBuilderFactory.Default));
-            checkCompilationResultsEqual(c, mode.name(), originalResultInContext, GraalCompiler.compile(request), installedCodeOwner);
+            CompilationResult result = GraalCompiler.compile(request);
+            if (expectedResult != null) {
+                checkCompilationResultsEqual(c, mode.name(), expectedResult, result, installedCodeOwner);
+            }
+            return result;
         } catch (Throwable e) {
             throw Debug.handle(e);
         }
     }
 
     protected void testReplayCompile(ResolvedJavaMethod installedCodeOwner) {
-        CompilationResult originalResult;
-
-        // Repeat the compilation without a context to account for any side-effects the
-        // initial compilation may have had. For example, if dumping was enabled then
-        // the dumping code may have changed profiles in methods that are inlined
-        // by the test method being compiled.
-        try (Debug.Scope s = Debug.scope("Repeating", new DebugDumpScope("Repeating", true))) {
-            StructuredGraph graphToCompile = parseForCompile(installedCodeOwner);
-            lastCompiledGraph = graphToCompile;
-            CallingConvention cc = getCallingConvention(getCodeCache(), Type.JavaCallee, graphToCompile.method(), false);
-            originalResult = GraalCompiler.compileGraph(graphToCompile, null, cc, installedCodeOwner, getProviders(), getBackend(), getCodeCache().getTarget(), null, getDefaultGraphBuilderSuite(),
-                            OptimisticOptimizations.ALL, getProfilingInfo(graphToCompile), getSpeculationLog(), getSuites(), new CompilationResult(), CompilationResultBuilderFactory.Default);
-        } catch (Throwable e) {
-            throw Debug.handle(e);
-        }
-
         try (Context c = new Context()) {
-            // Need to use an 'in context' copy of the original result when comparing for
-            // equality against other 'in context' results so that proxies are compared
-            // against proxies
-            CompilationResult originalResultInContext = c.get(originalResult);
 
             // Capturing compilation
-            testRecompile(c, Mode.Capturing, originalResultInContext, installedCodeOwner);
+            CompilationResult expected = testRecompile(c, Mode.Capturing, null, installedCodeOwner);
 
             // Replay compilation
-            testRecompile(c, Mode.Replaying, originalResultInContext, installedCodeOwner);
+            testRecompile(c, Mode.Replaying, expected, installedCodeOwner);
         }
     }
 

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Fri Nov 14 09:32:59 2014 -0800
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Sat Nov 15 16:39:23 2014 +0100
@@ -31,13 +31,14 @@
 import sun.misc.*;
 
 import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.remote.*;
 import com.oracle.graal.graph.Graph.NodeEventListener;
 import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodeinfo.*;
 
 /**
- * This class is the base class for all nodes, it represent a node which can be inserted in a
+ * This class is the base class for all nodes. It represents a node that can be inserted in a
  * {@link Graph}.
  * <p>
  * Once a node has been added to a graph, it has a graph-unique {@link #id()}. Edges in the
@@ -48,6 +49,11 @@
  * <p>
  * Nodes which are be value numberable should implement the {@link ValueNumberable} interface.
  *
+ * <h1>Replay Compilation</h1>
+ *
+ * To enable deterministic replay compilation, node hash set creation within a compilation scope
+ * must {@link #newNodeHashSet()} or {@link #newNodeHashSet(Collection)}.
+ *
  * <h1>Assertions and Verification</h1>
  *
  * The Node class supplies the {@link #assertTrue(boolean, String, Object...)} and
@@ -193,6 +199,22 @@
     }
 
     /**
+     * Creates a {@link Node} hash set. The return set will be a {@link LinkedHashSet} if the
+     * current thread has an active compilation replay scope. This is requires to make replay
+     * compilations deterministic.
+     */
+    public static <E extends Node> HashSet<E> newNodeHashSet() {
+        return Context.getCurrent() == null ? new HashSet<>() : new LinkedHashSet<>();
+    }
+
+    /**
+     * @see #newNodeHashSet()
+     */
+    public static <E extends Node> HashSet<E> newNodeHashSet(Collection<? extends E> c) {
+        return Context.getCurrent() == null ? new HashSet<>(c) : new LinkedHashSet<>(c);
+    }
+
+    /**
      * Gets the graph context of this node.
      */
     public Graph graph() {

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java	Fri Nov 14 09:32:59 2014 -0800
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java	Sat Nov 15 16:39:23 2014 +0100
@@ -434,7 +434,7 @@
 
             // build the intersection
             belowBound.intersect(aboveBound);
-            HashSet<Node> result = new HashSet<>();
+            HashSet<Node> result = Node.newNodeHashSet();
             for (Node node : belowBound) {
                 result.add(node);
             }
@@ -491,7 +491,7 @@
         }
 
         private void processUsages(Node duplicated, HashSet<Node> duplicatedNodes, MergeNode newBottomMerge, Deque<Node> worklist) {
-            HashSet<Node> unique = new HashSet<>();
+            HashSet<Node> unique = Node.newNodeHashSet();
             duplicated.usages().snapshotTo(unique);
             Node newOutsideClone = null;
             for (Node usage : unique) {

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ValueAnchorCleanupPhase.java	Fri Nov 14 09:32:59 2014 -0800
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ValueAnchorCleanupPhase.java	Sat Nov 15 16:39:23 2014 +0100
@@ -42,11 +42,11 @@
         private final HashSet<Node> anchoredValues;
 
         public State() {
-            anchoredValues = new HashSet<>();
+            anchoredValues = Node.newNodeHashSet();
         }
 
         public State(State other) {
-            anchoredValues = new HashSet<>(other.anchoredValues);
+            anchoredValues = Node.newNodeHashSet(other.anchoredValues);
         }
 
         @Override

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/InliningData.java	Fri Nov 14 09:32:59 2014 -0800
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/InliningData.java	Sat Nov 15 16:39:23 2014 +0100
@@ -22,37 +22,28 @@
  */
 package com.oracle.graal.phases.common.inlining.walker;
 
-import com.oracle.graal.api.code.Assumptions;
-import com.oracle.graal.api.code.BailoutException;
-import com.oracle.graal.api.meta.JavaTypeProfile;
-import com.oracle.graal.api.meta.ResolvedJavaMethod;
-import com.oracle.graal.api.meta.ResolvedJavaType;
-import com.oracle.graal.compiler.common.GraalInternalError;
-import com.oracle.graal.compiler.common.type.ObjectStamp;
-import com.oracle.graal.debug.Debug;
-import com.oracle.graal.debug.DebugMetric;
-import com.oracle.graal.graph.Graph;
-import com.oracle.graal.graph.Node;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.java.AbstractNewObjectNode;
-import com.oracle.graal.nodes.java.MethodCallTargetNode;
-import com.oracle.graal.nodes.virtual.AllocatedObjectNode;
-import com.oracle.graal.nodes.virtual.VirtualObjectNode;
-import com.oracle.graal.phases.OptimisticOptimizations;
-import com.oracle.graal.phases.common.CanonicalizerPhase;
-import com.oracle.graal.phases.common.inlining.InliningUtil;
-import com.oracle.graal.phases.common.inlining.info.*;
-import com.oracle.graal.phases.common.inlining.info.elem.Inlineable;
-import com.oracle.graal.phases.common.inlining.info.elem.InlineableGraph;
-import com.oracle.graal.phases.common.inlining.info.elem.InlineableMacroNode;
-import com.oracle.graal.phases.common.inlining.policy.InliningPolicy;
-import com.oracle.graal.phases.tiers.HighTierContext;
-import com.oracle.graal.phases.util.Providers;
+import static com.oracle.graal.compiler.common.GraalOptions.*;
+import static com.oracle.graal.phases.common.inlining.walker.CallsiteHolderDummy.*;
 
 import java.util.*;
 
-import static com.oracle.graal.compiler.common.GraalOptions.*;
-import static com.oracle.graal.phases.common.inlining.walker.CallsiteHolderDummy.DUMMY_CALLSITE_HOLDER;
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.type.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.nodes.virtual.*;
+import com.oracle.graal.phases.*;
+import com.oracle.graal.phases.common.*;
+import com.oracle.graal.phases.common.inlining.*;
+import com.oracle.graal.phases.common.inlining.info.*;
+import com.oracle.graal.phases.common.inlining.info.elem.*;
+import com.oracle.graal.phases.common.inlining.policy.*;
+import com.oracle.graal.phases.tiers.*;
+import com.oracle.graal.phases.util.*;
 
 /**
  * <p>
@@ -368,7 +359,7 @@
         InlineInfo calleeInfo = calleeInvocation.callee();
         try {
             try (Debug.Scope scope = Debug.scope("doInline", callerGraph)) {
-                Set<Node> canonicalizedNodes = new HashSet<>();
+                Set<Node> canonicalizedNodes = Node.newNodeHashSet();
                 calleeInfo.invoke().asNode().usages().snapshotTo(canonicalizedNodes);
                 Collection<Node> parameterUsages = calleeInfo.inline(new Providers(context), callerAssumptions);
                 canonicalizedNodes.addAll(parameterUsages);

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/util/HashSetNodeEventListener.java	Fri Nov 14 09:32:59 2014 -0800
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/util/HashSetNodeEventListener.java	Sat Nov 15 16:39:23 2014 +0100
@@ -40,7 +40,7 @@
      * Creates a {@link NodeEventListener} that collects nodes from all events.
      */
     public HashSetNodeEventListener() {
-        this.nodes = new HashSet<>();
+        this.nodes = Node.newNodeHashSet();
         this.filter = EnumSet.allOf(NodeEvent.class);
     }
 

--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/IdealGraphPrinter.java	Fri Nov 14 09:32:59 2014 -0800
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/IdealGraphPrinter.java	Sat Nov 15 16:39:23 2014 +0100
@@ -84,7 +84,7 @@
     @Override
     public void print(Graph graph, String title, SchedulePhase predefinedSchedule) {
         beginGraph(title);
-        Set<Node> noBlockNodes = new HashSet<>();
+        Set<Node> noBlockNodes = Node.newNodeHashSet();
         SchedulePhase schedule = predefinedSchedule;
         if (schedule == null && tryToSchedule) {
             if (PrintIdealGraphSchedule.getValue()) {
@@ -249,7 +249,7 @@
         endSuccessors();
         beginBlockNodes();
 
-        Set<Node> nodes = new HashSet<>();
+        Set<Node> nodes = Node.newNodeHashSet();
 
         if (nodeToBlock != null) {
             for (Node n : graph.getNodes()) {
@@ -270,7 +270,7 @@
                 }
             }
 
-            Set<Node> snapshot = new HashSet<>(nodes);
+            Set<Node> snapshot = Node.newNodeHashSet(nodes);
             // add all framestates and phis to their blocks
             for (Node node : snapshot) {
                 if (node instanceof StateSplit && ((StateSplit) node).stateAfter() != null) {