1 package Analysis.OwnershipAnalysis;
3 import Analysis.CallGraph.*;
10 public class OwnershipAnalysis {
12 ///////////////////////////////////////////
14 // Public interface to discover possible
15 // aliases in the program under analysis
17 ///////////////////////////////////////////
19 public HashSet<AllocationSite>
20 getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) {
22 return getFlaggedAllocationSitesReachableFromTaskPRIVATE( td );
25 public AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) {
26 return getAllocationSiteFromFlatNewPRIVATE( fn );
29 public boolean createsPotentialAliases( Descriptor taskOrMethod,
33 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
36 return createsPotentialAliases( og,
37 getHeapRegionIDset( og, paramIndex1 ),
38 getHeapRegionIDset( og, paramIndex2 ) );
41 public boolean createsPotentialAliases( Descriptor taskOrMethod,
43 AllocationSite alloc ) {
45 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
48 return createsPotentialAliases( og,
49 getHeapRegionIDset( og, paramIndex ),
50 getHeapRegionIDset( alloc ) );
53 public boolean createsPotentialAliases( Descriptor taskOrMethod,
57 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
60 return createsPotentialAliases( og,
61 getHeapRegionIDset( og, paramIndex ),
62 getHeapRegionIDset( alloc ) );
65 public boolean createsPotentialAliases( Descriptor taskOrMethod,
66 AllocationSite alloc1,
67 AllocationSite alloc2 ) {
69 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
72 return createsPotentialAliases( og,
73 getHeapRegionIDset( alloc1 ),
74 getHeapRegionIDset( alloc2 ) );
77 public boolean createsPotentialAliases( Descriptor taskOrMethod,
79 HashSet<AllocationSite> allocSet ) {
81 OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
84 return createsPotentialAliases( og,
85 getHeapRegionIDset( alloc ),
86 getHeapRegionIDset( allocSet ) );
90 // use the methods given above to check every possible alias
91 // between task parameters and flagged allocation sites reachable
93 public void writeAllAliases(String outputFile) throws java.io.IOException {
95 BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
97 // look through every task for potential aliases
98 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
99 while( taskItr.hasNext() ) {
100 TaskDescriptor td = (TaskDescriptor) taskItr.next();
102 HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask( td );
104 // for each task parameter, check for aliases with
105 // other task parameters and every allocation site
106 // reachable from this task
107 FlatMethod fm = state.getMethodFlat( td );
108 for( int i = 0; i < fm.numParameters(); ++i ) {
110 // for the ith parameter check for aliases to all
111 // higher numbered parameters
112 for( int j = i + 1; j < fm.numParameters(); ++j ) {
113 if( createsPotentialAliases( td, i, j ) ) {
114 bw.write( "Task "+td+" potentially aliases parameters "+i+" and "+j+".\n" );
118 // for the ith parameter, check for aliases against
119 // the set of allocation sites reachable from this
121 Iterator allocItr = allocSites.iterator();
122 while( allocItr.hasNext() ) {
123 AllocationSite as = (AllocationSite) allocItr.next();
124 if( createsPotentialAliases( td, i, as ) ) {
125 bw.write( "Task "+td+" potentially aliases parameter "+i+" and "+as+".\n" );
130 // for each allocation site check for aliases with
131 // other allocation sites in the context of execution
133 Iterator allocItr = allocSites.iterator();
134 while( allocItr.hasNext() ) {
135 AllocationSite as = (AllocationSite) allocItr.next();
136 if( createsPotentialAliases( td, as, allocSites ) ) {
137 bw.write( "Task "+td+" potentially aliases "+as+" and the rest of the set.\n" );
146 ///////////////////////////////////////////
148 // end public interface
150 ///////////////////////////////////////////
159 // data from the compiler
161 private CallGraph callGraph;
162 private int allocationDepth;
164 // used to identify HeapRegionNode objects
165 // A unique ID equates an object in one
166 // ownership graph with an object in another
167 // graph that logically represents the same
169 static private int uniqueIDcount = 0;
172 // Use these data structures to track progress of
173 // processing all methods in the program, and by methods
174 // TaskDescriptor and MethodDescriptor are combined
175 // together, with a common parent class Descriptor
176 private HashSet <Descriptor> descriptorsToVisit;
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;
188 // this analysis generates an ownership graph for every task
190 public OwnershipAnalysis(State state,
192 int allocationDepth) throws java.io.IOException {
194 this.callGraph = callGraph;
195 this.allocationDepth = allocationDepth;
197 // temporary for debugging
198 this.allocationDepth = 1;
200 descriptorsToVisit = new HashSet<Descriptor>();
202 mapDescriptorToCompleteOwnershipGraph =
203 new Hashtable<Descriptor, OwnershipGraph>();
205 mapFlatNewToAllocationSite =
206 new Hashtable<FlatNew, AllocationSite>();
208 mapDescriptorToAllocationSiteSet =
209 new Hashtable<Descriptor, HashSet<AllocationSite> >();
211 // use this set to prevent infinite recursion when
212 // traversing the call graph
213 HashSet<Descriptor> calleesScheduled = new HashSet<Descriptor>();
216 // initialize methods to visit as the set of all tasks in the
217 // program and then any method that could be called starting
219 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
220 while( taskItr.hasNext() ) {
221 Descriptor d = (Descriptor) taskItr.next();
222 descriptorsToVisit.add(d);
224 // recursively find all callees from this task
225 scheduleAllCallees(calleesScheduled, d);
228 // before beginning analysis, initialize every scheduled method
229 // with an ownership graph that has populated parameter index tables
230 // by analyzing the first node which is always a FlatMethod node
231 Iterator<Descriptor> dItr = calleesScheduled.iterator();
232 while( dItr.hasNext() ) {
233 Descriptor d = dItr.next();
234 OwnershipGraph og = new OwnershipGraph(allocationDepth);
237 if( d instanceof MethodDescriptor ) {
238 fm = state.getMethodFlat( (MethodDescriptor) d);
240 assert d instanceof TaskDescriptor;
241 fm = state.getMethodFlat( (TaskDescriptor) d);
244 analyzeFlatNode(d, fm, null, og);
245 mapDescriptorToCompleteOwnershipGraph.put(d, og);
248 // as mentioned above, analyze methods one-by-one, possibly revisiting
249 // a method if the methods that it calls are updated
253 // called from the constructor to help initialize the set
254 // of methods that needs to be analyzed by ownership analysis
255 private void scheduleAllCallees(HashSet<Descriptor> calleesScheduled,
257 if( calleesScheduled.contains(d) ) {
260 calleesScheduled.add(d);
262 Set callees = callGraph.getCalleeSet(d);
263 if( callees == null ) {
267 Iterator methItr = callees.iterator();
268 while( methItr.hasNext() ) {
269 MethodDescriptor md = (MethodDescriptor) methItr.next();
270 descriptorsToVisit.add(md);
272 // recursively find all callees from this task
273 scheduleAllCallees(calleesScheduled, md);
278 // manage the set of tasks and methods to be analyzed
279 // and be sure to reschedule tasks/methods when the methods
280 // they call are updated
281 private void analyzeMethods() throws java.io.IOException {
283 while( !descriptorsToVisit.isEmpty() ) {
284 Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
285 descriptorsToVisit.remove(d);
287 // because the task or method descriptor just extracted
288 // was in the "to visit" set it either hasn't been analyzed
289 // yet, or some method that it depends on has been
290 // updated. Recompute a complete ownership graph for
291 // this task/method and compare it to any previous result.
292 // If there is a change detected, add any methods/tasks
293 // that depend on this one to the "to visit" set.
295 System.out.println("Analyzing " + d);
298 if( d instanceof MethodDescriptor ) {
299 fm = state.getMethodFlat( (MethodDescriptor) d);
301 assert d instanceof TaskDescriptor;
302 fm = state.getMethodFlat( (TaskDescriptor) d);
305 OwnershipGraph og = analyzeFlatMethod(d, fm);
306 OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get(d);
307 if( !og.equals(ogPrev) ) {
308 mapDescriptorToCompleteOwnershipGraph.put(d, og);
313 boolean pruneGarbage,
314 boolean writeReferencers
316 og.writeGraph(d, true, true, true, false);
318 // only methods have dependents, tasks cannot
319 // be invoked by any user program calls
320 if( d instanceof MethodDescriptor ) {
321 MethodDescriptor md = (MethodDescriptor) d;
322 Set dependents = callGraph.getCallerSet(md);
323 if( dependents != null ) {
324 descriptorsToVisit.addAll(dependents);
336 // keep passing the Descriptor of the method along for debugging
337 // and dot file writing
338 private OwnershipGraph
339 analyzeFlatMethod(Descriptor mDesc,
340 FlatMethod flatm) throws java.io.IOException {
342 // initialize flat nodes to visit as the flat method
343 // because all other nodes in this flat method are
344 // decendents of the flat method itself
345 flatNodesToVisit = new HashSet<FlatNode>();
346 flatNodesToVisit.add(flatm);
348 // initilize the mapping of flat nodes in this flat method to
349 // ownership graph results to an empty mapping
350 mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
352 // initialize the set of return nodes that will be combined as
353 // the final ownership graph result to return as an empty set
354 returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
356 while( !flatNodesToVisit.isEmpty() ) {
357 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
358 flatNodesToVisit.remove(fn);
360 // perform this node's contributions to the ownership
361 // graph on a new copy, then compare it to the old graph
362 // at this node to see if anything was updated.
363 OwnershipGraph og = new OwnershipGraph(allocationDepth);
365 // start by merging all node's parents' graphs
366 for( int i = 0; i < fn.numPrev(); ++i ) {
367 FlatNode pn = fn.getPrev(i);
368 OwnershipGraph ogParent = getGraphFromFlatNode(pn);
372 // apply the analysis of the flat node to the
373 // ownership graph made from the merge of the
375 analyzeFlatNode(mDesc,
377 returnNodesToCombineForCompleteOwnershipGraph,
380 // if the results of the new graph are different from
381 // the current graph at this node, replace the graph
382 // with the update and enqueue the children for
384 OwnershipGraph ogPrev = getGraphFromFlatNode(fn);
386 if( !og.equals(ogPrev) ) {
387 setGraphForFlatNode(fn, og);
393 String s = String.format("debug%04d", x);
394 //og.writeGraph( s, true, true, true, false );
399 for( int i = 0; i < fn.numNext(); i++ ) {
400 FlatNode nn = fn.getNext(i);
401 flatNodesToVisit.add(nn);
406 // end by merging all return nodes into a complete
407 // ownership graph that represents all possible heap
408 // states after the flat method returns
409 OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth);
410 Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
411 while( retItr.hasNext() ) {
412 FlatReturnNode frn = (FlatReturnNode) retItr.next();
413 OwnershipGraph ogr = getGraphFromFlatNode(frn);
414 completeGraph.merge(ogr);
416 return completeGraph;
421 analyzeFlatNode(Descriptor methodDesc,
423 HashSet<FlatReturnNode> setRetNodes,
424 OwnershipGraph og) throws java.io.IOException {
430 // use node type to decide what alterations to make
431 // to the ownership graph
432 switch( fn.kind() ) {
434 case FKind.FlatMethod:
435 FlatMethod fm = (FlatMethod) fn;
437 // there should only be one FlatMethod node as the
438 // parent of all other FlatNode objects, so take
439 // the opportunity to construct the initial graph by
440 // adding parameters labels to new heap regions
441 for( int i = 0; i < fm.numParameters(); ++i ) {
442 TempDescriptor tdParam = fm.getParameter(i);
443 og.assignParameterAllocationToTemp(methodDesc instanceof TaskDescriptor,
450 case FKind.FlatOpNode:
451 FlatOpNode fon = (FlatOpNode) fn;
452 if( fon.getOp().getOp() == Operation.ASSIGN ) {
455 og.assignTempYToTempX(src, dst);
459 case FKind.FlatFieldNode:
460 FlatFieldNode ffn = (FlatFieldNode) fn;
463 fld = ffn.getField();
464 if( !fld.getType().isPrimitive() ) {
465 og.assignTempYFieldFToTempX(src, fld, dst);
469 case FKind.FlatSetFieldNode:
470 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
473 fld = fsfn.getField();
474 og.assignTempYToTempXFieldF(src, dst, fld);
478 FlatNew fnn = (FlatNew) fn;
480 AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
482 og.assignNewAllocationToTempX(dst, as);
486 FlatCall fc = (FlatCall) fn;
487 MethodDescriptor md = fc.getMethod();
488 FlatMethod flatm = state.getMethodFlat(md);
489 //HashSet<AllocationSite> allocSiteSet = getAllocationSiteSet( md );
490 OwnershipGraph ogAllPossibleCallees = new OwnershipGraph(allocationDepth);
492 if( md.isStatic() ) {
493 // a static method is simply always the same, makes life easy
494 OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get(md);
495 ogAllPossibleCallees.merge(onlyPossibleCallee);
498 if( onlyPossibleCallee != null ) {
499 onlyPossibleCallee.writeGraph( "only", false, false );
500 System.out.println( "There was only one possible callee, "+md );
505 // if the method descriptor is virtual, then there could be a
506 // set of possible methods that will actually be invoked, so
507 // find all of them and merge all of their graphs together
508 TypeDescriptor typeDesc = fc.getThis().getType();
509 Set possibleCallees = callGraph.getMethods(md, typeDesc);
513 Iterator i = possibleCallees.iterator();
514 while( i.hasNext() ) {
515 MethodDescriptor possibleMd = (MethodDescriptor) i.next();
516 //allocSiteSet.addAll( getAllocationSiteSet( possibleMd ) );
517 OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd);
520 if( ogPotentialCallee != null ) {
521 ogPotentialCallee.writeGraph( "potential"+j, false, false );
526 ogAllPossibleCallees.merge(ogPotentialCallee);
529 //System.out.println( "There were "+j+" potential callees merged together." );
532 //System.out.println( "AllocationSiteSet has "+allocSiteSet.size()+" items." );
534 // now we should have the following information to resolve this method call:
536 // 1. A FlatCall fc to query for the caller's context (argument labels, etc)
538 // 2. Whether the method is static; if not we need to deal with the "this" pointer
540 // *******************************************************************************************
541 // 3. The original FlatMethod flatm to query for callee's context (paramter labels)
542 // NOTE! I assume FlatMethod before virtual dispatch accurately describes all possible methods!
543 // *******************************************************************************************
545 // 4. The OwnershipGraph ogAllPossibleCallees is a merge of every ownership graph of all the possible
546 // methods to capture any possible references made.
548 // 5. The Set of AllocationSite objects, allocSiteSet that is the set of allocation sites from
549 // every possible method we might have chosen
551 og.resolveMethodCall(fc, md.isStatic(), flatm, ogAllPossibleCallees);
554 case FKind.FlatReturnNode:
555 FlatReturnNode frn = (FlatReturnNode) fn;
556 setRetNodes.add(frn);
562 // this method should generate integers strictly greater than zero!
563 // special "shadow" regions are made from a heap region by negating
565 static public Integer generateUniqueHeapRegionNodeID() {
567 return new Integer(uniqueIDcount);
571 private OwnershipGraph getGraphFromFlatNode(FlatNode fn) {
572 if( !mapFlatNodeToOwnershipGraph.containsKey(fn) ) {
573 mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth) );
576 return mapFlatNodeToOwnershipGraph.get(fn);
579 private void setGraphForFlatNode(FlatNode fn, OwnershipGraph og) {
580 mapFlatNodeToOwnershipGraph.put(fn, og);
588 // return just the allocation site associated with one FlatNew node
589 private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
591 if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
592 AllocationSite as = new AllocationSite(allocationDepth, fn.getType() );
594 // the newest nodes are single objects
595 for( int i = 0; i < allocationDepth; ++i ) {
596 Integer id = generateUniqueHeapRegionNodeID();
597 as.setIthOldest(i, id);
600 // the oldest node is a summary node
601 Integer idSummary = generateUniqueHeapRegionNodeID();
602 as.setSummary(idSummary);
604 mapFlatNewToAllocationSite.put(fn, as);
607 return mapFlatNewToAllocationSite.get(fn);
611 // return all allocation sites in the method (there is one allocation
612 // site per FlatNew node in a method)
613 private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
614 if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
615 buildAllocationSiteSet(d);
618 return mapDescriptorToAllocationSiteSet.get(d);
622 private void buildAllocationSiteSet(Descriptor d) {
623 HashSet<AllocationSite> s = new HashSet<AllocationSite>();
626 if( d instanceof MethodDescriptor ) {
627 fm = state.getMethodFlat( (MethodDescriptor) d);
629 assert d instanceof TaskDescriptor;
630 fm = state.getMethodFlat( (TaskDescriptor) d);
633 // visit every node in this FlatMethod's IR graph
634 // and make a set of the allocation sites from the
635 // FlatNew node's visited
636 HashSet<FlatNode> visited = new HashSet<FlatNode>();
637 HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
640 while( !toVisit.isEmpty() ) {
641 FlatNode n = toVisit.iterator().next();
643 if( n instanceof FlatNew ) {
644 s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
650 for( int i = 0; i < n.numNext(); ++i ) {
651 FlatNode child = n.getNext(i);
652 if( !visited.contains(child) ) {
658 mapDescriptorToAllocationSiteSet.put(d, s);
662 private HashSet<AllocationSite>
663 getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
665 HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
666 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
667 HashSet<Descriptor> visited = new HashSet<Descriptor>();
671 // traverse this task and all methods reachable from this task
672 while( !toVisit.isEmpty() ) {
673 Descriptor d = toVisit.iterator().next();
677 HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
678 Iterator asItr = asSet.iterator();
679 while( asItr.hasNext() ) {
680 AllocationSite as = (AllocationSite) asItr.next();
681 if( as.getType().getClassDesc().hasFlags() ) {
686 // enqueue callees of this method to be searched for
687 // allocation sites also
688 Set callees = callGraph.getCalleeSet(d);
689 if( callees != null ) {
690 Iterator methItr = callees.iterator();
691 while( methItr.hasNext() ) {
692 MethodDescriptor md = (MethodDescriptor) methItr.next();
694 if( !visited.contains(md) ) {
707 private HashSet<Integer> getHeapRegionIDset(OwnershipGraph og,
710 assert og.paramIndex2id.containsKey(paramIndex);
711 Integer idParam = og.paramIndex2id.get(paramIndex);
713 HashSet<Integer> idSet = new HashSet<Integer>();
720 private HashSet<Integer> getHeapRegionIDset(AllocationSite alloc) {
722 HashSet<Integer> idSet = new HashSet<Integer>();
724 for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
725 Integer id = alloc.getIthOldest(i);
729 Integer idSummary = alloc.getSummary();
730 idSet.add(idSummary);
735 private HashSet<Integer> getHeapRegionIDset(HashSet<AllocationSite> allocSet) {
737 HashSet<Integer> idSet = new HashSet<Integer>();
739 Iterator allocItr = allocSet.iterator();
740 while( allocItr.hasNext() ) {
741 AllocationSite alloc = (AllocationSite) allocItr.next();
743 for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
744 Integer id = alloc.getIthOldest(i);
748 Integer idSummary = alloc.getSummary();
749 idSet.add(idSummary);
755 private boolean createsPotentialAliases(OwnershipGraph og,
756 HashSet<Integer> idSetA,
757 HashSet<Integer> idSetB) {
758 boolean potentialAlias = false;
761 // first expand set B into the set of all heap region node ID's
762 // reachable from the nodes in set B
763 HashSet<Integer> idSetReachableFromB = og.getReachableSet( idSetB );
765 // then see if anything in A can reach a node in the set reachable
766 // from B. If so, there is a potential alias.
767 Iterator i = idSetA.iterator();
768 while( i.hasNext() ) {
769 Integer id = (Integer) i.next();
770 if( og.canIdReachSet( id, idSetB ) ) {