001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.controlflow;
014
015 import java.util.Enumeration;
016 import java.util.HashMap;
017
018 import org.jikesrvm.VM;
019 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
020 import org.jikesrvm.compilers.opt.ir.BasicBlock;
021 import org.jikesrvm.compilers.opt.ir.ControlFlowGraph;
022 import org.jikesrvm.compilers.opt.ir.IR;
023 import org.jikesrvm.compilers.opt.util.SpaceEffGraph;
024 import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge;
025 import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
026 import org.jikesrvm.compilers.opt.util.Stack;
027 import org.jikesrvm.util.BitVector;
028
029 /**
030 * Identify natural loops and builds the LST (Loop Structure Tree)
031 * <p>
032 * Note: throws an exception if an irreducible loop is found
033 * (which I believe could only happen in Java from modified bytecode,
034 * because Java source code is structured enough to prevent
035 * irreducible loops.)
036 *
037 * @see DominatorsPhase
038 */
039 public class LSTGraph extends SpaceEffGraph {
040 private static final boolean DEBUG = false;
041
042 protected LSTNode rootNode;
043 /** Map of bb to LSTNode of innermost loop containing bb */
044 private final HashMap<BasicBlock, LSTNode> loopMap;
045
046 /**
047 * The main entry point
048 * @param ir the IR to process
049 */
050 public static void perform(IR ir) {
051 if (DEBUG) System.out.println("LSTGraph:" + ir.method);
052 ir.HIRInfo.loopStructureTree = new LSTGraph(ir);
053 if (DEBUG) {
054 System.out.println(ir.HIRInfo.loopStructureTree.toString());
055 }
056 }
057
058 /**
059 * @param bb the basic block
060 * @return the loop nesting depth or 0, if not in loop
061 */
062 public int getLoopNestDepth(BasicBlock bb) {
063 LSTNode loop = loopMap.get(bb);
064 if (loop == null) return 0;
065 return loop.depth;
066 }
067
068 /**
069 * Is a given basic block in an innermost loop?
070 * @param bb the basic block
071 * @return whether the block is in an innermost loop
072 */
073 public boolean inInnermostLoop(BasicBlock bb) {
074 LSTNode node = loopMap.get(bb);
075 return node != null && node.firstOutEdge() == null && node.loop != null;
076 }
077
078 /**
079 * Is the edge from source to target an exit from the loop containing source?
080 * @param source the basic block that is the source of the edge
081 * @param target the basic block that is the target of the edge
082 */
083 public boolean isLoopExit(BasicBlock source, BasicBlock target) {
084 LSTNode snode = loopMap.get(source);
085 LSTNode tnode = loopMap.get(target);
086
087 if (snode == null || snode == rootNode) return false; // source isn't in a loop
088 if (tnode == null || tnode == rootNode) return true; // source is in a loop and target isn't
089 if (snode == tnode) return false; // in same loop
090
091 for (LSTNode ptr = tnode; ptr != rootNode; ptr = ptr.getParent()) {
092 if (ptr == snode) return false; // tnode is nested inside of snode
093 }
094
095 return true;
096 }
097
098 public LSTNode getLoop(BasicBlock b) {
099 return loopMap.get(b);
100 }
101
102 /**
103 * Return the root node of the tree
104 * @return the root node of the loop structure tree
105 */
106 public LSTNode getRoot() {
107 return rootNode;
108 }
109
110 @Override
111 public String toString() {
112 return "LST:\n" + dumpIt(rootNode);
113 }
114
115 private String dumpIt(LSTNode n) {
116 String ans = n.toString() + "\n";
117 for (Enumeration<LSTNode> e = n.getChildren(); e.hasMoreElements();) {
118 ans += dumpIt(e.nextElement());
119 }
120 return ans;
121 }
122
123 /*
124 * Code to construct the LST for an IR.
125 */
126
127 /**
128 * Copying constructor
129 *
130 * @param graph to copy
131 */
132 protected LSTGraph(LSTGraph graph) {
133 rootNode = graph.rootNode;
134 loopMap = graph.loopMap;
135 }
136
137 /**
138 * Constructor, it creates the LST graph
139 * @param ir the IR
140 */
141 private LSTGraph(IR ir) {
142 loopMap = new HashMap<BasicBlock, LSTNode>();
143
144 ControlFlowGraph cfg = ir.cfg;
145 BasicBlock entry = ir.cfg.entry();
146
147 // do DFN pass
148 cfg.clearDFS();
149 entry.sortDFS();
150 int dfn = 0;
151 for (SpaceEffGraphNode node = entry; node != null; node = node.nextSorted) {
152 node.clearLoopHeader();
153 node.scratch = dfn++;
154 clearBackEdges(node);
155 }
156 cfg.clearDFS();
157 findBackEdges(entry, ir.cfg.numberOfNodes());
158
159 // entry node is considered the LST head
160 LSTNode lstheader = new LSTNode(entry);
161 rootNode = lstheader;
162 addGraphNode(lstheader);
163
164 // compute the natural loops for each back edge.
165 // merge backedges with the same header
166 for (BasicBlock node = (BasicBlock) entry.nextSorted; node != null; node = (BasicBlock) node.nextSorted)
167 {
168 LSTNode header = null;
169 for (SpaceEffGraphEdge edge = node.firstInEdge(); edge != null; edge = edge.getNextIn()) {
170 if (edge.backEdge()) {
171 BitVector loop;
172 if (header == null) {
173 header = new LSTNode(node);
174 addGraphNode(header);
175 loop = new BitVector(cfg.numberOfNodes());
176 loop.set(node.getNumber());
177 header.loop = loop;
178 if (DEBUG) { System.out.println("header" + header); }
179 } else {
180 loop = header.loop;
181 }
182 cfg.clearDFS();
183 node.setDfsVisited();
184 findNaturalLoop(edge, loop);
185 }
186 }
187 }
188 if (DEBUG) {
189 for (SpaceEffGraphNode node = _firstNode; node != null; node = node.getNext()) {
190 System.out.println(node);
191 }
192 }
193
194 // now build the LST
195 lstloop:
196 for (LSTNode node = (LSTNode) _firstNode.getNext(); node != null; node = (LSTNode) node.getNext()) {
197 int number = node.header.getNumber();
198 for (LSTNode prev = (LSTNode) node.getPrev(); prev != _firstNode; prev = (LSTNode) prev.getPrev()) {
199 if (prev.loop.get(number)) { // nested
200 prev.insertOut(node);
201 continue lstloop;
202 }
203 }
204 // else the node is considered to be connected to the LST head
205 _firstNode.insertOut(node);
206 }
207
208 // Set loop nest depth for each node in the LST and initialize LoopMap
209 ir.resetBasicBlockMap();
210 setDepth(ir, rootNode, 0);
211 }
212
213 private void setDepth(IR ir, LSTNode node, int depth) {
214 if (VM.VerifyAssertions) VM._assert(node.depth == 0);
215 node.depth = depth;
216 for (Enumeration<LSTNode> e = node.getChildren(); e.hasMoreElements();) {
217 setDepth(ir, e.nextElement(), depth + 1);
218 }
219 BitVector loop = node.loop;
220 if (loop != null) {
221 for (int i = 0; i < loop.length(); i++) {
222 if (loop.get(i)) {
223 BasicBlock bb = ir.getBasicBlock(i);
224 if (loopMap.get(bb) == null) {
225 loopMap.put(bb, node);
226 }
227 }
228 }
229 }
230 }
231
232 /**
233 * This routine performs a non-recursive depth-first search starting at
234 * the block passed looking for back edges. It uses dominator information
235 * to determine back edges.
236 * @param bb The basic block to process
237 * @param numBlocks The number of basic blocks
238 */
239 private void findBackEdges(BasicBlock bb, int numBlocks) {
240 Stack<BasicBlock> stack = new Stack<BasicBlock>();
241 SpaceEffGraphNode.OutEdgeEnumeration[] BBenum = new SpaceEffGraphNode.OutEdgeEnumeration[numBlocks];
242
243 // push node on to the emulated activation stack
244 stack.push(bb);
245
246 recurse:
247 while (!stack.empty()) {
248 bb = stack.peek();
249
250 // check if we were already processing this node, if so we would have
251 // saved the state of the enumeration in the loop below
252 SpaceEffGraphNode.OutEdgeEnumeration e = BBenum[bb.getNumber()];
253 if (e == null) {
254 if (DEBUG) { System.out.println(" Initial processing of " + bb); }
255 bb.setDfsVisited();
256 e = bb.outEdges();
257 } else {
258 if (DEBUG) { System.out.println(" Resuming processing of " + bb); }
259 }
260
261 while (e.hasMoreElements()) {
262 SpaceEffGraphEdge outEdge = (SpaceEffGraphEdge) e.next();
263
264 BasicBlock outbb = (BasicBlock) outEdge.toNode();
265 if (LTDominatorInfo.isDominatedBy(bb, outbb)) { // backedge
266 outbb.setLoopHeader();
267 outEdge.setBackEdge();
268 if (DEBUG) {
269 System.out.println("backedge from " +
270 bb.scratch +
271 " ( " + bb + " ) " +
272 outbb.scratch +
273 " ( " + outbb + " ) ");
274 }
275 } else if (!outbb.dfsVisited()) {
276 // irreducible loop test
277 if (outbb.scratch < bb.scratch) {
278 throw new OptimizingCompilerException("irreducible loop found!");
279 }
280 // simulate a recursive call
281 // but first save the enumeration state for resumption later
282 BBenum[bb.getNumber()] = e;
283 stack.push(outbb);
284 continue recurse;
285 }
286 } // enum
287 // "Pop" from the emulated activiation stack
288 if (DEBUG) { System.out.println(" Popping"); }
289 stack.pop();
290 } // while !empty
291 }
292
293 /**
294 * Clears the back edges for the basic block passed
295 * @param bb the basic block
296 */
297 private void clearBackEdges(SpaceEffGraphNode bb) {
298 SpaceEffGraphNode.OutEdgeEnumeration f = bb.outEdges();
299 while (f.hasMoreElements()) {
300 SpaceEffGraphEdge outEdge = (SpaceEffGraphEdge) f.next();
301 outEdge.clearBackEdge();
302 }
303 }
304
305 /**
306 * This routine implements part of the algorithm to compute natural loops
307 * as defined in Muchnick p 192. See caller for more details.
308 * @param edge the edge to process
309 * @param loop bit vector to hold the results of the algorithm
310 */
311 private void findNaturalLoop(SpaceEffGraphEdge edge, BitVector loop) {
312
313 /* Algorithm to compute Natural Loops, Muchnick, pp. 192:
314 procedure Nat_Loop(m,n,Pred) return set of Node
315 m, n: in Node
316 Pred: in Node -> set of Node
317 begin
318 Loop: set of Node
319 Stack: sequence of Node
320 p, q: Node
321 Stack := []
322 Loop := {m,n}
323 if m != n then
324 Stack += [m]
325 while Stack != [] do
326 // add predecessors of m that are not predecessors of n
327 // to the set of nodes in the loop; since n dominates m,
328 // this only adds nodes in the loop
329 p := Stack drop -1
330 Stack -= -1
331 for each q in Pred(p) do
332 if q belongs Loop then
333 Loop U= {q}
334 Stack += [q]
335
336 return Loop
337 end
338 */
339
340 SpaceEffGraphNode fromNode = edge.fromNode();
341 if (!fromNode.dfsVisited()) {
342 fromNode.setDfsVisited();
343 loop.set(fromNode.getNumber());
344 for (SpaceEffGraphEdge in = fromNode.firstInEdge(); in != null; in = in.getNextIn()) {
345 findNaturalLoop(in, loop);
346 }
347 }
348 }
349 }