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