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