/*

 * Copyright (c) 2011, 2011, 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.phases.graph;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Deque;

import java.util.List;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeBitMap;

import org.graalvm.compiler.nodes.AbstractBeginNode;

import org.graalvm.compiler.nodes.AbstractMergeNode;

import org.graalvm.compiler.nodes.ControlSinkNode;

import org.graalvm.compiler.nodes.ControlSplitNode;

import org.graalvm.compiler.nodes.EndNode;

import org.graalvm.compiler.nodes.FixedNode;

import org.graalvm.compiler.nodes.FixedWithNextNode;

import org.graalvm.compiler.nodes.Invoke;

import org.graalvm.compiler.nodes.InvokeWithExceptionNode;

import org.graalvm.compiler.nodes.LoopBeginNode;

import org.graalvm.compiler.nodes.LoopEndNode;

import org.graalvm.compiler.nodes.StartNode;

import org.graalvm.compiler.nodes.StructuredGraph;

/**

 * A SinglePassNodeIterator iterates the fixed nodes of the graph in post order starting from its

 * start node. Unlike in iterative dataflow analysis, a single pass is performed, which allows

 * keeping a smaller working set of pending {@link MergeableState}. This iteration scheme requires:

 * <ul>

 * <li>{@link MergeableState#merge(AbstractMergeNode, List)} to always return <code>true</code> (an

 * assertion checks this)</li>

 * <li>{@link #controlSplit(ControlSplitNode)} to always return all successors (otherwise, not all

 * associated {@link EndNode} will be visited. In turn, visiting all the end nodes for a given

 * {@link AbstractMergeNode} is a precondition before that merge node can be visited)</li>

 * </ul>

 *

 * <p>

 * For this iterator the CFG is defined by the classical CFG nodes (

 * {@link org.graalvm.compiler.nodes.ControlSplitNode},

 * {@link org.graalvm.compiler.nodes.AbstractMergeNode} ...) and the

 * {@link org.graalvm.compiler.nodes.FixedWithNextNode#next() next} pointers of

 * {@link org.graalvm.compiler.nodes.FixedWithNextNode}.

 * </p>

 *

 * <p>

 * The lifecycle that single-pass node iterators go through is described in {@link #apply()}

 * </p>

 *

 * @param <T> the type of {@link MergeableState} handled by this SinglePassNodeIterator

 */

public abstract class SinglePassNodeIterator<T extends MergeableState<T>> {

    private final NodeBitMap visitedEnds;

    /**

     * @see SinglePassNodeIterator.PathStart

     */

    private final Deque<PathStart<T>> nodeQueue;

    /**

     * The keys in this map may be:

     * <ul>

     * <li>loop-begins and loop-ends, see {@link #finishLoopEnds(LoopEndNode)}</li>

     * <li>forward-ends of merge-nodes, see {@link #queueMerge(EndNode)}</li>

     * </ul>

     *

     * <p>

     * It's tricky to answer whether the state an entry contains is the pre-state or the post-state

     * for the key in question, because states are mutable. Thus an entry may be created to contain

     * a pre-state (at the time, as done for a loop-begin in {@link #apply()}) only to make it a

     * post-state soon after (continuing with the loop-begin example, also in {@link #apply()}). In

     * any case, given that keys are limited to the nodes mentioned in the previous paragraph, in

     * all cases an entry can be considered to hold a post-state by the time such entry is

     * retrieved.

     * </p>

     *

     * <p>

     * The only method that makes this map grow is {@link #keepForLater(FixedNode, MergeableState)}

     * and the only one that shrinks it is {@link #pruneEntry(FixedNode)}. To make sure no entry is

     * left behind inadvertently, asserts in {@link #finished()} are in place.

     * </p>

     */

    private final EconomicMap<FixedNode, T> nodeStates;

    private final StartNode start;

    protected T state;

    /**

     * An item queued in {@link #nodeQueue} can be used to continue with the single-pass visit after

     * the previous path can't be followed anymore. Such items are:

     * <ul>

     * <li>de-queued via {@link #nextQueuedNode()}</li>

     * <li>en-queued via {@link #queueMerge(EndNode)} and {@link #queueSuccessors(FixedNode)}</li>

     * </ul>

     *

     * <p>

     * Correspondingly each item may stand for:

     * <ul>

     * <li>a {@link AbstractMergeNode} whose pre-state results from merging those of its

     * forward-ends, see {@link #nextQueuedNode()}</li>

     * <li>a successor of a control-split node, in which case the state on entry to it (the

     * successor) is also stored in the item, see {@link #nextQueuedNode()}</li>

     * </ul>

     * </p>

     */

