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   // data from the compiler
  17   public State            state;
  18   public CallGraph        callGraph;
  19   public Liveness         liveness;
  20   public ArrayReferencees arrayReferencees;
  21   public TypeUtil         typeUtil;
  22   public int              allocationDepth;
  23
  24
  25   // used to identify HeapRegionNode objects
  26   // A unique ID equates an object in one
  27   // ownership graph with an object in another
  28   // graph that logically represents the same
  29   // heap region
  30   // start at 10 and increment to reserve some
  31   // IDs for special purposes
  32   static protected int uniqueIDcount = 10;
  33
  34
  35   // An out-of-scope method created by the
  36   // analysis that has no parameters, and
  37   // appears to allocate the command line
  38   // arguments, then invoke the source code's
  39   // main method.  The purpose of this is to
  40   // provide the analysis with an explicit
  41   // top-level context with no parameters
  42   protected MethodDescriptor mdAnalysisEntry;
  43   protected FlatMethod       fmAnalysisEntry;
  44
  45   // main method defined by source program
  46   protected MethodDescriptor mdSourceEntry;
  47
  48   // the set of task and/or method descriptors
  49   // reachable in call graph
  50   protected Set<Descriptor>
  51     descriptorsToAnalyze;
  52
  53   // current descriptors to visit in fixed-point
  54   // interprocedural analysis, prioritized by
  55   // dependency in the call graph
  56   protected PriorityQueue<DescriptorQWrapper>
  57     descriptorsToVisitQ;
  58
  59   // a duplication of the above structure, but
  60   // for efficient testing of inclusion
  61   protected HashSet<Descriptor>
  62     descriptorsToVisitSet;
  63
  64   // storage for priorities (doesn't make sense)
  65   // to add it to the Descriptor class, just in
  66   // this analysis
  67   protected Hashtable<Descriptor, Integer>
  68     mapDescriptorToPriority;
  69
  70
  71   // maps a descriptor to its current partial result
  72   // from the intraprocedural fixed-point analysis--
  73   // then the interprocedural analysis settles, this
  74   // mapping will have the final results for each
  75   // method descriptor
  76   protected Hashtable<Descriptor, ReachGraph>
  77     mapDescriptorToCompleteReachGraph;
  78
  79   // maps a descriptor to its known dependents: namely
  80   // methods or tasks that call the descriptor's method
  81   // AND are part of this analysis (reachable from main)
  82   protected Hashtable< Descriptor, Set<Descriptor> >
  83     mapDescriptorToSetDependents;
  84
  85   // maps each flat new to one analysis abstraction
  86   // allocate site object, these exist outside reach graphs
  87   protected Hashtable<FlatNew, AllocSite>
  88     mapFlatNewToAllocSite;
  89
  90   // maps intergraph heap region IDs to intergraph
  91   // allocation sites that created them, a redundant
  92   // structure for efficiency in some operations
  93   protected Hashtable<Integer, AllocSite>
  94     mapHrnIdToAllocSite;
  95
  96   // maps a method to its initial heap model (IHM) that
  97   // is the set of reachability graphs from every caller
  98   // site, all merged together.  The reason that we keep
  99   // them separate is that any one call site's contribution
 100   // to the IHM may changed along the path to the fixed point
 101   protected Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >
 102     mapDescriptorToIHMcontributions;
 103
 104   // TODO -- CHANGE EDGE/TYPE/FIELD storage!
 105   public static final String arrayElementFieldName = "___element_";
 106   static protected Hashtable<TypeDescriptor, FieldDescriptor>
 107     mapTypeToArrayField;
 108
 109   // for controlling DOT file output
 110   protected boolean writeFinalDOTs;
 111   protected boolean writeAllIncrementalDOTs;
 112
 113   // supporting DOT output--when we want to write every
 114   // partial method result, keep a tally for generating
 115   // unique filenames
 116   protected Hashtable<Descriptor, Integer>
 117     mapDescriptorToNumUpdates;
 118
 119
 120   // allocate various structures that are not local
 121   // to a single class method--should be done once
 122   protected void allocateStructures() {
 123     descriptorsToAnalyze = new HashSet<Descriptor>();
 124
 125     mapDescriptorToCompleteReachGraph =
 126       new Hashtable<Descriptor, ReachGraph>();
 127
 128     mapDescriptorToNumUpdates =
 129       new Hashtable<Descriptor, Integer>();
 130
 131     mapDescriptorToSetDependents =
 132       new Hashtable< Descriptor, Set<Descriptor> >();
 133
 134     mapFlatNewToAllocSite =
 135       new Hashtable<FlatNew, AllocSite>();
 136
 137     mapDescriptorToIHMcontributions =
 138       new Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >();
 139
 140     mapHrnIdToAllocSite =
 141       new Hashtable<Integer, AllocSite>();
 142
 143     mapTypeToArrayField =
 144       new Hashtable <TypeDescriptor, FieldDescriptor>();
 145
 146     descriptorsToVisitQ =
 147       new PriorityQueue<DescriptorQWrapper>();
 148
 149     descriptorsToVisitSet =
 150       new HashSet<Descriptor>();
 151
 152     mapDescriptorToPriority =
 153       new Hashtable<Descriptor, Integer>();
 154   }
 155
 156
 157
 158   // this analysis generates a disjoint reachability
 159   // graph for every reachable method in the program
 160   public DisjointAnalysis( State s,
 161                            TypeUtil tu,
 162                            CallGraph cg,
 163                            Liveness l,
 164                            ArrayReferencees ar
 165                            ) throws java.io.IOException {
 166     init( s, tu, cg, l, ar );
 167   }
 168
 169   protected void init( State state,
 170                        TypeUtil typeUtil,
 171                        CallGraph callGraph,
 172                        Liveness liveness,
 173                        ArrayReferencees arrayReferencees
 174                        ) throws java.io.IOException {
 175
 176     this.state                   = state;
 177     this.typeUtil                = typeUtil;
 178     this.callGraph               = callGraph;
 179     this.liveness                = liveness;
 180     this.arrayReferencees        = arrayReferencees;
 181     this.allocationDepth         = state.DISJOINTALLOCDEPTH;
 182     this.writeFinalDOTs          = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL;
 183     this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS &&  state.DISJOINTWRITEALL;
 184
 185     // set some static configuration for ReachGraphs
 186     ReachGraph.allocationDepth = allocationDepth;
 187     ReachGraph.typeUtil        = typeUtil;
 188
 189     allocateStructures();
 190
 191     double timeStartAnalysis = (double) System.nanoTime();
 192
 193     // start interprocedural fixed-point computation
 194     analyzeMethods();
 195
 196     double timeEndAnalysis = (double) System.nanoTime();
 197     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 198     String treport = String.format( "The reachability analysis took %.3f sec.", dt );
 199     String justtime = String.format( "%.2f", dt );
 200     System.out.println( treport );
 201
 202     if( writeFinalDOTs && !writeAllIncrementalDOTs ) {
 203       writeFinalGraphs();
 204     }
 205
 206     if( state.DISJOINTALIASFILE != null ) {
 207       if( state.TASK ) {
 208         // not supporting tasks yet...
 209       } else {
 210         /*
 211         writeAllAliasesJava( aliasFile,
 212                              treport,
 213                              justtime,
 214                              state.DISJOINTALIASTAB,
 215                              state.lines );
 216         */
 217       }
 218     }
 219   }
 220
 221
 222   // fixed-point computation over the call graph--when a
 223   // method's callees are updated, it must be reanalyzed
 224   protected void analyzeMethods() throws java.io.IOException {
 225
 226     if( state.TASK ) {
 227       // This analysis does not support Bamboo at the moment,
 228       // but if it does in the future we would initialize the
 229       // set of descriptors to analyze as the program-reachable
 230       // tasks and the methods callable by them.  For Java,
 231       // just methods reachable from the main method.
 232       System.out.println( "No Bamboo support yet..." );
 233       System.exit( -1 );
 234
 235     } else {
 236       // add all methods transitively reachable from the
 237       // source's main to set for analysis
 238       mdSourceEntry = typeUtil.getMain();
 239       descriptorsToAnalyze.add( mdSourceEntry );
 240       descriptorsToAnalyze.addAll(
 241         callGraph.getAllMethods( mdSourceEntry )
 242                                    );
 243
 244       // fabricate an empty calling context that will call
 245       // the source's main, but call graph doesn't know
 246       // about it, so explicitly add it
 247       makeAnalysisEntryMethod( mdSourceEntry );
 248       descriptorsToAnalyze.add( mdAnalysisEntry );
 249     }
 250
 251     // topologically sort according to the call graph so
 252     // leaf calls are ordered first, smarter analysis order
 253     LinkedList<Descriptor> sortedDescriptors =
 254       topologicalSort( descriptorsToAnalyze );
 255
 256     // add sorted descriptors to priority queue, and duplicate
 257     // the queue as a set for efficiently testing whether some
 258     // method is marked for analysis
 259     int p = 0;
 260     Iterator<Descriptor> dItr = sortedDescriptors.iterator();
 261     while( dItr.hasNext() ) {
 262       Descriptor d = dItr.next();
 263       mapDescriptorToPriority.put( d, new Integer( p ) );
 264       descriptorsToVisitQ.add( new DescriptorQWrapper( p, d ) );
 265       descriptorsToVisitSet.add( d );
 266       ++p;
 267     }
 268
 269     // analyze methods from the priority queue until it is empty
 270     while( !descriptorsToVisitQ.isEmpty() ) {
 271       Descriptor d = descriptorsToVisitQ.poll().getDescriptor();
 272       assert descriptorsToVisitSet.contains( d );
 273       descriptorsToVisitSet.remove( d );
 274
 275       // because the task or method descriptor just extracted
 276       // was in the "to visit" set it either hasn't been analyzed
 277       // yet, or some method that it depends on has been
 278       // updated.  Recompute a complete reachability graph for
 279       // this task/method and compare it to any previous result.
 280       // If there is a change detected, add any methods/tasks
 281       // that depend on this one to the "to visit" set.
 282
 283       System.out.println( "Analyzing " + d );
 284
 285       ReachGraph rg     = analyzeMethod( d );
 286       ReachGraph rgPrev = getPartial( d );
 287
 288       if( !rg.equals( rgPrev ) ) {
 289         setPartial( d, rg );
 290
 291         // results for d changed, so queue dependents
 292         // of d for further analysis
 293         Iterator<Descriptor> depsItr = getDependents( d ).iterator();
 294         while( depsItr.hasNext() ) {
 295           Descriptor dNext = depsItr.next();
 296
 297           if( !descriptorsToVisitSet.contains( dNext ) ) {
 298             Integer priority = mapDescriptorToPriority.get( dNext );
 299             descriptorsToVisitQ.add( new DescriptorQWrapper( priority ,
 300                                                              dNext )
 301                                      );
 302             descriptorsToVisitSet.add( dNext );
 303           }
 304         }
 305       }
 306     }
 307   }
 308
 309
 310   protected ReachGraph analyzeMethod( Descriptor d )
 311     throws java.io.IOException {
 312
 313     // get the flat code for this descriptor
 314     FlatMethod fm;
 315     if( d == mdAnalysisEntry ) {
 316       fm = fmAnalysisEntry;
 317     } else {
 318       fm = state.getMethodFlat( d );
 319     }
 320
 321     // intraprocedural work set
 322     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 323     flatNodesToVisit.add( fm );
 324
 325     // mapping of current partial results
 326     Hashtable<FlatNode, ReachGraph> mapFlatNodeToReachGraph =
 327       new Hashtable<FlatNode, ReachGraph>();
 328
 329     // the set of return nodes partial results that will be combined as
 330     // the final, conservative approximation of the entire method
 331     HashSet<FlatReturnNode> setReturns = new HashSet<FlatReturnNode>();
 332
 333     while( !flatNodesToVisit.isEmpty() ) {
 334       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 335       flatNodesToVisit.remove( fn );
 336
 337       //System.out.println( "  "+fn );
 338
 339       // effect transfer function defined by this node,
 340       // then compare it to the old graph at this node
 341       // to see if anything was updated.
 342
 343       ReachGraph rg = new ReachGraph();
 344
 345       // start by merging all node's parents' graphs
 346       for( int i = 0; i < fn.numPrev(); ++i ) {
 347         FlatNode pn = fn.getPrev( i );
 348         if( mapFlatNodeToReachGraph.containsKey( pn ) ) {
 349           ReachGraph rgParent = mapFlatNodeToReachGraph.get( pn );
 350           rg.merge( rgParent );
 351         }
 352       }
 353
 354       // modify rg with appropriate transfer function
 355       analyzeFlatNode( d, fm, fn, setReturns, rg );
 356
 357       /*
 358       if( takeDebugSnapshots &&
 359           d.getSymbol().equals( descSymbolDebug ) ) {
 360         debugSnapshot(og,fn);
 361       }
 362       */
 363
 364       // if the results of the new graph are different from
 365       // the current graph at this node, replace the graph
 366       // with the update and enqueue the children
 367       ReachGraph rgPrev = mapFlatNodeToReachGraph.get( fn );
 368       if( !rg.equals( rgPrev ) ) {
 369         mapFlatNodeToReachGraph.put( fn, rg );
 370
 371         for( int i = 0; i < fn.numNext(); i++ ) {
 372           FlatNode nn = fn.getNext( i );
 373           flatNodesToVisit.add( nn );
 374         }
 375       }
 376     }
 377
 378     // end by merging all return nodes into a complete
 379     // ownership graph that represents all possible heap
 380     // states after the flat method returns
 381     ReachGraph completeGraph = new ReachGraph();
 382
 383     assert !setReturns.isEmpty();
 384     Iterator retItr = setReturns.iterator();
 385     while( retItr.hasNext() ) {
 386       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 387
 388       assert mapFlatNodeToReachGraph.containsKey( frn );
 389       ReachGraph rgRet = mapFlatNodeToReachGraph.get( frn );
 390
 391       completeGraph.merge( rgRet );
 392     }
 393
 394     return completeGraph;
 395   }
 396
 397
 398   protected void
 399     analyzeFlatNode( Descriptor              d,
 400                      FlatMethod              fmContaining,
 401                      FlatNode                fn,
 402                      HashSet<FlatReturnNode> setRetNodes,
 403                      ReachGraph              rg
 404                      ) throws java.io.IOException {
 405
 406
 407     // any variables that are no longer live should be
 408     // nullified in the graph to reduce edges
 409     // NOTE: it is not clear we need this.  It costs a
 410     // liveness calculation for every method, so only
 411     // turn it on if we find we actually need it.
 412     // rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) );
 413
 414
 415     TempDescriptor  lhs;
 416     TempDescriptor  rhs;
 417     FieldDescriptor fld;
 418
 419     // use node type to decide what transfer function
 420     // to apply to the reachability graph
 421     switch( fn.kind() ) {
 422
 423     case FKind.FlatMethod: {
 424       // construct this method's initial heap model (IHM)
 425       // since we're working on the FlatMethod, we know
 426       // the incoming ReachGraph 'rg' is empty
 427
 428       Hashtable<FlatCall, ReachGraph> heapsFromCallers =
 429         getIHMcontributions( d );
 430
 431       Set entrySet = heapsFromCallers.entrySet();
 432       Iterator itr = entrySet.iterator();
 433       while( itr.hasNext() ) {
 434         Map.Entry  me        = (Map.Entry)  itr.next();
 435         FlatCall   fc        = (FlatCall)   me.getKey();
 436         ReachGraph rgContrib = (ReachGraph) me.getValue();
 437
 438         assert fc.getMethod().equals( d );
 439
 440         // some call sites are in same method context though,
 441         // and all of them should be merged together first,
 442         // then heaps from different contexts should be merged
 443         // THIS ASSUMES DIFFERENT CONTEXTS NEED SPECIAL CONSIDERATION!
 444         // such as, do allocation sites need to be aged?
 445
 446         rg.merge_diffMethodContext( rgContrib );
 447       }
 448
 449       FlatMethod fm = (FlatMethod) fn;
 450       for( int i = 0; i < fm.numParameters(); ++i ) {
 451         TempDescriptor tdParam = fm.getParameter( i );
 452         //assert rg.hasVariable( tdParam );
 453       }
 454     } break;
 455
 456     case FKind.FlatOpNode:
 457       FlatOpNode fon = (FlatOpNode) fn;
 458       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 459         lhs = fon.getDest();
 460         rhs = fon.getLeft();
 461         rg.assignTempXEqualToTempY( lhs, rhs );
 462       }
 463       break;
 464
 465     case FKind.FlatCastNode:
 466       FlatCastNode fcn = (FlatCastNode) fn;
 467       lhs = fcn.getDst();
 468       rhs = fcn.getSrc();
 469
 470       TypeDescriptor td = fcn.getType();
 471       assert td != null;
 472
 473       rg.assignTempXEqualToCastedTempY( lhs, rhs, td );
 474       break;
 475
 476     case FKind.FlatFieldNode:
 477       FlatFieldNode ffn = (FlatFieldNode) fn;
 478       lhs = ffn.getDst();
 479       rhs = ffn.getSrc();
 480       fld = ffn.getField();
 481       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 482         rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld );
 483       }
 484       break;
 485
 486     case FKind.FlatSetFieldNode:
 487       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 488       lhs = fsfn.getDst();
 489       fld = fsfn.getField();
 490       rhs = fsfn.getSrc();
 491       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 492         rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs );
 493       }
 494       break;
 495
 496     case FKind.FlatElementNode:
 497       FlatElementNode fen = (FlatElementNode) fn;
 498       lhs = fen.getDst();
 499       rhs = fen.getSrc();
 500       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 501
 502         assert rhs.getType() != null;
 503         assert rhs.getType().isArray();
 504
 505         TypeDescriptor  tdElement = rhs.getType().dereference();
 506         FieldDescriptor fdElement = getArrayField( tdElement );
 507
 508         rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement );
 509       }
 510       break;
 511
 512     case FKind.FlatSetElementNode:
 513       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 514
 515       if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) {
 516         // skip this node if it cannot create new reachability paths
 517         break;
 518       }
 519
 520       lhs = fsen.getDst();
 521       rhs = fsen.getSrc();
 522       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 523
 524         assert lhs.getType() != null;
 525         assert lhs.getType().isArray();
 526
 527         TypeDescriptor  tdElement = lhs.getType().dereference();
 528         FieldDescriptor fdElement = getArrayField( tdElement );
 529
 530         rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs );
 531       }
 532       break;
 533
 534     case FKind.FlatNew:
 535       FlatNew fnn = (FlatNew) fn;
 536       lhs = fnn.getDst();
 537       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 538         AllocSite as = getAllocSiteFromFlatNewPRIVATE( fnn );
 539         rg.assignTempEqualToNewAlloc( lhs, as );
 540       }
 541       break;
 542
 543     case FKind.FlatCall: {
 544       FlatCall         fc       = (FlatCall) fn;
 545       MethodDescriptor mdCallee = fc.getMethod();
 546       FlatMethod       fmCallee = state.getMethodFlat( mdCallee );
 547
 548       ReachGraph heapForThisCall_old =
 549         getIHMcontribution( mdCallee, fc );
 550
 551       ReachGraph heapForThisCall_cur = rg.makeCalleeView( fc,
 552                                                           fmCallee );
 553
 554       if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) {
 555         // if heap at call site changed, update the contribution,
 556         //  and reschedule the callee for analysis
 557         addIHMcontribution( mdCallee, fc, heapForThisCall_cur );
 558
 559         if( !descriptorsToVisitSet.contains( mdCallee ) ) {
 560           Integer priority = mapDescriptorToPriority.get( mdCallee );
 561           descriptorsToVisitQ.add( new DescriptorQWrapper( priority,
 562                                                            mdCallee )
 563                                    );
 564           descriptorsToVisitSet.add( mdCallee );
 565         }
 566       }
 567
 568       // now that we've got that taken care of, go ahead and update
 569       // the reach graph for this FlatCall node by whatever callee
 570       // result we do have
 571
 572
 573       /*
 574       ReachGraph ogMergeOfAllPossibleCalleeResults = new ReachGraph();
 575
 576       if( md.isStatic() ) {
 577         // a static method is simply always the same, makes life easy
 578         ogMergeOfAllPossibleCalleeResults = og;
 579
 580         Set<Integer> aliasedParamIndices =
 581           ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
 582
 583         Descriptor mcNew = new Descriptor( md, aliasedParamIndices );
 584         Set contexts = mapDescriptorToAllDescriptors.get( md );
 585         assert contexts != null;
 586         contexts.add( mcNew );
 587
 588         addDependent( mc, mcNew );
 589
 590         ReachGraph onlyPossibleCallee = mapDescriptorToCompleteReachabilityGraph.get( mcNew );
 591
 592         if( onlyPossibleCallee == null ) {
 593           // if this method context has never been analyzed just schedule it for analysis
 594           // and skip over this call site for now
 595           if( !methodContextsToVisitSet.contains( mcNew ) ) {
 596             methodContextsToVisitQ.add( new DescriptorQWrapper( mapDescriptorToPriority.get( md ),
 597                                                                    mcNew ) );
 598             methodContextsToVisitSet.add( mcNew );
 599           }
 600
 601         } else {
 602           ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc, null);
 603         }
 604
 605         meAnalysis.createNewMapping(mcNew);
 606         meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
 607
 608
 609       } else {
 610         // if the method descriptor is virtual, then there could be a
 611         // set of possible methods that will actually be invoked, so
 612         // find all of them and merge all of their results together
 613         TypeDescriptor typeDesc = fc.getThis().getType();
 614         Set possibleCallees = callGraph.getMethods(md, typeDesc);
 615
 616         Iterator i = possibleCallees.iterator();
 617         while( i.hasNext() ) {
 618           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 619           FlatMethod pflatm = state.getMethodFlat(possibleMd);
 620
 621           // don't alter the working graph (og) until we compute a result for every
 622           // possible callee, merge them all together, then set og to that
 623           ReachGraph ogCopy = new ReachGraph();
 624           ogCopy.merge(og);
 625
 626           Set<Integer> aliasedParamIndices =
 627             ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
 628
 629           Descriptor mcNew = new Descriptor( possibleMd, aliasedParamIndices );
 630           Set contexts = mapDescriptorToAllDescriptors.get( md );
 631           assert contexts != null;
 632           contexts.add( mcNew );
 633
 634
 635         meAnalysis.createNewMapping(mcNew);
 636
 637
 638           addDependent( mc, mcNew );
 639
 640           ReachGraph ogPotentialCallee = mapDescriptorToCompleteReachabilityGraph.get( mcNew );
 641
 642           if( ogPotentialCallee == null ) {
 643             // if this method context has never been analyzed just schedule it for analysis
 644             // and skip over this call site for now
 645             if( !methodContextsToVisitSet.contains( mcNew ) ) {
 646               methodContextsToVisitQ.add( new DescriptorQWrapper( mapDescriptorToPriority.get( md ),
 647                                                                      mcNew ) );
 648               methodContextsToVisitSet.add( mcNew );
 649             }
 650
 651           } else {
 652             ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc, null);
 653           }
 654
 655           ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
 656
 657           meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
 658         }
 659
 660       }
 661
 662       og = ogMergeOfAllPossibleCalleeResults;
 663       */
 664     } break;
 665
 666
 667     case FKind.FlatReturnNode:
 668       FlatReturnNode frn = (FlatReturnNode) fn;
 669       rhs = frn.getReturnTemp();
 670       if( rhs != null && !rhs.getType().isImmutable() ) {
 671         rg.assignReturnEqualToTemp( rhs );
 672       }
 673       setRetNodes.add( frn );
 674       break;
 675
 676     } // end switch
 677
 678     // at this point rg should be the correct update
 679     // by an above transfer function, or untouched if
 680     // the flat node type doesn't affect the heap
 681   }
 682
 683
 684   // this method should generate integers strictly greater than zero!
 685   // special "shadow" regions are made from a heap region by negating
 686   // the ID
 687   static public Integer generateUniqueHeapRegionNodeID() {
 688     ++uniqueIDcount;
 689     return new Integer( uniqueIDcount );
 690   }
 691
 692
 693
 694   static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
 695     FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
 696     if( fdElement == null ) {
 697       fdElement = new FieldDescriptor( new Modifiers( Modifiers.PUBLIC ),
 698                                        tdElement,
 699                                        arrayElementFieldName,
 700                                        null,
 701                                        false );
 702       mapTypeToArrayField.put( tdElement, fdElement );
 703     }
 704     return fdElement;
 705   }
 706
 707
 708
 709   private void writeFinalGraphs() {
 710     Set entrySet = mapDescriptorToCompleteReachGraph.entrySet();
 711     Iterator itr = entrySet.iterator();
 712     while( itr.hasNext() ) {
 713       Map.Entry  me = (Map.Entry)  itr.next();
 714       Descriptor  d = (Descriptor) me.getKey();
 715       ReachGraph rg = (ReachGraph) me.getValue();
 716
 717       try {
 718         rg.writeGraph( d+"COMPLETE",
 719                        true,   // write labels (variables)
 720                        true,   // selectively hide intermediate temp vars
 721                        true,   // prune unreachable heap regions
 722                        false,  // show back edges to confirm graph validity
 723                        true,   // hide subset reachability states
 724                        true ); // hide edge taints
 725       } catch( IOException e ) {}
 726     }
 727   }
 728
 729
 730   // return just the allocation site associated with one FlatNew node
 731   protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) {
 732
 733     if( !mapFlatNewToAllocSite.containsKey( fnew ) ) {
 734       AllocSite as =
 735         new AllocSite( allocationDepth, fnew, fnew.getDisjointId() );
 736
 737       // the newest nodes are single objects
 738       for( int i = 0; i < allocationDepth; ++i ) {
 739         Integer id = generateUniqueHeapRegionNodeID();
 740         as.setIthOldest( i, id );
 741         mapHrnIdToAllocSite.put( id, as );
 742       }
 743
 744       // the oldest node is a summary node
 745       Integer idSummary = generateUniqueHeapRegionNodeID();
 746       as.setSummary( idSummary );
 747
 748       mapFlatNewToAllocSite.put( fnew, as );
 749     }
 750
 751     return mapFlatNewToAllocSite.get( fnew );
 752   }
 753
 754
 755   /*
 756   // return all allocation sites in the method (there is one allocation
 757   // site per FlatNew node in a method)
 758   protected HashSet<AllocSite> getAllocSiteSet(Descriptor d) {
 759     if( !mapDescriptorToAllocSiteSet.containsKey(d) ) {
 760       buildAllocSiteSet(d);
 761     }
 762
 763     return mapDescriptorToAllocSiteSet.get(d);
 764
 765   }
 766   */
 767
 768   /*
 769   protected void buildAllocSiteSet(Descriptor d) {
 770     HashSet<AllocSite> s = new HashSet<AllocSite>();
 771
 772     FlatMethod fm = state.getMethodFlat( d );
 773
 774     // visit every node in this FlatMethod's IR graph
 775     // and make a set of the allocation sites from the
 776     // FlatNew node's visited
 777     HashSet<FlatNode> visited = new HashSet<FlatNode>();
 778     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
 779     toVisit.add( fm );
 780
 781     while( !toVisit.isEmpty() ) {
 782       FlatNode n = toVisit.iterator().next();
 783
 784       if( n instanceof FlatNew ) {
 785         s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) );
 786       }
 787
 788       toVisit.remove( n );
 789       visited.add( n );
 790
 791       for( int i = 0; i < n.numNext(); ++i ) {
 792         FlatNode child = n.getNext( i );
 793         if( !visited.contains( child ) ) {
 794           toVisit.add( child );
 795         }
 796       }
 797     }
 798
 799     mapDescriptorToAllocSiteSet.put( d, s );
 800   }
 801   */
 802   /*
 803   protected HashSet<AllocSite> getFlaggedAllocSites(Descriptor dIn) {
 804
 805     HashSet<AllocSite> out     = new HashSet<AllocSite>();
 806     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
 807     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
 808
 809     toVisit.add(dIn);
 810
 811     while( !toVisit.isEmpty() ) {
 812       Descriptor d = toVisit.iterator().next();
 813       toVisit.remove(d);
 814       visited.add(d);
 815
 816       HashSet<AllocSite> asSet = getAllocSiteSet(d);
 817       Iterator asItr = asSet.iterator();
 818       while( asItr.hasNext() ) {
 819         AllocSite as = (AllocSite) asItr.next();
 820         if( as.getDisjointAnalysisId() != null ) {
 821           out.add(as);
 822         }
 823       }
 824
 825       // enqueue callees of this method to be searched for
 826       // allocation sites also
 827       Set callees = callGraph.getCalleeSet(d);
 828       if( callees != null ) {
 829         Iterator methItr = callees.iterator();
 830         while( methItr.hasNext() ) {
 831           MethodDescriptor md = (MethodDescriptor) methItr.next();
 832
 833           if( !visited.contains(md) ) {
 834             toVisit.add(md);
 835           }
 836         }
 837       }
 838     }
 839
 840     return out;
 841   }
 842   */
 843
 844   /*
 845   protected HashSet<AllocSite>
 846   getFlaggedAllocSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
 847
 848     HashSet<AllocSite> asSetTotal = new HashSet<AllocSite>();
 849     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
 850     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
 851
 852     toVisit.add(td);
 853
 854     // traverse this task and all methods reachable from this task
 855     while( !toVisit.isEmpty() ) {
 856       Descriptor d = toVisit.iterator().next();
 857       toVisit.remove(d);
 858       visited.add(d);
 859
 860       HashSet<AllocSite> asSet = getAllocSiteSet(d);
 861       Iterator asItr = asSet.iterator();
 862       while( asItr.hasNext() ) {
 863         AllocSite as = (AllocSite) asItr.next();
 864         TypeDescriptor typed = as.getType();
 865         if( typed != null ) {
 866           ClassDescriptor cd = typed.getClassDesc();
 867           if( cd != null && cd.hasFlags() ) {
 868             asSetTotal.add(as);
 869           }
 870         }
 871       }
 872
 873       // enqueue callees of this method to be searched for
 874       // allocation sites also
 875       Set callees = callGraph.getCalleeSet(d);
 876       if( callees != null ) {
 877         Iterator methItr = callees.iterator();
 878         while( methItr.hasNext() ) {
 879           MethodDescriptor md = (MethodDescriptor) methItr.next();
 880
 881           if( !visited.contains(md) ) {
 882             toVisit.add(md);
 883           }
 884         }
 885       }
 886     }
 887
 888
 889     return asSetTotal;
 890   }
 891   */
 892
 893
 894   /*
 895   protected String computeAliasContextHistogram() {
 896
 897     Hashtable<Integer, Integer> mapNumContexts2NumDesc =
 898       new Hashtable<Integer, Integer>();
 899
 900     Iterator itr = mapDescriptorToAllDescriptors.entrySet().iterator();
 901     while( itr.hasNext() ) {
 902       Map.Entry me = (Map.Entry) itr.next();
 903       HashSet<Descriptor> s = (HashSet<Descriptor>) me.getValue();
 904
 905       Integer i = mapNumContexts2NumDesc.get( s.size() );
 906       if( i == null ) {
 907         i = new Integer( 0 );
 908       }
 909       mapNumContexts2NumDesc.put( s.size(), i + 1 );
 910     }
 911
 912     String s = "";
 913     int total = 0;
 914
 915     itr = mapNumContexts2NumDesc.entrySet().iterator();
 916     while( itr.hasNext() ) {
 917       Map.Entry me = (Map.Entry) itr.next();
 918       Integer c0 = (Integer) me.getKey();
 919       Integer d0 = (Integer) me.getValue();
 920       total += d0;
 921       s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 );
 922     }
 923
 924     s += String.format( "\n%4d total methods analayzed.\n", total );
 925
 926     return s;
 927   }
 928
 929   protected int numMethodsAnalyzed() {
 930     return descriptorsToAnalyze.size();
 931   }
 932   */
 933
 934
 935   /*
 936   // insert a call to debugSnapshot() somewhere in the analysis
 937   // to get successive captures of the analysis state
 938   boolean takeDebugSnapshots = false;
 939   String mcDescSymbolDebug = "setRoute";
 940   boolean stopAfterCapture = true;
 941
 942   // increments every visit to debugSnapshot, don't fiddle with it
 943   // IMPORTANT NOTE FOR SETTING THE FOLLOWING VALUES: this
 944   // counter increments just after every node is analyzed
 945   // from the body of the method whose symbol is specified
 946   // above.
 947   int debugCounter = 0;
 948
 949   // the value of debugCounter to start reporting the debugCounter
 950   // to the screen to let user know what debug iteration we're at
 951   int numStartCountReport = 0;
 952
 953   // the frequency of debugCounter values to print out, 0 no report
 954   int freqCountReport = 0;
 955
 956   // the debugCounter value at which to start taking snapshots
 957   int iterStartCapture = 0;
 958
 959   // the number of snapshots to take
 960   int numIterToCapture = 300;
 961
 962   void debugSnapshot(ReachabilityGraph og, FlatNode fn) {
 963     if( debugCounter > iterStartCapture + numIterToCapture ) {
 964       return;
 965     }
 966
 967     ++debugCounter;
 968     if( debugCounter > numStartCountReport &&
 969         freqCountReport > 0 &&
 970         debugCounter % freqCountReport == 0 ) {
 971       System.out.println("    @@@ debug counter = "+debugCounter);
 972     }
 973     if( debugCounter > iterStartCapture ) {
 974       System.out.println("    @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
 975       String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
 976       if( fn != null ) {
 977         graphName = graphName+fn;
 978       }
 979       try {
 980         og.writeGraph(graphName,
 981                       true,  // write labels (variables)
 982                       true,  // selectively hide intermediate temp vars
 983                       true,  // prune unreachable heap regions
 984                       false, // show back edges to confirm graph validity
 985                       false, // show parameter indices (unmaintained!)
 986                       true,  // hide subset reachability states
 987                       true); // hide edge taints
 988       } catch( Exception e ) {
 989         System.out.println("Error writing debug capture.");
 990         System.exit(0);
 991       }
 992     }
 993
 994     if( debugCounter == iterStartCapture + numIterToCapture && stopAfterCapture ) {
 995       System.out.println("Stopping analysis after debug captures.");
 996       System.exit(0);
 997     }
 998   }
 999   */
