1 /*
2 * Copyright (c) 2011, 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.nodes.util;
26
27 import java.util.ArrayList;
28 import java.util.Arrays;
29 import java.util.Collection;
30 import java.util.Collections;
31 import java.util.Iterator;
32 import java.util.List;
33 import java.util.Objects;
34 import java.util.function.BiFunction;
35
36 import jdk.internal.vm.compiler.collections.EconomicMap;
37 import jdk.internal.vm.compiler.collections.EconomicSet;
38 import jdk.internal.vm.compiler.collections.Equivalence;
39 import jdk.internal.vm.compiler.collections.MapCursor;
40 import org.graalvm.compiler.bytecode.Bytecode;
41 import org.graalvm.compiler.code.SourceStackTraceBailoutException;
42 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
43 import org.graalvm.compiler.core.common.type.ObjectStamp;
44 import org.graalvm.compiler.debug.DebugContext;
45 import org.graalvm.compiler.graph.Graph;
46 import org.graalvm.compiler.graph.Node;
47 import org.graalvm.compiler.graph.NodeBitMap;
48 import org.graalvm.compiler.graph.NodeSourcePosition;
49 import org.graalvm.compiler.graph.NodeStack;
50 import org.graalvm.compiler.graph.Position;
51 import org.graalvm.compiler.graph.iterators.NodeIterable;
52 import org.graalvm.compiler.graph.spi.SimplifierTool;
53 import org.graalvm.compiler.nodes.AbstractBeginNode;
54 import org.graalvm.compiler.nodes.AbstractEndNode;
55 import org.graalvm.compiler.nodes.AbstractMergeNode;
56 import org.graalvm.compiler.nodes.ConstantNode;
57 import org.graalvm.compiler.nodes.ControlSplitNode;
58 import org.graalvm.compiler.nodes.FixedNode;
59 import org.graalvm.compiler.nodes.FixedWithNextNode;
60 import org.graalvm.compiler.nodes.FrameState;
61 import org.graalvm.compiler.nodes.GuardNode;
62 import org.graalvm.compiler.nodes.LoopBeginNode;
63 import org.graalvm.compiler.nodes.LoopEndNode;
64 import org.graalvm.compiler.nodes.LoopExitNode;
65 import org.graalvm.compiler.nodes.NodeView;
66 import org.graalvm.compiler.nodes.PhiNode;
67 import org.graalvm.compiler.nodes.PiNode;
68 import org.graalvm.compiler.nodes.ProxyNode;
69 import org.graalvm.compiler.nodes.StateSplit;
70 import org.graalvm.compiler.nodes.StructuredGraph;
71 import org.graalvm.compiler.nodes.ValueNode;
72 import org.graalvm.compiler.nodes.ValuePhiNode;
73 import org.graalvm.compiler.nodes.ValueProxyNode;
74 import org.graalvm.compiler.nodes.java.LoadIndexedNode;
75 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
76 import org.graalvm.compiler.nodes.java.MonitorIdNode;
77 import org.graalvm.compiler.nodes.spi.ArrayLengthProvider;
78 import org.graalvm.compiler.nodes.spi.ArrayLengthProvider.FindLengthMode;
79 import org.graalvm.compiler.nodes.spi.LimitedValueProxy;
80 import org.graalvm.compiler.nodes.spi.LoweringProvider;
81 import org.graalvm.compiler.nodes.spi.ValueProxy;
82 import org.graalvm.compiler.nodes.spi.VirtualizerTool;
83 import org.graalvm.compiler.nodes.type.StampTool;
84 import org.graalvm.compiler.nodes.virtual.VirtualArrayNode;
85 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
86 import org.graalvm.compiler.options.Option;
87 import org.graalvm.compiler.options.OptionKey;
88 import org.graalvm.compiler.options.OptionType;
89 import org.graalvm.compiler.options.OptionValues;
90
91 import jdk.vm.ci.code.BailoutException;
92 import jdk.vm.ci.code.BytecodePosition;
93 import jdk.vm.ci.meta.Assumptions;
94 import jdk.vm.ci.meta.Constant;
95 import jdk.vm.ci.meta.ConstantReflectionProvider;
96 import jdk.vm.ci.meta.JavaKind;
97 import jdk.vm.ci.meta.MetaAccessProvider;
98 import jdk.vm.ci.meta.ResolvedJavaMethod;
99 import jdk.vm.ci.meta.ResolvedJavaType;
100
101 public class GraphUtil {
102
103 public static class Options {
104 @Option(help = "Verify that there are no new unused nodes when performing killCFG", type = OptionType.Debug)//
105 public static final OptionKey<Boolean> VerifyKillCFGUnusedNodes = new OptionKey<>(false);
106 }
107
108 private static void killCFGInner(FixedNode node) {
109 EconomicSet<Node> markedNodes = EconomicSet.create();
110 EconomicMap<AbstractMergeNode, List<AbstractEndNode>> unmarkedMerges = EconomicMap.create();
111
112 // Detach this node from CFG
113 node.replaceAtPredecessor(null);
114
115 markFixedNodes(node, markedNodes, unmarkedMerges);
116
117 fixSurvivingAffectedMerges(markedNodes, unmarkedMerges);
118
119 DebugContext debug = node.getDebug();
120 debug.dump(DebugContext.DETAILED_LEVEL, node.graph(), "After fixing merges (killCFG %s)", node);
121
122 // Mark non-fixed nodes
123 markUsages(markedNodes);
124
125 // Detach marked nodes from non-marked nodes
126 for (Node marked : markedNodes) {
127 for (Node input : marked.inputs()) {
128 if (!markedNodes.contains(input)) {
129 marked.replaceFirstInput(input, null);
130 tryKillUnused(input);
131 }
132 }
133 }
134 debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "After disconnecting non-marked inputs (killCFG %s)", node);
135 // Kill marked nodes
136 for (Node marked : markedNodes) {
137 if (marked.isAlive()) {
138 marked.markDeleted();
139 }
140 }
141 }
142
143 private static void markFixedNodes(FixedNode node, EconomicSet<Node> markedNodes, EconomicMap<AbstractMergeNode, List<AbstractEndNode>> unmarkedMerges) {
144 NodeStack workStack = new NodeStack();
145 workStack.push(node);
146 while (!workStack.isEmpty()) {
147 Node fixedNode = workStack.pop();
148 markedNodes.add(fixedNode);
149 if (fixedNode instanceof AbstractMergeNode) {
150 unmarkedMerges.removeKey((AbstractMergeNode) fixedNode);
151 }
152 while (fixedNode instanceof FixedWithNextNode) {
153 fixedNode = ((FixedWithNextNode) fixedNode).next();
154 if (fixedNode != null) {
155 markedNodes.add(fixedNode);
156 }
157 }
158 if (fixedNode instanceof ControlSplitNode) {
159 for (Node successor : fixedNode.successors()) {
160 workStack.push(successor);
161 }
162 } else if (fixedNode instanceof AbstractEndNode) {
163 AbstractEndNode end = (AbstractEndNode) fixedNode;
164 AbstractMergeNode merge = end.merge();
165 if (merge != null) {
166 assert !markedNodes.contains(merge) || (merge instanceof LoopBeginNode && end instanceof LoopEndNode) : merge;
167 if (merge instanceof LoopBeginNode) {
168 if (end == ((LoopBeginNode) merge).forwardEnd()) {
169 workStack.push(merge);
170 continue;
171 }
172 if (markedNodes.contains(merge)) {
173 continue;
174 }
175 }
176 List<AbstractEndNode> endsSeen = unmarkedMerges.get(merge);
177 if (endsSeen == null) {
178 endsSeen = new ArrayList<>(merge.forwardEndCount());
179 unmarkedMerges.put(merge, endsSeen);
180 }
181 endsSeen.add(end);
182 if (!(end instanceof LoopEndNode) && endsSeen.size() == merge.forwardEndCount()) {
183 assert merge.forwardEnds().filter(n -> !markedNodes.contains(n)).isEmpty();
184 // all this merge's forward ends are marked: it needs to be killed
185 workStack.push(merge);
186 }
187 }
188 }
189 }
190 }
191
192 private static void fixSurvivingAffectedMerges(EconomicSet<Node> markedNodes, EconomicMap<AbstractMergeNode, List<AbstractEndNode>> unmarkedMerges) {
193 MapCursor<AbstractMergeNode, List<AbstractEndNode>> cursor = unmarkedMerges.getEntries();
194 while (cursor.advance()) {
195 AbstractMergeNode merge = cursor.getKey();
196 for (AbstractEndNode end : cursor.getValue()) {
197 merge.removeEnd(end);
198 }
199 if (merge.phiPredecessorCount() == 1) {
200 if (merge instanceof LoopBeginNode) {
201 LoopBeginNode loopBegin = (LoopBeginNode) merge;
202 assert merge.forwardEndCount() == 1;
203 for (LoopExitNode loopExit : loopBegin.loopExits().snapshot()) {
204 if (markedNodes.contains(loopExit)) {
205 /*
206 * disconnect from loop begin so that reduceDegenerateLoopBegin doesn't
207 * transform it into a new beginNode
208 */
209 loopExit.replaceFirstInput(loopBegin, null);
210 }
211 }
212 merge.graph().reduceDegenerateLoopBegin(loopBegin);
213 } else {
214 merge.graph().reduceTrivialMerge(merge);
215 }
216 } else {
217 assert merge.phiPredecessorCount() > 1 : merge;
218 }
219 }
220 }
221
222 private static void markUsages(EconomicSet<Node> markedNodes) {
223 NodeStack workStack = new NodeStack(markedNodes.size() + 4);
224 for (Node marked : markedNodes) {
225 workStack.push(marked);
226 }
227 while (!workStack.isEmpty()) {
228 Node marked = workStack.pop();
229 for (Node usage : marked.usages()) {
230 if (!markedNodes.contains(usage)) {
231 workStack.push(usage);
232 markedNodes.add(usage);
233 }
234 }
235 }
236 }
237
238 @SuppressWarnings("try")
239 public static void killCFG(FixedNode node) {
240 DebugContext debug = node.getDebug();
241 try (DebugContext.Scope scope = debug.scope("KillCFG", node)) {
242 EconomicSet<Node> unusedNodes = null;
243 EconomicSet<Node> unsafeNodes = null;
244 Graph.NodeEventScope nodeEventScope = null;
245 OptionValues options = node.getOptions();
246 if (Graph.Options.VerifyGraalGraphEdges.getValue(options)) {
247 unsafeNodes = collectUnsafeNodes(node.graph());
248 }
249 if (GraphUtil.Options.VerifyKillCFGUnusedNodes.getValue(options)) {
250 EconomicSet<Node> collectedUnusedNodes = unusedNodes = EconomicSet.create(Equivalence.IDENTITY);
251 nodeEventScope = node.graph().trackNodeEvents(new Graph.NodeEventListener() {
252 @Override
253 public void changed(Graph.NodeEvent e, Node n) {
254 if (e == Graph.NodeEvent.ZERO_USAGES && isFloatingNode(n) && !(n instanceof GuardNode)) {
255 collectedUnusedNodes.add(n);
256 }
257 }
258 });
259 }
260 debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "Before killCFG %s", node);
261 killCFGInner(node);
262 debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "After killCFG %s", node);
263 if (Graph.Options.VerifyGraalGraphEdges.getValue(options)) {
264 EconomicSet<Node> newUnsafeNodes = collectUnsafeNodes(node.graph());
265 newUnsafeNodes.removeAll(unsafeNodes);
266 assert newUnsafeNodes.isEmpty() : "New unsafe nodes: " + newUnsafeNodes;
267 }
268 if (GraphUtil.Options.VerifyKillCFGUnusedNodes.getValue(options)) {
269 nodeEventScope.close();
270 Iterator<Node> iterator = unusedNodes.iterator();
271 while (iterator.hasNext()) {
272 Node curNode = iterator.next();
273 if (curNode.isDeleted()) {
274 iterator.remove();
275 }
276 }
277 assert unusedNodes.isEmpty() : "New unused nodes: " + unusedNodes;
278 }
279 } catch (Throwable t) {
280 throw debug.handle(t);
281 }
282 }
283
284 /**
285 * Collects all node in the graph which have non-optional inputs that are null.
286 */
287 private static EconomicSet<Node> collectUnsafeNodes(Graph graph) {
288 EconomicSet<Node> unsafeNodes = EconomicSet.create(Equivalence.IDENTITY);
289 for (Node n : graph.getNodes()) {
290 for (Position pos : n.inputPositions()) {
291 Node input = pos.get(n);
292 if (input == null) {
293 if (!pos.isInputOptional()) {
294 unsafeNodes.add(n);
295 }
296 }
297 }
298 }
299 return unsafeNodes;
300 }
301
302 public static boolean isFloatingNode(Node n) {
303 return !(n instanceof FixedNode);
304 }
305
306 private static boolean checkKill(Node node, boolean mayKillGuard) {
307 node.assertTrue(mayKillGuard || !(node instanceof GuardNode), "must not be a guard node %s", node);
308 node.assertTrue(node.isAlive(), "must be alive");
309 node.assertTrue(node.hasNoUsages(), "cannot kill node %s because of usages: %s", node, node.usages());
310 node.assertTrue(node.predecessor() == null, "cannot kill node %s because of predecessor: %s", node, node.predecessor());
311 return true;
312 }
313
314 public static void killWithUnusedFloatingInputs(Node node) {
315 killWithUnusedFloatingInputs(node, false);
316 }
317
318 public static void killWithUnusedFloatingInputs(Node node, boolean mayKillGuard) {
319 assert checkKill(node, mayKillGuard);
320 node.markDeleted();
321 outer: for (Node in : node.inputs()) {
322 if (in.isAlive()) {
323 in.removeUsage(node);
324 if (in.hasNoUsages()) {
325 node.maybeNotifyZeroUsages(in);
326 }
327 if (isFloatingNode(in)) {
328 if (in.hasNoUsages()) {
329 if (in instanceof GuardNode) {
330 // Guard nodes are only killed if their anchor dies.
331 } else {
332 killWithUnusedFloatingInputs(in);
333 }
334 } else if (in instanceof PhiNode) {
335 for (Node use : in.usages()) {
336 if (use != in) {
337 continue outer;
338 }
339 }
340 in.replaceAtUsages(null);
341 killWithUnusedFloatingInputs(in);
342 }
343 }
344 }
345 }
346 }
347
348 /**
349 * Removes all nodes created after the {@code mark}, assuming no "old" nodes point to "new"
350 * nodes.
351 */
352 public static void removeNewNodes(Graph graph, Graph.Mark mark) {
353 assert checkNoOldToNewEdges(graph, mark);
354 for (Node n : graph.getNewNodes(mark)) {
355 n.markDeleted();
356 for (Node in : n.inputs()) {
357 in.removeUsage(n);
358 }
359 }
360 }
361
362 private static boolean checkNoOldToNewEdges(Graph graph, Graph.Mark mark) {
363 for (Node old : graph.getNodes()) {
364 if (graph.isNew(mark, old)) {
365 break;
366 }
367 for (Node n : old.successors()) {
368 assert !graph.isNew(mark, n) : old + " -> " + n;
369 }
370 for (Node n : old.inputs()) {
371 assert !graph.isNew(mark, n) : old + " -> " + n;
372 }
373 }
374 return true;
375 }
376
377 public static void removeFixedWithUnusedInputs(FixedWithNextNode fixed) {
378 if (fixed instanceof StateSplit) {
379 FrameState stateAfter = ((StateSplit) fixed).stateAfter();
380 if (stateAfter != null) {
381 ((StateSplit) fixed).setStateAfter(null);
382 if (stateAfter.hasNoUsages()) {
383 killWithUnusedFloatingInputs(stateAfter);
384 }
385 }
386 }
387 unlinkFixedNode(fixed);
388 killWithUnusedFloatingInputs(fixed);
389 }
390
391 public static void unlinkFixedNode(FixedWithNextNode fixed) {
392 assert fixed.next() != null && fixed.predecessor() != null && fixed.isAlive() : fixed;
393 FixedNode next = fixed.next();
394 fixed.setNext(null);
395 fixed.replaceAtPredecessor(next);
396 }
397
398 public static void checkRedundantPhi(PhiNode phiNode) {
399 if (phiNode.isDeleted() || phiNode.valueCount() == 1) {
400 return;
401 }
402
403 ValueNode singleValue = phiNode.singleValueOrThis();
404 if (singleValue != phiNode) {
405 Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot();
406 Collection<ProxyNode> proxyUsages = phiNode.usages().filter(ProxyNode.class).snapshot();
407 phiNode.replaceAtUsagesAndDelete(singleValue);
408 for (PhiNode phi : phiUsages) {
409 checkRedundantPhi(phi);
410 }
411 for (ProxyNode proxy : proxyUsages) {
412 checkRedundantProxy(proxy);
413 }
414 }
415 }
416
417 public static void checkRedundantProxy(ProxyNode vpn) {
418 if (vpn.isDeleted()) {
419 return;
420 }
421 AbstractBeginNode proxyPoint = vpn.proxyPoint();
422 if (proxyPoint instanceof LoopExitNode) {
423 LoopExitNode exit = (LoopExitNode) proxyPoint;
424 LoopBeginNode loopBegin = exit.loopBegin();
425 Node vpnValue = vpn.value();
426 for (ValueNode v : loopBegin.stateAfter().values()) {
427 ValueNode v2 = v;
428 if (loopBegin.isPhiAtMerge(v2)) {
429 v2 = ((PhiNode) v2).valueAt(loopBegin.forwardEnd());
430 }
431 if (vpnValue == v2) {
432 Collection<PhiNode> phiUsages = vpn.usages().filter(PhiNode.class).snapshot();
433 Collection<ProxyNode> proxyUsages = vpn.usages().filter(ProxyNode.class).snapshot();
434 vpn.replaceAtUsagesAndDelete(vpnValue);
435 for (PhiNode phi : phiUsages) {
436 checkRedundantPhi(phi);
437 }
438 for (ProxyNode proxy : proxyUsages) {
439 checkRedundantProxy(proxy);
440 }
441 return;
442 }
443 }
444 }
445 }
446
447 /**
448 * Remove loop header without loop ends. This can happen with degenerated loops like this one:
449 *
450 * <pre>
451 * for (;;) {
452 * try {
453 * break;
454 * } catch (UnresolvedException iioe) {
455 * }
456 * }
457 * </pre>
458 */
459 public static void normalizeLoops(StructuredGraph graph) {
460 boolean loopRemoved = false;
461 for (LoopBeginNode begin : graph.getNodes(LoopBeginNode.TYPE)) {
462 if (begin.loopEnds().isEmpty()) {
463 assert begin.forwardEndCount() == 1;
464 graph.reduceDegenerateLoopBegin(begin);
465 loopRemoved = true;
466 } else {
467 normalizeLoopBegin(begin);
468 }
469 }
470
471 if (loopRemoved) {
472 /*
473 * Removing a degenerated loop can make non-loop phi functions unnecessary. Therefore,
474 * we re-check all phi functions and remove redundant ones.
475 */
476 for (Node node : graph.getNodes()) {
477 if (node instanceof PhiNode) {
478 checkRedundantPhi((PhiNode) node);
479 }
480 }
481 }
482 }
483
484 private static void normalizeLoopBegin(LoopBeginNode begin) {
485 // Delete unnecessary loop phi functions, i.e., phi functions where all inputs are either
486 // the same or the phi itself.
487 for (PhiNode phi : begin.phis().snapshot()) {
488 GraphUtil.checkRedundantPhi(phi);
489 }
490 for (LoopExitNode exit : begin.loopExits()) {
491 for (ProxyNode vpn : exit.proxies().snapshot()) {
492 GraphUtil.checkRedundantProxy(vpn);
493 }
494 }
495 }
496
497 /**
498 * Gets an approximate source code location for a node if possible.
499 *
500 * @return the StackTraceElements if an approximate source location is found, null otherwise
501 */
502 public static StackTraceElement[] approxSourceStackTraceElement(Node node) {
503 NodeSourcePosition position = node.getNodeSourcePosition();
504 if (position != null) {
505 // use GraphBuilderConfiguration and enable trackNodeSourcePosition to get better source
506 // positions.
507 return approxSourceStackTraceElement(position);
508 }
509 ArrayList<StackTraceElement> elements = new ArrayList<>();
510 Node n = node;
511 while (n != null) {
512 if (n instanceof MethodCallTargetNode) {
513 elements.add(((MethodCallTargetNode) n).targetMethod().asStackTraceElement(-1));
514 n = ((MethodCallTargetNode) n).invoke().asNode();
515 }
516
517 if (n instanceof StateSplit) {
518 FrameState state = ((StateSplit) n).stateAfter();
519 elements.addAll(Arrays.asList(approxSourceStackTraceElement(state)));
520 break;
521 }
522 n = n.predecessor();
523 }
524 return elements.toArray(new StackTraceElement[elements.size()]);
525 }
526
527 /**
528 * Gets an approximate source code location for frame state.
529 *
530 * @return the StackTraceElements if an approximate source location is found, null otherwise
531 */
532 public static StackTraceElement[] approxSourceStackTraceElement(FrameState frameState) {
533 ArrayList<StackTraceElement> elements = new ArrayList<>();
534 FrameState state = frameState;
535 while (state != null) {
536 Bytecode code = state.getCode();
537 if (code != null) {
538 elements.add(code.asStackTraceElement(state.bci - 1));
539 }
540 state = state.outerFrameState();
541 }
542 return elements.toArray(new StackTraceElement[0]);
543 }
544
545 /**
546 * Gets approximate stack trace elements for a bytecode position.
547 */
548 public static StackTraceElement[] approxSourceStackTraceElement(BytecodePosition bytecodePosition) {
549 ArrayList<StackTraceElement> elements = new ArrayList<>();
550 BytecodePosition position = bytecodePosition;
551 while (position != null) {
552 ResolvedJavaMethod method = position.getMethod();
553 if (method != null) {
554 elements.add(method.asStackTraceElement(position.getBCI()));
555 }
556 position = position.getCaller();
557 }
558 return elements.toArray(new StackTraceElement[0]);
559 }
560
561 /**
562 * Gets an approximate source code location for a node, encoded as an exception, if possible.
563 *
564 * @return the exception with the location
565 */
566 public static RuntimeException approxSourceException(Node node, Throwable cause) {
567 final StackTraceElement[] elements = approxSourceStackTraceElement(node);
568 return createBailoutException(cause == null ? "" : cause.getMessage(), cause, elements);
569 }
570
571 /**
572 * Creates a bailout exception with the given stack trace elements and message.
573 *
574 * @param message the message of the exception
575 * @param elements the stack trace elements
576 * @return the exception
577 */
578 public static BailoutException createBailoutException(String message, Throwable cause, StackTraceElement[] elements) {
579 return SourceStackTraceBailoutException.create(cause, message, elements);
580 }
581
582 /**
583 * Gets an approximate source code location for a node if possible.
584 *
585 * @return a file name and source line number in stack trace format (e.g. "String.java:32") if
586 * an approximate source location is found, null otherwise
587 */
588 public static String approxSourceLocation(Node node) {
589 StackTraceElement[] stackTraceElements = approxSourceStackTraceElement(node);
590 if (stackTraceElements != null && stackTraceElements.length > 0) {
591 StackTraceElement top = stackTraceElements[0];
592 if (top.getFileName() != null && top.getLineNumber() >= 0) {
593 return top.getFileName() + ":" + top.getLineNumber();
594 }
595 }
596 return null;
597 }
598
599 /**
600 * Returns a string representation of the given collection of objects.
601 *
602 * @param objects The {@link Iterable} that will be used to iterate over the objects.
603 * @return A string of the format "[a, b, ...]".
604 */
605 public static String toString(Iterable<?> objects) {
606 StringBuilder str = new StringBuilder();
607 str.append("[");
608 for (Object o : objects) {
609 str.append(o).append(", ");
610 }
611 if (str.length() > 1) {
612 str.setLength(str.length() - 2);
613 }
614 str.append("]");
615 return str.toString();
616 }
617
618 /**
619 * Gets the original value by iterating through all {@link ValueProxy ValueProxies}.
620 *
621 * @param value the start value.
622 * @return the first non-proxy value encountered
623 */
624 public static ValueNode unproxify(ValueNode value) {
625 if (value instanceof ValueProxy) {
626 return unproxify((ValueProxy) value);
627 } else {
628 return value;
629 }
630 }
631
632 /**
633 * Gets the original value by iterating through all {@link ValueProxy ValueProxies}.
634 *
635 * @param value the start value proxy.
636 * @return the first non-proxy value encountered
637 */
638 public static ValueNode unproxify(ValueProxy value) {
639 if (value != null) {
640 ValueNode result = value.getOriginalNode();
641 while (result instanceof ValueProxy) {
642 result = ((ValueProxy) result).getOriginalNode();
643 }
644 return result;
645 } else {
646 return null;
647 }
648 }
649
650 public static ValueNode skipPi(ValueNode node) {
651 ValueNode n = node;
652 while (n instanceof PiNode) {
653 PiNode piNode = (PiNode) n;
654 n = piNode.getOriginalNode();
655 }
656 return n;
657 }
658
659 public static ValueNode skipPiWhileNonNull(ValueNode node) {
660 ValueNode n = node;
661 while (n instanceof PiNode) {
662 PiNode piNode = (PiNode) n;
663 ObjectStamp originalStamp = (ObjectStamp) piNode.getOriginalNode().stamp(NodeView.DEFAULT);
664 if (originalStamp.nonNull()) {
665 n = piNode.getOriginalNode();
666 } else {
667 break;
668 }
669 }
670 return n;
671 }
672
673 /**
674 * Returns the length of the array described by the value parameter, or null if it is not
675 * available. Details of the different modes are documented in {@link FindLengthMode}.
676 *
677 * @param value The start value.
678 * @param mode The mode as documented in {@link FindLengthMode}.
679 * @return The array length if one was found, or null otherwise.
680 */
681 public static ValueNode arrayLength(ValueNode value, FindLengthMode mode, ConstantReflectionProvider constantReflection) {
682 Objects.requireNonNull(mode);
683
684 ValueNode current = value;
685 do {
686 /*
687 * PiArrayNode implements ArrayLengthProvider and ValueProxy. We want to treat it as an
688 * ArrayLengthProvider, therefore we check this case first.
689 */
690 if (current instanceof ArrayLengthProvider) {
691 return ((ArrayLengthProvider) current).findLength(mode, constantReflection);
692
693 } else if (current instanceof ValuePhiNode) {
694 return phiArrayLength((ValuePhiNode) current, mode, constantReflection);
695
696 } else if (current instanceof ValueProxyNode) {
697 ValueProxyNode proxy = (ValueProxyNode) current;
698 ValueNode length = arrayLength(proxy.getOriginalNode(), mode, constantReflection);
699 if (mode == ArrayLengthProvider.FindLengthMode.CANONICALIZE_READ && length != null && !length.isConstant()) {
700 length = new ValueProxyNode(length, proxy.proxyPoint());
701 }
702 return length;
703
704 } else if (current instanceof ValueProxy) {
705 /* Written as a loop instead of a recursive call to reduce recursion depth. */
706 current = ((ValueProxy) current).getOriginalNode();
707
708 } else {
709 return null;
710 }
711 } while (true);
712 }
713
714 private static ValueNode phiArrayLength(ValuePhiNode phi, ArrayLengthProvider.FindLengthMode mode, ConstantReflectionProvider constantReflection) {
715 if (phi.merge() instanceof LoopBeginNode) {
716 /* Avoid cycle detection by not processing phi functions that could introduce cycles. */
717 return null;
718 }
719
720 ValueNode singleLength = null;
721 for (int i = 0; i < phi.values().count(); i++) {
722 ValueNode input = phi.values().get(i);
723 ValueNode length = arrayLength(input, mode, constantReflection);
724 if (length == null) {
725 return null;
726 }
727 assert length.stamp(NodeView.DEFAULT).getStackKind() == JavaKind.Int;
728
729 if (i == 0) {
730 assert singleLength == null;
731 singleLength = length;
732 } else if (singleLength == length) {
733 /* Nothing to do, still having a single length. */
734 } else {
735 return null;
736 }
737 }
738 return singleLength;
739 }
740
741 /**
742 * Tries to find an original value of the given node by traversing through proxies and
743 * unambiguous phis. Note that this method will perform an exhaustive search through phis. It is
744 * intended to be used during graph building, when phi nodes aren't yet canonicalized.
745 *
746 * @param value The node whose original value should be determined.
747 * @return The original value (which might be the input value itself).
748 */
749 public static ValueNode originalValue(ValueNode value) {
750 ValueNode result = originalValueSimple(value);
751 assert result != null;
752 return result;
753 }
754
755 private static ValueNode originalValueSimple(ValueNode value) {
756 /* The very simple case: look through proxies. */
757 ValueNode cur = originalValueForProxy(value);
758
759 while (cur instanceof PhiNode) {
760 /*
761 * We found a phi function. Check if we can analyze it without allocating temporary data
762 * structures.
763 */
764 PhiNode phi = (PhiNode) cur;
765
766 ValueNode phiSingleValue = null;
767 int count = phi.valueCount();
768 for (int i = 0; i < count; ++i) {
769 ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i));
770 if (phiCurValue == phi) {
771 /* Simple cycle, we can ignore the input value. */
772 } else if (phiSingleValue == null) {
773 /* The first input. */
774 phiSingleValue = phiCurValue;
775 } else if (phiSingleValue != phiCurValue) {
776 /* Another input that is different from the first input. */
777
778 if (phiSingleValue instanceof PhiNode || phiCurValue instanceof PhiNode) {
779 /*
780 * We have two different input values for the phi function, and at least one
781 * of the inputs is another phi function. We need to do a complicated
782 * exhaustive check.
783 */
784 return originalValueForComplicatedPhi(phi, new NodeBitMap(value.graph()));
785 } else {
786 /*
787 * We have two different input values for the phi function, but none of them
788 * is another phi function. This phi function cannot be reduce any further,
789 * so the phi function is the original value.
790 */
791 return phi;
792 }
793 }
794 }
795
796 /*
797 * Successfully reduced the phi function to a single input value. The single input value
798 * can itself be a phi function again, so we might take another loop iteration.
799 */
800 assert phiSingleValue != null;
801 cur = phiSingleValue;
802 }
803
804 /* We reached a "normal" node, which is the original value. */
805 assert !(cur instanceof LimitedValueProxy) && !(cur instanceof PhiNode);
806 return cur;
807 }
808
809 private static ValueNode originalValueForProxy(ValueNode value) {
810 ValueNode cur = value;
811 while (cur instanceof LimitedValueProxy) {
812 cur = ((LimitedValueProxy) cur).getOriginalNode();
813 }
814 return cur;
815 }
816
817 /**
818 * Handling for complicated nestings of phi functions. We need to reduce phi functions
819 * recursively, and need a temporary map of visited nodes to avoid endless recursion of cycles.
820 */
821 private static ValueNode originalValueForComplicatedPhi(PhiNode phi, NodeBitMap visited) {
822 if (visited.isMarked(phi)) {
823 /*
824 * Found a phi function that was already seen. Either a cycle, or just a second phi
825 * input to a path we have already processed.
826 */
827 return null;
828 }
829 visited.mark(phi);
830
831 ValueNode phiSingleValue = null;
832 int count = phi.valueCount();
833 for (int i = 0; i < count; ++i) {
834 ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i));
835 if (phiCurValue instanceof PhiNode) {
836 /* Recursively process a phi function input. */
837 phiCurValue = originalValueForComplicatedPhi((PhiNode) phiCurValue, visited);
838 }
839
840 if (phiCurValue == null) {
841 /* Cycle to a phi function that was already seen. We can ignore this input. */
842 } else if (phiSingleValue == null) {
843 /* The first input. */
844 phiSingleValue = phiCurValue;
845 } else if (phiCurValue != phiSingleValue) {
846 /*
847 * Another input that is different from the first input. Since we already
848 * recursively looked through other phi functions, we now know that this phi
849 * function cannot be reduce any further, so the phi function is the original value.
850 */
851 return phi;
852 }
853 }
854 return phiSingleValue;
855 }
856
857 public static boolean tryKillUnused(Node node) {
858 if (node.isAlive() && isFloatingNode(node) && node.hasNoUsages() && !(node instanceof GuardNode)) {
859 killWithUnusedFloatingInputs(node);
860 return true;
861 }
862 return false;
863 }
864
865 /**
866 * Returns an iterator that will return the given node followed by all its predecessors, up
867 * until the point where {@link Node#predecessor()} returns null.
868 *
869 * @param start the node at which to start iterating
870 */
871 public static NodeIterable<FixedNode> predecessorIterable(final FixedNode start) {
872 return new NodeIterable<FixedNode>() {
873 @Override
874 public Iterator<FixedNode> iterator() {
875 return new Iterator<FixedNode>() {
876 public FixedNode current = start;
877
878 @Override
879 public boolean hasNext() {
880 return current != null;
881 }
882
883 @Override
884 public FixedNode next() {
885 try {
886 return current;
887 } finally {
888 current = (FixedNode) current.predecessor();
889 }
890 }
891 };
892 }
893 };
894 }
895
896 private static final class DefaultSimplifierTool implements SimplifierTool {
897 private final MetaAccessProvider metaAccess;
898 private final ConstantReflectionProvider constantReflection;
899 private final ConstantFieldProvider constantFieldProvider;
900 private final boolean canonicalizeReads;
901 private final Assumptions assumptions;
902 private final OptionValues options;
903 private final LoweringProvider loweringProvider;
904
905 DefaultSimplifierTool(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, boolean canonicalizeReads,
906 Assumptions assumptions, OptionValues options, LoweringProvider loweringProvider) {
907 this.metaAccess = metaAccess;
908 this.constantReflection = constantReflection;
909 this.constantFieldProvider = constantFieldProvider;
910 this.canonicalizeReads = canonicalizeReads;
911 this.assumptions = assumptions;
912 this.options = options;
913 this.loweringProvider = loweringProvider;
914 }
915
916 @Override
917 public MetaAccessProvider getMetaAccess() {
918 return metaAccess;
919 }
920
921 @Override
922 public ConstantReflectionProvider getConstantReflection() {
923 return constantReflection;
924 }
925
926 @Override
927 public ConstantFieldProvider getConstantFieldProvider() {
928 return constantFieldProvider;
929 }
930
931 @Override
932 public boolean canonicalizeReads() {
933 return canonicalizeReads;
934 }
935
936 @Override
937 public boolean allUsagesAvailable() {
938 return true;
939 }
940
941 @Override
942 public void deleteBranch(Node branch) {
943 FixedNode fixedBranch = (FixedNode) branch;
944 fixedBranch.predecessor().replaceFirstSuccessor(fixedBranch, null);
945 GraphUtil.killCFG(fixedBranch);
946 }
947
948 @Override
949 public void removeIfUnused(Node node) {
950 GraphUtil.tryKillUnused(node);
951 }
952
953 @Override
954 public void addToWorkList(Node node) {
955 }
956
957 @Override
958 public void addToWorkList(Iterable<? extends Node> nodes) {
959 }
960
961 @Override
962 public Assumptions getAssumptions() {
963 return assumptions;
964 }
965
966 @Override
967 public OptionValues getOptions() {
968 return options;
969 }
970
971 @Override
972 public Integer smallestCompareWidth() {
973 if (loweringProvider != null) {
974 return loweringProvider.smallestCompareWidth();
975 } else {
976 return null;
977 }
978 }
979 }
980
981 public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
982 boolean canonicalizeReads, Assumptions assumptions, OptionValues options) {
983 return getDefaultSimplifier(metaAccess, constantReflection, constantFieldProvider, canonicalizeReads, assumptions, options, null);
984 }
985
986 public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
987 boolean canonicalizeReads, Assumptions assumptions, OptionValues options, LoweringProvider loweringProvider) {
988 return new DefaultSimplifierTool(metaAccess, constantReflection, constantFieldProvider, canonicalizeReads, assumptions, options, loweringProvider);
989 }
990
991 public static Constant foldIfConstantAndRemove(ValueNode node, ValueNode constant) {
992 assert node.inputs().contains(constant);
993 if (constant.isConstant()) {
994 node.replaceFirstInput(constant, null);
995 Constant result = constant.asConstant();
996 tryKillUnused(constant);
997 return result;
998 }
999 return null;
1000 }
1001
1002 /**
1003 * Virtualize an array copy.
1004 *
1005 * @param tool the virtualization tool
1006 * @param source the source array
1007 * @param sourceLength the length of the source array
1008 * @param newLength the length of the new array
1009 * @param from the start index in the source array
1010 * @param newComponentType the component type of the new array
1011 * @param elementKind the kind of the new array elements
1012 * @param graph the node graph
1013 * @param virtualArrayProvider a functional provider that returns a new virtual array given the
1014 * component type and length
1015 */
1016 public static void virtualizeArrayCopy(VirtualizerTool tool, ValueNode source, ValueNode sourceLength, ValueNode newLength, ValueNode from, ResolvedJavaType newComponentType, JavaKind elementKind,
1017 StructuredGraph graph, BiFunction<ResolvedJavaType, Integer, VirtualArrayNode> virtualArrayProvider) {
1018
1019 ValueNode sourceAlias = tool.getAlias(source);
1020 ValueNode replacedSourceLength = tool.getAlias(sourceLength);
1021 ValueNode replacedNewLength = tool.getAlias(newLength);
1022 ValueNode replacedFrom = tool.getAlias(from);
1023 if (!replacedNewLength.isConstant() || !replacedFrom.isConstant() || !replacedSourceLength.isConstant()) {
1024 return;
1025 }
1026
1027 assert newComponentType != null : "An array copy can be virtualized only if the real type of the resulting array is known statically.";
1028
1029 int fromInt = replacedFrom.asJavaConstant().asInt();
1030 int newLengthInt = replacedNewLength.asJavaConstant().asInt();
1031 int sourceLengthInt = replacedSourceLength.asJavaConstant().asInt();
1032 if (sourceAlias instanceof VirtualObjectNode) {
1033 VirtualObjectNode sourceVirtual = (VirtualObjectNode) sourceAlias;
1034 assert sourceLengthInt == sourceVirtual.entryCount();
1035 }
1036
1037 if (fromInt < 0 || newLengthInt < 0 || fromInt > sourceLengthInt) {
1038 /* Illegal values for either from index, the new length or the source length. */
1039 return;
1040 }
1041
1042 if (newLengthInt > tool.getMaximumEntryCount()) {
1043 /* The new array size is higher than maximum allowed size of virtualized objects. */
1044 return;
1045 }
1046
1047 ValueNode[] newEntryState = new ValueNode[newLengthInt];
1048 int readLength = Math.min(newLengthInt, sourceLengthInt - fromInt);
1049
1050 if (sourceAlias instanceof VirtualObjectNode) {
1051 /* The source array is virtualized, just copy over the values. */
1052 VirtualObjectNode sourceVirtual = (VirtualObjectNode) sourceAlias;
1053 boolean alwaysAssignable = newComponentType.getJavaKind() == JavaKind.Object && newComponentType.isJavaLangObject();
1054 for (int i = 0; i < readLength; i++) {
1055 ValueNode entry = tool.getEntry(sourceVirtual, fromInt + i);
1056 if (!alwaysAssignable) {
1057 ResolvedJavaType entryType = StampTool.typeOrNull(entry, tool.getMetaAccess());
1058 if (entryType == null) {
1059 return;
1060 }
1061 if (!newComponentType.isAssignableFrom(entryType)) {
1062 return;
1063 }
1064 }
1065 newEntryState[i] = entry;
1066 }
1067 } else {
1068 /* The source array is not virtualized, emit index loads. */
1069 ResolvedJavaType sourceType = StampTool.typeOrNull(sourceAlias, tool.getMetaAccess());
1070 if (sourceType == null || !sourceType.isArray() || !newComponentType.isAssignableFrom(sourceType.getElementalType())) {
1071 return;
1072 }
1073 for (int i = 0; i < readLength; i++) {
1074 LoadIndexedNode load = new LoadIndexedNode(null, sourceAlias, ConstantNode.forInt(i + fromInt, graph), null, elementKind);
1075 tool.addNode(load);
1076 newEntryState[i] = load;
1077 }
1078 }
1079 if (readLength < newLengthInt) {
1080 /* Pad the copy with the default value of its elment kind. */
1081 ValueNode defaultValue = ConstantNode.defaultForKind(elementKind, graph);
1082 for (int i = readLength; i < newLengthInt; i++) {
1083 newEntryState[i] = defaultValue;
1084 }
1085 }
1086 /* Perform the replacement. */
1087 VirtualArrayNode newVirtualArray = virtualArrayProvider.apply(newComponentType, newLengthInt);
1088 tool.createVirtualObject(newVirtualArray, newEntryState, Collections.<MonitorIdNode> emptyList(), false);
1089 tool.replaceWithVirtual(newVirtualArray);
1090 }
1091 }