1 /* |
1 /* |
2 * Copyright (c) 2012, 2018, Oracle and/or its affiliates. All rights reserved. |
2 * Copyright (c) 2012, 2019, Oracle and/or its affiliates. All rights reserved. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * |
4 * |
5 * This code is free software; you can redistribute it and/or modify it |
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 |
6 * under the terms of the GNU General Public License version 2 only, as |
7 * published by the Free Software Foundation. |
7 * published by the Free Software Foundation. |
23 |
23 |
24 |
24 |
25 package org.graalvm.compiler.loop; |
25 package org.graalvm.compiler.loop; |
26 |
26 |
27 import java.util.ArrayDeque; |
27 import java.util.ArrayDeque; |
28 import java.util.Collections; |
|
29 import java.util.Deque; |
28 import java.util.Deque; |
30 import java.util.Iterator; |
29 import java.util.Iterator; |
31 |
30 |
32 import jdk.internal.vm.compiler.collections.EconomicMap; |
31 import jdk.internal.vm.compiler.collections.EconomicMap; |
33 import org.graalvm.compiler.debug.GraalError; |
32 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph; |
34 import org.graalvm.compiler.graph.Graph; |
33 import org.graalvm.compiler.graph.Graph; |
35 import org.graalvm.compiler.graph.Graph.DuplicationReplacement; |
34 import org.graalvm.compiler.graph.Graph.DuplicationReplacement; |
36 import org.graalvm.compiler.graph.Node; |
35 import org.graalvm.compiler.graph.Node; |
37 import org.graalvm.compiler.graph.NodeBitMap; |
36 import org.graalvm.compiler.graph.NodeBitMap; |
38 import org.graalvm.compiler.graph.iterators.NodeIterable; |
37 import org.graalvm.compiler.graph.iterators.NodeIterable; |
40 import org.graalvm.compiler.nodes.AbstractMergeNode; |
39 import org.graalvm.compiler.nodes.AbstractMergeNode; |
41 import org.graalvm.compiler.nodes.EndNode; |
40 import org.graalvm.compiler.nodes.EndNode; |
42 import org.graalvm.compiler.nodes.FixedNode; |
41 import org.graalvm.compiler.nodes.FixedNode; |
43 import org.graalvm.compiler.nodes.FrameState; |
42 import org.graalvm.compiler.nodes.FrameState; |
44 import org.graalvm.compiler.nodes.GuardNode; |
43 import org.graalvm.compiler.nodes.GuardNode; |
45 import org.graalvm.compiler.nodes.GuardPhiNode; |
|
46 import org.graalvm.compiler.nodes.GuardProxyNode; |
44 import org.graalvm.compiler.nodes.GuardProxyNode; |
47 import org.graalvm.compiler.nodes.Invoke; |
45 import org.graalvm.compiler.nodes.Invoke; |
|
46 import org.graalvm.compiler.nodes.LoopBeginNode; |
48 import org.graalvm.compiler.nodes.LoopExitNode; |
47 import org.graalvm.compiler.nodes.LoopExitNode; |
49 import org.graalvm.compiler.nodes.MergeNode; |
48 import org.graalvm.compiler.nodes.MergeNode; |
50 import org.graalvm.compiler.nodes.NodeView; |
|
51 import org.graalvm.compiler.nodes.PhiNode; |
49 import org.graalvm.compiler.nodes.PhiNode; |
52 import org.graalvm.compiler.nodes.ProxyNode; |
50 import org.graalvm.compiler.nodes.ProxyNode; |
53 import org.graalvm.compiler.nodes.StructuredGraph; |
51 import org.graalvm.compiler.nodes.StructuredGraph; |
54 import org.graalvm.compiler.nodes.ValueNode; |
52 import org.graalvm.compiler.nodes.ValueNode; |
55 import org.graalvm.compiler.nodes.ValuePhiNode; |
|
56 import org.graalvm.compiler.nodes.ValueProxyNode; |
|
57 import org.graalvm.compiler.nodes.VirtualState; |
53 import org.graalvm.compiler.nodes.VirtualState; |
58 import org.graalvm.compiler.nodes.cfg.Block; |
54 import org.graalvm.compiler.nodes.cfg.Block; |
59 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; |
55 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; |
60 import org.graalvm.compiler.nodes.java.MonitorEnterNode; |
56 import org.graalvm.compiler.nodes.java.MonitorEnterNode; |
61 import org.graalvm.compiler.nodes.spi.NodeWithState; |
57 import org.graalvm.compiler.nodes.spi.NodeWithState; |
197 } else { |
193 } else { |
198 // TODO (gd) apply fix ? |
194 // TODO (gd) apply fix ? |
199 } |
195 } |
200 } |
196 } |
201 |
197 |
202 protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks) { |
198 protected static void computeNodes(NodeBitMap nodes, Graph graph, LoopEx loop, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) { |
203 return computeNodes(graph, blocks, Collections.emptyList()); |
|
204 } |
|
205 |
|
206 protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) { |
|
207 final NodeBitMap nodes = graph.createNodeBitMap(); |
|
208 computeNodes(nodes, graph, blocks, earlyExits); |
|
209 return nodes; |
|
210 } |
|
211 |
|
212 protected static void computeNodes(NodeBitMap nodes, Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) { |
|
213 for (AbstractBeginNode b : blocks) { |
199 for (AbstractBeginNode b : blocks) { |
214 if (b.isDeleted()) { |
200 if (b.isDeleted()) { |
215 continue; |
201 continue; |
216 } |
202 } |
217 |
203 |
259 } |
245 } |
260 |
246 |
261 for (Node n : b.getBlockNodes()) { |
247 for (Node n : b.getBlockNodes()) { |
262 if (n instanceof CommitAllocationNode) { |
248 if (n instanceof CommitAllocationNode) { |
263 for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) { |
249 for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) { |
264 markFloating(worklist, obj, nodes, nonLoopNodes); |
250 markFloating(worklist, loop, obj, nodes, nonLoopNodes); |
265 } |
251 } |
266 } |
252 } |
267 if (n instanceof MonitorEnterNode) { |
253 if (n instanceof MonitorEnterNode) { |
268 markFloating(worklist, ((MonitorEnterNode) n).getMonitorId(), nodes, nonLoopNodes); |
254 markFloating(worklist, loop, ((MonitorEnterNode) n).getMonitorId(), nodes, nonLoopNodes); |
269 } |
255 } |
270 if (n instanceof AbstractMergeNode) { |
256 if (n instanceof AbstractMergeNode) { |
271 /* |
257 /* |
272 * Since we already marked all phi nodes as being in the loop to break cycles, |
258 * Since we already marked all phi nodes as being in the loop to break cycles, |
273 * we also have to iterate over their usages here. |
259 * we also have to iterate over their usages here. |
274 */ |
260 */ |
275 for (PhiNode phi : ((AbstractMergeNode) n).phis()) { |
261 for (PhiNode phi : ((AbstractMergeNode) n).phis()) { |
276 for (Node usage : phi.usages()) { |
262 for (Node usage : phi.usages()) { |
277 markFloating(worklist, usage, nodes, nonLoopNodes); |
263 markFloating(worklist, loop, usage, nodes, nonLoopNodes); |
278 } |
264 } |
279 } |
265 } |
280 } |
266 } |
281 for (Node usage : n.usages()) { |
267 for (Node usage : n.usages()) { |
282 markFloating(worklist, usage, nodes, nonLoopNodes); |
268 markFloating(worklist, loop, usage, nodes, nonLoopNodes); |
283 } |
269 } |
284 } |
270 } |
285 } |
271 } |
286 } |
272 } |
287 |
273 |
329 WorkListEntry entry = new WorkListEntry(node, loopNodes); |
315 WorkListEntry entry = new WorkListEntry(node, loopNodes); |
330 assert !workList.contains(entry) : "node " + node + " added to worklist twice"; |
316 assert !workList.contains(entry) : "node " + node + " added to worklist twice"; |
331 workList.push(entry); |
317 workList.push(entry); |
332 } |
318 } |
333 |
319 |
334 private static void markFloating(Deque<WorkListEntry> workList, Node start, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) { |
320 private static void markFloating(Deque<WorkListEntry> workList, LoopEx loop, Node start, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) { |
335 if (isLoopNode(start, loopNodes, nonLoopNodes).isKnown()) { |
321 if (isLoopNode(start, loopNodes, nonLoopNodes).isKnown()) { |
336 return; |
322 return; |
337 } |
323 } |
|
324 |
|
325 LoopBeginNode loopBeginNode = loop.loopBegin(); |
|
326 ControlFlowGraph cfg = loop.loopsData().getCFG(); |
|
327 |
338 pushWorkList(workList, start, loopNodes); |
328 pushWorkList(workList, start, loopNodes); |
339 while (!workList.isEmpty()) { |
329 while (!workList.isEmpty()) { |
340 WorkListEntry currentEntry = workList.peek(); |
330 WorkListEntry currentEntry = workList.peek(); |
341 if (currentEntry.usages.hasNext()) { |
331 if (currentEntry.usages.hasNext()) { |
342 Node current = currentEntry.usages.next(); |
332 Node current = currentEntry.usages.next(); |
350 } |
340 } |
351 } else { |
341 } else { |
352 workList.pop(); |
342 workList.pop(); |
353 boolean isLoopNode = currentEntry.isLoopNode; |
343 boolean isLoopNode = currentEntry.isLoopNode; |
354 Node current = currentEntry.n; |
344 Node current = currentEntry.n; |
355 if (!isLoopNode && current instanceof GuardNode) { |
345 if (!isLoopNode && current instanceof GuardNode && !current.hasUsages()) { |
356 /* |
346 GuardNode guard = (GuardNode) current; |
357 * (gd) this is only OK if we are not going to make loop transforms based on |
347 if (isLoopNode(guard.getCondition(), loopNodes, nonLoopNodes) != TriState.FALSE) { |
358 * this |
348 ValueNode anchor = guard.getAnchor().asNode(); |
359 */ |
349 TriState isAnchorInLoop = isLoopNode(anchor, loopNodes, nonLoopNodes); |
360 assert !((GuardNode) current).graph().hasValueProxies(); |
350 if (isAnchorInLoop != TriState.FALSE) { |
361 isLoopNode = true; |
351 if (!(anchor instanceof LoopExitNode && ((LoopExitNode) anchor).loopBegin() == loopBeginNode)) { |
|
352 /* |
|
353 * (gd) this is wrong in general, it's completely avoidable while we |
|
354 * are doing loop transforms using ValueProxies. If it happens after |
|
355 * it could still cause problem. |
|
356 */ |
|
357 assert !((GuardNode) current).graph().hasValueProxies(); |
|
358 isLoopNode = true; |
|
359 } |
|
360 } else if (AbstractControlFlowGraph.strictlyDominates(cfg.blockFor(anchor), cfg.blockFor(loopBeginNode))) { |
|
361 // The anchor is above the loop. The no-usage guard can potentially be |
|
362 // scheduled inside the loop. |
|
363 isLoopNode = true; |
|
364 } |
|
365 } |
362 } |
366 } |
363 if (isLoopNode) { |
367 if (isLoopNode) { |
364 loopNodes.mark(current); |
368 loopNodes.mark(current); |
365 for (WorkListEntry e : workList) { |
369 for (WorkListEntry e : workList) { |
366 e.isLoopNode = true; |
370 e.isLoopNode = true; |
465 continue; |
469 continue; |
466 } |
470 } |
467 final ValueNode replaceWith; |
471 final ValueNode replaceWith; |
468 ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value()); |
472 ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value()); |
469 if (newVpn != null) { |
473 if (newVpn != null) { |
470 PhiNode phi; |
474 PhiNode phi = vpn.createPhi(merge); |
471 if (vpn instanceof ValueProxyNode) { |
|
472 phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(NodeView.DEFAULT), merge)); |
|
473 } else if (vpn instanceof GuardProxyNode) { |
|
474 phi = graph.addWithoutUnique(new GuardPhiNode(merge)); |
|
475 } else { |
|
476 throw GraalError.shouldNotReachHere(); |
|
477 } |
|
478 phi.addInput(vpn); |
475 phi.addInput(vpn); |
479 phi.addInput(newVpn); |
476 phi.addInput(newVpn); |
480 replaceWith = phi; |
477 replaceWith = phi; |
481 } else { |
478 } else { |
482 replaceWith = vpn.value(); |
479 replaceWith = vpn.value(); |