Mercurial > hg > graal-jvmci-8
comparison graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java @ 6525:2c913b643422
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 } |