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(state.OWNERSHIPALIASFILE, 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 //        System.out.println("parent="+pn+"->"+rgParent);
 673           rg.merge( rgParent );
 674         }
 675       }
 676
 677       // modify rg with appropriate transfer function
 678       rg = analyzeFlatNode( d, fm, fn, setReturns, rg );
 679
 680       // if the results of the new graph are different from
 681       // the current graph at this node, replace the graph
 682       // with the update and enqueue the children
 683       ReachGraph rgPrev = mapFlatNodeToReachGraph.get( fn );
 684       if( !rg.equals( rgPrev ) ) {
 685         mapFlatNodeToReachGraph.put( fn, rg );
 686
 687         for( int i = 0; i < fn.numNext(); i++ ) {
 688           FlatNode nn = fn.getNext( i );
 689           flatNodesToVisit.add( nn );
 690         }
 691       }
 692     }
 693
 694     // end by merging all return nodes into a complete
 695     // ownership graph that represents all possible heap
 696     // states after the flat method returns
 697     ReachGraph completeGraph = new ReachGraph();
 698
 699     assert !setReturns.isEmpty();
 700     Iterator retItr = setReturns.iterator();
 701     while( retItr.hasNext() ) {
 702       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 703
 704       assert mapFlatNodeToReachGraph.containsKey( frn );
 705       ReachGraph rgRet = mapFlatNodeToReachGraph.get( frn );
 706
 707       completeGraph.merge( rgRet );
 708     }
 709     return completeGraph;
 710   }
 711
 712
 713   protected ReachGraph
 714     analyzeFlatNode( Descriptor              d,
 715                      FlatMethod              fmContaining,
 716                      FlatNode                fn,
 717                      HashSet<FlatReturnNode> setRetNodes,
 718                      ReachGraph              rg
 719                      ) throws java.io.IOException {
 720
 721
 722     // any variables that are no longer live should be
 723     // nullified in the graph to reduce edges
 724     //rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) );
 725
 726
 727     TempDescriptor  lhs;
 728     TempDescriptor  rhs;
 729     FieldDescriptor fld;
 730
 731     // use node type to decide what transfer function
 732     // to apply to the reachability graph
 733     switch( fn.kind() ) {
 734
 735     case FKind.FlatMethod: {
 736       // construct this method's initial heap model (IHM)
 737       // since we're working on the FlatMethod, we know
 738       // the incoming ReachGraph 'rg' is empty
 739
 740       Hashtable<FlatCall, ReachGraph> heapsFromCallers =
 741         getIHMcontributions( d );
 742
 743       Set entrySet = heapsFromCallers.entrySet();
 744       Iterator itr = entrySet.iterator();
 745       while( itr.hasNext() ) {
 746         Map.Entry  me        = (Map.Entry)  itr.next();
 747         FlatCall   fc        = (FlatCall)   me.getKey();
 748         ReachGraph rgContrib = (ReachGraph) me.getValue();
 749
 750         assert fc.getMethod().equals( d );
 751
 752         // some call sites are in same method context though,
 753         // and all of them should be merged together first,
 754         // then heaps from different contexts should be merged
 755         // THIS ASSUMES DIFFERENT CONTEXTS NEED SPECIAL CONSIDERATION!
 756         // such as, do allocation sites need to be aged?
 757
 758         rg.merge_diffMethodContext( rgContrib );
 759       }
 760     } break;
 761
 762     case FKind.FlatOpNode:
 763       FlatOpNode fon = (FlatOpNode) fn;
 764       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 765         lhs = fon.getDest();
 766         rhs = fon.getLeft();
 767         rg.assignTempXEqualToTempY( lhs, rhs );
 768       }
 769       break;
 770
 771     case FKind.FlatCastNode:
 772       FlatCastNode fcn = (FlatCastNode) fn;
 773       lhs = fcn.getDst();
 774       rhs = fcn.getSrc();
 775
 776       TypeDescriptor td = fcn.getType();
 777       assert td != null;
 778
 779       rg.assignTempXEqualToCastedTempY( lhs, rhs, td );
 780       break;
 781
 782     case FKind.FlatFieldNode:
 783       FlatFieldNode ffn = (FlatFieldNode) fn;
 784       lhs = ffn.getDst();
 785       rhs = ffn.getSrc();
 786       fld = ffn.getField();
 787       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 788         rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld );
 789       }
 790       break;
 791
 792     case FKind.FlatSetFieldNode:
 793       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 794       lhs = fsfn.getDst();
 795       fld = fsfn.getField();
 796       rhs = fsfn.getSrc();
 797       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 798         rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs );
 799       }
 800       break;
 801
 802     case FKind.FlatElementNode:
 803       FlatElementNode fen = (FlatElementNode) fn;
 804       lhs = fen.getDst();
 805       rhs = fen.getSrc();
 806       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 807
 808         assert rhs.getType() != null;
 809         assert rhs.getType().isArray();
 810
 811         TypeDescriptor  tdElement = rhs.getType().dereference();
 812         FieldDescriptor fdElement = getArrayField( tdElement );
 813
 814         rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement );
 815       }
 816       break;
 817
 818     case FKind.FlatSetElementNode:
 819       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 820
 821       if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) {
 822         // skip this node if it cannot create new reachability paths
 823         break;
 824       }
 825
 826       lhs = fsen.getDst();
 827       rhs = fsen.getSrc();
 828       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 829
 830         assert lhs.getType() != null;
 831         assert lhs.getType().isArray();
 832
 833         TypeDescriptor  tdElement = lhs.getType().dereference();
 834         FieldDescriptor fdElement = getArrayField( tdElement );
 835
 836         rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs );
 837       }
 838       break;
 839
 840     case FKind.FlatNew:
 841       FlatNew fnn = (FlatNew) fn;
 842       lhs = fnn.getDst();
 843       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 844         AllocSite as = getAllocSiteFromFlatNewPRIVATE( fnn );
 845         rg.assignTempEqualToNewAlloc( lhs, as );
 846       }
 847       break;
 848
 849     case FKind.FlatCall: {
 850       //TODO: temporal fix for task descriptor case
 851       //MethodDescriptor mdCaller = fmContaining.getMethod();
 852       Descriptor mdCaller;
 853       if(fmContaining.getMethod()!=null){
 854           mdCaller  = fmContaining.getMethod();
 855       }else{
 856           mdCaller = fmContaining.getTask();
 857       }
 858       FlatCall         fc       = (FlatCall) fn;
 859       MethodDescriptor mdCallee = fc.getMethod();
 860       FlatMethod       fmCallee = state.getMethodFlat( mdCallee );
 861
 862       boolean writeDebugDOTs =
 863         mdCaller.getSymbol().equals( state.DISJOINTDEBUGCALLER ) &&
 864         mdCallee.getSymbol().equals( state.DISJOINTDEBUGCALLEE );
 865
 866
 867       // calculate the heap this call site can reach--note this is
 868       // not used for the current call site transform, we are
 869       // grabbing this heap model for future analysis of the callees,
 870       // so if different results emerge we will return to this site
 871       ReachGraph heapForThisCall_old =
 872         getIHMcontribution( mdCallee, fc );
 873
 874       // the computation of the callee-reachable heap
 875       // is useful for making the callee starting point
 876       // and for applying the call site transfer function
 877       Set<Integer> callerNodeIDsCopiedToCallee =
 878         new HashSet<Integer>();
 879
 880       ReachGraph heapForThisCall_cur =
 881         rg.makeCalleeView( fc,
 882                            fmCallee,
 883                            callerNodeIDsCopiedToCallee,
 884                            writeDebugDOTs
 885                            );
 886
 887       if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) {
 888         // if heap at call site changed, update the contribution,
 889         // and reschedule the callee for analysis
 890         addIHMcontribution( mdCallee, fc, heapForThisCall_cur );
 891         enqueue( mdCallee );
 892       }
 893
 894
 895
 896
 897       // the transformation for a call site should update the
 898       // current heap abstraction with any effects from the callee,
 899       // or if the method is virtual, the effects from any possible
 900       // callees, so find the set of callees...
 901       Set<MethodDescriptor> setPossibleCallees =
 902         new HashSet<MethodDescriptor>();
 903
 904       if( mdCallee.isStatic() ) {
 905         setPossibleCallees.add( mdCallee );
 906       } else {
 907         TypeDescriptor typeDesc = fc.getThis().getType();
 908         setPossibleCallees.addAll( callGraph.getMethods( mdCallee,
 909                                                          typeDesc )
 910                                    );
 911       }
 912
 913       ReachGraph rgMergeOfEffects = new ReachGraph();
 914
 915       Iterator<MethodDescriptor> mdItr = setPossibleCallees.iterator();
 916       while( mdItr.hasNext() ) {
 917         MethodDescriptor mdPossible = mdItr.next();
 918         FlatMethod       fmPossible = state.getMethodFlat( mdPossible );
 919
 920         addDependent( mdPossible, // callee
 921                       d );        // caller
 922
 923         // don't alter the working graph (rg) until we compute a
 924         // result for every possible callee, merge them all together,
 925         // then set rg to that
 926         ReachGraph rgCopy = new ReachGraph();
 927         rgCopy.merge( rg );
 928
 929         ReachGraph rgEffect = getPartial( mdPossible );
 930
 931         if( rgEffect == null ) {
 932           // if this method has never been analyzed just schedule it
 933           // for analysis and skip over this call site for now
 934           enqueue( mdPossible );
 935         } else {
 936           rgCopy.resolveMethodCall( fc,
 937                                     fmPossible,
 938                                     rgEffect,
 939                                     callerNodeIDsCopiedToCallee,
 940                                     writeDebugDOTs
 941                                     );
 942         }
 943
 944         rgMergeOfEffects.merge( rgCopy );
 945       }
 946
 947
 948       // now that we've taken care of building heap models for
 949       // callee analysis, finish this transformation
 950       rg = rgMergeOfEffects;
 951     } break;
 952
 953
 954     case FKind.FlatReturnNode:
 955       FlatReturnNode frn = (FlatReturnNode) fn;
 956       rhs = frn.getReturnTemp();
 957       if( rhs != null && !rhs.getType().isImmutable() ) {
 958         rg.assignReturnEqualToTemp( rhs );
 959       }
 960       setRetNodes.add( frn );
 961       break;
 962
 963     } // end switch
 964
 965
 966     // dead variables were removed before the above transfer function
 967     // was applied, so eliminate heap regions and edges that are no
 968     // longer part of the abstractly-live heap graph, and sweep up
 969     // and reachability effects that are altered by the reduction
 970     //rg.abstractGarbageCollect();
 971     //rg.globalSweep();
 972
 973
 974     // at this point rg should be the correct update
 975     // by an above transfer function, or untouched if
 976     // the flat node type doesn't affect the heap
 977     return rg;
 978   }
 979
 980
 981   // this method should generate integers strictly greater than zero!
 982   // special "shadow" regions are made from a heap region by negating
 983   // the ID
 984   static public Integer generateUniqueHeapRegionNodeID() {
 985     ++uniqueIDcount;
 986     return new Integer( uniqueIDcount );
 987   }
 988
 989
 990
 991   static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
 992     FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
 993     if( fdElement == null ) {
 994       fdElement = new FieldDescriptor( new Modifiers( Modifiers.PUBLIC ),
 995                                        tdElement,
 996                                        arrayElementFieldName,
 997                                        null,
 998                                        false );
 999       mapTypeToArrayField.put( tdElement, fdElement );
1000     }
1001     return fdElement;
1002   }
1003
1004
1005
1006   private void writeFinalGraphs() {
1007     Set entrySet = mapDescriptorToCompleteReachGraph.entrySet();
1008     Iterator itr = entrySet.iterator();
1009     while( itr.hasNext() ) {
1010       Map.Entry  me = (Map.Entry)  itr.next();
1011       Descriptor  d = (Descriptor) me.getKey();
1012       ReachGraph rg = (ReachGraph) me.getValue();
1013
1014       try {
1015         rg.writeGraph( "COMPLETE"+d,
1016                        true,   // write labels (variables)
1017                        true,   // selectively hide intermediate temp vars
1018                        true,   // prune unreachable heap regions
1019                        false,  // hide subset reachability states
1020                        true ); // hide edge taints
1021       } catch( IOException e ) {}
1022     }
1023   }
1024
1025   private void writeFinalIHMs() {
1026     Iterator d2IHMsItr = mapDescriptorToIHMcontributions.entrySet().iterator();
1027     while( d2IHMsItr.hasNext() ) {
1028       Map.Entry                        me1 = (Map.Entry)                       d2IHMsItr.next();
1029       Descriptor                         d = (Descriptor)                      me1.getKey();
1030       Hashtable<FlatCall, ReachGraph> IHMs = (Hashtable<FlatCall, ReachGraph>) me1.getValue();
1031
1032       Iterator fc2rgItr = IHMs.entrySet().iterator();
1033       while( fc2rgItr.hasNext() ) {
1034         Map.Entry  me2 = (Map.Entry)  fc2rgItr.next();
1035         FlatCall   fc  = (FlatCall)   me2.getKey();
1036         ReachGraph rg  = (ReachGraph) me2.getValue();
1037
1038         try {
1039           rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc,
1040                          true,   // write labels (variables)
1041                          false,  // selectively hide intermediate temp vars
1042                          false,  // prune unreachable heap regions
1043                          false,  // hide subset reachability states
1044                          true ); // hide edge taints
1045         } catch( IOException e ) {}
1046       }
1047     }
1048   }
1049
1050
1051
1052
1053   // return just the allocation site associated with one FlatNew node
1054   protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) {
1055
1056     if( !mapFlatNewToAllocSite.containsKey( fnew ) ) {
1057       AllocSite as =
1058         (AllocSite) Canonical.makeCanonical( new AllocSite( allocationDepth,
1059                                                             fnew,
1060                                                             fnew.getDisjointId()
1061                                                             )
1062                                              );
1063
1064       // the newest nodes are single objects
1065       for( int i = 0; i < allocationDepth; ++i ) {
1066         Integer id = generateUniqueHeapRegionNodeID();
1067         as.setIthOldest( i, id );
1068         mapHrnIdToAllocSite.put( id, as );
1069       }
1070
1071       // the oldest node is a summary node
1072       as.setSummary( generateUniqueHeapRegionNodeID() );
1073
1074       mapFlatNewToAllocSite.put( fnew, as );
1075     }
1076
1077     return mapFlatNewToAllocSite.get( fnew );
1078   }
1079
1080
1081   /*
1082   // return all allocation sites in the method (there is one allocation
1083   // site per FlatNew node in a method)
1084   protected HashSet<AllocSite> getAllocSiteSet(Descriptor d) {
1085     if( !mapDescriptorToAllocSiteSet.containsKey(d) ) {
1086       buildAllocSiteSet(d);
1087     }
1088
1089     return mapDescriptorToAllocSiteSet.get(d);
1090
1091   }
1092   */
1093
1094   /*
1095   protected void buildAllocSiteSet(Descriptor d) {
1096     HashSet<AllocSite> s = new HashSet<AllocSite>();
1097
1098     FlatMethod fm = state.getMethodFlat( d );
1099
1100     // visit every node in this FlatMethod's IR graph
1101     // and make a set of the allocation sites from the
1102     // FlatNew node's visited
1103     HashSet<FlatNode> visited = new HashSet<FlatNode>();
1104     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1105     toVisit.add( fm );
1106
1107     while( !toVisit.isEmpty() ) {
1108       FlatNode n = toVisit.iterator().next();
1109
1110       if( n instanceof FlatNew ) {
1111         s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) );
1112       }
1113
1114       toVisit.remove( n );
1115       visited.add( n );
1116
1117       for( int i = 0; i < n.numNext(); ++i ) {
1118         FlatNode child = n.getNext( i );
1119         if( !visited.contains( child ) ) {
1120           toVisit.add( child );
1121         }
1122       }
1123     }
1124
1125     mapDescriptorToAllocSiteSet.put( d, s );
1126   }
1127   */
1128   /*
1129   protected HashSet<AllocSite> getFlaggedAllocSites(Descriptor dIn) {
1130
1131     HashSet<AllocSite> out     = new HashSet<AllocSite>();
1132     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
1133     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
1134
1135     toVisit.add(dIn);
1136
1137     while( !toVisit.isEmpty() ) {
1138       Descriptor d = toVisit.iterator().next();
1139       toVisit.remove(d);
1140       visited.add(d);
1141
1142       HashSet<AllocSite> asSet = getAllocSiteSet(d);
1143       Iterator asItr = asSet.iterator();
1144       while( asItr.hasNext() ) {
1145         AllocSite as = (AllocSite) asItr.next();
1146         if( as.getDisjointAnalysisId() != null ) {
1147           out.add(as);
1148         }
1149       }
1150
1151       // enqueue callees of this method to be searched for
1152       // allocation sites also
1153       Set callees = callGraph.getCalleeSet(d);
1154       if( callees != null ) {
1155         Iterator methItr = callees.iterator();
1156         while( methItr.hasNext() ) {
1157           MethodDescriptor md = (MethodDescriptor) methItr.next();
1158
1159           if( !visited.contains(md) ) {
1160             toVisit.add(md);
1161           }
1162         }
1163       }
1164     }
1165
1166     return out;
1167   }
1168   */
1169
1170   /*
1171   protected HashSet<AllocSite>
1172   getFlaggedAllocSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1173
1174     HashSet<AllocSite> asSetTotal = new HashSet<AllocSite>();
1175     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1176     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1177
1178     toVisit.add(td);
1179
1180     // traverse this task and all methods reachable from this task
1181     while( !toVisit.isEmpty() ) {
1182       Descriptor d = toVisit.iterator().next();
1183       toVisit.remove(d);
1184       visited.add(d);
1185
1186       HashSet<AllocSite> asSet = getAllocSiteSet(d);
1187       Iterator asItr = asSet.iterator();
1188       while( asItr.hasNext() ) {
1189         AllocSite as = (AllocSite) asItr.next();
1190         TypeDescriptor typed = as.getType();
1191         if( typed != null ) {
1192           ClassDescriptor cd = typed.getClassDesc();
1193           if( cd != null && cd.hasFlags() ) {
1194             asSetTotal.add(as);
1195           }
1196         }
1197       }
1198
1199       // enqueue callees of this method to be searched for
1200       // allocation sites also
1201       Set callees = callGraph.getCalleeSet(d);
1202       if( callees != null ) {
1203         Iterator methItr = callees.iterator();
1204         while( methItr.hasNext() ) {
1205           MethodDescriptor md = (MethodDescriptor) methItr.next();
1206
1207           if( !visited.contains(md) ) {
1208             toVisit.add(md);
1209           }
1210         }
1211       }
1212     }
1213
1214
1215     return asSetTotal;
1216   }
1217   */
1218
1219
1220   /*
1221   protected String computeAliasContextHistogram() {
1222
1223     Hashtable<Integer, Integer> mapNumContexts2NumDesc =
1224       new Hashtable<Integer, Integer>();
1225
1226     Iterator itr = mapDescriptorToAllDescriptors.entrySet().iterator();
1227     while( itr.hasNext() ) {
1228       Map.Entry me = (Map.Entry) itr.next();
1229       HashSet<Descriptor> s = (HashSet<Descriptor>) me.getValue();
1230
1231       Integer i = mapNumContexts2NumDesc.get( s.size() );
1232       if( i == null ) {
1233         i = new Integer( 0 );
1234       }
1235       mapNumContexts2NumDesc.put( s.size(), i + 1 );
1236     }
1237
1238     String s = "";
1239     int total = 0;
1240
1241     itr = mapNumContexts2NumDesc.entrySet().iterator();
1242     while( itr.hasNext() ) {
1243       Map.Entry me = (Map.Entry) itr.next();
1244       Integer c0 = (Integer) me.getKey();
1245       Integer d0 = (Integer) me.getValue();
1246       total += d0;
1247       s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 );
1248     }
1249
1250     s += String.format( "\n%4d total methods analayzed.\n", total );
1251
1252     return s;
1253   }
1254
1255   protected int numMethodsAnalyzed() {
1256     return descriptorsToAnalyze.size();
1257   }
1258   */
1259
1260
1261
1262
1263   // Take in source entry which is the program's compiled entry and
1264   // create a new analysis entry, a method that takes no parameters
1265   // and appears to allocate the command line arguments and call the
1266   // source entry with them.  The purpose of this analysis entry is
1267   // to provide a top-level method context with no parameters left.
1268   protected void makeAnalysisEntryMethod( MethodDescriptor mdSourceEntry ) {
1269
1270     Modifiers mods = new Modifiers();
1271     mods.addModifier( Modifiers.PUBLIC );
1272     mods.addModifier( Modifiers.STATIC );
1273
1274     TypeDescriptor returnType =
1275       new TypeDescriptor( TypeDescriptor.VOID );
1276
1277     this.mdAnalysisEntry =
1278       new MethodDescriptor( mods,
1279                             returnType,
1280                             "analysisEntryMethod"
1281                             );
1282
1283     TempDescriptor cmdLineArgs =
1284       new TempDescriptor( "args",
1285                           mdSourceEntry.getParamType( 0 )
1286                           );
1287
1288     FlatNew fn =
1289       new FlatNew( mdSourceEntry.getParamType( 0 ),
1290                    cmdLineArgs,
1291                    false // is global
1292                    );
1293
1294     TempDescriptor[] sourceEntryArgs = new TempDescriptor[1];
1295     sourceEntryArgs[0] = cmdLineArgs;
1296
1297     FlatCall fc =
1298       new FlatCall( mdSourceEntry,
1299                     null, // dst temp
1300                     null, // this temp
1301                     sourceEntryArgs
1302                     );
1303
1304     FlatReturnNode frn = new FlatReturnNode( null );
1305
1306     FlatExit fe = new FlatExit();
1307
1308     this.fmAnalysisEntry =
1309       new FlatMethod( mdAnalysisEntry,
1310                       fe
1311                       );
1312
1313     this.fmAnalysisEntry.addNext( fn );
1314     fn.addNext( fc );
1315     fc.addNext( frn );
1316     frn.addNext( fe );
1317   }
1318
1319
1320   protected LinkedList<Descriptor> topologicalSort( Set<Descriptor> toSort ) {
1321
1322     Set       <Descriptor> discovered = new HashSet   <Descriptor>();
1323     LinkedList<Descriptor> sorted     = new LinkedList<Descriptor>();
1324
1325     Iterator<Descriptor> itr = toSort.iterator();
1326     while( itr.hasNext() ) {
1327       Descriptor d = itr.next();
1328
1329       if( !discovered.contains( d ) ) {
1330         dfsVisit( d, toSort, sorted, discovered );
1331       }
1332     }
1333
1334     return sorted;
1335   }
1336
1337   // While we're doing DFS on call graph, remember
1338   // dependencies for efficient queuing of methods
1339   // during interprocedural analysis:
1340   //
1341   // a dependent of a method decriptor d for this analysis is:
1342   //  1) a method or task that invokes d
1343   //  2) in the descriptorsToAnalyze set
1344   protected void dfsVisit( Descriptor             d,
1345                            Set       <Descriptor> toSort,
1346                            LinkedList<Descriptor> sorted,
1347                            Set       <Descriptor> discovered ) {
1348     discovered.add( d );
1349
1350     // only methods have callers, tasks never do
1351     if( d instanceof MethodDescriptor ) {
1352
1353       MethodDescriptor md = (MethodDescriptor) d;
1354
1355       // the call graph is not aware that we have a fabricated
1356       // analysis entry that calls the program source's entry
1357       if( md == mdSourceEntry ) {
1358         if( !discovered.contains( mdAnalysisEntry ) ) {
1359           addDependent( mdSourceEntry,  // callee
1360                         mdAnalysisEntry // caller
1361                         );
1362           dfsVisit( mdAnalysisEntry, toSort, sorted, discovered );
1363         }
1364       }
1365
1366       // otherwise call graph guides DFS
1367       Iterator itr = callGraph.getCallerSet( md ).iterator();
1368       while( itr.hasNext() ) {
1369         Descriptor dCaller = (Descriptor) itr.next();
1370
1371         // only consider callers in the original set to analyze
1372         if( !toSort.contains( dCaller ) ) {
1373           continue;
1374         }
1375
1376         if( !discovered.contains( dCaller ) ) {
1377           addDependent( md,     // callee
1378                         dCaller // caller
1379                         );
1380
1381           dfsVisit( dCaller, toSort, sorted, discovered );
1382         }
1383       }
1384     }
1385
1386     sorted.addFirst( d );
1387   }
1388
1389
1390   protected void enqueue( Descriptor d ) {
1391     if( !descriptorsToVisitSet.contains( d ) ) {
1392       Integer priority = mapDescriptorToPriority.get( d );
1393       descriptorsToVisitQ.add( new DescriptorQWrapper( priority,
1394                                                        d )
1395                                );
1396       descriptorsToVisitSet.add( d );
1397     }
1398   }
1399
1400
1401   protected ReachGraph getPartial( Descriptor d ) {
1402     return mapDescriptorToCompleteReachGraph.get( d );
1403   }
1404
1405   protected void setPartial( Descriptor d, ReachGraph rg ) {
1406     mapDescriptorToCompleteReachGraph.put( d, rg );
1407
1408     // when the flag for writing out every partial
1409     // result is set, we should spit out the graph,
1410     // but in order to give it a unique name we need
1411     // to track how many partial results for this
1412     // descriptor we've already written out
1413     if( writeAllIncrementalDOTs ) {
1414       if( !mapDescriptorToNumUpdates.containsKey( d ) ) {
1415         mapDescriptorToNumUpdates.put( d, new Integer( 0 ) );
1416       }
1417       Integer n = mapDescriptorToNumUpdates.get( d );
1418       /*
1419       try {
1420         rg.writeGraph( d+"COMPLETE"+String.format( "%05d", n ),
1421                        true,  // write labels (variables)
1422                        true,  // selectively hide intermediate temp vars
1423                        true,  // prune unreachable heap regions
1424                        false, // show back edges to confirm graph validity
1425                        false, // show parameter indices (unmaintained!)
1426                        true,  // hide subset reachability states
1427                        true); // hide edge taints
1428       } catch( IOException e ) {}
1429       */
1430       mapDescriptorToNumUpdates.put( d, n + 1 );
1431     }
1432   }
1433
1434
1435   // a dependent of a method decriptor d for this analysis is:
1436   //  1) a method or task that invokes d
1437   //  2) in the descriptorsToAnalyze set
1438   protected void addDependent( Descriptor callee, Descriptor caller ) {
1439     Set<Descriptor> deps = mapDescriptorToSetDependents.get( callee );
1440     if( deps == null ) {
1441       deps = new HashSet<Descriptor>();
1442     }
1443     deps.add( caller );
1444     mapDescriptorToSetDependents.put( callee, deps );
1445   }
1446
1447   protected Set<Descriptor> getDependents( Descriptor callee ) {
1448     Set<Descriptor> deps = mapDescriptorToSetDependents.get( callee );
1449     if( deps == null ) {
1450       deps = new HashSet<Descriptor>();
1451       mapDescriptorToSetDependents.put( callee, deps );
1452     }
1453     return deps;
1454   }
1455
1456
1457   public Hashtable<FlatCall, ReachGraph> getIHMcontributions( Descriptor d ) {
1458
1459     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1460       mapDescriptorToIHMcontributions.get( d );
1461
1462     if( heapsFromCallers == null ) {
1463       heapsFromCallers = new Hashtable<FlatCall, ReachGraph>();
1464       mapDescriptorToIHMcontributions.put( d, heapsFromCallers );
1465     }
1466
1467     return heapsFromCallers;
1468   }
1469
1470   public ReachGraph getIHMcontribution( Descriptor d,
1471                                         FlatCall   fc
1472                                         ) {
1473     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1474       getIHMcontributions( d );
1475
1476     if( !heapsFromCallers.containsKey( fc ) ) {
1477       heapsFromCallers.put( fc, new ReachGraph() );
1478     }
1479
1480     return heapsFromCallers.get( fc );
1481   }
1482
1483   public void addIHMcontribution( Descriptor d,
1484                                   FlatCall   fc,
1485                                   ReachGraph rg
1486                                   ) {
1487     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1488       getIHMcontributions( d );
1489
1490     heapsFromCallers.put( fc, rg );
1491   }
1492
1493 private AllocSite createParameterAllocSite(ReachGraph rg, TempDescriptor tempDesc) {
1494
1495     // create temp descriptor for each parameter variable
1496     FlatNew flatNew = new FlatNew(tempDesc.getType(), tempDesc, false);
1497     // create allocation site
1498     AllocSite as = (AllocSite) Canonical.makeCanonical(new AllocSite( allocationDepth, flatNew, flatNew.getDisjointId()));
1499     for (int i = 0; i < allocationDepth; ++i) {
1500         Integer id = generateUniqueHeapRegionNodeID();
1501         as.setIthOldest(i, id);
1502         mapHrnIdToAllocSite.put(id, as);
1503     }
1504     // the oldest node is a summary node
1505     as.setSummary( generateUniqueHeapRegionNodeID() );
1506
1507     rg.age(as);
1508
1509     return as;
1510
1511 }
1512
1513 private ReachGraph createInitialTaskReachGraph(FlatMethod fm) {
1514     ReachGraph rg = new ReachGraph();
1515     TaskDescriptor taskDesc = fm.getTask();
1516
1517     for (int idx = 0; idx < taskDesc.numParameters(); idx++) {
1518         Descriptor paramDesc = taskDesc.getParameter(idx);
1519         TypeDescriptor paramTypeDesc = taskDesc.getParamType(idx);
1520
1521         // setup data structure
1522         Set<HashMap<HeapRegionNode, FieldDescriptor>> workSet =
1523             new HashSet<HashMap<HeapRegionNode, FieldDescriptor>>();
1524         Hashtable<TypeDescriptor, HeapRegionNode> mapTypeToExistingSummaryNode =
1525             new Hashtable<TypeDescriptor, HeapRegionNode>();
1526         Set<String> doneSet = new HashSet<String>();
1527
1528         TempDescriptor tempDesc = fm.getParameter(idx);
1529
1530         AllocSite as = createParameterAllocSite(rg, tempDesc);
1531         VariableNode lnX = rg.getVariableNodeFromTemp(tempDesc);
1532         Integer idNewest = as.getIthOldest(0);
1533         HeapRegionNode hrnNewest = rg.id2hrn.get(idNewest);
1534         // make a new reference to allocated node
1535         RefEdge edgeNew = new RefEdge(lnX, // source
1536                                       hrnNewest, // dest
1537                                       taskDesc.getParamType(idx), // type
1538                                       null, // field name
1539                                       hrnNewest.getAlpha(), // beta
1540                                       ExistPredSet.factory(rg.predTrue) // predicates
1541                                       );
1542         rg.addRefEdge(lnX, hrnNewest, edgeNew);
1543
1544         // set-up a work set for class field
1545         ClassDescriptor classDesc = paramTypeDesc.getClassDesc();
1546         for (Iterator it = classDesc.getFields(); it.hasNext();) {
1547             FieldDescriptor fd = (FieldDescriptor) it.next();
1548             TypeDescriptor fieldType = fd.getType();
1549             if (!fieldType.isImmutable() || fieldType.isArray()) {
1550                 HashMap<HeapRegionNode, FieldDescriptor> newMap = new HashMap<HeapRegionNode, FieldDescriptor>();
1551                 newMap.put(hrnNewest, fd);
1552                 workSet.add(newMap);
1553             }
1554         }
1555
1556         int uniqueIdentifier = 0;
1557         while (!workSet.isEmpty()) {
1558             HashMap<HeapRegionNode, FieldDescriptor> map = workSet
1559                 .iterator().next();
1560             workSet.remove(map);
1561
1562             Set<HeapRegionNode> key = map.keySet();
1563             HeapRegionNode srcHRN = key.iterator().next();
1564             FieldDescriptor fd = map.get(srcHRN);
1565             TypeDescriptor type = fd.getType();
1566             String doneSetIdentifier = srcHRN.getIDString() + "_" + fd;
1567
1568             if (!doneSet.contains(doneSetIdentifier)) {
1569                 doneSet.add(doneSetIdentifier);
1570                 if (!mapTypeToExistingSummaryNode.containsKey(type)) {
1571                     // create new summary Node
1572                     TempDescriptor td = new TempDescriptor("temp"
1573                                                            + uniqueIdentifier, type);
1574
1575                     AllocSite allocSite;
1576                     if(type.equals(paramTypeDesc)){
1577                     //corresponding allocsite has already been created for a parameter variable.
1578                         allocSite=as;
1579                     }else{
1580                         allocSite = createParameterAllocSite(rg, td);
1581                     }
1582                     String strDesc = allocSite.toStringForDOT()
1583                         + "\\nsummary";
1584                     HeapRegionNode hrnSummary =
1585                         rg.createNewHeapRegionNode(allocSite.getSummary(), // id or null to generate a new one
1586                                                    false, // single object?
1587                                                    true, // summary?
1588                                                    false, // flagged?
1589                                                    false, // out-of-context?
1590                                                    allocSite.getType(), // type
1591                                                    allocSite, // allocation site
1592                                                    null, // inherent reach
1593                                                    srcHRN.getAlpha(), // current reach
1594                                                    ExistPredSet.factory(), // predicates
1595                                                    strDesc // description
1596                                                    );
1597                     rg.id2hrn.put(allocSite.getSummary(),hrnSummary);
1598
1599                     // make a new reference to summary node
1600                     RefEdge edgeToSummary = new RefEdge(srcHRN, // source
1601                                                         hrnSummary, // dest
1602                                                         fd.getType(), // type
1603                                                         fd.getSymbol(), // field name
1604                                                         srcHRN.getAlpha(), // beta
1605                                                         ExistPredSet.factory(rg.predTrue) // predicates
1606                                                         );
1607
1608                     rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary);
1609
1610                     uniqueIdentifier++;
1611
1612                     mapTypeToExistingSummaryNode.put(type, hrnSummary);
1613
1614                     // set-up a work set for  fields of the class
1615                     if(!type.isImmutable()){
1616                     classDesc = type.getClassDesc();
1617                     for (Iterator it = classDesc.getFields(); it.hasNext();) {
1618                         FieldDescriptor typeFieldDesc = (FieldDescriptor) it.next();
1619                         TypeDescriptor fieldType = typeFieldDesc.getType();
1620                         if (!fieldType.isImmutable()) {
1621                             doneSetIdentifier = hrnSummary.getIDString() + "_" + typeFieldDesc;
1622                             if(!doneSet.contains(doneSetIdentifier)){
1623                                 // add new work item
1624                                 HashMap<HeapRegionNode, FieldDescriptor> newMap =
1625                                     new HashMap<HeapRegionNode, FieldDescriptor>();
1626                                 newMap.put(hrnSummary, typeFieldDesc);
1627                                 workSet.add(newMap);
1628                             }
1629                         }
1630                     }
1631                     }
1632
1633                 }else{
1634                     // if there exists corresponding summary node
1635                     HeapRegionNode hrnDst=mapTypeToExistingSummaryNode.get(type);
1636
1637                     RefEdge edgeToSummary = new RefEdge(srcHRN, // source
1638                                                         hrnDst, // dest
1639                                                         fd.getType(), // type
1640                                                         fd.getSymbol(), // field name
1641                                                         srcHRN.getAlpha(), // beta
1642                                                         ExistPredSet.factory(rg.predTrue) // predicates
1643                                                         );
1644                     rg.addRefEdge(srcHRN, hrnDst, edgeToSummary);
1645
1646                 }
1647             }
1648         }
1649     }
1650 //    debugSnapshot(rg, fm, true);
1651     return rg;
1652 }
1653
1654 // return all allocation sites in the method (there is one allocation
1655 // site per FlatNew node in a method)
1656 private HashSet<AllocSite> getAllocationSiteSet(Descriptor d) {
1657   if( !mapDescriptorToAllocSiteSet.containsKey(d) ) {
1658     buildAllocationSiteSet(d);
1659   }
1660
1661   return mapDescriptorToAllocSiteSet.get(d);
1662
1663 }
1664
1665 private void buildAllocationSiteSet(Descriptor d) {
1666     HashSet<AllocSite> s = new HashSet<AllocSite>();
1667
1668     FlatMethod fm;
1669     if( d instanceof MethodDescriptor ) {
1670       fm = state.getMethodFlat( (MethodDescriptor) d);
1671     } else {
1672       assert d instanceof TaskDescriptor;
1673       fm = state.getMethodFlat( (TaskDescriptor) d);
1674     }
1675
1676     // visit every node in this FlatMethod's IR graph
1677     // and make a set of the allocation sites from the
1678     // FlatNew node's visited
1679     HashSet<FlatNode> visited = new HashSet<FlatNode>();
1680     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1681     toVisit.add(fm);
1682
1683     while( !toVisit.isEmpty() ) {
1684       FlatNode n = toVisit.iterator().next();
1685
1686       if( n instanceof FlatNew ) {
1687         s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) );
1688       }
1689
1690       toVisit.remove(n);
1691       visited.add(n);
1692
1693       for( int i = 0; i < n.numNext(); ++i ) {
1694         FlatNode child = n.getNext(i);
1695         if( !visited.contains(child) ) {
1696           toVisit.add(child);
1697         }
1698       }
1699     }
1700
1701     mapDescriptorToAllocSiteSet.put(d, s);
1702   }
1703
1704         private HashSet<AllocSite> getFlaggedAllocationSites(Descriptor dIn) {
1705
1706                 HashSet<AllocSite> out = new HashSet<AllocSite>();
1707                 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
1708                 HashSet<Descriptor> visited = new HashSet<Descriptor>();
1709
1710                 toVisit.add(dIn);
1711
1712                 while (!toVisit.isEmpty()) {
1713                         Descriptor d = toVisit.iterator().next();
1714                         toVisit.remove(d);
1715                         visited.add(d);
1716
1717                         HashSet<AllocSite> asSet = getAllocationSiteSet(d);
1718                         Iterator asItr = asSet.iterator();
1719                         while (asItr.hasNext()) {
1720                                 AllocSite as = (AllocSite) asItr.next();
1721                                 if (as.getDisjointAnalysisId() != null) {
1722                                         out.add(as);
1723                                 }
1724                         }
1725
1726                         // enqueue callees of this method to be searched for
1727                         // allocation sites also
1728                         Set callees = callGraph.getCalleeSet(d);
1729                         if (callees != null) {
1730                                 Iterator methItr = callees.iterator();
1731                                 while (methItr.hasNext()) {
1732                                         MethodDescriptor md = (MethodDescriptor) methItr.next();
1733
1734                                         if (!visited.contains(md)) {
1735                                                 toVisit.add(md);
1736                                         }
1737                                 }
1738                         }
1739                 }
1740
1741                 return out;
1742         }
1743
1744
1745 private HashSet<AllocSite>
1746 getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1747
1748   HashSet<AllocSite> asSetTotal = new HashSet<AllocSite>();
1749   HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1750   HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1751
1752   toVisit.add(td);
1753
1754   // traverse this task and all methods reachable from this task
1755   while( !toVisit.isEmpty() ) {
1756     Descriptor d = toVisit.iterator().next();
1757     toVisit.remove(d);
1758     visited.add(d);
1759
1760     HashSet<AllocSite> asSet = getAllocationSiteSet(d);
1761     Iterator asItr = asSet.iterator();
1762     while( asItr.hasNext() ) {
1763         AllocSite as = (AllocSite) asItr.next();
1764         TypeDescriptor typed = as.getType();
1765         if( typed != null ) {
1766           ClassDescriptor cd = typed.getClassDesc();
1767           if( cd != null && cd.hasFlags() ) {
1768             asSetTotal.add(as);
1769           }
1770         }
1771     }
1772
1773     // enqueue callees of this method to be searched for
1774     // allocation sites also
1775     Set callees = callGraph.getCalleeSet(d);
1776     if( callees != null ) {
1777         Iterator methItr = callees.iterator();
1778         while( methItr.hasNext() ) {
1779           MethodDescriptor md = (MethodDescriptor) methItr.next();
1780
1781           if( !visited.contains(md) ) {
1782             toVisit.add(md);
1783           }
1784         }
1785     }
1786   }
1787
1788   return asSetTotal;
1789 }
1790
1791
1792   int zzz = 0;
1793
1794
1795
1796
1797   // get successive captures of the analysis state
1798   boolean takeDebugSnapshots = false;
1799   String descSymbolDebug = "main";
1800   boolean stopAfterCapture = true;
1801
1802   // increments every visit to debugSnapshot, don't fiddle with it
1803   int debugCounter = 0;
1804
1805   // the value of debugCounter to start reporting the debugCounter
1806   // to the screen to let user know what debug iteration we're at
1807   int numStartCountReport = 0;
1808
1809   // the frequency of debugCounter values to print out, 0 no report
1810   int freqCountReport = 0;
1811
1812   // the debugCounter value at which to start taking snapshots
1813   int iterStartCapture = 0;
1814
1815   // the number of snapshots to take
1816   int numIterToCapture = 300;
1817
1818   void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) {
1819     if( debugCounter > iterStartCapture + numIterToCapture ) {
1820       return;
1821     }
1822
1823     if( in ) {
1824       ++debugCounter;
1825     }
1826
1827     if( debugCounter    > numStartCountReport &&
1828         freqCountReport > 0                   &&
1829         debugCounter % freqCountReport == 0
1830         ) {
1831       System.out.println( "    @@@ debug counter = "+
1832                           debugCounter );
1833     }
1834
1835     if( debugCounter > iterStartCapture ) {
1836       System.out.println( "    @@@ capturing debug "+
1837                           (debugCounter - iterStartCapture)+
1838                           " @@@" );
1839       String graphName;
1840       if( in ) {
1841         graphName = String.format( "snap%04din",
1842                                    debugCounter - iterStartCapture );
1843       } else {
1844         graphName = String.format( "snap%04dout",
1845                                    debugCounter - iterStartCapture );
1846       }
1847       if( fn != null ) {
1848         graphName = graphName + fn;
1849       }
1850       try {
1851         rg.writeGraph( graphName,
1852                        true,  // write labels (variables)
1853                        true,  // selectively hide intermediate temp vars
1854                        true,  // prune unreachable heap regions
1855                        false, // hide subset reachability states
1856                        true );// hide edge taints
1857       } catch( Exception e ) {
1858         System.out.println( "Error writing debug capture." );
1859         System.exit( 0 );
1860       }
1861     }
1862
1863     if( debugCounter == iterStartCapture + numIterToCapture &&
1864         stopAfterCapture
1865         ) {
1866       System.out.println( "Stopping analysis after debug captures." );
1867       System.exit( 0 );
1868     }
1869   }
1870
1871 }