Robust/src/IR/Flat/RuntimeConflictResolver.java

   1 package IR.Flat;
   2
   3 import java.io.File;
   4 import java.io.FileNotFoundException;
   5 import java.util.ArrayList;
   6 import java.util.HashSet;
   7 import java.util.Hashtable;
   8 import java.util.Iterator;
   9 import java.util.Set;
  10 import java.util.Vector;
  11 import Util.Pair;
  12 import Analysis.Disjoint.*;
  13 import Analysis.Pointer.*;
  14 import Analysis.Pointer.AllocFactory.AllocNode;
  15 import IR.State;
  16 import IR.TypeDescriptor;
  17 import Analysis.OoOJava.ConflictEdge;
  18 import Analysis.OoOJava.ConflictGraph;
  19 import Analysis.OoOJava.ConflictNode;
  20 import Analysis.OoOJava.OoOJavaAnalysis;
  21 import Util.CodePrinter;
  22
  23 /* An instance of this class manages all OoOJava coarse-grained runtime conflicts
  24  * by generating C-code to either rule out the conflict at runtime or resolve one.
  25  *
  26  * How to Use:
  27  * 1) Instantiate singleton object (String input is to specify output dir)
  28  * 2) Call void close()
  29  */
  30 public class RuntimeConflictResolver {
  31   private CodePrinter headerFile, cFile;
  32   private static final String hashAndQueueCFileDir = "oooJava/";
  33
  34   //This keeps track of taints we've traversed to prevent printing duplicate traverse functions
  35   //The Integer keeps track of the weakly connected group it's in (used in enumerateHeapRoots)
  36   //private Hashtable<Taint, Integer> doneTaints;
  37   private Hashtable<Pair, Integer> idMap=new Hashtable<Pair,Integer>();
  38
  39   //Keeps track of stallsites that we've generated code for.
  40   protected Hashtable <FlatNode, TempDescriptor> processedStallSites = new Hashtable <FlatNode, TempDescriptor>();
  41
  42   public int currentID=1;
  43   private int totalWeakGroups;
  44   private OoOJavaAnalysis oooa;
  45   private State globalState;
  46
  47   // initializing variables can be found in printHeader()
  48   private static final String allocSite = "allocsite";
  49   private static final String queryAndAddToVisitedHashtable = "hashRCRInsert";
  50   private static final String enqueueInC = "enqueueRCRQueue";
  51   private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
  52   private static final String clearQueue = "resetRCRQueue()";
  53   // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
  54   private static final String mallocVisitedHashtable = "hashRCRCreate(128, 0.75)";
  55   private static final String deallocVisitedHashTable = "hashRCRDelete()";
  56   private static final String resetVisitedHashTable = "hashRCRreset()";
  57
  58   public RuntimeConflictResolver(String buildir,
  59                                  OoOJavaAnalysis oooa,
  60                                  State state)
  61   throws FileNotFoundException {
  62     this.oooa         = oooa;
  63     this.globalState  = state;
  64
  65     processedStallSites = new Hashtable <FlatNode, TempDescriptor>();
  66     BuildStateMachines bsm  = oooa.getBuildStateMachines();
  67     totalWeakGroups         = bsm.getTotalNumOfWeakGroups();
  68
  69     setupOutputFiles(buildir);
  70
  71     for( Pair<FlatNode, TempDescriptor> p : bsm.getAllMachineNames() ) {
  72       FlatNode taskOrStallSite      =  p.getFirst();
  73       TempDescriptor var                  =  p.getSecond();
  74       StateMachineForEffects stateMachine         = bsm.getStateMachine(taskOrStallSite, var);
  75
  76       //prints the traversal code
  77       printCMethod(taskOrStallSite, var, stateMachine);
  78     }
  79
  80     //IMPORTANT must call .close() elsewhere to finish printing the C files.
  81   }
  82
  83   /*
  84    * This method generates a C method for every inset variable and rblock.
  85    *
  86    * The C method works by generating a large switch statement that will run the appropriate
  87    * checking code for each object based on the current state. The switch statement is
  88    * surrounded by a while statement which dequeues objects to be checked from a queue. An
  89    * object is added to a queue only if it contains a conflict (in itself or in its referencees)
  90    * and we came across it while checking through it's referencer. Because of this property,
  91    * conflicts will be signaled by the referencer; the only exception is the inset variable which can
  92    * signal a conflict within itself.
  93    */
  94
  95   private void printCMethod(FlatNode taskOrStallSite,
  96                             TempDescriptor var,
  97                             StateMachineForEffects smfe) {
  98
  99     // collect info for code gen
 100     FlatSESEEnterNode task          = null;
 101     String inVar         = var.getSafeSymbol();
 102     SMFEState initialState  = smfe.getInitialState();
 103     boolean isStallSite   = !(taskOrStallSite instanceof FlatSESEEnterNode);
 104     int weakID        = smfe.getWeaklyConnectedGroupID(taskOrStallSite);
 105
 106     String blockName;
 107     //No need generate code for empty traverser
 108     if (smfe.isEmpty())
 109       return;
 110
 111     if( isStallSite ) {
 112       blockName = taskOrStallSite.toString();
 113       processedStallSites.put(taskOrStallSite, var);
 114     } else {
 115       task = (FlatSESEEnterNode) taskOrStallSite;
 116
 117       //if the task is the main task, there's no traverser
 118       if(task.isMainSESE)
 119         return;
 120
 121       blockName = task.getPrettyIdentifier();
 122     }
 123
 124
 125
 126     String methodName = "void traverse___" + inVar + removeInvalidChars(blockName) + "___(void * InVar, ";
 127     int index      = -1;
 128
 129     if( isStallSite ) {
 130       methodName += "SESEstall *record)";
 131     } else {
 132       methodName += task.getSESErecordName() +" *record)";
 133       //TODO check that this HACK is correct (i.e. adding and then polling immediately afterwards)
 134       task.addInVarForDynamicCoarseConflictResolution(var);
 135       index = task.getInVarsForDynamicCoarseConflictResolution().indexOf(var);
 136     }
 137
 138     cFile.println(methodName + " {");
 139     headerFile.println(methodName + ";");
 140
 141     cFile.println("  int totalcount = RUNBIAS;");
 142     if( isStallSite ) {
 143       cFile.println("  record->rcrRecords[0].count = RUNBIAS;");
 144     } else {
 145       cFile.println("  record->rcrRecords["+index+"].count = RUNBIAS;");
 146     }
 147
 148     //clears queue and hashtable that keeps track of where we've been.
 149     cFile.println(clearQueue + ";");
 150     cFile.println(resetVisitedHashTable + ";");
 151     cFile.println("  RCRQueueEntry * queueEntry; //needed for dequeuing");
 152
 153     cFile.println("  int traverserState = "+initialState.getID()+";");
 154
 155     //generic cast to ___Object___ to access ptr->allocsite field.
 156     cFile.println("  struct ___Object___ * ptr = (struct ___Object___ *) InVar;");
 157     cFile.println("  if (InVar != NULL) {");
 158     cFile.println("    " + queryAndAddToVisitedHashtable + "(ptr, "+initialState.getID()+");");
 159     cFile.println("    do {");
 160
 161     if( !isStallSite ) {
 162       cFile.println("      if(unlikely(record->common.doneExecuting)) {");
 163       cFile.println("        record->common.rcrstatus=0;");
 164       cFile.println("        return;");
 165       cFile.println("      }");
 166     }
 167
 168
 169     // Traverse the StateMachineForEffects (a graph)
 170     // that serves as a plan for building the heap examiner code.
 171     // SWITCH on the states in the state machine, THEN
 172     //   SWITCH on the concrete object's allocation site THEN
 173     //     consider conflicts, enqueue more work, inline more SWITCHES, etc.
 174
 175     boolean needswitch=smfe.getStates().size()>1;
 176
 177     if (needswitch) {
 178       cFile.println("  switch( traverserState ) {");
 179     }
 180     for(SMFEState state : smfe.getStates()) {
 181
 182       if(state.getRefCount() != 1 || initialState == state) {
 183         if (needswitch) {
 184           cFile.println("    case "+state.getID()+":");
 185         } else {
 186           cFile.println("  if(traverserState=="+state.getID()+") {");
 187         }
 188
 189         printAllocChecksInsideState(smfe, state, taskOrStallSite, var, "ptr", 0, weakID);
 190
 191         cFile.println("      break;");
 192       }
 193     }
 194
 195     if (needswitch) {
 196       cFile.println("        default: break;");
 197     }
 198     cFile.println("      } // end switch on traverser state");
 199     cFile.println("      queueEntry = " + dequeueFromQueueInC + ";");
 200     cFile.println("      if(queueEntry == NULL) {");
 201     cFile.println("        break;");
 202     cFile.println("      }");
 203     cFile.println("      ptr = queueEntry->object;");
 204     cFile.println("      traverserState = queueEntry->traverserState;");
 205     cFile.println("    } while(ptr != NULL);");
 206     cFile.println("  } // end if inVar not null");
 207
 208
 209     if( isStallSite ) {
 210       cFile.println("  if(atomic_sub_and_test(totalcount,&(record->rcrRecords[0].count))) {");
 211       cFile.println("    psem_give_tag(record->common.parentsStallSem, record->tag);");
 212       cFile.println("    BARRIER();");
 213       cFile.println("  }");
 214     } else {
 215       cFile.println("  if(atomic_sub_and_test(totalcount,&(record->rcrRecords["+index+"].count))) {");
 216       cFile.println("    int flag=LOCKXCHG32(&(record->rcrRecords["+index+"].flag),0);");
 217       cFile.println("    if(flag) {");
 218       //we have resolved a heap root...see if this was the last dependence
 219       cFile.println("      if(atomic_sub_and_test(1, &(record->common.unresolvedDependencies))) workScheduleSubmit((void *)record);");
 220       cFile.println("    }");
 221       cFile.println("  }");
 222     }
 223
 224     cFile.println("}");
 225     cFile.flush();
 226   }
 227
 228   public void printAllocChecksInsideState(StateMachineForEffects smfe, SMFEState state, FlatNode fn, TempDescriptor tmp, String prefix, int depth, int weakID) {
 229     EffectsTable et = new EffectsTable(state);
 230     boolean needswitch=et.getAllAllocs().size()>1;
 231     if (needswitch) {
 232       cFile.println("      switch(" + prefix+"->"+allocSite + ") {");
 233     }
 234
 235     //we assume that all allocs given in the effects are starting locs.
 236     for(Alloc a : et.getAllAllocs()) {
 237       if (needswitch) {
 238         cFile.println("    case "+a.getUniqueAllocSiteID()+": {");
 239       } else {
 240         cFile.println("     if("+prefix+"->"+allocSite+"=="+a.getUniqueAllocSiteID()+") {");
 241       }
 242       addChecker(smfe, a, fn, tmp, state, et, prefix, depth, weakID);
 243       if (needswitch) {
 244         cFile.println("       }");
 245         cFile.println("       break;");
 246       }
 247     }
 248     if (needswitch) {
 249       cFile.println("      default:");
 250       cFile.println("        break;");
 251     }
 252     cFile.println("      }");
 253   }
 254
 255   public void addChecker(StateMachineForEffects smfe, Alloc a, FlatNode fn, TempDescriptor tmp, SMFEState state, EffectsTable et, String prefix, int depth, int weakID) {
 256     if (depth>30) {
 257       System.out.println(fn+"  "+state+" "+state.toStringDOT());
 258     }
 259
 260     insertEntriesIntoHashStructureNew(fn, tmp, et, a, prefix, depth, weakID);
 261
 262     int pdepth = depth+1;
 263
 264     if(a.getType().isArray()) {
 265       String childPtr = "((struct ___Object___ **)(((char *) &(((struct ArrayObject *)"+ prefix+")->___length___))+sizeof(int)))[i]";
 266       String currPtr = "arrayElement" + pdepth;
 267
 268       boolean first=true;
 269
 270       for(Effect e : et.getEffects(a)) {
 271         if (!state.transitionsTo(e).isEmpty()) {
 272           if (first) {
 273             cFile.println("  int i;");
 274             cFile.println("  struct ___Object___ * "+currPtr+";");
 275             cFile.println("  for(i = 0; i<((struct ArrayObject *) " + prefix + " )->___length___; i++ ) {");
 276             first=false;
 277           }
 278           printRefSwitch(smfe, fn, tmp, pdepth, childPtr, currPtr, state.transitionsTo(e), weakID);
 279
 280           // only if we are traversing for a new task, not a stall site
 281           if( (fn instanceof FlatSESEEnterNode) &&
 282               smfe.getPossiblyEvilEffects().contains(e) ) {
 283
 284             FlatSESEEnterNode evilTask = (FlatSESEEnterNode)fn;
 285
 286             detectPossiblyEvilExecution(evilTask,
 287                                         evilTask.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp)
 288                                         );
 289           }
 290         }
 291       }
 292       if (!first)
 293         cFile.println("}");
 294     }  else {
 295       //All other cases
 296       String currPtr = "myPtr" + pdepth;
 297       cFile.println("    struct ___Object___ * "+currPtr+";");
 298
 299       for(Effect e : et.getEffects(a)) {
 300         if (!state.transitionsTo(e).isEmpty()) {
 301           String childPtr = "((struct "+a.getType().getSafeSymbol()+" *)"+prefix +")->" + e.getField().getSafeSymbol();
 302           printRefSwitch(smfe, fn, tmp, pdepth, childPtr, currPtr, state.transitionsTo(e), weakID);
 303
 304           // only if we are traversing for a new task, not a stall site
 305           if( (fn instanceof FlatSESEEnterNode) &&
 306               smfe.getPossiblyEvilEffects().contains(e) ) {
 307
 308             FlatSESEEnterNode evilTask = (FlatSESEEnterNode)fn;
 309
 310             detectPossiblyEvilExecution(evilTask,
 311                                         evilTask.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp)
 312                                         );
 313           }
 314         }
 315       }
 316     }
 317   }
 318
 319   private void printRefSwitch(StateMachineForEffects smfe, FlatNode fn, TempDescriptor tmp, int pdepth, String childPtr, String currPtr, Set<SMFEState> transitions, int weakID) {
 320
 321     for(SMFEState tr : transitions) {
 322       if(tr.getRefCount() == 1) {       //in-lineable case
 323         //Don't need to update state counter since we don't care really if it's inlined...
 324         cFile.println("    "+currPtr+"= (struct ___Object___ * ) " + childPtr + ";");
 325         cFile.println("    if (" + currPtr + " != NULL) { ");
 326
 327         printAllocChecksInsideState(smfe, tr, fn, tmp, currPtr, pdepth+1, weakID);
 328
 329         cFile.println("    }"); //break for internal switch and if
 330       } else {                          //non-inlineable cases
 331         cFile.println("    "+currPtr+"= (struct ___Object___ * ) " + childPtr + ";");
 332         cFile.println("    if("+queryAndAddToVisitedHashtable+"("+currPtr+","+tr.getID()+"))");
 333         cFile.println("    " + enqueueInC +"("+ currPtr + ", "+tr.getID()+");");
 334       }
 335     }
 336   }
 337
 338
 339   //FlatNode and TempDescriptor are what are used to make the taint
 340   private void insertEntriesIntoHashStructureNew(FlatNode fn, TempDescriptor tmp, EffectsTable et, Alloc a, String prefix, int depth, int weakID) {
 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     String strrcr = isRblock?"&record->rcrRecords[" + index + "], ":"NULL, ";
 349     String tasksrc =isRblock?"(SESEcommon *) record, ":"(SESEcommon *)(((INTPTR)record)|1LL), ";
 350
 351     if(et.hasWriteConflict(a)) {
 352       cFile.append("    int tmpkey" + depth + " = rcr_generateKey(" + prefix + ");\n");
 353       if (et.conflictDereference(a))
 354         cFile.append("    int tmpvar" + depth + " = rcr_WTWRITEBINCASE(allHashStructures[" + weakID + "], tmpkey" + depth + ", " + tasksrc + strrcr + index + ");\n");
 355       else
 356         cFile.append("    int tmpvar" + depth + " = rcr_WRITEBINCASE(allHashStructures["+ weakID + "], tmpkey" + depth + ", " + tasksrc + strrcr + index + ");\n");
 357     } else if(et.hasReadConflict(a)) {
 358       cFile.append("    int tmpkey" + depth + " = rcr_generateKey(" + prefix + ");\n");
 359       if (et.conflictDereference(a))
 360         cFile.append("    int tmpvar" + depth + " = rcr_WTREADBINCASE(allHashStructures[" + weakID + "], tmpkey" + depth + ", " + tasksrc + strrcr + index + ");\n");
 361       else
 362         cFile.append("    int tmpvar" + depth + " = rcr_READBINCASE(allHashStructures["+ weakID + "], tmpkey" + depth + ", " + tasksrc + strrcr + index + ");\n");
 363     }
 364
 365     if (et.hasReadConflict(a) || et.hasWriteConflict(a)) {
 366       cFile.append("if (!(tmpvar" + depth + "&READYMASK)) totalcount--;\n");
 367     }
 368   }
 369
 370
 371   private void detectPossiblyEvilExecution(FlatSESEEnterNode possiblyEvilTask,
 372                                            int rcrRecordIndex
 373                                            ) {
 374     // We have a situation in which a task can start executing and
 375     // "evil-ly" destroy the paths to some objects it will access as
 376     // it goes along.  If this is the case, a traverser should not
 377     // continue and instead intentionally hold up any tasks that might
 378     // come later, because now we might never be able to find the
 379     // effects that should block later tasks.  This should be rare!
 380     cFile.append("// a possibly evil task has been detected!\n");
 381     cFile.append("//  |\\_/| \n");
 382     cFile.append("//  \\*,*/ \n");
 383     cFile.append("//   ^^^  \n");
 384     cFile.append("BARRIER();\n");
 385     cFile.append("if( unlikely( record->common.unresolvedDependencies == 0 &&");
 386     cFile.append("BARRIER() &&");
 387     cFile.append("record->common.doneExecuting == FALSE ) ) {\n");
 388     cFile.append("  // first abort this traversal, doesn't matter what the flag is because\n");
 389     cFile.append("  // the traverser is not going to clear the task, it's already running...\n");
 390     cFile.println("     record->rcrstatus=0;");
 391     cFile.append("  // just wait for the the task to retire...\n");
 392     cFile.append("  while( record->common.doneExecuting == FALSE ) {\n");
 393     cFile.append("    BARRIER();\n");
 394     cFile.append("  }\n");
 395     cFile.append("  \n");
 396     cFile.append("  // and now its safe to release the traverser to clear other tasks\n");
 397     cFile.append("  return;\n");
 398     cFile.append("}\n");
 399   }
 400
 401
 402   private void setupOutputFiles(String buildir) throws FileNotFoundException {
 403     cFile = new CodePrinter(new File(buildir + "RuntimeConflictResolver" + ".c"));
 404     headerFile = new CodePrinter(new File(buildir + "RuntimeConflictResolver" + ".h"));
 405
 406     cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
 407                   + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>");
 408     cFile.println("#include \"classdefs.h\"");
 409     cFile.println("#include \"structdefs.h\"");
 410     cFile.println("#include \"mlp_runtime.h\"");
 411     cFile.println("#include \"RuntimeConflictResolver.h\"");
 412     cFile.println("#include \"hashStructure.h\"");
 413
 414     headerFile.println("#ifndef __3_RCR_H_");
 415     headerFile.println("#define __3_RCR_H_");
 416   }
 417
 418   //The official way to generate the name for a traverser call
 419   public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
 420     String flatname;
 421     if(fn instanceof FlatSESEEnterNode) {  //is SESE block
 422       flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
 423     } else {  //is stallsite
 424       flatname = fn.toString();
 425     }
 426
 427     return "traverse___" + invar.getSafeSymbol() + removeInvalidChars(flatname) + "___("+varString+");";
 428   }
 429
 430   public String removeInvalidChars(String in) {
 431     StringBuilder s = new StringBuilder(in);
 432     for(int i = 0; i < s.length(); i++) {
 433       if(s.charAt(i) == ' ' ||
 434          s.charAt(i) == '.' ||
 435          s.charAt(i) == '=' ||
 436          s.charAt(i) == '[' ||
 437          s.charAt(i) == ']'    ) {
 438
 439         s.deleteCharAt(i);
 440         i--;
 441       }
 442     }
 443     return s.toString();
 444   }
 445
 446   public int getTraverserID(TempDescriptor invar, FlatNode fn) {
 447     Pair<TempDescriptor, FlatNode> t = new Pair<TempDescriptor, FlatNode>(invar, fn);
 448     if (idMap.containsKey(t)) {
 449       return idMap.get(t).intValue();
 450     }
 451     int value=currentID++;
 452     idMap.put(t, new Integer(value));
 453     return value;
 454   }
 455
 456   public void close() {
 457     //Prints out the master traverser Invocation that'll call all other traversers
 458     //based on traverserID
 459     printMasterTraverserInvocation();
 460     createMasterHashTableArray();
 461
 462     // Adds Extra supporting methods
 463     cFile.println("void initializeStructsRCR() {\n  " + mallocVisitedHashtable + ";\n  " + clearQueue + ";\n}");
 464     cFile.println("void destroyRCR() {\n  " + deallocVisitedHashTable + ";\n}");
 465
 466     headerFile.println("void initializeStructsRCR();\nvoid destroyRCR();");
 467     headerFile.println("#endif\n");
 468
 469     cFile.close();
 470     headerFile.close();
 471   }
 472
 473   private void printMasterTraverserInvocation() {
 474     headerFile.println("int tasktraverse(SESEcommon * record);");
 475     cFile.println("int tasktraverse(SESEcommon * record) {");
 476     cFile.println("  if(!CAS(&record->rcrstatus,1,2)) {");
 477
 478     //release traverser reference...no traversal necessary
 479     cFile.println("#ifndef OOO_DISABLE_TASKMEMPOOL");
 480     cFile.println("    RELEASE_REFERENCE_TO(record);");
 481     cFile.println("#endif");
 482
 483     cFile.println("    return;");
 484     cFile.println("  }");
 485     cFile.println("  switch(record->classID) {");
 486
 487     for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator(); seseit.hasNext(); ) {
 488       FlatSESEEnterNode fsen=seseit.next();
 489       cFile.println("    /* "+fsen.getPrettyIdentifier()+" */");
 490       cFile.println("    case "+fsen.getIdentifier()+": {");
 491       cFile.println("      "+fsen.getSESErecordName()+" * rec=("+fsen.getSESErecordName()+" *) record;");
 492       Vector<TempDescriptor> invars=fsen.getInVarsForDynamicCoarseConflictResolution();
 493       for(int i=0; i<invars.size(); i++) {
 494         TempDescriptor tmp=invars.get(i);
 495
 496         /* In some cases we don't want to a dynamic traversal if it is
 497          * unlikely to increase parallelism...these are cases where we
 498          * are just enabling a stall site to possible clear faster*/
 499
 500         boolean isValidToPrune=true;
 501         for( FlatSESEEnterNode parentSESE : fsen.getParents() ) {
 502           ConflictGraph graph      = oooa.getConflictGraph(parentSESE);
 503           if(graph!=null) {
 504             String id         = tmp + "_sese" + fsen.getPrettyIdentifier();
 505             ConflictNode node       = graph.getId2cn().get(id);
 506             isValidToPrune &= node.IsValidToPrune();
 507           }
 508         }
 509
 510         if(isValidToPrune) {
 511           // if node is valid to prune examiner,
 512           // also needs to turn off stall site examiners connected to this node
 513           for( FlatSESEEnterNode parentSESE : fsen.getParents() ) {
 514             ConflictGraph graph      = oooa.getConflictGraph(parentSESE);
 515             String id         = tmp + "_sese" + fsen.getPrettyIdentifier();
 516             ConflictNode node       = graph.getId2cn().get(id);
 517
 518             for (Iterator iterator = node.getEdgeSet().iterator(); iterator.hasNext(); ) {
 519               ConflictEdge edge = (ConflictEdge) iterator.next();
 520               if (edge.getVertexU() == node) {
 521                 if (edge.getVertexV().isStallSiteNode()) {
 522                   edge.getVertexV().setToBePruned(true);
 523                 }
 524               } else {
 525                 if (edge.getVertexU().isStallSiteNode()) {
 526                   edge.getVertexU().setToBePruned(true);
 527                 }
 528               }
 529             }
 530           }
 531         }
 532
 533         if (i!=0) {
 534           cFile.println("      if (record->rcrstatus!=0)");
 535         }
 536
 537         if(globalState.NOSTALLTR && isValidToPrune) {
 538           cFile.println("    /*  " + getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen)+"*/");
 539         } else {
 540           cFile.println("      " + getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen));
 541         }
 542       }
 543       //release traverser reference...traversal finished...
 544       //executing thread will clean bins for us
 545       cFile.println("     record->rcrstatus=0;");
 546       cFile.println("#ifndef OOO_DISABLE_TASKMEMPOOL");
 547       cFile.println("    RELEASE_REFERENCE_TO(record);");
 548       cFile.println("#endif");
 549       cFile.println("    }");
 550       cFile.println("    break;");
 551     }
 552
 553     for(FlatNode stallsite : processedStallSites.keySet()) {
 554
 555       TempDescriptor var = processedStallSites.get(stallsite);
 556       Set<FlatSESEEnterNode> seseSet=oooa.getPossibleExecutingRBlocks(stallsite);
 557       boolean isValidToPrune=true;
 558       for (Iterator iterator = seseSet.iterator(); iterator.hasNext(); ) {
 559         FlatSESEEnterNode sese = (FlatSESEEnterNode) iterator.next();
 560         ConflictGraph graph      = oooa.getConflictGraph(sese);
 561         if(graph!=null) {
 562           String id = var + "_fn" + stallsite.hashCode();
 563           ConflictNode node       = graph.getId2cn().get(id);
 564           isValidToPrune &= node.isTobePruned();
 565         }
 566       }
 567
 568       cFile.println("    case -" + getTraverserID(var, stallsite)+ ": {");
 569       cFile.println("      SESEstall * rec=(SESEstall*) record;");
 570       if(globalState.NOSTALLTR && isValidToPrune) {
 571         cFile.println("     /*" + getTraverserInvocation(var, "rec->___obj___, rec", stallsite)+";*/");
 572       } else {
 573         cFile.println("      " + getTraverserInvocation(var, "rec->___obj___, rec", stallsite)+";");
 574       }
 575       cFile.println("     record->rcrstatus=0;");
 576       cFile.println("    }");
 577       cFile.println("    break;");
 578     }
 579
 580     cFile.println("    default:");
 581     cFile.println("      printf(\"Invalid SESE ID was passed in: %d.\\n\",record->classID);");
 582     cFile.println("      break;");
 583     cFile.println("  }");
 584     cFile.println("}");
 585   }
 586
 587   private void createMasterHashTableArray() {
 588     headerFile.println("struct Hashtable_rcr ** createAndFillMasterHashStructureArray();");
 589     cFile.println("struct Hashtable_rcr ** createAndFillMasterHashStructureArray() {");
 590
 591     cFile.println("  struct Hashtable_rcr **table=rcr_createMasterHashTableArray("+totalWeakGroups + ");");
 592
 593     for(int i = 0; i < totalWeakGroups; i++) {
 594       cFile.println("  table["+i+"] = (struct Hashtable_rcr *) rcr_createHashtable();");
 595     }
 596     cFile.println("  return table;");
 597     cFile.println("}");
 598   }
 599
 600   public int getWeakID(TempDescriptor invar, FlatNode fn) {
 601     //return weakMap.get(new Pair(invar, fn)).intValue();
 602     return 0;
 603   }
 604
 605
 606   public boolean hasEmptyTraversers(FlatSESEEnterNode fsen) {
 607     boolean hasEmpty = true;
 608
 609     Set<FlatSESEEnterNode> children = fsen.getChildren();
 610     for (Iterator<FlatSESEEnterNode> iterator = children.iterator(); iterator.hasNext(); ) {
 611       FlatSESEEnterNode child = (FlatSESEEnterNode) iterator.next();
 612       hasEmpty &= child.getInVarsForDynamicCoarseConflictResolution().size() == 0;
 613     }
 614     return hasEmpty;
 615   }
 616
 617
 618   //Simply rehashes and combines all effects for a AffectedAllocSite + Field.
 619   private class EffectsTable {
 620     private Hashtable<Alloc,Set<Effect>> table;
 621     SMFEState state;
 622
 623     public EffectsTable(SMFEState state) {
 624       table = new Hashtable<Alloc, Set<Effect>>();
 625       this.state=state;
 626       for(Effect e : state.getEffectsAllowed()) {
 627         Set<Effect> eg;
 628         if((eg = table.get(e.getAffectedAllocSite())) == null) {
 629           eg = new HashSet<Effect>();
 630           table.put(e.getAffectedAllocSite(), eg);
 631         }
 632         eg.add(e);
 633       }
 634     }
 635
 636     public boolean conflictDereference(Alloc a) {
 637       for(Effect e : getEffects(a)) {
 638         if (!state.transitionsTo(e).isEmpty()&&state.getConflicts().contains(e))
 639           return true;
 640       }
 641       return false;
 642     }
 643
 644     public boolean hasWriteConflict(Alloc a) {
 645       for(Effect e : getEffects(a)) {
 646         if (e.isWrite() && state.getConflicts().contains(e))
 647           return true;
 648       }
 649       return false;
 650     }
 651
 652     public boolean hasReadConflict(Alloc a) {
 653       for(Effect e : getEffects(a)) {
 654         if (e.isRead() && state.getConflicts().contains(e))
 655           return true;
 656       }
 657       return false;
 658     }
 659
 660     public Set<Effect> getEffects(Alloc a) {
 661       return table.get(a);
 662     }
 663
 664     public Set<Alloc> getAllAllocs() {
 665       return table.keySet();
 666     }
 667   }
 668 }