protected EffectsAnalysis effectsAnalysis;
protected BuildStateMachines buildStateMachines;
+ protected boolean doDefiniteReachAnalysis = false;
+ protected DefiniteReachAnalysis definiteReachAnalysis;
+
// data structure for public interface
private Hashtable< Descriptor, HashSet<AllocSite> >
mapDescriptorToReachGraph =
new Hashtable<Descriptor, ReachGraph>();
- pm = new PointerMethod();
-
fc2enclosing = new Hashtable<FlatCall, Descriptor>();
}
ReachGraph.debugCallSiteVisitCounter
= 0; // count visits from 1, is incremented before first visit
+ pm = new PointerMethod();
+
+ if( state.DO_DEFINITE_REACH_ANALYSIS ) {
+ doDefiniteReachAnalysis = true;
+ definiteReachAnalysis = new DefiniteReachAnalysis( pm );
+ }
if( suppressOutput ) {
FlatSESEEnterNode sese;
FlatSESEExitNode fsexn;
+ Set<EdgeKey> edgeKeysForLoad;
+ Set<EdgeKey> edgeKeysRemoved;
+ Set<EdgeKey> edgeKeysAdded;
+
//Stores the flatnode's reach graph at enter
ReachGraph rgOnEnter = new ReachGraph();
rgOnEnter.merge(rg);
fn2rgAtEnter.put(fn, rgOnEnter);
+
+ boolean didDefReachTransfer = false;
+
+
// use node type to decide what transfer function
// to apply to the reachability graph
rg.writeGraph("genReach"+fgrn.getGraphName(),
true, // write labels (variables)
- false, //true, // selectively hide intermediate temp vars
+ true, // selectively hide intermediate temp vars
true, // prune unreachable heap regions
- true, // hide reachability altogether
+ false, // hide reachability altogether
true, // hide subset reachability states
true, // hide predicates
true); //false); // hide edge taints
} break;
+ case FKind.FlatGenDefReachNode: {
+ FlatGenDefReachNode fgdrn = (FlatGenDefReachNode) fn;
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.writeState( fn, fgdrn.getOutputName() );
+ }
+ } break;
+
+
case FKind.FlatMethod: {
// construct this method's initial heap model (IHM)
// since we're working on the FlatMethod, we know
rg.merge(rgPrevContext);
mapDescriptorToInitialContext.put(d, rg);
+ if( doDefiniteReachAnalysis ) {
+ FlatMethod fm = (FlatMethod) fn;
+ Set<TempDescriptor> params = new HashSet<TempDescriptor>();
+ for( int i = 0; i < fm.numParameters(); ++i ) {
+ params.add( fm.getParameter( i ) );
+ }
+ definiteReachAnalysis.methodEntry( fn, params );
+ didDefReachTransfer = true;
+ }
} break;
case FKind.FlatOpNode:
// transfer func
rg.assignTempXEqualToTempY(lhs, rhs);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.copy( fn, lhs, rhs );
+ didDefReachTransfer = true;
+ }
}
break;
// transfer func
rg.assignTempXEqualToCastedTempY(lhs, rhs, td);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.copy( fn, lhs, rhs );
+ didDefReachTransfer = true;
+ }
break;
case FKind.FlatFieldNode:
}
}
+ edgeKeysForLoad = null;
+ if( doDefiniteReachAnalysis ) {
+ edgeKeysForLoad = new HashSet<EdgeKey>();
+ }
+
if( shouldAnalysisTrack(fld.getType() ) ) {
// transfer func
- rg.assignTempXEqualToTempYFieldF(lhs, rhs, fld, fn);
+ rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld, fn, edgeKeysForLoad );
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.load( fn, lhs, rhs, fld, edgeKeysForLoad );
+ didDefReachTransfer = true;
+ }
}
// after transfer, use updated graph to
boolean strongUpdate = false;
+ edgeKeysRemoved = null;
+ edgeKeysAdded = null;
+ if( doDefiniteReachAnalysis ) {
+ edgeKeysRemoved = new HashSet<EdgeKey>();
+ edgeKeysAdded = new HashSet<EdgeKey>();
+ }
+
// before transfer func, possibly inject
// stall-site taints
if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
if( shouldAnalysisTrack(fld.getType() ) ) {
// transfer func
- strongUpdate = rg.assignTempXFieldFEqualToTempY(lhs, fld, rhs, fn);
+ strongUpdate = rg.assignTempXFieldFEqualToTempY( lhs,
+ fld,
+ rhs,
+ fn,
+ edgeKeysRemoved,
+ edgeKeysAdded );
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.store( fn,
+ lhs,
+ fld,
+ rhs,
+ edgeKeysRemoved,
+ edgeKeysAdded );
+ didDefReachTransfer = true;
+ }
}
// use transformed graph to do effects analysis
}
}
+ edgeKeysForLoad = null;
+ if( doDefiniteReachAnalysis ) {
+ edgeKeysForLoad = new HashSet<EdgeKey>();
+ }
+
if( shouldAnalysisTrack(lhs.getType() ) ) {
// transfer func
- rg.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement, fn);
+ rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement, fn, edgeKeysForLoad );
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.load( fn, lhs, rhs, fdElement, edgeKeysForLoad );
+ didDefReachTransfer = true;
+ }
}
// use transformed graph to do effects analysis
lhs = fsen.getDst();
rhs = fsen.getSrc();
-
+
assert lhs.getType() != null;
assert lhs.getType().isArray();
tdElement = lhs.getType().dereference();
fdElement = getArrayField(tdElement);
+ edgeKeysRemoved = null;
+ edgeKeysAdded = null;
+ if( doDefiniteReachAnalysis ) {
+ edgeKeysRemoved = new HashSet<EdgeKey>();
+ edgeKeysAdded = new HashSet<EdgeKey>();
+ }
+
// before transfer func, possibly inject
// stall-site taints
if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
// transfer func, BUT
// skip this node if it cannot create new reachability paths
if( !arrayReferencees.doesNotCreateNewReaching(fsen) ) {
- rg.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs, fn);
+ rg.assignTempXFieldFEqualToTempY( lhs,
+ fdElement,
+ rhs,
+ fn,
+ edgeKeysRemoved,
+ edgeKeysAdded );
+ }
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.store( fn,
+ lhs,
+ fdElement,
+ rhs,
+ edgeKeysRemoved,
+ edgeKeysAdded );
+ didDefReachTransfer = true;
}
}
// transfer func
rg.assignTempEqualToNewAlloc(lhs, as);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.newObject( fn, lhs );
+ didDefReachTransfer = true;
+ }
}
break;
FlatMethod fmCallee = state.getMethodFlat(mdCallee);
-
-
-
-
-
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.methodCall( fn, fc.getReturnTemp() );
+ didDefReachTransfer = true;
+ }
// the transformation for a call site should update the
fc2enclosing.put(fc, mdCaller);
if( state.DISJOINTDEBUGSCHEDULING ) {
- System.out.println(" context changed, scheduling callee: "+mdPossible);
+ System.out.println(" context changed at callsite: "+fc+", scheduling callee: "+mdPossible);
}
if( state.DISJOINTDVISITSTACKEESONTOP ) {
} // end switch
+
+ if( doDefiniteReachAnalysis && !didDefReachTransfer ) {
+ definiteReachAnalysis.otherStatement( fn );
+ }
+
+
+
// 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
fn2rgAtExit.put(fn, rgOnExit);
+
// 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
Hashtable<FlatCall, ReachGraph> heapsFromCallers =
getIHMcontributions(d);
- heapsFromCallers.put(fc, rg);
+ // ensure inputs to initial contexts increase monotonically
+ ReachGraph merged = new ReachGraph();
+ merged.merge( rg );
+ merged.merge( heapsFromCallers.get( fc ) );
+
+ heapsFromCallers.put( fc, merged );
+
}
true, // selectively hide intermediate temp vars
true, // prune unreachable heap regions
false, // hide reachability
- false, // hide subset reachability states
+ true, // hide subset reachability states
true, // hide predicates
true); // hide edge taints
}