Mercurial > hg > truffle
changeset 3156:bdc1a456a6e0
Added calculation of loop depth and loop index to scheduler.
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Tue Jul 05 19:49:35 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Wed Jul 06 11:52:31 2011 +0200 @@ -122,6 +122,7 @@ IdentifyBlocksPhase schedule = new IdentifyBlocksPhase(true); schedule.apply(graph); + compilation.stats.loopCount = schedule.loopCount(); List<Block> blocks = schedule.getBlocks(); @@ -132,6 +133,8 @@ map.put(b, block); block.setInstructions(b.getInstructions()); block.setLinearScanNumber(b.blockID()); + block.setLoopDepth(b.loopDepth()); + block.setLoopIndex(b.loopIndex()); block.setFirstInstruction(b.firstNode()); block.setLastInstruction(b.lastNode()); @@ -166,7 +169,6 @@ ComputeLinearScanOrder clso = new ComputeLinearScanOrder(lirBlocks.size(), startBlock); orderedBlocks = clso.linearScanOrder(); - this.compilation.stats.loopCount = clso.numLoops(); int z = 0; for (LIRBlock b : orderedBlocks) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ArrayLength.java Tue Jul 05 19:49:35 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ArrayLength.java Wed Jul 06 11:52:31 2011 +0200 @@ -95,8 +95,7 @@ @Override public Node copy(Graph into) { - ArrayLength x = new ArrayLength(null, into); - return x; + return new ArrayLength(null, into); } @SuppressWarnings("unchecked")
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java Tue Jul 05 19:49:35 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java Wed Jul 06 11:52:31 2011 +0200 @@ -30,7 +30,6 @@ import com.oracle.max.graal.compiler.lir.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.graph.*; -import com.sun.cri.ci.*; public final class ComputeLinearScanOrder { @@ -124,9 +123,11 @@ countEdges(startBlock, null); if (numLoops > 0) { - markLoops(); - clearNonNaturalLoops(startBlock); - assignLoopDepth(startBlock); + TTY.println("num loops " + numLoops); + throw new IllegalStateException(); +// markLoops(); +// clearNonNaturalLoops(startBlock); +// assignLoopDepth(startBlock); } computeOrder(startBlock); @@ -193,15 +194,15 @@ // innermost loop has the lowest number. This is guaranteed by setting // the loop number after the recursive calls for the successors above // have returned. - if (cur.isLinearScanLoopHeader()) { - assert cur.loopIndex() == -1 : "cannot set loop-index twice"; - if (GraalOptions.TraceLinearScanLevel >= 3) { - TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops); - } - - cur.setLoopIndex(numLoops); - numLoops++; - } +// if (cur.isLinearScanLoopHeader()) { +// assert cur.loopIndex() == -1 : "cannot set loop-index twice"; +// if (GraalOptions.TraceLinearScanLevel >= 3) { +// TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops); +// } +// +// cur.setLoopIndex(numLoops); +// numLoops++; +// } if (GraalOptions.TraceLinearScanLevel >= 3) { TTY.println("Finished counting edges for block B%d", cur.blockID()); @@ -329,10 +330,10 @@ // this is necessary for the (very rare) case that two successive blocks have // the same loop depth, but a different loop index (can happen for endless loops // with exception handlers) - if (!cur.isLinearScanLoopHeader()) { - weight |= 1 << curBit; - } - curBit--; +// if (!cur.isLinearScanLoopHeader()) { +// weight |= 1 << curBit; +// } +// curBit--; // loop end blocks (blocks that end with a backward branch) are added // after all other blocks of the loop. @@ -360,10 +361,10 @@ // curBit--; // exceptions handlers are added as late as possible -// if (!cur.isExceptionEntry()) { -// weight |= 1 << curBit; -// } -// curBit--; + if (!cur.isExceptionEntry()) { + weight |= 1 << curBit; + } + curBit--; // guarantee that weight is > 0 weight |= 1; @@ -434,29 +435,22 @@ linearScanOrder.add(cur); } - void computeOrder(LIRBlock startBlock) { + private void computeOrder(LIRBlock startBlock) { if (GraalOptions.TraceLinearScanLevel >= 3) { TTY.println("----- computing final block order"); } // the start block is always the first block in the linear scan order linearScanOrder = new ArrayList<LIRBlock>(numBlocks); -// appendBlock(startBlock); - - LIRBlock stdEntry = startBlock; //.suxAt(0); // start processing with standard entry block assert workList.isEmpty() : "list must be empty before processing"; - if (readyForProcessing(stdEntry)) { - sortIntoWorkList(stdEntry); - } else { - throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)"); - } + assert readyForProcessing(startBlock); + sortIntoWorkList(startBlock); do { LIRBlock cur = workList.remove(workList.size() - 1); - appendBlock(cur); int i;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java Tue Jul 05 19:49:35 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java Wed Jul 06 11:52:31 2011 +0200 @@ -27,6 +27,7 @@ import com.oracle.max.asm.*; import com.oracle.max.graal.compiler.alloc.*; import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; @@ -174,8 +175,7 @@ } public int loopDepth() { - // TODO(tw): Set correct loop depth. - return 0; + return loopDepth; } public int loopIndex() { @@ -284,4 +284,8 @@ LIROpcode code = lirInstruction.code; return code == LIROpcode.Branch || code == LIROpcode.TableSwitch; } + + public boolean isExceptionEntry() { + return firstInstruction() instanceof ExceptionObject; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jul 05 19:49:35 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Wed Jul 06 11:52:31 2011 +0200 @@ -116,9 +116,11 @@ * @param graph */ public GraphBuilderPhase(GraalCompilation compilation, RiMethod method, boolean inline) { - super(inline ? "BuildInlineGraph " + method.holder().name() + "." + method.name() + method.signature().asString() : "BuildGraph"); + super(inline ? "BuildInlineGraph" : "BuildGraph"); this.compilation = compilation; + setDetailedName(getName() + " " + method.holder().name() + "." + method.name() + method.signature().asString()); + this.runtime = compilation.runtime; this.method = method; this.stats = compilation.stats;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java Tue Jul 05 19:49:35 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java Wed Jul 06 11:52:31 2011 +0200 @@ -30,12 +30,14 @@ public abstract class Phase { private final String name; + private String detailedName; private static final ThreadLocal<Phase> currentPhase = new ThreadLocal<Phase>(); private final boolean shouldVerify; public Phase() { this.name = this.getClass().getSimpleName(); this.shouldVerify = true; + this.detailedName = name; } public Phase(String name) { @@ -45,6 +47,11 @@ public Phase(String name, boolean shouldVerify) { this.name = name; this.shouldVerify = shouldVerify; + this.detailedName = name; + } + + protected void setDetailedName(String detailedName) { + this.detailedName = detailedName; } public final void apply(Graph graph) { @@ -71,13 +78,13 @@ } catch (AssertionError t) { GraalCompilation compilation = GraalCompilation.compilation(); if (compilation.compiler.isObserved() && plotOnError) { - compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "AssertionError in " + getName(), graph, true, false, true)); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "AssertionError in " + detailedName, graph, true, false, true)); } throw t; } catch (RuntimeException t) { GraalCompilation compilation = GraalCompilation.compilation(); if (compilation.compiler.isObserved() && plotOnError) { - compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "RuntimeException in " + getName(), graph, true, false, true)); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "RuntimeException in " + detailedName, graph, true, false, true)); } throw t; } @@ -98,7 +105,7 @@ } GraalCompilation compilation = GraalCompilation.compilation(); if (compilation.compiler.isObserved() && this.getClass() != IdentifyBlocksPhase.class) { - compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After " + getName(), graph, true, false)); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After " + detailedName, graph, true, false)); } assert !shouldVerify || graph.verify();
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Tue Jul 05 19:49:35 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Wed Jul 06 11:52:31 2011 +0200 @@ -38,6 +38,8 @@ private Block javaBlock; private final List<Block> dominators = new ArrayList<Block>(); private Anchor anchor; + private int loopDepth = 0; + private int loopIndex = -1; private Node firstNode; private Node lastNode; @@ -63,6 +65,22 @@ return lastNode; } + public int loopDepth() { + return loopDepth; + } + + public void setLoopDepth(int i) { + loopDepth = i; + } + + public int loopIndex() { + return loopIndex; + } + + public void setLoopIndex(int i) { + loopIndex = i; + } + public Anchor createAnchor() { if (anchor == null) { if (firstNode instanceof Anchor) { @@ -175,6 +193,10 @@ return firstNode instanceof LoopBegin; } + public boolean isLoopEnd() { + return lastNode instanceof LoopEnd; + } + public Block dominator() { return dominator; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Tue Jul 05 19:49:35 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Wed Jul 06 11:52:31 2011 +0200 @@ -24,8 +24,6 @@ import java.util.*; -import javax.annotation.*; - import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.ir.*; @@ -39,6 +37,7 @@ private NodeMap<Block> nodeToBlock; private Graph graph; private boolean scheduleAllNodes; + private int loopCount; public IdentifyBlocksPhase(boolean scheduleAllNodes) { super(scheduleAllNodes ? "FullSchedule" : "PartSchedule", false); @@ -67,6 +66,10 @@ return b; } + public int loopCount() { + return loopCount; + } + private Block assignBlockNew(Node n, Block b) { if (b == null) { b = createBlock(); @@ -171,17 +174,7 @@ if (scheduleAllNodes) { - - // Add successors of loop end nodes. Makes the graph cyclic. - for (Block block : blocks) { - Node n = block.lastNode(); - if (n instanceof LoopEnd) { - LoopEnd loopEnd = (LoopEnd) n; - assert loopEnd.loopBegin() != null; - block.addSuccessor(nodeToBlock.get(loopEnd.loopBegin())); - } - } - + computeLoopInformation(); // Will make the graph cyclic. assignLatestPossibleBlockToNodes(); sortNodesWithinBlocks(); } else { @@ -189,6 +182,47 @@ } } + private void computeLoopInformation() { + + // Add successors of loop end nodes. Makes the graph cyclic. + for (Block block : blocks) { + Node n = block.lastNode(); + if (n instanceof LoopEnd) { + LoopEnd loopEnd = (LoopEnd) n; + assert loopEnd.loopBegin() != null; + Block loopBeginBlock = nodeToBlock.get(loopEnd.loopBegin()); + block.addSuccessor(loopBeginBlock); + BitMap map = new BitMap(blocks.size()); + markBlocks(block, loopBeginBlock, map, loopCount++, block.loopDepth()); + } + } + +// for (Block block : blocks) { +// TTY.println("Block B" + block.blockID() + " loopIndex=" + block.loopIndex() + ", loopDepth=" + block.loopDepth()); +// } + } + + private void markBlocks(Block block, Block endBlock, BitMap map, int loopIndex, int initialDepth) { + if (map.get(block.blockID())) { + return; + } + + map.set(block.blockID()); + if (block.loopDepth() <= initialDepth) { + assert block.loopDepth() == initialDepth; + block.setLoopIndex(loopIndex); + } + block.setLoopDepth(block.loopDepth() + 1); + + if (block == endBlock) { + return; + } + + for (Block pred : block.getPredecessors()) { + markBlocks(pred, endBlock, map, loopIndex, initialDepth); + } + } + private void computeJavaBlocks() { for (Block b : blocks) { @@ -300,12 +334,12 @@ } } - if (GraalOptions.OptOptimisticSchedule) { - block = scheduleOutOfLoops(n, block); - } - nodeToBlock.set(n, block); if (block != null) { + if (GraalOptions.OptOptimisticSchedule) { + block = scheduleOutOfLoops(n, block); + } + nodeToBlock.set(n, block); block.getInstructions().add(n); } return block; @@ -313,15 +347,24 @@ private Block scheduleOutOfLoops(Node n, Block latestBlock) { Block cur = latestBlock; - while (cur != null) { + 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); + // 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; }