From 26ad8ed764373b80aa4d0d5b106edf4c45b8f8eb Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Sat, 7 Nov 2009 08:51:53 +0000
Subject: [PATCH] optimize some analysis so they run faster...benchmarks were
 taking too long to compile and too much memory...idea is to prune temp sets
 using the liveness analysis

---
 Robust/src/Analysis/Locality/DelayComputation.java |  3 +++
 Robust/src/Analysis/Loops/CopyPropagation.java     | 14 +++++++++-----
 Robust/src/Analysis/Loops/UseDef.java              |  5 +++++
 3 files changed, 17 insertions(+), 5 deletions(-)

diff --git a/Robust/src/Analysis/Locality/DelayComputation.java b/Robust/src/Analysis/Locality/DelayComputation.java
index dd8defa0..e6c45bd4 100644
--- a/Robust/src/Analysis/Locality/DelayComputation.java
+++ b/Robust/src/Analysis/Locality/DelayComputation.java
@@ -394,6 +394,7 @@ public class DelayComputation {
 	continue;
       }
 
+      Set<TempDescriptor> liveset=livemap.get(fn);
       //Do merge on incoming edges
       for(int i=0;i<fn.numPrev();i++) {
 	FlatNode fnprev=fn.getPrev(i);
@@ -401,6 +402,8 @@ public class DelayComputation {
 	if (prevmap!=null)
 	  for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
 	    TempDescriptor tmp=tmpit.next();
+	    if (!liveset.contains(tmp)) //skip dead temps
+	      continue;
 	    if (!tmptofn.containsKey(tmp))
 	      tmptofn.put(tmp, new HashSet<FlatNode>());
 	    tmptofn.get(tmp).addAll(prevmap.get(tmp));
diff --git a/Robust/src/Analysis/Loops/CopyPropagation.java b/Robust/src/Analysis/Loops/CopyPropagation.java
index 26b13f64..16e8aafc 100644
--- a/Robust/src/Analysis/Loops/CopyPropagation.java
+++ b/Robust/src/Analysis/Loops/CopyPropagation.java
@@ -6,13 +6,14 @@ import java.util.Hashtable;
 import java.util.HashSet;
 import java.util.Set;
 import java.util.Map;
+import Analysis.Liveness;
 
 public class CopyPropagation {
   public 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;
@@ -32,6 +33,7 @@ public class CopyPropagation {
 	  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)
@@ -39,10 +41,12 @@ public class CopyPropagation {
 	  for(Iterator tmpit=tp.entrySet().iterator();tmpit.hasNext();) {
 	    Map.Entry t=(Map.Entry)tmpit.next();
 	    TempDescriptor tmp=(TempDescriptor)t.getKey();
-	    
-	    if (!tab.containsKey(tmp))
-	      tab.put(tmp, tp.get(tmp));
-	    else if (tab.get(tmp)!=tp.get(tmp)) {
+	    if (!liveset.contains(tmp))
+	      continue;
+	    TempDescriptor dsttmp=tp.get(tmp);
+	    if (!tab.containsKey(tmp)) {
+	      tab.put(tmp, dsttmp);
+	    } else if (tab.get(tmp)!=dsttmp) {
 	      tab.put(tmp, bogustd);
 	    }
 	  }
diff --git a/Robust/src/Analysis/Loops/UseDef.java b/Robust/src/Analysis/Loops/UseDef.java
index 7bf6b54c..50d44f4d 100644
--- a/Robust/src/Analysis/Loops/UseDef.java
+++ b/Robust/src/Analysis/Loops/UseDef.java
@@ -5,6 +5,7 @@ import java.util.HashSet;
 import java.util.Hashtable;
 import java.util.Set;
 import java.util.Iterator;
+import Analysis.Liveness;
 
 public class UseDef{
   Hashtable<TempFlatPair, Set<FlatNode>> defs;
@@ -38,6 +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);
     toanalyze.addAll(fm.getNodeSet());
     while(!toanalyze.isEmpty()) {
       FlatNode fn=toanalyze.iterator().next();
@@ -45,6 +47,7 @@ public class UseDef{
 
       toanalyze.remove(fn);
       HashSet<TempFlatPair> s=new HashSet<TempFlatPair>();
+      Set<TempDescriptor> liveset=livemap.get(fn);
       for(int i=0;i<fn.numPrev();i++) {
 	FlatNode prev=fn.getPrev(i);
 	Set<TempFlatPair> prevs=tmp.get(prev);
@@ -52,6 +55,8 @@ public class UseDef{
 	  nexttfp:
 	  for(Iterator<TempFlatPair> tfit=prevs.iterator();tfit.hasNext();) {
 	    TempFlatPair tfp=tfit.next();
+	    if (!liveset.contains(tfp.t))
+	      continue;
 	    for(int j=0;j<fnwrites.length;j++) {
 	      if (tfp.t==fnwrites[j])
 		continue nexttfp;
-- 
2.34.1