Robust/src/IR/Flat/RuntimeConflictResolver.java

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