# HG changeset patch
# User Christian Humer <christian.humer@gmail.com>
# Date 1375383234 -7200
# Node ID 4f52b08bd2f9cff5a062ffc4d7fa40107f484b01
# Parent  14d5ff4683e0fdc132db36e796637c6c517e6741
Truffle-DSL: Implemented specialization grouping for generic cases.

diff -r 14d5ff4683e0 -r 4f52b08bd2f9 graal/com.oracle.truffle.api.dsl.test/src/com/oracle/truffle/api/dsl/test/SpecializationGroupingTest.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.truffle.api.dsl.test/src/com/oracle/truffle/api/dsl/test/SpecializationGroupingTest.java	Thu Aug 01 20:53:54 2013 +0200
@@ -0,0 +1,189 @@
+/*
+ * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.truffle.api.dsl.test;
+
+import org.junit.*;
+
+import com.oracle.truffle.api.*;
+import com.oracle.truffle.api.dsl.*;
+import com.oracle.truffle.api.dsl.test.SpecializationGroupingTestFactory.TestGroupingFactory;
+import com.oracle.truffle.api.dsl.test.TypeSystemTest.SimpleTypes;
+import com.oracle.truffle.api.dsl.test.TypeSystemTest.TestRootNode;
+import com.oracle.truffle.api.dsl.test.TypeSystemTest.ValueNode;
+import com.oracle.truffle.api.nodes.*;
+
+/**
+ * Tests execution counts of guards. While we do not make guarantees for guard invocation except for
+ * their execution order our implementation reduces the calls to guards as much as possible.
+ */
+public class SpecializationGroupingTest {
+
+    @Test
+    public void testGrouping() {
+        MockAssumption a1 = new MockAssumption(true);
+        MockAssumption a2 = new MockAssumption(false);
+        MockAssumption a3 = new MockAssumption(true);
+
+        TestRootNode<TestGrouping> root = TestHelper.createRoot(TestGroupingFactory.getInstance(), a1, a2, a3);
+
+        SimpleTypes.intCast = 0;
+        SimpleTypes.intCheck = 0;
+        TestGrouping.true1 = 0;
+        TestGrouping.false1 = 0;
+        TestGrouping.true2 = 0;
+        TestGrouping.false2 = 0;
+        TestGrouping.true3 = 0;
+
+        Assert.assertEquals(42, TestHelper.executeWith(root, 21, 21));
+        Assert.assertEquals(1, TestGrouping.true1);
+        Assert.assertEquals(1, TestGrouping.false1);
+        Assert.assertEquals(1, TestGrouping.true2);
+        Assert.assertEquals(1, TestGrouping.false2);
+        Assert.assertEquals(1, TestGrouping.true3);
+        Assert.assertEquals(2, SimpleTypes.intCheck);
+        Assert.assertEquals(2, SimpleTypes.intCast);
+        Assert.assertEquals(1, a1.checked);
+        Assert.assertEquals(1, a2.checked);
+        Assert.assertEquals(1, a3.checked);
+
+        Assert.assertEquals(42, TestHelper.executeWith(root, 21, 21));
+        Assert.assertEquals(2, TestGrouping.true1);
+        Assert.assertEquals(1, TestGrouping.false1);
+        Assert.assertEquals(2, TestGrouping.true2);
+        Assert.assertEquals(2, TestGrouping.false2);
+        Assert.assertEquals(2, TestGrouping.true3);
+
+        Assert.assertEquals(2, a1.checked);
+        Assert.assertEquals(1, a2.checked);
+        Assert.assertEquals(2, a3.checked);
+        Assert.assertEquals(2, SimpleTypes.intCheck);
+        Assert.assertEquals(2, SimpleTypes.intCast);
+
+    }
+
+    @SuppressWarnings("unused")
+    @NodeChildren({@NodeChild, @NodeChild})
+    @NodeAssumptions({"a1", "a2", "a3"})
+    public abstract static class TestGrouping extends ValueNode {
+
+        private static int true1;
+        private static int false1;
+        private static int true2;
+        private static int false2;
+        private static int true3;
+
+        protected boolean true1(int value) {
+            true1++;
+            return true;
+        }
+
+        protected boolean false1(int value, int value2) {
+            false1++;
+            return false;
+        }
+
+        protected boolean true2(int value) {
+            true2++;
+            return true;
+        }
+
+        protected boolean false2(int value) {
+            false2++;
+            return false;
+        }
+
+        protected boolean true3(int value) {
+            true3++;
+            return true;
+        }
+
+        @Specialization(order = 1)
+        public int fail(int value1, String value2) {
+            throw new AssertionError();
+        }
+
+        @Specialization(order = 2, guards = {"true1", "false1"})
+        public int fail1(int value1, int value2) {
+            throw new AssertionError();
+        }
+
+        @Specialization(order = 3, guards = {"true1", "true2"}, assumptions = {"a1", "a2"})
+        public int fail2(int value1, int value2) {
+            throw new AssertionError();
+        }
+
+        @Specialization(order = 4, guards = {"true1", "true2"}, assumptions = {"a1", "a3"}, rewriteOn = RuntimeException.class)
+        public int throwRewrite(int value1, int value2) {
+            throw new RuntimeException();
+        }
+
+        @Specialization(order = 5, guards = {"true1", "true2", "false2"}, assumptions = {"a1", "a3"})
+        public int fail4(int value1, int value2) {
+            throw new AssertionError();
+        }
+
+        @Specialization(order = 6, guards = {"true1", "true2", "!false2", "!true3"}, assumptions = {"a1", "a3"})
+        public int fail5(int value1, int value2) {
+            throw new AssertionError();
+        }
+
+        @Specialization(order = 7, guards = {"true1", "true2", "!false2", "true3"}, assumptions = {"a1", "a3"})
+        public int success(int value1, int value2) {
+            return value1 + value2;
+        }
+
+    }
+
+    private static class MockAssumption implements Assumption {
+
+        int checked;
+
+        private final boolean valid;
+
+        public MockAssumption(boolean valid) {
+            this.valid = valid;
+        }
+
+        public void check() throws InvalidAssumptionException {
+            checked++;
+            if (!valid) {
+                throw new InvalidAssumptionException();
+            }
+        }
+
+        public boolean isValid() {
+            checked++;
+            return valid;
+        }
+
+        public void invalidate() {
+            throw new UnsupportedOperationException();
+        }
+
+        public String getName() {
+            throw new UnsupportedOperationException();
+        }
+
+    }
+
+}
diff -r 14d5ff4683e0 -r 4f52b08bd2f9 graal/com.oracle.truffle.api.dsl.test/src/com/oracle/truffle/api/dsl/test/TypeSystemTest.java
--- a/graal/com.oracle.truffle.api.dsl.test/src/com/oracle/truffle/api/dsl/test/TypeSystemTest.java	Thu Aug 01 20:53:05 2013 +0200
+++ b/graal/com.oracle.truffle.api.dsl.test/src/com/oracle/truffle/api/dsl/test/TypeSystemTest.java	Thu Aug 01 20:53:54 2013 +0200
@@ -32,6 +32,22 @@
 
     @TypeSystem({int.class, boolean.class, String.class, Str.class, CallTarget.class, Object[].class})
     static class SimpleTypes {
+
+        static int intCheck;
+        static int intCast;
+
+        @TypeCheck
+        public boolean isInteger(Object value) {
+            intCheck++;
+            return value instanceof Integer;
+        }
+
+        @TypeCast
+        public int asInteger(Object value) {
+            intCast++;
+            return (int) value;
+        }
+
     }
 
     @TypeSystemReference(SimpleTypes.class)
