From 4c1afd2f75a816cbe151ac3ba2b8b4015ad3f7ae Mon Sep 17 00:00:00 2001 From: bdemsky Date: Thu, 22 Oct 2009 20:58:20 +0000 Subject: [PATCH] add new features...they don't break the build, but need to check if they work... --- .../Analysis/Locality/DelayComputation.java | 100 ++++++++++++++---- .../Analysis/Locality/DiscoverConflicts.java | 10 +- Robust/src/IR/Flat/BuildCode.java | 72 ++++++++++++- Robust/src/IR/Tree/BuildIR.java | 16 ++- Robust/src/Main/Main.java | 14 ++- Robust/src/Runtime/STM/stmlookup.c | 56 ++++++++++ 6 files changed, 237 insertions(+), 31 deletions(-) diff --git a/Robust/src/Analysis/Locality/DelayComputation.java b/Robust/src/Analysis/Locality/DelayComputation.java index 2216689d..af98cdc5 100644 --- a/Robust/src/Analysis/Locality/DelayComputation.java +++ b/Robust/src/Analysis/Locality/DelayComputation.java @@ -24,6 +24,7 @@ public class DelayComputation { DiscoverConflicts dcopts; Hashtable> notreadymap; Hashtable> cannotdelaymap; + Hashtable> derefmap; Hashtable> othermap; public DelayComputation(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) { @@ -33,6 +34,8 @@ public class DelayComputation { this.gft=gft; this.notreadymap=new Hashtable>(); this.cannotdelaymap=new Hashtable>(); + if (state.STMARRAY) + this.derefmap=new Hashtable>(); this.othermap=new Hashtable>(); } @@ -44,7 +47,17 @@ public class DelayComputation { return cannotdelaymap; } + + public HashSet 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 localityset=locality.getLocalityBindings(); for(Iterator lbit=localityset.iterator();lbit.hasNext();) { analyzeMethod(lbit.next()); @@ -272,6 +285,7 @@ public class DelayComputation { FlatMethod fm=state.getMethodFlat(md); HashSet delayedset=notreadymap.get(lb); + HashSet derefset=derefmap.get(lb); HashSet otherset=othermap.get(lb); HashSet cannotdelayset=cannotdelaymap.get(lb); Hashtable> livemap=Liveness.computeLiveTemps(fm); @@ -358,16 +372,27 @@ public class DelayComputation { } if (delayedset.contains(fn)) { - //If the node is in the second set, check our readset - TempDescriptor readset[]=fn.readsTemps(); - for(int i=0;i cannotdelay=new HashSet(); + HashSet derefset=new HashSet(); Hashtable atomictable=locality.getAtomic(lb); if (lb.isAtomic()) { //We are in a transaction already... @@ -448,6 +477,8 @@ public class DelayComputation { return; } + Hashtable> oldtempmap=dcopts.computeOldTemps(lb); + HashSet toanalyze=new HashSet(); toanalyze.addAll(fm.getNodeSet()); @@ -458,6 +489,7 @@ public class DelayComputation { Hashtable> nodelayfieldsrd=new Hashtable>(); Hashtable> nodelayarraysrd=new Hashtable>(); + Hashtable> revbranchmap=revGetBranchSet(lb); Hashtable> 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 @@ -518,11 +550,14 @@ public class DelayComputation { //Delay branches if possible if (fn.kind()==FKind.FlatCondBranch) { - Set leftset=getNext(fn, 0, cannotdelay, lb, locality,true); - Set rightset=getNext(fn, 1, cannotdelay, lb, locality,true); - if (leftset.size()>0&&rightset.size()>0&& - !leftset.equals(rightset)||leftset.size()>1) - isnodelay=true; + Set branchset=revbranchmap.get(lb); + for(Iterator 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 @@ -573,8 +608,11 @@ public class DelayComputation { Set fcbset=branchmap.get(fn); for(Iterator 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 */ @@ -609,26 +647,46 @@ public class DelayComputation { } } else { //Need to know which objects to lock on + Set 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; } } @@ -676,6 +734,8 @@ public class DelayComputation { }//end of while loop if (lb.getHasAtomic()) { + if (state.STMARRAY) + derefmap.put(lb, derefset); cannotdelaymap.put(lb, cannotdelay); } } //end of method diff --git a/Robust/src/Analysis/Locality/DiscoverConflicts.java b/Robust/src/Analysis/Locality/DiscoverConflicts.java index 3e13b36c..775c87eb 100644 --- a/Robust/src/Analysis/Locality/DiscoverConflicts.java +++ b/Robust/src/Analysis/Locality/DiscoverConflicts.java @@ -625,6 +625,9 @@ public class DiscoverConflicts { /* 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); @@ -633,14 +636,17 @@ public class DiscoverConflicts { FlatNode fn=fnit.next(); Hashtable atomictable=locality.getAtomic(lb); if (atomictable.get(fn).intValue()>0) { + Set 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: } diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index 82f889ba..f5f35791 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -271,13 +271,13 @@ public class BuildCode { 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(); @@ -285,7 +285,7 @@ public class BuildCode { 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 @@ -2149,20 +2149,32 @@ public class BuildCode { Set storeset=null; HashSet genset=null; + HashSet refset=null; Set unionset=null; if (state.DELAYCOMP&&!lb.isAtomic()&&lb.getHasAtomic()) { storeset=delaycomp.livecode(lb); genset=new HashSet(); + if (state.STMARRAY) { + refset=new HashSet(); + 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(); unionset.addAll(storeset); unionset.addAll(genset); + if (state.STMARRAY) + unionset.addAll(refset); } /* Do the actual code generation */ @@ -2236,13 +2248,19 @@ public class BuildCode { 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+" */"); @@ -2333,6 +2351,52 @@ public class BuildCode { } } + 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 assignLabels(FlatNode first) { return assignLabels(first, null); diff --git a/Robust/src/IR/Tree/BuildIR.java b/Robust/src/IR/Tree/BuildIR.java index 8a97ce79..e9176923 100644 --- a/Robust/src/IR/Tree/BuildIR.java +++ b/Robust/src/IR/Tree/BuildIR.java @@ -581,9 +581,19 @@ public class BuildIR { 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) { diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index a4e54b0d..4b70f6e7 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -479,8 +479,18 @@ public class Main { } 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. */ diff --git a/Robust/src/Runtime/STM/stmlookup.c b/Robust/src/Runtime/STM/stmlookup.c index 594e3aeb..42ce0d91 100644 --- a/Robust/src/Runtime/STM/stmlookup.c +++ b/Robust/src/Runtime/STM/stmlookup.c @@ -368,6 +368,62 @@ void dc_t_chashInsertOnceArray(void * key, unsigned int intkey, void *val) { } #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->numarray[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; -- 2.34.1