Mercurial > hg > truffle
changeset 19658:165244576c9e
Merge.
| author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
|---|---|
| date | Mon, 02 Mar 2015 16:31:59 +0100 |
| parents | dcfdf9eb8570 (diff) 5b35e0c85d1b (current diff) |
| children | 84776a6314d7 |
| files | graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java |
| diffstat | 12 files changed, 207 insertions(+), 27 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java Mon Mar 02 16:31:59 2015 +0100 @@ -60,6 +60,7 @@ import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.schedule.*; +import com.oracle.graal.phases.schedule.SchedulePhase.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.phases.util.*; import com.oracle.graal.printer.*; @@ -302,7 +303,8 @@ } protected static String getCanonicalGraphString(StructuredGraph graph, boolean excludeVirtual, boolean checkConstants) { - SchedulePhase schedule = new SchedulePhase(); + SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.EARLIEST); + schedule.setScheduleConstants(true); schedule.apply(graph); NodeMap<Integer> canonicalId = graph.createNodeMap();
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LongNodeChainTest.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LongNodeChainTest.java Mon Mar 02 16:31:59 2015 +0100 @@ -28,6 +28,7 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.debug.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.schedule.*; @@ -36,9 +37,10 @@ public class LongNodeChainTest extends GraalCompilerTest { - public static final int N = 100000; + public static final int N = 10000; - @Ignore + private static final SchedulingStrategy[] Strategies = new SchedulingStrategy[]{SchedulingStrategy.EARLIEST}; + @Test public void testLongAddChain() { longAddChain(true); @@ -51,6 +53,9 @@ ValueNode constant = graph.unique(ConstantNode.forPrimitive(JavaConstant.INT_1)); ValueNode value = null; if (reverse) { + // Make sure the constant's stamp is not used to infer the add node's stamp. + OpaqueNode opaque = graph.unique(new OpaqueNode(constant)); + constant = opaque; AddNode addNode = graph.unique(new AddNode(constant, constant)); value = addNode; for (int i = 1; i < N; ++i) { @@ -58,6 +63,7 @@ addNode.setY(newAddNode); addNode = newAddNode; } + opaque.replaceAndDelete(opaque.getValue()); } else { value = constant; for (int i = 0; i < N; ++i) { @@ -67,7 +73,7 @@ ReturnNode returnNode = graph.add(new ReturnNode(value)); graph.start().setNext(returnNode); - for (SchedulingStrategy s : SchedulingStrategy.values()) { + for (SchedulingStrategy s : Strategies) { new SchedulePhase(s).apply(graph); }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Mon Mar 02 16:31:59 2015 +0100 @@ -32,6 +32,7 @@ private long[] bits; private int nodeCount; private final NodeIdAccessor nodeIdAccessor; + private int counter; public NodeBitMap(Graph graph) { nodeCount = graph.nodeIdCount(); @@ -43,6 +44,10 @@ return (nodeCount + Long.SIZE - 1) >> SHIFT; } + public int getCounter() { + return counter; + } + private NodeBitMap(NodeBitMap other) { this.bits = other.bits.clone(); this.nodeCount = other.nodeCount; @@ -63,6 +68,16 @@ return isMarked(id); } + public boolean checkAndMarkInc(Node node) { + if (!isMarked(node)) { + this.counter++; + this.mark(node); + return true; + } else { + return false; + } + } + public boolean isMarked(int id) { return (bits[id >> SHIFT] & (1L << id)) != 0; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Mon Mar 02 16:31:59 2015 +0100 @@ -39,4 +39,12 @@ } public abstract double probability(AbstractBeginNode successor); + + /** + * Primary successor of the control split. Data dependencies on the node have to be scheduled in + * the primary successor. + * + * @return the primary successor + */ + public abstract AbstractBeginNode getPrimarySuccessor(); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Mon Mar 02 16:31:59 2015 +0100 @@ -1128,4 +1128,9 @@ return null; } + + @Override + public AbstractBeginNode getPrimarySuccessor() { + return this.trueSuccessor(); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Mon Mar 02 16:31:59 2015 +0100 @@ -232,4 +232,9 @@ updateUsagesInterface(this.guard, guard); this.guard = guard; } + + @Override + public AbstractBeginNode getPrimarySuccessor() { + return this.next(); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Mon Mar 02 16:31:59 2015 +0100 @@ -78,6 +78,10 @@ return reversePostOrder.get(0); } + public Iterable<Block> reversePostOrder() { + return reversePostOrder; + } + public Iterable<Block> postOrder() { return new Iterable<Block>() {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/debug/OpaqueNode.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/debug/OpaqueNode.java Mon Mar 02 16:31:59 2015 +0100 @@ -32,13 +32,17 @@ public final class OpaqueNode extends FloatingNode implements LIRLowerable { public static final NodeClass<OpaqueNode> TYPE = NodeClass.create(OpaqueNode.class); - @Input ValueNode value; + @Input protected ValueNode value; public OpaqueNode(ValueNode value) { super(TYPE, value.stamp().unrestricted()); this.value = value; } + public ValueNode getValue() { + return value; + } + @Override public void generate(NodeLIRBuilderTool gen) { gen.setResult(this, gen.operand(value));
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Mon Mar 02 16:31:59 2015 +0100 @@ -159,4 +159,9 @@ } return successors.get(defaultSuccessorIndex()); } + + @Override + public AbstractBeginNode getPrimarySuccessor() { + return this.defaultSuccessor(); + } }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Mon Mar 02 16:31:59 2015 +0100 @@ -42,7 +42,6 @@ import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo; -import com.oracle.graal.phases.util.*; public final class SchedulePhase extends Phase { @@ -321,7 +320,7 @@ @Override protected void run(StructuredGraph graph) { - assert GraphOrder.assertNonCyclicGraph(graph); + // assert GraphOrder.assertNonCyclicGraph(graph); cfg = ControlFlowGraph.compute(graph, true, true, true, false); earliestCache = graph.createNodeMap(); blockToNodesMap = new BlockMap<>(cfg); @@ -330,6 +329,11 @@ blockToKillSet = new BlockMap<>(cfg); } + if (selectedStrategy == SchedulingStrategy.EARLIEST) { + scheduleEarliestIterative(blockToNodesMap, graph); + return; + } + assignBlockToNodes(graph, selectedStrategy); printSchedule("after assign nodes to blocks"); @@ -337,6 +341,139 @@ printSchedule("after sorting nodes within blocks"); } + private void scheduleEarliestIterative(BlockMap<List<ValueNode>> blockToNodes, StructuredGraph graph) { + NodeMap<Block> nodeToBlock = graph.createNodeMap(); + NodeBitMap visited = graph.createNodeBitMap(); + + // Add begin nodes as the first entry and set the block for phi nodes. + for (Block b : cfg.getBlocks()) { + AbstractBeginNode beginNode = b.getBeginNode(); + nodeToBlock.set(beginNode, b); + ArrayList<ValueNode> nodes = new ArrayList<>(); + nodes.add(beginNode); + blockToNodes.put(b, nodes); + + if (beginNode instanceof AbstractMergeNode) { + AbstractMergeNode mergeNode = (AbstractMergeNode) beginNode; + for (PhiNode phi : mergeNode.phis()) { + nodeToBlock.set(phi, b); + } + } + } + + Stack<Node> stack = new Stack<>(); + + // Start analysis with control flow ends. + for (Block b : cfg.postOrder()) { + FixedNode endNode = b.getEndNode(); + stack.push(endNode); + nodeToBlock.set(endNode, b); + } + + processStack(blockToNodes, nodeToBlock, visited, stack); + + // Visit back input edges of loop phis. + for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) { + for (PhiNode phi : loopBegin.phis()) { + if (visited.isMarked(phi)) { + for (int i = 0; i < loopBegin.getLoopEndCount(); ++i) { + Node node = phi.valueAt(i + loopBegin.forwardEndCount()); + if (!visited.isMarked(node)) { + stack.push(node); + processStack(blockToNodes, nodeToBlock, visited, stack); + } + } + } + } + } + + // Check for dead nodes. + if (visited.getCounter() < graph.getNodeCount()) { + for (Node n : graph.getNodes()) { + if (!visited.isMarked(n)) { + n.clearInputs(); + n.markDeleted(); + } + } + } + + // Add end nodes as the last nodes in each block. + for (Block b : cfg.getBlocks()) { + blockToNodes.get(b).add(b.getEndNode()); + } + + this.blockToNodesMap = blockToNodes; + } + + private void processStack(BlockMap<List<ValueNode>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, Stack<Node> stack) { + Block startBlock = cfg.getStartBlock(); + while (!stack.isEmpty()) { + Node current = stack.peek(); + if (visited.checkAndMarkInc(current)) { + + // Push inputs and predecessor. + Node predecessor = current.predecessor(); + if (predecessor != null) { + stack.push(predecessor); + } + + if (current instanceof PhiNode) { + PhiNode phiNode = (PhiNode) current; + AbstractMergeNode merge = phiNode.merge(); + for (int i = 0; i < merge.forwardEndCount(); ++i) { + Node input = phiNode.valueAt(i); + stack.push(input); + } + } else { + for (Node input : current.inputs()) { + if (current instanceof FrameState && input instanceof StateSplit && ((StateSplit) input).stateAfter() == current) { + // Ignore the cycle. + } else { + stack.push(input); + } + } + } + } else { + + stack.pop(); + + if (nodeToBlock.get(current) == null) { + Node predecessor = current.predecessor(); + if (nodeToBlock.get(current) == null) { + Block curBlock; + if (predecessor != null) { + // Predecessor determines block. + curBlock = nodeToBlock.get(predecessor); + } else { + Block earliest = startBlock; + for (Node input : current.inputs()) { + if (current instanceof FrameState && input instanceof StateSplit && ((StateSplit) input).stateAfter() == current) { + // ignore + } else { + Block inputEarliest; + if (input instanceof ControlSplitNode) { + inputEarliest = nodeToBlock.get(((ControlSplitNode) input).getPrimarySuccessor()); + } else { + inputEarliest = nodeToBlock.get(input); + } + assert inputEarliest != null : current + " / " + input; + if (earliest.getDominatorDepth() < inputEarliest.getDominatorDepth()) { + earliest = inputEarliest; + } + } + } + curBlock = earliest; + } + if (current instanceof ValueNode) { + blockToNodes.get(curBlock).add((ValueNode) current); + } + nodeToBlock.set(current, curBlock); + } + } + } + } + } + private Block blockForMemoryNode(MemoryNode memory) { MemoryNode current = memory; while (current instanceof MemoryProxy) { @@ -982,25 +1119,8 @@ List<ValueNode> sortedInstructions = state.getSortedInstructions(); Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1); if (lastSorted != b.getEndNode()) { - int idx = sortedInstructions.indexOf(b.getEndNode()); - boolean canNotMove = false; - for (int i = idx + 1; i < sortedInstructions.size(); i++) { - if (sortedInstructions.get(i).inputs().contains(b.getEndNode())) { - canNotMove = true; - break; - } - } - if (canNotMove) { - if (b.getEndNode() instanceof ControlSplitNode) { - throw new GraalGraphInternalError("Schedule is not possible : needs to move a node after the last node of the block which can not be move").addContext(lastSorted).addContext( - b.getEndNode()); - } - - // b.setLastNode(lastSorted); - } else { - sortedInstructions.remove(b.getEndNode()); - sortedInstructions.add(b.getEndNode()); - } + sortedInstructions.remove(b.getEndNode()); + sortedInstructions.add(b.getEndNode()); } return sortedInstructions; }
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/DefaultJavaLoweringProvider.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/DefaultJavaLoweringProvider.java Mon Mar 02 16:31:59 2015 +0100 @@ -259,6 +259,7 @@ memoryRead.setStateAfter(n.stateAfter()); ValueNode readValue = implicitLoadConvert(graph, valueKind, memoryRead); + n.stateAfter().replaceFirstInput(n, memoryRead); n.replaceAtUsages(readValue); graph.replaceFixedWithFixed(n, memoryRead); }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerExactArithmeticSplitNode.java Mon Mar 02 14:43:43 2015 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerExactArithmeticSplitNode.java Mon Mar 02 16:31:59 2015 +0100 @@ -34,8 +34,8 @@ public abstract class IntegerExactArithmeticSplitNode extends ControlSplitNode implements LIRLowerable { public static final NodeClass<IntegerExactArithmeticSplitNode> TYPE = NodeClass.create(IntegerExactArithmeticSplitNode.class); + @Successor AbstractBeginNode next; @Successor AbstractBeginNode overflowSuccessor; - @Successor AbstractBeginNode next; @Input ValueNode x; @Input ValueNode y; @@ -48,6 +48,11 @@ } @Override + public AbstractBeginNode getPrimarySuccessor() { + return next; + } + + @Override public double probability(AbstractBeginNode successor) { return successor == next ? 1 : 0; }