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