Robust/src/IR/Flat/RuntimeConflictResolver.java

   1 package IR.Flat;
   2 import java.io.File;
   3 import java.io.FileNotFoundException;
   4 import java.util.ArrayList;
   5 import java.util.HashSet;
   6 import java.util.Hashtable;
   7 import java.util.Iterator;
   8 import java.util.Set;
   9 import java.util.Vector;
  10 import Util.Pair;
  11 import Analysis.Disjoint.*;
  12 import IR.State;
  13 import IR.TypeDescriptor;
  14 import Analysis.OoOJava.ConflictGraph;
  15 import Analysis.OoOJava.ConflictNode;
  16 import Analysis.OoOJava.OoOJavaAnalysis;
  17 import Analysis.OoOJava.SESELock;
  18 import Analysis.OoOJava.WaitingElement;
  19 import Analysis.OoOJava.CodePlan;
  20 import Util.CodePrinter;
  21
  22 /* An instance of this class manages all OoOJava coarse-grained runtime conflicts
  23  * by generating C-code to either rule out the conflict at runtime or resolve one.
  24  *
  25  * How to Use:
  26  * 1) Instantiate singleton object (String input is to specify output dir)
  27  * 2) Call setGlobalEffects setGlobalEffects(Hashtable<Taint, Set<Effect>> ) ONCE
  28  * 3) Input SESE blocks, for each block:
  29  *    3a) call addToTraverseToDoList(FlatSESEEnterNode , ReachGraph , Hashtable<Taint, Set<Effect>>) for the seseBlock
  30  *    3b) call String getTraverserInvocation(TempDescriptor, String, FlatSESEEnterNode) to get the name of the traverse method in C
  31  * 4) Call void close()
  32  * Note: All computation is done upon closing the object. Steps 1-3 only input data
  33  */
  34 public class RuntimeConflictResolver {
  35   //Shows weakly connected heaproots and which allocation sites were considered for traversal
  36   private boolean generalDebug = false;
  37
  38   //Prints out effects passed in, internal representation of effects, and internal representation of reach graph
  39   private boolean verboseDebug = false;
  40
  41   private CodePrinter headerFile, cFile;
  42   private static final String hashAndQueueCFileDir = "oooJava/";
  43
  44   //This keeps track of taints we've traversed to prevent printing duplicate traverse functions
  45   //The Integer keeps track of the weakly connected group it's in (used in enumerateHeapRoots)
  46   private Hashtable<Taint, Integer> doneTaints;
  47   private Hashtable<Pair, Integer> idMap=new Hashtable<Pair,Integer>();
  48   private Hashtable<Pair, Integer> weakMap=new Hashtable<Pair,Integer>();
  49   private Hashtable<Taint, Set<Effect>> globalEffects;
  50   private Hashtable<Taint, Set<Effect>> globalConflicts;
  51
  52   private ArrayList<TraversalInfo> traverserTODO;
  53
  54   // Hashtable provides fast access to heaproot # lookups
  55   private Hashtable<Taint, WeaklyConectedHRGroup> connectedHRHash;
  56   private ArrayList<WeaklyConectedHRGroup> num2WeaklyConnectedHRGroup;
  57   private int traverserIDCounter;
  58   public int currentID=1;
  59   private int weaklyConnectedHRCounter;
  60   private ArrayList<TaintAndInternalHeapStructure> pendingPrintout;
  61   private EffectsTable effectsLookupTable;
  62   private OoOJavaAnalysis oooa;
  63   private State state;
  64
  65   // initializing variables can be found in printHeader()
  66   private static final String getAllocSiteInC = "->allocsite";
  67   private static final String queryVistedHashtable = "hashRCRInsert";
  68   private static final String addToQueueInC = "enqueueRCRQueue(";
  69   private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
  70   private static final String clearQueue = "resetRCRQueue()";
  71   // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
  72   private static final String mallocVisitedHashtable = "hashRCRCreate(128, 0.75)";
  73   private static final String deallocVisitedHashTable = "hashRCRDelete()";
  74   private static final String resetVisitedHashTable = "hashRCRreset()";
  75
  76   /*
  77    * Basic Strategy:
  78    * 1) Get global effects and conflicts
  79    * 2) Create a hash structure (EffectsTable) to manage effects (hashed by affected Allocsite, then taint, then field)
  80    *     2a) Use Effects to verify we can access something (reads)
  81    *     2b) Use conflicts to mark conflicts (read/write/strongupdate)
  82    *     2c) At second level of hash, store Heaproots that can cause conflicts at the field
  83    * 3) Walk hash structure to identify and enumerate weakly connected groups
  84    * 4) Build internal representation of the rgs (pruned)
  85    * 5) Print c methods by walking internal representation
  86    */
  87   public RuntimeConflictResolver(String buildir, OoOJavaAnalysis oooa, Hashtable<Taint, Set<Effect>> globalEffects, State state)
  88   throws FileNotFoundException {
  89     this.oooa=oooa;
  90     this.state=state;
  91     this.generalDebug = state.RCR_DEBUG || state.RCR_DEBUG_VERBOSE;
  92     this.verboseDebug = state.RCR_DEBUG_VERBOSE;
  93
  94     doneTaints = new Hashtable<Taint, Integer>();
  95     connectedHRHash = new Hashtable<Taint, WeaklyConectedHRGroup>();
  96     pendingPrintout = new ArrayList<TaintAndInternalHeapStructure>();
  97     traverserTODO = new ArrayList<TraversalInfo>();
  98     globalConflicts = new Hashtable<Taint, Set<Effect>>();
  99     //Note: globalEffects is not instantiated since it'll be passed in whole while conflicts comes in chunks
 100
 101     traverserIDCounter = 1;
 102     weaklyConnectedHRCounter = 0;
 103
 104     //note: the order below MATTERS
 105     setupOutputFiles(buildir);
 106     setGlobalEffects(globalEffects);
 107     getAllTasksAndConflicts();
 108     buildEffectsLookupStructure();
 109     createInternalGraphs();
 110     //After the internal graphs are created, we can print,
 111     //but printing is done in close();
 112   }
 113
 114   private void setupOutputFiles(String buildir) throws FileNotFoundException {
 115     cFile = new CodePrinter(new File(buildir + "RuntimeConflictResolver" + ".c"));
 116     headerFile = new CodePrinter(new File(buildir + "RuntimeConflictResolver" + ".h"));
 117
 118     cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
 119         + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>");
 120     cFile.println("#include \"classdefs.h\"");
 121     cFile.println("#include \"structdefs.h\"");
 122     cFile.println("#include \"mlp_runtime.h\"");
 123     cFile.println("#include \"RuntimeConflictResolver.h\"");
 124     cFile.println("#include \"hashStructure.h\"");
 125
 126     headerFile.println("#ifndef __3_RCR_H_");
 127     headerFile.println("#define __3_RCR_H_");
 128   }
 129
 130   private void setGlobalEffects(Hashtable<Taint, Set<Effect>> effects) {
 131     globalEffects = effects;
 132
 133     if(verboseDebug) {
 134       System.out.println("============EFFECTS LIST AS PASSED IN============");
 135       for(Taint t: globalEffects.keySet()) {
 136         System.out.println("For Taint " + t);
 137         for(Effect e: globalEffects.get(t)) {
 138           System.out.println("\t" + e);
 139         }
 140       }
 141       System.out.println("====================END  LIST====================");
 142     }
 143   }
 144
 145   private void getAllTasksAndConflicts() {
 146     FlatSESEEnterNode fsen;
 147     FlatSESEEnterNode parentSESE;
 148     ConflictGraph conflictGraph;
 149     ReachGraph rg;
 150     Hashtable<Taint, Set<Effect>> conflicts;
 151     DisjointAnalysis disjointAnaylsis = oooa.getDisjointAnalysis();
 152
 153     //Go through the SESE's
 154     printDebug(generalDebug, "======================SESE's======================");
 155     for(Iterator<FlatSESEEnterNode> seseit = oooa.getAllSESEs().iterator();seseit.hasNext();) {
 156       fsen = seseit.next();
 157
 158       if ( fsen.getParents().size() > 0                                                           &&
 159           (parentSESE     = (FlatSESEEnterNode) fsen.getParents().iterator().next())   != null &&
 160           (conflictGraph  = oooa.getConflictGraph(parentSESE))                            != null &&
 161           (conflicts      = conflictGraph.getConflictEffectSet(fsen))                     != null &&
 162           (rg             = disjointAnaylsis.getEnterReachGraph(fsen))                    != null ){
 163
 164         addToTraverseToDoList(fsen, rg, conflicts, conflictGraph);
 165       }
 166     }
 167     printDebug(generalDebug, "==================END SESE LIST==================");
 168
 169
 170     // Go through the stall sites
 171     for(Iterator<FlatNode> codeit = oooa.getNodesWithPlans().iterator();codeit.hasNext();){
 172       FlatNode fn = codeit.next();
 173       CodePlan cp = oooa.getCodePlan(fn);
 174       fsen = cp.getCurrentSESE();
 175
 176       if(  fsen.getParents().size() != 0                                                     &&
 177           (conflictGraph  = oooa.getConflictGraph(fsen))                                != null &&
 178           (conflicts      = conflictGraph.getConflictEffectSet(fn))                     != null &&
 179           (rg             = disjointAnaylsis.getEnterReachGraph(fn))                    != null ){
 180
 181         Set<SESELock> seseLockSet = oooa.getLockMappings(conflictGraph);
 182         Set<WaitingElement> waitingElementSet =
 183             conflictGraph.getStallSiteWaitingElementSet(fn, seseLockSet);
 184
 185         if (waitingElementSet.size() > 0) {
 186           for (Iterator<WaitingElement> iterator = waitingElementSet.iterator(); iterator.hasNext();) {
 187
 188             WaitingElement waitingElement = (WaitingElement) iterator.next();
 189             addToTraverseToDoList(fn, waitingElement.getTempDesc(), rg, conflicts);
 190           }
 191         }
 192       }
 193     }
 194   }
 195
 196   public void addToTraverseToDoList(FlatSESEEnterNode rblock,
 197                                     ReachGraph rg,
 198                                     Hashtable<Taint, Set<Effect>> conflicts,
 199                                     ConflictGraph conflictGraph) {
 200
 201     traverserTODO.add(new TraversalInfo(rblock, rg));
 202     addToGlobalConflicts(conflicts);
 203
 204     if(generalDebug) {
 205       System.out.println(rblock);
 206       System.out.println(rblock.getParents());
 207       System.out.println("CG=" + conflictGraph);
 208       if(verboseDebug)
 209           rg.writeGraph("RCR_RG_SESE_DEBUG"+removeInvalidChars(rblock.getPrettyIdentifier()));
 210     }
 211   }
 212
 213   public void addToTraverseToDoList(FlatNode fn,
 214                                     TempDescriptor tempDesc,
 215                                     ReachGraph rg,
 216                                     Hashtable<Taint, Set<Effect>> conflicts)
 217   {
 218     traverserTODO.add(new TraversalInfo(fn, rg, tempDesc));
 219     addToGlobalConflicts(conflicts);
 220
 221     if (verboseDebug)
 222       rg.writeGraph("RCR_RG_STALLSITE_DEBUG"+removeInvalidChars(fn.toString()));
 223   }
 224
 225   private void addToGlobalConflicts(Hashtable<Taint, Set<Effect>> conflicts) {
 226     for(Taint t: conflicts.keySet()) {
 227       if(globalConflicts.containsKey(t)) {
 228         globalConflicts.get(t).addAll(conflicts.get(t));
 229       } else {
 230         globalConflicts.put(t, conflicts.get(t));
 231       }
 232     }
 233   }
 234
 235   //Builds Effects Table and runs the analysis on them to get weakly connected HRs
 236   //SPECIAL NOTE: Only runs after we've taken all the conflicts and effects (via getAllTasksAndConflicts)
 237   private void buildEffectsLookupStructure(){
 238     effectsLookupTable = new EffectsTable(globalEffects, globalConflicts);
 239     effectsLookupTable.runAnalysis();
 240     enumerateHeaproots();
 241   }
 242
 243   private void createInternalGraphs() {
 244     for(TraversalInfo t: traverserTODO) {
 245       printDebug(generalDebug, "Running Traversal on " + t.f);
 246
 247       //Runs stallsite graph creation
 248       if(t.isStallSite()) {
 249         assert t.invar != null;
 250         createTraversalGraph(t.f, t.invar, t.rg);
 251       }
 252       //runs rblock graph creation
 253       else {
 254         FlatSESEEnterNode rblock = (FlatSESEEnterNode)t.f;
 255
 256         for (TempDescriptor invar : rblock.getInVarSet()) {
 257           createTraversalGraph(rblock, invar, t.rg);
 258         }
 259       }
 260     }
 261   }
 262
 263   //This method creates an pruned version of the reach graph using effects
 264   //The graph ultimately steers the the runtime traverser and is used to generate output code
 265   private void createTraversalGraph(FlatNode fn, TempDescriptor invar, ReachGraph rg) {
 266     //"created" maps allocation site to RuntimeObjNode; keeps track of which parts of rg are visited.
 267     Hashtable<Integer, ConcreteRuntimeObjNode> created;
 268     VariableNode varNode = rg.getVariableNodeNoMutation(invar);
 269     Taint taint = getProperTaintForEnterNode(fn, varNode);
 270
 271     if (taint == null || invar.getType() == null || isReallyAPrimitive(invar.getType())) {
 272       printDebug(generalDebug, "Site " +varNode.getTempDescriptor().getSafeSymbol() + fn.toString() + " not traversed");
 273       return;
 274     }
 275
 276     //If already done, don't need to redoit.
 277     if(doneTaints.containsKey(taint))
 278       return;
 279
 280     created = new Hashtable<Integer, ConcreteRuntimeObjNode>(); //Pass 0: Create empty graph
 281     createPrunedGraph(created, varNode, taint);                 //Pass 1: Create graph pruned graph
 282     propagateConflicts(created);                                                                //Pass 2: Flag referencers with conflicts
 283
 284     //If there are valid nodes, add to printout queue
 285     if (!created.isEmpty()) {
 286       pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
 287
 288       //IF is SESE we need to tell the EnterNode that it has a traverser waiting for it.
 289       if(fn instanceof FlatSESEEnterNode) {
 290         for(Iterator<ConcreteRuntimeObjNode> it=created.values().iterator();it.hasNext();) {
 291           ConcreteRuntimeObjNode obj=it.next();
 292           if (obj.hasConflict() || obj.hasPrimitiveConflicts()){
 293             ((FlatSESEEnterNode) fn).addInVarForDynamicCoarseConflictResolution(invar);
 294             break;
 295           }
 296         }
 297       }
 298     }
 299
 300     doneTaints.put(taint, traverserIDCounter++);
 301   }
 302
 303   //This is Pass 1 of internal graph creation.
 304         private void createPrunedGraph(
 305                         Hashtable<Integer, ConcreteRuntimeObjNode> created,
 306                         VariableNode varNode,
 307                         Taint t) {
 308                 // For every inset HRN, create a graph node, and run a DFT (buildPrunedGraphFromRG)
 309                 Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
 310                 while (possibleEdges.hasNext()) {
 311                         RefEdge edge = possibleEdges.next();
 312                         assert edge != null;
 313
 314                         ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true);
 315                         int rootKey = singleRoot.allocSite.getUniqueAllocSiteID();
 316
 317                         if (!created.containsKey(rootKey)) {
 318                                 created.put(rootKey, singleRoot);
 319                                 buildPrunedGraphFromRG(singleRoot, edge.getDst().iteratorToReferencees(), created, t);
 320                         }
 321                 }
 322         }
 323
 324   //Performs Depth First Traversal on the ReachGraph to build an
 325   //internal representation of it. It prunes ptrs not reachable
 326   //by read Effects and stores in each node the effects by it.
 327   private void buildPrunedGraphFromRG(  ConcreteRuntimeObjNode curr,
 328                             Iterator<RefEdge> edges,
 329                             Hashtable<Integer, ConcreteRuntimeObjNode> created,
 330                             Taint taint) {
 331     EffectsGroup currEffects = effectsLookupTable.getEffects(curr.allocSite, taint);
 332
 333     if (currEffects == null || currEffects.isEmpty())
 334       return;
 335
 336     //Update parent flags for primitive accesses
 337     curr.primConfRead  |= currEffects.primConfRead;
 338     curr.primConfWrite |= currEffects.primConfWrite;
 339
 340     //Handle non-primitive references by creating a node for each reference
 341     //and updating the parent's conflict flags. If child is reachable through
 342     //a read effect, it recursively calls this function.
 343     if(currEffects.hasObjectEffects()) {
 344       while(edges.hasNext()) {
 345         RefEdge edge = edges.next();
 346         String field = edge.getField();
 347         CombinedEffects effectsForGivenField = currEffects.getObjEffect(field);
 348
 349         //If there are no effects, then there's no point in traversing this edge
 350         if(effectsForGivenField != null) {
 351           HeapRegionNode childHRN = edge.getDst();
 352           int childKey = childHRN.getAllocSite().getUniqueAllocSiteID();
 353           boolean isNewChild = !created.containsKey(childKey);
 354           ConcreteRuntimeObjNode child;
 355
 356           if(isNewChild) {
 357             child = new ConcreteRuntimeObjNode(childHRN, false);        //false = not inset
 358             created.put(childKey, child);
 359           } else {
 360             child = created.get(childKey);
 361           }
 362
 363           ObjRef reference = new ObjRef(field, curr, child, effectsForGivenField);
 364           curr.addReferencee(field, reference);
 365
 366           //update parent flags
 367           curr.objConfRead   |= effectsForGivenField.hasReadConflict;
 368           curr.objConfWrite  |= effectsForGivenField.hasWriteConflict;
 369
 370           //Update flags and recurse
 371           if(effectsForGivenField.hasReadEffect) {
 372             child.hasPotentialToBeIncorrectDueToConflict |= effectsForGivenField.hasReadConflict;
 373             child.addReferencer(reference);
 374
 375             if(isNewChild) {
 376               buildPrunedGraphFromRG(child, childHRN.iteratorToReferencees(), created, taint);
 377             }
 378           }
 379         }
 380       }
 381     }
 382   }
 383
 384   //Performs a reverse traversal from the conflict nodes up to the
 385   //inset variables and sets conflict flags on inner nodes.
 386   private void propagateConflicts(Hashtable<Integer, ConcreteRuntimeObjNode> created) {
 387     for(ConcreteRuntimeObjNode node: created.values()) {
 388       if(node.hasConflict()) {
 389         markReferencers(node, node.objConfRead || node.objConfWrite, node.primConfRead || node.primConfWrite);
 390       }
 391     }
 392   }
 393
 394   private void markReferencers(ConcreteRuntimeObjNode node, boolean ObjConf, boolean PrimConf) {
 395     for(ObjRef ref: node.referencers) {
 396       //if not already marked or data does not match
 397       if(!ref.reachesConflict ||
 398           (ObjConf  && !ref.parent.descendantsObjConflict) ||
 399           (PrimConf && !ref.parent.descendantsPrimConflict)) {
 400
 401         ref.parent.descendantsObjConflict  |= ObjConf;
 402         ref.parent.descendantsPrimConflict |= PrimConf;
 403         ref.reachesConflict = true;
 404         markReferencers(ref.parent, ObjConf, PrimConf);
 405       }
 406     }
 407   }
 408
 409   //This extends a tempDescriptor's isPrimitive test by also excluding primitive arrays.
 410   private boolean isReallyAPrimitive(TypeDescriptor type) {
 411     return (type.isPrimitive() && !type.isArray());
 412   }
 413
 414   //The official way to generate the name for a traverser call
 415   public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
 416     String flatname;
 417     if(fn instanceof FlatSESEEnterNode) {  //is SESE block
 418       flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
 419     } else {  //is stallsite
 420       flatname = fn.toString();
 421     }
 422
 423     return "traverse___" + invar.getSafeSymbol() +
 424     removeInvalidChars(flatname) + "___("+varString+");";
 425   }
 426
 427   public String removeInvalidChars(String in) {
 428     StringBuilder s = new StringBuilder(in);
 429     for(int i = 0; i < s.length(); i++) {
 430       if(s.charAt(i) == ' ' ||
 431          s.charAt(i) == '.' ||
 432          s.charAt(i) == '=' ||
 433          s.charAt(i) == '[' ||
 434          s.charAt(i) == ']'    ) {
 435
 436         s.deleteCharAt(i);
 437         i--;
 438       }
 439     }
 440     return s.toString();
 441   }
 442
 443   public int getWeakID(TempDescriptor invar, FlatNode fn) {
 444     return weakMap.get(new Pair(invar, fn)).intValue();
 445   }
 446
 447   public int getTraverserID(TempDescriptor invar, FlatNode fn) {
 448     Pair t=new Pair(invar, fn);
 449     if (idMap.containsKey(t))
 450       return idMap.get(t).intValue();
 451     int value=currentID++;
 452     idMap.put(t, new Integer(value));
 453     return value;
 454   }
 455
 456
 457   public void close() {
 458     //prints the traversal code
 459     for(TaintAndInternalHeapStructure ths: pendingPrintout) {
 460       printCMethod(ths.nodesInHeap, ths.t);
 461     }
 462
 463     //Prints out the master traverser Invocation that'll call all other traversers
 464     //based on traverserID
 465     printMasterTraverserInvocation();
 466     createMasterHashTableArray();
 467
 468     // Adds Extra supporting methods
 469     cFile.println("void initializeStructsRCR() {\n  " + mallocVisitedHashtable + ";\n  " + clearQueue + ";\n}");
 470     cFile.println("void destroyRCR() {\n  " + deallocVisitedHashTable + ";\n}");
 471
 472     headerFile.println("void initializeStructsRCR();\nvoid destroyRCR();");
 473     headerFile.println("#endif\n");
 474
 475     cFile.close();
 476     headerFile.close();
 477   }
 478
 479   private void createMasterHashTableArray() {
 480     headerFile.println("struct Hashtable_rcr ** createAndFillMasterHashStructureArray();");
 481     cFile.println("struct Hashtable_rcr ** createAndFillMasterHashStructureArray() {");
 482     cFile.println("  struct Hashtable_rcr **table=rcr_createMasterHashTableArray("+weaklyConnectedHRCounter + ");");
 483
 484     for(int i = 0; i < weaklyConnectedHRCounter; i++) {
 485       cFile.println("  table["+i+"] = (struct Hashtable_rcr *) rcr_createHashtable();");
 486     }
 487     cFile.println("  return table;");
 488     cFile.println("}");
 489   }
 490
 491   private void printMasterTraverserInvocation() {
 492     headerFile.println("\nint tasktraverse(SESEcommon * record);");
 493     cFile.println("\nint tasktraverse(SESEcommon * record) {");
 494     cFile.println("  if(!CAS(&record->rcrstatus,1,2)) {");
 495
 496     //release traverser reference...no traversal necessary
 497     cFile.println("#ifndef OOO_DISABLE_TASKMEMPOOL");
 498     cFile.println("    RELEASE_REFERENCE_TO(record);");
 499     cFile.println("#endif");
 500
 501     cFile.println("    return;");
 502     cFile.println("  }");
 503     cFile.println("  switch(record->classID) {");
 504
 505     for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
 506       FlatSESEEnterNode fsen=seseit.next();
 507       cFile.println(    "    /* "+fsen.getPrettyIdentifier()+" */");
 508       cFile.println(    "    case "+fsen.getIdentifier()+": {");
 509       cFile.println(    "      "+fsen.getSESErecordName()+" * rec=("+fsen.getSESErecordName()+" *) record;");
 510       Vector<TempDescriptor> invars=fsen.getInVarsForDynamicCoarseConflictResolution();
 511       for(int i=0;i<invars.size();i++) {
 512         TempDescriptor tmp=invars.get(i);
 513
 514         // FIX IT LATER! Right now, we assume that there is only one parent
 515         // JCJ ask yong hun what we should do in the multi-parent future!
 516         FlatSESEEnterNode parentSESE = (FlatSESEEnterNode) fsen.getParents().iterator().next();
 517         ConflictGraph     graph      = oooa.getConflictGraph(parentSESE);
 518         String            id         = tmp + "_sese" + fsen.getPrettyIdentifier();
 519         ConflictNode      node       = graph.getId2cn().get(id);
 520
 521         if (i!=0) {
 522             cFile.println("      if (record->rcrstatus!=0)");
 523         }
 524
 525         if(state.NOSTALLTR && node.IsValidToPrune()){
 526           cFile.println("    /*  " + this.getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen)+"*/");
 527         }else{
 528           cFile.println("      " + this.getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen));
 529         }
 530
 531       }
 532       //release traverser reference...traversal finished...
 533       //executing thread will clean bins for us
 534       cFile.println("     record->rcrstatus=0;");
 535       cFile.println("#ifndef OOO_DISABLE_TASKMEMPOOL");
 536       cFile.println("    RELEASE_REFERENCE_TO(record);");
 537       cFile.println("#endif");
 538       cFile.println(    "    }");
 539       cFile.println(    "    break;");
 540     }
 541
 542     for(Taint t: doneTaints.keySet()) {
 543       if (t.isStallSiteTaint()){
 544         cFile.println(    "    case -" + getTraverserID(t.getVar(), t.getStallSite())+ ": {");
 545         cFile.println(    "      SESEstall * rec=(SESEstall*) record;");
 546         cFile.println(    "      " + this.getTraverserInvocation(t.getVar(), "rec->___obj___, rec", t.getStallSite())+";");
 547         cFile.println(    "     record->rcrstatus=0;");
 548         cFile.println(    "    }");
 549         cFile.println("    break;");
 550       }
 551     }
 552
 553     cFile.println("    default:\n    printf(\"Invalid SESE ID was passed in: %d.\\n\",record->classID);\n    break;");
 554     cFile.println("  }");
 555     cFile.println("}");
 556   }
 557
 558
 559   //Currently UNUSED method but may be useful in the future.
 560   //This will print the traverser invocation that takes in a traverserID and starting ptr
 561   private void printResumeTraverserInvocation() {
 562     headerFile.println("\nint traverse(void * startingPtr, SESEcommon * record, int traverserID);");
 563     cFile.println("\nint traverse(void * startingPtr, SESEcommon *record, int traverserID) {");
 564     cFile.println("  switch(traverserID) {");
 565
 566     for(Taint t: doneTaints.keySet()) {
 567       cFile.println("  case " + doneTaints.get(t)+ ":");
 568       if(t.isRBlockTaint()) {
 569         cFile.println("    " + this.getTraverserInvocation(t.getVar(), "startingPtr, ("+t.getSESE().getSESErecordName()+" *)record", t.getSESE()));
 570       } else if (t.isStallSiteTaint()){
 571         // JCJ either remove this or consider writing a comment explaining what it is commented out for
 572         cFile.println("/*    " + this.getTraverserInvocation(t.getVar(), "startingPtr, record", t.getStallSite())+"*/");
 573       } else {
 574         System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t);
 575       }
 576       cFile.println("    break;");
 577     }
 578
 579     cFile.println("  default:\n    break;");
 580
 581     cFile.println(" }");
 582     cFile.println("}");
 583   }
 584
 585
 586   /*
 587    * This method generates a C method for every inset variable and rblock.
 588    *
 589    * The C method works by generating a large switch statement that will run the appropriate
 590    * checking code for each object based on its allocation site. The switch statement is
 591    * surrounded by a while statement which dequeues objects to be checked from a queue. An
 592    * object is added to a queue only if it contains a conflict (in itself or in its referencees)
 593    * and we came across it while checking through it's referencer. Because of this property,
 594    * conflicts will be signaled by the referencer; the only exception is the inset variable which can
 595    * signal a conflict within itself.
 596    */
 597
 598   private void printCMethod(Hashtable<Integer, ConcreteRuntimeObjNode> created, Taint taint) {
 599     String inVar = taint.getVar().getSafeSymbol();
 600     String rBlock;
 601
 602     if(taint.isStallSiteTaint()) {
 603       rBlock = taint.getStallSite().toString();
 604     } else if(taint.isRBlockTaint()) {
 605       rBlock = taint.getSESE().getPrettyIdentifier();
 606     } else {
 607       System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString());
 608       return;
 609     }
 610
 611     //This hash table keeps track of all the case statements generated.
 612     Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
 613
 614     //Generate C cases
 615     for (ConcreteRuntimeObjNode node : created.values()) {
 616       printDebug(generalDebug, "Considering " + node.allocSite + " for traversal");
 617       if (!cases.containsKey(node.allocSite) && qualifiesForCaseStatement(node)) {
 618         printDebug(generalDebug, "+\t" + node.allocSite + " qualified for case statement");
 619         addChecker(taint, node, cases, null, "ptr", 0);
 620       }
 621     }
 622
 623     String methodName;
 624     int index=-1;
 625
 626     if (taint.isStallSiteTaint()) {
 627       methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, SESEstall *record)";
 628     } else {
 629       methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, "+taint.getSESE().getSESErecordName() +" *record)";
 630       FlatSESEEnterNode fsese=taint.getSESE();
 631       TempDescriptor tmp=taint.getVar();
 632       index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
 633      }
 634
 635     cFile.println(methodName + " {");
 636     headerFile.println(methodName + ";");
 637
 638     if(cases.size() == 0) {
 639       cFile.println(" return;");
 640     } else {
 641       cFile.println("    int totalcount=RUNBIAS;");
 642       if (taint.isStallSiteTaint()) {
 643         cFile.println("    record->rcrRecords[0].count=RUNBIAS;");
 644       } else {
 645         cFile.println("    record->rcrRecords["+index+"].count=RUNBIAS;");
 646       }
 647
 648       //clears queue and hashtable that keeps track of where we've been.
 649       cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
 650       //generic cast to ___Object___ to access ptr->allocsite field.
 651       cFile.println("struct ___Object___ * ptr = (struct ___Object___ *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable + "(ptr);\n do {");
 652       if (taint.isRBlockTaint()) {
 653         cFile.println("  if(unlikely(record->common.doneExecuting)) {");
 654         cFile.println("    record->common.rcrstatus=0;");
 655         cFile.println("    return;");
 656         cFile.println("  }");
 657       }
 658       cFile.println("  switch(ptr->allocsite) {");
 659
 660       for(AllocSite singleCase: cases.keySet()) {
 661         cFile.append(cases.get(singleCase));
 662       }
 663
 664       cFile.println("  default:\n    break; ");
 665       cFile.println("  }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}");
 666
 667       if (taint.isStallSiteTaint()) {
 668         //need to add this
 669         cFile.println("     if(atomic_sub_and_test(totalcount,&(record->rcrRecords[0].count))) {");
 670         cFile.println("         psem_give_tag(record->common.parentsStallSem, record->tag);");
 671         cFile.println("         BARRIER();");
 672         cFile.println("}");
 673       } else {
 674         cFile.println("     if(atomic_sub_and_test(totalcount,&(record->rcrRecords["+index+"].count))) {");
 675         cFile.println("        int flag=LOCKXCHG32(&(record->rcrRecords["+index+"].flag),0);");
 676         cFile.println("        if(flag) {");
 677         //we have resolved a heap root...see if this was the last dependence
 678         cFile.println("            if(atomic_sub_and_test(1, &(record->common.unresolvedDependencies))) workScheduleSubmit((void *)record);");
 679         cFile.println("        }");
 680         cFile.println("     }");
 681       }
 682     }
 683     cFile.println("}");
 684     cFile.flush();
 685   }
 686
 687   /*
 688    * addChecker creates a case statement for every object that is an inset variable, has more
 689    * than 1 parent && has conflicts, or where resumes are possible
 690    * See .qualifiesForCaseStatement
 691    */
 692   private void addChecker(Taint taint,
 693                           ConcreteRuntimeObjNode node,
 694                           Hashtable<AllocSite,StringBuilder> cases,
 695                           StringBuilder possibleContinuingCase,
 696                           String prefix,
 697                           int depth) {
 698     StringBuilder currCase = possibleContinuingCase;
 699     if(qualifiesForCaseStatement(node)) {
 700       assert prefix.equals("ptr");
 701       assert !cases.containsKey(node.allocSite);
 702       currCase = new StringBuilder();
 703       cases.put(node.allocSite, currCase);
 704       currCase.append("  case " + node.allocSite.getUniqueAllocSiteID() + ": {\n");
 705     }
 706     //either currCase is continuing off a parent case or is its own.
 707     assert currCase !=null;
 708
 709     insertEntriesIntoHashStructure(taint, node, prefix, depth, currCase);
 710
 711     //Handle conflicts further down.
 712     if(node.descendantsConflict()) {
 713       int pdepth=depth+1;
 714       currCase.append("{\n");
 715
 716       //Array Case
 717       if(node.isArray()) {
 718         String childPtr = "((struct ___Object___ **)(((char *) &(((struct ArrayObject *)"+ prefix+")->___length___))+sizeof(int)))[i]";
 719         String currPtr = "arrayElement" + pdepth;
 720
 721         currCase.append("{\n  int i;\n");
 722         currCase.append("    struct ___Object___ * "+currPtr+";\n");
 723         currCase.append("  for(i = 0; i<((struct ArrayObject *) " + prefix + " )->___length___; i++ ) {\n");
 724
 725         //There should be only one field, hence we only take the first field in the keyset.
 726         assert node.referencees.keySet().size() <= 1;
 727         ObjRefList refsAtParticularField = node.referencees.get(node.referencees.keySet().iterator().next());
 728         printObjRefSwitchStatement(taint,cases,pdepth,currCase,refsAtParticularField,childPtr,currPtr);
 729         currCase.append("      }}\n");
 730       } else {
 731       //All other cases
 732         String currPtr = "myPtr" + pdepth;
 733         currCase.append("    struct ___Object___ * "+currPtr+";\n");
 734         for(String field: node.referencees.keySet()) {
 735           ObjRefList refsAtParticularField = node.referencees.get(field);
 736
 737           if(refsAtParticularField.hasConflicts()) {
 738             String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + field + "___";
 739             printObjRefSwitchStatement(taint,cases, pdepth, currCase, refsAtParticularField, childPtr, currPtr);
 740           }
 741         }
 742       }
 743
 744       currCase.append("}\n"); //For particular top level case statement.
 745     }
 746     if(qualifiesForCaseStatement(node)) {
 747       currCase.append("  }\n  break;\n");
 748     }
 749   }
 750
 751   private void insertEntriesIntoHashStructure(Taint taint, ConcreteRuntimeObjNode curr,
 752                                               String prefix, int depth, StringBuilder currCase) {
 753
 754     int index=0;
 755     if (taint.isRBlockTaint()) {
 756       FlatSESEEnterNode fsese=taint.getSESE();
 757       TempDescriptor tmp=taint.getVar();
 758       index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
 759     }
 760
 761     String strrcr=taint.isRBlockTaint()?"&record->rcrRecords["+index+"], ":"NULL, ";
 762     String tasksrc=taint.isRBlockTaint()?"(SESEcommon *) record, ":"(SESEcommon *)(((INTPTR)record)|1LL), ";
 763
 764     //Do call if we need it.
 765     if(curr.primConfWrite||curr.objConfWrite) {
 766       int heaprootNum = connectedHRHash.get(taint).id;
 767       assert heaprootNum != -1;
 768         currCase.append("    int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
 769       if (curr.descendantsConflict())
 770         currCase.append("    int tmpvar"+depth+"=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", "+tasksrc+strrcr+index+");\n");
 771       else
 772         currCase.append("    int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", "+ tasksrc+strrcr+index+");\n");
 773     } else if (curr.primConfRead||curr.objConfRead) {
 774       int heaprootNum = connectedHRHash.get(taint).id;
 775       assert heaprootNum != -1;
 776       currCase.append("    int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
 777       if (curr.descendantsConflict())
 778         currCase.append("    int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", "+tasksrc+strrcr+index+");\n");
 779       else
 780         currCase.append("    int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", "+tasksrc+strrcr+index+");\n");
 781     }
 782
 783     if(curr.primConfWrite||curr.objConfWrite||curr.primConfRead||curr.objConfRead) {
 784       currCase.append("if (!(tmpvar"+depth+"&READYMASK)) totalcount--;\n");
 785     }
 786   }
 787
 788   private void printObjRefSwitchStatement(Taint taint,
 789                                           Hashtable<AllocSite, StringBuilder> cases,
 790                                           int pDepth,
 791                                           StringBuilder currCase,
 792                                           ArrayList<ObjRef> refsAtParticularField,
 793                                           String childPtr,
 794                                           String currPtr) {
 795
 796     currCase.append("    "+currPtr+"= (struct ___Object___ * ) " + childPtr + ";\n");
 797     currCase.append("    if (" + currPtr + " != NULL) { \n");
 798     currCase.append("    switch(" + currPtr + getAllocSiteInC + ") {\n");
 799
 800     for(ObjRef ref: refsAtParticularField) {
 801       if(ref.child.descendantsConflict() || ref.child.hasPrimitiveConflicts()) {
 802         currCase.append("      case "+ref.allocSite+":\n      {\n");
 803         //The hash insert is here because we don't want to enqueue things unless we know it conflicts.
 804         currCase.append("        if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
 805
 806         if(qualifiesForCaseStatement(ref.child)){
 807             currCase.append("        " + addToQueueInC + childPtr + ");\n ");
 808         } else {
 809           addChecker(taint, ref.child, cases, currCase, currPtr, pDepth + 1);
 810         }
 811
 812         currCase.append("    }\n");  //close for queryVistedHashtable
 813
 814         currCase.append("}\n"); //close for internal case statement
 815       }
 816     }
 817
 818     currCase.append("    default:\n" +
 819                             "       break;\n"+
 820                             "    }}\n"); //internal switch.
 821   }
 822
 823   private boolean qualifiesForCaseStatement(ConcreteRuntimeObjNode node) {
 824     return (
 825         //insetVariable case
 826         (node.isInsetVar && (node.descendantsConflict() || node.hasPrimitiveConflicts()) || node.hasDirectObjConflict()) ||
 827         //non-inline-able code cases
 828         (node.getNumOfReachableParents() != 1 && node.descendantsConflict()) ||
 829         //Cases where resumes are possible
 830         (node.hasPotentialToBeIncorrectDueToConflict) && node.descendantsObjConflict);
 831   }
 832
 833   // decide whether the given SESE doesn't have traversers at all
 834   public boolean hasEmptyTraversers(FlatSESEEnterNode fsen) {
 835     boolean hasEmpty = true;
 836
 837     Set<FlatSESEEnterNode> children = fsen.getChildren();
 838     for (Iterator iterator = children.iterator(); iterator.hasNext();) {
 839       FlatSESEEnterNode child = (FlatSESEEnterNode) iterator.next();
 840       hasEmpty &= child.getInVarsForDynamicCoarseConflictResolution().size() == 0;
 841     }
 842     return hasEmpty;
 843
 844   }
 845   //Note we assume instance of FlatSESEEnterNode to be sese blocks else they are considered stallsites.
 846   private Taint getProperTaintForEnterNode(FlatNode fn, VariableNode var) {
 847     FlatNode flatnode;
 848     Set<Taint> taints = globalEffects.keySet();
 849     boolean isStallSite = !(fn instanceof FlatSESEEnterNode);
 850
 851     for (Taint t : taints) {
 852       flatnode = (isStallSite) ? t.getStallSite():t.getSESE();
 853
 854       if( flatnode != null        &&
 855           flatnode.equals(fn)     &&
 856           t.getVar().equals(var.getTempDescriptor())) {
 857         return t;
 858       }
 859     }
 860     return null;
 861   }
 862
 863   private void printDebug(boolean guard, String debugStatements) {
 864     if(guard)
 865       System.out.println(debugStatements);
 866   }
 867
 868   //Walks the connected heaproot groups, coalesces them, and numbers them
 869   //Special Note: Lookup Table must already be created
 870   private void enumerateHeaproots() {
 871     weaklyConnectedHRCounter = 0;
 872     num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
 873
 874     for(Taint t: connectedHRHash.keySet()) {
 875       if(connectedHRHash.get(t).id == -1) {
 876         WeaklyConectedHRGroup hg = connectedHRHash.get(t);
 877         hg.id = weaklyConnectedHRCounter;
 878         num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
 879         weaklyConnectedHRCounter++;
 880       }
 881
 882       if(t.isRBlockTaint()) {
 883         int id=connectedHRHash.get(t).id;
 884         Pair tup=new Pair(t.getVar(),t.getSESE());
 885         if (weakMap.containsKey(tup)) {
 886           if (weakMap.get(tup).intValue()!=id)
 887             throw new Error("Var/SESE not unique for weak component.");
 888         } else
 889             weakMap.put(tup, new Integer(id));
 890       }
 891     }
 892
 893     //output weakly connected groups for verification
 894     if(generalDebug) {
 895       System.out.println("==============Weakly Connected HeapRoots==============");
 896
 897       for(int i=0; i < num2WeaklyConnectedHRGroup.size(); i++){
 898         System.out.println("Heap Group #" + i);
 899         WeaklyConectedHRGroup hg = num2WeaklyConnectedHRGroup.get(i);
 900         for(Taint t: hg.connectedHRs) {
 901           System.out.println("\t" + t);
 902         }
 903       }
 904
 905       System.out.println("=======================END LIST=======================");
 906     }
 907   }
 908
 909   private void printoutTable(EffectsTable table) {
 910
 911     System.out.println("==============EFFECTS TABLE PRINTOUT==============");
 912     for(AllocSite as: table.table.keySet()) {
 913       System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
 914
 915       BucketOfEffects boe = table.table.get(as);
 916
 917       if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
 918         System.out.println("\t\tPotentially conflicting roots: ");
 919         for(String key: boe.potentiallyConflictingRoots.keySet()) {
 920           System.out.println("\t\t-Field: " + key);
 921           System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
 922         }
 923       }
 924       for(Taint t: boe.taint2EffectsGroup.keySet()) {
 925         System.out.println("\t\t For Taint " + t);
 926         EffectsGroup eg = boe.taint2EffectsGroup.get(t);
 927
 928         if(eg.hasPrimitiveConflicts()) {
 929           System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
 930           for(String field: eg.primitiveConflictingFields.keySet()) {
 931             System.out.print(field + " ");
 932           }
 933           System.out.println();
 934         }
 935         for(String fieldKey: eg.myObjEffects.keySet()) {
 936           CombinedEffects ce = eg.myObjEffects.get(fieldKey);
 937           System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
 938           System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
 939               " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
 940               " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
 941           for(Effect ef: ce.originalEffects) {
 942             System.out.println("\t" + ef);
 943           }
 944         }
 945       }
 946     }
 947
 948   }
 949
 950   private class EffectsGroup {
 951     Hashtable<String, CombinedEffects> myObjEffects;
 952     //In the end, we don't really care what the primitive fields are.
 953     Hashtable<String, CombinedEffects> primitiveConflictingFields;
 954     private boolean primConfRead;
 955     private boolean primConfWrite;
 956
 957     public EffectsGroup() {
 958       myObjEffects = new Hashtable<String, CombinedEffects>();
 959       primitiveConflictingFields = new Hashtable<String, CombinedEffects>();
 960
 961       primConfRead  = false;
 962       primConfWrite = false;
 963     }
 964
 965     public void addPrimitive(Effect e, boolean conflict) {
 966       CombinedEffects effects;
 967       if((effects = primitiveConflictingFields.get(e.getField().getSymbol())) == null) {
 968         effects = new CombinedEffects();
 969         primitiveConflictingFields.put(e.getField().getSymbol(), effects);
 970       }
 971       effects.add(e, conflict);
 972
 973       primConfRead  |= effects.hasReadConflict;
 974       primConfWrite |= effects.hasWriteConflict;
 975     }
 976
 977     public void addObjEffect(Effect e, boolean conflict) {
 978       CombinedEffects effects;
 979       if((effects = myObjEffects.get(e.getField().getSymbol())) == null) {
 980         effects = new CombinedEffects();
 981         myObjEffects.put(e.getField().getSymbol(), effects);
 982       }
 983       effects.add(e, conflict);
 984     }
 985
 986     public boolean isEmpty() {
 987       return myObjEffects.isEmpty() && primitiveConflictingFields.isEmpty();
 988     }
 989
 990     public boolean hasPrimitiveConflicts(){
 991       return !primitiveConflictingFields.isEmpty();
 992     }
 993
 994     public CombinedEffects getPrimEffect(String field) {
 995       return primitiveConflictingFields.get(field);
 996     }
 997
 998     public boolean hasObjectEffects() {
 999       return !myObjEffects.isEmpty();
1000     }
1001
1002     public CombinedEffects getObjEffect(String field) {
1003       return myObjEffects.get(field);
1004     }
1005   }
1006
1007   //Is the combined effects for all effects with the same affectedAllocSite and field
1008   private class CombinedEffects {
1009     ArrayList<Effect> originalEffects;
1010
1011     public boolean hasReadEffect;
1012     public boolean hasWriteEffect;
1013     public boolean hasStrongUpdateEffect;
1014
1015     public boolean hasReadConflict;
1016     public boolean hasWriteConflict;
1017     public boolean hasStrongUpdateConflict;
1018
1019
1020     public CombinedEffects() {
1021       originalEffects = new ArrayList<Effect>();
1022
1023       hasReadEffect = false;
1024       hasWriteEffect = false;
1025       hasStrongUpdateEffect = false;
1026
1027       hasReadConflict = false;
1028       hasWriteConflict = false;
1029       hasStrongUpdateConflict = false;
1030     }
1031
1032     public boolean add(Effect e, boolean conflict) {
1033       if(!originalEffects.add(e))
1034         return false;
1035
1036       switch(e.getType()) {
1037       case Effect.read:
1038         hasReadEffect = true;
1039         hasReadConflict = conflict;
1040         break;
1041       case Effect.write:
1042         hasWriteEffect = true;
1043         hasWriteConflict = conflict;
1044         break;
1045       case Effect.strongupdate:
1046         hasStrongUpdateEffect = true;
1047         hasStrongUpdateConflict = conflict;
1048         break;
1049       default:
1050         System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
1051         assert false;
1052         break;
1053       }
1054       return true;
1055     }
1056
1057     public boolean hasConflict() {
1058       return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
1059     }
1060
1061     public void mergeWith(CombinedEffects other) {
1062       for(Effect e: other.originalEffects) {
1063         if(!originalEffects.contains(e)){
1064           originalEffects.add(e);
1065         }
1066       }
1067
1068       hasReadEffect |= other.hasReadEffect;
1069       hasWriteEffect |= other.hasWriteEffect;
1070       hasStrongUpdateEffect |= other.hasStrongUpdateEffect;
1071
1072       hasReadConflict |= other.hasReadConflict;
1073       hasWriteConflict |= other.hasWriteConflict;
1074       hasStrongUpdateConflict |= other.hasStrongUpdateConflict;
1075     }
1076   }
1077
1078   //This will keep track of a reference
1079   private class ObjRef {
1080     CombinedEffects myEffects;
1081     boolean reachesConflict;
1082     int allocSite;
1083     String field;
1084
1085
1086     //This keeps track of the parent that we need to pass by inorder to get
1087     //to the conflicting child (if there is one).
1088     ConcreteRuntimeObjNode parent;
1089     ConcreteRuntimeObjNode child;
1090
1091     public ObjRef(String fieldname,
1092                   ConcreteRuntimeObjNode parent,
1093                   ConcreteRuntimeObjNode ref,
1094                   CombinedEffects myEffects) {
1095       field = fieldname;
1096       allocSite = ref.allocSite.getUniqueAllocSiteID();
1097       child = ref;
1098       this.parent = parent;
1099
1100       this.myEffects = myEffects;
1101       reachesConflict = false;
1102     }
1103
1104     public boolean hasConflictsDownThisPath() {
1105       return child.descendantsConflict() || child.hasPrimitiveConflicts() || myEffects.hasConflict();
1106     }
1107
1108     public boolean hasDirectObjConflict() {
1109       return myEffects.hasConflict();
1110     }
1111
1112     public boolean equals(Object other) {
1113       if(other == null || !(other instanceof ObjRef))
1114         return false;
1115
1116       ObjRef o = (ObjRef) other;
1117
1118       if(o.field == this.field && o.allocSite == this.allocSite && this.child.equals(o.child))
1119         return true;
1120
1121       return false;
1122     }
1123
1124     public int hashCode() {
1125       return child.allocSite.hashCode() ^ field.hashCode();
1126     }
1127
1128     public void mergeWith(ObjRef ref) {
1129       myEffects.mergeWith(ref.myEffects);
1130     }
1131   }
1132
1133   private class ConcreteRuntimeObjNode {
1134     HashSet<ObjRef> referencers;
1135     Hashtable<String, ObjRefList> referencees;
1136     HeapRegionNode original;
1137     AllocSite allocSite;
1138     boolean isInsetVar;
1139
1140     //Accesses BY this node
1141     boolean primConfRead=false;
1142     boolean primConfWrite=false;
1143     boolean objConfRead=false;
1144     boolean objConfWrite=false;
1145
1146     boolean descendantsObjConflict =false;
1147     boolean descendantsPrimConflict=false;
1148     boolean hasPotentialToBeIncorrectDueToConflict=false;
1149
1150     public ConcreteRuntimeObjNode(HeapRegionNode HRN, boolean isInset) {
1151       referencers = new HashSet<ObjRef>(4);
1152       referencees = new Hashtable<String, ObjRefList>(5);
1153
1154       original = HRN;
1155       allocSite = HRN.getAllocSite();
1156       isInsetVar = isInset;
1157     }
1158
1159
1160     public void addReferencer(ObjRef refToMe) {
1161       referencers.add(refToMe);
1162     }
1163
1164     public void addReferencee(String field, ObjRef refToChild) {
1165       ObjRefList array;
1166
1167       if((array = referencees.get(field)) == null) {
1168         array = new ObjRefList();
1169         referencees.put(field, array);
1170       }
1171
1172       array.add(refToChild);
1173     }
1174
1175     public boolean hasDirectObjConflict() {
1176       return objConfRead || objConfWrite;
1177     }
1178
1179     public boolean isArray() {
1180       return original.getType().isArray();
1181     }
1182
1183     public int getNumOfReachableParents() {
1184       return referencers.size();
1185     }
1186
1187     public boolean hasPrimitiveConflicts() {
1188       return primConfRead || primConfWrite;
1189     }
1190
1191     public boolean hasConflict() {
1192       return objConfRead || objConfWrite || primConfRead || primConfWrite;
1193     }
1194
1195     public boolean descendantsConflict() {
1196       return descendantsObjConflict||descendantsPrimConflict;
1197     }
1198   }
1199
1200   //Simple extension of the ArrayList to allow it to find if any ObjRefs conflict.
1201   private class ObjRefList extends ArrayList<ObjRef> {
1202     private static final long serialVersionUID = 326523675530835596L;
1203
1204     public ObjRefList() {
1205       super();
1206     }
1207
1208     public boolean add(ObjRef o){
1209       if(this.contains(o)) {
1210         ObjRef other = this.get(this.indexOf(o));
1211         other.mergeWith(o);
1212         return false;
1213       }
1214       else
1215         return super.add(o);
1216     }
1217
1218     public boolean hasConflicts() {
1219       for(ObjRef r: this) {
1220         if(r.hasConflictsDownThisPath() || r.child.hasPrimitiveConflicts()) {
1221           return true;
1222         }
1223       }
1224
1225       return false;
1226     }
1227   }
1228
1229   private class EffectsTable {
1230     private Hashtable<AllocSite, BucketOfEffects> table;
1231
1232     public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1233                         Hashtable<Taint, Set<Effect>> conflicts) {
1234       table = new Hashtable<AllocSite, BucketOfEffects>();
1235
1236       // rehash all effects (as a 5-tuple) by their affected allocation site
1237       for (Taint t : effects.keySet()) {
1238         Set<Effect> localConflicts = conflicts.get(t);
1239         for (Effect e : effects.get(t)) {
1240           BucketOfEffects bucket;
1241           if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1242             bucket = new BucketOfEffects();
1243             table.put(e.getAffectedAllocSite(), bucket);
1244           }
1245           printDebug(verboseDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts);
1246           bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1247         }
1248       }
1249     }
1250
1251     public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1252       //This would get the proper bucket of effects and then get all the effects
1253       //for a parent for a specific taint
1254       try {
1255         return table.get(parentKey).taint2EffectsGroup.get(taint);
1256       }
1257       catch (NullPointerException e) {
1258         return null;
1259       }
1260     }
1261
1262     // Run Analysis will walk the data structure and figure out the weakly
1263     // connected heap roots.
1264     public void runAnalysis() {
1265       if(verboseDebug) {
1266         printoutTable(this);
1267       }
1268
1269       for(AllocSite key: table.keySet()) {
1270         BucketOfEffects effects = table.get(key);
1271         //make sure there are actually conflicts in the bucket
1272         if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1273           for(String field: effects.potentiallyConflictingRoots.keySet()){
1274             ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1275             //For simplicity, we just create a new group and add everything to it instead of
1276             //searching through all of them for the largest group and adding everyone in.
1277             WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1278             group.add(taints); //This will automatically add the taint to the connectedHRhash
1279           }
1280         }
1281       }
1282     }
1283   }
1284
1285   private class WeaklyConectedHRGroup {
1286     HashSet<Taint> connectedHRs;
1287     int id;
1288
1289     public WeaklyConectedHRGroup() {
1290       connectedHRs = new HashSet<Taint>();
1291       id = -1;
1292     }
1293
1294     public void add(ArrayList<Taint> list) {
1295       for(Taint t: list) {
1296         this.add(t);
1297       }
1298     }
1299
1300     public void add(Taint t) {
1301       connectedHRs.add(t);
1302       WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1303       connectedHRHash.put(t, this); //put new group into hash
1304       //If the taint was already in another group, move all its buddies over.
1305       if(oldGroup != this && oldGroup != null) {
1306         Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1307         Taint relatedTaint;
1308
1309         while(it.hasNext() && (relatedTaint = it.next()) != null) {
1310           if(!connectedHRs.contains(relatedTaint)){
1311             this.add(relatedTaint);
1312           }
1313         }
1314       }
1315     }
1316   }
1317
1318   //This is a class that stores all the effects for an affected allocation site
1319   //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1320   //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1321   //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1322   //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1323   //field.
1324   private class BucketOfEffects {
1325     // This table is used for lookup while creating the traversal.
1326     Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1327
1328     //This table is used to help identify weakly connected groups: Contains ONLY
1329     //conflicting effects AND is only initialized when needed
1330     //String stores the field
1331     Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1332
1333     public BucketOfEffects() {
1334       taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1335     }
1336
1337     public void add(Taint t, Effect e, boolean conflict) {
1338       EffectsGroup effectsForGivenTaint;
1339
1340       if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1341         effectsForGivenTaint = new EffectsGroup();
1342         taint2EffectsGroup.put(t, effectsForGivenTaint);
1343       }
1344
1345       if (isReallyAPrimitive(e.getField().getType())) {
1346         if (conflict) {
1347           effectsForGivenTaint.addPrimitive(e, true);
1348         }
1349       } else {
1350         effectsForGivenTaint.addObjEffect(e, conflict);
1351       }
1352
1353       if(conflict) {
1354         if(potentiallyConflictingRoots == null) {
1355           potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1356         }
1357
1358         ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1359         if(taintsForField == null) {
1360           taintsForField = new ArrayList<Taint>();
1361           potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1362         }
1363
1364         if(!taintsForField.contains(t)) {
1365           taintsForField.add(t);
1366         }
1367       }
1368     }
1369   }
1370
1371   private class TaintAndInternalHeapStructure {
1372     public Taint t;
1373     public Hashtable<Integer, ConcreteRuntimeObjNode> nodesInHeap;
1374
1375     public TaintAndInternalHeapStructure(Taint taint, Hashtable<Integer, ConcreteRuntimeObjNode> nodesInHeap) {
1376       t = taint;
1377       this.nodesInHeap = nodesInHeap;
1378     }
1379   }
1380
1381   private class TraversalInfo {
1382     public FlatNode f;
1383     public ReachGraph rg;
1384     public TempDescriptor invar;
1385
1386     public TraversalInfo(FlatNode fn, ReachGraph rg1) {
1387       f = fn;
1388       rg = rg1;
1389       invar = null;
1390     }
1391
1392     public TraversalInfo(FlatNode fn, ReachGraph rg1, TempDescriptor tempDesc) {
1393       f = fn;
1394       rg =rg1;
1395       invar = tempDesc;
1396     }
1397
1398     public boolean isStallSite() {
1399       return !(f instanceof FlatSESEEnterNode);
1400     }
1401
1402     public boolean isRblock() {
1403       return (f instanceof FlatSESEEnterNode);
1404     }
1405   }
1406 }