# HG changeset patch # User Gilles Duboscq # Date 1312192180 -7200 # Node ID 970d06648c93159afff0507d24d6375bd91232e3 # Parent 13579dfa8a3c41a08cc573826381ad66d654b121 Changed liveRange computation in materialization cost & disable it for now diff -r 13579dfa8a3c -r 970d06648c93 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Mon Aug 01 10:33:53 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Mon Aug 01 11:49:40 2011 +0200 @@ -23,7 +23,6 @@ package com.oracle.max.graal.compiler.schedule; import java.util.*; -import java.util.Map.Entry; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; @@ -34,7 +33,7 @@ public class IdentifyBlocksPhase extends Phase { - private static final double LIVE_RANGE_COST_FACTOR = 0.1; + private static final double LIVE_RANGE_COST_FACTOR = 0.05; private static final double MATERIALIZATION_COST_FACTOR = 1.0 - LIVE_RANGE_COST_FACTOR; private final List blocks = new ArrayList(); @@ -335,10 +334,6 @@ block = earliestBlock(n); } else if (GraalOptions.ScheduleOutOfLoops) { block = scheduleOutOfLoops(n, latestBlock, earliestBlock(n)); - Block b2 = scheduleOutOfLoops(n, latestBlock); - if (block != b2) { - TTY.println(":> scheduleOutOfLoops disagreement for " + n + " : " + block + " vs. " + b2); - } } else { block = latestBlock; } @@ -369,14 +364,6 @@ return suxCount; } - private BitMap usagesBitMap(Set usages) { - BitMap usagesBitMap = new BitMap(blocks.size()); - for (Usage u : usages) { - usagesBitMap.set(u.block.blockID()); - } - return usagesBitMap; - } - private void maybeMaterialize(Node node, Block block, Map> usages, boolean materializedInDominator) { Set blockUsages = usages.get(block); @@ -404,7 +391,7 @@ for (Usage usage : blockUsages) { patch(usage, node, n); } - TTY.println("> Rematerialized " + node + " (new node id = " + n.id() + ") in " + block); + //TTY.println("> Rematerialized " + node + " (new node id = " + n.id() + ") in " + block); GraalMetrics.Rematerializations++; nodeToBlock.grow(n); } @@ -432,11 +419,7 @@ private double materializationCost(Block block, Set usages) { //TODO node cost - double blockProbability = block.probability(); - if (blockProbability <= 0.0) { - blockProbability = 0.01; - } - return LIVE_RANGE_COST_FACTOR * liveRange(block, usages) * MATERIALIZATION_COST_FACTOR * blockProbability * 1.0; + return /*LIVE_RANGE_COST_FACTOR * liveRange(block, usages) + MATERIALIZATION_COST_FACTOR **/ block.probability() * 1.0; } @@ -626,18 +609,6 @@ } } - private double liveRange(Block from, Set usages) { - BitMap notInRange = new BitMap(blocks.size()); - BitMap inRange = new BitMap(blocks.size()); - DoubleHolder range = new DoubleHolder(); - markInRange(from, inRange, notInRange, usagesBitMap(usages), range); - return range.value; - } - - private boolean noRematerialization(Node n) { - return n instanceof Local || n instanceof LocationNode || n instanceof Constant || n instanceof StateSplit || n instanceof FrameState || n instanceof CheckCast; //TODO why CheckCast ?? - } - private static class Usage { public final Block block; public final Node node; @@ -647,36 +618,38 @@ } } - private static class DoubleHolder{ - public double value; + private boolean noRematerialization(Node n) { + return n instanceof Local || n instanceof LocationNode || n instanceof Constant || n instanceof StateSplit || n instanceof FrameState; + } + + private double liveRange(Block from, Set usages) { + BitMap subTree = new BitMap(blocks.size()); + markSubTree(from, subTree); + double range = 0.0; + for (Usage usage : usages) { + range += markRangeUp(usage.block, subTree); + } + return range; } - private static boolean markInRange(Block b, BitMap inRange, BitMap notInRange, BitMap usages, DoubleHolder range) { - int blockID = b.blockID(); - if (notInRange.get(blockID)) { - return false; - } - if (inRange.get(blockID)) { - return true; - } - boolean ret = false; - if (usages.get(blockID)) { - ret = true; + private void markSubTree(Block from, BitMap subTree) { + subTree.set(from.blockID()); + for (Block b : from.getDominated()) { + markSubTree(b, subTree); } - if (!b.isLoopEnd()) { - for (Block sux : b.getSuccessors()) { - if (markInRange(sux, inRange, notInRange, usages, range)) { - ret = true; - } - } + } + + private double markRangeUp(Block from, BitMap subTree) { + int blockID = from.blockID(); + if (!subTree.get(blockID)) { + return 0.0; } - if (ret) { - inRange.set(blockID); - range.value += b.probability() * (b.getInstructions().size() + 2); - } else { - notInRange.set(blockID); + subTree.clear(blockID); + double range = from.probability() * (from.getInstructions().size() + 2); + for (Block pred : from.getPredecessors()) { + range += markRangeUp(pred, subTree); } - return ret; + return range; } private Block getCommonDominator(Block a, Block b) { @@ -859,62 +832,4 @@ } return i; } - - private Block scheduleOutOfLoops(Node n, Block latestBlock) { - Block cur = latestBlock; - while (cur.loopDepth() != 0) { - if (cur.isLoopHeader()) { - assert cur.getPredecessors().size() == 2 : cur.getPredecessors().size(); - if (canSchedule(n, cur.getPredecessors().get(0))) { - // TTY.println("can schedule out of loop!" + n); - return scheduleOutOfLoops(n, cur.getPredecessors().get(0)); - } else { - break; - } - } - Block prev = cur; - cur = cur.dominator(); - - // This must be a loop exit. - if (cur.loopDepth() > prev.loopDepth()) { -// TTY.println("break out because of different loop depth"); - break; - } - } - return latestBlock; - } - - private boolean canSchedule(Node n, Block block) { - Set allowedBlocks = new HashSet(); - Block cur = block; - while (cur != null) { - allowedBlocks.add(cur); - cur = cur.dominator(); - } - // Now we know the allowed blocks for inputs and predecessors. - return checkNodesAbove(allowedBlocks, n); - } - - private boolean checkNodesAbove(Set allowedBlocks, Node n) { - if (n == null) { - return true; - } - - if (nodeToBlock.get(n) != null) { - return allowedBlocks.contains(nodeToBlock.get(n)); - } else { - assert !(n instanceof Phi) : ((Phi) n).merge(); - for (Node input : n.inputs()) { - if (!checkNodesAbove(allowedBlocks, input)) { - return false; - } - } - for (Node pred : n.predecessors()) { - if (!checkNodesAbove(allowedBlocks, pred)) { - return false; - } - } - return true; - } - } }