Mercurial > hg > graal-jvmci-8
diff graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java @ 9699:9529ab567367
Drafted version of an inlining policy that uses the callee graph size as its metric.
author | Christian Haeubl <haeubl@ssw.jku.at> |
---|---|
date | Wed, 08 May 2013 16:31:59 +0200 |
parents | 8f01fe16e473 |
children | e538498d6eae |
line wrap: on
line diff
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Fri Apr 26 12:00:50 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Wed May 08 16:31:59 2013 +0200 @@ -22,7 +22,6 @@ */ package com.oracle.graal.phases.common; -import java.lang.reflect.*; import java.util.*; import java.util.concurrent.*; @@ -31,38 +30,30 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; import com.oracle.graal.phases.common.InliningUtil.InlineInfo; -import com.oracle.graal.phases.common.InliningUtil.InliningCallback; import com.oracle.graal.phases.common.InliningUtil.InliningPolicy; import com.oracle.graal.phases.graph.*; -public class InliningPhase extends Phase implements InliningCallback { +public class InliningPhase extends Phase { - /* - * - Detect method which only call another method with some parameters set to constants: void - * foo(a) -> void foo(a, b) -> void foo(a, b, c) ... These should not be taken into account when - * determining inlining depth. - honor the result of overrideInliningDecision(0, caller, - * invoke.bci, method, true); - */ + private static final HashMap<ResolvedJavaMethod, CompiledMethodInfo> compiledMethodInfo = new HashMap<>(); private final PhasePlan plan; - private final MetaAccessProvider runtime; - private final Assumptions assumptions; + private final Assumptions compilationAssumptions; private final Replacements replacements; private final GraphCache cache; private final InliningPolicy inliningPolicy; private final OptimisticOptimizations optimisticOpts; - private CustomCanonicalizer customCanonicalizer; + private final InliningData data; + private CustomCanonicalizer customCanonicalizer; private int inliningCount; - private int maxMethodPerInlining = Integer.MAX_VALUE; // Metrics @@ -73,18 +64,33 @@ public InliningPhase(MetaAccessProvider runtime, Map<Invoke, Double> hints, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) { - this(runtime, replacements, assumptions, cache, plan, createInliningPolicy(runtime, replacements, assumptions, optimisticOpts, hints), optimisticOpts); + this(runtime, replacements, assumptions, cache, plan, optimisticOpts, hints); + } + + public InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) { + this(runtime, replacements, assumptions, cache, plan, optimisticOpts, null); } - public InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, InliningPolicy inliningPolicy, - OptimisticOptimizations optimisticOpts) { + private InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts, + Map<Invoke, Double> hints) { this.runtime = runtime; this.replacements = replacements; - this.assumptions = assumptions; + this.compilationAssumptions = assumptions; this.cache = cache; this.plan = plan; - this.inliningPolicy = inliningPolicy; + this.inliningPolicy = new GreedyInliningPolicy(replacements, hints); this.optimisticOpts = optimisticOpts; + + this.data = new InliningData(); + } + + public static synchronized CompiledMethodInfo compiledMethodInfo(ResolvedJavaMethod m) { + CompiledMethodInfo info = compiledMethodInfo.get(m); + if (info == null) { + info = new CompiledMethodInfo(); + compiledMethodInfo.put(m, info); + } + return info; } public void setCustomCanonicalizer(CustomCanonicalizer customCanonicalizer) { @@ -99,261 +105,422 @@ return inliningCount; } + static class InliningData { + + private static final GraphInfo DummyGraphInfo = new GraphInfo(null, new Stack<Invoke>(), 1.0, 1.0); + + private final ArrayDeque<GraphInfo> graphQueue; + private final ArrayDeque<MethodInvocation> invocationQueue; + + private int maxGraphs = 1; + + public InliningData() { + this.graphQueue = new ArrayDeque<>(); + this.invocationQueue = new ArrayDeque<>(); + } + + public void pushGraph(StructuredGraph graph, double probability, double relevance) { + assert !contains(graph); + NodeBitMap visitedFixedNodes = graph.createNodeBitMap(); + Stack<Invoke> invokes = new InliningIterator(graph.start(), visitedFixedNodes).apply(); + assert invokes.size() == count(graph.getInvokes()); + graphQueue.push(new GraphInfo(graph, invokes, probability, relevance)); + assert graphQueue.size() <= maxGraphs; + } + + public void pushGraphDummy() { + graphQueue.push(DummyGraphInfo); + } + + public boolean hasUnprocessedGraphs() { + return !graphQueue.isEmpty(); + } + + public GraphInfo currentGraph() { + return graphQueue.peek(); + } + + public void popGraph() { + graphQueue.pop(); + assert graphQueue.size() <= maxGraphs; + } + + public MethodInvocation currentInvocation() { + return invocationQueue.peek(); + } + + public MethodInvocation pushInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) { + MethodInvocation methodInvocation = new MethodInvocation(info, new Assumptions(assumptions.useOptimisticAssumptions()), probability, relevance); + invocationQueue.push(methodInvocation); + maxGraphs += info.numberOfMethods(); + assert graphQueue.size() <= maxGraphs; + return methodInvocation; + } + + public void popInvocation() { + maxGraphs -= invocationQueue.peek().callee.numberOfMethods(); + assert graphQueue.size() <= maxGraphs; + invocationQueue.pop(); + } + + public int countRecursiveInlining(ResolvedJavaMethod method) { + int count = 0; + for (GraphInfo graphInfo : graphQueue) { + if (method.equals(graphInfo.graph().method())) { + count++; + } + } + return count; + } + + @Override + public String toString() { + StringBuilder result = new StringBuilder("Invocations: "); + + for (MethodInvocation invocation : invocationQueue) { + result.append(invocation.callee().numberOfMethods()); + result.append("x "); + result.append(invocation.callee().invoke()); + result.append("; "); + } + + result.append("\nGraphs: "); + for (GraphInfo graph : graphQueue) { + result.append(graph.graph()); + result.append("; "); + } + + return result.toString(); + } + + private boolean contains(StructuredGraph graph) { + for (GraphInfo info : graphQueue) { + if (info.graph() == graph) { + return true; + } + } + return false; + } + + private static int count(Iterable<Invoke> invokes) { + int count = 0; + Iterator<Invoke> iterator = invokes.iterator(); + while (iterator.hasNext()) { + iterator.next(); + count++; + } + return count; + } + + public int inliningDepth() { + return invocationQueue.size(); + } + } + + private static class MethodInvocation { + + private final InlineInfo callee; + private final Assumptions assumptions; + private final double probability; + private final double relevance; + + private int processedGraphs; + + public MethodInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) { + this.callee = info; + this.assumptions = assumptions; + this.probability = probability; + this.relevance = relevance; + } + + public void incrementProcessedGraphs() { + processedGraphs++; + } + + public boolean processedAllGraphs() { + assert processedGraphs <= callee.numberOfMethods(); + return processedGraphs == callee.numberOfMethods(); + } + + public InlineInfo callee() { + return callee; + } + + public Assumptions assumptions() { + return assumptions; + } + + public double probability() { + return probability; + } + + public double relevance() { + return relevance; + } + } + @Override protected void run(final StructuredGraph graph) { - NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); - NodesToDoubles nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); - inliningPolicy.initialize(graph); - - while (inliningPolicy.continueInlining(graph)) { - final InlineInfo candidate = inliningPolicy.next(); - - if (candidate != null) { - boolean isWorthInlining = inliningPolicy.isWorthInlining(candidate, nodeProbabilities, nodeRelevance); - isWorthInlining &= candidate.numberOfMethods() <= maxMethodPerInlining; + data.pushGraph(graph, 1.0, 1.0); - metricInliningConsidered.increment(); - if (isWorthInlining) { - int mark = graph.getMark(); - try { - List<Node> invokeUsages = candidate.invoke().asNode().usages().snapshot(); - candidate.inline(graph, runtime, replacements, this, assumptions); - Debug.dump(graph, "after %s", candidate); - Iterable<Node> newNodes = graph.getNewNodes(mark); - inliningPolicy.scanInvokes(newNodes); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase.Instance(runtime, assumptions, invokeUsages, mark, customCanonicalizer).apply(graph); - } - - nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); - nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); - - inliningCount++; - metricInliningPerformed.increment(); - } catch (BailoutException bailout) { - throw bailout; - } catch (AssertionError e) { - throw new GraalInternalError(e).addContext(candidate.toString()); - } catch (RuntimeException e) { - throw new GraalInternalError(e).addContext(candidate.toString()); - } catch (GraalInternalError e) { - throw e.addContext(candidate.toString()); + while (data.hasUnprocessedGraphs()) { + GraphInfo graphInfo = data.currentGraph(); + if (graphInfo.hasRemainingInvokes() && inliningPolicy.continueInlining(data)) { + processNextInvoke(graphInfo); + } else { + data.popGraph(); + MethodInvocation currentInvoke = data.currentInvocation(); + if (currentInvoke != null) { + assert currentInvoke.callee().invoke().asNode().isAlive(); + currentInvoke.incrementProcessedGraphs(); + if (currentInvoke.processedAllGraphs()) { + data.popInvocation(); + MethodInvocation parentInvoke = data.currentInvocation(); + tryToInline(data.currentGraph(), currentInvoke, parentInvoke); } - } else if (optimisticOpts.devirtualizeInvokes()) { - candidate.tryToDevirtualizeInvoke(graph, runtime, assumptions); } } } } - @Override - public StructuredGraph buildGraph(final ResolvedJavaMethod method) { - metricInliningRuns.increment(); + private void processNextInvoke(GraphInfo graphInfo) { + // process the next invoke and enqueue all its graphs for processing + Invoke invoke = graphInfo.popInvoke(); + MethodInvocation callerInvocation = data.currentInvocation(); + Assumptions parentAssumptions = callerInvocation == null ? compilationAssumptions : callerInvocation.assumptions(); + InlineInfo info = InliningUtil.getInlineInfo(data, invoke, maxMethodPerInlining, replacements, parentAssumptions, optimisticOpts); + + if (info != null) { + double callerProbability = graphInfo.getInvokeProbability(invoke); + double callerRelevance = graphInfo.getInvokeRelevance(invoke); + MethodInvocation calleeInvocation = data.pushInvocation(info, parentAssumptions, callerProbability, callerRelevance); + + for (int i = 0; i < info.numberOfMethods(); i++) { + InlineableElement elem = getInlineableElement(info.methodAt(i), info.invoke(), calleeInvocation.assumptions()); + info.setInlinableElement(i, elem); + if (elem instanceof StructuredGraph) { + data.pushGraph((StructuredGraph) elem, callerProbability * info.probabilityAt(i), callerRelevance * info.relevanceAt(i)); + } else { + data.pushGraphDummy(); + } + } + } + } + + private void tryToInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, MethodInvocation parentInvoke) { + InlineInfo callee = calleeInfo.callee(); + Assumptions callerAssumptions = parentInvoke == null ? compilationAssumptions : parentInvoke.assumptions(); + + if (inliningPolicy.isWorthInlining(callee, calleeInfo.probability(), calleeInfo.relevance())) { + doInline(callerGraphInfo, calleeInfo, callerAssumptions); + } else if (optimisticOpts.devirtualizeInvokes()) { + callee.tryToDevirtualizeInvoke(runtime, callerAssumptions); + } + metricInliningConsidered.increment(); + } + + private void doInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, Assumptions callerAssumptions) { + StructuredGraph callerGraph = callerGraphInfo.graph(); + int mark = callerGraph.getMark(); + InlineInfo callee = calleeInfo.callee(); + try { + List<Node> invokeUsages = callee.invoke().asNode().usages().snapshot(); + callee.inline(runtime, callerAssumptions); + callerAssumptions.record(calleeInfo.assumptions()); + metricInliningRuns.increment(); + Debug.dump(callerGraph, "after %s", callee); + + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase.Instance(runtime, callerAssumptions, invokeUsages, mark, customCanonicalizer).apply(callerGraph); + +// if (callerGraph.getNewNodes(mark).contains(Invoke.class)) { +// // TODO (chaeubl): invoke nodes might be created during canonicalization, which +// // is bad for the CF ordering of the invokes but we still have to handle it properly... +// } + } + + callerGraphInfo.computeProbabilities(); + + inliningCount++; + metricInliningPerformed.increment(); + } catch (BailoutException bailout) { + throw bailout; + } catch (AssertionError | RuntimeException e) { + throw new GraalInternalError(e).addContext(callee.toString()); + } catch (GraalInternalError e) { + throw e.addContext(callee.toString()); + } + } + + private InlineableElement getInlineableElement(final ResolvedJavaMethod method, Invoke invoke, Assumptions assumptions) { + Class<? extends FixedWithNextNode> macroNodeClass = InliningUtil.getMacroNodeClass(replacements, method); + if (macroNodeClass != null) { + return new InliningUtil.InlineableMacroNode(macroNodeClass); + } else { + return buildGraph(method, invoke, assumptions); + } + } + + private StructuredGraph buildGraph(final ResolvedJavaMethod method, final Invoke invoke, final Assumptions assumptions) { + final StructuredGraph newGraph; + final boolean parseBytecodes; + + // TODO (chaeubl): copying the graph is only necessary if it is modified + StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(replacements, method); + if (intrinsicGraph != null) { + newGraph = intrinsicGraph.copy(); + parseBytecodes = false; + } else { + StructuredGraph cachedGraph = getCachedGraph(method); + if (cachedGraph != null) { + newGraph = cachedGraph.copy(); + parseBytecodes = false; + } else { + newGraph = new StructuredGraph(method); + parseBytecodes = true; + } + } + + return Debug.scope("InlineGraph", newGraph, new Callable<StructuredGraph>() { + + @Override + public StructuredGraph call() throws Exception { + if (parseBytecodes) { + parseBytecodes(newGraph, assumptions); + } + + if (GraalOptions.PropagateArgumentsDuringInlining) { + // TODO (chaeubl): if args are not more concrete, inlining will not change the + // size of the graph + NodeInputList<ValueNode> args = invoke.callTarget().arguments(); + for (LocalNode localNode : newGraph.getNodes(LocalNode.class).snapshot()) { + ValueNode arg = args.get(localNode.index()); + if (arg.isConstant()) { + Constant constant = arg.asConstant(); + newGraph.replaceFloating(localNode, ConstantNode.forConstant(constant, runtime, newGraph)); + } else { + localNode.setStamp(localNode.stamp().join(arg.stamp())); + } + } + + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); + } + } + + return newGraph; + } + }); + } + + private StructuredGraph getCachedGraph(ResolvedJavaMethod method) { if (GraalOptions.CacheGraphs && cache != null) { StructuredGraph cachedGraph = cache.get(method); if (cachedGraph != null) { return cachedGraph; } } - final StructuredGraph newGraph = new StructuredGraph(method); - return Debug.scope("InlineGraph", newGraph, new Callable<StructuredGraph>() { + return null; + } - @Override - public StructuredGraph call() throws Exception { - if (plan != null) { - plan.runPhases(PhasePosition.AFTER_PARSING, newGraph); - } - assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; + private StructuredGraph parseBytecodes(StructuredGraph newGraph, Assumptions assumptions) { + if (plan != null) { + plan.runPhases(PhasePosition.AFTER_PARSING, newGraph); + } + assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; - new DeadCodeEliminationPhase().apply(newGraph); + new DeadCodeEliminationPhase().apply(newGraph); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); - } - if (GraalOptions.CullFrameStates) { - new CullFrameStatesPhase().apply(newGraph); - } - if (GraalOptions.CacheGraphs && cache != null) { - cache.put(newGraph); - } - return newGraph; - } - }); + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); + } + + if (GraalOptions.CullFrameStates) { + new CullFrameStatesPhase().apply(newGraph); + } + if (GraalOptions.CacheGraphs && cache != null) { + cache.put(newGraph.copy()); + } + return newGraph; } - private interface InliningDecision { + private static class GraphInfo { + + private final StructuredGraph graph; + private final Stack<Invoke> remainingInvokes; + private final double probability; + private final double relevance; + private NodesToDoubles nodeProbabilities; + private NodesToDoubles nodeRelevance; + + public GraphInfo(StructuredGraph graph, Stack<Invoke> invokes, double probability, double relevance) { + this.graph = graph; + this.remainingInvokes = invokes; + this.probability = probability; + this.relevance = relevance; + + if (graph != null) { + computeProbabilities(); + } + } - boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance); + public boolean hasRemainingInvokes() { + return !remainingInvokes.isEmpty(); + } + + public StructuredGraph graph() { + return graph; + } + + public Invoke popInvoke() { + return remainingInvokes.pop(); + } + + public void computeProbabilities() { + nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); + } + + public double getInvokeProbability(Invoke invoke) { + return probability * nodeProbabilities.get(invoke.asNode()); + } + + public double getInvokeRelevance(Invoke invoke) { + return Math.min(relevance, 1.0) * nodeRelevance.get(invoke.asNode()); + } } - private static class GreedySizeBasedInliningDecision implements InliningDecision { + private abstract static class AbstractInliningPolicy implements InliningPolicy { - private final MetaAccessProvider runtime; - private final Replacements replacements; - private final Map<Invoke, Double> hints; + protected final Replacements replacements; + protected final Map<Invoke, Double> hints; - public GreedySizeBasedInliningDecision(MetaAccessProvider runtime, Replacements replacements, Map<Invoke, Double> hints) { - this.runtime = runtime; + public AbstractInliningPolicy(Replacements replacements, Map<Invoke, Double> hints) { this.replacements = replacements; this.hints = hints; } - @Override - public boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance) { - /* - * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> - * will be compiled anyways and it is likely that we are the only caller... might be - * useful to inline those methods but increases bootstrap time (maybe those methods are - * also getting queued in the compilation queue concurrently) - */ - - if (GraalOptions.AlwaysInlineIntrinsics) { - if (onlyIntrinsics(replacements, info)) { - return InliningUtil.logInlinedMethod(info, "intrinsic"); - } - } else { - if (onlyForcedIntrinsics(replacements, info)) { - return InliningUtil.logInlinedMethod(info, "intrinsic"); - } - } - - double bonus = 1; - if (hints != null && hints.containsKey(info.invoke())) { - bonus = hints.get(info.invoke()); - } - - int bytecodeSize = (int) (bytecodeCodeSize(info) / bonus); - int complexity = (int) (compilationComplexity(info) / bonus); - int compiledCodeSize = (int) (compiledCodeSize(info) / bonus); - double relevance = nodeRelevance.get(info.invoke().asNode()); - /* - * as long as the compiled code size is small enough (or the method was not yet - * compiled), we can do a pretty general inlining that suits most situations - */ - if (compiledCodeSize < GraalOptions.SmallCompiledCodeSize) { - if (isTrivialInlining(bytecodeSize, complexity, compiledCodeSize)) { - return InliningUtil.logInlinedMethod(info, "trivial (bytecodes=%d, complexity=%d, codeSize=%d)", bytecodeSize, complexity, compiledCodeSize); - } - - if (canInlineRelevanceBased(relevance, bytecodeSize, complexity, compiledCodeSize)) { - return InliningUtil.logInlinedMethod(info, "relevance-based (relevance=%f, bytecodes=%d, complexity=%d, codeSize=%d)", relevance, bytecodeSize, complexity, compiledCodeSize); - } - } - - /* - * the normal inlining did not fit this invoke, so check if we have any reason why we - * should still do the inlining - */ - double probability = nodeProbabilities.get(info.invoke().asNode()); - int transferredValues = numberOfTransferredValues(info); - int invokeUsages = countInvokeUsages(info); - int moreSpecificArguments = countMoreSpecificArgumentInfo(info); - int level = info.level(); - - // TODO (chaeubl): compute metric that is used to check if this method should be inlined - - return InliningUtil.logNotInlinedMethod(info, - "(relevance=%f, bytecodes=%d, complexity=%d, codeSize=%d, probability=%f, transferredValues=%d, invokeUsages=%d, moreSpecificArguments=%d, level=%d, bonus=%f)", relevance, - bytecodeSize, complexity, compiledCodeSize, probability, transferredValues, invokeUsages, moreSpecificArguments, level, bonus); - } - - private static boolean isTrivialInlining(int bytecodeSize, int complexity, int compiledCodeSize) { - return bytecodeSize < GraalOptions.TrivialBytecodeSize || complexity < GraalOptions.TrivialComplexity || compiledCodeSize > 0 && compiledCodeSize < GraalOptions.TrivialCompiledCodeSize; - } - - private static boolean canInlineRelevanceBased(double relevance, int bytecodeSize, int complexity, int compiledCodeSize) { - return bytecodeSize < computeMaximumSize(relevance, GraalOptions.NormalBytecodeSize) || complexity < computeMaximumSize(relevance, GraalOptions.NormalComplexity) || compiledCodeSize > 0 && - compiledCodeSize < computeMaximumSize(relevance, GraalOptions.NormalCompiledCodeSize); - } - - private static double computeMaximumSize(double relevance, int configuredMaximum) { + protected double computeMaximumSize(double relevance, int configuredMaximum) { double inlineRatio = Math.min(GraalOptions.RelevanceCapForInlining, relevance); return configuredMaximum * inlineRatio; } - private static int numberOfTransferredValues(InlineInfo info) { - MethodCallTargetNode methodCallTargetNode = ((MethodCallTargetNode) info.invoke().callTarget()); - Signature signature = methodCallTargetNode.targetMethod().getSignature(); - int transferredValues = signature.getParameterCount(!Modifier.isStatic(methodCallTargetNode.targetMethod().getModifiers())); - if (signature.getReturnKind() != Kind.Void) { - transferredValues++; + protected double getInliningBonus(InlineInfo info) { + if (hints != null && hints.containsKey(info.invoke())) { + return hints.get(info.invoke()); } - return transferredValues; - } - - private static int countInvokeUsages(InlineInfo info) { - // inlining calls with lots of usages simplifies the caller - int usages = 0; - for (Node n : info.invoke().asNode().usages()) { - if (!(n instanceof FrameState)) { - usages++; - } - } - return usages; + return 1; } - private int countMoreSpecificArgumentInfo(InlineInfo info) { - /* - * inlining invokes where the caller has very specific information about the passed - * argument simplifies the callee - */ - int moreSpecificArgumentInfo = 0; - MethodCallTargetNode methodCallTarget = (MethodCallTargetNode) info.invoke().callTarget(); - boolean isStatic = methodCallTarget.isStatic(); - int signatureOffset = isStatic ? 0 : 1; - NodeInputList arguments = methodCallTarget.arguments(); - ResolvedJavaMethod targetMethod = methodCallTarget.targetMethod(); - ResolvedJavaType methodHolderClass = targetMethod.getDeclaringClass(); - Signature signature = targetMethod.getSignature(); - - for (int i = 0; i < arguments.size(); i++) { - Node n = arguments.get(i); - if (n instanceof ConstantNode) { - moreSpecificArgumentInfo++; - } else if (n instanceof ValueNode && !((ValueNode) n).kind().isPrimitive()) { - ResolvedJavaType actualType = ((ValueNode) n).stamp().javaType(runtime); - JavaType declaredType; - if (i == 0 && !isStatic) { - declaredType = methodHolderClass; - } else { - declaredType = signature.getParameterType(i - signatureOffset, methodHolderClass); - } - - if (declaredType instanceof ResolvedJavaType && !actualType.equals(declaredType) && ((ResolvedJavaType) declaredType).isAssignableFrom(actualType)) { - moreSpecificArgumentInfo++; - } - } - + protected boolean isIntrinsic(InlineInfo info) { + if (GraalOptions.AlwaysInlineIntrinsics) { + return onlyIntrinsics(info); + } else { + return onlyForcedIntrinsics(info); } - - return moreSpecificArgumentInfo; } - private static int bytecodeCodeSize(InlineInfo info) { - int result = 0; - for (int i = 0; i < info.numberOfMethods(); i++) { - result += info.methodAt(i).getCodeSize(); - } - return result; - } - - private static int compilationComplexity(InlineInfo info) { - int result = 0; - for (int i = 0; i < info.numberOfMethods(); i++) { - result += info.methodAt(i).getCompilationComplexity(); - } - return result; - } - - private static int compiledCodeSize(InlineInfo info) { - int result = 0; - for (int i = 0; i < info.numberOfMethods(); i++) { - result += info.methodAt(i).getCompiledCodeSize(); - } - return result; - } - - private static boolean onlyIntrinsics(Replacements replacements, InlineInfo info) { + private boolean onlyIntrinsics(InlineInfo info) { for (int i = 0; i < info.numberOfMethods(); i++) { if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) { return false; @@ -362,7 +529,7 @@ return true; } - private static boolean onlyForcedIntrinsics(Replacements replacements, InlineInfo info) { + private boolean onlyForcedIntrinsics(InlineInfo info) { for (int i = 0; i < info.numberOfMethods(); i++) { if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) { return false; @@ -375,82 +542,137 @@ } } - private static class CFInliningPolicy implements InliningPolicy { + private static class GreedyInliningPolicy extends AbstractInliningPolicy { - private final InliningDecision inliningDecision; - private final Assumptions assumptions; - private final Replacements replacements; - private final OptimisticOptimizations optimisticOpts; - private final Deque<Invoke> sortedInvokes; - private NodeBitMap visitedFixedNodes; - private FixedNode invokePredecessor; - - public CFInliningPolicy(InliningDecision inliningPolicy, Replacements replacements, Assumptions assumptions, OptimisticOptimizations optimisticOpts) { - this.inliningDecision = inliningPolicy; - this.replacements = replacements; - this.assumptions = assumptions; - this.optimisticOpts = optimisticOpts; - this.sortedInvokes = new ArrayDeque<>(); + public GreedyInliningPolicy(Replacements replacements, Map<Invoke, Double> hints) { + super(replacements, hints); } - public boolean continueInlining(StructuredGraph graph) { - if (graph.getNodeCount() >= GraalOptions.MaximumDesiredSize) { + public boolean continueInlining(InliningData data) { + if (data.currentGraph().graph().getNodeCount() >= GraalOptions.MaximumDesiredSize) { InliningUtil.logInliningDecision("inlining is cut off by MaximumDesiredSize"); metricInliningStoppedByMaxDesiredSize.increment(); return false; } - return !sortedInvokes.isEmpty(); - } + MethodInvocation currentInvocation = data.currentInvocation(); + if (currentInvocation == null) { + return true; + } + + InlineInfo info = currentInvocation.callee(); + double inliningBonus = getInliningBonus(info); + + int hirSize = previousHIRSize(info); + if (hirSize > GraalOptions.SmallCompiledGraphSize * inliningBonus) { + return InliningUtil.logNotInlinedMethod(info, "too large HIR graph: %s", hirSize); + } - public InlineInfo next() { - Invoke invoke = sortedInvokes.pop(); - InlineInfo info = InliningUtil.getInlineInfo(invoke, replacements, assumptions, optimisticOpts); - if (info != null) { - invokePredecessor = (FixedNode) info.invoke().predecessor(); - assert invokePredecessor.isAlive(); + int nodes = determineNodeCount(info); + if (nodes < GraalOptions.TrivialHighLevelGraphSize * inliningBonus) { + return InliningUtil.logInlinedMethod(info, "trivial (nodes=%d)", nodes); } - return info; + + double maximumNodes = computeMaximumSize(currentInvocation.relevance(), (int) (GraalOptions.NormalHighLevelGraphSize * inliningBonus)); + if (nodes < maximumNodes) { + return InliningUtil.logInlinedMethod(info, "relevance-based (relevance=%f, nodes=%d)", currentInvocation.relevance(), nodes); + } + + // TODO (chaeubl): compute metric that is used to check if this method should be + // inlined + + return InliningUtil.logNotInlinedMethod(info, "(relevance=%f, probability=%f, bonus=%f)", currentInvocation.relevance(), currentInvocation.probability(), inliningBonus); } @Override - public boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance) { - return inliningDecision.isWorthInlining(info, nodeProbabilities, nodeRelevance); - } + public boolean isWorthInlining(InlineInfo info, double probability, double relevance) { + if (isIntrinsic(info)) { + return InliningUtil.logInlinedMethod(info, "intrinsic"); + } + + double inliningBonus = getInliningBonus(info); + + int hirSize = previousHIRSize(info); + if (hirSize > GraalOptions.SmallCompiledGraphSize * inliningBonus) { + return InliningUtil.logNotInlinedMethod(info, "too large HIR graph: %s", hirSize); + } + + /* + * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> + * will be compiled anyways and it is likely that we are the only caller... might be + * useful to inline those methods but increases bootstrap time (maybe those methods are + * also getting queued in the compilation queue concurrently) + */ + + // TODO (chaeubl): we could do a shortcut here, i.e. if it resulted in something simple + // before avoid building the graphs - public void initialize(StructuredGraph graph) { - visitedFixedNodes = graph.createNodeBitMap(true); - scanGraphForInvokes(graph.start()); - } + // @formatter:off + // trivial + // few nodes + // linear and no invokes + // leaf + // no invokes + // normal + // many nodes + // no frequently executed invokes + // complex + // many nodes + // frequently executed invokes + // @formatter:on - public void scanInvokes(Iterable<? extends Node> newNodes) { - assert invokePredecessor.isAlive(); - int invokes = scanGraphForInvokes(invokePredecessor); - assert invokes == countInvokes(newNodes); + int nodes = determineNodeCount(info); + if (nodes < GraalOptions.TrivialHighLevelGraphSize * inliningBonus) { + return InliningUtil.logInlinedMethod(info, "trivial (nodes=%d)", nodes); + } + + double invokes = determineInvokeProbability(info); + if (GraalOptions.LimitInlinedInvokes > 0 && invokes > GraalOptions.LimitInlinedInvokes * inliningBonus) { + return InliningUtil.logNotInlinedMethod(info, "invoke probability is too high (%f)", invokes); + } + + double maximumNodes = computeMaximumSize(relevance, (int) (GraalOptions.NormalHighLevelGraphSize * inliningBonus)); + if (nodes < maximumNodes) { + return InliningUtil.logInlinedMethod(info, "relevance-based (relevance=%f, nodes=%d)", relevance, nodes); + } + + // TODO (chaeubl): compute metric that is used to check if this method should be inlined + + return InliningUtil.logNotInlinedMethod(info, "(relevance=%f, probability=%f, bonus=%f)", relevance, probability, inliningBonus); } - private int scanGraphForInvokes(FixedNode start) { - ArrayList<Invoke> invokes = new InliningIterator(start, visitedFixedNodes).apply(); - - // insert the newly found invokes in their correct control-flow order - for (int i = invokes.size() - 1; i >= 0; i--) { - Invoke invoke = invokes.get(i); - assert !sortedInvokes.contains(invoke); - sortedInvokes.addFirst(invoke); - + private static int previousHIRSize(InlineInfo info) { + int size = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + size += compiledMethodInfo(info.methodAt(i)).getHighLevelNodes(); } - - return invokes.size(); + return size; } - private static int countInvokes(Iterable<? extends Node> nodes) { - int count = 0; - for (Node n : nodes) { - if (n instanceof Invoke) { - count++; + private static int determineNodeCount(InlineInfo info) { + int nodes = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + InlineableElement elem = info.inlineableElementAt(i); + if (elem != null) { + nodes += elem.getNodeCount(); } } - return count; + return nodes; + } + + private static double determineInvokeProbability(InlineInfo info) { + double invokeProbability = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + InlineableElement callee = info.inlineableElementAt(i); + Iterable<Invoke> invokes = callee.getInvokes(); + if (invokes.iterator().hasNext()) { + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure((StructuredGraph) callee).apply(); + for (Invoke invoke : invokes) { + invokeProbability += nodeProbabilities.get(invoke.asNode()); + } + } + } + return invokeProbability; } } @@ -467,8 +689,8 @@ assert start.isAlive(); } - public ArrayList<Invoke> apply() { - ArrayList<Invoke> invokes = new ArrayList<>(); + public Stack<Invoke> apply() { + Stack<Invoke> invokes = new Stack<>(); FixedNode current; forcedQueue(start); @@ -477,7 +699,7 @@ if (current instanceof Invoke) { if (current != start) { - invokes.add((Invoke) current); + invokes.push((Invoke) current); } queueSuccessors(current); } else if (current instanceof LoopBeginNode) { @@ -547,8 +769,79 @@ } } - private static InliningPolicy createInliningPolicy(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, OptimisticOptimizations optimisticOpts, Map<Invoke, Double> hints) { - InliningDecision inliningDecision = new GreedySizeBasedInliningDecision(runtime, replacements, hints); - return new CFInliningPolicy(inliningDecision, replacements, assumptions, optimisticOpts); + public static class CompiledMethodInfo { + + private int highLevelNodes; + private int midLevelNodes; + private int lowLevelNodes; + private int compiledCodeSize; + private double summedUpProbabilityOfRemainingInvokes; + private double maxProbabilityOfRemainingInvokes; + private int numberOfRemainingInvokes; + + public CompiledMethodInfo() { + } + + public int getHighLevelNodes() { + return highLevelNodes; + } + + public int getMidLevelNodes() { + return midLevelNodes; + } + + public int getLowLevelNodes() { + return lowLevelNodes; + } + + public int getCompiledCodeSize() { + return compiledCodeSize; + } + + public double getMaxProbabilityOfRemainingInvokes() { + return maxProbabilityOfRemainingInvokes; + } + + public double getSummedUpProbabilityOfRemainingInvokes() { + return summedUpProbabilityOfRemainingInvokes; + } + + public int getNumberOfRemainingInvokes() { + return numberOfRemainingInvokes; + } + + public void setHighLevelNodes(int highLevelNodes) { + this.highLevelNodes = highLevelNodes; + } + + public void setMidLevelNodes(int midLevelNodes) { + this.midLevelNodes = midLevelNodes; + } + + public void setLowLevelNodes(int lowLevelNodes) { + this.lowLevelNodes = lowLevelNodes; + } + + public void setMaxProbabilityOfRemainingInvokes(double maxProbabilityOfRemainingInvokes) { + this.maxProbabilityOfRemainingInvokes = maxProbabilityOfRemainingInvokes; + } + + public void setSummedUpProbabilityOfRemainingInvokes(double summedUpProbabilityOfRemainingInvokes) { + this.summedUpProbabilityOfRemainingInvokes = summedUpProbabilityOfRemainingInvokes; + } + + public void setCompiledCodeSize(int compiledCodeSize) { + this.compiledCodeSize = compiledCodeSize; + } + + public void setNumberOfRemainingInvokes(int numberOfRemainingInvokes) { + this.numberOfRemainingInvokes = numberOfRemainingInvokes; + } + + @Override + public String toString() { + return String.format("High: %d, Mid: %d, Low: %d, Compiled: %d, #Invokes: %d, SumOfInvokes: %f, MaxOfInvokes: %f", highLevelNodes, midLevelNodes, lowLevelNodes, compiledCodeSize, + numberOfRemainingInvokes, summedUpProbabilityOfRemainingInvokes, maxProbabilityOfRemainingInvokes); + } } }