@@ -126,6 +142,16 @@
             return frame.getArguments(TestArguments.class).get(index);
         }
 
+        @Override
+        public int executeInt(VirtualFrame frame) throws UnexpectedResultException {
+            // avoid casts for some tests
+            Object o = frame.getArguments(TestArguments.class).get(index);
+            if (o instanceof Integer) {
+                return (int) o;
+            }
+            throw new UnexpectedResultException(o);
+        }
+
     }
 
 }
diff -r 14d5ff4683e0 -r 4f52b08bd2f9 graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/Specialization.java
--- a/graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/Specialization.java	Thu Aug 01 20:53:05 2013 +0200
+++ b/graal/com.oracle.truffle.api.dsl/src/com/oracle/truffle/api/dsl/Specialization.java	Thu Aug 01 20:53:54 2013 +0200
@@ -38,8 +38,10 @@
 
     /**
      * Defines the assumptions to check for this specialization. When the specialization method is
-     * invoked it is guaranteed that the assigned assumptions still hold. To declare assumptions use
-     * the {@link NodeAssumptions} annotation at class level.
+     * invoked it is guaranteed that these assumptions still hold. It is not guaranteed that they
+     * are checked before the {@link #guards()} methods. They may be checked before after or in
+     * between {@link #guards()}. To declare assumptions use the {@link NodeAssumptions} annotation
+     * at class level.
      */
     String[] assumptions() default {};
 
diff -r 14d5ff4683e0 -r 4f52b08bd2f9 graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/node/NodeCodeGenerator.java
--- a/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/node/NodeCodeGenerator.java	Thu Aug 01 20:53:05 2013 +0200
+++ b/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/node/NodeCodeGenerator.java	Thu Aug 01 20:53:54 2013 +0200
@@ -440,7 +440,7 @@
                 continue;
             }
 
-            CodeTree cast = createCast(parent, field, valueParam, guardedParam);
+            CodeTree cast = createCast(parent, field, valueParam, guardedParam.getTypeSystemType());
             if (cast == null) {
                 continue;
             }
@@ -479,7 +479,7 @@
                 valueParam = guardedParam;
             }
 
-            CodeTree implicitGuard = createImplicitGuard(builder, field, valueParam, guardedParam);
+            CodeTree implicitGuard = createTypeGuard(builder, field, valueParam, guardedParam.getTypeSystemType());
             if (implicitGuard == null) {
                 continue;
             }
@@ -492,11 +492,11 @@
         return builder.isEmpty() ? null : builder.getRoot();
     }
 
