Mercurial > hg > graal-compiler
changeset 2800:e3a0630a1dab
added code for computing dominators.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Fri, 27 May 2011 14:58:55 +0200 |
parents | 58e65eb6bb5d |
children | 2af109bec0c0 |
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/ir/Merge.java |
diffstat | 3 files changed, 124 insertions(+), 19 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Fri May 27 14:20:30 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Fri May 27 14:58:55 2011 +0200 @@ -32,13 +32,26 @@ 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>(); + private List<Instruction> instructions = new ArrayList<Instruction>(); private boolean exceptionEntry; + private Block dominator; + private final List<Block> dominators = new ArrayList<Block>(); public List<Block> getSuccessors() { return Collections.unmodifiableList(successors); } + public void setDominator(Block dominator) { + assert this.dominator == null; + assert dominator != null; + this.dominator = dominator; + dominator.dominators.add(this); + } + + public List<Block> getDominators() { + return Collections.unmodifiableList(dominators); + } + public List<Instruction> getInstructions() { return instructions; } @@ -97,4 +110,12 @@ public String toString() { return "B" + blockID; } + + public Block dominator() { + return dominator; + } + + public void setInstructions(List<Instruction> instructions) { + this.instructions = instructions; + } }
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Fri May 27 14:20:30 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Fri May 27 14:58:55 2011 +0200 @@ -27,6 +27,8 @@ import com.oracle.graal.graph.*; import com.sun.c1x.debug.*; import com.sun.c1x.ir.*; +import com.sun.cri.ci.*; +import com.sun.jmx.remote.util.*; public class Schedule { @@ -149,20 +151,94 @@ } } - orderBlocks(); + //computeDominators(); + //sortNodesWithinBlocks(); //print(); } - private void orderBlocks() { - /* List<Block> orderedBlocks = new ArrayList<Block>(); - Block startBlock = nodeToBlock.get(graph.start().start()); - List<Block> toSchedule = new ArrayList<Block>(); - toSchedule.add(startBlock); + private void sortNodesWithinBlocks() { + for (Block b : blocks) { + sortNodesWithinBlocks(b); + } + } + + private void sortNodesWithinBlocks(Block b) { + List<Instruction> instructions = b.getInstructions(); + Collections.shuffle(instructions); + + List<Instruction> sortedInstructions = new ArrayList<Instruction>(); + sortedInstructions.addAll(instructions); + b.setInstructions(sortedInstructions); + } + + private void computeDominators() { + Block dominatorRoot = nodeToBlock.get(graph.start()); + assert dominatorRoot.getPredecessors().size() == 0; + CiBitMap visited = new CiBitMap(blocks.size()); + visited.set(dominatorRoot.blockID()); + LinkedList<Block> workList = new LinkedList<Block>(); + workList.add(dominatorRoot); + + while (!workList.isEmpty()) { + Block b = workList.remove(); + + TTY.println("processing" + b); + List<Block> predecessors = b.getPredecessors(); + if (predecessors.size() == 1) { + b.setDominator(predecessors.get(0)); + } else if (predecessors.size() > 0) { + boolean delay = false; + for (Block pred : predecessors) { + if (pred != dominatorRoot && pred.dominator() == null) { + delay = true; + break; + } + } - while (toSchedule.size() != 0) { + if (delay) { + workList.add(b); + continue; + } + + Block dominator = null; + for (Block pred : predecessors) { + if (dominator == null) { + dominator = pred; + } else { + dominator = commonDominator(dominator, pred); + } + } + b.setDominator(dominator); + } + for (Block succ : b.getSuccessors()) { + if (!visited.get(succ.blockID())) { + visited.set(succ.blockID()); + workList.add(succ); + } + } + } + } - }*/ + public Block commonDominator(Block a, Block b) { + CiBitMap bitMap = new CiBitMap(blocks.size()); + Block cur = a; + while (cur != null) { + bitMap.set(cur.blockID()); + cur = cur.dominator(); + } + + cur = b; + while (cur != null) { + if (bitMap.get(cur.blockID())) { + return cur; + } + cur = cur.dominator(); + } + + print(); + assert false : "no common dominator between " + a + " and " + b; + return null; } private void print() { @@ -185,6 +261,10 @@ for (Block pred : b.getPredecessors()) { TTY.print(pred + ";"); } + + if (b.dominator() != null) { + TTY.print(" dom=" + b.dominator()); + } TTY.println(); if (b.getInstructions().size() > 0) {
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java Fri May 27 14:20:30 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java Fri May 27 14:58:55 2011 +0200 @@ -95,18 +95,22 @@ builder.append(" ["); builder.append("]"); - //if (end() != null) { - builder.append(" -> "); - boolean hasSucc = false; - for (Node s : this.successors()) { - if (hasSucc) { - builder.append(", "); - } - builder.append("#"); + + builder.append(" -> "); + boolean hasSucc = false; + for (Node s : this.successors()) { + if (hasSucc) { + builder.append(", "); + } + builder.append("#"); + if (s != null) { builder.append(s.id()); - hasSucc = true; + } else { + builder.append("null"); } - //} + hasSucc = true; + } + return builder.toString(); }