Robust/src/Analysis/Disjoint/DisjointAnalysis.java

   1 package Analysis.Disjoint;
   2
   3 import Analysis.CallGraph.*;
   4 import Analysis.Liveness;
   5 import Analysis.ArrayReferencees;
   6 import IR.*;
   7 import IR.Flat.*;
   8 import IR.Tree.Modifiers;
   9 import java.util.*;
  10 import java.io.*;
  11
  12
  13 public class DisjointAnalysis {
  14
  15           ///////////////////////////////////////////
  16           //
  17           //  Public interface to discover possible
  18           //  aliases in the program under analysis
  19           //
  20           ///////////////////////////////////////////
  21
  22           public HashSet<AllocSite>
  23           getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
  24             checkAnalysisComplete();
  25             return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
  26           }
  27
  28           public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) {
  29                     checkAnalysisComplete();
  30                     return getAllocSiteFromFlatNewPRIVATE(fn);
  31            }
  32
  33           public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) {
  34                     checkAnalysisComplete();
  35                     return mapHrnIdToAllocSite.get(id);
  36           }
  37
  38           public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
  39               int paramIndex1,
  40               int paramIndex2) {
  41                   checkAnalysisComplete();
  42                   ReachGraph rg=mapDescriptorToCompleteReachGraph.get(taskOrMethod);
  43                   FlatMethod fm=state.getMethodFlat(taskOrMethod);
  44                   assert(rg != null);
  45                   return rg.mayReachSharedObjects(fm, paramIndex1, paramIndex2);
  46           }
  47
  48         public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
  49                         int paramIndex, AllocSite alloc) {
  50                 checkAnalysisComplete();
  51                 ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
  52             FlatMethod fm=state.getMethodFlat(taskOrMethod);
  53                 assert (rg != null);
  54                 return rg.mayReachSharedObjects(fm, paramIndex, alloc);
  55         }
  56
  57         public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
  58                         AllocSite alloc, int paramIndex) {
  59                 checkAnalysisComplete();
  60                 ReachGraph rg  = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
  61                 FlatMethod fm=state.getMethodFlat(taskOrMethod);
  62                 assert (rg != null);
  63                 return rg.mayReachSharedObjects(fm, paramIndex, alloc);
  64         }
  65
  66         public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
  67                         AllocSite alloc1, AllocSite alloc2) {
  68                 checkAnalysisComplete();
  69                 ReachGraph rg  = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
  70                 assert (rg != null);
  71                 return rg.mayReachSharedObjects(alloc1, alloc2);
  72         }
  73
  74         public String prettyPrintNodeSet(Set<HeapRegionNode> s) {
  75                 checkAnalysisComplete();
  76
  77                 String out = "{\n";
  78
  79                 Iterator<HeapRegionNode> i = s.iterator();
  80                 while (i.hasNext()) {
  81                         HeapRegionNode n = i.next();
  82
  83                         AllocSite as = n.getAllocSite();
  84                         if (as == null) {
  85                                 out += "  " + n.toString() + ",\n";
  86                         } else {
  87                                 out += "  " + n.toString() + ": " + as.toStringVerbose()
  88                                                 + ",\n";
  89                         }
  90                 }
  91
  92                 out += "}\n";
  93                 return out;
  94         }
  95
  96         // use the methods given above to check every possible alias
  97           // between task parameters and flagged allocation sites reachable
  98           // from the task
  99           public void writeAllAliases(String outputFile,
 100                                       String timeReport,
 101                                       String justTime,
 102                                       boolean tabularOutput,
 103                                       int numLines
 104 )
 105                         throws java.io.IOException {
 106                 checkAnalysisComplete();
 107
 108                 BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile));
 109
 110                 if (!tabularOutput) {
 111                         bw.write("Conducting ownership analysis with allocation depth = "
 112                                         + allocationDepth + "\n");
 113                         bw.write(timeReport + "\n");
 114                 }
 115
 116                 int numAlias = 0;
 117
 118                 // look through every task for potential aliases
 119                 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 120                 while (taskItr.hasNext()) {
 121                         TaskDescriptor td = (TaskDescriptor) taskItr.next();
 122
 123                         if (!tabularOutput) {
 124                                 bw.write("\n---------" + td + "--------\n");
 125                         }
 126
 127                         HashSet<AllocSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
 128
 129                         Set<HeapRegionNode> common;
 130
 131                         // for each task parameter, check for aliases with
 132                         // other task parameters and every allocation site
 133                         // reachable from this task
 134                         boolean foundSomeAlias = false;
 135
 136                         FlatMethod fm = state.getMethodFlat(td);
 137                         for (int i = 0; i < fm.numParameters(); ++i) {
 138
 139                                 // for the ith parameter check for aliases to all
 140                                 // higher numbered parameters
 141                                 for (int j = i + 1; j < fm.numParameters(); ++j) {
 142                                         common = createsPotentialAliases(td, i, j);
 143                                         if (!common.isEmpty()) {
 144                                                 foundSomeAlias = true;
 145                                                 if (!tabularOutput) {
 146                                                         bw.write("Potential alias between parameters " + i
 147                                                                         + " and " + j + ".\n");
 148                                                         bw.write(prettyPrintNodeSet(common) + "\n");
 149                                                 } else {
 150                                                         ++numAlias;
 151                                                 }
 152                                         }
 153                                 }
 154
 155                                 // for the ith parameter, check for aliases against
 156                                 // the set of allocation sites reachable from this
 157                                 // task context
 158                                 Iterator allocItr = allocSites.iterator();
 159                                 while (allocItr.hasNext()) {
 160                                         AllocSite as = (AllocSite) allocItr.next();
 161                                         common = createsPotentialAliases(td, i, as);
 162                                         if (!common.isEmpty()) {
 163                                                 foundSomeAlias = true;
 164                                                 if (!tabularOutput) {
 165                                                         bw.write("Potential alias between parameter " + i
 166                                                                         + " and " + as.getFlatNew() + ".\n");
 167                                                         bw.write(prettyPrintNodeSet(common) + "\n");
 168                                                 } else {
 169                                                         ++numAlias;
 170                                                 }
 171                                         }
 172                                 }
 173                         }
 174
 175                         // for each allocation site check for aliases with
 176                         // other allocation sites in the context of execution
 177                         // of this task
 178                         HashSet<AllocSite> outerChecked = new HashSet<AllocSite>();
 179                         Iterator allocItr1 = allocSites.iterator();
 180                         while (allocItr1.hasNext()) {
 181                                 AllocSite as1 = (AllocSite) allocItr1.next();
 182
 183                                 Iterator allocItr2 = allocSites.iterator();
 184                                 while (allocItr2.hasNext()) {
 185                                         AllocSite as2 = (AllocSite) allocItr2.next();
 186
 187                                         if (!outerChecked.contains(as2)) {
 188                                                 common = createsPotentialAliases(td, as1, as2);
 189
 190                                                 if (!common.isEmpty()) {
 191                                                         foundSomeAlias = true;
 192                                                         if (!tabularOutput) {
 193                                                                 bw.write("Potential alias between "
 194                                                                                 + as1.getFlatNew() + " and "
 195                                                                                 + as2.getFlatNew() + ".\n");
 196                                                                 bw.write(prettyPrintNodeSet(common) + "\n");
 197                                                         } else {
 198                                                                 ++numAlias;
 199                                                         }
 200                                                 }
 201                                         }
 202                                 }
 203
 204                                 outerChecked.add(as1);
 205                         }
 206
 207                         if (!foundSomeAlias) {
 208                                 if (!tabularOutput) {
 209                                         bw.write("No aliases between flagged objects in Task " + td
 210                                                         + ".\n");
 211                                 }
 212                         }
 213                 }
 214
 215                 /*
 216                 if (!tabularOutput) {
 217                         bw.write("\n" + computeAliasContextHistogram());
 218                 } else {
 219                         bw.write(" & " + numAlias + " & " + justTime + " & " + numLines
 220                                         + " & " + numMethodsAnalyzed() + " \\\\\n");
 221                 }
 222                 */
 223
 224                 bw.close();
 225         }
 226
 227         // this version of writeAllAliases is for Java programs that have no tasks
 228           public void writeAllAliasesJava(String outputFile,
 229                                           String timeReport,
 230                                           String justTime,
 231                                           boolean tabularOutput,
 232                                           int numLines
 233 )
 234                         throws java.io.IOException {
 235                 checkAnalysisComplete();
 236
 237                 assert !state.TASK;
 238
 239                 BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile));
 240
 241                 bw.write("Conducting ownership analysis with allocation depth = "
 242                                 + allocationDepth + "\n");
 243                 bw.write(timeReport + "\n\n");
 244
 245                 boolean foundSomeAlias = false;
 246
 247                 Descriptor d = typeUtil.getMain();
 248                 HashSet<AllocSite> allocSites = getFlaggedAllocationSites(d);
 249
 250                 // for each allocation site check for aliases with
 251                 // other allocation sites in the context of execution
 252                 // of this task
 253                 HashSet<AllocSite> outerChecked = new HashSet<AllocSite>();
 254                 Iterator allocItr1 = allocSites.iterator();
 255                 while (allocItr1.hasNext()) {
 256                         AllocSite as1 = (AllocSite) allocItr1.next();
 257
 258                         Iterator allocItr2 = allocSites.iterator();
 259                         while (allocItr2.hasNext()) {
 260                                 AllocSite as2 = (AllocSite) allocItr2.next();
 261
 262                                 if (!outerChecked.contains(as2)) {
 263                                         Set<HeapRegionNode> common = createsPotentialAliases(d,
 264                                                         as1, as2);
 265
 266                                         if (!common.isEmpty()) {
 267                                                 foundSomeAlias = true;
 268                                                 bw.write("Potential alias between "
 269                                                                 + as1.getDisjointAnalysisId() + " and "
 270                                                                 + as2.getDisjointAnalysisId() + ".\n");
 271                                                 bw.write(prettyPrintNodeSet(common) + "\n");
 272                                         }
 273                                 }
 274                         }
 275
 276                         outerChecked.add(as1);
 277                 }
 278
 279                 if (!foundSomeAlias) {
 280                         bw.write("No aliases between flagged objects found.\n");
 281                 }
 282
 283 //              bw.write("\n" + computeAliasContextHistogram());
 284                 bw.close();
 285         }
 286
 287           ///////////////////////////////////////////
 288           //
 289           // end public interface
 290           //
 291           ///////////////////////////////////////////
 292
 293           protected void checkAnalysisComplete() {
 294                     if( !analysisComplete ) {
 295                       throw new Error("Warning: public interface method called while analysis is running.");
 296                     }
 297           }
 298
 299
 300   // data from the compiler
 301   public State            state;
 302   public CallGraph        callGraph;
 303   public Liveness         liveness;
 304   public ArrayReferencees arrayReferencees;
 305   public TypeUtil         typeUtil;
 306   public int              allocationDepth;
 307
 308   // data structure for public interface
 309   private Hashtable<Descriptor,    HashSet<AllocSite> > mapDescriptorToAllocSiteSet;
 310
 311
 312   // for public interface methods to warn that they
 313   // are grabbing results during analysis
 314   private boolean analysisComplete;
 315
 316
 317   // used to identify HeapRegionNode objects
 318   // A unique ID equates an object in one
 319   // ownership graph with an object in another
 320   // graph that logically represents the same
 321   // heap region
 322   // start at 10 and increment to reserve some
 323   // IDs for special purposes
 324   static protected int uniqueIDcount = 10;
 325
 326
 327   // An out-of-scope method created by the
 328   // analysis that has no parameters, and
 329   // appears to allocate the command line
 330   // arguments, then invoke the source code's
 331   // main method.  The purpose of this is to
 332   // provide the analysis with an explicit
 333   // top-level context with no parameters
 334   protected MethodDescriptor mdAnalysisEntry;
 335   protected FlatMethod       fmAnalysisEntry;
 336
 337   // main method defined by source program
 338   protected MethodDescriptor mdSourceEntry;
 339
 340   // the set of task and/or method descriptors
 341   // reachable in call graph
 342   protected Set<Descriptor>
 343     descriptorsToAnalyze;
 344
 345   // current descriptors to visit in fixed-point
 346   // interprocedural analysis, prioritized by
 347   // dependency in the call graph
 348   protected PriorityQueue<DescriptorQWrapper>
 349     descriptorsToVisitQ;
 350
 351   // a duplication of the above structure, but
 352   // for efficient testing of inclusion
 353   protected HashSet<Descriptor>
 354     descriptorsToVisitSet;
 355
 356   // storage for priorities (doesn't make sense)
 357   // to add it to the Descriptor class, just in
 358   // this analysis
 359   protected Hashtable<Descriptor, Integer>
 360     mapDescriptorToPriority;
 361
 362
 363   // maps a descriptor to its current partial result
 364   // from the intraprocedural fixed-point analysis--
 365   // then the interprocedural analysis settles, this
 366   // mapping will have the final results for each
 367   // method descriptor
 368   protected Hashtable<Descriptor, ReachGraph>
 369     mapDescriptorToCompleteReachGraph;
 370
 371   // maps a descriptor to its known dependents: namely
 372   // methods or tasks that call the descriptor's method
 373   // AND are part of this analysis (reachable from main)
 374   protected Hashtable< Descriptor, Set<Descriptor> >
 375     mapDescriptorToSetDependents;
 376
 377   // maps each flat new to one analysis abstraction
 378   // allocate site object, these exist outside reach graphs
 379   protected Hashtable<FlatNew, AllocSite>
 380     mapFlatNewToAllocSite;
 381
 382   // maps intergraph heap region IDs to intergraph
 383   // allocation sites that created them, a redundant
 384   // structure for efficiency in some operations
 385   protected Hashtable<Integer, AllocSite>
 386     mapHrnIdToAllocSite;
 387
 388   // maps a method to its initial heap model (IHM) that
 389   // is the set of reachability graphs from every caller
 390   // site, all merged together.  The reason that we keep
 391   // them separate is that any one call site's contribution
 392   // to the IHM may changed along the path to the fixed point
 393   protected Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >
 394     mapDescriptorToIHMcontributions;
 395
 396   // TODO -- CHANGE EDGE/TYPE/FIELD storage!
 397   public static final String arrayElementFieldName = "___element_";
 398   static protected Hashtable<TypeDescriptor, FieldDescriptor>
 399     mapTypeToArrayField;
 400
 401   // for controlling DOT file output
 402   protected boolean writeFinalDOTs;
 403   protected boolean writeAllIncrementalDOTs;
 404
 405   // supporting DOT output--when we want to write every
 406   // partial method result, keep a tally for generating
 407   // unique filenames
 408   protected Hashtable<Descriptor, Integer>
 409     mapDescriptorToNumUpdates;
 410
 411   //map task descriptor to initial task parameter
 412   protected Hashtable<Descriptor, ReachGraph>
 413   mapDescriptorToReachGraph;
 414
 415
 416   // allocate various structures that are not local
 417   // to a single class method--should be done once
 418   protected void allocateStructures() {
 419     descriptorsToAnalyze = new HashSet<Descriptor>();
 420
 421     mapDescriptorToCompleteReachGraph =
 422       new Hashtable<Descriptor, ReachGraph>();
 423
 424     mapDescriptorToNumUpdates =
 425       new Hashtable<Descriptor, Integer>();
 426
 427     mapDescriptorToSetDependents =
 428       new Hashtable< Descriptor, Set<Descriptor> >();
 429
 430     mapFlatNewToAllocSite =
 431       new Hashtable<FlatNew, AllocSite>();
 432
 433     mapDescriptorToIHMcontributions =
 434       new Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >();
 435
 436     mapHrnIdToAllocSite =
 437       new Hashtable<Integer, AllocSite>();
 438
 439     mapTypeToArrayField =
 440       new Hashtable <TypeDescriptor, FieldDescriptor>();
 441
 442     descriptorsToVisitQ =
 443       new PriorityQueue<DescriptorQWrapper>();
 444
 445     descriptorsToVisitSet =
 446       new HashSet<Descriptor>();
 447
 448     mapDescriptorToPriority =
 449       new Hashtable<Descriptor, Integer>();
 450
 451     mapDescriptorToAllocSiteSet =
 452         new Hashtable<Descriptor,    HashSet<AllocSite> >();
 453
 454     mapDescriptorToReachGraph =
 455         new Hashtable<Descriptor, ReachGraph>();
 456   }
 457
 458
 459
 460   // this analysis generates a disjoint reachability
 461   // graph for every reachable method in the program
 462   public DisjointAnalysis( State            s,
 463                            TypeUtil         tu,
 464                            CallGraph        cg,
 465                            Liveness         l,
 466                            ArrayReferencees ar
 467                            ) throws java.io.IOException {
 468     init( s, tu, cg, l, ar );
 469   }
 470
 471   protected void init( State            state,
 472                        TypeUtil         typeUtil,
 473                        CallGraph        callGraph,
 474                        Liveness         liveness,
 475                        ArrayReferencees arrayReferencees
 476                        ) throws java.io.IOException {
 477
 478         analysisComplete = false;
 479
 480     this.state                   = state;
 481     this.typeUtil                = typeUtil;
 482     this.callGraph               = callGraph;
 483     this.liveness                = liveness;
 484     this.arrayReferencees        = arrayReferencees;
 485     this.allocationDepth         = state.DISJOINTALLOCDEPTH;
 486     this.writeFinalDOTs          = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL;
 487     this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS &&  state.DISJOINTWRITEALL;
 488
 489     // set some static configuration for ReachGraphs
 490     ReachGraph.allocationDepth = allocationDepth;
 491     ReachGraph.typeUtil        = typeUtil;
 492
 493     allocateStructures();
 494
 495     double timeStartAnalysis = (double) System.nanoTime();
 496
 497     // start interprocedural fixed-point computation
 498     analyzeMethods();
 499     analysisComplete=true;
 500
 501     double timeEndAnalysis = (double) System.nanoTime();
 502     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 503     String treport = String.format( "The reachability analysis took %.3f sec.", dt );
 504     String justtime = String.format( "%.2f", dt );
 505     System.out.println( treport );
 506
 507     if( writeFinalDOTs && !writeAllIncrementalDOTs ) {
 508       writeFinalGraphs();
 509     }
 510
 511     if( state.DISJOINTWRITEIHMS ) {
 512       writeFinalIHMs();
 513     }
 514
 515     if( state.DISJOINTALIASFILE != null ) {
 516       if( state.TASK ) {
 517         // not supporting tasks yet...
 518           writeAllAliases("allresult", treport, justtime, state.OWNERSHIPALIASTAB, state.lines);
 519       } else {
 520         /*
 521         writeAllAliasesJava( aliasFile,
 522                              treport,
 523                              justtime,
 524                              state.DISJOINTALIASTAB,
 525                              state.lines );
 526         */
 527       }
 528     }
 529   }
 530
 531
 532   // fixed-point computation over the call graph--when a
 533   // method's callees are updated, it must be reanalyzed
 534   protected void analyzeMethods() throws java.io.IOException {
 535
 536     if( state.TASK ) {
 537       // This analysis does not support Bamboo at the moment,
 538       // but if it does in the future we would initialize the
 539       // set of descriptors to analyze as the program-reachable
 540       // tasks and the methods callable by them.  For Java,
 541       // just methods reachable from the main method.
 542       System.out.println( "Bamboo..." );
 543       Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 544
 545       while (taskItr.hasNext()) {
 546           TaskDescriptor td = (TaskDescriptor) taskItr.next();
 547           if (!descriptorsToAnalyze.contains(td)) {
 548               descriptorsToAnalyze.add(td);
 549               descriptorsToAnalyze.addAll(callGraph.getAllMethods(td));
 550           }
 551       }
 552
 553     } else {
 554       // add all methods transitively reachable from the
 555       // source's main to set for analysis
 556       mdSourceEntry = typeUtil.getMain();
 557       descriptorsToAnalyze.add( mdSourceEntry );
 558       descriptorsToAnalyze.addAll(
 559         callGraph.getAllMethods( mdSourceEntry )
 560                                    );
 561
 562       // fabricate an empty calling context that will call
 563       // the source's main, but call graph doesn't know
 564       // about it, so explicitly add it
 565       makeAnalysisEntryMethod( mdSourceEntry );
 566       descriptorsToAnalyze.add( mdAnalysisEntry );
 567     }
 568
 569     // topologically sort according to the call graph so
 570     // leaf calls are ordered first, smarter analysis order
 571     LinkedList<Descriptor> sortedDescriptors =
 572       topologicalSort( descriptorsToAnalyze );
 573
 574     // add sorted descriptors to priority queue, and duplicate
 575     // the queue as a set for efficiently testing whether some
 576     // method is marked for analysis
 577     int p = 0;
 578     Iterator<Descriptor> dItr = sortedDescriptors.iterator();
 579     while( dItr.hasNext() ) {
 580       Descriptor d = dItr.next();
 581       mapDescriptorToPriority.put( d, new Integer( p ) );
 582       descriptorsToVisitQ.add( new DescriptorQWrapper( p, d ) );
 583       descriptorsToVisitSet.add( d );
 584       ++p;
 585     }
 586
 587     // analyze methods from the priority queue until it is empty
 588     while( !descriptorsToVisitQ.isEmpty() ) {
 589       Descriptor d = descriptorsToVisitQ.poll().getDescriptor();
 590       assert descriptorsToVisitSet.contains( d );
 591       descriptorsToVisitSet.remove( d );
 592
 593       // because the task or method descriptor just extracted
 594       // was in the "to visit" set it either hasn't been analyzed
 595       // yet, or some method that it depends on has been
 596       // updated.  Recompute a complete reachability graph for
 597       // this task/method and compare it to any previous result.
 598       // If there is a change detected, add any methods/tasks
 599       // that depend on this one to the "to visit" set.
 600
 601       System.out.println( "Analyzing " + d );
 602
 603       ReachGraph rg     = analyzeMethod( d );
 604       ReachGraph rgPrev = getPartial( d );
 605
 606       if( !rg.equals( rgPrev ) ) {
 607         setPartial( d, rg );
 608
 609         // results for d changed, so enqueue dependents
 610         // of d for further analysis
 611         Iterator<Descriptor> depsItr = getDependents( d ).iterator();
 612         while( depsItr.hasNext() ) {
 613           Descriptor dNext = depsItr.next();
 614           enqueue( dNext );
 615         }
 616       }
 617     }
 618   }
 619
 620   protected ReachGraph analyzeMethod( Descriptor d )
 621     throws java.io.IOException {
 622
 623     // get the flat code for this descriptor
 624     FlatMethod fm;
 625     if( d == mdAnalysisEntry ) {
 626       fm = fmAnalysisEntry;
 627     } else {
 628       fm = state.getMethodFlat( d );
 629     }
 630
 631     // intraprocedural work set
 632     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 633     flatNodesToVisit.add( fm );
 634
 635     // mapping of current partial results
 636     Hashtable<FlatNode, ReachGraph> mapFlatNodeToReachGraph =
 637       new Hashtable<FlatNode, ReachGraph>();
 638
 639     // the set of return nodes partial results that will be combined as
 640     // the final, conservative approximation of the entire method
 641     HashSet<FlatReturnNode> setReturns = new HashSet<FlatReturnNode>();
 642
 643     while( !flatNodesToVisit.isEmpty() ) {
 644       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 645       flatNodesToVisit.remove( fn );
 646
 647       //System.out.println( "  "+fn );
 648
 649       // effect transfer function defined by this node,
 650       // then compare it to the old graph at this node
 651       // to see if anything was updated.
 652
 653       ReachGraph rg = new ReachGraph();
 654       TaskDescriptor taskDesc;
 655       if(fn instanceof FlatMethod && (taskDesc=((FlatMethod)fn).getTask())!=null){
 656           if(mapDescriptorToReachGraph.containsKey(taskDesc)){
 657                   // retrieve existing reach graph if it is not first time
 658                   rg=mapDescriptorToReachGraph.get(taskDesc);
 659           }else{
 660                   // create initial reach graph for a task
 661                   rg=createInitialTaskReachGraph((FlatMethod)fn);
 662                   rg.globalSweep();
 663                   mapDescriptorToReachGraph.put(taskDesc, rg);
 664           }
 665       }
 666
 667       // start by merging all node's parents' graphs
 668       for( int i = 0; i < fn.numPrev(); ++i ) {
 669         FlatNode pn = fn.getPrev( i );
 670         if( mapFlatNodeToReachGraph.containsKey( pn ) ) {
 671           ReachGraph rgParent = mapFlatNodeToReachGraph.get( pn );
 672           rg.merge( rgParent );
 673         }
 674       }
 675
 676       if( takeDebugSnapshots &&
 677           d.getSymbol().equals( descSymbolDebug )
 678           ) {
 679         debugSnapshot( rg, fn, true );
 680       }
 681
 682       // modify rg with appropriate transfer function
 683       rg = analyzeFlatNode( d, fm, fn, setReturns, rg );
 684
 685       if( takeDebugSnapshots &&
 686           d.getSymbol().equals( descSymbolDebug )
 687           ) {
 688         debugSnapshot( rg, fn, false );
 689       }
 690
 691
 692       // if the results of the new graph are different from
 693       // the current graph at this node, replace the graph
 694       // with the update and enqueue the children
 695       ReachGraph rgPrev = mapFlatNodeToReachGraph.get( fn );
 696       if( !rg.equals( rgPrev ) ) {
 697         mapFlatNodeToReachGraph.put( fn, rg );
 698
 699         for( int i = 0; i < fn.numNext(); i++ ) {
 700           FlatNode nn = fn.getNext( i );
 701           flatNodesToVisit.add( nn );
 702         }
 703       }
 704     }
 705
 706     // end by merging all return nodes into a complete
 707     // ownership graph that represents all possible heap
 708     // states after the flat method returns
 709     ReachGraph completeGraph = new ReachGraph();
 710
 711     assert !setReturns.isEmpty();
 712     Iterator retItr = setReturns.iterator();
 713     while( retItr.hasNext() ) {
 714       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 715
 716       assert mapFlatNodeToReachGraph.containsKey( frn );
 717       ReachGraph rgRet = mapFlatNodeToReachGraph.get( frn );
 718
 719       completeGraph.merge( rgRet );
 720     }
 721     return completeGraph;
 722   }
 723
 724
 725   protected ReachGraph
 726     analyzeFlatNode( Descriptor              d,
 727                      FlatMethod              fmContaining,
 728                      FlatNode                fn,
 729                      HashSet<FlatReturnNode> setRetNodes,
 730                      ReachGraph              rg
 731                      ) throws java.io.IOException {
 732
 733
 734     // any variables that are no longer live should be
 735     // nullified in the graph to reduce edges
 736     //rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) );
 737
 738
 739     TempDescriptor  lhs;
 740     TempDescriptor  rhs;
 741     FieldDescriptor fld;
 742
 743     // use node type to decide what transfer function
 744     // to apply to the reachability graph
 745     switch( fn.kind() ) {
 746
 747     case FKind.FlatMethod: {
 748       // construct this method's initial heap model (IHM)
 749       // since we're working on the FlatMethod, we know
 750       // the incoming ReachGraph 'rg' is empty
 751
 752       Hashtable<FlatCall, ReachGraph> heapsFromCallers =
 753         getIHMcontributions( d );
 754
 755       Set entrySet = heapsFromCallers.entrySet();
 756       Iterator itr = entrySet.iterator();
 757       while( itr.hasNext() ) {
 758         Map.Entry  me        = (Map.Entry)  itr.next();
 759         FlatCall   fc        = (FlatCall)   me.getKey();
 760         ReachGraph rgContrib = (ReachGraph) me.getValue();
 761
 762         assert fc.getMethod().equals( d );
 763
 764         // some call sites are in same method context though,
 765         // and all of them should be merged together first,
 766         // then heaps from different contexts should be merged
 767         // THIS ASSUMES DIFFERENT CONTEXTS NEED SPECIAL CONSIDERATION!
 768         // such as, do allocation sites need to be aged?
 769
 770         rg.merge_diffMethodContext( rgContrib );
 771       }
 772     } break;
 773
 774     case FKind.FlatOpNode:
 775       FlatOpNode fon = (FlatOpNode) fn;
 776       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 777         lhs = fon.getDest();
 778         rhs = fon.getLeft();
 779         rg.assignTempXEqualToTempY( lhs, rhs );
 780       }
 781       break;
 782
 783     case FKind.FlatCastNode:
 784       FlatCastNode fcn = (FlatCastNode) fn;
 785       lhs = fcn.getDst();
 786       rhs = fcn.getSrc();
 787
 788       TypeDescriptor td = fcn.getType();
 789       assert td != null;
 790
 791       rg.assignTempXEqualToCastedTempY( lhs, rhs, td );
 792       break;
 793
 794     case FKind.FlatFieldNode:
 795       FlatFieldNode ffn = (FlatFieldNode) fn;
 796       lhs = ffn.getDst();
 797       rhs = ffn.getSrc();
 798       fld = ffn.getField();
 799       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 800         rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld );
 801       }
 802       break;
 803
 804     case FKind.FlatSetFieldNode:
 805       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 806       lhs = fsfn.getDst();
 807       fld = fsfn.getField();
 808       rhs = fsfn.getSrc();
 809       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 810         rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs );
 811       }
 812       break;
 813
 814     case FKind.FlatElementNode:
 815       FlatElementNode fen = (FlatElementNode) fn;
 816       lhs = fen.getDst();
 817       rhs = fen.getSrc();
 818       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 819
 820         assert rhs.getType() != null;
 821         assert rhs.getType().isArray();
 822
 823         TypeDescriptor  tdElement = rhs.getType().dereference();
 824         FieldDescriptor fdElement = getArrayField( tdElement );
 825
 826         rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement );
 827       }
 828       break;
 829
 830     case FKind.FlatSetElementNode:
 831       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 832
 833       if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) {
 834         // skip this node if it cannot create new reachability paths
 835         break;
 836       }
 837
 838       lhs = fsen.getDst();
 839       rhs = fsen.getSrc();
 840       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 841
 842         assert lhs.getType() != null;
 843         assert lhs.getType().isArray();
 844
 845         TypeDescriptor  tdElement = lhs.getType().dereference();
 846         FieldDescriptor fdElement = getArrayField( tdElement );
 847
 848         rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs );
 849       }
 850       break;
 851
 852     case FKind.FlatNew:
 853       FlatNew fnn = (FlatNew) fn;
 854       lhs = fnn.getDst();
 855       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 856         AllocSite as = getAllocSiteFromFlatNewPRIVATE( fnn );
 857         rg.assignTempEqualToNewAlloc( lhs, as );
 858       }
 859       break;
 860
 861     case FKind.FlatCall: {
 862       //TODO: temporal fix for task descriptor case
 863       //MethodDescriptor mdCaller = fmContaining.getMethod();
 864       Descriptor mdCaller;
 865       if(fmContaining.getMethod()!=null){
 866           mdCaller  = fmContaining.getMethod();
 867       }else{
 868           mdCaller = fmContaining.getTask();
 869       }
 870       FlatCall         fc       = (FlatCall) fn;
 871       MethodDescriptor mdCallee = fc.getMethod();
 872       FlatMethod       fmCallee = state.getMethodFlat( mdCallee );
 873
 874       boolean writeDebugDOTs =
 875         mdCaller.getSymbol().equals( state.DISJOINTDEBUGCALLER ) &&
 876         mdCallee.getSymbol().equals( state.DISJOINTDEBUGCALLEE );
 877
 878
 879       // calculate the heap this call site can reach--note this is
 880       // not used for the current call site transform, we are
 881       // grabbing this heap model for future analysis of the callees,
 882       // so if different results emerge we will return to this site
 883       ReachGraph heapForThisCall_old =
 884         getIHMcontribution( mdCallee, fc );
 885
 886       // the computation of the callee-reachable heap
 887       // is useful for making the callee starting point
 888       // and for applying the call site transfer function
 889       Set<Integer> callerNodeIDsCopiedToCallee =
 890         new HashSet<Integer>();
 891
 892       ReachGraph heapForThisCall_cur =
 893         rg.makeCalleeView( fc,
 894                            fmCallee,
 895                            callerNodeIDsCopiedToCallee,
 896                            writeDebugDOTs
 897                            );
 898
 899       if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) {
 900         // if heap at call site changed, update the contribution,
 901         // and reschedule the callee for analysis
 902         addIHMcontribution( mdCallee, fc, heapForThisCall_cur );
 903         enqueue( mdCallee );
 904       }
 905
 906
 907
 908
 909       // the transformation for a call site should update the
 910       // current heap abstraction with any effects from the callee,
 911       // or if the method is virtual, the effects from any possible
 912       // callees, so find the set of callees...
 913       Set<MethodDescriptor> setPossibleCallees =
 914         new HashSet<MethodDescriptor>();
 915
 916       if( mdCallee.isStatic() ) {
 917         setPossibleCallees.add( mdCallee );
 918       } else {
 919         TypeDescriptor typeDesc = fc.getThis().getType();
 920         setPossibleCallees.addAll( callGraph.getMethods( mdCallee,
 921                                                          typeDesc )
 922                                    );
 923       }
 924
 925       ReachGraph rgMergeOfEffects = new ReachGraph();
 926
 927       Iterator<MethodDescriptor> mdItr = setPossibleCallees.iterator();
 928       while( mdItr.hasNext() ) {
 929         MethodDescriptor mdPossible = mdItr.next();
 930         FlatMethod       fmPossible = state.getMethodFlat( mdPossible );
 931
 932         addDependent( mdPossible, // callee
 933                       d );        // caller
 934
 935         // don't alter the working graph (rg) until we compute a
 936         // result for every possible callee, merge them all together,
 937         // then set rg to that
 938         ReachGraph rgCopy = new ReachGraph();
 939         rgCopy.merge( rg );
 940
 941         ReachGraph rgEffect = getPartial( mdPossible );
 942
 943         if( rgEffect == null ) {
 944           // if this method has never been analyzed just schedule it
 945           // for analysis and skip over this call site for now
 946           enqueue( mdPossible );
 947         } else {
 948           rgCopy.resolveMethodCall( fc,
 949                                     fmPossible,
 950                                     rgEffect,
 951                                     callerNodeIDsCopiedToCallee,
 952                                     writeDebugDOTs
 953                                     );
 954         }
 955
 956         rgMergeOfEffects.merge( rgCopy );
 957       }
 958
 959
 960       // now that we've taken care of building heap models for
 961       // callee analysis, finish this transformation
 962       rg = rgMergeOfEffects;
 963     } break;
 964
 965
 966     case FKind.FlatReturnNode:
 967       FlatReturnNode frn = (FlatReturnNode) fn;
 968       rhs = frn.getReturnTemp();
 969       if( rhs != null && !rhs.getType().isImmutable() ) {
 970         rg.assignReturnEqualToTemp( rhs );
 971       }
 972       setRetNodes.add( frn );
 973       break;
 974
 975     } // end switch
 976
 977
 978     // dead variables were removed before the above transfer function
 979     // was applied, so eliminate heap regions and edges that are no
 980     // longer part of the abstractly-live heap graph, and sweep up
 981     // and reachability effects that are altered by the reduction
 982     //rg.abstractGarbageCollect();
 983     //rg.globalSweep();
 984
 985
 986     // at this point rg should be the correct update
 987     // by an above transfer function, or untouched if
 988     // the flat node type doesn't affect the heap
 989     return rg;
 990   }
 991
 992
 993   // this method should generate integers strictly greater than zero!
 994   // special "shadow" regions are made from a heap region by negating
 995   // the ID
 996   static public Integer generateUniqueHeapRegionNodeID() {
 997     ++uniqueIDcount;
 998     return new Integer( uniqueIDcount );
 999   }
