# HG changeset patch # User Christian Haeubl # Date 1366645753 -7200 # Node ID 8f01fe16e473395c686d7a6ced4ba656e7e3cf2e # Parent 5fbee58dba3354e0931db45d645e4d839de86b3b refactorings and cleanups for the removal of FixedNode.probability diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java --- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Mon Apr 22 17:49:13 2013 +0200 @@ -26,6 +26,7 @@ import java.util.*; import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.util.*; /** * Computes an ordering of the block that can be used by the linear scan register allocator and the @@ -66,7 +67,7 @@ * * @return sorted list of blocks */ - public static List computeLinearScanOrder(int blockCount, Block startBlock, NodeProbabilities nodeProbabilities) { + public static List computeLinearScanOrder(int blockCount, Block startBlock, NodesToDoubles nodeProbabilities) { List order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); PriorityQueue worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); @@ -80,7 +81,7 @@ * * @return sorted list of blocks */ - public static List computeCodeEmittingOrder(int blockCount, Block startBlock, NodeProbabilities nodeProbabilities) { + public static List computeCodeEmittingOrder(int blockCount, Block startBlock, NodesToDoubles nodeProbabilities) { List order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); PriorityQueue worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); @@ -92,7 +93,7 @@ /** * Iteratively adds paths to the code emission block order. */ - private static void computeCodeEmittingOrder(List order, PriorityQueue worklist, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { + private static void computeCodeEmittingOrder(List order, PriorityQueue worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { while (!worklist.isEmpty()) { Block nextImportantPath = worklist.poll(); addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); @@ -102,7 +103,7 @@ /** * Iteratively adds paths to the linear scan block order. */ - private static void computeLinearScanOrder(List order, PriorityQueue worklist, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { + private static void computeLinearScanOrder(List order, PriorityQueue worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { while (!worklist.isEmpty()) { Block nextImportantPath = worklist.poll(); addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); @@ -112,7 +113,7 @@ /** * Initializes the priority queue used for the work list of blocks and adds the start block. */ - private static PriorityQueue initializeWorklist(Block startBlock, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { + private static PriorityQueue initializeWorklist(Block startBlock, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { PriorityQueue result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(nodeProbabilities)); result.add(startBlock); visitedBlocks.set(startBlock.getId()); @@ -122,7 +123,7 @@ /** * Add a linear path to the linear scan order greedily following the most likely successor. */ - private static void addPathToLinearScanOrder(Block block, List order, PriorityQueue worklist, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { + private static void addPathToLinearScanOrder(Block block, List order, PriorityQueue worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { block.setLinearScanNumber(order.size()); order.add(block); Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); @@ -134,11 +135,11 @@ double unscheduledSum = 0.0; for (Block pred : mostLikelySuccessor.getPredecessors()) { if (pred.getLinearScanNumber() == -1) { - unscheduledSum += nodeProbabilities.getProbability(pred.getBeginNode()); + unscheduledSum += nodeProbabilities.get(pred.getBeginNode()); } } - if (unscheduledSum > nodeProbabilities.getProbability(block.getBeginNode()) / PENALTY_VERSUS_UNSCHEDULED) { + if (unscheduledSum > nodeProbabilities.get(block.getBeginNode()) / PENALTY_VERSUS_UNSCHEDULED) { // Add this merge only after at least one additional predecessor gets scheduled. visitedBlocks.clear(mostLikelySuccessor.getId()); return; @@ -151,7 +152,7 @@ /** * Add a linear path to the code emission order greedily following the most likely successor. */ - private static void addPathToCodeEmittingOrder(Block block, List order, PriorityQueue worklist, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { + private static void addPathToCodeEmittingOrder(Block block, List order, PriorityQueue worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { // Skip loop headers if there is only a single loop end block to make the backward jump be a // conditional jump. @@ -198,12 +199,12 @@ /** * Find the highest likely unvisited successor block of a given block. */ - private static Block findAndMarkMostLikelySuccessor(Block block, BitSet visitedBlocks, NodeProbabilities nodeProbabilities) { + private static Block findAndMarkMostLikelySuccessor(Block block, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { Block result = null; for (Block successor : block.getSuccessors()) { - assert nodeProbabilities.getProbability(successor.getBeginNode()) >= 0.0 : "Probabilities must be positive"; + assert nodeProbabilities.get(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 == null || nodeProbabilities.get(successor.getBeginNode()) >= nodeProbabilities.get(result.getBeginNode()))) { result = successor; } } @@ -246,9 +247,9 @@ */ private static class BlockOrderComparator implements Comparator { - private final NodeProbabilities probabilities; + private final NodesToDoubles probabilities; - public BlockOrderComparator(NodeProbabilities probabilities) { + public BlockOrderComparator(NodesToDoubles probabilities) { this.probabilities = probabilities; } @@ -261,7 +262,7 @@ } // Blocks with high probability before blocks with low probability. - if (probabilities.getProbability(a.getBeginNode()) > probabilities.getProbability(b.getBeginNode())) { + if (probabilities.get(a.getBeginNode()) > probabilities.get(b.getBeginNode())) { return -1; } else { return 1; diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Mon Apr 22 17:49:13 2013 +0200 @@ -33,10 +33,11 @@ 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.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.virtual.nodes.*; import com.oracle.graal.virtual.phases.ea.*; @@ -133,11 +134,11 @@ 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(); + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(result).apply(); double probabilitySum = 0; int materializeCount = 0; for (MaterializeObjectNode materialize : result.getNodes(MaterializeObjectNode.class)) { - probabilitySum += nodeProbabilities.getProbability(materialize); + probabilitySum += nodeProbabilities.get(materialize); materializeCount++; } Assert.assertEquals("unexpected number of MaterializeObjectNodes", expectedCount, materializeCount); diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Apr 22 17:49:13 2013 +0200 @@ -38,9 +38,11 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.schedule.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.virtual.phases.ea.*; @@ -170,7 +172,7 @@ @Override public LIR call() { - NodeProbabilities nodeProbabilities = new ComputeProbabilityClosure(graph).run(); + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); List codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock, nodeProbabilities); List linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock, nodeProbabilities); diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Mon Apr 22 17:49:13 2013 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; public abstract class LoopPolicies { @@ -35,9 +36,9 @@ } // TODO (gd) change when inversion is available - public static boolean shouldPeel(LoopEx loop, NodeProbabilities probabilities) { + public static boolean shouldPeel(LoopEx loop, NodesToDoubles probabilities) { LoopBeginNode loopBegin = loop.loopBegin(); - double entryProbability = probabilities.getProbability(loopBegin.forwardEnd()); + double entryProbability = probabilities.get(loopBegin.forwardEnd()); return entryProbability > GraalOptions.MinimumPeelProbability && loop.size() + loopBegin.graph().getNodeCount() < GraalOptions.MaximumDesiredSize; } diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java Mon Apr 22 17:49:13 2013 +0200 @@ -25,9 +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.nodes.util.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.graph.*; public class LoopTransformHighPhase extends Phase { @@ -35,7 +35,7 @@ protected void run(StructuredGraph graph) { if (graph.hasLoops()) { if (GraalOptions.LoopPeeling) { - NodeProbabilities probabilities = new ComputeProbabilityClosure(graph).run(); + NodesToDoubles probabilities = new ComputeProbabilityClosure(graph).apply(); LoopsData data = new LoopsData(graph); for (LoopEx loop : data.outterFirst()) { if (LoopPolicies.shouldPeel(loop, probabilities)) { diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/NodeProbabilities.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/NodeProbabilities.java Mon Apr 22 17:06:06 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,50 +0,0 @@ -/* - * 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 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(); - } -} diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodesToDoubles.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodesToDoubles.java Mon Apr 22 17:49:13 2013 +0200 @@ -0,0 +1,46 @@ +/* + * 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.util; + +import java.util.*; + +import com.oracle.graal.nodes.*; + +public class NodesToDoubles { + + private final IdentityHashMap nodeProbabilities; + + public NodesToDoubles(int numberOfNodes) { + this.nodeProbabilities = new IdentityHashMap<>(numberOfNodes); + } + + public void put(FixedNode n, double value) { + nodeProbabilities.put(n, value); + } + + public double get(FixedNode n) { + Double value = nodeProbabilities.get(n); + assert value != null; + return value; + } +} diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeInliningRelevanceClosure.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeInliningRelevanceClosure.java Mon Apr 22 17:06:06 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,223 +0,0 @@ -/* - * 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 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 computeLowestPathProbabilities() { - HashMap 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 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 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 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 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 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 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; - } - } -} diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityClosure.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityClosure.java Mon Apr 22 17:06:06 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,296 +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.graph.*; - -/** - * Computes probabilities for nodes in a graph. - *

