< prev index next >
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/cfg/ControlFlowGraph.java
Print this page
rev 52509 : [mq]: graal
*** 51,68 ****
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
/**
! * Don't allow probability values to be become too small or too high as this makes frequency
! * calculations over- or underflow the range of a double. This commonly happens with infinite
! * loops within infinite loops. The value is chosen a bit lower than half the maximum exponent
! * supported by double. That way we can never overflow to infinity when multiplying two
! * probability values.
*/
! public static final double MIN_PROBABILITY = 0x1.0p-500;
! public static final double MAX_PROBABILITY = 1 / MIN_PROBABILITY;
public final StructuredGraph graph;
private NodeMap<Block> nodeToBlock;
private Block[] reversePostOrder;
--- 51,68 ----
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
/**
! * Don't allow relative frequency values to be become too small or too high as this makes
! * frequency calculations over- or underflow the range of a double. This commonly happens with
! * infinite loops within infinite loops. The value is chosen a bit lower than half the maximum
! * exponent supported by double. That way we can never overflow to infinity when multiplying two
! * relative frequency values.
*/
! public static final double MIN_RELATIVE_FREQUENCY = 0x1.0p-500;
! public static final double MAX_RELATIVE_FREQUENCY = 1 / MIN_RELATIVE_FREQUENCY;
public final StructuredGraph graph;
private NodeMap<Block> nodeToBlock;
private Block[] reversePostOrder;
*** 76,86 ****
}
public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
ControlFlowGraph cfg = new ControlFlowGraph(graph);
cfg.identifyBlocks();
! cfg.computeProbabilities();
if (computeLoops) {
cfg.computeLoopInformation();
}
if (computeDominators) {
--- 76,86 ----
}
public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
ControlFlowGraph cfg = new ControlFlowGraph(graph);
cfg.identifyBlocks();
! cfg.computeFrequencies();
if (computeLoops) {
cfg.computeLoopInformation();
}
if (computeDominators) {
*** 422,432 ****
}
private void identifyBlock(Block block) {
FixedWithNextNode cur = block.getBeginNode();
while (true) {
! assert !cur.isDeleted();
assert nodeToBlock.get(cur) == null;
nodeToBlock.set(cur, block);
FixedNode next = cur.next();
if (next instanceof AbstractBeginNode) {
block.endNode = cur;
--- 422,432 ----
}
private void identifyBlock(Block block) {
FixedWithNextNode cur = block.getBeginNode();
while (true) {
! assert cur.isAlive() : cur;
assert nodeToBlock.get(cur) == null;
nodeToBlock.set(cur, block);
FixedNode next = cur.next();
if (next instanceof AbstractBeginNode) {
block.endNode = cur;
*** 548,590 ****
predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]);
}
block.setPredecessors(predecessors);
}
! private void computeProbabilities() {
for (Block block : reversePostOrder) {
Block[] predecessors = block.getPredecessors();
! double probability;
if (predecessors.length == 0) {
! probability = 1D;
} else if (predecessors.length == 1) {
Block pred = predecessors[0];
! probability = pred.probability;
if (pred.getSuccessorCount() > 1) {
assert pred.getEndNode() instanceof ControlSplitNode;
ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
! probability = multiplyProbabilities(probability, controlSplit.probability(block.getBeginNode()));
}
} else {
! probability = predecessors[0].probability;
for (int i = 1; i < predecessors.length; ++i) {
! probability += predecessors[i].probability;
}
if (block.getBeginNode() instanceof LoopBeginNode) {
LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
! probability = multiplyProbabilities(probability, loopBegin.loopFrequency());
}
}
! if (probability < MIN_PROBABILITY) {
! probability = MIN_PROBABILITY;
! } else if (probability > MAX_PROBABILITY) {
! probability = MAX_PROBABILITY;
}
! block.setProbability(probability);
}
}
private void computeLoopInformation() {
--- 548,595 ----
predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]);
}
block.setPredecessors(predecessors);
}
! /**
! * Computes the frequencies of all blocks relative to the start block. It uses the probability
! * information attached to control flow splits to calculate the frequency of a block based on
! * the frequency of its predecessor and the probability of its incoming control flow branch.
! */
! private void computeFrequencies() {
for (Block block : reversePostOrder) {
Block[] predecessors = block.getPredecessors();
! double relativeFrequency;
if (predecessors.length == 0) {
! relativeFrequency = 1D;
} else if (predecessors.length == 1) {
Block pred = predecessors[0];
! relativeFrequency = pred.relativeFrequency;
if (pred.getSuccessorCount() > 1) {
assert pred.getEndNode() instanceof ControlSplitNode;
ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
! relativeFrequency = multiplyRelativeFrequencies(relativeFrequency, controlSplit.probability(block.getBeginNode()));
}
} else {
! relativeFrequency = predecessors[0].relativeFrequency;
for (int i = 1; i < predecessors.length; ++i) {
! relativeFrequency += predecessors[i].relativeFrequency;
}
if (block.getBeginNode() instanceof LoopBeginNode) {
LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
! relativeFrequency = multiplyRelativeFrequencies(relativeFrequency, loopBegin.loopFrequency());
}
}
! if (relativeFrequency < MIN_RELATIVE_FREQUENCY) {
! relativeFrequency = MIN_RELATIVE_FREQUENCY;
! } else if (relativeFrequency > MAX_RELATIVE_FREQUENCY) {
! relativeFrequency = MAX_RELATIVE_FREQUENCY;
}
! block.setRelativeFrequency(relativeFrequency);
}
}
private void computeLoopInformation() {
*** 761,780 ****
public void setNodeToBlock(NodeMap<Block> nodeMap) {
this.nodeToBlock = nodeMap;
}
/**
! * Multiplies a and b and clamps the between {@link ControlFlowGraph#MIN_PROBABILITY} and
! * {@link ControlFlowGraph#MAX_PROBABILITY}.
*/
! public static double multiplyProbabilities(double a, double b) {
assert !Double.isNaN(a) && !Double.isNaN(b) && Double.isFinite(a) && Double.isFinite(b) : a + " " + b;
double r = a * b;
! if (r > MAX_PROBABILITY) {
! return MAX_PROBABILITY;
}
! if (r < MIN_PROBABILITY) {
! return MIN_PROBABILITY;
}
return r;
}
}
--- 766,785 ----
public void setNodeToBlock(NodeMap<Block> nodeMap) {
this.nodeToBlock = nodeMap;
}
/**
! * Multiplies a and b and clamps the between {@link ControlFlowGraph#MIN_RELATIVE_FREQUENCY} and
! * {@link ControlFlowGraph#MAX_RELATIVE_FREQUENCY}.
*/
! public static double multiplyRelativeFrequencies(double a, double b) {
assert !Double.isNaN(a) && !Double.isNaN(b) && Double.isFinite(a) && Double.isFinite(b) : a + " " + b;
double r = a * b;
! if (r > MAX_RELATIVE_FREQUENCY) {
! return MAX_RELATIVE_FREQUENCY;
}
! if (r < MIN_RELATIVE_FREQUENCY) {
! return MIN_RELATIVE_FREQUENCY;
}
return r;
}
}
< prev index next >