3 import java.io.FileNotFoundException;
4 import java.io.PrintWriter;
5 import java.util.ArrayList;
6 import java.util.Collection;
7 import java.util.HashSet;
8 import java.util.Hashtable;
9 import java.util.Iterator;
11 import java.util.Vector;
12 import Analysis.Disjoint.*;
13 import IR.TypeDescriptor;
14 import Analysis.OoOJava.OoOJavaAnalysis;
16 /* An instance of this class manages all OoOJava coarse-grained runtime conflicts
17 * by generating C-code to either rule out the conflict at runtime or resolve one.
20 * 1) Instantiate singleton object (String input is to specify output dir)
21 * 2) Call setGlobalEffects setGlobalEffects(Hashtable<Taint, Set<Effect>> ) ONCE
22 * 3) Input SESE blocks, for each block:
23 * 3a) call addToTraverseToDoList(FlatSESEEnterNode , ReachGraph , Hashtable<Taint, Set<Effect>>) for the seseBlock
24 * 3b) call String getTraverserInvocation(TempDescriptor, String, FlatSESEEnterNode) to get the name of the traverse method in C
25 * 4) Call void close()
26 * Note: All computation is done upon closing the object. Steps 1-3 only input data
28 public class RuntimeConflictResolver {
29 public static final boolean javaDebug = true;
30 public static final boolean cSideDebug = false;
32 private PrintWriter cFile;
33 private PrintWriter headerFile;
34 private static final String hashAndQueueCFileDir = "oooJava/";
35 //This keeps track of taints we've traversed to prevent printing duplicate traverse functions
36 //The Integer keeps track of the weakly connected group it's in (used in enumerateHeapRoots)
37 private Hashtable<Taint, Integer> doneTaints;
38 private Hashtable<Taint, Set<Effect>> globalEffects;
39 private Hashtable<Taint, Set<Effect>> globalConflicts;
40 private ArrayList<TraversalInfo> toTraverse;
42 // initializing variables can be found in printHeader()
43 private static final String getAllocSiteInC = "->allocsite";
44 private static final String queryVistedHashtable = "hashRCRInsert";
45 private static final String addToQueueInC = "enqueueRCRQueue(";
46 private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
47 private static final String clearQueue = "resetRCRQueue()";
48 // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
49 private static final String mallocVisitedHashtable = "hashRCRCreate(128, 0.75)";
50 private static final String deallocVisitedHashTable = "hashRCRDelete()";
51 private static final String resetVisitedHashTable = "hashRCRreset()";
53 //TODO find correct strings for these
54 private static final String addCheckFromHashStructure = "checkFromHashStructure(";
55 private static final String putWaitingQueueBlock = "putWaitingQueueBlock("; //lifting of blocks will be done by hashtable.
56 private static final String putIntoAllocQueue = "putIntoWaitingQ(";
57 private static final int noConflict = 0;
58 private static final int conflictButTraverserCanContinue = 1;
59 private static final int conflictButTraverserCannotContinue = 2;
60 private static final int allocQueueIsNotEmpty = 0;
62 // Hashtable provides fast access to heaproot # lookups
63 private Hashtable<Taint, WeaklyConectedHRGroup> connectedHRHash;
64 private ArrayList<WeaklyConectedHRGroup> num2WeaklyConnectedHRGroup;
65 private int traverserIDCounter;
66 private int weaklyConnectedHRCounter;
67 private ArrayList<TaintAndInternalHeapStructure> pendingPrintout;
68 private EffectsTable effectsLookupTable;
69 private OoOJavaAnalysis oooa;
71 public RuntimeConflictResolver(String buildir, OoOJavaAnalysis oooa) throws FileNotFoundException {
72 String outputFile = buildir + "RuntimeConflictResolver";
75 cFile = new PrintWriter(new File(outputFile + ".c"));
76 headerFile = new PrintWriter(new File(outputFile + ".h"));
78 cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
79 + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>");
80 cFile.println("#include \"classdefs.h\"");
81 cFile.println("#include \"structdefs.h\"");
82 cFile.println("#include \"mlp_runtime.h\"");
83 cFile.println("#include \"RuntimeConflictResolver.h\"");
84 cFile.println("#include \"hashStructure.h\"");
86 headerFile.println("#ifndef __3_RCR_H_");
87 headerFile.println("#define __3_RCR_H_");
89 doneTaints = new Hashtable<Taint, Integer>();
90 connectedHRHash = new Hashtable<Taint, WeaklyConectedHRGroup>();
92 traverserIDCounter = 1;
93 weaklyConnectedHRCounter = 0;
94 pendingPrintout = new ArrayList<TaintAndInternalHeapStructure>();
95 toTraverse = new ArrayList<TraversalInfo>();
96 globalConflicts = new Hashtable<Taint, Set<Effect>>();
97 //Note: globalEffects is not instantiated since it'll be passed in whole while conflicts comes in chunks
100 public void setGlobalEffects(Hashtable<Taint, Set<Effect>> effects) {
101 globalEffects = effects;
104 System.out.println("============EFFECTS LIST AS PASSED IN============");
105 for(Taint t: globalEffects.keySet()) {
106 System.out.println("For Taint " + t);
107 for(Effect e: globalEffects.get(t)) {
108 System.out.println("\t" + e);
111 System.out.println("====================END LIST====================");
117 * 1) Get global effects and conflicts
118 * 2) Create a hash structure (EffectsTable) to manage effects (hashed by affected Allocsite, then taint, then field)
119 * 2a) Use Effects to verify we can access something (reads)
120 * 2b) Use conflicts to mark conflicts (read/write/strongupdate)
121 * 2c) At second level of hash, store Heaproots that can cause conflicts at the field
122 * 3) Walk hash structure to identify and enumerate weakly connected groups and generate waiting queue slots.
123 * 4) Build internal representation of the rgs (pruned)
124 * 5) Print c methods by walking internal representation
127 public void addToTraverseToDoList(FlatSESEEnterNode rblock, ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
129 toTraverse.add(new TraversalInfo(rblock, rg));
131 //Add to Global conflicts
132 for(Taint t: conflicts.keySet()) {
133 if(globalConflicts.containsKey(t)) {
134 globalConflicts.get(t).addAll(conflicts.get(t));
136 globalConflicts.put(t, conflicts.get(t));
142 public void addToTraverseToDoList(FlatNode fn, TempDescriptor tempDesc,
143 ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
144 toTraverse.add(new TraversalInfo(fn, rg, tempDesc));
146 for(Taint t: conflicts.keySet()) {
147 if(globalConflicts.containsKey(t)) {
148 globalConflicts.get(t).addAll(conflicts.get(t));
150 globalConflicts.put(t, conflicts.get(t));
155 private void traverseSESEBlock(FlatSESEEnterNode rblock, ReachGraph rg) {
156 Collection<TempDescriptor> inVars = rblock.getInVarSet();
158 if (inVars.size() == 0)
161 // For every non-primitive variable, generate unique method
162 // Special Note: The Criteria for executing printCMethod in this loop should match
163 // exactly the criteria in buildcode.java to invoke the generated C method(s).
164 for (TempDescriptor invar : inVars) {
165 TypeDescriptor type = invar.getType();
166 if(type == null || type.isPrimitive()) {
170 //created stores nodes with specific alloc sites that have been traversed while building
171 //internal data structure. It is later traversed sequentially to find inset variables and
173 Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
174 VariableNode varNode = rg.getVariableNodeNoMutation(invar);
175 Taint taint = getProperTaintForFlatSESEEnterNode(rblock, varNode, globalEffects);
177 printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + rblock.toPrettyString());
181 //This is to prevent duplicate traversals from being generated
182 if(doneTaints.containsKey(taint))
185 doneTaints.put(taint, traverserIDCounter++);
186 createConcreteGraph(effectsLookupTable, created, varNode, taint);
189 //This will add the taint to the printout, there will be NO duplicates (checked above)
190 if(!created.isEmpty()) {
191 rblock.addInVarForDynamicCoarseConflictResolution(invar);
192 pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
197 private void traverseStallSite(FlatNode enterNode, TempDescriptor invar, ReachGraph rg) {
198 TypeDescriptor type = invar.getType();
199 if(type == null || type.isPrimitive()) {
202 Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
203 VariableNode varNode = rg.getVariableNodeNoMutation(invar);
204 Taint taint = getProperTaintForEnterNode(enterNode, varNode, globalEffects);
207 printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + enterNode.toString());
211 if(doneTaints.containsKey(taint))
214 doneTaints.put(taint, traverserIDCounter++);
215 createConcreteGraph(effectsLookupTable, created, varNode, taint);
217 if (!created.isEmpty()) {
218 pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
222 public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
224 if(fn instanceof FlatSESEEnterNode) {
225 flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
227 flatname = fn.toString();
230 return "traverse___" + removeInvalidChars(invar.getSafeSymbol()) +
231 removeInvalidChars(flatname) + "___("+varString+");";
234 public String removeInvalidChars(String in) {
235 StringBuilder s = new StringBuilder(in);
236 for(int i = 0; i < s.length(); i++) {
237 if(s.charAt(i) == ' ' || s.charAt(i) == '.' || s.charAt(i) == '=') {
245 public void close() {
246 buildEffectsLookupStructure();
247 runAllTraverserals();
249 //prints out all generated code
250 for(TaintAndInternalHeapStructure ths: pendingPrintout) {
251 printCMethod(ths.nodesInHeap, ths.t);
254 //Prints out the master traverser Invocation that'll call all other traverser
255 //based on traverserID
256 printMasterTraverserInvocation();
257 printResumeTraverserInvocation();
259 //TODO this is only temporary, remove when thread local vars implemented.
260 createMasterHashTableArray();
262 // Adds Extra supporting methods
263 cFile.println("void initializeStructsRCR() {\n " + mallocVisitedHashtable + ";\n " + clearQueue + ";\n}");
264 cFile.println("void destroyRCR() {\n " + deallocVisitedHashTable + ";\n}");
266 headerFile.println("void initializeStructsRCR();\nvoid destroyRCR();");
267 headerFile.println("#endif\n");
273 //Builds Effects Table and runs the analysis on them to get weakly connected HRs
274 //SPECIAL NOTE: Only runs after we've taken all the conflicts
275 private void buildEffectsLookupStructure(){
276 effectsLookupTable = new EffectsTable(globalEffects, globalConflicts);
277 effectsLookupTable.runAnaylsis();
278 enumerateHeaproots();
281 private void runAllTraverserals() {
282 for(TraversalInfo t: toTraverse) {
283 printDebug(javaDebug, "Running Traversal a traversal on " + t.f);
285 if(t.f instanceof FlatSESEEnterNode) {
286 traverseSESEBlock((FlatSESEEnterNode)t.f, t.rg);
288 if(t.invar == null) {
289 System.out.println("RCR ERROR: Attempted to run a stall site traversal with NO INVAR");
291 traverseStallSite(t.f, t.invar, t.rg);
298 //TODO: This is only temporary, remove when thread local variables are functional.
299 private void createMasterHashTableArray() {
300 headerFile.println("void createAndFillMasterHashStructureArray();");
301 cFile.println("void createAndFillMasterHashStructureArray() {\n" +
302 " rcr_createMasterHashTableArray("+weaklyConnectedHRCounter + ");");
304 for(int i = 0; i < weaklyConnectedHRCounter; i++) {
305 cFile.println(" allHashStructures["+i+"] = (HashStructure *) rcr_createHashtable("+num2WeaklyConnectedHRGroup.get(i).connectedHRs.size()+");");
310 private void printMasterTraverserInvocation() {
311 headerFile.println("\nint tasktraverse(SESEcommon * record);");
312 cFile.println("\nint tasktraverse(SESEcommon * record) {");
313 cFile.println(" switch(record->classID) {");
315 for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
316 FlatSESEEnterNode fsen=seseit.next();
317 cFile.println( " /* "+fsen.getPrettyIdentifier()+" */");
318 cFile.println( " case "+fsen.getIdentifier()+": {");
319 cFile.println( " "+fsen.getSESErecordName()+" * rec=("+fsen.getSESErecordName()+" *) record;");
320 Vector<TempDescriptor> invars=fsen.getInVarsForDynamicCoarseConflictResolution();
321 for(int i=0;i<invars.size();i++) {
322 TempDescriptor tmp=invars.get(i);
323 cFile.println(" " + this.getTraverserInvocation(tmp, "rec->"+tmp, fsen));
325 cFile.println( " }");
326 cFile.println( " break;");
329 cFile.println(" default:\n printf(\"Invalid SESE ID was passed in.\\n\");\n break;");
336 //This will print the traverser invocation that takes in a traverserID and
338 private void printResumeTraverserInvocation() {
339 headerFile.println("\nint traverse(void * startingPtr, int traverserID);");
340 cFile.println("\nint traverse(void * startingPtr, int traverserID) {");
341 cFile.println(" switch(traverserID) {");
343 for(Taint t: doneTaints.keySet()) {
344 cFile.println(" case " + doneTaints.get(t)+ ":");
345 if(t.isRBlockTaint()) {
346 cFile.println(" " + this.getTraverserInvocation(t.getVar(), "startingPtr", t.getSESE()));
347 } else if (t.isStallSiteTaint()){
348 cFile.println(" " + this.getTraverserInvocation(t.getVar(), "startingPtr", t.getStallSite()));
350 System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t);
354 if(RuntimeConflictResolver.cSideDebug) {
355 cFile.println(" default:\n printf(\"Invalid traverser ID %u was passed in.\\n\", traverserID);\n break;");
357 cFile.println(" default:\n break;");
364 private void createConcreteGraph(
366 Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
367 VariableNode varNode,
370 // if table is null that means there's no conflicts, therefore we need not
371 // create a traversal
375 Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
376 while (possibleEdges.hasNext()) {
377 RefEdge edge = possibleEdges.next();
380 ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true);
381 AllocSite rootKey = singleRoot.allocSite;
383 if (!created.containsKey(rootKey)) {
384 created.put(rootKey, singleRoot);
385 createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table, t);
390 //This code is the old way of generating an effects lookup table.
391 //The new way is to instantiate an EffectsGroup
393 private Hashtable<AllocSite, EffectsGroup> generateEffectsLookupTable(
394 Taint taint, Hashtable<Taint,
395 Set<Effect>> effects,
396 Hashtable<Taint, Set<Effect>> conflicts) {
400 Set<Effect> localEffects = effects.get(taint);
401 Set<Effect> localConflicts = conflicts.get(taint);
403 //Debug Code for manually checking effects
405 printEffectsAndConflictsSets(taint, localEffects, localConflicts);
408 if (localEffects == null || localEffects.isEmpty() || localConflicts == null || localConflicts.isEmpty())
411 Hashtable<AllocSite, EffectsGroup> lookupTable = new Hashtable<AllocSite, EffectsGroup>();
413 for (Effect e : localEffects) {
414 boolean conflict = localConflicts.contains(e);
415 AllocSite key = e.getAffectedAllocSite();
416 EffectsGroup myEffects = lookupTable.get(key);
418 if(myEffects == null) {
419 myEffects = new EffectsGroup();
420 lookupTable.put(key, myEffects);
423 if(e.getField().getType().isPrimitive()) {
425 myEffects.addPrimitive(e, true);
429 myEffects.addObjEffect(e, conflict);
436 // Plan is to add stuff to the tree depth-first sort of way. That way, we can
437 // propagate up conflicts
438 private void createHelper(ConcreteRuntimeObjNode curr,
439 Iterator<RefEdge> edges,
440 Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
443 assert table != null;
444 AllocSite parentKey = curr.allocSite;
445 EffectsGroup currEffects = table.getEffects(parentKey, taint);
447 if (currEffects == null || currEffects.isEmpty())
450 //Handle Objects (and primitives if child is new)
451 if(currEffects.hasObjectEffects()) {
452 while(edges.hasNext()) {
453 RefEdge edge = edges.next();
454 String field = edge.getField();
455 CombinedObjEffects effectsForGivenField = currEffects.getObjEffect(field);
456 //If there are no effects, then there's no point in traversing this edge
457 if(effectsForGivenField != null) {
458 HeapRegionNode childHRN = edge.getDst();
459 AllocSite childKey = childHRN.getAllocSite();
460 boolean isNewChild = !created.containsKey(childKey);
461 ConcreteRuntimeObjNode child;
464 child = new ConcreteRuntimeObjNode(childHRN, false);
465 created.put(childKey, child);
467 child = created.get(childKey);
470 curr.addObjChild(field, child, effectsForGivenField);
472 if (effectsForGivenField.hasConflict()) {
473 child.hasPotentialToBeIncorrectDueToConflict = true;
474 propogateObjConflict(curr, child);
477 if(effectsForGivenField.hasReadEffect) {
478 child.addReachableParent(curr);
480 //If isNewChild, flag propagation will be handled at recursive call
482 createHelper(child, childHRN.iteratorToReferencees(), created, table, taint);
484 //This makes sure that all conflicts below the child is propagated up the referencers.
485 if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) {
486 propogatePrimConflict(child, child.enqueueToWaitingQueueUponConflict);
489 if(child.decendantsObjConflict) {
490 propogateObjConflict(child, child.enqueueToWaitingQueueUponConflict);
499 curr.primitiveConflictingFields = currEffects.primitiveConflictingFields;
500 if(currEffects.hasPrimitiveConflicts()) {
501 //Reminder: primitive conflicts are abstracted to object.
502 propogatePrimConflict(curr, curr);
506 // This will propagate the conflict up the data structure.
507 private void propogateObjConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
508 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
509 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
510 (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) // case where referencer has never seen possible unresolved referencee below
512 referencer.decendantsObjConflict = true;
513 propogateObjConflict(referencer, pointsOfAccess);
518 private void propogateObjConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
519 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
520 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
521 (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) // case where referencer has never seen possible unresolved referencee below
523 referencer.decendantsObjConflict = true;
524 propogateObjConflict(referencer, pointOfAccess);
529 private void propogatePrimConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
530 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
531 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
532 (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess)))
534 referencer.decendantsPrimConflict = true;
535 propogatePrimConflict(referencer, pointsOfAccess);
540 private void propogatePrimConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
541 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
542 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
543 (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess)))
545 referencer.decendantsPrimConflict = true;
546 propogatePrimConflict(referencer, pointOfAccess);
554 * This method generates a C method for every inset variable and rblock.
556 * The C method works by generating a large switch statement that will run the appropriate
557 * checking code for each object based on its allocation site. The switch statement is
558 * surrounded by a while statement which dequeues objects to be checked from a queue. An
559 * object is added to a queue only if it contains a conflict (in itself or in its referencees)
560 * and we came across it while checking through it's referencer. Because of this property,
561 * conflicts will be signaled by the referencer; the only exception is the inset variable which can
562 * signal a conflict within itself.
565 private void printCMethod(Hashtable<AllocSite, ConcreteRuntimeObjNode> created, Taint taint) {
566 //This hash table keeps track of all the case statements generated. Although it may seem a bit much
567 //for its purpose, I think it may come in handy later down the road to do it this way.
568 //(i.e. what if we want to eliminate some cases? Or build filter for 1 case)
569 String inVar = taint.getVar().getSafeSymbol();
572 if(taint.isStallSiteTaint()) {
573 rBlock = taint.getStallSite().toString();
574 } else if(taint.isRBlockTaint()) {
575 rBlock = taint.getSESE().getPrettyIdentifier();
577 System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString());
581 Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
584 for (ConcreteRuntimeObjNode node : created.values()) {
585 if (!cases.containsKey(node.allocSite) && (
587 (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
588 //non-inline-able code cases
589 (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
590 //Cases where resumes are possible
591 (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict)) {
593 printDebug(javaDebug, node.allocSite + " qualified for case statement");
594 addChecker(taint, node, cases, null, "ptr", 0);
597 //IMPORTANT: remember to change getTraverserInvocation if you change the line below
598 String methodName = "void traverse___" + removeInvalidChars(inVar) +
599 removeInvalidChars(rBlock) + "___(void * InVar)";
601 cFile.println(methodName + " {");
602 headerFile.println(methodName + ";");
605 cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
608 if(cases.size() == 0) {
609 cFile.println(" return; }");
612 //clears queue and hashtable that keeps track of where we've been.
613 cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
615 //Casts the ptr to a genericObjectStruct so we can get to the ptr->allocsite field.
616 cFile.println("struct genericObjectStruct * ptr = (struct genericObjectStruct *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable
619 cFile.println(" switch(ptr->allocsite) {");
621 for(AllocSite singleCase: cases.keySet())
622 cFile.append(cases.get(singleCase));
624 cFile.println(" default:\n break; ");
625 cFile.println(" }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}\n}\n");
631 * addChecker creates a case statement for every object that is either an inset variable
632 * or has multiple referencers (incoming edges). Else it just prints the checker for that object
633 * so that its processing can be pushed up to the referencer node.
635 private void addChecker(Taint taint,
636 ConcreteRuntimeObjNode node,
637 Hashtable<AllocSite,StringBuilder> cases,
638 StringBuilder possibleContinuingCase,
641 StringBuilder currCase = possibleContinuingCase;
642 // We don't need a case statement for things with either 1 incoming or 0 out
643 // going edges, because they can be processed when checking the parent.
644 if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
645 (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
646 node.hasPotentialToBeIncorrectDueToConflict && node.decendantsObjConflict) {
647 assert prefix.equals("ptr") && !cases.containsKey(node.allocSite);
648 currCase = new StringBuilder();
649 cases.put(node.allocSite, currCase);
650 currCase.append(" case " + node.getAllocationSite() + ": {\n");
652 //either currCase is continuing off a parent case or is its own.
653 assert currCase !=null;
654 boolean primConfRead=false;
655 boolean primConfWrite=false;
656 boolean objConfRead=false;
657 boolean objConfWrite=false;
660 for(String field: node.primitiveConflictingFields.keySet()) {
661 CombinedObjEffects effect=node.primitiveConflictingFields.get(field);
662 primConfRead|=effect.hasReadConflict;
663 primConfWrite|=effect.hasWriteConflict;
666 //Object Reference Test
667 for(ObjRef ref: node.objectRefs) {
668 CombinedObjEffects effect=ref.myEffects;
669 objConfRead|=effect.hasReadConflict;
670 objConfWrite|=effect.hasWriteConflict;
674 currCase.append(" if(");
675 checkWaitingQueue(currCase, taint, node);
676 currCase.append("||");
679 //Do call if we need it.
680 if(primConfWrite||objConfWrite) {
681 int heaprootNum = connectedHRHash.get(taint).id;
682 assert heaprootNum != -1;
683 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
684 int traverserID = doneTaints.get(taint);
685 currCase.append(" rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"],"+prefix+","+traverserID+",NULL,NULL)");
686 } else if (primConfRead||objConfRead) {
687 int heaprootNum = connectedHRHash.get(taint).id;
688 assert heaprootNum != -1;
689 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
690 int traverserID = doneTaints.get(taint);
691 currCase.append(" rcr_READBINCASE(allHashStructures["+heaprootNum+"],"+prefix+","+traverserID+",NULL,NULL)");
695 currCase.append(") {\n");
696 putIntoWaitingQueue(currCase, taint, node, prefix);
697 currCase.append(" break;\n");
698 currCase.append(" }\n");
699 } else if(primConfRead||primConfWrite||objConfWrite) {
700 currCase.append(";\n");
704 for(ObjRef ref: node.objectRefs) {
705 // Will only process edge if there is some sort of conflict with the Child
706 if (ref.hasConflictsDownThisPath()) {
707 String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + ref.field + "___";
709 String currPtr = "myPtr" + pdepth;
710 String structType = ref.child.original.getType().getSafeSymbol();
711 currCase.append(" struct " + structType + " * "+currPtr+"= (struct "+ structType + " * ) " + childPtr + ";\n");
714 // Checks if the child exists and has allocsite matching the conflict
715 currCase.append(" if (" + currPtr + " != NULL && " + currPtr + getAllocSiteInC + "==" + ref.allocSite + ") {\n");
717 if (ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
718 // Checks if we have visited the child before
720 currCase.append(" if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
721 if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
722 addChecker(taint, ref.child, cases, currCase, currPtr, depth + 1);
725 currCase.append(" " + addToQueueInC + childPtr + ");\n ");
728 currCase.append(" }\n");
730 //one more brace for the opening if
731 if(ref.hasDirectObjConflict()) {
732 currCase.append(" }\n");
735 currCase.append(" }\n ");
739 if((node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
740 (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
741 (node.hasPotentialToBeIncorrectDueToConflict && node.decendantsObjConflict)) {
742 currCase.append(" }\n break;\n");
746 //This method will touch the waiting queues if necessary.
747 //IMPORTANT NOTE: This needs a closing } from the caller and the if is cannot continue
748 private void addCheckHashtableAndWaitingQ(StringBuilder currCase, Taint t, ConcreteRuntimeObjNode node, String ptr, int depth) {
749 Iterator<ConcreteRuntimeObjNode> it = node.enqueueToWaitingQueueUponConflict.iterator();
751 currCase.append(" int retval"+depth+" = "+ addCheckFromHashStructure + ptr + ");\n");
752 currCase.append(" if (retval"+depth+" == " + conflictButTraverserCannotContinue + " || ");
753 checkWaitingQueue(currCase, t, node);
754 currCase.append(") {\n");
755 //If cannot continue, then add all the undetermined references that lead from this child, including self.
756 //TODO need waitingQueue Side to automatically check the thing infront of it to prevent double adds.
757 putIntoWaitingQueue(currCase, t, node, ptr);
759 ConcreteRuntimeObjNode related;
760 while(it.hasNext()) {
762 //TODO maybe ptr won't even be needed since upon resume, the hashtable will remove obj.
763 putIntoWaitingQueue(currCase, t, related, ptr);
768 private void handleObjConflict(StringBuilder currCase, String childPtr, AllocSite allocSite, ObjRef ref) {
769 currCase.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.getUniqueAllocSiteID() + ");");
772 private void handlePrimitiveConflict(StringBuilder currCase, String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
773 currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); ");
777 private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
778 Hashtable<Taint, Set<Effect>> effects) {
779 Set<Taint> taints = effects.keySet();
780 for (Taint t : taints) {
781 FlatSESEEnterNode sese = t.getSESE();
782 if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
790 private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
791 Hashtable<Taint, Set<Effect>> effects) {
792 Set<Taint> taints = effects.keySet();
793 for (Taint t : taints) {
794 FlatNode flatnode = t.getStallSite();
795 if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
802 private void printEffectsAndConflictsSets(Taint taint, Set<Effect> localEffects,
803 Set<Effect> localConflicts) {
804 System.out.println("#### List of Effects/Conflicts ####");
805 System.out.println("For Taint " + taint);
806 System.out.println("Effects");
807 if(localEffects != null) {
808 for(Effect e: localEffects) {
809 System.out.println(e);
812 System.out.println("Conflicts");
813 if(localConflicts != null) {
814 for(Effect e: localConflicts) {
815 System.out.println(e);
820 private void printDebug(boolean guard, String debugStatements) {
822 System.out.println(debugStatements);
825 //TODO finish this once waitingQueue side is figured out
826 private void putIntoWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node, String resumePtr ) {
827 //Method looks like this: void put(int allocSiteID, x
828 //struct WaitingQueue * queue, //get this from hashtable
829 //int effectType, //not so sure we would actually need this one.
831 //int traverserID); }
832 int heaprootNum = connectedHRHash.get(taint).id;
833 assert heaprootNum != -1;
834 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
835 int traverserID = doneTaints.get(taint);
837 //NOTE if the C-side is changed, this will have to be changed accordingly
838 //TODO make sure this matches c-side
839 sb.append(" putIntoWaitingQueue("+allocSiteID+", " +
840 "allHashStructures["+ heaprootNum +"]->waitingQueue, " +
845 //TODO finish waitingQueue side
847 * Inserts check to see if waitingQueue is occupied.
849 * On C-side, =0 means empty queue, else occupied.
851 private void checkWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node) {
852 //Method looks like int check(struct WaitingQueue * queue, int allocSiteID)
853 assert sb != null && taint !=null;
854 int heaprootNum = connectedHRHash.get(taint).id;
855 assert heaprootNum != -1;
856 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
858 sb.append(" (isEmptyForWaitingQ(allHashStructures["+ heaprootNum +"]->waitingQueue, " + allocSiteID + ") == "+ allocQueueIsNotEmpty+")");
861 private void enumerateHeaproots() {
862 //reset numbers jsut in case
863 weaklyConnectedHRCounter = 0;
864 num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
866 for(Taint t: connectedHRHash.keySet()) {
867 if(connectedHRHash.get(t).id == -1) {
868 WeaklyConectedHRGroup hg = connectedHRHash.get(t);
869 hg.id = weaklyConnectedHRCounter;
870 num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
871 weaklyConnectedHRCounter++;
876 private void printoutTable(EffectsTable table) {
878 System.out.println("==============EFFECTS TABLE PRINTOUT==============");
879 for(AllocSite as: table.table.keySet()) {
880 System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
882 BucketOfEffects boe = table.table.get(as);
884 if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
885 System.out.println("\t\tPotentially conflicting roots: ");
886 for(String key: boe.potentiallyConflictingRoots.keySet()) {
887 System.out.println("\t\t-Field: " + key);
888 System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
891 for(Taint t: boe.taint2EffectsGroup.keySet()) {
892 System.out.println("\t\t For Taint " + t);
893 EffectsGroup eg = boe.taint2EffectsGroup.get(t);
895 if(eg.hasPrimitiveConflicts()) {
896 System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
897 for(String field: eg.primitiveConflictingFields.keySet()) {
898 System.out.print(field + " ");
900 System.out.println();
902 for(String fieldKey: eg.myEffects.keySet()) {
903 CombinedObjEffects ce = eg.myEffects.get(fieldKey);
904 System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
905 System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
906 " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
907 " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
908 for(Effect ef: ce.originalEffects) {
909 System.out.println("\t" + ef);
918 private class EffectsGroup {
919 Hashtable<String, CombinedObjEffects> myEffects;
920 Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
922 public EffectsGroup() {
923 myEffects = new Hashtable<String, CombinedObjEffects>();
924 primitiveConflictingFields = new Hashtable<String, CombinedObjEffects>();
927 public void addPrimitive(Effect e, boolean conflict) {
928 CombinedObjEffects effects;
929 if((effects = primitiveConflictingFields.get(e.getField().getSymbol())) == null) {
930 effects = new CombinedObjEffects();
931 primitiveConflictingFields.put(e.getField().getSymbol(), effects);
933 effects.add(e, conflict);
936 public void addObjEffect(Effect e, boolean conflict) {
937 CombinedObjEffects effects;
938 if((effects = myEffects.get(e.getField().getSymbol())) == null) {
939 effects = new CombinedObjEffects();
940 myEffects.put(e.getField().getSymbol(), effects);
942 effects.add(e, conflict);
945 public boolean isEmpty() {
946 return myEffects.isEmpty() && primitiveConflictingFields.isEmpty();
949 public boolean hasPrimitiveConflicts(){
950 return !primitiveConflictingFields.isEmpty();
953 public CombinedObjEffects getPrimEffect(String field) {
954 return primitiveConflictingFields.get(field);
957 public boolean hasObjectEffects() {
958 return !myEffects.isEmpty();
961 public CombinedObjEffects getObjEffect(String field) {
962 return myEffects.get(field);
966 //Is the combined effects for all effects with the same affectedAllocSite and field
967 private class CombinedObjEffects {
968 ArrayList<Effect> originalEffects;
970 public boolean hasReadEffect;
971 public boolean hasWriteEffect;
972 public boolean hasStrongUpdateEffect;
974 public boolean hasReadConflict;
975 public boolean hasWriteConflict;
976 public boolean hasStrongUpdateConflict;
979 public CombinedObjEffects() {
980 originalEffects = new ArrayList<Effect>();
982 hasReadEffect = false;
983 hasWriteEffect = false;
984 hasStrongUpdateEffect = false;
986 hasReadConflict = false;
987 hasWriteConflict = false;
988 hasStrongUpdateConflict = false;
991 public boolean add(Effect e, boolean conflict) {
992 if(!originalEffects.add(e))
995 switch(e.getType()) {
997 hasReadEffect = true;
998 hasReadConflict = conflict;
1001 hasWriteEffect = true;
1002 hasWriteConflict = conflict;
1004 case Effect.strongupdate:
1005 hasStrongUpdateEffect = true;
1006 hasStrongUpdateConflict = conflict;
1009 System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
1016 public boolean hasConflict() {
1017 return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
1021 //This will keep track of a reference
1022 private class ObjRef {
1025 CombinedObjEffects myEffects;
1027 //This keeps track of the parent that we need to pass by inorder to get
1028 //to the conflicting child (if there is one).
1029 ConcreteRuntimeObjNode child;
1031 public ObjRef(String fieldname,
1032 ConcreteRuntimeObjNode ref,
1033 CombinedObjEffects myEffects) {
1035 allocSite = ref.getAllocationSite();
1038 this.myEffects = myEffects;
1041 public boolean hasConflictsDownThisPath() {
1042 return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
1045 public boolean hasDirectObjConflict() {
1046 return myEffects.hasConflict();
1050 private class ConcreteRuntimeObjNode {
1051 ArrayList<ObjRef> objectRefs;
1052 Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1053 HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
1054 HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
1055 //this set keeps track of references down the line that need to be enqueued if traverser is "paused"
1056 HashSet<ConcreteRuntimeObjNode> enqueueToWaitingQueueUponConflict;
1057 boolean decendantsPrimConflict;
1058 boolean decendantsObjConflict;
1059 boolean hasPotentialToBeIncorrectDueToConflict;
1061 AllocSite allocSite;
1062 HeapRegionNode original;
1064 public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar) {
1065 objectRefs = new ArrayList<ObjRef>();
1066 primitiveConflictingFields = null;
1067 parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
1068 parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
1069 enqueueToWaitingQueueUponConflict = new HashSet<ConcreteRuntimeObjNode>();
1070 allocSite = me.getAllocSite();
1072 isInsetVar = isInVar;
1073 decendantsPrimConflict = false;
1074 decendantsObjConflict = false;
1075 hasPotentialToBeIncorrectDueToConflict = false;
1078 public void addReachableParent(ConcreteRuntimeObjNode curr) {
1079 parentsWithReadToNode.add(curr);
1083 public boolean equals(Object obj) {
1084 return original.equals(obj);
1087 public int getAllocationSite() {
1088 return allocSite.getUniqueAllocSiteID();
1091 public int getNumOfReachableParents() {
1092 return parentsThatWillLeadToConflicts.size();
1095 public boolean hasPrimitiveConflicts() {
1096 return !primitiveConflictingFields.isEmpty();
1099 public boolean decendantsConflict() {
1100 return decendantsPrimConflict || decendantsObjConflict;
1104 //returns true if at least one of the objects in points of access has been added
1105 public boolean addPossibleWaitingQueueEnqueue(HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
1106 boolean addedNew = false;
1107 for(ConcreteRuntimeObjNode dec: pointsOfAccess) {
1108 if(dec != null && dec != this){
1109 addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec);
1116 public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) {
1117 if(pointOfAccess != null && pointOfAccess != this){
1118 return enqueueToWaitingQueueUponConflict.add(pointOfAccess);
1124 public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
1125 ObjRef ref = new ObjRef(field, child, ce);
1126 objectRefs.add(ref);
1129 public String toString() {
1130 return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
1131 " decCon="+decendantsObjConflict+
1132 " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
1136 private class EffectsTable {
1137 private Hashtable<AllocSite, BucketOfEffects> table;
1139 public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1140 Hashtable<Taint, Set<Effect>> conflicts) {
1141 table = new Hashtable<AllocSite, BucketOfEffects>();
1143 // rehash all effects (as a 5-tuple) by their affected allocation site
1144 for (Taint t : effects.keySet()) {
1145 Set<Effect> localConflicts = conflicts.get(t);
1146 for (Effect e : effects.get(t)) {
1147 BucketOfEffects bucket;
1148 if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1149 bucket = new BucketOfEffects();
1150 table.put(e.getAffectedAllocSite(), bucket);
1152 printDebug(javaDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts);
1153 bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1158 public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1159 //This would get the proper bucket of effects and then get all the effects
1160 //for a parent for a specific taint
1161 return table.get(parentKey).taint2EffectsGroup.get(taint);
1164 // Run Analysis will walk the data structure and figure out the weakly
1165 // connected heap roots.
1166 public void runAnaylsis() {
1168 printoutTable(this);
1171 //TODO is there a higher performance way to do this?
1172 for(AllocSite key: table.keySet()) {
1173 BucketOfEffects effects = table.get(key);
1174 //make sure there are actually conflicts in the bucket
1175 if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1176 for(String field: effects.potentiallyConflictingRoots.keySet()){
1177 ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1178 //For simplicity, we just create a new group and add everything to it instead of
1179 //searching through all of them for the largest group and adding everyone in.
1180 WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1181 group.add(taints); //This will automatically add the taint to the connectedHRhash
1188 private class WeaklyConectedHRGroup {
1189 HashSet<Taint> connectedHRs;
1190 //This is to keep track of unique waitingQueue positions for each allocsite.
1191 Hashtable<AllocSite, Integer> allocSiteToWaitingQueueMap;
1192 int waitingQueueCounter;
1195 public WeaklyConectedHRGroup() {
1196 connectedHRs = new HashSet<Taint>();
1197 id = -1; //this will be later modified
1198 waitingQueueCounter = 0;
1199 allocSiteToWaitingQueueMap = new Hashtable<AllocSite, Integer>();
1202 public void add(ArrayList<Taint> list) {
1203 for(Taint t: list) {
1208 public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) {
1209 if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) {
1210 return allocSiteToWaitingQueueMap.get(node.allocSite);
1213 allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter);
1214 return waitingQueueCounter++;
1218 public void add(Taint t) {
1219 connectedHRs.add(t);
1220 WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1221 connectedHRHash.put(t, this); //put new group into hash
1222 //If the taint was already in another group, move all its buddies over.
1223 if(oldGroup != this && oldGroup != null) {
1224 Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1227 while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) {
1228 this.add(relatedTaint);
1234 //This is a class that stores all the effects for an affected allocation site
1235 //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1236 //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1237 //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1238 //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1240 private class BucketOfEffects {
1241 // This table is used for lookup while creating the traversal.
1242 Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1244 //This table is used to help identify weakly connected groups: Contains ONLY
1245 //conflicting effects AND is only initialized when needed
1246 //String stores the field
1247 Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1249 public BucketOfEffects() {
1250 taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1253 public void add(Taint t, Effect e, boolean conflict) {
1254 EffectsGroup effectsForGivenTaint;
1256 if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1257 effectsForGivenTaint = new EffectsGroup();
1258 taint2EffectsGroup.put(t, effectsForGivenTaint);
1261 if (e.getField().getType().isPrimitive()) {
1263 effectsForGivenTaint.addPrimitive(e, true);
1266 effectsForGivenTaint.addObjEffect(e, conflict);
1270 if(potentiallyConflictingRoots == null) {
1271 potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1274 ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1275 if(taintsForField == null) {
1276 taintsForField = new ArrayList<Taint>();
1277 potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1280 if(!taintsForField.contains(t)) {
1281 taintsForField.add(t);
1287 private class TaintAndInternalHeapStructure {
1289 public Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap;
1291 public TaintAndInternalHeapStructure(Taint taint, Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap) {
1293 this.nodesInHeap = nodesInHeap;
1297 private class TraversalInfo {
1299 public ReachGraph rg;
1300 public TempDescriptor invar;
1302 public TraversalInfo(FlatNode fn, ReachGraph g) {
1308 public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) {