DiscoverConflicts dcopts;
Hashtable<LocalityBinding, HashSet<FlatNode>> notreadymap;
Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap;
+ Hashtable<LocalityBinding, HashSet<FlatNode>> derefmap;
Hashtable<LocalityBinding, HashSet<FlatNode>> othermap;
public DelayComputation(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
this.gft=gft;
this.notreadymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
this.cannotdelaymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
+ if (state.STMARRAY)
+ this.derefmap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
this.othermap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
}
return cannotdelaymap;
}
+
+ public HashSet<FlatNode> getDeref(LocalityBinding lb) {
+ return derefmap.get(lb);
+ }
+
public void doAnalysis() {
+ //first dcopts...use to figure out what we need to lock
+ dcopts=new DiscoverConflicts(locality, state, typeanalysis, null);
+ dcopts.doAnalysis();
+
+ //compute cannotdelaymap
Set<LocalityBinding> localityset=locality.getLocalityBindings();
for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
analyzeMethod(lbit.next());
FlatMethod fm=state.getMethodFlat(md);
HashSet<FlatNode> delayedset=notreadymap.get(lb);
+ HashSet<FlatNode> derefset=derefmap.get(lb);
HashSet<FlatNode> otherset=othermap.get(lb);
HashSet<FlatNode> cannotdelayset=cannotdelaymap.get(lb);
Hashtable<FlatNode,Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
}
if (delayedset.contains(fn)) {
- //If the node is in the second set, 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
- unionset.addAll(tmptofn.get(tmp));
+ if(state.STMARRAY&&derefset.contains(fn)) {
+ //FlatElementNodes don't read anything...
+ if (fn.kind()==FKind.FlatSetElementNode) {
+ //check only the source read tmp
+ TempDescriptor tmp=((FlatSetElementNode)fn).getSrc();
+ if (tmptofn.containsKey(tmp)) {
+ livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
+ unionset.addAll(tmptofn.get(tmp));
+ }
+ }
+ } else {
+ //If the node is in the second set, 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
+ unionset.addAll(tmptofn.get(tmp));
+ }
}
}
-
//Do kills
TempDescriptor writeset[]=fn.writesTemps();
for(int i=0;i<writeset.length;i++) {
return reachable;
}
+ //Computes cannotdelayset---flatnodes that must be evaluated in the
+ //speculative component.
+
public void analyzeMethod(LocalityBinding lb) {
MethodDescriptor md=lb.getMethod();
FlatMethod fm=state.getMethodFlat(md);
HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
+ HashSet<FlatNode> derefset=new HashSet<FlatNode>();
Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
if (lb.isAtomic()) {
//We are in a transaction already...
return;
}
+ Hashtable<FlatNode, Set<TempDescriptor>> oldtempmap=dcopts.computeOldTemps(lb);
+
HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
toanalyze.addAll(fm.getNodeSet());
Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
+ Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
//Effect of adding something to nodelay set is to move it up past everything in delay set
//Have to make sure we can do this commute
//Delay branches if possible
if (fn.kind()==FKind.FlatCondBranch) {
- Set<FlatNode> leftset=getNext(fn, 0, cannotdelay, lb, locality,true);
- Set<FlatNode> rightset=getNext(fn, 1, cannotdelay, lb, locality,true);
- if (leftset.size()>0&&rightset.size()>0&&
- !leftset.equals(rightset)||leftset.size()>1)
- isnodelay=true;
+ Set<FlatNode> branchset=revbranchmap.get(lb);
+ for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
+ FlatNode branchnode=brit.next();
+ if (cannotdelay.contains(branchnode)||(state.STMARRAY&&derefset.contains(branchnode))) {
+ isnodelay=true;
+ break;
+ }
+ }
}
//Check for field conflicts
Set<FlatCondBranch> fcbset=branchmap.get(fn);
for(Iterator<FlatCondBranch> fcbit=fcbset.iterator();fcbit.hasNext();) {
FlatCondBranch fcb=fcbit.next();
- cannotdelay.add(fcb);
- nodelaytempset.add(fcb.getTest());
+ //enqueue flatcondbranch node for reanalysis
+ if (cannotdelay.contains(fcb)) {
+ cannotdelay.add(fcb);
+ toanalyze.add(fcb);
+ }
}
}
/* Do we write to fields */
}
} else {
//Need to know which objects to lock on
+ Set<TempDescriptor> oldtemps=oldtempmap.get(fn);
switch(fn.kind()) {
- //TODO: Can improve by only locking if there is a field that requires a lock
case FKind.FlatSetFieldNode: {
FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
- nodelaytempset.add(fsfn.getDst());
+ if (oldtemps.contains(fsfn.getDst())) {
+ nodelaytempset.add(fsfn.getDst());
+ }
break;
}
case FKind.FlatSetElementNode: {
FlatSetElementNode fsen=(FlatSetElementNode)fn;
- nodelaytempset.add(fsen.getDst());
+ if (oldtemps.contains(fsen.getDst())) {
+ nodelaytempset.add(fsen.getDst());
+ //Word Array support requires index
+ if (state.STMARRAY) {
+ nodelaytempset.add(fsen.getIndex());
+ derefset.add(fsen);
+ }
+ }
break;
}
case FKind.FlatFieldNode: {
FlatFieldNode ffn=(FlatFieldNode)fn;
- nodelaytempset.add(ffn.getSrc());
+ if (oldtemps.contains(ffn.getSrc())&&
+ dcopts.getFields().contains(ffn.getField())) {
+ nodelaytempset.add(ffn.getSrc());
+ }
break;
}
case FKind.FlatElementNode: {
FlatElementNode fen=(FlatElementNode)fn;
- nodelaytempset.add(fen.getSrc());
+ if (oldtemps.contains(fen.getSrc())&&
+ dcopts.getArrays().contains(fen.getSrc().getType())) {
+ nodelaytempset.add(fen.getSrc());
+ //Word Array support requires index
+ if (state.STMARRAY) {
+ nodelaytempset.add(fen.getIndex());
+ derefset.add(fen);
+ }
+ }
break;
}
}
}//end of while loop
if (lb.getHasAtomic()) {
+ if (state.STMARRAY)
+ derefmap.put(lb, derefset);
cannotdelaymap.put(lb, cannotdelay);
}
} //end of method
/* See what fields and arrays transactions might modify. We only
* look at changes to old objects. */
+ //Bug fix: original version forget to check if object is new and
+ //could be optimized
+
public void computeModified(LocalityBinding lb) {
MethodDescriptor md=lb.getMethod();
FlatMethod fm=state.getMethodFlat(md);
FlatNode fn=fnit.next();
Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
if (atomictable.get(fn).intValue()>0) {
+ Set<TempDescriptor> oldtemp=oldtemps.get(fn);
switch (fn.kind()) {
case FKind.FlatSetFieldNode:
FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
- fields.add(fsfn.getField());
+ if (oldtemp.contains(fsfn.getDst()))
+ fields.add(fsfn.getField());
break;
case FKind.FlatSetElementNode:
FlatSetElementNode fsen=(FlatSetElementNode) fn;
- arrays.add(fsen.getDst().getType());
+ if (oldtemp.contains(fsen.getDst()))
+ arrays.add(fsen.getDst().getType());
break;
default:
}
generateOptionalArrays(outoptionalarrays, optionalheaders, state.getAnalysisResult(), state.getOptionalTaskDescriptors());
outoptionalarrays.close();
}
-
+
/* Output structure definitions for repair tool */
if (state.structfile!=null) {
buildRepairStructs(outrepairstructs);
outrepairstructs.close();
}
-
+
/* Close files */
outmethodheader.println("#endif");
outmethodheader.close();
outstructs.println("#endif");
outstructs.close();
}
-
+
/* This code just generates the main C method for java programs.
* The main C method packs up the arguments into a string array
Set<FlatNode> storeset=null;
HashSet<FlatNode> genset=null;
+ HashSet<FlatNode> refset=null;
Set<FlatNode> unionset=null;
if (state.DELAYCOMP&&!lb.isAtomic()&&lb.getHasAtomic()) {
storeset=delaycomp.livecode(lb);
genset=new HashSet<FlatNode>();
+ if (state.STMARRAY) {
+ refset=new HashSet<FlatNode>();
+ refset.addAll(delaycomp.getDeref(lb));
+ refset.removeAll(delaycomp.getCannotDelay(lb));
+ refset.removeAll(delaycomp.getOther(lb));
+ }
if (firstpass) {
genset.addAll(delaycomp.getCannotDelay(lb));
genset.addAll(delaycomp.getOther(lb));
} else {
genset.addAll(delaycomp.getNotReady(lb));
+ if (state.STMARRAY) {
+ genset.removeAll(refset);
+ }
}
unionset=new HashSet<FlatNode>();
unionset.addAll(storeset);
unionset.addAll(genset);
+ if (state.STMARRAY)
+ unionset.addAll(refset);
}
/* Do the actual code generation */
if (genset==null||genset.contains(current_node)||specialprimitive)
generateFlatNode(fm, lb, current_node, output);
+ if (state.STMARRAY&&refset.contains(current_node)) {
+ //need to acquire lock
+ handleArrayDeref(fm, lb, current_node, output, firstpass);
+ }
if (storeset!=null&&storeset.contains(current_node)&&!specialprimitive) {
TempDescriptor wrtmp=current_node.writesTemps()[0];
if (firstpass) {
//need to store value written by previous node
if (wrtmp.getType().isPtr()) {
//only lock the objects that may actually need locking
- if (recorddc.getNeedTrans(lb, current_node)) {
+ if (recorddc.getNeedTrans(lb, current_node)&&
+ (!state.STMARRAY||!wrtmp.getType().isArray()||
+ wrtmp.getType().getSymbol().equals(TypeUtil.ObjectClass))) {
output.println("STOREPTR("+generateTemp(fm, wrtmp,lb)+");/* "+current_node.nodeid+" */");
} else {
output.println("STOREPTRNOLOCK("+generateTemp(fm, wrtmp,lb)+");/* "+current_node.nodeid+" */");
}
}
+ protected void handleArrayDeref(FlatMethod fm, LocalityBinding lb, FlatNode fn, PrintWriter output, boolean firstpass) {
+ if (fn.kind()==FKind.FlatSetElementNode) {
+ FlatSetElementNode fsen=(FlatSetElementNode) fn;
+ String dst=generateTemp(fm, fsen.getDst(), lb);
+ String src=generateTemp(fm, fsen.getSrc(), lb);
+ String index=generateTemp(fm, fsen.getIndex(), lb);
+ if (firstpass) {
+ output.println("STOREARRAY("+dst+","+index+")");
+ } else {
+ TypeDescriptor elementtype=fsen.getDst().getType().dereference();
+ String type="";
+ if (elementtype.isArray()||elementtype.isClass())
+ type="void *";
+ else
+ type=elementtype.getSafeSymbol()+" ";
+ output.println("{");
+ output.println(" struct ___ArrayObject___ *array;");
+ output.println(" int index;");
+ output.println(" RESTOREARRAY(array,index);");
+ output.println(" (("+type+"*)((struct ___ArrayObject___*) (((char *)&array->___length___))+sizeof(int)))[index]="+fsen.getSrc()+";");
+ output.println("}");
+ }
+ } else if (fn.kind()==FKind.FlatElementNode) {
+ FlatElementNode fen=(FlatElementNode) fn;
+ String src=generateTemp(fm, fen.getSrc(), lb);
+ String index=generateTemp(fm, fen.getIndex(), lb);
+ if (firstpass) {
+ output.println("STOREARRAY("+src+","+index+");");
+ } else {
+ TypeDescriptor elementtype=fen.getDst().getType().dereference();
+ String dst=generateTemp(fm, fen.getDst(), lb);
+ String type="";
+ if (elementtype.isArray()||elementtype.isClass())
+ type="void *";
+ else
+ type=elementtype.getSafeSymbol()+" ";
+ output.println("{");
+ output.println(" struct ___ArrayObject___ *array;");
+ output.println(" int index;");
+ output.println(" RESTOREARRAY(array,index);");
+ output.println(" "+dst+"=(("+type+"*)((struct ___ArrayObject___*) (((char *)&array->___length___))+sizeof(int)))[index];");
+ output.println("}");
+ }
+ }
+ }
+
/** This method assigns labels to FlatNodes */
protected Hashtable<FlatNode, Integer> assignLabels(FlatNode first) {
return assignLabels(first, null);
ParseNode headern=pn.getChild("method_header");
ParseNode bodyn=pn.getChild("body");
MethodDescriptor md=parseMethodHeader(headern);
- BlockNode bn=parseBlock(bodyn);
- cn.addMethod(md);
- state.addTreeCode(md,bn);
+ try {
+ BlockNode bn=parseBlock(bodyn);
+ cn.addMethod(md);
+ state.addTreeCode(md,bn);
+ } catch (Exception e) {
+ System.out.println("Error with method:"+md.getSymbol());
+ e.printStackTrace();
+ throw new Error();
+ } catch (Error e) {
+ System.out.println("Error with method:"+md.getSymbol());
+ e.printStackTrace();
+ throw new Error();
+ }
}
private void parseConstructorDecl(ClassDescriptor cn, ParseNode pn) {
}
public static void loadClass(State state, BuildIR bir, String sourcefile) {
- ParseNode pn=readSourceFile(state, sourcefile);
- bir.buildtree(pn, null);
+ try {
+ ParseNode pn=readSourceFile(state, sourcefile);
+ bir.buildtree(pn, null);
+ } catch (Exception e) {
+ System.out.println("Error in sourcefile:"+sourcefile);
+ e.printStackTrace();
+ System.exit(-1);
+ } catch (Error e) {
+ System.out.println("Error in sourcefile:"+sourcefile);
+ e.printStackTrace();
+ System.exit(-1);
+ }
}
/** Reads in a source file and adds the parse tree to the state object. */
}
#endif
+#ifdef STMARRAY
+//Store objects and their pointers into hash
+void dc_t_chashInsertOnce(void * key, unsigned int indexkey, void *val) {
+ chashlistnode_t *ptr;
+
+ if (key==NULL)
+ return;
+
+ if(dc_c_numelements > (dc_c_threshold)) {
+ //Resize
+ unsigned int newsize = dc_c_size << 1;
+ dc_t_chashResize(newsize);
+ }
+
+ ptr = &dc_c_table[(((unsigned INTPTR)key)&dc_c_mask)>>4];
+
+ if(ptr->key==0) {
+ ptr->key=key;
+ ptr->val=val;
+ ptr->lnext=dc_c_list;
+ dc_c_list=ptr;
+ dc_c_numelements++;
+ } else { // Insert in the beginning of linked list
+ chashlistnode_t * node;
+ chashlistnode_t *search=ptr;
+
+ //make sure it isn't here
+ do {
+ if(search->key == key) {
+ return;
+ }
+ search=search->next;
+ } while(search != NULL);
+
+ dc_c_numelements++;
+ if (dc_c_structs->num<NUMCLIST) {
+ node=&dc_c_structs->array[dc_c_structs->num];
+ dc_c_structs->num++;
+ } else {
+ //get new list
+ cliststruct_t *tcl=calloc(1,sizeof(cliststruct_t));
+ tcl->next=dc_c_structs;
+ dc_c_structs=tcl;
+ node=&tcl->array[0];
+ tcl->num=1;
+ }
+ node->key = key;
+ node->val = val;
+ node->next = ptr->next;
+ ptr->next=node;
+ node->lnext=dc_c_list;
+ dc_c_list=node;
+ }
+}
+#endif
+
unsigned int dc_t_chashResize(unsigned int newsize) {
dchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next chashlistnodes in a linked list
unsigned int oldsize;