# HG changeset patch # User Christian Humer # Date 1429017374 -7200 # Node ID 2170de9acab09ca4c8e5256ea239f95e0d5b2e4f # Parent f7bc60c3a8f6da653d0545fdffab8431fbd8632c SL: use DSL for call dispatches. diff -r f7bc60c3a8f6 -r 2170de9acab0 graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/SLMain.java --- 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}. *
  • Function calls: {@link SLInvokeNode invocations} are efficiently implemented with - * {@link SLAbstractDispatchNode polymorphic inline caches}. + * {@link SLDispatchNode polymorphic inline caches}. * * *

    diff -r f7bc60c3a8f6 -r 2170de9acab0 graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLAbstractDispatchNode.java --- 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. - *

    - * Example of the chain of nodes ({@code I}: {@link SLInvokeNode}; {@code U}: - * {@link SLUninitializedDispatchNode}; {@code D}: {@link SLDirectDispatchNode}; {@code G}: - * {@link SLGenericDispatchNode}): - *

      - *
    1. After parsing: {@code I->U} - *
    2. After execution of function {@code f1}: {@code I->D(f1)->U} - *
    3. After execution of function {@code f2}: {@code I->D(f1)->D(f2)->U} - *
    4. After execution of function {@code f3}: {@code I->G} - *
    - */ -public abstract class SLAbstractDispatchNode extends Node { - - protected static final int INLINE_CACHE_SIZE = 2; - - protected abstract Object executeDispatch(VirtualFrame frame, SLFunction function, Object[] arguments); -} diff -r f7bc60c3a8f6 -r 2170de9acab0 graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLDirectDispatchNode.java --- 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. - *

    - * 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); - } -} diff -r f7bc60c3a8f6 -r 2170de9acab0 graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLDispatchNode.java --- /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. + * + *

    + * 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. + *

    + * + *

    + * {@code limit = "INLINE_CACHE_SIZE"} Specifies the limit number of inline cache specialization + * instantiations. + *

    + *

    + * {@code guards = "function == cachedFunction"} The inline cache check. Note that + * cachedFunction is a final field so that the compiler can optimize the check. + *

    + *

    + * {@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. + *

    + * + * @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 INLINE_CACHE_SIZE. 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); + } + +} diff -r f7bc60c3a8f6 -r 2170de9acab0 graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLGenericDispatchNode.java --- 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); - } - -} diff -r f7bc60c3a8f6 -r 2170de9acab0 graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLInvokeNode.java --- 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 diff -r f7bc60c3a8f6 -r 2170de9acab0 graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLUninitializedDispatchNode.java --- 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); - } -}