From 580fad79940663d7d1bbaf75063d4ebf0c158556 Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Fri, 19 Jun 2009 09:41:54 +0000
Subject: [PATCH] changes

---
 .../Analysis/Locality/DelayComputation.java   | 147 ++++++++++++++++--
 Robust/src/IR/Flat/BuildCode.java             |   2 +-
 2 files changed, 132 insertions(+), 17 deletions(-)

diff --git a/Robust/src/Analysis/Locality/DelayComputation.java b/Robust/src/Analysis/Locality/DelayComputation.java
index fa765069..8bc4713f 100644
--- a/Robust/src/Analysis/Locality/DelayComputation.java
+++ b/Robust/src/Analysis/Locality/DelayComputation.java
@@ -8,6 +8,7 @@ import Analysis.Loops.GlobalFieldType;
 import java.util.HashSet;
 import java.util.Hashtable;
 import java.util.Set;
+import java.util.Stack;
 import java.util.Iterator;
 
 public class DelayComputation {
@@ -16,12 +17,18 @@ public class DelayComputation {
   TypeAnalysis typeanalysis;
   GlobalFieldType gft;
   DiscoverConflicts dcopts;
+  Hashtable<LocalityBinding, HashSet<FlatNode>> notreadymap;
+  Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap;
+  Hashtable<LocalityBinding, HashSet<FlatNode>> othermap;
 
   public DelayComputation(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
     this.locality=locality;
     this.state=state;
     this.typeanalysis=typeanalysis;
     this.gft=gft;
+    this.notreadymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
+    this.cannotdelaymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
+    this.othermap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
   }
 
   public DiscoverConflicts getConflicts() {
@@ -35,6 +42,127 @@ public class DelayComputation {
     }
   }
 
+  public HashSet<FlatNode> getNotReady(LocalityBinding lb) {
+    return notreadymap.get(lb);
+  }
+
+  public HashSet<FlatNode> getCannotDelay(LocalityBinding lb) {
+    return cannotdelaymap.get(lb);
+  }
+
+  public HashSet<FlatNode> getOther(LocalityBinding lb) {
+    return othermap.get(lb);
+  }
+
+  //This method computes which nodes from the first part of the
+  //transaction must store their output for the second part
+  //Note that many nodes don't need to...
+
+  public Set<FlatNode> livecode(LocalityBinding lb) {
+    if (!othermap.containsKey(lb))
+      return null;
+    HashSet<FlatNode> delayedset=notreadymap.get(lb);
+    MethodDescriptor md=lb.getMethod();
+    FlatMethod fm=state.getMethodFlat(md);
+    Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>> map=new Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>>();
+
+    HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
+    toanalyze.add(fm);
+    
+    HashSet<FlatNode> livenodes=new HashSet<FlatNode>();
+
+    while(!toanalyze.isEmpty()) {
+      FlatNode fn=toanalyze.iterator().next();
+      toanalyze.remove(fn);
+      Hashtable<TempDescriptor, HashSet<FlatNode>> tmptofn=new Hashtable<TempDescriptor, HashSet<FlatNode>>();
+      
+      //Do merge on incoming edges
+      for(int i=0;i<fn.numPrev();i++) {
+	FlatNode fnprev=fn.getPrev(i);
+	Hashtable<TempDescriptor, HashSet<FlatNode>> prevmap=map.get(fnprev);
+
+	for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
+	  TempDescriptor tmp=tmpit.next();
+	  if (!tmptofn.containsKey(tmp))
+	    tmptofn.put(tmp, new HashSet<FlatNode>());
+	  tmptofn.get(tmp).addAll(prevmap.get(tmp));
+	}
+      }
+
+      if (delayedset.contains(fn)) {
+	//Check our readset
+	TempDescriptor readset[]=fn.readsTemps();
+	for(int i=0;i<readset.length;i++) {
+	  TempDescriptor tmp=readset[i];
+	  if (tmptofn.containsKey(tmp))
+	    livenodes.addAll(tmptofn.get(tmp)); // add live nodes
+	}
+
+	//Do kills
+	TempDescriptor writeset[]=fn.writesTemps();
+	for(int i=0;i<writeset.length;i++) {
+	  TempDescriptor tmp=writeset[i];
+	  tmptofn.remove(tmp);
+	}
+      } else {
+	//We write -- our reads are done
+	TempDescriptor writeset[]=fn.writesTemps();
+	for(int i=0;i<writeset.length;i++) {
+	  TempDescriptor tmp=writeset[i];
+	  HashSet<FlatNode> set=new HashSet<FlatNode>();
+	  set.add(fn);
+	  tmptofn.put(tmp,set);
+	}
+	if (fn.numNext()>1) {
+	  //We have a conditional branch...need to handle this carefully
+	  Set<FlatNode> set0=getNext(fn, 0, delayedset);
+	  Set<FlatNode> set1=getNext(fn, 1, delayedset);
+	  if (!set0.equals(set1)||set0.size()>1) {
+	    //This branch is important--need to remember how it goes
+	    livenodes.add(fn);
+	  }
+	}
+      }
+      if (!map.containsKey(fn)||!map.get(fn).equals(tmptofn)) {
+	map.put(fn, tmptofn);
+	//enqueue next ndoes
+	for(int i=0;i<fn.numNext();i++)
+	  toanalyze.add(fn.getNext(i));
+      }
+    }
+    return livenodes;
+  }
+  
+  //Returns null if more than one possible next
+
+  public static Set<FlatNode> getNext(FlatNode fn, int i, HashSet<FlatNode> delayset) {
+    FlatNode fnnext=fn.getNext(i);
+    HashSet<FlatNode> reachable=new HashSet<FlatNode>();    
+
+    if (delayset.contains(fnnext)) {
+      reachable.add(fnnext);
+      return reachable;
+    }
+    Stack<FlatNode> nodes=new Stack<FlatNode>();
+    HashSet<FlatNode> visited=new HashSet<FlatNode>();
+    nodes.push(fnnext);
+
+    while(!nodes.isEmpty()) {
+      FlatNode fn2=nodes.pop();
+      if (visited.contains(fn2)) 
+	continue;
+      visited.add(fn2);
+      for (int j=0;j<fn2.numNext();j++) {
+	FlatNode fn2next=fn2.getNext(j);
+	if (delayset.contains(fn2next)) {
+	  reachable.add(fn2next);
+	} else
+	  nodes.push(fn2next);
+      }
+    }
+    return reachable;
+  }
+
   public void analyzeMethod(LocalityBinding lb) {
     MethodDescriptor md=lb.getMethod();
     FlatMethod fm=state.getMethodFlat(md);
@@ -264,22 +392,9 @@ public class DelayComputation {
     if (!atomicset.isEmpty()) {
       atomicset.removeAll(notreadyset);
       atomicset.removeAll(cannotdelay);
-      System.out.println("-----------------------------------------------------");
-      System.out.println(md);
-      Hashtable map=new Hashtable();
-
-      for(Iterator it=atomicset.iterator();it.hasNext();) {
-	map.put(it.next(),"A");
-      }
-
-      for(Iterator it=notreadyset.iterator();it.hasNext();) {
-	map.put(it.next(),"2");
-      }
-
-      for(Iterator it=cannotdelay.iterator();it.hasNext();) {
-	map.put(it.next(),"1");
-      }
-      System.out.println(fm.printMethod(map));
+      notreadymap.put(lb, notreadyset);
+      cannotdelaymap.put(lb, cannotdelay);
+      othermap.put(lb, atomicset);
     }
 
     //We now have:
diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java
index 2b165153..b1503beb 100644
--- a/Robust/src/IR/Flat/BuildCode.java
+++ b/Robust/src/IR/Flat/BuildCode.java
@@ -108,7 +108,7 @@ public class BuildCode {
       this.dc=new DiscoverConflicts(locality, st, typeanalysis);
       dc.doAnalysis();
     }
-    if (state.SINGLETM&&state.DELAYCOMP) {
+    if (state.DELAYCOMP) {
       //TypeAnalysis typeanalysis=new TypeAnalysis(locality, st, typeutil,callgraph);
       TypeAnalysis typeanalysis=new TypeAnalysis(locality, st, typeutil,callgraph);
       GlobalFieldType gft=new GlobalFieldType(callgraph, st, typeutil.getMain());
-- 
2.34.1