Robust/src/IR/Flat/RuntimeConflictResolver.java

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