From 0e4983893a39906c5e884df57a77afc73da0c4a3 Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Sat, 11 Apr 2009 01:31:12 +0000
Subject: [PATCH] changes

---
 .../Analysis/Locality/DiscoverConflicts.java  | 376 ++++++++++++++++++
 .../Analysis/Locality/LocalityAnalysis.java   |   4 +-
 2 files changed, 378 insertions(+), 2 deletions(-)
 create mode 100644 Robust/src/Analysis/Locality/DiscoverConflicts.java

diff --git a/Robust/src/Analysis/Locality/DiscoverConflicts.java b/Robust/src/Analysis/Locality/DiscoverConflicts.java
new file mode 100644
index 00000000..36da9d6b
--- /dev/null
+++ b/Robust/src/Analysis/Locality/DiscoverConflicts.java
@@ -0,0 +1,376 @@
+package Analysis.Locality;
+
+import IR.Flat.*;
+import java.util.Set;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Hashtable;
+import IR.State;
+import IR.TypeDescriptor;
+import IR.MethodDescriptor;
+import IR.FieldDescriptor;
+
+public DiscoverConflicts {
+    Set<FieldDescriptor> fields;
+    Set<TypeDescriptor> arrays;
+    LocalityAnalysis locality;
+    State state;
+    Hashtable<Locality, Set<FlatNode>> needsTR;
+
+    public DiscoverConflicts(LocalityAnalysis locality, State state) {
+	this.locality=locality;
+	this.fields=new HashSet<FieldDescriptor>();
+	this.arrays=new HashSet<TypeDescriptor>();
+	this.needsTR=new Hashtable<Locality, Set<FlatNode>>();
+	this.state=state;
+	transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
+	srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
+    }
+    
+    public void doAnalysis() {
+	//Compute fields and arrays for all transactions
+	Set<LocalityBinding> localityset=locality.getLocalityBindings();
+	for(Iterator<LocalityBinding> lb=localityset.iteratory();lb.hasNext();) {
+	    computeModified(lb.next());
+	}
+	expandTypes();
+	//Compute set of nodes that need transread
+	Set<LocalityBinding> localityset=locality.getLocalityBindings();
+	for(Iterator<LocalityBinding> lb=localityset.iteratory();lb.hasNext();) {
+	    analyzeLocality(lb.next());
+	}
+    }
+    public void expandTypes() {
+	FIX ARRAY...compute super/sub sets of each so we can do simple membership test
+    }
+
+    Hashtable<TempDescriptor, Set<FlatNode>> doMerge(FlatNode fn, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> tmptofnset) {
+	Hashtable<TempDescriptor, Set<FlatNode>> table=new Hashtable<TempDescriptor, Set<FlatNode>>();
+	for(int i=0;i<fn.numPrev();i++) {
+	    FlatNode fprev=fn.getPrev(i);
+	    Hashtable<TempDescriptor, Set<FlatNode>> tabset=tmptofnset.get(fprev);
+	    if (tabset!=null) {
+		for(Iterator<TempDescriptor> tmpit=tabset.keySet().iterator();tmpit.hasNext();) {
+		    TempDescriptor td=tmpit.next();
+		    Set<FlatNode> fnset=tabset.get(td);
+		    if (!table.containsKey(td))
+			table.put(td, new HashSet<FlatNode>());
+		    table.get(td).addAll(fnset);
+		}
+	    }
+	}
+	return table;
+    }
+
+    Hashtable<LocalityBinding, Set<TempFlatPair>> transreadmap;
+    Hashtable<LocalityBinding, Set<FlatNode>> srcmap;
+
+
+    public void analyzeLocality(LocalityBinding lb) {
+	Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
+	HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fnmap);
+	HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
+	transreadmap.put(lb, tfset);
+	srcmap.put(lb,srctrans);
+
+	for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
+	    FlatNode fn=fnit.next();
+	    Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
+	    if (atomictable.get(fn).intValue()>0) {
+		Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
+		switch(fn.kind()) {
+		case FKind.FlatSetFieldNode: { 
+		    //definitely need to translate these
+		    FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
+		    Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
+		    for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
+			TempFlatPair tfp=tfpit.nexT();
+			if (tfset.contains(tfp)) {
+			    srctrans.add(fsfn);
+			    break;
+			}
+		    }
+		    break;
+		}
+		case FKind.FlatSetElementNode: { 
+		    //definitely need to translate these
+		    FlatSetElementNode fsen=(FlatSetElementNode)fn;
+		    Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
+		    for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
+			TempFlatPair tfp=tfpit.nexT();
+			if (tfset.contains(tfp)) {
+			    srctrans.add(fsfn);
+			    break;
+			}
+		    }
+		    break;
+		}
+		default:
+		}
+	    }
+	}
+    }
+
+    HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap) {
+	HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
+
+	for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
+	    FlatNode fn=fnit.next();
+	    Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
+	    if (atomictable.get(fn).intValue()>0) {
+		Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
+		switch(fn.kind()) {
+		case FKind.FlatElementNode: {
+		    FlatElementNode fen=(FlatElementNode)fn;
+		    if (arrays.contains(fen.getField())) {
+			//this could cause conflict...figure out conflict set
+			Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
+			tfset.addAll(tfpset);
+		    }
+		    break;
+		}
+		case FKind.FlatFieldNode: { 
+		    FlatFieldNode ffn=(FlatFieldNode)fn;
+		    if (fields.contains(ffn.getField())) {
+			//this could cause conflict...figure out conflict set
+			Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
+			tfset.addAll(tfpset);
+		    }
+		    break;
+		}
+		case FKind.FlatSetFieldNode: { 
+		    //definitely need to translate these
+		    FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
+		    Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
+		    tfset.addAll(tfpset);
+		    break;
+		}
+		case FKind.FlatSetElementNode: { 
+		    //definitely need to translate these
+		    FlatSetElementNode fsen=(FlatSetElementNode)fn;
+		    Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
+		    tfset.addAll(tfpset);
+		    break;
+		}
+		case FKind.FlatCall: //assume pessimistically that calls do bad things
+		case FKind.FlatReturn: {
+		    TempDescriptor []readarray=fn.readsTemps();
+		    for(int i=0;i<readarray.length;i++) {
+			TempDescriptor rtmp=readarray[i];
+			Set<TempFlatPair> tfpset=tmap.get(rtmp);
+			tfset.addAll(tfpset);
+		    }
+		    break;
+		default:
+		    //do nothing
+		}
+		}
+	    }
+	}	
+	return tfset;
+    }
+
+    Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
+	Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor>, Set<TempFlatPair>>();
+	HashSet<FlatNode> discovered=new HashSet<FlatNode>();
+	HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
+	MethodDescriptor md=lb.getMethod();
+	FlatMethod fm=state.getMethodFlat(md);
+	Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
+	Hashtable<FlatNode, Set<TempDescriptor>> livetemps=locality.computeLiveTemps(fm);
+	tovisit.add(fm);
+	discovered.add(fm);
+	
+	while(!tovisit.isEmpty()) {
+	    FlatNode fn=tovisit.iterator().next();
+	    tovisit.remove(fn);
+	    for(int i=0;i<fn.numNext();i++) {
+		FlatNode fnext=fn.getNext(i);
+		if (!discovered.contains(fnext)) {
+		    discovered.add(fnext);
+		    tovisit.add(fnext);
+		}
+	    }
+	    Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
+	    if (atomictable.get(fn).intValue()!=0) {
+		if (fn.numPrev()>0&&atomictable.get(fn.getPrev(0))) {
+		    //flatatomic enter node...  see what we really need to transread
+		    Set<TempDescriptor> liveset=livetemps.get(fn);
+		    ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
+		    for(Iterator<TempDescriptor> tmpit=liveset.iterator();tmpit.hasNext();) {
+			TempDescriptor tmp=tmpit.next();
+			if (tmp.getType().isPtr()) {
+			    HashSet<TempFlatPair> fnset=new HashSet<TempFlatPair>();
+			    fnset.add(new TempFlatPair(tmp, fn));
+			    ttofn.put(tmp, fnset);
+			}
+		    }
+		} else {
+		    ttofn=doMerge(fn, tmptofnset);
+		    switch(fn.kind()) {
+		    case FKind.FlatFieldNode:
+		    case FKind.FlatElementNode: {
+			TempDescriptor[] writes=fn.writesTemps();
+			for(int i=0;i<writes.length;i++) {
+			    TempDescriptor wtmp=writes[i];
+			    HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
+			    set.add(new TempFlatPair(wtmp, fn));
+			    mtable.put(wtmp, set);
+			}
+			break;
+		    }
+		    case FKind.FlatOpNode: {
+			FlatOpNode fon=(FlatOpNode)fn;
+			if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
+			    mtable.put(fon.getDest(), new HashSet<TempFlatPair>(mtable.get(fon.getLeft())));
+			    break;
+			}
+		    }
+		    default:
+			//Do kill computation
+			TempDescriptor[] writes=fn.writesTemps();
+			for(int i=0;i<writes.length;i++) {
+			    TempDescriptor wtmp=writes[i];
+			    mtable.remove(writes[i]);
+			}
+		    }
+		}
+		if (ttofn!=null) {
+		    if (!tmptofnset.containsKey(fn)||
+			!tmptofnset.get(fn).equals(ttofn)) {
+			//enqueue nodes to process
+			tmptofnset.put(fn, ttofn);
+			for(int i=0;i<fn.numNext();i++) {
+			    FlatNode fnext=fn.getNext(i);
+			    tovisit.add(fnext);
+			}
+		    }
+		}
+	    }
+	}	
+	return tmptofnset;
+    }
+
+    public void computeModified(LocalityBinding lb) {
+	Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
+	for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
+	    FlatNode fn=fnit.next();
+	    Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
+	    if (atomictable.get(fn).intValue()>0) {
+		switch (fn.kind()) {
+		case FKind.FlatSetFieldNode:
+		    FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
+		    fields.add(fsfn.getField());
+		    break;
+		case FKind.FlatSetElementNode:
+		    FlatSetElementNode fsfn=(FlatSetElementNode) fn;
+		    arrays.add(fsen.getDst().getType());
+		    break;
+		default:
+		}
+	    }
+	}
+    }
+    
+    Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
+	Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
+	HashSet<FlatNode> discovered=new HashSet<FlatNode>();
+	HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
+	MethodDescriptor md=lb.getMethod();
+	FlatMethod fm=state.getMethodFlat(md);
+	Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
+	Hashtable<FlatNode, Set<TempDescriptor>> livetemps=locality.computeLiveTemps(fm);
+	tovisit.add(fm);
+	discovered.add(fm);
+	
+	while(!tovisit.isEmpty()) {
+	    FlatNode fn=tovisit.iterator().next();
+	    tovisit.remove(fn);
+	    for(int i=0;i<fn.numNext();i++) {
+		FlatNode fnext=fn.getNext(i);
+		if (!discovered.contains(fnext)) {
+		    discovered.add(fnext);
+		    tovisit.add(fnext);
+		}
+	    }
+	    HashSet<TempDescriptor> oldtemps=null;
+	    if (atomictable.get(fn).intValue()!=0) {
+		if (fn.numPrev()>0&&atomictable.get(fn.getPrev(0))) {
+		    //Everything live is old
+		    Set<TempDescriptor> lives=livetemps.get(fn);
+		    oldtemps=new HashSet<TempDescriptor>();
+		    
+		    for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
+			TempDescriptor tmp=it.next();
+			if (tmp.getType().isPtr()) {
+			    oldtemps.add(tmp);
+			}
+		    } else {
+			oldtemps=new HashSet<TempDescriptor>();
+			//Compute union of old temporaries
+			for(int i=0;i<fn.numPrev();i++) {
+			    HashSet<TempDescriptor> pset=fnotooldtmp.get(fn.getPrev(i));
+			    if (pset!=null)
+				oldtemps.addAll(pset);
+			}
+			
+			switch (fn.kind()) {
+			case FKind.FlatNew:
+			    oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
+			    break;
+			case FKind.FlatOpNode:
+			    {
+				FlatOpNode fon=(FlatOpNode)fn;
+				if (fon.getOp().getOp()==Operation.ASSIGN&&fn.getDest().getType().isPtr()) {
+				    if (oldtemps.contains(fn.getLeft()))
+					oldtemps.add(fn.getDest());
+				    else
+					oldtemps.remove(fn.getDest());
+				    break;
+				}
+			    }
+			default:
+			    {
+				TempDescriptor[] writes=fn.writesTemps();
+				for(int i=0;i<writes.length;i++) {
+				    TempDescriptor wtemp=writes[i];
+				    if (wtemp.getType().isPtr())
+					oldtemps.add(wtemp);
+				}
+			    }
+			}
+		    }
+		}
+	    }
+	    if (oldtemps!=null) {
+		if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
+		    fntooldtmp.put(fn, oldtemps);
+		    //propagate changes
+		    for(int i=0;i<fn.numNext();i++) {
+			FlatNode fnext=fn.getNext(i);
+			tovisit.add(fnext);
+		    }
+		}
+	    }
+	}
+	return fntooldtmp;
+    }
+}
+
+class TempFlatPair {
+    FlatNode f;
+    TempDescriptor t;
+    TempFlatPair(TempDescriptor t, FlatNode f) {
+	this.t=t;
+	this.f=f;
+    }
+
+    public int hashCode() {
+	return f.hashCode()^t.hashCode();
+    }
+    public boolean equals(Object o) {
+	TempFlatPair tf=(TempFlatPair)o;
+	return t.equals(tf.t)&&f.equals(tf.f);
+    }
+}
diff --git a/Robust/src/Analysis/Locality/LocalityAnalysis.java b/Robust/src/Analysis/Locality/LocalityAnalysis.java
index 889116c4..7c2fd640 100644
--- a/Robust/src/Analysis/Locality/LocalityAnalysis.java
+++ b/Robust/src/Analysis/Locality/LocalityAnalysis.java
@@ -844,8 +844,8 @@ public class LocalityAnalysis {
     int atomic=atomictable.get(fen).intValue();
     atomictable.put(fen, new Integer(atomic-1));
   }
-
-  private Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
+    
+  Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
 
     Set<FlatNode> toprocess=fm.getNodeSet();
-- 
2.34.1