public String toString() {
return "allocSite" + id;
}
+
+ public String toStringVerbose() {
+ return "allocSite" + id + " "+type.toPrettyString();
+ }
}
TaskDescriptor td = (TaskDescriptor) taskItr.next();
bw.write("\n---------"+td+"--------\n");
+ bw.flush();
HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
if( !outerChecked.contains(as2) &&
createsPotentialAliases(td, as1, as2) ) {
+ foundSomeAlias = true;
bw.write("Potential alias between "+as1+" and "+as2+".\n");
}
}
// data from the compiler
private State state;
+ private TypeUtil typeUtil;
private CallGraph callGraph;
private int allocationDepth;
// this analysis generates an ownership graph for every task
// in the program
public OwnershipAnalysis(State state,
+ TypeUtil tu,
CallGraph callGraph,
int allocationDepth,
boolean writeFinalGraphs,
boolean writeAllUpdates) throws java.io.IOException {
this.state = state;
+ this.typeUtil = tu;
this.callGraph = callGraph;
this.allocationDepth = allocationDepth;
this.writeFinalGraphs = writeFinalGraphs;
Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
while( dItr.hasNext() ) {
Descriptor d = dItr.next();
- OwnershipGraph og = new OwnershipGraph(allocationDepth);
+ OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
FlatMethod fm;
if( d instanceof MethodDescriptor ) {
System.out.println("Previsiting " + d);
- analyzeFlatNode(d, fm, null, og);
+ og = analyzeFlatNode(d, fm, null, og);
setGraphForDescriptor(d, og);
}
// perform this node's contributions to the ownership
// graph on a new copy, then compare it to the old graph
// at this node to see if anything was updated.
- OwnershipGraph og = new OwnershipGraph(allocationDepth);
+ OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
// start by merging all node's parents' graphs
for( int i = 0; i < fn.numPrev(); ++i ) {
// apply the analysis of the flat node to the
// ownership graph made from the merge of the
// parent graphs
- analyzeFlatNode(mDesc,
- fn,
- returnNodesToCombineForCompleteOwnershipGraph,
- og);
+ og = analyzeFlatNode(mDesc,
+ fn,
+ returnNodesToCombineForCompleteOwnershipGraph,
+ og);
// if the results of the new graph are different from
// the current graph at this node, replace the graph
// end by merging all return nodes into a complete
// ownership graph that represents all possible heap
// states after the flat method returns
- OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth);
+ OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth, typeUtil);
Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
while( retItr.hasNext() ) {
FlatReturnNode frn = (FlatReturnNode) retItr.next();
}
- private void
+ private OwnershipGraph
analyzeFlatNode(Descriptor methodDesc,
FlatNode fn,
HashSet<FlatReturnNode> setRetNodes,
}
// then remember it
- OwnershipGraph ogResult = new OwnershipGraph(allocationDepth);
+ OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil);
ogResult.merge(og);
mapFlatMethodToInitialParamAllocGraph.put(fm, ogResult);
FlatCall fc = (FlatCall) fn;
MethodDescriptor md = fc.getMethod();
FlatMethod flatm = state.getMethodFlat(md);
- OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth);
+ OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth, typeUtil);
if( md.isStatic() ) {
// a static method is simply always the same, makes life easy
// don't alter the working graph (og) until we compute a result for every
// possible callee, merge them all together, then set og to that
- OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth);
+ OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil);
ogCopy.merge(og);
OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd);
setRetNodes.add(frn);
break;
}
+
+ return og;
}
private OwnershipGraph getGraphFromFlatNode(FlatNode fn) {
if( !mapFlatNodeToOwnershipGraph.containsKey(fn) ) {
- mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth) );
+ mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth, typeUtil) );
}
return mapFlatNodeToOwnershipGraph.get(fn);
Iterator asItr = asSet.iterator();
while( asItr.hasNext() ) {
AllocationSite as = (AllocationSite) asItr.next();
- if( as.getType().getClassDesc().hasFlags() ) {
- asSetTotal.add(as);
+ TypeDescriptor typed = as.getType();
+ if( typed != null ) {
+ ClassDescriptor cd = typed.getClassDesc();
+ if( cd != null && cd.hasFlags() ) {
+ asSetTotal.add(as);
+ }
}
}
public class OwnershipGraph {
private int allocationDepth;
+ private TypeUtil typeUtil;
// there was already one other very similar reason
// for traversing heap nodes that is no longer needed
- public OwnershipGraph(int allocationDepth) {
+ public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
this.allocationDepth = allocationDepth;
+ this.typeUtil = typeUtil;
id2hrn = new Hashtable<Integer, HeapRegionNode>();
td2ln = new Hashtable<TempDescriptor, LabelNode >();
Iterator srcItr = possibleCallerSrcs.iterator();
while( srcItr.hasNext() ) {
HeapRegionNode src = (HeapRegionNode) srcItr.next();
-
- // check that if this source node has a definite type that
- // it also has the appropriate field, otherwise prune this
- AllocationSite asSrc = src.getAllocationSite();
- if( asSrc != null ) {
- boolean foundField = false;
- TypeDescriptor tdSrc = asSrc.getType();
- if( tdSrc != null && tdSrc.isClass() ) {
- Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
- while( fieldsSrcItr.hasNext() ) {
- FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
- if( fd == edgeCallee.getFieldDesc() ) {
- foundField = true;
- break;
- }
- }
- if( !foundField ) {
- // prune this source node possibility
- continue;
- }
- }
+
+ if( !hasMatchingField( src, edgeCallee ) ) {
+ // prune this source node possibility
+ continue;
}
Iterator dstItr = possibleCallerDsts.iterator();
while( dstItr.hasNext() ) {
HeapRegionNode dst = (HeapRegionNode) dstItr.next();
- // check if this dst node has a definite type and
- // if it matches the callee edge
- AllocationSite asDst = dst.getAllocationSite();
- if( asDst != null && edgeCallee.getFieldDesc() != null ) {
- if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) {
- continue;
- }
- if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) {
- continue;
- }
- if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
- if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) {
- continue;
- }
- }
+ if( !hasMatchingType( edgeCallee, dst ) ) {
+ // prune
+ continue;
}
// otherwise the caller src and dst pair can match the edge, so make it
while( itrHrn.hasNext() ) {
HeapRegionNode hrnCaller = itrHrn.next();
- // check if this dst node has a definite type and
- // if it matches the callee edge
- // check if this dst node has a definite type and
- // if it matches the callee edge
- AllocationSite asDst = hrnCaller.getAllocationSite();
- if( asDst != null && edgeCallee.getFieldDesc() != null ) {
- if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) {
- continue;
- }
- if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) {
- continue;
- }
- if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
- if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) {
- continue;
- }
- }
+ if( !hasMatchingType( edgeCallee, hrnCaller ) ) {
+ // prune
+ continue;
}
// otherwise caller node can match callee edge, so make it
ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
if( edgeExisting == null ) {
+
// if this edge doesn't exist in the caller, create it
addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
} else {
}
+ protected boolean hasMatchingField( HeapRegionNode src, ReferenceEdge edge ) {
+
+ // if no allocation site, then it's a match-everything region
+ AllocationSite asSrc = src.getAllocationSite();
+ if( asSrc == null ) { return true; }
+
+ TypeDescriptor tdSrc = asSrc.getType();
+ assert tdSrc != null;
+
+ // if it's not a class, it doesn't have any fields to match
+ if( !tdSrc.isClass() ) { return false; }
+
+ Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
+ while( fieldsSrcItr.hasNext() ) {
+ FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
+ if( fd == edge.getFieldDesc() ) {
+ return true;
+ }
+ }
+
+ // otherwise it is a class with fields
+ // but we didn't find a match
+ return false;
+ }
+
+
+ protected boolean hasMatchingType( ReferenceEdge edge, HeapRegionNode dst ) {
+
+ // if the region has no type, matches everything
+ AllocationSite asDst = dst.getAllocationSite();
+ if( asDst == null ) { return true; }
+
+ TypeDescriptor tdDst = asDst.getType();
+ assert tdDst != null;
+
+ // if the type is not a class don't match because
+ // primitives are copied, no memory aliases
+ ClassDescriptor cdDst = tdDst.getClassDesc();
+ if( cdDst == null ) { return false; }
+
+ // if the field is null, it matches everything
+ FieldDescriptor fd = edge.getFieldDesc();
+ if( fd == null ) { return true; }
+ TypeDescriptor tdFd = fd.getType();
+ assert tdFd != null;
+
+ return typeUtil.isSuperorType( tdFd, tdDst );
+ }
+
+
+
protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
edge.setBeta(edge.getBeta().unshadowTokens(as) );
}
CallGraph callGraph = new CallGraph(state);
int allocationDepth = 3;
OwnershipAnalysis oa =
- new OwnershipAnalysis(state, callGraph, allocationDepth, true, true);
+ new OwnershipAnalysis(state, tu, callGraph, allocationDepth, true, false);
// oa.writeAllAliases( "identifiedAliases.txt" );
}
projects / IRC.git / commitdiff