public class OwnershipGraph {
- protected static final int VISIT_HRN_WRITE_FULL = 0;
- protected static final int VISIT_HRN_WRITE_CONDENSED = 1;
+ private int allocationDepth;
+ private TypeUtil typeUtil;
+ // there was already one other very similar reason
+ // for traversing heap nodes that is no longer needed
+ // instead of writing a new heap region visitor, use
+ // the existing method with a new mode to describe what
+ // actions to take during the traversal
+ protected static final int VISIT_HRN_WRITE_FULL = 0;
- protected static int heapRegionNodeIDs = 0;
- public Hashtable<Integer, HeapRegionNode> id2hrn;
- public Hashtable<Integer, HeapRegionNode> heapRoots;
+ protected static TempDescriptor tdReturn = new TempDescriptor("_Return___");
- protected static int labelNodeIDs = 0;
- public Hashtable<TempDescriptor, LabelNode> td2ln;
- public HashSet<TempDescriptor> analysisRegionLabels;
+ public Hashtable<Integer, HeapRegionNode> id2hrn;
+ public Hashtable<TempDescriptor, LabelNode > td2ln;
+ public Hashtable<Integer, Integer > id2paramIndex;
+ public Hashtable<Integer, Integer > paramIndex2id;
+ public Hashtable<Integer, TempDescriptor> paramIndex2tdQ;
- protected Hashtable<TempDescriptor, TempDescriptor> linkedRegions;
+ public HashSet<AllocationSite> allocationSites;
- protected int newDepthK;
- public Hashtable<FlatNew, NewCluster> fn2nc;
- public OwnershipGraph( int newDepthK ) {
- id2hrn = new Hashtable<Integer, HeapRegionNode>();
- heapRoots = new Hashtable<Integer, HeapRegionNode>();
- td2ln = new Hashtable<TempDescriptor, LabelNode>();
+ public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
+ this.allocationDepth = allocationDepth;
+ this.typeUtil = typeUtil;
- analysisRegionLabels = new HashSet<TempDescriptor>();
+ id2hrn = new Hashtable<Integer, HeapRegionNode>();
+ td2ln = new Hashtable<TempDescriptor, LabelNode >();
+ id2paramIndex = new Hashtable<Integer, Integer >();
+ paramIndex2id = new Hashtable<Integer, Integer >();
+ paramIndex2tdQ = new Hashtable<Integer, TempDescriptor>();
- linkedRegions = new Hashtable<TempDescriptor, TempDescriptor>();
+ allocationSites = new HashSet <AllocationSite>();
+ }
- this.newDepthK = newDepthK;
- fn2nc = new Hashtable<FlatNew, NewCluster>();
- }
+ // label nodes are much easier to deal with than
+ // heap region nodes. Whenever there is a request
+ // for the label node that is associated with a
+ // temp descriptor we can either find it or make a
+ // new one and return it. This is because temp
+ // descriptors are globally unique and every label
+ // node is mapped to exactly one temp descriptor.
+ protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
+ assert td != null;
- protected void addReferenceEdge( OwnershipNode referencer,
- HeapRegionNode referencee,
- ReferenceEdgeProperties rep ) {
- assert referencer != null;
- assert referencee != null;
- referencer.addReferencedRegion( referencee, rep );
- referencee.addReferencer( referencer );
+ if( !td2ln.containsKey(td) ) {
+ td2ln.put(td, new LabelNode(td) );
}
- protected void removeReferenceEdge( OwnershipNode referencer,
- HeapRegionNode referencee ) {
- assert referencer != null;
- assert referencee != null;
- assert referencer.getReferenceTo( referencee ) != null;
- assert referencee.isReferencedBy( referencer );
-
- referencer.removeReferencedRegion( referencee );
- referencee.removeReferencer( referencer );
+ return td2ln.get(td);
+ }
+
+
+ // the reason for this method is to have the option
+ // creating new heap regions with specific IDs, or
+ // duplicating heap regions with specific IDs (especially
+ // in the merge() operation) or to create new heap
+ // regions with a new unique ID.
+ protected HeapRegionNode
+ createNewHeapRegionNode(Integer id,
+ boolean isSingleObject,
+ boolean isFlagged,
+ boolean isNewSummary,
+ boolean isParameter,
+ AllocationSite allocSite,
+ ReachabilitySet alpha,
+ String description) {
+
+ if( id == null ) {
+ id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
}
- protected void clearReferenceEdgesFrom( OwnershipNode referencer ) {
- assert referencer != null;
+ if( alpha == null ) {
+ if( isFlagged || isParameter ) {
+ alpha = new ReachabilitySet(new TokenTuple(id,
+ !isSingleObject,
+ TokenTuple.ARITY_ONE)
+ ).makeCanonical();
+ } else {
+ alpha = new ReachabilitySet(new TokenTupleSet()
+ ).makeCanonical();
+ }
+ }
- // get a copy of the table to iterate over, otherwise
- // we will be trying to take apart the table as we
- // are iterating over it, which won't work
- Iterator i = referencer.setIteratorToReferencedRegionsClone();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- HeapRegionNode referencee = (HeapRegionNode) me.getKey();
- removeReferenceEdge( referencer, referencee );
- }
+ HeapRegionNode hrn = new HeapRegionNode(id,
+ isSingleObject,
+ isFlagged,
+ isNewSummary,
+ allocSite,
+ alpha,
+ description);
+ id2hrn.put(id, hrn);
+ return hrn;
+ }
+
+
+
+ ////////////////////////////////////////////////
+ //
+ // Low-level referencee and referencer methods
+ //
+ // These methods provide the lowest level for
+ // creating references between ownership nodes
+ // and handling the details of maintaining both
+ // list of referencers and referencees.
+ //
+ ////////////////////////////////////////////////
+ protected void addReferenceEdge(OwnershipNode referencer,
+ HeapRegionNode referencee,
+ ReferenceEdge edge) {
+ assert referencer != null;
+ assert referencee != null;
+ assert edge != null;
+ assert edge.getSrc() == referencer;
+ assert edge.getDst() == referencee;
+
+ referencer.addReferencee(edge);
+ referencee.addReferencer(edge);
+ }
+
+ protected void removeReferenceEdge(OwnershipNode referencer,
+ HeapRegionNode referencee,
+ FieldDescriptor fieldDesc) {
+ assert referencer != null;
+ assert referencee != null;
+
+ ReferenceEdge edge = referencer.getReferenceTo(referencee,
+ fieldDesc);
+ assert edge != null;
+ assert edge == referencee.getReferenceFrom(referencer,
+ fieldDesc);
+
+ referencer.removeReferencee(edge);
+ referencee.removeReferencer(edge);
+ }
+
+ protected void clearReferenceEdgesFrom(OwnershipNode referencer,
+ FieldDescriptor fieldDesc,
+ boolean removeAll) {
+ assert referencer != null;
+
+ // get a copy of the set to iterate over, otherwise
+ // we will be trying to take apart the set as we
+ // are iterating over it, which won't work
+ Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
+ while( i.hasNext() ) {
+ ReferenceEdge edge = i.next();
+
+ if( removeAll || edge.getFieldDesc() == fieldDesc ) {
+ HeapRegionNode referencee = edge.getDst();
+
+ removeReferenceEdge(referencer,
+ referencee,
+ edge.getFieldDesc() );
+ }
+ }
+ }
+
+ protected void clearReferenceEdgesTo(HeapRegionNode referencee,
+ FieldDescriptor fieldDesc,
+ boolean removeAll) {
+ assert referencee != null;
+
+ // get a copy of the set to iterate over, otherwise
+ // we will be trying to take apart the set as we
+ // are iterating over it, which won't work
+ Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
+ while( i.hasNext() ) {
+ ReferenceEdge edge = i.next();
+
+ if( removeAll || edge.getFieldDesc() == fieldDesc ) {
+ OwnershipNode referencer = edge.getSrc();
+ removeReferenceEdge(referencer,
+ referencee,
+ edge.getFieldDesc() );
+ }
}
+ }
- protected void clearReferenceEdgesTo( HeapRegionNode referencee ) {
- assert referencee != null;
- // get a copy of the table to iterate over, otherwise
- // we will be trying to take apart the table as we
- // are iterating over it, which won't work
- Iterator i = referencee.iteratorToReferencersClone();
- while( i.hasNext() ) {
- OwnershipNode referencer = (OwnershipNode) i.next();
- removeReferenceEdge( referencer, referencee );
- }
- }
-
+ protected void propagateTokensOverNodes(HeapRegionNode nPrime,
+ ChangeTupleSet c0,
+ HashSet<HeapRegionNode> nodesWithNewAlpha,
+ HashSet<ReferenceEdge> edgesWithNewBeta) {
+
+ HashSet<HeapRegionNode> todoNodes
+ = new HashSet<HeapRegionNode>();
+ todoNodes.add(nPrime);
+
+ HashSet<ReferenceEdge> todoEdges
+ = new HashSet<ReferenceEdge>();
+ Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
+ = new Hashtable<HeapRegionNode, ChangeTupleSet>();
+ nodePlannedChanges.put(nPrime, c0);
- ////////////////////////////////////////////////////
- //
- // New Reference Methods
- //
- // The destination in an assignment statement is
- // going to have new references. The method of
- // determining the references depends on the type
- // of the FlatNode assignment and the predicates
- // of the nodes and edges involved.
- //
- ////////////////////////////////////////////////////
- public void assignTempToTemp( TempDescriptor src,
- TempDescriptor dst ) {
- LabelNode srcln = getLabelNodeFromTemp( src );
- LabelNode dstln = getLabelNodeFromTemp( dst );
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
+ = new Hashtable<ReferenceEdge, ChangeTupleSet>();
- clearReferenceEdgesFrom( dstln );
- HeapRegionNode newReferencee = null;
- Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
- while( srcRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) srcRegionsItr.next();
- newReferencee = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
- addReferenceEdge( dstln, newReferencee, rep.copy() );
+ while( !todoNodes.isEmpty() ) {
+ HeapRegionNode n = todoNodes.iterator().next();
+ ChangeTupleSet C = nodePlannedChanges.get(n);
+
+ Iterator itrC = C.iterator();
+ while( itrC.hasNext() ) {
+ ChangeTuple c = (ChangeTuple) itrC.next();
+
+ if( n.getAlpha().contains(c.getSetToMatch() ) ) {
+ ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
+ n.setAlphaNew(n.getAlphaNew().union(withChange) );
+ nodesWithNewAlpha.add(n);
}
- }
+ }
- public void assignTempToField( TempDescriptor src,
- TempDescriptor dst,
- FieldDescriptor fd ) {
- LabelNode srcln = getLabelNodeFromTemp( src );
- LabelNode dstln = getLabelNodeFromTemp( dst );
+ Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
+ while( referItr.hasNext() ) {
+ ReferenceEdge edge = referItr.next();
+ todoEdges.add(edge);
- clearReferenceEdgesFrom( dstln );
+ if( !edgePlannedChanges.containsKey(edge) ) {
+ edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
+ }
- HeapRegionNode hrn = null;
- Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
- while( srcRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) srcRegionsItr.next();
- hrn = (HeapRegionNode) me.getKey();
+ edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
+ }
- HeapRegionNode hrnOneHop = null;
- Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
- while( hrnRegionsItr.hasNext() ) {
- Map.Entry meH = (Map.Entry) hrnRegionsItr.next();
- hrnOneHop = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
+ Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
+ while( refeeItr.hasNext() ) {
+ ReferenceEdge edgeF = refeeItr.next();
+ HeapRegionNode m = edgeF.getDst();
- addReferenceEdge( dstln, hrnOneHop, rep.copy() );
- }
+ ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
+
+ Iterator<ChangeTuple> itrCprime = C.iterator();
+ while( itrCprime.hasNext() ) {
+ ChangeTuple c = itrCprime.next();
+ if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
+ changesToPass = changesToPass.union(c);
+ }
}
- }
- public void assignFieldToTemp( TempDescriptor src,
- TempDescriptor dst,
- FieldDescriptor fd ) {
- LabelNode srcln = getLabelNodeFromTemp( src );
- LabelNode dstln = getLabelNodeFromTemp( dst );
+ if( !changesToPass.isEmpty() ) {
+ if( !nodePlannedChanges.containsKey(m) ) {
+ nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
+ }
- HeapRegionNode hrn = null;
- Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
- while( dstRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) dstRegionsItr.next();
- hrn = (HeapRegionNode) me.getKey();
+ ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
- HeapRegionNode hrnSrc = null;
- Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
- while( srcRegionsItr.hasNext() ) {
- Map.Entry meS = (Map.Entry) srcRegionsItr.next();
- hrnSrc = (HeapRegionNode) meS.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meS.getValue();
+ if( !changesToPass.isSubset(currentChanges) ) {
- addReferenceEdge( hrn, hrnSrc, rep.copy() );
- }
- }
+ nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
+ todoNodes.add(m);
+ }
+ }
+ }
+
+ todoNodes.remove(n);
}
- ////////////////////////////////////////////////////
- // end new reference methods
- ////////////////////////////////////////////////////
+ propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
+ }
+
+
+ protected void propagateTokensOverEdges(
+ HashSet<ReferenceEdge> todoEdges,
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
+ HashSet<ReferenceEdge> edgesWithNewBeta) {
- protected HeapRegionNode
- createNewHeapRegionNode( Integer id,
- boolean isSingleObject,
- boolean isFlagged,
- boolean isNewSummary ) {
- if( id == null ) {
- id = new Integer( heapRegionNodeIDs );
- ++heapRegionNodeIDs;
+ while( !todoEdges.isEmpty() ) {
+ ReferenceEdge edgeE = todoEdges.iterator().next();
+ todoEdges.remove(edgeE);
+
+ if( !edgePlannedChanges.containsKey(edgeE) ) {
+ edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet C = edgePlannedChanges.get(edgeE);
+
+ ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
+
+ Iterator<ChangeTuple> itrC = C.iterator();
+ while( itrC.hasNext() ) {
+ ChangeTuple c = itrC.next();
+ if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
+ ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
+ edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
+ edgesWithNewBeta.add(edgeE);
+ changesToPass = changesToPass.union(c);
}
+ }
+
+ OwnershipNode onSrc = edgeE.getSrc();
+
+ if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
+ HeapRegionNode n = (HeapRegionNode) onSrc;
- HeapRegionNode hrn = new HeapRegionNode( id,
- isSingleObject,
- isFlagged,
- isNewSummary );
- id2hrn.put( id, hrn );
- return hrn;
+ Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
+ while( referItr.hasNext() ) {
+ ReferenceEdge edgeF = referItr.next();
+
+ if( !edgePlannedChanges.containsKey(edgeF) ) {
+ edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
+
+ if( !changesToPass.isSubset(currentChanges) ) {
+ todoEdges.add(edgeF);
+ edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
+ }
+ }
+ }
+ }
+ }
+
+
+ ////////////////////////////////////////////////////
+ //
+ // Assignment Operation Methods
+ //
+ // These methods are high-level operations for
+ // modeling program assignment statements using
+ // the low-level reference create/remove methods
+ // above.
+ //
+ // The destination in an assignment statement is
+ // going to have new references. The method of
+ // determining the references depends on the type
+ // of the FlatNode assignment and the predicates
+ // of the nodes and edges involved.
+ //
+ ////////////////////////////////////////////////////
+ public void assignTempXEqualToTempY(TempDescriptor x,
+ TempDescriptor y) {
+
+ LabelNode lnX = getLabelNodeFromTemp(x);
+ LabelNode lnY = getLabelNodeFromTemp(y);
+
+ clearReferenceEdgesFrom(lnX, null, true);
+
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode referencee = edgeY.getDst();
+ ReferenceEdge edgeNew = edgeY.copy();
+ edgeNew.setSrc(lnX);
+
+ addReferenceEdge(lnX, referencee, edgeNew);
}
+ }
+
+ public void assignTempXEqualToTempYFieldF(TempDescriptor x,
+ TempDescriptor y,
+ FieldDescriptor f) {
+ LabelNode lnX = getLabelNodeFromTemp(x);
+ LabelNode lnY = getLabelNodeFromTemp(y);
- public void parameterAllocation( TempDescriptor td ) {
- assert td != null;
+ clearReferenceEdgesFrom(lnX, null, true);
- LabelNode lnParam = getLabelNodeFromTemp( td );
- HeapRegionNode hrn = createNewHeapRegionNode( null, false, true, false );
- heapRoots.put( hrn.getID(), hrn );
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+ ReachabilitySet betaY = edgeY.getBeta();
- addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false ) );
- addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false ) );
+ Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
+ while( itrHrnFhrn.hasNext() ) {
+ ReferenceEdge edgeHrn = itrHrnFhrn.next();
+ HeapRegionNode hrnHrn = edgeHrn.getDst();
+ ReachabilitySet betaHrn = edgeHrn.getBeta();
+
+ if( edgeHrn.getFieldDesc() == null ||
+ edgeHrn.getFieldDesc() == f ) {
+
+ ReferenceEdge edgeNew = new ReferenceEdge(lnX,
+ hrnHrn,
+ f,
+ false,
+ betaY.intersection(betaHrn) );
+
+ addReferenceEdge(lnX, hrnHrn, edgeNew);
+ }
+ }
}
-
- public void assignTempToNewAllocation( TempDescriptor td, FlatNew fn ) {
- assert td != null;
- assert fn != null;
+ }
- NewCluster nc = getNewClusterFromFlatNew( fn );
- // move existing references down the line toward
- // the oldest element
- for( int i = newDepthK - 2; i >= 0; --i ) {
- // move references from the ith oldest to the i+1 oldest
- HeapRegionNode hrnIthOld = nc.getIthOldest( i );
- HeapRegionNode hrnIp1Old = nc.getIthOldest( i + 1 );
+ public void assignTempXFieldFEqualToTempY(TempDescriptor x,
+ FieldDescriptor f,
+ TempDescriptor y) {
+ LabelNode lnX = getLabelNodeFromTemp(x);
+ LabelNode lnY = getLabelNodeFromTemp(y);
- // clear i + 1 references in and out, unless it is the
- // oldest node which keeps everything
- if( !(i + 1 == newDepthK - 1) ) {
- clearReferenceEdgesFrom( hrnIp1Old );
- clearReferenceEdgesTo ( hrnIp1Old );
- }
+ HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
+ HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
- // copy each edge in and out of i to i + 1
- HeapRegionNode hrnReferencee = null;
- Iterator itrReferencee = hrnIthOld.setIteratorToReferencedRegions();
- while( itrReferencee.hasNext() ) {
- Map.Entry me = (Map.Entry) itrReferencee.next();
- hrnReferencee = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
-
- addReferenceEdge( hrnIp1Old, hrnReferencee, rep.copy() );
- }
+ Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
+ while( itrXhrn.hasNext() ) {
+ ReferenceEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
+ ReachabilitySet betaX = edgeX.getBeta();
- OwnershipNode onReferencer = null;
- Iterator itrReferencer = hrnIthOld.iteratorToReferencers();
- while( itrReferencer.hasNext() ) {
- onReferencer = (OwnershipNode) itrReferencer.next();
+ ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
- ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnIthOld );
- assert rep != null;
+ Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ ReferenceEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+ ReachabilitySet O = edgeY.getBeta();
- addReferenceEdge( onReferencer, hrnIp1Old, rep.copy() );
- }
+
+ // propagate tokens over nodes starting from hrnSrc, and it will
+ // take care of propagating back up edges from any touched nodes
+ ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
+ propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
+
+
+ // then propagate back just up the edges from hrn
+ ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
+
+ HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
+
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
+ new Hashtable<ReferenceEdge, ChangeTupleSet>();
+
+ Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
+ while( referItr.hasNext() ) {
+ ReferenceEdge edgeUpstream = referItr.next();
+ todoEdges.add(edgeUpstream);
+ edgePlannedChanges.put(edgeUpstream, Cx);
}
- HeapRegionNode hrnNewest = nc.getIthOldest( 0 );
- ReferenceEdgeProperties rep = new ReferenceEdgeProperties( true );
- LabelNode dst = getLabelNodeFromTemp( td );
+ propagateTokensOverEdges(todoEdges,
+ edgePlannedChanges,
+ edgesWithNewBeta);
- // clear all references in and out of newest node
- clearReferenceEdgesFrom( hrnNewest );
- clearReferenceEdgesTo ( hrnNewest );
- // finally assign the temp descriptor to the newest
- // node in the new cluster
- addReferenceEdge( dst, hrnNewest, rep );
- }
- protected NewCluster getNewClusterFromFlatNew( FlatNew fn ) {
- if( !fn2nc.containsKey( fn ) ) {
- NewCluster nc = new NewCluster( newDepthK );
+ //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
+
+ // create the actual reference edge hrnX.f -> hrnY
+ ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
+ hrnY,
+ f,
+ false,
+ edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
+ //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
+ );
+ addReferenceEdge(hrnX, hrnY, edgeNew);
- // the first k-1 nodes are single objects
- for( int i = 0; i < newDepthK - 1; ++i ) {
- HeapRegionNode hrn = createNewHeapRegionNode( null, true, false, false );
- nc.setIthOldest( i, hrn );
+ /*
+ 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 );
}
- // the kth node is a newSummaryNode
- HeapRegionNode hrnNewSummary = createNewHeapRegionNode( null, false, false, true );
- nc.setIthOldest( newDepthK - 1, hrnNewSummary );
+ addReferenceEdge( hrnX, hrnY, edgeNew );
- fn2nc.put( fn, nc );
- }
+ } 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 );
- return fn2nc.get( fn );
+ 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 );
+ }
+ }
+ */
+ }
}
+ Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
+ while( nodeItr.hasNext() ) {
+ nodeItr.next().applyAlphaNew();
+ }
+
+ Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
+ while( edgeItr.hasNext() ) {
+ edgeItr.next().applyBetaNew();
+ }
+ }
+
+
+ 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);
+
+ // this is a non-program-accessible label that picks up beta
+ // info to be used for fixing a caller of this method
+ TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
+ LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
+
+ // keep track of heap regions that were created for
+ // parameter labels, the index of the parameter they
+ // are for is important when resolving method calls
+ Integer newID = hrn.getID();
+ assert !id2paramIndex.containsKey(newID);
+ assert !id2paramIndex.containsValue(paramIndex);
+ id2paramIndex.put(newID, paramIndex);
+ paramIndex2id.put(paramIndex, newID);
+ paramIndex2tdQ.put(paramIndex, tdParamQ);
+
+ ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
+ true,
+ TokenTuple.ARITY_ONE) );
+
+ // heap regions for parameters are always multiple object (see above)
+ // and have a reference to themselves, because we can't know the
+ // structure of memory that is passed into the method. We're assuming
+ // the worst here.
+
+ ReferenceEdge edgeFromLabel =
+ new ReferenceEdge(lnParam, hrn, null, false, beta);
+
+ ReferenceEdge edgeFromLabelQ =
+ new ReferenceEdge(lnParamQ, hrn, null, false, beta);
+
+ ReferenceEdge edgeReflexive =
+ new ReferenceEdge(hrn, hrn, null, true, beta);
+
+ addReferenceEdge(lnParam, hrn, edgeFromLabel);
+ addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
+ addReferenceEdge(hrn, hrn, edgeReflexive);
+ }
+
+
+ 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;
+
+ age(as);
+
+ // after the age operation the newest (or zero-ith oldest)
+ // node associated with the allocation site should have
+ // no references to it as if it were a newly allocated
+ // heap region, so make a reference to it to complete
+ // this operation
+
+ Integer idNewest = as.getIthOldest(0);
+ HeapRegionNode hrnNewest = id2hrn.get(idNewest);
+ assert hrnNewest != null;
+
+ LabelNode lnX = getLabelNodeFromTemp(x);
+ clearReferenceEdgesFrom(lnX, null, true);
+
+ ReferenceEdge edgeNew =
+ new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
+
+ addReferenceEdge(lnX, hrnNewest, edgeNew);
+ }
+
+
+ // use the allocation site (unique to entire analysis) to
+ // locate the heap region nodes in this ownership graph
+ // that should be aged. The process models the allocation
+ // of new objects and collects all the oldest allocations
+ // in a summary node to allow for a finite analysis
+ //
+ // There is an additional property of this method. After
+ // running it on a particular ownership graph (many graphs
+ // may have heap regions related to the same allocation site)
+ // the heap region node objects in this ownership graph will be
+ // allocated. Therefore, after aging a graph for an allocation
+ // site, attempts to retrieve the heap region nodes using the
+ // integer id's contained in the allocation site should always
+ // return non-null heap regions.
+ public void age(AllocationSite as) {
+
+ // aging adds this allocation site to the graph's
+ // list of sites that exist in the graph, or does
+ // nothing if the site is already in the list
+ allocationSites.add(as);
+
+ // get the summary node for the allocation site in the context
+ // of this particular ownership graph
+ HeapRegionNode hrnSummary = getSummaryNode(as);
+
+ // merge oldest node into summary
+ Integer idK = as.getOldest();
+ HeapRegionNode hrnK = id2hrn.get(idK);
+ mergeIntoSummary(hrnK, hrnSummary);
+
+ // move down the line of heap region nodes
+ // clobbering the ith and transferring all references
+ // to and from i-1 to node i. Note that this clobbers
+ // the oldest node (hrnK) that was just merged into
+ // the summary
+ for( int i = allocationDepth - 1; i > 0; --i ) {
+
+ // move references from the i-1 oldest to the ith oldest
+ Integer idIth = as.getIthOldest(i);
+ HeapRegionNode hrnI = id2hrn.get(idIth);
+ Integer idImin1th = as.getIthOldest(i - 1);
+ HeapRegionNode hrnImin1 = id2hrn.get(idImin1th);
+
+ transferOnto(hrnImin1, hrnI);
+ }
+
+ // as stated above, the newest node should have had its
+ // references moved over to the second oldest, so we wipe newest
+ // in preparation for being the new object to assign something to
+ Integer id0th = as.getIthOldest(0);
+ HeapRegionNode hrn0 = id2hrn.get(id0th);
+ assert hrn0 != null;
+ // clear all references in and out of newest node
+ clearReferenceEdgesFrom(hrn0, null, true);
+ clearReferenceEdgesTo(hrn0, null, true);
- public void addAnalysisRegion( TempDescriptor td ) {
- assert td != null;
- analysisRegionLabels.add( td );
+
+ // now tokens in reachability sets need to "age" also
+ 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() ) {
+ ageTokens(as, itrEdges.next() );
+ }
}
- // This method gives an existing label node for a temp
- // descriptor or creates one if it has not been requested
- // yet. The system is simple because temp descriptors and
- // label nodes have a one-to-one mapping and no special
- // predicates
- protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) {
- assert td != null;
+ Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
+ while( itrAllHRNodes.hasNext() ) {
+ Map.Entry me = (Map.Entry)itrAllHRNodes.next();
+ HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
- if( !td2ln.containsKey( td ) ) {
- Integer id = new Integer( labelNodeIDs );
- td2ln.put( td, new LabelNode( td ) );
- ++labelNodeIDs;
- }
+ ageTokens(as, hrnToAge);
- return td2ln.get( td );
+ Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
+ while( itrEdges.hasNext() ) {
+ ageTokens(as, itrEdges.next() );
+ }
}
+ // after tokens have been aged, reset newest node's reachability
+ if( hrn0.isFlagged() ) {
+ hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
+ new TokenTuple(hrn0)
+ )
+ ).makeCanonical()
+ );
+ } else {
+ hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
+ ).makeCanonical()
+ );
+ }
+ }
+
+
+ protected HeapRegionNode getSummaryNode(AllocationSite as) {
+
+ Integer idSummary = as.getSummary();
+ HeapRegionNode hrnSummary = id2hrn.get(idSummary);
+
+ // If this is null then we haven't touched this allocation site
+ // in the context of the current ownership graph, so allocate
+ // heap region nodes appropriate for the entire allocation site.
+ // This should only happen once per ownership graph per allocation site,
+ // and a particular integer id can be used to locate the heap region
+ // in different ownership graphs that represents the same part of an
+ // allocation site.
+ if( hrnSummary == null ) {
+
+ boolean hasFlags = false;
+ if( as.getType().isClass() ) {
+ hasFlags = as.getType().getClassDesc().hasFlags();
+ }
+
+ hrnSummary = createNewHeapRegionNode(idSummary,
+ false,
+ hasFlags,
+ true,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\nsummary");
+
+ for( int i = 0; i < as.getAllocationDepth(); ++i ) {
+ Integer idIth = as.getIthOldest(i);
+ assert !id2hrn.containsKey(idIth);
+ createNewHeapRegionNode(idIth,
+ true,
+ hasFlags,
+ false,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\n" + i + " oldest");
+ }
+ }
- ////////////////////////////////////////////////////
- // in merge() and equals() methods the suffix A
- // represents the passed in graph and the suffix
- // B refers to the graph in this object
- ////////////////////////////////////////////////////
+ return hrnSummary;
+ }
+
+
+ protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
+
+ Integer idShadowSummary = as.getSummaryShadow();
+ HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
+
+ if( hrnShadowSummary == null ) {
+
+ boolean hasFlags = false;
+ if( as.getType().isClass() ) {
+ hasFlags = as.getType().getClassDesc().hasFlags();
+ }
+
+ hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
+ false,
+ hasFlags,
+ true,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\nshadowSum");
+
+ for( int i = 0; i < as.getAllocationDepth(); ++i ) {
+ Integer idShadowIth = as.getIthOldestShadow(i);
+ assert !id2hrn.containsKey(idShadowIth);
+ createNewHeapRegionNode(idShadowIth,
+ true,
+ hasFlags,
+ false,
+ false,
+ as,
+ null,
+ as + "\\n" + as.getType() + "\\n" + i + " shadow");
+ }
+ }
- public void merge( OwnershipGraph og ) {
- mergeOwnershipNodes ( og );
- mergeReferenceEdges ( og );
- mergeHeapRoots ( og );
- mergeAnalysisRegions( og );
- mergeNewClusters ( og );
+ return hrnShadowSummary;
+ }
+
+
+ protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
+ assert hrnSummary.isNewSummary();
+
+ // transfer references _from_ hrn over to hrnSummary
+ Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
+ while( itrReferencee.hasNext() ) {
+ ReferenceEdge edge = itrReferencee.next();
+ ReferenceEdge edgeMerged = edge.copy();
+ edgeMerged.setSrc(hrnSummary);
+
+ HeapRegionNode hrnReferencee = edge.getDst();
+ ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
+
+ if( edgeSummary == null ) {
+ // the merge is trivial, nothing to be done
+ } else {
+ // otherwise an edge from the referencer to hrnSummary exists already
+ // and the edge referencer->hrn should be merged with it
+ edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
+ }
+
+ addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
}
- protected void mergeOwnershipNodes( OwnershipGraph og ) {
- Set sA = og.id2hrn.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- Integer idA = (Integer) meA.getKey();
- HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
-
- // if this graph doesn't have a node the
- // incoming graph has, allocate it
- if( !id2hrn.containsKey( idA ) ) {
- HeapRegionNode hrnB = hrnA.copy();
- id2hrn.put( idA, hrnB );
- }
- }
+ // next transfer references _to_ hrn over to hrnSummary
+ Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
+ while( itrReferencer.hasNext() ) {
+ ReferenceEdge edge = itrReferencer.next();
+ ReferenceEdge edgeMerged = edge.copy();
+ edgeMerged.setDst(hrnSummary);
+
+ OwnershipNode onReferencer = edge.getSrc();
+ ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
+
+ if( edgeSummary == null ) {
+ // the merge is trivial, nothing to be done
+ } else {
+ // otherwise an edge from the referencer to alpha_S exists already
+ // and the edge referencer->alpha_K should be merged with it
+ edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
+ }
+
+ addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
+ }
- // now add any label nodes that are in graph B but
- // not in A
- sA = og.td2ln.entrySet();
- iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- TempDescriptor tdA = (TempDescriptor) meA.getKey();
- LabelNode lnA = (LabelNode) meA.getValue();
-
- // if the label doesn't exist in B, allocate and add it
- LabelNode lnB = getLabelNodeFromTemp( tdA );
- }
+ // then merge hrn reachability into hrnSummary
+ hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
+ }
+
+
+ protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
+
+ // clear references in and out of node i
+ clearReferenceEdgesFrom(hrnB, null, true);
+ clearReferenceEdgesTo(hrnB, null, true);
+
+ // copy each edge in and out of A to B
+ Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
+ while( itrReferencee.hasNext() ) {
+ ReferenceEdge edge = itrReferencee.next();
+ HeapRegionNode hrnReferencee = edge.getDst();
+ ReferenceEdge edgeNew = edge.copy();
+ edgeNew.setSrc(hrnB);
+
+ addReferenceEdge(hrnB, hrnReferencee, edgeNew);
}
- protected void mergeReferenceEdges( OwnershipGraph og ) {
- // there is a data structure for storing label nodes
- // retireved by temp descriptors, and a data structure
- // for stroing heap region nodes retrieved by integer
- // ids. Because finding edges requires interacting
- // with these disparate data structures frequently the
- // process is nearly duplicated, one for each
-
- // heap regions
- Set sA = og.id2hrn.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- Integer idA = (Integer) meA.getKey();
- HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
-
- HeapRegionNode hrnChildA = null;
- Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildA = hrnChildA.getID();
-
- // at this point we know an edge in graph A exists
- // idA -> idChildA, does this exist in B?
- boolean edgeFound = false;
- assert id2hrn.containsKey( idA );
- HeapRegionNode hrnB = id2hrn.get( idA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meC.getKey();
-
- if( hrnChildB.equals( idChildA ) ) {
- edgeFound = true;
- }
- }
-
- // if the edge from A was not found in B,
- // add it to B.
- if( !edgeFound ) {
- assert id2hrn.containsKey( idChildA );
- hrnChildB = id2hrn.get( idChildA );
- ReferenceEdgeProperties repB = repA.copy();
- addReferenceEdge( hrnB, hrnChildB, repB );
- }
- // otherwise, the edge already existed in both graphs.
- // if this is the case, check to see whether the isUnique
- // predicate of the edges might change
- else
- {
-
- }
- }
- }
+ Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
+ while( itrReferencer.hasNext() ) {
+ ReferenceEdge edge = itrReferencer.next();
+ OwnershipNode onReferencer = edge.getSrc();
+ ReferenceEdge edgeNew = edge.copy();
+ edgeNew.setDst(hrnB);
+
+ addReferenceEdge(onReferencer, hrnB, edgeNew);
+ }
+
+ // replace hrnB reachability with hrnA's
+ hrnB.setAlpha(hrnA.getAlpha() );
+ }
+
+
+ protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
+ edge.setBeta(edge.getBeta().ageTokens(as) );
+ }
+
+ protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
+ hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
+ }
+
- // and then again with label nodes
- sA = og.td2ln.entrySet();
- iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- TempDescriptor tdA = (TempDescriptor) meA.getKey();
- LabelNode lnA = (LabelNode) meA.getValue();
-
- HeapRegionNode hrnChildA = null;
- Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
-
- Integer idChildA = hrnChildA.getID();
-
- // at this point we know an edge in graph A exists
- // tdA -> idChildA, does this exist in B?
- boolean edgeFound = false;
- assert td2ln.containsKey( tdA );
- LabelNode lnB = td2ln.get( tdA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry meC = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meC.getKey();
-
- if( hrnChildB.equals( idChildA ) ) {
- edgeFound = true;
- }
- }
-
- // if the edge from A was not found in B,
- // add it to B.
- if( !edgeFound ) {
- assert id2hrn.containsKey( idChildA );
- hrnChildB = id2hrn.get( idChildA );
- ReferenceEdgeProperties repB = repA.copy();
- addReferenceEdge( lnB, hrnChildB, repB );
- }
- // otherwise, the edge already existed in both graphs.
- // if this is the case, check to see whether the isUnique
- // predicate of the edges might change
- else
- {
-
- }
- }
+ public void resolveMethodCall(FlatCall fc,
+ boolean isStatic,
+ FlatMethod fm,
+ OwnershipGraph ogCallee) {
+
+ // define rewrite rules and other structures to organize
+ // data by parameter/argument index
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
+ new Hashtable<Integer, ReachabilitySet>();
+
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
+ new Hashtable<Integer, ReachabilitySet>();
+
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
+ new Hashtable<Integer, ReachabilitySet>();
+
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
+ new Hashtable<Integer, ReachabilitySet>();
+
+ // helpful structures
+ Hashtable<TokenTuple, Integer> paramToken2paramIndex =
+ new Hashtable<TokenTuple, Integer>();
+
+ Hashtable<Integer, TokenTuple> paramIndex2paramToken =
+ new Hashtable<Integer, TokenTuple>();
+
+ Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
+ new Hashtable<TokenTuple, Integer>();
+
+ Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
+ new Hashtable<Integer, TokenTuple>();
+
+ Hashtable<Integer, LabelNode> paramIndex2ln =
+ new Hashtable<Integer, LabelNode>();
+
+ Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
+ new Hashtable<Integer, HashSet<HeapRegionNode> >();
+
+
+ // 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);
+
+
+ for( int i = 0; i < fm.numParameters(); ++i ) {
+ Integer paramIndex = new Integer(i);
+
+ assert ogCallee.paramIndex2id.containsKey(paramIndex);
+ Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
+
+ assert ogCallee.id2hrn.containsKey(idParam);
+ HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
+ assert hrnParam != null;
+ paramIndex2rewriteH.put(paramIndex,
+
+ toShadowTokens(ogCallee, hrnParam.getAlpha() )
+ );
+
+ ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
+ assert edgeReflexive_i != null;
+ paramIndex2rewriteJ.put(paramIndex,
+ toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
+ );
+
+ TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
+ assert tdParamQ != null;
+ LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
+ assert lnParamQ != 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);
+
+ // 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);
+ } else {
+ if( paramIndex == 0 ) {
+ argTemp_i = fc.getThis();
+ } else {
+ argTemp_i = fc.getArg(paramIndex - 1);
}
+ }
+
+ // in non-static methods there is a "this" pointer
+ // that should be taken into account
+ if( isStatic ) {
+ assert fc.numArgs() == fm.numParameters();
+ } else {
+ assert fc.numArgs() + 1 == fm.numParameters();
+ }
+
+ 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.exhaustiveArityCombinations();
+
+ paramIndex2rewriteD.put(paramIndex, D_i);
}
-
- protected void mergeHeapRoots( OwnershipGraph og ) {
- Set sA = og.heapRoots.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- Integer idA = (Integer) meA.getKey();
- HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
-
- if( !heapRoots.containsKey( idA ) ) {
- assert id2hrn.containsKey( idA );
- HeapRegionNode hrnB = id2hrn.get( idA );
- heapRoots.put( idA, hrnB );
+
+
+ HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
+ HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
+
+ HashSet<ReferenceEdge> edgesReachable = new HashSet<ReferenceEdge>();
+ HashSet<ReferenceEdge> edgesUpstream = new HashSet<ReferenceEdge>();
+
+ Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
+ while( lnArgItr.hasNext() ) {
+ Map.Entry me = (Map.Entry)lnArgItr.next();
+ Integer index = (Integer) me.getKey();
+ LabelNode lnArg_i = (LabelNode) me.getValue();
+
+ // rewrite alpha for the nodes reachable from argument label i
+ HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
+ HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
+
+ // to find all reachable nodes, start with label referencees
+ Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
+ while( edgeArgItr.hasNext() ) {
+ ReferenceEdge edge = edgeArgItr.next();
+ 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);
+
+ Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+
+ if( !reachableNodes.contains(edge.getDst() ) ) {
+ todoNodes.add(edge.getDst() );
+ }
+ }
+ }
+
+ // save for later
+ paramIndex2reachableCallerNodes.put(index, reachableNodes);
+
+ // now iterate over reachable nodes to update their alpha, and
+ // classify edges found as "argument reachable" or "upstream"
+ Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
+ while( hrnItr.hasNext() ) {
+ HeapRegionNode hrn = hrnItr.next();
+
+ rewriteCallerNodeAlpha(fm.numParameters(),
+ index,
+ hrn,
+ paramIndex2rewriteH,
+ paramIndex2rewriteD,
+ paramIndex2paramToken,
+ paramIndex2paramTokenStar);
+
+ 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
+ Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+
+ OwnershipNode on = edge.getSrc();
+
+ if( on instanceof LabelNode ) {
+
+ LabelNode ln0 = (LabelNode) on;
+ if( ln0.equals(lnArg_i) ) {
+ edgesReachable.add(edge);
+ } else {
+ edgesUpstream.add(edge);
+ }
+
+ } else {
+
+ HeapRegionNode hrn0 = (HeapRegionNode) on;
+ if( reachableNodes.contains(hrn0) ) {
+ edgesReachable.add(edge);
+ } else {
+ 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);
+ }
+
+ // update upstream edges
+ 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);
+ }
+
+ propagateTokensOverEdges(edgesUpstream,
+ edgeUpstreamPlannedChanges,
+ edgesWithNewBeta);
+ }
+
+
+ // commit changes to alpha and beta
+ Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
+ while( nodeItr.hasNext() ) {
+ nodeItr.next().applyAlphaNew();
+ }
+
+ Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
+ while( edgeItr.hasNext() ) {
+ edgeItr.next().applyBetaNew();
}
- protected void mergeAnalysisRegions( OwnershipGraph og ) {
- Iterator iA = og.analysisRegionLabels.iterator();
- while( iA.hasNext() ) {
- TempDescriptor tdA = (TempDescriptor) iA.next();
- if( !analysisRegionLabels.contains( tdA ) ) {
- analysisRegionLabels.add( tdA );
+
+ // verify the existence of allocation sites and their
+ // shadows from the callee in the context of this caller graph
+ // then map allocated nodes of callee onto the caller shadows
+ // of them
+ Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
+ while( asItr.hasNext() ) {
+ AllocationSite allocSite = asItr.next();
+ HeapRegionNode hrnSummary = getSummaryNode(allocSite);
+
+ // assert that the shadow nodes have no reference edges
+ // because they're brand new to the graph, or last time
+ // they were used they should have been cleared of edges
+ HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
+ assert hrnShadowSummary.getNumReferencers() == 0;
+ assert hrnShadowSummary.getNumReferencees() == 0;
+
+ // then bring g_ij onto g'_ij and rewrite
+ transferOnto(hrnSummary, hrnShadowSummary);
+
+ 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);
+
+ hrnShadowSummary.applyAlphaNew();
+
+
+ for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
+ Integer idIth = allocSite.getIthOldest(i);
+ assert id2hrn.containsKey(idIth);
+ HeapRegionNode hrnIth = id2hrn.get(idIth);
+
+ Integer idShadowIth = -(allocSite.getIthOldest(i));
+ assert id2hrn.containsKey(idShadowIth);
+ HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
+ assert hrnIthShadow.getNumReferencers() == 0;
+ assert hrnIthShadow.getNumReferencees() == 0;
+
+ transferOnto(hrnIth, hrnIthShadow);
+
+ assert ogCallee.id2hrn.containsKey(idIth);
+ HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
+ hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
+
+ rewriteCallerNodeAlpha(fm.numParameters(),
+ bogusIndex,
+ hrnIthShadow,
+ paramIndex2rewriteH,
+ paramIndex2rewriteD,
+ paramIndex2paramToken,
+ paramIndex2paramTokenStar);
+
+ hrnIthShadow.applyAlphaNew();
+ }
+ }
+
+
+ // for every heap region->heap region edge in the
+ // callee graph, create the matching edge or edges
+ // in the caller graph
+ Set sCallee = ogCallee.id2hrn.entrySet();
+ Iterator iCallee = sCallee.iterator();
+ while( iCallee.hasNext() ) {
+ Map.Entry meCallee = (Map.Entry)iCallee.next();
+ Integer idCallee = (Integer) meCallee.getKey();
+ HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
+
+ Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
+ while( heapRegionsItrCallee.hasNext() ) {
+ ReferenceEdge edgeCallee = heapRegionsItrCallee.next();
+ 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:
+ // hrnCallee -> heapChildCallee
+ //
+ // or by the ownership-graph independent ID's:
+ // idCallee -> idChildCallee
+
+ // make the edge with src and dst so beta info is
+ // calculated once, then copy it for each new edge in caller
+ ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
+ null,
+ edgeCallee.getFieldDesc(),
+ false,
+ toShadowTokens(ogCallee, edgeCallee.getBeta() )
+ );
+ rewriteCallerEdgeBeta(fm.numParameters(),
+ bogusIndex,
+ edgeNewInCallerTemplate,
+ paramIndex2rewriteJ,
+ paramIndex2rewriteD,
+ paramIndex2paramToken,
+ paramIndex2paramTokenStar,
+ false,
+ null);
+
+ edgeNewInCallerTemplate.applyBetaNew();
+
+
+ // So now make a set of possible source heaps in the caller graph
+ // and a set of destination heaps in the caller graph, and make
+ // a reference edge in the caller for every possible (src,dst) pair
+ HashSet<HeapRegionNode> possibleCallerSrcs =
+ getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
+ (HeapRegionNode) edgeCallee.getSrc(),
+ paramIndex2reachableCallerNodes);
+
+ HashSet<HeapRegionNode> possibleCallerDsts =
+ 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() );
+ if( edgeExisting == null ) {
+ // if this edge doesn't exist in the caller, create it
+ addReferenceEdge(src, dst, edgeNewInCaller);
+ } else {
+ // if it already exists, merge with it
+ edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
+ }
}
+ }
}
+ }
}
- protected void mergeNewClusters( OwnershipGraph og ) {
- Set sA = og.fn2nc.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- FlatNew fnA = (FlatNew) meA.getKey();
- NewCluster ncA = (NewCluster) meA.getValue();
-
- // if the A cluster doesn't exist in B we have to construct
- // it carefully because the nodes and their edges have already
- // been merged above. Just find the equivalent heap regions
- // in the B graph by matching IDs
-
- // if the cluster already exists the edges of its elements
- // should already have been merged by the above code that
- // does not care whether the regions are part of clusters
- NewCluster ncB = null;
- if( !fn2nc.containsKey( fnA ) ) {
- ncB = new NewCluster( newDepthK );
-
- for( int i = 0; i < newDepthK; ++i ) {
- HeapRegionNode hrnA = ncA.getIthOldest( i );
-
- // this node shouldn't exist in graph B if the
- // corresponding new cluster didn't exist in B
- //assert !id2hrn.containsKey( hrnA.getID() );
-
- HeapRegionNode hrnB = createNewHeapRegionNode( hrnA.getID(),
- hrnA.isSingleObject(),
- hrnA.isFlagged(),
- hrnA.isNewSummary() );
- ncB.setIthOldest( i, hrnB );
- }
-
- fn2nc.put( fnA, ncB );
- }
+
+ // 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() )
+ );
+ rewriteCallerEdgeBeta(fm.numParameters(),
+ bogusIndex,
+ edgeNewInCallerTemplate,
+ paramIndex2rewriteJ,
+ paramIndex2rewriteD,
+ paramIndex2paramToken,
+ paramIndex2paramTokenStar,
+ 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() ) {
+ AllocationSite as = allocItr.next();
- // it is necessary in the equals() member functions
- // to "check both ways" when comparing the data
- // structures of two graphs. For instance, if all
- // edges between heap region nodes in graph A are
- // present and equal in graph B it is not sufficient
- // to say the graphs are equal. Consider that there
- // may be edges in graph B that are not in graph A.
- // the only way to know that all edges in both graphs
- // are equally present is to iterate over both data
- // structures and compare against the other graph.
- public boolean equals( OwnershipGraph og ) {
-
- if( !areHeapRegionNodesEqual( og ) ) {
- return false;
- }
+ // first age each allocation site enough times to make room for the shadow nodes
+ for( int i = 0; i < as.getAllocationDepth(); ++i ) {
+ age(as);
+ }
- if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
- return false;
- }
+ // then merge the shadow summary into the normal summary
+ HeapRegionNode hrnSummary = getSummaryNode(as);
+ assert hrnSummary != null;
- if( !areLabelNodesEqual( og ) ) {
- return false;
- }
+ HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
+ assert hrnSummaryShadow != null;
- if( !areLabelToHeapRegionEdgesEqual( og ) ) {
- return false;
- }
+ mergeIntoSummary(hrnSummaryShadow, hrnSummary);
- if( !areHeapRootsEqual( og ) ) {
- return false;
- }
+ // 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);
- if( !areAnalysisRegionLabelsEqual( og ) ) {
- return false;
+ // clear off shadow nodes after transfer
+ clearReferenceEdgesFrom(hrnIthShadow, null, true);
+ clearReferenceEdgesTo(hrnIthShadow, null, true);
+ hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
+ }
+
+ // finally, globally change shadow tokens into normal tokens
+ Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
+ while( itrAllLabelNodes.hasNext() ) {
+ Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
+ 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();
- if( !areNewClustersEqual( og ) ) {
- return false;
+ unshadowTokens(as, hrnToAge);
+
+ Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
+ while( itrEdges.hasNext() ) {
+ unshadowTokens(as, itrEdges.next() );
}
+ }
+ }
+ }
- return true;
+
+ 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;
}
- protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
- // check all nodes in A for presence in graph B
- Set sA = og.id2hrn.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- Integer idA = (Integer) meA.getKey();
- HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
-
- if( !id2hrn.containsKey( idA ) ) {
- return false;
- }
+ TypeDescriptor tdSrc = asSrc.getType();
+ assert tdSrc != null;
- HeapRegionNode hrnB = og.id2hrn.get( idA );
- if( !hrnA.equals( hrnB ) ) {
- return false;
- }
- }
-
- // then check all nodes in B verses graph A
- Set sB = id2hrn.entrySet();
- Iterator iB = sB.iterator();
- while( iB.hasNext() ) {
- Map.Entry meB = (Map.Entry) iB.next();
- Integer idB = (Integer) meB.getKey();
- HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
-
- if( !og.id2hrn.containsKey( idB ) ) {
- return false;
- }
-
- // we should have already checked the equality
- // of this pairing in the last pass if they both
- // exist so assert that they are equal now
- HeapRegionNode hrnA = og.id2hrn.get( idB );
- assert hrnB.equals( hrnA );
- }
+ // 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;
+ }
}
- protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
- Set sA = og.id2hrn.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- Integer idA = (Integer) meA.getKey();
- HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
-
- // we should have already checked that the same
- // heap regions exist in both graphs
- assert id2hrn.containsKey( idA );
-
- // and are their edges the same? first check every
- // edge in A for presence and equality in B
- HeapRegionNode hrnChildA = null;
- Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildA = hrnChildA.getID();
- assert id2hrn.containsKey( idChildA );
-
- // at this point we know an edge in graph A exists
- // idA -> idChildA, does this edge exist in B?
- boolean edgeFound = false;
- HeapRegionNode hrnB = id2hrn.get( idA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
-
- if( idChildA.equals( hrnChildB.getID() ) ) {
- if( !repA.equals( repB ) ) {
- return false;
- }
- edgeFound = true;
- }
- }
-
- if( !edgeFound ) {
- return false;
- }
- }
+ // otherwise it is a class with fields
+ // but we didn't find a match
+ return false;
+ }
- // then check every edge in B for presence in A, starting
- // from the same parent HeapRegionNode
- HeapRegionNode hrnB = id2hrn.get( idA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildB = hrnChildB.getID();
-
- // at this point we know an edge in graph B exists
- // idB -> idChildB, does this edge exist in A?
- boolean edgeFound = false;
-
- hrnChildA = null;
- heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
-
- if( idChildB.equals( hrnChildA.getID() ) ) {
- assert repB.equals( repA );
- edgeFound = true;
- }
- }
-
- if( !edgeFound ) {
- return false;
- }
- }
- }
- return true;
+ protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
+
+ // if the region has no type, matches everything
+ AllocationSite asDst = dst.getAllocationSite();
+ if( asDst == null ) {
+ return true;
}
- protected boolean areLabelNodesEqual( OwnershipGraph og ) {
- // are all label nodes in A also in graph B?
- Set sA = og.td2ln.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- TempDescriptor tdA = (TempDescriptor) meA.getKey();
+ TypeDescriptor tdDst = asDst.getType();
+ assert tdDst != null;
- if( !td2ln.containsKey( tdA ) ) {
- return false;
- }
- }
+ // 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;
+ }
- // are all label nodes in B also in A?
- Set sB = td2ln.entrySet();
- Iterator iB = sB.iterator();
- while( iB.hasNext() ) {
- Map.Entry meB = (Map.Entry) iB.next();
- TempDescriptor tdB = (TempDescriptor) meB.getKey();
+ // if the field is null, it matches everything
+ FieldDescriptor fd = edge.getFieldDesc();
+ if( fd == null ) {
+ return true;
+ }
+ TypeDescriptor tdFd = fd.getType();
+ assert tdFd != null;
- if( !og.td2ln.containsKey( tdB ) ) {
- return false;
- }
- }
+ return typeUtil.isSuperorType(tdFd, tdDst);
+ }
- return true;
+
+
+ protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
+ edge.setBeta(edge.getBeta().unshadowTokens(as) );
+ }
+
+ protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
+ hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
+ }
+
+
+ private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
+ ReachabilitySet rsIn) {
+
+ ReachabilitySet rsOut = new ReachabilitySet(rsIn);
+
+ Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
+ while( allocItr.hasNext() ) {
+ AllocationSite as = allocItr.next();
+
+ rsOut = rsOut.toShadowTokens(as);
}
- protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
- Set sA = og.td2ln.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- TempDescriptor tdA = (TempDescriptor) meA.getKey();
- LabelNode lnA = (LabelNode) meA.getValue();
-
- // we should have already checked that the same
- // label nodes exist in both graphs
- assert td2ln.containsKey( tdA );
-
- // and are their edges the same? first check every
- // edge in A for presence and equality in B
- HeapRegionNode hrnChildA = null;
- Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildA = hrnChildA.getID();
- assert id2hrn.containsKey( idChildA );
-
- // at this point we know an edge in graph A exists
- // tdA -> idChildA, does this edge exist in B?
- boolean edgeFound = false;
- LabelNode lnB = td2ln.get( tdA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
-
- if( idChildA.equals( hrnChildB.getID() ) ) {
- if( !repA.equals( repB ) ) {
- return false;
- }
- edgeFound = true;
- }
- }
-
- if( !edgeFound ) {
- return false;
- }
- }
+ return rsOut.makeCanonical();
+ }
- // then check every edge in B for presence in A, starting
- // from the same parent LabelNode
- LabelNode lnB = td2ln.get( tdA );
-
- HeapRegionNode hrnChildB = null;
- Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
- while( heapRegionsItrB.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItrB.next();
- hrnChildB = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
-
- Integer idChildB = hrnChildB.getID();
-
- // at this point we know an edge in graph B exists
- // tdB -> idChildB, does this edge exist in A?
- boolean edgeFound = false;
-
- hrnChildA = null;
- heapRegionsItrA = lnA.setIteratorToReferencedRegions();
- while( heapRegionsItrA.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItrA.next();
- hrnChildA = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
-
- if( idChildB.equals( hrnChildA.getID() ) ) {
- assert repB.equals( repA );
- edgeFound = true;
- }
- }
-
- if( !edgeFound ) {
- return false;
- }
- }
- }
- return true;
+ private void rewriteCallerNodeAlpha(int numParameters,
+ Integer paramIndex,
+ HeapRegionNode hrn,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
+ Hashtable<Integer, TokenTuple> paramIndex2paramToken,
+ Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
+
+ ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
+ assert rules != null;
+
+ TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
+ assert tokenToRewrite != null;
+
+ ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
+ Iterator<TokenTupleSet> ttsItr = rules.iterator();
+ while( ttsItr.hasNext() ) {
+ TokenTupleSet tts = ttsItr.next();
+ r0 = r0.union(tts.rewriteToken(tokenToRewrite,
+ hrn.getAlpha(),
+ false,
+ null) );
}
- protected boolean areHeapRootsEqual( OwnershipGraph og ) {
- if( og.heapRoots.size() != heapRoots.size() ) {
- return false;
+ ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
+ ttsItr = r0.iterator();
+ while( ttsItr.hasNext() ) {
+ TokenTupleSet tts = ttsItr.next();
+ r1 = r1.union(rewriteDpass(numParameters,
+ paramIndex,
+ tts,
+ paramIndex2rewriteD,
+ paramIndex2paramToken,
+ paramIndex2paramTokenStar) );
+ }
+
+ hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
+ }
+
+
+ private void rewriteCallerEdgeBeta(int numParameters,
+ Integer paramIndex,
+ ReferenceEdge edge,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
+ Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
+ Hashtable<Integer, TokenTuple> paramIndex2paramToken,
+ Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
+ boolean makeChangeSet,
+ Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
+
+ ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex);
+ assert rules != null;
+
+ TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
+ assert tokenToRewrite != null;
+
+ ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
+
+ Iterator<TokenTupleSet> ttsItr = rules.iterator();
+ while( ttsItr.hasNext() ) {
+ TokenTupleSet tts = ttsItr.next();
+
+ Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > forChangeSet =
+ new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
+
+ ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
+ edge.getBeta(),
+ true,
+ forChangeSet);
+
+ Iterator fcsItr = forChangeSet.entrySet().iterator();
+ while( fcsItr.hasNext() ) {
+ Map.Entry me = (Map.Entry)fcsItr.next();
+ TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
+ HashSet<TokenTupleSet> ttsAddSet = (HashSet<TokenTupleSet>) me.getValue();
+ Iterator<TokenTupleSet> ttsAddItr = ttsAddSet.iterator();
+ while( ttsAddItr.hasNext() ) {
+ TokenTupleSet ttsAdd = ttsAddItr.next();
+
+ ChangeTuple ct = new ChangeTuple(ttsMatch,
+ ttsAdd
+ ).makeCanonical();
+
+ cts0 = cts0.union(ct);
}
+ }
+ }
- Set sA = og.heapRoots.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- Integer idA = (Integer) meA.getKey();
- if( !heapRoots.containsKey( idA ) ) {
- return false;
- }
+ 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);
}
+ }
+ }
- Set sB = heapRoots.entrySet();
- Iterator iB = sB.iterator();
- while( iB.hasNext() ) {
- Map.Entry meB = (Map.Entry) iB.next();
- Integer idB = (Integer) meB.getKey();
+ if( makeChangeSet ) {
+ edgePlannedChanges.put(edge, cts1);
+ }
- if( !heapRoots.containsKey( idB ) ) {
- return false;
- }
+ 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;
+ }
+ }
+ }
+
+ 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;
}
+ }
+ }
- return true;
+ if( !rewritten ) {
+ rsOut = rsOut.union(ttsIn);
}
- protected boolean areAnalysisRegionLabelsEqual( OwnershipGraph og ) {
- if( og.analysisRegionLabels.size() != analysisRegionLabels.size() ) {
- return false;
+ return rsOut;
+ }
+
+
+ private HashSet<HeapRegionNode>
+ getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
+ HeapRegionNode hrnCallee,
+ Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
+ ) {
+
+ HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
+
+ Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
+
+ if( paramIndexCallee == null ) {
+ // this is a node allocated in the callee then and it has
+ // exactly one shadow node in the caller to map to
+ AllocationSite as = hrnCallee.getAllocationSite();
+ assert as != null;
+
+ int age = as.getAgeCategory(hrnCallee.getID() );
+ assert age != AllocationSite.AGE_notInThisSite;
+
+ Integer idCaller;
+ if( age == AllocationSite.AGE_summary ) {
+ idCaller = as.getSummaryShadow();
+ } else if( age == AllocationSite.AGE_oldest ) {
+ idCaller = as.getOldestShadow();
+ } else {
+ assert age == AllocationSite.AGE_in_I;
+
+ Integer I = as.getAge(hrnCallee.getID() );
+ assert I != null;
+
+ idCaller = as.getIthOldestShadow(I);
+ }
+
+ 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);
+ }
+
+ return possibleCallerHRNs;
+ }
+
+
+
+ ////////////////////////////////////////////////////
+ // in merge() and equals() methods the suffix A
+ // represents the passed in graph and the suffix
+ // B refers to the graph in this object
+ // Merging means to take the incoming graph A and
+ // merge it into B, so after the operation graph B
+ // is the final result.
+ ////////////////////////////////////////////////////
+ public void merge(OwnershipGraph og) {
+
+ if( og == null ) {
+ return;
+ }
+
+ mergeOwnershipNodes(og);
+ mergeReferenceEdges(og);
+ mergeId2paramIndex(og);
+ mergeAllocationSites(og);
+ }
+
+
+ protected void mergeOwnershipNodes(OwnershipGraph og) {
+ Set sA = og.id2hrn.entrySet();
+ Iterator iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry)iA.next();
+ Integer idA = (Integer) meA.getKey();
+ HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
+
+ // if this graph doesn't have a node the
+ // incoming graph has, allocate it
+ if( !id2hrn.containsKey(idA) ) {
+ HeapRegionNode hrnB = hrnA.copy();
+ id2hrn.put(idA, hrnB);
+
+ } else {
+ // otherwise this is a node present in both graphs
+ // so make the new reachability set a union of the
+ // nodes' reachability sets
+ HeapRegionNode hrnB = id2hrn.get(idA);
+ hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
+ }
+ }
+
+ // now add any label nodes that are in graph B but
+ // not in A
+ sA = og.td2ln.entrySet();
+ iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry)iA.next();
+ TempDescriptor tdA = (TempDescriptor) meA.getKey();
+ LabelNode lnA = (LabelNode) meA.getValue();
+
+ // if the label doesn't exist in B, allocate and add it
+ LabelNode lnB = getLabelNodeFromTemp(tdA);
+ }
+ }
+
+ protected void mergeReferenceEdges(OwnershipGraph og) {
+
+ // heap regions
+ Set sA = og.id2hrn.entrySet();
+ Iterator iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry)iA.next();
+ Integer idA = (Integer) meA.getKey();
+ HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
+
+ Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
+ while( heapRegionsItrA.hasNext() ) {
+ ReferenceEdge edgeA = heapRegionsItrA.next();
+ HeapRegionNode hrnChildA = edgeA.getDst();
+ Integer idChildA = hrnChildA.getID();
+
+ // at this point we know an edge in graph A exists
+ // idA -> idChildA, does this exist in B?
+ assert id2hrn.containsKey(idA);
+ HeapRegionNode hrnB = id2hrn.get(idA);
+ ReferenceEdge edgeToMerge = null;
+
+ Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
+ while( heapRegionsItrB.hasNext() &&
+ edgeToMerge == null ) {
+
+ ReferenceEdge edgeB = heapRegionsItrB.next();
+ HeapRegionNode hrnChildB = edgeB.getDst();
+ Integer idChildB = hrnChildB.getID();
+
+ // don't use the ReferenceEdge.equals() here because
+ // we're talking about existence between graphs
+ if( idChildB.equals(idChildA) &&
+ edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
+ edgeToMerge = edgeB;
+ }
}
- Iterator iA = og.analysisRegionLabels.iterator();
- while( iA.hasNext() ) {
- TempDescriptor tdA = (TempDescriptor) iA.next();
- if( !analysisRegionLabels.contains( tdA ) ) {
- return false;
- }
+ // if the edge from A was not found in B,
+ // add it to B.
+ if( edgeToMerge == null ) {
+ assert id2hrn.containsKey(idChildA);
+ HeapRegionNode hrnChildB = id2hrn.get(idChildA);
+ edgeToMerge = edgeA.copy();
+ edgeToMerge.setSrc(hrnB);
+ edgeToMerge.setDst(hrnChildB);
+ addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
+ }
+ // otherwise, the edge already existed in both graphs
+ // so merge their reachability sets
+ else {
+ // just replace this beta set with the union
+ assert edgeToMerge != null;
+ edgeToMerge.setBeta(
+ edgeToMerge.getBeta().union(edgeA.getBeta() )
+ );
+ if( !edgeA.isInitialParamReflexive() ) {
+ edgeToMerge.setIsInitialParamReflexive(false);
+ }
}
+ }
+ }
- Iterator iB = analysisRegionLabels.iterator();
- while( iB.hasNext() ) {
- TempDescriptor tdB = (TempDescriptor) iB.next();
- if( !og.analysisRegionLabels.contains( tdB ) ) {
- return false;
- }
+ // and then again with label nodes
+ sA = og.td2ln.entrySet();
+ iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry)iA.next();
+ TempDescriptor tdA = (TempDescriptor) meA.getKey();
+ LabelNode lnA = (LabelNode) meA.getValue();
+
+ Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
+ while( heapRegionsItrA.hasNext() ) {
+ ReferenceEdge edgeA = heapRegionsItrA.next();
+ HeapRegionNode hrnChildA = edgeA.getDst();
+ Integer idChildA = hrnChildA.getID();
+
+ // at this point we know an edge in graph A exists
+ // tdA -> idChildA, does this exist in B?
+ assert td2ln.containsKey(tdA);
+ LabelNode lnB = td2ln.get(tdA);
+ ReferenceEdge edgeToMerge = null;
+
+ // labels never have edges with a field
+ //assert edgeA.getFieldDesc() == null;
+
+ Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
+ while( heapRegionsItrB.hasNext() &&
+ edgeToMerge == null ) {
+
+ ReferenceEdge edgeB = heapRegionsItrB.next();
+ HeapRegionNode hrnChildB = edgeB.getDst();
+ Integer idChildB = hrnChildB.getID();
+
+ // labels never have edges with a field
+ //assert edgeB.getFieldDesc() == null;
+
+ // don't use the ReferenceEdge.equals() here because
+ // we're talking about existence between graphs
+ if( idChildB.equals(idChildA) &&
+ edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
+ edgeToMerge = edgeB;
+ }
}
- return true;
+ // if the edge from A was not found in B,
+ // add it to B.
+ if( edgeToMerge == null ) {
+ assert id2hrn.containsKey(idChildA);
+ HeapRegionNode hrnChildB = id2hrn.get(idChildA);
+ edgeToMerge = edgeA.copy();
+ edgeToMerge.setSrc(lnB);
+ edgeToMerge.setDst(hrnChildB);
+ addReferenceEdge(lnB, hrnChildB, edgeToMerge);
+ }
+ // otherwise, the edge already existed in both graphs
+ // so merge their reachability sets
+ else {
+ // just replace this beta set with the union
+ edgeToMerge.setBeta(
+ edgeToMerge.getBeta().union(edgeA.getBeta() )
+ );
+ if( !edgeA.isInitialParamReflexive() ) {
+ edgeToMerge.setIsInitialParamReflexive(false);
+ }
+ }
+ }
+ }
+ }
+
+ // you should only merge ownership graphs that have the
+ // same number of parameters, or if one or both parameter
+ // index tables are empty
+ protected void mergeId2paramIndex(OwnershipGraph og) {
+ if( id2paramIndex.size() == 0 ) {
+ id2paramIndex = og.id2paramIndex;
+ paramIndex2id = og.paramIndex2id;
+ paramIndex2tdQ = og.paramIndex2tdQ;
+ return;
}
- protected boolean areNewClustersEqual( OwnershipGraph og ) {
- if( og.fn2nc.size() != fn2nc.size() ) {
- return false;
- }
+ if( og.id2paramIndex.size() == 0 ) {
+ return;
+ }
- Set sA = og.fn2nc.entrySet();
- Iterator iA = sA.iterator();
- while( iA.hasNext() ) {
- Map.Entry meA = (Map.Entry) iA.next();
- FlatNew fnA = (FlatNew) meA.getKey();
+ assert id2paramIndex.size() == og.id2paramIndex.size();
+ }
- if( !fn2nc.containsKey( fnA ) ) {
- return false;
- }
- }
+ protected void mergeAllocationSites(OwnershipGraph og) {
+ allocationSites.addAll(og.allocationSites);
+ }
- Set sB = fn2nc.entrySet();
- Iterator iB = sB.iterator();
- while( iB.hasNext() ) {
- Map.Entry meB = (Map.Entry) iB.next();
- FlatNew fnB = (FlatNew) meB.getKey();
- if( !fn2nc.containsKey( fnB ) ) {
- return false;
- }
+
+ // it is necessary in the equals() member functions
+ // to "check both ways" when comparing the data
+ // structures of two graphs. For instance, if all
+ // edges between heap region nodes in graph A are
+ // present and equal in graph B it is not sufficient
+ // to say the graphs are equal. Consider that there
+ // may be edges in graph B that are not in graph A.
+ // the only way to know that all edges in both graphs
+ // are equally present is to iterate over both data
+ // structures and compare against the other graph.
+ public boolean equals(OwnershipGraph og) {
+
+ if( og == null ) {
+ return false;
+ }
+
+ if( !areHeapRegionNodesEqual(og) ) {
+ return false;
+ }
+
+ if( !areLabelNodesEqual(og) ) {
+ return false;
+ }
+
+ if( !areReferenceEdgesEqual(og) ) {
+ return false;
+ }
+
+ if( !areId2paramIndexEqual(og) ) {
+ return false;
+ }
+
+ // if everything is equal up to this point,
+ // assert that allocationSites is also equal--
+ // this data is redundant and kept for efficiency
+ assert allocationSites.equals(og.allocationSites);
+
+ return true;
+ }
+
+ protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
+
+ if( !areallHRNinAalsoinBandequal(this, og) ) {
+ return false;
+ }
+
+ if( !areallHRNinAalsoinBandequal(og, this) ) {
+ return false;
+ }
+
+ return true;
+ }
+
+ static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
+ OwnershipGraph ogB) {
+ Set sA = ogA.id2hrn.entrySet();
+ Iterator iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry)iA.next();
+ Integer idA = (Integer) meA.getKey();
+ HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
+
+ if( !ogB.id2hrn.containsKey(idA) ) {
+ return false;
+ }
+
+ HeapRegionNode hrnB = ogB.id2hrn.get(idA);
+ if( !hrnA.equalsIncludingAlpha(hrnB) ) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+
+ protected boolean areLabelNodesEqual(OwnershipGraph og) {
+
+ if( !areallLNinAalsoinBandequal(this, og) ) {
+ return false;
+ }
+
+ if( !areallLNinAalsoinBandequal(og, this) ) {
+ return false;
+ }
+
+ return true;
+ }
+
+ static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
+ OwnershipGraph ogB) {
+ Set sA = ogA.td2ln.entrySet();
+ Iterator iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry)iA.next();
+ TempDescriptor tdA = (TempDescriptor) meA.getKey();
+
+ if( !ogB.td2ln.containsKey(tdA) ) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+
+ protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
+ if( !areallREinAandBequal(this, og) ) {
+ return false;
+ }
+
+ return true;
+ }
+
+ static protected boolean areallREinAandBequal(OwnershipGraph ogA,
+ OwnershipGraph ogB) {
+
+ // check all the heap region->heap region edges
+ Set sA = ogA.id2hrn.entrySet();
+ Iterator iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry)iA.next();
+ Integer idA = (Integer) meA.getKey();
+ HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
+
+ // we should have already checked that the same
+ // heap regions exist in both graphs
+ assert ogB.id2hrn.containsKey(idA);
+
+ if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
+ return false;
+ }
+
+ // then check every edge in B for presence in A, starting
+ // from the same parent HeapRegionNode
+ HeapRegionNode hrnB = ogB.id2hrn.get(idA);
+
+ if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
+ return false;
+ }
+ }
+
+ // then check all the label->heap region edges
+ sA = ogA.td2ln.entrySet();
+ iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry)iA.next();
+ TempDescriptor tdA = (TempDescriptor) meA.getKey();
+ LabelNode lnA = (LabelNode) meA.getValue();
+
+ // we should have already checked that the same
+ // label nodes exist in both graphs
+ assert ogB.td2ln.containsKey(tdA);
+
+ if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
+ return false;
+ }
+
+ // then check every edge in B for presence in A, starting
+ // from the same parent LabelNode
+ LabelNode lnB = ogB.td2ln.get(tdA);
+
+ if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+
+ static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
+ OwnershipNode onA,
+ OwnershipGraph ogB) {
+
+ Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
+ while( itrA.hasNext() ) {
+ ReferenceEdge edgeA = itrA.next();
+ HeapRegionNode hrnChildA = edgeA.getDst();
+ Integer idChildA = hrnChildA.getID();
+
+ assert ogB.id2hrn.containsKey(idChildA);
+
+ // at this point we know an edge in graph A exists
+ // onA -> idChildA, does this exact edge exist in B?
+ boolean edgeFound = false;
+
+ OwnershipNode onB = null;
+ if( onA instanceof HeapRegionNode ) {
+ HeapRegionNode hrnA = (HeapRegionNode) onA;
+ onB = ogB.id2hrn.get(hrnA.getID() );
+ } else {
+ LabelNode lnA = (LabelNode) onA;
+ onB = ogB.td2ln.get(lnA.getTempDescriptor() );
+ }
+
+ Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
+ while( itrB.hasNext() ) {
+ ReferenceEdge edgeB = itrB.next();
+ HeapRegionNode hrnChildB = edgeB.getDst();
+ Integer idChildB = hrnChildB.getID();
+
+ if( idChildA.equals(idChildB) &&
+ edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
+
+ // there is an edge in the right place with the right field,
+ // but do they have the same attributes?
+ if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
+
+ edgeFound = true;
+ //} else {
+ //return false;
+ }
}
+ }
+
+ if( !edgeFound ) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+
+ protected boolean areId2paramIndexEqual(OwnershipGraph og) {
+ 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 pStar1 = new TokenTuple(hrnParam1.getID(),
+ true,
+ TokenTuple.ARITY_MANY).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 pStar2 = new TokenTuple(hrnParam2.getID(),
+ true,
+ TokenTuple.ARITY_MANY).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(pStar1, p2) ) {
+ return true;
+ }
+ if( beta1.containsTupleSetWithBoth(p1, 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 pStar = new TokenTuple(hrnParam.getID(),
+ true,
+ TokenTuple.ARITY_MANY).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 gsStar = new TokenTuple(as.getSummary(),
+ true,
+ TokenTuple.ARITY_MANY).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;
+ }
+
+ // check for other nodes
+ for( int i = 0; i < as.getAllocationDepth(); ++i ) {
+
+ // the other nodes of an allocation site are single, no stars
+ TokenTuple gi = new TokenTuple(as.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ if( beta.containsTupleSetWithBoth(p, gi) ) {
+ return true;
+ }
+ if( beta.containsTupleSetWithBoth(pStar, gi) ) {
return true;
+ }
}
+ return false;
+ }
- public void writeGraph( String graphName ) throws java.io.IOException {
- BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
- bw.write( "digraph "+graphName+" {\n" );
+ public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
- // first write out new clusters
- Integer newClusterNum = new Integer( 100 );
- Set s = fn2nc.entrySet();
- Iterator i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- FlatNew fn = (FlatNew) me.getKey();
- NewCluster nc = (NewCluster) me.getValue();
+ // get tokens for summary nodes
+ TokenTuple gs1 = new TokenTuple(as1.getSummary(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical();
- bw.write( " subgraph cluster" + newClusterNum + " {\n" );
- bw.write( " color=blue;\n" );
- bw.write( " rankdir=LR;\n" );
- bw.write( " label=\"" + fn.toString() + "\";\n" );
-
- for( int j = 0; j < newDepthK; ++j ) {
- HeapRegionNode hrn = nc.getIthOldest( j );
- bw.write( " " + hrn.toString() + ";\n" );
- }
+ TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
+ true,
+ TokenTuple.ARITY_MANY).makeCanonical();
- bw.write( " }\n" );
- }
+ // 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;
- // then visit every heap region node
- HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
- s = heapRoots.entrySet();
- i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- HeapRegionNode hrn = (HeapRegionNode) me.getValue();
- traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL, hrn, bw, null, visited );
- }
+ // and for the other one
+ TokenTuple gs2 = new TokenTuple(as2.getSummary(),
+ true,
+ TokenTuple.ARITY_ONE).makeCanonical();
- // then visit every label node
- s = td2ln.entrySet();
- i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- LabelNode ln = (LabelNode) me.getValue();
-
- HeapRegionNode hrn = null;
- Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
- while( heapRegionsItr.hasNext() ) {
- Map.Entry meH = (Map.Entry) heapRegionsItr.next();
- hrn = (HeapRegionNode) meH.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
-
- String edgeLabel = "";
- if( rep.isUnique() ) {
- edgeLabel = "Unique";
- }
- bw.write( " " + ln.toString() +
- " -> " + hrn.toString() +
- "[label=\"" + edgeLabel +
- "\"];\n" );
- }
- }
+ TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
+ true,
+ TokenTuple.ARITY_MANY).makeCanonical();
- bw.write( "}\n" );
- bw.close();
+ // 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(gsStar2) ) {
+ return true;
+ }
+ if( alphaSum2.containsTuple(gsStar1) ) {
+ return true;
}
- public void writeCondensedAnalysis( String graphName ) throws java.io.IOException {
- BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
- bw.write( "graph "+graphName+" {\n" );
+ // only check non-star token if they are different sites
+ if( as1 != as2 ) {
+ if( alphaSum1.containsTuple(gs2) ) {
+ return true;
+ }
+ if( alphaSum2.containsTuple(gs1) ) {
+ return true;
+ }
+ }
- // find linked regions
- Iterator i = analysisRegionLabels.iterator();
- while( i.hasNext() ) {
- TempDescriptor td = (TempDescriptor) i.next();
- bw.write( " "+td.getSymbol()+";\n" );
- LabelNode ln = getLabelNodeFromTemp( td );
- HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
+ // 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;
- HeapRegionNode hrn = null;
- Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
- while( heapRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) heapRegionsItr.next();
- hrn = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
+ // the other nodes of an allocation site are single, no stars
+ TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ONE).makeCanonical();
- traverseHeapRegionNodes( VISIT_HRN_WRITE_CONDENSED, hrn, bw, td, visited );
- }
+ if( alphaSum2.containsTuple(gi1) ) {
+ return true;
+ }
+ if( alphaI1.containsTuple(gs2) ) {
+ return true;
+ }
+ if( alphaI1.containsTuple(gsStar2) ) {
+ return true;
+ }
+ }
+
+ // 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;
+
+ TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
+ false,
+ TokenTuple.ARITY_ONE).makeCanonical();
+
+ if( alphaSum1.containsTuple(gi2) ) {
+ return true;
+ }
+ if( alphaI2.containsTuple(gs1) ) {
+ return true;
+ }
+ if( alphaI2.containsTuple(gsStar1) ) {
+ return true;
+ }
+
+ // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
+ for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
+ Integer idI1 = as1.getIthOldest(j);
+
+ // if these are the same site, don't look for the same token, no alias
+ // different tokens of the same site could alias together though
+ if( idI1 == idI2 ) {
+ continue;
+ }
+
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+ ReachabilitySet alphaI1 = hrnI1.getAlpha();
+ TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
+ false,
+ TokenTuple.ARITY_ONE).makeCanonical();
+ if( alphaI2.containsTuple(gi1) ) {
+ return true;
}
+ if( alphaI1.containsTuple(gi2) ) {
+ return true;
+ }
+ }
+ }
- // write out linked regions
- Set s = linkedRegions.entrySet();
- Iterator lri = s.iterator();
- while( lri.hasNext() ) {
- Map.Entry me = (Map.Entry) lri.next();
- TempDescriptor t1 = (TempDescriptor) me.getKey();
- TempDescriptor t2 = (TempDescriptor) me.getValue();
- bw.write( " "+t1.getSymbol()+" -- "+t2.getSymbol()+";\n" );
+ return false;
+ }
+
+
+ // for writing ownership graphs to dot files
+ public void writeGraph(Descriptor methodDesc,
+ FlatNode fn,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+ writeGraph(
+ methodDesc.getSymbol() +
+ methodDesc.getNum() +
+ fn.toString(),
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
+ }
+
+ public void writeGraph(Descriptor methodDesc,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+
+ writeGraph(methodDesc+"COMPLETE",
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
+ }
+
+ public void writeGraph(Descriptor methodDesc,
+ Integer numUpdate,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings
+ ) throws java.io.IOException {
+
+ 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 writeParamMappings
+ ) throws java.io.IOException {
+
+ // remove all non-word characters from the graph name so
+ // the filename and identifier in dot don't cause errors
+ graphName = graphName.replaceAll("[\\W]", "");
+
+ BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
+ bw.write("digraph "+graphName+" {\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();
+ if( !visited.contains(hrn) ) {
+ traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
+ hrn,
+ bw,
+ null,
+ visited,
+ writeReferencers);
}
+ }
+ }
- bw.write( "}\n" );
- bw.close();
+ 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");
+ }
}
- protected void traverseHeapRegionNodes( int mode,
- HeapRegionNode hrn,
- BufferedWriter bw,
- TempDescriptor td,
- HashSet<HeapRegionNode> visited
- ) throws java.io.IOException {
+ // then visit every label node, useful for debugging
+ if( writeLabels ) {
+ Set s = td2ln.entrySet();
+ Iterator i = s.iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry)i.next();
+ LabelNode ln = (LabelNode) me.getValue();
+
+ if( labelSelect ) {
+ String labelStr = ln.getTempDescriptorString();
+ if( labelStr.startsWith("___temp") ||
+ labelStr.startsWith("___dst") ||
+ labelStr.startsWith("___srctmp") ||
+ labelStr.startsWith("___neverused") ) {
+ continue;
+ }
+ }
- if( visited.contains( hrn ) ) {
- return;
+ bw.write(ln.toString() + ";\n");
+
+ Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
+ while( heapRegionsItr.hasNext() ) {
+ ReferenceEdge edge = heapRegionsItr.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ if( pruneGarbage && !visited.contains(hrn) ) {
+ traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
+ hrn,
+ bw,
+ null,
+ visited,
+ writeReferencers);
+ }
+
+ bw.write(" " + ln.toString() +
+ " -> " + hrn.toString() +
+ "[label=\"" + edge.toGraphEdgeString() +
+ "\",decorate];\n");
}
- visited.add( hrn );
+ }
+ }
- switch( mode ) {
- case VISIT_HRN_WRITE_FULL:
-
- String isSingleObjectStr = "isSingleObject";
- if( !hrn.isSingleObject() ) {
- isSingleObjectStr = "!isSingleObject";
- }
- String isFlaggedStr = "isFlagged";
- if( !hrn.isFlagged() ) {
- isFlaggedStr = "!isFlagged";
- }
+ bw.write("}\n");
+ bw.close();
+ }
- String isNewSummaryStr = "isNewSummary";
- if( !hrn.isNewSummary() ) {
- isNewSummaryStr = "!isNewSummary";
- }
+ protected void traverseHeapRegionNodes(int mode,
+ HeapRegionNode hrn,
+ BufferedWriter bw,
+ TempDescriptor td,
+ HashSet<HeapRegionNode> visited,
+ boolean writeReferencers
+ ) throws java.io.IOException {
- bw.write( " " + hrn.toString() +
- "[shape=box,label=\"" + isFlaggedStr +
- "\\n" + isSingleObjectStr +
- "\\n" + isNewSummaryStr +
- "\"];\n" );
- break;
-
- case VISIT_HRN_WRITE_CONDENSED:
-
- Iterator i = hrn.iteratorToAnalysisRegionAliases();
- while( i.hasNext() ) {
- TempDescriptor tdn = (TempDescriptor) i.next();
-
- // only add a linked region if the td passed in and
- // the td's aliased to this node haven't already been
- // added as linked regions
- TempDescriptor tdAlias = null;
- if( linkedRegions.containsKey( td ) ) {
- tdAlias = linkedRegions.get( td );
- }
-
- TempDescriptor tdnAlias = null;
- if( linkedRegions.containsKey( tdn ) ) {
- tdnAlias = linkedRegions.get( tdn );
- }
-
- if( tdn != tdAlias && td != tdnAlias ) {
- linkedRegions.put( td, tdn );
- }
- }
-
- hrn.addAnalysisRegionAlias( td );
- break;
- }
+ if( visited.contains(hrn) ) {
+ return;
+ }
+ visited.add(hrn);
+ switch( mode ) {
+ case VISIT_HRN_WRITE_FULL:
- OwnershipNode onRef = null;
- Iterator refItr = hrn.iteratorToReferencers();
- while( refItr.hasNext() ) {
- onRef = (OwnershipNode) refItr.next();
+ String attributes = "[";
- switch( mode ) {
- case VISIT_HRN_WRITE_FULL:
- bw.write( " " + hrn.toString() +
- " -> " + onRef.toString() +
- "[color=lightgray];\n" );
- break;
- }
- }
+ if( hrn.isSingleObject() ) {
+ attributes += "shape=box";
+ } else {
+ attributes += "shape=Msquare";
+ }
+ if( hrn.isFlagged() ) {
+ attributes += ",style=filled,fillcolor=lightgrey";
+ }
+
+ attributes += ",label=\"ID" +
+ hrn.getID() +
+ "\\n" +
+ hrn.getDescription() +
+ "\\n" +
+ hrn.getAlphaString() +
+ "\"]";
+
+ bw.write(" " + hrn.toString() + attributes + ";\n");
+ break;
+ }
- HeapRegionNode hrnChild = null;
- Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
- while( childRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) childRegionsItr.next();
- hrnChild = (HeapRegionNode) me.getKey();
- ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
-
- switch( mode ) {
- case VISIT_HRN_WRITE_FULL:
- String edgeLabel = "";
- if( rep.isUnique() ) {
- edgeLabel = "Unique";
- }
- bw.write( " " + hrn.toString() +
- " -> " + hrnChild.toString() +
- "[label=\"" + edgeLabel +
- "\"];\n" );
- break;
- }
- traverseHeapRegionNodes( mode, hrnChild, bw, td, visited );
+ // useful for debugging
+ if( writeReferencers ) {
+ OwnershipNode onRef = null;
+ Iterator refItr = hrn.iteratorToReferencers();
+ while( refItr.hasNext() ) {
+ onRef = (OwnershipNode) refItr.next();
+
+ switch( mode ) {
+ case VISIT_HRN_WRITE_FULL:
+ bw.write(" " + hrn.toString() +
+ " -> " + onRef.toString() +
+ "[color=lightgray];\n");
+ break;
}
+ }
+ }
+
+ Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
+ while( childRegionsItr.hasNext() ) {
+ ReferenceEdge edge = childRegionsItr.next();
+ HeapRegionNode hrnChild = edge.getDst();
+
+ switch( mode ) {
+ case VISIT_HRN_WRITE_FULL:
+ bw.write(" " + hrn.toString() +
+ " -> " + hrnChild.toString() +
+ "[label=\"" + edge.toGraphEdgeString() +
+ "\",decorate];\n");
+ break;
+ }
+
+ traverseHeapRegionNodes(mode,
+ hrnChild,
+ bw,
+ td,
+ visited,
+ writeReferencers);
}
+ }
}
projects / IRC.git / blobdiff