Mercurial > hg > graal-jvmci-8

comparison graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java @ 6525:2c913b643422

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rename packages in graal.phases to match project name
author Doug Simon <doug.simon@oracle.com>
date Sun, 07 Oct 2012 14:15:44 +0200
parents graal/com.oracle.graal.phases/src/com/oracle/graal/compiler/schedule/SchedulePhase.java@c612043278e9
children ee651c726397
comparison
equal deleted inserted replaced
6524:a206e077ffc8 6525:2c913b643422
1 /*
2 * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
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 com.oracle.graal.phases.schedule;
24
25 import java.util.*;
26
27 import com.oracle.graal.debug.*;
28 import com.oracle.graal.graph.*;
29 import com.oracle.graal.graph.Node.Verbosity;
30 import com.oracle.graal.lir.cfg.*;
31 import com.oracle.graal.nodes.*;
32 import com.oracle.graal.nodes.extended.*;
33 import com.oracle.graal.nodes.virtual.*;
34 import com.oracle.graal.phases.*;
35 import com.oracle.graal.phases.phases.*;
36
37 public class SchedulePhase extends Phase {
38 private ControlFlowGraph cfg;
39 private NodeMap<Block> earliestCache;
40
41 /**
42 * Map from blocks to the nodes in each block.
43 */
44 private BlockMap<List<ScheduledNode>> blockToNodesMap;
45
46 public SchedulePhase() {
47 super("Schedule");
48 }
49
50 @Override
51 protected void run(StructuredGraph graph) {
52 cfg = ControlFlowGraph.compute(graph, true, true, true, false);
53 earliestCache = graph.createNodeMap();
54 blockToNodesMap = new BlockMap<>(cfg);
55
56 assignBlockToNodes(graph);
57 sortNodesWithinBlocks(graph);
58 }
59
60 /**
61 * Sets {@link ScheduledNode#scheduledNext} on all scheduled nodes in all blocks using the scheduling built by @link {@link #run(StructuredGraph)}.
62 * This method should thus only be called when run has been successfully executed.
63 */
64 public void scheduleGraph() {
65 assert blockToNodesMap != null : "cannot set scheduledNext before run has been executed";
66 for (Block block : cfg.getBlocks()) {
67 List<ScheduledNode> nodeList = blockToNodesMap.get(block);
68 ScheduledNode last = null;
69 for (ScheduledNode node : nodeList) {
70 if (last != null) {
71 last.setScheduledNext(node);
72 }
73 last = node;
74 }
75 }
76 }
77
78 public ControlFlowGraph getCFG() {
79 return cfg;
80 }
81
82 /**
83 * Gets the map from each block to the nodes in the block.
84 */
85 public BlockMap<List<ScheduledNode>> getBlockToNodesMap() {
86 return blockToNodesMap;
87 }
88
89 /**
90 * Gets the nodes in a given block.
91 */
92 public List<ScheduledNode> nodesFor(Block block) {
93 return blockToNodesMap.get(block);
94 }
95
96 private void assignBlockToNodes(StructuredGraph graph) {
97 for (Block block : cfg.getBlocks()) {
98 List<ScheduledNode> nodes = new ArrayList<>();
99 assert blockToNodesMap.get(block) == null;
100 blockToNodesMap.put(block, nodes);
101 for (FixedNode node : block.getNodes()) {
102 nodes.add(node);
103 }
104 }
105
106 for (Node n : graph.getNodes()) {
107 if (n instanceof ScheduledNode) {
108 assignBlockToNode((ScheduledNode) n);
109 }
110 }
111 }
112
113 /**
114 * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are already assigned to a block.
115 */
116 private void assignBlockToNode(ScheduledNode node) {
117 assert !node.isDeleted();
118
119 Block prevBlock = cfg.getNodeToBlock().get(node);
120 if (prevBlock != null) {
121 return;
122 }
123 // PhiNodes and FixedNodes should already have been placed in blocks by ControlFlowGraph.identifyBlocks
124 assert !(node instanceof PhiNode) : node;
125 assert !(node instanceof FixedNode) : node;
126 // if in CFG, schedule at the latest position possible in the outermost loop possible
127 Block latestBlock = latestBlock(node);
128 Block block;
129 if (latestBlock == null) {
130 block = earliestBlock(node);
131 } else if (GraalOptions.ScheduleOutOfLoops && !(node instanceof VirtualObjectNode)) {
132 Block earliestBlock = earliestBlock(node);
133 block = scheduleOutOfLoops(node, latestBlock, earliestBlock);
134 assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + node + " (" + earliestBlock + " needs to dominate " + block + ")";
135 } else {
136 block = latestBlock;
137 }
138 cfg.getNodeToBlock().set(node, block);
139 blockToNodesMap.get(block).add(node);
140 }
141
142 /**
143 * Calculates the last block that the given node could be scheduled in, i.e., the common dominator of all usages.
144 * To do so all usages are also assigned to blocks.
145 */
146 private Block latestBlock(ScheduledNode node) {
147 CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null);
148 for (Node succ : node.successors().nonNull()) {
149 assert cfg.getNodeToBlock().get(succ) != null;
150 cdbc.apply(cfg.getNodeToBlock().get(succ));
151 }
152 ensureScheduledUsages(node);
153 for (Node usage : node.usages()) {
154 blocksForUsage(node, usage, cdbc);
155 }
156 return cdbc.block;
157 }
158
159 /**
160 * A closure that will calculate the common dominator of all blocks passed to its {@link #apply(Block)} method.
161 */
162 private static class CommonDominatorBlockClosure implements BlockClosure {
163 public Block block;
164 public CommonDominatorBlockClosure(Block block) {
165 this.block = block;
166 }
167 @Override
168 public void apply(Block newBlock) {
169 this.block = getCommonDominator(this.block, newBlock);
170 }
171 }
172
173 /**
174 * Determines the earliest block in which the given node can be scheduled.
175 */
176 private Block earliestBlock(Node node) {
177 Block earliest = cfg.getNodeToBlock().get(node);
178 if (earliest != null) {
179 return earliest;
180 }
181 earliest = earliestCache.get(node);
182 if (earliest != null) {
183 return earliest;
184 }
185 /*
186 * All inputs must be in a dominating block, otherwise the graph cannot be scheduled. This implies that the
187 * inputs' blocks have a total ordering via their dominance relation. So in order to find the earliest block
188 * placement for this node we need to find the input block that is dominated by all other input blocks.
189 *
190 * While iterating over the inputs a set of dominator blocks of the current earliest placement is maintained.
191 * When the block of an input is not within this set, it becomes the current earliest placement and the list of
192 * dominator blocks is updated.
193 */
194 BitSet dominators = new BitSet(cfg.getBlocks().length);
195
196 assert node.predecessor() == null;
197 for (Node input : node.inputs().nonNull()) {
198 assert input instanceof ValueNode;
199 Block inputEarliest = earliestBlock(input);
200 if (!dominators.get(inputEarliest.getId())) {
201 earliest = inputEarliest;
202 do {
203 dominators.set(inputEarliest.getId());
204 inputEarliest = inputEarliest.getDominator();
205 } while(inputEarliest != null && !dominators.get(inputEarliest.getId()));
206 }
207 }
208 if (earliest == null) {
209 earliest = cfg.getStartBlock();
210 }
211 earliestCache.set(node, earliest);
212 return earliest;
213 }
214
215
216 private static Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) {
217 assert latestBlock != null : "no latest : " + n;
218 Block cur = latestBlock;
219 Block result = latestBlock;
220 while (cur.getLoop() != null && cur != earliest && cur.getDominator() != null) {
221 Block dom = cur.getDominator();
222 if (dom.getLoopDepth() < result.getLoopDepth()) {
223 result = dom;
224 }
225 cur = dom;
226 }
227 return result;
228 }
229
230 /**
231 * Passes all blocks that a specific usage of a node is in to a given closure.
232 * This is more complex than just taking the usage's block because of of PhiNodes and FrameStates.
233 *
234 * @param node the node that needs to be scheduled
235 * @param usage the usage whose blocks need to be considered
236 * @param closure the closure that will be called for each block
237 */
238 private void blocksForUsage(ScheduledNode node, Node usage, BlockClosure closure) {
239 assert !(node instanceof PhiNode);
240
241 if (usage instanceof PhiNode) {
242 // An input to a PhiNode is used at the end of the predecessor block that corresponds to the PhiNode input.
243 // One PhiNode can use an input multiple times, the closure will be called for each usage.
244 PhiNode phi = (PhiNode) usage;
245 MergeNode merge = phi.merge();
246 Block mergeBlock = cfg.getNodeToBlock().get(merge);
247 assert mergeBlock != null : "no block for merge " + merge.toString(Verbosity.Id);
248 for (int i = 0; i < phi.valueCount(); ++i) {
249 if (phi.valueAt(i) == node) {
250 if (mergeBlock.getPredecessors().size() <= i) {
251 TTY.println(merge.toString());
252 TTY.println(phi.toString());
253 TTY.println(merge.cfgPredecessors().toString());
254 TTY.println(mergeBlock.getPredecessors().toString());
255 TTY.println(phi.inputs().toString());
256 TTY.println("value count: " + phi.valueCount());
257 }
258 closure.apply(mergeBlock.getPredecessors().get(i));
259 }
260 }
261 } else if (usage instanceof VirtualState) {
262 // The following logic does not work if node is a PhiNode, but this method is never called for PhiNodes.
263 for (Node unscheduledUsage : usage.usages()) {
264 if (unscheduledUsage instanceof VirtualState) {
265 // If a FrameState is an outer FrameState this method behaves as if the inner FrameState was the actual usage, by recursing.
266 blocksForUsage(node, unscheduledUsage, closure);
267 } else if (unscheduledUsage instanceof MergeNode) {
268 // Only FrameStates can be connected to MergeNodes.
269 assert usage instanceof FrameState;
270 // If a FrameState belongs to a MergeNode then it's inputs will be placed at the common dominator of all EndNodes.
271 for (Node pred : unscheduledUsage.cfgPredecessors()) {
272 closure.apply(cfg.getNodeToBlock().get(pred));
273 }
274 } else {
275 // For the time being, only FrameStates can be connected to StateSplits.
276 assert usage instanceof FrameState;
277 assert unscheduledUsage instanceof StateSplit;
278 // Otherwise: Put the input into the same block as the usage.
279 assignBlockToNode((ScheduledNode) unscheduledUsage);
280 closure.apply(cfg.getNodeToBlock().get(unscheduledUsage));
281 }
282 }
283 } else {
284 // All other types of usages: Put the input into the same block as the usage.
285 assignBlockToNode((ScheduledNode) usage);
286 closure.apply(cfg.getNodeToBlock().get(usage));
287 }
288 }
289
290 private void ensureScheduledUsages(Node node) {
291 for (Node usage : node.usages().filter(ScheduledNode.class)) {
292 assignBlockToNode((ScheduledNode) usage);
293 }
294 // now true usages are ready
295 }
296
297 private static Block getCommonDominator(Block a, Block b) {
298 if (a == null) {
299 return b;
300 }
301 if (b == null) {
302 return a;
303 }
304 return ControlFlowGraph.commonDominator(a, b);
305 }
306
307 private void sortNodesWithinBlocks(StructuredGraph graph) {
308 NodeBitMap visited = graph.createNodeBitMap();
309 for (Block b : cfg.getBlocks()) {
310 sortNodesWithinBlock(b, visited);
311 }
312 }
313
314 /**
315 * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over all inputs.
316 * This means that a node is added to the list after all its inputs have been processed.
317 */
318 private void sortNodesWithinBlock(Block b, NodeBitMap visited) {
319 List<ScheduledNode> instructions = blockToNodesMap.get(b);
320 List<ScheduledNode> sortedInstructions = new ArrayList<>(instructions.size() + 2);
321
322 assert !visited.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b;
323 assert !visited.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b;
324
325 for (ScheduledNode i : instructions) {
326 addToSorting(b, i, sortedInstructions, visited);
327 }
328
329 // Make sure that last node gets really last (i.e. when a frame state successor hangs off it).
330 Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1);
331 if (lastSorted != b.getEndNode()) {
332 int idx = sortedInstructions.indexOf(b.getEndNode());
333 boolean canNotMove = false;
334 for (int i = idx + 1; i < sortedInstructions.size(); i++) {
335 if (sortedInstructions.get(i).inputs().contains(b.getEndNode())) {
336 canNotMove = true;
337 break;
338 }
339 }
340 if (canNotMove) {
341 if (b.getEndNode() instanceof ControlSplitNode) {
342 throw new GraalInternalError("Schedule is not possible : needs to move a node after the last node of the block which can not be move").
343 addContext(lastSorted).
344 addContext(b.getEndNode());
345 }
346
347 //b.setLastNode(lastSorted);
348 } else {
349 sortedInstructions.remove(b.getEndNode());
350 sortedInstructions.add(b.getEndNode());
351 }
352 }
353 blockToNodesMap.put(b, sortedInstructions);
354 }
355
356 private void addUnscheduledToSorting(Block b, VirtualState state, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
357 if (state != null) {
358 // UnscheduledNodes should never be marked as visited.
359 assert !visited.isMarked(state);
360
361 for (Node input : state.inputs()) {
362 if (input instanceof VirtualState) {
363 addUnscheduledToSorting(b, (VirtualState) input, sortedInstructions, visited);
364 } else {
365 addToSorting(b, (ScheduledNode) input, sortedInstructions, visited);
366 }
367 }
368 }
369 }
370
371 private void addToSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
372 if (i == null || visited.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) {
373 return;
374 }
375
376 FrameState state = null;
377 WriteNode write = null;
378 for (Node input : i.inputs()) {
379 if (input instanceof WriteNode && !visited.isMarked(input) && cfg.getNodeToBlock().get(input) == b) {
380 assert write == null;
381 write = (WriteNode) input;
382 } else if (input instanceof FrameState) {
383 assert state == null;
384 state = (FrameState) input;
385 } else {
386 addToSorting(b, (ScheduledNode) input, sortedInstructions, visited);
387 }
388 }
389
390 addToSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited);
391 visited.mark(i);
392 addUnscheduledToSorting(b, state, sortedInstructions, visited);
393 assert write == null || !visited.isMarked(write);
394 addToSorting(b, write, sortedInstructions, visited);
395
396 // Now predecessors and inputs are scheduled => we can add this node.
397 sortedInstructions.add(i);
398 }
399 }