Robust/src/IR/Flat/RuntimeConflictResolver.java

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