Mercurial > hg > graal-compiler
changeset 7391:36dafe48bc38
added relevance-based inlining
line wrap: on
line diff
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotMethodData.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotMethodData.java Wed Jan 16 09:05:48 2013 +0100 @@ -379,6 +379,7 @@ Arrays.sort(ptypes); double notRecordedTypeProbability = entries < config.typeProfileWidth ? 0.0 : Math.min(1.0, Math.max(0.0, 1.0 - totalProbability)); + assert notRecordedTypeProbability == 0 || entries == config.typeProfileWidth; return new JavaTypeProfile(notRecordedTypeProbability, ptypes); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedNode.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedNode.java Wed Jan 16 09:05:48 2013 +0100 @@ -42,6 +42,7 @@ public void setProbability(double probability) { this.probability = probability; + assert !Double.isNaN(probability); } protected void copyInto(FixedNode newNode) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/Invoke.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/Invoke.java Wed Jan 16 09:05:48 2013 +0100 @@ -57,6 +57,10 @@ void setProbability(double value); + double inliningRelevance(); + + void setInliningRelevance(double value); + boolean useForInlining(); void setUseForInlining(boolean value);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Wed Jan 16 09:05:48 2013 +0100 @@ -42,6 +42,7 @@ private boolean polymorphic; private boolean useForInlining; private final long leafGraphId; + private double inliningRelevance; /** * Constructs a new Invoke instruction. @@ -56,6 +57,7 @@ this.leafGraphId = leafGraphId; this.polymorphic = false; this.useForInlining = true; + this.inliningRelevance = Double.NaN; } @Override @@ -88,6 +90,16 @@ } @Override + public double inliningRelevance() { + return inliningRelevance; + } + + @Override + public void setInliningRelevance(double value) { + inliningRelevance = value; + } + + @Override public long leafGraphId() { return leafGraphId; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Wed Jan 16 09:05:48 2013 +0100 @@ -41,6 +41,7 @@ private boolean polymorphic; private boolean useForInlining; private final long leafGraphId; + private double inliningRelevance; public InvokeWithExceptionNode(CallTargetNode callTarget, DispatchBeginNode exceptionEdge, int bci, long leafGraphId) { super(callTarget.returnStamp()); @@ -50,6 +51,7 @@ this.leafGraphId = leafGraphId; this.polymorphic = false; this.useForInlining = true; + this.inliningRelevance = Double.NaN; } public DispatchBeginNode exceptionEdge() { @@ -99,6 +101,16 @@ } @Override + public double inliningRelevance() { + return inliningRelevance; + } + + @Override + public void setInliningRelevance(double value) { + inliningRelevance = value; + } + + @Override public long leafGraphId() { return leafGraphId; }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java Wed Jan 16 09:05:48 2013 +0100 @@ -65,6 +65,8 @@ } } } + + new ComputeInliningRelevanceIterator(graph).apply(); } private void correctLoopFrequencies(Loop loop, double parentFrequency, BitSet visitedBlocks) { @@ -366,4 +368,74 @@ return probability; } } + + private static class ComputeInliningRelevanceIterator extends ScopedPostOrderNodeIterator { + private final HashMap<FixedNode, Double> lowestPathProbabilities; + private double currentProbability; + + public ComputeInliningRelevanceIterator(StructuredGraph graph) { + super(graph); + this.lowestPathProbabilities = computeLowestPathProbabilities(graph); + } + + @Override + protected void initializeScope() { + currentProbability = lowestPathProbabilities.get(currentScope); + } + + @Override + protected void invoke(Invoke invoke) { + assert !Double.isNaN(invoke.probability()); + invoke.setInliningRelevance(invoke.probability() / currentProbability); + } + + private HashMap<FixedNode, Double> computeLowestPathProbabilities(StructuredGraph graph) { + HashMap<FixedNode, Double> result = new HashMap<>(); + Deque<FixedNode> scopes = getScopes(graph); + + while (!scopes.isEmpty()) { + FixedNode scopeBegin = scopes.pop(); + double probability = computeLowestPathProbability(scopeBegin); + result.put(scopeBegin, probability); + } + + return result; + } + + private static double computeLowestPathProbability(FixedNode scopeStart) { + double minPathProbability = scopeStart.probability(); + Node current = scopeStart; + + while (current != null) { + if (current instanceof ControlSplitNode) { + ControlSplitNode controlSplit = (ControlSplitNode) current; + current = getMaxProbabilitySux(controlSplit); + if (((FixedNode) current).probability() < minPathProbability) { + minPathProbability = ((FixedNode) current).probability(); + } + } else { + assert current.successors().count() <= 1; + current = current.successors().first(); + } + } + + return minPathProbability; + } + + private static Node getMaxProbabilitySux(ControlSplitNode controlSplit) { + Node maxSux = null; + double maxProbability = 0.0; + + // TODO: process recursively if we have multiple successors with same probability + for (Node sux: controlSplit.successors()) { + double probability = controlSplit.probability((BeginNode) sux); + if (probability > maxProbability) { + maxProbability = probability; + maxSux = sux; + } + } + + return maxSux; + } + } }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Wed Jan 16 09:05:48 2013 +0100 @@ -78,6 +78,7 @@ while (inliningPolicy.continueInlining(graph)) { final InlineInfo candidate = inliningPolicy.next(); + if (candidate != null) { boolean isWorthInlining = inliningPolicy.isWorthInlining(candidate); @@ -146,7 +147,8 @@ } private abstract static class AbstractInliningDecision implements InliningDecision { - public static boolean decideSizeBasedInlining(InlineInfo info, double maxSize) { + protected static boolean decideSizeBasedInlining(InlineInfo info, double maxSize) { + assert !Double.isNaN(info.weight()) && !Double.isNaN(maxSize); boolean success = info.weight() <= maxSize; if (GraalOptions.Debug) { String formatterString = success ? "(size %f <= %f)" : "(too large %f > %f)"; @@ -155,13 +157,21 @@ return success; } - public static boolean checkCompiledCodeSize(InlineInfo info) { + protected static boolean checkCompiledCodeSize(InlineInfo info) { if (GraalOptions.SmallCompiledCodeSize >= 0 && info.compiledCodeSize() > GraalOptions.SmallCompiledCodeSize) { InliningUtil.logNotInlinedMethod(info, "(CompiledCodeSize %d > %d)", info.compiledCodeSize(), GraalOptions.SmallCompiledCodeSize); return false; } return true; } + + protected static double getRelevance(Invoke invoke) { + if (GraalOptions.UseRelevanceBasedInlining) { + return invoke.inliningRelevance(); + } else { + return invoke.probability(); + } + } } private static class C1StaticSizeBasedInliningDecision extends AbstractInliningDecision { @@ -180,7 +190,7 @@ return false; } - double inlineWeight = Math.min(GraalOptions.ProbabilityCapForInlining, info.invoke().probability()); + double inlineWeight = Math.min(GraalOptions.RatioCapForInlining, getRelevance(info.invoke())); double maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * GraalOptions.MaximumInlineSize * inlineWeight; maxSize = Math.max(GraalOptions.MaximumTrivialSize, maxSize); @@ -196,7 +206,8 @@ return false; } - double inlineBoost = Math.min(GraalOptions.ProbabilityCapForInlining, info.invoke().probability()) + Math.log10(Math.max(1, info.invoke().probability() - GraalOptions.ProbabilityCapForInlining + 1)); + double relevance = getRelevance(info.invoke()); + double inlineBoost = Math.min(GraalOptions.RatioCapForInlining, relevance) + Math.log10(Math.max(1, relevance - GraalOptions.RatioCapForInlining + 1)); double maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * GraalOptions.MaximumInlineSize; maxSize = maxSize + maxSize * inlineBoost; maxSize = Math.min(GraalOptions.MaximumGreedyInlineSize, Math.max(GraalOptions.MaximumTrivialSize, maxSize)); @@ -223,7 +234,7 @@ maxSize += transferredValues * GraalOptions.InliningBonusPerTransferredValue; } - double inlineRatio = Math.min(GraalOptions.ProbabilityCapForInlining, info.invoke().probability()); + double inlineRatio = Math.min(GraalOptions.RatioCapForInlining, getRelevance(info.invoke())); maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * maxSize * inlineRatio; maxSize = Math.max(maxSize, GraalOptions.MaximumTrivialSize); @@ -237,7 +248,7 @@ assert GraalOptions.ProbabilityAnalysis; double maxSize = GraalOptions.MaximumGreedyInlineSize; - double inlineRatio = Math.min(GraalOptions.ProbabilityCapForInlining, info.invoke().probability()); + double inlineRatio = Math.min(GraalOptions.RatioCapForInlining, getRelevance(info.invoke())); maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * maxSize * inlineRatio; maxSize = Math.max(maxSize, GraalOptions.MaximumTrivialSize);
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Wed Jan 16 09:05:48 2013 +0100 @@ -84,7 +84,7 @@ private static boolean logNotInlinedMethodAndReturnFalse(Invoke invoke, String msg) { if (shouldLogInliningDecision()) { - String methodString = invoke.callTarget() == null ? "callTarget=null" : invoke.callTarget().targetName(); + String methodString = invoke.toString() + (invoke.callTarget() == null ? " callTarget=null" : invoke.callTarget().targetName()); logInliningDecision(methodString, false, msg, new Object[0]); } return false; @@ -563,6 +563,7 @@ result.node().replaceFirstInput(result.callTarget(), callTarget); result.setUseForInlining(useForInlining); result.setProbability(probability); + result.setInliningRelevance(invoke.inliningRelevance() * probability); Kind kind = invoke.node().kind(); if (kind != Kind.Void) { @@ -757,6 +758,7 @@ return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "inlining polymorphic calls is disabled (%d types)", ptypes.size()); } if (!optimisticOpts.inlineMegamorphicCalls() && notRecordedTypeProbability > 0) { + // due to filtering impossible types, notRecordedTypeProbability can be > 0 although the number of types is lower than what can be recorded in a type profile return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.size(), notRecordedTypeProbability * 100); } @@ -816,14 +818,14 @@ } private static boolean checkInvokeConditions(Invoke invoke) { - if (!(invoke.callTarget() instanceof MethodCallTargetNode)) { + if (invoke.predecessor() == null || !invoke.node().isAlive()) { + return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is dead code"); + } else if (!(invoke.callTarget() instanceof MethodCallTargetNode)) { return logNotInlinedMethodAndReturnFalse(invoke, "the invoke has already been lowered, or has been created as a low-level node"); } else if (invoke.methodCallTarget().targetMethod() == null) { return logNotInlinedMethodAndReturnFalse(invoke, "target method is null"); } else if (invoke.stateAfter() == null) { return logNotInlinedMethodAndReturnFalse(invoke, "the invoke has no after state"); - } else if (invoke.predecessor() == null || !invoke.node().isAlive()) { - return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is dead code"); } else if (!invoke.useForInlining()) { return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is marked to be not used for inlining"); } else if (invoke.methodCallTarget().receiver() != null && invoke.methodCallTarget().receiver().isConstant() && invoke.methodCallTarget().receiver().asConstant().isNull()) { @@ -974,6 +976,14 @@ } fixed.setProbability(newProbability); } + if (node instanceof Invoke) { + Invoke newInvoke = (Invoke) node; + double newRelevance = newInvoke.inliningRelevance() * invoke.inliningRelevance(); + if (GraalOptions.LimitInlinedProbability) { + newRelevance = Math.min(newRelevance, invoke.inliningRelevance()); + } + newInvoke.setInliningRelevance(newRelevance); + } } if (node instanceof FrameState) { FrameState frameState = (FrameState) node;
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Mon Jan 07 10:56:06 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Wed Jan 16 09:05:48 2013 +0100 @@ -53,6 +53,7 @@ public static int MaximumRecursiveInlining = 1; public static int SmallCompiledCodeSize = 2200; public static boolean LimitInlinedProbability = ____; + public static boolean UseRelevanceBasedInlining = true; // WeightBasedInliningPolicy (0) public static float InliningSizePenaltyExp = 20; public static float MaximumInlineWeight = 1.25f; @@ -66,7 +67,7 @@ // Common options for inlining policies 1 to 4 public static float NestedInliningSizeRatio = 1f; public static float BoostInliningForEscapeAnalysis = 2f; - public static float ProbabilityCapForInlining = 1f; + public static float RatioCapForInlining = 1f; // escape analysis settings public static boolean PartialEscapeAnalysis = true;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScopedPostOrderNodeIterator.java Wed Jan 16 09:05:48 2013 +0100 @@ -0,0 +1,175 @@ +/* + * 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.phases.graph; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; + +public abstract class ScopedPostOrderNodeIterator { + private final NodeBitMap processedNodes; + private final Deque<FixedNode> nodeQueue; + private final NodeBitMap queuedNodes; + private final Deque<FixedNode> scopes; + + protected FixedNode currentScope; + + public ScopedPostOrderNodeIterator(StructuredGraph graph) { + this.processedNodes = graph.createNodeBitMap(); + this.queuedNodes = graph.createNodeBitMap(); + this.nodeQueue = new ArrayDeque<>(); + this.scopes = getScopes(graph); + } + + public void apply() { + while (!scopes.isEmpty()) { + processedNodes.clearAll(); + queuedNodes.clearAll(); + this.currentScope = scopes.pop(); + initializeScope(); + processScope(); + } + } + + public void processScope() { + FixedNode current = currentScope; + do { + assert current.isAlive(); + processedNodes.mark(current); + + if (current instanceof Invoke) { + invoke((Invoke) current); + queueSuccessors(current); + current = nextQueuedNode(); + } else if (current instanceof LoopBeginNode) { + queueLoopBeginSuccessors((LoopBeginNode) current); + current = nextQueuedNode(); + } else if (current instanceof LoopExitNode) { + queueLoopExitSuccessors((LoopExitNode) current); + current = nextQueuedNode(); + } else if (current instanceof LoopEndNode) { + current = nextQueuedNode(); + } else if (current instanceof MergeNode) { + current = ((MergeNode) current).next(); + assert current != null; + } else if (current instanceof FixedWithNextNode) { + queueSuccessors(current); + current = nextQueuedNode(); + } else if (current instanceof EndNode) { + queueMerge((EndNode) current); + current = nextQueuedNode(); + } else if (current instanceof DeoptimizeNode) { + current = nextQueuedNode(); + } else if (current instanceof ReturnNode) { + current = nextQueuedNode(); + } else if (current instanceof UnwindNode) { + current = nextQueuedNode(); + } else if (current instanceof ControlSplitNode) { + queueSuccessors(current); + current = nextQueuedNode(); + } else { + assert false : current; + } + } while(current != null); + } + + protected void queueLoopBeginSuccessors(LoopBeginNode node) { + if (currentScope == node) { + queue(node.next()); + } else if (currentScope instanceof LoopBeginNode) { + // so we are currently processing loop A and found another loop B + // -> queue all loop exits of B except those that also exit loop A + for (LoopExitNode loopExit: node.loopExits()) { + if (!((LoopBeginNode) currentScope).loopExits().contains(loopExit)) { + queue(loopExit); + } + } + } else { + queue(node.loopExits()); + } + } + + protected void queueLoopExitSuccessors(LoopExitNode node) { + if (!(currentScope instanceof LoopBeginNode) || !((LoopBeginNode) currentScope).loopExits().contains(node)) { + queueSuccessors(node); + } + } + + protected Deque<FixedNode> getScopes(StructuredGraph graph) { + Deque<FixedNode> result = new ArrayDeque<>(); + result.push(graph.start()); + for (LoopBeginNode loopBegin: graph.getNodes(LoopBeginNode.class)) { + result.push(loopBegin); + } + return result; + } + + private void queueSuccessors(FixedNode x) { + queue(x.successors()); + } + + private void queue(NodeIterable<? extends Node> iter) { + for (Node node : iter) { + queue(node); + } + } + + private void queue(Node node) { + if (node != null && !queuedNodes.isMarked(node)) { + queuedNodes.mark(node); + nodeQueue.addFirst((FixedNode) node); + } + } + + private FixedNode nextQueuedNode() { + if (nodeQueue.isEmpty()) { + return null; + } + + FixedNode result = nodeQueue.removeFirst(); + assert queuedNodes.isMarked(result); + return result; + } + + private void queueMerge(EndNode end) { + MergeNode merge = end.merge(); + if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) { + queuedNodes.mark(merge); + nodeQueue.add(merge); + } + } + + private boolean visitedAllEnds(MergeNode merge) { + for (int i = 0; i < merge.forwardEndCount(); i++) { + if (!processedNodes.isMarked(merge.forwardEndAt(i))) { + return false; + } + } + return true; + } + + protected abstract void initializeScope(); + protected abstract void invoke(Invoke invoke); +}