# HG changeset patch # User Thomas Wuerthinger # Date 1379430327 -7200 # Node ID 524d0a0a47b8e8f7d4002998eb3a2159b02c6c8d # Parent f7a09339e29bc8695d4bd1027250c6bb069875b8 New algorithm for Truffle tree expansion. diff -r f7a09339e29b -r 524d0a0a47b8 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java Tue Sep 17 16:22:17 2013 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java Tue Sep 17 17:05:27 2013 +0200 @@ -26,6 +26,7 @@ import static com.oracle.graal.phases.GraalOptions.*; import static com.oracle.graal.truffle.TruffleCompilerOptions.*; +import java.lang.reflect.*; import java.util.*; import com.oracle.graal.api.code.*; @@ -169,6 +170,11 @@ InliningPhase inliningPhase = new InliningPhase(canonicalizer); inliningPhase.apply(graph, context); + for (MethodCallTargetNode mctn : graph.getNodes(MethodCallTargetNode.class)) { + String methodName = mctn.targetName(); + // System.out.println("remaining invoke: " + methodName); + } + for (NeverPartOfCompilationNode neverPartOfCompilationNode : graph.getNodes(NeverPartOfCompilationNode.class)) { Throwable exception = new VerificationError(neverPartOfCompilationNode.getMessage()); throw GraphUtil.approxSourceException(neverPartOfCompilationNode, exception); @@ -199,43 +205,46 @@ return graph; } - private void expandTree(GraphBuilderConfiguration config, StructuredGraph graph, NewFrameNode newFrameNode, Assumptions assumptions) { + private void expandTree(@SuppressWarnings("unused") GraphBuilderConfiguration config, StructuredGraph graph, NewFrameNode newFrameNode, Assumptions assumptions) { + PhaseContext context = new PhaseContext(metaAccessProvider, assumptions, replacements); boolean changed; do { changed = false; - for (Node usage : newFrameNode.usages().snapshot()) { - if (usage instanceof MethodCallTargetNode && !usage.isDeleted()) { - MethodCallTargetNode methodCallTargetNode = (MethodCallTargetNode) usage; - InvokeKind kind = methodCallTargetNode.invokeKind(); - if (kind == InvokeKind.Special || kind == InvokeKind.Static) { - if (TruffleInlinePrinter.getValue()) { - InlinePrinterProcessor.addInlining(MethodHolder.getNewTruffleExecuteMethod(methodCallTargetNode)); + for (MethodCallTargetNode methodCallTargetNode : graph.getNodes(MethodCallTargetNode.class)) { + InvokeKind kind = methodCallTargetNode.invokeKind(); + if (kind == InvokeKind.Static || (kind == InvokeKind.Special && methodCallTargetNode.receiver().isConstant())) { + if (TruffleInlinePrinter.getValue()) { + InlinePrinterProcessor.addInlining(MethodHolder.getNewTruffleExecuteMethod(methodCallTargetNode)); + } + if (TraceTruffleCompilationDetails.getValue() && kind == InvokeKind.Special) { + ConstantNode constantNode = (ConstantNode) methodCallTargetNode.arguments().first(); + constantReceivers.add(constantNode.asConstant()); + } + StructuredGraph inlineGraph = replacements.getMethodSubstitution(methodCallTargetNode.targetMethod()); + + if (inlineGraph == null) { + Class macroSubstitution = replacements.getMacroSubstitution(methodCallTargetNode.targetMethod()); + if (macroSubstitution != null) { + InliningUtil.inlineMacroNode(methodCallTargetNode.invoke(), methodCallTargetNode.targetMethod(), methodCallTargetNode.graph(), macroSubstitution); + changed = true; + continue; } - if (TraceTruffleCompilationDetails.getValue() && kind == InvokeKind.Special && methodCallTargetNode.arguments().first() instanceof ConstantNode) { - ConstantNode constantNode = (ConstantNode) methodCallTargetNode.arguments().first(); - constantReceivers.add(constantNode.asConstant()); - } - StructuredGraph inlineGraph = replacements.getMethodSubstitution(methodCallTargetNode.targetMethod()); - NewFrameNode otherNewFrame = null; - if (inlineGraph == null) { - inlineGraph = parseGraph(methodCallTargetNode.targetMethod(), methodCallTargetNode.arguments(), assumptions); - otherNewFrame = inlineGraph.getNodes(NewFrameNode.class).first(); - } + } + + if (inlineGraph == null && !Modifier.isNative(methodCallTargetNode.targetMethod().getModifiers())) { + inlineGraph = parseGraph(methodCallTargetNode.targetMethod(), methodCallTargetNode.arguments(), assumptions, context); + } + if (inlineGraph != null) { int nodeCountBefore = graph.getNodeCount(); - Map mapping = InliningUtil.inline(methodCallTargetNode.invoke(), inlineGraph, false); + int mark = graph.getMark(); + InliningUtil.inline(methodCallTargetNode.invoke(), inlineGraph, false); + canonicalizer.applyIncremental(graph, context, mark); if (Debug.isDumpEnabled()) { int nodeCountAfter = graph.getNodeCount(); Debug.dump(graph, "After inlining %s %+d (%d)", methodCallTargetNode.targetMethod().toString(), nodeCountAfter - nodeCountBefore, nodeCountAfter); } changed = true; - - if (otherNewFrame != null) { - otherNewFrame = (NewFrameNode) mapping.get(otherNewFrame); - if (otherNewFrame.isAlive() && otherNewFrame.usages().isNotEmpty()) { - expandTree(config, graph, otherNewFrame, assumptions); - } - } } } @@ -243,52 +252,68 @@ throw new BailoutException("Truffle compilation is exceeding maximum node count: " + graph.getNodeCount()); } } - } while (changed && newFrameNode.isAlive() && newFrameNode.usages().isNotEmpty()); + } while (changed); } - private StructuredGraph parseGraph(final ResolvedJavaMethod targetMethod, final NodeInputList arguments, final Assumptions assumptions) { + private StructuredGraph parseGraph(final ResolvedJavaMethod targetMethod, final NodeInputList arguments, final Assumptions assumptions, final PhaseContext context) { - final StructuredGraph graph = truffleCache.lookup(targetMethod, arguments, assumptions, canonicalizer); - Debug.scope("parseGraph", targetMethod, new Runnable() { + StructuredGraph graph = truffleCache.lookup(targetMethod, arguments, assumptions, canonicalizer); - @Override - public void run() { + if (targetMethod.getAnnotation(ExplodeLoop.class) != null) { + assert graph.hasLoops(); + final StructuredGraph graphCopy = graph.copy(); + final List modifiedNodes = new ArrayList<>(); + for (LocalNode local : graphCopy.getNodes(LocalNode.class)) { + ValueNode arg = arguments.get(local.index()); + if (arg.isConstant()) { + Constant constant = arg.asConstant(); + ConstantNode constantNode = ConstantNode.forConstant(constant, metaAccessProvider, graphCopy); + local.replaceAndDelete(constantNode); + for (Node usage : constantNode.usages()) { + if (usage instanceof Canonicalizable) { + modifiedNodes.add(usage); + } + } + } + } + Debug.scope("TruffleUnrollLoop", targetMethod, new Runnable() { - if (graph.hasLoops()) { + @Override + public void run() { + + canonicalizer.applyIncremental(graphCopy, context, modifiedNodes); boolean unrolled; do { unrolled = false; - LoopsData loopsData = new LoopsData(graph); + LoopsData loopsData = new LoopsData(graphCopy); loopsData.detectedCountedLoops(); for (LoopEx ex : innerLoopsFirst(loopsData.countedLoops())) { if (ex.counted().isConstantMaxTripCount()) { long constant = ex.counted().constantMaxTripCount(); - if (constant <= TruffleConstantUnrollLimit.getValue() || targetMethod.getAnnotation(ExplodeLoop.class) != null) { - PhaseContext context = new PhaseContext(metaAccessProvider, assumptions, replacements); - LoopTransformations.fullUnroll(ex, context, canonicalizer); - Debug.dump(graph, "After loop unrolling %d times", constant); - unrolled = true; - break; - } + LoopTransformations.fullUnroll(ex, context, canonicalizer); + Debug.dump(graphCopy, "After loop unrolling %d times", constant); + unrolled = true; + break; } } } while (unrolled); } - } - private List innerLoopsFirst(Collection loops) { - ArrayList sortedLoops = new ArrayList<>(loops); - Collections.sort(sortedLoops, new Comparator() { + private List innerLoopsFirst(Collection loops) { + ArrayList sortedLoops = new ArrayList<>(loops); + Collections.sort(sortedLoops, new Comparator() { - @Override - public int compare(LoopEx o1, LoopEx o2) { - return o2.lirLoop().depth - o1.lirLoop().depth; - } - }); - return sortedLoops; - } - }); - - return graph; + @Override + public int compare(LoopEx o1, LoopEx o2) { + return o2.lirLoop().depth - o1.lirLoop().depth; + } + }); + return sortedLoops; + } + }); + return graphCopy; + } else { + return graph; + } } } diff -r f7a09339e29b -r 524d0a0a47b8 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluatorCanonicalizer.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluatorCanonicalizer.java Tue Sep 17 16:22:17 2013 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluatorCanonicalizer.java Tue Sep 17 17:05:27 2013 +0200 @@ -24,6 +24,8 @@ import java.lang.reflect.*; +import sun.misc.*; + import com.oracle.graal.api.meta.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; @@ -51,8 +53,20 @@ return ConstantNode.forConstant(constant, metaAccessProvider, node.graph()); } } + } else if (node instanceof LoadIndexedNode) { + LoadIndexedNode loadIndexedNode = (LoadIndexedNode) node; + if (loadIndexedNode.array().isConstant() && !loadIndexedNode.array().isNullConstant() && loadIndexedNode.index().isConstant()) { + Object array = loadIndexedNode.array().asConstant().asObject(); + long index = loadIndexedNode.index().asConstant().asLong(); + if (index >= 0 && index < Array.getLength(array)) { + int arrayBaseOffset = Unsafe.getUnsafe().arrayBaseOffset(array.getClass()); + int arrayIndexScale = Unsafe.getUnsafe().arrayIndexScale(array.getClass()); + Constant constant = metaAccessProvider.readUnsafeConstant(loadIndexedNode.elementKind(), array, arrayBaseOffset + index * arrayIndexScale, + loadIndexedNode.elementKind() == Kind.Object); + return ConstantNode.forConstant(constant, metaAccessProvider, loadIndexedNode.graph()); + } + } } - return node; } diff -r f7a09339e29b -r 524d0a0a47b8 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCache.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCache.java Tue Sep 17 16:22:17 2013 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCache.java Tue Sep 17 17:05:27 2013 +0200 @@ -131,71 +131,7 @@ } }); } - - // histogram.add(resultGraph); - - final StructuredGraph clonedResultGraph = resultGraph.copy(); - - Debug.sandbox("TruffleCacheConstants", new Object[]{metaAccessProvider, method}, DebugScope.getConfig(), new Runnable() { - - public void run() { - - Debug.dump(clonedResultGraph, "before applying constants"); - List modifiedLocals = new ArrayList<>(arguments.size()); - // Pass on constant arguments. - for (LocalNode local : clonedResultGraph.getNodes(LocalNode.class)) { - ValueNode arg = arguments.get(local.index()); - if (arg.isConstant()) { - Constant constant = arg.asConstant(); - ConstantNode constantNode = ConstantNode.forConstant(constant, metaAccessProvider, clonedResultGraph); - local.replaceAndDelete(constantNode); - modifiedLocals.add(constantNode); - } else if (!local.stamp().equals(arg.stamp())) { - local.setStamp(arg.stamp()); - modifiedLocals.add(local); - } - } - Debug.dump(clonedResultGraph, "after applying constants"); - List modifiedLocalsUsages = new ArrayList<>(modifiedLocals.size() * 2); - for (Node local : modifiedLocals) { - for (Node usage : local.usages()) { - if (usage instanceof Canonicalizable) { - modifiedLocalsUsages.add(usage); - } - } - } - optimizeGraph(clonedResultGraph, assumptions, modifiedLocalsUsages); - - modifiedLocalsUsages.clear(); - for (Node local : modifiedLocals) { - for (Node usage : local.usages()) { - if (usage instanceof Canonicalizable) { - modifiedLocalsUsages.add(usage); - } - } - } - - int newNodesMark = clonedResultGraph.getMark(); - new ReplaceLoadFinalPhase().apply(clonedResultGraph); - for (Node n : clonedResultGraph.getNewNodes(newNodesMark)) { - if (n instanceof Canonicalizable) { - modifiedLocalsUsages.add(n); - } - } - finalCanonicalizer.applyIncremental(clonedResultGraph, new PhaseContext(metaAccessProvider, assumptions, replacements), modifiedLocalsUsages); - - for (Node n : clonedResultGraph.getNodes()) { - if (n instanceof LoadFieldNode) { - LoadFieldNode loadFieldNode = (LoadFieldNode) n; - if (loadFieldNode.field().getAnnotation(Child.class) != null) { - throw new RuntimeException("found remaining child load field "); - } - - } - } - } - }); - return clonedResultGraph; + return resultGraph; } private void optimizeGraph(StructuredGraph newGraph, Assumptions assumptions, Iterable changedNodes) {