import Util.Tuple;
import Analysis.Disjoint.*;
import Analysis.MLP.CodePlan;
-import IR.Flat.*;
import IR.TypeDescriptor;
import Analysis.OoOJava.OoOJavaAnalysis;
private static final String deallocVisitedHashTable = "hashRCRDelete()";
private static final String resetVisitedHashTable = "hashRCRreset()";
- //TODO find correct strings for these
- private static final String addCheckFromHashStructure = "checkFromHashStructure(";
- private static final String putWaitingQueueBlock = "putWaitingQueueBlock("; //lifting of blocks will be done by hashtable.
- private static final String putIntoAllocQueue = "putIntoWaitingQ(";
- private static final int noConflict = 0;
- private static final int conflictButTraverserCanContinue = 1;
- private static final int conflictButTraverserCannotContinue = 2;
- private static final int allocQueueIsNotEmpty = 0;
-
// Hashtable provides fast access to heaproot # lookups
private Hashtable<Taint, WeaklyConectedHRGroup> connectedHRHash;
private ArrayList<WeaklyConectedHRGroup> num2WeaklyConnectedHRGroup;
}
public void init() {
- //Go through the SESE's
- for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
- FlatSESEEnterNode fsen=seseit.next();
+ // Go through the SESE's
+ for (Iterator<FlatSESEEnterNode> seseit = oooa.getAllSESEs().iterator(); seseit.hasNext();) {
+ FlatSESEEnterNode fsen = seseit.next();
Analysis.OoOJava.ConflictGraph conflictGraph;
Hashtable<Taint, Set<Effect>> conflicts;
System.out.println("-------");
System.out.println(fsen);
System.out.println(fsen.getIsCallerSESEplaceholder());
System.out.println(fsen.getParent());
-
- if (fsen.getParent()!=null) {
- conflictGraph = oooa.getConflictGraph(fsen.getParent());
- System.out.println("CG="+conflictGraph);
- if (conflictGraph!=null)
- System.out.println("Conflicts="+conflictGraph.getConflictEffectSet(fsen));
+
+ if (fsen.getParent() != null) {
+ conflictGraph = oooa.getConflictGraph(fsen.getParent());
+ System.out.println("CG=" + conflictGraph);
+ if (conflictGraph != null)
+ System.out.println("Conflicts=" + conflictGraph.getConflictEffectSet(fsen));
}
-
- if(!fsen.getIsCallerSESEplaceholder() && fsen.getParent()!=null &&
- (conflictGraph = oooa.getConflictGraph(fsen.getParent())) != null &&
- (conflicts = conflictGraph.getConflictEffectSet(fsen)) != null) {
- FlatMethod fm=fsen.getfmEnclosing();
- ReachGraph rg=oooa.getDisjointAnalysis().getReachGraph(fm.getMethod());
- if(cSideDebug)
- rg.writeGraph("RCR_RG_SESE_DEBUG");
-
- addToTraverseToDoList(fsen, rg, conflicts);
+
+ if (!fsen.getIsCallerSESEplaceholder() && fsen.getParent() != null
+ && (conflictGraph = oooa.getConflictGraph(fsen.getParent())) != null
+ && (conflicts = conflictGraph.getConflictEffectSet(fsen)) != null) {
+ FlatMethod fm = fsen.getfmEnclosing();
+ ReachGraph rg = oooa.getDisjointAnalysis().getReachGraph(fm.getMethod());
+ if (cSideDebug)
+ rg.writeGraph("RCR_RG_SESE_DEBUG");
+
+ addToTraverseToDoList(fsen, rg, conflicts);
}
}
- //Go through the stall sites
- for(Iterator<FlatNode> codeit=oooa.getNodesWithPlans().iterator();codeit.hasNext();) {
- FlatNode fn=codeit.next();
- CodePlan cp=oooa.getCodePlan(fn);
- FlatSESEEnterNode currentSESE=cp.getCurrentSESE();
+ // Go through the stall sites
+ for (Iterator<FlatNode> codeit = oooa.getNodesWithPlans().iterator(); codeit.hasNext();) {
+ FlatNode fn = codeit.next();
+ CodePlan cp = oooa.getCodePlan(fn);
+ FlatSESEEnterNode currentSESE = cp.getCurrentSESE();
Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(currentSESE);
- if(graph!=null){
- Set<Analysis.OoOJava.SESELock> seseLockSet = oooa.getLockMappings(graph);
- Set<Analysis.OoOJava.WaitingElement> waitingElementSet =
- graph.getStallSiteWaitingElementSet(fn, seseLockSet);
-
- if(waitingElementSet.size()>0){
- for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
- Analysis.OoOJava.WaitingElement waitingElement = (Analysis.OoOJava.WaitingElement) iterator.next();
-
- Analysis.OoOJava.ConflictGraph conflictGraph = graph;
- Hashtable<Taint, Set<Effect>> conflicts;
- ReachGraph rg = oooa.getDisjointAnalysis().getReachGraph(currentSESE.getmdEnclosing());
- if(cSideDebug) {
- rg.writeGraph("RCR_RG_STALLSITE_DEBUG");
- }
- if((conflictGraph != null) &&
- (conflicts = graph.getConflictEffectSet(fn)) != null &&
- (rg != null)){
- addToTraverseToDoList(fn, waitingElement.getTempDesc(), rg, conflicts);
- }
- }
- }
+ if (graph != null) {
+ Set<Analysis.OoOJava.SESELock> seseLockSet = oooa.getLockMappings(graph);
+ Set<Analysis.OoOJava.WaitingElement> waitingElementSet =
+ graph.getStallSiteWaitingElementSet(fn, seseLockSet);
+
+ if (waitingElementSet.size() > 0) {
+ for (Iterator<Analysis.OoOJava.WaitingElement> iterator = waitingElementSet.iterator(); iterator.hasNext();) {
+ Analysis.OoOJava.WaitingElement waitingElement =
+ (Analysis.OoOJava.WaitingElement) iterator.next();
+
+ Analysis.OoOJava.ConflictGraph conflictGraph = graph;
+ Hashtable<Taint, Set<Effect>> conflicts;
+ ReachGraph rg = oooa.getDisjointAnalysis().getReachGraph(currentSESE.getmdEnclosing());
+ if (cSideDebug) {
+ rg.writeGraph("RCR_RG_STALLSITE_DEBUG");
+ }
+ if ((conflictGraph != null) && (conflicts = graph.getConflictEffectSet(fn)) != null
+ && (rg != null)) {
+ addToTraverseToDoList(fn, waitingElement.getTempDesc(), rg, conflicts);
+ }
+ }
+ }
}
}
* 5) Print c methods by walking internal representation
*/
- public void addToTraverseToDoList(FlatSESEEnterNode rblock, ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
+ public void addToTraverseToDoList(FlatSESEEnterNode rblock, ReachGraph rg,
+ Hashtable<Taint, Set<Effect>> conflicts) {
//Add to todo list
toTraverse.add(new TraversalInfo(rblock, rg));
return;
System.out.println("RBLOCK:"+rblock);
System.out.println("["+inVars+"]");
+
// For every non-primitive variable, generate unique method
- // Special Note: The Criteria for executing printCMethod in this loop should match
- // exactly the criteria in buildcode.java to invoke the generated C method(s).
for (TempDescriptor invar : inVars) {
TypeDescriptor type = invar.getType();
- if(type.isPrimitive()) {
+ if(isReallyAPrimitive(type)) {
continue;
}
System.out.println(invar);
- //created stores nodes with specific alloc sites that have been traversed while building
- //internal data structure. It is later traversed sequentially to find inset variables and
+ //"created" stores nodes with specific alloc sites that have been traversed while building
+ //internal data structure. Created is later traversed sequentially to find inset variables and
//build output code.
- //NOTE: Integer stores Allocation Site ID
+ //NOTE: Integer stores Allocation Site ID in hashtable
Hashtable<Integer, ConcreteRuntimeObjNode> created = new Hashtable<Integer, ConcreteRuntimeObjNode>();
VariableNode varNode = rg.getVariableNodeNoMutation(invar);
Taint taint = getProperTaintForFlatSESEEnterNode(rblock, varNode, globalEffects);
//This will add the taint to the printout, there will be NO duplicates (checked above)
if(!created.isEmpty()) {
- for(Iterator<ConcreteRuntimeObjNode> it=created.values().iterator();it.hasNext();) {
- ConcreteRuntimeObjNode obj=it.next();
- if (obj.hasPrimitiveConflicts()||obj.decendantsConflict()) {
- rblock.addInVarForDynamicCoarseConflictResolution(invar);
- break;
- }
- }
+ for(Iterator<ConcreteRuntimeObjNode> it=created.values().iterator();it.hasNext();) {
+ ConcreteRuntimeObjNode obj=it.next();
+ if (obj.hasPrimitiveConflicts()||obj.decendantsConflict()) {
+ rblock.addInVarForDynamicCoarseConflictResolution(invar);
+ break;
+ }
+ }
+
pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
}
}
}
+
+ //This extends a tempDescriptor's isPrimitive test by also excluding primitive arrays.
+ private boolean isReallyAPrimitive(TypeDescriptor type) {
+ return (type.isPrimitive() && !type.isArray());
+ }
private void traverseStallSite(FlatNode enterNode, TempDescriptor invar, ReachGraph rg) {
TypeDescriptor type = invar.getType();
- if(type == null || type.isPrimitive()) {
+ if(type == null || isReallyAPrimitive(type)) {
return;
}
+
Hashtable<Integer, ConcreteRuntimeObjNode> created = new Hashtable<Integer, ConcreteRuntimeObjNode>();
VariableNode varNode = rg.getVariableNodeNoMutation(invar);
Taint taint = getProperTaintForEnterNode(enterNode, varNode, globalEffects);
printCMethod(ths.nodesInHeap, ths.t);
}
- //Prints out the master traverser Invocation that'll call all other traverser
+ //Prints out the master traverser Invocation that'll call all other traversers
//based on traverserID
printMasterTraverserInvocation();
printResumeTraverserInvocation();
}
//Builds Effects Table and runs the analysis on them to get weakly connected HRs
- //SPECIAL NOTE: Only runs after we've taken all the conflicts
+ //SPECIAL NOTE: Only runs after we've taken all the conflicts and effects
private void buildEffectsLookupStructure(){
effectsLookupTable = new EffectsTable(globalEffects, globalConflicts);
effectsLookupTable.runAnalysis();
private void printMasterTraverserInvocation() {
headerFile.println("\nint tasktraverse(SESEcommon * record);");
cFile.println("\nint tasktraverse(SESEcommon * record) {");
+ cFile.println(" if(!CAS(&record->rcrstatus,1,2)) return;");
cFile.println(" switch(record->classID) {");
for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
cFile.println( " "+fsen.getSESErecordName()+" * rec=("+fsen.getSESErecordName()+" *) record;");
Vector<TempDescriptor> invars=fsen.getInVarsForDynamicCoarseConflictResolution();
for(int i=0;i<invars.size();i++) {
- TempDescriptor tmp=invars.get(i);
- cFile.println(" " + this.getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen));
+ TempDescriptor tmp=invars.get(i);
+ cFile.println(" " + this.getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen));
}
cFile.println( " }");
cFile.println( " break;");
for(Taint t: doneTaints.keySet()) {
if (t.isStallSiteTaint()){
- cFile.println( " case -" + getTraverserID(t.getVar(), t.getStallSite())+ ": {");
- cFile.println( " SESEstall * rec=(SESEstall*) record;");
+ cFile.println( " case -" + getTraverserID(t.getVar(), t.getStallSite())+ ": {");
+ cFile.println( " SESEstall * rec=(SESEstall*) record;");
cFile.println( " " + this.getTraverserInvocation(t.getVar(), "rec->___obj___, rec", t.getStallSite())+";");
- cFile.println( " }");
- cFile.println(" break;");
+ cFile.println( " }");
+ cFile.println(" break;");
}
}
- cFile.println(" default:\n printf(\"Invalid SESE ID was passed in.\\n\");\n break;");
+ cFile.println(" default:\n printf(\"Invalid SESE ID was passed in: %d.\\n\",record->classID);\n break;");
cFile.println(" }");
cFile.println("}");
}
- //This will print the traverser invocation that takes in a traverserID and
- //starting ptr
+ //This will print the traverser invocation that takes in a traverserID and starting ptr
private void printResumeTraverserInvocation() {
headerFile.println("\nint traverse(void * startingPtr, SESEcommon * record, int traverserID);");
cFile.println("\nint traverse(void * startingPtr, SESEcommon *record, int traverserID) {");
RefEdge edge = possibleEdges.next();
assert edge != null;
- ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true, false);
+ ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true);
int rootKey = singleRoot.allocSite.getUniqueAllocSiteID();
if (!created.containsKey(rootKey)) {
}
}
}
-
- //This code is the old way of generating an effects lookup table.
- //The new way is to instantiate an EffectsGroup
- @Deprecated
- private Hashtable<AllocSite, EffectsGroup> generateEffectsLookupTable(
- Taint taint, Hashtable<Taint,
- Set<Effect>> effects,
- Hashtable<Taint, Set<Effect>> conflicts) {
- if(taint == null)
- return null;
-
- Set<Effect> localEffects = effects.get(taint);
- Set<Effect> localConflicts = conflicts.get(taint);
-
- //Debug Code for manually checking effects
- if(javaDebug) {
- printEffectsAndConflictsSets(taint, localEffects, localConflicts);
- }
-
- if (localEffects == null || localEffects.isEmpty() || localConflicts == null || localConflicts.isEmpty())
- return null;
-
- Hashtable<AllocSite, EffectsGroup> lookupTable = new Hashtable<AllocSite, EffectsGroup>();
-
- for (Effect e : localEffects) {
- boolean conflict = localConflicts.contains(e);
- AllocSite key = e.getAffectedAllocSite();
- EffectsGroup myEffects = lookupTable.get(key);
-
- if(myEffects == null) {
- myEffects = new EffectsGroup();
- lookupTable.put(key, myEffects);
- }
-
- if(e.getField().getType().isPrimitive()) {
- if(conflict) {
- myEffects.addPrimitive(e, true);
- }
- }
- else {
- myEffects.addObjEffect(e, conflict);
- }
- }
-
- return lookupTable;
- }
// Plan is to add stuff to the tree depth-first sort of way. That way, we can
// propagate up conflicts
ConcreteRuntimeObjNode child;
if(isNewChild) {
- child = new ConcreteRuntimeObjNode(childHRN, false, curr.isObjectArray());
+ child = new ConcreteRuntimeObjNode(childHRN, false);
created.put(childKey, child);
} else {
child = created.get(childKey);
curr.addObjChild(field, child, effectsForGivenField);
if (effectsForGivenField.hasConflict()) {
- child.hasPotentialToBeIncorrectDueToConflict = true;
+ child.hasPotentialToBeIncorrectDueToConflict |= effectsForGivenField.hasReadConflict;
propagateObjConflict(curr, child);
}
}
}
-
-
/*
* This method generates a C method for every inset variable and rblock.
*
*/
private void printCMethod(Hashtable<Integer, ConcreteRuntimeObjNode> created, Taint taint) {
- //This hash table keeps track of all the case statements generated. Although it may seem a bit much
- //for its purpose, I think it may come in handy later down the road to do it this way.
- //(i.e. what if we want to eliminate some cases? Or build filter for 1 case)
String inVar = taint.getVar().getSafeSymbol();
String rBlock;
return;
}
+ //This hash table keeps track of all the case statements generated.
Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
//Generate C cases
addChecker(taint, node, cases, null, "ptr", 0);
}
}
- //IMPORTANT: remember to change getTraverserInvocation if you change the line below
+
String methodName;
int index=-1;
if(cSideDebug) {
cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
- }
+ }
+
if(cases.size() == 0) {
cFile.println(" return;");
//clears queue and hashtable that keeps track of where we've been.
cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
-
- //Casts the ptr to a generic object struct so we can get to the ptr->allocsite field.
+ //generic cast to ___Object___ to access ptr->allocsite field.
cFile.println("struct ___Object___ * ptr = (struct ___Object___ *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable + "(ptr);\n do {");
-
+ if (taint.isRBlockTaint()) {
+ cFile.println(" if(unlikely(record->common.doneExecuting)) {");
+ cFile.println(" record->common.rcrstatus=0;");
+ cFile.println(" return;");
+ cFile.println(" }");
+ }
cFile.println(" switch(ptr->allocsite) {");
- for(AllocSite singleCase: cases.keySet())
+ for(AllocSite singleCase: cases.keySet()) {
cFile.append(cases.get(singleCase));
+ }
cFile.println(" default:\n break; ");
cFile.println(" }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}");
//we have resolved a heap root...see if this was the last dependence
cFile.println(" if(atomic_sub_and_test(1, &(record->common.unresolvedDependencies))) workScheduleSubmit((void *)record);");
cFile.println(" }");
- cFile.println("}");
+ cFile.println(" }");
+ cFile.println(" record->common.rcrstatus=0;");
}
}
cFile.println("}");
}
/*
- * addChecker creates a case statement for every object that is either an inset variable
- * or has multiple referencers (incoming edges). Else it just prints the checker for that object
- * so that its processing can be pushed up to the referencer node.
+ * addChecker creates a case statement for every object that is an inset variable, has more
+ * than 1 parent && has conflicts, or where resumes are possible (from waiting queue).
+ * See .qualifiesForCaseStatement
*/
private void addChecker(Taint taint,
ConcreteRuntimeObjNode node,
String prefix,
int depth) {
StringBuilder currCase = possibleContinuingCase;
- // We don't need a case statement for things with either 1 incoming or 0 out
- // going edges, because they can be processed when checking the parent.
if(qualifiesForCaseStatement(node)) {
assert prefix.equals("ptr") && !cases.containsKey(node.allocSite);
currCase = new StringBuilder();
}
//either currCase is continuing off a parent case or is its own.
assert currCase !=null;
+
boolean primConfRead=false;
boolean primConfWrite=false;
boolean objConfRead=false;
boolean objConfWrite=false;
- //Primitives Test
+ //Direct Primitives Test
for(String field: node.primitiveConflictingFields.keySet()) {
CombinedObjEffects effect=node.primitiveConflictingFields.get(field);
primConfRead|=effect.hasReadConflict;
primConfWrite|=effect.hasWriteConflict;
}
- //Object Reference Test
- for(ObjRef ref: node.objectRefs) {
- CombinedObjEffects effect=ref.myEffects;
- objConfRead|=effect.hasReadConflict;
- objConfWrite|=effect.hasWriteConflict;
+ //Direct Object Reference Test
+ for(String field: node.objectRefs.keySet()) {
+ for(ObjRef ref: node.objectRefs.get(field)) {
+ CombinedObjEffects effect=ref.myEffects;
+ objConfRead|=effect.hasReadConflict;
+ objConfWrite|=effect.hasWriteConflict;
+ }
}
int index=-1;
index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
}
+ String strrcr=taint.isRBlockTaint()?"&record->rcrRecords["+index+"], ":"NULL, ";
+
//Do call if we need it.
if(primConfWrite||objConfWrite) {
int heaprootNum = connectedHRHash.get(taint).id;
int traverserID = doneTaints.get(taint);
currCase.append(" int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
if (objConfRead)
- currCase.append(" int tmpvar"+depth+"=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n");
+ currCase.append(" int tmpvar"+depth+"=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n");
else
- currCase.append(" int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n");
+ currCase.append(" int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n");
} else if (primConfRead||objConfRead) {
int heaprootNum = connectedHRHash.get(taint).id;
assert heaprootNum != -1;
int traverserID = doneTaints.get(taint);
currCase.append(" int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
if (objConfRead)
- currCase.append(" int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n");
+ currCase.append(" int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n");
else
- currCase.append(" int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n");
+ currCase.append(" int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n");
}
if(primConfWrite||objConfWrite||primConfRead||objConfRead) {
currCase.append("if (!(tmpvar"+depth+"&READYMASK)) totalcount--;\n");
- currCase.append("if (!(tmpvar"+depth+"&SPEC)) {\n");
- if (taint.isStallSiteTaint()) {
- currCase.append(" struct rcrRecord * rcrrec=&record->rcrRecords["+index+"];\n");
- currCase.append(" struct rcrRecord * tmprec;\n");
- currCase.append(" if(likely(rcrrec->index<RCRSIZE)) {\n");
- currCase.append(" rcrrec->array[rcrrec->index++]=tmpkey"+depth+";\n");
- currCase.append("} else if(likely((tmprec=rcrrec->next)!=NULL)&&likely(tmprec->index<RCRSIZE)) {\n");
- currCase.append(" tmprec->array[tmprec->index++]=tmpkey"+depth+";\n");
- currCase.append("} else {\n");
- currCase.append(" struct rcrRecord *trec=RUNMALLOC(sizeof(struct rcrRecord));");
- currCase.append(" trec->array[0]=tmpkey"+depth+";\n");
- currCase.append(" trec->index=1;\n");
- currCase.append(" trec->next=tmprec;\n");
- currCase.append(" rcrrec->next=trec;\n");
- currCase.append("}\n");
- }
- currCase.append("}\n");
}
- //Array Case
- if(node.isObjectArray() && node.decendantsConflict()) {
- //since each array element will get its own case statement, we just need to enqueue each item into the queue
- //note that the ref would be the actual object and node would be of struct ArrayObject
+ //Handle conflicts further down.
+ if(node.decendantsConflict()) {
+ int pdepth=depth+1;
+ currCase.append("{\n");
- ArrayList<Integer> allocSitesWithProblems = node.getReferencedAllocSites();
- if(!allocSitesWithProblems.isEmpty()) {
- //This is done with the assumption that an array of object stores pointers.
+ //Array Case
+ if(node.isArray() && node.decendantsConflict()) {
+ String childPtr = "((struct ___Object___ **)(((char *) &(((struct ArrayObject *)"+ prefix+")->___length___))+sizeof(int)))[i]";
+ String currPtr = "arrayElement" + pdepth;
+
currCase.append("{\n int i;\n");
+ currCase.append(" struct ___Object___ * "+currPtr+";\n");
currCase.append(" for(i = 0; i<((struct ArrayObject *) " + prefix + " )->___length___; i++ ) {\n");
- currCase.append(" struct ___Object___ * arrayElement =((struct ___Object___ **)(((char *) &(((struct ArrayObject *)"+ prefix+")->___length___))+sizeof(int)))[i];\n");
- currCase.append(" if( arrayElement != NULL && (");
-
- for(Integer i: allocSitesWithProblems) {
- currCase.append("( arrayElement->allocsite == " + i.toString() +") ||");
- }
- //gets rid of the last ||
- currCase.delete(currCase.length()-3, currCase.length());
- currCase.append(") && "+queryVistedHashtable +"(arrayElement)) {\n");
- currCase.append(" " + addToQueueInC + "arrayElement); }}}\n");
- }
- } else {
- //All other cases
- for(ObjRef ref: node.objectRefs) {
- currCase.append("{ \n");
- // Will only process edge if there is some sort of conflict with the Child
- if (ref.hasConflictsDownThisPath()) {
- String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + ref.field + "___";
- int pdepth=depth+1;
- String currPtr = "myPtr" + pdepth;
- String structType = ref.child.original.getType().getSafeSymbol();
- currCase.append(" struct " + structType + " * "+currPtr+"= (struct "+ structType + " * ) " + childPtr + ";\n");
-
- // Checks if the child exists and has allocsite matching the conflict
- currCase.append(" if (" + currPtr + " != NULL && " + currPtr + getAllocSiteInC + "==" + ref.allocSite + ") {\n");
-
- if (ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
- // Checks if we have visited the child before
-
- currCase.append(" if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
- if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
- addChecker(taint, ref.child, cases, currCase, currPtr, depth + 1);
- }
- else {
- currCase.append(" " + addToQueueInC + childPtr + ");\n ");
- }
- currCase.append(" }\n");
- }
- //one more brace for the opening if
- if(ref.hasDirectObjConflict()) {
- currCase.append(" }\n");
+ //There should be only one field, hence we only take the first field in the keyset.
+ assert node.objectRefs.keySet().size() <= 1;
+ ObjRefList refsAtParticularField = node.objectRefs.get(node.objectRefs.keySet().iterator().next());
+ printObjRefSwitchStatement(taint,cases,pdepth,currCase,refsAtParticularField,childPtr,currPtr);
+ currCase.append(" }}\n");
+ } else {
+ //All other cases
+ String currPtr = "myPtr" + pdepth;
+ currCase.append(" struct ___Object___ * "+currPtr+";\n");
+ for(String field: node.objectRefs.keySet()) {
+ ObjRefList refsAtParticularField = node.objectRefs.get(field);
+
+ if(refsAtParticularField.hasConflicts()) {
+ String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + field + "___";
+ printObjRefSwitchStatement(taint, cases, depth, currCase, refsAtParticularField, childPtr, currPtr);
}
- currCase.append(" }\n ");
- }
- currCase.append("} ");
+ }
}
+
+ currCase.append("}\n"); //For particular top level case statement.
}
-
if(qualifiesForCaseStatement(node)) {
currCase.append(" }\n break;\n");
}
}
+
+ private void printObjRefSwitchStatement(Taint taint, Hashtable<AllocSite, StringBuilder> cases,
+ int pDepth, StringBuilder currCase, ObjRefList refsAtParticularField, String childPtr,
+ String currPtr) {
+
+ currCase.append(" "+currPtr+"= (struct ___Object___ * ) " + childPtr + ";\n");
+ currCase.append(" if (" + currPtr + " != NULL) { \n");
+ currCase.append(" switch(" + currPtr + getAllocSiteInC + ") {\n");
+
+ for(ObjRef ref: refsAtParticularField) {
+ if(ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
+ currCase.append(" case "+ref.allocSite+":\n {\n");
+ //The hash insert is here because we don't want to enqueue things unless we know it conflicts.
+ currCase.append(" if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
+
+ //Either it's an in-lineable case or we're just handling primitive conflicts
+ if ((ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) ||
+ (ref.child.hasPrimitiveConflicts() && !qualifiesForCaseStatement(ref.child)))
+ {
+ addChecker(taint, ref.child, cases, currCase, currPtr, pDepth + 1);
+ }
+ else {
+ //if we are going to insert something into the queue,
+ //we should be able to resume traverser from it.
+ assert qualifiesForCaseStatement(ref.child);
+ currCase.append(" " + addToQueueInC + childPtr + ");\n ");
+ }
+ currCase.append(" }\n"); //close for queryVistedHashtable
+
+ currCase.append("}\n"); //close for internal case statement
+ }
+ }
+
+ currCase.append(" default:\n" +
+ " break;\n"+
+ " }}\n"); //internal switch.
+ }
private boolean qualifiesForCaseStatement(ConcreteRuntimeObjNode node) {
return (
//non-inline-able code cases
(node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
//Cases where resumes are possible
- (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict) ||
- //Array elements since we have to enqueue them all, we can't in line their checks
- (node.canBeArrayElement() && (node.decendantsConflict() || node.hasPrimitiveConflicts()));
- }
-
- //This method will touch the waiting queues if necessary.
- //IMPORTANT NOTE: This needs a closing } from the caller and the if is cannot continue
- private void addCheckHashtableAndWaitingQ(StringBuilder currCase, Taint t, ConcreteRuntimeObjNode node, String ptr, int depth) {
- Iterator<ConcreteRuntimeObjNode> it = node.enqueueToWaitingQueueUponConflict.iterator();
-
- currCase.append(" int retval"+depth+" = "+ addCheckFromHashStructure + ptr + ");\n");
- currCase.append(" if (retval"+depth+" == " + conflictButTraverserCannotContinue + " || ");
- checkWaitingQueue(currCase, t, node);
- currCase.append(") {\n");
- //If cannot continue, then add all the undetermined references that lead from this child, including self.
- //TODO need waitingQueue Side to automatically check the thing infront of it to prevent double adds.
- putIntoWaitingQueue(currCase, t, node, ptr);
-
- ConcreteRuntimeObjNode related;
- while(it.hasNext()) {
- related = it.next();
- //TODO maybe ptr won't even be needed since upon resume, the hashtable will remove obj.
- putIntoWaitingQueue(currCase, t, related, ptr);
- }
- }
-
- /*
- private void handleObjConflict(StringBuilder currCase, String childPtr, AllocSite allocSite, ObjRef ref) {
- currCase.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.getUniqueAllocSiteID() + ");");
- }
-
- private void handlePrimitiveConflict(StringBuilder currCase, String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
- currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); ");
+ (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict);
}
- */
private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
Hashtable<Taint, Set<Effect>> effects) {
}
return null;
}
-
- private void printEffectsAndConflictsSets(Taint taint, Set<Effect> localEffects,
- Set<Effect> localConflicts) {
- System.out.println("#### List of Effects/Conflicts ####");
- System.out.println("For Taint " + taint);
- System.out.println("Effects");
- if(localEffects != null) {
- for(Effect e: localEffects) {
- System.out.println(e);
- }
- }
- System.out.println("Conflicts");
- if(localConflicts != null) {
- for(Effect e: localConflicts) {
- System.out.println(e);
- }
- }
- }
private void printDebug(boolean guard, String debugStatements) {
if(guard)
System.out.println(debugStatements);
}
- //TODO finish this once waitingQueue side is figured out
- private void putIntoWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node, String resumePtr ) {
- //Method looks like this: void put(int allocSiteID, x
- //struct WaitingQueue * queue, //get this from hashtable
- //int effectType, //not so sure we would actually need this one.
- //void * resumePtr,
- //int traverserID); }
- int heaprootNum = connectedHRHash.get(taint).id;
- assert heaprootNum != -1;
- int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
- int traverserID = doneTaints.get(taint);
-
- //NOTE if the C-side is changed, this will have to be changed accordingly
- //TODO make sure this matches c-side
- sb.append(" putIntoWaitingQueue("+allocSiteID+", " +
- "allHashStructures["+ heaprootNum +"]->waitingQueue, " +
- resumePtr + ", " +
- traverserID+");\n");
- }
-
- //TODO finish waitingQueue side
- /**
- * Inserts check to see if waitingQueue is occupied.
- *
- * On C-side, =0 means empty queue, else occupied.
- */
- private void checkWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node) {
- //Method looks like int check(struct WaitingQueue * queue, int allocSiteID)
- assert sb != null && taint !=null;
- int heaprootNum = connectedHRHash.get(taint).id;
- assert heaprootNum != -1;
- int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
-
- sb.append(" (isEmptyForWaitingQ(allHashStructures["+ heaprootNum +"]->waitingQueue, " + allocSiteID + ") == "+ allocQueueIsNotEmpty+")");
- }
-
private void enumerateHeaproots() {
- //reset numbers jsut in case
weaklyConnectedHRCounter = 0;
num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
}
private class ConcreteRuntimeObjNode {
- ArrayList<ObjRef> objectRefs;
+ Hashtable<String, ObjRefList> objectRefs;
Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
boolean decendantsObjConflict;
boolean hasPotentialToBeIncorrectDueToConflict;
boolean isInsetVar;
- boolean isArrayElement;
AllocSite allocSite;
HeapRegionNode original;
- public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar, boolean isArrayElement) {
- objectRefs = new ArrayList<ObjRef>();
+ public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar) {
+ objectRefs = new Hashtable<String, ObjRefList>(5);
primitiveConflictingFields = null;
parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
decendantsPrimConflict = false;
decendantsObjConflict = false;
hasPotentialToBeIncorrectDueToConflict = false;
- this.isArrayElement = isArrayElement;
}
public void addReachableParent(ConcreteRuntimeObjNode curr) {
}
public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
+ printDebug(javaDebug,this.allocSite.getUniqueAllocSiteID() + " added child at " + child.getAllocationSite());
ObjRef ref = new ObjRef(field, child, ce);
- if(objectRefs.contains(ref)) {
- ObjRef other = objectRefs.get(objectRefs.indexOf(ref));
- other.mergeWith(ref);
+ if(objectRefs.containsKey(field)){
+ ObjRefList array = objectRefs.get(field);
+
+ if(array.contains(ref)) {
+ ObjRef other = array.get(array.indexOf(ref));
+ other.mergeWith(ref);
+ printDebug(javaDebug," Merged with old");
+ printDebug(javaDebug," Old="+ other.child.original + "\n new="+ref.child.original);
+ }
+ else {
+ array.add(ref);
+ printDebug(javaDebug," Just added new;\n Field: " + field);
+ printDebug(javaDebug," AllocSite: " + child.getAllocationSite());
+ printDebug(javaDebug," Child: "+child.original);
+ }
}
else {
- objectRefs.add(ref);
+ ObjRefList array = new ObjRefList(3);
+
+ array.add(ref);
+ objectRefs.put(field, array);
}
}
- public boolean isObjectArray() {
- return original.getType().isArray() && !original.getType().isPrimitive() && !original.getType().isImmutable();
- }
-
- public boolean canBeArrayElement() {
- return isArrayElement;
+ public boolean isArray() {
+ return original.getType().isArray();
}
public ArrayList<Integer> getReferencedAllocSites() {
ArrayList<Integer> list = new ArrayList<Integer>();
- for(ObjRef r: objectRefs) {
- if(r.hasDirectObjConflict() || (r.child.parentsWithReadToNode.contains(this) && r.hasConflictsDownThisPath())) {
- list.add(r.allocSite);
+ for(String key: objectRefs.keySet()) {
+ for(ObjRef r: objectRefs.get(key)) {
+ if(r.hasDirectObjConflict() || (r.child.parentsWithReadToNode.contains(this) && r.hasConflictsDownThisPath())) {
+ list.add(r.allocSite);
+ }
}
}
}
}
+ //Simple extension of the ArrayList to allow it to find if any ObjRefs conflict.
+ private class ObjRefList extends ArrayList<ObjRef> {
+ private static final long serialVersionUID = 326523675530835596L;
+
+ public ObjRefList(int size) {
+ super(size);
+ }
+
+ public boolean add(ObjRef o){
+ return super.add(o);
+ }
+
+ public boolean hasConflicts() {
+ for(ObjRef r: this) {
+ if(r.hasConflictsDownThisPath() || r.child.hasPrimitiveConflicts())
+ return true;
+ }
+
+ return false;
+ }
+ }
+
private class EffectsTable {
private Hashtable<AllocSite, BucketOfEffects> table;
printoutTable(this);
}
- //TODO is there a higher performance way to do this?
for(AllocSite key: table.keySet()) {
BucketOfEffects effects = table.get(key);
//make sure there are actually conflicts in the bucket
taint2EffectsGroup.put(t, effectsForGivenTaint);
}
- if (e.getField().getType().isPrimitive()) {
+ if (isReallyAPrimitive(e.getField().getType())) {
if (conflict) {
effectsForGivenTaint.addPrimitive(e, true);
}