1 package Analysis.OwnershipAnalysis;
3 import Analysis.CallGraph.*;
6 import IR.Tree.Modifiers;
11 public class OwnershipAnalysis {
14 ///////////////////////////////////////////
16 // Public interface to discover possible
17 // aliases in the program under analysis
19 ///////////////////////////////////////////
21 public HashSet<AllocationSite>
22 getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) {
23 return getFlaggedAllocationSitesReachableFromTaskPRIVATE( td );
26 public AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) {
27 return getAllocationSiteFromFlatNewPRIVATE( fn );
30 public boolean createsPotentialAliases( Descriptor taskOrMethod,
34 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
36 return og.hasPotentialAlias( paramIndex1, paramIndex2 );
39 public boolean createsPotentialAliases( Descriptor taskOrMethod,
41 AllocationSite alloc ) {
43 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
45 return og.hasPotentialAlias( paramIndex, alloc );
48 public boolean createsPotentialAliases( Descriptor taskOrMethod,
52 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
54 return og.hasPotentialAlias( paramIndex, alloc );
57 public boolean createsPotentialAliases( Descriptor taskOrMethod,
58 AllocationSite alloc1,
59 AllocationSite alloc2 ) {
61 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
63 return og.hasPotentialAlias( alloc1, alloc2 );
66 // use the methods given above to check every possible alias
67 // between task parameters and flagged allocation sites reachable
69 public void writeAllAliases(String outputFile) throws java.io.IOException {
71 BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
73 // look through every task for potential aliases
74 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
75 while( taskItr.hasNext() ) {
76 TaskDescriptor td = (TaskDescriptor) taskItr.next();
78 bw.write( "\n---------"+td+"--------\n" );
80 HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask( td );
82 // for each task parameter, check for aliases with
83 // other task parameters and every allocation site
84 // reachable from this task
85 boolean foundSomeAlias = false;
87 FlatMethod fm = state.getMethodFlat( td );
88 for( int i = 0; i < fm.numParameters(); ++i ) {
90 // for the ith parameter check for aliases to all
91 // higher numbered parameters
92 for( int j = i + 1; j < fm.numParameters(); ++j ) {
93 if( createsPotentialAliases( td, i, j ) ) {
94 foundSomeAlias = true;
95 bw.write( "Potential alias between parameters "+i+" and "+j+".\n" );
99 // for the ith parameter, check for aliases against
100 // the set of allocation sites reachable from this
102 Iterator allocItr = allocSites.iterator();
103 while( allocItr.hasNext() ) {
104 AllocationSite as = (AllocationSite) allocItr.next();
105 if( createsPotentialAliases( td, i, as ) ) {
106 foundSomeAlias = true;
107 bw.write( "Potential alias between parameter "+i+" and "+as+".\n" );
112 // for each allocation site check for aliases with
113 // other allocation sites in the context of execution
115 HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
116 Iterator allocItr1 = allocSites.iterator();
117 while( allocItr1.hasNext() ) {
118 AllocationSite as1 = (AllocationSite) allocItr1.next();
120 Iterator allocItr2 = allocSites.iterator();
121 while( allocItr2.hasNext() ) {
122 AllocationSite as2 = (AllocationSite) allocItr2.next();
124 if( !outerChecked.contains( as2 ) &&
125 createsPotentialAliases( td, as1, as2 ) ) {
126 bw.write( "Potential alias between "+as1+" and "+as2+".\n" );
130 outerChecked.add( as1 );
133 if( !foundSomeAlias ) {
134 bw.write( "Task "+td+" contains no aliases between flagged objects.\n" );
141 ///////////////////////////////////////////
143 // end public interface
145 ///////////////////////////////////////////
154 // data from the compiler
156 private CallGraph callGraph;
157 private int allocationDepth;
159 // used to identify HeapRegionNode objects
160 // A unique ID equates an object in one
161 // ownership graph with an object in another
162 // graph that logically represents the same
164 // start at 10 and incerement to leave some
165 // reserved IDs for special purposes
166 static private int uniqueIDcount = 10;
169 // Use these data structures to track progress of
170 // processing all methods in the program, and by methods
171 // TaskDescriptor and MethodDescriptor are combined
172 // together, with a common parent class Descriptor
173 private Hashtable<Descriptor, OwnershipGraph> mapDescriptorToCompleteOwnershipGraph;
174 private Hashtable<FlatNew, AllocationSite> mapFlatNewToAllocationSite;
175 private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
177 // Use these data structures to track progress of one pass of
178 // processing the FlatNodes of a particular method
179 private HashSet <FlatNode> flatNodesToVisit;
180 private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
181 private HashSet <FlatReturnNode> returnNodesToCombineForCompleteOwnershipGraph;
183 // descriptorsToAnalyze identifies the set of tasks and methods
184 // that are reachable from the program tasks, this set is initialized
185 // and then remains static
186 private HashSet<Descriptor> descriptorsToAnalyze;
188 // descriptorsToVisit is initialized to descriptorsToAnalyze and is
189 // reduced by visiting a descriptor during analysis. When dependents
190 // must be scheduled, only those contained in descriptorsToAnalyze
191 // should be re-added to this set
192 private HashSet<Descriptor> descriptorsToVisit;
194 // a special field descriptor for all array elements
195 private static FieldDescriptor fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
196 new TypeDescriptor( "Array[]" ),
202 // this analysis generates an ownership graph for every task
204 public OwnershipAnalysis(State state,
206 int allocationDepth) throws java.io.IOException {
208 this.callGraph = callGraph;
209 this.allocationDepth = allocationDepth;
212 descriptorsToAnalyze = new HashSet<Descriptor>();
214 mapDescriptorToCompleteOwnershipGraph =
215 new Hashtable<Descriptor, OwnershipGraph>();
217 mapFlatNewToAllocationSite =
218 new Hashtable<FlatNew, AllocationSite>();
220 mapDescriptorToAllocationSiteSet =
221 new Hashtable<Descriptor, HashSet<AllocationSite> >();
224 // initialize methods to visit as the set of all tasks in the
225 // program and then any method that could be called starting
227 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
228 while( taskItr.hasNext() ) {
229 Descriptor d = (Descriptor) taskItr.next();
230 scheduleAllCallees(d);
233 // before beginning analysis, initialize every scheduled method
234 // with an ownership graph that has populated parameter index tables
235 // by analyzing the first node which is always a FlatMethod node
236 Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
237 while( dItr.hasNext() ) {
238 Descriptor d = dItr.next();
239 OwnershipGraph og = new OwnershipGraph(allocationDepth);
242 if( d instanceof MethodDescriptor ) {
243 fm = state.getMethodFlat( (MethodDescriptor) d);
245 assert d instanceof TaskDescriptor;
246 fm = state.getMethodFlat( (TaskDescriptor) d);
249 System.out.println("Previsiting " + d);
251 analyzeFlatNode(d, fm, null, og);
252 mapDescriptorToCompleteOwnershipGraph.put(d, og);
255 System.out.println("");
257 // as mentioned above, analyze methods one-by-one, possibly revisiting
258 // a method if the methods that it calls are updated
261 writeAllAliases( "identifiedAliases.txt" );
264 // called from the constructor to help initialize the set
265 // of methods that needs to be analyzed by ownership analysis
266 private void scheduleAllCallees(Descriptor d) {
267 if( descriptorsToAnalyze.contains(d) ) {
270 descriptorsToAnalyze.add(d);
272 // start with all method calls to further schedule
273 Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
275 if( d instanceof MethodDescriptor ) {
276 // see if this method has virtual dispatch
277 Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
278 moreMethodsToCheck.addAll(virtualMethods);
281 // keep following any further methods identified in
283 Iterator methItr = moreMethodsToCheck.iterator();
284 while( methItr.hasNext() ) {
285 Descriptor m = (Descriptor) methItr.next();
286 scheduleAllCallees(m);
291 // manage the set of tasks and methods to be analyzed
292 // and be sure to reschedule tasks/methods when the methods
293 // they call are updated
294 private void analyzeMethods() throws java.io.IOException {
296 descriptorsToVisit = (HashSet<Descriptor>)descriptorsToAnalyze.clone();
298 while( !descriptorsToVisit.isEmpty() ) {
299 Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
300 descriptorsToVisit.remove(d);
302 // because the task or method descriptor just extracted
303 // was in the "to visit" set it either hasn't been analyzed
304 // yet, or some method that it depends on has been
305 // updated. Recompute a complete ownership graph for
306 // this task/method and compare it to any previous result.
307 // If there is a change detected, add any methods/tasks
308 // that depend on this one to the "to visit" set.
310 System.out.println("Analyzing " + d);
313 if( d instanceof MethodDescriptor ) {
314 fm = state.getMethodFlat( (MethodDescriptor) d);
316 assert d instanceof TaskDescriptor;
317 fm = state.getMethodFlat( (TaskDescriptor) d);
320 OwnershipGraph og = analyzeFlatMethod(d, fm);
321 OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get(d);
322 if( !og.equals(ogPrev) ) {
323 mapDescriptorToCompleteOwnershipGraph.put(d, og);
325 /* boolean writeLabels,
327 boolean pruneGarbage,
328 boolean writeReferencers */
329 og.writeGraph(d, true, true, true, false);
331 // only methods have dependents, tasks cannot
332 // be invoked by any user program calls
333 if( d instanceof MethodDescriptor ) {
334 MethodDescriptor md = (MethodDescriptor) d;
335 Set dependents = callGraph.getCallerSet(md);
336 if( dependents != null ) {
337 Iterator depItr = dependents.iterator();
338 while( depItr.hasNext() ) {
339 Descriptor dependent = (Descriptor) depItr.next();
340 if( descriptorsToAnalyze.contains(dependent) ) {
341 descriptorsToVisit.add(dependent);
352 // keep passing the Descriptor of the method along for debugging
353 // and dot file writing
354 private OwnershipGraph
355 analyzeFlatMethod(Descriptor mDesc,
356 FlatMethod flatm) throws java.io.IOException {
358 // initialize flat nodes to visit as the flat method
359 // because all other nodes in this flat method are
360 // decendents of the flat method itself
361 flatNodesToVisit = new HashSet<FlatNode>();
362 flatNodesToVisit.add(flatm);
365 // A YUCKY HACK--this is to make sure that an initially empty
366 // graph (no parameters) will get passed the first "any changes?"
367 // test when it comes up for analysis. It's ugly but throwing
369 FlatNode fnJ = flatm.getNext(0);
371 flatNodesToVisit.add(fnJ);
374 // initilize the mapping of flat nodes in this flat method to
375 // ownership graph results to an empty mapping
376 mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
378 // initialize the set of return nodes that will be combined as
379 // the final ownership graph result to return as an empty set
380 returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
383 while( !flatNodesToVisit.isEmpty() ) {
384 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
385 flatNodesToVisit.remove(fn);
387 // perform this node's contributions to the ownership
388 // graph on a new copy, then compare it to the old graph
389 // at this node to see if anything was updated.
390 OwnershipGraph og = new OwnershipGraph(allocationDepth);
392 // start by merging all node's parents' graphs
393 for( int i = 0; i < fn.numPrev(); ++i ) {
394 FlatNode pn = fn.getPrev(i);
395 OwnershipGraph ogParent = getGraphFromFlatNode(pn);
399 // apply the analysis of the flat node to the
400 // ownership graph made from the merge of the
402 analyzeFlatNode(mDesc,
404 returnNodesToCombineForCompleteOwnershipGraph,
407 // if the results of the new graph are different from
408 // the current graph at this node, replace the graph
409 // with the update and enqueue the children for
411 OwnershipGraph ogPrev = getGraphFromFlatNode(fn);
413 if( !og.equals(ogPrev) ) {
414 setGraphForFlatNode(fn, og);
416 for( int i = 0; i < fn.numNext(); i++ ) {
417 FlatNode nn = fn.getNext(i);
418 flatNodesToVisit.add(nn);
423 // end by merging all return nodes into a complete
424 // ownership graph that represents all possible heap
425 // states after the flat method returns
426 OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth);
427 Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
428 while( retItr.hasNext() ) {
429 FlatReturnNode frn = (FlatReturnNode) retItr.next();
430 OwnershipGraph ogr = getGraphFromFlatNode(frn);
431 completeGraph.merge(ogr);
433 return completeGraph;
438 analyzeFlatNode(Descriptor methodDesc,
440 HashSet<FlatReturnNode> setRetNodes,
441 OwnershipGraph og) throws java.io.IOException {
447 // use node type to decide what alterations to make
448 // to the ownership graph
449 switch( fn.kind() ) {
451 case FKind.FlatMethod:
452 FlatMethod fm = (FlatMethod) fn;
454 // there should only be one FlatMethod node as the
455 // parent of all other FlatNode objects, so take
456 // the opportunity to construct the initial graph by
457 // adding parameters labels to new heap regions
458 for( int i = 0; i < fm.numParameters(); ++i ) {
459 TempDescriptor tdParam = fm.getParameter(i);
461 og.assignTempEqualToParamAlloc(tdParam,
462 methodDesc instanceof TaskDescriptor,
467 case FKind.FlatOpNode:
468 FlatOpNode fon = (FlatOpNode) fn;
469 if( fon.getOp().getOp() == Operation.ASSIGN ) {
472 og.assignTempXEqualToTempY(lhs, rhs);
476 case FKind.FlatFieldNode:
477 FlatFieldNode ffn = (FlatFieldNode) fn;
480 fld = ffn.getField();
481 if( !fld.getType().isPrimitive() ) {
482 og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
486 case FKind.FlatSetFieldNode:
487 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
489 fld = fsfn.getField();
491 og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
494 case FKind.FlatElementNode:
495 FlatElementNode fen = (FlatElementNode) fn;
498 if( !lhs.getType().isPrimitive() ) {
499 og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
503 case FKind.FlatSetElementNode:
504 FlatSetElementNode fsen = (FlatSetElementNode) fn;
507 if( !rhs.getType().isPrimitive() ) {
508 og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
513 FlatNew fnn = (FlatNew) fn;
515 AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
517 og.assignTempEqualToNewAlloc(lhs, as);
521 FlatCall fc = (FlatCall) fn;
522 MethodDescriptor md = fc.getMethod();
523 FlatMethod flatm = state.getMethodFlat(md);
524 OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth);
526 if( md.isStatic() ) {
527 // a static method is simply always the same, makes life easy
528 OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get(md);
529 ogMergeOfAllPossibleCalleeResults = og;
530 ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee);
532 // if the method descriptor is virtual, then there could be a
533 // set of possible methods that will actually be invoked, so
534 // find all of them and merge all of their results together
535 TypeDescriptor typeDesc = fc.getThis().getType();
536 Set possibleCallees = callGraph.getMethods(md, typeDesc);
538 Iterator i = possibleCallees.iterator();
539 while( i.hasNext() ) {
540 MethodDescriptor possibleMd = (MethodDescriptor) i.next();
542 // don't alter the working graph (og) until we compute a result for every
543 // possible callee, merge them all together, then set og to that
544 OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth);
547 OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd);
548 ogCopy.resolveMethodCall(fc, md.isStatic(), flatm, ogPotentialCallee );
549 ogMergeOfAllPossibleCalleeResults.merge( ogCopy );
553 og = ogMergeOfAllPossibleCalleeResults;
556 case FKind.FlatReturnNode:
557 FlatReturnNode frn = (FlatReturnNode) fn;
558 rhs = frn.getReturnTemp();
561 og.assignReturnEqualToTemp(rhs);
564 setRetNodes.add(frn);
570 // this method should generate integers strictly greater than zero!
571 // special "shadow" regions are made from a heap region by negating
573 static public Integer generateUniqueHeapRegionNodeID() {
575 return new Integer(uniqueIDcount);
579 private OwnershipGraph getGraphFromFlatNode(FlatNode fn) {
580 if( !mapFlatNodeToOwnershipGraph.containsKey(fn) ) {
581 mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth) );
584 return mapFlatNodeToOwnershipGraph.get(fn);
587 private void setGraphForFlatNode(FlatNode fn, OwnershipGraph og) {
588 mapFlatNodeToOwnershipGraph.put(fn, og);
593 // return just the allocation site associated with one FlatNew node
594 private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
596 if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
597 AllocationSite as = new AllocationSite(allocationDepth, fn.getType() );
599 // the newest nodes are single objects
600 for( int i = 0; i < allocationDepth; ++i ) {
601 Integer id = generateUniqueHeapRegionNodeID();
602 as.setIthOldest(i, id);
605 // the oldest node is a summary node
606 Integer idSummary = generateUniqueHeapRegionNodeID();
607 as.setSummary(idSummary);
609 mapFlatNewToAllocationSite.put(fn, as);
612 return mapFlatNewToAllocationSite.get(fn);
616 // return all allocation sites in the method (there is one allocation
617 // site per FlatNew node in a method)
618 private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
619 if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
620 buildAllocationSiteSet(d);
623 return mapDescriptorToAllocationSiteSet.get(d);
627 private void buildAllocationSiteSet(Descriptor d) {
628 HashSet<AllocationSite> s = new HashSet<AllocationSite>();
631 if( d instanceof MethodDescriptor ) {
632 fm = state.getMethodFlat( (MethodDescriptor) d);
634 assert d instanceof TaskDescriptor;
635 fm = state.getMethodFlat( (TaskDescriptor) d);
638 // visit every node in this FlatMethod's IR graph
639 // and make a set of the allocation sites from the
640 // FlatNew node's visited
641 HashSet<FlatNode> visited = new HashSet<FlatNode>();
642 HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
645 while( !toVisit.isEmpty() ) {
646 FlatNode n = toVisit.iterator().next();
648 if( n instanceof FlatNew ) {
649 s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
655 for( int i = 0; i < n.numNext(); ++i ) {
656 FlatNode child = n.getNext(i);
657 if( !visited.contains(child) ) {
663 mapDescriptorToAllocationSiteSet.put(d, s);
667 private HashSet<AllocationSite>
668 getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
670 HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
671 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
672 HashSet<Descriptor> visited = new HashSet<Descriptor>();
676 // traverse this task and all methods reachable from this task
677 while( !toVisit.isEmpty() ) {
678 Descriptor d = toVisit.iterator().next();
682 HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
683 Iterator asItr = asSet.iterator();
684 while( asItr.hasNext() ) {
685 AllocationSite as = (AllocationSite) asItr.next();
686 if( as.getType().getClassDesc().hasFlags() ) {
691 // enqueue callees of this method to be searched for
692 // allocation sites also
693 Set callees = callGraph.getCalleeSet(d);
694 if( callees != null ) {
695 Iterator methItr = callees.iterator();
696 while( methItr.hasNext() ) {
697 MethodDescriptor md = (MethodDescriptor) methItr.next();
699 if( !visited.contains(md) ) {