--- a/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.phases/src/org/graalvm/compiler/phases/schedule/SchedulePhase.java Fri Feb 02 10:37:48 2018 -0500
+++ b/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.phases/src/org/graalvm/compiler/phases/schedule/SchedulePhase.java Fri Feb 02 17:28:17 2018 -0800
@@ -22,14 +22,23 @@
*/
package org.graalvm.compiler.phases.schedule;
+import static org.graalvm.collections.Equivalence.IDENTITY;
+import static org.graalvm.compiler.core.common.GraalOptions.GuardPriorities;
import static org.graalvm.compiler.core.common.GraalOptions.OptScheduleOutOfLoops;
import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Comparator;
+import java.util.EnumMap;
import java.util.Formatter;
+import java.util.Iterator;
import java.util.List;
+import java.util.SortedSet;
+import java.util.TreeSet;
+import java.util.function.Function;
+import org.graalvm.collections.EconomicSet;
import org.graalvm.compiler.core.common.SuppressFBWarnings;
import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
import org.graalvm.compiler.core.common.cfg.BlockMap;
@@ -48,7 +57,6 @@
import org.graalvm.compiler.nodes.ControlSplitNode;
import org.graalvm.compiler.nodes.DeoptimizeNode;
import org.graalvm.compiler.nodes.FixedNode;
-import org.graalvm.compiler.nodes.FixedWithNextNode;
import org.graalvm.compiler.nodes.GuardNode;
import org.graalvm.compiler.nodes.IfNode;
import org.graalvm.compiler.nodes.KillingBeginNode;
@@ -57,6 +65,8 @@
import org.graalvm.compiler.nodes.PhiNode;
import org.graalvm.compiler.nodes.ProxyNode;
import org.graalvm.compiler.nodes.StartNode;
+import org.graalvm.compiler.nodes.StaticDeoptimizingNode;
+import org.graalvm.compiler.nodes.StaticDeoptimizingNode.GuardPriority;
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
@@ -78,10 +88,19 @@
public final class SchedulePhase extends Phase {
public enum SchedulingStrategy {
+ EARLIEST_WITH_GUARD_ORDER,
EARLIEST,
LATEST,
LATEST_OUT_OF_LOOPS,
- FINAL_SCHEDULE
+ FINAL_SCHEDULE;
+
+ public boolean isEarliest() {
+ return this == EARLIEST || this == EARLIEST_WITH_GUARD_ORDER;
+ }
+
+ public boolean isLatest() {
+ return !isEarliest();
+ }
}
private final SchedulingStrategy selectedStrategy;
@@ -164,13 +183,13 @@
this.nodeToBlockMap = currentNodeMap;
this.blockToNodesMap = earliestBlockToNodesMap;
- scheduleEarliestIterative(earliestBlockToNodesMap, currentNodeMap, visited, graph, immutableGraph);
+ scheduleEarliestIterative(earliestBlockToNodesMap, currentNodeMap, visited, graph, immutableGraph, selectedStrategy == SchedulingStrategy.EARLIEST_WITH_GUARD_ORDER);
- if (selectedStrategy != SchedulingStrategy.EARLIEST) {
+ if (!selectedStrategy.isEarliest()) {
// For non-earliest schedules, we need to do a second pass.
BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);
for (Block b : cfg.getBlocks()) {
- latestBlockToNodesMap.put(b, new ArrayList<Node>());
+ latestBlockToNodesMap.put(b, new ArrayList<>());
}
BlockMap<ArrayList<FloatingReadNode>> watchListMap = calcLatestBlocks(selectedStrategy, currentNodeMap, earliestBlockToNodesMap, visited, latestBlockToNodesMap, immutableGraph);
@@ -181,8 +200,8 @@
this.blockToNodesMap = latestBlockToNodesMap;
- cfg.setNodeToBlock(currentNodeMap);
}
+ cfg.setNodeToBlock(currentNodeMap);
graph.setLastSchedule(new ScheduleResult(this.cfg, this.nodeToBlockMap, this.blockToNodesMap));
}
@@ -524,7 +543,6 @@
assert latestBlock != null : currentNode;
if (strategy == SchedulingStrategy.FINAL_SCHEDULE || strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS) {
- assert latestBlock != null;
Block currentBlock = latestBlock;
while (currentBlock.getLoopDepth() > earliestBlock.getLoopDepth() && currentBlock != earliestBlock.getDominator()) {
Block previousCurrentBlock = currentBlock;
@@ -645,7 +663,7 @@
*/
public void add(Node node) {
assert !(node instanceof FixedNode) : node;
- NodeEntry newTail = new NodeEntry(node, null);
+ NodeEntry newTail = new NodeEntry(node);
if (tail == null) {
tail = head = newTail;
} else {
@@ -659,9 +677,18 @@
* Number of nodes in this micro block.
*/
public int getNodeCount() {
+ assert getActualNodeCount() == nodeCount : getActualNodeCount() + " != " + nodeCount;
return nodeCount;
}
+ private int getActualNodeCount() {
+ int count = 0;
+ for (NodeEntry e = head; e != null; e = e.next) {
+ count++;
+ }
+ return count;
+ }
+
/**
* The id of the micro block, with a block always associated with a lower id than its
* successors.
@@ -685,6 +712,7 @@
*/
public void prependChildrenTo(MicroBlock newBlock) {
if (tail != null) {
+ assert head != null;
tail.next = newBlock.head;
newBlock.head = head;
head = tail = null;
@@ -697,6 +725,11 @@
public String toString() {
return String.format("MicroBlock[id=%d]", id);
}
+
+ @Override
+ public int hashCode() {
+ return id;
+ }
}
/**
@@ -706,9 +739,9 @@
private final Node node;
private NodeEntry next;
- NodeEntry(Node node, NodeEntry next) {
+ NodeEntry(Node node) {
this.node = node;
- this.next = next;
+ this.next = null;
}
public NodeEntry getNext() {
@@ -720,7 +753,8 @@
}
}
- private void scheduleEarliestIterative(BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph, boolean immutableGraph) {
+ private void scheduleEarliestIterative(BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph, boolean immutableGraph,
+ boolean withGuardOrder) {
NodeMap<MicroBlock> entries = graph.createNodeMap();
NodeStack stack = new NodeStack();
@@ -729,62 +763,44 @@
MicroBlock startBlock = null;
int nextId = 1;
for (Block b : cfg.reversePostOrder()) {
- FixedNode current = b.getBeginNode();
- while (true) {
+ for (FixedNode current : b.getBeginNode().getBlockNodes()) {
MicroBlock microBlock = new MicroBlock(nextId++);
- entries.put(current, microBlock);
- visited.checkAndMarkInc(current);
-
+ entries.set(current, microBlock);
+ boolean isNew = visited.checkAndMarkInc(current);
+ assert isNew;
if (startBlock == null) {
startBlock = microBlock;
}
-
- // Process inputs of this fixed node.
- for (Node input : current.inputs()) {
- if (entries.get(input) == null) {
- processStack(input, startBlock, entries, visited, stack);
- }
- }
-
- if (current == b.getEndNode()) {
- // Break loop when reaching end node.
- break;
- }
-
- current = ((FixedWithNextNode) current).next();
}
}
- // Now process guards.
- for (GuardNode guardNode : graph.getNodes(GuardNode.TYPE)) {
- if (entries.get(guardNode) == null) {
- processStack(guardNode, startBlock, entries, visited, stack);
+ if (graph.getGuardsStage().allowsFloatingGuards() && graph.getNodes(GuardNode.TYPE).isNotEmpty()) {
+ // Now process guards.
+ if (GuardPriorities.getValue(graph.getOptions()) && withGuardOrder) {
+ EnumMap<GuardPriority, List<GuardNode>> guardsByPriority = new EnumMap<>(GuardPriority.class);
+ for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) {
+ guardsByPriority.computeIfAbsent(guard.computePriority(), p -> new ArrayList<>()).add(guard);
+ }
+ // `EnumMap.values` returns values in "natural" key order
+ for (List<GuardNode> guards : guardsByPriority.values()) {
+ processNodes(visited, entries, stack, startBlock, guards);
+ }
+ GuardOrder.resortGuards(graph, entries, stack);
+ } else {
+ processNodes(visited, entries, stack, startBlock, graph.getNodes(GuardNode.TYPE));
}
+ } else {
+ assert graph.getNodes(GuardNode.TYPE).isEmpty();
}
// Now process inputs of fixed nodes.
for (Block b : cfg.reversePostOrder()) {
- FixedNode current = b.getBeginNode();
- while (true) {
-
- // Process inputs of this fixed node.
- for (Node input : current.inputs()) {
- if (entries.get(input) == null) {
- processStack(input, startBlock, entries, visited, stack);
- }
- }
-
- if (current == b.getEndNode()) {
- // Break loop when reaching end node.
- break;
- }
-
- current = ((FixedWithNextNode) current).next();
+ for (FixedNode current : b.getBeginNode().getBlockNodes()) {
+ processNodes(visited, entries, stack, startBlock, current.inputs());
}
}
if (visited.getCounter() < graph.getNodeCount()) {
-
// Visit back input edges of loop phis.
boolean changed;
boolean unmarkedPhi;
@@ -829,36 +845,29 @@
if (fixedNode instanceof ControlSplitNode) {
ControlSplitNode controlSplitNode = (ControlSplitNode) fixedNode;
MicroBlock endBlock = entries.get(fixedNode);
- MicroBlock primarySuccessor = entries.get(controlSplitNode.getPrimarySuccessor());
- endBlock.prependChildrenTo(primarySuccessor);
+ AbstractBeginNode primarySuccessor = controlSplitNode.getPrimarySuccessor();
+ if (primarySuccessor != null) {
+ endBlock.prependChildrenTo(entries.get(primarySuccessor));
+ } else {
+ assert endBlock.tail == null;
+ }
}
}
- // Initialize with begin nodes
+ // Create lists for each block
for (Block b : cfg.reversePostOrder()) {
-
- FixedNode current = b.getBeginNode();
+ // Count nodes in block
int totalCount = 0;
- while (true) {
-
+ for (FixedNode current : b.getBeginNode().getBlockNodes()) {
MicroBlock microBlock = entries.get(current);
totalCount += microBlock.getNodeCount() + 1;
-
- if (current == b.getEndNode()) {
- // Break loop when reaching end node.
- break;
- }
-
- current = ((FixedWithNextNode) current).next();
}
// Initialize with begin node, it is always the first node.
ArrayList<Node> nodes = new ArrayList<>(totalCount);
blockToNodes.put(b, nodes);
- current = b.getBeginNode();
- while (true) {
-
+ for (FixedNode current : b.getBeginNode().getBlockNodes()) {
MicroBlock microBlock = entries.get(current);
nodeToBlock.set(current, b);
nodes.add(current);
@@ -869,19 +878,20 @@
nodes.add(nextNode);
next = next.getNext();
}
-
- if (current == b.getEndNode()) {
- // Break loop when reaching end node.
- break;
- }
-
- current = ((FixedWithNextNode) current).next();
}
}
assert (!Assertions.detailedAssertionsEnabled(cfg.graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), blockToNodes);
}
+ private static void processNodes(NodeBitMap visited, NodeMap<MicroBlock> entries, NodeStack stack, MicroBlock startBlock, Iterable<? extends Node> nodes) {
+ for (Node node : nodes) {
+ if (entries.get(node) == null) {
+ processStack(node, startBlock, entries, visited, stack);
+ }
+ }
+ }
+
private static void processStackPhi(NodeStack stack, PhiNode phiNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
stack.pop();
if (visited.checkAndMarkInc(phiNode)) {
@@ -944,6 +954,166 @@
}
}
+ private static class GuardOrder {
+ /**
+ * After an earliest schedule, this will re-sort guards to honor their
+ * {@linkplain StaticDeoptimizingNode#computePriority() priority}.
+ *
+ * Note that this only changes the order of nodes within {@linkplain MicroBlock
+ * micro-blocks}, nodes will not be moved from one micro-block to another.
+ */
+ private static void resortGuards(StructuredGraph graph, NodeMap<MicroBlock> entries, NodeStack stack) {
+ assert stack.isEmpty();
+ EconomicSet<MicroBlock> blocksWithGuards = EconomicSet.create(IDENTITY);
+ for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) {
+ MicroBlock block = entries.get(guard);
+ assert block != null : guard + "should already be scheduled to a micro-block";
+ blocksWithGuards.add(block);
+ }
+ assert !blocksWithGuards.isEmpty();
+ NodeMap<GuardPriority> priorities = graph.createNodeMap();
+ NodeBitMap blockNodes = graph.createNodeBitMap();
+ for (MicroBlock block : blocksWithGuards) {
+ MicroBlock newBlock = resortGuards(block, stack, blockNodes, priorities);
+ assert stack.isEmpty();
+ assert blockNodes.isEmpty();
+ if (newBlock != null) {
+ assert block.getNodeCount() == newBlock.getNodeCount();
+ block.head = newBlock.head;
+ block.tail = newBlock.tail;
+ }
+ }
+ }
+
+ /**
+ * This resorts guards within one micro-block.
+ *
+ * {@code stack}, {@code blockNodes} and {@code priorities} are just temporary
+ * data-structures which are allocated once by the callers of this method. They should
+ * be in their "initial"/"empty" state when calling this method and when it returns.
+ */
+ private static MicroBlock resortGuards(MicroBlock block, NodeStack stack, NodeBitMap blockNodes, NodeMap<GuardPriority> priorities) {
+ if (!propagatePriority(block, stack, priorities, blockNodes)) {
+ return null;
+ }
+
+ Function<GuardNode, GuardPriority> transitiveGuardPriorityGetter = priorities::get;
+ Comparator<GuardNode> globalGuardPriorityComparator = Comparator.comparing(transitiveGuardPriorityGetter).thenComparing(GuardNode::computePriority).thenComparingInt(Node::hashCode);
+
+ SortedSet<GuardNode> availableGuards = new TreeSet<>(globalGuardPriorityComparator);
+ MicroBlock newBlock = new MicroBlock(block.getId());
+
+ NodeBitMap sorted = blockNodes;
+ sorted.invert();
+
+ for (NodeEntry e = block.head; e != null; e = e.next) {
+ checkIfAvailable(e.node, stack, sorted, newBlock, availableGuards, false);
+ }
+ do {
+ while (!stack.isEmpty()) {
+ checkIfAvailable(stack.pop(), stack, sorted, newBlock, availableGuards, true);
+ }
+ Iterator<GuardNode> iterator = availableGuards.iterator();
+ if (iterator.hasNext()) {
+ addNodeToResort(iterator.next(), stack, sorted, newBlock, true);
+ iterator.remove();
+ }
+ } while (!stack.isEmpty() || !availableGuards.isEmpty());
+
+ blockNodes.clearAll();
+ return newBlock;
+ }
+
+ /**
+ * This checks if {@code n} can be scheduled, if it is the case, it schedules it now by
+ * calling {@link #addNodeToResort(Node, NodeStack, NodeBitMap, MicroBlock, boolean)}.
+ */
+ private static void checkIfAvailable(Node n, NodeStack stack, NodeBitMap sorted, Instance.MicroBlock newBlock, SortedSet<GuardNode> availableGuardNodes, boolean pushUsages) {
+ if (sorted.isMarked(n)) {
+ return;
+ }
+ for (Node in : n.inputs()) {
+ if (!sorted.isMarked(in)) {
+ return;
+ }
+ }
+ if (n instanceof GuardNode) {
+ availableGuardNodes.add((GuardNode) n);
+ } else {
+ addNodeToResort(n, stack, sorted, newBlock, pushUsages);
+ }
+ }
+
+ /**
+ * Add a node to the re-sorted micro-block. This also pushes nodes that need to be
+ * (re-)examined on the stack.
+ */
+ private static void addNodeToResort(Node n, NodeStack stack, NodeBitMap sorted, MicroBlock newBlock, boolean pushUsages) {
+ sorted.mark(n);
+ newBlock.add(n);
+ if (pushUsages) {
+ for (Node u : n.usages()) {
+ if (!sorted.isMarked(u)) {
+ stack.push(u);
+ }
+ }
+ }
+ }
+
+ /**
+ * This fills in a map of transitive priorities ({@code priorities}). It also marks the
+ * nodes from this micro-block in {@code blockNodes}.
+ *
+ * The transitive priority of a guard is the highest of its priority and the priority of
+ * the guards that depend on it (transitively).
+ *
+ * This method returns {@code false} if no re-ordering is necessary in this micro-block.
+ */
+ private static boolean propagatePriority(MicroBlock block, NodeStack stack, NodeMap<GuardPriority> priorities, NodeBitMap blockNodes) {
+ assert stack.isEmpty();
+ assert blockNodes.isEmpty();
+ GuardPriority lowestPriority = GuardPriority.highest();
+ for (NodeEntry e = block.head; e != null; e = e.next) {
+ blockNodes.mark(e.node);
+ if (e.node instanceof GuardNode) {
+ GuardNode guard = (GuardNode) e.node;
+ GuardPriority priority = guard.computePriority();
+ if (lowestPriority != null) {
+ if (priority.isLowerPriorityThan(lowestPriority)) {
+ lowestPriority = priority;
+ } else if (priority.isHigherPriorityThan(lowestPriority)) {
+ lowestPriority = null;
+ }
+ }
+ stack.push(guard);
+ priorities.set(guard, priority);
+ }
+ }
+ if (lowestPriority != null) {
+ stack.clear();
+ blockNodes.clearAll();
+ return false;
+ }
+
+ do {
+ Node current = stack.pop();
+ assert blockNodes.isMarked(current);
+ GuardPriority priority = priorities.get(current);
+ for (Node input : current.inputs()) {
+ if (!blockNodes.isMarked(input)) {
+ continue;
+ }
+ GuardPriority inputPriority = priorities.get(input);
+ if (inputPriority == null || inputPriority.isLowerPriorityThan(priority)) {
+ priorities.set(input, priority);
+ stack.push(input);
+ }
+ }
+ } while (!stack.isEmpty());
+ return true;
+ }
+ }
+
/**
* Processes the inputs of given block. Pushes unprocessed inputs onto the stack. Returns
* null if there were still unprocessed inputs, otherwise returns the earliest block given
@@ -960,7 +1130,7 @@
if (inputBlock == null) {
earliestBlock = null;
stack.push(input);
- } else if (earliestBlock != null && inputBlock.getId() >= earliestBlock.getId()) {
+ } else if (earliestBlock != null && inputBlock.getId() > earliestBlock.getId()) {
earliestBlock = inputBlock;
}
}