jdk-sandbox: comparison src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.phases/src/org/graalvm/compiler/phases/schedule/SchedulePhase.java

equal deleted inserted replaced

-:5bce1b7e7800
+:47f19ff9903c
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */
 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;
 import org.graalvm.compiler.debug.Assertions;
 import org.graalvm.compiler.graph.Graph.NodeEvent;
 import org.graalvm.compiler.nodes.AbstractMergeNode;
 import org.graalvm.compiler.nodes.ControlSinkNode;
 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;
 import org.graalvm.compiler.nodes.LoopBeginNode;
 import org.graalvm.compiler.nodes.LoopExitNode;
 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;
 import org.graalvm.compiler.nodes.ValueNode;
 import org.graalvm.compiler.nodes.VirtualState;
 import org.graalvm.word.LocationIdentity;
 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;
 private final boolean immutableGraph;
 NodeBitMap visited = graph.createNodeBitMap();
 BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg);
 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);
 sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
 assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap);
 assert (!Assertions.detailedAssertionsEnabled(graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), latestBlockToNodesMap);
 this.blockToNodesMap = latestBlockToNodesMap;
-cfg.setNodeToBlock(currentNodeMap);
+}
-}
+cfg.setNodeToBlock(currentNodeMap);
 graph.setLastSchedule(new ScheduleResult(this.cfg, this.nodeToBlockMap, this.blockToNodesMap));
 }
 @SuppressFBWarnings(value = "RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE", justification = "false positive found by findbugs")
 }
 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;
 currentBlock = currentBlock.getDominator();
 if (previousCurrentBlock.isLoopHeader()) {
 /**
 * Adds a new floating node into the micro block.
 */
 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 {
 tail.next = newTail;
 tail = newTail;
 /**
 * 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.
 *
 * @param newBlock the new block for the nodes
 */
 public void prependChildrenTo(MicroBlock newBlock) {
 if (tail != null) {
+assert head != null;
 tail.next = newBlock.head;
 newBlock.head = head;
 head = tail = null;
 newBlock.nodeCount += nodeCount;
 nodeCount = 0;
 }
 @Override
 public String toString() {
 return String.format("MicroBlock[id=%d]", id);
+}
+@Override
+public int hashCode() {
+return id;
 }
 }
 /**
 * Entry in the linked list of nodes.
 */
 private static class NodeEntry {
 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() {
 return next;
 }
 public Node getNode() {
 return node;
 }
 }
-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();
 // Initialize with fixed nodes.
 MicroBlock startBlock = null;
 int nextId = 1;
 for (Block b : cfg.reversePostOrder()) {
-FixedNode current = b.getBeginNode();
+for (FixedNode current : b.getBeginNode().getBlockNodes()) {
-while (true) {
 MicroBlock microBlock = new MicroBlock(nextId++);
-entries.put(current, microBlock);
+entries.set(current, microBlock);
-visited.checkAndMarkInc(current);
+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) {
+if (graph.getGuardsStage().allowsFloatingGuards() && graph.getNodes(GuardNode.TYPE).isNotEmpty()) {
-processStack(input, startBlock, entries, visited, stack);
+// 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)) {
-if (current == b.getEndNode()) {
+guardsByPriority.computeIfAbsent(guard.computePriority(), p -> new ArrayList<>()).add(guard);
-// Break loop when reaching end node.
+}
-break;
+// `EnumMap.values` returns values in "natural" key order
-}
+for (List<GuardNode> guards : guardsByPriority.values()) {
+processNodes(visited, entries, stack, startBlock, guards);
-current = ((FixedWithNextNode) current).next();
+}
-}
+GuardOrder.resortGuards(graph, entries, stack);
-}
+} else {
+processNodes(visited, entries, stack, startBlock, graph.getNodes(GuardNode.TYPE));
-// Now process guards.
+}
-for (GuardNode guardNode : graph.getNodes(GuardNode.TYPE)) {
+} else {
-if (entries.get(guardNode) == null) {
+assert graph.getNodes(GuardNode.TYPE).isEmpty();
-processStack(guardNode, startBlock, entries, visited, stack);
-}
 }
 // Now process inputs of fixed nodes.
 for (Block b : cfg.reversePostOrder()) {
-FixedNode current = b.getBeginNode();
+for (FixedNode current : b.getBeginNode().getBlockNodes()) {
-while (true) {
+processNodes(visited, entries, stack, startBlock, current.inputs());
-// 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();
 }
 }
 if (visited.getCounter() < graph.getNodeCount()) {
 // Visit back input edges of loop phis.
 boolean changed;
 boolean unmarkedPhi;
 do {
 changed = false;
 for (Block b : cfg.reversePostOrder()) {
 FixedNode fixedNode = b.getEndNode();
 if (fixedNode instanceof ControlSplitNode) {
 ControlSplitNode controlSplitNode = (ControlSplitNode) fixedNode;
 MicroBlock endBlock = entries.get(fixedNode);
-MicroBlock primarySuccessor = entries.get(controlSplitNode.getPrimarySuccessor());
+AbstractBeginNode primarySuccessor = controlSplitNode.getPrimarySuccessor();
-endBlock.prependChildrenTo(primarySuccessor);
+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()) {
+// Count nodes in block
-FixedNode current = b.getBeginNode();
 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();
+for (FixedNode current : b.getBeginNode().getBlockNodes()) {
-while (true) {
 MicroBlock microBlock = entries.get(current);
 nodeToBlock.set(current, b);
 nodes.add(current);
 NodeEntry next = microBlock.getFirstNode();
 while (next != null) {
 Node nextNode = next.getNode();
 nodeToBlock.set(nextNode, b);
 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)) {
 }
 current = stack.peek();
 }
 }
+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
 * node can be scheduled in.
 */
 for (Node input : current.inputs()) {
 MicroBlock inputBlock = nodeToBlock.get(input);
 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;
 }
 }
 return earliestBlock;
 }

changeset 48861	47f19ff9903c
parent 47798	9fe9292f5931
child 49873	26ebfe8ce852