1 /* 2 * Copyright (c) 2011, 2018, 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 */ 23 24 25 package org.graalvm.compiler.phases.graph; 26 27 import java.util.ArrayDeque; 28 import java.util.ArrayList; 29 import java.util.Deque; 30 import java.util.List; 31 import java.util.function.Predicate; 32 33 import jdk.internal.vm.compiler.collections.EconomicMap; 34 import jdk.internal.vm.compiler.collections.Equivalence; 35 import org.graalvm.compiler.core.common.PermanentBailoutException; 36 import org.graalvm.compiler.core.common.RetryableBailoutException; 37 import org.graalvm.compiler.core.common.cfg.Loop; 38 import org.graalvm.compiler.core.common.util.CompilationAlarm; 39 import org.graalvm.compiler.nodes.AbstractEndNode; 40 import org.graalvm.compiler.nodes.AbstractMergeNode; 41 import org.graalvm.compiler.nodes.FixedNode; 42 import org.graalvm.compiler.nodes.LoopBeginNode; 43 import org.graalvm.compiler.nodes.StructuredGraph; 44 import org.graalvm.compiler.nodes.cfg.Block; 45 46 public final class ReentrantBlockIterator { 47 48 public static class LoopInfo<StateT> { 49 50 public final List<StateT> endStates; 51 public final List<StateT> exitStates; 52 53 public LoopInfo(int endCount, int exitCount) { 54 endStates = new ArrayList<>(endCount); 55 exitStates = new ArrayList<>(exitCount); 56 } 57 } 58 59 public abstract static class BlockIteratorClosure<StateT> { 60 61 protected abstract StateT getInitialState(); 62 63 protected abstract StateT processBlock(Block block, StateT currentState); 64 65 protected abstract StateT merge(Block merge, List<StateT> states); 66 67 protected abstract StateT cloneState(StateT oldState); 68 69 protected abstract List<StateT> processLoop(Loop<Block> loop, StateT initialState); 70 } 71 72 private ReentrantBlockIterator() { 73 // no instances allowed 74 } 75 76 public static <StateT> LoopInfo<StateT> processLoop(BlockIteratorClosure<StateT> closure, Loop<Block> loop, StateT initialState) { 77 EconomicMap<FixedNode, StateT> blockEndStates = apply(closure, loop.getHeader(), initialState, block -> !(block.getLoop() == loop || block.isLoopHeader())); 78 79 Block[] predecessors = loop.getHeader().getPredecessors(); 80 LoopInfo<StateT> info = new LoopInfo<>(predecessors.length - 1, loop.getLoopExits().size()); 81 for (int i = 1; i < predecessors.length; i++) { 82 StateT endState = blockEndStates.get(predecessors[i].getEndNode()); 83 // make sure all end states are unique objects 84 info.endStates.add(closure.cloneState(endState)); 85 } 86 for (Block loopExit : loop.getLoopExits()) { 87 assert loopExit.getPredecessorCount() == 1; 88 assert blockEndStates.containsKey(loopExit.getBeginNode()) : loopExit.getBeginNode() + " " + blockEndStates; 89 StateT exitState = blockEndStates.get(loopExit.getBeginNode()); 90 // make sure all exit states are unique objects 91 info.exitStates.add(closure.cloneState(exitState)); 92 } 93 return info; 94 } 95 96 public static <StateT> void apply(BlockIteratorClosure<StateT> closure, Block start) { 97 apply(closure, start, closure.getInitialState(), null); 98 } 99 100 public static <StateT> EconomicMap<FixedNode, StateT> apply(BlockIteratorClosure<StateT> closure, Block start, StateT initialState, Predicate<Block> stopAtBlock) { 101 Deque<Block> blockQueue = new ArrayDeque<>(); 102 /* 103 * States are stored on EndNodes before merges, and on BeginNodes after ControlSplitNodes. 104 */ 105 EconomicMap<FixedNode, StateT> states = EconomicMap.create(Equivalence.IDENTITY); 106 107 StateT state = initialState; 108 Block current = start; 109 110 StructuredGraph graph = start.getBeginNode().graph(); 111 CompilationAlarm compilationAlarm = CompilationAlarm.current(); 112 while (true) { 113 if (compilationAlarm.hasExpired()) { 114 int period = CompilationAlarm.Options.CompilationExpirationPeriod.getValue(graph.getOptions()); 115 if (period > 120) { 116 throw new PermanentBailoutException("Compilation exceeded %d seconds during CFG traversal", period); 117 } else { 118 throw new RetryableBailoutException("Compilation exceeded %d seconds during CFG traversal", period); 119 } 120 } 121 Block next = null; 122 if (stopAtBlock != null && stopAtBlock.test(current)) { 123 states.put(current.getBeginNode(), state); 124 } else { 125 state = closure.processBlock(current, state); 126 127 Block[] successors = current.getSuccessors(); 128 if (successors.length == 0) { 129 // nothing to do... 130 } else if (successors.length == 1) { 131 Block successor = successors[0]; 132 if (successor.isLoopHeader()) { 133 if (current.isLoopEnd()) { 134 // nothing to do... loop ends only lead to loop begins we've already 135 // visited 136 states.put(current.getEndNode(), state); 137 } else { 138 recurseIntoLoop(closure, blockQueue, states, state, successor); 139 } 140 } else if (current.getEndNode() instanceof AbstractEndNode) { 141 AbstractEndNode end = (AbstractEndNode) current.getEndNode(); 142 143 // add the end node and see if the merge is ready for processing 144 AbstractMergeNode merge = end.merge(); 145 if (allEndsVisited(states, current, merge)) { 146 ArrayList<StateT> mergedStates = mergeStates(states, state, current, successor, merge); 147 state = closure.merge(successor, mergedStates); 148 next = successor; 149 } else { 150 assert !states.containsKey(end); 151 states.put(end, state); 152 } 153 } else { 154 next = successor; 155 } 156 } else { 157 next = processMultipleSuccessors(closure, blockQueue, states, state, successors); 158 } 159 } 160 161 // get next queued block 162 if (next != null) { 163 current = next; 164 } else if (blockQueue.isEmpty()) { 165 return states; 166 } else { 167 current = blockQueue.removeFirst(); 168 assert current.getPredecessorCount() == 1; 169 assert states.containsKey(current.getBeginNode()); 170 state = states.removeKey(current.getBeginNode()); 171 } 172 } 173 } 174 175 private static <StateT> boolean allEndsVisited(EconomicMap<FixedNode, StateT> states, Block current, AbstractMergeNode merge) { 176 for (AbstractEndNode forwardEnd : merge.forwardEnds()) { 177 if (forwardEnd != current.getEndNode() && !states.containsKey(forwardEnd)) { 178 return false; 179 } 180 } 181 return true; 182 } 183 184 private static <StateT> Block processMultipleSuccessors(BlockIteratorClosure<StateT> closure, Deque<Block> blockQueue, EconomicMap<FixedNode, StateT> states, StateT state, Block[] successors) { 185 assert successors.length > 1; 186 for (int i = 1; i < successors.length; i++) { 187 Block successor = successors[i]; 188 blockQueue.addFirst(successor); 189 states.put(successor.getBeginNode(), closure.cloneState(state)); 190 } 191 return successors[0]; 192 } 193 194 private static <StateT> ArrayList<StateT> mergeStates(EconomicMap<FixedNode, StateT> states, StateT state, Block current, Block successor, AbstractMergeNode merge) { 195 ArrayList<StateT> mergedStates = new ArrayList<>(merge.forwardEndCount()); 196 for (Block predecessor : successor.getPredecessors()) { 197 assert predecessor == current || states.containsKey(predecessor.getEndNode()); 198 StateT endState = predecessor == current ? state : states.removeKey(predecessor.getEndNode()); 199 mergedStates.add(endState); 200 } 201 return mergedStates; 202 } 203 204 private static <StateT> void recurseIntoLoop(BlockIteratorClosure<StateT> closure, Deque<Block> blockQueue, EconomicMap<FixedNode, StateT> states, StateT state, Block successor) { 205 // recurse into the loop 206 Loop<Block> loop = successor.getLoop(); 207 LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode(); 208 assert successor.getBeginNode() == loopBegin; 209 210 List<StateT> exitStates = closure.processLoop(loop, state); 211 212 int i = 0; 213 assert loop.getLoopExits().size() == exitStates.size(); 214 for (Block exit : loop.getLoopExits()) { 215 states.put(exit.getBeginNode(), exitStates.get(i++)); 216 blockQueue.addFirst(exit); 217 } 218 } 219 }