/* * Copyright (c) 2011, 2017, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package org.graalvm.compiler.nodes.util; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.Iterator; import java.util.List; import java.util.function.BiFunction; import org.graalvm.compiler.bytecode.Bytecode; import org.graalvm.compiler.code.SourceStackTraceBailoutException; import org.graalvm.compiler.core.common.spi.ConstantFieldProvider; import org.graalvm.compiler.core.common.type.ObjectStamp; import org.graalvm.compiler.debug.DebugContext; import org.graalvm.compiler.graph.Graph; import org.graalvm.compiler.graph.Node; import org.graalvm.compiler.graph.NodeBitMap; import org.graalvm.compiler.graph.NodeSourcePosition; import org.graalvm.compiler.graph.NodeStack; import org.graalvm.compiler.graph.Position; import org.graalvm.compiler.graph.iterators.NodeIterable; import org.graalvm.compiler.graph.spi.SimplifierTool; import org.graalvm.compiler.nodes.AbstractBeginNode; import org.graalvm.compiler.nodes.AbstractEndNode; import org.graalvm.compiler.nodes.AbstractMergeNode; import org.graalvm.compiler.nodes.ConstantNode; import org.graalvm.compiler.nodes.ControlSplitNode; import org.graalvm.compiler.nodes.FixedNode; import org.graalvm.compiler.nodes.FixedWithNextNode; import org.graalvm.compiler.nodes.FrameState; import org.graalvm.compiler.nodes.GuardNode; import org.graalvm.compiler.nodes.LoopBeginNode; import org.graalvm.compiler.nodes.LoopEndNode; import org.graalvm.compiler.nodes.LoopExitNode; import org.graalvm.compiler.nodes.PhiNode; import org.graalvm.compiler.nodes.PiNode; import org.graalvm.compiler.nodes.ProxyNode; import org.graalvm.compiler.nodes.StateSplit; import org.graalvm.compiler.nodes.StructuredGraph; import org.graalvm.compiler.nodes.ValueNode; import org.graalvm.compiler.nodes.java.LoadIndexedNode; import org.graalvm.compiler.nodes.java.MethodCallTargetNode; import org.graalvm.compiler.nodes.java.MonitorIdNode; import org.graalvm.compiler.nodes.spi.ArrayLengthProvider; import org.graalvm.compiler.nodes.spi.LimitedValueProxy; import org.graalvm.compiler.nodes.spi.LoweringProvider; import org.graalvm.compiler.nodes.spi.ValueProxy; import org.graalvm.compiler.nodes.spi.VirtualizerTool; import org.graalvm.compiler.nodes.virtual.VirtualArrayNode; import org.graalvm.compiler.nodes.virtual.VirtualObjectNode; import org.graalvm.compiler.options.Option; import org.graalvm.compiler.options.OptionKey; import org.graalvm.compiler.options.OptionType; import org.graalvm.compiler.options.OptionValues; import org.graalvm.util.EconomicMap; import org.graalvm.util.EconomicSet; import org.graalvm.util.Equivalence; import org.graalvm.util.MapCursor; import jdk.vm.ci.code.BailoutException; import jdk.vm.ci.code.BytecodePosition; import jdk.vm.ci.meta.Assumptions; import jdk.vm.ci.meta.Constant; import jdk.vm.ci.meta.ConstantReflectionProvider; import jdk.vm.ci.meta.JavaKind; import jdk.vm.ci.meta.MetaAccessProvider; import jdk.vm.ci.meta.ResolvedJavaMethod; import jdk.vm.ci.meta.ResolvedJavaType; public class GraphUtil { public static class Options { @Option(help = "Verify that there are no new unused nodes when performing killCFG", type = OptionType.Debug)// public static final OptionKey VerifyKillCFGUnusedNodes = new OptionKey<>(false); } private static void killCFGInner(FixedNode node) { EconomicSet markedNodes = EconomicSet.create(); EconomicMap> unmarkedMerges = EconomicMap.create(); // Detach this node from CFG node.replaceAtPredecessor(null); markFixedNodes(node, markedNodes, unmarkedMerges); fixSurvivingAffectedMerges(markedNodes, unmarkedMerges); DebugContext debug = node.getDebug(); debug.dump(DebugContext.DETAILED_LEVEL, node.graph(), "After fixing merges (killCFG %s)", node); // Mark non-fixed nodes markUsages(markedNodes); // Detach marked nodes from non-marked nodes for (Node marked : markedNodes) { for (Node input : marked.inputs()) { if (!markedNodes.contains(input)) { marked.replaceFirstInput(input, null); tryKillUnused(input); } } } debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "After disconnecting non-marked inputs (killCFG %s)", node); // Kill marked nodes for (Node marked : markedNodes) { if (marked.isAlive()) { marked.markDeleted(); } } } private static void markFixedNodes(FixedNode node, EconomicSet markedNodes, EconomicMap> unmarkedMerges) { NodeStack workStack = new NodeStack(); workStack.push(node); while (!workStack.isEmpty()) { Node fixedNode = workStack.pop(); markedNodes.add(fixedNode); if (fixedNode instanceof AbstractMergeNode) { unmarkedMerges.removeKey((AbstractMergeNode) fixedNode); } while (fixedNode instanceof FixedWithNextNode) { fixedNode = ((FixedWithNextNode) fixedNode).next(); if (fixedNode != null) { markedNodes.add(fixedNode); } } if (fixedNode instanceof ControlSplitNode) { for (Node successor : fixedNode.successors()) { workStack.push(successor); } } else if (fixedNode instanceof AbstractEndNode) { AbstractEndNode end = (AbstractEndNode) fixedNode; AbstractMergeNode merge = end.merge(); if (merge != null) { assert !markedNodes.contains(merge) || (merge instanceof LoopBeginNode && end instanceof LoopEndNode) : merge; if (merge instanceof LoopBeginNode) { if (end == ((LoopBeginNode) merge).forwardEnd()) { workStack.push(merge); continue; } if (markedNodes.contains(merge)) { continue; } } List endsSeen = unmarkedMerges.get(merge); if (endsSeen == null) { endsSeen = new ArrayList<>(merge.forwardEndCount()); unmarkedMerges.put(merge, endsSeen); } endsSeen.add(end); if (!(end instanceof LoopEndNode) && endsSeen.size() == merge.forwardEndCount()) { assert merge.forwardEnds().filter(n -> !markedNodes.contains(n)).isEmpty(); // all this merge's forward ends are marked: it needs to be killed workStack.push(merge); } } } } } private static void fixSurvivingAffectedMerges(EconomicSet markedNodes, EconomicMap> unmarkedMerges) { MapCursor> cursor = unmarkedMerges.getEntries(); while (cursor.advance()) { AbstractMergeNode merge = cursor.getKey(); for (AbstractEndNode end : cursor.getValue()) { merge.removeEnd(end); } if (merge.phiPredecessorCount() == 1) { if (merge instanceof LoopBeginNode) { LoopBeginNode loopBegin = (LoopBeginNode) merge; assert merge.forwardEndCount() == 1; for (LoopExitNode loopExit : loopBegin.loopExits().snapshot()) { if (markedNodes.contains(loopExit)) { /* * disconnect from loop begin so that reduceDegenerateLoopBegin doesn't * transform it into a new beginNode */ loopExit.replaceFirstInput(loopBegin, null); } } merge.graph().reduceDegenerateLoopBegin(loopBegin); } else { merge.graph().reduceTrivialMerge(merge); } } else { assert merge.phiPredecessorCount() > 1 : merge; } } } private static void markUsages(EconomicSet markedNodes) { NodeStack workStack = new NodeStack(markedNodes.size() + 4); for (Node marked : markedNodes) { workStack.push(marked); } while (!workStack.isEmpty()) { Node marked = workStack.pop(); for (Node usage : marked.usages()) { if (!markedNodes.contains(usage)) { workStack.push(usage); markedNodes.add(usage); } } } } @SuppressWarnings("try") public static void killCFG(FixedNode node) { DebugContext debug = node.getDebug(); try (DebugContext.Scope scope = debug.scope("KillCFG", node)) { EconomicSet unusedNodes = null; EconomicSet unsafeNodes = null; Graph.NodeEventScope nodeEventScope = null; OptionValues options = node.getOptions(); if (Graph.Options.VerifyGraalGraphEdges.getValue(options)) { unsafeNodes = collectUnsafeNodes(node.graph()); } if (GraphUtil.Options.VerifyKillCFGUnusedNodes.getValue(options)) { EconomicSet collectedUnusedNodes = unusedNodes = EconomicSet.create(Equivalence.IDENTITY); nodeEventScope = node.graph().trackNodeEvents(new Graph.NodeEventListener() { @Override public void changed(Graph.NodeEvent e, Node n) { if (e == Graph.NodeEvent.ZERO_USAGES && isFloatingNode(n) && !(n instanceof GuardNode)) { collectedUnusedNodes.add(n); } } }); } debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "Before killCFG %s", node); killCFGInner(node); debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "After killCFG %s", node); if (Graph.Options.VerifyGraalGraphEdges.getValue(options)) { EconomicSet newUnsafeNodes = collectUnsafeNodes(node.graph()); newUnsafeNodes.removeAll(unsafeNodes); assert newUnsafeNodes.isEmpty() : "New unsafe nodes: " + newUnsafeNodes; } if (GraphUtil.Options.VerifyKillCFGUnusedNodes.getValue(options)) { nodeEventScope.close(); Iterator iterator = unusedNodes.iterator(); while (iterator.hasNext()) { Node curNode = iterator.next(); if (curNode.isDeleted()) { iterator.remove(); } } assert unusedNodes.isEmpty() : "New unused nodes: " + unusedNodes; } } catch (Throwable t) { throw debug.handle(t); } } /** * Collects all node in the graph which have non-optional inputs that are null. */ private static EconomicSet collectUnsafeNodes(Graph graph) { EconomicSet unsafeNodes = EconomicSet.create(Equivalence.IDENTITY); for (Node n : graph.getNodes()) { for (Position pos : n.inputPositions()) { Node input = pos.get(n); if (input == null) { if (!pos.isInputOptional()) { unsafeNodes.add(n); } } } } return unsafeNodes; } public static boolean isFloatingNode(Node n) { return !(n instanceof FixedNode); } private static boolean checkKill(Node node, boolean mayKillGuard) { node.assertTrue(mayKillGuard || !(node instanceof GuardNode), "must not be a guard node %s", node); node.assertTrue(node.isAlive(), "must be alive"); node.assertTrue(node.hasNoUsages(), "cannot kill node %s because of usages: %s", node, node.usages()); node.assertTrue(node.predecessor() == null, "cannot kill node %s because of predecessor: %s", node, node.predecessor()); return true; } public static void killWithUnusedFloatingInputs(Node node) { killWithUnusedFloatingInputs(node, false); } public static void killWithUnusedFloatingInputs(Node node, boolean mayKillGuard) { assert checkKill(node, mayKillGuard); node.markDeleted(); outer: for (Node in : node.inputs()) { if (in.isAlive()) { in.removeUsage(node); if (in.hasNoUsages()) { node.maybeNotifyZeroUsages(in); } if (isFloatingNode(in)) { if (in.hasNoUsages()) { if (in instanceof GuardNode) { // Guard nodes are only killed if their anchor dies. } else { killWithUnusedFloatingInputs(in); } } else if (in instanceof PhiNode) { for (Node use : in.usages()) { if (use != in) { continue outer; } } in.replaceAtUsages(null); killWithUnusedFloatingInputs(in); } } } } } /** * Removes all nodes created after the {@code mark}, assuming no "old" nodes point to "new" * nodes. */ public static void removeNewNodes(Graph graph, Graph.Mark mark) { assert checkNoOldToNewEdges(graph, mark); for (Node n : graph.getNewNodes(mark)) { n.markDeleted(); for (Node in : n.inputs()) { in.removeUsage(n); } } } private static boolean checkNoOldToNewEdges(Graph graph, Graph.Mark mark) { for (Node old : graph.getNodes()) { if (graph.isNew(mark, old)) { break; } for (Node n : old.successors()) { assert !graph.isNew(mark, n) : old + " -> " + n; } for (Node n : old.inputs()) { assert !graph.isNew(mark, n) : old + " -> " + n; } } return true; } public static void removeFixedWithUnusedInputs(FixedWithNextNode fixed) { if (fixed instanceof StateSplit) { FrameState stateAfter = ((StateSplit) fixed).stateAfter(); if (stateAfter != null) { ((StateSplit) fixed).setStateAfter(null); if (stateAfter.hasNoUsages()) { killWithUnusedFloatingInputs(stateAfter); } } } unlinkFixedNode(fixed); killWithUnusedFloatingInputs(fixed); } public static void unlinkFixedNode(FixedWithNextNode fixed) { assert fixed.next() != null && fixed.predecessor() != null && fixed.isAlive() : fixed; FixedNode next = fixed.next(); fixed.setNext(null); fixed.replaceAtPredecessor(next); } public static void checkRedundantPhi(PhiNode phiNode) { if (phiNode.isDeleted() || phiNode.valueCount() == 1) { return; } ValueNode singleValue = phiNode.singleValueOrThis(); if (singleValue != phiNode) { Collection phiUsages = phiNode.usages().filter(PhiNode.class).snapshot(); Collection proxyUsages = phiNode.usages().filter(ProxyNode.class).snapshot(); phiNode.replaceAtUsagesAndDelete(singleValue); for (PhiNode phi : phiUsages) { checkRedundantPhi(phi); } for (ProxyNode proxy : proxyUsages) { checkRedundantProxy(proxy); } } } public static void checkRedundantProxy(ProxyNode vpn) { if (vpn.isDeleted()) { return; } AbstractBeginNode proxyPoint = vpn.proxyPoint(); if (proxyPoint instanceof LoopExitNode) { LoopExitNode exit = (LoopExitNode) proxyPoint; LoopBeginNode loopBegin = exit.loopBegin(); Node vpnValue = vpn.value(); for (ValueNode v : loopBegin.stateAfter().values()) { ValueNode v2 = v; if (loopBegin.isPhiAtMerge(v2)) { v2 = ((PhiNode) v2).valueAt(loopBegin.forwardEnd()); } if (vpnValue == v2) { Collection phiUsages = vpn.usages().filter(PhiNode.class).snapshot(); Collection proxyUsages = vpn.usages().filter(ProxyNode.class).snapshot(); vpn.replaceAtUsagesAndDelete(vpnValue); for (PhiNode phi : phiUsages) { checkRedundantPhi(phi); } for (ProxyNode proxy : proxyUsages) { checkRedundantProxy(proxy); } return; } } } } /** * Remove loop header without loop ends. This can happen with degenerated loops like this one: * * 
     * for (;;) {
     *     try {
     *         break;
     *     } catch (UnresolvedException iioe) {
     *     }
     * }
     *
*/ public static void normalizeLoops(StructuredGraph graph) { boolean loopRemoved = false; for (LoopBeginNode begin : graph.getNodes(LoopBeginNode.TYPE)) { if (begin.loopEnds().isEmpty()) { assert begin.forwardEndCount() == 1; graph.reduceDegenerateLoopBegin(begin); loopRemoved = true; } else { normalizeLoopBegin(begin); } } if (loopRemoved) { /* * Removing a degenerated loop can make non-loop phi functions unnecessary. Therefore, * we re-check all phi functions and remove redundant ones. */ for (Node node : graph.getNodes()) { if (node instanceof PhiNode) { checkRedundantPhi((PhiNode) node); } } } } private static void normalizeLoopBegin(LoopBeginNode begin) { // Delete unnecessary loop phi functions, i.e., phi functions where all inputs are either // the same or the phi itself. for (PhiNode phi : begin.phis().snapshot()) { GraphUtil.checkRedundantPhi(phi); } for (LoopExitNode exit : begin.loopExits()) { for (ProxyNode vpn : exit.proxies().snapshot()) { GraphUtil.checkRedundantProxy(vpn); } } } /** * Gets an approximate source code location for a node if possible. * * @return the StackTraceElements if an approximate source location is found, null otherwise */ public static StackTraceElement[] approxSourceStackTraceElement(Node node) { NodeSourcePosition position = node.getNodeSourcePosition(); if (position != null) { // use GraphBuilderConfiguration and enable trackNodeSourcePosition to get better source // positions. return approxSourceStackTraceElement(position); } ArrayList elements = new ArrayList<>(); Node n = node; while (n != null) { if (n instanceof MethodCallTargetNode) { elements.add(((MethodCallTargetNode) n).targetMethod().asStackTraceElement(-1)); n = ((MethodCallTargetNode) n).invoke().asNode(); } if (n instanceof StateSplit) { FrameState state = ((StateSplit) n).stateAfter(); elements.addAll(Arrays.asList(approxSourceStackTraceElement(state))); break; } n = n.predecessor(); } return elements.toArray(new StackTraceElement[elements.size()]); } /** * Gets an approximate source code location for frame state. * * @return the StackTraceElements if an approximate source location is found, null otherwise */ public static StackTraceElement[] approxSourceStackTraceElement(FrameState frameState) { ArrayList elements = new ArrayList<>(); FrameState state = frameState; while (state != null) { Bytecode code = state.getCode(); if (code != null) { elements.add(code.asStackTraceElement(state.bci - 1)); } state = state.outerFrameState(); } return elements.toArray(new StackTraceElement[0]); } /** * Gets approximate stack trace elements for a bytecode position. */ public static StackTraceElement[] approxSourceStackTraceElement(BytecodePosition bytecodePosition) { ArrayList elements = new ArrayList<>(); BytecodePosition position = bytecodePosition; while (position != null) { ResolvedJavaMethod method = position.getMethod(); if (method != null) { elements.add(method.asStackTraceElement(position.getBCI())); } position = position.getCaller(); } return elements.toArray(new StackTraceElement[0]); } /** * Gets an approximate source code location for a node, encoded as an exception, if possible. * * @return the exception with the location */ public static RuntimeException approxSourceException(Node node, Throwable cause) { final StackTraceElement[] elements = approxSourceStackTraceElement(node); return createBailoutException(cause == null ? "" : cause.getMessage(), cause, elements); } /** * Creates a bailout exception with the given stack trace elements and message. * * @param message the message of the exception * @param elements the stack trace elements * @return the exception */ public static BailoutException createBailoutException(String message, Throwable cause, StackTraceElement[] elements) { return SourceStackTraceBailoutException.create(cause, message, elements); } /** * Gets an approximate source code location for a node if possible. * * @return a file name and source line number in stack trace format (e.g. "String.java:32") if * an approximate source location is found, null otherwise */ public static String approxSourceLocation(Node node) { StackTraceElement[] stackTraceElements = approxSourceStackTraceElement(node); if (stackTraceElements != null && stackTraceElements.length > 0) { StackTraceElement top = stackTraceElements[0]; if (top.getFileName() != null && top.getLineNumber() >= 0) { return top.getFileName() + ":" + top.getLineNumber(); } } return null; } /** * Returns a string representation of the given collection of objects. * * @param objects The {@link Iterable} that will be used to iterate over the objects. * @return A string of the format "[a, b, ...]". */ public static String toString(Iterable objects) { StringBuilder str = new StringBuilder(); str.append("["); for (Object o : objects) { str.append(o).append(", "); } if (str.length() > 1) { str.setLength(str.length() - 2); } str.append("]"); return str.toString(); } /** * Gets the original value by iterating through all {@link ValueProxy ValueProxies}. * * @param value the start value. * @return the first non-proxy value encountered */ public static ValueNode unproxify(ValueNode value) { if (value instanceof ValueProxy) { return unproxify((ValueProxy) value); } else { return value; } } /** * Gets the original value by iterating through all {@link ValueProxy ValueProxies}. * * @param value the start value proxy. * @return the first non-proxy value encountered */ public static ValueNode unproxify(ValueProxy value) { if (value != null) { ValueNode result = value.getOriginalNode(); while (result instanceof ValueProxy) { result = ((ValueProxy) result).getOriginalNode(); } return result; } else { return null; } } public static ValueNode skipPi(ValueNode node) { ValueNode n = node; while (n instanceof PiNode) { PiNode piNode = (PiNode) n; n = piNode.getOriginalNode(); } return n; } public static ValueNode skipPiWhileNonNull(ValueNode node) { ValueNode n = node; while (n instanceof PiNode) { PiNode piNode = (PiNode) n; ObjectStamp originalStamp = (ObjectStamp) piNode.getOriginalNode().stamp(); if (originalStamp.nonNull()) { n = piNode.getOriginalNode(); } else { break; } } return n; } /** * Looks for an {@link ArrayLengthProvider} while iterating through all {@link ValueProxy * ValueProxies}. * * @param value The start value. * @return The array length if one was found, or null otherwise. */ public static ValueNode arrayLength(ValueNode value) { ValueNode current = value; do { if (current instanceof ArrayLengthProvider) { ValueNode length = ((ArrayLengthProvider) current).length(); if (length != null) { return length; } } if (current instanceof ValueProxy) { current = ((ValueProxy) current).getOriginalNode(); } else { break; } } while (true); return null; } /** * Tries to find an original value of the given node by traversing through proxies and * unambiguous phis. Note that this method will perform an exhaustive search through phis. It is * intended to be used during graph building, when phi nodes aren't yet canonicalized. * * @param value The node whose original value should be determined. * @return The original value (which might be the input value itself). */ public static ValueNode originalValue(ValueNode value) { ValueNode result = originalValueSimple(value); assert result != null; return result; } private static ValueNode originalValueSimple(ValueNode value) { /* The very simple case: look through proxies. */ ValueNode cur = originalValueForProxy(value); while (cur instanceof PhiNode) { /* * We found a phi function. Check if we can analyze it without allocating temporary data * structures. */ PhiNode phi = (PhiNode) cur; ValueNode phiSingleValue = null; int count = phi.valueCount(); for (int i = 0; i < count; ++i) { ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i)); if (phiCurValue == phi) { /* Simple cycle, we can ignore the input value. */ } else if (phiSingleValue == null) { /* The first input. */ phiSingleValue = phiCurValue; } else if (phiSingleValue != phiCurValue) { /* Another input that is different from the first input. */ if (phiSingleValue instanceof PhiNode || phiCurValue instanceof PhiNode) { /* * We have two different input values for the phi function, and at least one * of the inputs is another phi function. We need to do a complicated * exhaustive check. */ return originalValueForComplicatedPhi(phi, new NodeBitMap(value.graph())); } else { /* * We have two different input values for the phi function, but none of them * is another phi function. This phi function cannot be reduce any further, * so the phi function is the original value. */ return phi; } } } /* * Successfully reduced the phi function to a single input value. The single input value * can itself be a phi function again, so we might take another loop iteration. */ assert phiSingleValue != null; cur = phiSingleValue; } /* We reached a "normal" node, which is the original value. */ assert !(cur instanceof LimitedValueProxy) && !(cur instanceof PhiNode); return cur; } private static ValueNode originalValueForProxy(ValueNode value) { ValueNode cur = value; while (cur instanceof LimitedValueProxy) { cur = ((LimitedValueProxy) cur).getOriginalNode(); } return cur; } /** * Handling for complicated nestings of phi functions. We need to reduce phi functions * recursively, and need a temporary map of visited nodes to avoid endless recursion of cycles. */ private static ValueNode originalValueForComplicatedPhi(PhiNode phi, NodeBitMap visited) { if (visited.isMarked(phi)) { /* * Found a phi function that was already seen. Either a cycle, or just a second phi * input to a path we have already processed. */ return null; } visited.mark(phi); ValueNode phiSingleValue = null; int count = phi.valueCount(); for (int i = 0; i < count; ++i) { ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i)); if (phiCurValue instanceof PhiNode) { /* Recursively process a phi function input. */ phiCurValue = originalValueForComplicatedPhi((PhiNode) phiCurValue, visited); } if (phiCurValue == null) { /* Cycle to a phi function that was already seen. We can ignore this input. */ } else if (phiSingleValue == null) { /* The first input. */ phiSingleValue = phiCurValue; } else if (phiCurValue != phiSingleValue) { /* * Another input that is different from the first input. Since we already * recursively looked through other phi functions, we now know that this phi * function cannot be reduce any further, so the phi function is the original value. */ return phi; } } return phiSingleValue; } public static boolean tryKillUnused(Node node) { if (node.isAlive() && isFloatingNode(node) && node.hasNoUsages() && !(node instanceof GuardNode)) { killWithUnusedFloatingInputs(node); return true; } return false; } /** * Returns an iterator that will return the given node followed by all its predecessors, up * until the point where {@link Node#predecessor()} returns null. * * @param start the node at which to start iterating */ public static NodeIterable predecessorIterable(final FixedNode start) { return new NodeIterable() { @Override public Iterator iterator() { return new Iterator() { public FixedNode current = start; @Override public boolean hasNext() { return current != null; } @Override public FixedNode next() { try { return current; } finally { current = (FixedNode) current.predecessor(); } } }; } }; } private static final class DefaultSimplifierTool implements SimplifierTool { private final MetaAccessProvider metaAccess; private final ConstantReflectionProvider constantReflection; private final ConstantFieldProvider constantFieldProvider; private final boolean canonicalizeReads; private final Assumptions assumptions; private final OptionValues options; private final LoweringProvider loweringProvider; DefaultSimplifierTool(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, boolean canonicalizeReads, Assumptions assumptions, OptionValues options, LoweringProvider loweringProvider) { this.metaAccess = metaAccess; this.constantReflection = constantReflection; this.constantFieldProvider = constantFieldProvider; this.canonicalizeReads = canonicalizeReads; this.assumptions = assumptions; this.options = options; this.loweringProvider = loweringProvider; } @Override public MetaAccessProvider getMetaAccess() { return metaAccess; } @Override public ConstantReflectionProvider getConstantReflection() { return constantReflection; } @Override public ConstantFieldProvider getConstantFieldProvider() { return constantFieldProvider; } @Override public boolean canonicalizeReads() { return canonicalizeReads; } @Override public boolean allUsagesAvailable() { return true; } @Override public void deleteBranch(Node branch) { FixedNode fixedBranch = (FixedNode) branch; fixedBranch.predecessor().replaceFirstSuccessor(fixedBranch, null); GraphUtil.killCFG(fixedBranch); } @Override public void removeIfUnused(Node node) { GraphUtil.tryKillUnused(node); } @Override public void addToWorkList(Node node) { } @Override public void addToWorkList(Iterable nodes) { } @Override public Assumptions getAssumptions() { return assumptions; } @Override public OptionValues getOptions() { return options; } @Override public Integer smallestCompareWidth() { if (loweringProvider != null) { return loweringProvider.smallestCompareWidth(); } else { return null; } } } public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, boolean canonicalizeReads, Assumptions assumptions, OptionValues options) { return getDefaultSimplifier(metaAccess, constantReflection, constantFieldProvider, canonicalizeReads, assumptions, options, null); } public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, boolean canonicalizeReads, Assumptions assumptions, OptionValues options, LoweringProvider loweringProvider) { return new DefaultSimplifierTool(metaAccess, constantReflection, constantFieldProvider, canonicalizeReads, assumptions, options, loweringProvider); } public static Constant foldIfConstantAndRemove(ValueNode node, ValueNode constant) { assert node.inputs().contains(constant); if (constant.isConstant()) { node.replaceFirstInput(constant, null); Constant result = constant.asConstant(); tryKillUnused(constant); return result; } return null; } /** * Virtualize an array copy. * * @param tool the virtualization tool * @param source the source array * @param sourceLength the length of the source array * @param newLength the length of the new array * @param from the start index in the source array * @param newComponentType the component type of the new array * @param elementKind the kind of the new array elements * @param graph the node graph * @param virtualArrayProvider a functional provider that returns a new virtual array given the * component type and length */ public static void virtualizeArrayCopy(VirtualizerTool tool, ValueNode source, ValueNode sourceLength, ValueNode newLength, ValueNode from, ResolvedJavaType newComponentType, JavaKind elementKind, StructuredGraph graph, BiFunction virtualArrayProvider) { ValueNode sourceAlias = tool.getAlias(source); ValueNode replacedSourceLength = tool.getAlias(sourceLength); ValueNode replacedNewLength = tool.getAlias(newLength); ValueNode replacedFrom = tool.getAlias(from); if (!replacedNewLength.isConstant() || !replacedFrom.isConstant() || !replacedSourceLength.isConstant()) { return; } assert newComponentType != null : "An array copy can be virtualized only if the real type of the resulting array is known statically."; int fromInt = replacedFrom.asJavaConstant().asInt(); int newLengthInt = replacedNewLength.asJavaConstant().asInt(); int sourceLengthInt = replacedSourceLength.asJavaConstant().asInt(); if (sourceAlias instanceof VirtualObjectNode) { VirtualObjectNode sourceVirtual = (VirtualObjectNode) sourceAlias; assert sourceLengthInt == sourceVirtual.entryCount(); } if (fromInt < 0 || newLengthInt < 0 || fromInt > sourceLengthInt) { /* Illegal values for either from index, the new length or the source length. */ return; } if (newLengthInt >= tool.getMaximumEntryCount()) { /* The new array size is higher than maximum allowed size of virtualized objects. */ return; } ValueNode[] newEntryState = new ValueNode[newLengthInt]; int readLength = Math.min(newLengthInt, sourceLengthInt - fromInt); if (sourceAlias instanceof VirtualObjectNode) { /* The source array is virtualized, just copy over the values. */ VirtualObjectNode sourceVirtual = (VirtualObjectNode) sourceAlias; for (int i = 0; i < readLength; i++) { newEntryState[i] = tool.getEntry(sourceVirtual, fromInt + i); } } else { /* The source array is not virtualized, emit index loads. */ for (int i = 0; i < readLength; i++) { LoadIndexedNode load = new LoadIndexedNode(null, sourceAlias, ConstantNode.forInt(i + fromInt, graph), elementKind); tool.addNode(load); newEntryState[i] = load; } } if (readLength < newLengthInt) { /* Pad the copy with the default value of its elment kind. */ ValueNode defaultValue = ConstantNode.defaultForKind(elementKind, graph); for (int i = readLength; i < newLengthInt; i++) { newEntryState[i] = defaultValue; } } /* Perform the replacement. */ VirtualArrayNode newVirtualArray = virtualArrayProvider.apply(newComponentType, newLengthInt); tool.createVirtualObject(newVirtualArray, newEntryState, Collections. emptyList(), false); tool.replaceWithVirtual(newVirtualArray); } }