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( Set<ReachTuple> oocTuples,
- 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( rtItr.hasNext() ) {
ReachTuple rt = rtItr.next();
- // only translate this tuple if it is in the out-context bag
+ // only translate this tuple if it is
+ // in the out-callee-context bag
if( !oocTuples.contains( rt ) ) {
- stateNew = Canonical.union( stateNew, rt );
+ stateNew = Canonical.add( stateNew, rt );
continue;
}
if( age == AllocSite.AGE_notInThisSite ) {
// things not from the site just go back in
- stateNew = Canonical.union( stateNew, rt );
+ 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.union( stateNew,
- ReachTuple.factory( as.getSummary(),
- true, // multi
- rt.getArity(),
- true // out-of-context
- )
- );
+ 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
assert !rt.isMultiObject();
- stateNew = Canonical.union( stateNew,
- ReachTuple.factory( rt.getHrnID(),
- rt.isMultiObject(),
- rt.getArity(),
- true // out-of-context
- )
- );
+ stateNew = Canonical.add( stateNew,
+ ReachTuple.factory( rt.getHrnID(),
+ rt.isMultiObject(),
+ rt.getArity(),
+ true // out-of-context
+ )
+ );
}
}
stateCallee = stateNew;
}
-
-
- ExistPredSet preds;
-
- 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 );
- }
- preds = ExistPredSet.factory( pred );
- }
+ // attach the passed in preds
stateCallee = Canonical.attach( stateCallee,
preds );
stateCaller = Canonical.attach( stateCaller,
calleeStatesSatisfied.get( stateCallee )
);
- out = Canonical.union( out,
- stateCaller
- );
+ out = Canonical.add( out,
+ stateCaller
+ );
}
- }
+ }
}
assert out.isCanonical();
false, // out-of-context?
hrnCaller.getType(),
hrnCaller.getAllocSite(),
- toCalleeContext( oocTuples,
- hrnCaller.getInherent(), // in state
- hrnCaller.getID(), // node pred
- null, null, null, null, null, // edge pred
- false ), // ooc pred
- toCalleeContext( oocTuples,
- hrnCaller.getAlpha(), // in state
- hrnCaller.getID(), // node pred
- null, null, null, null, null, // edge pred
- false ), // ooc pred
+ toCalleeContext( hrnCaller.getInherent(),
+ preds,
+ oocTuples
+ ),
+ toCalleeContext( hrnCaller.getAlpha(),
+ preds,
+ oocTuples
+ ),
preds,
hrnCaller.getDescription()
);
reArg.getType(),
reArg.getField(),
null,
- false ); // out-of-context
+ true, // out-of-callee-context
+ false // out-of-caller-context
+ );
ExistPredSet preds =
ExistPredSet.factory( pred );
hrnDstCallee,
reArg.getType(),
reArg.getField(),
- toCalleeContext( oocTuples,
- reArg.getBeta(), // in state
- null, // node pred
- arg, // edge pred
- null, // edge pred
- hrnDstCallee.getID(), // edge pred
- reArg.getType(), // edge pred
- reArg.getField(), // edge pred
- false ), // ooc pred
+ toCalleeContext( reArg.getBeta(),
+ preds,
+ oocTuples
+ ),
preds
);
reCaller.getType(),
reCaller.getField(),
null,
- false ); // out-of-context
+ false, // out-of-callee-context
+ false // out-of-caller-context
+ );
ExistPredSet preds =
ExistPredSet.factory( pred );
hrnDstCallee,
reCaller.getType(),
reCaller.getField(),
- toCalleeContext( oocTuples,
- reCaller.getBeta(), // in state
- null, // node pred
- null, // edge pred
- hrnSrcCallee.getID(), // edge pred
- hrnDstCallee.getID(), // edge pred
- reCaller.getType(), // edge pred
- reCaller.getField(), // edge pred
- false ), // ooc pred
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
+ ),
preds
);
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();
+ oocPredSrcID = hrnSrcCaller.getID();
+ if( hrnSrcCaller.isOutOfContext() ) {
+ outOfCalleeContext = false;
+ outOfCallerContext = true;
+ } else {
+ outOfCalleeContext = true;
+ outOfCallerContext = false;
+ }
}
ExistPred pred =
reCaller.getType(),
reCaller.getField(),
null,
- true ); // out-of-context
+ outOfCalleeContext,
+ outOfCallerContext
+ );
ExistPredSet preds =
ExistPredSet.factory( pred );
true, // out-of-context?
oocNodeType,
null, // alloc site, shouldn't be used
- toCalleeContext( oocTuples,
- oocReach, // in state
- null, // node pred
- null, null, null, null, null, // edge pred
- true // ooc pred
- ), // inherent
- toCalleeContext( oocTuples,
- 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"
);
true, // out-of-context?
oocNodeType,
null, // alloc site, shouldn't be used
- toCalleeContext( oocTuples,
- oocReach, // in state
- null, // node pred
- null, null, null, null, null, // edge pred
- true // ooc pred
- ), // inherent
- toCalleeContext( oocTuples,
- 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"
);
+ } else {
+ // otherwise it is there, so merge reachability
+ hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ )
+ )
+ );
}
}
hrnDstCallee,
reCaller.getType(),
reCaller.getField(),
- toCalleeContext( oocTuples,
- reCaller.getBeta(), // in state
- null, // node pred
- oocPredSrcTemp, // edge pred
- oocPredSrcID, // edge pred
- hrnDstCaller.getID(), // edge pred
- reCaller.getType(), // edge pred
- reCaller.getField(), // edge pred
- false // ooc pred
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
),
preds
)
} else {
// the out-of-context edge already exists
- oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
- toCalleeContext( oocTuples,
- reCaller.getBeta(), // in state
- null, // node pred
- oocPredSrcTemp, // edge pred
- oocPredSrcID, // edge pred
- hrnDstCaller.getID(), // edge pred
- reCaller.getType(), // edge pred
- reCaller.getField(), // edge pred
- false // ooc pred
- )
+ oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
+ toCalleeContext( reCaller.getBeta(),
+ preds,
+ oocTuples
+ )
)
);
reCaller.getPreds()
)
);
+
+ HeapRegionNode hrnCalleeAndOutContext =
+ (HeapRegionNode) oocEdgeExisting.getSrc();
+ hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
+ toCalleeContext( oocReach,
+ preds,
+ oocTuples
+ )
+ )
+ );
+
}
}
if( writeDebugDOTs ) {
try {
rg.writeGraph( "calleeview",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ 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, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
- writeGraph( "caller00In",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true, // hide edge taints
+ 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, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller30BeforeAddingNodes",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller31BeforeAddingEdges",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
ChangeSet cs = ChangeSet.factory();
Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
while( rsItr.hasNext() ) {
- ReachState state = rsItr.next();
- ExistPredSet preds2 = state.getPreds();
- assert preds2.preds.size() == 1;
+ ReachState state = rsItr.next();
+ ExistPredSet predsPreCallee = state.getPreds();
if( state.isEmpty() ) {
continue;
}
- ExistPred pred = preds2.preds.iterator().next();
- ReachState old = pred.ne_state;
+ Iterator<ExistPred> predItr = predsPreCallee.iterator();
+ while( predItr.hasNext() ) {
+ ExistPred pred = predItr.next();
+ ReachState old = pred.ne_state;
- if( old == null ) {
- old = rstateEmpty;
- }
-
- assert old != null;
+ if( old == null ) {
+ old = rstateEmpty;
+ }
- cs = Canonical.union( cs,
+ 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()
)
);
if( writeDebugDOTs ) {
try {
writeGraph( "caller35BeforeAssignReturnValue",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller38propagateReach",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller40BeforeShadowMerge",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller45BeforeUnshadow",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller50BeforeGlobalSweep",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
if( writeDebugDOTs ) {
try {
writeGraph( "caller90AfterTransfer",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- true, // hide subset reachability states
- true ); // hide edge taints
+ resolveMethodDebugDOTwriteLabels,
+ resolveMethodDebugDOTselectTemps,
+ resolveMethodDebugDOTpruneGarbage,
+ resolveMethodDebugDOThideSubsetReach,
+ resolveMethodDebugDOThideEdgeTaints );
} catch( IOException e ) {}
}
}
);
if( prevResult == null ||
- Canonical.union( prevResult,
- intersection ).size() > prevResult.size() ) {
+ Canonical.unionORpreds( prevResult,
+ intersection ).size()
+ > prevResult.size()
+ ) {
if( prevResult == null ) {
boldB_f.put( edgePrime,
- Canonical.union( edgePrime.getBeta(),
- intersection
- )
+ Canonical.unionORpreds( edgePrime.getBeta(),
+ intersection
+ )
);
} else {
boldB_f.put( edgePrime,
- Canonical.union( prevResult,
- intersection
- )
+ Canonical.unionORpreds( prevResult,
+ intersection
+ )
);
}
workSetEdges.add( edgePrime );
if( B != null ) {
ReachSet boldB_rtOld_incident = B.get( incidentEdge );
if( boldB_rtOld_incident != null &&
- boldB_rtOld_incident.contains( stateOld ) ) {
+ boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
+ ) {
foundState = true;
}
}
// 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()
)
);
// just replace this beta set with the union
assert edgeToMerge != null;
edgeToMerge.setBeta(
- Canonical.union( edgeToMerge.getBeta(),
+ Canonical.unionORpreds( edgeToMerge.getBeta(),
edgeA.getBeta()
)
);
// 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()
)
);
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