1 // LoopFinder.java, created Tue Jun 15 23:15:07 1999 by bdemsky
2 // Licensed under the terms of the GNU GPL; see COPYING for details.
3 // Copyright 1999 by Brian Demsky
5 package Analysis.Loops;
7 import IR.Flat.FlatMethod;
8 import IR.Flat.FlatNode;
9 import java.util.HashSet;
11 import java.util.Stack;
12 import java.util.Hashtable;
13 import java.util.Iterator;
15 * <code>LoopFinder</code> implements Dominator Tree Loop detection.
17 * @author Brian Demsky <bdemsky@mit.edu>
18 * @version $Id: LoopFinder.java,v 1.1 2009/03/27 00:59:36 bdemsky Exp $
21 public class LoopFinder implements Loops {
29 /** Creates a new LoopFinder object.
30 * This call takes an HCode and a CFGrapher
31 * and returns a LoopFinder object
35 public LoopFinder(FlatMethod hc) {
37 this.dominator=new DomTree(hc);
42 /**This method is for internal use only.
43 *It returns a Loopfinder object at any level,
44 *but it doesn't regenerate the internal tree
45 *so any external calls would result in garbage.*/
47 private LoopFinder(FlatMethod hc, DomTree dt, Loop root, Loop ptr) {
55 /*-----------------------------*/
57 /** This method returns the Root level loop for a given <code>HCode</code>.
58 * Does the same thing as the constructor call, but for an existing
59 * LoopFinder object.*/
61 public Loops getRootloop(FlatMethod hc) {
64 return new LoopFinder(hc,dominator,root,root);
67 /** This method returns the entry point of the loop.
68 * For the natural loops we consider, that is simply the header.
69 * It returns a <code>Set</code> of <code>HCodeElement</code>s.*/
71 public Set loopEntrances() {
72 HashSet entries=new HashSet();
74 entries.push(ptr.header);
79 /**Returns a <code>Set</code> with all of the <code>HCodeElement</code>s of the loop and
80 *loops included entirely within this loop. */
82 public Set loopIncElements() {
84 HashSet A=new HashSet(ptr.entries);
88 /** Returns all of the <code>HCodeElement</code>s of this loop that aren't in a nested
89 * loop. This returns a <code>Set</code> of <code>HCodeElement</code>s.*/
91 public Set loopExcElements() {
93 HashSet A=new HashSet(ptr.entries);
94 HashSet todo=new WorkSet();
96 todo.addAll(ptr.children);
99 while(!todo.isEmpty()) {
100 Loop currptr=(Loop)todo.pop();
101 todo.addAll(currptr.children);
102 A.removeAll(currptr.entries);
107 /** Returns a <code>Set</code> of loops that are nested inside of this loop.*/
109 public Set nestedLoops() {
111 HashSet L=new HashSet();
112 Iterator iterate=ptr.children.iterator();
113 while (iterate.hasNext())
114 L.add(new LoopFinder(hc,grapher,dominator,root,(Loop) iterate.next()));
118 /** Returns the <code>Loops</code> that contains this loop.
119 * If this is the top level loop, this call returns a null pointer.*/
121 public Loops parentLoop() {
123 if (ptr.parent!=null)
124 return new LoopFinder(hc,grapher,dominator,root,ptr.parent);
128 /*---------------------------*/
129 // public information accessor methods.
131 /*---------------------------*/
135 /** Main analysis method. */
138 //Have we analyzed this set before?
139 //If so, don't do it again!!!
142 //Did the caller hand us a bogus object?
143 //If so, throw it something
147 //Set up the top level loop, so we can fill it with HCodeElements
152 //Set up a WorkSet for storing loops before we build the
154 setofloops=new HashSet();
159 //Build the nested loop tree
166 //go through set of generated loops
167 while(!setofloops.isEmpty()) {
169 Loop A=(Loop) setofloops.iterator().next();
170 setofloops.remove(A);
172 //Add it to the tree, complain if oddness
173 if (addnode(A, root)!=1)
174 System.out.println("Evil Error in LoopFinder while building tree.");
178 //Adds a node to the tree...Its recursive
180 int addnode(Loop A, Loop treenode) {
181 //Only need to go deeper if the header is contained in this loop
182 if (treenode.entries.contains(A.header))
184 //Do we share headers?
185 if (treenode.header!=A.header) {
187 //No... Loop through our children to see if they want this
190 //Use integers for tri-state:
191 //0=not stored here, 1=stored and everything is good
192 //2=combined 2 natural loops with same header...need cleanup
195 Iterator iterate=treenode.children.iterator();
196 Loop temp=new Loop();
197 while (iterate.hasNext()) {
198 temp=(Loop) iterate.next();
199 stored=addnode(A,temp);
200 if (stored!=0) break;
203 //See what our children did for us
206 //We get a new child...
207 treenode.children.push(A);
211 //Need to do cleanup for case 0 or 2
212 //temp points to the new child
216 //Have to make sure that none of the nodes under this one
217 //are children of the new node
219 Iterator iterate2=treenode.children.iterator();
220 temp.parent=treenode;
222 //Loop through the children
223 while (iterate2.hasNext()) {
224 Loop temp2=(Loop)iterate2.next();
226 //Don't look at the new node...otherwise we will create
227 //a unreachable subtree
230 //If the new node has a childs header
231 //give the child up to it...
233 if (temp.entries.contains(temp2.header)) {
234 temp.children.push(temp2);
240 //We fixed everything...let our parents know
243 //need to combine loops
244 while (!A.entries.isEmpty()) {
245 treenode.entries.push(A.entries.removeLast());
247 //let the previous caller know that they have stuff todo
250 //We aren't adopting the new node
254 void findloopheaders(FlatNode current_nodeOrig) {
255 Stack stk = new Stack();
256 stk.push( current_nodeOrig );
257 while( ! stk.isEmpty() ){
258 FlatNode current_node = (FlatNode) stk.pop();
259 //look at the current node
262 //add it to the all inclusive root loop
263 root.entries.push(current_node);
265 //See if those we dominate are backedges
266 stk.addAll(dominator.children(current_node));
270 void visit(FlatNode q) {
272 HashSet B=new HashSet();
274 //Loop through all of our outgoing edges
275 for (int i=0;i<q.numNext();i++) {
277 FlatNode temp_to=q.next(i);
279 //Go up the dominator tree until
280 //we hit the root element or we
281 //find the node we jump back too
284 temp=dominator.idom(temp);
287 //If we found the node we jumped back to
293 A.entries.push(temp); //Push the header
295 B.push(q); //Put the backedge in the todo list
297 //Starting with the backedge, work on the incoming edges
298 //until we get back to the loop header...
299 //Then we have the entire natural loop
301 while(!B.isEmpty()) {
302 FlatNode newnode=(FlatNode)B.removeLast();
304 //Add all of the new incoming edges that we haven't already
306 for (int j=0;j<newnode.numPrev;j++) {
307 FlatNode from=newnode.prev(j);
308 if (!A.entries.contains(from))
312 //push the new node on our list of nodes in the loop
313 A.entries.push(newnode);
322 //Structure for building internal trees...
325 public HashSet entries=new HashSet();
326 public FlatNode header;
327 //Elements of the WorkSet of children are
329 public HashSet children=new HashSet();