public class OwnershipGraph {
- private int allocationDepth;
- private TypeUtil typeUtil;
+ // use to disable improvements for comparison
+ protected static final boolean DISABLE_STRONG_UPDATES = false;
+ protected static final boolean DISABLE_GLOBAL_SWEEP = false;
+
+ 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;
// there was already one other very similar reason
// for traversing heap nodes that is no longer needed
// actions to take during the traversal
protected static final int VISIT_HRN_WRITE_FULL = 0;
- protected static TempDescriptor tdReturn = new TempDescriptor("_Return___");
+ protected static final String qString = new String( "Q_spec_" );
+ protected static final String rString = new String( "R_spec_" );
+ protected static final String blobString = new String( "_AliasBlob___" );
+
+ protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
+ protected static final TempDescriptor tdAliasBlob = new TempDescriptor( blobString );
+
+ protected static final TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
+ protected static final ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
+ protected static final ReachabilitySet rsWttsEmpty = new ReachabilitySet( ttsEmpty ).makeCanonical();
+
+ // add a bogus entry with the identity rule for easy rewrite
+ // of new callee nodes and edges, doesn't belong to any parameter
+ protected static final int bogusParamIndexInt = -2;
+ protected static final Integer bogusID = new Integer( bogusParamIndexInt );
+ protected static final Integer bogusIndex = new Integer( bogusParamIndexInt );
+ protected static final TokenTuple bogusToken = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONE ).makeCanonical();
+ protected static final TokenTuple bogusTokenPlus = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONEORMORE ).makeCanonical();
+ protected static final TokenTuple bogusTokenStar = new TokenTuple( bogusID, true, TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
+ protected static final ReachabilitySet rsIdentity =
+ new ReachabilitySet( new TokenTupleSet( bogusToken ).makeCanonical() ).makeCanonical();
public Hashtable<Integer, HeapRegionNode> id2hrn;
public Hashtable<TempDescriptor, LabelNode > td2ln;
- public Hashtable<Integer, Integer > id2paramIndex;
- public Hashtable<Integer, Integer > paramIndex2id;
+
+ public Hashtable<Integer, Set<Integer> > idPrimary2paramIndexSet;
+ public Hashtable<Integer, Integer > paramIndex2idPrimary;
+
+ public Hashtable<Integer, Set<Integer> > idSecondary2paramIndexSet;
+ public Hashtable<Integer, Integer > paramIndex2idSecondary;
+
public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
+ public Hashtable<Integer, TempDescriptor> paramIndex2tdR;
+
public HashSet<AllocationSite> allocationSites;
+ public Hashtable<TokenTuple, Integer> paramTokenPrimary2paramIndex;
+ public Hashtable<Integer, TokenTuple> paramIndex2paramTokenPrimary;
+
+ public Hashtable<TokenTuple, Integer> paramTokenSecondary2paramIndex;
+ public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondary;
+ public Hashtable<TokenTuple, Integer> paramTokenSecondaryPlus2paramIndex;
+ public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryPlus;
+ public Hashtable<TokenTuple, Integer> paramTokenSecondaryStar2paramIndex;
+ public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryStar;
+
+
+ public OwnershipGraph() {
+ id2hrn = new Hashtable<Integer, HeapRegionNode>();
+ td2ln = new Hashtable<TempDescriptor, LabelNode >();
+ idPrimary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
+ paramIndex2idPrimary = new Hashtable<Integer, Integer >();
+ idSecondary2paramIndexSet = new Hashtable<Integer, Set<Integer> >();
+ paramIndex2idSecondary = new Hashtable<Integer, Integer >();
+ paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
+ paramIndex2tdR = new Hashtable<Integer, TempDescriptor>();
- public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
- this.allocationDepth = allocationDepth;
- this.typeUtil = typeUtil;
+ paramTokenPrimary2paramIndex = new Hashtable<TokenTuple, Integer >();
+ paramIndex2paramTokenPrimary = new Hashtable<Integer, TokenTuple >();
- id2hrn = new Hashtable<Integer, HeapRegionNode>();
- td2ln = new Hashtable<TempDescriptor, LabelNode >();
- id2paramIndex = new Hashtable<Integer, Integer >();
- paramIndex2id = new Hashtable<Integer, Integer >();
- paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
+ paramTokenSecondary2paramIndex = new Hashtable<TokenTuple, Integer >();
+ paramIndex2paramTokenSecondary = new Hashtable<Integer, TokenTuple >();
+ paramTokenSecondaryPlus2paramIndex = new Hashtable<TokenTuple, Integer >();
+ paramIndex2paramTokenSecondaryPlus = new Hashtable<Integer, TokenTuple >();
+ paramTokenSecondaryStar2paramIndex = new Hashtable<TokenTuple, Integer >();
+ paramIndex2paramTokenSecondaryStar = new Hashtable<Integer, TokenTuple >();
allocationSites = new HashSet <AllocationSite>();
}
protected HeapRegionNode
createNewHeapRegionNode(Integer id,
boolean isSingleObject,
- boolean isFlagged,
boolean isNewSummary,
+ boolean isFlagged,
boolean isParameter,
+ TypeDescriptor type,
AllocationSite allocSite,
ReachabilitySet alpha,
String description) {
+ boolean markForAnalysis = isFlagged || isParameter;
+
+ TypeDescriptor typeToUse = null;
+ if( allocSite != null ) {
+ typeToUse = allocSite.getType();
+ } else {
+ typeToUse = type;
+ }
+
+ if( allocSite != null && allocSite.getDisjointId() != null ) {
+ markForAnalysis = true;
+ }
+
if( id == null ) {
id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
}
if( alpha == null ) {
- if( isFlagged || isParameter ) {
- alpha = new ReachabilitySet(new TokenTuple(id,
- !isSingleObject,
- TokenTuple.ARITY_ONE)
- ).makeCanonical();
+ if( markForAnalysis ) {
+ alpha = new ReachabilitySet(
+ new TokenTuple(id,
+ !isSingleObject,
+ TokenTuple.ARITY_ONE
+ ).makeCanonical()
+ ).makeCanonical();
} else {
- alpha = new ReachabilitySet(new TokenTupleSet()
- ).makeCanonical();
+ alpha = new ReachabilitySet(
+ new TokenTupleSet().makeCanonical()
+ ).makeCanonical();
}
}
HeapRegionNode hrn = new HeapRegionNode(id,
isSingleObject,
- isFlagged,
+ markForAnalysis,
+ isParameter,
isNewSummary,
+ typeToUse,
allocSite,
alpha,
description);
protected void removeReferenceEdge(OwnershipNode referencer,
HeapRegionNode referencee,
- FieldDescriptor fieldDesc) {
+ TypeDescriptor type,
+ String field) {
assert referencer != null;
assert referencee != null;
-
+
ReferenceEdge edge = referencer.getReferenceTo(referencee,
- fieldDesc);
+ type,
+ field);
assert edge != null;
assert edge == referencee.getReferenceFrom(referencer,
- fieldDesc);
+ type,
+ field);
+
+// int oldTaint=edge.getTaintIdentifier();
+// if(referencer instanceof HeapRegionNode){
+// depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
+// }
referencer.removeReferencee(edge);
referencee.removeReferencer(edge);
}
protected void clearReferenceEdgesFrom(OwnershipNode referencer,
- FieldDescriptor fieldDesc,
+ TypeDescriptor type,
+ String field,
boolean removeAll) {
assert referencer != null;
while( i.hasNext() ) {
ReferenceEdge edge = i.next();
- if( removeAll || edge.getFieldDesc() == fieldDesc ) {
- HeapRegionNode referencee = edge.getDst();
+ if( removeAll ||
+ (edge.typeEquals( type ) && edge.fieldEquals( field ))
+ ){
+ HeapRegionNode referencee = edge.getDst();
+
removeReferenceEdge(referencer,
referencee,
- edge.getFieldDesc() );
+ edge.getType(),
+ edge.getField() );
}
}
}
protected void clearReferenceEdgesTo(HeapRegionNode referencee,
- FieldDescriptor fieldDesc,
+ TypeDescriptor type,
+ String field,
boolean removeAll) {
assert referencee != null;
while( i.hasNext() ) {
ReferenceEdge edge = i.next();
- if( removeAll || edge.getFieldDesc() == fieldDesc ) {
+ if( removeAll ||
+ (edge.typeEquals( type ) && edge.fieldEquals( field ))
+ ){
+
OwnershipNode referencer = edge.getSrc();
+
removeReferenceEdge(referencer,
referencee,
- edge.getFieldDesc() );
- }
- }
- }
-
-
- protected void propagateTokensOverNodes(HeapRegionNode nPrime,
- ChangeTupleSet c0,
- HashSet<HeapRegionNode> nodesWithNewAlpha,
- HashSet<ReferenceEdge> edgesWithNewBeta) {
-
- HashSet<HeapRegionNode> todoNodes
- = new HashSet<HeapRegionNode>();
- todoNodes.add(nPrime);
-
- HashSet<ReferenceEdge> todoEdges
- = new HashSet<ReferenceEdge>();
-
- Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
- = new Hashtable<HeapRegionNode, ChangeTupleSet>();
- nodePlannedChanges.put(nPrime, c0);
-
- Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
- = new Hashtable<ReferenceEdge, ChangeTupleSet>();
-
-
- while( !todoNodes.isEmpty() ) {
- HeapRegionNode n = todoNodes.iterator().next();
- ChangeTupleSet C = nodePlannedChanges.get(n);
-
- Iterator itrC = C.iterator();
- while( itrC.hasNext() ) {
- ChangeTuple c = (ChangeTuple) itrC.next();
-
- if( n.getAlpha().contains(c.getSetToMatch() ) ) {
- ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
- n.setAlphaNew(n.getAlphaNew().union(withChange) );
- nodesWithNewAlpha.add(n);
- }
- }
-
- Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
- while( referItr.hasNext() ) {
- ReferenceEdge edge = referItr.next();
- todoEdges.add(edge);
-
- if( !edgePlannedChanges.containsKey(edge) ) {
- edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
- }
-
- edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
- }
-
- Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
- while( refeeItr.hasNext() ) {
- ReferenceEdge edgeF = refeeItr.next();
- HeapRegionNode m = edgeF.getDst();
-
- ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
-
- Iterator<ChangeTuple> itrCprime = C.iterator();
- while( itrCprime.hasNext() ) {
- ChangeTuple c = itrCprime.next();
- if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
- changesToPass = changesToPass.union(c);
- }
- }
-
- if( !changesToPass.isEmpty() ) {
- if( !nodePlannedChanges.containsKey(m) ) {
- nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
- }
-
- ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
-
- if( !changesToPass.isSubset(currentChanges) ) {
-
- nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
- todoNodes.add(m);
- }
- }
- }
-
- todoNodes.remove(n);
- }
-
- propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
- }
-
-
- protected void propagateTokensOverEdges(
- HashSet<ReferenceEdge> todoEdges,
- Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
- HashSet<ReferenceEdge> edgesWithNewBeta) {
-
-
- while( !todoEdges.isEmpty() ) {
- ReferenceEdge edgeE = todoEdges.iterator().next();
- todoEdges.remove(edgeE);
-
- if( !edgePlannedChanges.containsKey(edgeE) ) {
- edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
- }
-
- ChangeTupleSet C = edgePlannedChanges.get(edgeE);
-
- ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
-
- Iterator<ChangeTuple> itrC = C.iterator();
- while( itrC.hasNext() ) {
- ChangeTuple c = itrC.next();
- if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
- ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
- edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
- edgesWithNewBeta.add(edgeE);
- changesToPass = changesToPass.union(c);
- }
- }
-
- OwnershipNode onSrc = edgeE.getSrc();
-
- if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
- HeapRegionNode n = (HeapRegionNode) onSrc;
-
- Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
- while( referItr.hasNext() ) {
- ReferenceEdge edgeF = referItr.next();
-
- if( !edgePlannedChanges.containsKey(edgeF) ) {
- edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
- }
-
- ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
-
- if( !changesToPass.isSubset(currentChanges) ) {
- todoEdges.add(edgeF);
- edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
- }
- }
+ edge.getType(),
+ edge.getField() );
}
}
}
LabelNode lnX = getLabelNodeFromTemp(x);
LabelNode lnY = getLabelNodeFromTemp(y);
- clearReferenceEdgesFrom(lnX, null, true);
+ clearReferenceEdgesFrom(lnX, null, null, true);
Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
while( itrYhrn.hasNext() ) {
- ReferenceEdge edgeY = itrYhrn.next();
+ ReferenceEdge edgeY = itrYhrn.next();
HeapRegionNode referencee = edgeY.getDst();
- ReferenceEdge edgeNew = edgeY.copy();
+ ReferenceEdge edgeNew = edgeY.copy();
edgeNew.setSrc(lnX);
addReferenceEdge(lnX, referencee, edgeNew);
}
+ public void assignTypedTempXEqualToTempY(TempDescriptor x,
+ TempDescriptor y,
+ TypeDescriptor type) {
+
+ LabelNode lnX = getLabelNodeFromTemp(x);
+ LabelNode lnY = getLabelNodeFromTemp(y);
+
+ clearReferenceEdgesFrom(lnX, null, null, true);
+
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode referencee = edgeY.getDst();
+ ReferenceEdge edgeNew = edgeY.copy();
+ edgeNew.setSrc( lnX );
+ edgeNew.setType( type );
+ edgeNew.setField( null );
+
+ addReferenceEdge(lnX, referencee, edgeNew);
+ }
+ }
+
+
public void assignTempXEqualToTempYFieldF(TempDescriptor x,
TempDescriptor y,
FieldDescriptor f) {
LabelNode lnX = getLabelNodeFromTemp(x);
LabelNode lnY = getLabelNodeFromTemp(y);
- clearReferenceEdgesFrom(lnX, null, true);
+ clearReferenceEdgesFrom(lnX, null, null, true);
Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
while( itrYhrn.hasNext() ) {
- ReferenceEdge edgeY = itrYhrn.next();
- HeapRegionNode hrnY = edgeY.getDst();
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
ReachabilitySet betaY = edgeY.getBeta();
Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
while( itrHrnFhrn.hasNext() ) {
- ReferenceEdge edgeHrn = itrHrnFhrn.next();
- HeapRegionNode hrnHrn = edgeHrn.getDst();
+ ReferenceEdge edgeHrn = itrHrnFhrn.next();
+ HeapRegionNode hrnHrn = edgeHrn.getDst();
ReachabilitySet betaHrn = edgeHrn.getBeta();
- if( edgeHrn.getFieldDesc() == null ||
- edgeHrn.getFieldDesc() == f ) {
+ if( edgeHrn.getType() == null ||
+ (edgeHrn.getType() .equals( f.getType() ) &&
+ edgeHrn.getField().equals( f.getSymbol() ) )
+ ) {
ReferenceEdge edgeNew = new ReferenceEdge(lnX,
hrnHrn,
- f,
+ f.getType(),
+ null,
false,
betaY.intersection(betaHrn) );
+
+ int newTaintIdentifier=getTaintIdentifierFromHRN(hrnHrn);
+ edgeNew.setTaintIdentifier(newTaintIdentifier);
addReferenceEdge(lnX, hrnHrn, edgeNew);
}
HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
+ // first look for possible strong updates and remove those edges
+ boolean strongUpdate = false;
+
Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
while( itrXhrn.hasNext() ) {
ReferenceEdge edgeX = itrXhrn.next();
- HeapRegionNode hrnX = edgeX.getDst();
+ HeapRegionNode hrnX = edgeX.getDst();
+
+ // we can do a strong update here if one of two cases holds
+ if( f != null &&
+ f != OwnershipAnalysis.getArrayField( f.getType() ) &&
+ ( (hrnX.getNumReferencers() == 1) || // case 1
+ (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2
+ )
+ ) {
+ if( !DISABLE_STRONG_UPDATES ) {
+ strongUpdate = true;
+ clearReferenceEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
+ }
+ }
+ }
+
+ // then do all token propagation
+ itrXhrn = lnX.iteratorToReferencees();
+ while( itrXhrn.hasNext() ) {
+ ReferenceEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
ReachabilitySet betaX = edgeX.getBeta();
ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
while( itrYhrn.hasNext() ) {
ReferenceEdge edgeY = itrYhrn.next();
- HeapRegionNode hrnY = edgeY.getDst();
- ReachabilitySet O = edgeY.getBeta();
+ HeapRegionNode hrnY = edgeY.getDst();
+ ReachabilitySet O = edgeY.getBeta();
// propagate tokens over nodes starting from hrnSrc, and it will
// then propagate back just up the edges from hrn
ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
-
- HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
+ HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
new Hashtable<ReferenceEdge, ChangeTupleSet>();
propagateTokensOverEdges(todoEdges,
edgePlannedChanges,
edgesWithNewBeta);
+ }
+ }
+
+ // apply the updates to reachability
+ Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
+ while( nodeItr.hasNext() ) {
+ nodeItr.next().applyAlphaNew();
+ }
+ Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
+ while( edgeItr.hasNext() ) {
+ edgeItr.next().applyBetaNew();
+ }
- //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
- // create the actual reference edge hrnX.f -> hrnY
+ // then go back through and add the new edges
+ itrXhrn = lnX.iteratorToReferencees();
+ while( itrXhrn.hasNext() ) {
+ ReferenceEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
+
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+
+ // prepare the new reference edge hrnX.f -> hrnY
ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
hrnY,
- f,
+ f.getType(),
+ f.getSymbol(),
false,
- edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
- //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
+ edgeY.getBeta().pruneBy( hrnX.getAlpha() )
);
- addReferenceEdge(hrnX, hrnY, edgeNew);
- /*
- if( f != null ) {
- // we can do a strong update here if one of two cases holds
- // SAVE FOR LATER, WITHOUT STILL CORRECT
- if( (hrnX.getNumReferencers() == 1) ||
- ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
- ) {
- clearReferenceEdgesFrom( hrnX, f, false );
- }
+ // look to see if an edge with same field exists
+ // and merge with it, otherwise just add the edge
+ ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY,
+ f.getType(),
+ 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>());
+ addReferenceEdge( hrnX, hrnY, edgeNew );
+ }
+ }
+ }
- addReferenceEdge( hrnX, hrnY, edgeNew );
+ // if there was a strong update, make sure to improve
+ // reachability with a global sweep
+ if( strongUpdate ) {
+ if( !DISABLE_GLOBAL_SWEEP ) {
+ globalSweep();
+ }
+ }
+ }
- } else {
- // if the field is null, or "any" field, then
- // look to see if an any field already exists
- // and merge with it, otherwise just add the edge
- ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
- if( edgeExisting != null ) {
- edgeExisting.setBetaNew(
- edgeExisting.getBetaNew().union( edgeNew.getBeta() )
- );
- // a new edge here cannot be reflexive, so existing will
- // always be also not reflexive anymore
- edgeExisting.setIsInitialParamReflexive( false );
- } else {
- addReferenceEdge( hrnX, hrnY, edgeNew );
- }
- }
- */
+
+ // 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 ) {
+ 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(
+ OwnershipAnalysis.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(
+ OwnershipAnalysis.getArrayField( typeDeref )
+ );
+ }
}
}
- Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
- while( nodeItr.hasNext() ) {
- nodeItr.next().applyAlphaNew();
- }
+ // 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 );
+ }
+ }
- Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
- while( edgeItr.hasNext() ) {
- edgeItr.next().applyBetaNew();
+ cd = cd.getSuperDesc();
+ }
}
- }
-
- public void assignTempEqualToParamAlloc(TempDescriptor td,
- boolean isTask,
- Integer paramIndex) {
- assert td != null;
- LabelNode lnParam = getLabelNodeFromTemp(td);
- HeapRegionNode hrn = createNewHeapRegionNode(null,
- false,
- isTask,
- false,
- true,
- null,
- null,
- "param" + paramIndex);
+ // now build everything we need
+ LabelNode lnParam = getLabelNodeFromTemp( 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" );
// 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+"specialQ");
- LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
+ TempDescriptor tdParamQ = new TempDescriptor( td+qString );
+ paramIndex2tdQ.put( paramIndex, tdParamQ );
+ LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
// 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 newID = hrn.getID();
- assert !id2paramIndex.containsKey(newID);
- assert !id2paramIndex.containsValue(paramIndex);
- id2paramIndex.put(newID, paramIndex);
- paramIndex2id.put(paramIndex, newID);
- paramIndex2tdQ.put(paramIndex, tdParamQ);
-
- ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
- true,
- TokenTuple.ARITY_ONE) );
-
- // heap regions for parameters are always multiple object (see above)
- // and have a reference to themselves, because we can't know the
- // structure of memory that is passed into the method. We're assuming
- // the worst here.
+ 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 );
+
+
+ TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
+ false, // multi-object
+ TokenTuple.ARITY_ONE ).makeCanonical();
+
+ HeapRegionNode hrnSecondary = null;
+ Integer newSecondaryID = null;
+ TokenTuple ttSecondary = null;
+ TempDescriptor tdParamR = null;
+ LabelNode lnParamR = null;
+
+ if( createSecondaryRegion ) {
+ tdParamR = new TempDescriptor( td+rString );
+ paramIndex2tdR.put( paramIndex, tdParamR );
+ lnParamR = getLabelNodeFromTemp( tdParamR );
+
+ 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" );
+
+ 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 TokenTuple( newSecondaryID,
+ true, // multi-object
+ TokenTuple.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
+ TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
+ ReachabilitySet betaSoup;
+ if( createSecondaryRegion ) {
+ TokenTupleSet tts1 = new TokenTupleSet( ttSecondary ).makeCanonical();
+ TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttSecondary );
+ betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
+ } else {
+ betaSoup = ReachabilitySet.factory( tts0 );
+ }
ReferenceEdge edgeFromLabel =
- new ReferenceEdge(lnParam, hrn, null, false, beta);
+ new ReferenceEdge( lnParam, // src
+ hrnPrimary, // dst
+ typeParam, // type
+ null, // field
+ false, // special param initial (not needed on label->node)
+ betaSoup ); // reachability
+ edgeFromLabel.tainedBy(paramIndex);
+ addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
ReferenceEdge edgeFromLabelQ =
- new ReferenceEdge(lnParamQ, hrn, null, false, beta);
+ new ReferenceEdge( lnParamQ, // src
+ hrnPrimary, // dst
+ null, // type
+ null, // field
+ false, // special param initial (not needed on label->node)
+ betaSoup ); // reachability
+ edgeFromLabelQ.tainedBy(paramIndex);
+ addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
+
+ ReferenceEdge edgeSecondaryReflexive;
+ if( createSecondaryRegion ) {
+ edgeSecondaryReflexive =
+ new ReferenceEdge( hrnSecondary, // src
+ hrnSecondary, // dst
+ null, // match all types
+ null, // match all fields
+ true, // special param initial
+ betaSoup ); // reachability
+ addReferenceEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive );
+
+ ReferenceEdge edgeSecondary2Primary =
+ new ReferenceEdge( hrnSecondary, // src
+ hrnPrimary, // dst
+ null, // match all types
+ null, // match all fields
+ true, // special param initial
+ betaSoup ); // reachability
+ addReferenceEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary );
+
+ ReferenceEdge edgeFromLabelR =
+ new ReferenceEdge( lnParamR, // src
+ hrnSecondary, // dst
+ null, // type
+ null, // field
+ false, // special param initial (not needed on label->node)
+ betaSoup ); // reachability
+ edgeFromLabelR.tainedBy(paramIndex);
+ addReferenceEdge( lnParamR, hrnSecondary, edgeFromLabelR );
+ }
+
+ Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
+ while( fieldItr.hasNext() ) {
+ FieldDescriptor fd = fieldItr.next();
+
+ ReferenceEdge edgePrimaryReflexive =
+ new ReferenceEdge( hrnPrimary, // src
+ hrnPrimary, // dst
+ fd.getType(), // type
+ fd.getSymbol(), // field
+ true, // special param initial
+ betaSoup ); // reachability
+ addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
+ }
+
+ fieldItr = primary2secondaryFields.iterator();
+ while( fieldItr.hasNext() ) {
+ FieldDescriptor fd = fieldItr.next();
+
+ ReferenceEdge edgePrimary2Secondary =
+ new ReferenceEdge( hrnPrimary, // src
+ hrnSecondary, // dst
+ fd.getType(), // type
+ fd.getSymbol(), // field
+ true, // special param initial
+ betaSoup ); // reachability
+ addReferenceEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary );
+ }
+ }
+
+
+ public void makeAliasedParamHeapRegionNode() {
+
+ LabelNode lnBlob = getLabelNodeFromTemp( tdAliasBlob );
+ 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" );
+
+
+ ReachabilitySet beta = new ReachabilitySet( new TokenTuple( hrn.getID(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical()
+ ).makeCanonical();
+
+ ReferenceEdge edgeFromLabel =
+ new ReferenceEdge( lnBlob, hrn, null, null, false, beta );
ReferenceEdge edgeReflexive =
- new ReferenceEdge(hrn, hrn, null, true, beta);
+ new ReferenceEdge( hrn, hrn, null, null, true, beta );
+
+ addReferenceEdge( lnBlob, hrn, edgeFromLabel );
+ addReferenceEdge( hrn, hrn, edgeReflexive );
+ }
+
+
+ public void assignTempEqualToAliasedParam( TempDescriptor tdParam,
+ Integer paramIndex ) {
+ assert tdParam != null;
+
+ TypeDescriptor typeParam = tdParam.getType();
+ assert typeParam != null;
+
+ LabelNode lnParam = getLabelNodeFromTemp( tdParam );
+ LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
+
+ // 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 );
+
+ LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
+ LabelNode lnParamR = getLabelNodeFromTemp( tdParamR );
+
+ // 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();
+
+
+ TokenTuple ttAliased = new TokenTuple( idAliased,
+ true, // multi-object
+ TokenTuple.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" );
+
+ 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 );
+
+
+
+ TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
+ false, // multi-object
+ TokenTuple.ARITY_ONE ).makeCanonical();
+
+
+ TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
+ TokenTupleSet tts1 = new TokenTupleSet( ttAliased ).makeCanonical();
+ TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttAliased );
+ ReachabilitySet betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
+
+
+ ReferenceEdge edgeFromLabel =
+ new ReferenceEdge( lnParam, // src
+ hrnPrimary, // dst
+ typeParam, // type
+ null, // field
+ false, // special param initial (not needed on label->node)
+ betaSoup ); // reachability
+ edgeFromLabel.tainedBy(paramIndex);
+ addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
+
+ ReferenceEdge edgeFromLabelQ =
+ new ReferenceEdge( lnParamQ, // src
+ hrnPrimary, // dst
+ null, // type
+ null, // field
+ false, // special param initial (not needed on label->node)
+ betaSoup ); // reachability
+ edgeFromLabelQ.tainedBy(paramIndex);
+ addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
+
+ ReferenceEdge edgeAliased2Primary =
+ new ReferenceEdge( hrnAliasBlob, // src
+ hrnPrimary, // dst
+ null, // match all types
+ null, // match all fields
+ true, // special param initial
+ betaSoup ); // reachability
+ addReferenceEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary );
+
+ ReferenceEdge edgeFromLabelR =
+ new ReferenceEdge( lnParamR, // src
+ hrnAliasBlob, // dst
+ null, // type
+ null, // field
+ false, // special param initial (not needed on label->node)
+ betaSoup ); // reachability
+ edgeFromLabelR.tainedBy(paramIndex);
+ addReferenceEdge( lnParamR, hrnAliasBlob, edgeFromLabelR );
+ }
- addReferenceEdge(lnParam, hrn, edgeFromLabel);
- addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
- addReferenceEdge(hrn, hrn, edgeReflexive);
+
+ public void addParam2ParamAliasEdges( FlatMethod fm,
+ Set<Integer> aliasedParamIndices ) {
+
+ LabelNode lnAliased = getLabelNodeFromTemp( 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();
+
+
+ TokenTuple ttAliased = new TokenTuple( idAliased,
+ true, // multi-object
+ TokenTuple.ARITY_ONE ).makeCanonical();
+
+
+ Iterator<Integer> apItrI = aliasedParamIndices.iterator();
+ while( apItrI.hasNext() ) {
+ Integer i = apItrI.next();
+ TempDescriptor tdParamI = fm.getParameter( i );
+ TypeDescriptor typeI = tdParamI.getType();
+ LabelNode lnParamI = getLabelNodeFromTemp( tdParamI );
+
+ Integer idPrimaryI = paramIndex2idPrimary.get( i );
+
+ /*
+ if( idPrimaryI == null ) {
+ try {
+ writeGraph( "debugalias",
+ 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( Exception e ) {}
+ System.out.println( "FlatMethod="+fm+"\nalias set="+aliasedParamIndices+
+ "\nindex bad="+i);
+ }
+ */
+
+ assert idPrimaryI != null;
+ HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
+ assert primaryI != null;
+
+ TokenTuple ttPrimaryI = new TokenTuple( idPrimaryI,
+ false, // multi-object
+ TokenTuple.ARITY_ONE ).makeCanonical();
+
+ TokenTupleSet ttsI = new TokenTupleSet( ttPrimaryI ).makeCanonical();
+ TokenTupleSet ttsA = new TokenTupleSet( ttAliased ).makeCanonical();
+ TokenTupleSet ttsIA = new TokenTupleSet( ttPrimaryI ).makeCanonical().union( ttAliased );
+ ReachabilitySet betaSoup = ReachabilitySet.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(
+ OwnershipAnalysis.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(
+ OwnershipAnalysis.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();
+
+ ReferenceEdge edgePrimaryReflexive =
+ new ReferenceEdge( primaryI, // src
+ primaryI, // dst
+ fd.getType(), // type
+ fd.getSymbol(), // field
+ true, // special param initial
+ betaSoup ); // reachability
+ addReferenceEdge( primaryI, primaryI, edgePrimaryReflexive );
+ }
+
+ fieldItr = primary2secondaryFields.iterator();
+ while( fieldItr.hasNext() ) {
+ FieldDescriptor fd = fieldItr.next();
+ TypeDescriptor typeField = fd.getType();
+ assert typeField != null;
+
+ ReferenceEdge edgePrimary2Secondary =
+ new ReferenceEdge( primaryI, // src
+ hrnAliasBlob, // dst
+ fd.getType(), // type
+ fd.getSymbol(), // field
+ true, // special param initial
+ betaSoup ); // reachability
+ addReferenceEdge( 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;
+
+ TokenTuple ttPrimaryJ = new TokenTuple( idPrimaryJ,
+ false, // multi-object
+ TokenTuple.ARITY_ONE ).makeCanonical();
+
+ TokenTupleSet ttsJ = new TokenTupleSet( ttPrimaryJ ).makeCanonical();
+ TokenTupleSet ttsIJ = ttsI.union( ttsJ );
+ TokenTupleSet ttsAJ = ttsA.union( ttsJ );
+ TokenTupleSet ttsIAJ = ttsIA.union( ttsJ );
+ ReachabilitySet betaSoupWJ = ReachabilitySet.factory( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
+
+ ReferenceEdge edgePrimaryI2PrimaryJ =
+ new ReferenceEdge( primaryI, // src
+ primaryJ, // dst
+ fd.getType(), // type
+ fd.getSymbol(), // field
+ true, // special param initial
+ betaSoupWJ ); // reachability
+ addReferenceEdge( 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();
+ LabelNode lnParamJ = getLabelNodeFromTemp( 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;
+
+ ReferenceEdge lnJ2PrimaryJ = lnParamJ.getReferenceTo( primaryJ,
+ tdParamJ.getType(),
+ null );
+ assert lnJ2PrimaryJ != null;
+
+ ReferenceEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy();
+ lnI2PrimaryJ.setSrc( lnParamI );
+ lnI2PrimaryJ.setType( tdParamI.getType() );
+ lnI2PrimaryJ.tainedBy(new Integer(j));
+ addReferenceEdge( 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 );
+
+ TokenTuple p_i = new TokenTuple( hrnPrimary.getID(),
+ false, // multiple-object?
+ TokenTuple.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 );
+
+ TokenTuple s_i = new TokenTuple( hrnSecondary.getID(),
+ true, // multiple-object?
+ TokenTuple.ARITY_ONE ).makeCanonical();
+ paramTokenSecondary2paramIndex.put( s_i, paramIndex );
+ paramIndex2paramTokenSecondary.put( paramIndex, s_i );
+
+ TokenTuple s_i_plus = new TokenTuple( hrnSecondary.getID(),
+ true, // multiple-object?
+ TokenTuple.ARITY_ONEORMORE ).makeCanonical();
+ paramTokenSecondaryPlus2paramIndex.put( s_i_plus, paramIndex );
+ paramIndex2paramTokenSecondaryPlus.put( paramIndex, s_i_plus );
+
+ TokenTuple s_i_star = new TokenTuple( hrnSecondary.getID(),
+ true, // multiple-object?
+ TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
+ paramTokenSecondaryStar2paramIndex.put( s_i_star, paramIndex );
+ paramIndex2paramTokenSecondaryStar.put( paramIndex, s_i_star );
+ }
+ }
+ }
+
+
public void assignReturnEqualToTemp(TempDescriptor x) {
LabelNode lnR = getLabelNodeFromTemp(tdReturn);
LabelNode lnX = getLabelNodeFromTemp(x);
- clearReferenceEdgesFrom(lnR, null, true);
+ clearReferenceEdgesFrom(lnR, null, null, true);
Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
while( itrXhrn.hasNext() ) {
assert x != null;
assert as != null;
- age(as);
+ age( as );
// after the age operation the newest (or zero-ith oldest)
// node associated with the allocation site should have
// no references to it as if it were a newly allocated
- // heap region, so make a reference to it to complete
- // this operation
-
- Integer idNewest = as.getIthOldest(0);
- HeapRegionNode hrnNewest = id2hrn.get(idNewest);
- assert hrnNewest != null;
-
- LabelNode lnX = getLabelNodeFromTemp(x);
- clearReferenceEdgesFrom(lnX, null, true);
-
- ReferenceEdge edgeNew =
- new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
-
- addReferenceEdge(lnX, hrnNewest, edgeNew);
+ // heap region
+ Integer idNewest = as.getIthOldest( 0 );
+ HeapRegionNode hrnNewest = id2hrn.get( idNewest );
+ assert hrnNewest != null;
+
+ LabelNode lnX = getLabelNodeFromTemp( x );
+ clearReferenceEdgesFrom( lnX, null, null, true );
+
+ // make a new reference to allocated node
+ TypeDescriptor type = as.getType();
+ ReferenceEdge edgeNew =
+ new ReferenceEdge( lnX, // source
+ hrnNewest, // dest
+ type, // type
+ null, // field name
+ false, // is initial param
+ hrnNewest.getAlpha() // beta
+ );
+
+ addReferenceEdge( lnX, hrnNewest, edgeNew );
}
assert hrn0 != null;
// clear all references in and out of newest node
- clearReferenceEdgesFrom(hrn0, null, true);
- clearReferenceEdgesTo(hrn0, null, true);
+ clearReferenceEdgesFrom(hrn0, null, null, true);
+ clearReferenceEdgesTo(hrn0, null, null, true);
// now tokens in reachability sets need to "age" also
// after tokens have been aged, reset newest node's reachability
if( hrn0.isFlagged() ) {
- hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
- new TokenTuple(hrn0)
- )
- ).makeCanonical()
+ hrn0.setAlpha(new ReachabilitySet(
+ new TokenTupleSet(
+ new TokenTuple(hrn0).makeCanonical()
+ ).makeCanonical()
+ ).makeCanonical()
);
} else {
- hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
- ).makeCanonical()
+ hrn0.setAlpha(new ReachabilitySet(
+ new TokenTupleSet().makeCanonical()
+ ).makeCanonical()
);
}
}
if( as.getType().isClass() ) {
hasFlags = as.getType().getClassDesc().hasFlags();
}
+
+ if(as.getFlag()){
+ hasFlags=as.getFlag();
+ }
- hrnSummary = createNewHeapRegionNode(idSummary,
- false,
- hasFlags,
- true,
- false,
- as,
- null,
- as + "\\n" + as.getType() + "\\nsummary");
+ 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");
for( int i = 0; i < as.getAllocationDepth(); ++i ) {
Integer idIth = as.getIthOldest(i);
assert !id2hrn.containsKey(idIth);
- createNewHeapRegionNode(idIth,
- true,
- hasFlags,
- false,
- false,
- as,
- null,
- as + "\\n" + as.getType() + "\\n" + i + " oldest");
+ 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");
}
}
hasFlags = as.getType().getClassDesc().hasFlags();
}
- hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
- false,
- hasFlags,
- true,
- false,
- as,
- null,
+ 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,
- true,
- hasFlags,
- false,
- false,
- as,
- null,
+ 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");
}
}
edgeMerged.setSrc(hrnSummary);
HeapRegionNode hrnReferencee = edge.getDst();
- ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
+ ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee,
+ edge.getType(),
+ edge.getField() );
if( edgeSummary == null ) {
// the merge is trivial, nothing to be done
edgeMerged.setDst(hrnSummary);
OwnershipNode onReferencer = edge.getSrc();
- ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
+ ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary,
+ edge.getType(),
+ edge.getField() );
+
+ if( edgeSummary == null ) {
+ // the merge is trivial, nothing to be done
+ } 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() ) );
+ }
+
+ addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
+ }
+
+ // then merge hrn reachability into hrnSummary
+ hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
+ }
+
+
+ protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
+
+ // clear references in and out of node b
+ clearReferenceEdgesFrom(hrnB, null, null, true);
+ clearReferenceEdgesTo(hrnB, null, null, true);
+
+ // copy each edge in and out of A to B
+ Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
+ while( itrReferencee.hasNext() ) {
+ ReferenceEdge edge = itrReferencee.next();
+ HeapRegionNode hrnReferencee = edge.getDst();
+ ReferenceEdge edgeNew = edge.copy();
+ edgeNew.setSrc(hrnB);
+
+ addReferenceEdge(hrnB, hrnReferencee, edgeNew);
+ }
+
+ Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
+ while( itrReferencer.hasNext() ) {
+ ReferenceEdge edge = itrReferencer.next();
+ OwnershipNode onReferencer = edge.getSrc();
+ ReferenceEdge edgeNew = edge.copy();
+ edgeNew.setDst(hrnB);
+
+ addReferenceEdge(onReferencer, hrnB, edgeNew);
+ }
+
+ // replace hrnB reachability with hrnA's
+ hrnB.setAlpha(hrnA.getAlpha() );
+ }
+
+
+ protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
+ edge.setBeta(edge.getBeta().ageTokens(as) );
+ }
+
+ protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
+ hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
+ }
+
+
+
+ protected void propagateTokensOverNodes(HeapRegionNode nPrime,
+ ChangeTupleSet c0,
+ HashSet<HeapRegionNode> nodesWithNewAlpha,
+ HashSet<ReferenceEdge> edgesWithNewBeta) {
+
+ HashSet<HeapRegionNode> todoNodes
+ = new HashSet<HeapRegionNode>();
+ todoNodes.add(nPrime);
+
+ HashSet<ReferenceEdge> todoEdges
+ = new HashSet<ReferenceEdge>();
+
+ Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
+ = new Hashtable<HeapRegionNode, ChangeTupleSet>();
+ nodePlannedChanges.put(nPrime, c0);
+
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
+ = new Hashtable<ReferenceEdge, ChangeTupleSet>();
+
+ // first propagate change sets everywhere they can go
+ while( !todoNodes.isEmpty() ) {
+ HeapRegionNode n = todoNodes.iterator().next();
+ ChangeTupleSet C = nodePlannedChanges.get(n);
+
+ Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
+ while( referItr.hasNext() ) {
+ ReferenceEdge edge = referItr.next();
+ todoEdges.add(edge);
+
+ if( !edgePlannedChanges.containsKey(edge) ) {
+ edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
+ }
+
+ edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
+ }
+
+ Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
+ while( refeeItr.hasNext() ) {
+ ReferenceEdge edgeF = refeeItr.next();
+ HeapRegionNode m = edgeF.getDst();
+
+ ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
+
+ Iterator<ChangeTuple> itrCprime = C.iterator();
+ while( itrCprime.hasNext() ) {
+ ChangeTuple c = itrCprime.next();
+ if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
+ changesToPass = changesToPass.union(c);
+ }
+ }
+
+ if( !changesToPass.isEmpty() ) {
+ if( !nodePlannedChanges.containsKey(m) ) {
+ nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
+
+ if( !changesToPass.isSubset(currentChanges) ) {
+
+ nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
+ todoNodes.add(m);
+ }
+ }
+ }
+
+ todoNodes.remove(n);
+ }
+
+ // then apply all of the changes for each node at once
+ Iterator itrMap = nodePlannedChanges.entrySet().iterator();
+ while( itrMap.hasNext() ) {
+ Map.Entry me = (Map.Entry) itrMap.next();
+ HeapRegionNode n = (HeapRegionNode) me.getKey();
+ ChangeTupleSet C = (ChangeTupleSet) me.getValue();
+
+ n.setAlphaNew( n.getAlpha().applyChangeSet( C, true ) );
+ nodesWithNewAlpha.add( n );
+ }
+
+ propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
+ }
+
+
+ protected void propagateTokensOverEdges(
+ HashSet<ReferenceEdge> todoEdges,
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
+ HashSet<ReferenceEdge> edgesWithNewBeta) {
+
+ // first propagate all change tuples everywhere they can go
+ while( !todoEdges.isEmpty() ) {
+ ReferenceEdge edgeE = todoEdges.iterator().next();
+ todoEdges.remove(edgeE);
+
+ if( !edgePlannedChanges.containsKey(edgeE) ) {
+ edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet C = edgePlannedChanges.get(edgeE);
+
+ ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
+
+ Iterator<ChangeTuple> itrC = C.iterator();
+ while( itrC.hasNext() ) {
+ ChangeTuple c = itrC.next();
+ if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
+ changesToPass = changesToPass.union(c);
+ }
+ }
+
+ OwnershipNode onSrc = edgeE.getSrc();
+
+ if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
+ HeapRegionNode n = (HeapRegionNode) onSrc;
+
+ Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
+ while( referItr.hasNext() ) {
+ ReferenceEdge edgeF = referItr.next();
+
+ if( !edgePlannedChanges.containsKey(edgeF) ) {
+ edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
+
+ if( !changesToPass.isSubset(currentChanges) ) {
+ todoEdges.add(edgeF);
+ edgePlannedChanges.put(edgeF, currentChanges.union(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();
+ ReferenceEdge e = (ReferenceEdge) me.getKey();
+ ChangeTupleSet C = (ChangeTupleSet) me.getValue();
+
+ e.setBetaNew( e.getBetaNew().union( e.getBeta().applyChangeSet( C, true ) ) );
+ edgesWithNewBeta.add( e );
+ }
+ }
+
+
+ public Set<Integer> calculateAliasedParamSet( FlatCall fc,
+ FlatMethod fm ) {
+ // to decide if two parameters are aliased, look
+ // at the caller graph (this graph) and if these
+ // two conditions are met, they may be aliased:
+ // 1. The argument labels reference a shared node
+ // 2. The edges to that shared node have a common
+ // reachability state.
+
+ Set<Integer> aliasedIndices = new HashSet<Integer>();
+
+
+ //System.out.println("Aliases for "+fm+" at "+fc);
+
+
+ for( int i = 0; i < fm.numParameters(); ++i ) {
+ for( int j = 0; j < i; ++j ) {
+
+ TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, i );
+ LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
+
+ TempDescriptor argTemp_j = fc.getArgMatchingParamIndex( fm, j );
+ LabelNode argLabel_j = getLabelNodeFromTemp( argTemp_j );
+
+ /*
+ System.out.println(" "+argTemp_i.getType()+" "+argTemp_i+" and "+
+ argTemp_j.getType()+" "+argTemp_j+" aliased?");
+ */
+
+ // first condition--do these arguments
+ // reference any common nodes?
+ Iterator<ReferenceEdge> edgeItr;
+
+ Set<HeapRegionNode> hrnSetI = new HashSet<HeapRegionNode>();
+ edgeItr = argLabel_i.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ hrnSetI.add( edgeItr.next().getDst() );
+ }
+
+ Set<HeapRegionNode> hrnSetJ = new HashSet<HeapRegionNode>();
+ edgeItr = argLabel_j.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ hrnSetJ.add( edgeItr.next().getDst() );
+ }
+
+ Set<HeapRegionNode> intersection =
+ new HashSet<HeapRegionNode>( hrnSetI );
+ intersection.retainAll( hrnSetJ );
+
+ // condition two--for each shared node, do the reference
+ // edges to it from arguments have a common reachability
+ // state that is *ALSO* on the shared node?
+ boolean foundAlias = false;
+
+ Iterator<HeapRegionNode> hrnItr = intersection.iterator();
+ while( hrnItr.hasNext() ) {
+ HeapRegionNode hrn = hrnItr.next();
+
+ ReferenceEdge ei = argLabel_i.getReferenceTo( hrn,
+ argTemp_i.getType(),
+ null );
+
+ ReferenceEdge ej = argLabel_j.getReferenceTo( hrn,
+ argTemp_j.getType(),
+ null );
+ assert ei != null;
+ assert ej != null;
+
+ ReachabilitySet allStatesForParamI =
+ ei.getBeta().intersection( hrn.getAlpha() );
+
+ ReachabilitySet allStatesForParamJ =
+ ej.getBeta().intersection( hrn.getAlpha() );
+
+ ReachabilitySet commonStates =
+ allStatesForParamI.intersection( allStatesForParamJ );
+
+ if( !commonStates.isEmpty() ) {
+ foundAlias = true;
+ aliasedIndices.add( new Integer( i ) );
+ aliasedIndices.add( new Integer( j ) );
+
+ //System.out.println( " yes!" );
+ }
+ }
- if( edgeSummary == null ) {
- // the merge is trivial, nothing to be done
- } 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() ) );
+ // as soon as we detect one possible way to alias
+ // these parameters, skip on to another pair
+ if( foundAlias ) {
+ continue;
+ }
}
-
- addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
}
- // then merge hrn reachability into hrnSummary
- hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
+ if( !aliasedIndices.isEmpty() ) {
+ try {
+ writeGraph( "foundaliases",
+ 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( Exception e ) {}
+ /*
+ System.out.println("FlatCall="+fc+
+ "\nflat method="+fm+
+ "\nAliases="+aliasedIndices );
+ */
+ }
+
+ return aliasedIndices;
}
- protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
+ private String makeMapKey( Integer i, Integer j, String field ) {
+ return i+","+j+","+field;
+ }
- // clear references in and out of node i
- clearReferenceEdgesFrom(hrnB, null, true);
- clearReferenceEdgesTo(hrnB, null, true);
+ private String makeMapKey( Integer i, String field ) {
+ return i+","+field;
+ }
- // copy each edge in and out of A to B
- Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
- while( itrReferencee.hasNext() ) {
- ReferenceEdge edge = itrReferencee.next();
- HeapRegionNode hrnReferencee = edge.getDst();
- ReferenceEdge edgeNew = edge.copy();
- edgeNew.setSrc(hrnB);
+ // 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>();
+ }
+ edge_index_pairs.put( indexI, ei );
+ }
- addReferenceEdge(hrnB, hrnReferencee, edgeNew);
+ private void addEdgeIndexPair( Hashtable< Integer, Set<Vector> > edge_index_pairs,
+ Integer indexI,
+ ReferenceEdge 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 );
+ }
- Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
- while( itrReferencer.hasNext() ) {
- ReferenceEdge edge = itrReferencer.next();
- OwnershipNode onReferencer = edge.getSrc();
- ReferenceEdge edgeNew = edge.copy();
- edgeNew.setDst(hrnB);
+ private ReachabilitySet funcScriptR( ReachabilitySet rsIn,
+ OwnershipGraph ogCallee,
+ MethodContext mc ) {
- addReferenceEdge(onReferencer, hrnB, edgeNew);
- }
+ ReachabilitySet rsOut = new ReachabilitySet( rsIn );
- // replace hrnB reachability with hrnA's
- hrnB.setAlpha(hrnA.getAlpha() );
- }
+ Iterator itr = ogCallee.paramIndex2paramTokenPrimary.entrySet().iterator();
+ while( itr.hasNext() ) {
+ Map.Entry me = (Map.Entry) itr.next();
+ Integer i = (Integer) me.getKey();
+ TokenTuple p_i = (TokenTuple) me.getValue();
+ TokenTuple 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;
+ }
- protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
- edge.setBeta(edge.getBeta().ageTokens(as) );
+ rsOut = rsOut.removeTokenAIfTokenB( p_i, s_i );
+ }
+
+ return rsOut;
}
- protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
- hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
+ // detects strong updates to the primary parameter object and
+ // effects the removal of old edges in the calling graph
+ private void effectCalleeStrongUpdates( Integer paramIndex,
+ OwnershipGraph 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 ) {
+
+ 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() ) ) {
+ clearReferenceEdgesFrom( hrnCaller, fd.getType(), fd.getSymbol(), false );
+ }
+ }
+
+ cd = cd.getSuperDesc();
+ }
}
+ private boolean hasFieldBeenUpdated( HeapRegionNode hrnPrimary, String field ) {
- public void resolveMethodCall(FlatCall fc,
- boolean isStatic,
- FlatMethod fm,
- OwnershipGraph ogCallee) {
+ Iterator<ReferenceEdge> itr = hrnPrimary.iteratorToReferencees();
+ while( itr.hasNext() ) {
+ ReferenceEdge e = itr.next();
+ if( e.fieldEquals( field ) && e.isInitialParam() ) {
+ return false;
+ }
+ }
- // define rewrite rules and other structures to organize
- // data by parameter/argument index
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
- new Hashtable<Integer, ReachabilitySet>();
+ return true;
+ }
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
- new Hashtable<Integer, ReachabilitySet>();
+ // 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)
+ OwnershipGraph 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 ) {}
+
+ System.out.println( " "+mc+" is calling "+fm );
+ }
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
- new Hashtable<Integer, ReachabilitySet>();
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
- new Hashtable<Integer, ReachabilitySet>();
- // helpful structures
- Hashtable<TokenTuple, Integer> paramToken2paramIndex =
- new Hashtable<TokenTuple, Integer>();
+ // define rewrite rules and other structures to organize data by parameter/argument index
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachabilitySet>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachabilitySet>();
+
+ Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2p = new Hashtable<String, ReachabilitySet>(); // select( i, j, f )
+ Hashtable<String, ReachabilitySet> paramIndex2rewriteJ_p2s = new Hashtable<String, ReachabilitySet>(); // select( i, f )
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachabilitySet>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachabilitySet>();
- Hashtable<Integer, TokenTuple> paramIndex2paramToken =
- new Hashtable<Integer, TokenTuple>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p = new Hashtable<Integer, ReachabilitySet>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachabilitySet>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_s = new Hashtable<Integer, ReachabilitySet>();
- Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
- new Hashtable<TokenTuple, Integer>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachabilitySet>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachabilitySet>();
- Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
- new Hashtable<Integer, TokenTuple>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD = new Hashtable<Integer, ReachabilitySet>();
- Hashtable<Integer, LabelNode> paramIndex2ln =
- new Hashtable<Integer, LabelNode>();
- Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
- new Hashtable<Integer, HashSet<HeapRegionNode> >();
+ Hashtable<Integer, LabelNode> paramIndex2ln = new Hashtable<Integer, LabelNode>();
- // add a bogus entry with the identity rule for easy rewrite
- // of new callee nodes and edges, doesn't belong to any parameter
- Integer bogusID = new Integer(-1);
- Integer bogusIndex = new Integer(-1);
- TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
- TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY);
- ReachabilitySet rsIdentity =
- new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
+ paramIndex2rewriteH_p.put( bogusIndex, rsIdentity );
+ paramIndex2rewriteH_s.put( bogusIndex, rsIdentity );
- paramIndex2rewriteH.put(bogusIndex, rsIdentity);
- paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
- paramToken2paramIndex.put(bogusToken, bogusIndex);
- paramIndex2paramToken.put(bogusIndex, bogusToken);
- paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
- paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
+ 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 < fm.numParameters(); ++i ) {
Integer paramIndex = new Integer(i);
- assert ogCallee.paramIndex2id.containsKey(paramIndex);
- Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
-
- assert ogCallee.id2hrn.containsKey(idParam);
- HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
- assert hrnParam != null;
- paramIndex2rewriteH.put(paramIndex,
-
- toShadowTokens(ogCallee, hrnParam.getAlpha() )
- );
+ if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) {
+ // skip this immutable parameter
+ continue;
+ }
+
+ // 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<ReferenceEdge> p2xItr = hrnPrimary.iteratorToReferencees();
+ while( p2xItr.hasNext() ) {
+ ReferenceEdge 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() ) );
+ }
- ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
- assert edgeReflexive_i != null;
- paramIndex2rewriteJ.put(paramIndex,
- toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
- );
+ } else {
+ assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() );
+ paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ),
+ toShadowTokens( ogCallee, p2xEdge.getBeta() ) );
+ }
+ }
- TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
+ // setup K (primary)
+ TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
assert tdParamQ != null;
- LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
+ LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ );
assert lnParamQ != null;
- ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
+ ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null );
assert edgeSpecialQ_i != null;
- paramIndex2rewriteK.put(paramIndex,
- toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
- );
-
- TokenTuple p_i = new TokenTuple(hrnParam.getID(),
- true,
- TokenTuple.ARITY_ONE).makeCanonical();
- paramToken2paramIndex.put(p_i, paramIndex);
- paramIndex2paramToken.put(paramIndex, p_i);
-
- TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
- true,
- TokenTuple.ARITY_MANY).makeCanonical();
- paramTokenStar2paramIndex.put(p_i_star, paramIndex);
- paramIndex2paramTokenStar.put(paramIndex, p_i_star);
+ ReachabilitySet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() );
- // 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;
- if( isStatic ) {
- argTemp_i = fc.getArg(paramIndex);
+ TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex );
+ TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex );
+
+ ReachabilitySet K_p = new ReachabilitySet().makeCanonical();
+ ReachabilitySet K_p2 = new ReachabilitySet().makeCanonical();
+ if( s_i == null ) {
+ K_p = qBeta;
} else {
- if( paramIndex == 0 ) {
- argTemp_i = fc.getThis();
- } else {
- argTemp_i = fc.getArg(paramIndex - 1);
+ // sort qBeta into K_p1 and K_p2
+ Iterator<TokenTupleSet> ttsItr = qBeta.iterator();
+ while( ttsItr.hasNext() ) {
+ TokenTupleSet 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 );
+
+
+ // if there is a secondary node, compute the rest of the rewrite rules
+ if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) {
+
+ // 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() ) );
+
+
+ // setup J (secondary->X)
+ Iterator<ReferenceEdge> s2xItr = hrnSecondary.iteratorToReferencees();
+ while( s2xItr.hasNext() ) {
+ ReferenceEdge 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() ) );
+ }
+ }
- // in non-static methods there is a "this" pointer
- // that should be taken into account
- if( isStatic ) {
- assert fc.numArgs() == fm.numParameters();
- } else {
- assert fc.numArgs() + 1 == fm.numParameters();
+ // setup K (secondary)
+ TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex );
+ assert tdParamR != null;
+ LabelNode lnParamR = ogCallee.td2ln.get( tdParamR );
+ assert lnParamR != null;
+ ReferenceEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null );
+ assert edgeSpecialR_i != null;
+ paramIndex2rewriteK_s.put( paramIndex,
+ toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) );
}
+
+
+ // 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 );
- LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
- paramIndex2ln.put(paramIndex, argLabel_i);
+ // remember which caller arg label maps to param index
+ LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
+ paramIndex2ln.put( paramIndex, argLabel_i );
- ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
+ // do a callee-effect strong update pre-pass here
+ if( argTemp_i.getType().isClass() ) {
+
+ Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ if( (hrn.getNumReferencers() == 1) || // case 1
+ (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
+ ) {
+ if( !DISABLE_STRONG_UPDATES ) {
+ effectCalleeStrongUpdates( paramIndex, ogCallee, hrn );
+ }
+ }
+ }
+ }
+
+ // then calculate the d and D rewrite rules
+ ReachabilitySet d_i_p = new ReachabilitySet().makeCanonical();
+ ReachabilitySet d_i_s = new ReachabilitySet().makeCanonical();
Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
while( edgeItr.hasNext() ) {
ReferenceEdge edge = edgeItr.next();
- D_i = D_i.union(edge.getBeta() );
+
+ d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) );
+ d_i_s = d_i_s.union( edge.getBeta() );
}
- D_i = D_i.exhaustiveArityCombinations();
- paramIndex2rewriteD.put(paramIndex, D_i);
+ paramIndex2rewrite_d_p.put( paramIndex, d_i_p );
+ paramIndex2rewrite_d_s.put( paramIndex, d_i_s );
+
+ // TODO: we should only do this when we need it, and then
+ // memoize it for the rest of the mapping procedure
+ ReachabilitySet D_i = d_i_s.exhaustiveArityCombinations();
+ paramIndex2rewriteD.put( paramIndex, D_i );
}
+ // with respect to each argument, map parameter effects into caller
HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
- HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
- HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
+ Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
+ new Hashtable<Integer, Set<HeapRegionNode> >();
+
+ Hashtable<Integer, Set<HeapRegionNode> > pi2r =
+ new Hashtable<Integer, Set<HeapRegionNode> >();
+
+ Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
while( lnArgItr.hasNext() ) {
- Map.Entry me = (Map.Entry)lnArgItr.next();
- Integer index = (Integer) me.getKey();
+ Map.Entry me = (Map.Entry) lnArgItr.next();
+ Integer index = (Integer) me.getKey();
LabelNode lnArg_i = (LabelNode) me.getValue();
+
+ Set<HeapRegionNode> dr = new HashSet<HeapRegionNode>();
+ Set<HeapRegionNode> r = new HashSet<HeapRegionNode>();
+ Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
- // rewrite alpha for the nodes reachable from argument label i
- HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
- HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
-
- // to find all reachable nodes, start with label referencees
+ // find all reachable nodes starting with label referencees
Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
while( edgeArgItr.hasNext() ) {
ReferenceEdge edge = edgeArgItr.next();
- todoNodes.add(edge.getDst() );
- }
+ HeapRegionNode hrn = edge.getDst();
- // then follow links until all reachable nodes have been found
- while( !todoNodes.isEmpty() ) {
- HeapRegionNode hrn = todoNodes.iterator().next();
- todoNodes.remove(hrn);
- reachableNodes.add(hrn);
+ dr.add( hrn );
- Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- ReferenceEdge edge = edgeItr.next();
+ if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
+ defParamObj.add( hrn );
+ }
- if( !reachableNodes.contains(edge.getDst() ) ) {
- todoNodes.add(edge.getDst() );
+ Iterator<ReferenceEdge> edgeHrnItr = hrn.iteratorToReferencees();
+ while( edgeHrnItr.hasNext() ) {
+ ReferenceEdge 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<ReferenceEdge> edgeItr = hrnr.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edger = edgeItr.next();
+ if( !r.contains( edger.getDst() ) ) {
+ todo.add( edger.getDst() );
+ }
}
}
+
+ if( hrn.isSingleObject() ) {
+ r.remove( hrn );
+ }
+ }
+
+ pi2dr.put( index, dr );
+ pi2r .put( index, r );
+ }
+
+ assert defParamObj.size() <= fm.numParameters();
+
+ // if we're in parameter decomposition mode, report some results here
+ if( pd != null ) {
+ Iterator mapItr;
+
+ // 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 );
+ }
}
- // save for later
- paramIndex2reachableCallerNodes.put(index, reachableNodes);
+ // 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<TokenTuple, ReachabilitySet> tokens2states = new Hashtable<TokenTuple, ReachabilitySet>();
- // now iterate over reachable nodes to update their alpha, and
- // classify edges found as "argument reachable" or "upstream"
- Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
+ 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();
+ LabelNode lnArg_i = (LabelNode) me.getValue();
+
+ TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index );
+ TokenTuple 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();
- rewriteCallerNodeAlpha(fm.numParameters(),
- index,
- hrn,
- paramIndex2rewriteH,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar);
+ tokens2states.clear();
+ tokens2states.put( p_i, hrn.getAlpha() );
- nodesWithNewAlpha.add(hrn);
+ rewriteCallerReachability( index,
+ hrn,
+ null,
+ paramIndex2rewriteH_p.get( index ),
+ tokens2states,
+ paramIndex2rewrite_d_p,
+ paramIndex2rewrite_d_s,
+ paramIndex2rewriteD,
+ ogCallee,
+ false,
+ null );
- // look at all incoming edges to the reachable nodes
- // and sort them as edges reachable from the argument
- // label node, or upstream edges
+ nodesWithNewAlpha.add( hrn );
+
+ // sort edges
Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
while( edgeItr.hasNext() ) {
ReferenceEdge edge = edgeItr.next();
+ OwnershipNode on = edge.getSrc();
+
+ boolean edge_classified = false;
- OwnershipNode on = edge.getSrc();
- if( on instanceof LabelNode ) {
+ 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();
- LabelNode ln0 = (LabelNode) on;
- if( ln0.equals(lnArg_i) ) {
- edgesReachable.add(edge);
- } else {
- edgesUpstream.add(edge);
+ if( dr_i.contains( hrn0 ) ) {
+ addEdgeIndexPair( edges_p2p, pi, edge, index );
+ edge_classified = true;
+ }
}
- } else {
+ 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_s2p, pi, edge, index );
+ edge_classified = true;
+ }
+ }
+ }
+
+ // all of these edges are upstream of directly reachable objects
+ if( !edge_classified ) {
+ addEdgeIndexPair( edges_up_dr, index, edge, index );
+ }
+ }
+ }
+
+
+ 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 ReachabilitySet().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<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+ OwnershipNode 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;
- if( reachableNodes.contains(hrn0) ) {
- edgesReachable.add(edge);
- } else {
- edgesUpstream.add(edge);
+
+ 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;
+ }
+ }
+ }
+
+ // these edges are all upstream of some reachable node
+ if( !edge_classified ) {
+ addEdgeIndexPair( edges_up_r, index, edge, index );
}
}
}
+ }
+
+
+ // 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();
+ LabelNode lnArg_i = (LabelNode) me.getValue();
// update reachable edges
- Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
- while( edgeReachableItr.hasNext() ) {
- ReferenceEdge edgeReachable = edgeReachableItr.next();
+ Iterator edgeItr = edges_p2p.get( index ).iterator();
+ while( edgeItr.hasNext() ) {
+ Vector mo = (Vector) edgeItr.next();
+ ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
+ Integer indexJ = (Integer) mo.get( 1 );
+
+ if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
+ indexJ,
+ edge.getField() ) ) ) {
+ continue;
+ }
+
+ TokenTuple 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 );
+ }
+
+
+ edgeItr = edges_p2s.get( index ).iterator();
+ while( edgeItr.hasNext() ) {
+ Vector mo = (Vector) edgeItr.next();
+ ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
+ Integer indexJ = (Integer) mo.get( 1 );
+
+ if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
+ edge.getField() ) ) ) {
+ continue;
+ }
+
+ TokenTuple 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 );
+ }
+
+
+ edgeItr = edges_s2p.get( index ).iterator();
+ while( edgeItr.hasNext() ) {
+ Vector mo = (Vector) edgeItr.next();
+ ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
+ Integer indexJ = (Integer) mo.get( 1 );
+
+ if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) {
+ continue;
+ }
+
+ TokenTuple 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 );
+ }
+
+
+ edgeItr = edges_s2s.get( index ).iterator();
+ while( edgeItr.hasNext() ) {
+ Vector mo = (Vector) edgeItr.next();
+ ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
+ Integer indexJ = (Integer) mo.get( 1 );
+
+ if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) {
+ continue;
+ }
+
+ TokenTuple 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 );
+ }
+
- rewriteCallerEdgeBeta(fm.numParameters(),
- index,
- edgeReachable,
- paramIndex2rewriteJ,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar,
- false,
- null);
+ // update directly upstream edges
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
+ new Hashtable<ReferenceEdge, ChangeTupleSet>();
+
+ HashSet<ReferenceEdge> edgesDirectlyUpstream =
+ new HashSet<ReferenceEdge>();
- edgesWithNewBeta.add(edgeReachable);
+ edgeItr = edges_up_dr.get( index ).iterator();
+ while( edgeItr.hasNext() ) {
+ Vector mo = (Vector) edgeItr.next();
+ ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
+ Integer indexJ = (Integer) mo.get( 1 );
+
+ edgesDirectlyUpstream.add( edge );
+
+ TokenTuple 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
+ TokenTuple 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 );
}
+ propagateTokensOverEdges( edgesDirectlyUpstream,
+ edgeUpstreamPlannedChanges,
+ edgesWithNewBeta );
+
// update upstream edges
- Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
- = new Hashtable<ReferenceEdge, ChangeTupleSet>();
+ edgeUpstreamPlannedChanges =
+ new Hashtable<ReferenceEdge, ChangeTupleSet>();
+
+ HashSet<ReferenceEdge> edgesUpstream =
+ new HashSet<ReferenceEdge>();
+
+ edgeItr = edges_up_r.get( index ).iterator();
+ while( edgeItr.hasNext() ) {
+ Vector mo = (Vector) edgeItr.next();
+ ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
+ Integer indexJ = (Integer) mo.get( 1 );
+
+ if( !paramIndex2rewriteK_s.containsKey( index ) ) {
+ continue;
+ }
+
+ edgesUpstream.add( edge );
+
+ TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ );
+ assert p_j != null;
- Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
- while( edgeUpstreamItr.hasNext() ) {
- ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
+ TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ );
+ assert s_j != null;
- rewriteCallerEdgeBeta(fm.numParameters(),
- index,
- edgeUpstream,
- paramIndex2rewriteK,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar,
- true,
- edgeUpstreamPlannedChanges);
+ tokens2states.clear();
+ tokens2states.put( p_j, rsWttsEmpty );
+ tokens2states.put( s_j, edge.getBeta() );
- edgesWithNewBeta.add(edgeUpstream);
+ rewriteCallerReachability( index,
+ null,
+ edge,
+ paramIndex2rewriteK_s.get( index ),
+ tokens2states,
+ paramIndex2rewrite_d_p,
+ paramIndex2rewrite_d_s,
+ paramIndex2rewriteD,
+ ogCallee,
+ true,
+ edgeUpstreamPlannedChanges );
+
+ edgesWithNewBeta.add( edge );
}
- propagateTokensOverEdges(edgesUpstream,
- edgeUpstreamPlannedChanges,
- edgesWithNewBeta);
- }
+ propagateTokensOverEdges( edgesUpstream,
+ edgeUpstreamPlannedChanges,
+ edgesWithNewBeta );
+
+ } // end effects per argument/parameter map
// commit changes to alpha and beta
edgeItr.next().applyBetaNew();
}
-
-
+
// 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<TokenTuple, ReachabilitySet> tokens2statesEmpty = new Hashtable<TokenTuple, ReachabilitySet>();
+
Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
while( asItr.hasNext() ) {
AllocationSite allocSite = asItr.next();
- HeapRegionNode hrnSummary = getSummaryNode(allocSite);
+
+ // 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);
+ HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
assert hrnShadowSummary.getNumReferencers() == 0;
assert hrnShadowSummary.getNumReferencees() == 0;
// then bring g_ij onto g'_ij and rewrite
- transferOnto(hrnSummary, hrnShadowSummary);
-
- HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
- hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
+ 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
- rewriteCallerNodeAlpha(fm.numParameters(),
- bogusIndex,
- hrnShadowSummary,
- paramIndex2rewriteH,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar);
+ rewriteCallerReachability( bogusIndex,
+ hrnShadowSummary,
+ null,
+ funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ),
+ tokens2statesEmpty,
+ paramIndex2rewrite_d_p,
+ paramIndex2rewrite_d_s,
+ paramIndex2rewriteD,
+ ogCallee,
+ false,
+ null );
hrnShadowSummary.applyAlphaNew();
assert hrnIthShadow.getNumReferencers() == 0;
assert hrnIthShadow.getNumReferencees() == 0;
- transferOnto(hrnIth, hrnIthShadow);
-
assert ogCallee.id2hrn.containsKey(idIth);
HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
- rewriteCallerNodeAlpha(fm.numParameters(),
- bogusIndex,
- hrnIthShadow,
- paramIndex2rewriteH,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar);
+ 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();
+ Set sCallee = ogCallee.id2hrn.entrySet();
Iterator iCallee = sCallee.iterator();
+
while( iCallee.hasNext() ) {
- Map.Entry meCallee = (Map.Entry)iCallee.next();
- Integer idCallee = (Integer) meCallee.getKey();
+ Map.Entry meCallee = (Map.Entry) iCallee.next();
+ Integer idCallee = (Integer) meCallee.getKey();
HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
while( heapRegionsItrCallee.hasNext() ) {
- ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
+ ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
HeapRegionNode hrnChildCallee = edgeCallee.getDst();
- Integer idChildCallee = hrnChildCallee.getID();
+ Integer idChildCallee = hrnChildCallee.getID();
- // only address this edge if it is not a special reflexive edge
- if( !edgeCallee.isInitialParamReflexive() ) {
+ // 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
// make the edge with src and dst so beta info is
// calculated once, then copy it for each new edge in caller
- ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
- null,
- edgeCallee.getFieldDesc(),
- false,
- toShadowTokens(ogCallee, edgeCallee.getBeta() )
- );
- rewriteCallerEdgeBeta(fm.numParameters(),
- bogusIndex,
- edgeNewInCallerTemplate,
- paramIndex2rewriteJ,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar,
- false,
- null);
+
+ ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( 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();
// 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(),
- paramIndex2reachableCallerNodes);
+ getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
+ (HeapRegionNode) edgeCallee.getSrc(),
+ pi2dr,
+ pi2r );
HashSet<HeapRegionNode> possibleCallerDsts =
- getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
- edgeCallee.getDst(),
- paramIndex2reachableCallerNodes);
-
+ 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) ) {
+ if( !hasMatchingField( src, edgeCallee ) ) {
// prune this source node possibility
continue;
}
while( dstItr.hasNext() ) {
HeapRegionNode dst = (HeapRegionNode) dstItr.next();
- if( !hasMatchingType(edgeCallee, dst) ) {
+ if( !hasMatchingType( edgeCallee, dst ) ) {
// prune
continue;
}
// otherwise the caller src and dst pair can match the edge, so make it
ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
- edgeNewInCaller.setSrc(src);
- edgeNewInCaller.setDst(dst);
+ edgeNewInCaller.setSrc( src );
+ edgeNewInCaller.setDst( dst );
+
+ // 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);
+ }
- ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
+ ReferenceEdge edgeExisting = src.getReferenceTo( dst,
+ edgeNewInCaller.getType(),
+ edgeNewInCaller.getField() );
if( edgeExisting == null ) {
// if this edge doesn't exist in the caller, create it
- addReferenceEdge(src, dst, edgeNewInCaller);
+ addReferenceEdge( src, dst, edgeNewInCaller );
+
} else {
// if it already exists, merge with it
- edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
+ edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
}
}
}
// return value may need to be assigned in caller
- if( fc.getReturnTemp() != null ) {
+ TempDescriptor returnTemp = fc.getReturnTemp();
+ if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
- LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() );
- clearReferenceEdgesFrom(lnLhsCaller, null, true);
+ LabelNode lnLhsCaller = getLabelNodeFromTemp( returnTemp );
+ clearReferenceEdgesFrom( lnLhsCaller, null, null, true );
- LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
+ LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp( tdReturn );
Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
while( edgeCalleeItr.hasNext() ) {
ReferenceEdge edgeCallee = edgeCalleeItr.next();
- ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
- null,
- edgeCallee.getFieldDesc(),
- false,
- toShadowTokens(ogCallee, edgeCallee.getBeta() )
- );
- rewriteCallerEdgeBeta(fm.numParameters(),
- bogusIndex,
- edgeNewInCallerTemplate,
- paramIndex2rewriteJ,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar,
- false,
- null);
+ ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( 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(),
- paramIndex2reachableCallerNodes);
+ getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
+ edgeCallee.getDst(),
+ pi2dr,
+ pi2r );
Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
while( itrHrn.hasNext() ) {
HeapRegionNode hrnCaller = itrHrn.next();
- if( !hasMatchingType(edgeCallee, hrnCaller) ) {
+ if( !hasMatchingType( edgeCallee, hrnCaller ) ) {
// prune
continue;
}
// otherwise caller node can match callee edge, so make it
ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
- edgeNewInCaller.setSrc(lnLhsCaller);
- edgeNewInCaller.setDst(hrnCaller);
+ edgeNewInCaller.setSrc( lnLhsCaller );
+ edgeNewInCaller.setDst( hrnCaller );
- ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
+ ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller,
+ edgeNewInCaller.getType(),
+ edgeNewInCaller.getField() );
if( edgeExisting == null ) {
// if this edge doesn't exist in the caller, create it
- addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
+ addReferenceEdge( lnLhsCaller, hrnCaller, edgeNewInCaller );
} else {
// if it already exists, merge with it
- edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
+ edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
}
}
}
}
+ /*
+ if( debugCallMap &&
+ mc.getDescriptor().getSymbol().equals( debugCaller ) &&
+ fm.getMethod().getSymbol().equals( debugCallee )
+ ) {
+
+ try {
+ writeGraph("debug7JustBeforeMergeToKCapacity",
+ 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 ) {}
+ }
+ */
+
// merge the shadow nodes of allocation sites back down to normal capacity
Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
// first age each allocation site enough times to make room for the shadow nodes
for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- age(as);
+ age( as );
}
// then merge the shadow summary into the normal summary
- HeapRegionNode hrnSummary = getSummaryNode(as);
+ HeapRegionNode hrnSummary = getSummaryNode( as );
assert hrnSummary != null;
- HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
+ HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
assert hrnSummaryShadow != null;
- mergeIntoSummary(hrnSummaryShadow, hrnSummary);
+ mergeIntoSummary( hrnSummaryShadow, hrnSummary );
// then clear off after merge
- clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
- clearReferenceEdgesTo(hrnSummaryShadow, null, true);
- hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
+ clearReferenceEdgesFrom( hrnSummaryShadow, null, null, true );
+ clearReferenceEdgesTo ( hrnSummaryShadow, null, null, true );
+ hrnSummaryShadow.setAlpha( new ReachabilitySet().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);
+ Integer idIth = as.getIthOldest( i );
+ HeapRegionNode hrnIth = id2hrn.get( idIth );
+ Integer idIthShadow = as.getIthOldestShadow( i );
+ HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow );
- transferOnto(hrnIthShadow, hrnIth);
+ transferOnto( hrnIthShadow, hrnIth );
// clear off shadow nodes after transfer
- clearReferenceEdgesFrom(hrnIthShadow, null, true);
- clearReferenceEdgesTo(hrnIthShadow, null, true);
- hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
+ clearReferenceEdgesFrom( hrnIthShadow, null, null, true );
+ clearReferenceEdgesTo ( hrnIthShadow, null, null, true );
+ hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() );
}
// finally, globally change shadow tokens into normal tokens
Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
while( itrAllLabelNodes.hasNext() ) {
- Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
+ Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
LabelNode ln = (LabelNode) me.getValue();
Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
while( itrEdges.hasNext() ) {
- unshadowTokens(as, itrEdges.next() );
+ unshadowTokens( 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();
- unshadowTokens(as, hrnToAge);
+ unshadowTokens( as, hrnToAge );
Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
while( itrEdges.hasNext() ) {
- unshadowTokens(as, itrEdges.next() );
+ unshadowTokens( as, itrEdges.next() );
}
}
}
+
+
+ /*
+ if( debugCallMap &&
+ mc.getDescriptor().getSymbol().equals( debugCaller ) &&
+ fm.getMethod().getSymbol().equals( debugCallee )
+ ) {
+
+ try {
+ writeGraph( "debug8JustBeforeSweep",
+ 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 ) {}
+ }
+ */
+
+
+ // 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 );
+ }
+ }
}
+ static int x = 0;
+
protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
- // if no allocation site, then it's a match-everything region
- AllocationSite asSrc = src.getAllocationSite();
- if( asSrc == null ) {
+ // if no type, then it's a match-everything region
+ TypeDescriptor tdSrc = src.getType();
+ if( tdSrc == null ) {
return true;
}
- TypeDescriptor tdSrc = asSrc.getType();
- assert tdSrc != null;
+ if( tdSrc.isArray() ) {
+ TypeDescriptor td = edge.getType();
+ assert td != null;
+
+ TypeDescriptor tdSrcDeref = tdSrc.dereference();
+ assert tdSrcDeref != null;
+
+ if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
+ return false;
+ }
+
+ return edge.getField().equals( OwnershipAnalysis.arrayElementFieldName );
+ }
// if it's not a class, it doesn't have any fields to match
if( !tdSrc.isClass() ) {
return false;
}
- Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
- while( fieldsSrcItr.hasNext() ) {
- FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
- if( fd == edge.getFieldDesc() ) {
- return true;
+ ClassDescriptor cd = tdSrc.getClassDesc();
+ while( cd != null ) {
+ Iterator fieldItr = cd.getFields();
+
+ while( fieldItr.hasNext() ) {
+ FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
+
+ if( fd.getType().equals( edge.getType() ) &&
+ fd.getSymbol().equals( edge.getField() ) ) {
+ return true;
+ }
}
+
+ cd = cd.getSuperDesc();
}
-
+
// otherwise it is a class with fields
// but we didn't find a match
return false;
protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
-
+
// if the region has no type, matches everything
- AllocationSite asDst = dst.getAllocationSite();
- if( asDst == null ) {
+ TypeDescriptor tdDst = dst.getType();
+ if( tdDst == null ) {
return true;
}
- TypeDescriptor tdDst = asDst.getType();
- assert tdDst != null;
-
- // if the type is not a class don't match because
- // primitives are copied, no memory aliases
+ // 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 ) {
+ if( cdDst == null && !tdDst.isArray() ) {
return false;
}
- // if the field is null, it matches everything
- FieldDescriptor fd = edge.getFieldDesc();
- if( fd == null ) {
+ // if the edge type is null, it matches everything
+ TypeDescriptor tdEdge = edge.getType();
+ if( tdEdge == null ) {
return true;
}
- TypeDescriptor tdFd = fd.getType();
- assert tdFd != null;
- return typeUtil.isSuperorType(tdFd, tdDst);
+ return typeUtil.isSuperorType(tdEdge, tdDst);
}
private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
ReachabilitySet rsIn) {
- ReachabilitySet rsOut = new ReachabilitySet(rsIn);
+ ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
while( allocItr.hasNext() ) {
}
- private void rewriteCallerNodeAlpha(int numParameters,
- Integer paramIndex,
- HeapRegionNode hrn,
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
- Hashtable<Integer, TokenTuple> paramIndex2paramToken,
- Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
-
- ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
- assert rules != null;
-
- TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
- assert tokenToRewrite != null;
-
- ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
- Iterator<TokenTupleSet> ttsItr = rules.iterator();
- while( ttsItr.hasNext() ) {
- TokenTupleSet tts = ttsItr.next();
- r0 = r0.union(tts.rewriteToken(tokenToRewrite,
- hrn.getAlpha(),
- false,
- null) );
- }
-
- ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
- ttsItr = r0.iterator();
- while( ttsItr.hasNext() ) {
- TokenTupleSet tts = ttsItr.next();
- r1 = r1.union(rewriteDpass(numParameters,
- paramIndex,
- tts,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar) );
- }
-
- hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
- }
-
-
- private void rewriteCallerEdgeBeta(int numParameters,
- Integer paramIndex,
- ReferenceEdge edge,
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
- Hashtable<Integer, TokenTuple> paramIndex2paramToken,
- Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
- boolean makeChangeSet,
- Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
-
- ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex);
- assert rules != null;
-
- TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
- assert tokenToRewrite != null;
-
- ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
-
- Iterator<TokenTupleSet> ttsItr = rules.iterator();
- while( ttsItr.hasNext() ) {
- TokenTupleSet tts = ttsItr.next();
-
- Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > forChangeSet =
- new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
-
- ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
- edge.getBeta(),
- true,
- forChangeSet);
-
- Iterator fcsItr = forChangeSet.entrySet().iterator();
- while( fcsItr.hasNext() ) {
- Map.Entry me = (Map.Entry)fcsItr.next();
- TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
- HashSet<TokenTupleSet> ttsAddSet = (HashSet<TokenTupleSet>) me.getValue();
- Iterator<TokenTupleSet> ttsAddItr = ttsAddSet.iterator();
- while( ttsAddItr.hasNext() ) {
- TokenTupleSet ttsAdd = ttsAddItr.next();
-
- ChangeTuple ct = new ChangeTuple(ttsMatch,
- ttsAdd
- ).makeCanonical();
+ private void rewriteCallerReachability(Integer paramIndex,
+ HeapRegionNode hrn,
+ ReferenceEdge edge,
+ ReachabilitySet rules,
+ Hashtable<TokenTuple, ReachabilitySet> tokens2states,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
+ OwnershipGraph ogCallee,
+ boolean makeChangeSet,
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
+
+ assert(hrn == null && edge != null) ||
+ (hrn != null && edge == null);
+
+ assert rules != null;
+ assert tokens2states != null;
+
+ ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
+
+ // for initializing structures in this method
+ TokenTupleSet ttsEmpty = new TokenTupleSet().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<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
+ new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
+ rewritten2source.put( ttsEmpty, new HashSet<TokenTupleSet>() );
+
+
+ Iterator<TokenTupleSet> rulesItr = rules.iterator();
+ while(rulesItr.hasNext()) {
+ TokenTupleSet rule = rulesItr.next();
+
+ ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
+
+ Iterator<TokenTuple> ruleItr = rule.iterator();
+ while(ruleItr.hasNext()) {
+ TokenTuple ttCallee = ruleItr.next();
+
+ // compute the possibilities for rewriting this callee token
+ ReachabilitySet 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;
- cts0 = cts0.union(ct);
+ } else {
+ // otherwise there's no need for a rewrite, just pass this one on
+ TokenTupleSet ttsCaller = new TokenTupleSet( ttCallee ).makeCanonical();
+ ttCalleeRewrites = new ReachabilitySet( ttsCaller ).makeCanonical();
}
- }
- }
+ // branch every version of the working rewritten rule with
+ // the possibilities for rewriting the current callee token
+ ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
+
+ Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
+ while( rewrittenRuleItr.hasNext() ) {
+ TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
- ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
- ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
+ Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
+ while( ttCalleeRewritesItr.hasNext() ) {
+ TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
- Iterator<ChangeTuple> ctItr = cts0.iterator();
- while( ctItr.hasNext() ) {
- ChangeTuple ct = ctItr.next();
+ TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
- ReachabilitySet rTemp = rewriteDpass(numParameters,
- paramIndex,
- ct.getSetToAdd(),
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar
- ).makeCanonical();
- r1 = r1.union(rTemp);
+ 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<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
+ assert sourceSets != null;
- if( makeChangeSet ) {
- assert edgePlannedChanges != null;
+ // make a shallow copy for possible modification
+ sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
- Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
- while( ttsTempItr.hasNext() ) {
- TokenTupleSet tts = ttsTempItr.next();
+ // if we used something from the caller to rewrite it, remember
+ if( callerSourceUsed ) {
+ sourceSets.add( ttsBranch );
+ }
- ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(),
- tts
- ).makeCanonical();
+ // set mapping for the further rewritten rule
+ rewritten2source.put( ttsRewrittenNext, sourceSets );
+ }
- cts1 = cts1.union(ctFinal);
+ rewrittenRuleWithTTCallee =
+ rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
+ }
}
+
+ // now the rewritten rule's possibilities have been extended by
+ // rewriting the current callee token, remember result
+ rewrittenRule = rewrittenRuleWithTTCallee;
}
+
+ // 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 ) {
- edgePlannedChanges.put(edge, cts1);
- }
-
- edge.setBetaNew(edge.getBetaNew().union(r1) );
- }
-
-
- private ReachabilitySet rewriteDpass(int numParameters,
- Integer paramIndex,
- TokenTupleSet ttsIn,
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
- Hashtable<Integer, TokenTuple> paramIndex2paramToken,
- Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
-
- ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
-
- boolean rewritten = false;
-
- for( int j = 0; j < numParameters; ++j ) {
- Integer paramIndexJ = new Integer(j);
- ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ);
- assert D_j != null;
-
- if( paramIndexJ != paramIndex ) {
- TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ);
- assert tokenToRewriteJ != null;
- if( ttsIn.containsTuple(tokenToRewriteJ) ) {
- ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ,
- D_j,
- false,
- null);
- Iterator<TokenTupleSet> ttsItr = r.iterator();
- while( ttsItr.hasNext() ) {
- TokenTupleSet tts = ttsItr.next();
- rsOut = rsOut.union(rewriteDpass(numParameters,
- paramIndex,
- tts,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar) );
- rewritten = true;
- }
+ ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
+
+ // each possibility for the final reachability should have a set of
+ // caller sources mapped to it, use to create the change set
+ Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
+ while( callerReachabilityItr.hasNext() ) {
+ TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
+ HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewrittenFinal );
+ assert sourceSets != null;
+
+ Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
+ while( sourceSetsItr.hasNext() ) {
+ TokenTupleSet ttsSource = sourceSetsItr.next();
+
+ callerChangeSet =
+ callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
}
}
- TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ);
- assert tokenStarToRewriteJ != null;
- if( ttsIn.containsTuple(tokenStarToRewriteJ) ) {
- ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ,
- D_j,
- false,
- null);
- Iterator<TokenTupleSet> ttsItr = r.iterator();
- while( ttsItr.hasNext() ) {
- TokenTupleSet tts = ttsItr.next();
- rsOut = rsOut.union(rewriteDpass(numParameters,
- paramIndex,
- tts,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar) );
- rewritten = true;
- }
- }
+ assert edgePlannedChanges != null;
+ edgePlannedChanges.put( edge, callerChangeSet );
}
- if( !rewritten ) {
- rsOut = rsOut.union(ttsIn);
+ if( hrn == null ) {
+ edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) );
+ } else {
+ hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) );
}
-
- return rsOut;
}
- private HashSet<HeapRegionNode>
- getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
- HeapRegionNode hrnCallee,
- Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
- ) {
+ private HashSet<HeapRegionNode>
+ getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
+ HeapRegionNode hrnCallee,
+ Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
+ Hashtable<Integer, Set<HeapRegionNode> > pi2r
+ ) {
+
HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
- Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
+ Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() );
+ Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() );
- if( paramIndexCallee == null ) {
- // this is a node allocated in the callee then and it has
+ 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
AllocationSite as = hrnCallee.getAllocationSite();
assert as != null;
- int age = as.getAgeCategory(hrnCallee.getID() );
+ int age = as.getAgeCategory( hrnCallee.getID() );
assert age != AllocationSite.AGE_notInThisSite;
Integer idCaller;
if( age == AllocationSite.AGE_summary ) {
idCaller = as.getSummaryShadow();
+
} else if( age == AllocationSite.AGE_oldest ) {
idCaller = as.getOldestShadow();
+
} else {
assert age == AllocationSite.AGE_in_I;
- Integer I = as.getAge(hrnCallee.getID() );
+ Integer I = as.getAge( hrnCallee.getID() );
assert I != null;
- idCaller = as.getIthOldestShadow(I);
+ idCaller = as.getIthOldestShadow( I );
}
- assert id2hrn.containsKey(idCaller);
- HeapRegionNode hrnCaller = id2hrn.get(idCaller);
- possibleCallerHRNs.add(hrnCaller);
+ assert id2hrn.containsKey( idCaller );
+ possibleCallerHRNs.add( id2hrn.get( idCaller ) );
- } else {
+ 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 a whole mess of heap regions
- assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
- possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
+ // 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 ) );
+ }
+ }
+
+ // 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 ) );
+ }
}
+ // TODO: is this true?
+ // one of the two cases above should have put something in here
+ //assert !possibleCallerHRNs.isEmpty();
+
return possibleCallerHRNs;
}
+ ////////////////////////////////////////////////////
+ //
+ // This global sweep is an optional step to prune
+ // reachability sets that are not internally
+ // consistent with the global graph. It should be
+ // invoked after strong updates or method calls.
+ //
+ ////////////////////////////////////////////////////
+ public void globalSweep() {
+
+ // boldB is part of the phase 1 sweep
+ Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> > boldB =
+ new Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> >();
+
+ // visit every heap region to initialize alphaNew and calculate boldB
+ Set hrns = id2hrn.entrySet();
+ Iterator itrHrns = hrns.iterator();
+ while( itrHrns.hasNext() ) {
+ Map.Entry me = (Map.Entry)itrHrns.next();
+ Integer token = (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() );
+
+ Iterator<ReferenceEdge> itrRers = hrn.iteratorToReferencers();
+ while( itrRers.hasNext() ) {
+ ReferenceEdge edge = itrRers.next();
+ assert rsEmpty.equals( edge.getBetaNew() );
+ }
+
+ // calculate boldB for this flagged node
+ if( hrn.isFlagged() || hrn.isParameter() ) {
+
+ Hashtable<ReferenceEdge, ReachabilitySet> boldB_f =
+ new Hashtable<ReferenceEdge, ReachabilitySet>();
+
+ Set<ReferenceEdge> workSetEdges = new HashSet<ReferenceEdge>();
+
+ // initial boldB_f constraints
+ Iterator<ReferenceEdge> itrRees = hrn.iteratorToReferencees();
+ while( itrRees.hasNext() ) {
+ ReferenceEdge edge = itrRees.next();
+
+ assert !boldB.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() ) {
+ ReferenceEdge edge = workSetEdges.iterator().next();
+ workSetEdges.remove( edge );
+
+ Iterator<ReferenceEdge> itrPrime = edge.getDst().iteratorToReferencees();
+ while( itrPrime.hasNext() ) {
+ ReferenceEdge edgePrime = itrPrime.next();
+
+ ReachabilitySet prevResult = boldB_f.get( edgePrime );
+ ReachabilitySet 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 );
+ }
+ }
+ }
+
+ boldB.put( token, boldB_f );
+ }
+ }
+
+
+ // use boldB to prune tokens from alpha states that are impossible
+ // and propagate the differences backwards across edges
+ HashSet<ReferenceEdge> edgesForPropagation = new HashSet<ReferenceEdge>();
+
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
+ new Hashtable<ReferenceEdge, ChangeTupleSet>();
+
+ hrns = id2hrn.entrySet();
+ itrHrns = hrns.iterator();
+ while( itrHrns.hasNext() ) {
+ Map.Entry me = (Map.Entry)itrHrns.next();
+ Integer token = (Integer) me.getKey();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ // never remove the identity token from a flagged region
+ // because it is trivially satisfied
+ TokenTuple ttException = new TokenTuple( token,
+ !hrn.isSingleObject(),
+ TokenTuple.ARITY_ONE ).makeCanonical();
+
+ ChangeTupleSet cts = new ChangeTupleSet().makeCanonical();
+
+ // mark tokens for removal
+ Iterator<TokenTupleSet> stateItr = hrn.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ TokenTupleSet ttsOld = stateItr.next();
+
+ TokenTupleSet markedTokens = new TokenTupleSet().makeCanonical();
+
+ Iterator<TokenTuple> ttItr = ttsOld.iterator();
+ while( ttItr.hasNext() ) {
+ TokenTuple ttOld = ttItr.next();
+
+ // never remove the identity token from a flagged region
+ // because it is trivially satisfied
+ if( hrn.isFlagged() || hrn.isParameter() ) {
+ if( ttOld == ttException ) {
+ continue;
+ }
+ }
+
+ // does boldB_ttOld allow this token?
+ boolean foundState = false;
+ Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
+ while( incidentEdgeItr.hasNext() ) {
+ ReferenceEdge incidentEdge = incidentEdgeItr.next();
+
+ // if it isn't allowed, mark for removal
+ Integer idOld = ttOld.getToken();
+ assert id2hrn.containsKey( idOld );
+ Hashtable<ReferenceEdge, ReachabilitySet> B = boldB.get( idOld );
+ ReachabilitySet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
+ if( boldB_ttOld_incident != null &&
+ boldB_ttOld_incident.contains( ttsOld ) ) {
+ foundState = true;
+ }
+ }
+
+ if( !foundState ) {
+ markedTokens = markedTokens.add( ttOld );
+ }
+ }
+
+ // if there is nothing marked, just move on
+ if( markedTokens.isEmpty() ) {
+ hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
+ continue;
+ }
+
+ // remove all marked tokens and establish a change set that should
+ // propagate backwards over edges from this node
+ TokenTupleSet ttsPruned = new TokenTupleSet().makeCanonical();
+ ttItr = ttsOld.iterator();
+ while( ttItr.hasNext() ) {
+ TokenTuple ttOld = ttItr.next();
+
+ if( !markedTokens.containsTuple( ttOld ) ) {
+ ttsPruned = ttsPruned.union( ttOld );
+ }
+ }
+ assert !ttsOld.equals( ttsPruned );
+
+ hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
+ ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
+ cts = cts.union( ct );
+ }
+
+ // throw change tuple set on all incident edges
+ if( !cts.isEmpty() ) {
+ Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
+ while( incidentEdgeItr.hasNext() ) {
+ ReferenceEdge incidentEdge = incidentEdgeItr.next();
+
+ edgesForPropagation.add( incidentEdge );
+
+ if( edgePlannedChanges.get( incidentEdge ) == null ) {
+ edgePlannedChanges.put( incidentEdge, cts );
+ } else {
+ edgePlannedChanges.put(
+ incidentEdge,
+ edgePlannedChanges.get( incidentEdge ).union( cts )
+ );
+ }
+ }
+ }
+ }
+
+ HashSet<ReferenceEdge> edgesUpdated = new HashSet<ReferenceEdge>();
+
+ propagateTokensOverEdges( edgesForPropagation,
+ edgePlannedChanges,
+ edgesUpdated );
+
+ // at the end of the 1st phase reference edges have
+ // beta, betaNew that correspond to beta and betaR
+ //
+ // commit beta<-betaNew, so beta=betaR and betaNew
+ // will represent the beta' calculation in 2nd phase
+ //
+ // commit alpha<-alphaNew because it won't change
+ HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
+
+ Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
+ while( nodeItr.hasNext() ) {
+ HeapRegionNode hrn = nodeItr.next();
+ hrn.applyAlphaNew();
+ Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
+ while( itrRes.hasNext() ) {
+ res.add( itrRes.next() );
+ }
+ }
+
+
+ // 2nd phase
+ Iterator<ReferenceEdge> edgeItr = res.iterator();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ // commit results of last phase
+ if( edgesUpdated.contains( edge ) ) {
+ edge.applyBetaNew();
+ }
+
+ // compute intial condition of 2nd phase
+ edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
+ }
+
+ // every edge in the graph is the initial workset
+ Set<ReferenceEdge> edgeWorkSet = (Set) res.clone();
+ while( !edgeWorkSet.isEmpty() ) {
+ ReferenceEdge edgePrime = edgeWorkSet.iterator().next();
+ edgeWorkSet.remove( edgePrime );
+
+ OwnershipNode on = edgePrime.getSrc();
+ if( !(on instanceof HeapRegionNode) ) {
+ continue;
+ }
+ HeapRegionNode hrn = (HeapRegionNode) on;
+
+ Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
+ while( itrEdge.hasNext() ) {
+ ReferenceEdge edge = itrEdge.next();
+
+ ReachabilitySet prevResult = edge.getBetaNew();
+ assert prevResult != null;
+
+ ReachabilitySet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
+
+ if( prevResult.union( intersection ).size() > prevResult.size() ) {
+ edge.setBetaNew( prevResult.union( intersection ) );
+ edgeWorkSet.add( edge );
+ }
+ }
+ }
+
+ // commit beta' (beta<-betaNew)
+ edgeItr = res.iterator();
+ while( edgeItr.hasNext() ) {
+ edgeItr.next().applyBetaNew();
+ }
+ }
+
+
+
////////////////////////////////////////////////////
// in merge() and equals() methods the suffix A
// represents the passed in graph and the suffix
mergeOwnershipNodes(og);
mergeReferenceEdges(og);
- mergeId2paramIndex(og);
+ mergeParamIndexMappings(og);
mergeAllocationSites(og);
}
// don't use the ReferenceEdge.equals() here because
// we're talking about existence between graphs
- if( idChildB.equals(idChildA) &&
- edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
+ if( idChildB.equals( idChildA ) &&
+ edgeB.typeAndFieldEquals( edgeA ) ) {
+
edgeToMerge = edgeB;
}
}
edgeToMerge.setBeta(
edgeToMerge.getBeta().union(edgeA.getBeta() )
);
- if( !edgeA.isInitialParamReflexive() ) {
- edgeToMerge.setIsInitialParamReflexive(false);
+ //TODO eom
+ edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
+ if( !edgeA.isInitialParam() ) {
+ edgeToMerge.setIsInitialParam(false);
}
}
}
LabelNode lnB = td2ln.get(tdA);
ReferenceEdge edgeToMerge = null;
- // labels never have edges with a field
- //assert edgeA.getFieldDesc() == null;
-
Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
while( heapRegionsItrB.hasNext() &&
edgeToMerge == null ) {
- ReferenceEdge edgeB = heapRegionsItrB.next();
+ ReferenceEdge edgeB = heapRegionsItrB.next();
HeapRegionNode hrnChildB = edgeB.getDst();
- Integer idChildB = hrnChildB.getID();
-
- // labels never have edges with a field
- //assert edgeB.getFieldDesc() == null;
+ Integer idChildB = hrnChildB.getID();
// don't use the ReferenceEdge.equals() here because
// we're talking about existence between graphs
- if( idChildB.equals(idChildA) &&
- edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
+ if( idChildB.equals( idChildA ) &&
+ edgeB.typeAndFieldEquals( edgeA ) ) {
+
edgeToMerge = edgeB;
}
}
edgeToMerge.setBeta(
edgeToMerge.getBeta().union(edgeA.getBeta() )
);
- if( !edgeA.isInitialParamReflexive() ) {
- edgeToMerge.setIsInitialParamReflexive(false);
+ edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
+ if( !edgeA.isInitialParam() ) {
+ edgeToMerge.setIsInitialParam(false);
}
}
}
// 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 mergeId2paramIndex(OwnershipGraph og) {
- if( id2paramIndex.size() == 0 ) {
- id2paramIndex = og.id2paramIndex;
- paramIndex2id = og.paramIndex2id;
- paramIndex2tdQ = og.paramIndex2tdQ;
+ protected void mergeParamIndexMappings(OwnershipGraph 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.id2paramIndex.size() == 0 ) {
+ 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 id2paramIndex.size() == og.id2paramIndex.size();
+ assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size();
+ assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
}
protected void mergeAllocationSites(OwnershipGraph og) {
return false;
}
- if( !areId2paramIndexEqual(og) ) {
+ if( !areParamIndexMappingsEqual(og) ) {
return false;
}
HeapRegionNode hrnChildB = edgeB.getDst();
Integer idChildB = hrnChildB.getID();
- if( idChildA.equals(idChildB) &&
- edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
+ 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() ) ) {
-
edgeFound = true;
- //} else {
- //return false;
}
}
}
}
- protected boolean areId2paramIndexEqual(OwnershipGraph og) {
- return id2paramIndex.size() == og.id2paramIndex.size();
- }
-
+ protected boolean areParamIndexMappingsEqual(OwnershipGraph og) {
- public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
+ if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
+ return false;
+ }
- // get parameter's heap region
- assert paramIndex2id.containsKey(paramIndex1);
- Integer idParam1 = paramIndex2id.get(paramIndex1);
+ if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
+ return false;
+ }
- assert id2hrn.containsKey(idParam1);
- HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
- assert hrnParam1 != null;
+ return true;
+ }
- // get tokens for this parameter
- TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
- true,
- TokenTuple.ARITY_ONE).makeCanonical();
- TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
- true,
- TokenTuple.ARITY_MANY).makeCanonical();
+ public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
+ assert hrn1 != null;
+ assert hrn2 != null;
+ // then get the various tokens for these heap regions
+ TokenTuple h1 = new TokenTuple(hrn1.getID(),
+ !hrn1.isSingleObject(),
+ TokenTuple.ARITY_ONE).makeCanonical();
- // get tokens for the other parameter
- assert paramIndex2id.containsKey(paramIndex2);
- Integer idParam2 = paramIndex2id.get(paramIndex2);
+ TokenTuple h1plus = new TokenTuple(hrn1.getID(),
+ !hrn1.isSingleObject(),
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
- assert id2hrn.containsKey(idParam2);
- HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
- assert hrnParam2 != null;
+ TokenTuple h1star = new TokenTuple(hrn1.getID(),
+ !hrn1.isSingleObject(),
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
- TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
- true,
+ TokenTuple h2 = new TokenTuple(hrn2.getID(),
+ !hrn2.isSingleObject(),
TokenTuple.ARITY_ONE).makeCanonical();
- TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
- true,
- TokenTuple.ARITY_MANY).makeCanonical();
+ TokenTuple h2plus = new TokenTuple(hrn2.getID(),
+ !hrn2.isSingleObject(),
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+ TokenTuple h2star = new TokenTuple(hrn2.getID(),
+ !hrn2.isSingleObject(),
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
- // get special label p_q for first parameter
- TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
- assert tdParamQ1 != null;
- LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
- assert lnParamQ1 != null;
+ // then get the merged beta of all out-going edges from these heap regions
+ ReachabilitySet beta1 = new ReachabilitySet().makeCanonical();
+ Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
+ while( itrEdge.hasNext() ) {
+ ReferenceEdge edge = itrEdge.next();
+ beta1 = beta1.union( edge.getBeta() );
+ }
- // then get the edge from label q to parameter's hrn
- ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
- assert edgeSpecialQ1 != null;
+ ReachabilitySet beta2 = new ReachabilitySet().makeCanonical();
+ itrEdge = hrn2.iteratorToReferencees();
+ while( itrEdge.hasNext() ) {
+ ReferenceEdge edge = itrEdge.next();
+ beta2 = beta2.union( edge.getBeta() );
+ }
- // if the beta of this edge has tokens from both parameters in one
- // token tuple set, then there is a potential alias between them
- ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
- assert beta1 != null;
+ boolean aliasDetected = false;
- if( beta1.containsTupleSetWithBoth(p1, p2) ) {
- return true;
+ // only do this one if they are different tokens
+ if( h1 != h2 &&
+ beta1.containsTupleSetWithBoth(h1, h2) ) {
+ aliasDetected = true;
}
- if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
- return true;
+ if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
+ aliasDetected = true;
}
- if( beta1.containsTupleSetWithBoth(p1, pStar2) ) {
- return true;
+ if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
+ aliasDetected = true;
}
- if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
- return 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;
}
- return false;
+ 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;
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if( aliasDetected ) {
+ common = findCommonReachableNodes( hrn1, hrn2 );
+ if( !(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP) ) {
+ assert !common.isEmpty();
+ }
+ }
+
+ return common;
}
- public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
+ public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
- // get parameter's heap region
- assert paramIndex2id.containsKey(paramIndex);
- Integer idParam = paramIndex2id.get(paramIndex);
+ // get parameter 1's heap regions
+ assert paramIndex2idPrimary.containsKey(paramIndex1);
+ Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1);
- assert id2hrn.containsKey(idParam);
- HeapRegionNode hrnParam = id2hrn.get(idParam);
- assert hrnParam != null;
+ assert id2hrn.containsKey(idParamPri1);
+ HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1);
+ assert hrnParamPri1 != null;
- // get tokens for this parameter
- TokenTuple p = new TokenTuple(hrnParam.getID(),
- true,
- TokenTuple.ARITY_ONE).makeCanonical();
+ HeapRegionNode hrnParamSec1 = null;
+ if( paramIndex2idSecondary.containsKey(paramIndex1) ) {
+ Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1);
- TokenTuple pStar = new TokenTuple(hrnParam.getID(),
- true,
- TokenTuple.ARITY_MANY).makeCanonical();
+ assert id2hrn.containsKey(idParamSec1);
+ hrnParamSec1 = id2hrn.get(idParamSec1);
+ assert hrnParamSec1 != null;
+ }
- // get special label p_q
- TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
- assert tdParamQ != null;
- LabelNode lnParamQ = td2ln.get(tdParamQ);
- assert lnParamQ != null;
- // then get the edge from label q to parameter's hrn
- ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
- assert edgeSpecialQ != null;
+ // get the other parameter
+ assert paramIndex2idPrimary.containsKey(paramIndex2);
+ Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2);
- // look through this beta set for potential aliases
- ReachabilitySet beta = edgeSpecialQ.getBeta();
- assert beta != null;
+ assert id2hrn.containsKey(idParamPri2);
+ HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2);
+ assert hrnParamPri2 != null;
+ HeapRegionNode hrnParamSec2 = null;
+ if( paramIndex2idSecondary.containsKey(paramIndex2) ) {
+ Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2);
- // get tokens for summary node
- TokenTuple gs = new TokenTuple(as.getSummary(),
- true,
- TokenTuple.ARITY_ONE).makeCanonical();
+ assert id2hrn.containsKey(idParamSec2);
+ hrnParamSec2 = id2hrn.get(idParamSec2);
+ assert hrnParamSec2 != null;
+ }
- TokenTuple gsStar = new TokenTuple(as.getSummary(),
- true,
- TokenTuple.ARITY_MANY).makeCanonical();
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ common.addAll( hasPotentialAlias( hrnParamPri1, hrnParamPri2 ) );
- if( beta.containsTupleSetWithBoth(p, gs) ) {
- return true;
+ if( hrnParamSec1 != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamPri2 ) );
}
- if( beta.containsTupleSetWithBoth(pStar, gs) ) {
- return true;
+
+ if( hrnParamSec2 != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec2, hrnParamPri1 ) );
}
- if( beta.containsTupleSetWithBoth(p, gsStar) ) {
- return true;
+
+ if( hrnParamSec1 != null && hrnParamSec2 != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamSec2 ) );
}
- if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
- return true;
+
+ return common;
+ }
+
+
+ public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocationSite as) {
+
+ // get parameter's heap regions
+ assert paramIndex2idPrimary.containsKey(paramIndex);
+ Integer idParamPri = paramIndex2idPrimary.get(paramIndex);
+
+ assert id2hrn.containsKey(idParamPri);
+ HeapRegionNode hrnParamPri = id2hrn.get(idParamPri);
+ assert hrnParamPri != null;
+
+ HeapRegionNode hrnParamSec = null;
+ if( paramIndex2idSecondary.containsKey(paramIndex) ) {
+ Integer idParamSec = paramIndex2idSecondary.get(paramIndex);
+
+ assert id2hrn.containsKey(idParamSec);
+ hrnParamSec = id2hrn.get(idParamSec);
+ assert hrnParamSec != null;
+ }
+
+ // get summary node
+ assert id2hrn.containsKey( as.getSummary() );
+ HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
+ assert hrnSummary != null;
+
+ Set<HeapRegionNode> common = hasPotentialAlias( hrnParamPri, hrnSummary );
+
+ if( hrnParamSec != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec, hrnSummary ) );
}
// check for other nodes
for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- // the other nodes of an allocation site are single, no stars
- TokenTuple gi = new TokenTuple(as.getIthOldest(i),
- false,
- TokenTuple.ARITY_ONE).makeCanonical();
+ assert id2hrn.containsKey( as.getIthOldest( i ) );
+ HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) );
+ assert hrnIthOldest != null;
- if( beta.containsTupleSetWithBoth(p, gi) ) {
- return true;
- }
- if( beta.containsTupleSetWithBoth(pStar, gi) ) {
- return true;
+ common = hasPotentialAlias( hrnParamPri, hrnIthOldest );
+
+ if( hrnParamSec != null ) {
+ common.addAll( hasPotentialAlias( hrnParamSec, hrnIthOldest ) );
}
}
-
- return false;
+
+ return common;
}
- public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
-
- // get tokens for summary nodes
- TokenTuple gs1 = new TokenTuple(as1.getSummary(),
- true,
- TokenTuple.ARITY_ONE).makeCanonical();
-
- TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
- true,
- TokenTuple.ARITY_MANY).makeCanonical();
+ public Set<HeapRegionNode> hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
- // get summary node's alpha
+ // get summary node 1's alpha
Integer idSum1 = as1.getSummary();
assert id2hrn.containsKey(idSum1);
HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
assert hrnSum1 != null;
- ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
- assert alphaSum1 != null;
-
- // and for the other one
- TokenTuple gs2 = new TokenTuple(as2.getSummary(),
- true,
- TokenTuple.ARITY_ONE).makeCanonical();
-
- TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
- true,
- TokenTuple.ARITY_MANY).makeCanonical();
-
- // get summary node's alpha
+ // get summary node 2's alpha
Integer idSum2 = as2.getSummary();
assert id2hrn.containsKey(idSum2);
HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
assert hrnSum2 != null;
- ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
- assert alphaSum2 != null;
-
- // does either one report reachability from the other tokens?
- if( alphaSum1.containsTuple(gsStar2) ) {
- return true;
- }
- if( alphaSum2.containsTuple(gsStar1) ) {
- return true;
- }
-
- // only check non-star token if they are different sites
- if( as1 != as2 ) {
- if( alphaSum1.containsTuple(gs2) ) {
- return true;
- }
- if( alphaSum2.containsTuple(gs1) ) {
- return true;
- }
- }
+ Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
// check sum2 against alloc1 nodes
for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
assert id2hrn.containsKey(idI1);
HeapRegionNode hrnI1 = id2hrn.get(idI1);
assert hrnI1 != null;
- ReachabilitySet alphaI1 = hrnI1.getAlpha();
- assert alphaI1 != null;
- // the other nodes of an allocation site are single, no stars
- TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
- false,
- TokenTuple.ARITY_ONE).makeCanonical();
-
- if( alphaSum2.containsTuple(gi1) ) {
- return true;
- }
- if( alphaI1.containsTuple(gs2) ) {
- return true;
- }
- if( alphaI1.containsTuple(gsStar2) ) {
- return true;
- }
+ common.addAll( hasPotentialAlias( hrnI1, hrnSum2 ) );
}
// check sum1 against alloc2 nodes
assert id2hrn.containsKey(idI2);
HeapRegionNode hrnI2 = id2hrn.get(idI2);
assert hrnI2 != null;
- ReachabilitySet alphaI2 = hrnI2.getAlpha();
- assert alphaI2 != null;
- TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
- false,
- TokenTuple.ARITY_ONE).makeCanonical();
-
- if( alphaSum1.containsTuple(gi2) ) {
- return true;
- }
- if( alphaI2.containsTuple(gs1) ) {
- return true;
- }
- if( alphaI2.containsTuple(gsStar1) ) {
- return true;
- }
+ 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
+ // 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 == idI2 ) {
+ if( idI1.equals( idI2 ) ) {
continue;
}
HeapRegionNode hrnI1 = id2hrn.get(idI1);
- ReachabilitySet alphaI1 = hrnI1.getAlpha();
- TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
- false,
- TokenTuple.ARITY_ONE).makeCanonical();
- if( alphaI2.containsTuple(gi1) ) {
- return true;
+
+ common.addAll( hasPotentialAlias( hrnI1, hrnI2 ) );
+ }
+ }
+
+ 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 );
+
+ // follow links until all reachable nodes have been found
+ while( !todoNodes1.isEmpty() ) {
+ HeapRegionNode hrn = todoNodes1.iterator().next();
+ todoNodes1.remove( hrn );
+ reachableNodes1.add(hrn);
+
+ Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+
+ if( !reachableNodes1.contains( edge.getDst() ) ) {
+ todoNodes1.add( edge.getDst() );
}
- if( alphaI1.containsTuple(gi2) ) {
- return true;
+ }
+ }
+
+ while( !todoNodes2.isEmpty() ) {
+ HeapRegionNode hrn = todoNodes2.iterator().next();
+ todoNodes2.remove( hrn );
+ reachableNodes2.add(hrn);
+
+ Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+
+ if( !reachableNodes2.contains( edge.getDst() ) ) {
+ todoNodes2.add( edge.getDst() );
}
}
}
+
+ Set<HeapRegionNode> intersection =
+ new HashSet<HeapRegionNode>( reachableNodes1 );
- return false;
+ intersection.retainAll( reachableNodes2 );
+
+ return intersection;
}
+ /*
// for writing ownership graphs to dot files
- public void writeGraph(Descriptor methodDesc,
+ public void writeGraph(MethodContext mc,
FlatNode fn,
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
boolean writeReferencers,
- boolean writeParamMappings
+ boolean writeParamMappings
) throws java.io.IOException {
writeGraph(
- methodDesc.getSymbol() +
- methodDesc.getNum() +
+ mc.toString() +
fn.toString(),
writeLabels,
labelSelect,
);
}
- public void writeGraph(Descriptor methodDesc,
+ public void writeGraph(MethodContext mc,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+
+ writeGraph(mc+"COMPLETE",
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
+ }
+
+ public void writeGraph(MethodContext mc,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings,
+ boolean hideSubsetReachability
+ ) throws java.io.IOException {
+
+ writeGraph(mc+"COMPLETE",
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings,
+ hideSubsetReachability
+ );
+ }
+
+ public void writeGraph(MethodContext mc,
+ Integer numUpdate,
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
boolean writeReferencers,
- boolean writeParamMappings
+ boolean writeParamMappings
) throws java.io.IOException {
- writeGraph(methodDesc+"COMPLETE",
+ writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
writeLabels,
labelSelect,
pruneGarbage,
writeReferencers,
- writeParamMappings
+ writeParamMappings
);
}
- public void writeGraph(Descriptor methodDesc,
+ public void writeGraph(MethodContext mc,
Integer numUpdate,
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
boolean writeReferencers,
- boolean writeParamMappings
+ boolean writeParamMappings,
+ boolean hideSubsetReachability
) throws java.io.IOException {
- writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
+ writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings,
+ hideSubsetReachability
+ );
+ }
+
+ public void writeGraph(String graphName,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+ writeGraph(graphName,
writeLabels,
labelSelect,
pruneGarbage,
writeReferencers,
- writeParamMappings
+ writeParamMappings,
+ false
);
}
+ */
public void writeGraph(String graphName,
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
boolean writeReferencers,
- boolean writeParamMappings
+ boolean writeParamMappings,
+ boolean hideSubsetReachability,
+ boolean hideEdgeTaints
) throws java.io.IOException {
// remove all non-word characters from the graph name so
HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
// then visit every heap region node
- if( !pruneGarbage ) {
- Set s = id2hrn.entrySet();
- Iterator i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry)i.next();
- HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+ Set s = id2hrn.entrySet();
+ Iterator i = s.iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry)i.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ if( !pruneGarbage ||
+ (hrn.isFlagged() && hrn.getID() > 0) ||
+ hrn.getDescription().startsWith("param")
+ ) {
+
if( !visited.contains(hrn) ) {
traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
hrn,
bw,
null,
visited,
- writeReferencers);
+ writeReferencers,
+ hideSubsetReachability,
+ hideEdgeTaints);
}
}
}
bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
if( writeParamMappings ) {
+ /* UNMAINTAINED
Set df = paramIndex2id.entrySet();
Iterator ih = df.iterator();
while( ih.hasNext() ) {
Integer id = (Integer) meh.getValue();
bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
}
+ */
}
// then visit every label node, useful for debugging
if( writeLabels ) {
- Set s = td2ln.entrySet();
- Iterator i = s.iterator();
+ s = td2ln.entrySet();
+ i = s.iterator();
while( i.hasNext() ) {
Map.Entry me = (Map.Entry)i.next();
LabelNode ln = (LabelNode) me.getValue();
if( labelStr.startsWith("___temp") ||
labelStr.startsWith("___dst") ||
labelStr.startsWith("___srctmp") ||
- labelStr.startsWith("___neverused") ) {
+ labelStr.startsWith("___neverused") ||
+ labelStr.contains(qString) ||
+ labelStr.contains(rString) ||
+ labelStr.contains(blobString)
+ ) {
continue;
}
}
- bw.write(ln.toString() + ";\n");
+ //bw.write(" "+ln.toString() + ";\n");
Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
while( heapRegionsItr.hasNext() ) {
bw,
null,
visited,
- writeReferencers);
+ writeReferencers,
+ hideSubsetReachability,
+ hideEdgeTaints);
}
bw.write(" " + ln.toString() +
" -> " + hrn.toString() +
- "[label=\"" + edge.toGraphEdgeString() +
+ "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
+ hideEdgeTaints) +
"\",decorate];\n");
}
}
BufferedWriter bw,
TempDescriptor td,
HashSet<HeapRegionNode> visited,
- boolean writeReferencers
+ boolean writeReferencers,
+ boolean hideSubsetReachability,
+ boolean hideEdgeTaints
) throws java.io.IOException {
if( visited.contains(hrn) ) {
attributes += ",style=filled,fillcolor=lightgrey";
}
- attributes += ",label=\"ID" +
- hrn.getID() +
- "\\n" +
- hrn.getDescription() +
- "\\n" +
- hrn.getAlphaString() +
+ attributes += ",label=\"ID" +
+ hrn.getID() +
+ "\\n";
+
+ if( hrn.getType() != null ) {
+ attributes += hrn.getType().toPrettyString() + "\\n";
+ }
+
+ attributes += hrn.getDescription() +
+ "\\n" +
+ hrn.getAlphaString(hideSubsetReachability) +
"\"]";
bw.write(" " + hrn.toString() + attributes + ";\n");
// useful for debugging
+ // UNMAINTAINED
+ /*
if( writeReferencers ) {
OwnershipNode onRef = null;
Iterator refItr = hrn.iteratorToReferencers();
}
}
}
+ */
Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
while( childRegionsItr.hasNext() ) {
case VISIT_HRN_WRITE_FULL:
bw.write(" " + hrn.toString() +
" -> " + hrnChild.toString() +
- "[label=\"" + edge.toGraphEdgeString() +
+ "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
+ hideEdgeTaints) +
"\",decorate];\n");
break;
}
bw,
td,
visited,
- writeReferencers);
+ writeReferencers,
+ hideSubsetReachability,
+ hideEdgeTaints);
}
}
+
+ public int getTaintIdentifierFromHRN(HeapRegionNode hrn){
+ HashSet<ReferenceEdge> referenceEdges=hrn.referencers;
+ Iterator<ReferenceEdge> iter=referenceEdges.iterator();
+
+ int taintIdentifier=0;
+ while(iter.hasNext()){
+ ReferenceEdge edge=iter.next();
+ taintIdentifier=taintIdentifier | edge.getTaintIdentifier();
+ }
+
+ return taintIdentifier;
+
+ }
+
+ public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet){
+
+ HashSet<ReferenceEdge> setEdge=hrn.referencers;
+ Iterator<ReferenceEdge> iter=setEdge.iterator();
+ while(iter.hasNext()){
+ ReferenceEdge 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<ReferenceEdge> setEdge=hrn.referencers;
+ Iterator<ReferenceEdge> iter=setEdge.iterator();
+ while(iter.hasNext()){
+ ReferenceEdge 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);
+ }
+
+ }
+ }
+
+ }
+
}
projects / IRC.git / blobdiff