- * The computation of absolute probabilities works in three steps: - *

    - *
  1. {@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.
    2. - *
  2. - *
  3. {@link PropagateLoopFrequency} propagates the loop frequencies and multiplies each - * {@link FixedNode}'s probability with its loop frequency.
    4. - *
- * 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 loopInfos; - private final Map> 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> 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 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 { - - public double probability; - public HashSet loops; - public LoopInfo loopInfo; - - public Probability(double probability, HashSet 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 withStates) { - if (merge.forwardEndCount() > 1) { - HashSet 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 loopEndStates) { - assert loopInfo != null; - List loopEnds = loopBegin.orderedLoopEnds(); - int i = 0; - for (Probability proba : loopEndStates) { - LoopEndNode loopEnd = loopEnds.get(i++); - Set 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 { - - 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 { - - 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 withStates) { - assert merge.forwardEndCount() == withStates.size() + 1; - if (merge.forwardEndCount() > 1) { - Set 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 loopEndStates) { - // nothing to do... - } - - @Override - public void afterSplit(BeginNode node) { - // nothing to do... - } - } - - private class PropagateLoopFrequency extends PostOrderNodeIterator { - - public PropagateLoopFrequency(FixedNode start) { - super(start, new LoopCount(1d)); - } - - @Override - protected void node(FixedNode node) { - nodeProbabilities.setProbability(node, nodeProbabilities.getProbability(node) * state.count); - } - - } -} diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Mon Apr 22 17:49:13 2013 +0200 @@ -31,15 +31,16 @@ 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.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; import com.oracle.graal.phases.common.InliningUtil.InlineInfo; import com.oracle.graal.phases.common.InliningUtil.InliningCallback; import com.oracle.graal.phases.common.InliningUtil.InliningPolicy; +import com.oracle.graal.phases.graph.*; public class InliningPhase extends Phase implements InliningCallback { @@ -100,8 +101,8 @@ @Override protected void run(final StructuredGraph graph) { - NodeProbabilities nodeProbabilities = new ComputeProbabilityClosure(graph).run(); - NodeProbabilities nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).run(); + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + NodesToDoubles nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); inliningPolicy.initialize(graph); while (inliningPolicy.continueInlining(graph)) { @@ -124,8 +125,8 @@ new CanonicalizerPhase.Instance(runtime, assumptions, invokeUsages, mark, customCanonicalizer).apply(graph); } - nodeProbabilities = new ComputeProbabilityClosure(graph).run(); - nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).run(); + nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); inliningCount++; metricInliningPerformed.increment(); @@ -164,9 +165,8 @@ } assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; - if (GraalOptions.ProbabilityAnalysis) { - new DeadCodeEliminationPhase().apply(newGraph); - } + new DeadCodeEliminationPhase().apply(newGraph); + if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); } @@ -183,7 +183,7 @@ private interface InliningDecision { - boolean isWorthInlining(InlineInfo info, NodeProbabilities nodeProbabilities, NodeProbabilities nodeRelevance); + boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance); } private static class GreedySizeBasedInliningDecision implements InliningDecision { @@ -199,8 +199,7 @@ } @Override - public boolean isWorthInlining(InlineInfo info, NodeProbabilities nodeProbabilities, NodeProbabilities nodeRelevance) { - assert GraalOptions.ProbabilityAnalysis; + public boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance) { /* * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> * will be compiled anyways and it is likely that we are the only caller... might be @@ -226,7 +225,7 @@ int bytecodeSize = (int) (bytecodeCodeSize(info) / bonus); int complexity = (int) (compilationComplexity(info) / bonus); int compiledCodeSize = (int) (compiledCodeSize(info) / bonus); - double relevance = nodeRelevance.getProbability(info.invoke().asNode()); + double relevance = nodeRelevance.get(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 @@ -245,7 +244,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 = nodeProbabilities.getProbability(info.invoke().asNode()); + double probability = nodeProbabilities.get(info.invoke().asNode()); int transferredValues = numberOfTransferredValues(info); int invokeUsages = countInvokeUsages(info); int moreSpecificArguments = countMoreSpecificArgumentInfo(info); @@ -415,7 +414,7 @@ } @Override - public boolean isWorthInlining(InlineInfo info, NodeProbabilities nodeProbabilities, NodeProbabilities nodeRelevance) { + public boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance) { return inliningDecision.isWorthInlining(info, nodeProbabilities, nodeRelevance); } diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Mon Apr 22 17:49:13 2013 +0200 @@ -35,7 +35,6 @@ 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; @@ -71,7 +70,7 @@ void scanInvokes(Iterable newNodes); - boolean isWorthInlining(InlineInfo info, NodeProbabilities nodeProbabilities, NodeProbabilities nodeRelevance); + boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance); } /** diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java Mon Apr 22 17:49:13 2013 +0200 @@ -29,13 +29,13 @@ 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.*; import com.oracle.graal.nodes.type.*; import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.graph.*; /** * This class is a phase that looks for opportunities for tail duplication. The static method @@ -130,12 +130,12 @@ @Override protected void run(StructuredGraph graph) { - NodeProbabilities nodeProbabilities = new ComputeProbabilityClosure(graph).run(); + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); // 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) && nodeProbabilities.getProbability(merge) >= GraalOptions.TailDuplicationProbability) { + if (!(merge instanceof LoopBeginNode) && nodeProbabilities.get(merge) >= GraalOptions.TailDuplicationProbability) { tailDuplicate(merge, DEFAULT_DECISION, null); } } diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Mon Apr 22 17:49:13 2013 +0200 @@ -73,9 +73,6 @@ public static double TailDuplicationProbability = 0.5; public static int TailDuplicationTrivialSize = 1; - // absolute probability analysis - public static boolean ProbabilityAnalysis = true; - // profiling information public static int DeoptsToDisableOptimisticOptimization = 40; public static int MatureExecutionsBranch = 1; diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java Mon Apr 22 17:49:13 2013 +0200 @@ -53,10 +53,6 @@ if (checkDeoptimizations(method.getProfilingInfo(), deoptReason)) { enabledOpts.add(optimization); } else { - /* - * TODO (chaeubl): see GRAAL-75 (remove when we are sure that optimistic optimizations - * are not disabled unnecessarily - */ disabledOptimisticOptsMetric.increment(); } } diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeInliningRelevanceClosure.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeInliningRelevanceClosure.java Mon Apr 22 17:49:13 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.graph; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.util.*; + +public class ComputeInliningRelevanceClosure { + + private static final double EPSILON = 1d / Integer.MAX_VALUE; + + private final StructuredGraph graph; + private final NodesToDoubles nodeProbabilities; + private final NodesToDoubles nodeRelevances; + + public ComputeInliningRelevanceClosure(StructuredGraph graph, NodesToDoubles nodeProbabilities) { + this.graph = graph; + this.nodeProbabilities = nodeProbabilities; + this.nodeRelevances = new NodesToDoubles(graph.getNodeCount()); + } + + public NodesToDoubles apply() { + new ComputeInliningRelevanceIterator(graph).apply(); + return nodeRelevances; + } + + private class ComputeInliningRelevanceIterator extends ScopedPostOrderNodeIterator { + + private final HashMap 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.get(end); + } + return parentProbability / scope.parent.minPathProbability; + } else { + assert scope.parent == null; + return 1.0; + } + } + + @Override + protected void invoke(Invoke invoke) { + double probability = nodeProbabilities.get(invoke.asNode()); + assert !Double.isNaN(probability); + + double relevance = (probability / currentProbability) * Math.min(1.0, parentRelevance); + nodeRelevances.put(invoke.asNode(), relevance); + assert !Double.isNaN(relevance); + } + + private HashMap computeLowestPathProbabilities() { + HashMap 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 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 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 pathBeginNodes = new ArrayList<>(); + pathBeginNodes.add(scopeStart); + double minPathProbability = nodeProbabilities.get(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.get(current) < minPathProbability) { + return nodeProbabilities.get(current); + } + return minPathProbability; + } + + private Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList 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 pathBeginNodes) { + Node maxSux = null; + double maxProbability = 0.0; + int pathBeginCount = pathBeginNodes.size(); + + for (LoopExitNode sux : loopBegin.loopExits()) { + double probability = nodeProbabilities.get(sux); + if (probability > maxProbability) { + maxProbability = probability; + maxSux = sux; + truncate(pathBeginNodes, pathBeginCount); + } else if (probability == maxProbability) { + pathBeginNodes.add(sux); + } + } + + return maxSux; + } + + private void truncate(ArrayList 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; + } + } +} diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java Mon Apr 22 17:49:13 2013 +0200 @@ -0,0 +1,295 @@ +/* + * 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.graph; + +import java.util.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.util.*; + +/** + * Computes probabilities for nodes in a graph. + *

+ * The computation of absolute probabilities works in three steps: + *

    + *
  1. {@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.
    2. + *
  2. + *
  3. {@link PropagateLoopFrequency} propagates the loop frequencies and multiplies each + * {@link FixedNode}'s probability with its loop frequency.
    4. + *
+ * 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 NodesToDoubles nodeProbabilities; + private final Set loopInfos; + private final Map> mergeLoops; + + public ComputeProbabilityClosure(StructuredGraph graph) { + this.graph = graph; + this.nodeProbabilities = new NodesToDoubles(graph.getNodeCount()); + this.loopInfos = new HashSet<>(); + this.mergeLoops = new IdentityHashMap<>(); + } + + public NodesToDoubles apply() { + 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> requires; + + private double loopFrequency = -1; + public boolean ended = false; + + public LoopInfo(LoopBeginNode loopBegin) { + this.loopBegin = loopBegin; + this.requires = loopBegin.graph().createNodeMap(); + } + + public double loopFrequency(NodesToDoubles nodeProbabilities) { + if (loopFrequency == -1 && ended) { + double backEdgeProb = 0.0; + for (LoopEndNode le : loopBegin.loopEnds()) { + double factor = 1; + Set requireds = requires.get(le); + for (LoopInfo required : requireds) { + double t = required.loopFrequency(nodeProbabilities); + if (t == -1) { + return -1; + } + factor *= t; + } + backEdgeProb += nodeProbabilities.get(le) * factor; + } + double d = nodeProbabilities.get(loopBegin) - backEdgeProb; + if (d < EPSILON) { + d = EPSILON; + } + loopFrequency = nodeProbabilities.get(loopBegin) / d; + loopBegin.setLoopFrequency(loopFrequency); + } + return loopFrequency; + } + } + + private class Probability implements MergeableState { + + public double probability; + public HashSet loops; + public LoopInfo loopInfo; + + public Probability(double probability, HashSet 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 withStates) { + if (merge.forwardEndCount() > 1) { + HashSet 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 loopEndStates) { + assert loopInfo != null; + List loopEnds = loopBegin.orderedLoopEnds(); + int i = 0; + for (Probability proba : loopEndStates) { + LoopEndNode loopEnd = loopEnds.get(i++); + Set 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 { + + public PropagateProbability(FixedNode start) { + super(start, new Probability(1d, null)); + } + + @Override + protected void node(FixedNode node) { + nodeProbabilities.put(node, state.probability); + } + } + + private class LoopCount implements MergeableState { + + 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 withStates) { + assert merge.forwardEndCount() == withStates.size() + 1; + if (merge.forwardEndCount() > 1) { + Set 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 loopEndStates) { + // nothing to do... + } + + @Override + public void afterSplit(BeginNode node) { + // nothing to do... + } + } + + private class PropagateLoopFrequency extends PostOrderNodeIterator { + + public PropagateLoopFrequency(FixedNode start) { + super(start, new LoopCount(1d)); + } + + @Override + protected void node(FixedNode node) { + nodeProbabilities.put(node, nodeProbabilities.get(node) * state.count); + } + + } +} diff -r 5fbee58dba33 -r 8f01fe16e473 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Mon Apr 22 17:06:06 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Mon Apr 22 17:49:13 2013 +0200 @@ -29,9 +29,9 @@ 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.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; @@ -201,21 +201,21 @@ } public static Map getHints(StructuredGraph graph) { - NodeProbabilities probabilities = new ComputeProbabilityClosure(graph).run(); + NodesToDoubles probabilities = new ComputeProbabilityClosure(graph).apply(); Map 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 += probabilities.getProbability((FixedNode) usage); + sum += probabilities.get((FixedNode) usage); } else { if (usage instanceof MethodCallTargetNode) { - invokeSum += probabilities.getProbability(((MethodCallTargetNode) usage).invoke().asNode()); + invokeSum += probabilities.get(((MethodCallTargetNode) usage).invoke().asNode()); } for (Node secondLevelUage : materialize.usages()) { if (secondLevelUage instanceof FixedNode) { - sum += probabilities.getProbability(((FixedNode) secondLevelUage)); + sum += probabilities.get(((FixedNode) secondLevelUage)); } } }