Mercurial > hg > truffle
changeset 19824:6b73ce815fc2
Add a new algorithm for latest possible schedule. Fix earliest possible schedule for the case of floating reads. Add scheduling test cases.
line wrap: on
line diff
--- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/LocationIdentity.java Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/LocationIdentity.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java Thu Mar 12 23:24:03 2015 +0100 @@ -324,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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SchedulingTest.java Thu Mar 12 23:24:03 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/LIRGenerationPhase.java Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/NodeLIRBuilder.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchContext.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchPattern.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchRuleRegistry.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchStatement.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java Thu Mar 12 23:24:03 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); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeLIRBuilderTool.java Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeLIRBuilderTool.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeMappableLIRBuilder.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScheduledNodeIterator.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Thu Mar 12 23:24:03 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 @@ -75,96 +75,6 @@ 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; @@ -299,7 +209,7 @@ /** * 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; @@ -317,37 +227,382 @@ scheduleConstants = value; } + private static final boolean USE_NEW_STRATEGY = true; + @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 if (USE_NEW_STRATEGY) { + 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 (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 (selectedStrategy != SchedulingStrategy.EARLIEST && graph.isAfterFloatingReadPhase()) { - blockToKillSet = new BlockMap<>(cfg); + 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); + } + } else { + + earliestCache = graph.createNodeMap(); + blockToNodesMap = new BlockMap<>(cfg); + + if (selectedStrategy != SchedulingStrategy.EARLIEST && graph.isAfterFloatingReadPhase()) { + blockToKillSet = new BlockMap<>(cfg); + } + + assignBlockToNodes(graph, selectedStrategy); + printSchedule("after assign nodes to blocks"); + + sortNodesWithinBlocks(graph, selectedStrategy); + printSchedule("after sorting nodes within blocks"); + } + } + + 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,7 +629,7 @@ nodeToBlock.set(endNode, b); } - processStack(blockToNodes, nodeToBlock, visited, stack); + processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack); // Visit back input edges of loop phis. for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) { @@ -384,7 +639,7 @@ Node node = phi.valueAt(i + loopBegin.forwardEndCount()); if (node != null && !visited.isMarked(node)) { stack.push(node); - processStack(blockToNodes, nodeToBlock, visited, stack); + processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack); } } } @@ -409,16 +664,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(); @@ -479,10 +798,14 @@ 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); } } } @@ -564,7 +887,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; } @@ -575,13 +898,13 @@ /** * 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<>(); + List<Node> nodes = new ArrayList<>(); if (blockToNodesMap.get(block) != null) { throw new SchedulingError(); } @@ -956,8 +1279,8 @@ } private boolean noDuplicatedNodesInBlock(Block b) { - List<ValueNode> list = blockToNodesMap.get(b); - Set<ValueNode> hashset = Node.newSet(list); + List<Node> list = blockToNodesMap.get(b); + Set<Node> hashset = Node.newSet(list); return list.size() == hashset.size(); } @@ -969,7 +1292,7 @@ throw new SchedulingError(); } - List<ValueNode> sortedInstructions; + List<Node> 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: " + @@ -978,9 +1301,9 @@ blockToNodesMap.put(b, sortedInstructions); } - private static List<ValueNode> removeProxies(List<ValueNode> list) { - List<ValueNode> result = new ArrayList<>(); - for (ValueNode n : list) { + private static List<Node> removeProxies(List<Node> list) { + List<Node> result = new ArrayList<>(); + for (Node n : list) { if (!(n instanceof ProxyNode)) { result.add(n); } @@ -988,9 +1311,9 @@ return result; } - private static List<ValueNode> filterSchedulableNodes(List<ValueNode> list) { - List<ValueNode> result = new ArrayList<>(); - for (ValueNode n : list) { + private static List<Node> filterSchedulableNodes(List<Node> list) { + List<Node> result = new ArrayList<>(); + for (Node n : list) { if (!(n instanceof PhiNode)) { result.add(n); } @@ -998,12 +1321,12 @@ return result; } - private static boolean sameOrderForFixedNodes(List<ValueNode> fixed, List<ValueNode> sorted) { - Iterator<ValueNode> fixedIterator = fixed.iterator(); - Iterator<ValueNode> sortedIterator = sorted.iterator(); + private static boolean sameOrderForFixedNodes(List<Node> fixed, List<Node> sorted) { + Iterator<Node> fixedIterator = fixed.iterator(); + Iterator<Node> sortedIterator = sorted.iterator(); while (sortedIterator.hasNext()) { - ValueNode sortedCurrent = sortedIterator.next(); + Node sortedCurrent = sortedIterator.next(); if (sortedCurrent instanceof FixedNode) { if (!(fixedIterator.hasNext() && fixedIterator.next() == sortedCurrent)) { return false; @@ -1024,10 +1347,10 @@ private Block block; private NodeBitMap visited; private NodeBitMap beforeLastLocation; - private List<ValueNode> sortedInstructions; + private List<Node> sortedInstructions; private List<FloatingReadNode> reads; - SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<ValueNode> sortedInstructions) { + SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<Node> sortedInstructions) { this.block = block; this.visited = visited; this.beforeLastLocation = beforeLastLocation; @@ -1073,7 +1396,7 @@ return reads.size(); } - void removeRead(ValueNode i) { + void removeRead(Node i) { assert reads != null; reads.remove(i); } @@ -1083,15 +1406,15 @@ return new ArrayList<>(reads); } - List<ValueNode> getSortedInstructions() { + List<Node> getSortedInstructions() { return sortedInstructions; } - boolean containsInstruction(ValueNode i) { + boolean containsInstruction(Node i) { return sortedInstructions.contains(i); } - void addInstruction(ValueNode i) { + void addInstruction(Node i) { sortedInstructions.add(i); } } @@ -1101,11 +1424,11 @@ * 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) { + private List<Node> 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); + List<Node> instructions = blockToNodesMap.get(b); - for (ValueNode i : instructions) { + for (Node i : instructions) { if (i instanceof FloatingReadNode) { FloatingReadNode frn = (FloatingReadNode) i; if (!frn.location().getLocationIdentity().isImmutable()) { @@ -1118,14 +1441,14 @@ } } - for (ValueNode i : instructions) { + for (Node 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(); + List<Node> sortedInstructions = state.getSortedInstructions(); Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1); if (lastSorted != b.getEndNode()) { sortedInstructions.remove(b.getEndNode()); @@ -1159,13 +1482,13 @@ if (input instanceof VirtualState) { addUnscheduledToLatestSorting((VirtualState) input, sortState); } else { - addToLatestSorting((ValueNode) input, sortState); + addToLatestSorting(input, sortState); } } } } - private void addToLatestSorting(ValueNode i, SortState state) { + private void addToLatestSorting(Node i, SortState state) { if (i == null || state.isVisited(i) || cfg.getNodeToBlock().get(i) != state.currentBlock() || i instanceof PhiNode) { return; } @@ -1186,7 +1509,7 @@ addToLatestSortingHelper(i, state); } - private void addToLatestSortingHelper(ValueNode i, SortState state) { + private void addToLatestSortingHelper(Node i, SortState state) { FrameState stateAfter = null; if (i instanceof StateSplit) { stateAfter = ((StateSplit) i).stateAfter(); @@ -1206,7 +1529,7 @@ assert MemoryCheckpoint.TypeAssertion.correctType(i); } - addToLatestSorting((ValueNode) i.predecessor(), state); + addToLatestSorting(i.predecessor(), state); state.markVisited(i); addUnscheduledToLatestSorting(stateAfter, state); @@ -1220,14 +1543,14 @@ } } - private void addInputsToLatestSorting(ValueNode i, SortState state, FrameState stateAfter) { + private void addInputsToLatestSorting(Node 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); + addToLatestSorting(input, state); } } }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Thu Mar 12 23:24:03 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 Tue Mar 10 22:18:53 2015 -0700 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Thu Mar 12 23:24:03 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);