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 *
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 public String toString() {
111 return "LST:\n" + dumpIt(rootNode);
112 }
113
114 private String dumpIt(LSTNode n) {
115 String ans = n.toString() + "\n";
116 for (Enumeration<LSTNode> e = n.getChildren(); e.hasMoreElements();) {
117 ans += dumpIt(e.nextElement());
118 }
119 return ans;
120 }
121
122 /*
123 * Code to construct the LST for an IR.
124 */
125
126 /**
127 * Copying constructor
128 *
129 * @param graph to copy
130 */
131 protected LSTGraph(LSTGraph graph) {
132 rootNode = graph.rootNode;
133 loopMap = graph.loopMap;
134 }
135
136 /**
137 * Constructor, it creates the LST graph
138 * @param ir the IR
139 */
140 private LSTGraph(IR ir) {
141 loopMap = new HashMap<BasicBlock, LSTNode>();
142
143 ControlFlowGraph cfg = ir.cfg;
144 BasicBlock entry = ir.cfg.entry();
145
146 // do DFN pass
147 cfg.clearDFS();
148 entry.sortDFS();
149 int dfn = 0;
150 for (SpaceEffGraphNode node = entry; node != null; node = node.nextSorted) {
151 node.clearLoopHeader();
152 node.scratch = dfn++;
153 clearBackEdges(node);
154 }
155 cfg.clearDFS();
156 findBackEdges(entry, ir.cfg.numberOfNodes());
157
158 // entry node is considered the LST head
159 LSTNode lstheader = new LSTNode(entry);
160 rootNode = lstheader;
161 addGraphNode(lstheader);
162
163 // compute the natural loops for each back edge.
164 // merge backedges with the same header
165 for (BasicBlock node = (BasicBlock) entry.nextSorted; node != null; node = (BasicBlock) node.nextSorted)
166 {
167 LSTNode header = null;
168 for (SpaceEffGraphEdge edge = node.firstInEdge(); edge != null; edge = edge.getNextIn()) {
169 if (edge.backEdge()) {
170 BitVector loop;
171 if (header == null) {
172 header = new LSTNode(node);
173 addGraphNode(header);
174 loop = new BitVector(cfg.numberOfNodes());
175 loop.set(node.getNumber());
176 header.loop = loop;
177 if (DEBUG) { System.out.println("header" + header); }
178 } else {
179 loop = header.loop;
180 }
181 cfg.clearDFS();
182 node.setDfsVisited();
183 findNaturalLoop(edge, loop);
184 }
185 }
186 }
187 if (DEBUG) {
188 for (SpaceEffGraphNode node = _firstNode; node != null; node = node.getNext()) {
189 System.out.println(node);
190 }
191 }
192
193 // now build the LST
194 lstloop:
195 for (LSTNode node = (LSTNode) _firstNode.getNext(); node != null; node = (LSTNode) node.getNext()) {
196 int number = node.header.getNumber();
197 for (LSTNode prev = (LSTNode) node.getPrev(); prev != _firstNode; prev = (LSTNode) prev.getPrev()) {
198 if (prev.loop.get(number)) { // nested
199 prev.insertOut(node);
200 continue lstloop;
201 }
202 }
203 // else the node is considered to be connected to the LST head
204 _firstNode.insertOut(node);
205 }
206
207 // Set loop nest depth for each node in the LST and initialize LoopMap
208 ir.resetBasicBlockMap();
209 setDepth(ir, rootNode, 0);
210 }
211
212 private void setDepth(IR ir, LSTNode node, int depth) {
213 if (VM.VerifyAssertions) VM._assert(node.depth == 0);
214 node.depth = depth;
215 for (Enumeration<LSTNode> e = node.getChildren(); e.hasMoreElements();) {
216 setDepth(ir, e.nextElement(), depth + 1);
217 }
218 BitVector loop = node.loop;
219 if (loop != null) {
220 for (int i = 0; i < loop.length(); i++) {
221 if (loop.get(i)) {
222 BasicBlock bb = ir.getBasicBlock(i);
223 if (loopMap.get(bb) == null) {
224 loopMap.put(bb, node);
225 }
226 }
227 }
228 }
229 }
230
231 /**
232 * This routine performs a non-recursive depth-first search starting at
233 * the block passed looking for back edges. It uses dominator information
234 * to determine back edges.
235 * @param bb The basic block to process
236 * @param numBlocks The number of basic blocks
237 */
238 private void findBackEdges(BasicBlock bb, int numBlocks) {
239 Stack<BasicBlock> stack = new Stack<BasicBlock>();
240 SpaceEffGraphNode.OutEdgeEnumeration[] BBenum = new SpaceEffGraphNode.OutEdgeEnumeration[numBlocks];
241
242 // push node on to the emulated activation stack
243 stack.push(bb);
244
245 recurse:
246 while (!stack.empty()) {
247 bb = stack.peek();
248
249 // check if we were already processing this node, if so we would have
250 // saved the state of the enumeration in the loop below
251 SpaceEffGraphNode.OutEdgeEnumeration e = BBenum[bb.getNumber()];
252 if (e == null) {
253 if (DEBUG) { System.out.println(" Initial processing of " + bb); }
254 bb.setDfsVisited();
255 e = bb.outEdges();
256 } else {
257 if (DEBUG) { System.out.println(" Resuming processing of " + bb); }
258 }
259
260 while (e.hasMoreElements()) {
261 SpaceEffGraphEdge outEdge = (SpaceEffGraphEdge) e.next();
262
263 BasicBlock outbb = (BasicBlock) outEdge.toNode();
264 if (LTDominatorInfo.isDominatedBy(bb, outbb)) { // backedge
265 outbb.setLoopHeader();
266 outEdge.setBackEdge();
267 if (DEBUG) {
268 System.out.println("backedge from " +
269 bb.scratch +
270 " ( " + bb + " ) " +
271 outbb.scratch +
272 " ( " + outbb + " ) ");
273 }
274 } else if (!outbb.dfsVisited()) {
275 // irreducible loop test
276 if (outbb.scratch < bb.scratch) {
277 throw new OptimizingCompilerException("irreducible loop found!");
278 }
279 // simulate a recursive call
280 // but first save the enumeration state for resumption later
281 BBenum[bb.getNumber()] = e;
282 stack.push(outbb);
283 continue recurse;
284 }
285 } // enum
286 // "Pop" from the emulated activiation stack
287 if (DEBUG) { System.out.println(" Popping"); }
288 stack.pop();
289 } // while !empty
290 }
291
292 /**
293 * Clears the back edges for the basic block passed
294 * @param bb the basic block
295 */
296 private void clearBackEdges(SpaceEffGraphNode bb) {
297 SpaceEffGraphNode.OutEdgeEnumeration f = bb.outEdges();
298 while (f.hasMoreElements()) {
299 SpaceEffGraphEdge outEdge = (SpaceEffGraphEdge) f.next();
300 outEdge.clearBackEdge();
301 }
302 }
303
304 /**
305 * This routine implements part of the algorithm to compute natural loops
306 * as defined in Muchnick p 192. See caller for more details.
307 * @param edge the edge to process
308 * @param loop bit vector to hold the results of the algorithm
309 */
310 private void findNaturalLoop(SpaceEffGraphEdge edge, BitVector loop) {
311
312 /* Algorithm to compute Natural Loops, Muchnick, pp. 192:
313 procedure Nat_Loop(m,n,Pred) return set of Node
314 m, n: in Node
315 Pred: in Node -> set of Node
316 begin
317 Loop: set of Node
318 Stack: sequence of Node
319 p, q: Node
320 Stack := []
321 Loop := {m,n}
322 if m != n then
323 Stack += [m]
324 while Stack != [] do
325 // add predecessors of m that are not predecessors of n
326 // to the set of nodes in the loop; since n dominates m,
327 // this only adds nodes in the loop
328 p := Stack drop -1
329 Stack -= -1
330 for each q in Pred(p) do
331 if q belongs Loop then
332 Loop U= {q}
333 Stack += [q]
334
335 return Loop
336 end
337 */
338
339 SpaceEffGraphNode fromNode = edge.fromNode();
340 if (!fromNode.dfsVisited()) {
341 fromNode.setDfsVisited();
342 loop.set(fromNode.getNumber());
343 for (SpaceEffGraphEdge in = fromNode.firstInEdge(); in != null; in = in.getNextIn()) {
344 findNaturalLoop(in, loop);
345 }
346 }
347 }
348 }