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
  31   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  32                                          int paramIndex1,
  33                                          int paramIndex2) {
  34
  35     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  36     assert(og != null);
  37     return og.hasPotentialAlias(paramIndex1, paramIndex2);
  38   }
  39
  40   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  41                                          int paramIndex,
  42                                          AllocationSite alloc) {
  43
  44     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  45     assert(og != null);
  46     return og.hasPotentialAlias(paramIndex, alloc);
  47   }
  48
  49   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  50                                          AllocationSite alloc,
  51                                          int paramIndex) {
  52
  53     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  54     assert(og != null);
  55     return og.hasPotentialAlias(paramIndex, alloc);
  56   }
  57
  58   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  59                                          AllocationSite alloc1,
  60                                          AllocationSite alloc2) {
  61
  62     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  63     assert(og != null);
  64     return og.hasPotentialAlias(alloc1, alloc2);
  65   }
  66
  67
  68   protected OwnershipGraph getGraphOfAllContextsFromDescriptor(Descriptor d) {
  69     assert d != null;
  70
  71     OwnershipGraph og = new OwnershipGraph( allocationDepth, typeUtil );
  72
  73     assert mapDescriptorToAllMethodContexts.containsKey( d );
  74     HashSet<MethodContext> contexts = mapDescriptorToAllMethodContexts.get( d );
  75     Iterator<MethodContext> mcItr = contexts.iterator();
  76     while( mcItr.hasNext() ) {
  77       MethodContext mc = mcItr.next();
  78
  79       OwnershipGraph ogContext = mapMethodContextToCompleteOwnershipGraph.get(mc);
  80       assert ogContext != null;
  81
  82       og.merge( ogContext );
  83     }
  84
  85     return og;
  86   }
  87
  88
  89   // use the methods given above to check every possible alias
  90   // between task parameters and flagged allocation sites reachable
  91   // from the task
  92   public void writeAllAliases(String outputFile) throws java.io.IOException {
  93
  94     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
  95
  96     bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth);
  97
  98     // look through every task for potential aliases
  99     Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 100     while( taskItr.hasNext() ) {
 101       TaskDescriptor td = (TaskDescriptor) taskItr.next();
 102
 103       bw.write("\n---------"+td+"--------\n");
 104
 105       HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
 106
 107       // for each task parameter, check for aliases with
 108       // other task parameters and every allocation site
 109       // reachable from this task
 110       boolean foundSomeAlias = false;
 111
 112       FlatMethod fm = state.getMethodFlat(td);
 113       for( int i = 0; i < fm.numParameters(); ++i ) {
 114
 115         // for the ith parameter check for aliases to all
 116         // higher numbered parameters
 117         for( int j = i + 1; j < fm.numParameters(); ++j ) {
 118           if( createsPotentialAliases(td, i, j) ) {
 119             foundSomeAlias = true;
 120             bw.write("Potential alias between parameters "+i+" and "+j+".\n");
 121           }
 122         }
 123
 124         // for the ith parameter, check for aliases against
 125         // the set of allocation sites reachable from this
 126         // task context
 127         Iterator allocItr = allocSites.iterator();
 128         while( allocItr.hasNext() ) {
 129           AllocationSite as = (AllocationSite) allocItr.next();
 130           if( createsPotentialAliases(td, i, as) ) {
 131             foundSomeAlias = true;
 132             bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n");
 133           }
 134         }
 135       }
 136
 137       // for each allocation site check for aliases with
 138       // other allocation sites in the context of execution
 139       // of this task
 140       HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
 141       Iterator allocItr1 = allocSites.iterator();
 142       while( allocItr1.hasNext() ) {
 143         AllocationSite as1 = (AllocationSite) allocItr1.next();
 144
 145         Iterator allocItr2 = allocSites.iterator();
 146         while( allocItr2.hasNext() ) {
 147           AllocationSite as2 = (AllocationSite) allocItr2.next();
 148
 149           if( !outerChecked.contains(as2) &&
 150               createsPotentialAliases(td, as1, as2) ) {
 151             foundSomeAlias = true;
 152             bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n");
 153           }
 154         }
 155
 156         outerChecked.add(as1);
 157       }
 158
 159       if( !foundSomeAlias ) {
 160         bw.write("No aliases between flagged objects in Task "+td+".\n");
 161       }
 162     }
 163
 164     bw.close();
 165   }
 166
 167
 168   // this version of writeAllAliases is for Java programs that have no tasks
 169   public void writeAllAliasesJava(String outputFile) throws java.io.IOException {
 170     assert !state.TASK;
 171
 172     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
 173
 174     bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n");
 175     boolean foundSomeAlias = false;
 176
 177     Descriptor d = typeUtil.getMain();
 178     HashSet<AllocationSite> allocSites = getFlaggedAllocationSites(d);
 179
 180     // for each allocation site check for aliases with
 181     // other allocation sites in the context of execution
 182     // of this task
 183     HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
 184     Iterator allocItr1 = allocSites.iterator();
 185     while( allocItr1.hasNext() ) {
 186       AllocationSite as1 = (AllocationSite) allocItr1.next();
 187
 188       Iterator allocItr2 = allocSites.iterator();
 189       while( allocItr2.hasNext() ) {
 190         AllocationSite as2 = (AllocationSite) allocItr2.next();
 191
 192         if( !outerChecked.contains(as2) &&
 193             createsPotentialAliases(d, as1, as2) ) {
 194           foundSomeAlias = true;
 195           bw.write("Potential alias between "+as1.getDisjointId()+" and "+as2.getDisjointId()+".\n");
 196         }
 197       }
 198
 199       outerChecked.add(as1);
 200     }
 201
 202     if( !foundSomeAlias ) {
 203       bw.write("No aliases between flagged objects found.\n");
 204     }
 205
 206     bw.close();
 207   }
 208   ///////////////////////////////////////////
 209   //
 210   // end public interface
 211   //
 212   ///////////////////////////////////////////
 213
 214
 215
 216
 217
 218
 219
 220
 221   // data from the compiler
 222   private State state;
 223   private TypeUtil typeUtil;
 224   private CallGraph callGraph;
 225   private int allocationDepth;
 226
 227   // used to identify HeapRegionNode objects
 228   // A unique ID equates an object in one
 229   // ownership graph with an object in another
 230   // graph that logically represents the same
 231   // heap region
 232   // start at 10 and increment to leave some
 233   // reserved IDs for special purposes
 234   static private int uniqueIDcount = 10;
 235
 236
 237   // Use these data structures to track progress of
 238   // processing all methods in the program, and by methods
 239   // TaskDescriptor and MethodDescriptor are combined
 240   // together, with a common parent class Descriptor
 241   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToInitialParamAllocGraph;
 242   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToCompleteOwnershipGraph;
 243   private Hashtable<FlatNew,       AllocationSite>           mapFlatNewToAllocationSite;
 244   private Hashtable<Descriptor,    HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
 245   private Hashtable<MethodContext, Integer>                  mapMethodContextToNumUpdates;
 246   private Hashtable<Descriptor,    HashSet<MethodContext> >  mapDescriptorToAllMethodContexts;
 247
 248   // Use these data structures to track progress of one pass of
 249   // processing the FlatNodes of a particular method
 250   private HashSet  <FlatNode>                 flatNodesToVisit;
 251   private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
 252   private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
 253
 254   // descriptorsToAnalyze identifies the set of tasks and methods
 255   // that are reachable from the program tasks, this set is initialized
 256   // and then remains static
 257   private HashSet<Descriptor> descriptorsToAnalyze;
 258
 259   // descriptorsToVisit is initialized to descriptorsToAnalyze and is
 260   // reduced by visiting a descriptor during analysis.  When dependents
 261   // must be scheduled, only those contained in descriptorsToAnalyze
 262   // should be re-added to this set
 263   private HashSet   <MethodContext> methodContextsToVisit;
 264
 265   // used in conjunction with the methodContextsToVisit set, fill with
 266   // a topological sort of methodContextsToVisit and then empty that set
 267   // algorithm should analyze something in the linked list until it is
 268   // empty, and then work on the set as normal.  The sorted linked list
 269   // is just another, specially sorted bucket that is part of the
 270   // methodContextsToVisit set
 271   private LinkedList<MethodContext> sortedMethodContextsToVisit;
 272
 273
 274   // special field descriptors for array elements
 275   private Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
 276
 277
 278   // a special temp descriptor for setting more than one parameter label
 279   // to the all-aliased-parameters heap region node
 280   protected static TempDescriptor tdAliasedParams = new TempDescriptor("_AllAliasedParams___");
 281
 282
 283   // for controlling DOT file output
 284   private boolean writeDOTs;
 285   private boolean writeAllDOTs;
 286
 287
 288
 289   // this analysis generates an ownership graph for every task
 290   // in the program
 291   public OwnershipAnalysis(State state,
 292                            TypeUtil tu,
 293                            CallGraph callGraph,
 294                            int allocationDepth,
 295                            boolean writeDOTs,
 296                            boolean writeAllDOTs,
 297                            String aliasFile) throws java.io.IOException {
 298
 299     double timeStartAnalysis = (double) System.nanoTime();
 300
 301     this.state           = state;
 302     this.typeUtil        = tu;
 303     this.callGraph       = callGraph;
 304     this.allocationDepth = allocationDepth;
 305     this.writeDOTs       = writeDOTs;
 306     this.writeAllDOTs    = writeAllDOTs;
 307
 308     descriptorsToAnalyze = new HashSet<Descriptor>();
 309
 310     mapMethodContextToInitialParamAllocGraph =
 311       new Hashtable<MethodContext, OwnershipGraph>();
 312
 313     mapMethodContextToCompleteOwnershipGraph =
 314       new Hashtable<MethodContext, OwnershipGraph>();
 315
 316     mapFlatNewToAllocationSite =
 317       new Hashtable<FlatNew, AllocationSite>();
 318
 319     mapDescriptorToAllocationSiteSet =
 320       new Hashtable<Descriptor, HashSet<AllocationSite> >();
 321
 322     mapDescriptorToAllMethodContexts =
 323       new Hashtable<Descriptor, HashSet<MethodContext> >();
 324
 325     mapTypeToArrayField =
 326       new Hashtable<TypeDescriptor, FieldDescriptor>();
 327
 328     if( writeAllDOTs ) {
 329       mapMethodContextToNumUpdates = new Hashtable<MethodContext, Integer>();
 330     }
 331
 332
 333     if( state.TASK ) {
 334       // initialize methods to visit as the set of all tasks in the
 335       // program and then any method that could be called starting
 336       // from those tasks
 337       Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 338       while( taskItr.hasNext() ) {
 339         Descriptor d = (Descriptor) taskItr.next();
 340         scheduleAllCallees(d);
 341       }
 342
 343     } else {
 344       // we are not in task mode, just normal Java, so start with
 345       // the main method
 346       Descriptor d = typeUtil.getMain();
 347       scheduleAllCallees(d);
 348     }
 349
 350
 351     // before beginning analysis, initialize every scheduled method
 352     // with an ownership graph that has populated parameter index tables
 353     // by analyzing the first node which is always a FlatMethod node
 354     Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
 355     while( dItr.hasNext() ) {
 356       Descriptor d  = dItr.next();
 357       OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
 358
 359       FlatMethod fm;
 360       if( d instanceof MethodDescriptor ) {
 361         fm = state.getMethodFlat( (MethodDescriptor) d);
 362       } else {
 363         assert d instanceof TaskDescriptor;
 364         fm = state.getMethodFlat( (TaskDescriptor) d);
 365       }
 366
 367       MethodContext mc = new MethodContext( d );
 368       assert !mapDescriptorToAllMethodContexts.containsKey( d );
 369       HashSet<MethodContext> s = new HashSet<MethodContext>();
 370       s.add( mc );
 371       mapDescriptorToAllMethodContexts.put( d, s );
 372
 373       //System.out.println("Previsiting " + mc);
 374
 375       og = analyzeFlatNode(mc, fm, null, og);
 376       setGraphForMethodContext(mc, og);
 377     }
 378
 379     // as mentioned above, analyze methods one-by-one, possibly revisiting
 380     // a method if the methods that it calls are updated
 381     analyzeMethods();
 382
 383     double timeEndAnalysis = (double) System.nanoTime();
 384     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 385     String treport = String.format( "The analysis took %.3f sec.", dt );
 386     System.out.println( treport );
 387
 388     if( writeDOTs && !writeAllDOTs ) {
 389       writeFinalContextGraphs();
 390     }
 391
 392     if( aliasFile != null ) {
 393       if( state.TASK ) {
 394         writeAllAliases(aliasFile);
 395       } else {
 396         writeAllAliasesJava(aliasFile);
 397       }
 398     }
 399   }
 400
 401   // called from the constructor to help initialize the set
 402   // of methods that needs to be analyzed by ownership analysis
 403   private void scheduleAllCallees(Descriptor d) {
 404     if( descriptorsToAnalyze.contains(d) ) {
 405       return;
 406     }
 407     descriptorsToAnalyze.add(d);
 408
 409     // start with all method calls to further schedule
 410     Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
 411
 412     if( d instanceof MethodDescriptor ) {
 413       // see if this method has virtual dispatch
 414       Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
 415       moreMethodsToCheck.addAll(virtualMethods);
 416     }
 417
 418     // keep following any further methods identified in
 419     // the call chain
 420     Iterator methItr = moreMethodsToCheck.iterator();
 421     while( methItr.hasNext() ) {
 422       Descriptor m = (Descriptor) methItr.next();
 423       scheduleAllCallees(m);
 424     }
 425   }
 426
 427
 428   // manage the set of tasks and methods to be analyzed
 429   // and be sure to reschedule tasks/methods when the methods
 430   // they call are updated
 431   private void analyzeMethods() throws java.io.IOException {
 432
 433     methodContextsToVisit       = new HashSet   <MethodContext>();
 434     sortedMethodContextsToVisit = new LinkedList<MethodContext>();
 435
 436     Iterator<Descriptor> itrd2a = descriptorsToAnalyze.iterator();
 437     while( itrd2a.hasNext() ) {
 438       HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() );
 439       assert mcs != null;
 440
 441       Iterator<MethodContext> itrmc = mcs.iterator();
 442       while( itrmc.hasNext() ) {
 443         methodContextsToVisit.add( itrmc.next() );
 444       }
 445     }
 446
 447     sortedMethodContextsToVisit = topologicalSort( methodContextsToVisit );
 448     methodContextsToVisit.clear();
 449
 450     while( !methodContextsToVisit.isEmpty()       ||
 451            !sortedMethodContextsToVisit.isEmpty()    ) {
 452
 453       MethodContext mc = null;
 454
 455       if( !sortedMethodContextsToVisit.isEmpty() ) {
 456         mc = sortedMethodContextsToVisit.removeFirst();
 457       } else {
 458         mc = methodContextsToVisit.iterator().next();
 459         methodContextsToVisit.remove(mc);
 460       }
 461
 462
 463       // because the task or method descriptor just extracted
 464       // was in the "to visit" set it either hasn't been analyzed
 465       // yet, or some method that it depends on has been
 466       // updated.  Recompute a complete ownership graph for
 467       // this task/method and compare it to any previous result.
 468       // If there is a change detected, add any methods/tasks
 469       // that depend on this one to the "to visit" set.
 470
 471       System.out.println("Analyzing " + mc);
 472
 473       Descriptor d = mc.getDescriptor();
 474       FlatMethod fm;
 475       if( d instanceof MethodDescriptor ) {
 476         fm = state.getMethodFlat( (MethodDescriptor) d);
 477       } else {
 478         assert d instanceof TaskDescriptor;
 479         fm = state.getMethodFlat( (TaskDescriptor) d);
 480       }
 481
 482       OwnershipGraph og = analyzeFlatMethod(mc, fm);
 483       OwnershipGraph ogPrev = mapMethodContextToCompleteOwnershipGraph.get(mc);
 484       if( !og.equals(ogPrev) ) {
 485         setGraphForMethodContext(mc, og);
 486
 487         // only methods have dependents, tasks cannot
 488         // be invoked by any user program calls
 489         if( d instanceof MethodDescriptor ) {
 490           MethodDescriptor md = (MethodDescriptor) d;
 491           Set dependents = callGraph.getCallerSet(md);
 492           if( dependents != null ) {
 493             Iterator depItr = dependents.iterator();
 494             while( depItr.hasNext() ) {
 495               Descriptor dependent = (Descriptor) depItr.next();
 496               if( descriptorsToAnalyze.contains(dependent) ) {
 497
 498                 HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( dependent );
 499                 assert mcs != null;
 500
 501                 Iterator<MethodContext> itrmc = mcs.iterator();
 502                 while( itrmc.hasNext() ) {
 503                   methodContextsToVisit.add( itrmc.next() );
 504                 }
 505               }
 506             }
 507           }
 508         }
 509       }
 510     }
 511
 512   }
 513
 514
 515   // keep passing the Descriptor of the method along for debugging
 516   // and dot file writing
 517   private OwnershipGraph
 518   analyzeFlatMethod(MethodContext mc,
 519                     FlatMethod flatm) throws java.io.IOException {
 520
 521     // initialize flat nodes to visit as the flat method
 522     // because it is the entry point
 523
 524     flatNodesToVisit = new HashSet<FlatNode>();
 525     flatNodesToVisit.add(flatm);
 526
 527     // initilize the mapping of flat nodes in this flat method to
 528     // ownership graph results to an empty mapping
 529     mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 530
 531     // initialize the set of return nodes that will be combined as
 532     // the final ownership graph result to return as an empty set
 533     returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 534
 535
 536     while( !flatNodesToVisit.isEmpty() ) {
 537       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 538       flatNodesToVisit.remove(fn);
 539
 540       //System.out.println( "  "+fn );
 541
 542       // perform this node's contributions to the ownership
 543       // graph on a new copy, then compare it to the old graph
 544       // at this node to see if anything was updated.
 545       OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
 546
 547       // start by merging all node's parents' graphs
 548       for( int i = 0; i < fn.numPrev(); ++i ) {
 549         FlatNode pn = fn.getPrev(i);
 550         if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
 551           OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
 552           og.merge(ogParent);
 553         }
 554       }
 555
 556       // apply the analysis of the flat node to the
 557       // ownership graph made from the merge of the
 558       // parent graphs
 559       og = analyzeFlatNode(mc,
 560                            fn,
 561                            returnNodesToCombineForCompleteOwnershipGraph,
 562                            og);
 563
 564       /*
 565       if( mc.getDescriptor().getSymbol().equals( "addFlightPlan" ) ) {
 566         debugSnapshot(og,fn);
 567       }
 568       */
 569
 570
 571       // if the results of the new graph are different from
 572       // the current graph at this node, replace the graph
 573       // with the update and enqueue the children for
 574       // processing
 575       OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
 576       if( !og.equals(ogPrev) ) {
 577         mapFlatNodeToOwnershipGraph.put(fn, og);
 578
 579         for( int i = 0; i < fn.numNext(); i++ ) {
 580           FlatNode nn = fn.getNext(i);
 581           flatNodesToVisit.add(nn);
 582         }
 583       }
 584     }
 585
 586     // end by merging all return nodes into a complete
 587     // ownership graph that represents all possible heap
 588     // states after the flat method returns
 589     OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth, typeUtil);
 590     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 591     while( retItr.hasNext() ) {
 592       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 593       assert mapFlatNodeToOwnershipGraph.containsKey(frn);
 594       OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
 595       completeGraph.merge(ogr);
 596     }
 597
 598     return completeGraph;
 599   }
 600
 601
 602   private OwnershipGraph
 603   analyzeFlatNode(MethodContext mc,
 604                   FlatNode fn,
 605                   HashSet<FlatReturnNode> setRetNodes,
 606                   OwnershipGraph og) throws java.io.IOException {
 607
 608     TempDescriptor lhs;
 609     TempDescriptor rhs;
 610     FieldDescriptor fld;
 611
 612     // use node type to decide what alterations to make
 613     // to the ownership graph
 614     switch( fn.kind() ) {
 615
 616     case FKind.FlatMethod:
 617       FlatMethod fm = (FlatMethod) fn;
 618
 619       // there should only be one FlatMethod node as the
 620       // parent of all other FlatNode objects, so take
 621       // the opportunity to construct the initial graph by
 622       // adding parameters labels to new heap regions
 623       // AND this should be done once globally so that the
 624       // parameter IDs are consistent between analysis
 625       // iterations, so if this step has been done already
 626       // just merge in the cached version
 627       OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
 628       if( ogInitParamAlloc == null ) {
 629
 630         // if the method context has aliased parameters, make sure
 631         // there is a blob region for all those param labels to
 632         // reference
 633         Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
 634         if( !aliasedParamIndices.isEmpty() ) {
 635           og.makeAliasedParamHeapRegionNode( tdAliasedParams );
 636         }
 637
 638         // set up each parameter
 639         for( int i = 0; i < fm.numParameters(); ++i ) {
 640           TempDescriptor tdParam = fm.getParameter( i );
 641           Integer        paramIndex = new Integer( i );
 642
 643           if( aliasedParamIndices.contains( paramIndex ) ) {
 644             // just point this one to the alias blob
 645             og.assignTempEqualToAliasedParam( tdParam,
 646                                               tdAliasedParams,
 647                                               paramIndex );
 648           } else {
 649             // this parameter is not aliased to others, give it
 650             // a fresh parameter heap region
 651
 652             og.assignTempEqualToParamAlloc(tdParam,
 653                                            mc.getDescriptor() instanceof TaskDescriptor,
 654                                            paramIndex );
 655           }
 656         }
 657
 658         // cache the graph
 659         OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil);
 660         ogResult.merge(og);
 661         mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
 662
 663       } else {
 664         // or just leverage the cached copy
 665         og.merge(ogInitParamAlloc);
 666       }
 667       break;
 668
 669     case FKind.FlatOpNode:
 670       FlatOpNode fon = (FlatOpNode) fn;
 671       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 672         lhs = fon.getDest();
 673         rhs = fon.getLeft();
 674         og.assignTempXEqualToTempY(lhs, rhs);
 675       }
 676       break;
 677
 678     case FKind.FlatFieldNode:
 679       FlatFieldNode ffn = (FlatFieldNode) fn;
 680       lhs = ffn.getDst();
 681       rhs = ffn.getSrc();
 682       fld = ffn.getField();
 683       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 684         og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
 685       }
 686       break;
 687
 688     case FKind.FlatSetFieldNode:
 689       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 690       lhs = fsfn.getDst();
 691       fld = fsfn.getField();
 692       rhs = fsfn.getSrc();
 693       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 694         og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
 695       }
 696       break;
 697
 698     case FKind.FlatElementNode:
 699       FlatElementNode fen = (FlatElementNode) fn;
 700       lhs = fen.getDst();
 701       rhs = fen.getSrc();
 702       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 703
 704         assert rhs.getType() != null;
 705         assert rhs.getType().isArray();
 706
 707         TypeDescriptor  tdElement = rhs.getType().dereference();
 708         FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
 709         if( fdElement == null ) {
 710           fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
 711                                           tdElement,
 712                                           "_element",
 713                                           null,
 714                                           false);
 715           mapTypeToArrayField.put( tdElement, fdElement );
 716         }
 717
 718         og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
 719       }
 720       break;
 721
 722     case FKind.FlatSetElementNode:
 723       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 724       lhs = fsen.getDst();
 725       rhs = fsen.getSrc();
 726       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 727
 728         assert lhs.getType() != null;
 729         assert lhs.getType().isArray();
 730
 731         TypeDescriptor  tdElement = lhs.getType().dereference();
 732
 733         System.out.println( "lhs.Type  = "+lhs.getType().toPrettyString() );
 734         System.out.println( "tdElement = "+tdElement.toPrettyString() );
 735
 736         FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
 737         if( fdElement == null ) {
 738           fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
 739                                           tdElement,
 740                                           "_element",
 741                                           null,
 742                                           false);
 743           mapTypeToArrayField.put( tdElement, fdElement );
 744         }
 745
 746         og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
 747       }
 748       break;
 749
 750     case FKind.FlatNew:
 751       FlatNew fnn = (FlatNew) fn;
 752       lhs = fnn.getDst();
 753       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 754         AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
 755         og.assignTempEqualToNewAlloc(lhs, as);
 756       }
 757       break;
 758
 759     case FKind.FlatCall:
 760       FlatCall fc = (FlatCall) fn;
 761       MethodDescriptor md = fc.getMethod();
 762       FlatMethod flatm = state.getMethodFlat(md);
 763       OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth, typeUtil);
 764
 765       if( md.isStatic() ) {
 766         // a static method is simply always the same, makes life easy
 767         ogMergeOfAllPossibleCalleeResults = og;
 768
 769         Set<Integer> aliasedParamIndices =
 770           ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
 771         MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
 772         OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 773
 774         if( onlyPossibleCallee == null ) {
 775           // if this method context has never been analyzed just schedule it for analysis
 776           // and skip over this call site for now
 777           methodContextsToVisit.add( mcNew );
 778
 779         } else {
 780           ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee);
 781         }
 782
 783       } else {
 784         // if the method descriptor is virtual, then there could be a
 785         // set of possible methods that will actually be invoked, so
 786         // find all of them and merge all of their results together
 787         TypeDescriptor typeDesc = fc.getThis().getType();
 788         Set possibleCallees = callGraph.getMethods(md, typeDesc);
 789
 790         Iterator i = possibleCallees.iterator();
 791         while( i.hasNext() ) {
 792           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 793           FlatMethod pflatm = state.getMethodFlat(possibleMd);
 794
 795           // don't alter the working graph (og) until we compute a result for every
 796           // possible callee, merge them all together, then set og to that
 797           OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil);
 798           ogCopy.merge(og);
 799
 800           Set<Integer> aliasedParamIndices =
 801             ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
 802           MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
 803           OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 804
 805           if( ogPotentialCallee == null ) {
 806             // if this method context has never been analyzed just schedule it for analysis
 807             // and skip over this call site for now
 808             methodContextsToVisit.add( mcNew );
 809
 810           } else {
 811             ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee);
 812           }
 813
 814           ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
 815         }
 816       }
 817
 818       og = ogMergeOfAllPossibleCalleeResults;
 819       break;
 820
 821     case FKind.FlatReturnNode:
 822       FlatReturnNode frn = (FlatReturnNode) fn;
 823       rhs = frn.getReturnTemp();
 824       if( rhs != null && !rhs.getType().isImmutable() ) {
 825         og.assignReturnEqualToTemp(rhs);
 826       }
 827       setRetNodes.add(frn);
 828       break;
 829     }
 830
 831     return og;
 832   }
 833
 834
 835   // insert a call to debugSnapshot() somewhere in the analysis to get
 836   // successive captures of the analysis state
 837   int debugCounter        = 0;
 838   int numStartCountReport = 0;
 839   int freqCountReport     = 1;
 840   int iterStartCapture    = 0;
 841   int numIterToCapture    = 500;
 842   void debugSnapshot(OwnershipGraph og, FlatNode fn) {
 843     if( debugCounter > numStartCountReport + numIterToCapture ) {
 844       return;
 845     }
 846
 847     ++debugCounter;
 848     if( debugCounter > numStartCountReport &&
 849         debugCounter % freqCountReport == 0 ) {
 850       System.out.println("    @@@ debug counter = "+debugCounter);
 851     }
 852     if( debugCounter > iterStartCapture ) {
 853       System.out.println("    @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
 854       String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
 855       if( fn != null ) {
 856         graphName = graphName+fn;
 857       }
 858       try {
 859         og.writeGraph(graphName, true, true, false, false, false);
 860       } catch( Exception e ) {
 861         System.out.println("Error writing debug capture.");
 862         System.exit(0);
 863       }
 864     }
 865     /*
 866     if( debugCounter == iterStartCapture + numIterToCapture ) {
 867       System.out.println("Stopping analysis after debug captures.");
 868       System.exit(0);
 869     }
 870     */
 871   }
 872
 873
 874
 875   // this method should generate integers strictly greater than zero!
 876   // special "shadow" regions are made from a heap region by negating
 877   // the ID
 878   static public Integer generateUniqueHeapRegionNodeID() {
 879     ++uniqueIDcount;
 880     return new Integer(uniqueIDcount);
 881   }
 882
 883
 884   private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og) {
 885
 886     mapMethodContextToCompleteOwnershipGraph.put(mc, og);
 887
 888     if( writeDOTs && writeAllDOTs ) {
 889       if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
 890         mapMethodContextToNumUpdates.put(mc, new Integer(0) );
 891       }
 892       Integer n = mapMethodContextToNumUpdates.get(mc);
 893       try {
 894         og.writeGraph(mc, n, true, true, true, false, false);
 895       } catch( IOException e ) {}
 896       mapMethodContextToNumUpdates.put(mc, n + 1);
 897     }
 898   }
 899
 900
 901   private void writeFinalContextGraphs() {
 902     // arguments to writeGraph are:
 903     // boolean writeLabels,
 904     // boolean labelSelect,
 905     // boolean pruneGarbage,
 906     // boolean writeReferencers
 907     // boolean writeParamMappings
 908
 909     Set entrySet = mapMethodContextToCompleteOwnershipGraph.entrySet();
 910     Iterator itr = entrySet.iterator();
 911     while( itr.hasNext() ) {
 912       Map.Entry      me = (Map.Entry)      itr.next();
 913       MethodContext  mc = (MethodContext)  me.getKey();
 914       OwnershipGraph og = (OwnershipGraph) me.getValue();
 915
 916       try {
 917         og.writeGraph(mc, true, true, true, false, false);
 918       } catch( IOException e ) {}
 919     }
 920   }
 921
 922
 923   // return just the allocation site associated with one FlatNew node
 924   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
 925
 926     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
 927       AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
 928
 929       // the newest nodes are single objects
 930       for( int i = 0; i < allocationDepth; ++i ) {
 931         Integer id = generateUniqueHeapRegionNodeID();
 932         as.setIthOldest(i, id);
 933       }
 934
 935       // the oldest node is a summary node
 936       Integer idSummary = generateUniqueHeapRegionNodeID();
 937       as.setSummary(idSummary);
 938
 939       mapFlatNewToAllocationSite.put(fn, as);
 940     }
 941
 942     return mapFlatNewToAllocationSite.get(fn);
 943   }
 944
 945
 946   // return all allocation sites in the method (there is one allocation
 947   // site per FlatNew node in a method)
 948   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
 949     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
 950       buildAllocationSiteSet(d);
 951     }
 952
 953     return mapDescriptorToAllocationSiteSet.get(d);
 954
 955   }
 956
 957   private void buildAllocationSiteSet(Descriptor d) {
 958     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
 959
 960     FlatMethod fm;
 961     if( d instanceof MethodDescriptor ) {
 962       fm = state.getMethodFlat( (MethodDescriptor) d);
 963     } else {
 964       assert d instanceof TaskDescriptor;
 965       fm = state.getMethodFlat( (TaskDescriptor) d);
 966     }
 967
 968     // visit every node in this FlatMethod's IR graph
 969     // and make a set of the allocation sites from the
 970     // FlatNew node's visited
 971     HashSet<FlatNode> visited = new HashSet<FlatNode>();
 972     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
 973     toVisit.add(fm);
 974
 975     while( !toVisit.isEmpty() ) {
 976       FlatNode n = toVisit.iterator().next();
 977
 978       if( n instanceof FlatNew ) {
 979         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
 980       }
 981
 982       toVisit.remove(n);
 983       visited.add(n);
 984
 985       for( int i = 0; i < n.numNext(); ++i ) {
 986         FlatNode child = n.getNext(i);
 987         if( !visited.contains(child) ) {
 988           toVisit.add(child);
 989         }
 990       }
 991     }
 992
 993     mapDescriptorToAllocationSiteSet.put(d, s);
 994   }
 995
 996
 997   private HashSet<AllocationSite> getFlaggedAllocationSites(Descriptor dIn) {
 998
 999     HashSet<AllocationSite> out     = new HashSet<AllocationSite>();
1000     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
1001     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
1002
1003     toVisit.add(dIn);
1004
1005     while( !toVisit.isEmpty() ) {
1006       Descriptor d = toVisit.iterator().next();
1007       toVisit.remove(d);
1008       visited.add(d);
1009
1010       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1011       Iterator asItr = asSet.iterator();
1012       while( asItr.hasNext() ) {
1013         AllocationSite as = (AllocationSite) asItr.next();
1014         if( as.getDisjointId() != null ) {
1015           out.add(as);
1016         }
1017       }
1018
1019       // enqueue callees of this method to be searched for
1020       // allocation sites also
1021       Set callees = callGraph.getCalleeSet(d);
1022       if( callees != null ) {
1023         Iterator methItr = callees.iterator();
1024         while( methItr.hasNext() ) {
1025           MethodDescriptor md = (MethodDescriptor) methItr.next();
1026
1027           if( !visited.contains(md) ) {
1028             toVisit.add(md);
1029           }
1030         }
1031       }
1032     }
1033
1034     return out;
1035   }
1036
1037
1038   private HashSet<AllocationSite>
1039   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1040
1041     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
1042     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1043     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1044
1045     toVisit.add(td);
1046
1047     // traverse this task and all methods reachable from this task
1048     while( !toVisit.isEmpty() ) {
1049       Descriptor d = toVisit.iterator().next();
1050       toVisit.remove(d);
1051       visited.add(d);
1052
1053       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1054       Iterator asItr = asSet.iterator();
1055       while( asItr.hasNext() ) {
1056         AllocationSite as = (AllocationSite) asItr.next();
1057         TypeDescriptor typed = as.getType();
1058         if( typed != null ) {
1059           ClassDescriptor cd = typed.getClassDesc();
1060           if( cd != null && cd.hasFlags() ) {
1061             asSetTotal.add(as);
1062           }
1063         }
1064       }
1065
1066       // enqueue callees of this method to be searched for
1067       // allocation sites also
1068       Set callees = callGraph.getCalleeSet(d);
1069       if( callees != null ) {
1070         Iterator methItr = callees.iterator();
1071         while( methItr.hasNext() ) {
1072           MethodDescriptor md = (MethodDescriptor) methItr.next();
1073
1074           if( !visited.contains(md) ) {
1075             toVisit.add(md);
1076           }
1077         }
1078       }
1079     }
1080
1081
1082     return asSetTotal;
1083   }
1084
1085
1086   private LinkedList<MethodContext> topologicalSort( HashSet<MethodContext> set ) {
1087     HashSet   <MethodContext> discovered = new HashSet   <MethodContext>();
1088     LinkedList<MethodContext> sorted     = new LinkedList<MethodContext>();
1089
1090     Iterator<MethodContext> itr = set.iterator();
1091     while( itr.hasNext() ) {
1092       MethodContext mc = itr.next();
1093
1094       if( !discovered.contains( mc ) ) {
1095         dfsVisit( set, mc, sorted, discovered );
1096       }
1097     }
1098
1099     return sorted;
1100   }
1101
1102   private void dfsVisit( HashSet<MethodContext> set,
1103                          MethodContext mc,
1104                          LinkedList<MethodContext> sorted,
1105                          HashSet   <MethodContext> discovered ) {
1106     discovered.add( mc );
1107
1108     Descriptor d = mc.getDescriptor();
1109     if( d instanceof MethodDescriptor ) {
1110       MethodDescriptor md = (MethodDescriptor) d;
1111       Iterator itr = callGraph.getCallerSet( md ).iterator();
1112       while( itr.hasNext() ) {
1113         Descriptor dCaller = (Descriptor) itr.next();
1114
1115         // only consider the callers in the original set to analyze
1116         Set<MethodContext> callerContexts = mapDescriptorToAllMethodContexts.get( dCaller );
1117         if( callerContexts == null )
1118           continue;
1119
1120         // since the analysis hasn't started, there should be exactly one
1121         // context if there are any at all
1122         assert callerContexts.size() == 1;
1123         MethodContext mcCaller = callerContexts.iterator().next();
1124         assert set.contains( mcCaller );
1125
1126         if( !discovered.contains( mcCaller ) ) {
1127           dfsVisit( set, mcCaller, sorted, discovered );
1128         }
1129       }
1130     }
1131
1132     sorted.addFirst( mc );
1133   }
1134 }