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