X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FDisjoint%2FDisjointAnalysis.java;h=129bffd2ddafff07ed8f643d16c9c1ecb83dde25;hb=8c85b514ccea2de665db0d83f44004bc8e422f25;hp=688d342a40acdb65dcae0e0013298cb7b5e92d5c;hpb=895be5373dacd04e839184eb308d7301d8e72789;p=IRC.git diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 688d342a..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,13 +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(); @@ -138,20 +562,48 @@ 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(); } @@ -162,65 +614,165 @@ public class DisjointAnalysis { TypeUtil tu, CallGraph cg, Liveness l, - ArrayReferencees ar - ) throws java.io.IOException { - init( s, tu, cg, l, ar ); + 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 { + 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.DISJOINTWRITEIHMS ) { - writeFinalIHMs(); - } + try { + if( writeFinalDOTs && !writeAllIncrementalDOTs ) { + writeFinalGraphs(); + } - if( state.DISJOINTALIASFILE != null ) { - if( state.TASK ) { - // not supporting tasks yet... - } else { - /* - writeAllAliasesJava( aliasFile, - treport, - justtime, - state.DISJOINTALIASTAB, - state.lines ); - */ + 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" ); } @@ -228,32 +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( "Bamboo..." ); - Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + System.out.println( "Bamboo mode..." ); - while (taskItr.hasNext()) { - TaskDescriptor td = (TaskDescriptor) taskItr.next(); - if (!descriptorsToAnalyze.contains(td)) { - descriptorsToAnalyze.add(td); - descriptorsToAnalyze.addAll(callGraph.getAllMethods(td)); - } + 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 @@ -261,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 ); @@ -295,11 +890,19 @@ 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 enqueue dependents // of d for further analysis @@ -307,9 +910,28 @@ public class DisjointAnalysis { while( depsItr.hasNext() ) { Descriptor dNext = depsItr.next(); enqueue( 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 ) @@ -322,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 = @@ -336,46 +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(); - - if(fn instanceof FlatMethod && ((FlatMethod)fn).getTask()!=null){ - // create initial reach graph for a task - rg=createInitialTaskReachGraph((FlatMethod)fn); + 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 ) + d.getSymbol().equals( descSymbolDebug ) ) { - debugSnapshot( rg, fn, true ); + debugSnapshot( rg, fn, true ); } + // modify rg with appropriate transfer function rg = analyzeFlatNode( d, fm, fn, setReturns, rg ); - + + if( takeDebugSnapshots && - d.getSymbol().equals( descSymbolDebug ) + d.getSymbol().equals( descSymbolDebug ) ) { - debugSnapshot( rg, fn, false ); + debugSnapshot( rg, fn, false ); + ++snapNodeCounter; } - + // if the results of the new graph are different from // the current graph at this node, replace the graph @@ -384,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(); @@ -406,7 +1058,26 @@ 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; } @@ -424,10 +1095,13 @@ public class DisjointAnalysis { // nullified in the graph to reduce edges //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 @@ -450,14 +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( 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 ); - rg.merge_diffMethodContext( rgContrib ); - } } break; case FKind.FlatOpNode: @@ -465,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; @@ -476,93 +1165,285 @@ 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 ); + + 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(); + + 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 ); + } + } - 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: { - //TODO: temporal fix for task descriptor case - //MethodDescriptor mdCaller = fmContaining.getMethod(); Descriptor mdCaller; - if(fmContaining.getMethod()!=null){ - mdCaller = fmContaining.getMethod(); - }else{ - mdCaller = fmContaining.getTask(); + 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 writeDebugDOTs = + + boolean debugCallSite = mdCaller.getSymbol().equals( state.DISJOINTDEBUGCALLER ) && - mdCallee.getSymbol().equals( state.DISJOINTDEBUGCALLEE ); + 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 @@ -589,18 +1470,35 @@ public class DisjointAnalysis { // if heap at call site changed, update the contribution, // and reschedule the callee for analysis addIHMcontribution( mdCallee, fc, heapForThisCall_cur ); - enqueue( mdCallee ); - } + // map a FlatCall to its enclosing method/task descriptor + // so we can write that info out later + fc2enclosing.put( fc, mdCaller ); + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " context changed, scheduling callee: "+mdCallee ); + } + if( state.DISJOINTDVISITSTACKEESONTOP ) { + calleesToEnqueue.add( mdCallee ); + } else { + enqueue( mdCallee ); + } + + } // 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 = - new HashSet(); + 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 ); @@ -611,7 +1509,7 @@ public class DisjointAnalysis { ); } - ReachGraph rgMergeOfEffects = new ReachGraph(); + ReachGraph rgMergeOfPossibleCallers = new ReachGraph(); Iterator mdItr = setPossibleCallees.iterator(); while( mdItr.hasNext() ) { @@ -624,40 +1522,73 @@ public class DisjointAnalysis { // 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 rgCopy = new ReachGraph(); - rgCopy.merge( rg ); + ReachGraph rgPossibleCaller = new ReachGraph(); + rgPossibleCaller.merge( rg ); - ReachGraph rgEffect = getPartial( mdPossible ); + ReachGraph rgPossibleCallee = getPartial( mdPossible ); - if( rgEffect == null ) { + if( rgPossibleCallee == null ) { // if this method has never been analyzed just schedule it // for analysis and skip over this call site for now - enqueue( mdPossible ); + if( state.DISJOINTDVISITSTACKEESONTOP ) { + calleesToEnqueue.add( mdPossible ); + } else { + enqueue( mdPossible ); + } + + if( state.DISJOINTDEBUGSCHEDULING ) { + System.out.println( " callee hasn't been analyzed, scheduling: "+mdPossible ); + } + + } else { - rgCopy.resolveMethodCall( fc, - fmPossible, - rgEffect, - callerNodeIDsCopiedToCallee, - writeDebugDOTs - ); + // 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() ); + } + } + } - rgMergeOfEffects.merge( rgCopy ); + rgMergeOfPossibleCallers.merge( rgPossibleCaller ); + } + + + if( stopAfter ) { + System.out.println( "$$$ Exiting after requested captures of call site. $$$" ); + System.exit( 0 ); } // now that we've taken care of building heap models for // callee analysis, finish this transformation - rg = rgMergeOfEffects; + 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; @@ -672,12 +1603,20 @@ public class DisjointAnalysis { //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 @@ -712,15 +1651,14 @@ public class DisjointAnalysis { Descriptor d = (Descriptor) me.getKey(); ReachGraph rg = (ReachGraph) me.getValue(); - try { - rg.writeGraph( "COMPLETE"+d, - true, // write labels (variables) - true, // selectively hide intermediate temp vars - true, // prune unreachable heap regions - false, // show back edges to confirm graph validity - true, // hide subset reachability states - true ); // hide edge taints - } catch( IOException e ) {} + 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 } } @@ -737,32 +1675,85 @@ public class DisjointAnalysis { FlatCall fc = (FlatCall) me2.getKey(); ReachGraph rg = (ReachGraph) me2.getValue(); - try { - rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc, - true, // write labels (variables) - false, // selectively hide intermediate temp vars - false, // prune unreachable heap regions - false, // show back edges to confirm graph validity - true, // hide subset reachability states - true ); // hide edge taints - } catch( IOException e ) {} + 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 + true, // hide subset reachability states + false, // hide predicates + true ); // hide edge taints + } + } + } + + 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(); + + 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 + } + } + + + protected ReachGraph getPartial( Descriptor d ) { + return mapDescriptorToCompleteReachGraph.get( d ); + } + + protected void setPartial( Descriptor d, ReachGraph rg ) { + mapDescriptorToCompleteReachGraph.put( d, rg ); + + // 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 ); } } - // return just the allocation site associated with one FlatNew node protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) { + boolean flagProgrammatically = false; + if( sitesToFlag != null && sitesToFlag.contains( fnew ) ) { + flagProgrammatically = true; + } + if( !mapFlatNewToAllocSite.containsKey( fnew ) ) { - AllocSite as = - (AllocSite) Canonical.makeCanonical( new AllocSite( allocationDepth, - fnew, - fnew.getDisjointId() - ) - ); + AllocSite as = AllocSite.factory( allocationDepth, + fnew, + fnew.getDisjointId(), + flagProgrammatically + ); // the newest nodes are single objects for( int i = 0; i < allocationDepth; ++i ) { @@ -781,184 +1772,21 @@ public class DisjointAnalysis { } - /* - // 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); - } - - 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) ); - } - - toVisit.remove( n ); - visited.add( n ); - - for( int i = 0; i < n.numNext(); ++i ) { - FlatNode child = n.getNext( i ); - if( !visited.contains( child ) ) { - toVisit.add( child ); - } - } - } - - 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(); - - if( !visited.contains(md) ) { - toVisit.add(md); - } - } - } - } - - 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); - - 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); - } - } - } - - // 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; - } - */ - - - /* - 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(); } - */ + @@ -1022,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() ) { @@ -1086,51 +1923,28 @@ public class DisjointAnalysis { } } - sorted.addFirst( d ); + // for leaf-nodes last now! + sorted.addLast( d ); } protected void enqueue( Descriptor d ) { - if( !descriptorsToVisitSet.contains( d ) ) { - Integer priority = mapDescriptorToPriority.get( d ); - descriptorsToVisitQ.add( new DescriptorQWrapper( priority, - d ) - ); - descriptorsToVisitSet.add( d ); - } - } - - protected ReachGraph getPartial( Descriptor d ) { - return mapDescriptorToCompleteReachGraph.get( d ); - } + if( !descriptorsToVisitSet.contains( d ) ) { - protected void setPartial( Descriptor d, ReachGraph rg ) { - mapDescriptorToCompleteReachGraph.put( d, rg ); + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { + descriptorsToVisitStack.add( 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 ) ); + } 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 ); } } @@ -1177,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 @@ -1193,12 +2008,33 @@ public class DisjointAnalysis { heapsFromCallers.put( fc, rg ); } -private AllocSite createParameterAllocSite(ReachGraph rg, TempDescriptor tempDesc) { + + private AllocSite createParameterAllocSite( ReachGraph rg, + TempDescriptor tempDesc, + boolean flagRegions + ) { - // create temp descriptor for each parameter variable - FlatNew flatNew = new FlatNew(tempDesc.getType(), tempDesc, false); + 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) Canonical.makeCanonical(new AllocSite( allocationDepth, flatNew, flatNew.getDisjointId())); + AllocSite as = AllocSite.factory( allocationDepth, + flatNew, + flatNew.getDisjointId(), + false + ); for (int i = 0; i < allocationDepth; ++i) { Integer id = generateUniqueHeapRegionNodeID(); as.setIthOldest(i, id); @@ -1211,8 +2047,147 @@ private AllocSite createParameterAllocSite(ReachGraph rg, TempDescriptor tempDes 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(); @@ -1226,32 +2201,34 @@ private ReachGraph createInitialTaskReachGraph(FlatMethod fm) { new HashSet>(); Hashtable mapTypeToExistingSummaryNode = new Hashtable(); + Hashtable mapToFirstDimensionArrayNode = + new Hashtable(); Set doneSet = new HashSet(); - TempDescriptor tempDesc = new TempDescriptor(paramDesc.getSymbol(), - paramTypeDesc); + TempDescriptor tempDesc = fm.getParameter(idx); - AllocSite as = createParameterAllocSite(rg, tempDesc); + 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 + 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 (!fieldType.isImmutable() || fieldType.isArray()) { + if (shouldAnalysisTrack( fieldType )) { HashMap newMap = new HashMap(); newMap.put(hrnNewest, fd); workSet.add(newMap); @@ -1282,57 +2259,68 @@ private ReachGraph createInitialTaskReachGraph(FlatMethod fm) { //corresponding allocsite has already been created for a parameter variable. allocSite=as; }else{ - allocSite = createParameterAllocSite(rg, td); + allocSite = createParameterAllocSite(rg, td, false); } String strDesc = allocSite.toStringForDOT() + "\\nsummary"; - HeapRegionNode hrnSummary = - rg.createNewHeapRegionNode(allocSite.getSummary(), // id or null to generate a new one - false, // single object? - true, // summary? - false, // flagged? - false, // out-of-context? - allocSite.getType(), // type - allocSite, // allocation site - null, // inherent reach - srcHRN.getAlpha(), // current reach - ExistPredSet.factory(), // predicates - strDesc // description - ); + 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 - fd.getType(), // type + type, // type fd.getSymbol(), // field name - srcHRN.getAlpha(), // beta - ExistPredSet.factory(rg.predTrue) // predicates + 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 - if(!type.isImmutable()){ - classDesc = type.getClassDesc(); - for (Iterator it = classDesc.getFields(); it.hasNext();) { - FieldDescriptor typeFieldDesc = (FieldDescriptor) it.next(); - TypeDescriptor fieldType = typeFieldDesc.getType(); - if (!fieldType.isImmutable()) { - doneSetIdentifier = hrnSummary.getIDString() + "_" + typeFieldDesc; - if(!doneSet.contains(doneSetIdentifier)){ - // add new work item - HashMap newMap = - new HashMap(); - newMap.put(hrnSummary, typeFieldDesc); - workSet.add(newMap); - } + 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 @@ -1343,7 +2331,8 @@ private ReachGraph createInitialTaskReachGraph(FlatMethod fm) { fd.getType(), // type fd.getSymbol(), // field name srcHRN.getAlpha(), // beta - ExistPredSet.factory(rg.predTrue) // predicates + ExistPredSet.factory(rg.predTrue), // predicates + null ); rg.addRefEdge(srcHRN, hrnDst, edgeToSummary); @@ -1354,87 +2343,203 @@ private ReachGraph createInitialTaskReachGraph(FlatMethod fm) { // 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); - int zzz = 0; + // 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); + } + } + } - - - // get successive captures of the analysis state - boolean takeDebugSnapshots = false; - String descSymbolDebug = "main"; - boolean stopAfterCapture = true; + // 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(); - // increments every visit to debugSnapshot, don't fiddle with it - int debugCounter = 0; + if( !visited.contains(md) ) { + toVisit.add(md); + } + } + } + } - // 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; + return asSetTotal; +} - // the frequency of debugCounter values to print out, 0 no report - int freqCountReport = 0; + public Set getDescriptorsToAnalyze() { + return descriptorsToAnalyze; + } - // the debugCounter value at which to start taking snapshots - int iterStartCapture = 0; + 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; - // the number of snapshots to take - int numIterToCapture = 300; void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) { - if( debugCounter > iterStartCapture + numIterToCapture ) { + if( snapVisitCounter > visitStartCapture + numVisitsToCapture ) { return; } if( in ) { - ++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)+ + if( snapVisitCounter >= visitStartCapture ) { + System.out.println( " @@@ snapping visit="+snapVisitCounter+ + ", node="+snapNodeCounter+ " @@@" ); String graphName; if( in ) { - graphName = String.format( "snap%04din", - debugCounter - iterStartCapture ); + graphName = String.format( "snap%03d_%04din", + snapVisitCounter, + snapNodeCounter ); } else { - graphName = String.format( "snap%04dout", - debugCounter - iterStartCapture ); + graphName = String.format( "snap%03d_%04dout", + snapVisitCounter, + snapNodeCounter ); } if( fn != null ) { graphName = graphName + fn; } - try { - rg.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 - 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 ); + 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 } }