Mercurial > hg > truffle
changeset 2945:41318fcb6b56
Added two algorithms for identifying Java-level blocks.
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Thu Jun 09 17:34:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Thu Jun 09 18:59:28 2011 +0200 @@ -112,9 +112,9 @@ public void print(Graph graph, String title, boolean shortNames) { stream.printf(" <graph name='%s'>%n", escape(title)); noBlockNodes.clear(); - Schedule schedule = null; + IdentifyBlocksPhase schedule = null; try { - schedule = new Schedule(); + schedule = new IdentifyBlocksPhase(true); schedule.apply(graph); } catch (Throwable t) { // nothing to do here...
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Thu Jun 09 17:34:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Thu Jun 09 18:59:28 2011 +0200 @@ -91,9 +91,11 @@ new DeadCodeEliminationPhase().apply(compilation.graph); } + new LoweringPhase().apply(graph); + new SplitCriticalEdgesPhase().apply(graph); - Schedule schedule = new Schedule(); + IdentifyBlocksPhase schedule = new IdentifyBlocksPhase(true); schedule.apply(graph);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Thu Jun 09 17:34:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Thu Jun 09 18:59:28 2011 +0200 @@ -30,7 +30,7 @@ * The {@code Phi} instruction represents the merging of dataflow * in the instruction graph. It refers to a join block and a variable. */ -public final class Phi extends FixedNode { +public final class Phi extends FloatingNode { private static final int DEFAULT_MAX_VALUES = 2;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Thu Jun 09 17:34:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Thu Jun 09 18:59:28 2011 +0200 @@ -1262,7 +1262,7 @@ traceInstruction(bci, opcode, blockStart); processBytecode(bci, opcode); - if (Schedule.isBlockEnd(lastInstr) || lastInstr.next() != null) { + if (IdentifyBlocksPhase.isBlockEnd(lastInstr) || lastInstr.next() != null) { break; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java Thu Jun 09 17:34:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java Thu Jun 09 18:59:28 2011 +0200 @@ -25,6 +25,7 @@ import java.util.*; import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.schedule.*; import com.oracle.max.graal.graph.*; @@ -32,54 +33,100 @@ public class LoweringPhase extends Phase { @Override protected void run(Graph graph) { + IdentifyBlocksPhase s = new IdentifyBlocksPhase(false); + s.apply(graph); + +// for (Block b : s.getBlocks()) { +// TTY.println("Java block for block " + b.blockID() + " is " + b.javaBlock().blockID()); +// } + NodeMap<Node> javaBlockNodes = graph.createNodeMap(); + NodeMap<Node> dominators = graph.createNodeMap(); for (Node n : graph.getNodes()) { - if (n instanceof FixedNode) { - LoweringOp op = n.lookup(LoweringOp.class); - if (op != null) { - Node javaBlockNode = getJavaBlockNode(javaBlockNodes, n); - } + if (IdentifyBlocksPhase.isFixed(n)) { + //LoweringOp op = n.lookup(LoweringOp.class); + //if (op != null) { + Node javaBlockNode = getJavaBlockNode(javaBlockNodes, dominators, n); + + //TTY.println("Java block node for " + n.id() + " is " + ((javaBlockNode == null) ? "null" : javaBlockNode.id())); + //} } } } - private Node getJavaBlockNode(NodeMap<Node> javaBlockNodes, Node n) { - assert n instanceof FixedNode; + private Node getJavaBlockNode(NodeMap<Node> javaBlockNodes, NodeMap<Node> dominators, final Node n) { + assert IdentifyBlocksPhase.isFixed(n); + if (n == n.graph().start()) { + return null; + } + if (javaBlockNodes.get(n) == null) { Node truePred = null; int count = 0; for (Node pred : n.predecessors()) { - if (pred instanceof FixedNode) { + if (pred instanceof FixedNode || pred == n.graph().start()) { truePred = pred; count++; } } - assert count > 0; + assert count > 0 : n + "; " + IdentifyBlocksPhase.isFixed(n); if (count == 1) { - if (Schedule.trueSuccessorCount(truePred) == 1) { - javaBlockNodes.set(n, getJavaBlockNode(javaBlockNodes, truePred)); + if (IdentifyBlocksPhase.trueSuccessorCount(truePred) == 1) { + javaBlockNodes.set(n, getJavaBlockNode(javaBlockNodes, dominators, truePred)); } else { - // Single predecessor is a split => we are our own Java block node. - javaBlockNodes.set(n, n); + // Single predecessor is a split => this is our Java block node. + javaBlockNodes.set(n, truePred); } } else { Node dominator = null; for (Node pred : n.predecessors()) { - if (pred instanceof FixedNode) { - dominator = getCommonDominator(javaBlockNodes, dominator, pred); + if (IdentifyBlocksPhase.isFixed(pred)) { + dominator = getCommonDominator(javaBlockNodes, dominators, dominator, pred); } } + + final Node finalDominator = dominator; + final List<Node> visitedNodesList = new ArrayList<Node>(); + NodeBitMap visitedNodes = NodeIterator.iterate(EdgeType.PREDECESSORS, n, null, new NodeVisitor() { + @Override + public boolean visit(Node curNode) { + if((curNode instanceof FixedNode) || finalDominator != curNode) { + visitedNodesList.add(curNode); + return true; + } + return false; + } + }); + + visitedNodes.mark(finalDominator); + visitedNodesList.add(finalDominator); + + Node result = getJavaBlockNode(javaBlockNodes, dominators, finalDominator); + L1: for (Node curNode : visitedNodesList) { + if (curNode != n) { + for (Node succ : curNode.successors()) { + if (succ instanceof FixedNode && !visitedNodes.isMarked(succ)) { + result = n; + break L1; + } + } + } + } + + if (result != finalDominator) { + dominators.set(n, finalDominator); + } + javaBlockNodes.set(n, result); } } - assert Schedule.truePredecessorCount(javaBlockNodes.get(n)) == 1; return javaBlockNodes.get(n); } - private Node getCommonDominator(NodeMap<Node> javaBlockNodes, Node a, Node b) { + private Node getCommonDominator(NodeMap<Node> javaBlockNodes, NodeMap<Node> dominators, Node a, Node b) { if (a == null) { return b; } @@ -88,7 +135,30 @@ return a; } - Node cur = getJavaBlockNode(javaBlockNodes, a); + NodeBitMap visitedNodes = a.graph().createNodeBitMap(); + Node cur = a; + while (cur != null) { + visitedNodes.mark(cur); + cur = getDominator(javaBlockNodes, dominators, cur); + } + + cur = b; + while (cur != null) { + if (visitedNodes.isMarked(cur)) { + return cur; + } + cur = getDominator(javaBlockNodes, dominators, cur); + } + + throw new IllegalStateException("no common dominator between " + a + " and " + b); + } + + private Node getDominator(NodeMap<Node> javaBlockNodes, NodeMap<Node> dominators, Node cur) { + Node n = getJavaBlockNode(javaBlockNodes, dominators, cur); + if (dominators.get(cur) != null) { + return dominators.get(cur); + } + return n; } public interface LoweringOp extends Op {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/SplitCriticalEdgesPhase.java Thu Jun 09 17:34:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/SplitCriticalEdgesPhase.java Thu Jun 09 18:59:28 2011 +0200 @@ -36,10 +36,10 @@ List<Node> nodes = graph.getNodes(); for (int i = 0; i < nodes.size(); ++i) { Node n = nodes.get(i); - if (Schedule.trueSuccessorCount(n) > 1) { + if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) { for (int j = 0; j < n.successors().size(); ++j) { Node succ = n.successors().get(j); - if (Schedule.truePredecessorCount(succ) > 1) { + if (IdentifyBlocksPhase.truePredecessorCount(succ) > 1) { Anchor a = new Anchor(graph); a.successors().setAndClear(1, n, j); n.successors().set(j, a);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Thu Jun 09 17:34:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Thu Jun 09 18:59:28 2011 +0200 @@ -35,6 +35,7 @@ private final List<Block> predecessors = new ArrayList<Block>(); private List<Node> instructions = new ArrayList<Node>(); private Block dominator; + private Block javaBlock; private final List<Block> dominators = new ArrayList<Block>(); private Node firstNode; @@ -48,6 +49,14 @@ this.firstNode = node; } + public Block javaBlock() { + return javaBlock; + } + + public void setJavaBlock(Block javaBlock) { + this.javaBlock = javaBlock; + } + public Node lastNode() { return lastNode; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Thu Jun 09 18:59:28 2011 +0200 @@ -0,0 +1,530 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.compiler.schedule; + +import java.util.*; + +import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.phases.*; +import com.oracle.max.graal.compiler.value.*; +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; + + +public class IdentifyBlocksPhase extends Phase { + private final List<Block> blocks = new ArrayList<Block>(); + private NodeMap<Block> nodeToBlock; + private Graph graph; + private boolean scheduleAllNodes; + + public IdentifyBlocksPhase(boolean scheduleAllNodes) { + super(scheduleAllNodes ? "FullSchedule" : "PartSchedule"); + this.scheduleAllNodes = scheduleAllNodes; + } + + + @Override + protected void run(Graph graph) { + this.graph = graph; + nodeToBlock = graph.createNodeMap(); + identifyBlocks(); + } + + public List<Block> getBlocks() { + return Collections.unmodifiableList(blocks); + } + + public NodeMap<Block> getNodeToBlock() { + return nodeToBlock; + } + + private Block createBlock() { + Block b = new Block(blocks.size()); + blocks.add(b); + return b; + } + + private Block assignBlock(Node n) { + Block curBlock = nodeToBlock.get(n); + if (curBlock == null) { + curBlock = createBlock(); + return assignBlock(n, curBlock); + } + return curBlock; + } + + + private Block assignBlock(Node n, Block b) { + assert nodeToBlock.get(n) == null; + nodeToBlock.set(n, b); + if (b.firstNode() == null) { + b.setFirstNode(n); + b.setLastNode(n); + } else { + if (b.lastNode() != null) { + b.getInstructions().add(b.lastNode()); + } + b.setLastNode(n); + } + b.setLastNode(n); + return b; + } + + public static boolean isFixed(Node n) { + return n != null && ((n instanceof FixedNode) || n == n.graph().start()); + } + + public static boolean isBlockEnd(Node n) { + return trueSuccessorCount(n) > 1 || n instanceof Anchor || n instanceof Return || n instanceof Unwind; + } + + private void identifyBlocks() { + // Identify blocks. + final ArrayList<Node> blockBeginNodes = new ArrayList<Node>(); + NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, new NodeVisitor() { + @Override + public boolean visit(Node n) { + if (!isFixed(n)) { + return false; + } + + if (n instanceof LoopBegin) { + // a LoopBegin is always a merge + assignBlock(n); + blockBeginNodes.add(n); + return true; + } + + Node singlePred = null; + for (Node pred : n.predecessors()) { + if (isFixed(pred)) { + if (singlePred == null) { + singlePred = pred; + } else { + // We have more than one predecessor => we are a merge block. + assignBlock(n); + blockBeginNodes.add(n); + return true; + } + } + } + + if (singlePred == null) { + // We have no predecessor => we are the start block. + assignBlock(n); + blockBeginNodes.add(n); + } else { + // We have a single predecessor => check its successor count. + if (isBlockEnd(singlePred)) { + assignBlock(n); + blockBeginNodes.add(n); + } else { + assignBlock(n, nodeToBlock.get(singlePred)); + } + } + return true; + }} + ); + + // Connect blocks. + for (Node n : blockBeginNodes) { + Block block = nodeToBlock.get(n); + for (Node pred : n.predecessors()) { + if (isFixed(pred)) { + Block predBlock = nodeToBlock.get(pred); + predBlock.addSuccessor(block); + } + } + + if (n instanceof Merge) { + for (Node usage : n.usages()) { + if (usage instanceof Phi) { + nodeToBlock.set(usage, block); + } + } + } + } + + for (Node n : graph.getNodes()) { + if (n instanceof FrameState) { + FrameState f = (FrameState) n; + if (f.predecessors().size() == 1) { + Block predBlock = nodeToBlock.get(f.predecessors().get(0)); + assert predBlock != null; + nodeToBlock.set(f, predBlock); + predBlock.getInstructions().add(f); + } else { + assert f.predecessors().size() == 0; + } + } + } + + computeDominators(); + + + if (scheduleAllNodes) { + + // Add successors of loop end nodes. Makes the graph cyclic. + for (Node n : blockBeginNodes) { + Block block = nodeToBlock.get(n); + if (n instanceof LoopBegin) { + LoopBegin loopBegin = (LoopBegin) n; + nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block); + } + } + + assignLatestPossibleBlockToNodes(); + sortNodesWithinBlocks(); + } else { + computeJavaBlocks(); + } + + //print(); + } + + private void computeJavaBlocks() { + + for (Block b : blocks) { + computeJavaBlock(b); + } + } + + private Block computeJavaBlock(Block b) { + if (b.javaBlock() == null) { + if (b.getPredecessors().size() == 0) { + b.setJavaBlock(b); + } else if (b.getPredecessors().size() == 1) { + Block pred = b.getPredecessors().get(0); + if (pred.getSuccessors().size() > 1) { + b.setJavaBlock(b); + } else { + b.setJavaBlock(computeJavaBlock(pred)); + } + } else { + Block dominatorBlock = b.getPredecessors().get(0); + for (int i=1; i<b.getPredecessors().size(); ++i) { + dominatorBlock = getCommonDominator(dominatorBlock, b.getPredecessors().get(i)); + } + CiBitMap blockMap = new CiBitMap(blocks.size()); + markPredecessors(b, dominatorBlock, blockMap); + + Block result = dominatorBlock; + L1: for (Block curBlock : blocks) { + if (curBlock != b && blockMap.get(curBlock.blockID())) { + for (Block succ : curBlock.getSuccessors()) { + if (!blockMap.get(succ.blockID())) { + result = b; + break L1; + } + } + } + } + b.setJavaBlock(result); + } + } + return b.javaBlock(); + } + + private void markPredecessors(Block b, Block stopBlock, CiBitMap blockMap) { + if (blockMap.get(b.blockID())) { + return; + } + blockMap.set(b.blockID()); + if (b != stopBlock) { + for (Block pred : b.getPredecessors()) { + markPredecessors(pred, stopBlock, blockMap); + } + } + } + + private void assignLatestPossibleBlockToNodes() { + for (Node n : graph.getNodes()) { + assignLatestPossibleBlockToNode(n); + } + } + + private Block assignLatestPossibleBlockToNode(Node n) { + if (n == null) { + return null; + } + + Block prevBlock = nodeToBlock.get(n); + if (prevBlock != null) { + return prevBlock; + } + + Block block = null; + for (Node succ : n.successors()) { + block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ)); + } + for (Node usage : n.usages()) { + if (usage instanceof Phi) { + Phi phi = (Phi) usage; + Merge merge = phi.merge(); + Block mergeBlock = nodeToBlock.get(merge); + assert mergeBlock != null : "no block for merge " + merge.id(); + for (int i = 0; i < phi.valueCount(); ++i) { + if (phi.valueAt(i) == n) { + if (mergeBlock.getPredecessors().size() == 0) { + TTY.println(merge.toString()); + TTY.println(phi.toString()); + TTY.println(merge.predecessors().toString()); + TTY.println("value count: " + phi.valueCount()); + } + block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); + } + } + } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { + Merge merge = ((FrameState) usage).block(); + for (Node pred : merge.predecessors()) { + if (isFixed(pred)) { + block = getCommonDominator(block, nodeToBlock.get(pred)); + } + } + } else { + block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); + } + } + + nodeToBlock.set(n, block); + if (block != null) { + block.getInstructions().add(n); + } + return block; + } + + private Block getCommonDominator(Block a, Block b) { + if (a == null) { + return b; + } + if (b == null) { + return a; + } + return commonDominator(a, b); + } + + private void sortNodesWithinBlocks() { + NodeBitMap map = graph.createNodeBitMap(); + for (Block b : blocks) { + sortNodesWithinBlocks(b, map); + } + } + + private void sortNodesWithinBlocks(Block b, NodeBitMap map) { + List<Node> instructions = b.getInstructions(); + List<Node> sortedInstructions = new ArrayList<Node>(); + assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b; + + boolean scheduleFirst = true; + + if (b.firstNode() == b.lastNode()) { + Node node = b.firstNode(); + if (!(node instanceof Merge)) { + scheduleFirst = false; + } + } + if (scheduleFirst) { + addToSorting(b, b.firstNode(), sortedInstructions, map); + } + for (Node i : instructions) { + addToSorting(b, i, sortedInstructions, map); + } + addToSorting(b, b.lastNode(), sortedInstructions, map); + //assert b.firstNode() == sortedInstructions.get(0) : b.firstNode(); + // assert b.lastNode() == sortedInstructions.get(sortedInstructions.size() - 1); + b.setInstructions(sortedInstructions); +// TTY.println("Block " + b); +// for (Node n : sortedInstructions) { +// TTY.println("Node: " + n); +// } + } + + private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) { + if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof Local) { + return; + } + + for (Node input : i.inputs()) { + addToSorting(b, input, sortedInstructions, map); + } + + for (Node pred : i.predecessors()) { + addToSorting(b, pred, sortedInstructions, map); + } + + map.mark(i); + + for (Node succ : i.successors()) { + if (succ instanceof FrameState) { + addToSorting(b, succ, sortedInstructions, map); + } + } + + // Now predecessors and inputs are scheduled => we can add this node. + if (!(i instanceof FrameState)) { + sortedInstructions.add(i); + } + } + + 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(); + + 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; + } + } + + 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(); + } + + throw new IllegalStateException("no common dominator between " + a + " and " + b); + } + + private void print() { + TTY.println("============================================"); + TTY.println("%d blocks", blocks.size()); + + for (Block b : blocks) { + TTY.println(); + TTY.print(b.toString()); + + TTY.print(" succs="); + for (Block succ : b.getSuccessors()) { + TTY.print(succ + ";"); + } + + TTY.print(" preds="); + for (Block pred : b.getPredecessors()) { + TTY.print(pred + ";"); + } + + if (b.dominator() != null) { + TTY.print(" dom=" + b.dominator()); + } + TTY.println(); + + if (b.getInstructions().size() > 0) { + TTY.print("first instr: " + b.getInstructions().get(0)); + TTY.print("last instr: " + b.getInstructions().get(b.getInstructions().size() - 1)); + } + } + +/* + TTY.println("============================================"); + TTY.println("%d nodes", nodeToBlock.size()); + for (Node n : graph.getNodes()) { + if (n != null) { + TTY.print("Node %d: %s", n.id(), n.getClass().toString()); + Block curBlock = nodeToBlock.get(n); + if (curBlock != null) { + TTY.print(" %s", curBlock); + } + TTY.println(); + } + }*/ + } + + public static int trueSuccessorCount(Node n) { + if (n == null) { + return 0; + } + int i = 0; + for (Node s : n.successors()) { + if (isFixed(s)) { + i++; + } + } + return i; + } + + public static int truePredecessorCount(Node n) { + if (n == null) { + return 0; + } + int i = 0; + for (Node s : n.predecessors()) { + if (isFixed(s)) { + i++; + } + } + + if (n instanceof LoopBegin) { + i++; + } + return i; + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Schedule.java Thu Jun 09 17:34:10 2011 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,467 +0,0 @@ -/* - * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.max.graal.compiler.schedule; - -import java.util.*; - -import com.oracle.max.graal.compiler.debug.*; -import com.oracle.max.graal.compiler.ir.*; -import com.oracle.max.graal.compiler.phases.*; -import com.oracle.max.graal.compiler.value.*; -import com.oracle.max.graal.graph.*; -import com.sun.cri.ci.*; - - -public class Schedule extends Phase { - private final List<Block> blocks = new ArrayList<Block>(); - private NodeMap<Block> nodeToBlock; - private Graph graph; - - - @Override - protected void run(Graph graph) { - this.graph = graph; - nodeToBlock = graph.createNodeMap(); - identifyBlocks(); - } - - public List<Block> getBlocks() { - return Collections.unmodifiableList(blocks); - } - - public NodeMap<Block> getNodeToBlock() { - return nodeToBlock; - } - - private Block createBlock() { - Block b = new Block(blocks.size()); - blocks.add(b); - return b; - } - - private Block assignBlock(Node n) { - Block curBlock = nodeToBlock.get(n); - if (curBlock == null) { - curBlock = createBlock(); - return assignBlock(n, curBlock); - } - return curBlock; - } - - - private Block assignBlock(Node n, Block b) { - assert nodeToBlock.get(n) == null; - nodeToBlock.set(n, b); - if (b.firstNode() == null) { - b.setFirstNode(n); - b.setLastNode(n); - } else { - if (b.lastNode() != null) { - b.getInstructions().add(b.lastNode()); - } - b.setLastNode(n); - } - b.setLastNode(n); - return b; - } - - public static boolean isFixed(Node n) { - return n != null && ((n instanceof FixedNode) || n == n.graph().start()); - } - - public static boolean isBlockEnd(Node n) { - return trueSuccessorCount(n) > 1 || n instanceof Anchor || n instanceof Return || n instanceof Unwind; - } - - private void identifyBlocks() { - // Identify blocks. - final ArrayList<Node> blockBeginNodes = new ArrayList<Node>(); - NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, new NodeVisitor() { - @Override - public boolean visit(Node n) { - if (!isFixed(n)) { - return false; - } - - if (n instanceof LoopBegin) { - // a LoopBegin is always a merge - assignBlock(n); - blockBeginNodes.add(n); - return true; - } - - Node singlePred = null; - for (Node pred : n.predecessors()) { - if (isFixed(pred)) { - if (singlePred == null) { - singlePred = pred; - } else { - // We have more than one predecessor => we are a merge block. - assignBlock(n); - blockBeginNodes.add(n); - return true; - } - } - } - - if (singlePred == null) { - // We have no predecessor => we are the start block. - assignBlock(n); - blockBeginNodes.add(n); - } else { - // We have a single predecessor => check its successor count. - if (isBlockEnd(singlePred)) { - assignBlock(n); - blockBeginNodes.add(n); - } else { - assignBlock(n, nodeToBlock.get(singlePred)); - } - } - return true; - }} - ); - - // Connect blocks. - for (Node n : blockBeginNodes) { - Block block = nodeToBlock.get(n); - for (Node pred : n.predecessors()) { - if (isFixed(pred)) { - Block predBlock = nodeToBlock.get(pred); - predBlock.addSuccessor(block); - } - } - - if (n instanceof Merge) { - for (Node usage : n.usages()) { - if (usage instanceof Phi) { - nodeToBlock.set(usage, block); - } - } - } - } - - for (Node n : graph.getNodes()) { - if (n instanceof FrameState) { - FrameState f = (FrameState) n; - if (f.predecessors().size() == 1) { - Block predBlock = nodeToBlock.get(f.predecessors().get(0)); - assert predBlock != null; - nodeToBlock.set(f, predBlock); - predBlock.getInstructions().add(f); - } else { - assert f.predecessors().size() == 0; - } - } - } - - computeDominators(); - - - - // Add successors of loop end nodes. Makes the graph cyclic. - for (Node n : blockBeginNodes) { - Block block = nodeToBlock.get(n); - if (n instanceof LoopBegin) { - LoopBegin loopBegin = (LoopBegin) n; - nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block); - } - } - - assignLatestPossibleBlockToNodes(); - sortNodesWithinBlocks(); - - //print(); - } - - private void assignLatestPossibleBlockToNodes() { - for (Node n : graph.getNodes()) { - assignLatestPossibleBlockToNode(n); - } - } - - private Block assignLatestPossibleBlockToNode(Node n) { - if (n == null) { - return null; - } - - Block prevBlock = nodeToBlock.get(n); - if (prevBlock != null) { - return prevBlock; - } - - Block block = null; - for (Node succ : n.successors()) { - block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ)); - } - for (Node usage : n.usages()) { - if (usage instanceof Phi) { - Phi phi = (Phi) usage; - Merge merge = phi.merge(); - Block mergeBlock = nodeToBlock.get(merge); - assert mergeBlock != null : "no block for merge " + merge.id(); - for (int i = 0; i < phi.valueCount(); ++i) { - if (phi.valueAt(i) == n) { - if (mergeBlock.getPredecessors().size() == 0) { - TTY.println(merge.toString()); - TTY.println(phi.toString()); - TTY.println(merge.predecessors().toString()); - TTY.println("value count: " + phi.valueCount()); - } - block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); - } - } - } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { - Merge merge = ((FrameState) usage).block(); - for (Node pred : merge.predecessors()) { - if (isFixed(pred)) { - block = getCommonDominator(block, nodeToBlock.get(pred)); - } - } - } else { - block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); - } - } - - nodeToBlock.set(n, block); - if (block != null) { - block.getInstructions().add(n); - } - return block; - } - - private Block getCommonDominator(Block a, Block b) { - if (a == null) { - return b; - } - if (b == null) { - return a; - } - return commonDominator(a, b); - } - - private void sortNodesWithinBlocks() { - NodeBitMap map = graph.createNodeBitMap(); - for (Block b : blocks) { - sortNodesWithinBlocks(b, map); - } - } - - private void sortNodesWithinBlocks(Block b, NodeBitMap map) { - List<Node> instructions = b.getInstructions(); - List<Node> sortedInstructions = new ArrayList<Node>(); - assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b; - - boolean scheduleFirst = true; - - if (b.firstNode() == b.lastNode()) { - Node node = b.firstNode(); - if (!(node instanceof Merge)) { - scheduleFirst = false; - } - } - if (scheduleFirst) { - addToSorting(b, b.firstNode(), sortedInstructions, map); - } - for (Node i : instructions) { - addToSorting(b, i, sortedInstructions, map); - } - addToSorting(b, b.lastNode(), sortedInstructions, map); - //assert b.firstNode() == sortedInstructions.get(0) : b.firstNode(); - // assert b.lastNode() == sortedInstructions.get(sortedInstructions.size() - 1); - b.setInstructions(sortedInstructions); -// TTY.println("Block " + b); -// for (Node n : sortedInstructions) { -// TTY.println("Node: " + n); -// } - } - - private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) { - if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof Local) { - return; - } - - for (Node input : i.inputs()) { - addToSorting(b, input, sortedInstructions, map); - } - - for (Node pred : i.predecessors()) { - addToSorting(b, pred, sortedInstructions, map); - } - - map.mark(i); - - for (Node succ : i.successors()) { - if (succ instanceof FrameState) { - addToSorting(b, succ, sortedInstructions, map); - } - } - - // Now predecessors and inputs are scheduled => we can add this node. - if (!(i instanceof FrameState)) { - sortedInstructions.add(i); - } - } - - 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(); - - 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; - } - } - - 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() { - TTY.println("============================================"); - TTY.println("%d blocks", blocks.size()); - - for (Block b : blocks) { - TTY.println(); - TTY.print(b.toString()); - - TTY.print(" succs="); - for (Block succ : b.getSuccessors()) { - TTY.print(succ + ";"); - } - - TTY.print(" preds="); - for (Block pred : b.getPredecessors()) { - TTY.print(pred + ";"); - } - - if (b.dominator() != null) { - TTY.print(" dom=" + b.dominator()); - } - TTY.println(); - - if (b.getInstructions().size() > 0) { - TTY.print("first instr: " + b.getInstructions().get(0)); - TTY.print("last instr: " + b.getInstructions().get(b.getInstructions().size() - 1)); - } - } - -/* - TTY.println("============================================"); - TTY.println("%d nodes", nodeToBlock.size()); - for (Node n : graph.getNodes()) { - if (n != null) { - TTY.print("Node %d: %s", n.id(), n.getClass().toString()); - Block curBlock = nodeToBlock.get(n); - if (curBlock != null) { - TTY.print(" %s", curBlock); - } - TTY.println(); - } - }*/ - } - - public static int trueSuccessorCount(Node n) { - if (n == null) { - return 0; - } - int i = 0; - for (Node s : n.successors()) { - if (isFixed(s)) { - i++; - } - } - return i; - } - - public static int truePredecessorCount(Node n) { - if (n == null) { - return 0; - } - int i = 0; - for (Node s : n.predecessors()) { - if (isFixed(s)) { - i++; - } - } - - if (n instanceof LoopBegin) { - i++; - } - return i; - } -}
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMExitsNative.java Thu Jun 09 17:34:10 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMExitsNative.java Thu Jun 09 18:59:28 2011 +0200 @@ -77,7 +77,6 @@ public void startCompiler() { originalOut = System.out; originalErr = System.err; - TTY.println("startCompiler: " + originalOut); } public void shutdownCompiler() throws Throwable {