Robust/src/Analysis/Loops/LoopFinder.java

   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
   4
   5 package Analysis.Loops;
   6
   7 import IR.Flat.FlatMethod;
   8 import IR.Flat.FlatNode;
   9 import java.util.HashSet;
  10 import java.util.Set;
  11 import java.util.Stack;
  12 import java.util.Hashtable;
  13 import java.util.Iterator;
  14 /**
  15  * <code>LoopFinder</code> implements Dominator Tree Loop detection.
  16  *
  17  * @author  Brian Demsky <bdemsky@mit.edu>
  18  * @version $Id: LoopFinder.java,v 1.1 2009/03/27 00:59:36 bdemsky Exp $
  19  */
  20
  21 public class LoopFinder implements Loops {
  22   DomTree dominator;
  23   FlatMethod hc,lasthc;
  24   HashSet setofloops;
  25   Loop root;
  26   Loop ptr;
  27
  28
  29   /** Creates a new LoopFinder object.
  30    * This call takes an HCode and a CFGrapher
  31    * and returns a LoopFinder object
  32    * at the root level.
  33    */
  34
  35   public LoopFinder(FlatMethod hc) {
  36         this.hc=hc;
  37         this.dominator=new DomTree(hc);
  38         analyze();
  39         this.ptr=root;
  40     }
  41
  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.*/
  46
  47   private LoopFinder(FlatMethod hc, DomTree dt, Loop root, Loop ptr) {
  48     this.lasthc=hc;
  49     this.hc=hc;
  50     this.dominator=dt;
  51     this.root=root;
  52     this.ptr=ptr;
  53   }
  54
  55   /*-----------------------------*/
  56
  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.*/
  60
  61   public Loops getRootloop(FlatMethod hc) {
  62     this.hc=hc;
  63     analyze();
  64     return new LoopFinder(hc,dominator,root,root);
  65   }
  66
  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.*/
  70
  71   public Set loopEntrances() {
  72     HashSet entries=new HashSet();
  73     analyze();
  74     entries.push(ptr.header);
  75     return entries;
  76   }
  77
  78
  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. */
  81
  82   public Set loopIncElements() {
  83     analyze();
  84     HashSet A=new HashSet(ptr.entries);
  85     return A;
  86   }
  87
  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.*/
  90
  91   public Set loopExcElements() {
  92     analyze();
  93     HashSet A=new HashSet(ptr.entries);
  94     HashSet todo=new WorkSet();
  95     //Get the children
  96     todo.addAll(ptr.children);
  97
  98     //Go down the tree
  99     while(!todo.isEmpty()) {
 100       Loop currptr=(Loop)todo.pop();
 101       todo.addAll(currptr.children);
 102       A.removeAll(currptr.entries);
 103     }
 104     return A;
 105   }
 106
 107   /** Returns a <code>Set</code> of loops that are nested inside of this loop.*/
 108
 109   public Set nestedLoops() {
 110     analyze();
 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()));
 115     return L;
 116   }
 117
 118   /** Returns the <code>Loops</code> that contains this loop.
 119    *  If this is the top level loop, this call returns a null pointer.*/
 120
 121   public Loops parentLoop() {
 122     analyze();
 123     if (ptr.parent!=null)
 124       return new LoopFinder(hc,grapher,dominator,root,ptr.parent);
 125     else return null;
 126   }
 127
 128   /*---------------------------*/
 129   // public information accessor methods.
 130
 131   /*---------------------------*/
 132   // Analysis code.
 133
 134
 135   /** Main analysis method. */
 136
 137   void analyze() {
 138     //Have we analyzed this set before?
 139     //If so, don't do it again!!!
 140     if (hc!=lasthc) {
 141
 142       //Did the caller hand us a bogus object?
 143       //If so, throw it something
 144
 145       lasthc=hc;
 146
 147       //Set up the top level loop, so we can fill it with HCodeElements
 148       //as we go along
 149       root=new Loop();
 150       root.header=hc;
 151
 152       //Set up a WorkSet for storing loops before we build the
 153       //nested loop tree
 154       setofloops=new HashSet();
 155
 156       //Find loops
 157       findloopheaders(hc);
 158
 159       //Build the nested loop tree
 160       buildtree();
 161     }
 162   }
 163   // end analysis.
 164
 165   void buildtree() {
 166     //go through set of generated loops
 167     while(!setofloops.isEmpty()) {
 168       //Pull out one
 169       Loop A=(Loop) setofloops.iterator().next();
 170       setofloops.remove(A);
 171
 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.");
 175     }
 176   }
 177
 178     //Adds a node to the tree...Its recursive
 179
 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))
 183
 184             //Do we share headers?
 185             if (treenode.header!=A.header) {
 186
 187                 //No...  Loop through our children to see if they want this
 188                 //node.
 189
 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
 193
 194                 int stored=0;
 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;
 201                 }
 202
 203                 //See what our children did for us
 204
 205                 if (stored==0) {
 206                     //We get a new child...
 207                     treenode.children.push(A);
 208                     temp=A;
 209                 }
 210
 211                 //Need to do cleanup for case 0 or 2
 212                 //temp points to the new child
 213
 214                 if (stored!=1) {
 215
 216                     //Have to make sure that none of the nodes under this one
 217                     //are children of the new node
 218
 219                     Iterator iterate2=treenode.children.iterator();
 220                     temp.parent=treenode;
 221
 222                     //Loop through the children
 223                     while (iterate2.hasNext()) {
 224                         Loop temp2=(Loop)iterate2.next();
 225
 226                         //Don't look at the new node...otherwise we will create
 227                         //a unreachable subtree
 228
 229                         if (temp2!=temp)
 230                             //If the new node has a childs header
 231                             //give the child up to it...
 232
 233                             if (temp.entries.contains(temp2.header)) {
 234                                 temp.children.push(temp2);
 235                                 iterate2.remove();
 236                             }
 237                     }
 238                 }
 239
 240                 //We fixed everything...let our parents know
 241                 return 1;
 242             } else {
 243                 //need to combine loops
 244                 while (!A.entries.isEmpty()) {
 245                     treenode.entries.push(A.entries.removeLast());
 246                 }
 247                 //let the previous caller know that they have stuff todo
 248                 return 2;
 249             }
 250         //We aren't adopting the new node
 251         else return 0;
 252     }
 253
 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
 260             visit(current_node);
 261
 262             //add it to the all inclusive root loop
 263             root.entries.push(current_node);
 264
 265             //See if those we dominate are backedges
 266             stk.addAll(dominator.children(current_node));
 267         }
 268     }
 269
 270   void visit(FlatNode q) {
 271     Loop A=new Loop();
 272     HashSet B=new HashSet();
 273
 274     //Loop through all of our outgoing edges
 275     for (int i=0;i<q.numNext();i++) {
 276       FlatNode temp=q;
 277       FlatNode temp_to=q.next(i);
 278
 279       //Go up the dominator tree until
 280       //we hit the root element or we
 281       //find the node we jump back too
 282       while ((temp!=hc)&&
 283              (temp_to!=temp)) {
 284         temp=dominator.idom(temp);
 285       }
 286
 287       //If we found the node we jumped back to
 288       //then build loop
 289
 290       if (temp_to==temp) {
 291
 292         //found a loop
 293         A.entries.push(temp); //Push the header
 294         A.header=temp;
 295         B.push(q); //Put the backedge in the todo list
 296
 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
 300
 301         while(!B.isEmpty()) {
 302           FlatNode newnode=(FlatNode)B.removeLast();
 303
 304           //Add all of the new incoming edges that we haven't already
 305           //visited
 306           for (int j=0;j<newnode.numPrev;j++) {
 307             FlatNode from=newnode.prev(j);
 308             if (!A.entries.contains(from))
 309               B.push(from);
 310           }
 311
 312           //push the new node on our list of nodes in the loop
 313           A.entries.push(newnode);
 314         }
 315
 316         //save our new loop
 317         setofloops.add(A);
 318       }
 319     }
 320   }
 321
 322   //Structure for building internal trees...
 323
 324   class Loop {
 325     public HashSet entries=new HashSet();
 326     public FlatNode header;
 327     //Elements of the WorkSet of children are
 328     //of the type Loop
 329     public HashSet children=new HashSet();
 330     public Loop parent;
 331   }
 332 }