assert rep != null;
referencer.addReferencedRegion( referencee, rep );
referencee.addReferencer( referencer );
+ rep.setSrc( referencer );
+ rep.setDst( referencee );
}
protected void removeReferenceEdge( OwnershipNode referencer,
}
}
+ protected void propagateTokensOverNodes( HeapRegionNode nPrime,
+ ChangeTupleSet c0,
+ HashSet<HeapRegionNode> nodesWithNewAlpha,
+ HashSet<ReferenceEdgeProperties> edgesWithNewBeta ) {
+
+ HashSet<HeapRegionNode> todoNodes
+ = new HashSet<HeapRegionNode>();
+ todoNodes.add( nPrime );
+
+ HashSet<ReferenceEdgeProperties> todoEdges
+ = new HashSet<ReferenceEdgeProperties>();
+
+ Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
+ = new Hashtable<HeapRegionNode, ChangeTupleSet>();
+ nodePlannedChanges.put( nPrime, c0 );
+
+ Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges
+ = new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
+
+ Hashtable<HeapRegionNode, ChangeTupleSet> nodeChangesMade
+ = new Hashtable<HeapRegionNode, ChangeTupleSet>();
+
+ while( !todoNodes.isEmpty() ) {
+ HeapRegionNode n = todoNodes.iterator().next();
+ todoNodes.remove( n );
+
+ ChangeTupleSet C = nodePlannedChanges.get( n );
+
+ if( !nodeChangesMade.containsKey( n ) ) {
+ nodeChangesMade.put( n, new ChangeTupleSet().makeCanonical() );
+ }
+
+ 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 );
+ nodeChangesMade.put( n, nodeChangesMade.get( n ).union( c ) );
+ }
+ }
+
+ ChangeTupleSet Cprime = nodeChangesMade.get( n );
+
+ Iterator referItr = n.iteratorToReferencers();
+ while( referItr.hasNext() ) {
+ OwnershipNode on = (OwnershipNode) referItr.next();
+ ReferenceEdgeProperties rep = on.getReferenceTo( n );
+ todoEdges.add( rep );
+
+ if( !edgePlannedChanges.containsKey( rep ) ) {
+ edgePlannedChanges.put( rep, new ChangeTupleSet().makeCanonical() );
+ }
+
+ edgePlannedChanges.put( rep, edgePlannedChanges.get( rep ).union( Cprime ) );
+ }
+
+ HeapRegionNode m = null;
+ ReferenceEdgeProperties f = null;
+ Iterator refeeItr = n.setIteratorToReferencedRegions();
+ while( refeeItr.hasNext() ) {
+ Map.Entry me = (Map.Entry) refeeItr.next();
+ m = (HeapRegionNode) me.getKey();
+ f = (ReferenceEdgeProperties) me.getValue();
+
+ ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
+
+ Iterator itrCprime = Cprime.iterator();
+ while( itrCprime.hasNext() ) {
+ ChangeTuple c = (ChangeTuple) itrCprime.next();
+ if( f.getBeta().contains( c.getSetToMatch() ) ) {
+ changesToPass = changesToPass.union( c );
+ }
+ }
+
+ if( !changesToPass.isEmpty() ) {
+ if( !nodePlannedChanges.containsKey( m ) ) {
+ nodePlannedChanges.put( m, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet currentChanges = nodePlannedChanges.get( m );
+
+ if( !changesToPass.isSubset( currentChanges ) ) {
+ todoNodes.add( m );
+ nodePlannedChanges.put( m, currentChanges.union( changesToPass ) );
+ }
+ }
+ }
+ }
+
+ propagateTokensOverEdges( todoEdges, edgePlannedChanges, nodesWithNewAlpha, edgesWithNewBeta );
+ }
+
+
+ protected void propagateTokensOverEdges(
+ HashSet<ReferenceEdgeProperties> todoEdges,
+ Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges,
+ HashSet<HeapRegionNode> nodesWithNewAlpha,
+ HashSet<ReferenceEdgeProperties> edgesWithNewBeta ) {
+
+
+ while( !todoEdges.isEmpty() ) {
+ ReferenceEdgeProperties e = todoEdges.iterator().next();
+ todoEdges.remove( e );
+
+ if( !edgePlannedChanges.containsKey( e ) ) {
+ edgePlannedChanges.put( e, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet C = edgePlannedChanges.get( e );
+
+ ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
+
+ Iterator itrC = C.iterator();
+ while( itrC.hasNext() ) {
+ ChangeTuple c = (ChangeTuple) itrC.next();
+ if( e.getBeta().contains( c.getSetToMatch() ) ) {
+ ReachabilitySet withChange = e.getBeta().union( c.getSetToAdd() );
+ e.setBetaNew( e.getBetaNew().union( withChange ) );
+ edgesWithNewBeta.add( e );
+ changesToPass = changesToPass.union( c );
+ }
+ }
+
+ OwnershipNode onSrc = e.getSrc();
+
+ if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
+ HeapRegionNode n = (HeapRegionNode) onSrc;
+ Iterator referItr = n.iteratorToReferencers();
+
+ while( referItr.hasNext() ) {
+ OwnershipNode onRef = (OwnershipNode) referItr.next();
+ ReferenceEdgeProperties f = onRef.getReferenceTo( n );
+
+ if( !edgePlannedChanges.containsKey( f ) ) {
+ edgePlannedChanges.put( f, new ChangeTupleSet().makeCanonical() );
+ }
+
+ ChangeTupleSet currentChanges = edgePlannedChanges.get( f );
+
+ if( !changesToPass.isSubset( currentChanges ) ) {
+ todoEdges.add( f );
+ edgePlannedChanges.put( f, currentChanges.union( changesToPass ) );
+ }
+ }
+ }
+ }
+ }
+
////////////////////////////////////////////////////
//
ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue();
ReachabilitySet beta2 = rep2.getBeta();
- ReferenceEdgeProperties rep = rep2.copy();
- rep.setBeta( beta1.intersection( beta2 ) );
+ ReferenceEdgeProperties rep =
+ new ReferenceEdgeProperties( false,
+ false,
+ beta1.intersection( beta2 ) );
addReferenceEdge( dstln, hrnOneHop, rep );
}
public void assignFieldToTemp( TempDescriptor src,
TempDescriptor dst,
FieldDescriptor fd ) {
+
+ // I think my use of src and dst are actually backwards in this method!
+ // acccording to the Reachability Notes, think of dst at N and src as N prime
+
LabelNode srcln = getLabelNodeFromTemp( src );
LabelNode dstln = getLabelNodeFromTemp( dst );
- HeapRegionNode hrn = null;
+ HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
+ HashSet<ReferenceEdgeProperties> edgesWithNewBeta = new HashSet<ReferenceEdgeProperties>();
+
+ HeapRegionNode hrn = null;
+ ReferenceEdgeProperties rep = null;
Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
while( dstRegionsItr.hasNext() ) {
- Map.Entry me = (Map.Entry) dstRegionsItr.next();
- hrn = (HeapRegionNode) me.getKey();
+ Map.Entry me = (Map.Entry) dstRegionsItr.next();
+ hrn = (HeapRegionNode) me.getKey();
+ rep = (ReferenceEdgeProperties) me.getValue();
+
+ ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
- HeapRegionNode hrnSrc = null;
+ HeapRegionNode hrnSrc = null;
+ ReferenceEdgeProperties repSrc = null;
Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
while( srcRegionsItr.hasNext() ) {
- Map.Entry meS = (Map.Entry) srcRegionsItr.next();
- hrnSrc = (HeapRegionNode) meS.getKey();
+ Map.Entry meS = (Map.Entry) srcRegionsItr.next();
+ hrnSrc = (HeapRegionNode) meS.getKey();
+ repSrc = (ReferenceEdgeProperties) meS.getValue();
+
+ ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta();
+
+
+ // 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( hrnSrc, Cy, nodesWithNewAlpha, edgesWithNewBeta );
+
+
+ // then propagate back just up the edges from hrn
+ ChangeTupleSet Cx = R.unionUpArityToChangeSet( O );
+
+ HashSet<ReferenceEdgeProperties> todoEdges =
+ new HashSet<ReferenceEdgeProperties>();
+
+ Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges =
+ new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
+
+ Iterator referItr = hrn.iteratorToReferencers();
+ while( referItr.hasNext() ) {
+ OwnershipNode onRef = (OwnershipNode) referItr.next();
+ ReferenceEdgeProperties repUpstream = onRef.getReferenceTo( hrn );
+
+ todoEdges.add( repUpstream );
+ edgePlannedChanges.put( repUpstream, Cx );
+ }
+
+ propagateTokensOverEdges( todoEdges,
+ edgePlannedChanges,
+ nodesWithNewAlpha,
+ edgesWithNewBeta );
+
+ // finally, create the actual reference edge hrn->hrnSrc
+ ReferenceEdgeProperties repNew
+ = new ReferenceEdgeProperties( false,
+ false,
+ repSrc.getBetaNew().pruneBy( hrn.getAlpha() )
+ );
- ReferenceEdgeProperties rep = new ReferenceEdgeProperties();
- addReferenceEdge( hrn, hrnSrc, rep );
+ addReferenceEdge( hrn, hrnSrc, repNew );
}
}
+
+ Iterator nodeItr = nodesWithNewAlpha.iterator();
+ while( nodeItr.hasNext() ) {
+ ((HeapRegionNode) nodeItr.next()).applyAlphaNew();
+ }
+
+ Iterator edgeItr = edgesWithNewBeta.iterator();
+ while( edgeItr.hasNext() ) {
+ ((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew();
+ }
}
public void assignTempToParameterAllocation( boolean isTask,
LabelNode dst = getLabelNodeFromTemp( td );
clearReferenceEdgesFrom( dst );
- addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false ) );
+
+ addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false, false, hrnNewest.getAlpha() ) );
}
boolean hasFlags = false;
if( as.getType().isClass() ) {
- hasFlags = as.getType().getClassDesc().hasFlags();
+ hasFlags = as.getType().getClassDesc().hasFlags();
}
hrnSummary = createNewHeapRegionNode( idSummary,
Map.Entry me = (Map.Entry) itrReferencee.next();
hrnReferencee = (HeapRegionNode) me.getKey();
ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
-
- // determine if another summary node is already referencing this referencee
- boolean hasSummaryReferencer = false;
- OwnershipNode onReferencer = null;
- Iterator itrReferencer = hrnReferencee.iteratorToReferencers();
- while( itrReferencer.hasNext() ) {
- onReferencer = (OwnershipNode) itrReferencer.next();
- if( onReferencer instanceof HeapRegionNode ) {
- HeapRegionNode hrnPossibleSummary = (HeapRegionNode) onReferencer;
- if( hrnPossibleSummary.isNewSummary() ) {
- hasSummaryReferencer = true;
- }
- }
+
+ ReferenceEdgeProperties repSummary = hrnSummary.getReferenceTo( hrnReferencee );
+ ReferenceEdgeProperties repMerged = rep.copy();
+
+ if( repSummary == 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
+ repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
}
- addReferenceEdge( hrnSummary,
- hrnReferencee,
- new ReferenceEdgeProperties( !hasSummaryReferencer ) );
+ addReferenceEdge( hrnSummary, hrnReferencee, repMerged );
}
// next transfer references to alpha_k over to alpha_s
onReferencer = (OwnershipNode) itrReferencer.next();
ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK );
- assert rep != null;
-
- addReferenceEdge( onReferencer, hrnSummary, rep.copy() );
+ assert rep != null;
+ ReferenceEdgeProperties repSummary = onReferencer.getReferenceTo( hrnSummary );
+ ReferenceEdgeProperties repMerged = rep.copy();
+
+ if( repSummary == 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
+ repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
+ }
+
+ addReferenceEdge( onReferencer, hrnSummary, repMerged );
}
+ // then merge alpha_k reachability into alpha_s
+ hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrnK.getAlpha() ) );
+
// then move down the line of heap region nodes
// clobbering the ith and transferring all references
addReferenceEdge( onReferencer, hrnI, rep.copy() );
}
+
+ // replace hrnI reachability with hrnImin1
+ hrnI.setAlpha( hrnImin1.getAlpha() );
}
// as stated above, the newest node alpha_0 should have had its
// have touched this node, therefore assert it is non-null
assert hrn0 != null;
+
// clear all references in and out of newest node
clearReferenceEdgesFrom( hrn0 );
clearReferenceEdgesTo ( hrn0 );
+
+
+ // now tokens in reachability sets need to "age" as well
+ ReferenceEdgeProperties repToAge = null;
+ Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
+ while( itrAllLabelNodes.hasNext() ) {
+ Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
+ LabelNode ln = (LabelNode) me.getValue();
+
+ Iterator itrEdges = ln.setIteratorToReferencedRegions();
+ while( itrEdges.hasNext() ) {
+ Map.Entry meE = (Map.Entry) itrEdges.next();
+ repToAge = (ReferenceEdgeProperties) meE.getValue();
+
+ ageTokens( as, repToAge );
+ }
+ }
+ HeapRegionNode hrnToAge = null;
+ Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
+ while( itrAllHRNodes.hasNext() ) {
+ Map.Entry me = (Map.Entry) itrAllHRNodes.next();
+ hrnToAge = (HeapRegionNode) me.getValue();
+
+ ageTokens( as, hrnToAge );
+
+ Iterator itrEdges = hrnToAge.setIteratorToReferencedRegions();
+ while( itrEdges.hasNext() ) {
+ Map.Entry meE = (Map.Entry) itrEdges.next();
+ repToAge = (ReferenceEdgeProperties) meE.getValue();
+
+ ageTokens( as, repToAge );
+ }
+ }
+
+
+ // after tokens have been aged, reset newest node's reachability
+ hrn0.setAlpha( new ReachabilitySet(
+ new TokenTupleSet(
+ new TokenTuple( hrn0 )
+ )
+ ).makeCanonical()
+ );
+ }
+
+ protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) {
+ rep.setBeta( rep.getBeta().ageTokens( as ) );
+ }
+
+ protected void ageTokens( AllocationSite as, HeapRegionNode hrn ) {
+ hrn.setAlpha( hrn.getAlpha().ageTokens( as ) );
}
//System.out.println( "idCallee is "+idCallee );
//System.out.println( "idChildCallee is "+idChildCallee );
- try {
- writeGraph( "caller", false, false );
- ogCallee.writeGraph( "callee", false, false );
+ try {
+ writeGraph( "caller", false, false, false );
+ ogCallee.writeGraph( "callee", false, false, false );
} catch( IOException e ) {}
}
// for writing ownership graphs to dot files
+ public void writeGraph( Descriptor methodDesc,
+ FlatNode fn,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean writeReferencers
+ ) throws java.io.IOException {
+ writeGraph(
+ methodDesc.getSymbol() +
+ methodDesc.getNum() +
+ fn.toString(),
+ writeLabels,
+ labelSelect,
+ writeReferencers
+ );
+ }
+
public void writeGraph( Descriptor methodDesc,
FlatNode fn,
boolean writeLabels,
methodDesc.getNum() +
fn.toString(),
writeLabels,
+ false,
writeReferencers
);
}
methodDesc.getNum() +
"COMPLETE",
writeLabels,
+ false,
+ writeReferencers
+ );
+ }
+
+ public void writeGraph( Descriptor methodDesc,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean writeReferencers
+ ) throws java.io.IOException {
+ writeGraph(
+ methodDesc.getSymbol() +
+ methodDesc.getNum() +
+ "COMPLETE",
+ writeLabels,
+ labelSelect,
writeReferencers
);
}
public void writeGraph( String graphName,
boolean writeLabels,
+ boolean labelSelect,
boolean writeReferencers
) throws java.io.IOException {
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;
+ }
+ }
+
HeapRegionNode hrn = null;
Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
while( heapRegionsItr.hasNext() ) {
bw.write( " " + ln.toString() +
" -> " + hrn.toString() +
"[label=\"" + rep.toEdgeLabelString() +
- "\"];\n" );
+ "\",decorate];\n" );
}
}
}
bw.write( " " + hrn.toString() +
" -> " + hrnChild.toString() +
"[label=\"" + rep.toEdgeLabelString() +
- "\"];\n" );
+ "\",decorate];\n" );
break;
}
projects / IRC.git / blobdiff