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