// 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___" );
// some frequently used reachability constants
- protected static final ReachState rstateEmpty = new ReachState().makeCanonical();
- protected static final ReachSet rsetEmpty = new ReachSet().makeCanonical();
- protected static final ReachSet rsetWithEmptyState = new ReachSet( rstateEmpty ).makeCanonical();
+ 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 );
+
// from DisjointAnalysis for convenience
protected static int allocationDepth = -1;
}
+ // 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
boolean isSingleObject,
boolean isNewSummary,
boolean isFlagged,
- boolean isClean,
boolean isOutOfContext,
TypeDescriptor type,
AllocSite allocSite,
ReachSet inherent,
ReachSet alpha,
+ ExistPredSet preds,
String description
) {
if( inherent == null ) {
if( markForAnalysis ) {
- inherent = new ReachSet(
- new ReachTuple( id,
- !isSingleObject,
- ReachTuple.ARITY_ONE
- ).makeCanonical()
- ).makeCanonical();
+ inherent =
+ ReachSet.factory(
+ ReachState.factory(
+ ReachTuple.factory( id,
+ !isSingleObject,
+ ReachTuple.ARITY_ONE,
+ false // out-of-context
+ )
+ )
+ );
} else {
inherent = rsetWithEmptyState;
}
if( alpha == null ) {
alpha = inherent;
}
+
+ if( preds == null ) {
+ // TODO: do this right? For out-of-context nodes?
+ preds = ExistPredSet.factory();
+ }
HeapRegionNode hrn = new HeapRegionNode( id,
isSingleObject,
markForAnalysis,
isNewSummary,
- isClean,
isOutOfContext,
typeToUse,
allocSite,
inherent,
alpha,
+ preds,
description );
id2hrn.put( id, hrn );
return hrn;
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
+ // this check to prevent that
+ assert referencer.getReferenceTo( referencee,
+ edge.getType(),
+ edge.getField()
+ ) == null;
referencer.addReferencee( edge );
referencee.addReferencer( edge );
}
}
+ protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
+ assert referencee != null;
+
+ // 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
+ Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
+ while( i.hasNext() ) {
+ RefEdge edge = i.next();
+ RefSrcNode referencer = edge.getSrc();
+ if( !(referencer instanceof VariableNode) ) {
+ removeRefEdge( referencer,
+ referencee,
+ edge.getType(),
+ edge.getField() );
+ }
+ }
+ }
+
////////////////////////////////////////////////////
//
TypeDescriptor tdNewEdge =
mostSpecificType( edgeHrn.getType(),
hrnHrn.getType()
- );
+ );
RefEdge edgeNew = new RefEdge( lnX,
hrnHrn,
tdNewEdge,
null,
- false,
- betaY.intersection( betaHrn )
+ Canonical.intersection( betaY, betaHrn ),
+ predsTrue
);
- addRefEdge( lnX, hrnHrn, edgeNew );
+ addRefEdge( lnX, hrnHrn, edgeNew );
}
}
}
// anytime you might remove edges between heap regions
- // you must global sweep to clean up broken reachability
+ // you must global sweep to clean up broken reachability
if( !impossibleEdges.isEmpty() ) {
if( !DISABLE_GLOBAL_SWEEP ) {
globalSweep();
}
- }
+ }
}
RefEdge edgeX = itrXhrn.next();
HeapRegionNode hrnX = edgeX.getDst();
ReachSet betaX = edgeX.getBeta();
- ReachSet R = hrnX.getAlpha().intersection( edgeX.getBeta() );
+ ReachSet R = Canonical.intersection( hrnX.getAlpha(),
+ edgeX.getBeta()
+ );
Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
while( itrYhrn.hasNext() ) {
// propagate tokens over nodes starting from hrnSrc, and it will
// take care of propagating back up edges from any touched nodes
- ChangeSet Cy = O.unionUpArityToChangeSet( R );
+ ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
// then propagate back just up the edges from hrn
- ChangeSet Cx = R.unionUpArityToChangeSet(O);
+ ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
hrnY,
tdNewEdge,
f.getSymbol(),
- false,
- edgeY.getBeta().pruneBy( hrnX.getAlpha() )
+ Canonical.pruneBy( edgeY.getBeta(),
+ hrnX.getAlpha()
+ ),
+ predsTrue
);
// look to see if an edge with same field exists
if( edgeExisting != null ) {
edgeExisting.setBeta(
- edgeExisting.getBeta().union( edgeNew.getBeta() )
+ Canonical.union( edgeExisting.getBeta(),
+ edgeNew.getBeta()
+ )
);
- // we touched this edge in the current context
- // so dirty it
- edgeExisting.setIsClean( false );
+ edgeExisting.setPreds(
+ Canonical.join( edgeExisting.getPreds(),
+ edgeNew.getPreds()
+ )
+ );
} else {
addRefEdge( hrnX, hrnY, edgeNew );
}
// if there was a strong update, make sure to improve
- // reachability with a global sweep
+ // reachability with a global sweep
if( strongUpdate || !impossibleEdges.isEmpty() ) {
if( !DISABLE_GLOBAL_SWEEP ) {
globalSweep();
}
- }
+ }
}
hrnNewest, // dest
type, // type
null, // field name
- false, // is initial param
- hrnNewest.getAlpha() // beta
+ hrnNewest.getAlpha(), // beta
+ predsTrue // predicates
);
addRefEdge( lnX, hrnNewest, edgeNew );
// return non-null heap regions.
public void age( AllocSite as ) {
- // aging adds this allocation site to the graph's
- // list of sites that exist in the graph, or does
- // nothing if the site is already in the list
+ // keep track of allocation sites that are represented
+ // in this graph for efficiency with other operations
allocSites.add( as );
- // get the summary node for the allocation site in the context
- // of this particular reachability graph
- HeapRegionNode hrnSummary = getSummaryNode( as );
+ // if there is a k-th oldest node, it merges into
+ // the summary node
+ Integer idK = as.getOldest();
+ if( id2hrn.containsKey( idK ) ) {
+ HeapRegionNode hrnK = id2hrn.get( idK );
- // merge oldest node into summary
- Integer idK = as.getOldest();
- HeapRegionNode hrnK = id2hrn.get( idK );
- mergeIntoSummary( hrnK, hrnSummary );
+ // retrieve the summary node, or make it
+ // from scratch
+ HeapRegionNode hrnSummary = getSummaryNode( as, false );
+
+ mergeIntoSummary( hrnK, hrnSummary );
+ }
// move down the line of heap region nodes
// clobbering the ith and transferring all references
- // to and from i-1 to node i. Note that this clobbers
- // the oldest node (hrnK) that was just merged into
- // the summary
+ // to and from i-1 to node i.
for( int i = allocationDepth - 1; i > 0; --i ) {
- // move references from the i-1 oldest to the ith oldest
- Integer idIth = as.getIthOldest( i );
- HeapRegionNode hrnI = id2hrn.get( idIth );
- Integer idImin1th = as.getIthOldest( i - 1 );
- HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
+ // only do the transfer if the i-1 node exists
+ Integer idImin1th = as.getIthOldest( i - 1 );
+ if( id2hrn.containsKey( idImin1th ) ) {
+ HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
+ if( hrnImin1.isWiped() ) {
+ // there is no info on this node, just skip
+ continue;
+ }
+
+ // either retrieve or make target of transfer
+ HeapRegionNode hrnI = getIthNode( as, i, false );
+
+ transferOnto( hrnImin1, hrnI );
+ }
- transferOnto( hrnImin1, hrnI );
}
// as stated above, the newest node should have had its
// references moved over to the second oldest, so we wipe newest
// in preparation for being the new object to assign something to
- Integer id0th = as.getIthOldest( 0 );
- HeapRegionNode hrn0 = id2hrn.get( id0th );
- assert hrn0 != null;
-
- // clear all references in and out of newest node
- clearRefEdgesFrom( hrn0, null, null, true );
- clearRefEdgesTo ( hrn0, null, null, true );
-
+ HeapRegionNode hrn0 = getIthNode( as, 0, false );
+ wipeOut( hrn0, true );
// now tokens in reachability sets need to "age" also
Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
while( itrEdges.hasNext() ) {
- ageTokens(as, itrEdges.next() );
+ ageTuplesFrom( as, itrEdges.next() );
}
}
Map.Entry me = (Map.Entry) itrAllHRNodes.next();
HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
- ageTokens( as, hrnToAge );
+ ageTuplesFrom( as, hrnToAge );
Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
while( itrEdges.hasNext() ) {
- ageTokens( as, itrEdges.next() );
+ ageTuplesFrom( as, itrEdges.next() );
}
}
// after tokens have been aged, reset newest node's reachability
+ // and a brand new node has a "true" predicate
hrn0.setAlpha( hrn0.getInherent() );
+ hrn0.setPreds( predsTrue );
}
- protected HeapRegionNode getSummaryNode( AllocSite as ) {
+ // either retrieve or create the needed heap region node
+ protected HeapRegionNode getSummaryNode( AllocSite as,
+ boolean shadow ) {
+
+ Integer idSummary;
+ if( shadow ) {
+ idSummary = as.getSummaryShadow();
+ } else {
+ idSummary = as.getSummary();
+ }
- Integer idSummary = as.getSummary();
HeapRegionNode hrnSummary = id2hrn.get( idSummary );
- // If this is null then we haven't touched this allocation site
- // in the context of the current reachability graph, so allocate
- // heap region nodes appropriate for the entire allocation site.
- // This should only happen once per reachability graph per allocation site,
- // and a particular integer id can be used to locate the heap region
- // in different reachability graphs that represents the same part of an
- // allocation site.
if( hrnSummary == null ) {
boolean hasFlags = false;
}
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?
- false, // clean?
false, // out-of-context?
as.getType(), // type
as, // allocation site
null, // inherent reach
null, // current reach
+ predsEmpty, // predicates
strDesc // description
- );
-
- for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- Integer idIth = as.getIthOldest( i );
- assert !id2hrn.containsKey( idIth );
- strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
- createNewHeapRegionNode( idIth, // id or null to generate a new one
- true, // single object?
- false, // summary?
- hasFlags, // flagged?
- false, // clean?
- false, // out-of-context?
- as.getType(), // type
- as, // allocation site
- null, // inherent reach
- null, // current reach
- strDesc // description
- );
- }
+ );
}
-
+
return hrnSummary;
}
+ // either retrieve or create the needed heap region node
+ protected HeapRegionNode getIthNode( AllocSite as,
+ Integer i,
+ boolean shadow ) {
- protected HeapRegionNode getShadowSummaryNode( AllocSite as ) {
-
- Integer idShadowSummary = as.getSummaryShadow();
- HeapRegionNode hrnShadowSummary = id2hrn.get( idShadowSummary );
-
- if( hrnShadowSummary == null ) {
+ Integer idIth;
+ if( shadow ) {
+ idIth = as.getIthOldestShadow( i );
+ } else {
+ idIth = as.getIthOldest( i );
+ }
+
+ HeapRegionNode hrnIth = id2hrn.get( idIth );
+
+ if( hrnIth == null ) {
boolean hasFlags = false;
if( as.getType().isClass() ) {
- hasFlags = as.getType().getClassDesc().hasFlags();
+ hasFlags = as.getType().getClassDesc().hasFlags();
}
-
+
if( as.getFlag() ){
hasFlags = as.getFlag();
}
- String strDesc = as+"\\n"+as.getType()+"\\nshadowSum";
- hrnShadowSummary =
- createNewHeapRegionNode( idShadowSummary, // id or null to generate a new one
- false, // single object?
- true, // summary?
- hasFlags, // flagged?
- false, // clean?
- false, // out-of-context?
- as.getType(), // type
- as, // allocation site
- null, // inherent reach
- null, // current reach
- strDesc // description
- );
-
- for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- Integer idShadowIth = as.getIthOldestShadow( i );
- assert !id2hrn.containsKey( idShadowIth );
- strDesc = as+"\\n"+as.getType()+"\\n"+i+" shadow";
- createNewHeapRegionNode( idShadowIth, // id or null to generate a new one
- true, // single object?
- false, // summary?
- hasFlags, // flagged?
- false, // clean?
- false, // out-of-context?
- as.getType(), // type
- as, // allocation site
- null, // inherent reach
- null, // current reach
- strDesc // description
- );
+ 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
+ null, // inherent reach
+ null, // current reach
+ predsEmpty, // predicates
+ strDesc // description
+ );
}
- return hrnShadowSummary;
+ return hrnIth;
}
HeapRegionNode hrnSummary ) {
assert hrnSummary.isNewSummary();
+ // assert that these nodes belong to THIS graph
+ assert belongsToThis( hrn );
+ assert belongsToThis( hrnSummary );
+
+ assert hrn != hrnSummary;
+
// transfer references _from_ hrn over to hrnSummary
Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
while( itrReferencee.hasNext() ) {
if( edgeSummary == null ) {
// the merge is trivial, nothing to be done
+ addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
+
} else {
// otherwise an edge from the referencer to hrnSummary exists already
// and the edge referencer->hrn should be merged with it
- edgeMerged.setBeta( edgeMerged.getBeta().union( edgeSummary.getBeta() ) );
+ edgeSummary.setBeta(
+ Canonical.union( edgeMerged.getBeta(),
+ edgeSummary.getBeta()
+ )
+ );
+ edgeSummary.setPreds(
+ Canonical.join( edgeMerged.getPreds(),
+ edgeSummary.getPreds()
+ )
+ );
}
-
- addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
}
// next transfer references _to_ hrn over to hrnSummary
if( edgeSummary == null ) {
// the merge is trivial, nothing to be done
+ addRefEdge( onReferencer, hrnSummary, edgeMerged );
+
} else {
// otherwise an edge from the referencer to alpha_S exists already
// and the edge referencer->alpha_K should be merged with it
- edgeMerged.setBeta( edgeMerged.getBeta().union( edgeSummary.getBeta() ) );
+ edgeSummary.setBeta(
+ Canonical.union( edgeMerged.getBeta(),
+ edgeSummary.getBeta()
+ )
+ );
+ edgeSummary.setPreds(
+ Canonical.join( edgeMerged.getPreds(),
+ edgeSummary.getPreds()
+ )
+ );
}
-
- addRefEdge( onReferencer, hrnSummary, edgeMerged );
}
// then merge hrn reachability into hrnSummary
- hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrn.getAlpha() ) );
+ hrnSummary.setAlpha(
+ Canonical.union( hrnSummary.getAlpha(),
+ hrn.getAlpha()
+ )
+ );
+
+ hrnSummary.setPreds(
+ Canonical.join( hrnSummary.getPreds(),
+ hrn.getPreds()
+ )
+ );
+
+ // and afterward, this node is gone
+ wipeOut( hrn, true );
}
protected void transferOnto( HeapRegionNode hrnA,
HeapRegionNode hrnB ) {
- // clear references in and out of node b
- clearRefEdgesFrom( hrnB, null, null, true );
- clearRefEdgesTo ( hrnB, null, null, true );
+ assert belongsToThis( hrnA );
+ assert belongsToThis( hrnB );
+ assert hrnA != hrnB;
+
+ // 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();
HeapRegionNode hrnReferencee = edge.getDst();
RefEdge edgeNew = edge.copy();
edgeNew.setSrc( hrnB );
+ edgeNew.setDst( hrnReferencee );
addRefEdge( hrnB, hrnReferencee, edgeNew );
}
Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
while( itrReferencer.hasNext() ) {
- RefEdge edge = itrReferencer.next();
- RefSrcNode onReferencer = edge.getSrc();
- RefEdge edgeNew = edge.copy();
+ 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 with hrnA's
+ // replace hrnB reachability and preds with hrnA's
hrnB.setAlpha( hrnA.getAlpha() );
+ hrnB.setPreds( hrnA.getPreds() );
+
+ // after transfer, wipe out source
+ wipeOut( hrnA, true );
+ }
+
+
+ // the purpose of this method is to conceptually "wipe out"
+ // a heap region from the graph--purposefully not called REMOVE
+ // because the node is still hanging around in the graph, just
+ // not mechanically connected or have any reach or predicate
+ // information on it anymore--lots of ops can use this
+ protected void wipeOut( HeapRegionNode hrn,
+ boolean wipeVariableReferences ) {
+
+ assert belongsToThis( hrn );
+
+ clearRefEdgesFrom( hrn, null, null, true );
+
+ if( wipeVariableReferences ) {
+ clearRefEdgesTo( hrn, null, null, true );
+ } else {
+ clearNonVarRefEdgesTo( hrn );
+ }
+
+ hrn.setAlpha( rsetEmpty );
+ hrn.setPreds( predsEmpty );
}
- protected void ageTokens( AllocSite as, RefEdge edge ) {
- edge.setBeta( edge.getBeta().ageTokens( as ) );
+ protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
+ edge.setBeta(
+ Canonical.ageTuplesFrom( edge.getBeta(),
+ as
+ )
+ );
}
- protected void ageTokens( AllocSite as, HeapRegionNode hrn ) {
- hrn.setAlpha( hrn.getAlpha().ageTokens( as ) );
+ protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
+ hrn.setAlpha(
+ Canonical.ageTuplesFrom( hrn.getAlpha(),
+ as
+ )
+ );
}
- protected void propagateTokensOverNodes(
- HeapRegionNode nPrime,
- ChangeSet c0,
- HashSet<HeapRegionNode> nodesWithNewAlpha,
- HashSet<RefEdge> edgesWithNewBeta ) {
+ protected void propagateTokensOverNodes( HeapRegionNode nPrime,
+ ChangeSet c0,
+ HashSet<HeapRegionNode> nodesWithNewAlpha,
+ HashSet<RefEdge> edgesWithNewBeta ) {
HashSet<HeapRegionNode> todoNodes
= new HashSet<HeapRegionNode>();
- todoNodes.add(nPrime);
-
+ todoNodes.add( nPrime );
+
HashSet<RefEdge> todoEdges
= new HashSet<RefEdge>();
-
+
Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
= new Hashtable<HeapRegionNode, ChangeSet>();
- nodePlannedChanges.put(nPrime, c0);
+ nodePlannedChanges.put( nPrime, c0 );
Hashtable<RefEdge, ChangeSet> edgePlannedChanges
= new Hashtable<RefEdge, ChangeSet>();
// first propagate change sets everywhere they can go
while( !todoNodes.isEmpty() ) {
HeapRegionNode n = todoNodes.iterator().next();
- ChangeSet C = nodePlannedChanges.get(n);
+ ChangeSet C = nodePlannedChanges.get( n );
Iterator<RefEdge> referItr = n.iteratorToReferencers();
while( referItr.hasNext() ) {
RefEdge edge = referItr.next();
- todoEdges.add(edge);
+ todoEdges.add( edge );
- if( !edgePlannedChanges.containsKey(edge) ) {
- edgePlannedChanges.put(edge, new ChangeSet().makeCanonical() );
+ if( !edgePlannedChanges.containsKey( edge ) ) {
+ edgePlannedChanges.put( edge,
+ ChangeSet.factory()
+ );
}
- edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
+ edgePlannedChanges.put( edge,
+ Canonical.union( edgePlannedChanges.get( edge ),
+ C
+ )
+ );
}
Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
while( refeeItr.hasNext() ) {
- RefEdge edgeF = refeeItr.next();
+ RefEdge edgeF = refeeItr.next();
HeapRegionNode m = edgeF.getDst();
- ChangeSet changesToPass = new ChangeSet().makeCanonical();
+ ChangeSet changesToPass = ChangeSet.factory();
Iterator<ChangeTuple> itrCprime = C.iterator();
while( itrCprime.hasNext() ) {
ChangeTuple c = itrCprime.next();
if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
- changesToPass = changesToPass.union(c);
+ changesToPass = Canonical.union( changesToPass, c );
}
}
if( !changesToPass.isEmpty() ) {
- if( !nodePlannedChanges.containsKey(m) ) {
- nodePlannedChanges.put(m, new ChangeSet().makeCanonical() );
+ if( !nodePlannedChanges.containsKey( m ) ) {
+ nodePlannedChanges.put( m, ChangeSet.factory() );
}
- ChangeSet currentChanges = nodePlannedChanges.get(m);
+ ChangeSet currentChanges = nodePlannedChanges.get( m );
- if( !changesToPass.isSubset(currentChanges) ) {
+ if( !changesToPass.isSubset( currentChanges ) ) {
- nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
- todoNodes.add(m);
+ nodePlannedChanges.put( m,
+ Canonical.union( currentChanges,
+ changesToPass
+ )
+ );
+ todoNodes.add( m );
}
}
}
- todoNodes.remove(n);
+ todoNodes.remove( n );
}
// then apply all of the changes for each node at once
while( itrMap.hasNext() ) {
Map.Entry me = (Map.Entry) itrMap.next();
HeapRegionNode n = (HeapRegionNode) me.getKey();
- ChangeSet C = (ChangeSet) me.getValue();
+ ChangeSet C = (ChangeSet) me.getValue();
// this propagation step is with respect to one change,
// so we capture the full change from the old alpha:
- ReachSet localDelta = n.getAlpha().applyChangeSet( C, true );
-
+ ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
+ C,
+ true
+ );
// 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( n.getAlphaNew().union( localDelta ) );
+ n.setAlphaNew( Canonical.union( n.getAlphaNew(),
+ localDelta
+ )
+ );
nodesWithNewAlpha.add( n );
}
- propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
+ propagateTokensOverEdges( todoEdges,
+ edgePlannedChanges,
+ edgesWithNewBeta
+ );
}
- protected void propagateTokensOverEdges(
- HashSet <RefEdge> todoEdges,
- Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
- HashSet <RefEdge> edgesWithNewBeta ) {
-
+ protected void propagateTokensOverEdges( HashSet <RefEdge> todoEdges,
+ Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
+ HashSet <RefEdge> edgesWithNewBeta ) {
+
// first propagate all change tuples everywhere they can go
while( !todoEdges.isEmpty() ) {
RefEdge edgeE = todoEdges.iterator().next();
- todoEdges.remove(edgeE);
+ todoEdges.remove( edgeE );
- if( !edgePlannedChanges.containsKey(edgeE) ) {
- edgePlannedChanges.put(edgeE, new ChangeSet().makeCanonical() );
+ if( !edgePlannedChanges.containsKey( edgeE ) ) {
+ edgePlannedChanges.put( edgeE,
+ ChangeSet.factory()
+ );
}
- ChangeSet C = edgePlannedChanges.get(edgeE);
+ ChangeSet C = edgePlannedChanges.get( edgeE );
- ChangeSet changesToPass = new ChangeSet().makeCanonical();
+ ChangeSet changesToPass = ChangeSet.factory();
Iterator<ChangeTuple> itrC = C.iterator();
while( itrC.hasNext() ) {
ChangeTuple c = itrC.next();
if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
- changesToPass = changesToPass.union(c);
+ changesToPass = Canonical.union( changesToPass, c );
}
}
- RefSrcNode onSrc = edgeE.getSrc();
+ RefSrcNode rsn = edgeE.getSrc();
- if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
- HeapRegionNode n = (HeapRegionNode) onSrc;
+ if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
+ HeapRegionNode n = (HeapRegionNode) rsn;
Iterator<RefEdge> referItr = n.iteratorToReferencers();
while( referItr.hasNext() ) {
RefEdge edgeF = referItr.next();
- if( !edgePlannedChanges.containsKey(edgeF) ) {
- edgePlannedChanges.put(edgeF, new ChangeSet().makeCanonical() );
+ if( !edgePlannedChanges.containsKey( edgeF ) ) {
+ edgePlannedChanges.put( edgeF,
+ ChangeSet.factory()
+ );
}
- ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
+ ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
- if( !changesToPass.isSubset(currentChanges) ) {
- todoEdges.add(edgeF);
- edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
+ if( !changesToPass.isSubset( currentChanges ) ) {
+ todoEdges.add( edgeF );
+ edgePlannedChanges.put( edgeF,
+ Canonical.union( currentChanges,
+ changesToPass
+ )
+ );
}
}
}
// then apply all of the changes for each edge at once
Iterator itrMap = edgePlannedChanges.entrySet().iterator();
while( itrMap.hasNext() ) {
- Map.Entry me = (Map.Entry) itrMap.next();
- RefEdge e = (RefEdge) me.getKey();
+ Map.Entry me = (Map.Entry) itrMap.next();
+ RefEdge e = (RefEdge) me.getKey();
ChangeSet C = (ChangeSet) me.getValue();
// this propagation step is with respect to one change,
// so we capture the full change from the old beta:
- ReachSet localDelta = e.getBeta().applyChangeSet( C, true );
+ ReachSet localDelta =
+ Canonical.applyChangeSet( e.getBeta(),
+ C,
+ true
+ );
// 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( e.getBetaNew().union( localDelta ) );
+ e.setBetaNew( Canonical.union( e.getBetaNew(),
+ localDelta
+ )
+ );
edgesWithNewBeta.add( e );
}
}
+ // 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
+ protected RefEdge
+ getOutOfContextReferenceTo( HeapRegionNode hrn,
+ TypeDescriptor srcType,
+ TypeDescriptor refType,
+ String refField ) {
+ assert belongsToThis( hrn );
+
+ HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
+ if( hrnInContext == null ) {
+ return 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;
+ }
+
+ HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
+ if( !hrnSrc.isOutOfContext() ) {
+ continue;
+ }
+
+ if( srcType == null ) {
+ if( hrnSrc.getType() != null ) {
+ continue;
+ }
+ } else {
+ if( !srcType.equals( hrnSrc.getType() ) ) {
+ continue;
+ }
+ }
+
+ if( !re.typeEquals( refType ) ) {
+ continue;
+ }
+
+ if( !re.fieldEquals( refField ) ) {
+ continue;
+ }
+
+ // tada! We found it!
+ return re;
+ }
+
+ return null;
+ }
+
+ // used below to convert a ReachSet to its callee-context
+ // equivalent with respect to allocation sites in this graph
+ protected ReachSet toCalleeContext( Set<ReachTuple> oocTuples,
+ ReachSet rs,
+ Integer hrnID,
+ TempDescriptor tdSrc,
+ Integer hrnSrcID,
+ Integer hrnDstID,
+ TypeDescriptor type,
+ String field,
+ boolean outOfContext
+ ) {
+ 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-context bag
+ if( !oocTuples.contains( rt ) ) {
+ stateNew = Canonical.union( 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.union( 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.union( 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.union( stateNew,
+ ReachTuple.factory( rt.getHrnID(),
+ rt.isMultiObject(),
+ rt.getArity(),
+ true // out-of-context
+ )
+ );
+ }
+ }
+
+ stateCallee = stateNew;
+ }
+
+
+ ExistPredSet preds;
+
+ if( outOfContext ) {
+ preds = predsEmpty;
+ } else {
+ ExistPred pred;
+ if( hrnID != null ) {
+ assert tdSrc == null;
+ assert hrnSrcID == null;
+ assert hrnDstID == null;
+ pred = ExistPred.factory( hrnID,
+ stateCaller );
+ } else {
+ assert tdSrc != null || hrnSrcID != null;
+ assert hrnDstID != null;
+ pred = ExistPred.factory( tdSrc,
+ hrnSrcID,
+ hrnDstID,
+ type,
+ field,
+ stateCaller,
+ false );
+ }
+ preds = ExistPredSet.factory( pred );
+ }
+
+ stateCallee = Canonical.attach( stateCallee,
+ preds );
+
+ 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();
+
+ 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( rs, 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.union( 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;
+ }
+
// use this method to make a new reach graph that is
// what heap the FlatMethod callee from the FlatCall
// would start with reaching from its arguments in
// this reach graph
- public ReachGraph makeCalleeView( FlatCall fc,
- FlatMethod fm ) {
+ public ReachGraph
+ makeCalleeView( FlatCall fc,
+ 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
- Set callerNodesCopiedToCallee = new HashSet<HeapRegionNode>();
- Set callerEdgesCopiedToCallee = 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 ) {
-
- // 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 );
+ // 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>();
+
+ // 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 );
- // 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
-
- if( rsnCaller == vnCaller ) {
- // if the caller node is the param symbol, we
- // have to do this translation for the callee
- rsnCallee = vnCallee;
- } 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;
-
- if( !callerNodesCopiedToCallee.contains( rsnCaller ) ) {
- rsnCallee =
- rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
- hrnSrcCaller.isSingleObject(),
- hrnSrcCaller.isNewSummary(),
- hrnSrcCaller.isFlagged(),
- true, // clean?
- false, // out-of-context?
- hrnSrcCaller.getType(),
- hrnSrcCaller.getAllocSite(),
- toShadowTokens( this, hrnSrcCaller.getInherent() ),
- toShadowTokens( this, hrnSrcCaller.getAlpha() ),
- hrnSrcCaller.getDescription()
- );
- callerNodesCopiedToCallee.add( rsnCaller );
- } else {
- rsnCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
- }
- }
-
- // 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
-
- if( !callerNodesCopiedToCallee.contains( hrnCaller ) ) {
- hrnCallee =
- rg.createNewHeapRegionNode( hrnCaller.getID(),
- hrnCaller.isSingleObject(),
- hrnCaller.isNewSummary(),
- hrnCaller.isFlagged(),
- true, // clean?
- false, // out-of-context?
- hrnCaller.getType(),
- hrnCaller.getAllocSite(),
- toShadowTokens( this, hrnCaller.getInherent() ),
- toShadowTokens( this, hrnCaller.getAlpha() ),
- hrnCaller.getDescription()
- );
- callerNodesCopiedToCallee.add( hrnCaller );
+
+ callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
+ reachableCallerNodes.add( hrnCaller );
+
+ if( reCaller.getSrc() instanceof HeapRegionNode ) {
+ reachableCallerEdges.add( reCaller );
} else {
- hrnCallee = rg.id2hrn.get( hrnCaller.getID() );
+ if( rsnCaller.equals( vnArgCaller ) ) {
+ reachableCallerArgEdges2paramIndex.put( reCaller, i );
+ } else {
+ oocCallerEdges.add( reCaller );
+ }
}
- // FOURTH - copy edge over if needed
- if( !callerEdgesCopiedToCallee.contains( reCaller ) ) {
- rg.addRefEdge( rsnCallee,
- hrnCallee,
- new RefEdge( rsnCallee,
- hrnCallee,
- reCaller.getType(),
- reCaller.getField(),
- true, // clean?
- toShadowTokens( this, reCaller.getBeta() )
- )
- );
- callerEdgesCopiedToCallee.add( reCaller );
- }
-
- // 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<HeapRegionNode> itrInContext =
- callerNodesCopiedToCallee.iterator();
+ // now collect out-of-context reach tuples and
+ // more out-of-context edges
+ Set<ReachTuple> oocTuples = new HashSet<ReachTuple>();
+
+ Iterator<Integer> itrInContext =
+ callerNodeIDsCopiedToCallee.iterator();
while( itrInContext.hasNext() ) {
- HeapRegionNode hrnCallerAndInContext = itrInContext.next();
+ Integer hrnID = itrInContext.next();
+ HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
Iterator<RefEdge> itrMightCross =
hrnCallerAndInContext.iteratorToReferencers();
while( itrMightCross.hasNext() ) {
- RefEdge edgeMightCross = itrMightCross.next();
-
- // we're only interested in edges with a source
- // 1) out-of-context and 2) is a heap region
- if( callerNodesCopiedToCallee.contains( edgeMightCross.getSrc() ) ||
- !(edgeMightCross.getSrc() instanceof HeapRegionNode)
- ) {
- // then just skip
+ RefEdge edgeMightCross = itrMightCross.next();
+
+ RefSrcNode rsnCallerAndOutContext =
+ edgeMightCross.getSrc();
+
+ if( rsnCallerAndOutContext instanceof VariableNode ) {
+ // variables do not have out-of-context reach states,
+ // so jump out now
+ oocCallerEdges.add( edgeMightCross );
continue;
}
-
+
HeapRegionNode hrnCallerAndOutContext =
- (HeapRegionNode)edgeMightCross.getSrc();
-
- // 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, // clean?
- true, // out-of-context?
- hrnCallerAndOutContext.getType(),
- null, // alloc site, shouldn't be used
- toShadowTokens( this, hrnCallerAndOutContext.getAlpha() ), // inherent
- toShadowTokens( this, hrnCallerAndOutContext.getAlpha() ), // alpha
- "out-of-context"
- );
-
- HeapRegionNode hrnCalleeAndInContext =
- rg.id2hrn.get( hrnCallerAndInContext.getID() );
+ (HeapRegionNode) rsnCallerAndOutContext;
- rg.addRefEdge( hrnCalleeAndOutContext,
- hrnCalleeAndInContext,
- new RefEdge( hrnCalleeAndOutContext,
- hrnCalleeAndInContext,
- edgeMightCross.getType(),
- edgeMightCross.getField(),
- true, // clean?
- toShadowTokens( this, edgeMightCross.getBeta() )
- )
- );
- }
- }
+ // is this source node out-of-context?
+ if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
+ // no, skip this edge
+ continue;
+ }
+ // okay, we got one
+ oocCallerEdges.add( edgeMightCross );
- try {
- rg.writeGraph( "calleeview", true, true, true, false, true, true );
- } catch( IOException e ) {}
+ // 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();
- if( fc.getMethod().getSymbol().equals( "f1" ) ) {
- System.exit( 0 );
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+
+ oocTuples.add( rt );
+ }
+ }
+ }
}
- return rg;
- }
+ // the callee view is a new graph: DON'T MODIFY *THIS* graph
+ ReachGraph rg = new ReachGraph();
- public void resolveMethodCall( FlatCall fc,
- FlatMethod fm,
- ReachGraph rgCallee
- ) {
- /*
- // to map the callee effects into the caller graph,
- // traverse the callee and categorize each element as,
- // Callee elements:
- // 1) new node (not in caller)
- // 2) old node, clean (not modified in callee)
- // 3) old node, dirty
- // 4) new edge,
- // 5) old edge, clean
- // 6) old edge, dirty
- // 7) out-of-context nodes
- // 8) edge that crosses out-of-context to in-
-
- Iterator hrnItr = rgCallee.id2hrn.entrySet().iterator();
+ // add nodes to callee graph
+ Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
while( hrnItr.hasNext() ) {
- Map.Entry me = (Map.Entry) hrnItr.next();
- Integer id = (Integer) me.getKey();
- HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
+ 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 );
- if( hrnCallee.isOutOfContext() ) {
- // 7) out-of-context nodes aren't altered by callee
- // analysis, they just help calculate changes to other
- // elements, so do nothing for this node
+ rg.createNewHeapRegionNode( hrnCaller.getID(),
+ hrnCaller.isSingleObject(),
+ hrnCaller.isNewSummary(),
+ hrnCaller.isFlagged(),
+ false, // out-of-context?
+ hrnCaller.getType(),
+ hrnCaller.getAllocSite(),
+ toCalleeContext( oocTuples,
+ hrnCaller.getInherent(), // in state
+ hrnCaller.getID(), // node pred
+ null, null, null, null, null, // edge pred
+ false ), // ooc pred
+ toCalleeContext( oocTuples,
+ hrnCaller.getAlpha(), // in state
+ hrnCaller.getID(), // node pred
+ null, null, null, null, null, // edge pred
+ false ), // ooc pred
+ 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();
+
+ TempDescriptor arg = fmCallee.getParameter( index );
+
+ VariableNode vnCallee =
+ rg.getVariableNodeFromTemp( arg );
+
+ HeapRegionNode hrnDstCaller = reArg.getDst();
+ HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
+ assert hrnDstCallee != null;
+
+ ExistPred pred =
+ ExistPred.factory( arg,
+ null,
+ hrnDstCallee.getID(),
+ reArg.getType(),
+ reArg.getField(),
+ null,
+ false ); // out-of-context
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge reCallee =
+ new RefEdge( vnCallee,
+ hrnDstCallee,
+ reArg.getType(),
+ reArg.getField(),
+ toCalleeContext( oocTuples,
+ reArg.getBeta(), // in state
+ null, // node pred
+ arg, // edge pred
+ null, // edge pred
+ hrnDstCallee.getID(), // edge pred
+ reArg.getType(), // edge pred
+ reArg.getField(), // edge pred
+ false ), // ooc pred
+ 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,
+ false ); // out-of-context
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge reCallee =
+ new RefEdge( hrnSrcCallee,
+ hrnDstCallee,
+ reCaller.getType(),
+ reCaller.getField(),
+ toCalleeContext( oocTuples,
+ reCaller.getBeta(), // in state
+ null, // node pred
+ null, // edge pred
+ hrnSrcCallee.getID(), // edge pred
+ hrnDstCallee.getID(), // edge pred
+ reCaller.getType(), // edge pred
+ reCaller.getField(), // edge pred
+ false ), // ooc pred
+ preds
+ );
+
+ 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;
+
+ if( rsnCaller instanceof VariableNode ) {
+ VariableNode vnCaller = (VariableNode) rsnCaller;
+ oocNodeType = null;
+ oocReach = rsetEmpty;
+ oocPredSrcTemp = vnCaller.getTempDescriptor();
} else {
- // node is in the callee context...
-
- if( !this.id2hrn.containsKey( id ) ) {
- // 1) this is a new node in the callee
- assert !hrnCallee.isClean();
-
- // bring this node into caller as-is, and do the
- // unshadow of tokens in-place
- this.createNewHeapRegionNode( id,
- hrnCallee.isSingleObject(),
- hrnCallee.isNewSummary(),
- hrnCallee.isFlagged(),
- false, // clean?
- false, // out-of-context?
- hrnCallee.getType(),
- hrnCallee.getAllocSite(),
- unShadowTokens( rgCallee, hrnCallee.getInherent() ),
- unShadowTokens( rgCallee, hrnCallee.getAlpha() ),
- hrnCallee.getDescription()
- );
+ HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
+ assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
+ oocNodeType = hrnSrcCaller.getType();
+ oocReach = hrnSrcCaller.getAlpha();
+ oocPredSrcID = hrnSrcCaller.getID();
+ }
+
+ ExistPred pred =
+ ExistPred.factory( oocPredSrcTemp,
+ oocPredSrcID,
+ hrnDstCallee.getID(),
+ reCaller.getType(),
+ reCaller.getField(),
+ null,
+ true ); // out-of-context
+
+ 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?
+ false, // flagged?
+ true, // out-of-context?
+ oocNodeType,
+ null, // alloc site, shouldn't be used
+ toCalleeContext( oocTuples,
+ oocReach, // in state
+ null, // node pred
+ null, null, null, null, null, // edge pred
+ true // ooc pred
+ ), // inherent
+ toCalleeContext( oocTuples,
+ oocReach, // in state
+ null, // node pred
+ null, null, null, null, null, // edge pred
+ true // ooc pred
+ ), // alpha
+ preds,
+ "out-of-context"
+ );
+
+ oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
} else {
- // otherwise, both graphs have this node, so...
- if( hrnCallee.isClean() ) {
- // 2) this node was not modified by callee,
- // just leave it alone in caller
-
- } else {
- // 3) this node is already in caller, was modified
- // by the callee, so update caller node in-place
- hrnCaller = this.id2hrn.get( id );
-
- assert hrnCaller.getInherent().equals(
- unShadowTokens( rgCallee, hrnCallee.getInherent() )
- );
- hrnCaller.setAlpha(
- unShadowTokens( rgCallee, hrnCallee.getAlpha() )
- );
-
- hrnCaller.setClean( false );
+ // 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?
+ false, // flagged?
+ true, // out-of-context?
+ oocNodeType,
+ null, // alloc site, shouldn't be used
+ toCalleeContext( oocTuples,
+ oocReach, // in state
+ null, // node pred
+ null, null, null, null, null, // edge pred
+ true // ooc pred
+ ), // inherent
+ toCalleeContext( oocTuples,
+ oocReach, // in state
+ null, // node pred
+ null, null, null, null, null, // edge pred
+ true // ooc pred
+ ), // alpha
+ preds,
+ "out-of-context"
+ );
}
- }
- }
- } // end visiting callee nodes
+ }
- // what else?
- */
- }
+ rg.addRefEdge( hrnCalleeAndOutContext,
+ hrnDstCallee,
+ new RefEdge( hrnCalleeAndOutContext,
+ hrnDstCallee,
+ reCaller.getType(),
+ reCaller.getField(),
+ toCalleeContext( oocTuples,
+ reCaller.getBeta(), // in state
+ null, // node pred
+ oocPredSrcTemp, // edge pred
+ oocPredSrcID, // edge pred
+ hrnDstCaller.getID(), // edge pred
+ reCaller.getType(), // edge pred
+ reCaller.getField(), // edge pred
+ false // ooc pred
+ ),
+ preds
+ )
+ );
+
+ } else {
+ // the out-of-context edge already exists
+ oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
+ toCalleeContext( oocTuples,
+ reCaller.getBeta(), // in state
+ null, // node pred
+ oocPredSrcTemp, // edge pred
+ oocPredSrcID, // edge pred
+ hrnDstCaller.getID(), // edge pred
+ reCaller.getType(), // edge pred
+ reCaller.getField(), // edge pred
+ false // ooc pred
+ )
+ )
+ );
+
+ oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
+ reCaller.getPreds()
+ )
+ );
+
+ }
+ }
-
- protected void unshadowTokens( AllocSite as,
- RefEdge edge
- ) {
- edge.setBeta( edge.getBeta().unshadowTokens( as ) );
- }
- protected void unshadowTokens( AllocSite as,
- HeapRegionNode hrn
- ) {
- hrn.setAlpha( hrn.getAlpha().unshadowTokens( as ) );
- }
+ if( writeDebugDOTs ) {
+ try {
+ rg.writeGraph( "calleeview", true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+ return rg;
+ }
+
+ private static Hashtable<String, Integer> oocid2hrnid =
+ new Hashtable<String, Integer>();
+
+
+
+ public void
+ resolveMethodCall( FlatCall fc,
+ 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 ) {}
+ }
+
+
+ // method call transfer function steps:
+ // 1. Use current callee-reachable heap (CRH) to test callee
+ // predicates and mark what will be coming in.
+ // 2. Wipe CRH out of caller.
+ // 3. Transplant marked callee parts in:
+ // a) bring in nodes
+ // b) bring in callee -> callee edges
+ // c) resolve out-of-context -> callee edges
+ // d) assign return value
+ // 4. Collapse shadow nodes down
+ // 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<ReachState, ExistPredSet> calleeStatesSatisfied =
+ new Hashtable<ReachState, 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 to this node
+ continue;
+ }
+
+ // since the node is coming over, find out which reach
+ // states on it should come over, too
+ Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState stateCallee = stateItr.next();
+
+ predsIfSatis =
+ stateCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( predsIfSatis != null ) {
+ calleeStatesSatisfied.put( stateCallee, predsIfSatis );
+ }
+ }
+
+ // then look at edges to the node
+ Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
+ while( reItr.hasNext() ) {
+ 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. What about (param var->heap region)
+ // edges in callee? They are dealt with below this loop.
+ // So, yes, at this point skip (var->region) edges in callee
+ if( rsnCallee instanceof VariableNode ) {
+ continue;
+ }
+
+ // 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() ) {
+
+ assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
+ Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
+
+ HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
+ 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 );
+
+ // since the edge is coming over, find out which reach
+ // states on it should come over, too
+ stateItr = reCallee.getBeta().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState stateCallee = stateItr.next();
+
+ predsIfSatis =
+ stateCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( predsIfSatis != null ) {
+ calleeStatesSatisfied.put( stateCallee, predsIfSatis );
+ }
+ }
+
+ }
+
+ }
+ }
+
+ // test param -> HRN edges, also
+ for( int i = 0; i < fmCallee.numParameters(); ++i ) {
+
+ // parameter defined here is the symbol in the callee
+ TempDescriptor tdParam = fmCallee.getParameter( i );
+ VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
+
+ Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
+ while( reItr.hasNext() ) {
+ RefEdge reCallee = reItr.next();
+
+ ExistPredSet ifDst =
+ reCallee.getDst().getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( ifDst == null ) {
+ continue;
+ }
+
+ ExistPredSet predsIfSatis =
+ reCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( predsIfSatis != null ) {
+ calleeEdgesSatisfied.put( reCallee, predsIfSatis );
+
+ // since the edge is coming over, find out which reach
+ // states on it should come over, too
+ Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState stateCallee = stateItr.next();
+
+ predsIfSatis =
+ stateCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee
+ );
+ if( predsIfSatis != null ) {
+ calleeStatesSatisfied.put( stateCallee, predsIfSatis );
+ }
+ }
+
+ }
+ }
+ }
+
+
+
+
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller20BeforeWipe",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+
+
+ // 2. predicates tested, ok to wipe out caller part
+ Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
+ while( hrnItr.hasNext() ) {
+ Integer hrnID = hrnItr.next();
+ HeapRegionNode hrnCaller = id2hrn.get( hrnID );
+ assert hrnCaller != null;
+
+ // when clearing off nodes, also eliminate variable
+ // references
+ wipeOut( hrnCaller, true );
+ }
+
+
+
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller30BeforeAddingNodes",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+
+
+ // 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
+ // some caller element ER. We bring EE into the caller
+ // context as ERee with the preds of ER, namely ERp, which
+ // in the following algorithm is the value in the mapping
+
+ // 3.a) nodes
+ Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
+ while( satisItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) satisItr.next();
+ 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;
+ }
+
+ AllocSite as = hrnCallee.getAllocSite();
+ allocSites.add( as );
+
+ Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
+
+ HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
+ if( hrnCaller == null ) {
+ hrnCaller =
+ 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
+ toCallerContext( hrnCallee.getInherent(),
+ calleeStatesSatisfied ), // inherent reach
+ null, // current reach
+ predsEmpty, // predicates
+ hrnCallee.getDescription() // description
+ );
+ } else {
+ assert hrnCaller.isWiped();
+ }
+
+ hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
+ calleeStatesSatisfied
+ )
+ );
+
+ hrnCaller.setPreds( preds );
+ }
+
+
+
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller31BeforeAddingEdges",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+
+
+ // 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
+ satisItr = calleeEdgesSatisfied.entrySet().iterator();
+ while( satisItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) satisItr.next();
+ RefEdge reCallee = (RefEdge) me.getKey();
+ ExistPredSet preds = (ExistPredSet) me.getValue();
+
+ HeapRegionNode hrnDstCallee = reCallee.getDst();
+ AllocSite asDst = hrnDstCallee.getAllocSite();
+ allocSites.add( asDst );
+
+ Integer hrnIDDstShadow =
+ asDst.getShadowIDfromID( hrnDstCallee.getID() );
+
+ HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
+ assert hrnDstCaller != null;
+
+
+ RefSrcNode rsnCallee = reCallee.getSrc();
+
+ Set<RefSrcNode> rsnCallers =
+ new HashSet<RefSrcNode>();
+
+ Set<RefSrcNode> oocCallers =
+ calleeEdges2oocCallerSrcMatches.get( reCallee );
+
+ boolean oocEdges = false;
+
+ 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;
+ }
+ rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
+ oocEdges = true;
+
+ } else {
+ // otherwise source is in context, one region
+ HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
+
+ // translate an in-context node to shadow
+ AllocSite asSrc = hrnSrcCallee.getAllocSite();
+ allocSites.add( asSrc );
+
+ Integer hrnIDSrcShadow =
+ asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
+
+ HeapRegionNode hrnSrcCallerShadow =
+ this.id2hrn.get( hrnIDSrcShadow );
+
+ if( hrnSrcCallerShadow == null ) {
+ hrnSrcCallerShadow =
+ createNewHeapRegionNode( hrnIDSrcShadow, // id or null to generate a new one
+ hrnSrcCallee.isSingleObject(), // single object?
+ hrnSrcCallee.isNewSummary(), // summary?
+ hrnSrcCallee.isFlagged(), // flagged?
+ false, // out-of-context?
+ hrnSrcCallee.getType(), // type
+ hrnSrcCallee.getAllocSite(), // allocation site
+ toCallerContext( hrnSrcCallee.getInherent(),
+ calleeStatesSatisfied ), // inherent reach
+ toCallerContext( hrnSrcCallee.getAlpha(),
+ calleeStatesSatisfied ), // current reach
+ predsEmpty, // predicates
+ hrnSrcCallee.getDescription() // description
+ );
+ }
+
+ 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 );
+ oocEdges = true;
+ }
+
+ // 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(),
+ calleeStatesSatisfied ),
+ preds
+ );
+
+ ChangeSet cs = ChangeSet.factory();
+ Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
+ while( rsItr.hasNext() ) {
+ ReachState state = rsItr.next();
+ ExistPredSet preds2 = state.getPreds();
+ assert preds2.preds.size() == 1;
+
+ if( state.isEmpty() ) {
+ continue;
+ }
+
+ ExistPred pred = preds2.preds.iterator().next();
+ ReachState old = pred.ne_state;
+
+ if( old == null ) {
+ old = rstateEmpty;
+ }
+
+ assert old != null;
+
+ cs = Canonical.union( cs,
+ ChangeTuple.factory( old,
+ state
+ )
+ );
+ }
+
+ // 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()
+ )
+ );
+
+ // for reach propagation
+ if( !cs.isEmpty() ) {
+ edgePlannedChanges.put(
+ edgeExisting,
+ Canonical.union( edgePlannedChanges.get( edgeExisting ),
+ cs
+ )
+ );
+ }
+
+ } else {
+ addRefEdge( rsnCaller, hrnDstCaller, reCaller );
+
+ // for reach propagation
+ if( !cs.isEmpty() ) {
+ edgesForPropagation.add( reCaller );
+ assert !edgePlannedChanges.containsKey( reCaller );
+ edgePlannedChanges.put( reCaller, cs );
+ }
+ }
+ }
+ }
+
+
+
+
+
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller35BeforeAssignReturnValue",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+
+
+
+ // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
+ // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
+ // EDGES, JUST BRINGING THEM ALL! It'll work for now, over approximation
+
+ // 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() );
+
+ HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
+ if( hrnDstCaller == null ) {
+ hrnDstCaller =
+ createNewHeapRegionNode( hrnIDDstShadow, // id or null to generate a new one
+ hrnDstCallee.isSingleObject(), // single object?
+ hrnDstCallee.isNewSummary(), // summary?
+ hrnDstCallee.isFlagged(), // flagged?
+ false, // out-of-context?
+ hrnDstCallee.getType(), // type
+ hrnDstCallee.getAllocSite(), // allocation site
+ toCallerContext( hrnDstCallee.getInherent(),
+ calleeStatesSatisfied ), // inherent reach
+ toCallerContext( hrnDstCallee.getAlpha(),
+ calleeStatesSatisfied ), // current reach
+ predsTrue, // predicates
+ hrnDstCallee.getDescription() // description
+ );
+ } else {
+ assert hrnDstCaller.isWiped();
+ }
+
+ TypeDescriptor tdNewEdge =
+ mostSpecificType( reCallee.getType(),
+ hrnDstCallee.getType(),
+ hrnDstCaller.getType()
+ );
+
+ RefEdge reCaller = new RefEdge( vnLhsCaller,
+ hrnDstCaller,
+ tdNewEdge,
+ null,
+ toCallerContext( reCallee.getBeta(),
+ calleeStatesSatisfied ),
+ predsTrue
+ );
+
+ addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
+ }
+ }
+
+
+
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller38propagateReach",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+
+ // 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();
+ }
+
+
+
+
+
+
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller40BeforeShadowMerge",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+
+
+ // 4) merge shadow nodes so alloc sites are back to k
+ Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
+ while( asItr.hasNext() ) {
+ // for each allocation site do the following to merge
+ // shadow nodes (newest from callee) with any existing
+ // look for the newest normal and newest shadow "slot"
+ // not being used, transfer normal to shadow. Keep
+ // doing this until there are no more normal nodes, or
+ // no empty shadow slots: then merge all remaining normal
+ // nodes into the shadow summary. Finally, convert all
+ // shadow to their normal versions.
+ AllocSite as = asItr.next();
+ int ageNorm = 0;
+ int ageShad = 0;
+ while( ageNorm < allocationDepth &&
+ ageShad < allocationDepth ) {
+
+ // first, are there any normal nodes left?
+ Integer idNorm = as.getIthOldest( ageNorm );
+ HeapRegionNode hrnNorm = id2hrn.get( idNorm );
+ if( hrnNorm == null ) {
+ // no, this age of normal node not in the caller graph
+ ageNorm++;
+ continue;
+ }
+
+ // yes, a normal node exists, is there an empty shadow
+ // "slot" to transfer it onto?
+ HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
+ if( !hrnShad.isWiped() ) {
+ // no, this age of shadow node is not empty
+ ageShad++;
+ continue;
+ }
+
+ // yes, this shadow node is empty
+ transferOnto( hrnNorm, hrnShad );
+ ageNorm++;
+ ageShad++;
+ }
+
+ // now, while there are still normal nodes but no shadow
+ // slots, merge normal nodes into the shadow summary
+ while( ageNorm < allocationDepth ) {
+
+ // first, are there any normal nodes left?
+ Integer idNorm = as.getIthOldest( ageNorm );
+ HeapRegionNode hrnNorm = id2hrn.get( idNorm );
+ if( hrnNorm == null ) {
+ // no, this age of normal node not in the caller graph
+ ageNorm++;
+ continue;
+ }
+
+ // yes, a normal node exists, so get the shadow summary
+ HeapRegionNode summShad = getSummaryNode( as, true );
+ mergeIntoSummary( hrnNorm, summShad );
+ ageNorm++;
+ }
+
+ // if there is a normal summary, merge it into shadow summary
+ Integer idNorm = as.getSummary();
+ HeapRegionNode summNorm = id2hrn.get( idNorm );
+ if( summNorm != null ) {
+ HeapRegionNode summShad = getSummaryNode( as, true );
+ mergeIntoSummary( summNorm, summShad );
+ }
+
+ // finally, flip all existing shadow nodes onto the normal
+ for( int i = 0; i < allocationDepth; ++i ) {
+ Integer idShad = as.getIthOldestShadow( i );
+ HeapRegionNode hrnShad = id2hrn.get( idShad );
+ if( hrnShad != null ) {
+ // flip it
+ HeapRegionNode hrnNorm = getIthNode( as, i, false );
+ assert hrnNorm.isWiped();
+ transferOnto( hrnShad, hrnNorm );
+ }
+ }
+
+ Integer idShad = as.getSummaryShadow();
+ HeapRegionNode summShad = id2hrn.get( idShad );
+ if( summShad != null ) {
+ summNorm = getSummaryNode( as, false );
+ transferOnto( summShad, summNorm );
+ }
+ }
+
+
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller45BeforeUnshadow",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+
+
+ 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 ) {
+ try {
+ writeGraph( "caller50BeforeGlobalSweep",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
+ }
+
+
+ // 5.
+ if( !DISABLE_GLOBAL_SWEEP ) {
+ globalSweep();
+ }
+
- private ReachSet toShadowTokens( ReachGraph rg,
- ReachSet rsIn
- ) {
- ReachSet rsOut = new ReachSet( rsIn ).makeCanonical();
- Iterator<AllocSite> allocItr = rg.allocSites.iterator();
- while( allocItr.hasNext() ) {
- AllocSite as = allocItr.next();
- rsOut = rsOut.toShadowTokens( as );
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller90AfterTransfer",
+ true, false, false, false, true, true );
+ } catch( IOException e ) {}
}
+ }
+
+
+
+ ////////////////////////////////////////////////////
+ //
+ // Abstract garbage collection simply removes
+ // heap region nodes that are not mechanically
+ // reachable from a root set. This step is
+ // essential for testing node and edge existence
+ // predicates efficiently
+ //
+ ////////////////////////////////////////////////////
+ public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
+
+ // calculate a root set, will be different for Java
+ // version of analysis versus Bamboo version
+ Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
+
+ // visit every variable in graph while building root
+ // set, and do iterating on a copy, so we can remove
+ // dead variables while we're at this
+ Iterator makeCopyItr = td2vn.entrySet().iterator();
+ Set entrysCopy = new HashSet();
+ while( makeCopyItr.hasNext() ) {
+ entrysCopy.add( makeCopyItr.next() );
+ }
+
+ Iterator eItr = entrysCopy.iterator();
+ while( eItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) eItr.next();
+ TempDescriptor td = (TempDescriptor) me.getKey();
+ VariableNode vn = (VariableNode) me.getValue();
- return rsOut.makeCanonical();
+ if( liveSet.contains( td ) ) {
+ toVisit.add( vn );
+
+ } else {
+ // dead var, remove completely from graph
+ td2vn.remove( td );
+ clearRefEdgesFrom( vn, null, null, true );
+ }
+ }
+
+ // everything visited in a traversal is
+ // considered abstractly live
+ Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
+
+ while( !toVisit.isEmpty() ) {
+ RefSrcNode rsn = toVisit.iterator().next();
+ toVisit.remove( rsn );
+ visited.add( rsn );
+
+ Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
+ while( hrnItr.hasNext() ) {
+ RefEdge edge = hrnItr.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ if( !visited.contains( hrn ) ) {
+ toVisit.add( hrn );
+ }
+ }
+ }
+
+ // get a copy of the set to iterate over because
+ // we're going to monkey with the graph when we
+ // identify a garbage node
+ Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
+ Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
+ while( hrnItr.hasNext() ) {
+ hrnAllPrior.add( hrnItr.next() );
+ }
+
+ Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
+ while( hrnAllItr.hasNext() ) {
+ HeapRegionNode hrn = hrnAllItr.next();
+
+ if( !visited.contains( hrn ) ) {
+
+ // heap region nodes are compared across ReachGraph
+ // objects by their integer ID, so when discarding
+ // garbage nodes we must also discard entries in
+ // the ID -> heap region hashtable.
+ id2hrn.remove( hrn.getID() );
+
+ // RefEdge objects are two-way linked between
+ // nodes, so when a node is identified as garbage,
+ // actively clear references to and from it so
+ // live nodes won't have dangling RefEdge's
+ wipeOut( hrn, true );
+
+ // if we just removed the last node from an allocation
+ // site, it should be taken out of the ReachGraph's list
+ AllocSite as = hrn.getAllocSite();
+ if( !hasNodesOf( as ) ) {
+ allocSites.remove( as );
+ }
+ }
+ }
}
+ protected boolean hasNodesOf( AllocSite as ) {
+ if( id2hrn.containsKey( as.getSummary() ) ) {
+ return true;
+ }
+
+ for( int i = 0; i < allocationDepth; ++i ) {
+ if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
+ return true;
+ }
+ }
+ return false;
+ }
////////////////////////////////////////////////////
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
- Set hrns = id2hrn.entrySet();
- Iterator itrHrns = hrns.iterator();
+ // 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();
- Integer token = (Integer) me.getKey();
- HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+ Map.Entry me = (Map.Entry) itrHrns.next();
+ Integer hrnID = (Integer) me.getKey();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
// assert that this node and incoming edges have clean alphaNew
// and betaNew sets, respectively
- assert rstateEmpty.equals( hrn.getAlphaNew() );
+ assert rsetEmpty.equals( hrn.getAlphaNew() );
Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
while( itrRers.hasNext() ) {
RefEdge edge = itrRers.next();
- assert rstateEmpty.equals( edge.getBetaNew() );
+ assert rsetEmpty.equals( edge.getBetaNew() );
}
- // calculate boldB for this flagged node
+ // calculate boldB for this flagged node, or out-of-context node
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() );
+ Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
+ srcs.add( hrn );
+ icID2srcs.put( hrn.getID(), srcs );
+ }
- // initial boldB_f constraints
- Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
- while( itrRees.hasNext() ) {
- RefEdge edge = itrRees.next();
+ if( hrn.isOutOfContext() ) {
+ assert !hrn.isFlagged();
- assert !boldB.containsKey( edge );
- boldB_f.put( edge, edge.getBeta() );
+ Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
- assert !workSetEdges.contains( edge );
- workSetEdges.add( edge );
- }
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+ assert rt.isOutOfContext();
- // 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 = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
-
- if( prevResult == null ||
- prevResult.union( intersection ).size() > prevResult.size() ) {
-
- if( prevResult == null ) {
- boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
- } else {
- boldB_f.put( edgePrime, prevResult .union( intersection ) );
- }
- workSetEdges.add( edgePrime );
- }
- }
- }
+ Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
+ if( srcs == null ) {
+ srcs = new HashSet<HeapRegionNode>();
+ }
+ srcs.add( hrn );
+ oocID2srcs.put( rt.getHrnID(), srcs );
+ }
+ }
+ }
+ }
+
+ // calculate boldB for all hrnIDs identified by the above
+ // node traversal, propagating from every source
+ while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
+
+ Integer hrnID;
+ Set<HeapRegionNode> srcs;
+ boolean inContext;
+
+ 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 );
+
+ } 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>();
- boldB.put( token, boldB_f );
- }
+ Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
+
+ Iterator<HeapRegionNode> hrnItr = srcs.iterator();
+ while( hrnItr.hasNext() ) {
+ HeapRegionNode hrn = hrnItr.next();
+
+ 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
+ )
+ );
+ } else {
+ boldB_f.put( edgePrime,
+ Canonical.union( prevResult,
+ intersection
+ )
+ );
+ }
+ workSetEdges.add( edgePrime );
+ }
+ }
+ }
+ }
+
+ if( inContext ) {
+ boldBic.put( hrnID, boldB_f );
+ } else {
+ boldBooc.put( hrnID, boldB_f );
+ }
}
- // use boldB to prune tokens from alpha states that are impossible
+ // use boldB to prune hrnIDs from alpha states that are impossible
// and propagate the differences backwards across edges
HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
new Hashtable<RefEdge, ChangeSet>();
- hrns = id2hrn.entrySet();
- itrHrns = hrns.iterator();
+
+ itrHrns = id2hrn.entrySet().iterator();
while( itrHrns.hasNext() ) {
- Map.Entry me = (Map.Entry)itrHrns.next();
- Integer token = (Integer) me.getKey();
- HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+ Map.Entry me = (Map.Entry) itrHrns.next();
+ Integer hrnID = (Integer) me.getKey();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ // out-of-context nodes don't participate in the
+ // global sweep, they serve as sources for the pass
+ // performed above
+ if( hrn.isOutOfContext() ) {
+ continue;
+ }
- // never remove the identity token from a flagged region
- // because it is trivially satisfied
- ReachTuple ttException = new ReachTuple( token,
- !hrn.isSingleObject(),
- ReachTuple.ARITY_ONE ).makeCanonical();
+ // 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 = new ChangeSet().makeCanonical();
+ ChangeSet cts = ChangeSet.factory();
- // mark tokens for removal
+ // mark hrnIDs for removal
Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
while( stateItr.hasNext() ) {
- ReachState ttsOld = stateItr.next();
+ ReachState stateOld = stateItr.next();
- ReachState markedTokens = new ReachState().makeCanonical();
+ ReachState markedHrnIDs = ReachState.factory();
- Iterator<ReachTuple> ttItr = ttsOld.iterator();
- while( ttItr.hasNext() ) {
- ReachTuple ttOld = ttItr.next();
+ Iterator<ReachTuple> rtItr = stateOld.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rtOld = rtItr.next();
- // never remove the identity token from a flagged region
+ // never remove the inherent hrnID from a flagged region
// because it is trivially satisfied
if( hrn.isFlagged() ) {
- if( ttOld == ttException ) {
+ if( rtOld == rtException ) {
continue;
}
}
- // does boldB_ttOld allow this token?
+ // 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 = ttOld.getToken();
- assert id2hrn.containsKey( idOld );
- Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
- ReachSet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
- if( boldB_ttOld_incident != null &&
- boldB_ttOld_incident.contains( ttsOld ) ) {
- foundState = true;
- }
+ Hashtable<RefEdge, ReachSet> B;
+ if( rtOld.isOutOfContext() ) {
+ B = boldBooc.get( rtOld.getHrnID() );
+ } else {
+ assert id2hrn.containsKey( rtOld.getHrnID() );
+ B = boldBic.get( rtOld.getHrnID() );
+ }
+
+ if( B != null ) {
+ ReachSet boldB_rtOld_incident = B.get( incidentEdge );
+ if( boldB_rtOld_incident != null &&
+ boldB_rtOld_incident.contains( stateOld ) ) {
+ foundState = true;
+ }
+ }
}
-
+
if( !foundState ) {
- markedTokens = markedTokens.add( ttOld );
+ markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
}
}
// if there is nothing marked, just move on
- if( markedTokens.isEmpty() ) {
- hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
+ if( markedHrnIDs.isEmpty() ) {
+ hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
+ stateOld
+ )
+ );
continue;
}
- // remove all marked tokens and establish a change set that should
+ // remove all marked hrnIDs and establish a change set that should
// propagate backwards over edges from this node
- ReachState ttsPruned = new ReachState().makeCanonical();
- ttItr = ttsOld.iterator();
- while( ttItr.hasNext() ) {
- ReachTuple ttOld = ttItr.next();
+ ReachState statePruned = ReachState.factory();
+ rtItr = stateOld.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rtOld = rtItr.next();
- if( !markedTokens.containsTuple( ttOld ) ) {
- ttsPruned = ttsPruned.union( ttOld );
+ if( !markedHrnIDs.containsTuple( rtOld ) ) {
+ statePruned = Canonical.union( statePruned, rtOld );
}
}
- assert !ttsOld.equals( ttsPruned );
+ assert !stateOld.equals( statePruned );
- hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
- ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
- cts = cts.union( ct );
+ hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
+ statePruned
+ )
+ );
+ ChangeTuple ct = ChangeTuple.factory( stateOld,
+ statePruned
+ );
+ cts = Canonical.union( cts, ct );
}
// throw change tuple set on all incident edges
edgePlannedChanges.put( incidentEdge, cts );
} else {
edgePlannedChanges.put(
- incidentEdge,
- edgePlannedChanges.get( incidentEdge ).union( cts )
- );
+ incidentEdge,
+ Canonical.union( edgePlannedChanges.get( incidentEdge ),
+ cts
+ )
+ );
}
}
}
// 2nd phase
Iterator<RefEdge> edgeItr = res.iterator();
while( edgeItr.hasNext() ) {
- RefEdge edge = edgeItr.next();
- HeapRegionNode hrn = edge.getDst();
+ RefEdge edge = edgeItr.next();
+ HeapRegionNode hrn = edge.getDst();
// commit results of last phase
if( edgesUpdated.contains( edge ) ) {
}
// compute intial condition of 2nd phase
- edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
+ edge.setBetaNew( Canonical.intersection( edge.getBeta(),
+ hrn.getAlpha()
+ )
+ );
}
// every edge in the graph is the initial workset
RefEdge edgePrime = edgeWorkSet.iterator().next();
edgeWorkSet.remove( edgePrime );
- RefSrcNode on = edgePrime.getSrc();
- if( !(on instanceof HeapRegionNode) ) {
+ RefSrcNode rsn = edgePrime.getSrc();
+ if( !(rsn instanceof HeapRegionNode) ) {
continue;
}
- HeapRegionNode hrn = (HeapRegionNode) on;
+ HeapRegionNode hrn = (HeapRegionNode) rsn;
Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
while( itrEdge.hasNext() ) {
ReachSet prevResult = edge.getBetaNew();
assert prevResult != null;
- ReachSet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
+ ReachSet intersection =
+ Canonical.intersection( edge.getBeta(),
+ edgePrime.getBetaNew()
+ );
- if( prevResult.union( intersection ).size() > prevResult.size() ) {
- edge.setBetaNew( prevResult.union( intersection ) );
+ if( Canonical.union( prevResult,
+ intersection
+ ).size() > prevResult.size() ) {
+ edge.setBetaNew(
+ Canonical.union( prevResult,
+ intersection
+ )
+ );
edgeWorkSet.add( edge );
}
}
// so make the new reachability set a union of the
// nodes' reachability sets
HeapRegionNode hrnB = id2hrn.get( idA );
- hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
+ hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
+ hrnA.getAlpha()
+ )
+ );
- // if hrnB is already dirty or hrnA is dirty,
- // the hrnB should end up dirty
- if( !hrnA.isClean() ) {
- hrnB.setIsClean( false );
- }
+ hrnB.setPreds( Canonical.join( hrnB.getPreds(),
+ hrnA.getPreds()
+ )
+ );
}
}
// just replace this beta set with the union
assert edgeToMerge != null;
edgeToMerge.setBeta(
- edgeToMerge.getBeta().union( edgeA.getBeta() )
- );
- if( !edgeA.isClean() ) {
- edgeToMerge.setIsClean( false );
- }
+ Canonical.union( edgeToMerge.getBeta(),
+ edgeA.getBeta()
+ )
+ );
+ edgeToMerge.setPreds(
+ Canonical.join( edgeToMerge.getPreds(),
+ edgeA.getPreds()
+ )
+ );
}
}
}
// so merge their reachability sets
else {
// just replace this beta set with the union
- edgeToMerge.setBeta(
- edgeToMerge.getBeta().union( edgeA.getBeta() )
- );
- if( !edgeA.isClean() ) {
- edgeToMerge.setIsClean( false );
- }
+ edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
+ edgeA.getBeta()
+ )
+ );
+ edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
+ edgeA.getPreds()
+ )
+ );
}
}
}
}
HeapRegionNode hrnB = rgB.id2hrn.get( idA );
- if( !hrnA.equalsIncludingAlpha( hrnB ) ) {
+ if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
return false;
}
}
// there is an edge in the right place with the right field,
// but do they have the same attributes?
- if( edgeA.getBeta().equals( edgeB.getBeta() ) ) {
+ if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
+ edgeA.equalsPreds( edgeB )
+ ) {
edgeFound = true;
}
}
}
- public void writeGraph( String graphName,
+
+ public void writeGraph( String graphName,
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
boolean hideSubsetReachability,
boolean hideEdgeTaints
) throws java.io.IOException {
+ writeGraph( graphName,
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ hideSubsetReachability,
+ hideEdgeTaints,
+ null );
+ }
+
+ public void writeGraph( String graphName,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean hideSubsetReachability,
+ 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
bw.write( "digraph "+graphName+" {\n" );
+
+ // this is an optional step to form the callee-reachable
+ // "cut-out" into a DOT cluster for visualization
+ if( callerNodeIDsCopiedToCallee != null ) {
+
+ 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( hideSubsetReachability )+
+ ";\n" );
+
+ }
+ }
+
+ bw.write( " }\n" );
+ }
+
+
Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
- // then visit every heap region node
- Set s = id2hrn.entrySet();
- Iterator i = s.iterator();
+ // 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();
visited,
writeReferencers,
hideSubsetReachability,
- hideEdgeTaints );
+ hideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
}
}
}
// then visit every label node, useful for debugging
if( writeLabels ) {
- s = td2vn.entrySet();
- i = s.iterator();
+ i = td2vn.entrySet().iterator();
while( i.hasNext() ) {
Map.Entry me = (Map.Entry) i.next();
VariableNode vn = (VariableNode) me.getValue();
continue;
}
}
-
- //bw.write(" "+vn.toString() + ";\n");
Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
while( heapRegionsItr.hasNext() ) {
visited,
writeReferencers,
hideSubsetReachability,
- hideEdgeTaints );
+ hideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
}
- bw.write( " " + vn.toString() +
- " -> " + hrn.toString() +
- "[label=\"" + edge.toGraphEdgeString( hideSubsetReachability ) +
- "\",decorate];\n" );
+ bw.write( " "+vn.toString()+
+ " -> "+hrn.toString()+
+ edge.toStringDOT( hideSubsetReachability, "" )+
+ ";\n" );
}
}
}
bw.close();
}
- protected void traverseHeapRegionNodes( HeapRegionNode hrn,
- BufferedWriter bw,
- TempDescriptor td,
+ protected void traverseHeapRegionNodes( HeapRegionNode hrn,
+ BufferedWriter bw,
+ TempDescriptor td,
Set<HeapRegionNode> visited,
- boolean writeReferencers,
- boolean hideSubsetReachability,
- boolean hideEdgeTaints
+ boolean writeReferencers,
+ boolean hideSubsetReachability,
+ boolean hideEdgeTaints,
+ Set<Integer> callerNodeIDsCopiedToCallee
) throws java.io.IOException {
if( visited.contains( hrn ) ) {
}
visited.add( hrn );
- String attributes = "[";
-
- if( hrn.isSingleObject() ) {
- attributes += "shape=box";
- } else {
- attributes += "shape=Msquare";
- }
-
- if( hrn.isFlagged() ) {
- attributes += ",style=filled,fillcolor=lightgrey";
- }
-
- attributes += ",label=\"ID" +
- hrn.getID() +
- "\\n";
-
- if( hrn.getType() != null ) {
- attributes += hrn.getType().toPrettyString() + "\\n";
+ // if we're drawing the callee-view subgraph, only
+ // write out the node info if it hasn't already been
+ // written
+ if( callerNodeIDsCopiedToCallee == null ||
+ !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
+ ) {
+ bw.write( " "+hrn.toString()+
+ hrn.toStringDOT( hideSubsetReachability )+
+ ";\n" );
}
-
- attributes += hrn.getDescription() +
- "\\n" +
- hrn.getAlphaString( hideSubsetReachability ) +
- "\"]";
-
- bw.write( " "+hrn.toString()+attributes+";\n" );
-
Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
while( childRegionsItr.hasNext() ) {
RefEdge edge = childRegionsItr.next();
HeapRegionNode hrnChild = edge.getDst();
- bw.write( " " +hrn.toString()+
- " -> " +hrnChild.toString()+
- "[label=\""+edge.toGraphEdgeString( hideSubsetReachability )+
- "\",decorate];\n");
-
+ if( callerNodeIDsCopiedToCallee != null &&
+ (edge.getSrc() instanceof HeapRegionNode) ) {
+ HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
+ if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID() ) &&
+ callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
+ ) {
+ bw.write( " "+hrn.toString()+
+ " -> "+hrnChild.toString()+
+ edge.toStringDOT( hideSubsetReachability, ",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" )+
+ ";\n");
+ } else {
+ bw.write( " "+hrn.toString()+
+ " -> "+hrnChild.toString()+
+ edge.toStringDOT( hideSubsetReachability, "" )+
+ ";\n");
+ }
+ } else {
+ bw.write( " "+hrn.toString()+
+ " -> "+hrnChild.toString()+
+ edge.toStringDOT( hideSubsetReachability, "" )+
+ ";\n");
+ }
+
traverseHeapRegionNodes( hrnChild,
bw,
td,
visited,
writeReferencers,
hideSubsetReachability,
- hideEdgeTaints );
+ hideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
}
}
projects / IRC.git / blobdiff