import java.io.*;
public class ReachGraph {
+
+ // use to disable improvements for comparison
+ protected static final boolean DISABLE_STRONG_UPDATES = false;
+ protected static final boolean DISABLE_GLOBAL_SWEEP = false;
- protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
+ // 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 );
- public Hashtable<Integer, HeapRegionNode> id2hrn;
- public Hashtable<TempDescriptor, VariableNode > td2vn;
-
- public HashSet<AllocSite> allocSites;
-
+ // 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 );
- // use to disable improvements for comparison
- protected static final boolean DISABLE_STRONG_UPDATES = false;
- protected static final boolean DISABLE_GLOBAL_SWEEP = false;
+ // from DisjointAnalysis for convenience
protected static int allocationDepth = -1;
protected static TypeUtil typeUtil = null;
- protected static boolean debugCallMap = false;
- protected static int debugCallMapCount = 0;
- protected static String debugCallee = null;
- protected static String debugCaller = null;
+ // variable and heap region nodes indexed by unique ID
+ public Hashtable<Integer, HeapRegionNode> id2hrn;
+ public Hashtable<TempDescriptor, VariableNode > td2vn;
+
+ // convenient set of alloc sites for all heap regions
+ // present in the graph without having to search
+ public HashSet<AllocSite> allocSites;
public ReachGraph() {
- /*
- id2hrn = new Hashtable<Integer, HeapRegionNode>();
- td2vn = new Hashtable<TempDescriptor, VariableNode >();
-
+ id2hrn = new Hashtable<Integer, HeapRegionNode>();
+ td2vn = new Hashtable<TempDescriptor, VariableNode >();
allocSites = new HashSet<AllocSite>();
- */
}
- /*
- // temp descriptors are globally unique and maps to
+
+ // temp descriptors are globally unique and map to
// exactly one variable node, easy
protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
assert td != null;
return td2vn.get( td );
}
+ public boolean hasVariable( TempDescriptor td ) {
+ return td2vn.containsKey( td );
+ }
+
+
+ // 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
// in the merge() operation) or to create new heap
// regions with a new unique ID
protected HeapRegionNode
- createNewHeapRegionNode( Integer id,
- boolean isSingleObject,
- boolean isNewSummary,
- boolean isFlagged,
+ createNewHeapRegionNode( Integer id,
+ boolean isSingleObject,
+ boolean isNewSummary,
+ boolean isFlagged,
+ boolean isOutOfContext,
TypeDescriptor type,
- AllocSite allocSite,
- ReachSet alpha,
- String description,
- String globalIdentifier ) {
+ AllocSite allocSite,
+ ReachSet inherent,
+ ReachSet alpha,
+ ExistPredSet preds,
+ String description
+ ) {
boolean markForAnalysis = isFlagged;
TypeDescriptor typeToUse = null;
if( allocSite != null ) {
typeToUse = allocSite.getType();
+ allocSites.add( allocSite );
} else {
typeToUse = type;
}
id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
}
- if( alpha == null ) {
+ if( inherent == null ) {
if( markForAnalysis ) {
- alpha = 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 {
- alpha = new ReachSet(
- new ReachState().makeCanonical()
- ).makeCanonical();
+ inherent = rsetWithEmptyState;
}
}
+
+ if( alpha == null ) {
+ alpha = inherent;
+ }
+
+ assert preds != null;
HeapRegionNode hrn = new HeapRegionNode( id,
isSingleObject,
markForAnalysis,
isNewSummary,
+ isOutOfContext,
typeToUse,
allocSite,
+ inherent,
alpha,
- description,
- globalIdentifier );
+ preds,
+ description );
id2hrn.put( id, hrn );
return hrn;
}
// Low-level referencee and referencer methods
//
// These methods provide the lowest level for
- // creating references between ownership nodes
+ // creating references between reachability nodes
// and handling the details of maintaining both
// list of referencers and referencees.
//
////////////////////////////////////////////////
- protected void addRefEdge(RefSrcNode referencer,
- HeapRegionNode referencee,
- RefEdge edge) {
+ protected void addRefEdge( RefSrcNode referencer,
+ HeapRegionNode referencee,
+ RefEdge edge ) {
assert referencer != null;
assert referencee != null;
assert edge != null;
assert edge.getSrc() == referencer;
assert edge.getDst() == referencee;
-
- referencer.addReferencee(edge);
- referencee.addReferencer(edge);
+ 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 removeRefEdge(RefEdge e) {
- removeRefEdge(e.getSrc(),
- e.getDst(),
- e.getType(),
- e.getField() );
+ protected void removeRefEdge( RefEdge e ) {
+ removeRefEdge( e.getSrc(),
+ e.getDst(),
+ e.getType(),
+ e.getField() );
}
- protected void removeRefEdge(RefSrcNode referencer,
- HeapRegionNode referencee,
- TypeDescriptor type,
- String field) {
+ protected void removeRefEdge( RefSrcNode referencer,
+ HeapRegionNode referencee,
+ TypeDescriptor type,
+ String field ) {
assert referencer != null;
assert referencee != null;
- RefEdge edge = referencer.getReferenceTo(referencee,
- type,
- field);
+ RefEdge edge = referencer.getReferenceTo( referencee,
+ type,
+ field );
assert edge != null;
- assert edge == referencee.getReferenceFrom(referencer,
- type,
- field);
+ assert edge == referencee.getReferenceFrom( referencer,
+ type,
+ field );
-// int oldTaint=edge.getTaintIdentifier();
-// if(referencer instanceof HeapRegionNode){
-// depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
-// }
-
- referencer.removeReferencee(edge);
- referencee.removeReferencer(edge);
+ referencer.removeReferencee( edge );
+ referencee.removeReferencer( edge );
}
- protected void clearRefEdgesFrom(RefSrcNode referencer,
- TypeDescriptor type,
- String field,
- boolean removeAll) {
+ protected void clearRefEdgesFrom( RefSrcNode referencer,
+ TypeDescriptor type,
+ String field,
+ boolean removeAll ) {
assert referencer != null;
// get a copy of the set to iterate over, otherwise
HeapRegionNode referencee = edge.getDst();
- removeRefEdge(referencer,
- referencee,
- edge.getType(),
- edge.getField() );
+ removeRefEdge( referencer,
+ referencee,
+ edge.getType(),
+ edge.getField() );
}
}
}
- protected void clearRefEdgesTo(HeapRegionNode referencee,
- TypeDescriptor type,
- String field,
- boolean removeAll) {
+ protected void clearRefEdgesTo( HeapRegionNode referencee,
+ TypeDescriptor type,
+ String field,
+ boolean removeAll ) {
assert referencee != null;
// get a copy of the set to iterate over, otherwise
RefSrcNode referencer = edge.getSrc();
- removeRefEdge(referencer,
- referencee,
- edge.getType(),
- edge.getField() );
+ removeRefEdge( referencer,
+ referencee,
+ edge.getType(),
+ edge.getField() );
+ }
+ }
+ }
+
+ 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() );
}
}
}
// the low-level reference create/remove methods
// above.
//
- // The destination in an assignment statement is
- // going to have new references. The method of
- // determining the references depends on the type
- // of the FlatNode assignment and the predicates
- // of the nodes and edges involved.
- //
////////////////////////////////////////////////////
- public void nullifyDeadVars( Set<TempDescriptor> liveIn ) {
-
- // make a set of the temps that are out of scope, don't
- // consider them when nullifying dead in-scope variables
- Set<TempDescriptor> outOfScope = new HashSet<TempDescriptor>();
- outOfScope.add( tdReturn );
- outOfScope.add( tdAliasBlob );
- outOfScope.addAll( paramIndex2tdQ.values() );
- outOfScope.addAll( paramIndex2tdR.values() );
-
- Iterator varItr = td2vn.entrySet().iterator();
- while( varItr.hasNext() ) {
- Map.Entry me = (Map.Entry) varItr.next();
- TempDescriptor td = (TempDescriptor) me.getKey();
- VariableNode ln = (VariableNode) me.getValue();
-
- // if this variable is not out-of-scope or live
- // in graph, nullify its references to anything
- if( !outOfScope.contains( td ) &&
- !liveIn.contains( td )
- ) {
- clearRefEdgesFrom( ln, null, null, true );
- }
- }
- }
-
-
public void assignTempXEqualToTempY( TempDescriptor x,
TempDescriptor y ) {
assignTempXEqualToCastedTempY( x, y, null );
Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
while( itrYhrn.hasNext() ) {
- RefEdge edgeY = itrYhrn.next();
+ RefEdge edgeY = itrYhrn.next();
HeapRegionNode referencee = edgeY.getDst();
- RefEdge edgeNew = edgeY.copy();
+ RefEdge edgeNew = edgeY.copy();
if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
impossibleEdges.add( edgeY );
edgeNew.setSrc( lnX );
- edgeNew.setType( mostSpecificType( y.getType(),
- tdCast,
- edgeY.getType(),
- referencee.getType()
- )
- );
+ if( tdCast == null ) {
+ edgeNew.setType( mostSpecificType( y.getType(),
+ edgeY.getType(),
+ referencee.getType()
+ )
+ );
+ } else {
+ edgeNew.setType( mostSpecificType( y.getType(),
+ edgeY.getType(),
+ referencee.getType(),
+ tdCast
+ )
+ );
+ }
edgeNew.setField( null );
Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
while( itrYhrn.hasNext() ) {
- RefEdge edgeY = itrYhrn.next();
- HeapRegionNode hrnY = edgeY.getDst();
- ReachSet betaY = edgeY.getBeta();
+ RefEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+ ReachSet betaY = edgeY.getBeta();
Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
while( itrHrnFhrn.hasNext() ) {
- RefEdge edgeHrn = itrHrnFhrn.next();
- HeapRegionNode hrnHrn = edgeHrn.getDst();
- ReachSet betaHrn = edgeHrn.getBeta();
+ RefEdge edgeHrn = itrHrnFhrn.next();
+ HeapRegionNode hrnHrn = edgeHrn.getDst();
+ ReachSet betaHrn = edgeHrn.getBeta();
// prune edges that are not a matching field
if( edgeHrn.getType() != null &&
TypeDescriptor tdNewEdge =
mostSpecificType( edgeHrn.getType(),
hrnHrn.getType()
- );
+ );
RefEdge edgeNew = new RefEdge( lnX,
- hrnHrn,
- tdNewEdge,
- null,
- false,
- betaY.intersection( betaHrn )
- );
+ hrnHrn,
+ tdNewEdge,
+ null,
+ Canonical.intersection( betaY, betaHrn ),
+ predsTrue
+ );
- int newTaintIdentifier=getTaintIdentifierFromHRN(hrnHrn);
- edgeNew.setTaintIdentifier(newTaintIdentifier);
-
- 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();
}
- }
+ }
}
VariableNode lnY = getVariableNodeFromTemp( y );
HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
- HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
+ HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
// note it is possible that the types of temps in the
// flat node to analyze will reveal that some typed
Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
while( itrXhrn.hasNext() ) {
- RefEdge edgeX = itrXhrn.next();
- HeapRegionNode hrnX = edgeX.getDst();
+ RefEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
// we can do a strong update here if one of two cases holds
if( f != null &&
// then do all token propagation
itrXhrn = lnX.iteratorToReferencees();
while( itrXhrn.hasNext() ) {
- RefEdge edgeX = itrXhrn.next();
- HeapRegionNode hrnX = edgeX.getDst();
- ReachSet betaX = edgeX.getBeta();
- ReachSet R = hrnX.getAlpha().intersection( edgeX.getBeta() );
+ RefEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
+ ReachSet betaX = edgeX.getBeta();
+ ReachSet R = Canonical.intersection( hrnX.getAlpha(),
+ edgeX.getBeta()
+ );
Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
while( itrYhrn.hasNext() ) {
- RefEdge edgeY = itrYhrn.next();
- HeapRegionNode hrnY = edgeY.getDst();
- ReachSet O = edgeY.getBeta();
+ RefEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+ ReachSet O = edgeY.getBeta();
// check for impossible edges
if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
// 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 =
// then go back through and add the new edges
itrXhrn = lnX.iteratorToReferencees();
while( itrXhrn.hasNext() ) {
- RefEdge edgeX = itrXhrn.next();
- HeapRegionNode hrnX = edgeX.getDst();
+ RefEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
while( itrYhrn.hasNext() ) {
- RefEdge edgeY = itrYhrn.next();
- HeapRegionNode hrnY = edgeY.getDst();
+ RefEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
// skip impossible edges here, we already marked them
// when computing reachability propagations above
);
RefEdge edgeNew = new RefEdge( hrnX,
- hrnY,
- tdNewEdge,
- f.getSymbol(),
- false,
- edgeY.getBeta().pruneBy( hrnX.getAlpha() )
- );
+ hrnY,
+ tdNewEdge,
+ f.getSymbol(),
+ Canonical.pruneBy( edgeY.getBeta(),
+ hrnX.getAlpha()
+ ),
+ predsTrue
+ );
// look to see if an edge with same field exists
// and merge with it, otherwise just add the edge
RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
- tdNewEdge,
- f.getSymbol() );
+ tdNewEdge,
+ f.getSymbol() );
if( edgeExisting != null ) {
edgeExisting.setBeta(
- edgeExisting.getBeta().union( edgeNew.getBeta() )
- );
-
- if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
- int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
- edgeExisting.unionTaintIdentifier(newTaintIdentifier);
- }
- // a new edge here cannot be reflexive, so existing will
- // always be also not reflexive anymore
- edgeExisting.setIsInitialParam( false );
- } else {
-
- if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){
- int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY);
- edgeNew.setTaintIdentifier(newTaintIdentifier);
- }
- //currently, taint isn't propagated through the chain of refrences
- //propagateTaintIdentifier(hrnX,newTaintIdentifier,new HashSet<HeapRegionNode>());
-
+ Canonical.unionORpreds( edgeExisting.getBeta(),
+ edgeNew.getBeta()
+ )
+ );
+ 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();
}
- }
- }
-
-
- // the parameter model is to use a single-object heap region
- // for the primary parameter, and a multiple-object heap
- // region for the secondary objects reachable through the
- // primary object, if necessary
- public void assignTempEqualToParamAlloc( TempDescriptor td,
- boolean isTask,
- Integer paramIndex, FlatMethod fm ) {
- assert td != null;
-
- TypeDescriptor typeParam = td.getType();
- assert typeParam != null;
-
- // either the parameter is an array or a class to be in this method
- assert typeParam.isArray() || typeParam.isClass();
-
- // discover some info from the param type and use it below
- // to get parameter model as precise as we can
- boolean createSecondaryRegion = false;
- Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
- Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
-
- // there might be an element reference for array types
- if( typeParam.isArray() ) {
- // only bother with this if the dereferenced type can
- // affect reachability
- TypeDescriptor typeDeref = typeParam.dereference();
- if( !typeDeref.isImmutable() || typeDeref.isArray() ) {
- primary2secondaryFields.add(
- DisjointAnalysis.getArrayField( typeDeref )
- );
- createSecondaryRegion = true;
-
- // also handle a special case where an array of objects
- // can point back to the array, which is an object!
- if( typeParam.toPrettyString().equals( "Object[]" ) &&
- typeDeref.toPrettyString().equals( "Object" ) ) {
-
- primary2primaryFields.add(
- DisjointAnalysis.getArrayField( typeDeref )
- );
- }
- }
- }
-
- // there might be member references for class types
- if( typeParam.isClass() ) {
- ClassDescriptor cd = typeParam.getClassDesc();
- while( cd != null ) {
-
- Iterator fieldItr = cd.getFields();
- while( fieldItr.hasNext() ) {
-
- FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
- TypeDescriptor typeField = fd.getType();
- assert typeField != null;
-
- if( !typeField.isImmutable() || typeField.isArray() ) {
- primary2secondaryFields.add( fd );
- createSecondaryRegion = true;
- }
-
- if( typeUtil.isSuperorType( typeField, typeParam ) ) {
- primary2primaryFields.add( fd );
- }
- }
-
- cd = cd.getSuperDesc();
- }
- }
-
-
- // now build everything we need
- VariableNode lnParam = getVariableNodeFromTemp( td );
- HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
- true, // single object?
- false, // summary?
- false, // flagged?
- true, // is a parameter?
- typeParam, // type
- null, // allocation site
- null, // reachability set
- "param"+paramIndex+" obj",
- generateUniqueIdentifier(fm,paramIndex,"P"));
-
- parameterTemps.add( td );
- parameterLabels.add( lnParam );
-
-
- // this is a non-program-accessible label that picks up beta
- // info to be used for fixing a caller of this method
- TempDescriptor tdParamQ = new TempDescriptor( td+qString );
- paramIndex2tdQ.put( paramIndex, tdParamQ );
- VariableNode lnParamQ = getVariableNodeFromTemp( tdParamQ );
-
- outOfScopeTemps.add( tdParamQ );
- outOfScopeLabels.add( lnParamQ );
-
- // keep track of heap regions that were created for
- // parameter labels, the index of the parameter they
- // are for is important when resolving method calls
- Integer newPrimaryID = hrnPrimary.getID();
- assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
- Set<Integer> s = new HashSet<Integer>();
- s.add( paramIndex );
- idPrimary2paramIndexSet.put( newPrimaryID, s );
- paramIndex2idPrimary.put( paramIndex, newPrimaryID );
-
- ReachTuple ttPrimary = new ReachTuple( newPrimaryID,
- false, // multi-object
- ReachTuple.ARITY_ONE ).makeCanonical();
-
-
- HeapRegionNode hrnSecondary = null;
- Integer newSecondaryID = null;
- ReachTuple ttSecondary = null;
- TempDescriptor tdParamR = null;
- VariableNode lnParamR = null;
-
- if( createSecondaryRegion ) {
- tdParamR = new TempDescriptor( td+rString );
- paramIndex2tdR.put( paramIndex, tdParamR );
- lnParamR = getVariableNodeFromTemp( tdParamR );
-
- outOfScopeTemps.add( tdParamR );
- outOfScopeLabels.add( lnParamR );
-
- hrnSecondary = createNewHeapRegionNode( null, // id or null to generate a new one
- false, // single object?
- false, // summary?
- false, // flagged?
- true, // is a parameter?
- null, // type
- null, // allocation site
- null, // reachability set
- "param"+paramIndex+" reachable",
- generateUniqueIdentifier(fm,paramIndex,"S"));
-
- newSecondaryID = hrnSecondary.getID();
- assert !idSecondary2paramIndexSet.containsKey( newSecondaryID );
- Set<Integer> s2 = new HashSet<Integer>();
- s2.add( paramIndex );
- idSecondary2paramIndexSet.put( newSecondaryID, s2 );
- paramIndex2idSecondary.put( paramIndex, newSecondaryID );
-
-
- ttSecondary = new ReachTuple( newSecondaryID,
- true, // multi-object
- ReachTuple.ARITY_ONE ).makeCanonical();
- }
-
- // use a beta that has everything and put it all over the
- // parameter model, then use a global sweep later to fix
- // it up, since parameters can have different shapes
- ReachState tts0 = new ReachState( ttPrimary ).makeCanonical();
- ReachSet betaSoup;
- if( createSecondaryRegion ) {
- ReachState tts1 = new ReachState( ttSecondary ).makeCanonical();
- ReachState tts2 = new ReachState( ttPrimary ).makeCanonical().union( ttSecondary );
- betaSoup = ReachSet.factory( tts0 ).union( tts1 ).union( tts2 );
- } else {
- betaSoup = ReachSet.factory( tts0 );
- }
-
- RefEdge edgeFromLabel =
- new RefEdge( lnParam, // src
- hrnPrimary, // dst
- typeParam, // type
- null, // field
- false, // special param initial (not needed on label->node)
- betaSoup ); // reachability
- edgeFromLabel.tainedBy(paramIndex);
- addRefEdge( lnParam, hrnPrimary, edgeFromLabel );
-
- RefEdge edgeFromLabelQ =
- new RefEdge( lnParamQ, // src
- hrnPrimary, // dst
- null, // type
- null, // field
- false, // special param initial (not needed on label->node)
- betaSoup ); // reachability
- edgeFromLabelQ.tainedBy(paramIndex);
- addRefEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
-
- RefEdge edgeSecondaryReflexive;
- if( createSecondaryRegion ) {
- edgeSecondaryReflexive =
- new RefEdge( hrnSecondary, // src
- hrnSecondary, // dst
- null, // match all types
- null, // match all fields
- true, // special param initial
- betaSoup ); // reachability
- addRefEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive );
-
- RefEdge edgeSecondary2Primary =
- new RefEdge( hrnSecondary, // src
- hrnPrimary, // dst
- null, // match all types
- null, // match all fields
- true, // special param initial
- betaSoup ); // reachability
- addRefEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary );
-
- RefEdge edgeFromLabelR =
- new RefEdge( lnParamR, // src
- hrnSecondary, // dst
- null, // type
- null, // field
- false, // special param initial (not needed on label->node)
- betaSoup ); // reachability
- edgeFromLabelR.tainedBy(paramIndex);
- addRefEdge( lnParamR, hrnSecondary, edgeFromLabelR );
- }
-
- Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
- while( fieldItr.hasNext() ) {
- FieldDescriptor fd = fieldItr.next();
-
- RefEdge edgePrimaryReflexive =
- new RefEdge( hrnPrimary, // src
- hrnPrimary, // dst
- fd.getType(), // type
- fd.getSymbol(), // field
- true, // special param initial
- betaSoup ); // reachability
- addRefEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
- }
-
- fieldItr = primary2secondaryFields.iterator();
- while( fieldItr.hasNext() ) {
- FieldDescriptor fd = fieldItr.next();
-
- RefEdge edgePrimary2Secondary =
- new RefEdge( hrnPrimary, // src
- hrnSecondary, // dst
- fd.getType(), // type
- fd.getSymbol(), // field
- true, // special param initial
- betaSoup ); // reachability
- addRefEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary );
- }
- }
-
-
- public void makeAliasedParamHeapRegionNode(FlatMethod fm) {
-
- VariableNode lnBlob = getVariableNodeFromTemp( tdAliasBlob );
-
- outOfScopeTemps.add( tdAliasBlob );
- outOfScopeLabels.add( lnBlob );
-
- HeapRegionNode hrn = createNewHeapRegionNode( null, // id or null to generate a new one
- false, // single object?
- false, // summary?
- false, // flagged?
- true, // is a parameter?
- null, // type
- null, // allocation site
- null, // reachability set
- "aliasedParams",
- generateUniqueIdentifier(fm,0,"A"));
-
-
- ReachSet beta = new ReachSet( new ReachTuple( hrn.getID(),
- true,
- ReachTuple.ARITY_ONE).makeCanonical()
- ).makeCanonical();
-
- RefEdge edgeFromLabel =
- new RefEdge( lnBlob, hrn, null, null, false, beta );
-
- RefEdge edgeReflexive =
- new RefEdge( hrn, hrn, null, null, true, beta );
-
- addRefEdge( lnBlob, hrn, edgeFromLabel );
- addRefEdge( hrn, hrn, edgeReflexive );
- }
-
-
- public void assignTempEqualToAliasedParam( TempDescriptor tdParam,
- Integer paramIndex, FlatMethod fm ) {
- assert tdParam != null;
-
- TypeDescriptor typeParam = tdParam.getType();
- assert typeParam != null;
-
- VariableNode lnParam = getVariableNodeFromTemp( tdParam );
- VariableNode lnAliased = getVariableNodeFromTemp( tdAliasBlob );
-
- parameterTemps.add( tdParam );
- parameterLabels.add( lnParam );
-
- // this is a non-program-accessible label that picks up beta
- // info to be used for fixing a caller of this method
- TempDescriptor tdParamQ = new TempDescriptor( tdParam+qString );
- TempDescriptor tdParamR = new TempDescriptor( tdParam+rString );
-
- paramIndex2tdQ.put( paramIndex, tdParamQ );
- paramIndex2tdR.put( paramIndex, tdParamR );
-
- VariableNode lnParamQ = getVariableNodeFromTemp( tdParamQ );
- VariableNode lnParamR = getVariableNodeFromTemp( tdParamR );
-
- outOfScopeTemps.add( tdParamR );
- outOfScopeLabels.add( lnParamR );
- outOfScopeTemps.add( tdParamQ );
- outOfScopeLabels.add( lnParamQ );
-
- // the lnAliased should always only reference one node, and that
- // heap region node is the aliased param blob
- assert lnAliased.getNumReferencees() == 1;
- HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
- Integer idAliased = hrnAliasBlob.getID();
-
-
- ReachTuple ttAliased = new ReachTuple( idAliased,
- true, // multi-object
- ReachTuple.ARITY_ONE ).makeCanonical();
-
-
- HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
- true, // single object?
- false, // summary?
- false, // flagged?
- true, // is a parameter?
- typeParam, // type
- null, // allocation site
- null, // reachability set
- "param"+paramIndex+" obj",
- generateUniqueIdentifier(fm, paramIndex.intValue(), "P"));
-
- Integer newPrimaryID = hrnPrimary.getID();
- assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
- Set<Integer> s1 = new HashSet<Integer>();
- s1.add( paramIndex );
- idPrimary2paramIndexSet.put( newPrimaryID, s1 );
- paramIndex2idPrimary.put( paramIndex, newPrimaryID );
-
- Set<Integer> s2 = idSecondary2paramIndexSet.get( idAliased );
- if( s2 == null ) {
- s2 = new HashSet<Integer>();
- }
- s2.add( paramIndex );
- idSecondary2paramIndexSet.put( idAliased, s2 );
- paramIndex2idSecondary.put( paramIndex, idAliased );
-
-
-
- ReachTuple ttPrimary = new ReachTuple( newPrimaryID,
- false, // multi-object
- ReachTuple.ARITY_ONE ).makeCanonical();
-
-
- ReachState tts0 = new ReachState( ttPrimary ).makeCanonical();
- ReachState tts1 = new ReachState( ttAliased ).makeCanonical();
- ReachState tts2 = new ReachState( ttPrimary ).makeCanonical().union( ttAliased );
- ReachSet betaSoup = ReachSet.factory( tts0 ).union( tts1 ).union( tts2 );
-
-
- RefEdge edgeFromLabel =
- new RefEdge( lnParam, // src
- hrnPrimary, // dst
- typeParam, // type
- null, // field
- false, // special param initial (not needed on label->node)
- betaSoup ); // reachability
- edgeFromLabel.tainedBy(paramIndex);
- addRefEdge( lnParam, hrnPrimary, edgeFromLabel );
-
- RefEdge edgeFromLabelQ =
- new RefEdge( lnParamQ, // src
- hrnPrimary, // dst
- null, // type
- null, // field
- false, // special param initial (not needed on label->node)
- betaSoup ); // reachability
- edgeFromLabelQ.tainedBy(paramIndex);
- addRefEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
-
- RefEdge edgeAliased2Primary =
- new RefEdge( hrnAliasBlob, // src
- hrnPrimary, // dst
- null, // match all types
- null, // match all fields
- true, // special param initial
- betaSoup ); // reachability
- addRefEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary );
-
- RefEdge edgeFromLabelR =
- new RefEdge( lnParamR, // src
- hrnAliasBlob, // dst
- null, // type
- null, // field
- false, // special param initial (not needed on label->node)
- betaSoup ); // reachability
- edgeFromLabelR.tainedBy(paramIndex);
- addRefEdge( lnParamR, hrnAliasBlob, edgeFromLabelR );
- }
-
-
- public void addParam2ParamAliasEdges( FlatMethod fm,
- Set<Integer> aliasedParamIndices ) {
-
- VariableNode lnAliased = getVariableNodeFromTemp( tdAliasBlob );
-
- // the lnAliased should always only reference one node, and that
- // heap region node is the aliased param blob
- assert lnAliased.getNumReferencees() == 1;
- HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
- Integer idAliased = hrnAliasBlob.getID();
-
-
- ReachTuple ttAliased = new ReachTuple( idAliased,
- true, // multi-object
- ReachTuple.ARITY_ONE ).makeCanonical();
-
-
- Iterator<Integer> apItrI = aliasedParamIndices.iterator();
- while( apItrI.hasNext() ) {
- Integer i = apItrI.next();
- TempDescriptor tdParamI = fm.getParameter( i );
- TypeDescriptor typeI = tdParamI.getType();
- VariableNode lnParamI = getVariableNodeFromTemp( tdParamI );
-
- Integer idPrimaryI = paramIndex2idPrimary.get( i );
- assert idPrimaryI != null;
- HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
- assert primaryI != null;
-
- ReachTuple ttPrimaryI = new ReachTuple( idPrimaryI,
- false, // multi-object
- ReachTuple.ARITY_ONE ).makeCanonical();
-
- ReachState ttsI = new ReachState( ttPrimaryI ).makeCanonical();
- ReachState ttsA = new ReachState( ttAliased ).makeCanonical();
- ReachState ttsIA = new ReachState( ttPrimaryI ).makeCanonical().union( ttAliased );
- ReachSet betaSoup = ReachSet.factory( ttsI ).union( ttsA ).union( ttsIA );
-
-
- // calculate whether fields of this aliased parameter are able to
- // reference its own primary object, the blob, or other parameter's
- // primary objects!
- Set<FieldDescriptor> primary2primaryFields = new HashSet<FieldDescriptor>();
- Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
-
- // there might be an element reference for array types
- if( typeI.isArray() ) {
- // only bother with this if the dereferenced type can
- // affect reachability
- TypeDescriptor typeDeref = typeI.dereference();
-
-
-
- /////////////////////////////////////////////////////////////
- // NOTE! For the KMeans benchmark a parameter of type float
- // array, which has an immutable dereferenced type, is causing
- // this assertion to fail. I'm commenting it out for now which
- // is safe, because it allows aliasing where no aliasing can occur,
- // so it can only get a worse-but-not-wrong answer. FIX!
- /////////////////////////////////////////////////////////////
- // for this parameter to be aliased the following must be true
- //assert !typeDeref.isImmutable() || typeDeref.isArray();
-
-
-
- primary2secondaryFields.add(
- DisjointAnalysis.getArrayField( typeDeref )
- );
-
- // also handle a special case where an array of objects
- // can point back to the array, which is an object!
- if( typeI .toPrettyString().equals( "Object[]" ) &&
- typeDeref.toPrettyString().equals( "Object" ) ) {
- primary2primaryFields.add(
- DisjointAnalysis.getArrayField( typeDeref )
- );
- }
- }
-
- // there might be member references for class types
- if( typeI.isClass() ) {
- ClassDescriptor cd = typeI.getClassDesc();
- while( cd != null ) {
-
- Iterator fieldItr = cd.getFields();
- while( fieldItr.hasNext() ) {
-
- FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
- TypeDescriptor typeField = fd.getType();
- assert typeField != null;
-
- if( !typeField.isImmutable() || typeField.isArray() ) {
- primary2secondaryFields.add( fd );
- }
-
- if( typeUtil.isSuperorType( typeField, typeI ) ) {
- primary2primaryFields.add( fd );
- }
- }
-
- cd = cd.getSuperDesc();
- }
- }
-
- Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
- while( fieldItr.hasNext() ) {
- FieldDescriptor fd = fieldItr.next();
-
- RefEdge edgePrimaryReflexive =
- new RefEdge( primaryI, // src
- primaryI, // dst
- fd.getType(), // type
- fd.getSymbol(), // field
- true, // special param initial
- betaSoup ); // reachability
- addRefEdge( primaryI, primaryI, edgePrimaryReflexive );
- }
-
- fieldItr = primary2secondaryFields.iterator();
- while( fieldItr.hasNext() ) {
- FieldDescriptor fd = fieldItr.next();
- TypeDescriptor typeField = fd.getType();
- assert typeField != null;
-
- RefEdge edgePrimary2Secondary =
- new RefEdge( primaryI, // src
- hrnAliasBlob, // dst
- fd.getType(), // type
- fd.getSymbol(), // field
- true, // special param initial
- betaSoup ); // reachability
- addRefEdge( primaryI, hrnAliasBlob, edgePrimary2Secondary );
-
- // ask whether these fields might match any of the other aliased
- // parameters and make those edges too
- Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
- while( apItrJ.hasNext() ) {
- Integer j = apItrJ.next();
- TempDescriptor tdParamJ = fm.getParameter( j );
- TypeDescriptor typeJ = tdParamJ.getType();
-
- if( !i.equals( j ) && typeUtil.isSuperorType( typeField, typeJ ) ) {
-
- Integer idPrimaryJ = paramIndex2idPrimary.get( j );
- assert idPrimaryJ != null;
- HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
- assert primaryJ != null;
-
- ReachTuple ttPrimaryJ = new ReachTuple( idPrimaryJ,
- false, // multi-object
- ReachTuple.ARITY_ONE ).makeCanonical();
-
- ReachState ttsJ = new ReachState( ttPrimaryJ ).makeCanonical();
- ReachState ttsIJ = ttsI.union( ttsJ );
- ReachState ttsAJ = ttsA.union( ttsJ );
- ReachState ttsIAJ = ttsIA.union( ttsJ );
- ReachSet betaSoupWJ = ReachSet.factory( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
-
- RefEdge edgePrimaryI2PrimaryJ =
- new RefEdge( primaryI, // src
- primaryJ, // dst
- fd.getType(), // type
- fd.getSymbol(), // field
- true, // special param initial
- betaSoupWJ ); // reachability
- addRefEdge( primaryI, primaryJ, edgePrimaryI2PrimaryJ );
- }
- }
- }
-
-
- // look at whether aliased parameters i and j can
- // possibly be the same primary object, add edges
- Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
- while( apItrJ.hasNext() ) {
- Integer j = apItrJ.next();
- TempDescriptor tdParamJ = fm.getParameter( j );
- TypeDescriptor typeJ = tdParamJ.getType();
- VariableNode lnParamJ = getVariableNodeFromTemp( tdParamJ );
-
- if( !i.equals( j ) && typeUtil.isSuperorType( typeI, typeJ ) ) {
-
- Integer idPrimaryJ = paramIndex2idPrimary.get( j );
- assert idPrimaryJ != null;
- HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ );
- assert primaryJ != null;
-
- RefEdge lnJ2PrimaryJ = lnParamJ.getReferenceTo( primaryJ,
- tdParamJ.getType(),
- null );
- assert lnJ2PrimaryJ != null;
-
- RefEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy();
- lnI2PrimaryJ.setSrc( lnParamI );
- lnI2PrimaryJ.setType( tdParamI.getType() );
- lnI2PrimaryJ.tainedBy(new Integer(j));
- addRefEdge( lnParamI, primaryJ, lnI2PrimaryJ );
- }
- }
- }
- }
-
- public void prepareParamTokenMaps( FlatMethod fm ) {
-
- // always add the bogus mappings that are used to
- // rewrite "with respect to no parameter"
- paramTokenPrimary2paramIndex.put( bogusToken, bogusIndex );
- paramIndex2paramTokenPrimary.put( bogusIndex, bogusToken );
-
- paramTokenSecondary2paramIndex.put( bogusToken, bogusIndex );
- paramIndex2paramTokenSecondary.put( bogusIndex, bogusToken );
- paramTokenSecondaryPlus2paramIndex.put( bogusTokenPlus, bogusIndex );
- paramIndex2paramTokenSecondaryPlus.put( bogusIndex, bogusTokenPlus );
- paramTokenSecondaryStar2paramIndex.put( bogusTokenStar, bogusIndex );
- paramIndex2paramTokenSecondaryStar.put( bogusIndex, bogusTokenStar );
-
- for( int i = 0; i < fm.numParameters(); ++i ) {
- Integer paramIndex = new Integer( i );
-
- // immutable objects have no primary regions
- if( paramIndex2idPrimary.containsKey( paramIndex ) ) {
- Integer idPrimary = paramIndex2idPrimary.get( paramIndex );
-
- assert id2hrn.containsKey( idPrimary );
- HeapRegionNode hrnPrimary = id2hrn.get( idPrimary );
-
- ReachTuple p_i = new ReachTuple( hrnPrimary.getID(),
- false, // multiple-object?
- ReachTuple.ARITY_ONE ).makeCanonical();
- paramTokenPrimary2paramIndex.put( p_i, paramIndex );
- paramIndex2paramTokenPrimary.put( paramIndex, p_i );
- }
-
- // any parameter object, by type, may have no secondary region
- if( paramIndex2idSecondary.containsKey( paramIndex ) ) {
- Integer idSecondary = paramIndex2idSecondary.get( paramIndex );
-
- assert id2hrn.containsKey( idSecondary );
- HeapRegionNode hrnSecondary = id2hrn.get( idSecondary );
-
- ReachTuple s_i = new ReachTuple( hrnSecondary.getID(),
- true, // multiple-object?
- ReachTuple.ARITY_ONE ).makeCanonical();
- paramTokenSecondary2paramIndex.put( s_i, paramIndex );
- paramIndex2paramTokenSecondary.put( paramIndex, s_i );
-
- ReachTuple s_i_plus = new ReachTuple( hrnSecondary.getID(),
- true, // multiple-object?
- ReachTuple.ARITY_ONEORMORE ).makeCanonical();
- paramTokenSecondaryPlus2paramIndex.put( s_i_plus, paramIndex );
- paramIndex2paramTokenSecondaryPlus.put( paramIndex, s_i_plus );
-
- ReachTuple s_i_star = new ReachTuple( hrnSecondary.getID(),
- true, // multiple-object?
- ReachTuple.ARITY_ZEROORMORE ).makeCanonical();
- paramTokenSecondaryStar2paramIndex.put( s_i_star, paramIndex );
- paramIndex2paramTokenSecondaryStar.put( paramIndex, s_i_star );
- }
- }
+ }
}
+ public void assignReturnEqualToTemp( TempDescriptor x ) {
- public void assignReturnEqualToTemp(TempDescriptor x) {
-
- VariableNode lnR = getVariableNodeFromTemp(tdReturn);
- VariableNode lnX = getVariableNodeFromTemp(x);
+ VariableNode lnR = getVariableNodeFromTemp( tdReturn );
+ VariableNode lnX = getVariableNodeFromTemp( x );
- clearRefEdgesFrom(lnR, null, null, true);
+ clearRefEdgesFrom( lnR, null, null, true );
Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
while( itrXhrn.hasNext() ) {
- RefEdge edgeX = itrXhrn.next();
+ RefEdge edgeX = itrXhrn.next();
HeapRegionNode referencee = edgeX.getDst();
- RefEdge edgeNew = edgeX.copy();
- edgeNew.setSrc(lnR);
+ RefEdge edgeNew = edgeX.copy();
+ edgeNew.setSrc( lnR );
- addRefEdge(lnR, referencee, edgeNew);
+ addRefEdge( lnR, referencee, edgeNew );
}
}
- public void assignTempEqualToNewAlloc(TempDescriptor x,
- AllocSite as) {
+ public void assignTempEqualToNewAlloc( TempDescriptor x,
+ AllocSite as ) {
assert x != null;
assert as != null;
clearRefEdgesFrom( lnX, null, null, true );
// make a new reference to allocated node
- TypeDescriptor type = as.getType();
- RefEdge edgeNew =
+ TypeDescriptor type = as.getType();
+
+ RefEdge edgeNew =
new RefEdge( lnX, // source
- hrnNewest, // dest
- type, // type
- null, // field name
- false, // is initial param
- hrnNewest.getAlpha() // beta
- );
+ hrnNewest, // dest
+ type, // type
+ null, // field name
+ hrnNewest.getAlpha(), // beta
+ predsTrue // predicates
+ );
addRefEdge( lnX, hrnNewest, edgeNew );
}
// use the allocation site (unique to entire analysis) to
- // locate the heap region nodes in this ownership graph
+ // locate the heap region nodes in this reachability graph
// that should be aged. The process models the allocation
// of new objects and collects all the oldest allocations
// in a summary node to allow for a finite analysis
//
// There is an additional property of this method. After
- // running it on a particular ownership graph (many graphs
+ // running it on a particular reachability graph (many graphs
// may have heap regions related to the same allocation site)
- // the heap region node objects in this ownership graph will be
+ // the heap region node objects in this reachability graph will be
// allocated. Therefore, after aging a graph for an allocation
// site, attempts to retrieve the heap region nodes using the
// integer id's contained in the allocation site should always
// return non-null heap regions.
- public void age(AllocSite as) {
+ 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
- allocSites.add(as);
+ // 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 ownership 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();
while( itrAllVariableNodes.hasNext() ) {
- Map.Entry me = (Map.Entry)itrAllVariableNodes.next();
+ Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
VariableNode ln = (VariableNode) me.getValue();
Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
while( itrEdges.hasNext() ) {
- ageTokens(as, itrEdges.next() );
+ ageTuplesFrom( as, itrEdges.next() );
}
}
Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
while( itrAllHRNodes.hasNext() ) {
- Map.Entry me = (Map.Entry)itrAllHRNodes.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
- if( hrn0.isFlagged() ) {
- hrn0.setAlpha(new ReachSet(
- new ReachState(
- new ReachTuple(hrn0).makeCanonical()
- ).makeCanonical()
- ).makeCanonical()
- );
- } else {
- hrn0.setAlpha(new ReachSet(
- new ReachState().makeCanonical()
- ).makeCanonical()
- );
- }
+ // 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 = as.getSummary();
- HeapRegionNode hrnSummary = id2hrn.get(idSummary);
+ Integer idSummary;
+ if( shadow ) {
+ idSummary = as.getSummaryShadow();
+ } else {
+ 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 ownership graph, so allocate
- // heap region nodes appropriate for the entire allocation site.
- // This should only happen once per ownership graph per allocation site,
- // and a particular integer id can be used to locate the heap region
- // in different ownership graphs that represents the same part of an
- // allocation site.
if( hrnSummary == null ) {
boolean hasFlags = false;
hasFlags = as.getType().getClassDesc().hasFlags();
}
- if(as.getFlag()){
- hasFlags=as.getFlag();
+ if( as.getFlag() ){
+ hasFlags = as.getFlag();
}
- hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one
- false, // single object?
- true, // summary?
- hasFlags, // flagged?
- false, // is a parameter?
- as.getType(), // type
- as, // allocation site
- null, // reachability set
- as.toStringForDOT() + "\\nsummary",
- generateUniqueIdentifier(as,0,true));
-
- for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- Integer idIth = as.getIthOldest(i);
- assert !id2hrn.containsKey(idIth);
- createNewHeapRegionNode(idIth, // id or null to generate a new one
- true, // single object?
- false, // summary?
- hasFlags, // flagged?
- false, // is a parameter?
- as.getType(), // type
- as, // allocation site
- null, // reachability set
- as.toStringForDOT() + "\\n" + i + " oldest",
- generateUniqueIdentifier(as,i,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, // out-of-context?
+ as.getType(), // type
+ as, // allocation site
+ null, // inherent reach
+ null, // current reach
+ predsEmpty, // predicates
+ 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();
}
- hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, // id or null to generate a new one
- false, // single object?
- true, // summary?
- hasFlags, // flagged?
- false, // is a parameter?
- as.getType(), // type
- as, // allocation site
- null, // reachability set
- as + "\\n" + as.getType() + "\\nshadowSum",
- "");
-
- for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- Integer idShadowIth = as.getIthOldestShadow(i);
- assert !id2hrn.containsKey(idShadowIth);
- createNewHeapRegionNode(idShadowIth, // id or null to generate a new one
- true, // single object?
- false, // summary?
- hasFlags, // flagged?
- false, // is a parameter?
- as.getType(), // type
- as, // allocation site
- null, // reachability set
- as + "\\n" + as.getType() + "\\n" + i + " shadow",
- "");
+ String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
+ if( shadow ) {
+ strDesc += " shadow";
}
- }
- return hrnShadowSummary;
+ 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 hrnIth;
}
- protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
+ protected void mergeIntoSummary( HeapRegionNode hrn,
+ 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() ) {
RefEdge edge = itrReferencee.next();
RefEdge edgeMerged = edge.copy();
- edgeMerged.setSrc(hrnSummary);
+ edgeMerged.setSrc( hrnSummary );
HeapRegionNode hrnReferencee = edge.getDst();
- RefEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
- edge.getType(),
- edge.getField() );
-
+ RefEdge edgeSummary =
+ hrnSummary.getReferenceTo( hrnReferencee,
+ edge.getType(),
+ edge.getField()
+ );
+
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.unionORpreds( edgeMerged.getBeta(),
+ edgeSummary.getBeta()
+ )
+ );
+ edgeSummary.setPreds(
+ Canonical.join( edgeMerged.getPreds(),
+ edgeSummary.getPreds()
+ )
+ );
}
-
- addRefEdge(hrnSummary, hrnReferencee, edgeMerged);
}
// next transfer references _to_ hrn over to hrnSummary
while( itrReferencer.hasNext() ) {
RefEdge edge = itrReferencer.next();
RefEdge edgeMerged = edge.copy();
- edgeMerged.setDst(hrnSummary);
+ edgeMerged.setDst( hrnSummary );
RefSrcNode onReferencer = edge.getSrc();
- RefEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
- edge.getType(),
- edge.getField() );
+ RefEdge edgeSummary =
+ onReferencer.getReferenceTo( hrnSummary,
+ edge.getType(),
+ edge.getField()
+ );
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.unionORpreds( 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.unionORpreds( 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) {
+ protected void transferOnto( HeapRegionNode hrnA,
+ HeapRegionNode hrnB ) {
+
+ assert belongsToThis( hrnA );
+ assert belongsToThis( hrnB );
+ assert hrnA != hrnB;
- // clear references in and out of node b
- clearRefEdgesFrom(hrnB, null, null, true);
- clearRefEdgesTo(hrnB, null, null, true);
+ // 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();
+ RefEdge edge = itrReferencee.next();
HeapRegionNode hrnReferencee = edge.getDst();
- RefEdge edgeNew = edge.copy();
- edgeNew.setSrc(hrnB);
+ RefEdge edgeNew = edge.copy();
+ edgeNew.setSrc( hrnB );
+ edgeNew.setDst( hrnReferencee );
- addRefEdge(hrnB, hrnReferencee, edgeNew);
+ addRefEdge( hrnB, hrnReferencee, edgeNew );
}
Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
while( itrReferencer.hasNext() ) {
- RefEdge edge = itrReferencer.next();
- RefSrcNode onReferencer = edge.getSrc();
- RefEdge edgeNew = edge.copy();
- edgeNew.setDst(hrnB);
+ RefEdge edge = itrReferencer.next();
+ RefSrcNode rsnReferencer = edge.getSrc();
+ RefEdge edgeNew = edge.copy();
+ edgeNew.setSrc( rsnReferencer );
+ edgeNew.setDst( hrnB );
+
+ addRefEdge( rsnReferencer, hrnB, edgeNew );
+ }
+
+ // 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 );
- addRefEdge(onReferencer, hrnB, edgeNew);
+ clearRefEdgesFrom( hrn, null, null, true );
+
+ if( wipeVariableReferences ) {
+ clearRefEdgesTo( hrn, null, null, true );
+ } else {
+ clearNonVarRefEdgesTo( hrn );
}
- // replace hrnB reachability with hrnA's
- hrnB.setAlpha(hrnA.getAlpha() );
+ 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);
+ if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
+ != null
+ ) {
+ changesToPass = Canonical.add( 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.unionORpreds( 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);
+ if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
+ != null
+ ) {
+ changesToPass = Canonical.add( 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.unionORpreds( e.getBetaNew(),
+ localDelta
+ )
+ );
edgesWithNewBeta.add( e );
}
}
- public Set<Integer> calculateAliasedParamSet( FlatCall fc,
- boolean isStatic,
- FlatMethod fm ) {
+ // 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 );
- Hashtable<Integer, VariableNode> paramIndex2ln =
- new Hashtable<Integer, VariableNode>();
+ HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
+ if( hrnInContext == null ) {
+ return null;
+ }
- Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
- new Hashtable<Integer, HashSet<HeapRegionNode> >();
+ Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
+ while( refItr.hasNext() ) {
+ RefEdge re = refItr.next();
- for( int i = 0; i < fm.numParameters(); ++i ) {
- Integer paramIndex = new Integer( i );
- TempDescriptor tdParam = fm.getParameter( i );
- TypeDescriptor typeParam = tdParam.getType();
+ assert belongsToThis( re.getSrc() );
+ assert belongsToThis( re.getDst() );
- if( typeParam.isImmutable() && !typeParam.isArray() ) {
- // don't bother with this primitive parameter, it
- // cannot affect reachability
- continue;
+ if( !(re.getSrc() instanceof HeapRegionNode) ) {
+ continue;
}
- // now depending on whether the callee is static or not
- // we need to account for a "this" argument in order to
- // find the matching argument in the caller context
- TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
-
- VariableNode argLabel_i = getVariableNodeFromTemp(argTemp_i);
- paramIndex2ln.put(paramIndex, argLabel_i);
- }
-
- Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
- while( lnArgItr.hasNext() ) {
- Map.Entry me = (Map.Entry)lnArgItr.next();
- Integer index = (Integer) me.getKey();
- VariableNode lnArg_i = (VariableNode) me.getValue();
-
- HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
- HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
-
- // to find all reachable nodes, start with label referencees
- Iterator<RefEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
- while( edgeArgItr.hasNext() ) {
- RefEdge edge = edgeArgItr.next();
- todoNodes.add( edge.getDst() );
+ HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
+ if( !hrnSrc.isOutOfContext() ) {
+ continue;
}
-
- // then follow links until all reachable nodes have been found
- while( !todoNodes.isEmpty() ) {
- HeapRegionNode hrn = todoNodes.iterator().next();
- todoNodes.remove(hrn);
- reachableNodes.add(hrn);
-
- Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- RefEdge edge = edgeItr.next();
-
- if( !reachableNodes.contains(edge.getDst() ) ) {
- todoNodes.add(edge.getDst() );
- }
- }
+
+ if( srcType == null ) {
+ if( hrnSrc.getType() != null ) {
+ continue;
+ }
+ } else {
+ if( !srcType.equals( hrnSrc.getType() ) ) {
+ continue;
+ }
}
- // save for later
- paramIndex2reachableCallerNodes.put(index, reachableNodes);
- }
-
- Set<Integer> aliasedIndices = new HashSet<Integer>();
-
- // check for arguments that are aliased
- for( int i = 0; i < fm.numParameters(); ++i ) {
- for( int j = 0; j < i; ++j ) {
- HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
- HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
-
- // some parameters are immutable or primitive, so skip em
- if( s1 == null || s2 == null ) {
- continue;
- }
-
- Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
- intersection.retainAll(s2);
-
- if( !intersection.isEmpty() ) {
- aliasedIndices.add( new Integer( i ) );
- aliasedIndices.add( new Integer( j ) );
- }
+ if( !re.typeEquals( refType ) ) {
+ continue;
}
- }
-
- return aliasedIndices;
- }
+ if( !re.fieldEquals( refField ) ) {
+ continue;
+ }
- private String makeMapKey( Integer i, Integer j, String field ) {
- return i+","+j+","+field;
- }
-
- private String makeMapKey( Integer i, String field ) {
- return i+","+field;
- }
-
- // these hashtables are used during the mapping procedure to say that
- // with respect to some argument i there is an edge placed into some
- // category for mapping with respect to another argument index j
- // so the key into the hashtable is i, the value is a two-element vector
- // that contains in 0 the edge and in 1 the Integer index j
- private void ensureEmptyEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
- Integer indexI ) {
-
- Set<Vector> ei = edge_index_pairs.get( indexI );
- if( ei == null ) {
- ei = new HashSet<Vector>();
+ // tada! We found it!
+ return re;
}
- edge_index_pairs.put( indexI, ei );
- }
-
- private void addEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
- Integer indexI,
- RefEdge edge,
- Integer indexJ ) {
- Vector v = new Vector(); v.setSize( 2 );
- v.set( 0 , edge );
- v.set( 1 , indexJ );
- Set<Vector> ei = edge_index_pairs.get( indexI );
- if( ei == null ) {
- ei = new HashSet<Vector>();
- }
- ei.add( v );
- edge_index_pairs.put( indexI, ei );
+ return null;
}
- private ReachSet funcScriptR( ReachSet rsIn,
- ReachGraph ogCallee,
- MethodContext mc ) {
-
- ReachSet rsOut = new ReachSet( rsIn );
-
- Iterator itr = ogCallee.paramIndex2paramTokenPrimary.entrySet().iterator();
+ // used below to convert a ReachSet to its callee-context
+ // equivalent with respect to allocation sites in this graph
+ protected ReachSet toCalleeContext( ReachSet rs,
+ ExistPredSet preds,
+ Set<ReachTuple> oocTuples
+ ) {
+ ReachSet out = ReachSet.factory();
+
+ Iterator<ReachState> itr = rs.iterator();
while( itr.hasNext() ) {
- Map.Entry me = (Map.Entry) itr.next();
- Integer i = (Integer) me.getKey();
- ReachTuple p_i = (ReachTuple) me.getValue();
- ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( i );
-
- // skip this if there is no secondary token or the parameter
- // is part of the aliasing context
- if( s_i == null || mc.getAliasedParamIndices().contains( i ) ) {
- continue;
+ ReachState stateCaller = itr.next();
+
+ ReachState stateCallee = stateCaller;
+
+ Iterator<AllocSite> asItr = allocSites.iterator();
+ while( asItr.hasNext() ) {
+ AllocSite as = asItr.next();
+
+ ReachState stateNew = ReachState.factory();
+ Iterator<ReachTuple> rtItr = stateCallee.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+
+ // only translate this tuple if it is
+ // in the out-callee-context bag
+ if( !oocTuples.contains( rt ) ) {
+ stateNew = Canonical.add( stateNew, rt );
+ continue;
+ }
+
+ int age = as.getAgeCategory( rt.getHrnID() );
+
+ // this is the current mapping, where 0, 1, 2S were allocated
+ // in the current context, 0?, 1? and 2S? were allocated in a
+ // previous context, and we're translating to a future context
+ //
+ // 0 -> 0?
+ // 1 -> 1?
+ // 2S -> 2S?
+ // 2S* -> 2S?*
+ //
+ // 0? -> 2S?
+ // 1? -> 2S?
+ // 2S? -> 2S?
+ // 2S?* -> 2S?*
+
+ if( age == AllocSite.AGE_notInThisSite ) {
+ // things not from the site just go back in
+ stateNew = Canonical.add( stateNew, rt );
+
+ } else if( age == AllocSite.AGE_summary ||
+ rt.isOutOfContext()
+ ) {
+ // the in-context summary and all existing out-of-context
+ // stuff all become
+ stateNew = Canonical.add( stateNew,
+ ReachTuple.factory( as.getSummary(),
+ true, // multi
+ rt.getArity(),
+ true // out-of-context
+ )
+ );
+ } else {
+ // otherwise everything else just goes to an out-of-context
+ // version, everything else the same
+ Integer I = as.getAge( rt.getHrnID() );
+ assert I != null;
+
+ assert !rt.isMultiObject();
+
+ stateNew = Canonical.add( stateNew,
+ ReachTuple.factory( rt.getHrnID(),
+ rt.isMultiObject(),
+ rt.getArity(),
+ true // out-of-context
+ )
+ );
+ }
+ }
+
+ stateCallee = stateNew;
}
+
+ // attach the passed in preds
+ stateCallee = Canonical.attach( stateCallee,
+ preds );
- rsOut = rsOut.removeTokenAIfTokenB( p_i, s_i );
- }
-
- return rsOut;
- }
-
- // detects strong updates to the primary parameter object and
- // effects the removal of old edges in the calling graph
- private void effectCalleeStrongUpdates( Integer paramIndex,
- ReachGraph ogCallee,
- HeapRegionNode hrnCaller
- ) {
- Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
- assert idPrimary != null;
-
- HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
- assert hrnPrimary != null;
-
- TypeDescriptor typeParam = hrnPrimary.getType();
- assert typeParam.isClass();
-
- Set<String> fieldNamesToRemove = new HashSet<String>();
-
- ClassDescriptor cd = typeParam.getClassDesc();
- while( cd != null ) {
+ out = Canonical.add( out,
+ stateCallee
+ );
- Iterator fieldItr = cd.getFields();
- while( fieldItr.hasNext() ) {
-
- FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
- TypeDescriptor typeField = fd.getType();
- assert typeField != null;
-
- if( ogCallee.hasFieldBeenUpdated( hrnPrimary, fd.getSymbol() ) ) {
- clearRefEdgesFrom( hrnCaller, fd.getType(), fd.getSymbol(), false );
- }
- }
-
- cd = cd.getSuperDesc();
}
+ assert out.isCanonical();
+ return out;
}
- private boolean hasFieldBeenUpdated( HeapRegionNode hrnPrimary, String field ) {
+ // 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<RefEdge> itr = hrnPrimary.iteratorToReferencees();
+ Iterator<ReachState> itr = rs.iterator();
while( itr.hasNext() ) {
- RefEdge e = itr.next();
- if( e.fieldEquals( field ) && e.isInitialParam() ) {
- return false;
- }
- }
+ ReachState stateCallee = itr.next();
- return true;
- }
+ if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
- // resolveMethodCall() is used to incorporate a callee graph's effects into
- // *this* graph, which is the caller. This method can also be used, after
- // the entire analysis is complete, to perform parameter decomposition for
- // a given call chain.
- public void resolveMethodCall(FlatCall fc, // call site in caller method
- boolean isStatic, // whether it is a static method
- FlatMethod fm, // the callee method (when virtual, can be many)
- ReachGraph ogCallee, // the callee's current ownership graph
- MethodContext mc, // the aliasing context for this call
- ParameterDecomposition pd // if this is not null, we're calling after analysis
- ) {
-
- if( debugCallMap &&
- mc.getDescriptor().getSymbol().equals( debugCaller ) &&
- fm.getMethod().getSymbol().equals( debugCallee )
- ) {
-
- try {
- writeGraph("debug1BeforeCall",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- false, // show back edges to confirm graph validity
- false, // show parameter indices (unmaintained!)
- true, // hide subset reachability states
- true); // hide edge taints
-
- ogCallee.writeGraph("debug0Callee",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- false, // show back edges to confirm graph validity
- false, // show parameter indices (unmaintained!)
- true, // hide subset reachability states
- true); // hide edge taints
- } catch( IOException e ) {}
+ // starting from one callee state...
+ ReachSet rsCaller = ReachSet.factory( stateCallee );
- System.out.println( " "+mc+" is calling "+fm );
- }
+ // possibly branch it into many states, which any
+ // allocation site might do, so lots of derived states
+ Iterator<AllocSite> asItr = allocSites.iterator();
+ while( asItr.hasNext() ) {
+ AllocSite as = asItr.next();
+ rsCaller = Canonical.toCallerContext( rsCaller, as );
+ }
+
+ // then before adding each derived, now caller-context
+ // states to the output, attach the appropriate pred
+ // based on the source callee state
+ Iterator<ReachState> stateItr = rsCaller.iterator();
+ while( stateItr.hasNext() ) {
+ ReachState stateCaller = stateItr.next();
+ stateCaller = Canonical.attach( stateCaller,
+ calleeStatesSatisfied.get( stateCallee )
+ );
+ out = Canonical.add( out,
+ stateCaller
+ );
+ }
+ }
+ }
+ assert out.isCanonical();
+ return out;
+ }
+ // used below to convert a ReachSet to an equivalent
+ // version with shadow IDs merged into unshadowed IDs
+ protected ReachSet unshadow( ReachSet rs ) {
+ ReachSet out = rs;
+ Iterator<AllocSite> asItr = allocSites.iterator();
+ while( asItr.hasNext() ) {
+ AllocSite as = asItr.next();
+ out = Canonical.unshadow( out, as );
+ }
+ assert out.isCanonical();
+ return out;
+ }
- // define rewrite rules and other structures to organize data by parameter/argument index
- Hashtable<Integer, ReachSet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachSet>();
- Hashtable<Integer, ReachSet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachSet>();
-
- Hashtable<String, ReachSet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachSet>(); // select( i, j, f )
- Hashtable<String, ReachSet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachSet>(); // select( i, f )
- Hashtable<Integer, ReachSet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachSet>();
- Hashtable<Integer, ReachSet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachSet>();
- Hashtable<Integer, ReachSet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachSet>();
- Hashtable<Integer, ReachSet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachSet>();
- Hashtable<Integer, ReachSet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachSet>();
+ // 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 fmCallee,
+ Set<Integer> callerNodeIDsCopiedToCallee,
+ boolean writeDebugDOTs
+ ) {
- Hashtable<Integer, ReachSet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachSet>();
- Hashtable<Integer, ReachSet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachSet>();
- Hashtable<Integer, ReachSet> paramIndex2rewriteD = new Hashtable<Integer, ReachSet>();
+ // 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>();
- Hashtable<Integer, VariableNode> paramIndex2ln = new Hashtable<Integer, VariableNode>();
+ // 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>();
- paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
- paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
- paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity );
- paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity );
- paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity );
- paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity );
+ for( int i = 0; i < fmCallee.numParameters(); ++i ) {
+ TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
+ VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
- for( int i = 0; i < fm.numParameters(); ++i ) {
- Integer paramIndex = new Integer(i);
+ Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
+ Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
- if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
- // skip this immutable parameter
- continue;
- }
+ toVisitInCaller.add( vnArgCaller );
- // setup H (primary)
- Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex );
- assert ogCallee.id2hrn.containsKey( idPrimary );
- HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary );
- assert hrnPrimary != null;
- paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) );
-
- // setup J (primary->X)
- Iterator<RefEdge> p2xItr = hrnPrimary.iteratorToReferencees();
- while( p2xItr.hasNext() ) {
- RefEdge p2xEdge = p2xItr.next();
-
- // we only care about initial parameter edges here
- if( !p2xEdge.isInitialParam() ) { continue; }
-
- HeapRegionNode hrnDst = p2xEdge.getDst();
-
- if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
- Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
- while( jItr.hasNext() ) {
- Integer j = jItr.next();
- paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ),
- toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
- }
-
- } else {
- assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
- paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
- toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
- }
- }
-
- // setup K (primary)
- TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
- assert tdParamQ != null;
- VariableNode lnParamQ = ogCallee.td2vn.get( tdParamQ );
- assert lnParamQ != null;
- RefEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
- assert edgeSpecialQ_i != null;
- ReachSet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
-
- ReachTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
- ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
-
- ReachSet K_p = new ReachSet().makeCanonical();
- ReachSet K_p2 = new ReachSet().makeCanonical();
- if( s_i == null ) {
- K_p = qBeta;
- } else {
- // sort qBeta into K_p1 and K_p2
- Iterator<ReachState> ttsItr = qBeta.iterator();
- while( ttsItr.hasNext() ) {
- ReachState tts = ttsItr.next();
- if( s_i != null && tts.containsBoth( p_i, s_i ) ) {
- K_p2 = K_p2.union( tts );
- } else {
- K_p = K_p.union( tts );
- }
- }
- }
- paramIndex2rewriteK_p .put( paramIndex, K_p );
- paramIndex2rewriteK_p2.put( paramIndex, K_p2 );
+ while( !toVisitInCaller.isEmpty() ) {
+ RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
+ toVisitInCaller.remove( rsnCaller );
+ visitedInCaller.add( rsnCaller );
+
+ Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
+ while( itrRefEdges.hasNext() ) {
+ RefEdge reCaller = itrRefEdges.next();
+ HeapRegionNode hrnCaller = reCaller.getDst();
+
+ callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
+ reachableCallerNodes.add( hrnCaller );
+
+ if( reCaller.getSrc() instanceof HeapRegionNode ) {
+ reachableCallerEdges.add( reCaller );
+ } else {
+ if( rsnCaller.equals( vnArgCaller ) ) {
+ reachableCallerArgEdges2paramIndex.put( reCaller, i );
+ } else {
+ oocCallerEdges.add( reCaller );
+ }
+ }
+
+ if( !visitedInCaller.contains( hrnCaller ) ) {
+ toVisitInCaller.add( hrnCaller );
+ }
+
+ } // end edge iteration
+ } // end visiting heap nodes in caller
+ } // end iterating over parameters as starting points
+
+
+ // 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() ) {
+ Integer hrnID = itrInContext.next();
+ HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
+
+ Iterator<RefEdge> itrMightCross =
+ hrnCallerAndInContext.iteratorToReferencers();
+ while( itrMightCross.hasNext() ) {
+ 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) rsnCallerAndOutContext;
+
+ // is this source node out-of-context?
+ if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
+ // no, skip this edge
+ continue;
+ }
- // if there is a secondary node, compute the rest of the rewrite rules
- if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
+ // okay, we got one
+ oocCallerEdges.add( edgeMightCross );
- // setup H (secondary)
- Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex );
- assert ogCallee.id2hrn.containsKey( idSecondary );
- HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary );
- assert hrnSecondary != null;
- paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
+ // 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();
- // setup J (secondary->X)
- Iterator<RefEdge> s2xItr = hrnSecondary.iteratorToReferencees();
- while( s2xItr.hasNext() ) {
- RefEdge s2xEdge = s2xItr.next();
-
- if( !s2xEdge.isInitialParam() ) { continue; }
-
- HeapRegionNode hrnDst = s2xEdge.getDst();
-
- if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) {
- Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator();
- while( jItr.hasNext() ) {
- Integer j = jItr.next();
- paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
- }
-
- } else {
- assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
- paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) );
- }
- }
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
- // setup K (secondary)
- TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
- assert tdParamR != null;
- VariableNode lnParamR = ogCallee.td2vn.get( tdParamR );
- assert lnParamR != null;
- RefEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
- assert edgeSpecialR_i != null;
- paramIndex2rewriteK_s.put( paramIndex,
- toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
+ oocTuples.add( rt );
+ }
+ }
}
-
+ }
- // now depending on whether the callee is static or not
- // we need to account for a "this" argument in order to
- // find the matching argument in the caller context
- TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex );
- // remember which caller arg label maps to param index
- VariableNode argLabel_i = getVariableNodeFromTemp( argTemp_i );
- paramIndex2ln.put( paramIndex, argLabel_i );
+ // the callee view is a new graph: DON'T MODIFY *THIS* graph
+ ReachGraph rg = new ReachGraph();
- // do a callee-effect strong update pre-pass here
- if( argTemp_i.getType().isClass() ) {
+ // add nodes to callee graph
+ Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
+ while( hrnItr.hasNext() ) {
+ HeapRegionNode hrnCaller = hrnItr.next();
- Iterator<RefEdge> edgeItr = argLabel_i.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- RefEdge edge = edgeItr.next();
- HeapRegionNode hrn = edge.getDst();
+ assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
+ assert !rg.id2hrn.containsKey( hrnCaller.getID() );
+
+ ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
+ ExistPredSet preds = ExistPredSet.factory( pred );
+
+ rg.createNewHeapRegionNode( hrnCaller.getID(),
+ hrnCaller.isSingleObject(),
+ hrnCaller.isNewSummary(),
+ hrnCaller.isFlagged(),
+ false, // out-of-context?
+ hrnCaller.getType(),
+ hrnCaller.getAllocSite(),
+ toCalleeContext( hrnCaller.getInherent(),
+ preds,
+ oocTuples
+ ),
+ toCalleeContext( hrnCaller.getAlpha(),
+ preds,
+ oocTuples
+ ),
+ 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,
+ true, // out-of-callee-context
+ false // out-of-caller-context
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge reCallee =
+ new RefEdge( vnCallee,
+ hrnDstCallee,
+ reArg.getType(),
+ reArg.getField(),
+ toCalleeContext( reArg.getBeta(),
+ preds,
+ oocTuples
+ ),
+ 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-callee-context
+ false // out-of-caller-context
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge reCallee =
+ new RefEdge( hrnSrcCallee,
+ hrnDstCallee,
+ reCaller.getType(),
+ reCaller.getField(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
+ ),
+ 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;
+ boolean outOfCalleeContext;
+ boolean outOfCallerContext;
+
+ if( rsnCaller instanceof VariableNode ) {
+ VariableNode vnCaller = (VariableNode) rsnCaller;
+ oocNodeType = null;
+ oocReach = rsetEmpty;
+ oocPredSrcTemp = vnCaller.getTempDescriptor();
+ outOfCalleeContext = true;
+ outOfCallerContext = false;
- if( (hrn.getNumReferencers() == 1) || // case 1
- (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
- ) {
- if( !DISABLE_STRONG_UPDATES ) {
- effectCalleeStrongUpdates( paramIndex, ogCallee, hrn );
- }
- }
- }
+ } else {
+ HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
+ assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
+ oocNodeType = hrnSrcCaller.getType();
+ oocReach = hrnSrcCaller.getAlpha();
+ oocPredSrcID = hrnSrcCaller.getID();
+ if( hrnSrcCaller.isOutOfContext() ) {
+ outOfCalleeContext = false;
+ outOfCallerContext = true;
+ } else {
+ outOfCalleeContext = true;
+ outOfCallerContext = false;
+ }
}
- // then calculate the d and D rewrite rules
- ReachSet d_i_p = new ReachSet().makeCanonical();
- ReachSet d_i_s = new ReachSet().makeCanonical();
- Iterator<RefEdge> edgeItr = argLabel_i.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- RefEdge edge = edgeItr.next();
-
- d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
- d_i_s = d_i_s.union( edge.getBeta() );
- }
- paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
- paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
+ ExistPred pred =
+ ExistPred.factory( oocPredSrcTemp,
+ oocPredSrcID,
+ hrnDstCallee.getID(),
+ reCaller.getType(),
+ reCaller.getField(),
+ null,
+ outOfCalleeContext,
+ outOfCallerContext
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge oocEdgeExisting =
+ rg.getOutOfContextReferenceTo( hrnDstCallee,
+ oocNodeType,
+ reCaller.getType(),
+ reCaller.getField()
+ );
+
+ if( oocEdgeExisting == null ) {
+ // for consistency, map one out-of-context "identifier"
+ // to one heap region node id, otherwise no convergence
+ String oocid = "oocid"+
+ fmCallee+
+ hrnDstCallee.getIDString()+
+ oocNodeType+
+ reCaller.getType()+
+ reCaller.getField();
+
+ Integer oocHrnID = oocid2hrnid.get( oocid );
+
+ HeapRegionNode hrnCalleeAndOutContext;
+
+ if( oocHrnID == null ) {
+
+ hrnCalleeAndOutContext =
+ rg.createNewHeapRegionNode( null, // ID
+ false, // single object?
+ false, // new summary?
+ false, // flagged?
+ true, // out-of-context?
+ oocNodeType,
+ null, // alloc site, shouldn't be used
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ ),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ ),
+ preds,
+ "out-of-context"
+ );
+
+ oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
+
+ } else {
+
+ // the mapping already exists, so see if node is there
+ hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
+
+ if( hrnCalleeAndOutContext == null ) {
+ // nope, make it
+ hrnCalleeAndOutContext =
+ rg.createNewHeapRegionNode( oocHrnID, // ID
+ false, // single object?
+ false, // new summary?
+ false, // flagged?
+ true, // out-of-context?
+ oocNodeType,
+ null, // alloc site, shouldn't be used
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ ),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ ),
+ preds,
+ "out-of-context"
+ );
+ } else {
+ // otherwise it is there, so merge reachability
+ hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ )
+ )
+ );
+ }
+ }
- // TODO: we should only do this when we need it, and then
- // memoize it for the rest of the mapping procedure
- ReachSet D_i = d_i_s.exhaustiveArityCombinations();
- paramIndex2rewriteD.put( paramIndex, D_i );
+ rg.addRefEdge( hrnCalleeAndOutContext,
+ hrnDstCallee,
+ new RefEdge( hrnCalleeAndOutContext,
+ hrnDstCallee,
+ reCaller.getType(),
+ reCaller.getField(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
+ ),
+ preds
+ )
+ );
+
+ } else {
+ // the out-of-context edge already exists
+ oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
+ )
+ )
+ );
+
+ oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
+ reCaller.getPreds()
+ )
+ );
+
+ HeapRegionNode hrnCalleeAndOutContext =
+ (HeapRegionNode) oocEdgeExisting.getSrc();
+ hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ )
+ )
+ );
+
+
+ }
}
- // with respect to each argument, map parameter effects into caller
- HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
- HashSet<RefEdge> edgesWithNewBeta = new HashSet<RefEdge>();
-
- Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
- new Hashtable<Integer, Set<HeapRegionNode> >();
-
- Hashtable<Integer, Set<HeapRegionNode> > pi2r =
- new Hashtable<Integer, Set<HeapRegionNode> >();
+ if( writeDebugDOTs ) {
+ try {
+ rg.writeGraph( "calleeview",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
+ }
- Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
+ return rg;
+ }
- Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
- while( lnArgItr.hasNext() ) {
- Map.Entry me = (Map.Entry) lnArgItr.next();
- Integer index = (Integer) me.getKey();
- VariableNode lnArg_i = (VariableNode) me.getValue();
-
- Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
- Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
- Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
+ private static Hashtable<String, Integer> oocid2hrnid =
+ new Hashtable<String, Integer>();
- // find all reachable nodes starting with label referencees
- Iterator<RefEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
- while( edgeArgItr.hasNext() ) {
- RefEdge edge = edgeArgItr.next();
- HeapRegionNode hrn = edge.getDst();
- dr.add( hrn );
+ // useful since many graphs writes in the method call debug code
+ private static boolean resolveMethodDebugDOTwriteLabels = true;
+ private static boolean resolveMethodDebugDOTselectTemps = true;
+ private static boolean resolveMethodDebugDOTpruneGarbage = true;
+ private static boolean resolveMethodDebugDOThideSubsetReach = false;
+ private static boolean resolveMethodDebugDOThideEdgeTaints = true;
- if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
- defParamObj.add( hrn );
- }
- Iterator<RefEdge> edgeHrnItr = hrn.iteratorToReferencees();
- while( edgeHrnItr.hasNext() ) {
- RefEdge edger = edgeHrnItr.next();
- todo.add( edger.getDst() );
- }
- // then follow links until all reachable nodes have been found
- while( !todo.isEmpty() ) {
- HeapRegionNode hrnr = todo.iterator().next();
- todo.remove( hrnr );
-
- r.add( hrnr );
-
- Iterator<RefEdge> edgeItr = hrnr.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- RefEdge edger = edgeItr.next();
- if( !r.contains( edger.getDst() ) ) {
- todo.add( edger.getDst() );
- }
- }
- }
+ public void
+ resolveMethodCall( FlatCall fc,
+ FlatMethod fmCallee,
+ ReachGraph rgCallee,
+ Set<Integer> callerNodeIDsCopiedToCallee,
+ boolean writeDebugDOTs
+ ) {
- if( hrn.isSingleObject() ) {
- r.remove( hrn );
- }
- }
- pi2dr.put( index, dr );
- pi2r .put( index, r );
+ if( writeDebugDOTs ) {
+ try {
+ rgCallee.writeGraph( "callee",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+
+ writeGraph( "caller00In",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
+ } catch( IOException e ) {}
}
- assert defParamObj.size() <= fm.numParameters();
- // if we're in parameter decomposition mode, report some results here
- if( pd != null ) {
- Iterator mapItr;
+ // 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.
- // report primary parameter object mappings
- mapItr = pi2dr.entrySet().iterator();
- while( mapItr.hasNext() ) {
- Map.Entry me = (Map.Entry) mapItr.next();
- Integer paramIndex = (Integer) me.getKey();
- Set<HeapRegionNode> hrnAset = (Set<HeapRegionNode>) me.getValue();
- Iterator<HeapRegionNode> hrnItr = hrnAset.iterator();
- while( hrnItr.hasNext() ) {
- HeapRegionNode hrnA = hrnItr.next();
- pd.mapRegionToParamObject( hrnA, paramIndex );
- }
- }
- // report parameter-reachable mappings
- mapItr = pi2r.entrySet().iterator();
- while( mapItr.hasNext() ) {
- Map.Entry me = (Map.Entry) mapItr.next();
- Integer paramIndex = (Integer) me.getKey();
- Set<HeapRegionNode> hrnRset = (Set<HeapRegionNode>) me.getValue();
-
- Iterator<HeapRegionNode> hrnItr = hrnRset.iterator();
- while( hrnItr.hasNext() ) {
- HeapRegionNode hrnR = hrnItr.next();
- pd.mapRegionToParamReachable( hrnR, paramIndex );
- }
+ // 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 );
+ }
}
- // and we're done in this method for special param decomp mode
- return;
- }
-
-
- // now iterate over reachable nodes to rewrite their alpha, and
- // classify edges found for beta rewrite
- Hashtable<ReachTuple, ReachSet> tokens2states = new Hashtable<ReachTuple, ReachSet>();
-
- Hashtable< Integer, Set<Vector> > edges_p2p = new Hashtable< Integer, Set<Vector> >();
- Hashtable< Integer, Set<Vector> > edges_p2s = new Hashtable< Integer, Set<Vector> >();
- Hashtable< Integer, Set<Vector> > edges_s2p = new Hashtable< Integer, Set<Vector> >();
- Hashtable< Integer, Set<Vector> > edges_s2s = new Hashtable< Integer, Set<Vector> >();
- Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
- Hashtable< Integer, Set<Vector> > edges_up_r = new Hashtable< Integer, Set<Vector> >();
-
- // so again, with respect to some arg i...
- lnArgItr = paramIndex2ln.entrySet().iterator();
- while( lnArgItr.hasNext() ) {
- Map.Entry me = (Map.Entry) lnArgItr.next();
- Integer index = (Integer) me.getKey();
- VariableNode lnArg_i = (VariableNode) me.getValue();
-
- ReachTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index );
- ReachTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( index );
- assert p_i != null;
-
- ensureEmptyEdgeIndexPair( edges_p2p, index );
- ensureEmptyEdgeIndexPair( edges_p2s, index );
- ensureEmptyEdgeIndexPair( edges_s2p, index );
- ensureEmptyEdgeIndexPair( edges_s2s, index );
- ensureEmptyEdgeIndexPair( edges_up_dr, index );
- ensureEmptyEdgeIndexPair( edges_up_r, index );
-
- Set<HeapRegionNode> dr = pi2dr.get( index );
- Iterator<HeapRegionNode> hrnItr = dr.iterator();
- while( hrnItr.hasNext() ) {
- // this heap region is definitely an "a_i" or primary by virtue of being in dr
- HeapRegionNode hrn = hrnItr.next();
-
- tokens2states.clear();
- tokens2states.put( p_i, hrn.getAlpha() );
-
- rewriteCallerReachability( index,
- hrn,
- null,
- paramIndex2rewriteH_p.get( index ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- nodesWithNewAlpha.add( hrn );
-
- // sort edges
- Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
- while( edgeItr.hasNext() ) {
- RefEdge edge = edgeItr.next();
- RefSrcNode on = edge.getSrc();
-
- boolean edge_classified = false;
-
-
- if( on instanceof HeapRegionNode ) {
- // hrn0 may be "a_j" and/or "r_j" or even neither
- HeapRegionNode hrn0 = (HeapRegionNode) on;
-
- Iterator itr = pi2dr.entrySet().iterator();
- while( itr.hasNext() ) {
- Map.Entry mo = (Map.Entry) itr.next();
- Integer pi = (Integer) mo.getKey();
- Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
-
- if( dr_i.contains( hrn0 ) ) {
- addEdgeIndexPair( edges_p2p, pi, edge, index );
- edge_classified = true;
- }
- }
+ // 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;
+ }
+ }
+ }
- itr = pi2r.entrySet().iterator();
- while( itr.hasNext() ) {
- Map.Entry mo = (Map.Entry) itr.next();
- Integer pi = (Integer) mo.getKey();
- Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
+ rsnCallers.add( rsnCaller );
+ matchedOutOfContext = true;
+ }
- if( r_i.contains( hrn0 ) ) {
- addEdgeIndexPair( edges_s2p, pi, edge, index );
- edge_classified = true;
- }
- }
- }
+ if( !rsnCallers.isEmpty() ) {
+ calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
+ }
+ }
- // all of these edges are upstream of directly reachable objects
- if( !edge_classified ) {
- addEdgeIndexPair( edges_up_dr, index, edge, index );
- }
- }
+ 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 ) {
- Set<HeapRegionNode> r = pi2r.get( index );
- hrnItr = r.iterator();
- while( hrnItr.hasNext() ) {
- // this heap region is definitely an "r_i" or secondary by virtue of being in r
- HeapRegionNode hrn = hrnItr.next();
-
- if( paramIndex2rewriteH_s.containsKey( index ) ) {
-
- tokens2states.clear();
- tokens2states.put( p_i, new ReachSet().makeCanonical() );
- tokens2states.put( s_i, hrn.getAlpha() );
-
- rewriteCallerReachability( index,
- hrn,
- null,
- paramIndex2rewriteH_s.get( index ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- nodesWithNewAlpha.add( hrn );
- }
-
- // sort edges
- Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
- while( edgeItr.hasNext() ) {
- RefEdge edge = edgeItr.next();
- RefSrcNode on = edge.getSrc();
-
- boolean edge_classified = false;
-
- if( on instanceof HeapRegionNode ) {
- // hrn0 may be "a_j" and/or "r_j" or even neither
- HeapRegionNode hrn0 = (HeapRegionNode) on;
-
- Iterator itr = pi2dr.entrySet().iterator();
- while( itr.hasNext() ) {
- Map.Entry mo = (Map.Entry) itr.next();
- Integer pi = (Integer) mo.getKey();
- Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
-
- if( dr_i.contains( hrn0 ) ) {
- addEdgeIndexPair( edges_p2s, pi, edge, index );
- edge_classified = true;
- }
- }
-
- itr = pi2r.entrySet().iterator();
- while( itr.hasNext() ) {
- Map.Entry mo = (Map.Entry) itr.next();
- Integer pi = (Integer) mo.getKey();
- Set<HeapRegionNode> r_i = (Set<HeapRegionNode>) mo.getValue();
-
- if( r_i.contains( hrn0 ) ) {
- addEdgeIndexPair( edges_s2s, pi, edge, index );
- edge_classified = true;
- }
- }
- }
+ // parameter defined here is the symbol in the callee
+ TempDescriptor tdParam = fmCallee.getParameter( i );
+ VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
- // these edges are all upstream of some reachable node
- if( !edge_classified ) {
- addEdgeIndexPair( edges_up_r, index, edge, index );
- }
- }
+ 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 );
+ }
+ }
+
+ }
}
}
- // and again, with respect to some arg i...
- lnArgItr = paramIndex2ln.entrySet().iterator();
- while( lnArgItr.hasNext() ) {
- Map.Entry me = (Map.Entry) lnArgItr.next();
- Integer index = (Integer) me.getKey();
- VariableNode lnArg_i = (VariableNode) me.getValue();
- // update reachable edges
- Iterator edgeItr = edges_p2p.get( index ).iterator();
- while( edgeItr.hasNext() ) {
- Vector mo = (Vector) edgeItr.next();
- RefEdge edge = (RefEdge) mo.get( 0 );
- Integer indexJ = (Integer) mo.get( 1 );
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller20BeforeWipe",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
+ }
- if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
- indexJ,
- edge.getField() ) ) ) {
- continue;
- }
- ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
- assert p_j != null;
-
- tokens2states.clear();
- tokens2states.put( p_j, edge.getBeta() );
-
- rewriteCallerReachability( index,
- null,
- edge,
- paramIndex2rewriteJ_p2p.get( makeMapKey( index,
- indexJ,
- edge.getField() ) ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- edgesWithNewBeta.add( edge );
- }
+ // 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 );
+ }
- edgeItr = edges_p2s.get( index ).iterator();
- while( edgeItr.hasNext() ) {
- Vector mo = (Vector) edgeItr.next();
- RefEdge edge = (RefEdge) mo.get( 0 );
- Integer indexJ = (Integer) mo.get( 1 );
- if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
- edge.getField() ) ) ) {
- continue;
- }
- ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
- assert s_j != null;
-
- tokens2states.clear();
- tokens2states.put( s_j, edge.getBeta() );
-
- rewriteCallerReachability( index,
- null,
- edge,
- paramIndex2rewriteJ_p2s.get( makeMapKey( index,
- edge.getField() ) ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- edgesWithNewBeta.add( edge );
- }
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller30BeforeAddingNodes",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
+ }
- edgeItr = edges_s2p.get( index ).iterator();
- while( edgeItr.hasNext() ) {
- Vector mo = (Vector) edgeItr.next();
- RefEdge edge = (RefEdge) mo.get( 0 );
- Integer indexJ = (Integer) mo.get( 1 );
+ // 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
- if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) {
- continue;
- }
+ // 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();
- ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
- assert p_j != null;
-
- tokens2states.clear();
- tokens2states.put( p_j, edge.getBeta() );
-
- rewriteCallerReachability( index,
- null,
- edge,
- paramIndex2rewriteJ_s2p.get( index ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- edgesWithNewBeta.add( edge );
+ // 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;
}
-
- edgeItr = edges_s2s.get( index ).iterator();
- while( edgeItr.hasNext() ) {
- Vector mo = (Vector) edgeItr.next();
- RefEdge edge = (RefEdge) mo.get( 0 );
- Integer indexJ = (Integer) mo.get( 1 );
-
- if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) {
- continue;
- }
-
- ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
- assert s_j != null;
-
- tokens2states.clear();
- tokens2states.put( s_j, edge.getBeta() );
-
- rewriteCallerReachability( index,
- null,
- edge,
- paramIndex2rewriteJ_s2s.get( index ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- edgesWithNewBeta.add( edge );
+ 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
+ )
+ );
- // update directly upstream edges
- Hashtable<RefEdge, ChangeSet> edgeUpstreamPlannedChanges =
- new Hashtable<RefEdge, ChangeSet>();
-
- HashSet<RefEdge> edgesDirectlyUpstream =
- new HashSet<RefEdge>();
-
- edgeItr = edges_up_dr.get( index ).iterator();
- while( edgeItr.hasNext() ) {
- Vector mo = (Vector) edgeItr.next();
- RefEdge edge = (RefEdge) mo.get( 0 );
- Integer indexJ = (Integer) mo.get( 1 );
-
- edgesDirectlyUpstream.add( edge );
-
- ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
- assert p_j != null;
-
- // start with K_p2 and p_j
- tokens2states.clear();
- tokens2states.put( p_j, edge.getBeta() );
-
- rewriteCallerReachability( index,
- null,
- edge,
- paramIndex2rewriteK_p2.get( index ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- true,
- edgeUpstreamPlannedChanges );
-
- // and add in s_j, if required, and do K_p
- ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
- if( s_j != null ) {
- tokens2states.put( s_j, edge.getBeta() );
- }
-
- rewriteCallerReachability( index,
- null,
- edge,
- paramIndex2rewriteK_p.get( index ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- true,
- edgeUpstreamPlannedChanges );
-
- edgesWithNewBeta.add( edge );
- }
+ hrnCaller.setPreds( preds );
+ }
- propagateTokensOverEdges( edgesDirectlyUpstream,
- edgeUpstreamPlannedChanges,
- edgesWithNewBeta );
-
- // update upstream edges
- edgeUpstreamPlannedChanges =
- new Hashtable<RefEdge, ChangeSet>();
- HashSet<RefEdge> edgesUpstream =
- new HashSet<RefEdge>();
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller31BeforeAddingEdges",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
+ }
- edgeItr = edges_up_r.get( index ).iterator();
- while( edgeItr.hasNext() ) {
- Vector mo = (Vector) edgeItr.next();
- RefEdge edge = (RefEdge) mo.get( 0 );
- Integer indexJ = (Integer) mo.get( 1 );
- if( !paramIndex2rewriteK_s.containsKey( index ) ) {
- continue;
- }
+ // 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>();
- edgesUpstream.add( edge );
+ Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
+ new Hashtable<RefEdge, ChangeSet>();
- ReachTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
- assert p_j != null;
- ReachTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
- assert s_j != null;
+ // 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();
- tokens2states.clear();
- tokens2states.put( p_j, rsWttsEmpty );
- tokens2states.put( s_j, edge.getBeta() );
+ HeapRegionNode hrnDstCallee = reCallee.getDst();
+ AllocSite asDst = hrnDstCallee.getAllocSite();
+ allocSites.add( asDst );
- rewriteCallerReachability( index,
- null,
- edge,
- paramIndex2rewriteK_s.get( index ),
- tokens2states,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- true,
- edgeUpstreamPlannedChanges );
+ Integer hrnIDDstShadow =
+ asDst.getShadowIDfromID( hrnDstCallee.getID() );
+
+ HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
+ assert hrnDstCaller != null;
+
+
+ RefSrcNode rsnCallee = reCallee.getSrc();
- edgesWithNewBeta.add( edge );
- }
+ Set<RefSrcNode> rsnCallers =
+ new HashSet<RefSrcNode>();
+
+ Set<RefSrcNode> oocCallers =
+ calleeEdges2oocCallerSrcMatches.get( reCallee );
- propagateTokensOverEdges( edgesUpstream,
- edgeUpstreamPlannedChanges,
- edgesWithNewBeta );
+ 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 );
+ }
- } // end effects per argument/parameter map
+ } 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 predsPreCallee = state.getPreds();
+
+ if( state.isEmpty() ) {
+ continue;
+ }
+
+ Iterator<ExistPred> predItr = predsPreCallee.iterator();
+ while( predItr.hasNext() ) {
+ ExistPred pred = predItr.next();
+ ReachState old = pred.ne_state;
+
+ if( old == null ) {
+ old = rstateEmpty;
+ }
- // commit changes to alpha and beta
- Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
- while( nodeItr.hasNext() ) {
- nodeItr.next().applyAlphaNew();
- }
+ cs = Canonical.add( cs,
+ ChangeTuple.factory( old,
+ state
+ )
+ );
+ }
+ }
+
- Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
- while( edgeItr.hasNext() ) {
- edgeItr.next().applyBetaNew();
+ // 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.unionORpreds( 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 );
+ }
+ }
+ }
}
-
- // verify the existence of allocation sites and their
- // shadows from the callee in the context of this caller graph
- // then map allocated nodes of callee onto the caller shadows
- // of them
- Hashtable<ReachTuple, ReachSet> tokens2statesEmpty = new Hashtable<ReachTuple, ReachSet>();
- Iterator<AllocSite> asItr = ogCallee.allocSites.iterator();
- while( asItr.hasNext() ) {
- AllocSite allocSite = asItr.next();
-
- // grab the summary in the caller just to make sure
- // the allocation site has nodes in the caller
- HeapRegionNode hrnSummary = getSummaryNode( allocSite );
-
- // assert that the shadow nodes have no reference edges
- // because they're brand new to the graph, or last time
- // they were used they should have been cleared of edges
- HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
- assert hrnShadowSummary.getNumReferencers() == 0;
- assert hrnShadowSummary.getNumReferencees() == 0;
-
- // then bring g_ij onto g'_ij and rewrite
- HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite );
- hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) );
-
- // shadow nodes only are touched by a rewrite one time,
- // so rewrite and immediately commit--and they don't belong
- // to a particular parameter, so use a bogus param index
- // that pulls a self-rewrite out of H
- rewriteCallerReachability( bogusIndex,
- hrnShadowSummary,
- null,
- funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ),
- tokens2statesEmpty,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- hrnShadowSummary.applyAlphaNew();
-
-
- for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
- Integer idIth = allocSite.getIthOldest(i);
- assert id2hrn.containsKey(idIth);
- HeapRegionNode hrnIth = id2hrn.get(idIth);
-
- Integer idShadowIth = -(allocSite.getIthOldest(i));
- assert id2hrn.containsKey(idShadowIth);
- HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
- assert hrnIthShadow.getNumReferencers() == 0;
- assert hrnIthShadow.getNumReferencees() == 0;
-
- assert ogCallee.id2hrn.containsKey(idIth);
- HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
- hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
-
- rewriteCallerReachability( bogusIndex,
- hrnIthShadow,
- null,
- funcScriptR( hrnIthShadow.getAlpha(), ogCallee, mc ),
- tokens2statesEmpty,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- hrnIthShadow.applyAlphaNew();
- }
- }
- // for every heap region->heap region edge in the
- // callee graph, create the matching edge or edges
- // in the caller graph
- Set sCallee = ogCallee.id2hrn.entrySet();
- Iterator iCallee = sCallee.iterator();
-
- while( iCallee.hasNext() ) {
- Map.Entry meCallee = (Map.Entry) iCallee.next();
- Integer idCallee = (Integer) meCallee.getKey();
- HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
-
- Iterator<RefEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
- while( heapRegionsItrCallee.hasNext() ) {
- RefEdge edgeCallee = heapRegionsItrCallee.next();
- HeapRegionNode hrnChildCallee = edgeCallee.getDst();
- Integer idChildCallee = hrnChildCallee.getID();
-
- // only address this edge if it is not a special initial edge
- if( !edgeCallee.isInitialParam() ) {
-
- // now we know that in the callee method's ownership graph
- // there is a heap region->heap region reference edge given
- // by heap region pointers:
- // hrnCallee -> heapChildCallee
- //
- // or by the ownership-graph independent ID's:
- // idCallee -> idChildCallee
-
- // make the edge with src and dst so beta info is
- // calculated once, then copy it for each new edge in caller
-
- RefEdge edgeNewInCallerTemplate = new RefEdge( null,
- null,
- edgeCallee.getType(),
- edgeCallee.getField(),
- false,
- funcScriptR( toShadowTokens( ogCallee,
- edgeCallee.getBeta()
- ),
- ogCallee,
- mc )
- );
-
- rewriteCallerReachability( bogusIndex,
- null,
- edgeNewInCallerTemplate,
- edgeNewInCallerTemplate.getBeta(),
- tokens2statesEmpty,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- edgeNewInCallerTemplate.applyBetaNew();
-
-
- // So now make a set of possible source heaps in the caller graph
- // and a set of destination heaps in the caller graph, and make
- // a reference edge in the caller for every possible (src,dst) pair
- HashSet<HeapRegionNode> possibleCallerSrcs =
- getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
- (HeapRegionNode) edgeCallee.getSrc(),
- pi2dr,
- pi2r );
-
- HashSet<HeapRegionNode> possibleCallerDsts =
- getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
- edgeCallee.getDst(),
- pi2dr,
- pi2r );
-
- // make every possible pair of {srcSet} -> {dstSet} edges in the caller
- Iterator srcItr = possibleCallerSrcs.iterator();
- while( srcItr.hasNext() ) {
- HeapRegionNode src = (HeapRegionNode) srcItr.next();
-
- if( !hasMatchingField( src, edgeCallee ) ) {
- // prune this source node possibility
- continue;
- }
- Iterator dstItr = possibleCallerDsts.iterator();
- while( dstItr.hasNext() ) {
- HeapRegionNode dst = (HeapRegionNode) dstItr.next();
-
- if( !hasMatchingType( edgeCallee, dst ) ) {
- // prune
- continue;
- }
-
-
-
-
-
- // otherwise the caller src and dst pair can match the edge, so make it
- TypeDescriptor tdNewEdge =
- mostSpecificType( edgeCallee.getType(),
- hrnChildCallee.getType(),
- dst.getType()
- );
-
- RefEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
- edgeNewInCaller.setSrc( src );
- edgeNewInCaller.setDst( dst );
- edgeNewInCaller.setType( tdNewEdge );
-
-
- // handle taint info if callee created this edge
- // added by eom
- Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
- Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
- HashSet<Integer> paramSet=new HashSet<Integer>();
- if(pParamSet!=null){
- paramSet.addAll(pParamSet);
- }
- if(sParamSet!=null){
- paramSet.addAll(sParamSet);
- }
- Iterator<Integer> paramIter=paramSet.iterator();
- int newTaintIdentifier=0;
- while(paramIter.hasNext()){
- Integer paramIdx=paramIter.next();
- edgeNewInCaller.tainedBy(paramIdx);
- }
-
- RefEdge edgeExisting = src.getReferenceTo( dst,
- edgeNewInCaller.getType(),
- edgeNewInCaller.getField() );
- if( edgeExisting == null ) {
- // if this edge doesn't exist in the caller, create it
- addRefEdge( src, dst, edgeNewInCaller );
-
- } else {
- // if it already exists, merge with it
- edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
- }
- }
- }
- }
- }
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller35BeforeAssignReturnValue",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
}
- // return value may need to be assigned in caller
+ // 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 lnLhsCaller = getVariableNodeFromTemp( returnTemp );
- clearRefEdgesFrom( lnLhsCaller, null, null, true );
+ VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
+ clearRefEdgesFrom( vnLhsCaller, null, null, true );
- VariableNode lnReturnCallee = ogCallee.getVariableNodeFromTemp( tdReturn );
- Iterator<RefEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
- while( edgeCalleeItr.hasNext() ) {
- RefEdge edgeCallee = edgeCalleeItr.next();
- HeapRegionNode hrnChildCallee = edgeCallee.getDst();
+ 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(), edgeCallee.getType() ) ) {
- System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+edgeCallee+" for return temp "+returnTemp );
+ if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
+ System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
+ reCallee+" for return temp "+returnTemp );
// prune
continue;
}
- RefEdge edgeNewInCallerTemplate = new RefEdge( null,
- null,
- edgeCallee.getType(),
- edgeCallee.getField(),
- false,
- funcScriptR( toShadowTokens(ogCallee,
- edgeCallee.getBeta() ),
- ogCallee,
- mc )
- );
- rewriteCallerReachability( bogusIndex,
- null,
- edgeNewInCallerTemplate,
- edgeNewInCallerTemplate.getBeta(),
- tokens2statesEmpty,
- paramIndex2rewrite_d_p,
- paramIndex2rewrite_d_s,
- paramIndex2rewriteD,
- ogCallee,
- false,
- null );
-
- edgeNewInCallerTemplate.applyBetaNew();
-
-
- HashSet<HeapRegionNode> assignCallerRhs =
- getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
- edgeCallee.getDst(),
- pi2dr,
- pi2r );
-
- Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
- while( itrHrn.hasNext() ) {
- HeapRegionNode hrnCaller = itrHrn.next();
-
- // don't make edge in caller if it is disallowed by types
- if( !isSuperiorType( returnTemp.getType(), hrnCaller.getType() ) ) {
- // prune
- continue;
- }
-
- if( !isSuperiorType( returnTemp.getType(), hrnChildCallee.getType() ) ) {
- // 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();
+ }
- if( !isSuperiorType( edgeCallee.getType(), hrnCaller.getType() ) ) {
- // prune
- continue;
- }
-
- TypeDescriptor tdNewEdge =
- mostSpecificType( edgeCallee.getType(),
- hrnChildCallee.getType(),
- hrnCaller.getType()
- );
-
- // otherwise caller node can match callee edge, so make it
- RefEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
- edgeNewInCaller.setSrc( lnLhsCaller );
- edgeNewInCaller.setDst( hrnCaller );
- edgeNewInCaller.setType( tdNewEdge );
-
- RefEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
- tdNewEdge,
- edgeNewInCaller.getField() );
- if( edgeExisting == null ) {
-
- // if this edge doesn't exist in the caller, create it
- addRefEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
- } else {
- // if it already exists, merge with it
- edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
- }
- }
+ 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 );
}
}
- // merge the shadow nodes of allocation sites back down to normal capacity
- Iterator<AllocSite> allocItr = ogCallee.allocSites.iterator();
- while( allocItr.hasNext() ) {
- AllocSite as = allocItr.next();
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller38propagateReach",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
+ }
- // first age each allocation site enough times to make room for the shadow nodes
- for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- age( as );
- }
+ // 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();
+ }
- // then merge the shadow summary into the normal summary
- HeapRegionNode hrnSummary = getSummaryNode( as );
- assert hrnSummary != null;
- HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
- assert hrnSummaryShadow != null;
- mergeIntoSummary( hrnSummaryShadow, hrnSummary );
- // then clear off after merge
- clearRefEdgesFrom( hrnSummaryShadow, null, null, true );
- clearRefEdgesTo ( hrnSummaryShadow, null, null, true );
- hrnSummaryShadow.setAlpha( new ReachSet().makeCanonical() );
- // then transplant shadow nodes onto the now clean normal nodes
- for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- Integer idIth = as.getIthOldest( i );
- HeapRegionNode hrnIth = id2hrn.get( idIth );
- Integer idIthShadow = as.getIthOldestShadow( i );
- HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller40BeforeShadowMerge",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
+ }
+
- transferOnto( hrnIthShadow, hrnIth );
+ // 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;
+ }
- // clear off shadow nodes after transfer
- clearRefEdgesFrom( hrnIthShadow, null, null, true );
- clearRefEdgesTo ( hrnIthShadow, null, null, true );
- hrnIthShadow.setAlpha( new ReachSet().makeCanonical() );
+ // 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++;
}
- // finally, globally change shadow tokens into normal tokens
- Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
- while( itrAllVariableNodes.hasNext() ) {
- Map.Entry me = (Map.Entry) itrAllVariableNodes.next();
- VariableNode ln = (VariableNode) me.getValue();
+ // 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;
+ }
- Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
- while( itrEdges.hasNext() ) {
- unshadowTokens( as, itrEdges.next() );
- }
+ // yes, a normal node exists, so get the shadow summary
+ HeapRegionNode summShad = getSummaryNode( as, true );
+ mergeIntoSummary( hrnNorm, summShad );
+ ageNorm++;
}
- Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
- while( itrAllHRNodes.hasNext() ) {
- Map.Entry me = (Map.Entry) itrAllHRNodes.next();
- HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
-
- unshadowTokens( as, hrnToAge );
-
- Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
- while( itrEdges.hasNext() ) {
- unshadowTokens( as, itrEdges.next() );
- }
+ // 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 );
}
- }
-
-
-
- // improve reachability as much as possible
- if( !DISABLE_GLOBAL_SWEEP ) {
- globalSweep();
- }
-
-
- if( debugCallMap &&
- mc.getDescriptor().getSymbol().equals( debugCaller ) &&
- fm.getMethod().getSymbol().equals( debugCallee )
- ) {
- try {
- writeGraph( "debug9endResolveCall",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- false, // show back edges to confirm graph validity
- false, // show parameter indices (unmaintained!)
- true, // hide subset reachability states
- true); // hide edge taints
- } catch( IOException e ) {}
- System.out.println( " "+mc+" done calling "+fm );
- ++x;
- if( x == debugCallMapCount ) {
- System.exit( 0 );
+ // 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 );
+ }
}
- }
-
- static int x = 0;
-
- protected boolean hasMatchingField(HeapRegionNode src, RefEdge edge) {
- // if no type, then it's a match-everything region
- TypeDescriptor tdSrc = src.getType();
- if( tdSrc == null ) {
- return true;
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller45BeforeUnshadow",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
}
-
- if( tdSrc.isArray() ) {
- TypeDescriptor td = edge.getType();
- assert td != null;
-
- TypeDescriptor tdSrcDeref = tdSrc.dereference();
- assert tdSrcDeref != null;
-
- if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
- return false;
+
+
+ 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() ) );
}
-
- return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
}
+
- // if it's not a class, it doesn't have any fields to match
- if( !tdSrc.isClass() ) {
- return false;
- }
- ClassDescriptor cd = tdSrc.getClassDesc();
- while( cd != null ) {
- Iterator fieldItr = cd.getFields();
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller50BeforeGlobalSweep",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
+ }
- while( fieldItr.hasNext() ) {
- FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
- if( fd.getType().equals( edge.getType() ) &&
- fd.getSymbol().equals( edge.getField() ) ) {
- return true;
- }
- }
-
- cd = cd.getSuperDesc();
+ // 5.
+ if( !DISABLE_GLOBAL_SWEEP ) {
+ globalSweep();
}
- // otherwise it is a class with fields
- // but we didn't find a match
- return false;
- }
- protected boolean hasMatchingType(RefEdge edge, HeapRegionNode dst) {
-
- // if the region has no type, matches everything
- TypeDescriptor tdDst = dst.getType();
- if( tdDst == null ) {
- return true;
- }
-
- // if the type is not a class or an array, don't
- // match because primitives are copied, no aliases
- ClassDescriptor cdDst = tdDst.getClassDesc();
- if( cdDst == null && !tdDst.isArray() ) {
- return false;
- }
-
- // if the edge type is null, it matches everything
- TypeDescriptor tdEdge = edge.getType();
- if( tdEdge == null ) {
- return true;
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller90AfterTransfer",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
}
-
- return typeUtil.isSuperorType(tdEdge, tdDst);
- }
-
-
- 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) );
- }
-
+ }
- private ReachSet toShadowTokens(ReachGraph ogCallee,
- ReachSet rsIn) {
+
- ReachSet rsOut = new ReachSet(rsIn).makeCanonical();
+ ////////////////////////////////////////////////////
+ //
+ // 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 ) {
- Iterator<AllocSite> allocItr = ogCallee.allocSites.iterator();
- while( allocItr.hasNext() ) {
- AllocSite as = allocItr.next();
+ // calculate a root set, will be different for Java
+ // version of analysis versus Bamboo version
+ Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
- rsOut = rsOut.toShadowTokens(as);
+ // 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() );
}
-
- return rsOut.makeCanonical();
- }
-
-
- private void rewriteCallerReachability(Integer paramIndex,
- HeapRegionNode hrn,
- RefEdge edge,
- ReachSet rules,
- Hashtable<ReachTuple, ReachSet> tokens2states,
- Hashtable<Integer, ReachSet> paramIndex2rewrite_d_p,
- Hashtable<Integer, ReachSet> paramIndex2rewrite_d_s,
- Hashtable<Integer, ReachSet> paramIndex2rewriteD,
- ReachGraph ogCallee,
- boolean makeChangeSet,
- Hashtable<RefEdge, ChangeSet> edgePlannedChanges) {
-
- assert(hrn == null && edge != null) ||
- (hrn != null && edge == null);
-
- assert rules != null;
- assert tokens2states != null;
-
- ReachSet callerReachabilityNew = new ReachSet().makeCanonical();
-
- // for initializing structures in this method
- ReachState ttsEmpty = new ReachState().makeCanonical();
-
- // use this to construct a change set if required; the idea is to
- // map every partially rewritten token tuple set to the set of
- // caller-context token tuple sets that were used to generate it
- Hashtable<ReachState, HashSet<ReachState> > rewritten2source =
- new Hashtable<ReachState, HashSet<ReachState> >();
- rewritten2source.put( ttsEmpty, new HashSet<ReachState>() );
-
- Iterator<ReachState> rulesItr = rules.iterator();
- while(rulesItr.hasNext()) {
- ReachState rule = rulesItr.next();
-
- ReachSet rewrittenRule = new ReachSet(ttsEmpty).makeCanonical();
-
- Iterator<ReachTuple> ruleItr = rule.iterator();
- while(ruleItr.hasNext()) {
- ReachTuple ttCallee = ruleItr.next();
-
- // compute the possibilities for rewriting this callee token
- ReachSet ttCalleeRewrites = null;
- boolean callerSourceUsed = false;
-
- if( tokens2states.containsKey( ttCallee ) ) {
- callerSourceUsed = true;
- ttCalleeRewrites = tokens2states.get( ttCallee );
- assert ttCalleeRewrites != null;
-
- } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) {
- // use little d_p
- Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee );
- assert paramIndex_j != null;
- ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j );
- assert ttCalleeRewrites != null;
-
- } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) {
- // use little d_s
- Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee );
- assert paramIndex_j != null;
- ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j );
- assert ttCalleeRewrites != null;
-
- } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) {
- // worse, use big D
- Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee );
- assert paramIndex_j != null;
- ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
- assert ttCalleeRewrites != null;
-
- } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) {
- // worse, use big D
- Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee );
- assert paramIndex_j != null;
- ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
- assert ttCalleeRewrites != null;
-
- } else {
- // otherwise there's no need for a rewrite, just pass this one on
- ReachState ttsCaller = new ReachState( ttCallee ).makeCanonical();
- ttCalleeRewrites = new ReachSet( ttsCaller ).makeCanonical();
- }
-
- // branch every version of the working rewritten rule with
- // the possibilities for rewriting the current callee token
- ReachSet rewrittenRuleWithTTCallee = new ReachSet().makeCanonical();
-
- Iterator<ReachState> rewrittenRuleItr = rewrittenRule.iterator();
- while( rewrittenRuleItr.hasNext() ) {
- ReachState ttsRewritten = rewrittenRuleItr.next();
-
- Iterator<ReachState> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
- while( ttCalleeRewritesItr.hasNext() ) {
- ReachState ttsBranch = ttCalleeRewritesItr.next();
-
- ReachState ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
-
- if( makeChangeSet ) {
- // in order to keep the list of source token tuple sets
- // start with the sets used to make the partially rewritten
- // rule up to this point
- HashSet<ReachState> sourceSets = rewritten2source.get( ttsRewritten );
- assert sourceSets != null;
-
- // make a shallow copy for possible modification
- sourceSets = (HashSet<ReachState>) sourceSets.clone();
-
- // if we used something from the caller to rewrite it, remember
- if( callerSourceUsed ) {
- sourceSets.add( ttsBranch );
- }
-
- // set mapping for the further rewritten rule
- rewritten2source.put( ttsRewrittenNext, sourceSets );
- }
+ Iterator eItr = entrysCopy.iterator();
+ while( eItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) eItr.next();
+ TempDescriptor td = (TempDescriptor) me.getKey();
+ VariableNode vn = (VariableNode) me.getValue();
- rewrittenRuleWithTTCallee =
- rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
- }
- }
+ if( liveSet.contains( td ) ) {
+ toVisit.add( vn );
- // now the rewritten rule's possibilities have been extended by
- // rewriting the current callee token, remember result
- rewrittenRule = rewrittenRuleWithTTCallee;
+ } else {
+ // dead var, remove completely from graph
+ td2vn.remove( td );
+ clearRefEdgesFrom( vn, null, null, true );
}
-
- // the rule has been entirely rewritten into the caller context
- // now, so add it to the new reachability information
- callerReachabilityNew =
- callerReachabilityNew.union( rewrittenRule );
}
- if( makeChangeSet ) {
- ChangeSet callerChangeSet = new ChangeSet().makeCanonical();
-
- // each possibility for the final reachability should have a set of
- // caller sources mapped to it, use to create the change set
- Iterator<ReachState> callerReachabilityItr = callerReachabilityNew.iterator();
- while( callerReachabilityItr.hasNext() ) {
- ReachState ttsRewrittenFinal = callerReachabilityItr.next();
- HashSet<ReachState> sourceSets = rewritten2source.get( ttsRewrittenFinal );
- assert sourceSets != null;
-
- Iterator<ReachState> sourceSetsItr = sourceSets.iterator();
- while( sourceSetsItr.hasNext() ) {
- ReachState ttsSource = sourceSetsItr.next();
-
- callerChangeSet =
- callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
- }
+ // 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 );
+ }
}
-
- assert edgePlannedChanges != null;
- edgePlannedChanges.put( edge, callerChangeSet );
}
- if( hrn == null ) {
- edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
- } else {
- hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
+ // 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() );
}
- }
-
-
- private HashSet<HeapRegionNode>
- getHRNSetThatPossiblyMapToCalleeHRN( ReachGraph ogCallee,
- HeapRegionNode hrnCallee,
- Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
- Hashtable<Integer, Set<HeapRegionNode> > pi2r
- ) {
-
- HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
-
- Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
- Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
-
- if( paramIndicesCallee_p == null &&
- paramIndicesCallee_s == null ) {
- // this is a node allocated in the callee and it has
- // exactly one shadow node in the caller to map to
- AllocSite as = hrnCallee.getAllocSite();
- assert as != null;
-
- int age = as.getAgeCategory( hrnCallee.getID() );
- assert age != AllocSite.AGE_notInThisSite;
+ Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
+ while( hrnAllItr.hasNext() ) {
+ HeapRegionNode hrn = hrnAllItr.next();
- Integer idCaller;
- if( age == AllocSite.AGE_summary ) {
- idCaller = as.getSummaryShadow();
+ if( !visited.contains( hrn ) ) {
- } else if( age == AllocSite.AGE_oldest ) {
- idCaller = as.getOldestShadow();
+ // 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() );
- } else {
- assert age == AllocSite.AGE_in_I;
-
- Integer I = as.getAge( hrnCallee.getID() );
- assert I != null;
+ // 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 );
- idCaller = as.getIthOldestShadow( I );
+ // 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 );
+ }
}
-
- assert id2hrn.containsKey( idCaller );
- possibleCallerHRNs.add( id2hrn.get( idCaller ) );
-
- return possibleCallerHRNs;
}
+ }
- // find out what primary objects this might be
- if( paramIndicesCallee_p != null ) {
- // this is a node that was created to represent a parameter
- // so it maps to some regions directly reachable from the arg labels
- Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
- while( itrIndex.hasNext() ) {
- Integer paramIndexCallee = itrIndex.next();
- assert pi2dr.containsKey( paramIndexCallee );
- possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) );
- }
+ protected boolean hasNodesOf( AllocSite as ) {
+ if( id2hrn.containsKey( as.getSummary() ) ) {
+ return true;
}
- // find out what secondary objects this might be
- if( paramIndicesCallee_s != null ) {
- // this is a node that was created to represent objs reachable from
- // some parameter, so it maps to regions reachable from the arg labels
- Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
- while( itrIndex.hasNext() ) {
- Integer paramIndexCallee = itrIndex.next();
- assert pi2r.containsKey( paramIndexCallee );
- possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) );
- }
+ for( int i = 0; i < allocationDepth; ++i ) {
+ if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
+ return true;
+ }
}
-
- // TODO: is this true?
- // one of the two cases above should have put something in here
- //assert !possibleCallerHRNs.isEmpty();
-
- return possibleCallerHRNs;
+ return false;
}
-
////////////////////////////////////////////////////
//
// This global sweep is an optional step to prune
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 rsEmpty.equals( hrn.getAlphaNew() );
+ assert rsetEmpty.equals( hrn.getAlphaNew() );
Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
while( itrRers.hasNext() ) {
RefEdge edge = itrRers.next();
- assert rsEmpty.equals( edge.getBetaNew() );
+ assert rsetEmpty.equals( edge.getBetaNew() );
}
- // calculate boldB for this flagged node
- if( hrn.isFlagged() || hrn.isParameter() ) {
-
- Hashtable<RefEdge, ReachSet> boldB_f =
- new Hashtable<RefEdge, ReachSet>();
-
- Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
+ // calculate boldB for this flagged node, or out-of-context node
+ if( hrn.isFlagged() ) {
+ 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.unionORpreds( prevResult,
+ intersection ).size()
+ > prevResult.size()
+ ) {
+
+ if( prevResult == null ) {
+ boldB_f.put( edgePrime,
+ Canonical.unionORpreds( edgePrime.getBeta(),
+ intersection
+ )
+ );
+ } else {
+ boldB_f.put( edgePrime,
+ Canonical.unionORpreds( 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() || hrn.isParameter() ) {
- if( ttOld == ttException ) {
+ if( hrn.isFlagged() ) {
+ 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.containsIgnorePreds( stateOld ) != null
+ ) {
+ 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.add( 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.add( statePruned, rtOld );
}
}
- assert !ttsOld.equals( ttsPruned );
-
- hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
- ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
- cts = cts.union( ct );
+ assert !stateOld.equals( statePruned );
+
+ hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
+ statePruned
+ )
+ );
+ ChangeTuple ct = ChangeTuple.factory( stateOld,
+ statePruned
+ );
+ cts = Canonical.add( 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
+ )
+ );
}
}
}
Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
while( nodeItr.hasNext() ) {
HeapRegionNode hrn = nodeItr.next();
- hrn.applyAlphaNew();
+
+ // as mentioned above, out-of-context nodes only serve
+ // as sources of reach states for the sweep, not part
+ // of the changes
+ if( hrn.isOutOfContext() ) {
+ assert hrn.getAlphaNew().equals( rsetEmpty );
+ } else {
+ hrn.applyAlphaNew();
+ }
+
Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
while( itrRes.hasNext() ) {
res.add( itrRes.next() );
// 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.unionORpreds( prevResult,
+ intersection
+ ).size()
+ > prevResult.size()
+ ) {
+
+ edge.setBetaNew(
+ Canonical.unionORpreds( prevResult,
+ intersection
+ )
+ );
edgeWorkSet.add( edge );
}
}
edgeItr.next().applyBetaNew();
}
}
- */
+
+ ////////////////////////////////////////////////////
+ // high-level merge operations
+ ////////////////////////////////////////////////////
+ public void merge_sameMethodContext( ReachGraph rg ) {
+ // when merging two graphs that abstract the heap
+ // of the same method context, we just call the
+ // basic merge operation
+ merge( rg );
+ }
+
+ public void merge_diffMethodContext( ReachGraph rg ) {
+ // when merging graphs for abstract heaps in
+ // different method contexts we should:
+ // 1) age the allocation sites?
+ merge( rg );
+ }
+
////////////////////////////////////////////////////
// in merge() and equals() methods the suffix A
// represents the passed in graph and the suffix
// merge it into B, so after the operation graph B
// is the final result.
////////////////////////////////////////////////////
- public void merge( ReachGraph rg ) {
+ protected void merge( ReachGraph rg ) {
if( rg == null ) {
return;
}
- /*
- mergeRefSrcNodes(og);
- mergeRefEdges(og);
- mergeParamIndexMappings(og);
- mergeAllocSites(og);
- mergeAccessPaths(og);
- mergeTempAndLabelCategories(og);
- */
+ mergeNodes ( rg );
+ mergeRefEdges ( rg );
+ mergeAllocSites( rg );
}
+
+ protected void mergeNodes( ReachGraph rg ) {
- /*
- protected void mergeRefSrcNodes(ReachGraph og) {
- Set sA = og.id2hrn.entrySet();
+ // start with heap region nodes
+ Set sA = rg.id2hrn.entrySet();
Iterator iA = sA.iterator();
while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry)iA.next();
- Integer idA = (Integer) meA.getKey();
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
// if this graph doesn't have a node the
// incoming graph has, allocate it
- if( !id2hrn.containsKey(idA) ) {
+ if( !id2hrn.containsKey( idA ) ) {
HeapRegionNode hrnB = hrnA.copy();
- id2hrn.put(idA, hrnB);
+ id2hrn.put( idA, hrnB );
} else {
// otherwise this is a node present in both graphs
// 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() ) );
+ HeapRegionNode hrnB = id2hrn.get( idA );
+ hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
+ hrnA.getAlpha()
+ )
+ );
+
+ hrnB.setPreds( Canonical.join( hrnB.getPreds(),
+ hrnA.getPreds()
+ )
+ );
}
}
- // now add any label nodes that are in graph B but
+ // now add any variable nodes that are in graph B but
// not in A
- sA = og.td2vn.entrySet();
+ sA = rg.td2vn.entrySet();
iA = sA.iterator();
while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry)iA.next();
+ Map.Entry meA = (Map.Entry) iA.next();
TempDescriptor tdA = (TempDescriptor) meA.getKey();
- VariableNode lnA = (VariableNode) meA.getValue();
+ VariableNode lnA = (VariableNode) meA.getValue();
- // if the label doesn't exist in B, allocate and add it
- VariableNode lnB = getVariableNodeFromTemp(tdA);
+ // if the variable doesn't exist in B, allocate and add it
+ VariableNode lnB = getVariableNodeFromTemp( tdA );
}
}
- protected void mergeRefEdges(ReachGraph og) {
+ protected void mergeRefEdges( ReachGraph rg ) {
- // heap regions
- Set sA = og.id2hrn.entrySet();
+ // between heap regions
+ Set sA = rg.id2hrn.entrySet();
Iterator iA = sA.iterator();
while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry)iA.next();
- Integer idA = (Integer) meA.getKey();
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
while( heapRegionsItrA.hasNext() ) {
- RefEdge edgeA = heapRegionsItrA.next();
+ RefEdge edgeA = heapRegionsItrA.next();
HeapRegionNode hrnChildA = edgeA.getDst();
- Integer idChildA = hrnChildA.getID();
+ Integer idChildA = hrnChildA.getID();
// at this point we know an edge in graph A exists
// idA -> idChildA, does this exist in B?
- assert id2hrn.containsKey(idA);
- HeapRegionNode hrnB = id2hrn.get(idA);
- RefEdge edgeToMerge = null;
+ assert id2hrn.containsKey( idA );
+ HeapRegionNode hrnB = id2hrn.get( idA );
+ RefEdge edgeToMerge = null;
Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
while( heapRegionsItrB.hasNext() &&
edgeToMerge == null ) {
- RefEdge edgeB = heapRegionsItrB.next();
+ RefEdge edgeB = heapRegionsItrB.next();
HeapRegionNode hrnChildB = edgeB.getDst();
- Integer idChildB = hrnChildB.getID();
+ Integer idChildB = hrnChildB.getID();
// don't use the RefEdge.equals() here because
- // we're talking about existence between graphs
+ // we're talking about existence between graphs,
+ // not intragraph equal
if( idChildB.equals( idChildA ) &&
edgeB.typeAndFieldEquals( edgeA ) ) {
// if the edge from A was not found in B,
// add it to B.
if( edgeToMerge == null ) {
- assert id2hrn.containsKey(idChildA);
- HeapRegionNode hrnChildB = id2hrn.get(idChildA);
+ assert id2hrn.containsKey( idChildA );
+ HeapRegionNode hrnChildB = id2hrn.get( idChildA );
edgeToMerge = edgeA.copy();
- edgeToMerge.setSrc(hrnB);
- edgeToMerge.setDst(hrnChildB);
- addRefEdge(hrnB, hrnChildB, edgeToMerge);
+ edgeToMerge.setSrc( hrnB );
+ edgeToMerge.setDst( hrnChildB );
+ addRefEdge( hrnB, hrnChildB, edgeToMerge );
}
// otherwise, the edge already existed in both graphs
// so merge their reachability sets
// just replace this beta set with the union
assert edgeToMerge != null;
edgeToMerge.setBeta(
- edgeToMerge.getBeta().union(edgeA.getBeta() )
- );
- //TODO eom
- edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
- if( !edgeA.isInitialParam() ) {
- edgeToMerge.setIsInitialParam(false);
- }
+ Canonical.unionORpreds( edgeToMerge.getBeta(),
+ edgeA.getBeta()
+ )
+ );
+ edgeToMerge.setPreds(
+ Canonical.join( edgeToMerge.getPreds(),
+ edgeA.getPreds()
+ )
+ );
}
}
}
- // and then again with label nodes
- sA = og.td2vn.entrySet();
+ // and then again from variable nodes
+ sA = rg.td2vn.entrySet();
iA = sA.iterator();
while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry)iA.next();
+ Map.Entry meA = (Map.Entry) iA.next();
TempDescriptor tdA = (TempDescriptor) meA.getKey();
- VariableNode lnA = (VariableNode) meA.getValue();
+ VariableNode vnA = (VariableNode) meA.getValue();
- Iterator<RefEdge> heapRegionsItrA = lnA.iteratorToReferencees();
+ Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
while( heapRegionsItrA.hasNext() ) {
- RefEdge edgeA = heapRegionsItrA.next();
+ RefEdge edgeA = heapRegionsItrA.next();
HeapRegionNode hrnChildA = edgeA.getDst();
- Integer idChildA = hrnChildA.getID();
+ Integer idChildA = hrnChildA.getID();
// at this point we know an edge in graph A exists
// tdA -> idChildA, does this exist in B?
- assert td2vn.containsKey(tdA);
- VariableNode lnB = td2vn.get(tdA);
- RefEdge edgeToMerge = null;
+ assert td2vn.containsKey( tdA );
+ VariableNode vnB = td2vn.get( tdA );
+ RefEdge edgeToMerge = null;
- Iterator<RefEdge> heapRegionsItrB = lnB.iteratorToReferencees();
+ Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
while( heapRegionsItrB.hasNext() &&
edgeToMerge == null ) {
- RefEdge edgeB = heapRegionsItrB.next();
+ RefEdge edgeB = heapRegionsItrB.next();
HeapRegionNode hrnChildB = edgeB.getDst();
Integer idChildB = hrnChildB.getID();
// if the edge from A was not found in B,
// add it to B.
if( edgeToMerge == null ) {
- assert id2hrn.containsKey(idChildA);
- HeapRegionNode hrnChildB = id2hrn.get(idChildA);
+ assert id2hrn.containsKey( idChildA );
+ HeapRegionNode hrnChildB = id2hrn.get( idChildA );
edgeToMerge = edgeA.copy();
- edgeToMerge.setSrc(lnB);
- edgeToMerge.setDst(hrnChildB);
- addRefEdge(lnB, hrnChildB, edgeToMerge);
+ edgeToMerge.setSrc( vnB );
+ edgeToMerge.setDst( hrnChildB );
+ addRefEdge( vnB, hrnChildB, edgeToMerge );
}
// otherwise, the edge already existed in both graphs
// so merge their reachability sets
else {
// just replace this beta set with the union
- edgeToMerge.setBeta(
- edgeToMerge.getBeta().union(edgeA.getBeta() )
- );
- edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
- if( !edgeA.isInitialParam() ) {
- edgeToMerge.setIsInitialParam(false);
- }
+ edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
+ edgeA.getBeta()
+ )
+ );
+ edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
+ edgeA.getPreds()
+ )
+ );
}
}
}
}
- // you should only merge ownership graphs that have the
- // same number of parameters, or if one or both parameter
- // index tables are empty
- protected void mergeParamIndexMappings(ReachGraph og) {
-
- if( idPrimary2paramIndexSet.size() == 0 ) {
-
- idPrimary2paramIndexSet = og.idPrimary2paramIndexSet;
- paramIndex2idPrimary = og.paramIndex2idPrimary;
-
- idSecondary2paramIndexSet = og.idSecondary2paramIndexSet;
- paramIndex2idSecondary = og.paramIndex2idSecondary;
-
- paramIndex2tdQ = og.paramIndex2tdQ;
- paramIndex2tdR = og.paramIndex2tdR;
-
- paramTokenPrimary2paramIndex = og.paramTokenPrimary2paramIndex;
- paramIndex2paramTokenPrimary = og.paramIndex2paramTokenPrimary;
-
- paramTokenSecondary2paramIndex = og.paramTokenSecondary2paramIndex;
- paramIndex2paramTokenSecondary = og.paramIndex2paramTokenSecondary;
- paramTokenSecondaryPlus2paramIndex = og.paramTokenSecondaryPlus2paramIndex;
- paramIndex2paramTokenSecondaryPlus = og.paramIndex2paramTokenSecondaryPlus;
- paramTokenSecondaryStar2paramIndex = og.paramTokenSecondaryStar2paramIndex;
- paramIndex2paramTokenSecondaryStar = og.paramIndex2paramTokenSecondaryStar;
-
- return;
- }
-
- if( og.idPrimary2paramIndexSet.size() == 0 ) {
-
- og.idPrimary2paramIndexSet = idPrimary2paramIndexSet;
- og.paramIndex2idPrimary = paramIndex2idPrimary;
-
- og.idSecondary2paramIndexSet = idSecondary2paramIndexSet;
- og.paramIndex2idSecondary = paramIndex2idSecondary;
-
- og.paramIndex2tdQ = paramIndex2tdQ;
- og.paramIndex2tdR = paramIndex2tdR;
-
- og.paramTokenPrimary2paramIndex = paramTokenPrimary2paramIndex;
- og.paramIndex2paramTokenPrimary = paramIndex2paramTokenPrimary;
-
- og.paramTokenSecondary2paramIndex = paramTokenSecondary2paramIndex;
- og.paramIndex2paramTokenSecondary = paramIndex2paramTokenSecondary;
- og.paramTokenSecondaryPlus2paramIndex = paramTokenSecondaryPlus2paramIndex;
- og.paramIndex2paramTokenSecondaryPlus = paramIndex2paramTokenSecondaryPlus;
- og.paramTokenSecondaryStar2paramIndex = paramTokenSecondaryStar2paramIndex;
- og.paramIndex2paramTokenSecondaryStar = paramIndex2paramTokenSecondaryStar;
-
- return;
- }
-
- assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size();
- assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
- }
-
- protected void mergeAllocSites(ReachGraph og) {
- allocSites.addAll(og.allocSites);
- }
-
- protected void mergeAccessPaths(ReachGraph og) {
- UtilAlgorithms.mergeHashtablesWithHashSetValues(temp2accessPaths,
- og.temp2accessPaths);
- }
-
- protected void mergeTempAndLabelCategories(ReachGraph og) {
- outOfScopeTemps.addAll(og.outOfScopeTemps);
- outOfScopeLabels.addAll(og.outOfScopeLabels);
- parameterTemps.addAll(og.parameterTemps);
- parameterLabels.addAll(og.parameterLabels);
- }
- */
+ protected void mergeAllocSites( ReachGraph rg ) {
+ allocSites.addAll( rg.allocSites );
+ }
// it is necessary in the equals() member functions
if( rg == null ) {
return false;
}
-
- /*
- if( !areHeapRegionNodesEqual(og) ) {
- return false;
- }
-
- if( !areVariableNodesEqual(og) ) {
- return false;
- }
-
- if( !areRefEdgesEqual(og) ) {
+
+ if( !areHeapRegionNodesEqual( rg ) ) {
return false;
}
- if( !areParamIndexMappingsEqual(og) ) {
+ if( !areVariableNodesEqual( rg ) ) {
return false;
}
- if( !areAccessPathsEqual(og) ) {
+ if( !areRefEdgesEqual( rg ) ) {
return false;
}
// if everything is equal up to this point,
// assert that allocSites is also equal--
- // this data is redundant and kept for efficiency
- assert allocSites .equals(og.allocSites );
- assert outOfScopeTemps .equals(og.outOfScopeTemps );
- assert outOfScopeLabels.equals(og.outOfScopeLabels);
- assert parameterTemps .equals(og.parameterTemps );
- assert parameterLabels .equals(og.parameterLabels );
- */
+ // this data is redundant but kept for efficiency
+ assert allocSites.equals( rg.allocSites );
return true;
}
- /*
- protected boolean areHeapRegionNodesEqual(ReachGraph og) {
+
+ protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
- if( !areallHRNinAalsoinBandequal(this, og) ) {
+ if( !areallHRNinAalsoinBandequal( this, rg ) ) {
return false;
}
- if( !areallHRNinAalsoinBandequal(og, this) ) {
+ if( !areallHRNinAalsoinBandequal( rg, this ) ) {
return false;
}
return true;
}
- static protected boolean areallHRNinAalsoinBandequal(ReachGraph ogA,
- ReachGraph ogB) {
- Set sA = ogA.id2hrn.entrySet();
+ static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
+ ReachGraph rgB ) {
+ Set sA = rgA.id2hrn.entrySet();
Iterator iA = sA.iterator();
while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry)iA.next();
- Integer idA = (Integer) meA.getKey();
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
- if( !ogB.id2hrn.containsKey(idA) ) {
+ if( !rgB.id2hrn.containsKey( idA ) ) {
return false;
}
- HeapRegionNode hrnB = ogB.id2hrn.get(idA);
- if( !hrnA.equalsIncludingAlpha(hrnB) ) {
+ HeapRegionNode hrnB = rgB.id2hrn.get( idA );
+ if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
return false;
}
}
-
+
return true;
}
+
+ protected boolean areVariableNodesEqual( ReachGraph rg ) {
- protected boolean areVariableNodesEqual(ReachGraph og) {
-
- if( !areallLNinAalsoinBandequal(this, og) ) {
+ if( !areallVNinAalsoinBandequal( this, rg ) ) {
return false;
}
- if( !areallLNinAalsoinBandequal(og, this) ) {
+ if( !areallVNinAalsoinBandequal( rg, this ) ) {
return false;
}
return true;
}
- static protected boolean areallLNinAalsoinBandequal(ReachGraph ogA,
- ReachGraph ogB) {
- Set sA = ogA.td2vn.entrySet();
+ static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
+ ReachGraph rgB ) {
+ Set sA = rgA.td2vn.entrySet();
Iterator iA = sA.iterator();
while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry)iA.next();
+ Map.Entry meA = (Map.Entry) iA.next();
TempDescriptor tdA = (TempDescriptor) meA.getKey();
- if( !ogB.td2vn.containsKey(tdA) ) {
+ if( !rgB.td2vn.containsKey( tdA ) ) {
return false;
}
}
}
- protected boolean areRefEdgesEqual(ReachGraph og) {
- if( !areallREinAandBequal(this, og) ) {
+ protected boolean areRefEdgesEqual( ReachGraph rg ) {
+ if( !areallREinAandBequal( this, rg ) ) {
return false;
}
return true;
}
- static protected boolean areallREinAandBequal(ReachGraph ogA,
- ReachGraph ogB) {
+ static protected boolean areallREinAandBequal( ReachGraph rgA,
+ ReachGraph rgB ) {
// check all the heap region->heap region edges
- Set sA = ogA.id2hrn.entrySet();
+ Set sA = rgA.id2hrn.entrySet();
Iterator iA = sA.iterator();
while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry)iA.next();
- Integer idA = (Integer) meA.getKey();
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
// we should have already checked that the same
// heap regions exist in both graphs
- assert ogB.id2hrn.containsKey(idA);
+ assert rgB.id2hrn.containsKey( idA );
- if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
+ if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
return false;
}
// then check every edge in B for presence in A, starting
// from the same parent HeapRegionNode
- HeapRegionNode hrnB = ogB.id2hrn.get(idA);
+ HeapRegionNode hrnB = rgB.id2hrn.get( idA );
- if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
+ if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
return false;
}
}
- // then check all the label->heap region edges
- sA = ogA.td2vn.entrySet();
+ // then check all the variable->heap region edges
+ sA = rgA.td2vn.entrySet();
iA = sA.iterator();
while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry)iA.next();
+ Map.Entry meA = (Map.Entry) iA.next();
TempDescriptor tdA = (TempDescriptor) meA.getKey();
- VariableNode lnA = (VariableNode) meA.getValue();
+ VariableNode vnA = (VariableNode) meA.getValue();
// we should have already checked that the same
// label nodes exist in both graphs
- assert ogB.td2vn.containsKey(tdA);
+ assert rgB.td2vn.containsKey( tdA );
- if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
+ if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
return false;
}
// then check every edge in B for presence in A, starting
// from the same parent VariableNode
- VariableNode lnB = ogB.td2vn.get(tdA);
+ VariableNode vnB = rgB.td2vn.get( tdA );
- if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
+ if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
return false;
}
}
}
- static protected boolean areallREfromAequaltoB(ReachGraph ogA,
- RefSrcNode onA,
- ReachGraph ogB) {
+ static protected boolean areallREfromAequaltoB( ReachGraph rgA,
+ RefSrcNode rnA,
+ ReachGraph rgB ) {
- Iterator<RefEdge> itrA = onA.iteratorToReferencees();
+ Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
while( itrA.hasNext() ) {
- RefEdge edgeA = itrA.next();
+ RefEdge edgeA = itrA.next();
HeapRegionNode hrnChildA = edgeA.getDst();
- Integer idChildA = hrnChildA.getID();
+ Integer idChildA = hrnChildA.getID();
- assert ogB.id2hrn.containsKey(idChildA);
+ assert rgB.id2hrn.containsKey( idChildA );
// at this point we know an edge in graph A exists
- // onA -> idChildA, does this exact edge exist in B?
+ // rnA -> idChildA, does this exact edge exist in B?
boolean edgeFound = false;
- RefSrcNode onB = null;
- if( onA instanceof HeapRegionNode ) {
- HeapRegionNode hrnA = (HeapRegionNode) onA;
- onB = ogB.id2hrn.get(hrnA.getID() );
+ RefSrcNode rnB = null;
+ if( rnA instanceof HeapRegionNode ) {
+ HeapRegionNode hrnA = (HeapRegionNode) rnA;
+ rnB = rgB.id2hrn.get( hrnA.getID() );
} else {
- VariableNode lnA = (VariableNode) onA;
- onB = ogB.td2vn.get(lnA.getTempDescriptor() );
+ VariableNode vnA = (VariableNode) rnA;
+ rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
}
- Iterator<RefEdge> itrB = onB.iteratorToReferencees();
+ Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
while( itrB.hasNext() ) {
- RefEdge edgeB = itrB.next();
+ RefEdge edgeB = itrB.next();
HeapRegionNode hrnChildB = edgeB.getDst();
- Integer idChildB = hrnChildB.getID();
+ Integer idChildB = hrnChildB.getID();
if( idChildA.equals( idChildB ) &&
edgeA.typeAndFieldEquals( edgeB ) ) {
// 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;
}
}
}
-
+
if( !edgeFound ) {
return false;
}
}
- protected boolean areParamIndexMappingsEqual(ReachGraph og) {
- if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
- return false;
- }
+ // this analysis no longer has the "match anything"
+ // type which was represented by null
+ protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
+ TypeDescriptor td2 ) {
+ assert td1 != null;
+ assert td2 != null;
- if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
- return false;
+ if( td1.isNull() ) {
+ return td2;
}
-
- return true;
+ if( td2.isNull() ) {
+ return td1;
+ }
+ return typeUtil.mostSpecific( td1, td2 );
}
+
+ protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
+ TypeDescriptor td2,
+ TypeDescriptor td3 ) {
+
+ return mostSpecificType( td1,
+ mostSpecificType( td2, td3 )
+ );
+ }
+
+ protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
+ TypeDescriptor td2,
+ TypeDescriptor td3,
+ TypeDescriptor td4 ) {
+
+ return mostSpecificType( mostSpecificType( td1, td2 ),
+ mostSpecificType( td3, td4 )
+ );
+ }
+ protected boolean isSuperiorType( TypeDescriptor possibleSuper,
+ TypeDescriptor possibleChild ) {
+ assert possibleSuper != null;
+ assert possibleChild != null;
+
+ if( possibleSuper.isNull() ||
+ possibleChild.isNull() ) {
+ return true;
+ }
- protected boolean areAccessPathsEqual(ReachGraph og) {
- return temp2accessPaths.equals( og.temp2accessPaths );
+ return typeUtil.isSuperorType( possibleSuper, possibleChild );
}
+ protected boolean hasMatchingField( HeapRegionNode src,
+ RefEdge edge ) {
- public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
- assert hrn1 != null;
- assert hrn2 != null;
-
- // then get the various tokens for these heap regions
- ReachTuple h1 = new ReachTuple(hrn1.getID(),
- !hrn1.isSingleObject(),
- ReachTuple.ARITY_ONE).makeCanonical();
-
- ReachTuple h1plus = new ReachTuple(hrn1.getID(),
- !hrn1.isSingleObject(),
- ReachTuple.ARITY_ONEORMORE).makeCanonical();
-
- ReachTuple h1star = new ReachTuple(hrn1.getID(),
- !hrn1.isSingleObject(),
- ReachTuple.ARITY_ZEROORMORE).makeCanonical();
+ TypeDescriptor tdSrc = src.getType();
+ assert tdSrc != null;
- ReachTuple h2 = new ReachTuple(hrn2.getID(),
- !hrn2.isSingleObject(),
- ReachTuple.ARITY_ONE).makeCanonical();
+ if( tdSrc.isArray() ) {
+ TypeDescriptor td = edge.getType();
+ assert td != null;
- ReachTuple h2plus = new ReachTuple(hrn2.getID(),
- !hrn2.isSingleObject(),
- ReachTuple.ARITY_ONEORMORE).makeCanonical();
+ TypeDescriptor tdSrcDeref = tdSrc.dereference();
+ assert tdSrcDeref != null;
- ReachTuple h2star = new ReachTuple(hrn2.getID(),
- !hrn2.isSingleObject(),
- ReachTuple.ARITY_ZEROORMORE).makeCanonical();
+ if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
+ return false;
+ }
- // then get the merged beta of all out-going edges from these heap regions
- ReachSet beta1 = new ReachSet().makeCanonical();
- Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
- while( itrEdge.hasNext() ) {
- RefEdge edge = itrEdge.next();
- beta1 = beta1.union( edge.getBeta() );
+ return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
}
- ReachSet beta2 = new ReachSet().makeCanonical();
- itrEdge = hrn2.iteratorToReferencees();
- while( itrEdge.hasNext() ) {
- RefEdge edge = itrEdge.next();
- beta2 = beta2.union( edge.getBeta() );
+ // if it's not a class, it doesn't have any fields to match
+ if( !tdSrc.isClass() ) {
+ return false;
}
- boolean aliasDetected = false;
-
- // only do this one if they are different tokens
- if( h1 != h2 &&
- beta1.containsTupleSetWithBoth(h1, h2) ) {
- aliasDetected = true;
- }
- if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
- aliasDetected = true;
- }
- if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
- aliasDetected = true;
- }
- if( beta1.containsTupleSetWithBoth(h1, h2plus) ) {
- aliasDetected = true;
- }
- if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
- aliasDetected = true;
- }
- if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
- aliasDetected = true;
- }
- if( beta1.containsTupleSetWithBoth(h1, h2star) ) {
- aliasDetected = true;
- }
- if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
- aliasDetected = true;
- }
- if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
- aliasDetected = true;
- }
+ ClassDescriptor cd = tdSrc.getClassDesc();
+ while( cd != null ) {
+ Iterator fieldItr = cd.getFields();
- if( h1 != h2 &&
- beta2.containsTupleSetWithBoth(h1, h2) ) {
- aliasDetected = true;
- }
- if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
- aliasDetected = true;
- }
- if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
- aliasDetected = true;
- }
- if( beta2.containsTupleSetWithBoth(h1, h2plus) ) {
- aliasDetected = true;
- }
- if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
- aliasDetected = true;
- }
- if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
- aliasDetected = true;
- }
- if( beta2.containsTupleSetWithBoth(h1, h2star) ) {
- aliasDetected = true;
- }
- if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
- aliasDetected = true;
- }
- if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
- aliasDetected = true;
- }
+ while( fieldItr.hasNext() ) {
+ FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
- Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
- if( aliasDetected ) {
- common = findCommonReachableNodes( hrn1, hrn2 );
- if( !(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP) ) {
- assert !common.isEmpty();
+ if( fd.getType().equals( edge.getType() ) &&
+ fd.getSymbol().equals( edge.getField() ) ) {
+ return true;
+ }
}
+
+ cd = cd.getSuperDesc();
}
-
- return common;
+
+ // otherwise it is a class with fields
+ // but we didn't find a match
+ return false;
}
-
- public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
-
- // get parameter 1's heap regions
- assert paramIndex2idPrimary.containsKey(paramIndex1);
- Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1);
-
- assert id2hrn.containsKey(idParamPri1);
- HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1);
- assert hrnParamPri1 != null;
-
- HeapRegionNode hrnParamSec1 = null;
- if( paramIndex2idSecondary.containsKey(paramIndex1) ) {
- Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1);
-
- assert id2hrn.containsKey(idParamSec1);
- hrnParamSec1 = id2hrn.get(idParamSec1);
- assert hrnParamSec1 != null;
+ protected boolean hasMatchingType( RefEdge edge,
+ HeapRegionNode dst ) {
+
+ // if the region has no type, matches everything
+ TypeDescriptor tdDst = dst.getType();
+ assert tdDst != null;
+
+ // if the type is not a class or an array, don't
+ // match because primitives are copied, no aliases
+ ClassDescriptor cdDst = tdDst.getClassDesc();
+ if( cdDst == null && !tdDst.isArray() ) {
+ return false;
}
+
+ // if the edge type is null, it matches everything
+ TypeDescriptor tdEdge = edge.getType();
+ assert tdEdge != null;
+
+ return typeUtil.isSuperorType( tdEdge, tdDst );
+ }
+
- // get the other parameter
- assert paramIndex2idPrimary.containsKey(paramIndex2);
- Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2);
-
- assert id2hrn.containsKey(idParamPri2);
- HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2);
- assert hrnParamPri2 != null;
-
- HeapRegionNode hrnParamSec2 = null;
- if( paramIndex2idSecondary.containsKey(paramIndex2) ) {
- Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2);
-
- assert id2hrn.containsKey(idParamSec2);
- hrnParamSec2 = id2hrn.get(idParamSec2);
- assert hrnParamSec2 != null;
- }
+ public void writeGraph( String graphName,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean hideSubsetReachability,
+ boolean hideEdgeTaints
+ ) throws java.io.IOException {
+ writeGraph( graphName,
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ hideSubsetReachability,
+ hideEdgeTaints,
+ null );
+ }
- Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
- common.addAll( hasPotentialAlias( hrnParamPri1, hrnParamPri2 ) );
+ public void writeGraph( String graphName,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ 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
+ graphName = graphName.replaceAll( "[\\W]", "" );
- if( hrnParamSec1 != null ) {
- common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamPri2 ) );
- }
+ BufferedWriter bw =
+ new BufferedWriter( new FileWriter( graphName+".dot" ) );
- if( hrnParamSec2 != null ) {
- common.addAll( hasPotentialAlias( hrnParamSec2, hrnParamPri1 ) );
- }
+ bw.write( "digraph "+graphName+" {\n" );
- if( hrnParamSec1 != null && hrnParamSec2 != null ) {
- common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamSec2 ) );
- }
- return common;
- }
+ // 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" );
- public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocSite as) {
+ 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" );
+
+ }
+ }
- // get parameter's heap regions
- assert paramIndex2idPrimary.containsKey(paramIndex);
- Integer idParamPri = paramIndex2idPrimary.get(paramIndex);
+ bw.write( " }\n" );
+ }
- assert id2hrn.containsKey(idParamPri);
- HeapRegionNode hrnParamPri = id2hrn.get(idParamPri);
- assert hrnParamPri != null;
- HeapRegionNode hrnParamSec = null;
- if( paramIndex2idSecondary.containsKey(paramIndex) ) {
- Integer idParamSec = paramIndex2idSecondary.get(paramIndex);
+ Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
- assert id2hrn.containsKey(idParamSec);
- hrnParamSec = id2hrn.get(idParamSec);
- assert hrnParamSec != null;
- }
+ // 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();
- // get summary node
- assert id2hrn.containsKey( as.getSummary() );
- HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
- assert hrnSummary != null;
+ // only visit nodes worth writing out--for instance
+ // not every node at an allocation is referenced
+ // (think of it as garbage-collected), etc.
+ if( !pruneGarbage ||
+ hrn.isOutOfContext()
+ ) {
- Set<HeapRegionNode> common = hasPotentialAlias( hrnParamPri, hrnSummary );
-
- if( hrnParamSec != null ) {
- common.addAll( hasPotentialAlias( hrnParamSec, hrnSummary ) );
+ if( !visited.contains( hrn ) ) {
+ traverseHeapRegionNodes( hrn,
+ bw,
+ null,
+ visited,
+ hideSubsetReachability,
+ hideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
+ }
+ }
}
- // check for other nodes
- for( int i = 0; i < as.getAllocationDepth(); ++i ) {
-
- assert id2hrn.containsKey( as.getIthOldest( i ) );
- HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) );
- assert hrnIthOldest != null;
+ bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" );
+
- common = hasPotentialAlias( hrnParamPri, hrnIthOldest );
-
- if( hrnParamSec != null ) {
- common.addAll( hasPotentialAlias( hrnParamSec, hrnIthOldest ) );
+ // then visit every label node, useful for debugging
+ if( writeLabels ) {
+ i = td2vn.entrySet().iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry) i.next();
+ VariableNode vn = (VariableNode) me.getValue();
+
+ if( labelSelect ) {
+ String labelStr = vn.getTempDescriptorString();
+ if( labelStr.startsWith( "___temp" ) ||
+ labelStr.startsWith( "___dst" ) ||
+ labelStr.startsWith( "___srctmp" ) ||
+ labelStr.startsWith( "___neverused" )
+ ) {
+ continue;
+ }
+ }
+
+ Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
+ while( heapRegionsItr.hasNext() ) {
+ RefEdge edge = heapRegionsItr.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ if( !visited.contains( hrn ) ) {
+ traverseHeapRegionNodes( hrn,
+ bw,
+ null,
+ visited,
+ hideSubsetReachability,
+ hideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
+ }
+
+ bw.write( " "+vn.toString()+
+ " -> "+hrn.toString()+
+ edge.toStringDOT( hideSubsetReachability, "" )+
+ ";\n" );
+ }
}
}
- return common;
+ bw.write( "}\n" );
+ bw.close();
}
+ protected void traverseHeapRegionNodes( HeapRegionNode hrn,
+ BufferedWriter bw,
+ TempDescriptor td,
+ Set<HeapRegionNode> visited,
+ boolean hideSubsetReachability,
+ boolean hideEdgeTaints,
+ Set<Integer> callerNodeIDsCopiedToCallee
+ ) throws java.io.IOException {
- public Set<HeapRegionNode> hasPotentialAlias(AllocSite as1, AllocSite as2) {
-
- // get summary node 1's alpha
- Integer idSum1 = as1.getSummary();
- assert id2hrn.containsKey(idSum1);
- HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
- assert hrnSum1 != null;
-
- // get summary node 2's alpha
- Integer idSum2 = as2.getSummary();
- assert id2hrn.containsKey(idSum2);
- HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
- assert hrnSum2 != null;
-
- Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
-
- // check sum2 against alloc1 nodes
- for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
- Integer idI1 = as1.getIthOldest(i);
- assert id2hrn.containsKey(idI1);
- HeapRegionNode hrnI1 = id2hrn.get(idI1);
- assert hrnI1 != null;
-
- common.addAll( hasPotentialAlias( hrnI1, hrnSum2 ) );
+ if( visited.contains( hrn ) ) {
+ return;
}
+ visited.add( hrn );
- // check sum1 against alloc2 nodes
- for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
- Integer idI2 = as2.getIthOldest(i);
- assert id2hrn.containsKey(idI2);
- HeapRegionNode hrnI2 = id2hrn.get(idI2);
- assert hrnI2 != null;
-
- common.addAll( hasPotentialAlias( hrnSum1, hrnI2 ) );
-
- // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
- for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
- Integer idI1 = as1.getIthOldest(j);
-
- // if these are the same site, don't look for the same token, no alias.
- // different tokens of the same site could alias together though
- if( idI1.equals( idI2 ) ) {
- continue;
- }
-
- HeapRegionNode hrnI1 = id2hrn.get(idI1);
-
- common.addAll( hasPotentialAlias( hrnI1, hrnI2 ) );
- }
+ // 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" );
}
- return common;
- }
-
-
- public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
- HeapRegionNode hrn2 ) {
-
- Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
- Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
-
- Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
- todoNodes1.add( hrn1 );
-
- Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
- todoNodes2.add( hrn2 );
+ Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
+ while( childRegionsItr.hasNext() ) {
+ RefEdge edge = childRegionsItr.next();
+ HeapRegionNode hrnChild = edge.getDst();
- // follow links until all reachable nodes have been found
- while( !todoNodes1.isEmpty() ) {
- HeapRegionNode hrn = todoNodes1.iterator().next();
- todoNodes1.remove( hrn );
- reachableNodes1.add(hrn);
-
- Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- RefEdge edge = edgeItr.next();
-
- if( !reachableNodes1.contains( edge.getDst() ) ) {
- todoNodes1.add( edge.getDst() );
- }
+ 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");
}
- }
-
- while( !todoNodes2.isEmpty() ) {
- HeapRegionNode hrn = todoNodes2.iterator().next();
- todoNodes2.remove( hrn );
- reachableNodes2.add(hrn);
- Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- RefEdge edge = edgeItr.next();
-
- if( !reachableNodes2.contains( edge.getDst() ) ) {
- todoNodes2.add( edge.getDst() );
- }
- }
+ traverseHeapRegionNodes( hrnChild,
+ bw,
+ td,
+ visited,
+ hideSubsetReachability,
+ hideEdgeTaints,
+ callerNodeIDsCopiedToCallee );
}
-
- Set<HeapRegionNode> intersection =
- new HashSet<HeapRegionNode>( reachableNodes1 );
-
- intersection.retainAll( reachableNodes2 );
+ }
- return intersection;
- }
+ public Set<HeapRegionNode> findCommonReachableNodes(HeapRegionNode hrn1,
+ HeapRegionNode hrn2) {
-
- public void writeGraph(String graphName,
- boolean writeLabels,
- boolean labelSelect,
- boolean pruneGarbage,
- boolean writeReferencers,
- boolean writeParamMappings,
- boolean hideSubsetReachability,
- boolean hideEdgeTaints
- ) throws java.io.IOException {
+ Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
+ Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
- // remove all non-word characters from the graph name so
- // the filename and identifier in dot don't cause errors
- graphName = graphName.replaceAll("[\\W]", "");
+ Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
+ todoNodes1.add(hrn1);
- BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
- bw.write("digraph "+graphName+" {\n");
+ Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
+ todoNodes2.add(hrn2);
- HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
+ // follow links until all reachable nodes have been found
+ while (!todoNodes1.isEmpty()) {
+ HeapRegionNode hrn = todoNodes1.iterator().next();
+ todoNodes1.remove(hrn);
+ reachableNodes1.add(hrn);
- // then visit every heap region node
- Set s = id2hrn.entrySet();
- Iterator i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry)i.next();
- HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+ Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
+ while (edgeItr.hasNext()) {
+ RefEdge edge = edgeItr.next();
- if( !pruneGarbage ||
- (hrn.isFlagged() && hrn.getID() > 0) ||
- hrn.getDescription().startsWith("param")
- ) {
+ if (!reachableNodes1.contains(edge.getDst())) {
+ todoNodes1.add(edge.getDst());
+ }
+ }
+ }
- if( !visited.contains(hrn) ) {
- traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
- hrn,
- bw,
- null,
- visited,
- writeReferencers,
- hideSubsetReachability,
- hideEdgeTaints);
- }
- }
- }
+ while (!todoNodes2.isEmpty()) {
+ HeapRegionNode hrn = todoNodes2.iterator().next();
+ todoNodes2.remove(hrn);
+ reachableNodes2.add(hrn);
- bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
- }
-
- // then visit every label node, useful for debugging
- if( writeLabels ) {
- s = td2vn.entrySet();
- i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry)i.next();
- VariableNode ln = (VariableNode) me.getValue();
-
- if( labelSelect ) {
- String labelStr = ln.getTempDescriptorString();
- if( labelStr.startsWith("___temp") ||
- labelStr.startsWith("___dst") ||
- labelStr.startsWith("___srctmp") ||
- labelStr.startsWith("___neverused") ||
- labelStr.contains(qString) ||
- labelStr.contains(rString) ||
- labelStr.contains(blobString)
- ) {
- continue;
- }
- }
+ Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
+ while (edgeItr.hasNext()) {
+ RefEdge edge = edgeItr.next();
- //bw.write(" "+ln.toString() + ";\n");
-
- Iterator<RefEdge> heapRegionsItr = ln.iteratorToReferencees();
- while( heapRegionsItr.hasNext() ) {
- RefEdge edge = heapRegionsItr.next();
- HeapRegionNode hrn = edge.getDst();
-
- if( pruneGarbage && !visited.contains(hrn) ) {
- traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
- hrn,
- bw,
- null,
- visited,
- writeReferencers,
- hideSubsetReachability,
- hideEdgeTaints);
- }
-
- bw.write(" " + ln.toString() +
- " -> " + hrn.toString() +
- "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
- hideEdgeTaints) +
- "\",decorate];\n");
- }
- }
- }
-
-
- bw.write("}\n");
- bw.close();
- }
-
- protected void traverseHeapRegionNodes(int mode,
- HeapRegionNode hrn,
- BufferedWriter bw,
- TempDescriptor td,
- HashSet<HeapRegionNode> visited,
- boolean writeReferencers,
- boolean hideSubsetReachability,
- boolean hideEdgeTaints
- ) throws java.io.IOException {
-
- if( visited.contains(hrn) ) {
- return;
- }
- visited.add(hrn);
+ if (!reachableNodes2.contains(edge.getDst())) {
+ todoNodes2.add(edge.getDst());
+ }
+ }
+ }
- switch( mode ) {
- case VISIT_HRN_WRITE_FULL:
+ Set<HeapRegionNode> intersection =
+ new HashSet<HeapRegionNode>( reachableNodes1 );
- String attributes = "[";
+ intersection.retainAll( reachableNodes2 );
- if( hrn.isSingleObject() ) {
- attributes += "shape=box";
- } else {
- attributes += "shape=Msquare";
- }
+ return intersection;
+ }
+
+ public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
+ HeapRegionNode hrn2) {
+ assert hrn1 != null;
+ assert hrn2 != null;
+
+ // then get the various tokens for these heap regions
+ ReachTuple h1 = ReachTuple.factory(hrn1.getID(),
+ !hrn1.isSingleObject(), ReachTuple.ARITY_ONE, false);
+
+ int arity;
+ if(hrn1.isSingleObject){
+ arity=ReachTuple.ARITY_ONE;
+ }else{
+ arity=ReachTuple.ARITY_ZEROORMORE;
+ }
+ ReachTuple h1star = ReachTuple.factory(hrn1.getID(), !hrn1
+ .isSingleObject(), arity, false);
+
+ ReachTuple h2 = ReachTuple.factory(hrn2.getID(),
+ !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false);
+
+ if(hrn2.isSingleObject){
+ arity=ReachTuple.ARITY_ONE;
+ }else{
+ arity=ReachTuple.ARITY_ZEROORMORE;
+ }
+
+ ReachTuple h2star = ReachTuple.factory(hrn2.getID(), !hrn2
+ .isSingleObject(), arity, false);
+
+ // then get the merged beta of all out-going edges from these heap
+ // regions
+
+ ReachSet beta1 = ReachSet.factory();
+ Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
+ }
+
+ ReachSet beta2 = ReachSet.factory();
+ itrEdge = hrn2.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
+ }
+
+ boolean aliasDetected = false;
+
+ // only do this one if they are different tokens
+ if (h1 != h2 && beta1.containsStateWithBoth(h1, h2)) {
+ aliasDetected = true;
+ }
+// if (beta1.containsStateWithBoth(h1plus, h2)) {
+// aliasDetected = true;
+// }
+ if (beta1.containsStateWithBoth(h1star, h2)) {
+ aliasDetected = true;
+ }
+// if (beta1.containsStateWithBoth(h1, h2plus)) {
+// aliasDetected = true;
+// }
+// if (beta1.containsStateWithBoth(h1plus, h2plus)) {
+// aliasDetected = true;
+// }
+// if (beta1.containsStateWithBoth(h1star, h2plus)) {
+// aliasDetected = true;
+// }
+ if (beta1.containsStateWithBoth(h1, h2star)) {
+ aliasDetected = true;
+ }
+// if (beta1.containsStateWithBoth(h1plus, h2star)) {
+// aliasDetected = true;
+// }
+ if (beta1.containsStateWithBoth(h1star, h2star)) {
+ aliasDetected = true;
+ }
+
+ if (h1 != h2 && beta2.containsStateWithBoth(h1, h2)) {
+ aliasDetected = true;
+ }
+// if (beta2.containsStateWithBoth(h1plus, h2)) {
+// aliasDetected = true;
+// }
+ if (beta2.containsStateWithBoth(h1star, h2)) {
+ aliasDetected = true;
+ }
+// if (beta2.containsStateWithBoth(h1, h2plus)) {
+// aliasDetected = true;
+// }
+// if (beta2.containsStateWithBoth(h1plus, h2plus)) {
+// aliasDetected = true;
+// }
+// if (beta2.containsStateWithBoth(h1star, h2plus)) {
+// aliasDetected = true;
+// }
+ if (beta2.containsStateWithBoth(h1, h2star)) {
+ aliasDetected = true;
+ }
+// if (beta2.containsStateWithBoth(h1plus, h2star)) {
+// aliasDetected = true;
+// }
+ if (beta2.containsStateWithBoth(h1star, h2star)) {
+ aliasDetected = true;
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if (aliasDetected) {
+ common = findCommonReachableNodes(hrn1, hrn2);
+ if (!(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP)) {
+ assert !common.isEmpty();
+ }
+ }
+
+ return common;
+ }
- if( hrn.isFlagged() ) {
- attributes += ",style=filled,fillcolor=lightgrey";
- }
+ public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
+ Integer paramIndex1, Integer paramIndex2) {
- attributes += ",label=\"ID" +
- hrn.getID() +
- "\\n";
+ // get parameter's heap regions
+ TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
+ VariableNode argVar1 = getVariableNodeFromTemp(paramTemp1);
+ RefEdge argEdge1 = argVar1.iteratorToReferencees().next();
+ HeapRegionNode hrnParam1 = argEdge1.getDst();
- if( hrn.getType() != null ) {
- attributes += hrn.getType().toPrettyString() + "\\n";
- }
-
- attributes += hrn.getDescription() +
- "\\n" +
- hrn.getAlphaString(hideSubsetReachability) +
- "\"]";
+ TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
+ VariableNode argVar2 = getVariableNodeFromTemp(paramTemp2);
+ RefEdge argEdge2 = argVar2.iteratorToReferencees().next();
+ HeapRegionNode hrnParam2 = argEdge2.getDst();
- bw.write(" " + hrn.toString() + attributes + ";\n");
- break;
- }
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
+ return common;
+ }
+ public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
+ Integer paramIndex, AllocSite as) {
- Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
- while( childRegionsItr.hasNext() ) {
- RefEdge edge = childRegionsItr.next();
- HeapRegionNode hrnChild = edge.getDst();
+ // get parameter's heap regions
+ TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
+ VariableNode argVar = getVariableNodeFromTemp(paramTemp);
+ RefEdge argEdge = argVar.iteratorToReferencees().next();
+ HeapRegionNode hrnParam = argEdge.getDst();
- switch( mode ) {
- case VISIT_HRN_WRITE_FULL:
- bw.write(" " + hrn.toString() +
- " -> " + hrnChild.toString() +
- "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
- hideEdgeTaints) +
- "\",decorate];\n");
- break;
- }
+ // get summary node
+ HeapRegionNode hrnSummary=null;
+ if(id2hrn.containsKey(as.getSummary())){
+ // if summary node doesn't exist, ignore this case
+ hrnSummary = id2hrn.get(as.getSummary());
+ assert hrnSummary != null;
+ }
- traverseHeapRegionNodes(mode,
- hrnChild,
- bw,
- td,
- visited,
- writeReferencers,
- hideSubsetReachability,
- hideEdgeTaints);
- }
- }
-
- public int getTaintIdentifierFromHRN(HeapRegionNode hrn){
- HashSet<RefEdge> referenceEdges=hrn.referencers;
- Iterator<RefEdge> iter=referenceEdges.iterator();
-
- int taintIdentifier=0;
- while(iter.hasNext()){
- RefEdge edge=iter.next();
- taintIdentifier=taintIdentifier | edge.getTaintIdentifier();
- }
-
- return taintIdentifier;
-
- }
-
- public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
-
- HashSet<RefEdge> setEdge=hrn.referencers;
- Iterator<RefEdge> iter=setEdge.iterator();
- while(iter.hasNext()){
- RefEdge edge= iter.next();
- edge.unionTaintIdentifier(newTaintIdentifier);
- if(edge.getSrc() instanceof HeapRegionNode){
-
- HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
- //check whether it is reflexive edge
- if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
- visitedSet.add(refHRN);
- propagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
- }
-
- }
- }
-
- }
-
- public void depropagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
-
- HashSet<RefEdge> setEdge=hrn.referencers;
- Iterator<RefEdge> iter=setEdge.iterator();
- while(iter.hasNext()){
- RefEdge edge= iter.next();
- edge.minusTaintIdentifier(newTaintIdentifier);
- if(edge.getSrc() instanceof HeapRegionNode){
-
- HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
- //check whether it is reflexive edge
- if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){
- visitedSet.add(refHRN);
- depropagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
- }
-
- }
- }
-
- }
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if(hrnSummary!=null){
+ common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
+ }
+ // check for other nodes
+ for (int i = 0; i < as.getAllocationDepth(); ++i) {
- // in this analysis specifically:
- // we have a notion that a null type is the "match any" type,
- // so wrap calls to the utility methods that deal with null
- public TypeDescriptor mostSpecificType( TypeDescriptor td1,
- TypeDescriptor td2 ) {
- if( td1 == null ) {
- return td2;
- }
- if( td2 == null ) {
- return td1;
- }
- if( td1.isNull() ) {
- return td2;
- }
- if( td2.isNull() ) {
- return td1;
- }
- return typeUtil.mostSpecific( td1, td2 );
- }
-
- public TypeDescriptor mostSpecificType( TypeDescriptor td1,
- TypeDescriptor td2,
- TypeDescriptor td3 ) {
-
- return mostSpecificType( td1,
- mostSpecificType( td2, td3 )
- );
- }
-
- public TypeDescriptor mostSpecificType( TypeDescriptor td1,
- TypeDescriptor td2,
- TypeDescriptor td3,
- TypeDescriptor td4 ) {
-
- return mostSpecificType( mostSpecificType( td1, td2 ),
- mostSpecificType( td3, td4 )
- );
- }
+ assert id2hrn.containsKey(as.getIthOldest(i));
+ HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
+ assert hrnIthOldest != null;
- // remember, in this analysis a null type means "any type"
- public boolean isSuperiorType( TypeDescriptor possibleSuper,
- TypeDescriptor possibleChild ) {
- if( possibleSuper == null ||
- possibleChild == null ) {
- return true;
- }
+ common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
- if( possibleSuper.isNull() ||
- possibleChild.isNull() ) {
- return true;
- }
+ }
- return typeUtil.isSuperorType( possibleSuper, possibleChild );
- }
+ return common;
+ }
- public String generateUniqueIdentifier(FlatMethod fm, int paramIdx, String type){
-
- //type: A->aliapsed parameter heap region
- // P -> primary paramter heap region
- // S -> secondary paramter heap region
-
- String identifier;
- if(type.equals("A")){
- //aliased param
- identifier="FM"+fm.hashCode()+".A";
- }else{
- identifier="FM"+fm.hashCode()+"."+paramIdx+"."+type;
- }
- return identifier;
-
- }
+ public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
+ AllocSite as2) {
+
+ // get summary node 1's alpha
+ Integer idSum1 = as1.getSummary();
+ HeapRegionNode hrnSum1=null;
+ if(id2hrn.containsKey(idSum1)){
+ hrnSum1 = id2hrn.get(idSum1);
+ }
+
+ // get summary node 2's alpha
+ Integer idSum2 = as2.getSummary();
+ HeapRegionNode hrnSum2=null;
+ if(id2hrn.containsKey(idSum2)){
+ hrnSum2 = id2hrn.get(idSum2);
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if(hrnSum1!=null && hrnSum2!=null){
+ common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
+ }
+
+ // check sum2 against alloc1 nodes
+ if(hrnSum2!=null){
+ for (int i = 0; i < as1.getAllocationDepth(); ++i) {
+ Integer idI1 = as1.getIthOldest(i);
+ assert id2hrn.containsKey(idI1);
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+ assert hrnI1 != null;
+ common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
+ }
+ }
+
+ // check sum1 against alloc2 nodes
+ for (int i = 0; i < as2.getAllocationDepth(); ++i) {
+ Integer idI2 = as2.getIthOldest(i);
+ assert id2hrn.containsKey(idI2);
+ HeapRegionNode hrnI2 = id2hrn.get(idI2);
+ assert hrnI2 != null;
+
+ if(hrnSum1!=null){
+ common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
+ }
+
+ // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
+ for (int j = 0; j < as1.getAllocationDepth(); ++j) {
+ Integer idI1 = as1.getIthOldest(j);
+
+ // if these are the same site, don't look for the same token, no
+ // alias.
+ // different tokens of the same site could alias together though
+ if (idI1.equals(idI2)) {
+ continue;
+ }
+
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+
+ common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
+ }
+ }
+
+ return common;
+ }
- public String generateUniqueIdentifier(AllocSite as, int age, boolean isSummary){
-
- String identifier;
-
- FlatNew fn=as.getFlatNew();
-
- if(isSummary){
- identifier="FN"+fn.hashCode()+".S";
- }else{
- identifier="FN"+fn.hashCode()+"."+age;
- }
-
- return identifier;
-
- }
-*/
}
projects / IRC.git / blobdiff