    private static final class PathStart<U> {

        private final AbstractBeginNode node;

        private final U stateOnEntry;

        private PathStart(AbstractBeginNode node, U stateOnEntry) {

            this.node = node;

            this.stateOnEntry = stateOnEntry;

            assert repOK();

        }

        /**

         * @return true iff this instance is internally consistent (ie, its "representation is OK")

         */

        private boolean repOK() {

            if (node == null) {

                return false;

            }

            if (node instanceof AbstractMergeNode) {

                return stateOnEntry == null;

            }

            return (stateOnEntry != null);

        }

    }

    public SinglePassNodeIterator(StartNode start, T initialState) {

        StructuredGraph graph = start.graph();

        visitedEnds = graph.createNodeBitMap();

        nodeQueue = new ArrayDeque<>();

        nodeStates = EconomicMap.create(Equivalence.IDENTITY);

        this.start = start;

        this.state = initialState;

    }

    /**

     * Performs a single-pass iteration.

     *

     * <p>

     * After this method has been invoked, the {@link SinglePassNodeIterator} instance can't be used

     * again. This saves clearing up fields in {@link #finished()}, the assumption being that this

     * instance will be garbage-collected soon afterwards.

     * </p>

     */

    public void apply() {

        FixedNode current = start;

        do {

            if (current instanceof InvokeWithExceptionNode) {

                invoke((Invoke) current);

                queueSuccessors(current);

                current = nextQueuedNode();

            } else if (current instanceof LoopBeginNode) {

                state.loopBegin((LoopBeginNode) current);

                keepForLater(current, state);

                state = state.clone();

                loopBegin((LoopBeginNode) current);

                current = ((LoopBeginNode) current).next();

                assert current != null;

            } else if (current instanceof LoopEndNode) {

                loopEnd((LoopEndNode) current);

                finishLoopEnds((LoopEndNode) current);

                current = nextQueuedNode();

            } else if (current instanceof AbstractMergeNode) {

                merge((AbstractMergeNode) current);

                current = ((AbstractMergeNode) current).next();

                assert current != null;

            } else if (current instanceof FixedWithNextNode) {

                FixedNode next = ((FixedWithNextNode) current).next();

                assert next != null : current;

                node(current);

                current = next;

            } else if (current instanceof EndNode) {

                end((EndNode) current);

                queueMerge((EndNode) current);

                current = nextQueuedNode();

            } else if (current instanceof ControlSinkNode) {

                node(current);

                current = nextQueuedNode();

            } else if (current instanceof ControlSplitNode) {

                controlSplit((ControlSplitNode) current);

                queueSuccessors(current);

                current = nextQueuedNode();

            } else {

                assert false : current;

            }

        } while (current != null);

        finished();

    }

    /**

     * Two methods enqueue items in {@link #nodeQueue}. Of them, only this method enqueues items

     * with non-null state (the other method being {@link #queueMerge(EndNode)}).

     *

     * <p>

     * A space optimization is made: the state is cloned for all successors except the first. Given

     * that right after invoking this method, {@link #nextQueuedNode()} is invoked, that single

     * non-cloned state instance is in effect "handed over" to its next owner (thus realizing an

     * owner-is-mutator access protocol).

     * </p>

     */

    private void queueSuccessors(FixedNode x) {

        T startState = state;

        T curState = startState;

        for (Node succ : x.successors()) {

            if (succ != null) {

                if (curState == null) {

                    // the current state isn't cloned for the first successor

                    // conceptually, the state is handed over to it

                    curState = startState.clone();

                }

                AbstractBeginNode begin = (AbstractBeginNode) succ;

                nodeQueue.addFirst(new PathStart<>(begin, curState));

            }

        }

    }

    /**

     * This method is invoked upon not having a (single) next {@link FixedNode} to visit. This

     * method picks such next-node-to-visit from {@link #nodeQueue} and updates {@link #state} with

     * the pre-state for that node.

     *

     * <p>

     * Upon reaching a {@link AbstractMergeNode}, some entries are pruned from {@link #nodeStates}

     * (ie, the entries associated to forward-ends for that merge-node).

     * </p>

     */

