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.5 2011/04/27 20:51: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,false);
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.add(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 HashSet();
96 todo.addAll(ptr.children);
99 while(!todo.isEmpty()) {
100 Loop currptr=(Loop)todo.iterator().next();
101 todo.remove(currptr);
102 todo.addAll(currptr.children);
103 A.removeAll(currptr.entries);
108 /** Returns a <code>Set</code> of loops that are nested inside of this loop.*/
110 public Set nestedLoops() {
112 HashSet L=new HashSet();
113 Iterator iterate=ptr.children.iterator();
114 while (iterate.hasNext())
115 L.add(new LoopFinder(hc,dominator,root,(Loop) iterate.next()));
119 /** Returns the <code>Loops</code> that contains this loop.
120 * If this is the top level loop, this call returns a null pointer.*/
122 public Loops parentLoop() {
124 if (ptr.parent!=null)
125 return new LoopFinder(hc,dominator,root,ptr.parent);
129 /*---------------------------*/
130 // public information accessor methods.
132 /*---------------------------*/
136 /** Main analysis method. */
139 //Have we analyzed this set before?
140 //If so, don't do it again!!!
143 //Did the caller hand us a bogus object?
144 //If so, throw it something
148 //Set up the top level loop, so we can fill it with HCodeElements
153 //Set up a WorkSet for storing loops before we build the
155 setofloops=new HashSet();
161 //Build the nested loop tree
168 //go through set of generated loops
169 while(!setofloops.isEmpty()) {
171 Loop A=(Loop) setofloops.iterator().next();
172 setofloops.remove(A);
174 //Add it to the tree, complain if oddness
175 if (addnode(A, root)!=1)
176 System.out.println("Evil Error in LoopFinder while building tree.");
180 //Adds a node to the tree...Its recursive
182 int addnode(Loop A, Loop treenode) {
183 //Only need to go deeper if the header is contained in this loop
184 if (treenode.entries.contains(A.header))
186 //Do we share headers?
187 if (treenode.header!=A.header) {
189 //No... Loop through our children to see if they want this
192 //Use integers for tri-state:
193 //0=not stored here, 1=stored and everything is good
194 //2=combined 2 natural loops with same header...need cleanup
197 Iterator iterate=treenode.children.iterator();
198 Loop temp=new Loop();
199 while (iterate.hasNext()) {
200 temp=(Loop) iterate.next();
201 stored=addnode(A,temp);
202 if (stored!=0) break;
205 //See what our children did for us
208 //We get a new child...
209 treenode.children.add(A);
213 //Need to do cleanup for case 0 or 2
214 //temp points to the new child
218 //Have to make sure that none of the nodes under this one
219 //are children of the new node
221 Iterator iterate2=treenode.children.iterator();
222 temp.parent=treenode;
224 //Loop through the children
225 while (iterate2.hasNext()) {
226 Loop temp2=(Loop)iterate2.next();
228 //Don't look at the new node...otherwise we will create
229 //a unreachable subtree
232 //If the new node has a childs header
233 //give the child up to it...
235 if (temp.entries.contains(temp2.header)) {
236 temp.children.add(temp2);
242 //We fixed everything...let our parents know
245 //need to combine loops
246 while (!A.entries.isEmpty()) {
247 FlatNode node=(FlatNode)A.entries.iterator().next();
248 A.entries.remove(node);
249 treenode.entries.add(node);
251 //let the previous caller know that they have stuff todo
254 //We aren't adopting the new node
258 void findloopheaders(FlatNode current_nodeOrig) {
259 Stack stk = new Stack();
260 stk.push(current_nodeOrig);
261 while( !stk.isEmpty() ) {
262 FlatNode current_node = (FlatNode) stk.pop();
263 //look at the current node
266 //add it to the all inclusive root loop
267 root.entries.add(current_node);
269 //See if those we dominate are backedges
270 Set<FlatNode> children=dominator.children(current_node);
272 if (children!=null) {
273 for(Iterator<FlatNode> it=children.iterator(); it.hasNext(); ) {
274 FlatNode fn=it.next();
275 if (fn!=current_node)
282 void visit(FlatNode q) {
284 HashSet B=new HashSet();
286 //Loop through all of our outgoing edges
287 for (int i=0; i<q.numNext(); i++) {
289 FlatNode temp_to=q.getNext(i);
291 //Go up the dominator tree until
292 //we hit the root element or we
293 //find the node we jump back too
296 temp=dominator.idom(temp);
299 //If we found the node we jumped back to
305 A.entries.add(temp); //Push the header
307 B.add(q); //Put the backedge in the todo list
309 //Starting with the backedge, work on the incoming edges
310 //until we get back to the loop header...
311 //Then we have the entire natural loop
313 while(!B.isEmpty()) {
314 FlatNode newnode=(FlatNode)B.iterator().next();
317 //Add all of the new incoming edges that we haven't already
319 for (int j=0; j<newnode.numPrev(); j++) {
320 FlatNode from=newnode.getPrev(j);
321 if (!A.entries.contains(from))
325 //push the new node on our list of nodes in the loop
326 A.entries.add(newnode);
335 //Structure for building internal trees...
338 public HashSet entries=new HashSet();
339 public FlatNode header;
340 //Elements of the WorkSet of children are
342 public HashSet children=new HashSet();