001/*
002 * Copyright (c) 2011, 2012, 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
030public final class ReentrantNodeIterator {
031
032    public static class LoopInfo<StateT> {
033
034        public final Map<LoopEndNode, StateT> endStates;
035        public final Map<LoopExitNode, StateT> exitStates;
036
037        public LoopInfo(int endCount, int exitCount) {
038            endStates = Node.newIdentityMap(endCount);
039            exitStates = Node.newIdentityMap(exitCount);
040        }
041    }
042
043    public abstract static class NodeIteratorClosure<StateT> {
044
045        protected abstract StateT processNode(FixedNode node, StateT currentState);
046
047        protected abstract StateT merge(AbstractMergeNode merge, List<StateT> states);
048
049        protected abstract StateT afterSplit(AbstractBeginNode node, StateT oldState);
050
051        protected abstract Map<LoopExitNode, StateT> processLoop(LoopBeginNode loop, StateT initialState);
052
053        /**
054         * Determine whether iteration should continue in the current state.
055         *
056         * @param currentState
057         */
058        protected boolean continueIteration(StateT currentState) {
059            return true;
060        }
061    }
062
063    private ReentrantNodeIterator() {
064        // no instances allowed
065    }
066
067    public static <StateT> LoopInfo<StateT> processLoop(NodeIteratorClosure<StateT> closure, LoopBeginNode loop, StateT initialState) {
068        Map<FixedNode, StateT> blockEndStates = apply(closure, loop, initialState, loop);
069
070        LoopInfo<StateT> info = new LoopInfo<>(loop.loopEnds().count(), loop.loopExits().count());
071        for (LoopEndNode end : loop.loopEnds()) {
072            if (blockEndStates.containsKey(end)) {
073                info.endStates.put(end, blockEndStates.get(end));
074            }
075        }
076        for (LoopExitNode exit : loop.loopExits()) {
077            if (blockEndStates.containsKey(exit)) {
078                info.exitStates.put(exit, blockEndStates.get(exit));
079            }
080        }
081        return info;
082    }
083
084    public static <StateT> void apply(NodeIteratorClosure<StateT> closure, FixedNode start, StateT initialState) {
085        apply(closure, start, initialState, null);
086    }
087
088    private static <StateT> Map<FixedNode, StateT> apply(NodeIteratorClosure<StateT> closure, FixedNode start, StateT initialState, LoopBeginNode boundary) {
089        assert start != null;
090        Deque<AbstractBeginNode> nodeQueue = new ArrayDeque<>();
091        Map<FixedNode, StateT> blockEndStates = Node.newIdentityMap();
092
093        StateT state = initialState;
094        FixedNode current = start;
095        do {
096            while (current instanceof FixedWithNextNode) {
097                if (boundary != null && current instanceof LoopExitNode && ((LoopExitNode) current).loopBegin() == boundary) {
098                    blockEndStates.put(current, state);
099                    current = null;
100                } else {
101                    FixedNode next = ((FixedWithNextNode) current).next();
102                    state = closure.processNode(current, state);
103                    current = closure.continueIteration(state) ? next : null;
104                }
105            }
106
107            if (current != null) {
108                state = closure.processNode(current, state);
109
110                if (closure.continueIteration(state)) {
111                    NodePosIterator successors = current.successors().iterator();
112                    if (!successors.hasNext()) {
113                        if (current instanceof LoopEndNode) {
114                            blockEndStates.put(current, state);
115                        } else if (current instanceof EndNode) {
116                            // add the end node and see if the merge is ready for processing
117                            AbstractMergeNode merge = ((EndNode) current).merge();
118                            if (merge instanceof LoopBeginNode) {
119                                Map<LoopExitNode, StateT> loopExitState = closure.processLoop((LoopBeginNode) merge, state);
120                                for (Map.Entry<LoopExitNode, StateT> entry : loopExitState.entrySet()) {
121                                    blockEndStates.put(entry.getKey(), entry.getValue());
122                                    nodeQueue.add(entry.getKey());
123                                }
124                            } else {
125                                boolean endsVisited = true;
126                                for (AbstractEndNode forwardEnd : merge.forwardEnds()) {
127                                    if (forwardEnd != current && !blockEndStates.containsKey(forwardEnd)) {
128                                        endsVisited = false;
129                                        break;
130                                    }
131                                }
132                                if (endsVisited) {
133                                    ArrayList<StateT> states = new ArrayList<>(merge.forwardEndCount());
134                                    for (int i = 0; i < merge.forwardEndCount(); i++) {
135                                        AbstractEndNode forwardEnd = merge.forwardEndAt(i);
136                                        assert forwardEnd == current || blockEndStates.containsKey(forwardEnd);
137                                        StateT other = forwardEnd == current ? state : blockEndStates.remove(forwardEnd);
138                                        states.add(other);
139                                    }
140                                    state = closure.merge(merge, states);
141                                    current = closure.continueIteration(state) ? merge : null;
142                                    continue;
143                                } else {
144                                    assert !blockEndStates.containsKey(current);
145                                    blockEndStates.put(current, state);
146                                }
147                            }
148                        }
149                    } else {
150                        FixedNode firstSuccessor = (FixedNode) successors.next();
151                        if (!successors.hasNext()) {
152                            current = firstSuccessor;
153                            continue;
154                        } else {
155                            do {
156                                AbstractBeginNode successor = (AbstractBeginNode) successors.next();
157                                StateT successorState = closure.afterSplit(successor, state);
158                                if (closure.continueIteration(successorState)) {
159                                    blockEndStates.put(successor, successorState);
160                                    nodeQueue.add(successor);
161                                }
162                            } while (successors.hasNext());
163
164                            state = closure.afterSplit((AbstractBeginNode) firstSuccessor, state);
165                            current = closure.continueIteration(state) ? firstSuccessor : null;
166                            continue;
167                        }
168                    }
169                }
170            }
171
172            // get next queued block
173            if (nodeQueue.isEmpty()) {
174                return blockEndStates;
175            } else {
176                current = nodeQueue.removeFirst();
177                assert blockEndStates.containsKey(current);
178                state = blockEndStates.remove(current);
179                assert !(current instanceof AbstractMergeNode) && current instanceof AbstractBeginNode;
180            }
181        } while (true);
182    }
183}