Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import Analysis.CallGraph.*;
   4 import IR.*;
   5 import IR.Flat.*;
   6 import IR.Tree.Modifiers;
   7 import java.util.*;
   8 import java.io.*;
   9
  10
  11 public class OwnershipAnalysis {
  12
  13
  14   ///////////////////////////////////////////
  15   //
  16   //  Public interface to discover possible
  17   //  aliases in the program under analysis
  18   //
  19   ///////////////////////////////////////////
  20
  21   public HashSet<AllocationSite>
  22   getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
  23     return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
  24   }
  25
  26   public AllocationSite getAllocationSiteFromFlatNew(FlatNew fn) {
  27     return getAllocationSiteFromFlatNewPRIVATE(fn);
  28   }
  29
  30
  31   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  32                                          int paramIndex1,
  33                                          int paramIndex2) {
  34
  35     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  36     assert(og != null);
  37     return og.hasPotentialAlias(paramIndex1, paramIndex2);
  38   }
  39
  40   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  41                                          int paramIndex,
  42                                          AllocationSite alloc) {
  43
  44     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  45     assert(og != null);
  46     return og.hasPotentialAlias(paramIndex, alloc);
  47   }
  48
  49   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  50                                          AllocationSite alloc,
  51                                          int paramIndex) {
  52
  53     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  54     assert(og != null);
  55     return og.hasPotentialAlias(paramIndex, alloc);
  56   }
  57
  58   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  59                                          AllocationSite alloc1,
  60                                          AllocationSite alloc2) {
  61
  62     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  63     assert(og != null);
  64     return og.hasPotentialAlias(alloc1, alloc2);
  65   }
  66
  67
  68   protected OwnershipGraph getGraphOfAllContextsFromDescriptor(Descriptor d) {
  69     assert d != null;
  70
  71     OwnershipGraph og = new OwnershipGraph( allocationDepth, typeUtil );
  72
  73     assert mapDescriptorToAllMethodContexts.containsKey( d );
  74     HashSet<MethodContext> contexts = mapDescriptorToAllMethodContexts.get( d );
  75     Iterator<MethodContext> mcItr = contexts.iterator();
  76     while( mcItr.hasNext() ) {
  77       MethodContext mc = mcItr.next();
  78
  79       OwnershipGraph ogContext = mapMethodContextToCompleteOwnershipGraph.get(mc);
  80       assert ogContext != null;
  81
  82       og.merge( ogContext );
  83     }
  84
  85     return og;
  86   }
  87
  88
  89   // use the methods given above to check every possible alias
  90   // between task parameters and flagged allocation sites reachable
  91   // from the task
  92   public void writeAllAliases(String outputFile) throws java.io.IOException {
  93
  94     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
  95
  96     bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth);
  97
  98     // look through every task for potential aliases
  99     Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 100     while( taskItr.hasNext() ) {
 101       TaskDescriptor td = (TaskDescriptor) taskItr.next();
 102
 103       bw.write("\n---------"+td+"--------\n");
 104
 105       HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
 106
 107       // for each task parameter, check for aliases with
 108       // other task parameters and every allocation site
 109       // reachable from this task
 110       boolean foundSomeAlias = false;
 111
 112       FlatMethod fm = state.getMethodFlat(td);
 113       for( int i = 0; i < fm.numParameters(); ++i ) {
 114
 115         // for the ith parameter check for aliases to all
 116         // higher numbered parameters
 117         for( int j = i + 1; j < fm.numParameters(); ++j ) {
 118           if( createsPotentialAliases(td, i, j) ) {
 119             foundSomeAlias = true;
 120             bw.write("Potential alias between parameters "+i+" and "+j+".\n");
 121           }
 122         }
 123
 124         // for the ith parameter, check for aliases against
 125         // the set of allocation sites reachable from this
 126         // task context
 127         Iterator allocItr = allocSites.iterator();
 128         while( allocItr.hasNext() ) {
 129           AllocationSite as = (AllocationSite) allocItr.next();
 130           if( createsPotentialAliases(td, i, as) ) {
 131             foundSomeAlias = true;
 132             bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n");
 133           }
 134         }
 135       }
 136
 137       // for each allocation site check for aliases with
 138       // other allocation sites in the context of execution
 139       // of this task
 140       HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
 141       Iterator allocItr1 = allocSites.iterator();
 142       while( allocItr1.hasNext() ) {
 143         AllocationSite as1 = (AllocationSite) allocItr1.next();
 144
 145         Iterator allocItr2 = allocSites.iterator();
 146         while( allocItr2.hasNext() ) {
 147           AllocationSite as2 = (AllocationSite) allocItr2.next();
 148
 149           if( !outerChecked.contains(as2) &&
 150               createsPotentialAliases(td, as1, as2) ) {
 151             foundSomeAlias = true;
 152             bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n");
 153           }
 154         }
 155
 156         outerChecked.add(as1);
 157       }
 158
 159       if( !foundSomeAlias ) {
 160         bw.write("No aliases between flagged objects in Task "+td+".\n");
 161       }
 162     }
 163
 164     bw.close();
 165   }
 166
 167   ///////////////////////////////////////////
 168   //
 169   // end public interface
 170   //
 171   ///////////////////////////////////////////
 172
 173
 174
 175
 176
 177
 178
 179
 180   // data from the compiler
 181   private State state;
 182   private TypeUtil typeUtil;
 183   private CallGraph callGraph;
 184   private int allocationDepth;
 185
 186   // used to identify HeapRegionNode objects
 187   // A unique ID equates an object in one
 188   // ownership graph with an object in another
 189   // graph that logically represents the same
 190   // heap region
 191   // start at 10 and incerement to leave some
 192   // reserved IDs for special purposes
 193   static private int uniqueIDcount = 10;
 194
 195
 196   // Use these data structures to track progress of
 197   // processing all methods in the program, and by methods
 198   // TaskDescriptor and MethodDescriptor are combined
 199   // together, with a common parent class Descriptor
 200   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToInitialParamAllocGraph;
 201   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToCompleteOwnershipGraph;
 202   private Hashtable<FlatNew,       AllocationSite>           mapFlatNewToAllocationSite;
 203   private Hashtable<Descriptor,    HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
 204   private Hashtable<MethodContext, Integer>                  mapMethodContextToNumUpdates;
 205   private Hashtable<Descriptor,    HashSet<MethodContext> >  mapDescriptorToAllMethodContexts;
 206
 207   // Use these data structures to track progress of one pass of
 208   // processing the FlatNodes of a particular method
 209   private HashSet  <FlatNode>                 flatNodesToVisit;
 210   private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
 211   private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
 212
 213   // descriptorsToAnalyze identifies the set of tasks and methods
 214   // that are reachable from the program tasks, this set is initialized
 215   // and then remains static
 216   private HashSet<Descriptor> descriptorsToAnalyze;
 217
 218   // descriptorsToVisit is initialized to descriptorsToAnalyze and is
 219   // reduced by visiting a descriptor during analysis.  When dependents
 220   // must be scheduled, only those contained in descriptorsToAnalyze
 221   // should be re-added to this set
 222   private HashSet<MethodContext> methodContextsToVisit;
 223
 224   // a special field descriptor for all array elements
 225   private static FieldDescriptor fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
 226                                                                  new TypeDescriptor("Array[]"),
 227                                                                  "elements",
 228                                                                  null,
 229                                                                  false);
 230
 231   // a special temp descriptor for setting more than one parameter label
 232   // to the all-aliased-parameters heap region node
 233   protected static TempDescriptor tdAliasedParams = new TempDescriptor("_AllAliasedParams___");
 234
 235
 236   // for controlling DOT file output
 237   private boolean writeDOTs;
 238   private boolean writeAllDOTs;
 239
 240
 241
 242   // this analysis generates an ownership graph for every task
 243   // in the program
 244   public OwnershipAnalysis(State state,
 245                            TypeUtil tu,
 246                            CallGraph callGraph,
 247                            int allocationDepth,
 248                            boolean writeDOTs,
 249                            boolean writeAllDOTs,
 250                            String aliasFile) throws java.io.IOException {
 251
 252     double timeStartAnalysis = (double) System.nanoTime();
 253
 254     this.state           = state;
 255     this.typeUtil        = tu;
 256     this.callGraph       = callGraph;
 257     this.allocationDepth = allocationDepth;
 258     this.writeDOTs       = writeDOTs;
 259     this.writeAllDOTs    = writeAllDOTs;
 260
 261     descriptorsToAnalyze = new HashSet<Descriptor>();
 262
 263     mapMethodContextToInitialParamAllocGraph =
 264       new Hashtable<MethodContext, OwnershipGraph>();
 265
 266     mapMethodContextToCompleteOwnershipGraph =
 267       new Hashtable<MethodContext, OwnershipGraph>();
 268
 269     mapFlatNewToAllocationSite =
 270       new Hashtable<FlatNew, AllocationSite>();
 271
 272     mapDescriptorToAllocationSiteSet =
 273       new Hashtable<Descriptor, HashSet<AllocationSite> >();
 274
 275     mapDescriptorToAllMethodContexts =
 276       new Hashtable<Descriptor, HashSet<MethodContext> >();
 277
 278
 279     if( writeAllDOTs ) {
 280       mapMethodContextToNumUpdates = new Hashtable<MethodContext, Integer>();
 281     }
 282
 283
 284     if( state.TASK ) {
 285       // initialize methods to visit as the set of all tasks in the
 286       // program and then any method that could be called starting
 287       // from those tasks
 288       Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 289       while( taskItr.hasNext() ) {
 290         Descriptor d = (Descriptor) taskItr.next();
 291         scheduleAllCallees(d);
 292       }
 293
 294     } else {
 295       // we are not in task mode, just normal Java, so start with
 296       // the main method
 297       Descriptor d = tu.getMain();
 298       scheduleAllCallees(d);
 299
 300       /*
 301       Iterator classItr = state.getClassSymbolTable().getDescriptorsIterator();
 302       while( classItr.hasNext() ) {
 303         ClassDescriptor cd = (ClassDescriptor) classItr.next();
 304
 305         Iterator methItr = cd.getMethods();
 306         while( methItr.hasNext() ) {
 307           Descriptor d = (Descriptor) methItr.next();
 308
 309           if( d.getSymbol().equals( "main" ) ) {
 310             scheduleAllCallees(d);
 311           }
 312         }
 313       }
 314       */
 315     }
 316
 317
 318     // before beginning analysis, initialize every scheduled method
 319     // with an ownership graph that has populated parameter index tables
 320     // by analyzing the first node which is always a FlatMethod node
 321     Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
 322     while( dItr.hasNext() ) {
 323       Descriptor d  = dItr.next();
 324       OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
 325
 326       FlatMethod fm;
 327       if( d instanceof MethodDescriptor ) {
 328         fm = state.getMethodFlat( (MethodDescriptor) d);
 329       } else {
 330         assert d instanceof TaskDescriptor;
 331         fm = state.getMethodFlat( (TaskDescriptor) d);
 332       }
 333
 334       MethodContext mc = new MethodContext( d );
 335       assert !mapDescriptorToAllMethodContexts.containsKey( d );
 336       HashSet<MethodContext> s = new HashSet<MethodContext>();
 337       s.add( mc );
 338       mapDescriptorToAllMethodContexts.put( d, s );
 339
 340       //System.out.println("Previsiting " + mc);
 341
 342       og = analyzeFlatNode(mc, fm, null, og);
 343       setGraphForMethodContext(mc, og);
 344     }
 345
 346     //System.out.println("");
 347
 348     // as mentioned above, analyze methods one-by-one, possibly revisiting
 349     // a method if the methods that it calls are updated
 350     analyzeMethods();
 351
 352     //System.out.println("");
 353
 354     double timeEndAnalysis = (double) System.nanoTime();
 355     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 356     String treport = String.format( "The analysis took %.3f sec.", dt );
 357     System.out.println( treport );
 358
 359     if( aliasFile != null ) {
 360       writeAllAliases(aliasFile);
 361     }
 362   }
 363
 364   // called from the constructor to help initialize the set
 365   // of methods that needs to be analyzed by ownership analysis
 366   private void scheduleAllCallees(Descriptor d) {
 367     if( descriptorsToAnalyze.contains(d) ) {
 368       return;
 369     }
 370     descriptorsToAnalyze.add(d);
 371
 372     // start with all method calls to further schedule
 373     Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
 374
 375     if( d instanceof MethodDescriptor ) {
 376       // see if this method has virtual dispatch
 377       Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
 378       moreMethodsToCheck.addAll(virtualMethods);
 379     }
 380
 381     // keep following any further methods identified in
 382     // the call chain
 383     Iterator methItr = moreMethodsToCheck.iterator();
 384     while( methItr.hasNext() ) {
 385       Descriptor m = (Descriptor) methItr.next();
 386       scheduleAllCallees(m);
 387     }
 388   }
 389
 390
 391   // manage the set of tasks and methods to be analyzed
 392   // and be sure to reschedule tasks/methods when the methods
 393   // they call are updated
 394   private void analyzeMethods() throws java.io.IOException {
 395
 396     methodContextsToVisit = new HashSet<MethodContext>();
 397     Iterator<Descriptor> itrd2a = descriptorsToAnalyze.iterator();
 398     while( itrd2a.hasNext() ) {
 399       HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() );
 400       assert mcs != null;
 401
 402       Iterator<MethodContext> itrmc = mcs.iterator();
 403       while( itrmc.hasNext() ) {
 404         methodContextsToVisit.add( itrmc.next() );
 405       }
 406     }
 407
 408     while( !methodContextsToVisit.isEmpty() ) {
 409       MethodContext mc = methodContextsToVisit.iterator().next();
 410       methodContextsToVisit.remove(mc);
 411
 412
 413       // because the task or method descriptor just extracted
 414       // was in the "to visit" set it either hasn't been analyzed
 415       // yet, or some method that it depends on has been
 416       // updated.  Recompute a complete ownership graph for
 417       // this task/method and compare it to any previous result.
 418       // If there is a change detected, add any methods/tasks
 419       // that depend on this one to the "to visit" set.
 420
 421       System.out.println("Analyzing " + mc);
 422
 423       Descriptor d = mc.getDescriptor();
 424       FlatMethod fm;
 425       if( d instanceof MethodDescriptor ) {
 426         fm = state.getMethodFlat( (MethodDescriptor) d);
 427       } else {
 428         assert d instanceof TaskDescriptor;
 429         fm = state.getMethodFlat( (TaskDescriptor) d);
 430       }
 431
 432       OwnershipGraph og = analyzeFlatMethod(mc, fm);
 433       OwnershipGraph ogPrev = mapMethodContextToCompleteOwnershipGraph.get(mc);
 434       if( !og.equals(ogPrev) ) {
 435         setGraphForMethodContext(mc, og);
 436
 437         // only methods have dependents, tasks cannot
 438         // be invoked by any user program calls
 439         if( d instanceof MethodDescriptor ) {
 440           MethodDescriptor md = (MethodDescriptor) d;
 441           Set dependents = callGraph.getCallerSet(md);
 442           if( dependents != null ) {
 443             Iterator depItr = dependents.iterator();
 444             while( depItr.hasNext() ) {
 445               Descriptor dependent = (Descriptor) depItr.next();
 446               if( descriptorsToAnalyze.contains(dependent) ) {
 447
 448                 HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( dependent );
 449                 assert mcs != null;
 450
 451                 Iterator<MethodContext> itrmc = mcs.iterator();
 452                 while( itrmc.hasNext() ) {
 453                   methodContextsToVisit.add( itrmc.next() );
 454                 }
 455               }
 456             }
 457           }
 458         }
 459       }
 460     }
 461
 462   }
 463
 464
 465   // keep passing the Descriptor of the method along for debugging
 466   // and dot file writing
 467   private OwnershipGraph
 468   analyzeFlatMethod(MethodContext mc,
 469                     FlatMethod flatm) throws java.io.IOException {
 470
 471     // initialize flat nodes to visit as the flat method
 472     // because it is the entry point
 473
 474     flatNodesToVisit = new HashSet<FlatNode>();
 475     flatNodesToVisit.add(flatm);
 476
 477     // initilize the mapping of flat nodes in this flat method to
 478     // ownership graph results to an empty mapping
 479     mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 480
 481     // initialize the set of return nodes that will be combined as
 482     // the final ownership graph result to return as an empty set
 483     returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 484
 485
 486     while( !flatNodesToVisit.isEmpty() ) {
 487       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 488       flatNodesToVisit.remove(fn);
 489
 490       //System.out.println( "  "+fn );
 491
 492       // perform this node's contributions to the ownership
 493       // graph on a new copy, then compare it to the old graph
 494       // at this node to see if anything was updated.
 495       OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
 496
 497       // start by merging all node's parents' graphs
 498       for( int i = 0; i < fn.numPrev(); ++i ) {
 499         FlatNode pn = fn.getPrev(i);
 500         if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
 501           OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
 502           og.merge(ogParent);
 503         }
 504       }
 505
 506       // apply the analysis of the flat node to the
 507       // ownership graph made from the merge of the
 508       // parent graphs
 509       og = analyzeFlatNode(mc,
 510                            fn,
 511                            returnNodesToCombineForCompleteOwnershipGraph,
 512                            og);
 513
 514
 515       //debugSnapshot(og,fn);
 516
 517
 518
 519       // if the results of the new graph are different from
 520       // the current graph at this node, replace the graph
 521       // with the update and enqueue the children for
 522       // processing
 523       OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
 524       if( !og.equals(ogPrev) ) {
 525         mapFlatNodeToOwnershipGraph.put(fn, og);
 526
 527         for( int i = 0; i < fn.numNext(); i++ ) {
 528           FlatNode nn = fn.getNext(i);
 529           flatNodesToVisit.add(nn);
 530         }
 531       }
 532     }
 533
 534     // end by merging all return nodes into a complete
 535     // ownership graph that represents all possible heap
 536     // states after the flat method returns
 537     OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth, typeUtil);
 538     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 539     while( retItr.hasNext() ) {
 540       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 541       assert mapFlatNodeToOwnershipGraph.containsKey(frn);
 542       OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
 543       completeGraph.merge(ogr);
 544     }
 545
 546     return completeGraph;
 547   }
 548
 549
 550   private OwnershipGraph
 551   analyzeFlatNode(MethodContext mc,
 552                   FlatNode fn,
 553                   HashSet<FlatReturnNode> setRetNodes,
 554                   OwnershipGraph og) throws java.io.IOException {
 555
 556     TempDescriptor lhs;
 557     TempDescriptor rhs;
 558     FieldDescriptor fld;
 559
 560     // use node type to decide what alterations to make
 561     // to the ownership graph
 562     switch( fn.kind() ) {
 563
 564     case FKind.FlatMethod:
 565       FlatMethod fm = (FlatMethod) fn;
 566
 567       // there should only be one FlatMethod node as the
 568       // parent of all other FlatNode objects, so take
 569       // the opportunity to construct the initial graph by
 570       // adding parameters labels to new heap regions
 571       // AND this should be done once globally so that the
 572       // parameter IDs are consistent between analysis
 573       // iterations, so if this step has been done already
 574       // just merge in the cached version
 575       OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
 576       if( ogInitParamAlloc == null ) {
 577
 578         // if the method context has aliased parameters, make sure
 579         // there is a blob region for all those param labels to
 580         // reference
 581         Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
 582         if( !aliasedParamIndices.isEmpty() ) {
 583           og.makeAliasedParamHeapRegionNode( tdAliasedParams );
 584         }
 585
 586         // set up each parameter
 587         for( int i = 0; i < fm.numParameters(); ++i ) {
 588           TempDescriptor tdParam = fm.getParameter( i );
 589           Integer        paramIndex = new Integer( i );
 590
 591           if( aliasedParamIndices.contains( paramIndex ) ) {
 592             // just point this one to the alias blob
 593             og.assignTempEqualToAliasedParam( tdParam,
 594                                               tdAliasedParams,
 595                                               paramIndex );
 596           } else {
 597             // this parameter is not aliased to others, give it
 598             // a fresh parameter heap region
 599
 600             og.assignTempEqualToParamAlloc(tdParam,
 601                                            mc.getDescriptor() instanceof TaskDescriptor,
 602                                            paramIndex );
 603           }
 604         }
 605
 606         // cache the graph
 607         OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil);
 608         ogResult.merge(og);
 609         mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
 610
 611       } else {
 612         // or just leverage the cached copy
 613         og.merge(ogInitParamAlloc);
 614       }
 615       break;
 616
 617     case FKind.FlatOpNode:
 618       FlatOpNode fon = (FlatOpNode) fn;
 619       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 620         lhs = fon.getDest();
 621         rhs = fon.getLeft();
 622         og.assignTempXEqualToTempY(lhs, rhs);
 623       }
 624       break;
 625
 626     case FKind.FlatFieldNode:
 627       FlatFieldNode ffn = (FlatFieldNode) fn;
 628       lhs = ffn.getDst();
 629       rhs = ffn.getSrc();
 630       fld = ffn.getField();
 631       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 632         og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
 633       }
 634       break;
 635
 636     case FKind.FlatSetFieldNode:
 637       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 638       lhs = fsfn.getDst();
 639       fld = fsfn.getField();
 640       rhs = fsfn.getSrc();
 641       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 642         og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
 643       }
 644       break;
 645
 646     case FKind.FlatElementNode:
 647       FlatElementNode fen = (FlatElementNode) fn;
 648       lhs = fen.getDst();
 649       rhs = fen.getSrc();
 650       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 651         og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
 652       }
 653       break;
 654
 655     case FKind.FlatSetElementNode:
 656       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 657       lhs = fsen.getDst();
 658       rhs = fsen.getSrc();
 659       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 660         og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
 661       }
 662       break;
 663
 664     case FKind.FlatNew:
 665       FlatNew fnn = (FlatNew) fn;
 666       lhs = fnn.getDst();
 667       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 668         AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
 669         og.assignTempEqualToNewAlloc(lhs, as);
 670       }
 671       break;
 672
 673     case FKind.FlatCall:
 674       FlatCall fc = (FlatCall) fn;
 675       MethodDescriptor md = fc.getMethod();
 676       FlatMethod flatm = state.getMethodFlat(md);
 677       OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth, typeUtil);
 678
 679       if( md.isStatic() ) {
 680         // a static method is simply always the same, makes life easy
 681         ogMergeOfAllPossibleCalleeResults = og;
 682
 683         Set<Integer> aliasedParamIndices =
 684           ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
 685         MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
 686         OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 687
 688         if( onlyPossibleCallee == null ) {
 689           // if this method context has never been analyzed just schedule it for analysis
 690           // and skip over this call site for now
 691           methodContextsToVisit.add( mcNew );
 692
 693         } else {
 694           ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee);
 695         }
 696
 697       } else {
 698         // if the method descriptor is virtual, then there could be a
 699         // set of possible methods that will actually be invoked, so
 700         // find all of them and merge all of their results together
 701         TypeDescriptor typeDesc = fc.getThis().getType();
 702         Set possibleCallees = callGraph.getMethods(md, typeDesc);
 703
 704         Iterator i = possibleCallees.iterator();
 705         while( i.hasNext() ) {
 706           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 707           FlatMethod pflatm = state.getMethodFlat(possibleMd);
 708
 709           // don't alter the working graph (og) until we compute a result for every
 710           // possible callee, merge them all together, then set og to that
 711           OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil);
 712           ogCopy.merge(og);
 713
 714           Set<Integer> aliasedParamIndices =
 715             ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
 716           MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
 717           OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 718
 719           if( ogPotentialCallee == null ) {
 720             // if this method context has never been analyzed just schedule it for analysis
 721             // and skip over this call site for now
 722             methodContextsToVisit.add( mcNew );
 723
 724           } else {
 725             ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee);
 726           }
 727
 728           ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
 729         }
 730       }
 731
 732       og = ogMergeOfAllPossibleCalleeResults;
 733       break;
 734
 735     case FKind.FlatReturnNode:
 736       FlatReturnNode frn = (FlatReturnNode) fn;
 737       rhs = frn.getReturnTemp();
 738       if( rhs != null && !rhs.getType().isImmutable() ) {
 739         og.assignReturnEqualToTemp(rhs);
 740       }
 741       setRetNodes.add(frn);
 742       break;
 743     }
 744
 745     return og;
 746   }
 747
 748
 749   // insert a call to debugSnapshot() somewhere in the analysis to get
 750   // successive captures of the analysis state
 751   int debugCounter        = 0;
 752   int numStartCountReport = 0;
 753   int freqCountReport     = 1000;
 754   int iterStartCapture    = 20000;
 755   int numIterToCapture    = 400;
 756   void debugSnapshot(OwnershipGraph og, FlatNode fn) {
 757     ++debugCounter;
 758     if( debugCounter > numStartCountReport &&
 759         debugCounter % freqCountReport == 0 ) {
 760       System.out.println("    @@@ debug counter = "+debugCounter);
 761     }
 762     if( debugCounter > iterStartCapture ) {
 763       System.out.println("    @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
 764       String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
 765       if( fn != null ) {
 766         graphName = graphName+fn;
 767       }
 768       try {
 769         og.writeGraph(graphName, true, true, false, false, false);
 770       } catch( Exception e ) {
 771         System.out.println("Error writing debug capture.");
 772         System.exit(0);
 773       }
 774     }
 775     if( debugCounter == iterStartCapture + numIterToCapture ) {
 776       System.out.println("Stopping analysis after debug captures.");
 777       System.exit(0);
 778     }
 779   }
 780
 781
 782
 783   // this method should generate integers strictly greater than zero!
 784   // special "shadow" regions are made from a heap region by negating
 785   // the ID
 786   static public Integer generateUniqueHeapRegionNodeID() {
 787     ++uniqueIDcount;
 788     return new Integer(uniqueIDcount);
 789   }
 790
 791
 792   private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og)
 793   throws IOException {
 794
 795     mapMethodContextToCompleteOwnershipGraph.put(mc, og);
 796
 797     // arguments to writeGraph are:
 798     // boolean writeLabels,
 799     // boolean labelSelect,
 800     // boolean pruneGarbage,
 801     // boolean writeReferencers
 802     // boolean writeParamMappings
 803
 804     if( writeDOTs ) {
 805
 806       if( !writeAllDOTs ) {
 807         og.writeGraph(mc, true, true, true, false, false);
 808
 809       } else {
 810         if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
 811           mapMethodContextToNumUpdates.put(mc, new Integer(0) );
 812         }
 813         Integer n = mapMethodContextToNumUpdates.get(mc);
 814         og.writeGraph(mc, n, true, true, true, false, false);
 815         mapMethodContextToNumUpdates.put(mc, n + 1);
 816       }
 817     }
 818   }
 819
 820
 821   // return just the allocation site associated with one FlatNew node
 822   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
 823
 824     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
 825       AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
 826
 827       // the newest nodes are single objects
 828       for( int i = 0; i < allocationDepth; ++i ) {
 829         Integer id = generateUniqueHeapRegionNodeID();
 830         as.setIthOldest(i, id);
 831       }
 832
 833       // the oldest node is a summary node
 834       Integer idSummary = generateUniqueHeapRegionNodeID();
 835       as.setSummary(idSummary);
 836
 837       mapFlatNewToAllocationSite.put(fn, as);
 838     }
 839
 840     return mapFlatNewToAllocationSite.get(fn);
 841   }
 842
 843
 844   // return all allocation sites in the method (there is one allocation
 845   // site per FlatNew node in a method)
 846   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
 847     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
 848       buildAllocationSiteSet(d);
 849     }
 850
 851     return mapDescriptorToAllocationSiteSet.get(d);
 852
 853   }
 854
 855   private void buildAllocationSiteSet(Descriptor d) {
 856     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
 857
 858     FlatMethod fm;
 859     if( d instanceof MethodDescriptor ) {
 860       fm = state.getMethodFlat( (MethodDescriptor) d);
 861     } else {
 862       assert d instanceof TaskDescriptor;
 863       fm = state.getMethodFlat( (TaskDescriptor) d);
 864     }
 865
 866     // visit every node in this FlatMethod's IR graph
 867     // and make a set of the allocation sites from the
 868     // FlatNew node's visited
 869     HashSet<FlatNode> visited = new HashSet<FlatNode>();
 870     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
 871     toVisit.add(fm);
 872
 873     while( !toVisit.isEmpty() ) {
 874       FlatNode n = toVisit.iterator().next();
 875
 876       if( n instanceof FlatNew ) {
 877         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
 878       }
 879
 880       toVisit.remove(n);
 881       visited.add(n);
 882
 883       for( int i = 0; i < n.numNext(); ++i ) {
 884         FlatNode child = n.getNext(i);
 885         if( !visited.contains(child) ) {
 886           toVisit.add(child);
 887         }
 888       }
 889     }
 890
 891     mapDescriptorToAllocationSiteSet.put(d, s);
 892   }
 893
 894
 895   private HashSet<AllocationSite>
 896   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
 897
 898     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
 899     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
 900     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
 901
 902     toVisit.add(td);
 903
 904     // traverse this task and all methods reachable from this task
 905     while( !toVisit.isEmpty() ) {
 906       Descriptor d = toVisit.iterator().next();
 907       toVisit.remove(d);
 908       visited.add(d);
 909
 910       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
 911       Iterator asItr = asSet.iterator();
 912       while( asItr.hasNext() ) {
 913         AllocationSite as = (AllocationSite) asItr.next();
 914         TypeDescriptor typed = as.getType();
 915         if( typed != null ) {
 916           ClassDescriptor cd = typed.getClassDesc();
 917           if( cd != null && cd.hasFlags() ) {
 918             asSetTotal.add(as);
 919           }
 920         }
 921       }
 922
 923       // enqueue callees of this method to be searched for
 924       // allocation sites also
 925       Set callees = callGraph.getCalleeSet(d);
 926       if( callees != null ) {
 927         Iterator methItr = callees.iterator();
 928         while( methItr.hasNext() ) {
 929           MethodDescriptor md = (MethodDescriptor) methItr.next();
 930
 931           if( !visited.contains(md) ) {
 932             toVisit.add(md);
 933           }
 934         }
 935       }
 936     }
 937
 938
 939     return asSetTotal;
 940   }
 941 }