Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import Analysis.CallGraph.*;
   4 import IR.*;
   5 import IR.Flat.*;
   6 import java.util.*;
   7 import java.io.*;
   8
   9
  10 public class OwnershipAnalysis {
  11
  12     ///////////////////////////////////////////
  13     //
  14     //  Public interface to discover possible
  15     //  aliases in the program under analysis
  16     //
  17     ///////////////////////////////////////////
  18     public HashSet<AllocationSite>
  19         getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) {
  20
  21         return getFlaggedAllocationSitesReachableFromTaskPRIVATE( td );
  22     }
  23
  24     public AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) {
  25         return getAllocationSiteFromFlatNewPRIVATE( fn );
  26     }
  27
  28     public boolean createsPotentialAliases( Descriptor     taskOrMethod,
  29                                             int            paramIndex1,
  30                                             int            paramIndex2 ) {
  31
  32         OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  33         assert( og != null );
  34
  35         return createsPotentialAliases( og,
  36                                         getHeapRegionIDset( og, paramIndex1 ),
  37                                         getHeapRegionIDset( og, paramIndex2 ) );
  38     }
  39
  40     public boolean createsPotentialAliases( Descriptor     taskOrMethod,
  41                                             int            paramIndex,
  42                                             AllocationSite alloc ) {
  43
  44         OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  45         assert( og != null );
  46
  47         return createsPotentialAliases( og,
  48                                         getHeapRegionIDset( og, paramIndex ),
  49                                         getHeapRegionIDset( alloc ) );
  50     }
  51
  52     public boolean createsPotentialAliases( Descriptor     taskOrMethod,
  53                                             AllocationSite alloc,
  54                                             int            paramIndex ) {
  55
  56         OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  57         assert( og != null );
  58
  59         return createsPotentialAliases( og,
  60                                         getHeapRegionIDset( og, paramIndex ),
  61                                         getHeapRegionIDset( alloc ) );
  62     }
  63
  64     public boolean createsPotentialAliases( Descriptor     taskOrMethod,
  65                                             AllocationSite alloc1,
  66                                             AllocationSite alloc2 ) {
  67
  68         OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  69         assert( og != null );
  70
  71         return createsPotentialAliases( og,
  72                                         getHeapRegionIDset( alloc1 ),
  73                                         getHeapRegionIDset( alloc2 ) );
  74     }
  75
  76     public boolean createsPotentialAliases( Descriptor              taskOrMethod,
  77                                             AllocationSite          alloc,
  78                                             HashSet<AllocationSite> allocSet ) {
  79
  80         OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  81         assert( og != null );
  82
  83         return createsPotentialAliases( og,
  84                                         getHeapRegionIDset( alloc ),
  85                                         getHeapRegionIDset( allocSet ) );
  86     }
  87
  88     // use the methods given above to check every possible alias
  89     // between task parameters and flagged allocation sites reachable
  90     // from the task
  91     public void writeAllAliases( String outputFile ) throws java.io.IOException {
  92
  93         BufferedWriter bw = new BufferedWriter( new FileWriter( outputFile ) );
  94
  95         // look through every task for potential aliases
  96         Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
  97         while( taskItr.hasNext() ) {
  98             TaskDescriptor td = (TaskDescriptor) taskItr.next();
  99
 100             HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask( td );
 101
 102             // for each task parameter, check for aliases with
 103             // other task parameters and every allocation site
 104             // reachable from this task
 105             FlatMethod fm = state.getMethodFlat( td );
 106             for( int i = 0; i < fm.numParameters(); ++i ) {
 107
 108                 // for the ith parameter check for aliases to all
 109                 // higher numbered parameters
 110                 for( int j = i + 1; j < fm.numParameters(); ++j ) {
 111                     if( createsPotentialAliases( td, i, j ) ) {
 112                         bw.write( "Task "+td+" potentially aliases parameters "+i+" and "+j+".\n" );
 113                     }
 114                 }
 115
 116                 // for the ith parameter, check for aliases against
 117                 // the set of allocation sites reachable from this
 118                 // task context
 119                 Iterator allocItr = allocSites.iterator();
 120                 while( allocItr.hasNext() ) {
 121                     AllocationSite as = (AllocationSite) allocItr.next();
 122                     if( createsPotentialAliases( td, i, as ) ) {
 123                         bw.write( "Task "+td+" potentially aliases parameter "+i+" and "+as+".\n" );
 124                     }
 125                 }
 126             }
 127
 128             // for each allocation site check for aliases with
 129             // other allocation sites in the context of execution
 130             // of this task
 131             Iterator allocItr = allocSites.iterator();
 132             while( allocItr.hasNext() ) {
 133                 AllocationSite as = (AllocationSite) allocItr.next();
 134                 if( createsPotentialAliases( td, as, allocSites ) ) {
 135                     bw.write( "Task "+td+" potentially aliases "+as+" and the rest of the set.\n" );
 136                 }
 137             }
 138         }
 139
 140         bw.close();
 141     }
 142
 143     ///////////////////////////////////////////
 144     //
 145     // end public interface
 146     //
 147     ///////////////////////////////////////////
 148
 149
 150
 151
 152
 153
 154
 155
 156     // data from the compiler
 157     private State     state;
 158     private CallGraph callGraph;
 159     private int       allocationDepth;
 160
 161     // used to identify HeapRegionNode objects
 162     // A unique ID equates an object in one
 163     // ownership graph with an object in another
 164     // graph that logically represents the same
 165     // heap region
 166     static private int uniqueIDcount = 0;
 167
 168
 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 HashSet  <Descriptor>                           descriptorsToVisit;
 174     private Hashtable<Descriptor, OwnershipGraph>           mapDescriptorToCompleteOwnershipGraph;
 175     private Hashtable<FlatNew,    AllocationSite>           mapFlatNewToAllocationSite;
 176     private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
 177
 178     // Use these data structures to track progress of one pass of
 179     // processing the FlatNodes of a particular method
 180     private HashSet  <FlatNode>                 flatNodesToVisit;
 181     private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
 182     private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
 183
 184
 185     // this analysis generates an ownership graph for every task
 186     // in the program
 187     public OwnershipAnalysis( State     state,
 188                               CallGraph callGraph,
 189                               int       allocationDepth ) throws java.io.IOException {
 190         this.state           = state;
 191         this.callGraph       = callGraph;
 192         this.allocationDepth = allocationDepth;
 193
 194         descriptorsToVisit = new HashSet<Descriptor>();
 195
 196         mapDescriptorToCompleteOwnershipGraph =
 197             new Hashtable<Descriptor, OwnershipGraph>();
 198
 199         mapFlatNewToAllocationSite =
 200             new Hashtable<FlatNew, AllocationSite>();
 201
 202         mapDescriptorToAllocationSiteSet =
 203             new Hashtable<Descriptor, HashSet<AllocationSite> >();
 204
 205         // use this set to prevent infinite recursion when
 206         // traversing the call graph
 207         HashSet<Descriptor> calleesScheduled = new HashSet<Descriptor>();
 208
 209         // initialize methods to visit as the set of all tasks in the
 210         // program and then any method that could be called starting
 211         // from those tasks
 212         Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 213         while( taskItr.hasNext() ) {
 214             Descriptor d = (Descriptor) taskItr.next();
 215             descriptorsToVisit.add( d );
 216
 217             // recursively find all callees from this task
 218             scheduleAllCallees( calleesScheduled, d );
 219         }
 220
 221         // as mentioned above, analyze methods one-by-one, possibly revisiting
 222         // a method if the methods that it calls are updated
 223         analyzeMethods();
 224     }
 225
 226     // called from the constructor to help initialize the set
 227     // of methods that needs to be analyzed by ownership analysis
 228     private void scheduleAllCallees( HashSet<Descriptor> calleesScheduled,
 229                                      Descriptor d ) {
 230         if( calleesScheduled.contains( d ) ) {
 231             return;
 232         }
 233         calleesScheduled.add( d );
 234
 235         Set callees = callGraph.getCalleeSet( d );
 236         if( callees == null ) {
 237             return;
 238         }
 239
 240         Iterator methItr = callees.iterator();
 241         while( methItr.hasNext() ) {
 242             MethodDescriptor md = (MethodDescriptor) methItr.next();
 243             descriptorsToVisit.add( md );
 244
 245             // recursively find all callees from this task
 246             scheduleAllCallees( calleesScheduled, md );
 247         }
 248     }
 249
 250
 251     // manage the set of tasks and methods to be analyzed
 252     // and be sure to reschedule tasks/methods when the methods
 253     // they call are updated
 254     private void analyzeMethods() throws java.io.IOException {
 255
 256         while( !descriptorsToVisit.isEmpty() ) {
 257             Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
 258             descriptorsToVisit.remove( d );
 259
 260             // because the task or method descriptor just extracted
 261             // was in the "to visit" set it either hasn't been analyzed
 262             // yet, or some method that it depends on has been
 263             // updated.  Recompute a complete ownership graph for
 264             // this task/method and compare it to any previous result.
 265             // If there is a change detected, add any methods/tasks
 266             // that depend on this one to the "to visit" set.
 267
 268             System.out.println( "Analyzing " + d );
 269
 270             FlatMethod fm;
 271             if( d instanceof MethodDescriptor ) {
 272                 fm = state.getMethodFlat( (MethodDescriptor) d );
 273             } else {
 274                 assert d instanceof TaskDescriptor;
 275                 fm = state.getMethodFlat( (TaskDescriptor) d );
 276             }
 277
 278             OwnershipGraph og     = analyzeFlatMethod( d, fm );
 279             OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get( d );
 280
 281             if( !og.equals( ogPrev ) ) {
 282                 mapDescriptorToCompleteOwnershipGraph.put( d, og );
 283
 284                 og.writeGraph( d, false, false );
 285
 286                 // only methods have dependents, tasks cannot
 287                 // be invoked by any user program calls
 288                 if( d instanceof MethodDescriptor ) {
 289                     MethodDescriptor md = (MethodDescriptor) d;
 290                     Set dependents = callGraph.getCallerSet( md );
 291                     if( dependents != null ) {
 292                         descriptorsToVisit.addAll( dependents );
 293                     }
 294                 }
 295             }
 296         }
 297
 298     }
 299
 300
 301     // keep passing the Descriptor of the method along for debugging
 302     // and dot file writing
 303     private OwnershipGraph
 304         analyzeFlatMethod( Descriptor mDesc,
 305                            FlatMethod flatm ) throws java.io.IOException {
 306
 307         // initialize flat nodes to visit as the flat method
 308         // because all other nodes in this flat method are
 309         // decendents of the flat method itself
 310         flatNodesToVisit = new HashSet<FlatNode>();
 311         flatNodesToVisit.add( flatm );
 312
 313         // initilize the mapping of flat nodes in this flat method to
 314         // ownership graph results to an empty mapping
 315         mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 316
 317         // initialize the set of return nodes that will be combined as
 318         // the final ownership graph result to return as an empty set
 319         returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 320
 321
 322         // DEBUG
 323         //int x = 0;
 324
 325
 326         while( !flatNodesToVisit.isEmpty() ) {
 327             FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 328             flatNodesToVisit.remove( fn );
 329
 330             // perform this node's contributions to the ownership
 331             // graph on a new copy, then compare it to the old graph
 332             // at this node to see if anything was updated.
 333             OwnershipGraph og = new OwnershipGraph( allocationDepth );
 334
 335             // start by merging all node's parents' graphs
 336             for( int i = 0; i < fn.numPrev(); ++i ) {
 337                 FlatNode       pn       = fn.getPrev( i );
 338                 OwnershipGraph ogParent = getGraphFromFlatNode( pn );
 339                 og.merge( ogParent );
 340             }
 341
 342             // apply the analysis of the flat node to the
 343             // ownership graph made from the merge of the
 344             // parent graphs
 345             analyzeFlatNode( mDesc,
 346                              fn,
 347                              returnNodesToCombineForCompleteOwnershipGraph,
 348                              og );
 349
 350             // if the results of the new graph are different from
 351             // the current graph at this node, replace the graph
 352             // with the update and enqueue the children for
 353             // processing
 354             OwnershipGraph ogPrev = getGraphFromFlatNode( fn );
 355
 356             if( !og.equals( ogPrev ) ) {
 357                 setGraphForFlatNode( fn, og );
 358
 359                 // DEBUG
 360                 /*
 361                 ++x;
 362
 363                 if( x > 5000 ) {
 364                 String s = String.format( "%04d", x );
 365                 og.writeGraph( "debug"+s, false, false );
 366                 }
 367
 368                 if( x == 5020 ) {
 369                     System.exit( -1 );
 370                 }
 371                 */
 372
 373                 for( int i = 0; i < fn.numNext(); i++ ) {
 374                     FlatNode nn = fn.getNext( i );
 375                     flatNodesToVisit.add( nn );
 376                 }
 377             }
 378         }
 379
 380         // end by merging all return nodes into a complete
 381         // ownership graph that represents all possible heap
 382         // states after the flat method returns
 383         OwnershipGraph completeGraph = new OwnershipGraph( allocationDepth );
 384         Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 385         while( retItr.hasNext() ) {
 386             FlatReturnNode frn = (FlatReturnNode) retItr.next();
 387             OwnershipGraph ogr = getGraphFromFlatNode( frn );
 388             completeGraph.merge( ogr );
 389         }
 390         return completeGraph;
 391     }
 392
 393
 394     private void
 395         analyzeFlatNode( Descriptor              methodDesc,
 396                          FlatNode                fn,
 397                          HashSet<FlatReturnNode> setRetNodes,
 398                          OwnershipGraph          og ) throws java.io.IOException {
 399
 400         TempDescriptor  src;
 401         TempDescriptor  dst;
 402         FieldDescriptor fld;
 403
 404         // use node type to decide what alterations to make
 405         // to the ownership graph
 406         switch( fn.kind() ) {
 407
 408         case FKind.FlatMethod:
 409             FlatMethod fm = (FlatMethod) fn;
 410
 411             // there should only be one FlatMethod node as the
 412             // parent of all other FlatNode objects, so take
 413             // the opportunity to construct the initial graph by
 414             // adding parameters labels to new heap regions
 415             for( int i = 0; i < fm.numParameters(); ++i ) {
 416                 TempDescriptor tdParam = fm.getParameter( i );
 417                 og.assignTempToParameterAllocation( methodDesc instanceof TaskDescriptor,
 418                                                     tdParam,
 419                                                     new Integer( i ) );
 420             }
 421
 422             break;
 423
 424         case FKind.FlatOpNode:
 425             FlatOpNode fon = (FlatOpNode) fn;
 426             if( fon.getOp().getOp() == Operation.ASSIGN ) {
 427                 src = fon.getLeft();
 428                 dst = fon.getDest();
 429                 og.assignTempToTemp( src, dst );
 430             }
 431             break;
 432
 433         case FKind.FlatFieldNode:
 434             FlatFieldNode ffn = (FlatFieldNode) fn;
 435             src = ffn.getSrc();
 436             dst = ffn.getDst();
 437             fld = ffn.getField();
 438             if( !fld.getType().isPrimitive() ) {
 439                 og.assignTempToField( src, dst, fld );
 440             }
 441             break;
 442
 443         case FKind.FlatSetFieldNode:
 444             FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 445             src = fsfn.getSrc();
 446             dst = fsfn.getDst();
 447             fld = fsfn.getField();
 448             og.assignFieldToTemp( src, dst, fld );
 449             break;
 450
 451         case FKind.FlatNew:
 452             FlatNew fnn = (FlatNew) fn;
 453             dst = fnn.getDst();
 454             AllocationSite as = getAllocationSiteFromFlatNewPRIVATE( fnn );
 455
 456             og.assignTempToNewAllocation( dst, as );
 457             break;
 458
 459         case FKind.FlatCall:
 460             FlatCall                fc           = (FlatCall) fn;
 461             MethodDescriptor        md           = fc.getMethod();
 462             FlatMethod              flatm        = state.getMethodFlat( md );
 463             //HashSet<AllocationSite> allocSiteSet = getAllocationSiteSet( md );
 464             OwnershipGraph ogAllPossibleCallees  = new OwnershipGraph( allocationDepth );
 465
 466             if( md.isStatic() ) {
 467                 // a static method is simply always the same, makes life easy
 468                 OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get( md );
 469                 ogAllPossibleCallees.merge( onlyPossibleCallee );
 470
 471                 /*
 472                 if( onlyPossibleCallee != null ) {
 473                     onlyPossibleCallee.writeGraph( "only", false, false );
 474                     System.out.println( "There was only one possible callee, "+md );
 475                 }
 476                 */
 477
 478             } else {
 479                 // if the method descriptor is virtual, then there could be a
 480                 // set of possible methods that will actually be invoked, so
 481                 // find all of them and merge all of their graphs together
 482                 TypeDescriptor typeDesc        = fc.getThis().getType();
 483                 Set            possibleCallees = callGraph.getMethods( md, typeDesc );
 484
 485                 //int j = 0;
 486
 487                 Iterator i = possibleCallees.iterator();
 488                 while( i.hasNext() ) {
 489                     MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 490                     //allocSiteSet.addAll( getAllocationSiteSet( possibleMd ) );
 491                     OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get( possibleMd );
 492
 493                     /*
 494                     if( ogPotentialCallee != null ) {
 495                         ogPotentialCallee.writeGraph( "potential"+j, false, false );
 496                         ++j;
 497                     }
 498                     */
 499
 500                     ogAllPossibleCallees.merge( ogPotentialCallee );
 501                 }
 502
 503                 //System.out.println( "There were "+j+" potential callees merged together." );
 504             }
 505
 506             //System.out.println( "AllocationSiteSet has "+allocSiteSet.size()+" items." );
 507
 508             // now we should have the following information to resolve this method call:
 509             //
 510             // 1. A FlatCall fc to query for the caller's context (argument labels, etc)
 511             //
 512             // 2. Whether the method is static; if not we need to deal with the "this" pointer
 513             //
 514             // *******************************************************************************************
 515             // 3. The original FlatMethod flatm to query for callee's context (paramter labels)
 516             //   NOTE!  I assume FlatMethod before virtual dispatch accurately describes all possible methods!
 517             // *******************************************************************************************
 518             //
 519             // 4. The OwnershipGraph ogAllPossibleCallees is a merge of every ownership graph of all the possible
 520             // methods to capture any possible references made.
 521             //
 522             // 5. The Set of AllocationSite objects, allocSiteSet that is the set of allocation sites from
 523             // every possible method we might have chosen
 524             //
 525             og.resolveMethodCall( fc, md.isStatic(), flatm, ogAllPossibleCallees );
 526
 527             //og.writeGraph( methodDesc, fn );
 528             break;
 529
 530         case FKind.FlatReturnNode:
 531             FlatReturnNode frn = (FlatReturnNode) fn;
 532             setRetNodes.add( frn );
 533             //og.writeGraph( methodDesc, fn );
 534             break;
 535         }
 536     }
 537
 538
 539     static public Integer generateUniqueHeapRegionNodeID() {
 540         ++uniqueIDcount;
 541         return new Integer( uniqueIDcount );
 542     }
 543
 544
 545     private OwnershipGraph getGraphFromFlatNode( FlatNode fn ) {
 546         if( !mapFlatNodeToOwnershipGraph.containsKey( fn ) ) {
 547             mapFlatNodeToOwnershipGraph.put( fn, new OwnershipGraph( allocationDepth ) );
 548         }
 549
 550         return mapFlatNodeToOwnershipGraph.get( fn );
 551     }
 552
 553     private void setGraphForFlatNode( FlatNode fn, OwnershipGraph og ) {
 554         mapFlatNodeToOwnershipGraph.put( fn, og );
 555     }
 556
 557
 558
 559
 560
 561
 562     // return just the allocation site associated with one FlatNew node
 563     private AllocationSite getAllocationSiteFromFlatNewPRIVATE( FlatNew fn ) {
 564         if( !mapFlatNewToAllocationSite.containsKey( fn ) ) {
 565             AllocationSite as = new AllocationSite( allocationDepth, fn.getType() );
 566
 567             // the newest nodes are single objects
 568             for( int i = 0; i < allocationDepth; ++i ) {
 569                 Integer id = generateUniqueHeapRegionNodeID();
 570                 as.setIthOldest( i, id );
 571             }
 572
 573             // the oldest node is a summary node
 574             Integer idSummary = generateUniqueHeapRegionNodeID();
 575             as.setSummary( idSummary );
 576
 577             mapFlatNewToAllocationSite.put( fn, as );
 578         }
 579
 580         return mapFlatNewToAllocationSite.get( fn );
 581     }
 582
 583
 584     // return all allocation sites in the method (there is one allocation
 585     // site per FlatNew node in a method)
 586     private HashSet<AllocationSite> getAllocationSiteSet( Descriptor d ) {
 587         if( !mapDescriptorToAllocationSiteSet.containsKey( d ) ) {
 588             buildAllocationSiteSet( d );
 589         }
 590
 591         return mapDescriptorToAllocationSiteSet.get( d );
 592
 593     }
 594
 595     private void buildAllocationSiteSet( Descriptor d ) {
 596         HashSet<AllocationSite> s = new HashSet<AllocationSite>();
 597
 598         FlatMethod fm;
 599         if( d instanceof MethodDescriptor ) {
 600             fm = state.getMethodFlat( (MethodDescriptor) d );
 601         } else {
 602             assert d instanceof TaskDescriptor;
 603             fm = state.getMethodFlat( (TaskDescriptor) d );
 604         }
 605
 606         // visit every node in this FlatMethod's IR graph
 607         // and make a set of the allocation sites from the
 608         // FlatNew node's visited
 609         HashSet<FlatNode> visited = new HashSet<FlatNode>();
 610         HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
 611         toVisit.add( fm );
 612
 613         while( !toVisit.isEmpty() ) {
 614             FlatNode n = toVisit.iterator().next();
 615
 616             if( n instanceof FlatNew ) {
 617                 s.add( getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n ) );
 618             }
 619
 620             toVisit.remove( n );
 621             visited.add( n );
 622
 623             for( int i = 0; i < n.numNext(); ++i ) {
 624                 FlatNode child = n.getNext( i );
 625                 if( !visited.contains( child ) ) {
 626                     toVisit.add( child );
 627                 }
 628             }
 629         }
 630
 631         mapDescriptorToAllocationSiteSet.put( d, s );
 632     }
 633
 634
 635     private HashSet<AllocationSite>
 636         getFlaggedAllocationSitesReachableFromTaskPRIVATE( TaskDescriptor td ) {
 637
 638         HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
 639         HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
 640         HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
 641
 642         toVisit.add( td );
 643
 644         // traverse this task and all methods reachable from this task
 645         while( !toVisit.isEmpty() ) {
 646             Descriptor d = toVisit.iterator().next();
 647             toVisit.remove( d );
 648             visited.add( d );
 649
 650             HashSet<AllocationSite> asSet = getAllocationSiteSet( d );
 651             Iterator asItr = asSet.iterator();
 652             while( asItr.hasNext() ) {
 653                 AllocationSite as = (AllocationSite) asItr.next();
 654                 if( as.getType().getClassDesc().hasFlags() ) {
 655                     asSetTotal.add( as );
 656                 }
 657             }
 658
 659             // enqueue callees of this method to be searched for
 660             // allocation sites also
 661             Set callees = callGraph.getCalleeSet( d );
 662             if( callees != null ) {
 663                 Iterator methItr = callees.iterator();
 664                 while( methItr.hasNext() ) {
 665                     MethodDescriptor md = (MethodDescriptor) methItr.next();
 666
 667                     if( !visited.contains( md ) ) {
 668                         toVisit.add( md );
 669                     }
 670                 }
 671             }
 672         }
 673
 674
 675         return asSetTotal;
 676     }
 677
 678
 679
 680     private HashSet<Integer> getHeapRegionIDset( OwnershipGraph og,
 681                                                  int paramIndex ) {
 682
 683         assert og.paramIndex2id.containsKey( paramIndex );
 684         Integer idParam = og.paramIndex2id.get( paramIndex );
 685
 686         HashSet<Integer> idSet = new HashSet<Integer>();
 687         idSet.add( idParam );
 688
 689         return idSet;
 690     }
 691
 692     private HashSet<Integer> getHeapRegionIDset( AllocationSite alloc ) {
 693
 694         HashSet<Integer> idSet = new HashSet<Integer>();
 695
 696         for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
 697             Integer id = alloc.getIthOldest( i );
 698             idSet.add( id );
 699         }
 700
 701         Integer idSummary = alloc.getSummary();
 702         idSet.add( idSummary );
 703
 704         return idSet;
 705     }
 706
 707     private HashSet<Integer> getHeapRegionIDset( HashSet<AllocationSite> allocSet ) {
 708
 709         HashSet<Integer> idSet = new HashSet<Integer>();
 710
 711         Iterator allocItr = allocSet.iterator();
 712         while( allocItr.hasNext() ) {
 713             AllocationSite alloc = (AllocationSite) allocItr.next();
 714
 715             for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
 716                 Integer id = alloc.getIthOldest( i );
 717                 idSet.add( id );
 718             }
 719
 720             Integer idSummary = alloc.getSummary();
 721             idSet.add( idSummary );
 722         }
 723
 724         return idSet;
 725     }
 726
 727     private boolean createsPotentialAliases( OwnershipGraph   og,
 728                                              HashSet<Integer> idSetA,
 729                                              HashSet<Integer> idSetB ) {
 730         boolean potentialAlias = false;
 731
 732         // first expand set B into the set of all heap region node ID's
 733         // reachable from the nodes in set B
 734         HashSet<Integer> idSetReachableFromB = og.getReachableSet( idSetB );
 735
 736         // then see if anything in A can reach a node in the set reachable
 737         // from B.  If so, there is a potential alias.
 738         Iterator i = idSetA.iterator();
 739         while( i.hasNext() ) {
 740             Integer id = (Integer) i.next();
 741             if( og.canIdReachSet( id, idSetB ) ) {
 742                 return true;
 743             }
 744         }
 745
 746         return false;
 747     }
 748 }