# HG changeset patch # User Christian Haeubl # Date 1368710185 -7200 # Node ID b5dd7e3c8c80b5b88369dc2274c42d1321045f73 # Parent 65452ead4b71fb1dac675a1add5286a5090ff4ad Bugfixes for the inlining phase and for -XX:+PrintInlining. diff -r 65452ead4b71 -r b5dd7e3c8c80 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 15 14:30:29 2013 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Thu May 16 15:16:25 2013 +0200 @@ -99,27 +99,34 @@ @Override protected void run(final StructuredGraph graph) { - InliningData data = new InliningData(); - data.pushGraph(graph, 1.0, 1.0); + InliningData data = new InliningData(graph, compilationAssumptions); while (data.hasUnprocessedGraphs()) { + MethodInvocation currentInvocation = data.currentInvocation(); GraphInfo graphInfo = data.currentGraph(); - if (graphInfo.hasRemainingInvokes() && inliningPolicy.continueInlining(data)) { + if (!currentInvocation.isRoot() && !inliningPolicy.isWorthInlining(currentInvocation.callee(), data.inliningDepth(), currentInvocation.probability(), currentInvocation.relevance(), false)) { + int remainingGraphs = currentInvocation.totalGraphs() - currentInvocation.processedGraphs(); + assert remainingGraphs > 0; + data.popGraphs(remainingGraphs); + data.popInvocation(); + } else if (graphInfo.hasRemainingInvokes() && inliningPolicy.continueInlining(graphInfo.graph())) { processNextInvoke(data, graphInfo); } else { data.popGraph(); - MethodInvocation currentInvocation = data.currentInvocation(); - if (currentInvocation != null) { + if (!currentInvocation.isRoot()) { assert currentInvocation.callee().invoke().asNode().isAlive(); currentInvocation.incrementProcessedGraphs(); - if (currentInvocation.processedAllGraphs()) { + if (currentInvocation.processedGraphs() == currentInvocation.totalGraphs()) { data.popInvocation(); MethodInvocation parentInvoke = data.currentInvocation(); - tryToInline(data.currentGraph(), currentInvocation, parentInvoke); + tryToInline(data.currentGraph(), currentInvocation, parentInvoke, data.inliningDepth() + 1); } } } } + + assert data.inliningDepth() == 0; + assert data.graphCount() == 0; } /** @@ -128,32 +135,35 @@ private void processNextInvoke(InliningData data, GraphInfo graphInfo) { Invoke invoke = graphInfo.popInvoke(); MethodInvocation callerInvocation = data.currentInvocation(); - Assumptions parentAssumptions = callerInvocation == null ? compilationAssumptions : callerInvocation.assumptions(); + Assumptions parentAssumptions = callerInvocation.assumptions(); InlineInfo info = InliningUtil.getInlineInfo(data, invoke, maxMethodPerInlining, replacements, parentAssumptions, optimisticOpts); - double invokeProbability = graphInfo.invokeProbability(invoke); - double invokeRelevance = graphInfo.invokeRelevance(invoke); - if (info != null && inliningPolicy.isWorthInlining(info, invokeProbability, invokeRelevance, false)) { - MethodInvocation calleeInvocation = data.pushInvocation(info, parentAssumptions, invokeProbability, invokeRelevance); + if (info != null) { + double invokeProbability = graphInfo.invokeProbability(invoke); + double invokeRelevance = graphInfo.invokeRelevance(invoke); + + if (inliningPolicy.isWorthInlining(info, data.inliningDepth(), 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; - data.pushDummyGraph(); + 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; + data.pushDummyGraph(); + } } } } } - private void tryToInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, MethodInvocation parentInvocation) { + private void tryToInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, MethodInvocation parentInvocation, int inliningDepth) { InlineInfo callee = calleeInfo.callee(); - Assumptions callerAssumptions = parentInvocation == null ? compilationAssumptions : parentInvocation.assumptions(); + Assumptions callerAssumptions = parentInvocation.assumptions(); - if (inliningPolicy.isWorthInlining(callee, calleeInfo.probability(), calleeInfo.relevance(), true)) { + if (inliningPolicy.isWorthInlining(callee, inliningDepth, calleeInfo.probability(), calleeInfo.relevance(), true)) { doInline(callerGraphInfo, calleeInfo, callerAssumptions); } else if (optimisticOpts.devirtualizeInvokes()) { callee.tryToDevirtualizeInvoke(runtime, callerAssumptions); @@ -399,32 +409,26 @@ super(replacements, hints); } - public boolean continueInlining(InliningData data) { - if (data.currentGraph().graph().getNodeCount() >= GraalOptions.MaximumDesiredSize) { + public boolean continueInlining(StructuredGraph currentGraph) { + if (currentGraph.getNodeCount() >= GraalOptions.MaximumDesiredSize) { InliningUtil.logInliningDecision("inlining is cut off by MaximumDesiredSize"); metricInliningStoppedByMaxDesiredSize.increment(); return false; } - - MethodInvocation currentInvocation = data.currentInvocation(); - if (currentInvocation == null) { - return true; - } - - return isWorthInlining(currentInvocation.callee(), currentInvocation.probability(), currentInvocation.relevance(), false); + return true; } @Override - public boolean isWorthInlining(InlineInfo info, double probability, double relevance, boolean fullyProcessed) { + public boolean isWorthInlining(InlineInfo info, int inliningDepth, double probability, double relevance, boolean fullyProcessed) { if (isIntrinsic(info)) { - return InliningUtil.logInlinedMethod(info, fullyProcessed, "intrinsic"); + return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "intrinsic"); } double inliningBonus = getInliningBonus(info); int lowLevelGraphSize = previousLowLevelGraphSize(info); if (GraalOptions.SmallCompiledLowLevelGraphSize > 0 && lowLevelGraphSize > GraalOptions.SmallCompiledLowLevelGraphSize * inliningBonus) { - return InliningUtil.logNotInlinedMethod(info, "too large previous low-level graph: %d", lowLevelGraphSize); + return InliningUtil.logNotInlinedMethod(info, inliningDepth, "too large previous low-level graph: %d", lowLevelGraphSize); } /* @@ -436,20 +440,20 @@ int nodes = determineNodeCount(info); if (nodes < GraalOptions.TrivialInliningSize * inliningBonus) { - return InliningUtil.logInlinedMethod(info, fullyProcessed, "trivial (nodes=%d)", nodes); + return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "trivial (nodes=%d)", nodes); } double invokes = determineInvokeProbability(info); if (GraalOptions.LimitInlinedInvokes > 0 && fullyProcessed && invokes > GraalOptions.LimitInlinedInvokes * inliningBonus) { - return InliningUtil.logNotInlinedMethod(info, "invoke probability is too high (%f)", invokes); + return InliningUtil.logNotInlinedMethod(info, inliningDepth, "invoke probability is too high (%f)", invokes); } double maximumNodes = computeMaximumSize(relevance, (int) (GraalOptions.MaximumInliningSize * inliningBonus)); if (nodes < maximumNodes) { - return InliningUtil.logInlinedMethod(info, fullyProcessed, "relevance-based (relevance=%f, nodes=%d)", relevance, nodes); + return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "relevance-based (relevance=%f, nodes=%d)", relevance, nodes); } - return InliningUtil.logNotInlinedMethod(info, "(relevance=%f, probability=%f, bonus=%f)", relevance, probability, inliningBonus); + return InliningUtil.logNotInlinedMethod(info, inliningDepth, "(relevance=%f, probability=%f, bonus=%f)", relevance, probability, inliningBonus); } } @@ -466,8 +470,8 @@ assert start.isAlive(); } - public Stack apply() { - Stack invokes = new Stack<>(); + public LinkedList apply() { + LinkedList invokes = new LinkedList<>(); FixedNode current; forcedQueue(start); @@ -476,7 +480,7 @@ if (current instanceof Invoke) { if (current != start) { - invokes.push((Invoke) current); + invokes.addLast((Invoke) current); } queueSuccessors(current); } else if (current instanceof LoopBeginNode) { @@ -552,22 +556,30 @@ */ static class InliningData { - private static final GraphInfo DummyGraphInfo = new GraphInfo(null, new Stack(), 1.0, 1.0); + private static final GraphInfo DummyGraphInfo = new GraphInfo(null, new LinkedList(), 1.0, 1.0); private final ArrayDeque graphQueue; private final ArrayDeque invocationQueue; - private int maxGraphs = 1; + private int maxGraphs; - public InliningData() { + public InliningData(StructuredGraph rootGraph, Assumptions rootAssumptions) { this.graphQueue = new ArrayDeque<>(); this.invocationQueue = new ArrayDeque<>(); + this.maxGraphs = 1; + + invocationQueue.push(new MethodInvocation(null, rootAssumptions, 1.0, 1.0)); + pushGraph(rootGraph, 1.0, 1.0); + } + + public int graphCount() { + return graphQueue.size(); } public void pushGraph(StructuredGraph graph, double probability, double relevance) { assert !contains(graph); NodeBitMap visitedFixedNodes = graph.createNodeBitMap(); - Stack invokes = new InliningIterator(graph.start(), visitedFixedNodes).apply(); + LinkedList 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; @@ -590,6 +602,13 @@ assert graphQueue.size() <= maxGraphs; } + public void popGraphs(int count) { + assert count >= 0; + for (int i = 0; i < count; i++) { + graphQueue.pop(); + } + } + public MethodInvocation currentInvocation() { return invocationQueue.peek(); } @@ -619,7 +638,8 @@ } public int inliningDepth() { - return invocationQueue.size(); + assert invocationQueue.size() > 0; + return invocationQueue.size() - 1; } @Override @@ -683,9 +703,13 @@ assert processedGraphs <= callee.numberOfMethods(); } - public boolean processedAllGraphs() { + public int processedGraphs() { assert processedGraphs <= callee.numberOfMethods(); - return processedGraphs == callee.numberOfMethods(); + return processedGraphs; + } + + public int totalGraphs() { + return callee.numberOfMethods(); } public InlineInfo callee() { @@ -703,19 +727,23 @@ public double relevance() { return relevance; } + + public boolean isRoot() { + return callee == null; + } } private static class GraphInfo { private final StructuredGraph graph; - private final Stack remainingInvokes; + private final LinkedList remainingInvokes; private final double probability; private final double relevance; private NodesToDoubles nodeProbabilities; private NodesToDoubles nodeRelevance; - public GraphInfo(StructuredGraph graph, Stack invokes, double probability, double relevance) { + public GraphInfo(StructuredGraph graph, LinkedList invokes, double probability, double relevance) { this.graph = graph; this.remainingInvokes = invokes; this.probability = probability; @@ -739,7 +767,7 @@ } public Invoke popInvoke() { - return remainingInvokes.pop(); + return remainingInvokes.removeFirst(); } public void pushInvoke(Invoke invoke) { diff -r 65452ead4b71 -r b5dd7e3c8c80 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 15 14:30:29 2013 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Thu May 16 15:16:25 2013 +0200 @@ -59,9 +59,9 @@ public interface InliningPolicy { - boolean continueInlining(InliningData data); + boolean continueInlining(StructuredGraph graph); - boolean isWorthInlining(InlineInfo info, double probability, double relevance, boolean fullyProcessed); + boolean isWorthInlining(InlineInfo info, int inliningDepth, double probability, double relevance, boolean fullyProcessed); } public static class InlineableMacroNode implements InlineableElement { @@ -90,14 +90,14 @@ /** * Print a HotSpot-style inlining message to the console. */ - private static void printInlining(final InlineInfo info, final boolean success, final String msg, final Object... args) { - printInlining(info.methodAt(0), info.invoke(), success, msg, args); + private static void printInlining(final InlineInfo info, final int inliningDepth, final boolean success, final String msg, final Object... args) { + printInlining(info.methodAt(0), info.invoke(), inliningDepth, success, msg, args); } /** * Print a HotSpot-style inlining message to the console. */ - private static void printInlining(final ResolvedJavaMethod method, final Invoke invoke, final boolean success, final String msg, final Object... args) { + private static void printInlining(final ResolvedJavaMethod method, final Invoke invoke, final int inliningDepth, final boolean success, final String msg, final Object... args) { if (GraalOptions.HotSpotPrintInlining) { final int mod = method.getModifiers(); // 1234567 @@ -108,25 +108,24 @@ TTY.print("%c%c%c%c%c ", ' ', Modifier.isSynchronized(mod) ? 's' : ' ', ' ', ' ', Modifier.isNative(mod) ? 'n' : ' '); TTY.print(" "); // more indent TTY.print(" "); // initial inlining indent - final int level = computeInliningLevel(invoke); - for (int i = 0; i < level; i++) { + for (int i = 0; i < inliningDepth; i++) { TTY.print(" "); } TTY.println(String.format("@ %d %s %s%s", invoke.bci(), methodName(method, null), success ? "" : "not inlining ", String.format(msg, args))); } } - public static boolean logInlinedMethod(InlineInfo info, boolean allowLogging, String msg, Object... args) { - return logInliningDecision(info, allowLogging, true, msg, args); + public static boolean logInlinedMethod(InlineInfo info, int inliningDepth, boolean allowLogging, String msg, Object... args) { + return logInliningDecision(info, inliningDepth, allowLogging, true, msg, args); } - public static boolean logNotInlinedMethod(InlineInfo info, String msg, Object... args) { - return logInliningDecision(info, true, false, msg, args); + public static boolean logNotInlinedMethod(InlineInfo info, int inliningDepth, String msg, Object... args) { + return logInliningDecision(info, inliningDepth, true, false, msg, args); } - public static boolean logInliningDecision(InlineInfo info, boolean allowLogging, boolean success, String msg, final Object... args) { + public static boolean logInliningDecision(InlineInfo info, int inliningDepth, boolean allowLogging, boolean success, String msg, final Object... args) { if (allowLogging) { - printInlining(info, success, msg, args); + printInlining(info, inliningDepth, success, msg, args); if (shouldLogInliningDecision()) { logInliningDecision(methodName(info), success, msg, args); } @@ -151,12 +150,12 @@ return false; } - private static InlineInfo logNotInlinedMethodAndReturnNull(Invoke invoke, ResolvedJavaMethod method, String msg) { - return logNotInlinedMethodAndReturnNull(invoke, method, msg, new Object[0]); + private static InlineInfo logNotInlinedMethodAndReturnNull(Invoke invoke, int inliningDepth, ResolvedJavaMethod method, String msg) { + return logNotInlinedMethodAndReturnNull(invoke, inliningDepth, method, msg, new Object[0]); } - private static InlineInfo logNotInlinedMethodAndReturnNull(Invoke invoke, ResolvedJavaMethod method, String msg, Object... args) { - printInlining(method, invoke, false, msg, args); + private static InlineInfo logNotInlinedMethodAndReturnNull(Invoke invoke, int inliningDepth, ResolvedJavaMethod method, String msg, Object... args) { + printInlining(method, invoke, inliningDepth, false, msg, args); if (shouldLogInliningDecision()) { String methodString = methodName(method, invoke); logInliningDecision(methodString, false, msg, args); @@ -164,8 +163,8 @@ return null; } - private static boolean logNotInlinedMethodAndReturnFalse(Invoke invoke, ResolvedJavaMethod method, String msg) { - printInlining(method, invoke, false, msg, new Object[0]); + private static boolean logNotInlinedMethodAndReturnFalse(Invoke invoke, int inliningDepth, ResolvedJavaMethod method, String msg) { + printInlining(method, invoke, inliningDepth, false, msg, new Object[0]); if (shouldLogInliningDecision()) { String methodString = methodName(method, invoke); logInliningDecision(methodString, false, msg, new Object[0]); @@ -1085,18 +1084,18 @@ TypeProfileProxyNode typeProfileProxyNode = (TypeProfileProxyNode) receiver; typeProfile = typeProfileProxyNode.getProfile(); } else { - return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "no type profile exists"); + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "no type profile exists"); } ProfiledType[] ptypes = typeProfile.getTypes(); if (ptypes == null || ptypes.length <= 0) { - return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "no types in profile"); + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "no types in profile"); } double notRecordedTypeProbability = typeProfile.getNotRecordedProbability(); if (ptypes.length == 1 && notRecordedTypeProbability == 0) { if (!optimisticOpts.inlineMonomorphicCalls()) { - return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "inlining monomorphic calls is disabled"); + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "inlining monomorphic calls is disabled"); } ResolvedJavaType type = ptypes[0].getType(); @@ -1109,12 +1108,12 @@ invoke.setPolymorphic(true); if (!optimisticOpts.inlinePolymorphicCalls() && notRecordedTypeProbability == 0) { - return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "inlining polymorphic calls is disabled (%d types)", ptypes.length); + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "inlining polymorphic calls is disabled (%d types)", ptypes.length); } 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.length, + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.length, notRecordedTypeProbability * 100); } @@ -1135,7 +1134,7 @@ } if (concreteMethods.size() > maxNumberOfMethods) { - return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "polymorphic call with more than %d target methods", maxNumberOfMethods); + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "polymorphic call with more than %d target methods", maxNumberOfMethods); } // Clear methods that fall below the threshold. @@ -1151,7 +1150,8 @@ if (newConcreteMethods.size() == 0) { // No method left that is worth inlining. - return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "no methods remaining after filtering less frequent methods (%d methods previously)", concreteMethods.size()); + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "no methods remaining after filtering less frequent methods (%d methods previously)", + concreteMethods.size()); } concreteMethods = newConcreteMethods; @@ -1174,12 +1174,12 @@ if (usedTypes.size() == 0) { // No type left that is worth checking for. - return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "no types remaining after filtering less frequent types (%d types previously)", ptypes.length); + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "no types remaining after filtering less frequent types (%d types previously)", ptypes.length); } for (ResolvedJavaMethod concrete : concreteMethods) { if (!checkTargetConditions(data, replacements, invoke, concrete, optimisticOpts)) { - return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined"); + return logNotInlinedMethodAndReturnNull(invoke, data.inliningDepth(), targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined"); } } return new MultiTypeGuardInlineInfo(invoke, concreteMethods, concreteMethodsProbabilities, usedTypes, typesToConcretes, notRecordedTypeProbability); @@ -1214,34 +1214,24 @@ private static boolean checkTargetConditions(InliningData data, Replacements replacements, Invoke invoke, ResolvedJavaMethod method, OptimisticOptimizations optimisticOpts) { if (method == null) { - return logNotInlinedMethodAndReturnFalse(invoke, method, "the method is not resolved"); + return logNotInlinedMethodAndReturnFalse(invoke, data.inliningDepth(), method, "the method is not resolved"); } else if (Modifier.isNative(method.getModifiers()) && (!GraalOptions.Intrinsify || !InliningUtil.canIntrinsify(replacements, method))) { - return logNotInlinedMethodAndReturnFalse(invoke, method, "it is a non-intrinsic native method"); + return logNotInlinedMethodAndReturnFalse(invoke, data.inliningDepth(), method, "it is a non-intrinsic native method"); } else if (Modifier.isAbstract(method.getModifiers())) { - return logNotInlinedMethodAndReturnFalse(invoke, method, "it is an abstract method"); + return logNotInlinedMethodAndReturnFalse(invoke, data.inliningDepth(), method, "it is an abstract method"); } else if (!method.getDeclaringClass().isInitialized()) { - return logNotInlinedMethodAndReturnFalse(invoke, method, "the method's class is not initialized"); + return logNotInlinedMethodAndReturnFalse(invoke, data.inliningDepth(), method, "the method's class is not initialized"); } else if (!method.canBeInlined()) { - return logNotInlinedMethodAndReturnFalse(invoke, method, "it is marked non-inlinable"); + return logNotInlinedMethodAndReturnFalse(invoke, data.inliningDepth(), method, "it is marked non-inlinable"); } else if (data.countRecursiveInlining(method) > GraalOptions.MaximumRecursiveInlining) { - return logNotInlinedMethodAndReturnFalse(invoke, method, "it exceeds the maximum recursive inlining depth"); + return logNotInlinedMethodAndReturnFalse(invoke, data.inliningDepth(), method, "it exceeds the maximum recursive inlining depth"); } else if (new OptimisticOptimizations(method).lessOptimisticThan(optimisticOpts)) { - return logNotInlinedMethodAndReturnFalse(invoke, method, "the callee uses less optimistic optimizations than caller"); + return logNotInlinedMethodAndReturnFalse(invoke, data.inliningDepth(), method, "the callee uses less optimistic optimizations than caller"); } else { return true; } } - private static int computeInliningLevel(Invoke invoke) { - int count = -1; - FrameState curState = invoke.stateAfter(); - while (curState != null) { - count++; - curState = curState.outerFrameState(); - } - return count; - } - static MonitorExitNode findPrecedingMonitorExit(UnwindNode unwind) { Node pred = unwind.predecessor(); while (pred != null) {