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