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