Mercurial > hg > truffle
changeset 4986:c4a0a220e0f3
small fix to loop frequency propagation
added a loop frequency propagation policy that uses a higher penalty for hot loops in cold code
author | Christian Haeubl <christian.haeubl@oracle.com> |
---|---|
date | Mon, 27 Feb 2012 14:47:55 -0800 |
parents | a59fe7906f0b |
children | f292f9c590ba |
files | graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java |
diffstat | 1 files changed, 36 insertions(+), 37 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java Mon Feb 27 19:41:14 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java Mon Feb 27 14:47:55 2012 -0800 @@ -24,7 +24,6 @@ import java.util.*; -import com.oracle.max.criutils.*; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.graph.*; import com.oracle.max.graal.debug.*; @@ -57,42 +56,52 @@ Debug.dump(graph, "After computeLoopFactors"); new PropagateLoopFrequency(graph.start()).apply(); - ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); - if (GraalOptions.LoopFrequencyPropagationPolicy < 0) { + ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); + BitMap visitedBlocks = new BitMap(cfg.getBlocks().length); for (Loop loop : cfg.getLoops()) { if (loop.parent == null) { - correctLoopFrequencies(loop); + correctLoopFrequencies(loop, 1, visitedBlocks); } } } } - private void correctLoopFrequencies(Loop loop) { - double frequency = ((LoopBeginNode) loop.header.getBeginNode()).loopFrequency(); + private void correctLoopFrequencies(Loop loop, double parentFrequency, BitMap visitedBlocks) { + LoopBeginNode loopBegin = ((LoopBeginNode) loop.header.getBeginNode()); + double frequency = parentFrequency * loopBegin.loopFrequency(); + for (Loop child : loop.children) { + correctLoopFrequencies(child, frequency, visitedBlocks); + } - double factor; + double factor = getCorrectionFactor(loopBegin.probability(), frequency); + for (Block block : loop.blocks) { + int blockId = block.getId(); + if (!visitedBlocks.get(blockId)) { + visitedBlocks.set(blockId); + + FixedNode node = block.getBeginNode(); + while (node != block.getEndNode()) { + node.setProbability(node.probability() * factor); + node = ((FixedWithNextNode) node).next(); + } + node.setProbability(node.probability() * factor); + } + } + } + + private static double getCorrectionFactor(double probability, double frequency) { switch (GraalOptions.LoopFrequencyPropagationPolicy) { case -1: - factor = 1 / frequency; - break; + return 1 / frequency; case -2: - factor = (1 / frequency) * (Math.log(Math.E + frequency) - 1); - break; - default: throw GraalInternalError.shouldNotReachHere(); - } - - for (Block block : loop.blocks) { - FixedNode node = block.getBeginNode(); - - while (node != block.getEndNode()) { - node.setProbability(node.probability() * factor); - node = ((FixedWithNextNode) node).next(); - } - } - - for (Loop child : loop.children) { - correctLoopFrequencies(child); + return (1 / frequency) * (Math.log(Math.E + frequency) - 1); + case -3: + double originalProbability = probability / frequency; + assert isRelativeProbability(originalProbability); + return (1 / frequency) * Math.max(1, Math.pow(originalProbability, 1.5) * Math.log10(frequency)); + default: + throw GraalInternalError.shouldNotReachHere(); } } @@ -330,14 +339,13 @@ private static FrequencyPropagationPolicy createFrequencyPropagationPolicy() { switch (GraalOptions.LoopFrequencyPropagationPolicy) { + case -3: + case -2: case -1: - case -2: case 0: return new FullFrequencyPropagation(); case 1: return new NoFrequencyPropagation(); - case 2: - return new LogarithmicFrequencyPropagation(); default: throw GraalInternalError.shouldNotReachHere(); } @@ -363,13 +371,4 @@ return probability; } } - - private static class LogarithmicFrequencyPropagation implements FrequencyPropagationPolicy { - - @Override - public double compute(double probability, double frequency) { - double result = Math.pow(probability, 1.5) * Math.log(frequency); - return Math.max(probability, result); - } - } }