    private FixedNode nextQueuedNode() {

        if (nodeQueue.isEmpty()) {

            return null;

        }

        PathStart<T> elem = nodeQueue.removeFirst();

        if (elem.node instanceof AbstractMergeNode) {

            AbstractMergeNode merge = (AbstractMergeNode) elem.node;

            state = pruneEntry(merge.forwardEndAt(0));

            ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1);

            for (int i = 1; i < merge.forwardEndCount(); i++) {

                T other = pruneEntry(merge.forwardEndAt(i));

                states.add(other);

            }

            boolean ready = state.merge(merge, states);

            assert ready : "Not a single-pass iterator after all";

            return merge;

        } else {

            AbstractBeginNode begin = elem.node;

            assert begin.predecessor() != null;

            state = elem.stateOnEntry;

            state.afterSplit(begin);

            return begin;

        }

    }

    /**

     * Once all loop-end-nodes for a given loop-node have been visited.

     * <ul>

     * <li>the state for that loop-node is updated based on the states of the loop-end-nodes</li>

     * <li>entries in {@link #nodeStates} are pruned for the loop (they aren't going to be looked up

     * again, anyway)</li>

     * </ul>

     *

     * <p>

     * The entries removed by this method were inserted:

     * <ul>

     * <li>for the loop-begin, by {@link #apply()}</li>

     * <li>for loop-ends, by (previous) invocations of this method</li>

     * </ul>

     * </p>

     */

    private void finishLoopEnds(LoopEndNode end) {

        assert !visitedEnds.isMarked(end);

        visitedEnds.mark(end);

        keepForLater(end, state);

        LoopBeginNode begin = end.loopBegin();

        boolean endsVisited = true;

        for (LoopEndNode le : begin.loopEnds()) {

            if (!visitedEnds.isMarked(le)) {

                endsVisited = false;

                break;

            }

        }

        if (endsVisited) {

            ArrayList<T> states = new ArrayList<>(begin.loopEnds().count());

            for (LoopEndNode le : begin.orderedLoopEnds()) {

                T leState = pruneEntry(le);

                states.add(leState);

            }

            T loopBeginState = pruneEntry(begin);

            loopBeginState.loopEnds(begin, states);

        }

    }

    /**

     * Once all end-nodes for a given merge-node have been visited, that merge-node is added to the

     * {@link #nodeQueue}

     *

     * <p>

     * {@link #nextQueuedNode()} is in charge of pruning entries (held by {@link #nodeStates}) for

     * the forward-ends inserted by this method.

     * </p>

     */

    private void queueMerge(EndNode end) {

        assert !visitedEnds.isMarked(end);

        visitedEnds.mark(end);

        keepForLater(end, state);

        AbstractMergeNode merge = end.merge();

        boolean endsVisited = true;

        for (int i = 0; i < merge.forwardEndCount(); i++) {

            if (!visitedEnds.isMarked(merge.forwardEndAt(i))) {

                endsVisited = false;

                break;

            }

        }

        if (endsVisited) {

            nodeQueue.add(new PathStart<>(merge, null));

        }

    }

    protected abstract void node(FixedNode node);

    protected void end(EndNode endNode) {

        node(endNode);

    }

    protected void merge(AbstractMergeNode merge) {

        node(merge);

    }

    protected void loopBegin(LoopBeginNode loopBegin) {

        node(loopBegin);

    }

    protected void loopEnd(LoopEndNode loopEnd) {

        node(loopEnd);

    }

    protected void controlSplit(ControlSplitNode controlSplit) {

        node(controlSplit);

    }

    protected void invoke(Invoke invoke) {

        node(invoke.asNode());

    }

    /**

     * The lifecycle that single-pass node iterators go through is described in {@link #apply()}

     *

     * <p>

     * When overriding this method don't forget to invoke this implementation, otherwise the

     * assertions will be skipped.

     * </p>

     */

    protected void finished() {

        assert nodeQueue.isEmpty();

        assert nodeStates.isEmpty();

    }

    private void keepForLater(FixedNode x, T s) {

        assert !nodeStates.containsKey(x);

        assert (x instanceof LoopBeginNode) || (x instanceof LoopEndNode) || (x instanceof EndNode);

        assert s != null;

        nodeStates.put(x, s);

    }

    private T pruneEntry(FixedNode x) {

        T result = nodeStates.removeKey(x);

        assert result != null;

        return result;

    }

}