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         cFile.println("      " + this.getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen));
 423       }
 424       //release traverser reference...traversal finished...
 425       //executing thread will clean bins for us
 426       cFile.println("#ifndef OOO_DISABLE_TASKMEMPOOL");
 427       cFile.println("    RELEASE_REFERENCE_TO(record);");
 428       cFile.println("#endif");
 429       cFile.println(    "    }");
 430       cFile.println(    "    break;");
 431     }
 432
 433     for(Taint t: doneTaints.keySet()) {
 434       if (t.isStallSiteTaint()){
 435         cFile.println(    "    case -" + getTraverserID(t.getVar(), t.getStallSite())+ ": {");
 436         cFile.println(    "      SESEstall * rec=(SESEstall*) record;");
 437         cFile.println(    "      " + this.getTraverserInvocation(t.getVar(), "rec->___obj___, rec", t.getStallSite())+";");
 438         cFile.println(    "    }");
 439         cFile.println("    break;");
 440       }
 441     }
 442
 443     cFile.println("    default:\n    printf(\"Invalid SESE ID was passed in: %d.\\n\",record->classID);\n    break;");
 444     cFile.println("  }");
 445     cFile.println("}");
 446   }
 447
 448
 449   //This will print the traverser invocation that takes in a traverserID and starting ptr
 450   private void printResumeTraverserInvocation() {
 451     headerFile.println("\nint traverse(void * startingPtr, SESEcommon * record, int traverserID);");
 452     cFile.println("\nint traverse(void * startingPtr, SESEcommon *record, int traverserID) {");
 453     cFile.println("  switch(traverserID) {");
 454
 455     for(Taint t: doneTaints.keySet()) {
 456       cFile.println("  case " + doneTaints.get(t)+ ":");
 457       if(t.isRBlockTaint()) {
 458         cFile.println("    " + this.getTraverserInvocation(t.getVar(), "startingPtr, ("+t.getSESE().getSESErecordName()+" *)record", t.getSESE()));
 459       } else if (t.isStallSiteTaint()){
 460         cFile.println("/*    " + this.getTraverserInvocation(t.getVar(), "startingPtr, record", t.getStallSite())+"*/");
 461       } else {
 462         System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t);
 463       }
 464       cFile.println("    break;");
 465     }
 466
 467     if(RuntimeConflictResolver.cSideDebug) {
 468       cFile.println("  default:\n    printf(\"Invalid traverser ID %u was passed in.\\n\", traverserID);\n    break;");
 469     } else {
 470       cFile.println("  default:\n    break;");
 471     }
 472
 473     cFile.println(" }");
 474     cFile.println("}");
 475   }
 476
 477   private void createConcreteGraph(
 478       EffectsTable table,
 479       Hashtable<Integer, ConcreteRuntimeObjNode> created,
 480       VariableNode varNode,
 481       Taint t) {
 482
 483     // if table is null that means there's no conflicts, therefore we need not
 484     // create a traversal
 485     if (table == null)
 486       return;
 487
 488     Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
 489     while (possibleEdges.hasNext()) {
 490       RefEdge edge = possibleEdges.next();
 491       assert edge != null;
 492
 493       ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true);
 494       int rootKey = singleRoot.allocSite.getUniqueAllocSiteID();
 495
 496       if (!created.containsKey(rootKey)) {
 497         created.put(rootKey, singleRoot);
 498         createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table, t);
 499       }
 500     }
 501   }
 502
 503   // Plan is to add stuff to the tree depth-first sort of way. That way, we can
 504   // propagate up conflicts
 505   private void createHelper(ConcreteRuntimeObjNode curr,
 506                             Iterator<RefEdge> edges,
 507                             Hashtable<Integer, ConcreteRuntimeObjNode> created,
 508                             EffectsTable table,
 509                             Taint taint) {
 510     assert table != null;
 511     AllocSite parentKey = curr.allocSite;
 512     EffectsGroup currEffects = table.getEffects(parentKey, taint);
 513
 514     if (currEffects == null || currEffects.isEmpty())
 515       return;
 516
 517     //Handle Objects (and primitives if child is new)
 518     if(currEffects.hasObjectEffects()) {
 519       while(edges.hasNext()) {
 520         RefEdge edge = edges.next();
 521         String field = edge.getField();
 522         CombinedObjEffects effectsForGivenField = currEffects.getObjEffect(field);
 523         //If there are no effects, then there's no point in traversing this edge
 524         if(effectsForGivenField != null) {
 525           HeapRegionNode childHRN = edge.getDst();
 526           int childKey = childHRN.getAllocSite().getUniqueAllocSiteID();
 527           boolean isNewChild = !created.containsKey(childKey);
 528           ConcreteRuntimeObjNode child;
 529
 530           if(isNewChild) {
 531             child = new ConcreteRuntimeObjNode(childHRN, false);
 532             created.put(childKey, child);
 533           } else {
 534             child = created.get(childKey);
 535           }
 536
 537           curr.addObjChild(field, child, effectsForGivenField);
 538
 539           if (effectsForGivenField.hasConflict()) {
 540             child.hasPotentialToBeIncorrectDueToConflict |= effectsForGivenField.hasReadConflict;
 541             propagateObjConflict(curr, child);
 542           }
 543
 544           if(effectsForGivenField.hasReadEffect) {
 545             child.addReachableParent(curr);
 546
 547             //If isNewChild, flag propagation will be handled at recursive call
 548             if(isNewChild) {
 549               createHelper(child, childHRN.iteratorToReferencees(), created, table, taint);
 550             } else {
 551             //This makes sure that all conflicts below the child is propagated up the referencers.
 552               if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) {
 553                 propagatePrimConflict(child, child.enqueueToWaitingQueueUponConflict);
 554               }
 555
 556               if(child.decendantsObjConflict) {
 557                 propagateObjConflict(child, child.enqueueToWaitingQueueUponConflict);
 558               }
 559             }
 560           }
 561         }
 562       }
 563     }
 564
 565     //Handles primitives
 566     curr.primitiveConflictingFields = currEffects.primitiveConflictingFields;
 567     if(currEffects.hasPrimitiveConflicts()) {
 568       //Reminder: primitive conflicts are abstracted to object.
 569       propagatePrimConflict(curr, curr);
 570     }
 571   }
 572
 573   // This will propagate the conflict up the data structure.
 574   private void propagateObjConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
 575     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 576       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
 577           (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) // case where referencer has never seen possible unresolved referencee below
 578       {
 579         referencer.decendantsObjConflict = true;
 580         propagateObjConflict(referencer, pointsOfAccess);
 581       }
 582     }
 583   }
 584
 585   private void propagateObjConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
 586     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 587       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
 588           (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) // case where referencer has never seen possible unresolved referencee below
 589       {
 590         referencer.decendantsObjConflict = true;
 591         propagateObjConflict(referencer, pointOfAccess);
 592       }
 593     }
 594   }
 595
 596   private void propagatePrimConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
 597     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 598       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
 599           (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess)))
 600       {
 601         referencer.decendantsPrimConflict = true;
 602         propagatePrimConflict(referencer, pointsOfAccess);
 603       }
 604     }
 605   }
 606
 607   private void propagatePrimConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
 608     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 609       if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
 610           (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess)))
 611       {
 612         referencer.decendantsPrimConflict = true;
 613         propagatePrimConflict(referencer, pointOfAccess);
 614       }
 615     }
 616   }
 617
 618   /*
 619    * This method generates a C method for every inset variable and rblock.
 620    *
 621    * The C method works by generating a large switch statement that will run the appropriate
 622    * checking code for each object based on its allocation site. The switch statement is
 623    * surrounded by a while statement which dequeues objects to be checked from a queue. An
 624    * object is added to a queue only if it contains a conflict (in itself or in its referencees)
 625    *  and we came across it while checking through it's referencer. Because of this property,
 626    *  conflicts will be signaled by the referencer; the only exception is the inset variable which can
 627    *  signal a conflict within itself.
 628    */
 629
 630   private void printCMethod(Hashtable<Integer, ConcreteRuntimeObjNode> created, Taint taint) {
 631     String inVar = taint.getVar().getSafeSymbol();
 632     String rBlock;
 633
 634     if(taint.isStallSiteTaint()) {
 635       rBlock = taint.getStallSite().toString();
 636     } else if(taint.isRBlockTaint()) {
 637       rBlock = taint.getSESE().getPrettyIdentifier();
 638     } else {
 639       System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString());
 640       return;
 641     }
 642
 643     //This hash table keeps track of all the case statements generated.
 644     Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
 645
 646     //Generate C cases
 647     for (ConcreteRuntimeObjNode node : created.values()) {
 648       printDebug(generalDebug, "Considering " + node.allocSite + " for traversal");
 649       if (!cases.containsKey(node.allocSite) && qualifiesForCaseStatement(node)) {
 650         printDebug(generalDebug, "+\t" + node.allocSite + " qualified for case statement");
 651         addChecker(taint, node, cases, null, "ptr", 0);
 652       }
 653     }
 654
 655     String methodName;
 656     int index=-1;
 657
 658     if (taint.isStallSiteTaint()) {
 659       methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, SESEstall *record)";
 660     } else {
 661       methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, "+taint.getSESE().getSESErecordName() +" *record)";
 662       FlatSESEEnterNode fsese=taint.getSESE();
 663       TempDescriptor tmp=taint.getVar();
 664       index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
 665      }
 666
 667     cFile.println(methodName + " {");
 668     headerFile.println(methodName + ";");
 669
 670     if(cSideDebug) {
 671       cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
 672       }
 673
 674
 675     if(cases.size() == 0) {
 676       cFile.println(" return;");
 677     } else {
 678       cFile.println("    int totalcount=RUNBIAS;");
 679       if (taint.isStallSiteTaint()) {
 680         cFile.println("    record->rcrRecords[0].count=RUNBIAS;");
 681       } else {
 682         cFile.println("    record->rcrRecords["+index+"].count=RUNBIAS;");
 683       }
 684
 685       //clears queue and hashtable that keeps track of where we've been.
 686       cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
 687       //generic cast to ___Object___ to access ptr->allocsite field.
 688       cFile.println("struct ___Object___ * ptr = (struct ___Object___ *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable + "(ptr);\n do {");
 689       if (taint.isRBlockTaint()) {
 690         cFile.println("  if(unlikely(record->common.doneExecuting)) {");
 691         cFile.println("    record->common.rcrstatus=0;");
 692         cFile.println("    return;");
 693         cFile.println("  }");
 694       }
 695       cFile.println("  switch(ptr->allocsite) {");
 696
 697       for(AllocSite singleCase: cases.keySet()) {
 698         cFile.append(cases.get(singleCase));
 699       }
 700
 701       cFile.println("  default:\n    break; ");
 702       cFile.println("  }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}");
 703
 704       if (taint.isStallSiteTaint()) {
 705         //need to add this
 706         cFile.println("     if(atomic_sub_and_test(totalcount,&(record->rcrRecords[0].count))) {");
 707         cFile.println("         psem_give_tag(record->common.parentsStallSem, record->tag);");
 708         cFile.println("         BARRIER();");
 709         cFile.println("}");
 710         cFile.println("         record->common.rcrstatus=0;");
 711       } else {
 712         cFile.println("     if(atomic_sub_and_test(totalcount,&(record->rcrRecords["+index+"].count))) {");
 713         cFile.println("        int flag=LOCKXCHG32(&(record->rcrRecords["+index+"].flag),0);");
 714         cFile.println("        if(flag) {");
 715         //we have resolved a heap root...see if this was the last dependence
 716         cFile.println("            if(atomic_sub_and_test(1, &(record->common.unresolvedDependencies))) workScheduleSubmit((void *)record);");
 717         cFile.println("        }");
 718         cFile.println("     }");
 719         cFile.println("     record->common.rcrstatus=0;");
 720       }
 721     }
 722     cFile.println("}");
 723     cFile.flush();
 724   }
 725
 726   /*
 727    * addChecker creates a case statement for every object that is an inset variable, has more
 728    * than 1 parent && has conflicts, or where resumes are possible (from waiting queue).
 729    * See .qualifiesForCaseStatement
 730    */
 731   private void addChecker(Taint taint,
 732                           ConcreteRuntimeObjNode node,
 733                           Hashtable<AllocSite,StringBuilder> cases,
 734                           StringBuilder possibleContinuingCase,
 735                           String prefix,
 736                           int depth) {
 737     StringBuilder currCase = possibleContinuingCase;
 738     if(qualifiesForCaseStatement(node)) {
 739       assert prefix.equals("ptr");
 740       assert !cases.containsKey(node.allocSite);
 741       currCase = new StringBuilder();
 742       cases.put(node.allocSite, currCase);
 743       currCase.append("  case " + node.getAllocationSite() + ": {\n");
 744     }
 745     //either currCase is continuing off a parent case or is its own.
 746     assert currCase !=null;
 747
 748     insertEntriesIntoHashStructure(taint, node, prefix, depth, currCase);
 749
 750     //Handle conflicts further down.
 751     if(node.decendantsConflict()) {
 752       int pdepth=depth+1;
 753       currCase.append("{\n");
 754
 755       //Array Case
 756       if(node.isArray() && node.decendantsConflict()) {
 757         String childPtr = "((struct ___Object___ **)(((char *) &(((struct ArrayObject *)"+ prefix+")->___length___))+sizeof(int)))[i]";
 758         String currPtr = "arrayElement" + pdepth;
 759
 760         currCase.append("{\n  int i;\n");
 761         currCase.append("    struct ___Object___ * "+currPtr+";\n");
 762         currCase.append("  for(i = 0; i<((struct ArrayObject *) " + prefix + " )->___length___; i++ ) {\n");
 763
 764         //There should be only one field, hence we only take the first field in the keyset.
 765         assert node.objectRefs.keySet().size() <= 1;
 766         ObjRefList refsAtParticularField = node.objectRefs.get(node.objectRefs.keySet().iterator().next());
 767         printObjRefSwitchStatement(taint,cases,pdepth,currCase,refsAtParticularField,childPtr,currPtr);
 768         currCase.append("      }}\n");
 769       } else {
 770       //All other cases
 771         String currPtr = "myPtr" + pdepth;
 772         currCase.append("    struct ___Object___ * "+currPtr+";\n");
 773         for(String field: node.objectRefs.keySet()) {
 774           ObjRefList refsAtParticularField = node.objectRefs.get(field);
 775
 776           if(refsAtParticularField.hasConflicts()) {
 777             String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + field + "___";
 778             printObjRefSwitchStatement(taint,cases, pdepth, currCase, refsAtParticularField, childPtr, currPtr);
 779           }
 780         }
 781       }
 782
 783       currCase.append("}\n"); //For particular top level case statement.
 784     }
 785     if(qualifiesForCaseStatement(node)) {
 786       currCase.append("  }\n  break;\n");
 787     }
 788   }
 789
 790   private void insertEntriesIntoHashStructure(Taint taint, ConcreteRuntimeObjNode curr,
 791       String prefix, int depth, StringBuilder currCase) {
 792     boolean primConfRead=false;
 793     boolean primConfWrite=false;
 794     boolean objConfRead=false;
 795     boolean objConfWrite=false;
 796
 797     //Direct Primitives Test
 798     for(String field: curr.primitiveConflictingFields.keySet()) {
 799       CombinedObjEffects effect=curr.primitiveConflictingFields.get(field);
 800       primConfRead|=effect.hasReadConflict;
 801       primConfWrite|=effect.hasWriteConflict;
 802     }
 803
 804     //Direct Object Reference Test
 805     for(String field: curr.objectRefs.keySet()) {
 806       for(ObjRef ref: curr.objectRefs.get(field)) {
 807         CombinedObjEffects effect=ref.myEffects;
 808         objConfRead|=effect.hasReadConflict;
 809         objConfWrite|=effect.hasWriteConflict;
 810       }
 811     }
 812
 813     int index=0;
 814     if (taint.isRBlockTaint()) {
 815       FlatSESEEnterNode fsese=taint.getSESE();
 816       TempDescriptor tmp=taint.getVar();
 817       index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
 818     }
 819
 820     String strrcr=taint.isRBlockTaint()?"&record->rcrRecords["+index+"], ":"NULL, ";
 821     String tasksrc=taint.isRBlockTaint()?"(SESEcommon *) record, ":"(SESEcommon *)(((INTPTR)record)|1LL), ";
 822
 823     //Do call if we need it.
 824     if(primConfWrite||objConfWrite) {
 825       int heaprootNum = connectedHRHash.get(taint).id;
 826       assert heaprootNum != -1;
 827       int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(curr);
 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_WTWRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", "+tasksrc+strrcr+index+");\n");
 832       else
 833         currCase.append("    int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", "+ tasksrc+strrcr+index+");\n");
 834     } else if (primConfRead||objConfRead) {
 835       int heaprootNum = connectedHRHash.get(taint).id;
 836       assert heaprootNum != -1;
 837       int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(curr);
 838       int traverserID = doneTaints.get(taint);
 839       currCase.append("    int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
 840       if (objConfRead)
 841         currCase.append("    int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", "+tasksrc+strrcr+index+");\n");
 842       else
 843         currCase.append("    int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", "+tasksrc+strrcr+index+");\n");
 844     }
 845
 846     if(primConfWrite||objConfWrite||primConfRead||objConfRead) {
 847       currCase.append("if (!(tmpvar"+depth+"&READYMASK)) totalcount--;\n");
 848     }
 849   }
 850
 851   private void printObjRefSwitchStatement(Taint taint, Hashtable<AllocSite, StringBuilder> cases,
 852       int pDepth, StringBuilder currCase, ObjRefList refsAtParticularField, String childPtr,
 853       String currPtr) {
 854
 855     currCase.append("    "+currPtr+"= (struct ___Object___ * ) " + childPtr + ";\n");
 856     currCase.append("    if (" + currPtr + " != NULL) { \n");
 857     currCase.append("    switch(" + currPtr + getAllocSiteInC + ") {\n");
 858
 859     for(ObjRef ref: refsAtParticularField) {
 860       if(ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
 861         currCase.append("      case "+ref.allocSite+":\n      {\n");
 862         //The hash insert is here because we don't want to enqueue things unless we know it conflicts.
 863         currCase.append("        if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
 864
 865         if(qualifiesForCaseStatement(ref.child)){
 866             currCase.append("        " + addToQueueInC + childPtr + ");\n ");
 867         } else {
 868           addChecker(taint, ref.child, cases, currCase, currPtr, pDepth + 1);
 869         }
 870
 871         currCase.append("    }\n");  //close for queryVistedHashtable
 872
 873         currCase.append("}\n"); //close for internal case statement
 874       }
 875     }
 876
 877     currCase.append("    default:\n" +
 878                             "       break;\n"+
 879                             "    }}\n"); //internal switch.
 880   }
 881
 882   private boolean qualifiesForCaseStatement(ConcreteRuntimeObjNode node) {
 883     return (
 884         //insetVariable case
 885         (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts()) || node.hasDirectObjConflict) ||
 886         //non-inline-able code cases
 887         (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
 888         //Cases where resumes are possible
 889         (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict);
 890   }
 891
 892   private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
 893       Hashtable<Taint, Set<Effect>> effects) {
 894     Set<Taint> taints = effects.keySet();
 895     for (Taint t : taints) {
 896       FlatSESEEnterNode sese = t.getSESE();
 897       if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
 898         return t;
 899       }
 900     }
 901     return null;
 902   }
 903
 904
 905   private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
 906       Hashtable<Taint, Set<Effect>> effects) {
 907     Set<Taint> taints = effects.keySet();
 908     for (Taint t : taints) {
 909       FlatNode flatnode = t.getStallSite();
 910       if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
 911         return t;
 912       }
 913     }
 914     return null;
 915   }
 916
 917   private void printDebug(boolean guard, String debugStatements) {
 918     if(guard)
 919       System.out.println(debugStatements);
 920   }
 921
 922   private void enumerateHeaproots() {
 923     weaklyConnectedHRCounter = 0;
 924     num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
 925
 926     for(Taint t: connectedHRHash.keySet()) {
 927       if(connectedHRHash.get(t).id == -1) {
 928         WeaklyConectedHRGroup hg = connectedHRHash.get(t);
 929         hg.id = weaklyConnectedHRCounter;
 930         num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
 931         weaklyConnectedHRCounter++;
 932       }
 933
 934       if(t.isRBlockTaint()) {
 935         int id=connectedHRHash.get(t).id;
 936         Tuple tup=new Tuple(t.getVar(),t.getSESE());
 937         if (weakMap.containsKey(tup)) {
 938           if (weakMap.get(tup).intValue()!=id)
 939             throw new Error("Var/SESE not unique for weak component.");
 940         } else
 941             weakMap.put(tup, new Integer(id));
 942       }
 943     }
 944
 945     //output weakly connected groups for verification
 946     if(generalDebug) {
 947       System.out.println("==============Weakly Connected HeapRoots==============");
 948
 949       for(int i=0; i < num2WeaklyConnectedHRGroup.size(); i++){
 950         System.out.println("Heap Group #" + i);
 951         WeaklyConectedHRGroup hg = num2WeaklyConnectedHRGroup.get(i);
 952         for(Taint t: hg.connectedHRs) {
 953           System.out.println("\t" + t);
 954         }
 955       }
 956
 957       System.out.println("=======================END LIST=======================");
 958     }
 959   }
 960
 961   private void printoutTable(EffectsTable table) {
 962
 963     System.out.println("==============EFFECTS TABLE PRINTOUT==============");
 964     for(AllocSite as: table.table.keySet()) {
 965       System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
 966
 967       BucketOfEffects boe = table.table.get(as);
 968
 969       if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
 970         System.out.println("\t\tPotentially conflicting roots: ");
 971         for(String key: boe.potentiallyConflictingRoots.keySet()) {
 972           System.out.println("\t\t-Field: " + key);
 973           System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
 974         }
 975       }
 976       for(Taint t: boe.taint2EffectsGroup.keySet()) {
 977         System.out.println("\t\t For Taint " + t);
 978         EffectsGroup eg = boe.taint2EffectsGroup.get(t);
 979
 980         if(eg.hasPrimitiveConflicts()) {
 981           System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
 982           for(String field: eg.primitiveConflictingFields.keySet()) {
 983             System.out.print(field + " ");
 984           }
 985           System.out.println();
 986         }
 987         for(String fieldKey: eg.myEffects.keySet()) {
 988           CombinedObjEffects ce = eg.myEffects.get(fieldKey);
 989           System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
 990           System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
 991               " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
 992               " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
 993           for(Effect ef: ce.originalEffects) {
 994             System.out.println("\t" + ef);
 995           }
 996         }
 997       }
 998
 999     }
