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
- 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,
+ alpha = new ReachabilitySet(
+ new TokenTuple(id,
!isSingleObject,
- TokenTuple.ARITY_ONE)
+ TokenTuple.ARITY_ONE
+ ).makeCanonical()
).makeCanonical();
} else {
- alpha = new ReachabilitySet(new TokenTupleSet()
+ alpha = new ReachabilitySet(
+ new TokenTupleSet().makeCanonical()
).makeCanonical();
}
}
// then propagate back just up the edges from hrn
ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
+
HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
edgesWithNewBeta);
+ // THIS IS A HACK--NEED TO CHANGE GENERATATION OF BETA-NEW SO THIS DOESN'T
+ // HAPPEN OTHERWISE PROPAGATION FAILS
+ if( edgeY.getBetaNew().equals( new ReachabilitySet().makeCanonical() ) ) {
+ edgeY.setBetaNew( new ReachabilitySet( new TokenTupleSet().makeCanonical() ).makeCanonical() );
+ }
+
- //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
+
+ /*
+ System.out.println( "---------------------------\n" +
+ edgeY.getBetaNew() +
+ "\nbeing pruned by\n" +
+ hrnX.getAlpha() +
+ "\nis\n" +
+ edgeY.getBetaNew().pruneBy(hrnX.getAlpha())
+ );
+ */
// create the actual reference edge hrnX.f -> hrnY
ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
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
// after tokens have been aged, reset newest node's reachability
if( hrn0.isFlagged() ) {
- hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
- new TokenTuple(hrn0)
- )
+ hrn0.setAlpha(new ReachabilitySet(
+ new TokenTupleSet(
+ new TokenTuple(hrn0).makeCanonical()
+ ).makeCanonical()
).makeCanonical()
);
} else {
- hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
+ hrn0.setAlpha(new ReachabilitySet(
+ new TokenTupleSet().makeCanonical()
).makeCanonical()
);
}
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 =
// 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);
+ 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();
+ 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);
+ paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
+ paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
for( int i = 0; i < fm.numParameters(); ++i ) {
paramToken2paramIndex.put(p_i, paramIndex);
paramIndex2paramToken.put(paramIndex, p_i);
- TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
+ TokenTuple p_i_plus = new TokenTuple(hrnParam.getID(),
true,
- TokenTuple.ARITY_MANY).makeCanonical();
- paramTokenStar2paramIndex.put(p_i_star, paramIndex);
- paramIndex2paramTokenStar.put(paramIndex, p_i_star);
+ 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
if( isStatic ) {
argTemp_i = fc.getArg(paramIndex);
} else {
- if( paramIndex == 0 ) {
+ if( paramIndex.equals( 0 ) ) {
argTemp_i = fc.getThis();
} else {
argTemp_i = fc.getArg(paramIndex - 1);
LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
paramIndex2ln.put(paramIndex, argLabel_i);
- ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
+ 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();
+ paramIndex2rewrite_d.put(paramIndex, d_i);
+
+ ReachabilitySet D_i = d_i.exhaustiveArityCombinations();
paramIndex2rewriteD.put(paramIndex, D_i);
}
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);
}
}
-
// 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);
+ 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);
+ rewriteCallerReachability(index,
+ null,
+ edgeUpstream,
+ paramIndex2rewriteK.get(index),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ paramIndex2paramToken.get(index),
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ true,
+ edgeUpstreamPlannedChanges);
edgesWithNewBeta.add(edgeUpstream);
}
}
-
// 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
// 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();
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,
+ hrnIthShadow.getAlpha(),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ bogusToken,
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ false,
+ null);
hrnIthShadow.applyAlphaNew();
}
null,
edgeCallee.getFieldDesc(),
false,
- toShadowTokens(ogCallee, edgeCallee.getBeta() )
+ toShadowTokens(ogCallee,
+ edgeCallee.getBeta() )
);
- rewriteCallerEdgeBeta(fm.numParameters(),
- bogusIndex,
- edgeNewInCallerTemplate,
- paramIndex2rewriteJ,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar,
- false,
- null);
+ rewriteCallerReachability(bogusIndex,
+ null,
+ edgeNewInCallerTemplate,
+ edgeNewInCallerTemplate.getBeta(),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ bogusToken,
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ false,
+ null);
edgeNewInCallerTemplate.applyBetaNew();
while( srcItr.hasNext() ) {
HeapRegionNode src = (HeapRegionNode) srcItr.next();
- // check that if this source node has a definite type that
- // it also has the appropriate field, otherwise prune this
- AllocationSite asSrc = src.getAllocationSite();
- if( asSrc != null ) {
- boolean foundField = false;
- TypeDescriptor tdSrc = asSrc.getType();
- if( tdSrc != null && tdSrc.isClass() ) {
- Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
- while( fieldsSrcItr.hasNext() ) {
- FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
- if( fd == edgeCallee.getFieldDesc() ) {
- foundField = true;
- break;
- }
- }
- if( !foundField ) {
- // prune this source node possibility
- continue;
- }
- }
+ if( !hasMatchingField(src, edgeCallee) ) {
+ // prune this source node possibility
+ continue;
}
Iterator dstItr = possibleCallerDsts.iterator();
while( dstItr.hasNext() ) {
HeapRegionNode dst = (HeapRegionNode) dstItr.next();
- // check if this dst node has a definite type and
- // if it matches the callee edge
- AllocationSite asDst = dst.getAllocationSite();
- if( asDst != null && edgeCallee.getFieldDesc() != null ) {
- if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) {
- continue;
- }
- if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) {
- continue;
- }
- if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
- if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) {
- continue;
- }
- }
+ if( !hasMatchingType(edgeCallee, dst) ) {
+ // prune
+ continue;
}
// otherwise the caller src and dst pair can match the edge, so make it
}
-
// 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() );
+ LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
clearReferenceEdgesFrom(lnLhsCaller, null, true);
LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
null,
edgeCallee.getFieldDesc(),
false,
- toShadowTokens(ogCallee, edgeCallee.getBeta() )
+ toShadowTokens(ogCallee,
+ edgeCallee.getBeta() )
);
- rewriteCallerEdgeBeta(fm.numParameters(),
- bogusIndex,
- edgeNewInCallerTemplate,
- paramIndex2rewriteJ,
- paramIndex2rewriteD,
- paramIndex2paramToken,
- paramIndex2paramTokenStar,
- false,
- null);
+ rewriteCallerReachability(bogusIndex,
+ null,
+ edgeNewInCallerTemplate,
+ edgeNewInCallerTemplate.getBeta(),
+ paramIndex2rewrite_d,
+ paramIndex2rewriteD,
+ bogusToken,
+ paramToken2paramIndex,
+ paramTokenPlus2paramIndex,
+ false,
+ null);
edgeNewInCallerTemplate.applyBetaNew();
while( itrHrn.hasNext() ) {
HeapRegionNode hrnCaller = itrHrn.next();
- // check if this dst node has a definite type and
- // if it matches the callee edge
- // check if this dst node has a definite type and
- // if it matches the callee edge
- AllocationSite asDst = hrnCaller.getAllocationSite();
- if( asDst != null && edgeCallee.getFieldDesc() != null ) {
- if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) {
- continue;
- }
- if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) {
- continue;
- }
- if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
- if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) {
- continue;
- }
- }
+ if( !hasMatchingType(edgeCallee, hrnCaller) ) {
+ // prune
+ continue;
}
// otherwise caller node can match callee edge, so make it
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 {
}
-
// merge the shadow nodes of allocation sites back down to normal capacity
Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
while( allocItr.hasNext() ) {
}
+ 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) {
- 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) {
+ 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);
- ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
assert rules != null;
+ assert p_i != 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 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) );
- }
+ ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
- hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
- }
+ // 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>() );
- 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;
+ Iterator<TokenTupleSet> rulesItr = rules.iterator();
+ while(rulesItr.hasNext()) {
+ TokenTupleSet rule = rulesItr.next();
- TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
- assert tokenToRewrite != null;
+ ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
- ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
+ Iterator<TokenTuple> ruleItr = rule.iterator();
+ while(ruleItr.hasNext()) {
+ TokenTuple ttCallee = ruleItr.next();
- Iterator<TokenTupleSet> ttsItr = rules.iterator();
- while( ttsItr.hasNext() ) {
- TokenTupleSet tts = ttsItr.next();
+ // compute the possibilities for rewriting this callee token
+ ReachabilitySet ttCalleeRewrites = null;
+ boolean callerSourceUsed = false;
- Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
- new Hashtable<TokenTupleSet, TokenTupleSet>();
+ 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;
- ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
- edge.getBeta(),
- true,
- forChangeSet);
+ } 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;
- 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();
+ } 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();
+
+ Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
+ while( ttCalleeRewritesItr.hasNext() ) {
+ TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
+
+ TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
+
+ if( makeChangeSet ) {
+ // in order to keep the list of source token tuple sets
+ // start with the sets used to make the partially rewritten
+ // rule up to this point
+ HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
+ assert sourceSets != null;
+
+ // make a shallow copy for possible modification
+ sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
+
+ // if we used something from the caller to rewrite it, remember
+ if( callerSourceUsed ) {
+ sourceSets.add( ttsBranch );
+ }
- ChangeTuple ct = new ChangeTuple(ttsMatch,
- ttsAdd
- ).makeCanonical();
+ // set mapping for the further rewritten rule
+ rewritten2source.put( ttsRewrittenNext, sourceSets );
+ }
+
+ rewrittenRuleWithTTCallee =
+ rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
+ }
+ }
- cts0 = cts0.union(ct);
+ // now the rewritten rule's possibilities have been extended by
+ // rewriting the current callee token, remember result
+ rewrittenRule = rewrittenRuleWithTTCallee;
}
- }
-
-
- 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();
-
- ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(),
- tts
- ).makeCanonical();
-
- cts1 = cts1.union(ctFinal);
- }
- }
+ // 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,
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_MANY).makeCanonical();
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
// get tokens for the other parameter
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_MANY).makeCanonical();
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
// get special label p_q for first parameter
ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
assert beta1 != null;
- if( beta1.containsTupleSetWithBoth(p1, p2) ) {
- return true;
- }
- if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
- return true;
- }
- if( beta1.containsTupleSetWithBoth(p1, pStar2) ) {
- return true;
- }
- if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
- return true;
- }
+ 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;
}
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_MANY).makeCanonical();
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
// get special label p_q
TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
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_MANY).makeCanonical();
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
- if( beta.containsTupleSetWithBoth(p, gs) ) {
- return true;
- }
- if( beta.containsTupleSetWithBoth(pStar, gs) ) {
- return true;
- }
- if( beta.containsTupleSetWithBoth(p, gsStar) ) {
- return true;
- }
- if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
- return true;
- }
+
+ 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 ) {
- // the other nodes of an allocation site are single, no stars
+ // the other nodes of an allocation site are single, no plus
TokenTuple gi = new TokenTuple(as.getIthOldest(i),
false,
TokenTuple.ARITY_ONE).makeCanonical();
- if( beta.containsTupleSetWithBoth(p, gi) ) {
- return true;
- }
- if( beta.containsTupleSetWithBoth(pStar, gi) ) {
- return true;
- }
+ TokenTuple giStar = new TokenTuple(as.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+ 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; }
}
return false;
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_MANY).makeCanonical();
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
// get summary node's alpha
Integer idSum1 = as1.getSummary();
true,
TokenTuple.ARITY_ONE).makeCanonical();
+ TokenTuple gsPlus2 = new TokenTuple(as2.getSummary(),
+ true,
+ TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
true,
- TokenTuple.ARITY_MANY).makeCanonical();
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
// get summary node's alpha
Integer idSum2 = as2.getSummary();
assert alphaSum2 != null;
// does either one report reachability from the other tokens?
- if( alphaSum1.containsTuple(gsStar2) ) {
- return true;
- }
- if( alphaSum2.containsTuple(gsStar1) ) {
- return true;
- }
+ if( alphaSum1.containsTuple(gsPlus2) ) { return true; }
+ if( alphaSum1.containsTuple(gsStar2) ) { return true; }
+ if( alphaSum2.containsTuple(gsPlus1) ) { return true; }
+ if( alphaSum2.containsTuple(gsStar1) ) { return true; }
- // only check non-star token if they are different sites
+ // only check ONE token if they are different sites
if( as1 != as2 ) {
- if( alphaSum1.containsTuple(gs2) ) {
- return true;
- }
- if( alphaSum2.containsTuple(gs1) ) {
- return true;
- }
+ if( alphaSum1.containsTuple(gs2) ) { return true; }
+ if( alphaSum2.containsTuple(gs1) ) { return true; }
}
false,
TokenTuple.ARITY_ONE).makeCanonical();
- if( alphaSum2.containsTuple(gi1) ) {
- return true;
- }
- if( alphaI1.containsTuple(gs2) ) {
- return true;
- }
- if( alphaI1.containsTuple(gsStar2) ) {
- return true;
- }
+ 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; }
}
// check sum1 against alloc2 nodes
false,
TokenTuple.ARITY_ONE).makeCanonical();
- if( alphaSum1.containsTuple(gi2) ) {
- return true;
- }
- if( alphaI2.containsTuple(gs1) ) {
- return true;
- }
- if( alphaI2.containsTuple(gsStar1) ) {
- return true;
- }
+ TokenTuple giStar2 = new TokenTuple(as2.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+ 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; }
// 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 ) {
continue;
TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
false,
TokenTuple.ARITY_ONE).makeCanonical();
- if( alphaI2.containsTuple(gi1) ) {
- return true;
- }
- if( alphaI1.containsTuple(gi2) ) {
- return true;
- }
+
+ TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(j),
+ false,
+ TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+ if( alphaI2.containsTuple(gi1 ) ) { return true; }
+ if( alphaI2.containsTuple(giStar1) ) { return true; }
+ if( alphaI1.containsTuple(gi2 ) ) { return true; }
+ if( alphaI1.containsTuple(giStar2) ) { return true; }
}
}
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
);
}
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers
+ boolean writeReferencers,
+ boolean writeParamMappings
) throws java.io.IOException {
writeGraph(methodDesc+"COMPLETE",
writeLabels,
labelSelect,
pruneGarbage,
- writeReferencers
+ writeReferencers,
+ writeParamMappings
);
}
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers
+ boolean writeReferencers,
+ boolean writeParamMappings
) throws java.io.IOException {
writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
writeLabels,
labelSelect,
pruneGarbage,
- writeReferencers
+ writeReferencers,
+ writeParamMappings
);
}
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,
- null,
- visited,
- writeReferencers);
+ hrn,
+ bw,
+ null,
+ visited,
+ writeReferencers);
}
}
}
-
+
bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
- 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");
+ 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