001/*
002 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.graph;
024
025import java.util.*;
026
027import com.oracle.graal.graph.*;
028import com.oracle.graal.nodes.*;
029
030/**
031 * This iterator implements a reverse post order iteration over the fixed nodes in the graph,
032 * starting at the given fixed node.
033 *
034 * No changes to the fixed nodes are expected during the iteration, they cause undefined behavior.
035 */
036public abstract class StatelessPostOrderNodeIterator {
037
038    private final NodeBitMap visitedEnds;
039    private final Deque<AbstractBeginNode> nodeQueue;
040    private final FixedNode start;
041
042    public StatelessPostOrderNodeIterator(FixedNode start) {
043        visitedEnds = start.graph().createNodeBitMap();
044        nodeQueue = new ArrayDeque<>();
045        this.start = start;
046    }
047
048    public void apply() {
049        FixedNode current = start;
050
051        do {
052            if (current instanceof LoopBeginNode) {
053                loopBegin((LoopBeginNode) current);
054                current = ((LoopBeginNode) current).next();
055                assert current != null;
056            } else if (current instanceof LoopEndNode) {
057                loopEnd((LoopEndNode) current);
058                assert !visitedEnds.isMarked(current);
059                visitedEnds.mark(current);
060                current = nodeQueue.pollFirst();
061            } else if (current instanceof AbstractMergeNode) {
062                merge((AbstractMergeNode) current);
063                current = ((AbstractMergeNode) current).next();
064                assert current != null;
065            } else if (current instanceof FixedWithNextNode) {
066                node(current);
067                current = ((FixedWithNextNode) current).next();
068            } else if (current instanceof EndNode) {
069                end((EndNode) current);
070                queueMerge((EndNode) current);
071                current = nodeQueue.pollFirst();
072            } else if (current instanceof ControlSinkNode) {
073                node(current);
074                current = nodeQueue.pollFirst();
075            } else if (current instanceof ControlSplitNode) {
076                controlSplit((ControlSplitNode) current);
077                for (Node node : current.successors()) {
078                    if (node != null) {
079                        nodeQueue.addFirst((AbstractBeginNode) node);
080                    }
081                }
082                current = nodeQueue.pollFirst();
083            } else {
084                assert false : current;
085            }
086        } while (current != null);
087        finished();
088    }
089
090    private void queueMerge(EndNode end) {
091        assert !visitedEnds.isMarked(end);
092        visitedEnds.mark(end);
093        AbstractMergeNode merge = end.merge();
094        boolean endsVisited = true;
095        for (int i = 0; i < merge.forwardEndCount(); i++) {
096            if (!visitedEnds.isMarked(merge.forwardEndAt(i))) {
097                endsVisited = false;
098                break;
099            }
100        }
101        if (endsVisited) {
102            nodeQueue.add(merge);
103        }
104    }
105
106    protected void node(@SuppressWarnings("unused") FixedNode node) {
107        // empty default implementation
108    }
109
110    protected void end(EndNode endNode) {
111        node(endNode);
112    }
113
114    protected void merge(AbstractMergeNode merge) {
115        node(merge);
116    }
117
118    protected void loopBegin(LoopBeginNode loopBegin) {
119        node(loopBegin);
120    }
121
122    protected void loopEnd(LoopEndNode loopEnd) {
123        node(loopEnd);
124    }
125
126    protected void controlSplit(ControlSplitNode controlSplit) {
127        node(controlSplit);
128    }
129
130    protected void finished() {
131        // nothing to do
132    }
133}