/*
 * 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 static org.graalvm.compiler.graph.Graph.Options.VerifyGraalGraphEdges;
import static org.graalvm.compiler.nodes.util.GraphUtil.Options.VerifyKillCFGUnusedNodes;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;

import org.graalvm.compiler.bytecode.Bytecode;
import org.graalvm.compiler.code.SourceStackTraceBailoutException;
import org.graalvm.compiler.core.common.CollectionsFactory;
import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
import org.graalvm.compiler.core.common.type.StampFactory;
import org.graalvm.compiler.debug.Debug;
import org.graalvm.compiler.graph.Graph;
import org.graalvm.compiler.graph.Node;
import org.graalvm.compiler.graph.NodeClass;
import org.graalvm.compiler.graph.NodeWorkList;
import org.graalvm.compiler.graph.Position;
import org.graalvm.compiler.graph.iterators.NodeIterable;
import org.graalvm.compiler.graph.spi.SimplifierTool;
import org.graalvm.compiler.nodeinfo.InputType;
import org.graalvm.compiler.nodeinfo.NodeInfo;
import org.graalvm.compiler.nodes.AbstractBeginNode;
import org.graalvm.compiler.nodes.AbstractEndNode;
import org.graalvm.compiler.nodes.AbstractMergeNode;
import org.graalvm.compiler.nodes.FixedNode;
import org.graalvm.compiler.nodes.FixedWithNextNode;
import org.graalvm.compiler.nodes.FrameState;
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.ProxyNode;
import org.graalvm.compiler.nodes.StateSplit;
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.ValueNode;
import org.graalvm.compiler.nodes.calc.FloatingNode;
import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
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.options.Option;
import org.graalvm.compiler.options.OptionType;
import org.graalvm.compiler.options.OptionValue;

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.MetaAccessProvider;
import jdk.vm.ci.meta.ResolvedJavaMethod;

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 OptionValue<Boolean> VerifyKillCFGUnusedNodes = new OptionValue<>(false);
    }

    @SuppressWarnings("try")
    public static void killCFG(FixedNode node, SimplifierTool tool) {
        try (Debug.Scope scope = Debug.scope("KillCFG", node)) {
            Set<Node> unusedNodes = null;
            Set<Node> unsafeNodes = null;
            Graph.NodeEventScope nodeEventScope = null;
            if (VerifyGraalGraphEdges.getValue()) {
                unsafeNodes = collectUnsafeNodes(node.graph());
            }
            if (VerifyKillCFGUnusedNodes.getValue()) {
                Set<Node> collectedUnusedNodes = unusedNodes = CollectionsFactory.newSet();
                nodeEventScope = node.graph().trackNodeEvents(new Graph.NodeEventListener() {
                    @Override
                    public void event(Graph.NodeEvent e, Node n) {
                        if (e == Graph.NodeEvent.ZERO_USAGES && isFloatingNode(n)) {
                            collectedUnusedNodes.add(n);
                        }
                    }
                });
            }
            Debug.dump(Debug.VERY_DETAILED_LOG_LEVEL, node.graph(), "Before killCFG %s", node);
            NodeWorkList worklist = killCFG(node, tool, null);
            if (worklist != null) {
                for (Node n : worklist) {
                    killCFG(n, tool, worklist);
                }
            }
            if (VerifyGraalGraphEdges.getValue()) {
                Set<Node> newUnsafeNodes = collectUnsafeNodes(node.graph());
                newUnsafeNodes.removeAll(unsafeNodes);
                assert newUnsafeNodes.isEmpty() : "New unsafe nodes: " + newUnsafeNodes;
            }
            if (VerifyKillCFGUnusedNodes.getValue()) {
                nodeEventScope.close();
                unusedNodes.removeIf(n -> n.isDeleted());
                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.
/**
     * Collects all node in the graph which have non-optional inputs that are null.
     */
    private static Set<Node> collectUnsafeNodes(Graph graph) {
        Set<Node> unsafeNodes = CollectionsFactory.newSet();
        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;
    }

    private static NodeWorkList killCFG(Node node, SimplifierTool tool, NodeWorkList worklist) {
        NodeWorkList newWorklist = worklist;
        if (node instanceof FixedNode) {
            newWorklist = killCFGLinear((FixedNode) node, newWorklist, tool);
        } else {
            newWorklist = propagateKill(node, newWorklist);
            Debug.dump(Debug.VERY_DETAILED_LOG_LEVEL, node.graph(), "killCFG (Floating) %s", node);
        }
        return newWorklist;
    }

    private static NodeWorkList killCFGLinear(FixedNode in, NodeWorkList worklist, SimplifierTool tool) {
        NodeWorkList newWorklist = worklist;
        FixedNode current = in;
        while (current != null) {
            FixedNode next = null;
            assert current.isAlive();
            if (current instanceof AbstractEndNode) {
                // We reached a control flow end.
                AbstractEndNode end = (AbstractEndNode) current;
                newWorklist = killEnd(end, newWorklist, tool);
            } else if (current instanceof FixedWithNextNode) {
                // Node guaranteed to have a single successor
                FixedWithNextNode fixedWithNext = (FixedWithNextNode) current;
                assert fixedWithNext.successors().count() == 1 || fixedWithNext.successors().count() == 0;
                assert fixedWithNext.successors().first() == fixedWithNext.next();
                next = fixedWithNext.next();
            } else {
                /*
                 * We do not take a successor snapshot because this iterator supports concurrent
                 * modifications as long as they do not change the size of the successor list. Not
                 * taking a snapshot allows us to see modifications to other branches that may
                 * happen while processing one branch.
                 */
                Iterator<Node> successors = current.successors().iterator();
                if (successors.hasNext()) {
                    Node first = successors.next();
                    if (!successors.hasNext()) {
                        next = (FixedNode) first;
                    } else {
                        if (newWorklist == null) {
                            newWorklist = in.graph().createNodeWorkList();
                        }
                        for (Node successor : current.successors()) {
                            newWorklist.add(successor);
                            if (successor instanceof LoopExitNode) {
                                LoopExitNode exit = (LoopExitNode) successor;
                                exit.replaceFirstInput(exit.loopBegin(), null);
                            }
                        }
                    }
                }
            }
            current.replaceAtPredecessor(null);
            newWorklist = propagateKill(current, newWorklist);
            Debug.dump(Debug.VERY_DETAILED_LOG_LEVEL, current.graph(), "killCFGLinear %s", current);
            current = next;
        }
        Debug.dump(Debug.DETAILED_LOG_LEVEL, in.graph(), "killCFGLinear %s", in);
        return newWorklist;
    }

    public static void killCFG(FixedNode node) {
        killCFG(node, null);
    }

    
