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