1000
1001
1002   // Take in source entry which is the program's compiled entry and
1003   // create a new analysis entry, a method that takes no parameters
1004   // and appears to allocate the command line arguments and call the
1005   // source entry with them.  The purpose of this analysis entry is
1006   // to provide a top-level method context with no parameters left.
1007   protected void makeAnalysisEntryMethod( MethodDescriptor mdSourceEntry ) {
1008
1009     Modifiers mods = new Modifiers();
1010     mods.addModifier( Modifiers.PUBLIC );
1011     mods.addModifier( Modifiers.STATIC );
1012
1013     TypeDescriptor returnType =
1014       new TypeDescriptor( TypeDescriptor.VOID );
1015
1016     this.mdAnalysisEntry =
1017       new MethodDescriptor( mods,
1018                             returnType,
1019                             "analysisEntryMethod"
1020                             );
1021
1022     TempDescriptor cmdLineArgs =
1023       new TempDescriptor( "args",
1024                           mdSourceEntry.getParamType( 0 )
1025                           );
1026
1027     FlatNew fn =
1028       new FlatNew( mdSourceEntry.getParamType( 0 ),
1029                    cmdLineArgs,
1030                    false // is global
1031                    );
1032
1033     TempDescriptor[] sourceEntryArgs = new TempDescriptor[1];
1034     sourceEntryArgs[0] = cmdLineArgs;
1035
1036     FlatCall fc =
1037       new FlatCall( mdSourceEntry,
1038                     null, // dst temp
1039                     null, // this temp
1040                     sourceEntryArgs
1041                     );
1042
1043     FlatReturnNode frn = new FlatReturnNode( null );
1044
1045     FlatExit fe = new FlatExit();
1046
1047     this.fmAnalysisEntry =
1048       new FlatMethod( mdAnalysisEntry,
1049                       fe
1050                       );
1051
1052     this.fmAnalysisEntry.addNext( fn );
1053     fn.addNext( fc );
1054     fc.addNext( frn );
1055     frn.addNext( fe );
1056   }
1057
1058
1059   protected LinkedList<Descriptor> topologicalSort( Set<Descriptor> toSort ) {
1060
1061     Set       <Descriptor> discovered = new HashSet   <Descriptor>();
1062     LinkedList<Descriptor> sorted     = new LinkedList<Descriptor>();
1063
1064     Iterator<Descriptor> itr = toSort.iterator();
1065     while( itr.hasNext() ) {
1066       Descriptor d = itr.next();
1067
1068       if( !discovered.contains( d ) ) {
1069         dfsVisit( d, toSort, sorted, discovered );
1070       }
1071     }
1072
1073     return sorted;
1074   }
1075
1076   // While we're doing DFS on call graph, remember
1077   // dependencies for efficient queuing of methods
1078   // during interprocedural analysis:
1079   //
1080   // a dependent of a method decriptor d for this analysis is:
1081   //  1) a method or task that invokes d
1082   //  2) in the descriptorsToAnalyze set
1083   protected void dfsVisit( Descriptor             d,
1084                            Set       <Descriptor> toSort,
1085                            LinkedList<Descriptor> sorted,
1086                            Set       <Descriptor> discovered ) {
1087     discovered.add( d );
1088
1089     // only methods have callers, tasks never do
1090     if( d instanceof MethodDescriptor ) {
1091
1092       MethodDescriptor md = (MethodDescriptor) d;
1093
1094       // the call graph is not aware that we have a fabricated
1095       // analysis entry that calls the program source's entry
1096       if( md == mdSourceEntry ) {
1097         if( !discovered.contains( mdAnalysisEntry ) ) {
1098           addDependent( mdSourceEntry,  // callee
1099                         mdAnalysisEntry // caller
1100                         );
1101           dfsVisit( mdAnalysisEntry, toSort, sorted, discovered );
1102         }
1103       }
1104
1105       // otherwise call graph guides DFS
1106       Iterator itr = callGraph.getCallerSet( md ).iterator();
1107       while( itr.hasNext() ) {
1108         Descriptor dCaller = (Descriptor) itr.next();
1109
1110         // only consider callers in the original set to analyze
1111         if( !toSort.contains( dCaller ) ) {
1112           continue;
1113         }
1114
1115         if( !discovered.contains( dCaller ) ) {
1116           addDependent( md,     // callee
1117                         dCaller // caller
1118                         );
1119
1120           dfsVisit( dCaller, toSort, sorted, discovered );
1121         }
1122       }
1123     }
1124
1125     sorted.addFirst( d );
1126   }
1127
1128
1129   protected ReachGraph getPartial( Descriptor d ) {
1130     return mapDescriptorToCompleteReachGraph.get( d );
1131   }
1132
1133   protected void setPartial( Descriptor d, ReachGraph rg ) {
1134     mapDescriptorToCompleteReachGraph.put( d, rg );
1135
1136     // when the flag for writing out every partial
1137     // result is set, we should spit out the graph,
1138     // but in order to give it a unique name we need
1139     // to track how many partial results for this
1140     // descriptor we've already written out
1141     if( writeAllIncrementalDOTs ) {
1142       if( !mapDescriptorToNumUpdates.containsKey( d ) ) {
1143         mapDescriptorToNumUpdates.put( d, new Integer( 0 ) );
1144       }
1145       Integer n = mapDescriptorToNumUpdates.get( d );
1146       /*
1147       try {
1148         rg.writeGraph( d+"COMPLETE"+String.format( "%05d", n ),
1149                        true,  // write labels (variables)
1150                        true,  // selectively hide intermediate temp vars
1151                        true,  // prune unreachable heap regions
1152                        false, // show back edges to confirm graph validity
1153                        false, // show parameter indices (unmaintained!)
1154                        true,  // hide subset reachability states
1155                        true); // hide edge taints
1156       } catch( IOException e ) {}
1157       */
1158       mapDescriptorToNumUpdates.put( d, n + 1 );
1159     }
1160   }
1161
1162
1163   // a dependent of a method decriptor d for this analysis is:
1164   //  1) a method or task that invokes d
1165   //  2) in the descriptorsToAnalyze set
1166   protected void addDependent( Descriptor callee, Descriptor caller ) {
1167     Set<Descriptor> deps = mapDescriptorToSetDependents.get( callee );
1168     if( deps == null ) {
1169       deps = new HashSet<Descriptor>();
1170     }
1171     deps.add( caller );
1172     mapDescriptorToSetDependents.put( callee, deps );
1173   }
1174
1175   protected Set<Descriptor> getDependents( Descriptor callee ) {
1176     Set<Descriptor> deps = mapDescriptorToSetDependents.get( callee );
1177     if( deps == null ) {
1178       deps = new HashSet<Descriptor>();
1179       mapDescriptorToSetDependents.put( callee, deps );
1180     }
1181     return deps;
1182   }
1183
1184
1185   public Hashtable<FlatCall, ReachGraph> getIHMcontributions( Descriptor d ) {
1186
1187     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1188       mapDescriptorToIHMcontributions.get( d );
1189
1190     if( heapsFromCallers == null ) {
1191       heapsFromCallers = new Hashtable<FlatCall, ReachGraph>();
1192     }
1193
1194     return heapsFromCallers;
1195   }
1196
1197   public ReachGraph getIHMcontribution( Descriptor d,
1198                                         FlatCall   fc
1199                                         ) {
1200     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1201       getIHMcontributions( d );
1202
1203     if( !heapsFromCallers.containsKey( fc ) ) {
1204       heapsFromCallers.put( fc, new ReachGraph() );
1205     }
1206
1207     return heapsFromCallers.get( fc );
1208   }
1209
1210   public void addIHMcontribution( Descriptor d,
1211                                   FlatCall   fc,
1212                                   ReachGraph rg
1213                                   ) {
1214     Hashtable<FlatCall, ReachGraph> heapsFromCallers =
1215       getIHMcontributions( d );
1216
1217     heapsFromCallers.put( fc, rg );
1218   }
1219
1220 }