protected EffectsAnalysis effectsAnalysis;
protected BuildStateMachines buildStateMachines;
+ protected boolean doDefiniteReachAnalysis = false;
+ protected DefiniteReachAnalysis definiteReachAnalysis;
+
// data structure for public interface
private Hashtable< Descriptor, HashSet<AllocSite> >
protected Hashtable<Descriptor, ReachGraph>
mapDescriptorToInitialContext;
+ // mapping of current partial results for a given node. Note that
+ // to reanalyze a method we discard all partial results because a
+ // null reach graph indicates the node needs to be visited on the
+ // way to the fixed point.
+ // The reason for a persistent mapping is so after the analysis we
+ // can ask for the graph of any node at the fixed point, but this
+ // option is only enabled with a compiler flag.
+ protected Hashtable<FlatNode, ReachGraph> mapFlatNodeToReachGraphPersist;
+ protected Hashtable<FlatNode, ReachGraph> mapFlatNodeToReachGraph;
+
+
// 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
mapDescriptorToInitialContext =
new Hashtable<Descriptor, ReachGraph>();
+ mapFlatNodeToReachGraphPersist =
+ new Hashtable<FlatNode, ReachGraph>();
+
mapBackEdgeToMonotone =
new Hashtable<FlatNode, ReachGraph>();
ReachGraph.debugCallSiteVisitCounter
= 0; // count visits from 1, is incremented before first visit
+ if( state.DO_DEFINITE_REACH_ANALYSIS ) {
+ doDefiniteReachAnalysis = true;
+ definiteReachAnalysis = new DefiniteReachAnalysis();
+ }
if( suppressOutput ) {
writeFinalGraphs();
}
- if( state.DISJOINTWRITEIHMS && !suppressOutput ) {
+ if( state.DISJOINTWRITEIHMS ) {
writeFinalIHMs();
}
- if( state.DISJOINTWRITEINITCONTEXTS && !suppressOutput ) {
+ if( state.DISJOINTWRITEINITCONTEXTS ) {
writeInitialContexts();
}
+ if( state.DISJOINT_WRITE_ALL_NODE_FINAL_GRAPHS ) {
+ writeFinalGraphsForEveryNode();
+ }
+
if( state.DISJOINTALIASFILE != null && !suppressOutput ) {
if( state.TASK ) {
writeAllSharing(state.DISJOINTALIASFILE, treport, justtime, state.DISJOINTALIASTAB, state.lines);
flatNodesToVisitQ.add(fm);
}
- // mapping of current partial results
- Hashtable<FlatNode, ReachGraph> mapFlatNodeToReachGraph =
+ // start a new mapping of partial results
+ mapFlatNodeToReachGraph =
new Hashtable<FlatNode, ReachGraph>();
// the set of return nodes partial results that will be combined as
if( !rg.equals(rgPrev) ) {
mapFlatNodeToReachGraph.put(fn, rg);
+ // we don't necessarily want to keep the reach graph for every
+ // node in the program unless a client or the user wants it
+ if( state.DISJOINT_WRITE_ALL_NODE_FINAL_GRAPHS ) {
+ mapFlatNodeToReachGraphPersist.put(fn, rg);
+ }
+
for( int i = 0; i < pm.numNext(fn); i++ ) {
FlatNode nn = pm.getNext(fn, i);
// states after the flat method returns
ReachGraph completeGraph = new ReachGraph();
+ if( setReturns.isEmpty() ) {
+ System.out.println( "d = "+d );
+
+ }
assert !setReturns.isEmpty();
Iterator retItr = setReturns.iterator();
while( retItr.hasNext() ) {
FlatSESEEnterNode sese;
FlatSESEExitNode fsexn;
+ Set<EdgeKey> edgeKeysRemoved;
+
//Stores the flatnode's reach graph at enter
ReachGraph rgOnEnter = new ReachGraph();
rgOnEnter.merge(rg);
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 );
+ }
} break;
case FKind.FlatOpNode:
if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
if(rblockRel.isPotentialStallSite(fn)) {
// x gets status of y
-// if(!rg.isAccessible(rhs)){
if(!accessible.isAccessible(fn, rhs)) {
rg.makeInaccessible(lhs);
}
// transfer func
rg.assignTempXEqualToTempY(lhs, rhs);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.copy( fn, lhs, rhs );
+ }
}
break;
if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
if(rblockRel.isPotentialStallSite(fn)) {
// x gets status of y
-// if(!rg.isAccessible(rhs)){
if(!accessible.isAccessible(fn,rhs)) {
rg.makeInaccessible(lhs);
}
// transfer func
rg.assignTempXEqualToCastedTempY(lhs, rhs, td);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.copy( fn, lhs, rhs );
+ }
break;
case FKind.FlatFieldNode:
if(rblockRel.isPotentialStallSite(fn)) {
// x=y.f, stall y if not accessible
// contributes read effects on stall site of y
-// if(!rg.isAccessible(rhs)) {
if(!accessible.isAccessible(fn,rhs)) {
rg.taintStallSite(fn, rhs);
}
if( shouldAnalysisTrack(fld.getType() ) ) {
// transfer func
rg.assignTempXEqualToTempYFieldF(lhs, rhs, fld, fn);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.load( fn, lhs, rhs, fld );
+ }
}
// after transfer, use updated graph to
boolean strongUpdate = false;
+ edgeKeysRemoved = null;
+ if( doDefiniteReachAnalysis ) {
+ edgeKeysRemoved = new HashSet<EdgeKey>();
+ }
+
// before transfer func, possibly inject
// stall-site taints
if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
if(rblockRel.isPotentialStallSite(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)) {
if(!accessible.isAccessible(fn,lhs)) {
rg.taintStallSite(fn, lhs);
}
-// if(!rg.isAccessible(rhs)) {
if(!accessible.isAccessible(fn,rhs)) {
rg.taintStallSite(fn, rhs);
}
if( shouldAnalysisTrack(fld.getType() ) ) {
// transfer func
- strongUpdate = rg.assignTempXFieldFEqualToTempY(lhs, fld, rhs, fn);
+ strongUpdate = rg.assignTempXFieldFEqualToTempY(lhs, fld, rhs, fn, edgeKeysRemoved);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.store( fn, lhs, fld, rhs, edgeKeysRemoved );
+ }
}
// use transformed graph to do effects analysis
// 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)) {
if(!accessible.isAccessible(fn,rhs)) {
rg.taintStallSite(fn, rhs);
}
if( shouldAnalysisTrack(lhs.getType() ) ) {
// transfer func
rg.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement, fn);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.load( fn, lhs, rhs, fdElement );
+ }
}
// 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;
+ if( doDefiniteReachAnalysis ) {
+ edgeKeysRemoved = new HashSet<EdgeKey>();
+ }
+
// before transfer func, possibly inject
// stall-site taints
if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
if(rblockRel.isPotentialStallSite(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)) {
if(!accessible.isAccessible(fn,lhs)) {
rg.taintStallSite(fn, lhs);
}
-// if(!rg.isAccessible(rhs)) {
if(!accessible.isAccessible(fn,rhs)) {
rg.taintStallSite(fn, rhs);
}
// 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);
+ }
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.store( fn, lhs, fdElement, rhs, edgeKeysRemoved );
}
}
// transfer func
rg.assignTempEqualToNewAlloc(lhs, as);
+
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.newObject( fn, lhs );
+ }
}
break;
FlatMethod fmCallee = state.getMethodFlat(mdCallee);
+ if( doDefiniteReachAnalysis ) {
+ definiteReachAnalysis.methodCall( fn, fc.getReturnTemp() );
+ }
+
// the transformation for a call site should update the
// current heap abstraction with any effects from the callee,
Set<Integer> callerNodeIDsCopiedToCallee =
new HashSet<Integer>();
+
ReachGraph heapForThisCall_cur =
rg.makeCalleeView(fc,
fmPossible,
dcsd.writeDebugDOTs
);
+
// enforce that a call site contribution can only
// monotonically increase
heapForThisCall_cur.merge(heapForThisCall_old);
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 ) {
}
+
statusDebugCallSite( dcsd );
+
// now that we've taken care of building heap models for
// callee analysis, finish this transformation
rg = rgMergeOfPossibleCallers;
// before transfer, do effects analysis support
if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) {
-// if(!rg.isAccessible(rhs)){
if(!accessible.isAccessible(fn,rhs)) {
rg.makeInaccessible(ReachGraph.tdReturn);
}
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
}
}
+ private void writeFinalGraphsForEveryNode() {
+ Set entrySet = mapFlatNodeToReachGraphPersist.entrySet();
+ Iterator itr = entrySet.iterator();
+ while( itr.hasNext() ) {
+ Map.Entry me = (Map.Entry) itr.next();
+ FlatNode fn = (FlatNode) me.getKey();
+ ReachGraph rg = (ReachGraph) me.getValue();
+
+ rg.writeGraph("NODEFINAL"+fn,
+ true, // write labels (variables)
+ false, // selectively hide intermediate temp vars
+ true, // prune unreachable heap regions
+ true, // hide all reachability
+ true, // hide subset reachability states
+ true, // hide predicates
+ true); // hide edge taints
+ }
+ }
+
protected ReachGraph getPartial(Descriptor d) {
return mapDescriptorToCompleteReachGraph.get(d);
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 );
+
}
state.DISJOINTDEBUGCALLER.equals( taskOrMethodCaller.getSymbol() );
}
+
dcsd.debugCallSite = debugCalleeMatches && debugCallerMatches;
- dcsd.writeDebugDOTs = dcsd.debugCallSite;
+
+
+ dcsd.writeDebugDOTs =
+
+ dcsd.debugCallSite &&
+
+ (ReachGraph.debugCallSiteVisitCounter >=
+ ReachGraph.debugCallSiteVisitStartCapture) &&
+
+ (ReachGraph.debugCallSiteVisitCounter <
+ ReachGraph.debugCallSiteVisitStartCapture +
+ ReachGraph.debugCallSiteNumVisitsToCapture);
+
+
if( dcsd.debugCallSite ) {
dcsd.didOneDebug = true;
- System.out.println( " --> Debugging "+taskOrMethodCaller+" calling "+mdCallee );
}
}
dcsd.stopAfter = false;
if( dcsd.didOneDebug ) {
- ++ReachGraph.debugCallSiteVisitCounter;
System.out.println(" $$$ Debug call site visit "+
ReachGraph.debugCallSiteVisitCounter+
" $$$"
dcsd.stopAfter = true;
}
}
+
+ ++ReachGraph.debugCallSiteVisitCounter;
}
if( dcsd.stopAfter ) {
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
}
return rgAtEnter.canPointTo( x );
}
-
-
- public Set<Alloc> canPointToAfter( TempDescriptor x,
- FlatNode programPoint ) {
-
- ReachGraph rgAtExit = fn2rgAtExit.get( programPoint );
- if( rgAtExit == null ) {
- return null;
- }
-
- return rgAtExit.canPointTo( x );
- }
public Hashtable< Alloc, Set<Alloc> > canPointToAt( TempDescriptor x,
return rgAtEnter.canPointTo( x, arrayElementFieldName, x.getType().dereference() );
}
+
+
+ public Set<Alloc> canPointToAfter( TempDescriptor x,
+ FlatNode programPoint ) {
+
+ ReachGraph rgAtExit = fn2rgAtExit.get( programPoint );
+
+ if( rgAtExit == null ) {
+ return null;
+ }
+
+ return rgAtExit.canPointTo( x );
+ }
+
+
+ public Hashtable< Alloc, Set<Alloc> > canPointToAfter( TempDescriptor x,
+ FieldDescriptor f,
+ FlatNode programPoint ) {
+
+ ReachGraph rgAtExit = fn2rgAtExit.get( programPoint );
+ if( rgAtExit == null ) {
+ return null;
+ }
+
+ return rgAtExit.canPointTo( x, f.getSymbol(), f.getType() );
+ }
+
+
+ public Hashtable< Alloc, Set<Alloc> > canPointToAfterElement( TempDescriptor x,
+ FlatNode programPoint ) {
+
+ ReachGraph rgAtExit = fn2rgAtExit.get( programPoint );
+ if( rgAtExit == null ) {
+ return null;
+ }
+
+ assert x.getType() != null;
+ assert x.getType().isArray();
+
+ return rgAtExit.canPointTo( x, arrayElementFieldName, x.getType().dereference() );
+ }
}
projects / IRC.git / blobdiff