public class OwnershipGraph {
private int allocationDepth;
+ private TypeUtil typeUtil;
// 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___");
+
public Hashtable<Integer, HeapRegionNode> id2hrn;
public Hashtable<TempDescriptor, LabelNode > td2ln;
public HashSet<AllocationSite> allocationSites;
- public OwnershipGraph(int allocationDepth) {
+
+
+ public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
this.allocationDepth = allocationDepth;
+ this.typeUtil = typeUtil;
id2hrn = new Hashtable<Integer, HeapRegionNode>();
td2ln = new Hashtable<TempDescriptor, LabelNode >();
if( alpha == null ) {
if( isFlagged || isParameter ) {
- alpha = new ReachabilitySet(new TokenTuple(id,
- !isSingleObject,
- TokenTuple.ARITY_ONE)
- ).makeCanonical();
+ 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,
+ isParameter,
isNewSummary,
allocSite,
alpha,
// of the nodes and edges involved.
//
////////////////////////////////////////////////////
- public void assignTempYToTempX(TempDescriptor y,
- TempDescriptor x) {
+ public void assignTempXEqualToTempY(TempDescriptor x,
+ TempDescriptor y) {
LabelNode lnX = getLabelNodeFromTemp(x);
LabelNode lnY = getLabelNodeFromTemp(y);
}
- public void assignTempYFieldFToTempX(TempDescriptor y,
- FieldDescriptor f,
- TempDescriptor x) {
-
+ public void assignTempXEqualToTempYFieldF(TempDescriptor x,
+ TempDescriptor y,
+ FieldDescriptor f) {
LabelNode lnX = getLabelNodeFromTemp(x);
LabelNode lnY = getLabelNodeFromTemp(y);
}
- public void assignTempYToTempXFieldF(TempDescriptor y,
- TempDescriptor x,
- FieldDescriptor f) {
-
+ public void assignTempXFieldFEqualToTempY(TempDescriptor x,
+ FieldDescriptor f,
+ TempDescriptor y) {
LabelNode lnX = getLabelNodeFromTemp(x);
LabelNode lnY = getLabelNodeFromTemp(y);
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();
+
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+
+ // we can do a strong update here if one of two cases holds
+ if( f != null &&
+ hrnX.isSingleObject() &&
+ ( (hrnX.getNumReferencers() == 1) ||
+ ( lnX.getNumReferencees() == 1)
+ )
+ ) {
+ strongUpdate = true;
+ clearReferenceEdgesFrom( hrnX, f, 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();
+ }
- //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
+ Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
+ while( edgeItr.hasNext() ) {
+ edgeItr.next().applyBetaNew();
+ }
+
+
+ // 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();
- // create the actual reference edge hrnX.f -> hrnY
+ // prepare the new reference edge hrnX.f -> hrnY
ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
hrnY,
f,
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 );
- }
-
- addReferenceEdge( hrnX, hrnY, edgeNew );
- } 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 );
- }
- }
- */
+ // 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 );
+
+ if( edgeExisting != null ) {
+ edgeExisting.setBeta(
+ edgeExisting.getBeta().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 );
+ }
}
}
- Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
- while( nodeItr.hasNext() ) {
- nodeItr.next().applyAlphaNew();
- }
- Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
- while( edgeItr.hasNext() ) {
- edgeItr.next().applyBetaNew();
- }
+ // if there was a strong update, make sure to improve
+ // reachability with a global sweep
+ if( strongUpdate ) {
+ globalSweep();
+ }
}
- public void assignParameterAllocationToTemp(boolean isTask,
- TempDescriptor td,
- Integer paramIndex) {
+ 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);
+ false,
+ isTask,
+ false,
+ true,
+ null,
+ null,
+ "param" + paramIndex);
// this is a non-program-accessible label that picks up beta
// info to be used for fixing a caller of this method
ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
true,
- TokenTuple.ARITY_ONE) );
+ TokenTuple.ARITY_ONE).makeCanonical()
+ ).makeCanonical();
// heap regions for parameters are always multiple object (see above)
// and have a reference to themselves, because we can't know the
}
- public void assignNewAllocationToTempX(TempDescriptor x,
- AllocationSite as) {
+ public void assignReturnEqualToTemp(TempDescriptor x) {
+
+ LabelNode lnR = getLabelNodeFromTemp(tdReturn);
+ LabelNode lnX = getLabelNodeFromTemp(x);
+
+ clearReferenceEdgesFrom(lnR, null, true);
+
+ Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
+ while( itrXhrn.hasNext() ) {
+ ReferenceEdge edgeX = itrXhrn.next();
+ HeapRegionNode referencee = edgeX.getDst();
+ ReferenceEdge edgeNew = edgeX.copy();
+ edgeNew.setSrc(lnR);
+
+ addReferenceEdge(lnR, referencee, edgeNew);
+ }
+ }
+
+
+ public void assignTempEqualToNewAlloc(TempDescriptor x,
+ AllocationSite as) {
assert x != null;
assert as != null;
// 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()
);
}
}
FlatMethod fm,
OwnershipGraph ogCallee) {
-
// define rewrite rules and other structures to organize
// data by parameter/argument index
Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
new Hashtable<Integer, ReachabilitySet>();
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d =
+ new Hashtable<Integer, ReachabilitySet>();
+
Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
new Hashtable<Integer, ReachabilitySet>();
Hashtable<Integer, TokenTuple> paramIndex2paramToken =
new Hashtable<Integer, TokenTuple>();
- Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
+ Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex =
new Hashtable<TokenTuple, Integer>();
- Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
+ Hashtable<Integer, TokenTuple> paramIndex2paramTokenPlus =
new Hashtable<Integer, TokenTuple>();
Hashtable<Integer, LabelNode> paramIndex2ln =
// 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.put( bogusIndex, rsIdentity );
- paramIndex2rewriteJ.put( bogusIndex, rsIdentity );
- paramToken2paramIndex.put( bogusToken, bogusIndex );
- paramIndex2paramToken.put( bogusIndex, bogusToken );
- paramTokenStar2paramIndex.put( bogusTokenStar, bogusIndex );
- paramIndex2paramTokenStar.put( bogusIndex, bogusTokenStar );
+ Integer bogusID = new Integer(-1);
+ Integer bogusIndex = new Integer(-1);
+ TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE).makeCanonical();
+ TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE).makeCanonical();
+ ReachabilitySet rsIdentity =
+ new ReachabilitySet(
+ new TokenTupleSet(bogusToken).makeCanonical()
+ ).makeCanonical();
+
+ paramIndex2rewriteH.put(bogusIndex, rsIdentity);
+ paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
+ paramToken2paramIndex.put(bogusToken, bogusIndex);
+ paramIndex2paramToken.put(bogusIndex, bogusToken);
+ paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
+ paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
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 );
+ 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() )
- );
+ paramIndex2rewriteH.put(paramIndex,
+
+ toShadowTokens(ogCallee, hrnParam.getAlpha() )
+ );
- ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo( hrnParam, null );
+ ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
assert edgeReflexive_i != null;
- paramIndex2rewriteJ.put( paramIndex,
- toShadowTokens( ogCallee, edgeReflexive_i.getBeta() )
- );
+ paramIndex2rewriteJ.put(paramIndex,
+ toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
+ );
- TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
+ 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(hrnParam, 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 );
+ 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_plus = new TokenTuple(hrnParam.getID(),
+ true,
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+ paramTokenPlus2paramIndex.put(p_i_plus, paramIndex);
+ paramIndex2paramTokenPlus.put(paramIndex, p_i_plus);
// 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 );
+ argTemp_i = fc.getArg(paramIndex);
} else {
- if( paramIndex == 0 ) {
+ if( paramIndex.equals(0) ) {
argTemp_i = fc.getThis();
} else {
- argTemp_i = fc.getArg( paramIndex - 1 );
+ argTemp_i = fc.getArg(paramIndex - 1);
}
}
-
+
// in non-static methods there is a "this" pointer
// that should be taken into account
if( isStatic ) {
} else {
assert fc.numArgs() + 1 == fm.numParameters();
}
-
- LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
- paramIndex2ln.put( paramIndex, argLabel_i );
- ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
+ LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
+ paramIndex2ln.put(paramIndex, argLabel_i);
+
+ ReachabilitySet d_i = 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 = d_i.union(edge.getBeta());
}
- D_i = D_i.exhaustiveArityCombinations();
- paramIndex2rewriteD.put( paramIndex, D_i );
+ paramIndex2rewrite_d.put(paramIndex, d_i);
+
+ ReachabilitySet D_i = d_i.exhaustiveArityCombinations();
+ paramIndex2rewriteD.put(paramIndex, D_i);
}
-
+
HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
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();
// rewrite alpha for the nodes reachable from argument label i
Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
while( edgeArgItr.hasNext() ) {
ReferenceEdge edge = edgeArgItr.next();
- todoNodes.add( edge.getDst() );
+ todoNodes.add(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 );
+ todoNodes.remove(hrn);
+ reachableNodes.add(hrn);
Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
while( edgeItr.hasNext() ) {
ReferenceEdge edge = edgeItr.next();
- if( !reachableNodes.contains( edge.getDst() ) ) {
- todoNodes.add( edge.getDst() );
+ if( !reachableNodes.contains(edge.getDst() ) ) {
+ todoNodes.add(edge.getDst() );
}
- }
+ }
}
-
+
// save for later
- paramIndex2reachableCallerNodes.put( index, reachableNodes );
+ paramIndex2reachableCallerNodes.put(index, reachableNodes);
// now iterate over reachable nodes to update their alpha, and
// classify edges found as "argument reachable" or "upstream"
while( hrnItr.hasNext() ) {
HeapRegionNode hrn = hrnItr.next();
- rewriteCallerNodeAlpha( fm.numParameters(),
- index,
- hrn,
- paramIndex2rewriteH,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar );
+ rewriteCallerReachability(index,
+ hrn,
+ null,
+ paramIndex2rewriteH.get(index),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ paramIndex2paramToken.get(index),
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ false,
+ null);
+
+ nodesWithNewAlpha.add(hrn);
- nodesWithNewAlpha.add( hrn );
-
// look at all incoming edges to the reachable nodes
// and sort them as edges reachable from the argument
// label node, or upstream edges
if( on instanceof LabelNode ) {
LabelNode ln0 = (LabelNode) on;
- if( ln0.equals( lnArg_i ) ) {
- edgesReachable.add( edge );
- } else {
- edgesUpstream.add( edge );
+ if( ln0.equals(lnArg_i) ) {
+ edgesReachable.add(edge);
+ } else {
+ edgesUpstream.add(edge);
}
} else {
HeapRegionNode hrn0 = (HeapRegionNode) on;
- if( reachableNodes.contains( hrn0 ) ) {
- edgesReachable.add( edge );
+ if( reachableNodes.contains(hrn0) ) {
+ edgesReachable.add(edge);
} else {
- edgesUpstream.add( edge );
+ edgesUpstream.add(edge);
}
}
- }
+ }
}
-
// update reachable edges
Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
while( edgeReachableItr.hasNext() ) {
ReferenceEdge edgeReachable = edgeReachableItr.next();
- rewriteCallerEdgeBeta( fm.numParameters(),
- index,
- edgeReachable,
- paramIndex2rewriteJ,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar,
- false,
- null );
-
- edgesWithNewBeta.add( edgeReachable );
- }
-
+ rewriteCallerReachability(index,
+ null,
+ edgeReachable,
+ paramIndex2rewriteJ.get(index),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ paramIndex2paramToken.get(index),
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ false,
+ null);
+
+ edgesWithNewBeta.add(edgeReachable);
+ }
// update upstream edges
- Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
- = new Hashtable<ReferenceEdge, ChangeTupleSet>();
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
+ new Hashtable<ReferenceEdge, ChangeTupleSet>();
Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
while( edgeUpstreamItr.hasNext() ) {
ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
- rewriteCallerEdgeBeta( fm.numParameters(),
- index,
- edgeUpstream,
- paramIndex2rewriteK,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar,
- true,
- edgeUpstreamPlannedChanges );
-
- edgesWithNewBeta.add( edgeUpstream );
+ rewriteCallerReachability(index,
+ null,
+ edgeUpstream,
+ paramIndex2rewriteK.get(index),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ paramIndex2paramToken.get(index),
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ true,
+ edgeUpstreamPlannedChanges);
+
+ edgesWithNewBeta.add(edgeUpstream);
}
- propagateTokensOverEdges( edgesUpstream,
- edgeUpstreamPlannedChanges,
- edgesWithNewBeta );
- }
-
+ propagateTokensOverEdges(edgesUpstream,
+ edgeUpstreamPlannedChanges,
+ edgesWithNewBeta);
+ }
+
// commit changes to alpha and beta
Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
}
-
// 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
Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
while( asItr.hasNext() ) {
AllocationSite allocSite = asItr.next();
- HeapRegionNode hrnSummary = getSummaryNode( allocSite );
-
+ 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 );
+ transferOnto(hrnSummary, hrnShadowSummary);
- hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnShadowSummary.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,
+ hrnShadowSummary.getAlpha(),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ bogusToken,
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ false,
+ null);
+
+ hrnShadowSummary.applyAlphaNew();
for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
assert hrnIthShadow.getNumReferencers() == 0;
assert hrnIthShadow.getNumReferencees() == 0;
- transferOnto( hrnIth, hrnIthShadow );
-
- hrnIthShadow.setAlpha( toShadowTokens( ogCallee, hrnIthShadow.getAlpha() ) );
+ transferOnto(hrnIth, hrnIthShadow);
- rewriteCallerNodeAlpha( fm.numParameters(),
- bogusIndex,
- hrnIthShadow,
- paramIndex2rewriteH,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar );
+ assert ogCallee.id2hrn.containsKey(idIth);
+ HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
+ hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
+
+ rewriteCallerReachability(bogusIndex,
+ hrnIthShadow,
+ null,
+ hrnIthShadow.getAlpha(),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ bogusToken,
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ 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();
- HeapRegionNode hrnChildCallee = edgeCallee.getDst();
+ HeapRegionNode hrnChildCallee = edgeCallee.getDst();
Integer idChildCallee = hrnChildCallee.getID();
-
+
// only address this edge if it is not a special reflexive edge
if( !edgeCallee.isInitialParamReflexive() ) {
-
+
// now we know that in the callee method's ownership graph
// there is a heap region->heap region reference edge given
// by heap region pointers:
// 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.getFieldDesc(),
+ false,
+ toShadowTokens(ogCallee,
+ edgeCallee.getBeta() )
+ );
+ rewriteCallerReachability(bogusIndex,
+ null,
+ edgeNewInCallerTemplate,
+ edgeNewInCallerTemplate.getBeta(),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ bogusToken,
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ false,
+ null);
+ edgeNewInCallerTemplate.applyBetaNew();
// So now make a set of possible source heaps in the caller graph
// and a set of destination heaps in the caller graph, and make
// a reference edge in the caller for every possible (src,dst) pair
HashSet<HeapRegionNode> possibleCallerSrcs =
- getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
- edgeCallee,
- true,
- paramIndex2reachableCallerNodes );
-
+ getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
+ (HeapRegionNode) edgeCallee.getSrc(),
+ paramIndex2reachableCallerNodes);
+
HashSet<HeapRegionNode> possibleCallerDsts =
- getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
- edgeCallee,
- false,
- paramIndex2reachableCallerNodes );
-
+ getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
+ edgeCallee.getDst(),
+ paramIndex2reachableCallerNodes);
+
+
// make every possible pair of {srcSet} -> {dstSet} edges in the caller
Iterator srcItr = possibleCallerSrcs.iterator();
while( srcItr.hasNext() ) {
HeapRegionNode src = (HeapRegionNode) srcItr.next();
-
+
+ if( !hasMatchingField(src, edgeCallee) ) {
+ // prune this source node possibility
+ continue;
+ }
+
Iterator dstItr = possibleCallerDsts.iterator();
while( dstItr.hasNext() ) {
HeapRegionNode dst = (HeapRegionNode) dstItr.next();
-
+
+ if( !hasMatchingType(edgeCallee, dst) ) {
+ // prune
+ continue;
+ }
+
+ // otherwise the caller src and dst pair can match the edge, so make it
ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
- edgeNewInCaller.setSrc( src );
- edgeNewInCaller.setDst( dst );
-
- ReferenceEdge edgeExisting = src.getReferenceTo( dst, edgeNewInCaller.getFieldDesc() );
+ edgeNewInCaller.setSrc(src);
+ edgeNewInCaller.setDst(dst);
+
+ ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
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
+ TempDescriptor returnTemp = fc.getReturnTemp();
+ if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
+
+ LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
+ clearReferenceEdgesFrom(lnLhsCaller, null, true);
+
+ 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() )
+ );
+ rewriteCallerReachability(bogusIndex,
+ null,
+ edgeNewInCallerTemplate,
+ edgeNewInCallerTemplate.getBeta(),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ bogusToken,
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ false,
+ null);
+
+ edgeNewInCallerTemplate.applyBetaNew();
+
+
+ HashSet<HeapRegionNode> assignCallerRhs =
+ getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
+ edgeCallee.getDst(),
+ paramIndex2reachableCallerNodes);
+
+ Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
+ while( itrHrn.hasNext() ) {
+ HeapRegionNode hrnCaller = itrHrn.next();
+
+ 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);
+
+ ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
+ if( edgeExisting == null ) {
+
+ // if this edge doesn't exist in the caller, create it
+ addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
+ } else {
+ // if it already exists, merge with it
+ edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
+ }
+ }
+ }
+ }
+
+
// merge the shadow nodes of allocation sites back down to normal capacity
Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
while( allocItr.hasNext() ) {
// 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() );
// 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);
-
+
transferOnto(hrnIthShadow, hrnIth);
-
+
// clear off shadow nodes after transfer
clearReferenceEdgesFrom(hrnIthShadow, null, true);
clearReferenceEdgesTo(hrnIthShadow, null, true);
- hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() );
- }
+ 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();
LabelNode ln = (LabelNode) me.getValue();
-
+
Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
while( itrEdges.hasNext() ) {
unshadowTokens(as, itrEdges.next() );
}
}
-
+
Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
while( itrAllHRNodes.hasNext() ) {
Map.Entry me = (Map.Entry)itrAllHRNodes.next();
HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
-
+
unshadowTokens(as, hrnToAge);
-
+
Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
while( itrEdges.hasNext() ) {
unshadowTokens(as, itrEdges.next() );
}
- }
+ }
+ }
+
+ // improve reachability as much as possible
+ globalSweep();
+ }
+
+
+ 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 ) {
+ return true;
+ }
+
+ TypeDescriptor tdSrc = asSrc.getType();
+ assert tdSrc != null;
+
+ // 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;
+ }
+ }
+
+ // 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 ) {
+ 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
+ ClassDescriptor cdDst = tdDst.getClassDesc();
+ if( cdDst == null ) {
+ return false;
+ }
+
+ // if the field is null, it matches everything
+ FieldDescriptor fd = edge.getFieldDesc();
+ if( fd == null ) {
+ return true;
+ }
+ TypeDescriptor tdFd = fd.getType();
+ assert tdFd != null;
+
+ return typeUtil.isSuperorType(tdFd, tdDst);
}
+
protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
edge.setBeta(edge.getBeta().unshadowTokens(as) );
}
}
- private ReachabilitySet toShadowTokens( OwnershipGraph ogCallee,
- ReachabilitySet rsIn ) {
+ 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() ) {
AllocationSite as = allocItr.next();
- rsOut = rsOut.toShadowTokens( as );
+ rsOut = rsOut.toShadowTokens(as);
}
return rsOut.makeCanonical();
}
- 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;
+ private void rewriteCallerReachability(Integer paramIndex,
+ HeapRegionNode hrn,
+ ReferenceEdge edge,
+ ReachabilitySet rules,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
+ TokenTuple p_i,
+ Hashtable<TokenTuple, Integer> paramToken2paramIndex,
+ Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex,
+ boolean makeChangeSet,
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
+ assert(hrn == null && edge != null) ||
+ (hrn != null && edge == null);
- TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
- assert tokenToRewrite != null;
+ assert rules != null;
+ assert p_i != 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 callerReachabilityCurrent;
+ if( hrn == null ) {
+ callerReachabilityCurrent = edge.getBeta();
+ } else {
+ callerReachabilityCurrent = hrn.getAlpha();
}
-
- 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 ) );
- }
+ ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
+ // for initializing structures in this method
+ TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
- 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;
+ // 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>() );
- TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
- assert tokenToRewrite != null;
- ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
+ Iterator<TokenTupleSet> rulesItr = rules.iterator();
+ while(rulesItr.hasNext()) {
+ TokenTupleSet rule = rulesItr.next();
- Iterator<TokenTupleSet> ttsItr = rules.iterator();
- while( ttsItr.hasNext() ) {
- TokenTupleSet tts = ttsItr.next();
+ ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
- Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
- new Hashtable<TokenTupleSet, 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();
- TokenTupleSet ttsAdd = (TokenTupleSet) me.getValue();
-
- ChangeTuple ct = new ChangeTuple( ttsMatch,
- ttsAdd
- ).makeCanonical();
-
- cts0 = cts0.union( ct );
- }
- }
+ Iterator<TokenTuple> ruleItr = rule.iterator();
+ while(ruleItr.hasNext()) {
+ TokenTuple ttCallee = ruleItr.next();
-
- ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
- ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
-
- Iterator<ChangeTuple> ctItr = cts0.iterator();
- while( ctItr.hasNext() ) {
- ChangeTuple ct = ctItr.next();
-
- ReachabilitySet rTemp = rewriteDpass( numParameters,
- paramIndex,
- ct.getSetToAdd(),
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar
- ).makeCanonical();
- r1 = r1.union( rTemp );
-
- if( makeChangeSet ) {
- assert edgePlannedChanges != null;
-
- Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
- while( ttsTempItr.hasNext() ) {
- TokenTupleSet tts = ttsTempItr.next();
+ // compute the possibilities for rewriting this callee token
+ ReachabilitySet ttCalleeRewrites = null;
+ boolean callerSourceUsed = false;
+
+ if( ttCallee.equals(p_i) ) {
+ // replace the arity-one token of the current parameter with the reachability
+ // information from the caller edge
+ ttCalleeRewrites = callerReachabilityCurrent;
+ callerSourceUsed = true;
+
+ } else if( paramToken2paramIndex.containsKey(ttCallee) ) {
+ // use little d
+ Integer paramIndex_j = paramToken2paramIndex.get(ttCallee);
+ assert paramIndex_j != null;
+ ttCalleeRewrites = paramIndex2rewrite_d.get(paramIndex_j);
+ assert ttCalleeRewrites != null;
- ChangeTuple ctFinal = new ChangeTuple( ct.getSetToMatch(),
- tts
- ).makeCanonical();
+ } else if( paramTokenPlus2paramIndex.containsKey(ttCallee) ) {
+ // worse, use big D
+ Integer paramIndex_j = paramTokenPlus2paramIndex.get(ttCallee);
+ assert paramIndex_j != null;
+ ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
+ assert ttCalleeRewrites != null;
- cts1 = cts1.union( ctFinal );
+ } 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();
}
- }
- }
- if( makeChangeSet ) {
- edgePlannedChanges.put( edge, cts1 );
- }
+ // branch every version of the working rewritten rule with
+ // the possibilities for rewriting the current callee token
+ ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
- edge.setBetaNew( edge.getBetaNew().union( r1 ) );
- }
+ Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
+ while( rewrittenRuleItr.hasNext() ) {
+ TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
+ Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
+ while( ttCalleeRewritesItr.hasNext() ) {
+ TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
- private ReachabilitySet rewriteDpass( int numParameters,
- Integer paramIndex,
- TokenTupleSet ttsIn,
- Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
- Hashtable<Integer, TokenTuple> paramIndex2paramToken,
- Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
+ TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity(ttsBranch);
- ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
+ 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;
- boolean rewritten = false;
+ // make a shallow copy for possible modification
+ sourceSets = (HashSet<TokenTupleSet>)sourceSets.clone();
- 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;
- }
+ // if we used something from the caller to rewrite it, remember
+ if( callerSourceUsed ) {
+ sourceSets.add(ttsBranch);
+ }
+
+ // set mapping for the further rewritten rule
+ rewritten2source.put(ttsRewrittenNext, sourceSets);
+ }
+
+ rewrittenRuleWithTTCallee =
+ rewrittenRuleWithTTCallee.union(ttsRewrittenNext);
+ }
}
+
+ // now the rewritten rule's possibilities have been extended by
+ // rewriting the current callee token, remember result
+ rewrittenRule = rewrittenRuleWithTTCallee;
}
-
- 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;
+
+ // 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 ) {
+ 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) );
}
}
+
+ 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,
- ReferenceEdge edgeCallee,
- boolean mapFromSrc,
- Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
- ) {
-
+
+ private HashSet<HeapRegionNode>
+ getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
+ HeapRegionNode hrnCallee,
+ Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
+ ) {
+
HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
-
- HeapRegionNode hrnCallee;
- if( mapFromSrc ) {
- OwnershipNode on = edgeCallee.getSrc();
- assert on instanceof HeapRegionNode;
- hrnCallee = (HeapRegionNode) on;
- } else {
- hrnCallee = edgeCallee.getDst();
- }
- Integer paramIndexCallee = ogCallee.id2paramIndex.get( hrnCallee.getID() );
+ Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
if( paramIndexCallee == null ) {
// this is a node allocated in the callee then and it has
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;
} 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);
+ HeapRegionNode hrnCaller = id2hrn.get(idCaller);
+ possibleCallerHRNs.add(hrnCaller);
+
} else {
// 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 );
-
- // TODO PRUNE BY TYPE/FIELD NAME!!
+ assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
+ possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
}
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.
+ //
+ ////////////////////////////////////////////////////
+ protected void globalSweep() {
+
+ // a work set for performing the sweep
+ Hashtable<HeapRegionNode, HashSet<TokenTupleSet> > workSet =
+ new Hashtable<HeapRegionNode, HashSet<TokenTupleSet> >();
+
+ // first initialize every alphaNew for a flagged region
+ // (or parameter region) to a set with just that token
+ 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
+ ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
+ assert rsEmpty.equals( hrn.getAlphaNew() );
+
+ Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
+ while( itrRes.hasNext() ) {
+ ReferenceEdge edge = itrRes.next();
+ assert rsEmpty.equals( edge.getBetaNew() );
+ }
+
+ TokenTuple tt = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONE ).makeCanonical();
+ TokenTuple ttPlus = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONEORMORE ).makeCanonical();
+ TokenTuple ttStar = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
+
+ TokenTupleSet tts = new TokenTupleSet( tt ).makeCanonical();
+ TokenTupleSet ttsPlus = new TokenTupleSet( ttPlus ).makeCanonical();
+ TokenTupleSet ttsStar = new TokenTupleSet( ttStar ).makeCanonical();
+ TokenTupleSet ttsEmpty = new TokenTupleSet( ).makeCanonical();
+
+ if( hrn.isFlagged() || hrn.isParameter() ) {
+ HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
+ subWorkSet.add( tts );
+ subWorkSet.add( ttsPlus );
+ subWorkSet.add( ttsStar );
+ workSet.put( hrn, subWorkSet );
+
+ hrn.setAlphaNew( new ReachabilitySet( tts ).makeCanonical() );
+ } else {
+ hrn.setAlphaNew( new ReachabilitySet( ttsEmpty ).makeCanonical() );
+ }
+ }
+
+ // then propagate tokens forward one step at a time
+ while( !workSet.isEmpty() ) {
+ HeapRegionNode hrn = workSet.keySet().iterator().next();
+
+ HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
+ assert subWorkSet != null;
+
+ if( subWorkSet.isEmpty() ) {
+ // we're currently done with sub work at this heap region, although
+ // more work may get queued up later, but remove it for now and continue
+ workSet.remove( hrn );
+ continue;
+ }
+
+ TokenTupleSet tts = subWorkSet.iterator().next();
+ subWorkSet.remove( tts );
+
+ // try to push this TokenTupleSet over all outgoing edges
+ Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencees();
+ while( itrRes.hasNext() ) {
+ ReferenceEdge edge = itrRes.next();
+
+ if( edge.getBeta().containsSuperSet( tts ) ) {
+ HeapRegionNode dst = edge.getDst();
+
+ // make a set of possible contributions this token
+ // might have on the alpha set here
+ HashSet<TokenTupleSet> ttsNewSet = new HashSet<TokenTupleSet>();
+
+ Iterator<TokenTupleSet> itrDstAlphaNew = dst.getAlphaNew().iterator();
+ while( itrDstAlphaNew.hasNext() ) {
+ TokenTupleSet ttsDstAlphaNew = itrDstAlphaNew.next();
+ ttsNewSet.add( tts.unionUpArity( ttsDstAlphaNew ) );
+ }
+
+ // only add this to the dst alpha new if it is in the beta of
+ // the edge we crossed to get here, and then only continue the
+ // propagation if it isn't already in the dst alpha new
+ Iterator<TokenTupleSet> itrNewSet = ttsNewSet.iterator();
+ while( itrNewSet.hasNext() ) {
+ TokenTupleSet ttsNew = itrNewSet.next();
+
+ if( edge.getBeta().containsSuperSet( ttsNew ) &&
+ !dst.getAlphaNew().contains( ttsNew ) ) {
+
+ // okay, this is a valid propagation, and add to the
+ // work set to further propagate it
+ dst.setAlphaNew( dst.getAlphaNew().union( ttsNew ) );
+
+ HashSet<TokenTupleSet> subWorkSetDst = workSet.get( dst );
+ if( subWorkSetDst == null ) {
+ subWorkSetDst = new HashSet<TokenTupleSet>();
+ }
+
+ subWorkSetDst.add( ttsNew );
+ workSet.put( dst, subWorkSetDst );
+ }
+ }
+ }
+ }
+ }
+
+ // now prepare work sets to propagate token sets backwards
+ // from heap regions across all edges
+ assert workSet.isEmpty();
+ hrns = id2hrn.entrySet();
+ itrHrns = hrns.iterator();
+ while( itrHrns.hasNext() ) {
+ Map.Entry me = (Map.Entry)itrHrns.next();
+ HeapRegionNode hrn = (HeapRegionNode) me.getValue();
+
+ HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
+
+ Iterator<TokenTupleSet> itrAlphaNewSets = hrn.getAlphaNew().iterator();
+ while( itrAlphaNewSets.hasNext() ) {
+ TokenTupleSet tts = itrAlphaNewSets.next();
+ subWorkSet.add( tts );
+ }
+
+ workSet.put( hrn, subWorkSet );
+ }
+
+ // propagate token sets backwards across edges one step at a time
+ while( !workSet.isEmpty() ) {
+ HeapRegionNode hrn = workSet.keySet().iterator().next();
+
+ HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
+ assert subWorkSet != null;
+
+ if( subWorkSet.isEmpty() ) {
+ // we're currently done with sub work at this heap region, although
+ // more work may get queued up later, but remove it for now and continue
+ workSet.remove( hrn );
+ continue;
+ }
+
+ TokenTupleSet tts = subWorkSet.iterator().next();
+ subWorkSet.remove( tts );
+
+ // try to push this TokenTupleSet back up incoming edges
+ Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
+ while( itrRes.hasNext() ) {
+ ReferenceEdge edge = itrRes.next();
+ if( edge.getBeta().containsWithZeroes( tts ) &&
+ !edge.getBetaNew().contains( tts ) ) {
+ // okay, this is a valid propagation, and add to the
+ // work set to further propagate it
+ edge.setBetaNew( edge.getBetaNew().union( tts ) );
+
+ OwnershipNode src = edge.getSrc();
+ if( src instanceof HeapRegionNode ) {
+
+ HashSet<TokenTupleSet> subWorkSetSrc = workSet.get( (HeapRegionNode) src );
+ if( subWorkSetSrc == null ) {
+ subWorkSetSrc = new HashSet<TokenTupleSet>();
+ }
+
+ subWorkSetSrc.add( tts );
+ workSet.put( (HeapRegionNode) src, subWorkSetSrc );
+ }
+ }
+ }
+ }
+
+ // apply alphaNew and betaNew to all nodes and edges
+ 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() );
+ }
+ }
+
+ Iterator<ReferenceEdge> edgeItr = res.iterator();
+ while( edgeItr.hasNext() ) {
+ edgeItr.next().applyBetaNew();
+ }
+ }
+
////////////////////////////////////////////////////
return id2paramIndex.size() == og.id2paramIndex.size();
}
+ public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
+
+ // get parameter's heap region
+ assert paramIndex2id.containsKey(paramIndex1);
+ Integer idParam1 = paramIndex2id.get(paramIndex1);
+
+ assert id2hrn.containsKey(idParam1);
+ HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
+ assert hrnParam1 != null;
+
+ // get tokens for this parameter
+ TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ TokenTuple pPlus1 = new TokenTuple(hrnParam1.getID(),
+ true,
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
+ TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
+ true,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+
+ // get tokens for the other parameter
+ assert paramIndex2id.containsKey(paramIndex2);
+ Integer idParam2 = paramIndex2id.get(paramIndex2);
+
+ assert id2hrn.containsKey(idParam2);
+ HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
+ assert hrnParam2 != null;
+
+ TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ TokenTuple pPlus2 = new TokenTuple(hrnParam2.getID(),
+ true,
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
+ TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
+ true,
+ 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 edge from label q to parameter's hrn
+ ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
+ assert edgeSpecialQ1 != null;
+
+ // 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;
+
+ if( beta1.containsTupleSetWithBoth(p1, p2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(pPlus1, p2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(p1, pPlus2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(pPlus1, pPlus2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(pStar1, pPlus2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(p1, pStar2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(pPlus1, pStar2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
+ return true;
+ }
+
+ return false;
+ }
+
+
+ public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
+
+ // get parameter's heap region
+ assert paramIndex2id.containsKey(paramIndex);
+ Integer idParam = paramIndex2id.get(paramIndex);
+
+ assert id2hrn.containsKey(idParam);
+ HeapRegionNode hrnParam = id2hrn.get(idParam);
+ assert hrnParam != null;
+
+ // get tokens for this parameter
+ TokenTuple p = new TokenTuple(hrnParam.getID(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ TokenTuple pPlus = new TokenTuple(hrnParam.getID(),
+ true,
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
+ TokenTuple pStar = new TokenTuple(hrnParam.getID(),
+ true,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+ // 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;
+
+ // look through this beta set for potential aliases
+ ReachabilitySet beta = edgeSpecialQ.getBeta();
+ assert beta != null;
+
+
+ // get tokens for summary node
+ TokenTuple gs = new TokenTuple(as.getSummary(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ TokenTuple gsPlus = new TokenTuple(as.getSummary(),
+ true,
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
+ TokenTuple gsStar = new TokenTuple(as.getSummary(),
+ true,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+
+ if( beta.containsTupleSetWithBoth(p, gs) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pPlus, gs) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pStar, gs) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(p, gsPlus) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pPlus, gsPlus) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pStar, gsPlus) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(p, gsStar) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pPlus, gsStar) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
+ return true;
+ }
+
+ // check for other nodes
+ for( int i = 0; i < as.getAllocationDepth(); ++i ) {
- /*
- // given a set B of heap region node ID's, return the set of heap
- // region node ID's that is reachable from B
- public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
+ // the other nodes of an allocation site are single, no plus
+ TokenTuple gi = new TokenTuple(as.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ONE).makeCanonical();
- HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
- HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
+ TokenTuple giStar = new TokenTuple(as.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
- // initial nodes to visit are from set B
- Iterator initialItr = idSetB.iterator();
- while( initialItr.hasNext() ) {
- Integer idInitial = (Integer) initialItr.next();
- assert id2hrn.contains( idInitial );
- HeapRegionNode hrnInitial = id2hrn.get( idInitial );
- toVisit.add( hrnInitial );
+ if( beta.containsTupleSetWithBoth(p, gi) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pPlus, gi) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pStar, gi) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(p, giStar) ) {
+ return true;
}
+ if( beta.containsTupleSetWithBoth(pPlus, giStar) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pStar, giStar) ) {
+ return true;
+ }
+ }
- HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
+ return false;
+ }
+
+
+ public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
+
+ // get tokens for summary nodes
+ TokenTuple gs1 = new TokenTuple(as1.getSummary(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ TokenTuple gsPlus1 = new TokenTuple(as1.getSummary(),
+ true,
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
+ TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
+ true,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+ // get summary node'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;
- // do a heap traversal
- while( !toVisit.isEmpty() ) {
- HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
- toVisit.remove( hrnVisited );
- visited.add ( hrnVisited );
- // for every node visited, add it to the total
- // reachable set
- idSetReachableFromB.add( hrnVisited.getID() );
+ // and for the other one
+ TokenTuple gs2 = new TokenTuple(as2.getSummary(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical();
- // find other reachable nodes
- Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
- while( referenceeItr.hasNext() ) {
- Map.Entry me = (Map.Entry) referenceeItr.next();
- HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
+ TokenTuple gsPlus2 = new TokenTuple(as2.getSummary(),
+ true,
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
+ TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
+ true,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+ // get summary node'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(gsPlus2) ) {
+ return true;
+ }
+ if( alphaSum1.containsTuple(gsStar2) ) {
+ return true;
+ }
+ if( alphaSum2.containsTuple(gsPlus1) ) {
+ return true;
+ }
+ if( alphaSum2.containsTuple(gsStar1) ) {
+ return true;
+ }
- if( !visited.contains( hrnReferencee ) ) {
- toVisit.add( hrnReferencee );
- }
- }
+ // only check ONE token if they are different sites
+ if( as1 != as2 ) {
+ if( alphaSum1.containsTuple(gs2) ) {
+ return true;
+ }
+ if( alphaSum2.containsTuple(gs1) ) {
+ return true;
}
+ }
- return idSetReachableFromB;
- }
+ // check sum2 against alloc1 nodes
+ for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
+ Integer idI1 = as1.getIthOldest(i);
+ assert id2hrn.containsKey(idI1);
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+ assert hrnI1 != null;
+ ReachabilitySet alphaI1 = hrnI1.getAlpha();
+ assert alphaI1 != null;
- // used to find if a heap region can possibly have a reference to
- // any of the heap regions in the given set
- // if the id supplied is in the set, then a self-referencing edge
- // would return true, but that special case is specifically allowed
- // meaning that it isn't an external alias
- public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
+ // the other nodes of an allocation site are single, no stars
+ TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ONE).makeCanonical();
- assert id2hrn.contains( id );
- HeapRegionNode hrn = id2hrn.get( id );
+ TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+ if( alphaSum2.containsTuple(gi1) ) {
+ return true;
+ }
+ if( alphaSum2.containsTuple(giStar1) ) {
+ return true;
+ }
+ if( alphaI1.containsTuple(gs2) ) {
+ return true;
+ }
+ if( alphaI1.containsTuple(gsPlus2) ) {
+ return true;
+ }
+ if( alphaI1.containsTuple(gsStar2) ) {
+ return true;
+ }
+ }
- //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
+ // check sum1 against alloc2 nodes
+ for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
+ Integer idI2 = as2.getIthOldest(i);
+ assert id2hrn.containsKey(idI2);
+ HeapRegionNode hrnI2 = id2hrn.get(idI2);
+ assert hrnI2 != null;
+ ReachabilitySet alphaI2 = hrnI2.getAlpha();
+ assert alphaI2 != null;
- //Iterator i = idSet.iterator();
- //while( i.hasNext() ) {
- // Integer idFromSet = (Integer) i.next();
- // assert id2hrn.contains( idFromSet );
- // hrnSet.add( id2hrn.get( idFromSet ) );
- //}
+ TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ONE).makeCanonical();
+ TokenTuple giStar2 = new TokenTuple(as2.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
- // do a traversal from hrn and see if any of the
- // heap regions from the set come up during that
- HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
- HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
+ if( alphaSum1.containsTuple(gi2) ) {
+ return true;
+ }
+ if( alphaSum1.containsTuple(giStar2) ) {
+ return true;
+ }
+ if( alphaI2.containsTuple(gs1) ) {
+ return true;
+ }
+ if( alphaI2.containsTuple(gsPlus1) ) {
+ return true;
+ }
+ if( alphaI2.containsTuple(gsStar1) ) {
+ return true;
+ }
- toVisit.add( hrn );
- while( !toVisit.isEmpty() ) {
- HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
- toVisit.remove( hrnVisited );
- visited.add ( hrnVisited );
+ // 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);
- Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
- while( referenceeItr.hasNext() ) {
- Map.Entry me = (Map.Entry) referenceeItr.next();
- HeapRegionNode hrnReferencee = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
+ // 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 ) {
+ continue;
+ }
+
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+ ReachabilitySet alphaI1 = hrnI1.getAlpha();
+ TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
+ false,
+ TokenTuple.ARITY_ONE).makeCanonical();
- if( idSet.contains( hrnReferencee.getID() ) ) {
- if( !id.equals( hrnReferencee.getID() ) ) {
- return true;
- }
- }
+ TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(j),
+ false,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
- if( !visited.contains( hrnReferencee ) ) {
- toVisit.add( hrnReferencee );
- }
- }
+ if( alphaI2.containsTuple(gi1) ) {
+ return true;
+ }
+ if( alphaI2.containsTuple(giStar1) ) {
+ return true;
+ }
+ if( alphaI1.containsTuple(gi2) ) {
+ return true;
+ }
+ if( alphaI1.containsTuple(giStar2) ) {
+ return true;
+ }
}
+ }
- return false;
- }
- */
+ return false;
+ }
// for writing ownership graphs to dot files
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers
+ boolean writeReferencers,
+ boolean writeParamMappings
) throws java.io.IOException {
writeGraph(
methodDesc.getSymbol() +
writeLabels,
labelSelect,
pruneGarbage,
- writeReferencers
+ writeReferencers,
+ writeParamMappings
);
}
public void writeGraph(Descriptor methodDesc,
- FlatNode fn,
boolean writeLabels,
- boolean writeReferencers
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
) throws java.io.IOException {
- writeGraph(
- methodDesc.getSymbol() +
- methodDesc.getNum() +
- fn.toString(),
- writeLabels,
- false,
- false,
- writeReferencers
- );
- }
- public void writeGraph(Descriptor methodDesc,
- boolean writeLabels,
- boolean writeReferencers
- ) throws java.io.IOException {
- writeGraph(
- methodDesc.getSymbol() +
- methodDesc.getNum() +
- "COMPLETE",
- writeLabels,
- false,
- false,
- writeReferencers
- );
+ writeGraph(methodDesc+"COMPLETE",
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
}
public void writeGraph(Descriptor methodDesc,
+ Integer numUpdate,
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers
+ boolean writeReferencers,
+ boolean writeParamMappings
) throws java.io.IOException {
- writeGraph(
- methodDesc.getSymbol() +
- methodDesc.getNum() +
- "COMPLETE",
- writeLabels,
- labelSelect,
- pruneGarbage,
- writeReferencers
- );
+
+ writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
}
public void writeGraph(String graphName,
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers
+ boolean writeReferencers,
+ boolean writeParamMappings
) throws java.io.IOException {
// remove all non-word characters from the graph name so
BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
bw.write("digraph "+graphName+" {\n");
- //bw.write( " size=\"7.5,10\";\n" );
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.getDescription().startsWith("param")
+ ) {
+
if( !visited.contains(hrn) ) {
traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
hrn,
bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
+ if( writeParamMappings ) {
+ Set df = paramIndex2id.entrySet();
+ Iterator ih = df.iterator();
+ while( ih.hasNext() ) {
+ Map.Entry meh = (Map.Entry)ih.next();
+ Integer pi = (Integer) meh.getKey();
+ 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();
}
}
- bw.write(ln.toString() + ";\n");
+ //bw.write(" "+ln.toString() + ";\n");
Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
while( heapRegionsItr.hasNext() ) {
projects / IRC.git / blobdiff