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