# HG changeset patch # User Thomas Wuerthinger # Date 1392914549 -3600 # Node ID 14018434a59a416a1075d35ce11b82e1c7a6d729 # Parent 25b86e46536514345e0d008ea3bb88ee1339723d# Parent fcc40370f78dbfb5eced6b8f5bbd780d4e850c47 Merge. diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/PartialEvaluationTest.java --- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/PartialEvaluationTest.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/PartialEvaluationTest.java Thu Feb 20 17:42:29 2014 +0100 @@ -88,11 +88,10 @@ final OptimizedCallTarget compilable = (OptimizedCallTarget) Truffle.getRuntime().createCallTarget(root); // Executed AST so that all classes are loaded and initialized. - do { - compilable.call(null, arguments); - compilable.call(null, arguments); - compilable.call(null, arguments); - } while (compilable.inline()); + compilable.call(null, arguments); + compilable.call(null, arguments); + compilable.call(null, arguments); + compilable.performInlining(); try (Scope s = Debug.scope("TruffleCompilation", new TruffleDebugJavaMethod(compilable))) { diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/CompilationProfile.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/CompilationProfile.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/CompilationProfile.java Thu Feb 20 17:42:29 2014 +0100 @@ -26,9 +26,6 @@ public class CompilationProfile { - private int invokeCounter; - private int originalInvokeCounter; - private int loopAndInvokeCounter; /** * Number of times an installed code for this tree was invalidated. */ @@ -41,17 +38,30 @@ private long previousTimestamp; - private final int compilationThreshold; private final String name; + private int callCount; + private int callAndLoopCount; + private int compilationCallThreshold; + private int compilationCallAndLoopThreshold; + + private final int originalInvokeCounter; + private final int originalCompilationThreshold; + public CompilationProfile(final int compilationThreshold, final int initialInvokeCounter, final String name) { - this.invokeCounter = initialInvokeCounter; - this.loopAndInvokeCounter = compilationThreshold; - this.originalInvokeCounter = compilationThreshold; this.previousTimestamp = System.nanoTime(); + this.compilationCallThreshold = initialInvokeCounter; + this.compilationCallAndLoopThreshold = compilationThreshold; + this.originalInvokeCounter = initialInvokeCounter; + this.originalCompilationThreshold = compilationThreshold; + this.name = name; + } - this.compilationThreshold = compilationThreshold; - this.name = name; + public void reset() { + callCount = 0; + callAndLoopCount = 0; + compilationCallAndLoopThreshold = originalCompilationThreshold; + compilationCallThreshold = originalInvokeCounter; } public long getPreviousTimestamp() { @@ -70,54 +80,64 @@ return nodeReplaceCount; } - public int getInvokeCounter() { - return invokeCounter; + public int getCallAndLoopCount() { + return callAndLoopCount; + } + + public int getCallCount() { + return callCount; + } + + public int getCompilationCallAndLoopThreshold() { + return compilationCallAndLoopThreshold; } - public int getOriginalInvokeCounter() { - return originalInvokeCounter; + public int getCompilationCallThreshold() { + return compilationCallThreshold; } - public int getLoopAndInvokeCounter() { - return loopAndInvokeCounter; + void ensureProfiling(int calls, int callsAndLoop) { + int increaseCallAndLoopThreshold = callsAndLoop - (this.compilationCallAndLoopThreshold - this.callAndLoopCount); + if (increaseCallAndLoopThreshold > 0) { + this.compilationCallAndLoopThreshold += increaseCallAndLoopThreshold; + } + + int increaseCallsThreshold = calls - (this.compilationCallThreshold - this.callCount); + if (increaseCallsThreshold > 0) { + this.compilationCallThreshold += increaseCallsThreshold; + } } void reportTiminingFailed(long timestamp) { - this.loopAndInvokeCounter = compilationThreshold; - this.originalInvokeCounter = compilationThreshold; + ensureProfiling(0, originalCompilationThreshold); this.previousTimestamp = timestamp; } void reportInvalidated() { invalidationCount++; - int invalidationReprofileCount = TruffleInvalidationReprofileCount.getValue(); - invokeCounter = invalidationReprofileCount; - originalInvokeCounter += invalidationReprofileCount; + int reprofile = TruffleInvalidationReprofileCount.getValue(); + ensureProfiling(reprofile, reprofile); } void reportInterpreterCall() { - invokeCounter--; - loopAndInvokeCounter--; + callCount++; + callAndLoopCount++; } - void reportInliningPerformed(TruffleInlining inlining) { - invokeCounter = inlining.getInvocationReprofileCount(); - int inliningReprofileCount = inlining.getReprofileCount(); - loopAndInvokeCounter = inliningReprofileCount; - originalInvokeCounter = inliningReprofileCount; + void reportInterpreterCalls(int calls) { + this.callCount += calls; + this.callAndLoopCount += calls; } void reportLoopCount(int count) { - loopAndInvokeCounter = Math.max(0, loopAndInvokeCounter - count); + callAndLoopCount += count; } void reportNodeReplaced() { nodeReplaceCount++; // delay compilation until tree is deemed stable enough int replaceBackoff = TruffleReplaceReprofileCount.getValue(); - if (loopAndInvokeCounter < replaceBackoff) { - loopAndInvokeCounter = replaceBackoff; - } + ensureProfiling(1, replaceBackoff); } } diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultCompilationPolicy.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultCompilationPolicy.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultCompilationPolicy.java Thu Feb 20 17:42:29 2014 +0100 @@ -25,7 +25,7 @@ public class DefaultCompilationPolicy implements CompilationPolicy { public boolean shouldCompile(CompilationProfile profile) { - return profile.getInvokeCounter() <= 0 && profile.getLoopAndInvokeCounter() <= 0; + return profile.getCallCount() >= profile.getCompilationCallThreshold() && profile.getCallAndLoopCount() >= profile.getCompilationCallAndLoopThreshold(); } } diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/GraalTruffleRuntime.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/GraalTruffleRuntime.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/GraalTruffleRuntime.java Thu Feb 20 17:42:29 2014 +0100 @@ -48,6 +48,7 @@ import com.oracle.graal.runtime.*; import com.oracle.truffle.api.*; import com.oracle.truffle.api.frame.*; +import com.oracle.truffle.api.impl.*; import com.oracle.truffle.api.nodes.*; /** @@ -79,6 +80,14 @@ return new OptimizedCallTarget(rootNode, truffleCompiler, TruffleMinInvokeThreshold.getValue(), TruffleCompilationThreshold.getValue(), acceptForCompilation(rootNode)); } + public CallNode createCallNode(CallTarget target) { + if (target instanceof OptimizedCallTarget) { + return OptimizedCallNode.create((OptimizedCallTarget) target); + } else { + return new DefaultCallNode(target); + } + } + @Override public VirtualFrame createVirtualFrame(PackedFrame caller, Arguments arguments, FrameDescriptor frameDescriptor) { return OptimizedCallTarget.createFrame(frameDescriptor, caller, arguments); diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNode.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNode.java Thu Feb 20 17:42:29 2014 +0100 @@ -0,0 +1,291 @@ +/* + * 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 com.oracle.truffle.api.*; +import com.oracle.truffle.api.frame.*; +import com.oracle.truffle.api.impl.*; +import com.oracle.truffle.api.nodes.*; + +/** + * Call target that is optimized by Graal upon surpassing a specific invocation threshold. + */ +abstract class OptimizedCallNode extends DefaultCallNode { + + protected int callCount; + + private OptimizedCallNode(OptimizedCallTarget target) { + super(target); + } + + @Override + public final boolean isInlinable() { + return true; + } + + @Override + public final boolean isSplittable() { + return getCallTarget().getRootNode().isSplittable(); + } + + @Override + public final OptimizedCallTarget getCallTarget() { + return (OptimizedCallTarget) super.getCallTarget(); + } + + public final int getCallCount() { + return callCount; + } + + public TruffleInliningProfile createInliningProfile() { + return new OptimizedCallNodeProfile(this); + } + + @Override + public OptimizedCallTarget getSplitCallTarget() { + return null; + } + + final OptimizedCallNode inlineImpl() { + if (getParent() == null) { + throw new IllegalStateException("CallNode must be adopted before it is split."); + } + return replace(new InlinedOptimizedCallNode(getCallTarget(), getSplitCallTarget(), getExecutedCallTarget().getRootNode(), callCount)); + } + + public final OptimizedCallTarget getExecutedCallTarget() { + return getSplitCallTarget() != null ? getSplitCallTarget() : getCallTarget(); + } + + public static OptimizedCallNode create(OptimizedCallTarget target) { + return new DefaultOptimizedCallNode(target); + } + + private static final class DefaultOptimizedCallNode extends OptimizedCallNode { + + private boolean splitTried; + + DefaultOptimizedCallNode(OptimizedCallTarget target) { + super(target); + } + + @Override + public Object call(PackedFrame caller, Arguments arguments) { + if (CompilerDirectives.inInterpreter()) { + callCount++; + if (!splitTried) { + return trySplit(caller, arguments); + } + } + return callTarget.call(caller, arguments); + } + + private Object trySplit(PackedFrame caller, Arguments arguments) { + int effectiveCallCount = callCount; + // we try splitting for the first two invocations + if (effectiveCallCount == 1 || effectiveCallCount == 2) { + if (isSplittable() && shouldSplit()) { + return splitImpl().call(caller, arguments); + } + } + if (effectiveCallCount >= 2) { + splitTried = true; + } + return callTarget.call(caller, arguments); + } + + @Override + public boolean isInlined() { + return false; + } + + @Override + public boolean split() { + if (!isSplittable()) { + // split is only allowed once and if the root node supports it + return false; + } + if (getParent() == null) { + throw new IllegalStateException("CallNode must be adopted before it is split."); + } + splitImpl(); + return true; + } + + private OptimizedCallNode splitImpl() { + RootNode splittedRoot = getCallTarget().getRootNode().split(); + OptimizedCallTarget splitCallTarget = (OptimizedCallTarget) Truffle.getRuntime().createCallTarget(splittedRoot); + OptimizedCallTarget.logSplit(getCallTarget(), splitCallTarget); + return replace(new SplitOptimizedCallNode(getCallTarget(), splitCallTarget, callCount)); + } + + private boolean shouldSplit() { + if (!TruffleCompilerOptions.TruffleSplittingEnabled.getValue()) { + return false; + } + RootNode targetRoot = getCallTarget().getRootNode(); + int nodeCount = NodeUtil.countNodes(targetRoot, null, true); + if (nodeCount >= TruffleCompilerOptions.TruffleSplittingMaxCalleeSize.getValue()) { + return false; + } + SplitScoreVisitor visitor = new SplitScoreVisitor(); + targetRoot.accept(visitor); + int genericNess = visitor.getSplitScore(); + return genericNess > 0; + } + + @Override + public void inline() { + inlineImpl(); + } + + @Override + public OptimizedCallTarget getSplitCallTarget() { + return null; + } + + } + + private static final class InlinedOptimizedCallNode extends OptimizedCallNode { + + private final RootNode inlinedRoot; + private final OptimizedCallTarget splittedTarget; + + public InlinedOptimizedCallNode(OptimizedCallTarget target, OptimizedCallTarget splittedTarget, RootNode inlinedRoot, int callCount) { + super(target); + this.inlinedRoot = inlinedRoot; + this.splittedTarget = splittedTarget; + this.callCount = callCount; + installParentInlinedCall(); + } + + @Override + public Object call(PackedFrame caller, Arguments arguments) { + if (CompilerDirectives.inInterpreter()) { + callCount++; + } + return inlinedRoot.execute(Truffle.getRuntime().createVirtualFrame(caller, arguments, inlinedRoot.getFrameDescriptor())); + } + + @Override + public void inline() { + } + + @Override + public boolean split() { + return false; + } + + @Override + public boolean isInlined() { + return true; + } + + @Override + public RootNode getInlinedRoot() { + return inlinedRoot; + } + + @Override + public OptimizedCallTarget getSplitCallTarget() { + return splittedTarget; + } + } + + private static class SplitOptimizedCallNode extends OptimizedCallNode { + + private final OptimizedCallTarget splittedTarget; + + public SplitOptimizedCallNode(OptimizedCallTarget target, OptimizedCallTarget splittedTarget, int callCount) { + super(target); + this.callCount = callCount; + this.splittedTarget = splittedTarget; + } + + @Override + public Object call(PackedFrame caller, Arguments arguments) { + if (CompilerDirectives.inInterpreter()) { + callCount++; + } + return splittedTarget.call(caller, arguments); + } + + @Override + public boolean isInlined() { + return false; + } + + @Override + public final boolean split() { + return false; + } + + @Override + public void inline() { + inlineImpl(); + } + + @Override + public final OptimizedCallTarget getSplitCallTarget() { + return splittedTarget; + } + + } + + private static final class SplitScoreVisitor implements NodeVisitor { + + private int splitScore = 0; + + public boolean visit(Node node) { + if (node instanceof OptimizedCallNode) { + OptimizedCallNode call = (OptimizedCallNode) node; + if (call.getInlinedRoot() != null) { + call.getInlinedRoot().accept(this); + } + } + splitScore += splitScore(node); + return true; + } + + public int getSplitScore() { + return splitScore; + } + + private static int splitScore(Node node) { + NodeInfo info = node.getClass().getAnnotation(NodeInfo.class); + if (info == null) { + return 0; + } + switch (info.kind()) { + case GENERIC: + return 3; + case POLYMORPHIC: + return 1; + default: + return 0; + } + } + + } + +} diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNodeProfile.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNodeProfile.java Thu Feb 20 17:42:29 2014 +0100 @@ -0,0 +1,170 @@ +/* + * 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 com.oracle.truffle.api.nodes.*; + +import static com.oracle.graal.truffle.TruffleCompilerOptions.*; + +public class OptimizedCallNodeProfile implements TruffleInliningProfile { + + private static final String REASON_RECURSION = "recursion"; + private static final String REASON_FREQUENCY_CUTOFF = "frequency < " + TruffleInliningMinFrequency.getValue(); + private static final String REASON_MAXIMUM_NODE_COUNT = "shallowTargetCount > " + TruffleInliningMaxCalleeSize.getValue(); + private static final String REASON_MAXIMUM_TOTAL_NODE_COUNT = "deepTargetCount + currentNodeCount > " + TruffleInliningMaxCallerSize.getValue(); + + private final OptimizedCallNode callNode; + + private final int targetDeepNodeCount; + private final int targetShallowNodeCount; + private final List compilationRoots; + private final double averageFrequency; + private final double score; + private String reason; + + public OptimizedCallNodeProfile(OptimizedCallNode callNode) { + this.callNode = callNode; + RootNode inlineRoot = callNode.getExecutedCallTarget().getRootNode(); + this.targetShallowNodeCount = NodeUtil.countNodes(inlineRoot, null, false); + this.targetDeepNodeCount = NodeUtil.countNodes(inlineRoot, null, true); + this.compilationRoots = findCompilationRoots(callNode); + this.averageFrequency = calculateAverageFrequency(compilationRoots); + this.score = calculateScore(); + } + + public OptimizedCallNode getCallNode() { + return callNode; + } + + public double getScore() { + return score; + } + + public double calculateScore() { + return averageFrequency / targetDeepNodeCount; + } + + public boolean isInliningAllowed() { + OptimizedCallTarget inlineTarget = callNode.getExecutedCallTarget(); + for (OptimizedCallTarget compilationRoot : compilationRoots) { + if (compilationRoot == inlineTarget) { + // recursive call found + reason = REASON_RECURSION; + return false; + } + } + + // frequency cut-off + if (averageFrequency < TruffleInliningMinFrequency.getValue() && targetDeepNodeCount > TruffleInliningTrivialSize.getValue()) { + reason = REASON_FREQUENCY_CUTOFF; + return false; + } + + if (targetShallowNodeCount > TruffleInliningMaxCalleeSize.getValue()) { + reason = REASON_MAXIMUM_NODE_COUNT; + return false; + } + + // The maximum total node count cannot be cached since it may change during inlining. + int currentNodeCount = calculateCurrentNodeCount(compilationRoots); + if (targetDeepNodeCount + currentNodeCount > TruffleInliningMaxCallerSize.getValue()) { + reason = REASON_MAXIMUM_TOTAL_NODE_COUNT; + return false; + } + + return true; + } + + private static int calculateCurrentNodeCount(List compilationRoots) { + int currentNodeCount = 0; + for (OptimizedCallTarget compilationRoot : compilationRoots) { + if (compilationRoot.getRootNode().getParentInlinedCalls().isEmpty()) { + currentNodeCount = Math.max(currentNodeCount, NodeUtil.countNodes(compilationRoot.getRootNode(), null, true)); + } + } + return currentNodeCount; + } + + @SuppressWarnings("unused") + private double calculateSimpleFrequency() { + RootNode root = callNode.getRootNode(); + OptimizedCallTarget target = ((OptimizedCallTarget) root.getCallTarget()); + + int totalCallCount = target.getCompilationProfile().getCallCount(); + List parentInlined = root.getParentInlinedCalls(); + for (CallNode node : parentInlined) { + int callCount = ((OptimizedCallNode) node).getCallCount(); + if (callCount >= 0) { + totalCallCount += callCount; + } + } + return callNode.getCallCount() / (double) totalCallCount; + } + + private double calculateAverageFrequency(List roots) { + int compilationRootCallCountSum = 0; + int compilationRootCount = 0; + for (OptimizedCallTarget compilationRoot : roots) { + if (compilationRoot.getRootNode().getParentInlinedCalls().isEmpty()) { + compilationRootCallCountSum += compilationRoot.getCompilationProfile().getCallCount(); + compilationRootCount++; + } + } + return (callNode.getCallCount() * compilationRootCount) / (double) compilationRootCallCountSum; + } + + private static List findCompilationRoots(Node call) { + RootNode root = call.getRootNode(); + if (root == null) { + return Collections.emptyList(); + } + List roots = new ArrayList<>(); + roots.add((OptimizedCallTarget) root.getCallTarget()); + for (CallNode callNode : root.getParentInlinedCalls()) { + roots.addAll(findCompilationRoots(callNode)); + } + return roots; + } + + public int compareTo(TruffleInliningProfile o) { + if (o instanceof OptimizedCallNodeProfile) { + return Double.compare(((OptimizedCallNodeProfile) o).getScore(), getScore()); + } + return 0; + } + + public Map getDebugProperties() { + Map properties = new LinkedHashMap<>(); + properties.put("shallowCount", targetShallowNodeCount); + properties.put("deepCount", targetDeepNodeCount); + properties.put("currentCount", calculateCurrentNodeCount(compilationRoots)); + properties.put("score", score); + properties.put("frequency", averageFrequency); + properties.put("callCount", callNode.getCallCount()); + properties.put("reason", reason); + return properties; + } + +} diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java Thu Feb 20 17:42:29 2014 +0100 @@ -44,13 +44,13 @@ private InstalledCode installedCode; private Future installedCodeTask; + private boolean compilationEnabled; + private int callCount; + private final TruffleCompiler compiler; private final CompilationProfile compilationProfile; private final CompilationPolicy compilationPolicy; - private final TruffleInlining inlining; - private boolean compilationEnabled; - private int callCount; - private SpeculationLog speculationLog = new SpeculationLog(); + private final SpeculationLog speculationLog = new SpeculationLog(); OptimizedCallTarget(RootNode rootNode, TruffleCompiler compiler, int invokeCounter, int compilationThreshold, boolean compilationEnabled) { super(rootNode); @@ -67,8 +67,19 @@ if (TruffleCallTargetProfiling.getValue()) { registerCallTarget(this); } - this.inlining = new TruffleInliningImpl(); + } + @Override + public String toString() { + String superString = super.toString(); + if (installedCode != null) { + superString += " "; + } + return superString; + } + + public boolean isOptimized() { + return installedCode != null || installedCodeTask != null; } @CompilerDirectives.SlowPath @@ -107,26 +118,29 @@ } private Object compiledCodeInvalidated(PackedFrame caller, Arguments args) { - invalidate(); + invalidate("Compiled code invalidated"); return call(caller, args); } - private void invalidate() { + private void invalidate(String reason) { InstalledCode m = this.installedCode; if (m != null) { CompilerAsserts.neverPartOfCompilation(); installedCode = null; compilationProfile.reportInvalidated(); if (TraceTruffleCompilation.getValue()) { - OUT.printf("[truffle] invalidated %-48s %08x |InvalidationCount %2d |ReplaceCount %3d\n", getRootNode(), getRootNode().hashCode(), compilationProfile.getInvalidationCount(), - compilationProfile.getNodeReplaceCount()); + logOptimizedInvalidated(this, reason); } } + cancelInstalledTask(reason); + } + private void cancelInstalledTask(String reason) { Future task = this.installedCodeTask; if (task != null) { task.cancel(true); this.installedCodeTask = null; + logOptimizingCancelled(this, reason); compilationProfile.reportInvalidated(); } } @@ -134,29 +148,68 @@ private Object interpreterCall(PackedFrame caller, Arguments args) { CompilerAsserts.neverPartOfCompilation(); compilationProfile.reportInterpreterCall(); - if (compilationEnabled && shouldCompile()) { - if (isCompiling()) { - return waitForCompilation(caller, args); - } - boolean inlined = shouldInline() && inline(); - if (!inlined) { - compile(); + + if (compilationEnabled && compilationPolicy.shouldCompile(compilationProfile)) { + InstalledCode code = compile(); + if (code != null && code.isValid()) { + this.installedCode = code; + try { + return code.execute(this, caller, args); + } catch (InvalidInstalledCodeException ex) { + return compiledCodeInvalidated(caller, args); + } } } return executeHelper(caller, args); } - private boolean shouldCompile() { - return compilationPolicy.shouldCompile(compilationProfile); + public void performInlining() { + if (!TruffleCompilerOptions.TruffleFunctionInlining.getValue()) { + return; + } + PriorityQueue queue = new PriorityQueue<>(); + + // Used to avoid running in cycles or inline nodes in Truffle trees + // which do not suffice the tree property twice. + Set visitedCallNodes = new HashSet<>(); + + queueCallSitesForInlining(getRootNode(), visitedCallNodes, queue); + TruffleInliningProfile callSite = queue.poll(); + while (callSite != null) { + if (callSite.isInliningAllowed()) { + OptimizedCallNode callNode = callSite.getCallNode(); + logInlined(callSite); + RootNode inlinedRoot = callNode.inlineImpl().getInlinedRoot(); + assert inlinedRoot != null; + queueCallSitesForInlining(inlinedRoot, visitedCallNodes, queue); + } else { + logInliningFailed(callSite); + } + callSite = queue.poll(); + } } - private static boolean shouldInline() { - return TruffleFunctionInlining.getValue(); + private static void queueCallSitesForInlining(RootNode rootNode, final Set visitedCallSites, final PriorityQueue queue) { + rootNode.accept(new NodeVisitor() { + public boolean visit(Node node) { + if (node instanceof OptimizedCallNode) { + OptimizedCallNode call = ((OptimizedCallNode) node); + if (call.isInlinable() && !call.isInlined() && !visitedCallSites.contains(call)) { + queue.add(call.createInliningProfile()); + visitedCallSites.add(call); + } else if (call.getInlinedRoot() != null) { + call.getInlinedRoot().accept(this); + } + } + return true; + } + }); } private boolean isCompiling() { - if (installedCodeTask != null) { - if (installedCodeTask.isCancelled()) { + Future codeTask = this.installedCodeTask; + if (codeTask != null) { + if (codeTask.isCancelled()) { installedCodeTask = null; return false; } @@ -165,18 +218,21 @@ return false; } - public void compile() { - this.installedCodeTask = compiler.compile(this); - if (!TruffleBackgroundCompilation.getValue()) { - installedCode = receiveInstalledCode(); + public InstalledCode compile() { + if (isCompiling()) { + if (installedCodeTask.isDone()) { + return receiveInstalledCode(); + } + return null; + } else { + logOptimizing(this); + performInlining(); + this.installedCodeTask = compiler.compile(this); + if (!TruffleBackgroundCompilation.getValue()) { + return receiveInstalledCode(); + } } - } - - private Object waitForCompilation(PackedFrame caller, Arguments args) { - if (installedCodeTask.isDone()) { - installedCode = receiveInstalledCode(); - } - return executeHelper(caller, args); + return null; } private InstalledCode receiveInstalledCode() { @@ -199,19 +255,6 @@ } } - /** - * Forces inlining whether or not function inlining is enabled. - * - * @return true if an inlining was performed - */ - public boolean inline() { - boolean result = inlining.performInlining(this); - if (result) { - compilationProfile.reportInliningPerformed(inlining); - } - return result; - } - public Object executeHelper(PackedFrame caller, Arguments args) { VirtualFrame frame = createFrame(getRootNode().getFrameDescriptor(), caller, args); return getRootNode().execute(frame); @@ -227,15 +270,96 @@ } @Override - public void nodeReplaced() { + public void nodeReplaced(Node oldNode, Node newNode, String reason) { compilationProfile.reportNodeReplaced(); - invalidate(); + invalidate(reason); } public SpeculationLog getSpeculationLog() { return speculationLog; } + private static void logInliningFailed(TruffleInliningProfile callSite) { + if (TraceTruffleInliningDetails.getValue() || TraceTruffleCompilationDetails.getValue()) { + log(0, "inline failed", callSite.getCallNode().getExecutedCallTarget().toString(), callSite.getDebugProperties()); + } + } + + private static void logOptimizing(OptimizedCallTarget target) { + if (TraceTruffleInliningDetails.getValue() || TraceTruffleCompilationDetails.getValue()) { + log(0, "optimizing", target.toString(), null); + } + } + + private static void logOptimizedInvalidated(OptimizedCallTarget target, String reason) { + if (TraceTruffleInliningDetails.getValue() || TraceTruffleCompilationDetails.getValue()) { + Map properties = new LinkedHashMap<>(); + properties.put("Invalidation#", target.compilationProfile.getInvalidationCount()); + properties.put("Replace#", target.compilationProfile.getNodeReplaceCount()); + properties.put("Reason", reason); + log(0, "invalidated", target.toString(), properties); + } + } + + private static void logOptimizingCancelled(OptimizedCallTarget target, String reason) { + if (TraceTruffleInliningDetails.getValue() || TraceTruffleCompilationDetails.getValue()) { + Map properties = new LinkedHashMap<>(); + properties.put("Invalidation#", target.compilationProfile.getInvalidationCount()); + properties.put("Replace#", target.compilationProfile.getNodeReplaceCount()); + properties.put("Reason", reason); + log(0, "optimizing stop", target.toString(), properties); + } + } + + static void logOptimized(OptimizedCallTarget target, Map properties) { + if (TraceTruffleCompilationDetails.getValue() || TraceTruffleCompilation.getValue()) { + log(0, "optimizing done", target.toString(), properties); + } + } + + private static void logInlined(TruffleInliningProfile callSite) { + if (TraceTruffleInliningDetails.getValue() || TraceTruffleInlining.getValue()) { + log(0, "inline success", callSite.getCallNode().getExecutedCallTarget().toString(), callSite.getDebugProperties()); + } + } + + static void logSplit(@SuppressWarnings("unused") OptimizedCallTarget target, OptimizedCallTarget newTarget) { + if (TraceTruffleInliningDetails.getValue() || TraceTruffleInlining.getValue()) { + log(0, "split", newTarget.toString(), null); + } + } + + static void log(int indent, String msg, String details, Map properties) { + OUT.printf("[truffle] %-16s ", msg); + for (int i = 0; i < indent; i++) { + OUT.print(" "); + } + OUT.printf("%-" + (60 - indent) + "s", details); + if (properties != null) { + for (String property : properties.keySet()) { + Object value = properties.get(property); + if (value == null) { + continue; + } + OUT.print("|"); + OUT.print(property); + + StringBuilder propertyBuilder = new StringBuilder(); + if (value instanceof Integer) { + propertyBuilder.append(String.format("%6d", value)); + } else if (value instanceof Double) { + propertyBuilder.append(String.format("%8.2f", value)); + } else { + propertyBuilder.append(value); + } + + int length = Math.max(1, 20 - property.length()); + OUT.printf(" %" + length + "s ", propertyBuilder.toString()); + } + } + OUT.println(); + } + private static void printProfiling() { List sortedCallTargets = new ArrayList<>(OptimizedCallTarget.callTargets.keySet()); Collections.sort(sortedCallTargets, new Comparator() { @@ -248,7 +372,6 @@ int totalCallCount = 0; int totalInlinedCallSiteCount = 0; - int totalNotInlinedCallSiteCount = 0; int totalNodeCount = 0; int totalInvalidationCount = 0; @@ -259,21 +382,19 @@ continue; } - int notInlinedCallSiteCount = TruffleInliningImpl.getInlinableCallSites(callTarget, callTarget).size(); int nodeCount = NodeUtil.countNodes(callTarget.getRootNode(), null, true); int inlinedCallSiteCount = countInlinedNodes(callTarget.getRootNode()); String comment = callTarget.installedCode == null ? " int" : ""; comment += callTarget.compilationEnabled ? "" : " fail"; - OUT.printf("%-50s | %10d | %15d | %15d | %10d | %3d%s\n", callTarget.getRootNode(), callTarget.callCount, inlinedCallSiteCount, notInlinedCallSiteCount, nodeCount, + OUT.printf("%-50s | %10d | %15d | %10d | %3d%s\n", callTarget.getRootNode(), callTarget.callCount, inlinedCallSiteCount, nodeCount, callTarget.getCompilationProfile().getInvalidationCount(), comment); totalCallCount += callTarget.callCount; totalInlinedCallSiteCount += inlinedCallSiteCount; - totalNotInlinedCallSiteCount += notInlinedCallSiteCount; totalNodeCount += nodeCount; totalInvalidationCount += callTarget.getCompilationProfile().getInvalidationCount(); } - OUT.printf("%-50s | %10d | %15d | %15d | %10d | %3d\n", "Total", totalCallCount, totalInlinedCallSiteCount, totalNotInlinedCallSiteCount, totalNodeCount, totalInvalidationCount); + OUT.printf("%-50s | %10d | %15d | %10d | %3d\n", "Total", totalCallCount, totalInlinedCallSiteCount, totalNodeCount, totalInvalidationCount); } private static int countInlinedNodes(Node rootNode) { diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerImpl.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerImpl.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerImpl.java Thu Feb 20 17:42:29 2014 +0100 @@ -169,10 +169,18 @@ if (TraceTruffleCompilation.getValue()) { int nodeCountTruffle = NodeUtil.countNodes(compilable.getRootNode(), null, true); byte[] code = compiledMethod.getCode(); - OUT.printf("[truffle] optimized %-50s %08x |Tree %8d |Time %5.0f(%4.0f+%-4.0f)ms |Graph %5d/%5d |CodeSize %6d @ %s\n", compilable.getRootNode(), compilable.hashCode(), nodeCountTruffle, - (timeCompilationFinished - timeCompilationStarted) / 1e6, (timePartialEvaluationFinished - timeCompilationStarted) / 1e6, - (timeCompilationFinished - timePartialEvaluationFinished) / 1e6, nodeCountPartialEval, nodeCountLowered, code != null ? code.length : 0, - formatSourceSection(compilable.getRootNode().getSourceSection())); + Map properties = new LinkedHashMap<>(); + properties.put("", String.format("%8x", compilable.hashCode())); + properties.put("Nodes", nodeCountTruffle); + properties.put("Time", String.format("%5.0f(%4.0f+%-4.0f)ms", // + (timeCompilationFinished - timeCompilationStarted) / 1e6, // + (timePartialEvaluationFinished - timeCompilationStarted) / 1e6, // + (timeCompilationFinished - timePartialEvaluationFinished) / 1e6)); + properties.put("Nodes", String.format("%5d/%5d", nodeCountPartialEval, nodeCountLowered)); + properties.put("CodeSize", code != null ? code.length : 0); + properties.put("Source", formatSourceSection(compilable.getRootNode().getSourceSection())); + + OptimizedCallTarget.logOptimized(compilable, properties); } return compiledMethod; } @@ -206,7 +214,8 @@ private int indent(Node n) { if (n instanceof RootNode) { - CallNode inlinedParent = ((RootNode) n).getParentInlinedCall(); + List inlinedParents = ((RootNode) n).getParentInlinedCalls(); + CallNode inlinedParent = inlinedParents.isEmpty() ? null : inlinedParents.get(0); if (inlinedParent != null) { return indent(inlinedParent) + 1; } diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java Thu Feb 20 17:42:29 2014 +0100 @@ -68,6 +68,10 @@ @Option(help = "") public static final OptionValue TruffleInliningMinFrequency = new OptionValue<>(0.3); @Option(help = "") + public static final OptionValue TruffleSplittingEnabled = new OptionValue<>(true); + @Option(help = "") + public static final OptionValue TruffleSplittingMaxCalleeSize = new OptionValue<>(50); + @Option(help = "") public static final OptionValue TruffleUseTimeForCompilationDecision = new OptionValue<>(false); @Option(help = "") public static final OptionValue TruffleCompilationDecisionTime = new OptionValue<>(100); @@ -94,7 +98,7 @@ @Option(help = "") public static final OptionValue TruffleCompilationExceptionsAreFatal = new OptionValue<>(true); @Option(help = "") - public static final OptionValue TraceTruffleInlining = new OptionValue<>(true); + public static final OptionValue TraceTruffleInlining = new OptionValue<>(false); @Option(help = "") public static final OptionValue TraceTruffleInliningTree = new OptionValue<>(false); @Option(help = "") diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInlining.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInlining.java Thu Feb 20 17:42:18 2014 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,41 +0,0 @@ -/* - * 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; - -public interface TruffleInlining { - - /** Returns true if reprofiling is required else false. */ - boolean performInlining(OptimizedCallTarget callTarget); - - /** - * Returns the minimum number of invocations required until the next inlining can occur. Only - * used if {@link #performInlining(OptimizedCallTarget)} returned true. - */ - int getInvocationReprofileCount(); - - /** - * Returns the number of invocations or loop invocations required until the next inlining can - * occur. Only used if {@link #performInlining(OptimizedCallTarget)} returned true. - */ - int getReprofileCount(); -} diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningImpl.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningImpl.java Thu Feb 20 17:42:18 2014 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,275 +0,0 @@ -/* - * 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 static com.oracle.graal.truffle.TruffleCompilerOptions.*; - -import java.io.*; -import java.util.*; - -import com.oracle.graal.debug.*; -import com.oracle.truffle.api.*; -import com.oracle.truffle.api.nodes.*; -import com.oracle.truffle.api.nodes.CallNode.*; - -class TruffleInliningImpl implements TruffleInlining { - - private static final int MIN_INVOKES_AFTER_INLINING = 2; - - private static final PrintStream OUT = TTY.out().out(); - - public int getReprofileCount() { - return TruffleCompilerOptions.TruffleInliningReprofileCount.getValue(); - } - - public int getInvocationReprofileCount() { - return MIN_INVOKES_AFTER_INLINING; - } - - private static void refresh(InliningPolicy policy, List infos) { - for (InlinableCallSiteInfo info : infos) { - info.refresh(policy); - } - } - - @Override - public boolean performInlining(OptimizedCallTarget target) { - final InliningPolicy policy = new InliningPolicy(target); - if (!policy.continueInlining()) { - if (TraceTruffleInliningDetails.getValue()) { - List inlinableCallSites = getInlinableCallSites(policy, target); - if (!inlinableCallSites.isEmpty()) { - OUT.printf("[truffle] inlining hit caller size limit (%3d >= %3d).%3d remaining call sites in %s:\n", policy.callerNodeCount, TruffleInliningMaxCallerSize.getValue(), - inlinableCallSites.size(), target.getRootNode()); - InliningPolicy.sortByRelevance(inlinableCallSites); - printCallSiteInfo(policy, inlinableCallSites, ""); - } - } - return false; - } - - List inlinableCallSites = getInlinableCallSites(policy, target); - if (inlinableCallSites.isEmpty()) { - return false; - } - - InliningPolicy.sortByRelevance(inlinableCallSites); - - boolean inlined = false; - for (InlinableCallSiteInfo inlinableCallSite : inlinableCallSites) { - if (!inlinableCallSite.isWorth()) { - break; - } - if (inlinableCallSite.getCallNode().inline()) { - if (TraceTruffleInlining.getValue()) { - printCallSiteInfo(policy, inlinableCallSite, "inlined"); - } - inlined = true; - break; - } - } - - if (inlined) { - for (InlinableCallSiteInfo callSite : inlinableCallSites) { - CompilerCallView callView = callSite.getCallNode().getCompilerCallView(); - if (callView != null) { - callView.resetCallCount(); - } - } - } else { - if (TraceTruffleInliningDetails.getValue()) { - OUT.printf("[truffle] inlining stopped.%3d remaining call sites in %s:\n", inlinableCallSites.size(), target.getRootNode()); - printCallSiteInfo(policy, inlinableCallSites, ""); - } - } - - return inlined; - } - - private static void printCallSiteInfo(InliningPolicy policy, List inlinableCallSites, String msg) { - for (InlinableCallSiteInfo candidate : inlinableCallSites) { - printCallSiteInfo(policy, candidate, msg); - } - } - - private static void printCallSiteInfo(InliningPolicy policy, InlinableCallSiteInfo callSite, String msg) { - String calls = String.format("%4s/%4s", callSite.getCallCount(), policy.callerInvocationCount); - String nodes = String.format("%3s/%3s", callSite.getInlineNodeCount(), policy.callerNodeCount); - CallTarget inlined = callSite.getCallNode().getCallTarget(); - OUT.printf("[truffle] %-9s %-50s %08x |Tree %8s |Calls %6s %7.3f @ %s\n", msg, inlined, inlined.hashCode(), nodes, calls, policy.metric(callSite), callSite.getCallNode()); - } - - private static final class InliningPolicy { - - private final int callerNodeCount; - private final int callerInvocationCount; - - public InliningPolicy(OptimizedCallTarget caller) { - this.callerNodeCount = NodeUtil.countNodes(caller.getRootNode(), null, true); - this.callerInvocationCount = caller.getCompilationProfile().getOriginalInvokeCounter(); - } - - public boolean continueInlining() { - return callerNodeCount < TruffleInliningMaxCallerSize.getValue(); - } - - public boolean isWorthInlining(InlinableCallSiteInfo callSite) { - return callSite.getInlineNodeCount() <= TruffleInliningMaxCalleeSize.getValue() && callSite.getInlineNodeCount() + callerNodeCount <= TruffleInliningMaxCallerSize.getValue() && - callSite.getCallCount() > 0 && callSite.getRecursiveDepth() < TruffleInliningMaxRecursiveDepth.getValue() && - (frequency(callSite) >= TruffleInliningMinFrequency.getValue() || callSite.getInlineNodeCount() <= TruffleInliningTrivialSize.getValue()); - } - - public double metric(InlinableCallSiteInfo callSite) { - double cost = callSite.getInlineNodeCount(); - double metric = frequency(callSite) / cost; - return metric; - } - - private double frequency(InlinableCallSiteInfo callSite) { - return (double) callSite.getCallCount() / (double) callerInvocationCount; - } - - private static void sortByRelevance(List inlinableCallSites) { - Collections.sort(inlinableCallSites, new Comparator() { - - @Override - public int compare(InlinableCallSiteInfo cs1, InlinableCallSiteInfo cs2) { - boolean cs1Worth = cs1.isWorth(); - boolean cs2Worth = cs2.isWorth(); - if (cs1Worth && cs2Worth) { - return Double.compare(cs2.getScore(), cs1.getScore()); - } else if (cs1Worth ^ cs2Worth) { - return cs1Worth ? -1 : 1; - } - return 0; - } - }); - } - } - - private static final class InlinableCallSiteInfo { - - private final CallNode callNode; - private final int nodeCount; - private final int recursiveDepth; - - private int callCount; - private boolean worth; - private double score; - - @SuppressWarnings("unused") - public InlinableCallSiteInfo(InliningPolicy policy, CallNode callNode) { - assert callNode.isInlinable(); - this.callNode = callNode; - RootCallTarget target = (RootCallTarget) callNode.getCallTarget(); - - this.nodeCount = target.getRootNode().getInlineNodeCount(); - this.recursiveDepth = calculateRecursiveDepth(); - } - - public int getRecursiveDepth() { - return recursiveDepth; - } - - public void refresh(InliningPolicy policy) { - this.callCount = callNode.getCompilerCallView().getCallCount(); - this.worth = policy.isWorthInlining(this); - if (worth) { - this.score = policy.metric(this); - } - // TODO shall we refresh the node count as well? - } - - public boolean isWorth() { - return worth; - } - - public double getScore() { - return score; - } - - private int calculateRecursiveDepth() { - int depth = 0; - - Node parent = callNode.getParent(); - while (parent != null) { - if (parent instanceof RootNode) { - RootNode root = ((RootNode) parent); - if (root.getCallTarget() == callNode.getCallTarget()) { - depth++; - } - parent = root.getParentInlinedCall(); - } else { - parent = parent.getParent(); - } - } - return depth; - } - - public CallNode getCallNode() { - return callNode; - } - - public int getCallCount() { - return callCount; - } - - public int getInlineNodeCount() { - return nodeCount; - } - } - - private static List getInlinableCallSites(final InliningPolicy policy, final RootCallTarget target) { - final ArrayList inlinableCallSites = new ArrayList<>(); - target.getRootNode().accept(new NodeVisitor() { - - @Override - public boolean visit(Node node) { - if (node instanceof CallNode) { - CallNode callNode = (CallNode) node; - - if (!callNode.isInlined()) { - if (callNode.isInlinable()) { - CompilerCallView view = callNode.getCompilerCallView(); - InlinableCallSiteInfo info = (InlinableCallSiteInfo) view.load(); - if (info == null) { - info = new InlinableCallSiteInfo(policy, callNode); - view.store(info); - } - inlinableCallSites.add(info); - } - } else { - callNode.getInlinedRoot().accept(this); - } - } - return true; - } - }); - refresh(policy, inlinableCallSites); - return inlinableCallSites; - } - - static List getInlinableCallSites(final OptimizedCallTarget target, final RootCallTarget root) { - return getInlinableCallSites(new InliningPolicy(target), root); - } -} diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningProfile.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleInliningProfile.java Thu Feb 20 17:42:29 2014 +0100 @@ -0,0 +1,37 @@ +/* + * 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.*; + +public interface TruffleInliningProfile extends Comparable { + + OptimizedCallNode getCallNode(); + + boolean isInliningAllowed(); + + int compareTo(TruffleInliningProfile o); + + Map getDebugProperties(); + +} diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.api/src/com/oracle/truffle/api/ReplaceObserver.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/ReplaceObserver.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/ReplaceObserver.java Thu Feb 20 17:42:29 2014 +0100 @@ -24,10 +24,12 @@ */ package com.oracle.truffle.api; +import com.oracle.truffle.api.nodes.*; + /** * An observer that is notified whenever a child node is replaced. */ public interface ReplaceObserver { - void nodeReplaced(); + void nodeReplaced(Node oldNode, Node newNode, String reason); } diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.api/src/com/oracle/truffle/api/TruffleRuntime.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/TruffleRuntime.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/TruffleRuntime.java Thu Feb 20 17:42:29 2014 +0100 @@ -50,6 +50,8 @@ */ RootCallTarget createCallTarget(RootNode rootNode); + CallNode createCallNode(CallTarget target); + /** * Creates a new assumption object that can be checked and invalidated. * diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.api/src/com/oracle/truffle/api/impl/DefaultCallNode.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/impl/DefaultCallNode.java Thu Feb 20 17:42:29 2014 +0100 @@ -0,0 +1,80 @@ +/* + * Copyright (c) 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. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.truffle.api.impl; + +import com.oracle.truffle.api.*; +import com.oracle.truffle.api.frame.*; +import com.oracle.truffle.api.nodes.*; + +public class DefaultCallNode extends CallNode { + + public DefaultCallNode(CallTarget target) { + super(target); + } + + @Override + public Object call(PackedFrame caller, Arguments arguments) { + return getCallTarget().call(caller, arguments); + } + + @Override + public void inline() { + } + + @Override + public CallTarget getSplitCallTarget() { + return null; + } + + @Override + public boolean split() { + return false; + } + + @Override + public boolean isSplittable() { + return false; + } + + @Override + public boolean isInlinable() { + return false; + } + + @Override + public RootNode getInlinedRoot() { + return null; + } + + @Override + public boolean isInlined() { + return false; + } + + @Override + public String toString() { + return getParent() != null ? getParent().toString() : super.toString(); + } +} diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.api/src/com/oracle/truffle/api/impl/DefaultTruffleRuntime.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/impl/DefaultTruffleRuntime.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/impl/DefaultTruffleRuntime.java Thu Feb 20 17:42:29 2014 +0100 @@ -53,6 +53,10 @@ return new DefaultCallTarget(rootNode); } + public CallNode createCallNode(CallTarget target) { + return new DefaultCallNode(target); + } + @Override public VirtualFrame createVirtualFrame(PackedFrame caller, Arguments arguments, FrameDescriptor frameDescriptor) { return new DefaultVirtualFrame(frameDescriptor, caller, arguments); diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/CallNode.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/CallNode.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/CallNode.java Thu Feb 20 17:42:29 2014 +0100 @@ -26,12 +26,13 @@ import com.oracle.truffle.api.*; import com.oracle.truffle.api.frame.*; -import com.oracle.truffle.api.impl.*; /** * This node represents a call to a static {@link CallTarget}. This node should be used whenever a * {@link CallTarget} is considered constant at a certain location in the tree. This enables the - * Truffle runtime to perform inlining or other optimizations for this call-site. + * Truffle runtime to perform inlining or other optimizations for this call-site. This class is + * intended to be implemented by truffle runtime implementors and not by guest languague + * implementors. * * @see #create(CallTarget) to create a CallNode instance. */ @@ -39,7 +40,7 @@ protected final CallTarget callTarget; - private CallNode(CallTarget callTarget) { + protected CallNode(CallTarget callTarget) { this.callTarget = callTarget; } @@ -59,12 +60,6 @@ */ public abstract Object call(PackedFrame caller, Arguments arguments); - /** - * Returns true if the {@link CallTarget} contained in this {@link CallNode} can be - * inlined. A {@link CallTarget} is considered inlinable if it was created using - * {@link TruffleRuntime#createCallTarget(RootNode)} and if the enclosed {@link RootNode} - * returns true for {@link RootNode#isInlinable()}. - */ public abstract boolean isInlinable(); /** @@ -72,209 +67,30 @@ */ public abstract boolean isInlined(); - /** - * Enforces an inlining optimization on this {@link CallNode} instance. If not performed - * manually the Truffle runtime may perform inlining using an heuristic to optimize the - * performance of the execution. It is recommended to implement an version of - * {@link RootNode#inline()} that adapts the inlining for possible guest language specific - * behavior. If the this {@link CallNode} is not inlinable or is already inlined - * false is returned. - * - * @return true if the inlining operation was successful. - */ - public abstract boolean inline(); + public abstract void inline(); + + public abstract boolean isSplittable(); - /** - * Returns the inlined root node if the call node was inlined. If the {@link CallNode} was not - * inlined null is returned. - * - * @return the inlined root node returned by {@link RootNode#inline()} - */ - public RootNode getInlinedRoot() { - return null; - } + public abstract boolean split(); + + public abstract CallTarget getSplitCallTarget(); + + public abstract RootNode getInlinedRoot(); /** * Creates a new {@link CallNode} using a {@link CallTarget}. * * @param target the {@link CallTarget} to call * @return a call node that calls the provided target - */ - public static CallNode create(CallTarget target) { - if (isInlinable(target)) { - return new InlinableCallNode((RootCallTarget) target); - } else { - return new DefaultCallNode(target); - } - } - - /** - * Warning: this is internal API and may change without notice. - */ - public interface CompilerCallView { - - int getCallCount(); - - void resetCallCount(); - - void store(Object value); - - Object load(); - } - - /** - * Warning: this is internal API and may change without notice. + * @deprecated use {@link TruffleRuntime#createCallNode(CallTarget)} instead */ - public CompilerCallView getCompilerCallView() { - return null; - } - - private static boolean isInlinable(CallTarget callTarget) { - if (callTarget instanceof RootCallTarget) { - return (((RootCallTarget) callTarget).getRootNode()).isInlinable(); - } - return false; - } - - @Override - public String toString() { - return getParent() != null ? getParent().toString() : super.toString(); - } - - static final class DefaultCallNode extends CallNode { - - public DefaultCallNode(CallTarget target) { - super(target); - } - - @Override - public Object call(PackedFrame caller, Arguments arguments) { - return callTarget.call(caller, arguments); - } - - @Override - public boolean inline() { - return false; - } - - @Override - public boolean isInlinable() { - return false; - } - - @Override - public boolean isInlined() { - return false; - } - + @Deprecated + public static CallNode create(CallTarget target) { + return Truffle.getRuntime().createCallNode(target); } - static final class InlinableCallNode extends CallNode implements CompilerCallView { - - private int callCount; - - public InlinableCallNode(RootCallTarget target) { - super(target); - } - - @Override - public Object call(PackedFrame parentFrame, Arguments arguments) { - if (CompilerDirectives.inInterpreter()) { - callCount++; - } - return callTarget.call(parentFrame, arguments); - } - - @Override - public boolean inline() { - DefaultCallTarget defaultTarget = (DefaultCallTarget) getCallTarget(); - RootNode originalRootNode = defaultTarget.getRootNode(); - if (originalRootNode.isInlinable()) { - RootNode inlinedRootNode = defaultTarget.getRootNode().inline(); - inlinedRootNode.setCallTarget(callTarget); - inlinedRootNode.setParentInlinedCall(this); - replace(new InlinedCallNode(defaultTarget, inlinedRootNode)); - return true; - } - return false; - } - - @Override - public boolean isInlined() { - return false; - } - - @Override - public boolean isInlinable() { - return true; - } - - @Override - public CompilerCallView getCompilerCallView() { - return this; - } - - /* Truffle internal API. */ - public int getCallCount() { - return callCount; - } - - /* Truffle internal API. */ - public void resetCallCount() { - callCount = 0; - } - - private Object storedCompilerInfo; - - public void store(Object value) { - this.storedCompilerInfo = value; - } - - public Object load() { - return storedCompilerInfo; - } - - } - - static final class InlinedCallNode extends CallNode { - - private final RootNode inlinedRoot; - - public InlinedCallNode(DefaultCallTarget callTarget, RootNode inlinedRoot) { - super(callTarget); - this.inlinedRoot = inlinedRoot; - } - - @Override - public Object call(PackedFrame caller, Arguments arguments) { - return inlinedRoot.execute(Truffle.getRuntime().createVirtualFrame(caller, arguments, inlinedRoot.getFrameDescriptor())); - } - - @Override - public InlinedCallNode copy() { - return new InlinedCallNode((DefaultCallTarget) getCallTarget(), NodeUtil.cloneNode(inlinedRoot)); - } - - @Override - public RootNode getInlinedRoot() { - return inlinedRoot; - } - - @Override - public boolean inline() { - return false; - } - - @Override - public boolean isInlinable() { - return true; - } - - @Override - public boolean isInlined() { - return true; - } - + protected final void installParentInlinedCall() { + getInlinedRoot().addParentInlinedCall(this); } } diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java Thu Feb 20 17:42:29 2014 +0100 @@ -185,7 +185,7 @@ if (!NodeUtil.replaceChild(this.parent, this, newNode)) { fixupTree(); } - reportReplace(); + reportReplace(this, newNode, reason); return newNode; } @@ -245,11 +245,11 @@ return false; } - private void reportReplace() { - RootNode rootNode = NodeUtil.findOutermostRootNode(this); - if (rootNode != null) { - if (rootNode.getCallTarget() instanceof ReplaceObserver) { - ((ReplaceObserver) rootNode.getCallTarget()).nodeReplaced(); + private void reportReplace(Node oldNode, Node newNode, String reason) { + Collection targets = NodeUtil.findOutermostCallTargets(this); + for (CallTarget target : targets) { + if (target instanceof ReplaceObserver) { + ((ReplaceObserver) target).nodeReplaced(oldNode, newNode, reason); } } } @@ -395,7 +395,7 @@ * * @return the {@link RootNode} or {@code null} if there is none. */ - protected final RootNode getRootNode() { + public final RootNode getRootNode() { Node rootNode = this; while (rootNode.getParent() != null) { assert !(rootNode instanceof RootNode) : "root node must not have a parent"; diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java Thu Feb 20 17:42:29 2014 +0100 @@ -451,13 +451,28 @@ return null; } + public static List findOutermostCallTargets(Node node) { + RootNode root = node.getRootNode(); + if (root == null) { + return Collections.emptyList(); + } + List roots = new ArrayList<>(); + roots.add(root.getCallTarget()); + for (CallNode callNode : root.getParentInlinedCalls()) { + roots.addAll(findOutermostCallTargets(callNode)); + } + return roots; + } + /** * Returns the outermost not inlined {@link RootNode} which is a parent of this node. * - * @see RootNode#getParentInlinedCall() + * @see RootNode#getParentInlinedCalls() * @param node to search * @return the outermost {@link RootNode} + * @deprecated use {@link #findOutermostCallTargets(Node)} */ + @Deprecated public static RootNode findOutermostRootNode(Node node) { Node parent = node; while (parent != null) { diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/RootNode.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/RootNode.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/RootNode.java Thu Feb 20 17:42:29 2014 +0100 @@ -24,6 +24,8 @@ */ package com.oracle.truffle.api.nodes; +import java.util.*; + import com.oracle.truffle.api.*; import com.oracle.truffle.api.CompilerDirectives.*; import com.oracle.truffle.api.frame.*; @@ -42,7 +44,7 @@ * Internal field to keep reference to the inlined call node. The inlined parent should not be * the same as the Node parent to keep the same tree hierarchy if inlined vs not inlined. */ - @CompilationFinal private CallNode parentInlinedCall; + @CompilationFinal private List parentInlinedCalls = new ArrayList<>(); protected RootNode() { this(null, null); @@ -62,55 +64,38 @@ } /** - * Creates a copy of the current {@link RootNode} for use as inlined AST. The default - * implementation copies this {@link RootNode} and all its children recursively. It is - * recommended to override this method to provide an implementation that copies an uninitialized - * version of this AST. An uninitialized version of an AST was usually never executed which - * means that it has not yet collected any profiling feedback. Please note that changes in the - * behavior of this method might also require changes in {@link #getInlineNodeCount()}. - * - * @see RootNode#getInlineNodeCount() - * @see RootNode#isInlinable() - * - * @return the copied RootNode for inlining - * @throws UnsupportedOperationException if {@link #isInlinable()} returns false + * @deprecated Not required anymore. Do not use. */ + @Deprecated public RootNode inline() { if (!isInlinable()) { throw new UnsupportedOperationException("Inlining is not enabled."); } - return NodeUtil.cloneNode(this); + return split(); + } + + /** + * @deprecated Not required anymore. Do not use. + */ + @Deprecated + public int getInlineNodeCount() { + return 0; } /** - * Returns the number of nodes that would be returned if {@link #inline()} would get invoked. - * This node count may be used for the calculation in a smart inlining heuristic. - * - * @see RootNode#inline() - * @see RootNode#isInlinable() - * - * @return the number of nodes that will get inlined - * @throws UnsupportedOperationException if {@link #isInlinable()} returns false + * @deprecated Not required anymore. Do not use. */ - public int getInlineNodeCount() { - if (!isInlinable()) { - throw new UnsupportedOperationException("Inlining is not enabled."); - } - return NodeUtil.countNodes(this); + @Deprecated + public boolean isInlinable() { + return true; } - /** - * Returns true if this RootNode can be inlined. If this method returns true implementations of - * {@link #inline()} and {@link #getInlineNodeCount()} must be provided. Returns - * true by default. - * - * @see RootNode#inline() - * @see RootNode#getInlineNodeCount() - * - * @return true if this RootNode can be inlined - */ - public boolean isInlinable() { - return true; + public RootNode split() { + return NodeUtil.cloneNode(this); + } + + public boolean isSplittable() { + return false; } /** @@ -118,8 +103,11 @@ * heuristics can use the loop count to guide compilation and inlining. */ public void reportLoopCount(int count) { - if (getCallTarget() instanceof LoopCountReceiver) { - ((LoopCountReceiver) getCallTarget()).reportLoopCount(count); + List callTargets = NodeUtil.findOutermostCallTargets(this); + for (CallTarget target : callTargets) { + if (target instanceof LoopCountReceiver) { + ((LoopCountReceiver) target).reportLoopCount(count); + } } } @@ -144,18 +132,19 @@ } /* Internal API. Do not use. */ - void setParentInlinedCall(CallNode inlinedParent) { - this.parentInlinedCall = inlinedParent; + void addParentInlinedCall(CallNode inlinedParent) { + this.parentInlinedCalls.add(inlinedParent); + } + + public final List getParentInlinedCalls() { + return Collections.unmodifiableList(parentInlinedCalls); } /** - * Returns the {@link CallNode} that uses this {@link RootNode} for an inlined call. Returns - * null if this {@link RootNode} is not inlined into a caller. This method can be - * used to also traverse parent {@link CallTarget} that have been inlined into this call. - * - * @return the responsible {@link CallNode} for inlining. + * @deprecated use {@link #getParentInlinedCalls()} instead. */ + @Deprecated public final CallNode getParentInlinedCall() { - return parentInlinedCall; + return parentInlinedCalls.isEmpty() ? null : parentInlinedCalls.get(0); } } diff -r 25b86e465365 -r 14018434a59a graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/SLRootNode.java --- a/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/SLRootNode.java Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/SLRootNode.java Thu Feb 20 17:42:29 2014 +0100 @@ -62,18 +62,13 @@ } @Override - public RootNode inline() { - return new SLRootNode(getFrameDescriptor().shallowCopy(), NodeUtil.cloneNode(uninitializedBodyNode), name); + public boolean isSplittable() { + return true; } @Override - public int getInlineNodeCount() { - return NodeUtil.countNodes(uninitializedBodyNode); - } - - @Override - public boolean isInlinable() { - return true; + public RootNode split() { + return new SLRootNode(getFrameDescriptor().shallowCopy(), NodeUtil.cloneNode(uninitializedBodyNode), name); } @Override diff -r 25b86e465365 -r 14018434a59a 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 Thu Feb 20 17:42:18 2014 +0100 +++ b/graal/com.oracle.truffle.sl/src/com/oracle/truffle/sl/nodes/call/SLDirectDispatchNode.java Thu Feb 20 17:42:29 2014 +0100 @@ -53,7 +53,7 @@ protected SLDirectDispatchNode(SLAbstractDispatchNode next, SLFunction cachedFunction) { this.cachedFunction = cachedFunction; - this.callCachedTargetNode = adoptChild(CallNode.create(cachedFunction.getCallTarget())); + this.callCachedTargetNode = adoptChild(Truffle.getRuntime().createCallNode(cachedFunction.getCallTarget())); this.cachedTargetStable = cachedFunction.getCallTargetStable(); this.nextNode = adoptChild(next); }