Robust/src/IR/Flat/RuntimeConflictResolver.java

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