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