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