public class ReachGraph {
// use to disable improvements for comparison
- protected static final boolean DISABLE_STRONG_UPDATES = false;
- protected static final boolean DISABLE_GLOBAL_SWEEP = false;
-
- // a special out-of-scope temp
- protected static final TempDescriptor tdReturn = new TempDescriptor("_Return___");
+ protected static boolean DISABLE_STRONG_UPDATES = false;
+ protected static boolean DISABLE_GLOBAL_SWEEP = false;
+ protected static boolean DISABLE_PREDICATES = false;
+
+ // a special out-of-scope temps
+ protected static TempDescriptor tdReturn;
+ protected static TempDescriptor tdStrLiteralBytes;
+
+ public static void initOutOfScopeTemps() {
+ tdReturn = new TempDescriptor("_Return___");
+
+ tdStrLiteralBytes =
+ new TempDescriptor("_strLiteralBytes___",
+ new TypeDescriptor(TypeDescriptor.CHAR).makeArray( state )
+ );
+ }
// predicate constants
public static final ExistPred predTrue = ExistPred.factory(); // if no args, true
referencee.removeReferencer(edge);
}
- // return whether at least one edge was removed
+
protected boolean clearRefEdgesFrom(RefSrcNode referencer,
TypeDescriptor type,
String field,
boolean removeAll) {
+ return clearRefEdgesFrom( referencer, type, field, removeAll, null, null );
+ }
+
+ // return whether at least one edge was removed
+ protected boolean clearRefEdgesFrom(RefSrcNode referencer,
+ TypeDescriptor type,
+ String field,
+ boolean removeAll,
+ Set<EdgeKey> edgeKeysRemoved,
+ FieldDescriptor fd) {
assert referencer != null;
boolean atLeastOneEdgeRemoved = false;
HeapRegionNode referencee = edge.getDst();
+ if( edgeKeysRemoved != null ) {
+ assert fd != null;
+ assert referencer instanceof HeapRegionNode;
+ edgeKeysRemoved.add( new EdgeKey( ((HeapRegionNode)referencer).getID(),
+ referencee.getID(),
+ fd )
+ );
+ }
+
removeRefEdge(referencer,
referencee,
edge.getType(),
//
////////////////////////////////////////////////////
+ public void assignTempEqualToStringLiteral(TempDescriptor x,
+ AllocSite asStringLiteral,
+ AllocSite asStringLiteralBytes,
+ FieldDescriptor fdStringBytesField) {
+ // model this to get points-to information right for
+ // pointers to string literals, even though it doesn't affect
+ // reachability paths in the heap
+ assignTempEqualToNewAlloc( x,
+ asStringLiteral );
+
+ assignTempEqualToNewAlloc( tdStrLiteralBytes,
+ asStringLiteralBytes );
+
+ assignTempXFieldFEqualToTempY( x,
+ fdStringBytesField,
+ tdStrLiteralBytes,
+ null,
+ false,
+ null,
+ null,
+ null );
+ }
+
+
public void assignTempXEqualToTempY(TempDescriptor x,
TempDescriptor y) {
assignTempXEqualToCastedTempY(x, y, null);
public void assignTempXEqualToTempYFieldF(TempDescriptor x,
TempDescriptor y,
FieldDescriptor f,
- FlatNode currentProgramPoint
+ FlatNode currentProgramPoint,
+ Set<EdgeKey> edgeKeysForLoad
) {
VariableNode lnX = getVariableNodeFromTemp(x);
continue;
}
+ // for definite reach analysis only
+ if( edgeKeysForLoad != null ) {
+ assert f != null;
+ edgeKeysForLoad.add( new EdgeKey( hrnY.getID(),
+ hrnHrn.getID(),
+ f )
+ );
+ }
+
+
TypeDescriptor tdNewEdge =
mostSpecificType(edgeHrn.getType(),
hrnHrn.getType()
public boolean assignTempXFieldFEqualToTempY(TempDescriptor x,
FieldDescriptor f,
TempDescriptor y,
- FlatNode currentProgramPoint
+ FlatNode currentProgramPoint,
+ boolean alreadyReachable,
+ Set<EdgeKey> edgeKeysRemoved,
+ Set<EdgeKey> edgeKeysAdded,
+ Set<DefiniteReachState.FdEntry> edgesToElideFromPropFd
) {
VariableNode lnX = getVariableNodeFromTemp(x);
if( !DISABLE_STRONG_UPDATES ) {
strongUpdateCond = true;
- boolean atLeastOne =
- clearRefEdgesFrom(hrnX,
- f.getType(),
- f.getSymbol(),
- false);
+ boolean atLeastOne = clearRefEdgesFrom(hrnX,
+ f.getType(),
+ f.getSymbol(),
+ false,
+ edgeKeysRemoved,
+ f);
if( atLeastOne ) {
edgeRemovedByStrongUpdate = true;
}
}
}
- // then do all token propagation
- itrXhrn = lnX.iteratorToReferencees();
- while( itrXhrn.hasNext() ) {
- RefEdge edgeX = itrXhrn.next();
- HeapRegionNode hrnX = edgeX.getDst();
- ReachSet betaX = edgeX.getBeta();
- ReachSet R = Canonical.intersection(hrnX.getAlpha(),
- edgeX.getBeta()
- );
- Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
- while( itrYhrn.hasNext() ) {
- RefEdge edgeY = itrYhrn.next();
- HeapRegionNode hrnY = edgeY.getDst();
- ReachSet O = edgeY.getBeta();
+ // definite reachability analysis can elide some edges from
+ // propagating reach information
+ Set<RefEdge> edgesToElideFromProp = null;
+ if( edgesToElideFromPropFd != null ) {
+ edgesToElideFromProp = new HashSet<RefEdge>();
+ Iterator<RefEdge> itrY = lnY.iteratorToReferencees();
+ while( itrY.hasNext() ) {
+ HeapRegionNode hrnSrc = itrY.next().getDst();
- // check for impossible edges
- if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
- impossibleEdges.add(edgeY);
- continue;
+ Iterator<RefEdge> itrhrn = hrnSrc.iteratorToReferencees();
+ while( itrhrn.hasNext() ) {
+ RefEdge edgeToElide = itrhrn.next();
+ String f0 = edgeToElide.getField();
+ HeapRegionNode hrnDst = edgeToElide.getDst();
+
+ // does this graph edge match a statically-named edge
+ // that def reach says we don't have to prop over?
+ for( DefiniteReachState.FdEntry entry : edgesToElideFromPropFd ) {
+ if( !entry.f0.getSymbol().equals( f0 ) ) {
+ continue;
+ }
+ boolean refByZ = false;
+ Iterator<RefEdge> itrRef = hrnDst.iteratorToReferencers();
+ while( itrRef.hasNext() ) {
+ RefEdge edgeZ = itrRef.next();
+ if( edgeZ.getSrc() instanceof VariableNode ) {
+ VariableNode vnZ = (VariableNode) edgeZ.getSrc();
+ if( vnZ.getTempDescriptor().equals( entry.z ) ) {
+ refByZ = true;
+ break;
+ }
+ }
+ }
+ if( refByZ ) {
+ // this graph edge matches the def reach edge, mark it for
+ // no propagation
+ edgesToElideFromProp.add( edgeToElide );
+ }
+ }
}
+ }
+ }
- // propagate tokens over nodes starting from hrnSrc, and it will
- // take care of propagating back up edges from any touched nodes
- ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R);
- propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
- // then propagate back just up the edges from hrn
- ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O);
- HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
- Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
- new Hashtable<RefEdge, ChangeSet>();
+ // definite reachability analysis can elide reachability propagation
+ if( !alreadyReachable ) {
- Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
- while( referItr.hasNext() ) {
- RefEdge edgeUpstream = referItr.next();
- todoEdges.add(edgeUpstream);
- edgePlannedChanges.put(edgeUpstream, Cx);
- }
+ // then do all token propagation
+ itrXhrn = lnX.iteratorToReferencees();
+ while( itrXhrn.hasNext() ) {
+ RefEdge edgeX = itrXhrn.next();
+ HeapRegionNode hrnX = edgeX.getDst();
+ ReachSet betaX = edgeX.getBeta();
+ ReachSet R = Canonical.intersection(hrnX.getAlpha(),
+ edgeX.getBeta()
+ );
- propagateTokensOverEdges(todoEdges,
- edgePlannedChanges,
- edgesWithNewBeta);
+ Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
+ while( itrYhrn.hasNext() ) {
+ RefEdge edgeY = itrYhrn.next();
+ HeapRegionNode hrnY = edgeY.getDst();
+ ReachSet O = edgeY.getBeta();
+
+ // check for impossible edges
+ if( !isSuperiorType(f.getType(), edgeY.getType() ) ) {
+ impossibleEdges.add(edgeY);
+ continue;
+ }
+
+ // propagate tokens over nodes starting from hrnSrc, and it will
+ // take care of propagating back up edges from any touched nodes
+ ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R);
+ propagateTokensOverNodes( hrnY,
+ Cy,
+ nodesWithNewAlpha,
+ edgesWithNewBeta,
+ edgesToElideFromProp );
+
+ // then propagate back just up the edges from hrn
+ ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O);
+ HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
+
+ Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
+ new Hashtable<RefEdge, ChangeSet>();
+
+ Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
+ while( referItr.hasNext() ) {
+ RefEdge edgeUpstream = referItr.next();
+ todoEdges.add(edgeUpstream);
+ edgePlannedChanges.put(edgeUpstream, Cx);
+ }
+
+ propagateTokensOverEdges( todoEdges,
+ edgePlannedChanges,
+ edgesWithNewBeta,
+ edgesToElideFromProp );
+ }
}
}
-
+
// apply the updates to reachability
Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
continue;
}
+
+ // for definite reach analysis only
+ if( edgeKeysAdded != null ) {
+ assert f != null;
+ edgeKeysAdded.add( new EdgeKey( hrnX.getID(),
+ hrnY.getID(),
+ f )
+ );
+
+
+ }
+
// prepare the new reference edge hrnX.f -> hrnY
TypeDescriptor tdNewEdge =
mostSpecificType(y.getType(),
currentProgramPoint);
}
+
+ ReachSet betaNew;
+ if( alreadyReachable ) {
+ betaNew = edgeY.getBeta();
+ } else {
+ betaNew = Canonical.pruneBy( edgeY.getBeta(),
+ hrnX.getAlpha() );
+ }
+
+
RefEdge edgeNew =
new RefEdge(hrnX,
hrnY,
tdNewEdge,
f.getSymbol(),
- Canonical.changePredsTo(
- Canonical.pruneBy(edgeY.getBeta(),
- hrnX.getAlpha()
- ),
- predsTrue
- ),
+ Canonical.changePredsTo( betaNew,
+ predsTrue ),
predsTrue,
taints
);
// after tokens have been aged, reset newest node's reachability
// and a brand new node has a "true" predicate
- hrn0.setAlpha(hrn0.getInherent() );
- hrn0.setPreds(predsTrue);
+ hrn0.setAlpha( Canonical.changePredsTo( hrn0.getInherent(), predsTrue ) );
+ hrn0.setPreds( predsTrue);
}
protected void propagateTokensOverNodes(HeapRegionNode nPrime,
ChangeSet c0,
HashSet<HeapRegionNode> nodesWithNewAlpha,
- HashSet<RefEdge> edgesWithNewBeta) {
+ HashSet<RefEdge> edgesWithNewBeta,
+ Set<RefEdge> edgesToElideProp ) {
HashSet<HeapRegionNode> todoNodes
= new HashSet<HeapRegionNode>();
Iterator<RefEdge> referItr = n.iteratorToReferencers();
while( referItr.hasNext() ) {
RefEdge edge = referItr.next();
+
+ if( edgesToElideProp != null && edgesToElideProp.contains( edge ) ) {
+ continue;
+ }
todoEdges.add(edge);
if( !edgePlannedChanges.containsKey(edge) ) {
Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
while( refeeItr.hasNext() ) {
RefEdge edgeF = refeeItr.next();
+
+ if( edgesToElideProp != null && edgesToElideProp.contains( edgeF ) ) {
+ continue;
+ }
+
HeapRegionNode m = edgeF.getDst();
ChangeSet changesToPass = ChangeSet.factory();
propagateTokensOverEdges(todoEdges,
edgePlannedChanges,
- edgesWithNewBeta
- );
+ edgesWithNewBeta,
+ edgesToElideProp);
}
protected void propagateTokensOverEdges(HashSet <RefEdge> todoEdges,
Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
- HashSet <RefEdge> edgesWithNewBeta) {
+ HashSet <RefEdge> edgesWithNewBeta,
+ Set<RefEdge> edgesToElideProp ) {
// first propagate all change tuples everywhere they can go
while( !todoEdges.isEmpty() ) {
while( referItr.hasNext() ) {
RefEdge edgeF = referItr.next();
+ if( edgesToElideProp != null && edgesToElideProp.contains( edgeF ) ) {
+ continue;
+ }
+
if( !edgePlannedChanges.containsKey(edgeF) ) {
edgePlannedChanges.put(edgeF,
ChangeSet.factory()
predNodeOrEdge.e_hrnDstID,
predNodeOrEdge.e_type,
predNodeOrEdge.e_field,
- stateCallee,
+ stateCaller,
null,
predNodeOrEdge.e_srcOutCalleeContext,
predNodeOrEdge.e_srcOutCallerContext
// 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>();
+ // NOTE! One argument may be passed in as more than one parameter,
+ // so map to a set of parameter indices!
+ Hashtable< RefEdge, Set<Integer> > reachableCallerArgEdges2paramIndices =
+ new Hashtable< RefEdge, Set<Integer> >();
// caller edges from local vars or callee-unreachable nodes
// (out-of-context sources) to callee-reachable nodes
if( reCaller.getSrc() instanceof HeapRegionNode ) {
reachableCallerEdges.add(reCaller);
} else {
+
if( rsnCaller.equals(vnArgCaller) ) {
- reachableCallerArgEdges2paramIndex.put(reCaller, i);
+ Set<Integer> pIndices =
+ reachableCallerArgEdges2paramIndices.get( reCaller );
+
+ if( pIndices == null ) {
+ pIndices = new HashSet<Integer>();
+ reachableCallerArgEdges2paramIndices.put( reCaller, pIndices );
+ }
+ pIndices.add( i );
+
} else {
oocCallerEdges.add(reCaller);
}
} // end iterating over parameters as starting points
+
// now collect out-of-callee-context IDs and
// map them to whether the ID is out of the caller
// context as well
// add param edges to callee graph
Iterator argEdges =
- reachableCallerArgEdges2paramIndex.entrySet().iterator();
+ reachableCallerArgEdges2paramIndices.entrySet().iterator();
while( argEdges.hasNext() ) {
- Map.Entry me = (Map.Entry)argEdges.next();
- RefEdge reArg = (RefEdge) me.getKey();
- Integer index = (Integer) me.getValue();
+ Map.Entry me = (Map.Entry) argEdges.next();
+ RefEdge reArg = (RefEdge) me.getKey();
+ Set<Integer> pInxs = (Set<Integer>) me.getValue();
- VariableNode vnCaller = (VariableNode) reArg.getSrc();
+ VariableNode vnCaller = (VariableNode) reArg.getSrc();
TempDescriptor argCaller = vnCaller.getTempDescriptor();
- TempDescriptor paramCallee = fmCallee.getParameter(index);
- VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
-
HeapRegionNode hrnDstCaller = reArg.getDst();
HeapRegionNode hrnDstCallee = rg.id2hrn.get(hrnDstCaller.getID() );
assert hrnDstCallee != null;
ExistPredSet preds =
ExistPredSet.factory(pred);
- RefEdge reCallee =
- new RefEdge(vnCallee,
- hrnDstCallee,
- reArg.getType(),
- reArg.getField(),
- toCalleeContext(reArg.getBeta(),
- preds,
- oocHrnIdOoc2callee
- ),
- preds,
- toCalleeContext(reArg.getTaints(),
- preds)
- );
+ for( Integer index: pInxs ) {
- rg.addRefEdge(vnCallee,
- hrnDstCallee,
- reCallee
- );
+ TempDescriptor paramCallee = fmCallee.getParameter(index);
+ VariableNode vnCallee = rg.getVariableNodeFromTemp(paramCallee);
+
+ RefEdge reCallee =
+ new RefEdge(vnCallee,
+ hrnDstCallee,
+ reArg.getType(),
+ reArg.getField(),
+ toCalleeContext(reArg.getBeta(),
+ preds,
+ oocHrnIdOoc2callee
+ ),
+ preds,
+ toCalleeContext(reArg.getTaints(),
+ preds)
+ );
+
+ rg.addRefEdge(vnCallee,
+ hrnDstCallee,
+ reCallee
+ );
+ }
}
// add in-context edges to callee graph
}
}
- assert hrnCalleeAndOutContext.reachHasOnlyOOC();
+ if( !DISABLE_GLOBAL_SWEEP ) {
+ assert hrnCalleeAndOutContext.reachHasOnlyOOC();
+ }
rg.addRefEdge(hrnCalleeAndOutContext,
hrnDstCallee,
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 resolveMethodDebugDOThideReach = true;
+ private static boolean resolveMethodDebugDOThideReach = false;
private static boolean resolveMethodDebugDOThideSubsetReach = true;
- private static boolean resolveMethodDebugDOThidePreds = true;
- private static boolean resolveMethodDebugDOThideEdgeTaints = false;
+ private static boolean resolveMethodDebugDOThidePreds = false;
+ private static boolean resolveMethodDebugDOThideEdgeTaints = true;
static String debugGraphPrefix;
static int debugCallSiteVisitCounter;
new Hashtable< RefEdge, Set<RefSrcNode> >();
+
Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
while( meItr.hasNext() ) {
Map.Entry me = (Map.Entry)meItr.next();
// should have, and it is inefficient to find this again later
ExistPredSet predsIfSatis =
hrnCallee.getPreds().isSatisfiedBy(this,
- callerNodeIDsCopiedToCallee
- );
+ callerNodeIDsCopiedToCallee,
+ null);
if( predsIfSatis != null ) {
calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
continue;
}
+
+
// since the node is coming over, find out which reach
// states on it should come over, too
assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
predsIfSatis =
stateCallee.getPreds().isSatisfiedBy(this,
- callerNodeIDsCopiedToCallee
- );
+ callerNodeIDsCopiedToCallee,
+ null);
if( predsIfSatis != null ) {
Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
predsIfSatis =
hrnSrcCallee.getPreds().isSatisfiedBy(this,
- callerNodeIDsCopiedToCallee
- );
+ callerNodeIDsCopiedToCallee,
+ null);
if( predsIfSatis != null ) {
calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
} else {
} else {
// hrnSrcCallee is out-of-context
-
assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
- // is the target node in the caller?
- HeapRegionNode hrnDstCaller = this.id2hrn.get(hrnCallee.getID() );
- if( hrnDstCaller == null ) {
- continue;
- }
-
- Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
- while( reDstItr.hasNext() ) {
- // the edge and field (either possibly null) must match
- RefEdge reCaller = reDstItr.next();
-
- if( !reCaller.typeEquals(reCallee.getType() ) ||
- !reCaller.fieldEquals(reCallee.getField() )
- ) {
- continue;
- }
-
- RefSrcNode rsnCaller = reCaller.getSrc();
- if( rsnCaller instanceof VariableNode ) {
-
- // a variable node matches an OOC region with null type
- if( hrnSrcCallee.getType() != null ) {
- continue;
- }
-
- } else {
- // otherwise types should match
- HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
- if( hrnSrcCallee.getType() == null ) {
- if( hrnCallerSrc.getType() != null ) {
- continue;
- }
- } else {
- if( !hrnSrcCallee.getType().equals(hrnCallerSrc.getType() ) ) {
- continue;
- }
- }
- }
-
- rsnCallers.add(rsnCaller);
- matchedOutOfContext = true;
- }
+ // use the isSatisfiedBy with a non-null callers set to capture
+ // nodes in the caller that match the predicates
+ reCallee.getPreds().isSatisfiedBy( this,
+ callerNodeIDsCopiedToCallee,
+ rsnCallers );
if( !rsnCallers.isEmpty() ) {
+ matchedOutOfContext = true;
calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
}
}
predsIfSatis =
reCallee.getPreds().isSatisfiedBy(this,
- callerNodeIDsCopiedToCallee
- );
+ callerNodeIDsCopiedToCallee,
+ null);
+
if( predsIfSatis != null ) {
calleeEdgesSatisfied.put(reCallee, predsIfSatis);
predsIfSatis =
stateCallee.getPreds().isSatisfiedBy(this,
- callerNodeIDsCopiedToCallee
- );
+ callerNodeIDsCopiedToCallee,
+ null);
if( predsIfSatis != null ) {
Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
predsIfSatis =
tCallee.getPreds().isSatisfiedBy(this,
- callerNodeIDsCopiedToCallee
- );
+ callerNodeIDsCopiedToCallee,
+ null);
if( predsIfSatis != null ) {
Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
AllocSite as = hrnCallee.getAllocSite();
allocSites.add(as);
-
+
Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
// 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
+ propagateTokensOverEdges( edgesForPropagation, // source edges
+ edgePlannedChanges, // map src edge to change set
+ edgesUpdated, // list of updated edges
+ null );
// commit beta' (beta<-betaNew)
Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
propagateTokensOverEdges(edgesForPropagation,
edgePlannedChanges,
- edgesUpdated);
+ edgesUpdated,
+ null);
// at the end of the 1st phase reference edges have
// beta, betaNew that correspond to beta and betaR
- static boolean dbgEquals = false;
+ static public boolean dbgEquals = false;
// it is necessary in the equals() member functions
// there is an edge in the right place with the right field,
// but do they have the same attributes?
- if( edgeA.getBeta().equals(edgeB.getBeta() ) &&
- edgeA.equalsPreds(edgeB)
- ) {
+ if( edgeA.equalsIncludingBetaPredsTaints( edgeB ) ) {
edgeFound = true;
}
}
//System.out.println( "*** Asking if A is no smaller than B ***" );
-
Iterator iA = rgA.id2hrn.entrySet().iterator();
while( iA.hasNext() ) {
Map.Entry meA = (Map.Entry)iA.next();
System.out.println(" regions smaller");
return false;
}
-
- //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
- /* NOT EQUALS, NO SMALLER THAN!
- if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
- System.out.println( " regions smaller" );
- return false;
- }
- */
}
// this works just fine, no smaller than
System.out.println(" edges smaller:");
return false;
}
-
- // REMEMBER, IS NO SMALLER THAN
- /*
- System.out.println( " edges smaller" );
- return false;
- }
- */
-
}
}
try {
// remove all non-word characters from the graph name so
// the filename and identifier in dot don't cause errors
- graphName = graphName.replaceAll("[\\W]", "");
+ // jjenista - also replace underscore '_' to prevent some
+ // really, really long names from IHMS debugging
+ graphName = graphName.replaceAll("[\\W_]", "");
BufferedWriter bw =
new BufferedWriter(new FileWriter(graphName+".dot") );
public Set<TempDescriptor> getInaccessibleVars() {
return inaccessibleVars;
}
+
+
+
+
+ public Set<Alloc> canPointTo( TempDescriptor x ) {
+
+ if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
+ // if we don't care to track it, return null which means
+ // "a client of this result shouldn't care either"
+ return HeapAnalysis.DONTCARE_PTR;
+ }
+
+ Set<Alloc> out = new HashSet<Alloc>();
+
+ VariableNode vn = getVariableNodeNoMutation( x );
+ if( vn == null ) {
+ // the empty set means "can't point to anything"
+ return out;
+ }
+
+ Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ HeapRegionNode hrn = edgeItr.next().getDst();
+ out.add( hrn.getAllocSite() );
+ }
+
+ return out;
+ }
+
+
+
+ public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
+ String field,
+ TypeDescriptor fieldType ) {
+
+ if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
+ // if we don't care to track it, return null which means
+ // "a client of this result shouldn't care either"
+ return HeapAnalysis.DONTCARE_DREF;
+ }
+
+ Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
+
+ VariableNode vn = getVariableNodeNoMutation( x );
+ if( vn == null ) {
+ // the empty table means "x can't point to anything"
+ return out;
+ }
+
+ Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ HeapRegionNode hrn = edgeItr.next().getDst();
+ Alloc key = hrn.getAllocSite();
+
+ if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
+ // if we don't care to track it, put no entry which means
+ // "a client of this result shouldn't care either"
+ out.put( key, HeapAnalysis.DONTCARE_PTR );
+ continue;
+ }
+
+ Set<Alloc> moreValues = new HashSet<Alloc>();
+ Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
+ while( edgeItr2.hasNext() ) {
+ RefEdge edge = edgeItr2.next();
+
+ if( field.equals( edge.getField() ) ) {
+ moreValues.add( edge.getDst().getAllocSite() );
+ }
+ }
+
+ if( out.containsKey( key ) ) {
+ out.get( key ).addAll( moreValues );
+ } else {
+ out.put( key, moreValues );
+ }
+ }
+
+ return out;
+ }
+
+
+
+ // for debugging
+ public TempDescriptor findVariableByName( String name ) {
+
+ for( TempDescriptor td: td2vn.keySet() ) {
+ if( td.getSymbol().contains( name ) ) {
+ return td;
+ }
+ }
+
+ return null;
+ }
+
+
+ public String countGraphElements() {
+ long numNodes = 0;
+ long numEdges = 0;
+ long numNodeStates = 0;
+ long numEdgeStates = 0;
+ long numNodeStateNonzero = 0;
+ long numEdgeStateNonzero = 0;
+
+ for( HeapRegionNode node : id2hrn.values() ) {
+ numNodes++;
+ numNodeStates += node.getAlpha().numStates();
+ numNodeStateNonzero += node.getAlpha().numNonzeroTuples();
+
+ // all edges in the graph point TO a heap node, so scanning
+ // all referencers of all nodes gets every edge
+ Iterator<RefEdge> refItr = node.iteratorToReferencers();
+ while( refItr.hasNext() ) {
+ RefEdge edge = refItr.next();
+
+ numEdges++;
+ numEdgeStates += edge.getBeta().numStates();
+ numEdgeStateNonzero += edge.getBeta().numNonzeroTuples();
+ }
+ }
+
+ return
+ "################################################\n"+
+ "Nodes = "+numNodes+"\n"+
+ "Edges = "+numEdges+"\n"+
+ "Node states = "+numNodeStates+"\n"+
+ "Edge states = "+numEdgeStates+"\n"+
+ "Node non-zero tuples = "+numNodeStateNonzero+"\n"+
+ "Edge non-zero tuples = "+numEdgeStateNonzero+"\n"+
+ "################################################\n";
+ }
}
projects / IRC.git / blobdiff