From f67b4ce2d7b119ad234cf6f69be962bf8f989332 Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Fri, 27 Mar 2009 09:02:25 +0000
Subject: [PATCH 1/1] loop analysis stuff

---
 Robust/src/Analysis/Loops/DomTree.java    | 61 +++++++++++++++--------
 Robust/src/Analysis/Loops/LoopFinder.java | 42 +++++++++-------
 Robust/src/Analysis/Loops/UseDef.java     | 19 ++++++-
 3 files changed, 81 insertions(+), 41 deletions(-)

diff --git a/Robust/src/Analysis/Loops/DomTree.java b/Robust/src/Analysis/Loops/DomTree.java
index aef079de..758876ac 100644
--- a/Robust/src/Analysis/Loops/DomTree.java
+++ b/Robust/src/Analysis/Loops/DomTree.java
@@ -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
diff --git a/Robust/src/Analysis/Loops/LoopFinder.java b/Robust/src/Analysis/Loops/LoopFinder.java
index ab87c148..c6779720 100755
--- a/Robust/src/Analysis/Loops/LoopFinder.java
+++ b/Robust/src/Analysis/Loops/LoopFinder.java
@@ -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
diff --git a/Robust/src/Analysis/Loops/UseDef.java b/Robust/src/Analysis/Loops/UseDef.java
index b72a05a9..243c7da0 100644
--- a/Robust/src/Analysis/Loops/UseDef.java
+++ b/Robust/src/Analysis/Loops/UseDef.java
@@ -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();
-- 
2.34.1