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.*;
026import java.util.function.*;
027
028import com.oracle.graal.compiler.common.cfg.*;
029import com.oracle.graal.graph.*;
030import com.oracle.graal.nodes.*;
031import com.oracle.graal.nodes.cfg.*;
032
033public final class ReentrantBlockIterator {
034
035    public static class LoopInfo<StateT> {
036
037        public final List<StateT> endStates;
038        public final List<StateT> exitStates;
039
040        public LoopInfo(int endCount, int exitCount) {
041            endStates = new ArrayList<>(endCount);
042            exitStates = new ArrayList<>(exitCount);
043        }
044    }
045
046    public abstract static class BlockIteratorClosure<StateT> {
047
048        protected abstract StateT getInitialState();
049
050        protected abstract StateT processBlock(Block block, StateT currentState);
051
052        protected abstract StateT merge(Block merge, List<StateT> states);
053
054        protected abstract StateT cloneState(StateT oldState);
055
056        protected abstract List<StateT> processLoop(Loop<Block> loop, StateT initialState);
057    }
058
059    private ReentrantBlockIterator() {
060        // no instances allowed
061    }
062
063    public static <StateT> LoopInfo<StateT> processLoop(BlockIteratorClosure<StateT> closure, Loop<Block> loop, StateT initialState) {
064        Map<FixedNode, StateT> blockEndStates = apply(closure, loop.getHeader(), initialState, block -> !(block.getLoop() == loop || block.isLoopHeader()));
065
066        List<Block> predecessors = loop.getHeader().getPredecessors();
067        LoopInfo<StateT> info = new LoopInfo<>(predecessors.size() - 1, loop.getExits().size());
068        for (int i = 1; i < predecessors.size(); i++) {
069            StateT endState = blockEndStates.get(predecessors.get(i).getEndNode());
070            // make sure all end states are unique objects
071            info.endStates.add(closure.cloneState(endState));
072        }
073        for (Block loopExit : loop.getExits()) {
074            assert loopExit.getPredecessorCount() == 1;
075            assert blockEndStates.containsKey(loopExit.getBeginNode()) : loopExit.getBeginNode() + " " + blockEndStates;
076            StateT exitState = blockEndStates.get(loopExit.getBeginNode());
077            // make sure all exit states are unique objects
078            info.exitStates.add(closure.cloneState(exitState));
079        }
080        return info;
081    }
082
083    public static <StateT> void apply(BlockIteratorClosure<StateT> closure, Block start) {
084        apply(closure, start, closure.getInitialState(), null);
085    }
086
087    public static <StateT> Map<FixedNode, StateT> apply(BlockIteratorClosure<StateT> closure, Block start, StateT initialState, Predicate<Block> stopAtBlock) {
088        Deque<Block> blockQueue = new ArrayDeque<>();
089        /*
090         * States are stored on EndNodes before merges, and on BeginNodes after ControlSplitNodes.
091         */
092        Map<FixedNode, StateT> states = Node.newIdentityMap();
093
094        StateT state = initialState;
095        Block current = start;
096
097        while (true) {
098            Block next = null;
099            if (stopAtBlock != null && stopAtBlock.test(current)) {
100                states.put(current.getBeginNode(), state);
101            } else {
102                state = closure.processBlock(current, state);
103
104                List<Block> successors = current.getSuccessors();
105                if (successors.isEmpty()) {
106                    // nothing to do...
107                } else if (successors.size() == 1) {
108                    Block successor = successors.get(0);
109                    if (successor.isLoopHeader()) {
110                        if (current.isLoopEnd()) {
111                            // nothing to do... loop ends only lead to loop begins we've already
112                            // visited
113                            states.put(current.getEndNode(), state);
114                        } else {
115                            recurseIntoLoop(closure, blockQueue, states, state, successor);
116                        }
117                    } else if (current.getEndNode() instanceof AbstractEndNode) {
118                        AbstractEndNode end = (AbstractEndNode) current.getEndNode();
119
120                        // add the end node and see if the merge is ready for processing
121                        AbstractMergeNode merge = end.merge();
122                        if (allEndsVisited(states, current, merge)) {
123                            ArrayList<StateT> mergedStates = mergeStates(states, state, current, successor, merge);
124                            state = closure.merge(successor, mergedStates);
125                            next = successor;
126                        } else {
127                            assert !states.containsKey(end);
128                            states.put(end, state);
129                        }
130                    } else {
131                        next = successor;
132                    }
133                } else {
134                    next = processMultipleSuccessors(closure, blockQueue, states, state, successors);
135                }
136            }
137
138            // get next queued block
139            if (next != null) {
140                current = next;
141            } else if (blockQueue.isEmpty()) {
142                return states;
143            } else {
144                current = blockQueue.removeFirst();
145                assert current.getPredecessorCount() == 1;
146                assert states.containsKey(current.getBeginNode());
147                state = states.remove(current.getBeginNode());
148            }
149        }
150    }
151
152    private static <StateT> boolean allEndsVisited(Map<FixedNode, StateT> states, Block current, AbstractMergeNode merge) {
153        for (AbstractEndNode forwardEnd : merge.forwardEnds()) {
154            if (forwardEnd != current.getEndNode() && !states.containsKey(forwardEnd)) {
155                return false;
156            }
157        }
158        return true;
159    }
160
161    private static <StateT> Block processMultipleSuccessors(BlockIteratorClosure<StateT> closure, Deque<Block> blockQueue, Map<FixedNode, StateT> states, StateT state, List<Block> successors) {
162        assert successors.size() > 1;
163        for (int i = 1; i < successors.size(); i++) {
164            Block successor = successors.get(i);
165            blockQueue.addFirst(successor);
166            states.put(successor.getBeginNode(), closure.cloneState(state));
167        }
168        return successors.get(0);
169    }
170
171    private static <StateT> ArrayList<StateT> mergeStates(Map<FixedNode, StateT> states, StateT state, Block current, Block successor, AbstractMergeNode merge) {
172        ArrayList<StateT> mergedStates = new ArrayList<>(merge.forwardEndCount());
173        for (Block predecessor : successor.getPredecessors()) {
174            assert predecessor == current || states.containsKey(predecessor.getEndNode());
175            StateT endState = predecessor == current ? state : states.remove(predecessor.getEndNode());
176            mergedStates.add(endState);
177        }
178        return mergedStates;
179    }
180
181    private static <StateT> void recurseIntoLoop(BlockIteratorClosure<StateT> closure, Deque<Block> blockQueue, Map<FixedNode, StateT> states, StateT state, Block successor) {
182        // recurse into the loop
183        Loop<Block> loop = successor.getLoop();
184        LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
185        assert successor.getBeginNode() == loopBegin;
186
187        List<StateT> exitStates = closure.processLoop(loop, state);
188
189        int i = 0;
190        assert loop.getExits().size() == exitStates.size();
191        for (Block exit : loop.getExits()) {
192            states.put(exit.getBeginNode(), exitStates.get(i++));
193            blockQueue.addFirst(exit);
194        }
195    }
196}