1 /*
2 * Copyright (c) 2012, 2018, 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
24
25 package org.graalvm.compiler.loop;
26
27 import java.util.ArrayDeque;
28 import java.util.Collections;
29 import java.util.Deque;
30 import java.util.Iterator;
31
32 import jdk.internal.vm.compiler.collections.EconomicMap;
33 import org.graalvm.compiler.debug.GraalError;
34 import org.graalvm.compiler.graph.Graph;
35 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
36 import org.graalvm.compiler.graph.Node;
37 import org.graalvm.compiler.graph.NodeBitMap;
38 import org.graalvm.compiler.graph.iterators.NodeIterable;
39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.AbstractMergeNode;
41 import org.graalvm.compiler.nodes.EndNode;
42 import org.graalvm.compiler.nodes.FixedNode;
43 import org.graalvm.compiler.nodes.FrameState;
44 import org.graalvm.compiler.nodes.GuardNode;
45 import org.graalvm.compiler.nodes.GuardPhiNode;
46 import org.graalvm.compiler.nodes.GuardProxyNode;
47 import org.graalvm.compiler.nodes.Invoke;
48 import org.graalvm.compiler.nodes.LoopExitNode;
49 import org.graalvm.compiler.nodes.MergeNode;
50 import org.graalvm.compiler.nodes.NodeView;
51 import org.graalvm.compiler.nodes.PhiNode;
52 import org.graalvm.compiler.nodes.ProxyNode;
53 import org.graalvm.compiler.nodes.StructuredGraph;
54 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;
58 import org.graalvm.compiler.nodes.cfg.Block;
59 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
60 import org.graalvm.compiler.nodes.java.MonitorEnterNode;
61 import org.graalvm.compiler.nodes.spi.NodeWithState;
62 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
63 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
64
65 import jdk.vm.ci.meta.TriState;
66
67 public abstract class LoopFragment {
68
69 private final LoopEx loop;
70 private final LoopFragment original;
71 protected NodeBitMap nodes;
72 protected boolean nodesReady;
73 private EconomicMap<Node, Node> duplicationMap;
74
75 public LoopFragment(LoopEx loop) {
76 this(loop, null);
77 this.nodesReady = true;
78 }
79
80 public LoopFragment(LoopEx loop, LoopFragment original) {
81 this.loop = loop;
82 this.original = original;
83 this.nodesReady = false;
84 }
85
86 /**
87 * Return the original LoopEx for this fragment. For duplicated fragments this returns null.
88 */
89 protected LoopEx loop() {
90 return loop;
91 }
92
93 public abstract LoopFragment duplicate();
94
95 public abstract void insertBefore(LoopEx l);
96
97 public void disconnect() {
98 // TODO (gd) possibly abstract
99 }
100
101 public boolean contains(Node n) {
102 return nodes().isMarkedAndGrow(n);
103 }
104
105 @SuppressWarnings("unchecked")
106 public <New extends Node, Old extends New> New getDuplicatedNode(Old n) {
107 assert isDuplicate();
108 return (New) duplicationMap.get(n);
109 }
110
111 protected <New extends Node, Old extends New> void putDuplicatedNode(Old oldNode, New newNode) {
112 duplicationMap.put(oldNode, newNode);
113 }
114
115 /**
116 * Gets the corresponding value in this fragment. Should be called on duplicate fragments with a
117 * node from the original fragment as argument.
118 *
119 * @param b original value
120 * @return corresponding value in the peel
121 */
122 protected abstract ValueNode prim(ValueNode b);
123
124 public boolean isDuplicate() {
125 return original != null;
126 }
127
128 public LoopFragment original() {
129 return original;
130 }
131
132 public abstract NodeBitMap nodes();
133
134 public StructuredGraph graph() {
135 LoopEx l;
136 if (isDuplicate()) {
137 l = original().loop();
138 } else {
139 l = loop();
140 }
141 return l.loopBegin().graph();
142 }
143
144 protected abstract DuplicationReplacement getDuplicationReplacement();
145
146 protected abstract void beforeDuplication();
147
148 protected void finishDuplication() {
149 LoopEx originalLoopEx = original().loop();
150 ControlFlowGraph cfg = originalLoopEx.loopsData().getCFG();
151 for (LoopExitNode exit : originalLoopEx.loopBegin().loopExits().snapshot()) {
152 if (!originalLoopEx.loop().isLoopExit(cfg.blockFor(exit))) {
153 // this LoopExitNode is too low, we need to remove it otherwise it will be below
154 // merged exits
155 exit.removeExit();
156 }
157 }
158
159 }
160
161 protected void patchNodes(final DuplicationReplacement dataFix) {
162 if (isDuplicate() && !nodesReady) {
163 assert !original.isDuplicate();
164 final DuplicationReplacement cfgFix = original().getDuplicationReplacement();
165 DuplicationReplacement dr;
166 if (cfgFix == null && dataFix != null) {
167 dr = dataFix;
168 } else if (cfgFix != null && dataFix == null) {
169 dr = cfgFix;
170 } else if (cfgFix != null && dataFix != null) {
171 dr = new DuplicationReplacement() {
172
173 @Override
174 public Node replacement(Node o) {
175 Node r1 = dataFix.replacement(o);
176 if (r1 != o) {
177 assert cfgFix.replacement(o) == o;
178 return r1;
179 }
180 Node r2 = cfgFix.replacement(o);
181 if (r2 != o) {
182 return r2;
183 }
184 return o;
185 }
186 };
187 } else {
188 dr = null;
189 }
190 beforeDuplication();
191 NodeIterable<Node> nodesIterable = original().nodes();
192 duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr);
193 finishDuplication();
194 nodes = new NodeBitMap(graph());
195 nodes.markAll(duplicationMap.getValues());
196 nodesReady = true;
197 } else {
198 // TODO (gd) apply fix ?
199 }
200 }
201
202 protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks) {
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) {
214 if (b.isDeleted()) {
215 continue;
216 }
217
218 for (Node n : b.getBlockNodes()) {
219 if (n instanceof Invoke) {
220 nodes.mark(((Invoke) n).callTarget());
221 }
222 if (n instanceof NodeWithState) {
223 NodeWithState withState = (NodeWithState) n;
224 withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node)));
225 }
226 if (n instanceof AbstractMergeNode) {
227 // if a merge is in the loop, all of its phis are also in the loop
228 for (PhiNode phi : ((AbstractMergeNode) n).phis()) {
229 nodes.mark(phi);
230 }
231 }
232 nodes.mark(n);
233 }
234 }
235 for (AbstractBeginNode earlyExit : earlyExits) {
236 if (earlyExit.isDeleted()) {
237 continue;
238 }
239
240 nodes.mark(earlyExit);
241
242 if (earlyExit instanceof LoopExitNode) {
243 LoopExitNode loopExit = (LoopExitNode) earlyExit;
244 FrameState stateAfter = loopExit.stateAfter();
245 if (stateAfter != null) {
246 stateAfter.applyToVirtual(node -> nodes.mark(node));
247 }
248 for (ProxyNode proxy : loopExit.proxies()) {
249 nodes.mark(proxy);
250 }
251 }
252 }
253
254 final NodeBitMap nonLoopNodes = graph.createNodeBitMap();
255 Deque<WorkListEntry> worklist = new ArrayDeque<>();
256 for (AbstractBeginNode b : blocks) {
257 if (b.isDeleted()) {
258 continue;
259 }
260
261 for (Node n : b.getBlockNodes()) {
262 if (n instanceof CommitAllocationNode) {
263 for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) {
264 markFloating(worklist, obj, nodes, nonLoopNodes);
265 }
266 }
267 if (n instanceof MonitorEnterNode) {
268 markFloating(worklist, ((MonitorEnterNode) n).getMonitorId(), nodes, nonLoopNodes);
269 }
270 if (n instanceof AbstractMergeNode) {
271 /*
272 * 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.
274 */
275 for (PhiNode phi : ((AbstractMergeNode) n).phis()) {
276 for (Node usage : phi.usages()) {
277 markFloating(worklist, usage, nodes, nonLoopNodes);
278 }
279 }
280 }
281 for (Node usage : n.usages()) {
282 markFloating(worklist, usage, nodes, nonLoopNodes);
283 }
284 }
285 }
286 }
287
288 static class WorkListEntry {
289 final Iterator<Node> usages;
290 final Node n;
291 boolean isLoopNode;
292
293 WorkListEntry(Node n, NodeBitMap loopNodes) {
294 this.n = n;
295 this.usages = n.usages().iterator();
296 this.isLoopNode = loopNodes.isMarked(n);
297 }
298
299 @Override
300 public boolean equals(Object obj) {
301 if (!(obj instanceof WorkListEntry)) {
302 return false;
303 }
304 WorkListEntry other = (WorkListEntry) obj;
305 return this.n == other.n;
306 }
307
308 @Override
309 public int hashCode() {
310 return n.hashCode();
311 }
312 }
313
314 static TriState isLoopNode(Node n, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) {
315 if (loopNodes.isMarked(n)) {
316 return TriState.TRUE;
317 }
318 if (nonLoopNodes.isMarked(n)) {
319 return TriState.FALSE;
320 }
321 if (n instanceof FixedNode || n instanceof PhiNode) {
322 // phi nodes are treated the same as fixed nodes in this algorithm to break cycles
323 return TriState.FALSE;
324 }
325 return TriState.UNKNOWN;
326 }
327
328 private static void pushWorkList(Deque<WorkListEntry> workList, Node node, NodeBitMap loopNodes) {
329 WorkListEntry entry = new WorkListEntry(node, loopNodes);
330 assert !workList.contains(entry) : "node " + node + " added to worklist twice";
331 workList.push(entry);
332 }
333
334 private static void markFloating(Deque<WorkListEntry> workList, Node start, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) {
335 if (isLoopNode(start, loopNodes, nonLoopNodes).isKnown()) {
336 return;
337 }
338 pushWorkList(workList, start, loopNodes);
339 while (!workList.isEmpty()) {
340 WorkListEntry currentEntry = workList.peek();
341 if (currentEntry.usages.hasNext()) {
342 Node current = currentEntry.usages.next();
343 TriState result = isLoopNode(current, loopNodes, nonLoopNodes);
344 if (result.isKnown()) {
345 if (result.toBoolean()) {
346 currentEntry.isLoopNode = true;
347 }
348 } else {
349 pushWorkList(workList, current, loopNodes);
350 }
351 } else {
352 workList.pop();
353 boolean isLoopNode = currentEntry.isLoopNode;
354 Node current = currentEntry.n;
355 if (!isLoopNode && current instanceof GuardNode) {
356 /*
357 * (gd) this is only OK if we are not going to make loop transforms based on
358 * this
359 */
360 assert !((GuardNode) current).graph().hasValueProxies();
361 isLoopNode = true;
362 }
363 if (isLoopNode) {
364 loopNodes.mark(current);
365 for (WorkListEntry e : workList) {
366 e.isLoopNode = true;
367 }
368 } else {
369 nonLoopNodes.mark(current);
370 }
371 }
372 }
373 }
374
375 public static NodeIterable<AbstractBeginNode> toHirBlocks(final Iterable<Block> blocks) {
376 return new NodeIterable<AbstractBeginNode>() {
377
378 @Override
379 public Iterator<AbstractBeginNode> iterator() {
380 final Iterator<Block> it = blocks.iterator();
381 return new Iterator<AbstractBeginNode>() {
382
383 @Override
384 public void remove() {
385 throw new UnsupportedOperationException();
386 }
387
388 @Override
389 public AbstractBeginNode next() {
390 return it.next().getBeginNode();
391 }
392
393 @Override
394 public boolean hasNext() {
395 return it.hasNext();
396 }
397 };
398 }
399
400 };
401 }
402
403 /**
404 * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with
405 * the original fragment's exits.
406 */
407 protected void mergeEarlyExits() {
408 assert isDuplicate();
409 StructuredGraph graph = graph();
410 for (AbstractBeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getLoopExits())) {
411 FixedNode next = earlyExit.next();
412 if (earlyExit.isDeleted() || !this.original().contains(earlyExit)) {
413 continue;
414 }
415 AbstractBeginNode newEarlyExit = getDuplicatedNode(earlyExit);
416 if (newEarlyExit == null) {
417 continue;
418 }
419 MergeNode merge = graph.add(new MergeNode());
420 EndNode originalEnd = graph.add(new EndNode());
421 EndNode newEnd = graph.add(new EndNode());
422 merge.addForwardEnd(originalEnd);
423 merge.addForwardEnd(newEnd);
424 earlyExit.setNext(originalEnd);
425 newEarlyExit.setNext(newEnd);
426 merge.setNext(next);
427
428 FrameState exitState = null;
429 if (earlyExit instanceof LoopExitNode) {
430 LoopExitNode earlyLoopExit = (LoopExitNode) earlyExit;
431 exitState = earlyLoopExit.stateAfter();
432 if (exitState != null) {
433 FrameState originalExitState = exitState;
434 exitState = exitState.duplicateWithVirtualState();
435 earlyLoopExit.setStateAfter(exitState);
436 merge.setStateAfter(originalExitState);
437 /*
438 * Using the old exit's state as the merge's state is necessary because some of
439 * the VirtualState nodes contained in the old exit's state may be shared by
440 * other dominated VirtualStates. Those dominated virtual states need to see the
441 * proxy->phi update that are applied below.
442 *
443 * We now update the original fragment's nodes accordingly:
444 */
445 originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node));
446 exitState.applyToVirtual(node -> original.nodes.markAndGrow(node));
447 }
448 }
449
450 for (Node anchored : earlyExit.anchored().snapshot()) {
451 anchored.replaceFirstInput(earlyExit, merge);
452 }
453
454 if (earlyExit instanceof LoopExitNode) {
455 LoopExitNode earlyLoopExit = (LoopExitNode) earlyExit;
456 FrameState finalExitState = exitState;
457 boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode;
458 for (ProxyNode vpn : earlyLoopExit.proxies().snapshot()) {
459 if (vpn.hasNoUsages()) {
460 continue;
461 }
462 if (vpn.value() == null) {
463 assert vpn instanceof GuardProxyNode;
464 vpn.replaceAtUsages(null);
465 continue;
466 }
467 final ValueNode replaceWith;
468 ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value());
469 if (newVpn != null) {
470 PhiNode phi;
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);
479 phi.addInput(newVpn);
480 replaceWith = phi;
481 } else {
482 replaceWith = vpn.value();
483 }
484 vpn.replaceAtMatchingUsages(replaceWith, usage -> {
485 if (merge.isPhiAtMerge(usage)) {
486 return false;
487 }
488 if (usage instanceof VirtualState) {
489 VirtualState stateUsage = (VirtualState) usage;
490 if (finalExitState != null && finalExitState.isPartOfThisState(stateUsage)) {
491 return false;
492 }
493 }
494 return true;
495 });
496 }
497 }
498 }
499 }
500 }