# HG changeset patch # User Christian Humer # Date 1394058805 -3600 # Node ID ca92db718c74232f0c0fbf635f5362f57fb6fb95 # Parent f157fabf6b3819b5ad3a0b4e285646d060dcede9 Truffle: refined split/inlining heuristics. diff -r f157fabf6b38 -r ca92db718c74 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNode.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNode.java Wed Mar 05 23:33:25 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNode.java Wed Mar 05 23:33:25 2014 +0100 @@ -61,7 +61,6 @@ @SuppressWarnings("unused") public void nodeReplaced(Node oldNode, Node newNode, String reason) { - } @Override @@ -88,38 +87,28 @@ private static final class DefaultOptimizedCallNode extends OptimizedCallNode { - private boolean splitTried; + private boolean trySplit = true; DefaultOptimizedCallNode(OptimizedCallTarget target) { super(target); + registerCallTarget(this); } @Override public Object call(PackedFrame caller, Arguments arguments) { if (CompilerDirectives.inInterpreter()) { callCount++; - if (!splitTried) { + if (trySplit && callCount > 1) { + trySplit = false; return trySplit(caller, arguments); } } return callTarget.call(caller, arguments); } - @Override - public void nodeReplaced(Node oldNode, Node newNode, String reason) { - - } - private Object trySplit(PackedFrame caller, Arguments arguments) { - int effectiveCallCount = callCount; - // we try splitting for the first two invocations - if (effectiveCallCount <= 3) { - if (isSplittable() && shouldSplit()) { - return splitImpl(true).call(caller, arguments); - } - if (effectiveCallCount == 3) { - splitTried = true; - } + if (shouldSplit()) { + return splitImpl(true).call(caller, arguments); } return callTarget.call(caller, arguments); } @@ -128,20 +117,35 @@ if (!TruffleCompilerOptions.TruffleSplittingEnabled.getValue()) { return false; } - + if (!isSplittable()) { + return false; + } int nodeCount = NodeUtil.countNodes(getCallTarget().getRootNode(), null, false); - - // max one child call and callCount > 2 and kind of small number of nodes - if (callCount > 2 && isMaxSingleCall()) { - if (nodeCount <= 100) { - return true; - } - } - if (nodeCount > TruffleCompilerOptions.TruffleSplittingMaxCalleeSize.getValue()) { return false; } - return countPolymorphic() > 1 || countGeneric() > 0; + +// // is the only call target -> do not split +// if (getCallTarget().getRootNode().getCachedCallNodes().size() == 1 && +// getCallTarget().getRootNode().getCachedCallNodes().contains(this)) { +// return false; +// } + + // max one child call and callCount > 2 and kind of small number of nodes + if (isMaxSingleCall()) { + return true; + } + return countPolymorphic() >= 1 || countGeneric() > 0; + } + + @Override + public void nodeReplaced(Node oldNode, Node newNode, String reason) { + trySplit = true; + } + + @Override + protected void notifyCallNodeAdded() { + trySplit = true; } private boolean isMaxSingleCall() { @@ -159,11 +163,11 @@ } private int countPolymorphic() { - return NodeUtil.countNodes(getCallTarget().getRootNode(), null, Kind.POLYMORPHIC, true); + return NodeUtil.countNodes(getCallTarget().getRootNode(), null, Kind.POLYMORPHIC, false); } private int countGeneric() { - return NodeUtil.countNodes(getCallTarget().getRootNode(), null, Kind.GENERIC, true); + return NodeUtil.countNodes(getCallTarget().getRootNode(), null, Kind.GENERIC, false); } @Override diff -r f157fabf6b38 -r ca92db718c74 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNodeProfile.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNodeProfile.java Wed Mar 05 23:33:25 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallNodeProfile.java Wed Mar 05 23:33:25 2014 +0100 @@ -52,12 +52,12 @@ this.targetShallowNodeCount = NodeUtil.countNodes(inlineRoot, null, false); this.targetDeepNodeCount = NodeUtil.countNodes(inlineRoot, null, true); this.compilationRoots = findCompilationRoots(callNode); - this.averageFrequency = calculateFrequency(compilationRoots); + this.averageFrequency = calculateFrequency(); this.score = calculateScore(); } - private double calculateFrequency(@SuppressWarnings("unused") List compilationRoots2) { - return calculateSimpleFrequency(); + private double calculateFrequency() { + return calculateAdvancedFrequency(); } public OptimizedCallNode getCallNode() { @@ -143,6 +143,50 @@ } + double calculateAdvancedFrequency() { + // get the call hierarchy from call target to the call node + final ArrayDeque callStack = new ArrayDeque<>(); + callTarget.getRootNode().accept(new NodeVisitor() { + private boolean found = false; + + public boolean visit(Node node) { + if (node == callNode) { + // found our call + callStack.push((OptimizedCallNode) node); + found = true; + return false; + } + + if (node instanceof OptimizedCallNode) { + OptimizedCallNode c = ((OptimizedCallNode) node); + if (c.isInlined()) { + if (!found) { + callStack.push(c); + } + c.getCurrentRootNode().accept(this); + if (!found) { + callStack.pop(); + } + } + } + return !found; + } + }); + + int parentCallCount = callTarget.getCompilationProfile().getCallCount(); + double frequency = 1.0d; + for (OptimizedCallNode c : callStack) { + int childCallCount = c.getCallCount(); + frequency *= childCallCount / (double) parentCallCount; + if (c.isInlined() || c.isSplit()) { + parentCallCount = childCallCount; + } else { + parentCallCount = c.getCurrentCallTarget().getCompilationProfile().getCallCount(); + } + } + return frequency; + } + double calculateSimpleFrequency() { return callNode.getCallCount() / (double) callTarget.getCompilationProfile().getCallCount(); } diff -r f157fabf6b38 -r ca92db718c74 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 Wed Mar 05 23:33:25 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java Wed Mar 05 23:33:25 2014 +0100 @@ -213,7 +213,7 @@ public boolean visit(Node node) { if (node instanceof OptimizedCallNode) { OptimizedCallNode call = ((OptimizedCallNode) node); - if (call.isInlinable() && !call.isInlined() && !visitedCallSites.contains(call)) { + if (!call.isInlined() && !visitedCallSites.contains(call)) { queue.add(call.createInliningProfile(target)); visitedCallSites.add(call); } diff -r f157fabf6b38 -r ca92db718c74 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 Wed Mar 05 23:33:25 2014 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java Wed Mar 05 23:33:25 2014 +0100 @@ -66,7 +66,7 @@ @Option(help = "Enable call target splitting") public static final OptionValue TruffleSplittingEnabled = new OptionValue<>(true); @Option(help = "Disable call target splitting if tree size exceeds this limit") - public static final OptionValue TruffleSplittingMaxCalleeSize = new OptionValue<>(50); + public static final OptionValue TruffleSplittingMaxCalleeSize = new OptionValue<>(100); @Option(help = "Number of most recently used methods in truffle cache") public static final OptionValue TruffleMaxCompilationCacheSize = new OptionValue<>(512); @Option(help = "Enable asynchronous truffle compilation in background thread") diff -r f157fabf6b38 -r ca92db718c74 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 Wed Mar 05 23:33:25 2014 +0100 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/CallNode.java Wed Mar 05 23:33:25 2014 +0100 @@ -111,13 +111,13 @@ oldRoot.removeCachedCallNode(oldCall); } - /* - * New call nodes are registered in the new target root node. - */ - CallNode newCall = (CallNode) newNode; - RootNode newRoot = newCall.getCurrentRootNode(); + registerCallTarget((CallNode) newNode); + } + + protected final void registerCallTarget(CallNode newNode) { + RootNode newRoot = newNode.getCurrentRootNode(); if (newRoot != null) { - newRoot.addCachedCallNode(newCall); + newRoot.addCachedCallNode(newNode); } }