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