Mercurial > hg > truffle
changeset 2777:3e4d992fd312
towards replacing computelinearscanorder with scheduler.
| author | Thomas Wuerthinger <thomas@wuerthinger.net> |
|---|---|
| date | Tue, 24 May 2011 14:40:47 +0200 |
| parents | 398b8fa5dc81 |
| children | 2ac7b30b7290 |
| files | graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java graal/GraalCompiler/src/com/sun/c1x/graph/IR.java graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java graal/GraalGraph/src/com/oracle/graal/graph/NodeVisitor.java |
| diffstat | 6 files changed, 73 insertions(+), 27 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Tue May 24 13:55:56 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Tue May 24 14:40:47 2011 +0200 @@ -24,17 +24,24 @@ import java.util.*; +import com.sun.c1x.ir.*; + public class Block { private int blockID; private final List<Block> successors = new ArrayList<Block>(); private final List<Block> predecessors = new ArrayList<Block>(); + private final List<Instruction> instructions = new ArrayList<Instruction>(); public List<Block> getSuccessors() { return Collections.unmodifiableList(successors); } + public List<Instruction> getInstructions() { + return instructions; + } + public List<Block> getPredecessors() { return Collections.unmodifiableList(predecessors); }
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Tue May 24 13:55:56 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Tue May 24 14:40:47 2011 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.sun.c1x.debug.*; +import com.sun.c1x.ir.*; public class Schedule { @@ -57,32 +58,43 @@ Block curBlock = nodeToBlock.get(n); if (curBlock == null) { curBlock = createBlock(); - nodeToBlock.set(n, curBlock); + return assignBlock(n, curBlock); } return curBlock; } - private void identifyBlocks() { - // Identify nodes that form the control flow. - final NodeBitMap topDownBitMap = NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, null); - final NodeBitMap combinedBitMap = NodeIterator.iterate(EdgeType.PREDECESSORS, graph.end(), topDownBitMap, null); + private Block assignBlock(Node n, Block b) { + assert nodeToBlock.get(n) == null; + nodeToBlock.set(n, b); + b.getInstructions().add((Instruction) n); + return b; + } + private boolean isCFG(Node n) { + return n != null && (n instanceof Instruction); + } + + private void identifyBlocks() { // Identify blocks. final ArrayList<Node> blockBeginNodes = new ArrayList<Node>(); - NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), combinedBitMap, new NodeVisitor() { + NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start().successors().get(0), null, new NodeVisitor() { @Override - public void visit(Node n) { + public boolean visit(Node n) { + if (!isCFG(n)) { + return false; + } + Node singlePred = null; for (Node pred : n.predecessors()) { - if (pred != null && combinedBitMap.isMarked(pred)) { + if (isCFG(pred)) { if (singlePred == null) { singlePred = pred; } else { // We have more than one predecessor => we are a merge block. assignBlock(n); blockBeginNodes.add(n); - return; + return true; } } } @@ -95,18 +107,19 @@ // We have a single predecessor => check its successor count. int successorCount = 0; for (Node succ : singlePred.successors()) { - if (succ != null && combinedBitMap.isMarked(succ)) { + if (isCFG(succ)) { successorCount++; if (successorCount > 1) { // Our predecessor is a split => we need a new block. assignBlock(n); blockBeginNodes.add(n); - return; + return true; } } } - nodeToBlock.set(n, nodeToBlock.get(singlePred)); + assignBlock(n, nodeToBlock.get(singlePred)); } + return true; }} ); @@ -114,10 +127,14 @@ for (Node n : blockBeginNodes) { Block block = nodeToBlock.get(n); for (Node pred : n.predecessors()) { - Block predBlock = nodeToBlock.get(pred); - predBlock.addSuccessor(block); + if (isCFG(pred)) { + Block predBlock = nodeToBlock.get(pred); + predBlock.addSuccessor(block); + } } } + + //print(); } private void print() {
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Tue May 24 13:55:56 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Tue May 24 14:40:47 2011 +0200 @@ -80,12 +80,20 @@ C1XTimers.HIR_OPTIMIZE.start(); } + CriticalEdgeFinder finder = new CriticalEdgeFinder(this); + getHIRStartBlock().iteratePreOrder(finder); + finder.splitCriticalEdges(); + Schedule schedule = new Schedule(this.compilation.graph); List<Block> blocks = schedule.getBlocks(); NodeMap<Block> nodeToBlock = schedule.getNodeToBlock(); + /* orderedBlocks = new ArrayList<LIRBlock>(); Map<Block, LIRBlock> map = new HashMap<Block, LIRBlock>(); for (Block b : blocks) { - map.put(b, new LIRBlock(b.blockID())); + LIRBlock block = new LIRBlock(b.blockID()); + map.put(b, block); + block.setInstructions(b.getInstructions()); + orderedBlocks.add(block); } for (Block b : blocks) { @@ -96,12 +104,25 @@ for (Block pred : b.getPredecessors()) { map.get(b).blockPredecessors().add(map.get(pred)); } - } + }*/ + // TODO(tw): Schedule nodes within a block. - valueToBlock = computeLinearScanOrder(); + + + computeLinearScanOrder(); + + + valueToBlock = new HashMap<Value, LIRBlock>(); + for (LIRBlock b : orderedBlocks) { + for (Instruction i : b.getInstructions()) { + valueToBlock.put(i, b); + } + } + startBlock = valueToBlock.get(getHIRStartBlock()); + assert startBlock != null; verifyAndPrint("After linear scan order"); if (C1XOptions.PrintTimers) { @@ -125,12 +146,9 @@ private Map<Value, LIRBlock> makeLinearScanOrder() { - Map<Value, LIRBlock> valueToBlock = new HashMap<Value, LIRBlock>(); + if (orderedBlocks == null) { - if (orderedBlocks == null) { - CriticalEdgeFinder finder = new CriticalEdgeFinder(this); - getHIRStartBlock().iteratePreOrder(finder); - finder.splitCriticalEdges(); + Map<Value, LIRBlock> valueToBlock = new HashMap<Value, LIRBlock>(); ComputeLinearScanOrder computeLinearScanOrder = new ComputeLinearScanOrder(compilation.stats.blockCount, getHIRStartBlock()); List<BlockBegin> blocks = computeLinearScanOrder.linearScanOrder(); orderedBlocks = new ArrayList<LIRBlock>(); @@ -167,9 +185,6 @@ ++z; } - startBlock = valueToBlock.get(getHIRStartBlock()); - assert startBlock != null; - compilation.stats.loopCount = computeLinearScanOrder.numLoops(); } return valueToBlock; }
--- a/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java Tue May 24 13:55:56 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java Tue May 24 14:40:47 2011 +0200 @@ -219,4 +219,8 @@ successors.clear(); predecessors.clear(); } + + public void setInstructions(List<Instruction> list) { + instructions = list; + } }
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java Tue May 24 13:55:56 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java Tue May 24 14:40:47 2011 +0200 @@ -35,7 +35,10 @@ while (nodes.size() > 0) { Node n = nodes.remove(); if (visitor != null) { - visitor.visit(n); + boolean followEdges = visitor.visit(n); + if (!followEdges) { + continue; + } } switch(e) { case INPUTS: