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