1000
1001   }
1002
1003   private class EffectsGroup {
1004     Hashtable<String, CombinedObjEffects> myEffects;
1005     Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1006
1007     public EffectsGroup() {
1008       myEffects = new Hashtable<String, CombinedObjEffects>();
1009       primitiveConflictingFields = new Hashtable<String, CombinedObjEffects>();
1010     }
1011
1012     public void addPrimitive(Effect e, boolean conflict) {
1013       CombinedObjEffects effects;
1014       if((effects = primitiveConflictingFields.get(e.getField().getSymbol())) == null) {
1015         effects = new CombinedObjEffects();
1016         primitiveConflictingFields.put(e.getField().getSymbol(), effects);
1017       }
1018       effects.add(e, conflict);
1019     }
1020
1021     public void addObjEffect(Effect e, boolean conflict) {
1022       CombinedObjEffects effects;
1023       if((effects = myEffects.get(e.getField().getSymbol())) == null) {
1024         effects = new CombinedObjEffects();
1025         myEffects.put(e.getField().getSymbol(), effects);
1026       }
1027       effects.add(e, conflict);
1028     }
1029
1030     public boolean isEmpty() {
1031       return myEffects.isEmpty() && primitiveConflictingFields.isEmpty();
1032     }
1033
1034     public boolean hasPrimitiveConflicts(){
1035       return !primitiveConflictingFields.isEmpty();
1036     }
1037
1038     public CombinedObjEffects getPrimEffect(String field) {
1039       return primitiveConflictingFields.get(field);
1040     }
1041
1042     public boolean hasObjectEffects() {
1043       return !myEffects.isEmpty();
1044     }
1045
1046     public CombinedObjEffects getObjEffect(String field) {
1047       return myEffects.get(field);
1048     }
1049   }
1050
1051   //Is the combined effects for all effects with the same affectedAllocSite and field
1052   private class CombinedObjEffects {
1053     ArrayList<Effect> originalEffects;
1054
1055     public boolean hasReadEffect;
1056     public boolean hasWriteEffect;
1057     public boolean hasStrongUpdateEffect;
1058
1059     public boolean hasReadConflict;
1060     public boolean hasWriteConflict;
1061     public boolean hasStrongUpdateConflict;
1062
1063
1064     public CombinedObjEffects() {
1065       originalEffects = new ArrayList<Effect>();
1066
1067       hasReadEffect = false;
1068       hasWriteEffect = false;
1069       hasStrongUpdateEffect = false;
1070
1071       hasReadConflict = false;
1072       hasWriteConflict = false;
1073       hasStrongUpdateConflict = false;
1074     }
1075
1076     public boolean add(Effect e, boolean conflict) {
1077       if(!originalEffects.add(e))
1078         return false;
1079
1080       switch(e.getType()) {
1081       case Effect.read:
1082         hasReadEffect = true;
1083         hasReadConflict = conflict;
1084         break;
1085       case Effect.write:
1086         hasWriteEffect = true;
1087         hasWriteConflict = conflict;
1088         break;
1089       case Effect.strongupdate:
1090         hasStrongUpdateEffect = true;
1091         hasStrongUpdateConflict = conflict;
1092         break;
1093       default:
1094         System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
1095         assert false;
1096         break;
1097       }
1098       return true;
1099     }
1100
1101     public boolean hasConflict() {
1102       return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
1103     }
1104
1105     public void mergeWith(CombinedObjEffects other) {
1106       for(Effect e: other.originalEffects) {
1107         if(!originalEffects.contains(e)){
1108           originalEffects.add(e);
1109         }
1110       }
1111
1112       hasReadEffect |= other.hasReadEffect;
1113       hasWriteEffect |= other.hasWriteEffect;
1114       hasStrongUpdateEffect |= other.hasStrongUpdateEffect;
1115
1116       hasReadConflict |= other.hasReadConflict;
1117       hasWriteConflict |= other.hasWriteConflict;
1118       hasStrongUpdateConflict |= other.hasStrongUpdateConflict;
1119     }
1120   }
1121
1122   //This will keep track of a reference
1123   private class ObjRef {
1124     String field;
1125     int allocSite;
1126     CombinedObjEffects myEffects;
1127
1128     //This keeps track of the parent that we need to pass by inorder to get
1129     //to the conflicting child (if there is one).
1130     ConcreteRuntimeObjNode child;
1131
1132     public ObjRef(String fieldname,
1133                   ConcreteRuntimeObjNode ref,
1134                   CombinedObjEffects myEffects) {
1135       field = fieldname;
1136       allocSite = ref.getAllocationSite();
1137       child = ref;
1138
1139       this.myEffects = myEffects;
1140     }
1141
1142     public boolean hasConflictsDownThisPath() {
1143       return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
1144     }
1145
1146     public boolean hasDirectObjConflict() {
1147       return myEffects.hasConflict();
1148     }
1149
1150     public boolean equals(Object other) {
1151       if(other == null || !(other instanceof ObjRef))
1152         return false;
1153
1154       ObjRef o = (ObjRef) other;
1155
1156       if(o.field == this.field && o.allocSite == this.allocSite && this.child.equals(o.child))
1157         return true;
1158
1159       return false;
1160     }
1161
1162     public int hashCode() {
1163       return child.allocSite.hashCode() ^ field.hashCode();
1164     }
1165
1166     public void mergeWith(ObjRef ref) {
1167       myEffects.mergeWith(ref.myEffects);
1168     }
1169   }
1170
1171   private class ConcreteRuntimeObjNode {
1172     Hashtable<String, ObjRefList> objectRefs;
1173     Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1174     HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
1175     HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
1176     //this set keeps track of references down the line that need to be enqueued if traverser is "paused"
1177     HashSet<ConcreteRuntimeObjNode> enqueueToWaitingQueueUponConflict;
1178     boolean decendantsPrimConflict;
1179     boolean decendantsObjConflict;
1180     boolean hasDirectObjConflict;
1181     boolean hasPotentialToBeIncorrectDueToConflict;
1182     boolean isInsetVar;
1183     AllocSite allocSite;
1184     HeapRegionNode original;
1185
1186     public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar) {
1187       objectRefs = new Hashtable<String, ObjRefList>(5);
1188       primitiveConflictingFields = null;
1189       parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
1190       parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
1191       enqueueToWaitingQueueUponConflict = new HashSet<ConcreteRuntimeObjNode>();
1192       allocSite = me.getAllocSite();
1193       original = me;
1194       isInsetVar = isInVar;
1195       decendantsPrimConflict = false;
1196       decendantsObjConflict = false;
1197       hasDirectObjConflict = false;
1198       hasPotentialToBeIncorrectDueToConflict = false;
1199     }
1200
1201     public void addReachableParent(ConcreteRuntimeObjNode curr) {
1202       parentsWithReadToNode.add(curr);
1203     }
1204
1205     @Override
1206     public boolean equals(Object other) {
1207       if(other == null || !(other instanceof ConcreteRuntimeObjNode))
1208         return false;
1209
1210       return original.equals(((ConcreteRuntimeObjNode)other).original);
1211     }
1212
1213     public int getAllocationSite() {
1214       return allocSite.getUniqueAllocSiteID();
1215     }
1216
1217     public int getNumOfReachableParents() {
1218       return parentsThatWillLeadToConflicts.size();
1219     }
1220
1221     public boolean hasPrimitiveConflicts() {
1222       return primitiveConflictingFields != null && !primitiveConflictingFields.isEmpty();
1223     }
1224
1225     public boolean decendantsConflict() {
1226       return decendantsPrimConflict || decendantsObjConflict;
1227     }
1228
1229     //returns true if at least one of the objects in points of access has been added
1230     public boolean addPossibleWaitingQueueEnqueue(HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
1231       boolean addedNew = false;
1232       for(ConcreteRuntimeObjNode dec: pointsOfAccess) {
1233         if(dec != null && dec != this){
1234           addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec);
1235         }
1236       }
1237
1238       return addedNew;
1239     }
1240
1241     public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) {
1242       if(pointOfAccess != null && pointOfAccess != this){
1243         return enqueueToWaitingQueueUponConflict.add(pointOfAccess);
1244       }
1245
1246       return false;
1247     }
1248
1249     public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
1250       printDebug(traceDataStructureBuild,this.allocSite.getUniqueAllocSiteID() + " added child at " + child.getAllocationSite());
1251       hasDirectObjConflict |= ce.hasConflict();
1252       ObjRef ref = new ObjRef(field, child, ce);
1253
1254       if(objectRefs.containsKey(field)){
1255         ObjRefList array = objectRefs.get(field);
1256
1257         if(array.contains(ref)) {
1258           ObjRef other = array.get(array.indexOf(ref));
1259           other.mergeWith(ref);
1260           printDebug(traceDataStructureBuild,"    Merged with old");
1261           printDebug(traceDataStructureBuild,"    Old="+ other.child.original + "\n    new="+ref.child.original);
1262         }
1263         else {
1264           array.add(ref);
1265           printDebug(traceDataStructureBuild,"    Just added new;\n      Field: " + field);
1266           printDebug(traceDataStructureBuild,"      AllocSite: " + child.getAllocationSite());
1267           printDebug(traceDataStructureBuild,"      Child: "+child.original);
1268         }
1269       }
1270       else {
1271         ObjRefList array = new ObjRefList(3);
1272
1273         array.add(ref);
1274         objectRefs.put(field, array);
1275       }
1276     }
1277
1278     public boolean isArray() {
1279       return original.getType().isArray();
1280     }
1281
1282     public ArrayList<Integer> getReferencedAllocSites() {
1283       ArrayList<Integer> list = new ArrayList<Integer>();
1284
1285       for(String key: objectRefs.keySet()) {
1286         for(ObjRef r: objectRefs.get(key)) {
1287           if(r.hasDirectObjConflict() || (r.child.parentsWithReadToNode.contains(this) && r.hasConflictsDownThisPath())) {
1288             list.add(r.allocSite);
1289           }
1290         }
1291       }
1292
1293       return list;
1294     }
1295
1296     public String toString() {
1297       return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
1298               " decCon="+decendantsObjConflict+
1299               " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
1300     }
1301   }
1302
1303   //Simple extension of the ArrayList to allow it to find if any ObjRefs conflict.
1304   private class ObjRefList extends ArrayList<ObjRef> {
1305     private static final long serialVersionUID = 326523675530835596L;
1306
1307     public ObjRefList(int size) {
1308       super(size);
1309     }
1310
1311     public boolean add(ObjRef o){
1312       return super.add(o);
1313     }
1314
1315     public boolean hasConflicts() {
1316       for(ObjRef r: this) {
1317         if(r.hasConflictsDownThisPath() || r.child.hasPrimitiveConflicts())
1318           return true;
1319       }
1320
1321       return false;
1322     }
1323   }
1324
1325   private class EffectsTable {
1326     private Hashtable<AllocSite, BucketOfEffects> table;
1327
1328     public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1329         Hashtable<Taint, Set<Effect>> conflicts) {
1330       table = new Hashtable<AllocSite, BucketOfEffects>();
1331
1332       // rehash all effects (as a 5-tuple) by their affected allocation site
1333       for (Taint t : effects.keySet()) {
1334         Set<Effect> localConflicts = conflicts.get(t);
1335         for (Effect e : effects.get(t)) {
1336           BucketOfEffects bucket;
1337           if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1338             bucket = new BucketOfEffects();
1339             table.put(e.getAffectedAllocSite(), bucket);
1340           }
1341           printDebug(printEffectsAndEffectsTable, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts);
1342           bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1343         }
1344       }
1345     }
1346
1347     public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1348       //This would get the proper bucket of effects and then get all the effects
1349       //for a parent for a specific taint
1350       try {
1351         return table.get(parentKey).taint2EffectsGroup.get(taint);
1352       }
1353       catch (NullPointerException e) {
1354         return null;
1355       }
1356     }
1357
1358     // Run Analysis will walk the data structure and figure out the weakly
1359     // connected heap roots.
1360     public void runAnalysis() {
1361       if(printEffectsAndEffectsTable) {
1362         printoutTable(this);
1363       }
1364
1365       for(AllocSite key: table.keySet()) {
1366         BucketOfEffects effects = table.get(key);
1367         //make sure there are actually conflicts in the bucket
1368         if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1369           for(String field: effects.potentiallyConflictingRoots.keySet()){
1370             ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1371             //For simplicity, we just create a new group and add everything to it instead of
1372             //searching through all of them for the largest group and adding everyone in.
1373             WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1374             group.add(taints); //This will automatically add the taint to the connectedHRhash
1375           }
1376         }
1377       }
1378     }
1379   }
1380
1381   private class WeaklyConectedHRGroup {
1382     HashSet<Taint> connectedHRs;
1383     //This is to keep track of unique waitingQueue positions for each allocsite.
1384     Hashtable<AllocSite, Integer> allocSiteToWaitingQueueMap;
1385     int waitingQueueCounter;
1386     int id;
1387
1388     public WeaklyConectedHRGroup() {
1389       connectedHRs = new HashSet<Taint>();
1390       id = -1; //this will be later modified
1391       waitingQueueCounter = 0;
1392       allocSiteToWaitingQueueMap = new Hashtable<AllocSite, Integer>();
1393     }
1394
1395     public void add(ArrayList<Taint> list) {
1396       for(Taint t: list) {
1397         this.add(t);
1398       }
1399     }
1400
1401     public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) {
1402       if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) {
1403         return allocSiteToWaitingQueueMap.get(node.allocSite);
1404       } else {
1405         allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter);
1406         return waitingQueueCounter++;
1407       }
1408     }
1409
1410     public void add(Taint t) {
1411       connectedHRs.add(t);
1412       WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1413       connectedHRHash.put(t, this); //put new group into hash
1414       //If the taint was already in another group, move all its buddies over.
1415       if(oldGroup != this && oldGroup != null) {
1416         Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1417         Taint relatedTaint;
1418
1419         while(it.hasNext() && (relatedTaint = it.next()) != null) {
1420           if(!connectedHRs.contains(relatedTaint)){
1421             this.add(relatedTaint);
1422           }
1423         }
1424       }
1425     }
1426   }
1427
1428   //This is a class that stores all the effects for an affected allocation site
1429   //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1430   //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1431   //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1432   //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1433   //field.
1434   private class BucketOfEffects {
1435     // This table is used for lookup while creating the traversal.
1436     Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1437
1438     //This table is used to help identify weakly connected groups: Contains ONLY
1439     //conflicting effects AND is only initialized when needed
1440     //String stores the field
1441     Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1442
1443     public BucketOfEffects() {
1444       taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1445     }
1446
1447     public void add(Taint t, Effect e, boolean conflict) {
1448       EffectsGroup effectsForGivenTaint;
1449
1450       if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1451         effectsForGivenTaint = new EffectsGroup();
1452         taint2EffectsGroup.put(t, effectsForGivenTaint);
1453       }
1454
1455       if (isReallyAPrimitive(e.getField().getType())) {
1456         if (conflict) {
1457           effectsForGivenTaint.addPrimitive(e, true);
1458         }
1459       } else {
1460         effectsForGivenTaint.addObjEffect(e, conflict);
1461       }
1462
1463       if(conflict) {
1464         if(potentiallyConflictingRoots == null) {
1465           potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1466         }
1467
1468         ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1469         if(taintsForField == null) {
1470           taintsForField = new ArrayList<Taint>();
1471           potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1472         }
1473
1474         if(!taintsForField.contains(t)) {
1475           taintsForField.add(t);
1476         }
1477       }
1478     }
1479   }
1480
1481   private class TaintAndInternalHeapStructure {
1482     public Taint t;
1483     public Hashtable<Integer, ConcreteRuntimeObjNode> nodesInHeap;
1484
1485     public TaintAndInternalHeapStructure(Taint taint, Hashtable<Integer, ConcreteRuntimeObjNode> nodesInHeap) {
1486       t = taint;
1487       this.nodesInHeap = nodesInHeap;
1488     }
1489   }
1490
1491   private class TraversalInfo {
1492     public FlatNode f;
1493     public ReachGraph rg;
1494     public TempDescriptor invar;
1495
1496     public TraversalInfo(FlatNode fn, ReachGraph g) {
1497       f = fn;
1498       rg =g;
1499       invar = null;
1500     }
1501
1502     public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) {
1503       f = fn;
1504       rg =rg2;
1505       invar = tempDesc;
1506     }
1507   }
1508 }