1) allow to set the maximum threshold for the liveness analysis. if threashold is...

diff --git a/Robust/src/Analysis/Liveness.java b/Robust/src/Analysis/Liveness.java
index b4b3a8dcf017a5a513375d1b7040f54977bb61ae..1374b24e14c265e91f5b86cfc711a58622a6dfd4 100644 (file)
--- 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.*/
 
   /* 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();
     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 (!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));
       }
        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) {
   }
 
   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();) {
     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 ) ) {
 
   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 );
   }
     }
     return fm2liveMap.get( fm ).get( fn );
   }

diff --git a/Robust/src/Analysis/Locality/DelayComputation.java b/Robust/src/Analysis/Locality/DelayComputation.java
index d032cfae3111e7e386b340e7048e544f20a84d42..2d9cbe10dcade3965d836337e2436d541847881b 100644 (file)
--- 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>();
 
 
     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();
 
     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();
     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());
 
 
     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();
     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());
     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);
       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>>>();
     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 44fb4790c84828773ad4a92fbdbf0a7da974f5cc..eb9aad85878fb0dccd0c354df5ca9c8b55e69dae 100644 (file)
--- 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);
     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);
 
     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);
     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);
 
     tovisit.add(fm);
     discovered.add(fm);
 

diff --git a/Robust/src/Analysis/Locality/LocalityAnalysis.java b/Robust/src/Analysis/Locality/LocalityAnalysis.java
index 0441898444eb8bd9e2d8edb60f66c3da788e8517..d036269e8db55cdeff88b18d7a2895af3e633031 100644 (file)
--- 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();
 
     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, 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>();
     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 9615fdb1d5fffcf65ca3d73505e77185e46b4f59..efa1f8437a7d82b5c239885a478cb1c0fc87ad3e 100644 (file)
--- 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);
         }
       }
       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++) {
       //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:
 
       switch(fn.kind()) {
       case FKind.FlatAtomicEnterNode:

diff --git a/Robust/src/Analysis/Loops/CopyPropagation.java b/Robust/src/Analysis/Loops/CopyPropagation.java
index c4eead83dc21a772da527dc876463e759de00629..06cff5da07b7493018ff154e28c87b98d9cfd17e 100644 (file)
--- 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) {
   }
 
   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, 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);
       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;
         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
 
           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)
         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)) {
               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);
             }
           }
         }
             } 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++) {
         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 dabb5fd1977ebd063089f369ce1b036060df84c9..b58c1a4ce81153c29e0c41a592a74389384dc55a 100644 (file)
--- 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>();
   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();
     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 5a648767050f2b0c3678e4cc79b8910747f62700..8b0ce00bfac302c3987be65ed739192fd9236ab1 100644 (file)
--- 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));
   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) {
       for(BBlock bblock : blockMap.get(fm).getBlocks()) {
         FlatNode fn=bblock.nodes.get(0);
         if (fn==fm) {