// use to disable improvements for comparison
protected static final boolean DISABLE_STRONG_UPDATES = false;
- protected static final boolean DISABLE_GLOBAL_SWEEP = true;
+ protected static final boolean DISABLE_GLOBAL_SWEEP = false;
// a special out-of-scope temp
protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
+
+ // predicate constants
+ public static final ExistPred predTrue = ExistPred.factory(); // if no args, true
+ public static final ExistPredSet predsEmpty = ExistPredSet.factory();
+ public static final ExistPredSet predsTrue = ExistPredSet.factory( predTrue );
// some frequently used reachability constants
protected static final ReachState rstateEmpty = ReachState.factory();
protected static final ReachSet rsetEmpty = ReachSet.factory();
- protected static final ReachSet rsetWithEmptyState = ReachSet.factory( rstateEmpty );
-
- // predicate constants
- protected static final ExistPred predTrue = ExistPred.factory(); // if no args, true
- protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
- protected static final ExistPredSet predsTrue = ExistPredSet.factory( predTrue );
-
+ protected static final ReachSet rsetWithEmptyState = Canonical.changePredsTo( ReachSet.factory( rstateEmpty ),
+ predsTrue );
// from DisjointAnalysis for convenience
protected static int allocationDepth = -1;
// convenient set of alloc sites for all heap regions
// present in the graph without having to search
public HashSet<AllocSite> allocSites;
+
+ // set of accessible variables for current program statement
+ // if not contains, it is an inaccessible variable
+ public HashSet<TempDescriptor> accessibleVars;
public ReachGraph() {
id2hrn = new Hashtable<Integer, HeapRegionNode>();
td2vn = new Hashtable<TempDescriptor, VariableNode >();
allocSites = new HashSet<AllocSite>();
+ accessibleVars = new HashSet<TempDescriptor>();
}
}
+ // this suite of methods can be used to assert a
+ // very important property of ReachGraph objects:
+ // some element, HeapRegionNode, RefEdge etc.
+ // should be referenced by at most ONE ReachGraph!!
+ // If a heap region or edge or variable should be
+ // in another graph, make a new object with
+ // equivalent properties for a new graph
+ public boolean belongsToThis( RefSrcNode rsn ) {
+ if( rsn instanceof VariableNode ) {
+ VariableNode vn = (VariableNode) rsn;
+ return this.td2vn.get( vn.getTempDescriptor() ) == vn;
+ }
+ HeapRegionNode hrn = (HeapRegionNode) rsn;
+ return this.id2hrn.get( hrn.getID() ) == hrn;
+ }
+
+
+
+
+
// the reason for this method is to have the option
// of creating new heap regions with specific IDs, or
// duplicating heap regions with specific IDs (especially
createNewHeapRegionNode( Integer id,
boolean isSingleObject,
boolean isNewSummary,
- boolean isFlagged,
boolean isOutOfContext,
TypeDescriptor type,
AllocSite allocSite,
String description
) {
- boolean markForAnalysis = isFlagged;
-
TypeDescriptor typeToUse = null;
if( allocSite != null ) {
typeToUse = allocSite.getType();
typeToUse = type;
}
- if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
+ boolean markForAnalysis = false;
+ if( allocSite != null && allocSite.isFlagged() ) {
markForAnalysis = true;
}
+
+ if( allocSite == null ) {
+ assert !markForAnalysis;
+
+ } else if( markForAnalysis != allocSite.isFlagged() ) {
+ assert false;
+ }
+
if( id == null ) {
id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
if( inherent == null ) {
if( markForAnalysis ) {
inherent =
- ReachSet.factory(
- ReachState.factory(
- ReachTuple.factory( id,
- !isSingleObject,
- ReachTuple.ARITY_ONE
- )
- )
- );
+ Canonical.changePredsTo(
+ ReachSet.factory(
+ ReachState.factory(
+ ReachTuple.factory( id,
+ !isSingleObject,
+ ReachTuple.ARITY_ONE,
+ false // out-of-context
+ )
+ )
+ ),
+ predsTrue
+ );
} else {
inherent = rsetWithEmptyState;
}
alpha = inherent;
}
- if( preds == null ) {
- // TODO: do this right? For out-of-context nodes?
- preds = ExistPredSet.factory();
- }
-
+ assert preds != null;
+
HeapRegionNode hrn = new HeapRegionNode( id,
isSingleObject,
markForAnalysis,
assert edge != null;
assert edge.getSrc() == referencer;
assert edge.getDst() == referencee;
+ assert belongsToThis( referencer );
+ assert belongsToThis( referencee );
// edges are getting added twice to graphs now, the
// kind that should have abstract facts merged--use
referencer.removeReferencee( edge );
referencee.removeReferencer( edge );
+
+ // TODO
+
+// int oldTaint=edge.getTaintIdentifier();
+// if(referencer instanceof HeapRegionNode){
+// depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
+// }
+
+
}
- protected void clearRefEdgesFrom( RefSrcNode referencer,
- TypeDescriptor type,
- String field,
- boolean removeAll ) {
+ // return whether at least one edge was removed
+ protected boolean clearRefEdgesFrom( RefSrcNode referencer,
+ TypeDescriptor type,
+ String field,
+ boolean removeAll ) {
assert referencer != null;
+ boolean atLeastOneEdgeRemoved = false;
+
// get a copy of the set to iterate over, otherwise
// we will be trying to take apart the set as we
// are iterating over it, which won't work
referencee,
edge.getType(),
edge.getField() );
+
+ atLeastOneEdgeRemoved = true;
}
}
+
+ return atLeastOneEdgeRemoved;
}
protected void clearRefEdgesTo( HeapRegionNode referencee,
}
}
+ // this is a common operation in many transfer functions: we want
+ // to add an edge, but if there is already such an edge we should
+ // merge the properties of the existing and the new edges
+ protected void addEdgeOrMergeWithExisting( RefEdge edgeNew ) {
+
+ RefSrcNode src = edgeNew.getSrc();
+ assert belongsToThis( src );
+
+ HeapRegionNode dst = edgeNew.getDst();
+ assert belongsToThis( dst );
+
+ // look to see if an edge with same field exists
+ // and merge with it, otherwise just add the edge
+ RefEdge edgeExisting = src.getReferenceTo( dst,
+ edgeNew.getType(),
+ edgeNew.getField()
+ );
+
+ if( edgeExisting != null ) {
+ edgeExisting.setBeta(
+ Canonical.unionORpreds( edgeExisting.getBeta(),
+ edgeNew.getBeta()
+ )
+ );
+ edgeExisting.setPreds(
+ Canonical.join( edgeExisting.getPreds(),
+ edgeNew.getPreds()
+ )
+ );
+ edgeExisting.setTaints(
+ Canonical.unionORpreds( edgeExisting.getTaints(),
+ edgeNew.getTaints()
+ )
+ );
+
+ } else {
+ addRefEdge( src, dst, edgeNew );
+ }
+ }
+
+
////////////////////////////////////////////////////
//
public void assignTempXEqualToTempY( TempDescriptor x,
TempDescriptor y ) {
assignTempXEqualToCastedTempY( x, y, null );
+
+ // x gets status of y
+ // if it is in region,
+ //if(accessibleVars.contains(y)){
+ // accessibleVars.add(x);
+ //}
}
public void assignTempXEqualToCastedTempY( TempDescriptor x,
tdNewEdge,
null,
Canonical.intersection( betaY, betaHrn ),
- predsTrue
+ predsTrue,
+ edgeY.getTaints()
);
-
- addRefEdge( lnX, hrnHrn, edgeNew );
+
+ addEdgeOrMergeWithExisting( edgeNew );
}
}
if( !DISABLE_GLOBAL_SWEEP ) {
globalSweep();
}
- }
+ }
+
+ // accessible status update
+ // if it is in region,
+ //accessibleVars.add(x);
+ //accessibleVars.add(y);
}
- public void assignTempXFieldFEqualToTempY( TempDescriptor x,
- FieldDescriptor f,
- TempDescriptor y ) {
+ // return whether a strong update was actually effected
+ public boolean assignTempXFieldFEqualToTempY( TempDescriptor x,
+ FieldDescriptor f,
+ TempDescriptor y ) {
VariableNode lnX = getVariableNodeFromTemp( x );
VariableNode lnY = getVariableNodeFromTemp( y );
Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
// first look for possible strong updates and remove those edges
- boolean strongUpdate = false;
+ boolean strongUpdateCond = false;
+ boolean edgeRemovedByStrongUpdate = false;
Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
while( itrXhrn.hasNext() ) {
)
) {
if( !DISABLE_STRONG_UPDATES ) {
- strongUpdate = true;
- clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
+ strongUpdateCond = true;
+
+ boolean atLeastOne =
+ clearRefEdgesFrom( hrnX,
+ f.getType(),
+ f.getSymbol(),
+ false );
+ if( atLeastOne ) {
+ edgeRemovedByStrongUpdate = true;
+ }
}
}
}
hrnY.getType()
);
- RefEdge edgeNew = new RefEdge( hrnX,
- hrnY,
- tdNewEdge,
- f.getSymbol(),
- Canonical.pruneBy( edgeY.getBeta(),
- hrnX.getAlpha()
- ),
- predsTrue
- );
+ RefEdge edgeNew =
+ new RefEdge( hrnX,
+ hrnY,
+ tdNewEdge,
+ f.getSymbol(),
+ Canonical.changePredsTo(
+ Canonical.pruneBy( edgeY.getBeta(),
+ hrnX.getAlpha()
+ ),
+ predsTrue
+ ),
+ predsTrue,
+ Canonical.changePredsTo( edgeY.getTaints(),
+ predsTrue )
+ );
- // look to see if an edge with same field exists
- // and merge with it, otherwise just add the edge
- RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
- tdNewEdge,
- f.getSymbol() );
-
- if( edgeExisting != null ) {
- edgeExisting.setBeta(
- Canonical.union( edgeExisting.getBeta(),
- edgeNew.getBeta()
- )
- );
- edgeExisting.setPreds(
- Canonical.join( edgeExisting.getPreds(),
- edgeNew.getPreds()
- )
- );
-
- } else {
- addRefEdge( hrnX, hrnY, edgeNew );
- }
+ addEdgeOrMergeWithExisting( edgeNew );
}
}
// if there was a strong update, make sure to improve
// reachability with a global sweep
- if( strongUpdate || !impossibleEdges.isEmpty() ) {
+ if( edgeRemovedByStrongUpdate || !impossibleEdges.isEmpty() ) {
if( !DISABLE_GLOBAL_SWEEP ) {
globalSweep();
}
}
+
+
+ // after x.y=f , stall x and y if they are not accessible
+ // also contribute write effects on stall site of x
+ // accessible status update
+ // if it is in region
+ //accessibleVars.add(x);
+ //accessibleVars.add(y);
+
+ return edgeRemovedByStrongUpdate;
}
HeapRegionNode referencee = edgeX.getDst();
RefEdge edgeNew = edgeX.copy();
edgeNew.setSrc( lnR );
+ edgeNew.setTaints( Canonical.changePredsTo( edgeNew.getTaints(),
+ predsTrue
+ )
+ );
addRefEdge( lnR, referencee, edgeNew );
}
type, // type
null, // field name
hrnNewest.getAlpha(), // beta
- predsTrue // predicates
+ predsTrue, // predicates
+ TaintSet.factory() // taints
);
addRefEdge( lnX, hrnNewest, edgeNew );
+
+ // after x=new , x is accessible
+ // if (isInRegion()) {
+ //accessibleVars.add(x);
}
if( hrnSummary == null ) {
- boolean hasFlags = false;
- if( as.getType().isClass() ) {
- hasFlags = as.getType().getClassDesc().hasFlags();
- }
-
- if( as.getFlag() ){
- hasFlags = as.getFlag();
- }
-
String strDesc = as.toStringForDOT()+"\\nsummary";
- if( shadow ) {
- strDesc += " shadow";
- }
hrnSummary =
createNewHeapRegionNode( idSummary, // id or null to generate a new one
false, // single object?
- true, // summary?
- hasFlags, // flagged?
+ true, // summary?
false, // out-of-context?
as.getType(), // type
as, // allocation site
if( hrnIth == null ) {
- boolean hasFlags = false;
- if( as.getType().isClass() ) {
- hasFlags = as.getType().getClassDesc().hasFlags();
- }
-
- if( as.getFlag() ){
- hasFlags = as.getFlag();
- }
-
String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
- if( shadow ) {
- strDesc += " shadow";
- }
hrnIth = createNewHeapRegionNode( idIth, // id or null to generate a new one
true, // single object?
false, // summary?
- hasFlags, // flagged?
false, // out-of-context?
as.getType(), // type
as, // allocation site
}
- // used to assert that the given node object
- // belongs to THIS graph instance, some gross bugs
- // have popped up where a node from one graph works
- // itself into another
- public boolean belongsToThis( HeapRegionNode hrn ) {
- return this.id2hrn.get( hrn.getID() ) == hrn;
- }
-
protected void mergeIntoSummary( HeapRegionNode hrn,
HeapRegionNode hrnSummary ) {
assert hrnSummary.isNewSummary();
assert belongsToThis( hrn );
assert belongsToThis( hrnSummary );
+ assert hrn != hrnSummary;
+
// transfer references _from_ hrn over to hrnSummary
Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
while( itrReferencee.hasNext() ) {
// otherwise an edge from the referencer to hrnSummary exists already
// and the edge referencer->hrn should be merged with it
edgeSummary.setBeta(
- Canonical.union( edgeMerged.getBeta(),
+ Canonical.unionORpreds( edgeMerged.getBeta(),
edgeSummary.getBeta()
)
);
// otherwise an edge from the referencer to alpha_S exists already
// and the edge referencer->alpha_K should be merged with it
edgeSummary.setBeta(
- Canonical.union( edgeMerged.getBeta(),
+ Canonical.unionORpreds( edgeMerged.getBeta(),
edgeSummary.getBeta()
)
);
// then merge hrn reachability into hrnSummary
hrnSummary.setAlpha(
- Canonical.union( hrnSummary.getAlpha(),
+ Canonical.unionORpreds( hrnSummary.getAlpha(),
hrn.getAlpha()
)
);
assert belongsToThis( hrnA );
assert belongsToThis( hrnB );
+ assert hrnA != hrnB;
- // clear references in and out of node b
+ // clear references in and out of node b?
assert hrnB.isWiped();
- // copy each edge in and out of A to B
+ // copy each: (edge in and out of A) to B
Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
while( itrReferencee.hasNext() ) {
RefEdge edge = itrReferencee.next();
Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
while( itrReferencer.hasNext() ) {
- RefEdge edge = itrReferencer.next();
- RefSrcNode onReferencer = edge.getSrc();
- RefEdge edgeNew = edge.copy();
- edgeNew.setDst( hrnB );
+ RefEdge edge = itrReferencer.next();
+ RefSrcNode rsnReferencer = edge.getSrc();
+ RefEdge edgeNew = edge.copy();
+ edgeNew.setSrc( rsnReferencer );
edgeNew.setDst( hrnB );
- addRefEdge( onReferencer, hrnB, edgeNew );
+ addRefEdge( rsnReferencer, hrnB, edgeNew );
}
// replace hrnB reachability and preds with hrnA's
Iterator<ChangeTuple> itrCprime = C.iterator();
while( itrCprime.hasNext() ) {
ChangeTuple c = itrCprime.next();
- if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
- changesToPass = Canonical.union( changesToPass, c );
+ if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
+ != null
+ ) {
+ changesToPass = Canonical.add( changesToPass, c );
}
}
// but this propagation may be only one of many concurrent
// possible changes, so keep a running union with the node's
// partially updated new alpha set
- n.setAlphaNew( Canonical.union( n.getAlphaNew(),
+ n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
localDelta
)
);
Iterator<ChangeTuple> itrC = C.iterator();
while( itrC.hasNext() ) {
ChangeTuple c = itrC.next();
- if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
- changesToPass = Canonical.union( changesToPass, c );
+ if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
+ != null
+ ) {
+ changesToPass = Canonical.add( changesToPass, c );
}
}
// but this propagation may be only one of many concurrent
// possible changes, so keep a running union with the edge's
// partially updated new beta set
- e.setBetaNew( Canonical.union( e.getBetaNew(),
+ e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
localDelta
)
);
}
+ public void taintInSetVars( FlatSESEEnterNode sese ) {
+ if( sese.getIsCallerSESEplaceholder() ) {
+ return;
+ }
+
+ Iterator<TempDescriptor> isvItr = sese.getInVarSet().iterator();
+ while( isvItr.hasNext() ) {
+ TempDescriptor isv = isvItr.next();
+ VariableNode vn = getVariableNodeFromTemp( isv );
+
+ Iterator<RefEdge> reItr = vn.iteratorToReferencees();
+ while( reItr.hasNext() ) {
+ RefEdge re = reItr.next();
+
+ // these in-set taints should have empty
+ // predicates so they never propagate
+ // out to callers
+ Taint t = Taint.factory( sese,
+ null,
+ isv,
+ re.getDst().getAllocSite(),
+ ExistPredSet.factory()
+ );
+
+ re.setTaints( Canonical.add( re.getTaints(),
+ t
+ )
+ );
+ }
+ }
+ }
+
+ // this is useful for more general tainting
+ public void taintTemp( Taint taint,
+ TempDescriptor td,
+ ExistPredSet preds
+ ) {
+
+ VariableNode vn = getVariableNodeFromTemp( td );
+
+ Iterator<RefEdge> reItr = vn.iteratorToReferencees();
+ while( reItr.hasNext() ) {
+ RefEdge re = reItr.next();
+
+ re.setTaints( Canonical.add( re.getTaints(),
+ taint
+ )
+ );
+ }
+ }
+
+ public void removeInContextTaints( FlatSESEEnterNode sese ) {
+ if( sese.getIsCallerSESEplaceholder() ) {
+ return;
+ }
+
+ Iterator meItr = id2hrn.entrySet().iterator();
+ while( meItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) meItr.next();
+ Integer id = (Integer) me.getKey();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ Iterator<RefEdge> reItr = hrn.iteratorToReferencers();
+ while( reItr.hasNext() ) {
+ RefEdge re = reItr.next();
+
+ re.setTaints( Canonical.removeTaintsBy( re.getTaints(),
+ sese
+ )
+ );
+ }
+ }
+ }
+
+
// used in makeCalleeView below to decide if there is
// already an appropriate out-of-context edge in a callee
// view graph for merging, or null if a new one will be added
TypeDescriptor srcType,
TypeDescriptor refType,
String refField ) {
+ assert belongsToThis( hrn );
HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
if( hrnInContext == null ) {
Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
while( refItr.hasNext() ) {
RefEdge re = refItr.next();
+
+ assert belongsToThis( re.getSrc() );
+ assert belongsToThis( re.getDst() );
+
if( !(re.getSrc() instanceof HeapRegionNode) ) {
continue;
}
return null;
}
+ // used below to convert a ReachSet to its callee-context
+ // equivalent with respect to allocation sites in this graph
+ protected ReachSet toCalleeContext( ReachSet rs,
+ ExistPredSet predsNodeOrEdge,
+ Set<HrnIdOoc> oocHrnIdOoc2callee
+ ) {
+ ReachSet out = ReachSet.factory();
+
+ Iterator<ReachState> itr = rs.iterator();
+ while( itr.hasNext() ) {
+ ReachState stateCaller = itr.next();
+
+ ReachState stateCallee = stateCaller;
+
+ Iterator<AllocSite> asItr = allocSites.iterator();
+ while( asItr.hasNext() ) {
+ AllocSite as = asItr.next();
+
+ ReachState stateNew = ReachState.factory();
+ Iterator<ReachTuple> rtItr = stateCallee.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+
+ // only translate this tuple if it is
+ // in the out-callee-context bag
+ HrnIdOoc hio = new HrnIdOoc( rt.getHrnID(),
+ rt.isOutOfContext()
+ );
+ if( !oocHrnIdOoc2callee.contains( hio ) ) {
+ stateNew = Canonical.add( stateNew, rt );
+ continue;
+ }
+
+ int age = as.getAgeCategory( rt.getHrnID() );
+
+ // this is the current mapping, where 0, 1, 2S were allocated
+ // in the current context, 0?, 1? and 2S? were allocated in a
+ // previous context, and we're translating to a future context
+ //
+ // 0 -> 0?
+ // 1 -> 1?
+ // 2S -> 2S?
+ // 2S* -> 2S?*
+ //
+ // 0? -> 2S?
+ // 1? -> 2S?
+ // 2S? -> 2S?
+ // 2S?* -> 2S?*
+
+ if( age == AllocSite.AGE_notInThisSite ) {
+ // things not from the site just go back in
+ stateNew = Canonical.add( stateNew, rt );
+
+ } else if( age == AllocSite.AGE_summary ||
+ rt.isOutOfContext()
+ ) {
+ // the in-context summary and all existing out-of-context
+ // stuff all become
+ stateNew = Canonical.add( stateNew,
+ ReachTuple.factory( as.getSummary(),
+ true, // multi
+ rt.getArity(),
+ true // out-of-context
+ )
+ );
+ } else {
+ // otherwise everything else just goes to an out-of-context
+ // version, everything else the same
+ Integer I = as.getAge( rt.getHrnID() );
+ assert I != null;
+
+ assert !rt.isMultiObject();
+
+ stateNew = Canonical.add( stateNew,
+ ReachTuple.factory( rt.getHrnID(),
+ rt.isMultiObject(),
+ rt.getArity(),
+ true // out-of-context
+ )
+ );
+ }
+ }
+
+ stateCallee = stateNew;
+ }
+
+ // make a predicate of the caller graph element
+ // and the caller state we just converted
+ ExistPredSet predsWithState = ExistPredSet.factory();
+
+ Iterator<ExistPred> predItr = predsNodeOrEdge.iterator();
+ while( predItr.hasNext() ) {
+ ExistPred predNodeOrEdge = predItr.next();
+
+ predsWithState =
+ Canonical.add( predsWithState,
+ ExistPred.factory( predNodeOrEdge.n_hrnID,
+ predNodeOrEdge.e_tdSrc,
+ predNodeOrEdge.e_hrnSrcID,
+ predNodeOrEdge.e_hrnDstID,
+ predNodeOrEdge.e_type,
+ predNodeOrEdge.e_field,
+ stateCallee,
+ null,
+ predNodeOrEdge.e_srcOutCalleeContext,
+ predNodeOrEdge.e_srcOutCallerContext
+ )
+ );
+ }
+
+ stateCallee = Canonical.changePredsTo( stateCallee,
+ predsWithState );
+
+ out = Canonical.add( out,
+ stateCallee
+ );
+ }
+ assert out.isCanonical();
+ return out;
+ }
+
+ // used below to convert a ReachSet to its caller-context
+ // equivalent with respect to allocation sites in this graph
+ protected ReachSet
+ toCallerContext( ReachSet rs,
+ Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
+ ) {
+ ReachSet out = ReachSet.factory();
+
+ // when the mapping is null it means there were no
+ // predicates satisfied
+ if( calleeStatesSatisfied == null ) {
+ return out;
+ }
+
+ Iterator<ReachState> itr = rs.iterator();
+ while( itr.hasNext() ) {
+ ReachState stateCallee = itr.next();
+
+ if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
+
+ // starting from one callee state...
+ ReachSet rsCaller = ReachSet.factory( stateCallee );
+
+ // possibly branch it into many states, which any
+ // allocation site might do, so lots of derived states
+ Iterator<AllocSite> asItr = allocSites.iterator();
+ while( asItr.hasNext() ) {
+ AllocSite as = asItr.next();
+ rsCaller = Canonical.toCallerContext( rsCaller, as );
+ }
+
+ // then before adding each derived, now caller-context
+ // states to the output, attach the appropriate pred
+ // based on the source callee state
+ Iterator<ReachState> stateItr = rsCaller.iterator();
+ while( stateItr.hasNext() ) {
+ ReachState stateCaller = stateItr.next();
+ stateCaller = Canonical.attach( stateCaller,
+ calleeStatesSatisfied.get( stateCallee )
+ );
+ out = Canonical.add( out,
+ stateCaller
+ );
+ }
+ }
+ }
+
+ assert out.isCanonical();
+ return out;
+ }
+
+
+ // used below to convert a ReachSet to an equivalent
+ // version with shadow IDs merged into unshadowed IDs
+ protected ReachSet unshadow( ReachSet rs ) {
+ ReachSet out = rs;
+ Iterator<AllocSite> asItr = allocSites.iterator();
+ while( asItr.hasNext() ) {
+ AllocSite as = asItr.next();
+ out = Canonical.unshadow( out, as );
+ }
+ assert out.isCanonical();
+ return out;
+ }
+
+
+ // convert a caller taint set into a callee taint set
+ protected TaintSet
+ toCalleeContext( TaintSet ts,
+ ExistPredSet predsEdge ) {
+
+ TaintSet out = TaintSet.factory();
+
+ // the idea is easy, the taint identifier itself doesn't
+ // change at all, but the predicates should be tautology:
+ // start with the preds passed in from the caller edge
+ // that host the taints, and alter them to have the taint
+ // added, just becoming more specific than edge predicate alone
+
+ Iterator<Taint> itr = ts.iterator();
+ while( itr.hasNext() ) {
+ Taint tCaller = itr.next();
+
+ ExistPredSet predsWithTaint = ExistPredSet.factory();
+
+ Iterator<ExistPred> predItr = predsEdge.iterator();
+ while( predItr.hasNext() ) {
+ ExistPred predEdge = predItr.next();
+
+ predsWithTaint =
+ Canonical.add( predsWithTaint,
+ ExistPred.factory( predEdge.e_tdSrc,
+ predEdge.e_hrnSrcID,
+ predEdge.e_hrnDstID,
+ predEdge.e_type,
+ predEdge.e_field,
+ null,
+ tCaller,
+ predEdge.e_srcOutCalleeContext,
+ predEdge.e_srcOutCallerContext
+ )
+ );
+ }
+
+ Taint tCallee = Canonical.changePredsTo( tCaller,
+ predsWithTaint );
+
+ out = Canonical.add( out,
+ tCallee
+ );
+ }
+
+ assert out.isCanonical();
+ return out;
+ }
+
+
+ // used below to convert a TaintSet to its caller-context
+ // equivalent, just eliminate Taints with bad preds
+ protected TaintSet
+ toCallerContext( TaintSet ts,
+ Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied
+ ) {
+
+ TaintSet out = TaintSet.factory();
+
+ // when the mapping is null it means there were no
+ // predicates satisfied
+ if( calleeTaintsSatisfied == null ) {
+ return out;
+ }
+
+ Iterator<Taint> itr = ts.iterator();
+ while( itr.hasNext() ) {
+ Taint tCallee = itr.next();
+
+ if( calleeTaintsSatisfied.containsKey( tCallee ) ) {
+
+ Taint tCaller =
+ Canonical.attach( Taint.factory( tCallee.sese,
+ tCallee.stallSite,
+ tCallee.var,
+ tCallee.allocSite,
+ ExistPredSet.factory() ),
+ calleeTaintsSatisfied.get( tCallee )
+ );
+ out = Canonical.add( out,
+ tCaller
+ );
+ }
+ }
+
+ assert out.isCanonical();
+ return out;
+ }
+
+
+
// use this method to make a new reach graph that is
// what heap the FlatMethod callee from the FlatCall
// this reach graph
public ReachGraph
makeCalleeView( FlatCall fc,
- FlatMethod fm,
+ FlatMethod fmCallee,
Set<Integer> callerNodeIDsCopiedToCallee,
boolean writeDebugDOTs
) {
- // the callee view is a new graph: DON'T MODIFY
- // *THIS* graph
- ReachGraph rg = new ReachGraph();
- // track what parts of this graph have already been
- // added to callee view, variables not needed.
- // Note that we need this because when we traverse
- // this caller graph for each parameter we may find
- // nodes and edges more than once (which the per-param
- // "visit" sets won't show) and we only want to create
- // an element in the new callee view one time
+ // first traverse this context to find nodes and edges
+ // that will be callee-reachable
+ Set<HeapRegionNode> reachableCallerNodes =
+ new HashSet<HeapRegionNode>();
+ // caller edges between callee-reachable nodes
+ Set<RefEdge> reachableCallerEdges =
+ new HashSet<RefEdge>();
- // a conservative starting point is to take the
- // mechanically-reachable-from-arguments graph
- // as opposed to using reachability information
- // to prune the graph further
- for( int i = 0; i < fm.numParameters(); ++i ) {
+ // caller edges from arg vars, and the matching param index
+ // because these become a special edge in callee
+ Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
+ new Hashtable<RefEdge, Integer>();
+
+ // caller edges from local vars or callee-unreachable nodes
+ // (out-of-context sources) to callee-reachable nodes
+ Set<RefEdge> oocCallerEdges =
+ new HashSet<RefEdge>();
+
+
+ for( int i = 0; i < fmCallee.numParameters(); ++i ) {
+
+ TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
+ VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
- // for each parameter index, get the symbol in the
- // caller view and callee view
-
- // argument defined here is the symbol in the caller
- TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
-
- // parameter defined here is the symbol in the callee
- TempDescriptor tdParam = fm.getParameter( i );
-
- // use these two VariableNode objects to translate
- // between caller and callee--its easy to compare
- // a HeapRegionNode across callee and caller because
- // they will have the same heap region ID
- VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
- VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
-
- // now traverse the calleR view using the argument to
- // build the calleE view which has the parameter symbol
Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
- toVisitInCaller.add( vnCaller );
+ toVisitInCaller.add( vnArgCaller );
+
while( !toVisitInCaller.isEmpty() ) {
RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
- RefSrcNode rsnCallee;
-
toVisitInCaller.remove( rsnCaller );
visitedInCaller.add( rsnCaller );
-
- // FIRST - setup the source end of an edge, and
- // remember the identifying info of the source
- // to build predicates
- TempDescriptor tdSrc = null;
- Integer hrnSrcID = null;
-
- if( rsnCaller == vnCaller ) {
- // if the caller node is the param symbol, we
- // have to do this translation for the callee
- rsnCallee = vnCallee;
- tdSrc = tdArg;
-
- } else {
- // otherwise the callee-view node is a heap
- // region with the same ID, that may or may
- // not have been created already
- assert rsnCaller instanceof HeapRegionNode;
-
- HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
- hrnSrcID = hrnSrcCaller.getID();
-
- if( !callerNodeIDsCopiedToCallee.contains( hrnSrcID ) ) {
-
- ExistPred pred =
- ExistPred.factory( hrnSrcID, null );
-
- ExistPredSet preds =
- ExistPredSet.factory( pred );
-
- rsnCallee =
- rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
- hrnSrcCaller.isSingleObject(),
- hrnSrcCaller.isNewSummary(),
- hrnSrcCaller.isFlagged(),
- false, // out-of-context?
- hrnSrcCaller.getType(),
- hrnSrcCaller.getAllocSite(),
- /*toShadowTokens( this,*/ hrnSrcCaller.getInherent() /*)*/,
- /*toShadowTokens( this,*/ hrnSrcCaller.getAlpha() /*)*/,
- preds,
- hrnSrcCaller.getDescription()
- );
-
- callerNodeIDsCopiedToCallee.add( hrnSrcID );
-
- } else {
- rsnCallee = rg.id2hrn.get( hrnSrcID );
- }
- }
-
- // SECOND - go over all edges from that source
Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
while( itrRefEdges.hasNext() ) {
RefEdge reCaller = itrRefEdges.next();
HeapRegionNode hrnCaller = reCaller.getDst();
- HeapRegionNode hrnCallee;
-
- // THIRD - setup destination ends of edges
- Integer hrnDstID = hrnCaller.getID();
-
- if( !callerNodeIDsCopiedToCallee.contains( hrnDstID ) ) {
-
- ExistPred pred =
- ExistPred.factory( hrnDstID, null );
-
- ExistPredSet preds =
- ExistPredSet.factory( pred );
-
- hrnCallee =
- rg.createNewHeapRegionNode( hrnDstID,
- hrnCaller.isSingleObject(),
- hrnCaller.isNewSummary(),
- hrnCaller.isFlagged(),
- false, // out-of-context?
- hrnCaller.getType(),
- hrnCaller.getAllocSite(),
- /*toShadowTokens( this,*/ hrnCaller.getInherent() /*)*/,
- /*toShadowTokens( this,*/ hrnCaller.getAlpha() /*)*/,
- preds,
- hrnCaller.getDescription()
- );
- callerNodeIDsCopiedToCallee.add( hrnDstID );
+ callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
+ reachableCallerNodes.add( hrnCaller );
+ if( reCaller.getSrc() instanceof HeapRegionNode ) {
+ reachableCallerEdges.add( reCaller );
} else {
- hrnCallee = rg.id2hrn.get( hrnDstID );
+ if( rsnCaller.equals( vnArgCaller ) ) {
+ reachableCallerArgEdges2paramIndex.put( reCaller, i );
+ } else {
+ oocCallerEdges.add( reCaller );
+ }
}
- // FOURTH - copy edge over if needed
- RefEdge reCallee = rsnCallee.getReferenceTo( hrnCallee,
- reCaller.getType(),
- reCaller.getField()
- );
- if( reCallee == null ) {
-
- ExistPred pred =
- ExistPred.factory( tdSrc,
- hrnSrcID,
- hrnDstID,
- reCaller.getType(),
- reCaller.getField(),
- null );
-
- ExistPredSet preds =
- ExistPredSet.factory( pred );
-
- rg.addRefEdge( rsnCallee,
- hrnCallee,
- new RefEdge( rsnCallee,
- hrnCallee,
- reCaller.getType(),
- reCaller.getField(),
- /*toShadowTokens( this,*/ reCaller.getBeta() /*)*/,
- preds
- )
- );
- }
-
- // keep traversing nodes reachable from param i
- // that we haven't visited yet
if( !visitedInCaller.contains( hrnCaller ) ) {
toVisitInCaller.add( hrnCaller );
}
- } // end edge iteration
+ } // end edge iteration
} // end visiting heap nodes in caller
} // end iterating over parameters as starting points
- // find the set of edges in this graph with source
- // out-of-context (not in nodes copied) and have a
- // destination in context (one of nodes copied) as
- // a starting point for building out-of-context nodes
- Iterator<Integer> itrInContext =
+ // now collect out-of-callee-context IDs and
+ // map them to whether the ID is out of the caller
+ // context as well
+ Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
+
+ Iterator<Integer> itrInContext =
callerNodeIDsCopiedToCallee.iterator();
while( itrInContext.hasNext() ) {
Integer hrnID = itrInContext.next();
RefSrcNode rsnCallerAndOutContext =
edgeMightCross.getSrc();
- TypeDescriptor oocNodeType;
- ReachSet oocReach;
-
if( rsnCallerAndOutContext instanceof VariableNode ) {
- // variables are always out-of-context
- oocNodeType = null;
- oocReach = rsetEmpty;
-
- } else {
+ // variables do not have out-of-context reach states,
+ // so jump out now
+ oocCallerEdges.add( edgeMightCross );
+ continue;
+ }
- HeapRegionNode hrnCallerAndOutContext =
- (HeapRegionNode) rsnCallerAndOutContext;
-
- // is this source node out-of-context?
- if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
- // no, skip this edge
- continue;
- }
-
- oocNodeType = hrnCallerAndOutContext.getType();
- oocReach = hrnCallerAndOutContext.getAlpha();
- }
+ HeapRegionNode hrnCallerAndOutContext =
+ (HeapRegionNode) rsnCallerAndOutContext;
+ // is this source node out-of-context?
+ if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
+ // no, skip this edge
+ continue;
+ }
- HeapRegionNode hrnCalleeAndInContext =
- rg.id2hrn.get( hrnCallerAndInContext.getID() );
-
- RefEdge oocEdgeExisting =
- rg.getOutOfContextReferenceTo( hrnCalleeAndInContext,
- oocNodeType,
- edgeMightCross.getType(),
- edgeMightCross.getField()
- );
+ // okay, we got one
+ oocCallerEdges.add( edgeMightCross );
- if( oocEdgeExisting == null ) {
- // we found a reference that crosses from out-of-context
- // to in-context, so build a special out-of-context node
- // for the callee IHM and its reference edge
- HeapRegionNode hrnCalleeAndOutContext =
- rg.createNewHeapRegionNode( null, // ID
- false, // single object?
- false, // new summary?
- false, // flagged?
- true, // out-of-context?
- oocNodeType,
- null, // alloc site, shouldn't be used
- /*toShadowTokens( this,*/ oocReach /*)*/, // inherent
- /*toShadowTokens( this,*/ oocReach /*)*/, // alpha
- predsEmpty,
- "out-of-context"
- );
+ // add all reach tuples on the node to list
+ // of things that are out-of-context: insight
+ // if this node is reachable from someting that WAS
+ // in-context, then this node should already be in-context
+ Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
- rg.addRefEdge( hrnCalleeAndOutContext,
- hrnCalleeAndInContext,
- new RefEdge( hrnCalleeAndOutContext,
- hrnCalleeAndInContext,
- edgeMightCross.getType(),
- edgeMightCross.getField(),
- /*toShadowTokens( this,*/ edgeMightCross.getBeta() /*)*/,
- predsEmpty
- )
- );
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
- } else {
- // the out-of-context edge already exists
- oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
- edgeMightCross.getBeta()
- )
- );
- }
+ oocHrnIdOoc2callee.add( new HrnIdOoc( rt.getHrnID(),
+ rt.isOutOfContext()
+ )
+ );
+ }
+ }
}
- }
-
- if( writeDebugDOTs ) {
- try {
- rg.writeGraph( "calleeview", true, false, false, false, true, true );
- } catch( IOException e ) {}
}
- return rg;
- }
+ // the callee view is a new graph: DON'T MODIFY *THIS* graph
+ ReachGraph rg = new ReachGraph();
+ // add nodes to callee graph
+ Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
+ while( hrnItr.hasNext() ) {
+ HeapRegionNode hrnCaller = hrnItr.next();
+ assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
+ assert !rg.id2hrn.containsKey( hrnCaller.getID() );
+
+ ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
+ ExistPredSet preds = ExistPredSet.factory( pred );
+
+ rg.createNewHeapRegionNode( hrnCaller.getID(),
+ hrnCaller.isSingleObject(),
+ hrnCaller.isNewSummary(),
+ false, // out-of-context?
+ hrnCaller.getType(),
+ hrnCaller.getAllocSite(),
+ toCalleeContext( hrnCaller.getInherent(),
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ toCalleeContext( hrnCaller.getAlpha(),
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ preds,
+ hrnCaller.getDescription()
+ );
+ }
+
+ // add param edges to callee graph
+ Iterator argEdges =
+ reachableCallerArgEdges2paramIndex.entrySet().iterator();
+ while( argEdges.hasNext() ) {
+ Map.Entry me = (Map.Entry) argEdges.next();
+ RefEdge reArg = (RefEdge) me.getKey();
+ Integer index = (Integer) me.getValue();
+
+ VariableNode vnCaller = (VariableNode) reArg.getSrc();
+ TempDescriptor argCaller = vnCaller.getTempDescriptor();
+
+ TempDescriptor paramCallee = fmCallee.getParameter( index );
+ VariableNode vnCallee = rg.getVariableNodeFromTemp( paramCallee );
+
+ HeapRegionNode hrnDstCaller = reArg.getDst();
+ HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
+ assert hrnDstCallee != null;
+
+ ExistPred pred =
+ ExistPred.factory( argCaller,
+ null,
+ hrnDstCallee.getID(),
+ reArg.getType(),
+ reArg.getField(),
+ null, // state
+ null, // taint
+ true, // out-of-callee-context
+ false // out-of-caller-context
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge reCallee =
+ new RefEdge( vnCallee,
+ hrnDstCallee,
+ reArg.getType(),
+ reArg.getField(),
+ toCalleeContext( reArg.getBeta(),
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ preds,
+ toCalleeContext( reArg.getTaints(),
+ preds )
+ );
+
+ rg.addRefEdge( vnCallee,
+ hrnDstCallee,
+ reCallee
+ );
+ }
+
+ // add in-context edges to callee graph
+ Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
+ while( reItr.hasNext() ) {
+ RefEdge reCaller = reItr.next();
+ RefSrcNode rsnCaller = reCaller.getSrc();
+ assert rsnCaller instanceof HeapRegionNode;
+ HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
+ HeapRegionNode hrnDstCaller = reCaller.getDst();
+
+ HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
+ HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
+ assert hrnSrcCallee != null;
+ assert hrnDstCallee != null;
+
+ ExistPred pred =
+ ExistPred.factory( null,
+ hrnSrcCallee.getID(),
+ hrnDstCallee.getID(),
+ reCaller.getType(),
+ reCaller.getField(),
+ null, // state
+ null, // taint
+ false, // out-of-callee-context
+ false // out-of-caller-context
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge reCallee =
+ new RefEdge( hrnSrcCallee,
+ hrnDstCallee,
+ reCaller.getType(),
+ reCaller.getField(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ preds,
+ TaintSet.factory() // no taints for in-context edges
+ );
+
+ rg.addRefEdge( hrnSrcCallee,
+ hrnDstCallee,
+ reCallee
+ );
+ }
+
+ // add out-of-context edges to callee graph
+ reItr = oocCallerEdges.iterator();
+ while( reItr.hasNext() ) {
+ RefEdge reCaller = reItr.next();
+ RefSrcNode rsnCaller = reCaller.getSrc();
+ HeapRegionNode hrnDstCaller = reCaller.getDst();
+ HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
+ assert hrnDstCallee != null;
+
+ TypeDescriptor oocNodeType;
+ ReachSet oocReach;
+ TempDescriptor oocPredSrcTemp = null;
+ Integer oocPredSrcID = null;
+ boolean outOfCalleeContext;
+ boolean outOfCallerContext;
+
+ if( rsnCaller instanceof VariableNode ) {
+ VariableNode vnCaller = (VariableNode) rsnCaller;
+ oocNodeType = null;
+ oocReach = rsetEmpty;
+ oocPredSrcTemp = vnCaller.getTempDescriptor();
+ outOfCalleeContext = true;
+ outOfCallerContext = false;
+
+ } else {
+ HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
+ assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
+ oocNodeType = hrnSrcCaller.getType();
+ oocReach = hrnSrcCaller.getAlpha();
+ oocPredSrcID = hrnSrcCaller.getID();
+ if( hrnSrcCaller.isOutOfContext() ) {
+ outOfCalleeContext = false;
+ outOfCallerContext = true;
+ } else {
+ outOfCalleeContext = true;
+ outOfCallerContext = false;
+ }
+ }
+
+ ExistPred pred =
+ ExistPred.factory( oocPredSrcTemp,
+ oocPredSrcID,
+ hrnDstCallee.getID(),
+ reCaller.getType(),
+ reCaller.getField(),
+ null,
+ null,
+ outOfCalleeContext,
+ outOfCallerContext
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge oocEdgeExisting =
+ rg.getOutOfContextReferenceTo( hrnDstCallee,
+ oocNodeType,
+ reCaller.getType(),
+ reCaller.getField()
+ );
+
+ if( oocEdgeExisting == null ) {
+ // for consistency, map one out-of-context "identifier"
+ // to one heap region node id, otherwise no convergence
+ String oocid = "oocid"+
+ fmCallee+
+ hrnDstCallee.getIDString()+
+ oocNodeType+
+ reCaller.getType()+
+ reCaller.getField();
+
+ Integer oocHrnID = oocid2hrnid.get( oocid );
+
+ HeapRegionNode hrnCalleeAndOutContext;
+
+ if( oocHrnID == null ) {
+
+ hrnCalleeAndOutContext =
+ rg.createNewHeapRegionNode( null, // ID
+ false, // single object?
+ false, // new summary?
+ true, // out-of-context?
+ oocNodeType,
+ null, // alloc site, shouldn't be used
+ toCalleeContext( oocReach,
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ toCalleeContext( oocReach,
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ preds,
+ "out-of-context"
+ );
+
+ oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
+
+ } else {
+
+ // the mapping already exists, so see if node is there
+ hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
+
+ if( hrnCalleeAndOutContext == null ) {
+ // nope, make it
+ hrnCalleeAndOutContext =
+ rg.createNewHeapRegionNode( oocHrnID, // ID
+ false, // single object?
+ false, // new summary?
+ true, // out-of-context?
+ oocNodeType,
+ null, // alloc site, shouldn't be used
+ toCalleeContext( oocReach,
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ toCalleeContext( oocReach,
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ preds,
+ "out-of-context"
+ );
+
+ } else {
+ // otherwise it is there, so merge reachability
+ hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
+ toCalleeContext( oocReach,
+ preds,
+ oocHrnIdOoc2callee
+ )
+ )
+ );
+ }
+ }
+
+ assert hrnCalleeAndOutContext.reachHasOnlyOOC();
+
+ rg.addRefEdge( hrnCalleeAndOutContext,
+ hrnDstCallee,
+ new RefEdge( hrnCalleeAndOutContext,
+ hrnDstCallee,
+ reCaller.getType(),
+ reCaller.getField(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ preds,
+ toCalleeContext( reCaller.getTaints(),
+ preds )
+ )
+ );
+
+ } else {
+ // the out-of-context edge already exists
+ oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocHrnIdOoc2callee
+ )
+ )
+ );
+
+ oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
+ preds
+ )
+ );
+
+ oocEdgeExisting.setTaints( Canonical.unionORpreds( oocEdgeExisting.getTaints(),
+ toCalleeContext( reCaller.getTaints(),
+ preds
+ )
+ )
+ );
+
+ HeapRegionNode hrnCalleeAndOutContext =
+ (HeapRegionNode) oocEdgeExisting.getSrc();
+ hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
+ toCalleeContext( oocReach,
+ preds,
+ oocHrnIdOoc2callee
+ )
+ )
+ );
+
+ assert hrnCalleeAndOutContext.reachHasOnlyOOC();
+ }
+ }
+
+
+ if( writeDebugDOTs ) {
+ debugGraphPrefix = String.format( "call%03d", debugCallSiteVisitCounter );
+ rg.writeGraph( debugGraphPrefix+"calleeview",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
+ }
+
+ return rg;
+ }
+
+ private static Hashtable<String, Integer> oocid2hrnid =
+ new Hashtable<String, Integer>();
+
+
+ // useful since many graphs writes in the method call debug code
+ private static boolean resolveMethodDebugDOTwriteLabels = true;
+ private static boolean resolveMethodDebugDOTselectTemps = true;
+ private static boolean resolveMethodDebugDOTpruneGarbage = true;
+ private static boolean resolveMethodDebugDOThideReach = true;
+ private static boolean resolveMethodDebugDOThideSubsetReach = true;
+ private static boolean resolveMethodDebugDOThidePreds = true;
+ private static boolean resolveMethodDebugDOThideEdgeTaints = true;
+
+ static String debugGraphPrefix;
+ static int debugCallSiteVisitCounter;
+ static int debugCallSiteVisitStartCapture;
+ static int debugCallSiteNumVisitsToCapture;
+ static boolean debugCallSiteStopAfter;
+
public void
resolveMethodCall( FlatCall fc,
- FlatMethod fm,
+ FlatMethod fmCallee,
ReachGraph rgCallee,
Set<Integer> callerNodeIDsCopiedToCallee,
boolean writeDebugDOTs
) {
-
if( writeDebugDOTs ) {
- try {
- rgCallee.writeGraph( "callee",
- true, false, false, false, true, true );
- writeGraph( "caller00In",
- true, false, false, false, true, true,
- callerNodeIDsCopiedToCallee );
- } catch( IOException e ) {}
+ System.out.println( " Writing out visit "+
+ debugCallSiteVisitCounter+
+ " to debug call site" );
+
+ debugGraphPrefix = String.format( "call%03d",
+ debugCallSiteVisitCounter );
+
+ rgCallee.writeGraph( debugGraphPrefix+"callee",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
+
+ writeGraph( debugGraphPrefix+"caller00In",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
}
+
// method call transfer function steps:
// 1. Use current callee-reachable heap (CRH) to test callee
// predicates and mark what will be coming in.
// 5. Global sweep it.
-
// 1. mark what callee elements have satisfied predicates
Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
new Hashtable<HeapRegionNode, ExistPredSet>();
Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
new Hashtable<RefEdge, ExistPredSet>();
+ Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
+ calleeNode2calleeStatesSatisfied =
+ new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
+
+ Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
+ calleeEdge2calleeStatesSatisfied =
+ new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
+
+ Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
+ calleeEdge2calleeTaintsSatisfied =
+ new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
+
+ Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
+ new Hashtable< RefEdge, Set<RefSrcNode> >();
+
+
Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
while( meItr.hasNext() ) {
Map.Entry me = (Map.Entry) meItr.next();
Integer id = (Integer) me.getKey();
HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
-
+
+ // if a callee element's predicates are satisfied then a set
+ // of CALLER predicates is returned: they are the predicates
+ // that the callee element moved into the caller context
+ // should have, and it is inefficient to find this again later
ExistPredSet predsIfSatis =
hrnCallee.getPreds().isSatisfiedBy( this,
callerNodeIDsCopiedToCallee
);
+
if( predsIfSatis != null ) {
calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
} else {
- // otherwise don't bother looking at edges from this node
+ // otherwise don't bother looking at edges to this node
continue;
}
+
+ // since the node is coming over, find out which reach
+ // states on it should come over, too
+ assert calleeNode2calleeStatesSatisfied.get( hrnCallee ) == null;
+
+ Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState stateCallee = stateItr.next();
+
+ predsIfSatis =
+ stateCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( predsIfSatis != null ) {
+
+ Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
+ calleeNode2calleeStatesSatisfied.get( hrnCallee );
+
+ if( calleeStatesSatisfied == null ) {
+ calleeStatesSatisfied =
+ new Hashtable<ReachState, ExistPredSet>();
+
+ calleeNode2calleeStatesSatisfied.put( hrnCallee, calleeStatesSatisfied );
+ }
+
+ calleeStatesSatisfied.put( stateCallee, predsIfSatis );
+ }
+ }
- Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencees();
+ // then look at edges to the node
+ Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
while( reItr.hasNext() ) {
- RefEdge reCallee = reItr.next();
+ RefEdge reCallee = reItr.next();
+ RefSrcNode rsnCallee = reCallee.getSrc();
+
+ // (caller local variables to in-context heap regions)
+ // have an (out-of-context heap region -> in-context heap region)
+ // abstraction in the callEE, so its true we never need to
+ // look at a (var node -> heap region) edge in callee to bring
+ // those over for the call site transfer, except for the special
+ // case of *RETURN var* -> heap region edges.
+ // What about (param var->heap region)
+ // edges in callee? They are dealt with below this loop.
+
+ if( rsnCallee instanceof VariableNode ) {
+
+ // looking for the return-value variable only
+ VariableNode vnCallee = (VariableNode) rsnCallee;
+ if( vnCallee.getTempDescriptor() != tdReturn ) {
+ continue;
+ }
- ExistPredSet ifDst =
- reCallee.getDst().getPreds().isSatisfiedBy( this,
- callerNodeIDsCopiedToCallee
- );
- if( ifDst == null ) {
- continue;
+ TempDescriptor returnTemp = fc.getReturnTemp();
+ if( returnTemp == null ||
+ !DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
+ ) {
+ continue;
+ }
+
+ // note that the assignment of the return value is to a
+ // variable in the caller which is out-of-context with
+ // respect to the callee
+ VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
+ Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
+ rsnCallers.add( vnLhsCaller );
+ calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
+
+
+ } else {
+ // for HeapRegionNode callee sources...
+
+ // first see if the source is out-of-context, and only
+ // proceed with this edge if we find some caller-context
+ // matches
+ HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
+ boolean matchedOutOfContext = false;
+
+ if( !hrnSrcCallee.isOutOfContext() ) {
+
+ predsIfSatis =
+ hrnSrcCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( predsIfSatis != null ) {
+ calleeNodesSatisfied.put( hrnSrcCallee, predsIfSatis );
+ } else {
+ // otherwise forget this edge
+ continue;
+ }
+
+ } else {
+ // hrnSrcCallee is out-of-context
+
+ assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
+
+ Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
+
+ // is the target node in the caller?
+ HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
+ if( hrnDstCaller == null ) {
+ continue;
+ }
+
+ Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
+ while( reDstItr.hasNext() ) {
+ // the edge and field (either possibly null) must match
+ RefEdge reCaller = reDstItr.next();
+
+ if( !reCaller.typeEquals ( reCallee.getType() ) ||
+ !reCaller.fieldEquals( reCallee.getField() )
+ ) {
+ continue;
+ }
+
+ RefSrcNode rsnCaller = reCaller.getSrc();
+ if( rsnCaller instanceof VariableNode ) {
+
+ // a variable node matches an OOC region with null type
+ if( hrnSrcCallee.getType() != null ) {
+ continue;
+ }
+
+ } else {
+ // otherwise types should match
+ HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
+ if( hrnSrcCallee.getType() == null ) {
+ if( hrnCallerSrc.getType() != null ) {
+ continue;
+ }
+ } else {
+ if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
+ continue;
+ }
+ }
+ }
+
+ rsnCallers.add( rsnCaller );
+ matchedOutOfContext = true;
+ }
+
+ if( !rsnCallers.isEmpty() ) {
+ calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
+ }
+ }
+
+ if( hrnSrcCallee.isOutOfContext() &&
+ !matchedOutOfContext ) {
+ continue;
+ }
}
+
predsIfSatis =
reCallee.getPreds().isSatisfiedBy( this,
callerNodeIDsCopiedToCallee
);
+
if( predsIfSatis != null ) {
calleeEdgesSatisfied.put( reCallee, predsIfSatis );
- }
- }
- }
- // test param -> HRN edges, also
- for( int i = 0; i < fm.numParameters(); ++i ) {
+ // since the edge is coming over, find out which reach
+ // states on it should come over, too
+ assert calleeEdge2calleeStatesSatisfied.get( reCallee ) == null;
- // parameter defined here is the symbol in the callee
- TempDescriptor tdParam = fm.getParameter( i );
- VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
+ stateItr = reCallee.getBeta().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState stateCallee = stateItr.next();
+
+ predsIfSatis =
+ stateCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( predsIfSatis != null ) {
+
+ Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
+ calleeEdge2calleeStatesSatisfied.get( reCallee );
+
+ if( calleeStatesSatisfied == null ) {
+ calleeStatesSatisfied =
+ new Hashtable<ReachState, ExistPredSet>();
+
+ calleeEdge2calleeStatesSatisfied.put( reCallee, calleeStatesSatisfied );
+ }
+
+ calleeStatesSatisfied.put( stateCallee, predsIfSatis );
+ }
+ }
- Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
- while( reItr.hasNext() ) {
- RefEdge reCallee = reItr.next();
+ // since the edge is coming over, find out which taints
+ // on it should come over, too
+ assert calleeEdge2calleeTaintsSatisfied.get( reCallee ) == null;
- ExistPredSet ifDst =
- reCallee.getDst().getPreds().isSatisfiedBy( this,
- callerNodeIDsCopiedToCallee
- );
- if( ifDst == null ) {
- continue;
- }
+ Iterator<Taint> tItr = reCallee.getTaints().iterator();
+ while( tItr.hasNext() ) {
+ Taint tCallee = tItr.next();
- ExistPredSet predsIfSatis =
- reCallee.getPreds().isSatisfiedBy( this,
- callerNodeIDsCopiedToCallee
- );
- if( predsIfSatis != null ) {
- calleeEdgesSatisfied.put( reCallee, predsIfSatis );
- }
- }
- }
+ predsIfSatis =
+ tCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( predsIfSatis != null ) {
+
+ Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
+ calleeEdge2calleeTaintsSatisfied.get( reCallee );
+ if( calleeTaintsSatisfied == null ) {
+ calleeTaintsSatisfied =
+ new Hashtable<Taint, ExistPredSet>();
+ calleeEdge2calleeTaintsSatisfied.put( reCallee, calleeTaintsSatisfied );
+ }
+ calleeTaintsSatisfied.put( tCallee, predsIfSatis );
+ }
+ }
+ }
+ }
+ }
if( writeDebugDOTs ) {
- try {
- writeGraph( "caller20BeforeWipe",
- true, false, false, false, true, true );
- } catch( IOException e ) {}
+ writeGraph( debugGraphPrefix+"caller20BeforeWipe",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
}
HeapRegionNode hrnCaller = id2hrn.get( hrnID );
assert hrnCaller != null;
- // when clearing off nodes, don't eliminate variable
+ // when clearing off nodes, also eliminate variable
// references
- wipeOut( hrnCaller, false );
+ wipeOut( hrnCaller, true );
}
+ // if we are assigning the return value to something, clobber now
+ // as part of the wipe
+ TempDescriptor returnTemp = fc.getReturnTemp();
+ if( returnTemp != null &&
+ DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
+ ) {
+
+ VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
+ clearRefEdgesFrom( vnLhsCaller, null, null, true );
+ }
+
+
if( writeDebugDOTs ) {
- try {
- writeGraph( "caller30BeforeAddingNodes",
- true, false, false, false, true, true );
- } catch( IOException e ) {}
+ writeGraph( debugGraphPrefix+"caller30BeforeAddingNodes",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
}
+
+
// 3. callee elements with satisfied preds come in, note that
// the mapping of elements satisfied to preds is like this:
// A callee element EE has preds EEp that are satisfied by
HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
ExistPredSet preds = (ExistPredSet) me.getValue();
+ // TODO: I think its true that the current implementation uses
+ // the type of the OOC region and the predicates OF THE EDGE from
+ // it to link everything up in caller context, so that's why we're
+ // skipping this... maybe that's a sillier way to do it?
if( hrnCallee.isOutOfContext() ) {
continue;
}
createNewHeapRegionNode( hrnIDshadow, // id or null to generate a new one
hrnCallee.isSingleObject(), // single object?
hrnCallee.isNewSummary(), // summary?
- hrnCallee.isFlagged(), // flagged?
false, // out-of-context?
hrnCallee.getType(), // type
hrnCallee.getAllocSite(), // allocation site
- hrnCallee.getInherent(), // inherent reach
+ toCallerContext( hrnCallee.getInherent(),
+ calleeNode2calleeStatesSatisfied.get( hrnCallee ) ), // inherent reach
null, // current reach
predsEmpty, // predicates
hrnCallee.getDescription() // description
assert hrnCaller.isWiped();
}
- // TODO: alpha should be some rewritten version of callee in caller context
- hrnCaller.setAlpha( rsetEmpty );
+ hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
+ calleeNode2calleeStatesSatisfied.get( hrnCallee )
+ )
+ );
hrnCaller.setPreds( preds );
}
+
+
if( writeDebugDOTs ) {
- try {
- writeGraph( "caller31BeforeAddingEdges",
- true, false, false, false, true, true );
- } catch( IOException e ) {}
+ writeGraph( debugGraphPrefix+"caller31BeforeAddingEdges",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
}
- // 3.b) callee -> callee edges
+ // set these up during the next procedure so after
+ // the caller has all of its nodes and edges put
+ // back together we can propagate the callee's
+ // reach changes backwards into the caller graph
+ HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
+
+ Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
+ new Hashtable<RefEdge, ChangeSet>();
+
+
+ // 3.b) callee -> callee edges AND out-of-context -> callee
+ // which includes return temp -> callee edges now, too
satisItr = calleeEdgesSatisfied.entrySet().iterator();
while( satisItr.hasNext() ) {
Map.Entry me = (Map.Entry) satisItr.next();
RefEdge reCallee = (RefEdge) me.getKey();
ExistPredSet preds = (ExistPredSet) me.getValue();
- RefSrcNode rsnCallee = reCallee.getSrc();
- RefSrcNode rsnCaller;
-
- if( rsnCallee instanceof VariableNode ) {
- continue;
- /*
- VariableNode vnCallee = (VariableNode) rsnCallee;
- TempDescriptor tdParam = vnCallee.getTempDescriptor();
- TempDescriptor tdArg = fc.getArgMatchingParam( fm,
- tdParam );
- if( tdArg == null ) {
- // this means the variable isn't a parameter, its local
- // to the callee so we ignore it in call site transfer
- continue;
- }
-
- System.out.println( "going with "+tdParam+" to "+tdArg );
+ HeapRegionNode hrnDstCallee = reCallee.getDst();
+ AllocSite asDst = hrnDstCallee.getAllocSite();
+ allocSites.add( asDst );
- rsnCaller = this.getVariableNodeFromTemp( tdArg );
- */
- } else {
- HeapRegionNode hrnSrcCallee = (HeapRegionNode) reCallee.getSrc();
+ Integer hrnIDDstShadow =
+ asDst.getShadowIDfromID( hrnDstCallee.getID() );
+
+ HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
+ assert hrnDstCaller != null;
+
+
+ RefSrcNode rsnCallee = reCallee.getSrc();
- AllocSite asSrc = hrnSrcCallee.getAllocSite();
- allocSites.add( asSrc );
+ Set<RefSrcNode> rsnCallers =
+ new HashSet<RefSrcNode>();
+
+ Set<RefSrcNode> oocCallers =
+ calleeEdges2oocCallerSrcMatches.get( reCallee );
- Integer hrnIDSrcShadow = asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
- rsnCaller = id2hrn.get( hrnIDSrcShadow );
+ if( rsnCallee instanceof HeapRegionNode ) {
+ HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
+ if( hrnCalleeSrc.isOutOfContext() ) {
+ assert oocCallers != null;
+ }
}
+
- assert rsnCaller != null;
-
- HeapRegionNode hrnDstCallee = reCallee.getDst();
+ if( oocCallers == null ) {
+ // there are no out-of-context matches, so it's
+ // either a param/arg var or one in-context heap region
+ if( rsnCallee instanceof VariableNode ) {
+ // variable -> node in the callee should only
+ // come into the caller if its from a param var
+ VariableNode vnCallee = (VariableNode) rsnCallee;
+ TempDescriptor tdParam = vnCallee.getTempDescriptor();
+ TempDescriptor tdArg = fc.getArgMatchingParam( fmCallee,
+ tdParam );
+ if( tdArg == null ) {
+ // this means the variable isn't a parameter, its local
+ // to the callee so we ignore it in call site transfer
+ // shouldn't this NEVER HAPPEN?
+ assert false;
+ }
- AllocSite asDst = hrnDstCallee.getAllocSite();
- allocSites.add( asDst );
+ rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
- Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
+ } else {
+ // otherwise source is in context, one region
+
+ HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
- HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
- assert hrnDstCaller != null;
-
- // TODO: beta rewrites
- RefEdge reCaller = new RefEdge( rsnCaller,
- hrnDstCaller,
- reCallee.getType(),
- reCallee.getField(),
- rsetEmpty,
- preds
- );
+ // translate an in-context node to shadow
+ AllocSite asSrc = hrnSrcCallee.getAllocSite();
+ allocSites.add( asSrc );
+
+ Integer hrnIDSrcShadow =
+ asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
- // look to see if an edge with same field exists
- // and merge with it, otherwise just add the edge
- RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
- reCallee.getType(),
- reCallee.getField()
- );
- if( edgeExisting != null ) {
- edgeExisting.setBeta(
- Canonical.union( edgeExisting.getBeta(),
- reCaller.getBeta()
- )
- );
- edgeExisting.setPreds(
- Canonical.join( edgeExisting.getPreds(),
- reCaller.getPreds()
- )
- );
-
- } else {
- addRefEdge( rsnCaller, hrnDstCaller, reCaller );
+ HeapRegionNode hrnSrcCallerShadow =
+ this.id2hrn.get( hrnIDSrcShadow );
+
+ assert hrnSrcCallerShadow != null;
+
+ rsnCallers.add( hrnSrcCallerShadow );
+ }
+
+ } else {
+ // otherwise we have a set of out-of-context srcs
+ // that should NOT be translated to shadow nodes
+ assert !oocCallers.isEmpty();
+ rsnCallers.addAll( oocCallers );
}
-
- }
+ // now make all caller edges we've identified from
+ // this callee edge with a satisfied predicate
+ assert !rsnCallers.isEmpty();
+ Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
+ while( rsnItr.hasNext() ) {
+ RefSrcNode rsnCaller = rsnItr.next();
+
+ RefEdge reCaller = new RefEdge( rsnCaller,
+ hrnDstCaller,
+ reCallee.getType(),
+ reCallee.getField(),
+ toCallerContext( reCallee.getBeta(),
+ calleeEdge2calleeStatesSatisfied.get( reCallee ) ),
+ preds,
+ toCallerContext( reCallee.getTaints(),
+ calleeEdge2calleeTaintsSatisfied.get( reCallee ) )
+ );
- if( writeDebugDOTs ) {
- try {
- writeGraph( "caller33BeforeResolveOutOfContextEdges",
- true, false, false, false, true, true );
- } catch( IOException e ) {}
- }
+ ChangeSet cs = ChangeSet.factory();
+ Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
+ while( rsItr.hasNext() ) {
+ ReachState state = rsItr.next();
+ ExistPredSet predsPreCallee = state.getPreds();
- // 3.c) resolve out-of-context -> callee edges
+ if( state.isEmpty() ) {
+ continue;
+ }
+ Iterator<ExistPred> predItr = predsPreCallee.iterator();
+ while( predItr.hasNext() ) {
+ ExistPred pred = predItr.next();
+ ReachState old = pred.ne_state;
+ if( old == null ) {
+ old = rstateEmpty;
+ }
+ cs = Canonical.add( cs,
+ ChangeTuple.factory( old,
+ state
+ )
+ );
+ }
+ }
- if( writeDebugDOTs ) {
- try {
- writeGraph( "caller35BeforeAssignReturnValue",
- true, false, false, false, true, true );
- } catch( IOException e ) {}
+ // we're just going to use the convenient "merge-if-exists"
+ // edge call below, but still take a separate look if there
+ // is an existing caller edge to build change sets properly
+ if( !cs.isEmpty() ) {
+ RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
+ reCallee.getType(),
+ reCallee.getField()
+ );
+ if( edgeExisting != null ) {
+ ChangeSet csExisting = edgePlannedChanges.get( edgeExisting );
+ if( csExisting == null ) {
+ csExisting = ChangeSet.factory();
+ }
+ edgePlannedChanges.put( edgeExisting,
+ Canonical.union( csExisting,
+ cs
+ )
+ );
+ } else {
+ edgesForPropagation.add( reCaller );
+ assert !edgePlannedChanges.containsKey( reCaller );
+ edgePlannedChanges.put( reCaller, cs );
+ }
+ }
+
+ // then add new caller edge or merge
+ addEdgeOrMergeWithExisting( reCaller );
+ }
}
-
- // 3.d) handle return value assignment if needed
- TempDescriptor returnTemp = fc.getReturnTemp();
- if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
- VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
- clearRefEdgesFrom( vnLhsCaller, null, null, true );
- VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
- Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
- while( reCalleeItr.hasNext() ) {
- RefEdge reCallee = reCalleeItr.next();
- HeapRegionNode hrnDstCallee = reCallee.getDst();
-
- // some edge types are not possible return values when we can
- // see what type variable we are assigning it to
- if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
- System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
- reCallee+" for return temp "+returnTemp );
- // prune
- continue;
- }
- AllocSite asDst = hrnDstCallee.getAllocSite();
- allocSites.add( asDst );
- Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
+ if( writeDebugDOTs ) {
+ writeGraph( debugGraphPrefix+"caller38propagateReach",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
+ }
+
+ // propagate callee reachability changes to the rest
+ // of the caller graph edges
+ HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
+
+ propagateTokensOverEdges( edgesForPropagation, // source edges
+ edgePlannedChanges, // map src edge to change set
+ edgesUpdated ); // list of updated edges
+
+ // commit beta' (beta<-betaNew)
+ Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
+ while( edgeItr.hasNext() ) {
+ edgeItr.next().applyBetaNew();
+ }
- HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
- assert hrnDstCaller != null;
- TypeDescriptor tdNewEdge =
- mostSpecificType( reCallee.getType(),
- hrnDstCallee.getType(),
- hrnDstCaller.getType()
- );
- RefEdge reCaller = new RefEdge( vnLhsCaller,
- hrnDstCaller,
- tdNewEdge,
- null,
- rsetEmpty,
- predsTrue
- );
- addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
- }
- }
if( writeDebugDOTs ) {
- try {
- writeGraph( "caller40BeforeShadowMerge",
- true, false, false, false, true, true );
- } catch( IOException e ) {}
+ writeGraph( debugGraphPrefix+"caller40BeforeShadowMerge",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
}
}
+
+
+
+
if( writeDebugDOTs ) {
- try {
- writeGraph( "caller50BeforeGlobalSweep",
- true, false, false, false, true, true );
- } catch( IOException e ) {}
+ writeGraph( debugGraphPrefix+"caller45BeforeUnshadow",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
+ }
+
+
+ Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
+ while( itrAllHRNodes.hasNext() ) {
+ Map.Entry me = (Map.Entry) itrAllHRNodes.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ hrn.setAlpha( unshadow( hrn.getAlpha() ) );
+
+ Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
+ while( itrEdges.hasNext() ) {
+ RefEdge re = itrEdges.next();
+ re.setBeta( unshadow( re.getBeta() ) );
+ }
+ }
+
+
+
+
+ if( writeDebugDOTs ) {
+ writeGraph( debugGraphPrefix+"caller50BeforeGlobalSweep",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
}
// 5.
- globalSweep();
+ if( !DISABLE_GLOBAL_SWEEP ) {
+ globalSweep();
+ }
-
if( writeDebugDOTs ) {
- try {
- writeGraph( "caller90AfterTransfer",
- true, false, false, false, true, true );
- } catch( IOException e ) {}
+ writeGraph( debugGraphPrefix+"caller90AfterTransfer",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideReach,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThidePreds,
+ resolveMethodDebugDOThideEdgeTaints );
}
}
public void globalSweep() {
// boldB is part of the phase 1 sweep
- Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
+ // it has an in-context table and an out-of-context table
+ Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
+ new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
+
+ Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
- // visit every heap region to initialize alphaNew and calculate boldB
+ // visit every heap region to initialize alphaNew and betaNew,
+ // and make a map of every hrnID to the source nodes it should
+ // propagate forward from. In-context flagged hrnID's propagate
+ // from only the in-context node they name, but out-of-context
+ // ID's may propagate from several out-of-context nodes
+ Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
+ new Hashtable< Integer, Set<HeapRegionNode> >();
+
+ Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
+ new Hashtable< Integer, Set<HeapRegionNode> >();
+
+
Iterator itrHrns = id2hrn.entrySet().iterator();
while( itrHrns.hasNext() ) {
Map.Entry me = (Map.Entry) itrHrns.next();
assert rsetEmpty.equals( edge.getBetaNew() );
}
- // calculate boldB for this flagged node
+ // make a mapping of IDs to heap regions they propagate from
if( hrn.isFlagged() ) {
-
- Hashtable<RefEdge, ReachSet> boldB_f =
- new Hashtable<RefEdge, ReachSet>();
-
- Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
+ assert !hrn.isOutOfContext();
+ assert !icID2srcs.containsKey( hrn.getID() );
+
+ // in-context flagged node IDs simply propagate from the
+ // node they name
+ Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
+ srcs.add( hrn );
+ icID2srcs.put( hrn.getID(), srcs );
+ }
+
+ if( hrn.isOutOfContext() ) {
+ assert !hrn.isFlagged();
+
+ // the reachability states on an out-of-context
+ // node are not really important (combinations of
+ // IDs or arity)--what matters is that the states
+ // specify which nodes this out-of-context node
+ // stands in for. For example, if the state [17?, 19*]
+ // appears on the ooc node, it may serve as a source
+ // for node 17? and a source for node 19.
+ Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
+
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+ assert rt.isOutOfContext();
+
+ Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
+ if( srcs == null ) {
+ srcs = new HashSet<HeapRegionNode>();
+ }
+ srcs.add( hrn );
+ oocID2srcs.put( rt.getHrnID(), srcs );
+ }
+ }
+ }
+ }
- // initial boldB_f constraints
- Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
- while( itrRees.hasNext() ) {
- RefEdge edge = itrRees.next();
+ // calculate boldB for all hrnIDs identified by the above
+ // node traversal, propagating from every source
+ while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
- assert !boldB.containsKey( edge );
- boldB_f.put( edge, edge.getBeta() );
+ Integer hrnID;
+ Set<HeapRegionNode> srcs;
+ boolean inContext;
- assert !workSetEdges.contains( edge );
- workSetEdges.add( edge );
- }
+ if( !icID2srcs.isEmpty() ) {
+ Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
+ hrnID = (Integer) me.getKey();
+ srcs = (Set<HeapRegionNode>) me.getValue();
+ inContext = true;
+ icID2srcs.remove( hrnID );
- // enforce the boldB_f constraint at edges until we reach a fixed point
- while( !workSetEdges.isEmpty() ) {
- RefEdge edge = workSetEdges.iterator().next();
- workSetEdges.remove( edge );
-
- Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
- while( itrPrime.hasNext() ) {
- RefEdge edgePrime = itrPrime.next();
+ } else {
+ assert !oocID2srcs.isEmpty();
+
+ Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
+ hrnID = (Integer) me.getKey();
+ srcs = (Set<HeapRegionNode>) me.getValue();
+ inContext = false;
+ oocID2srcs.remove( hrnID );
+ }
+
+
+ Hashtable<RefEdge, ReachSet> boldB_f =
+ new Hashtable<RefEdge, ReachSet>();
+
+ Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
+
+ Iterator<HeapRegionNode> hrnItr = srcs.iterator();
+ while( hrnItr.hasNext() ) {
+ HeapRegionNode hrn = hrnItr.next();
- ReachSet prevResult = boldB_f.get( edgePrime );
- ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
+ assert workSetEdges.isEmpty();
+
+ // initial boldB_f constraints
+ Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
+ while( itrRees.hasNext() ) {
+ RefEdge edge = itrRees.next();
+
+ assert !boldB_f.containsKey( edge );
+ boldB_f.put( edge, edge.getBeta() );
+
+ assert !workSetEdges.contains( edge );
+ workSetEdges.add( edge );
+ }
+
+ // enforce the boldB_f constraint at edges until we reach a fixed point
+ while( !workSetEdges.isEmpty() ) {
+ RefEdge edge = workSetEdges.iterator().next();
+ workSetEdges.remove( edge );
+
+ Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
+ while( itrPrime.hasNext() ) {
+ RefEdge edgePrime = itrPrime.next();
+
+ ReachSet prevResult = boldB_f.get( edgePrime );
+ ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
edgePrime.getBeta()
);
-
- if( prevResult == null ||
- Canonical.union( prevResult,
- intersection ).size() > prevResult.size() ) {
-
- if( prevResult == null ) {
- boldB_f.put( edgePrime,
- Canonical.union( edgePrime.getBeta(),
- intersection
- )
+
+ if( prevResult == null ||
+ Canonical.unionORpreds( prevResult,
+ intersection ).size()
+ > prevResult.size()
+ ) {
+
+ if( prevResult == null ) {
+ boldB_f.put( edgePrime,
+ Canonical.unionORpreds( edgePrime.getBeta(),
+ intersection
+ )
);
- } else {
- boldB_f.put( edgePrime,
- Canonical.union( prevResult,
- intersection
- )
+ } else {
+ boldB_f.put( edgePrime,
+ Canonical.unionORpreds( prevResult,
+ intersection
+ )
);
- }
- workSetEdges.add( edgePrime );
- }
- }
- }
-
- boldB.put( hrnID, boldB_f );
- }
+ }
+ workSetEdges.add( edgePrime );
+ }
+ }
+ }
+ }
+
+ if( inContext ) {
+ boldBic.put( hrnID, boldB_f );
+ } else {
+ boldBooc.put( hrnID, boldB_f );
+ }
}
Integer hrnID = (Integer) me.getKey();
HeapRegionNode hrn = (HeapRegionNode) me.getValue();
- // create the inherent hrnID from a flagged region
- // as an exception to removal below
- ReachTuple rtException =
- ReachTuple.factory( hrnID,
- !hrn.isSingleObject(),
- ReachTuple.ARITY_ONE
- );
+ // out-of-context nodes don't participate in the
+ // global sweep, they serve as sources for the pass
+ // performed above
+ if( hrn.isOutOfContext() ) {
+ continue;
+ }
+
+ // the inherent states of a region are the exception
+ // to removal as the global sweep prunes
+ ReachTuple rtException = ReachTuple.factory( hrnID,
+ !hrn.isSingleObject(),
+ ReachTuple.ARITY_ONE,
+ false // out-of-context
+ );
ChangeSet cts = ChangeSet.factory();
}
}
- // does boldB_ttOld allow this hrnID?
+ // does boldB allow this hrnID?
boolean foundState = false;
Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
while( incidentEdgeItr.hasNext() ) {
RefEdge incidentEdge = incidentEdgeItr.next();
- // if it isn't allowed, mark for removal
- Integer idOld = rtOld.getHrnID();
- assert id2hrn.containsKey( idOld );
- Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
- ReachSet boldB_ttOld_incident = B.get( incidentEdge );
- if( boldB_ttOld_incident != null &&
- boldB_ttOld_incident.contains( stateOld ) ) {
- foundState = true;
- }
+ Hashtable<RefEdge, ReachSet> B;
+ if( rtOld.isOutOfContext() ) {
+ B = boldBooc.get( rtOld.getHrnID() );
+ } else {
+
+ if( !id2hrn.containsKey( rtOld.getHrnID() ) ) {
+ // let symbols not in the graph get pruned
+ break;
+ }
+
+ B = boldBic.get( rtOld.getHrnID() );
+ }
+
+ if( B != null ) {
+ ReachSet boldB_rtOld_incident = B.get( incidentEdge );
+ if( boldB_rtOld_incident != null &&
+ boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
+ ) {
+ foundState = true;
+ }
+ }
}
-
+
if( !foundState ) {
markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
}
// if there is nothing marked, just move on
if( markedHrnIDs.isEmpty() ) {
- hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
- stateOld
- )
+ hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
+ stateOld
+ )
);
continue;
}
ReachTuple rtOld = rtItr.next();
if( !markedHrnIDs.containsTuple( rtOld ) ) {
- statePruned = Canonical.union( statePruned, rtOld );
+ statePruned = Canonical.add( statePruned, rtOld );
}
}
assert !stateOld.equals( statePruned );
- hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
- statePruned
- )
+ hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
+ statePruned
+ )
);
ChangeTuple ct = ChangeTuple.factory( stateOld,
statePruned
);
- cts = Canonical.union( cts, ct );
+ cts = Canonical.add( cts, ct );
}
// throw change tuple set on all incident edges
Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
while( nodeItr.hasNext() ) {
HeapRegionNode hrn = nodeItr.next();
- hrn.applyAlphaNew();
+
+ // as mentioned above, out-of-context nodes only serve
+ // as sources of reach states for the sweep, not part
+ // of the changes
+ if( hrn.isOutOfContext() ) {
+ assert hrn.getAlphaNew().equals( rsetEmpty );
+ } else {
+ hrn.applyAlphaNew();
+ }
+
Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
while( itrRes.hasNext() ) {
res.add( itrRes.next() );
edgePrime.getBetaNew()
);
- if( Canonical.union( prevResult,
- intersection
- ).size() > prevResult.size() ) {
+ if( Canonical.unionORpreds( prevResult,
+ intersection
+ ).size()
+ > prevResult.size()
+ ) {
+
edge.setBetaNew(
- Canonical.union( prevResult,
- intersection
- )
+ Canonical.unionORpreds( prevResult,
+ intersection
+ )
);
edgeWorkSet.add( edge );
}
}
+ // a useful assertion for debugging:
+ // every in-context tuple on any edge or
+ // any node should name a node that is
+ // part of the graph
+ public boolean inContextTuplesInGraph() {
- ////////////////////////////////////////////////////
- // high-level merge operations
- ////////////////////////////////////////////////////
- public void merge_sameMethodContext( ReachGraph rg ) {
- // when merging two graphs that abstract the heap
- // of the same method context, we just call the
- // basic merge operation
- merge( rg );
+ Iterator hrnItr = id2hrn.entrySet().iterator();
+ while( hrnItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) hrnItr.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ {
+ Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
+
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+
+ if( !rt.isOutOfContext() ) {
+ if( !id2hrn.containsKey( rt.getHrnID() ) ) {
+ System.out.println( rt.getHrnID()+" is missing" );
+ return false;
+ }
+ }
+ }
+ }
+ }
+
+ Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
+ while( edgeItr.hasNext() ) {
+ RefEdge edge = edgeItr.next();
+
+ Iterator<ReachState> stateItr = edge.getBeta().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
+
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+
+ if( !rt.isOutOfContext() ) {
+ if( !id2hrn.containsKey( rt.getHrnID() ) ) {
+ System.out.println( rt.getHrnID()+" is missing" );
+ return false;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ return true;
+ }
+
+
+ // another useful assertion for debugging
+ public boolean noEmptyReachSetsInGraph() {
+
+ Iterator hrnItr = id2hrn.entrySet().iterator();
+ while( hrnItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) hrnItr.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ if( !hrn.isOutOfContext() &&
+ !hrn.isWiped() &&
+ hrn.getAlpha().isEmpty()
+ ) {
+ System.out.println( "!!! "+hrn+" has an empty ReachSet !!!" );
+ return false;
+ }
+
+ Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
+ while( edgeItr.hasNext() ) {
+ RefEdge edge = edgeItr.next();
+
+ if( edge.getBeta().isEmpty() ) {
+ System.out.println( "!!! "+edge+" has an empty ReachSet !!!" );
+ return false;
+ }
+ }
+ }
+
+ return true;
}
- public void merge_diffMethodContext( ReachGraph rg ) {
- // when merging graphs for abstract heaps in
- // different method contexts we should:
- // 1) age the allocation sites?
- merge( rg );
+
+ public boolean everyReachStateWTrue() {
+
+ Iterator hrnItr = id2hrn.entrySet().iterator();
+ while( hrnItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) hrnItr.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ {
+ Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
+
+ if( !state.getPreds().equals( predsTrue ) ) {
+ return false;
+ }
+ }
+ }
+
+ Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
+ while( edgeItr.hasNext() ) {
+ RefEdge edge = edgeItr.next();
+
+ Iterator<ReachState> stateItr = edge.getBeta().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
+
+ if( !state.getPreds().equals( predsTrue ) ) {
+ return false;
+ }
+ }
+ }
+ }
+
+ return true;
}
+
+
+
////////////////////////////////////////////////////
// in merge() and equals() methods the suffix A
mergeNodes ( rg );
mergeRefEdges ( rg );
mergeAllocSites( rg );
+ mergeAccessibleSet( rg );
}
protected void mergeNodes( ReachGraph rg ) {
// so make the new reachability set a union of the
// nodes' reachability sets
HeapRegionNode hrnB = id2hrn.get( idA );
- hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
+ hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
hrnA.getAlpha()
)
);
- // if hrnB is already dirty or hrnA is dirty,
- // the hrnB should end up dirty: TODO
- /*
- if( !hrnA.isClean() ) {
- hrnB.setIsClean( false );
+ hrnB.setPreds( Canonical.join( hrnB.getPreds(),
+ hrnA.getPreds()
+ )
+ );
+
+
+
+ if( !hrnA.equals( hrnB ) ) {
+ rg.writeGraph( "graphA" );
+ this.writeGraph( "graphB" );
+ throw new Error( "flagged not matching" );
}
- */
+
+
+
}
}
// just replace this beta set with the union
assert edgeToMerge != null;
edgeToMerge.setBeta(
- Canonical.union( edgeToMerge.getBeta(),
- edgeA.getBeta()
- )
+ Canonical.unionORpreds( edgeToMerge.getBeta(),
+ edgeA.getBeta()
+ )
);
- // TODO: what?
- /*
- if( !edgeA.isClean() ) {
- edgeToMerge.setIsClean( false );
- }
- */
+ edgeToMerge.setPreds(
+ Canonical.join( edgeToMerge.getPreds(),
+ edgeA.getPreds()
+ )
+ );
+ edgeToMerge.setTaints(
+ Canonical.union( edgeToMerge.getTaints(),
+ edgeA.getTaints()
+ )
+ );
}
}
}
// so merge their reachability sets
else {
// just replace this beta set with the union
- edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
+ edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
edgeA.getBeta()
)
);
- // TODO: what?
- /*
- if( !edgeA.isClean() ) {
- edgeToMerge.setIsClean( false );
- }
- */
+ edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
+ edgeA.getPreds()
+ )
+ );
+ edgeToMerge.setTaints(
+ Canonical.union( edgeToMerge.getTaints(),
+ edgeA.getTaints()
+ )
+ );
}
}
}
protected void mergeAllocSites( ReachGraph rg ) {
allocSites.addAll( rg.allocSites );
}
+
+ protected void mergeAccessibleSet( ReachGraph rg ){
+ // inaccesible status is prior to accessible status
+
+ Set<TempDescriptor> varsToMerge=rg.getAccessibleVar();
+ Set<TempDescriptor> varsRemoved=new HashSet<TempDescriptor>();
+
+ for (Iterator iterator = accessibleVars.iterator(); iterator.hasNext();) {
+ TempDescriptor accessibleVar = (TempDescriptor) iterator.next();
+ if(!varsToMerge.contains(accessibleVar)){
+ varsRemoved.add(accessibleVar);
+ }
+ }
+
+ accessibleVars.removeAll(varsRemoved);
+
+ }
+
+
+
+ static boolean dbgEquals = false;
// it is necessary in the equals() member functions
public boolean equals( ReachGraph rg ) {
if( rg == null ) {
+ if( dbgEquals ) {
+ System.out.println( "rg is null" );
+ }
return false;
}
if( !areHeapRegionNodesEqual( rg ) ) {
+ if( dbgEquals ) {
+ System.out.println( "hrn not equal" );
+ }
return false;
}
if( !areVariableNodesEqual( rg ) ) {
+ if( dbgEquals ) {
+ System.out.println( "vars not equal" );
+ }
return false;
}
if( !areRefEdgesEqual( rg ) ) {
+ if( dbgEquals ) {
+ System.out.println( "edges not equal" );
+ }
+ return false;
+ }
+
+ if( !accessibleVars.equals( rg.accessibleVars) ){
return false;
}
return true;
}
-
protected boolean areVariableNodesEqual( ReachGraph rg ) {
return false;
}
+ if( !areallREinAandBequal( rg, this ) ) {
+ return false;
+ }
+
return true;
}
}
+ // can be used to assert monotonicity
+ static public boolean isNoSmallerThan( ReachGraph rgA,
+ ReachGraph rgB ) {
+
+ //System.out.println( "*** Asking if A is no smaller than B ***" );
+
+
+ Iterator iA = rgA.id2hrn.entrySet().iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
+
+ if( !rgB.id2hrn.containsKey( idA ) ) {
+ System.out.println( " regions smaller" );
+ return false;
+ }
+
+ //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
+ /* NOT EQUALS, NO SMALLER THAN!
+ if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
+ System.out.println( " regions smaller" );
+ return false;
+ }
+ */
+ }
+
+ // this works just fine, no smaller than
+ if( !areallVNinAalsoinBandequal( rgA, rgB ) ) {
+ System.out.println( " vars smaller:" );
+ System.out.println( " A:"+rgA.td2vn.keySet() );
+ System.out.println( " B:"+rgB.td2vn.keySet() );
+ return false;
+ }
+
+
+ iA = rgA.id2hrn.entrySet().iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
+
+ Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
+ while( reItr.hasNext() ) {
+ RefEdge edgeA = reItr.next();
+ RefSrcNode rsnA = edgeA.getSrc();
+
+ // we already checked that nodes were present
+ HeapRegionNode hrnB = rgB.id2hrn.get( hrnA.getID() );
+ assert hrnB != null;
+
+ RefSrcNode rsnB;
+ if( rsnA instanceof VariableNode ) {
+ VariableNode vnA = (VariableNode) rsnA;
+ rsnB = rgB.td2vn.get( vnA.getTempDescriptor() );
+
+ } else {
+ HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
+ rsnB = rgB.id2hrn.get( hrnSrcA.getID() );
+ }
+ assert rsnB != null;
+
+ RefEdge edgeB = rsnB.getReferenceTo( hrnB,
+ edgeA.getType(),
+ edgeA.getField()
+ );
+ if( edgeB == null ) {
+ System.out.println( " edges smaller:" );
+ return false;
+ }
+
+ // REMEMBER, IS NO SMALLER THAN
+ /*
+ System.out.println( " edges smaller" );
+ return false;
+ }
+ */
+
+ }
+ }
+
+
+ return true;
+ }
+
+
+
+
// this analysis no longer has the "match anything"
// type which was represented by null
+ // the default signature for quick-and-dirty debugging
+ public void writeGraph( String graphName ) {
+ writeGraph( graphName,
+ true, // write labels
+ true, // label select
+ true, // prune garbage
+ false, // hide reachability
+ true, // hide subset reachability
+ true, // hide predicates
+ true, // hide edge taints
+ null // in-context boundary
+ );
+ }
+
public void writeGraph( String graphName,
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers,
+ boolean hideReachability,
boolean hideSubsetReachability,
+ boolean hidePredicates,
boolean hideEdgeTaints
- ) throws java.io.IOException {
+ ) {
writeGraph( graphName,
writeLabels,
labelSelect,
pruneGarbage,
- writeReferencers,
+ hideReachability,
hideSubsetReachability,
+ hidePredicates,
hideEdgeTaints,
null );
}
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers,
+ boolean hideReachability,
boolean hideSubsetReachability,
+ boolean hidePredicates,
boolean hideEdgeTaints,
Set<Integer> callerNodeIDsCopiedToCallee
- ) throws java.io.IOException {
+ ) {
- // remove all non-word characters from the graph name so
- // the filename and identifier in dot don't cause errors
- graphName = graphName.replaceAll( "[\\W]", "" );
-
- BufferedWriter bw =
- new BufferedWriter( new FileWriter( graphName+".dot" ) );
-
- bw.write( "digraph "+graphName+" {\n" );
-
+ try {
+ // remove all non-word characters from the graph name so
+ // the filename and identifier in dot don't cause errors
+ graphName = graphName.replaceAll( "[\\W]", "" );
- // this is an optional step to form the callee-reachable
- // "cut-out" into a DOT cluster for visualization
- if( callerNodeIDsCopiedToCallee != null ) {
+ BufferedWriter bw =
+ new BufferedWriter( new FileWriter( graphName+".dot" ) );
- bw.write( " subgraph cluster0 {\n" );
- bw.write( " color=blue;\n" );
+ bw.write( "digraph "+graphName+" {\n" );
- Iterator i = id2hrn.entrySet().iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ // this is an optional step to form the callee-reachable
+ // "cut-out" into a DOT cluster for visualization
+ if( callerNodeIDsCopiedToCallee != null ) {
- if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
- bw.write( " "+hrn.toString()+
- hrn.toStringDOT( hideSubsetReachability )+
- ";\n" );
+ bw.write( " subgraph cluster0 {\n" );
+ bw.write( " color=blue;\n" );
+
+ Iterator i = id2hrn.entrySet().iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry) i.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+ if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
+ bw.write( " "+
+ hrn.toString()+
+ hrn.toStringDOT( hideReachability,
+ hideSubsetReachability,
+ hidePredicates )+
+ ";\n" );
+ }
}
+
+ bw.write( " }\n" );
}
-
- bw.write( " }\n" );
- }
-
-
- Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
-
- // then visit every heap region node
- Iterator i = id2hrn.entrySet().iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- HeapRegionNode hrn = (HeapRegionNode) me.getValue();
-
- // only visit nodes worth writing out--for instance
- // not every node at an allocation is referenced
- // (think of it as garbage-collected), etc.
- if( !pruneGarbage ||
- (hrn.isFlagged() && hrn.getID() > 0) ||
- hrn.getDescription().startsWith( "param" ) ||
- hrn.isOutOfContext()
- ) {
-
- if( !visited.contains( hrn ) ) {
- traverseHeapRegionNodes( hrn,
- bw,
- null,
- visited,
- writeReferencers,
- hideSubsetReachability,
- hideEdgeTaints,
- callerNodeIDsCopiedToCallee );
- }
- }
- }
-
- bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
-
-
- // then visit every label node, useful for debugging
- if( writeLabels ) {
- i = td2vn.entrySet().iterator();
+
+
+ Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
+
+ // then visit every heap region node
+ Iterator i = id2hrn.entrySet().iterator();
while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- VariableNode vn = (VariableNode) me.getValue();
-
- if( labelSelect ) {
- String labelStr = vn.getTempDescriptorString();
- if( labelStr.startsWith("___temp") ||
- labelStr.startsWith("___dst") ||
- labelStr.startsWith("___srctmp") ||
- labelStr.startsWith("___neverused")
- ) {
- continue;
- }
- }
+ Map.Entry me = (Map.Entry) i.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
- Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
- while( heapRegionsItr.hasNext() ) {
- RefEdge edge = heapRegionsItr.next();
- HeapRegionNode hrn = edge.getDst();
+ // only visit nodes worth writing out--for instance
+ // not every node at an allocation is referenced
+ // (think of it as garbage-collected), etc.
+ if( !pruneGarbage ||
+ hrn.isOutOfContext() ||
+ (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
+ ) {
- if( pruneGarbage && !visited.contains( hrn ) ) {
+ if( !visited.contains( hrn ) ) {
traverseHeapRegionNodes( hrn,
bw,
null,
visited,
- writeReferencers,
+ hideReachability,
hideSubsetReachability,
+ hidePredicates,
hideEdgeTaints,
callerNodeIDsCopiedToCallee );
}
+ }
+ }
+
+ bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
+
+
+ // then visit every label node, useful for debugging
+ if( writeLabels ) {
+ i = td2vn.entrySet().iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry) i.next();
+ VariableNode vn = (VariableNode) me.getValue();
+
+ if( labelSelect ) {
+ String labelStr = vn.getTempDescriptorString();
+ if( labelStr.startsWith( "___temp" ) ||
+ labelStr.startsWith( "___dst" ) ||
+ labelStr.startsWith( "___srctmp" ) ||
+ labelStr.startsWith( "___neverused" )
+ ) {
+ continue;
+ }
+ }
+
+ Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
+ while( heapRegionsItr.hasNext() ) {
+ RefEdge edge = heapRegionsItr.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ if( !visited.contains( hrn ) ) {
+ traverseHeapRegionNodes( hrn,
+ bw,
+ null,
+ visited,
+ hideReachability,
+ hideSubsetReachability,
+ hidePredicates,
+ hideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
+ }
- bw.write( " "+vn.toString()+
- " -> "+hrn.toString()+
- edge.toStringDOT( hideSubsetReachability, "" )+
- ";\n" );
+ bw.write( " "+vn.toString()+
+ " -> "+hrn.toString()+
+ edge.toStringDOT( hideReachability,
+ hideSubsetReachability,
+ hidePredicates,
+ hideEdgeTaints,
+ "" )+
+ ";\n" );
+ }
}
}
- }
- bw.write( "}\n" );
- bw.close();
+ bw.write( "}\n" );
+ bw.close();
+
+ } catch( IOException e ) {
+ throw new Error( "Error writing out DOT graph "+graphName );
+ }
}
- protected void traverseHeapRegionNodes( HeapRegionNode hrn,
- BufferedWriter bw,
- TempDescriptor td,
- Set<HeapRegionNode> visited,
- boolean writeReferencers,
- boolean hideSubsetReachability,
- boolean hideEdgeTaints,
- Set<Integer> callerNodeIDsCopiedToCallee
- ) throws java.io.IOException {
+ protected void
+ traverseHeapRegionNodes( HeapRegionNode hrn,
+ BufferedWriter bw,
+ TempDescriptor td,
+ Set<HeapRegionNode> visited,
+ boolean hideReachability,
+ boolean hideSubsetReachability,
+ boolean hidePredicates,
+ boolean hideEdgeTaints,
+ Set<Integer> callerNodeIDsCopiedToCallee
+ ) throws java.io.IOException {
if( visited.contains( hrn ) ) {
return;
if( callerNodeIDsCopiedToCallee == null ||
!callerNodeIDsCopiedToCallee.contains( hrn.getID() )
) {
- bw.write( " "+hrn.toString()+
- hrn.toStringDOT( hideSubsetReachability )+
+ bw.write( " "+
+ hrn.toString()+
+ hrn.toStringDOT( hideReachability,
+ hideSubsetReachability,
+ hidePredicates )+
";\n" );
}
) {
bw.write( " "+hrn.toString()+
" -> "+hrnChild.toString()+
- edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
+ edge.toStringDOT( hideReachability,
+ hideSubsetReachability,
+ hidePredicates,
+ hideEdgeTaints,
+ ",color=blue" )+
";\n");
} else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
) {
bw.write( " "+hrn.toString()+
" -> "+hrnChild.toString()+
- edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
+ edge.toStringDOT( hideReachability,
+ hideSubsetReachability,
+ hidePredicates,
+ hideEdgeTaints,
+ ",color=blue,style=dashed" )+
";\n");
} else {
bw.write( " "+hrn.toString()+
" -> "+hrnChild.toString()+
- edge.toStringDOT( hideSubsetReachability, "" )+
+ edge.toStringDOT( hideReachability,
+ hideSubsetReachability,
+ hidePredicates,
+ hideEdgeTaints,
+ "" )+
";\n");
}
} else {
bw.write( " "+hrn.toString()+
" -> "+hrnChild.toString()+
- edge.toStringDOT( hideSubsetReachability, "" )+
+ edge.toStringDOT( hideReachability,
+ hideSubsetReachability,
+ hidePredicates,
+ hideEdgeTaints,
+ "" )+
";\n");
}
bw,
td,
visited,
- writeReferencers,
+ hideReachability,
hideSubsetReachability,
+ hidePredicates,
hideEdgeTaints,
callerNodeIDsCopiedToCallee );
}
}
+
+
+
+
+
+ public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
+
+ Set<HeapRegionNode> exhibitProofState =
+ new HashSet<HeapRegionNode>();
+
+ Iterator hrnItr = id2hrn.entrySet().iterator();
+ while( hrnItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) hrnItr.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ ReachSet intersection =
+ Canonical.intersection( proofOfSharing,
+ hrn.getAlpha()
+ );
+ if( !intersection.isEmpty() ) {
+ assert !hrn.isOutOfContext();
+ exhibitProofState.add( hrn );
+ }
+ }
+
+ return exhibitProofState;
+ }
+
+
+ public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
+ HeapRegionNode hrn2) {
+ assert hrn1 != null;
+ assert hrn2 != null;
+
+ assert !hrn1.isOutOfContext();
+ assert !hrn2.isOutOfContext();
+
+ assert belongsToThis( hrn1 );
+ assert belongsToThis( hrn2 );
+
+ assert !hrn1.getID().equals( hrn2.getID() );
+
+
+ // then get the various tokens for these heap regions
+ ReachTuple h1 =
+ ReachTuple.factory( hrn1.getID(),
+ !hrn1.isSingleObject(), // multi?
+ ReachTuple.ARITY_ONE,
+ false ); // ooc?
+
+ ReachTuple h1star = null;
+ if( !hrn1.isSingleObject() ) {
+ h1star =
+ ReachTuple.factory( hrn1.getID(),
+ !hrn1.isSingleObject(),
+ ReachTuple.ARITY_ZEROORMORE,
+ false );
+ }
+
+ ReachTuple h2 =
+ ReachTuple.factory( hrn2.getID(),
+ !hrn2.isSingleObject(),
+ ReachTuple.ARITY_ONE,
+ false );
+
+ ReachTuple h2star = null;
+ if( !hrn2.isSingleObject() ) {
+ h2star =
+ ReachTuple.factory( hrn2.getID(),
+ !hrn2.isSingleObject(),
+ ReachTuple.ARITY_ZEROORMORE,
+ false );
+ }
+
+ // then get the merged beta of all out-going edges from these heap
+ // regions
+
+ ReachSet beta1 = ReachSet.factory();
+ Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
+ }
+
+ ReachSet beta2 = ReachSet.factory();
+ itrEdge = hrn2.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
+ }
+
+ ReachSet proofOfSharing = ReachSet.factory();
+
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta1.getStatesWithBoth( h1, h2 )
+ );
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta2.getStatesWithBoth( h1, h2 )
+ );
+
+ if( !hrn1.isSingleObject() ) {
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta1.getStatesWithBoth( h1star, h2 )
+ );
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta2.getStatesWithBoth( h1star, h2 )
+ );
+ }
+
+ if( !hrn2.isSingleObject() ) {
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta1.getStatesWithBoth( h1, h2star )
+ );
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta2.getStatesWithBoth( h1, h2star )
+ );
+ }
+
+ if( !hrn1.isSingleObject() &&
+ !hrn2.isSingleObject()
+ ) {
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta1.getStatesWithBoth( h1star, h2star )
+ );
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta2.getStatesWithBoth( h1star, h2star )
+ );
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if( !proofOfSharing.isEmpty() ) {
+ common = findCommonReachableNodes( proofOfSharing );
+ if( !DISABLE_STRONG_UPDATES &&
+ !DISABLE_GLOBAL_SWEEP
+ ) {
+ assert !common.isEmpty();
+ }
+ }
+
+ return common;
+ }
+
+ // this version of the above method checks whether there is sharing
+ // among the objects in a summary node
+ public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
+ assert hrn != null;
+ assert hrn.isNewSummary();
+ assert !hrn.isOutOfContext();
+ assert belongsToThis( hrn );
+
+ ReachTuple hstar =
+ ReachTuple.factory( hrn.getID(),
+ true, // multi
+ ReachTuple.ARITY_ZEROORMORE,
+ false ); // ooc
+
+ // then get the merged beta of all out-going edges from
+ // this heap region
+
+ ReachSet beta = ReachSet.factory();
+ Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta = Canonical.unionORpreds(beta, edge.getBeta());
+ }
+
+ ReachSet proofOfSharing = ReachSet.factory();
+ proofOfSharing =
+ Canonical.unionORpreds( proofOfSharing,
+ beta.getStatesWithBoth( hstar, hstar )
+ );
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if( !proofOfSharing.isEmpty() ) {
+ common = findCommonReachableNodes( proofOfSharing );
+ if( !DISABLE_STRONG_UPDATES &&
+ !DISABLE_GLOBAL_SWEEP
+ ) {
+ assert !common.isEmpty();
+ }
+ }
+
+ return common;
+ }
+
+
+ public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
+ Integer paramIndex1,
+ Integer paramIndex2) {
+
+ // get parameter's heap regions
+ TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
+ assert this.hasVariable( paramTemp1 );
+ VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
+
+
+ if( !(paramVar1.getNumReferencees() == 1) ) {
+ System.out.println( "\n fm="+fm+"\n param="+paramTemp1 );
+ writeGraph( "whatup" );
+ }
+
+
+ assert paramVar1.getNumReferencees() == 1;
+ RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
+ HeapRegionNode hrnParam1 = paramEdge1.getDst();
+
+ TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
+ assert this.hasVariable( paramTemp2 );
+ VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
+
+ if( !(paramVar2.getNumReferencees() == 1) ) {
+ System.out.println( "\n fm="+fm+"\n param="+paramTemp2 );
+ writeGraph( "whatup" );
+ }
+
+ assert paramVar2.getNumReferencees() == 1;
+ RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
+ HeapRegionNode hrnParam2 = paramEdge2.getDst();
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
+
+ return common;
+ }
+
+ public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
+ Integer paramIndex,
+ AllocSite as) {
+
+ // get parameter's heap regions
+ TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
+ assert this.hasVariable( paramTemp );
+ VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
+ assert paramVar.getNumReferencees() == 1;
+ RefEdge paramEdge = paramVar.iteratorToReferencees().next();
+ HeapRegionNode hrnParam = paramEdge.getDst();
+
+ // get summary node
+ HeapRegionNode hrnSummary=null;
+ if(id2hrn.containsKey(as.getSummary())){
+ // if summary node doesn't exist, ignore this case
+ hrnSummary = id2hrn.get(as.getSummary());
+ assert hrnSummary != null;
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if(hrnSummary!=null){
+ common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
+ }
+
+ // check for other nodes
+ for (int i = 0; i < as.getAllocationDepth(); ++i) {
+
+ assert id2hrn.containsKey(as.getIthOldest(i));
+ HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
+ assert hrnIthOldest != null;
+
+ common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
+
+ }
+
+ return common;
+ }
+
+ public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
+ AllocSite as2) {
+
+ // get summary node 1's alpha
+ Integer idSum1 = as1.getSummary();
+ HeapRegionNode hrnSum1=null;
+ if(id2hrn.containsKey(idSum1)){
+ hrnSum1 = id2hrn.get(idSum1);
+ }
+
+ // get summary node 2's alpha
+ Integer idSum2 = as2.getSummary();
+ HeapRegionNode hrnSum2=null;
+ if(id2hrn.containsKey(idSum2)){
+ hrnSum2 = id2hrn.get(idSum2);
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
+ common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
+ }
+
+ if(hrnSum1!=null){
+ // ask if objects from this summary share among each other
+ common.addAll(mayReachSharedObjects(hrnSum1));
+ }
+
+ // check sum2 against alloc1 nodes
+ if(hrnSum2!=null){
+ for (int i = 0; i < as1.getAllocationDepth(); ++i) {
+ Integer idI1 = as1.getIthOldest(i);
+ assert id2hrn.containsKey(idI1);
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+ assert hrnI1 != null;
+ common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
+ }
+
+ // also ask if objects from this summary share among each other
+ common.addAll(mayReachSharedObjects(hrnSum2));
+ }
+
+ // check sum1 against alloc2 nodes
+ for (int i = 0; i < as2.getAllocationDepth(); ++i) {
+ Integer idI2 = as2.getIthOldest(i);
+ assert id2hrn.containsKey(idI2);
+ HeapRegionNode hrnI2 = id2hrn.get(idI2);
+ assert hrnI2 != null;
+
+ if(hrnSum1!=null){
+ common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
+ }
+
+ // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
+ for (int j = 0; j < as1.getAllocationDepth(); ++j) {
+ Integer idI1 = as1.getIthOldest(j);
+
+ // if these are the same site, don't look for the same token, no
+ // alias.
+ // different tokens of the same site could alias together though
+ if (idI1.equals(idI2)) {
+ continue;
+ }
+
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+
+ common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
+ }
+ }
+
+ return common;
+ }
+
+ public void addAccessibleVar(TempDescriptor td){
+ accessibleVars.add(td);
+ }
+
+ public Set<TempDescriptor> getAccessibleVar(){
+ return accessibleVars;
+ }
+
+ public void clearAccessibleVarSet(){
+ accessibleVars.clear();
+ }
+
}
projects / IRC.git / blobdiff