Mercurial > hg > truffle

changeset 20956:2170de9acab0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
SL: use DSL for call dispatches.
author Christian Humer <christian.humer@gmail.com>
date Tue, 14 Apr 2015 15:16:14 +0200
parents f7bc60c3a8f6
children 71509cb61f17
files graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/SLMain.java graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLAbstractDispatchNode.java graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLDirectDispatchNode.java graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLDispatchNode.java graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLGenericDispatchNode.java graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLInvokeNode.java graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLUninitializedDispatchNode.java
diffstat 7 files changed, 106 insertions(+), 310 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/SLMain.java	Tue Apr 14 15:16:14 2015 +0200
+++ b/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/SLMain.java	Tue Apr 14 15:16:14 2015 +0200
@@ -86,7 +86,7 @@
  * {@link SLWhileNode while} with {@link SLBreakNode break} and {@link SLContinueNode continue},
  * {@link SLReturnNode return}.
  * <li>Function calls: {@link SLInvokeNode invocations} are efficiently implemented with
- * {@link SLAbstractDispatchNode polymorphic inline caches}.
+ * {@link SLDispatchNode polymorphic inline caches}.
  * </ul>
  *
  * <p>
--- a/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLAbstractDispatchNode.java	Tue Apr 14 15:16:14 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,53 +0,0 @@
-/*
- * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package com.oracle.truffle.sl.nodes.call;
-
-import com.oracle.truffle.api.frame.*;
-import com.oracle.truffle.api.nodes.*;
-import com.oracle.truffle.sl.runtime.*;
-
-/**
- * Before a call is executed the first time, the dispatch node is a
- * {@link SLUninitializedDispatchNode}. During execution, the call is optimized using a polymorphic
- * inline cache, i.e., a chain of {@link SLDirectDispatchNode}s. The chain is terminated by a
- * {@link SLUninitializedDispatchNode}. If the chain gets too long (longer than
- * {@link #INLINE_CACHE_SIZE}), i.e., if the call is too polymorphic, the whole chain is replaced by
- * a single {@link SLGenericDispatchNode}. All this rewriting happens on runtime, based on profiling
- * feedback of the actual execution.
- * <p>
- * Example of the chain of nodes ({@code I}: {@link SLInvokeNode}; {@code U}:
- * {@link SLUninitializedDispatchNode}; {@code D}: {@link SLDirectDispatchNode}; {@code G}:
- * {@link SLGenericDispatchNode}):
- * <ol>
- * <li>After parsing: {@code I->U}
- * <li>After execution of function {@code f1}: {@code I->D(f1)->U}
- * <li>After execution of function {@code f2}: {@code I->D(f1)->D(f2)->U}
- * <li>After execution of function {@code f3}: {@code I->G}
- * </ol>
- */
-public abstract class SLAbstractDispatchNode extends Node {
-
-    protected static final int INLINE_CACHE_SIZE = 2;
-
-    protected abstract Object executeDispatch(VirtualFrame frame, SLFunction function, Object[] arguments);
-}
--- a/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLDirectDispatchNode.java	Tue Apr 14 15:16:14 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,112 +0,0 @@
-/*
- * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package com.oracle.truffle.sl.nodes.call;
-
-import com.oracle.truffle.api.*;
-import com.oracle.truffle.api.frame.*;
-import com.oracle.truffle.api.nodes.*;
-import com.oracle.truffle.sl.runtime.*;
-
-/**
- * An entry in the polymorphic inline cache.
- */
-final class SLDirectDispatchNode extends SLAbstractDispatchNode {
-
-    /** The cached function. */
-    private final SLFunction cachedFunction;
-
-    /**
-     * {@link DirectCallNode} is part of the Truffle API and handles all the steps necessary for
-     * method inlining: if the call is executed frequently and the callee is small, then the call is
-     * inlined, i.e., the call node is replaced with a copy of the callee's AST.
-     */
-    @Child private DirectCallNode callCachedTargetNode;
-
-    /** Assumption that the {@link #callCachedTargetNode} is still valid. */
-    private final Assumption cachedTargetStable;
-
-    /**
-     * The next entry of the polymorphic inline cache, either another {@link SLDirectDispatchNode}
-     * or a {@link SLUninitializedDispatchNode}.
-     */
-    @Child private SLAbstractDispatchNode nextNode;
-
-    protected SLDirectDispatchNode(SLAbstractDispatchNode next, SLFunction cachedFunction) {
-        this.cachedFunction = cachedFunction;
-        this.callCachedTargetNode = Truffle.getRuntime().createDirectCallNode(cachedFunction.getCallTarget());
-        this.cachedTargetStable = cachedFunction.getCallTargetStable();
-        this.nextNode = next;
-    }
-
-    /**
-     * Perform the inline cache check. If it succeeds, execute the cached
-     * {@link #cachedTargetStable call target}; if it fails, defer to the next element in the chain.
-     * <p>
-     * Since SL is a quite simple language, the benefit of the inline cache is quite small: after
-     * checking that the actual function to be executed is the same as the
-     * {@link SLDirectDispatchNode#cachedFunction}, we can safely execute the cached call target.
-     * You can reasonably argue that caching the call target is overkill, since we could just
-     * retrieve it via {@code function.getCallTarget()}. However, in a more complex language the
-     * lookup of the call target is usually much more complicated than in SL. In addition, caching
-     * the call target allows method inlining.
-     */
-    @Override
-    protected Object executeDispatch(VirtualFrame frame, SLFunction function, Object[] arguments) {
-        /*
-         * The inline cache check. Note that cachedFunction must be a final field so that the
-         * compiler can optimize the check.
-         */
-        if (this.cachedFunction == function) {
-            /* Inline cache hit, we are safe to execute the cached call target. */
-            try {
-                /*
-                 * Support for function redefinition: When a function is redefined, the call target
-                 * maintained by the SLFunction object is change. To avoid a check for that, we use
-                 * an Assumption that is invalidated by the SLFunction when the change is performed.
-                 * Since checking an assumption is a no-op in compiled code, the line below does not
-                 * add any overhead during optimized execution.
-                 */
-                cachedTargetStable.check();
-
-                /*
-                 * Now we are really ready to perform the call. We use a Truffle CallNode for that,
-                 * because it does all the work for method inlining.
-                 */
-                return callCachedTargetNode.call(frame, arguments);
-
-            } catch (InvalidAssumptionException ex) {
-                /*
-                 * The function has been redefined. Remove ourself from the polymorphic inline
-                 * cache, so that we fail the check only once. Note that this replacement has subtle
-                 * semantics: we are changing a node in the tree that is currently executed. This is
-                 * only safe because we know that after the call to replace(), there is no more code
-                 * that requires that this node is part of the tree.
-                 */
-                replace(nextNode);
-                /* Execute the next node in the chain by falling out of the if block. */
-            }
-        }
-        /* Inline cache miss, defer to the next element in the chain. */
-        return nextNode.executeDispatch(frame, function, arguments);
-    }
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLDispatchNode.java	Tue Apr 14 15:16:14 2015 +0200
@@ -0,0 +1,97 @@
+/*
+ * Copyright (c) 2013, 2015, 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.sl.nodes.call;
+
+import com.oracle.truffle.api.*;
+import com.oracle.truffle.api.dsl.*;
+import com.oracle.truffle.api.frame.*;
+import com.oracle.truffle.api.nodes.*;
+import com.oracle.truffle.sl.runtime.*;
+
+public abstract class SLDispatchNode extends Node {
+
+    protected static final int INLINE_CACHE_SIZE = 2;
+
+    public abstract Object executeDispatch(VirtualFrame frame, SLFunction function, Object[] arguments);
+
+    /**
+     * Inline cached specialization of the dispatch.
+     *
+     * <p>
+     * Since SL is a quite simple language, the benefit of the inline cache is quite small: after
+     * checking that the actual function to be executed is the same as the cachedFuntion, we can
+     * safely execute the cached call target. You can reasonably argue that caching the call target
+     * is overkill, since we could just retrieve it via {@code function.getCallTarget()}. However,
+     * in a more complex language the lookup of the call target is usually much more complicated
+     * than in SL. In addition, caching the call target allows method inlining.
+     * </p>
+     *
+     * <p>
+     * {@code limit = "INLINE_CACHE_SIZE"} Specifies the limit number of inline cache specialization
+     * instantiations.
+     * </p>
+     * <p>
+     * {@code guards = "function == cachedFunction"} The inline cache check. Note that
+     * cachedFunction is a final field so that the compiler can optimize the check.
+     * </p>
+     * <p>
+     * {@code assumptions = "cachedFunction.getCallTargetStable()"} Support for function
+     * redefinition: When a function is redefined, the call target maintained by the SLFunction
+     * object is change. To avoid a check for that, we use an Assumption that is invalidated by the
+     * SLFunction when the change is performed. Since checking an assumption is a no-op in compiled
+     * code, the assumption check performed by the DSL does not add any overhead during optimized
+     * execution.
+     * </p>
+     *
+     * @see Cached
+     * @see Specialization
+     *
+     * @param function the dynamically provided function
+     * @param cachedFunction the cached function of the specialization instance
+     * @param callNode the {@link DirectCallNode} specifically created for the {@link CallTarget} in
+     *            cachedFunction.
+     */
+    @Specialization(limit = "INLINE_CACHE_SIZE", guards = "function == cachedFunction", assumptions = "cachedFunction.getCallTargetStable()")
+    protected static Object doDirect(VirtualFrame frame, SLFunction function, Object[] arguments, //
+                    @Cached("function") SLFunction cachedFunction, //
+                    @Cached("create(cachedFunction.getCallTarget())") DirectCallNode callNode) {
+        /* Inline cache hit, we are safe to execute the cached call target. */
+        return callNode.call(frame, arguments);
+    }
+
+    /**
+     * Slow-path code for a call, used when the polymorphic inline cache exceeded its maximum size
+     * specified in <code>INLINE_CACHE_SIZE</code>. Such calls are not optimized any further, e.g.,
+     * no method inlining is performed.
+     */
+    @Specialization(contains = "doDirect")
+    protected static Object doIndirect(VirtualFrame frame, SLFunction function, Object[] arguments, //
+                    @Cached("create()") IndirectCallNode callNode) {
+        /*
+         * SL has a quite simple call lookup: just ask the function for the current call target, and
+         * call it.
+         */
+        return callNode.call(frame, function.getCallTarget(), arguments);
+    }
+
+}
--- a/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLGenericDispatchNode.java	Tue Apr 14 15:16:14 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,52 +0,0 @@
-/*
- * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package com.oracle.truffle.sl.nodes.call;
-
-import com.oracle.truffle.api.*;
-import com.oracle.truffle.api.frame.*;
-import com.oracle.truffle.api.nodes.*;
-import com.oracle.truffle.sl.runtime.*;
-
-/**
- * Slow-path code for a call, used when the polymorphic inline cache exceeded its maximum size. Such
- * calls are not optimized any further, e.g., no method inlining is performed.
- */
-final class SLGenericDispatchNode extends SLAbstractDispatchNode {
-
-    /**
-     * {@link IndirectCallNode} is part of the Truffle API and handles all the steps necessary for
-     * calling a megamorphic call-site. The Graal specific version of this node performs additional
-     * optimizations for the fast access of the SimpleLanguage stack trace.
-     */
-    @Child private IndirectCallNode callNode = Truffle.getRuntime().createIndirectCallNode();
-
-    @Override
-    protected Object executeDispatch(VirtualFrame frame, SLFunction function, Object[] arguments) {
-        /*
-         * SL has a quite simple call lookup: just ask the function for the current call target, and
-         * call it.
-         */
-        return callNode.call(frame, function.getCallTarget(), arguments);
-    }
-
-}
--- a/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLInvokeNode.java	Tue Apr 14 15:16:14 2015 +0200
+++ b/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLInvokeNode.java	Tue Apr 14 15:16:14 2015 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2013, 2015, 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
@@ -35,24 +35,24 @@
  * {@link SLFunction target function} can be computed by an {@link #functionNode arbitrary
  * expression}. This node is responsible for evaluating this expression, as well as evaluating the
  * {@link #argumentNodes arguments}. The actual dispatch is then delegated to a chain of
- * {@link SLAbstractDispatchNode}s that form a polymorphic inline cache.
+ * {@link SLDispatchNode} that form a polymorphic inline cache.
  */
 @NodeInfo(shortName = "invoke")
 public final class SLInvokeNode extends SLExpressionNode {
 
     public static SLInvokeNode create(SourceSection src, SLExpressionNode function, SLExpressionNode[] arguments) {
-        return new SLInvokeNode(src, function, arguments, new SLUninitializedDispatchNode());
+        return new SLInvokeNode(src, function, arguments);
     }
 
-    @Child protected SLExpressionNode functionNode;
-    @Children protected final SLExpressionNode[] argumentNodes;
-    @Child protected SLAbstractDispatchNode dispatchNode;
+    @Child private SLExpressionNode functionNode;
+    @Children private final SLExpressionNode[] argumentNodes;
+    @Child private SLDispatchNode dispatchNode;
 
-    private SLInvokeNode(SourceSection src, SLExpressionNode functionNode, SLExpressionNode[] argumentNodes, SLAbstractDispatchNode dispatchNode) {
+    private SLInvokeNode(SourceSection src, SLExpressionNode functionNode, SLExpressionNode[] argumentNodes) {
         super(src);
         this.functionNode = functionNode;
         this.argumentNodes = argumentNodes;
-        this.dispatchNode = dispatchNode;
+        this.dispatchNode = SLDispatchNodeGen.create();
     }
 
     @Override
--- a/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLUninitializedDispatchNode.java	Tue Apr 14 15:16:14 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,84 +0,0 @@
-/*
- * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package com.oracle.truffle.sl.nodes.call;
-
-import com.oracle.truffle.api.*;
-import com.oracle.truffle.api.frame.*;
-import com.oracle.truffle.api.nodes.*;
-import com.oracle.truffle.sl.*;
-import com.oracle.truffle.sl.runtime.*;
-
-/**
- * The last entry of a polymorphic inline cache.
- */
-final class SLUninitializedDispatchNode extends SLAbstractDispatchNode {
-
-    /**
-     * When we reach this method, all the previous cache entries did not match the function. If the
-     * cache is still small enough, we extend it by adding another {@link SLDirectDispatchNode}. If
-     * the cache reached its maximum size, we replace the whole dispatch chain with a
-     * {@link SLGenericDispatchNode}.
-     */
-    @Override
-    protected Object executeDispatch(VirtualFrame frame, SLFunction function, Object[] arguments) {
-        /* The following code modifies the AST, so compiled code must be invalidated. */
-        CompilerDirectives.transferToInterpreterAndInvalidate();
-
-        /*
-         * Count the number of SLDirectDispatchNodes we already have in the cache. We walk the chain
-         * of parent nodes until we hit the SLCallNode. We know that a SLCallNode is always present.
-         */
-        Node cur = this;
-        int depth = 0;
-        while (cur.getParent() instanceof SLAbstractDispatchNode) {
-            cur = cur.getParent();
-            depth++;
-        }
-        SLInvokeNode invokeNode = (SLInvokeNode) cur.getParent();
-
-        SLAbstractDispatchNode replacement;
-        if (function.getCallTarget() == null) {
-            /* Corner case: the function is not defined, so report an error to the user. */
-            throw new SLException("Call of undefined function: " + function.getName());
-
-        } else if (depth < INLINE_CACHE_SIZE) {
-            /* Extend the inline cache. Allocate the new cache entry, and the new end of the cache. */
-            SLAbstractDispatchNode next = new SLUninitializedDispatchNode();
-            replacement = new SLDirectDispatchNode(next, function);
-            /* Replace ourself with the new cache entry. */
-            replace(replacement);
-
-        } else {
-            /* Cache size exceeded, fall back to a single generic dispatch node. */
-            replacement = new SLGenericDispatchNode();
-            /* Replace the whole chain, not just ourself, with the new generic node. */
-            invokeNode.dispatchNode.replace(replacement);
-        }
-
-        /*
-         * Execute the newly created node perform the actual dispatch. That saves us from
-         * duplicating the actual call logic here.
-         */
-        return replacement.executeDispatch(frame, function, arguments);
-    }
-}