# HG changeset patch # User Christian Haeubl # Date 1368443657 -7200 # Node ID e538498d6eae725b5101059d4018647ad44503c2 # Parent 197426668a5d1609a2408edda266104e6a66b81d some refactorings and cleanups for the InliningPhase diff -r 197426668a5d -r e538498d6eae graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Wed May 08 17:21:38 2013 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon May 13 13:14:17 2013 +0200 @@ -42,7 +42,6 @@ import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.InliningPhase.CompiledMethodInfo; import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.schedule.*; import com.oracle.graal.phases.tiers.*; @@ -134,25 +133,20 @@ new IterativeConditionalEliminationPhase().apply(graph, highTierContext); } } + InliningPhase.saveGraphStatistics(graph); } plan.runPhases(PhasePosition.HIGH_LEVEL, graph); - CompiledMethodInfo info = InliningPhase.compiledMethodInfo(graph.method()); - analyzeInvokes(graph, info); - Suites.DEFAULT.getHighTier().apply(graph, highTierContext); - info.setHighLevelNodes(graph.getNodeCount()); MidTierContext midTierContext = new MidTierContext(runtime, assumptions, replacements, target); Suites.DEFAULT.getMidTier().apply(graph, midTierContext); - info.setMidLevelNodes(graph.getNodeCount()); plan.runPhases(PhasePosition.LOW_LEVEL, graph); LowTierContext lowTierContext = new LowTierContext(runtime, assumptions, replacements, target); Suites.DEFAULT.getLowTier().apply(graph, lowTierContext); - info.setLowLevelNodes(graph.getNodeCount()); final SchedulePhase schedule = new SchedulePhase(); schedule.apply(graph); @@ -180,21 +174,6 @@ } - private static void analyzeInvokes(final StructuredGraph graph, CompiledMethodInfo info) { - NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); - double summedUpProbabilityOfRemainingInvokes = 0; - double maxProbabilityOfRemainingInvokes = 0; - int invokes = 0; - for (Invoke invoke : graph.getInvokes()) { - summedUpProbabilityOfRemainingInvokes += nodeProbabilities.get(invoke.asNode()); - maxProbabilityOfRemainingInvokes = Math.max(maxProbabilityOfRemainingInvokes, nodeProbabilities.get(invoke.asNode())); - invokes++; - } - info.setSummedUpProbabilityOfRemainingInvokes(summedUpProbabilityOfRemainingInvokes); - info.setMaxProbabilityOfRemainingInvokes(maxProbabilityOfRemainingInvokes); - info.setNumberOfRemainingInvokes(invokes); - } - public static LIRGenerator emitLIR(Backend backend, final TargetDescription target, final LIR lir, StructuredGraph graph, final ResolvedJavaMethod method) { final FrameMap frameMap = backend.newFrameMap(); final LIRGenerator lirGen = backend.newLIRGenerator(graph, frameMap, method, lir); @@ -236,7 +215,6 @@ TargetMethodAssembler tasm = backend.newAssembler(lirGen, compilationResult); backend.emitCode(tasm, method, lirGen); CompilationResult result = tasm.finishTargetMethod(method, false); - InliningPhase.compiledMethodInfo(method).setCompiledCodeSize(result.getTargetCodeSize()); if (!assumptions.isEmpty()) { result.setAssumptions(assumptions); } diff -r 197426668a5d -r e538498d6eae graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Wed May 08 17:21:38 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Mon May 13 13:14:17 2013 +0200 @@ -31,11 +31,13 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; 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.InlineableMacroNode; import com.oracle.graal.phases.common.InliningUtil.InliningPolicy; import com.oracle.graal.phases.graph.*; @@ -50,7 +52,6 @@ private final GraphCache cache; private final InliningPolicy inliningPolicy; private final OptimisticOptimizations optimisticOpts; - private final InliningData data; private CustomCanonicalizer customCanonicalizer; private int inliningCount; @@ -67,10 +68,6 @@ 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); - } - private InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts, Map hints) { this.runtime = runtime; @@ -80,17 +77,6 @@ this.plan = plan; 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) { @@ -105,213 +91,75 @@ return inliningCount; } - static class InliningData { - - private static final GraphInfo DummyGraphInfo = new GraphInfo(null, new Stack(), 1.0, 1.0); - - private final ArrayDeque graphQueue; - private final ArrayDeque 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 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 invokes) { - int count = 0; - Iterator 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; - } + public static void saveGraphStatistics(StructuredGraph graph) { + CompiledMethodInfo info = compiledMethodInfo(graph.method()); + double summedUpProbabilityOfRemainingInvokes = sumUpInvokeProbabilities(graph); + info.setSummedUpProbabilityOfRemainingInvokes(summedUpProbabilityOfRemainingInvokes); + info.setHighLevelNodeCount(graph.getNodeCount()); } @Override protected void run(final StructuredGraph graph) { + InliningData data = new InliningData(); data.pushGraph(graph, 1.0, 1.0); while (data.hasUnprocessedGraphs()) { GraphInfo graphInfo = data.currentGraph(); if (graphInfo.hasRemainingInvokes() && inliningPolicy.continueInlining(data)) { - processNextInvoke(graphInfo); + processNextInvoke(data, 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); - } + tryToInlineCurrentInvocation(data); + } + } + } + + /** + * Process the next invoke and enqueue all its graphs for processing. + */ + private void processNextInvoke(InliningData data, GraphInfo graphInfo) { + 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); + + double invokeProbability = graphInfo.getInvokeProbability(invoke); + double invokeRelevance = graphInfo.getInvokeRelevance(invoke); + if (info != null && inliningPolicy.isWorthInlining(info, invokeProbability, invokeRelevance, false)) { + MethodInvocation calleeInvocation = data.pushInvocation(info, parentAssumptions, invokeProbability, invokeRelevance); + + 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, invokeProbability * info.probabilityAt(i), invokeRelevance * info.relevanceAt(i)); + } else { + assert elem instanceof InlineableMacroNode; + // directly mark one callee as done because we do not have a graph to process + calleeInvocation.incrementProcessedGraphs(); } } } } - 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 tryToInlineCurrentInvocation(InliningData data) { + MethodInvocation currentInvocation = data.currentInvocation(); + if (currentInvocation != null) { + assert currentInvocation.callee().invoke().asNode().isAlive(); + currentInvocation.incrementProcessedGraphs(); + if (currentInvocation.processedAllGraphs()) { + data.popInvocation(); + MethodInvocation parentInvoke = data.currentInvocation(); + tryToInline(data.currentGraph(), currentInvocation, parentInvoke); } } } - private void tryToInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, MethodInvocation parentInvoke) { + private void tryToInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, MethodInvocation parentInvocation) { InlineInfo callee = calleeInfo.callee(); - Assumptions callerAssumptions = parentInvoke == null ? compilationAssumptions : parentInvoke.assumptions(); + Assumptions callerAssumptions = parentInvocation == null ? compilationAssumptions : parentInvocation.assumptions(); - if (inliningPolicy.isWorthInlining(callee, calleeInfo.probability(), calleeInfo.relevance())) { + if (inliningPolicy.isWorthInlining(callee, calleeInfo.probability(), calleeInfo.relevance(), true)) { doInline(callerGraphInfo, calleeInfo, callerAssumptions); } else if (optimisticOpts.devirtualizeInvokes()) { callee.tryToDevirtualizeInvoke(runtime, callerAssumptions); @@ -321,7 +169,7 @@ private void doInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, Assumptions callerAssumptions) { StructuredGraph callerGraph = callerGraphInfo.graph(); - int mark = callerGraph.getMark(); + int markBeforeInlining = callerGraph.getMark(); InlineInfo callee = calleeInfo.callee(); try { List invokeUsages = callee.invoke().asNode().usages().snapshot(); @@ -331,12 +179,15 @@ Debug.dump(callerGraph, "after %s", callee); if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase.Instance(runtime, callerAssumptions, invokeUsages, mark, customCanonicalizer).apply(callerGraph); + int markBeforeCanonicalization = callerGraph.getMark(); + new CanonicalizerPhase.Instance(runtime, callerAssumptions, invokeUsages, markBeforeInlining, 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... -// } + // process invokes that are possibly created during canonicalization + for (Node newNode : callerGraph.getNewNodes(markBeforeCanonicalization)) { + if (newNode instanceof Invoke) { + callerGraphInfo.pushInvoke((Invoke) newNode); + } + } } callerGraphInfo.computeProbabilities(); @@ -355,7 +206,7 @@ private InlineableElement getInlineableElement(final ResolvedJavaMethod method, Invoke invoke, Assumptions assumptions) { Class macroNodeClass = InliningUtil.getMacroNodeClass(replacements, method); if (macroNodeClass != null) { - return new InliningUtil.InlineableMacroNode(macroNodeClass); + return new InlineableMacroNode(macroNodeClass); } else { return buildGraph(method, invoke, assumptions); } @@ -365,7 +216,8 @@ final StructuredGraph newGraph; final boolean parseBytecodes; - // TODO (chaeubl): copying the graph is only necessary if it is modified + // TODO (chaeubl): copying the graph is only necessary if it is modified or if it contains + // any invokes StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(replacements, method); if (intrinsicGraph != null) { newGraph = intrinsicGraph.copy(); @@ -390,19 +242,29 @@ } if (GraalOptions.PropagateArgumentsDuringInlining) { - // TODO (chaeubl): if args are not more concrete, inlining will not change the - // size of the graph + boolean callerHasMoreInformationAboutArguments = false; NodeInputList 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)); + callerHasMoreInformationAboutArguments = true; } else { - localNode.setStamp(localNode.stamp().join(arg.stamp())); + Stamp joinedStamp = localNode.stamp().join(arg.stamp()); + if (!joinedStamp.equals(localNode.stamp())) { + localNode.setStamp(joinedStamp); + callerHasMoreInformationAboutArguments = true; + } } } + if (!callerHasMoreInformationAboutArguments) { + // TODO (chaeubl): if args are not more concrete, inlining should be avoided + // in most cases or we could at least use the previous graph size + invoke + // probability to check the inlining + } + if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); } @@ -444,6 +306,24 @@ return newGraph; } + private static synchronized CompiledMethodInfo compiledMethodInfo(ResolvedJavaMethod m) { + CompiledMethodInfo info = compiledMethodInfo.get(m); + if (info == null) { + info = new CompiledMethodInfo(); + compiledMethodInfo.put(m, info); + } + return info; + } + + private static double sumUpInvokeProbabilities(StructuredGraph graph) { + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + double summedUpProbabilityOfRemainingInvokes = 0; + for (Invoke invoke : graph.getInvokes()) { + summedUpProbabilityOfRemainingInvokes += nodeProbabilities.get(invoke.asNode()); + } + return summedUpProbabilityOfRemainingInvokes; + } + private static class GraphInfo { private final StructuredGraph graph; @@ -459,9 +339,7 @@ this.probability = probability; this.relevance = relevance; - if (graph != null) { - computeProbabilities(); - } + computeProbabilities(); } public boolean hasRemainingInvokes() { @@ -476,6 +354,10 @@ return remainingInvokes.pop(); } + public void pushInvoke(Invoke invoke) { + remainingInvokes.push(invoke); + } + public void computeProbabilities() { nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); @@ -540,6 +422,40 @@ } return true; } + + protected static int previousHIRSize(InlineInfo info) { + int size = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + size += compiledMethodInfo(info.methodAt(i)).getHighLevelNodes(); + } + return size; + } + + protected 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 nodes; + } + + protected static double determineInvokeProbability(InlineInfo info) { + double invokeProbability = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + InlineableElement callee = info.inlineableElementAt(i); + Iterable 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; + } } private static class GreedyInliningPolicy extends AbstractInliningPolicy { @@ -560,34 +476,13 @@ 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); - } - - int nodes = determineNodeCount(info); - if (nodes < GraalOptions.TrivialHighLevelGraphSize * inliningBonus) { - return InliningUtil.logInlinedMethod(info, "trivial (nodes=%d)", nodes); - } - - 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); + return isWorthInlining(currentInvocation.callee(), currentInvocation.probability(), currentInvocation.relevance(), false); } @Override - public boolean isWorthInlining(InlineInfo info, double probability, double relevance) { + public boolean isWorthInlining(InlineInfo info, double probability, double relevance, boolean fullyProcessed) { if (isIntrinsic(info)) { - return InliningUtil.logInlinedMethod(info, "intrinsic"); + return InliningUtil.logInlinedMethod(info, fullyProcessed, "intrinsic"); } double inliningBonus = getInliningBonus(info); @@ -604,76 +499,23 @@ * 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 - - // @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 - int nodes = determineNodeCount(info); if (nodes < GraalOptions.TrivialHighLevelGraphSize * inliningBonus) { - return InliningUtil.logInlinedMethod(info, "trivial (nodes=%d)", nodes); + return InliningUtil.logInlinedMethod(info, fullyProcessed, "trivial (nodes=%d)", nodes); } double invokes = determineInvokeProbability(info); - if (GraalOptions.LimitInlinedInvokes > 0 && invokes > GraalOptions.LimitInlinedInvokes * inliningBonus) { + if (GraalOptions.LimitInlinedInvokes > 0 && fullyProcessed && 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); + return InliningUtil.logInlinedMethod(info, fullyProcessed, "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 static int previousHIRSize(InlineInfo info) { - int size = 0; - for (int i = 0; i < info.numberOfMethods(); i++) { - size += compiledMethodInfo(info.methodAt(i)).getHighLevelNodes(); - } - return size; - } - - 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 nodes; - } - - private static double determineInvokeProbability(InlineInfo info) { - double invokeProbability = 0; - for (int i = 0; i < info.numberOfMethods(); i++) { - InlineableElement callee = info.inlineableElementAt(i); - Iterable 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; - } } private static class InliningIterator { @@ -769,15 +611,162 @@ } } - public static class CompiledMethodInfo { + /** + * Holds the data for building the callee graphs recursively: graphs and invocations (each + * invocation can have multiple graphs). + */ + static class InliningData { + + private final ArrayDeque graphQueue; + private final ArrayDeque 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 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 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; + } + + public int inliningDepth() { + return invocationQueue.size(); + } + + @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 invokes) { + int count = 0; + Iterator iterator = invokes.iterator(); + while (iterator.hasNext()) { + iterator.next(); + count++; + } + return count; + } + } + + 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; + } + } + + private 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() { } @@ -786,62 +775,16 @@ return highLevelNodes; } - public int getMidLevelNodes() { - return midLevelNodes; - } - - public int getLowLevelNodes() { - return lowLevelNodes; - } - - public int getCompiledCodeSize() { - return compiledCodeSize; - } - - public double getMaxProbabilityOfRemainingInvokes() { - return maxProbabilityOfRemainingInvokes; + public void setHighLevelNodeCount(int highLevelNodes) { + this.highLevelNodes = highLevelNodes; } 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); - } } } diff -r 197426668a5d -r e538498d6eae graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Wed May 08 17:21:38 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Mon May 13 13:14:17 2013 +0200 @@ -59,7 +59,7 @@ boolean continueInlining(InliningData data); - boolean isWorthInlining(InlineInfo info, double probability, double relevance); + boolean isWorthInlining(InlineInfo info, double probability, double relevance, boolean fullyProcessed); } public static class InlineableMacroNode implements InlineableElement { @@ -114,21 +114,22 @@ } } - public static boolean logInlinedMethod(InlineInfo info, String msg, Object... args) { - logInliningDecision(info, true, msg, args); - return true; + public static boolean logInlinedMethod(InlineInfo info, boolean allowLogging, String msg, Object... args) { + return logInliningDecision(info, allowLogging, true, msg, args); } public static boolean logNotInlinedMethod(InlineInfo info, String msg, Object... args) { - logInliningDecision(info, false, msg, args); - return false; + return logInliningDecision(info, true, false, msg, args); } - public static void logInliningDecision(InlineInfo info, boolean success, String msg, final Object... args) { - printInlining(info, success, msg, args); - if (shouldLogInliningDecision()) { - logInliningDecision(methodName(info), success, msg, args); + public static boolean logInliningDecision(InlineInfo info, boolean allowLogging, boolean success, String msg, final Object... args) { + if (allowLogging) { + printInlining(info, success, msg, args); + if (shouldLogInliningDecision()) { + logInliningDecision(methodName(info), success, msg, args); + } } + return success; } public static void logInliningDecision(final String msg, final Object... args) { @@ -140,7 +141,7 @@ }); } - private static boolean logNotInlinedMethodAndReturnFalse(Invoke invoke, String msg) { + private static boolean logNotInlinedMethod(Invoke invoke, String msg) { if (shouldLogInliningDecision()) { String methodString = invoke.toString() + (invoke.callTarget() == null ? " callTarget=null" : invoke.callTarget().targetName()); logInliningDecision(methodString, false, msg, new Object[0]); @@ -1068,19 +1069,19 @@ // TODO (chaeubl): cleanup this method private static boolean checkInvokeConditions(Invoke invoke) { if (invoke.predecessor() == null || !invoke.asNode().isAlive()) { - return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is dead code"); + return logNotInlinedMethod(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"); + return logNotInlinedMethod(invoke, "the invoke has already been lowered, or has been created as a low-level node"); } else if (((MethodCallTargetNode) invoke.callTarget()).targetMethod() == null) { - return logNotInlinedMethodAndReturnFalse(invoke, "target method is null"); + return logNotInlinedMethod(invoke, "target method is null"); } else if (invoke.stateAfter() == null) { // TODO (chaeubl): why should an invoke not have a state after? - return logNotInlinedMethodAndReturnFalse(invoke, "the invoke has no after state"); + return logNotInlinedMethod(invoke, "the invoke has no after state"); } else if (!invoke.useForInlining()) { - return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is marked to be not used for inlining"); + return logNotInlinedMethod(invoke, "the invoke is marked to be not used for inlining"); } else if (((MethodCallTargetNode) invoke.callTarget()).receiver() != null && ((MethodCallTargetNode) invoke.callTarget()).receiver().isConstant() && ((MethodCallTargetNode) invoke.callTarget()).receiver().asConstant().isNull()) { - return logNotInlinedMethodAndReturnFalse(invoke, "receiver is null"); + return logNotInlinedMethod(invoke, "receiver is null"); } else { return true; } diff -r 197426668a5d -r e538498d6eae graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Wed May 08 17:21:38 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Mon May 13 13:14:17 2013 +0200 @@ -51,9 +51,9 @@ public static float RelevanceCapForInlining = 1f; public static boolean IterativeInlining = ____; - public static int TrivialHighLevelGraphSize = 20; - public static int NormalHighLevelGraphSize = 100; - public static int SmallCompiledGraphSize = 150; + public static int TrivialHighLevelGraphSize = 10; + public static int NormalHighLevelGraphSize = 300; + public static int SmallCompiledGraphSize = 300; public static double LimitInlinedInvokes = 10.0; public static boolean PropagateArgumentsDuringInlining = true;