public void doAnalysis(FlatMethod fm) {
Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr=new Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>>();
-
HashSet toprocess=new HashSet();
HashSet discovered=new HashSet();
toprocess.add(fm);
}
switch(fn.kind()) {
+ case FKind.FlatAtomicEnterNode:
+ {
+ killexpressions(tab, null, null, true);
+ }
case FKind.FlatCall:
{
FlatCall fc=(FlatCall) fn;
MethodDescriptor md=fc.getMethod();
Set<FieldDescriptor> fields=gft.getFields(md);
Set<TypeDescriptor> arrays=gft.getArrays(md);
- killexpressions(tab, fields, arrays);
+ killexpressions(tab, fields, arrays, gft.containsAtomic(md));
break;
}
case FKind.FlatOpNode:
{
FlatOpNode fon=(FlatOpNode) fn;
- Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
+ Expression e=new Expression(fon.getLeft(), fon.getRight(), fon.getOp());
tab.put(e, fon.getDest());
break;
}
FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
Set<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
fields.add(fsfn.getField());
- killexpressions(tab, fields, null);
+ killexpressions(tab, fields, null, false);
Expression e=new Expression(fsfn.getDst(), fsfn.getField());
tab.put(e, fsfn.getSrc());
break;
}
}
}
+
doOptimize(fm, availexpr);
}
public void doOptimize(FlatMethod fm, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
- for(Iterator<FlatNode> it=fm.getNodeSet().iterator();it.hasNext();) {
- FlatNode fn=it.next();
- Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
- switch(fn.kind()) {
- case FKind.FlatOpNode:
- {
- FlatOpNode fon=(FlatOpNode) fn;
- Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
- if (tab.containsKey(e)) {
- TempDescriptor t=tab.get(e);
- FlatOpNode newfon=new FlatOpNode(fon.getDest(),t,null,new Operation(Operation.ASSIGN));
- fon.replace(newfon);
- }
- break;
- }
- case FKind.FlatFieldNode:
- {
- FlatFieldNode ffn=(FlatFieldNode)fn;
- Expression e=new Expression(ffn.getSrc(), ffn.getField());
- if (tab.containsKey(e)) {
- TempDescriptor t=tab.get(e);
- FlatOpNode newfon=new FlatOpNode(ffn.getDst(),t,null,new Operation(Operation.ASSIGN));
- ffn.replace(newfon);
- }
- break;
- }
- case FKind.FlatElementNode:
- {
- FlatElementNode fen=(FlatElementNode)fn;
- Expression e=new Expression(fen.getSrc(),fen.getIndex());
- if (tab.containsKey(e)) {
- TempDescriptor t=tab.get(e);
- FlatOpNode newfon=new FlatOpNode(fen.getDst(),t,null,new Operation(Operation.ASSIGN));
- fen.replace(newfon);
- }
- break;
- }
- default:
+ Hashtable<FlatNode, FlatNode> replacetable=new Hashtable<FlatNode, FlatNode>();
+ for(Iterator<FlatNode> it=fm.getNodeSet().iterator();it.hasNext();) {
+ FlatNode fn=it.next();
+ Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
+ switch(fn.kind()) {
+ case FKind.FlatOpNode:
+ {
+ FlatOpNode fon=(FlatOpNode) fn;
+ Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
+ if (tab.containsKey(e)) {
+ TempDescriptor t=tab.get(e);
+ FlatNode newfon=new FlatOpNode(fon.getDest(),t,null,new Operation(Operation.ASSIGN));
+ replacetable.put(fon,newfon);
}
+ break;
+ }
+ case FKind.FlatFieldNode:
+ {
+ FlatFieldNode ffn=(FlatFieldNode)fn;
+ Expression e=new Expression(ffn.getSrc(), ffn.getField());
+ if (tab.containsKey(e)) {
+ TempDescriptor t=tab.get(e);
+ FlatNode newfon=new FlatOpNode(ffn.getDst(),t,null,new Operation(Operation.ASSIGN));
+ replacetable.put(ffn,newfon);
+ }
+ break;
+ }
+ case FKind.FlatElementNode:
+ {
+ FlatElementNode fen=(FlatElementNode)fn;
+ Expression e=new Expression(fen.getSrc(),fen.getIndex());
+ if (tab.containsKey(e)) {
+ TempDescriptor t=tab.get(e);
+ FlatNode newfon=new FlatOpNode(fen.getDst(),t,null,new Operation(Operation.ASSIGN));
+ replacetable.put(fen,newfon);
+ }
+ break;
+ }
+ default:
}
+ }
+ for(Iterator<FlatNode> it=replacetable.keySet().iterator();it.hasNext();) {
+ FlatNode fn=it.next();
+ FlatNode newfn=replacetable.get(fn);
+ fn.replace(newfn);
+ }
}
-
+
public Hashtable<Expression, TempDescriptor> computeIntersection(FlatNode fn, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
Hashtable<Expression, TempDescriptor> tab=new Hashtable<Expression, TempDescriptor>();
boolean first=true;
for(int i=0;i<fn.numPrev();i++) {
FlatNode prev=fn.getPrev(i);
if (first) {
- if (availexpr.containsKey(prev))
+ if (availexpr.containsKey(prev)) {
tab.putAll(availexpr.get(prev));
- first=false;
+ first=false;
+ }
} else {
if (availexpr.containsKey(prev)) {
Hashtable<Expression, TempDescriptor> table=availexpr.get(prev);
return tab;
}
- public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays) {
+ public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays, boolean killall) {
for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
Map.Entry m=(Map.Entry)it.next();
Expression e=(Expression)m.getKey();
- if (e.f!=null&&fields!=null&&fields.contains(e.f))
+ if (killall&&(e.f!=null||e.a!=null))
+ it.remove();
+ else if (e.f!=null&&fields!=null&&fields.contains(e.f))
it.remove();
else if ((e.a!=null)&&(arrays!=null)) {
for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
//get rid of useless nodes
for(Iterator<FlatNode> it=fm.getNodeSet().iterator();it.hasNext();) {
FlatNode fn=it.next();
- if (!useful.contains(fn)) {
+ if (!useful.contains(fn)||isuseless(fn)) {
//We have a useless node
FlatNode fnnext=fn.getNext(0);
-
for(int i=0;i<fn.numPrev();i++) {
FlatNode nprev=fn.getPrev(i);
}
}
}
+ public boolean isuseless(FlatNode fn) {
+ if (fn.kind()==FKind.FlatOpNode) {
+ FlatOpNode fon=(FlatOpNode)fn;
+ if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getLeft()==fon.getDest())
+ return true;
+ }
+ return false;
+ }
+
}
\ No newline at end of file
MethodDescriptor root;
Hashtable<MethodDescriptor, Set<FieldDescriptor>> fields;
Hashtable<MethodDescriptor, Set<TypeDescriptor>> arrays;
+ HashSet<MethodDescriptor> containsAtomic;
public GlobalFieldType(CallGraph cg, State st, MethodDescriptor root) {
this.cg=cg;
this.root=root;
this.fields=new Hashtable<MethodDescriptor, Set<FieldDescriptor>>();
this.arrays=new Hashtable<MethodDescriptor, Set<TypeDescriptor>>();
+ this.containsAtomic=new HashSet<MethodDescriptor>();
doAnalysis();
}
private void doAnalysis() {
changed=true;
if (arrays.get(md).addAll(arrays.get(md2)))
changed=true;
+ if (containsAtomic.contains(md2)) {
+ if (containsAtomic.add(md))
+ changed=true;
+ }
}
}
}
}
+ public boolean containsAtomic(MethodDescriptor md) {
+ return containsAtomic.contains(md);
+ }
+
public Set<FieldDescriptor> getFields(MethodDescriptor md) {
return fields.get(md);
}
} else if (fn.kind()==FKind.FlatSetFieldNode) {
FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
fields.get(md).add(fsfn.getField());
+ } else if (fn.kind()==FKind.FlatAtomicEnterNode) {
+ containsAtomic.add(md);
}
}
}
--- /dev/null
+package Analysis.Loops;
+import IR.Flat.*;
+import Analysis.Locality.*;
+import IR.Operation;
+import IR.State;
+import IR.MethodDescriptor;
+import java.util.HashSet;
+import java.util.Hashtable;
+import java.util.Iterator;
+
+public class WriteBarrier {
+ /* This computes whether we actually need a write barrier. */
+ LocalityAnalysis la;
+ State state;
+ public WriteBarrier(LocalityAnalysis la, State state) {
+ this.la=la;
+ this.state=state;
+ }
+
+ public boolean needBarrier(FlatNode fn) {
+ HashSet<TempDescriptor> nb=computeIntersection(fn);
+ switch(fn.kind()) {
+ case FKind.FlatSetElementNode:
+ {
+ FlatSetElementNode fsen=(FlatSetElementNode)fn;
+ return !nb.contains(fsen.getDst());
+ }
+ case FKind.FlatSetFieldNode:
+ {
+ FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
+ return !nb.contains(fsfn.getDst());
+ }
+ default:
+ return true;
+ }
+ }
+
+ Hashtable<FlatNode,HashSet<TempDescriptor>> needbarrier;
+
+ public void analyze(LocalityBinding lb) {
+ MethodDescriptor md=lb.getMethod();
+ FlatMethod fm=state.getMethodFlat(md);
+ HashSet useful=new HashSet();
+ HashSet toprocess=new HashSet();
+ HashSet discovered=new HashSet();
+ needbarrier=new Hashtable<FlatNode,HashSet<TempDescriptor>>();
+ toprocess.add(fm);
+ discovered.add(fm);
+ Hashtable<FlatNode, Integer> atomic=la.getAtomic(lb);
+
+ while(!toprocess.isEmpty()) {
+ FlatNode fn=(FlatNode)toprocess.iterator().next();
+ toprocess.remove(fn);
+ for(int i=0;i<fn.numNext();i++) {
+ FlatNode nnext=fn.getNext(i);
+ if (!discovered.contains(nnext)) {
+ toprocess.add(nnext);
+ discovered.add(nnext);
+ }
+ }
+ HashSet<TempDescriptor> nb=computeIntersection(fn);
+ TempDescriptor[] writes=fn.writesTemps();
+ for(int i=0;i<writes.length;i++) {
+ nb.remove(writes[i]);
+ }
+ switch(fn.kind()) {
+ case FKind.FlatSetElementNode:
+ {
+ FlatSetElementNode fsen=(FlatSetElementNode)fn;
+ nb.add(fsen.getDst());
+ break;
+ }
+ case FKind.FlatSetFieldNode:
+ {
+ FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
+ nb.add(fsfn.getDst());
+ break;
+ }
+ case FKind.FlatOpNode:
+ {
+ FlatOpNode fon=(FlatOpNode)fn;
+ if (fon.getOp().getOp()==Operation.ASSIGN) {
+ if (nb.contains(fon.getLeft())) {
+ nb.add(fon.getDest());
+ }
+ }
+ break;
+ }
+ case FKind.FlatNew:
+ {
+ FlatNew fnew=(FlatNew)fn;
+ nb.add(fnew.getDst());
+ break;
+ }
+ default:
+ //If we enter a transaction toss everything
+ if (atomic.get(fn).intValue()>0&&
+ atomic.get(fn.getPrev(0)).intValue()==0) {
+ nb=new HashSet<TempDescriptor>();
+ }
+ }
+ if (!needbarrier.containsKey(fn)||
+ !needbarrier.get(fn).equals(nb)) {
+ for(int i=0;i<fn.numNext();i++) {
+ FlatNode nnext=fn.getNext(i);
+ toprocess.add(nnext);
+ }
+ needbarrier.put(fn,nb);
+ }
+ }
+ }
+ HashSet<TempDescriptor> computeIntersection(FlatNode fn) {
+ HashSet<TempDescriptor> tab=new HashSet<TempDescriptor>();
+ boolean first=true;
+ for(int i=0;i<fn.numPrev();i++) {
+ FlatNode fprev=fn.getPrev(i);
+ HashSet<TempDescriptor> hs=needbarrier.get(fprev);
+ if (hs!=null) {
+ if (first) {
+ tab.addAll(hs);
+ first=false;
+ } else {
+ //Intersect sets
+ for(Iterator<TempDescriptor> it=tab.iterator();it.hasNext();) {
+ TempDescriptor t=it.next();
+ if (!hs.contains(t))
+ it.remove();
+ }
+ }
+ }
+ }
+ return tab;
+ }
+}
\ No newline at end of file
Group g=getGroup(table,e);
TempDescriptor td=getTemp(g);
if (td!=null) {
- FlatOpNode nfon=new FlatOpNode(fon.getDest(),td,null,new Operation(Operation.ASSIGN));
+ FlatNode nfon=new FlatOpNode(fon.getDest(),td,null,new Operation(Operation.ASSIGN));
fn.replace(nfon);
}
g.set.add(dst);
dstf.set.add(src);
HashSet<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
fields.add(fsfn.getField());
- kill(table, fields, null);
+ kill(table, fields, null, false);
table.put(src, dstf);
break;
}
dstf.set.add(src);
HashSet<TypeDescriptor> arrays=new HashSet<TypeDescriptor>();
arrays.add(fsen.getDst().getType());
- kill(table, null, arrays);
+ kill(table, null, arrays, false);
table.put(src, dstf);
break;
}
MethodDescriptor md=fc.getMethod();
Set<FieldDescriptor> fields=gft.getFields(md);
Set<TypeDescriptor> arrays=gft.getArrays(md);
- kill(table, fields, arrays);
+ kill(table, fields, arrays, gft.containsAtomic(md));
}
default: {
TempDescriptor[] writes=fn.writesTemps();
} while(fn.numPrev()==1);
}
}
- public void kill(Hashtable<LocalExpression, Group> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays) {
+ public void kill(Hashtable<LocalExpression, Group> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays, boolean isAtomic) {
Set<LocalExpression> eset=tab.keySet();
for(Iterator<LocalExpression> it=eset.iterator();it.hasNext();) {
LocalExpression e=it.next();
- if (e.td!=null) {
+ if (isAtomic&&(e.td!=null||e.f!=null)) {
+ Group g=tab.get(e);
+ g.set.remove(e);
+ it.remove();
+ } else if (e.td!=null) {
//have array
TypeDescriptor artd=e.td;
for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
projects / IRC.git / commitdiff