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