X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=Robust%2Fsrc%2FAnalysis%2FDisjoint%2FDisjointAnalysis.java;h=129bffd2ddafff07ed8f643d16c9c1ecb83dde25;hb=8c85b514ccea2de665db0d83f44004bc8e422f25;hp=9fb1f9c94f31c13c99149c707f5a42ca79a46f55;hpb=49ed071cafa6dbe18aca5971d19e3f8ae9689b8b;p=IRC.git diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 9fb1f9c9..129bffd2 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -3,6 +3,8 @@ package Analysis.Disjoint; import Analysis.CallGraph.*; import Analysis.Liveness; import Analysis.ArrayReferencees; +import Analysis.OoOJava.RBlockRelationAnalysis; +import Analysis.OoOJava.RBlockStatusAnalysis; import IR.*; import IR.Flat.*; import IR.Tree.Modifiers; @@ -11,6 +13,371 @@ import java.io.*; public class DisjointAnalysis { + + /////////////////////////////////////////// + // + // Public interface to discover possible + // sharing in the program under analysis + // + /////////////////////////////////////////// + + // if an object allocated at the target site may be + // reachable from both an object from root1 and an + // object allocated at root2, return TRUE + public boolean mayBothReachTarget( FlatMethod fm, + FlatNew fnRoot1, + FlatNew fnRoot2, + FlatNew fnTarget ) { + + AllocSite asr1 = getAllocationSiteFromFlatNew( fnRoot1 ); + AllocSite asr2 = getAllocationSiteFromFlatNew( fnRoot2 ); + assert asr1.isFlagged(); + assert asr2.isFlagged(); + + AllocSite ast = getAllocationSiteFromFlatNew( fnTarget ); + ReachGraph rg = getPartial( fm.getMethod() ); + + return rg.mayBothReachTarget( asr1, asr2, ast ); + } + + // similar to the method above, return TRUE if ever + // more than one object from the root allocation site + // may reach an object from the target site + public boolean mayManyReachTarget( FlatMethod fm, + FlatNew fnRoot, + FlatNew fnTarget ) { + + AllocSite asr = getAllocationSiteFromFlatNew( fnRoot ); + assert asr.isFlagged(); + + AllocSite ast = getAllocationSiteFromFlatNew( fnTarget ); + ReachGraph rg = getPartial( fm.getMethod() ); + + return rg.mayManyReachTarget( asr, ast ); + } + + + + + public HashSet + getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) { + checkAnalysisComplete(); + return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td); + } + + public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) { + checkAnalysisComplete(); + return getAllocSiteFromFlatNewPRIVATE(fn); + } + + public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) { + checkAnalysisComplete(); + return mapHrnIdToAllocSite.get(id); + } + + public Set hasPotentialSharing(Descriptor taskOrMethod, + int paramIndex1, + int paramIndex2) { + checkAnalysisComplete(); + ReachGraph rg=mapDescriptorToCompleteReachGraph.get(taskOrMethod); + FlatMethod fm=state.getMethodFlat(taskOrMethod); + assert(rg != null); + return rg.mayReachSharedObjects(fm, paramIndex1, paramIndex2); + } + + public Set hasPotentialSharing(Descriptor taskOrMethod, + int paramIndex, AllocSite alloc) { + checkAnalysisComplete(); + ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); + FlatMethod fm=state.getMethodFlat(taskOrMethod); + assert (rg != null); + return rg.mayReachSharedObjects(fm, paramIndex, alloc); + } + + public Set hasPotentialSharing(Descriptor taskOrMethod, + AllocSite alloc, int paramIndex) { + checkAnalysisComplete(); + ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); + FlatMethod fm=state.getMethodFlat(taskOrMethod); + assert (rg != null); + return rg.mayReachSharedObjects(fm, paramIndex, alloc); + } + + public Set hasPotentialSharing(Descriptor taskOrMethod, + AllocSite alloc1, AllocSite alloc2) { + checkAnalysisComplete(); + ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); + assert (rg != null); + return rg.mayReachSharedObjects(alloc1, alloc2); + } + + public String prettyPrintNodeSet(Set s) { + checkAnalysisComplete(); + + String out = "{\n"; + + Iterator i = s.iterator(); + while (i.hasNext()) { + HeapRegionNode n = i.next(); + + AllocSite as = n.getAllocSite(); + if (as == null) { + out += " " + n.toString() + ",\n"; + } else { + out += " " + n.toString() + ": " + as.toStringVerbose() + + ",\n"; + } + } + + out += "}\n"; + return out; + } + + // use the methods given above to check every possible sharing class + // between task parameters and flagged allocation sites reachable + // from the task + public void writeAllSharing(String outputFile, + String timeReport, + String justTime, + boolean tabularOutput, + int numLines + ) + throws java.io.IOException { + checkAnalysisComplete(); + + BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile)); + + if (!tabularOutput) { + bw.write("Conducting ownership analysis with allocation depth = " + + allocationDepth + "\n"); + bw.write(timeReport + "\n"); + } + + int numSharing = 0; + + // look through every task for potential sharing + Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + while (taskItr.hasNext()) { + TaskDescriptor td = (TaskDescriptor) taskItr.next(); + + if (!tabularOutput) { + bw.write("\n---------" + td + "--------\n"); + } + + HashSet allocSites = getFlaggedAllocationSitesReachableFromTask(td); + + Set common; + + // for each task parameter, check for sharing classes with + // other task parameters and every allocation site + // reachable from this task + boolean foundSomeSharing = false; + + FlatMethod fm = state.getMethodFlat(td); + for (int i = 0; i < fm.numParameters(); ++i) { + + // skip parameters with types that cannot reference + // into the heap + if( !shouldAnalysisTrack( fm.getParameter( i ).getType() ) ) { + continue; + } + + // for the ith parameter check for sharing classes to all + // higher numbered parameters + for (int j = i + 1; j < fm.numParameters(); ++j) { + + // skip parameters with types that cannot reference + // into the heap + if( !shouldAnalysisTrack( fm.getParameter( j ).getType() ) ) { + continue; + } + + + common = hasPotentialSharing(td, i, j); + if (!common.isEmpty()) { + foundSomeSharing = true; + ++numSharing; + if (!tabularOutput) { + bw.write("Potential sharing between parameters " + i + + " and " + j + ".\n"); + bw.write(prettyPrintNodeSet(common) + "\n"); + } + } + } + + // for the ith parameter, check for sharing classes against + // the set of allocation sites reachable from this + // task context + Iterator allocItr = allocSites.iterator(); + while (allocItr.hasNext()) { + AllocSite as = (AllocSite) allocItr.next(); + common = hasPotentialSharing(td, i, as); + if (!common.isEmpty()) { + foundSomeSharing = true; + ++numSharing; + if (!tabularOutput) { + bw.write("Potential sharing between parameter " + i + + " and " + as.getFlatNew() + ".\n"); + bw.write(prettyPrintNodeSet(common) + "\n"); + } + } + } + } + + // for each allocation site check for sharing classes with + // other allocation sites in the context of execution + // of this task + HashSet outerChecked = new HashSet(); + Iterator allocItr1 = allocSites.iterator(); + while (allocItr1.hasNext()) { + AllocSite as1 = (AllocSite) allocItr1.next(); + + Iterator allocItr2 = allocSites.iterator(); + while (allocItr2.hasNext()) { + AllocSite as2 = (AllocSite) allocItr2.next(); + + if (!outerChecked.contains(as2)) { + common = hasPotentialSharing(td, as1, as2); + + if (!common.isEmpty()) { + foundSomeSharing = true; + ++numSharing; + if (!tabularOutput) { + bw.write("Potential sharing between " + + as1.getFlatNew() + " and " + + as2.getFlatNew() + ".\n"); + bw.write(prettyPrintNodeSet(common) + "\n"); + } + } + } + } + + outerChecked.add(as1); + } + + if (!foundSomeSharing) { + if (!tabularOutput) { + bw.write("No sharing between flagged objects in Task " + td + + ".\n"); + } + } + } + + + if (tabularOutput) { + bw.write(" & " + numSharing + " & " + justTime + " & " + numLines + + " & " + numMethodsAnalyzed() + " \\\\\n"); + } else { + bw.write("\nNumber sharing classes: "+numSharing); + } + + bw.close(); + } + + + + // this version of writeAllSharing is for Java programs that have no tasks + // *********************************** + // WARNING: THIS DOES NOT DO THE RIGHT THING, REPORTS 0 ALWAYS! + // It should use mayBothReachTarget and mayManyReachTarget like + // OoOJava does to query analysis results + // *********************************** + public void writeAllSharingJava(String outputFile, + String timeReport, + String justTime, + boolean tabularOutput, + int numLines + ) + throws java.io.IOException { + checkAnalysisComplete(); + + assert !state.TASK; + + int numSharing = 0; + + BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile)); + + bw.write("Conducting disjoint reachability analysis with allocation depth = " + + allocationDepth + "\n"); + bw.write(timeReport + "\n\n"); + + boolean foundSomeSharing = false; + + Descriptor d = typeUtil.getMain(); + HashSet allocSites = getFlaggedAllocationSites(d); + + // for each allocation site check for sharing classes with + // other allocation sites in the context of execution + // of this task + HashSet outerChecked = new HashSet(); + Iterator allocItr1 = allocSites.iterator(); + while (allocItr1.hasNext()) { + AllocSite as1 = (AllocSite) allocItr1.next(); + + Iterator allocItr2 = allocSites.iterator(); + while (allocItr2.hasNext()) { + AllocSite as2 = (AllocSite) allocItr2.next(); + + if (!outerChecked.contains(as2)) { + Set common = hasPotentialSharing(d, + as1, as2); + + if (!common.isEmpty()) { + foundSomeSharing = true; + bw.write("Potential sharing between " + + as1.getDisjointAnalysisId() + " and " + + as2.getDisjointAnalysisId() + ".\n"); + bw.write(prettyPrintNodeSet(common) + "\n"); + ++numSharing; + } + } + } + + outerChecked.add(as1); + } + + if (!foundSomeSharing) { + bw.write("No sharing classes between flagged objects found.\n"); + } else { + bw.write("\nNumber sharing classes: "+numSharing); + } + + bw.write("Number of methods analyzed: "+numMethodsAnalyzed()+"\n"); + + bw.close(); + } + + /////////////////////////////////////////// + // + // end public interface + // + /////////////////////////////////////////// + + + + protected void checkAnalysisComplete() { + if( !analysisComplete ) { + throw new Error("Warning: public interface method called while analysis is running."); + } + } + + + + + + + // run in faster mode, only when bugs wrung out! + public static boolean releaseMode; + + // use command line option to set this, analysis + // should attempt to be deterministic + public static boolean determinismDesired; + + // when we want to enforce determinism in the + // analysis we need to sort descriptors rather + // than toss them in efficient sets, use this + public static DescriptorComparator dComp = + new DescriptorComparator(); // data from the compiler @@ -18,9 +385,23 @@ public class DisjointAnalysis { public CallGraph callGraph; public Liveness liveness; public ArrayReferencees arrayReferencees; + public RBlockRelationAnalysis rblockRel; + public RBlockStatusAnalysis rblockStatus; public TypeUtil typeUtil; public int allocationDepth; + protected boolean doEffectsAnalysis = false; + protected EffectsAnalysis effectsAnalysis; + + // data structure for public interface + private Hashtable< Descriptor, HashSet > + mapDescriptorToAllocSiteSet; + + + // for public interface methods to warn that they + // are grabbing results during analysis + private boolean analysisComplete; + // used to identify HeapRegionNode objects // A unique ID equates an object in one @@ -53,6 +434,8 @@ public class DisjointAnalysis { // current descriptors to visit in fixed-point // interprocedural analysis, prioritized by // dependency in the call graph + protected Stack + descriptorsToVisitStack; protected PriorityQueue descriptorsToVisitQ; @@ -67,6 +450,12 @@ public class DisjointAnalysis { protected Hashtable mapDescriptorToPriority; + // when analyzing a method and scheduling more: + // remember set of callee's enqueued for analysis + // so they can be put on top of the callers in + // the stack-visit mode + protected Set + calleesToEnqueue; // maps a descriptor to its current partial result // from the intraprocedural fixed-point analysis-- @@ -82,6 +471,11 @@ public class DisjointAnalysis { protected Hashtable< Descriptor, Set > mapDescriptorToSetDependents; + // if the analysis client wants to flag allocation sites + // programmatically, it should provide a set of FlatNew + // statements--this may be null if unneeded + protected Set sitesToFlag; + // maps each flat new to one analysis abstraction // allocate site object, these exist outside reach graphs protected Hashtable @@ -101,7 +495,20 @@ public class DisjointAnalysis { protected Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > > mapDescriptorToIHMcontributions; - // TODO -- CHANGE EDGE/TYPE/FIELD storage! + // additionally, keep a mapping from descriptors to the + // merged in-coming initial context, because we want this + // initial context to be STRICTLY MONOTONIC + protected Hashtable + mapDescriptorToInitialContext; + + // make the result for back edges analysis-wide STRICTLY + // MONOTONIC as well, but notice we use FlatNode as the + // key for this map: in case we want to consider other + // nodes as back edge's in future implementations + protected Hashtable + mapBackEdgeToMonotone; + + public static final String arrayElementFieldName = "___element_"; static protected Hashtable mapTypeToArrayField; @@ -115,12 +522,30 @@ public class DisjointAnalysis { // unique filenames protected Hashtable mapDescriptorToNumUpdates; + + //map task descriptor to initial task parameter + protected Hashtable + mapDescriptorToReachGraph; + + protected PointerMethod pm; + + static protected Hashtable fn2rg = + new Hashtable(); + + private Hashtable fc2enclosing; // allocate various structures that are not local // to a single class method--should be done once - protected void allocateStructures() { - descriptorsToAnalyze = new HashSet(); + protected void allocateStructures() { + + if( determinismDesired ) { + // use an ordered set + descriptorsToAnalyze = new TreeSet( dComp ); + } else { + // otherwise use a speedy hashset + descriptorsToAnalyze = new HashSet(); + } mapDescriptorToCompleteReachGraph = new Hashtable(); @@ -137,85 +562,217 @@ public class DisjointAnalysis { mapDescriptorToIHMcontributions = new Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >(); + mapDescriptorToInitialContext = + new Hashtable(); + + mapBackEdgeToMonotone = + new Hashtable(); + mapHrnIdToAllocSite = new Hashtable(); mapTypeToArrayField = new Hashtable (); - descriptorsToVisitQ = - new PriorityQueue(); + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { + descriptorsToVisitStack = + new Stack(); + } + + if( state.DISJOINTDVISITPQUE ) { + descriptorsToVisitQ = + new PriorityQueue(); + } descriptorsToVisitSet = new HashSet(); mapDescriptorToPriority = new Hashtable(); + + calleesToEnqueue = + new HashSet(); + + mapDescriptorToAllocSiteSet = + new Hashtable >(); + + mapDescriptorToReachGraph = + new Hashtable(); + + pm = new PointerMethod(); + + fc2enclosing = new Hashtable(); } // this analysis generates a disjoint reachability // graph for every reachable method in the program - public DisjointAnalysis( State s, - TypeUtil tu, - CallGraph cg, - Liveness l, - ArrayReferencees ar - ) throws java.io.IOException { - init( s, tu, cg, l, ar ); + public DisjointAnalysis( State s, + TypeUtil tu, + CallGraph cg, + Liveness l, + ArrayReferencees ar, + Set sitesToFlag, + RBlockRelationAnalysis rra, + RBlockStatusAnalysis rsa + ) { + init( s, tu, cg, l, ar, sitesToFlag, rra, rsa, false ); + } + + public DisjointAnalysis( State s, + TypeUtil tu, + CallGraph cg, + Liveness l, + ArrayReferencees ar, + Set sitesToFlag, + RBlockRelationAnalysis rra, + RBlockStatusAnalysis rsa, + boolean suppressOutput + ) { + init( s, tu, cg, l, ar, sitesToFlag, rra, rsa, suppressOutput ); } - protected void init( State state, - TypeUtil typeUtil, - CallGraph callGraph, - Liveness liveness, - ArrayReferencees arrayReferencees - ) throws java.io.IOException { + protected void init( State state, + TypeUtil typeUtil, + CallGraph callGraph, + Liveness liveness, + ArrayReferencees arrayReferencees, + Set sitesToFlag, + RBlockRelationAnalysis rra, + RBlockStatusAnalysis rsa, + boolean suppressOutput + ) { + + analysisComplete = false; - this.state = state; - this.typeUtil = typeUtil; - this.callGraph = callGraph; - this.liveness = liveness; - this.arrayReferencees = arrayReferencees; + this.state = state; + this.typeUtil = typeUtil; + this.callGraph = callGraph; + this.liveness = liveness; + this.arrayReferencees = arrayReferencees; + this.sitesToFlag = sitesToFlag; + this.rblockRel = rra; + this.rblockStatus = rsa; + + if( rblockRel != null ) { + doEffectsAnalysis = true; + effectsAnalysis = new EffectsAnalysis(); + } + this.allocationDepth = state.DISJOINTALLOCDEPTH; - this.writeFinalDOTs = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL; - this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS && state.DISJOINTWRITEALL; + this.releaseMode = state.DISJOINTRELEASEMODE; + this.determinismDesired = state.DISJOINTDETERMINISM; + + this.writeFinalDOTs = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL && !suppressOutput; + this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS && state.DISJOINTWRITEALL && !suppressOutput; + + this.takeDebugSnapshots = state.DISJOINTSNAPSYMBOL != null; + this.descSymbolDebug = state.DISJOINTSNAPSYMBOL; + this.visitStartCapture = state.DISJOINTSNAPVISITTOSTART; + this.numVisitsToCapture = state.DISJOINTSNAPNUMVISITS; + this.stopAfterCapture = state.DISJOINTSNAPSTOPAFTER; + this.snapVisitCounter = 1; // count visits from 1 (user will write 1, means 1st visit) + this.snapNodeCounter = 0; // count nodes from 0 + + assert + state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITPQUE || + state.DISJOINTDVISITSTACKEESONTOP; + assert !(state.DISJOINTDVISITSTACK && state.DISJOINTDVISITPQUE); + assert !(state.DISJOINTDVISITSTACK && state.DISJOINTDVISITSTACKEESONTOP); + assert !(state.DISJOINTDVISITPQUE && state.DISJOINTDVISITSTACKEESONTOP); // set some static configuration for ReachGraphs ReachGraph.allocationDepth = allocationDepth; ReachGraph.typeUtil = typeUtil; + ReachGraph.debugCallSiteVisitStartCapture + = state.DISJOINTDEBUGCALLVISITTOSTART; + + ReachGraph.debugCallSiteNumVisitsToCapture + = state.DISJOINTDEBUGCALLNUMVISITS; + + ReachGraph.debugCallSiteStopAfter + = state.DISJOINTDEBUGCALLSTOPAFTER; + + ReachGraph.debugCallSiteVisitCounter + = 0; // count visits from 1, is incremented before first visit + + + allocateStructures(); double timeStartAnalysis = (double) System.nanoTime(); // start interprocedural fixed-point computation - analyzeMethods(); + try { + analyzeMethods(); + } catch( IOException e ) { + throw new Error( "IO Exception while writing disjointness analysis output." ); + } + + analysisComplete=true; + double timeEndAnalysis = (double) System.nanoTime(); double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) ); - String treport = String.format( "The reachability analysis took %.3f sec.", dt ); + + String treport; + if( sitesToFlag != null ) { + treport = String.format( "Disjoint reachability analysis flagged %d sites and took %.3f sec.", sitesToFlag.size(), dt ); + } else { + treport = String.format( "Disjoint reachability analysis took %.3f sec.", dt ); + } String justtime = String.format( "%.2f", dt ); System.out.println( treport ); - if( writeFinalDOTs && !writeAllIncrementalDOTs ) { - writeFinalGraphs(); - } - if( state.DISJOINTALIASFILE != null ) { - if( state.TASK ) { - // not supporting tasks yet... - } else { - /* - writeAllAliasesJava( aliasFile, - treport, - justtime, - state.DISJOINTALIASTAB, - state.lines ); - */ + try { + if( writeFinalDOTs && !writeAllIncrementalDOTs ) { + writeFinalGraphs(); + } + + if( state.DISJOINTWRITEIHMS && !suppressOutput ) { + writeFinalIHMs(); + } + + if( state.DISJOINTWRITEINITCONTEXTS && !suppressOutput ) { + writeInitialContexts(); + } + + if( state.DISJOINTALIASFILE != null && !suppressOutput ) { + if( state.TASK ) { + writeAllSharing(state.DISJOINTALIASFILE, treport, justtime, state.DISJOINTALIASTAB, state.lines); + } else { + writeAllSharingJava(state.DISJOINTALIASFILE, + treport, + justtime, + state.DISJOINTALIASTAB, + state.lines + ); + } } + } catch( IOException e ) { + throw new Error( "IO Exception while writing disjointness analysis output." ); + } + + } + + + protected boolean moreDescriptorsToVisit() { + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { + return !descriptorsToVisitStack.isEmpty(); + + } else if( state.DISJOINTDVISITPQUE ) { + return !descriptorsToVisitQ.isEmpty(); } + + throw new Error( "Neither descriptor visiting mode set" ); } @@ -223,24 +780,33 @@ public class DisjointAnalysis { // method's callees are updated, it must be reanalyzed protected void analyzeMethods() throws java.io.IOException { + // task or non-task (java) mode determines what the roots + // of the call chain are, and establishes the set of methods + // reachable from the roots that will be analyzed + if( state.TASK ) { - // This analysis does not support Bamboo at the moment, - // but if it does in the future we would initialize the - // set of descriptors to analyze as the program-reachable - // tasks and the methods callable by them. For Java, - // just methods reachable from the main method. - System.out.println( "No Bamboo support yet..." ); - System.exit( -1 ); - + System.out.println( "Bamboo mode..." ); + + Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + while( taskItr.hasNext() ) { + TaskDescriptor td = (TaskDescriptor) taskItr.next(); + if( !descriptorsToAnalyze.contains( td ) ) { + // add all methods transitively reachable from the + // tasks as well + descriptorsToAnalyze.add( td ); + descriptorsToAnalyze.addAll( callGraph.getAllMethods( td ) ); + } + } + } else { + System.out.println( "Java mode..." ); + // add all methods transitively reachable from the // source's main to set for analysis mdSourceEntry = typeUtil.getMain(); descriptorsToAnalyze.add( mdSourceEntry ); - descriptorsToAnalyze.addAll( - callGraph.getAllMethods( mdSourceEntry ) - ); - + descriptorsToAnalyze.addAll( callGraph.getAllMethods( mdSourceEntry ) ); + // fabricate an empty calling context that will call // the source's main, but call graph doesn't know // about it, so explicitly add it @@ -248,27 +814,69 @@ public class DisjointAnalysis { descriptorsToAnalyze.add( mdAnalysisEntry ); } - // topologically sort according to the call graph so - // leaf calls are ordered first, smarter analysis order - LinkedList sortedDescriptors = - topologicalSort( descriptorsToAnalyze ); - - // add sorted descriptors to priority queue, and duplicate - // the queue as a set for efficiently testing whether some - // method is marked for analysis - int p = 0; - Iterator dItr = sortedDescriptors.iterator(); - while( dItr.hasNext() ) { - Descriptor d = dItr.next(); - mapDescriptorToPriority.put( d, new Integer( p ) ); - descriptorsToVisitQ.add( new DescriptorQWrapper( p, d ) ); - descriptorsToVisitSet.add( d ); - ++p; + + // now, depending on the interprocedural mode for visiting + // methods, set up the needed data structures + + if( state.DISJOINTDVISITPQUE ) { + + // topologically sort according to the call graph so + // leaf calls are last, helps build contexts up first + LinkedList sortedDescriptors = + topologicalSort( descriptorsToAnalyze ); + + // add sorted descriptors to priority queue, and duplicate + // the queue as a set for efficiently testing whether some + // method is marked for analysis + int p = 0; + Iterator dItr; + + // for the priority queue, give items at the head + // of the sorted list a low number (highest priority) + while( !sortedDescriptors.isEmpty() ) { + Descriptor d = sortedDescriptors.removeFirst(); + mapDescriptorToPriority.put( d, new Integer( p ) ); + descriptorsToVisitQ.add( new DescriptorQWrapper( p, d ) ); + descriptorsToVisitSet.add( d ); + ++p; + } + + } else if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { + // if we're doing the stack scheme, just throw the root + // method or tasks on the stack + if( state.TASK ) { + Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + while( taskItr.hasNext() ) { + TaskDescriptor td = (TaskDescriptor) taskItr.next(); + descriptorsToVisitStack.add( td ); + descriptorsToVisitSet.add( td ); + } + + } else { + descriptorsToVisitStack.add( mdAnalysisEntry ); + descriptorsToVisitSet.add( mdAnalysisEntry ); + } + + } else { + throw new Error( "Unknown method scheduling mode" ); } - // analyze methods from the priority queue until it is empty - while( !descriptorsToVisitQ.isEmpty() ) { - Descriptor d = descriptorsToVisitQ.poll().getDescriptor(); + + // analyze scheduled methods until there are no more to visit + while( moreDescriptorsToVisit() ) { + Descriptor d = null; + + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { + d = descriptorsToVisitStack.pop(); + + } else if( state.DISJOINTDVISITPQUE ) { + d = descriptorsToVisitQ.poll().getDescriptor(); + } + assert descriptorsToVisitSet.contains( d ); descriptorsToVisitSet.remove( d ); @@ -282,30 +890,49 @@ public class DisjointAnalysis { System.out.println( "Analyzing " + d ); + if( state.DISJOINTDVISITSTACKEESONTOP ) { + assert calleesToEnqueue.isEmpty(); + } + ReachGraph rg = analyzeMethod( d ); ReachGraph rgPrev = getPartial( d ); - + if( !rg.equals( rgPrev ) ) { setPartial( d, rg ); + + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " complete graph changed, scheduling callers for analysis:" ); + } - // results for d changed, so queue dependents + // results for d changed, so enqueue dependents // of d for further analysis Iterator depsItr = getDependents( d ).iterator(); while( depsItr.hasNext() ) { Descriptor dNext = depsItr.next(); + enqueue( dNext ); - if( !descriptorsToVisitSet.contains( dNext ) ) { - Integer priority = mapDescriptorToPriority.get( dNext ); - descriptorsToVisitQ.add( new DescriptorQWrapper( priority , - dNext ) - ); - descriptorsToVisitSet.add( dNext ); - } + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " "+dNext ); + } } - } - } - } + } + + // whether or not the method under analysis changed, + // we may have some callees that are scheduled for + // more analysis, and they should go on the top of + // the stack now (in other method-visiting modes they + // are already enqueued at this point + if( state.DISJOINTDVISITSTACKEESONTOP ) { + Iterator depsItr = calleesToEnqueue.iterator(); + while( depsItr.hasNext() ) { + Descriptor dNext = depsItr.next(); + enqueue( dNext ); + } + calleesToEnqueue.clear(); + } + } + } protected ReachGraph analyzeMethod( Descriptor d ) throws java.io.IOException { @@ -317,10 +944,19 @@ public class DisjointAnalysis { } else { fm = state.getMethodFlat( d ); } - + pm.analyzeMethod( fm ); + // intraprocedural work set Set flatNodesToVisit = new HashSet(); flatNodesToVisit.add( fm ); + + // if determinism is desired by client, shadow the + // set with a queue to make visit order deterministic + Queue flatNodesToVisitQ = null; + if( determinismDesired ) { + flatNodesToVisitQ = new LinkedList(); + flatNodesToVisitQ.add( fm ); + } // mapping of current partial results Hashtable mapFlatNodeToReachGraph = @@ -331,35 +967,62 @@ public class DisjointAnalysis { HashSet setReturns = new HashSet(); while( !flatNodesToVisit.isEmpty() ) { - FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); - flatNodesToVisit.remove( fn ); - //System.out.println( " "+fn ); + FlatNode fn; + if( determinismDesired ) { + assert !flatNodesToVisitQ.isEmpty(); + fn = flatNodesToVisitQ.remove(); + } else { + fn = flatNodesToVisit.iterator().next(); + } + flatNodesToVisit.remove( fn ); // effect transfer function defined by this node, // then compare it to the old graph at this node // to see if anything was updated. ReachGraph rg = new ReachGraph(); + TaskDescriptor taskDesc; + if(fn instanceof FlatMethod && (taskDesc=((FlatMethod)fn).getTask())!=null){ + if(mapDescriptorToReachGraph.containsKey(taskDesc)){ + // retrieve existing reach graph if it is not first time + rg=mapDescriptorToReachGraph.get(taskDesc); + }else{ + // create initial reach graph for a task + rg=createInitialTaskReachGraph((FlatMethod)fn); + rg.globalSweep(); + mapDescriptorToReachGraph.put(taskDesc, rg); + } + } // start by merging all node's parents' graphs - for( int i = 0; i < fn.numPrev(); ++i ) { - FlatNode pn = fn.getPrev( i ); + for( int i = 0; i < pm.numPrev(fn); ++i ) { + FlatNode pn = pm.getPrev(fn,i); if( mapFlatNodeToReachGraph.containsKey( pn ) ) { ReachGraph rgParent = mapFlatNodeToReachGraph.get( pn ); rg.merge( rgParent ); } } + + + if( takeDebugSnapshots && + d.getSymbol().equals( descSymbolDebug ) + ) { + debugSnapshot( rg, fn, true ); + } + // modify rg with appropriate transfer function - analyzeFlatNode( d, fm, fn, setReturns, rg ); - - /* + rg = analyzeFlatNode( d, fm, fn, setReturns, rg ); + + if( takeDebugSnapshots && - d.getSymbol().equals( descSymbolDebug ) ) { - debugSnapshot(og,fn); + d.getSymbol().equals( descSymbolDebug ) + ) { + debugSnapshot( rg, fn, false ); + ++snapNodeCounter; } - */ + // if the results of the new graph are different from // the current graph at this node, replace the graph @@ -368,15 +1031,20 @@ public class DisjointAnalysis { if( !rg.equals( rgPrev ) ) { mapFlatNodeToReachGraph.put( fn, rg ); - for( int i = 0; i < fn.numNext(); i++ ) { - FlatNode nn = fn.getNext( i ); + for( int i = 0; i < pm.numNext( fn ); i++ ) { + FlatNode nn = pm.getNext( fn, i ); + flatNodesToVisit.add( nn ); + if( determinismDesired ) { + flatNodesToVisitQ.add( nn ); + } } } } + // end by merging all return nodes into a complete - // ownership graph that represents all possible heap + // reach graph that represents all possible heap // states after the flat method returns ReachGraph completeGraph = new ReachGraph(); @@ -390,12 +1058,31 @@ public class DisjointAnalysis { completeGraph.merge( rgRet ); } - + + + if( takeDebugSnapshots && + d.getSymbol().equals( descSymbolDebug ) + ) { + // increment that we've visited the debug snap + // method, and reset the node counter + System.out.println( " @@@ debug snap at visit "+snapVisitCounter ); + ++snapVisitCounter; + snapNodeCounter = 0; + + if( snapVisitCounter == visitStartCapture + numVisitsToCapture && + stopAfterCapture + ) { + System.out.println( "!!! Stopping analysis after debug snap captures. !!!" ); + System.exit( 0 ); + } + } + + return completeGraph; } - protected void + protected ReachGraph analyzeFlatNode( Descriptor d, FlatMethod fmContaining, FlatNode fn, @@ -406,15 +1093,15 @@ public class DisjointAnalysis { // any variables that are no longer live should be // nullified in the graph to reduce edges - // NOTE: it is not clear we need this. It costs a - // liveness calculation for every method, so only - // turn it on if we find we actually need it. - // rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) ); + //rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) ); - - TempDescriptor lhs; - TempDescriptor rhs; - FieldDescriptor fld; + TempDescriptor lhs; + TempDescriptor rhs; + FieldDescriptor fld; + TypeDescriptor tdElement; + FieldDescriptor fdElement; + FlatSESEEnterNode sese; + FlatSESEExitNode fsexn; // use node type to decide what transfer function // to apply to the reachability graph @@ -437,20 +1124,17 @@ public class DisjointAnalysis { assert fc.getMethod().equals( d ); - // some call sites are in same method context though, - // and all of them should be merged together first, - // then heaps from different contexts should be merged - // THIS ASSUMES DIFFERENT CONTEXTS NEED SPECIAL CONSIDERATION! - // such as, do allocation sites need to be aged? - - rg.merge_diffMethodContext( rgContrib ); - } - - FlatMethod fm = (FlatMethod) fn; - for( int i = 0; i < fm.numParameters(); ++i ) { - TempDescriptor tdParam = fm.getParameter( i ); - //assert rg.hasVariable( tdParam ); + rg.merge( rgContrib ); } + + // additionally, we are enforcing STRICT MONOTONICITY for the + // method's initial context, so grow the context by whatever + // the previously computed context was, and put the most + // up-to-date context back in the map + ReachGraph rgPrevContext = mapDescriptorToInitialContext.get( d ); + rg.merge( rgPrevContext ); + mapDescriptorToInitialContext.put( d, rg ); + } break; case FKind.FlatOpNode: @@ -458,7 +1142,19 @@ public class DisjointAnalysis { if( fon.getOp().getOp() == Operation.ASSIGN ) { lhs = fon.getDest(); rhs = fon.getLeft(); - rg.assignTempXEqualToTempY( lhs, rhs ); + + // before transfer, do effects analysis support + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + if(rblockStatus.isInCriticalRegion(fmContaining, fn)){ + // x gets status of y + if(!rg.isAccessible(rhs)){ + rg.makeInaccessible(lhs); + } + } + } + + // transfer func + rg.assignTempXEqualToTempY( lhs, rhs ); } break; @@ -469,217 +1165,458 @@ public class DisjointAnalysis { TypeDescriptor td = fcn.getType(); assert td != null; + + // before transfer, do effects analysis support + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + if(rblockStatus.isInCriticalRegion(fmContaining, fn)){ + // x gets status of y + if(!rg.isAccessible(rhs)){ + rg.makeInaccessible(lhs); + } + } + } + // transfer func rg.assignTempXEqualToCastedTempY( lhs, rhs, td ); break; case FKind.FlatFieldNode: FlatFieldNode ffn = (FlatFieldNode) fn; + lhs = ffn.getDst(); rhs = ffn.getSrc(); fld = ffn.getField(); - if( !fld.getType().isImmutable() || fld.getType().isArray() ) { + + // before graph transform, possible inject + // a stall-site taint + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + + if(rblockStatus.isInCriticalRegion(fmContaining, fn)){ + // x=y.f, stall y if not accessible + // contributes read effects on stall site of y + if(!rg.isAccessible(rhs)) { + rg.taintStallSite(fn, rhs); + } + + // after this, x and y are accessbile. + rg.makeAccessible(lhs); + rg.makeAccessible(rhs); + } + } + + if( shouldAnalysisTrack( fld.getType() ) ) { + // transfer func rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld ); } + + // after transfer, use updated graph to + // do effects analysis + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fld ); + } break; case FKind.FlatSetFieldNode: FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + lhs = fsfn.getDst(); fld = fsfn.getField(); rhs = fsfn.getSrc(); - if( !fld.getType().isImmutable() || fld.getType().isArray() ) { - rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs ); - } - break; - case FKind.FlatElementNode: - FlatElementNode fen = (FlatElementNode) fn; - lhs = fen.getDst(); + boolean strongUpdate = false; + + // before transfer func, possibly inject + // stall-site taints + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + + if(rblockStatus.isInCriticalRegion(fmContaining, fn)){ + // x.y=f , stall x and y if they are not accessible + // also contribute write effects on stall site of x + if(!rg.isAccessible(lhs)) { + rg.taintStallSite(fn, lhs); + } + + if(!rg.isAccessible(rhs)) { + rg.taintStallSite(fn, rhs); + } + + // accessible status update + rg.makeAccessible(lhs); + rg.makeAccessible(rhs); + } + } + + if( shouldAnalysisTrack( fld.getType() ) ) { + // transfer func + strongUpdate = rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs ); + } + + // use transformed graph to do effects analysis + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fld, strongUpdate ); + } + break; + + case FKind.FlatElementNode: + FlatElementNode fen = (FlatElementNode) fn; + + lhs = fen.getDst(); rhs = fen.getSrc(); - if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) { - assert rhs.getType() != null; - assert rhs.getType().isArray(); - - TypeDescriptor tdElement = rhs.getType().dereference(); - FieldDescriptor fdElement = getArrayField( tdElement ); - + assert rhs.getType() != null; + assert rhs.getType().isArray(); + + tdElement = rhs.getType().dereference(); + fdElement = getArrayField( tdElement ); + + // before transfer func, possibly inject + // stall-site taint + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + + if(rblockStatus.isInCriticalRegion(fmContaining, fn)){ + // x=y.f, stall y if not accessible + // contributes read effects on stall site of y + // after this, x and y are accessbile. + if(!rg.isAccessible(rhs)) { + rg.taintStallSite(fn, rhs); + } + + rg.makeAccessible(lhs); + rg.makeAccessible(rhs); + } + } + + if( shouldAnalysisTrack( lhs.getType() ) ) { + // transfer func rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement ); } + + // use transformed graph to do effects analysis + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fdElement ); + } break; case FKind.FlatSetElementNode: FlatSetElementNode fsen = (FlatSetElementNode) fn; - if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) { - // skip this node if it cannot create new reachability paths - break; - } - lhs = fsen.getDst(); rhs = fsen.getSrc(); - if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) { - assert lhs.getType() != null; - assert lhs.getType().isArray(); - - TypeDescriptor tdElement = lhs.getType().dereference(); - FieldDescriptor fdElement = getArrayField( tdElement ); + assert lhs.getType() != null; + assert lhs.getType().isArray(); - rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs ); + tdElement = lhs.getType().dereference(); + fdElement = getArrayField( tdElement ); + + // before transfer func, possibly inject + // stall-site taints + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + + if(rblockStatus.isInCriticalRegion(fmContaining, fn)){ + // x.y=f , stall x and y if they are not accessible + // also contribute write effects on stall site of x + if(!rg.isAccessible(lhs)) { + rg.taintStallSite(fn, lhs); + } + + if(!rg.isAccessible(rhs)) { + rg.taintStallSite(fn, rhs); + } + + // accessible status update + rg.makeAccessible(lhs); + rg.makeAccessible(rhs); + } + } + + if( shouldAnalysisTrack( rhs.getType() ) ) { + // transfer func, BUT + // skip this node if it cannot create new reachability paths + if( !arrayReferencees.doesNotCreateNewReaching( fsen ) ) { + rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs ); + } + } + + // use transformed graph to do effects analysis + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fdElement, + false ); } break; case FKind.FlatNew: FlatNew fnn = (FlatNew) fn; lhs = fnn.getDst(); - if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) { + if( shouldAnalysisTrack( lhs.getType() ) ) { AllocSite as = getAllocSiteFromFlatNewPRIVATE( fnn ); - rg.assignTempEqualToNewAlloc( lhs, as ); + + // before transform, support effects analysis + if (doEffectsAnalysis && fmContaining != fmAnalysisEntry) { + if (rblockStatus.isInCriticalRegion(fmContaining, fn)) { + // after creating new object, lhs is accessible + rg.makeAccessible(lhs); + } + } + + // transfer func + rg.assignTempEqualToNewAlloc( lhs, as ); + } + break; + + case FKind.FlatSESEEnterNode: + sese = (FlatSESEEnterNode) fn; + + if( sese.getIsCallerSESEplaceholder() ) { + // ignore these dummy rblocks! + break; + } + + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + + // always remove ALL stall site taints at enter + rg.removeAllStallSiteTaints(); + + // inject taints for in-set vars + rg.taintInSetVars( sese ); + + } + break; + + case FKind.FlatSESEExitNode: + fsexn = (FlatSESEExitNode) fn; + sese = fsexn.getFlatEnter(); + + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + + // @ sese exit make all live variables + // inaccessible to later parent statements + rg.makeInaccessible( liveness.getLiveInTemps( fmContaining, fn ) ); + + // always remove ALL stall site taints at exit + rg.removeAllStallSiteTaints(); + + // remove in-set var taints for the exiting rblock + rg.removeInContextTaints( sese ); } break; + case FKind.FlatCall: { + Descriptor mdCaller; + if( fmContaining.getMethod() != null ){ + mdCaller = fmContaining.getMethod(); + } else { + mdCaller = fmContaining.getTask(); + } FlatCall fc = (FlatCall) fn; MethodDescriptor mdCallee = fc.getMethod(); FlatMethod fmCallee = state.getMethodFlat( mdCallee ); + + boolean debugCallSite = + mdCaller.getSymbol().equals( state.DISJOINTDEBUGCALLER ) && + mdCallee.getSymbol().equals( state.DISJOINTDEBUGCALLEE ); + + boolean writeDebugDOTs = false; + boolean stopAfter = false; + if( debugCallSite ) { + ++ReachGraph.debugCallSiteVisitCounter; + System.out.println( " $$$ Debug call site visit "+ + ReachGraph.debugCallSiteVisitCounter+ + " $$$" + ); + if( + (ReachGraph.debugCallSiteVisitCounter >= + ReachGraph.debugCallSiteVisitStartCapture) && + + (ReachGraph.debugCallSiteVisitCounter < + ReachGraph.debugCallSiteVisitStartCapture + + ReachGraph.debugCallSiteNumVisitsToCapture) + ) { + writeDebugDOTs = true; + System.out.println( " $$$ Capturing this call site visit $$$" ); + if( ReachGraph.debugCallSiteStopAfter && + (ReachGraph.debugCallSiteVisitCounter == + ReachGraph.debugCallSiteVisitStartCapture + + ReachGraph.debugCallSiteNumVisitsToCapture - 1) + ) { + stopAfter = true; + } + } + } + + // calculate the heap this call site can reach--note this is + // not used for the current call site transform, we are + // grabbing this heap model for future analysis of the callees, + // so if different results emerge we will return to this site ReachGraph heapForThisCall_old = getIHMcontribution( mdCallee, fc ); - ReachGraph heapForThisCall_cur = rg.makeCalleeView( fc, - fmCallee ); + // the computation of the callee-reachable heap + // is useful for making the callee starting point + // and for applying the call site transfer function + Set callerNodeIDsCopiedToCallee = + new HashSet(); - if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) { - // if heap at call site changed, update the contribution, - // and reschedule the callee for analysis - addIHMcontribution( mdCallee, fc, heapForThisCall_cur ); + ReachGraph heapForThisCall_cur = + rg.makeCalleeView( fc, + fmCallee, + callerNodeIDsCopiedToCallee, + writeDebugDOTs + ); - if( !descriptorsToVisitSet.contains( mdCallee ) ) { - Integer priority = mapDescriptorToPriority.get( mdCallee ); - descriptorsToVisitQ.add( new DescriptorQWrapper( priority, - mdCallee ) - ); - descriptorsToVisitSet.add( mdCallee ); - } - } - - // now that we've taken care of that, go ahead and update - // the reach graph for this FlatCall node by whatever callee - // result we do have - - - /* - ReachGraph ogMergeOfAllPossibleCalleeResults = new ReachGraph(); - - if( md.isStatic() ) { - // a static method is simply always the same, makes life easy - ogMergeOfAllPossibleCalleeResults = og; + if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) { + // if heap at call site changed, update the contribution, + // and reschedule the callee for analysis + addIHMcontribution( mdCallee, fc, heapForThisCall_cur ); - Set aliasedParamIndices = - ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm); + // map a FlatCall to its enclosing method/task descriptor + // so we can write that info out later + fc2enclosing.put( fc, mdCaller ); - Descriptor mcNew = new Descriptor( md, aliasedParamIndices ); - Set contexts = mapDescriptorToAllDescriptors.get( md ); - assert contexts != null; - contexts.add( mcNew ); + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " context changed, scheduling callee: "+mdCallee ); + } - addDependent( mc, mcNew ); + if( state.DISJOINTDVISITSTACKEESONTOP ) { + calleesToEnqueue.add( mdCallee ); + } else { + enqueue( mdCallee ); + } - ReachGraph onlyPossibleCallee = mapDescriptorToCompleteReachabilityGraph.get( mcNew ); + } - if( onlyPossibleCallee == null ) { - // if this method context has never been analyzed just schedule it for analysis - // and skip over this call site for now - if( !methodContextsToVisitSet.contains( mcNew ) ) { - methodContextsToVisitQ.add( new DescriptorQWrapper( mapDescriptorToPriority.get( md ), - mcNew ) ); - methodContextsToVisitSet.add( mcNew ); - } - - } else { - ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc, null); - } - - meAnalysis.createNewMapping(mcNew); - meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc); - + // the transformation for a call site should update the + // current heap abstraction with any effects from the callee, + // or if the method is virtual, the effects from any possible + // callees, so find the set of callees... + Set setPossibleCallees; + if( determinismDesired ) { + // use an ordered set + setPossibleCallees = new TreeSet( dComp ); + } else { + // otherwise use a speedy hashset + setPossibleCallees = new HashSet(); + } + if( mdCallee.isStatic() ) { + setPossibleCallees.add( mdCallee ); } else { - // if the method descriptor is virtual, then there could be a - // set of possible methods that will actually be invoked, so - // find all of them and merge all of their results together TypeDescriptor typeDesc = fc.getThis().getType(); - Set possibleCallees = callGraph.getMethods(md, typeDesc); - - Iterator i = possibleCallees.iterator(); - while( i.hasNext() ) { - MethodDescriptor possibleMd = (MethodDescriptor) i.next(); - FlatMethod pflatm = state.getMethodFlat(possibleMd); - - // don't alter the working graph (og) until we compute a result for every - // possible callee, merge them all together, then set og to that - ReachGraph ogCopy = new ReachGraph(); - ogCopy.merge(og); + setPossibleCallees.addAll( callGraph.getMethods( mdCallee, + typeDesc ) + ); + } - Set aliasedParamIndices = - ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm); + ReachGraph rgMergeOfPossibleCallers = new ReachGraph(); + + Iterator mdItr = setPossibleCallees.iterator(); + while( mdItr.hasNext() ) { + MethodDescriptor mdPossible = mdItr.next(); + FlatMethod fmPossible = state.getMethodFlat( mdPossible ); + + addDependent( mdPossible, // callee + d ); // caller + + // don't alter the working graph (rg) until we compute a + // result for every possible callee, merge them all together, + // then set rg to that + ReachGraph rgPossibleCaller = new ReachGraph(); + rgPossibleCaller.merge( rg ); + + ReachGraph rgPossibleCallee = getPartial( mdPossible ); + + if( rgPossibleCallee == null ) { + // if this method has never been analyzed just schedule it + // for analysis and skip over this call site for now + if( state.DISJOINTDVISITSTACKEESONTOP ) { + calleesToEnqueue.add( mdPossible ); + } else { + enqueue( mdPossible ); + } + + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " callee hasn't been analyzed, scheduling: "+mdPossible ); + } + + + } else { + // calculate the method call transform + rgPossibleCaller.resolveMethodCall( fc, + fmPossible, + rgPossibleCallee, + callerNodeIDsCopiedToCallee, + writeDebugDOTs + ); + + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + if( !rgPossibleCallee.isAccessible( ReachGraph.tdReturn ) ) { + rgPossibleCaller.makeInaccessible( fc.getReturnTemp() ); + } + } - Descriptor mcNew = new Descriptor( possibleMd, aliasedParamIndices ); - Set contexts = mapDescriptorToAllDescriptors.get( md ); - assert contexts != null; - contexts.add( mcNew ); - - - meAnalysis.createNewMapping(mcNew); - - - addDependent( mc, mcNew ); + } + + rgMergeOfPossibleCallers.merge( rgPossibleCaller ); + } - ReachGraph ogPotentialCallee = mapDescriptorToCompleteReachabilityGraph.get( mcNew ); - if( ogPotentialCallee == null ) { - // if this method context has never been analyzed just schedule it for analysis - // and skip over this call site for now - if( !methodContextsToVisitSet.contains( mcNew ) ) { - methodContextsToVisitQ.add( new DescriptorQWrapper( mapDescriptorToPriority.get( md ), - mcNew ) ); - methodContextsToVisitSet.add( mcNew ); - } - - } else { - ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc, null); - } - - ogMergeOfAllPossibleCalleeResults.merge(ogCopy); - - meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc); - } - + if( stopAfter ) { + System.out.println( "$$$ Exiting after requested captures of call site. $$$" ); + System.exit( 0 ); } - og = ogMergeOfAllPossibleCalleeResults; - */ + + // now that we've taken care of building heap models for + // callee analysis, finish this transformation + rg = rgMergeOfPossibleCallers; } break; case FKind.FlatReturnNode: FlatReturnNode frn = (FlatReturnNode) fn; rhs = frn.getReturnTemp(); - if( rhs != null && !rhs.getType().isImmutable() ) { + + // before transfer, do effects analysis support + if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { + if(!rg.isAccessible(rhs)){ + rg.makeInaccessible(ReachGraph.tdReturn); + } + } + + if( rhs != null && shouldAnalysisTrack( rhs.getType() ) ) { rg.assignReturnEqualToTemp( rhs ); } + setRetNodes.add( frn ); break; } // end switch + + + // dead variables were removed before the above transfer function + // was applied, so eliminate heap regions and edges that are no + // longer part of the abstractly-live heap graph, and sweep up + // and reachability effects that are altered by the reduction + //rg.abstractGarbageCollect(); + //rg.globalSweep(); + + + // back edges are strictly monotonic + if( pm.isBackEdge( fn ) ) { + ReachGraph rgPrevResult = mapBackEdgeToMonotone.get( fn ); + rg.merge( rgPrevResult ); + mapBackEdgeToMonotone.put( fn, rg ); + } // at this point rg should be the correct update // by an above transfer function, or untouched if // the flat node type doesn't affect the heap + return rg; } + // this method should generate integers strictly greater than zero! // special "shadow" regions are made from a heap region by negating @@ -714,292 +1651,144 @@ public class DisjointAnalysis { Descriptor d = (Descriptor) me.getKey(); ReachGraph rg = (ReachGraph) me.getValue(); - try { - rg.writeGraph( d+"COMPLETE", + rg.writeGraph( "COMPLETE"+d, + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // hide reachability altogether + true, // hide subset reachability states + true, // hide predicates + false ); // hide edge taints + } + } + + private void writeFinalIHMs() { + Iterator d2IHMsItr = mapDescriptorToIHMcontributions.entrySet().iterator(); + while( d2IHMsItr.hasNext() ) { + Map.Entry me1 = (Map.Entry) d2IHMsItr.next(); + Descriptor d = (Descriptor) me1.getKey(); + Hashtable IHMs = (Hashtable) me1.getValue(); + + Iterator fc2rgItr = IHMs.entrySet().iterator(); + while( fc2rgItr.hasNext() ) { + Map.Entry me2 = (Map.Entry) fc2rgItr.next(); + FlatCall fc = (FlatCall) me2.getKey(); + ReachGraph rg = (ReachGraph) me2.getValue(); + + rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc2enclosing.get( fc )+fc, true, // write labels (variables) true, // selectively hide intermediate temp vars + true, // hide reachability altogether true, // prune unreachable heap regions - false, // show back edges to confirm graph validity true, // hide subset reachability states + false, // hide predicates true ); // hide edge taints - } catch( IOException e ) {} - } - } - - - // return just the allocation site associated with one FlatNew node - protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) { - - if( !mapFlatNewToAllocSite.containsKey( fnew ) ) { - AllocSite as = - new AllocSite( allocationDepth, fnew, fnew.getDisjointId() ); - - // the newest nodes are single objects - for( int i = 0; i < allocationDepth; ++i ) { - Integer id = generateUniqueHeapRegionNodeID(); - as.setIthOldest( i, id ); - mapHrnIdToAllocSite.put( id, as ); } - - // the oldest node is a summary node - as.setSummary( generateUniqueHeapRegionNodeID() ); - - // and one special node is older than all - // nodes and shadow nodes for the site - as.setSiteSummary( generateUniqueHeapRegionNodeID() ); - - mapFlatNewToAllocSite.put( fnew, as ); } - - return mapFlatNewToAllocSite.get( fnew ); } + private void writeInitialContexts() { + Set entrySet = mapDescriptorToInitialContext.entrySet(); + Iterator itr = entrySet.iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + Descriptor d = (Descriptor) me.getKey(); + ReachGraph rg = (ReachGraph) me.getValue(); - /* - // return all allocation sites in the method (there is one allocation - // site per FlatNew node in a method) - protected HashSet getAllocSiteSet(Descriptor d) { - if( !mapDescriptorToAllocSiteSet.containsKey(d) ) { - buildAllocSiteSet(d); + rg.writeGraph( "INITIAL"+d, + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // hide all reachability + true, // hide subset reachability states + true, // hide predicates + false );// hide edge taints } - - return mapDescriptorToAllocSiteSet.get(d); - } - */ - - /* - protected void buildAllocSiteSet(Descriptor d) { - HashSet s = new HashSet(); - - FlatMethod fm = state.getMethodFlat( d ); - - // visit every node in this FlatMethod's IR graph - // and make a set of the allocation sites from the - // FlatNew node's visited - HashSet visited = new HashSet(); - HashSet toVisit = new HashSet(); - toVisit.add( fm ); - - while( !toVisit.isEmpty() ) { - FlatNode n = toVisit.iterator().next(); + - if( n instanceof FlatNew ) { - s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) ); - } + protected ReachGraph getPartial( Descriptor d ) { + return mapDescriptorToCompleteReachGraph.get( d ); + } - toVisit.remove( n ); - visited.add( n ); + protected void setPartial( Descriptor d, ReachGraph rg ) { + mapDescriptorToCompleteReachGraph.put( d, rg ); - for( int i = 0; i < n.numNext(); ++i ) { - FlatNode child = n.getNext( i ); - if( !visited.contains( child ) ) { - toVisit.add( child ); - } + // when the flag for writing out every partial + // result is set, we should spit out the graph, + // but in order to give it a unique name we need + // to track how many partial results for this + // descriptor we've already written out + if( writeAllIncrementalDOTs ) { + if( !mapDescriptorToNumUpdates.containsKey( d ) ) { + mapDescriptorToNumUpdates.put( d, new Integer( 0 ) ); } + Integer n = mapDescriptorToNumUpdates.get( d ); + + rg.writeGraph( d+"COMPLETE"+String.format( "%05d", n ), + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // hide all reachability + true, // hide subset reachability states + false, // hide predicates + false); // hide edge taints + + mapDescriptorToNumUpdates.put( d, n + 1 ); } - - mapDescriptorToAllocSiteSet.put( d, s ); } - */ - /* - protected HashSet getFlaggedAllocSites(Descriptor dIn) { - - HashSet out = new HashSet(); - HashSet toVisit = new HashSet(); - HashSet visited = new HashSet(); - - toVisit.add(dIn); - while( !toVisit.isEmpty() ) { - Descriptor d = toVisit.iterator().next(); - toVisit.remove(d); - visited.add(d); - HashSet asSet = getAllocSiteSet(d); - Iterator asItr = asSet.iterator(); - while( asItr.hasNext() ) { - AllocSite as = (AllocSite) asItr.next(); - if( as.getDisjointAnalysisId() != null ) { - out.add(as); - } - } - // enqueue callees of this method to be searched for - // allocation sites also - Set callees = callGraph.getCalleeSet(d); - if( callees != null ) { - Iterator methItr = callees.iterator(); - while( methItr.hasNext() ) { - MethodDescriptor md = (MethodDescriptor) methItr.next(); + // return just the allocation site associated with one FlatNew node + protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) { - if( !visited.contains(md) ) { - toVisit.add(md); - } - } - } + boolean flagProgrammatically = false; + if( sitesToFlag != null && sitesToFlag.contains( fnew ) ) { + flagProgrammatically = true; } - - return out; - } - */ - - /* - protected HashSet - getFlaggedAllocSitesReachableFromTaskPRIVATE(TaskDescriptor td) { - - HashSet asSetTotal = new HashSet(); - HashSet toVisit = new HashSet(); - HashSet visited = new HashSet(); - toVisit.add(td); - - // traverse this task and all methods reachable from this task - while( !toVisit.isEmpty() ) { - Descriptor d = toVisit.iterator().next(); - toVisit.remove(d); - visited.add(d); + if( !mapFlatNewToAllocSite.containsKey( fnew ) ) { + AllocSite as = AllocSite.factory( allocationDepth, + fnew, + fnew.getDisjointId(), + flagProgrammatically + ); - HashSet asSet = getAllocSiteSet(d); - Iterator asItr = asSet.iterator(); - while( asItr.hasNext() ) { - AllocSite as = (AllocSite) asItr.next(); - TypeDescriptor typed = as.getType(); - if( typed != null ) { - ClassDescriptor cd = typed.getClassDesc(); - if( cd != null && cd.hasFlags() ) { - asSetTotal.add(as); - } - } + // the newest nodes are single objects + for( int i = 0; i < allocationDepth; ++i ) { + Integer id = generateUniqueHeapRegionNodeID(); + as.setIthOldest( i, id ); + mapHrnIdToAllocSite.put( id, as ); } - // enqueue callees of this method to be searched for - // allocation sites also - Set callees = callGraph.getCalleeSet(d); - if( callees != null ) { - Iterator methItr = callees.iterator(); - while( methItr.hasNext() ) { - MethodDescriptor md = (MethodDescriptor) methItr.next(); + // the oldest node is a summary node + as.setSummary( generateUniqueHeapRegionNodeID() ); - if( !visited.contains(md) ) { - toVisit.add(md); - } - } - } + mapFlatNewToAllocSite.put( fnew, as ); } - - return asSetTotal; + return mapFlatNewToAllocSite.get( fnew ); } - */ - - - /* - protected String computeAliasContextHistogram() { - - Hashtable mapNumContexts2NumDesc = - new Hashtable(); - - Iterator itr = mapDescriptorToAllDescriptors.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - HashSet s = (HashSet) me.getValue(); - - Integer i = mapNumContexts2NumDesc.get( s.size() ); - if( i == null ) { - i = new Integer( 0 ); - } - mapNumContexts2NumDesc.put( s.size(), i + 1 ); - } - String s = ""; - int total = 0; - itr = mapNumContexts2NumDesc.entrySet().iterator(); - while( itr.hasNext() ) { - Map.Entry me = (Map.Entry) itr.next(); - Integer c0 = (Integer) me.getKey(); - Integer d0 = (Integer) me.getValue(); - total += d0; - s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 ); + public static boolean shouldAnalysisTrack( TypeDescriptor type ) { + // don't track primitive types, but an array + // of primitives is heap memory + if( type.isImmutable() ) { + return type.isArray(); } - s += String.format( "\n%4d total methods analayzed.\n", total ); - - return s; + // everything else is an object + return true; } protected int numMethodsAnalyzed() { return descriptorsToAnalyze.size(); } - */ - - - /* - // insert a call to debugSnapshot() somewhere in the analysis - // to get successive captures of the analysis state - boolean takeDebugSnapshots = false; - String mcDescSymbolDebug = "setRoute"; - boolean stopAfterCapture = true; - - // increments every visit to debugSnapshot, don't fiddle with it - // IMPORTANT NOTE FOR SETTING THE FOLLOWING VALUES: this - // counter increments just after every node is analyzed - // from the body of the method whose symbol is specified - // above. - int debugCounter = 0; - - // the value of debugCounter to start reporting the debugCounter - // to the screen to let user know what debug iteration we're at - int numStartCountReport = 0; - - // the frequency of debugCounter values to print out, 0 no report - int freqCountReport = 0; - - // the debugCounter value at which to start taking snapshots - int iterStartCapture = 0; - - // the number of snapshots to take - int numIterToCapture = 300; - - void debugSnapshot(ReachabilityGraph og, FlatNode fn) { - if( debugCounter > iterStartCapture + numIterToCapture ) { - return; - } - - ++debugCounter; - if( debugCounter > numStartCountReport && - freqCountReport > 0 && - debugCounter % freqCountReport == 0 ) { - System.out.println(" @@@ debug counter = "+debugCounter); - } - if( debugCounter > iterStartCapture ) { - System.out.println(" @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@"); - String graphName = String.format("snap%04d",debugCounter-iterStartCapture); - if( fn != null ) { - graphName = graphName+fn; - } - try { - og.writeGraph(graphName, - true, // write labels (variables) - true, // selectively hide intermediate temp vars - true, // prune unreachable heap regions - false, // show back edges to confirm graph validity - false, // show parameter indices (unmaintained!) - true, // hide subset reachability states - true); // hide edge taints - } catch( Exception e ) { - System.out.println("Error writing debug capture."); - System.exit(0); - } - } + - if( debugCounter == iterStartCapture + numIterToCapture && stopAfterCapture ) { - System.out.println("Stopping analysis after debug captures."); - System.exit(0); - } - } - */ + // Take in source entry which is the program's compiled entry and @@ -1061,8 +1850,17 @@ public class DisjointAnalysis { protected LinkedList topologicalSort( Set toSort ) { - Set discovered = new HashSet (); - LinkedList sorted = new LinkedList(); + Set discovered; + + if( determinismDesired ) { + // use an ordered set + discovered = new TreeSet( dComp ); + } else { + // otherwise use a speedy hashset + discovered = new HashSet(); + } + + LinkedList sorted = new LinkedList(); Iterator itr = toSort.iterator(); while( itr.hasNext() ) { @@ -1125,40 +1923,28 @@ public class DisjointAnalysis { } } - sorted.addFirst( d ); + // for leaf-nodes last now! + sorted.addLast( d ); } - protected ReachGraph getPartial( Descriptor d ) { - return mapDescriptorToCompleteReachGraph.get( d ); - } + protected void enqueue( Descriptor d ) { - protected void setPartial( Descriptor d, ReachGraph rg ) { - mapDescriptorToCompleteReachGraph.put( d, rg ); + if( !descriptorsToVisitSet.contains( d ) ) { - // when the flag for writing out every partial - // result is set, we should spit out the graph, - // but in order to give it a unique name we need - // to track how many partial results for this - // descriptor we've already written out - if( writeAllIncrementalDOTs ) { - if( !mapDescriptorToNumUpdates.containsKey( d ) ) { - mapDescriptorToNumUpdates.put( d, new Integer( 0 ) ); + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { + descriptorsToVisitStack.add( d ); + + } else if( state.DISJOINTDVISITPQUE ) { + Integer priority = mapDescriptorToPriority.get( d ); + descriptorsToVisitQ.add( new DescriptorQWrapper( priority, + d ) + ); } - Integer n = mapDescriptorToNumUpdates.get( d ); - /* - try { - rg.writeGraph( d+"COMPLETE"+String.format( "%05d", n ), - true, // write labels (variables) - true, // selectively hide intermediate temp vars - true, // prune unreachable heap regions - false, // show back edges to confirm graph validity - false, // show parameter indices (unmaintained!) - true, // hide subset reachability states - true); // hide edge taints - } catch( IOException e ) {} - */ - mapDescriptorToNumUpdates.put( d, n + 1 ); + + descriptorsToVisitSet.add( d ); } } @@ -1192,6 +1978,7 @@ public class DisjointAnalysis { if( heapsFromCallers == null ) { heapsFromCallers = new Hashtable(); + mapDescriptorToIHMcontributions.put( d, heapsFromCallers ); } return heapsFromCallers; @@ -1204,12 +1991,13 @@ public class DisjointAnalysis { getIHMcontributions( d ); if( !heapsFromCallers.containsKey( fc ) ) { - heapsFromCallers.put( fc, new ReachGraph() ); + return null; } return heapsFromCallers.get( fc ); } + public void addIHMcontribution( Descriptor d, FlatCall fc, ReachGraph rg @@ -1220,4 +2008,539 @@ public class DisjointAnalysis { heapsFromCallers.put( fc, rg ); } + + private AllocSite createParameterAllocSite( ReachGraph rg, + TempDescriptor tempDesc, + boolean flagRegions + ) { + + FlatNew flatNew; + if( flagRegions ) { + flatNew = new FlatNew( tempDesc.getType(), // type + tempDesc, // param temp + false, // global alloc? + "param"+tempDesc // disjoint site ID string + ); + } else { + flatNew = new FlatNew( tempDesc.getType(), // type + tempDesc, // param temp + false, // global alloc? + null // disjoint site ID string + ); + } + + // create allocation site + AllocSite as = AllocSite.factory( allocationDepth, + flatNew, + flatNew.getDisjointId(), + false + ); + for (int i = 0; i < allocationDepth; ++i) { + Integer id = generateUniqueHeapRegionNodeID(); + as.setIthOldest(i, id); + mapHrnIdToAllocSite.put(id, as); + } + // the oldest node is a summary node + as.setSummary( generateUniqueHeapRegionNodeID() ); + + rg.age(as); + + return as; + + } + +private Set getFieldSetTobeAnalyzed(TypeDescriptor typeDesc){ + + Set fieldSet=new HashSet(); + if(!typeDesc.isImmutable()){ + ClassDescriptor classDesc = typeDesc.getClassDesc(); + for (Iterator it = classDesc.getFields(); it.hasNext();) { + FieldDescriptor field = (FieldDescriptor) it.next(); + TypeDescriptor fieldType = field.getType(); + if (shouldAnalysisTrack( fieldType )) { + fieldSet.add(field); + } + } + } + return fieldSet; + +} + + private HeapRegionNode createMultiDeimensionalArrayHRN(ReachGraph rg, AllocSite alloc, HeapRegionNode srcHRN, FieldDescriptor fd, Hashtable map, Hashtable mapToExistingNode, ReachSet alpha ){ + + int dimCount=fd.getType().getArrayCount(); + HeapRegionNode prevNode=null; + HeapRegionNode arrayEntryNode=null; + for(int i=dimCount;i>0;i--){ + TypeDescriptor typeDesc=fd.getType().dereference();//hack to get instance of type desc + typeDesc.setArrayCount(i); + TempDescriptor tempDesc=new TempDescriptor(typeDesc.getSymbol(),typeDesc); + HeapRegionNode hrnSummary ; + if(!mapToExistingNode.containsKey(typeDesc)){ + AllocSite as; + if(i==dimCount){ + as = alloc; + }else{ + as = createParameterAllocSite(rg, tempDesc, false); + } + // make a new reference to allocated node + hrnSummary = + rg.createNewHeapRegionNode(as.getSummary(), // id or null to generate a new one + false, // single object? + true, // summary? + false, // out-of-context? + as.getType(), // type + as, // allocation site + alpha, // inherent reach + alpha, // current reach + ExistPredSet.factory(rg.predTrue), // predicates + tempDesc.toString() // description + ); + rg.id2hrn.put(as.getSummary(),hrnSummary); + + mapToExistingNode.put(typeDesc, hrnSummary); + }else{ + hrnSummary=mapToExistingNode.get(typeDesc); + } + + if(prevNode==null){ + // make a new reference between new summary node and source + RefEdge edgeToSummary = new RefEdge(srcHRN, // source + hrnSummary, // dest + typeDesc, // type + fd.getSymbol(), // field name + alpha, // beta + ExistPredSet.factory(rg.predTrue), // predicates + null + ); + + rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary); + prevNode=hrnSummary; + arrayEntryNode=hrnSummary; + }else{ + // make a new reference between summary nodes of array + RefEdge edgeToSummary = new RefEdge(prevNode, // source + hrnSummary, // dest + typeDesc, // type + arrayElementFieldName, // field name + alpha, // beta + ExistPredSet.factory(rg.predTrue), // predicates + null + ); + + rg.addRefEdge(prevNode, hrnSummary, edgeToSummary); + prevNode=hrnSummary; + } + + } + + // create a new obj node if obj has at least one non-primitive field + TypeDescriptor type=fd.getType(); + if(getFieldSetTobeAnalyzed(type).size()>0){ + TypeDescriptor typeDesc=type.dereference(); + typeDesc.setArrayCount(0); + if(!mapToExistingNode.containsKey(typeDesc)){ + TempDescriptor tempDesc=new TempDescriptor(type.getSymbol(),typeDesc); + AllocSite as = createParameterAllocSite(rg, tempDesc, false); + // make a new reference to allocated node + HeapRegionNode hrnSummary = + rg.createNewHeapRegionNode(as.getSummary(), // id or null to generate a new one + false, // single object? + true, // summary? + false, // out-of-context? + typeDesc, // type + as, // allocation site + alpha, // inherent reach + alpha, // current reach + ExistPredSet.factory(rg.predTrue), // predicates + tempDesc.toString() // description + ); + rg.id2hrn.put(as.getSummary(),hrnSummary); + mapToExistingNode.put(typeDesc, hrnSummary); + RefEdge edgeToSummary = new RefEdge(prevNode, // source + hrnSummary, // dest + typeDesc, // type + arrayElementFieldName, // field name + alpha, // beta + ExistPredSet.factory(rg.predTrue), // predicates + null + ); + rg.addRefEdge(prevNode, hrnSummary, edgeToSummary); + prevNode=hrnSummary; + }else{ + HeapRegionNode hrnSummary=mapToExistingNode.get(typeDesc); + if(prevNode.getReferenceTo(hrnSummary, typeDesc, arrayElementFieldName)==null){ + RefEdge edgeToSummary = new RefEdge(prevNode, // source + hrnSummary, // dest + typeDesc, // type + arrayElementFieldName, // field name + alpha, // beta + ExistPredSet.factory(rg.predTrue), // predicates + null + ); + rg.addRefEdge(prevNode, hrnSummary, edgeToSummary); + } + prevNode=hrnSummary; + } + } + + map.put(arrayEntryNode, prevNode); + return arrayEntryNode; +} + +private ReachGraph createInitialTaskReachGraph(FlatMethod fm) { + ReachGraph rg = new ReachGraph(); + TaskDescriptor taskDesc = fm.getTask(); + + for (int idx = 0; idx < taskDesc.numParameters(); idx++) { + Descriptor paramDesc = taskDesc.getParameter(idx); + TypeDescriptor paramTypeDesc = taskDesc.getParamType(idx); + + // setup data structure + Set> workSet = + new HashSet>(); + Hashtable mapTypeToExistingSummaryNode = + new Hashtable(); + Hashtable mapToFirstDimensionArrayNode = + new Hashtable(); + Set doneSet = new HashSet(); + + TempDescriptor tempDesc = fm.getParameter(idx); + + AllocSite as = createParameterAllocSite(rg, tempDesc, true); + VariableNode lnX = rg.getVariableNodeFromTemp(tempDesc); + Integer idNewest = as.getIthOldest(0); + HeapRegionNode hrnNewest = rg.id2hrn.get(idNewest); + + // make a new reference to allocated node + RefEdge edgeNew = new RefEdge(lnX, // source + hrnNewest, // dest + taskDesc.getParamType(idx), // type + null, // field name + hrnNewest.getAlpha(), // beta + ExistPredSet.factory(rg.predTrue), // predicates + null + ); + rg.addRefEdge(lnX, hrnNewest, edgeNew); + + // set-up a work set for class field + ClassDescriptor classDesc = paramTypeDesc.getClassDesc(); + for (Iterator it = classDesc.getFields(); it.hasNext();) { + FieldDescriptor fd = (FieldDescriptor) it.next(); + TypeDescriptor fieldType = fd.getType(); + if (shouldAnalysisTrack( fieldType )) { + HashMap newMap = new HashMap(); + newMap.put(hrnNewest, fd); + workSet.add(newMap); + } + } + + int uniqueIdentifier = 0; + while (!workSet.isEmpty()) { + HashMap map = workSet + .iterator().next(); + workSet.remove(map); + + Set key = map.keySet(); + HeapRegionNode srcHRN = key.iterator().next(); + FieldDescriptor fd = map.get(srcHRN); + TypeDescriptor type = fd.getType(); + String doneSetIdentifier = srcHRN.getIDString() + "_" + fd; + + if (!doneSet.contains(doneSetIdentifier)) { + doneSet.add(doneSetIdentifier); + if (!mapTypeToExistingSummaryNode.containsKey(type)) { + // create new summary Node + TempDescriptor td = new TempDescriptor("temp" + + uniqueIdentifier, type); + + AllocSite allocSite; + if(type.equals(paramTypeDesc)){ + //corresponding allocsite has already been created for a parameter variable. + allocSite=as; + }else{ + allocSite = createParameterAllocSite(rg, td, false); + } + String strDesc = allocSite.toStringForDOT() + + "\\nsummary"; + TypeDescriptor allocType=allocSite.getType(); + + HeapRegionNode hrnSummary; + if(allocType.isArray() && allocType.getArrayCount()>0){ + hrnSummary=createMultiDeimensionalArrayHRN(rg,allocSite,srcHRN,fd,mapToFirstDimensionArrayNode,mapTypeToExistingSummaryNode,hrnNewest.getAlpha()); + }else{ + hrnSummary = + rg.createNewHeapRegionNode(allocSite.getSummary(), // id or null to generate a new one + false, // single object? + true, // summary? + false, // out-of-context? + allocSite.getType(), // type + allocSite, // allocation site + hrnNewest.getAlpha(), // inherent reach + hrnNewest.getAlpha(), // current reach + ExistPredSet.factory(rg.predTrue), // predicates + strDesc // description + ); + rg.id2hrn.put(allocSite.getSummary(),hrnSummary); + + // make a new reference to summary node + RefEdge edgeToSummary = new RefEdge(srcHRN, // source + hrnSummary, // dest + type, // type + fd.getSymbol(), // field name + hrnNewest.getAlpha(), // beta + ExistPredSet.factory(rg.predTrue), // predicates + null + ); + + rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary); + } + uniqueIdentifier++; + + mapTypeToExistingSummaryNode.put(type, hrnSummary); + + // set-up a work set for fields of the class + Set fieldTobeAnalyzed=getFieldSetTobeAnalyzed(type); + for (Iterator iterator = fieldTobeAnalyzed.iterator(); iterator + .hasNext();) { + FieldDescriptor fieldDescriptor = (FieldDescriptor) iterator + .next(); + HeapRegionNode newDstHRN; + if(mapToFirstDimensionArrayNode.containsKey(hrnSummary)){ + //related heap region node is already exsited. + newDstHRN=mapToFirstDimensionArrayNode.get(hrnSummary); + }else{ + newDstHRN=hrnSummary; + } + doneSetIdentifier = newDstHRN.getIDString() + "_" + fieldDescriptor; + if(!doneSet.contains(doneSetIdentifier)){ + // add new work item + HashMap newMap = + new HashMap(); + newMap.put(newDstHRN, fieldDescriptor); + workSet.add(newMap); + } + } + + }else{ + // if there exists corresponding summary node + HeapRegionNode hrnDst=mapTypeToExistingSummaryNode.get(type); + + RefEdge edgeToSummary = new RefEdge(srcHRN, // source + hrnDst, // dest + fd.getType(), // type + fd.getSymbol(), // field name + srcHRN.getAlpha(), // beta + ExistPredSet.factory(rg.predTrue), // predicates + null + ); + rg.addRefEdge(srcHRN, hrnDst, edgeToSummary); + + } + } + } + } +// debugSnapshot(rg, fm, true); + return rg; +} + +// return all allocation sites in the method (there is one allocation +// site per FlatNew node in a method) +private HashSet getAllocationSiteSet(Descriptor d) { + if( !mapDescriptorToAllocSiteSet.containsKey(d) ) { + buildAllocationSiteSet(d); + } + + return mapDescriptorToAllocSiteSet.get(d); + +} + +private void buildAllocationSiteSet(Descriptor d) { + HashSet s = new HashSet(); + + FlatMethod fm; + if( d instanceof MethodDescriptor ) { + fm = state.getMethodFlat( (MethodDescriptor) d); + } else { + assert d instanceof TaskDescriptor; + fm = state.getMethodFlat( (TaskDescriptor) d); + } + pm.analyzeMethod(fm); + + // visit every node in this FlatMethod's IR graph + // and make a set of the allocation sites from the + // FlatNew node's visited + HashSet visited = new HashSet(); + HashSet toVisit = new HashSet(); + toVisit.add(fm); + + while( !toVisit.isEmpty() ) { + FlatNode n = toVisit.iterator().next(); + + if( n instanceof FlatNew ) { + s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) ); + } + + toVisit.remove(n); + visited.add(n); + + for( int i = 0; i < pm.numNext(n); ++i ) { + FlatNode child = pm.getNext(n, i); + if( !visited.contains(child) ) { + toVisit.add(child); + } + } + } + + mapDescriptorToAllocSiteSet.put(d, s); + } + + private HashSet getFlaggedAllocationSites(Descriptor dIn) { + + HashSet out = new HashSet(); + HashSet toVisit = new HashSet(); + HashSet visited = new HashSet(); + + toVisit.add(dIn); + + while (!toVisit.isEmpty()) { + Descriptor d = toVisit.iterator().next(); + toVisit.remove(d); + visited.add(d); + + HashSet asSet = getAllocationSiteSet(d); + Iterator asItr = asSet.iterator(); + while (asItr.hasNext()) { + AllocSite as = (AllocSite) asItr.next(); + if (as.getDisjointAnalysisId() != null) { + out.add(as); + } + } + + // enqueue callees of this method to be searched for + // allocation sites also + Set callees = callGraph.getCalleeSet(d); + if (callees != null) { + Iterator methItr = callees.iterator(); + while (methItr.hasNext()) { + MethodDescriptor md = (MethodDescriptor) methItr.next(); + + if (!visited.contains(md)) { + toVisit.add(md); + } + } + } + } + + return out; + } + + +private HashSet +getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { + + HashSet asSetTotal = new HashSet(); + HashSet toVisit = new HashSet(); + HashSet visited = new HashSet(); + + toVisit.add(td); + + // traverse this task and all methods reachable from this task + while( !toVisit.isEmpty() ) { + Descriptor d = toVisit.iterator().next(); + toVisit.remove(d); + visited.add(d); + + HashSet asSet = getAllocationSiteSet(d); + Iterator asItr = asSet.iterator(); + while( asItr.hasNext() ) { + AllocSite as = (AllocSite) asItr.next(); + TypeDescriptor typed = as.getType(); + if( typed != null ) { + ClassDescriptor cd = typed.getClassDesc(); + if( cd != null && cd.hasFlags() ) { + asSetTotal.add(as); + } + } + } + + // enqueue callees of this method to be searched for + // allocation sites also + Set callees = callGraph.getCalleeSet(d); + if( callees != null ) { + Iterator methItr = callees.iterator(); + while( methItr.hasNext() ) { + MethodDescriptor md = (MethodDescriptor) methItr.next(); + + if( !visited.contains(md) ) { + toVisit.add(md); + } + } + } + } + + return asSetTotal; +} + + public Set getDescriptorsToAnalyze() { + return descriptorsToAnalyze; + } + + public EffectsAnalysis getEffectsAnalysis(){ + return effectsAnalysis; + } + + public ReachGraph getReachGraph(Descriptor d){ + return mapDescriptorToCompleteReachGraph.get(d); + } + + + // get successive captures of the analysis state, use compiler + // flags to control + boolean takeDebugSnapshots = false; + String descSymbolDebug = null; + boolean stopAfterCapture = false; + int snapVisitCounter = 0; + int snapNodeCounter = 0; + int visitStartCapture = 0; + int numVisitsToCapture = 0; + + + void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) { + if( snapVisitCounter > visitStartCapture + numVisitsToCapture ) { + return; + } + + if( in ) { + + } + + if( snapVisitCounter >= visitStartCapture ) { + System.out.println( " @@@ snapping visit="+snapVisitCounter+ + ", node="+snapNodeCounter+ + " @@@" ); + String graphName; + if( in ) { + graphName = String.format( "snap%03d_%04din", + snapVisitCounter, + snapNodeCounter ); + } else { + graphName = String.format( "snap%03d_%04dout", + snapVisitCounter, + snapNodeCounter ); + } + if( fn != null ) { + graphName = graphName + fn; + } + rg.writeGraph( graphName, + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // hide reachability + true, // hide subset reachability states + true, // hide predicates + false );// hide edge taints + } + } + }