Mercurial > hg > truffle

changeset 19757:e8d2f3f95dcd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Truffle-DSL: implemented duplication check for specializations with @Cached to avoid duplicates for multithreaded AST execution.
author Christian Humer <christian.humer@gmail.com>
date Tue, 10 Mar 2015 19:28:26 +0100
parents d03352ba2efb
children f682b9e6ca07
files graal/com.oracle.truffle.api.dsl.test/src/com/oracle/truffle/api/dsl/test/MergeSpecializationsTest.java graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/internal/RewriteEvent.java graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/internal/SlowPathEvent.java graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/internal/SpecializationNode.java graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/generator/NodeGenFactory.java
diffstat 5 files changed, 646 insertions(+), 309 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.truffle.api.dsl.test/src/com/oracle/truffle/api/dsl/test/MergeSpecializationsTest.java	Tue Mar 10 13:47:46 2015 +0100
+++ b/graal/com.oracle.truffle.api.dsl.test/src/com/oracle/truffle/api/dsl/test/MergeSpecializationsTest.java	Tue Mar 10 19:28:26 2015 +0100
@@ -40,7 +40,7 @@
 
 public class MergeSpecializationsTest {
 
-    private static final int THREADS = 8;
+    private static final int THREADS = 50;
 
     @NodeChild
     @SuppressWarnings("unused")
@@ -92,19 +92,16 @@
         multithreadedMerge(TestNodeFactory.getInstance(), new Executions(1.0, 1L << 32, 1), 3, 2, 1);
     }
 
-    @Ignore
     @Test
     public void testMultithreadedMergeCachedInOrder() {
         multithreadedMerge(TestCachedNodeFactory.getInstance(), new Executions(1, 1L << 32, 1.0), 1, 2, 3);
     }
 
-    @Ignore
     @Test
     public void testMultithreadedMergeCachedTwoEntries() {
         multithreadedMerge(TestCachedNodeFactory.getInstance(), new Executions(1, 2, 1.0), 1, 1, 3);
     }
 
