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