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