Mercurial > hg > truffle
changeset 9234:b9cf7d0b598e
removal of FixedNode.probability (draft)
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Mon Apr 22 13:29:55 2013 +0200 @@ -66,11 +66,11 @@ * * @return sorted list of blocks */ - public static List<Block> computeLinearScanOrder(int blockCount, Block startBlock) { + public static List<Block> computeLinearScanOrder(int blockCount, Block startBlock, NodeProbabilities nodeProbabilities) { List<Block> order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks); - computeLinearScanOrder(order, worklist, visitedBlocks); + PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); + computeLinearScanOrder(order, worklist, visitedBlocks, nodeProbabilities); assert checkOrder(order, blockCount); return order; } @@ -80,11 +80,11 @@ * * @return sorted list of blocks */ - public static List<Block> computeCodeEmittingOrder(int blockCount, Block startBlock) { + public static List<Block> computeCodeEmittingOrder(int blockCount, Block startBlock, NodeProbabilities nodeProbabilities) { List<Block> order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks); - computeCodeEmittingOrder(order, worklist, visitedBlocks); + PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); + computeCodeEmittingOrder(order, worklist, visitedBlocks, nodeProbabilities); assert checkOrder(order, blockCount); return order; } @@ -92,28 +92,28 @@ /** * Iteratively adds paths to the code emission block order. */ - private static void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + private static void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { while (!worklist.isEmpty()) { Block nextImportantPath = worklist.poll(); - addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks); + addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); } } /** * Iteratively adds paths to the linear scan block order. */ - private static void computeLinearScanOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + private static void computeLinearScanOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { while (!worklist.isEmpty()) { Block nextImportantPath = worklist.poll(); - addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks); + addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); } } /** * Initializes the priority queue used for the work list of blocks and adds the start block. */ - private static PriorityQueue<Block> initializeWorklist(Block startBlock, BitSet visitedBlocks) { - PriorityQueue<Block> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, blockComparator); + private static PriorityQueue<Block> initializeWorklist(Block startBlock, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { + PriorityQueue<Block> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(nodeProbabilities)); result.add(startBlock); visitedBlocks.set(startBlock.getId()); return result; @@ -122,10 +122,10 @@ /** * Add a linear path to the linear scan order greedily following the most likely successor. */ - private static void addPathToLinearScanOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + private static void addPathToLinearScanOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { block.setLinearScanNumber(order.size()); order.add(block); - Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks); + Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); enqueueSuccessors(block, worklist, visitedBlocks); if (mostLikelySuccessor != null) { if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) { @@ -134,24 +134,24 @@ double unscheduledSum = 0.0; for (Block pred : mostLikelySuccessor.getPredecessors()) { if (pred.getLinearScanNumber() == -1) { - unscheduledSum += pred.getBeginNode().probability(); + unscheduledSum += nodeProbabilities.getProbability(pred.getBeginNode()); } } - if (unscheduledSum > block.getProbability() / PENALTY_VERSUS_UNSCHEDULED) { + if (unscheduledSum > nodeProbabilities.getProbability(block.getBeginNode()) / PENALTY_VERSUS_UNSCHEDULED) { // Add this merge only after at least one additional predecessor gets scheduled. visitedBlocks.clear(mostLikelySuccessor.getId()); return; } } - addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks); + addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks, nodeProbabilities); } } /** * Add a linear path to the code emission order greedily following the most likely successor. */ - private static void addPathToCodeEmittingOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + private static void addPathToCodeEmittingOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { // Skip loop headers if there is only a single loop end block to make the backward jump be a // conditional jump. @@ -180,10 +180,10 @@ } } - Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks); + Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); enqueueSuccessors(block, worklist, visitedBlocks); if (mostLikelySuccessor != null) { - addPathToCodeEmittingOrder(mostLikelySuccessor, order, worklist, visitedBlocks); + addPathToCodeEmittingOrder(mostLikelySuccessor, order, worklist, visitedBlocks, nodeProbabilities); } } @@ -198,11 +198,12 @@ /** * Find the highest likely unvisited successor block of a given block. */ - private static Block findAndMarkMostLikelySuccessor(Block block, BitSet visitedBlocks) { + private static Block findAndMarkMostLikelySuccessor(Block block, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { Block result = null; for (Block successor : block.getSuccessors()) { - assert successor.getProbability() >= 0.0 : "Probabilities must be positive"; - if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || successor.getProbability() >= result.getProbability())) { + assert nodeProbabilities.getProbability(successor.getBeginNode()) >= 0.0 : "Probabilities must be positive"; + if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && + (result == null || nodeProbabilities.getProbability(successor.getBeginNode()) >= nodeProbabilities.getProbability(result.getBeginNode()))) { result = successor; } } @@ -243,7 +244,13 @@ /** * Comparator for sorting blocks based on loop depth and probability. */ - private static Comparator<Block> blockComparator = new Comparator<Block>() { + private static class BlockOrderComparator implements Comparator<Block> { + + private final NodeProbabilities probabilities; + + public BlockOrderComparator(NodeProbabilities probabilities) { + this.probabilities = probabilities; + } @Override public int compare(Block a, Block b) { @@ -254,11 +261,11 @@ } // Blocks with high probability before blocks with low probability. - if (a.getProbability() > b.getProbability()) { + if (probabilities.getProbability(a.getBeginNode()) > probabilities.getProbability(b.getBeginNode())) { return -1; } else { return 1; } } - }; + } }
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/BoxingEliminationTest.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/BoxingEliminationTest.java Mon Apr 22 13:29:55 2013 +0200 @@ -306,7 +306,6 @@ private void processMethod(final String snippet) { graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions); new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph); @@ -325,7 +324,6 @@ public void run() { graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions); new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Mon Apr 22 13:29:55 2013 +0200 @@ -218,9 +218,6 @@ public ReturnNode call() { new GraphBuilderPhase(runtime, GraphBuilderConfiguration.getEagerDefault(), OptimisticOptimizations.ALL).apply(graph); - for (Invoke n : graph.getInvokes()) { - n.setInliningRelevance(1); - } Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/IterativeInliningTest.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/IterativeInliningTest.java Mon Apr 22 13:29:55 2013 +0200 @@ -33,7 +33,6 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.virtual.phases.ea.*; @@ -101,7 +100,6 @@ private void processMethod(final String snippet) { graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); GraalOptions.OptEarlyReadElimination = true; HighTierContext context = new HighTierContext(runtime(), new Assumptions(false)); new IterativeInliningPhase(replacements, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL, false).apply(graph, context);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java Mon Apr 22 13:29:55 2013 +0200 @@ -221,7 +221,6 @@ private void processMethod(final String snippet) { graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions); new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Mon Apr 22 13:29:55 2013 +0200 @@ -33,6 +33,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; @@ -131,10 +132,12 @@ try { Assert.assertTrue("partial escape analysis should have removed all NewInstanceNode allocations", result.getNodes(NewInstanceNode.class).isEmpty()); Assert.assertTrue("partial escape analysis should have removed all NewArrayNode allocations", result.getNodes(NewArrayNode.class).isEmpty()); + + NodeProbabilities nodeProbabilities = new ComputeProbabilityClosure(result).run(); double probabilitySum = 0; int materializeCount = 0; for (MaterializeObjectNode materialize : result.getNodes(MaterializeObjectNode.class)) { - probabilitySum += materialize.probability(); + probabilitySum += nodeProbabilities.getProbability(materialize); materializeCount++; } Assert.assertEquals("unexpected number of MaterializeObjectNodes", expectedCount, materializeCount); @@ -156,10 +159,7 @@ @Override public StructuredGraph call() { StructuredGraph graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); - for (Invoke n : graph.getInvokes()) { - n.asNode().setProbability(100000); - } + Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions); new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/inlining/InliningTest.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/inlining/InliningTest.java Mon Apr 22 13:29:55 2013 +0200 @@ -158,7 +158,6 @@ StructuredGraph graph = eagerInfopointMode ? parseDebug(method) : parse(method); PhasePlan phasePlan = getDefaultPhasePlan(eagerInfopointMode); Assumptions assumptions = new Assumptions(true); - new ComputeProbabilityPhase().apply(graph); Debug.dump(graph, "Graph"); new InliningPhase(runtime(), null, replacements, assumptions, null, phasePlan, OptimisticOptimizations.ALL).apply(graph); Debug.dump(graph, "Graph");
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Apr 22 13:29:55 2013 +0200 @@ -99,8 +99,8 @@ * * @param target */ - public static LIR emitHIR(GraalCodeCacheProvider runtime, TargetDescription target, StructuredGraph graph, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, - OptimisticOptimizations optimisticOpts, final SpeculationLog speculationLog) { + public static LIR emitHIR(GraalCodeCacheProvider runtime, TargetDescription target, final StructuredGraph graph, Replacements replacements, Assumptions assumptions, GraphCache cache, + PhasePlan plan, OptimisticOptimizations optimisticOpts, final SpeculationLog speculationLog) { if (speculationLog != null) { speculationLog.snapshot(); @@ -113,10 +113,6 @@ Debug.dump(graph, "initial state"); } - if (GraalOptions.ProbabilityAnalysis && graph.start().probability() == 0) { - new ComputeProbabilityPhase().apply(graph); - } - if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase.Instance(runtime, assumptions).apply(graph); } @@ -170,14 +166,13 @@ assert startBlock != null; assert startBlock.getPredecessorCount() == 0; - new ComputeProbabilityPhase().apply(graph); - return Debug.scope("ComputeLinearScanOrder", new Callable<LIR>() { @Override public LIR call() { - List<Block> codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock); - List<Block> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock); + NodeProbabilities nodeProbabilities = new ComputeProbabilityClosure(graph).run(); + List<Block> codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock, nodeProbabilities); + List<Block> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock, nodeProbabilities); LIR lir = new LIR(schedule.getCFG(), schedule.getBlockToNodesMap(), linearScanOrder, codeEmittingOrder, speculationLog); Debug.dump(lir, "After linear scan order");
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Mon Apr 22 13:29:55 2013 +0200 @@ -248,7 +248,6 @@ continue; } MergeNode merge = graph.add(new MergeNode()); - merge.setProbability(next.probability()); EndNode originalEnd = graph.add(new EndNode()); EndNode newEnd = graph.add(new EndNode()); merge.addForwardEnd(originalEnd);
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java Mon Apr 22 13:29:55 2013 +0200 @@ -102,7 +102,6 @@ GraphUtil.killWithUnusedFloatingInputs(state); } loop.entryPoint().replaceAtPredecessor(entry); - end.setProbability(loop.entryPoint().probability()); end.setNext(loop.entryPoint()); }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Mon Apr 22 13:29:55 2013 +0200 @@ -35,9 +35,9 @@ } // TODO (gd) change when inversion is available - public static boolean shouldPeel(LoopEx loop) { + public static boolean shouldPeel(LoopEx loop, NodeProbabilities probabilities) { LoopBeginNode loopBegin = loop.loopBegin(); - double entryProbability = loopBegin.forwardEnd().probability(); + double entryProbability = probabilities.getProbability(loopBegin.forwardEnd()); return entryProbability > GraalOptions.MinimumPeelProbability && loop.size() + loopBegin.graph().getNodeCount() < GraalOptions.MaximumDesiredSize; }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Mon Apr 22 13:29:55 2013 +0200 @@ -27,7 +27,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; -import com.oracle.graal.loop.InductionVariable.*; +import com.oracle.graal.loop.InductionVariable.Direction; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.cfg.*; @@ -39,7 +39,6 @@ private ControlFlowGraph cfg; public LoopsData(final StructuredGraph graph) { - cfg = Debug.scope("ControlFlowGraph", new Callable<ControlFlowGraph>() { @Override
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java Mon Apr 22 13:29:55 2013 +0200 @@ -25,7 +25,9 @@ import com.oracle.graal.debug.*; import com.oracle.graal.loop.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.common.*; public class LoopTransformHighPhase extends Phase { @@ -33,9 +35,10 @@ protected void run(StructuredGraph graph) { if (graph.hasLoops()) { if (GraalOptions.LoopPeeling) { + NodeProbabilities probabilities = new ComputeProbabilityClosure(graph).run(); LoopsData data = new LoopsData(graph); for (LoopEx loop : data.outterFirst()) { - if (LoopPolicies.shouldPeel(loop)) { + if (LoopPolicies.shouldPeel(loop, probabilities)) { Debug.log("Peeling %s", loop); LoopTransformations.peel(loop); Debug.dump(graph, "After peeling %s", loop);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedNode.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedNode.java Mon Apr 22 13:29:55 2013 +0200 @@ -28,8 +28,6 @@ public abstract class FixedNode extends ValueNode { - private double probability; - public FixedNode(Stamp stamp) { super(stamp); } @@ -42,20 +40,6 @@ super(stamp, dependencies); } - public double probability() { - return probability; - } - - public void setProbability(double probability) { - assert probability >= 0 : String.format("Invalid argument %f, because the probability of a node must not be negative.", probability); - this.probability = probability; - assert !Double.isNaN(probability); - } - - protected void copyInto(FixedNode newNode) { - newNode.setProbability(probability); - } - @Override public boolean verify() { assertTrue(this.successors().isNotEmpty() || this.predecessor() != null, "FixedNode should not float");
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Mon Apr 22 13:29:55 2013 +0200 @@ -361,13 +361,10 @@ PhiNode oldPhi = (PhiNode) oldMerge.usages().first(); PhiNode newPhi = graph().add(new PhiNode(oldPhi.stamp(), newMerge)); - double probability = 0.0; for (EndNode end : ends) { newPhi.addInput(phiValues.get(end)); newMerge.addForwardEnd(end); - probability += end.probability(); } - newMerge.setProbability(probability); FrameState stateAfter = oldMerge.stateAfter(); if (stateAfter != null) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/Invoke.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/Invoke.java Mon Apr 22 13:29:55 2013 +0200 @@ -45,14 +45,6 @@ void intrinsify(Node node); - double probability(); - - void setProbability(double value); - - double inliningRelevance(); - - void setInliningRelevance(double value); - boolean useForInlining(); void setUseForInlining(boolean value);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Mon Apr 22 13:29:55 2013 +0200 @@ -41,7 +41,6 @@ private final int bci; private boolean polymorphic; private boolean useForInlining; - private double inliningRelevance; /** * Constructs a new Invoke instruction. @@ -55,7 +54,6 @@ this.bci = bci; this.polymorphic = false; this.useForInlining = true; - this.inliningRelevance = Double.NaN; } @Override @@ -83,16 +81,6 @@ } @Override - public double inliningRelevance() { - return inliningRelevance; - } - - @Override - public void setInliningRelevance(double value) { - inliningRelevance = value; - } - - @Override public Map<Object, Object> getDebugProperties(Map<Object, Object> map) { Map<Object, Object> debugProperties = super.getDebugProperties(map); debugProperties.put("targetMethod", callTarget.targetName());
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Mon Apr 22 13:29:55 2013 +0200 @@ -42,7 +42,6 @@ private final int bci; private boolean polymorphic; private boolean useForInlining; - private double inliningRelevance; public InvokeWithExceptionNode(CallTargetNode callTarget, DispatchBeginNode exceptionEdge, int bci) { super(callTarget.returnStamp()); @@ -51,7 +50,6 @@ this.callTarget = callTarget; this.polymorphic = false; this.useForInlining = true; - this.inliningRelevance = Double.NaN; } public DispatchBeginNode exceptionEdge() { @@ -101,16 +99,6 @@ } @Override - public double inliningRelevance() { - return inliningRelevance; - } - - @Override - public void setInliningRelevance(double value) { - inliningRelevance = value; - } - - @Override public String toString(Verbosity verbosity) { if (verbosity == Verbosity.Long) { return super.toString(Verbosity.Short) + "(bci=" + bci() + ")";
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Mon Apr 22 13:29:55 2013 +0200 @@ -236,7 +236,6 @@ public void replaceFixedWithFixed(FixedWithNextNode node, FixedWithNextNode replacement) { assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement; - replacement.setProbability(node.probability()); FixedNode next = node.next(); node.setNext(null); replacement.setNext(next); @@ -307,7 +306,6 @@ public void addAfterFixed(FixedWithNextNode node, FixedNode newNode) { assert node != null && newNode != null && node.isAlive() && newNode.isAlive() : "cannot add " + newNode + " after " + node; - newNode.setProbability(node.probability()); FixedNode next = node.next(); node.setNext(newNode); if (next != null) { @@ -322,7 +320,6 @@ assert node != null && newNode != null && node.isAlive() && newNode.isAlive() : "cannot add " + newNode + " before " + node; assert node.predecessor() != null && node.predecessor() instanceof FixedWithNextNode : "cannot add " + newNode + " before " + node; assert newNode.next() == null : newNode; - newNode.setProbability(node.probability()); FixedWithNextNode pred = (FixedWithNextNode) node.predecessor(); pred.setNext(newNode); newNode.setNext(node); @@ -334,7 +331,6 @@ reduceTrivialMerge(begin); } else { // convert to merge MergeNode merge = this.add(new MergeNode()); - merge.setProbability(begin.probability()); this.replaceFixedWithFixed(begin, merge); } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Mon Apr 22 13:29:55 2013 +0200 @@ -29,9 +29,10 @@ public final class Block { + protected final BeginNode beginNode; + protected int id; - protected BeginNode beginNode; protected FixedNode endNode; protected Loop loop; @@ -45,8 +46,10 @@ private boolean align; private int linearScanNumber; - protected Block() { - id = ControlFlowGraph.BLOCK_ID_INITIAL; + protected Block(BeginNode node) { + this.beginNode = node; + + this.id = ControlFlowGraph.BLOCK_ID_INITIAL; this.linearScanNumber = -1; } @@ -206,10 +209,6 @@ return dominator.isDominatedBy(block); } - public double getProbability() { - return getBeginNode().probability(); - } - public int getLinearScanNumber() { return linearScanNumber; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Mon Apr 22 13:29:55 2013 +0200 @@ -39,6 +39,7 @@ public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) { ControlFlowGraph cfg = new ControlFlowGraph(graph); cfg.identifyBlocks(); + if (connectBlocks || computeLoops || computeDominators || computePostdominators) { cfg.connectBlocks(); } @@ -111,16 +112,15 @@ public void clearNodeToBlock() { nodeToBlock.clear(); for (Block block : reversePostOrder) { - identifyBlock(block, block.beginNode); + identifyBlock(block); } } protected static final int BLOCK_ID_INITIAL = -1; protected static final int BLOCK_ID_VISITED = -2; - private void identifyBlock(Block block, BeginNode begin) { - block.beginNode = begin; - Node cur = begin; + private void identifyBlock(Block block) { + Node cur = block.getBeginNode(); Node last; do { assert !cur.isDeleted(); @@ -145,9 +145,9 @@ int numBlocks = 0; for (Node node : graph.getNodes()) { if (node instanceof BeginNode) { - Block block = new Block(); + Block block = new Block((BeginNode) node); numBlocks++; - identifyBlock(block, (BeginNode) node); + identifyBlock(block); } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/NodeProbabilities.java Mon Apr 22 13:29:55 2013 +0200 @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.cfg; + +import java.util.*; + +import com.oracle.graal.nodes.*; + +public class NodeProbabilities { + + private final IdentityHashMap<FixedNode, Double> nodeProbabilities; + + public NodeProbabilities(int numberOfNodes) { + this.nodeProbabilities = new IdentityHashMap<>(numberOfNodes); + } + + public void setProbability(FixedNode n, double value) { + nodeProbabilities.put(n, value); + } + + public double getProbability(FixedNode n) { + Double value = nodeProbabilities.get(n); + assert value != null; + return value; + } + + public int size() { + return nodeProbabilities.size(); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeInliningRelevanceClosure.java Mon Apr 22 13:29:55 2013 +0200 @@ -0,0 +1,223 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.phases.common; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.phases.graph.*; + +public class ComputeInliningRelevanceClosure { + + private static final double EPSILON = 1d / Integer.MAX_VALUE; + + private final StructuredGraph graph; + private final NodeProbabilities nodeProbabilities; + private final NodeProbabilities nodeRelevances; + + public ComputeInliningRelevanceClosure(StructuredGraph graph, NodeProbabilities nodeProbabilities) { + this.graph = graph; + this.nodeProbabilities = nodeProbabilities; + this.nodeRelevances = new NodeProbabilities(graph.getNodeCount()); + } + + public NodeProbabilities run() { + new ComputeInliningRelevanceIterator(graph).apply(); + return nodeRelevances; + } + + private class ComputeInliningRelevanceIterator extends ScopedPostOrderNodeIterator { + + private final HashMap<FixedNode, Scope> scopes; + private double currentProbability; + private double parentRelevance; + + public ComputeInliningRelevanceIterator(StructuredGraph graph) { + super(graph); + this.scopes = computeLowestPathProbabilities(); + } + + @Override + protected void initializeScope() { + Scope scope = scopes.get(currentScopeStart); + parentRelevance = getParentScopeRelevance(scope); + currentProbability = scope.minPathProbability; + } + + private double getParentScopeRelevance(Scope scope) { + if (scope.start instanceof LoopBeginNode) { + assert scope.parent != null; + double parentProbability = 0; + for (EndNode end : ((LoopBeginNode) scope.start).forwardEnds()) { + parentProbability += nodeProbabilities.getProbability(end); + } + return parentProbability / scope.parent.minPathProbability; + } else { + assert scope.parent == null; + return 1.0; + } + } + + @Override + protected void invoke(Invoke invoke) { + double probability = nodeProbabilities.getProbability(invoke.asNode()); + assert !Double.isNaN(probability); + + double relevance = (probability / currentProbability) * Math.min(1.0, parentRelevance); + nodeRelevances.setProbability(invoke.asNode(), relevance); + assert !Double.isNaN(relevance); + } + + private HashMap<FixedNode, Scope> computeLowestPathProbabilities() { + HashMap<FixedNode, Scope> result = new HashMap<>(); + + for (Scope scope : computeScopes()) { + double lowestPathProbability = computeLowestPathProbability(scope); + scope.minPathProbability = Math.max(EPSILON, lowestPathProbability); + result.put(scope.start, scope); + } + + return result; + } + + private Scope[] computeScopes() { + ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); + + Loop[] loops = cfg.getLoops(); + HashMap<Loop, Scope> processedScopes = new HashMap<>(); + Scope[] result = new Scope[loops.length + 1]; + Scope methodScope = new Scope(graph.start(), null); + processedScopes.put(null, methodScope); + + result[0] = methodScope; + for (int i = 0; i < loops.length; i++) { + result[i + 1] = createScope(loops[i], processedScopes); + } + + return result; + } + + private Scope createScope(Loop loop, HashMap<Loop, Scope> processedLoops) { + Scope parent = processedLoops.get(loop.parent); + if (parent == null) { + parent = createScope(loop.parent, processedLoops); + } + Scope result = new Scope(loop.loopBegin(), parent); + processedLoops.put(loop, result); + return result; + } + + private double computeLowestPathProbability(Scope scope) { + FixedNode scopeStart = scope.start; + ArrayList<FixedNode> pathBeginNodes = new ArrayList<>(); + pathBeginNodes.add(scopeStart); + double minPathProbability = nodeProbabilities.getProbability(scopeStart); + boolean isLoopScope = scopeStart instanceof LoopBeginNode; + + do { + Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1); + do { + if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) { + return minPathProbability; + } else if (current instanceof LoopBeginNode && current != scopeStart) { + current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes); + minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability); + } else if (current instanceof ControlSplitNode) { + current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes); + minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability); + } else { + assert current.successors().count() <= 1; + current = current.successors().first(); + } + } while (current != null); + } while (!pathBeginNodes.isEmpty()); + + return minPathProbability; + } + + private double getMinPathProbability(FixedNode current, double minPathProbability) { + if (current != null && nodeProbabilities.getProbability(current) < minPathProbability) { + return nodeProbabilities.getProbability(current); + } + return minPathProbability; + } + + private Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) { + Node maxSux = null; + double maxProbability = 0.0; + int pathBeginCount = pathBeginNodes.size(); + + for (Node sux : controlSplit.successors()) { + double probability = controlSplit.probability((BeginNode) sux); + if (probability > maxProbability) { + maxProbability = probability; + maxSux = sux; + truncate(pathBeginNodes, pathBeginCount); + } else if (probability == maxProbability) { + pathBeginNodes.add((FixedNode) sux); + } + } + + return maxSux; + } + + private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) { + Node maxSux = null; + double maxProbability = 0.0; + int pathBeginCount = pathBeginNodes.size(); + + for (LoopExitNode sux : loopBegin.loopExits()) { + double probability = nodeProbabilities.getProbability(sux); + if (probability > maxProbability) { + maxProbability = probability; + maxSux = sux; + truncate(pathBeginNodes, pathBeginCount); + } else if (probability == maxProbability) { + pathBeginNodes.add(sux); + } + } + + return maxSux; + } + + private void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) { + for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) { + pathBeginNodes.remove(pathBeginNodes.size() - 1); + } + } + } + + private static class Scope { + + public final FixedNode start; + public final Scope parent; + public double minPathProbability; + + public Scope(FixedNode start, Scope parent) { + this.start = start; + this.parent = parent; + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityClosure.java Mon Apr 22 13:29:55 2013 +0200 @@ -0,0 +1,296 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.phases.common; + +import java.util.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.phases.graph.*; + +/** + * Computes probabilities for nodes in a graph. + * <p> + * The computation of absolute probabilities works in three steps: + * <ol> + * <li>{@link PropagateProbability} traverses the graph in post order (merges after their ends, ...) + * and keeps track of the "probability state". Whenever it encounters a {@link ControlSplitNode} it + * uses the split's probability information to divide the probability upon the successors. Whenever + * it encounters an {@link Invoke} it assumes that the exception edge is unlikely and propagates the + * whole probability to the normal successor. Whenever it encounters a {@link MergeNode} it sums up + * the probability of all predecessors. It also maintains a set of active loops (whose + * {@link LoopBeginNode} has been visited) and builds def/use information for step 2.</li> + * <li></li> + * <li>{@link PropagateLoopFrequency} propagates the loop frequencies and multiplies each + * {@link FixedNode}'s probability with its loop frequency.</li> + * </ol> + * TODO: add exception probability information to Invokes + */ +public class ComputeProbabilityClosure { + + private static final double EPSILON = 1d / Integer.MAX_VALUE; + + private final StructuredGraph graph; + private final NodeProbabilities nodeProbabilities; + private final Set<LoopInfo> loopInfos; + private final Map<MergeNode, Set<LoopInfo>> mergeLoops; + + public ComputeProbabilityClosure(StructuredGraph graph) { + this.graph = graph; + this.nodeProbabilities = new NodeProbabilities(graph.getNodeCount()); + this.loopInfos = new HashSet<>(); + this.mergeLoops = new IdentityHashMap<>(); + } + + public NodeProbabilities run() { + new PropagateProbability(graph.start()).apply(); + Debug.dump(graph, "After PropagateProbability"); + computeLoopFactors(); + Debug.dump(graph, "After computeLoopFactors"); + new PropagateLoopFrequency(graph.start()).apply(); + return nodeProbabilities; + } + + private void computeLoopFactors() { + for (LoopInfo info : loopInfos) { + double frequency = info.loopFrequency(nodeProbabilities); + assert frequency != -1; + } + } + + private static boolean isRelativeProbability(double prob) { + // 1.01 to allow for some rounding errors + return prob >= 0 && prob <= 1.01; + } + + public static class LoopInfo { + + public final LoopBeginNode loopBegin; + + public final NodeMap<Set<LoopInfo>> requires; + + private double loopFrequency = -1; + public boolean ended = false; + + public LoopInfo(LoopBeginNode loopBegin) { + this.loopBegin = loopBegin; + this.requires = loopBegin.graph().createNodeMap(); + } + + public double loopFrequency(NodeProbabilities nodeProbabilities) { + if (loopFrequency == -1 && ended) { + double backEdgeProb = 0.0; + for (LoopEndNode le : loopBegin.loopEnds()) { + double factor = 1; + Set<LoopInfo> requireds = requires.get(le); + for (LoopInfo required : requireds) { + double t = required.loopFrequency(nodeProbabilities); + if (t == -1) { + return -1; + } + factor *= t; + } + backEdgeProb += nodeProbabilities.getProbability(le) * factor; + } + double d = nodeProbabilities.getProbability(loopBegin) - backEdgeProb; + if (d < EPSILON) { + d = EPSILON; + } + loopFrequency = nodeProbabilities.getProbability(loopBegin) / d; + loopBegin.setLoopFrequency(loopFrequency); + } + return loopFrequency; + } + } + + private class Probability implements MergeableState<Probability> { + + public double probability; + public HashSet<LoopInfo> loops; + public LoopInfo loopInfo; + + public Probability(double probability, HashSet<LoopInfo> loops) { + this.probability = probability; + this.loops = new HashSet<>(4); + if (loops != null) { + this.loops.addAll(loops); + } + } + + @Override + public Probability clone() { + return new Probability(probability, loops); + } + + @Override + public boolean merge(MergeNode merge, List<Probability> withStates) { + if (merge.forwardEndCount() > 1) { + HashSet<LoopInfo> intersection = new HashSet<>(loops); + for (Probability other : withStates) { + intersection.retainAll(other.loops); + } + for (LoopInfo info : loops) { + if (!intersection.contains(info)) { + double loopFrequency = info.loopFrequency(nodeProbabilities); + if (loopFrequency == -1) { + return false; + } + probability *= loopFrequency; + } + } + for (Probability other : withStates) { + double prob = other.probability; + for (LoopInfo info : other.loops) { + if (!intersection.contains(info)) { + double loopFrequency = info.loopFrequency(nodeProbabilities); + if (loopFrequency == -1) { + return false; + } + prob *= loopFrequency; + } + } + probability += prob; + } + loops = intersection; + mergeLoops.put(merge, new HashSet<>(intersection)); + assert isRelativeProbability(probability) : probability; + } + return true; + } + + @Override + public void loopBegin(LoopBeginNode loopBegin) { + loopInfo = new LoopInfo(loopBegin); + loopInfos.add(loopInfo); + loops.add(loopInfo); + } + + @Override + public void loopEnds(LoopBeginNode loopBegin, List<Probability> loopEndStates) { + assert loopInfo != null; + List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds(); + int i = 0; + for (Probability proba : loopEndStates) { + LoopEndNode loopEnd = loopEnds.get(i++); + Set<LoopInfo> requires = loopInfo.requires.get(loopEnd); + if (requires == null) { + requires = new HashSet<>(); + loopInfo.requires.set(loopEnd, requires); + } + for (LoopInfo innerLoop : proba.loops) { + if (innerLoop != loopInfo && !this.loops.contains(innerLoop)) { + requires.add(innerLoop); + } + } + } + loopInfo.ended = true; + } + + @Override + public void afterSplit(BeginNode node) { + assert node.predecessor() != null; + Node pred = node.predecessor(); + if (pred instanceof Invoke) { + Invoke x = (Invoke) pred; + if (x.next() != node) { + probability = 0; + } + } else { + assert pred instanceof ControlSplitNode; + ControlSplitNode x = (ControlSplitNode) pred; + probability *= x.probability(node); + } + } + } + + private class PropagateProbability extends PostOrderNodeIterator<Probability> { + + public PropagateProbability(FixedNode start) { + super(start, new Probability(1d, null)); + } + + @Override + protected void node(FixedNode node) { + nodeProbabilities.setProbability(node, state.probability); + } + } + + private class LoopCount implements MergeableState<LoopCount> { + + public double count; + + public LoopCount(double count) { + this.count = count; + } + + @Override + public LoopCount clone() { + return new LoopCount(count); + } + + @Override + public boolean merge(MergeNode merge, List<LoopCount> withStates) { + assert merge.forwardEndCount() == withStates.size() + 1; + if (merge.forwardEndCount() > 1) { + Set<LoopInfo> loops = mergeLoops.get(merge); + assert loops != null; + double countProd = 1; + for (LoopInfo loop : loops) { + countProd *= loop.loopFrequency(nodeProbabilities); + } + count = countProd; + } + return true; + } + + @Override + public void loopBegin(LoopBeginNode loopBegin) { + count *= loopBegin.loopFrequency(); + } + + @Override + public void loopEnds(LoopBeginNode loopBegin, List<LoopCount> loopEndStates) { + // nothing to do... + } + + @Override + public void afterSplit(BeginNode node) { + // nothing to do... + } + } + + private class PropagateLoopFrequency extends PostOrderNodeIterator<LoopCount> { + + public PropagateLoopFrequency(FixedNode start) { + super(start, new LoopCount(1d)); + } + + @Override + protected void node(FixedNode node) { + nodeProbabilities.setProbability(node, nodeProbabilities.getProbability(node) * state.count); + } + + } +}
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java Sun Apr 21 21:41:09 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,459 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common; - -import java.util.*; - -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.cfg.*; -import com.oracle.graal.phases.*; -import com.oracle.graal.phases.graph.*; - -/** - * Computes probabilities for nodes in a graph. - * <p> - * The computation of absolute probabilities works in three steps: - * <ol> - * <li>{@link PropagateProbability} traverses the graph in post order (merges after their ends, ...) - * and keeps track of the "probability state". Whenever it encounters a {@link ControlSplitNode} it - * uses the split's probability information to divide the probability upon the successors. Whenever - * it encounters an {@link Invoke} it assumes that the exception edge is unlikely and propagates the - * whole probability to the normal successor. Whenever it encounters a {@link MergeNode} it sums up - * the probability of all predecessors. It also maintains a set of active loops (whose - * {@link LoopBeginNode} has been visited) and builds def/use information for step 2.</li> - * <li></li> - * <li>{@link PropagateLoopFrequency} propagates the loop frequencies and multiplies each - * {@link FixedNode}'s probability with its loop frequency.</li> - * </ol> - * TODO: add exception probability information to Invokes - */ -public class ComputeProbabilityPhase extends Phase { - - private static final double EPSILON = 1d / Integer.MAX_VALUE; - - @Override - protected void run(StructuredGraph graph) { - new PropagateProbability(graph.start()).apply(); - Debug.dump(graph, "After PropagateProbability"); - computeLoopFactors(); - Debug.dump(graph, "After computeLoopFactors"); - new PropagateLoopFrequency(graph.start()).apply(); - new ComputeInliningRelevanceIterator(graph).apply(); - } - - private void computeLoopFactors() { - for (LoopInfo info : loopInfos) { - double frequency = info.loopFrequency(); - assert frequency != -1; - } - } - - private static boolean isRelativeProbability(double prob) { - // 1.01 to allow for some rounding errors - return prob >= 0 && prob <= 1.01; - } - - public static class LoopInfo { - - public final LoopBeginNode loopBegin; - - public final NodeMap<Set<LoopInfo>> requires; - - private double loopFrequency = -1; - public boolean ended = false; - - public LoopInfo(LoopBeginNode loopBegin) { - this.loopBegin = loopBegin; - this.requires = loopBegin.graph().createNodeMap(); - } - - public double loopFrequency() { - if (loopFrequency == -1 && ended) { - double backEdgeProb = 0.0; - for (LoopEndNode le : loopBegin.loopEnds()) { - double factor = 1; - Set<LoopInfo> requireds = requires.get(le); - for (LoopInfo required : requireds) { - double t = required.loopFrequency(); - if (t == -1) { - return -1; - } - factor *= t; - } - backEdgeProb += le.probability() * factor; - } - double d = loopBegin.probability() - backEdgeProb; - if (d < EPSILON) { - d = EPSILON; - } - loopFrequency = loopBegin.probability() / d; - loopBegin.setLoopFrequency(loopFrequency); - } - return loopFrequency; - } - } - - public Set<LoopInfo> loopInfos = new HashSet<>(); - public Map<MergeNode, Set<LoopInfo>> mergeLoops = new IdentityHashMap<>(); - - private class Probability implements MergeableState<Probability> { - - public double probability; - public HashSet<LoopInfo> loops; - public LoopInfo loopInfo; - - public Probability(double probability, HashSet<LoopInfo> loops) { - this.probability = probability; - this.loops = new HashSet<>(4); - if (loops != null) { - this.loops.addAll(loops); - } - } - - @Override - public Probability clone() { - return new Probability(probability, loops); - } - - @Override - public boolean merge(MergeNode merge, List<Probability> withStates) { - if (merge.forwardEndCount() > 1) { - HashSet<LoopInfo> intersection = new HashSet<>(loops); - for (Probability other : withStates) { - intersection.retainAll(other.loops); - } - for (LoopInfo info : loops) { - if (!intersection.contains(info)) { - double loopFrequency = info.loopFrequency(); - if (loopFrequency == -1) { - return false; - } - probability *= loopFrequency; - } - } - for (Probability other : withStates) { - double prob = other.probability; - for (LoopInfo info : other.loops) { - if (!intersection.contains(info)) { - double loopFrequency = info.loopFrequency(); - if (loopFrequency == -1) { - return false; - } - prob *= loopFrequency; - } - } - probability += prob; - } - loops = intersection; - mergeLoops.put(merge, new HashSet<>(intersection)); - assert isRelativeProbability(probability) : probability; - } - return true; - } - - @Override - public void loopBegin(LoopBeginNode loopBegin) { - loopInfo = new LoopInfo(loopBegin); - loopInfos.add(loopInfo); - loops.add(loopInfo); - } - - @Override - public void loopEnds(LoopBeginNode loopBegin, List<Probability> loopEndStates) { - assert loopInfo != null; - List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds(); - int i = 0; - for (Probability proba : loopEndStates) { - LoopEndNode loopEnd = loopEnds.get(i++); - Set<LoopInfo> requires = loopInfo.requires.get(loopEnd); - if (requires == null) { - requires = new HashSet<>(); - loopInfo.requires.set(loopEnd, requires); - } - for (LoopInfo innerLoop : proba.loops) { - if (innerLoop != loopInfo && !this.loops.contains(innerLoop)) { - requires.add(innerLoop); - } - } - } - loopInfo.ended = true; - } - - @Override - public void afterSplit(BeginNode node) { - assert node.predecessor() != null; - Node pred = node.predecessor(); - if (pred instanceof Invoke) { - Invoke x = (Invoke) pred; - if (x.next() != node) { - probability = 0; - } - } else { - assert pred instanceof ControlSplitNode; - ControlSplitNode x = (ControlSplitNode) pred; - probability *= x.probability(node); - } - } - } - - private class PropagateProbability extends PostOrderNodeIterator<Probability> { - - public PropagateProbability(FixedNode start) { - super(start, new Probability(1d, null)); - } - - @Override - protected void node(FixedNode node) { - node.setProbability(state.probability); - } - } - - private class LoopCount implements MergeableState<LoopCount> { - - public double count; - - public LoopCount(double count) { - this.count = count; - } - - @Override - public LoopCount clone() { - return new LoopCount(count); - } - - @Override - public boolean merge(MergeNode merge, List<LoopCount> withStates) { - assert merge.forwardEndCount() == withStates.size() + 1; - if (merge.forwardEndCount() > 1) { - Set<LoopInfo> loops = mergeLoops.get(merge); - assert loops != null; - double countProd = 1; - for (LoopInfo loop : loops) { - countProd *= loop.loopFrequency(); - } - count = countProd; - } - return true; - } - - @Override - public void loopBegin(LoopBeginNode loopBegin) { - count *= loopBegin.loopFrequency(); - } - - @Override - public void loopEnds(LoopBeginNode loopBegin, List<LoopCount> loopEndStates) { - // nothing to do... - } - - @Override - public void afterSplit(BeginNode node) { - // nothing to do... - } - } - - private class PropagateLoopFrequency extends PostOrderNodeIterator<LoopCount> { - - public PropagateLoopFrequency(FixedNode start) { - super(start, new LoopCount(1d)); - } - - @Override - protected void node(FixedNode node) { - node.setProbability(node.probability() * state.count); - } - - } - - private static class ComputeInliningRelevanceIterator extends ScopedPostOrderNodeIterator { - - private final HashMap<FixedNode, Scope> scopes; - private double currentProbability; - private double parentRelevance; - - public ComputeInliningRelevanceIterator(StructuredGraph graph) { - super(graph); - this.scopes = computeLowestPathProbabilities(computeScopeInformation(graph)); - } - - @Override - protected void initializeScope() { - Scope scope = scopes.get(currentScopeStart); - parentRelevance = getParentScopeRelevance(scope); - currentProbability = scope.minPathProbability; - } - - private static double getParentScopeRelevance(Scope scope) { - if (scope.start instanceof LoopBeginNode) { - assert scope.parent != null; - double parentProbability = 0; - for (EndNode end : ((LoopBeginNode) scope.start).forwardEnds()) { - parentProbability += end.probability(); - } - return parentProbability / scope.parent.minPathProbability; - } else { - assert scope.parent == null; - return 1.0; - } - } - - @Override - protected void invoke(Invoke invoke) { - assert !Double.isNaN(invoke.probability()); - invoke.setInliningRelevance((invoke.probability() / currentProbability) * Math.min(1.0, parentRelevance)); - assert !Double.isNaN(invoke.inliningRelevance()); - } - - private static Scope[] computeScopeInformation(StructuredGraph graph) { - ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); - - Loop[] loops = cfg.getLoops(); - HashMap<Loop, Scope> processedScopes = new HashMap<>(); - Scope[] scopes = new Scope[loops.length + 1]; - Scope methodScope = new Scope(graph.start(), null); - processedScopes.put(null, methodScope); - - scopes[0] = methodScope; - for (int i = 0; i < loops.length; i++) { - scopes[i + 1] = createScope(loops[i], processedScopes); - } - - return scopes; - } - - private static Scope createScope(Loop loop, HashMap<Loop, Scope> processedLoops) { - Scope parent = processedLoops.get(loop.parent); - if (parent == null) { - parent = createScope(loop.parent, processedLoops); - } - Scope result = new Scope(loop.loopBegin(), parent); - processedLoops.put(loop, result); - return result; - } - - private static HashMap<FixedNode, Scope> computeLowestPathProbabilities(Scope[] scopes) { - HashMap<FixedNode, Scope> result = new HashMap<>(); - - for (Scope scope : scopes) { - double lowestPathProbability = computeLowestPathProbability(scope); - scope.minPathProbability = Math.max(EPSILON, lowestPathProbability); - result.put(scope.start, scope); - } - - return result; - } - - private static double computeLowestPathProbability(Scope scope) { - FixedNode scopeStart = scope.start; - ArrayList<FixedNode> pathBeginNodes = new ArrayList<>(); - pathBeginNodes.add(scopeStart); - double minPathProbability = scopeStart.probability(); - boolean isLoopScope = scopeStart instanceof LoopBeginNode; - - do { - Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1); - do { - if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) { - return minPathProbability; - } else if (current instanceof LoopBeginNode && current != scopeStart) { - current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes); - minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability); - } else if (current instanceof ControlSplitNode) { - current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes); - minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability); - } else { - assert current.successors().count() <= 1; - current = current.successors().first(); - } - } while (current != null); - } while (!pathBeginNodes.isEmpty()); - - return minPathProbability; - } - - private static double getMinPathProbability(FixedNode current, double minPathProbability) { - if (current != null && current.probability() < minPathProbability) { - return current.probability(); - } - return minPathProbability; - } - - private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) { - Node maxSux = null; - double maxProbability = 0.0; - int pathBeginCount = pathBeginNodes.size(); - - for (Node sux : controlSplit.successors()) { - double probability = controlSplit.probability((BeginNode) sux); - if (probability > maxProbability) { - maxProbability = probability; - maxSux = sux; - truncate(pathBeginNodes, pathBeginCount); - } else if (probability == maxProbability) { - pathBeginNodes.add((FixedNode) sux); - } - } - - return maxSux; - } - - private static Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) { - Node maxSux = null; - double maxProbability = 0.0; - int pathBeginCount = pathBeginNodes.size(); - - for (LoopExitNode sux : loopBegin.loopExits()) { - double probability = sux.probability(); - if (probability > maxProbability) { - maxProbability = probability; - maxSux = sux; - truncate(pathBeginNodes, pathBeginCount); - } else if (probability == maxProbability) { - pathBeginNodes.add(sux); - } - } - - return maxSux; - } - - public static void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) { - for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) { - pathBeginNodes.remove(pathBeginNodes.size() - 1); - } - } - } - - private static class Scope { - - public final FixedNode start; - public final Scope parent; - public double minPathProbability; - - public Scope(FixedNode start, Scope parent) { - this.start = start; - this.parent = parent; - } - } -}
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Mon Apr 22 13:29:55 2013 +0200 @@ -31,6 +31,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; @@ -99,13 +100,15 @@ @Override protected void run(final StructuredGraph graph) { + NodeProbabilities nodeProbabilities = new ComputeProbabilityClosure(graph).run(); + NodeProbabilities nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).run(); inliningPolicy.initialize(graph); while (inliningPolicy.continueInlining(graph)) { final InlineInfo candidate = inliningPolicy.next(); if (candidate != null) { - boolean isWorthInlining = inliningPolicy.isWorthInlining(candidate); + boolean isWorthInlining = inliningPolicy.isWorthInlining(candidate, nodeProbabilities, nodeRelevance); isWorthInlining &= candidate.numberOfMethods() <= maxMethodPerInlining; metricInliningConsidered.increment(); @@ -120,6 +123,10 @@ if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase.Instance(runtime, assumptions, invokeUsages, mark, customCanonicalizer).apply(graph); } + + nodeProbabilities = new ComputeProbabilityClosure(graph).run(); + nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).run(); + inliningCount++; metricInliningPerformed.increment(); } catch (BailoutException bailout) { @@ -159,7 +166,6 @@ if (GraalOptions.ProbabilityAnalysis) { new DeadCodeEliminationPhase().apply(newGraph); - new ComputeProbabilityPhase().apply(newGraph); } if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); @@ -177,7 +183,7 @@ private interface InliningDecision { - boolean isWorthInlining(InlineInfo info); + boolean isWorthInlining(InlineInfo info, NodeProbabilities nodeProbabilities, NodeProbabilities nodeRelevance); } private static class GreedySizeBasedInliningDecision implements InliningDecision { @@ -193,7 +199,7 @@ } @Override - public boolean isWorthInlining(InlineInfo info) { + public boolean isWorthInlining(InlineInfo info, NodeProbabilities nodeProbabilities, NodeProbabilities nodeRelevance) { assert GraalOptions.ProbabilityAnalysis; /* * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> @@ -220,8 +226,7 @@ int bytecodeSize = (int) (bytecodeCodeSize(info) / bonus); int complexity = (int) (compilationComplexity(info) / bonus); int compiledCodeSize = (int) (compiledCodeSize(info) / bonus); - double relevance = info.invoke().inliningRelevance(); - + double relevance = nodeRelevance.getProbability(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 @@ -240,7 +245,7 @@ * the normal inlining did not fit this invoke, so check if we have any reason why we * should still do the inlining */ - double probability = info.invoke().probability(); + double probability = nodeProbabilities.getProbability(info.invoke().asNode()); int transferredValues = numberOfTransferredValues(info); int invokeUsages = countInvokeUsages(info); int moreSpecificArguments = countMoreSpecificArgumentInfo(info); @@ -409,8 +414,9 @@ return info; } - public boolean isWorthInlining(InlineInfo info) { - return inliningDecision.isWorthInlining(info); + @Override + public boolean isWorthInlining(InlineInfo info, NodeProbabilities nodeProbabilities, NodeProbabilities nodeRelevance) { + return inliningDecision.isWorthInlining(info, nodeProbabilities, nodeRelevance); } public void initialize(StructuredGraph graph) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Mon Apr 22 13:29:55 2013 +0200 @@ -35,6 +35,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.java.MethodCallTargetNode.InvokeKind; @@ -70,7 +71,7 @@ void scanInvokes(Iterable<? extends Node> newNodes); - boolean isWorthInlining(InlineInfo info); + boolean isWorthInlining(InlineInfo info, NodeProbabilities nodeProbabilities, NodeProbabilities nodeRelevance); } /** @@ -260,7 +261,6 @@ } catch (ReflectiveOperationException | IllegalArgumentException | SecurityException e) { throw new GraalInternalError(e).addContext(invoke.asNode()).addContext("macroSubstitution", macroNodeClass); } - macroNode.setProbability(invoke.asNode().probability()); CallTargetNode callTarget = invoke.callTarget(); if (invoke instanceof InvokeNode) { graph.replaceFixedWithFixed((InvokeNode) invoke, graph.add(macroNode)); @@ -466,7 +466,6 @@ ValueNode originalReceiver = ((MethodCallTargetNode) invoke.callTarget()).receiver(); // setup merge and phi nodes for results and exceptions MergeNode returnMerge = graph.add(new MergeNode()); - returnMerge.setProbability(invoke.probability()); returnMerge.setStateAfter(invoke.stateAfter().duplicate(invoke.stateAfter().bci)); PhiNode returnValuePhi = null; @@ -481,7 +480,6 @@ ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithException.exceptionEdge(); exceptionMerge = graph.add(new MergeNode()); - exceptionMerge.setProbability(exceptionEdge.probability()); FixedNode exceptionSux = exceptionEdge.next(); graph.addBeforeFixed(exceptionSux, exceptionMerge); @@ -492,20 +490,13 @@ // create one separate block for each invoked method BeginNode[] successors = new BeginNode[numberOfMethods + 1]; for (int i = 0; i < numberOfMethods; i++) { - double probability = 0; - for (int j = 0; j < typesToConcretes.length; j++) { - if (typesToConcretes[j] == i) { - probability += ptypes.get(j).getProbability(); - } - } - - successors[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, invoke.probability() * probability, true); + successors[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, true); } // create the successor for an unknown type FixedNode unknownTypeSux; if (shouldFallbackToInvoke()) { - unknownTypeSux = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, notRecordedTypeProbability, false); + unknownTypeSux = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, false); } else { unknownTypeSux = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated)); } @@ -612,7 +603,6 @@ assert concretes.size() == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0; BeginNode calleeEntryNode = graph.add(new BeginNode()); - calleeEntryNode.setProbability(invoke.probability()); BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); BeginNode[] successors = new BeginNode[]{calleeEntryNode, unknownTypeSux}; @@ -649,15 +639,12 @@ } private static BeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, MergeNode returnMerge, PhiNode returnValuePhi, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, - double probability, boolean useForInlining) { - Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining, probability); + boolean useForInlining) { + Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining); BeginNode calleeEntryNode = graph.add(new BeginNode()); calleeEntryNode.setNext(duplicatedInvoke.asNode()); - calleeEntryNode.setProbability(probability); EndNode endNode = graph.add(new EndNode()); - endNode.setProbability(probability); - duplicatedInvoke.setNext(endNode); returnMerge.addForwardEnd(endNode); @@ -667,13 +654,11 @@ return calleeEntryNode; } - private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining, double probability) { + private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining) { Invoke result = (Invoke) invoke.asNode().copyWithInputs(); Node callTarget = result.callTarget().copyWithInputs(); result.asNode().replaceFirstInput(result.callTarget(), callTarget); result.setUseForInlining(useForInlining); - result.setProbability(probability); - result.setInliningRelevance(invoke.inliningRelevance() * probability); Kind kind = invoke.asNode().kind(); if (kind != Kind.Void) { @@ -738,8 +723,6 @@ InliningUtil.receiverNullCheck(invoke); BeginNode invocationEntry = graph.add(new BeginNode()); - invocationEntry.setProbability(invoke.probability()); - BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); BeginNode[] successors = new BeginNode[]{invocationEntry, unknownTypeSux}; createDispatchOnTypeBeforeInvoke(graph, successors, true); @@ -966,6 +949,7 @@ return graph.unique(new PiNode(receiver, exact ? StampFactory.exactNonNull(commonType) : StampFactory.declaredNonNull(commonType), anchor)); } + // 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"); @@ -974,6 +958,7 @@ } else if (((MethodCallTargetNode) invoke.callTarget()).targetMethod() == null) { return logNotInlinedMethodAndReturnFalse(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"); } else if (!invoke.useForInlining()) { return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is marked to be not used for inlining"); @@ -1127,27 +1112,8 @@ } FrameState outerFrameState = null; - double invokeProbability = invoke.asNode().probability(); int callerLockDepth = stateAfter.nestedLockDepth(); for (Node node : duplicates.values()) { - if (GraalOptions.ProbabilityAnalysis) { - if (node instanceof FixedNode) { - FixedNode fixed = (FixedNode) node; - double newProbability = fixed.probability() * invokeProbability; - if (GraalOptions.LimitInlinedProbability) { - newProbability = Math.min(newProbability, invokeProbability); - } - fixed.setProbability(newProbability); - } - if (node instanceof Invoke) { - Invoke newInvoke = (Invoke) node; - double newRelevance = newInvoke.inliningRelevance() * invoke.inliningRelevance(); - if (GraalOptions.LimitInlinedRelevance) { - newRelevance = Math.min(newRelevance, invoke.inliningRelevance()); - } - newInvoke.setInliningRelevance(newRelevance); - } - } if (node instanceof FrameState) { FrameState frameState = (FrameState) node; assert frameState.bci != FrameState.BEFORE_BCI : frameState;
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java Mon Apr 22 13:29:55 2013 +0200 @@ -29,6 +29,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.VirtualState.NodeClosure; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; @@ -129,10 +130,12 @@ @Override protected void run(StructuredGraph graph) { + NodeProbabilities nodeProbabilities = new ComputeProbabilityClosure(graph).run(); + // A snapshot is taken here, so that new MergeNode instances aren't considered for tail // duplication. for (MergeNode merge : graph.getNodes(MergeNode.class).snapshot()) { - if (!(merge instanceof LoopBeginNode) && merge.probability() >= GraalOptions.TailDuplicationProbability) { + if (!(merge instanceof LoopBeginNode) && nodeProbabilities.getProbability(merge) >= GraalOptions.TailDuplicationProbability) { tailDuplicate(merge, DEFAULT_DECISION, null); } } @@ -219,7 +222,7 @@ * </ul> */ private void duplicate() { - Debug.log("tail duplication at merge %s in %s (prob %f)", merge, graph.method(), merge.probability()); + Debug.log("tail duplication at merge %s in %s", merge, graph.method()); ValueAnchorNode anchor = addValueAnchor(); @@ -420,9 +423,7 @@ */ private EndNode createNewMerge(FixedNode successor, FrameState stateAfterMerge) { MergeNode newBottomMerge = graph.add(new MergeNode()); - newBottomMerge.setProbability(successor.probability()); EndNode newBottomEnd = graph.add(new EndNode()); - newBottomEnd.setProbability(successor.probability()); newBottomMerge.addForwardEnd(newBottomEnd); newBottomMerge.setStateAfter(stateAfterMerge); ((FixedWithNextNode) successor.predecessor()).setNext(newBottomEnd);
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Mon Apr 22 13:29:55 2013 +0200 @@ -47,8 +47,6 @@ static boolean InlineMegamorphicCalls = ____; public static int MaximumDesiredSize = 5000; public static int MaximumRecursiveInlining = 1; - public static boolean LimitInlinedProbability = ____; - public static boolean LimitInlinedRelevance = true; public static float BoostInliningForEscapeAnalysis = 2f; public static float RelevanceCapForInlining = 1f; public static boolean IterativeInlining = ____;
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Mon Apr 22 13:29:55 2013 +0200 @@ -146,7 +146,8 @@ } else if (object instanceof StructuredGraph) { if (cfgPrinter.cfg == null) { - cfgPrinter.cfg = ControlFlowGraph.compute((StructuredGraph) object, true, true, true, false); + StructuredGraph graph = (StructuredGraph) object; + cfgPrinter.cfg = ControlFlowGraph.compute(graph, true, true, true, false); } cfgPrinter.printCFG(message, Arrays.asList(cfgPrinter.cfg.getBlocks()));
--- a/graal/com.oracle.graal.replacements.test/src/com/oracle/graal/replacements/test/MethodSubstitutionTest.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.replacements.test/src/com/oracle/graal/replacements/test/MethodSubstitutionTest.java Mon Apr 22 13:29:55 2013 +0200 @@ -50,7 +50,6 @@ StructuredGraph graph = parse(snippet); PhasePlan phasePlan = getDefaultPhasePlan(); Assumptions assumptions = new Assumptions(true); - new ComputeProbabilityPhase().apply(graph); Debug.dump(graph, "Graph"); new InliningPhase(runtime(), null, replacements, assumptions, null, phasePlan, OptimisticOptimizations.ALL).apply(graph); Debug.dump(graph, "Graph");
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsImpl.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsImpl.java Mon Apr 22 13:29:55 2013 +0200 @@ -379,10 +379,7 @@ end.disableSafepoint(); } - if (GraalOptions.ProbabilityAnalysis) { - new DeadCodeEliminationPhase().apply(graph); - new ComputeProbabilityPhase().apply(graph); - } + new DeadCodeEliminationPhase().apply(graph); return graph; } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Mon Apr 22 13:29:55 2013 +0200 @@ -169,7 +169,6 @@ MaterializeObjectNode materialize = new MaterializeObjectNode(virtual, obj.getLockCount()); ValueNode[] values = new ValueNode[obj.getEntries().length]; - materialize.setProbability(fixed.probability()); obj.escape(materialize, state); deferred.add(virtual); for (int i = 0; i < fieldState.length; i++) {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Mon Apr 22 13:29:55 2013 +0200 @@ -49,7 +49,6 @@ assert position.isAlive(); DynamicCounterNode node = graph.add(new DynamicCounterNode(name, increment, addContext)); graph.addBeforeFixed(position, node); - node.setProbability(position.probability()); } }); } @@ -70,7 +69,6 @@ assert position.isAlive(); DynamicCounterNode node = graph.add(new SurvivingCounterNode(name, increment, addContext, checkedValue)); graph.addBeforeFixed(position, node); - node.setProbability(position.probability()); } }); } @@ -94,7 +92,6 @@ public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { assert !node.isAlive() && !node.isDeleted() && position.isAlive(); graph.addBeforeFixed(position, graph.add(node)); - node.setProbability(position.probability()); } }); } @@ -140,7 +137,6 @@ public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { assert !node.isAlive() && !node.isDeleted() && position.isAlive(); graph.addBeforeFixed(position, graph.add(node)); - node.setProbability(position.probability()); for (int i = 0; i < values.length; i++) { node.getValues().set(i, values[i]); }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Sun Apr 21 21:41:09 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Mon Apr 22 13:29:55 2013 +0200 @@ -29,6 +29,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; @@ -200,20 +201,21 @@ } public static Map<Invoke, Double> getHints(StructuredGraph graph) { + NodeProbabilities probabilities = new ComputeProbabilityClosure(graph).run(); Map<Invoke, Double> hints = null; for (MaterializeObjectNode materialize : graph.getNodes(MaterializeObjectNode.class)) { double sum = 0; double invokeSum = 0; for (Node usage : materialize.usages()) { if (usage instanceof FixedNode) { - sum += ((FixedNode) usage).probability(); + sum += probabilities.getProbability((FixedNode) usage); } else { if (usage instanceof MethodCallTargetNode) { - invokeSum += ((MethodCallTargetNode) usage).invoke().probability(); + invokeSum += probabilities.getProbability(((MethodCallTargetNode) usage).invoke().asNode()); } for (Node secondLevelUage : materialize.usages()) { if (secondLevelUage instanceof FixedNode) { - sum += ((FixedNode) secondLevelUage).probability(); + sum += probabilities.getProbability(((FixedNode) secondLevelUage)); } } }