Node type used temporarily while deleting loops. It is used as replacement for the loop PhiNodes in order to break data-flow cycles before deleting the loop. The control-flow of the whole loop is killed before killing the poison node if they are still alive. /**
     * Node type used temporarily while deleting loops.
     *
     * It is used as replacement for the loop {@link PhiNode PhiNodes} in order to break data-flow
     * cycles before deleting the loop. The control-flow of the whole loop is killed before killing
     * the poison node if they are still alive.
     */
    @NodeInfo(allowedUsageTypes = InputType.Unchecked)
    private static final class PoisonNode extends FloatingNode {
        public static final NodeClass<PoisonNode> TYPE = NodeClass.create(PoisonNode.class);

        protected PoisonNode() {
            super(TYPE, StampFactory.forVoid());
        }
    }

    private static NodeWorkList killEnd(AbstractEndNode end, NodeWorkList worklist, SimplifierTool tool) {
        NodeWorkList newWorklist = worklist;
        AbstractMergeNode merge = end.merge();
        if (merge != null) {
            merge.removeEnd(end);
            StructuredGraph graph = end.graph();
            if (merge instanceof LoopBeginNode && merge.forwardEndCount() == 0) {
                // dead loop
                LoopBeginNode begin = (LoopBeginNode) merge;
                // disconnect and delete loop ends & loop exits
                for (LoopEndNode loopend : begin.loopEnds().snapshot()) {
                    loopend.predecessor().replaceFirstSuccessor(loopend, null);
                    loopend.safeDelete();
                }
                // clean unused proxies to avoid creating new unused nodes
                for (LoopExitNode exit : begin.loopExits()) {
                    for (ProxyNode vpn : exit.proxies().snapshot()) {
                        tryKillUnused(vpn);
                    }
                }
                begin.removeExits();
                PoisonNode poison = null;
                if (merge.phis().isNotEmpty()) {
                    poison = graph.unique(new PoisonNode());
                    for (PhiNode phi : merge.phis()) {
                        phi.replaceAtUsages(poison);
                    }
                    for (PhiNode phi : merge.phis().snapshot()) {
                        killWithUnusedFloatingInputs(phi);
                    }
                }
                FixedNode loopBody = begin.next();
                Debug.dump(Debug.VERY_DETAILED_LOG_LEVEL, end.graph(), "killEnd (Loop) %s after initial loop cleanup", end);
                if (loopBody != null) {
                    // for small infinite loops, the body may already be killed while killing the
                    // LoopEnds
                    newWorklist = killCFG(loopBody, tool, worklist);
                }
                FrameState frameState = begin.stateAfter();
                begin.safeDelete();
                if (frameState != null) {
                    tryKillUnused(frameState);
                }
                if (poison != null && poison.isAlive()) {
                    if (newWorklist == null) {
                        newWorklist = graph.createNodeWorkList();
                    }
                    // drain the worklist to finish the loop before adding the poison
                    for (Node n : newWorklist) {
                        killCFG(n, tool, newWorklist);
                    }
                    if (poison.isAlive()) {
                        newWorklist.add(poison);
                    }
                }
            } else if (merge instanceof LoopBeginNode && ((LoopBeginNode) merge).loopEnds().isEmpty()) {
                // not a loop anymore
                if (tool != null) {
                    for (PhiNode phi : merge.phis()) {
                        tool.addToWorkList(phi.usages());
                    }
                }
                graph.reduceDegenerateLoopBegin((LoopBeginNode) merge);
            } else if (merge.phiPredecessorCount() == 1) {
                // not a merge anymore
                if (tool != null) {
                    for (PhiNode phi : merge.phis()) {
                        tool.addToWorkList(phi.usages());
                    }
                }
                graph.reduceTrivialMerge(merge);
            }
        }
        return newWorklist;
    }

    public static boolean isFloatingNode(Node n) {
        return !(n instanceof FixedNode);
    }

    private static NodeWorkList propagateKill(Node node, NodeWorkList workList) {
        NodeWorkList newWorkList = workList;
        if (node != null && node.isAlive()) {
            for (Node usage : node.usages().snapshot()) {
                assert usage.isAlive();
                if (isFloatingNode(usage)) {
                    boolean addUsage = false;
                    if (usage instanceof PhiNode) {
                        PhiNode phi = (PhiNode) usage;
                        assert phi.merge() != null;
                        if (phi.merge() == node) {
                            // we reach the phi directly through he merge, queue it.
                            addUsage = true;
                        } else {
                            // we reach it though a value
                            assert phi.values().contains(node);
                            // let that be handled when we reach the corresponding End node
                        }
                    } else {
                        addUsage = true;
                    }
                    if (addUsage) {
                        if (newWorkList == null) {
                            newWorkList = node.graph().createNodeWorkList();
                        }
                        newWorkList.add(usage);
                    }
                }
                usage.replaceFirstInput(node, null);
            }
            killWithUnusedFloatingInputs(node);
        }
        return newWorkList;
    }

    private static boolean checkKill(Node 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) {
        assert checkKill(node);
        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()) {
                        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 mark, assuming no "old" nodes point to "new" nodes. /**
     * 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.singleValue();
        if (singleValue != PhiNode.MULTIPLE_VALUES) {
            Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot();
            Collection<ProxyNode> 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<PhiNode> phiUsages = vpn.usages().filter(PhiNode.class).snapshot();
                    Collection<ProxyNode> 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) {
    }
}

/**
     * Remove loop header without loop ends. This can happen with degenerated loops like this one:
     *
     * <pre>
     * for (;;) {
     *     try {
     *         break;
     *     } catch (UnresolvedException iioe) {
     *     }
     * }
     * </pre>
     */
    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.
Returns:
the StackTraceElements if an approximate source location is found, null otherwise/**
     * 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) {
        ArrayList<StackTraceElement> 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.
Returns:
the StackTraceElements if an approximate source location is found, null otherwise/**
     * 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<StackTraceElement> 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.
/**
     * Gets approximate stack trace elements for a bytecode position.
     */
    public static StackTraceElement[] approxSourceStackTraceElement(BytecodePosition bytecodePosition) {
        ArrayList<StackTraceElement> 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.
Returns:
the exception with the location/**
     * 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.
Params:
message – the message of the exception
elements – the stack trace elements
Returns:
the exception/**
     * 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.
Returns:
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/**
     * 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.
Params:
objects – The Iterable that will be used to iterate over the objects.
Returns:
A string of the format "[a, b, ...]"./**
     * 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 ValueProxies. 
Params:
value – The start value.
Returns:
The first non-proxy value encountered./**
     * 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) {
        ValueNode result = value;
        while (result instanceof ValueProxy) {
            result = ((ValueProxy) result).getOriginalNode();
        }
        return result;
    }

    
Looks for an ArrayLengthProvider while iterating through all 
ValueProxies. 
Params:
value – The start value.
Returns:
The array length if one was found, or null otherwise./**
     * 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.
Params:
proxy – The node whose original value should be determined./**
     * 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 proxy The node whose original value should be determined.
     */
    public static ValueNode originalValue(ValueNode proxy) {
        ValueNode v = proxy;
        do {
            if (v instanceof LimitedValueProxy) {
                v = ((LimitedValueProxy) v).getOriginalNode();
            } else if (v instanceof PhiNode) {
                v = ((PhiNode) v).singleValue();
                if (v == PhiNode.MULTIPLE_VALUES) {
                    v = null;
                }
            } else {
                break;
            }
        } while (v != null);

        if (v == null) {
            v = new OriginalValueSearch(proxy).result;
        }
        return v;
    }

    public static boolean tryKillUnused(Node node) {
        if (node.isAlive() && isFloatingNode(node) && node.hasNoUsages()) {
            killWithUnusedFloatingInputs(node);
            return true;
        }
        return false;
    }

    
Exhaustive search for GraphUtil.originalValue(ValueNode) when a simple search fails. This can happen in the presence of complicated phi/proxy/phi constructs. /**
     * Exhaustive search for {@link GraphUtil#originalValue(ValueNode)} when a simple search fails.
     * This can happen in the presence of complicated phi/proxy/phi constructs.
     */
    static class OriginalValueSearch {
        ValueNode result;

        OriginalValueSearch(ValueNode proxy) {
            NodeWorkList worklist = proxy.graph().createNodeWorkList();
            worklist.add(proxy);
            for (Node node : worklist) {
                if (node instanceof LimitedValueProxy) {
                    ValueNode originalValue = ((LimitedValueProxy) node).getOriginalNode();
                    if (!process(originalValue, worklist)) {
                        return;
                    }
                } else if (node instanceof PhiNode) {
                    for (Node value : ((PhiNode) node).values()) {
                        if (!process((ValueNode) value, worklist)) {
                            return;
                        }
                    }
                } else {
                    if (!process((ValueNode) node, null)) {
                        return;
                    }
                }
            }
        }

        
Process a node as part of this search.
Params:
node – the next node encountered in the search
worklist – if non-null, node will be added to this list. Otherwise, node is treated as a candidate result.
Returns:
true if the search should continue, false if a definitive result has been found/**
         * Process a node as part of this search.
         *
         * @param node the next node encountered in the search
         * @param worklist if non-null, {@code node} will be added to this list. Otherwise,
         *            {@code node} is treated as a candidate result.
         * @return true if the search should continue, false if a definitive {@link #result} has
         *         been found
         */
        private boolean process(ValueNode node, NodeWorkList worklist) {
            if (node.isAlive()) {
                if (worklist == null) {
                    if (result == null) {
                        // Initial candidate result: continue search
                        result = node;
                    } else if (result != node) {
                        // Conflicts with existing candidate: stop search with null result
                        result = null;
                        return false;
                    }
                } else {
                    worklist.add(node);
                }
            }
            return true;
        }
    }

    
Returns an iterator that will return the given node followed by all its predecessors, up until the point where Node.predecessor() returns null. 
Params:
start – the node at which to start iterating/**
     * 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<FixedNode> predecessorIterable(final FixedNode start) {
        return new NodeIterable<FixedNode>() {
            @Override
            public Iterator<FixedNode> iterator() {
                return new Iterator<FixedNode>() {
                    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 LoweringProvider loweringProvider;

        DefaultSimplifierTool(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, boolean canonicalizeReads,
                        Assumptions assumptions, LoweringProvider loweringProvider) {
            this.metaAccess = metaAccess;
            this.constantReflection = constantReflection;
            this.constantFieldProvider = constantFieldProvider;
            this.canonicalizeReads = canonicalizeReads;
            this.assumptions = assumptions;
            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, this);
        }

        @Override
        public void removeIfUnused(Node node) {
            GraphUtil.tryKillUnused(node);
        }

        @Override
        public void addToWorkList(Node node) {
        }

        @Override
        public void addToWorkList(Iterable<? extends Node> nodes) {
        }

        @Override
        public Assumptions getAssumptions() {
            return assumptions;
        }

        @Override
        public boolean supportSubwordCompare(int bits) {
            if (loweringProvider != null) {
                return loweringProvider.supportSubwordCompare(bits);
            } else {
                return false;
            }
        }
    }

    public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
                    boolean canonicalizeReads, Assumptions assumptions) {
        return getDefaultSimplifier(metaAccess, constantReflection, constantFieldProvider, canonicalizeReads, assumptions, null);
    }

    public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
                    boolean canonicalizeReads, Assumptions assumptions, LoweringProvider loweringProvider) {
        return new DefaultSimplifierTool(metaAccess, constantReflection, constantFieldProvider, canonicalizeReads, assumptions, 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;
    }
}