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 );
58 public boolean createsPotentialAliases( Descriptor taskOrMethod,
59 AllocationSite alloc1,
60 AllocationSite alloc2 ) {
62 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
64 return createsPotentialAliases( og,
65 getHeapRegionIDset( alloc1 ),
66 getHeapRegionIDset( alloc2 ) );
69 public boolean createsPotentialAliases( Descriptor taskOrMethod,
71 HashSet<AllocationSite> allocSet ) {
72 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
74 return createsPotentialAliases( og,
75 getHeapRegionIDset( alloc ),
76 getHeapRegionIDset( allocSet ) );
80 // use the methods given above to check every possible alias
81 // between task parameters and flagged allocation sites reachable
83 public void writeAllAliases(String outputFile) throws java.io.IOException {
85 BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
87 // look through every task for potential aliases
88 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
89 while( taskItr.hasNext() ) {
90 TaskDescriptor td = (TaskDescriptor) taskItr.next();
92 HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask( td );
94 // for each task parameter, check for aliases with
95 // other task parameters and every allocation site
96 // reachable from this task
97 boolean foundSomeAlias = false;
99 FlatMethod fm = state.getMethodFlat( td );
100 for( int i = 0; i < fm.numParameters(); ++i ) {
102 // for the ith parameter check for aliases to all
103 // higher numbered parameters
104 for( int j = i + 1; j < fm.numParameters(); ++j ) {
105 if( createsPotentialAliases( td, i, j ) ) {
106 foundSomeAlias = true;
107 bw.write( "Task "+td+" potentially aliases parameters "+i+" and "+j+".\n" );
111 // for the ith parameter, check for aliases against
112 // the set of allocation sites reachable from this
114 Iterator allocItr = allocSites.iterator();
115 while( allocItr.hasNext() ) {
116 AllocationSite as = (AllocationSite) allocItr.next();
117 if( createsPotentialAliases( td, i, as ) ) {
118 foundSomeAlias = true;
119 bw.write( "Task "+td+" potentially aliases parameter "+i+" and "+as+".\n" );
125 // for each allocation site check for aliases with
126 // other allocation sites in the context of execution
128 Iterator allocItr = allocSites.iterator();
129 while( allocItr.hasNext() ) {
130 AllocationSite as = (AllocationSite) allocItr.next();
131 if( createsPotentialAliases( td, as, allocSites ) ) {
132 bw.write( "Task "+td+" potentially aliases "+as+" and the rest of the set.\n" );
137 if( !foundSomeAlias ) {
138 bw.write( "Task "+td+" contains no aliases between flagged objects.\n" );
145 ///////////////////////////////////////////
147 // end public interface
149 ///////////////////////////////////////////
158 // data from the compiler
160 private CallGraph callGraph;
161 private int allocationDepth;
163 // used to identify HeapRegionNode objects
164 // A unique ID equates an object in one
165 // ownership graph with an object in another
166 // graph that logically represents the same
168 // start at 10 and incerement to leave some
169 // reserved IDs for special purposes
170 static private int uniqueIDcount = 10;
173 // Use these data structures to track progress of
174 // processing all methods in the program, and by methods
175 // TaskDescriptor and MethodDescriptor are combined
176 // together, with a common parent class Descriptor
177 private Hashtable<Descriptor, OwnershipGraph> mapDescriptorToCompleteOwnershipGraph;
178 private Hashtable<FlatNew, AllocationSite> mapFlatNewToAllocationSite;
179 private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
181 // Use these data structures to track progress of one pass of
182 // processing the FlatNodes of a particular method
183 private HashSet <FlatNode> flatNodesToVisit;
184 private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
185 private HashSet <FlatReturnNode> returnNodesToCombineForCompleteOwnershipGraph;
187 // descriptorsToAnalyze identifies the set of tasks and methods
188 // that are reachable from the program tasks, this set is initialized
189 // and then remains static
190 private HashSet<Descriptor> descriptorsToAnalyze;
192 // descriptorsToVisit is initialized to descriptorsToAnalyze and is
193 // reduced by visiting a descriptor during analysis. When dependents
194 // must be scheduled, only those contained in descriptorsToAnalyze
195 // should be re-added to this set
196 private HashSet<Descriptor> descriptorsToVisit;
198 // a special field descriptor for all array elements
199 private static FieldDescriptor fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
200 new TypeDescriptor( "Array[]" ),
206 // this analysis generates an ownership graph for every task
208 public OwnershipAnalysis(State state,
210 int allocationDepth) throws java.io.IOException {
212 this.callGraph = callGraph;
213 this.allocationDepth = allocationDepth;
216 descriptorsToAnalyze = new HashSet<Descriptor>();
218 mapDescriptorToCompleteOwnershipGraph =
219 new Hashtable<Descriptor, OwnershipGraph>();
221 mapFlatNewToAllocationSite =
222 new Hashtable<FlatNew, AllocationSite>();
224 mapDescriptorToAllocationSiteSet =
225 new Hashtable<Descriptor, HashSet<AllocationSite> >();
228 // initialize methods to visit as the set of all tasks in the
229 // program and then any method that could be called starting
231 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
232 while( taskItr.hasNext() ) {
233 Descriptor d = (Descriptor) taskItr.next();
234 scheduleAllCallees(d);
237 // before beginning analysis, initialize every scheduled method
238 // with an ownership graph that has populated parameter index tables
239 // by analyzing the first node which is always a FlatMethod node
240 Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
241 while( dItr.hasNext() ) {
242 Descriptor d = dItr.next();
243 OwnershipGraph og = new OwnershipGraph(allocationDepth);
246 if( d instanceof MethodDescriptor ) {
247 fm = state.getMethodFlat( (MethodDescriptor) d);
249 assert d instanceof TaskDescriptor;
250 fm = state.getMethodFlat( (TaskDescriptor) d);
253 System.out.println("Previsiting " + d);
255 analyzeFlatNode(d, fm, null, og);
256 mapDescriptorToCompleteOwnershipGraph.put(d, og);
259 System.out.println("");
261 // as mentioned above, analyze methods one-by-one, possibly revisiting
262 // a method if the methods that it calls are updated
265 writeAllAliases( "identifiedAliases.txt" );
268 // called from the constructor to help initialize the set
269 // of methods that needs to be analyzed by ownership analysis
270 private void scheduleAllCallees(Descriptor d) {
271 if( descriptorsToAnalyze.contains(d) ) {
274 descriptorsToAnalyze.add(d);
276 // start with all method calls to further schedule
277 Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
279 if( d instanceof MethodDescriptor ) {
280 // see if this method has virtual dispatch
281 Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
282 moreMethodsToCheck.addAll(virtualMethods);
285 // keep following any further methods identified in
287 Iterator methItr = moreMethodsToCheck.iterator();
288 while( methItr.hasNext() ) {
289 Descriptor m = (Descriptor) methItr.next();
290 scheduleAllCallees(m);
295 // manage the set of tasks and methods to be analyzed
296 // and be sure to reschedule tasks/methods when the methods
297 // they call are updated
298 private void analyzeMethods() throws java.io.IOException {
300 descriptorsToVisit = (HashSet<Descriptor>)descriptorsToAnalyze.clone();
302 while( !descriptorsToVisit.isEmpty() ) {
303 Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
304 descriptorsToVisit.remove(d);
306 // because the task or method descriptor just extracted
307 // was in the "to visit" set it either hasn't been analyzed
308 // yet, or some method that it depends on has been
309 // updated. Recompute a complete ownership graph for
310 // this task/method and compare it to any previous result.
311 // If there is a change detected, add any methods/tasks
312 // that depend on this one to the "to visit" set.
314 System.out.println("Analyzing " + d);
317 if( d instanceof MethodDescriptor ) {
318 fm = state.getMethodFlat( (MethodDescriptor) d);
320 assert d instanceof TaskDescriptor;
321 fm = state.getMethodFlat( (TaskDescriptor) d);
324 OwnershipGraph og = analyzeFlatMethod(d, fm);
325 OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get(d);
326 if( !og.equals(ogPrev) ) {
327 mapDescriptorToCompleteOwnershipGraph.put(d, og);
329 /* boolean writeLabels,
331 boolean pruneGarbage,
332 boolean writeReferencers */
333 og.writeGraph(d, true, true, true, false);
335 // only methods have dependents, tasks cannot
336 // be invoked by any user program calls
337 if( d instanceof MethodDescriptor ) {
338 MethodDescriptor md = (MethodDescriptor) d;
339 Set dependents = callGraph.getCallerSet(md);
340 if( dependents != null ) {
341 Iterator depItr = dependents.iterator();
342 while( depItr.hasNext() ) {
343 Descriptor dependent = (Descriptor) depItr.next();
344 if( descriptorsToAnalyze.contains(dependent) ) {
345 descriptorsToVisit.add(dependent);
356 // keep passing the Descriptor of the method along for debugging
357 // and dot file writing
358 private OwnershipGraph
359 analyzeFlatMethod(Descriptor mDesc,
360 FlatMethod flatm) throws java.io.IOException {
362 // initialize flat nodes to visit as the flat method
363 // because all other nodes in this flat method are
364 // decendents of the flat method itself
365 flatNodesToVisit = new HashSet<FlatNode>();
366 flatNodesToVisit.add(flatm);
369 // A YUCKY HACK--this is to make sure that an initially empty
370 // graph (no parameters) will get passed the first "any changes?"
371 // test when it comes up for analysis. It's ugly but throwing
373 FlatNode fnJ = flatm.getNext(0);
375 flatNodesToVisit.add(fnJ);
378 // initilize the mapping of flat nodes in this flat method to
379 // ownership graph results to an empty mapping
380 mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
382 // initialize the set of return nodes that will be combined as
383 // the final ownership graph result to return as an empty set
384 returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
387 while( !flatNodesToVisit.isEmpty() ) {
388 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
389 flatNodesToVisit.remove(fn);
391 // perform this node's contributions to the ownership
392 // graph on a new copy, then compare it to the old graph
393 // at this node to see if anything was updated.
394 OwnershipGraph og = new OwnershipGraph(allocationDepth);
396 // start by merging all node's parents' graphs
397 for( int i = 0; i < fn.numPrev(); ++i ) {
398 FlatNode pn = fn.getPrev(i);
399 OwnershipGraph ogParent = getGraphFromFlatNode(pn);
403 // apply the analysis of the flat node to the
404 // ownership graph made from the merge of the
406 analyzeFlatNode(mDesc,
408 returnNodesToCombineForCompleteOwnershipGraph,
411 // if the results of the new graph are different from
412 // the current graph at this node, replace the graph
413 // with the update and enqueue the children for
415 OwnershipGraph ogPrev = getGraphFromFlatNode(fn);
417 if( !og.equals(ogPrev) ) {
418 setGraphForFlatNode(fn, og);
420 for( int i = 0; i < fn.numNext(); i++ ) {
421 FlatNode nn = fn.getNext(i);
422 flatNodesToVisit.add(nn);
427 // end by merging all return nodes into a complete
428 // ownership graph that represents all possible heap
429 // states after the flat method returns
430 OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth);
431 Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
432 while( retItr.hasNext() ) {
433 FlatReturnNode frn = (FlatReturnNode) retItr.next();
434 OwnershipGraph ogr = getGraphFromFlatNode(frn);
435 completeGraph.merge(ogr);
437 return completeGraph;
442 analyzeFlatNode(Descriptor methodDesc,
444 HashSet<FlatReturnNode> setRetNodes,
445 OwnershipGraph og) throws java.io.IOException {
451 // use node type to decide what alterations to make
452 // to the ownership graph
453 switch( fn.kind() ) {
455 case FKind.FlatMethod:
456 FlatMethod fm = (FlatMethod) fn;
458 // there should only be one FlatMethod node as the
459 // parent of all other FlatNode objects, so take
460 // the opportunity to construct the initial graph by
461 // adding parameters labels to new heap regions
462 for( int i = 0; i < fm.numParameters(); ++i ) {
463 TempDescriptor tdParam = fm.getParameter(i);
464 og.assignTempEqualToParamAlloc(tdParam,
465 methodDesc instanceof TaskDescriptor,
471 case FKind.FlatOpNode:
472 FlatOpNode fon = (FlatOpNode) fn;
473 if( fon.getOp().getOp() == Operation.ASSIGN ) {
476 og.assignTempXEqualToTempY(lhs, rhs);
480 case FKind.FlatFieldNode:
481 FlatFieldNode ffn = (FlatFieldNode) fn;
484 fld = ffn.getField();
485 if( !fld.getType().isPrimitive() ) {
486 og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
490 case FKind.FlatSetFieldNode:
491 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
493 fld = fsfn.getField();
495 og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
498 case FKind.FlatElementNode:
499 FlatElementNode fen = (FlatElementNode) fn;
502 if( !lhs.getType().isPrimitive() ) {
503 og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
507 case FKind.FlatSetElementNode:
508 FlatSetElementNode fsen = (FlatSetElementNode) fn;
511 if( !rhs.getType().isPrimitive() ) {
512 og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
517 FlatNew fnn = (FlatNew) fn;
519 AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
521 og.assignTempEqualToNewAlloc(lhs, as);
525 FlatCall fc = (FlatCall) fn;
526 MethodDescriptor md = fc.getMethod();
527 FlatMethod flatm = state.getMethodFlat(md);
528 OwnershipGraph ogAllPossibleCallees = new OwnershipGraph(allocationDepth);
530 if( md.isStatic() ) {
531 // a static method is simply always the same, makes life easy
532 OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get(md);
533 ogAllPossibleCallees.merge(onlyPossibleCallee);
536 // if the method descriptor is virtual, then there could be a
537 // set of possible methods that will actually be invoked, so
538 // find all of them and merge all of their graphs together
539 TypeDescriptor typeDesc = fc.getThis().getType();
540 Set possibleCallees = callGraph.getMethods(md, typeDesc);
542 Iterator i = possibleCallees.iterator();
543 while( i.hasNext() ) {
544 MethodDescriptor possibleMd = (MethodDescriptor) i.next();
545 OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd);
546 ogAllPossibleCallees.merge(ogPotentialCallee);
550 // Now we should have the following information to resolve this method call:
552 // 1. A FlatCall fc to query for the caller's context (argument labels, etc)
554 // 2. Whether the method is static; if not we need to deal with the "this" pointer
556 // *******************************************************************************************
557 // 3. The original FlatMethod flatm to query for callee's context (paramter labels)
558 // NOTE! I assume FlatMethod before virtual dispatch accurately describes all possible methods!
559 // *******************************************************************************************
561 // 4. The OwnershipGraph ogAllPossibleCallees is a merge of every ownership graph of all the possible
562 // methods to capture any possible references made.
564 og.resolveMethodCall(fc, md.isStatic(), flatm, ogAllPossibleCallees);
567 case FKind.FlatReturnNode:
568 FlatReturnNode frn = (FlatReturnNode) fn;
569 rhs = frn.getReturnTemp();
572 og.assignReturnEqualToTemp(rhs);
575 setRetNodes.add(frn);
581 // this method should generate integers strictly greater than zero!
582 // special "shadow" regions are made from a heap region by negating
584 static public Integer generateUniqueHeapRegionNodeID() {
586 return new Integer(uniqueIDcount);
590 private OwnershipGraph getGraphFromFlatNode(FlatNode fn) {
591 if( !mapFlatNodeToOwnershipGraph.containsKey(fn) ) {
592 mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth) );
595 return mapFlatNodeToOwnershipGraph.get(fn);
598 private void setGraphForFlatNode(FlatNode fn, OwnershipGraph og) {
599 mapFlatNodeToOwnershipGraph.put(fn, og);
604 // return just the allocation site associated with one FlatNew node
605 private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
607 if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
608 AllocationSite as = new AllocationSite(allocationDepth, fn.getType() );
610 // the newest nodes are single objects
611 for( int i = 0; i < allocationDepth; ++i ) {
612 Integer id = generateUniqueHeapRegionNodeID();
613 as.setIthOldest(i, id);
616 // the oldest node is a summary node
617 Integer idSummary = generateUniqueHeapRegionNodeID();
618 as.setSummary(idSummary);
620 mapFlatNewToAllocationSite.put(fn, as);
623 return mapFlatNewToAllocationSite.get(fn);
627 // return all allocation sites in the method (there is one allocation
628 // site per FlatNew node in a method)
629 private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
630 if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
631 buildAllocationSiteSet(d);
634 return mapDescriptorToAllocationSiteSet.get(d);
638 private void buildAllocationSiteSet(Descriptor d) {
639 HashSet<AllocationSite> s = new HashSet<AllocationSite>();
642 if( d instanceof MethodDescriptor ) {
643 fm = state.getMethodFlat( (MethodDescriptor) d);
645 assert d instanceof TaskDescriptor;
646 fm = state.getMethodFlat( (TaskDescriptor) d);
649 // visit every node in this FlatMethod's IR graph
650 // and make a set of the allocation sites from the
651 // FlatNew node's visited
652 HashSet<FlatNode> visited = new HashSet<FlatNode>();
653 HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
656 while( !toVisit.isEmpty() ) {
657 FlatNode n = toVisit.iterator().next();
659 if( n instanceof FlatNew ) {
660 s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
666 for( int i = 0; i < n.numNext(); ++i ) {
667 FlatNode child = n.getNext(i);
668 if( !visited.contains(child) ) {
674 mapDescriptorToAllocationSiteSet.put(d, s);
678 private HashSet<AllocationSite>
679 getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
681 HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
682 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
683 HashSet<Descriptor> visited = new HashSet<Descriptor>();
687 // traverse this task and all methods reachable from this task
688 while( !toVisit.isEmpty() ) {
689 Descriptor d = toVisit.iterator().next();
693 HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
694 Iterator asItr = asSet.iterator();
695 while( asItr.hasNext() ) {
696 AllocationSite as = (AllocationSite) asItr.next();
697 if( as.getType().getClassDesc().hasFlags() ) {
702 // enqueue callees of this method to be searched for
703 // allocation sites also
704 Set callees = callGraph.getCalleeSet(d);
705 if( callees != null ) {
706 Iterator methItr = callees.iterator();
707 while( methItr.hasNext() ) {
708 MethodDescriptor md = (MethodDescriptor) methItr.next();
710 if( !visited.contains(md) ) {
723 private HashSet<Integer> getHeapRegionIDset(OwnershipGraph og,
726 assert og.paramIndex2id.containsKey(paramIndex);
727 Integer idParam = og.paramIndex2id.get(paramIndex);
729 HashSet<Integer> idSet = new HashSet<Integer>();
736 private HashSet<Integer> getHeapRegionIDset(AllocationSite alloc) {
738 HashSet<Integer> idSet = new HashSet<Integer>();
740 for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
741 Integer id = alloc.getIthOldest(i);
745 Integer idSummary = alloc.getSummary();
746 idSet.add(idSummary);
751 private HashSet<Integer> getHeapRegionIDset(HashSet<AllocationSite> allocSet) {
753 HashSet<Integer> idSet = new HashSet<Integer>();
755 Iterator allocItr = allocSet.iterator();
756 while( allocItr.hasNext() ) {
757 AllocationSite alloc = (AllocationSite) allocItr.next();
759 for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
760 Integer id = alloc.getIthOldest(i);
764 Integer idSummary = alloc.getSummary();
765 idSet.add(idSummary);
771 private boolean createsPotentialAliases(OwnershipGraph og,
772 HashSet<Integer> idSetA,
773 HashSet<Integer> idSetB) {
774 boolean potentialAlias = false;
777 // first expand set B into the set of all heap region node ID's
778 // reachable from the nodes in set B
779 HashSet<Integer> idSetReachableFromB = og.getReachableSet( idSetB );
781 // then see if anything in A can reach a node in the set reachable
782 // from B. If so, there is a potential alias.
783 Iterator i = idSetA.iterator();
784 while( i.hasNext() ) {
785 Integer id = (Integer) i.next();
786 if( og.canIdReachSet( id, idSetB ) ) {