001/*
002 * Copyright (c) 2013, 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.graph.iterators.*;
029import com.oracle.graal.nodes.*;
030
031public abstract class ScopedPostOrderNodeIterator {
032
033    private final Deque<FixedNode> nodeQueue;
034    private final NodeBitMap queuedNodes;
035    private final Deque<FixedNode> scopes;
036
037    protected FixedNode currentScopeStart;
038
039    public ScopedPostOrderNodeIterator(StructuredGraph graph) {
040        this.queuedNodes = graph.createNodeBitMap();
041        this.nodeQueue = new ArrayDeque<>();
042        this.scopes = getScopes(graph);
043    }
044
045    public void apply() {
046        while (!scopes.isEmpty()) {
047            queuedNodes.clearAll();
048            this.currentScopeStart = scopes.pop();
049            initializeScope();
050            processScope();
051        }
052    }
053
054    public void processScope() {
055        FixedNode current;
056        queue(currentScopeStart);
057
058        while ((current = nextQueuedNode()) != null) {
059            assert current.isAlive();
060
061            if (current instanceof Invoke) {
062                invoke((Invoke) current);
063                queueSuccessors(current);
064            } else if (current instanceof LoopBeginNode) {
065                queueLoopBeginSuccessors((LoopBeginNode) current);
066            } else if (current instanceof LoopExitNode) {
067                queueLoopExitSuccessors((LoopExitNode) current);
068            } else if (current instanceof LoopEndNode) {
069                // nothing todo
070            } else if (current instanceof AbstractMergeNode) {
071                queueSuccessors(current);
072            } else if (current instanceof FixedWithNextNode) {
073                queueSuccessors(current);
074            } else if (current instanceof EndNode) {
075                queueMerge((EndNode) current);
076            } else if (current instanceof ControlSinkNode) {
077                // nothing todo
078            } else if (current instanceof ControlSplitNode) {
079                queueSuccessors(current);
080            } else {
081                assert false : current;
082            }
083        }
084    }
085
086    protected void queueLoopBeginSuccessors(LoopBeginNode node) {
087        if (currentScopeStart == node) {
088            queue(node.next());
089        } else if (currentScopeStart instanceof LoopBeginNode) {
090            // so we are currently processing loop A and found another loop B
091            // -> queue all loop exits of B except those that also exit loop A
092            for (LoopExitNode loopExit : node.loopExits()) {
093                if (!((LoopBeginNode) currentScopeStart).loopExits().contains(loopExit)) {
094                    queue(loopExit);
095                }
096            }
097        } else {
098            queue(node.loopExits());
099        }
100    }
101
102    protected void queueLoopExitSuccessors(LoopExitNode node) {
103        if (!(currentScopeStart instanceof LoopBeginNode) || !((LoopBeginNode) currentScopeStart).loopExits().contains(node)) {
104            queueSuccessors(node);
105        }
106    }
107
108    protected Deque<FixedNode> getScopes(StructuredGraph graph) {
109        Deque<FixedNode> result = new ArrayDeque<>();
110        result.push(graph.start());
111        for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
112            result.push(loopBegin);
113        }
114        return result;
115    }
116
117    private void queueSuccessors(FixedNode x) {
118        queue(x.successors());
119    }
120
121    private void queue(NodeIterable<? extends Node> iter) {
122        for (Node node : iter) {
123            queue(node);
124        }
125    }
126
127    private void queue(Node node) {
128        if (node != null && !queuedNodes.isMarked(node)) {
129            queuedNodes.mark(node);
130            nodeQueue.addFirst((FixedNode) node);
131        }
132    }
133
134    private FixedNode nextQueuedNode() {
135        if (nodeQueue.isEmpty()) {
136            return null;
137        }
138
139        FixedNode result = nodeQueue.removeFirst();
140        assert queuedNodes.isMarked(result);
141        return result;
142    }
143
144    private void queueMerge(AbstractEndNode end) {
145        AbstractMergeNode merge = end.merge();
146        if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) {
147            queue(merge);
148        }
149    }
150
151    private boolean visitedAllEnds(AbstractMergeNode merge) {
152        for (int i = 0; i < merge.forwardEndCount(); i++) {
153            if (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
154                return false;
155            }
156        }
157        return true;
158    }
159
160    protected abstract void initializeScope();
161
162    protected abstract void invoke(Invoke invoke);
163}