// use to disable improvements for comparison
protected static final boolean DISABLE_STRONG_UPDATES = false;
- protected static final boolean DISABLE_GLOBAL_SWEEP = true;
+ protected static final boolean DISABLE_GLOBAL_SWEEP = false;
// a special out-of-scope temp
protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
alpha = inherent;
}
- if( preds == null ) {
- // TODO: do this right? For out-of-context nodes?
- preds = ExistPredSet.factory();
- }
+ assert preds != null;
HeapRegionNode hrn = new HeapRegionNode( id,
isSingleObject,
if( edgeExisting != null ) {
edgeExisting.setBeta(
- Canonical.union( edgeExisting.getBeta(),
+ Canonical.unionORpreds( edgeExisting.getBeta(),
edgeNew.getBeta()
)
);
// otherwise an edge from the referencer to hrnSummary exists already
// and the edge referencer->hrn should be merged with it
edgeSummary.setBeta(
- Canonical.union( edgeMerged.getBeta(),
+ Canonical.unionORpreds( edgeMerged.getBeta(),
edgeSummary.getBeta()
)
);
// otherwise an edge from the referencer to alpha_S exists already
// and the edge referencer->alpha_K should be merged with it
edgeSummary.setBeta(
- Canonical.union( edgeMerged.getBeta(),
+ Canonical.unionORpreds( edgeMerged.getBeta(),
edgeSummary.getBeta()
)
);
// then merge hrn reachability into hrnSummary
hrnSummary.setAlpha(
- Canonical.union( hrnSummary.getAlpha(),
+ Canonical.unionORpreds( hrnSummary.getAlpha(),
hrn.getAlpha()
)
);
Iterator<ChangeTuple> itrCprime = C.iterator();
while( itrCprime.hasNext() ) {
ChangeTuple c = itrCprime.next();
- if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
- changesToPass = Canonical.union( changesToPass, c );
+ if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
+ != null
+ ) {
+ changesToPass = Canonical.add( changesToPass, c );
}
}
// but this propagation may be only one of many concurrent
// possible changes, so keep a running union with the node's
// partially updated new alpha set
- n.setAlphaNew( Canonical.union( n.getAlphaNew(),
+ n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
localDelta
)
);
Iterator<ChangeTuple> itrC = C.iterator();
while( itrC.hasNext() ) {
ChangeTuple c = itrC.next();
- if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
- changesToPass = Canonical.union( changesToPass, c );
+ if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
+ != null
+ ) {
+ changesToPass = Canonical.add( changesToPass, c );
}
}
// but this propagation may be only one of many concurrent
// possible changes, so keep a running union with the edge's
// partially updated new beta set
- e.setBetaNew( Canonical.union( e.getBetaNew(),
+ e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
localDelta
)
);
// used below to convert a ReachSet to its callee-context
// equivalent with respect to allocation sites in this graph
- protected ReachSet toCalleeContext( ReachSet rs,
- Integer hrnID,
- TempDescriptor tdSrc,
- Integer hrnSrcID,
- Integer hrnDstID,
- TypeDescriptor type,
- String field,
- boolean outOfContext
+ protected ReachSet toCalleeContext( ReachSet rs,
+ ExistPredSet preds,
+ Set<ReachTuple> oocTuples
) {
ReachSet out = ReachSet.factory();
while( asItr.hasNext() ) {
AllocSite as = asItr.next();
- stateCallee = Canonical.toCalleeContext( stateCallee, as );
- }
+ ReachState stateNew = ReachState.factory();
+ Iterator<ReachTuple> rtItr = stateCallee.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
- ExistPredSet preds;
+ // only translate this tuple if it is
+ // in the out-callee-context bag
+ if( !oocTuples.contains( rt ) ) {
+ stateNew = Canonical.add( stateNew, rt );
+ continue;
+ }
- if( outOfContext ) {
- preds = predsEmpty;
- } else {
- ExistPred pred;
- if( hrnID != null ) {
- assert tdSrc == null;
- assert hrnSrcID == null;
- assert hrnDstID == null;
- pred = ExistPred.factory( hrnID,
- stateCaller );
- } else {
- assert tdSrc != null || hrnSrcID != null;
- assert hrnDstID != null;
- pred = ExistPred.factory( tdSrc,
- hrnSrcID,
- hrnDstID,
- type,
- field,
- stateCaller,
- false );
+ int age = as.getAgeCategory( rt.getHrnID() );
+
+ // this is the current mapping, where 0, 1, 2S were allocated
+ // in the current context, 0?, 1? and 2S? were allocated in a
+ // previous context, and we're translating to a future context
+ //
+ // 0 -> 0?
+ // 1 -> 1?
+ // 2S -> 2S?
+ // 2S* -> 2S?*
+ //
+ // 0? -> 2S?
+ // 1? -> 2S?
+ // 2S? -> 2S?
+ // 2S?* -> 2S?*
+
+ if( age == AllocSite.AGE_notInThisSite ) {
+ // things not from the site just go back in
+ stateNew = Canonical.add( stateNew, rt );
+
+ } else if( age == AllocSite.AGE_summary ||
+ rt.isOutOfContext()
+ ) {
+ // the in-context summary and all existing out-of-context
+ // stuff all become
+ stateNew = Canonical.add( stateNew,
+ ReachTuple.factory( as.getSummary(),
+ true, // multi
+ rt.getArity(),
+ true // out-of-context
+ )
+ );
+ } else {
+ // otherwise everything else just goes to an out-of-context
+ // version, everything else the same
+ Integer I = as.getAge( rt.getHrnID() );
+ assert I != null;
+
+ assert !rt.isMultiObject();
+
+ stateNew = Canonical.add( stateNew,
+ ReachTuple.factory( rt.getHrnID(),
+ rt.isMultiObject(),
+ rt.getArity(),
+ true // out-of-context
+ )
+ );
+ }
}
- preds = ExistPredSet.factory( pred );
+
+ stateCallee = stateNew;
}
+ // attach the passed in preds
stateCallee = Canonical.attach( stateCallee,
preds );
Iterator<AllocSite> asItr = allocSites.iterator();
while( asItr.hasNext() ) {
AllocSite as = asItr.next();
- rsCaller = Canonical.toCallerContext( rs, as );
- }
+ rsCaller = Canonical.toCallerContext( rsCaller, as );
+ }
// then before adding each derived, now caller-context
// states to the output, attach the appropriate pred
stateCaller = Canonical.attach( stateCaller,
calleeStatesSatisfied.get( stateCallee )
);
- out = Canonical.union( out,
- stateCaller
- );
+ out = Canonical.add( out,
+ stateCaller
+ );
}
- }
- }
-
+ }
+ }
+
assert out.isCanonical();
return out;
}
boolean writeDebugDOTs
) {
- // the callee view is a new graph: DON'T MODIFY
- // *THIS* graph
- ReachGraph rg = new ReachGraph();
- // track what parts of this graph have already been
- // added to callee view, variables not needed.
- // Note that we need this because when we traverse
- // this caller graph for each parameter we may find
- // nodes and edges more than once (which the per-param
- // "visit" sets won't show) and we only want to create
- // an element in the new callee view one time
+ // first traverse this context to find nodes and edges
+ // that will be callee-reachable
+ Set<HeapRegionNode> reachableCallerNodes =
+ new HashSet<HeapRegionNode>();
+
+ // caller edges between callee-reachable nodes
+ Set<RefEdge> reachableCallerEdges =
+ new HashSet<RefEdge>();
+
+ // caller edges from arg vars, and the matching param index
+ // because these become a special edge in callee
+ Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
+ new Hashtable<RefEdge, Integer>();
+
+ // caller edges from local vars or callee-unreachable nodes
+ // (out-of-context sources) to callee-reachable nodes
+ Set<RefEdge> oocCallerEdges =
+ new HashSet<RefEdge>();
- // a conservative starting point is to take the
- // mechanically-reachable-from-arguments graph
- // as opposed to using reachability information
- // to prune the graph further
for( int i = 0; i < fmCallee.numParameters(); ++i ) {
- // for each parameter index, get the symbol in the
- // caller view and callee view
-
- // argument defined here is the symbol in the caller
TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
+ VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
- // parameter defined here is the symbol in the callee
- TempDescriptor tdParam = fmCallee.getParameter( i );
-
- // use these two VariableNode objects to translate
- // between caller and callee--its easy to compare
- // a HeapRegionNode across callee and caller because
- // they will have the same heap region ID
- VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
- VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
-
- // now traverse the calleR view using the argument to
- // build the calleE view which has the parameter symbol
Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
- toVisitInCaller.add( vnCaller );
+ toVisitInCaller.add( vnArgCaller );
+
while( !toVisitInCaller.isEmpty() ) {
RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
- RefSrcNode rsnCallee;
-
toVisitInCaller.remove( rsnCaller );
visitedInCaller.add( rsnCaller );
-
- // FIRST - setup the source end of an edge, and
- // remember the identifying info of the source
- // to build predicates
- TempDescriptor tdSrc = null;
- Integer hrnSrcID = null;
-
- if( rsnCaller == vnCaller ) {
- // if the caller node is the param symbol, we
- // have to do this translation for the callee
- rsnCallee = vnCallee;
- tdSrc = tdArg;
-
- } else {
- // otherwise the callee-view node is a heap
- // region with the same ID, that may or may
- // not have been created already
- assert rsnCaller instanceof HeapRegionNode;
-
- HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
- hrnSrcID = hrnSrcCaller.getID();
-
- if( !callerNodeIDsCopiedToCallee.contains( hrnSrcID ) ) {
-
- ExistPred pred =
- ExistPred.factory( hrnSrcID, null );
-
- ExistPredSet preds =
- ExistPredSet.factory( pred );
-
- rsnCallee =
- rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
- hrnSrcCaller.isSingleObject(),
- hrnSrcCaller.isNewSummary(),
- hrnSrcCaller.isFlagged(),
- false, // out-of-context?
- hrnSrcCaller.getType(),
- hrnSrcCaller.getAllocSite(),
- toCalleeContext( hrnSrcCaller.getInherent(), // in state
- hrnSrcCaller.getID(), // node pred
- null, null, null, null, null, // edge pred
- false ), // ooc pred
- toCalleeContext( hrnSrcCaller.getAlpha(), // in state
- hrnSrcCaller.getID(), // node pred
- null, null, null, null, null, // edge pred
- false ), // ooc pred
- preds,
- hrnSrcCaller.getDescription()
- );
-
- callerNodeIDsCopiedToCallee.add( hrnSrcID );
-
- } else {
- rsnCallee = rg.id2hrn.get( hrnSrcID );
- }
- }
-
- // SECOND - go over all edges from that source
Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
while( itrRefEdges.hasNext() ) {
RefEdge reCaller = itrRefEdges.next();
HeapRegionNode hrnCaller = reCaller.getDst();
- HeapRegionNode hrnCallee;
-
- // THIRD - setup destination ends of edges
- Integer hrnDstID = hrnCaller.getID();
- if( !callerNodeIDsCopiedToCallee.contains( hrnDstID ) ) {
-
- ExistPred pred =
- ExistPred.factory( hrnDstID, null );
-
- ExistPredSet preds =
- ExistPredSet.factory( pred );
-
- hrnCallee =
- rg.createNewHeapRegionNode( hrnDstID,
- hrnCaller.isSingleObject(),
- hrnCaller.isNewSummary(),
- hrnCaller.isFlagged(),
- false, // out-of-context?
- hrnCaller.getType(),
- hrnCaller.getAllocSite(),
- toCalleeContext( hrnCaller.getInherent(), // in state
- hrnDstID, // node pred
- null, null, null, null, null, // edge pred
- false ), // ooc pred
- toCalleeContext( hrnCaller.getAlpha(), // in state
- hrnDstID, // node pred
- null, null, null, null, null, // edge pred
- false ), // ooc pred
- preds,
- hrnCaller.getDescription()
- );
-
- callerNodeIDsCopiedToCallee.add( hrnDstID );
+ callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
+ reachableCallerNodes.add( hrnCaller );
+ if( reCaller.getSrc() instanceof HeapRegionNode ) {
+ reachableCallerEdges.add( reCaller );
} else {
- hrnCallee = rg.id2hrn.get( hrnDstID );
+ if( rsnCaller.equals( vnArgCaller ) ) {
+ reachableCallerArgEdges2paramIndex.put( reCaller, i );
+ } else {
+ oocCallerEdges.add( reCaller );
+ }
}
- // FOURTH - copy edge over if needed
- RefEdge reCallee = rsnCallee.getReferenceTo( hrnCallee,
- reCaller.getType(),
- reCaller.getField()
- );
- if( reCallee == null ) {
-
- ExistPred pred =
- ExistPred.factory( tdSrc,
- hrnSrcID,
- hrnDstID,
- reCaller.getType(),
- reCaller.getField(),
- null,
- rsnCaller instanceof VariableNode ); // out-of-context
-
- ExistPredSet preds =
- ExistPredSet.factory( pred );
-
- rg.addRefEdge( rsnCallee,
- hrnCallee,
- new RefEdge( rsnCallee,
- hrnCallee,
- reCaller.getType(),
- reCaller.getField(),
- toCalleeContext( reCaller.getBeta(), // in state
- null, // node pred
- tdSrc, // edge pred
- hrnSrcID, // edge pred
- hrnDstID, // edge pred
- reCaller.getType(), // edge pred
- reCaller.getField(), // edge pred
- false ), // ooc pred
- preds
- )
- );
- }
-
- // keep traversing nodes reachable from param i
- // that we haven't visited yet
if( !visitedInCaller.contains( hrnCaller ) ) {
toVisitInCaller.add( hrnCaller );
}
- } // end edge iteration
+ } // end edge iteration
} // end visiting heap nodes in caller
} // end iterating over parameters as starting points
- // find the set of edges in this graph with source
- // out-of-context (not in nodes copied) and have a
- // destination in context (one of nodes copied) as
- // a starting point for building out-of-context nodes
- Iterator<Integer> itrInContext =
+ // now collect out-of-context reach tuples and
+ // more out-of-context edges
+ Set<ReachTuple> oocTuples = new HashSet<ReachTuple>();
+
+ Iterator<Integer> itrInContext =
callerNodeIDsCopiedToCallee.iterator();
while( itrInContext.hasNext() ) {
Integer hrnID = itrInContext.next();
RefSrcNode rsnCallerAndOutContext =
edgeMightCross.getSrc();
- TypeDescriptor oocNodeType;
- ReachSet oocReach;
+ if( rsnCallerAndOutContext instanceof VariableNode ) {
+ // variables do not have out-of-context reach states,
+ // so jump out now
+ oocCallerEdges.add( edgeMightCross );
+ continue;
+ }
+
+ HeapRegionNode hrnCallerAndOutContext =
+ (HeapRegionNode) rsnCallerAndOutContext;
- TempDescriptor oocPredSrcTemp = null;
- Integer oocPredSrcID = null;
+ // is this source node out-of-context?
+ if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
+ // no, skip this edge
+ continue;
+ }
- if( rsnCallerAndOutContext instanceof VariableNode ) {
- // variables are always out-of-context
- oocNodeType = null;
- oocReach = rsetEmpty;
- oocPredSrcTemp =
- ((VariableNode)rsnCallerAndOutContext).getTempDescriptor();
+ // okay, we got one
+ oocCallerEdges.add( edgeMightCross );
- } else {
-
- HeapRegionNode hrnCallerAndOutContext =
- (HeapRegionNode) rsnCallerAndOutContext;
+ // add all reach tuples on the node to list
+ // of things that are out-of-context: insight
+ // if this node is reachable from someting that WAS
+ // in-context, then this node should already be in-context
+ Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
- // is this source node out-of-context?
- if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
- // no, skip this edge
- continue;
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+
+ oocTuples.add( rt );
}
+ }
+ }
+ }
- oocNodeType = hrnCallerAndOutContext.getType();
- oocReach = hrnCallerAndOutContext.getAlpha();
- oocPredSrcID = hrnCallerAndOutContext.getID();
- }
- // if we're here we've found an out-of-context edge
+ // the callee view is a new graph: DON'T MODIFY *THIS* graph
+ ReachGraph rg = new ReachGraph();
+
+ // add nodes to callee graph
+ Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
+ while( hrnItr.hasNext() ) {
+ HeapRegionNode hrnCaller = hrnItr.next();
- ExistPred pred =
- ExistPred.factory( oocPredSrcTemp,
- oocPredSrcID,
- hrnID,
- edgeMightCross.getType(),
- edgeMightCross.getField(),
- null,
- true ); // out-of-context
+ assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
+ assert !rg.id2hrn.containsKey( hrnCaller.getID() );
+
+ ExistPred pred = ExistPred.factory( hrnCaller.getID(), null );
+ ExistPredSet preds = ExistPredSet.factory( pred );
+
+ rg.createNewHeapRegionNode( hrnCaller.getID(),
+ hrnCaller.isSingleObject(),
+ hrnCaller.isNewSummary(),
+ hrnCaller.isFlagged(),
+ false, // out-of-context?
+ hrnCaller.getType(),
+ hrnCaller.getAllocSite(),
+ toCalleeContext( hrnCaller.getInherent(),
+ preds,
+ oocTuples
+ ),
+ toCalleeContext( hrnCaller.getAlpha(),
+ preds,
+ oocTuples
+ ),
+ preds,
+ hrnCaller.getDescription()
+ );
+ }
- ExistPredSet preds =
- ExistPredSet.factory( pred );
+ // add param edges to callee graph
+ Iterator argEdges =
+ reachableCallerArgEdges2paramIndex.entrySet().iterator();
+ while( argEdges.hasNext() ) {
+ Map.Entry me = (Map.Entry) argEdges.next();
+ RefEdge reArg = (RefEdge) me.getKey();
+ Integer index = (Integer) me.getValue();
+
+ TempDescriptor arg = fmCallee.getParameter( index );
+
+ VariableNode vnCallee =
+ rg.getVariableNodeFromTemp( arg );
+
+ HeapRegionNode hrnDstCaller = reArg.getDst();
+ HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
+ assert hrnDstCallee != null;
+
+ ExistPred pred =
+ ExistPred.factory( arg,
+ null,
+ hrnDstCallee.getID(),
+ reArg.getType(),
+ reArg.getField(),
+ null,
+ true, // out-of-callee-context
+ false // out-of-caller-context
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge reCallee =
+ new RefEdge( vnCallee,
+ hrnDstCallee,
+ reArg.getType(),
+ reArg.getField(),
+ toCalleeContext( reArg.getBeta(),
+ preds,
+ oocTuples
+ ),
+ preds
+ );
+
+ rg.addRefEdge( vnCallee,
+ hrnDstCallee,
+ reCallee
+ );
+ }
+ // add in-context edges to callee graph
+ Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
+ while( reItr.hasNext() ) {
+ RefEdge reCaller = reItr.next();
+ RefSrcNode rsnCaller = reCaller.getSrc();
+ assert rsnCaller instanceof HeapRegionNode;
+ HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
+ HeapRegionNode hrnDstCaller = reCaller.getDst();
+
+ HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
+ HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
+ assert hrnSrcCallee != null;
+ assert hrnDstCallee != null;
+
+ ExistPred pred =
+ ExistPred.factory( null,
+ hrnSrcCallee.getID(),
+ hrnDstCallee.getID(),
+ reCaller.getType(),
+ reCaller.getField(),
+ null,
+ false, // out-of-callee-context
+ false // out-of-caller-context
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
+
+ RefEdge reCallee =
+ new RefEdge( hrnSrcCallee,
+ hrnDstCallee,
+ reCaller.getType(),
+ reCaller.getField(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
+ ),
+ preds
+ );
+
+ rg.addRefEdge( hrnSrcCallee,
+ hrnDstCallee,
+ reCallee
+ );
+ }
+
+ // add out-of-context edges to callee graph
+ reItr = oocCallerEdges.iterator();
+ while( reItr.hasNext() ) {
+ RefEdge reCaller = reItr.next();
+ RefSrcNode rsnCaller = reCaller.getSrc();
+ HeapRegionNode hrnDstCaller = reCaller.getDst();
+ HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
+ assert hrnDstCallee != null;
+
+ TypeDescriptor oocNodeType;
+ ReachSet oocReach;
+ TempDescriptor oocPredSrcTemp = null;
+ Integer oocPredSrcID = null;
+ boolean outOfCalleeContext;
+ boolean outOfCallerContext;
+
+ if( rsnCaller instanceof VariableNode ) {
+ VariableNode vnCaller = (VariableNode) rsnCaller;
+ oocNodeType = null;
+ oocReach = rsetEmpty;
+ oocPredSrcTemp = vnCaller.getTempDescriptor();
+ outOfCalleeContext = true;
+ outOfCallerContext = false;
+
+ } else {
+ HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
+ assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
+ oocNodeType = hrnSrcCaller.getType();
+ oocReach = hrnSrcCaller.getAlpha();
+ oocPredSrcID = hrnSrcCaller.getID();
+ if( hrnSrcCaller.isOutOfContext() ) {
+ outOfCalleeContext = false;
+ outOfCallerContext = true;
+ } else {
+ outOfCalleeContext = true;
+ outOfCallerContext = false;
+ }
+ }
- HeapRegionNode hrnCalleeAndInContext =
- rg.id2hrn.get( hrnCallerAndInContext.getID() );
+ ExistPred pred =
+ ExistPred.factory( oocPredSrcTemp,
+ oocPredSrcID,
+ hrnDstCallee.getID(),
+ reCaller.getType(),
+ reCaller.getField(),
+ null,
+ outOfCalleeContext,
+ outOfCallerContext
+ );
+
+ ExistPredSet preds =
+ ExistPredSet.factory( pred );
- RefEdge oocEdgeExisting =
- rg.getOutOfContextReferenceTo( hrnCalleeAndInContext,
- oocNodeType,
- edgeMightCross.getType(),
- edgeMightCross.getField()
- );
+ RefEdge oocEdgeExisting =
+ rg.getOutOfContextReferenceTo( hrnDstCallee,
+ oocNodeType,
+ reCaller.getType(),
+ reCaller.getField()
+ );
- if( oocEdgeExisting == null ) {
- // we found a reference that crosses from out-of-context
- // to in-context, so build a special out-of-context node
- // for the callee IHM and its reference edge
-
+ if( oocEdgeExisting == null ) {
// for consistency, map one out-of-context "identifier"
// to one heap region node id, otherwise no convergence
- String oocid = "oocid"+
- fmCallee+
- hrnCalleeAndInContext.getIDString()+
- oocNodeType+
- edgeMightCross.getType()+
- edgeMightCross.getField();
+ String oocid = "oocid"+
+ fmCallee+
+ hrnDstCallee.getIDString()+
+ oocNodeType+
+ reCaller.getType()+
+ reCaller.getField();
- Integer oocHrnID = oocid2hrnid.get( oocid );
-
- HeapRegionNode hrnCalleeAndOutContext;
+ Integer oocHrnID = oocid2hrnid.get( oocid );
+
+ HeapRegionNode hrnCalleeAndOutContext;
+
+ if( oocHrnID == null ) {
+
+ hrnCalleeAndOutContext =
+ rg.createNewHeapRegionNode( null, // ID
+ false, // single object?
+ false, // new summary?
+ false, // flagged?
+ true, // out-of-context?
+ oocNodeType,
+ null, // alloc site, shouldn't be used
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ ),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ ),
+ preds,
+ "out-of-context"
+ );
+
+ oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
+
+ } else {
- if( oocHrnID == null ) {
+ // the mapping already exists, so see if node is there
+ hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
+ if( hrnCalleeAndOutContext == null ) {
+ // nope, make it
hrnCalleeAndOutContext =
- rg.createNewHeapRegionNode( null, // ID
+ rg.createNewHeapRegionNode( oocHrnID, // ID
false, // single object?
false, // new summary?
false, // flagged?
true, // out-of-context?
oocNodeType,
null, // alloc site, shouldn't be used
- toCalleeContext( oocReach, // in state
- null, // node pred
- null, null, null, null, null, // edge pred
- true // ooc pred
- ), // inherent
- toCalleeContext( oocReach, // in state
- null, // node pred
- null, null, null, null, null, // edge pred
- true // ooc pred
- ), // alpha
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ ),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ ),
preds,
"out-of-context"
);
-
- oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
-
} else {
-
- // the mapping already exists, so see if node is there
- hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
-
- if( hrnCalleeAndOutContext == null ) {
- // nope, make it
- hrnCalleeAndOutContext =
- rg.createNewHeapRegionNode( oocHrnID, // ID
- false, // single object?
- false, // new summary?
- false, // flagged?
- true, // out-of-context?
- oocNodeType,
- null, // alloc site, shouldn't be used
- toCalleeContext( oocReach, // in state
- null, // node pred
- null, null, null, null, null, // edge pred
- true // ooc pred
- ), // inherent
- toCalleeContext( oocReach, // in state
- null, // node pred
- null, null, null, null, null, // edge pred
- true // ooc pred
- ), // alpha
- preds,
- "out-of-context"
- );
- }
+ // otherwise it is there, so merge reachability
+ hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ )
+ )
+ );
}
+ }
- rg.addRefEdge( hrnCalleeAndOutContext,
- hrnCalleeAndInContext,
- new RefEdge( hrnCalleeAndOutContext,
- hrnCalleeAndInContext,
- edgeMightCross.getType(),
- edgeMightCross.getField(),
- toCalleeContext( edgeMightCross.getBeta(), // in state
- null, // node pred
- oocPredSrcTemp, // edge pred
- oocPredSrcID, // edge pred
- hrnCallerAndInContext.getID(), // edge pred
- edgeMightCross.getType(), // edge pred
- edgeMightCross.getField(), // edge pred
- false // ooc pred
- ),
- preds
- )
- );
-
+ rg.addRefEdge( hrnCalleeAndOutContext,
+ hrnDstCallee,
+ new RefEdge( hrnCalleeAndOutContext,
+ hrnDstCallee,
+ reCaller.getType(),
+ reCaller.getField(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
+ ),
+ preds
+ )
+ );
+
} else {
- // the out-of-context edge already exists
- oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
- toCalleeContext( edgeMightCross.getBeta(), // in state
- null, // node pred
- oocPredSrcTemp, // edge pred
- oocPredSrcID, // edge pred
- hrnCallerAndInContext.getID(), // edge pred
- edgeMightCross.getType(), // edge pred
- edgeMightCross.getField(), // edge pred
- false // ooc pred
- )
- )
- );
-
- oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
- edgeMightCross.getPreds()
- )
- );
+ // the out-of-context edge already exists
+ oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
+ )
+ )
+ );
- }
- }
- }
+ oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
+ reCaller.getPreds()
+ )
+ );
+
+ HeapRegionNode hrnCalleeAndOutContext =
+ (HeapRegionNode) oocEdgeExisting.getSrc();
+ hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ )
+ )
+ );
+
+
+ }
+ }
+
if( writeDebugDOTs ) {
try {
- rg.writeGraph( "calleeview", true, false, false, false, true, true );
+ rg.writeGraph( "calleeview",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
new Hashtable<String, Integer>();
+ // useful since many graphs writes in the method call debug code
+ private static boolean resolveMethodDebugDOTwriteLabels = true;
+ private static boolean resolveMethodDebugDOTselectTemps = true;
+ private static boolean resolveMethodDebugDOTpruneGarbage = true;
+ private static boolean resolveMethodDebugDOThideSubsetReach = false;
+ private static boolean resolveMethodDebugDOThideEdgeTaints = true;
+
+
public void
resolveMethodCall( FlatCall fc,
if( writeDebugDOTs ) {
try {
rgCallee.writeGraph( "callee",
- true, false, false, false, true, true );
- writeGraph( "caller00In",
- true, false, false, false, true, true,
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+
+ writeGraph( "caller00In",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints,
callerNodeIDsCopiedToCallee );
} catch( IOException e ) {}
}
calleeStatesSatisfied.put( stateCallee, predsIfSatis );
}
}
-
}
-
}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller20BeforeWipe",
- true, false, false, false, true, true );
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller30BeforeAddingNodes",
- true, false, false, false, true, true );
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller31BeforeAddingEdges",
- true, false, false, false, true, true );
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
+ // set these up during the next procedure so after
+ // the caller has all of its nodes and edges put
+ // back together we can propagate the callee's
+ // reach changes backwards into the caller graph
+ HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
+
+ Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
+ new Hashtable<RefEdge, ChangeSet>();
+
+
// 3.b) callee -> callee edges AND out-of-context -> callee
satisItr = calleeEdgesSatisfied.entrySet().iterator();
while( satisItr.hasNext() ) {
Set<RefSrcNode> oocCallers =
calleeEdges2oocCallerSrcMatches.get( reCallee );
+
+ boolean oocEdges = false;
if( oocCallers == null ) {
// there are no out-of-context matches, so it's
// to the callee so we ignore it in call site transfer
// shouldn't this NEVER HAPPEN?
assert false;
- //continue;
}
rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
+ oocEdges = true;
} else {
// otherwise source is in context, one region
// that should NOT be translated to shadow nodes
assert !oocCallers.isEmpty();
rsnCallers.addAll( oocCallers );
+ oocEdges = true;
}
// now make all caller edges we've identified from
while( rsnItr.hasNext() ) {
RefSrcNode rsnCaller = rsnItr.next();
- // TODO: beta rewrites
RefEdge reCaller = new RefEdge( rsnCaller,
hrnDstCaller,
reCallee.getType(),
calleeStatesSatisfied ),
preds
);
+
+ ChangeSet cs = ChangeSet.factory();
+ Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
+ while( rsItr.hasNext() ) {
+ ReachState state = rsItr.next();
+ ExistPredSet predsPreCallee = state.getPreds();
+
+ if( state.isEmpty() ) {
+ continue;
+ }
+
+ Iterator<ExistPred> predItr = predsPreCallee.iterator();
+ while( predItr.hasNext() ) {
+ ExistPred pred = predItr.next();
+ ReachState old = pred.ne_state;
+
+ if( old == null ) {
+ old = rstateEmpty;
+ }
+
+ cs = Canonical.add( cs,
+ ChangeTuple.factory( old,
+ state
+ )
+ );
+ }
+ }
+
// look to see if an edge with same field exists
// and merge with it, otherwise just add the edge
RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
);
if( edgeExisting != null ) {
edgeExisting.setBeta(
- Canonical.union( edgeExisting.getBeta(),
+ Canonical.unionORpreds( edgeExisting.getBeta(),
reCaller.getBeta()
)
);
reCaller.getPreds()
)
);
+
+ // for reach propagation
+ if( !cs.isEmpty() ) {
+ edgePlannedChanges.put(
+ edgeExisting,
+ Canonical.union( edgePlannedChanges.get( edgeExisting ),
+ cs
+ )
+ );
+ }
} else {
addRefEdge( rsnCaller, hrnDstCaller, reCaller );
+
+ // for reach propagation
+ if( !cs.isEmpty() ) {
+ edgesForPropagation.add( reCaller );
+ assert !edgePlannedChanges.containsKey( reCaller );
+ edgePlannedChanges.put( reCaller, cs );
+ }
}
}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller35BeforeAssignReturnValue",
- true, false, false, false, true, true );
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
+ if( writeDebugDOTs ) {
+ try {
+ writeGraph( "caller38propagateReach",
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
+ } catch( IOException e ) {}
+ }
+
+ // propagate callee reachability changes to the rest
+ // of the caller graph edges
+ HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
+
+ propagateTokensOverEdges( edgesForPropagation, // source edges
+ edgePlannedChanges, // map src edge to change set
+ edgesUpdated ); // list of updated edges
+
+ // commit beta' (beta<-betaNew)
+ Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
+ while( edgeItr.hasNext() ) {
+ edgeItr.next().applyBetaNew();
+ }
+
+
+
+
+
+
if( writeDebugDOTs ) {
try {
writeGraph( "caller40BeforeShadowMerge",
- true, false, false, false, true, true );
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller45BeforeUnshadow",
- true, false, false, false, true, true );
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller50BeforeGlobalSweep",
- true, false, false, false, true, true );
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
// 5.
- globalSweep();
+ if( !DISABLE_GLOBAL_SWEEP ) {
+ globalSweep();
+ }
if( writeDebugDOTs ) {
try {
writeGraph( "caller90AfterTransfer",
- true, false, false, false, true, true );
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
}
public void globalSweep() {
// boldB is part of the phase 1 sweep
- Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
+ // it has an in-context table and an out-of-context table
+ Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
+ new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
+
+ Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
- // visit every heap region to initialize alphaNew and calculate boldB
+ // visit every heap region to initialize alphaNew and betaNew,
+ // and make a map of every hrnID to the source nodes it should
+ // propagate forward from. In-context flagged hrnID's propagate
+ // from only the in-context node they name, but out-of-context
+ // ID's may propagate from several out-of-context nodes
+ Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
+ new Hashtable< Integer, Set<HeapRegionNode> >();
+
+ Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
+ new Hashtable< Integer, Set<HeapRegionNode> >();
+
+
Iterator itrHrns = id2hrn.entrySet().iterator();
while( itrHrns.hasNext() ) {
Map.Entry me = (Map.Entry) itrHrns.next();
assert rsetEmpty.equals( edge.getBetaNew() );
}
- // calculate boldB for this flagged node
+ // calculate boldB for this flagged node, or out-of-context node
if( hrn.isFlagged() ) {
-
- Hashtable<RefEdge, ReachSet> boldB_f =
- new Hashtable<RefEdge, ReachSet>();
-
- Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
+ assert !hrn.isOutOfContext();
+ assert !icID2srcs.containsKey( hrn.getID() );
+ Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
+ srcs.add( hrn );
+ icID2srcs.put( hrn.getID(), srcs );
+ }
- // initial boldB_f constraints
- Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
- while( itrRees.hasNext() ) {
- RefEdge edge = itrRees.next();
+ if( hrn.isOutOfContext() ) {
+ assert !hrn.isFlagged();
- assert !boldB.containsKey( edge );
- boldB_f.put( edge, edge.getBeta() );
+ Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
+ while( stateItr.hasNext() ) {
+ ReachState state = stateItr.next();
- assert !workSetEdges.contains( edge );
- workSetEdges.add( edge );
- }
+ Iterator<ReachTuple> rtItr = state.iterator();
+ while( rtItr.hasNext() ) {
+ ReachTuple rt = rtItr.next();
+ assert rt.isOutOfContext();
- // enforce the boldB_f constraint at edges until we reach a fixed point
- while( !workSetEdges.isEmpty() ) {
- RefEdge edge = workSetEdges.iterator().next();
- workSetEdges.remove( edge );
-
- Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
- while( itrPrime.hasNext() ) {
- RefEdge edgePrime = itrPrime.next();
+ Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
+ if( srcs == null ) {
+ srcs = new HashSet<HeapRegionNode>();
+ }
+ srcs.add( hrn );
+ oocID2srcs.put( rt.getHrnID(), srcs );
+ }
+ }
+ }
+ }
+
+ // calculate boldB for all hrnIDs identified by the above
+ // node traversal, propagating from every source
+ while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
+
+ Integer hrnID;
+ Set<HeapRegionNode> srcs;
+ boolean inContext;
+
+ if( !icID2srcs.isEmpty() ) {
+ Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
+ hrnID = (Integer) me.getKey();
+ srcs = (Set<HeapRegionNode>) me.getValue();
+ inContext = true;
+ icID2srcs.remove( hrnID );
+
+ } else {
+ assert !oocID2srcs.isEmpty();
+
+ Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
+ hrnID = (Integer) me.getKey();
+ srcs = (Set<HeapRegionNode>) me.getValue();
+ inContext = false;
+ oocID2srcs.remove( hrnID );
+ }
+
+
+ Hashtable<RefEdge, ReachSet> boldB_f =
+ new Hashtable<RefEdge, ReachSet>();
+
+ Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
- ReachSet prevResult = boldB_f.get( edgePrime );
- ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
+ Iterator<HeapRegionNode> hrnItr = srcs.iterator();
+ while( hrnItr.hasNext() ) {
+ HeapRegionNode hrn = hrnItr.next();
+
+ assert workSetEdges.isEmpty();
+
+ // initial boldB_f constraints
+ Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
+ while( itrRees.hasNext() ) {
+ RefEdge edge = itrRees.next();
+
+ assert !boldB_f.containsKey( edge );
+ boldB_f.put( edge, edge.getBeta() );
+
+ assert !workSetEdges.contains( edge );
+ workSetEdges.add( edge );
+ }
+
+ // enforce the boldB_f constraint at edges until we reach a fixed point
+ while( !workSetEdges.isEmpty() ) {
+ RefEdge edge = workSetEdges.iterator().next();
+ workSetEdges.remove( edge );
+
+ Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
+ while( itrPrime.hasNext() ) {
+ RefEdge edgePrime = itrPrime.next();
+
+ ReachSet prevResult = boldB_f.get( edgePrime );
+ ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
edgePrime.getBeta()
);
-
- if( prevResult == null ||
- Canonical.union( prevResult,
- intersection ).size() > prevResult.size() ) {
-
- if( prevResult == null ) {
- boldB_f.put( edgePrime,
- Canonical.union( edgePrime.getBeta(),
- intersection
- )
+
+ if( prevResult == null ||
+ Canonical.unionORpreds( prevResult,
+ intersection ).size()
+ > prevResult.size()
+ ) {
+
+ if( prevResult == null ) {
+ boldB_f.put( edgePrime,
+ Canonical.unionORpreds( edgePrime.getBeta(),
+ intersection
+ )
);
- } else {
- boldB_f.put( edgePrime,
- Canonical.union( prevResult,
- intersection
- )
+ } else {
+ boldB_f.put( edgePrime,
+ Canonical.unionORpreds( prevResult,
+ intersection
+ )
);
- }
- workSetEdges.add( edgePrime );
- }
- }
- }
-
- boldB.put( hrnID, boldB_f );
- }
+ }
+ workSetEdges.add( edgePrime );
+ }
+ }
+ }
+ }
+
+ if( inContext ) {
+ boldBic.put( hrnID, boldB_f );
+ } else {
+ boldBooc.put( hrnID, boldB_f );
+ }
}
Integer hrnID = (Integer) me.getKey();
HeapRegionNode hrn = (HeapRegionNode) me.getValue();
- // create the inherent hrnID from a flagged region
- // as an exception to removal below
- ReachTuple rtException =
- ReachTuple.factory( hrnID,
- !hrn.isSingleObject(),
- ReachTuple.ARITY_ONE,
- false // out-of-context
- );
+ // out-of-context nodes don't participate in the
+ // global sweep, they serve as sources for the pass
+ // performed above
+ if( hrn.isOutOfContext() ) {
+ continue;
+ }
+
+ // the inherent states of a region are the exception
+ // to removal as the global sweep prunes
+ ReachTuple rtException = ReachTuple.factory( hrnID,
+ !hrn.isSingleObject(),
+ ReachTuple.ARITY_ONE,
+ false // out-of-context
+ );
ChangeSet cts = ChangeSet.factory();
}
}
- // does boldB_ttOld allow this hrnID?
+ // does boldB allow this hrnID?
boolean foundState = false;
Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
while( incidentEdgeItr.hasNext() ) {
RefEdge incidentEdge = incidentEdgeItr.next();
- // if it isn't allowed, mark for removal
- Integer idOld = rtOld.getHrnID();
- assert id2hrn.containsKey( idOld );
- Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
- ReachSet boldB_ttOld_incident = B.get( incidentEdge );
- if( boldB_ttOld_incident != null &&
- boldB_ttOld_incident.contains( stateOld ) ) {
- foundState = true;
- }
- }
+ Hashtable<RefEdge, ReachSet> B;
+ if( rtOld.isOutOfContext() ) {
+ B = boldBooc.get( rtOld.getHrnID() );
+ } else {
+ assert id2hrn.containsKey( rtOld.getHrnID() );
+ B = boldBic.get( rtOld.getHrnID() );
+ }
+ if( B != null ) {
+ ReachSet boldB_rtOld_incident = B.get( incidentEdge );
+ if( boldB_rtOld_incident != null &&
+ boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
+ ) {
+ foundState = true;
+ }
+ }
+ }
+
if( !foundState ) {
markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
}
// if there is nothing marked, just move on
if( markedHrnIDs.isEmpty() ) {
- hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
- stateOld
- )
+ hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
+ stateOld
+ )
);
continue;
}
ReachTuple rtOld = rtItr.next();
if( !markedHrnIDs.containsTuple( rtOld ) ) {
- statePruned = Canonical.union( statePruned, rtOld );
+ statePruned = Canonical.add( statePruned, rtOld );
}
}
assert !stateOld.equals( statePruned );
- hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
- statePruned
- )
+ hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
+ statePruned
+ )
);
ChangeTuple ct = ChangeTuple.factory( stateOld,
statePruned
);
- cts = Canonical.union( cts, ct );
+ cts = Canonical.add( cts, ct );
}
// throw change tuple set on all incident edges
Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
while( nodeItr.hasNext() ) {
HeapRegionNode hrn = nodeItr.next();
- hrn.applyAlphaNew();
+
+ // as mentioned above, out-of-context nodes only serve
+ // as sources of reach states for the sweep, not part
+ // of the changes
+ if( hrn.isOutOfContext() ) {
+ assert hrn.getAlphaNew().equals( rsetEmpty );
+ } else {
+ hrn.applyAlphaNew();
+ }
+
Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
while( itrRes.hasNext() ) {
res.add( itrRes.next() );
edgePrime.getBetaNew()
);
- if( Canonical.union( prevResult,
- intersection
- ).size() > prevResult.size() ) {
+ if( Canonical.unionORpreds( prevResult,
+ intersection
+ ).size()
+ > prevResult.size()
+ ) {
+
edge.setBetaNew(
- Canonical.union( prevResult,
- intersection
- )
+ Canonical.unionORpreds( prevResult,
+ intersection
+ )
);
edgeWorkSet.add( edge );
}
// so make the new reachability set a union of the
// nodes' reachability sets
HeapRegionNode hrnB = id2hrn.get( idA );
- hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
+ hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
hrnA.getAlpha()
)
);
- // if hrnB is already dirty or hrnA is dirty,
- // the hrnB should end up dirty: TODO
- /*
- if( !hrnA.isClean() ) {
- hrnB.setIsClean( false );
- }
- */
+ hrnB.setPreds( Canonical.join( hrnB.getPreds(),
+ hrnA.getPreds()
+ )
+ );
}
}
// just replace this beta set with the union
assert edgeToMerge != null;
edgeToMerge.setBeta(
- Canonical.union( edgeToMerge.getBeta(),
+ Canonical.unionORpreds( edgeToMerge.getBeta(),
edgeA.getBeta()
)
);
- // TODO: what?
- /*
- if( !edgeA.isClean() ) {
- edgeToMerge.setIsClean( false );
- }
- */
+ edgeToMerge.setPreds(
+ Canonical.join( edgeToMerge.getPreds(),
+ edgeA.getPreds()
+ )
+ );
}
}
}
// so merge their reachability sets
else {
// just replace this beta set with the union
- edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
+ edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
edgeA.getBeta()
)
);
- // TODO: what?
- /*
- if( !edgeA.isClean() ) {
- edgeToMerge.setIsClean( false );
- }
- */
+ edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
+ edgeA.getPreds()
+ )
+ );
}
}
}
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers,
boolean hideSubsetReachability,
boolean hideEdgeTaints
) throws java.io.IOException {
writeLabels,
labelSelect,
pruneGarbage,
- writeReferencers,
hideSubsetReachability,
hideEdgeTaints,
null );
boolean writeLabels,
boolean labelSelect,
boolean pruneGarbage,
- boolean writeReferencers,
boolean hideSubsetReachability,
boolean hideEdgeTaints,
Set<Integer> callerNodeIDsCopiedToCallee
// only visit nodes worth writing out--for instance
// not every node at an allocation is referenced
// (think of it as garbage-collected), etc.
- if( !pruneGarbage ||
- (hrn.isFlagged() && hrn.getID() > 0) ||
- hrn.getDescription().startsWith( "param" ) ||
+ if( !pruneGarbage ||
hrn.isOutOfContext()
) {
bw,
null,
visited,
- writeReferencers,
hideSubsetReachability,
hideEdgeTaints,
callerNodeIDsCopiedToCallee );
if( labelSelect ) {
String labelStr = vn.getTempDescriptorString();
- if( labelStr.startsWith("___temp") ||
- labelStr.startsWith("___dst") ||
- labelStr.startsWith("___srctmp") ||
- labelStr.startsWith("___neverused")
+ if( labelStr.startsWith( "___temp" ) ||
+ labelStr.startsWith( "___dst" ) ||
+ labelStr.startsWith( "___srctmp" ) ||
+ labelStr.startsWith( "___neverused" )
) {
continue;
}
RefEdge edge = heapRegionsItr.next();
HeapRegionNode hrn = edge.getDst();
- if( pruneGarbage && !visited.contains( hrn ) ) {
+ if( !visited.contains( hrn ) ) {
traverseHeapRegionNodes( hrn,
bw,
null,
visited,
- writeReferencers,
hideSubsetReachability,
hideEdgeTaints,
callerNodeIDsCopiedToCallee );
BufferedWriter bw,
TempDescriptor td,
Set<HeapRegionNode> visited,
- boolean writeReferencers,
boolean hideSubsetReachability,
boolean hideEdgeTaints,
Set<Integer> callerNodeIDsCopiedToCallee
bw,
td,
visited,
- writeReferencers,
hideSubsetReachability,
hideEdgeTaints,
callerNodeIDsCopiedToCallee );
}
}
+
+ public Set<HeapRegionNode> findCommonReachableNodes(HeapRegionNode hrn1,
+ HeapRegionNode hrn2) {
+
+ Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
+ Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
+
+ Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
+ todoNodes1.add(hrn1);
+
+ Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
+ todoNodes2.add(hrn2);
+
+ // follow links until all reachable nodes have been found
+ while (!todoNodes1.isEmpty()) {
+ HeapRegionNode hrn = todoNodes1.iterator().next();
+ todoNodes1.remove(hrn);
+ reachableNodes1.add(hrn);
+
+ Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
+ while (edgeItr.hasNext()) {
+ RefEdge edge = edgeItr.next();
+
+ if (!reachableNodes1.contains(edge.getDst())) {
+ todoNodes1.add(edge.getDst());
+ }
+ }
+ }
+
+ while (!todoNodes2.isEmpty()) {
+ HeapRegionNode hrn = todoNodes2.iterator().next();
+ todoNodes2.remove(hrn);
+ reachableNodes2.add(hrn);
+
+ Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
+ while (edgeItr.hasNext()) {
+ RefEdge edge = edgeItr.next();
+
+ if (!reachableNodes2.contains(edge.getDst())) {
+ todoNodes2.add(edge.getDst());
+ }
+ }
+ }
+
+ Set<HeapRegionNode> intersection =
+ new HashSet<HeapRegionNode>( reachableNodes1 );
+
+ intersection.retainAll( reachableNodes2 );
+
+ return intersection;
+ }
+
+ public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
+ HeapRegionNode hrn2) {
+ assert hrn1 != null;
+ assert hrn2 != null;
+
+ // then get the various tokens for these heap regions
+ ReachTuple h1 = ReachTuple.factory(hrn1.getID(),
+ !hrn1.isSingleObject(), ReachTuple.ARITY_ONE, false);
+
+ int arity;
+ if(hrn1.isSingleObject){
+ arity=ReachTuple.ARITY_ONE;
+ }else{
+ arity=ReachTuple.ARITY_ZEROORMORE;
+ }
+ ReachTuple h1star = ReachTuple.factory(hrn1.getID(), !hrn1
+ .isSingleObject(), arity, false);
+
+ ReachTuple h2 = ReachTuple.factory(hrn2.getID(),
+ !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false);
+
+ if(hrn2.isSingleObject){
+ arity=ReachTuple.ARITY_ONE;
+ }else{
+ arity=ReachTuple.ARITY_ZEROORMORE;
+ }
+
+ ReachTuple h2star = ReachTuple.factory(hrn2.getID(), !hrn2
+ .isSingleObject(), arity, false);
+
+ // then get the merged beta of all out-going edges from these heap
+ // regions
+
+ ReachSet beta1 = ReachSet.factory();
+ Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
+ }
+
+ ReachSet beta2 = ReachSet.factory();
+ itrEdge = hrn2.iteratorToReferencees();
+ while (itrEdge.hasNext()) {
+ RefEdge edge = itrEdge.next();
+ beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
+ }
+
+ boolean aliasDetected = false;
+
+ // only do this one if they are different tokens
+ if (h1 != h2 && beta1.containsStateWithBoth(h1, h2)) {
+ aliasDetected = true;
+ }
+// if (beta1.containsStateWithBoth(h1plus, h2)) {
+// aliasDetected = true;
+// }
+ if (beta1.containsStateWithBoth(h1star, h2)) {
+ aliasDetected = true;
+ }
+// if (beta1.containsStateWithBoth(h1, h2plus)) {
+// aliasDetected = true;
+// }
+// if (beta1.containsStateWithBoth(h1plus, h2plus)) {
+// aliasDetected = true;
+// }
+// if (beta1.containsStateWithBoth(h1star, h2plus)) {
+// aliasDetected = true;
+// }
+ if (beta1.containsStateWithBoth(h1, h2star)) {
+ aliasDetected = true;
+ }
+// if (beta1.containsStateWithBoth(h1plus, h2star)) {
+// aliasDetected = true;
+// }
+ if (beta1.containsStateWithBoth(h1star, h2star)) {
+ aliasDetected = true;
+ }
+
+ if (h1 != h2 && beta2.containsStateWithBoth(h1, h2)) {
+ aliasDetected = true;
+ }
+// if (beta2.containsStateWithBoth(h1plus, h2)) {
+// aliasDetected = true;
+// }
+ if (beta2.containsStateWithBoth(h1star, h2)) {
+ aliasDetected = true;
+ }
+// if (beta2.containsStateWithBoth(h1, h2plus)) {
+// aliasDetected = true;
+// }
+// if (beta2.containsStateWithBoth(h1plus, h2plus)) {
+// aliasDetected = true;
+// }
+// if (beta2.containsStateWithBoth(h1star, h2plus)) {
+// aliasDetected = true;
+// }
+ if (beta2.containsStateWithBoth(h1, h2star)) {
+ aliasDetected = true;
+ }
+// if (beta2.containsStateWithBoth(h1plus, h2star)) {
+// aliasDetected = true;
+// }
+ if (beta2.containsStateWithBoth(h1star, h2star)) {
+ aliasDetected = true;
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if (aliasDetected) {
+ common = findCommonReachableNodes(hrn1, hrn2);
+ if (!(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP)) {
+ assert !common.isEmpty();
+ }
+ }
+
+ return common;
+ }
+ public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
+ Integer paramIndex1, Integer paramIndex2) {
+
+ // get parameter's heap regions
+ TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
+ VariableNode argVar1 = getVariableNodeFromTemp(paramTemp1);
+ RefEdge argEdge1 = argVar1.iteratorToReferencees().next();
+ HeapRegionNode hrnParam1 = argEdge1.getDst();
+
+ TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
+ VariableNode argVar2 = getVariableNodeFromTemp(paramTemp2);
+ RefEdge argEdge2 = argVar2.iteratorToReferencees().next();
+ HeapRegionNode hrnParam2 = argEdge2.getDst();
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
+
+ return common;
+ }
+
+ public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
+ Integer paramIndex, AllocSite as) {
+
+ // get parameter's heap regions
+ TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
+ VariableNode argVar = getVariableNodeFromTemp(paramTemp);
+ RefEdge argEdge = argVar.iteratorToReferencees().next();
+ HeapRegionNode hrnParam = argEdge.getDst();
+
+ // get summary node
+ HeapRegionNode hrnSummary=null;
+ if(id2hrn.containsKey(as.getSummary())){
+ // if summary node doesn't exist, ignore this case
+ hrnSummary = id2hrn.get(as.getSummary());
+ assert hrnSummary != null;
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if(hrnSummary!=null){
+ common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
+ }
+
+ // check for other nodes
+ for (int i = 0; i < as.getAllocationDepth(); ++i) {
+
+ assert id2hrn.containsKey(as.getIthOldest(i));
+ HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
+ assert hrnIthOldest != null;
+
+ common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
+
+ }
+
+ return common;
+ }
+
+ public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
+ AllocSite as2) {
+
+ // get summary node 1's alpha
+ Integer idSum1 = as1.getSummary();
+ HeapRegionNode hrnSum1=null;
+ if(id2hrn.containsKey(idSum1)){
+ hrnSum1 = id2hrn.get(idSum1);
+ }
+
+ // get summary node 2's alpha
+ Integer idSum2 = as2.getSummary();
+ HeapRegionNode hrnSum2=null;
+ if(id2hrn.containsKey(idSum2)){
+ hrnSum2 = id2hrn.get(idSum2);
+ }
+
+ Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
+ if(hrnSum1!=null && hrnSum2!=null){
+ common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
+ }
+
+ // check sum2 against alloc1 nodes
+ if(hrnSum2!=null){
+ 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;
+ common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
+ }
+ }
+
+ // 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;
+
+ if(hrnSum1!=null){
+ common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
+ }
+
+ // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
+ for (int j = 0; j < as1.getAllocationDepth(); ++j) {
+ Integer idI1 = as1.getIthOldest(j);
+
+ // if these are the same site, don't look for the same token, no
+ // alias.
+ // different tokens of the same site could alias together though
+ if (idI1.equals(idI2)) {
+ continue;
+ }
+
+ HeapRegionNode hrnI1 = id2hrn.get(idI1);
+
+ common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
+ }
+ }
+
+ return common;
+ }
+
}
projects / IRC.git / blobdiff