From: yeom <yeom>
Date: Sat, 13 Aug 2011 01:28:26 +0000 (+0000)
Subject: 1) allow to set the maximum threshold for the liveness analysis. if threashold is... 
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=b124b7bf09a5eed6e272119acba9cfc5a1374b60;hp=88cc6f37e1158f55870e1b55100e91a09b8d1556

1) allow to set the maximum threshold for the liveness analysis. if threashold is set to -1, there is no threshold. 2) bug fix on CSE
---

diff --git a/Robust/src/Analysis/Liveness.java b/Robust/src/Analysis/Liveness.java
index b4b3a8dc..1374b24e 100644
--- a/Robust/src/Analysis/Liveness.java
+++ b/Robust/src/Analysis/Liveness.java
@@ -13,10 +13,10 @@ public class Liveness {
   /* This methods takes in a FlatMethod and returns a map from a
    * FlatNode to the set of temps that are live into the FlatNode.*/
 
-  public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
-    return computeLiveTemps(fm, null);
+  public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, int threshold) {
+    return computeLiveTemps(fm, null, threshold);
   }
-  public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, LocalityBinding lb) {
+  public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, LocalityBinding lb, int threshold) {
     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
     
     Set<FlatNode> toprocess=fm.getNodeSet();
@@ -42,6 +42,9 @@ public class Liveness {
       if (!nodetotemps.containsKey(fn)||
           !nodetotemps.get(fn).equals(tempset)) {
 	nodetotemps.put(fn, tempset);
+	if(threshold!=-1 && nodetotemps.size()>threshold){
+	  return null;
+	}
 	for(int i=0; i<fn.numPrev(); i++)
 	  toprocess.add(fn.getPrev(i));
       }
@@ -54,7 +57,7 @@ public class Liveness {
   }
 
   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm, LocalityBinding lb) {
-    Hashtable<FlatNode, Set<TempDescriptor>> liveinmap=computeLiveTemps(fm, lb);
+    Hashtable<FlatNode, Set<TempDescriptor>> liveinmap=computeLiveTemps(fm, lb,-1);
     Hashtable<FlatNode, Set<TempDescriptor>> liveoutmap=new Hashtable<FlatNode, Set<TempDescriptor>>();
     
     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext();) {
@@ -88,7 +91,7 @@ public class Liveness {
 
   public Set<TempDescriptor> getLiveInTemps( FlatMethod fm, FlatNode fn ) {
     if( !fm2liveMap.containsKey( fm ) ) {
-      fm2liveMap.put( fm, Liveness.computeLiveTemps( fm ) );
+      fm2liveMap.put( fm, Liveness.computeLiveTemps( fm,-1 ) );
     }
     return fm2liveMap.get( fm ).get( fn );
   }
diff --git a/Robust/src/Analysis/Locality/DelayComputation.java b/Robust/src/Analysis/Locality/DelayComputation.java
index d032cfae..2d9cbe10 100644
--- a/Robust/src/Analysis/Locality/DelayComputation.java
+++ b/Robust/src/Analysis/Locality/DelayComputation.java
@@ -199,7 +199,7 @@ public class DelayComputation {
 
     Set<TempDescriptor> liveinto=new HashSet<TempDescriptor>();
 
-    Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true);
+    Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm,-1), true);
 
     for(Iterator<FlatNode> fnit=secondpart.iterator(); fnit.hasNext(); ) {
       FlatNode fn=fnit.next();
@@ -227,8 +227,8 @@ public class DelayComputation {
     MethodDescriptor md=lb.getMethod();
     FlatMethod fm=state.getMethodFlat(md);
     Set<FlatNode> exits=faen.getExits();
-    Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
-    Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true);
+    Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm,-1);
+    Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm,-1), true);
 
     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
 
@@ -272,7 +272,7 @@ public class DelayComputation {
     MethodDescriptor md=lb.getMethod();
     FlatMethod fm=state.getMethodFlat(md);
     Set<FlatNode> exits=faen.getExits();
-    Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
+    Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm,-1);
     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, livemap, true);
 
     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
