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