Robust/src/IR/Flat/RuntimeConflictResolver.java

   1 package IR.Flat;
   2
   3 import java.io.File;
   4 import java.io.FileNotFoundException;
   5 import java.io.PrintWriter;
   6 import java.util.ArrayList;
   7 import java.util.HashSet;
   8 import java.util.Hashtable;
   9 import java.util.Iterator;
  10 import java.util.Set;
  11 import Analysis.Disjoint.*;
  12 import IR.TypeDescriptor;
  13
  14 //TODO: the below may be outdated.
  15 /* An instance of this class manages all OoOJava coarse-grained runtime conflicts
  16  * by generating C-code to either rule out the conflict at runtime or resolve one.
  17  *
  18  * How to Use:
  19  * 1) Instantiate singleton object
  20  * 2a) Call void traverse(FlatSESEEnterNode rblock, Hashtable<Taint, Set<Effect>> effects, Hashtable<Taint, Set<Effect>> conflicts, ReachGraph rg)
  21  *    as many times as needed
  22  * 2b) call String getTraverserInvocation(TempDescriptor invar, String varString, FlatSESEEnterNode sese) to get the name of the traverse method in C
  23  * 3) Call void close()
  24  */
  25 public class RuntimeConflictResolver {
  26   public static final boolean javaDebug = true;
  27   public static final boolean cSideDebug = true;
  28
  29   private PrintWriter cFile;
  30   private PrintWriter headerFile;
  31   private static final String hashAndQueueCFileDir = "oooJava/";
  32   //This keeps track of taints we've traversed to prevent printing duplicate traverse functions
  33   //TODO change it to keep track of traverser ID as well
  34   private Hashtable<Taint, Integer> doneTaints;
  35
  36   // initializing variables can be found in printHeader()
  37   private static final String getAllocSiteInC = "->allocsite";
  38   private static final String queryAndAddHashTableInC = "hashRCRInsert(";
  39   private static final String addToQueueInC = "enqueueRCRQueue(";
  40   private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
  41
  42   private static final String clearQueue = "resetRCRQueue()";
  43   // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
  44   private static final String mallocHashTable = "hashRCRCreate(1024, 0.25)";
  45   private static final String deallocHashTable = "hashRCRDelete()";
  46   private static final String resetHashTable = "hashRCRreset()";
  47
  48   // hashtable provides fast access to heaproot # lookups
  49   private Hashtable<Taint, WeaklyConectedHRGroup> connectedHRHash;
  50   private int traverserIDCounter;
  51
  52   public RuntimeConflictResolver(String buildir) throws FileNotFoundException {
  53     String outputFile = buildir + "RuntimeConflictResolver";
  54
  55     cFile = new PrintWriter(new File(outputFile + ".c"));
  56     headerFile = new PrintWriter(new File(outputFile + ".h"));
  57
  58     cFile.append("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
  59         + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>\n");
  60     cFile.append("#include \"classdefs.h\"\n");
  61     cFile.append("#include \"RuntimeConflictResolver.h\"\n");
  62
  63     headerFile.append("#ifndef __3_RCR_H_\n");
  64     headerFile.append("#define __3_RCR_H_\n");
  65     //TODO more closely integrate this by asking generic type from other components?
  66     //generic cast struct
  67     cFile.append("struct genericObjectStruct {int type; int oid; int allocsite; int ___cachedCode___; int ___cachedHash___;};\n");
  68
  69     doneTaints = new Hashtable<Taint, Integer>();
  70     connectedHRHash = new Hashtable<Taint, WeaklyConectedHRGroup>();
  71
  72     traverserIDCounter = 1;
  73   }
  74
  75   //TODO update basic steps.
  76   /*
  77    * Basic steps:
  78    * 1) Create a hashed Effects Lookup Table (hashed by affected allocsite and then taint).
  79    *     1a) Use effects sets to verify if we can access something (reads)
  80    *     1b) Use conflicts list to mark conflicts
  81    * 2) Build runtime representation of data structure
  82    *     2a) Mark conflicts with 2 flags (one for self, one for references down the line)
  83    * 3) Printout via traversing data structure created in previous step.
  84    *
  85    */
  86
  87   //TODO ask YongHun if all these effects/conflicts are global, meaning they include stallsites
  88   //and all SESEblocks.
  89   public void traverseSESEBlock(FlatSESEEnterNode rblock,
  90       Hashtable<Taint, Set<Effect>> effects,
  91       Hashtable<Taint, Set<Effect>> conflicts,
  92       ReachGraph rg) {
  93     Set<TempDescriptor> inVars = rblock.getInVarSet();
  94     EffectsTable effectsLookupTable = new EffectsTable(effects, conflicts);
  95
  96     if (inVars.size() == 0)
  97       return;
  98
  99     // For every non-primitive variable, generate unique method
 100     // Special Note: The Criteria for executing printCMethod in this loop should match
 101     // exactly the criteria in buildcode.java to invoke the generated C method(s).
 102     for (TempDescriptor invar : inVars) {
 103       TypeDescriptor type = invar.getType();
 104       if(type == null || type.isPrimitive()) {
 105         continue;
 106       }
 107
 108       //created stores nodes with specific alloc sites that have been traversed while building
 109       //internal data structure. It is later traversed sequentially to find inset variables and
 110       //build output code.
 111       Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
 112       VariableNode varNode = rg.getVariableNodeNoMutation(invar);
 113
 114       Taint taint = getProperTaintForFlatSESEEnterNode(rblock, varNode, effects);
 115       if (taint == null) {
 116         printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + rblock.toPrettyString());
 117         return;
 118       }
 119
 120       //This is to prevent duplicate from being generated
 121       if(doneTaints.containsKey(taint) && doneTaints.get(taint) != null)
 122         return;
 123
 124       doneTaints.put(taint, traverserIDCounter++);
 125
 126       createConcreteGraph(effectsLookupTable, created, varNode, taint);
 127
 128       if (!created.isEmpty()) {
 129         rblock.addInVarForDynamicCoarseConflictResolution(invar);
 130         printCMethods(created, invar.getSafeSymbol(), rblock.getPrettyIdentifier());
 131       }
 132     }
 133   }
 134
 135   public void traverseStallSite(
 136       FlatNode enterNode,
 137       TempDescriptor invar,
 138       Hashtable<Taint, Set<Effect>> effects,
 139       Hashtable<Taint, Set<Effect>> conflicts,
 140       ReachGraph rg) {
 141     TypeDescriptor type = invar.getType();
 142     if(type == null || type.isPrimitive()) {
 143       return;
 144     }
 145
 146     Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
 147     VariableNode varNode = rg.getVariableNodeNoMutation(invar);
 148     Taint taint = getProperTaintForEnterNode(enterNode, varNode, effects);
 149     EffectsTable effectsLookupTable = new EffectsTable(effects, conflicts);
 150
 151     if (taint == null) {
 152       printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + enterNode.toString());
 153       return;
 154     }
 155
 156     if(doneTaints.containsKey(taint) && doneTaints.get(taint) != null)
 157       return;
 158
 159     doneTaints.put(taint, traverserIDCounter++);
 160
 161     createConcreteGraph(effectsLookupTable, created, varNode, taint);
 162
 163     if (!created.isEmpty()) {
 164       printCMethods(created, invar.getSafeSymbol(), enterNode.toString());
 165     }
 166
 167   }
 168
 169   //TODO replace this with new format of passing in a starting variable and a traverser ID
 170   public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
 171     String flatname;
 172     if(fn instanceof FlatSESEEnterNode) {
 173       flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
 174     }
 175     else {
 176       flatname = fn.toString();
 177     }
 178
 179     return "traverse___" + removeInvalidChars(invar.getSafeSymbol()) +
 180     removeInvalidChars(flatname) + "___("+varString+");";
 181   }
 182
 183   public String removeInvalidChars(String in) {
 184     StringBuilder s = new StringBuilder(in);
 185     for(int i = 0; i < s.length(); i++) {
 186       if(s.charAt(i) == ' ' || s.charAt(i) == '.' || s.charAt(i) == '=') {
 187         s.deleteCharAt(i);
 188         i--;
 189       }
 190     }
 191     return s.toString();
 192   }
 193
 194   public void close() {
 195     // Adds Extra supporting methods
 196     cFile.append("void initializeStructsRCR() { " + mallocHashTable + "; " + clearQueue + "; }");
 197     cFile.append("void destroyRCR() { " + deallocHashTable + "; }\n");
 198
 199     headerFile.append("void initializeStructsRCR(); \nvoid destroyRCR(); \n");
 200     headerFile.append("#endif\n");
 201
 202     cFile.close();
 203     headerFile.close();
 204   }
 205
 206   private void createConcreteGraph(
 207       EffectsTable table,
 208       Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
 209       VariableNode varNode,
 210       Taint t) {
 211
 212     // if table is null that means there's no conflicts, therefore we need not
 213     // create a traversal
 214     if (table == null)
 215       return;
 216
 217     //TODO restore debug functionality
 218 //    if(javaDebug) {
 219 //      printLookupTableDebug(table);
 220 //    }
 221
 222     Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
 223
 224     while (possibleEdges.hasNext()) {
 225       RefEdge edge = possibleEdges.next();
 226       assert edge != null;
 227
 228       ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true);
 229       AllocSite rootKey = singleRoot.allocSite;
 230
 231       if (!created.containsKey(rootKey)) {
 232         created.put(rootKey, singleRoot);
 233         createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table, t);
 234       }
 235     }
 236   }
 237
 238
 239   //This code is the old way of generating an effects lookup table.
 240   //The new way is to instantiate an EffectsGroup
 241   private Hashtable<AllocSite, EffectsGroup> generateEffectsLookupTable(
 242       Taint taint, Hashtable<Taint,
 243       Set<Effect>> effects,
 244       Hashtable<Taint, Set<Effect>> conflicts) {
 245     if(taint == null)
 246       return null;
 247
 248     Set<Effect> localEffects = effects.get(taint);
 249     Set<Effect> localConflicts = conflicts.get(taint);
 250
 251     //Debug Code for manually checking effects
 252     if(javaDebug) {
 253       printEffectsAndConflictsSets(taint, localEffects, localConflicts);
 254     }
 255
 256     if (localEffects == null || localEffects.isEmpty() || localConflicts == null || localConflicts.isEmpty())
 257       return null;
 258
 259     Hashtable<AllocSite, EffectsGroup> lookupTable = new Hashtable<AllocSite, EffectsGroup>();
 260
 261     for (Effect e : localEffects) {
 262       boolean conflict = localConflicts.contains(e);
 263       AllocSite key = e.getAffectedAllocSite();
 264       EffectsGroup myEffects = lookupTable.get(key);
 265
 266       if(myEffects == null) {
 267         myEffects = new EffectsGroup();
 268         lookupTable.put(key, myEffects);
 269       }
 270
 271       if(e.getField().getType().isPrimitive()) {
 272         if(conflict) {
 273           myEffects.addPrimative(e);
 274         }
 275       }
 276       else {
 277         myEffects.addObjEffect(e, conflict);
 278       }
 279     }
 280
 281     return lookupTable;
 282   }
 283
 284   // Plan is to add stuff to the tree depth-first sort of way. That way, we can
 285   // propagate up conflicts
 286   private void createHelper(ConcreteRuntimeObjNode curr,
 287                             Iterator<RefEdge> edges,
 288                             Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
 289                             EffectsTable table,
 290                             Taint taint) {
 291     assert table != null;
 292     AllocSite parentKey = curr.allocSite;
 293     EffectsGroup currEffects = table.getEffects(parentKey, taint);
 294
 295     if (currEffects == null || currEffects.isEmpty())
 296       return;
 297
 298     //Handle Objects (and primitive conflict flag propagation)
 299     if(currEffects.hasObjectEffects()) {
 300       while(edges.hasNext()) {
 301         RefEdge edge = edges.next();
 302         String field = edge.getField();
 303         CombinedObjEffects effectsForGivenField = currEffects.getObjEffect(field);
 304         //If there are no effects, then there's no point in traversing this edge
 305         if(effectsForGivenField != null) {
 306           HeapRegionNode childHRN = edge.getDst();
 307           AllocSite childKey = childHRN.getAllocSite();
 308           boolean isNewChild = !created.containsKey(childKey);
 309           ConcreteRuntimeObjNode child;
 310
 311           if(isNewChild) {
 312             child = new ConcreteRuntimeObjNode(childHRN, false);
 313             created.put(childKey, child);
 314           }
 315           else {
 316             child = created.get(childKey);
 317           }
 318
 319           curr.addObjChild(field, child, effectsForGivenField);
 320
 321           if (effectsForGivenField.hasConflict()) {
 322             propogateObjConflictFlag(curr);
 323           }
 324
 325           if(effectsForGivenField.hasReadEffect) {
 326             child.addReachableParent(curr);
 327
 328             //If isNewChild, flag propagation will be handled at recursive call
 329             if(isNewChild) {
 330               createHelper(child, childHRN.iteratorToReferencees(), created, table, taint);
 331             }
 332             else {
 333               if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) {
 334                 propogatePrimConflictFlag(child);
 335               }
 336
 337               if(child.decendantsObjConflict) {
 338                 propogateObjConflictFlag(child);
 339               }
 340             }
 341           }
 342         }
 343       }
 344     }
 345
 346     //Handles primitives
 347     if(currEffects.hasPrimativeConflicts()) {
 348       curr.conflictingPrimitiveFields = currEffects.primativeConflictingFields;
 349       propogatePrimConflictFlag(curr);
 350     }
 351   }
 352
 353   // This will propagate the conflict up the data structure.
 354   private void propogateObjConflictFlag(ConcreteRuntimeObjNode curr) {
 355     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 356       if(curr.parentsThatWillLeadToConflicts.add(referencer)) {
 357         referencer.decendantsObjConflict = true;
 358         propogateObjConflictFlag(referencer);
 359       }
 360     }
 361   }
 362
 363   private void propogatePrimConflictFlag(ConcreteRuntimeObjNode curr) {
 364     for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
 365       if(curr.parentsThatWillLeadToConflicts.add(referencer)) {
 366         referencer.decendantsPrimConflict = true;
 367         propogatePrimConflictFlag(referencer);
 368       }
 369     }
 370   }
 371
 372   /*
 373    * This method generates a C method for every inset variable and rblock.
 374    *
 375    * The C method works by generating a large switch statement that will run the appropriate
 376    * checking code for each object based on its allocation site. The switch statement is
 377    * surrounded by a while statement which dequeues objects to be checked from a queue. An
 378    * object is added to a queue only if it contains a conflict (in itself or in its referencees)
 379    *  and we came across it while checking through it's referencer. Because of this property,
 380    *  conflicts will be signaled by the referencer; the only exception is the inset variable which can
 381    *  signal a conflict within itself.
 382    */
 383   private void printCMethods(Hashtable<AllocSite, ConcreteRuntimeObjNode> created, String inVar, String rBlock) {
 384     //This hash table keeps track of all the case statements generated. Although it may seem a bit much
 385     //for its purpose, I think it may come in handy later down the road to do it this way.
 386     //(i.e. what if we want to eliminate some cases? Or build filter for 1 case)
 387     Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
 388
 389     //Generate C cases
 390     for (ConcreteRuntimeObjNode node : created.values()) {
 391       if (!cases.containsKey(node.allocSite) && (
 392           //insetVariable case
 393           (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 394           //non-inline-able code cases
 395           (node.getNumOfReachableParents() != 1 && node.decendantsConflict()))) {
 396
 397         printDebug(javaDebug, node.allocSite + " qualified for case statement");
 398         addChecker(node, cases, null, "ptr", 0);
 399       }
 400     }
 401     //IMPORTANT: remember to change getTraverserInvocation if you change the line below
 402     String methodName = "void traverse___" + removeInvalidChars(inVar) +
 403                         removeInvalidChars(rBlock) + "___(void * InVar)";
 404
 405     cFile.append(methodName + " {\n");
 406     headerFile.append(methodName + ";\n");
 407
 408     if(cSideDebug) {
 409       cFile.append("printf(\"The traverser ran for " + methodName + "\\n\");\n");
 410     }
 411
 412     if(cases.size() == 0) {
 413       cFile.append(" return; }");
 414     }
 415     else {
 416       //Casts the ptr to a genericObjectStruct so we can get to the ptr->allocsite field.
 417       cFile.append("struct genericObjectStruct * ptr = (struct genericObjectStruct *) InVar;  if(InVar != NULL) { " + queryAndAddHashTableInC
 418           + "ptr); do { ");
 419
 420       cFile.append("switch(ptr->allocsite) { ");
 421
 422       for(AllocSite singleCase: cases.keySet())
 423         cFile.append(cases.get(singleCase));
 424
 425       cFile.append(" default : break; ");
 426       cFile.append("}} while( (ptr = " + dequeueFromQueueInC + ") != NULL); ");
 427
 428       //Closes the method by clearing the Queue and reseting the hashTable to prevent
 429       //overhead from freeing and mallocing the structures.
 430       cFile.append(clearQueue + "; " + resetHashTable + "; }}\n");
 431     }
 432     cFile.flush();
 433   }
 434
 435   /*
 436    * addChecker creates a case statement for every object that is either an inset variable
 437    * or has multiple referencers (incoming edges). Else it just prints the checker for that object
 438    * so that its processing can be pushed up to the referencer node.
 439    */
 440   private void addChecker(ConcreteRuntimeObjNode node,
 441                           Hashtable<AllocSite,StringBuilder> cases,
 442                           StringBuilder possibleContinuingCase,
 443                           String prefix,
 444                           int depth) {
 445     StringBuilder currCase = possibleContinuingCase;
 446     // We don't need a case statement for things with either 1 incoming or 0 out
 447     // going edges, because they can be processed when checking the parent.
 448
 449     if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 450        (node.getNumOfReachableParents() != 1 && node.decendantsConflict())) {
 451       assert prefix.equals("ptr") && !cases.containsKey(node.allocSite);
 452       currCase = new StringBuilder();
 453       cases.put(node.allocSite, currCase);
 454       currCase.append("case " + node.getAllocationSite() + ":\n { ");
 455     }
 456     //either currCase is continuing off a parent case or is its own.
 457     assert currCase !=null;
 458
 459     //Specific Primitives test for invars
 460     if(node.isInsetVar && node.hasPrimitiveConflicts()) {
 461       handlePrimitiveConflict(currCase, prefix, node.conflictingPrimitiveFields, node.allocSite);
 462     }
 463
 464     //Casts C pointer; depth is used to create unique "myPtr" name for when things are inlined
 465     String currPtr = "myPtr" + depth;
 466     String structType = node.original.getType().getSafeSymbol();
 467     currCase.append("struct " + structType + " * "+currPtr+"= (struct "+ structType + " * ) " + prefix + "; ");
 468
 469     //Handles Objects
 470     for (ObjRef ref : node.objectRefs) {
 471       // Will only process edge if there is some sort of conflict with the Child
 472       if (ref.hasConflictsDownThisPath()) {
 473         String childPtr = currPtr +"->___" + ref.field + "___";
 474
 475         // Checks if the child exists and has allocsite matching the conflict
 476         currCase.append("if(" + childPtr + " != NULL && " + childPtr + getAllocSiteInC + "=="
 477             + ref.allocSite + ") { ");
 478
 479         // Prints out conflicts of child
 480         if (ref.hasDirectObjConflict()) {
 481           handleObjConflict(currCase, childPtr, node.allocSite, ref);
 482         }
 483
 484         if(ref.child.hasPrimitiveConflicts()) {
 485           handlePrimitiveConflict(currCase, childPtr, ref.child.conflictingPrimitiveFields, ref.child.allocSite);
 486         }
 487
 488         if (ref.child.decendantsConflict()) {
 489           // Checks if we have visited the child before
 490           currCase.append("if(" + queryAndAddHashTableInC + childPtr + ")) { ");
 491           if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
 492             addChecker(ref.child, cases, currCase, childPtr, depth + 1);
 493           }
 494           else {
 495             currCase.append(addToQueueInC + childPtr + ");");
 496           }
 497
 498           currCase.append(" } ");
 499         }
 500         currCase.append(" } ");
 501       }
 502     }
 503
 504     if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
 505         (node.getNumOfReachableParents() != 1 && node.decendantsConflict())) {
 506       currCase.append(" } break; \n");
 507     }
 508   }
 509
 510   private void handleObjConflict(StringBuilder currCase, String childPtr, AllocSite allocSite, ObjRef ref) {
 511     currCase.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.getUniqueAllocSiteID() + ");");
 512   }
 513
 514   private void handlePrimitiveConflict(StringBuilder currCase, String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
 515     currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); ");
 516   }
 517
 518   private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
 519       Hashtable<Taint, Set<Effect>> effects) {
 520     Set<Taint> taints = effects.keySet();
 521     for (Taint t : taints) {
 522       FlatSESEEnterNode sese = t.getSESE();
 523       if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
 524         return t;
 525       }
 526     }
 527     return null;
 528   }
 529
 530   private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
 531       Hashtable<Taint, Set<Effect>> effects) {
 532     Set<Taint> taints = effects.keySet();
 533     for (Taint t : taints) {
 534       FlatNode flatnode = t.getStallSite();
 535       if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
 536         return t;
 537       }
 538     }
 539     return null;
 540   }
 541
 542   private void printEffectsAndConflictsSets(Taint taint, Set<Effect> localEffects,
 543       Set<Effect> localConflicts) {
 544     System.out.println("#### List of Effects/Conflicts ####");
 545     System.out.println("For Taint " + taint);
 546     System.out.println("Effects");
 547     if(localEffects != null) {
 548       for(Effect e: localEffects) {
 549        System.out.println(e);
 550       }
 551     }
 552     System.out.println("Conflicts");
 553     if(localConflicts != null) {
 554       for(Effect e: localConflicts) {
 555         System.out.println(e);
 556       }
 557     }
 558   }
 559
 560   private void printLookupTableDebug(Hashtable<AllocSite, EffectsGroup> table) {
 561     System.out.println("==========Table print out============");
 562       System.out.print("    Key is effect Exists/Conflict\n");
 563       for(AllocSite allockey: table.keySet()) {
 564         EffectsGroup eg= table.get(allockey);
 565         if(eg.hasPrimativeConflicts()) {
 566           System.out.print("Primitive Conflicts at alloc " + allockey.getUniqueAllocSiteID() +" : ");
 567           for(String field: eg.primativeConflictingFields) {
 568             System.out.print(field + " ");
 569           }
 570           System.out.println();
 571         }
 572         for(String fieldKey: eg.myEffects.keySet()) {
 573           CombinedObjEffects ce = eg.myEffects.get(fieldKey);
 574           System.out.println("\nFor allocSite " + allockey.getUniqueAllocSiteID() + " && field " + fieldKey);
 575           System.out.println("\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
 576               " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
 577               " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
 578           for(Effect ef: ce.originalEffects) {
 579             System.out.println("\t" + ef);
 580           }
 581         }
 582       }
 583       System.out.println("===========End print out=============");
 584   }
 585
 586   private void printDebug(boolean guard, String debugStatements) {
 587     if(guard)
 588       System.out.println(debugStatements);
 589   }
 590
 591   //This will print the traverser invocation that takes in a traverserID and
 592   //starting ptr
 593   public void printMasterTraverserInvocation() {
 594     headerFile.println("\nint traverse(void * startingPtr, int traverserID);");
 595     cFile.println("\nint traverse(void * startingPtr, int traverserID) {" +
 596                 "switch(traverserID) { ");
 597
 598     for(Taint t: doneTaints.keySet()) {
 599       cFile.println("  case: " + doneTaints.get(t));
 600       if(t.isRBlockTaint()) {
 601         cFile.println("    " + this.getTraverserInvocation(t.getVar(), "startingPtr", t.getSESE()));
 602       }
 603       else if (t.isStallSiteTaint()){
 604         cFile.println("    " + this.getTraverserInvocation(t.getVar(), "startingPtr", t.getStallSite()));
 605       } else if(RuntimeConflictResolver.javaDebug) {
 606         System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite.");
 607       }
 608     }
 609
 610     if(RuntimeConflictResolver.cSideDebug) {
 611       cFile.println("default: printf(\" invalid traverser ID %u was passed in.\n\", traverserID); break;");
 612     } else {
 613       cFile.println("default: break;");
 614     }
 615
 616     cFile.println("}}");
 617   }
 618
 619   private class EffectsGroup
 620   {
 621     Hashtable<String, CombinedObjEffects> myEffects;
 622     ArrayList<String> primativeConflictingFields;
 623
 624     public EffectsGroup() {
 625       myEffects = new Hashtable<String, CombinedObjEffects>();
 626       primativeConflictingFields = new ArrayList<String>();
 627     }
 628
 629     public void addPrimative(Effect e) {
 630       primativeConflictingFields.add(e.getField().toPrettyStringBrief());
 631     }
 632
 633     public void addObjEffect(Effect e, boolean conflict) {
 634       CombinedObjEffects effects;
 635       if((effects = myEffects.get(e.getField().getSymbol())) == null) {
 636         effects = new CombinedObjEffects();
 637         myEffects.put(e.getField().getSymbol(), effects);
 638       }
 639       effects.add(e, conflict);
 640     }
 641
 642     public boolean isEmpty() {
 643       return myEffects.isEmpty() && primativeConflictingFields.isEmpty();
 644     }
 645
 646     public boolean hasPrimativeConflicts(){
 647       return !primativeConflictingFields.isEmpty();
 648     }
 649
 650     public boolean hasObjectEffects() {
 651       return !myEffects.isEmpty();
 652     }
 653
 654     public CombinedObjEffects getObjEffect(String field) {
 655       return myEffects.get(field);
 656     }
 657   }
 658
 659   //Is the combined effects for all effects with the same affectedAllocSite and field
 660   private class CombinedObjEffects {
 661     ArrayList<Effect> originalEffects;
 662
 663     public boolean hasReadEffect;
 664     public boolean hasWriteEffect;
 665     public boolean hasStrongUpdateEffect;
 666
 667     public boolean hasReadConflict;
 668     public boolean hasWriteConflict;
 669     public boolean hasStrongUpdateConflict;
 670
 671
 672     public CombinedObjEffects() {
 673       originalEffects = new ArrayList<Effect>();
 674
 675       hasReadEffect = false;
 676       hasWriteEffect = false;
 677       hasStrongUpdateEffect = false;
 678
 679       hasReadConflict = false;
 680       hasWriteConflict = false;
 681       hasStrongUpdateConflict = false;
 682     }
 683
 684     public boolean add(Effect e, boolean conflict) {
 685       if(!originalEffects.add(e))
 686         return false;
 687
 688       switch(e.getType()) {
 689       case Effect.read:
 690         hasReadEffect = true;
 691         hasReadConflict = conflict;
 692         break;
 693       case Effect.write:
 694         hasWriteEffect = true;
 695         hasWriteConflict = conflict;
 696         break;
 697       case Effect.strongupdate:
 698         hasStrongUpdateEffect = true;
 699         hasStrongUpdateConflict = conflict;
 700         break;
 701       default:
 702         System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
 703         assert false;
 704         break;
 705       }
 706       return true;
 707     }
 708
 709     public boolean hasConflict() {
 710       return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
 711     }
 712   }
 713
 714   //This will keep track of a reference
 715   private class ObjRef {
 716     String field;
 717     int allocSite;
 718     CombinedObjEffects myEffects;
 719
 720     //This keeps track of the parent that we need to pass by inorder to get
 721     //to the conflicting child (if there is one).
 722     ConcreteRuntimeObjNode child;
 723
 724     public ObjRef(String fieldname,
 725                   ConcreteRuntimeObjNode ref,
 726                   CombinedObjEffects myEffects) {
 727       field = fieldname;
 728       allocSite = ref.getAllocationSite();
 729       child = ref;
 730
 731       this.myEffects = myEffects;
 732     }
 733
 734     public boolean hasConflictsDownThisPath() {
 735       return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
 736     }
 737
 738     public boolean hasDirectObjConflict() {
 739       return myEffects.hasConflict();
 740     }
 741   }
 742
 743   private class ConcreteRuntimeObjNode {
 744     ArrayList<ObjRef> objectRefs;
 745     ArrayList<String> conflictingPrimitiveFields;
 746     HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
 747     HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
 748     boolean decendantsPrimConflict;
 749     boolean decendantsObjConflict;
 750     boolean isInsetVar;
 751     AllocSite allocSite;
 752     HeapRegionNode original;
 753
 754     public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar) {
 755       objectRefs = new ArrayList<ObjRef>();
 756       conflictingPrimitiveFields = null;
 757       parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
 758       parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
 759       allocSite = me.getAllocSite();
 760       original = me;
 761       isInsetVar = isInVar;
 762       decendantsPrimConflict = false;
 763       decendantsObjConflict = false;
 764     }
 765
 766     public void addReachableParent(ConcreteRuntimeObjNode curr) {
 767       parentsWithReadToNode.add(curr);
 768     }
 769
 770     @Override
 771     public int hashCode() {
 772       // This gets allocsite number
 773       return allocSite.hashCodeSpecific();
 774     }
 775
 776     @Override
 777     public boolean equals(Object obj) {
 778       return original.equals(obj);
 779     }
 780
 781     public int getAllocationSite() {
 782       return allocSite.getUniqueAllocSiteID();
 783     }
 784
 785     public int getNumOfReachableParents() {
 786       return parentsThatWillLeadToConflicts.size();
 787     }
 788
 789     public boolean hasPrimitiveConflicts() {
 790       return conflictingPrimitiveFields != null;
 791     }
 792
 793     public boolean decendantsConflict() {
 794       return decendantsPrimConflict || decendantsObjConflict;
 795     }
 796
 797     public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
 798       ObjRef ref = new ObjRef(field, child, ce);
 799       objectRefs.add(ref);
 800     }
 801
 802     public String toString()
 803     {
 804       return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
 805               " decCon="+decendantsObjConflict+
 806               " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
 807     }
 808   }
 809
 810   private class EffectsTable {
 811     private Hashtable<AllocSite, BucketOfEffects> table;
 812     private boolean analysisComplete;
 813
 814     public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
 815         Hashtable<Taint, Set<Effect>> conflicts) {
 816       table = new Hashtable<AllocSite, BucketOfEffects>();
 817       analysisComplete = false;
 818
 819       // rehash all effects (as a 5-tuple) by their affected allocation site
 820       for (Taint t : effects.keySet()) {
 821         Set<Effect> localConflicts = conflicts.get(t);
 822
 823         for (Effect e : effects.get(t)) {
 824           BucketOfEffects bucket;
 825           if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
 826             bucket = new BucketOfEffects();
 827             table.put(e.getAffectedAllocSite(), bucket);
 828           }
 829           bucket.add(t, e, localConflicts.contains(e));
 830         }
 831       }
 832     }
 833
 834     public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
 835       //This would get the proper bucket of effects and then get all the effects
 836       //for a parent for a specific taint
 837       return table.get(parentKey).effects.get(taint);
 838     }
 839
 840     // Run Analysis will walk the data structure and figure out the weakly
 841     // connected heap roots #'s
 842     public void runAnaylsis() {
 843       if (analysisComplete) {
 844         if (RuntimeConflictResolver.javaDebug) {
 845           System.out.println("Err: runAnaylsis was called twice in EffectsTable");
 846         }
 847         return;
 848       }
 849
 850       //TODO is there a higher performance way to do this?
 851       //walk the structure and put all groups into official groups
 852       for(AllocSite key: table.keySet()) {
 853         BucketOfEffects effects = table.get(key);
 854         //make sure there are actually conflicts in the bucket
 855         if(effects.potentiallyConflictingRoots != null && effects.potentiallyConflictingRoots.size() !=0){
 856           for(String field: effects.potentiallyConflictingRoots.keySet()){
 857             ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
 858             //For simplicity, we just create a new group and add everything to it instead of
 859             //searching through all of them for the largest group and adding everyone in.
 860             WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
 861             group.add(taints); //This will automatically add the taint to the connectedHRhash
 862           }
 863         }
 864       }
 865
 866       //Walk the official groups and assign each a unique number
 867       int counter = 0;
 868       for(Taint t: connectedHRHash.keySet()) {
 869         if(connectedHRHash.get(t).id == -1) {
 870           connectedHRHash.get(t).id = counter++;
 871         }
 872       }
 873     }
 874   }
 875
 876   private class WeaklyConectedHRGroup {
 877     HashSet<Taint> connectedHRs;
 878     int id;
 879
 880     public WeaklyConectedHRGroup() {
 881       connectedHRs = new HashSet<Taint>();
 882       id = -1; //this will be later modified
 883     }
 884
 885     public void add(ArrayList<Taint> list) {
 886       for(Taint t: list) {
 887         this.add(t);
 888       }
 889     }
 890
 891     public void add(Taint t) {
 892       connectedHRs.add(t);
 893       WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
 894       connectedHRHash.put(t, this); //put new group into hash
 895       //If the taint was already in another group, move all its buddies over.
 896       if(oldGroup != this && oldGroup != null) {
 897         Iterator<Taint> it = oldGroup.connectedHRs.iterator();
 898         Taint relatedTaint;
 899
 900         while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) {
 901           this.add(relatedTaint);
 902         }
 903       }
 904     }
 905
 906   }
 907
 908   //This is a class that stores all the effects for an affected allocation site
 909   //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
 910   //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
 911   //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
 912   //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
 913   //field.
 914   private class BucketOfEffects {
 915     // This table is used for lookup while creating the traversal.
 916     Hashtable<Taint, EffectsGroup> effects;
 917
 918     //This table is used to help identify weakly connected groups: Contains ONLY
 919     //conflicting effects AND is only initialized when needed
 920     Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
 921
 922     public BucketOfEffects() {
 923       effects = new Hashtable<Taint, EffectsGroup>();
 924     }
 925
 926     public void add(Taint t, Effect e, boolean conflict) {
 927       EffectsGroup effectsForGivenTaint;
 928
 929       if ((effectsForGivenTaint = effects.get(t)) == null) {
 930         effectsForGivenTaint = new EffectsGroup();
 931         effects.put(t, effectsForGivenTaint);
 932       }
 933
 934       if (e.getField().getType().isPrimitive()) {
 935         if (conflict) {
 936           effectsForGivenTaint.addPrimative(e);
 937         }
 938       } else {
 939         effectsForGivenTaint.addObjEffect(e, conflict);
 940       }
 941
 942
 943       //TODO: Is this what we really want to do for primitives as well?
 944       if(conflict) {
 945         if(potentiallyConflictingRoots == null) {
 946           potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
 947         }
 948
 949         ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField());
 950         if(taintsForField == null) {
 951           taintsForField = new ArrayList<Taint>();
 952           potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
 953         }
 954
 955         if(!taintsForField.contains(t)) {
 956           taintsForField.add(t);
 957         }
 958       }
 959
 960     }
 961   }
 962 }