1000
1001
1002
1003   static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
1004     FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
1005     if( fdElement == null ) {
1006       fdElement = new FieldDescriptor( new Modifiers( Modifiers.PUBLIC ),
1007                                        tdElement,
1008                                        arrayElementFieldName,
1009                                        null,
1010                                        false );
1011       mapTypeToArrayField.put( tdElement, fdElement );
1012     }
1013     return fdElement;
1014   }
1015
1016
1017
1018   private void writeFinalGraphs() {
1019     Set entrySet = mapDescriptorToCompleteReachGraph.entrySet();
1020     Iterator itr = entrySet.iterator();
1021     while( itr.hasNext() ) {
1022       Map.Entry  me = (Map.Entry)  itr.next();
1023       Descriptor  d = (Descriptor) me.getKey();
1024       ReachGraph rg = (ReachGraph) me.getValue();
1025
1026       try {
1027         rg.writeGraph( "COMPLETE"+d,
1028                        true,   // write labels (variables)
1029                        true,   // selectively hide intermediate temp vars
1030                        true,   // prune unreachable heap regions
1031                        false,  // hide subset reachability states
1032                        true ); // hide edge taints
1033       } catch( IOException e ) {}
1034     }
1035   }
1036
1037   private void writeFinalIHMs() {
1038     Iterator d2IHMsItr = mapDescriptorToIHMcontributions.entrySet().iterator();
1039     while( d2IHMsItr.hasNext() ) {
1040       Map.Entry                        me1 = (Map.Entry)                       d2IHMsItr.next();
1041       Descriptor                         d = (Descriptor)                      me1.getKey();
1042       Hashtable<FlatCall, ReachGraph> IHMs = (Hashtable<FlatCall, ReachGraph>) me1.getValue();
1043
1044       Iterator fc2rgItr = IHMs.entrySet().iterator();
1045       while( fc2rgItr.hasNext() ) {
1046         Map.Entry  me2 = (Map.Entry)  fc2rgItr.next();
1047         FlatCall   fc  = (FlatCall)   me2.getKey();
1048         ReachGraph rg  = (ReachGraph) me2.getValue();
1049
1050         try {
1051           rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc,
1052                          true,   // write labels (variables)
1053                          false,  // selectively hide intermediate temp vars
1054                          false,  // prune unreachable heap regions
1055                          false,  // hide subset reachability states
1056                          true ); // hide edge taints
1057         } catch( IOException e ) {}
1058       }
1059     }
1060   }
1061
1062
1063
1064
1065   // return just the allocation site associated with one FlatNew node
1066   protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) {
1067
1068     if( !mapFlatNewToAllocSite.containsKey( fnew ) ) {
1069       AllocSite as =
1070         (AllocSite) Canonical.makeCanonical( new AllocSite( allocationDepth,
1071                                                             fnew,
1072                                                             fnew.getDisjointId()
1073                                                             )
1074                                              );
1075
1076       // the newest nodes are single objects
1077       for( int i = 0; i < allocationDepth; ++i ) {
1078         Integer id = generateUniqueHeapRegionNodeID();
1079         as.setIthOldest( i, id );
1080         mapHrnIdToAllocSite.put( id, as );
1081       }
1082
1083       // the oldest node is a summary node
1084       as.setSummary( generateUniqueHeapRegionNodeID() );
1085
1086       mapFlatNewToAllocSite.put( fnew, as );
1087     }
1088
1089     return mapFlatNewToAllocSite.get( fnew );
1090   }
1091
1092
1093   /*
1094   // return all allocation sites in the method (there is one allocation
1095   // site per FlatNew node in a method)
1096   protected HashSet<AllocSite> getAllocSiteSet(Descriptor d) {
1097     if( !mapDescriptorToAllocSiteSet.containsKey(d) ) {
1098       buildAllocSiteSet(d);
1099     }
1100
1101     return mapDescriptorToAllocSiteSet.get(d);
1102
1103   }
1104   */
1105
1106   /*
1107   protected void buildAllocSiteSet(Descriptor d) {
1108     HashSet<AllocSite> s = new HashSet<AllocSite>();
1109
1110     FlatMethod fm = state.getMethodFlat( d );
1111
1112     // visit every node in this FlatMethod's IR graph
1113     // and make a set of the allocation sites from the
1114     // FlatNew node's visited
1115     HashSet<FlatNode> visited = new HashSet<FlatNode>();
1116     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1117     toVisit.add( fm );
1118
1119     while( !toVisit.isEmpty() ) {
1120       FlatNode n = toVisit.iterator().next();
1121
1122       if( n instanceof FlatNew ) {
1123         s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) );
1124       }
1125
1126       toVisit.remove( n );
1127       visited.add( n );
1128
1129       for( int i = 0; i < n.numNext(); ++i ) {
1130         FlatNode child = n.getNext( i );
1131         if( !visited.contains( child ) ) {
1132           toVisit.add( child );
1133         }
1134       }
1135     }
1136
1137     mapDescriptorToAllocSiteSet.put( d, s );
1138   }
1139   */
1140   /*
1141   protected HashSet<AllocSite> getFlaggedAllocSites(Descriptor dIn) {
1142
1143     HashSet<AllocSite> out     = new HashSet<AllocSite>();
1144     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
1145     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
1146
1147     toVisit.add(dIn);
1148
1149     while( !toVisit.isEmpty() ) {
1150       Descriptor d = toVisit.iterator().next();
1151       toVisit.remove(d);
1152       visited.add(d);
1153
1154       HashSet<AllocSite> asSet = getAllocSiteSet(d);
1155       Iterator asItr = asSet.iterator();
1156       while( asItr.hasNext() ) {
1157         AllocSite as = (AllocSite) asItr.next();
1158         if( as.getDisjointAnalysisId() != null ) {
1159           out.add(as);
1160         }
1161       }
1162
1163       // enqueue callees of this method to be searched for
1164       // allocation sites also
1165       Set callees = callGraph.getCalleeSet(d);
1166       if( callees != null ) {
1167         Iterator methItr = callees.iterator();
1168         while( methItr.hasNext() ) {
1169           MethodDescriptor md = (MethodDescriptor) methItr.next();
1170
1171           if( !visited.contains(md) ) {
1172             toVisit.add(md);
1173           }
1174         }
1175       }
1176     }
1177
1178     return out;
1179   }
1180   */
1181
1182   /*
1183   protected HashSet<AllocSite>
1184   getFlaggedAllocSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1185
1186     HashSet<AllocSite> asSetTotal = new HashSet<AllocSite>();
1187     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1188     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1189
1190     toVisit.add(td);
1191
1192     // traverse this task and all methods reachable from this task
1193     while( !toVisit.isEmpty() ) {
1194       Descriptor d = toVisit.iterator().next();
1195       toVisit.remove(d);
1196       visited.add(d);
1197
1198       HashSet<AllocSite> asSet = getAllocSiteSet(d);
1199       Iterator asItr = asSet.iterator();
1200       while( asItr.hasNext() ) {
1201         AllocSite as = (AllocSite) asItr.next();
1202         TypeDescriptor typed = as.getType();
1203         if( typed != null ) {
1204           ClassDescriptor cd = typed.getClassDesc();
1205           if( cd != null && cd.hasFlags() ) {
1206             asSetTotal.add(as);
1207           }
1208         }
1209       }
1210
1211       // enqueue callees of this method to be searched for
1212       // allocation sites also
1213       Set callees = callGraph.getCalleeSet(d);
1214       if( callees != null ) {
1215         Iterator methItr = callees.iterator();
1216         while( methItr.hasNext() ) {
1217           MethodDescriptor md = (MethodDescriptor) methItr.next();
1218
1219           if( !visited.contains(md) ) {
1220             toVisit.add(md);
1221           }
1222         }
1223       }
1224     }
1225
1226
1227     return asSetTotal;
1228   }
1229   */
1230
1231
1232   /*
1233   protected String computeAliasContextHistogram() {
1234
1235     Hashtable<Integer, Integer> mapNumContexts2NumDesc =
1236       new Hashtable<Integer, Integer>();
1237
1238     Iterator itr = mapDescriptorToAllDescriptors.entrySet().iterator();
1239     while( itr.hasNext() ) {
1240       Map.Entry me = (Map.Entry) itr.next();
1241       HashSet<Descriptor> s = (HashSet<Descriptor>) me.getValue();
1242
1243       Integer i = mapNumContexts2NumDesc.get( s.size() );
1244       if( i == null ) {
1245         i = new Integer( 0 );
1246       }
1247       mapNumContexts2NumDesc.put( s.size(), i + 1 );
1248     }
1249
1250     String s = "";
1251     int total = 0;
1252
1253     itr = mapNumContexts2NumDesc.entrySet().iterator();
1254     while( itr.hasNext() ) {
1255       Map.Entry me = (Map.Entry) itr.next();
1256       Integer c0 = (Integer) me.getKey();
1257       Integer d0 = (Integer) me.getValue();
1258       total += d0;
1259       s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 );
1260     }
1261
1262     s += String.format( "\n%4d total methods analayzed.\n", total );
1263
1264     return s;
1265   }
1266
1267   protected int numMethodsAnalyzed() {
1268     return descriptorsToAnalyze.size();
1269   }
1270   */
1271
1272
1273
1274
1275   // Take in source entry which is the program's compiled entry and
1276   // create a new analysis entry, a method that takes no parameters
1277   // and appears to allocate the command line arguments and call the
1278   // source entry with them.  The purpose of this analysis entry is
1279   // to provide a top-level method context with no parameters left.
1280   protected void makeAnalysisEntryMethod( MethodDescriptor mdSourceEntry ) {
1281
1282     Modifiers mods = new Modifiers();
1283     mods.addModifier( Modifiers.PUBLIC );
1284     mods.addModifier( Modifiers.STATIC );
1285
1286     TypeDescriptor returnType =
1287       new TypeDescriptor( TypeDescriptor.VOID );
1288
1289     this.mdAnalysisEntry =
1290       new MethodDescriptor( mods,
1291                             returnType,
1292                             "analysisEntryMethod"
1293                             );
1294
1295     TempDescriptor cmdLineArgs =
1296       new TempDescriptor( "args",
1297                           mdSourceEntry.getParamType( 0 )
1298                           );
1299
1300     FlatNew fn =
1301       new FlatNew( mdSourceEntry.getParamType( 0 ),
1302                    cmdLineArgs,
1303                    false // is global
1304                    );
1305
1306     TempDescriptor[] sourceEntryArgs = new TempDescriptor[1];
1307     sourceEntryArgs[0] = cmdLineArgs;
1308
1309     FlatCall fc =
1310       new FlatCall( mdSourceEntry,
1311                     null, // dst temp
1312                     null, // this temp
1313                     sourceEntryArgs
1314                     );
1315
1316     FlatReturnNode frn = new FlatReturnNode( null );
1317
1318     FlatExit fe = new FlatExit();
1319
1320     this.fmAnalysisEntry =
1321       new FlatMethod( mdAnalysisEntry,
1322                       fe
1323                       );
1324
1325     this.fmAnalysisEntry.addNext( fn );
1326     fn.addNext( fc );
1327     fc.addNext( frn );
1328     frn.addNext( fe );
1329   }
1330
1331
1332   protected LinkedList<Descriptor> topologicalSort( Set<Descriptor> toSort ) {
1333
1334     Set       <Descriptor> discovered = new HashSet   <Descriptor>();
1335     LinkedList<Descriptor> sorted     = new LinkedList<Descriptor>();
1336
1337     Iterator<Descriptor> itr = toSort.iterator();
1338     while( itr.hasNext() ) {
1339       Descriptor d = itr.next();
1340
1341       if( !discovered.contains( d ) ) {
1342         dfsVisit( d, toSort, sorted, discovered );
1343       }
1344     }
1345
1346     return sorted;
1347   }
1348
1349   // While we're doing DFS on call graph, remember
1350   // dependencies for efficient queuing of methods
1351   // during interprocedural analysis:
1352   //
1353   // a dependent of a method decriptor d for this analysis is:
1354   //  1) a method or task that invokes d
1355   //  2) in the descriptorsToAnalyze set
1356   protected void dfsVisit( Descriptor             d,
1357                            Set       <Descriptor> toSort,
1358                            LinkedList<Descriptor> sorted,
1359                            Set       <Descriptor> discovered ) {
1360     discovered.add( d );
1361
1362     // only methods have callers, tasks never do
1363     if( d instanceof MethodDescriptor ) {
1364
1365       MethodDescriptor md = (MethodDescriptor) d;
1366
1367       // the call graph is not aware that we have a fabricated
1368       // analysis entry that calls the program source's entry
1369       if( md == mdSourceEntry ) {
1370         if( !discovered.contains( mdAnalysisEntry ) ) {
1371           addDependent( mdSourceEntry,  // callee
1372                         mdAnalysisEntry // caller
1373                         );
1374           dfsVisit( mdAnalysisEntry, toSort, sorted, discovered );
1375         }
1376       }
1377
1378       // otherwise call graph guides DFS
1379       Iterator itr = callGraph.getCallerSet( md ).iterator();
1380       while( itr.hasNext() ) {
1381         Descriptor dCaller = (Descriptor) itr.next();
1382
1383         // only consider callers in the original set to analyze
1384         if( !toSort.contains( dCaller ) ) {
1385           continue;
1386         }
1387
1388         if( !discovered.contains( dCaller ) ) {
1389           addDependent( md,     // callee
1390                         dCaller // caller
1391                         );
1392
1393           dfsVisit( dCaller, toSort, sorted, discovered );
1394         }
1395       }
1396     }
1397
1398     sorted.addFirst( d );
1399   }
1400
1401
1402   protected void enqueue( Descriptor d ) {
1403     if( !descriptorsToVisitSet.contains( d ) ) {
1404       Integer priority = mapDescriptorToPriority.get( d );
1405       descriptorsToVisitQ.add( new DescriptorQWrapper( priority,
1406                                                        d )
1407                                );
1408       descriptorsToVisitSet.add( d );
1409     }
1410   }
1411
1412
1413   protected ReachGraph getPartial( Descriptor d ) {
1414     return mapDescriptorToCompleteReachGraph.get( d );
1415   }
1416
1417   protected void setPartial( Descriptor d, ReachGraph rg ) {
1418     mapDescriptorToCompleteReachGraph.put( d, rg );
1419
1420     // when the flag for writing out every partial
1421     // result is set, we should spit out the graph,
1422     // but in order to give it a unique name we need
1423     // to track how many partial results for this
1424     // descriptor we've already written out
1425     if( writeAllIncrementalDOTs ) {
1426       if( !mapDescriptorToNumUpdates.containsKey( d ) ) {
1427         mapDescriptorToNumUpdates.put( d, new Integer( 0 ) );
1428       }
1429       Integer n = mapDescriptorToNumUpdates.get( d );
1430       /*
1431       try {
1432         rg.writeGraph( d+"COMPLETE"+String.format( "%05d", n ),
1433                        true,  // write labels (variables)
1434                        true,  // selectively hide intermediate temp vars
1435                        true,  // prune unreachable heap regions
1436                        false, // show back edges to confirm graph validity
1437                        false, // show parameter indices (unmaintained!)
1438                        true,  // hide subset reachability states
1439                        true); // hide edge taints
1440       } catch( IOException e ) {}
1441       */
1442       mapDescriptorToNumUpdates.put( d, n + 1 );
1443     }
1444   }
1445
1446
1447   // a dependent of a method decriptor d for this analysis is:
1448   //  1) a method or task that invokes d
1449   //  2) in the descriptorsToAnalyze set
1450   protected void addDependent( Descriptor callee, Descriptor caller ) {
1451     Set<Descriptor> deps = mapDescriptorToSetDependents.get( callee );
1452     if( deps == null ) {
1453       deps = new HashSet<Descriptor>();
1454     }
1455     deps.add( caller );
1456     mapDescriptorToSetDependents.put( callee, deps );
1457   }
1458
1459   protected Set<Descriptor> getDependents( Descriptor callee ) {
1460     Set<Descriptor> deps = mapDescriptorToSetDependents.get( callee );
1461     if( deps == null ) {
1462       deps = new HashSet<Descriptor>();
1463       mapDescriptorToSetDependents.put( callee, deps );
1464     }
1465     return deps;
1466   }
1467
1468
1469   public Hashtable<FlatCall, ReachGraph> getIHMcontributions( Descriptor d ) {
1470
1471     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1472       mapDescriptorToIHMcontributions.get( d );
1473
1474     if( heapsFromCallers == null ) {
1475       heapsFromCallers = new Hashtable<FlatCall, ReachGraph>();
1476       mapDescriptorToIHMcontributions.put( d, heapsFromCallers );
1477     }
1478
1479     return heapsFromCallers;
1480   }
1481
1482   public ReachGraph getIHMcontribution( Descriptor d,
1483                                         FlatCall   fc
1484                                         ) {
1485     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1486       getIHMcontributions( d );
1487
1488     if( !heapsFromCallers.containsKey( fc ) ) {
1489       heapsFromCallers.put( fc, new ReachGraph() );
1490     }
1491
1492     return heapsFromCallers.get( fc );
1493   }
1494
1495   public void addIHMcontribution( Descriptor d,
1496                                   FlatCall   fc,
1497                                   ReachGraph rg
1498                                   ) {
1499     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1500       getIHMcontributions( d );
1501
1502     heapsFromCallers.put( fc, rg );
1503   }
1504
1505 private AllocSite createParameterAllocSite(ReachGraph rg, TempDescriptor tempDesc) {
1506
1507     // create temp descriptor for each parameter variable
1508     FlatNew flatNew = new FlatNew(tempDesc.getType(), tempDesc, false);
1509     // create allocation site
1510     AllocSite as = (AllocSite) Canonical.makeCanonical(new AllocSite( allocationDepth, flatNew, flatNew.getDisjointId()));
1511     for (int i = 0; i < allocationDepth; ++i) {
1512         Integer id = generateUniqueHeapRegionNodeID();
1513         as.setIthOldest(i, id);
1514         mapHrnIdToAllocSite.put(id, as);
1515     }
1516     // the oldest node is a summary node
1517     as.setSummary( generateUniqueHeapRegionNodeID() );
1518
1519     rg.age(as);
1520
1521     return as;
1522
1523 }
1524
1525 private ReachGraph createInitialTaskReachGraph(FlatMethod fm) {
1526     ReachGraph rg = new ReachGraph();
1527     TaskDescriptor taskDesc = fm.getTask();
1528
1529     for (int idx = 0; idx < taskDesc.numParameters(); idx++) {
1530         Descriptor paramDesc = taskDesc.getParameter(idx);
1531         TypeDescriptor paramTypeDesc = taskDesc.getParamType(idx);
1532
1533         // setup data structure
1534         Set<HashMap<HeapRegionNode, FieldDescriptor>> workSet =
1535             new HashSet<HashMap<HeapRegionNode, FieldDescriptor>>();
1536         Hashtable<TypeDescriptor, HeapRegionNode> mapTypeToExistingSummaryNode =
1537             new Hashtable<TypeDescriptor, HeapRegionNode>();
1538         Set<String> doneSet = new HashSet<String>();
1539
1540         TempDescriptor tempDesc = fm.getParameter(idx);
1541
1542         AllocSite as = createParameterAllocSite(rg, tempDesc);
1543         VariableNode lnX = rg.getVariableNodeFromTemp(tempDesc);
1544         Integer idNewest = as.getIthOldest(0);
1545         HeapRegionNode hrnNewest = rg.id2hrn.get(idNewest);
1546         // make a new reference to allocated node
1547         RefEdge edgeNew = new RefEdge(lnX, // source
1548                                       hrnNewest, // dest
1549                                       taskDesc.getParamType(idx), // type
1550                                       null, // field name
1551                                       hrnNewest.getAlpha(), // beta
1552                                       ExistPredSet.factory(rg.predTrue) // predicates
1553                                       );
1554         rg.addRefEdge(lnX, hrnNewest, edgeNew);
1555
1556         // set-up a work set for class field
1557         ClassDescriptor classDesc = paramTypeDesc.getClassDesc();
1558         for (Iterator it = classDesc.getFields(); it.hasNext();) {
1559             FieldDescriptor fd = (FieldDescriptor) it.next();
1560             TypeDescriptor fieldType = fd.getType();
1561             if (!fieldType.isImmutable() || fieldType.isArray()) {
1562                 HashMap<HeapRegionNode, FieldDescriptor> newMap = new HashMap<HeapRegionNode, FieldDescriptor>();
1563                 newMap.put(hrnNewest, fd);
1564                 workSet.add(newMap);
1565             }
1566         }
1567
1568         int uniqueIdentifier = 0;
1569         while (!workSet.isEmpty()) {
1570             HashMap<HeapRegionNode, FieldDescriptor> map = workSet
1571                 .iterator().next();
1572             workSet.remove(map);
1573
1574             Set<HeapRegionNode> key = map.keySet();
1575             HeapRegionNode srcHRN = key.iterator().next();
1576             FieldDescriptor fd = map.get(srcHRN);
1577             TypeDescriptor type = fd.getType();
1578             String doneSetIdentifier = srcHRN.getIDString() + "_" + fd;
1579
1580             if (!doneSet.contains(doneSetIdentifier)) {
1581                 doneSet.add(doneSetIdentifier);
1582                 if (!mapTypeToExistingSummaryNode.containsKey(type)) {
1583                     // create new summary Node
1584                     TempDescriptor td = new TempDescriptor("temp"
1585                                                            + uniqueIdentifier, type);
1586
1587                     AllocSite allocSite;
1588                     if(type.equals(paramTypeDesc)){
1589                     //corresponding allocsite has already been created for a parameter variable.
1590                         allocSite=as;
1591                     }else{
1592                         allocSite = createParameterAllocSite(rg, td);
1593                     }
1594                     String strDesc = allocSite.toStringForDOT()
1595                         + "\\nsummary";
1596                     HeapRegionNode hrnSummary =
1597                         rg.createNewHeapRegionNode(allocSite.getSummary(), // id or null to generate a new one
1598                                                    false, // single object?
1599                                                    true, // summary?
1600                                                    false, // flagged?
1601                                                    false, // out-of-context?
1602                                                    allocSite.getType(), // type
1603                                                    allocSite, // allocation site
1604                                                    null, // inherent reach
1605                                                    srcHRN.getAlpha(), // current reach
1606                                                    ExistPredSet.factory(), // predicates
1607                                                    strDesc // description
1608                                                    );
1609
1610                     // make a new reference to summary node
1611                     RefEdge edgeToSummary = new RefEdge(srcHRN, // source
1612                                                         hrnSummary, // dest
1613                                                         fd.getType(), // type
1614                                                         fd.getSymbol(), // field name
1615                                                         srcHRN.getAlpha(), // beta
1616                                                         ExistPredSet.factory(rg.predTrue) // predicates
1617                                                         );
1618
1619                     rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary);
1620
1621                     uniqueIdentifier++;
1622
1623                     mapTypeToExistingSummaryNode.put(type, hrnSummary);
1624
1625                     // set-up a work set for  fields of the class
1626                     if(!type.isImmutable()){
1627                     classDesc = type.getClassDesc();
1628                     for (Iterator it = classDesc.getFields(); it.hasNext();) {
1629                         FieldDescriptor typeFieldDesc = (FieldDescriptor) it.next();
1630                         TypeDescriptor fieldType = typeFieldDesc.getType();
1631                         if (!fieldType.isImmutable()) {
1632                             doneSetIdentifier = hrnSummary.getIDString() + "_" + typeFieldDesc;
1633                             if(!doneSet.contains(doneSetIdentifier)){
1634                                 // add new work item
1635                                 HashMap<HeapRegionNode, FieldDescriptor> newMap =
1636                                     new HashMap<HeapRegionNode, FieldDescriptor>();
1637                                 newMap.put(hrnSummary, typeFieldDesc);
1638                                 workSet.add(newMap);
1639                             }
1640                         }
1641                     }
1642                     }
1643
1644                 }else{
1645                     // if there exists corresponding summary node
1646                     HeapRegionNode hrnDst=mapTypeToExistingSummaryNode.get(type);
1647
1648                     RefEdge edgeToSummary = new RefEdge(srcHRN, // source
1649                                                         hrnDst, // dest
1650                                                         fd.getType(), // type
1651                                                         fd.getSymbol(), // field name
1652                                                         srcHRN.getAlpha(), // beta
1653                                                         ExistPredSet.factory(rg.predTrue) // predicates
1654                                                         );
1655                     rg.addRefEdge(srcHRN, hrnDst, edgeToSummary);
1656
1657                 }
1658             }
1659         }
1660     }
1661 //    debugSnapshot(rg, fm, true);
1662     return rg;
1663 }
1664
1665 // return all allocation sites in the method (there is one allocation
1666 // site per FlatNew node in a method)
1667 private HashSet<AllocSite> getAllocationSiteSet(Descriptor d) {
1668   if( !mapDescriptorToAllocSiteSet.containsKey(d) ) {
1669     buildAllocationSiteSet(d);
1670   }
1671
1672   return mapDescriptorToAllocSiteSet.get(d);
1673
1674 }
1675
1676 private void buildAllocationSiteSet(Descriptor d) {
1677     HashSet<AllocSite> s = new HashSet<AllocSite>();
1678
1679     FlatMethod fm;
1680     if( d instanceof MethodDescriptor ) {
1681       fm = state.getMethodFlat( (MethodDescriptor) d);
1682     } else {
1683       assert d instanceof TaskDescriptor;
1684       fm = state.getMethodFlat( (TaskDescriptor) d);
1685     }
1686
1687     // visit every node in this FlatMethod's IR graph
1688     // and make a set of the allocation sites from the
1689     // FlatNew node's visited
1690     HashSet<FlatNode> visited = new HashSet<FlatNode>();
1691     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1692     toVisit.add(fm);
1693
1694     while( !toVisit.isEmpty() ) {
1695       FlatNode n = toVisit.iterator().next();
1696
1697       if( n instanceof FlatNew ) {
1698         s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) );
1699       }
1700
1701       toVisit.remove(n);
1702       visited.add(n);
1703
1704       for( int i = 0; i < n.numNext(); ++i ) {
1705         FlatNode child = n.getNext(i);
1706         if( !visited.contains(child) ) {
1707           toVisit.add(child);
1708         }
1709       }
1710     }
1711
1712     mapDescriptorToAllocSiteSet.put(d, s);
1713   }
1714
1715         private HashSet<AllocSite> getFlaggedAllocationSites(Descriptor dIn) {
1716
1717                 HashSet<AllocSite> out = new HashSet<AllocSite>();
1718                 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
1719                 HashSet<Descriptor> visited = new HashSet<Descriptor>();
1720
1721                 toVisit.add(dIn);
1722
1723                 while (!toVisit.isEmpty()) {
1724                         Descriptor d = toVisit.iterator().next();
1725                         toVisit.remove(d);
1726                         visited.add(d);
1727
1728                         HashSet<AllocSite> asSet = getAllocationSiteSet(d);
1729                         Iterator asItr = asSet.iterator();
1730                         while (asItr.hasNext()) {
1731                                 AllocSite as = (AllocSite) asItr.next();
1732                                 if (as.getDisjointAnalysisId() != null) {
1733                                         out.add(as);
1734                                 }
1735                         }
1736
1737                         // enqueue callees of this method to be searched for
1738                         // allocation sites also
1739                         Set callees = callGraph.getCalleeSet(d);
1740                         if (callees != null) {
1741                                 Iterator methItr = callees.iterator();
1742                                 while (methItr.hasNext()) {
1743                                         MethodDescriptor md = (MethodDescriptor) methItr.next();
1744
1745                                         if (!visited.contains(md)) {
1746                                                 toVisit.add(md);
1747                                         }
1748                                 }
1749                         }
1750                 }
1751
1752                 return out;
1753         }
1754
1755
1756 private HashSet<AllocSite>
1757 getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1758
1759   HashSet<AllocSite> asSetTotal = new HashSet<AllocSite>();
1760   HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1761   HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1762
1763   toVisit.add(td);
1764
1765   // traverse this task and all methods reachable from this task
1766   while( !toVisit.isEmpty() ) {
1767     Descriptor d = toVisit.iterator().next();
1768     toVisit.remove(d);
1769     visited.add(d);
1770
1771     HashSet<AllocSite> asSet = getAllocationSiteSet(d);
1772     Iterator asItr = asSet.iterator();
1773     while( asItr.hasNext() ) {
1774         AllocSite as = (AllocSite) asItr.next();
1775         TypeDescriptor typed = as.getType();
1776         if( typed != null ) {
1777           ClassDescriptor cd = typed.getClassDesc();
1778           if( cd != null && cd.hasFlags() ) {
1779             asSetTotal.add(as);
1780           }
1781         }
1782     }
1783
1784     // enqueue callees of this method to be searched for
1785     // allocation sites also
1786     Set callees = callGraph.getCalleeSet(d);
1787     if( callees != null ) {
1788         Iterator methItr = callees.iterator();
1789         while( methItr.hasNext() ) {
1790           MethodDescriptor md = (MethodDescriptor) methItr.next();
1791
1792           if( !visited.contains(md) ) {
1793             toVisit.add(md);
1794           }
1795         }
1796     }
1797   }
1798
1799   return asSetTotal;
1800 }
1801
1802
1803   int zzz = 0;
1804
1805
1806
1807
1808   // get successive captures of the analysis state
1809   boolean takeDebugSnapshots = false;
1810   String descSymbolDebug = "main";
1811   boolean stopAfterCapture = true;
1812
1813   // increments every visit to debugSnapshot, don't fiddle with it
1814   int debugCounter = 0;
1815
1816   // the value of debugCounter to start reporting the debugCounter
1817   // to the screen to let user know what debug iteration we're at
1818   int numStartCountReport = 0;
1819
1820   // the frequency of debugCounter values to print out, 0 no report
1821   int freqCountReport = 0;
1822
1823   // the debugCounter value at which to start taking snapshots
1824   int iterStartCapture = 0;
1825
1826   // the number of snapshots to take
1827   int numIterToCapture = 300;
1828
1829   void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) {
1830     if( debugCounter > iterStartCapture + numIterToCapture ) {
1831       return;
1832     }
1833
1834     if( in ) {
1835       ++debugCounter;
1836     }
1837
1838     if( debugCounter    > numStartCountReport &&
1839         freqCountReport > 0                   &&
1840         debugCounter % freqCountReport == 0
1841         ) {
1842       System.out.println( "    @@@ debug counter = "+
1843                           debugCounter );
1844     }
1845
1846     if( debugCounter > iterStartCapture ) {
1847       System.out.println( "    @@@ capturing debug "+
1848                           (debugCounter - iterStartCapture)+
1849                           " @@@" );
1850       String graphName;
1851       if( in ) {
1852         graphName = String.format( "snap%04din",
1853                                    debugCounter - iterStartCapture );
1854       } else {
1855         graphName = String.format( "snap%04dout",
1856                                    debugCounter - iterStartCapture );
1857       }
1858       if( fn != null ) {
1859         graphName = graphName + fn;
1860       }
1861       try {
1862         rg.writeGraph( graphName,
1863                        true,  // write labels (variables)
1864                        true,  // selectively hide intermediate temp vars
1865                        true,  // prune unreachable heap regions
1866                        true,  // hide subset reachability states
1867                        true );// hide edge taints
1868       } catch( Exception e ) {
1869         System.out.println( "Error writing debug capture." );
1870         System.exit( 0 );
1871       }
1872     }
1873
1874     if( debugCounter == iterStartCapture + numIterToCapture &&
1875         stopAfterCapture
1876         ) {
1877       System.out.println( "Stopping analysis after debug captures." );
1878       System.exit( 0 );
1879     }
1880   }
1881
1882 }