X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FIR%2FFlat%2FRuntimeConflictResolver.java;h=9b580b4d7a9a095072d794067195b60172c46a1a;hb=a265ff8477925a0f10dfb8ff8c021bdfe795cada;hp=f852c54de5b953269d6cc8505d2a90c90b9b6116;hpb=297805cd3b458096e0d4fcb39e5ea7542ad45077;p=IRC.git diff --git a/Robust/src/IR/Flat/RuntimeConflictResolver.java b/Robust/src/IR/Flat/RuntimeConflictResolver.java index f852c54d..9b580b4d 100644 --- a/Robust/src/IR/Flat/RuntimeConflictResolver.java +++ b/Robust/src/IR/Flat/RuntimeConflictResolver.java @@ -1,320 +1,387 @@ package IR.Flat; + import java.io.File; import java.io.FileNotFoundException; -import java.io.PrintWriter; import java.util.ArrayList; -import java.util.Collection; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; import java.util.Set; import java.util.Vector; -import Util.Tuple; +import Util.Pair; import Analysis.Disjoint.*; -import Analysis.MLP.CodePlan; -import IR.Flat.*; +import Analysis.Pointer.*; +import Analysis.Pointer.AllocFactory.AllocNode; +import IR.State; import IR.TypeDescriptor; +import Analysis.OoOJava.ConflictEdge; +import Analysis.OoOJava.ConflictGraph; +import Analysis.OoOJava.ConflictNode; import Analysis.OoOJava.OoOJavaAnalysis; +import Util.CodePrinter; /* An instance of this class manages all OoOJava coarse-grained runtime conflicts * by generating C-code to either rule out the conflict at runtime or resolve one. * * How to Use: * 1) Instantiate singleton object (String input is to specify output dir) - * 2) Call setGlobalEffects setGlobalEffects(Hashtable> ) ONCE - * 3) Input SESE blocks, for each block: - * 3a) call addToTraverseToDoList(FlatSESEEnterNode , ReachGraph , Hashtable>) for the seseBlock - * 3b) call String getTraverserInvocation(TempDescriptor, String, FlatSESEEnterNode) to get the name of the traverse method in C - * 4) Call void close() - * Note: All computation is done upon closing the object. Steps 1-3 only input data + * 2) Call void close() */ public class RuntimeConflictResolver { - public static final boolean javaDebug = true; - public static final boolean cSideDebug = false; - - private PrintWriter cFile; - private PrintWriter headerFile; + private CodePrinter headerFile, cFile; private static final String hashAndQueueCFileDir = "oooJava/"; + //This keeps track of taints we've traversed to prevent printing duplicate traverse functions //The Integer keeps track of the weakly connected group it's in (used in enumerateHeapRoots) - private Hashtable doneTaints; - private Hashtable idMap=new Hashtable(); - private Hashtable> globalEffects; - private Hashtable> globalConflicts; - private ArrayList toTraverse; - + //private Hashtable doneTaints; + private Hashtable idMap=new Hashtable(); + + //Keeps track of stallsites that we've generated code for. + protected Hashtable processedStallSites = new Hashtable (); + public int currentID=1; - + private int totalWeakGroups; + private OoOJavaAnalysis oooa; + private State globalState; + // initializing variables can be found in printHeader() - private static final String getAllocSiteInC = "->allocsite"; - private static final String queryVistedHashtable = "hashRCRInsert"; - private static final String addToQueueInC = "enqueueRCRQueue("; + private static final String allocSite = "allocsite"; + private static final String queryAndAddToVisitedHashtable = "hashRCRInsert"; + private static final String enqueueInC = "enqueueRCRQueue"; private static final String dequeueFromQueueInC = "dequeueRCRQueue()"; private static final String clearQueue = "resetRCRQueue()"; // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor) private static final String mallocVisitedHashtable = "hashRCRCreate(128, 0.75)"; 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 connectedHRHash; - private ArrayList num2WeaklyConnectedHRGroup; - private int traverserIDCounter; - private int weaklyConnectedHRCounter; - private ArrayList pendingPrintout; - private EffectsTable effectsLookupTable; - private OoOJavaAnalysis oooa; - public RuntimeConflictResolver(String buildir, OoOJavaAnalysis oooa) throws FileNotFoundException { - String outputFile = buildir + "RuntimeConflictResolver"; - this.oooa=oooa; + public RuntimeConflictResolver( String buildir, + OoOJavaAnalysis oooa, + State state) + throws FileNotFoundException { + this.oooa = oooa; + this.globalState = state; - cFile = new PrintWriter(new File(outputFile + ".c")); - headerFile = new PrintWriter(new File(outputFile + ".h")); + processedStallSites = new Hashtable (); + BuildStateMachines bsm = oooa.getBuildStateMachines(); + totalWeakGroups = bsm.getTotalNumOfWeakGroups(); - cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \"" - + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include "); - cFile.println("#include \"classdefs.h\""); - cFile.println("#include \"structdefs.h\""); - cFile.println("#include \"mlp_runtime.h\""); - cFile.println("#include \"RuntimeConflictResolver.h\""); - cFile.println("#include \"hashStructure.h\""); + setupOutputFiles(buildir); + + for( Pair p: bsm.getAllMachineNames() ) { + FlatNode taskOrStallSite = p.getFirst(); + TempDescriptor var = p.getSecond(); + StateMachineForEffects stateMachine = bsm.getStateMachine( taskOrStallSite, var ); + + //prints the traversal code + printCMethod( taskOrStallSite, var, stateMachine); + } - headerFile.println("#ifndef __3_RCR_H_"); - headerFile.println("#define __3_RCR_H_"); + //IMPORTANT must call .close() elsewhere to finish printing the C files. + } + + /* + * This method generates a C method for every inset variable and rblock. + * + * The C method works by generating a large switch statement that will run the appropriate + * checking code for each object based on the current state. The switch statement is + * surrounded by a while statement which dequeues objects to be checked from a queue. An + * object is added to a queue only if it contains a conflict (in itself or in its referencees) + * and we came across it while checking through it's referencer. Because of this property, + * conflicts will be signaled by the referencer; the only exception is the inset variable which can + * signal a conflict within itself. + */ + + private void printCMethod( FlatNode taskOrStallSite, + TempDescriptor var, + StateMachineForEffects smfe) { + + // collect info for code gen + FlatSESEEnterNode task = null; + String inVar = var.getSafeSymbol(); + SMFEState initialState = smfe.getInitialState(); + boolean isStallSite = !(taskOrStallSite instanceof FlatSESEEnterNode); + int weakID = smfe.getWeaklyConnectedGroupID(taskOrStallSite); - doneTaints = new Hashtable(); - connectedHRHash = new Hashtable(); + String blockName; + //No need generate code for empty traverser + if (smfe.isEmpty()) + return; + + if( isStallSite ) { + blockName = taskOrStallSite.toString(); + processedStallSites.put(taskOrStallSite, var); + } else { + task = (FlatSESEEnterNode) taskOrStallSite; + + //if the task is the main task, there's no traverser + if(task.isMainSESE) + return; + + blockName = task.getPrettyIdentifier(); + } + + - traverserIDCounter = 1; - weaklyConnectedHRCounter = 0; - pendingPrintout = new ArrayList(); - toTraverse = new ArrayList(); - globalConflicts = new Hashtable>(); - //Note: globalEffects is not instantiated since it'll be passed in whole while conflicts comes in chunks - } + String methodName = "void traverse___" + inVar + removeInvalidChars(blockName) + "___(void * InVar, "; + int index = -1; - public void setGlobalEffects(Hashtable> effects) { - globalEffects = effects; + if( isStallSite ) { + methodName += "SESEstall *record)"; + } else { + methodName += task.getSESErecordName() +" *record)"; + //TODO check that this HACK is correct (i.e. adding and then polling immediately afterwards) + task.addInVarForDynamicCoarseConflictResolution(var); + index = task.getInVarsForDynamicCoarseConflictResolution().indexOf( var ); + } - if(javaDebug) { - System.out.println("============EFFECTS LIST AS PASSED IN============"); - for(Taint t: globalEffects.keySet()) { - System.out.println("For Taint " + t); - for(Effect e: globalEffects.get(t)) { - System.out.println("\t" + e); - } - } - System.out.println("====================END LIST===================="); + cFile.println( methodName + " {"); + headerFile.println( methodName + ";" ); + + cFile.println( " int totalcount = RUNBIAS;"); + if( isStallSite ) { + cFile.println(" record->rcrRecords[0].count = RUNBIAS;"); + } else { + cFile.println(" record->rcrRecords["+index+"].count = RUNBIAS;"); } - } - public void init() { - //Go through the SESE's - for(Iterator seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) { - FlatSESEEnterNode fsen=seseit.next(); - Analysis.OoOJava.ConflictGraph conflictGraph; - Hashtable> 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)); - } + //clears queue and hashtable that keeps track of where we've been. + cFile.println(clearQueue + ";"); + cFile.println(resetVisitedHashTable + ";"); + cFile.println(" RCRQueueEntry * queueEntry; //needed for dequeuing"); + + cFile.println(" int traverserState = "+initialState.getID()+";"); + + //generic cast to ___Object___ to access ptr->allocsite field. + cFile.println(" struct ___Object___ * ptr = (struct ___Object___ *) InVar;"); + cFile.println(" if (InVar != NULL) {"); + cFile.println(" " + queryAndAddToVisitedHashtable + "(ptr, "+initialState.getID()+");"); + cFile.println(" do {"); + + if( !isStallSite ) { + cFile.println(" if(unlikely(record->common.doneExecuting)) {"); + cFile.println(" record->common.rcrstatus=0;"); + cFile.println(" return;"); + cFile.println(" }"); + } + + + // Traverse the StateMachineForEffects (a graph) + // that serves as a plan for building the heap examiner code. + // SWITCH on the states in the state machine, THEN + // SWITCH on the concrete object's allocation site THEN + // consider conflicts, enqueue more work, inline more SWITCHES, etc. - 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); - } + boolean needswitch=smfe.getStates().size()>1; + + if (needswitch) { + cFile.println(" switch( traverserState ) {"); } - //Go through the stall sites - for(Iterator 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); + for(SMFEState state: smfe.getStates()) { - if(graph!=null){ - Set seseLockSet = oooa.getLockMappings(graph); - Set 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> 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(state.getRefCount() != 1 || initialState == state) { + if (needswitch) { + cFile.println(" case "+state.getID()+":"); + } else { + cFile.println(" if(traverserState=="+state.getID()+") {"); } + + printAllocChecksInsideState(state, taskOrStallSite, var, "ptr", 0, weakID); + + cFile.println(" break;"); } } + + if (needswitch) { + cFile.println(" default: break;"); + } + cFile.println(" } // end switch on traverser state"); + cFile.println(" queueEntry = " + dequeueFromQueueInC + ";"); + cFile.println(" if(queueEntry == NULL) {"); + cFile.println(" break;"); + cFile.println(" }"); + cFile.println(" ptr = queueEntry->object;"); + cFile.println(" traverserState = queueEntry->traverserState;"); + cFile.println(" } while(ptr != NULL);"); + cFile.println(" } // end if inVar not null"); + + + if( isStallSite ) { + cFile.println(" if(atomic_sub_and_test(totalcount,&(record->rcrRecords[0].count))) {"); + cFile.println(" psem_give_tag(record->common.parentsStallSem, record->tag);"); + cFile.println(" BARRIER();"); + cFile.println(" }"); + } else { + cFile.println(" if(atomic_sub_and_test(totalcount,&(record->rcrRecords["+index+"].count))) {"); + cFile.println(" int flag=LOCKXCHG32(&(record->rcrRecords["+index+"].flag),0);"); + cFile.println(" if(flag) {"); + //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(" }"); + } - buildEffectsLookupStructure(); - runAllTraversals(); + cFile.println("}"); + cFile.flush(); } - /* - * Basic Strategy: - * 1) Get global effects and conflicts - * 2) Create a hash structure (EffectsTable) to manage effects (hashed by affected Allocsite, then taint, then field) - * 2a) Use Effects to verify we can access something (reads) - * 2b) Use conflicts to mark conflicts (read/write/strongupdate) - * 2c) At second level of hash, store Heaproots that can cause conflicts at the field - * 3) Walk hash structure to identify and enumerate weakly connected groups and generate waiting queue slots. - * 4) Build internal representation of the rgs (pruned) - * 5) Print c methods by walking internal representation - */ - - public void addToTraverseToDoList(FlatSESEEnterNode rblock, ReachGraph rg, Hashtable> conflicts) { - //Add to todo list - toTraverse.add(new TraversalInfo(rblock, rg)); + public void printAllocChecksInsideState(SMFEState state, FlatNode fn, TempDescriptor tmp, String prefix, int depth, int weakID) { + EffectsTable et = new EffectsTable(state); + boolean needswitch=et.getAllAllocs().size()>1; + if (needswitch) { + cFile.println(" switch(" + prefix+"->"+allocSite + ") {"); + } - //Add to Global conflicts - for(Taint t: conflicts.keySet()) { - if(globalConflicts.containsKey(t)) { - globalConflicts.get(t).addAll(conflicts.get(t)); + //we assume that all allocs given in the effects are starting locs. + for(Alloc a: et.getAllAllocs()) { + if (needswitch) { + cFile.println(" case "+a.getUniqueAllocSiteID()+": {"); } else { - globalConflicts.put(t, conflicts.get(t)); + cFile.println(" if("+prefix+"->"+allocSite+"=="+a.getUniqueAllocSiteID()+") {"); + } + addChecker(a, fn, tmp, state, et, prefix, depth, weakID); + if (needswitch) { + cFile.println(" }"); + cFile.println(" break;"); } } + if (needswitch) { + cFile.println(" default:"); + cFile.println(" break;"); + } + cFile.println(" }"); } - - public void addToTraverseToDoList(FlatNode fn, TempDescriptor tempDesc, - ReachGraph rg, Hashtable> conflicts) { - toTraverse.add(new TraversalInfo(fn, rg, tempDesc)); - - for(Taint t: conflicts.keySet()) { - if(globalConflicts.containsKey(t)) { - globalConflicts.get(t).addAll(conflicts.get(t)); - } else { - globalConflicts.put(t, conflicts.get(t)); - } + public void addChecker(Alloc a, FlatNode fn, TempDescriptor tmp, SMFEState state, EffectsTable et, String prefix, int depth, int weakID) { + if (depth>30) { + System.out.println(fn+" "+state+" "+state.toStringDOT()); } - } - private void traverseSESEBlock(FlatSESEEnterNode rblock, ReachGraph rg) { - Collection inVars = rblock.getInVarSet(); + insertEntriesIntoHashStructureNew(fn, tmp, et, a, prefix, depth, weakID); - if (inVars.size() == 0) - return; + int pdepth = depth+1; - // 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 == null || type.isPrimitive()) { - continue; - } - - //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 - //build output code. - Hashtable created = new Hashtable(); - VariableNode varNode = rg.getVariableNodeNoMutation(invar); - Taint taint = getProperTaintForFlatSESEEnterNode(rblock, varNode, globalEffects); - if (taint == null) { - printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + rblock.toPrettyString()); - return; - } - - //This is to prevent duplicate traversals from being generated - if(doneTaints.containsKey(taint)) - return; + if(a.getType().isArray()) { + String childPtr = "((struct ___Object___ **)(((char *) &(((struct ArrayObject *)"+ prefix+")->___length___))+sizeof(int)))[i]"; + String currPtr = "arrayElement" + pdepth; - doneTaints.put(taint, traverserIDCounter++); - createConcreteGraph(effectsLookupTable, created, varNode, taint); + boolean first=true; + for(Effect e: et.getEffects(a)) { + if (!state.transitionsTo(e).isEmpty()) { + if (first) { + cFile.println(" int i;"); + cFile.println(" struct ___Object___ * "+currPtr+";"); + cFile.println(" for(i = 0; i<((struct ArrayObject *) " + prefix + " )->___length___; i++ ) {"); + first=false; + } + printRefSwitch(fn, tmp, pdepth, childPtr, currPtr, state.transitionsTo(e), weakID); + } + } + if (!first) + cFile.println("}"); + } else { + //All other cases + String currPtr = "myPtr" + pdepth; + cFile.println(" struct ___Object___ * "+currPtr+";"); - //This will add the taint to the printout, there will be NO duplicates (checked above) - if(!created.isEmpty()) { - rblock.addInVarForDynamicCoarseConflictResolution(invar); - pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created)); + for(Effect e: et.getEffects(a)) { + if (!state.transitionsTo(e).isEmpty()) { + String childPtr = "((struct "+a.getType().getSafeSymbol()+" *)"+prefix +")->" + e.getField().getSafeSymbol(); + printRefSwitch(fn, tmp, pdepth, childPtr, currPtr, state.transitionsTo(e), weakID); + } } } } + + private void printRefSwitch(FlatNode fn, TempDescriptor tmp, int pdepth, String childPtr, String currPtr, Set transitions, int weakID) { + + for(SMFEState tr: transitions) { + if(tr.getRefCount() == 1) { //in-lineable case + //Don't need to update state counter since we don't care really if it's inlined... + cFile.println(" "+currPtr+"= (struct ___Object___ * ) " + childPtr + ";"); + cFile.println(" if (" + currPtr + " != NULL) { "); + + printAllocChecksInsideState(tr, fn, tmp, currPtr, pdepth+1, weakID); + + cFile.println(" }"); //break for internal switch and if + } else { //non-inlineable cases + cFile.println(" "+currPtr+"= (struct ___Object___ * ) " + childPtr + ";"); + cFile.println(" if("+queryAndAddToVisitedHashtable+"("+currPtr+","+tr.getID()+"))"); + cFile.println(" " + enqueueInC +"("+ currPtr + ", "+tr.getID()+");"); + } + } + } - private void traverseStallSite(FlatNode enterNode, TempDescriptor invar, ReachGraph rg) { - TypeDescriptor type = invar.getType(); - if(type == null || type.isPrimitive()) { - return; + + //FlatNode and TempDescriptor are what are used to make the taint + private void insertEntriesIntoHashStructureNew(FlatNode fn, TempDescriptor tmp, EffectsTable et, Alloc a, String prefix, int depth, int weakID) { + int index = 0; + boolean isRblock = (fn instanceof FlatSESEEnterNode); + if (isRblock) { + FlatSESEEnterNode fsese = (FlatSESEEnterNode) fn; + index = fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp); } - Hashtable created = new Hashtable(); - VariableNode varNode = rg.getVariableNodeNoMutation(invar); - Taint taint = getProperTaintForEnterNode(enterNode, varNode, globalEffects); - - if (taint == null) { - printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + enterNode.toString()); - return; - } - if(doneTaints.containsKey(taint)) - return; + String strrcr = isRblock ? "&record->rcrRecords[" + index + "], " : "NULL, "; + String tasksrc =isRblock ? "(SESEcommon *) record, ":"(SESEcommon *)(((INTPTR)record)|1LL), "; + + if(et.hasWriteConflict(a)) { + cFile.append(" int tmpkey" + depth + " = rcr_generateKey(" + prefix + ");\n"); + if (et.conflictDereference(a)) + cFile.append(" int tmpvar" + depth + " = rcr_WTWRITEBINCASE(allHashStructures[" + weakID + "], tmpkey" + depth + ", " + tasksrc + strrcr + index + ");\n"); + else + cFile.append(" int tmpvar" + depth + " = rcr_WRITEBINCASE(allHashStructures["+ weakID + "], tmpkey" + depth + ", " + tasksrc + strrcr + index + ");\n"); + } else if(et.hasReadConflict(a)) { + cFile.append(" int tmpkey" + depth + " = rcr_generateKey(" + prefix + ");\n"); + if (et.conflictDereference(a)) + cFile.append(" int tmpvar" + depth + " = rcr_WTREADBINCASE(allHashStructures[" + weakID + "], tmpkey" + depth + ", " + tasksrc + strrcr + index + ");\n"); + else + cFile.append(" int tmpvar" + depth + " = rcr_READBINCASE(allHashStructures["+ weakID + "], tmpkey" + depth + ", " + tasksrc + strrcr + index + ");\n"); + } + + if (et.hasReadConflict(a) || et.hasWriteConflict(a)) { + cFile.append("if (!(tmpvar" + depth + "&READYMASK)) totalcount--;\n"); + } + } + + private void setupOutputFiles(String buildir) throws FileNotFoundException { + cFile = new CodePrinter(new File(buildir + "RuntimeConflictResolver" + ".c")); + headerFile = new CodePrinter(new File(buildir + "RuntimeConflictResolver" + ".h")); - doneTaints.put(taint, traverserIDCounter++); - createConcreteGraph(effectsLookupTable, created, varNode, taint); + cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \"" + + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include "); + cFile.println("#include \"classdefs.h\""); + cFile.println("#include \"structdefs.h\""); + cFile.println("#include \"mlp_runtime.h\""); + cFile.println("#include \"RuntimeConflictResolver.h\""); + cFile.println("#include \"hashStructure.h\""); - if (!created.isEmpty()) { - pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created)); - } + headerFile.println("#ifndef __3_RCR_H_"); + headerFile.println("#define __3_RCR_H_"); } + //The official way to generate the name for a traverser call public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) { String flatname; - if(fn instanceof FlatSESEEnterNode) { + if(fn instanceof FlatSESEEnterNode) { //is SESE block flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier(); - } else { + } else { //is stallsite flatname = fn.toString(); } - return "traverse___" + invar.getSafeSymbol() + - removeInvalidChars(flatname) + "___("+varString+");"; - } - - public int getTraverserID(TempDescriptor invar, FlatNode fn) { - Tuple t=new Tuple(invar, fn); - if (idMap.containsKey(t)) - return idMap.get(t).intValue(); - int value=currentID++; - idMap.put(t, new Integer(value)); - return value; + return "traverse___" + invar.getSafeSymbol() + removeInvalidChars(flatname) + "___("+varString+");"; } public String removeInvalidChars(String in) { StringBuilder s = new StringBuilder(in); for(int i = 0; i < s.length(); i++) { - if(s.charAt(i) == ' ' || s.charAt(i) == '.' || s.charAt(i) == '='||s.charAt(i)=='['||s.charAt(i)==']') { + if(s.charAt(i) == ' ' || + s.charAt(i) == '.' || + s.charAt(i) == '=' || + s.charAt(i) == '[' || + s.charAt(i) == ']' ) { + s.deleteCharAt(i); i--; } @@ -322,18 +389,20 @@ public class RuntimeConflictResolver { return s.toString(); } - public void close() { - //prints out all generated code - for(TaintAndInternalHeapStructure ths: pendingPrintout) { - printCMethod(ths.nodesInHeap, ths.t); + public int getTraverserID(TempDescriptor invar, FlatNode fn) { + Pair t = new Pair(invar, fn); + if (idMap.containsKey(t)) { + return idMap.get(t).intValue(); } - - //Prints out the master traverser Invocation that'll call all other traverser + int value=currentID++; + idMap.put(t, new Integer(value)); + return value; + } + + public void close() { + //Prints out the master traverser Invocation that'll call all other traversers //based on traverserID - printMasterTraverserInvocation(); - printResumeTraverserInvocation(); - - //TODO this is only temporary, remove when thread local vars implemented. + printMasterTraverserInvocation(); createMasterHashTableArray(); // Adds Extra supporting methods @@ -347,46 +416,18 @@ public class RuntimeConflictResolver { headerFile.close(); } - //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 - private void buildEffectsLookupStructure(){ - effectsLookupTable = new EffectsTable(globalEffects, globalConflicts); - effectsLookupTable.runAnaylsis(); - enumerateHeaproots(); - } + private void printMasterTraverserInvocation() { + headerFile.println("int tasktraverse(SESEcommon * record);"); + cFile.println("int tasktraverse(SESEcommon * record) {"); + cFile.println(" if(!CAS(&record->rcrstatus,1,2)) {"); - private void runAllTraversals() { - for(TraversalInfo t: toTraverse) { - printDebug(javaDebug, "Running Traversal a traversal on " + t.f); - - if(t.f instanceof FlatSESEEnterNode) { - traverseSESEBlock((FlatSESEEnterNode)t.f, t.rg); - } else { - if(t.invar == null) { - System.out.println("RCR ERROR: Attempted to run a stall site traversal with NO INVAR"); - } else { - traverseStallSite(t.f, t.invar, t.rg); - } - } - - } - } + //release traverser reference...no traversal necessary + cFile.println("#ifndef OOO_DISABLE_TASKMEMPOOL"); + cFile.println(" RELEASE_REFERENCE_TO(record);"); + cFile.println("#endif"); - //TODO: This is only temporary, remove when thread local variables are functional. - private void createMasterHashTableArray() { - headerFile.println("void createAndFillMasterHashStructureArray();"); - cFile.println("void createAndFillMasterHashStructureArray() {\n" + - " rcr_createMasterHashTableArray("+weaklyConnectedHRCounter + ");"); - - for(int i = 0; i < weaklyConnectedHRCounter; i++) { - cFile.println(" allHashStructures["+i+"] = (HashStructure *) rcr_createHashtable("+num2WeaklyConnectedHRGroup.get(i).connectedHRs.size()+");"); - } - cFile.println("}"); - } - - private void printMasterTraverserInvocation() { - headerFile.println("\nint tasktraverse(SESEcommon * record);"); - cFile.println("\nint tasktraverse(SESEcommon * record) {"); + cFile.println(" return;"); + cFile.println(" }"); cFile.println(" switch(record->classID) {"); for(Iterator seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) { @@ -396,1095 +437,178 @@ public class RuntimeConflictResolver { cFile.println( " "+fsen.getSESErecordName()+" * rec=("+fsen.getSESErecordName()+" *) record;"); Vector invars=fsen.getInVarsForDynamicCoarseConflictResolution(); for(int i=0;i"+tmp+", rec", fsen)); + TempDescriptor tmp=invars.get(i); + + /* In some cases we don't want to a dynamic traversal if it is + * unlikely to increase parallelism...these are cases where we + * are just enabling a stall site to possible clear faster*/ + + boolean isValidToPrune=true; + for( FlatSESEEnterNode parentSESE: fsen.getParents() ) { + ConflictGraph graph = oooa.getConflictGraph(parentSESE); + if(graph!=null){ + String id = tmp + "_sese" + fsen.getPrettyIdentifier(); + ConflictNode node = graph.getId2cn().get(id); + isValidToPrune &= node.IsValidToPrune(); + } + } + + if(isValidToPrune){ + // if node is valid to prune examiner, + // also needs to turn off stall site examiners connected to this node + for( FlatSESEEnterNode parentSESE: fsen.getParents() ) { + ConflictGraph graph = oooa.getConflictGraph(parentSESE); + String id = tmp + "_sese" + fsen.getPrettyIdentifier(); + ConflictNode node = graph.getId2cn().get(id); + + for (Iterator iterator = node.getEdgeSet().iterator(); iterator.hasNext();) { + ConflictEdge edge = (ConflictEdge) iterator.next(); + if (edge.getVertexU() == node) { + if (edge.getVertexV().isStallSiteNode()) { + edge.getVertexV().setToBePruned(true); + } + } else { + if (edge.getVertexU().isStallSiteNode()) { + edge.getVertexU().setToBePruned(true); + } + } } + } + } + + if (i!=0) { + cFile.println(" if (record->rcrstatus!=0)"); + } + + if(globalState.NOSTALLTR && isValidToPrune) { + cFile.println(" /* " + getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen)+"*/"); + } else { + cFile.println(" " + getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen)); + } + } + //release traverser reference...traversal finished... + //executing thread will clean bins for us + cFile.println(" record->rcrstatus=0;"); + cFile.println("#ifndef OOO_DISABLE_TASKMEMPOOL"); + cFile.println(" RELEASE_REFERENCE_TO(record);"); + cFile.println("#endif"); 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( " " + this.getTraverserInvocation(t.getVar(), "rec->___obj___, rec", t.getStallSite())+";"); - cFile.println( " }"); - cFile.println(" break;"); - } - } - - cFile.println(" default:\n printf(\"Invalid SESE ID was passed in.\\n\");\n break;"); - - cFile.println(" }"); - cFile.println("}"); - } - - - //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) {"); - cFile.println(" switch(traverserID) {"); - - for(Taint t: doneTaints.keySet()) { - cFile.println(" case " + doneTaints.get(t)+ ":"); - if(t.isRBlockTaint()) { - cFile.println(" " + this.getTraverserInvocation(t.getVar(), "startingPtr, ("+t.getSESE().getSESErecordName()+" *)record", t.getSESE())); - } else if (t.isStallSiteTaint()){ - cFile.println("/* " + this.getTraverserInvocation(t.getVar(), "startingPtr, record", t.getStallSite())+"*/"); - } else { - System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t); - } - cFile.println(" break;"); - } - - if(RuntimeConflictResolver.cSideDebug) { - cFile.println(" default:\n printf(\"Invalid traverser ID %u was passed in.\\n\", traverserID);\n break;"); - } else { - cFile.println(" default:\n break;"); - } - - cFile.println(" }"); - cFile.println("}"); - } - - private void createConcreteGraph( - EffectsTable table, - Hashtable created, - VariableNode varNode, - Taint t) { - - // if table is null that means there's no conflicts, therefore we need not - // create a traversal - if (table == null) - return; - - Iterator possibleEdges = varNode.iteratorToReferencees(); - while (possibleEdges.hasNext()) { - RefEdge edge = possibleEdges.next(); - assert edge != null; - - ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true, false); - AllocSite rootKey = singleRoot.allocSite; - - if (!created.containsKey(rootKey)) { - created.put(rootKey, singleRoot); - createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table, t); - } - } - } - - //This code is the old way of generating an effects lookup table. - //The new way is to instantiate an EffectsGroup - @Deprecated - private Hashtable generateEffectsLookupTable( - Taint taint, Hashtable> effects, - Hashtable> conflicts) { - if(taint == null) - return null; - - Set localEffects = effects.get(taint); - Set 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 lookupTable = new Hashtable(); - - 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); - } + for(FlatNode stallsite: processedStallSites.keySet()) { - if(e.getField().getType().isPrimitive()) { - if(conflict) { - myEffects.addPrimitive(e, true); + TempDescriptor var = processedStallSites.get(stallsite); + Set seseSet=oooa.getPossibleExecutingRBlocks(stallsite); + boolean isValidToPrune=true; + for (Iterator iterator = seseSet.iterator(); iterator.hasNext();) { + FlatSESEEnterNode sese = (FlatSESEEnterNode) iterator.next(); + ConflictGraph graph = oooa.getConflictGraph(sese); + if(graph!=null){ + String id = var + "_fn" + stallsite.hashCode(); + ConflictNode node = graph.getId2cn().get(id); + isValidToPrune &= node.isTobePruned(); } } - else { - myEffects.addObjEffect(e, conflict); + + cFile.println( " case -" + getTraverserID(var, stallsite)+ ": {"); + cFile.println( " SESEstall * rec=(SESEstall*) record;"); + if(globalState.NOSTALLTR && isValidToPrune){ + cFile.println( " /*" + getTraverserInvocation(var, "rec->___obj___, rec", stallsite)+";*/"); + }else{ + cFile.println( " " + getTraverserInvocation(var, "rec->___obj___, rec", stallsite)+";"); } - } - - return lookupTable; - } - - // Plan is to add stuff to the tree depth-first sort of way. That way, we can - // propagate up conflicts - private void createHelper(ConcreteRuntimeObjNode curr, - Iterator edges, - Hashtable created, - EffectsTable table, - Taint taint) { - assert table != null; - AllocSite parentKey = curr.allocSite; - EffectsGroup currEffects = table.getEffects(parentKey, taint); - - if (currEffects == null || currEffects.isEmpty()) - return; - - //Handle Objects (and primitives if child is new) - if(currEffects.hasObjectEffects()) { - while(edges.hasNext()) { - RefEdge edge = edges.next(); - String field = edge.getField(); - CombinedObjEffects effectsForGivenField = currEffects.getObjEffect(field); - //If there are no effects, then there's no point in traversing this edge - if(effectsForGivenField != null) { - HeapRegionNode childHRN = edge.getDst(); - AllocSite childKey = childHRN.getAllocSite(); - boolean isNewChild = !created.containsKey(childKey); - ConcreteRuntimeObjNode child; - - if(isNewChild) { - child = new ConcreteRuntimeObjNode(childHRN, false, curr.isObjectArray()); - created.put(childKey, child); - } else { - child = created.get(childKey); - } - - curr.addObjChild(field, child, effectsForGivenField); - - if (effectsForGivenField.hasConflict()) { - child.hasPotentialToBeIncorrectDueToConflict = true; - propogateObjConflict(curr, child); - } - - if(effectsForGivenField.hasReadEffect) { - child.addReachableParent(curr); - - //If isNewChild, flag propagation will be handled at recursive call - if(isNewChild) { - createHelper(child, childHRN.iteratorToReferencees(), created, table, taint); - } else { - //This makes sure that all conflicts below the child is propagated up the referencers. - if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) { - propogatePrimConflict(child, child.enqueueToWaitingQueueUponConflict); - } - - if(child.decendantsObjConflict) { - propogateObjConflict(child, child.enqueueToWaitingQueueUponConflict); - } - } - } - } - } - } - - //Handles primitives - curr.primitiveConflictingFields = currEffects.primitiveConflictingFields; - if(currEffects.hasPrimitiveConflicts()) { - //Reminder: primitive conflicts are abstracted to object. - propogatePrimConflict(curr, curr); - } - } - - // This will propagate the conflict up the data structure. - private void propogateObjConflict(ConcreteRuntimeObjNode curr, HashSet pointsOfAccess) { - for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) { - if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer - (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) // case where referencer has never seen possible unresolved referencee below - { - referencer.decendantsObjConflict = true; - propogateObjConflict(referencer, pointsOfAccess); - } - } - } - - private void propogateObjConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) { - for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) { - if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer - (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) // case where referencer has never seen possible unresolved referencee below - { - referencer.decendantsObjConflict = true; - propogateObjConflict(referencer, pointOfAccess); - } - } - } - - private void propogatePrimConflict(ConcreteRuntimeObjNode curr, HashSet pointsOfAccess) { - for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) { - if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above - (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) - { - referencer.decendantsPrimConflict = true; - propogatePrimConflict(referencer, pointsOfAccess); - } - } - } - - private void propogatePrimConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) { - for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) { - if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above - (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) - { - referencer.decendantsPrimConflict = true; - propogatePrimConflict(referencer, pointOfAccess); - } - } - } - - - - /* - * This method generates a C method for every inset variable and rblock. - * - * The C method works by generating a large switch statement that will run the appropriate - * checking code for each object based on its allocation site. The switch statement is - * surrounded by a while statement which dequeues objects to be checked from a queue. An - * object is added to a queue only if it contains a conflict (in itself or in its referencees) - * and we came across it while checking through it's referencer. Because of this property, - * conflicts will be signaled by the referencer; the only exception is the inset variable which can - * signal a conflict within itself. - */ - - private void printCMethod(Hashtable 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; - - if(taint.isStallSiteTaint()) { - rBlock = taint.getStallSite().toString(); - } else if(taint.isRBlockTaint()) { - rBlock = taint.getSESE().getPrettyIdentifier(); - } else { - System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString()); - return; - } - - Hashtable cases = new Hashtable(); - - //Generate C cases - for (ConcreteRuntimeObjNode node : created.values()) { - printDebug(javaDebug, "Considering " + node.allocSite + " for traversal"); - if (!cases.containsKey(node.allocSite) && qualifiesForCaseStatement(node)) { - printDebug(javaDebug, "+\t" + node.allocSite + " qualified for case statement"); - addChecker(taint, node, cases, null, "ptr", 0); - } - } - //IMPORTANT: remember to change getTraverserInvocation if you change the line below - String methodName; - int index=-1; - - if (taint.isStallSiteTaint()) { - methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, SESEstall *record)"; - } else { - methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, "+taint.getSESE().getSESErecordName() +" *record)"; - FlatSESEEnterNode fsese=taint.getSESE(); - TempDescriptor tmp=taint.getVar(); - index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp); + cFile.println( " record->rcrstatus=0;"); + cFile.println( " }"); + cFile.println(" break;"); } - cFile.println(methodName + " {"); - headerFile.println(methodName + ";"); - cFile.println(" int totalcount=RUNBIAS;\n"); - if (taint.isStallSiteTaint()) { - cFile.println(" record->rcrRecords[0].count=RUNBIAS;\n"); - cFile.println(" record->rcrRecords[0].index=0;\n"); - } else { - cFile.println(" record->rcrRecords["+index+"].count=RUNBIAS;\n"); - cFile.println(" record->rcrRecords["+index+"].index=0;\n"); - } - - if(cSideDebug) { - cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");"); - } - - if(cases.size() == 0) { - cFile.println(" return;"); - } else { - //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. - cFile.println("struct ___Object___ * ptr = (struct ___Object___ *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable + "(ptr);\n do {"); - - cFile.println(" switch(ptr->allocsite) {"); - - for(AllocSite singleCase: cases.keySet()) - cFile.append(cases.get(singleCase)); - - cFile.println(" default:\n break; "); - cFile.println(" }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}"); - } - if (taint.isStallSiteTaint()) { - //need to add this - cFile.println(" if(atomic_sub_and_test(RUNBIAS-totalcount,&(record->rcrRecords[0].count))) {"); - cFile.println(" psem_give_tag(record->common.parentsStallSem, record->tag);"); - cFile.println(" BARRIER();"); - cFile.println(" record->common.rcrstatus=0;"); - cFile.println("}"); - } else { - cFile.println(" if(atomic_sub_and_test(RUNBIAS-totalcount,&(record->rcrRecords["+index+"].count))) {"); - cFile.println(" int flag=LOCKXCHG32(&(record->rcrRecords["+index+"].flag),0);"); - cFile.println(" if(flag) {"); - //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(" default:"); + cFile.println(" printf(\"Invalid SESE ID was passed in: %d.\\n\",record->classID);"); + cFile.println(" break;"); + cFile.println(" }"); cFile.println("}"); - cFile.flush(); - } - - /* - * 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. - */ - private void addChecker(Taint taint, - ConcreteRuntimeObjNode node, - Hashtable cases, - StringBuilder possibleContinuingCase, - 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(); - cases.put(node.allocSite, currCase); - currCase.append(" case " + node.getAllocationSite() + ": {\n"); - } - //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 - 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; - } - - int index=-1; - if (taint.isRBlockTaint()) { - FlatSESEEnterNode fsese=taint.getSESE(); - TempDescriptor tmp=taint.getVar(); - index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp); - } - - //Do call if we need it. - if(primConfWrite||objConfWrite) { - int heaprootNum = connectedHRHash.get(taint).id; - assert heaprootNum != -1; - int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node); - int traverserID = doneTaints.get(taint); - if (objConfRead) - currCase.append(" int tmpvar"+depth+"=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+");\n"); - else - currCase.append(" int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+");\n"); - } else if (primConfRead||objConfRead) { - int heaprootNum = connectedHRHash.get(taint).id; - assert heaprootNum != -1; - int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node); - int traverserID = doneTaints.get(taint); - if (objConfRead) - currCase.append(" int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+");\n"); - else - currCase.append(" int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+");\n"); - } - - if(primConfWrite||objConfWrite||primConfRead||objConfRead) { - currCase.append("if (!(tmpvar"+depth+"&READYMASK)) totalcount--;\n"); - currCase.append("if (!(tmpvar"+depth+"&SPEC)) {\n"); - currCase.append(" struct rcrRecord * rcrrec=&record->rcrRecords["+index+"];"); - currCase.append(" rcrrec->array[rcrrec->index++];"); - 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 - - ArrayList allocSitesWithProblems = node.getReferencedAllocSites(); - if(!allocSitesWithProblems.isEmpty()) { - //This is done with the assumption that an array of object stores pointers. - currCase.append("{\n int i;\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) { - // 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"); - } - currCase.append(" }\n "); - } - } - } - - if(qualifiesForCaseStatement(node)) { - currCase.append(" }\n break;\n"); - } } - private boolean qualifiesForCaseStatement(ConcreteRuntimeObjNode node) { - return ( - //insetVariable case - (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) || - //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())); - } + private void createMasterHashTableArray() { + headerFile.println("struct Hashtable_rcr ** createAndFillMasterHashStructureArray();"); + cFile.println("struct Hashtable_rcr ** createAndFillMasterHashStructureArray() {"); - //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 it = node.enqueueToWaitingQueueUponConflict.iterator(); + cFile.println(" struct Hashtable_rcr **table=rcr_createMasterHashTableArray("+totalWeakGroups + ");"); - 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); + for(int i = 0; i < totalWeakGroups; i++) { + cFile.println(" table["+i+"] = (struct Hashtable_rcr *) rcr_createHashtable();"); } + cFile.println(" return table;"); + cFile.println("}"); } - /* - 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 conflicts, AllocSite allocSite) { - currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); "); - } - */ - - private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var, - Hashtable> effects) { - Set taints = effects.keySet(); - for (Taint t : taints) { - FlatSESEEnterNode sese = t.getSESE(); - if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) { - return t; - } - } - return null; - } - - - private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var, - Hashtable> effects) { - Set taints = effects.keySet(); - for (Taint t : taints) { - FlatNode flatnode = t.getStallSite(); - if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) { - return t; - } - } - return null; - } - - private void printEffectsAndConflictsSets(Taint taint, Set localEffects, - Set 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); - } - } + public int getWeakID(TempDescriptor invar, FlatNode fn) { + //return weakMap.get(new Pair(invar, fn)).intValue(); + return 0; } - 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(); - - for(Taint t: connectedHRHash.keySet()) { - if(connectedHRHash.get(t).id == -1) { - WeaklyConectedHRGroup hg = connectedHRHash.get(t); - hg.id = weaklyConnectedHRCounter; - num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg); - weaklyConnectedHRCounter++; - } - } - } - - private void printoutTable(EffectsTable table) { - - System.out.println("==============EFFECTS TABLE PRINTOUT=============="); - for(AllocSite as: table.table.keySet()) { - System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID()); - - BucketOfEffects boe = table.table.get(as); - - if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) { - System.out.println("\t\tPotentially conflicting roots: "); - for(String key: boe.potentiallyConflictingRoots.keySet()) { - System.out.println("\t\t-Field: " + key); - System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key)); - } - } - for(Taint t: boe.taint2EffectsGroup.keySet()) { - System.out.println("\t\t For Taint " + t); - EffectsGroup eg = boe.taint2EffectsGroup.get(t); - - if(eg.hasPrimitiveConflicts()) { - System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : "); - for(String field: eg.primitiveConflictingFields.keySet()) { - System.out.print(field + " "); - } - System.out.println(); - } - for(String fieldKey: eg.myEffects.keySet()) { - CombinedObjEffects ce = eg.myEffects.get(fieldKey); - System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey); - System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict + - " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict + - " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict); - for(Effect ef: ce.originalEffects) { - System.out.println("\t" + ef); - } - } - } - - } - - } - - private class EffectsGroup { - Hashtable myEffects; - Hashtable primitiveConflictingFields; - - public EffectsGroup() { - myEffects = new Hashtable(); - primitiveConflictingFields = new Hashtable(); - } - public void addPrimitive(Effect e, boolean conflict) { - CombinedObjEffects effects; - if((effects = primitiveConflictingFields.get(e.getField().getSymbol())) == null) { - effects = new CombinedObjEffects(); - primitiveConflictingFields.put(e.getField().getSymbol(), effects); - } - effects.add(e, conflict); - } - - public void addObjEffect(Effect e, boolean conflict) { - CombinedObjEffects effects; - if((effects = myEffects.get(e.getField().getSymbol())) == null) { - effects = new CombinedObjEffects(); - myEffects.put(e.getField().getSymbol(), effects); - } - effects.add(e, conflict); - } - - public boolean isEmpty() { - return myEffects.isEmpty() && primitiveConflictingFields.isEmpty(); - } + public boolean hasEmptyTraversers(FlatSESEEnterNode fsen) { + boolean hasEmpty = true; - public boolean hasPrimitiveConflicts(){ - return !primitiveConflictingFields.isEmpty(); - } - - public CombinedObjEffects getPrimEffect(String field) { - return primitiveConflictingFields.get(field); + Set children = fsen.getChildren(); + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + FlatSESEEnterNode child = (FlatSESEEnterNode) iterator.next(); + hasEmpty &= child.getInVarsForDynamicCoarseConflictResolution().size() == 0; } + return hasEmpty; + } - public boolean hasObjectEffects() { - return !myEffects.isEmpty(); - } - - public CombinedObjEffects getObjEffect(String field) { - return myEffects.get(field); - } - } - //Is the combined effects for all effects with the same affectedAllocSite and field - private class CombinedObjEffects { - ArrayList originalEffects; - - public boolean hasReadEffect; - public boolean hasWriteEffect; - public boolean hasStrongUpdateEffect; - - public boolean hasReadConflict; - public boolean hasWriteConflict; - public boolean hasStrongUpdateConflict; - - - public CombinedObjEffects() { - originalEffects = new ArrayList(); - - hasReadEffect = false; - hasWriteEffect = false; - hasStrongUpdateEffect = false; - - hasReadConflict = false; - hasWriteConflict = false; - hasStrongUpdateConflict = false; - } - - public boolean add(Effect e, boolean conflict) { - if(!originalEffects.add(e)) - return false; - - switch(e.getType()) { - case Effect.read: - hasReadEffect = true; - hasReadConflict = conflict; - break; - case Effect.write: - hasWriteEffect = true; - hasWriteConflict = conflict; - break; - case Effect.strongupdate: - hasStrongUpdateEffect = true; - hasStrongUpdateConflict = conflict; - break; - default: - System.out.println("RCR ERROR: An Effect Type never seen before has been encountered"); - assert false; - break; - } - return true; - } - - public boolean hasConflict() { - return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict; - } - } - - //This will keep track of a reference - private class ObjRef { - String field; - int allocSite; - CombinedObjEffects myEffects; - - //This keeps track of the parent that we need to pass by inorder to get - //to the conflicting child (if there is one). - ConcreteRuntimeObjNode child; - - public ObjRef(String fieldname, - ConcreteRuntimeObjNode ref, - CombinedObjEffects myEffects) { - field = fieldname; - allocSite = ref.getAllocationSite(); - child = ref; - - this.myEffects = myEffects; - } - - public boolean hasConflictsDownThisPath() { - return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict(); - } - - public boolean hasDirectObjConflict() { - return myEffects.hasConflict(); - } - } - - private class ConcreteRuntimeObjNode { - ArrayList objectRefs; - Hashtable primitiveConflictingFields; - HashSet parentsWithReadToNode; - HashSet parentsThatWillLeadToConflicts; - //this set keeps track of references down the line that need to be enqueued if traverser is "paused" - HashSet enqueueToWaitingQueueUponConflict; - boolean decendantsPrimConflict; - boolean decendantsObjConflict; - boolean hasPotentialToBeIncorrectDueToConflict; - boolean isInsetVar; - boolean isArrayElement; - AllocSite allocSite; - HeapRegionNode original; - - public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar, boolean isArrayElement) { - objectRefs = new ArrayList(); - primitiveConflictingFields = null; - parentsThatWillLeadToConflicts = new HashSet(); - parentsWithReadToNode = new HashSet(); - enqueueToWaitingQueueUponConflict = new HashSet(); - allocSite = me.getAllocSite(); - original = me; - isInsetVar = isInVar; - decendantsPrimConflict = false; - decendantsObjConflict = false; - hasPotentialToBeIncorrectDueToConflict = false; - this.isArrayElement = isArrayElement; - } - - public void addReachableParent(ConcreteRuntimeObjNode curr) { - parentsWithReadToNode.add(curr); - } - - @Override - public boolean equals(Object obj) { - return original.equals(obj); - } - - public int getAllocationSite() { - return allocSite.getUniqueAllocSiteID(); - } - - public int getNumOfReachableParents() { - return parentsThatWillLeadToConflicts.size(); - } - - public boolean hasPrimitiveConflicts() { - return primitiveConflictingFields != null && !primitiveConflictingFields.isEmpty(); - } - - public boolean decendantsConflict() { - return decendantsPrimConflict || decendantsObjConflict; - } - - - //returns true if at least one of the objects in points of access has been added - public boolean addPossibleWaitingQueueEnqueue(HashSet pointsOfAccess) { - boolean addedNew = false; - for(ConcreteRuntimeObjNode dec: pointsOfAccess) { - if(dec != null && dec != this){ - addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec); + //Simply rehashes and combines all effects for a AffectedAllocSite + Field. + private class EffectsTable { + private Hashtable> table; + SMFEState state; + + public EffectsTable(SMFEState state) { + table = new Hashtable>(); + this.state=state; + for(Effect e: state.getEffectsAllowed()) { + Set eg; + if((eg = table.get(e.getAffectedAllocSite())) == null) { + eg = new HashSet(); + table.put(e.getAffectedAllocSite(), eg); } + eg.add(e); } - - return addedNew; } - public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) { - if(pointOfAccess != null && pointOfAccess != this){ - return enqueueToWaitingQueueUponConflict.add(pointOfAccess); + public boolean conflictDereference(Alloc a) { + for(Effect e:getEffects(a)) { + if (!state.transitionsTo(e).isEmpty()&&state.getConflicts().contains(e)) + return true; } - return false; } - public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) { - ObjRef ref = new ObjRef(field, child, ce); - objectRefs.add(ref); - } - - public boolean isObjectArray() { - return original.getType().isArray() && !original.getType().isPrimitive() && !original.getType().isImmutable(); - } - - public boolean canBeArrayElement() { - return isArrayElement; - } - - public ArrayList getReferencedAllocSites() { - ArrayList list = new ArrayList(); - - for(ObjRef r: objectRefs) { - if(r.hasDirectObjConflict() || (r.child.parentsWithReadToNode.contains(this) && r.hasConflictsDownThisPath())) { - list.add(r.allocSite); - } - } - - return list; - } - - public String toString() { - return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() + - " decCon="+decendantsObjConflict+ - " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size(); - } - } - - private class EffectsTable { - private Hashtable table; - - public EffectsTable(Hashtable> effects, - Hashtable> conflicts) { - table = new Hashtable(); - - // rehash all effects (as a 5-tuple) by their affected allocation site - for (Taint t : effects.keySet()) { - Set localConflicts = conflicts.get(t); - for (Effect e : effects.get(t)) { - BucketOfEffects bucket; - if ((bucket = table.get(e.getAffectedAllocSite())) == null) { - bucket = new BucketOfEffects(); - table.put(e.getAffectedAllocSite(), bucket); - } - printDebug(javaDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts); - bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false); - } - } - } - - public EffectsGroup getEffects(AllocSite parentKey, Taint taint) { - //This would get the proper bucket of effects and then get all the effects - //for a parent for a specific taint - try { - return table.get(parentKey).taint2EffectsGroup.get(taint); - } - catch (NullPointerException e) { - return null; + public boolean hasWriteConflict(Alloc a) { + for(Effect e:getEffects(a)) { + if (e.isWrite() && state.getConflicts().contains(e)) + return true; } + return false; } - // Run Analysis will walk the data structure and figure out the weakly - // connected heap roots. - public void runAnaylsis() { - if(javaDebug) { - printoutTable(this); + public boolean hasReadConflict(Alloc a) { + for(Effect e:getEffects(a)) { + if (e.isRead() && state.getConflicts().contains(e)) + return true; } - - //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 - if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){ - for(String field: effects.potentiallyConflictingRoots.keySet()){ - ArrayList taints = effects.potentiallyConflictingRoots.get(field); - //For simplicity, we just create a new group and add everything to it instead of - //searching through all of them for the largest group and adding everyone in. - WeaklyConectedHRGroup group = new WeaklyConectedHRGroup(); - group.add(taints); //This will automatically add the taint to the connectedHRhash - } - } - } - } - } - - private class WeaklyConectedHRGroup { - HashSet connectedHRs; - //This is to keep track of unique waitingQueue positions for each allocsite. - Hashtable allocSiteToWaitingQueueMap; - int waitingQueueCounter; - int id; - - public WeaklyConectedHRGroup() { - connectedHRs = new HashSet(); - id = -1; //this will be later modified - waitingQueueCounter = 0; - allocSiteToWaitingQueueMap = new Hashtable(); - } - - public void add(ArrayList list) { - for(Taint t: list) { - this.add(t); - } - } - - public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) { - if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) { - return allocSiteToWaitingQueueMap.get(node.allocSite); - } - else { - allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter); - return waitingQueueCounter++; - } - } - - public void add(Taint t) { - connectedHRs.add(t); - WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t); - connectedHRHash.put(t, this); //put new group into hash - //If the taint was already in another group, move all its buddies over. - if(oldGroup != this && oldGroup != null) { - Iterator it = oldGroup.connectedHRs.iterator(); - Taint relatedTaint; - - while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) { - this.add(relatedTaint); - } - } - } - } - - //This is a class that stores all the effects for an affected allocation site - //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed - //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code - //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string - //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that - //field. - private class BucketOfEffects { - // This table is used for lookup while creating the traversal. - Hashtable taint2EffectsGroup; - - //This table is used to help identify weakly connected groups: Contains ONLY - //conflicting effects AND is only initialized when needed - //String stores the field - Hashtable> potentiallyConflictingRoots; - - public BucketOfEffects() { - taint2EffectsGroup = new Hashtable(); + return false; } - public void add(Taint t, Effect e, boolean conflict) { - EffectsGroup effectsForGivenTaint; - - if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) { - effectsForGivenTaint = new EffectsGroup(); - taint2EffectsGroup.put(t, effectsForGivenTaint); - } - - if (e.getField().getType().isPrimitive()) { - if (conflict) { - effectsForGivenTaint.addPrimitive(e, true); - } - } else { - effectsForGivenTaint.addObjEffect(e, conflict); - } - - if(conflict) { - if(potentiallyConflictingRoots == null) { - potentiallyConflictingRoots = new Hashtable>(); - } - - ArrayList taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol()); - if(taintsForField == null) { - taintsForField = new ArrayList(); - potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField); - } - - if(!taintsForField.contains(t)) { - taintsForField.add(t); - } - } - } - } - - private class TaintAndInternalHeapStructure { - public Taint t; - public Hashtable nodesInHeap; - - public TaintAndInternalHeapStructure(Taint taint, Hashtable nodesInHeap) { - t = taint; - this.nodesInHeap = nodesInHeap; - } - } - - private class TraversalInfo { - public FlatNode f; - public ReachGraph rg; - public TempDescriptor invar; - - public TraversalInfo(FlatNode fn, ReachGraph g) { - f = fn; - rg =g; - invar = null; + public Set getEffects(Alloc a) { + return table.get(a); } - public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) { - f = fn; - rg =rg2; - invar = tempDesc; + public Set getAllAllocs() { + return table.keySet(); } } }