///////////////////////////////////////////
public HashSet<AllocationSite>
- getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) {
- return getFlaggedAllocationSitesReachableFromTaskPRIVATE( td );
+ getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
+ return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
}
- public AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) {
- return getAllocationSiteFromFlatNewPRIVATE( fn );
+ public AllocationSite getAllocationSiteFromFlatNew(FlatNew fn) {
+ return getAllocationSiteFromFlatNewPRIVATE(fn);
}
- public boolean createsPotentialAliases( Descriptor taskOrMethod,
- int paramIndex1,
- int paramIndex2 ) {
-
- OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
- assert( og != null );
- return og.hasPotentialAlias( paramIndex1, paramIndex2 );
+ public boolean createsPotentialAliases(Descriptor taskOrMethod,
+ int paramIndex1,
+ int paramIndex2) {
+
+ OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get(taskOrMethod);
+ assert(og != null);
+ return og.hasPotentialAlias(paramIndex1, paramIndex2);
}
- public boolean createsPotentialAliases( Descriptor taskOrMethod,
- int paramIndex,
- AllocationSite alloc ) {
-
- OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
- assert( og != null );
- return og.hasPotentialAlias( paramIndex, alloc );
+ public boolean createsPotentialAliases(Descriptor taskOrMethod,
+ int paramIndex,
+ AllocationSite alloc) {
+
+ OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get(taskOrMethod);
+ assert(og != null);
+ return og.hasPotentialAlias(paramIndex, alloc);
}
- public boolean createsPotentialAliases( Descriptor taskOrMethod,
- AllocationSite alloc,
- int paramIndex ) {
-
- OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
- assert( og != null );
- return og.hasPotentialAlias( paramIndex, alloc );
+ public boolean createsPotentialAliases(Descriptor taskOrMethod,
+ AllocationSite alloc,
+ int paramIndex) {
+
+ OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get(taskOrMethod);
+ assert(og != null);
+ return og.hasPotentialAlias(paramIndex, alloc);
}
- public boolean createsPotentialAliases( Descriptor taskOrMethod,
- AllocationSite alloc1,
- AllocationSite alloc2 ) {
-
- OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
- assert( og != null );
- return og.hasPotentialAlias( alloc1, alloc2 );
+ public boolean createsPotentialAliases(Descriptor taskOrMethod,
+ AllocationSite alloc1,
+ AllocationSite alloc2) {
+
+ OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get(taskOrMethod);
+ assert(og != null);
+ return og.hasPotentialAlias(alloc1, alloc2);
}
// use the methods given above to check every possible alias
BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
+ bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth);
+
// look through every task for potential aliases
Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
while( taskItr.hasNext() ) {
TaskDescriptor td = (TaskDescriptor) taskItr.next();
-
- bw.write( "\n---------"+td+"--------\n" );
- HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask( td );
-
+ bw.write("\n---------"+td+"--------\n");
+
+ HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
+
// for each task parameter, check for aliases with
// other task parameters and every allocation site
// reachable from this task
boolean foundSomeAlias = false;
- FlatMethod fm = state.getMethodFlat( td );
+ FlatMethod fm = state.getMethodFlat(td);
for( int i = 0; i < fm.numParameters(); ++i ) {
// for the ith parameter check for aliases to all
// higher numbered parameters
for( int j = i + 1; j < fm.numParameters(); ++j ) {
- if( createsPotentialAliases( td, i, j ) ) {
+ if( createsPotentialAliases(td, i, j) ) {
foundSomeAlias = true;
- bw.write( "Potential alias between parameters "+i+" and "+j+".\n" );
+ bw.write("Potential alias between parameters "+i+" and "+j+".\n");
}
}
Iterator allocItr = allocSites.iterator();
while( allocItr.hasNext() ) {
AllocationSite as = (AllocationSite) allocItr.next();
- if( createsPotentialAliases( td, i, as ) ) {
+ if( createsPotentialAliases(td, i, as) ) {
foundSomeAlias = true;
- bw.write( "Potential alias between parameter "+i+" and "+as+".\n" );
+ bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n");
}
}
}
while( allocItr2.hasNext() ) {
AllocationSite as2 = (AllocationSite) allocItr2.next();
- if( !outerChecked.contains( as2 ) &&
- createsPotentialAliases( td, as1, as2 ) ) {
- bw.write( "Potential alias between "+as1+" and "+as2+".\n" );
+ if( !outerChecked.contains(as2) &&
+ createsPotentialAliases(td, as1, as2) ) {
+ foundSomeAlias = true;
+ bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n");
}
}
- outerChecked.add( as1 );
+ outerChecked.add(as1);
}
if( !foundSomeAlias ) {
- bw.write( "Task "+td+" contains no aliases between flagged objects.\n" );
+ bw.write("Task "+td+" contains no aliases between flagged objects.\n");
}
}
-
+
bw.close();
}
// data from the compiler
private State state;
+ private TypeUtil typeUtil;
private CallGraph callGraph;
private int allocationDepth;
// processing all methods in the program, and by methods
// TaskDescriptor and MethodDescriptor are combined
// together, with a common parent class Descriptor
+ private Hashtable<FlatMethod, OwnershipGraph> mapFlatMethodToInitialParamAllocGraph;
private Hashtable<Descriptor, OwnershipGraph> mapDescriptorToCompleteOwnershipGraph;
private Hashtable<FlatNew, AllocationSite> mapFlatNewToAllocationSite;
private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
+ private Hashtable<Descriptor, Integer> mapDescriptorToNumUpdates;
// Use these data structures to track progress of one pass of
// processing the FlatNodes of a particular method
// a special field descriptor for all array elements
private static FieldDescriptor fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
- new TypeDescriptor( "Array[]" ),
- "elements",
- null,
- false);
+ new TypeDescriptor("Array[]"),
+ "elements",
+ null,
+ false);
+ // for controlling DOT file output
+ private boolean writeDOTs;
+ private boolean writeAllDOTs;
+
// this analysis generates an ownership graph for every task
// in the program
public OwnershipAnalysis(State state,
+ TypeUtil tu,
CallGraph callGraph,
- int allocationDepth) throws java.io.IOException {
+ int allocationDepth,
+ boolean writeDOTs,
+ boolean writeAllDOTs,
+ String aliasFile) throws java.io.IOException {
+
this.state = state;
+ this.typeUtil = tu;
this.callGraph = callGraph;
this.allocationDepth = allocationDepth;
-
+ this.writeDOTs = writeDOTs;
+ this.writeAllDOTs = writeAllDOTs;
descriptorsToAnalyze = new HashSet<Descriptor>();
+ mapFlatMethodToInitialParamAllocGraph =
+ new Hashtable<FlatMethod, OwnershipGraph>();
+
mapDescriptorToCompleteOwnershipGraph =
new Hashtable<Descriptor, OwnershipGraph>();
mapDescriptorToAllocationSiteSet =
new Hashtable<Descriptor, HashSet<AllocationSite> >();
+ if( writeAllDOTs ) {
+ mapDescriptorToNumUpdates = new Hashtable<Descriptor, Integer>();
+ }
// initialize methods to visit as the set of all tasks in the
// program and then any method that could be called starting
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);
- mapDescriptorToCompleteOwnershipGraph.put(d, og);
+ og = analyzeFlatNode(d, fm, null, og);
+ setGraphForDescriptor(d, og);
}
System.out.println("");
// a method if the methods that it calls are updated
analyzeMethods();
- writeAllAliases( "identifiedAliases.txt" );
+ System.out.println("");
+
+ if( aliasFile != null ) {
+ writeAllAliases(aliasFile);
+ }
}
// called from the constructor to help initialize the set
OwnershipGraph og = analyzeFlatMethod(d, fm);
OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get(d);
if( !og.equals(ogPrev) ) {
- mapDescriptorToCompleteOwnershipGraph.put(d, og);
-
- /* boolean writeLabels,
- boolean labelSelect,
- boolean pruneGarbage,
- boolean writeReferencers */
- og.writeGraph(d, true, true, true, false);
+ setGraphForDescriptor(d, og);
// only methods have dependents, tasks cannot
// be invoked by any user program calls
// initialize flat nodes to visit as the flat method
// because all other nodes in this flat method are
// decendents of the flat method itself
+
flatNodesToVisit = new HashSet<FlatNode>();
flatNodesToVisit.add(flatm);
-
- // A YUCKY HACK--this is to make sure that an initially empty
- // graph (no parameters) will get passed the first "any changes?"
- // test when it comes up for analysis. It's ugly but throwing
- // a child in works.
- FlatNode fnJ = flatm.getNext(0);
- assert fnJ != null;
- flatNodesToVisit.add(fnJ);
-
-
// initilize the mapping of flat nodes in this flat method to
// ownership graph results to an empty mapping
mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
flatNodesToVisit.remove(fn);
+ //System.out.println( " "+fn );
+
// 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 ) {
- FlatNode pn = fn.getPrev(i);
- OwnershipGraph ogParent = getGraphFromFlatNode(pn);
- og.merge(ogParent);
+ FlatNode pn = fn.getPrev(i);
+ if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
+ OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
+ og.merge(ogParent);
+ }
}
// 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);
+
+
+
+ //debugSnapshot(og,fn);
+
+
// if the results of the new graph are different from
// the current graph at this node, replace the graph
// with the update and enqueue the children for
// processing
- OwnershipGraph ogPrev = getGraphFromFlatNode(fn);
-
+ OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
if( !og.equals(ogPrev) ) {
- setGraphForFlatNode(fn, og);
+ mapFlatNodeToOwnershipGraph.put(fn, og);
for( int i = 0; i < fn.numNext(); i++ ) {
FlatNode nn = fn.getNext(i);
// 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();
- OwnershipGraph ogr = getGraphFromFlatNode(frn);
+ assert mapFlatNodeToOwnershipGraph.containsKey(frn);
+ OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
completeGraph.merge(ogr);
- }
+ }
+
return completeGraph;
}
- private void
+ private OwnershipGraph
analyzeFlatNode(Descriptor methodDesc,
FlatNode fn,
HashSet<FlatReturnNode> setRetNodes,
// parent of all other FlatNode objects, so take
// the opportunity to construct the initial graph by
// adding parameters labels to new heap regions
- for( int i = 0; i < fm.numParameters(); ++i ) {
- TempDescriptor tdParam = fm.getParameter(i);
+ // AND this should be done once globally so that the
+ // parameter IDs are consistent between analysis
+ // iterations, so if this step has been done already
+ // just merge in the cached version
+ OwnershipGraph ogInitParamAlloc = mapFlatMethodToInitialParamAllocGraph.get(fm);
+ if( ogInitParamAlloc == null ) {
+
+ // analyze this node one time globally
+ for( int i = 0; i < fm.numParameters(); ++i ) {
+ TempDescriptor tdParam = fm.getParameter(i);
+ og.assignTempEqualToParamAlloc(tdParam,
+ methodDesc instanceof TaskDescriptor,
+ new Integer(i) );
+ }
+
+ // then remember it
+ OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil);
+ ogResult.merge(og);
+ mapFlatMethodToInitialParamAllocGraph.put(fm, ogResult);
- og.assignTempEqualToParamAlloc(tdParam,
- methodDesc instanceof TaskDescriptor,
- new Integer(i) );
+ } else {
+ // or just leverage the cached copy
+ og.merge(ogInitParamAlloc);
}
break;
lhs = ffn.getDst();
rhs = ffn.getSrc();
fld = ffn.getField();
- if( !fld.getType().isPrimitive() ) {
+ if( !fld.getType().isImmutable() ) {
og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
}
break;
lhs = fsfn.getDst();
fld = fsfn.getField();
rhs = fsfn.getSrc();
- og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
+ if( !fld.getType().isImmutable() ) {
+ og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
+ }
break;
-
+
case FKind.FlatElementNode:
FlatElementNode fen = (FlatElementNode) fn;
lhs = fen.getDst();
rhs = fen.getSrc();
- if( !lhs.getType().isPrimitive() ) {
+ if( !lhs.getType().isImmutable() ) {
og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
}
break;
FlatSetElementNode fsen = (FlatSetElementNode) fn;
lhs = fsen.getDst();
rhs = fsen.getSrc();
- if( !rhs.getType().isPrimitive() ) {
+ if( !rhs.getType().isImmutable() ) {
og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
}
break;
case FKind.FlatNew:
FlatNew fnn = (FlatNew) fn;
lhs = fnn.getDst();
- AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
-
- og.assignTempEqualToNewAlloc(lhs, as);
+ if( !lhs.getType().isImmutable() ) {
+ AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
+ og.assignTempEqualToNewAlloc(lhs, as);
+ }
break;
case FKind.FlatCall:
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
// find all of them and merge all of their results together
TypeDescriptor typeDesc = fc.getThis().getType();
Set possibleCallees = callGraph.getMethods(md, typeDesc);
-
+
Iterator i = possibleCallees.iterator();
while( i.hasNext() ) {
MethodDescriptor possibleMd = (MethodDescriptor) i.next();
-
+
// 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);
- ogCopy.merge( og );
-
+ OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil);
+ ogCopy.merge(og);
+
OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd);
- ogCopy.resolveMethodCall(fc, md.isStatic(), flatm, ogPotentialCallee );
- ogMergeOfAllPossibleCalleeResults.merge( ogCopy );
+ ogCopy.resolveMethodCall(fc, md.isStatic(), flatm, ogPotentialCallee);
+ ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
}
}
- og = ogMergeOfAllPossibleCalleeResults;
+ og = ogMergeOfAllPossibleCalleeResults;
break;
case FKind.FlatReturnNode:
FlatReturnNode frn = (FlatReturnNode) fn;
rhs = frn.getReturnTemp();
-
- if( rhs != null ) {
+ if( rhs != null && !rhs.getType().isImmutable() ) {
og.assignReturnEqualToTemp(rhs);
}
-
setRetNodes.add(frn);
break;
}
+
+ return og;
}
+ // insert a call to debugSnapshot() somewhere in the analysis to get
+ // successive captures of the analysis state
+ int debugCounter = 0;
+ int numStartCountReport = 10000;
+ int freqCountReport = 10;
+ int iterStartCapture = 50;
+ int numIterToCapture = 16;
+ void debugSnapshot( OwnershipGraph og, FlatNode fn ) {
+ ++debugCounter;
+ if( debugCounter > numStartCountReport &&
+ debugCounter % freqCountReport == 0 ) {
+ System.out.println( " @@@ debug counter = "+debugCounter );
+ }
+ if( debugCounter > iterStartCapture ) {
+ System.out.println( " @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@" );
+ String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
+ if( fn != null ) {
+ graphName = graphName+fn;
+ }
+ try {
+ og.writeGraph( graphName, true, true, true, false, false );
+ } catch( Exception e ) {
+ System.out.println( "Error writing debug capture." );
+ System.exit( 0 );
+ }
+ }
+ if( debugCounter == iterStartCapture + numIterToCapture ) {
+ System.out.println( "Stopping analysis after debug captures." );
+ System.exit( 0 );
+ }
+ }
+
+
+
// this method should generate integers strictly greater than zero!
// special "shadow" regions are made from a heap region by negating
// the ID
}
- private OwnershipGraph getGraphFromFlatNode(FlatNode fn) {
- if( !mapFlatNodeToOwnershipGraph.containsKey(fn) ) {
- mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth) );
- }
+ private void setGraphForDescriptor(Descriptor d, OwnershipGraph og)
+ throws IOException {
- return mapFlatNodeToOwnershipGraph.get(fn);
- }
+ mapDescriptorToCompleteOwnershipGraph.put(d, og);
- private void setGraphForFlatNode(FlatNode fn, OwnershipGraph og) {
- mapFlatNodeToOwnershipGraph.put(fn, og);
- }
+ // arguments to writeGraph are:
+ // boolean writeLabels,
+ // boolean labelSelect,
+ // boolean pruneGarbage,
+ // boolean writeReferencers
+ // boolean writeParamMappings
+ if( writeDOTs ) {
+
+ if( !writeAllDOTs ) {
+ og.writeGraph(d, true, true, true, false, false);
+
+ } else {
+ if( !mapDescriptorToNumUpdates.containsKey(d) ) {
+ mapDescriptorToNumUpdates.put(d, new Integer(0) );
+ }
+ Integer n = mapDescriptorToNumUpdates.get(d);
+ og.writeGraph(d, n, true, true, true, false, false);
+ mapDescriptorToNumUpdates.put(d, n + 1);
+ }
+ }
+ }
// return just the allocation site associated with one FlatNew node
private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
- AllocationSite as = new AllocationSite(allocationDepth, fn.getType() );
+ AllocationSite as = new AllocationSite(allocationDepth, fn );
// the newest nodes are single objects
for( int i = 0; i < allocationDepth; ++i ) {
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);
+ }
}
}
projects / IRC.git / blobdiff