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.2 2009/03/27 09:02:25 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       //Find loops
 158       findloopheaders(hc);
 159
 160       //Build the nested loop tree
 161       buildtree();
 162     }
 163   }
 164   // end analysis.
 165
 166   void buildtree() {
 167     //go through set of generated loops
 168     while(!setofloops.isEmpty()) {
 169       //Pull out one
 170       Loop A=(Loop) setofloops.iterator().next();
 171       setofloops.remove(A);
 172
 173       //Add it to the tree, complain if oddness
 174       if (addnode(A, root)!=1)
 175         System.out.println("Evil Error in LoopFinder while building tree.");
 176     }
 177   }
 178
 179     //Adds a node to the tree...Its recursive
 180
 181     int addnode(Loop A, Loop treenode) {
 182         //Only need to go deeper if the header is contained in this loop
 183         if (treenode.entries.contains(A.header))
 184
 185             //Do we share headers?
 186             if (treenode.header!=A.header) {
 187
 188                 //No...  Loop through our children to see if they want this
 189                 //node.
 190
 191                 //Use integers for tri-state:
 192                 //0=not stored here, 1=stored and everything is good
 193                 //2=combined 2 natural loops with same header...need cleanup
 194
 195                 int stored=0;
 196                 Iterator iterate=treenode.children.iterator();
 197                 Loop temp=new Loop();
 198                 while (iterate.hasNext()) {
 199                     temp=(Loop) iterate.next();
 200                     stored=addnode(A,temp);
 201                     if (stored!=0) break;
 202                 }
 203
 204                 //See what our children did for us
 205
 206                 if (stored==0) {
 207                     //We get a new child...
 208                     treenode.children.add(A);
 209                     temp=A;
 210                 }
 211
 212                 //Need to do cleanup for case 0 or 2
 213                 //temp points to the new child
 214
 215                 if (stored!=1) {
 216
 217                     //Have to make sure that none of the nodes under this one
 218                     //are children of the new node
 219
 220                     Iterator iterate2=treenode.children.iterator();
 221                     temp.parent=treenode;
 222
 223                     //Loop through the children
 224                     while (iterate2.hasNext()) {
 225                         Loop temp2=(Loop)iterate2.next();
 226
 227                         //Don't look at the new node...otherwise we will create
 228                         //a unreachable subtree
 229
 230                         if (temp2!=temp)
 231                             //If the new node has a childs header
 232                             //give the child up to it...
 233
 234                             if (temp.entries.contains(temp2.header)) {
 235                                 temp.children.add(temp2);
 236                                 iterate2.remove();
 237                             }
 238                     }
 239                 }
 240
 241                 //We fixed everything...let our parents know
 242                 return 1;
 243             } else {
 244                 //need to combine loops
 245                 while (!A.entries.isEmpty()) {
 246                   FlatNode node=(FlatNode)A.entries.iterator().next();
 247                   A.entries.remove(node);
 248                   treenode.entries.add(node);
 249                 }
 250                 //let the previous caller know that they have stuff todo
 251                 return 2;
 252             }
 253         //We aren't adopting the new node
 254         else return 0;
 255     }
 256
 257     void findloopheaders(FlatNode current_nodeOrig) {
 258         Stack stk = new Stack();
 259         stk.push( current_nodeOrig );
 260         while( ! stk.isEmpty() ){
 261             FlatNode current_node = (FlatNode) stk.pop();
 262             //look at the current node
 263             visit(current_node);
 264
 265             //add it to the all inclusive root loop
 266             root.entries.add(current_node);
 267
 268             //See if those we dominate are backedges
 269             stk.addAll(dominator.children(current_node));
 270         }
 271     }
 272
 273   void visit(FlatNode q) {
 274     Loop A=new Loop();
 275     HashSet B=new HashSet();
 276
 277     //Loop through all of our outgoing edges
 278     for (int i=0;i<q.numNext();i++) {
 279       FlatNode temp=q;
 280       FlatNode temp_to=q.getNext(i);
 281
 282       //Go up the dominator tree until
 283       //we hit the root element or we
 284       //find the node we jump back too
 285       while ((temp!=hc)&&
 286              (temp_to!=temp)) {
 287         temp=dominator.idom(temp);
 288       }
 289
 290       //If we found the node we jumped back to
 291       //then build loop
 292
 293       if (temp_to==temp) {
 294
 295         //found a loop
 296         A.entries.add(temp); //Push the header
 297         A.header=temp;
 298         B.add(q); //Put the backedge in the todo list
 299
 300         //Starting with the backedge, work on the incoming edges
 301         //until we get back to the loop header...
 302         //Then we have the entire natural loop
 303
 304         while(!B.isEmpty()) {
 305           FlatNode newnode=(FlatNode)B.iterator().next();
 306           B.remove(newnode);
 307
 308           //Add all of the new incoming edges that we haven't already
 309           //visited
 310           for (int j=0;j<newnode.numPrev();j++) {
 311             FlatNode from=newnode.getPrev(j);
 312             if (!A.entries.contains(from))
 313               B.add(from);
 314           }
 315
 316           //push the new node on our list of nodes in the loop
 317           A.entries.add(newnode);
 318         }
 319
 320         //save our new loop
 321         setofloops.add(A);
 322       }
 323     }
 324   }
 325
 326   //Structure for building internal trees...
 327
 328   class Loop {
 329     public HashSet entries=new HashSet();
 330     public FlatNode header;
 331     //Elements of the WorkSet of children are
 332     //of the type Loop
 333     public HashSet children=new HashSet();
 334     public Loop parent;
 335   }
 336 }