public class DisjointAnalysis {
- ///////////////////////////////////////////
- //
- // Public interface to discover possible
- // aliases in the program under analysis
- //
- ///////////////////////////////////////////
-
- public HashSet<AllocSite>
- getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
- checkAnalysisComplete();
- return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
- }
+ ///////////////////////////////////////////
+ //
+ // 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<AllocSite>
+ getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
+ checkAnalysisComplete();
+ return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
+ }
- public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) {
- checkAnalysisComplete();
- return getAllocSiteFromFlatNewPRIVATE(fn);
- }
+ public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) {
+ checkAnalysisComplete();
+ return getAllocSiteFromFlatNewPRIVATE(fn);
+ }
- public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) {
- checkAnalysisComplete();
- return mapHrnIdToAllocSite.get(id);
- }
+ public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) {
+ checkAnalysisComplete();
+ return mapHrnIdToAllocSite.get(id);
+ }
- public Set<HeapRegionNode> 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<HeapRegionNode> 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<HeapRegionNode> 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<HeapRegionNode> 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<HeapRegionNode> 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<HeapRegionNode> 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<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
- AllocSite alloc1, AllocSite alloc2) {
- checkAnalysisComplete();
- ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
- assert (rg != null);
- return rg.mayReachSharedObjects(alloc1, alloc2);
- }
+ public Set<HeapRegionNode> 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<HeapRegionNode> s) {
- checkAnalysisComplete();
+ public String prettyPrintNodeSet(Set<HeapRegionNode> s) {
+ checkAnalysisComplete();
- String out = "{\n";
+ String out = "{\n";
- Iterator<HeapRegionNode> i = s.iterator();
- while (i.hasNext()) {
- HeapRegionNode n = i.next();
+ Iterator<HeapRegionNode> 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";
- }
- }
+ AllocSite as = n.getAllocSite();
+ if (as == null) {
+ out += " " + n.toString() + ",\n";
+ } else {
+ out += " " + n.toString() + ": " + as.toStringVerbose()
+ + ",\n";
+ }
+ }
- out += "}\n";
- return out;
- }
+ out += "}\n";
+ return out;
+ }
// use the methods given above to check every possible sharing class
// between task parameters and flagged allocation sites reachable
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,
//
///////////////////////////////////////////
+
+
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;
protected Hashtable< Descriptor, Set<Descriptor> >
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<FlatNew> sitesToFlag;
+
// maps each flat new to one analysis abstraction
// allocate site object, these exist outside reach graphs
protected Hashtable<FlatNew, AllocSite>
CallGraph cg,
Liveness l,
ArrayReferencees ar,
+ Set<FlatNew> sitesToFlag,
RBlockRelationAnalysis rra,
RBlockStatusAnalysis rsa
) {
- init( s, tu, cg, l, ar, rra, rsa );
+ init( s, tu, cg, l, ar, sitesToFlag, rra, rsa, false );
+ }
+
+ public DisjointAnalysis( State s,
+ TypeUtil tu,
+ CallGraph cg,
+ Liveness l,
+ ArrayReferencees ar,
+ Set<FlatNew> sitesToFlag,
+ RBlockRelationAnalysis rra,
+ RBlockStatusAnalysis rsa,
+ boolean suppressOutput
+ ) {
+ init( s, tu, cg, l, ar, sitesToFlag, rra, rsa, suppressOutput );
}
protected void init( State state,
CallGraph callGraph,
Liveness liveness,
ArrayReferencees arrayReferencees,
+ Set<FlatNew> sitesToFlag,
RBlockRelationAnalysis rra,
- RBlockStatusAnalysis rsa
+ RBlockStatusAnalysis rsa,
+ boolean suppressOutput
) {
analysisComplete = false;
- this.state = state;
- this.typeUtil = typeUtil;
- this.callGraph = callGraph;
- this.liveness = liveness;
- this.arrayReferencees = arrayReferencees;
- this.rblockRel = rra;
- this.rblockStatus = rsa;
+ 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;
this.releaseMode = state.DISJOINTRELEASEMODE;
this.determinismDesired = state.DISJOINTDETERMINISM;
- this.writeFinalDOTs = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL;
- this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS && state.DISJOINTWRITEALL;
+ this.writeFinalDOTs = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL && !suppressOutput;
+ this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS && state.DISJOINTWRITEALL && !suppressOutput;
this.takeDebugSnapshots = state.DISJOINTSNAPSYMBOL != null;
this.descSymbolDebug = state.DISJOINTSNAPSYMBOL;
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 );
+
try {
if( writeFinalDOTs && !writeAllIncrementalDOTs ) {
writeFinalGraphs();
}
- if( state.DISJOINTWRITEIHMS ) {
+ if( state.DISJOINTWRITEIHMS && !suppressOutput ) {
writeFinalIHMs();
}
- if( state.DISJOINTWRITEINITCONTEXTS ) {
+ if( state.DISJOINTWRITEINITCONTEXTS && !suppressOutput ) {
writeInitialContexts();
}
- if( state.DISJOINTALIASFILE != null ) {
+ if( state.DISJOINTALIASFILE != null && !suppressOutput ) {
if( state.TASK ) {
writeAllSharing(state.DISJOINTALIASFILE, treport, justtime, state.DISJOINTALIASTAB, state.lines);
} else {
throw new Error( "IO Exception while writing disjointness analysis output." );
}
- if( doEffectsAnalysis ) {
- effectsAnalysis.writeEffects( "effects.txt" );
- }
}
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 );
+ rg.taintInSetVars( sese );
+
}
break;
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 );
);
}
- ReachGraph rgMergeOfEffects = new ReachGraph();
+ ReachGraph rgMergeOfPossibleCallers = new ReachGraph();
Iterator<MethodDescriptor> mdItr = setPossibleCallees.iterator();
while( mdItr.hasNext() ) {
// 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
if( state.DISJOINTDVISITSTACKEESONTOP ) {
} else {
// calculate the method call transform
- rgCopy.resolveMethodCall( fc,
- fmPossible,
- rgEffect,
- callerNodeIDsCopiedToCallee,
- writeDebugDOTs
- );
+ 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 );
}
// 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();
+
+ // 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;
// 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.factory( allocationDepth,
fnew,
fnew.getDisjointId(),
- false
+ flagProgrammatically
);
// the newest nodes are single objects
return effectsAnalysis;
}
+ public ReachGraph getReachGraph(Descriptor d){
+ return mapDescriptorToCompleteReachGraph.get(d);
+ }
+
// get successive captures of the analysis state, use compiler
// flags to control