-    @Ignore
     @Test
     public void testMultithreadedMergeCachedThreeEntries() {
         multithreadedMerge(TestCachedNodeFactory.getInstance(), new Executions(1, 2, 3), 1, 1, 1);
--- a/graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/internal/RewriteEvent.java	Tue Mar 10 13:47:46 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,200 +0,0 @@
-/*
- * 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.  Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * 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.truffle.api.dsl.internal;
-
-import com.oracle.truffle.api.nodes.*;
-
-/**
- * Lazy rewrite event that implements {@link CharSequence} to be provided as message in
- * {@link Node#replace(Node, CharSequence)}.
- */
-abstract class RewriteEvent implements CharSequence {
-
-    private final Node source;
-    private final String reason;
-    private String message;
-
-    private RewriteEvent(Node source, String reason) {
-        this.source = source;
-        this.reason = reason;
-    }
-
-    public int length() {
-        return getMessage().length();
-    }
-
-    public char charAt(int index) {
-        return getMessage().charAt(index);
-    }
-
-    public CharSequence subSequence(int start, int end) {
-        return getMessage().subSequence(start, end);
-    }
-
-    @Override
-    public String toString() {
-        return getMessage();
-    }
-
-    private String getMessage() {
-        if (message == null) {
-            message = createMessage();
-        }
-        return message;
-    }
-
-    private String createMessage() {
-        StringBuilder builder = new StringBuilder();
-        builder.append(source);
-        builder.append(" ");
-        builder.append(reason);
-        Object[] values = getValues();
-        if (values.length > 0) {
-            builder.append(" with parameters (");
-            String sep = "";
-            for (Object value : values) {
-                builder.append(sep);
-                if (value == null) {
-                    builder.append("null");
-                } else {
-                    builder.append(value).append(" (").append(value.getClass().getSimpleName()).append(")");
-                }
-
-                sep = ", ";
-            }
-            builder.append(")");
-        }
-        return builder.toString();
-    }
-
-    public abstract Object[] getValues();
-
-    static final class RewriteEvent0 extends RewriteEvent {
-
-        private static final Object[] EMPTY = new Object[0];
-
-        public RewriteEvent0(Node source, String reason) {
-            super(source, reason);
-        }
-
-        @Override
-        public Object[] getValues() {
-            return EMPTY;
-        }
-
-    }
-
-    static final class RewriteEvent1 extends RewriteEvent {
-
-        private final Object o1;
-
-        public RewriteEvent1(Node source, String reason, Object o1) {
-            super(source, reason);
-            this.o1 = o1;
-        }
-
-        @Override
-        public Object[] getValues() {
-            return new Object[]{o1};
-        }
-
-    }
-
-    static final class RewriteEvent2 extends RewriteEvent {
-
-        private final Object o1;
-        private final Object o2;
-
-        public RewriteEvent2(Node source, String reason, Object o1, Object o2) {
-            super(source, reason);
-            this.o1 = o1;
-            this.o2 = o2;
-        }
-
-        @Override
-        public Object[] getValues() {
-            return new Object[]{o1, o2};
-        }
-
-    }
-
-    static final class RewriteEvent3 extends RewriteEvent {
-
-        private final Object o1;
-        private final Object o2;
-        private final Object o3;
-
-        public RewriteEvent3(Node source, String reason, Object o1, Object o2, Object o3) {
-            super(source, reason);
-            this.o1 = o1;
-            this.o2 = o2;
-            this.o3 = o3;
-        }
-
-        @Override
-        public Object[] getValues() {
-            return new Object[]{o1, o2, o3};
-        }
-
-    }
-
-    static final class RewriteEvent4 extends RewriteEvent {
-
-        private final Object o1;
-        private final Object o2;
-        private final Object o3;
-        private final Object o4;
-
-        public RewriteEvent4(Node source, String reason, Object o1, Object o2, Object o3, Object o4) {
-            super(source, reason);
-            this.o1 = o1;
-            this.o2 = o2;
-            this.o3 = o3;
-            this.o4 = o4;
-        }
-
-        @Override
-        public Object[] getValues() {
-            return new Object[]{o1, o2, o3, o4};
-        }
-
-    }
-
-    static final class RewriteEventN extends RewriteEvent {
-
-        private final Object[] args;
-
-        public RewriteEventN(Node source, String reason, Object... args) {
-            super(source, reason);
-            this.args = args;
-        }
-
-        @Override
-        public Object[] getValues() {
-            return args;
-        }
-
-    }
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/internal/SlowPathEvent.java	Tue Mar 10 19:28:26 2015 +0100
@@ -0,0 +1,227 @@
+/*
+ * 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.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * 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.truffle.api.dsl.internal;
+
+import com.oracle.truffle.api.frame.*;
+import com.oracle.truffle.api.nodes.*;
+
+/**
+ * Lazy rewrite event that implements {@link CharSequence} to be provided as message in
+ * {@link Node#replace(Node, CharSequence)}.
+ */
+abstract class SlowPathEvent implements CharSequence {
+
+    protected final SpecializationNode source;
+    protected final String reason;
+    protected final Frame frame;
+    private String message;
+
+    SlowPathEvent(SpecializationNode source, String reason, Frame frame) {
+        this.source = source;
+        this.reason = reason;
+        this.frame = frame;
+    }
+
+    public int length() {
+        return getMessage().length();
+    }
+
+    public char charAt(int index) {
+        return getMessage().charAt(index);
+    }
+
+    public CharSequence subSequence(int start, int end) {
+        return getMessage().subSequence(start, end);
+    }
+
+    @Override
+    public String toString() {
+        return getMessage();
+    }
+
+    private String getMessage() {
+        if (message == null) {
+            message = createMessage();
+        }
+        return message;
+    }
+
+    private String createMessage() {
+        StringBuilder builder = new StringBuilder();
+        builder.append(source);
+        builder.append(" ");
+        builder.append(reason);
+        Object[] values = getValues();
+        if (values.length > 0) {
+            builder.append(" with parameters (");
+            String sep = "";
+            for (Object value : values) {
+                builder.append(sep);
+                if (value == null) {
+                    builder.append("null");
+                } else {
+                    builder.append(value).append(" (").append(value.getClass().getSimpleName()).append(")");
+                }
+
+                sep = ", ";
+            }
+            builder.append(")");
+        }
+        return builder.toString();
+    }
+
+    public abstract Object[] getValues();
+
+    static class SlowPathEvent0 extends SlowPathEvent {
+
+        private static final Object[] EMPTY = new Object[0];
+
+        public SlowPathEvent0(SpecializationNode source, String reason, Frame frame) {
+            super(source, reason, frame);
+        }
+
+        @Override
+        public final Object[] getValues() {
+            return EMPTY;
+        }
+
+    }
+
+    static class SlowPathEvent1 extends SlowPathEvent {
+
+        protected final Object o1;
+
+        public SlowPathEvent1(SpecializationNode source, String reason, Frame frame, Object o1) {
+            super(source, reason, frame);
+            this.o1 = o1;
+        }
+
+        @Override
+        public final Object[] getValues() {
+            return new Object[]{o1};
+        }
+
+    }
+
+    static class SlowPathEvent2 extends SlowPathEvent {
+
+        protected final Object o1;
+        protected final Object o2;
+
+        public SlowPathEvent2(SpecializationNode source, String reason, Frame frame, Object o1, Object o2) {
+            super(source, reason, frame);
+            this.o1 = o1;
+            this.o2 = o2;
+        }
+
+        @Override
+        public final Object[] getValues() {
+            return new Object[]{o1, o2};
+        }
+
+    }
+
+    static class SlowPathEvent3 extends SlowPathEvent {
+
+        protected final Object o1;
+        protected final Object o2;
+        protected final Object o3;
+
+        public SlowPathEvent3(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3) {
+            super(source, reason, frame);
+            this.o1 = o1;
+            this.o2 = o2;
+            this.o3 = o3;
+        }
+
+        @Override
+        public final Object[] getValues() {
+            return new Object[]{o1, o2, o3};
+        }
+
+    }
+
+    static class SlowPathEvent4 extends SlowPathEvent {
+
+        protected final Object o1;
+        protected final Object o2;
+        protected final Object o3;
+        protected final Object o4;
+
+        public SlowPathEvent4(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3, Object o4) {
+            super(source, reason, frame);
+            this.o1 = o1;
+            this.o2 = o2;
+            this.o3 = o3;
+            this.o4 = o4;
+        }
+
+        @Override
+        public final Object[] getValues() {
+            return new Object[]{o1, o2, o3, o4};
+        }
+
+    }
+
+    static class SlowPathEvent5 extends SlowPathEvent {
+
+        protected final Object o1;
+        protected final Object o2;
+        protected final Object o3;
+        protected final Object o4;
+        protected final Object o5;
+
+        public SlowPathEvent5(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3, Object o4, Object o5) {
+            super(source, reason, frame);
+            this.o1 = o1;
+            this.o2 = o2;
+            this.o3 = o3;
+            this.o4 = o4;
+            this.o5 = o5;
+        }
+
+        @Override
+        public final Object[] getValues() {
+            return new Object[]{o1, o2, o3, o4, o5};
+        }
+
+    }
+
+    static class SlowPathEventN extends SlowPathEvent {
+
+        protected final Object[] args;
+
+        public SlowPathEventN(SpecializationNode source, String reason, Frame frame, Object... args) {
+            super(source, reason, frame);
+            this.args = args;
+        }
+
+        @Override
+        public final Object[] getValues() {
+            return args;
+        }
+
+    }
+}
--- a/graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/internal/SpecializationNode.java	Tue Mar 10 13:47:46 2015 +0100
+++ b/graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/internal/SpecializationNode.java	Tue Mar 10 19:28:26 2015 +0100
@@ -30,12 +30,13 @@
 
 import com.oracle.truffle.api.*;
 import com.oracle.truffle.api.dsl.*;
-import com.oracle.truffle.api.dsl.internal.RewriteEvent.RewriteEvent0;
-import com.oracle.truffle.api.dsl.internal.RewriteEvent.RewriteEvent1;
-import com.oracle.truffle.api.dsl.internal.RewriteEvent.RewriteEvent2;
-import com.oracle.truffle.api.dsl.internal.RewriteEvent.RewriteEvent3;
-import com.oracle.truffle.api.dsl.internal.RewriteEvent.RewriteEvent4;
-import com.oracle.truffle.api.dsl.internal.RewriteEvent.RewriteEventN;
+import com.oracle.truffle.api.dsl.internal.SlowPathEvent.SlowPathEvent0;
+import com.oracle.truffle.api.dsl.internal.SlowPathEvent.SlowPathEvent1;
+import com.oracle.truffle.api.dsl.internal.SlowPathEvent.SlowPathEvent2;
+import com.oracle.truffle.api.dsl.internal.SlowPathEvent.SlowPathEvent3;
+import com.oracle.truffle.api.dsl.internal.SlowPathEvent.SlowPathEvent4;
+import com.oracle.truffle.api.dsl.internal.SlowPathEvent.SlowPathEvent5;
+import com.oracle.truffle.api.dsl.internal.SlowPathEvent.SlowPathEventN;
 import com.oracle.truffle.api.frame.*;
 import com.oracle.truffle.api.nodes.*;
 import com.oracle.truffle.api.nodes.NodeUtil.NodeClass;
@@ -44,13 +45,13 @@
 /**
  * Internal implementation dependent base class for generated specialized nodes.
  */
+@NodeInfo(cost = NodeCost.NONE)
 @SuppressWarnings("unused")
-@NodeInfo(cost = NodeCost.NONE)
 public abstract class SpecializationNode extends Node {
 
     @Child protected SpecializationNode next;
 
-    private final int index;
+    final int index;
 
     public SpecializationNode() {
         this(-1);
@@ -92,10 +93,9 @@
         }
     }
 
-    protected final SpecializationNode polymorphicMerge(SpecializationNode newNode) {
-        SpecializationNode merged = next.merge(newNode);
-        if (merged == newNode && !isSame(newNode) && count() <= 2) {
-            return removeSame(new RewriteEvent0(findRoot(), "merged polymorphic to monomorphic"));
+    protected final SpecializationNode polymorphicMerge(SpecializationNode newNode, SpecializationNode merged) {
+        if (merged == newNode && count() <= 2) {
+            return removeSame(new SlowPathEvent0(this, "merged polymorphic to monomorphic", null));
         }
         return merged;
     }
@@ -114,15 +114,85 @@
 
     protected abstract Node[] getSuppliedChildren();
 
-    protected SpecializationNode merge(SpecializationNode newNode) {
-        if (this.isSame(newNode)) {
+    protected SpecializationNode merge(SpecializationNode newNode, Frame frame) {
+        if (isIdentical(newNode, frame)) {
+            return this;
+        }
+        return next != null ? next.merge(newNode, frame) : newNode;
+    }
+
+    protected SpecializationNode merge(SpecializationNode newNode, Frame frame, Object o1) {
+        if (isIdentical(newNode, frame, o1)) {
+            return this;
+        }
+        return next != null ? next.merge(newNode, frame, o1) : newNode;
+    }
+
+    protected SpecializationNode merge(SpecializationNode newNode, Frame frame, Object o1, Object o2) {
+        if (isIdentical(newNode, frame, o1, o2)) {
+            return this;
+        }
+        return next != null ? next.merge(newNode, frame, o1, o2) : newNode;
+    }
+
+    protected SpecializationNode merge(SpecializationNode newNode, Frame frame, Object o1, Object o2, Object o3) {
+        if (isIdentical(newNode, frame, o1, o2, o3)) {
+            return this;
+        }
+        return next != null ? next.merge(newNode, frame, o1, o2, o3) : newNode;
+    }
+
+    protected SpecializationNode merge(SpecializationNode newNode, Frame frame, Object o1, Object o2, Object o3, Object o4) {
+        if (isIdentical(newNode, frame, o1, o2, o3, o4)) {
+            return this;
+        }
+        return next != null ? next.merge(newNode, frame, o1, o2, o3, o4) : newNode;
+    }
+
+    protected SpecializationNode merge(SpecializationNode newNode, Frame frame, Object o1, Object o2, Object o3, Object o4, Object o5) {
+        if (isIdentical(newNode, frame, o1, o2, o3, o4, o5)) {
             return this;
         }
-        return next != null ? next.merge(newNode) : newNode;
+        return next != null ? next.merge(newNode, frame, o1, o2, o3, o4, o5) : newNode;
+    }
+
+    protected SpecializationNode merge(SpecializationNode newNode, Frame frame, Object... args) {
+        if (isIdentical(newNode, frame, args)) {
+            return this;
+        }
+        return next != null ? next.merge(newNode, frame, args) : newNode;
+    }
+
+    protected boolean isSame(SpecializationNode other) {
+        return getClass() == other.getClass();
+    }
+
+    protected boolean isIdentical(SpecializationNode newNode, Frame frame) {
+        return isSame(newNode);
     }
 
-    protected SpecializationNode mergeNoSame(SpecializationNode newNode) {
-        return next != null ? next.merge(newNode) : newNode;
+    protected boolean isIdentical(SpecializationNode newNode, Frame frame, Object o1) {
+        return isSame(newNode);
+    }
+
+    protected boolean isIdentical(SpecializationNode newNode, Frame frame, Object o1, Object o2) {
+        return isSame(newNode);
+    }
+
+    protected boolean isIdentical(SpecializationNode newNode, Frame frame, Object o1, Object o2, Object o3) {
+        return isSame(newNode);
+    }
+
+    protected boolean isIdentical(SpecializationNode newNode, Frame frame, Object o1, Object o2, Object o3, Object o4) {
+        return isSame(newNode);
+    }
+
+    protected boolean isIdentical(SpecializationNode newNode, Frame frame, Object o1, Object o2, Object o3, Object o4, Object o5) {
+        return isSame(newNode);
+    }
+
+    protected boolean isIdentical(SpecializationNode newNode, Frame frame, Object... args) {
+        return isSame(newNode);
     }
 
     protected final int countSame(SpecializationNode node) {
@@ -150,10 +220,6 @@
         return index;
     }
 
-    protected boolean isSame(SpecializationNode other) {
-        return getClass() == other.getClass();
-    }
-
     private int count() {
         return next != null ? next.count() + 1 : 1;
     }
@@ -226,8 +292,12 @@
         return findStart().getParent();
     }
 
-    private SpecializationNode removeSameImpl(SpecializationNode toRemove, CharSequence reason) {
-        SpecializationNode start = findStart();
+    private SpecializedNode findSpecializedNode() {
+        return (SpecializedNode) findEnd().findStart().getParent();
+    }
+
+    private static SpecializationNode removeSameImpl(SpecializationNode toRemove, CharSequence reason) {
+        SpecializationNode start = toRemove.findStart();
         SpecializationNode current = start;
         while (current != null) {
             if (current.isSame(toRemove)) {
@@ -238,7 +308,7 @@
             }
             current = current.next;
         }
-        return findEnd().findStart();
+        return toRemove.findEnd().findStart();
     }
 
     public Object acceptAndExecute(Frame frame) {
@@ -314,7 +384,7 @@
         if (nextSpecialization == null) {
             return unsupported(frame);
         }
-        return insertSpecialization(nextSpecialization, new RewriteEvent0(findRoot(), "inserted new specialization")).acceptAndExecute(frame);
+        return atomic(new InsertionEvent0(this, "insert new specialization", frame, nextSpecialization)).acceptAndExecute(frame);
     }
 
     protected final Object uninitialized(Frame frame, Object o1) {
@@ -326,7 +396,7 @@
         if (nextSpecialization == null) {
             return unsupported(frame, o1);
         }
-        return insertSpecialization(nextSpecialization, new RewriteEvent1(findRoot(), "inserted new specialization", o1)).acceptAndExecute(frame, o1);
+        return atomic(new InsertionEvent1(this, "insert new specialization", frame, o1, nextSpecialization)).acceptAndExecute(frame, o1);
     }
 
     protected final Object uninitialized(Frame frame, Object o1, Object o2) {
@@ -338,7 +408,7 @@
         if (nextSpecialization == null) {
             return unsupported(frame, o1, o2);
         }
-        return insertSpecialization(nextSpecialization, new RewriteEvent2(findRoot(), "inserted new specialization", o1, o2)).acceptAndExecute(frame, o1, o2);
+        return atomic(new InsertionEvent2(this, "insert new specialization", frame, o1, o2, nextSpecialization)).acceptAndExecute(frame, o1, o2);
     }
 
     protected final Object uninitialized(Frame frame, Object o1, Object o2, Object o3) {
@@ -350,7 +420,7 @@
         if (nextSpecialization == null) {
             return unsupported(frame, o1, o2, o3);
         }
-        return insertSpecialization(nextSpecialization, new RewriteEvent3(findRoot(), "inserted new specialization", o1, o2, o3)).acceptAndExecute(frame, o1, o2, o3);
+        return atomic(new InsertionEvent3(this, "insert new specialization", frame, o1, o2, o3, nextSpecialization)).acceptAndExecute(frame, o1, o2, o3);
     }
 
     protected final Object uninitialized(Frame frame, Object o1, Object o2, Object o3, Object o4) {
@@ -362,7 +432,7 @@
         if (nextSpecialization == null) {
             return unsupported(frame, o1, o2, o3, o4);
         }
-        return insertSpecialization(nextSpecialization, new RewriteEvent4(findRoot(), "inserts new specialization", o1, o2, o3, o4)).acceptAndExecute(frame, o1, o2, o3, o4);
+        return atomic(new InsertionEvent4(this, "insert new specialization", frame, o1, o2, o3, o4, nextSpecialization)).acceptAndExecute(frame, o1, o2, o3, o4);
     }
 
     protected final Object uninitialized(Frame frame, Object o1, Object o2, Object o3, Object o4, Object o5) {
@@ -374,7 +444,7 @@
         if (nextSpecialization == null) {
             unsupported(frame, o1, o2, o3, o4, o5);
         }
-        return insertSpecialization(nextSpecialization, new RewriteEventN(findRoot(), "inserts new specialization", o1, o2, o3, o4, o5)).acceptAndExecute(frame, o1, o2, o3, o4, o5);
+        return atomic(new InsertionEvent5(this, "insert new specialization", frame, o1, o2, o3, o4, o5, nextSpecialization)).acceptAndExecute(frame, o1, o2, o3, o4, o5);
     }
 
     protected final Object uninitialized(Frame frame, Object... args) {
@@ -386,39 +456,35 @@
         if (nextSpecialization == null) {
             unsupported(frame, args);
         }
-        return insertSpecialization(nextSpecialization, new RewriteEventN(findRoot(), "inserts new specialization", args)).acceptAndExecute(frame, args);
-    }
-
-    private boolean needsPolymorphic() {
-        return findStart().count() == 2;
+        return atomic(new InsertionEventN(this, "insert new specialization", frame, args, nextSpecialization)).acceptAndExecute(frame, args);
     }
 
     protected final Object remove(String reason, Frame frame) {
-        return removeSame(new RewriteEvent0(findRoot(), reason)).acceptAndExecute(frame);
+        return atomic(new RemoveEvent0(this, reason, frame)).acceptAndExecute(frame);
     }
 
     protected final Object remove(String reason, Frame frame, Object o1) {
-        return removeSame(new RewriteEvent1(findRoot(), reason, o1)).acceptAndExecute(frame, o1);
+        return atomic(new RemoveEvent1(this, reason, frame, o1)).acceptAndExecute(frame, o1);
     }
 
     protected final Object remove(String reason, Frame frame, Object o1, Object o2) {
-        return removeSame(new RewriteEvent2(findRoot(), reason, o1, o2)).acceptAndExecute(frame, o1, o2);
+        return atomic(new RemoveEvent2(this, reason, frame, o1, o2)).acceptAndExecute(frame, o1, o2);
     }
 
     protected final Object remove(String reason, Frame frame, Object o1, Object o2, Object o3) {
-        return removeSame(new RewriteEvent3(findRoot(), reason, o1, o2, o3)).acceptAndExecute(frame, o1, o2, o3);
+        return atomic(new RemoveEvent3(this, reason, frame, o1, o2, o3)).acceptAndExecute(frame, o1, o2, o3);
     }
 
     protected final Object remove(String reason, Frame frame, Object o1, Object o2, Object o3, Object o4) {
-        return removeSame(new RewriteEvent4(findRoot(), reason, o1, o2, o3, o4)).acceptAndExecute(frame, o1, o2, o3, o4);
+        return atomic(new RemoveEvent4(this, reason, frame, o1, o2, o3, o4)).acceptAndExecute(frame, o1, o2, o3, o4);
     }
 
     protected final Object remove(String reason, Frame frame, Object o1, Object o2, Object o3, Object o4, Object o5) {
-        return removeSame(new RewriteEventN(findRoot(), reason, o1, o2, o3, o4, o5)).acceptAndExecute(frame, o1, o2, o3, o4, o5);
+        return atomic(new RemoveEvent5(this, reason, frame, o1, o2, o3, o4, o5)).acceptAndExecute(frame, o1, o2, o3, o4, o5);
     }
 
     protected final Object remove(String reason, Frame frame, Object... args) {
-        return removeSame(new RewriteEventN(findRoot(), reason, args)).acceptAndExecute(frame, args);
+        return atomic(new RemoveEventN(this, reason, frame, args)).acceptAndExecute(frame, args);
     }
 
     protected Object unsupported(Frame frame) {
@@ -449,49 +515,24 @@
         throw new UnsupportedSpecializationException(findRoot(), getSuppliedChildren(), args);
     }
 
-    private SpecializationNode insertSpecialization(final SpecializationNode generated, final CharSequence message) {
-        return atomic(new Callable<SpecializationNode>() {
-            public SpecializationNode call() {
-                return insert(generated, message);
-            }
-        });
-    }
-
-    private SpecializationNode insert(final SpecializationNode generated, CharSequence message) {
-        SpecializationNode start = findStart();
-        if (start == this) {
-            // fast path for first insert
-            return insertBefore(this, generated, message);
-        } else {
-            return slowSortedInsert(start, generated, message);
-        }
-    }
-
-    private static <T> SpecializationNode slowSortedInsert(SpecializationNode start, final SpecializationNode generated, final CharSequence message) {
-        final SpecializationNode merged = start.merge(generated);
+    static SpecializationNode insertSorted(SpecializationNode start, final SpecializationNode generated, final CharSequence message, final SpecializationNode merged) {
         if (merged == generated) {
             // new node
             if (start.count() == 2) {
-                insertBefore(start, start.createPolymorphic(), "insert polymorphic");
+                insertAt(start, start.createPolymorphic(), "insert polymorphic");
             }
-            SpecializationNode insertBefore = findInsertBeforeNode(generated.index, start);
-            return insertBefore(insertBefore, generated, message);
+            SpecializationNode current = start;
+            while (current != null && current.index < generated.index) {
+                current = current.next;
+            }
+            return insertAt(current, generated, message);
         } else {
             // existing node
-            merged.replace(merged, new RewriteEvent0(merged.findRoot(), "merged specialization"));
             return start;
         }
     }
 
-    private static SpecializationNode findInsertBeforeNode(int generatedIndex, SpecializationNode start) {
-        SpecializationNode current = start;
-        while (current != null && current.index < generatedIndex) {
-            current = current.next;
-        }
-        return current;
-    }
-
-    private static <T> SpecializationNode insertBefore(SpecializationNode node, SpecializationNode insertBefore, CharSequence message) {
+    static <T> SpecializationNode insertAt(SpecializationNode node, SpecializationNode insertBefore, CharSequence message) {
         insertBefore.next = node;
         return node.replace(insertBefore, message);
     }
@@ -545,7 +586,6 @@
         b.append(")");
     }
 
-    // utilities for generated code
     protected static void check(Assumption assumption) throws InvalidAssumptionException {
         if (assumption != null) {
             assumption.check();
@@ -580,4 +620,226 @@
         return true;
     }
 
+    private static final class InsertionEvent0 extends SlowPathEvent0 implements Callable<SpecializationNode> {
+
+        private final SpecializationNode next;
+
+        public InsertionEvent0(SpecializationNode source, String reason, Frame frame, SpecializationNode next) {
+            super(source, reason, frame);
+            this.next = next;
+        }
+
+        public SpecializationNode call() throws Exception {
+            SpecializationNode start = source.findStart();
+            if (start.index == Integer.MAX_VALUE) {
+                return insertAt(start, next, this);
+            } else {
+                return insertSorted(start, next, this, start.merge(next, frame));
+            }
+        }
+
+    }
+
+    private static final class InsertionEvent1 extends SlowPathEvent1 implements Callable<SpecializationNode> {
+
+        private final SpecializationNode next;
+
+        public InsertionEvent1(SpecializationNode source, String reason, Frame frame, Object o1, SpecializationNode next) {
+            super(source, reason, frame, o1);
+            this.next = next;
+        }
+
+        public SpecializationNode call() throws Exception {
+            SpecializationNode start = source.findStart();
+            if (start.index == Integer.MAX_VALUE) {
+                return insertAt(start, next, this);
+            } else {
+                return insertSorted(start, next, this, start.merge(next, frame, o1));
+            }
+        }
+
+    }
+
+    private static final class InsertionEvent2 extends SlowPathEvent2 implements Callable<SpecializationNode> {
+
+        private final SpecializationNode next;
+
+        public InsertionEvent2(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, SpecializationNode next) {
+            super(source, reason, frame, o1, o2);
+            this.next = next;
+        }
+
+        public SpecializationNode call() throws Exception {
+            SpecializationNode start = source.findStart();
+            if (start.index == Integer.MAX_VALUE) {
+                return insertAt(start, next, this);
+            } else {
+                return insertSorted(start, next, this, start.merge(next, frame, o1, o2));
+            }
+        }
+
+    }
+
+    private static final class InsertionEvent3 extends SlowPathEvent3 implements Callable<SpecializationNode> {
+
+        private final SpecializationNode next;
+
+        public InsertionEvent3(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3, SpecializationNode next) {
+            super(source, reason, frame, o1, o2, o3);
+            this.next = next;
+        }
+
+        public SpecializationNode call() throws Exception {
+            SpecializationNode start = source.findStart();
+            if (start.index == Integer.MAX_VALUE) {
+                return insertAt(start, next, this);
+            } else {
+                return insertSorted(start, next, this, start.merge(next, frame, o1, o2, o3));
+            }
+        }
+
+    }
+
+    private static final class InsertionEvent4 extends SlowPathEvent4 implements Callable<SpecializationNode> {
+
+        private final SpecializationNode next;
+
+        public InsertionEvent4(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3, Object o4, SpecializationNode next) {
+            super(source, reason, frame, o1, o2, o3, o4);
+            this.next = next;
+        }
+
+        public SpecializationNode call() throws Exception {
+            SpecializationNode start = source.findStart();
+            if (start.index == Integer.MAX_VALUE) {
+                return insertAt(start, next, this);
+            } else {
+                return insertSorted(start, next, this, start.merge(next, frame, o1, o2, o3, o4));
+            }
+        }
+
+    }
+
+    private static final class InsertionEvent5 extends SlowPathEvent5 implements Callable<SpecializationNode> {
+
+        private final SpecializationNode next;
+
+        public InsertionEvent5(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3, Object o4, Object o5, SpecializationNode next) {
+            super(source, reason, frame, o1, o2, o3, o4, o5);
+            this.next = next;
+        }
+
+        public SpecializationNode call() throws Exception {
+            SpecializationNode start = source.findStart();
+            if (start.index == Integer.MAX_VALUE) {
+                return insertAt(start, next, this);
+            } else {
+                return insertSorted(start, next, this, start.merge(next, frame, o1, o2, o3, o4, o5));
+            }
+        }
+
+    }
+
+    private static final class InsertionEventN extends SlowPathEventN implements Callable<SpecializationNode> {
+
+        private final SpecializationNode next;
+
+        public InsertionEventN(SpecializationNode source, String reason, Frame frame, Object[] args, SpecializationNode next) {
+            super(source, reason, frame, args);
+            this.next = next;
+        }
+
+        public SpecializationNode call() throws Exception {
+            SpecializationNode start = source.findStart();
+            if (start.index == Integer.MAX_VALUE) {
+                return insertAt(start, next, this);
+            } else {
+                return insertSorted(start, next, this, start.merge(next, frame, args));
+            }
+        }
+    }
+
+    private static final class RemoveEvent0 extends SlowPathEvent0 implements Callable<SpecializationNode> {
+
+        public RemoveEvent0(SpecializationNode source, String reason, Frame frame) {
+            super(source, reason, frame);
+        }
+
+        public SpecializationNode call() throws Exception {
+            return removeSameImpl(source, this);
+        }
+
+    }
+
+    private static final class RemoveEvent1 extends SlowPathEvent1 implements Callable<SpecializationNode> {
+
+        public RemoveEvent1(SpecializationNode source, String reason, Frame frame, Object o1) {
+            super(source, reason, frame, o1);
+        }
+
+        public SpecializationNode call() throws Exception {
+            return removeSameImpl(source, this);
+        }
+
+    }
+
+    private static final class RemoveEvent2 extends SlowPathEvent2 implements Callable<SpecializationNode> {
+
+        public RemoveEvent2(SpecializationNode source, String reason, Frame frame, Object o1, Object o2) {
+            super(source, reason, frame, o1, o2);
+        }
+
+        public SpecializationNode call() throws Exception {
+            return removeSameImpl(source, this);
+        }
+
+    }
+
+    private static final class RemoveEvent3 extends SlowPathEvent3 implements Callable<SpecializationNode> {
+
+        public RemoveEvent3(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3) {
+            super(source, reason, frame, o1, o2, o3);
+        }
+
+        public SpecializationNode call() throws Exception {
+            return removeSameImpl(source, this);
+        }
+
+    }
+
+    private static final class RemoveEvent4 extends SlowPathEvent4 implements Callable<SpecializationNode> {
+
+        public RemoveEvent4(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3, Object o4) {
+            super(source, reason, frame, o1, o2, o3, o4);
+        }
+
+        public SpecializationNode call() throws Exception {
+            return removeSameImpl(source, this);
+        }
+
+    }
+
+    private static final class RemoveEvent5 extends SlowPathEvent5 implements Callable<SpecializationNode> {
+
+        public RemoveEvent5(SpecializationNode source, String reason, Frame frame, Object o1, Object o2, Object o3, Object o4, Object o5) {
+            super(source, reason, frame, o1, o2, o3, o4, o5);
+        }
+
+        public SpecializationNode call() throws Exception {
+            return removeSameImpl(source, this);
+        }
+
+    }
+
+    private static final class RemoveEventN extends SlowPathEventN implements Callable<SpecializationNode> {
+
+        public RemoveEventN(SpecializationNode source, String reason, Frame frame, Object[] args) {
+            super(source, reason, frame, args);
+        }
+
+        public SpecializationNode call() throws Exception {
+            return removeSameImpl(source, this);
+        }
+    }
+
 }
--- a/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/generator/NodeGenFactory.java	Tue Mar 10 13:47:46 2015 +0100
+++ b/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/generator/NodeGenFactory.java	Tue Mar 10 19:28:26 2015 +0100
@@ -447,6 +447,7 @@
         clazz.addOptional(createSpecializationCreateMethod(specialization, constructor));
         clazz.addOptional(createMergeMethod(specialization));
         clazz.addOptional(createIsSameMethod(specialization));
+        clazz.addOptional(createIsIdenticalMethod(specialization));
 
         TypeData returnType = specialization.getReturnType().getTypeSystemType();
         int signatureSize = specialization.getSignatureSize();
@@ -493,6 +494,36 @@
         return executable;
     }
 
+    private Element createIsIdenticalMethod(SpecializationData specialization) {
+        boolean cacheBoundGuard = specialization.hasMultipleInstances();
+        if (!cacheBoundGuard) {
+            return null;
+        }
+
+        LocalContext currentLocals = LocalContext.load(this, node.getSignatureSize(), varArgsThreshold);
+        currentLocals.loadFastPathState(specialization);
+
+        CodeExecutableElement method = new CodeExecutableElement(modifiers(PUBLIC), getType(boolean.class), "isIdentical");
+        method.addParameter(new CodeVariableElement(getType(SpecializationNode.class), "other"));
+        currentLocals.addParametersTo(method, FRAME_VALUE);
+        method.getAnnotationMirrors().add(new CodeAnnotationMirror(context.getDeclaredType(Override.class)));
+        final CodeTreeBuilder builder = method.createBuilder();
+
+        SpecializationGroup group = SpecializationGroup.create(specialization);
+        SpecializationBody executionFactory = new SpecializationBody(true, false) {
+            @Override
+            public CodeTree createBody(SpecializationData s, LocalContext values) {
+                return builder.create().returnTrue().build();
+            }
+        };
+
+        builder.startIf().string("isSame(other)").end().startBlock();
+        builder.tree(createGuardAndCast(group, typeSystem.getGenericTypeData(), currentLocals, executionFactory));
+        builder.end();
+        builder.returnFalse();
+        return method;
+    }
+
     private CodeExecutableElement createIsSameMethod(SpecializationData specialization) {
         if (!specialization.isSpecialized() || !options.implicitCastOptimization().isDuplicateTail()) {
             return null;
@@ -532,18 +563,29 @@
     }
 
     private Element createMergeMethod(SpecializationData specialization) {
-        boolean cacheBoundGuard = specialization.hasMultipleInstances();
-        if (specialization.getExcludedBy().isEmpty() && !specialization.isPolymorphic() && !cacheBoundGuard) {
+        if (specialization.getExcludedBy().isEmpty() && !specialization.isPolymorphic()) {
             return null;
         }
         TypeMirror specializationNodeType = getType(SpecializationNode.class);
+        LocalContext currentLocals = LocalContext.load(this, node.getSignatureSize(), varArgsThreshold);
+
         CodeExecutableElement executable = new CodeExecutableElement(modifiers(PUBLIC), specializationNodeType, "merge");
         executable.addParameter(new CodeVariableElement(specializationNodeType, "newNode"));
+        currentLocals.addParametersTo(executable, FRAME_VALUE);
         executable.getAnnotationMirrors().add(new CodeAnnotationMirror(context.getDeclaredType(Override.class)));
         CodeTreeBuilder builder = executable.createBuilder();
 
         if (specialization.isPolymorphic()) {
-            builder.statement("return polymorphicMerge(newNode)");
+            builder.startReturn();
+            builder.startCall("polymorphicMerge");
+            builder.string("newNode");
+            builder.startCall("super", "merge");
+            builder.string("newNode");
+            currentLocals.addReferencesTo(builder, FRAME_VALUE);
+            builder.end();
+            builder.end();
+            builder.end();
+
         } else {
             boolean elseIf = false;
             for (SpecializationData containedSpecialization : specialization.getExcludedBy()) {
@@ -554,11 +596,12 @@
                 builder.statement("removeSame(\"Contained by " + containedSpecialization.createReferenceName() + "\")");
                 builder.end();
             }
-            if (cacheBoundGuard) {
-                builder.statement("return super.mergeNoSame(newNode)");
-            } else {
-                builder.statement("return super.merge(newNode)");
-            }
+            builder.startReturn();
+            builder.startCall("super", "merge");
+            builder.string("newNode");
+            currentLocals.addReferencesTo(builder, FRAME_VALUE);
+            builder.end();
+            builder.end();
         }
 
         return executable;
@@ -638,18 +681,15 @@
 
         CodeTreeBuilder builder = method.createBuilder();
         SpecializationGroup group = createSpecializationGroups();
-        CodeTree execution = createGuardAndCast(group, genericType, locals, new SpecializationExecution() {
-            public CodeTree createExecute(SpecializationData specialization, LocalContext values) {
+        CodeTree execution = createGuardAndCast(group, genericType, locals, new SpecializationBody(false, false) {
+            @Override
+            public CodeTree createBody(SpecializationData specialization, LocalContext values) {
                 CodeTypeElement generatedType = specializationClasses.get(specialization);
                 if (generatedType == null) {
                     throw new AssertionError("No generated type for " + specialization);
                 }
                 return createSlowPathExecute(specialization, values);
             }
-
-            public boolean isFastPath() {
-                return false;
-            }
         });
 
         builder.tree(execution);
@@ -1525,14 +1565,11 @@
         } else {
             final TypeData finalType = type;
             SpecializationGroup group = SpecializationGroup.create(specialization);
-            SpecializationExecution executionFactory = new SpecializationExecution() {
-                public CodeTree createExecute(SpecializationData s, LocalContext values) {
+            SpecializationBody executionFactory = new SpecializationBody(true, true) {
+                @Override
+                public CodeTree createBody(SpecializationData s, LocalContext values) {
                     return createFastPathExecute(builder, finalType, s, values);
                 }
-
-                public boolean isFastPath() {
-                    return true;
-                }
             };
             builder.tree(createGuardAndCast(group, type, currentLocals, executionFactory));
             if (hasFallthrough(group, type, originalValues, true, null) || group.getSpecialization().isFallback()) {
@@ -1621,11 +1658,11 @@
         return builder.build();
     }
 
-    private CodeTree createGuardAndCast(SpecializationGroup group, TypeData forType, LocalContext currentValues, SpecializationExecution execution) {
+    private CodeTree createGuardAndCast(SpecializationGroup group, TypeData forType, LocalContext currentValues, SpecializationBody execution) {
         CodeTreeBuilder builder = CodeTreeBuilder.createBuilder();
 
         Set<TypeGuard> castGuards;
-        if (execution.isFastPath()) {
+        if (execution.needsCastedValues()) {
             castGuards = null; // cast all
         } else {
             castGuards = new HashSet<>();
@@ -1679,7 +1716,7 @@
                 builder.tree(createGuardAndCast(child, forType, currentValues.copy(), execution));
             }
             if (specialization != null) {
-                builder.tree(execution.createExecute(specialization, currentValues));
+                builder.tree(execution.createBody(specialization, currentValues));
             }
         }
         builder.end(ifCount);
@@ -2207,7 +2244,7 @@
     }
 
     private CodeTree[] createTypeCheckAndLocals(SpecializationData specialization, List<TypeGuard> typeGuards, Set<TypeGuard> castGuards, LocalContext currentValues,
-                    SpecializationExecution specializationExecution) {
+                    SpecializationBody specializationExecution) {
         CodeTreeBuilder checksBuilder = CodeTreeBuilder.createBuilder();
         CodeTreeBuilder localsBuilder = CodeTreeBuilder.createBuilder();
         for (TypeGuard typeGuard : typeGuards) {
@@ -2635,11 +2672,25 @@
 
     }
 
-    private interface SpecializationExecution {
-
-        boolean isFastPath();
-
-        CodeTree createExecute(SpecializationData specialization, LocalContext currentValues);
+    private abstract class SpecializationBody {
+
+        private final boolean fastPath;
+        private final boolean needsCastedValues;
+
+        public SpecializationBody(boolean fastPath, boolean needsCastedValues) {
+            this.fastPath = fastPath;
+            this.needsCastedValues = needsCastedValues;
+        }
+
+        public final boolean isFastPath() {
+            return fastPath;
+        }
+
+        public final boolean needsCastedValues() {
+            return needsCastedValues;
+        }
+
+        public abstract CodeTree createBody(SpecializationData specialization, LocalContext currentValues);
 
     }