Mercurial > hg > truffle
changeset 17256:88d5fd9e1a6c
Truffle: implemented context sensitive inlining; implemented basic partial evaluation caching for call targets (disabled by default).
line wrap: on
line diff
--- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/PartialEvaluationTest.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/PartialEvaluationTest.java Mon Sep 29 18:46:38 2014 +0200 @@ -97,7 +97,7 @@ try (Scope s = Debug.scope("TruffleCompilation", new TruffleDebugJavaMethod(compilable))) { - StructuredGraph resultGraph = truffleCompiler.getPartialEvaluator().createGraph(compilable, assumptions); + StructuredGraph resultGraph = truffleCompiler.getPartialEvaluator().createGraph(compilable, assumptions, null); CanonicalizerPhase canonicalizer = new CanonicalizerPhase(canonicalizeReads); PhaseContext context = new PhaseContext(getProviders(), assumptions);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/ContextSensitiveInlining.java Mon Sep 29 18:46:38 2014 +0200 @@ -0,0 +1,200 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.truffle; + +import java.util.*; +import java.util.stream.*; + +import com.oracle.graal.truffle.ContextSensitiveInlining.InliningDecision; + +public class ContextSensitiveInlining implements Iterable<InliningDecision> { + + private final List<InliningDecision> callSites; + + private ContextSensitiveInlining(List<InliningDecision> callSites) { + this.callSites = callSites; + } + + public ContextSensitiveInlining(OptimizedCallTarget sourceTarget, TruffleInliningPolicy policy) { + this(decideInlining(OptimizedCallUtils.countNonTrivialNodes(sourceTarget, false), exploreCallSites(new ArrayList<>(Arrays.asList(sourceTarget)), policy), policy)); + } + + private static List<InliningDecision> exploreCallSites(List<OptimizedCallTarget> stack, TruffleInliningPolicy policy) { + List<InliningDecision> exploredCallSites = new ArrayList<>(); + OptimizedCallTarget parentTarget = stack.get(stack.size() - 1); + for (OptimizedDirectCallNode callNode : parentTarget.getCallNodes()) { + OptimizedCallTarget currentTarget = callNode.getCurrentCallTarget(); + stack.add(currentTarget); // push + exploredCallSites.add(exploreCallSite(stack, policy, callNode)); + stack.remove(stack.size() - 1); // pop + } + return exploredCallSites; + } + + private static InliningDecision exploreCallSite(List<OptimizedCallTarget> callStack, TruffleInliningPolicy policy, OptimizedDirectCallNode callNode) { + OptimizedCallTarget parentTarget = callStack.get(callStack.size() - 2); + OptimizedCallTarget currentTarget = callStack.get(callStack.size() - 1); + + boolean recursive = isRecursiveStack(callStack); + boolean maxDepth = callStack.size() >= 15; + + List<InliningDecision> childCallSites; + double frequency = TruffleInliningHandler.calculateFrequency(parentTarget, callNode); + int nodeCount = OptimizedCallUtils.countNonTrivialNodes(callNode.getCurrentCallTarget(), false); + int deepNodeCount; + if (recursive || maxDepth) { + deepNodeCount = nodeCount; + childCallSites = Collections.emptyList(); + } else { + childCallSites = decideInlining(nodeCount, exploreCallSites(callStack, policy), policy); + deepNodeCount = nodeCount; + for (InliningDecision childCallSite : childCallSites) { + if (childCallSite.isInline()) { + deepNodeCount += childCallSite.getProfile().getDeepNodeCount(); + } + } + } + + TruffleInliningProfile profile = new TruffleInliningProfile(callNode, nodeCount, deepNodeCount, frequency, recursive, null); + profile.setScore(policy.calculateScore(profile)); + return new InliningDecision(currentTarget, profile, childCallSites); + } + + private static boolean isRecursiveStack(List<OptimizedCallTarget> stack) { + OptimizedCallTarget top = stack.get(stack.size() - 1); + for (int i = 0; i < stack.size() - 1; i++) { + if (stack.get(i) == top) { + return true; + } + } + return false; + } + + private static List<InliningDecision> decideInlining(int nodeCount, List<InliningDecision> callSites, TruffleInliningPolicy policy) { + int deepNodeCount = nodeCount; + int index = 0; + for (InliningDecision callSite : callSites.stream().sorted().collect(Collectors.toList())) { + TruffleInliningProfile profile = callSite.getProfile(); + profile.setQueryIndex(index++); + if (policy.isAllowed(profile, deepNodeCount)) { + callSite.setInline(true); + deepNodeCount += profile.getDeepNodeCount(); + } + } + return callSites; + } + + public boolean isInlined(List<OptimizedDirectCallNode> callNodeTrace) { + if (callNodeTrace.isEmpty()) { + return false; + } + + InliningDecision prev = null; + for (int i = 0; i < callNodeTrace.size(); i++) { + if (prev == null) { + prev = findByCall(callNodeTrace.get(i)); + } else { + prev = prev.findByCall(callNodeTrace.get(i)); + } + if (prev == null || !prev.isInline()) { + return false; + } + } + return true; + } + + public int countCalls() { + return callSites.stream().mapToInt(callSite -> callSite.isInline() ? callSite.countCalls() + 1 : 1).sum(); + } + + public int countInlinedCalls() { + return callSites.stream().filter(InliningDecision::isInline).mapToInt(callSite -> callSite.countInlinedCalls() + 1).sum(); + } + + public List<InliningDecision> getCallSites() { + return callSites; + } + + public Iterator<InliningDecision> iterator() { + return callSites.iterator(); + } + + public InliningDecision findByCall(OptimizedDirectCallNode callNode) { + return getCallSites().stream().filter(c -> c.getProfile().getCallNode() == callNode).findFirst().orElse(null); + } + + public static final class InliningDecision extends ContextSensitiveInlining implements Comparable<InliningDecision> { + + private final OptimizedCallTarget target; + private final TruffleInliningProfile profile; + private boolean inline; + + public InliningDecision(OptimizedCallTarget target, TruffleInliningProfile profile, List<InliningDecision> children) { + super(children); + this.target = target; + this.profile = profile; + } + + public OptimizedCallTarget getTarget() { + return target; + } + + public void setInline(boolean inline) { + this.inline = inline; + } + + public boolean isInline() { + return inline; + } + + public TruffleInliningProfile getProfile() { + return profile; + } + + public int compareTo(InliningDecision o) { + return Double.compare(o.getProfile().getScore(), getProfile().getScore()); + } + + public boolean isSameAs(InliningDecision other) { + if (getTarget() != other.getTarget()) { + return false; + } else if (isInline() != other.isInline()) { + return false; + } else if (!isInline()) { + assert !other.isInline(); + return true; + } else { + Iterator<InliningDecision> i1 = iterator(); + Iterator<InliningDecision> i2 = other.iterator(); + while (i1.hasNext() && i2.hasNext()) { + if (!i1.next().isSameAs(i2.next())) { + return false; + } + } + return !i1.hasNext() && !i2.hasNext(); + } + } + + } + +}
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java Mon Sep 29 18:46:38 2014 +0200 @@ -31,6 +31,7 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.debug.*; +import com.oracle.graal.truffle.ContextSensitiveInlining.InliningDecision; import com.oracle.truffle.api.*; import com.oracle.truffle.api.CompilerDirectives.CompilationFinal; import com.oracle.truffle.api.frame.*; @@ -58,9 +59,13 @@ private final RootNode rootNode; + /* Experimental fields for new splitting. */ private final Map<TruffleStamp, OptimizedCallTarget> splitVersions = new HashMap<>(); private TruffleStamp argumentStamp = DefaultTruffleStamp.getInstance(); + /* Experimental field for context sensitive inlining. */ + private ContextSensitiveInlining inliningDecision; + public final RootNode getRootNode() { return rootNode; } @@ -204,7 +209,36 @@ // We come here from compiled code (i.e., we have been inlined). } - return callRoot(args); + Object[] args1 = args; + if (this.profiledArgumentTypesAssumption != null && CompilerDirectives.inCompiledCode() && profiledArgumentTypesAssumption.isValid()) { + args1 = CompilerDirectives.unsafeCast(castArrayFixedLength(args1, profiledArgumentTypes.length), Object[].class, true, true); + if (TruffleArgumentTypeSpeculation.getValue()) { + args1 = castArguments(args1); + } + } + Object result = callRoot(args1); + + // Profile call return type + if (profiledReturnTypeAssumption == null) { + if (TruffleReturnTypeSpeculation.getValue()) { + CompilerDirectives.transferToInterpreterAndInvalidate(); + profiledReturnType = (result == null ? null : result.getClass()); + profiledReturnTypeAssumption = runtime.createAssumption("Profiled Return Type"); + } + } else if (profiledReturnType != null) { + if (result == null || profiledReturnType != result.getClass()) { + CompilerDirectives.transferToInterpreterAndInvalidate(); + profiledReturnType = null; + profiledReturnTypeAssumption.invalidate(); + } + } + + return result; + } + + private Object callRoot(Object[] args) { + VirtualFrame frame = createFrame(getRootNode().getFrameDescriptor(), args); + return callProxy(frame); } @Override @@ -241,6 +275,26 @@ } } + public ContextSensitiveInlining getInliningDecision() { + return inliningDecision; + } + + public void setInliningDecision(ContextSensitiveInlining inliningDecision) { + this.inliningDecision = inliningDecision; + } + + public boolean isInlined(List<OptimizedDirectCallNode> callNodeTrace) { + if (TruffleCompilerOptions.TruffleContextSensitiveInlining.getValue()) { + if (inliningDecision == null) { + return false; + } else { + return inliningDecision.isInlined(callNodeTrace); + } + } else { + return callNodeTrace.get(callNodeTrace.size() - 1).isInlined(); + } + } + private void cancelInstalledTask(Node oldNode, Node newNode, CharSequence reason) { if (this.runtime.cancelInstalledTask(this)) { logOptimizingUnqueued(this, oldNode, newNode, reason); @@ -275,6 +329,9 @@ public void compilationFinished(Throwable t) { if (t == null) { // Compilation was successful. + if (inliningDecision != null) { + dequeueInlinedCallSites(inliningDecision); + } } else { compilationPolicy.recordCompilationFailure(t); @@ -291,6 +348,18 @@ } } + private void dequeueInlinedCallSites(ContextSensitiveInlining parentDecision) { + for (InliningDecision decision : parentDecision) { + if (decision.isInline()) { + OptimizedCallTarget target = decision.getProfile().getCallNode().getCurrentCallTarget(); + if (runtime.cancelInstalledTask(target)) { + logOptimizingUnqueued(target, null, null, "Inlining caller compiled."); + } + dequeueInlinedCallSites(decision); + } + } + } + protected final Object callProxy(VirtualFrame frame) { try { return getRootNode().execute(frame); @@ -345,7 +414,7 @@ } public final void performInlining() { - if (!TruffleFunctionInlining.getValue()) { + if (!TruffleFunctionInlining.getValue() || TruffleContextSensitiveInlining.getValue()) { return; } if (inliningPerformed) { @@ -371,36 +440,6 @@ } } - public final Object callRoot(Object[] originalArguments) { - Object[] args = originalArguments; - if (this.profiledArgumentTypesAssumption != null && CompilerDirectives.inCompiledCode() && profiledArgumentTypesAssumption.isValid()) { - args = CompilerDirectives.unsafeCast(castArrayFixedLength(args, profiledArgumentTypes.length), Object[].class, true, true); - if (TruffleArgumentTypeSpeculation.getValue()) { - args = castArguments(args); - } - } - - VirtualFrame frame = createFrame(getRootNode().getFrameDescriptor(), args); - Object result = callProxy(frame); - - // Profile call return type - if (profiledReturnTypeAssumption == null) { - if (TruffleReturnTypeSpeculation.getValue()) { - CompilerDirectives.transferToInterpreterAndInvalidate(); - profiledReturnType = (result == null ? null : result.getClass()); - profiledReturnTypeAssumption = Truffle.getRuntime().createAssumption("Profiled Return Type"); - } - } else if (profiledReturnType != null) { - if (result == null || profiledReturnType != result.getClass()) { - CompilerDirectives.transferToInterpreterAndInvalidate(); - profiledReturnType = null; - profiledReturnTypeAssumption.invalidate(); - } - } - - return result; - } - @ExplodeLoop private Object[] castArguments(Object[] originalArguments) { Object[] castArguments = new Object[profiledArgumentTypes.length]; @@ -418,6 +457,10 @@ return new FrameWithoutBoxing(descriptor, args); } + public List<OptimizedDirectCallNode> getCallNodes() { + return NodeUtil.findAllNodeInstances(getRootNode(), OptimizedDirectCallNode.class); + } + @Override public void reportLoopCount(int count) { compilationProfile.reportLoopCount(count);
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTargetLog.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTargetLog.java Mon Sep 29 18:46:38 2014 +0200 @@ -28,6 +28,7 @@ import java.util.*; import com.oracle.graal.debug.*; +import com.oracle.graal.truffle.ContextSensitiveInlining.InliningDecision; import com.oracle.truffle.api.nodes.*; import com.oracle.truffle.api.nodes.NodeUtil.NodeCountFilter; @@ -53,6 +54,29 @@ private OptimizedCallTargetLog() { } + public static void logInliningDecision(OptimizedCallTarget target) { + ContextSensitiveInlining inlining = target.getInliningDecision(); + if (!TraceTruffleInlining.getValue() || inlining == null) { + return; + } + + logInliningStart(target); + logInliningDecisionRecursive(inlining, 1); + logInliningDone(target); + } + + private static void logInliningDecisionRecursive(ContextSensitiveInlining result, int depth) { + for (InliningDecision decision : result) { + TruffleInliningProfile profile = decision.getProfile(); + boolean inlined = decision.isInline(); + String msg = inlined ? "inline success" : "inline failed"; + logInlinedImpl(msg, decision.getProfile().getCallNode(), profile, depth); + if (inlined) { + logInliningDecisionRecursive(decision, depth + 1); + } + } + } + public static void logInliningDecision(TruffleInliningDecision result) { if (!TraceTruffleInlining.getValue()) { return; @@ -119,7 +143,6 @@ private static void logInlinedImpl(String status, OptimizedDirectCallNode callNode, TruffleInliningProfile profile, int depth) { Map<String, Object> properties = new LinkedHashMap<>(); - addASTSizeProperty(callNode.getCurrentCallTarget(), properties); if (profile != null) { properties.putAll(profile.getDebugProperties()); } @@ -224,20 +247,27 @@ } public static void addASTSizeProperty(OptimizedCallTarget target, Map<String, Object> properties) { - int polymorphicCount = NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { - public boolean isCounted(Node node) { - return node.getCost() == NodeCost.POLYMORPHIC; - } - }, true); + if (TruffleContextSensitiveInlining.getValue() && target.getInliningDecision() != null) { + int deepCount = target.getInliningDecision().getCallSites().stream().filter(callSite -> callSite.isInline()).mapToInt(callSite -> callSite.getProfile().getDeepNodeCount()).sum(); + long nodeCount = OptimizedCallUtils.countNonTrivialNodes(target, false); + properties.put("ASTSize", String.format("%5d/%5d", nodeCount, nodeCount + deepCount)); + } else { + int polymorphicCount = NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { + public boolean isCounted(Node node) { + return node.getCost() == NodeCost.POLYMORPHIC; + } + }, true); - int megamorphicCount = NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { - public boolean isCounted(Node node) { - return node.getCost() == NodeCost.MEGAMORPHIC; - } - }, true); + int megamorphicCount = NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { + public boolean isCounted(Node node) { + return node.getCost() == NodeCost.MEGAMORPHIC; + } + }, true); - String value = String.format("%4d (%d/%d)", OptimizedCallUtils.countNonTrivialNodes(target, true), polymorphicCount, megamorphicCount); - properties.put("ASTSize", value); + String value = String.format("%4d (%d/%d)", OptimizedCallUtils.countNonTrivialNodes(target, true), polymorphicCount, megamorphicCount); + properties.put("ASTSize", value); + } + } static void log(int indent, String msg, String details, Map<String, Object> properties) {
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallUtils.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallUtils.java Mon Sep 29 18:46:38 2014 +0200 @@ -32,19 +32,29 @@ public class OptimizedCallUtils { public static int countCalls(OptimizedCallTarget target) { - return NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { - public boolean isCounted(Node node) { - return node instanceof DirectCallNode; - } - }, true); + ContextSensitiveInlining inlining = target.getInliningDecision(); + if (inlining != null) { + return inlining.countCalls(); + } else { + return NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { + public boolean isCounted(Node node) { + return node instanceof DirectCallNode; + } + }, true); + } } public static int countCallsInlined(OptimizedCallTarget target) { - return NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { - public boolean isCounted(Node node) { - return (node instanceof OptimizedDirectCallNode) && ((OptimizedDirectCallNode) node).isInlined(); - } - }, true); + ContextSensitiveInlining inlining = target.getInliningDecision(); + if (inlining != null) { + return inlining.countInlinedCalls(); + } else { + return NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { + public boolean isCounted(Node node) { + return (node instanceof OptimizedDirectCallNode) && ((OptimizedDirectCallNode) node).isInlined(); + } + }, true); + } } public static int countNonTrivialNodes(final OptimizedCallTarget target, final boolean inlined) {
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedDirectCallNode.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedDirectCallNode.java Mon Sep 29 18:46:38 2014 +0200 @@ -57,7 +57,14 @@ if (CompilerDirectives.inInterpreter()) { onInterpreterCall(arguments); } - Object result = callProxy(this, getCurrentCallTarget(), frame, arguments, inlined, true); + boolean isInlined; + if (TruffleCompilerOptions.TruffleContextSensitiveInlining.getValue()) { + /* Inlining done during partial evalulation. */ + isInlined = false; + } else { + isInlined = this.inlined; + } + Object result = callProxy(this, getCurrentCallTarget(), frame, arguments, isInlined, true); if (CompilerDirectives.inInterpreter()) { afterInterpreterCall(result);
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java Mon Sep 29 18:46:38 2014 +0200 @@ -51,6 +51,7 @@ import com.oracle.graal.phases.common.inlining.info.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.phases.util.*; +import com.oracle.graal.truffle.ContextSensitiveInlining.InliningDecision; import com.oracle.graal.truffle.nodes.asserts.*; import com.oracle.graal.truffle.nodes.frame.*; import com.oracle.graal.truffle.nodes.frame.NewFrameNode.VirtualOnlyInstanceNode; @@ -58,6 +59,8 @@ import com.oracle.graal.virtual.phases.ea.*; import com.oracle.truffle.api.*; import com.oracle.truffle.api.nodes.*; +import com.oracle.truffle.api.nodes.Node.Child; +import com.oracle.truffle.api.nodes.Node.Children; /** * Class performing the partial evaluation starting from the root node of an AST. @@ -68,53 +71,43 @@ private final CanonicalizerPhase canonicalizer; private Set<Constant> constantReceivers; private final TruffleCache truffleCache; + private final SnippetReflectionProvider snippetReflection; + private final ResolvedJavaMethod directCallMethod; public PartialEvaluator(Providers providers, TruffleCache truffleCache) { this.providers = providers; CustomCanonicalizer customCanonicalizer = new PartialEvaluatorCanonicalizer(providers.getMetaAccess(), providers.getConstantReflection()); this.canonicalizer = new CanonicalizerPhase(!ImmutableCode.getValue(), customCanonicalizer); + this.snippetReflection = Graal.getRequiredCapability(SnippetReflectionProvider.class); this.truffleCache = truffleCache; + this.directCallMethod = providers.getMetaAccess().lookupJavaMethod(GraalFrameInstance.CallNodeFrame.METHOD); } - public StructuredGraph createGraph(final OptimizedCallTarget callTarget, final Assumptions assumptions) { - try (Scope s = Debug.scope("TruffleTree")) { + public StructuredGraph createGraph(final OptimizedCallTarget callTarget, final Assumptions assumptions, ContextSensitiveInlining inlining) { + if (TraceTruffleCompilationHistogram.getValue() || TraceTruffleCompilationDetails.getValue()) { + constantReceivers = new HashSet<>(); + } + + try (Scope c = Debug.scope("TruffleTree")) { Debug.dump(callTarget, "truffle tree"); } catch (Throwable e) { throw Debug.handle(e); } - - if (TraceTruffleCompilationHistogram.getValue() || TraceTruffleCompilationDetails.getValue()) { - constantReceivers = new HashSet<>(); - } - final StructuredGraph graph = truffleCache.createRootGraph(callTarget.toString()); assert graph != null : "no graph for root method"; try (Scope s = Debug.scope("CreateGraph", graph); Indent indent = Debug.logAndIndent("createGraph %s", graph.method())) { - - // Replace thisNode with constant. - ParameterNode thisNode = graph.getParameter(0); - - /* - * Converting the call target to a Constant using the SnippetReflectionProvider is a - * workaround, we should think about a better solution. Since object constants are - * VM-specific, only the hosting VM knows how to do the conversion. - */ - SnippetReflectionProvider snippetReflection = Graal.getRequiredCapability(SnippetReflectionProvider.class); - thisNode.replaceAndDelete(ConstantNode.forConstant(snippetReflection.forObject(callTarget), providers.getMetaAccess(), graph)); - // Canonicalize / constant propagate. PhaseContext baseContext = new PhaseContext(providers, assumptions); - canonicalizer.apply(graph, baseContext); - // Intrinsify methods. - new IncrementalCanonicalizerPhase<>(canonicalizer, new ReplaceIntrinsicsPhase(providers.getReplacements())).apply(graph, baseContext); + injectConstantCallTarget(graph, callTarget, baseContext); - Debug.dump(graph, "Before inlining"); + Debug.dump(graph, "Before expansion"); - // Make sure frame does not escape. expandTree(graph, assumptions); + expandCallBoundaries(graph, assumptions, inlining != null ? new TruffleInliningCache() : null, inlining); + if (Thread.currentThread().isInterrupted()) { return null; } @@ -170,6 +163,7 @@ } } } + } catch (Throwable e) { throw Debug.handle(e); } @@ -177,6 +171,37 @@ return graph; } + private void expandCallBoundaries(StructuredGraph graph, Assumptions assumptions, TruffleInliningCache inliningCache, ContextSensitiveInlining inlining) { + if (inlining == null) { + return; + } + PhaseContext phaseContext = new PhaseContext(providers, assumptions); + TruffleExpansionLogger expansionLogger = new TruffleExpansionLogger(providers, graph); + + for (MethodCallTargetNode methodCallTargetNode : graph.getNodes(MethodCallTargetNode.class).snapshot()) { + StructuredGraph inlineGraph = parseInlineGraph(phaseContext, assumptions, inliningCache, inlining, methodCallTargetNode); + + if (inlineGraph != null) { + expandTreeInline(graph, phaseContext, expansionLogger, methodCallTargetNode, inlineGraph); + } + } + } + + private void injectConstantCallTarget(final StructuredGraph graph, final OptimizedCallTarget constantCallTarget, PhaseContext baseContext) { + ParameterNode thisNode = graph.getParameter(0); + + /* + * Converting the call target to a Constant using the SnippetReflectionProvider is a + * workaround, we should think about a better solution. Since object constants are + * VM-specific, only the hosting VM knows how to do the conversion. + */ + thisNode.replaceAndDelete(ConstantNode.forConstant(snippetReflection.forObject(constantCallTarget), providers.getMetaAccess(), graph)); + + canonicalizer.apply(graph, baseContext); + + new IncrementalCanonicalizerPhase<>(canonicalizer, new ReplaceIntrinsicsPhase(providers.getReplacements())).apply(graph, baseContext); + } + private void createHistogram() { DebugHistogram histogram = Debug.createHistogram("Expanded Truffle Nodes"); for (Constant c : constantReceivers) { @@ -219,8 +244,8 @@ changed = changedInIteration = true; continue; } + StructuredGraph inlineGraph = replacements.getMethodSubstitution(methodCallTargetNode.targetMethod()); - StructuredGraph inlineGraph = replacements.getMethodSubstitution(methodCallTargetNode.targetMethod()); if (inlineGraph == null && !methodCallTargetNode.targetMethod().isNative() && methodCallTargetNode.targetMethod().canBeInlined()) { inlineGraph = parseGraph(methodCallTargetNode.targetMethod(), methodCallTargetNode.arguments(), assumptions, phaseContext); } @@ -236,6 +261,7 @@ throw new BailoutException("Truffle compilation is exceeding maximum node count: " + graph.getNodeCount()); } } + } while (changedInIteration); if (TraceTruffleExpansion.getValue()) { @@ -244,20 +270,115 @@ return changed; } + private StructuredGraph parseInlineGraph(PhaseContext phaseContext, Assumptions assumptions, TruffleInliningCache inliningCache, ContextSensitiveInlining inlining, + MethodCallTargetNode methodCallTargetNode) { + OptimizedDirectCallNode callNode = resolveConstantCallNode(methodCallTargetNode); + if (callNode == null) { + return null; + } + + InliningDecision decision = inlining.findByCall(callNode); + if (decision == null) { + if (TruffleCompilerOptions.PrintTrufflePerformanceWarnings.getValue()) { + OptimizedCallTargetLog.log(0, "perf warn", String.format( + "%s '%s' is reached using partial evaluation but it is not reachable in the Truffle AST. Did you miss @%s or @%s annotation on a node field?. ", + DirectCallNode.class.getSimpleName(), callNode, Child.class.getSimpleName(), Children.class.getSimpleName()), callNode.getRootNode().getDebugProperties()); + } + return null; + } + + assert decision.getProfile().getCallNode() == callNode; + + if (!decision.isInline()) { + return null; + } + + OptimizedCallTarget currentTarget = decision.getProfile().getCallNode().getCurrentCallTarget(); + if (decision.getTarget() != currentTarget) { + if (TruffleCompilerOptions.PrintTrufflePerformanceWarnings.getValue()) { + OptimizedCallTargetLog.log(0, "perf warn", + String.format("CallTarget '%s' changed to '%s' during compilation for call node '%s'. Call node was not inlined.", decision.getTarget(), currentTarget, callNode), null); + + } + return null; + } + + StructuredGraph graph; + if (inliningCache == null) { + graph = createInlineGraph(phaseContext, assumptions, null, decision); + } else { + graph = inliningCache.getCachedGraph(phaseContext, assumptions, decision); + } + + decision.getProfile().setGraalDeepNodeCount(graph.getNodeCount()); + + return graph; + } + + private StructuredGraph createInlineGraph(PhaseContext phaseContext, Assumptions assumptions, TruffleInliningCache cache, InliningDecision decision) { + OptimizedCallTarget target = decision.getTarget(); + StructuredGraph inlineGraph = truffleCache.createInlineGraph(target.toString()); + injectConstantCallTarget(inlineGraph, decision.getTarget(), phaseContext); + expandTree(inlineGraph, assumptions); + expandCallBoundaries(inlineGraph, assumptions, cache, decision); + return inlineGraph; + } + + private OptimizedDirectCallNode resolveConstantCallNode(MethodCallTargetNode methodCallTargetNode) { + if (methodCallTargetNode.targetMethod().getAnnotation(TruffleCallBoundary.class) == null) { + return null; + } + + Invoke invoke = methodCallTargetNode.invoke(); + if (invoke == null) { + return null; + } + + FrameState directCallState = invoke.stateAfter(); + while (directCallState != null && directCallState.method() != directCallMethod) { + directCallState = directCallState.outerFrameState(); + } + + if (directCallState == null) { + // not a direct call. May be indirect call. + return null; + } + + if (directCallState.values().isEmpty()) { + throw new AssertionError(String.format("Frame state of method '%s' is invalid.", directCallMethod.toString())); + } + + ValueNode node = directCallState.values().get(0); + if (!node.isConstant()) { + throw new AssertionError(String.format("Method argument for method '%s' is not constant.", directCallMethod.toString())); + } + + Constant constantCallNode = node.asConstant(); + Object value = snippetReflection.asObject(constantCallNode); + + if (!(value instanceof OptimizedDirectCallNode)) { + // might be an indirect call. + return null; + } + + return (OptimizedDirectCallNode) value; + } + private void expandTreeInline(StructuredGraph graph, PhaseContext phaseContext, TruffleExpansionLogger expansionLogger, MethodCallTargetNode methodCallTargetNode, StructuredGraph inlineGraph) { - try (Indent indent = Debug.logAndIndent("inline graph %s", methodCallTargetNode.targetMethod())) { + try (Indent indent = Debug.logAndIndent("expand graph %s", methodCallTargetNode.targetMethod())) { int nodeCountBefore = graph.getNodeCount(); if (TraceTruffleExpansion.getValue()) { expansionLogger.preExpand(methodCallTargetNode, inlineGraph); } List<Node> canonicalizedNodes = methodCallTargetNode.invoke().asNode().usages().snapshot(); + Map<Node, Node> inlined = InliningUtil.inline(methodCallTargetNode.invoke(), inlineGraph, false, canonicalizedNodes); if (TraceTruffleExpansion.getValue()) { expansionLogger.postExpand(inlined); } if (Debug.isDumpEnabled()) { int nodeCountAfter = graph.getNodeCount(); - Debug.dump(graph, "After inlining %s %+d (%d)", methodCallTargetNode.targetMethod().toString(), nodeCountAfter - nodeCountBefore, nodeCountAfter); + Debug.dump(graph, "After expand %s %+d (%d)", methodCallTargetNode.targetMethod().toString(), nodeCountAfter - nodeCountBefore, nodeCountAfter); } AbstractInlineInfo.getInlinedParameterUsages(canonicalizedNodes, inlineGraph, inlined); canonicalizer.applyIncremental(graph, phaseContext, canonicalizedNodes); @@ -325,4 +446,51 @@ return sortedLoops; } + private final class TruffleInliningCache { + + private final Map<CacheKey, StructuredGraph> cache; + + public TruffleInliningCache() { + this.cache = new HashMap<>(); + } + + public StructuredGraph getCachedGraph(PhaseContext phaseContext, Assumptions assumptions, InliningDecision decision) { + CacheKey cacheKey = new CacheKey(decision); + StructuredGraph inlineGraph = cache.get(cacheKey); + if (inlineGraph == null) { + inlineGraph = createInlineGraph(phaseContext, assumptions, this, decision); + cache.put(cacheKey, inlineGraph); + } + return inlineGraph; + } + + private final class CacheKey { + + public final InliningDecision decision; + + public CacheKey(InliningDecision decision) { + this.decision = decision; + /* + * If decision.isInline() is not true CacheKey#hashCode does not match + * CacheKey#equals + */ + assert decision.isInline(); + } + + @Override + public int hashCode() { + return decision.getTarget().hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof CacheKey)) { + return false; + } + CacheKey other = (CacheKey) obj; + return decision.isSameAs(other.decision); + } + } + } + }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCache.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCache.java Mon Sep 29 18:46:38 2014 +0200 @@ -35,6 +35,8 @@ */ StructuredGraph createRootGraph(String name); + StructuredGraph createInlineGraph(String name); + /** * Returns a cached graph for a method with given arguments. */
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCacheImpl.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCacheImpl.java Mon Sep 29 18:46:38 2014 +0200 @@ -56,7 +56,7 @@ private final Providers providers; private final GraphBuilderConfiguration config; - private final GraphBuilderConfiguration configForRootGraph; + private final GraphBuilderConfiguration configForRoot; private final OptimisticOptimizations optimisticOptimizations; private final HashMap<List<Object>, StructuredGraph> cache = new HashMap<>(); @@ -69,12 +69,14 @@ private final ResolvedJavaType controlFlowExceptionClass; private final ResolvedJavaMethod callBoundaryMethod; + private final ResolvedJavaMethod inlineCallBoundaryMethod; + private long counter; - public TruffleCacheImpl(Providers providers, GraphBuilderConfiguration config, GraphBuilderConfiguration configForRootGraph, OptimisticOptimizations optimisticOptimizations) { + public TruffleCacheImpl(Providers providers, GraphBuilderConfiguration config, GraphBuilderConfiguration configForRoot, OptimisticOptimizations optimisticOptimizations) { this.providers = providers; this.config = config; - this.configForRootGraph = configForRootGraph; + this.configForRoot = configForRoot; this.optimisticOptimizations = optimisticOptimizations; this.stringBuilderClass = providers.getMetaAccess().lookupJavaType(StringBuilder.class); @@ -83,15 +85,26 @@ this.controlFlowExceptionClass = providers.getMetaAccess().lookupJavaType(ControlFlowException.class); try { - callBoundaryMethod = providers.getMetaAccess().lookupJavaMethod(OptimizedCallTarget.class.getDeclaredMethod("callRoot", Object[].class)); + callBoundaryMethod = providers.getMetaAccess().lookupJavaMethod(OptimizedCallTarget.class.getDeclaredMethod("callBoundary", Object[].class)); + } catch (NoSuchMethodException ex) { + throw new RuntimeException(ex); + } + try { + inlineCallBoundaryMethod = providers.getMetaAccess().lookupJavaMethod(OptimizedCallTarget.class.getDeclaredMethod("callRoot", Object[].class)); } catch (NoSuchMethodException ex) { throw new RuntimeException(ex); } } + public StructuredGraph createInlineGraph(String name) { + StructuredGraph graph = new StructuredGraph(name, inlineCallBoundaryMethod); + new GraphBuilderPhase.Instance(providers.getMetaAccess(), config, TruffleCompilerImpl.Optimizations).apply(graph); + return graph; + } + public StructuredGraph createRootGraph(String name) { StructuredGraph graph = new StructuredGraph(name, callBoundaryMethod); - new GraphBuilderPhase.Instance(providers.getMetaAccess(), configForRootGraph, TruffleCompilerImpl.Optimizations).apply(graph); + new GraphBuilderPhase.Instance(providers.getMetaAccess(), configForRoot, TruffleCompilerImpl.Optimizations).apply(graph); return graph; }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerImpl.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerImpl.java Mon Sep 29 18:46:38 2014 +0200 @@ -80,7 +80,6 @@ ResolvedJavaType[] skippedExceptionTypes = getSkippedExceptionTypes(providers.getMetaAccess()); GraphBuilderConfiguration eagerConfig = GraphBuilderConfiguration.getEagerDefault().withSkippedExceptionTypes(skippedExceptionTypes); this.config = GraphBuilderConfiguration.getDefault().withSkippedExceptionTypes(skippedExceptionTypes); - this.truffleCache = new TruffleCacheImpl(providers, eagerConfig, config, TruffleCompilerImpl.Optimizations); this.partialEvaluator = new PartialEvaluator(providers, truffleCache); @@ -122,8 +121,9 @@ long timeCompilationStarted = System.nanoTime(); Assumptions assumptions = new Assumptions(true); + ContextSensitiveInlining inlining = TruffleCompilerOptions.TruffleContextSensitiveInlining.getValue() ? new ContextSensitiveInlining(compilable, new DefaultInliningPolicy()) : null; try (TimerCloseable a = PartialEvaluationTime.start(); Closeable c = PartialEvaluationMemUse.start()) { - graph = partialEvaluator.createGraph(compilable, assumptions); + graph = partialEvaluator.createGraph(compilable, assumptions, inlining); } if (Thread.currentThread().isInterrupted()) { @@ -136,13 +136,15 @@ long timeCompilationFinished = System.nanoTime(); int nodeCountLowered = graph.getNodeCount(); - if (Thread.currentThread().isInterrupted()) { - return; + compilable.setInliningDecision(inlining); + + if (TraceTruffleInlining.getValue() && inlining != null) { + OptimizedCallTargetLog.logInliningDecision(compilable); } - if (TraceTruffleCompilation.getValue()) { printTruffleCompilation(compilable, timeCompilationStarted, timePartialEvaluationFinished, nodeCountPartialEval, compilationResult, timeCompilationFinished, nodeCountLowered); } + } private static void printTruffleCompilation(final OptimizedCallTarget compilable, long timeCompilationStarted, long timePartialEvaluationFinished, int nodeCountPartialEval,
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java Mon Sep 29 18:46:38 2014 +0200 @@ -53,6 +53,10 @@ public static final OptionValue<Integer> TruffleReplaceReprofileCount = new OptionValue<>(10); @Option(help = "Enable automatic inlining of call targets") public static final OptionValue<Boolean> TruffleFunctionInlining = new OptionValue<>(true); + @Option(help = "Experimental: Enable context senstive inlining decisions.") + public static final StableOptionValue<Boolean> TruffleContextSensitiveInlining = new StableOptionValue<>(false); + @Option(help = "Experimental: Enable an expansion cache per CallTarget. Only functionable with TruffleContextSensitiveInlining enabled.") + public static final OptionValue<Boolean> TruffleCallTargetExpansionCache = new OptionValue<>(true); @Option(help = "Maximum number of Graal IR nodes during partial evaluation") public static final OptionValue<Integer> TruffleGraphMaxNodes = new OptionValue<>(200000); @Option(help = "Stop inlining if caller's cumulative tree size would exceed this limit") @@ -95,6 +99,8 @@ public static final OptionValue<Boolean> TruffleArgumentTypeSpeculation = new StableOptionValue<>(true); // tracing + @Option(help = "Prints potential performance problems of the guest language implementation.") + public static final OptionValue<Boolean> PrintTrufflePerformanceWarnings = new OptionValue<>(false); @Option(help = "") public static final OptionValue<Boolean> TraceTruffleCompilation = new OptionValue<>(false); @Option(help = "")
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningHandler.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningHandler.java Mon Sep 29 18:46:38 2014 +0200 @@ -110,7 +110,7 @@ return policy; } - private static double calculateFrequency(OptimizedCallTarget target, OptimizedDirectCallNode ocn) { + public static double calculateFrequency(OptimizedCallTarget target, OptimizedDirectCallNode ocn) { return (double) Math.max(1, ocn.getCallCount()) / (double) Math.max(1, target.getCompilationProfile().getCallCount()); }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningProfile.java Mon Sep 29 18:39:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningProfile.java Mon Sep 29 18:46:38 2014 +0200 @@ -33,6 +33,7 @@ private final boolean recursiveCall; private final TruffleInliningDecision recursiveResult; + private int graalDeepNodeCount = -1; private String failedReason; private int queryIndex = -1; private double score; @@ -104,11 +105,23 @@ public Map<String, Object> getDebugProperties() { Map<String, Object> properties = new LinkedHashMap<>(); - properties.put("nodeCount", String.format("%5d/%5d", deepNodeCount, nodeCount)); - properties.put("frequency", frequency); + properties.put("ASTSize", String.format("%5d/%5d", nodeCount, deepNodeCount)); + properties.put("frequency", String.format("%8.4f", getFrequency())); properties.put("score", String.format("%8.4f", getScore())); properties.put(String.format("index=%3d, force=%s, callSites=%2d", queryIndex, (isForced() ? "Y" : "N"), getCallSites()), ""); + if (graalDeepNodeCount != -1) { + properties.put("graalCount", String.format("%5d", graalDeepNodeCount)); + } properties.put("reason", failedReason); return properties; } + + public void setGraalDeepNodeCount(int graalDeepNodeCount) { + this.graalDeepNodeCount = graalDeepNodeCount; + } + + public int getGraalDeepNodeCount() { + return graalDeepNodeCount; + } + }