# HG changeset patch # User Christian Humer # Date 1404493014 -7200 # Node ID 7f862f0ab1bca157693ce4327cbd2b07e149ec6e # Parent 51b74b041bb78772158ed4dc07ee6a0862b6bc39 Truffle: added new experimental splitting heuristic. diff -r 51b74b041bb7 -r 7f862f0ab1bc CHANGELOG.md --- a/CHANGELOG.md Fri Jul 04 18:56:54 2014 +0200 +++ b/CHANGELOG.md Fri Jul 04 18:56:54 2014 +0200 @@ -14,6 +14,12 @@ * `truffle.jar`: strip out build-time only dependency into a seperated JAR file (`truffle-dsl-processor.jar`) * New flag -G:+TraceTruffleCompilationAST to print the AST before compilation. * New experimental TypedObject interface added. +* Renamed flag -G:+TruffleSplittingEnabled to -G:+TruffleSplitting +* New flag -G:+TruffleSplittingNew to enable the experimental splitting mode based on function arguments. +* New flag -G:+TruffleSplittingTypedInstanceStamps to enable splitting for TypedObject instances. +* New flag -G:+TruffleSplittingClassInstanceStamps to enable splitting for Java object instances except TypedObject. +* New flag -G:TruffleSplittingStartCallCount=3 which sets the number of minimal calls until splitting is performed. +* New flag -G:-TruffleSplittingAggressive if enabled splits every function call. * ... ## Version 0.3 diff -r 51b74b041bb7 -r 7f862f0ab1bc graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultTruffleSplittingStrategy.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultTruffleSplittingStrategy.java Fri Jul 04 18:56:54 2014 +0200 @@ -0,0 +1,80 @@ +package com.oracle.graal.truffle; + +import com.oracle.truffle.api.nodes.*; +import com.oracle.truffle.api.nodes.NodeUtil.NodeCountFilter; + +public class DefaultTruffleSplittingStrategy implements TruffleSplittingStrategy { + + private final OptimizedDirectCallNode call; + + public DefaultTruffleSplittingStrategy(OptimizedDirectCallNode call) { + this.call = call; + } + + public void beforeCall(Object[] arguments) { + if (call.getCallCount() == 2 && !call.isInlined()) { + if (shouldSplit()) { + forceSplitting(); + } + } + } + + public void forceSplitting() { + if (call.isSplit()) { + return; + } + call.installSplitCallTarget(call.getCallTarget().split()); + } + + public void afterCall(Object returnValue) { + } + + private boolean shouldSplit() { + if (call.getSplitCallTarget() != null) { + return false; + } + if (!TruffleCompilerOptions.TruffleSplitting.getValue()) { + return false; + } + if (!call.isSplittable()) { + return false; + } + OptimizedCallTarget splitTarget = call.getCallTarget(); + int nodeCount = OptimizedCallUtils.countNonTrivialNodes(splitTarget, false); + if (nodeCount > TruffleCompilerOptions.TruffleSplittingMaxCalleeSize.getValue()) { + return false; + } + + // disable recursive splitting for now + OptimizedCallTarget root = (OptimizedCallTarget) call.getRootNode().getCallTarget(); + if (root == splitTarget || root.getSplitSource() == splitTarget) { + // recursive call found + return false; + } + + // max one child call and callCount > 2 and kind of small number of nodes + if (isMaxSingleCall(call)) { + return true; + } + return countPolymorphic(call) >= 1; + } + + private static boolean isMaxSingleCall(OptimizedDirectCallNode call) { + return NodeUtil.countNodes(call.getCurrentCallTarget().getRootNode(), new NodeCountFilter() { + public boolean isCounted(Node node) { + return node instanceof DirectCallNode; + } + }) <= 1; + } + + private static int countPolymorphic(OptimizedDirectCallNode call) { + return NodeUtil.countNodes(call.getCurrentCallTarget().getRootNode(), new NodeCountFilter() { + public boolean isCounted(Node node) { + NodeCost cost = node.getCost(); + boolean polymorphic = cost == NodeCost.POLYMORPHIC || cost == NodeCost.MEGAMORPHIC; + return polymorphic; + } + }); + } + +} diff -r 51b74b041bb7 -r 7f862f0ab1bc graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultTruffleSplittingStrategyNew.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/DefaultTruffleSplittingStrategyNew.java Fri Jul 04 18:56:54 2014 +0200 @@ -0,0 +1,179 @@ +package com.oracle.graal.truffle; + +import java.util.*; + +import com.oracle.truffle.api.*; +import com.oracle.truffle.api.nodes.*; +import com.oracle.truffle.api.nodes.NodeUtil.*; + +public class DefaultTruffleSplittingStrategyNew implements TruffleSplittingStrategy { + private static int splitChangeCount; + + private final int splitStart; + private final OptimizedDirectCallNode call; + private final boolean splittingEnabled; + private boolean splittingForced; + private TruffleStamp argumentStamp; + + public DefaultTruffleSplittingStrategyNew(OptimizedDirectCallNode call) { + this.call = call; + this.splitStart = TruffleCompilerOptions.TruffleSplittingStartCallCount.getValue(); + this.splittingEnabled = isSplittingEnabled(); + this.argumentStamp = DefaultTruffleStamp.getInstance(); + if (TruffleCompilerOptions.TruffleSplittingAggressive.getValue()) { + splittingForced = true; + } + } + + private boolean isSplittingEnabled() { + if (!TruffleCompilerOptions.TruffleSplitting.getValue()) { + return false; + } + if (!call.isSplittable()) { + return false; + } + if (TruffleCompilerOptions.TruffleSplittingAggressive.getValue()) { + return true; + } + int size = OptimizedCallUtils.countNonTrivialNodes(call.getCallTarget(), false); + if (size > TruffleCompilerOptions.TruffleSplittingMaxCalleeSize.getValue()) { + return false; + } + return true; + } + + public void forceSplitting() { + splittingForced = true; + } + + public void beforeCall(Object[] arguments) { + newSplitting(arguments); + } + + public void afterCall(Object returnValue) { + } + + private void newSplitting(Object[] arguments) { + CompilerAsserts.neverPartOfCompilation(); + OptimizedCallTarget currentTarget = call.getCurrentCallTarget(); + + if (splittingForced) { + if (!call.isSplit()) { + call.installSplitCallTarget(currentTarget.split()); + } + return; + } + + TruffleStamp oldStamp = argumentStamp; + TruffleStamp newStamp = oldStamp; + if (!oldStamp.isCompatible(arguments)) { + newStamp = oldStamp.joinValue(arguments); + assert newStamp != oldStamp; + } + + int calls = call.getCallCount(); + + if (oldStamp != newStamp || calls == splitStart || !call.getCurrentCallTarget().getArgumentStamp().equals(newStamp)) { + currentTarget = runSplitIteration(oldStamp, newStamp, calls); + currentTarget.mergeArgumentStamp(newStamp); + argumentStamp = newStamp; + assert call.getCurrentCallTarget().getArgumentStamp().equals(newStamp); + } + } + + private OptimizedCallTarget runSplitIteration(TruffleStamp oldProfile, TruffleStamp newProfile, int calls) { + OptimizedCallTarget currentTarget = call.getCurrentCallTarget(); + if (!splittingEnabled || calls < splitStart) { + return currentTarget; + } + + OptimizedCallTarget target = call.getCallTarget(); + Map profiles = target.getSplitVersions(); + OptimizedCallTarget newTarget = currentTarget; + + boolean split = false; + if (!currentTarget.getArgumentStamp().equals(newProfile)) { + if (target.getArgumentStamp().equals(newProfile)) { + // the original target is compatible again. + // -> we can use the original call target. + newTarget = target; + } else if (currentTarget.getKnownCallSiteCount() == 1 && currentTarget.getArgumentStamp().equals(oldProfile)) { + // we are the only caller + the profile is not polluted by other call sites + // -> reuse the currentTarget but update the profile if necessary + newTarget = currentTarget; + if (currentTarget.getSplitSource() != null) { + profiles.remove(oldProfile); + profiles.put(newProfile, newTarget); + } + } else { + newTarget = profiles.get(newProfile); + if (newTarget == null) { + // in case no compatible target was found we need to split + newTarget = target.split(); + profiles.put(newProfile, newTarget); + split = true; + } + } + } + + call.installSplitCallTarget(newTarget); + + if (split && TruffleCompilerOptions.TraceTruffleSplitting.getValue()) { + traceSplit(currentTarget.getSplitSource() != null ? oldProfile : currentTarget.getArgumentStamp(), newProfile); + } + + cleanup(currentTarget); + return newTarget; + } + + private void traceSplit(TruffleStamp oldStamp, TruffleStamp newStamp) { + OptimizedCallTarget callTarget = call.getCallTarget(); + Map splitTargets = callTarget.getSplitVersions(); + String label = String.format("split %3s-%-4s-%-4s ", splitChangeCount++, call.getCurrentCallTarget().getSplitIndex(), call.getCallCount()); + OptimizedCallTargetLog.log(0, label, callTarget.toString(), callTarget.getDebugProperties()); + logProfile(callTarget.getArgumentStamp(), callTarget, oldStamp, newStamp); + for (TruffleStamp profile : splitTargets.keySet()) { + logProfile(profile, splitTargets.get(profile), oldStamp, newStamp); + } + } + + private static void logProfile(TruffleStamp stamp, OptimizedCallTarget target, TruffleStamp oldStamp, TruffleStamp newStamp) { + String id = String.format("@%8h %s", target.hashCode(), target.getSplitSource() == null ? "orig." : "split"); + String plusMinus = stamp.equals(newStamp) ? "+ " : (stamp.equals(oldStamp) ? "- " : ""); + System.out.printf("%16s%-20sCallers: %3d, Nodes:%10s %s%n", plusMinus, id, target.getKnownCallSiteCount(), // + String.format("%d (%d/%d)", count(target, NodeCost.MONOMORPHIC), count(target, NodeCost.POLYMORPHIC), count(target, NodeCost.MEGAMORPHIC)),// + stamp); + } + + private static int count(OptimizedCallTarget target, final NodeCost otherCost) { + return NodeUtil.countNodes(target.getRootNode(), new NodeCountFilter() { + public boolean isCounted(Node node) { + return node.getCost() == otherCost; + } + }); + } + + private static void cleanup(OptimizedCallTarget currentTarget) { + if (currentTarget.getKnownCallSiteCount() == 0 && currentTarget.getSplitSource() != null) { + OptimizedCallTarget removed = currentTarget.getSplitSource().getSplitVersions().remove(currentTarget.getArgumentStamp()); + if (removed != null) { + disposeTarget(removed); + } + } + } + + private static void disposeTarget(OptimizedCallTarget removed) { + removed.getRootNode().accept(new NodeVisitor() { + public boolean visit(Node node) { + if (node instanceof OptimizedDirectCallNode) { + OptimizedDirectCallNode call = ((OptimizedDirectCallNode) node); + call.getCurrentCallTarget().decrementKnownCallSites(); + cleanup(call.getCurrentCallTarget()); + } + return true; + } + }); + + } + +} diff -r 51b74b041bb7 -r 7f862f0ab1bc 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 Fri Jul 04 18:56:54 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java Fri Jul 04 18:56:54 2014 +0200 @@ -58,6 +58,9 @@ private final RootNode rootNode; + private final Map splitVersions = new HashMap<>(); + private TruffleStamp argumentStamp = DefaultTruffleStamp.getInstance(); + public final RootNode getRootNode() { return rootNode; } @@ -76,6 +79,34 @@ } } + public final void mergeArgumentStamp(TruffleStamp p) { + this.argumentStamp = this.argumentStamp.join(p); + } + + public final TruffleStamp getArgumentStamp() { + return argumentStamp; + } + + private int splitIndex; + + public int getSplitIndex() { + return splitIndex; + } + + public OptimizedCallTarget split() { + if (!getRootNode().isSplittable()) { + return null; + } + OptimizedCallTarget splitTarget = (OptimizedCallTarget) Truffle.getRuntime().createCallTarget(getRootNode().split()); + splitTarget.splitSource = this; + splitTarget.splitIndex = splitIndex++; + return splitTarget; + } + + public Map getSplitVersions() { + return splitVersions; + } + public SpeculationLog getSpeculationLog() { return speculationLog; } @@ -133,6 +164,7 @@ logOptimizedInvalidated(this, oldNode, newNode, reason); } cancelInstalledTask(oldNode, newNode, reason); + invalidateInlining(); } public void invalidateInlining() { @@ -233,10 +265,10 @@ public String toString() { String superString = rootNode.toString(); if (isValid()) { - superString += " "; + superString += " "; } if (splitSource != null) { - superString += " "; + superString += " "; } return superString; } @@ -334,4 +366,5 @@ return properties; } + } diff -r 51b74b041bb7 -r 7f862f0ab1bc graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTargetLog.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTargetLog.java Fri Jul 04 18:56:54 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTargetLog.java Fri Jul 04 18:56:54 2014 +0200 @@ -88,7 +88,7 @@ Map properties = new LinkedHashMap<>(); addASTSizeProperty(callNode.getCurrentCallTarget(), properties); properties.putAll(callNode.getCurrentCallTarget().getDebugProperties()); - + properties.put("Stamp", callNode.getCurrentCallTarget().getArgumentStamp()); log((depth * 2), "call", callNode.getCurrentCallTarget().toString() + dispatched, properties); if (callNode.isInlined()) { diff -r 51b74b041bb7 -r 7f862f0ab1bc graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedDirectCallNode.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedDirectCallNode.java Fri Jul 04 18:56:54 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedDirectCallNode.java Fri Jul 04 18:56:54 2014 +0200 @@ -27,7 +27,6 @@ import com.oracle.truffle.api.frame.FrameInstance.FrameAccess; import com.oracle.truffle.api.frame.*; import com.oracle.truffle.api.nodes.*; -import com.oracle.truffle.api.nodes.NodeUtil.NodeCountFilter; /** * A call node with a constant {@link CallTarget} that can be optimized by Graal. @@ -35,23 +34,39 @@ public final class OptimizedDirectCallNode extends DirectCallNode implements MaterializedFrameNotify { private int callCount; - private boolean trySplit = true; private boolean inliningForced; @CompilationFinal private boolean inlined; @CompilationFinal private OptimizedCallTarget splitCallTarget; @CompilationFinal private FrameAccess outsideFrameAccess = FrameAccess.NONE; + private final TruffleSplittingStrategy splittingStrategy; + private OptimizedDirectCallNode(OptimizedCallTarget target) { super(target); + if (TruffleCompilerOptions.TruffleSplittingNew.getValue()) { + this.splittingStrategy = new DefaultTruffleSplittingStrategyNew(this); + } else { + this.splittingStrategy = new DefaultTruffleSplittingStrategy(this); + } } @Override public Object call(VirtualFrame frame, Object[] arguments) { if (CompilerDirectives.inInterpreter()) { - onInterpreterCall(); + onInterpreterCall(arguments); + } + Object result = callProxy(this, getCurrentCallTarget(), frame, arguments, inlined, true); + + if (CompilerDirectives.inInterpreter()) { + afterInterpreterCall(result); } - return callProxy(this, getCurrentCallTarget(), frame, arguments, inlined, true); + return result; + } + + private void afterInterpreterCall(Object result) { + splittingStrategy.afterCall(result); + propagateInliningInvalidations(); } public static Object callProxy(MaterializedFrameNotify notify, CallTarget callTarget, VirtualFrame frame, Object[] arguments, boolean inlined, boolean direct) { @@ -74,9 +89,8 @@ public void resetInlining() { CompilerAsserts.neverPartOfCompilation(); - if (inlined) { + if (inlined && !inliningForced) { inlined = false; - getCurrentCallTarget().invalidateInlining(); } } @@ -129,19 +143,42 @@ return splitCallTarget; } - private void onInterpreterCall() { - callCount++; - if (trySplit) { - if (callCount == 1) { - // on first call - getCurrentCallTarget().incrementKnownCallSites(); - } - if (callCount > 1 && !inlined) { - trySplit = false; - if (shouldSplit()) { - splitImpl(true); - } - } + private void onInterpreterCall(Object[] arguments) { + int calls = ++callCount; + if (calls == 1) { + getCurrentCallTarget().incrementKnownCallSites(); + } + splittingStrategy.beforeCall(arguments); + propagateInliningInvalidations(); + } + + /** Used by the splitting strategy to install new targets. */ + public void installSplitCallTarget(OptimizedCallTarget newTarget) { + CompilerAsserts.neverPartOfCompilation(); + + OptimizedCallTarget currentTarget = getCurrentCallTarget(); + if (currentTarget == newTarget) { + return; + } + + if (callCount >= 1) { + currentTarget.decrementKnownCallSites(); + } + newTarget.incrementKnownCallSites(); + + // dummy replace to report the split + replace(this, "Split call " + newTarget.toString()); + + if (newTarget.getSplitSource() == null) { + splitCallTarget = null; + } else { + splitCallTarget = newTarget; + } + } + + private void propagateInliningInvalidations() { + if (isInlined() && !getCurrentCallTarget().inliningPerformed) { + replace(this, "Propagate invalid inlining from " + getCurrentCallTarget().toString()); } } @@ -157,75 +194,11 @@ @Override public boolean split() { - splitImpl(false); + splittingStrategy.forceSplitting(); return true; } - private void splitImpl(boolean heuristic) { - CompilerAsserts.neverPartOfCompilation(); - - OptimizedCallTarget splitTarget = (OptimizedCallTarget) Truffle.getRuntime().createCallTarget(getCallTarget().getRootNode().split()); - splitTarget.setSplitSource(getCallTarget()); - if (heuristic) { - OptimizedCallTargetLog.logSplit(this, getCallTarget(), splitTarget); - } - if (callCount >= 1) { - getCallTarget().decrementKnownCallSites(); - splitTarget.incrementKnownCallSites(); - } - this.splitCallTarget = splitTarget; - } - - private boolean shouldSplit() { - if (splitCallTarget != null) { - return false; - } - if (!TruffleCompilerOptions.TruffleSplittingEnabled.getValue()) { - return false; - } - if (!isSplittable()) { - return false; - } - OptimizedCallTarget splitTarget = getCallTarget(); - int nodeCount = OptimizedCallUtils.countNonTrivialNodes(splitTarget, false); - if (nodeCount > TruffleCompilerOptions.TruffleSplittingMaxCalleeSize.getValue()) { - return false; - } - - // disable recursive splitting for now - OptimizedCallTarget root = (OptimizedCallTarget) getRootNode().getCallTarget(); - if (root == splitTarget || root.getSplitSource() == splitTarget) { - // recursive call found - return false; - } - - // max one child call and callCount > 2 and kind of small number of nodes - if (isMaxSingleCall()) { - return true; - } - return countPolymorphic() >= 1; - } - - private boolean isMaxSingleCall() { - return NodeUtil.countNodes(getCurrentCallTarget().getRootNode(), new NodeCountFilter() { - public boolean isCounted(Node node) { - return node instanceof DirectCallNode; - } - }) <= 1; - } - - private int countPolymorphic() { - return NodeUtil.countNodes(getCurrentCallTarget().getRootNode(), new NodeCountFilter() { - public boolean isCounted(Node node) { - NodeCost cost = node.getCost(); - boolean polymorphic = cost == NodeCost.POLYMORPHIC || cost == NodeCost.MEGAMORPHIC; - return polymorphic; - } - }); - } - public static OptimizedDirectCallNode create(OptimizedCallTarget target) { return new OptimizedDirectCallNode(target); } - } diff -r 51b74b041bb7 -r 7f862f0ab1bc 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 Fri Jul 04 18:56:54 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerOptions.java Fri Jul 04 18:56:54 2014 +0200 @@ -63,8 +63,22 @@ public static final OptionValue TruffleInliningMinFrequency = new OptionValue<>(0.3); @Option(help = "Allow inlining of less hot candidates if tree size is small") public static final OptionValue TruffleInliningTrivialSize = new OptionValue<>(10); + @Option(help = "Enable call target splitting") - public static final OptionValue TruffleSplittingEnabled = new OptionValue<>(true); + public static final OptionValue TruffleSplitting = new OptionValue<>(true); + @Option(help = "Experimental: Enable the new version of truffle splitting.") + public static final OptionValue TruffleSplittingNew = new OptionValue<>(false); + @Option(help = "Experimental. New splitting only: Whether or not splitting should be based instance comparisons of non TypedObjects") + public static final OptionValue TruffleSplittingClassInstanceStamps = new OptionValue<>(true); + @Option(help = "Experimental. New splitting only: Whether or not splitting should be based instance comparisons of TypedObjects") + public static final OptionValue TruffleSplittingTypeInstanceStamps = new OptionValue<>(true); + @Option(help = "Experimental. New splitting only: The number of calls until splitting is performed. ") + public static final OptionValue TruffleSplittingStartCallCount = new OptionValue<>(3); + @Option(help = "Experimental. New splitting only: Split everything aggressively. ") + public static final OptionValue TruffleSplittingAggressive = new OptionValue<>(false); + + + @Option(help = "Disable call target splitting if tree size exceeds this limit") public static final OptionValue TruffleSplittingMaxCalleeSize = new OptionValue<>(100); @Option(help = "Number of most recently used methods in truffle cache") diff -r 51b74b041bb7 -r 7f862f0ab1bc graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleSplittingStrategy.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleSplittingStrategy.java Fri Jul 04 18:56:54 2014 +0200 @@ -0,0 +1,11 @@ +package com.oracle.graal.truffle; + +public interface TruffleSplittingStrategy { + + void beforeCall(Object[] arguments); + + void afterCall(Object returnValue); + + void forceSplitting(); + +}