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             if( !og.equals( ogPrev ) ) {
 281                 mapDescriptorToCompleteOwnershipGraph.put( d, og );
 282
 283                 og.writeGraph( d, true, false );
 284
 285                 // only methods have dependents, tasks cannot
 286                 // be invoked by any user program calls
 287                 if( d instanceof MethodDescriptor ) {
 288                     MethodDescriptor md = (MethodDescriptor) d;
 289                     Set dependents = callGraph.getCallerSet( md );
 290                     if( dependents != null ) {
 291                         descriptorsToVisit.addAll( dependents );
 292                     }
 293                 }
 294             }
 295         }
 296
 297     }
 298
 299
 300     // keep passing the Descriptor of the method along for debugging
 301     // and dot file writing
 302     private OwnershipGraph
 303         analyzeFlatMethod( Descriptor mDesc,
 304                            FlatMethod flatm ) throws java.io.IOException {
 305
 306         // initialize flat nodes to visit as the flat method
 307         // because all other nodes in this flat method are
 308         // decendents of the flat method itself
 309         flatNodesToVisit = new HashSet<FlatNode>();
 310         flatNodesToVisit.add( flatm );
 311
 312         // initilize the mapping of flat nodes in this flat method to
 313         // ownership graph results to an empty mapping
 314         mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 315
 316         // initialize the set of return nodes that will be combined as
 317         // the final ownership graph result to return as an empty set
 318         returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 319
 320
 321         // DEBUG
 322         //int x = 0;
 323
 324
 325         while( !flatNodesToVisit.isEmpty() ) {
 326             FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 327             flatNodesToVisit.remove( fn );
 328
 329             // perform this node's contributions to the ownership
 330             // graph on a new copy, then compare it to the old graph
 331             // at this node to see if anything was updated.
 332             OwnershipGraph og = new OwnershipGraph( allocationDepth );
 333
 334             // start by merging all node's parents' graphs
 335             for( int i = 0; i < fn.numPrev(); ++i ) {
 336                 FlatNode       pn       = fn.getPrev( i );
 337                 OwnershipGraph ogParent = getGraphFromFlatNode( pn );
 338                 og.merge( ogParent );
 339             }
 340
 341             // apply the analysis of the flat node to the
 342             // ownership graph made from the merge of the
 343             // parent graphs
 344             analyzeFlatNode( mDesc,
 345                              fn,
 346                              returnNodesToCombineForCompleteOwnershipGraph,
 347                              og );
 348
 349             // if the results of the new graph are different from
 350             // the current graph at this node, replace the graph
 351             // with the update and enqueue the children for
 352             // processing
 353             OwnershipGraph ogPrev = getGraphFromFlatNode( fn );
 354
 355             if( !og.equals( ogPrev ) ) {
 356                 setGraphForFlatNode( fn, og );
 357
 358                 // DEBUG
 359                 /*
 360                 ++x;
 361
 362                 if( x > 5000 ) {
 363                 String s = String.format( "%04d", x );
 364                 og.writeGraph( "debug"+s, false, false );
 365                 }
 366
 367                 if( x == 5020 ) {
 368                     System.exit( -1 );
 369                 }
 370                 */
 371
 372                 for( int i = 0; i < fn.numNext(); i++ ) {
 373                     FlatNode nn = fn.getNext( i );
 374                     flatNodesToVisit.add( nn );
 375                 }
 376             }
 377         }
 378
 379         // end by merging all return nodes into a complete
 380         // ownership graph that represents all possible heap
 381         // states after the flat method returns
 382         OwnershipGraph completeGraph = new OwnershipGraph( allocationDepth );
 383         Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 384         while( retItr.hasNext() ) {
 385             FlatReturnNode frn = (FlatReturnNode) retItr.next();
 386             OwnershipGraph ogr = getGraphFromFlatNode( frn );
 387             completeGraph.merge( ogr );
 388         }
 389         return completeGraph;
 390     }
 391
 392
 393     private void
 394         analyzeFlatNode( Descriptor              methodDesc,
 395                          FlatNode                fn,
 396                          HashSet<FlatReturnNode> setRetNodes,
 397                          OwnershipGraph          og ) throws java.io.IOException {
 398
 399         TempDescriptor  src;
 400         TempDescriptor  dst;
 401         FieldDescriptor fld;
 402
 403         // use node type to decide what alterations to make
 404         // to the ownership graph
 405         switch( fn.kind() ) {
 406
 407         case FKind.FlatMethod:
 408             FlatMethod fm = (FlatMethod) fn;
 409
 410             // there should only be one FlatMethod node as the
 411             // parent of all other FlatNode objects, so take
 412             // the opportunity to construct the initial graph by
 413             // adding parameters labels to new heap regions
 414             for( int i = 0; i < fm.numParameters(); ++i ) {
 415                 TempDescriptor tdParam = fm.getParameter( i );
 416                 og.assignTempToParameterAllocation( methodDesc instanceof TaskDescriptor,
 417                                                     tdParam,
 418                                                     new Integer( i ) );
 419             }
 420
 421             break;
 422
 423         case FKind.FlatOpNode:
 424             FlatOpNode fon = (FlatOpNode) fn;
 425             if( fon.getOp().getOp() == Operation.ASSIGN ) {
 426                 src = fon.getLeft();
 427                 dst = fon.getDest();
 428                 og.assignTempToTemp( src, dst );
 429             }
 430             break;
 431
 432         case FKind.FlatFieldNode:
 433             FlatFieldNode ffn = (FlatFieldNode) fn;
 434             src = ffn.getSrc();
 435             dst = ffn.getDst();
 436             fld = ffn.getField();
 437             if( !fld.getType().isPrimitive() ) {
 438                 og.assignTempToField( src, dst, fld );
 439             }
 440             break;
 441
 442         case FKind.FlatSetFieldNode:
 443             FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 444             src = fsfn.getSrc();
 445             dst = fsfn.getDst();
 446             fld = fsfn.getField();
 447             og.assignFieldToTemp( src, dst, fld );
 448             break;
 449
 450         case FKind.FlatNew:
 451             FlatNew fnn = (FlatNew) fn;
 452             dst = fnn.getDst();
 453             AllocationSite as = getAllocationSiteFromFlatNewPRIVATE( fnn );
 454
 455             og.assignTempToNewAllocation( dst, as );
 456             break;
 457
 458         case FKind.FlatCall:
 459             FlatCall                fc           = (FlatCall) fn;
 460             MethodDescriptor        md           = fc.getMethod();
 461             FlatMethod              flatm        = state.getMethodFlat( md );
 462             //HashSet<AllocationSite> allocSiteSet = getAllocationSiteSet( md );
 463             OwnershipGraph ogAllPossibleCallees  = new OwnershipGraph( allocationDepth );
 464
 465             if( md.isStatic() ) {
 466                 // a static method is simply always the same, makes life easy
 467                 OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get( md );
 468                 ogAllPossibleCallees.merge( onlyPossibleCallee );
 469
 470                 /*
 471                 if( onlyPossibleCallee != null ) {
 472                     onlyPossibleCallee.writeGraph( "only", false, false );
 473                     System.out.println( "There was only one possible callee, "+md );
 474                 }
 475                 */
 476
 477             } else {
 478                 // if the method descriptor is virtual, then there could be a
 479                 // set of possible methods that will actually be invoked, so
 480                 // find all of them and merge all of their graphs together
 481                 TypeDescriptor typeDesc        = fc.getThis().getType();
 482                 Set            possibleCallees = callGraph.getMethods( md, typeDesc );
 483
 484                 //int j = 0;
 485
 486                 Iterator i = possibleCallees.iterator();
 487                 while( i.hasNext() ) {
 488                     MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 489                     //allocSiteSet.addAll( getAllocationSiteSet( possibleMd ) );
 490                     OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get( possibleMd );
 491
 492                     /*
 493                     if( ogPotentialCallee != null ) {
 494                         ogPotentialCallee.writeGraph( "potential"+j, false, false );
 495                         ++j;
 496                     }
 497                     */
 498
 499                     ogAllPossibleCallees.merge( ogPotentialCallee );
 500                 }
 501
 502                 //System.out.println( "There were "+j+" potential callees merged together." );
 503             }
 504
 505             //System.out.println( "AllocationSiteSet has "+allocSiteSet.size()+" items." );
 506
 507             // now we should have the following information to resolve this method call:
 508             //
 509             // 1. A FlatCall fc to query for the caller's context (argument labels, etc)
 510             //
 511             // 2. Whether the method is static; if not we need to deal with the "this" pointer
 512             //
 513             // *******************************************************************************************
 514             // 3. The original FlatMethod flatm to query for callee's context (paramter labels)
 515             //   NOTE!  I assume FlatMethod before virtual dispatch accurately describes all possible methods!
 516             // *******************************************************************************************
 517             //
 518             // 4. The OwnershipGraph ogAllPossibleCallees is a merge of every ownership graph of all the possible
 519             // methods to capture any possible references made.
 520             //
 521             // 5. The Set of AllocationSite objects, allocSiteSet that is the set of allocation sites from
 522             // every possible method we might have chosen
 523             //
 524             og.resolveMethodCall( fc, md.isStatic(), flatm, ogAllPossibleCallees );
 525             break;
 526
 527         case FKind.FlatReturnNode:
 528             FlatReturnNode frn = (FlatReturnNode) fn;
 529             setRetNodes.add( frn );
 530             break;
 531         }
 532     }
 533
 534
 535     static public Integer generateUniqueHeapRegionNodeID() {
 536         ++uniqueIDcount;
 537         return new Integer( uniqueIDcount );
 538     }
 539
 540
 541     private OwnershipGraph getGraphFromFlatNode( FlatNode fn ) {
 542         if( !mapFlatNodeToOwnershipGraph.containsKey( fn ) ) {
 543             mapFlatNodeToOwnershipGraph.put( fn, new OwnershipGraph( allocationDepth ) );
 544         }
 545
 546         return mapFlatNodeToOwnershipGraph.get( fn );
 547     }
 548
 549     private void setGraphForFlatNode( FlatNode fn, OwnershipGraph og ) {
 550         mapFlatNodeToOwnershipGraph.put( fn, og );
 551     }
 552
 553
 554
 555
 556
 557
 558     // return just the allocation site associated with one FlatNew node
 559     private AllocationSite getAllocationSiteFromFlatNewPRIVATE( FlatNew fn ) {
 560
 561         if( !mapFlatNewToAllocationSite.containsKey( fn ) ) {
 562             AllocationSite as = new AllocationSite( allocationDepth, fn.getType() );
 563
 564             // the newest nodes are single objects
 565             for( int i = 0; i < allocationDepth; ++i ) {
 566                 Integer id = generateUniqueHeapRegionNodeID();
 567                 as.setIthOldest( i, id );
 568             }
 569
 570             // the oldest node is a summary node
 571             Integer idSummary = generateUniqueHeapRegionNodeID();
 572             as.setSummary( idSummary );
 573
 574             mapFlatNewToAllocationSite.put( fn, as );
 575         }
 576
 577         return mapFlatNewToAllocationSite.get( fn );
 578     }
 579
 580
 581     // return all allocation sites in the method (there is one allocation
 582     // site per FlatNew node in a method)
 583     private HashSet<AllocationSite> getAllocationSiteSet( Descriptor d ) {
 584         if( !mapDescriptorToAllocationSiteSet.containsKey( d ) ) {
 585             buildAllocationSiteSet( d );
 586         }
 587
 588         return mapDescriptorToAllocationSiteSet.get( d );
 589
 590     }
 591
 592     private void buildAllocationSiteSet( Descriptor d ) {
 593         HashSet<AllocationSite> s = new HashSet<AllocationSite>();
 594
 595         FlatMethod fm;
 596         if( d instanceof MethodDescriptor ) {
 597             fm = state.getMethodFlat( (MethodDescriptor) d );
 598         } else {
 599             assert d instanceof TaskDescriptor;
 600             fm = state.getMethodFlat( (TaskDescriptor) d );
 601         }
 602
 603         // visit every node in this FlatMethod's IR graph
 604         // and make a set of the allocation sites from the
 605         // FlatNew node's visited
 606         HashSet<FlatNode> visited = new HashSet<FlatNode>();
 607         HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
 608         toVisit.add( fm );
 609
 610         while( !toVisit.isEmpty() ) {
 611             FlatNode n = toVisit.iterator().next();
 612
 613             if( n instanceof FlatNew ) {
 614                 s.add( getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n ) );
 615             }
 616
 617             toVisit.remove( n );
 618             visited.add( n );
 619
 620             for( int i = 0; i < n.numNext(); ++i ) {
 621                 FlatNode child = n.getNext( i );
 622                 if( !visited.contains( child ) ) {
 623                     toVisit.add( child );
 624                 }
 625             }
 626         }
 627
 628         mapDescriptorToAllocationSiteSet.put( d, s );
 629     }
 630
 631
 632     private HashSet<AllocationSite>
 633         getFlaggedAllocationSitesReachableFromTaskPRIVATE( TaskDescriptor td ) {
 634
 635         HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
 636         HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
 637         HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
 638
 639         toVisit.add( td );
 640
 641         // traverse this task and all methods reachable from this task
 642         while( !toVisit.isEmpty() ) {
 643             Descriptor d = toVisit.iterator().next();
 644             toVisit.remove( d );
 645             visited.add( d );
 646
 647             HashSet<AllocationSite> asSet = getAllocationSiteSet( d );
 648             Iterator asItr = asSet.iterator();
 649             while( asItr.hasNext() ) {
 650                 AllocationSite as = (AllocationSite) asItr.next();
 651                 if( as.getType().getClassDesc().hasFlags() ) {
 652                     asSetTotal.add( as );
 653                 }
 654             }
 655
 656             // enqueue callees of this method to be searched for
 657             // allocation sites also
 658             Set callees = callGraph.getCalleeSet( d );
 659             if( callees != null ) {
 660                 Iterator methItr = callees.iterator();
 661                 while( methItr.hasNext() ) {
 662                     MethodDescriptor md = (MethodDescriptor) methItr.next();
 663
 664                     if( !visited.contains( md ) ) {
 665                         toVisit.add( md );
 666                     }
 667                 }
 668             }
 669         }
 670
 671
 672         return asSetTotal;
 673     }
 674
 675
 676
 677     private HashSet<Integer> getHeapRegionIDset( OwnershipGraph og,
 678                                                  int paramIndex ) {
 679
 680         assert og.paramIndex2id.containsKey( paramIndex );
 681         Integer idParam = og.paramIndex2id.get( paramIndex );
 682
 683         HashSet<Integer> idSet = new HashSet<Integer>();
 684         idSet.add( idParam );
 685
 686         return idSet;
 687     }
 688
 689
 690     private HashSet<Integer> getHeapRegionIDset( AllocationSite alloc ) {
 691
 692         HashSet<Integer> idSet = new HashSet<Integer>();
 693
 694         for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
 695             Integer id = alloc.getIthOldest( i );
 696             idSet.add( id );
 697         }
 698
 699         Integer idSummary = alloc.getSummary();
 700         idSet.add( idSummary );
 701
 702         return idSet;
 703     }
 704
 705     private HashSet<Integer> getHeapRegionIDset( HashSet<AllocationSite> allocSet ) {
 706
 707         HashSet<Integer> idSet = new HashSet<Integer>();
 708
 709         Iterator allocItr = allocSet.iterator();
 710         while( allocItr.hasNext() ) {
 711             AllocationSite alloc = (AllocationSite) allocItr.next();
 712
 713             for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
 714                 Integer id = alloc.getIthOldest( i );
 715                 idSet.add( id );
 716             }
 717
 718             Integer idSummary = alloc.getSummary();
 719             idSet.add( idSummary );
 720         }
 721
 722         return idSet;
 723     }
 724
 725     private boolean createsPotentialAliases( OwnershipGraph   og,
 726                                              HashSet<Integer> idSetA,
 727                                              HashSet<Integer> idSetB ) {
 728         boolean potentialAlias = false;
 729
 730         // first expand set B into the set of all heap region node ID's
 731         // reachable from the nodes in set B
 732         HashSet<Integer> idSetReachableFromB = og.getReachableSet( idSetB );
 733
 734         // then see if anything in A can reach a node in the set reachable
 735         // from B.  If so, there is a potential alias.
 736         Iterator i = idSetA.iterator();
 737         while( i.hasNext() ) {
 738             Integer id = (Integer) i.next();
 739             if( og.canIdReachSet( id, idSetB ) ) {
 740                 return true;
 741             }
 742         }
 743
 744         return false;
 745     }
 746 }