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