13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.phases.schedule;
24
25 import static org.graalvm.compiler.core.common.GraalOptions.OptScheduleOutOfLoops;
26 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;
27
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.Formatter;
31 import java.util.List;
32
33 import org.graalvm.compiler.core.common.GraalOptions;
34 import org.graalvm.compiler.core.common.SuppressFBWarnings;
35 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
36 import org.graalvm.compiler.core.common.cfg.BlockMap;
37 import org.graalvm.compiler.debug.Assertions;
38 import org.graalvm.compiler.graph.Graph.NodeEvent;
39 import org.graalvm.compiler.graph.Graph.NodeEventListener;
40 import org.graalvm.compiler.graph.Graph.NodeEventScope;
41 import org.graalvm.compiler.graph.Node;
42 import org.graalvm.compiler.graph.NodeBitMap;
43 import org.graalvm.compiler.graph.NodeMap;
44 import org.graalvm.compiler.graph.NodeStack;
45 import org.graalvm.compiler.nodes.AbstractBeginNode;
46 import org.graalvm.compiler.nodes.AbstractEndNode;
47 import org.graalvm.compiler.nodes.AbstractMergeNode;
48 import org.graalvm.compiler.nodes.ControlSinkNode;
49 import org.graalvm.compiler.nodes.ControlSplitNode;
50 import org.graalvm.compiler.nodes.DeoptimizeNode;
51 import org.graalvm.compiler.nodes.FixedNode;
52 import org.graalvm.compiler.nodes.FixedWithNextNode;
53 import org.graalvm.compiler.nodes.GuardNode;
90 private final boolean immutableGraph;
91
92 public SchedulePhase(OptionValues options) {
93 this(false, options);
94 }
95
96 public SchedulePhase(boolean immutableGraph, OptionValues options) {
97 this(OptScheduleOutOfLoops.getValue(options) ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST, immutableGraph);
98 }
99
100 public SchedulePhase(SchedulingStrategy strategy) {
101 this(strategy, false);
102 }
103
104 public SchedulePhase(SchedulingStrategy strategy, boolean immutableGraph) {
105 this.selectedStrategy = strategy;
106 this.immutableGraph = immutableGraph;
107 }
108
109 private NodeEventScope verifyImmutableGraph(StructuredGraph graph) {
110 if (immutableGraph && Assertions.ENABLED) {
111 return graph.trackNodeEvents(new NodeEventListener() {
112 @Override
113 public void event(NodeEvent e, Node node) {
114 assert false : "graph changed: " + e + " on node " + node;
115 }
116 });
117 } else {
118 return null;
119 }
120 }
121
122 @Override
123 @SuppressWarnings("try")
124 protected void run(StructuredGraph graph) {
125 try (NodeEventScope scope = verifyImmutableGraph(graph)) {
126 Instance inst = new Instance();
127 inst.run(graph, selectedStrategy, immutableGraph);
128 }
129 }
130
161
162 NodeMap<Block> currentNodeMap = graph.createNodeMap();
163 NodeBitMap visited = graph.createNodeBitMap();
164 BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg);
165 this.nodeToBlockMap = currentNodeMap;
166 this.blockToNodesMap = earliestBlockToNodesMap;
167
168 scheduleEarliestIterative(earliestBlockToNodesMap, currentNodeMap, visited, graph, immutableGraph);
169
170 if (selectedStrategy != SchedulingStrategy.EARLIEST) {
171 // For non-earliest schedules, we need to do a second pass.
172 BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);
173 for (Block b : cfg.getBlocks()) {
174 latestBlockToNodesMap.put(b, new ArrayList<Node>());
175 }
176
177 BlockMap<ArrayList<FloatingReadNode>> watchListMap = calcLatestBlocks(selectedStrategy, currentNodeMap, earliestBlockToNodesMap, visited, latestBlockToNodesMap, immutableGraph);
178 sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
179
180 assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap);
181 assert (!GraalOptions.DetailedAsserts.getValue(graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), latestBlockToNodesMap);
182
183 this.blockToNodesMap = latestBlockToNodesMap;
184
185 cfg.setNodeToBlock(currentNodeMap);
186 }
187
188 graph.setLastSchedule(new ScheduleResult(this.cfg, this.nodeToBlockMap, this.blockToNodesMap));
189 }
190
191 @SuppressFBWarnings(value = "RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE", justification = "false positive found by findbugs")
192 private BlockMap<ArrayList<FloatingReadNode>> calcLatestBlocks(SchedulingStrategy strategy, NodeMap<Block> currentNodeMap, BlockMap<List<Node>> earliestBlockToNodesMap, NodeBitMap visited,
193 BlockMap<List<Node>> latestBlockToNodesMap, boolean immutableGraph) {
194 BlockMap<ArrayList<FloatingReadNode>> watchListMap = new BlockMap<>(cfg);
195 Block[] reversePostOrder = cfg.reversePostOrder();
196 for (int j = reversePostOrder.length - 1; j >= 0; --j) {
197 Block currentBlock = reversePostOrder[j];
198 List<Node> blockToNodes = earliestBlockToNodesMap.get(currentBlock);
199 LocationSet killed = null;
200 int previousIndex = blockToNodes.size();
201 for (int i = blockToNodes.size() - 1; i >= 0; --i) {
863 MicroBlock microBlock = entries.get(current);
864 nodeToBlock.set(current, b);
865 nodes.add(current);
866 NodeEntry next = microBlock.getFirstNode();
867 while (next != null) {
868 Node nextNode = next.getNode();
869 nodeToBlock.set(nextNode, b);
870 nodes.add(nextNode);
871 next = next.getNext();
872 }
873
874 if (current == b.getEndNode()) {
875 // Break loop when reaching end node.
876 break;
877 }
878
879 current = ((FixedWithNextNode) current).next();
880 }
881 }
882
883 assert (!GraalOptions.DetailedAsserts.getValue(cfg.graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), blockToNodes);
884 }
885
886 private static void processStackPhi(NodeStack stack, PhiNode phiNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
887 stack.pop();
888 if (visited.checkAndMarkInc(phiNode)) {
889 MicroBlock mergeBlock = nodeToBlock.get(phiNode.merge());
890 assert mergeBlock != null : phiNode;
891 nodeToBlock.set(phiNode, mergeBlock);
892 AbstractMergeNode merge = phiNode.merge();
893 for (int i = 0; i < merge.forwardEndCount(); ++i) {
894 Node input = phiNode.valueAt(i);
895 if (input != null && nodeToBlock.get(input) == null) {
896 stack.push(input);
897 }
898 }
899 }
900 }
901
902 private static void processStackProxy(NodeStack stack, ProxyNode proxyNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
903 stack.pop();
|
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.phases.schedule;
24
25 import static org.graalvm.compiler.core.common.GraalOptions.OptScheduleOutOfLoops;
26 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;
27
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.Formatter;
31 import java.util.List;
32
33 import org.graalvm.compiler.core.common.SuppressFBWarnings;
34 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
35 import org.graalvm.compiler.core.common.cfg.BlockMap;
36 import org.graalvm.compiler.debug.Assertions;
37 import org.graalvm.compiler.graph.Graph.NodeEvent;
38 import org.graalvm.compiler.graph.Graph.NodeEventListener;
39 import org.graalvm.compiler.graph.Graph.NodeEventScope;
40 import org.graalvm.compiler.graph.Node;
41 import org.graalvm.compiler.graph.NodeBitMap;
42 import org.graalvm.compiler.graph.NodeMap;
43 import org.graalvm.compiler.graph.NodeStack;
44 import org.graalvm.compiler.nodes.AbstractBeginNode;
45 import org.graalvm.compiler.nodes.AbstractEndNode;
46 import org.graalvm.compiler.nodes.AbstractMergeNode;
47 import org.graalvm.compiler.nodes.ControlSinkNode;
48 import org.graalvm.compiler.nodes.ControlSplitNode;
49 import org.graalvm.compiler.nodes.DeoptimizeNode;
50 import org.graalvm.compiler.nodes.FixedNode;
51 import org.graalvm.compiler.nodes.FixedWithNextNode;
52 import org.graalvm.compiler.nodes.GuardNode;
89 private final boolean immutableGraph;
90
91 public SchedulePhase(OptionValues options) {
92 this(false, options);
93 }
94
95 public SchedulePhase(boolean immutableGraph, OptionValues options) {
96 this(OptScheduleOutOfLoops.getValue(options) ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST, immutableGraph);
97 }
98
99 public SchedulePhase(SchedulingStrategy strategy) {
100 this(strategy, false);
101 }
102
103 public SchedulePhase(SchedulingStrategy strategy, boolean immutableGraph) {
104 this.selectedStrategy = strategy;
105 this.immutableGraph = immutableGraph;
106 }
107
108 private NodeEventScope verifyImmutableGraph(StructuredGraph graph) {
109 if (immutableGraph && Assertions.assertionsEnabled()) {
110 return graph.trackNodeEvents(new NodeEventListener() {
111 @Override
112 public void event(NodeEvent e, Node node) {
113 assert false : "graph changed: " + e + " on node " + node;
114 }
115 });
116 } else {
117 return null;
118 }
119 }
120
121 @Override
122 @SuppressWarnings("try")
123 protected void run(StructuredGraph graph) {
124 try (NodeEventScope scope = verifyImmutableGraph(graph)) {
125 Instance inst = new Instance();
126 inst.run(graph, selectedStrategy, immutableGraph);
127 }
128 }
129
160
161 NodeMap<Block> currentNodeMap = graph.createNodeMap();
162 NodeBitMap visited = graph.createNodeBitMap();
163 BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg);
164 this.nodeToBlockMap = currentNodeMap;
165 this.blockToNodesMap = earliestBlockToNodesMap;
166
167 scheduleEarliestIterative(earliestBlockToNodesMap, currentNodeMap, visited, graph, immutableGraph);
168
169 if (selectedStrategy != SchedulingStrategy.EARLIEST) {
170 // For non-earliest schedules, we need to do a second pass.
171 BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);
172 for (Block b : cfg.getBlocks()) {
173 latestBlockToNodesMap.put(b, new ArrayList<Node>());
174 }
175
176 BlockMap<ArrayList<FloatingReadNode>> watchListMap = calcLatestBlocks(selectedStrategy, currentNodeMap, earliestBlockToNodesMap, visited, latestBlockToNodesMap, immutableGraph);
177 sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
178
179 assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap);
180 assert (!Assertions.detailedAssertionsEnabled(graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), latestBlockToNodesMap);
181
182 this.blockToNodesMap = latestBlockToNodesMap;
183
184 cfg.setNodeToBlock(currentNodeMap);
185 }
186
187 graph.setLastSchedule(new ScheduleResult(this.cfg, this.nodeToBlockMap, this.blockToNodesMap));
188 }
189
190 @SuppressFBWarnings(value = "RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE", justification = "false positive found by findbugs")
191 private BlockMap<ArrayList<FloatingReadNode>> calcLatestBlocks(SchedulingStrategy strategy, NodeMap<Block> currentNodeMap, BlockMap<List<Node>> earliestBlockToNodesMap, NodeBitMap visited,
192 BlockMap<List<Node>> latestBlockToNodesMap, boolean immutableGraph) {
193 BlockMap<ArrayList<FloatingReadNode>> watchListMap = new BlockMap<>(cfg);
194 Block[] reversePostOrder = cfg.reversePostOrder();
195 for (int j = reversePostOrder.length - 1; j >= 0; --j) {
196 Block currentBlock = reversePostOrder[j];
197 List<Node> blockToNodes = earliestBlockToNodesMap.get(currentBlock);
198 LocationSet killed = null;
199 int previousIndex = blockToNodes.size();
200 for (int i = blockToNodes.size() - 1; i >= 0; --i) {
862 MicroBlock microBlock = entries.get(current);
863 nodeToBlock.set(current, b);
864 nodes.add(current);
865 NodeEntry next = microBlock.getFirstNode();
866 while (next != null) {
867 Node nextNode = next.getNode();
868 nodeToBlock.set(nextNode, b);
869 nodes.add(nextNode);
870 next = next.getNext();
871 }
872
873 if (current == b.getEndNode()) {
874 // Break loop when reaching end node.
875 break;
876 }
877
878 current = ((FixedWithNextNode) current).next();
879 }
880 }
881
882 assert (!Assertions.detailedAssertionsEnabled(cfg.graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), blockToNodes);
883 }
884
885 private static void processStackPhi(NodeStack stack, PhiNode phiNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
886 stack.pop();
887 if (visited.checkAndMarkInc(phiNode)) {
888 MicroBlock mergeBlock = nodeToBlock.get(phiNode.merge());
889 assert mergeBlock != null : phiNode;
890 nodeToBlock.set(phiNode, mergeBlock);
891 AbstractMergeNode merge = phiNode.merge();
892 for (int i = 0; i < merge.forwardEndCount(); ++i) {
893 Node input = phiNode.valueAt(i);
894 if (input != null && nodeToBlock.get(input) == null) {
895 stack.push(input);
896 }
897 }
898 }
899 }
900
901 private static void processStackProxy(NodeStack stack, ProxyNode proxyNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
902 stack.pop();
|