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.3 2009/04/03 09:06:12 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,false);
  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.add(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 HashSet();
  95     //Get the children
  96     todo.addAll(ptr.children);
  97
  98     //Go down the tree
  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);
 104     }
 105     return A;
 106   }
 107
 108   /** Returns a <code>Set</code> of loops that are nested inside of this loop.*/
 109
 110   public Set nestedLoops() {
 111     analyze();
 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()));
 116     return L;
 117   }
 118
 119   /** Returns the <code>Loops</code> that contains this loop.
 120    *  If this is the top level loop, this call returns a null pointer.*/
 121
 122   public Loops parentLoop() {
 123     analyze();
 124     if (ptr.parent!=null)
 125       return new LoopFinder(hc,dominator,root,ptr.parent);
 126     else return null;
 127   }
 128
 129   /*---------------------------*/
 130   // public information accessor methods.
 131
 132   /*---------------------------*/
 133   // Analysis code.
 134
 135
 136   /** Main analysis method. */
 137
 138   void analyze() {
 139     //Have we analyzed this set before?
 140     //If so, don't do it again!!!
 141     if (hc!=lasthc) {
 142
 143       //Did the caller hand us a bogus object?
 144       //If so, throw it something
 145
 146       lasthc=hc;
 147
 148       //Set up the top level loop, so we can fill it with HCodeElements
 149       //as we go along
 150       root=new Loop();
 151       root.header=hc;
 152
 153       //Set up a WorkSet for storing loops before we build the
 154       //nested loop tree
 155       setofloops=new HashSet();
 156
 157
 158       //Find loops
 159       findloopheaders(hc);
 160
 161       //Build the nested loop tree
 162       buildtree();
 163     }
 164   }
 165   // end analysis.
 166
 167   void buildtree() {
 168     //go through set of generated loops
 169     while(!setofloops.isEmpty()) {
 170       //Pull out one
 171       Loop A=(Loop) setofloops.iterator().next();
 172       setofloops.remove(A);
 173
 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.");
 177     }
 178   }
 179
 180     //Adds a node to the tree...Its recursive
 181
 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))
 185
 186             //Do we share headers?
 187             if (treenode.header!=A.header) {
 188
 189                 //No...  Loop through our children to see if they want this
 190                 //node.
 191
 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
 195
 196                 int stored=0;
 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;
 203                 }
 204
 205                 //See what our children did for us
 206
 207                 if (stored==0) {
 208                     //We get a new child...
 209                     treenode.children.add(A);
 210                     temp=A;
 211                 }
 212
 213                 //Need to do cleanup for case 0 or 2
 214                 //temp points to the new child
 215
 216                 if (stored!=1) {
 217
 218                     //Have to make sure that none of the nodes under this one
 219                     //are children of the new node
 220
 221                     Iterator iterate2=treenode.children.iterator();
 222                     temp.parent=treenode;
 223
 224                     //Loop through the children
 225                     while (iterate2.hasNext()) {
 226                         Loop temp2=(Loop)iterate2.next();
 227
 228                         //Don't look at the new node...otherwise we will create
 229                         //a unreachable subtree
 230
 231                         if (temp2!=temp)
 232                             //If the new node has a childs header
 233                             //give the child up to it...
 234
 235                             if (temp.entries.contains(temp2.header)) {
 236                                 temp.children.add(temp2);
 237                                 iterate2.remove();
 238                             }
 239                     }
 240                 }
 241
 242                 //We fixed everything...let our parents know
 243                 return 1;
 244             } else {
 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);
 250                 }
 251                 //let the previous caller know that they have stuff todo
 252                 return 2;
 253             }
 254         //We aren't adopting the new node
 255         else return 0;
 256     }
 257
 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
 264             visit(current_node);
 265
 266             //add it to the all inclusive root loop
 267             root.entries.add(current_node);
 268
 269             //See if those we dominate are backedges
 270             Set<FlatNode> children=dominator.children(current_node);
 271
 272             if (children!=null) {
 273               for(Iterator<FlatNode> it=children.iterator();it.hasNext();) {
 274                 FlatNode fn=it.next();
 275                 if (fn!=current_node)
 276                   stk.push(fn);
 277               }
 278             }
 279         }
 280     }
 281
 282   void visit(FlatNode q) {
 283     Loop A=new Loop();
 284     HashSet B=new HashSet();
 285
 286     //Loop through all of our outgoing edges
 287     for (int i=0;i<q.numNext();i++) {
 288       FlatNode temp=q;
 289       FlatNode temp_to=q.getNext(i);
 290
 291       //Go up the dominator tree until
 292       //we hit the root element or we
 293       //find the node we jump back too
 294       while ((temp!=hc)&&
 295              (temp_to!=temp)) {
 296         temp=dominator.idom(temp);
 297       }
 298
 299       //If we found the node we jumped back to
 300       //then build loop
 301
 302       if (temp_to==temp) {
 303
 304         //found a loop
 305         A.entries.add(temp); //Push the header
 306         A.header=temp;
 307         B.add(q); //Put the backedge in the todo list
 308
 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
 312
 313         while(!B.isEmpty()) {
 314           FlatNode newnode=(FlatNode)B.iterator().next();
 315           B.remove(newnode);
 316
 317           //Add all of the new incoming edges that we haven't already
 318           //visited
 319           for (int j=0;j<newnode.numPrev();j++) {
 320             FlatNode from=newnode.getPrev(j);
 321             if (!A.entries.contains(from))
 322               B.add(from);
 323           }
 324
 325           //push the new node on our list of nodes in the loop
 326           A.entries.add(newnode);
 327         }
 328
 329         //save our new loop
 330         setofloops.add(A);
 331       }
 332     }
 333   }
 334
 335   //Structure for building internal trees...
 336
 337   class Loop {
 338     public HashSet entries=new HashSet();
 339     public FlatNode header;
 340     //Elements of the WorkSet of children are
 341     //of the type Loop
 342     public HashSet children=new HashSet();
 343     public Loop parent;
 344   }
 345 }