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___");
+ // 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,
+ 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,
+ Set<EdgeKey> edgeKeysRemoved,
+ Set<EdgeKey> edgeKeysAdded
) {
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;
}
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(),
// 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);
}
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
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 =
- 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;
+ }
}
projects / IRC.git / blobdiff