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