@@ -324,7 +324,7 @@ public class DelayComputation {
       derefset=derefmap.get(lb);
     HashSet<FlatNode> otherset=othermap.get(lb);
     HashSet<FlatNode> cannotdelayset=cannotdelaymap.get(lb);
-    Hashtable<FlatNode,Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
+    Hashtable<FlatNode,Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm,-1);
     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefsmap=ReachingDefs.computeReachingDefs(fm, livemap, true);
     HashSet<FlatNode> unionset=new HashSet<FlatNode>(delayedset);
     Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>> map=new Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>>();
diff --git a/Robust/src/Analysis/Locality/DiscoverConflicts.java b/Robust/src/Analysis/Locality/DiscoverConflicts.java
index 44fb4790..eb9aad85 100644
--- a/Robust/src/Analysis/Locality/DiscoverConflicts.java
+++ b/Robust/src/Analysis/Locality/DiscoverConflicts.java
@@ -568,7 +568,7 @@ public class DiscoverConflicts {
     MethodDescriptor md=lb.getMethod();
     FlatMethod fm=state.getMethodFlat(md);
     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
-    Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
+    Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm,-1);
     tovisit.add(fm);
     discovered.add(fm);
 
@@ -726,7 +726,7 @@ public class DiscoverConflicts {
     MethodDescriptor md=lb.getMethod();
     FlatMethod fm=state.getMethodFlat(md);
     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
-    Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
+    Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm,-1);
     tovisit.add(fm);
     discovered.add(fm);
 
diff --git a/Robust/src/Analysis/Locality/LocalityAnalysis.java b/Robust/src/Analysis/Locality/LocalityAnalysis.java
index 04418984..d036269e 100644
--- a/Robust/src/Analysis/Locality/LocalityAnalysis.java
+++ b/Robust/src/Analysis/Locality/LocalityAnalysis.java
@@ -323,7 +323,7 @@ public class LocalityAnalysis {
       }
     }
 
