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