Mercurial > hg > truffle
changeset 16318:31db7b7374f0
Merge
line wrap: on
line diff
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Mon Jun 02 21:00:37 2014 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Mon Jun 02 21:08:05 2014 +0200 @@ -121,10 +121,12 @@ } } - private void grow() { + public void grow() { nodeCount = Math.max(nodeCount, graph().nodeIdCount()); int newLength = Math.max((bits.length * 3 / 2) + 1, sizeForNodeCount(nodeCount)); - bits = Arrays.copyOf(bits, newLength); + if (newLength > bits.length) { + bits = Arrays.copyOf(bits, newLength); + } } private boolean check(Node node, boolean grow) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningPhase.java Mon Jun 02 21:00:37 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningPhase.java Mon Jun 02 21:08:05 2014 +0200 @@ -140,8 +140,10 @@ protected void run(final StructuredGraph graph, final HighTierContext context) { final InliningData data = new InliningData(graph, context, maxMethodPerInlining, canonicalizer, inliningPolicy); + assert data.repOK(); while (data.hasUnprocessedGraphs()) { boolean wasInlined = data.moveForward(); + assert data.repOK(); if (wasInlined) { inliningCount++; }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/info/elem/InlineableGraph.java Mon Jun 02 21:00:37 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/info/elem/InlineableGraph.java Mon Jun 02 21:08:05 2014 +0200 @@ -45,56 +45,38 @@ this.graph = buildGraph(method, invoke, context, canonicalizer); } + /** + * @return a (possibly cached) graph. The caller is responsible for cloning before modification. + */ + private static StructuredGraph getOriginalGraph(final ResolvedJavaMethod method, final HighTierContext context) { + StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(context.getReplacements(), method); + if (intrinsicGraph != null) { + return intrinsicGraph; + } + StructuredGraph cachedGraph = getCachedGraph(method, context); + if (cachedGraph != null) { + return cachedGraph; + } + return null; + } + private static StructuredGraph buildGraph(final ResolvedJavaMethod method, final Invoke invoke, final HighTierContext context, CanonicalizerPhase canonicalizer) { - final StructuredGraph newGraph; - final boolean parseBytecodes; + StructuredGraph newGraph = getOriginalGraph(method, context); + if (newGraph == null) { + newGraph = new StructuredGraph(method); + parseBytecodes(newGraph, context, canonicalizer); + } + newGraph = newGraph.copy(); // TODO (chaeubl): copying the graph is only necessary if it is modified or if it contains // any invokes - StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(context.getReplacements(), method); - if (intrinsicGraph != null) { - newGraph = intrinsicGraph.copy(); - parseBytecodes = false; - } else { - StructuredGraph cachedGraph = getCachedGraph(method, context); - if (cachedGraph != null) { - newGraph = cachedGraph.copy(); - parseBytecodes = false; - } else { - newGraph = new StructuredGraph(method); - parseBytecodes = true; - } - } try (Debug.Scope s = Debug.scope("InlineGraph", newGraph)) { - if (parseBytecodes) { - parseBytecodes(newGraph, context, canonicalizer); - } - boolean callerHasMoreInformationAboutArguments = false; - NodeInputList<ValueNode> args = invoke.callTarget().arguments(); - ArrayList<Node> parameterUsages = new ArrayList<>(); - for (ParameterNode param : newGraph.getNodes(ParameterNode.class).snapshot()) { - ValueNode arg = args.get(param.index()); - if (arg.isConstant()) { - Constant constant = arg.asConstant(); - newGraph.replaceFloating(param, ConstantNode.forConstant(constant, context.getMetaAccess(), newGraph)); - callerHasMoreInformationAboutArguments = true; - param.usages().snapshotTo(parameterUsages); - } else { - Stamp joinedStamp = param.stamp().join(arg.stamp()); - if (joinedStamp != null && !joinedStamp.equals(param.stamp())) { - param.setStamp(joinedStamp); - callerHasMoreInformationAboutArguments = true; - param.usages().snapshotTo(parameterUsages); - } - } - } - - if (callerHasMoreInformationAboutArguments) { - if (OptCanonicalizer.getValue()) { - canonicalizer.applyIncremental(newGraph, context, parameterUsages); - } + ArrayList<Node> parameterUsages = replaceParamsWithMoreInformativeArguments(invoke, newGraph, context); + if (parameterUsages != null && OptCanonicalizer.getValue()) { + assert !parameterUsages.isEmpty() : "The caller didn't have more information about arguments after all"; + canonicalizer.applyIncremental(newGraph, context, parameterUsages); } else { // 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 @@ -107,6 +89,67 @@ } } + private static boolean isArgMoreInformativeThanParam(ValueNode arg, ParameterNode param) { + if (arg.isConstant()) { + return true; + } else { + Stamp joinedStamp = param.stamp().join(arg.stamp()); + if (joinedStamp != null && !joinedStamp.equals(param.stamp())) { + return true; + } + } + return false; + } + + /** + * This method detects: + * <ul> + * <li> + * constants among the arguments to the <code>invoke</code></li> + * <li> + * arguments with more precise type than that declared by the corresponding parameter</li> + * </ul> + * + * <p> + * The corresponding parameters are updated to reflect the above information. Before doing so, + * their usages are added to <code>parameterUsages</code> for later incremental + * canonicalization. + * </p> + * + * @return null if no incremental canonicalization is need, a list of nodes for such + * canonicalization otherwise. + */ + private static ArrayList<Node> replaceParamsWithMoreInformativeArguments(final Invoke invoke, final StructuredGraph newGraph, final HighTierContext context) { + NodeInputList<ValueNode> args = invoke.callTarget().arguments(); + ArrayList<Node> parameterUsages = null; + for (ParameterNode param : newGraph.getNodes(ParameterNode.class).snapshot()) { + if (param.usages().isNotEmpty()) { + ValueNode arg = args.get(param.index()); + if (arg.isConstant()) { + Constant constant = arg.asConstant(); + parameterUsages = trackParameterUsages(param, parameterUsages); + // collect param usages before replacing the param + newGraph.replaceFloating(param, ConstantNode.forConstant(constant, context.getMetaAccess(), newGraph)); + } else { + Stamp joinedStamp = param.stamp().join(arg.stamp()); + if (joinedStamp != null && !joinedStamp.equals(param.stamp())) { + param.setStamp(joinedStamp); + parameterUsages = trackParameterUsages(param, parameterUsages); + } else { + assert !isArgMoreInformativeThanParam(arg, param); + } + } + } + } + return parameterUsages; + } + + private static ArrayList<Node> trackParameterUsages(ParameterNode param, ArrayList<Node> parameterUsages) { + ArrayList<Node> result = (parameterUsages == null) ? new ArrayList<>() : parameterUsages; + param.usages().snapshotTo(result); + return result; + } + private static StructuredGraph getCachedGraph(ResolvedJavaMethod method, HighTierContext context) { if (context.getGraphCache() != null) { StructuredGraph cachedGraph = context.getGraphCache().get(method); @@ -119,24 +162,29 @@ /** * This method builds the IR nodes for <code>newGraph</code> and canonicalizes them. Provided - * profiling info is mature, the resulting graph is cached. + * profiling info is mature, the resulting graph is cached. The caller is responsible for + * cloning before modification.</p> */ private static StructuredGraph parseBytecodes(StructuredGraph newGraph, HighTierContext context, CanonicalizerPhase canonicalizer) { - if (context.getGraphBuilderSuite() != null) { - context.getGraphBuilderSuite().apply(newGraph, context); - } - assert newGraph.start().next() != null : "graph needs to be populated the GraphBuilderSuite"; + try (Debug.Scope s = Debug.scope("InlineGraph", newGraph)) { + if (context.getGraphBuilderSuite() != null) { + context.getGraphBuilderSuite().apply(newGraph, context); + } + assert newGraph.start().next() != null : "graph needs to be populated by the GraphBuilderSuite"; - new DeadCodeEliminationPhase().apply(newGraph); + new DeadCodeEliminationPhase().apply(newGraph); - if (OptCanonicalizer.getValue()) { - canonicalizer.apply(newGraph, context); - } + if (OptCanonicalizer.getValue()) { + canonicalizer.apply(newGraph, context); + } - if (context.getGraphCache() != null) { - context.getGraphCache().put(newGraph.method(), newGraph.copy()); + if (context.getGraphCache() != null) { + context.getGraphCache().put(newGraph.method(), newGraph); + } + return newGraph; + } catch (Throwable e) { + throw Debug.handle(e); } - return newGraph; } @Override
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/InliningData.java Mon Jun 02 21:00:37 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/InliningData.java Mon Jun 02 21:08:05 2014 +0200 @@ -380,6 +380,7 @@ */ private boolean tryToInline(CallsiteHolder callerCallsiteHolder, MethodInvocation calleeInvocation, MethodInvocation parentInvocation, int inliningDepth) { InlineInfo calleeInfo = calleeInvocation.callee(); + assert iterContains(callerCallsiteHolder.graph().getInvokes(), calleeInfo.invoke()); Assumptions callerAssumptions = parentInvocation.assumptions(); metricInliningConsidered.increment(); @@ -395,6 +396,15 @@ return false; } + private static <T> boolean iterContains(Iterable<T> in, T elem) { + for (T i : in) { + if (i == elem) { + return true; + } + } + return false; + } + /** * Process the next invoke and enqueue all its graphs for processing. */ @@ -585,6 +595,10 @@ assert currentInvocation.callee().invoke().asNode().isAlive(); currentInvocation.incrementProcessedGraphs(); if (currentInvocation.processedGraphs() == currentInvocation.totalGraphs()) { + /* + * "all of currentInvocation's graphs processed" amounts to + * "all concrete methods that come into question already had the callees they contain analyzed for inlining" + */ popInvocation(); final MethodInvocation parentInvoke = currentInvocation(); try (Debug.Scope s = Debug.scope("Inlining", inliningContext())) { @@ -596,4 +610,48 @@ return false; } + + /** + * This method checks an invariant that {@link #moveForward()} must maintain: "the top + * invocation records how many concrete target methods (for it) remain on the + * {@link #graphQueue}; those targets 'belong' to the current invocation in question." + */ + private boolean topGraphsForTopInvocation() { + if (invocationQueue.isEmpty()) { + assert graphQueue.isEmpty(); + return true; + } + if (currentInvocation().isRoot()) { + if (!graphQueue.isEmpty()) { + assert graphQueue.size() == 1; + } + return true; + } + final int remainingGraphs = currentInvocation().totalGraphs() - currentInvocation().processedGraphs(); + final Iterator<CallsiteHolder> iter = graphQueue.iterator(); + for (int i = (remainingGraphs - 1); i >= 0; i--) { + if (!iter.hasNext()) { + assert false; + return false; + } + CallsiteHolder queuedTargetCH = iter.next(); + Inlineable targetIE = currentInvocation().callee().inlineableElementAt(i); + if (targetIE instanceof InlineableMacroNode) { + assert queuedTargetCH == DUMMY_CALLSITE_HOLDER; + } else { + InlineableGraph targetIG = (InlineableGraph) targetIE; + assert queuedTargetCH.method().equals(targetIG.getGraph().method()); + } + } + return true; + } + + /** + * This method checks invariants for this class. Named after shorthand for + * "internal representation is ok". + */ + public boolean repOK() { + assert topGraphsForTopInvocation(); + return true; + } }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/FixedNodeProbabilityCache.java Mon Jun 02 21:00:37 2014 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/FixedNodeProbabilityCache.java Mon Jun 02 21:08:05 2014 +0200 @@ -32,8 +32,7 @@ import com.oracle.graal.nodes.*; /** - * Compute probabilities for fixed nodes on the fly and cache at {@link BeginNode}s and - * {@link ControlSplitNode}s. + * Compute probabilities for fixed nodes on the fly and cache them at {@link BeginNode}s. */ public class FixedNodeProbabilityCache implements ToDoubleFunction<FixedNode> { @@ -41,15 +40,44 @@ private final Map<FixedNode, Double> cache = newIdentityMap(); + /** + * <p> + * Given a {@link FixedNode} this method finds the most immediate {@link BeginNode} preceding it + * that either: + * <ul> + * <li>has no predecessor (ie, the begin-node is a merge, in particular a loop-begin, or the + * start-node)</li> + * <li>has a control-split predecessor</li> + * </ul> + * </p> + * + * <p> + * The thus found {@link BeginNode} is equi-probable with the {@link FixedNode} it was obtained + * from. When computed for the first time (afterwards a cache lookup returns it) that + * probability is computed as follows, again depending on the begin-node's predecessor: + * <ul> + * <li>No predecessor. In this case the begin-node is either:</li> + * <ul> + * <li>a merge-node, whose probability adds up those of its forward-ends</li> + * <li>a loop-begin, with probability as above multiplied by the loop-frequency</li> + * </ul> + * <li>Control-split predecessor: probability of the branch times that of the control-split</li> + * </ul> + * </p> + * + * <p> + * As an exception to all the above, a probability of 1 is assumed for a {@link FixedNode} that + * appears to be dead-code (ie, lacks a predecessor). + * </p> + * + */ public double applyAsDouble(FixedNode node) { assert node != null; metricComputeNodeProbability.increment(); FixedNode current = node; while (true) { - if (current == null) { - return 1D; - } + assert current != null; Node predecessor = current.predecessor(); if (current instanceof BeginNode) { if (predecessor == null) { @@ -65,6 +93,7 @@ current = (FixedNode) predecessor; } + assert current instanceof BeginNode; Double cachedValue = cache.get(current); if (cachedValue != null) { return cachedValue;