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