loop analysis stuff
authorbdemsky <bdemsky>
Fri, 27 Mar 2009 09:02:25 +0000 (09:02 +0000)
committerbdemsky <bdemsky>
Fri, 27 Mar 2009 09:02:25 +0000 (09:02 +0000)
Robust/src/Analysis/Loops/DomTree.java
Robust/src/Analysis/Loops/LoopFinder.java
Robust/src/Analysis/Loops/UseDef.java

index aef079d..758876a 100644 (file)
@@ -1,10 +1,12 @@
 package Analysis.Loops;
+import java.util.Iterator;
 import java.util.Set;
 import java.util.HashSet;
 import java.util.Hashtable;
 import java.util.Vector;
 import java.util.Stack;
 import IR.Flat.FlatNode;
+import IR.Flat.FlatMethod;
 
 public class DomTree {
   Hashtable<FlatNode, FlatNode> domtable;
@@ -12,8 +14,8 @@ public class DomTree {
   Hashtable<FlatNode,Integer> vecindex;
   Hashtable<FlatNode, Set<FlatNode>> childtree;
 
-  public DomTree(FlatMethod fm) {
-    analyze(fm);
+  public DomTree(FlatMethod fm, boolean postdominator) {
+    analyze(fm, postdominator);
   }
 
   public FlatNode idom(FlatNode fn) {
@@ -21,16 +23,35 @@ public class DomTree {
   }
 
   public Set<FlatNode> children(FlatNode fn) {
-    return childtree(fn);
+    return childtree.get(fn);
   }
 
-  public void analyze(FlatMethod fm) {
-    DFS(fm);
+  public void analyze(FlatMethod fm, boolean postdominator) {
     domtable=new Hashtable<FlatNode, FlatNode>();
-    domtable.put(fm,fm);
-    HashSet<FlatNode> set=new HashSet<FlatNode> ();
-    set.add(fm);
-    childtree.put(fm,set);
+    if (postdominator) {
+      Set<FlatNode> fnodes=fm.getNodeSet();
+      Vector<FlatNode> v=new Vector<FlatNode>();
+      for(Iterator<FlatNode> fit=fnodes.iterator();fit.hasNext();) {
+       FlatNode fn=fit.next();
+       if (fn.numNext()==0)
+         v.add(fn);
+      }
+      FlatNode[] fnarray=new FlatNode[v.size()];
+      for(int i=0;i<v.size();i++) {
+       fnarray[i]=v.elementAt(i);
+       domtable.put(fnarray[i],fnarray[i]);
+       HashSet<FlatNode> set=new HashSet<FlatNode> ();
+       set.add(fnarray[i]);
+       childtree.put(fnarray[i],set);
+      }
+      DFS(fnarray, postdominator);
+    } else {
+      DFS(new FlatNode[] {fm}, postdominator);
+      HashSet<FlatNode> set=new HashSet<FlatNode> ();
+      domtable.put(fm,fm);
+      set.add(fm);
+      childtree.put(fm,set);
+    }
 
     boolean changed=true;
     while(changed) {
@@ -38,13 +59,13 @@ public class DomTree {
       for(int i=vec.size()-2;i>=0;i--) {
        FlatNode fn=vec.elementAt(i);
        FlatNode dom=null;
-       for(int j=0;j<fn.numPrev();j++) {
-         FlatNode ndom=domtable.get(fn.getPrev(i));
+       for(int j=0;j<(postdominator?fn.numNext():fn.numPrev());j++) {
+         FlatNode ndom=domtable.get(postdominator?fn.getNext(i):fn.getPrev(i));
          dom=intersect(dom,ndom);
        }
        if (!domtable.containsKey(fn)||
-           !domtable.get(fn).equals(ndom)) {
-         domtree.put(fn,dom);
+           !domtable.get(fn).equals(dom)) {
+         domtable.put(fn,dom);
          if (!childtree.containsKey(dom))
            childtree.put(dom, new HashSet<FlatNode>());
          childtree.get(dom).add(fn);
@@ -71,18 +92,20 @@ public class DomTree {
   }
 
 
-  public void DFS(FlatMethod fm) {
+  public void DFS(FlatNode[] fm, boolean postdominator) {
     vec=new Vector<FlatNode>();
     vecindex=new Hashtable<FlatNode,Integer>();
     HashSet visited=new HashSet();
     Stack<FlatNode> stack=new Stack<FlatNode>();
-    stack.push(fm);
-    visited.add(next);
+    for(int i=0;i<fm.length;i++) {
+      stack.push(fm[i]);
+      visited.add(fm[i]);
+    }
     mainloop:
     while(!stack.isEmpty()) {
       FlatNode fn=stack.peek();
-      for(int i=0;i<fn.numNext();i++) {
-       FlatNode next=fn.getNext(i);
+      for(int i=0;i<(postdominator?fn.numPrev():fn.numNext());i++) {
+       FlatNode next=postdominator?fn.getPrev(i):fn.getNext(i);
        if (!visited.contains(next)) {
          visited.add(next);
          stack.push(next);
@@ -95,6 +118,4 @@ public class DomTree {
       stack.pop();
     }
   }
-
-
 }
\ No newline at end of file
index ab87c14..c677972 100755 (executable)
@@ -15,7 +15,7 @@ import java.util.Iterator;
  * <code>LoopFinder</code> implements Dominator Tree Loop detection.
  * 
  * @author  Brian Demsky <bdemsky@mit.edu>
- * @version $Id: LoopFinder.java,v 1.1 2009/03/27 00:59:36 bdemsky Exp $
+ * @version $Id: LoopFinder.java,v 1.2 2009/03/27 09:02:25 bdemsky Exp $
  */
 
 public class LoopFinder implements Loops {
@@ -34,7 +34,7 @@ public class LoopFinder implements Loops {
   
   public LoopFinder(FlatMethod hc) {
        this.hc=hc;
-       this.dominator=new DomTree(hc);
+       this.dominator=new DomTree(hc,false);
        analyze();
        this.ptr=root;    
     }
@@ -71,7 +71,7 @@ public class LoopFinder implements Loops {
   public Set loopEntrances() {
     HashSet entries=new HashSet();
     analyze();
-    entries.push(ptr.header);
+    entries.add(ptr.header);
     return entries;
   }
   
@@ -91,13 +91,14 @@ public class LoopFinder implements Loops {
   public Set loopExcElements() {
     analyze();
     HashSet A=new HashSet(ptr.entries);
-    HashSet todo=new WorkSet();
+    HashSet todo=new HashSet();
     //Get the children
     todo.addAll(ptr.children);
 
     //Go down the tree
     while(!todo.isEmpty()) {
-      Loop currptr=(Loop)todo.pop();
+      Loop currptr=(Loop)todo.iterator().next();
+      todo.remove(currptr);
       todo.addAll(currptr.children);
       A.removeAll(currptr.entries);
     }
@@ -111,7 +112,7 @@ public class LoopFinder implements Loops {
     HashSet L=new HashSet();
     Iterator iterate=ptr.children.iterator();
     while (iterate.hasNext())
-      L.add(new LoopFinder(hc,grapher,dominator,root,(Loop) iterate.next()));
+      L.add(new LoopFinder(hc,dominator,root,(Loop) iterate.next()));
     return L;
   }
     
@@ -121,7 +122,7 @@ public class LoopFinder implements Loops {
   public Loops parentLoop() {
     analyze();
     if (ptr.parent!=null)
-      return new LoopFinder(hc,grapher,dominator,root,ptr.parent);
+      return new LoopFinder(hc,dominator,root,ptr.parent);
     else return null;
   }
   
@@ -204,7 +205,7 @@ public class LoopFinder implements Loops {
                
                if (stored==0) {
                    //We get a new child...
-                   treenode.children.push(A);
+                   treenode.children.add(A);
                    temp=A;
                }
                
@@ -231,7 +232,7 @@ public class LoopFinder implements Loops {
                            //give the child up to it...
                            
                            if (temp.entries.contains(temp2.header)) {
-                               temp.children.push(temp2);
+                               temp.children.add(temp2);
                                iterate2.remove();
                            }
                    }
@@ -242,7 +243,9 @@ public class LoopFinder implements Loops {
            } else {
                //need to combine loops
                while (!A.entries.isEmpty()) {
-                   treenode.entries.push(A.entries.removeLast());
+                 FlatNode node=(FlatNode)A.entries.iterator().next();
+                 A.entries.remove(node);
+                 treenode.entries.add(node);
                }
                //let the previous caller know that they have stuff todo
                return 2;
@@ -260,7 +263,7 @@ public class LoopFinder implements Loops {
            visit(current_node);
            
            //add it to the all inclusive root loop
-           root.entries.push(current_node);
+           root.entries.add(current_node);
            
            //See if those we dominate are backedges
            stk.addAll(dominator.children(current_node));
@@ -274,7 +277,7 @@ public class LoopFinder implements Loops {
     //Loop through all of our outgoing edges
     for (int i=0;i<q.numNext();i++) {
       FlatNode temp=q;
-      FlatNode temp_to=q.next(i);
+      FlatNode temp_to=q.getNext(i);
 
       //Go up the dominator tree until
       //we hit the root element or we
@@ -290,27 +293,28 @@ public class LoopFinder implements Loops {
       if (temp_to==temp) {
        
        //found a loop
-       A.entries.push(temp); //Push the header
+       A.entries.add(temp); //Push the header
        A.header=temp;
-       B.push(q); //Put the backedge in the todo list
+       B.add(q); //Put the backedge in the todo list
        
        //Starting with the backedge, work on the incoming edges
        //until we get back to the loop header...
        //Then we have the entire natural loop
        
        while(!B.isEmpty()) {
-         FlatNode newnode=(FlatNode)B.removeLast();
+         FlatNode newnode=(FlatNode)B.iterator().next();
+         B.remove(newnode);
          
          //Add all of the new incoming edges that we haven't already
          //visited
-         for (int j=0;j<newnode.numPrev;j++) {
-           FlatNode from=newnode.prev(j);
+         for (int j=0;j<newnode.numPrev();j++) {
+           FlatNode from=newnode.getPrev(j);
            if (!A.entries.contains(from))
-             B.push(from);
+             B.add(from);
          }
          
          //push the new node on our list of nodes in the loop
-         A.entries.push(newnode);
+         A.entries.add(newnode);
        }
        
        //save our new loop
index b72a05a..243c7da 100644 (file)
@@ -3,15 +3,30 @@ package Analysis.Loops;
 import IR.Flat.*;
 import java.util.HashSet;
 import java.util.Hashtable;
+import java.util.Set;
+import java.util.Iterator;
 
 public class UseDef{
   Hashtable<TempFlatPair, Set<FlatNode>> defs;
   Hashtable<TempFlatPair, Set<FlatNode>> uses;
 
+  public UseDef() {
+  }
+
   public UseDef(FlatMethod fm) {
     analyze(fm);
   }
 
+  /* Return FlatNodes that define Temp */
+  public Set<FlatNode> defMap(FlatNode fn, TempDescriptor t) {
+    return defs.get(new TempFlatPair(t,fn));
+  }
+
+  /* Return FlatNodes that use Temp */
+  public Set<FlatNode> useMap(FlatNode fn, TempDescriptor t) {
+    return uses.get(new TempFlatPair(t,fn));
+  }
+
   public void analyze(FlatMethod fm) {
     Hashtable<FlatNode, Set<TempFlatPair>> tmp=new Hashtable<FlatNode, Set<TempFlatPair>>();
     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
@@ -24,7 +39,7 @@ public class UseDef{
       HashSet<TempFlatPair> s=new HashSet<TempFlatPair>();
       for(int i=0;i<fn.numPrev();i++) {
        FlatNode prev=fn.getPrev(i);
-       HashSet<TempFlatPair> prevs=tmp.get(prev);
+       Set<TempFlatPair> prevs=tmp.get(prev);
        nexttfp:
        for(Iterator<TempFlatPair> tfit=prevs.iterator();tfit.hasNext();) {
          TempFlatPair tfp=tfit.next();
@@ -43,7 +58,7 @@ public class UseDef{
          !tmp.get(fn).equals(s)) {
        tmp.put(fn,s);
        for(int i=0;i<fn.numNext();i++)
-         toanalyze.put(fn.getNext(i));
+         toanalyze.add(fn.getNext(i));
       }
     }
     Set<FlatNode> fset=fm.getNodeSet();