Mercurial > hg > graal-compiler
changeset 2751:0fe79e7435c3
More scheduling. Removed need for cfg iteration in the phi simplifier.
line wrap: on
line diff
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Fri May 20 14:22:22 2011 +0200 @@ -27,6 +27,7 @@ public class Block { + private int blockID; private final List<Block> successors = new ArrayList<Block>(); private final List<Block> predecessors = new ArrayList<Block>(); @@ -38,8 +39,21 @@ return Collections.unmodifiableList(predecessors); } + public Block(int blockID) { + this.blockID = blockID; + } + public void addSuccessor(Block other) { successors.add(other); other.predecessors.add(this); } + + public int blockID() { + return blockID; + } + + @Override + public String toString() { + return "B" + blockID; + } }
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Fri May 20 14:22:22 2011 +0200 @@ -25,6 +25,8 @@ import java.util.*; import com.oracle.graal.graph.*; +import com.sun.c1x.debug.*; +import com.sun.c1x.ir.*; public class Schedule { @@ -38,12 +40,96 @@ identifyBlocks(); } + 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(); + nodeToBlock.set(n, curBlock); + } + return curBlock; + } + private void identifyBlocks() { - NodeIterator.doBFS(EdgeType.SUCCESSORS, graph.root(), new NodeVisitor() { + final NodeBitMap bottomUpBitMap = NodeIterator.iterate(EdgeType.PREDECESSORS, graph.end(), null); + NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), new NodeVisitor() { @Override public boolean visit(Node n) { + if (!bottomUpBitMap.isMarked(n)) { + return false; + } + + Node singlePred = null; + for (Node pred : n.predecessors()) { + if (pred != null && bottomUpBitMap.isMarked(pred)) { + if (singlePred == null) { + singlePred = pred; + } else { + // We have more than one predecessor => we are a merge block. + assignBlock(n); + return true; + } + } + } + + if (singlePred == null) { + // We have no predecessor => we are the start block. + assignBlock(n); + } else { + // We have a single predecessor => its successor count. + int successorCount = 0; + for (Node succ : singlePred.successors()) { + if (succ != null && bottomUpBitMap.isMarked(succ)) { + successorCount++; + if (successorCount > 1) { + // Our predecessor is a split => we need a new block. + assignBlock(n); + return true; + } + } + } + nodeToBlock.set(n, nodeToBlock.get(singlePred)); + } return true; + }} + ); + } + + private void print() { + TTY.println("============================================"); + TTY.println("%d blocks", blocks.size()); + for (Block b : blocks) { + 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 + ";"); + } + TTY.println(); + } + + + 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(); } - }); + } } }
--- a/graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java Fri May 20 14:22:22 2011 +0200 @@ -22,6 +22,7 @@ */ package com.sun.c1x.gen; +import com.oracle.graal.graph.*; import com.sun.c1x.graph.*; import com.sun.c1x.ir.*; import com.sun.c1x.value.*; @@ -37,7 +38,15 @@ public PhiSimplifier(IR ir) { this.ir = ir; - ir.getHIRStartBlock().iterateAnyOrder(this, false); + //ir.getHIRStartBlock().iterateAnyOrder(this, false); + + for (Node n : ir.compilation.graph.getNodes()) { + if (n instanceof Phi) { + simplify((Phi)n); + } + } + + } /**
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java Fri May 20 14:22:22 2011 +0200 @@ -180,7 +180,7 @@ BlockBegin startBlockBegin = new BlockBegin(0, startBlock.blockID, graph); startBlock.firstInstruction = startBlockBegin; - graph.root().setStart(startBlockBegin); + graph.start().setStart(startBlockBegin); RiExceptionHandler[] handlers = rootMethod.exceptionHandlers(); if (handlers != null && handlers.length > 0) {
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Fri May 20 14:22:22 2011 +0200 @@ -256,6 +256,6 @@ } public BlockBegin getHIRStartBlock() { - return (BlockBegin) compilation.graph.root().successors().get(0); + return (BlockBegin) compilation.graph.start().successors().get(0); } }
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java Fri May 20 14:22:22 2011 +0200 @@ -116,7 +116,7 @@ */ @SuppressWarnings({ "unchecked", "rawtypes" }) public List<Instruction> blockPredecessors() { - if (predecessors().size() == 1 && predecessors().get(0) == graph().root()) { + if (predecessors().size() == 1 && predecessors().get(0) == graph().start()) { return Collections.EMPTY_LIST; } else { return (List) Collections.unmodifiableList(predecessors()); @@ -145,65 +145,6 @@ } /** - * Iterate over all blocks transitively reachable from this block. - * @param closure the closure to apply to each block - * @param predecessors {@code true} if also to include this blocks predecessors - */ - public void iterateAnyOrder(BlockClosure closure, boolean predecessors) { - IdentityHashMap<BlockBegin, BlockBegin> mark = new IdentityHashMap<BlockBegin, BlockBegin>(); - LinkedList<BlockBegin> queue = new LinkedList<BlockBegin>(); - queue.offer(this); - mark.put(this, this); - BlockBegin block; - while ((block = queue.poll()) != null) { - closure.apply(block); - - Instruction inst = block; - ArrayList<BlockBegin> excBlocks = new ArrayList<BlockBegin>(); - while (inst != null) { - if (inst instanceof ExceptionEdgeInstruction) { - excBlocks.add(((ExceptionEdgeInstruction) inst).exceptionEdge()); - } - inst = inst.next(); - } - while (excBlocks.remove(null)) { - // nothing - } - if (excBlocks.size() > 0) { - queueBlocks(queue, excBlocks, mark); - } - - queueBlocks(queue, block.end().blockSuccessors(), mark); - if (predecessors) { - queueBlockEnds(queue, block.blockPredecessors(), mark); - } - } - } - - private void queueBlocks(LinkedList<BlockBegin> queue, List<BlockBegin> list, IdentityHashMap<BlockBegin, BlockBegin> mark) { - if (list != null) { - for (BlockBegin b : list) { - if (!mark.containsKey(b)) { - queue.offer(b); - mark.put(b, b); - } - } - } - } - - private void queueBlockEnds(LinkedList<BlockBegin> queue, List<Instruction> list, IdentityHashMap<BlockBegin, BlockBegin> mark) { - if (list != null) { - for (Instruction end : list) { - BlockBegin b = end.block(); - if (!mark.containsKey(b)) { - queue.offer(b); - mark.put(b, b); - } - } - } - } - - /** * Gets the bytecode index of this instruction. * @return the bytecode index of this instruction */ @@ -298,7 +239,7 @@ */ public int numberOfPreds() { // ignore the graph root - if (predecessors().size() == 1 && predecessors().get(0) == graph().root()) { + if (predecessors().size() == 1 && predecessors().get(0) == graph().start()) { return 0; } else { return predecessors().size();
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Return.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Return.java Fri May 20 14:22:22 2011 +0200 @@ -34,7 +34,8 @@ private static final int INPUT_COUNT = 1; private static final int INPUT_RESULT = 0; - private static final int SUCCESSOR_COUNT = 0; + private static final int SUCCESSOR_COUNT = 1; + private static final int SUCCESSOR_END = 0; @Override protected int inputCount() { @@ -57,6 +58,11 @@ return (Value) inputs().set(super.inputCount() + INPUT_RESULT, n); } + @Override + public Instruction next() { + return null; + } + /** * Constructs a new Return instruction. * @param result the instruction producing the result for this return; {@code null} if this @@ -67,6 +73,7 @@ public Return(Value result, Graph graph) { super(result == null ? CiKind.Void : result.kind, null, 0, INPUT_COUNT, SUCCESSOR_COUNT, graph); setResult(result); + successors().set(SUCCESSOR_END, graph.end()); } @Override
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Unwind.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Unwind.java Fri May 20 14:22:22 2011 +0200 @@ -34,7 +34,8 @@ private static final int INPUT_COUNT = 1; private static final int INPUT_EXCEPTION = 0; - private static final int SUCCESSOR_COUNT = 0; + private static final int SUCCESSOR_COUNT = 1; + private static final int SUCCESSOR_END = 0; @Override protected int inputCount() { @@ -46,6 +47,11 @@ return super.successorCount() + SUCCESSOR_COUNT; } + @Override + public Instruction next() { + return null; + } + /** * The instruction that produces the exception object. */ @@ -61,6 +67,7 @@ public Unwind(Value exception, Graph graph) { super(CiKind.Object, null, 0, INPUT_COUNT, SUCCESSOR_COUNT, graph); setException(exception); + successors().set(SUCCESSOR_END, graph.end()); } @Override
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java Fri May 20 14:22:22 2011 +0200 @@ -29,12 +29,14 @@ public class Graph { private final ArrayList<Node> nodes; - private final Root root; + private final StartNode start; + private final EndNode end; int nextId; public Graph() { nodes = new ArrayList<Node>(); - root = new Root(this); + start = new StartNode(this); + end = new EndNode(this); } public Collection<Node> getNodes() { @@ -51,8 +53,12 @@ nodes.set(node.id(), Node.Null); } - public Root root() { - return root; + public StartNode start() { + return start; + } + + public EndNode end() { + return end; } public NodeBitMap createNodeBitMap() {
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Node.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/Node.java Fri May 20 14:22:22 2011 +0200 @@ -27,7 +27,7 @@ import java.util.Collections; import java.util.List; -public abstract class Node implements Cloneable { +public abstract class Node { public static final Node Null = null; public static final int DeletedID = -1;
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java Fri May 20 14:22:22 2011 +0200 @@ -27,14 +27,14 @@ public class NodeIterator { - public static void doBFS(EdgeType e, Node start, NodeVisitor visitor) { + public static NodeBitMap iterate(EdgeType e, Node start, NodeVisitor visitor) { LinkedList<Node> nodes = new LinkedList<Node>(); NodeBitMap nodeBitMap = start.graph.createNodeBitMap(); add(nodes, nodeBitMap, start); while (nodes.size() > 0) { Node n = nodes.remove(); - if (visitor.visit(n)) { + if (visitor == null || visitor.visit(n)) { switch(e) { case INPUTS: for (Node inputs : n.inputs()) { @@ -61,6 +61,8 @@ } } } + + return nodeBitMap; } private static void add(List<Node> nodes, NodeBitMap nodeBitMap, Node node) {
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeMap.java Fri May 20 12:08:58 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeMap.java Fri May 20 14:22:22 2011 +0200 @@ -45,6 +45,10 @@ values[node.id()] = value; } + public int size() { + return values.length; + } + private void check(Node node) { assert node.graph == graph : "this node is not part of the graph"; assert node.id() < values.length : "this node was added to the graph after creating the node map";
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Root.java Fri May 20 12:08:58 2011 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,74 +0,0 @@ -/* - * Copyright (c) 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.graal.graph; - -public class Root extends Node { - - private static final int INPUT_COUNT = 0; - - private static final int SUCCESSOR_COUNT = 1; - private static final int SUCCESSOR_START = 0; - - @Override - protected int inputCount() { - return super.inputCount() + INPUT_COUNT; - } - - @Override - protected int successorCount() { - return super.successorCount() + SUCCESSOR_COUNT; - } - - public Node start() { - return (Node) successors().get(super.successorCount() + SUCCESSOR_START); - } - - public Node setStart(Node next) { - return successors().set(super.successorCount() + SUCCESSOR_START, next); - } - - Root(Graph graph) { - super(INPUT_COUNT, SUCCESSOR_COUNT, graph); - } - - @Override - public void replace(Node other) { - throw new UnsupportedOperationException(); - } - - @Override - public void delete() { - throw new UnsupportedOperationException(); - } - - @Override - protected Object clone() throws CloneNotSupportedException { - throw new UnsupportedOperationException(); - } - - @Override - public Node copy(Graph into) { - throw new UnsupportedOperationException(); - } - -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/StartNode.java Fri May 20 14:22:22 2011 +0200 @@ -0,0 +1,69 @@ +/* + * Copyright (c) 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.graal.graph; + +public class StartNode extends Node { + + private static final int INPUT_COUNT = 0; + + private static final int SUCCESSOR_COUNT = 1; + private static final int SUCCESSOR_START = 0; + + @Override + protected int inputCount() { + return super.inputCount() + INPUT_COUNT; + } + + @Override + protected int successorCount() { + return super.successorCount() + SUCCESSOR_COUNT; + } + + public Node start() { + return (Node) successors().get(super.successorCount() + SUCCESSOR_START); + } + + public Node setStart(Node next) { + return successors().set(super.successorCount() + SUCCESSOR_START, next); + } + + StartNode(Graph graph) { + super(INPUT_COUNT, SUCCESSOR_COUNT, graph); + } + + @Override + public void replace(Node other) { + throw new UnsupportedOperationException(); + } + + @Override + public void delete() { + throw new UnsupportedOperationException(); + } + + @Override + public Node copy(Graph into) { + throw new UnsupportedOperationException(); + } + +}