-    private CodeTree createImplicitGuard(CodeTreeBuilder parent, NodeChildData field, ActualParameter source, ActualParameter target) {
+    private CodeTree createTypeGuard(CodeTreeBuilder parent, NodeChildData field, ActualParameter source, TypeData targetType) {
         NodeData node = field.getNodeData();
+
         CodeTreeBuilder builder = new CodeTreeBuilder(parent);
 
-        TypeData targetType = target.getTypeSystemType();
         TypeData sourceType = source.getTypeSystemType();
 
         if (!sourceType.needsCastTo(getContext(), targetType)) {
@@ -506,14 +506,14 @@
         builder.startGroup();
 
         if (field.isShortCircuit()) {
-            ActualParameter shortCircuit = target.getPreviousParameter();
+            ActualParameter shortCircuit = source.getPreviousParameter();
             assert shortCircuit != null;
             builder.string("(");
             builder.string("!").string(valueName(shortCircuit));
             builder.string(" || ");
         }
 
-        startCallTypeSystemMethod(getContext(), builder, node, TypeSystemCodeGenerator.isTypeMethodName(target.getTypeSystemType()));
+        startCallTypeSystemMethod(getContext(), builder, node, TypeSystemCodeGenerator.isTypeMethodName(targetType));
         builder.string(valueName(source));
         builder.end().end(); // call
 
@@ -526,10 +526,9 @@
         return builder.getRoot();
     }
 
-    private CodeTree createCast(CodeTreeBuilder parent, NodeChildData field, ActualParameter source, ActualParameter target) {
+    private CodeTree createCast(CodeTreeBuilder parent, NodeChildData field, ActualParameter source, TypeData targetType) {
         NodeData node = field.getNodeData();
         TypeData sourceType = source.getTypeSystemType();
-        TypeData targetType = target.getTypeSystemType();
 
         if (!sourceType.needsCastTo(getContext(), targetType)) {
             return null;
@@ -537,14 +536,14 @@
 
         CodeTree condition = null;
         if (field.isShortCircuit()) {
-            ActualParameter shortCircuit = target.getPreviousParameter();
+            ActualParameter shortCircuit = source.getPreviousParameter();
             assert shortCircuit != null;
             condition = CodeTreeBuilder.singleString(valueName(shortCircuit));
         }
 
-        CodeTree value = createCallTypeSystemMethod(context, parent, node, TypeSystemCodeGenerator.asTypeMethodName(targetType), CodeTreeBuilder.singleString(valueName(target)));
-
-        return createLazyAssignment(parent, castValueName(target), target.getType(), condition, value);
+        CodeTree value = createCallTypeSystemMethod(context, parent, node, TypeSystemCodeGenerator.asTypeMethodName(targetType), CodeTreeBuilder.singleString(valueName(source)));
+
+        return createLazyAssignment(parent, castValueName(source), targetType.getPrimitiveType(), condition, value);
     }
 
     /**
@@ -1416,8 +1415,7 @@
             return var;
         }
 
-        private CodeExecutableElement createGenericExecuteAndSpecialize(NodeData node) {
-
+        private CodeExecutableElement createGenericExecuteAndSpecialize(final NodeData node) {
             TypeMirror genericReturnType = node.getGenericSpecialization().getReturnType().getType();
             CodeExecutableElement method = new CodeExecutableElement(modifiers(PROTECTED), genericReturnType, EXECUTE_SPECIALIZE_NAME);
             method.addParameter(new CodeVariableElement(getContext().getType(int.class), "minimumState"));
@@ -1436,33 +1434,36 @@
             builder.end().end();
 
             List<SpecializationData> specializations = node.getSpecializations();
-
-            boolean firstUnreachable = true;
-            SpecializationData previous = null;
+            List<SpecializationData> filteredSpecializations = new ArrayList<>();
             for (SpecializationData current : specializations) {
-                if (current.isUninitialized()) {
+                if (current.isUninitialized() || !current.isReachable()) {
                     continue;
                 }
-                String prefix = null;
-
-                if (current.hasRewrite(getContext())) {
-                    prefix = "minimumState < " + node.getSpecializations().indexOf(current);
+                filteredSpecializations.add(current);
+            }
+
+            List<SpecializationGroup> groups = SpecializationGroup.create(filteredSpecializations);
+
+            for (SpecializationGroup group : groups) {
+                builder.tree(createExecuteTree(builder, node.getGenericSpecialization(), group, true, new CodeBlock<SpecializationData>() {
+
+                    public CodeTree create(CodeTreeBuilder b, SpecializationData current) {
+                        return createGenericInvokeAndSpecialize(b, node.getGenericSpecialization(), current);
+                    }
+                }));
+            }
+
+            boolean firstUnreachable = true;
+            for (SpecializationData current : specializations) {
+                if (current.isUninitialized() || current.isReachable()) {
+                    continue;
                 }
-
-                if (current.isReachable()) {
-                    CodeTree execute = createGenericInvokeAndSpecialize(builder, node.getGenericSpecialization(), current);
-
-                    builder.tree(createGuardAndCast(builder, prefix, current.getNode().getGenericSpecialization(), current, true, execute, null, true, false));
-                } else {
-                    if (firstUnreachable) {
-                        if (previous != null && !previous.isGenericSpecialization(getContext()) && !previous.hasRewrite(getContext())) {
-                            emitEncounteredSynthetic(builder, current);
-                        }
-                        firstUnreachable = false;
-                    }
-                    builder.string("// unreachable ").string(current.getId()).newLine();
+                if (firstUnreachable) {
+                    emitEncounteredSynthetic(builder, current);
+                    firstUnreachable = false;
                 }
-                previous = current;
+
+                builder.string("// unreachable ").string(current.getId()).newLine();
             }
 
             return method;
@@ -1475,18 +1476,26 @@
             method.getAnnotationMirrors().add(new CodeAnnotationMirror(getContext().getTruffleTypes().getSlowPath()));
 
             addInternalValueParameters(method, node.getGenericSpecialization(), node.needsFrame(), false);
-            CodeTreeBuilder builder = method.createBuilder();
-
-            String prefix = null;
+            final CodeTreeBuilder builder = method.createBuilder();
+
             List<SpecializationData> specializations = node.getSpecializations();
-
+            List<SpecializationData> filteredSpecializations = new ArrayList<>();
             for (SpecializationData current : specializations) {
                 if (current.isUninitialized() || !current.isReachable()) {
                     continue;
                 }
-                CodeTreeBuilder execute = new CodeTreeBuilder(builder);
-                execute.tree(createGenericInvoke(builder, node.getGenericSpecialization(), current));
-                builder.tree(createGuardAndCast(builder, prefix, current.getNode().getGenericSpecialization(), current, true, execute.getRoot(), null, true, false));
+                filteredSpecializations.add(current);
+            }
+
+            List<SpecializationGroup> groups = SpecializationGroup.create(filteredSpecializations);
+
+            for (SpecializationGroup group : groups) {
+                builder.tree(createExecuteTree(builder, node.getGenericSpecialization(), group, false, new CodeBlock<SpecializationData>() {
+
+                    public CodeTree create(CodeTreeBuilder b, SpecializationData current) {
+                        return createGenericInvoke(builder, current.getNode().getGenericSpecialization(), current);
+                    }
+                }));
             }
 
             for (SpecializationData current : specializations) {
@@ -1499,6 +1508,209 @@
             return method;
         }
 
+        private CodeTree createExecuteTree(CodeTreeBuilder outerParent, final SpecializationData source, final SpecializationGroup group, final boolean checkMinimumState,
+                        final CodeBlock<SpecializationData> guardedblock) {
+            return guard(outerParent, source, group, checkMinimumState, new CodeBlock<Void>() {
+
+                public CodeTree create(CodeTreeBuilder parent, Void value) {
+                    CodeTreeBuilder builder = parent.create();
+
+                    if (group.getSpecialization() != null) {
+                        builder.tree(guardedblock.create(builder, group.getSpecialization()));
+
+                        assert group.getChildren().isEmpty() : "missed a specialization";
+                    } else {
+                        for (SpecializationGroup childGroup : group.getChildren()) {
+                            builder.tree(createExecuteTree(builder, source, childGroup, checkMinimumState, guardedblock));
+                        }
+                    }
+
+                    return builder.getRoot();
+                }
+            });
+        }
+
+        private CodeTree guard(CodeTreeBuilder parent, SpecializationData source, SpecializationGroup group, boolean checkMinimumState, CodeBlock<Void> bodyBlock) {
+            NodeData node = source.getNode();
+
+            CodeTreeBuilder guardsBuilder = parent.create();
+            CodeTreeBuilder castBuilder = parent.create();
+            CodeTreeBuilder guardsCastBuilder = parent.create();
+
+            String guardsAnd = "";
+            String guardsCastAnd = "";
+
+            boolean minimumState = checkMinimumState;
+            if (minimumState) {
+                int groupMaxIndex = group.getMaxSpecializationIndex();
+
+                int genericIndex = node.getSpecializations().indexOf(node.getGenericSpecialization());
+                if (groupMaxIndex >= genericIndex) {
+                    // no minimum state check for an generic index
+                    minimumState = false;
+                }
+
+                if (minimumState) {
+                    // no minimum state check if alread checked by parent group
+                    int parentMaxIndex = -1;
+                    if (group.getParent() != null) {
+                        parentMaxIndex = group.getParent().getMaxSpecializationIndex();
+                    }
+                    if (groupMaxIndex == parentMaxIndex) {
+                        minimumState = false;
+                    }
+                }
+
+                if (minimumState) {
+                    guardsBuilder.string(guardsAnd);
+                    guardsBuilder.string("minimumState < " + groupMaxIndex);
+                    guardsAnd = " && ";
+                }
+            }
+
+            for (String assumption : group.getAssumptions()) {
+                guardsBuilder.string(guardsAnd);
+                guardsBuilder.string("this");
+                guardsBuilder.string(".").string(assumption).string(".isValid()");
+                guardsAnd = " && ";
+            }
+
+            int argOffset = group.getTypeGuardOffset();
+            int argIndex = argOffset;
+            for (TypeData typeData : group.getTypeGuards()) {
+
+                ActualParameter valueParam = source.getSignatureParameter(argIndex);
+
+                if (valueParam == null) {
+                    /*
+                     * If used inside a execute evaluated method then the value param may not exist.
+                     * In that case we assume that the value is executed generic or of the current
+                     * specialization.
+                     */
+                    if (group.getSpecialization() != null) {
+                        valueParam = group.getSpecialization().getSignatureParameter(argIndex);
+                    } else {
+                        valueParam = node.getGenericSpecialization().getSignatureParameter(argIndex);
+                    }
+                }
+
+                NodeChildData child = node.findChild(valueParam.getSpecification().getName());
+                if (child == null) {
+                    throw new IllegalStateException();
+                }
+
+                CodeTree implicitGuard = createTypeGuard(guardsBuilder, child, valueParam, typeData);
+                if (implicitGuard != null) {
+                    guardsBuilder.string(guardsAnd);
+                    guardsBuilder.tree(implicitGuard);
+                    guardsAnd = " && ";
+                }
+
+                CodeTree cast = createCast(castBuilder, child, valueParam, typeData);
+                if (cast != null) {
+                    castBuilder.tree(cast);
+                }
+
+                argIndex++;
+            }
+            CodeTreeBuilder builder = parent.create();
+
+            int ifCount = 0;
+            if (isElseConnectableGroup(group)) {
+                if (minimumState) {
+                    builder.startElseIf().tree(guardsBuilder.getRoot()).end().startBlock();
+                } else {
+                    builder.startElseBlock();
+                }
+                ifCount++;
+
+            } else {
+                for (GuardData guard : group.getGuards()) {
+                    if (needsTypeGuard(source, group, guard)) {
+                        guardsCastBuilder.tree(createMethodGuard(parent, guardsCastAnd, source, guard));
+                        guardsCastAnd = " && ";
+                    } else {
+                        guardsBuilder.tree(createMethodGuard(parent, guardsAnd, source, guard));
+                        guardsAnd = " && ";
+                    }
+                }
+
+                if (!guardsBuilder.isEmpty()) {
+                    builder.startIf().tree(guardsBuilder.getRoot()).end().startBlock();
+                    ifCount++;
+                }
+                builder.tree(castBuilder.getRoot());
+
+                if (!guardsCastBuilder.isEmpty()) {
+                    builder.startIf().tree(guardsCastBuilder.getRoot()).end().startBlock();
+                    ifCount++;
+                }
+            }
+
+            builder.tree(bodyBlock.create(builder, null));
+
+            builder.end(ifCount);
+            return builder.getRoot();
+        }
+
+        private boolean isElseConnectableGroup(SpecializationGroup group) {
+            if (!group.getTypeGuards().isEmpty() || !group.getAssumptions().isEmpty()) {
+                return false;
+            }
+
+            SpecializationGroup previousGroup = group.getPreviousGroup();
+            if (previousGroup != null && group.getGuards().size() == 1 && previousGroup.getGuards().size() == 1) {
+                GuardData guard = group.getGuards().get(0);
+                GuardData previousGuard = previousGroup.getGuards().get(0);
+
+                if (guard.getMethod().equals(previousGuard.getMethod())) {
+                    assert guard.isNegated() != previousGuard.isNegated();
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        private boolean needsTypeGuard(SpecializationData source, SpecializationGroup group, GuardData guard) {
+            int offset = group.getTypeGuardOffset();
+            int argIndex = 0;
+            for (ActualParameter parameter : guard.getParameters()) {
+                if (!parameter.getSpecification().isSignature()) {
+                    continue;
+                }
+                if (argIndex < offset) {
+                    // type casted in parent group
+                    continue;
+                }
+
+                int guardIndex = argIndex - offset;
+                if (guardIndex < group.getTypeGuards().size()) {
+                    TypeData requiredType = group.getTypeGuards().get(guardIndex);
+
+                    ActualParameter sourceParameter = source.findParameter(parameter.getLocalName());
+                    if (sourceParameter == null) {
+                        sourceParameter = source.getNode().getGenericSpecialization().findParameter(parameter.getLocalName());
+                    }
+
+                    if (sourceParameter.getTypeSystemType().needsCastTo(getContext(), requiredType)) {
+                        return true;
+                    }
+                }
+                argIndex++;
+            }
+            return false;
+        }
+
+        private CodeTree createMethodGuard(CodeTreeBuilder parent, String prefix, SpecializationData source, GuardData guard) {
+            CodeTreeBuilder builder = parent.create();
+            builder.string(prefix);
+            if (guard.isNegated()) {
+                builder.string("!");
+            }
+            builder.tree(createTemplateMethodCall(builder, null, source, guard, null));
+            return builder.getRoot();
+        }
+
         protected CodeTree createGenericInvoke(CodeTreeBuilder parent, SpecializationData source, SpecializationData current) {
             CodeTreeBuilder builder = new CodeTreeBuilder(parent);
 
@@ -1508,14 +1720,16 @@
                 builder.startReturn().tree(createTemplateMethodCall(builder, null, source, current, null)).end();
             }
 
-            return encloseThrowsWithFallThrough(current, builder.getRoot());
+            return encloseThrowsWithFallThrough(current, builder.getRoot(), null);
         }
 
         protected CodeTree createGenericInvokeAndSpecialize(CodeTreeBuilder parent, SpecializationData source, SpecializationData current) {
-            CodeTreeBuilder builder = new CodeTreeBuilder(parent);
+            CodeTreeBuilder builder = parent.create();
+            CodeTreeBuilder prefix = parent.create();
 
             NodeData node = current.getNode();
 
+            String restoreNode = null;
             if (current.isGeneric() && node.isPolymorphic()) {
                 builder.startIf().string("next0 == null && minimumState > 0").end().startBlock();
                 builder.tree(createRewritePolymorphic(builder, node));
@@ -1525,10 +1739,18 @@
                 builder.end();
             } else {
                 // simple rewrite
-                builder.tree(createReturnRewriteAndInvoke(builder, null, null, source, current));
+                if (current.getExceptions().isEmpty()) {
+                    builder.tree(createGenericInvoke(builder, source, current, createReplaceCall(builder, current, null, null)));
+                } else {
+                    prefix.declaration(baseClassName(node), "restoreNode", createReplaceCall(builder, current, null, null));
+                    builder.tree(createGenericInvoke(builder, source, current, CodeTreeBuilder.singleString("restoreNode")));
+                    restoreNode = "restoreNode";
+                }
             }
-
-            return encloseThrowsWithFallThrough(current, builder.getRoot());
+            CodeTreeBuilder root = parent.create();
+            root.tree(prefix.getRoot());
+            root.tree(encloseThrowsWithFallThrough(current, builder.getRoot(), restoreNode));
+            return root.getRoot();
         }
 
         private CodeTree createRewriteGeneric(CodeTreeBuilder parent, SpecializationData source, SpecializationData current) {
@@ -1540,7 +1762,7 @@
             builder.tree(createFindRoot(builder, node, false));
             builder.end();
             builder.end();
-            builder.tree(createReturnRewriteAndInvoke(builder, "root", null, source, current));
+            builder.tree(createGenericInvoke(builder, source, current, createReplaceCall(builder, current, "root", null)));
             return builder.getRoot();
         }
 
@@ -1559,7 +1781,7 @@
             return builder.getRoot();
         }
 
-        private CodeTree encloseThrowsWithFallThrough(SpecializationData current, CodeTree tree) {
+        private CodeTree encloseThrowsWithFallThrough(SpecializationData current, CodeTree tree, String restoreNodeVarName) {
             if (current.getExceptions().isEmpty()) {
                 return tree;
             }
@@ -1569,6 +1791,16 @@
             builder.tree(tree);
             for (SpecializationThrowsData exception : current.getExceptions()) {
                 builder.end().startCatchBlock(exception.getJavaClass(), "rewriteEx");
+                if (restoreNodeVarName != null) {
+                    builder.startStatement().startCall(restoreNodeVarName, "replace").string("this");
+                    builder.startGroup();
+                    builder.startCall("createInfo0").doubleQuote("Rewrite exception thrown " + Utils.getSimpleName(exception.getJavaClass()) + ".");
+                    addInternalValueParameterNames(builder, current, current, null, false, true);
+                    builder.end();
+                    builder.end();
+                    builder.end().end();
+                }
+
                 builder.string("// fall through").newLine();
             }
             builder.end();
@@ -1576,9 +1808,28 @@
             return builder.getRoot();
         }
 
-        protected CodeTree createReturnRewriteAndInvoke(CodeTreeBuilder parent, String target, String message, SpecializationData source, SpecializationData current) {
+        protected CodeTree createGenericInvoke(CodeTreeBuilder parent, SpecializationData source, SpecializationData current, CodeTree replaceCall) {
+            CodeTreeBuilder builder = parent.create();
+            if (current.isGeneric()) {
+                builder.startReturn().tree(replaceCall).string(".").startCall(EXECUTE_GENERIC_NAME);
+                addInternalValueParameterNames(builder, source, current, null, current.getNode().needsFrame(), true);
+                builder.end().end();
+
+            } else if (current.getMethod() == null) {
+                builder.statement(replaceCall);
+                emitEncounteredSynthetic(builder, current);
+            } else if (!current.canBeAccessedByInstanceOf(getContext(), source.getNode().getNodeType())) {
+                builder.statement(replaceCall);
+                builder.startReturn().tree(createTemplateMethodCall(parent, null, source, current, null)).end();
+            } else {
+                replaceCall.add(new CodeTree(CodeTreeKind.STRING, null, "."));
+                builder.startReturn().tree(createTemplateMethodCall(parent, replaceCall, source, current, null)).end();
+            }
+            return builder.getRoot();
+        }
+
+        protected CodeTree createReplaceCall(CodeTreeBuilder builder, SpecializationData current, String target, String message) {
             String className = nodeSpecializationClassName(current);
-            CodeTreeBuilder builder = parent.create();
             CodeTreeBuilder replaceCall = builder.create();
             if (target != null) {
                 replaceCall.startCall(target, "replace");
@@ -1592,24 +1843,7 @@
                 replaceCall.doubleQuote(message);
             }
             replaceCall.end();
-
-            if (current.isGeneric()) {
-                replaceCall.string(".");
-                builder.startReturn().tree(replaceCall.getRoot()).startCall(EXECUTE_GENERIC_NAME);
-                addInternalValueParameterNames(builder, source, current, null, current.getNode().needsFrame(), true);
-                builder.end().end();
-
-            } else if (current.getMethod() == null) {
-                builder.statement(replaceCall.getRoot());
-                emitEncounteredSynthetic(builder, current);
-            } else if (!current.canBeAccessedByInstanceOf(getContext(), source.getNode().getNodeType())) {
-                builder.statement(replaceCall.getRoot());
-                builder.startReturn().tree(createTemplateMethodCall(builder, null, source, current, null)).end();
-            } else {
-                replaceCall.string(".");
-                builder.startReturn().tree(createTemplateMethodCall(builder, replaceCall.getRoot(), source, current, null)).end();
-            }
-            return builder.getRoot();
+            return replaceCall.getRoot();
         }
 
         private CodeTree createRewritePolymorphic(CodeTreeBuilder parent, NodeData node) {
@@ -2261,7 +2495,8 @@
             builder.startIf().string("depth > ").string(String.valueOf(node.getPolymorphicDepth())).end();
             builder.startBlock();
             String message = ("Polymorphic limit reached (" + node.getPolymorphicDepth() + ")");
-            builder.tree(createReturnRewriteAndInvoke(builder, "root", message, node.getGenericPolymorphicSpecialization(), node.getGenericSpecialization()));
+            builder.tree(createGenericInvoke(builder, node.getGenericPolymorphicSpecialization(), node.getGenericSpecialization(),
+                            createReplaceCall(builder, node.getGenericSpecialization(), "root", message)));
             builder.end();
 
             builder.startElseBlock();
@@ -2489,4 +2724,9 @@
 
     }
 
+    private interface CodeBlock<T> {
+
+        CodeTree create(CodeTreeBuilder parent, T value);
+
+    }
 }
diff -r 14d5ff4683e0 -r 4f52b08bd2f9 graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/node/SpecializationGroup.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/node/SpecializationGroup.java	Thu Aug 01 20:53:54 2013 +0200
@@ -0,0 +1,241 @@
+/*
+ * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.truffle.dsl.processor.node;
+
+import java.util.*;
+
+import com.oracle.truffle.dsl.processor.template.TemplateMethod.Signature;
+import com.oracle.truffle.dsl.processor.typesystem.*;
+
+/**
+ * Class creates groups of specializations to optimize the layout of generated executeAndSpecialize
+ * and generic execute methods.
+ */
+public final class SpecializationGroup {
+
+    private final List<String> assumptions;
+    private final List<TypeData> typeGuards;
+    private final List<GuardData> guards;
+
+    private final SpecializationData specialization;
+    private final List<SpecializationGroup> children = new ArrayList<>();
+
+    private SpecializationGroup parent;
+
+    private SpecializationGroup(SpecializationData data) {
+        this.assumptions = new ArrayList<>();
+        this.typeGuards = new ArrayList<>();
+        this.guards = new ArrayList<>();
+        this.specialization = data;
+
+        this.assumptions.addAll(data.getAssumptions());
+        Signature sig = data.getSignature();
+        for (int i = 1; i < sig.size(); i++) {
+            typeGuards.add(sig.get(i));
+        }
+        this.guards.addAll(data.getGuards());
+    }
+
+    public SpecializationGroup(List<SpecializationGroup> children, List<String> assumptionMatches, List<TypeData> typeGuardsMatches, List<GuardData> guardMatches) {
+        this.assumptions = assumptionMatches;
+        this.typeGuards = typeGuardsMatches;
+        this.guards = guardMatches;
+        this.specialization = null;
+        updateChildren(children);
+    }
+
+    private void updateChildren(List<SpecializationGroup> childs) {
+        if (!children.isEmpty()) {
+            children.clear();
+        }
+        this.children.addAll(childs);
+        for (SpecializationGroup child : childs) {
+            child.parent = this;
+        }
+    }
+
+    public int getTypeGuardOffset() {
+        return (parent != null ? parent.getTypeGuardOffsetRec() : 0);
+    }
+
+    private int getTypeGuardOffsetRec() {
+        return typeGuards.size() + (parent != null ? parent.getTypeGuardOffsetRec() : 0);
+    }
+
+    public SpecializationGroup getParent() {
+        return parent;
+    }
+
+    public List<String> getAssumptions() {
+        return assumptions;
+    }
+
+    public List<TypeData> getTypeGuards() {
+        return typeGuards;
+    }
+
+    public List<GuardData> getGuards() {
+        return guards;
+    }
+
+    public List<SpecializationGroup> getChildren() {
+        return children;
+    }
+
+    public SpecializationData getSpecialization() {
+        return specialization;
+    }
+
+    private static SpecializationGroup combine(List<SpecializationGroup> groups) {
+        if (groups.isEmpty()) {
+            throw new IllegalArgumentException("empty combinations");
+        }
+        if (groups.size() == 1) {
+            return null;
+        }
+
+        List<String> assumptionMatches = new ArrayList<>();
+        List<TypeData> typeGuardsMatches = new ArrayList<>();
+        List<GuardData> guardMatches = new ArrayList<>();
+
+        SpecializationGroup first = groups.get(0);
+        List<SpecializationGroup> others = groups.subList(1, groups.size());
+
+        outer: for (String assumption : first.assumptions) {
+            for (SpecializationGroup other : others) {
+                if (!other.assumptions.contains(assumption)) {
+                    // assumptions can be combined unordered
+                    continue outer;
+                }
+            }
+            assumptionMatches.add(assumption);
+        }
+
+        int typeGuardIndex = 0;
+        outer: for (TypeData typeGuard : first.typeGuards) {
+            for (SpecializationGroup other : others) {
+                if (typeGuardIndex >= other.typeGuards.size()) {
+                    break outer;
+                }
+
+                if (!other.typeGuards.get(typeGuardIndex).equals(typeGuard)) {
+                    break outer;
+                }
+            }
+            typeGuardsMatches.add(typeGuard);
+            typeGuardIndex++;
+        }
+
+        outer: for (GuardData guard : first.guards) {
+            for (SpecializationGroup other : others) {
+                if (!other.guards.contains(guard)) {
+                    // we must break here. One guard may depend on the other.
+                    break outer;
+                }
+            }
+            guardMatches.add(guard);
+        }
+
+        if (assumptionMatches.isEmpty() && typeGuardsMatches.isEmpty() && guardMatches.isEmpty()) {
+            return null;
+        }
+
+        for (SpecializationGroup group : groups) {
+            group.assumptions.removeAll(assumptionMatches);
+            group.typeGuards.subList(0, typeGuardIndex).clear();
+            group.guards.removeAll(guardMatches);
+        }
+
+        List<SpecializationGroup> newChildren = new ArrayList<>(groups);
+        return new SpecializationGroup(newChildren, assumptionMatches, typeGuardsMatches, guardMatches);
+    }
+
+    public static List<SpecializationGroup> create(List<SpecializationData> specializations) {
+        List<SpecializationGroup> groups = new ArrayList<>();
+        for (SpecializationData specialization : specializations) {
+            groups.add(new SpecializationGroup(specialization));
+        }
+        return createCombinationalGroups(groups);
+    }
+
+    @Override
+    public String toString() {
+        return "SpecializationGroup [assumptions=" + assumptions + ", typeGuards=" + typeGuards + ", guards=" + guards + "]";
+    }
+
+    private static List<SpecializationGroup> createCombinationalGroups(List<SpecializationGroup> groups) {
+        if (groups.size() <= 1) {
+            return groups;
+        }
+        List<SpecializationGroup> newGroups = new ArrayList<>();
+
+        int i = 0;
+        for (i = 0; i < groups.size();) {
+            SpecializationGroup combined = null;
+            for (int j = groups.size(); j > i + 1; j--) {
+                combined = combine(groups.subList(i, j));
+                if (combined != null) {
+                    break;
+                }
+            }
+            SpecializationGroup newGroup;
+            if (combined == null) {
+                newGroup = groups.get(i);
+                i++;
+            } else {
+                newGroup = combined;
+                List<SpecializationGroup> originalGroups = new ArrayList<>(combined.children);
+                combined.updateChildren(createCombinationalGroups(originalGroups));
+                i += originalGroups.size();
+            }
+
+            newGroups.add(newGroup);
+
+        }
+
+        return newGroups;
+    }
+
+    public SpecializationGroup getPreviousGroup() {
+        if (parent == null || parent.children.isEmpty()) {
+            return null;
+        }
+        int index = parent.children.indexOf(this);
+        if (index <= 0) {
+            return null;
+        }
+        return parent.children.get(index - 1);
+    }
+
+    public int getMaxSpecializationIndex() {
+        if (specialization != null) {
+            return specialization.getNode().getSpecializations().indexOf(specialization);
+        } else {
+            int max = Integer.MIN_VALUE;
+            for (SpecializationGroup childGroup : getChildren()) {
+                max = Math.max(max, childGroup.getMaxSpecializationIndex());
+            }
+            return max;
+        }
+    }
+}
diff -r 14d5ff4683e0 -r 4f52b08bd2f9 graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/typesystem/GuardData.java
--- a/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/typesystem/GuardData.java	Thu Aug 01 20:53:05 2013 +0200
+++ b/graal/com.oracle.truffle.dsl.processor/src/com/oracle/truffle/dsl/processor/typesystem/GuardData.java	Thu Aug 01 20:53:54 2013 +0200
@@ -40,6 +40,20 @@
         return negated;
     }
 
+    @Override
+    public boolean equals(Object obj) {
+        if (obj instanceof GuardData) {
+            GuardData other = (GuardData) obj;
+            return getMethod().equals(other.getMethod()) && negated == other.negated;
+        }
+        return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return getMethod().hashCode();
+    }
+
     public SpecializationData getSpecialization() {
         return specialization;
     }