Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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