1/*
2 * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23package org.graalvm.compiler.phases.graph;
24
25import java.util.ArrayDeque;
26import java.util.ArrayList;
27import java.util.Deque;
28import java.util.List;
29import java.util.function.Predicate;
30
31import org.graalvm.compiler.core.common.PermanentBailoutException;
32import org.graalvm.compiler.core.common.RetryableBailoutException;
33import org.graalvm.compiler.core.common.cfg.Loop;
34import org.graalvm.compiler.core.common.util.CompilationAlarm;
35import org.graalvm.compiler.nodes.AbstractEndNode;
36import org.graalvm.compiler.nodes.AbstractMergeNode;
37import org.graalvm.compiler.nodes.FixedNode;
38import org.graalvm.compiler.nodes.LoopBeginNode;
39import org.graalvm.compiler.nodes.StructuredGraph;
40import org.graalvm.compiler.nodes.cfg.Block;
41import org.graalvm.util.Equivalence;
42import org.graalvm.util.EconomicMap;
43
44public final class ReentrantBlockIterator {
45
46    public static class LoopInfo<StateT> {
47
48        public final List<StateT> endStates;
49        public final List<StateT> exitStates;
50
51        public LoopInfo(int endCount, int exitCount) {
52            endStates = new ArrayList<>(endCount);
53            exitStates = new ArrayList<>(exitCount);
54        }
55    }
56
57    public abstract static class BlockIteratorClosure<StateT> {
58
59        protected abstract StateT getInitialState();
60
61        protected abstract StateT processBlock(Block block, StateT currentState);
62
63        protected abstract StateT merge(Block merge, List<StateT> states);
64
65        protected abstract StateT cloneState(StateT oldState);
66
67        protected abstract List<StateT> processLoop(Loop<Block> loop, StateT initialState);
68    }
69
70    private ReentrantBlockIterator() {
71        // no instances allowed
72    }
73
74    public static <StateT> LoopInfo<StateT> processLoop(BlockIteratorClosure<StateT> closure, Loop<Block> loop, StateT initialState) {
75        EconomicMap<FixedNode, StateT> blockEndStates = apply(closure, loop.getHeader(), initialState, block -> !(block.getLoop() == loop || block.isLoopHeader()));
76
77        Block[] predecessors = loop.getHeader().getPredecessors();
78        LoopInfo<StateT> info = new LoopInfo<>(predecessors.length - 1, loop.getExits().size());
79        for (int i = 1; i < predecessors.length; i++) {
80            StateT endState = blockEndStates.get(predecessors[i].getEndNode());
81            // make sure all end states are unique objects
82            info.endStates.add(closure.cloneState(endState));
83        }
84        for (Block loopExit : loop.getExits()) {
85            assert loopExit.getPredecessorCount() == 1;
86            assert blockEndStates.containsKey(loopExit.getBeginNode()) : loopExit.getBeginNode() + " " + blockEndStates;
87            StateT exitState = blockEndStates.get(loopExit.getBeginNode());
88            // make sure all exit states are unique objects
89            info.exitStates.add(closure.cloneState(exitState));
90        }
91        return info;
92    }
93
94    public static <StateT> void apply(BlockIteratorClosure<StateT> closure, Block start) {
95        apply(closure, start, closure.getInitialState(), null);
96    }
97
98    public static <StateT> EconomicMap<FixedNode, StateT> apply(BlockIteratorClosure<StateT> closure, Block start, StateT initialState, Predicate<Block> stopAtBlock) {
99        Deque<Block> blockQueue = new ArrayDeque<>();
100        /*
101         * States are stored on EndNodes before merges, and on BeginNodes after ControlSplitNodes.
102         */
103        EconomicMap<FixedNode, StateT> states = EconomicMap.create(Equivalence.IDENTITY);
104
105        StateT state = initialState;
106        Block current = start;
107
108        StructuredGraph graph = start.getBeginNode().graph();
109        CompilationAlarm compilationAlarm = CompilationAlarm.current();
110        while (true) {
111            if (compilationAlarm.hasExpired()) {
112                int period = CompilationAlarm.Options.CompilationExpirationPeriod.getValue(graph.getOptions());
113                if (period > 120) {
114                    throw new PermanentBailoutException("Compilation exceeded %d seconds during CFG traversal", period);
115                } else {
116                    throw new RetryableBailoutException("Compilation exceeded %d seconds during CFG traversal", period);
117                }
118            }
119            Block next = null;
120            if (stopAtBlock != null && stopAtBlock.test(current)) {
121                states.put(current.getBeginNode(), state);
122            } else {
123                state = closure.processBlock(current, state);
124
125                Block[] successors = current.getSuccessors();
126                if (successors.length == 0) {
127                    // nothing to do...
128                } else if (successors.length == 1) {
129                    Block successor = successors[0];
130                    if (successor.isLoopHeader()) {
131                        if (current.isLoopEnd()) {
132                            // nothing to do... loop ends only lead to loop begins we've already
133                            // visited
134                            states.put(current.getEndNode(), state);
135                        } else {
136                            recurseIntoLoop(closure, blockQueue, states, state, successor);
137                        }
138                    } else if (current.getEndNode() instanceof AbstractEndNode) {
139                        AbstractEndNode end = (AbstractEndNode) current.getEndNode();
140
141                        // add the end node and see if the merge is ready for processing
142                        AbstractMergeNode merge = end.merge();
143                        if (allEndsVisited(states, current, merge)) {
144                            ArrayList<StateT> mergedStates = mergeStates(states, state, current, successor, merge);
145                            state = closure.merge(successor, mergedStates);
146                            next = successor;
147                        } else {
148                            assert !states.containsKey(end);
149                            states.put(end, state);
150                        }
151                    } else {
152                        next = successor;
153                    }
154                } else {
155                    next = processMultipleSuccessors(closure, blockQueue, states, state, successors);
156                }
157            }
158
159            // get next queued block
160            if (next != null) {
161                current = next;
162            } else if (blockQueue.isEmpty()) {
163                return states;
164            } else {
165                current = blockQueue.removeFirst();
166                assert current.getPredecessorCount() == 1;
167                assert states.containsKey(current.getBeginNode());
168                state = states.removeKey(current.getBeginNode());
169            }
170        }
171    }
172
173    private static <StateT> boolean allEndsVisited(EconomicMap<FixedNode, StateT> states, Block current, AbstractMergeNode merge) {
174        for (AbstractEndNode forwardEnd : merge.forwardEnds()) {
175            if (forwardEnd != current.getEndNode() && !states.containsKey(forwardEnd)) {
176                return false;
177            }
178        }
179        return true;
180    }
181
182    private static <StateT> Block processMultipleSuccessors(BlockIteratorClosure<StateT> closure, Deque<Block> blockQueue, EconomicMap<FixedNode, StateT> states, StateT state, Block[] successors) {
183        assert successors.length > 1;
184        for (int i = 1; i < successors.length; i++) {
185            Block successor = successors[i];
186            blockQueue.addFirst(successor);
187            states.put(successor.getBeginNode(), closure.cloneState(state));
188        }
189        return successors[0];
190    }
191
192    private static <StateT> ArrayList<StateT> mergeStates(EconomicMap<FixedNode, StateT> states, StateT state, Block current, Block successor, AbstractMergeNode merge) {
193        ArrayList<StateT> mergedStates = new ArrayList<>(merge.forwardEndCount());
194        for (Block predecessor : successor.getPredecessors()) {
195            assert predecessor == current || states.containsKey(predecessor.getEndNode());
196            StateT endState = predecessor == current ? state : states.removeKey(predecessor.getEndNode());
197            mergedStates.add(endState);
198        }
199        return mergedStates;
200    }
201
202    private static <StateT> void recurseIntoLoop(BlockIteratorClosure<StateT> closure, Deque<Block> blockQueue, EconomicMap<FixedNode, StateT> states, StateT state, Block successor) {
203        // recurse into the loop
204        Loop<Block> loop = successor.getLoop();
205        LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
206        assert successor.getBeginNode() == loopBegin;
207
208        List<StateT> exitStates = closure.processLoop(loop, state);
209
210        int i = 0;
211        assert loop.getExits().size() == exitStates.size();
212        for (Block exit : loop.getExits()) {
213            states.put(exit.getBeginNode(), exitStates.get(i++));
214            blockQueue.addFirst(exit);
215        }
216    }
217}
218