-    Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
+    Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm,-1);
 
     while(!tovisit.isEmpty()) {
       FlatNode fn=tovisit.iterator().next();
@@ -1213,7 +1213,7 @@ public class LocalityAnalysis {
     Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
     MethodDescriptor md=lb.getMethod();
     FlatMethod fm=state.getMethodFlat(md);
-    Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=Liveness.computeLiveTemps(fm);
+    Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=Liveness.computeLiveTemps(fm,-1);
     Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> nodetosavetemps=new Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>();
     tempstosave.put(lb, nodetosavetemps);
     Hashtable<FlatNode, FlatAtomicEnterNode> nodemap=new Hashtable<FlatNode, FlatAtomicEnterNode>();
diff --git a/Robust/src/Analysis/Loops/CSE.java b/Robust/src/Analysis/Loops/CSE.java
index 9615fdb1..efa1f843 100644
--- a/Robust/src/Analysis/Loops/CSE.java
+++ b/Robust/src/Analysis/Loops/CSE.java
@@ -37,13 +37,26 @@ public class CSE {
         }
       }
       Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
-
+      
+//      if(tab.size()>1000){
+//        System.out.println("Skipping CSE of "+fm.getMethod()+" due to size.");
+//        return;
+//      }
+      
       //Do kills of expression/variable mappings
       TempDescriptor[] write=fn.writesTemps();
       for(int i=0; i<write.length; i++) {
-        if (tab.containsKey(write[i]))
-          tab.remove(write[i]);
+        for(Iterator it=tab.entrySet().iterator(); it.hasNext(); ) {
+          Map.Entry m=(Map.Entry)it.next();
+          TempDescriptor td=(TempDescriptor)m.getValue();
+          if(td.equals(write[i])){
+            it.remove();
+          }        
+        }
       }
+      
+      
+      
 
       switch(fn.kind()) {
       case FKind.FlatAtomicEnterNode:
diff --git a/Robust/src/Analysis/Loops/CopyPropagation.java b/Robust/src/Analysis/Loops/CopyPropagation.java
index c4eead83..06cff5da 100644
--- a/Robust/src/Analysis/Loops/CopyPropagation.java
+++ b/Robust/src/Analysis/Loops/CopyPropagation.java
@@ -13,27 +13,36 @@ public class CopyPropagation {
   }
 
   public void optimize(FlatMethod fm) {
-    Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
     Hashtable<FlatNode, Hashtable<TempDescriptor, TempDescriptor>> table
       =new Hashtable<FlatNode, Hashtable<TempDescriptor, TempDescriptor>>();
     boolean changed=false;
     TempDescriptor bogustd=new TempDescriptor("bogus");
     do {
+      Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm,1000);
+      if(livetemps==null){
+        System.out.println("Skipping CopyPropagation of "+fm.getMethod()+" due to size.");
+        return;
+      }
       changed=false;
       HashSet tovisit=new HashSet();
       tovisit.add(fm);
       while(!tovisit.isEmpty()) {
         FlatNode fn=(FlatNode) tovisit.iterator().next();
         tovisit.remove(fn);
-
         Hashtable<TempDescriptor, TempDescriptor> tab;
-        if (fn.numPrev()>=1&&table.containsKey(fn.getPrev(0)))
-          tab=new Hashtable<TempDescriptor, TempDescriptor>(table.get(fn.getPrev(0)));
-        else
+        Set<TempDescriptor> liveset=livetemps.get(fn);
+
+        if (fn.numPrev()>=1&&table.containsKey(fn.getPrev(0))) {
+          tab=new Hashtable<TempDescriptor, TempDescriptor>();
+          for(Map.Entry<TempDescriptor, TempDescriptor> entry:table.get(fn.getPrev(0)).entrySet()) {
+              if (liveset.contains(entry.getKey())) {
+                  tab.put(entry.getKey(), entry.getValue());
+              }
+          }
+        } else
           tab=new Hashtable<TempDescriptor, TempDescriptor>();
         //Compute intersection
 
-        Set<TempDescriptor> liveset=livetemps.get(fn);
         for(int i=1; i<fn.numPrev(); i++) {
           Hashtable<TempDescriptor, TempDescriptor> tp=table.get(fn.getPrev(i));
           if (tp==null)
@@ -45,13 +54,13 @@ public class CopyPropagation {
               continue;
             TempDescriptor dsttmp=tp.get(tmp);
             if (!tab.containsKey(tmp)) {
-              tab.put(tmp, dsttmp);
+                tab.put(tmp, dsttmp);
             } else if (tab.get(tmp)!=dsttmp) {
               tab.put(tmp, bogustd);
             }
           }
         }
-
+        
         HashSet<TempDescriptor> toremove=new HashSet<TempDescriptor>();
         TempDescriptor[] writes=fn.writesTemps();
         for(int i=0; i<writes.length; i++) {
diff --git a/Robust/src/Analysis/Loops/UseDef.java b/Robust/src/Analysis/Loops/UseDef.java
index dabb5fd1..b58c1a4c 100644
--- a/Robust/src/Analysis/Loops/UseDef.java
+++ b/Robust/src/Analysis/Loops/UseDef.java
@@ -39,7 +39,7 @@ public class UseDef {
   public void analyze(FlatMethod fm) {
     Hashtable<FlatNode, Set<TempFlatPair>> tmp=new Hashtable<FlatNode, Set<TempFlatPair>>();
     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
-    Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
+    Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm,-1);
     toanalyze.addAll(fm.getNodeSet());
     while(!toanalyze.isEmpty()) {
       FlatNode fn=toanalyze.iterator().next();
diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java
index 5a648767..8b0ce00b 100644
--- a/Robust/src/Analysis/Pointer/Pointer.java
+++ b/Robust/src/Analysis/Pointer/Pointer.java
@@ -76,7 +76,7 @@ public class Pointer implements HeapAnalysis {
   public BasicBlock getBBlock(FlatMethod fm) {
     if (!blockMap.containsKey(fm)) {
       blockMap.put(fm, BasicBlock.getBBlock(fm));
-      Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
+      Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm,-1);
       for(BBlock bblock : blockMap.get(fm).getBlocks()) {
         FlatNode fn=bblock.nodes.get(0);
         if (fn==fm) {