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