Mercurial > hg > truffle
changeset 19828:79682c7f2ec7
Merge.
| author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
|---|---|
| date | Fri, 13 Mar 2015 12:27:07 +0100 |
| parents | 5d624638e8a5 (diff) e87d55dfbbbb (current diff) |
| children | 79d5fbcc6978 |
| files | graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/TruffleEventListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/impl/DefaultEventListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/impl/SimpleEventListener.java |
| diffstat | 28 files changed, 877 insertions(+), 1044 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/LocationIdentity.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/LocationIdentity.java Fri Mar 13 12:27:07 2015 +0100 @@ -59,4 +59,8 @@ default boolean isImmutable() { return false; } + + default boolean isMutable() { + return !isImmutable(); + } }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Fri Mar 13 12:27:07 2015 +0100 @@ -89,6 +89,14 @@ } /** + * True if block {@code a} dominates block {@code b} and {@code a} is not identical block to + * {@code b}. + */ + static boolean strictlyDominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { + return a != b && dominates(a, b); + } + + /** * True if block {@code a} dominates block {@code b}. */ static boolean dominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java Fri Mar 13 12:27:07 2015 +0100 @@ -305,7 +305,6 @@ protected static String getCanonicalGraphString(StructuredGraph graph, boolean excludeVirtual, boolean checkConstants) { SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.EARLIEST); - schedule.setScheduleConstants(true); schedule.apply(graph); NodeMap<Integer> canonicalId = graph.createNodeMap(); @@ -325,7 +324,7 @@ } result.append("\n"); for (Node node : schedule.getBlockToNodesMap().get(block)) { - if (node.isAlive()) { + if (node instanceof ValueNode && node.isAlive()) { if (!excludeVirtual || !(node instanceof VirtualObjectNode || node instanceof ProxyNode)) { if (node instanceof ConstantNode) { String name = checkConstants ? node.toString(Verbosity.Name) : node.getClass().getSimpleName();
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java Fri Mar 13 12:27:07 2015 +0100 @@ -45,7 +45,7 @@ Block aBlock = nodeToBlock.get(a); if (bBlock == aBlock) { - List<ValueNode> instructions = ibp.nodesFor(bBlock); + List<Node> instructions = ibp.nodesFor(bBlock); Assert.assertTrue(instructions.indexOf(b) > instructions.indexOf(a)); } else { Block block = bBlock;
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java Fri Mar 13 12:27:07 2015 +0100 @@ -23,10 +23,12 @@ package com.oracle.graal.compiler.test; import static com.oracle.graal.compiler.common.GraalOptions.*; + import java.util.*; import org.junit.*; +import com.oracle.graal.api.directives.*; import com.oracle.graal.debug.*; import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.graph.*; @@ -251,6 +253,62 @@ } /** + * Here the read should not float out of the loop. + */ + public static int testLoop6Snippet(int a, int b, MemoryScheduleTest obj) { + int ret = 0; + int bb = b; + for (int i = 0; i < a; i++) { + ret = obj.hash; + if (a > 10) { + bb++; + } else { + bb--; + for (int j = 0; j < b; ++j) { + obj.hash = 3; + } + } + ret = ret / 10; + } + return ret + bb; + } + + @Test + public void testLoop6() { + SchedulePhase schedule = getFinalSchedule("testLoop6Snippet", TestMode.WITHOUT_FRAMESTATES); + assertDeepEquals(13, schedule.getCFG().getBlocks().size()); + assertReadWithinStartBlock(schedule, false); + assertReadWithinAllReturnBlocks(schedule, false); + } + + /** + * Here the read should not float to the end. + */ + public static int testLoop7Snippet(int a, int b) { + int result = container.a; + for (int i = 0; i < a; i++) { + if (b < 0) { + container.b = 10; + break; + } else { + for (int j = 0; j < b; j++) { + container.a = 0; + } + } + } + GraalDirectives.controlFlowAnchor(); + return result; + } + + @Test + public void testLoop7() { + SchedulePhase schedule = getFinalSchedule("testLoop7Snippet", TestMode.WITHOUT_FRAMESTATES); + assertDeepEquals(10, schedule.getCFG().getBlocks().size()); + assertReadWithinStartBlock(schedule, true); + assertReadWithinAllReturnBlocks(schedule, false); + } + + /** * Here the read should float to the end (into the same block as the return). */ public static int testArrayCopySnippet(Integer intValue, char[] a, char[] b, int len) {
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SchedulingTest.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SchedulingTest.java Fri Mar 13 12:27:07 2015 +0100 @@ -60,10 +60,10 @@ NodeMap<Block> nodeToBlock = schedule.getCFG().getNodeToBlock(); assertTrue(graph.getNodes().filter(LoopExitNode.class).count() == 1); LoopExitNode loopExit = graph.getNodes().filter(LoopExitNode.class).first(); - List<ValueNode> list = schedule.nodesFor(nodeToBlock.get(loopExit)); + List<Node> list = schedule.nodesFor(nodeToBlock.get(loopExit)); for (BinaryArithmeticNode<?> node : graph.getNodes().filter(BinaryArithmeticNode.class)) { if (!(node instanceof AddNode)) { - assertTrue(nodeToBlock.get(node) == nodeToBlock.get(loopExit)); + assertTrue(node.toString(), nodeToBlock.get(node) == nodeToBlock.get(loopExit)); assertTrue(list.indexOf(node) + " < " + list.indexOf(loopExit) + ", " + node + ", " + loopExit, list.indexOf(node) < list.indexOf(loopExit)); } }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Fri Mar 13 12:27:07 2015 +0100 @@ -269,7 +269,6 @@ graph.maybeCompress(); SchedulePhase schedule = new SchedulePhase(); - schedule.setScheduleConstants(true); schedule.apply(graph); Debug.dump(schedule, "Final HIR schedule"); return schedule; @@ -284,7 +283,6 @@ // Repeatedly run the LIR code generation pass to improve statistical profiling results. for (int i = 0; i < EmitLIRRepeatCount.getValue(); i++) { SchedulePhase dummySchedule = new SchedulePhase(); - dummySchedule.setScheduleConstants(true); dummySchedule.apply(graph); emitLIR(backend, target, dummySchedule, graph, stub, cc, registerConfig, lirSuites); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java Fri Mar 13 12:27:07 2015 +0100 @@ -26,6 +26,7 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.graph.*; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.phases.*; import com.oracle.graal.nodes.*; @@ -61,7 +62,7 @@ context.lirGen.beforeRegisterAllocation(); } - private static void emitBlock(NodeLIRBuilderTool nodeLirGen, LIRGenerationResult lirGenRes, Block b, StructuredGraph graph, BlockMap<List<ValueNode>> blockMap) { + private static void emitBlock(NodeLIRBuilderTool nodeLirGen, LIRGenerationResult lirGenRes, Block b, StructuredGraph graph, BlockMap<List<Node>> blockMap) { if (lirGenRes.getLIR().getLIRforBlock(b) == null) { for (Block pred : b.getPredecessors()) { if (!b.isLoopHeader() || !pred.isLoopEnd()) {
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/NodeLIRBuilder.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/NodeLIRBuilder.java Fri Mar 13 12:27:07 2015 +0100 @@ -92,7 +92,7 @@ private ValueNode currentInstruction; private ValueNode lastInstructionPrinted; // Debugging only - private Map<Class<? extends ValueNode>, List<MatchStatement>> matchRules; + private Map<Class<? extends Node>, List<MatchStatement>> matchRules; public NodeLIRBuilder(StructuredGraph graph, LIRGeneratorTool gen) { this.gen = gen; @@ -116,18 +116,18 @@ * @param node A node that produces a result value. */ @Override - public Value operand(ValueNode node) { + public Value operand(Node node) { Value operand = getOperand(node); assert operand != null : String.format("missing operand for %1s", node); return operand; } @Override - public boolean hasOperand(ValueNode node) { + public boolean hasOperand(Node node) { return getOperand(node) != null; } - private Value getOperand(ValueNode node) { + private Value getOperand(Node node) { if (nodeOperands == null) { return null; } @@ -162,7 +162,7 @@ * Used by the {@link MatchStatement} machinery to override the generation LIR for some * ValueNodes. */ - public void setMatchResult(ValueNode x, Value operand) { + public void setMatchResult(Node x, Value operand) { assert operand.equals(ComplexMatchValue.INTERIOR_MATCH) || operand instanceof ComplexMatchValue; assert operand instanceof ComplexMatchValue || x.getUsageCount() == 1 : "interior matches must be single user"; assert nodeOperands != null && nodeOperands.get(x) == null : "operand cannot be set twice"; @@ -191,7 +191,7 @@ gen.append(op); } - public void doBlock(Block block, StructuredGraph graph, BlockMap<List<ValueNode>> blockMap) { + public void doBlock(Block block, StructuredGraph graph, BlockMap<List<Node>> blockMap) { gen.doBlockStart(block); if (block == gen.getResult().getLIR().getControlFlowGraph().getStartBlock()) { @@ -201,41 +201,44 @@ assert block.getPredecessorCount() > 0; } - List<ValueNode> nodes = blockMap.get(block); + List<Node> nodes = blockMap.get(block); // Allow NodeLIRBuilder subclass to specialize code generation of any interesting groups // of instructions matchComplexExpressions(nodes); for (int i = 0; i < nodes.size(); i++) { - ValueNode valueNode = nodes.get(i); - if (Options.TraceLIRGeneratorLevel.getValue() >= 3) { - TTY.println("LIRGen for " + valueNode); - } - Value operand = getOperand(valueNode); - if (operand == null) { - if (!peephole(valueNode)) { - try { - doRoot(valueNode); - } catch (GraalInternalError e) { - throw GraalGraphInternalError.transformAndAddContext(e, valueNode); - } catch (Throwable e) { - throw new GraalGraphInternalError(e).addContext(valueNode); + Node node = nodes.get(i); + if (node instanceof ValueNode) { + ValueNode valueNode = (ValueNode) node; + if (Options.TraceLIRGeneratorLevel.getValue() >= 3) { + TTY.println("LIRGen for " + valueNode); + } + Value operand = getOperand(valueNode); + if (operand == null) { + if (!peephole(valueNode)) { + try { + doRoot(valueNode); + } catch (GraalInternalError e) { + throw GraalGraphInternalError.transformAndAddContext(e, valueNode); + } catch (Throwable e) { + throw new GraalGraphInternalError(e).addContext(valueNode); + } } + } else if (ComplexMatchValue.INTERIOR_MATCH.equals(operand)) { + // Doesn't need to be evaluated + Debug.log("interior match for %s", valueNode); + } else if (operand instanceof ComplexMatchValue) { + Debug.log("complex match for %s", valueNode); + ComplexMatchValue match = (ComplexMatchValue) operand; + operand = match.evaluate(this); + if (operand != null) { + setResult(valueNode, operand); + } + } else { + // There can be cases in which the result of an instruction is already set + // before by other instructions. } - } else if (ComplexMatchValue.INTERIOR_MATCH.equals(operand)) { - // Doesn't need to be evaluated - Debug.log("interior match for %s", valueNode); - } else if (operand instanceof ComplexMatchValue) { - Debug.log("complex match for %s", valueNode); - ComplexMatchValue match = (ComplexMatchValue) operand; - operand = match.evaluate(this); - if (operand != null) { - setResult(valueNode, operand); - } - } else { - // There can be cases in which the result of an instruction is already set - // before by other instructions. } } @@ -256,19 +259,19 @@ gen.doBlockEnd(block); } - protected void matchComplexExpressions(List<ValueNode> nodes) { + protected void matchComplexExpressions(List<Node> nodes) { if (matchRules != null) { try (Scope s = Debug.scope("MatchComplexExpressions")) { if (LogVerbose.getValue()) { int i = 0; - for (ValueNode node : nodes) { + for (Node node : nodes) { Debug.log("%d: (%s) %1S", i++, node.getUsageCount(), node); } } // Match the nodes in backwards order to encourage longer matches. for (int index = nodes.size() - 1; index >= 0; index--) { - ValueNode node = nodes.get(index); + Node node = nodes.get(index); if (getOperand(node) != null) { continue; }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchContext.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchContext.java Fri Mar 13 12:27:07 2015 +0100 @@ -30,7 +30,7 @@ import com.oracle.graal.compiler.gen.*; import com.oracle.graal.compiler.match.MatchPattern.Result; import com.oracle.graal.debug.*; -import com.oracle.graal.nodes.*; +import com.oracle.graal.graph.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.virtual.*; @@ -39,15 +39,15 @@ */ public class MatchContext { - private final ValueNode root; + private final Node root; - private final List<ValueNode> nodes; + private final List<Node> nodes; private final MatchStatement rule; private Map<String, NamedNode> namedNodes; - private ArrayList<ValueNode> consumed; + private ArrayList<Node> consumed; private int startIndex; @@ -56,16 +56,16 @@ private final NodeLIRBuilder builder; private static class NamedNode { - final Class<? extends ValueNode> type; - final ValueNode value; + final Class<? extends Node> type; + final Node value; - NamedNode(Class<? extends ValueNode> type, ValueNode value) { + NamedNode(Class<? extends Node> type, Node value) { this.type = type; this.value = value; } } - public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, ValueNode node, List<ValueNode> nodes) { + public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, Node node, List<Node> nodes) { this.builder = builder; this.rule = rule; this.root = node; @@ -75,11 +75,11 @@ startIndex = endIndex = index; } - public ValueNode getRoot() { + public Node getRoot() { return root; } - public Result captureNamedValue(String name, Class<? extends ValueNode> type, ValueNode value) { + public Result captureNamedValue(String name, Class<? extends Node> type, Node value) { if (namedNodes == null) { namedNodes = new HashMap<>(2); } @@ -99,7 +99,7 @@ public Result validate() { // Ensure that there's no unsafe work in between these operations. for (int i = startIndex; i <= endIndex; i++) { - ValueNode node = nodes.get(i); + Node node = nodes.get(i); if (node instanceof VirtualObjectNode || node instanceof FloatingNode) { // The order of evaluation of these nodes controlled by data dependence so they // don't interfere with this match. @@ -108,7 +108,7 @@ if (LogVerbose.getValue()) { Debug.log("unexpected node %s", node); for (int j = startIndex; j <= endIndex; j++) { - ValueNode theNode = nodes.get(j); + Node theNode = nodes.get(j); Debug.log("%s(%s) %1s", (consumed != null && consumed.contains(theNode) || theNode == root) ? "*" : " ", theNode.getUsageCount(), theNode); } } @@ -131,7 +131,7 @@ Debug.log("with nodes %s", rule.formatMatch(root)); } if (consumed != null) { - for (ValueNode node : consumed) { + for (Node node : consumed) { // All the interior nodes should be skipped during the normal doRoot calls in // NodeLIRBuilder so mark them as interior matches. The root of the match will get a // closure which will be evaluated to produce the final LIR. @@ -146,7 +146,7 @@ * * @return Result.OK if the node can be safely consumed. */ - public Result consume(ValueNode node) { + public Result consume(Node node) { assert node.getUsageCount() <= 1 : "should have already been checked"; // Check NOT_IN_BLOCK first since that usually implies ALREADY_USED @@ -174,7 +174,7 @@ * @return the matched node * @throws GraalInternalError is the named node doesn't exist. */ - public ValueNode namedNode(String name) { + public Node namedNode(String name) { if (namedNodes != null) { NamedNode value = namedNodes.get(name); if (value != null) {
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchPattern.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchPattern.java Fri Mar 13 12:27:07 2015 +0100 @@ -25,7 +25,6 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodeinfo.*; -import com.oracle.graal.nodes.*; /** * A simple recursive pattern matcher for a DAG of nodes. @@ -50,11 +49,11 @@ static class Result { final MatchResultCode code; - final ValueNode node; + final Node node; final MatchPattern matcher; - Result(MatchResultCode result, ValueNode node, MatchPattern matcher) { + Result(MatchResultCode result, Node node, MatchPattern matcher) { this.code = result; this.node = node; this.matcher = matcher; @@ -75,32 +74,32 @@ private static final Result CACHED_NOT_SAFE = new Result(MatchResultCode.NOT_SAFE, null, null); private static final Result CACHED_ALREADY_USED = new Result(MatchResultCode.ALREADY_USED, null, null); - static Result wrongClass(ValueNode node, MatchPattern matcher) { + static Result wrongClass(Node node, MatchPattern matcher) { MatchResult_WRONG_CLASS.increment(); return Debug.isEnabled() ? new Result(MatchResultCode.WRONG_CLASS, node, matcher) : CACHED_WRONG_CLASS; } - static Result namedValueMismatch(ValueNode node, MatchPattern matcher) { + static Result namedValueMismatch(Node node, MatchPattern matcher) { MatchResult_NAMED_VALUE_MISMATCH.increment(); return Debug.isEnabled() ? new Result(MatchResultCode.NAMED_VALUE_MISMATCH, node, matcher) : CACHED_NAMED_VALUE_MISMATCH; } - static Result tooManyUsers(ValueNode node, MatchPattern matcher) { + static Result tooManyUsers(Node node, MatchPattern matcher) { MatchResult_TOO_MANY_USERS.increment(); return Debug.isEnabled() ? new Result(MatchResultCode.TOO_MANY_USERS, node, matcher) : CACHED_TOO_MANY_USERS; } - static Result notInBlock(ValueNode node, MatchPattern matcher) { + static Result notInBlock(Node node, MatchPattern matcher) { MatchResult_NOT_IN_BLOCK.increment(); return Debug.isEnabled() ? new Result(MatchResultCode.NOT_IN_BLOCK, node, matcher) : CACHED_NOT_IN_BLOCK; } - static Result notSafe(ValueNode node, MatchPattern matcher) { + static Result notSafe(Node node, MatchPattern matcher) { MatchResult_NOT_SAFE.increment(); return Debug.isEnabled() ? new Result(MatchResultCode.NOT_SAFE, node, matcher) : CACHED_NOT_SAFE; } - static Result alreadyUsed(ValueNode node, MatchPattern matcher) { + static Result alreadyUsed(Node node, MatchPattern matcher) { MatchResult_ALREADY_USED.increment(); return Debug.isEnabled() ? new Result(MatchResultCode.ALREADY_USED, node, matcher) : CACHED_ALREADY_USED; } @@ -121,7 +120,7 @@ /** * The expected type of the node. It must match exactly. */ - private final Class<? extends ValueNode> nodeClass; + private final Class<? extends Node> nodeClass; /** * An optional name for this node. A name can occur multiple times in a match and that name must @@ -151,7 +150,7 @@ this(null, name, singleUser); } - public MatchPattern(Class<? extends ValueNode> nodeClass, String name, boolean singleUser) { + public MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser) { this.nodeClass = nodeClass; this.name = name; this.singleUser = singleUser; @@ -159,7 +158,7 @@ this.inputs = null; } - private MatchPattern(Class<? extends ValueNode> nodeClass, String name, boolean singleUser, MatchPattern[] patterns, Position[] inputs) { + private MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser, MatchPattern[] patterns, Position[] inputs) { assert inputs == null || inputs.length == patterns.length; this.nodeClass = nodeClass; this.name = name; @@ -168,23 +167,23 @@ this.inputs = inputs; } - public MatchPattern(Class<? extends ValueNode> nodeClass, String name, MatchPattern first, Position[] inputs, boolean singleUser) { + public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, Position[] inputs, boolean singleUser) { this(nodeClass, name, singleUser, new MatchPattern[]{first}, inputs); } - public MatchPattern(Class<? extends ValueNode> nodeClass, String name, MatchPattern first, MatchPattern second, Position[] inputs, boolean singleUser) { + public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, Position[] inputs, boolean singleUser) { this(nodeClass, name, singleUser, new MatchPattern[]{first, second}, inputs); } - public MatchPattern(Class<? extends ValueNode> nodeClass, String name, MatchPattern first, MatchPattern second, MatchPattern third, Position[] inputs, boolean singleUser) { + public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, MatchPattern third, Position[] inputs, boolean singleUser) { this(nodeClass, name, singleUser, new MatchPattern[]{first, second, third}, inputs); } - Class<? extends ValueNode> nodeClass() { + Class<? extends Node> nodeClass() { return nodeClass; } - private Result matchType(ValueNode node) { + private Result matchType(Node node) { if (nodeClass != null && node.getClass() != nodeClass) { return Result.wrongClass(node, this); } @@ -198,7 +197,7 @@ * @param context * @return Result.OK is the pattern can be safely matched. */ - Result matchUsage(ValueNode node, MatchContext context) { + Result matchUsage(Node node, MatchContext context) { Result result = matchUsage(node, context, true); if (result == Result.OK) { result = context.validate(); @@ -206,7 +205,7 @@ return result; } - private Result matchUsage(ValueNode node, MatchContext context, boolean atRoot) { + private Result matchUsage(Node node, MatchContext context, boolean atRoot) { Result result = matchType(node); if (result != Result.OK) { return result; @@ -240,11 +239,11 @@ * @param statement * @return Result.OK if the shape of the pattern matches. */ - public Result matchShape(ValueNode node, MatchStatement statement) { + public Result matchShape(Node node, MatchStatement statement) { return matchShape(node, statement, true); } - private Result matchShape(ValueNode node, MatchStatement statement, boolean atRoot) { + private Result matchShape(Node node, MatchStatement statement, boolean atRoot) { Result result = matchType(node); if (result != Result.OK) { return result; @@ -271,7 +270,7 @@ * rule. It's assumed that a match has already succeeded against this rule, otherwise the * printing may produce exceptions. */ - public String formatMatch(ValueNode root) { + public String formatMatch(Node root) { String result = String.format("%s", root); if (patterns.length == 0) { return result; @@ -288,8 +287,8 @@ } } - private ValueNode getInput(int index, ValueNode node) { - return (ValueNode) inputs[index].get(node); + private Node getInput(int index, Node node) { + return inputs[index].get(node); } @Override
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchRuleRegistry.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchRuleRegistry.java Fri Mar 13 12:27:07 2015 +0100 @@ -32,7 +32,6 @@ import com.oracle.graal.debug.*; import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; public class MatchRuleRegistry { @@ -45,7 +44,7 @@ * @param names * @return an array of Position objects corresponding to the named fields. */ - public static Position[] findPositions(NodeClass<? extends ValueNode> nodeClass, String[] names) { + public static Position[] findPositions(NodeClass<? extends Node> nodeClass, String[] names) { Position[] result = new Position[names.length]; for (int i = 0; i < names.length; i++) { Edges edges = nodeClass.getInputEdges(); @@ -61,7 +60,7 @@ return result; } - private static final HashMap<Class<? extends NodeLIRBuilder>, Map<Class<? extends ValueNode>, List<MatchStatement>>> registry = new HashMap<>(); + private static final HashMap<Class<? extends NodeLIRBuilder>, Map<Class<? extends Node>, List<MatchStatement>>> registry = new HashMap<>(); /** * Collect all the {@link MatchStatement}s defined by the superclass chain of theClass. @@ -69,11 +68,11 @@ * @param theClass * @return the set of {@link MatchStatement}s applicable to theClass. */ - public static synchronized Map<Class<? extends ValueNode>, List<MatchStatement>> lookup(Class<? extends NodeLIRBuilder> theClass) { - Map<Class<? extends ValueNode>, List<MatchStatement>> result = registry.get(theClass); + public static synchronized Map<Class<? extends Node>, List<MatchStatement>> lookup(Class<? extends NodeLIRBuilder> theClass) { + Map<Class<? extends Node>, List<MatchStatement>> result = registry.get(theClass); if (result == null) { - Map<Class<? extends ValueNode>, List<MatchStatement>> rules = createRules(theClass); + Map<Class<? extends Node>, List<MatchStatement>> rules = createRules(theClass); registry.put(theClass, rules); assert registry.get(theClass) == rules; result = rules; @@ -81,7 +80,7 @@ if (LogVerbose.getValue()) { try (Scope s = Debug.scope("MatchComplexExpressions")) { Debug.log("Match rules for %s", theClass.getSimpleName()); - for (Entry<Class<? extends ValueNode>, List<MatchStatement>> entry : result.entrySet()) { + for (Entry<Class<? extends Node>, List<MatchStatement>> entry : result.entrySet()) { Debug.log(" For node class: %s", entry.getKey()); for (MatchStatement statement : entry.getValue()) { Debug.log(" %s", statement.getPattern()); @@ -101,7 +100,7 @@ * This is a separate, public method so that external clients can create rules with a custom * lookup and without the default caching behavior. */ - public static Map<Class<? extends ValueNode>, List<MatchStatement>> createRules(Class<? extends NodeLIRBuilder> theClass) { + public static Map<Class<? extends Node>, List<MatchStatement>> createRules(Class<? extends NodeLIRBuilder> theClass) { HashMap<Class<? extends NodeLIRBuilder>, MatchStatementSet> matchSets = new HashMap<>(); Iterable<MatchStatementSet> sl = Services.load(MatchStatementSet.class); for (MatchStatementSet rules : sl) { @@ -110,14 +109,14 @@ // Walk the class hierarchy collecting lists and merge them together. The subclass // rules are first which gives them preference over earlier rules. - Map<Class<? extends ValueNode>, List<MatchStatement>> rules = new HashMap<>(); + Map<Class<? extends Node>, List<MatchStatement>> rules = new HashMap<>(); Class<?> currentClass = theClass; do { MatchStatementSet matchSet = matchSets.get(currentClass); if (matchSet != null) { List<MatchStatement> statements = matchSet.statements(); for (MatchStatement statement : statements) { - Class<? extends ValueNode> nodeClass = statement.getPattern().nodeClass(); + Class<? extends Node> nodeClass = statement.getPattern().nodeClass(); List<MatchStatement> current = rules.get(nodeClass); if (current == null) { current = new ArrayList<>();
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchStatement.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchStatement.java Fri Mar 13 12:27:07 2015 +0100 @@ -33,11 +33,10 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodeinfo.*; -import com.oracle.graal.nodes.*; /** * A named {@link MatchPattern} along with a {@link MatchGenerator} that can be evaluated to replace - * one or more {@link ValueNode}s with a single {@link Value}. + * one or more {@link Node}s with a single {@link Value}. */ public class MatchStatement { @@ -80,7 +79,7 @@ * @return true if the statement matched something and set a {@link ComplexMatchResult} to be * evaluated by the NodeLIRBuilder. */ - public boolean generate(NodeLIRBuilder builder, int index, ValueNode node, List<ValueNode> nodes) { + public boolean generate(NodeLIRBuilder builder, int index, Node node, List<Node> nodes) { assert index == nodes.indexOf(node); // Check that the basic shape matches Result result = pattern.matchShape(node, this); @@ -115,8 +114,7 @@ /** * @param context - * @return the ValueNodes captured by the match rule in the order expected by the - * generatorMethod + * @return the Nodes captured by the match rule in the order expected by the generatorMethod */ private Object[] buildArgList(MatchContext context) { Object[] result = new Object[arguments.length]; @@ -133,7 +131,7 @@ return result; } - public String formatMatch(ValueNode root) { + public String formatMatch(Node root) { return pattern.formatMatch(root); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java Fri Mar 13 12:27:07 2015 +0100 @@ -246,7 +246,7 @@ protected static boolean livesLonger(ValueNode after, ValueNode value, NodeMappableLIRBuilder builder) { for (Node usage : value.usages()) { - if (usage != after && usage instanceof ValueNode && builder.hasOperand(((ValueNode) usage))) { + if (usage != after && usage instanceof ValueNode && builder.hasOperand(usage)) { return true; } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Fri Mar 13 12:27:07 2015 +0100 @@ -24,9 +24,11 @@ import java.util.*; +import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.extended.*; public final class Block extends AbstractBlockBase<Block> { @@ -39,6 +41,8 @@ protected Block postdominator; protected Block distancedDominatorCache; + private LocationSet killLocations; + private LocationSet killLocationsBetweenThisAndDominator; protected Block(AbstractBeginNode node) { this.beginNode = node; @@ -189,4 +193,85 @@ } return result; } + + public boolean canKill(LocationIdentity location) { + if (location.isImmutable()) { + return false; + } + return getKillLocations().contains(location); + } + + public LocationSet getKillLocations() { + if (killLocations == null) { + killLocations = calcKillLocations(); + } + return killLocations; + } + + private LocationSet calcKillLocations() { + LocationSet result = new LocationSet(); + for (FixedNode node : this.getNodes()) { + if (node instanceof MemoryCheckpoint.Single) { + LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity(); + result.add(identity); + } else if (node instanceof MemoryCheckpoint.Multi) { + for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) { + result.add(identity); + } + } + if (result.isKillAll()) { + break; + } + } + return result; + } + + public boolean canKillBetweenThisAndDominator(LocationIdentity location) { + if (location.isImmutable()) { + return false; + } + return this.getKillLocationsBetweenThisAndDominator().contains(location); + } + + private LocationSet getKillLocationsBetweenThisAndDominator() { + if (this.killLocationsBetweenThisAndDominator == null) { + LocationSet dominatorResult = new LocationSet(); + Block stopBlock = getDominator(); + for (Block b : this.getPredecessors()) { + if (b != stopBlock && (!this.isLoopHeader() || b.getLoopDepth() < this.getLoopDepth())) { + dominatorResult.addAll(b.getKillLocations()); + if (dominatorResult.isKillAll()) { + break; + } + b.calcKillLocationsBetweenThisAndTarget(dominatorResult, stopBlock); + if (dominatorResult.isKillAll()) { + break; + } + } + } + this.killLocationsBetweenThisAndDominator = dominatorResult; + } + return this.killLocationsBetweenThisAndDominator; + } + + private void calcKillLocationsBetweenThisAndTarget(LocationSet result, Block stopBlock) { + assert AbstractControlFlowGraph.dominates(stopBlock, this); + if (stopBlock == this || result.isKillAll()) { + // We reached the stop block => nothing to do. + return; + } else { + if (stopBlock == this.getDominator()) { + result.addAll(this.getKillLocationsBetweenThisAndDominator()); + } else { + // Divide and conquer: Aggregate kill locations from this to the dominator and then + // from the dominator onwards. + calcKillLocationsBetweenThisAndTarget(result, this.getDominator()); + result.addAll(this.getDominator().getKillLocations()); + if (result.isKillAll()) { + return; + } + this.getDominator().calcKillLocationsBetweenThisAndTarget(result, stopBlock); + } + } + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Fri Mar 13 12:27:07 2015 +0100 @@ -40,7 +40,7 @@ public final StructuredGraph graph; - private final NodeMap<Block> nodeToBlock; + private NodeMap<Block> nodeToBlock; private List<Block> reversePostOrder; private List<Loop<Block>> loops; @@ -365,4 +365,8 @@ } return iterA; } + + public void setNodeToBlock(NodeMap<Block> nodeMap) { + this.nodeToBlock = nodeMap; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java Fri Mar 13 12:27:07 2015 +0100 @@ -22,11 +22,14 @@ */ package com.oracle.graal.nodes.cfg; +import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.nodes.*; public class HIRLoop extends Loop<Block> { + private LocationSet killLocations; + protected HIRLoop(Loop<Block> parent, int index, Block header) { super(parent, index, header); } @@ -35,4 +38,29 @@ public long numBackedges() { return ((LoopBeginNode) getHeader().getBeginNode()).loopEnds().count(); } + + protected LocationSet getKillLocations() { + if (killLocations == null) { + killLocations = new LocationSet(); + for (Block b : this.getBlocks()) { + if (b.getLoop() == this) { + killLocations.addAll(b.getKillLocations()); + if (killLocations.isKillAll()) { + break; + } + } + } + } + for (Loop<Block> child : this.getChildren()) { + if (killLocations.isKillAll()) { + break; + } + killLocations.addAll(((HIRLoop) child).getKillLocations()); + } + return killLocations; + } + + public boolean canKill(LocationIdentity location) { + return getKillLocations().contains(location); + } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/LocationSet.java Fri Mar 13 12:27:07 2015 +0100 @@ -0,0 +1,137 @@ +/* + * Copyright (c) 2015, 2015, 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.nodes.cfg; + +import java.util.*; + +import com.oracle.graal.api.meta.*; + +public class LocationSet { + private LocationIdentity firstLocation; + private List<LocationIdentity> list; + + public LocationSet() { + list = null; + } + + public LocationSet(LocationSet other) { + this.firstLocation = other.firstLocation; + if (other.list != null && other.list.size() > 0) { + list = new ArrayList<>(other.list); + } + } + + private void initList() { + if (list == null) { + list = new ArrayList<>(4); + } + } + + public boolean isKillNone() { + return firstLocation == null; + } + + public boolean isKillAll() { + return LocationIdentity.ANY_LOCATION.equals(firstLocation); + } + + public void add(LocationIdentity location) { + if (this.isKillAll()) { + return; + } else if (LocationIdentity.ANY_LOCATION.equals(location)) { + firstLocation = location; + list = null; + } else { + if (firstLocation == null) { + firstLocation = location; + } else if (location.equals(firstLocation)) { + return; + } else { + initList(); + for (int i = 0; i < list.size(); ++i) { + LocationIdentity value = list.get(i); + if (location.equals(value)) { + return; + } + } + list.add(location); + } + } + } + + public void addAll(LocationSet other) { + if (other.firstLocation != null) { + add(other.firstLocation); + } + List<LocationIdentity> otherList = other.list; + if (otherList != null) { + for (LocationIdentity l : otherList) { + add(l); + } + } + } + + public boolean contains(LocationIdentity locationIdentity) { + assert locationIdentity != null; + assert !locationIdentity.equals(LocationIdentity.ANY_LOCATION); + assert locationIdentity.isMutable(); + if (LocationIdentity.ANY_LOCATION.equals(firstLocation)) { + return true; + } + if (locationIdentity.equals(firstLocation)) { + return true; + } + if (list != null) { + for (int i = 0; i < list.size(); ++i) { + LocationIdentity value = list.get(i); + if (locationIdentity.equals(value)) { + return true; + } + } + } + return false; + } + + public List<LocationIdentity> getCopyAsList() { + ArrayList<LocationIdentity> result = new ArrayList<>(); + if (firstLocation != null) { + result.add(firstLocation); + } + if (list != null) { + result.addAll(list); + } + return result; + } + + @Override + public String toString() { + if (this.isKillAll()) { + return "KILLALL"; + } else if (this.isKillNone()) { + return "KILLNONE"; + } else { + List<LocationIdentity> copyAsList = getCopyAsList(); + return Arrays.toString(copyAsList.toArray(new LocationIdentity[0])); + } + } +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeLIRBuilderTool.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeLIRBuilderTool.java Fri Mar 13 12:27:07 2015 +0100 @@ -28,6 +28,7 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.compiler.common.type.*; +import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.gen.*; import com.oracle.graal.nodes.*; @@ -71,5 +72,5 @@ Value[] visitInvokeArguments(CallingConvention cc, Collection<ValueNode> arguments); - void doBlock(Block block, StructuredGraph graph, BlockMap<List<ValueNode>> blockMap); + void doBlock(Block block, StructuredGraph graph, BlockMap<List<Node>> blockMap); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeMappableLIRBuilder.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeMappableLIRBuilder.java Fri Mar 13 12:27:07 2015 +0100 @@ -24,13 +24,14 @@ package com.oracle.graal.nodes.spi; import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; public interface NodeMappableLIRBuilder { - Value operand(ValueNode object); + Value operand(Node object); - boolean hasOperand(ValueNode object); + boolean hasOperand(Node object); Value setResult(ValueNode x, Value operand); }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java Fri Mar 13 12:27:07 2015 +0100 @@ -289,7 +289,7 @@ final LoweringToolImpl loweringTool = new LoweringToolImpl(context, startAnchor, activeGuards, b.getBeginNode()); // Lower the instructions of this block. - List<ValueNode> nodes = schedule.nodesFor(b); + List<Node> nodes = schedule.nodesFor(b); for (Node node : nodes) { if (node.isDeleted()) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java Fri Mar 13 12:27:07 2015 +0100 @@ -46,7 +46,7 @@ * a method and at each loop header. * * A schedule is created so that floating nodes can also be taken into account. The weight of a node - * is determined heuristically in the {@link ProfileCompiledMethodsPhase#getNodeWeight(ValueNode)} + * is determined heuristically in the {@link ProfileCompiledMethodsPhase#getNodeWeight(Node)} * method. * * Additionally, there's a second counter that's only increased for code sections without invokes. @@ -117,14 +117,14 @@ double count = 0; for (Block block : blocks) { double blockProbability = probabilities.applyAsDouble(block.getBeginNode()); - for (ValueNode node : schedule.getBlockToNodesMap().get(block)) { + for (Node node : schedule.getBlockToNodesMap().get(block)) { count += blockProbability * getNodeWeight(node); } } return count; } - private static double getNodeWeight(ValueNode node) { + private static double getNodeWeight(Node node) { if (node instanceof AbstractMergeNode) { return ((AbstractMergeNode) node).phiPredecessorCount(); } else if (node instanceof AbstractBeginNode || node instanceof AbstractEndNode || node instanceof MonitorIdNode || node instanceof ConstantNode || node instanceof ParameterNode || @@ -150,6 +150,8 @@ return node.successors().count(); } else if (node instanceof AbstractNewObjectNode) { return 10; + } else if (node instanceof VirtualState) { + return 0; } return 2; }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScheduledNodeIterator.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScheduledNodeIterator.java Fri Mar 13 12:27:07 2015 +0100 @@ -40,7 +40,7 @@ private FixedWithNextNode lastFixed; private FixedWithNextNode reconnect; - private ListIterator<ValueNode> iterator; + private ListIterator<Node> iterator; public void processNodes(Block block, SchedulePhase shedule) { lastFixed = block.getBeginNode();
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Fri Mar 13 12:27:07 2015 +0100 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2011, 2015, 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 @@ -22,26 +22,19 @@ */ package com.oracle.graal.phases.schedule; -import static com.oracle.graal.api.meta.LocationIdentity.*; import static com.oracle.graal.compiler.common.GraalOptions.*; import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*; import java.util.*; import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.common.*; import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.extended.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.virtual.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.graph.*; -import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; -import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo; public final class SchedulePhase extends Phase { @@ -75,234 +68,14 @@ LATEST_OUT_OF_LOOPS } - private class LocationSet { - private LocationIdentity firstLocation; - private List<LocationIdentity> list; - - public LocationSet() { - list = null; - } - - public LocationSet(LocationSet other) { - this.firstLocation = other.firstLocation; - if (other.list != null && other.list.size() > 0) { - list = new ArrayList<>(other.list); - } - } - - private void initList() { - if (list == null) { - list = new ArrayList<>(4); - } - } - - public void add(LocationIdentity location) { - if (LocationIdentity.ANY_LOCATION.equals(location)) { - firstLocation = location; - list = null; - } else { - if (firstLocation == null) { - firstLocation = location; - } else if (LocationIdentity.ANY_LOCATION.equals(firstLocation)) { - return; - } else if (location.equals(firstLocation)) { - return; - } else { - initList(); - for (int i = 0; i < list.size(); ++i) { - LocationIdentity value = list.get(i); - if (location.equals(value)) { - return; - } - } - list.add(location); - } - } - } - - public void addAll(LocationSet other) { - if (other.firstLocation != null) { - add(other.firstLocation); - } - List<LocationIdentity> otherList = other.list; - if (otherList != null) { - for (LocationIdentity l : otherList) { - add(l); - } - } - } - - public boolean contains(LocationIdentity locationIdentity) { - assert locationIdentity != null; - assert !locationIdentity.equals(LocationIdentity.ANY_LOCATION); - assert !locationIdentity.equals(LocationIdentity.FINAL_LOCATION); - if (LocationIdentity.ANY_LOCATION.equals(firstLocation)) { - return true; - } - if (locationIdentity.equals(firstLocation)) { - return true; - } - if (list != null) { - for (int i = 0; i < list.size(); ++i) { - LocationIdentity value = list.get(i); - if (locationIdentity.equals(value)) { - return true; - } - } - } - return false; - } - - public List<LocationIdentity> getCopyAsList() { - ArrayList<LocationIdentity> result = new ArrayList<>(); - if (firstLocation != null) { - result.add(firstLocation); - } - if (list != null) { - result.addAll(list); - } - return result; - } - } - - private class NewMemoryScheduleClosure extends BlockIteratorClosure<LocationSet> { - private Node excludeNode; - private Block upperBoundBlock; - - public NewMemoryScheduleClosure(Node excludeNode, Block upperBoundBlock) { - this.excludeNode = excludeNode; - this.upperBoundBlock = upperBoundBlock; - } - - public NewMemoryScheduleClosure() { - this(null, null); - } - - @Override - protected LocationSet getInitialState() { - return cloneState(blockToKillSet.get(getCFG().getStartBlock())); - } - - @Override - protected LocationSet processBlock(Block block, LocationSet currentState) { - assert block != null; - currentState.addAll(computeKillSet(block, block == upperBoundBlock ? excludeNode : null)); - return currentState; - } - - @Override - protected LocationSet merge(Block merge, List<LocationSet> states) { - assert merge.getBeginNode() instanceof AbstractMergeNode; - - LocationSet initKillSet = new LocationSet(); - for (LocationSet state : states) { - initKillSet.addAll(state); - } - - return initKillSet; - } - - @Override - protected LocationSet cloneState(LocationSet state) { - return new LocationSet(state); - } - - @Override - protected List<LocationSet> processLoop(Loop<Block> loop, LocationSet state) { - LoopInfo<LocationSet> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(state)); - - assert loop.getHeader().getBeginNode() instanceof LoopBeginNode; - LocationSet headerState = merge(loop.getHeader(), info.endStates); - - // second iteration, for propagating information to loop exits - info = ReentrantBlockIterator.processLoop(this, loop, cloneState(headerState)); - - return info.exitStates; - } - } - - /** - * gather all kill locations by iterating trough the nodes assigned to a block. - * - * assumptions: {@link MemoryCheckpoint MemoryCheckPoints} are {@link FixedNode FixedNodes}. - * - * @param block block to analyze - * @param excludeNode if null, compute normal set of kill locations. if != null, don't add kills - * until we reach excludeNode. - * @return all killed locations - */ - private LocationSet computeKillSet(Block block, Node excludeNode) { - // cache is only valid if we don't potentially exclude kills from the set - if (excludeNode == null) { - LocationSet cachedSet = blockToKillSet.get(block); - if (cachedSet != null) { - return cachedSet; - } - } - - // add locations to excludedLocations until we reach the excluded node - boolean foundExcludeNode = excludeNode == null; - - LocationSet set = new LocationSet(); - LocationSet excludedLocations = new LocationSet(); - if (block.getBeginNode() instanceof AbstractMergeNode) { - AbstractMergeNode mergeNode = (AbstractMergeNode) block.getBeginNode(); - for (MemoryPhiNode phi : mergeNode.usages().filter(MemoryPhiNode.class)) { - if (foundExcludeNode) { - set.add(phi.getLocationIdentity()); - } else { - excludedLocations.add(phi.getLocationIdentity()); - foundExcludeNode = phi == excludeNode; - } - } - } - - AbstractBeginNode startNode = cfg.getStartBlock().getBeginNode(); - assert startNode instanceof StartNode; - - LocationSet accm = foundExcludeNode ? set : excludedLocations; - for (Node node : block.getNodes()) { - if (!foundExcludeNode && node == excludeNode) { - foundExcludeNode = true; - } - if (node != startNode) { - if (node instanceof MemoryCheckpoint.Single) { - LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity(); - accm.add(identity); - } else if (node instanceof MemoryCheckpoint.Multi) { - for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) { - accm.add(identity); - } - } - assert MemoryCheckpoint.TypeAssertion.correctType(node); - } - - if (foundExcludeNode) { - accm = set; - } - } - - // merge it for the cache entry - excludedLocations.addAll(set); - blockToKillSet.put(block, excludedLocations); - - return set; - } - - private LocationSet computeKillSet(Block block) { - return computeKillSet(block, null); - } - private ControlFlowGraph cfg; - private NodeMap<Block> earliestCache; /** * Map from blocks to the nodes in each block. */ - private BlockMap<List<ValueNode>> blockToNodesMap; + private BlockMap<List<Node>> blockToNodesMap; private BlockMap<LocationSet> blockToKillSet; private final SchedulingStrategy selectedStrategy; - private boolean scheduleConstants; private NodeMap<Block> nodeToBlockMap; public SchedulePhase() { @@ -313,41 +86,366 @@ this.selectedStrategy = strategy; } - public void setScheduleConstants(boolean value) { - scheduleConstants = value; - } - @Override protected void run(StructuredGraph graph) { // assert GraphOrder.assertNonCyclicGraph(graph); cfg = ControlFlowGraph.compute(graph, true, true, true, false); - earliestCache = graph.createNodeMap(); - blockToNodesMap = new BlockMap<>(cfg); + + if (selectedStrategy == SchedulingStrategy.EARLIEST) { + this.nodeToBlockMap = graph.createNodeMap(); + this.blockToNodesMap = new BlockMap<>(cfg); + NodeBitMap visited = graph.createNodeBitMap(); + scheduleEarliestIterative(cfg, blockToNodesMap, nodeToBlockMap, visited, graph); + return; + } else { + boolean isOutOfLoops = selectedStrategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS; + if (selectedStrategy == SchedulingStrategy.LATEST || isOutOfLoops) { + NodeMap<Block> currentNodeMap = graph.createNodeMap(); + BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg); + NodeBitMap visited = graph.createNodeBitMap(); + scheduleEarliestIterative(cfg, earliestBlockToNodesMap, currentNodeMap, visited, graph); + BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg); + + for (Block b : cfg.getBlocks()) { + latestBlockToNodesMap.put(b, new ArrayList<Node>()); + } + + BlockMap<ArrayList<FloatingReadNode>> watchListMap = null; + for (Block b : cfg.postOrder()) { + List<Node> blockToNodes = earliestBlockToNodesMap.get(b); + LocationSet killed = null; + int previousIndex = blockToNodes.size(); + for (int i = blockToNodes.size() - 1; i >= 0; --i) { + Node currentNode = blockToNodes.get(i); + assert currentNodeMap.get(currentNode) == b; + assert !(currentNode instanceof PhiNode) && !(currentNode instanceof ProxyNode); + assert visited.isMarked(currentNode); + if (currentNode instanceof FixedNode) { + // For these nodes, the earliest is at the same time the latest block. + } else { + Block currentBlock = b; + assert currentBlock != null; + Block latestBlock = calcLatestBlock(b, isOutOfLoops, currentNode, currentNodeMap); + assert AbstractControlFlowGraph.dominates(currentBlock, latestBlock) || currentNode instanceof VirtualState : currentNode + " " + currentBlock + " " + latestBlock; + if (latestBlock != currentBlock) { + if (currentNode instanceof FloatingReadNode) { + + FloatingReadNode floatingReadNode = (FloatingReadNode) currentNode; + LocationIdentity location = floatingReadNode.getLocationIdentity(); + if (location.isMutable()) { + if (currentBlock.canKill(location)) { + if (killed == null) { + killed = new LocationSet(); + } + fillKillSet(killed, blockToNodes.subList(i + 1, previousIndex)); + previousIndex = i; + if (killed.contains(location)) { + latestBlock = currentBlock; + } + } - if (selectedStrategy != SchedulingStrategy.EARLIEST && graph.isAfterFloatingReadPhase()) { - blockToKillSet = new BlockMap<>(cfg); + if (latestBlock != currentBlock) { + // We are not constraint within currentBlock. Check if + // we are contraint while walking down the dominator + // line. + Block newLatestBlock = adjustLatestForRead(currentBlock, latestBlock, location); + assert dominates(newLatestBlock, latestBlock); + assert dominates(currentBlock, newLatestBlock); + latestBlock = newLatestBlock; + + if (newLatestBlock != currentBlock && latestBlock.canKill(location)) { + if (watchListMap == null) { + watchListMap = new BlockMap<>(cfg); + } + if (watchListMap.get(latestBlock) == null) { + watchListMap.put(latestBlock, new ArrayList<>()); + } + watchListMap.get(latestBlock).add(floatingReadNode); + } + } + } + } + currentNodeMap.set(currentNode, latestBlock); + currentBlock = latestBlock; + } + latestBlockToNodesMap.get(currentBlock).add(currentNode); + } + } + } + + sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited); + + this.blockToNodesMap = latestBlockToNodesMap; + this.nodeToBlockMap = currentNodeMap; + + assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap); + cfg.setNodeToBlock(currentNodeMap); + } + } + } + + private static boolean verifySchedule(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap) { + for (Block b : cfg.getBlocks()) { + List<Node> nodes = blockToNodesMap.get(b); + for (Node n : nodes) { + assert n.isAlive(); + assert nodeMap.get(n) == b; + } + } + return true; + } + + private static Block adjustLatestForRead(Block earliestBlock, Block latestBlock, LocationIdentity location) { + assert strictlyDominates(earliestBlock, latestBlock); + Block current = latestBlock.getDominator(); + + // Collect dominator chain that needs checking. + List<Block> dominatorChain = new ArrayList<>(); + dominatorChain.add(latestBlock); + while (current != earliestBlock) { + // Current is an intermediate dominator between earliestBlock and latestBlock. + assert strictlyDominates(earliestBlock, current) && strictlyDominates(current, latestBlock); + if (current.canKill(location)) { + dominatorChain.clear(); + } + dominatorChain.add(current); + current = current.getDominator(); } - if (selectedStrategy == SchedulingStrategy.EARLIEST) { - scheduleEarliestIterative(blockToNodesMap, graph); + // The first element of dominatorChain now contains the latest possible block. + assert dominatorChain.size() >= 1; + assert dominatorChain.get(dominatorChain.size() - 1).getDominator() == earliestBlock; + + Block lastBlock = earliestBlock; + for (int i = dominatorChain.size() - 1; i >= 0; --i) { + Block currentBlock = dominatorChain.get(i); + if (lastBlock.getLoop() != currentBlock.getLoop()) { + // We are crossing a loop boundary. Both loops must not kill the location for the + // crossing to be safe. + if (lastBlock.getLoop() != null && ((HIRLoop) lastBlock.getLoop()).canKill(location)) { + break; + } + if (currentBlock.getLoop() != null && ((HIRLoop) currentBlock.getLoop()).canKill(location)) { + break; + } + } + + if (currentBlock.canKillBetweenThisAndDominator(location)) { + break; + } + lastBlock = currentBlock; + } + + return lastBlock; + } + + private static void fillKillSet(LocationSet killed, List<Node> subList) { + if (!killed.isKillAll()) { + for (Node n : subList) { + // Check if this node kills a node in the watch list. + if (n instanceof MemoryCheckpoint.Single) { + LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity(); + killed.add(identity); + if (killed.isKillAll()) { + return; + } + } else if (n instanceof MemoryCheckpoint.Multi) { + for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) { + killed.add(identity); + if (killed.isKillAll()) { + return; + } + } + } + } + } + } + + private static void sortNodesLatestWithinBlock(ControlFlowGraph cfg, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> currentNodeMap, + BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap visited) { + for (Block b : cfg.getBlocks()) { + sortNodesLatestWithinBlock(b, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited); + } + } + + private static void sortNodesLatestWithinBlock(Block b, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> nodeMap, + BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap unprocessed) { + ArrayList<Node> result = new ArrayList<>(); + ArrayList<FloatingReadNode> watchList = null; + if (watchListMap != null) { + watchList = watchListMap.get(b); + assert watchList == null || !b.getKillLocations().isKillNone(); + } + AbstractBeginNode beginNode = b.getBeginNode(); + if (beginNode instanceof LoopExitNode) { + LoopExitNode loopExitNode = (LoopExitNode) beginNode; + for (ProxyNode proxy : loopExitNode.proxies()) { + unprocessed.clear(proxy); + ValueNode value = proxy.value(); + if (nodeMap.get(value) == b) { + sortIntoList(value, b, result, nodeMap, unprocessed, null); + } + } + } + FixedNode endNode = b.getEndNode(); + for (Node n : earliestBlockToNodesMap.get(b)) { + if (n != endNode) { + if (n instanceof FixedNode) { + assert nodeMap.get(n) == b; + checkWatchList(b, nodeMap, unprocessed, result, watchList, n); + sortIntoList(n, b, result, nodeMap, unprocessed, null); + } else if (nodeMap.get(n) == b && n instanceof FloatingReadNode) { + FloatingReadNode floatingReadNode = (FloatingReadNode) n; + LocationIdentity location = floatingReadNode.getLocationIdentity(); + if (b.canKill(location)) { + // This read can be killed in this block, add to watch list. + if (watchList == null) { + watchList = new ArrayList<>(); + } + watchList.add(floatingReadNode); + } + } + } + } + + for (Node n : latestBlockToNodesMap.get(b)) { + assert nodeMap.get(n) == b; + assert !(n instanceof FixedNode); + if (unprocessed.isMarked(n)) { + sortIntoList(n, b, result, nodeMap, unprocessed, endNode); + } + } + + if (unprocessed.isMarked(endNode)) { + sortIntoList(endNode, b, result, nodeMap, unprocessed, null); + } + + latestBlockToNodesMap.put(b, result); + } + + private static void checkWatchList(Block b, NodeMap<Block> nodeMap, NodeBitMap unprocessed, ArrayList<Node> result, ArrayList<FloatingReadNode> watchList, Node n) { + if (watchList != null && !watchList.isEmpty()) { + // Check if this node kills a node in the watch list. + if (n instanceof MemoryCheckpoint.Single) { + LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity(); + checkWatchList(watchList, identity, b, result, nodeMap, unprocessed); + } else if (n instanceof MemoryCheckpoint.Multi) { + for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) { + checkWatchList(watchList, identity, b, result, nodeMap, unprocessed); + } + } + } + } + + private static void checkWatchList(ArrayList<FloatingReadNode> watchList, LocationIdentity identity, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed) { + assert identity.isMutable(); + if (LocationIdentity.ANY_LOCATION.equals(identity)) { + for (FloatingReadNode r : watchList) { + if (unprocessed.isMarked(r)) { + sortIntoList(r, b, result, nodeMap, unprocessed, null); + } + } + watchList.clear(); + } else { + int index = 0; + while (index < watchList.size()) { + FloatingReadNode r = watchList.get(index); + LocationIdentity locationIdentity = r.getLocationIdentity(); + assert !LocationIdentity.FINAL_LOCATION.equals(locationIdentity); + if (unprocessed.isMarked(r)) { + if (LocationIdentity.ANY_LOCATION.equals(identity) || LocationIdentity.ANY_LOCATION.equals(locationIdentity) || identity.equals(locationIdentity)) { + sortIntoList(r, b, result, nodeMap, unprocessed, null); + } else { + ++index; + continue; + } + } + int lastIndex = watchList.size() - 1; + watchList.set(index, watchList.get(lastIndex)); + watchList.remove(lastIndex); + } + } + } + + private static void sortIntoList(Node n, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed, Node excludeNode) { + assert unprocessed.isMarked(n) : n; + unprocessed.clear(n); + + assert nodeMap.get(n) == b; + + if (n instanceof PhiNode) { return; } - assignBlockToNodes(graph, selectedStrategy); - printSchedule("after assign nodes to blocks"); + for (Node input : n.inputs()) { + if (nodeMap.get(input) == b && unprocessed.isMarked(input) && input != excludeNode) { + sortIntoList(input, b, result, nodeMap, unprocessed, excludeNode); + } + } - sortNodesWithinBlocks(graph, selectedStrategy); - printSchedule("after sorting nodes within blocks"); + if (n instanceof ProxyNode) { + // Skip proxy nodes. + } else { + result.add(n); + } + } - private void scheduleEarliestIterative(BlockMap<List<ValueNode>> blockToNodes, StructuredGraph graph) { - NodeMap<Block> nodeToBlock = graph.createNodeMap(); - NodeBitMap visited = graph.createNodeBitMap(); + private static Block calcLatestBlock(Block earliestBlock, boolean scheduleOutOfLoops, Node currentNode, NodeMap<Block> currentNodeMap) { + Block block = null; + assert currentNode.hasUsages(); + for (Node usage : currentNode.usages()) { + block = calcBlockForUsage(currentNode, usage, block, currentNodeMap); + if (scheduleOutOfLoops) { + while (block.getLoopDepth() > earliestBlock.getLoopDepth()) { + block = block.getDominator(); + } + } + if (block == earliestBlock) { + // No need to search further. The earliest block *must* be a valid schedule block. + break; + } + } + assert block != null : currentNode; + return block; + } + + private static Block calcBlockForUsage(Node node, Node usage, Block startCurrentBlock, NodeMap<Block> currentNodeMap) { + assert !(node instanceof PhiNode); + Block currentBlock = startCurrentBlock; + if (usage instanceof PhiNode) { + // An input to a PhiNode is used at the end of the predecessor block that corresponds to + // the PhiNode input. One PhiNode can use an input multiple times. + PhiNode phi = (PhiNode) usage; + AbstractMergeNode merge = phi.merge(); + Block mergeBlock = currentNodeMap.get(merge); + for (int i = 0; i < phi.valueCount(); ++i) { + if (phi.valueAt(i) == node) { + currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, mergeBlock.getPredecessors().get(i)); + } + } + } else if (usage instanceof AbstractBeginNode) { + AbstractBeginNode abstractBeginNode = (AbstractBeginNode) usage; + if (abstractBeginNode instanceof StartNode) { + currentBlock = currentNodeMap.get(abstractBeginNode); + } else { + currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(abstractBeginNode).getDominator()); + } + } else { + // All other types of usages: Put the input into the same block as the usage. + currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(usage)); + } + return currentBlock; + } + + private static void scheduleEarliestIterative(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph) { + + BlockMap<Boolean> floatingReads = new BlockMap<>(cfg); // Add begin nodes as the first entry and set the block for phi nodes. for (Block b : cfg.getBlocks()) { AbstractBeginNode beginNode = b.getBeginNode(); - ArrayList<ValueNode> nodes = new ArrayList<>(); + ArrayList<Node> nodes = new ArrayList<>(); nodeToBlock.set(beginNode, b); nodes.add(beginNode); blockToNodes.put(b, nodes); @@ -374,10 +472,9 @@ nodeToBlock.set(endNode, b); } - processStack(blockToNodes, nodeToBlock, visited, stack); + processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack); // Visit back input edges of loop phis. - boolean changed; boolean unmarkedPhi; do { @@ -391,7 +488,7 @@ if (node != null && !visited.isMarked(node)) { changed = true; stack.push(node); - processStack(blockToNodes, nodeToBlock, visited, stack); + processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack); } } } else { @@ -424,16 +521,80 @@ } } - this.blockToNodesMap = blockToNodes; - this.nodeToBlockMap = nodeToBlock; + for (Block b : cfg.getBlocks()) { + if (floatingReads.get(b) == Boolean.TRUE) { + resortEarliestWithinBlock(b, blockToNodes, nodeToBlock, visited); + } + } } - private static void addNode(BlockMap<List<ValueNode>> blockToNodes, Block b, ValueNode endNode) { + private static void resortEarliestWithinBlock(Block b, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap unprocessed) { + ArrayList<FloatingReadNode> watchList = new ArrayList<>(); + List<Node> oldList = blockToNodes.get(b); + AbstractBeginNode beginNode = b.getBeginNode(); + for (Node n : oldList) { + if (n instanceof FloatingReadNode) { + FloatingReadNode floatingReadNode = (FloatingReadNode) n; + LocationIdentity locationIdentity = floatingReadNode.getLocationIdentity(); + if (locationIdentity.isMutable()) { + ValueNode lastAccessLocation = floatingReadNode.getLastLocationAccess().asNode(); + if (nodeToBlock.get(lastAccessLocation) == b && lastAccessLocation != beginNode) { + // This node's last access location is within this block. Add to watch list + // when processing the last access location. + } else { + watchList.add(floatingReadNode); + } + } + } + } + + ArrayList<Node> newList = new ArrayList<>(); + assert oldList.get(0) == beginNode; + unprocessed.clear(beginNode); + newList.add(beginNode); + for (int i = 1; i < oldList.size(); ++i) { + Node n = oldList.get(i); + if (unprocessed.isMarked(n)) { + if (n instanceof MemoryCheckpoint) { + assert n instanceof FixedNode; + if (watchList.size() > 0) { + // Check whether we need to commit reads from the watch list. + checkWatchList(b, nodeToBlock, unprocessed, newList, watchList, n); + } + + // Add potential dependent reads to the watch list. + for (Node usage : n.usages()) { + if (usage instanceof FloatingReadNode) { + FloatingReadNode floatingReadNode = (FloatingReadNode) usage; + if (nodeToBlock.get(floatingReadNode) == b && floatingReadNode.getLastLocationAccess() == n) { + watchList.add(floatingReadNode); + } + } + } + } + assert unprocessed.isMarked(n); + unprocessed.clear(n); + newList.add(n); + } else { + // This node was pulled up. + assert !(n instanceof FixedNode); + } + } + + for (Node n : newList) { + unprocessed.mark(n); + } + + assert newList.size() == oldList.size(); + blockToNodes.put(b, newList); + } + + private static void addNode(BlockMap<List<Node>> blockToNodes, Block b, Node endNode) { assert !blockToNodes.get(b).contains(endNode) : endNode; blockToNodes.get(b).add(endNode); } - private void processStack(BlockMap<List<ValueNode>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, Stack<Node> stack) { + private static void processStack(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, BlockMap<Boolean> floatingReads, Stack<Node> stack) { Block startBlock = cfg.getStartBlock(); while (!stack.isEmpty()) { Node current = stack.peek(); @@ -494,32 +655,25 @@ curBlock = earliest; } assert curBlock != null; - if (current instanceof ValueNode) { - addNode(blockToNodes, curBlock, (ValueNode) current); + addNode(blockToNodes, curBlock, current); + nodeToBlock.set(current, curBlock); + if (current instanceof FloatingReadNode) { + FloatingReadNode floatingReadNode = (FloatingReadNode) current; + if (curBlock.canKill(floatingReadNode.getLocationIdentity())) { + floatingReads.put(curBlock, Boolean.TRUE); + } } - nodeToBlock.set(current, curBlock); } } } } - private Block blockForMemoryNode(MemoryNode memory) { - MemoryNode current = memory; - while (current instanceof MemoryProxy) { - current = ((MemoryProxy) current).getOriginalMemoryNode(); - } - Block b = cfg.getNodeToBlock().get(current.asNode()); - assert b != null : "all lastAccess locations should have a block assignment from CFG"; - return b; + @Override + public String toString() { + return printScheduleHelper("Schedule"); } - private void printSchedule(String desc) { - if (Debug.isLogEnabled()) { - printScheduleHelper(desc); - } - } - - private void printScheduleHelper(String desc) { + private String printScheduleHelper(String desc) { Formatter buf = new Formatter(); buf.format("=== %s / %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, desc); for (Block b : getCFG().getBlocks()) { @@ -548,7 +702,7 @@ } } buf.format("%n"); - Debug.log("%s", buf); + return buf.toString(); } private static void printNode(Node n) { @@ -579,7 +733,7 @@ /** * Gets the map from each block to the nodes in the block. */ - public BlockMap<List<ValueNode>> getBlockToNodesMap() { + public BlockMap<List<Node>> getBlockToNodesMap() { return blockToNodesMap; } @@ -590,660 +744,7 @@ /** * Gets the nodes in a given block. */ - public List<ValueNode> nodesFor(Block block) { + public List<Node> nodesFor(Block block) { return blockToNodesMap.get(block); } - - private void assignBlockToNodes(StructuredGraph graph, SchedulingStrategy strategy) { - for (Block block : cfg.getBlocks()) { - List<ValueNode> nodes = new ArrayList<>(); - if (blockToNodesMap.get(block) != null) { - throw new SchedulingError(); - } - blockToNodesMap.put(block, nodes); - for (FixedNode node : block.getNodes()) { - nodes.add(node); - } - } - - for (Node n : graph.getNodes()) { - if (n instanceof ValueNode) { - assignBlockToNode((ValueNode) n, strategy); - } - } - } - - /** - * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are - * already assigned to a block. - */ - private void assignBlockToNode(ValueNode node, SchedulingStrategy strategy) { - assert !node.isDeleted(); - - if (cfg.getNodeToBlock().containsKey(node)) { - return; - } - if (!scheduleConstants && node instanceof ConstantNode) { - return; - } - if (node instanceof VirtualObjectNode) { - return; - } - // PhiNodes, ProxyNodes and FixedNodes should already have been placed in blocks by - // ControlFlowGraph.identifyBlocks - if (node instanceof PhiNode || node instanceof ProxyNode || node instanceof FixedNode) { - throw new SchedulingError("%s should already have been placed in a block", node); - } - - Block earliestBlock = earliestBlock(node); - Block block = null; - Block latest = null; - switch (strategy) { - case EARLIEST: - block = earliestBlock; - break; - case LATEST: - case LATEST_OUT_OF_LOOPS: - boolean scheduleRead = node instanceof FloatingReadNode && !((FloatingReadNode) node).location().getLocationIdentity().isImmutable(); - if (scheduleRead) { - FloatingReadNode read = (FloatingReadNode) node; - block = optimalBlock(read, strategy); - Debug.log("schedule for %s: %s", read, block); - assert dominates(earliestBlock, block) : String.format("%s (%s) cannot be scheduled before earliest schedule (%s). location: %s", read, block, earliestBlock, - read.getLocationIdentity()); - } else { - block = latestBlock(node, strategy, earliestBlock); - } - if (block == null) { - // handle nodes without usages - block = earliestBlock; - } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) { - // schedule at the latest position possible in the outermost loop possible - latest = block; - block = scheduleOutOfLoops(node, block, earliestBlock); - } - - assert assertReadSchedule(node, earliestBlock, block, latest, scheduleRead); - break; - default: - throw new GraalInternalError("unknown scheduling strategy"); - } - if (!dominates(earliestBlock, block)) { - throw new SchedulingError("%s: Graph cannot be scheduled : inconsistent for %s, %d usages, (%s needs to dominate %s)", node.graph(), node, node.getUsageCount(), earliestBlock, block); - } - cfg.getNodeToBlock().set(node, block); - blockToNodesMap.get(block).add(node); - } - - private boolean assertReadSchedule(ValueNode node, Block earliestBlock, Block block, Block latest, boolean scheduleRead) { - if (scheduleRead) { - FloatingReadNode read = (FloatingReadNode) node; - MemoryNode lastLocationAccess = read.getLastLocationAccess(); - Block upperBound = blockForMemoryNode(lastLocationAccess); - assert dominates(upperBound, block) : String.format("out of loop movement voilated memory semantics for %s (location %s). moved to %s but upper bound is %s (earliest: %s, latest: %s)", - read, read.getLocationIdentity(), block, upperBound, earliestBlock, latest); - } - return true; - } - - /** - * this method tries to find the "optimal" schedule for a read, by pushing it down towards its - * latest schedule starting by the earliest schedule. By doing this, it takes care of memory - * dependencies using kill sets. - * - * In terms of domination relation, it looks like this: - * - * <pre> - * U upperbound block, defined by last access location of the floating read - * ∧ - * E earliest block - * ∧ - * O optimal block, first block that contains a kill of the read's location - * ∧ - * L latest block - * </pre> - * - * i.e. <code>upperbound `dom` earliest `dom` optimal `dom` latest</code>. - * - */ - private Block optimalBlock(FloatingReadNode n, SchedulingStrategy strategy) { - LocationIdentity locid = n.location().getLocationIdentity(); - assert !locid.isImmutable(); - - Block upperBoundBlock = blockForMemoryNode(n.getLastLocationAccess()); - Block earliestBlock = earliestBlock(n); - assert dominates(upperBoundBlock, earliestBlock) : "upper bound (" + upperBoundBlock + ") should dominate earliest (" + earliestBlock + ")"; - - Block latestBlock = latestBlock(n, strategy, earliestBlock); - assert latestBlock != null && dominates(earliestBlock, latestBlock) : "earliest (" + earliestBlock + ") should dominate latest block (" + latestBlock + ")"; - - Debug.log("processing %s (accessing %s): latest %s, earliest %s, upper bound %s (%s)", n, locid, latestBlock, earliestBlock, upperBoundBlock, n.getLastLocationAccess()); - if (earliestBlock == latestBlock) { - // read is fixed to this block, nothing to schedule - return latestBlock; - } - - Deque<Block> path = computePathInDominatorTree(earliestBlock, latestBlock); - Debug.log("|path| is %d: %s", path.size(), path); - - // follow path, start at earliest schedule - while (path.size() > 0) { - Block currentBlock = path.pop(); - Block dominatedBlock = path.size() == 0 ? null : path.peek(); - if (dominatedBlock != null && !currentBlock.getSuccessors().contains(dominatedBlock)) { - // the dominated block is not a successor -> we have a split - assert dominatedBlock.getBeginNode() instanceof AbstractMergeNode; - - NewMemoryScheduleClosure closure = null; - if (currentBlock == upperBoundBlock) { - assert earliestBlock == upperBoundBlock; - // don't treat lastLocationAccess node as a kill for this read. - closure = new NewMemoryScheduleClosure(ValueNodeUtil.asNode(n.getLastLocationAccess()), upperBoundBlock); - } else { - closure = new NewMemoryScheduleClosure(); - } - Map<FixedNode, LocationSet> states; - states = ReentrantBlockIterator.apply(closure, currentBlock, new LocationSet(), block -> block == dominatedBlock); - - LocationSet mergeState = states.get(dominatedBlock.getBeginNode()); - if (mergeState.contains(locid)) { - // location got killed somewhere in the branches, - // thus we've to move the read above it - return currentBlock; - } - } else { - if (currentBlock == upperBoundBlock) { - assert earliestBlock == upperBoundBlock; - LocationSet ks = computeKillSet(upperBoundBlock, ValueNodeUtil.asNode(n.getLastLocationAccess())); - if (ks.contains(locid)) { - return upperBoundBlock; - } - } else if (dominatedBlock == null || computeKillSet(currentBlock).contains(locid)) { - return currentBlock; - } - } - } - throw new SchedulingError("should have found a block for " + n); - } - - /** - * compute path in dominator tree from earliest schedule to latest schedule. - * - * @return the order of the stack is such as the first element is the earliest schedule. - */ - private static Deque<Block> computePathInDominatorTree(Block earliestBlock, Block latestBlock) { - Deque<Block> path = new LinkedList<>(); - Block currentBlock = latestBlock; - while (currentBlock != null && dominates(earliestBlock, currentBlock)) { - path.push(currentBlock); - currentBlock = currentBlock.getDominator(); - } - assert path.peek() == earliestBlock; - return path; - } - - /** - * Calculates the last block that the given node could be scheduled in, i.e., the common - * dominator of all usages. To do so all usages are also assigned to blocks. - * - * @param strategy - * @param earliestBlock - */ - private Block latestBlock(ValueNode node, SchedulingStrategy strategy, Block earliestBlock) { - Block block = null; - for (Node usage : node.usages()) { - block = blocksForUsage(node, usage, block, earliestBlock, strategy); - if (block == earliestBlock) { - break; - } - } - - assert assertLatestBlockResult(node, block); - return block; - } - - private boolean assertLatestBlockResult(ValueNode node, Block block) throws SchedulingError { - if (block != null && !dominates(earliestBlock(node), block)) { - throw new SchedulingError("failed to find correct latest schedule for %s. cdbc: %s, earliest: %s", node, block, earliestBlock(node)); - } - return true; - } - - /** - * Determines the earliest block in which the given node can be scheduled. - */ - private Block earliestBlock(Node node) { - Block earliest = cfg.getNodeToBlock().get(node); - if (earliest != null) { - return earliest; - } - earliest = earliestCache.get(node); - if (earliest != null) { - return earliest; - } - return earliestBlockHelper(node, earliest); - } - - private Block earliestBlockHelper(Node node, Block earliestStart) throws SchedulingError { - /* - * All inputs must be in a dominating block, otherwise the graph cannot be scheduled. This - * implies that the inputs' blocks have a total ordering via their dominance relation. So in - * order to find the earliest block placement for this node we need to find the input block - * that is dominated by all other input blocks. - */ - Block earliest = earliestStart; - - if (node.predecessor() != null) { - throw new SchedulingError(); - } - for (Node input : node.inputs()) { - if (input != null) { - assert input instanceof ValueNode; - Block inputEarliest; - if (input instanceof InvokeWithExceptionNode) { - inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next()); - } else { - inputEarliest = earliestBlock(input); - } - if (earliest == null || earliest.getDominatorDepth() < inputEarliest.getDominatorDepth()) { - earliest = inputEarliest; - } - } - } - if (earliest == null) { - earliest = cfg.getStartBlock(); - } - earliestCache.set(node, earliest); - return earliest; - } - - /** - * Schedules a node out of loop based on its earliest schedule. Note that this movement is only - * valid if it's done for <b>every</b> other node in the schedule, otherwise this movement is - * not valid. - * - * @param n Node to schedule - * @param latestBlock latest possible schedule for {@code n} - * @param earliest earliest possible schedule for {@code n} - * @return block schedule for {@code n} which is not inside a loop (if possible) - */ - private static Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) { - if (latestBlock == null) { - throw new SchedulingError("no latest : %s", n); - } - Block cur = latestBlock; - Block result = latestBlock; - Loop<?> earliestLoop = earliest.getLoop(); - while (true) { - Loop<?> curLoop = cur.getLoop(); - if (curLoop == earliestLoop) { - return result; - } else { - Block dom = cur.getDominator(); - if (dom.getLoopDepth() < result.getLoopDepth()) { - result = dom; - } - cur = dom; - } - } - } - - /** - * Passes all blocks that a specific usage of a node is in to a given closure. This is more - * complex than just taking the usage's block because of of PhiNodes and FrameStates. - * - * @param node the node that needs to be scheduled - * @param usage the usage whose blocks need to be considered - * @param earliestBlock - */ - private Block blocksForUsage(ValueNode node, Node usage, Block startCurrentBlock, Block earliestBlock, SchedulingStrategy strategy) { - assert !(node instanceof PhiNode); - Block currentBlock = startCurrentBlock; - if (usage instanceof PhiNode) { - // An input to a PhiNode is used at the end of the predecessor block that corresponds to - // the PhiNode input. - // One PhiNode can use an input multiple times, the closure will be called for each - // usage. - PhiNode phi = (PhiNode) usage; - AbstractMergeNode merge = phi.merge(); - Block mergeBlock = cfg.getNodeToBlock().get(merge); - for (int i = 0; i < phi.valueCount(); ++i) { - if (phi.valueAt(i) == node) { - currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, mergeBlock.getPredecessors().get(i)); - if (currentBlock == earliestBlock) { - break; - } - } - } - } else if (usage instanceof VirtualState) { - // The following logic does not work if node is a PhiNode, but this method is never - // called for PhiNodes. - for (Node unscheduledUsage : usage.usages()) { - if (unscheduledUsage instanceof VirtualState) { - // If a FrameState is an outer FrameState this method behaves as if the inner - // FrameState was the actual usage, by recursing. - currentBlock = blocksForUsage(node, unscheduledUsage, currentBlock, earliestBlock, strategy); - } else if (unscheduledUsage instanceof AbstractBeginNode) { - // Only FrameStates can be connected to BeginNodes. - if (!(usage instanceof FrameState)) { - throw new SchedulingError(usage.toString()); - } - if (unscheduledUsage instanceof StartNode) { - currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(unscheduledUsage)); - } else { - // If a FrameState belongs to a BeginNode then it's inputs will be placed at - // the common dominator of all EndNodes. - for (Node pred : unscheduledUsage.cfgPredecessors()) { - currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(pred)); - } - } - } else { - // For the time being, FrameStates can only be connected to NodeWithState. - if (!(usage instanceof FrameState)) { - throw new SchedulingError(usage.toString()); - } - if (!(unscheduledUsage instanceof NodeWithState)) { - throw new SchedulingError(unscheduledUsage.toString()); - } - // Otherwise: Put the input into the same block as the usage. - assignBlockToNode((ValueNode) unscheduledUsage, strategy); - currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(unscheduledUsage)); - } - if (currentBlock == earliestBlock) { - break; - } - } - } else { - // All other types of usages: Put the input into the same block as the usage. - assignBlockToNode((ValueNode) usage, strategy); - currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(usage)); - } - return currentBlock; - } - - private void sortNodesWithinBlocks(StructuredGraph graph, SchedulingStrategy strategy) { - NodeBitMap visited = graph.createNodeBitMap(); - NodeBitMap beforeLastLocation = graph.createNodeBitMap(); - for (Block b : cfg.getBlocks()) { - sortNodesWithinBlock(b, visited, beforeLastLocation, strategy); - assert noDuplicatedNodesInBlock(b) : "duplicated nodes in " + b; - } - } - - private boolean noDuplicatedNodesInBlock(Block b) { - List<ValueNode> list = blockToNodesMap.get(b); - Set<ValueNode> hashset = Node.newSet(list); - return list.size() == hashset.size(); - } - - private void sortNodesWithinBlock(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation, SchedulingStrategy strategy) { - if (visited.isMarked(b.getBeginNode()) || cfg.blockFor(b.getBeginNode()) != b) { - throw new SchedulingError(); - } - if (visited.isMarked(b.getEndNode()) || cfg.blockFor(b.getEndNode()) != b) { - throw new SchedulingError(); - } - - List<ValueNode> sortedInstructions; - assert strategy == SchedulingStrategy.LATEST || strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS; - sortedInstructions = sortNodesWithinBlockLatest(b, visited, beforeLastLocation); - assert filterSchedulableNodes(blockToNodesMap.get(b)).size() == removeProxies(sortedInstructions).size() : "sorted block does not contain the same amount of nodes: " + - filterSchedulableNodes(blockToNodesMap.get(b)) + " vs. " + removeProxies(sortedInstructions); - assert sameOrderForFixedNodes(blockToNodesMap.get(b), sortedInstructions) : "fixed nodes in sorted block are not in the same order"; - blockToNodesMap.put(b, sortedInstructions); - } - - private static List<ValueNode> removeProxies(List<ValueNode> list) { - List<ValueNode> result = new ArrayList<>(); - for (ValueNode n : list) { - if (!(n instanceof ProxyNode)) { - result.add(n); - } - } - return result; - } - - private static List<ValueNode> filterSchedulableNodes(List<ValueNode> list) { - List<ValueNode> result = new ArrayList<>(); - for (ValueNode n : list) { - if (!(n instanceof PhiNode)) { - result.add(n); - } - } - return result; - } - - private static boolean sameOrderForFixedNodes(List<ValueNode> fixed, List<ValueNode> sorted) { - Iterator<ValueNode> fixedIterator = fixed.iterator(); - Iterator<ValueNode> sortedIterator = sorted.iterator(); - - while (sortedIterator.hasNext()) { - ValueNode sortedCurrent = sortedIterator.next(); - if (sortedCurrent instanceof FixedNode) { - if (!(fixedIterator.hasNext() && fixedIterator.next() == sortedCurrent)) { - return false; - } - } - } - - while (fixedIterator.hasNext()) { - if (fixedIterator.next() instanceof FixedNode) { - return false; - } - } - - return true; - } - - private static class SortState { - private Block block; - private NodeBitMap visited; - private NodeBitMap beforeLastLocation; - private List<ValueNode> sortedInstructions; - private List<FloatingReadNode> reads; - - SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<ValueNode> sortedInstructions) { - this.block = block; - this.visited = visited; - this.beforeLastLocation = beforeLastLocation; - this.sortedInstructions = sortedInstructions; - this.reads = null; - } - - public Block currentBlock() { - return block; - } - - void markVisited(Node n) { - visited.mark(n); - } - - boolean isVisited(Node n) { - return visited.isMarked(n); - } - - void markBeforeLastLocation(FloatingReadNode n) { - beforeLastLocation.mark(n); - } - - void clearBeforeLastLocation(FloatingReadNode frn) { - beforeLastLocation.clear(frn); - } - - boolean isBeforeLastLocation(FloatingReadNode n) { - return beforeLastLocation.isMarked(n); - } - - void addRead(FloatingReadNode n) { - if (reads == null) { - reads = new ArrayList<>(); - } - reads.add(n); - } - - int readsSize() { - if (reads == null) { - return 0; - } - return reads.size(); - } - - void removeRead(ValueNode i) { - assert reads != null; - reads.remove(i); - } - - List<FloatingReadNode> readsSnapshot() { - assert reads != null; - return new ArrayList<>(reads); - } - - List<ValueNode> getSortedInstructions() { - return sortedInstructions; - } - - boolean containsInstruction(ValueNode i) { - return sortedInstructions.contains(i); - } - - void addInstruction(ValueNode i) { - sortedInstructions.add(i); - } - } - - /** - * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over - * all inputs. This means that a node is added to the list after all its inputs have been - * processed. - */ - private List<ValueNode> sortNodesWithinBlockLatest(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation) { - SortState state = new SortState(b, visited, beforeLastLocation, new ArrayList<>(blockToNodesMap.get(b).size() + 2)); - List<ValueNode> instructions = blockToNodesMap.get(b); - - for (ValueNode i : instructions) { - if (i instanceof FloatingReadNode) { - FloatingReadNode frn = (FloatingReadNode) i; - if (!frn.location().getLocationIdentity().isImmutable()) { - state.addRead(frn); - if (nodesFor(b).contains(frn.getLastLocationAccess())) { - assert !state.isBeforeLastLocation(frn); - state.markBeforeLastLocation(frn); - } - } - } - } - - for (ValueNode i : instructions) { - addToLatestSorting(i, state); - } - assert state.readsSize() == 0 : "not all reads are scheduled"; - - // Make sure that last node gets really last (i.e. when a frame state successor hangs off - // it). - List<ValueNode> sortedInstructions = state.getSortedInstructions(); - Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1); - if (lastSorted != b.getEndNode()) { - sortedInstructions.remove(b.getEndNode()); - sortedInstructions.add(b.getEndNode()); - } - return sortedInstructions; - } - - private void processKillLocation(Node node, LocationIdentity identity, SortState state) { - for (FloatingReadNode frn : state.readsSnapshot()) { - LocationIdentity readLocation = frn.location().getLocationIdentity(); - assert !readLocation.isImmutable(); - if (frn.getLastLocationAccess() == node) { - assert identity.equals(ANY_LOCATION) || readLocation.equals(identity) || node instanceof MemoryCheckpoint.Multi : "location doesn't match: " + readLocation + ", " + identity; - state.clearBeforeLastLocation(frn); - } else if (!state.isBeforeLastLocation(frn) && (readLocation.equals(identity) || (node != getCFG().graph.start() && ANY_LOCATION.equals(identity)))) { - state.removeRead(frn); - addToLatestSorting(frn, state); - } - } - } - - private void addUnscheduledToLatestSorting(VirtualState state, SortState sortState) { - if (state != null) { - // UnscheduledNodes should never be marked as visited. - if (sortState.isVisited(state)) { - throw new SchedulingError(); - } - - for (Node input : state.inputs()) { - if (input instanceof VirtualState) { - addUnscheduledToLatestSorting((VirtualState) input, sortState); - } else { - addToLatestSorting((ValueNode) input, sortState); - } - } - } - } - - private void addToLatestSorting(ValueNode i, SortState state) { - if (i == null || state.isVisited(i) || cfg.getNodeToBlock().get(i) != state.currentBlock() || i instanceof PhiNode) { - return; - } - - if (i instanceof ProxyNode) { - ProxyNode proxyNode = (ProxyNode) i; - addToLatestSorting(proxyNode.value(), state); - return; - } - - if (i instanceof LoopExitNode) { - LoopExitNode loopExitNode = (LoopExitNode) i; - for (ProxyNode proxy : loopExitNode.proxies()) { - addToLatestSorting(proxy, state); - } - } - - addToLatestSortingHelper(i, state); - } - - private void addToLatestSortingHelper(ValueNode i, SortState state) { - FrameState stateAfter = null; - if (i instanceof StateSplit) { - stateAfter = ((StateSplit) i).stateAfter(); - } - - addInputsToLatestSorting(i, state, stateAfter); - - if (state.readsSize() != 0) { - if (i instanceof MemoryCheckpoint.Single) { - LocationIdentity identity = ((MemoryCheckpoint.Single) i).getLocationIdentity(); - processKillLocation(i, identity, state); - } else if (i instanceof MemoryCheckpoint.Multi) { - for (LocationIdentity identity : ((MemoryCheckpoint.Multi) i).getLocationIdentities()) { - processKillLocation(i, identity, state); - } - } - assert MemoryCheckpoint.TypeAssertion.correctType(i); - } - - addToLatestSorting((ValueNode) i.predecessor(), state); - state.markVisited(i); - addUnscheduledToLatestSorting(stateAfter, state); - - // Now predecessors and inputs are scheduled => we can add this node. - if (!state.containsInstruction(i)) { - state.addInstruction(i); - } - - if (state.readsSize() != 0 && i instanceof FloatingReadNode) { - state.removeRead(i); - } - } - - private void addInputsToLatestSorting(ValueNode i, SortState state, FrameState stateAfter) { - for (Node input : i.inputs()) { - if (input instanceof FrameState) { - if (input != stateAfter) { - addUnscheduledToLatestSorting((FrameState) input, state); - } - } else { - addToLatestSorting((ValueNode) input, state); - } - } - } }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Fri Mar 13 12:27:07 2015 +0100 @@ -147,7 +147,7 @@ @Override protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) { - final List<ValueNode> list = schedule.getBlockToNodesMap().get(block); + final List<Node> list = schedule.getBlockToNodesMap().get(block); /* * A stateAfter is not valid directly after its associated state split, but @@ -155,7 +155,7 @@ * will be checked at the correct position. */ FrameState pendingStateAfter = null; - for (final ValueNode node : list) { + for (final Node node : list) { FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null; if (node instanceof FullInfopointNode) { stateAfter = ((FullInfopointNode) node).getState();
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java Fri Mar 13 12:27:07 2015 +0100 @@ -140,7 +140,7 @@ } } ControlFlowGraph cfg = schedule == null ? null : schedule.getCFG(); - BlockMap<List<ValueNode>> blockToNodes = schedule == null ? null : schedule.getBlockToNodesMap(); + BlockMap<List<Node>> blockToNodes = schedule == null ? null : schedule.getBlockToNodesMap(); List<Block> blocks = cfg == null ? null : cfg.getBlocks(); writeNodes(graph); writeBlocks(blocks, blockToNodes); @@ -468,11 +468,18 @@ } } - private void writeBlocks(List<Block> blocks, BlockMap<List<ValueNode>> blockToNodes) throws IOException { + private void writeBlocks(List<Block> blocks, BlockMap<List<Node>> blockToNodes) throws IOException { if (blocks != null) { + for (Block block : blocks) { + List<Node> nodes = blockToNodes.get(block); + if (nodes == null) { + writeInt(0); + return; + } + } writeInt(blocks.size()); for (Block block : blocks) { - List<ValueNode> nodes = blockToNodes.get(block); + List<Node> nodes = blockToNodes.get(block); writeInt(block.getId()); writeInt(nodes.size()); for (Node node : nodes) {
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Fri Mar 13 12:27:07 2015 +0100 @@ -604,7 +604,7 @@ printedNodes = null; } - private void printScheduledBlock(Block block, List<ValueNode> nodesFor) { + private void printScheduledBlock(Block block, List<Node> nodesFor) { printBlockProlog(block); begin("IR"); out.println("HIR");
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Fri Mar 13 11:26:37 2015 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Fri Mar 13 12:27:07 2015 +0100 @@ -119,7 +119,7 @@ @Override protected boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) { boolean isMarked = usages.isMarked(node); - if (isMarked || node instanceof VirtualizableRoot) { + if ((isMarked && node instanceof ValueNode) || node instanceof VirtualizableRoot) { VirtualUtil.trace("[[%s]] ", node); FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next(); return processNode((ValueNode) node, nextFixedNode, state, effects, isMarked);